读书频道 > 网站 > 网页设计 > 新编操作系统习题与解析
3.1.1 要点归纳
13-06-02    奋斗的小年轻
收藏    我要投稿   

本文所属图书 > 新编操作系统习题与解析

本书按照操作系统教学大纲的要求,并参照全国联考大纲编写。全书共6章,主要内容包括:操作系统概述、处理器管理、进程同步、通信和死锁、存储器管理、文件管理及设备管理。每章按知识点分节,每节先总结核心概念...立即去当当网订购
3.1  知识点1:进程同步

3.1.1  要点归纳

1. 进程同步的基本概念
并发执行的进程之间存在着不同的相互制约关系,为了协调进程之间的相互制约关系,需要实现进程同步或互斥。
(1)临界资源
设有两个进程A、B共享一台打印机,若让它们任意使用,则可能发生的情况是两个进程的输出结果交织在一起,很难区分。解决的方法是进程A要使用打印机时应先提出申请,一旦系统把打印机分配给进程A,打印机就一直被进程A所占有,进程B若要使用该打印机,就必须等待,直到进程A用完并释放打印机后,系统才能将该打印机分配给进程B使用。
由此可见,虽然计算机系统中的多个进程可以共享系统中的各种资源,然而其中许多资源一次只能为一个进程所使用,把一次仅允许一个进程使用的资源称为临界资源。许多物理设备都属于临界资源,如打印机、绘图机等。除物理设备外,还有许多变量、数据等都可以被若干进程共享,它们也属于临界资源。
在每个进程中,访问临界资源的那段程序称为临界区。为了保证临界资源的正确使用,可以把临界资源的访问过程分成如图3.1所示的4个部分:
l       进入区。为了进入临界区使用临界资源,在进入区需要检查可否进入临界区;如果可以进入临界区,则应设置正在访问临界区的标志,以阻止其他进程同时进入临界区。
l       临界区。进程中访问临界资源的那段代码,又称临界段。
l       退出区。将正在访问临界区的标志清除。
l       剩余区。代码中的其余部分。

