操作系统ch3进程同步

1、第三章 进程的同步与通信,进程互斥 信号量和、操作 进程同步 经典的进程同步问题 进程通信,1,进程互斥,基本概念 利用软件方法解决进程互斥问题 利用硬件方法解决进程互斥问题 用上锁开锁原语实现进程互斥,2,案例,与时间有关的错误: 一飞机订票系统，两个终端，运行T1、T2进程 T1 : T2: . . Read(x); Read(x); if x=1 then if x=1 then x:=x-1; x:=x-1; write(x); write(x); . .,3,基本概念（1）,同步：对于进程操作的时间顺序所加的某种限制，如操作应在之前执行。 互斥：同步的特例，多个操作决不能同时执行， 如：操作和操作不能在同时执行。 （注意：理解不能同时执行的准确含义）,4,基本概念（2）,临界资源(critical resource)：一次仅允许一个进程访问的资源。 如：进程共享一台打印机，若让它们交替使用则得到的结果肯定不是我们希望的。 临界资源可能是硬件，也可能是软件：变量，数据，表格，队列等。 并发进程对临界资源的访问必须作某种限制，否则就可能出与时间有关的错误，如：联网售票。,5,基本

2、概念（3）,临界区(critical section)：临界段，在每个程序中，访问临界资源的那段程序。 注意：临界区是对某一临界资源而言的，对于不同临界资源的临界区，它们之间不存在互斥。 如有程序段A、B是关于变量X的临界区，而C、D是关于变量Y的临界区，那么，A、B之间需要互斥执行，C、D之间也要互斥执行，而A与C、B与D之间不用互斥执行。,6,解决互斥的准则,为了禁止两个进程同时进入临界区内，可以采用软件办法或系统提供的同步机构来协调它们的关系。但是，不论用什么办法都要遵循下述准则： 1、当有若干进程欲进入它的临界区时，应在有限时间内使进程进入临界区。换言之，它们不应相互阻塞而致使彼此都不能进入临界区 2、每次至多有一个进程处于临界区。 3、进程在临界区内仅逗留有限的时间。,7,软件方法解决进程互斥,现在很少用软件方法解决互斥，但通过学习软件解法能使读者了解到，在早期进程互斥问题的解决并不是一件很简单的事。 假如有两个进程Pi和Pj，它们共享一个临界资源R。如何用软件方法使进程Pi和Pj能互斥地访问R。 下面介绍四个算法。,8,算法1,设整型变量turn，用于指示被允许进入临界区的

3、进程的编号，即若turn=i，表示进程Pi可进入。turn =j表示进程Pj可进入。,9,算法1的实现,进程Pi : Repeat While turni do no_op; Critical section turn:=j; Other code Until false;,10,算法1的问题,该算法可确保每次只允许一个进程进入临界区。但它强制两个进程轮流进入。如当Pi退出时将turn置为j，以便 Pj能进入，但Pj暂不需要进入，而这时Pi又需要进入时，它无法进入。这不能保证准则1。,11,算法2,设var flag:array01 of boolean，若flagi=true，表示进程Pi正在临界区内。flagi=false表示进程Pi不在临界区内。若flagj=true，表示进程Pj正在临界区内。flagj=false表示进程Pj不在临界区内。,12,算法2的实现,Pi进程： Repeat While flag j do no_op; flagi:=true; Critical section flagi:=false; Other code Until false;,13,算法2

4、的问题,该算法可确保准则1。但又出现新问题。当pi和pj都未进入时，它们各自的访问标志都为false。如果pi和pj几乎同时要求进入，它们都发现对方的标志为false，于是都进入了。 这不能保证准则2。,14,算法3,算法2 的问题在于：当进程Pi观察到进程Pj的标志为false后，便将自己的标志由false改为true，而正是在这两步之间，可能发生进程切换。当Pj运行时，它会观察到Pi的标志为false，从而可以将自己的标志设为true，并进入临界区。若在临界区的执行过程中发生了进程切换，Pi可能获得处理机而进入临界区。 在算法3 中，设var Flag:array01 of boolean，若flagi=true，表示进程Pi希望进入临界区内。若flagj=true，表示进程Pj希望进入临界区。,15,算法3的实现,Pi进程： Repeat flagi:=true; While flagj do no_op; Critical section flagi:=false; Other code Until false;,16,算法3的问题,该算法可确保准则2。但又出现新问题。它可能造

5、成谁也不能进入。如，当pi和pj几乎同时都要进入，分别把自己的标志置为true，都立即检查对方的标志，发现对方为true. 最终谁也不能进入。 这不能保证准则1。,17,算法4（正确算法）,组合算法1、3，为每一进程设标志位flagi，当flagi=true时，表示进程pi要求进入，或正在临界区中执行。此外再设一个变量turn，用于指示允许进入的进程编号。,18,算法4（续）,进程为了进入先置flagi=true，并置turn为j，表示应轮到pj进入。接着再判断flag j and turn=j的条件是否满足。若不满足则可进入。或者说，当flag j =false或者turn=i时，进程可以进入。前者表示pj未要求进入，后者表示仅允许pi进入。,19,算法4的实现,Repeat flagi:=true; turn:=j; While (flag j and turn=j) do no_op; Critical section flagi:=false; Other code Until false,20,算法4的实现（课本上）,Pi进程： Repeat flagi:=true; Whi

