第二章进程及其管理2.1作业.ppt

主讲 刘拥民Lym37212004 广义 处理机调度分类 在大型通用系统中 可能有数百个批处理作业存放在磁盘的作业队列中 有数百个终端同主机相联接 因此如何从这些作业中挑选作业进入主存运行 如何在作业或进程间分配处理等 问题无疑是操作系统的资源管理功能中的一个重要问题 本章主要讨论处理机分配问题 处理机调度 引论作业和进程的调度 广义 处理机调度分类 A 一般来说 处理机调度可以分成三级 生活中实例 淘汰竞赛 分成初赛 复赛 决赛 最终才能决定谁是冠军 高级调度 作业调度 其主要功能是按照某种原则从磁盘某些盘区的作业队列中选取作业进入主存 并为作业做好运行前的准备工作和作业完成后的善后工作 高级调度 高级调度 作业调度 长程调度 每次执行高级调度时 都需决定 1 接纳多少个作业 取决于多道程序度 即允许有多少作业同时在内存中运行 2 接纳哪些作业 取决于所采用的调度算法 常用的调度算法为 先来先服务调度 SJF算法 2种方式 中级调度 中级调度 中程调度 交换调度 它负责进程在内存和辅存对换区之间的对换 主要涉及内存管理和扩充 2 中级调度 它决定哪些进程被允许参与竞争处理机资源 中级调度主要只是起到短期调整系统负荷的作用 以平顺系统的操作 实现方法就是 挂起 中级调度将进程暂时移到辅存对换区 解除挂起 中级调度将满足等待条件的进程从辅存中调入内存 中级调度的图示说明 3 低级调度 进程调度 就是按照某种原则将处理机分配给就绪进程 由进程调度程序实现处理机在进程间的转换 它必须常驻主存 是操作系统内核的主要部分 3 2 2低级调度 低级调度 进程 短程调度 它决定就绪队列中的哪个进程获得处理机 然后由分派程序执行把处理机分配给该进程的操作 进程调度是最基本的调度方式 三级调度的图示说明 RUN readya blockeda readys blokeds 后备 完成 作业后备状态 执行 内存 时间片到 I O请求 I O完成 高级调度 作业调度 挂起 解挂 挂起 解挂 进程调度 低级调度 中级调度 处理机调度分类B 处理机的二级调度 宏观上 作业调度微观上 进程调度 事实上 进入计算机系统的作业只有经过两级调度后才能占用处理器 第一级是作业调度 使作业进入主存储器 第二级是处理器 特指进程 调度 使作业进程占用处理器 作业调度与处理器 特指进程 调度的配合能实现多道作业的同时执行 作业调度与进程调度的关系 第二章作业管理和用户接口 2 1作业组织和控制2 2作业管理举例2 3系统调用 SYSTEMCALL 2 4图形用户接口 GUI GRAPHICUSERINTERFACE 在这一章中 我们讨论OS向上提供的用户接口 即系统命令接口和系统调用接口 系统命令接口可完成用户作业的组织和控制 2 1 1作业和作业处理过程 1 作业的概念2 作业的组成3 作业的处理过程4 作业输入方式5 作业控制表 JCB JobControlBlock 一 作业 作业步 作业 是用户在一次上机活动中 要求计算机系统所做的一系列工作的集合 也称作任务 作业步 一个作业的处理过程中 计算机所做的相对独立的工作 实例 一个用高级语言写的用户作业 它的运行要分成三步 先编译 再连接 最后运行 1 作业的概念 一个作业是指在一次应用业务处理过程中 从输入开始到输出结束 用户要求计算机所做的有关该次业务处理的全部工作 用户的观点 在一次业务处理过程中 从输入程序和数据到输出结果的全过程 作业步 形成中间结果文件 系统的观点 针对作业进行资源分配 作业由程序及数据 作业体 和作业说明书 作业控制语言 作业由不同的顺序相连的作业步组成 2 作业的组成 作业说明书包括作业基本情况 作业控制 作业资源要求的描述 它体现用户的控制意图 如 预计运行时间 要求的资源情况 执行优先级等 作业基本情况 用户名 作业名 编程语言 最大处理时间等 作业控制描述 作业控制方式 作业步的操作顺序 作业执行出错处理 作业资源要求描述 处理时间 优先级 内存空间 外设类型和数量等 作业由程序 数据和作业说明书三部分组成 5 作业控制表 JCB JobControlBlock 作业名估计执行时间优先数 用于调度 作业说明书文件名程序类型 需调用的系统程序 资源要求 静态 或中间可以随作业步变化 效率不高 动态分配作业状态 提交 后备 执行 就绪 等待 完成 在运行过程中 系统对作业进行管理的必要信息 作业控制块 JCB JobControlBlock 每个作业进入系统时由系统为其建立一个作业控制块JCB JobControlBlock 它是存放作业控制和管理信息的数据结构 主要信息见右图 2 1 3作业控制语言 1 命令行2 环境变量 脱机作业控制 用户输入作业说明书 整个作业的运行由系统控制 联机作业控制 通过人 机会话方式控制作业运行 用户登录 控制台登录或远程登录 由系统自动执行一些命令脚本后 并进入shell 字符或GUI界面 接受用户的命令和操作 最后退出系统 5 1作业的状态与处理流程 一 作业状态 作业从提交给系统直到它完成后离开系统前的整个活动常划分为若干阶段 作业在每一阶段中所处的状况称为作业的状态 系统中的作业通常分为四种状态 1 提交状态 一个作业被提交给机房后或用户通过终端键盘向计算机中键入其作业时所处的状态为提交状态 2 后备状态 作业的全部信息都已通过输入机输入 并由操作系统将其存放在磁盘的某些盘区中等待运行 则称为后备状态 3 运行状态 作业一旦被作业调度程序先中而被送入主存中投入运行 称之为运行状态 4 完成状态 作业完成其全部运行 释放出其所占用的全部资源 准备退出系统的作业状况称为完成状态 3 作业的处理过程 作业提交 作业的输入 作业执行 先到 就绪 经调度 运行 有I O请求 等待 I O完成到 就绪 作业完成 作业的输出 4 作业输入方式 无通道处理方式 联机 降低了CPU效率 由主机直接控制输入 输出 I O与作业处理不能并行 脱机 人工干预 通过磁带或磁盘在外围处理机与主机之间交换作业 需人工移动 用于主机不太快的情况 直接耦合 通过共享外存在外围处理机与主机之间交换作业 用于高速主机 有通道处理 输入 输出由主机和通道来承担 假脱机 spooling SimultaneouslyPeripheralOperationOnLine 系统把作业处理的全过程划分为相对独立的三个部分 输入流 处理流和输出流 spooling in spooling out进程 控制输入 输出 网络 在网络上一台机器进行作业输入 输出 在另一台主机上运行 2 5 5选择调度算法的原则 l 资源利用率CPU利用率 CPU有效工作时间 CPU总的运行时间 CPU总的运行时间 CPU有效工作时间 CPU空闲等待时间 2 响应时间 交互式进程从提交一个请求 命令 到接收到响应之间的时间间隔称响应时间 使交互式用户的响应时间尽可能短 或尽快处理实时任务 这是分时系统和实时系统衡量调度性能的一个重要指标 3 周转时间 批处理用户从作业提交给系统开始 到作业完成为止的时间间隔称作业周转时间 应使作业周转时间或平均作业周转时间尽可能短 这是批处理系统衡量调度性能的一个重要指标 6 2 3调度性能的衡量 二 调度性能的衡量 尽量缩短周转时期 通常采用平均周转时间和带权平均周转时间作业的周转时间 ti tci tsiti 作业周转时间tci 作业完成时间tsi 作业提交时间 6 2 3调度性能的衡量 4 吞吐率单位时间内处理的作业数 5 公平性确保每个用户每个进程获得合理的CPU份额或其他资源份额 不会出现饿死情况 3 3常用调度算法 FIFO调度算法SJF调度算法 HRN调度算法 RR算法 3 3 1 先来先服务调度 FIFO Firstinfirstout 先来先服务 FCFS 按照作业进入系统的先后次序进行调度 先进入系统者先调度 即启动等待时间最长的作业 FIFO算法是不可抢占策略 优点 实现简单 公平缺点 没考虑资源利用率和作业的特殊性 FIFO 算法实例 注 约定表中数据为十进制 因为FIFO算法是按作业到达时间的先后而决定运行的先后 所以运行顺序为1 2 3 4 计算方法为 周转时间Ti 结束时间 时间到达 加权周转时间Wi 周转时间 运行时间 FIFO算法的周转时间 作业 提交时间 运行时间 开始时间 完成时间 周转时间 带权周本 ts 时 tR 时 tB 时 tC 时 ti 时 Wi Z 1234 8 008 509 009 50 2 000 500 100 20 8 0010 0010 5010 60 10 0010 5010 6010 80 2 002 001 601 306 90 1 004 0016 006 5027 50 平均周转时间T 6 90 4 1 725 小时 平均带权时间W 27 5 4 6 875 对FIFO算法的评价 这种算法按先来后到原则调度 比较公平 但是不利于短作业 此算法有利于CPU繁忙型作业 而不利于I O繁忙型作业 CPU繁忙型作业 指CPU进行处理时 不需频繁的请求I O 而每次I O的操作时间又很短 I O繁忙型作业 指该类作业无需大量的CPU时间进行计算 但要频繁地请求I O 3 3 2 短作业优先调度算法 SJF shortestjobfirst SJF 对短作业或短进程优先调度的算法 SJF算法可照顾短作业 使它能比长作业优先执行 该调度算法一个非抢占的策略 它一旦选中某个短作业后 就保证该作业尽可能快地完成运行并退出系统 运行中不允许被抢占 结论 假设系统中所有作业同时到达 可以证明采用SJF能得到最短的作业平均周转时间 SJF 算法实例 注 约定表中数据为十进制 按照SJF算法 调度顺序应为J1 因为8点钟的时候 仅有这一个作业 J3 J4 J2 计算方法为 周转时间Ti 结束时间 时间到达 加权周转时间Wi 周转时间 运行时间 SJF算法的周转时间 ts tR tB Ti Wi 1234 8 008 509 009 50 2 000 500 100 20 8 0010 3010 0010 10 2 002 301 100 806 20 1 004 6011 004 0020 60 T 1 55W 5 15优 比FCFS TW缺 有的作业始终得不到运行 tc 10 0010 8010 1010 30 对SJF算法的评价 优点 是有利于短作业 易于实现 强调了资源的充分利用 保证了系统的最大吞吐量 单位时间里处理作业的个数 改善调度性能 缺点 1 对长作业不利 2 完全没考虑作业的紧迫程度 不能保证紧迫作业会得到及时处理 3 由于作业的长短只根据用户提供的估计执行时间而定 而用户又有可能会有意无意的缩短其作业的估计执行时间 致使该算法不一定能真正做到短作业优先调度 实例比较 FCFS算法和SJF算法 3 3 3 最高响应比调度算法 HRN HighestResponseratio next 非抢占的调度策略 响应比最高的作业优先启动 它能保证任何作业都不会被无限延迟 作业的动态响应比计算公式如下 响应比 等待时间 估计运行时间 估计运行时间优点 公平 吞吐率大缺点 增加了计算 增加了开销 HRN 算法实例 注 约定表中数据为十进制 按照HRN算法 调度顺序应为J1 因为8点钟的时候 仅有这一个作业 J3 J2 J4 计算方法为 周转时间Ti 结束时间 时间到达 加权周转时间Wi 周转时间 运行时间 HRN算法的周转时间 6 响应比高者优先 HRN 算法 响应比 上题 顺序1 3 2 4 1234 8 008 509 009 50 2 000 500 100 20 8 0010 1010 1010 60 10 0010 6010 1010 80 2 002 101 101 306 50 1 004 2011 006 5022 7 T 1 625 W 5 675 响应比的计算 第一步 第二步 对HRN算法的评价 1 该算法有利于短作业 2 当要求服务时间相同时作业的响应比决定于其等待时间 因而实现了先来先服务 故对长作业也不歧视 当长作业的等待时间足够长时 其响应比便可升到最高 从而获得处理机 该算法是FCFS和SJF的结合 克服了两种算法的缺点 3 3 4 时间片轮转算法 RR rotaterun 一种剥夺式的调度算法 主要用于进程调度 当执行的时间片用完时 由一个计时器发出时钟中断 调度程序便据此信号来停止该进程的执行 然后该处理机分配给就绪队列中新的队首进程 同时也保证它执行一个时间片 这就保证就绪队列中的所有进程在一定的时间内均能获得一个时间片的处理机执行时间 注意 在进程执行期间 虽然时间片未到期 但是由于自身的原因 比如 因为要启动I O 或者要等待某种信号 或者由于程序自身出现异常而无法继续执行时 这种算法也立即启动抢占CPU并切换给其它进程 2 优先级调度算法 按照进程的优先级大小来调度 使高优先级进程得到优先的处理的高度策略称为优先级调度算法 但在许多采用优先级调度的系统中 通常采用动态优先数策略 进程的优先级不是固定的 往往随许多因素的变化而变化 尤其随作业 进程 的等待时间 已使用的处理机时间或其它资源的使用情况而定 优先级调度方法又可分为 非抢占的优先级调度法 即一旦某个高优先级的进程占有了处理机 就一直运行下去 直到由于其自身的原因而主动让出处理机时 任务完成或等待事件 才让另一高优先级进程运行 可抢占的优先级调度法 任何时刻都严格按照高优先级进程在处理机上运行的原则进行进程的调度 其他作业调度方