二、进程调度算法

2.4 调度

同城会有多个进程或线程同时竞争CPU，如果只有一个CPU可用，就必须选择下一个要运行的进程。在操作系统中，完成选择工作的这一部分称为调度程序，该程序使用的算法称为调度算法。许多适用于进程调度的处理方法同样适用于线程。当内核管理线程的时候，与线程所属的进程基本没有关联。

2.4.1 介绍

为了选取正确的进程运行，调度程序还要考虑CPU的利用率，因为进程切换的代价是比较高的。首先用户态必须切换到内核态；然后要保存当前进程的状态，包括进程表中存储寄存器值以便以后重新装载，在许多系统中内存映像（页表内的内存访问位等）也必须保存；接着，通过运行调度算法选择一个新进程；之后将新进程的内存映像重新装入MMU（内存管理单元）；最后新进程开始运行。切换进程太频繁会耗费大量的CPU时间。

如果需要运行I/O密集型进程，那么久应该让他尽快得到机会，以便发出磁盘请求并保持磁盘始终忙碌。

l  调度程序进行的时间：

1)        创建一个新进程后（觉得运行子进程还是父进程）

2)        一个进程退出时

3)        一个进程阻塞在I/O和信号量上或其他原因阻塞

4)        发送I/O中断时

l  调度算法分类

非抢占式调度算法、抢占式调度算法。

调度程序的环境：

1)        批处理

2)        交互式

3)        实时

批处理系统主要用于商业领域，主要用非抢占式算法。交互环境中，为避免一个进程霸占CPU拒绝为其他进程服务，抢占是必须的。

l  调度算法的目标

所有系统：

1)        公平----每个进程公平获得CPU份额

2)        策略强制执行----所采取的策略能够执行

3)        平衡----尽量保证系统的所有部分忙碌

批处理系统：

1)        吞吐量----每小时最大作业数

2)        周转时间----从提交到终止间的最小时间

3)        CPU利用率----保持CPU始终忙碌

交互系统：

1)        响应时间----快速响应请求

2)        均衡性----满足用户的期望

实时系统：

1)        满足截止时间----避免丢失数据

2)        可预测性----在多媒体系统中避免品质降低

2.4.2 批处理系统中的调度

1.        先来先服务

最简单的非抢占式调度算法。进程按照请求CPU的顺序使用CPU，不会产生终端，会一直运行进程直到进程完成或被阻塞。被阻塞的进程变为就绪态时像新来的进程一样进行排队。缺点：I/O密集型的进程会造成严重的CPU资源浪费。

2.        最短作业优先

非抢占式算法。优先运行所需时间最短的进程。在所有的作业都可同时运行的情况下，最短作业优先算法是能达到最小周转时间的最优化算法。

3.        最短剩余时间优先

抢占式算法。选择剩余时间最短的进行运行。必须能够提前掌握进程的运行时间。

2.4.3 交互式系统中的调度

1.        轮转调度

每个进程被分配一个时间段，称为时间片，允许该进程在该时间段中运行。时间片结束后将被剥夺CPU分配给另一个进程，如果在时间片结束前结束或者阻塞，则进行CPU切换。实现容易，调度程序需要维护一张可运行进程列表，进程用完时间片后就被移到队列的末尾。从一个进程切换到另一个进程需要处理的事物包括：保存和装入寄存器值及内存映像、更新各种列表和表格、清除和重新调入内存告诉缓存等，需要一定的CPU消耗。故时间片不宜设置地太小。一般为20ms至50ms。

2.        优先级调度

每个进程被赋予一个优先级，允许优先级高的可运行进程先运行。优先级可以被静态赋予或动态赋予。可将进程按优先级分为不同的类，相同优先级的进程间按轮转调度算法进行调度。

3.        多级队列

为CPU密集型进程设置较长的时间片更为高效。但是长时间片的进程会影响到响应时间。可以设立优先级类，高优先级的进程赋予较短的时间片，低优先级的进程赋予较长的时间片。

4.        最短进程优先

类似批处理系统中最短作业优先调度算法。可以用老化技术估计当前进程的运行时间。

5.        保证调度

对用户做出明确的性能保证。如有n个用户同时使用系统，可以保证每个用户获得CPU处理能力的1/n。

6.        彩票调度

基本思想是想进程提供各种系统资源（如CPU时间等）的彩票，需要调度时，随机抽出一张彩票，拥有该彩票的进程获得该资源。可以通过给予高优先级进程更多的彩票来保证高优先级进程更可能获得系统资源。彩票调度是反应迅速的，一个进程出现后该进程获得系统资源的概率与获得彩票的多少正相关；彩票调度也可以实现进程间的协作，如一个进程需要被另一个进程运行的结果而被阻塞，该进程可以选择给予另一个进程若干彩票从而加大另一个进程获得系统资源的概率。

7.        公平分享调度

根据用户来进行系统资源调度。保证开启进程较少的用户能够获得跟开启大量进程的用户获得相同的系统资源。

2.4.4 实时系统中的调度

实时系统可以分为硬实时和软实时，硬实时必须满足绝对的截止时间，而软实时系统虽然不希望错失截止时间，但是可以容忍。实时系统是可调度的系统的条件：

其中事件i以周期发生，以秒CPU时间进行处理。并且该公式忽略了上下文切换的开销。

2.4.5 策略和机制

存在这样的情况：一个进程有许多子进程并在其控制下运行。以上的调度算法都没有从进程的这一情况出发讨论。解决问题的方法是将调度机制与调度策略分离。操作系统已某种形式将调度算法参数化，参数可以由用户进程填写。这样，父进程本身不参与调度，但是可以控制如何调度子进程。调度机制位于内核，而调度策略则由用户决定。

2.4.6 线程调度

用户级线程和内核级线程。用户级线程中，内核不知道有线程存在，所以内核还是和进程调度一样进行进程调度，进程的线程调度程序负责调度线程。

在内核级线程中，内核选择一个特定的线程运行，不用考虑该线程属于哪个进程（也可以考虑）。

2.5 经典的IPC问题

2.5.1 哲学家就餐问题

用来验证同步原语，对于互斥访问优先资源的竞争问题一类的建模过程十分有用。

问题描述：五个哲学家围坐在一张圆桌周围，每个郑学军勉强都有一盘面，需要两把叉子才能就餐，每相邻的两个盘子间有一把叉子。哲学家每次只能拿一把叉子。需要对哲学家获取叉子的行为进行描述，不会进入死锁状态。

所有的程序都在不停的运行，但是无法取得进展，这种现象称为饥饿。

2.5.2 读者—写者问题

为数据库访问建立了一个模型。

2.6 进程与线程总结

系统吧一个进程视为一个容器，该容器用以聚集相关的资源，如地址空间、线程、打开的文件、保护许可等。对某些应用而言，在一个进程中使用多个控制线程是有用的。这些线程被独立调度，每个线程有自己的堆栈，但是在一个进程中的所有线程共享一个公共的地址空间。线程调度可以在用户空间和内核中实现。

进程之间通过进程间通信原语进行通信，如信号量、管程或消息。这些原语用来确保同一时刻不会有两个进程在临界区中，避免了混乱的情况。进程可以处于运行态、就绪态和阻塞态，该进程和其他进程执行某个进程间通信原语可以改变进程的状态。

有一大批研究出来的调度算法，批处理系统中主要的调度算法有：最短作业优先算法、最短剩余时间优先算法、先来先服务算法等。批处理与交互式系统中主要的调度算法有：轮转调度、优先级调度、多级队列、保证调度、彩票调度等。有些系统将调度策略和调度机制分离，这样可以使用户对调度算法进行控制。