OS4(同步软硬件方法)

1、Lifang 20151/25操作系统2.3 2.3 进程同步进程同步2.3.1 2.3.1 进程同步的基本概念进程同步的基本概念2.3.2 2.3.2 信号量信号量( (semaphore)semaphore)2.3.3 2.3.3 经典进程同步问题经典进程同步问题2.3.4 2.3.4 进程间通信进程间通信Lifang 20152/25操作系统正常行车到站停车开车售票开车门关车门司机售票员合作合作合作合作进程间的合作关系进程间的合作关系Lifang 20153/25操作系统打印进程打印进程1打印进程打印进程2打印打印打印打印获得打印数据获得打印数据获得打印数据获得打印数据竞争竞争进程间竞争

2、资源进程间竞争资源Lifang 20154/25操作系统计算进程计算进程打印进程打印进程计算结果送到计算结果送到Buffer从从Buffer中取数中取数Buffer竞争竞争竞争竞争完成数据计算完成数据计算打印打印通知打印进程打印通知打印进程打印通知计算进程通知计算进程送下一个数送下一个数合作与竞争合作与竞争合作合作合作合作Lifang 20155/25操作系统司机与售票员司机与售票员多个打印者多个打印者计算者与打印者计算者与打印者进程间存在两种关系进程间存在两种关系协调好这些关系的过程协调好这些关系的过程进程的同步进程的同步操作顺序冲突操作顺序冲突共享外设、内存（变共享外设、内存（变量）等资源

3、量）等资源Lifang 20156/25操作系统F竞争资源关系竞争资源关系直接相互制约：直接相互制约： 进程同步的主要任务：保证诸进程能进程同步的主要任务：保证诸进程能互斥互斥地地访问临界资源访问临界资源F相互合作关系相互合作关系间接相互制约：间接相互制约：进程同步的主要任务：保证相互合作的诸进进程同步的主要任务：保证相互合作的诸进程在执行次序上的协调程在执行次序上的协调同步同步。2.3.1 2.3.1 进程同步的基本概念进程同步的基本概念 P48P48Lifang 20157/25操作系统计算进程打印进程计算结果送到Buffer从Buffer中取数Buffer互斥互斥向打印进程发信号向打印进

4、程发信号通知其从通知其从Buffer里取数里取数Buffer空？空？否是完成数据计算完成数据计算打印打印向计算进程发信号向计算进程发信号通知其向通知其向Buffer送数送数Buffer空？空？否是协调计算进程与打印进程的同步计算进程与打印进程的同步Lifang 20158/25操作系统1.1.临界资源临界资源 对于计算机中的有些软硬件资源，当多个进程对其进对于计算机中的有些软硬件资源，当多个进程对其进行访问时（关键是进行写入或修改），必须互斥地进行访问时（关键是进行写入或修改），必须互斥地进行，这些一次只允许一个进程使用的资源称为行，这些一次只允许一个进程使用的资源称为临界资临界资源源( (c

5、ritical resource)critical resource)。打印机、内存变量、指针、数组等都是临界资源。打印机、内存变量、指针、数组等都是临界资源。生活中的例子如：电话机等。生活中的例子如：电话机等。临界资源需要采用互斥方式，实现对资源的共享。临界资源需要采用互斥方式，实现对资源的共享。Lifang 20159/25操作系统2 2、临界区、临界区 每个进程中访问临界每个进程中访问临界资源的那段程序段称为资源的那段程序段称为临界区（临界区（critical critical sectionsection）。）。Lifang 201510/25操作系统访问临界资源的循环进程访问临界资源

6、的循环进程Until false;Entry sectionCritical section;Exit sectionRemainder section;Repeat 进入区进入区：进入临界区之前，检查：进入临界区之前，检查可否进入临界区的一段代码。如果可否进入临界区的一段代码。如果可以进入临界区，通常设置相应可以进入临界区，通常设置相应“正在访问临界区正在访问临界区”标志；标志； 临界区：临界区：进程中访问临界资源的进程中访问临界资源的一段代码；一段代码； 退出区：退出区：用于将用于将 正在访问临界正在访问临界区区 标志清除。标志清除。 剩余区剩余区：代码中的其余部分。代码中的其余部分。Li

