操作系统课件CCH07-ProcessSynchronization

1、Module 7: Process SynchronizationBackground（背景）（背景）The Critical-Section Problem （临界区问题）（临界区问题）Synchronization Hardware （同步的硬件实现）（同步的硬件实现）Semaphores （信号量）（信号量）Classical Problems of Synchronization（经典同步问题）经典同步问题）Monitors （管程）（管程）Java Synchronization （Java中的同步机制）中的同步机制）Synchronization in Solaris 2 （Sol

2、aris 2的同步机制）的同步机制）Synchronization in Windows NT （Windows NT的同步机制）的同步机制）7.1 Background 进程间的联系进程间的联系:相交进程：指多个并发进程在逻辑上有某种联系相交进程：指多个并发进程在逻辑上有某种联系无关进程：在逻辑上无任何联系的进程无关进程：在逻辑上无任何联系的进程7.1 Backgroundl进程间的制约关系进程间的制约关系 间接制约：间接制约：有些资源需要互斥使用，因此各进程竞有些资源需要互斥使用，因此各进程竞争使用这些资源独占分配到的部分或全部共享争使用这些资源独占分配到的部分或全部共享资源，进程的这种关

3、系为资源，进程的这种关系为进程的互斥进程的互斥 直接制约：直接制约：系统中一些进程需要相互合作，共同完系统中一些进程需要相互合作，共同完成一项任务。具体说，一个进程运行到某一点时要成一项任务。具体说，一个进程运行到某一点时要求另一伙伴进程为它提供消息，在未获得消息之前求另一伙伴进程为它提供消息，在未获得消息之前，该进程处于等待状态，获得消息后被唤醒进入就，该进程处于等待状态，获得消息后被唤醒进入就绪态绪态.进程的这种关系为进程的这种关系为进程的同步进程的同步7.1 Background共享变量的修改冲突共享变量的修改冲突间接制约间接制约操作顺序冲突操作顺序冲突直接制约直接制约有有3个进程：个进

4、程：get, copy和和put，它们对它们对4个存储区域个存储区域f、s、t和和g进行操作。进行操作。7.1 Background7.1 Background Concurrent access to shared data may result in data inconsistency（对共享数据的并发访问可能导致（对共享数据的并发访问可能导致数据的不一致性）数据的不一致性）. Maintaining data consistency requires mechanisms to ensure the orderly execution of cooperating processes（

5、要保持数据的一致性，就需要一种保证并（要保持数据的一致性，就需要一种保证并发进程的正确执行顺序的机制）发进程的正确执行顺序的机制）.A race condition Depending on which process reaches the shared resource first, we have several possible results!The bounded bufferenter( )remove( )producerconsumerBounded Buffer public class BoundedBuffer public void enter(Object item

6、) / producer calls this method public Object remove() / consumer calls this method/ potential race condition on countprivate volatile int count; enter( )public void enter(Object item) while( count = BUFFER_SIZE) ; / do nothing! count+; bufferin = item; in = (in+1) % BUFFER_SIZE;remove( )public Objec

7、t remove() Object item; while( count = 0) ; / do nothing! count-; item = bufferout; out = (out+1) % BUFFER_SIZE;+ and at the machine level+count:Register1=count;Register1=register1+1;Count=register1-count:Register2=count;Register2=register2-1;Count=register2Understanding the issue Concurrent access

8、to shared data may result in data inconsistency Lack of synchronization means results may be non-deterministic and non-repeatable In the bounded buffer solution, both the consumer and the producer update counter 临界区临界区(critical section)：进程中访问临界资源的进程中访问临界资源的一段代码。一段代码。 假定一个系统有假定一个系统有n个进程个进程P0,P1,Pn-1,

9、每个进程有每个进程有一个代码段称为临界区一个代码段称为临界区,在该区中进程可能修改共享在该区中进程可能修改共享变量变量更新一个表更新一个表写一个文件等写一个文件等.当一个进程在临界当一个进程在临界区中执行时区中执行时,其他进程都不能进入临界区其他进程都不能进入临界区7.2 临界区问题临界区问题7.2 临界区问题临界区问题 临界区的执行在时间上是互斥的临界区的执行在时间上是互斥的, ,进程必须请求进入进程必须请求进入临界区临界区 进入区进入区(entry section)：在进入临界区之前，检查可否进入在进入临界区之前，检查可否进入临界区的一段代码。如果可以进入临界区，通常设置相应临界区的一段代