图3.1  临界区的访问过程
(2)进程互斥
在操作系统中,当一个进程进入临界区使用临界资源时,另一个进程必须等待,当占用临界资源的进程退出临界区后,才允许另一进程去访问此临界资源,将进程之间的这种相互制约关系称为进程互斥。
为禁止两个进程同时进入临界区,可以采用软件方法或同步机构来协调它们。但是,不论是软件方法或同步机构都应遵循下述准则:
l       空闲让进。当没有进程处于临界区时,可以允许一个请求进入临界区的进程立即进入临界区。
l       忙则等待。当已有进程进入临界区时,其他试图进入临界区的进程必须等待。
l       有限等待。对要求访问临界资源的进程,应保证能在有限时间内进入临界区,即既不会死锁,也不会饥饿
l       让权等待。当进程不能进入临界区时,应释放CPU。
(3)进程同步
一般来说,一个进程相对于另一个进程的运行速度是不确定的,但是相互合作的几个进程需要在某些确定点上协调它们的工作。所谓进程同步是指多个相互合作的进程,在一些关键点上可能需要互相等待或互相交换信息。
例如,系统中有两个合作的进程,它们共用一个单缓冲区,其中一个进程为计算进程,完成对数据的计算工作;另一个为打印进程,负责打印计算结果。当计算进程对数据的计算尚未完成时,计算的结果没有送入缓冲区,打印进程不能执行打印操作。一旦计算进程把计算结果送入缓冲区后,就应给打印进程发送一个信号,打印进程收到该信号后,便可以从缓冲区中取出计算结果进行打印。在打印进程尚未把缓冲区中的计算结果取出打印之前,计算进程也不能把下一次的计算结果送入缓冲区中。只有在打印进程取出缓冲区中的内容,给计算进程发出一个信号后,计算进程才能将下一次的计算结果送入缓冲区中。计算进程和打印进程之间就是使用这种发送信号的方式实现同步的。
2. 实现临界区互斥的基本方法
解决互斥问题既可以采用软件方法,也可以采用硬件方法。
(1)软件实现方法
软件实现方法就是在进入区设置和检查一些标志来标明是否有进程在临界区中,如果已有进程在临界区,则在进入区通过循环检查进行等待,进程离开临界区后则在退出区修改标志。其中主要问题是设置什么标志和如何检查标志。
例如,有两个进程P0和P1互斥地共享某个临界资源。P0和P1是循环进程,它们执行一个无限循环程序,每次使用该资源一个有限时间段。
算法1:设置一个公共整型变量turn,用来指示允许进入临界区的进程标识。若turn为0,则允许进程P0进入临界区;否则循环检查该变量,直到turn变为本进程标识;在退出区,修改允许进入进程的标识turn为1。进程P1的算法与此类似。两个进程的程序结构如下:
int turn=0;                         //公共变量
进程P0
do
{   while(turn!=0);               //进入区
    进程P0的临界区代码;              //临界区
    turn=1;                         //退出区
    进程P0的其他代码;               //剩余区
} while(true);
进程P1
do
{   while(turn!=1);               //进入区
    进程P1的临界区代码;              //临界区
    turn=0;                         //退出区
    进程P1的其他代码;               //剩余区
} while(true);
分析:当进程P0退出临界区后将turn设置为1,以便允许进程P1进入临界区,但如果进程P1暂时并未要求访问该临界资源,而P0又想再次访问临界资源,则P0将无法进入临界区。可见,此算法不能保证实现“空闲让进”准则。
结论:本算法可以保证两个进程互斥访问临界资源,但存在的问题是强制两个进程以交替次序进入临界区,造成资源利用不充分的情况。
算法2:设置标志数组flag[]表示进程是否在临界区中执行,初值均为false。在每个进程访问该临界资源之前,先检查另一个进程是否在临界区中,若不在则修改本进程的临界区标志为true并进入临界区,在退出区修改本进程临界区标志为false。两进程的程序结构如下:
enum  boolean {false,true};
boolean  flag[2] = {false,false};         //公共变量
进程P0
do
{   while (flag[1]);                       //进入区
    flag[0]=true;                           //进入区
    进程P0的临界区代码;                       //临界区
    flag[0]=false;                          //退出区
    进程P0的其他代码;                         //剩余区
} while(true);
进程P1
do
{   while (flag[0]);                       //进入区
    flag[1]=true;                           //进入区
    进程P1的临界区代码;                       //临界区
    flag[1]=false;                          //退出区
    进程P1的其他代码;                         //剩余区
} while(true)
分析:当两个进程都未进入临界区时,它们各自的访问标志值都为false,若此时两个进程几乎同时都想进入临界区,并且都发现对方标志值为false,于是两个进程同时进入了各自的临界区,这就违背了临界区的访问原则“忙则等待”。
结论:本算法不能解决临界资源互斥访问的问题。
算法3:本算法仍然设置标志数组flag[],但标志用来表示进程是否希望进入临界区。在每个进程访问临界资源之前,先将自己的标志flag[i]设置为true,表示进程希望进入临界区,然后再检查另一个进程的标志。若另一个进程的标志为true,则进程等待;否则进入临界区。两进程的程序结构如下:
enum  boolean {false,true};
boolean  flag[2] = {false,false};       //公共变量
进程P0
do
{   flag[0]=true;                        //进入区
    while (flag[1]);                       //进入区
    进程P0的临界区代码;                       //临界区
    flag[0]=false;                          //退出区
    进程P0的其他代码;                         //剩余区
} while(true);
进程P1
do
{   flag[1]=true;                        //进入区
    while (flag[0]);                       //进入区
    进程P1的临界区代码;                       //临界区
    flag[1]=false;                          //退出区
    进程P1的其他代码;                         //剩余区
} while(true);
分析:当两个进程几乎同时都想进入临界区时,它们分别将自己的标志值设置为true(即两个进程都分别执行flag[0]=true、flag[1]=true后),并且同时去检查对方的状态(都要执行while语句),发现对方也要进入临界区,于是双方互相谦让,结果谁也进不了临界区。
结论:可以有效地防止两个进程同时进入临界区,但存在两个进程都进不了临界区的问题,即会出现“饥饿”现象。
所谓“饥饿”现象是指在一个可以预见的时间内,一个或多个进程的需求得不到满足,如都不能访问临界资源。产生“饥饿”现象的主要原因是:在一个动态系统中,操作系统对每类系统资源(如临界资源)需要确定一个分配策略,有时资源分配策略是不公平的,即不能保证等待时间上界的存在,某些进程可能长时间等待,当等待时间给进程的推进和响应带来明显的影响时,称发生了进程饥饿。
算法4:本算法中标志数组flag[]表示进程是否希望进入临界区或是否正在临界区中执行,此外,还设置了一个turn变量,用于指示允许进入临界区的进程标识。两个进程的程序结构如下:
enum boolean {false,true};
boolean flag[2] = {false,false};
int turn;
进程P0
do
{   flag[0]=true;                           //进入区
        turn=1;                               //进入区
        while(flag[1] && turn==1);         //进入区
        进程P0的临界区代码;                   //临界区
        flag[0]=false;                      //退出区
        进程P0的其他代码;                     //剩余区
} while(true);
进程P1
do
{   flag[1]=true;                           //进入区
        turn=0;                               //进入区
        while(flag[0] && turn==0);         //进入区
        进程P1的临界区代码;                   //临界区
        flag[1]=false;                      //退出区
        进程P1的其他代码;                     //剩余区
} while(true);
分析:本算法的基本思想是算法3和算法1的结合。利用flag[]解决临界资源的互斥访问,而利用turn解决“饥饿”现象。
结论:本算法既能解决临界资源的互斥访问,又不会出现“饥饿”现象。
(2)硬件实现方法
① 开、关中断方法
当一个进程正在使用CPU执行它的临界区代码时,要防止其他进程再进入其临界区访问的最简单方法是禁止一切中断发生。因为CPU只在发生中断时引起进程切换,这时禁止中断就能保证当前运行进程将临界区代码顺利地执行完,从而保证了互斥的正确实现,然后再执行开中断。下面是用开、关中断方法实现互斥的典型模式:

关中断;
临界区;
开中断;

