进程管理：调度算法

调度算法的性能指标：

①CPU的使用率
②响应时间：调度器为一个就绪任务进行上下文切换时所需的时间，以及任务在就绪队列中的等待时间。
③周转时间：一个任务从提交到完成所经历的时间。
④调度开销：调度器在做出调度决策时所需要的时间和空间开销。
⑤公平性：大致相当的两个任务所得到的CPU的时间应该大致相同。
（要防止饥饿，即一个任务始终得不到处理器去运行。）
⑥均衡性:尽可能使整个系统的各个部分（CPU、I/O）都忙起来，提高系统资源的使用效率。
⑦吞吐量：单位时间内完成的任务数量。

性能指标之间具有一定的冲突性：
比如可通过让更多的任务处于就绪状态来提高CPU的使用率，但这显然会降低系统的响应时间。
调度程序的设计需要优先考虑最重要的需求，然后再各种因素之间进行折中处理。

调度算法-FCFS

先来先服务算法（First Come First Served，FCFS）：

也叫先进先出算法（First In First Out,FIFO）,按照任务到达的先后次序进行调度，是不可抢占式的调度方式。

①若当前任务占用CPU运行，一直等到它执行完成或被阻塞，才释放CPU。

②被阻塞的任务，被唤醒后，将其放在就绪队列的末尾，重新开始排队

先来先服务算法特点：
①简单，易于理解，易于实现

②一批人物的平均周转时间取决于各个任务达到的顺序，如果短任务位于长任务之后，将增大平均周转时间。

例如：假设有三个任务A,B,C，它们的实际时间非别是24,3，3分钟。

短作业优先算法（Shortest Job First,SJF）:

各个任务开始执行之前，实现预计好它的执行时间，从中选择用时较短的任务优先执行。

短作业优先算法有2种实现方案：
①不可抢占方式：任务正在运行时，即使来了一个更短的任务，也不会被打断，只有当它运行完毕或被阻塞时，才会让出CPU，进行新的调度。

②可抢占方式：如果一个新的短任务到了，且它的运行时间要小于当前正在运行的任务的剩余时间，则新任务会抢占CPU去运行。也称为最短剩余时间优先算法（Shortest Remaining Time First,SRTF）。

时间片轮转调度算法（Round-Robin scheduling,RR）:

①所有的就绪任务按照先来先服务的原则拍成一个队列

②在每次调度的时候，把处理器分派给队列当中的第一个任务，让它去执行一小段时间（时间片）。在这个时间段里任务被阻塞或结束，或者任务的时间片用完了，它会被送到就绪队列的末尾，然后调度器再执行当前队列的第一个任务。

时间片轮转调度算法的优点：
①公平性:各个就绪任务平均地分配使用CPU的时间

②活动性：每个就绪任务都能一直保持着活动性

采用时间片轮转调度算法时，任务的时间片大小要适当选择。

时间片大小的选择会影响系统的性能和效率。
时间片太大，时间片轮转调度就没有意义；
时间片太小，任务切换过于频繁，处理器开销大，真正用于运行应用程序的时间将会减小。

时间片轮转算法有一个默认前提，即位于就绪队列中的各个任务是同等重要的，任务按照先来后到的顺序拍成一个队列，大家轮流执行相同长度的时间片。

优先级算法：

①给每个任务都设置一个优先级。

②在任务调度的时候，在所有处于就绪状态的任务中选择优先级最高的那个任务去运行。

优先级算法分为：可抢占式和不可抢占式。
①可抢占式：当一个任务正在运行，一个优先级更高的新任务进入就绪状态，会立即抢占CPU运行新任务。

②不可抢占式：当一个任务正在运行，一个优先级更高的新任务进入就绪状态，等当前任务执行完再决定。

任务优先级有静态方式和动态方式两种确定方式。

静态优先级方式：
在创建任务的时候就确定任务的优先级，且一直保持不变直到任务结束。
缺点：高优先级的任务会一直占用着CPU运行，低优先级的任务可能会长时间地得不到CPU，一直处于“饥饿”状态。

动态优先级方式：
在创建任务的时候确定任务的优先级，但该优先级可以在任务的运行过程中动态改变，以获得更好的调度性能。

优先级算法优化——优先级分组

在优先级算法中，把任务按照不同的优先级进行分组，不同组的任务之间使用优先级算法，同一组的各任务之间使用时间片轮转算法。

优先级算法的问题——优先级翻转的产生

采用优先级调度算法是可能会发生优先级反转，出现任务“饥饿”现象。

理想情况下：
高优先级任务就绪后，能够立即抢占低优先级任务而得到执行。
实际系统中：
在有多个任务需要使用共享资源的情况下，可能会出现高优先级任务被低优先级任务阻塞，并等待低优先级任务执行的现象。

优先级反转：
高优先级任务需要等待低优先级任务释放资源，而低优先级任务又在等待中等优先级任务的现象。

总结

不同的任务调度算法的比较：