操作系统4同步软硬件方法

2011201120114.4.4.1 1 1/21/21/21操作系统操作系统操作系统3.3 3.3 进程同步进程同步3.3.1 3.3.1 进程同步的基本概念进程同步的基本概念3.3.2 3.3.2 信号量信号量(semaphore)(semaphore)3.3.3 3.3.3 经典进程同步问题经典进程同步问题3.3.4 3.3.4 进程间通信进程间通信 2011201120114.4.4.2 2 2/21/21/21操作系统操作系统操作系统正常行车到站停车开车售票开车门关车门司机售票员合作合作合作合作进程间的合作关系进程间的合作关系 2011201120114.4.4.3 3 3/21/21/21操作系统操作系统操作系统打印进程打印进程1打印进程打印进程2打印打印打印打印获得打印数据获得打印数据获得打印数据获得打印数据竞争竞争进程间竞争资源进程间竞争资源 2011201120114.4.4.4 4 4/21/21/21操作系统操作系统操作系统计算进程计算进程打印进程打印进程计算结果送到计算结果送到Buffer从从Buffer中取数中取数Buffer竞争竞争竞争竞争完成数据计算完成数据计算打印打印通知打印进程打印通知打印进程打印通知计算进程通知计算进程送下一个数送下一个数合作与竞争合作与竞争合作合作合作合作 2011201120114.4.4.5 5 5/21/21/21操作系统操作系统操作系统司机与售票员司机与售票员多个打印者多个打印者计算者与打印者计算者与打印者进程间存在两种关系进程间存在两种关系协调好这些关系的过程协调好这些关系的过程进程的同步进程的同步操作顺序冲突操作顺序冲突共享外设、内存（变共享外设、内存（变量）等资源量）等资源 2011201120114.4.4.6 6 6/21/21/21操作系统操作系统操作系统F竞争资源关系：竞争资源关系： 进程同步的主要任务：保证诸进程能进程同步的主要任务：保证诸进程能互斥互斥地地访问临界资源访问临界资源F相互合作关系：相互合作关系：进程同步的主要任务：保证相互合作的诸进进程同步的主要任务：保证相互合作的诸进程在执行次序上的协调程在执行次序上的协调同步同步。3.3.1 3.3.1 进程同步的基本概念进程同步的基本概念 2011201120114.4.4.7 7 7/21/21/21操作系统操作系统操作系统计算进程打印进程计算结果送到Buffer从Buffer中取数Buffer互斥互斥向打印进程发信号向打印进程发信号通知其从通知其从Buffer里取数里取数Buffer空？空？否是完成数据计算完成数据计算打印打印向计算进程发信号向计算进程发信号通知其向通知其向Buffer送数送数Buffer空？空？否是协调计算进程与打印进程的同步计算进程与打印进程的同步 2011201120114.4.4.8 8 8/21/21/21操作系统操作系统操作系统1.1.临界资源临界资源 对于计算机中的有些软硬件资源，当多个进程对其进对于计算机中的有些软硬件资源，当多个进程对其进行访问时（关键是进行写入或修改），必须互斥地进行访问时（关键是进行写入或修改），必须互斥地进行，这些一次只允许一个进程使用的资源称为行，这些一次只允许一个进程使用的资源称为临界资临界资源源(critical resource)(critical resource)。打印机、内存变量、指针、数组等都是临界资源。打印机、内存变量、指针、数组等都是临界资源。生活中的例子如：电话机等。生活中的例子如：电话机等。临界资源需要采用互斥方式，实现对资源的共享。临界资源需要采用互斥方式，实现对资源的共享。 2011201120114.4.4.9 9 9/21/21/21操作系统操作系统操作系统2 2、临界区、临界区 每个进程中访问临界每个进程中访问临界资源的那段程序段称为资源的那段程序段称为临界区（临界区（critical critical sectionsection）。）。 2011201120114.4.4.101010/21/21/21操作系统操作系统操作系统访问临界资源的循环进程访问临界资源的循环进程Until false;Entry sectionCritical section;Exit sectionRemainder section;Repeat 进入区进入区：进入临界区之前，检查：进入临界区之前，检查可否进入临界区的一段代码。如果可否进入临界区的一段代码。如果可以进入临界区，通常设置相应可以进入临界区，通常设置相应“正在访问临界区正在访问临界区”标志；标志； 临界区：临界区：进程中访问临界资源的进程中访问临界资源的一段代码；一段代码； 退出区：退出区：用于将用于将 正在访问临界正在访问临界区区 标志清除。标志清除。 剩余区剩余区：代码中的其余部分。：代码中的其余部分。 2011201120114.4.4.111111/21/21/21操作系统操作系统操作系统进入区进入区临界区临界区退出区退出区进入区进入区临界区临界区退出区退出区.阻塞等待阻塞等待资源释放资源释放改变资源改变资源状态状态释放资源释放资源进程进程1进程进程2进入区、退出区各部分的作用进入区、退出区各部分的作用 2011201120114.4.4.121212/21/21/21操作系统操作系统操作系统3 3、同步机制应遵循的准则、同步机制应遵循的准则空闲则入：其他进程均不处于临界区；空闲则入：其他进程均不处于临界区；忙则等待：已有进程处于其临界区；忙则等待：已有进程处于其临界区；有限等待：等待进入临界区的进程不能有限等待：等待进入临界区的进程不能 死等死等 ；让权等待：不能进入临界区的进程，应释放让权等待：不能进入临界区的进程，应释放CPUCPU（如转换到阻塞状态）如转换到阻塞状态） 2011201120114.4.4.131313/21/21/21操作系统操作系统操作系统4 4、进程互斥的软件方法（补充）、进程互斥的软件方法（补充）算法算法1 1：强制轮换法（单标志）：强制轮换法（单标志）n设立一个公用整型变量设立一个公用整型变量 turnturn：描述允许进入临界区的进程标识：描述允许进入临界区的进程标识F在进入区检查是否允许本进程进入在进入区检查是否允许本进程进入:turn:turn为为i i时时, ,进程进程PiPi可进入可进入; ;F在退出区修改在退出区修改turnturn的值：的值：进程进程PiPi退出时退出时, ,改改turnturn为为j j；n缺点：缺点：强制轮流强制轮流进入临界区，没进入临界区，没有考虑进程的实际需要。容易有考虑进程的实际需要。容易造成造成资源利用不充分资源利用不充分：在在PiPi出让临界区之后，出让临界区之后，PjPj使用临界区之前，使用临界区之前，PiPi不可能再不可能再次使用临界区；次使用临界区；Until false;RepeatWhile turn i do no_opCritical section;turn:=j;remainder section;n 有两个进程有两个进程Pi, PjPi, Pj，其中的，其中的PiPi 2011201120114.4.4.141414/21/21/21操作系统操作系统操作系统算法算法2 2：锁变量方法（双标志、先检查）：锁变量方法（双标志、先检查）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先检查，后修改：在进入区检查另一个进程是否在临界区，不在时先检查，后修改：在进入区检查另一个进程是否在临界区，不在时修改本进程在临界区的标志；修改本进程在临界区的标志；F在退出区修改本进程在临界区的标志；在退出区修改本进程在临界区的标志； 2011201120114.4.4.151515/21/21/21操作系统操作系统操作系统算法算法3 3：锁变量方法（双标志、后检查）：锁变量方法（双标志、后检查）n缺点：缺点：PiPi和和PjPj可能都进入不了临界区可能都进入不了临界区。按下面序列执行。按下面序列执行时，会都进不了临界区：时，会都进不了临界区：Pi Pj Pi PjPi Pj Pi Pj。Until false;Flagi:=true； While flagj do no_op Critical section;Flagi:=false;remainder section;Repeatn类似于算法类似于算法2 2，与，与2 2的区别在于先修改后检查。可防止两个进程同的区别在于先修改后检查。可防止两个进程同时进入临界区。时进入临界区。 2011201120114.4.4.161616/21/21/21操作系统操作系统操作系统算法算法4(Petersons Algorithm)4(Petersons Algorithm)：先修改、后检查、后修改者等待先修改、后检查、后修改者等待n结合算法结合算法1 1和算法和算法3 3，是正确的算法，是正确的算法nturn=j;turn=j;描述可进入的进程（同时修改标志时）描述可进入的进程（同时修改标志时）n在进入区先修改后检查，并检查并发修改的先后：在进入区先修改后检查，并检查并发修改的先后：F检查对方检查对方flagflag，如果不在临界区则自己进入，如果不在临界区则自己进入空闲则入空闲则入F否则再检查否则再检查turnturn：保存的是较晚的一次赋值，则较晚的进：保存的是较晚的一次赋值，则较晚的进程等待，较早的进程进入程等待，较早的进程进入先到先入，后到等待先到先入，后到等待Until false;Flagi:=true;turn:=j;While(flagj and turn=j) do no_opCritical section;Flagi:=false;remainder section;Repeat 2011201120114.4.4.171717/21/21/21操作系统操作系统操作系统5 5、进程互斥的硬件方法（补充）、进程互斥的硬件方法（补充）Test-and-SetTest-and-Set指令指令该指令读出标志后设置为该指令读出标志后设置为TRUETRUEboolean TS(boolean boolean TS(boolean * *lock) lock) boolean old; boolean old; old = old = * *lock; lock; * *lock = TRUE;lock = TRUE; return old; return old; locklock表示资源的两种状态：表示资源的两种状态：TRUETRUE表示正被占用，表示正被占用，FALSEFALSE表示空闲表示空闲n完全利用软件方法，有很大局限性（如不适于多进程），实现过完全利用软件方法，有很大局限性（如不适于多进程），实现过于复杂，需要高的编程技巧。于复杂，需要高的编程技巧。n可以利用某些硬件指令可以利用某些硬件指令其读写操作由一条指令完成，因而保其读写操作由一条指令完成，因而保证读操作与写操作不被打断；证读操作与写操作不被打断； 2011201120114.4.4.181818/21/21/21操作系统操作系统操作系统利用利用TSTS实现进程互斥实现进程互斥Until false;While TS(lock) do skipCritical 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; 2011201120114.4.4.191919/21/21/21操作系统操作系统操作系统SwapSwap指令（或指令（或ExchangeExchange指令）指令）交换两个字（字节）的内容：交换两个字（字节）的内容：void SWAP(int void SWAP(int * *a, int a, int * *b) b) int temp; int temp; temp = temp = * *a; a; * *a = a = * *b; b; * *b = temp;b = temp; 2011201120114.4.4.202020/21/21/21操作系统操作系统操作系统利用利用SwapSwap指令实现互斥算法指令实现互斥算法n利用利用SwapSwap实现进程互斥：每个临界资源设置一个公共布尔变量实现进程互斥：每个临界资源设置一个公共布尔变量locklock，初值为，初值为FALSEFALSE。每个进程设置一个私有布尔变量。每个进程设置一个私有布尔变量keykeyWhile(1);Key:=true;Do Swap(&lock,&key);while(key);Critical section;lock=false;remainder section;Dovoid SWAP(int void SWAP(int * *a,int a,int * *b)b) int temp; int temp; temp = temp = * *a; a; * *a = a = * *b; b; * *b = temp;b = temp; 2011201120114.4.4.212121/21/21/21操作系统操作系统操作系统硬件方法的优缺点硬件方法的优缺点n优点优点F适用于任意数目的进程，在单处理器或多处理器上适用于任意数目的进程，在单处理器或多处理器上F简单，容易验证其正确性简单，容易验证其正确性F可以支持进程内存在多个临界区，只需为每个临界可以支持进程内存在多个临界区，只需为每个临界区设立一个布尔变量区设立一个布尔变量n缺点缺点F等待要耗费等待要耗费CPUCPU时间，仍然不能实现时间，仍然不能实现 让权等待让权等待