操作系统第2章第二节.ppt

《操作系统第2章第二节.ppt》由会员分享，可在线阅读，更多相关《操作系统第2章第二节.ppt（54页珍藏版）》请在三一办公上搜索。

1、2.3 进程同步,进程同步是指对多个相关进程在执行次序上进行协调，目的是使系统中诸进程之间能有效地共享资源和相互合作，从而使程序的执行具有可再现性。或系统中诸进程之间在逻辑上的相互制约的关系（直接的-同步；间接的互斥）。用来实现同步的机制称为同步机制。如：信号量机制；管程机制。,一.进程同步的基本概念1.两种形式的制约关系2.临界资源、临界区3.同步机制应遵循的规则二.信号量机制1.整型信号量2.记录型信号量3.AND型信号量集、一般信号量集三.信号量的应用1.信号量实现进程互斥2.信号量描述进程间的前趋关系,2.3 进程同步,一、进程同步的基本概念,1、两种进程关系系统中诸进程之间在逻辑上存

2、在着两种制约系：,进程同步：直接制约关系，进程之间为了协作完成某项任务而有意识地相互“交换信息”。如前分别将I、C和P都看成是进程。,进程互斥：间接制约关系，进程之间通过竞争系统某些资源产生的关系。原因是某些资源不能同时被 多个进程使用,间接制约关系示例,用户A,CPU,打印机(系统负责打印),打印请求,用户B,打印请求,A打印完,A完成,B打印完,B完成,A进入等待打印完成阻塞队列,B进入申请打印机阻塞队列,A被唤醒从阻塞进入就绪队列,后投入运行;B分配打印机,B被唤醒从阻塞进入就绪队列,后投入运行,一、进程同步的基本概念,2、临界资源、临界区,一、进程同步的基本概念,临界资源(critic

3、al resource）系统中某些资源一次只允许一个进程使用，称这样的资源为临界资源或互斥资源或共享变量。临界区（互斥区，critical section）在进程中涉及到临界资源的程序段叫临界区，多个进程的临界区称为相关临界区。,一、进程同步的基本概念,2、临界资源、临界区,程序 段1,共享变量,程序 段2,程序 段3,临界区示意图,例：生产者-消费者(producer-consumer)问题。var n:integer；type item=；var buffer:array0，1，n-1 of item；in，out:0，1，n-1；counter:0，1，n；,一、进程同步的基本概念,2、

4、临界资源、临界区,producer:repeat produce an item in nextp；while counter=n do no-op；Bufferin:=nextp；in:=(in+1)mod n；counter:=counter+1；until false；,consumer:repeatwhile counter=0 do no-op；nextc:=bufferout；out:=(out+1)mod n；counter:=counter-1；consumer the item in nextc；until false；,一、进程同步的基本概念,2、临界资源、临界区,生产者对

5、counter做加1操作，消费者对counter做减1操作，这两个操作在用机器语言实现时，常可用下面的形式描述：,register1:=counter；register2:=counter；register1:=register1+1；register2:=register2-1；counter:=register1；counter:=register2；,一、进程同步的基本概念,2、临界资源、临界区,register1:=counter；(register1=5)register1:=register1+1；(register1=6)register2:=counter；(register2

6、=5)register2:=register2-1；(register2=4)counter:=register1；(counter=6)counter:=register2；(counter=4),一、进程同步的基本概念,2、临界资源、临界区,一、进程同步的基本概念,register2:=counter；register2:=register2-1；register1:=counter；counter:=register2；register1:=register1+1；counter:=register1；,2、临界资源、临界区,2、临界资源、临界区,一、进程同步的基本概念,实现各进程互斥进

7、入临界区 进程须在临界区前面增加一段用于进行上述检查的代码，称为进入区(entry section)。在临界区后面加上一段称为退出区(exit section)的代码。,while(1)进入区代码;临界区代码;退出区代码;其余代码;,进程中访问临界资源的代码段,在进入临界区之前，检查可否进入临界区的一段代码。如果可以进入临界区，通常设置相应“正在访问临界区”标志,用于将“正在访问临界区”标志清除,代码中的其余部分,进程同步研究如何编写进入区和退出区代码,并发进程代码示意图,3、同步机制应遵循的规则 各进程需要互斥访问临界资源，即不能同时进入各自的临界区。应遵守的原则：,有空让进:无进程在临界区

8、时，要求进入临界区的进程可进入。互斥（忙则等待）:不允许两个以上的进程同时进入临界区。有限等待：要求进入临界区的进程不能无限等待,以免陷入“死等(饥饿)”。让权等待：当进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入“忙等”。,一、进程同步的基本概念,二、信号量机制,信号量机制是荷兰科学家在1965年提出的一种同步机制，由最初的整型信号量发展为记录型信号量，进而发展为信号量集。基本原则在多个相互制约的进程之间使用简单的信号来同步，一个进程被强制停止在一个特定的地方直到收到一个专门的信号。,1、整型信号量,整型信号量非负整数，除了初始化外，只能通过两个原子操作wait和signal来访

9、问。wait和signal操作描述：wait(S)：while S0 do noop;/测试有无可用资源 S:=S-1;/可用资源数减一个单位signal(S)：S:=S+1;,主要问题：只要S0，wait操作就不断地测试(忙等)，因而，未做到“让权等待”。,2、记录型信号量,基本思想1、设置一个整型变量value代表资源数目2、设置一个链接所有等待进程的链表3、初始化一次后，仅能被wait(S)和signal(S)两个原语操作(同步原语，也称为P、V操作)访问记录型信号量的数据结构 struc semaphore value:integer;/可用资源个数，初值=0 L:list of pr

10、ocess；/等待该资源的进程队列，初值为空,2、记录型信号量,信号量的一般结构及PCB队列,信号量的声明：semaphore S;,2、记录型信号量,P、V操作定义,P(S)/=wait(S)S.value=S.value-1;if(S.value 0)block(S.L);,若申请资源不成功，则该进程阻塞，将该进程的PCB插入等待队列S.L的末尾；若申请成功，则进程继续。,2、记录型信号量,V(S)/signal(S)S.value=S.value+1;if(S.value=0)wakeup(S.L);,P、V操作定义,唤醒等待队列S.L中等待的一个进程。该进程继续。,2、记录型信号量,S

11、.value的物理含义0：表示有S.value个资源可用。S.value的初值应0=0：表示无资源可用且无进程在等待该资源0：表示有|S.value|个进程在等待该资源P、V操作的含义P(S)：表示申请一个资源(结果成功或不成功)V(S)：表示释放一个资源,AND型信号量的基本思想 将进程在整个运行过程中所需要的所有临界资源一次性全部分配给进程，待进程使用完后再一起释放。只要有一个资源未能分配给进程，其它所有可能分配的资源也不分配给该进程。从而可避免死锁发生。在wait操作中，增加了一个“AND”条件，故称为AND同步。,3、信号量集-AND型信号量,3、信号量集-AND型信号量,Swait(

12、S1,S2,Sn)/P原语while(1)if(S1=1,Ssignal(S1,S2,Sn)/V原语略；见书,3、信号量集-一般信号量,一般信号量集是指同时需要多种资源、每种占用的数目不同、且可分配的资源还存在一个临界值时的信号量处理。一般信号量集的基本思路就是在AND型信号量集的基础上进行扩充，在一次原语操作中完成所有的资源申请。,三、信号量的应用,利用信号量实现进程互斥：互斥信号量(公用信号量)利用信号量实现进程同步：同步信号量(私有信号量，资源信号量),三、信号量的应用,利用信号量实现进程互斥,有多个进程互斥访问某类资源，则互斥进程Pi的代码如图所示(mutex初值为该类资源初始可用个数

13、),P(mutex),V(mutex),P1,P2,P3,互斥区,P(mutex),P(mutex),V(mutex),V(mutex),三、信号量的应用,三、信号量的应用,例：三个进程共用两个I/O缓冲区。解：为缓冲区设置一个互斥信号量S，S.value=2，表示可用缓冲区有2个。,三、信号量的应用,进程互斥问题解题思路一类临界资源设置一个互斥信号量mutex，初值为其可用个数(如打印机台数)，一般为1所有互斥进程在进入区执行P(mutex)，退出区执行V(mutex)；次序不能颠倒P和V操作成对出现。遗漏P操作则不能保证互斥访问，遗漏V操作则可能造成死锁,利用信号量实现前驱关系,三、信号量

14、的应用,设置一个信号量S，S=0,P1；V(S);,P(S)；P2;,如此即可实现先执行P1，再执行P2,为每个前趋关系设置一个同步信号量，其初值为0,三、信号量的应用,例:程序前趋图如图所示，试用P、V操作实现其同步。,var a,b,c,d:semaphore:=0,0,0,0;begin cobegin s1;s2;s3;s4;coend;end;,s1:begin;v(a);end;,s2:begin v(b);v(c);end;,s3:begin p(a);p(b);v(d);end;,s4:begin p(c);p(d);.end;,利用信号量实现前驱关系,三、信号量的应用,思考：

15、,已知一个求值公式（A2+3*B）/（B+5*A），若A、B已赋值，画出该公式求值过程的前趋图,利用信号量实现前驱关系,三、信号量的应用,利用信号量实现同步,生产者-消费者问题的单缓冲区情况：有A、B两个进程和一个缓冲区，A负责将信息存入缓冲区，B负责取走缓冲区中的信息进行加工。如何利用信号量实现进程同步？,消费者,生产者,三、信号量的应用,利用信号量实现同步解：设两个同步信号量。S1：缓冲区是否满，初值为0；S2：缓冲区是否空，初值为1,三、信号量的应用,进程同步问题的解题思路有几类同步进程，就设几个同步信号量。设定信号量初值。同一信号量的P、V操作要成对出现，但分别在不同进程的代码中。,2

16、.4 经典进程的同步问题,生产者消费者问题生产者与消费者互斥访问公用数据缓冲区生产者生产“数据”，消费者消费“数据”哲学进家餐问题读者写者问题,1、“生产者消费者”问题,多缓冲区的生产者消费者问题描述一组生产者向一组消费者提供消息，它们共享一个有界(k 个)缓冲池，生产者向其中投放消息，消费者从中取得消息。任何时刻只能有一个进程可对共享缓冲池进行操作。,1、“生产者消费者”问题,1、“生产者消费者”问题,多缓冲区的同步互斥问题 同步：当缓冲池已放满了产品时(供过于求)，生产者进程必须等待；当缓冲池已空时(供不应求)，消费者进程应等待。互斥：所有进程应互斥使用缓冲池这一临界资源。,多缓冲区的生产

17、者消费者问题解法,1、“生产者消费者”问题,设置两个同步信号量及一个互斥信号量empty：空缓冲单元的数目，其初值为k。full：满缓冲单元的数目（即产品数目），其初值为0。mutex:所有进程都是互斥访问缓冲池的，所以设一个互斥信号量mutex，初值是1，表示缓冲池的访问权，整个缓冲池是一个临界资源。,1、“生产者消费者”问题,多缓冲区的生产者消费者问题解法,思考：P操作的顺序可换吗？,“生产者消费者”问题的算法描述：,Var mutex,empty,full:semaphore:=1,n,0;buffer:array0,k-1 of item;in,out:integer:=0,0;beg

18、incobeginproducer:begin repeat produce an item nextp;P(empty);P(mutex);buffer(in):=nextp;in:=(in+1)mod n;V(mutex);V(full);until false;endconsumer:beginrepeatP(full);P(mutex);nextc:=buffer(out);out:=(out+1)mod n;V(mutex);V(empty);consume the item in nextc;until false;endcoendend,注意,1.互斥信号量的P、V操作在每一程序

19、中必须成对出现,1、“生产者消费者”问题,2.资源信号量(full,empty)的P、V操作也必须成对出现，但分别处于不同的程序中,3.P操作的次序不能颠倒：先检查同步信号量，再检查互斥信号量。否则可能死锁,2、“哲学家进餐”问题,5个哲学家围圆桌而坐，每人面前有一只空盘子，每2人之间放一只筷子；哲学家的动作包括思考和进餐，进餐时需要拿起他左右两边的两只筷子，思考时则将两只筷子放回原处。如何保证哲学家们的动作有序进行？,问题描述,求解进程同步与互斥问题注意事项,进程应该先申请同步信号量，再申请互斥信号量；释放顺序不要求，但建议嵌套出现任何信号量的P和V操作都必须成对出现对互斥信号量的操作成对出

20、现在同一进程中对同步信号量的操作成对出现在不同进程中在生产者消费者问题中，若只有一个缓冲区，则不需要互斥信号量,进程同步与互斥问题解题思路,分清哪些是互斥问题(互斥访问临界资源)，哪些是同步问题(具有前后执行顺序要求，一个进程的操作结果影响另一个进程的操作)。一类临界资源设置一个互斥信号量，初值为其可用个数，一般为1，代表一次只允许一个进程访问临界资源。有几类同步进程，就设几个同步信号量。一个同步信号量表示一类同步进程是否可以开始或已经结束。,同步与互斥的解题步骤,确定进程。包括进程的数量、进程的工作内容，可以用流程图描述。确定同步互斥关系。根据使用的是临界资源还是处理的前后关系，确定同步与互

21、斥，然后确定信号量的个数、含义及对信号量的P、V操作。用类C语言描述同步或互斥算法。,读者写者问题,有两组并发进程:读者和写者,共享一组数据区 要求：允许多个读者同时执行读操作 不允许读者、写者同时操作 不允许多个写者同时操作,如果读者来：1）无读者、写者，新读者可以读2）有写者等，但有其它读者正在读，则新读者也可以读3）有写者写，新读者等如果写者来：1）无读者，新写者可以写2）有读者，新写者等待3）有其它写者，新写者等待,读者写者问题的解法,读者：while(true)P(rmutex);if(readcount=0)P(w);readcount+;V(rmutex);读 P(rmutex)

22、;readcount-;if(readcount=0)V(w);V(rmutex);,写者：while(true)P(w);写 V(w);,Mutex=1,readcount=0,w=1,理发店里有一位理发师、一把理发椅和 n 把供等候理发的顾客坐的椅子。如果没有顾客，理发师便在理发椅上睡觉。第一个顾客到来时，它必须叫醒理发师。如果理发师正在理发时又有顾客来到，则如果有空椅子可坐，就坐下来等待，否则就离开。如何用信号量解决理发师问题？,思考题,var waiting:integer;/*等候理发的顾客数*/CHAIRS:integer;/*为顾客准备的椅子数*/customers,barber

23、s，mutex:semaphore;waiting:=0;CHAIRS:=n;customers:=0;barbers:=0;waiting:=0;mutex:=1;Procedure barber;begin P(cutomers);/*若无顾客,理发师睡眠*/P(mutex);/*进程互斥*/waiting:=waiting 1;/*等候顾客数少一个*/V(barbers);/*理发师去为一个顾客理发*/V(mutex);/*开放临界区*/cut-hair();/*正在理发*/end;,procedure customer begin P(mutex);/*进程互斥*/if customersn then waiting waiting:=waiting+1;/*等候顾客数加1*/V(customers);/*必要的话唤醒理发师*/V(mutex);/*开放临界区*/P(barbers);/*无理发师,顾客坐着养神*/get-haircut();/*一个顾客坐下等理发*/else V(mutex);/*人满了,走吧!*/end;,