OS4(同步软硬件方法)

操作系统2.3进程同步2.3.1进程同步的基本概念2.3.2信号量(semaphore)2.3.3经典进程同步问题2.3.4进程间通信操作系统正常行车到站停车开车售票开车门关车门司机售票员合作合作进程间的合作关系操作系统打印进程1打印进程2打印打印获得打印数据获得打印数据竞争进程间竞争资源操作系统计算进程打印进程计算结果送到Buffer从Buffer中取数Buffer竞争竞争完成数据计算打印通知打印进程打印通知计算进程送下一个数合作与竞争合作合作操作系统相互合作竞争资源司机与售票员多个打印者计算者与打印者进程间存在两种关系协调好这些关系的过程——进程的同步操作顺序冲突共享外设、内存（变量）等资源操作系统竞争资源关系——直接相互制约：

进程同步的主要任务：保证诸进程能互斥地访问临界资源相互合作关系——间接相互制约：

进程同步的主要任务：保证相互合作的诸进程在执行次序上的协调——同步。2.3.1进程同步的基本概念P48操作系统计算进程打印进程计算结果送到Buffer从Buffer中取数Buffer互斥互斥向打印进程发信号通知其从Buffer里取数Buffer空？否是完成数据计算打印向计算进程发信号通知其向Buffer送数Buffer空？否是协调计算进程与打印进程的同步操作系统1.临界资源对于计算机中的有些软硬件资源，当多个进程对其进行访问时（关键是进行写入或修改），必须互斥地进行，这些一次只允许一个进程使用的资源称为临界资源(criticalresource)。打印机、内存变量、指针、数组等都是临界资源。生活中的例子如：电话机等。临界资源需要采用互斥方式，实现对资源的共享。操作系统2、临界区每个进程中访问临界资源的那段程序段称为临界区（criticalsection）。操作系统访问临界资源的循环进程Untilfalse;EntrysectionCriticalsection;ExitsectionRemaindersection;Repeat

进入区：进入临界区之前，检查可否进入临界区的一段代码。如果可以进入临界区，通常设置相应“正在访问临界区”标志；临界区：进程中访问临界资源的一段代码；

退出区：用于将"正在访问临界区"标志清除。

剩余区：代码中的其余部分。操作系统进入区临界区退出区进入区临界区退出区........................阻塞等待资源释放改变资源状态释放资源进程1进程2进入区、退出区各部分的作用互斥是针对不同进程访问同一临界资源。进程互斥进程互斥进程互斥是指若干共享临界资源的进程彼此交换信息以保证排他性的进入各自的临界区，即当若干个进程都要使用某一共享资源时，任何时刻最多只允许一个进程使用该资源，其他要使用该资源的进程必须等待，直到占有资源者释放该资源所谓同步是指若干相互合作的进程彼此交换信息以保证在执行次序上的协调。进程同步：进程同步是指若干相互合作的进程在一些关键点上可能需要互相等待或互相交换信息。进程同步进程互斥可在具有一定逻辑关系的伙伴进程之间，也可在非伙伴进程之间；同步发生在相互有逻辑关系的伙伴进程之间。进程同步是一般情况，互斥是同步的一种特殊情况。进程同步和互斥的关系操作系统3、同步机制应遵循的准则空闲则入：其他进程均不处于临界区；忙则等待：已有进程处于其临界区；有限等待：等待进入临界区的进程不能"死等"；让权等待：不能进入临界区的进程，应释放CPU（如转换到阻塞状态）解决互斥问题既可采用软件方法，也可采用硬件方法。4、进程互斥的基本方法软件实现方法就是在进入区设置和检查一些标志来标明是否有进程在临界区中，如果已有进程在临界区中，则在进入区通过循环检查进行等待，进程离开临界区后则在退出区修改标志。有两个进程Pi和Pj，它们互斥的共享某个临界资源。Pi和Pj是循环进程，它们执行一个无限循环程序，每次使用该资源一个有限的时间间隔。

(1)进程互斥的软件方法（补充）

例如:操作系统算法1：强制轮换法（单标志）

设立一个公用整型变量turn：描述允许进入临界区的进程标识在进入区检查是否允许本进程进入:turn为i时,进程Pi可进入;在退出区修改turn的值：进程Pi退出时,改turn为j；缺点： 强制轮流进入临界区，没有考虑进程的实际需要。容易造成资源利用不充分： 在Pi出让临界区之后，Pj使用临界区之前，Pi不可能再次使用临界区；Untilfalse;RepeatWhileturnidono_opCriticalsection;turn:=j;remaindersection;对两个进程Pi,Pj，其中的Pi描述如下图以进程P0、P1为例，类C语法的伪码描述P0进程如下：

intturn=0；

//公共变量

