2.7低级调度.ppt

* Operating System OS 操作系统 郑州大学 申丰山 * Operating System OS 操作系统 郑州大学 申丰山 主要内容： 低级调度的功能 低级调度算法 实时调度 多处理器调度 2.7低级调度 一、低级调度的功能 (1) 低级调度负责动态地把处理器分配给进程或内核级线程。操作系统中实现低级调度的程序称为进程(线程)调度程序，或分派程序(Dispatcher)。进程调度算法多数适用于线程调度。 1.引起低级调度的原因 有四种情况都会发生CPU调度: ?当一个进程从运行态切换成等待态时; ?当一个进程从运行态切换成就绪态时; ?当一个进程从等待态切换成就绪态时; ?当一个进程中止时。 也就是说当一个进程由运行状态变为非运行状态,或者一个进程变为就绪状态时,都会引起低级调度. 一、低级调度的功能 (2) 2.低级调度的主要功能 ?记录进程（内核级线程）的状态。一般记录在一个进程（内核级线程）的进程控制块（线程控制块）内。 ?决定某个进程（内核级线程）什么时候获得处理器，以及占用多长时间。 ?把处理器分配给进程（内核级线程）。即进行进程（内核级线程）上下文切换，把选中进程（内核级线程）的进程控制块（线程控制块）内有关现场信息送入处理器相应的寄存器中，让它占用处理器运行。 ?收回处理器。将处理器有关寄存器内容送入该进程（内核级线程）的进程控制块（线程控制块）内的相应单元，使该进程出让处理器。 一、低级调度的功能 (3) 低级调度的最初对象是传统操作系统中的进程，操作系统中引入了线程以后，进程只作为中级调度的对象，内核级线程则替代进程成为低级调度的对象。适用于进程调度的算法一般都适用于内核级线程的调度。 用户级线程的调度是应用程序自己的事。在纯用户级多线程策略中，低级调度的对象依然是进程；在混合策略中，低级调度的对象是内核级线程。 二、低级调度算法 (1) 1.先来先服务算法 按照进程进入就绪队列的先后次序分配处理器。 先进入就绪队列的进程优先被挑选，运行进程一旦占有处理器将一直运行直到结束或阻塞。这是一种非剥夺式调度。 算法容易实现，效率不高，不利于I/O频繁的进程。 2.时间片轮转调度算法 (1)算法思想 轮转法调度也称为时间片调度，时间片调度做法是：调度程序每次把CPU分配给就绪队列首进程使用一个时间片，例如100ms，就绪队列中的每个进程轮流地运行一个时间片。当这个时间片结束时，强迫一个进程让出处理器，让它排列到就绪队列的尾部，等候下一轮调度。 二、低级调度算法 (2) (2)实现原理 实现这种调度要使用一个间隔时钟。当一个进程开始运行时，就将时间片的值置入间隔时钟内，当发生间隔时钟中断时，中断处理程序就通知处理器调度进行处理器的切换工作。 (3)效果：轮转策略可防止那些很少使用外围设备的进程过长的占用处理器而使得要使用外围设备的那些进程没有机会去启动外围设备。 (4)常用轮转法 最常用的轮转法是基本轮转法，它要求每个进程轮流运行一个相同的时间片。改进的轮转法对于不同的进程给以不同的时间片；时间片的长短可以动态地修改等等。 二、低级调度算法 (3) (5)时间片取选 轮转法调度是一种剥夺式调度，系统耗费在进程切换上的开销比较大，这个开销与时间片的大小很有关系。 时间片取值太小，多数进程不能在一个时间片内运行完毕，切换就会频繁，开销显著增大，从系统效率来看，时间片取大一点好。 时间片取值较大，随就绪队列里进程数目增加，轮转一次的总时间增大，对进程的响应速度放慢了。如果时间片大到让每个进程足以完成其所有任务，这一算法就退化成先来先服务算法。为满足响应时间要求，要么限制就绪队列中进程数量，要么采用动态时间片法，根据负载状况，及时调整时间片的大小。 时间片大小的确定要从进程个数、切换开销、系统效率和响应时间等方面考虑。 二、低级调度算法 (4) 3.优先数调度 (1)含义： 给每一个进程确定一个优先数，处理器调度每次选择就绪进程中优先数最大者，让它占用处理器运行称优先数调度。 (2)优先数的确定依据（静态优先数法） ?使用外围设备频繁者优先数大，这样有利于提高效率； ?重要算题程序的进程优先数大，这样有利于用户更早得到结果； ?进入计算机时间长的进程优先数大，这样有利于缩短作业周转时间； ?交互式用户的进程优先数大，这样有利于终端用户的响应时间等等, 二、低级调度算法 (5) (3)动态优先数法及其确定原则 动态优先数法：在创建一个进程时，根据进程类型和资源使用情况确定一个优先数，当进程耗尽时间片或重新被调度时，再次计算并调整所有进程的优先数。 动态优先数的确定原则： ①根据进程占有CPU时间多少来决定,当进程占有