第4章 进程调度.pptx

操作系统 处理机调度 ;桌上有一空盘，只允许存放一个水果。爸爸可向盘中放苹果。也可向盘中放橘子。儿子专等吃盘中的橘子，女儿专等吃盘中的苹果。规定当盘中空时一次只能放一只水果供吃者取用。请用PV原语实现爸爸，儿子，女儿三个并发进程的同步; CPU的突发使用和等待I/O时期交替出现 CPU密集型进程 I/O密集型进程 ;处理机的调度过程 批量型作业：经历作业调度和进程调度 终端型作业：只需进程调度 完美操作系统：包含中级调度 每一级调度可以采用不同的调度方式和调度方法 ;WHAT：按什么原则分配CPU 　　　 —调度算法 WHEN：何时分配CPU 　　　—调度的时机 HOW： 如何分配CPU 　　 —CPU调度过程 ;处理器调度的目标是以满足系统目标的方式，把进程指定一个处理器或多个处理器执行 响应时间 吞吐率 处理系效率 ;处理机调度的类型;具有创建、终止和挂起状态的进程状态图;调度与进程状态转换图;调度的层次;称为作业调度或宏观调度，通过某种算法，用于把外存上处于后备队列中的那些作业调入内存，并为它们创建进程、分配必要的资源，然后再将新创建的进程排在就绪队列上，准备执行。 ;作业：比程序更广泛的概念（程序＼数据＼作业说明书） 作业步：在作业运行期间，每个作业都经过若干个相对独立又相互关联的顺序加工步骤才能得到结果，把其中的每一个加工步骤称为一个作业步 作业流：若干个作业进入系统后，依次存放在外存上，这便形成了输入的作业流． 作业控制块：作业在系统中存在的标志，其中保留了系统对作业进行管理和调度所需的全部信息 ;批处理系统的高级调度或是通用操作系统的批处理部分，新提交的作业被发送到磁盘，并保存在一个批处理队列中 高级调度完成的就是为可能的作业创建进程，这时要考虑两个决定 接纳多少个作业 决定接纳哪些作业 ;创建的进程越多，每个程序可以执行的时间百分比就越小 用户希望有短的周转时间 系统则希望有短的平均周转时间 ;应将哪些作业从外存调入内存，将取决于所采用的算法。 FCFS，先来先服务调度算法 SPN(Sortest Process Next), 短作业优先 HRRN(Highest Reponse Ration Next)最高响应比 从根本本说，调度属于管理队列方面的问题，用来减少延迟，并优化排队环境性能 ;对于分时操作系统来说 是否接受一个终端用户的连接 一个作业是否被计算机系统接纳并构成进程（通常做法是，直至系统饱和） 一个新建态的进程是能立即加入到就绪进程队列 ;决定就绪队列中哪个进程应获得处理机，然后再分派程序把处理机分配给该进程。 低级调度的功能： 记录进程中所有进程的执行情况：状态，优先级，所用资源情况等。 按某种算法选取进程 进行进程上、下文切换，分配处理机给进程。 ;低级调度的三个基本机制 排队器 分派器 上下文切换机制 （硬件提供，操作系统管理） ;低级调度 （任务状态段）;进程调度可采用下述两种调度方式 非抢占式调度 抢占式调度 ;非抢式调度（Nonpreemptive Mode) 可能引起进程调度的因素可归结为这样几个： ① 正在执行的进程执行完毕， 或因发生某事件而不能再继续执行；（时间片，系统调用） ② 执行中的进程因提出I/O请求而暂停执行； ③ 在进程通信或同步过程中执行了某种原语操作，;这种调度方式的优点是实现简单、系统开销小，适用于大多数的批处理系统环境。但它难以满足紧急任务的要求——立即执行，因而可能造成难以预料的后果。显然，在要求比较严格的实时系统中，不宜采用这种调度方式 ;抢占调度(Preemptive Mode)原则有 优先权原则 短作业（进程）优先原则 时间片原则 ;中级调度实际上就是存储器管理中的对换功能。主要目的是为了提高内存利用率和系统吞吐率。 中级调度事际上是两种挂起状态的调度实现 ;仅有进程调度的调度队列模型（分时系统） ;具有高级和低级调度的调度队列模型（批处理系统） ;同时具有三级调度的调度队列模型 ;面向用户的准则 周转时间短 响应时间快 截止时间的保证 优先权准则 面向系统准则 系统吞吐量 处理机利用率 各类资源的平衡利用 ;调度介绍;本节讨论各种常用的进程调度算法和作业调度算法 ;开源的仿真器（/） 算法可视化工具（/~galles/visualization/）;原理 把就绪状态的进程按进入的先后以队列方法排列 按照先来先服务的方式进行调度处理 优点 看似最“公平”， 操作简单 缺点 比较有利于长作业（进程），不利于短作业（进程）;先来先服务(FCFS)调度算法;原理 选择估计需要执行时间最短的作业投入执行 优点 比FCFS改善平均周转时间和平均带权周转时间，缩短作业的等待时间 提高系统的吞吐量 缺点 对长作业非常不利，可能长时间得不到执行 未能依据作业的