处理机调度

作业调度（宏观）：

决定哪些程序调入计算机系统。

进/线程调度（微观）：

决定哪个（些）进程占用CPU。

不同类型操作系统的侧重点不同。

批处理系统

2层作业—选择作业进入主存

进程—选择获得CPU的进程

分析：作业小时—分钟为单位发生的频率低

高效调度，充分优化

进程发生的频率高 ms为单位快速调度

例：20ms—时间片，2ms—调度执行

分时操作系统—进程调度

个人计算机操作系统—进程调度或线程调度

作业调度

一般来说，计算机系统把用户要求处理的一项工作称为一个作业。

作业有四种状态：

1 . 提交状态 用户将程序和数据提交计算中心；

2. 后备状态 将作业录入到后援存储设备；

3. 执行状态 作业调入计算机系统内存；

4. 完成状态 作业计算完成的善后处理。

作业调度的主要任务是完成作业从后备状态到执行状态和从执行状态到完成状态的转变。

功能：

**1. ** 确定数据结构，记录已进入系统的各作业的情况JCB（Job Control Block）

2. 按一定的调度算法，从后备作业中选择一个或几个作业进入内存；

3. 分配资源，为被选中的作业创建进程，并为其申请系统资源；

4. 作业结束后作善后处理。（进程和作业的资源回收是同时的）

作业控制块JCB

每个作业进入系统时由系统为其建立一个作业控制块JCB（Job Control Block)，它是存放作业控制和管理信息的数据结构。

调度算法性能的衡量

需要考虑系统中各种资源的负载均匀

作业的周转时间：
$$
t_i = t_ci - t_{si}\
t_i:作业周转时间，t_ci:作业完成时间，t_{si}：作业提交到系统的时间
$$
平均周转时间：
$$
t=1/n\sum_{i=1}^n t_i
$$
平均带权周转时间
$$
w=1/n\sum_{i=1}^nw_i\
w_i=t_i/t_{ri}\
t_{ri}:作业i实际运行时间
$$

作业调度算法

先来先服务算法FCFS

先来先服务算法是按作业来到的先后次序进行调度的，换句话说，调度程序每次选择的作业是等待时间最久的，而不管作业的运行时间的长短。这种调度算法突出的优点是实现简单，效率较低，在一些实际的系统和一般应用程序中采用这种算法的较多。

短作业优先算法SJF

短作业优先调度算法考虑作业的运行时间，每次总是选择一个运行时间最小的作业调入内存（系统）

在一般情况下这种调度算法比先来先服务调度算法的效率要高一些。实现相对先来先服务调度算法要困难些，如果作业的到来顺序及运行时间不合适，会出现饿死现象。

响应比高者优先算法

每调度一个作业投入运行时，就计算后备作业表中的每个作业的响应比，将响应比最高的作业投入运行。
$$
响应比=响应时间/执行时间\
响应时间=作业进入系统的等待时间+执行时间
$$

理论上讲是比较好的，但是需要估计作业的等待时间和运行时间，比较复杂，开销大。

优先数调度算法

优先数调度算法是终合考虑各方面的因素（作业等待时间、运行时间、缓急程度，系统资源使用等），给每个作业设置一个优先数，调度程序总是选择一个优先数最大（或者最小）的作业调入（系统）内存。

确定优先数的一种简单的方法是：用户为自己的作业确定一个优先级

当然，优先数是可以浮动的。

进程调度

见《进程管理》

UNIX系统进程调度

采用优先数调度算法
进程有一个进程优先数p_pri
p_pri取值范围是-127～127，其值越小，进程的优先级越高

优先数的确定
系统设置
在sleep（）中设置将要进入睡眠状态进程的优先数，当该进程被唤醒后，就以系统给它设置的优先数去参与处理机的竟争。

0＃进程（－100优先数）；
资源请求得不到满足的进程，磁盘（-80），打印机（-20），…；
所有处于用户态运行进程同步（一般情况下为大于**0）。

