操作系统-进程调度策略
1. 什么是进程
进程是操作系统进行资源分配的基本单位，每个进程都有它自己的内存空间和系统资源。进程实现了多处理机环境下进程调度，分派，切
换时，都需要花费较大的时间和空间开销；
为了提升系统的执行效率，减少CPU的【空转时间】和【调度切换】的时间，以便于系统的管理，所以有了线程的概念，线程是系统进行
资源调度的最小单位。一个进程包含一个或者多个线程，一个进程下的线程共享这个进程的资源。进程与进程之间的资源是不共享的，线
程和线程之间的资源也是不共享的。
2.什么是进程调度算法
当CPU有很多任务需要处理时，由于资源有限，不可能同时执行所有的作业和任务，这就需要确定一个规则来确定任务的执行顺序，这种
方式或者规则被称为调度算法。
进程有三种状态
- 运行态（running）： 正在占用CPU资源，正在运行中
- 就绪态（ready）：进程具备运行条件，等待系统分配CPU来运行
- 态阻塞 （wait）: 进程不具备运行条件，正在等待某个时间的完成
所谓进程调度，就是从进程的就绪队列（阻塞）中按照一定的算法选择一个进程并将 CPU 分配给它运行，以实现进程的并发执行。
这是操作系统中最基本（最低级）的一种调度，在一般的操作系统中都必须配置进程调度。 进程调度的频率很高，一般几十毫秒一次。
3、进程调度算法分类
进程调度算法分为两种：
- 抢占式调度：系统会按照进程的优先级高低来进行调度，进程之间可以插队，适合分时和实时OS
- 非抢占式调度：系统按照进程先到先服务的方式调度，进程之间不能插队，简单，系统开销较小。
4、调度算法介绍
4.1 先来先服务算法FCFS
按照作业提交或进程变为就绪状态的先后次序,分派CPU；
当前作业或进程占用CPU，直到执行完或阻塞，才出让CPU(非抢占方式)。
在作业或进程唤醒后(如I/O完成)，并不立即恢复执行，通常等到当前作业或进程出让CPU。是最简单的算法。
在进程调度中采用FCFS算法时，则每次调度是从就绪队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。该进程一
直运行到完成或发生某事件而阻塞后才放弃处理机
FCFS算法属于非抢占（剥夺）调度算法，这种算法比较简单，能够保证不会出现饥饿现象，但是，如果很多长时间作业先到达，后面大部分是短时间作业，这种方式对于后面的短时间任务不太友好。
4.2 短进程/作业优先算法SJF
短作业(进程)优先调度算法SJ(P)F，是指对短作业或短进程优先调度的算法。它们可以分别用于作业调度和进程调度。短作业优先(SJF)的调
度算法是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。而短进程优先(SPF)调度算法则是从就绪队列
中选出一个估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时再重新
调度。
1)优点
- 1)比FCFS改善平均周转时间和平均带权周转时间，缩短作业的等待时间；假定所有任务同时到达，平均等待时间最短。
- 2)提高系统的吞吐量。
2)缺点
- 1)对长作业非常不利，可能长时间得不到执行；长作业可能被饿死。
- 2)未能依据作业的紧迫程度来划分执行的优先级。
- 3)难以准确估计作业(进程)的执行时间，从而影响调度性能。
4.3 最高响应比优先算法HRN
FCFS方式只考虑每个作业的等待时间而未考虑执行时间的长短，而SJF方式只考虑执行时间而未考虑等待时间的长短。
因此，这两种调度算法在某些极端情况下会带来某些不便。
HRN调度策略同时考虑每个作业的等待时间长短和估计需要的执行时间长短，从中选出响应比最高的作业投入执行。
(1)优点
1)同时到达任务，短者优先。等待时间相等时，服务时间越短，优先级越高，符合SJF思想。
2)长作业随等待时间增加响应比增加。服务时间相等时，等待时间越长，优先级越高。对于长作业，只要其等待时间足够长，也能获
得处理机。
(2)缺点
1)吞吐量降低。这种算法是介于FCFS和SJF之间的一种折中算法。由于长作业也有机会投入运行，在同一时间内处理的作业数显然要
少于SJF法，从而采用HRN方式时其吞吐量将小于采用SJF法时的吞吐量。
2)系统开销增加。原因在于每次调度前要计算响应比。
4.4 最高优先数算法
在进程调度中，每次调度时，系统把处理机分配给就绪队列中优先数最高的进程。它又分为两种：非抢占式优先数算法和抢占式优先数算法。
在非抢占式优先数算法下，系统一旦把处理机分配给就绪队列中优先数最高的进程后，这个进程就会一直运行，直到完成或发生某事
件使它放弃处理机，这时系统才能重新将处理机分配给就绪队列中的另一个优先数最高的进程。
在抢占式优先数算法下，系统先将处理机分配给就绪队列中优先数最高的进程度让它运行，但在运行的过程中，如果出现另一个优先
数比它高的进程，它就要立即停止，并将处理机分配给新的高优先数进程。
在抢占式优先数算法下会麻烦一些。
4.5 时间片轮转调度算法
轮转(Round Robin，RR)调度算法是让每个进程在就绪队列中的等待时间与享受服务的时间成正比例。该算法适用于分时系统
每个进程所享受的CPU处理时间都是一致的。
过程：
- 将系统中所有的就绪进程按照FCFS原则，排成一个队列。
- 每次调度时将CPU分派给队首进程，让其执行一个时间片。时间片的长度从几个ms到几百ms。
- 在一个时间片结束时，发生时钟中断。
- 调度程序据此暂停当前进程的执行，将其送到就绪队列的末尾，并通过上下文切换执行当前的队首进程。
- 进程可以未使用完一个时间片，就出让CPU，如进程阻塞时。
4.6 最短剩余时间优先算法
最短剩余时间优先(Shortest Remaining Time Next，SRTN)调度算法多用于剥夺式的调度中。
在进程调度中，每次调度时，系统把处理机分配给就绪队列中运行完所需时间最短的进程。
最短剩余时间优先算法也可用于不剥夺式调度方式中，此时退化为短作业优先算法。
也就是短作业优先算法的升级版，只不过它是抢占式的。
4.7 多级反馈排队算法
设置多个就绪队列，分别赋予不同的优先级，如逐级降低，队列1的优先级最高。每个队列执行时间片的长度也不同，规定优先
级越低则时间片越长，如逐级加倍。
新进程进入内存后，先投入队列1的末尾，按FCFS算法调度；若按队列1一个时间片未能执行完，则降低投入到队列2的末尾，同样按
FCFS算法调度；如此下去，降低到最后的队列，则按“时间片轮转”算法调度直到完成。
仅当较高优先级的队列为空，才调度较低优先级的队列中的进程执行。如果进程执行时有新进程进入较高优先级的队列，则抢先执行
新进程，并把被抢先的进程投入原队列的末尾。
可以发现，对于短作业可能在第一队列中很快被处理完成，对于长作业，如果在第一队列中没有被执行完成，则会移入等待队列被执行，虽然等待时间变长了，但是运行时间也变长了，所以这种算法很好的兼容了长短作业，同时有比较好的响应时间。
4.8 系统算法使用场景
批处理系统、分时系统和实时系统中，各采用哪几种进程（作业）调度算法？
批处理系统常用调度算法：
①、先来先服务：FCFS
②、最短作业优先
③、最短剩余时间优先
④、响应比最高者优先
分时系统调度算法：
①、轮转调度
②、优先级调度
③、多级队列调度
④、彩票调度
实时系统调度算法：
①、单比率调度
②、限期调度
③、最少裕度法
5、操作算法性能指标
5.1 CPU利用率
CPU忙碌时间占总时间的比例
5.2 系统吞吐量
系统吞吐量 = 作业完成量 / 完成时间
利用尽可能少的时间处理尽可能多的作业；
5.3 周转时间
周转时间 = 完成时间 - 到达时间点
平均周转时间 = 周转时间和 / 作业数
带权周转时间 = 周转时间 / 作业实际运行时间， 这个时间肯定大于等于1，并且数值越小，说明算法越好。
平均带权周转时间 = 带权周转时间和 / 作业数
从作业被提交到系统到作业完成所经历的时间都有哪些部分？
5.4 等待时间
等待处理机时间之和： 等待时间 = 周转时间 - 运行时间（- IO时间）
这个等待时间越大，说明算法越差，作业需要考虑等待高级调度的时间，而进程是不需要的。
5.5 响应时间
从提交请求到产生首次响应的时间
5.6 饥饿
进程或作业长时间得不到服务，这种现象称之为“饥饿”