第五章 处理机管理 CPU Scheduling 处理机调度类型和模型 调度算法的选择和评价 调度算法

处理机调度的目的 处理机的高利用率High processor utilization 高吞吐量High throughput number of processes completed per unit time 快速的响应时间Low response time time elapse from the submission of a request to the beginning of the response

调度的类型 作业调度( Long-term scheduling) 中级调度( Medium-term scheduling) 进程调度( Short-term scheduling)

作业及作业步的概念 作业 作业步 OS为用户服务，用户交给计算机做的工作称为作业 作业由程序、数据、作业说明书三部分组成 程序是问题求解的算法描述 数据是程序加工的对象，但有些程序未必使用数据； 作业说明书是告诉操作系统本作业的程序和数据按什么样的控制要求使之执行。 作业步 一个作业的一次活动中若干相对独立的加工步骤 编译原程序 连接装配程序 运行程序

作业的状态 1 提交状态 2 后备状态 3 运行状态 4 完成状态 作业从输入设备进入外存储器时的状态 作业的全部信息调入外存后,系统将其加入后备作业队列时的状态 系统将为每个作业建立一个作业控制表(JCT) 3 运行状态 作业被调度程序选中,并分配到它所需要的资源时调入内存运行时的状态 4 完成状态 作业正常运行结束或因发生错误而终止时,释放占有的所有资源,准备离开系统时的状态

作业的状态转换 进程调度 程序 运行 执行 提交 后备 就绪 等待 作业注册程序 作业调度程序 完成 作业终止程序

作业控制块JCB 作业名 作业类型 资源要求 资源使用情况 优先级 当前状态 其它

作业调度及其功能 作业调度是按照某种调度算法从后备作业队列中选择作业装入内存运行，并当作业运行结束后做后续处理。 作业调度又称为宏观调度 分配资源：分配内存和外设资源 建立作业的进程 建立其它相关表格 作业后续处理(收回资源/撤消PCB和JCB) 作业调度又称为宏观调度 在实时系统和分时系统中通常不配置作业调度

中级(交换)调度 为了提高内存利用率和系统吞吐量 实施的方法是“挂起”和“解挂” 是存储器管理中的对换功能 常配置在具有挂起功能的OS中 可改善内存的利用率

进程调度 又称为微调度 通常几十毫秒运行一次 往往以原语方式存在 CPU及I/O 猝发(Burst)周期 Process execution consists of a cycle of CPU execution and I/O wait 任何一种操作系统中都必须配置该级调度

进程调度的方式 CPU scheduling decisions may take place when a process: 1. Switches from running to waiting state, e. g., I/O request, wait for an event to occur(child completion,system object: semaphore,message queue, socket …) 2. Switches from running to ready state,e.g., interrupt 3. Switches from waiting to ready. 4. Terminates. Scheduling under 1 and 4 is nonpreemptive.(非抢占) All other scheduling is preemptive.(抢占)

进程调度方式（续） 非抢占调度方式（nonpreemptive） 抢占调度方式（preemptive） 实现简单，系统开销小，适用于批处理系统环境 难于满足紧近任务立即执行的要求，实时系统中不宜采用 抢占调度方式（preemptive） 适用于分时系统和实时系统 调度方式的原则 时间片原则 优先级原则 短进程优先原则

调度队列模型 仅具有进程调度的调度队列模型 时间片用完 交互用户 等待事件（阻塞） 事件发生（被唤醒）

调度队列模型 具有作业调度和进程调度的调度队列模型 等待事件n 等待事件2 相应事件发生 则唤醒相应进程 队列中的进程 作业调度

调度队列模型 具有作业和进程和中级调度的调度队列模型 被挂起 被激活 事件发生被唤醒 被挂起 事件发生

调度算法的选择 选择时考虑的因素 各因素间往往相互矛盾 系统各类资源的均衡使用 用户作业到达系统的时间 用户作业估计执行的时间 用户公平并使用户满意 作业的优先级 作业对内存和外设的要求及整个系统的效率 各因素间往往相互矛盾

算法选择时主要考虑4个方面 1 系统设计目标 2 均衡处理系统和用户的要求 批处理系统主要追求大的系统吞吐量 实时系统主要关心实时处理 分时系统主要注重保证用户请求的及时响应 2 均衡处理系统和用户的要求 选择算法时不应使一个作业被无限期的推迟 常采用优先级可变方式 即作业的优先级可随等待时间的增加而提高 采用优先级调度算法

算法选择时主要考虑4个方面(续) 3 系统资源利用率 4 优先级 尽可能地使各种资源忙碌 将科学计算型(CPU密集型)和数据处理型(I/O密集型)作业搭配运行 4 优先级 引入优先级机制,可让某些紧急作业得到及时处理 实时系统中还需要采用抢占调度方式

