计算机操作系统(汤子瀛)版chapter2-2.ppt

第二章进程管理 2 第二章进程管理 2 2 4进程同步2 5管程机制2 6进程通信 2 4进程的同步 在多道程序系统中 由于资源共享或进程合作 使进程间形成间接相互制约和直接相互制约关系 这需要用进程互斥与同步机制来协调两种制约关系 进程同步的主要任务是使并发执行的进程间有效的共享资源和相互合作 进程的同步机制 信号量及P V操作 解决进程同步互斥问题 直接作用 相互合作 进程间的相互联系是有意识的安排的 直接作用只发生在相交进程间间接作用 资源共享 进程间要通过某种中介发生联系 是无意识安排的 可发生在相交进程之间 也可发生在无关进程之间 1 进程间的关系 2 进程的同步 直接作用 指系统中多个进程中发生的事件存在某种时序关系 需要相互合作 共同完成一项任务 具体说 一个进程运行到某一点时要求另一伙伴进程为它提供消息 在未获得消息之前 该进程处于等待状态 获得消息后被唤醒进入就绪状态 由于各进程要求共享资源 而有些资源需要互斥使用 因此各进程间竞争使用这些资源 进程的这种关系为进程的互斥 临界资源 系统中某些资源一次只允许一个进程使用 称这样的资源为临界资源或互斥资源或共享变量 3 进程的互斥 间接作用 4 基本概念 进程互斥 指在多道程序环境下 每次只允许一个进程对临界资源进行访问 进程同步 指多个相关进程在执行次序上的协调 临界资源 一次仅供一个进程使用的资源 在进程中涉及到临界资源的程序段叫临界区多个进程的临界区称为相关临界区 5 使用互斥区的原则 空闲让进 当无进程在互斥区时 任何有权使用互斥区的进程可进入忙则等待 不允许两个以上的进程同时进入互斥区有限等待 任何进入互斥区的要求应在有限的时间内得到满足让权等待 处于等待状态的进程应放弃占用CPU 以使其他进程有机会得到CPU的使用权 使用互斥区的原则 前提 任何进程无权停止其它进程的运行进程之间相对运行速度无硬性规定进程互斥的解决有两种做法 由竞争各方平等协商引入进程管理者 由管理者来协调竞争各方对互斥资源的使用具体方法 硬件 当一个进程进入临界区 就屏蔽所有中断 但成本高 软件 用编程解决 但常常忙等待 进程的同步机制 信号量及P V操作 解决进程同步 同步机制 信号量及P V操作 管程 条件临界域 路径表达式等 用于集中式系统中 会合 通信顺序进程 分布进程 远程过程调用等 适用于分布式系统中 信号量机制 信号量机制是一种卓有成效的进程同步工具 被广泛应用于单处理机和多处理机系统 以及计算机网络中 锁机制仅能表示 开 与 关 两种状态 开 关锁原语必须作为原子操作来进行 关锁原语言中反复测试 状态 浪费了处理机的时间 锁机制只能解决互斥 不能用于同步 信号量同步机制能完满地解决上述问题 信号量 semaphore 是一个数据结构定义如下 strucsemaphore intvalue pointer PCBqueue 信号量说明 semaphores P操作 P s s value s value if s value 0 该进程状态置为等待状态将该进程的PCB插入相应的等待队列末尾s queue 操作 意味着请求分配一个单位资源 V操作 V s s value s value if s value 0 唤醒相应等待队列s queue中等待的一个进程改变其状态为就绪态并将其插入就绪队列 操作 意味着释放一个单位资源 P V操作为原语操作原语 是由若干多机器指令构成的完成某种特定功能的一段程序 具有不可分割性 即原语的执行必须是连续的 在执行过程中不允许被中断实现 开关中断 信号量的使用 必须置一次且只能置一次初值初值不能为负数只能执行P V操作 用P V操作解决进程间互斥问题 互斥例子 三个进程共用两个I O缓冲区 解 设用信号量S表示共享资源 S初始值为2 同步例子 有A B两进程 A进程从卡片机读信息入缓冲区 B进程负责加工读进缓冲区的卡片解 设信号量S1 缓冲区中有否可供加工的信息 初始值为0 信号量S2 缓冲区是否为空 初始值为1 同步例子 续 在输入进程A中 可以把P S2 调到V S1 后面 而把信号量S2的初始值设为0 用P V操作描述前趋关系的例子 信号量还可以描述程序或语句之间的前趋关系 用P V操作描述前趋关系 续 描述如下 Vara b c d e f g semaphore 0 0 0 0 0 0 0 beginparbeginbeginS1 V a V b end beginP a S2 V c V d end beginP b S3 V e end beginP c S4 V f end beginP d S5 V g end beginP e P f P g S6 end parendend 经典的生产者 消费者问题 消费者 生产者 经典的生产者 消费者问题 同步问题 P进程不能往 满 的缓冲区中放产品 设置信号量为S1Q进程不能从 空 的缓冲区中取产品 设置信号量S2 S1初值为1 S2初值为0 P Q while true while true 生产一个产品 P s2 P s1 从缓冲区取产品 送产品到缓冲区 V s1 V s2 消费产品 生产者 消费者问题 生产者 消费者 Producer Consumer 问题是著名的进程同步问题 它描述一组生产者向一组消费者提供消息 它们共享一个有界缓冲池 生产者向其中投放消息 消费者从中取得消息 以下用信号量解决生产者 消费者问题 假设缓冲池中有n个缓冲区 每个缓冲区存放一个消息 可利用互斥信号量mutex使诸进程对缓冲池实现互斥访问 利用empty和full计数信号量分别表示空缓冲及满缓冲的数量 又假定这些生产者和消费者互相等效 只要缓冲池未满 生产者可将消息送入缓冲池 只要缓冲池未空 消费者可从缓冲池取走一个消息 生产者 消费者问题 续 其中 mutex empty full的初始值分别为1 n 0 P操作的顺序可换吗 P V操作讨论 1 信号量的物理含义 S 0表示有S个资源可用S 0表示无资源可用S 0则 S 表示S等待队列中的进程个数P S 表示申请一个资源V S 表示释放一个资源 信号量的初值应该大于等于02 P V操作必须成对出现 有一个P操作就一定有一个V操作当为互斥操作时 它们同处于同一进程当为同步操作时 则不在同一进程中出现如果P S1 和P S2 两个操作在一起 那么P操作的顺序至关重要 一个同步P操作与一个互斥P操作在一起时同步P操作在互斥P操作前而两个V操作无关紧要 P V操作的优缺点 P V操作优点 简单 而且表达能力强 用P V操作可解决任何同步互斥问题 缺点 不够安全 P V操作使用不当会出现死锁 遇到复杂同步互斥问题时实现复杂 8 信号量集 AND型信号量集 AND型信号量集是指同时需要多种资源且每种占用一个时的信号量操作AND型信号量集的基本思想 在一个原语中申请整段代码需要的多个临界资源 要么全部分配给它 要么一个都不分配AND型信号量集P原语为SwaitAND型信号量集V原语为Ssignal Swait S1 S2 Sn P原语 while TRUE if S1 1 Ssignal S1 S2 Sn for i 1 i n i Si 释放占用的资源 for 在Si queue中等待的每一个进程P 检查每种资源的等待队列的所有进程 从等待队列Si queue中取出进程P if 判断进程P是否通过Swait中的测试 注 与signal不同 这里要进行重新判断 通过检查 资源够用 时的处理 进程P进入就绪队列 else 未通过检查 资源不够用 时的处理 进程P进入某等待队列 9 一般 信号量集 一般信号量集是指同时需要多种资源 每种占用的数目不同 且可分配的资源还存在一个临界值时的信号量处理一般信号量集的基本思路就是在AND型信号量集的基础上进行扩充 在一次原语操作中完成所有的资源申请 进程对信号量Si的测试值为ti 表示信号量的判断条件 要求Si ti 即当资源数量低于ti时 便不予分配 占用值为di 表示资源的申请量 即Si Si di 对应的P V原语格式为 Swait S1 t1 d1 Sn tn dn Ssignal S1 d1 Sn dn 一般 信号量集 可以用于各种情况的资源分配和释放 几种特殊情况 Swait S d d 表示每次申请d个资源 当少于d个时 便不分配Swait S 1 1 表示互斥信号量Swait S 1 0 可作为一个可控开关 当S 1时 允许多个进程进入临界区 当S 0时 禁止任何进程进入临界区 思考题 1 用P V操作解决下图之同步问题 get copy put f s t g 用P V操作解决司机与售票员的问题 10 经典问题 1 读者写者问题有两组并发进程 读者和写者 共享一组数据区要求 允许多个读者同时执行读操作不允许读者 写者同时操作不允许多个写者同时操作 第一类 读者优先 如果读者来 1 无读者 写者 新读者可以读2 有写者等 但有其它读者正在读 则新读者也可以读3 有写者写 新读者等如果写者来 1 无读者 新写者可以写2 有读者 新写者等待3 有其它写者 新写者等待 第一类读者写者问题的解法 读者 while true P mutex readcount if readcount 1 P w V mutex 读P mutex readcount if readcount 0 V w V mutex 写者 while true P w 写V w 第一类读者写者问题的解法 一般信号量集 读者 swait wmutex 1 1 rcount R 0 写 ssignal wmutex 1 写者 swait rcount 1 1 wmutex 1 0 写 ssignal rcount 1 2 哲学家就餐问题 有五个哲学家围坐在一圆桌旁 桌中央有一盘通心粉 每人面前有一只空盘子 每两人之间放一只筷子每个哲学家的行为是思考 感到饥饿 然后吃通心粉为了吃通心粉 每个哲学家必须拿到两只筷子 并且每个人只能直接从自己的左边或右边去取筷子 defineN5voidphilosopher inti while true 思考 取fork i 取fork i 1 5 进食 放fork i 放fork i 1 5 为防止死锁发生可采取的措施 最多允许4个哲学家同时坐在桌子周围仅当一个哲学家左右两边的筷子都可用时 才允许他拿筷子 给所有哲学家编号 奇数号的哲学家必须首先拿左边的筷子 偶数号的哲学家则反之为了避免死锁 把哲学家分为三种状态 思考 饥饿 进食 并且一次拿到两只筷子 否则不拿 3 第二类读者写者问题 写者优先条件 1 多个读者可以同时进行读2 写者必须互斥 只允许一个写者写 也不能读者写者同时进行 3 写者优先于读者 一旦有写者 则后续读者必须等待 唤醒时优先考虑写者 第二章进程管理2 5管程机制 1 管程的提出 采用P V同步机制来编写并发程序 对于共享变量及信号量变量的操作将被分散于各个进程中缺点 易读性差 因为要了解对于一组共享变量及信号量的操作是否正确 则必须通读整个系统或者并发程序 不利于修改和维护 因为程序的局部性很差 所以任一组变量或一段代码的修改都可能影响全局 正确性难以保证 因为操作系统或并发程序通常很大 要保证这样一个复杂的系统没有逻辑错误是很难的 2 管程概念 概念 指关于共享资源的数据及在其上操作的一组过程或共享数据结构及其规定的所有操作 系统按资源管理的观点分解成若干模块 用数据表示抽象系统资源 同时分析了共享资源和专用资源在管理上的差别 按不同的管理方式定义模块的类型和结构 使同步操作相对集中 从而增加了模块的相对独立性 3 管程的组成 管程的四个组成部分 名称数据结构说明对该数据结构进行操作的一组过程 函数初始化语句局部于管程的数据结构 仅被局部于管程的过程访问 局部于管程的过程 也仅能访问管程内的数据结构 管程 相当于围墙 把共享变量和对它进行操作的若干过程围起来 管程 一种同步机制系统按资源管理的观点分解成若干模块 用数据表示抽象系统资源 同时分析了共享资源和专用资源在管理上的差别 按不同的管理方式定义模块的类型和结构 使同步操作相对集中 从而增加了模块的相对独立性 管程的形式TYPEmonitor name MONITOR 共享变量说明define本管程内所定义 本管程外可调用的过程 函数 名字表use本管程外所定义 本管程内将调用的过程 函数 名字表PROCEDURE过程名 形参表 过程局部变量说明 BEGIN语句序列 END FUNCTION函数名 形参表 值类型 函数局部变量说明 BEGIN语句序列 END BEGIN共享变量初始化语句序列 END 模块化 一个管程是一个基本程序单位 可以单独编译抽象数据类型 管程是一种特殊的数据类型 其中不仅有数据 而且有对数据进行操作的代码信息掩蔽 管程是半透明的 管程中的外部过程 函数 实现了某些功能 管程中的外部过程 函数 实现了某些功能 至于这些功能是怎样实现的 在其外部则是不可见的 4 管程的三个主要的特性 管程中的共享变量在管程外部是不可见的 外部只能通过调用管程中所说明的外部过程 函数 来间接地访问管程中的共享变量为了保证管程共享变量的数据完整性 规定管程互斥进入管程通常是用来管理资源的 因而在管程中应当设有进程等待队以及相应的等待及唤醒操作 5 管程的要素 问题 多个进程出现在管程中当一个进入管程的进程执行等待操作时 它应当释放管程的互斥权 当一个进入管程的进程执行唤醒操作时 如 唤醒 管程中便存在两个同时处于活动状态的进程处理方法有三种 等待 继续 直到 退出或等待 等待 继续 直到 等待或退出规定唤醒为管程中最后一个可执行的操作 因为管程是互斥进入的 所以当一个进程试图进入一个巳被占用的管程时它应当在管程的入口处等待 因而在管程的入口处应当有一个进程等待队列 称作入口等待队列如果进程 唤醒进程 则 等待 继续 如果进程 在执行又唤醒进程 则 等待 继续 如此 在管程内部 由于执行唤醒操作 可能会出现多个等待进程 因而还需要有一个进程等待队列 这个等待队列被称为紧急等待队列 它的优先级应当高于入口等待队列的优先级 由于管程通常是用于管理资源的 因而在管程内部 应当存在某种等待机制 当进入管程的进程因资源被占用等原因不能继续运行时使其等待 为此在管程内部可以说明和使用一种特殊类型的变量 称作条件变量 VARC condition 对于条件型变量 可以执行wait和signal操作 wait c 如果紧急等待队列非空 则唤醒第一个等待者 否则释放管程的互斥权 执行此操作的进程的PCB入c链尾部signal c 如果c链为空 则相当于空操作 执行此操作的进程继续 否则唤醒第一个等待者 执行此操作的进程的PCB入紧急等待队列的尾部 两个主要途径 直接构造 效率高 间接构造 即用某种已经实现的同步机制去构造例子 用P V操作构造管程 6 管程的实现 1 设置进程和管程的目的不同 2 系统管理数据结构进程 PCB管程 等待队列 3 管程被进程调用 4 管程是操作系统的固有成分 无创建和撤消 7 管程和进程的异同点 第二章进程管理2 6进程通信 1 进程通信概述 P V操作实现的是进程之间的低级通讯 所以P V为低级通讯原语 它只能传递简单的信号 不能传递交换大量信息如果要在进程间传递大量信息则要用Send Receive原语 高级通讯原语 2 实现进程通信的方式 共享存储器方式 相互通信的进程通过共享某些数据结构或存储区来进行通信 可分为共享数据结构方式 共享存储区方式 消息通信方式 进程间的消息交换以消息或报文为单位 程序员利用一组通信命令 原语 来实现通信 可分为直接 间接通信方式 共享文件方式 利用共享文件来实现进程间的通信 3 管道通信 在UNIX系统中 利用一个打开的共享文件来连接两个相互通信的进程 该共享文件称为管道 Pipe 因而该方式又称为管道通信 为了协调双方通信 管道通信必须提供三方面的协调能力 互斥 同步 对方是否存在 4 消息传递模式 系统为进程提供了两个高级通讯原语send和receive 要进行消息传递时执行send 当接收者要接收消息时执行receive消息缓冲 在内存中开设缓冲区 发送进程将消息送入缓冲区 接收进程接收传递来的缓冲区信箱通信 5 直接方式 共享文件模式 管道通信发送进程发消息时要指定接收进程的名字 反过来 接收时要指明发送进程的名字Send receiver message Receiver sender message 对称形式 一对一非对称形式 多对一 顾客 服务员 有缓冲 有界 无界 无缓冲 直接通信方式 直接通信方式模型 6 消息缓冲 有界缓冲区 在操作系统空间设置一组缓冲区 当发送进程需要发送消息时 执行send系统调用 产生自愿性中断 进入操作系统 操作系统为发送进程分配一个空缓冲区 并将所发送的消息从发送进程copy到缓冲区中 然后将该载有消息的缓冲区连接到接收进程的消息链链尾 如此就完成了发送过程 发送进程返回到用户态继续执行 在以后某个时刻 当接收进程执行到receive接收原语时 也产生自愿性中断进入操作系统