处理机调度算法详解专题

一.基础理论

1.基本概念

? ? ? ? 计算机中的资源数量有限无法处理多个任务时，需要制定某种规则来决定处理这些任务的顺序；处理机调度是对处理机进行分配，即从就绪队列中按照一定的算法（公平、高效的原则）选择一个进程并将处理机分配给它运行，以实现进程并发地执行~

? ? ? ? 处理机调度是多道操作系统的基础，是操作系统设计的核心问题~

2.层次

• 高级调度：即作业调度，按照一定的规则从外存上处于后备队列的作业中挑选一个（或多个），给它们分配内存、输入/输出设备等必要的资源，并建立相应的进程~
• 中级调度：即内存调度，引入的目的是提高内存利用率和系统吞吐量，为此，将那些暂时不能运行的进程调度至外存等待——此时进程的状态被称为挂起态
• 低级调度：即进程调度，按照某种算法从就绪队列中选择一个进程，将处理机分配给它，使用频率极高，是最基本的一种调度

二.调度算法

1.先来先服务FCFS

• 最简单的调度算法，既可以用于作业调度，也可以用于进程调度~
• 每次从后备作业队列中选择最优先进入该队列的进程，将处理机分配给它使其投入运行，直到运行完成或者金额因为某种原因阻塞才会归还处理机~

? ? ? ? 属于不可剥夺算法，表面上对所有作业公平，但长作业先到后则其他作业会等很长时间，不适用于分时和实时OS~

特点：

• 算法简单但是效率低
• 长作业有利，短作业不利
• 有利于CPU繁忙的作业，不利于IO繁忙的作业
• 不会导致饥饿?

2.短作业优先SJF

从后备队列中选择约个或若干个估计运行时间最短的作业（即需求服务时间最短~）

• 默认为非抢占式的模式
• 追求最少的平均等待时间、平均周转时间
• 对长作业不利（长作业会）

3.优先级调度算法

????????所谓的优先级用于描述作业的紧迫程度，在作业调度中，优先级算法每次从后备作业中选择优先级最高的一个或者几个作业，将他们调入进程并放入就绪队列。

4.高响应比优先调度算法

• FCFS和SJF的一种综合平衡
• 响应比计算公式：等待时间+要求服务时间的和，再与要求服务时间做商
• 同样也是非抢占式的算法，只能由进程主动放弃
• 可以克服饥饿现象

5.时间片轮转调度算法RR

????????调度程序选择就绪队列的第一个进程执行并分配一个时间片。在一个时间片用完之后，即使进程并未运行完成，它也必须释放出处理机给下一个就绪进程~

• 优点在于公平，而缺点则是不区分紧急程度
• 抢占式算法，由有关时钟中断的硬件来实现
• 伴随着分时OS的诞生而诞生

6.多级队列调度算法

????????该算法在系统中设置多个就绪队列，将不同类型或性质的进程固定分配到不同的就绪队列，每个队列可以实施不同的调度算法，因此，系统针对不同进程的需求，很容易提供多种调度策略。同一队列中的进程可以设置不同的优先级，不同的队列本身也可以由不同的优先级——适用于多处理机的系统，每个处理机拥有一个单独的就绪队列~

7.多级反馈队列调度算法

通过动态调整进程优先级和时间片的大小，多级反馈队列调度算法可以兼顾多方面的系统目标。

步骤：

• 设置多个就绪队列，并为每个队列设置不同的优先级
• 优先级越高的队列，每个进程赋予的时间片就越小
• 每个队列都采用先来先服务的FCFS先来先服务?

---

表格对比一下各种调度算法的区别：