进程的同步与死锁学习资料.pptx

第 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进程的同步是指系统中多个进程中发生的事件存在某种进程的同步是指系统中多个进程中发生的事件存在某种时序关系，需要相互合作，共同完成一项任务。具体说，时序关系，需要相互合作，共同完成一项任务。具体说，一个进程运行到某一点时要求另一伙伴进程为它提供消一个进程运行到某一点时要求另一伙伴进程为它提供消息，在未获得消息之前，该进程处于等待状态，获得消息，在未获得消息之前，该进程处于等待状态，获得消息后被唤醒进入就绪态。息后被唤醒进入就绪态。n通常，把共同完成一个任务的若干进程称为通常，把共同完成一个任务的若干进程称为合作进程。合作进程。合作进程在并发执行时必须同步推进才能得到正确的执合作进程在并发执行时必须同步推进才能得到正确的执行结果。行结果。4.1 4.1 进程的同步和互斥进程的同步和互斥4.1.2 4.1.2 进程互斥进程互斥1.1.进程互斥举例进程互斥举例n假定系统中只有一台打印机，进程假定系统中只有一台打印机，进程p1p1，p2p2都需要使用打印机，如果让都需要使用打印机，如果让它们同时使用，则两个进程的输出交织在一起，打印出的结果无法使它们同时使用，则两个进程的输出交织在一起，打印出的结果无法使用。用。n为了解决这一问题，进程使用之前先要提出申请，一旦系统将打印机为了解决这一问题，进程使用之前先要提出申请，一旦系统将打印机分配给它，就一直由它独占使用，其它申请使用打印机的进程则必须分配给它，就一直由它独占使用，其它申请使用打印机的进程则必须等待。等待。n进程进程p1p1和和p2p2在逻辑上完全独立，毫无关系，只是由于竞争同一个物理在逻辑上完全独立，毫无关系，只是由于竞争同一个物理资源而相互制约。这种进程之间的间接制约关系不具有时间次序的特资源而相互制约。这种进程之间的间接制约关系不具有时间次序的特征，谁先向系统提出申请，谁就先执行。这种对共享资源的排他性的征，谁先向系统提出申请，谁就先执行。这种对共享资源的排他性的使用关系就是进程的互斥关系。使用关系就是进程的互斥关系。4.1 4.1 进程的同步和互斥进程的同步和互斥2.2.临界资源临界资源n在计算机的资源中，有些资源，如上面提到的打印机资源，在计算机的资源中，有些资源，如上面提到的打印机资源，一次能被一个进程使用，这类资源称为临界资源（一次能被一个进程使用，这类资源称为临界资源（Critical Critical ResourceResource）。）。n临界资源可能是硬件，也可能是软件：变量，数据，表格，临界资源可能是硬件，也可能是软件：变量，数据，表格，队列等。它们虽然可以被若干个进程所共享，但一次能为一队列等。它们虽然可以被若干个进程所共享，但一次能为一个进程所利用。个进程所利用。n为了保证共享临界资源的各个进程能正确运行，当临界资源为了保证共享临界资源的各个进程能正确运行，当临界资源由一个进程占用后，其它进程如果要使用它，必须等待占用由一个进程占用后，其它进程如果要使用它，必须等待占用进程使用完毕并把它释放后，才能由另一个进程使用。多个进程使用完毕并把它释放后，才能由另一个进程使用。多个进程在共享临界资源时的这种制约关系称为进程的互斥。进程在共享临界资源时的这种制约关系称为进程的互斥。4.1 4.1 进程的同步和互斥进程的同步和互斥3.3.临界区的概念临界区的概念n一个程序片段的集合，这些程序片段分散在不同的进程中，一个程序片段的集合，这些程序片段分散在不同的进程中，对某个共享的数据结构（共享资源）进行操作。在进程中对某个共享的数据结构（共享资源）进行操作。在进程中涉及到临界资源的程序段叫涉及到临界资源的程序段叫临界区或临界段临界区或临界段。n 对临界区操作的诸进程必须互斥地进入临界区。对临界区操作的诸进程必须互斥地进入临界区。4.1 4.1 进程的同步和互斥进程的同步和互斥n临界区是对某一临界资源而言的，对于不同临界资源的临临界区是对某一临界资源而言的，对于不同临界资源的临界区，它们之间不相交，所以不必互斥地执行，而相对于界区，它们之间不相交，所以不必互斥地执行，而相对于同一临界资源的若干个临界区，则必须互斥的进入，即对同一临界资源的若干个临界区，则必须互斥的进入，即对临界资源的操作必须互斥地执行。临界资源的操作必须互斥地执行。n例如有程序段例如有程序段A、B是关于变量是关于变量X的临界区，而的临界区，而C、D是关是关于变量于变量Y的临界区，那么，的临界区，那么，A、B之间需要互斥执行，之间需要互斥执行，C、D之间也要互斥执行，而之间也要互斥执行，而A与与C、B与与D之间不用互斥执行。之间不用互斥执行。4.1 4.1 进程的同步和互斥进程的同步和互斥n临界区进入准则：临界区进入准则：u 空闲让进空闲让进。当无进程处于临界区时，表明临界资源处于空闲。当无进程处于临界区时，表明临界资源处于空闲状态，应允许一个请求进入临界区的进程立即进入自己的临状态，应允许一个请求进入临界区的进程立即进入自己的临界区。界区。u忙则等待。忙则等待。当已有进程进入临界区时，表明临界资源正在被当已有进程进入临界区时，表明临界资源正在被访问，因而其他试图进入临界区的进程必须等待。访问，因而其他试图进入临界区的进程必须等待。u有限等待有限等待。对任何要求访问临界资源的进程，应保证在有限。对任何要求访问临界资源的进程，应保证在有限的时间内能进入自己的临界区，以免陷入的时间内能进入自己的临界区，以免陷入“死等死等”状态。状态。u让权等待让权等待。当进程不能进入自己的临界区，应立即放弃占用。当进程不能进入自己的临界区，应立即放弃占用CPUCPU，以使其他进程有机会得到，以使其他进程有机会得到CPUCPU的使用权，以免陷入的使用权，以免陷入“忙忙等等”。4.1 4.1 进程的同步和互斥进程的同步和互斥4.4.进程同步和互斥的区别进程同步和互斥的区别互斥的各个进程在各自单独执行时都可以得到正确的运行互斥的各个进程在各自单独执行时都可以得到正确的运行结果，但是当它们在临界区内交叉执行时就可能出现问题。结果，但是当它们在临界区内交叉执行时就可能出现问题。而同步的各个进程，如果各自单独执行将不会完成作业的特而同步的各个进程，如果各自单独执行将不会完成作业的特定任务，只要当它们互相配合、共同协调推进时才能得到正定任务，只要当它们互相配合、共同协调推进时才能得到正确的运行结果。确的运行结果。互斥的进程只要求它们不能同时进入临界区，而至于哪个进互斥的进程只要求它们不能同时进入临界区，而至于哪个进程先进入则不会产生运行的错误。但同步的进程的协调关系程先进入则不会产生运行的错误。但同步的进程的协调关系是建立在它们之间执行时序的基础上，所以，各个进程必须是建立在它们之间执行时序的基础上，所以，各个进程必须按照严格的先后次序执行。按照严格的先后次序执行。一般情况下，互斥的进程并不知道对方的存在，而同步的进一般情况下，互斥的进程并不知道对方的存在，而同步的进程不仅知道其它进程的存在，还要通过与其它进程的通信来程不仅知道其它进程的存在，还要通过与其它进程的通信来达到相互的协调。达到相互的协调。4.1 4.1 进程的同步和互斥进程的同步和互斥4.1.3 4.1.3 信号量机制信号量机制n信号量（信号量（SemaphoreSemaphore）机制是荷兰学者）机制是荷兰学者E.W.DijkstraE.W.Dijkstra在在19651965年提出的一种解决进程同步、互斥问题的更通用工具，并年提出的一种解决进程同步、互斥问题的更通用工具，并在在THETHE操作系统中得到实现。操作系统中得到实现。n信号量信号量S S是个整数变量，除了初始化外，它只能通过两个标是个整数变量，除了初始化外，它只能通过两个标准的原子操作准的原子操作waitwait和和signalsignal来访问。这两个操作原来被称来访问。这两个操作原来被称为为P(P(用于用于waitwait，表测试，表测试)和和V(V(用于用于signalsignal，表增加，表增加)操作。操作。4.1 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）临界区（临界区（CS)signal(mutex)4.1 4.1 进程的同步和互斥进程的同步和互斥n也可以使用信号量来解决各种同步问题。例如，考虑两个也可以使用信号量来解决各种同步问题。例如，考虑两个正在执行的并发进程：正在执行的并发进程：p1p1有语句有语句s1s1，而，而p2p2有语句有语句s2s2。假设。假设要求只有在要求只有在s1s1执行完之后才执行执行完之后才执行s2s2，可以很容易地实现这，可以很容易地实现这一要求：让一要求：让p1p1和和p2p2共享一个共同信号量共享一个共同信号量synchsynch，且初始化为，且初始化为0 0。在进程在进程p1p1中插入语句中插入语句：s1;signal(synch);在进程在进程p2中插入语句：中插入语句：wait(synch);s2;4.1 4.1 进程的同步和互斥进程的同步和互斥2.2.信号量的实现信号量的实现n上面定义的信号量虽然能够用来解决进程的同步和互斥问上面定义的信号量虽然能够用来解决进程的同步和互斥问题，但存在一个明显的缺陷，即该机制没有遵循题，但存在一个明显的缺陷，即该机制没有遵循“让权等让权等待待”的原则，而是使进程处于的原则，而是使进程处于“忙等忙等”状态。状态。n为了克服这个缺点，可定义一个结构体信号量：为了克服这个缺点，可定义一个结构体信号量：typedefstructintvalue;structprocess*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信号量的说明：信号量的说明：在信号量的实现中，在信号量的实现中，S.value的初值表示系统某类资源的数目，因而又的初值表示系统某类资源的数目，因而又称为资源信号量，对它的每次称为资源信号量，对它的每次wait操作，意味着进程请求一个单位的该操作，意味着进程请求一个单位的该类资源。类资源。当当S.value=1&S2=1&Sn=1)/满足资源要求时的处理；满足资源要求时的处理；for(i=1;i=n;+i).-Si;else/某些资源不够时的处理；某些资源不够时的处理；调用进程进入第一个小于调用进程进入第一个小于1信号量的等待队列信号量的等待队列Sj.queue;阻塞调用进程阻塞调用进程;4.1 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 进程的同步和互斥进程的同步和互斥n引入引入AND信号量后，上面的例子就可以简单改写为：信号量后，上面的例子就可以简单改写为：processA:processB:Swait(Dmutex,Emutex);Swait(Emutex,Dmetux);Ssignal(Dmutex,Emutex);Ssignal(Emutex,Dmutex);这样也就不会出现死锁问题。这样也就不会出现死锁问题。4.1 4.1 进程的同步和互斥进程的同步和互斥4.4.信号量的应用信号量的应用利用信号量可以很好的解决进程之间的同步问题。一般利用信号量可以很好的解决进程之间的同步问题。一般同步问题可分为两类：一类是保证一组合作进程按逻辑需同步问题可分为两类：一类是保证一组合作进程按逻辑需要所确定的次序执行；另一类是保证共享缓冲区（或共享要所确定的次序执行；另一类是保证共享缓冲区（或共享数据）的合作进程的同步。数据）的合作进程的同步。（1 1）合作进程的执行次序）合作进程的执行次序n若干个进程为了完成一个共同任务而并发执行，然而，这若干个进程为了完成一个共同任务而并发执行，然而，这些并发进程之间根据逻辑上的需要，有的操作可以没有时些并发进程之间根据逻辑上的需要，有的操作可以没有时间上的先后次序，即不论谁先做，最后的计算结果都是正间上的先后次序，即不论谁先做，最后的计算结果都是正确的。但有的操作有一定的先后次序，也就是说它们必须确的。但有的操作有一定的先后次序，也就是说它们必须遵循一定的同步规则，只有这样，并发执行的最后结果才遵循一定的同步规则，只有这样，并发执行的最后结果才是正确的。是正确的。4.1 4.1 进程的同步和互斥进程的同步和互斥n为了描述方便，可以用一个图来表示进程集合的执行次序。为了描述方便，可以用一个图来表示进程集合的执行次序。图的连接描述了进程开始和结束的次序约束。此图称为图的连接描述了进程开始和结束的次序约束。此图称为进进程流图程流图。如果用。如果用s s表示系统中某一任务启动，表示系统中某一任务启动，f f表示完成，表示完成，则可以下列的进程流图来表示这一组合作进程执行的先后则可以下列的进程流图来表示这一组合作进程执行的先后顺序顺序。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=c+dt2=c+dS SF Ft1=a+bt1=a+bt3=e/ft3=e/ft4=t1t2t4=t1t2t5=t4-t3t5=t4-t34.1 4.1 进程的同步和互斥进程的同步和互斥n例题例题4-1：进程：进程pa,pb,pc为一组为一组合作进程，其进程流图如右图合作进程，其进程流图如右图所示，使用信号量机制来实现所示，使用信号量机制来实现这三个进程的同步。这三个进程的同步。分析：分析：n从图可以看出，进程从图可以看出，进程pbpb、pcpc只有在进程只有在进程papa执行完成以后才执行完成以后才能执行，进程能执行，进程pbpb、pcpc可以并发执行。可以并发执行。n为确保这三个进程的执行顺序，设两个同步信号量为确保这三个进程的执行顺序，设两个同步信号量SBSB、SCSC分别表示进程分别表示进程pbpb和和pcpc能否开始执行，其初值均为。能否开始执行，其初值均为。4.1 4.1 进程的同步和互斥进程的同步和互斥voidpa()signal(SB);signal(SC);main()semaphoreSB=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进程负责不断进程负责不断地从缓冲区地从缓冲区bufferbuffer中取出数据去打印。中取出数据去打印。cpiop缓冲区缓冲区buffer 分析：分析：cpcp、iopiop必须遵守以下同步规则：必须遵守以下同步规则：（1）当）当cp进程把计算结果送入缓冲区进程把计算结果送入缓冲区buffer时，时，iop进程才能从缓冲区进程才能从缓冲区buffer中取出结果去打印中取出结果去打印。（2 2）当）当iopiop进程把缓冲区进程把缓冲区bufferbuffer中的数据取出打印后，中的数据取出打印后，cpcp进程才能把下进程才能把下一个计算结果送入缓冲区一个计算结果送入缓冲区bufferbuffer中。中。4.1 4.1 进程的同步和互斥进程的同步和互斥voidcp()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.问题描述问题描述 生产者生产者消费者问题可描述如消费者问题可描述如下：有下：有n n个生产者和个生产者和m m个消费者，个消费者，连接在一个有连接在一个有N N个单位缓冲区的个单位缓冲区的有界缓冲上。其中，有界缓冲上。其中，pipi和和cjcj都是都是并发进程，只要缓冲区未满，生并发进程，只要缓冲区未满，生产者产者pipi生产的产品就可投入缓冲生产的产品就可投入缓冲区；只要缓冲区不空，消费者进区；只要缓冲区不空，消费者进程程cjcj就可从缓冲区取走并消耗产就可从缓冲区取走并消耗产品。如右图所示。品。如右图所示。4.2 4.2 经典同步问题经典同步问题2.2.问题分析问题分析n为了使这两类进程协调工作，防止盲目生产和消费，它们为了使这两类进程协调工作，防止盲目生产和消费，它们应满足如下的同步条件：应满足如下的同步条件：任何时刻所有生产者存放产品的数目不能超过缓冲区的任何时刻所有生产者存放产品的数目不能超过缓冲区的总容量（总容量（N N）;所有消费者取出的产品总量不能超过所有生产者当前生所有消费者取出的产品总量不能超过所有生产者当前生产的产品总量。产的产品总量。n设置三个信号量：设置三个信号量：full：表示放有产品的缓冲区数，其初值为：表示放有产品的缓冲区数，其初值为0。empty：表示可供使用的缓冲区数，其初值为：表示可供使用的缓冲区数，其初值为N。mutex：互斥信号量，初值为：互斥信号量，初值为1，表示各进程互斥进入临，表示各进程互斥进入临界区，保证任何时候只有一个进程使用缓冲区。界区，保证任何时候只有一个进程使用缓冲区。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.2 经典同步问题经典同步问题4.2.2 4.2.2 读者读者写者问题写者问题1.1.问题描述：问题描述：有两组并发进程：读者和写者，共享一个文件有两组并发进程：读者和写者，共享一个文件F F，要求：，要求：l允许多个读者同时执行读操作允许多个读者同时执行读操作l任一写者在完成写操作之前不允许其它读者或写者工作任一写者在完成写操作之前不允许其它读者或写者工作l写者执行写操作前，应让已有的写者和读者全部退出写者执行写操作前，应让已有的写者和读者全部退出2.2.问题分析：问题分析：通通过过分分析析，我我们们可可以以发发现现读读者者和和写写者者、写写者者和和写写者者之之间间必必须须保保持持互互斥斥，为为此此应应设设置置一一个个信信号号量量（wmutex）用用于于读读者者和和写写者者以以及及写写者者和和写写者者之之间间的的互互斥斥。另另外外，为为了了说说明明多多个个读读者者可可以以同同时时读读，可可以以设设置置一一个个读读者者计计数数器器（readcount）。它它是是一一个个整整型型变变量量，初初值为值为0。4.2 4.2 经典同步问题经典同步问题读者读者Readers:while(TRUE)wait(rmutex);readcount=readcount+1;if(readcount=1)wait(wmutex);signal(rmutex);执行读操作执行读操作wait(rmutex);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.问题描述：问题描述：假设有五个哲学家，他们花费一生的时光思假设有五个哲学家，他们花费一生的时光思考和吃饭。这些哲学家公用一个圆桌，每个考和吃饭。这些哲学家公用一个圆桌，每个哲学家都有一把椅子。在桌中央有一碗米饭。哲学家都有一把椅子。在桌中央有一碗米饭。每个哲学家面前有一只空盘于，每两人之间每个哲学家面前有一只空盘于，每两人之间放一根筷子（如右图）。当一个哲学家思考放一根筷子（如右图）。当一个哲学家思考时，他与其他同事不交互，时而，哲学家会时，他与其他同事不交互，时而，哲学家会感到饥饿，并试图拿起与他最近的两支筷子感到饥饿，并试图拿起与他最近的两支筷子（他与邻近左、右两人之间的筷子）。一个（他与邻近左、右两人之间的筷子）。一个哲学家一次只能拿起一支筷子。显然，他不哲学家一次只能拿起一支筷子。显然，他不能从其他哲学家手里拿走筷子。当一个饥饿能从其他哲学家手里拿走筷子。当一个饥饿的哲学家同时有两支筷子时，他就能不用释的哲学家同时有两支筷子时，他就能不用释放他的筷子而自己吃了。当吃完后，他会放放他的筷子而自己吃了。当吃完后，他会放下两支筷子，并再次开始思考。下两支筷子，并再次开始思考。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 经典同步问题经典同步问题分析分析:n以上解法会出现死锁。为防止死锁发生可采取的措施：以上解法会出现死锁。为防止死锁发生可采取的措施：u最多允许最多允许4 4个哲学家同时坐在桌子周围个哲学家同时坐在桌子周围u仅当一个哲学家左右两边的筷子都可用时，才允许他仅当一个哲学家左右两边的筷子都可用时，才允许他拿筷子（拿筷子（）u给所有哲学家编号，奇数号的哲学家必须首先拿左边给所有哲学家编号，奇数号的哲学家必须首先拿左边的筷子，偶数号的哲学家则反之的筷子，偶数号的哲学家则反之n为了避免死锁，把哲学家分为三种状态，思考，饥饿，为了避免死锁，把哲学家分为三种状态，思考，饥饿，进食，并且一次拿到两只筷子，否则不拿。进食，并且一次拿到两只筷子，否则不拿。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把把供供等等候候理理发发的的顾顾客客坐坐的的椅椅子子。如如果果没没有有顾顾客客，理理发发师师便便在在理理发发椅椅上上睡睡觉觉。一一个个顾顾客客到到来来时时，他他必必须须叫叫醒醒理理发发师师。如如果果理理发发师师正正在在理理发发时时又又有有顾顾客客来来到到，则则如如果果有有空空椅椅子子可坐，就坐下来等待，否则就离开这个理发店。可坐，就坐下来等待，否则就离开这个理发店。4.2 4.2 经典同步问题经典同步问题2.2.问题分析问题分析 为了解决这个问题，可以定义三个信号量为了解决这个问题，可以定义三个信号量customercustomer、barbersbarbers和和mutexmutex以及一个计数变量以及一个计数变量waitingwaiting。n信号量信号量customercustomer用来记录等待理发的顾客数（不包括正用来记录等待理发的顾客数（不包括正在理发的顾客），其初值化为在理发的顾客），其初值化为0 0。n信号量信号量barbersbarbers用来记录正在等候顾客的理发师数，其用来记录正在等候顾客的理发师数，其初值为初值为0 0或或1 1。n信号量信号量mutex mutex 用于对变量用于对变量waiting waiting 的互斥操作。的互斥操作。n计数变量计数变量waitingwaiting记录正在等候理发的顾客数，初值为记录正在等候理发的顾客数，初值为0 0。它实际上是信号量。它实际上是信号量customercustomer的一份拷贝，之所以使用的一份拷贝，之所以使用变量变量waitingwaiting主要是因为无法读取信号量的当前值。主要是因为无法读取信号量的当前值。4.2 4.2 经典同步问题经典同步问题3.3.具体解法如下：具体解法如下：#defineCHAIR5/*为顾客准备的椅子数为顾客准备的椅子数*/intwaiting=0;/*等候理发的顾客数等候理发的顾客数*/semaphorecustomers=0;semaphorebarbers=0;semaphoremutex=1;voidbarber()while(TRUE);/*理完一人理完一人,还有顾客吗还有顾客吗?*/wait(cutomers);/*若无顾客若无顾客,理发师睡眠理发师睡眠*/wait(mutex);/*进程互斥进程互斥*/waiting=waiting-1;/等候顾客数少一个等候顾客数少一个cut_hair();/理发师为一个顾客理发理发师为一个顾客理发signal(mutex);/*开放临界区开放临界区*/signal(barbers);/理发师为顾客理完发理发师为顾客理完发4.2 4.2 经典同步问题经典同步问题voidcustomer()wait(mutex);/*进程互斥进程互斥*/if(waitingCHAIRS)/*看看有没有空椅子看看有没有空椅子*/waiting=waiting+1;/*等候顾客数加等候顾客数加1*/signal(customers);/*必要的话唤醒理发师必要的话唤醒理发师*/signal(mutex);/*开放临界区开放临界区*/wait(barbers);/*无理发师无理发师,顾客坐着养神顾客坐着养神*/get-haircut();/*一个顾客坐下等理发一个顾客坐下等理发*/elsesignal(mutex);/*人满了人满了,走吧走吧!*/习题课(二)习题课习题课(二二)1.1.内容提要内容提要:进程同步进程同步临界资源临界资源进程互斥进程互斥进程同步进程同步信号量机制信号量机制习题课习题课(二二)2.2.典型例题和考研题分析典型例题和考研题分析:例例1.1.设有设有n n个进程共享一个互斥段个进程共享一个互斥段,对于如下两种情况对于如下两种情况:(1)(1)如果每次只允许一个进程进入互斥段；如果每次只允许一个进程进入互斥段；(2)(2)如果每次最多允许如果每次最多允许m(mn)m(mn)个同时进入互斥。个同时进入互斥。请问请问:所采用的互斥信号量的初值是否相同所采用的互斥信号量的初值是否相同,信号量的变化范围如何信号量的变化范围如何?例例2:2:有有3 3个进程个进程PAPA、PBPB、PCPC合作解决记录打印问题：合作解决记录打印问题：PAPA将记录从磁盘读入将记录从磁盘读入主存的缓冲区主存的缓冲区1 1，每执行一次读一个记录；，每执行一次读一个记录；PBPB将缓冲区将缓冲区1 1的记录复制到的记录复制到缓冲区缓冲区2 2，每执行一次复制一个记录；，每执行一次复制一个记录；PCPC将缓冲区将缓冲区2 2的记录打印出来，的记录打印出来，每执行一次打印一个记录；缓冲区的大小等于一个记录的大小。请用每执行一次打印一个记录；缓冲区的大小等于一个记录的大小。请用信号量操作来保证记录的正确打印。信号量操作来保证记录的正确打印。习题课习题课(二二)同步与互斥的解题步骤：同步与互斥的解题步骤：（1 1）确定进程。包括进程的数量、进程的工作内容，可）确定进程。包括进程的数量、进程的工作内容，可以用流程图描述。以用流程图描述。（2 2）确定同步互斥关系。根据是否使用的是临界资源，）确定同步互斥关系。根据是否使用的是临界资源，还是处理的前后关系，确定同步与互斥，然后确定信号还是处理的前后关系，确定同步与互斥，然后确定信号量的个数、含义，以及对信号量的量的个数、含义，以及对信号量的waitwait、signalsignal操作。操作。（3 3）用类）用类C C语言描述同步或互斥算法。语言描述同步或互斥算法。习题课习题课(二二)例例2 2的分析与解答：的分析与解答：（1 1）确定进程：）确定进程：PAPA、PBPB、PCPC的工作流程如下：的工作流程如下：readrecordfromdiskputrecordintobuffer1PAreadrecordfrombuffer1putrecordintobuffer2PBreadrecordfrombuffer2printrecordPC需要知道需要知道buffer1buffer1是否空闲是否空闲需要知道需要知道buffer1buffer1是否有数据是否有数据需要知道需要知道buffer2buffer2是否空闲是否空闲需要知道需要知道buffer2buffer2是否有数据是否有数据习题课习题课(二二)（2 2）确定同步关系。）确定同步关系。根据前面的分析，这三个进程之间存在执行次序问题，根据前面的分析，这三个进程之间存在执行次序问题，因此是一个同步问题，因此，应设置四个信号量，其含因此是一个同步问题，因此，应设置四个信号量，其含义和初值如下：义和初值如下：lempty1:buffer1empty1:buffer1是否为空，初值为是否为空，初值为1 1lempty2:buffer2empty2:buffer2是否为空，初值为是否为空，初值为1 1lfull1:buffer1full1:buffer1是否有数据，初值为是否有数据，初值为0 0lfull2:buffer2full2:buffer2是否有数据，初值为是否有数据，初值为0 0习题课习题课(二二)（3 3）用类）用类C C语言描述同步或互斥算法。语言描述同步或互斥算法。semaphore empty1=1,empty2=1,full1=0,full2=0;main()processPA()while(true)从磁盘读入一个记录；wait(empty1)；将记录放入缓冲区1；signal(full1)；processPB()while(true)wait(full1);从缓冲区从缓冲区1取出记录；取出记录；signal(empty1)；wait(empty2)；将记录放入缓冲区将记录放入缓冲区2；signal(full2)；processPC()while(true)wait(full2);从缓冲区从缓冲区2取出记录；取出记录；signal(empty2)；打印记录；打印记录；习题课习题课(二二)例例3.3.（南京理工，（南京理工，20042004）桌上有一空盘，最多允许存放一桌上有一空盘，最多允许存放一只水果。爸爸可向盘中放一个苹果或放一个桔子，儿子只水果。爸爸可向盘中放一个苹果或放一个桔子，儿子专等吃盘中的桔子，女儿专等吃苹果。试用专等吃盘中的桔子，女儿专等吃苹果。试用waitwait、signalsignal操作实现爸爸、儿子、女儿三个并发进程的同步。操作实现爸爸、儿子、女儿三个并发进程的同步。提示：提示：设置一个信号量表示可否向盘中放水果，一个信号设置一个信号量表示可否向盘中放水果，一个信号量表示可否取桔子，一个信号量表示可否取苹果。量表示可否取桔子，一个信号量表示可否取苹果。习题课习题课(二二)例题例题3 3解答：解答：设置三个信号量设置三个信号量S,So,Sa S,So,Sa，初值分别为，初值分别为1 1，0 0，0 0。分。分别表示可否向盘中放水果，可否取桔子，可否取苹果。别表示可否向盘中放水果，可否取桔子，可否取苹果。Father()while(1)wait(S);将水果放入盘中将水果放入盘中;if(是桔子是桔子)signal(So);elsesignal(Sa);Son()while(1)wait(So)取桔子取桔子signal(S);吃桔子吃桔子;Daughter()while(1)wait(Sa)取苹果取苹果signal(S);吃苹果吃苹果;3.3.作业作业1.1.某寺庙有大、小和尚若干，有一水缸。由小和尚挑水入缸供老、大和尚某寺庙有大、小和尚若干，有一水缸。由小和尚挑水入缸供老、大和尚饮用。水缸可容饮用。水缸可容1010桶水，水取自同一井。水井很窄，每次只能容一个水桶水，水取自同一井。水井很窄，每次只能容一个水桶取水。水桶总数为桶取水。水桶总数为3 3个。每次入、取缸水仅为个。每次入、取缸水仅为1 1桶，且不可同时进行。桶，且不可同时进行。试给出取水、入水的同步算法。试给出取水、入水的同步算法。2.2.假定某阅览室任何时刻最多可容纳假定某阅览室任何时刻最多可容纳100100名读者进入，读者在进入和离开阅名读者进入，读者在进入和离开阅览室时必须在阅览室门口的一个登记表上