处理机调度

处理机调度

基本概念

我们前面说过处理机cpu空闲时会在就绪态进程中挑选一个上cpu执行，这就是调度。当有一堆任务要处理，但由于资源有限，这些事情没有办法同时处理，这就需要某种规则来决定处理这些任务的顺序，这就是“调度”索要研究的问题。在多道程序系统中，进程的数量往往是多于处理机的个数的，这样不可能同时并行地处理各个进程。处理机调度，就是从就绪队列中按照一定的算法选择一个进程并将处理机分配给他使用，以实现进程的并发执行。

调度的三个层次

高级调度（作业调度）

由于内存的空间有限，有时无法将用户提交的所有作业全部放入内存中，因此就需要某种规则来决定将作业调入内存的顺序。高级调度（也叫做作业调度）就是按一定的原则从外存（硬盘等）上处于后备队列的作业中挑选一个（或多个）作业，给他们分配内存等必要资源，一旦进入内存就说明次进程被创建并处于了就绪态，所以需要操作系统创建并分配给其一个PCB，以使他们获得了竞争处理机的权利。

所以高级调度是外存（也叫辅存）与内存之间的调度。每个作业只调入一次，作业调入时会建立相应的PCB，作业调出时才撤销PCB，这也就说明当一个进程处于阻塞态下cpu后仍会存储在内存中随时准备上cpu，而只有当是终止态时才会从内存中取出然后作业调出。高级调度主要是指调入的问题，因为只有调入的时机需要操作系统确定，但调出的时机必然是作业运行结束才掉出。

中级调度（内存调度）

引入了虚拟存储技术后我们知道每次并不是将进程全部的数据放入内存，而是将常用的放入，而可将暂时不能运行的进程调至外存等待，等他重新具备了运行条件且内存又稍有空闲时，再重新调入内存，这么做的目的就是为了提高内存利用率和系统的吞吐量。暂时调到外存等待的进程状态为挂起状态（不是阻塞态），值得注意的是，PCB并不会一起调到外存，而是会常驻在内存中。PCB会记录进程数据在外存中存放的位置，进程状态等信息，操作系统通过内存中的PCB来保持对各个进程的监控和管理，被挂起的进程PCB会被放到挂起队列中。

中级调度（内存调度）就是要决定哪个处于挂起状态的进程重新调入内存，一个进程可能会被多次调出，调入内存，因此中级调度发生的频率要比高级调度更高。

思考：挂起状态在状态转换模型中的位置以及他和阻塞态的区别？

暂时调到外存等待的进程状态为挂起状态，挂起态又可以进一步分为就绪挂起和阻塞挂起两种状态。所以加上后5状态模型->7状态模型

低级调度（进程调度）

低级调度（进程调度）其主要任务是按照某种方法和策略从就绪队列中选取一个进程，将处理机分配给他（这个会涉及到很多种调度算法，后面会详细讲解）。进程调度是操作系统中最基本的一种调度，在一般的操作系统中都必须配置进程调度，进程调度的频率很高，一般几十毫秒一次。

思考：三种调度的联系与对比

总结

进程调度

这里我们详细展开对低级调度或者叫进程调度的详细研究。

进程调度的时机

进程调度就是按照某种算法从就绪队列中选择一个进程为其分配处理机。一般进程调度会发生在以下两种情况，当然，在某些系统中只允许进程主动放弃处理机（即只有上半部分功能），当然也有的系统除了可以进程主动放弃处理机以外，当有更紧急的任务需要处理时，也会强行剥夺该进程的处理机使用权给更加紧急重要的进程使用（被动放弃）。

一般是发生在运行态转换为其他状态，cpu空闲时发生。但是在以下的情况下一般进程调度很难发生

一定要注意第二点，是进程在操作系统内核程序临界区而不是进程自身处于临界区。当进程处于自身临界区时是可以进行处理机调度的。

思考：什么是临界区？什么是临界资源？

临界资源是一个时间段内只允许一个进程使用的资源，各进程需要互斥地访问临界资源。而临界区就是访问临界资源的那段代码。所以内核程序临界区就是一般用来访问某种内核数据结构的代码，比如访问进程的就绪队列（由个就绪进程的PCB组成）。

之所以此时一般不发生进程调度，是因为如果内核程序还没退出临界区（即临界资源还没解锁） 就进行进程调度，但是进程调度相关的程序也需要访问就绪队列， 但此时就绪队列被锁住了，因此又无法顺利进行进程调度，同时，内核程序临界区访问的临界资源如果不尽快释放的话，极有可能影响到操作系统内核的其他管理工作。因此在访问内核程序临界区期间不能进行调度与切换。但是当在进程处于临界区时是可以进行处理机调度的，例如：在打印机打印完成之前，进程一直处于临界区内，临界资源不会解锁。但打印机又是慢速设备，此时如果一直不允许进程调度的话就会导致CPU一直空闲内核程序临界区访问的临界资源如果不尽快释放的话，极有可能影响到操作系统内核的其他管理工作。因此在访问内核程序临界区期间不能进行调度与切换而普通临界区访问的临界资源不会直接影响操作系统内核的管理工作。因此在访问普通临界区时是可以进行调度和切换的。

进程调度的方式

非剥夺调度方式

又称为非抢占方式，即只允许进程主动放弃处理机（一般是通过系统调用陷入函数发送请求中断该进程），这种方式，在运行过程中即便有更紧迫的任务到达，当前进程依然会继续使用处理机，知道该进程结束或者主动要求进入阻塞态。这种方式明显不合理，但是实现简单，系统开销小但是无法及时处理紧急任务，一般适用于早期的批处理系统。

剥夺调度方式