6、le flagj do no_op; begin flagi:=false; flagi:=true; end Critical section flagi:=false; Other code Until false;,21,软件解法的缺点,1. 忙等待 2. 实现过于复杂，需要较高的编程技巧,22,硬件方法解决进程互斥,用软件解决很难，现代计算机大多提供一些硬件指令。 利用Test-and-Set指令实现互斥 利用swap指令实现进程互斥,23,Test-and-Set指令实现互斥,Test-and-Set指令实现： function TS(var lock:boolean):boolean; begin if lock=0 then begin lock:=1; TS:=true; end else TS:=false end; 其中，有lock有两种状态：当lock=false时，表示该资源空闲；当lock=true时，表示该资源正在被使用。,24,Test-and-Set指令实现互斥（续）,TS指令的使用 为每个临界资源设置一个全局布尔变量lock，并赋初值false，表示资

7、源空闲。 repeat while TS(lock) do skip; critical section lock:=false; Other code Until false;,25,swap指令实现进程互斥,swap指令又称交换指令，X86中称为XCHG指令。 swap指令的实现： Procedure swap(var a,b:boolean); Var temp:boolean; Begin Temp:=a; A:=b; B:=temp; End;,26,swap指令的使用,为每一临界资源设置一个全局布尔变量lock，其初值为false，在每个进程中有局部布尔变量key。 Repeat key:=true; Repeat swap(lock,key); Until key=false; Critical section lock:=false; Other code Until false;,27,用原语实现进程互斥,锁即操作系统中的一标志位，表示资源可用，表示资源已被占用。用户程序不能对锁直接操作，必须通过操作系统提供的上锁和开锁原语来操作。 通常锁用w表示，上锁开锁原语分别用

8、lock(w)、unlock(w)来表示。,28,上锁和开锁原语,上锁原语lock(w)可描述为： L：if(w=1) goto L else w=1； 开锁原语unlock(w)可描述为： w=0；,29,用原语实现进程互斥,30,改进的上锁原语,31,上述上锁原语中存在忙等待。,改进的开锁原语,32,信号量及P、V操作,1965年，由荷兰学者Dijkstra提出（所以P、V分别是荷兰语的test (proberen) 和increment (verhogen) ） 一种卓有成效的进程同步机制 最初提出的是二元信号量（互斥） 推广到一般信号量（多值）（同步） P、V操作是原语,33,信号量：semaphore,是一个数据结构 定义如下： struct semaphore int value; pointer_PCB queue; 信号量说明： semaphore s;,34,P操作,P(s) s.value = s.value -1 ; if (s.value 0) 该进程状态置为等待状态 将该进程的PCB插入相应的等待队列末尾s.queue; ,35,V操作,V(s) s.valu

9、e = s.value +1; if (s.value = 0) 唤醒相应等待队列s.queue中等待的一个进程 改变其状态为就绪态 并将其插入就绪队列 ,36,信号量的使用,必须置一次且只能置一次初值 初值不能为负数 只能执行P、V操作,37,用P、V操作解决进程间互斥问题,38,信号量及P、V操作讨论,对于两个并发进程，互斥信号量的值仅取1、0和-1三个值 若1表示没有进程进入临界区 若0表示有一个进程进入临界区 若-1表示一个进程进入临界区，另一个进程等待进入。,39,思考,对于N个并发进程，信号量的取值范围是什么，有什么含义。,40,信号量及P、V操作讨论（3-1）,1) 信号量的物理含义： S0表示有S个资源可用 S=0表示无资源可用 S0则| S |表示S等待队列中的进程个数 P(S)：表示申请一个资源 V(S)：表示释放一个资源 信号量的初值应该大于等于0,41,信号量及P、V操作讨论（3-2）,2) P、V操作必须成对出现，有一个P操作就一定有一个V操作 当为互斥操作时，它们同处于同一进程 当为同步操作时，则不在同一进程中出现 如果P(S1)和P(S2)两个操作在一起，那么P操作的顺序至关重要。 一个同步P操作与一个互斥P操作在一起时同步P操作在互斥P操作前。 而两个V操作无关紧要,42,信号量及P、V操作讨论（3-3）,3）P、V操作的优缺点 优点： 简单，而且表达能力强（用P、V操作可解决任何同步互斥问题） 缺点： 不够安全，P、V操作使用不当会出现死锁； 遇到复杂同步互斥问题时实现复杂,43,信号量集AND型信号量集,AND型信号量集是指同时需要多种资源且每种占用一个时的信号量操作 AND型信号量集的基本思想：在一个原语中申请整段代码需要的多个临界资源，要么全部分配给它，要么一个都不分配 AND型信号量集P原语为Swait AND型信号量集V原语为Ssignal,44,Swait原语,Swait(S1, S2, , Sn) /P原语； if

《操作系统ch3进程同步》由会员san****019分享，可在线阅读，更多相关《操作系统ch3进程同步》请在金锄头文库上搜索。