操作系统调度设计

0.调度算法的目标

所有系统

• 公平-给每个进程公平的CPU份额
• 策略强制执行-看到所宣布的策略执行
• 平衡-保持系统的所有部分都忙碌

批处理系统

• 吞吐量-每小时最大作业数
• 周转时间-从提交到终止间的最小时间
• CPU利用率-保持CPU始终忙碌

交互式系统

• 响应时间-快速响应请求
• 均衡性-满足用户的期望

实时系统

• 满足截止时间-避免丢失数据
• 可预测性-在多媒体系统中避免品质降低

---

一.批处理系统中的调度

1.先来先服务

先到来的服务，系统先对其进行服务 FIFO

2.短作业优先

评估当前作业中，运行时间最短的作业优先服务

• 能够提前掌握作业的运行时间
• 只有所有作业是同时运行时调度才是最优的

3.最短剩余时间优先

当一个作业到达时，评估当前系统中作业的剩余时间和该作业所需时间，选择剩余时间最小的进行调度

• 能够提前掌握作业的运行时间

二.交互式系统中的调度

1.轮转调度

每个进程被分配一个时间片，如果时间片内没做完则强制切换，提前做完提前切换

• 进程切换(上下文切换)需要cpu时间
• 时间片太短，频繁切换影响效率；时间片太长，可能使短交互请求响应时间变长
• 时间片长度相同

2.优先级调度

每个进程拥有不同的优先级，优先调度优先级高的进程，同优先级的进程采用轮转调度。

• 时间片长度相同

3.多级队列

调度系统拥有不同优先级的队列，每个队列的时间片长度不同，进程依情况加入不同的队列中，调度中的进程可能由于时间片用完导致转移到较低级别队列

• 目的是最大可能的减少切换，同时又不影响高优先级的响应时间

注：伯克利XDS940分4个优先级 中断、I/O，短时间片，长时间片

4.最短进程优先

从当前可用进程中找出最短的一个进程进行调度
评估算法为 $T_0=aT_0+(1-a)T_1$
$a$：权值
$T_0$：当前估计时间
$T_1$：测量其下一次运行时间

• 这种通过当前测量值和先前估计值进行加权平均而得到下一次估计值的技术称作老化
• 权值($a$)越高老化的越慢,反之越快

5.保证调度

保证n个进程/用户获得CPU处理能力的$1 \over n$，选择$k$最低的进程进行调度，直到其值小于最近接该进程的竞争者
比率计算 $k= \frac {T_0} {T_1}$
$T_0$ ：实际获得时间，进程自创建以来该进程实际获得时间
$T_1$ ：应得时间，进程自创建以来过去的时间除以n

• 在运行中动态的保证

6.彩票调度

每个进程拥有f份彩票，所有进程总彩票为m，则每个进程的被调度几率为$f\over m$

• 在一些其他方法不易解决的问题中，此方法有易理解的优势
• 例如：视频服务器的若干进程为客户提供服务，每个进程的帧数率为10、20、25帧，则给每个进程10 20 25份彩票，最终CPU划分将以10:20:25进行划分

7.公平分享调度

在进程调度前先判断进程的所有者是谁，以保证用户之间的调度公平

三.实时系统中的调度

可调度：满足$\sum_{i=1}^m \frac {C_i}{P_i} \leq1$
$m个周期事件，事件i以周期P_i发生需要C_i秒处理$

• 硬实时：必须满足绝对截止时间
• 软实时：偶尔可以容忍
• 根据事件是否以规则时间间隔发生，将事件分为周期性和非周期性

四.策略与机制

为了使用户进程参与有关调度决策，可以将调度机制与调度策略分离，也就是将调度算法以某种形式参数化，而参数可以由用户进程填写

五.线程调度

线程调度的分类：分为用户级线程和内核级线程

1.用户级线程

• 调度系统(内核)决定哪个进程获得时间片
• 进程中的线程调度程序决定具体线程运行
• 同一时间片只会有该进程的线程运行
• 不必修改内存映像，不清除高速缓存内容
• 可使用自定制的线程调度
• 某线程的I/O阻塞时，整个进程可能被挂起
• 缺乏一个时钟对线程中断(例如某个线程相对运行过长)

2.内核级线程

• 内核直接选择一个线程运行
• 切换不同的线程时，需要完整的上下文切换
• 线程阻塞在I/O上不需要挂起整个进程