操作系统原理与实践教程04.ppt

《操作系统原理与实践教程04.ppt》由会员分享，可在线阅读，更多相关《操作系统原理与实践教程04.ppt（99页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第 4 章进程的同步和死锁三两草上传4.1 4.1 进程的同步和互斥进程的同步和互斥4.1.1 4.1.1 进程的同步进程的同步1.1.进程同步举例进程同步举例例例.公共汽车中的司机和售票员。公共汽车中的司机和售票员。司机司机 P1 P1 售票员售票员 P2P2 while(true)while(true)while(true)while(true)启动车辆；启动车辆；关门；关门；正常运行；正常运行；售票；售票；到站停车；到站停车；开门；开门；4.1 4.1 进程的同步和互斥进程的同步和互斥2.2.进程同步的概念进程同步的概念n进程的同步是指系统中多个进程中发生的事件存在某种进程的同步是指系统

2、中多个进程中发生的事件存在某种时序关系，需要相互合作，共同完成一项任务。具体说，时序关系，需要相互合作，共同完成一项任务。具体说，一个进程运行到某一点时要求另一伙伴进程为它提供消一个进程运行到某一点时要求另一伙伴进程为它提供消息，在未获得消息之前，该进程处于等待状态，获得消息，在未获得消息之前，该进程处于等待状态，获得消息后被唤醒进入就绪态。息后被唤醒进入就绪态。n通常，把共同完成一个任务的若干进程称为通常，把共同完成一个任务的若干进程称为合作进程。合作进程。合作进程在并发执行时必须同步推进才能得到正确的执合作进程在并发执行时必须同步推进才能得到正确的执行结果。行结果。4.1 4.1 进程的同

3、步和互斥进程的同步和互斥4.1.2 4.1.2 进程互斥进程互斥1.1.进程互斥举例进程互斥举例n假定系统中只有一台打印机，进程假定系统中只有一台打印机，进程p1p1，p2p2都需要使用打印机，如果让都需要使用打印机，如果让它们同时使用，则两个进程的输出交织在一起，打印出的结果无法使它们同时使用，则两个进程的输出交织在一起，打印出的结果无法使用。用。n为了解决这一问题，进程使用之前先要提出申请，一旦系统将打印机为了解决这一问题，进程使用之前先要提出申请，一旦系统将打印机分配给它，就一直由它独占使用，其它申请使用打印机的进程则必须分配给它，就一直由它独占使用，其它申请使用打印机的进程则必须等待。

4、等待。n进程进程p1p1和和p2p2在逻辑上完全独立，毫无关系，只是由于竞争同一个物理在逻辑上完全独立，毫无关系，只是由于竞争同一个物理资源而相互制约。这种进程之间的间接制约关系不具有时间次序的特资源而相互制约。这种进程之间的间接制约关系不具有时间次序的特征，谁先向系统提出申请，谁就先执行。这种对共享资源的排他性的征，谁先向系统提出申请，谁就先执行。这种对共享资源的排他性的使用关系就是进程的互斥关系。使用关系就是进程的互斥关系。4.1 4.1 进程的同步和互斥进程的同步和互斥2.2.临界资源临界资源n在计算机的资源中，有些资源，如上面提到的打印机资源，在计算机的资源中，有些资源，如上面提到的打

5、印机资源，一次能被一个进程使用，这类资源称为临界资源（一次能被一个进程使用，这类资源称为临界资源（Critical Critical ResourceResource）。）。n临界资源可能是硬件，也可能是软件：变量，数据，表格，临界资源可能是硬件，也可能是软件：变量，数据，表格，队列等。它们虽然可以被若干个进程所共享，但一次能为一队列等。它们虽然可以被若干个进程所共享，但一次能为一个进程所利用。个进程所利用。n为了保证共享临界资源的各个进程能正确运行，当临界资源为了保证共享临界资源的各个进程能正确运行，当临界资源由一个进程占用后，其它进程如果要使用它，必须等待占用由一个进程占用后，其它进程如果

6、要使用它，必须等待占用进程使用完毕并把它释放后，才能由另一个进程使用。多个进程使用完毕并把它释放后，才能由另一个进程使用。多个进程在共享临界资源时的这种制约关系称为进程的互斥。进程在共享临界资源时的这种制约关系称为进程的互斥。4.1 4.1 进程的同步和互斥进程的同步和互斥3.3.临界区的概念临界区的概念n一个程序片段的集合，这些程序片段分散在不同的进程中，一个程序片段的集合，这些程序片段分散在不同的进程中，对某个共享的数据结构（共享资源）进行操作。在进程中对某个共享的数据结构（共享资源）进行操作。在进程中涉及到临界资源的程序段叫涉及到临界资源的程序段叫临界区或临界段临界区或临界段。n 对临界

