OS4(同步软硬件方法).ppt

3.3 进程同步 3.3.1 进程同步的基本概念 1.临界资源 2、临界区 访问临界资源的循环进程 3、同步机制应遵循的准则 空闲则入：其他进程均不处于临界区； 忙则等待：已有进程处于其临界区； 有限等待：等待进入临界区的进程不能死等； 让权等待：不能进入临界区的进程，应释放CPU（如转换到阻塞状态） 4、进程互斥的软件方法（补充） 算法2：锁变量方法（双标志、先检查） 算法3：锁变量方法（双标志、后检查） 算法4(Peterson’s Algorithm)：先修改、后检查、后修改者等待 结合算法1和算法3，是正确的算法 turn=j;描述可进入的进程（同时修改标志时） 在进入区先修改后检查，并检查并发修改的先后： 检查对方flag，如果不在临界区则自己进入——空闲则入 否则再检查turn：保存的是较晚的一次赋值，则较晚的进程等待，较早的进程进入——先到先入，后到等待 5、进程互斥的硬件方法（补充） 利用TS实现进程互斥 Swap指令（或Exchange指令） 利用Swap指令实现互斥算法 利用Swap实现进程互斥：每个临界资源设置一个公共布尔变量lock，初值为FALSE。每个进程设置一个私有布尔变量key 硬件方法的优缺点 Lifang ?2011 */25 操作系统 * 3.3.1 进程同步的基本概念 3.3.2 信号量(semaphore) 3.3.3 经典进程同步问题 3.3.4 进程间通信 正常行车 到站停车 开车 售票 开车门 关车门 司机 售票员 合作 合作 进程间的合作关系 打印进程1 打印进程2 打印 打印 获得打印数据 获得打印数据 竞争 进程间竞争资源 计算进程 打印进程 计算结果送到Buffer 从Buffer中取数 Buffer 竞争 竞争 完成数据计算 打印 通知打印进程打印 通知计算进程 送下一个数 合作与竞争 合作 合作 司机与售票员 多个打印者 计算者与打印者 进程间存在两种关系 协调好这些关系的过程——进程的同步 操作顺序冲突 共享外设、内存（变量）等资源 竞争资源关系： 进程同步的主要任务：保证诸进程能互斥地访问临界资源 相互合作关系： 进程同步的主要任务：保证相互合作的诸进程在执行次序上的协调——同步。 计算进程 打印进程 计算结果送到Buffer 从Buffer中取数 Buffer 互斥 互斥 向打印进程发信号 通知其从Buffer里取数 Buffer空？ 否 是 完成数据计算 打印 向计算进程发信号 通知其向Buffer送数 Buffer空？ 否 是 协调 计算进程与打印进程的同步 对于计算机中的有些软硬件资源，当多个进程对其进行访问时（关键是进行写入或修改），必须互斥地进行，这些一次只允许一个进程使用的资源称为临界资源(critical resource)。 打印机、内存变量、指针、数组等都是临界资源。 生活中的例子如：电话机等。 临界资源需要采用互斥方式，实现对资源的共享。 每个进程中访问临界资源的那段程序段称为临界区（critical section）。 Until false; Entry section Critical section; Exit section Remainder section; Repeat 进入区：进入临界区之前，检查可否进入临界区的一段代码。如果可以进入临界区，通常设置相应“正在访问临界区”标志； 临界区：进程中访问临界资源的一段代码； 退出区：用于将正在访问临界区标志清除。 剩余区：代码中的其余部分。 进入区 临界区 退出区 进入区 临界区 退出区 ... ... ... ... ... ... ... ... 阻塞等待 资源释放 改变资源 状态 释放资源 进程1 进程2 进入区、退出区各部分的作用 算法1：强制轮换法（单标志） 设立一个公用整型变量 turn：描述允许进入临界区的进程标识 在进入区检查是否允许本进程进入:turn为i时,进程Pi可进入; 在退出区修改turn的值：进程Pi退出时,改turn为j； 缺点： 强制轮流进入临界区，没有考虑进程的实际需要。容易造成资源利用不充分： 在Pi出让临界区之后，Pj使用临界区之前，Pi不可能再次使用临界区； Until false; Repeat While turn?i do no_op Critical section; turn:=j; remainder section; 有两个进程Pi, Pj，其中的Pi描述如下图 优点:不用交替进入,可连续使用 缺点：Pi和Pj可能同时进入临界区。按下面序列执行时，会同时进入：Pia Pja Pib Pjb。 Until false; While flag[j] do no_op a Flag[