采用开/关中断的方法实现进程互斥既简单又有效,但同时也存在一些不足。如这种方法限制了CPU交替执行程序的能力,因此执行的效率将会明显降低;对于内核来说,当它在执行更新变量或列表的几条指令期间将中断关闭是很方便的,但将关中断的权力交给用户进程则很不明智,若一个进程关中断之后不再开中断,则系统可能会因此终止。
② 硬件指令方法
许多计算机中都提供了专门的硬件指令,完成对一个字或字节中的内容进行检查、修改或交换两个字或字节内容的功能,利用这些指令可以解决临界区的互斥问题。在多道程序环境中,当多个进程共同访问或修改同一个共享变量时,由于中断的原因,使得一个进程对一个共享变量的检查和修改不能作为一个整体来执行,在这两个动作(通常要由2~3条指令来完成)之间,可以插入其他进程对此共享变量的访问和修改,从而破坏了此共享变量数据的完整性和正确性。现在,用一条指令来检查和修改这两个功能,这样中断就不可能发生,所以不会影响此共享变量数据的完整性。
实现这种功能的硬件指令有两种,即TS指令和Swap指令。
TS(Test-and-Set)指令的功能是读出指定标志后把该标志设置为真。TS指令的功能描述如下:
boolean  TS(boolean  *1ock)
{   boolean old;
    old = *lock;
    *lock = true;
    return old;
}
为了实现多个进程对临界资源的互斥访问,可以为每个临界资源设置一个共享布尔变量lock(锁变量),用来表示资源的两种状态:true表示正被占用,false表示空闲,初值为false。在进程访问临界资源之前,进行TS检查和修改标志lock;若有进程在临界区,则重复检查,直到进程退出。利用TS指令实现进程互斥的算法描述如下:
while TS(&lock);          //若lock为true,则执行while循环重复检测,即等待
进程的临界区代码CS;
lock = false;
进程的其他代码;
TS是一条完整的指令,在其执行中间是不会被中断的,即是不可分割指令,所以保证了锁的测试和关闭操作的连续性。
Swap指令(或Exchange指令)的功能是交换两个字(字节)的内容。Swap指令的功能描述如下:
Swap(boolean *a,boolean *b)
{   boolean  temp;
    temp = *a;
    *a = *b;
    *b = temp;
}
利用Swap指令实现进程互斥时,应为每个临界资源设置一个共享布尔变量lock(锁变量),初值设置为false;在每个进程中再设置一个局部布尔变量key,用于与lock交换信息。在进入临界区之前先利用Swap指令交换lock与key的内容,然后检查key的状态;有进程在临界区时,重复交换和检查过程,直到进程退出。利用Swap指令实现进程互斥的算法描述如下:
key = true;
while (key!=false)       //若key为true则重复执行Swap指令,即等待
     Swap(&lock,&key);