优先数的计算

 p_pri = min{127, (p_cpu/16+p_nice+PUSER)}
 其中：
p_cpu: 进程占用CPU的程度
p_nice: 用户通过系统调用nice(priority)设置的
   进程优先数
PUSER: 常数，其值为100

Linux系统进程调度

进程调度程序是内核的组成部分，负责选择下一个要运行的进程。

进程调度可看作在可运行态进程之间分配有限的处理器时间资源的内核子系统。

进程调度程序是如Linux这样的多任务操作系统的基础。

Linux进程调度策略

基于动态优先级和可变时间片的调度

调度方式为可抢占式调度

调度目标

实现算法复杂度为O(1)级的调度
- 进程调度算法保证在恒定的时间内完成
- 算法执行时间与系统中处于就绪(可运行)状态的进程个数无关
提高交互性能
- 提高交互性能，保证系统能快速响应
保证公平
- 在合理设定的时间范围内，没有进程会出现饥饿状态，也不会有进程获得大量的时间片
实现对称多处理器（SMP）可扩展性

I/O消耗型和处理器消耗型的进程

I/O消耗型进程
- 大部分时间是使用外部设备，交互式进程具有此特征
处理器消耗型进程
- 大部分时间是使用CPU，计算进程具有此特征

交互式的程序都是I/O消耗型的。Linux为了保证交互式应用，优化了进程的响应，更倾向于优先调度I/O消耗型进程，但并未忽略处理器消耗型程序。

进程调度的特点

Linux系统实现了基于进程过去行为的启发式算法；
Linux系统选择优先级高的进程先运行，相同优先级的进程按循环方式调度；
动态优先级依进程占有CPU的情况、休眠时间的长短来增、减；
系统根据进程优先级调整分配给它的时间片；
实施可抢占调度方式

动态优先级

每个进程有一个动态优先级，它是进程调度程序选择可运行进程所使用的参数，其取值范围是100(最高优先级) ~ 139(最低优先级)

动态优先级的计算

动态优先级 = max(100，min(静态优先级－ bonus + 5，139))

bonus是范围 0 ～ 10的值，

值小于5表示降低动态优先级以示惩罚

值大于5表示增加动态优先级以示奖励

进程调度使用的是动态优先级，通过effective_prio( )函数来计算一个进程的动态优先级。

确定I/O消耗型和处理器消耗型进程的方法

依据 —— 进程睡眠时间的长短

若进程睡眠时间长 —— I/O消耗型

若进程睡眠时间短 ——处理器消耗型

可变时间片

对交互式进程,系统提供较长的时间片

调度程序根据进程的优先级动态调整分配给它的时间片

时间片处理的时机

创建新进程时的处理
- 新创建的子进程和父进程均分父进程剩余的时间片
进程用完时间片时的处理
- 当一个进程的时间片用完时，依任务的静态优先级重新计算时间片；
- task_timeslice()函数为给定任务返回一个新的时间片

时间片的使用

一个进程拥有的时间片可分多次使用，放弃CPU时进入活动队列
当一个进程的时间片耗尽时，认为是过期进程，进入过期队

时间片的计算

基本时间片

静态优先级本质上决定了进程的基本时间片

(140 －静态优先级) ×20 若静态优先级＜ 120

(140 －静态优先级) ×5 若静态优先级 ≥ 120

静态优先级越高(值越小)，基本时间片越长。

活动队列和过期队列

每个处理器维护两个优先级数组—— 活动数组和过期数组

活动数组上的可执行队列中的进程都有剩余时间片

过期数组上的可执行队列中的进程都已耗尽时间片

当一个进程的时间片耗尽时，被移至过期队列中；

当活动数组上的可执行队列中的所有进程都已耗尽时时间片，这时，在活动数组和过期数组之间切换指针。

问题

6-3 某系统的进程状态变迁图如图6.12所示 (设该系统的进程调度方式为非剥夺方式)。