又称为抢占方式，当一个进程正在处理机上执行时，如果有一个更重要或者更加紧迫的进程需要使用处理机，则操作系统会立即暂停正在执行的进程，将处理机分配给更加紧迫重要的进程。这种方式优先处理更紧急的进程，也可以实现让各进程按时间片流转执行的功能（通过时钟中断）。适用于分时操作系统，实时操作系统。

进程的切换与过程

思考：狭义的进程调度和进程切换的区别？

狭义的进程调度就是指从一个就绪队列中选出一个要运行的已就绪的进程（这个进程可以是刚刚被暂停执行的进程或者也可以是另一个进程，而后一种情况就需要进程切换）即仅仅是选择，进程切换是指一个进程让出处理机，由另一个进程占用处理机的过程。

广义的进程调度包括选选择一个进程和进程切换两个步骤，进程的切换过程主要完成了：

1. 对原来运行进程各种数据的保存
2. 对新的进程各种数据的恢复（如操作系统根据PCB对程序计数器，程序状态字寄存器PSW，各种段寄存器等处理机现场信息）

所以进程切换是有代价的，因此如果过于频繁的进行进程调度，切换必然会导致整个系统的效率降低，使得系统花费大量时间在进程切换上，而真正用于执行进程的时间减少。

总结

调度算法的评价指标

cpu利用率

因为早期的cpu造价昂贵（说实话现在对于学生来说也得吃好几天土。。），因此人们希望cpu尽可能的多工作，所以就引出了cpu利用率–用来描述cpu忙碌的时间占总时间的比例。

$$利用率=忙碌的时间/总时间$$

一般设备的利用率指的都是cpu利用率，如：某计算机只支持单道程序（单核），某个作业刚开始需要在CPU上运行5秒， 再用打印机打印输出5秒，之后再执行5秒，才能结束。在此过程中， CPU利用率、打印机利用率分别是多少？

很简单的计算：cpu利用率=5+5/5+5+5=66.6%，同理打印机利用率=33.3%。通常会考察多道程序并发执行的情况，可以使用“甘特图”来辅助计算。

思考：什么是甘特图？

就是横道图、条状图。其通过条状图来显示项目、进度和其他时间相关的系统进展的内在关系随着时间进展的情况。类似于下图：

系统吞吐量

对于计算机来说，希望能够尽可能用少的时间处理完尽可能多的作业，这就是系统吞吐量–单位时间内完成的作业的数量。

$$系统吞吐量=总共完成了多少道作业/总共花了多少时间$$

例如：某计算机系统处理完10道作业，共花费100秒，则系统吞吐量为？

10/100=0.1道/秒。

周转时间

对于计算机的用户来说，他最关心的就是自己的作业从提交（注意不是开始运行）到完成花费的时间。周转时间就是指从作业被提交给系统开始（一般是双击应用程序开始）到作业完成为止的这段时间间隔。一般周转时间由四部分组成：作业在外存后备队列上等待作业调度（高级调度）的时间、进程在就绪队列上等待进程调度（低级调度）的时间，进程在cpu上运行的时间、进程等待I/O操作完成（一半是阻塞态或者挂起态）的时间。后三个在一个作业的整个执行过程中，可能发生多次。

$$（作业）周转时间=作业完成时间-作业提交时间$$

上面的周转时间是指对于用户来说更加关心自己的单个作业的周转时间，而对于整个操作系统来说，更关系的是系统自身的整体表现即周转时间的平均值。

$$平均周转时间=各作业周转时间之和/作业数量$$

带权周转时间

因为有的作业运行时间长，有的作业运行时间短，因此在周转时间相同的情况下，运行时间不同的作业给用户的感受也是不一样的。可能有的作业虽然运行时间长会导致平均周转时间更大，但是其对用户产生的满意度更高，所以不能操作系统不能仅仅用平均周转时间来衡量，如果只追求平均周转时间短，那岂不是每次都会尽量做运行时间短的任务，但是可能运行时间更长的大型主机游戏对用户的满意度提升更高也就更主要。所以这里引出一个新的概念–带权周转时间。

$$带权周转时间=作业周转时间/作业实际运行的时间$$

因为一作业周转时间还包括等待时间，所以带权周转时间必然>=1，但是等待时间肯定是越小越好，所以操作系统需要尽量使带权周转时间和周转时间都是越小越好。

平均带权周转时间

当然肯定也会再引进一个平均带权周转时间的概念

$$平均带权周转时间=各作业的带权周转时间之和/作业数$$

思考：周转时间和带权周转时间的关系？

对于周转时间相同的两个作业，实际运行时间更长的作业在相同时间内被服务的时间肯定更多，相应的带权周转时间就更小，用户满意度更高。对于实际运行时间相同的两个作业，周转时间更短的带权周转时间更小，等待时间更短，用户满意度越高。

等待时间

计算机的用户希望自己的作业尽可能少的等待处理机，等待时间就是指进程（或作业）处于等待处理机状态时间（即处于就绪态）之和，等待的时间越长，带权周转时间越大，用户满意度越低。

对于进程来说，等待时间就是指进程建立后等待被服务的时间，在等待/O完成的期间其实进程也是在被服务的，所以不计入等待时间。对于作业来说，不仅要考虑建立进程后的等待时间，还要加上作业在外存后备队列中等待高级调度的时间。

一个作业总共需要被cpu服务多久，被I/O设备服务多久一般是确定不变的，因此调度算法其实只会影响进程/作业的等待时间，当然，和前面的指标类似，也有“平均等待时间”来评价整体性能的。

响应时间

对于计算机用户来说，会希望自己的提交的请求（比如通过键盘输入一个调试指令）尽早地开始被系统服务、回应，响应时间就是指从用户提交到首次产生相应的时间。