进程的临界区代码CS;
lock = false;
进程的其他代码;
Swap和TS一样,也是不可分割指令。
具体而言,硬件方法的优点体现在以下几个方面:
l       适用范围广。硬件方法适用任何个数的进程,在单处理器和多处理器环境中完全相同。
l       简单。硬件方法的标志设置简单,含义明确,容易验证其正确性。
l       支持多个临界区。在一个进程内有多个临界区时,只需为每个临界区设立一个布尔变量。
硬件方法有许多优点,但也有一些自身无法克服的缺点。这些缺点主要包括:进程在等待进入临界区时要耗费处理器时间,不能实现让权等待;由于进入临界区的进程是从等待进程中随机选择的,有的进程可能一直未被选上,从而导致“饥饿”现象。
3. 信号量
(1)什么是信号量
信号量是一种实现进程同步互斥的工具。信号量主要有两种。
① 整型信号量
Dijkstra把整型信号量定义为一个用于表示资源个数的整型量S。
② 记录型信号量
记录型信号量是零型信号量的发展,它含有一个整型变量和一个等待队列,其定义如下:
typedef struct Semaphore
{   int value;
    L:等待队列;
}
其中,整型变量value表示系统中某类资源的个数,当其值大于0时,表示系统中当前可用资源的个数;当其值小于0时,其绝对值表示系统中因请求该类资源而被阻塞的进程个数,即在该信号量的等待队列L上排队的进程个数。
一个信号量的建立必须经过定义,即应该准确指定S的意义和初值(注意:通常这个初值不是一个负值)。每个信号量都有相应的一个队列,在建立信号量时,队列为空。信号量S的定义如下:
Semaphore S=1;
信号量可被用于多种目的,如控制访问具有若干个实例的某种资源,此时信号量的初值应为可用资源的数量。如实现临界资源的互斥访问,此时信号量的初值应为1。
(2)信号量的操作原语
P、V操作以原语方式实现,信号量的值仅能由这两条原语加以改变。所谓原语是指其作为一个单一的、不可分割的操作完成。这样可以保证一旦该操作开始,则在其完成或阻塞之前其他进程均不允许访问它。
① P操作
P操作记为P(S),其中S为一个信号量,它执行时主要完成下述动作:
l       S.value=S.value-1,表示信号量S中的整型变量减1,意味着请求系统给进程分配一个资源。
l       若S.value≥0,则进程继续执行;否则(即S.value<0)阻塞该进程,并将它插入该信号量的等待队列S.L中。
对一信号量S执行P操作的过程是:先将S.value值减1,再看S.value≥0是否成立。若成立,表示存在该类资源,则将一个该类资源分配给进程继续运行。若S.value<0,则表示该类资源已分配完毕,进程自我阻塞,放弃处理器,并插入到信号量的等待队列S.L中。
P(S)操作原语描述如下:
void P(Semaphore S)
{   S.value=S.value-1;
    if (S.value<0) block(S.P);   //将进程插入到S的等待队列中
}
若信号量S.value为正数,此值等于在封锁进程之前对信号量S可施行的P操作数,即S所代表的实际可用的资源数。
② V操作
V操作记为V(S),S为一个信号量,它执行时主要完成下述动作:
l       S.value=S.value+1,表示信号量S中的整型变量增1,意味着释放一个资源。
l       若S.value>0,则进程继续执行;否则(即S.value≤0)从信号量的等待队列S.L中移出第一个进程,使其变为就绪状态并插入到就绪队列,然后再返回原进程继续执行。
对一信号量S执行V操作的过程是:表示某执行进程释放了一个资源,使系统中可供分配的该类资源数增加一个,所以S.value=S.value+1表示资源个数加1。若加1后S.value>0成立,表示存在该类资源,进程继续执行。若加1后仍是S.value≤0,则表示在该信号量的等待队列S.L中,仍有等待该资源的进程被阻塞,则将S.L中的第一个等待进程唤醒。
V(S)操作原语描述如下:
void V(Semaphore S)
{   S.value=S.value+1;
    if (S.value<=0) wakeup(S.P);      //唤醒S的等待队列中的第一个进程
}
若信号量S.value为负数,其绝对值等于登记排列在S信号量队列之中等待的进程个数,正好等于对信号量S施行P操作而被封锁并进入信号量S等待队列的进程数。
结论:P操作通常意味着申请一个资源,而V操作意味着释放一个资源,在一定条件下,P操作代表挂起进程的操作,V操作代表唤醒被挂起进程的操作。P操作和V操作在系统中总是成对出现的,它们既可以出现在同一进程中,也可以出现在不同的进程中。
(3)利用信号量实现同步
进程同步的主要任务是对多个相关进程在执行次序上进行协调,以使并发执行的诸进程之间能有效地共享资源和相互合作,从而使得程序的执行具有可再现性。利用信号量能方便地实现进程同步。设S为两个并发进程P1、P2的公共信号量,初值为0。P1执行的程序中有一条语句S1,P2执行的程序中有一条语句S2。而且,只有当P1执行S1语句后,P2才能开始执行S2语句。对这种简单的同步问题,很容易使用信号量解决。其描述如下:
main()
{   Semaphore S=0;                 //信号量S置初值0
    Cobegin                         //两进程并发执行
        P1();P2();
    Coend
}
P1()                                 //进程P1
{   …
        S1;                          //执行语句S1
        V(S);
    …
}
P2()                                 //进程P2
{   …
        P(S);
        S2;                          //执行语句S2
        …
}
两个进程P1、P2的同步(先执行S1语句后执行S2语句)图示,如图3.2所示。

图3.2  两个进程同步
进程P1→P2(先执行P1,然后执行P2)同步实现方式是:进程P1对一个信号量S执行V操作后,进程P2对同一个信号量S执行P操作,然后使P1继续前进,在这种情况下,P2要同步等待P1。若进程P1也要同步等待P2(此时P1、P2交替执行),则还要设置另一个信号量。
 
【例3.1】例如P1、P2、P3、P4、P5、P6为一组合作进程,其前趋图如图3.3所示,试用P、V操作实现这6个进程的同步。

图3.3  描述进程执行先后次序的前趋图
解法1:图3.3说明任务启动后P1先执行,当它结束后P2、P3可以开始执行,P2完成后P4、P5可以开始执行,仅当P3、P4、P5都执行完后,P6才能开始执行。为了确保这一执行顺序,设置5个同步信号量s1、s2、s3、s4、s5分别表示进程P1、P2、P3、P4、P5是否执行完成,其初值均为0。这6个进程的同步描述如下:
Semaphore s1=0;            //表示进程P1是否执行完成
Semaphore s2=0;            //表示进程P2是否执行完成
Semaphore s3=0;            //表示进程P3是否执行完成
Semaphore s4=0;            //表示进程P4是否执行完成
Semaphore s5=0;            //表示进程P5是否执行完成
main()
{   Cobegin
        P1();P2();P3();P4();P5();P6();
    Coend
}
P1()
{   … V(s1); V(s1); }
P2()
{   P(s1); … V(s2); v(S2); }
P3()
{   P(s1); … V(s3); }
P4()
{   P(s2); … V(s4); }
P5()
{   P(s2); … V(s5); }
P6()
{   P(s3); P(s4); P(s5); … }
解法2:采用信号量实现进程同步的另一种解法是,先找出所有的直接前趋关系,然后对每种直接前趋关系,如Pi→Pj,设置一个初值为0的信号量,并在Pi结束后执行对该信号量的V操作,而在Pj开始之前执行对该信号量的P操作,这样可保证Pi执行完后才执行Pj。设置7个信号量如图3.4所示,这6个进程的同步描述如下:
Semaphore a=0,b=0,c=0,d=0,e=0,f=0,g=0;
main()
{   Cobegin               //P1~P6进程并发执行
        P1();P2();P3();P4();P5();P6();
    Coend
}
P1()
{   … V(a); V(b); }
P2()
{   P(a); … V(c); V(d); }
P3()
{   P(b); … V(g); }
P4()
{   P(c); … V(e); }
P5()
{   P(d); … V(f); }
P6()
{   P(e); P(f); P(g); … }

