操作系统教程—Linux实例分析 孟庆昌 第3章 处理机调度.ppt

第3章处理机调度 3 1调度级别3 2作业调度3 3进程调度3 4性能评价标准3 5常用调度算法3 6Linux系统中的进程调度习题 3 1调度级别 一般来说 作业从进入系统到最后完成 可能要经历三级调度 高级调度 中级调度和低级调度 1 高级调度 又称作业调度 2 中级调度 为了使内存中同时存放的进程数目不至于太多 有时就需要把某些进程从内存中移到外存上 以减少多道程序的数目 为此设立了中级调度 3 低级调度 又称进程调度 其主要功能是根据一定的算法将CPU分派给就绪队列中的一个进程 3 2作业调度 3 2 1作业状态如前所述 作业从提交给系统 直到完成任务后退出系统前 在整个活动过程中它会处于不同的状态 通常 作业状态分为四种 提交 后备 执行和完成 如图3 1所示 图3 1作业的基本状态 1 提交状态 即用户向系统提交一个作业时 该作业所处的状态 2 后备状态 即用户作业经输入设备 如读卡机 送入输入井 磁盘 中存放 等待进入内存时所处的状况 3 执行状态 即作业分配到所需的资源 被调入内存 并且在处理机 CPU 上执行相应的程序时所处的状况 4 完成状态 即作业完成了计算任务 结果由打印机输出 最后由系统回收分配给它的全部资源 准备退出系统时的作业状况 3 2 2作业调度1 作业控制块 JCB 在多道批处理系统中通常有上百个作业被收容在输入井 磁盘 中 为了管理和调度作业 系统为每个作业设置了一个作业控制块 JCB 它记录该作业的有关信息 不同系统的JCB的组成内容有所区别 JCB的主要内容如图3 2所示 图3 2作业控制块 2 作业调度的功能如上所述 作业调度的主要任务是完成作业从后备状态到执行状态和从执行状态到完成状态的转换 具体来说 通常作业调度程序要完成以下工作 这就是作业调度的功能 1 记录系统中各个作业的情况 2 按照某种调度算法从后备作业队列中挑选作业 3 为选中的作业分配内存和外设等资源 4 为选中的作业建立相应的进程 5 作业结束后进行善后处理工作 如输出必要的信息 收回该作业所占用的全部资源 撤消与该作业相关的全部进程和该作业的JCB 3 3进程调度 3 3 1进程调度的功能和时机进程只有在得到CPU之后才能真正活动起来 一个就绪进程怎样获得CPU的控制权呢 这是由进程调度实现的 进程调度也被称为低级调度 进程调度程序也往往被称为低级调度程序 它完成进程状态从就绪态到运行态的转化 实际上 进程调度程序主要是完成一台物理的CPU转变成多台虚拟 或逻辑 的CPU的工作 1 功能进程调度的主要功能是 1 保存现场 2 挑选进程 3 恢复现场 2 时机在什么情况下执行进程调度呢 一般是在以下事件发生后作进程调度 1 完成任务 2 等待资源 3 运行到时 4 发现标志 5 创建新进程 图3 3进程调度流程 3 3 2两级调度模型作业调度和进程调度是CPU主要的两级调度 二者的关系可用图3 4表示 图3 4两级调度简化队列图 3 3 3三级调度模型当一个系统中三级调度同时存在时 其相互间的关系如图3 5所示 简单来说 作业调度从后备作业中选择一批合适的作业放入内存 并创建相应的进程 进程调度从就绪队列中选择一个合适进程 令其投入运行 中级调度将在内存中驻留时间较长的进程换到磁盘上 从就绪队列转到就绪 挂起队列 从阻塞队列转到阻塞 挂起队列 当内存中有足够的可用空间时 中级调度就从就绪 挂起队列中选择一些合适的进程放入内存 使之进入就绪队列 图3 5三级调度简化队列 3 4性能评价标准 1 所用算法应保证实现系统的设计目标 2 对所有作业或进程应公平对待 3 均衡使用资源 尽量使系统中各种资源都同时得到利用 4 兼顾响应时间和资源利用率 5 基于相对优先级 但避免无限延期 6 系统开销不应太大 3 4 2性能评价标准1 CPU利用率CPU的利用率可从0 100 2 吞吐量吞吐量表示单位时间内CPU完成作业 或进程 的数量 3 周转时间从一个特定作业的观点出发 最重要的标准就是完成这个作业要花费多长时间 作业i的周转时间Ti为 其中 tsi表示作业i的提交时刻 tci表示作业i的完成时刻 系统中n个作业的平均周转时间T为 作业周转时间没有区分作业实际运行时间长短的特性 因为长作业不可能具有比运行时间还短的周转时间 为了合理反映长短作业的差别 定义了另一个衡量标准 带权周转时间W 即W T R 其中T为周转时间 R为实际运行时间 平均带权周转时间W为 4 就绪等待时间CPU调度算法并不真正影响作业执行或I O操作的时间数量 各种CPU调度算法仅影响作业 进程 在就绪队列中所花费的时间数量 5 响应时间在交互式系统中 周转时间不可能是最好的评价标准 一个进程往往可以很早地就产生某些输出 当前面的结果在终端上输出时它可以继续计算新的结果 于是 有另一个评价标准 就是从提交第一个请求到产生第一个响应所用的时间 这就叫做响应时间 3 5常用调度算法 3 5 1先来先服务 FCFS 最简单的CPU调度算法就是先来先服务 FirstComeFirstServed 方法 即按作业 进程 到来的先后次序进行调度 这样 在系统中等待时间最长的作业就优先被调度 而不管其所需运行时间的长短 FCFS的性能很差 考虑下面三个作业 如图3 6所示 对每个作业 设已知其运行时间 我们计算这三个作业的平均周转时间 图3 6三个作业 如果作业按1 2 3的顺序几乎同时到达 那么采用FCFS方式的服务顺序也是1 2 3 如图3 7所示 图3 7FCFS方式 作业1的周转时间是24 作业2的周转时间是27 作业3的周转时间是30 平均周转时间是 24 27 30 3 27 然而 若作业的到达顺序是2 3 1 则服务顺序如图3 8所示 图3 8另一种作业运行顺序 3 5 2短作业优先 SJF CPU调度的另一种方式是短作业优先 ShortestJobFirst 算法 所谓作业的长短是指作业要求运行时间的多少 当CPU可供使用时 SJF算法就把CPU分给最短的作业 例如 考虑如图3 9所示的一组作业 它们同时提交到系统 图3 9同时到达的一组作业 利用短作业优先法调度 作业执行的顺序如图3 10所示 其平均周转时间是13 图3 10SJF调度法 对于一组给定的作业来说 短作业优先法给出最小的平均等待时间 可以证明 在这方面它是最佳的 证明的办法是 把一个短作业移到长作业之前所减少的短作业的等待时间大于增加的长作业等待时间 相应地 平均等待时间也减少了 如图3 11所示 图3 11SJF有最小平均等待时间 3 5 3优先级 Priority 短作业优先法是一般优先级调度算法的特例 每个进程有一个优先级 CPU分给优先级最高的进程 优先级相同的进程按FCFS调度 短作业优先法是简化的优先级算法 这里优先级 p 反比于估计的下一次CPU工作时间 p 1 CPU工作时间越长 其优先级越低 3 5 4抢占式和非抢占式算法SJF既可以为抢占式 又可以为非抢占式 当一个作业正在执行时 一个新作业到来 并进入就绪队列 而新作业比当前正在执行的作业还短 在此情况下 就有两种不同的处理方式 抢占式短作业优先算法强行中止当前正在执行的作业 调度新作业执行 而非抢占式SJF将允许当前作业继续运行 直到完成它的CPU运行工作 抢占式短作业优先法也叫做最短剩余时间优先法 SRTF ShortesRemainingTimeFirst 作为例子 考虑下面4个作业 如图3 12所示 图3 124个作业示例 如果这些作业按上面所示的时间进入就绪队列并需要指定的运行时间 那么下面的示意图 如图3 13所示 就说明了最短剩余时间优先法调度的结果 图3 13SRTF法调度示例 表3 1SRTF调度算法的性能 3 5 5轮转法 RR 轮转法 RR RoundRobin 主要是为分时系统设计的 一个极为重要的参数就是时间片 它是一个小的时间单位 不能取得过大或者过小 通常为10 100ms数量级 就绪队列可看成是一个环形队列 CPU调度程序轮流地把CPU分给就绪队列中的每个进程 时间长度都是一个时间片 图3 14RR法q 1和q 4时进程运行的情况 由图3 14可以看出 在轮转法中 一次轮回时间内分给任何进程的CPU时间都不会大于一个时间片 如果一个进程在一个时间片内没有做完自己的事情 那么在时间片用完时 该进程就被剥夺对CPU的控制权 放回到就绪队列的末尾 所以 一个需运行较长时间的进程要经过多次轮转才能完成工作 表3 2给出各进程的周转时间和带权周转时间项等指标 表3 2RR调度算法的性能 时间片的长短通常由以下几个因素确定 1 系统的响应时间 在进程数目一定时 时间片的长短直接正比于系统对响应时间的要求 2 就绪队列进程的数目 当系统要求的响应时间一定时 时间片的大小反比于就绪队列中的进程数 3 进程的转换时间 若进程的转换时间为t 时间片为q 为保证系统开销不大于某个标准 应使比值t q不大于某一数值 如1 10 4 CPU运行指令速度 CPU运行速度快 则时间片可以短些 反之 则应取得长些 3 5 6多级队列法 MQ 另一类调度算法是把多个进程分成不同级别的组 例如 通常的划分方式是分为前台进程 交互 和后台进程 批处理 这两类进程的响应时间要求是完全不同的 所以有不同的调度算法 多级队列 MQ MultilevelQueue 调度算法把就绪队列划分成几个单独的队列 如图3 15所示 图3 15多级队列调度 下面是多级队列调度法的一个例子 有如下5个队列 1 系统进程 2 交互进程 3 交互编辑进程 4 批处理进程 5 学生批处理进程 3 5 7多级反馈队列法 MFQ 通常在多级队列法中 进程是永久性地放到一个队列中的 它们不能从一个队列移到另一个队列 而多级反馈队列法 MFQ MultilevelFeedbackQueue 允许进程在各队列间移动 其基本思想是把具有不同CPU工作时间这一特性的进程区分开来 图3 16多级反馈队列 3 5 8多级调度综合示例在一个系统中会采用多级调度 如作业调度和进程调度 并且各采用不同的调度算法 如作业调度可采用FCFS SJF SRTF等算法 而进程调度可采用最高优先权优先法 HPF RR MQ等算法 例如 在一个有两道作业的批处理系统中 作业调度采用短作业优先的调度算法 进程调度采用抢占式优先级调度算法 设有以下作业序列 如图3 17所示 图3 17作业序列示例 其中 给出的作业优先数即为相应进程的优先数 其数值越小 优先级越高 在这种情况下 每个作业从到达系统到完成要经历两级调度 首先由作业调度程序根据其采用的算法和内存的实际情况 挑选作业送入内存 并建立相应进程 然后由进程调度程序依据自己的调度算法从就绪队列中选出合适进程 令其投入运行 这4个作业 进程 的活动情况如图3 18所示 图3 184个作业的活动过程 表3 34个作业活动的有关数据 3 6Linux系统中的进程调度 3 6 1进程调度1 调度方式Linux内核的调度方式基本上采用 抢占式优先级 方式 即当进程在用户模式下运行时 不管是否自愿 在一定条件下 如时间片用完或等待I O 核心就可以暂时剥夺其运行而调度其他进程进入运行 Linux系统中进程分为实时进程和非实时进程 它们的优先级由不同方式确定 实时进程的优先级采用静态优先级 即由用户预先指定 以后不会改变 非实时进程的优先级采用动态优先级 它由调度程序计算出来 实时进程的静态优先级通常比非实时进程的动态优先级要高 Linux系统中的调度策略基本上继承了UNIX的以优先级为基础的调度 2 调度策略Linux系统针对不同类别的进程提供了三种不同的调度策略 即SCHED FIFO SCHED RR以及SCHED OTHER 3 调度时机核心进行进程调度的时机有以下5种情况 1 当前进程调用nanosleep 或者pause 使自己进入睡眠状态 主动让出一段时间CPU的使用权 2 进程终止 永久地放弃对CPU的使用 3 在时钟中断处理程序执行过程中 发现当前进程连续运行的时间过长 4 当唤醒一个睡眠进程时 发现被唤醒的进程比当前进程更有资格运行 5 一个进程通过执行系统调用来改变调度策略或者降低自身的优先权 如nice命令 从而引起立即调度 4 调度算法进程调度的算法应该比较简单 以便减少频繁调度时的系统开销 Linux执行进程调度时 首先查找所有在就绪队列中的进程 从中选出优先级最高且在内存的一个进程 3 6 2shell基本工作原理Linux系统提供给用户的最重要的系统程序是shell命令语言解释程序 它不属于内核部分 而是在核心之外以用户态方式运行 其基本功能是解释并执行用户键入的各种命令 实现用户与Linux核心的接口 系统初启后 核心为每个终端用户建立一个进程去执行shell解释程序 它的执行过程基本上按照如下步骤 1 读取用户由键盘输入的命令行 2 分析命令 以命令名作为文件名 并将其他参数改造为系统调用execve 内部处理所要求的形式 3 终端进程调用fork 建立一个子进程 4 终端进程本身用系统调用wait4 来等待子进程完成 如果是后台命令 则不等待 5 如果命令末尾有 号 后台命令符号 则终端进程不用执行系统调用wait4 而是立即发提示符 让用户输入下一个命令 转步骤 1 shell基本执行过程以及父子进程之间的关系如图3 19所示 图3 19shell命令执行过程 3 6 3系统初启1 硬件检测当PC启动时 首先CPU进入实模式 开始执行ROM BIOS起始位置的代码 2 加载引导程序整个硬盘的第一个扇区是引导扇区 加电后从这个扇区 引导 所以它称为 主引导记录块 MBR MBR中会有磁盘分区的数据和一段简短的程序 共512字节 引导扇区中的程序及其辅助程序 不包括LILO 采用汇编语言编写 共有三个 1 bootsect S 这是Linux引导扇区的源代码 汇编后不能超过512字节 2 setup S 这是辅助程序的一部分 3 video S 这是另一部分辅助程序 用于引导过程中的屏幕显示 3 系统初始化辅助程序setup为内核映像的执行作好了准备 包括解压缩 以后 就跳转到0 x100000开始执行内核本身 下面就是内核的初始化过程 初始化过程可以分为三个阶段 第一阶段主要是CPU本身的初始化 例如页式映射的建立 第二阶段主要是系统中一些基础设施的初始化 例如内存管理和进程管理的建立和初始化 最后是对上层部分初始化 如根设备的安装和外部设备的初始化等 在初始化的第一阶段 首先设置内核页表 并启动页面映射机制 在第二阶段调用函数start kernel 继续进行内核的初始化 甚至可以说这才真正开始内核初始化 这是在较高层次上的初始化 在第三阶段 内核线程init首先锁定内核 然后调用过程来初始化外部设备及加载驱动程序 对外设的初始化包括PCI总线的初始化 网络初始化 一系列其他设备的初始化等 创建第二个内核线程keventd 由它充当 代