四川大学操作系统原理、操作系统课件 处理器调度（1）.ppt

回顾 举例理解进程的概念 回顾 程序的顺序执行与并发执行 顺序执行 并发执行 调度的概念与本质 调度： 系统将计算机资源分配给进程。 单道程序环境与多道程序环境 处理器调度： 多道程序环境下将处理器分配给各进程 处理器调度的层次 处理机是计算机系统中的重要资源 处理机调度算法对整个计算机系统的综合性能指标有重要影响 处理机调度的三个层次： 高级调度 中级调度 低级调度 高级调度-作业的概念与分类 概念： 作业由一组统一管理和操作的进程集合构成，是用户要求计算机系统完成的一项相对独立的工作。 作业可以是完成了编译、链接之后的一个用户程序，也可以是用各种命令构成的一个脚本。 分类： 根据需要处理工作的类型，分为计算型作业和I/O型作业。 按照作业提交方式，分为批处理作业和终端型作业。 一个系统能够接纳作业的个数称为系统的多道程序度。 高级调度-概念与模型 作业调度概念： 按照操作系统预先规定的策略，从磁盘的作业后备队列中选择作业调入内存，为作业分配所需要的资源并建立与作业相对应的进程。 当作业运行的准备工作完成后，作业调度启动作业运行。 在作业运行结束后，作业调度归还并释放作业占用的资源，结束作业。 模型： 高级调度-策略与因素 接纳多少个作业 作业数目太多时，可能会影响到系统的服务质量; 作业的数量太少时，又会导致系统的资源利用率和系统吞吐量太低 接纳哪些作业 先来先服务调度算法 短作业优先调度算法 基于作业优先级的调度算法 响应比高者优先”的调度算法 高级调度-OS任务 作业调度中操作系统需要完成如下主要工作： 确定作业的数据结构 确定作业的调度算法 为作业分配资源 回收作业资源 高级调度-作业状态转换 作业调度将作业从后备状态转换到内存执行状态 作业执行状态包含作业所对应进程的就绪、运行和阻塞状态 中级调度-概念与功能 又称为中程调度，是为了提高内存利用率和平衡系统负载而采取的一种利用外存补充内存的措施。 多进程环境下，内存中存在多个进程，其中有些进程可能需要挂起，这些进程暂时不参与对处理器的竞争。 为了充分利用内存资源，系统会采用进程对换的方法将进程换出到外存，将这些进程占用的内存空间释放，让内存能够接纳新的进程或使得内存中的进程能够更快推进。当被换出到外存中的进程挂起时间到时，又需要将这些进程换入到内存。 中级调度是在换出内存的进程中确定需要进入内存的进程的一种调度操作。 低级调度-概念与功能 又称为进程调度、短程调度 按照一定的调度算法从内存的就绪进程队列中选择进程，为进程分配处理器，避免进程对处理器竞争的方法。 与作业调度和中级调度比较，进程调度发生的频率最高，作业调度发生的频率最低，中级调度主要用于内存管理，特别是虚拟存储器管理。 3.1.2 进程调度模型 只有进程调度的调度队列模型 3.1.2 进程调度模型 具有高、低两级调度的调度队列模型 3.1.2 进程调度模型 具有三级调度时的调度队列模型 低级调度-原因与机制 引起进程调度的主要原因如下： 处理器执行的进程完成任务，处理器空闲 处理器执行的进程转入阻塞状态，此时处理器空闲 处理器执行的进程被其它进程抢占 处理器执行的进程被挂起 机制： 排队器 分派器 上下文切换机制 低级调度-调度方式 非抢占方式： 简单，实时性差 抢占方式 时间片原则 优先权原则 短作业优先原则。 调度算法的评价准则 基本原则： 具有公平性 资源利用率高（特别是CPU利用率） 在交互式系统情况下要追求响应时间（越短越好） 在批处理系统情况下要追求系统吞吐量 处理器利用率 CPU utilization 响应时间 response time 周转时间 turnaround time 系统吞吐量 throughput 作业调度算法 概念回顾 作业调度是在资源满足的条件下，将处于后备状态的作业调入内存，同时生成与作业相对应的进程，并为这些进程提供所需要的资源。 作业调度程序只保证被调度的作业有获得处理器的资格，而处理器的分配则需要进程调度才能完成。 主要算法 FCFS：先来先服务（First-Come First-Served) SJF：短作业优先（Shortest-Job-First） HRRF：响应比高者优先 HPF：优先权高者优先（ Highest-Priority-First) 分类调度 FCFS：先来先服务 基本思想 遵循先进入后备队列的作业，先进行调度的原则。 非抢占式算法 简单，易于编码实现 优先考虑作业的等待时间，没有考虑作业的执行时间长短、作业的运行特性和作业对资源的要求 算法评价 有利于长作业，不利于短作业 有利于CPU繁忙的作业，不利于I/O繁忙的作业 举例？ FCFS：先来先服务-例1 作业J1、J2、J3、J4依次到达作业后备队列，需要处理时间分别如下：J1为1