第6章进程间的制约关系

第6章进程间的制约关系 第6章进程间的制约关系 1 2 3 本章讲述内容 进程间的两种制约关系 互斥与同步 正确处理互斥与同步的方法 信号量以及在信号量上的P V操作 死锁以及解决死锁的途径 进程间的高级通信 4 教学目的与要求 理解进程间的两种制约关系 互斥与同步理解临界资源和临界区的概念理解并掌握记录型信号量机制及如何用于解决经典进程同步问题 理解并掌握死锁的预防 避免和检测算法了解进程通信的类型 理解并掌握消息传递通信机制 重点和难点 重点 进程的同步和互斥用信号量机制解决进程同步 互斥问题进程间的通信机制产生死锁的必要条件用于死锁避免的银行家算法难点 进程的同步和互斥用信号量机制解决进程同步 互斥问题进程间的通信机制 主要外语词汇 Synchronization 同步 Criticalsection 临界区 CriticalresourceSemaphore 信号量 Deadlock 第6章进程间的制约关系 6 1进程间的制约关系 6 2信号量与P V操作 6 3死锁 6 4高级进程通信 6 1进程间的制约关系 6 1 1与时间有关的错误6 1 2竞争资源 互斥6 1 3协同工作 同步 6 1进程间的制约关系 6 1 1与时间有关的错误 1 与时间有关的错误一个进程对其他进程的影响无法预测 进程的并发 使一个进程何时占有处理机 占有多长时间 执行速度的快慢 以及外界对进程产生作用等都带有随机性 在操作系统里 把这种由于时间因素的影响而产生的错误 称为 与时间有关的错误 为输出井设置一张 输出井文件目录表 每个目录项记录一个要打印输出的文件名以及该文件在磁盘的存放地址 系统安排两个指针 out和in out总是指向下一个被打印的文件 in总是指向下一个可用的目录项位置 缓输出程序 根据out的指点进行打印 井管理写程序根据in的指点存放要求输出的文件目录信息 2 对输入井文件目录的管理 实例 进程Ain 7进程B in 8 in 9 3 通过双缓冲区复制文件 编写一个复制n个记录的程序 把文件F中的每个记录依次读到输入缓冲区R 再从R拷贝到输出缓冲区T 最后写到文件G中 假定R和T正好存放一个记录 GET 从文件F按照顺序读出一个记录 送入输入缓冲区R COPY 把输入缓冲区R里的记录拷贝到输出缓冲区T里 PUT 从输出缓冲区T里读出一个记录 依照顺序写入文件G 若不管GET COPY PUT的执行关系 可有六种执行可能 1 COPY PUT GET 2 COPY GET PUT 3 PUT COPY GET4 PUT GET COPY 5 GET COPY PUT 6 GET PUT COPY 6 1 2竞争资源 互斥 进程Ain 7进程B in 8 in 9 对共享变量in的使用要保持 互斥 两个进程不能同时使用变量in 6 1 2竞争资源 互斥 1 共享变量 或 临界资源 可以被进程共享的资源 如文件 队列 缓冲区 表格 变量等 互斥 进程间的制约关系 与一个共享变量 或临界资源 交往的多个进程 为了保证它们各自运行结果的正确性 当其中的一个进程正在对该变量 或临界资源 进行操作时 不允许其他进程同时对它进行操作 4 解决临界区互斥必须遵循的准则空闲则入忙则等待 互斥 有限等待 3 临界区 临界区 或临界段 进程程序中 真正需要保证互斥执行 的那一段程序 只有涉及到共享变量的那一部分程序 才真正需要保证互斥地执行 进程的互斥 两个或两个以上的进程不能同时进入共享同一临界资源的临界区 6 1 3协同工作 同步 进程间的同步 当一个进程运行到某一点时 除非合作进程已经完成了某种操作或发来了消息 否则就必须暂时等待那些操作的完成或信息的到来 GET和COPY间的协调一致 同步点 同步点 进程间的制约关系 临界资源 可以被进程 互斥 共享的资源 临界区 每个进程中访问临界资源的那一部分程序代码 互斥 间接制约 两个或两个以上的进程不能同时进入共享同一临界资源的临界区 进程间竞争共享资源 独占分配到的部分或全部共享资源 同步 直接制约 又称协作关系 指某些进程为完成同一任务需要分工协作等待来自其他进程的信息 6 2 1信号量与P V操作的定义 1 信号量的定义 信号量 是一个具有非负初值的整型变量 并有一个队列与它关联 定义一个信号量S时 要给出它的初值Vs 给出与它相关的队列指针Vq 在一个信号量S上 只能做规定的两种操作 P操作 记为P S 和V操作 记为V S 6 2信号量与P V操作 2 P操作和V操作P s s s if s 0 该进程状态置为等待状态将该进程的PCB插入相应的等待队列末尾 V s s s if s 0 唤醒相应等待队列中等待的一个进程改变其状态为就绪态并将其插入就绪队列 3 关于信号量及其P V操作的几点说明 S 0时 信号量值表示该类资源的可用资源数S0时 每执行一次P操作 意味着请求分配一个单位的该类资源给执行P操作的进程 即S S 1 S 0时 每执行一次V操作 意味着进程释放一个单位的该类可用资源 即S S 1 而此时若S等待队列中有因该资源而被封锁的进程 则把队列中的一个进程唤醒 转入就绪队列 6 2 2用P V操作实现互斥 P V操作图示 为临界资源设置一个互斥信号量s 其初值为1 在每个进程中将临界区代码置于P s 和V s 原语之间 必须成对使用P和V原语 遗漏P原语则不能保证互斥访问遗漏V原语则不能在使用临界资源之后将其释放 给其他等待的进程 P V原语不能次序错误 重复或遗漏 例1两个进程互斥访问公用变量count semophores intcount count 0 s 1 Cobeginprocessp1Cobeginprocessp2 p s p s R1 count R2 count R1 R1 1 R2 R2 1 count R1 count R2 v s v s Coend Coend 例2飞机订票 一民航航班售票系统由n个售票处 每个售票处通过终端访问系统中的公用数据区 假定公共数据区中一些单元Hk k 1 2 3 分别存放各次航班的现存票数 设P1 P2 Pn表示各售票处的处理进程 R1 R2 Rn表示各进程执行时所用的工作单元 用信号量实现进程互斥 semophores s 1 intRi CobeginprocessPi i 1 2 n 按旅客定票要求找到某次航班Hi P s Ri Hi ifRi 1 Ri Ri 1 Hi Ri V s 输出一张票 else V s 输出票已售完 Coend 6 2 3用P V操作实现同步 同步图示 用P V操作解决GET与COPY的同步问题 从文件F取出一个记录送至输入缓冲区R 向COPY发送 可以拷贝 的消息 等待COPY发来的 拷贝结束 消息 等待GET发来 可以拷贝 的消息 将输入缓冲区R里的记录拷贝到输出缓冲区T里 向GET发送 拷拷贝结束 消息 GET COPY 1 1 2 2 3 3 V s1 P s1 P s2 V s2 S1 0s2 0 6 2 4互斥 同步样例分析 1生产者 消费者问题 theproducer consumerproblem 2读者 写者问题 thereaders writersproblem 3哲学家进餐问题 Thedinningphilosophersproblem 1 生产者 消费者问题 问题描述 若干进程通过有限的共享缓冲区交换数据 其中 生产者 进程不断写入 而 消费者 进程不断读出 生产者 消费者问题 theproducer consumerproblem 把并发进程的同步和互斥问题一般化 可抽象为一般模型 生产者 消费者问题资源的消费者 系统中使用某一类资源的进程资源的生产者 系统中释放同一类资源的进程 生产者 消费者问题描述 生产者进程与消费者进程之间设置一个具有n个缓冲区的缓冲池 它们之间必须保持同步 不允许消费者进程到一个空缓冲区去取产品 不允许生产者进程向一个已装满产品且尚未被取走的缓冲区中投放产品 in out 定义变量 用数组表示具有n个 0 1 n 1 缓冲区的缓冲池 用输入指针in指示下一个可投放产品的缓冲区 生产者进程投放一个产品后 输入指针加1 用输出指针out指示下一个可从中获取产品的缓冲区 消费者进程取走一个产品后 输出指针加1 假设缓冲池是组织成循环缓冲的 应把输入指针加1表示成in in 1 modn 输出指针加1表示成out out 1 modn 当 in 1 modn out时表示缓冲池满 当in out时表示缓冲池空 1 一个生产者 一个消费者 多个缓冲区 算法分析 1 消费者想接收数据时 有界缓冲区中至少有一个单元是满的 2 生产者想发送数据时 有界缓冲区中至少有一个单元是空的 2 有界缓冲区是临界资源 各生产进程和消费者必须互斥访问 1 一个生产者 一个消费者 多个缓冲区 生产者While true 生产一件产品 放入一件产品 in in 1 mod10 消费者While true 取出一件产品 out out 1 mod10消费产品 P empty P full V empty V full Question empty full初值 semaphoreempty full empty 10 full 0 2 多个生产者 多个消费者 n个缓冲区 Question 两个生产者进程同时向缓冲区中放产品 生产者While true 生产一件产品 放入一件产品 消费者While true 取出一件产品 消费产品 P empty P full V empty V full semaphoreempty full empty 10 full 0 P S1 V S1 P S2 V S2 semaphoreS1 S2 S1 1 S2 1 2 读者 写者 问题 问题描述 对共享资源的读写操作 任一时刻 写者 最多只允许一个 而 读者 则允许多个 读 写 互斥 写 写 互斥 读 读 允许 Thefirstreaders writersproblemnoreaderwillbekeptwaitingunlessawriterhasalreadyobtainedpermissiontousethesharedobject Thesecondreaders writersproblemonceawriterisready thatwriterperformsitswriteassoonaspossible Inotherwords ifawriteriswaitingtoaccesstheobject nonewreadersmaystartreading 读者 写者 问题分类 Reader进程优先 Thefirstreaders writersproblem 如果Reader进程来 无Reader进程 Writer进程 新Reader进程可以读 有Writer进程等 但有其它Reader进程正在读 则新Reader进程也可以读 有Writer进程写 新Reader进程等 如果Writer进程来 无Reader进程 新Writer进程可以写 有Reader进程 新Writer进程等待 有其它Writer进程 新Writer进程等待 Reader进程优先问题的解法 变量和信号量定义如下 使用Readcount对Reader进程计数 初值为0 rmutex是对变量Readcount进行互斥操作的信号量 初值设为1 Wmutex是写信号量 初值设为1 Varrmutex wmutex semaphore 1 1 Readcount integer 0 Reader进程 repeatP rmutex Readcount Readcount 1 ifReadcount 1thenP wmutex 读进程把写进程阻塞 V rmutex performreadoperation P rmutex Readcount Readcount 1 IfReadcount 0thenV wmutex 最后一个读进程退出 V rmutex untilfalse 第一个Reader进程申请读操作 要检查是否有Writer进程在执行写操作 最后一个Reader进程退出时 要检查是否有Writer进程在等待 若有则唤醒 repeatP wmutex 实现Writer进程间的互斥 performwriteoperation V wmutex untilfalse Writer进程 Reader进程 repeatP rmutex Readcount Readcount 1 ifReadcount 1thenP wmutex V rmutex performreadoperation P rmutex Readcount Readcount 1 IfReadcount 0thenV wmutex V rmutex untilfalse Writer进程 repeatP wmutex performwriteoperation V wmutex untilfalse Varrmutex wmutex semaphore 1 1 Readcount integer 0 Question 当有读者在读时 若同时有读者和写者访问共享资源 读者优先读 写者等待 写者 饥饿 写者优先算法 思考题 读者 写者问题如果再要求 写者优先 即一旦有Writer进程到达 后续的Reader进程必须等待 而且无论是否有读者在读文件 怎样解决 3哲学家进餐问题 Thedinningphilosophersproblem Z0 Z3 Z4 Z2 Z1 0 1 2 4 3 要求 每个哲学家思考 饥饿 然后进餐 每个哲学家饥饿时 总是先拿左边的筷子 拿不到则等待 拿到后再拿右边的筷子 拿到两把筷子后才能进餐 进餐完毕 先放下左边的筷子 再放下右边的筷子 保证不会有两个相邻的哲学家同时进餐 算法分析 筷子是临界资源 每一把筷子必须互斥使用 需设置对应的互斥信号量 Varchopstick array 0 4 ofsemaphore 一个信号量chopstick i 表示一只筷子 初值为1 philosopher i while TRUE think P chopstick i P chopstick i 1 mod5 eat V chopstick i V chopstick i 1 mod5 方案1 Question 若每个哲学家同时拿起各自左边的筷子 Severalpossibleremediestothedeadlockproblem 几种可能的补救方案 Allowatmostfourphilosopherstobesittingsimultaneouslyatthetable 最多允许四个哲学家同时坐在桌旁 Allowaphilosophertopickuphischopsticksonlyifbothchopsticksareavailable todothisshemustpickthemupinacriticalsection 仅当两支筷子都可用时才允许拿起筷子 Useanasymmetricsolution thatis anoddphilosopherpicksupfirstherleftchopstickandthenherrightchopstick whereasanevenphilosopherpicksupherrightchopstickandthenherleftchopstick 采用非对称方案 奇数哲学家先拿起左手的筷子再拿右手的筷子 而偶数哲学家采用相反顺序 为防止出现死锁危险 可考虑只允许4位哲学家进入餐厅 第5位只有在已进入就餐的一位哲学家退席后 才能去就餐 这时最多只有4位哲学家就座 因此至少可保证有一位哲学家能拿到他左右的两只筷子 从而完成就餐 方案2 5只筷子仍需互斥使用 所以仍将筷子编号为0 4 对应设置5个初值为1的互斥信息量 chopstick i 0 i 4 设置同步信号量seat 初值为4 管理4个座位 第i 0 i 4 个哲学家的 思考 就餐 思考 过程可以描述为 philosopher i while TRUE think P seat 请求进餐P chopstick i P chopstick i 1 mod5 eat V chopstick i V chopstick i 1 mod5 V seat 退出进餐 6 3死锁 6 3 1死锁与产生死锁的必要条件 资源分配图 1 哲学家进餐问题产生死锁 Z0 Z3 Z4 Z2 Z1 0 1 2 4 3 P V操作使用不当产生死锁 从文件F取出一个记录送至输入缓冲区R 向COPY发送 可以拷贝 的消息 等待COPY发来的 拷贝结束 消息 等待GET发来 可以拷贝 的消息 将输入缓冲区R里的记录拷贝到输出缓冲区T里 向GET发送 拷拷贝结束 消息 GET COPY 1 1 2 2 3 3 V s1 P s1 P s2 V s2 S1 0s2 0 Question V S1 P S2 互换 竞争系统资源引起的死锁情况 设系统有一台打印机 R1 一台扫描仪 R2 可供进程P1和P2共享 若形成环路 这样会产生死锁 2 死锁的定义 死锁 指系统中若存在一组进程 它们中的每一个都占用了某种资源而又都在等待其中另一个所占用的资源 这种等待永远不会结束 称这一组进程处于死锁状态 关于死锁的一些结论 参与死锁的进程最少是两个参与死锁的进程至少有两个已经占有资源参与死锁的所有进程都在等待资源参与死锁的进程是当前系统中所有进程的子集注 如果死锁发生 会浪费大量系统资源 甚至导致系统崩溃 3 产生死锁的必要条件 互斥条件 资源独占 进程所竞争的资源必须被互斥使用部分分配 占用并等待 条件 请求和保持条件 请求资源得不到满足而等待时不释放已占有资源非剥夺条件 不可强占 进程已获得的资源 只能使用完时自行释放 不能被抢占 循环等待条件 环路等待条件 存在一个至少包含两个进程的循环等待资源链 其中 每个进程都正在等待前一个进程所占有的资源 4处理死锁的基本方法 预防死锁 破坏产生死锁的某个必要条件防止发生死锁 避免死锁 在资源的动态分配过程中 用某种方法防止系统进入不安全状态 从而避免发生死锁 检测死锁 允许发生死锁 及时地检测出死锁的发生 并精确地确定与死锁有关的进程和资源 恢复死锁 采取适当措施 从系统中将已发生的死锁清除掉 6 3 2死锁的预防 死锁的预防 破坏产生死锁的某个必要条件防止发生死锁 预防死锁的三种策略 破坏 部分分配 占用并等待 条件 资源一次性分配破坏 非剥夺条件 破坏 循环等待条件 6 3 3死锁的避免 死锁的避免 在资源的动态分配过程中 用某种方法防止系统进入不安全状态 从而避免发生死锁 避免死锁 把系统的状态分为安全状态和不安全状态 只有能使系统始终都处于安全状态 便可避免发生死锁 典型的避免死锁的算法是 银行家算法 1 安全状态与不安全状态 安全状态 指系统能按某种进程顺序来为每个进程分配其所需资源 直至满足每个进程对资源的最大需求 使每个进程都可以顺序完成 若系统不存在这样一个序列 则称系统处于不安全状态 在T0时刻存在一个安全序列 P2 P1 P3 2 安全状态之例 假定系统中有三个进程P1 P2和P3 共有12台磁带机 进程P1总共要求10台磁带机 P2和P3分别要求4台和9台 假设在T0时刻 系统状态如下表所示 如果不按照安全序列分配资源 则系统可能会由安全状态进入不安全状态 3 由安全状态向不安全状态的转换 例如 在T0时刻以后 P3又请求1台磁带机 若此时系统把剩余3台中的1台分配给P3 则系统便进入不安全状态 大家可以思考一下 其中的原因 4 安全状态与不安全状态的结论 处于安全状态下的系统不会发生死锁 避免死锁的关键 让系统在动态分配资源的过程中 不要进入不安全状态 5 银行家算法 银行家拥有一笔周转资金客户要求分期贷款 如果客户能够得到各期贷款 就一定能够归还贷款 否则就一定不能归还贷款银行家应谨慎的贷款 防止出现坏帐 用银行家算法避免死锁操作系统 银行家 操作系统管理的资源 周转资金 进程 要求贷款的客户 银行家算法 银行家算法的流程图 开始 1 所有进程的 运行完标志 置为假 2 对某进程的资源申请试探性分配 3 比较系统剩余资源数与 运行完标志 为假的进程尚需资源数 寻找能满足资源需求的进程 存在这样的进程吗 将该进程的 运行完标志 置真 并假定运行完归还所占资源 系统中还有 运行完标志 为假的进程吗 对 2 中进程的资源申请分配后 系统处于安全状态 完成分配 对 2 中进程的资源申请分配后 系统处于不安全状态 拒绝分配 结束 Y N Y N 单项资源的银行家算法 4个客户每个都有一个贷款额度 多项资源的银行家算法 总的资源E 已分配资源P 剩余资源A 1 多项资源的银行家算法中的数据结构 1 可利用资源向量Available 数组 每一个元素代表一类可利用的资源数目 Available j K 表示系统中现有Rj类资源K个 2 最大需求矩阵Max n m的矩阵 定义系统中n个进程中的每一个进程对m类资源的最大需求 Max i j K 表示进程i需要Rj类资源的最大数目为K 1 银行家算法中的数据结构 3 分配矩阵Allocation n m的矩阵 定义系统中每一类资源当前已分配给每一进程的资源数 Allocation i j K 表示进程i当前已分得Rj类资源的数目为K 4 需求矩阵Need n m的矩阵 表示每一个进程尚需的各类资源数 Need i j K 表示进程i还需要Rj类资源K个 方能完成其任务 Need i j Max i j Allocation i j 需求矩阵Need可以用下述公式计算 1 银行家算法中的数据结构 2 银行家算法 设Requesti是进程Pi的请求向量Requesti j K 表示进程Pi需要K个Rj类型的资源 当进程Pi发出资源请求后 系统按下述步骤进行检查 1 如果Requesti j Need i j 便转向步骤2 否则认为出错 因为它所需要的资源数已超过它所宣布的最大值 2 如果Requesti j Available j 便转向步骤 3 否则表示尚无足够资源 Pi等待 3 系统试探着把资源分配给进程Pi 并修改下面数据结构中的数值 Available j Available j Requesti j Allocation i j Allocation i j Requesti j Need i j Need i j Requesti j 4 系统执行安全性算法 检查此次资源分配后 系统是否处于安全状态 若安全 才正式将资源分配给进程Pi 完成本次分配 否则 将本次的试探分配作废 恢复原来的资源分配状态 让进程Pi等待 1 设置两个向量 工作向量Work 表示系统可提供给进程继续运行所需的各类资源数目 含有m个元素 在执行安全算法开始时 Work Available 进程运行完标志Finish 表示系统是否有足够的资源分配给进程 使之运行完成 开始时先做Finish i false 当有足够资源分配给进程时 再令Finish i true 3 安全性算法 2 从进程集合中找一个能满足下述条件的进程 Finish i false Need i j Work j 若找到 执行步骤 3 否则 执行步骤 4 3 当进程Pi获得资源后 可顺利执行 直至完成 并释放出分配给它的资源 故应执行 Work j Work j Allocation i j Finish i true gotostep2 4 如果所有进程的Finish i true都满足 则表示系统处于安全状态 否则 系统处于不安全状态 银行家算法的流程图 开始 1 所有进程的 运行完标志 置为假 2 对某进程的资源申请试探性分配 3 比较系统剩余资源数与 运行完标志 为假的进程尚需资源数 寻找能满足资源需求的进程 存在这样的进程吗 将该进程的 运行完标志 置真 并假定运行完归还所占资源 系统中还有 运行完标志 为假的进程吗 对 2 中进程的资源申请分配后 系统处于安全状态 完成分配 对 2 中进程的资源申请分配后 系统处于不安全状态 拒绝分配 结束 Y N Y N T0时刻的资源分配表 最大需求矩阵 分配矩阵 需求矩阵 可用资源向量 4 银行家算法之例 假定系统中有五个进程 P0 P1 P2 P3 P4 和三类资源 A B C 各种资源的数量分别为10 5 7 在T0时刻的资源分配情况如下图所示 问题 1 利用安全性算法 检查T0时刻的安全性 2 在T0时刻 P1发出请求向量Request1 1 0 2 系统能否将资源分配给它 1 T0时刻的安全性 利用安全性算法对T0时刻的资源分配情况进行分析 在T0时刻存在一个安全序列 P1 P3 P4 P2 P0 因此 系统是安全的 在T0时刻还有其他的安全序列吗 T0时刻的安全序列 工作向量 2 P1请求资源 P1发出请求向量Request1 1 0 2 系统按银行家算法进行检查 Request1 1 0 2 Need1 1 2 2 Request1 1 0 2 Available1 3 3 2 系统先假定可为P1分配资源 并修改Available Allocation1和Need1向量 由此形成的资源变化情况如原图中的圆括号所示 再利用安全性算法检查此时系统是否安全 2 P1申请资源时的安全性检查 由所进行的安全性检查得知 可以找到一个安全序列 P1 P3 P4 P0 P2 因此 系统是安全的 可以把P1申请的资源分配给它 思考题 在T0时刻 P4发出请求向量Request4 3 3 0 系统能否将资源分配给它 在T0时刻 P0发出请求向量Request0 0 2 0 系统能否将资源分配给它 6 3 4死锁的检测并恢复 1 利用资源分配图检测死锁 6 3 4死锁的检测并恢复 2 死锁的恢复 删除环中的若干进程 释放占用的资源 使其他进程能继续运行 临时把某个资源从占用者手中剥夺 给另一个进程使用 周期地记录各进程执行情况 一旦检测到死锁 就按记录的文件进行回退 让损失减到最小 6 4高级进程通信 1 进程间的低级与高级通信 进程间的低级通信信号量上的P V操作是进程间的一种通信方式 通信双方不交换信息 只是事先的一种约定 用P V操作实现的通信 是进程间的 低级通信 进程间的高级通信进程间交换数据 系统提供通信命令给用户在程序中使用 2 5 1进程通信的类型 1 管道通信2 共享存储区通信3 消息传递通信 1 管道通信 管道通信又称共享文件通信机制 管道 pipe 是连接读 写进程的一个特殊文件 允许进程按先进先出方式传送数据 也能使进程同步执行操作 管道通信 发送进程以字符流形式把大量数据送入管道 接收进程从管道中接收数据 管道通信机制示意图 管道 2 共享存储区通信 Shared MemorySystem 共享存储器通信 相互通讯的进程通过对共享存储区的读写来交