11 处理机管理

2 2处理机管理 进程的概念进程的控制进程的调度进程的互斥与同步进程的通信死锁 多道程序系统 程序A 程序B OS调度 I OA I OB t1 t2 如何把CPU合理地分配给某个需要的程序 并在其用完后予以回收 合理利用及减少开销 分配 回收 处理机管理的核心问题 CPU 2 2 1进程的概念一 程序与进程 程序 由若干条具有一定功能的机器指令所组成的解题顺序和步骤 顺序执行 单道系统 并发执行 多道系统 顺序性 封闭性 可再现性 程序执行严格按照一定顺序 不受外界因素影响 结果只由初始条件决定 相互约束 资源争夺与共享 程序执行是相互交替穿插进行 执行次序每次变化 受外界影响 结果与速度有关 前驱图 有向无环图节点 表示一条语句 或一段程序有向线段 表示语句之间的顺序关系无环 当程序中出现循环时 一般将整个循环作为一个节点 a1 5 b1 a1 5 print b1 I1 C1 P1 Input Calculate Print 前驱图 a1 5 b1 a1 5 print b1 a3 5 b3 a3 10 print b3 a2 5 b2 a2 6 print b2 I1 C1 P1 程序1 程序2 程序3 I2 C2 P2 I3 C3 P3 程序1 程序2 程序3 I1 输入 处理机 打印机 I2 C1 I3 C2 P1 C3 P2 t1 t2 t3 t4 t7 程序顺序执行 t5 t6 t8 P3 t9 I1 P3 输入 处理机 打印机 t1 t2 t3 t4 t5 由于多道程序中IK CJ与PL之间不存在前趋关系 程序之间可以并发执行 程序顺序执行与并发执行例 顺序执行 t2 t1 t3 t4 t5 t6 顺序执行 结果 y 5y 6 并发执行 一 并发执行 t2 t1 t3 t4 t5 t6 结果 y 3y 3 并发执行 二 并发执行 t2 t1 t3 t4 t5 t6 结果 y y 3 可见 程序的概念已无法描述动态执行过程中的并发活动 解决办法 引入进程来描述程序的一次执行 使并发执行的程序保持 可再现性 进程包括 执行现场的保留 资源的分配情况 程序的执行位置等 进程的定义 进程是可并发执行的程序在给定数据集合上的一次执行过程 是系统进行资源分配和调度的一个独立的基本单位和实体 是指执行一个映象程序的总环境 1 程序是指令的集合 是静态概念 进程是程序的执行过程 是动态概念 2 程序可作为软件资源长期保存 进程只是一次短暂活动或过程 3 一个程序可对应多个进程 一个进程可包含多段程序 程序与进程比较 二 进程的特征 动态性 并发性 独立性 异步性 具备生命周期 可以被建立 挂起 撤销 进程执行时间时间重叠 资源分配的基本单位 相对独立 速度不可预知 走走停停 三 进程的描述 进程的结构 进程控制块 ProcessControlBlock 操作系统用来描述进程执行情况和状态变化的一种专门数据结构 内容 调度信息和现场信息 典型的进程控制块PCB结构 进程标识符 进程状态 CPU现场 程序状态字 寄存器内容等 资源清单 优先级 队列指针 家族关系 通信机制 信箱或消息队列 同步机制 信号量 存储位置 一串数值 供计算机系统使用 PCB的作用 PCB可唯一标识一个进程PCB中的信息为进程的控制提供依据PCB将程序变成了进程PCB是进程在系统中存在的唯一标志 PCBs的组织方式 系统如何管理多个进程的 将各进程的PCB以一定的方式组织起来 链接方式 索引方式 1 2 4 10 15 四 进程的三种基本状态 就绪状态 Ready 执行状态 Executing 等待状态 Wait 获得了除了CPU外的一切所需资源 具备执行条件 占有CPU 正在执行 唯一的 因等待某种事件而暂时不能执行 进程状态的转换 新进程 就绪 执行 结束 阻塞 接纳 进程调度 中断或时间片用完 完成 I O请求或等待某事件 I O完成或事件发生 状态转换原因图 状态转换执行图 新进程 就绪 执行 结束 阻塞 进入就绪队列 分配CPU使用权 强制放弃CPU回到就绪队列 释放所有资源 进程主动放弃CPU进入阻塞等待队列 进程被释放回到就绪队列 进程状态转换归纳 新进程 就绪状态 事件 动作 接纳 进入就绪队列 就绪 执行 进程调度 分配CPU 执行 结束 完成 释放资源 执行 阻塞 时间片到时高优先中断 系统剥夺CPU 执行 就绪 I O请求等待某事件 进程放弃CPU进入阻塞等待队列 阻塞 就绪 阻塞事件释放 进程进入就绪队列 注意 执行 就绪 进程从执行态到阻塞态是主动的进程发现需要等待某一事件 主动向系统申请进入阻塞态进程从阻塞态到就绪态是被动的当系统 或其它进程 发现阻塞进程阻塞的条件已释放 向系统申请将该阻塞进程置为就绪态 2 2 2进程的控制 进程的控制 控制进程在其生命周期的各种活动及状态转换 通过操作系统的原语 primitive 来实现 原语 用以完成特定功能的不可分割的一段程序 原语的执行过程是不可中断的 创建原语 撤销原语 阻塞原语 唤醒原语 一 创建原语 实质是创建进程控制块 进程创建步骤 二 撤销原语 进程撤销步骤 进程完成任务或异常中断 三 阻塞原语 阻塞 执行 阻塞原语 引发阻塞的事件 启动I O操作 等待新数据 无工作可做 请求系统服务 进程阻塞步骤 四 唤醒原语 就绪 等待 唤醒原语 引发唤醒的事件 服务完成 新数据到达 新任务下达 I O操作完成 进程唤醒步骤 2 2 3进程的调度 含义 目的 对象 处理机调度 为各个进程分配处理机 使每个进程都能合理的使用处理机 得到及时的响应 处于就绪队列的进程 进程调度的任务是控制协调进程对CPU的竞争 即按一定的调度算法从就绪队列中选中一个进程 把CPU的使用权交给被选中的进程 一 进程调度的原因 进程执行完毕 进程等待某个事件阻塞 进程的时间片用完 有新进程 高优先级或其他 进入就绪队列 剥夺式 抢占式 非剥夺式 非抢占式 系统按照某种原则剥夺现行进程的CPU使用权 并交给其他进程 现行进程的CPU使用权无法剥夺 除非由于时间片完或者进程自身原因才能交出CPU使用权 高优先权 短进程 二 进程调度的方式 三 进程调度的功能 记录系统中各进程的执行情况和环境状态 以便在处理机空闲的时候选择合适的进程执行 选择合适的调度算法以选择合适的进程执行 在执行 撤销 进程时装入 释放 PCB信息 四 进程调度的过程 记录进程的相关信息 选取适当的进程执行 为进程分配处理机 进程本身信息和环境信息 进程调度算法 恢复进程的现场信息 五 进程调度的算法 算法设计的准则 用户 周转时间 响应时间 优先权 系统 系统吞吐量 处理机效率 资源利用的平衡 截止时间 简单的调度算法 先来先服务算法 短进程优先 轮转法 等时间片轮转 不等时间片轮转 优先权法 抢占式优先权 非抢占式优先权 静态优先权 动态优先权 多级反馈队列算法 算法的分类 1 先到先服务 FCFS 算法 常用算法 按照就绪进程进入就绪队列的先后顺序调度 先进入先服务 2 短进程优先 SCBF 算法 按照就绪进程对系统服务时间的需求确定优先权 服务时间需求短的进程优先被调度 调度算法评价指标 周转时间 TT 进程第一次进入就绪队列到进程运行结束的时间间隔 TT 等待时间 WT 服务时间 ST 平均周转时间 ATT 系统各进程周转时间的平均值 ATT TT N 带权周转时间 QTT 进程周转时间与系统服务时间的比值 QTT TT 服务时间 平均带权周转时间 AQTT 例 AQTT QTT N 例 A请求系统服务时间5s B请求系统服务时间为100s 设第0到第5秒前 CPU运行C进程 第1秒时B进入系统内存 第2秒时A进入内存当CPU空闲 需要调度进程时根据不同的算法选择A或B 问 分别计算FCFS算法下和SCBF算法下 A和B的周转时间 带权周转时间和系统平均周转时间 B A FCFS算法 先来先服务A 周转时间为3 100 5 108s带权周转时间为108 5 20 4B 周转时间为4 100 104s带权周转时间为104 100 1 04平均带权周转时间为 20 4 1 04 2 10 72SCBF算法 短进程优先A 周转时间为3 5 8s带权周转时间为8 5 1 6B 周转时间为4 5 100 109s带权周转时间为109 100 1 09平均带权周转时间为 1 6 1 09 2 1 345 先调度B后调度A 先调度A后调度B 3 等时间片轮转 ERR 算法 按照FCFS算法从就绪队列调度调入进程 为每个进程分配相同的时间片 并执行 时间片完 进程执行完 调度下一个进程 时间片完 进程未执行完 进程进入就绪队尾 等待下一次调度 时间片选取原则 q 时间片大小 T 响应时间 N 就绪队列进程数 时间片选取过大或者过小有什么后果 应该按什么原则选取时间片 时间片长度公式 公平性的保证 响应及时性的保证 ERR优点 4 不等时间片轮转 ERR 算法 在保证及时响应的基础上 为不同的需求分配大小不等的时间片 降低周转时间 长进程 短进程 I O频繁型 CPU密集型 长时间片 短时间片 5 最高优先权 HPF 算法 按照就绪队列中进程的优先级进行调度 高优先级的进程优先被调度 优先级确定原则 进程类型 系统 用户 前台 后台 实时 一般 资源需求 需求小 需求大 到达时间 先到 后到 用户类型 用户自己确定 静态优先级算法 优先级算法 静态优先级算法 动态优先级算法 进程的优先级在进程创建时确定 不再更改 B 动态优先级算法 在创建进程时确定一个基本优先级 在进程执行过程中按照一定原则动态改变 就绪等待进程优先级随等待时间增加而升高 执行进程的优先级随CPU占用时间增加而下降 6 多级队列反馈算法 设置多个就绪队列 各队列优先级不同 从高优先级队列开始调度 采用时间片原则 高优先级队列调度完毕 继续调度下一优先级队列 注意 2 2 4进程的互斥与同步 进程的并发执行 资源的竞争 结果的不可再现 进程同步 目标 实现资源的有效共享 保证结果的可再现 进程间的同步关系例1 正常行车 到站停车 开车 售票 开车门 关车门 司机 售票员 合作 合作 进程间的同步关系例2 打印进程1 打印进程2 打印 打印 互斥 获得打印数据 获得打印数据 进程间的同步关系例3 计算进程 打印进程 计算结果送到Buffer 从Buffer中取数 Buffer 互斥 互斥 完成数据计算 打印 通知打印进程打印 通知计算进程送下一个数 合作 进程同步时面临的两种主要关系 相互合作 竞争资源 司机与售票员 多个打印者 计算者与打印者 进程的同步 多个进程通过执行时序上的某种限制 相互合作 而产生的制约关系 进程的互斥 由于多个进程共享同一资源而产生的相互制约的关系 同步机制 实现进程互斥与同步的机制 临界资源与临界区 以互斥关系共享的资源 一次 一个时刻 只允许一个进程访问 排他性 临界区 进程中访问临界资源的代码区 进程代码的组成 进入区 临界区 退出区 进入区 临界区 退出区 阻塞等待资源释放 改变资源状态 释放资源唤醒等待进程 进程1 进程2 同步机制应遵循的原则 空闲让进 忙则等待 有限等待 让权等待 无进程处于临界区 可让一新进程进入 有进程处于临界区 其余进程必须等待 进程进入临界区的要求必须在有限时间内满足 等待进入临界区的进程 其CPU占用必须释放 临界资源锁机制 为临界资源加一个 锁 锁变量Lock True资源在用 False资源空闲 每个进程必须按照以下过程操作临界资源 关锁 进入临界区 开锁 例 check if Lock 0 gotocheck elseLock 1 临界区 Lock 进程1 进程2 unlock Lock check if Lock 0 gotocheck elseLock 1 临界区 unlock Lock 临界资源锁的特点 关锁操作不可被打断 原语 例 引入TS指令 关锁操作在一个指令周期内完成 信号量与P V操作 信号量是对具体共享资源的抽象描述 信号量的值为整数 表示资源使用情况 不同共享资源可以用不同的信号量表示 P操作 申请分配一个资源 V操作 释放一个资源 信号量是比锁更高级的资源抽象方式 PV操作均是原语 1 信号量同步机制 通过信号量S和基于S的P V操作实现 S是资源的数目 2 用信号量实现互斥 实现了让权等待 P S 临界区 V S 进程1 进程2 P S 临界区 V S P S 访问资源 V S 状态 状态 唤醒 就绪 执行 就绪 执行 阻塞 司机进程 正常行车 到站停车 V S停车 喝茶 P S关车门 正常行车 售票 P S停车 开车门 关车门 V S关车门 售票 售票员进程 两个信号量初值均为0 3 用信号量实现同步 例1 计算进程 计算数据 P S空 数据入buffer V S满 P S满 从buffer取数据 V S空 打印进程 设一个信号量 S空代表buffer空 初值为 再设一信号量 S满代表buffer满 初值为 3 用信号量实现同步 例2 设2个信号量 S2 S3空代表buffer1和buffer2是否满再设2信号量 S1 S4代表buffer1和buffer2是否空初值分别为 S1 S4 1 S2 S3 0 3 用信号量实现同步 教材例2 P S1 将数据放入buf1 V S2 P S2 P S4 从buf1取数据并存入buffer2 V S1 V S3 P S3 从buf2取数据 V S4 进程get 进程copy 进程put 公用信号量 私用信号量 一组进程共享 都可进行P V操作 用于进程间资源的竞争 拥有信号量的进程只对信号量进行P操作 V操作由其他进程进行 用于进程间的合作 4 公用信号量与私用信号量 4 经典同步问题 生产者 消费者问题 Producer ConsumerProblems 问题描述 多个生产者生产产品多个消费者消费产品 进程使用资源进程释放资源 算法分析 生产者生产资源后消费者才能消费消费者消费后生产者才能将生产资源放入资源区 生产者和消费者对资源区的使用是互斥合作的关系 使用循环队列来实现资源区使用公共信号量控制资源区的互斥访问使用私用信号量控制生产者和消费者的合作 生产者 消费者 思考 信号量与P V操作总结 信号量S的初值应该大于等于0S 0表示有S个资源可用 S 0表示无资源可用 S 0则 S 表示S等待队列中的进程个数 P V操作必须成对出现 有一个P操作就一定有一个V操作 当实现互斥时 它们处于同一进程 当实现同步时 它们则不在同一进程中出现 如果两个P操作在一起 那么它们的顺序至关重要 一个同步P操作应在一个互斥P操作前 两个V操作顺序无关紧要 优点 简单 而且表达能力强 用P V操作可解决任何同步互斥问题 缺点 不够安全 P V操作使用不当会出现死锁 遇到复杂同步互斥问题时实现复杂 2 2 5进程的通信 进程的通信 并发执行的进程之间所进行的信息交换 进程通信 低级通信 高级通信 消息缓冲通信 管道通信 信箱通信 一 消息缓冲通信 1 系统管理空白缓冲区 2 发送者向系统申请空白缓冲区 4 发送者将填有消息的缓冲区挂到接收者的消息队列 5 接收者在适当时候从消息队列中读取数据 3 发送者向空白缓冲区填入信息 系统提供消息通信原语 Send Receive Send receiver m 申请缓冲区 P mutex 填入消息 消息插入消息队列 V mutex V sm Receive n P sm P mutex 取消息 释放缓冲区 V mutex Send原语 Receive原语 二 信箱通信 中间实体 信箱头 信箱名等相关信息 信箱体 传递的信息 三 管道通信 管道 连接接收进程和发送进程的共享文件 管道通信 两个进程之间利用共享文件进行信息交换 对于管道的读写是互斥访问的写后读 读后写的同步关系只有在管道双方都存在时才能通信 2 2 6进程的死锁 死锁 由于资源分配不当 造成多个进程阻塞而无法被唤醒继续执行的现象 死锁 死锁的原因 1 资源分配不当 2 进程推进顺序不对 产生死锁的必要条件 1 资源访问的互斥条件 进程 资源环形链 1 从资源出发的箭头表示已分配该资源 2 从进程出发的箭头表示进程正在申请资源 表示原则 进程1等待进程2占有的资源 资源2 进程2等待进程1占有的资源 资源1 形成了一个进程等待资源的环路 一 死锁的预防 方法1 破坏死锁产生的必要条件 预防死锁产生 1 破坏请求和保持条件 破坏部分分配条件 资源预分配 2 破坏不剥夺条件 阻塞进程释放所有的资源 3 破坏环路等待条件 资源按序分配 简单方便 利用率低 延迟大 效率高 复杂 开销大 资源利用率不高 可能有浪费 二 死锁的避免 方法2 资源预测分配 分配资源前 检查分配的安全性 系统状态不安全 不分配资源 系统状态安全 分配资源 安全状态 在当前的状态下 能找到一个正确的推进顺序满足所有的进程的资源需求 将它们推进完毕 安全状态检测 银行家算法假设本次分配 检测分配后的系统状态是否安全 例 条件P1 P2 P3三个进程对同类资源竞争 P1最大需要10个该资源 P2最大需要4个 P3为9个 该资源总数为12个 已知当前时刻 系统状态1 当前是否为安全状态2 若进程2提出2个资源需求是否可以分配3 若进程3提出2个资源需求是否可以分配 进程 最大需求 已分配 剩余 1 2 3 10 4 9 2 P2 P1 P3 3 1 2 4 5 0 5 10 10 存在一个正确的顺序推进进程 例 条件P1 P2 P3三个进程对同类资源竞争 P1最大需要10个该资源 P2最大需要4个 P3为9个 该资源总数为12个 已知当前时刻 系统状态1 当前是否为安全状态2 若进程2提出2个资源需求是否可以分配3 若进程3提出2个资源需求是否可以分配 进程 最大需求 已分配 剩余 1 2 3 10 4 9 2 P2 P1 P3 3 2 5 假设分配给2两个资源 1 4 P2 P1 P3 例 条件P1 P2 P3三个进程对同类资源竞争 P1最大需要10个该资源 P2最大需要4个 P3为9个 该资源总数为12个 已知当前时刻 系统状态1 当前是否为安全状态2 若进程2提出2个资源需求是否可以分配3 若进程