图3.4  前趋关系与信号量
(4)用信号量实现互斥
利用信号量可以方便地实现进程互斥。设S为两个进程P1、P2实现互斥的信号量,由于每次只允许一个进程进入临界区,所以S的初值应为1(即可用资源个数为1)。只需把临界区置于P(S)和V(S)之间,即可实现两个进程的互斥。两个进程P1、P2对临界区的互斥使用图示,如图3.5所示。互斥访问临界区的描述如下:
main()
{   Semaphore S=1;   //信号量S置初值1
    Cobegin               //两进程并发执行
        P1();P2();
    Coend
}
P1()
{   …
    P(S);             //申请进入临界区
    临界区;
    V(S);             //释放临界区
    …
}
P2()
{   …
    P(S);             //申请进入临界区
    临界区;
    V(S);             //释放临界区
    …
}

图3.5  两个进程互斥
两个或多个进程使用的初值为1的信号量可保证同时只有一个进程能够进入临界区。如果每个进程在进入临界区前都执行一个P操作,并在退出时执行一个V操作,则能够实现互斥。
归纳起来,P、V操作必须成对出现,有一个P操作就一定有一个V操作。当为互斥操作时,它们处于同一进程;当为同步操作时,则不在同一进程中出现。如果P(S1)和P(S2)两个操作在一起,那么P操作的顺序至关重要。一个同步P操作与一个互斥P操作在一起时,同步P操作在互斥P操作前,而两个V操作无关紧要。
(5)解决进程同步和互斥问题的求解步骤
解决进程同步和互斥问题的求解步骤如下:
*  先要确定哪些操作是并发的、哪些操作是互斥的。并发操作可以用多个进程实现,同步和互斥就发生在这多个进程之间。多个进程操作同一临界资源就是进程间的互斥问题,多个进程要按一定的顺序操作就是进程间的同步问题。
*  每道题都指定了互斥和同步的规则,从中提炼出正确的操作条件,从而确定互斥和同步的操作流程。
Adobe Systems  根据互斥和同步规则以及操作流程确定信号量的个数以及每个信号量表示的含义,只有确切地知道信号量所代表的含义,设置这个信号量才有意义。
Adobe Systems  同步信号量的初值要根据进程的初始状态确定,具体问题具体分析,没有统一的方法。互斥信号量的初值通常是1。
Adobe Systems  根据同步、互斥规则和每个进程的操作流程可以确定P、V操作的位置。需要说明的是,无论是互斥问题还是同步问题,只要是需要进程进入阻塞状态,就必须想到在什么时候将进程唤醒。
同步进程之间具有某种合作关系,如在执行时间上必须按一定的顺序协调进行,或者共享某种资源。互斥进程彼此在逻辑上完全无关,它们的运行不具有次序的特征。
4.经典同步问题
下面将介绍几个经典的同步问题及其解法。
(1)生产者-消费者问题
生产者-消费者问题是一个著名的进程同步问题。它描述了一组生产者向一组消费者提供产品的问题,生产者与消费者共享一个缓冲区,生产者向其中投放产品,消费者从中取得产品。生产者-消费者问题是许多相互合作进程的一种抽象,例如,在输入时,输入进程是生产者,计算进程是消费者;在输出时,计算进程是生产者,打印进程是消费者。
把一个长度为n的缓冲区(n>0,n为缓冲区中单元个数)与一群生产者进程P1、P2、…、Pm和一群消费者进程C1、C2、…、Ck联系起来,如图3.6所示。假定这些生产者和消费者是互相等效的。只要缓冲区未满,生产者就可以把产品送入缓冲区;类似地,只要缓冲区未空,消费者便可以从缓冲区中取走产品并消费它。生产者和消费者的同步关系将禁止生产者向满的缓冲区中输送产品,也禁止消费者从空的缓冲区中提取产品。