7、fang 201511/25操作系统进入区进入区临界区临界区退出区退出区进入区进入区临界区临界区退出区退出区.阻塞等待阻塞等待资源释放资源释放改变资源改变资源状态状态释放资源释放资源进程进程1进程进程2进入区、退出区各部分的作用进入区、退出区各部分的作用Lifang 201512/25v互斥是针对不同进程访问同一临界资源。进程互斥进程互斥进程互斥进程互斥是指若干共享临界资源的进程彼此交换信息以保证排他性的进入各自的临界区，即当若干个进程都要使用某一共享资源时，任何时刻最多只允许一个进程使用该资源，其他要使用该资源的进程必须等待，直到占有资源者释放该资源Lifang 201513/25所谓同步是

8、指若干相互合作的进程彼此交换信息以保证在执行次序上的协调。进程同步：进程同步是指若干相互合作的进程在一些关键点上可能需要互相等待或互相交换信息。进程同步进程同步Lifang 201514/25进程互斥可在具有一定逻辑关系的伙伴进程之间，也可在非伙伴进程之间；同步发生在相互有逻辑关系的伙伴进程之间。进程同步是一般情况，互斥是同步的一种特殊情况。进程同步和互斥的关系进程同步和互斥的关系Lifang 201515/25操作系统3 3、同步机制应遵循的准则、同步机制应遵循的准则空闲则入：其他进程均不处于临界区；空闲则入：其他进程均不处于临界区；忙则等待：已有进程处于其临界区；忙则等待：已有进程处于其临

9、界区；有限等待：等待进入临界区的进程不能有限等待：等待进入临界区的进程不能 死等死等 ；让权等待：不能进入临界区的进程，应释放让权等待：不能进入临界区的进程，应释放CPUCPU（如转换到阻塞状态）如转换到阻塞状态）Lifang 201516/25v解决互斥问题既可采用软件方法，也可采用硬件方法。4 4、进程互斥的、进程互斥的基本基本方法方法软件实现方法就是在进入区设置和检查一些标志来标明是否有进程在临界区中，如果已有进程在临界区中，则在进入区通过循环检查进行等待，进程离开临界区后则在退出区修改标志。Lifang 201517/25v有两个进程Pi和Pj，它们互斥的共享某个临界资源。vPi和Pj

10、是循环进程，它们执行一个无限循环程序，每次使用该资源一个有限的时间间隔。 (1) 进程互斥的软件方法（补充）进程互斥的软件方法（补充）例如例如: :Lifang 201518/25操作系统算法算法1：强制轮换法（单标志）：强制轮换法（单标志）n设立一个公用整型变量设立一个公用整型变量 turnturn：描述允许进入临界区的进程标识描述允许进入临界区的进程标识F在进入区检查是否允许本进程进入在进入区检查是否允许本进程进入:turn:turn为为i i时时, ,进程进程PiPi可进入可进入; ;F在退出区修改在退出区修改turnturn的值：的值：进程进程PiPi退出时退出时, ,改改turntu

11、rn为为j j；n缺点：缺点：强制轮流强制轮流进入临界区，没进入临界区，没有考虑进程的实际需要。容易有考虑进程的实际需要。容易造成造成资源利用不充分资源利用不充分：在在PiPi出让临界区之后，出让临界区之后，PjPj使用临界区之前，使用临界区之前，PiPi不可能再不可能再次使用临界区；次使用临界区；Until false;RepeatWhile turn i do no_opCritical section;turn:=j;remainder section;n对两个进程对两个进程Pi, PjPi, Pj，其中的其中的PiPi描述如下图描述如下图Lifang 201519/25以进程以进程P0

12、、P1为例，类为例，类C语法的伪码描述语法的伪码描述P0进程如下：进程如下： int turn=0； /公共变量公共变量 进程P0：do while (turn!=0); /进入区 Critical section ； /临界区 turn=1; /退出区 P0其他代码； /剩余区 while (true);P0退出临界区后将turn置1，以便允许P1进入临界区，但若P1暂时并未要求访问该临界资源，恰好P0又想再次访问该临界资源，则P0将无法进入临界区。此算法不能保证“空闲让进”准则。Lifang 201520/25操作系统算法算法2 2：锁变量方法（双标志、先检查）：锁变量方法（双标志、先检查