(1) 说明一个进程发生变迁3的原因是什么? 发生变迁2、变迁4的原因又是什么？

(2) 下述因果变迁是否会发生，如果有可能的话，在什么情况下发生 ?

① 2→5； ② 2→1； ③ 4→5； ④ 4→2； ⑤ 3→5

(3) 根据此进程状态变迁图叙述该系统的调度策略、调度效果。

(1) 答：

发生变迁3的原因：当运行进程在执行过程中，需要等待某事件的发生才能继续向下执行时会发生变迁3。

发生变迁2的原因：运行进程在分得的时间片100ms 或500ms内未完成，当其时间片到时将发生变迁2。

发生变迁4的原因：当等待进程等待的事件发生了，将会发生变迁4。

(2) 答：

① 2→5的因果变迁可能发生。条件是：高优先就绪队列非空。

② 2→1的因果变迁可能发生，当运行进程的时间片到时发生的变迁2，若此时高优先就绪队列为空，必然引起低优先就绪队列中的一个就绪进程被调度执行而发生变迁1。

③ 4→5的因果变迁不可能发生，因为采用的是非剥调度夺式。

④ 4→2的因果变迁不可能发生。

⑤ 3→5的因果变迁可能发生，条件是：高优先就绪队列非空。

(3) 答：

调度策略：首先调度高就绪队列中的进程 (一般是I/O 型进程) 投入运行，给高优先就绪队列中的进程分配的时间片大小为100ms。只有当高就绪队列中的所有进程全部运行完或因等待某事件发生处于阻塞状态，高就绪队列中没有进程可运行时，才调度低优先就绪队列中的进程 (一般是计算型进程) ，给低优先就绪队列中的进程分配的时间片大小为500ms。若一个运行进程时间片100ms 或500ms到时未完成就进入低优先就绪队列。若某进程在运行期间因等待某事件发生而进入阻塞队列，则当所等待事件完成后，它将进入高优先就绪队列。

调度效果：这种算法优先照顾了I/O 量大的进程 (高优先级) ，但通过给计算型进程分配更长的时间片也适当照顾了计算型进程。

6-10 Linux2.6版本为了实现O(1)级算法复杂度，采用了什么措施?

答：Linux系统进程调度用的数据结构最重要的是运行队列结构，该结构给出了处理机上可运行进程的链表。该结构中包含一个称为优先级数组的结构数组。每个数组都表示一个可运行进程集合，包括两个重要信息：① 一个优先级位图；

② 140个双向链表头，每个链表对应一个可能的进程优先级队列。

Linux系统采用优先调度策略。在Linux2.6版本的进程调度程序中，基于上述进程调度用数据结构，查找系统中优先级最高的进程这一问题转化为查找优先级位图中第一个置为1的位。找到这一位就是找到了最高优先级链表，即可确定优先级最高的、可运行的进程。由于优先级个数是定值，所以查找时间恒定。许多体系结构提供find_first_bit指令（字操作指令），找到第一个设置为1的位所花费的时间微不足道。这是保证Linux系统进程调度具有O(1)级算法复杂度的关键所在。

1．系统有5个进程，它们的到达时间和服务时间如表4-8所示。新进程（没有运行过）与老进程（运行过的进程）的条件相同时，假定系统选新进程运行。

表4-8 进程情况

进程名	到达时间	服务时间
A	0	3
B	2	6
C	4	4
D	6	5
E	8	2

若按先来先服务（FCFS）、时间片轮法（时间片q=1）、短进程优先（SPN）、最短剩余时间优先（SRT，时间片q=1）、响应比高者优先（HRRN）及多级反馈队列（MFQ，第一个队列的时间片为1，第i（i>1）个队列的时间片q=2（i-1））算法进行CPU调度，请给出各个进程的完成时间、周转时间、带权周转时间，及所有的进程的平均周转时间和平均带权周转时间。

答：