10、码。如果可以进入临界区，通常设置相应“正在访问临界区正在访问临界区”标志。标志。 退出区退出区(exit section)：用于将用于将正在访问临界区正在访问临界区标志清除标志清除 剩余区剩余区(remainder section)：代码中的其余部分。代码中的其余部分。7.2 临界区问题临界区问题entry sectionexit section critical section remainder sectionSolution to Critical-Section Problem1.Mutual Exclusion. If process Pi is executing in its c

11、ritical section, then no other processes can be executing in their critical sections（互斥。假定进程（互斥。假定进程Pi在其临界区内执行，其他任在其临界区内执行，其他任何进程将被排斥在自己的临界区之外）何进程将被排斥在自己的临界区之外）.2. Progress. If no process is executing in its critical section and there exist some processes that wish to enter their critical section, t

12、hen the selection of the processes that will enter the critical section next cannot be postponed indefinitely（有空让进。当没有进程在临界区中执行时，需要进（有空让进。当没有进程在临界区中执行时，需要进入临界区的进程，应能够很快进入入临界区的进程，应能够很快进入. ）3. Bounded Waiting. A bound must exist on the number of times that other processes are allowed to enter their cr

13、itical sections after a process has made a request to enter its critical section and before that request is granted（有限等待。在一个进程提出进入临界区的请求和该请求（有限等待。在一个进程提出进入临界区的请求和该请求得到答复的时间内，其他进程进入临界区的次数必须是有限的）得到答复的时间内，其他进程进入临界区的次数必须是有限的）.两进程互斥的软件方法两进程互斥的软件方法 算法算法1:单标志单标志 算法算法2：双标志、后检查：双标志、后检查 算法算法3(Petersons Algori

14、thm)：先修改、后检先修改、后检查；后修改者等待查；后修改者等待算法算法1：单标志：单标志 设立一个公用整型变量设立一个公用整型变量 turn：描述允许进入临界区描述允许进入临界区的进程标识的进程标识.有两个进程有两个进程Pi, Pj，其中的其中的Piwhile (turn != i);critical sectionturn = j;remainder section在进入区循环检查是否允许本进程进入：在进入区循环检查是否允许本进程进入：turn为为i时，进程时，进程Pi可进入；可进入；在退出区修改允许进入进程标识：进程在退出区修改允许进入进程标识：进程Pi退出时，改退出时，改turn为进

15、程为进程Pj的的标识标识j； 缺点：强制轮流进入临界区，没有考虑进程缺点：强制轮流进入临界区，没有考虑进程的实际需要。容易造成资源利用不充分：在的实际需要。容易造成资源利用不充分：在进程进程1出让临界区之后，进程出让临界区之后，进程2使用临界区之使用临界区之前，进程前，进程1不可能再次使用临界区；不可能再次使用临界区；Algorithm 1算法算法2：双标志、后检查：双标志、后检查 设立一个标志数组设立一个标志数组flag：描述进程是否在临界区，初描述进程是否在临界区，初值均为值均为FALSE,先修改后检查。可防止两个进程同时进先修改后检查。可防止两个进程同时进入临界区。入临界区。flagi

16、= TRUE;while (flagj);critical sectionflagi = FALSE;remainder section 缺点：缺点： Pi和和Pj可能都进入不了临界区。按下面序列执可能都进入不了临界区。按下面序列执行时，会都进不了临界区：行时，会都进不了临界区：Pi Pj Pi Pj。即在切换自己即在切换自己flag之后和检查对方之后和检查对方flag之前之前有一段时间，结果都切换有一段时间，结果都切换flag，都检查不通过。都检查不通过。Algorithm 2算法算法3(Petersons Algorithm)：先修改、后检查；后修改者等待先修改、后检查；后修改者等待tur