调度算法的性能评价 1 周转时间 作业i从提交时刻tsi到完成时刻tei称为作业的周转时间。 Ti=Tei - Tsi 完成时刻 提交时刻 一个作业的周转时间包括: 作业在外存后备作业队列中等待调度的时间 作业进程在就绪队列中等待获取CPU的时间 作业进程在CPU上执行的时间 作业等待I/O操作等阻塞或挂起的时间

调度算法的性能评价 作业平均周转时间 T 作业平均带权周转时间 W 用于衡量不同调度算法对同一作业流的调度性能 周转时间与实际运行时间之比 用于衡量某种调度算法对不同作业流的调度性能 W反映了作业对单位执行时间所付出的平均等时间 TRi是作业的实际运行时间

调度算法 调度算法是根据系统的资源分配策略所规定的资源分配算法实行调度 目前有很多处理机调度算法,有些适用于作业调度,有些适用于进程调度,有些两者都能适用 常用的几种调度算法 先来先服务调度算法 短作业(短进程)优先调度算法 优先级调度算法 时间片轮转调度算法 多级反馈队列调度算法 实时调度算法

先来先服务调度算法(FCFS) First Come First Served 作业调度: 选择一个或多个最先进入并能被系统满足的作业装入内存,分配资源,创建相应进程,放入就绪队列 进程调度: 从就绪队列中选最先进入队列的进程分配处理机,让它进入执行状态,该进程一直执行,直到完成或因等待某事件而阻塞时,才放弃处理机.

FCFS调度例子 假设：用户区空间100KB，内存连续分配且运行中不能移动。 作业名 进入SPOOLING的时间 需计算的时间（分） A 8:06 42 15 B 8:18 30 60 C 8:30 24 50 D 8:36 10 E 8:42 12 20

T=(42+60+66+96+96)/5=72(min) W=(1+2+2.75+4+8)/5=3.55 内存容量 100K 作业 需时 需内存 A 42 15 B 30 60 C 24 50 D 10 E 12 20 作业名 入时间 作业调度时 进程开始时 结束时间 周转时间 带权周转时间 A 8:06 B 8:18 C 8:30 9:18 D 8:36 E 8:42 8:06 8:48 42 42/42 8:48 9:18 60 60/30 9:42 10:06 96 96/24 9:18 9:42 66 66/24 10:06 10:18 96 96/12 T=(42+60+66+96+96)/5=72(min) W=(1+2+2.75+4+8)/5=3.55

FCFS的优缺点 优点 缺点 存在的问题 比较容易实现 不公平 有利于长作业(长进程) 不得于短作业(短进程) 当计算机时间长的作业选中后可能使计算机时间短的作业等待很长时间,使短作业用户不满意,而且使短作业周转时间变长,使作业平均周转时间变长,降低了系统的吞能力

轮转法 设定时间片, 轮流将处理机分配为各就绪进程 仅适用于进程调度 时间片的选择 根据当前进程数量动态计算 固定法 q = R / Nmax 根据当前进程数量动态计算

短作业(短进程)优先调度算法 Shortest-Job-First/Shortest-Process-First SJF短作业优先 从后备作业中选择一个或若干个估计运行时间最短且当能获得所要求资源的作业装入内存 SPF短进程优先 从就绪队列中选出一个估计运行时间最短的进程分配处理机,该进程立即执行并一直执行到完成或因等待事件发生而阻塞放弃处理机为止

短作业/进程调度例子 T=(42+60+66+108+72)/5=69.6(min) W=(1+2+11/4+9/2+6)/5=3.25 需时 需内存 A 42 15 B 30 60 C 24 50 D 10 E 12 20 作业名 入时间 作业调度时 进程开始时 结束时间 周转时间 带权周转时间 A 8:06 B 8:18 C 8:30 9:18 D 8:36 E 8:42 8:06 8:48 42 42/42 8:48 9:18 60 60/30 9:54 10:18 108 108/24 9:18 9:42 66 66/24 9:42 9:54 72 72/12 T=(42+60+66+108+72)/5=69.6(min) W=(1+2+11/4+9/2+6)/5=3.25

非抢占式SJF调度例子 Example of Non-Preemptive SJF Process Arrival Time UseTime P1 0.0 7 P2 2.0 4 P3 4.0 1 P4 5.0 4 SJF (non-preemptive 非抢占) Average waiting time = (0 + 6 + 3 + 7)/4 = 4 T = (7+10+4+11)/4= 8 P1 P3 P2 P4 3 7 8 12 16

抢占式SJF调度例子 Example of Preemptive SJF Process Arrival Time Use Time P1 0.0 7 P2 2.0 4 P3 4.0 1 P4 5.0 4 SJF (preemptive 抢占) Average waiting time = (9 + 1 + 0 +2)/4 = 3 T= (16+5+1+6)/4 = 7 P1 P2 P3 P2 P4 P1 11 16 2 4 5 7

SJF/SPF优缺点 优点 缺点 在平均周转时间和平均带权周转时间上比FCFS好 对长作业不利（延迟不确定） 紧迫作业、进程不能及时得到处理 执行时间可能有虚假（估计的执行时间由用户提供）