操作系统进程同步互斥问题.doc

利用软件方法解决进程互斥问题假设有两个进程Pi和Pj,它们共享一个临界资源R，请使用软件方法使进程Pi和Pj能互斥地访问资源R。算法1：设置整形变量turn,用于指示被允许进入临界区的进程的编号，即若turn=0,表示允许进程Pi进入临界区。注意：该算法强制两个进程轮流进入临界区，不考虑实际需要。很容易造成资源的不充分利用。对Pi进程的描述如下：repeatwhile turn i do no-opcritical sectionturn:=jremainder sectionuntil false算法2：在每一个进程访问临界资源之前，先去查看一下临界资源是否正被访问，若正被访问，该进程等待；否则，进入自己的临界区。设置数组flag，使其中每个元素的初值为false表示所有进程都未进入临界区，而当其中的第i个元素值非false时，即若flagi=ture 表示进程 Pi正在临界区内执行。注意：该算法解决了有空让进的原则，但当Pi和Pj的访问标志flag都为 false时，如果Pi 和Pj几乎同时都要求进入临界区，因而都发现对方的标志为false，于是，两进程都 先后进入临界区，又违背了忙则等待的原则。算法描述如下：Var flag:arry0,1,n of Boolean;RepeatWhile flagj do no-opFlagi:=true;Critical sectionFlagi:=false;Remainder sectionUntil false算法3：设数组flagn,当flagi=ture表示进程Pi希望进入临界区，即每当Pi要进入临界区前，先将flagi=ture表示进程已要求进入临界区，再去查看Pj的标志，若flagj=ture,则Pi等待，否则，Pi进入临界区。（即要求进入临界区的进程先设置其要求进入的标志，然后再去查看其他进程的标志）注意：该算法可以有效地防止两个进程进入临界区，但又可能导致最终都不进入临界区的情况它即违背了“有空让进”的准则，又违背了“有限等待”的准则，描述如下：repeatflagi:=ture;while flagi do no-opcritical sectionflagi:=false;remainder sectionuntil false算法4：该算法为进程Pi设置了标志位flagi,当flagi=ture表示Pi要求进入临界区，或正在临界区中执行。还设置了ture变量指示允许进入临界区的进程编号。注意：保证了“忙则等待”和“有空让进“的准则。Repeatflagi:=ture；turn：=j; 表示Pi已进入临界区，轮到Pj进入临界区。while flagi and turn:=j do no-op ； 若flagi and turn:=j为false,则Pj进入临界区。critical sectionflagi:=false;remainder sectionuntil false用硬件法解决进程互斥的问题1、利用Testand-set指令实现互斥function TS （VAR lock：boolean）：boolean；begin TS：=lock；Lock：=true；End其中：lock=false表示该资源空闲；当lock=true表示该资源正在使用。2、利用TS实现进程互斥(1)可为每个临界资源设置一个布尔变量lock，初值为false表示资源空闲。Function TS (var lock:Boolean):BooleanBeginTS:=lock;Lock:=true;End(2)利用TS实现进程互斥为每一个临界资源设置一个布尔变量lock，初值为false表示资源空闲；用TS指令将变量lock的状态记录在变量TS中，并将true赋予lock；这等于关闭了临界区，使任何进程都不能进入临界区。利用TS指令实现互斥的循环进程可描述为：repeat while TS(lock) do skip;critical sectionlock:=false;remainder sectionuntil false3、利用Swap指令实现进程互斥（1）Swap指令Procedure Swap (var a,b:Boolean) (交换两个字的内容)Var temp:boolean;Begin Temp:=a;A:=b;B:=temp;End （2）利用Swap指令实现进程互斥re