17、n=j;描述可进入的进程（同时修改标志时）描述可进入的进程（同时修改标志时）在进入区先修改后检查，并检查并发修改的先后：在进入区先修改后检查，并检查并发修改的先后： 检查对方检查对方flag，如果不在临界区则自己进入空闲则入如果不在临界区则自己进入空闲则入 否则再检查否则再检查turn：保存的是较晚的一次赋值，则较晚的进程等待，保存的是较晚的一次赋值，则较晚的进程等待，较早的进程进入先到先入，后到等待较早的进程进入先到先入，后到等待flagi = TRUE; turn = j;while (flagj & turn = j);critical sectionflagi = FALSE;rema

18、inder section7.3 进程互斥的硬件方法进程互斥的硬件方法 完全利用软件方法，有很大局限性（如不适于多进完全利用软件方法，有很大局限性（如不适于多进程），现在已很少采用。程），现在已很少采用。 特殊硬件指令原子地执行，因而保证读写操作特殊硬件指令原子地执行，因而保证读写操作不被中断不被中断: Test-and-Set (TS)指令指令 SWAP指令指令Test-and-Set指令指令为每个临界资源设置一个公共布尔变量为每个临界资源设置一个公共布尔变量lock，初值为初值为FALSElock表示资源的两种状态：表示资源的两种状态：TRUE:占用占用FALSE:空闲空闲该指令读出标志后

19、设置为该指令读出标志后设置为TRUE boolean TS(boolean *lock) boolean old; old = *lock; *lock = TRUE; return old; Test-and-Set指令指令 在进入区利用在进入区利用TS进行检查：进行检查：有进程在临界区时，重复有进程在临界区时，重复检查；直到其它进程退出检查；直到其它进程退出时，检查通过；时，检查通过； 在退出区置在退出区置lock为为FALSEwhile TS(&lock);lock = FALSE;critical sectionremainder sectionSwap instruction交换两个

20、字（字节）的内容交换两个字（字节）的内容void SWAP(int *a, int *b) int temp; temp = *a; *a = *b; *b = temp;Swap instruction 利用利用Swap实现进程互斥：每个临界资源设置一个公共实现进程互斥：每个临界资源设置一个公共布尔变量布尔变量lock，初值为初值为FALSE。每个进程设置一个私每个进程设置一个私有布尔变量有布尔变量keykey = TRUE;do SWAP(&lock, &key); while (key);lock = FALSE;critical sectionremainder section硬件方法

21、的优点硬件方法的优点 适用于任意数目的进程适用于任意数目的进程 简单，容易验证其正确性简单，容易验证其正确性 可以支持进程内存在多个临界区，只需为每个临界可以支持进程内存在多个临界区，只需为每个临界区设立一个布尔变量区设立一个布尔变量硬件方法的缺点硬件方法的缺点 等待要耗费等待要耗费CPU时间时间 可能可能饥饿饥饿：从等待进程中随机选择一个进入临界：从等待进程中随机选择一个进入临界区，有的进程可能一直选不上区，有的进程可能一直选不上 可能死锁可能死锁Synchronization Hardware7.4 进程的同步机制进程的同步机制 进程在并发执行时为了保证结果的可再现性，对各进进程在并发执行

22、时为了保证结果的可再现性，对各进程的执行次序必须加以限制程的执行次序必须加以限制,以保证互斥地使用临界以保证互斥地使用临界资源，相互合作完成任务。资源，相互合作完成任务。l前面的互斥算法都存在问题，它们是平等进程间的一前面的互斥算法都存在问题，它们是平等进程间的一种协商机制，需要一个地位高于进程的管理者来解决种协商机制，需要一个地位高于进程的管理者来解决公有资源的使用问题。公有资源的使用问题。 多个相关进程在执行次序上的协调称为进程同步。多个相关进程在执行次序上的协调称为进程同步。 用于保证多个进程在执行次序上的协调关系的相应机用于保证多个进程在执行次序上的协调关系的相应机制称为进程同步机制。

