2.4 进程调度 首先明白两个概念：多个进程处于就绪态而CPU只有一个时，CPU必须决定先运行那个进程，这个起决定作用的就是调度器（scheduler），使用的算法就是调度算法（scheduler algorithm）.
2.4.1 调度介绍进程行为 进程行为有两种：I/O请求和CPU计算，两者交替进行。当然，并不是说所有与I/O有关的都是I/O操作，比如说CPU向视频RAM输入以更新屏幕时，由于CPU参与了，就算CPU计算，而真正的I/O操作是指进程进入阻塞等待外部设备完成工作，才是I/O的执行过程
有些进程I/O的时间长，有的CPU计算时间长，根据这个不同分为
计算密集型（compute-bound）和
I/O密集型（I/O-bound）。值得一提的是I/O密集型之所以是I/O密集型，不是因为它所执行的I/O请求时间长，而是因为I/O请求之间的CPU计算较少，说白了就是间隔小。
调度的时机 首先看肯定会发生调度的情况：
下面几种情况不是必须的，但经常发生
注意，“I/O中断发生”是指完成了I/O部分的操作，而不是阻塞进程，此时可以考虑调度因为该设备引起阻塞的进程。
时钟中断是指进程运行完自己的时间片之后发生的中断。根据如何处理时钟中断可以把调度算法分为两类：
- 非抢占式调度算法（non-preemptive scheduling algorithm）：挑选一个进程，一直运行到阻塞或自愿退出。
- 抢占式调度算法（preemptive scheduling algorithm）：挑选一个进程，所运行的最大时间是固定的，到时间之后进程会被挂起，调度器选择另一个进程运行。
调度算法的分类 不同的环境下不同。区分以下三种系统：
- 批处理：非抢占式或者拥有较长时间间隔的抢占式比较适合
- 交互式：抢占式
- 实时
调度算法的目标 几个衡量标准：
- 吞吐量：系统每秒完成的作业数量。越大越好
- 周转时间：作业提交到处理完毕的平均时间间隔，衡量一个用户等待一个输出的平均时间。越短越好
- CPU利用率：越大越好
2.4.2 批处理系统中的调度先到先服务（first-come first-servered）
进程按照请求CPU的顺序使用CPU。
优点是简单，易于理解。
缺点是特定情况下进程完成情况差。
最短作业优先 适用于运行时间可以预知的批作业处理。非抢占式调度算法。
只有在所有作业同时启动才是最优的。
最短剩余时间优先（shortest remaining time next）
最短作业优先的抢占式版本。运行时间必须预知，新作业到来时，与剩余时间作比较。
三级调度 所谓的三级调度指以下三种：
- 准调度器（admission scheduler）：决定哪些作业进入系统。
- 内存调度器：决定哪些进入系统的作业调入内存，剩余的存入磁盘。
- CPU调度器：在内存中选择下一个要执行的进程。
2.4.3 交互系统中的调度时间片轮转调度（quantum round robin）
进程在时间片内运行，时间片结束时CPU将被抢占并分配给其他进程。如果在时间片前阻塞或结束，立即切换CPU
一个问题是时间片多长，太短进程老切换，每次进程切换（process switch）或上下文切换（context switch）都要耗时，这样就降低CPU效率了；太长吧，又引起对短的交互请求的响应变差。一般比较合理的是20-50ms。
优先级调度（priority scheduling）
每个进程被赋予一个优先级，先运行优先级高的就绪进程。
为了防止高优先级的进程无休止运行，可以考虑在么个时钟中断时降低进程的优先级；或者结合时间片。
多重队列 属于最高优先级的进程运行1个时间片，次高级的2个时间片，再次一级的4个时间片。。。
随着进程优先级不断降低，运行频度逐渐放慢（实际就是每次运行的时间长了）。假设一个进程需要计算100个时间片，第一次运行一个时间片，第二次运行2个时间片，第三次4个，8，16。。。，最后一次是分配给它64个时间片，只需运行其中的37即可，这样一共装入了7次，而采用纯粹的时间片的话要装入100次。
最短进程优先 问题在于如何选出中运行时间最短的进程。一种方法是根据过去的行为进行推测。假设某终端上每条命令估计运行时间为T0，假设测量到其下一次运行的时间为T1，则用这两个值进行加权平均来计算。aT0+(1-a)T1。
保证调度算法 向用户做出明确的性能保证，然后去实现。
彩票调度算法（lottery scheduling）
为进城发放针对系统各种资源的（如CPU时间）的彩票。随机进行选择。重要的进程会分发格外的彩票以提升其中奖概率
公平分享调度 考虑进程的拥有者是谁，为进程的拥有者分配资源。
2.4.4 实时系统调度 实时系统是那些时间因素非常关键的系统。
实时系统分为：
- 硬实时（hard real time）：存在必须满足的时间限制。
- 软实时（soft real time）：偶尔超过限制是可以容忍的。
实时响应的事件分为周期性（每隔一段固定时间发生）和非周期性（在不可预测的时候发生）。
假设有m个周期性事件，事件i的周期是Pi，其中每个事件i需要Ci秒的CPU事件来处理，则只有满足条件
才可能处理所有的负载。称为
可调度的（schedulable）。
实时调度可以是静态或动态，前者在系统启动之前完成所有决策，后者在运行中完成决策。
2.4.5 策略与机制 有时主进程明确知道子进程的重要程度，但是前面所说的所有调度算法都没有从用户进程接受有关的调度决策信息。导致调度器无法做出最优选择。
解决办法是将
调度机制（scheduling mechanism）和
调度策略(scheduling policy)分开。
机制存在于内核中，策略可以由用户程序指定。
2.4.6 线程调度 两个层次的并行：进程级和线程级。具体的处理要看系统支持的是用户级进程还是内核级进程。
- 用户级进程，内核无法感知，所以以进程为单位调度，进程内部的线程调度器进行调度常用的是轮转调度和优先级调度。存在的唯一约束是没有时钟中断来打断运行了足够长时间的线程。
- 内核级线程，内核调用的单位，可以跨进程进行调度。
两者区别在于表现的性能。用户线程简单，内核线程要进行完整的上下文切换，修改内存映射等操作，比用户线程慢几个数量级。另一方面，用户级线程阻塞则阻塞整个进程；内核线程不会出现这种情况。
阅读(857) | 评论(1) | 转发(0) |
