一、进程调度概念
多道程序设计的目的在于无论何时都有程序在运行，使得CPU利用率打到最大化；分时系统的目的是在进程间快速切换cpu以便用户在程序运行时能与其进行交互；为了达到这样的目的，进程调度选择一个可用的进程(可能从多个可用进程集合中选择)到CPU上执行，余下的需要等待CPU空闲并重新调度；
调度队列：进程进入系统时，会被加载到作业队列中，该队列包括系统中的所有进程。驻留在内存中就绪的、等待运行的进程保存在就绪队列中，该队列通常用链表实现，头结点指向链表的第一个和最后一个PCB块的指针，每个PCB块包括一个指向就绪队列的下一个PCB的指针域；
附：Linux操作系统中进程控制块是用c结构的task_struct表示，这个结构包含了表示一个进程所需要的所有信息，包括进程状态、调度和内存管理信息、打开文件列表和指向父进程和所有子进程的指针；为一个双向链表
操作系统也有其他队列，当给进程分配了CPU后，开始执行并最终完成，或者中断或等待指定事件完成(如i/o请求)；等待特定i/o设备的进程列表称为设备队列，每个设备都有自己的设备队列；
二、调度程序
进程在生命周期中会在各种调度队列之间迁移，为了调度，操作系统必须按照某种方式从这些队列中选择进程，进程选择是由相应的调度程序完成（scheduler）
通常对于批处理系统，进程更多的是被提交，而不是马上执行，这些进程被放到大容量存储设备（通常为磁盘）的缓冲池中，保存在那里以便以后执行；
长期调度程序（long-termscheduler）或者作业调度程序（job scheduler）从该池中选择进程装入内存准备执行；而短期调度程序（short-term scheduler）和CPU调度程序从准备执行的进程中选择进程，并为之分配CPU；
三、调度算法
调度算法的性能衡量
1、面向用户
1、周转时间短；周转时间是指作业提交系统开始，直到作业完成的时间间隔：作业在外存后备队列中的等待时间、作业调入内存后创建的相应进程在就绪队列中的等待时间、进程在CPU上执行时间、进程等待某些操作完成后的时间；带权周转时间是指作业周转时间与作业实际运行服务时间的比值，平均周转时间和平均带权周转时间是衡量批处理系统调度算法的重要准则；
2、响应时间快：响应时间是从用户提交请求开始，知道系统首次产生响应为之的时间间隔，是衡量分时系统调度算法的重要准则；
3、截止时间保证：开始截止时间，指某任务必须开始执行的最迟时间，完成截止时间，指某任务必须完成的最迟时间；
4、优先权：批处理系统、分时系统、实时系统都可以优先执行优先级更高的作业；
2、面向系统：
1、吞吐量高：系统吞吐量，系统在单位时间内能完成的总得工作量，它与批处理系统中的作业长短有关，短作业执行时间段，吞吐量高，长作业相反；
2、CPU利用率：
3、资源的平衡利用：
调度的相关时间：
- 服务时间：作业需要运行的时间；
- 完成时间=开始时间+服务时间；
- 等待时间=开始时间-提交时间；
- 周转时间=完成时间-提交时间；
- 带权周转时间=周转时间/服务时间
响应比=（等待时间+服务时间）/服务时间=等待时间/服务时间+1；
3、调度算法
调度算法:约六种
1、先来先服务（fcfs）是最简单的调度算法，用以作业调度和进程的调度，按照作业进入系统后备作业队列的先后次序 来挑选作业，加入就绪队列，等待执行；fcfs是非抢占式的，易于实现，但是效率不高，性能不好，有利于长期作业（CPU繁忙性）而不利于短作业（i/o繁忙性）
2、短作业优先（short job first） 用于进程调度时又称为短进程优先调度算法short process first，该算法既可用于作业调度也可用于进程调度；在作业调度中，该算法每次从后备作业队列中挑选估计服务时间最短的一个或者几个作业，将他们调入内存，分配必要的资源，创建进程并放入就绪队列，在进程调度中的原理类似；
sjf是非抢占式的，优先照顾短作业，性能较好，减低平均等待时间，提高吞吐量，但是不利于长作业，长作业可能一直处于等待状态，出现饥饿现象，完全未考虑作业的优先紧迫度，不能用于实时系统；
3、最短剩余时间优先（SJF）本身是非抢占式的，用于抢占式调度系统时，对应的算法 最短剩余时间优先调度算法；该算法首先按照作业的服务时间挑选最短的作业运行，在该作业运行期间，一旦有新作业到达，并且该新作业的服务时间比当前运行作业的剩余服务时间短，则发生抢占，否则，当前作业继续运行，该算法确保一旦新的短作业或短进程加入能得到很快处理但是由于频繁的抢占和进程切换，系统开销大，算法实现代价高，一般用于实时系统；
4、高响应比优先：高响应比优先调度算法Highest Reponse Ratio First （HRRF） 是非抢占式，主要用于作业调度；
基本思想：每次进行作业调度时，先计算后备作业队列中每个作业的响应比，挑选最高的作业投入系统运行；
响应比=（等待时间+服务时间）/服务时间=等待时间/服务时间 +1；由响应比分析，该算法介于FCFS和SJF之间，但是每次需要计算每个作业的响应比，增加系统开销；
5、优先级：每次挑选优先级最高的一个或几个调入，可用于作业调度和进程调度，分为非抢占式和抢占式；
6、时间片轮转：RR-round Robin 用于分时系统的进程调度；
基本思想：系统将CPU处理时间划分为若干个时间片q，进程按照到达先后顺序排列，每次调度选择队首的进程，执行完一个时间片q后，计数器发出时钟中断请求，该进程移至队尾。以后每次调度都是如此。
该算法能在给定时间内响应所有用户请求，达到分时系统的目的，其性能主要取决于时间片q的大小，q太大则所有进程在一个q内完成，退外围FCFS；太小则进程频繁切换，开销大；该算法简单有效，常用于分时系统，但是不利于i/o频繁紧凑，由于这种进程用不完一个时间片，就因为等待i/o操作而阻塞，当i/o操作结束后，只能插入到就绪队列的末尾，等待下一轮调度；
【附】：
多级反馈队列 mutilevel feedback 综合调度算法，Unix BSD使用；
基本思想：设置多个就绪队列，第一级队列优先级最高，优先级高，时间片越短，优先级越低，时间片越长；
第一级队列为空时，开始调度第二级队列，依次类推；各级队列使用RR算法调度；当一个新建进程就绪后，进入第一级队列，进程用完时间片后，放弃CPU，进入下一级队列；
由于阻塞而放弃CPU的进程，进入相应的等待队列，一旦等待的事件发生，就回到原来的就绪队列；多级反馈队列对i/o型进程更友好；
评论区