23、制称为进程同步机制。Semaphore信号量信号量lOS从进程管理者的角度来处理互斥的问题，信从进程管理者的角度来处理互斥的问题，信号量就是号量就是OS提供的管理公有资源的有效手段。提供的管理公有资源的有效手段。l1965年，信号量由荷兰学者年，信号量由荷兰学者Dijkstra提出（所提出（所以以P、V分别是荷兰语的分别是荷兰语的test(proberen)和和increment(verhogen)），），是一种卓有成效的进程是一种卓有成效的进程同步机制同步机制。Semaphore Implementation With busy wait : Atomicity Entire wait (S

24、) must be atomic How? Disable interrupts Or use another mutex solution, e.g., lockSemaphore Implementation with no Busy waiting With each semaphore there is an associated waiting queue. A waiting queue has two data items: value (of type integer) pointer to a list of PCBs Introduce a pointer in the P

25、CB structure Two operations: block place the process invoking the operation on the appropriate waiting queue. wakeup remove one of processes in the waiting queue and place it in the ready queue. FIFO ordering = bounded-waiting Is busy waiting completely gone? Semaphore Implementation with no Busy wa

26、iting (Cont.)Implementation of wait: wait (S) value-; if (value 0) add this process to waiting queue block(); Implementation of signal: Signal (S) value+; if (value = 0) remove a process P from the waiting queue wakeup(P); Semaphore Implementation with no Busy waiting: Atomicity Implementation of wa

27、it: wait (S) value-; if (value 0) add this process to waiting queue block(); Implementation of signal: Signal (S) value+; if (value = 0) remove a process P from the waiting queue wakeup(P); How to make these atomic?Semaphore Implementation with no Busy waiting: Atomicity Uniprocessors Disable interr

28、upts during wait and signal Once interrupts are disabled, instructions from different processes cannot be interleaved. Only the currently running process executes until interrupts are re-enabled and the scheduler can regain control. Multi-processors Inhibiting interrupts does not work Instructions f

29、rom different processes (running on different processors) may be interleaved in some arbitrary way If the hardware does not provide any special instructions, we can employ any of the correct software solutions (e.g., Petersons, Bakery) for the critical-section problem, where the critical sections co

30、nsist of the wait and signal operations (EXTREMELY COOL) So, we have not completely eliminated busy waiting with this definition of wait and signal We have moved busy waiting to the critical sections Furthermore, we have limited busy waiting to the critical sections of wait and signalSemaphore Imple

31、mentation with no Busy waiting: Atomicity Uniprocessors Disable interrupts during wait and signal Once interrupts are disabled, instructions from different processes cannot be interleaved. Only the currently running process executes until interrupts are re-enabled and the scheduler can regain contro

32、l. Multi-processors Inhibiting interrupts does not work Instructions from different processes (running on different processors) may be interleaved in some arbitrary way If the hardware does not provide any special instructions, we can employ any of the correct software solutions (e.g., Petersons, Ba

33、kery) for the critical-section problem, where the critical sections consist of the wait and signal operations (EXTREMELY COOL) So, we have not completely eliminated busy waiting with this definition of wait and signal We have moved busy waiting to the critical sections Furthermore, we have limited b

34、usy waiting to the critical sections of wait and signalSemaphore Implementation with no Busy waiting: Atomicity Uniprocessors Disable interrupts during wait and signal Once interrupts are disabled, instructions from different processes cannot be interleaved. Only the currently running process execut

35、es until interrupts are re-enabled and the scheduler can regain control. Multi-processors Inhibiting interrupts does not work Instructions from different processes (running on different processors) may be interleaved in some arbitrary way If the hardware does not provide any special instructions, we

36、 can employ any of the correct software solutions (e.g., Petersons) for the critical-section problem, where the critical sections consist of the wait and signal operations (EXTREMELY COOL) So, we have not completely eliminated busy waiting with this definition of wait and signal We have moved busy w

37、aiting to the critical sections Furthermore, we have limited busy waiting to the critical sections of wait and signal信号量和信号量和P、V原语原语 S是与临界区内所使用的公用资源有关的信号量是与临界区内所使用的公用资源有关的信号量 S0 可供并发进程使用的资源数可供并发进程使用的资源数 S=1 & S2 = 1 & & Sn = 1) /满足资源要求时的处理；满足资源要求时的处理； for (i = 1; i = n; +i) -Si; /注：与注：与wait的处理不同，这里是

