《操作系统》是所有计算机专业的必修课程，也是编程的基础，不管是前端还是后端都应该去了解

进程调度算法

调度实质是一种资源分配，因而调度算法是指：根据系统分配策略所规定的资源分配算法。不同的系统和系统目标，通常采用不同的调度算法

1.FCFS [first come first service]

FCFS的意思是先来先服务(First Come First Service)。顾名思义就是按照进程被添加到等待队列的先后顺序来进行调用的。在进程调度中，FCFS调度算法每次从就绪队列中选择最先进入该队列的进程，将处理机分配给它，使之投入运行，直到完成或因某种原因而阻塞时才释放处理机。

例如：假设系统中有4个作业，它们的提交时间分别是8、8.4、8.8、9，运行时间依次是2、1、0.5、0.2，系统釆用FCFS调度算法，这组作业的平均等待时间、平均周转时间和平均带权周转时间

    作业号	提交时间	运行时间	开始时间	等待时间	完成时间	周转时间	带权周转时间 
       1	   8	   2	   8	   0	   10	   2	  1
       2	   8.4	   1	   10	   1.6	   11	   2.6	  2.6
       3	   8.8	   0.5	   11	   2.2	   11.5	   2.7	  5.4
       4	   9	   0.2	   11.5    2.5	   11.7	   2.7	  13.5
    
    平均等待时间 t = (0+1.6+2.2+2.5)/4=1.575
    平均周转时间 T = (2+2.6+2.7+2.7)/4=2.5
    平均带权周转时间 W = (1+2.6+5.牡13.5)/4=5.625

说明：FCFS调度算法属于不可剥夺算法。从表面上看，它对所有作业都是公平的，但若一个长作业先到达系统，就会使后面许多短作业等待很长时间，因此它不能作为分时系统和实时系统的主要调度策略。但它常被结合在其他调度策略中使用。

例如，在使用优先级作为调度策略的系统中，往往对多个具有相同优先级的进程按FCFS原则处理。

缺点：

• FCFS调度算法的特点是算法简单，但效率低；

• 对长作业比较有利，但对短作业不利（相对SJF和高响应比）；

• 有利于CPU繁忙型作业，而不利于I/O繁忙型作业。

2.SPF [Short Process First] or SJF[Short Job First]

SPF(SJF)的意思是短进程(作业)优先。进程要运行多长时间都可以提前知道。这个值是程序提前写在进程里面的了，系统只要去读取这个值就可以了

SJF调度算法的性能:

    作业号	提交时间	运行时间	开始时间	等待时间	完成时间	周转时间	带权周转时间
       1	8	      2	      8	       0	  10	  2	    1
       2	8,4	      1	      10.7	  2.3	  11.7	  3.3	3.3
       3	8.8	     0.5	  10.2	  1.4	  10.7	  1.9	3.8
       4	9	     0.2	  10	   1	  10.2	  1.2	6
    平均等待时间 t = (0+2.3+1.4+1)/4=1.175
    平均周转时间 T = (2+3.3+1.9+1.2)/4=2.1
    平均带权周转时间 W = (1+3.3+3.8+6)/4=3.525

缺点：