13、）n优点优点: :不用交替进入不用交替进入, ,可连续使用可连续使用n缺点：缺点：PiPi和和PjPj可能同时进入临界可能同时进入临界区。按下面序列执行时，会同时区。按下面序列执行时，会同时进入：进入： Pi Pj Pi Pi Pj Pi PjPj。Until false;While flagj do no_op Flagi:=true； Critical section;Flagi:=false;remainder section;Repeatn设立一个标志数组设立一个标志数组flagflag：描述进程是否在临界区，初值均为描述进程是否在临界区，初值均为FALSEFALSE。F先检查，后修改

14、：在进入区检查另一个进程是否在临界区，不在时先检查，后修改：在进入区检查另一个进程是否在临界区，不在时修改本进程在临界区的标志；修改本进程在临界区的标志；F在退出区修改本进程在临界区的标志；在退出区修改本进程在临界区的标志；Lifang 201521/25do while (flag1); /进入区 flag0=true; /进入区 P0的临界区代码； /临界区 flag0=false; /退出区 P0的其他代码； /剩余区 while (true);venum boolean false, true;vboolean flag2=false, false; /公共变量公共变量以进程以进程P0

15、、P1为例，类为例，类C语法的伪码描述语法的伪码描述P0进程如下：进程如下：进程P0：v当两个进程都未进入临界区时，它们各自的访问标志都为false，若此时两个进程几乎同时都想进入临界区，并且都发现对方标志值为false，两进程同时进入了各自的临界区，违背了临界区访问的“忙则等待”原则。Lifang 201522/25操作系统算法算法3 3：锁变量方法（双标志、后检查）：锁变量方法（双标志、后检查）n缺点：缺点：PiPi和和PjPj可能都进入不了临界区可能都进入不了临界区。按下面序列执行。按下面序列执行时，会都进不了临界区：时，会都进不了临界区： Pi Pj Pi PjPi Pj Pi Pj。

16、Until false;Flagi:=true； While flagj do no_op Critical section;Flagi:=false;remainder section;Repeatn类似于算法类似于算法2 2，与，与2 2的区别在于先修改后检查。可防止两个进程同的区别在于先修改后检查。可防止两个进程同时进入临界区。时进入临界区。Lifang 201523/25venum boolean false, true;vboolean flag2=false, false; /公共变量公共变量以进程以进程P0、P1为例，类为例，类C语法的伪码描述语法的伪码描述P0进程如下：进程如下

17、：进程P0：do flag0=true; /进入区 while (flag1);/进入区 P0的临界区代码； /临界区 flag0=false; /退出区 P0的其他代码； /剩余区 while (true);当两个进程几乎同时都想进入临界区时，由于“先修改、后检查”，它们分别将自己的标志置为true，并且同时去检查对方的状态，发现对方也是true，得知对方也要进入临界区，于是双方互相谦让，结果是谁也进不了临界区。算法3可以有效防止两个进程同时进入临界区，但存在两个进程都进入不了临界区的问题，即发生“饥饿”现象。Lifang 201524/25在一个可以预见的时间内，一个或多个进程得不到满足，

18、在一个可以预见的时间内，一个或多个进程得不到满足，如都不能访问临界资源。如都不能访问临界资源。在一个动态系统中，操作系统对每类系统资源在一个动态系统中，操作系统对每类系统资源( (临界资源临界资源) )需要需要确定一个分配策略，有时资源分配策略是不公平的，即不能保确定一个分配策略，有时资源分配策略是不公平的，即不能保证等待时间上界的存在。当进程等待时间给进程推进和响应带证等待时间上界的存在。当进程等待时间给进程推进和响应带明显影响时称发生了进程饥饿。明显影响时称发生了进程饥饿。“饥饿”现象产生产生“饥饿饥饿”现象的原因：现象的原因：Lifang 201525/25操作系统算法算法4(Peter

19、son4(Petersons Algorithm)s Algorithm)：先修改、后检查、后修改者等待先修改、后检查、后修改者等待n结合算法结合算法1 1和算法和算法3 3，是正确的算法，是正确的算法nturn=j;turn=j;描述可进入的进程（同时修改标志时）描述可进入的进程（同时修改标志时）n在进入区先修改后检查，并检查并发修改的先后：在进入区先修改后检查，并检查并发修改的先后：F检查对方检查对方flagflag，如果不在临界区则自己进入如果不在临界区则自己进入空闲则入空闲则入F否则再检查否则再检查turnturn：保存的是较晚的一次赋值，则较晚的进保存的是较晚的一次赋值，则较晚的进程

