7月28日学习笔记

缺点：可能导致饥饿，连续的短进程流会使长进程无法获得CPU资源；需要预知未来，如何预估下一个CPU计算的持续时间？

预测的简单解决办法：

询问用户：1、用户欺骗就杀死进程；2、用户不知道怎么办

用历史的执行时间来预估未来的执行时间 T(n+1)=atn+(1-a)Tn，其中0<=a<=1，tn为第n次的CPU计算时间，T(n+1)为第n+1次的CPU计算时间预估，a为衰减系数

最高响应比优先算法（HRRN）

选择就绪队列中响应比R值最高的进程

R=(w+s)/s w:等待时间(waiting time) s:执行时间(service time)

在短进程优先算法的基础上改进

不可抢占

关注进程的等待时间

防止无限期推迟，因为等的时间越长，优先级越高，最终会变成最高优先级，所以能得到CPU的使用权

11.4 时间片轮转、多级反馈队列、公平共享调度算法和ucore调度框架

时间片：分配处理机资源的基本时间单元

算法思路：

时间片结束时，按FCFS算法切换到下一个就绪进程

每隔（n-1）个时间片进程执行一个时间片q

RR算法开销：

额外的上下文切换

时间片太大

等待时间过长

极限情况退化成FCFS

时间片太小

反应迅速，但产生大量上下文切换

大量上下文切换开销影响到系统吞吐量

时间片长度选择目标：

选择一个合适的时间片长度

经验规则：维持上下文切换开销处于1%以内

多级队列调度算法（MQ）

就绪队列被划分成多个独立的子队列，如，前台（交互）、后台（批处理）

每个队列拥有自己的调度策略，如：前台-RR、后台-FCFS

队列间的调度

固定优先级

先处理前台，然后处理后台

可能导致饥饿

时间片轮转

每个队列都得到一个确定的能够调度其进程的CPU时间

如：80%CPU时间用于前台，20%CPU时间用于后台

多级反馈队列算法（MLFQ）

进程可在不同队列间移动的多级队列算法

时间片大小随优先级级别增加而增加

如进程在当前的时间片没有完成，则降到下一个优先级

特征：CPU密集型进程的优先级下降很快，IO密集型进程会停留在高优先级上

公平共享调度（FSS，Fair Share Scheduling）

FSS控制用户对系统资源的访问

一些用户组比其它用户组更重要

保证不重要的组无法垄断资源

未使用的资源按比例分配

没有达到资源使用率目标的组获得更高的优先级

11.5 实时和多处理机调度

实时调度是对时间有要求的调度算法

实时操作系统：正确性依赖其时间和功能两个方面的OS

性能指标：

时间约束的及时性（deadlines）

速度和平均性能相对不重要

特征：时间约束的可预测性

实时任务：任务（工作单元）：一次计算，一次文件读取，一次信息传递等

任务属性：完成任务所需要的资源；定时参数

周期实时任务：一系列相似的任务

任务有规律的重复，周期p=任务请求时间间隔（0<p）

执行时间e = 最大执行时间（0 < e < p）

使用率U=e/p

硬时限（Hard deadline）：错过任务时限会导致灾难性或非常严重的后果；必须验证，在最坏情况下能够满足时限

软时限（Soft deadline）：通常能满足任务时限，如有时不能满足，则降低要求；尽力保证满足任务时限

可调度性：一个实时操作系统能够满足任务时限要求

需要确定实时任务的执行顺序

静态优先级调度

动态优先级调度

静态调度算法：速率单调调度算法（RM，Rate Monotonic）

通过周期安排优先级

周期越短优先级越高

执行周期最短的任务

最早截止时间优先算法（EDF，Earliest Deadline First）

截止时间越早优先级越高

执行截止时间最早的任务

多处理器调度

特征：多个处理机组成一个多处理机系统；处理机间可负载共享；

对称多处理器（SMP，Symmetric multiprocessing）调度

每个处理器运行自己的调度程序

调度程序对共享资源的访问需要进行同步

静态进程分配

进程从开始到结束都被分配到一个固定的处理机上执行

每个处理机有自己的就绪队列

调度开销小

各处理机可能忙闲不均

动态进程分配

进程在执行中可分配到任意空闲处理机执行

所有处理机共享一个公共的就绪队列

调度开销大

各处理机的负载是均衡的

11.6 优先级