图3.6  生产者-消费者问题
解法:对于生产者-消费者问题,第一步需要考虑生产者只有当存在空闲的缓冲区单元(不满,即空缓冲区单元数>0)时才能将产品放入缓冲区,即不能往满的缓冲区中输送产品,设置空闲缓冲区单元数的信号量empty。第二步考虑消费者只有当存在满缓冲区单元(不空,满缓冲区单元数>0)时才能从缓冲区中提取产品,即不能从空的缓冲区中提取产品,设置满缓冲区单元数的信号量full。第三步考虑缓冲区是一个临界资源,设置一个互斥信号量mutex。归纳起来需要使用如下3个信号量:
l       full:用来记录满的缓冲区单元个数,其初值为0。
l       empty:用于记录空的缓冲区单元数,其初值为缓冲区内缓冲区单元的个数(设为n)。
l       mutex:缓冲区为临界资源,该信号量用来确保生产者和消费者不会同时访问缓冲区,其初值为1。一般地,当两个或多个进程使用初值为1的信号量时,可以保证同时只有一个进程可以进入临界区。如果每个进程在进入临界区前都执行一个P操作,并在退出时执行一个V操作,则能够实现互斥。
生产者-消费者问题的同步描述如下:
Semaphore  full=0;                 //满缓冲区单元的个数
Semaphore  empty=n;                //空缓冲区单元的个数
Semaphore  mutex=1;                //控制对临界区访问的互斥信号量
ItemType buffer[0..n-1];          //缓冲区定义
int in=0,out=0;
main()
{   Cobegin                         //两进程并发执行
        producer();
        consumer();
    Coend
}
producer()                          //生产者进程
{   while(true)
    {   生产一个产品nextp;
        P(empty);                   //递减空缓冲区单元数
        P(mutex);                   //进入临界区
        buffer[in]=nextp;          //将产品nextp送到缓冲区
        in=(in+1) MOD n;
        V(mutex);                   //离开临界区
        V(full);                   //递增满缓冲区单元数
    }
}
consumer()                          //消费者进程
{   while(true)
    {   P(full);                   //递减满缓冲区单元数
        P(mutex);                   //进入临界区
        nextc=buffer[out];        //从缓冲区中取出一个产品nextc
        out=(out+1) MOD n;
        V(mutex);                   //离开临界区
        V(empty);                   //递增空缓冲区单元数
        消费nextc中的产品;
    }
}

生产者进程先执行P(empty),然后执行P(mutex),消费者进程先执行P(full),然后执行P(mutex)。可不可以颠倒一下?即生产者进程先执行P(mutex),然后执行P(empty),消费者进程先执行P(mutex),然后执行P(full)呢?回答是不行的。设想生产者进程已经将缓冲区放满,消费者进程并没有取产品,即empty=0,当下次仍然是生产者进程运行时,它先执行P(mutex),封锁信号量,再执行P(empty)时将被阻塞,希望消费者取出产品后将其唤醒;轮到消费者进程运行时,它先执行P(mutex),然而由于生产者进程已经封锁mutex信号量,消费者进程也会被阻塞,这样一来生产者、消费者进程都将阻塞,都指望对方唤醒自己,就陷入无休止的等待了。同理,如果消费者进程已经将缓冲区取空,即full=0,下次如果还是消费者先运行,也会出现类似的死锁。不过生产者释放信号量时,mutex、full先释放哪一个都无所谓,消费者先释放mutex还是empty也都可以。
(2)读者-写者问题
读者-写者问题是指多个进程对一个共享资源即数据集(如文件或记录集)进行读写操作的问题,如图3.7所示,其中有些进程只要求读数据集的内容,而另一些进程则要求修改或写数据集的内容。把只要求读数据的进程称为读进程,把要求修改数据的进程称为写进程。多个读进程可以同时读此数据集,不需要互斥也不会产生任何问题,不存在破坏数据集完整性、正确性的问题,但是一个写进程不能与其他进程(不管是写进程还是读进程)同时访问此数据集,它们之间必须互斥,否则将破坏此数据集的完整性。
解法:第一步考查多个读进程可以并发读数据集,用一个变量rc记录并发读数据集的进程数(初值为0),当rc≥1时禁止写进程对数据集进行写操作,当rc=0时允许写进程对数据集进行写操作。第二步考虑rc对于读进程而言是一个临界资源,为此设置一个互斥信号量mutex,防止几个读进程同时修改rc的值。第三步考虑数据集对于写进程而言是一个临界资源,为此设置一个互斥信号量db。归纳起来使用如下两个信号量和一个公共变量。
l       mutex:保护对rc的访问,初值为1。
l       db:控制写进程对数据集的访问,初值为1。
l       rc:公共变量,记录读进程的个数。