38、在确信可满足的处理不同，这里是在确信可满足 /全部资源要求时，才进行减全部资源要求时，才进行减1操作；操作； break; else /某些资源不够时的处理；某些资源不够时的处理； 进程进入第一个小于进程进入第一个小于1信号量的等待队列信号量的等待队列Sj.queue; 阻塞调用进程阻塞调用进程; AND型信号量集型信号量集 Ssignal(S1, S2, , Sn) for (i = 1; i = n; +i) +Si;/释放占用的资源；释放占用的资源； for (each process P waiting in Si.queue) /检查每种资源的等待队列；检查每种资源的等待队列； 从等

39、待队列从等待队列Si.queue中取出进程中取出进程P; if (判断进程判断进程P是否通过是否通过Swait中的测试中的测试) /注：与注：与signal不同，这里要进行重新判断；不同，这里要进行重新判断； /通过检查（资源够用）时的处理；通过检查（资源够用）时的处理； 进程进程P进入就绪队列进入就绪队列; else /未通过检查（资源不够用）时的处理；未通过检查（资源不够用）时的处理； 进程进程P进入某等待队列；进入某等待队列； AND型信号量集型信号量集一般信号量集一般信号量集l一般信号量集用于同时需要多种资源、每种占用的数目不同、且可一般信号量集用于同时需要多种资源、每种占用的数目不同

40、、且可分配的资源还存在一个临界值时的处理；分配的资源还存在一个临界值时的处理；l一次需要一次需要N个某类临界资源时，就要进行个某类临界资源时，就要进行N次次wait操作低效又操作低效又可能死锁可能死锁l基本思想：在基本思想：在AND型信号量集的基础上进行扩充：进程对信号量型信号量集的基础上进行扩充：进程对信号量Si的测试值为的测试值为ti（用于信号量的判断，即用于信号量的判断，即Si =1时，允许多个进程进入临界区；时，允许多个进程进入临界区； 当当S=0时，禁止任何进程进入临界区；时，禁止任何进程进入临界区；一般信号量集未必成对使用一般信号量集未必成对使用Swait和和Ssignal：如：一

41、起申请，但不如：一起申请，但不一起释放；一起释放；一般信号量集一般信号量集Semaphore机制机制l同步、互斥的约束条件同步、互斥的约束条件l临界资源的抽象临界资源的抽象l初始条件初始条件l正确的正确的P-V操作操作7.5 Classical Problems of Synchronization Dining-Philosophers Problem （哲学家就餐问题）（哲学家就餐问题） Bounded-Buffer Problem （有限缓冲区问题）（有限缓冲区问题） Readers and Writers Problem （读者写者问题）（读者写者问题）7.5.1 哲学家进餐问题哲学家

42、进餐问题(the dining philosophers problem)l问题描述：（由问题描述：（由Dijkstra首先提出并解决）首先提出并解决）5个哲个哲学家围绕一张圆桌而坐，桌子上放着学家围绕一张圆桌而坐，桌子上放着5支筷子，每支筷子，每两个哲学家之间放一支；哲学家的动作包括思考和两个哲学家之间放一支；哲学家的动作包括思考和进餐，进餐时需要同时拿起他左边和右边的两支筷进餐，进餐时需要同时拿起他左边和右边的两支筷子，思考时则同时将两支筷子放回原处。如何保证子，思考时则同时将两支筷子放回原处。如何保证哲学家们的动作有序进行？哲学家们的动作有序进行？Dining-Philosophers

43、ProblemShared data Semaphore chopStick = new Semaphore5;Repeat 思考；思考； 取取chopSticki; 取取chopStick(i+1) mod 5； 进食；进食； 放放chopSticki; 放放chopStick(i+1) mod 5；Until false;Philosopher(i)Dining-Philosophers Problem (Cont.)Philosopher i:while (true) / get left chopstickchopSticki.P();/ get right chopstickchop