7、区操作的诸进程必须互斥地进入临界区。对临界区操作的诸进程必须互斥地进入临界区。4.1 4.1 进程的同步和互斥进程的同步和互斥n临界区是对某一临界资源而言的，对于不同临界资源的临临界区是对某一临界资源而言的，对于不同临界资源的临界区，它们之间不相交，所以不必互斥地执行，而相对于界区，它们之间不相交，所以不必互斥地执行，而相对于同一临界资源的若干个临界区，则必须互斥的进入，即对同一临界资源的若干个临界区，则必须互斥的进入，即对临界资源的操作必须互斥地执行。临界资源的操作必须互斥地执行。n例如有程序段例如有程序段A、B是关于变量是关于变量X的临界区，而的临界区，而C、D是关是关于变量于变量Y的临界

8、区，那么，的临界区，那么，A、B之间需要互斥执行，之间需要互斥执行，C、D之间也要互斥执行，而之间也要互斥执行，而A与与C、B与与D之间不用互斥执行。之间不用互斥执行。4.1 4.1 进程的同步和互斥进程的同步和互斥n临界区进入准则：临界区进入准则：u 空闲让进空闲让进。当无进程处于临界区时，表明临界资源处于空闲。当无进程处于临界区时，表明临界资源处于空闲状态，应允许一个请求进入临界区的进程立即进入自己的临状态，应允许一个请求进入临界区的进程立即进入自己的临界区。界区。u忙则等待。忙则等待。当已有进程进入临界区时，表明临界资源正在被当已有进程进入临界区时，表明临界资源正在被访问，因而其他试图进

9、入临界区的进程必须等待。访问，因而其他试图进入临界区的进程必须等待。u有限等待有限等待。对任何要求访问临界资源的进程，应保证在有限。对任何要求访问临界资源的进程，应保证在有限的时间内能进入自己的临界区，以免陷入的时间内能进入自己的临界区，以免陷入“死等死等”状态。状态。u让权等待让权等待。当进程不能进入自己的临界区，应立即放弃占用。当进程不能进入自己的临界区，应立即放弃占用CPUCPU，以使其他进程有机会得到，以使其他进程有机会得到CPUCPU的使用权，以免陷入的使用权，以免陷入“忙忙等等”。4.1 4.1 进程的同步和互斥进程的同步和互斥4.4.进程同步和互斥的区别进程同步和互斥的区别互斥的

10、各个进程在各自单独执行时都可以得到正确的运行互斥的各个进程在各自单独执行时都可以得到正确的运行结果，但是当它们在临界区内交叉执行时就可能出现问题。结果，但是当它们在临界区内交叉执行时就可能出现问题。而同步的各个进程，如果各自单独执行将不会完成作业的特而同步的各个进程，如果各自单独执行将不会完成作业的特定任务，只要当它们互相配合、共同协调推进时才能得到正定任务，只要当它们互相配合、共同协调推进时才能得到正确的运行结果。确的运行结果。互斥的进程只要求它们不能同时进入临界区，而至于哪个进互斥的进程只要求它们不能同时进入临界区，而至于哪个进程先进入则不会产生运行的错误。但同步的进程的协调关系程先进入则

11、不会产生运行的错误。但同步的进程的协调关系是建立在它们之间执行时序的基础上，所以，各个进程必须是建立在它们之间执行时序的基础上，所以，各个进程必须按照严格的先后次序执行。按照严格的先后次序执行。一般情况下，互斥的进程并不知道对方的存在，而同步的进一般情况下，互斥的进程并不知道对方的存在，而同步的进程不仅知道其它进程的存在，还要通过与其它进程的通信来程不仅知道其它进程的存在，还要通过与其它进程的通信来达到相互的协调。达到相互的协调。4.1 4.1 进程的同步和互斥进程的同步和互斥4.1.3 4.1.3 信号量机制信号量机制n信号量（信号量（SemaphoreSemaphore）机制是荷兰学者）机

