os-2-2-同步互斥2

12.4进程的同步与互斥进程的同步和互斥机制的主要任务：控制并发执行的诸进程之间能有效地共享和相互协作，同时使并发执行的程序仍具有可再现性。进程互斥进程同步利用信号量机制解决具体问题22.4.1进程同步的基本概念并发系统中诸进程由于资源共享、进程合作，而产生进程之间的相互制约；又因共享资源的方式不同，而导致两种不同的制约关系：1间接制约关系（进程互斥）由于共享资源而引起的临界区内不允许并发进程交叉执行的现象,由共享公有资源而造成的对并发进程执行速度的间接制约。多个进程彼此无关，完全不知道或只能间接感知其它进程的存在系统须保证诸进程能互斥地访问临界资源系统资源应统一分配，而不允许用户进程直接使用2直接制约关系（进程同步）由于并发进程互相共享对方的私有资源所引起的直接制约。系统应保证相互合作的诸进程在执行次序上的协调和防止与时间有关的差错第3页同步定义：进程之间这种相互合作、协同工作的关系称为进程的同步。简单说来就是：多个相关进程在执行次序上的协调。制约关系：直接制约。第4页互斥定义：当多个进程因为争夺临界资源而互斥执行称为进程的互斥。即不允许两个以上的共享该资源的并发进程同时进入临界区称为互斥制约关系：间接制约。临界资源：也称独占资源，是指在一段时间内只允许一个进程访问的资源。例如打印机，磁带机，也可以是进程共享的数据、变量等。第5页临界资源处理不当带来的问题–执行结果错误…a=n//n表示剩余的票数if(a=1){a=a-1;//售出一张票n=a;}………a=n//n表示剩余的票数if(a=1){a=a-1;//售出一张票n=a;}……服务器售票员A售票员B临界资源临界区：与临界资源操作相关的程序段。第6页–死锁（DeadLock）在并发系统中，程序执行结果的正确性不仅取决于自身的正确性，还与其在执行过程中能否正确的与其它进程实施同步或互斥有关。必须对临界资源的访问进行控制。7临界区的管理计算机专家Dijkstra1965年提出临界区设计原则，即一组并发进程互斥执行时必须满足：①每次至多有一个进程处于临界区②当若干进程同时要求进入它们的临界区时，应在有限时间内使一进程进入临界区，而不应相互堵塞而致使彼此不能进入临界区③进程仅在临界区内逗留有限的时间。简言之，同步机制的准则有：1空闲让进；2忙则等待；3让权等待；4有限等待；第8页2.4.2硬件同步机制1.关中断法(开关中断指令)关中断法也称为“硬件锁”，是实现互斥最简单的方法。做法：每个进程在进入临界区后先关中断，屏蔽其它请求，在离开之前再开中断。优点：实现简单。缺点：中断被关掉后，CPU不再响应任何外部事件，此时进程将会独占CPU，直至关闭中断，如果中断关闭时间过长，会造成严重后果，因此把开关中断的权力交给用户进程是很不明智的。第9页2.锁变量法(测试和设置指令)做法：设置一个共享(锁)变量W，初值为0。当一个进程想进入其临界区时，它首先测试这把锁。如果锁的值为0，则进程将其置为1并进入临界区。若锁已经为1，则进程等待直到其变成0。于是，0就表示临界区内没有进程，1表示已经有某个进程进入了临界区。优点：较为简单。缺点：当有一个进程进入临界区后，其它试图进入的进程必须反复不断的测试W以便在W为0时进入，此时CPU会一直处于忙状态(busywaiting)。因此这种方法效率也很低。……LOCK(W);//加锁原语临界区;UNLOCK(W);//解锁原语……第10页3.其它方法Dekker算法：进程被强制轮流进入临界区(不管是否愿意)。Peterson算法：设置标识指示是否又要求进入临界区。Swap指令法：通过全局变量和每个进程的局部变量交换实现互斥访问临界区。……第11页2.4.3信号量机制信号量(Semaphore)和P、V操作–信号量：1965年由荷兰学者Dijkstra提出，它是一种特殊的数据结构。功能：表示资源的实体。特殊之处：–每个信号量与一个队列关联；–其值只能通过初始化和P、V操作来访问。–信号量的类型：公用信号量：用于进程间的互斥，初值通常为1私有信号量：用于进程间的同步，初值通常为0或n第12页1.整形信号量P操作：荷兰语“proberen”——“检测”之意。意味着请求分配一个单位资源。P(S)：//S为信号量{S=S-1;if(S0){调用进程被阻塞，进入S的等待队列；}}PCBPCBPCBPCB和S相关的等待队列PCB第13页V操作：荷兰语“verhogen”——“增量”之意，意味着释放一个单位资源。V(S)：//S为信号量{S=S+1;if(S=0){从S的等待队列中唤醒一个进程使其进入就绪状态；}}PCBPCBPCBPCB和S相关的等待队列PCB第14页信号量及P、V操作的应用–进程的互斥semaphoreS;//设置公有信号量S=1;//初值{…P(S);printfile1;V(S);…}{…P(S);printfile2;V(S);…}2.在整型信号量机制中的wait操作，只要是信号量S≤0，就会不断地测试。因此，该机制并未遵循“让权等待”的准则，而是使进程处于“忙等”的状态。记录型信号量机制，则是一种不存在“忙等”现象的进程同步机制。但在采取了“让权等待”的策略后，又会出现多个进程等待访问同一临界资源的情况。为此，在信号量机制中，除了需要一个用于代表资源数目的整型变量value外，还应增加一个进程链表L，用于链接上述的所有等待进程。记录型信号量是由于它采用了记录型的数据结构而得名的。它所包含的上述两个数据项可描述为：typesemaphore=recordvalue:integer;L:listofprocess;end相应地，wait(S)和signal(S)proceduresignal(S)varS:semaphore;beginS.value∶=S.value+1;ifS.value≤0thenwakeup(S,L);endprocedurewait(S)varS:semaphore;beginS.value∶=S.value-1;ifS.value＜0thenblock(S,L)end17入口s.value=s.value-1s.value≥0调度进程入等待队列转进程调度入口s.value=s.value＋1s.value≤0唤醒等待队列中的一个进程返回或转进程调度返回返回s.value0是是否wait(S)原语操作功能流程图signal(S)原语操作功能流程图AND同步机制的基本思想是：将进程在整个运行过程中需要的所有资源，一次性全部地分配给进程，待进程使用完后再一起释放。只要尚有一个资源未能分配给进程，其它所有可能为之分配的资源，也不分配给他。亦即，对若干个临界资源的分配，采取原子操作方式：要么全部分配到进程，要么一个也不分配。由死锁理论可知，这样就可避免上述死锁情况的发生。为此，在wait操作中，增加了一个“AND”条件，故称为AND同步，或称为同时wait操作。3.AND型信号量例如：在两个进程中都要包含两个对Dmutex和Emutex的操作，即processA:processB:wait(Dmutex);wait(Emutex);wait(Emutex);wait(Dmutex);若进程A和B按下述次序交替执行waitprocessA:wait(Dmutex);于是Dmutex=0processB:wait(Emutex);于是Emutex=0processA:wait(Emutex);于是Emutex=-1AprocessB:wait(Dmutex);于是Dmutex=-1B阻塞Swait(S1,S2,…,Sn)ifSi≥1and…andSn≥1thenfori∶=1tondoSi∶=Si-1;endforelseplacetheprocessinthewaitingqueueassociatedwiththefirstSifoundwithSi＜1,andsettheprogramcountofthisprocesstothebeginningofSwaitoperationendifSsignal(S1,S2,…,Sn)fori∶=1tondoSi=Si+1;RemovealltheprocesswaitinginthequeueassociatedwithSiintothereadyqueue.endfor;21记录型信号量集机制中，wait(s)和signal(s)操作仅能对信号量施以增1和减1的操作，即每次只能获得或释放一个单位的临界资源。当一次需d个某类临界资源时，便需要进行d次wait(s)操作，这显然是低效的。此外，在有些情况下，要求当资源数量低于某一下限值时，便不予分配。故在每次分配之前，都必须测试该资源的数量是否不小于测试值t。基于以上两点可以对AND信号量机制进行扩充，形成一般化的“信号量集”机制。4.信号量集Swait(S1,t1,d1,…,Sn,tn,dn)ifSi≥t1and…andSn≥tnthenfori∶=1tondoSi∶=Si-di;endforelsePlacetheexecutingprocessinthewaitingqueueofthefirstSiwithSi＜tiandsetitsprogramcountertothebeginningoftheSwaitOperation.endifsignal(S1,d1,…,Sn,dn)fori∶=1tondoSi∶=Si+di;RemovealltheprocesswaitinginthequeueassociatedwithSiintothereadyqueueendfor;一般“信号量集”(1)Swait(S,d,d)。此时在信号量集中只有一个信号量S，但允许它每次申请d个资源，当现有资源数少于d时，不予分配。(2)Swait(S,1,1)。此时的信号量集已蜕化为一般的记录型信号量(S＞1时)或互斥信号量(S=1时)。(3)Swait(S,1,0)。这是一种很特殊且很有用的信号量操作。当S≥1时，允许多个进程进入某特定区；当S变为0后，将阻止任何进程进入特定区。换言之，它相当于一个可控开关。2.4.4信号量的应用1.利用信号量实现进程互斥Varmutex:semaphore∶=1;beginparbeginprocess1:beginrepeatwait(mutex);criticalsectionsignal(mutex);remainderseetionuntilfalse;endprocess2:beginrepeatwait(mutex);criticalsectionsignal(mutex);remaindersectionuntilfalse;endparend2.利用信号量实现前趋关系图2-14前趋图举例S4S5S3S1S6S2Vara,b,c,d,e,f,g;semaphore∶=0,0,0,0,0,0,0;beginparbeginbeginS1;signal(a);signal(b);end;beginwait(a);S2;signal(c);signal(d);end;beginwait(b);S3;signal(e);end;beginwait(c);S4;signal(f);end;beginwait(d);S5;signal(g);end;beginwait(e);wait(f);wait(g);S6;end;parendend第27页2.4.5管程机制管程(monitor)–定义：1973年，Hoare和BrinchHanson提出，他们给出的定义“一个管程定义了一个数据结构和能为并发进程所执行(在该数据结构上)的一组操作，这组操作能同步进程和改变管程中的数据”。简单说来：管程是由若干公共变量和所有访问这些变量的过程所组成的一个特殊的模块或软件包。–基本思想：集中管理各进程中的临界区：管程把分散在各个进程中互斥