20、等待，较早的进程进入程等待，较早的进程进入先到先入，后到等待先到先入，后到等待Until false;Flagi:=true;turn:=j;While(flagj and turn=j) do no_opCritical section;Flagi:=false;remainder section;RepeatLifang 201526/25do flag0=true; /进入区 turn=1; /进入区 while(flag1&turn=1); /进入区 P0的临界区代码； /临界区 flag0=false;/退出区 P0的其他代码； /剩余区while (true);enum boole

21、an false, true;boolean flag2=false, false; int turn;以进程以进程P0、P1为例，类为例，类C语法的伪码描述语法的伪码描述P0进程如下：进程如下： 进程P0：Lifang 201527/25操作系统练习：假设只有练习：假设只有P0P0和和P1P1两个进程竞争临界资源，关于临两个进程竞争临界资源，关于临界问题的一个算法如下，界问题的一个算法如下，i i为为0 0或或1 1。试问该算法能够保证两个进程互斥的进入临界区？会不试问该算法能够保证两个进程互斥的进入临界区？会不会出现死等（饥饿）现象？会出现死等（饥饿）现象？Until false;retr

22、y:if(turn-1) turn:=i;if(turn i) goto retry;turn=-1;Critical section;turn:=0;remainder section;RepeatLifang 201528/25操作系统(2)(2)进程互斥的硬件方法进程互斥的硬件方法 P51P51n完全利用软件方法，有很大局限性（如不适于多进程），实现过完全利用软件方法，有很大局限性（如不适于多进程），实现过于复杂，需要高的编程技巧。于复杂，需要高的编程技巧。n可以利用某些硬件指令可以利用某些硬件指令其读写操作由一条指令完成，因而保其读写操作由一条指令完成，因而保证读操作与写操作不被打断；

23、证读操作与写操作不被打断；两种硬件方法：两种硬件方法： 中断屏蔽方法中断屏蔽方法 硬件指令方法硬件指令方法(TS(TS指令，指令，SwapSwap指令指令) )Lifang 201529/25关中断关中断临界区临界区开中断开中断优点：优点：简单、有效简单、有效缺点：限制了处理机交替执行程序的能力，执行效率降低。将关中断的权力交给用户进程，将使得某一个进程关中断后若不再开中断，则系统可能会因此终止。1.中断屏蔽方法中断屏蔽方法Lifang 201530/25操作系统2.2.利用利用TSTS实现进程互斥实现进程互斥该指令读出标志后设置为该指令读出标志后设置为TRUETRUEboolean TS(b

24、oolean boolean TS(boolean * *lock) lock) boolean old; boolean old; old = old = * *lock; lock; * *lock = TRUE;lock = TRUE; return old; return old; locklock表示资源的两种状态：表示资源的两种状态：TRUETRUE表示正被占用，表示正被占用，FALSEFALSE表示空闲表示空闲Test-and-Set指令指令Lifang 201531/25操作系统TSTS实现进程互斥实现进程互斥Until false;While TS(lock) do skip

25、Critical section;lock:=false;remainder section;Repeatn利用利用TSTS实现进程互斥：每个临界资源设置一个公共布尔变量实现进程互斥：每个临界资源设置一个公共布尔变量locklock，初值为初值为FALSEFALSEn在进入区利用在进入区利用TSTS进行检查：有进程在临界区时，重复检查；进行检查：有进程在临界区时，重复检查；直到其它进程退出时，检查通过；直到其它进程退出时，检查通过；boolean TS(boolean boolean TS(boolean * *lock) lock) boolean old; boolean old; old = old = * *lock; lock; * *lock = lock = TRUE;TRUE; return old; return old; Lifang