调度简介
当计算机系统是多道程序设计系统时，通常会有多个进程或线程同时竞争cpu,只要有两个以上的进程处于就绪状态，并且只有一个cpu可用，那么就必须选择下一个要运行的进程
完成这项工作的这一程序称作调度程序,该程序使用的算法叫做调度算法
何时调度
- 创建进程：创建一个新进程后需要决策是优先运行父进程还是子进程，由于这两种进程都处于就绪状态，是一个正常的调度，调度程序可以合法选择先运行父进程还是子进程
- 进程退出：从就绪进程中选择一个进程，如果没有就绪的进程，通常会运行一个系统提供的空闲进程
- IO阻塞：根据阻塞的原因决定选择调度的进程
- IO中断：通过抢占式和非抢占式算法决定调度
抢占式
一旦进程开始执行，调度就在进程从运行状态切换到就绪状态以及从等待状态切换到就绪状态时发生，称为抢先调度。
在这种调度中，资源(CPU周期)会在短时间内分配给该进程，如果遇到某些优先级更高的进程，则可以暂停当前进程以处理该进程。
非抢占式
一旦进程开始执行，调度将在进程终止或进程从运行状态切换到等待状态时进行。
在非抢占式调度中，调度程序在执行过程中不会中断当前正在运行的进程。 但是它等待进程完成其与CPU的执行，然后可以将CPU分配给另一个进程。
抢占式调度在执行过程的中间，执行被中断，而; 在非抢占式调度中，在执行过程中不会中断执行。
调度算法
批处理
先来先服务
使用队列数据结构实现
- 按照作业提交，或进程变为就绪状态的先后次序分派CPU；
- 新作业只有当当前作业或进程执行完或阻塞才获得CPU运行
- 被唤醒的作业或进程不立即恢复执行，通常等到当前作业或进程出让CPU,容易产生延迟。（所以，默认即是非抢占方式）
- 有利于CPU繁忙型的作业，而不利于I/O繁忙的作业（进程）。
最短作业优先
运行时间可以预知的非抢占式批处理调度算法，适用于所有作业都可同时运行
假设我们知道进程A,B,C,D的运行时间,A 8秒，B 4秒，C 4秒，D 4秒，由下图可知，选择B、C、D、A的顺序运行，平均等待时间最短
最短剩余时间优先
调度程序总是选择运行时间最短的那个进程优先执行
交互式
轮转调度
为每个进程分配一个时间片，进程在被允许的时间范围内执行，如果超出时间范围还在执行,cpu会剥夺该进程，并分配给另一个进程，如果进程提前执行完，cpu立即切换，是一种最公平、最简单的调度算法
时间片轮转会维护一张进程表，当一个进程用完它的时间片后，就会被移动到队列末尾
由于进程切换时，需要维护管理所需要的保存和装入的寄存器值及内存映像，各种更新表格和列表，会产生进程上下文切换，所以当时间片过短时，进程频繁切换，降低cpu效率，如果过长，会引起短的交互请求等待过程，通常时间片设置到20～50ms是比较合适的折中
优先级
维护优先级队列，每个进程被分配优先级权重，按优先级高低分配到优先级队列
多级队列
多级队列调度算法将就绪队列分成多个单独队列。根据进程属性，如内存大小、进程优先级、进程类型等，一个进程永久分到一个队列，每个队列有自己的调度算法。
队列之间划分时间片
- 最高优先级上进程运行一个时间片，次高优先级上进程运行两个时间片，再下级运行四个时间片，依次类推。
- 每次从队列头开始运行进程，每当一个进程在一个优先级队列中用完它时间片后就移到队列尾部；只有当高优先级队列为空时，才会从不为空的低优先级队列中选择进程运行；在低优先队列中等待时间过长进程将会移动高优先级队列
最短进程优先
对于批处理系统而言，由于最短作业通常可以伴随着最短相应时间，所以如果被应用到交互式系统中，那将是非常好的，而最短进程就可以看作是最短作业被应用到交互式系统
保证调度
保证调度算法是另外一种类型的调度算法,它向用户所做出的保证并不是优先运行,而是明确的性能保证,该算法可以做到调度的公平性。
一种比较容易实现的性能保证是处理机分配的公平性。如果在系统中有n个相同类型的进程同时运行,为公平起见,须保证每个进程都获得相同的处理机时间1/n
彩票调度
彩票数（ticket）代表了进程（或用户或其他）占有某个资源的份额。一个进程拥有的彩票数占总彩票数的百分比，就是它占有资源的份额。
实时
实时系统通常可以分为硬实时和软实时，前者的含义是必须满足绝对的截止时间，后者的含义是虽然不希望偶尔错失截止时间，但是可以容忍。在这两种情形中，实时性能都是通过把程序划分为一组进程而实现的，其中每个进程的行为是可预测和提前掌握的。这些进程一般寿命较短，并且极快地就运行完成。在检测到一个外部信号时，调度程序的任务就是按照满足所有截止时间的要求调度进程。
实时系统中的事件可以按照响应方式进一步分类为周期性（以规则的时间间隔发生）事件或非周期性（发生时间不可预知）事件。一个系统可能要响应多个周期性事件流。根据每个事件需要处理时间的长短，系统甚至有可能无法处理完所有的事件。例如，如果有m个周期事件，事件i以周期Pi发生，并需要Ci秒CPU时间处理一个事件，那么可以处理负载的条件是
c1/p1+c2/p2+......+cm/pm≤1
满足这个条件的实时系统称为是可调度的。
作为一个例子，考虑一个有三个周期性事件的软实时系统，其周期分别是100ms、200ms和500ms。如果这些事件分别需要50ms、30ms和100 ms的CPU时间，那么该系统是可调度的，因为 0.5 + 0.15 + 0.2 < 1。如果有第四个事件加入，其周期为1秒，那么只要这个事件是不超过每事件150ms的CPU时间，那么该系统就仍然是可调度的。在这个计算中隐含了一个假设，即上下文切换的开销很小，可以忽略不计。
实时系统的调度算法可以是静态或动态的。前者在系统开始运行之前作出调度决策；后者在运行过程中进行调度决策。只有在可以提前掌握所完成的工作以及必须满足的截止时间等全部信息时，静态调度才能工作。而动态调度算法不需要这些限制。