• 1.该算法对长作业不利，SJF调度算法中长作业的周转时间会增加。更严重的是，如果有一长作业进入系统的后备队列，由于调度程序总是优先调度那些 (即使是后进来的）短作业，将导致长作业长期不被调度（“饥饿”现象，注意区分“死锁”。后者是系统环形等待，前者是调度策略问题）

• 2.该算法完全未考虑作业的紧迫程度，因而不能保证紧迫性作业会被及时处理。

• 3.由于作业的长短只是根据用户所提供的估计执行时间而定的，而用户又可能会有意或无意地缩短其作业的估计运行时间，致使该算法不一定能真正做到短作业优先调度。

3.优先级调度算法

优先级调度算法又称优先权调度算法，该算法既可以用于作业调度，也可以用于进程调度，该算法中的优先级用于描述作业运行的紧迫程度。

在作业调度中，优先级调度算法每次从后备作业队列中选择优先级最髙的一个或几个作业，将它们调入内存，分配必要的资源，创建进程并放入就绪队列。在进程调度中，优先级调度算法每次从就绪队列中选择优先级最高的进程，将处理机分配给它，使之投入运行。

3.1 根据新的更高优先级进程能否抢占正在执行的进程，可将该调度算法分为：

• 非剥夺式优先级调度算法：当某一个进程正在处理机上运行时，即使有某个更为重要或紧迫的进程进入就绪队列，仍然让正在运行的进程继续运行，直到由于其自身的原因而主动让出处理机时（任务完成或等待事件），才把处理机分配给更为重要或紧迫的进程。

• 剥夺式优先级调度算法：当一个进程正在处理机上运行时，若有某个更为重要或紧迫的进程进入就绪队列，则立即暂停正在运行的进程，将处理机分配给更重要或紧迫的进程。

3.2 而根据进程创建后其优先级是否可以改变，可以将进程优先级分为以下两种：

• 静态优先级：优先级是在创建进程时确定的，且在进程的整个运行期间保持不变。确定静态优先级的主要依据有进程类型、进程对资源的要求、用户要求

• 动态优先级：在进程运行过程中，根据进程情况的变化动态调整优先级。动态调整优先级的主要依据为进程占有CPU时间的长短、就绪进程等待CPU时间的长短

总之：确认优先级是否可变，正在执行的进程是否能被优先级更高的进程阻塞

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

高响应比优先调度算法主要用于进程(作业)调度，该算法是对FCFS调度算法和SPF(SJF)调度算法的一种综合平衡，同时考虑每个作业的等待时间和估计的运行时间。在每次进行作业调度时，先计算后备作业队列中每个作业的响应比，从中选出响应比最高的作业投入运行。

响应比的变化规律可描述为：

响应比 = (等待时间 + 要求服务的时间)/要求服务的时间

• 当作业的等待时间相同时，则要求服务时间越短，其响应比越高，有利于短作业

• 当要求服务时间相同时，作业的响应比由其等待时间决定，等待时间越长，其响应比越高，因而它实现的是先来先服务。

• 对于长作业，作业的响应比可以随等待时间的增加而提高，当其等待时间足够长时，其响应比便可升到很高，从而也可获得处理机。克服了饥饿状态，兼顾了长作业

5.时间片轮转调度算法

• 时间片轮转调度算法主要适用于分时系统。在这种算法中，系统将所有就绪进程按到达时间的先后次序排成一个队列，进程调度程序总是选择就绪队列中第一个进程执行，即先来先服务的原则，但仅能运行一个时间片，如100ms。在使用完一个时间片后，即使进程并未完成其运行，它也必须释放出（被剥夺）处理机给下一个就绪的进程，而被剥夺的进程返回到就绪队列的末尾重新排队，等候再次运行。

• 在时间片轮转调度算法中，时间片的大小对系统性能的影响很大。如果时间片足够大，以至于所有进程都能在一个时间片内执行完毕，则时间片轮转调度算法就退化为先来先服务调度算法。如果时间片很小，那么处理机将在进程间过于频繁切换，使处理机的开销增大，而真正用于运行用户进程的时间将减少。因此时间片的大小应选择适当。

• 时间片的长短通常由以下因素确定：系统的响应时间、就绪队列中的进程数目和系统的处理能力。

6.多级反馈队列调度算法（集合了前几种算法的优点）

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

例如:

• 为提高系统吞吐量和缩短平均周转时间而照顾短进程；

• 为获得较好的I/O设备利用率和缩短响应时间而照顾I/O型进程；同时，也不必事先估计进程的执行时间。

多级反馈队列调度算法的实现思想如下：

1. 应设置多个就绪队列，并为各个队列赋予不同的优先级，第1级队列的优先级最高，第2级队列次之，其余队列的优先级逐次降低。

2. 赋予各个队列中进程执行时间片的大小也各不相同，在优先级越高的队列中，每个进程的运行时间片就越小。例如，第2级队列的时间片要比第1级队列的时间片长一倍， ……第i+1级队列的时间片要比第i级队列的时间片长一倍。

3. 当一个新进程进入内存后，首先将它放入第1级队列的末尾，按FCFS原则排队等待调度。当轮到该进程执行时，如它能在该时间片内完成，便可准备撤离系统；如果它在一个时间片结束时尚未完成，调度程序便将该进程转入第2级队列的末尾，再同样地按FCFS 原则等待调度执行；如果它在第2级队列中运行一个时间片后仍未完成，再以同样的方法放入第3级队列……如此下去，当一个长进程从第1级队列依次降到第 n 级队列后，在第 n 级队列中便釆用时间片轮转的方式运行。

多级反馈队列的优势有：

1. 终端型作业用户：短作业优先。

2. 短批处理作业用户：周转时间较短。

3. 长批处理作业用户：经过前面几个队列得到部分执行，不会长期得不到处理。

作业与进程：

• 作业是用户向计算机提交任务的任务实体。在用户向计算机提交作业后，系统将它放入外存中的作业等待队列中等待执行。而进程则是完成用户任务的执行实体，是向系统申请分配资源的基本单位。任一进程，只要它被创建，总有相应的部分存在于内存中。

• 一个作业可由多个进程组成，且必须至少由一个进程组成，反过来则不成立

• 作业的概念主要用在批处理系统中，像UNIX这样的分时系统中就没有作业的概念。而进程的概念则用在几乎所有的多道程序系统中进程是操作系统进行资源分配的单位。

• 仅当第1级队列为空时，调度程序才调度第2级队列中的进程运行；仅当第1 ~ (i-1)级队列均为空时，才会调度第i级队列中的进程运行。如果处理机正在执行第i级队列中的某进程时，又有新进程进入优先级较高的队列（第 1 ~ (i-1)中的任何一个队列），则此时新进程将抢占正在运行进程的处理机，即由调度程序把正在运行的进程放回到第i级队列的末尾，把处理机分配给新到的更高优先级的进程。

在Windows下,进程又被细化为线程,也就是一个进程下有多个能独立运行的更小的单位.

而超线程是一种技术（并不能和进程，作业进行直接比对）：所谓超线程技术就是利用特殊的硬件指令，把多线程处理器内部的两个逻辑内核模拟成两个物理芯片，从而使单个处理器就能“享用”线程级的并行计算的处理器技术。多线程技术可以在支持多线程的操作系统和软件上，有效的增强处理器在多任务、多线程处理上的处理能力。

超线程技术可以使操作系统或者应用软件的多个线程，同时运行于一个超线程处理器上，其内部的两个逻辑处理器共享一组处理器执行单元，并行完成加、乘、负载等操作。这样做可以使得处理器的处理能力提高30%，因为在同一时间里，应用程序可以充分使用芯片的各个运算单元