进程P0：do{while(turn!=0);//进入区

Criticalsection；//临界区

turn=1;//退出区P0其他代码；//剩余区

}while(true);P0退出临界区后将turn置1，以便允许P1进入临界区，但若P1暂时并未要求访问该临界资源，恰好P0又想再次访问该临界资源，则P0将无法进入临界区。此算法不能保证“空闲让进”准则。操作系统算法2：锁变量方法（双标志、先检查）优点:不用交替进入,可连续使用缺点：Pi和Pj可能同时进入临界区。按下面序列执行时，会同时进入："Pi<a>Pj<a>Pi<b>Pj<b>"。Untilfalse;Whileflag[j]dono_op<a>Flag[i]:=true；<b>Criticalsection;Flag[i]:=false;remaindersection;Repeat设立一个标志数组flag[]：描述进程是否在临界区，初值均为FALSE。先检查，后修改：在进入区检查另一个进程是否在临界区，不在时修改本进程在临界区的标志；在退出区修改本进程在临界区的标志；do{while(flag[1]);//进入区

flag[0]=true;//进入区P0的临界区代码；//临界区

flag[0]=false;//退出区

P0的其他代码；//剩余区}while(true);enumboolean{false,true};booleanflag[2]={false,false};//公共变量以进程P0、P1为例，类C语法的伪码描述P0进程如下：

进程P0：当两个进程都未进入临界区时，它们各自的访问标志都为false，若此时两个进程几乎同时都想进入临界区，并且都发现对方标志值为false，两进程同时进入了各自的临界区，违背了临界区访问的“忙则等待”原则。操作系统算法3：锁变量方法（双标志、后检查）缺点：Pi和Pj可能都进入不了临界区。按下面序列执行时，会都进不了临界区："Pi<a>Pj<a>Pi<b>Pj<b>"。Untilfalse;Flag[i]:=true；<a>Whileflag[j]dono_op<b>Criticalsection;Flag[i]:=false;remaindersection;Repeat类似于算法2，与2的区别在于先修改后检查。可防止两个进程同时进入临界区。enumboolean{false,true};booleanflag[2]={false,false};//公共变量以进程P0、P1为例，类C语法的伪码描述P0进程如下：

进程P0：do{flag[0]=true;//进入区while(flag[1]);//进入区P0的临界区代码；//临界区

flag[0]=false;//退出区P0的其他代码；//剩余区}while(true);当两个进程几乎同时都想进入临界区时，由于“先修改、后检查”，它们分别将自己的标志置为true，并且同时去检查对方的状态，发现对方也是true，得知对方也要进入临界区，于是双方互相谦让，结果是谁也进不了临界区。算法3可以有效防止两个进程同时进入临界区，但存在两个进程都进入不了临界区的问题，即发生“饥饿”现象。在一个可以预见的时间内，一个或多个进程得不到满足，如都不能访问临界资源。在一个动态系统中，操作系统对每类系统资源(临界资源)需要确定一个分配策略，有时资源分配策略是不公平的，即不能保证等待时间上界的存在。当进程等待时间给进程推进和响应带明显影响时称发生了进程饥饿。“饥饿”现象产生“饥饿”现象的原因：操作系统算法4(Peterson’sAlgorithm)：

先修改、后检查、后修改者等待结合算法1和算法3，是正确的算法turn=j;描述可进入的进程（同时修改标志时）在进入区先修改后检查，并检查并发修改的先后：检查对方flag，如果不在临界区则自己进入——空闲则入否则再检查turn：保存的是较晚的一次赋值，则较晚的进程等待，较早的进程进入——先到先入，后到等待Untilfalse;Flag[i]:=true;turn:=j;While(flag[j]andturn=j)dono_opCriticalsection;Flag[i]:=false;remaindersection;Repeatdo{flag[0]=true; //进入区turn=1; //进入区while(flag[1]&&turn==1); //进入区P0的临界区代码； //临界区

flag[0]=false; //退出区P0的其他代码； //剩余区}while(true);enumboolean{false,true};booleanflag[2]={false,false};intturn;以进程P0、P1为例，类C语法的伪码描述P0进程如下：

进程P0：操作系统练习：假设只有P0和P1两个进程竞争临界资源，关于临界问题的一个算法如下，i为0或1。

试问该算法能够保证两个进程互斥的进入临界区？会不会出现死等（饥饿）现象？Untilfalse;retry:if(turn-1)turn:=i;if(turn

i)gotoretry;turn=-1;Criticalsection;turn:=0;remaindersection;Repeat操作系统(2)进程互斥的硬件方法P51完全利用软件方法，有很大局限性（如不适于多进程），实现过于复杂，需要高的编程技巧。可以利用某些硬件指令——其读写操作由一条指令完成，因而保证读操作与写操作不被打断；两种硬件方法：

中断屏蔽方法

硬件指令方法(TS指令，Swap指令)…关中断临界区开中断…优点：简单、有效缺点：限制了处理机交替执行程序的能力，执行效率降低。将关中断的权力交给用户进程，将使得某一个进程关中断后若不再开中断，则系统可能会因此终止。1.中断屏蔽方法操作系统2.利用TS实现进程互斥该指令读出标志后设置为TRUEbooleanTS(boolean*lock){booleanold;old=*lock;*lock=TRUE;returnold;}lock表示资源的两种状态：TRUE表示正被占用，FALSE表示空闲Test-and-Set指令操作系统TS实现进程互斥Untilfalse;WhileTS(lock)doskipCriticalsection;lock:=false;remaindersection;Repeat利用TS实现进程互斥：每个临界资源设置一个公共布尔变量lock，初值为FALSE在进入区利用TS进行