资源描述
,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,Chapter 7进程同步,进程的同步隐含了系统中并发进程之间存在的两种相互制约关系：竞争（互斥）与协作（同步）,互斥：,两个并行的进程,A、B，,如果当,A,进行某个操作时，,B,不能做这一操作，进程间的这种限制条件称为进程互斥，这是引起资源不可共享的原因。,同步：,我们把进程间的这种必须互相合作的协同工作关系，称为进程同步。,进程之间的互斥是由于共享系统资源而引起的一种间接制约关系,进程之间的同步是并发进程由于要协作完成同一个任务而引起的一种直接制约关系,如果无进程在使用共享资源时，可允许任何一个进程去使用共享资源（即使某个进程刚用过也允许再次使用），这是通过,进程互斥,的方式来管理共享资源,如果某个进程,通过共享资源得到指定消息,时，在指定消息未到达之前，即使无进程在共享资源仍不允许该进程去使用共享资源，这是通过采用,进程同步,的方式来管理共享资源。,有些问题是互斥问题，有些是同步问题，有些是互斥同步混合问题,实现临界区互斥的基本方法,临界资源：一些被,共享的资源,，具有,一次仅允许一个进程使用,的特点,临界区：,并发进程访问临界资源,的那段,必须互斥执行的程序,实现临界区互斥一个遵循的准则,有空让进，临界区空闲时，允许一个进程进入执行,无空等待，有进程在临界区执行时，要进入的进程必须等待,让权等待，有进程在临界区执行时，要求进入的进程必须立即释放,CPU,而等待,有限等待，不应该使进入临界区的进程无限期地等待在临界区之外,实现方法：软件方法、硬件方法,临界区问题的解决方案-满足三个基本条件,Mutual Exclusion(,互斥条件,)：,If process,P,i,is executing in its CS, then no other processes can be executing in their CSs,Progress(,进入条件,)：,If no process is executing in its CS and some processes wish to enter their CSs, then only those processes that are not executing in their RSs can participate in the decision on which will enter its CS next, and this selection cannot be postponed indefinitely.,Bounded Waiting(,有限等待的条件,)：,There exists a bound, or limit, on the number of times that other processes are allowed to enter their CSa after a process has made a request to enter its CS and before that request is granted.,信号量,信号量表示资源的物理实体,typedef struct ,int value;/,系统初始化时根据代表资源类可用的数量给其赋值,struct process *L;/,等待使用该资源的进程列表, semaphore,信号量的操作：,P,（,wait,）、,V,（,signal,）,P,相当于申请资源,V,相当于释放资源,操作系统利用信号量的状态对进程和资源进行管理，根据用途不同，可以把信号量分为,公用信号量,和,私有信号量,公用信号量,，用于解决进程之间,互斥,进入临界区,私有信号量,，用于解决异步环境下进程之间的,同步,，,利用信号量解决临界区互斥，设置一个公用信号量,Mutext,，初始值为,1,，任何要使用临界区资源的进程：调用,P(Mutext),，使用临界区，调用,V(Mutex),利用信号量和,PV,操作实现进程同步，对所有协作关系的并发进程，他们在使用共享资源时必须,互通消息,，仅当进程收到指定的消息后才能使用共享资源，否则需等待，直到指定的消息到达。,经典同步问题,生产者,-,消费者,同步，生产者将生产的产品放入缓存区，消费者从缓存区取用产品，所以他们要互通消息，生产者放之前要测试缓存区是不是满，消费者在从缓存区取之前要测试是不是为空。,互斥，任何时候只有一个生产者或者消费者可以访问缓存区,读者,-,写者,读写互斥访问,写写互斥访问,允许多个读者同时读，多个读者共享读者计数器变量，互斥操作,哲学家就餐,读者-写者（写者优先）,int readcount=0, writecount=0;/,读者、写者计数,semaphore rmutex=1, wmutex=1;/,读者、写者分别互斥访问,readcount, writecount,semaphore rwmutex=1;/,读者、写者互斥访问文件,semaphore r=1;/,所有读者排队,semaphore rw=1;/,一个读者与一个写者竞争访问文件,/,读者,do,wait(r);/,其他读进程在,r,上排队,wait(rw);/,一个读进程与一个写进程在,rw,上竞争,wait(rmutex);,readcount+;,if(readcount =1) wait(rwmutex);,signal(rmutex);,signal(rw);,signal(r);,读数据,/CS,wait(rmutex);,readcount-;,if(readcount =0) signal(rwmutex);,signal(rmutex);,while(1);,/,写者,Do,wait(wmutex);,writecount+;,if(writecount=1) wait(rw);/,一个写进程在,rw,竞争,signal(wmutex);,wait(rwmutex);/,其他写进程在,rwmutex,上排队,写数据,/CS,wait(wmutex);,writecount-;,if(writecount=0) signal(rw); /,都写完通知读进程,signal(wmutex);,While(1),读者-写者（两者公平）,int readcount=0;/,读者计数,semaphore rmutex=1;/,读者互斥访问,readcount,semaphore rwmutex=1;/,读者、写者互斥访问文件,semaphore rw=1;/,读者与写者竞争访问文件,/,读者,do,wait(rw);/,读进程与写进程在,rw,上竞争,wait(rmutex);,readcount+;,if(readcount =1) wait(rwmutex);,signal(rmutex);,signal(rw);,读数据,/CS,wait(rmutex);,readcount-;,if(readcount =0) signal(rwmutex);,signal(rmutex);,while(1);,/,写者,Do,wait(rw);/,读者写者竞争,wait(rwmutex);,写数据,/CS,signal(wmutex);,signal(rw);,While(1),哲学家就餐,共享变量,semaphore chopstick5, mutex;/Initially all values are 1,Philosopher i:,do ,wait(mutex);,wait(chopsticki),wait(chopstick(i+1) % 5),signal(mutex);,eat,signal(chopsticki);,signal(chopstick(i+1) % 5);,think, while (1);,Chapter 7,7.4,The first known correct software solution to the critical-section problem for two threads was developed by Dekker. The two threads,T,0 and,T,1, share the following variables:,Boolean flag2; /* initially false */,int turn;,The structure of thread,T,i (i=0 or 1), with,T,j (j=1 or 0) being the other thread, is shown as:,do ,flag i = true; while ( flag j ),if (turn = j),flag i = false;,while (turn = = j);,flag i = true;,critical section,turn = j;,flag i = false;,remainder section, while (1);,Prove that the algorithm satisfies all three requirements for the critical-section problem.,互斥：只能有一个在临界区,Pi,在临界区，,Pj,想进，看,flag,某进程进入临界区之前，,Pi,、,Pj,都置,flag,为,true,，看,turn,，只有进了的进程退出临界区以后另一个才能进,进度：,当前没有进程在临界区，只有一个进程试图进，看,flag,两个都试图进，看,turn,，进了进程在有限时间内复位,flag,有限等待：,Pi,被拒绝进入临界区，,Pj,已在临界区或者获准进入，当,Pj,退出临界区，置,turn,为,i,，复位,flag,，,Pi,可以进,7-cont.,7.5,The first known correct software solution to the critical-section problem for,n,processes with a lower bound on waiting of,n,- 1 turns was presented by Eisenberg and McGuire. The processes share the following variables:,enum pstate fidle, want in, in csg;,pstate flagn;,int turn;,All the elements of,flag,are initially idle; the initial value of,turn,is immaterial (between 0 and n-1). The structure of process,Pi,is shown as:,Prove that the algorithm satisfies all three requirements for the critical-section problem.,7-cont.,7.7,Show that, if the wait and signal operations are not executed atomically, then mutual exclusion may be violated.,7-cont.,7.8 The Sleeping-Barber Problem.,A barbershop consists of a waiting room with,n,chairs and the barber room containing the barber chair. If there are no customers to be served, the barber goes to sleep. If a customer enters the barbershop and all chairs are occupied, then the customer leaves the shop. If the barber is busy but chairs are available, then the customer sits in one of the free chairs. If the barber is asleep, the customer wakes up the barber. Write a program to coordinate the barber and the customers.,理发师和顾客同步，理发师必须由顾客唤醒，理发师给一个顾客理发完，要让理发完的顾客退出，让等待顾客进入，顾客互斥的占用,n,个位置,/,共享变量,semaphore,Scuthair,Snumchair,;/ Scuthair,制约理发师, Snumchair,制约顾客,Scuthair=0; Snumchair=0;,barber:,do ,wait(,Scuthair,);/,检查是否有顾客，无就睡眠,给某个顾客理发,signal(,Snumchair,);/,让理发完的顾客退出，让等待的一个顾客进入, while (1);,Customer i:,wait(,Snumchair,);/,申请占用椅子,signal(,Scuthair,);/,给理发师发一个信号,坐在椅子上等着理发,/,共享变量,semaphore Scuthair, Mutexchair;/ Scuthair,给理发师, Mutexchair,制约顾客对椅子的互斥占领,int number = 0;/,顾客的共享变量，记录已经有的顾客数,Scuthair=0; Mutexchair =1;,Customer i:,wait(Mutexchair);/,申请对共享变量,number,的操作（申请占用椅子）,if(number = = n-1)signal(Mutexchair); exit;,number = number +1;,signal(Scuthair);/,给理发师发一个信号,signal(Mutexchair);,等待理发,理发完毕,wait(Mutexchair);/,申请对共享变量,number,的操作,number = number -1;,signal(Mutexchair);,离开理发店,barber:,do ,wait(Scuthair);/,检查是否有顾客，无，就睡眠,给某个顾客理发, while (1);,7-cont.,7.9 The Cigarette-Smokers Problem.,Consider a system with three,smoker,processes and one,agent,process. Each smoker continuously rolls a cigarette and then smokes it. But to roll and smoke a cigarette, the smoker needs three ingredients: tobacco, paper, and matches. One of the smoker processes has paper, another has tobacco, and the third has matches. The agent has an infinite supply of all three materials. The agent places two of the ingredients on the table. The smoker who has the remaining ingredient then makes and smokes a cigarette, signaling the agent on completion. The agent then puts out another two of the three ingredients, and the cycle repeats. Write a program to synchronize the agent and the smokers.,原料供应者和三个吸烟者之间需要同步,/,共享变量,semaphore Sa, Ss;/,分别控制供应者和吸烟者,Sa = 1;,Ss =0;,/,供应者,wait(Sa);/,桌面上没有原料,任意丢两样东西到桌面,signal(Ss);/,通知吸烟者,/,吸烟者,wait(Ss);/,查看桌面原料，同时只能有一个吸烟者查看,if(,是我需要的两种原料,),取原料，卷烟，吸烟,signal(Sa);/,通知供应者可以放新的原料,else,signal(Ss);/,让别的吸烟者查看,吸烟者另解-更细,/,共享变量,semaphore Sa;/,控制供应者,semaphore S1, S2, S3;/,控制三个吸烟者,Sa = 1; S1 = S2 = S3 = 0;,/,供应者,flag f1, f2, f3;/,三个标记，分别代表纸，烟草，火柴,wait(Sa);/,桌面上没有原料,任意丢两样东西到桌面,if(f2&f3)/,供烟草，火柴,signal(S1); /,通知有纸的吸烟者,elseif(f1&f3),signal(S2); /,通知有烟草的吸烟者,else,signal(S3); /,通知有火柴的吸烟者,/,有纸的吸烟者,wait(S1);/,等待桌面上有需要的原料,取烟草，火柴，卷烟，吸烟,signal(Sa);/,通知供应者可以放新的原料,/,有烟草的吸烟者,wait(S2);/,等待桌面上有需要的原料,取纸，火柴，卷烟，吸烟,signal(Sa);/,通知供应者可以放新的原料,/,有火柴的吸烟者,wait(S3);/,等待桌面上有需要的原料,取纸，烟草，卷烟，吸烟,signal(Sa);/,通知供应者可以放新的原料,Chapter 8,资源是有限的，对资源的需求可能是无限的,当占有了部分资源而渴求更多的资源的时候，可能会引起,deadlock,（死锁）,计算机资源具有两类不同的性质：可抢占和不可抢占,可抢占资源：当资源从占用进程剥夺走时，对进程不产生破坏性影响，,CPU,和主存,不可抢占资源：当资源从占用进程剥夺走时，可能引起进程计算失败，打印机、绘图仪、,通常，死锁涉及的是不可抢占资源,死锁：一组进程是死锁的，该组中的每一个进程正在等待这组中其他进程占有的资源时可能引起的一种错误现象。,死锁产生的原因,根本原因，系统资源不足,进程推进顺序不当,死锁产生的必要条件,互斥，占有和等待，不可剥夺，循环等待,死锁处理策略,忽略不计,预防，设法破坏四个必要条件,避免,为进程分配资源时，每当完成分配后，立即检查系统是否处于安全状态，若是，分配成功，否则，分配作废，让其阻塞等待,资源分配图算法、银行家算法,需要进程对资源需求的先验知识,设法找到一种安全的进程执行序列,检测与恢复,采用资源动态分配算法，当进程请求分配资源时，只要系统有可用资源就满足，系统定期启动死锁检测算法，检查是否有环（进程等待图）,Chapter 8,8.4,Consider the traffic deadlock depicted in following,Figure.,a. Show that the four necessary conditions for deadlock indeed hold in this example.,b. State a simple rule that will avoid deadlocks in this system.,8 cont.,8.6,In a real computer system, neither the resources available nor the demands of processes for resources are consistent over long periods (months). Resources break or are replaced, new processes come and go, new resources are bought and added to the system. If deadlock is controlled by the bankers algorithm, which of the following changes can be made safely (without introducing the possibility of deadlock), and under what circumstances?,a. Increase,Available,(new resources added),b. Decrease,Available,(resource permanently removed from system),c. Increase,Max,for one process (the process needs more resources than allowed, it may want more),d. Decrease,Max,for one process (the process decides it does not need that many resources),e. Increase the number of processes,f. Decrease the number of processes,8-cont.,8.9,Consider a system consisting of,m,resources of the same type, being shared by,n,processes. Resources can be requested and released by processes only one at a time. Show that the system is deadlock-free if the following two conditions hold:,a. The maximum need of each process is between 1 and,m,resources,b. The sum of all maximum needs is less than,m,+,n,已知：资源,m,个，进程,n,个，资源的请求和释放一次一个,Max,i,1, m, Max,i, m+n,因为,Need,i,+ Allocation,i,= Max,i,所以,Need,i,+ Allocation,i,= Max,i, m+n,假设存在死锁，则,所有资源分配完成即,Allocation,i,= m,由,Need,i,+ Allocation,i, m+n,得,Need,i, n,，故有进程,P,i,所需资源为,0,由于,Max,i,1, m,所以,P,i,已经分配至少一个资源，他执行完以后至少可以释放一个资源，由已知可知资源的请求一次只一个，所以不会存在死锁。,8-cont.,8.13,Consider the following snapshot of a system:,Answer the following questions using the bankers algorithm:,a. What is the content of the matrix,Need,?,b. Is the system in a safe state?,c. If a request from process,P,1,arrives for (0,4,2,0), can the request be granted immediately?,a. Need = Max Allocation,0 0 0 0,0 7 5 0,1 0 0 2,0 0 2 0,0 6 4 2,b.安全算法找安全序列,c.先请求算法，再安全算法找安全序列，如果安全，请求可以响应。,
展开阅读全文