图3.7  读者-写者问题
读者-写者问题的同步算法可描述如下:
Semaphore mutex=1;           //保护对rc的访问
Semaphore db=1;               //控制对数据集的访问
int rc=0;                  //读数据集的读进程个数
main()
{   Cobegin               //两个进程并发执行
        reader();
        writer();
    Coend
}   
void reader()             //读者进程
{   while(true)
    {   P(mutex);          //互斥对rc的访问
        rc=rc+1;           //增加一个读进程数
        if(rc==1)          //当第一个读进程读数据集时,阻止写进程写
            P(db);
        V(mutex);          //恢复对rc的访问
        读数据集;
        P(mutex);          //互斥对rc的访问
        rc=rc-1;           //读者减少一个
        if(rc==0)          //当最后一个读进程读完数据集时,允许写进程写
            V(db);
        V(mutex);          //恢复对rc的访问
    }
}
void writer()             //写者进程
{   while(true)
    {   P(db);             //排斥访问数据集
        写数据集;
        V(db);             //恢复访问数据集
    }
}
在上述算法中,当第一个读进程对信号量db执行P操作时,随后的读进程只是递增计数器rc。当读进程离开时,它们递减这个计数器,而最后一个读进程则对db执行V操作,这样就允许一个阻塞的写进程可以访问数据集。
设想当一个读进程在使用数据集时,另一个读进程也来访问数据集,由于允许多个读进程同时进行读操作,所以第二个读进程也被允许进入,同理第三个及随后更多的读进程也都被允许进入。
现在假设一个写进程到来,由于写操作是排他的,所以它不能访问数据集,而是被挂起。随后其他的读进程到来,这样只要有一个读进程活跃,随后而来的读进程都被允许访问数据集。这样的结果是:只要有读进程陆续到来,它们一来就被允许进入,而写进程将一直被挂起直到没有一个读进程为止,所以上述算法是以读者为优先的算法。
如果希望写者优先,即当有读进程正在读数据集时,有写进程请求访问,这时应禁止后续读进程的读请求,等待已在读数据集的读进程执行完毕则立即让写进程执行,只有在无写进程执行的情况下才允许读进程再次投入运行。为了提高写进程的优先级,可以增加一个信号量w,即当有写进程提出写请求时,通过信号量w封锁后续读进程的读请求。
写进程优先的算法描述如下:
Semaphore mutex=1;            //保护对rc的访问
Semaphore db=1;                //控制对数据集的访问
Semaphore w=1;                 //提高写进程优先级
int rc=0;                      //读数据集的读进程个数
main()
{   Cobegin                     //两个进程并发执行
        reader();
        writer();
    Coend
}
void reader()                  //读者进程
{   while(true)
    {   P(w);                   //在无写进程请求时进入
        P(mutex);              //互斥对rc的访问
        rc = rc+1;             //增加一个读进程数
        if(rc==1)              //当第一个读进程读数据集时,阻止写进程写
            P(db);
        V(mutex);              //恢复对rc的访问
        V(w);                   //恢复对数据集的访问
        读数据集;
        P(mutex);              //互斥对rc的访问
        rc=rc-1;                //读者减少一个
        if(rc==0)              //当最后一个读进程读完数据集时,允许写进程写
            V(db);
        V(mutex);              //恢复对rc的访问
    }
}
void writer()                  //写者进程
{   while(true)
    {   P(w);                   //在无写进程请求时进入
        P(db);                  //排斥访问数据集
        写数据集;
        V(db);                  //恢复访问数据集
        V(w);                   //恢复对数据集的访问
    }
}
这里写进程优先并不是说写进程总是比读进程优先,实际上是置读写进程为平等地位,谁先请求谁优先,所以w信号量是确定读进程、写进程请求顺序的信号量。
(3)哲学家进餐问题
哲学家进餐问题描述的是5个哲学家,他们的生活方式是交替地进行思考和进餐。哲学家们共用一张圆桌,分别坐在桌子周围的5把椅子上。在圆桌上有5个碗和5支筷子,平时哲学家进行思考,饥饿时便试图取用其左、右边最靠近他的筷子,只有在他拿到两支筷子时才能进餐。进餐完毕后,放下筷子又继续思考。哲学家进餐问题也许并不重要,但可以将此问题看作并发进程执行时处理共享资源的一个有代表性的问题。哲学家进餐问题如图3.8所示。

