进程的并发控制互斥与同步PPT课件.ppt

第三章进程的并发控制 互斥与同步 与时间有关的错误问题进程协调的概念对临界区管理的准则简单的同步机制 标志法 信号量机制 实现进程互斥与同步的控制 1 3 1程序的两种执行方式 程序的顺序执行程序在运行的时独占系统资源 且系统按照程序步骤顺序执行地执行 在该程序执行完之前 其他程序只能等待 程序的并发执行多道程序设计的系统中 若干个作业可以同时执行 这些进程轮流地占用CPU 即一个进程的工作没有全部完成之前 另一个进程就可开始工作 我们说这些执行的进程具有并发性 2 3 1与时间有关的错误问题 1 问题描述 设有一个游乐场设置了一个自动计算机系统 用一个变量count指示在场的人数 当有人进入 则PIN进程完成count 当有人退出 则POUT进程完成count 进程PINProcessPIN intR1 R1 count R1 R1 1 count R1 进程POUTProcessPOUT intR2 R2 count R2 R2 1 count R2 3 3 1与时间有关的错误问题 1 两个进程的顺序执行 不产生错误 假设某一时刻count nintR1 R1 count R1 R1 1 count R1 intR2 R2 count R2 R2 1 count R2 正确结果count n不变 假设某一时刻count nintR2 R2 count R2 R2 1 count R2 intR1 R1 count R1 R1 1 count R1 正确结果count n不变 4 3 1与时间有关的错误问题 1 并发执行一种错误的可能结果 假设某一时刻count nR1 count count nR1 R1 1 PIN进程被挂起R2 count R2 R2 1 count n 1count R2 POUT进程结束 PIN唤醒count R1 错误的结果值count n 1 实际该为n 5 3 1与时间有关的错误问题 1 并发执行另一种错误的可能结果 假设某一时刻count nR1 count count nR1 R1 1 PIN进程被挂起 R1 n 1R2 count count nR2 R2 1 POUT进程被挂起 PIN唤醒R2 n 1count R1 PIN进程结束 POUT唤醒count n 1count R2 POUT进程结束 count n 1错误的结果值count n 1 实际该为n 6 3 1与时间有关的错误问题 1 分析产生错误的可能原因一个进程运行时由于自身或外界的原因可能被中断 且断点是不固定的 进程执行的相对速度不能由自己来控制两个并发进程使用共享的变量count两个进程在不同时间里访问count变量 可能得到相同的count变量值 7 3 1与时间有关的错误问题 2 问题描述 设一个飞机航班售票系统有n个售票处 每个售票处通过终端访问系统公共数据区 假定公共数据区中的一些单元Aj j 1 2 分别存放某年某月某日某次航班的剩余票数 设P1 P2 Pn表示各个售票处的处理进程 R1 R2 Rn表示各进程执行时所用的工作单元 当各售票处有旅客买票时 进程工作如下 8 3 1与时间有关的错误问题 2 可能产生的错误结果可能有若干个旅客在几乎相同的时间里到不同的售票处要求购买同一天同一航班的机票 于是若干进程都要访问同一个Aj 则结果可能出现同一张票卖给几个不同的旅客 ProcessPi i 1 2 n 根据用户需求找到Aj Ri Aj if Ri 1 Ri Ri 1 Aj Ri 提示已卖出一张票信息 else输出 票已售完 9 3 1与时间有关的错误问题 2 假设某一个时刻三个客户在不同网点但几乎同时到达购票访问的情况 10 3 2进程的协调概念 在os支持下 多个进程既独立又并发执行 然而进程之间可能合作完成一项任务 可能共享一种系统资源 可能相互支持和依赖 甚至制约对方 为了协调进程间的关系 os必须进行进程间的协调 11 3 2进程的制约关系 直接相互制约关系源于进程的合作 同步关系如 A B两个进程通过缓冲区合作完成一项任务 A负责存数据到缓冲区 B负责从缓冲区中取数 间接相互制约关系源于资源共享 互斥关系如 A B两个进程共享打印机 若分配给A 则当B需要打印机时被阻塞而等待 12 3 2进程的互斥与同步 进程间具有一种互斥关系也就是说对于某个系统资源 如果一个进程正在使用 其他进程就必须等待其用完 不能同时使用 进程间具有一种同步关系即多个相关的进程在执行次序上需要协调 如当两个进程或多个进程合作完成一个任务 在并发执行中 一个进程需等待其合作伙伴发送消息或建立条件再向前执行 这种制约关系通常称为进程的同步 13 几个专业术语 临界资源一次只允许一个进程使用的资源广义上 包括物理实体资源 如 打印机软件资源 如 变量 文件等临界区一个进程访问这种临界资源的那段程序代码 称为临界区 14 几个专业术语 剩余区除临界区外的其余代码说明 进程互斥的再定义 就是两个进程不能同时进入访问同一临界资源的临界区操作系统中实现互斥和同步的机制统称为同步机制 15 3 3临界区的管理准则 P79 操作系统的进程同步机制必须遵循如下准则空闲让进忙则等待有限等待让权等待 16 3 3临界区的管理准则 空闲让进当无进程处于临界区时 允许一个进程进入忙则等待当有进程在临界区 其他欲进入临界区的进程须等待 否则无需等待 一次至多一个进程能够进入临界区 17 3 3临界区的管理准则 有限等待对要求进入临界区的进程 应在有限时间内让其进入 避免 死等 不能让一个进程无限在临界区执行 任何进入临界区的进程必须在有限时间内退出 18 临界区的管理准则 让权等待临界区让出 必须立即释放CPU 让等待进程进入 避免 忙等 不能让一个进程无限等待进入 即有进程退出临界区时 应让等待进程进入临界区执行 19 3 4简单的同步机制 标志位机制 进程互斥问题的软件解决方法轮流标志法 单标志法 双标志法三标志法 20 3 4简单的同步机制 单标志位法 算法的基本思想设置一个标志变量turn 两个进程P0 P1要进入临界区先要访问该标志 根据标志值决定自己是否进入临界区 例如当turn 0 表示允许P0进程进入 当P0退出临界区后 置turn 1 P1才可进入临界区 反之当turn 1 表示允许P1进程进入 退出时置turn 0 则P0才可进入 21 3 4简单的同步机制 单标志位法 ProcessP0 do while turn 0 临界区turn 1 剩余区 while 1 ProcessP1 do while turn 1 临界区turn 0 剩余区 while 1 初始值turn 0 或者turn 1 22 3 4简单的同步机制 单标志位法 该算法的致命缺点要求进入临界区执行的两个进程必须严格的交替运行 当进程A大于进程B时 将阻塞进程B再次进入临界区 因为交替原则 B必须等待A执行结束 即产生了长进程阻塞短进程的问题 不满足临界区管理的第一个准则 因为存在一个进程当它在剩余区时 也不允许另一个进程进入临界区 23 3 4简单的同步机制 双标志位法 算法的基本思想先修改后检查算法为每个进程都设置一个标志位 引入数组flag 2 初始化为false 表示临界区中无进程 欲进入者可以进入 进程Pi欲进入时将自身标志flag i 置为true 阻止另一个进程进入 接着判定对方的标志是否为false 若是才可以进入临界区 否则必须等待 任一个进程退出临界区后都将自身标志置为false 表示退出临界区 允许对方进程进入临界区 24 3 4简单的同步机制 双标志位法 1 算法的主要伪代码 ProcessP0 do flag 0 true while flag 1 临界区flag 0 false 剩余区 while 1 ProcessP1 do flag 1 true while flag 0 临界区flag 1 false 剩余区 while 1 初始值flag i false 25 3 4简单的同步机制 双标志位法 1 算法的特点可以解决两个进程严格交替的问题但当两个进程几乎同时到达时 结果两个进程都不能进入临界区执行产生死锁问题可能导致对方进程的 饥饿 问题 将永远被阻塞不满足管理准则中的 空闲让进 26 3 4简单的同步机制 双标志位法 2 算法的基本思想先检查算法交换修改与检查语句的顺序 先做while检查 再做true值的设置修改 27 3 4简单的同步机制 双标志位法 2 算法的主要伪代码 ProcessP0 do while flag 1 flag 0 true 临界区flag 0 false 剩余区 while 1 ProcessP1 do while flag 0 flag 1 true 临界区flag 1 false 剩余区 while 1 28 3 4简单的同步机制 双标志位法 2 算法的致命缺点比前两种方法更差 不能解决互斥问题导致所有进程都可以进入临界区不满足管理准则中的 忙则等待 29 3 4简单的同步机制 三标志位法 算法的基本思想先修改 后检查 后修改者等待算法为了解决两个进程的同时到达问题 将前两者算法结合 在双标志法的基础上再引入turn变量 当两个进程几乎同时到达时 进程根据turn值决定哪一个进程进入临界区 即保证任一个时刻 turn值为0或者为1 使得只有一个进程满足条件而进入临界区 30 3 4简单的同步机制 三标志位法 算法的主要伪代码 ProcessP0 do flag 0 true turn 1 while flag 1 ProcessP1 do flag 1 true turn 0 while flag 0 31 3 4简单的同步机制 三标志位法 两个进程几乎同时到达的情况 flag 0 true flag 1 true turn 1 while flag 1 P0退出 P1可被解除剩余区 P0的剩余区 32 3 4简单的同步机制 三标志位法 两个进程几乎同时到达的情况 flag 0 true flag 1 true turn 1 turn 0 后修改者P1while flag 0 P0退出 P1可被解除剩余区 P0的剩余区 33 3 4简单的同步机制 三标志位法 两个进程几乎同时到达的情况 flag 0 true flag 1 true turn 0 turn 1 后修改者P0while flag 1 P1退出 P0可被解除剩余区 P1的剩余区 34 3 4简单的同步机制 三标志位法 算法的特点满足管理准则 空闲让进 忙则等待等解决进程的互斥与并发实现较复杂系统开销大 35 3 4简单的同步机制 四个算法的共同缺点只适合解决两进程的互斥问题不能处理进程的同步问题 36 3 5信号量机制 信号量协调机制可实现2个或2个以上的进程协调 既可用与互斥 也可用用于同步 信号量 semaphore 是由荷兰计算机科学家E W Dijkstra于1965年提出的 它取自交通管理中的信号灯的概念 37 3 5信号量机制 信号量的基本概念信号量是用于控制进程互斥与同步的物理变量信号量S 通常用S表示 是一个整型变量 初始值为非负数每个信号量S对应设置了一个等待队列对信号量的操作只能通过PV操作进行 38 3 5信号量机制 PV操作 P操作和V操作都是不可分割的原子操作 也叫原语P操作可以记为P S wait S 或者down S V操作可以记为V S signal S 或者up S 为减化 我们用P S 和V S 表示 教材采用wait 和signal 表示 39 3 5信号量机制 PV操作 Dijkstra把互斥和同步的关键含义抽象成信号量 semaphore 概念 并引入在信号量上的P V操作作为同步原语 P和V分别是荷兰文的 等待 和 发信号 两词的首字母 PV操作对于每一个进程来说 都只能进行一次 而且必须成对使用 40 3 5信号量机制 P操作 P S 操作的定义S值减一若S 0 当前进程继续运行 说明等待队列无进程 当前进程可继续不阻塞 P操作的伪代码P ints s if s 0 wait 当前被挂起return 当前继续 41 3 5信号量机制 V操作 V S 操作的定义S值加一 若S0 当前进程继续执行 说明等待队列无进程 无需执行唤醒操作 V操作的伪代码V ints s if s 0 wakeup 移出一个进程 插入就绪队列 相当唤醒return 当前继续 42 3 5信号量机制 解决互斥问题 如果有若干个进程都调用P操作 提出申请 则只有第一个调用P操作的进程不成为等待状态而可以继续执行P操作第一次调用后 S的值成为 0 以后的进程调用P操作时 S值总小于0 S 0 因为S 进程被阻塞置为等待状态而不能继续执行直到有一个进程退出临界区 调用一次V操作后 才释放一个等待者 设S 1 P S 临界区V S 43 3 5信号量机制 解决互斥问题 能实现对临界区管理的要求当无进程在临界区时 若有进程要进入临界区则允许一个进程立即进入它的临界区 当有一个进程在临界区执行时 其他试图进入临界区的进程必须等待 当有一个进程离开临界区时 若有等待进入临界区的进程 则允许其中一个进程进入它的临界区 系统中的共享资源均有一个信号量与之对应 OS按其状态对进程和资源进行管理 44 3 5信号量机制 解决互斥问题 实现互斥的方法首先判断临界资源其次判断相关的代码即临界区定义信号量的个数设置信号量初始值在进入临界区之前调用P操作 相当申请进入临界区 在退出临界区之后调用V操作 相当唤醒等待进程进入临界区 45 3 5信号量机制 游乐场问题 游乐场关于计数的两个进程 进程P2Processp2 intR2 R2 count R2 R2 1 count R2 进程P1Processp1 intR1 R1 count R1 R1 1 count R1 46 3 5信号量机制 游乐场问题 分析上述进程 找到临界资源即count这个全局共享变量分析有关对count变量进行操作的代码即临界区 包括三条语句一个共享资源count变量对应一个信号量 信号量S表示由于每次只能让一个进程使用 且共享的资源个数为1 所以信号量S的初始值为1 47 3 5信号量机制 游乐场问题 互斥信号量S初值为1说明了任意时刻只允许一个进程进入临界区 其他想进入的进程只能等待 Processp2 intR2 P S R2 count R2 R2 1 count R2 V S Processp1 intR1 P S R1 count R1 R1 1 count R1 V S SemaphoreS S 1 48 3 5信号量机制 游乐场问题 这是两个进程互斥的问题 对信号量S的分析S 1 表示当前共享资源只有一个可供使用 一次只能允许一个进程使用 且任何时刻只能一个进程进入临界区 其他欲进入的进程必须等待 互斥概念 S 0 表示有一个进程在临界区 无可用资源 无等待进程 49 3 5信号量机制 游乐场问题 这是两个进程互斥的问题S 1 表示有一个等待的进程S的取值范围 1 0 1 S 的含义 表示有 S 个进程在等待 50 3 5信号量机制 订票系统问题 飞机订票系统关于联网订票的进程 Processpi intR 根据用户需求找到Aj if Aj 1 R Aj R R 1 Aj R 提示已卖出一张票信息 else输出票已售完 51 3 5信号量机制 订票系统问题 解决互斥方法一 Processpi intR 根据用户需求找到Aj if Aj 1 P S R Aj R R 1 Aj R V S 提示已卖出一张票信息 else输出票已售完 SemaphoreS 1 思考 互斥问题是否得到解决 如果没有 原因在哪 52 3 5信号量机制 订票系统问题 法一的问题分析表面上看实现互斥的管理 实际上仍然存在读取相同Aj值的情况分析判定共享资源应该是 Aj变量分析判定临界区 包括所有对Aj变量操作的代码区注意 若查询结果是无票 虽不影响临界区的使用 不产生错误 但存在潜在的错误 53 3 5信号量机制 订票系统问题 互斥解法二 SemaphoreS 1 Processpi 修改进程的表示 intR 根据用户需求找到Aj R Aj if R 1 R R 1 Aj R 提示已卖出一张票信息 else输出票已售完 Processpi I 1 2 n intR 根据用户需求找到Aj P S R Aj if R 1 R R 1 Aj R V S 提示已卖出一张票信息 else输出票已售完 54 3 5信号量机制 订票系统问题 法二的问题分析PV操作没有成对出现对第一个查询结果无票的进程而言 能顺利退出临界区 但后续进程均被挂起 不能得到响应导致系统内部存在 饥饿 进程 55 3 5信号量机制 订票系统问题 正确的解法 SemaphoreS 1 Processpi intR P S 根据用户需求找到Aj R Aj if R 1 R R 1 Aj R V S 提示已卖出一张票信息 else V S 输出票已售完 说明 准确判断临界区是非常重要的 但要注意在退出临界区是否执行了V操作 要注意PV操作的成对性 56 3 5信号量机制 订票系统问题 对信号量S的分析S 1 表示当前共享资源只有一个可供使用 且任何时刻只能一个进程进入临界区 其他欲进入的进程必须等待 互斥概念 S 0 表示有一个进程在临界区 无可用资源S 1 2 表示有1个 2个 等待的进程S的取值范围 n 1 1 S 的含义 表示有 S 个进程在等待 这是n个进程的互斥问题 57 3 5信号量机制 同步问题 假设缓冲区一次只能放一个物品 缓冲区 进程B 消费者 进程A 生产者 存 取 读 加工 问题 如果两个进程不相互制约的话会造成什么错误 58 3 5信号量机制 同步问题 问题分析在B还没来得及从缓冲区中取走当前数据之前 A又存入一个新记录 则引起数据被覆盖的错误在A还没来得及生产新的数据之前 B又从缓冲区中取走相同的数据 导致重复取记录的错误 59 3 5信号量机制 同步问题 错误的原因AB两个进程的执行速度不同步造成 A比B快 或B比A快 所以AB进程需同步 需要协调说明 进程的同步关系源于进程的合作 协作 60 3 5信号量机制 解决同步问题 问题提出要实现进程同步就必须提供一种机制 该机制能测试进程所需的消息是否到达 也能把它所需的消息发送出去实现思想用一个信号量与一个消息联系起来 当信号量的值为 0 时 表示期望的消息还没有产生 当信号量的值为非 0 时表示期望的消息已经存在 61 实现方法通过调用P操作可以测试自己所期望的消息是否到达 相当申请进入临界区 而任何进程要向其它进程发送消息时 相当唤醒下一个进程进入临界区 可以调用V操作 3 5信号量机制 解决同步问题 62 3 5信号量机制 解决同步问题 实现原理P操作的理解用信号量S表示一种消息 如果消息还没有产生 则S 0 调用P S 操作后 调用者将成为等待状态 申请进入临界区失败 如果消息已经存在 则S 0 调用P S 操作后 调用者不会成为等待状态 即申请进入临界区成功 63 3 5信号量机制 解决同步问题 实现原理V操作的理解若调用V S 操作前S 0 表示消息还没有产生也没有等待消息的进程 这时调用V S 操作后 S 0 调用V S 后 意味着消息产生 即相当通知或者唤醒操作 若调用V操作前S 0 表示消息还没有产生且有进程在等待该消息 这时调用V S 操作后将释放一个在等待消息的进程 即调用V S 操作的进程把消息发给在等待消息的进程且允许它继续进行 即相当通知或者唤醒操作 64 3 5经典同步问题 生产者 消费者问题 生产者与消费者问题描述 现假定有一个生产者和一个消费者 他们共用一个缓冲器 生产者不断地生产物品 每生产一件物品就要存入缓冲器 但缓冲器中每次只能存入一件物品 只有当消费者把物品取走后 生产者才能把第二件物品存入缓冲器 同样地 消费者不断地取出物品去消费 当缓冲器中有物品时他就可以去取 每取走一件物品后必须等生产者放入一件物品才可再取 65 3 5经典同步问题 生产者 消费者问题 生产者进程和消费者进程 未采用同步机制前的主要代码 Processproducer L1 produceaproduct Buffer product gotoL1 Processconsumer L1 takeaproductfromBuffer consume gotoL1 66 3 5经典同步问题 生产者 消费者问题 问题分析消息的个数 2个需要的信号量两个 定义两个变量SP SG分别表示生产者和消费者的信号量 私有信号量 两个进程生产和消费各自独立 并发执行两个进程只在访问公共的缓冲器把物品存入或取出时才要互通消息 67 3 5经典同步问题 生产者 消费者问题 信号量初值的分析初始状态 缓冲器为空 允许生产者生产的物品存入缓冲器 相当于通知消费者进程取物品的消息已经到了 代表此消息的信号量SP初值应该为 1 初始状态 缓冲区为空 不能取数消费 也就不能通知再生产 所以对应信号量SG的初值应该为 0 68 3 5经典同步问题 生产者 消费者问题 信号量的定义 SemaphoreSP SG SP 1 SG 0 SP 表示是否可以把物品存入缓冲区 由于缓冲区每次只能放一个物品 所以初值为1 SG 表示缓冲区是否存在有物品 显然初值为0 表示开始还没有物品在缓冲区 69 3 5经典同步问题 生产者 消费者问题 实现的基本方法生产者进入缓冲区前调用P操作判断消息是否到达 或者说申请进入的消息是否允许通过 退出缓冲区时 调用V操作发送消息通知消费者 相当唤醒消费者消费者在进入缓冲区前 首先调用P操作判断是否可以取数 即通知取数的消息是否到达 当取数后退出缓冲区 调用V操作 发送消息 通知生产者 70 3 5经典同步问题 生产者 消费者问题 将PV操作加入到原来的伪代码中 结果如下 SemaphoreSP SG SP 1 SG 0 intBuffer Processproducer L1 produceaproduct P SP Buffer product V SG gotoL1 Processconsumer L1 P SG takeaproductfromBuffer V SP consume gotoL1 71 3 5经典同步问题 生产者 消费者问题 分析下列几种情况 看PV操作是否能管理 先生产再消费 然后再生产再消费的同步过程 可以 先生产 然后想再生产 是否可行 不行 如果再次生产失败则转为消费 消费后再生产 但如果消费后企图再消费是否可行 不行 一开始就要消费 是否可行 不行 开始没有产品 不能消费 结果必然转为生产 72 3 5经典同步问题 生产者 消费者问题 分析SP和SG的取值范围缓冲器任何时候只允许一个进程使用 两个进程 当生产者 消费者在缓冲器内 消费者 生产者只能等待 所以等待的进程个数最多一个 取值范围 1 0 1 73 3 5经典同步问题 生产者 消费者共享容量n的缓冲区 问题变为 一个生产者和一个消费者共享容量为n的缓冲区的同步问题 生产k 取数t 74 3 5经典同步问题 生产者 消费者共享容量n的缓冲区 变量k和t的理解由于缓冲区的容量为n 则必须考虑 生产者生产的物品存入缓冲区的哪个位置 以及消费者取出的物品来自缓冲区的哪个位置 因此相应需要增加k和t两个变量表示生产者往缓冲区存物品和消费者从缓冲区中取物品的相对位置 它们的初值为 0 即定义intk 0 t 0 75 3 5经典同步问题 生产者 消费者共享容量n的缓冲区 生产者和消费者的进程表示如下 还没有实现同步机制前 Processproducer L1 produceaproduct B k product k k 1 n gotoL1 Processconsumer L1 takeaproductfromB t t t 1 n gotoL1 76 3 5经典同步问题 生产者 消费者共享容量n的缓冲区 信号量的定义需要传送的消息个数 2个 不变 定义2个信号量 分别用SP SG表示信号量的初始化SP 初值为 n 表示开始有n个空闲区可以放置物品SG 初值为 0 表示开始没有物品在缓冲区中 77 3 5经典同步问题 生产者 消费者共享容量n的缓冲区 问题提出 在PV操作之前必须准确判断临界区 这里的临界区在哪 Processproducer L1 produceaproduct B k product k k 1 n gotoL1 Processconsumer L1 takeaproductfromB t t t 1 n gotoL1 78 3 5经典同步问题 生产者 消费者共享容量n的缓冲区 intB n k 0 t 0 SemaphoreSP n SG 0 Processproducer L1 produceaproduct P SP B k product k k 1 n V SG gotoL1 Processconsumer L2 P SG takeaproductfromB t t t 1 n V SP gotoL2 79 3 5经典同步问题 补充例子 例2 假定有三个进程R W1 W2共享一个缓冲器B 而B中每次只能存放一个数 当缓冲器中无数时 进程R可将从输入设备上读入的数存放到缓冲器B中 若存放到缓冲器中的是奇数 则允许进程W1将其取出打印 若存放到缓冲器中的是偶数 则允许进程W2将其取出打印 同时规定 进程R必须等缓冲器中的数取出打印后才能再存放一个数 进程W1或W2对每次存入缓冲器中的数只能打印一次 W1和W2都不能从空的缓冲器中取数 写出这三个并发进程能正确工作的程序 80 3 5经典同步问题 补充例子 进程R的伪代码描述 ProcessR intx L1 takeanumberfromdevice 读数x number B x 读数后存入缓冲区if B 奇数 通知w1进程else通知w2进程 gotoL1 81 3 5经典同步问题 补充例子 进程w1 w2的伪代码描述 ProcessW1 inty L2 y B 取数printthenumbery gotoL2 ProcessW2 intz L3 z B printthenumberz gotoL3 82 3 5经典同步问题 补充例子 分析问题哪个进程看成是生产者 哪个是消费者 把R看成是生产者 把进程W1和W2看成消费者 生产者 R进程 生产不同的产品 奇数或偶数 存入缓冲器B 供不同的消费者 W1和W2进程 取用 83 3 5经典同步问题 补充例子 需要发送的消息是什么以及消息个数 当进程R读入的是奇数 则要把有奇数的消息发送给进程W1 当进程R读入的是偶数 则要把有偶数的消息发送给W2 在进程W1和W2从缓冲器中取出数后 应把缓冲器中又可以存一个数的消息告诉给进程R 84 3 5经典同步问题 补充例子 分析信号量个数及其分别代表的含义通过上述分析得知 需要发送三个消息 所以需要定义三个信号量 分别用S SO SE表示如下 S 表示是否可以把数存入缓冲器 由于缓冲器中每次只能存放一个数 初始缓冲区为空 所以它的初值为 1 SO 表示缓冲器中是否有奇数 初值为 0 表示开始无奇数SE 表示缓冲器中是否有偶数 初值为 0 表示开始无偶数 85 3 5经典同步问题 补充例子 根据上面的分析 得出信号量的定义和变量定义如下 intB SemaphoreS SO SE S 1 SO 0 SE 0 ProcessR intx L1 takeanumberfromdevice x number P S B x if B 奇数 V SO elseV SE gotoL1 86 3 5经典同步问题 补充例子 ProcessW1 inty L2 P SO y B V S printthenumbery gotoL2 ProcessW2 intz L3 P SE z B V S printthenumberz gotoL3 87 3 5经典同步问题 总结 总结进程的互斥实际上是进程同步的一种特殊情况 若干进程互斥使用资源时 一个等待使用资源的进程在等待占用资源的进程发出 归还资源 的消息后 它就可去使用资源 因此互斥使用资源的进程实际上也存在一种一个进程依赖另一个进程发出消息的制约关系 把用来解决进程互斥与同步的机制 如PV操作 称为同步机制 88 3 5经典同步问题 总结 进程互斥与进程同步是有区别的进程的互斥是进程间竞争共享资源的使用权 这种竞争没有固定的必然联系 哪个进程竞争到使用权则共享资源就归哪个进程使用 直到不需要使用时再归还使用权任何进程可竞争使用空闲的共享资源 即使该进程刚刚使用过该共享资源 若此时无其它进程要使用这个共享资源 那么该进程仍可再次使用该共享资源 89 3 5经典同步问题 总结 进程互斥与进程同步是有区别的而进程的同步就不同了 涉及共享资源的并发之间有一种必然的依赖关系 当进程必须同步时 即使没有进程在使用共享资源 还没有得到同步消息的进程也不能去使用这个资源 90 3 5进程的同步与互斥混合 生产者与消费者 问题叙述讨论m个生产者和r个消费者怎样共享容量为n的缓冲器 假定每个生产者都要把各自生产的物品存入缓冲器 而每个消费者也都要从缓冲器中取出物品去消费 得出结论在这个问题中 不仅生产者与消费者之间存在同步 而且m个生产者之间 r个消费者之间还必须互斥的访问缓冲器 91 3 5进程的同步与互斥混合 生产者与消费者 问题提出我们发现生产者和消费者之间应该同步这是显而易见的 只有互通消息才能知道是否可以存放物品或者是否可以从缓冲器中取出物品 为什么生产者和消费者之间需要互斥访问缓冲器呢 92 3 5进程的同步与互斥混合 生产者与消费者 intB n k 0 t 0 SemaphoreSP n SG 0 Processproduceri i 1 2 n L1 produceaproduct P SP B k product k k 1 n V SG gotoL1 Processproducerj j 1 2 n L2 P SG takeaproductfromB t t t 1 n V SP gotoL2 分析 如果不进行互斥 结果会产生什么样的错误 93 3 5进程的同步与互斥混合 生产者与消费者 分析理由 生产者如果m个生产者各自生产了物品都要存入缓冲器中 当第一个生产者按指针k指示的位置放入了一件物品 但在改变指针之前可能被打断执行 于是当第二个生产者要存放物品时将仍按原先的指针值所指的位置存放物品 这样两件物品被重复存放在同一位置上由于系统进程生产的物品往往是数据 当重复的在一个位置存放数据 必定是后者覆盖了前者 造成数据的丢失 所以存放物品时必须互斥 94 3 5进程的同步与互斥混合 生产者与消费者 分析理由 消费者同理 r个消费者都要取物品时 也可能出现从指针t相同的位置取物品 造成一件物品被重复多次取出 这也是错的 因此取物品时也必须互斥 95 3 5进程的同步与互斥混合 生产者与消费者 同步信号量分析m个生产者和r个消费者之间进行同步操作需要互通的消息还是两个 即缓冲器中是否可以存放物品和缓冲器中是否已经有物品 仍用SP和SG表示 SP的初值为 n n表示缓冲区的空闲个数 SG的初值仍为 0 96 3 5进程的同步与互斥混合 生产者与消费者 互斥信号量分析共享变量k t是临界资源对共享变量k与t的操作必须互斥 所以定义两个用于互斥的信号量S1和S2信号量S1用于m个生产者之间互斥的往缓冲器中存放物品信号量S2用于r个消费者之间互斥的从缓冲器中取物品S1 S2初值都为 1 表示开始无进程进入临界区 97 3 5进程的同步与互斥混合 生产者与消费者 intB n k 0 t 0 SemaphoreSP n SG 0 S1 1 S2 1 Processproduceri i 1 2 n L1 produceaproduct P SP P S1 B k product k k 1 n V S1 V SG gotoL1 Processproducerj j 1 2 n L2 P SG P S2 takeaproductfromB t t t 1 n V S2 V SP consume gotoL2 98 3 5进程的同步与互斥混合 生产者与消费者 互斥信号量与同步信号量的位置可以交换 Processproduceri i 1 2 n L1 produceaproduct P S1 P SP B k product k k 1 n V SG V S1 gotoL1 Processproducerj j 1 2 n L2 P S2 P SG takeaproductfromB t t t 1 n V SP V S2 consume gotoL2 99 3 5读者与写者问题 问题描述假定有某个共享文件F 系统允许进程对文件F读和写 规定读者与写者互斥 写者与写者互斥 多个读者可以同时读 读者与写者进程的伪代码 ProcessReader readfileF ProcessWriter writefileF 100 3 5读者与写者问题 问题分析共享资源 文件F临界区 读 写文件 ProcessReader readfileF ProcessWriter writefileF 101 3 5读者与写者问题 情况一不考虑多个读者可以同时读 或假设只有一个读者 则问题转为简单的互斥问题实现读者与写者的互斥 读者与读者的互斥 写者与写者的互斥 即全互斥问题信号量的分析因只有一个共享资源F 定义一个互斥信号量即可 用S表示信号量S的初始值为 1 102 3 5读者与写者问题 情况一的解决方法SemaphoreS 1 ProcessReader P S readfileF V S ProcessWriter j 1 2 3 n P S writefileF V S 103 3 5读者