进程调度

讨论cpu调度的概念和算法

1.基本概念

多道程序的目标：多个进程同时处于内存，当一个进程等待时，操作系统将CPU交给另个进程，有效利用CPU。

执行周期：在CPU执行和IO等待之间，不断交替。经验表明，执行时间有大量短CPU执行和少量长CPU执行

调度程序：CPU空闲时，从内存中选择一个能够执行的进程，为其分配CPU。

需要进行CPU调度的情况：

• 运行状态->等待状态（IO请求）
• 运行态->就绪态（中断）
• 等待态->就绪态（IO完成）
• 进程终止

调度方案：

• 非抢占式：一旦某个进程分配到CPU，就会一直使用CPU，直到该进程切换到等待状态或终止。（1或4）

• 抢占式

多个进程共享数据时，抢占式可能导致竞争情况。

调度程序：将CPU控制权交给调度程序选择的进程。调度所需时间叫调度延迟

• 切换上下文
• 切换到用户模式
• 跳转到用户程序合适位置， 以便重新启动程序

2.调度准则

最大化CPU使用率和吞吐量，并且最小化周转时间，等待时间和响应时间

3.调度算法

3.1 先到先服务FCFS

先请求CPU的进程先分配到CPU。最简单，可以使用FIFO队列实现。

缺点

• 平均等待时间往往很长
• 调度性能不好，CPU和IO使用率低。“护航效果”
• 非抢占式。一旦CPU分配给了某个进程，该进程就会一直使用CPU，直到终止或IO

3.2 最短作业优先SJF

该算法将每个进程与其下次CPU执行的长度关联起来。当CPU空闲时，会先分配给具有最短CPU执行的进程。

因此该算法也叫做最短下次CPU执行算法。

可以证明，SJF算法是最优的，平均等待时间最少。但是困难的是，如何知道下次CPU执行的长度。

在批处理的长期调度中，可以将用户指定的进程时限作为长度。但是短期调度就无法实现了，只能根据历史情况近似预测。

3.3 优先级调度

每个进程都有一个优先级与其关联，高优先级的进程会分配到CPU。

上一个算法SJF是优先级调度的一个特例，其优先级是下次CPU执行的时间的倒数。CPU执行越长，优先级越小。

优先级的定义分为内部和外部。内部采用测量数据来定义，例如时限，内存，打开文件数量等。外部定义例如进程的重要性等

存在的问题：“无穷阻塞”，低优任务可能永远获取不到CPU

解决方案：“老化”，逐渐增加低优任务的优先级

3.4 轮转调度

3.5 多级队列调度

3.6 多级反馈队列调度