内核－进程调度1

1、UNIX内核进程调度（1） 进程调度（1）作为多任务操作系统，进程调度是它的最基本的操作之一。希望在一台单处理器的机器上同时运行多个进程的时候，必须有某种形式的进程调度。这是明显的，因为在任何特定的瞬间，机器只能为一个进程执行一条命令。为了使机器上的若干个进程同时取得进展，必须由准备好运行的进程共享CPU时间。调度程序的任务是选择下一个准备好运行的进程，将CPU时间分配给它。1. 背景当调度程序进行调度任务时，它试图达到一些目标。我们将看到有些目标对调度程序提出的要求是互相冲突的。调度程序的最重要的目标有：· 使每个进程公平地共享CPU时间。· 使CPU的空闲时间

2、达到最少（即保持CPU处于忙碌状态）。· 吞吐能力达到最高。这表明在给定时间内完成任务的进程数达到最多。· 使系统响应用户请求的时间达到最短。似乎应该以某种方式优先考虑用户请求，但是这和所有进程公平共享CPU时间的目标明显发生冲突。一般来说调度程序直接面对的问题是：当它启动进程时，对进程的了解很少。如进程平均使用多少CPU时间才停下来等待输入输出；以及进程提出输入输出请求后，平均用多长时间进行等待等是未知数。另一个问题是：对进行输入/输出前占用很长CPU时间的进程应该采取什么措施？能让它独占CPU一直运行下去？显然不能、否则这一进程可能使所有的其他进程都处于停顿状态。这说明

3、在当前进程运行足够长的时间后，要有某种方法将CPU切换给另外一个进程。但是从哪里着手，又如何进行这样的调度。这里有两种可能。第1种可能使让进程在CPU上运行一段时间后，自愿放弃对CPU的控制。第2种情况是找出某种办法强制进程释放对CPU的控制。第一种称为非抢先调度。第二种称为抢先调度。当我们讨论线程（thread）时将看到；运行由相互协调的程序组成的系统时候，用非抢先调度进行切换是完全行的通的。然而对多用户环境下的进程调度来讲，更安全的做法是：最好的情况：进程间并不知道对方的存在。在最坏的情况：进程之间互相竞争CPU的使用。结果是在多用户的环境下几乎毫无例外地使用抢先调度。具体的做法是：给每个

4、进程分配一段最长的不间断的CPU时间，同时系统产生快速和周期性的时钟计时中断，用来决定进程什么时候拥有它的时间片。当分配给当前进程的时间片消逝以后，调度程序投入运行，由它来决定是否还有准备好运行的进程，它是否比刚用完时间片的当前进程更有资格投入运行。如果有，由新的进程取代当前的进程，如果没有，让当前进程继续运行：从前面的讨论可以看到，进程有几种不同的状态。随着不同事件的出现，在这些状态间进行切换。上图表示CPU调度程序控制下的简化的进程状态转换图，而且标出了在下列情况下发生的6种转换。1.启动（start)转换。当进程首次被启动时（fork()），并没有让它直接控制CPU。而是将它置为可运行状

5、态，和其他进程一起放在一个队列中。只要给它们分配CPU时间，就立即可以投入运行。2.将处于可运行状态的进程转换为运行状态。在可运行进程队列中的进程，最终将被调度程序选中，在CPU上执行一段时间。3.有几种方法使一个在CPU上运行的进程转换为其他状态。转换3就是其中的一种，将当前运行的进程放回可运行的进程的清单中。当在处理器上运行的进程种用完了分配的时间片后，就发生这种转换，使其他进程有机会投入运行。4.另一种主要方式是当运行中的进程提出输入/输出请求时，它将失去对CPU的控制。机器的硬设备对请求作出响应之前会有一段时间的延迟。在等待输入输出完成时，即使 CPU空闲，进程也不能运行。所以当进程停下等待输入输出完成时，它不能被放回可运行进程的清单中，而是通过转换4将它设置为挂起的状态，等待输入输出的完成。5.当一个挂起的进程等待的输入输出事件发生了。它再次成为有资格运行的进程。然而并不立即给这个进程提供CPU时间片去处理它的输入输出，只是将它送到可运行进程的清单中，等待再次被调度程序选中。这是转换5完成的工作。6.在简化图中，最后一种失去对CPU控制的方式发生在运行的进程结束时，转换6表示导致进程结束的事件。也许出人意料，不管CPU调度程序采用什么算法决定下一个应该运行的进程