44、Stick(i + 1) % 5.P();/ eat for a while/return left chopstick chopSticki.V();/ return right chopstick chopStick(i + 1) % 5.V();/ think for awhileDining-Philosophers Problem (Cont.) The structure of Philosopher i:do wait ( chopsticki ); wait ( chopStick (i + 1) % 5 ); / eat signal ( chopsticki ); sign

45、al (chopstick (i + 1) % 5 ); / think while (TRUE);Deadlock? Starvation?What happens if all pick their left chopsticks?为防止死锁发生可采取的措施： 最多允许4个哲学家同时坐在桌子周围 仅当一个哲学家左右两边的筷子都可用时，才允许他拿筷子（） 给所有哲学家编号，奇数号的哲学家必须首先拿左边的筷子，偶数号的哲学家则反之 为了避免死锁，把哲学家分为三种状态，思考，饥饿，进食，并且一次拿到两只筷子，否则不拿 state:array0.4 of (思考，饥饿，进食）； ph: array

46、0.4 of semaphore; mutex:semaphore; i:0.4;Procedure test(i:=04); begin if (state i = 饥饿饥饿) And (state(i-1)mod5进食进食) And (state(i+1)mod5进食进食) then begin state i =进食进食 V(ph i ) end endProcedure philosopher(i: 04) Begin Repeat 思考；思考； statei :=饥饿；饥饿； P(mutex); test(i); V(mutex); P(ph i ); 拿左筷子；拿左筷子； 拿右筷子

47、；拿右筷子； 进食；进食； 放左筷子；放左筷子； 放右筷子；放右筷子；P(mutex)state i :=思考；思考；test(i-1mod5);tset(i+1mod5);V(mutex);until falesEndstate I =思考思考ph I =0mutex=1解法：解法：AND型信号量型信号量Var chopstick array0,4 of semaphore :=(1,1,1,1,1);Processi Reeat think; Swait (chopstick(I+1) mod 5,chopstickI); Eat; Ssignal (chopstick(I+1) mod

48、5,chopstickI); Until false;7.5.2 生产者消费者问题生产者消费者问题(the producer-consumer problem)l若干进程通过若干进程通过有限有限的共享缓冲区交换数据。的共享缓冲区交换数据。-“生产者生产者”进程不断写入进程不断写入-“消费者消费者”进程不断读出进程不断读出-共享缓冲区共有共享缓冲区共有N个个-任何时刻只能有一个进程可对共享缓冲区进行操作任何时刻只能有一个进程可对共享缓冲区进行操作共享缓冲区生产指针消费指针Producer 1Producer 2.Producer MConsumer 1Consumer 2.Consumer N满

49、空指针移动方向采用信号量机制：采用信号量机制： full是是满满数目，初值为数目，初值为0，empty是是空空数目，初值为数目，初值为N。实际实际上，上，full + empty = N mutex用于访问缓冲区时的互斥，初值是用于访问缓冲区时的互斥，初值是1 每个进程中各个每个进程中各个P操作的次序是重要的：先检查资源数目，再检操作的次序是重要的：先检查资源数目，再检查是否互斥查是否互斥否则可能死锁否则可能死锁采用采用AND信号量集：信号量集：Swait(empty, mutex), Ssignal(full, mutex), 7.5.2 生产者消费者问题生产者消费者问题(the produ

50、cer-consumer problem)ConsumerProducerP(empty);P(mutex);/进入区 one unit - buffer;V(mutex);V(full);/退出区P(full);P(mutex);/进入区 one unit 0表示有表示有S个资源可用个资源可用 S=0表示无资源可用表示无资源可用 S= n then notfull.wait ; buffer ( in ) : = nextp ; in := (in+1) mod n ; count = count + 1 ; if notempty.queue then notempty.signal ;

51、end procedure entry get ( item) begin if count = 0 then notempty.wait ; nextc := buffer ( out ) ; out := (out+1) mod n ; count := count - 1 ;if notfull.queue then notfull.signal ; end begin in := out := 0 ; count := 0; end producer : begin repeat produce an item in nextp ; PC.put ( item) ; until false ; endconsumer : begin repeat PC.get (item) ; consume the item in nextc ; until false ; end利用管程解决生产者利用管程解决生产者消费者问题消费者问题Solution to Dining Philosophersmonit