操作系统笔记5

CPU调度

多道程序是为了是的CPU在任何时候都有某些进程运行，以使得CPU使用率最大化，多个进程可以同时存在内存中，当一个进程必须等待时，操作系统会从该进程拿走CPU使用权，将CPU使用权交给其他进程。

CPU-I/O区间周期

进程的执行由CPU执行和I/O等待周期组成。进程执行从CPU区间，CPU burst开始，之后是I/O区间，I/O burst，接着是另一个CPU区间，接着是另一个I/O区间…如此循环，最终最后的CPU区间通过系统请求终止执行。

进程的执行包括CPU执行和I/O等待
进程在着两种状态中切换

I/O约束程序通常具有很多短CPU区间，CPU约束程序可能有少量长CPU区间。这种分布有助于选择合适的CPU调度算法。

CPU调度程序

每当CPU空闲时，操作系统就必须从就绪队列中选择合适的一个进程来执行，进程的选择由CPU调度程序，或短期调度程序执行。调度程序从内存中选择合适的进程，为它分配CPU。

CPU调度程序执行的时机：

进程从运行到等待：进程主动放弃CPU，此时CPU为空，是非抢占式的
进程从运行到就绪：进程时间片到了，或有更高优先级的进程来了，是抢占式的
进程从等待到就绪：此时CPU调度程序会判断一下优先级，就绪队列中每来一个新进程，就会引起调度程序判断优先级。是抢占式的，但不一定抢占CPU
进程终止：非抢占式的。

分派程序

与CPU调度功能有关的另一个部分是分派程序。分派程序用来将CPU的控制交给由短期调度程序选择的进程。功能包括：

上下文切换
切换到用户模式
跳转到用户程序的合适位置（PC中存有下一条指令），以重新启动程序

调度准则

为了比较CPU调度算法，有许多准则，包括：

CPU利用率
吞吐量
周转时间：后备队列时间+宏观运行时间。即：后备等待高级调度的时间+在ready队列的时间之和+在running状态的时间之和+在waiting队列的时间之和
等待时间：在就绪队列中等待所花费的时间之和
响应时间：提交请求到产生第一响应的时间

CPU调度——调度算法

附：进程调度Gantt图（以FCFS为例）：

进程	区间时间
P1	24
P2	3
P3	3

先到先服务调度（FCFS）

即排队。先进入ready队列的进程先调度。

FCFS调度算法是非抢占的，FCFS算法对于分时系统是特别麻烦的，允许一个进程保持CPU时间过长将是一个严重的错误。

优点：简单
缺点：效率低

最短作业优先调度（SJF）

将每个进程与其下一个CPU区间段相关联。当CPU空闲时，会赋给具有最短区间段的进程。

采用指数平均法来预估预测下一CPU区间

优点：平均等待时间更低
缺点：对长作业不利，可能永远无法得到调度

优先级调度

SJF算法可以作为优先级调度的一个特例。

每一个进程都有与其关联的优先级。优先级最高的进程会分配到CPU

优先级调度可以是抢占或非抢占的。

优先级调度算法的一个主要问题是无穷阻塞或饥饿，解决方法是老化

轮转调度法（时间片轮转，Round-Robin）

专门为分时系统设计的。

定义了一个较小时间单元，称为时间片，通常在10-100ms。CPU调度程序循环就绪队列，为每个进程分配不超过一个时间片的CPU。

在极端情况下，如果时间片非常大，rr算法将和fcfs算法一样。如果时间片非常小，rr算法称为处理器共享

多级队列调度

将就绪队列划分成：

前台（交互）进程
后台（批处理）进程

在前台队列实行RR调度，在后台队列实行FCFS调度。前台进程有更高的优先级

优点：低调度开销

缺点：进程被永久分配到一个队列中，不够灵活

多级反馈队列调度

多级反馈队列调度算法允许进程在队列之间移动

每个队列有不同的优先级
每个队列都是RR，且时间片逐渐加大
所有新进程都入最高优先级

如果在调度非最高优先级队列时，有新进程进入：

抢占式：当前进程回原队队尾
非抢占式：等待时间片完

附：进程挂起的原因

系统负荷过重
进程中间结果与预期不符
父进程可以挂起子进程