图3.8  5个哲学家进餐
解法:在哲学家进餐问题中,第一步需要考虑每支筷子都是一个临界资源,它不可能同时被两人使用,为此每支筷子对应一个信号量,这5个信号量构成信号量数组Semaphore stick[5],所有信号量初值均为1。第二步需要考虑一个哲学家只有同时拿到左右两边的筷子后才能就餐。哲学家进餐问题的算法可描述如下:
Semaphore stick[5]={1,1,1,1,1};
main()
{   Cobegin
        philosopher(0);
        philosopher(1);
        philosopher(2);
        philosopher(3);
        philosopher(4);
    Coend
}
philosopher(int i)
{   while(true)
    {   思考;
        P(stick[i]);           //取左边筷子
        P(stick[(i+1) % 5]);      //取右边筷子
        进餐;
        V(stick[i]);           //放回左边筷子
        V(stick[(i+1) % 5]);      //放回右边筷子
    }
}
上述算法可以保证不会有相邻的两个哲学家同时进餐,但有可能引起死锁,如5个哲学家几乎同时饥饿而各自拿起了左边的筷子,这使5个筷子的信号量的值均为0,当他们试图去拿右边筷子时,都将因无筷子可拿而无限期地等待下去。
为了防止死锁的发生,可以对哲学家进餐施加一些限制条件,如至多允许4个哲学家同时进餐;仅当一个哲学家左右两边的筷子都可用时才允许他抓起筷子;将所有哲学家顺序编号,要求奇数号哲学家先抓起他左边的筷子,然后再抓起他右边的筷子,而要求偶数号哲学家先抓起他右边的筷子,然后再抓起他左边的筷子。
(4)理发师睡觉问题
文本框: 图3.9  睡觉的理发师图 2-20.gif (7360 bytes)理发店里有一位理发师、一把理发椅和5把(这里假设为5)供等候理发的顾客坐的椅子。如果没有顾客,则理发师便在理发椅上睡觉,如图
3.9所示。当一个顾客到来时,他必须先叫醒理发师,如果理发师正在理发时又有顾客到来,则如果有空椅子可坐,他们就坐下来等。如果没有空椅子,他就离开。这里的问题是为理发师和顾客各编写一段程序来描述他们的行为,要求不能带有竞争条件。
解法:对理发师睡觉问题,理发师和顾客的工作流程如图3.10所示(图中虚框是另设的)。第一步需要考虑等待的顾客数(即坐在椅子上的顾客数),设置一个变量waiting(初值为0),当进来一个顾客时,waiting增1,当一个顾客理发时,waiting减1。第二步需要考虑对waiting临界变量的互斥操作,设置一个信号量mutex(初值为1)。第三步需要考虑空椅子个数,每个空椅子是一个临界资源,设置一个信号量wchair(初值为5)。第四步考虑是否有顾客坐在理发椅上,理发椅是一个临界资源,设置一个信号量bchair(初值为1)。第五步顾客和理发师的同步操作,设置ready和finish两个信号量(初值均为0),前者表示顾客是否准备好,后者表示理发师是否完成理发。
理发师睡觉问题的算法可描述如下:
int waiting=0;                     //等待的顾客(含正在理发的人数,最多不超过6人)
Semaphore mutex=1;                 //用于waiting变量的互斥操作
Semaphore bchair=1;                //理发椅的个数
Semaphore wchair=5;               //空椅子的个数
Semaphore ready=0;                 //是否有顾客准备好
Semaphore finish=0;               //理发师是否完成理发
main()
{   Cobegin
        barber();
        customer();
    Coend
}
void barber()                      //理发师进程
{   while (true)
    {   P(ready);                   //有顾客准备好了
        理发;
        V(finsish);                 //允许其他顾客理发
    }
}
void customer()                   //顾客进程
{   P(mutex);                       //互斥waiting变量的操作
    if (waiting<6)                 //如果有空的椅子,就找到椅子坐下等待
    {                                //含正在理发的顾客,最多可6个人等待
        waiting=waiting+1;         //等待顾客数增1
        V(mutex);                   //允许waiting变量的操作
    }
    else
    {   V(mutex);                   //允许waiting变量的操作
        离开;
    }
    P(wchair);                      //找一个空椅子坐下
    P(bchair);                      //再找理发椅坐下
    V(wchair);                      //允许其他人坐空椅子
    V(ready);                       //该顾客准备好了
    P(finish);                      //等待理发师完成理发
    V(bchair);                      //离开理发椅
    P(mutex);                       //互斥waiting变量的操作
    waiting=waiting-1;             //等待顾客数减1
    V(mutex);                       //允许waiting变量的操作
}

图3.10  理发师和顾客的工作流程
5. 管程
虽然信号量提供了一种方便且有效的机制以处理进程同步,但使用不正确仍然会导致一些时序错误,并且难以检测,因为这些错误只有在特定执行顺序的情况下才会出现,而这些顺序并不是总会出现的,为此提出了管程的概念。
管程定义了一个数据结构和能为并发进程所执行的一组操作,这组操作能使进程同步和改变管程中的数据。管程由三部分组成:局限于管程的共享变量说明、对该数据结构进行操作的一组过程以及对局限于管程的数据设置初始值的语句,如图3.11所示。管程把分散在各个进程中互斥访问公共变量的那些临界区集中起来,提供对它们的保护。
管程有以下基本特性:
l       局限于管程的数据只能被局限于管程内的过程所访问。
l       一个进程只有通过调用管程内的过程才能进入管程访问共享数据。
l       每次仅允许一个进程在管程内执行某个内部过程,即进程互斥地通过调用内部过程进入管程。当某进程在管程内执行时,其他想进入管程的进程必须等待。
l       因为管程是一个语言成分,所以管程的互斥访问完全由编译程序在编译时自动添加,无须程序员关注,而且保证正确。
为实现进程间的同步,管程还必须包含若干用于同步的设施:
l       局限于管程并仅能从管程内进行访问的若干条件变量,用于区别各种不同的等待原因。
l       在条件变量上进行操作的两个函数过程是wait和signal。wait将调用此函数的进程阻塞在与该条件变量相关的队列中,并使管程成为可用,即允许其他进程进入管程。signal唤醒在该条件变量上阻塞的进程,如果有多个这样的进程则选择其中的一个进程唤醒,如果该条件变量上没有阻塞进程,则什么也不做。管程的signal过程必须在wait过程调用之后调用。

图3.11  管程的示意图
点击复制链接 与好友分享!回本站首页
分享到: 更多
您对本文章有什么意见或着疑问吗?请到论坛讨论您的关注和建议是我们前行的参考和动力  
上一篇:1.3 功能
下一篇:1.5 小结
相关文章
图文推荐
JavaScript网页动画设
1.9 响应式
1.8 登陆页式
1.7 主题式
排行
热门
文章
下载
读书

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训
版权所有: 红黑联盟--致力于做最好的IT技术学习网站