操作系统知识回顾---单机调度

一、处理机调度类型

处理机就是我们说的CPU了，那是系统中最关键的资源之一，所以其调度的过程影响到了系统的整体性能。一般的处理机调度可以根据调度对象分为长调度（作业调度）、中程调度（交换技术）、短程调度（进程调度）或者说进程状态切换更明白些。从调度算法角度，不同类型中的调度方法可以有相同的模型抽象出来，但是对于具体的问题，又有不同的算法实现。甚至于到了内存换页，磁盘调度都会考虑到这些调度算法的实现过程，他们的想法都是让最优的对象首先执行，提高系统的资源利用率。

实际上，调度过程与进程状态切换息息相关，从新建到加入就绪队列，可以看做长调度，从就绪到运行态就是短调度，从挂起态到激活态就是中程调度了。我们这里讨论的是进程调度，近程调度，CPU调度，都是一个事儿。

进程调度的任务是控制和协调进程之间对CPU的竞争，换句话说，调度过程就是从就绪队列中选择将要执行的进程的过程。调度算法要解决三个问题：如何调度？何时调度？调度过程？

常见的调度算法这里就不罗列了，遍地都是。说一下调度时机吧，考虑两个角度，系统协调者角度：进程终止；进程阻塞；I/O中断；时钟中断等各种让出CPU的事件。进程角度：新进程创建后进入就绪队列，可以被调度；实际上，就绪队列更新后会发生新的调度事件，也就是调度时机。甚至可以这样说，跟运行态相关联的状态列表发生变更的时候，都会有调度事件发生。

调度事件发生后，需要进行进程切换的活动，说到底，进程的切换源于进程状态的转变，进程状态切换又基于调度时机和调度事件的发生。那么，进程切换过程中有会有那些步骤呢？

1.保存进程上下文信息到将要切换出的进程PCB中；

2.用新状态和其他信息更新即将切换出CPU的进程PCB；

3.将切换出的进程移到合适的队列；

4.选择另一个进程，就绪队列中没有进程时，运行IDLE；

5.更新被选中的进程PCB；

6.将被选中的进程信息装入系统上下文。

二、设计调度算法的原则

我们考虑调度算法的依据是被调度对象的种类，也就是进程的类型。一般情况下，有

交互式进程：需要经常与用户交互，花大量时间等待用户输入，响应时间要短，在用户可以忍受的范围内；

批处理进程：不必与用户交互，通常后台运行，不必计算响应时间，关注的是系统吞吐率和执行效率；

实时进程：对响应时间有刚性需求，不能被低优先级进程阻塞。

由于不同的系统类型有不同的用户需求，从而导致不同的调度算法。我们在选择调度算法的时候，从这个基本点出发，并遵循下边的规则。

进程控制块中的相关信息 ；进程优先级及就绪队列的组织 ；时间片大小选择及设置；抢占式调度与非抢占式调度 ；衡量指标（周转时间、归一化周转时间） ；调度器的开销 ；能否恒定（不依赖于当前系统负载）；调度机制和调度策略分离的原则 ；是否会产生“饥饿” 。

三、典型调度算法

现在比较火的就是基于优先级的调度策略，那么我们有必要将优先数提前讲一下。在系统中，有静态优先数和动态优先数两种，顾名思义，静态就是在进程创建之初便赋予了优先级，而且在其生命周期中不会改变，动态优先级就不同了，也是在进程创建时给出的优先级，但随着系统运行，优先数会进行重算。如果把两者比作常量和变量，理解起来会方便一些。

有了优先级，就会有高优先级对低优先级的抢断，这种资源的抢断叫做抢占，有两种占用CPU的方式：可抢占式，不可抢占式。这种方式是在进程创建之初定义的，有的系统干脆将抢占形式做到了系统中，也就是说某一个系统只能是抢占或非抢占的系统。当然现在看来，那已经过时了。不过系统一直保留一种自带的抢占CPU的方式，那就是时间片。

时间片就是根据系统时间，向就绪队列中的进行发放的可运行时间段。根据不同复杂度的系统，也会有可变时间片的出现。当然最关键的问题在于，如何设置时间片，一个时间片设置为多大。一般情况下，时间片的大小依据切换进程的开销，系统响应时间的要求，就绪进程的个数等多个因素来权衡。

讲完这些基本的概念，我们来看一下最重要的部分，调度算法，从三种不同的进程系统方向来区分：

批处理系统

先进先出：最简单高效公平的方式；

短作业优先：使用贪婪算法，但会导致长作业饿死；

短剩余时间优先：跟短作业相似，只不过会查看当前系统中各个进程的运行状态；

高响应比优先：作业周转时间/作业处理时间，数值越大表示等待越久，越急需上CPU。

交互式系统

轮转调度：根据系统分配给就绪队列中的每一个进程的时间片进行轮转调度；

优先级调度：为等待的进程分配优先级，高优先级可以中断低优先级的进程，抢占CPU执行，这样会使低优先级进程饿死；

多级队列：为进程等待按照优先级先后分为多个等待队列，同等优先级在同一个队列，同一个队列内部可以按照RR调度，也可以按照高响应比调度；

最短进程优先：跟短作业优先相似；

公平竞争共享：这是一个理想的状态，真正的公平是不存在的；

保证调度：跟公平共享相同，为了达到公平，系统总是计算各个进程的运行时间，然后让等待时间最久的上CPU

彩票调度：类似于彩票制度，系统给每一个进程发放调度号，然后每一次都会随机产生一个调度号，与调度号一致的进程得以运行。

实时调度

调度算法比较单一，为了达到及时响应，可以计算进程的紧急程度，为各个进程调度进行简单的分配，实际上，进程的调度和切换带来的开销对于实时系统来讲是致命的。所以，尽量少的进行调度就是最好的算法。
常见操作系统采用的调度策略：

UNIX动态优先级

BSD多级反馈调度队列

Windows基于优先级的抢占式多任务调度

Linux抢占式调度

Solaris综合调度算法

四、调度实例--windows

windows 中，调度对象是线程，上文已讲，windows是基于优先级的抢占式多任务调度算法，但是应该注意，不同的处理机个数，其调度算法是不同的。

就绪线程按照优先级进入等待队列；系统总是先运行优先级高的线程；同一个优先级的线程按RR进行调度。

线程调度时机

引用调度部分的一句话，当与运行态相关联的队列中发生变化时，就是调度时机了。还有一种情况是系统或者线程本身因为系统调用而改变了优先级，产生调度事件；

Windows中使用32个优先级，分为三类，实时优先级，可变优先级，系统线程。其中有几个特殊的优先级编号，比如0号优先级用于对系统中空闲的物理页面清零。