处理机调度

目录导航

基本内容

　在多道程序设计系统中，内存中有多道程序运行，他们相互争夺处理机这一重要的资源。处理机调度就是从就绪队列中，按照一定的算法选择一个进程并将处理机分配给它运行，以实现进程并发地执行。

　　1.处理机调度的功能

　　一般情况下，当占用处理机的进程因为某种请求得不到满足二不得不放弃CPU进入等待状态时，或者当时间片到，系统不得不将CPU分配给就绪队列中另以进程的时候，都要引起处理机调度。除此之外，进程正常结束、中断处理等也可能引起处理机的调度。因此，处理机调度是操作系统核心的重要组成部分，它的主要功能如下：

　　（1）记住进程的状态，如进程名称、指令计数器、程序状态寄存器以及所有通用寄存器等现场信息，将这些信息记录在相应的进程控制块中。

　　（2）根据一定的算法，决定哪个进程能获得处理机，以及占用多长时间。

　　（3）收回处理机，即正在执行的进程因为时间片用完或因为某种原因不能再执行的时候，保存该进程的现场，并收回处理机。

　　处理机调度的功能中，很重要的一项就是根据一定算法，从就绪队列中选出一个进程占用CPU运行。可见，算法是处理机调度的关键。

　　 2.处理机调度的性能准则

　　处理机调度，有许多不问的调度算法，不同的调度算法具有不同的特性。因此，再介绍算法之前，先介绍衡量一个算法的基本准则。

　　衡量喝比较调度算法性能优劣主要有一下几个因素：

　　（1）CPU利用率。CPU是计算机系统中最重要的资源，所以应尽可能使CPU保持忙，使这一资源利用率最高。

　　（2）吞吐量。CPU运行时表示系统正处于工作状态，工作量的大小是以每单位时间所完成的昨夜树木来描述的，这就叫吞吐量。

　　（3）周转时间。指从作业提交到作业完成所经过的时间，包括作业等待，在就绪队列中排队，在处理机上运行以及进行输入/输出操作所花时间的总和。

　　（4）等待时间。处理机调度算法实际上并不影响作业执行或输入/输出操作的时间，只影响作业在就绪队列中等待所花的时间。因此，衡量一个调度算法优劣常常简单的考察等待时间。

　　（5）响应时间。指从作业提交到系统作出相应所经过的时间。在交互式系统中，作业的周转时间并不一定是最好的衡量准则，因此，常常使用另一种度量准则，即相应时间。从用户观点看，相应时间应该快一点好，但这常常要牺牲系统资源利用率为代价。

　　 3.处理机调度算法

　　1）先来先服调度算法（FIFO）

　　这是最简单的处理机调度算法，其基本思想是按照进程进入就绪队列的先后顺序调度并分配处理机执行。先来先服务调度算法是一种不可抢占的算法，先进入就绪队列的进程，先费培处理机运行。一旦一个进程占有了处理机，它就一直运行下去，知道该进程完成工作或者因为等待某事件而不能继续运行时才释放处理机。

　　从表面上看，FIFO算法对所有作业都是公平的，并且一个作业的等待时间时可能预先估计的。但实际上这种算法是不利于小作业的，因为当一个大作业先进入就绪队列时，就会使其后的许多小作业等待很长的时间。这对小作业来说，等待时间可能要远远超出它运行的时间。

　　先来先服算法简单，易于程序实现，但它性能较差，在实际运行的操作系统中，很少单独使用，它常常配合其他调度算法一起使用。

　　2）时间片轮转调度算法（RR）

　　时间片轮转调度算法的基本思想是：对就绪队列中的每一进程部分配一个时间片，时间片的长度q一般从10ms-1100ms不等。把就绪队列堪称时一个环状结构，调度程序按时间片长度q轮流电镀就绪队列中的每一进程，使每一进程都有机会获得相同长度的时间占用处理机运行。

　　时间片轮转调度算法在分时系统中，时一种既简单又有效的调度策略。一个分时系统又许多中断。中断用户在各自的中断设备上同时使用计算机。如果某个中断用户的程序长时间的暂用处理机，那么其他中断用户的请求就不能得到即使相应。一般说来，中断用户提出请求后，能在几秒钟内得到相应也就感到满意了。采用时间片轮转算法，可以使系统即使的相应各中断用户的请求。

　　时间片轮转调度算法的性能极大的以来于时间片长度q的取值，如果时间片过大。则RR算法就退化为FIFO算法了；反之，如果时间片过小，那么，处理机在各进程之间频繁转接，处理机时间开销变得很大，而提供给用户程序的时间将大大减少。

　　3）优先数法

　　优先数法的基本思想是：对就绪队列中的每个进程，首先安某种原则定义一个优先数来表示它，处理机调度时，每次选择就绪队列中优先数最大者（也可规定优先数愈小，其优先权愈高），让它占用处理机运行。

　　确定优先数一般可以又一下集中考虑：

　　（1）频繁使用外部舒服输出设备的进程优先数大。这样有利于提高CPU使用效率。

　　（2）重要程序的进程优先数大，怎样有利于用户灵活操作。

　　（3）进入计算机系统时间长的进程优先数大，这样有利于缩短作业的完成时间。

　　（4）交互式用户作业进程优先数大，这样有利于提高中断相应时间。

　　优先数的设置可以采用静态和动态两种方式。静态设置方式就是指系统在建立一个进程时，就按照某种原则为进程制定一个优先数，这个优先数在进程存在期间一直保持不便。而动态设置方式是指系统在进程存在期间经常改变进程的优先数，如何动态的改变进程的优先数，依赖于具体操作系统的设计目标。