操作系统进程管理ppt课件.ppt

1 第四章进程管理 多道程序设计进程线程进程 线程 调度 CPU调度 进程间的同步与互斥进程间的通信管程 2 五 进程的同步机制 进程的同步与互斥临界区的概念及使用原则信号量及PV操作生产者消费者问题读者写者问题哲学家就餐问题 3 同步问题 例子 谁买面包 甲5 00查看冰箱 面包没了5 05去超市5 10到达超市5 15买好面包5 20回家 把面包放入冰箱5 255 30 乙查看冰箱 面包没了去超市到达超市买好面包回家 把面包放入冰箱噢 TooMuch 4 直接作用和间接作用直接作用 进程间的相互联系是有意识的安排的 直接作用只发生在相交进程间间接作用 进程间要通过某种中介发生联系 是无意识安排的 可发生在两个有联系的进程之间 也可发生在无关进程之间 1 进程间的联系 5 进程的同步 直接作用 进程的同步 synchronism指系统中多个进程中发生的事件存在某种时序关系 需要相互合作 共同完成一项任务 具体说 一个进程运行到某一点时要求另一伙伴进程为它提供消息 在未获得消息之前 该进程处于等待状态 获得消息后被唤醒进入就绪态 6 例子 司机P1售票员P2while true while true 启动车辆 关门 正常运行 售票 到站停车 开门 7 进程的互斥 间接作用 由于各进程要求共享资源 而有些资源需要互斥使用 因此各进程间竞争使用这些资源 进程的这种关系为进程的互斥临界资源 criticalresource系统中某些资源一次只允许一个进程使用 称这样的资源为临界资源或互斥资源或共享变量 8 思考题 例举两个现实生活中需要同步与互斥的例子 9 临界区 互斥区 criticalsection 一个程序片段的集合 这些程序片段分散在不同的进程中 对某个共享的数据结构 共享资源 进行操作临界区 在进程中涉及到临界资源的程序段相关临界区 多个进程的临界区 10 a a 1print a a a 1print a P1 互斥 P2 互斥 Ifa 0thena a 1elsea a 1 P3 互斥 进程的互斥 间接作用 11 使用互斥区的原则 有空让进 当无进程在互斥区时 任何有权使用互斥区的进程可进入无空等待 不允许两个以上的进程同时进入互斥区多中择一 当没有进程在临界区 而同时有多个进程要求进入临界区 只能让其中之一进入临界区 其他进程必须等待有限等待 任何进入互斥区的要求应在有限的时间内得到满足让权等待 处于等待状态的进程应放弃占用CPU 以使其他进程有机会得到CPU的使用权 12 前提 任何进程无权停止其它进程的运行进程之间相对运行速度无硬性规定进程互斥的解决有两种做法 由竞争各方平等协商引入进程管理者 由管理者来协调竞争各方对互斥资源的使用具体方法 硬件软件 使用互斥区的原则 续 13 谁买面包 解法1 基本思想留言 锁 取消留言 解锁 如果看到留言 就不买 等待 解法1if nobread if noNote leaveNote buybread removeNote 14 谁买面包 解法2 进程AleavenoteA If noNoteB if noBread buybread removenoteA 进程BleavenoteB If noNoteA if noBread buybread removenoteB 15 谁买面包 解法3 进程AleavenoteA while NoteB Xdonothing if noBread buybread removenoteA 进程BleavenoteB If noNoteA Ydonothing if noBread buybread removenoteB 16 软件解法 1 free 表示临界区标志true 有进程在临界区false 无进程在临界区 初值 while free free true 临界区free false 17 软件解法 2 turn trueP进入临界区falseQ进入临界区 P while notturn 临界区turn false Q while turn 临界区turn true 18 软件解法 3 pturn qturn 初值为falseP进入临界区的条件 pturn notqturnQ进入临界区的条件 notpturn qturnP Q pturn true qturn true while qturn while pturn 临界区临界区pturn false qturn false 19 软件解法 4 Dekker算法 1 2 在解法 3 基础上引入turn枚举类型初值任意P while true pturn true while qturn if turn 2 pturn false while turn 2 pturn true 临界区turn 2 pturn false 20 软件解法 4 2 2 Q while true qturn true while pturn if turn 1 qturn false while turn 1 qturn true 临界区turn 1 qturn false 21 软件解法 5 Peterson算法 1 3 enter region i 临界区leave region i 非临界区 processi 当一个进程想进入临界区时 先调用enter region函数 判断是否能安全进入 不能则等待 当它从临界区退出后 需调用leave region函数 允许其它进程进入临界区 注 参数为进程号 22 defineFALSE0 defineTRUE1 defineN2 进程的个数intturn 轮到谁 intinterested N 兴趣数组 初始值均为FALSEvoidenter region intprocess process 0或1 intother 另外一个进程的进程号other 1 process interested process TRUE 表明本进程感兴趣turn process 设置标志位while turn process 软件解法 5 Peterson算法 2 3 23 voidleave region intprocess interested process FALSE 本进程已离开临界区 Peterson算法解决了互斥访问的问题 而且克服了强制轮流法的缺点 可以完全正常地工作 软件解法 5 Peterson算法 3 3 24 软件解法的缺点 1 忙等待 busywaiting 2 实现过于复杂 需要高的编程技巧硬件解法 提供专门的硬件指令 允许对一个字的内容进行检测和修正 或交换两个字的内容目的 解决共享变量的完整性和正确性简单 有效 特别适用于多处理机缺点 1 忙等待 2 饥饿 现象 25 硬件解法 1 测试并设置 TS 指令 booleanTS boolean lock booleanold old lock lock true TS指令功能描述 whileTS 每个临界资源设置一个lock 初值为false 26 硬件解法 2 交换 指令 voidSWAP int a int b inttemp temp a a b b temp Swap指令的功能描述 key true do SWAP 每个临界资源设置一个lock 初值为false 27 中断屏蔽方法 开关中断 指令 进入临界区前执行 执行 关中断 指令离开临界区后执行 执行 开中断 指令简单 有效较高的代价 限制CPU并发能力 临界区大小 不适用于多处理器 28 2 进程的同步机制 信号量及P V操作 以上介绍的各种算法都存在问题 它们是平等进程间的一种协商机制 需要一个地位高于进程的管理者来解决公有资源的使用问题操作系统可从进程管理者的角度来处理互斥的问题 信号量就是操作系统提供的管理公有资源的有效手段 29 进程的同步机制 续 同步机制 信号量及P V操作 管程 条件临界域 路径表达式等 用于集中式系统中 会合 通信顺序进程 分布式进程 远程过程调用等 适用于分布式系统中 30 同步机制应满足的基本要求 描述能力 可以实现 效率高 使用方便 进程的同步机制 续 31 1965年 由荷兰学者Dijkstra提出 所以P V分别是荷兰语的test proberen 和increment verhogen 一种卓有成效的进程同步机制最初提出的是二元信号量 互斥 推广到一般信号量 多值 同步 信号量及P V操作 32 信号量 semaphore 是一个数据结构定义如下 strucsemaphore intvalue pointer PCBqueue 信号量说明 semaphores 33 P操作 P s s value s value 1 if s value 0 该进程状态置为等待状态将该进程的PCB插入相应的等待队列末尾s queue 重新调度 34 V操作 V s s value s value 1 if s value 0 唤醒相应等待队列s queue中等待的一个进程改变其状态为就绪态 并将其插入就绪队列 35 P V操作为原语操作原语 primitiveoratomicaction是完成某种特定功能的一段程序 具有不可分割性或不可中断性即原语的执行必须是连续的 在执行过程中不允许被中断实现 屏蔽中断 信号量及P V操作 1 3 36 信号量的使用 必须置一次且只能置一次初值初值不能为负数只能执行P V操作 信号量及P V操作 2 3 37 用P V操作解决进程间互斥问题 38 经典的生产者 消费者问题 1 3 消费者 生产者 39 经典的生产者 消费者问题 2 3 同步问题 P进程不能往 满 的缓冲区中放产品 设置信号量为S1Q进程不能从 空 的缓冲区中取产品 设置信号量S2 40 S1初值为1 S2初值为0 P Q while true while true 生产一个产品 P s2 P s1 从缓冲区取产品 送产品到缓冲区 V s1 V s2 消费产品 经典的生产者 消费者问题 3 3 41 42 多个缓冲区的生产者和消费者 P i 0 while true 生产产品 P S1 往Buffer i 放产品 V S2 i i 1 n Q j 0 while true P S2 从Buffer j 取产品 V S1 消费产品 j j 1 n 有错误 43 思考题 要不要对缓冲区 临界资源 进行互斥操作 多个缓冲区的生产者和消费者 续 44 Q1 Q2 j 0 while true P S2 P mutex 从Buffer j 取产品 V mutex V S1 消费产品 j j 1 n n个缓冲区 m个生产者和k个消费者 P1 P2 i 0 while true 生产产品 P S1 P mutex 往Buffer i 放产品 V mutex V S2 i i 1 n 有错误 若颠倒两个P操作的顺序 45 Q1 Q2 j 0 while true P S2 P mutex2 从Buffer j 取产品 j j 1 n V mutex2 V S1 消费产品 n个缓冲区 m个生产者和k个消费者 P1 P2 i 0 while true 生产产品 P S1 P mutex1 往Buffer i 放产品 i i 1 n V mutex1 V S2 正确 46 1 信号量的物理含义 S 0表示有S个资源可用S 0表示无资源可用S 0则 S 表示S等待队列中的进程个数P S 表示申请一个资源V S 表示释放一个资源信号量的初值应该大于等于0 信号量及P V操作讨论 1 3 47 2 P V操作必须成对出现 有一个P操作就一定有一个V操作当为互斥操作时 它们同处于同一进程当为同步操作时 则不在同一进程中出现如果P S1 和P S2 两个操作在一起 那么P操作的顺序至关重要 一个同步P操作与一个互斥P操作在一起时同步P操作在互斥P操作前而两个V操作无关紧要 信号量及P V操作讨论 2 3 48 3 P V操作的优缺点优点 简单 而且表达能力强 用P V操作可解决任何同步互斥问题 缺点 不够安全 P V操作使用不当会出现死锁 遇到复杂同步互斥问题时实现复杂 信号量及P V操作讨论 3 3 49 思考题 1 用P V操作解决下图之同步问题 get copy put f s t g 50 用P V操作解决司机与售票员的问题 51 4 IPC经典问题 1 读者写者问题问题描述 有两组并发进程 读者和写者 共享一组数据区要求 允许多个读者同时执行读操作不允许读者 写者同时操作不允许多个写者同时操作 52 第一类 读者优先 如果读者到 1 无读者 写者 新读者可以读2 有写者等 但有其它读者正在读 则新读者也可以读3 有写者写 新读者等如果写者到 1 无读者 新写者可以写2 有读者 新写者等待3 有其它写者 新写者等待 53 第一类读者写者问题的解法 读者 P mutex readcount if readcount 1 P w V mutex 读P mutex readcount if readcount 0 V w V mutex 写者 P w 写V w 54 2 哲学家就餐问题 问题描述 有五个哲学家围坐在一圆桌旁 桌中央有一盘通心粉 每人面前有一只空盘子 每两人之间放一只筷子每个哲学家的行为是思考 感到饥饿 然后吃通心粉为了吃通心粉 每个哲学家必须拿到两只筷子 并且每个人只能直接从自己的左边或右边去取筷子 55 哲学家就餐问题解法 1 defineN5voidphilosopher inti while true 思考 取fork i 取fork i 1 5 进食 放fork i 放fork i 1 5 56 为防止死锁发生可采取的措施 最多允许4个哲学家同时坐在桌子周围仅当一个哲学家左右两边的筷子都可用时 才允许他拿筷子 给所有哲学家编号 奇数号的哲学家必须首先拿左边的筷子 偶数号的哲学家则反之为了避免死锁 把哲学家分为三种状态 思考 饥饿 进食 并且一次拿到两只筷子 否则不拿 哲学家就餐问题解法 1 57 哲学家就餐问题解法 2 defineN5 defineTHINKING0 defineHUNGRY1 defineEATING2 typedefintsemaphore intstate N semaphoremutex 1 semaphores N 58 voidtest inti if state i HUNGRY 哲学家就餐问题解法 1 59 voidphilosopher inti while true 思考 P 拿左筷子 拿右筷子 进食 放左筷子 放右筷子 P state i THINKINGs i 0 哲学家就餐问题解法 1 60 六 进程通信 概述消息缓冲通信方式 61 概述 P V操作实现进程间的低级通信 它只能传递简单的信号 不能传递交换大量信息P V操作称为低级通信原语如果要在进程间传递大量信息则要用高级通信原语 称为进程间通信 62 1 进程通信的方式 1 4 1 共享内存相互通信的进程间设置公共内存一组进程向该公共内存中写另一组进程从公共内存中读 实现两组进程间的信息交换该通信模式需要解决两个问题 63 2 消息传递系统提供了两个高级通信原语 send和receivesend 当要进行消息传递时执行sendreceive 当接收者要接收消息时执行receive 进程通信的方式 2 4 64 两种消息传递实现方案 消息缓冲在内存中开设缓冲区 发送进程将消息送入缓冲区 接收进程接收传递来的缓冲区信箱通信 进程通信的方式 3 4 65 3 共享文件模式管道通信 进程通信的方式 4 4 66 2 消息缓冲 1 5 有界缓冲区工作原理 在操作系统空间设置一组缓冲区 当发送进程需要发送消息时 执行send系统调用 产生自愿性中断 进入操作系统 操作系统为发送进程分配一个空缓冲区 并将所发送的消息从发送进程copy到缓冲区中 然后将该载有消息的缓冲区连接到接收进程的消息链链尾 如此就完成了发送过程 发送进程返回到用户态继续执行 67 消息缓冲 2 5 有界缓冲区工作原理 在以后某个时刻 当接收进程执行到receive接收原语时 也产生自愿性中断进入操作系统 由操作系统将载有消息的缓冲区从消息链中取出 并把消息内容copy到接收进程空间 之后收回缓冲区 如此就完成了消息的接收 接收进程返回到用户态继续进行 68 消息缓冲 3 5 69 消息缓冲区结构 消息长度消息正文发送者消息队列指针 消息缓冲 4 5 70 用P V操作来实现Send原语 Send R M P m mutex Begin把缓冲区挂到接收进程根据R找接收进程 的消息链链尾 如果没找到出错返回 V m mutex 申请空缓冲区P s b V s m P b mutex END摘空缓冲区 V b mutex 把消息从M处copy到空缓冲区 其中s b初值 n s m初值 0 消息缓冲 5 5 71 3 信箱通信 1 4 信箱组成信箱说明与信箱体可存放信件数 已存放信件数 指针信箱使用规则若发送信件时信箱已满 则发送进程被置为 等信箱 状态 直到信箱有空时才被释放若取信件时信箱中无信 则接收进程被置为 等信件 状态 直到有信件时才被释放 72 信箱通信 2 4 Send实现send N M 把信件M送到指定的信箱N中步骤 查找指定信箱N 若信箱未满 则把信件M送入信箱且释放 等信件 者 若信箱已满置发送信件进程为 等信箱 状态 73 信箱通信 3 4 Receive实现receive N X 从指定信箱N中取出一封信 存放到指定的地址X中步骤 查找指定信箱N若信箱中有信 则取出一封信存于X中且释放 等信箱 者若信箱中无信件则置接收信件进程 等信件 状态 74 信箱通信 4 4 应用实例 磁盘管理进程 从信箱中收取信件 处理 启动磁盘工作其他进程 要求访问磁盘 向磁盘管理进程发一封信思考题 用进程通信的办法解决生产者消费者问题 75 4 管道通信方式Pipe 也称共享文件方式 基于文件系统 利用一个打开的共享文件连接两个相互通信的进程 文件作为缓冲传输介质 76 5 高级通信的特征 通信链路 点对点 多点 广播单向 双向有容量 链路带缓冲区 无容量 发送方和接收方需自备缓冲区 数据格式 字节流 各次发送之间的分界 在接收时不被保留 没有格式报文 各次发送之间的分界 在接收时被保留 通常有格式 如表示类型 定长 不定长报文 可靠报文 不可靠报文收发操作的同步方式发送阻塞 直到被链路容量或接收方所接受 和不阻塞 失败时立即返回 接收阻塞 直到有数据可读 和不阻塞 无数据时立即返回 由事件驱动收发 在允许发送或有数据可读时 才做发送和接收操作 77 六 进程的同步机制 管程 管程的提出问题 采用PV同步机制来编写并发程序 对于共享变量及信号量变量的操作将被分散于各个进程中缺点 易读性差 不利于修改和维护 正确性难以保证解决 Dijkstra 1971 秘书 进程Hansen和Hoare 1973 管程 78 定义 管程一种同步机制是关于共享资源的数据及在其上操作的一组过程 或共享数据结构及其规定的所有操作 系统按资源管理的观点分解成若干模块 用数据表示抽象系统资源 同时分析了共享资源和专用资源在管理上的差别 按不同的管理方式定义模块的类型和结构 使同步操作相对集中 从而增加了模块的相对独立性 管程的定义 79 管程的形式 TYPEmonitor name MONITOR 共享变量说明define本管程内所定义 本管程外可调用的过程 函数 名字表use本管程外所定义 本管程内将调用的过程 函数 名字表PROCEDURE过程名 形参表 过程局部变量说明 BEGIN语句序列 END 80 FUNCTION函数名 形参表 值类型 函数局部变量说明 BEGIN语句序列 END BEGIN共享变量初始化语句序列 END 管程的四个组成部分 名称数据结构说明对该数据结构进行操作的一组过程 函数初始化语句 管程的形式 续 81 1 模块化 一个管程是一个基本程序单位 可以单独编译 2 抽象数据类型 管程是一种特殊的数据类型 其中不仅有数据 而且有对数据进行操作的代码 3 信息掩蔽 管程是半透明的 管程中的外部过程 函数 实现了某些功能 至于这些功能是怎样实现的 在其外部则是不可见的 管程的三个主要的特性 82 管程有如下几个要素 1 管程中的共享变量在管程外部是不可见的 外部只能通过调用管程中所说明的外部过程 函数 来间接地访问管程中的共享变量 2 为了保证管程共享变量的数据完整性 规定管程互斥进入 3 管程通常是用来管理资源的 因而在管程中应当设有进程等待队以及相应的等待及唤醒操作 管程的要素 83 问题 多个进程出现在管程中当一个进入管程的进程执行等待操作时 它应当释放管程的互斥权当一个进入管程的进程执行唤醒操作时 如 唤醒 管程中便存在两个同时处于活动状态的进程处理方法有三种 等待 继续 直到 退出或等待 Hoare 等待 继续 直到 等待或退出规定唤醒为管程中最后一个可执行的操作 管程实现时遇到的问题 1 2 84 因为管程是互斥进入的 所以当一个进程试图进入一个已被占用的管程时 应当在管程的入口处等待 所以在管程的入口处应当有一个进程等待队列 称作入口等待队列如果进程 唤醒进程 则 等待 继续 如果进程 在执行又唤醒进程 则 等待 继续 如此 在管程内部 由于执行唤醒操作 可能会出现多个等待进程 因而还需要有一个进程等待队列 这个等待队列被称为紧急等待队列 它的优先级应当高于入口等待队列的优先级 管程实现时遇到的问题 2 2 85 由于管程通常是用于管理资源的 因而在管程内部 应当存在某种等待机制 当进入管程的进程因资源被占用等原因不能继续运行时使其等待 为此在管程内部可以说明和使用一种特殊类型的变量 称作条件变量 varc condition 对于条件型变量 可以执行wait和signal操作 管程实现时遇到问题的解决 1 2 86 wait c 如果紧急等待队列非空 则唤醒第一个等待者 否则释放管程的互斥权 执行此操作的进程的PCB入c链尾部signal c 如果c链为空 则相当于空操作 执行此操作的进程继续 否则唤醒第一个等待者 执行此操作的进程的PCB入紧急等待队列的尾部 管程实现时遇到问题的解决 2 2 87 管程实现的两个主要途径 直接构造 效率高 间接构造 用某种已经实现的同步机制去构造例如 用P V操作构造管程 管程的实现 88 TYPEone instance RECORDmutex semaphore 初值1 urgent semaphore 初值0 urgent count integer 初值0 END TYPEmonitor elements MODULE defineenter leave wait signal mutex 入口互斥队列 urgent 紧急等待队列 urgent count 紧急等待队列计数 89 PROCEDUREenter VARinstance one instance BEGINP instance mutex END 90 PROCEDUREleave VARinstance one instance BEGINIFinstance urgent count 0THENBEGINinstance urgent count V instance urgent ENDELSEV instance mutex END 91 PROCEDUREwait VARinstance one instance VARs semephore VARcount integer BEGINcount IFinstance urgent count 0THENBEGINinstance urgent count V instance urgent ENDELSEV instance mutex P s END 92 PROCEDUREsignal VARinstance one instance VARs semaphore VARcount integer BEGINIFcount 0THENBEGINcount instance urgent count V s P instance urgent ENDEND 93 例子 读者 写者问题 94 TYPEr and w MODULE VARinstance one instance rq wq semaphore r count w count integer reading count write count integer definestart r finish r start w finish w usemonitor elements enter monitor elements leave monitor elements wait monitor elements signal 95 PROCEDUREstart r BEGINmonitor elements enter instance IFwrite count 0THENmonitor elements wait instance rq r count reading count monitor elements signal instance rq r count monitor elements leave instance END 96 PROCEDUREfinish r BEGINmonitor elements enter instance reading count IFreading count 0THENmonitor elements signal instance wq w count monitor elements leave instance END 97 PROCEDUREstart w BEGINmonitor elements enter instance write count IF write count 1 OR reading count 0 THENmonitor elements wait instance wq w count monitor elements leave instance END 98 PROCEDUREfinish w BEGINmonitor elements enter instance write count IF r count 0 THENmonitor elements signal instance wq w count E