操作系统原理 ch3 进程同步.ppt

1 第三章进程的同步与通信 进程互斥信号量和 操作进程同步经典的进程同步问题进程通信 2 进程互斥 基本概念利用软件方法解决进程互斥问题利用硬件方法解决进程互斥问题用上锁开锁原语实现进程互斥 3 基本概念 与时间有关的错误 一飞机订票系统 两个终端 运行T1 T2进程T1 T2 Read x Read x ifx 1thenifx 1thenx x 1 x x 1 write x write x 4 并发环境下程序间的制约关系 5 同步 对于进程操作的时间顺序所加的某种限制 如操作 应在 之前执行 互斥 同步的特例 多个操作决不能同时执行 如 操作 和操作 不能在同时执行 注意 理解不能同时执行的准确含义 6 临界资源 criticalresource 一次仅允许一个进程访问的资源 如 进程 共享一台打印机 若让它们交替使用则得到的结果肯定不是我们希望的 临界资源可能是硬件 也可能是软件 变量 数据 表格 队列等 并发进程对临界资源的访问必须作某种限制 否则就可能出与时间有关的错误 如 联网售票 7 临界区 criticalsection 临界段 在每个程序中 访问临界资源的那段程序 注意 临界区是对某一临界资源而言的 对于不同临界资源的临界区 它们之间不存在互斥 如有程序段A B是关于变量X的临界区 而C D是关于变量Y的临界区 那么 A B之间需要互斥执行 C D之间也要互斥执行 而A与C B与D之间不用互斥执行 8 解决互斥的准则 为了禁止两个进程同时进入临界区内 可以采用软件办法或系统提供的同步机构来协调它们的关系 但是 不论用什么办法都要遵循下述准则 1 当有若干进程欲进入它的临界区时 应在有限时间内使进程进入临界区 换言之 它们不应相互阻塞而致使彼此都不能进入临界区2 每次至多有一个进程处于临界区 3 进程在临界区内仅逗留有限的时间 9 软件方法解决进程互斥 现在很少用软件方法解决互斥 但通过学习软件解法能使读者了解到 在早期进程互斥问题的解决并不是一件很简单的事 假如有两个进程Pi和Pj 它们共享一个临界资源R 如何用软件方法使进程Pi和Pj能互斥地访问R 下面介绍四个算法 10 算法1 设整型变量turn 用于指示被允许进入临界区的进程的编号 即若turn i 表示进程Pi可进入 turn j表示进程Pj可进入 11 进程Pi RepeatWhileturnidono op Criticalsectionturn j OthercodeUntilfalse 12 算法1的问题 该算法可确保每次只允许一个进程进入临界区 但它强制两个进程轮流进入 如当Pi退出时将turn置为j 以便Pj能进入 但Pj暂不需要进入 而这时Pi又需要进入时 它无法进入 这不能保证准则1 13 算法2 设varflag array 0 1 ofboolean 若flag i true 表示进程Pi正在临界区内 flag i false表示进程Pi不在临界区内 若flag j true 表示进程Pj正在临界区内 flag j false表示进程Pj不在临界区内 14 Pi进程 RepeatWhileflag j dono op flag i true Criticalsectionflag i false OthercodeUntilfalse 15 算法2的问题 该算法可确保准则1 但又出现新问题 当pi和pj都未进入时 它们各自的访问标志都为false 如果pi和pj几乎同时要求进入 它们都发现对方的标志为false 于是都进入了 这不能保证准则2 16 算法3 算法2的问题在于 当进程Pi观察到进程Pj的标志为false后 便将自己的标志由false改为true 而正是在这两步之间 可能发生进程切换 当Pj运行时 它会观察到Pi的标志为false 从而可以将自己的标志设为true 并进入临界区 若在临界区的执行过程中发生了进程切换 Pi可能获得处理机而进入临界区 17 在算法3中 设varFlag array 0 1 ofboolean 若flag i true 表示进程Pi希望进入临界区内 若flag j true 表示进程Pj希望进入临界区 18 Pi进程 Repeatflag i true Whileflag j dono op Criticalsectionflag i false OthercodeUntilfalse 19 算法3的问题 该算法可确保准则2 但又出现新问题 它可能造成谁也不能进入 如 当pi和pj几乎同时都要进入 分别把自己的标志置为true 都立即检查对方的标志 发现对方为true 最终谁也不能进入 这不能保证准则1 20 课本上的解法4 Pi进程 Repeatflag i true Whileflag j dono op beginflag i false flag i true endCriticalsectionflag i false OthercodeUntilfalse 21 算法4 正确算法 组合算法1 3 为每一进程设标志位flag i 当flag i true时 表示进程pi要求进入 或正在临界区中执行 此外再设一个变量turn 用于指示允许进入的进程编号 22 进程为了进入先置flag i true 并置turn为j 表示应轮到pj进入 接着再判断flag j andturn j的条件是否满足 若不满足则可进入 或者说 当flag j false或者turn i时 进程可以进入 前者表示pj未要求进入 后者表示仅允许pi进入 23 算法4 正确算法 Repeatflag i true turn j While flag j andturn j dono op Criticalsectionflag i false OthercodeUntilfalse 24 软件解法的缺点 1 忙等待2 实现过于复杂 需要较高的编程技巧 25 硬件方法解决进程互斥 用软件解决很难 现代计算机大多提供一些硬件指令 利用Test and Set指令实现互斥利用swap指令实现进程互斥 26 Test and Set指令实现互斥 1 Test and Set指令functionTS varlock boolean boolean beginiflock 0thenbeginlock 1 TS true endelseTS falseend 其中 有lock有两种状态 当lock false时 表示该资源空闲 当lock true时 表示该资源正在被使用 27 2 利用TS指令实现进程互斥为每个临界资源设置一个全局布尔变量lock 并赋初值false 表示资源空闲 repeatwhileTS lock doskip criticalsectionlock false OthercodeUntilfalse 28 swap指令实现进程互斥 1 swap指令又称交换指令 X86中称为XCHG指令 Procedureswap vara b boolean Vartemp boolean BeginTemp a A b B temp End 29 2 利用swap实现进程互斥为每一临界资源设置一个全局布尔变量lock 其初值为false 在每个进程中有局部布尔变量key Repeatkey true RepeatSwap lock key Untilkey false Criticalsectionlock false OthercodeUntilfalse 30 用原语实现进程互斥 锁即操作系统中的一标志位 表示资源可用 表示资源已被占用 用户程序不能对锁直接操作 必须通过操作系统提供的上锁和开锁原语来操作 通常锁用w表示 上锁开锁原语分别用lock w unlock w 来表示 31 上锁和开锁原语 上锁原语lock w 可描述为 L if w 1 gotoLelsew 1 开锁原语unlock w 可描述为 w 0 32 用原语实现进程互斥 33 改进的上锁原语 上述上锁原语中存在忙等待 34 改进的开锁原语 35 1965年 由荷兰学者Dijkstra提出 所以P V分别是荷兰语的test proberen 和increment verhogen 一种卓有成效的进程同步机制最初提出的是二元信号量 互斥 推广到一般信号量 多值 同步 P V操作是原语 信号量及P V操作 36 信号量 semaphore 是一个数据结构定义如下 structsemaphore intvalue pointer PCBqueue 信号量说明 semaphores 37 P操作 P s s value s value 1 if s value 0 该进程状态置为等待状态将该进程的PCB插入相应的等待队列末尾s queue 38 V操作 V s s value s value 1 if s value 0 唤醒相应等待队列s queue中等待的一个进程改变其状态为就绪态并将其插入就绪队列 39 必须置一次且只能置一次初值初值不能为负数只能执行P V操作 信号量的使用 40 用P V操作解决进程间互斥问题 41 信号量及P V操作讨论 对于两个并发进程 互斥信号量的值仅取1 0和 1三个值若 1表示没有进程进入临界区若 0表示有一个进程进入临界区若 1表示一个进程进入临界区 另一个进程等待进入 42 思考 对于N个并发进程 信号量的取值范围是什么 有什么含义 43 1 信号量的物理含义 S 0表示有S个资源可用S 0表示无资源可用S 0则 S 表示S等待队列中的进程个数P S 表示申请一个资源V S 表示释放一个资源 信号量的初值应该大于等于0 信号量及P V操作讨论 续1 44 2 P V操作必须成对出现 有一个P操作就一定有一个V操作当为互斥操作时 它们同处于同一进程当为同步操作时 则不在同一进程中出现如果P S1 和P S2 两个操作在一起 那么P操作的顺序至关重要 一个同步P操作与一个互斥P操作在一起时同步P操作在互斥P操作前而两个V操作无关紧要 信号量及P V操作讨论 续2 45 3 P V操作的优缺点优点 简单 而且表达能力强 用P V操作可解决任何同步互斥问题 缺点 不够安全 P V操作使用不当会出现死锁 遇到复杂同步互斥问题时实现复杂 信号量及P V操作讨论 续3 46 信号量集 AND型信号量集 AND型信号量集是指同时需要多种资源且每种占用一个时的信号量操作AND型信号量集的基本思想 在一个原语中申请整段代码需要的多个临界资源 要么全部分配给它 要么一个都不分配AND型信号量集P原语为SwaitAND型信号量集V原语为Ssignal 47 Swait S1 S2 Sn P原语 if S1 1 Swait原语 48 Ssignal S1 S2 Sn for i 1 i n i Si 释放占用的资源 for 在Si queue中等待的每一个进程P 从等待队列Si queue中取出进程P if 判断进程P是否通过Swait中的测试 重新判断 进程P进入就绪队列 break else进程P进入某等待队列 Ssignal原语 49 一般 信号量集 一般信号量集是指同时需要多种资源 每种占用的数目不同 且可分配的资源还存在一个临界值时的信号量处理 一次需要N个某类临界资源时 就要进行N次V操作 低效又可能死锁 一般信号量集的基本思路就是在AND型信号量集的基础上进行扩充 在一次原语操作中完成所有的资源申请 50 进程对信号量Si的测试值为ti 表示信号量的判断条件 要求Si ti 即当资源数量低于ti时 便不予分配 占用值为di 表示资源的申请量 即Si Si di 对应的P V原语格式为 Swait S1 t1 d1 Sn tn dn Ssignal S1 d1 Sn dn 51 一般 信号量集 可以用于各种情况的资源分配和释放 几种特殊情况 Swait S d d 表示每次申请d个资源 当少于d个时 便不分配Swait S 1 1 表示互斥信号量Swait S 1 0 可作为一个可控开关 当S 1时 允许多个进程进入特定区域 当S 0时 禁止任何进程进入该特定区域 一般 信号量集 未必成对使用Swait和Ssignal 如 一起申请 但不一起释放 52 进程同步 同步问题可分为两类 保证一组合作进程按确定的次序执行保证共享缓冲区的合作进程的同步 53 合作进程的执行次序 若干个进程为了完成一个共同任务而并发执行 在这些进程中 有些进程之间有次序的要求 有些进程之间没有次序的要求 为了描述方便 可以用一个图来表示进程集合的执行次序 如图 54 例 如图 试用信号量实现这三个进程的同步 设有两个信号量SB SC 初值均为 Pa Pb Pc P SB P SC V SB V SC 55 思考题1 如图 试用信号量实现这三个进程的同步 56 解 设有两个信号量S1 S2 初值均为 P1 P2 P3 P S1 V S1 V S2 P S2 57 思考题2 如图 试用信号量实现这6个进程的同步 58 解 设有5个信号量S2 S3 S4 S5 S6 初值均为 P1 P2 P3 P S2 P S3 V S2 V S3 V S4 V S6 V S5 P4 P5 P6 P S4 P S5 P S6 P S5 P S6 V S5 V S6 59 思考题3 用P V操作解决司机与售票员的问题 60 解 设有两个信号量S1 S2 初值均为0 61 共享缓冲区的进程的同步 设某计算进程 和打印进程 共用一个单缓冲区 进程负责不断地计算数据并送入缓冲区 中 进程负责不断地从缓冲区 中取出数据去打印 62 分析 通过分析可知 必须遵守以下同步规则 当 进程把计算结果送入缓冲区时 IOP进程才能从缓冲区中取出结果去打印 当IOP进程把缓冲区中的数据取出打印后 进程才能把下一个计算结果送入缓冲区 63 解 为此设有两个信号量Sa 0 Sb 1 Sa表示缓冲区中有无数据 Sb表示缓冲区中有无空位置 两个进程的同步可以描述如下 64 思考题 1 用P V操作解决下图之同步问题提示 分别考虑对缓冲区S和T的同步 再合并考虑 get copy put s t 65 解 设置四个信号量Sin 1 Sout 0 Tin 1 Tout 0 get while 1 P Sin 将数放入S V Sout copy while 1 P Sout P Tin 将数从S取出放入T V Tout V Sin put while 1 P Tout 将数从T取走 V Tin 66 思考题 桌上有一空盘 最多允许存放一只水果 爸爸可向盘中放一个苹果或放一个桔子 儿子专等吃盘中的桔子 女儿专等吃苹果 试用P V操作实现爸爸 儿子 女儿三个并发进程的同步 提示 设置一个信号量表示可否向盘中放水果 一个信号量表示可否取桔子 一个信号量表示可否取苹果 67 解 设置三个信号量S So Sa 初值分别为1 0 0 分别表示可否向盘中放水果 可否取桔子 可否取苹果 68 69 经典的进程同步问题 生产者 消费者问题读者 写者问题哲学家进餐问题 70 生产者 消费者问题 生产者消费者问题是一种同步问题的抽象描述 计算机系统中的每个进程都可以消费 使用 或生产 释放 某类资源 这些资源可以是硬件资源 也可以是软件资源 当某一进程使用某一资源时 可以看作是消费 称该进程为消费者 而当某一进程释放某一资源时 它就相当于生产者 71 问题描述 通过一个有界缓冲区可以把一群生产者p1 p2 pm 和一群消费者Q1 Q2 Qn联系起来 如图只要缓冲区未满 生产者就可以把产品送入缓冲区 只要缓冲区未空 消费者就可以从缓冲区中取走物品 72 图 73 问题分析 为解决生产者消费者问题 应该设两个同步信号量 一个说明空缓冲区的数目 用S1表示 初值为有界缓冲区的大小N 另一个说明已用缓冲区的数目 用S2表示 初值为 由于在此问题中有M个生产者和N个消费者 它们在执行生产活动和消费活动中要对有界缓冲区进行操作 由于有界缓冲区是一个临界资源 必须互斥使用 所以 另外还需要设置一个互斥信号量mutex 其初值为 74 问题的解 Q j 0 while 1 P S2 P mutex 从Buffer j 取产品 j j 1 n V mutex V S1 消费产品 P i 0 while 1 生产产品 P S1 P mutex 往Buffer i 放产品 i i 1 n V mutex V S2 75 采用AND信号量集解决生产者 消费者问题 Q j 0 while 1 Swait s2 mutex 从Buffer j 取产品 j j 1 n Ssignal s1 mutex 消费产品 P i 0 while 1 生产产品 Swait s1 mutex 往Buffer i 放产品 i i 1 n Ssignal s2 mutex 76 思考题 如果生产者消费者问题中的缓冲区是无界的 又该如何解呢 77 解设信号量S1 mutex初值均为0 Q j 0 while 1 P S1 P mutex 从Buffer j 取产品 j j 1 n V mutex 消费产品 P i 0 while 1 生产产品 P mutex 往Buffer i 放产品 i i 1 n V mutex V S1 s1代表缓冲区是否为空 78 思考题 有一个仓库 可以存放A和B两种产品 但要求 1 每次只能存入一种产品 A或B 2 N A产品数量 B产品数量 M 其中 N和M是正整数 试用P V操作描述产品A与B的入库过程 提示 设两个信号量Sa SbSa表示允许A产品比B产品多入库的数量Sb表示允许B产品比A产品多入库的数量 79 解 设两个信号量Sa Sb 初值分别为M 1 N 1Sa表示允许A产品比B产品多入库的数量Sb表示允许B产品比A产品多入库的数量设互斥信号量mutex 初值为1 80 B产品入库进程 j 0 while 1 P Sb P mutex B产品入库V mutex V Sa 消费产品 A产品入库进程 i 0 while 1 生产产品 P Sa P mutex A产品入库V mutex V Sb 81 读者 写者问题 有两组并发进程 读者和写者 共享一组数据区要求 允许多个读者同时执行读操作不允许读者 写者同时操作不允许多个写者同时操作 82 第一类 读者优先 如果读者来 1 无读者 写者 新读者可以读2 有写者等 但有其它读者正在读 则新读者也可以读3 有写者写 新读者等如果写者来 1 无读者 新写者可以写2 有读者 新写者等待3 有其它写者 新写者等待 83 第一类读者写者问题的解法 设有两个信号量w 1 mutex 1另设一个全局变量readcount 0w用于读者和写者 写者和写者之间的互斥readcount表示正在读的读者数目mutex用于对readcount这个临界资源的互斥访问 84 读者 while 1 P mutex readcount if readcount 1 P w V mutex 读P mutex readcount if readcount 0 V w V mutex 写者 while 1 P w 写V w 85 第一类读者写者问题的解法 一般信号量集 写者 while 1 Swait wmutex 1 1 rcount R 0 写 Ssignal wmutex 1 读者 while 1 Swait rcount 1 1 wmutex 1 0 读 Ssignal rcount 1 增加一个限制条件 同时读的 读者 最多R个wmutex表示 允许写 初值是1rcount表示 允许读者数目 初值为R 86 思考题 写优先 修改以上读者写者问题的算法 使之对写者优先 即一旦有写者到达 后续的读者必须必须等待 无论是否有读者在读 提示 增加一个信号量 用于在写者到达后封锁后续的读者 87 解增加一个信号量s 初值为1 读者 while 1 P s P mutex readcount if readcount 1 P w V mutex V s 读P mutex readcount if readcount 0 V w V mutex 写者 while 1 P s P w 写V w V s 88 哲学家就餐问题 有五个哲学家围坐在一圆桌旁 桌中央有一盘通心粉 每人面前有一只空盘子 每两人之间放一只筷子每个哲学家的行为是思考 感到饥饿 然后吃通心粉为了吃通心粉 每个哲学家必须拿到两只筷子 并且每个人只能直接从自己的左边或右边去取筷子 89 设fork 5 为5个信号量 初值为均1Philosopheri while 1 思考 P fork i P fork i 1 5 进食 V fork i V fork i 1 5 解 90 以上解法会出现死锁为防止死锁发生可采取的措施 最多允许4个哲学家同时坐在桌子周围仅当一个哲学家左右两边的筷子都可用时 才允许他拿筷子 给所有哲学家编号 奇数号的哲学家必须首先拿左边的筷子 偶数号的哲学家则反之 分析 91 采用AND信号量集解决哲学家就餐问题 设fork 5 为5个信号量 初值为均1Philosopheri while 1 思考 Swait fork i fork i 1 5 进食 Ssignal fork i fork i 1 5 92 进程通信 概念进程通信类型消息缓冲通信的实现信箱通信的实现 93 概念 所谓进程通信是指进程之间可直接以较高的效率传递较多数据的信息交换方式 P V操作实现的是进程之间的低级通讯 所以P V为低级通讯原语 它只能传递简单的信号 不能传递交换大量信息 如果要在进程间传递大量信息则要用Send Receive原语 高级通讯原语 94 进程通信类型 共享存储器系统消息传递系统管道通信 共享文件方式 95 1 共享存储器系统 基于共享数据结构的通信方式诸进程公用某些数据结构 进程通过它们交换信息 如生产者 消费者问题中的有界缓冲区 96 基于共享存储区的通信方式高级通信 在存储器中划出一块共享存储区 进程在通信前 向系统申请共享存储区中的一个分区 并指定该分区的关键字 若系统已经给其它进程分配了这样的分区 则将该分区的描述符返回给申请者 接着 申请者把获得的共享存储分区连接到本进程上 此后可读写该分区 以上两种方式的同步互斥都要由进程自己负责 97 2 消息传递系统 进程间的数据交换以消息为单位 程序员利用系统的通信原语实现通信 操作系统隐藏了通信的实现细节 简化了通信程序编制的复杂性 因而得到广泛应用 98 消息传递系统可分为 直接通信 发送进程直接把消息发送给接收者 并将它挂在接收进程的消息缓冲队列上 接收进程从消息缓冲队列中取得消息 也称为消息缓冲通信 99 间接通信 发送进程将消息发送到某种中间实体中 信箱 接收进程从中取得消息 也称信箱通信 在网络中称为电子邮件系统 100 思考 两种方式的主要区别 前者需要两进程都存在 后者不需要 101 3 管道通信 所谓管道 是指用于连接一个读进程和一个写进程的文件 称pipe文件 向管道提供输入的进程 称写进程 以字符流的形式将大量数据送入管道 而接受管道输出的进程 读进程 可从管道中接收数据 该方式首创于UNIX 它能传送大量数据 被广泛采用 102 消息缓冲通信的实现 在操作系统空间设置一组缓冲区 当发送进程需要发送消息时 执行send系统调用 产生访管中断 进入操作系统 操作系统为发送进程分配一个空缓冲区 并将所发送的消息从发送进程copy到缓冲区中 然后将该载有消息的缓冲区连接到接收进程的消息链链尾 如此就完成了发送过程 发送进程返回到用户态继续执行 103 在以后某个时刻 当接收进程执行到receive接收原语时 也产生访管中断进入操作系统 由操作系统将载有消息的缓冲区从消息链中取出 并把消息内容copy到接收进程空间 之后收回缓冲区 如此就完成了消息的接收 接收进程返回到用户态继续进行 104 105 typemessageBuffer recordsender 发送者IDsize 消息长度text 消息正文next 消息队列指针end 消息缓冲区结构 106 PCB中有关通信的数据项 typePCB record mq 消息队列首指针mutex 消息队列互斥信号量sm 消息队列资源信号量end 107 send R M begin在OS中分配M size大小的缓冲区t 将M中的内容复制到t 得到进程R的PCB的指针q P q mutex 将t挂到队列q mq队尾 V q mutex V q sm end 用P V操作来实现Send原语 108 Receive N begin得到本进程PCB的指针q P q sm P q mutex 从q mq队首取下一个缓冲区t V q mutex 将t的内容复制到N 并释放tend 用P V操作来实现Receive原语 109 信箱通信的实现 信箱使用规则若发送信件时信箱已满 则发送进程被置为 等信箱 状态 直到信箱有空时才被唤醒若取信件时信箱中无信 则接收进程被置为 等信件 状态 直到有信件时才被唤醒 110 Send实现 send MailBox M 把信件M送到指定的信箱MailBox中步骤 查找指定信箱MailBox 若信箱未满 则把信件M送入信箱且唤醒 等信件 者 若信箱已满置发送信件进程为 等信箱 状态 111 Receive实现 receive MailBox X 从指定信箱MailBox中取出一封信 存放到指定的地址X中步骤 查找指定信箱MailBox 若信箱中有信 则取出一封信存于X中且唤醒 等信箱 者 若信箱中无信件则置接收信件进程 等信件 状态 112 设fork 5 为5个信号量 初值均为1设信号量Mutex W 初值为1设有全局变量Count初值为0W用于封锁第5个哲学家Mutex用于对临界资源Count的访问 无死锁哲学家就餐问题解1 113 Philosopheri while 1 思考 P Mutex Count if Count 4 P W V Mutex P fork i P fork i 1 5 进食 V fork i V fork i 1 5 P Mutex Count i