12、制是荷兰学者E.W.DijkstraE.W.Dijkstra在在19651965年提出的一种解决进程同步、互斥问题的更通用工具，并年提出的一种解决进程同步、互斥问题的更通用工具，并在在THETHE操作系统中得到实现。操作系统中得到实现。n信号量信号量S S是个整数变量，除了初始化外，它只能通过两个标是个整数变量，除了初始化外，它只能通过两个标准的原子操作准的原子操作waitwait和和signalsignal来访问。这两个操作原来被称来访问。这两个操作原来被称为为P(P(用于用于waitwait，表测试，表测试)和和V(V(用于用于signalsignal，表增加，表增加)操作。操作。4.1

13、4.1 进程的同步和互斥进程的同步和互斥nwaitwait的经典定义可用伪代码表示为：的经典定义可用伪代码表示为：wait(s)while(s=0)；/no.ops-.;nsignalsignal的经典定义可用伪代码表示为：的经典定义可用伪代码表示为：signal(s)s+；4.1 4.1 进程的同步和互斥进程的同步和互斥1.1.信号量的使用信号量的使用n可使用信号量来解决可使用信号量来解决n个进程的临界区问题。这个进程的临界区问题。这n个进程共个进程共享一个信号量享一个信号量mutex,并初始化为并初始化为1。每个进程。每个进程Pi的组织结构的组织结构如下：如下：wait(mutex）临界区

14、（临界区（CS)signal(mutex)4.1 4.1 进程的同步和互斥进程的同步和互斥n也可以使用信号量来解决各种同步问题。例如，考虑两个也可以使用信号量来解决各种同步问题。例如，考虑两个正在执行的并发进程：正在执行的并发进程：p1p1有语句有语句s1s1，而，而p2p2有语句有语句s2s2。假设。假设要求只有在要求只有在s1s1执行完之后才执行执行完之后才执行s2s2，可以很容易地实现这，可以很容易地实现这一要求：让一要求：让p1p1和和p2p2共享一个共同信号量共享一个共同信号量synchsynch，且初始化为，且初始化为0 0。在进程在进程p1p1中插入语句中插入语句：s1;sign

15、al(synch);在进程在进程p2中插入语句：中插入语句：wait(synch);s2;4.1 4.1 进程的同步和互斥进程的同步和互斥2.2.信号量的实现信号量的实现n上面定义的信号量虽然能够用来解决进程的同步和互斥问上面定义的信号量虽然能够用来解决进程的同步和互斥问题，但存在一个明显的缺陷，即该机制没有遵循题，但存在一个明显的缺陷，即该机制没有遵循“让权等让权等待待”的原则，而是使进程处于的原则，而是使进程处于“忙等忙等”状态。状态。n为了克服这个缺点，可定义一个结构体信号量：为了克服这个缺点，可定义一个结构体信号量：typedefstructintvalue;structprocess

16、*L;/进程链表进程链表semaphore;4.1 4.1 进程的同步和互斥进程的同步和互斥n信号量操作信号量操作waitwait现在可按如下来定义：现在可按如下来定义：voidwait(semaphoreS)S.value-;if(S.value0)addthisprocesstoS.L;block();n信号量操作信号量操作signalsignal现在可按如下来定义：现在可按如下来定义：voidsignal(semaphoreS)S.value+;if(S.value=0)removeaprocessPfromS.L;wakeup(P);4.1 4.1 进程的同步和互斥进程的同步和互斥n信

17、号量的说明：信号量的说明：在信号量的实现中，在信号量的实现中，S.value的初值表示系统某类资源的数目，因而又的初值表示系统某类资源的数目，因而又称为资源信号量，对它的每次称为资源信号量，对它的每次wait操作，意味着进程请求一个单位的该操作，意味着进程请求一个单位的该类资源。类资源。当当S.value=1&S2=1&Sn=1)/满足资源要求时的处理；满足资源要求时的处理；for(i=1;i=n;+i).-Si;else/某些资源不够时的处理；某些资源不够时的处理；调用进程进入第一个小于调用进程进入第一个小于1信号量的等待队列信号量的等待队列Sj.queue;阻塞调用进程阻塞调用进程;4.1

18、 4.1 进程的同步和互斥进程的同步和互斥nAND型信号量集型信号量集signal原语为原语为Ssignal,其定义如下：其定义如下：Ssignal(S1,S2,Sn)for(i=1;i=n;+i)+Si;/释放占用的资源；释放占用的资源；for(在在Si.queue中等待的每一个进程中等待的每一个进程P)从等待队列从等待队列Si.queue中取出进程中取出进程P;if(判断进程判断进程P是否通过是否通过Swait中的测试中的测试)/重新判断重新判断进程进程P进入就绪队列进入就绪队列;break；else进程进程P进入某等待队列；进入某等待队列；4.1 4.1 进程的同步和互斥进程的同步和互斥

19、n引入引入AND信号量后，上面的例子就可以简单改写为：信号量后，上面的例子就可以简单改写为：processA:processB:Swait(Dmutex,Emutex);Swait(Emutex,Dmetux);Ssignal(Dmutex,Emutex);Ssignal(Emutex,Dmutex);这样也就不会出现死锁问题。这样也就不会出现死锁问题。4.1 4.1 进程的同步和互斥进程的同步和互斥4.4.信号量的应用信号量的应用利用信号量可以很好的解决进程之间的同步问题。一般利用信号量可以很好的解决进程之间的同步问题。一般同步问题可分为两类：一类是保证一组合作进程按逻辑需同步问题可分为两类

20、：一类是保证一组合作进程按逻辑需要所确定的次序执行；另一类是保证共享缓冲区（或共享要所确定的次序执行；另一类是保证共享缓冲区（或共享数据）的合作进程的同步。数据）的合作进程的同步。（1 1）合作进程的执行次序）合作进程的执行次序n若干个进程为了完成一个共同任务而并发执行，然而，这若干个进程为了完成一个共同任务而并发执行，然而，这些并发进程之间根据逻辑上的需要，有的操作可以没有时些并发进程之间根据逻辑上的需要，有的操作可以没有时间上的先后次序，即不论谁先做，最后的计算结果都是正间上的先后次序，即不论谁先做，最后的计算结果都是正确的。但有的操作有一定的先后次序，也就是说它们必须确的。但有的操作有一

21、定的先后次序，也就是说它们必须遵循一定的同步规则，只有这样，并发执行的最后结果才遵循一定的同步规则，只有这样，并发执行的最后结果才是正确的。是正确的。4.1 4.1 进程的同步和互斥进程的同步和互斥n为了描述方便，可以用一个图来表示进程集合的执行次序。为了描述方便，可以用一个图来表示进程集合的执行次序。图的连接描述了进程开始和结束的次序约束。此图称为图的连接描述了进程开始和结束的次序约束。此图称为进进程流图程流图。如果用。如果用s s表示系统中某一任务启动，表示系统中某一任务启动，f f表示完成，表示完成，则可以下列的进程流图来表示这一组合作进程执行的先后则可以下列的进程流图来表示这一组合作进

22、程执行的先后顺序顺序。4.1 4.1 进程的同步和互斥进程的同步和互斥n例题：假设某个程序段包含例题：假设某个程序段包含如下语句：如下语句：inta,b,c,d,e,f;intt1,t2,t3,t4,t5;t1=a+b;t2=c+d;t3=e/f;t4=t1*t2;t5=t4-t3;t2=t2=c+dc+dS SF Ft1=t1=a+ba+bt3=t3=e/fe/ft4=t1t4=t1t2t2t5=t4-t3t5=t4-t34.1 4.1 进程的同步和互斥进程的同步和互斥n例题例题4-1：进程：进程pa,pb,pc为一组为一组合作进程，其进程流图如右图合作进程，其进程流图如右图所示，使用信号量

23、机制来实现所示，使用信号量机制来实现这三个进程的同步。这三个进程的同步。分析：分析：n从图可以看出，进程从图可以看出，进程pbpb、pcpc只有在进程只有在进程papa执行完成以后才执行完成以后才能执行，进程能执行，进程pbpb、pcpc可以并发执行。可以并发执行。n为确保这三个进程的执行顺序，设两个同步信号量为确保这三个进程的执行顺序，设两个同步信号量SBSB、SCSC分别表示进程分别表示进程pbpb和和pcpc能否开始执行，其初值均为。能否开始执行，其初值均为。4.1 4.1 进程的同步和互斥进程的同步和互斥voidpa()signal(SB);signal(SC);main()semap

24、horeSB=SC=0;cobeginpa();pb();pc();coend;voidpb()wait(SB);voidpc()wait(SC);4.1 4.1 进程的同步和互斥进程的同步和互斥（2 2）共享缓冲区的进程的同步共享缓冲区的进程的同步 例题例题4-24-2：设某计算进程：设某计算进程cpcp和打印进程和打印进程iopiop共用一个单缓冲区（如右图所示）。共用一个单缓冲区（如右图所示）。其中，其中，cpcp进程负责不断地计算数据并送进程负责不断地计算数据并送入缓冲区入缓冲区bufferbuffer中，中，iopiop进程负责不断进程负责不断地从缓冲区地从缓冲区bufferbuff

25、er中取出数据去打印。中取出数据去打印。cpiop缓冲区缓冲区buffer 分析：分析：cpcp、iopiop必须遵守以下同步规则：必须遵守以下同步规则：（1）当）当cp进程把计算结果送入缓冲区进程把计算结果送入缓冲区buffer时，时，iop进程才能从缓冲区进程才能从缓冲区buffer中取出结果去打印中取出结果去打印。（2 2）当）当iopiop进程把缓冲区进程把缓冲区bufferbuffer中的数据取出打印后，中的数据取出打印后，cpcp进程才能把下进程才能把下一个计算结果送入缓冲区一个计算结果送入缓冲区bufferbuffer中。中。4.1 4.1 进程的同步和互斥进程的同步和互斥voi

26、dcp()while(计算未完成计算未完成)得到一个计算结果；得到一个计算结果；wait(Sb);将计算结果送缓冲区将计算结果送缓冲区buffer中；中；signal(Sa);main()semaphoreSa=0;semaphoreSb=1;cobegincp();iop();coend;voidiop()while(打印工作未完成打印工作未完成)wait(Sa);从缓冲区从缓冲区buffer中取出中取出信息；信息；signal(Sb);打印输出结果；打印输出结果；4.2 4.2 经典同步问题经典同步问题4.2.1 4.2.1 生产者生产者消费者问题消费者问题1.1.问题描述问题描述 生产者

27、生产者消费者问题可描述如消费者问题可描述如下：有下：有n n个生产者和个生产者和m m个消费者，个消费者，连接在一个有连接在一个有N N个单位缓冲区的个单位缓冲区的有界缓冲上。其中，有界缓冲上。其中，pipi和和cjcj都是都是并发进程，只要缓冲区未满，生并发进程，只要缓冲区未满，生产者产者pipi生产的产品就可投入缓冲生产的产品就可投入缓冲区；只要缓冲区不空，消费者进区；只要缓冲区不空，消费者进程程cjcj就可从缓冲区取走并消耗产就可从缓冲区取走并消耗产品。如右图所示。品。如右图所示。4.2 4.2 经典同步问题经典同步问题2.2.问题分析问题分析n为了使这两类进程协调工作，防止盲目生产和消

28、费，它们为了使这两类进程协调工作，防止盲目生产和消费，它们应满足如下的同步条件：应满足如下的同步条件：任何时刻所有生产者存放产品的数目不能超过缓冲区的任何时刻所有生产者存放产品的数目不能超过缓冲区的总容量（总容量（N N）;所有消费者取出的产品总量不能超过所有生产者当前生所有消费者取出的产品总量不能超过所有生产者当前生产的产品总量。产的产品总量。n设置三个信号量：设置三个信号量：full：表示放有产品的缓冲区数，其初值为：表示放有产品的缓冲区数，其初值为0。empty：表示可供使用的缓冲区数，其初值为：表示可供使用的缓冲区数，其初值为N。mutex：互斥信号量，初值为：互斥信号量，初值为1，表

29、示各进程互斥进入临，表示各进程互斥进入临界区，保证任何时候只有一个进程使用缓冲区。界区，保证任何时候只有一个进程使用缓冲区。voidproducer()voidconsumer()dodowait(full);produceaproduct;wait(mutex);wait(empty);removeanitemfrombuffer;wait(mutex);signal(mutex);addnextptobuffer;signal(empty);signal(mutex);consumetheiteminnextc;signal(full);while（1）；）；while(1);4.2 4.

30、2 经典同步问题经典同步问题4.2.2 4.2.2 读者读者写者问题写者问题1.1.问题描述：问题描述：有两组并发进程：读者和写者，共享一个文件有两组并发进程：读者和写者，共享一个文件F F，要求：，要求：l允许多个读者同时执行读操作允许多个读者同时执行读操作l任一写者在完成写操作之前不允许其它读者或写者工作任一写者在完成写操作之前不允许其它读者或写者工作l写者执行写操作前，应让已有的写者和读者全部退出写者执行写操作前，应让已有的写者和读者全部退出2.2.问题分析：问题分析：通通过过分分析析，我我们们可可以以发发现现读读者者和和写写者者、写写者者和和写写者者之之间间必必须须保保持持互互斥斥，为

31、为此此应应设设置置一一个个信信号号量量（wmutex）用用于于读读者者和和写写者者以以及及写写者者和和写写者者之之间间的的互互斥斥。另另外外，为为了了说说明明多多个个读读者者可可以以同同时时读读，可可以以设设置置一一个个读读者者计计数数器器（readcount）。它它是是一一个个整整型型变变量量，初初值为值为0。4.2 4.2 经典同步问题经典同步问题读者读者Readers:while(TRUE)wait(rmutex);readcount=readcount+1;if(readcount=1)wait(wmutex);signal(rmutex);执行读操作执行读操作wait(rmutex)

32、;readcount=readcount-1;if(readcount=0)singal(wmutex);singal(rmutex);使用读取的数据使用读取的数据写者写者Writers：while(TRUE)wait(wmutex);执行写操作执行写操作singal(wmutex);这个算法隐含读者的优这个算法隐含读者的优先级高于写者。先级高于写者。4.2 4.2 经典同步问题经典同步问题4.2.3 4.2.3 哲学家进餐问题哲学家进餐问题1.1.问题描述：问题描述：假设有五个哲学家，他们花费一生的时光思假设有五个哲学家，他们花费一生的时光思考和吃饭。这些哲学家公用一个圆桌，每个考和吃饭。这

33、些哲学家公用一个圆桌，每个哲学家都有一把椅子。在桌中央有一碗米饭。哲学家都有一把椅子。在桌中央有一碗米饭。每个哲学家面前有一只空盘于，每两人之间每个哲学家面前有一只空盘于，每两人之间放一根筷子（如右图）。当一个哲学家思考放一根筷子（如右图）。当一个哲学家思考时，他与其他同事不交互，时而，哲学家会时，他与其他同事不交互，时而，哲学家会感到饥饿，并试图拿起与他最近的两支筷子感到饥饿，并试图拿起与他最近的两支筷子（他与邻近左、右两人之间的筷子）。一个（他与邻近左、右两人之间的筷子）。一个哲学家一次只能拿起一支筷子。显然，他不哲学家一次只能拿起一支筷子。显然，他不能从其他哲学家手里拿走筷子。当一个饥饿

34、能从其他哲学家手里拿走筷子。当一个饥饿的哲学家同时有两支筷子时，他就能不用释的哲学家同时有两支筷子时，他就能不用释放他的筷子而自己吃了。当吃完后，他会放放他的筷子而自己吃了。当吃完后，他会放下两支筷子，并再次开始思考。下两支筷子，并再次开始思考。4.2 4.2 经典同步问题经典同步问题设设fork5为为5个信号量，初值均为个信号量，初值均为1voidphilosopher(inti)while(1)思考；思考；wait(forki);wait(fork(i+1)%5)；进食；进食；signal(forki);signal(fork(i+1)%5)；4.2 4.2 经典同步问题经典同步问题分析分

35、析:n以上解法会出现死锁。为防止死锁发生可采取的措施：以上解法会出现死锁。为防止死锁发生可采取的措施：u最多允许最多允许4 4个哲学家同时坐在桌子周围个哲学家同时坐在桌子周围u仅当一个哲学家左右两边的筷子都可用时，才允许他仅当一个哲学家左右两边的筷子都可用时，才允许他拿筷子（拿筷子（）u给所有哲学家编号，奇数号的哲学家必须首先拿左边给所有哲学家编号，奇数号的哲学家必须首先拿左边的筷子，偶数号的哲学家则反之的筷子，偶数号的哲学家则反之n为了避免死锁，把哲学家分为三种状态，思考，饥饿，为了避免死锁，把哲学家分为三种状态，思考，饥饿，进食，并且一次拿到两只筷子，否则不拿。进食，并且一次拿到两只筷子，

36、否则不拿。4.2 4.2 经典同步问题经典同步问题采用采用ANDAND信号量集解决哲学家就餐问题信号量集解决哲学家就餐问题设设fork5为为5个信号量，初值为均个信号量，初值为均1Philosopher（i）while(1)思考；思考；Swait(forki,fork(i+1)%5)；进食；进食；Ssignal(forki,fork(i+1)%5)；4.2 4.2 经典同步问题经典同步问题4.2.4 4.2.4 理发师理发师问题问题1.1.问题描述：问题描述：理理发发店店有有一一位位理理发发师师、一一把把理理发发椅椅和和n n把把供供等等候候理理发发的的顾顾客客坐坐的的椅椅子子。如如果果没没有

37、有顾顾客客，理理发发师师便便在在理理发发椅椅上上睡睡觉觉。一一个个顾顾客客到到来来时时，他他必必须须叫叫醒醒理理发发师师。如如果果理理发发师师正正在在理理发发时时又又有有顾顾客客来来到到，则则如如果果有有空空椅椅子子可坐，就坐下来等待，否则就离开这个理发店。可坐，就坐下来等待，否则就离开这个理发店。4.2 4.2 经典同步问题经典同步问题2.2.问题分析问题分析 为了解决这个问题，可以定义三个信号量为了解决这个问题，可以定义三个信号量customercustomer、barbersbarbers和和mutexmutex以及一个计数变量以及一个计数变量waitingwaiting。n信号量信号量

38、customercustomer用来记录等待理发的顾客数（不包括正用来记录等待理发的顾客数（不包括正在理发的顾客），其初值化为在理发的顾客），其初值化为0 0。n信号量信号量barbersbarbers用来记录正在等候顾客的理发师数，其用来记录正在等候顾客的理发师数，其初值为初值为0 0或或1 1。n信号量信号量mutexmutex 用于对变量用于对变量waiting waiting 的互斥操作。的互斥操作。n计数变量计数变量waitingwaiting记录正在等候理发的顾客数，初值为记录正在等候理发的顾客数，初值为0 0。它实际上是信号量它实际上是信号量customercustomer的一份

39、拷贝，之所以使用变的一份拷贝，之所以使用变量量waitingwaiting主要是因为无法读取信号量的当前值。主要是因为无法读取信号量的当前值。4.2 4.2 经典同步问题经典同步问题3.3.具体解法如下：具体解法如下：#defineCHAIR5/*为顾客准备的椅子数为顾客准备的椅子数*/intwaiting=0;/*等候理发的顾客数等候理发的顾客数*/semaphorecustomers=0;semaphorebarbers=0;semaphoremutex=1;voidbarber()while(TRUE);/*理完一人理完一人,还有顾客吗还有顾客吗?*/wait(cutomers);/*若

40、无顾客若无顾客,理发师睡眠理发师睡眠*/wait(mutex);/*进程互斥进程互斥*/waiting=waiting-1;/等候顾客数少一个等候顾客数少一个cut_hair();/理发师为一个顾客理发理发师为一个顾客理发signal(mutex);/*开放临界区开放临界区*/signal(barbers);/理发师为顾客理完发理发师为顾客理完发4.2 4.2 经典同步问题经典同步问题voidcustomer()wait(mutex);/*进程互斥进程互斥*/if(waitingCHAIRS)/*看看有没有空椅子看看有没有空椅子*/waiting=waiting+1;/*等候顾客数加等候顾客数

41、加1*/signal(customers);/*必要的话唤醒理发师必要的话唤醒理发师*/signal(mutex);/*开放临界区开放临界区*/wait(barbers);/*无理发师无理发师,顾客坐着养神顾客坐着养神*/get-haircut();/*一个顾客坐下等理发一个顾客坐下等理发*/elsesignal(mutex);/*人满了人满了,走吧走吧!*/4.3 4.3 管程管程4.3.1 4.3.1 管程的概念管程的概念1.1.问题的提出问题的提出 采用信号量同步机制来编写并发程序，对于共享变量采用信号量同步机制来编写并发程序，对于共享变量及信号量变量的操作将被分散于各个进程中，具有以下

42、缺及信号量变量的操作将被分散于各个进程中，具有以下缺点：点：n易读性差，因为要了解对于一组共享变量及信号量的操作易读性差，因为要了解对于一组共享变量及信号量的操作是否正确，则必须通读整个系统或者并发程序。是否正确，则必须通读整个系统或者并发程序。n不利于修改和维护，因为程序的局部性很差，所以任一组不利于修改和维护，因为程序的局部性很差，所以任一组变量或一段代码的修改都可能影响全局。变量或一段代码的修改都可能影响全局。n正确性难以保证，因为操作系统或并发程序通常很大，要正确性难以保证，因为操作系统或并发程序通常很大，要保证这样一个复杂的系统没有逻辑错误是很难的。保证这样一个复杂的系统没有逻辑错误

43、是很难的。4.3 4.3 管程管程2.2.管程的概念管程的概念n一个管程定义了一个数据结构和能为并发进程所执行（在一个管程定义了一个数据结构和能为并发进程所执行（在该数据结构上）的一组操作，这组操作能同步进程和改变该数据结构上）的一组操作，这组操作能同步进程和改变管程中的数据。管程中的数据。n管程由三部分组成：管程由三部分组成：（1 1）局部于管程的若干公共变量说明；）局部于管程的若干公共变量说明；（2 2）对该数据结构进行操作的一组过程；）对该数据结构进行操作的一组过程；（3 3）对局部于管程的数据设置初值的语句。此外，还必须）对局部于管程的数据设置初值的语句。此外，还必须给管程赋予一个名字

44、。给管程赋予一个名字。管程的基本形式管程的基本形式TYPE=MONITOR;define;use；procedure();begin；end;procedure();begin；end;begin；end;局部数据过程1过程k出口初始化代码入口管程等待调用的进程队列4.3 4.3 管程管程n管程具有以下三个特性：管程具有以下三个特性：管程内部的局部数据变量只能被管程内定义的过程管程内部的局部数据变量只能被管程内定义的过程所访问，不能被管程外面声明的过程直接访问。所访问，不能被管程外面声明的过程直接访问。进程要想进入管程，必须调用管程内的某个过程。进程要想进入管程，必须调用管程内的某个过程。一次

45、只能有一个进程在管程内执行，而其余调用该一次只能有一个进程在管程内执行，而其余调用该管程的进程都被挂起，等待该管程成为可用的。即管程的进程都被挂起，等待该管程成为可用的。即管程能有效地实现互斥。管程能有效地实现互斥。4.3 4.3 管程管程4.3.2 4.3.2 条件变量条件变量n管程构造确保一次只能有一个进程在管程内活动，提供了一种实现互管程构造确保一次只能有一个进程在管程内活动，提供了一种实现互斥的简便途径，但这还不够，还需要一种办法使得进程在无法继续运斥的简便途径，但这还不够，还需要一种办法使得进程在无法继续运行时被阻塞。例如，当一个进程进入管程后等待某个条件未满足时，行时被阻塞。例如，

46、当一个进程进入管程后等待某个条件未满足时，这个进程必须挂起，释放管程，以便其他进程能够进入。以后，当所这个进程必须挂起，释放管程，以便其他进程能够进入。以后，当所需的条件满足了，且该管程处于可用的情况下，就要恢复该进程的执需的条件满足了，且该管程处于可用的情况下，就要恢复该进程的执行，且让它在先前的挂起点重新进入该管程。行，且让它在先前的挂起点重新进入该管程。n解决这个问题的方法是引入解决这个问题的方法是引入条件变量条件变量（conditionvariables）。条件变）。条件变量是当调用管程过程的进程无法运行时，用于阻塞进程的一种信号量，量是当调用管程过程的进程无法运行时，用于阻塞进程的一

47、种信号量，它包含在管程内，且只能在管程内对它进行访问。对条件变量仅有的它包含在管程内，且只能在管程内对它进行访问。对条件变量仅有的操作是操作是wait和和signal。当一个管程过程发现无法继续时，它在某些条。当一个管程过程发现无法继续时，它在某些条件变量件变量condition上执行上执行wait，这个动作引起调用进程阻塞，并将另一，这个动作引起调用进程阻塞，并将另一个先前被挡在管程之外的进程调入管程。个先前被挡在管程之外的进程调入管程。4.3 4.3 管程管程n另另一一个个进进程程可可以以通通过过对对其其伙伙伴伴在在等等待待的的同同一一个个条条件件变变量量conditionconditio

48、n上执行同步原语上执行同步原语signalsignal操作来唤醒等待进程。操作来唤醒等待进程。n使使用用signalsignal释释放放等等待待进进程程时时，可可能能出出现现两两个个进进程程同同时时停停留留在管程内。解决方法：在管程内。解决方法：执执行行signalsignal的的进进程程等等待待，直直到到被被释释放放进进程程退退出出管管程程或或等待另一个条件等待另一个条件被被释释放放进进程程等等待待，直直到到执执行行signalsignal的的进进程程退退出出管管程程或或等待另一个条件等待另一个条件4.3 4.3 管程管程4.3.3 4.3.3 利用管程解决生产者利用管程解决生产者消费者问题

49、消费者问题在利用管程方法来解决生产者在利用管程方法来解决生产者消费者问题时，首消费者问题时，首先要为它们建立一个管程，并命名为先要为它们建立一个管程，并命名为Procedure_ConsumerProcedure_Consumer,其中包括两个过程：其中包括两个过程：（1 1）put(itemput(item)过程。生产者利用该过程将自己生产过程。生产者利用该过程将自己生产的产品放入缓冲池，并用整型变量的产品放入缓冲池，并用整型变量countcount来表示在缓冲池来表示在缓冲池中已有的产品数目，当中已有的产品数目，当countncountn时，表示缓冲池已满，生时，表示缓冲池已满，生产者必须

50、等待。产者必须等待。（2 2）get(itemget(item）过程。消费者利用该过程从缓冲池中）过程。消费者利用该过程从缓冲池中取走一个产品，当取走一个产品，当count0count0时，表示缓冲池中已无可取走时，表示缓冲池中已无可取走的产品，消费者应等待。的产品，消费者应等待。4.3 4.3 管程管程 monitorProcedure_Consumerintin,out,count;itembuffern;/空缓冲区数目空缓冲区数目conditionnotfull,notempty;/条件变量条件变量voidput(item)if（countn）notfull.wait;bufferin=