第3章chapter3
进程同步1.1微型计算机简介操作系统引入进程后,虽然改善了资源的利用率,提高了系统的吞吐量,但是系统中的多个进程由于竞争使用系统资源,导致它们之间存在一定的相互依赖、相互制约的关系。为了有效地协调各个并发进程间的关系,系统必须采用同步机制,确保进程之间能正确地竞争资源,并相互协调、相互合作。
3.1基本概念[4/5]3.1.1进程的制约关系多道程序环境下,系统中存在着多个并发进程。这些并发进程之间可能相互独立,即一个进程的执行不影响其他进程的执行,此时系统无须对这些并发进程进行特别控制;并发进程之间也可能彼此相关、相互影响,即一个进程的执行可能影响其他进程的执行结果,此时,系统就需要合理地控制和协调这些进程的执行。根据共享资源性质的不同,并发进程之间的关系可以分为间接制约关系和直接制约关系。
（1）间接制约关系:也称“竞争关系”,指系统中多个进程访问相同的资源,其中一个进程访问资源时,其他需访问此资源的进程必须等待,只有当该进程释放该资源后,其他进程才能访问。进程的竞争关系可通过进程互斥方式来解决。
（2）直接制约关系:也称“合作关系”,指系统中多个进程需要相互合作才能完成同一任务。例如,假设输入进程和计算进程共同使用一个单缓冲区,那么当输入进程将数据写入缓冲区后,计算进程才能开始计算;当计算进程将缓冲区中的数据取走后,输入进程才可以再次向缓冲区中写入数据。进程的合作关系可通过进程同步机制来实现。
3.1.2进程互斥与同步[2]1.临界资源及临界区为了便于控制和管理竞争资源,系统引入了临界资源和临界区的概念:
（1）临界资源:指一次只允许一个进程访问的资源。临界资源在任何时刻都不允许两个及以上并发进程同时访问。系统中有许多独占性硬件资源（如卡片输入机和打印机等）和软件资源（如变量、表格、队列、栈和文件等）均属于临界资源。
（2）临界区:指进程访问临界资源的那段程序代码。
系统若能保证进程互斥地进入各自的临界区,便可实现临界资源的互斥访问。
2.进程互斥
进程互斥是指当一个进程进入临界区使用临界资源时,其他进程必须等待。当占用临界资源的进程退出临界区后,另外一个进程才被允许使用临界资源。
◆计算机操作系统原理第◆3章进程同步若要实现各进程对临界资源的互斥访问,则需要保证各进程互斥地进入自己的临界区。进程在进入临界区之前,应先对临界资源进行检查,确认该资源是否正在被访问。若临界资源正被其他进程访问,则该进程不能进入临界区;若临界资源空闲,该进程便可以进入临界区对临界资源进行访问,并将该资源的标志设置为正在被访问。因此,进程访问临界资源前,应增加一段用于进行上述检查的代码,这段代码称为进入临界区;临界资源访问结束后,也要增加一段用于将临界资源标志恢复为未被访问的代码,这段代码称为退出临界区。临界区的框架如下:do{
进入临界区
访问临界资源
退出临界区
其余代码
}while(1);3.进程同步
进程同步是指多个进程为了合作完成同一个任务,在执行次序上相互协调、相互合作,在一些关键点上还需要相互等待或相互通信。
进程同步的例子在现实生活中随处可见,如司机与售票员的关系。公共汽车的司机负责开车和到站停车,售票员负责售票和开关车门,他们之间是相互合作、相互配合的。例如车门关闭后才能启动,到站停车后才能打开车门,即“启动汽车”在“关闭车门”之后,而“打开车门”在“到站停车”之后。司机和售票员之间的活动关系如图31所示。
图31司机与售票员的关系
若进程P1和P2分别表示司机和售票员,当它们并发向前推进时,则需满足以下要求:
（1）若P1推进到①,但P2未到达②时,则P1应等待,直到P2到达②为止。
（2）若P2推进到④,但P1未到达③时,则P2应等待,直到P1到达③为止。
（3）若P1在①处等待,则当P2到达②处时,应通知（唤醒）P1。
（4）若P2在④处等待,则当P1到达③处时,应通知（唤醒）P2。
由此可知,为了协调进程推进次序,相互合作的并发进程有时需要互相等待与互相唤醒。
4.同步与互斥的关系
同步与互斥是并发进程之间两种重要关系,其中互斥反映了进程间的竞争关系,而同步则反映了进程间的合作关系。
进程互斥是进程同步的一种特殊情况。例如,某个进程进入临界区时,其他进程不允许进入临界区。当进程完成任务离开临界区,并归还临界资源后,唤醒其等待进入临界区的进程。这说明互斥的进程也存在特殊的合作关系。因此,互斥是一种特殊的同步关系。
互斥所涉及的并发进程之间只是竞争获得共享资源的使用权,这种竞争没有固定的、必然的联系,谁竞争到资源,谁就拥有资源的使用权,直到不需要时才归还;而同步所涉及的并发进程之间有一种必然的联系,在进程同步过程中,即使没有进程使用共享资源,尚未得到同步消息的进程也不能去使用共享资源。
5.临界区的管理准则
为了实现进程的同步与互斥,可以利用软件方法或在系统中设置专门的同步机制,协调各个并发进程。同步机制必须遵循以下4条准则:
（1）闲则让进:当临界资源处于空闲状态时,系统应允许一个请求访问该临界资源的进程进入自己的临界区,访问该临界资源。
（2）忙则等待:当临界资源正在被访问时,其他试图进入临界区访问该临界资源的进程必须等待,以保证临界资源的互斥访问。
（3）有限等待:对于等待访问临界资源的进程,系统应保证这些等待进程在有限时间内能进入临界区,访问临界资源,以避免陷入“死等”状态。
（4）让权等待:当进程不能进入临界区访问临界资源时,应立即释放CPU,以免该进程陷入“忙等”（即等待时占有CPU）状态。
3.2同步机制
进程同步机制的基本目标是在功能上保证进程能够正确地互斥执行各自的临界区,其具体的实现方法包括软件方法、硬件方法、信号量方法和管程这四大类。
3.2.1软件方法
软件方法是指通过编写程序代码方式进入临界区,以访问临界资源。此方法既适用于单CPU环境,也适用于多CPU环境,只需这些CPU共享一个存储区,且各个进程对该存储区串行访问即可。
下面通过程序伪代码方式说明实现进程之间互斥访问临界资源的软件方法。
1.算法1
该算法的基本思想:若一个进程申请使用临界资源,应先查看该资源当前是否被一个进程访问。若资源正在被访问,则该进程只能等待,否则进入自己的临界区执行。下面是进程P1和P2的程序伪代码,其中inside1和inside2为布尔型变量,且初值均false,表示P1和P2均不在其临界区内。booleaninside1,inside2;
inside1=false;//P1不在其临界区内
inside2=false;//P2不在其临界区内
cobegin
processP1(){
while(inside2);
inside1=ture;
访问临界资源;
inside1=false;
}
processP2(){
while(inside1);
inside2=ture;
访问临界资源;
inside2=false;
}
coend该算法虽然实现了进程互斥管理的“闲则让进”准则,保证了每次只允许一个进程进入临界区,但违背了“忙则等待”准则。例如,假设P1和P2先后执行“while（inside2）;”和“while（inside1）;”,发现对方均不在临界区内,则它们执行“inside1=true;”和“inside2=true;”,并进入了各自临界区内,同时访问该临界资源。
2.算法2
算法1违背了“忙则等待”准则,没有实现对临界区的互斥访问。算法2对其进行了改进,即进程若想进入临界区,必须抢先将自己的标志设置为true,以防止对方再进入临界区。
算法2的程序伪代码如下:booleaninside1,inside2;
inside1=false;//P1不在其临界区内
inside2=false;//P2不在其临界区内
cobegin
processP1(){
inside1=ture;
while(inside2);
访问临界资源;
inside1=false;
}
processP2(){
inside2=ture;
while(inside1);
访问临界资源;
inside2=false;
}
coend算法2虽然解决了“忙则等待”问题,但存在着“有限等待”问题。例如,当P1和P2都判断对方不在临界区时,P1执行“inside1=true;”,此时P2同样也执行“inside2=true;”,然后P1和P2分别执行“while(inside2);”和“while(inside1);”时,均因为条件不满足,而无法往下执行,导致P1和P2将陷入无限等待状态。
3.Peterson算法
Peterson采用了原语形式,提出了一种表述简单的算法,很好地解决了临界区互斥的问题,能满足临界区访问的四个条件。Peterson算法的基本思想:当一个进程需要进入临界区,需先调用enter_section()函数,判断是否可以安全进入临界区,若不能则等待;当从临界区退出后,调用leave_section()函数,允许其他进程进入临界区。Peterson算法流程如下:#defineFALSE0
#defineTRUE1
#defineN2//竞争资源的进程数目
intobserver;//轮到哪个进程观察要进入临界区的情况
intwanted_in(N);//各进程希望进入临界区的标志
enter_section(process)//进入临界区的互斥控制函数
intprocess;//进程编号,0或1
{
intother;//对方进程号
other=1-process;
wanted_in\[process\]=TRUE;//本进程要进入临界区
observer=process;//观察进入临界区的情况,设置标志位
while(observer==process&&wanted_in\[other\]);//等待,什么都不做
}
leaver_section(process)//退出临界区函数
intprocess;
{
wanted_in\[process\]=FALSE;//离开了临界区
}3.2.2硬件方法
软件方法相对复杂且容易出错,因而现在系统较少采用。目前常用的是通过硬件方法实现同步互斥操作。
1.开关中断法
开关中断法采用中断方式,借助硬件中断机构实现临界区的管理。当进程进入临界区后,关闭系统中断;离开临界区时,重新开启系统中断。由于进程切换是由时钟或其他中断导致,因而当中断被屏蔽后,其他进程无法获得CPU调度,导致无法运行,从而实现了临界区的互斥访问。进程进入临界区后,只要不自行挂起,就会连续地执行,直至退出临界区,并在执行开中断指令后,才可能重新调度,允许其他进程进入临界区。do{
开中断
访问临界资源
关中断
其余代码
}while(1);开关中断方法具有效率高、简单易行,且系统不会出现忙等现象;但其缺点也较明显,如只适用于单CPU系统和系统效率较低,进而影响系统处理紧迫事件的能力。多CPU系统中,禁止中断只会影响当前CPU,而其他CPU上并行执行的进程仍然能不受阻碍地进入临界区。
2.测试与设置方法
测试和设置（TestandSet,TS）方法利用指令读取内存中某个变量的值后,重新给它赋一个新值。TS指令定义如下:intTS(inttarget){
inttemp;
temp=target;
target=1;
return(temp);
}TS指令首先读取当前变量的值,作为参数返回,同时将其值置为1。由于该指令是原子操作,因此,它在执行期间不允许被打断,即所有语句要么全执行,要么都不执行。
TS指令可用来实现进程互斥操作。具体地,设置一个共享变量（如lock）,置其初值为0,表示临界区内没有进程。每个进程在进入临界区之前,先使用TS指令测试该共享变量。若其值为0,则进入临界区,并将其值置为1;若其值为1,则表明其他进程已进入临界区,此时该进程需等待。进程离开临界区时,需将共享变量的值置为0。使用TS指令的互斥算法如下:while(1){
while(TS(lock));
访问临界资源;
lock=0;
}尽管上面算法可以实现进程互斥操作,但仍然存在“忙碌等待”,浪费了CPU宝贵的资源,因而实际情况中较少使用。
3.swap指令
Swap指令也称交换指令,其功能是交换两个变量的值,具体实现如下:voidswap(inta,b){
inttemp;
temp=a;a=b;b=temp;
}Swap指令是原子操作,执行期间是不可分割的。使用swap指令实现进程互斥时,需对临界区（可表示为一组共享变量）定义一个全局变量（如lock）,并对每个进程定义一个局部变量（如key）。利用swap指令实现的进程互斥算法具体实现如下:key=1;
do{
swap(&lock,&key);
whlie(key==1);
访问临界资源;
lock=0;
其余代码;
}while(1);进程在进入临界区前,利用swap指令交换lock和key的值,检查key的状态,判断是否有进程已进入临界区。若其他进程已进入,则该进程不断重复交换和检查过程,直到其他进程退出临界区。
3.3信号量方法
由于硬件方法采用原语或指令形式,将修改和检查作为一个不可分割的整体,因而比软件方法具有明显的优势。然而,进入临界区的进程是随机选择的,使得部分进程可能一直未被选择,从而导致“饥饿”现象。为此,实际系统中常采用信号量机制和PV操作进程互斥。
信号量机制是指两个或多个进程利用彼此之间收发的简单信号来实现并发执行,其中进程若未收到指定的信号,则停留在特定的地方,直至收到了信号后才能继续往下执行。信号量机制目前是一种卓有成效的进程同步机制,已被广泛应用于各种系统。
3.3.1信号量机制[2]1.信号量的概念信号量（Semaphore）是一种特殊变量,它用来表示系统中资源的使用情况,其值与临界区内所使用的临界资源的状态有关。如果信号量S是一个整型变量,则其值表示系统中某类资源的数目。S必须且只能设置一次初值,并大于或等于0。当其值大于0时,表示系统中对应可用资源的数目;当其值小于0时,其绝对值表示等待该类资源的进程的数目;当其值等于0时,表示系统中对应资源已用完,且没有进程等待该类资源。
2.信号量的操作
信号量机制中,信号量的值仅能通过两个标准的原语操作来改变,它们分别是P操作和V操作。信号量S的P、V操作表示为:P(S)和V(S),也称为wait和signal。由于P、V操作是原语,因此,它们在执行的过程中不可中断。
利用信号量和P、V操作既可以解决并发进程对资源的竞争问题,又可以解决并发进程的合作问题。进程在互斥访问临界资源、进入临界区前,先执行P操作,退出临界区后应执行V操作。
3.3.2信号量的分类
信号量机制自提出以来得到了很大发展,已从最初的单信号量机制发展到多信号量机制。
1.单信号量机制
单信号量机制是指信号量所涉及的变量只有一个。根据变量的类型,单信号量机制包括互斥型信号量、整型信号量和记录型信号量等,其中互斥型信号量最简单,而记录型信号量表达能力最强。
（1）互斥型信号量
互斥型信号量也称0/1信号量,它的值为0、1或FALSE、TRUE,表示当前信号量所代表的临界资源是否可用,其中1或TRUE表示临界资源可用,而0或FALSE表示临界资源当前已被占用。
互斥型信号量定义为:booleanS;//互斥信号量的定义互斥型信号量的P、V操作描述如下:voidP(booleanS){
while(!S);//若信号量为FALSE,表示资源不可用,继续测试
S=FALSE;//表示可以进入临界区,同时不允许其他进程进入
}
voidV(booleanS){
S=TRUE;//允许其他进程进入临界区
}（2）整型信号量
互斥型信号量虽然能保证进程互斥地访问临界资源,但不能反映临界资源的数量。针对这个问题,提出了整型信号量,即信号量的类型为整型。整型信号量S的初始值应大于等于0,其值不仅能表示临界资源是否空闲,还具有如下物理意义:
①S>0:表示当前有S个资源可用;
②S=0:表示当前没有资源可用,且没有等待该资源的进程;
③S<0:表示当前有|S|个进程正在等待此资源。
整型信号量定义为:intS;//整型信号量定义整型信号量的P、V操作描述如下:voidP(intS){
S--;//表示申请一个资源
while(S<0);//若信号量为0,表示无资源可用,反复测试
}……
新书资讯