# Basic Concepts （基本概念）

• 通过多道程序设计得到 CPU 的最高利用率
• CPU-I/O 脉冲周期 - 进程的执行包括进程在 CPU 上执行和等待 I/O
• 进程的执行以 CPU 脉冲开始，其后跟着 I/O 脉冲。进程的执行就是在这两个状态之间进行转换.

# CPU burst distribution

CPU 脉冲的分布，在系统中，存在许多短 CPU 脉冲，只有少量的长 CPU 脉冲
比如：I/O 型作业具有许多短 CPU 脉冲，而 CPU 型作业则会有几个长 CPU 脉冲，这个分布规律对 CPU 调度算法的选择是非常重要的

# CPU 调度

• 当 CPU 空闲时，OS 就选择内存中的某个就绪进程，并给其分配 CPU
• CPU 调度可能发生在以下情况下:

1. Switches from running to waiting state（从运行转到等待）.
2. Switches from running to ready state（从运行转到就绪）.
3. Switches from waiting to ready（从等待转到就绪）.
4. Terminates（终止运行）.
   Scheduling under 1 and 4 is nonpreemptive （发生在 1、4 两种情况下的调度称为非抢占式调度）.
   All other scheduling is preemptive （其他情况下发生的调度称为抢占式调度）.

# CPU 调度方式

• 非抢占方式 (nonpreemptive)
  • 把处理机分配给某进程后，便让其一直执行，直到该进程完成或发生某事件而被阻塞时，才把处理机分配给其它进程，不允许其他进程抢占已经分配出去的处理机。
  • 优点：实现简单、系统开销小，适用于大多数批处理系统环境
  • 缺点：难以满足紧急任务的要求，不适用于实时、分时系统要求
• 抢占方式（Preemptive mode）
  • 允许调度程序根据某个原则，去停止某个正在执行的进程，将处理机重新分配给另一个进程。
• 抢占的原则：
  • 时间片原则：各进程按时间片运行，当一个时间片用完后，便仃止该进程的执行而重新进行调度。这个原则适用于分时系统。
  • 优先权原则：通常对一些重要的和紧急的进程赋予较高的优先权。当这种进程进入就绪队列时，如果其优先权比正在执行的进程优先权高，便仃止正在执行的进程，将处理机分配给优先权高的进程，使之执行
  • 短作业优先原则：当新到达的作业比正在执行的作业明显短时，将暂停当前长作业的执行，将处理机分配给新到的短作业，使之执行。

# 分派程序

分派程序负责将对 CPU 的控制权转交给短调度选择的进程，包括

• 切换上下文
• 切换到用户态
• 跳转到用户程序的适当位置并重新运行之
• 分派延迟：分派程序终止一个进程的运行并启动另一个进程运行所花的时间

# Scheduling Criteria （调度准则）

• CPU 利用率 – 使 CPU 尽可能的忙碌
• 吞吐量 – 单位时间内运行完的进程数
• 周转时间 – 进程从提交到运行结束的全部时间
• 等待时间 – 进程在就绪队列中等待调度的时间片总和
• 响应时间 – 从进程提出请求到首次被响应的时间段 [在分时系统环境下不是输出完结果的时间]
• 调度算法影响的是等待时间，而不能影响进程真正使用 CPU 的时间和 I/O 时间

# Scheduling Algorithms （调度算法）

# 先来先服务 (FCFS)

• First-Come, First-Served
• 先来先服务 First-Come-First-Served:
  • 最简单的调度算法
  • 可用于作业或进程调度
  • 算法的原则是按照作业到达后备作业队列（或进程进入就绪队列）的先后次序来选择作业（或进程）
• FCFS 算法属于非抢占方式：一旦一个进程占有处理机，它就一直运行下去，直到该进程完成或者因等待某事件而不能继续运行时才释放处理机。
• FCFS 算法易于实现，表面上很公平，实际上有利于长作业，不利于短作业；有利于 CPU 繁忙型，不利于 I/O 繁忙型。

# 短作业优先 (SJF)

• Shortest-Job-First
• 关联到每个进程下次运行的 CPU 脉冲长度，调度最短的进程
  • 非抢占式调度 – 一旦进程拥有 CPU，它的使用权限只能在该 CPU 脉冲结束后让出
  • 抢占式调度 – 发生在有比当前进程剩余时间片更短的进程到达时，也称为最短剩余时间优先调度
• SJF 是最优的 – 对一组指定的进程而言，它给出了最短的平均等待时间
• 将短进程移到长进程之前，短进程等待时间的减少大于长进程等待时间的增加

# Determining Length of Next CPU Burst

$t_\alpha=实际第n个cpu脉冲长度\\ \tau_{n+1}=下一个CPU脉冲的预测值\\ 0\leq \alpha\leq 1\\ \tau_{n+1}=\alpha t_n+(1+\alpha)\tau_n$

# SJF 的优缺点

• 采用 SJF 有利于系统减少平均周转时间，提高系统吞吐量。
• 一般情况下 SJF 调度算法比 FCFS 调度算法的效率要高一些，但实现相对要困难些。
• 如果作业的到来顺序及运行时间不合适，会出现饥饿现象，例如，系统中有一个运行时间很长的作业 JN，和几个运行时间小的作业，然后，不断地有运行时间小于 JN 的作业的到来，这样，作业 JN 就因得不到调度而饿死。另外，作业运行的估计时间也有问题。

# 优先权调度 (Priority Scheduling)

• 每个进程都有自己的优先数 [整数]
• CPU 分配给最高优先级的进程 [假定最小的整数 = 最高的优先级]
  • Preemptive（抢占式）
  • Nonpreemptive （非抢占式）
• SJF 是以下一次 CPU 脉冲长度为优先数的优先级调度

# 优先权

• 确定进程优先权的依据有：
• 静态优先权在进程创建时确定，且在整个生命期中保持不变。
  • 进程类型，通常系统进程的优先权高于一般用户进程的优先权。在用户进程中，I/O 繁忙的进程应优先于 CPU 繁忙的进程，以保证 CPU 和 I/O 设备之间的并行操作。
  • 进程对资源的需求，如进程执行时间及内存需要少的进程应赋予较高的优先权；
  • 根据用户要求，由用户的紧迫程度及用户所付费用的多少来确定进程的优先权。
  • 在分时系统中，前台进程应优先于后台进程
• 静态优先权的问题：饥饿 – 低优先级的可能永远得不到运行
• 解决方法：老化 – 视进程等待时间的延长提高其优先数
• 动态优先权是指进程的优先权可以随进程的推进而改变，以便获得更好的调度性能
  • 改变优先权的因素
  • 进程的等待时间
  • 已使用处理机的时间
  • 资源使用情况

# 时间片轮转 (Round Robin)

• 每个进程将得到小单位的 CPU 时间 [时间片]，通常为 10-100 毫 秒。时间片用完后，该进程将被抢占并插入就绪队列末尾
• 假定就绪队列中有 n 个进程、时间量为 q, 则每个进程每次得到 1/n 的 CPU 时间、长度不超过 q 单位的成块 CPU 时间，没有任何一个进程的等待时间会超过 (n-1) q 单位
• q 相对于切换上下文的时间而言足够长，否则将导致系统开销过大
• q 足够大就是 FCFS

一组进程的平均周转时间并不一定随着时间片的增大而降低。一般来说，如果大多数（80%）进程能在一个时间片内完成，就会改善平均周转时间

# 多级队列调度 (Multilevel Queue)

• 按进程的属性来分类，如进程的类型、优先权、占用内存的多少，每类进程组成一个就绪队列，每个进程固定地处于某一个队列，如
  • 就绪队列分为
    • 前台：交互式
    • 后台：批处理
  • 每个队列都有自己的调度算法：前台 RR 后台 FCFS
  • 调度须在队列间进行
• 固定优先级调度，即前台运行完后再运行后台。有可能产生饥饿
• 给定时间片调度，即每个队列得到一定的 CPU 时间，进程在给定时间内执行；如，80% 的时间执行前台的 RR 调度，20% 的时间执行后台的 FCFS 调度

# 多级反馈队列调度算法 (Multilevel Feedback Queue)\

• 存在多个就绪队列，具有不同的优先级，各自按时间片轮转法调度
  允许进程在队列之间移动
• 各个就绪队列中时间片的大小各不相同，优先级越高的队列时间片越小。
• 当一个进程执行完一个完整的时间片后被抢占处理器，被抢占的进程优先级降低一级而进入下级就绪队列，如此继续，直至降到进程的基本优先级。而一个进程从阻塞态变为就绪态时要提高优先级
• 最后会将 I/O 型和交互式进程留在较高优先级队列
• 进程能在不同的队列间移动；可实现老化
• 多级反馈队列调度程序由以下参数定义
  • 队列数
  • 每一队列的调度算法
  • 决定进程升级的方法
  • 决定进程降级的方法
  • 决定需要服务的进程将进入哪个队列的方法

# Highest Response Ratio Next (HRRN) 高响应比优先 (作业) 调度算法

• SJF 中长作业运行得不到保证，引入动态优先权
• 高响应比优先调度算法 — 基于优先权算法
  • 在每次选择作业投入运行时，先计算后备作业队列中每个作业的响应比 RP, 然后选择其值最大的作业投入运行。
• RP 值定义为：
  RP＝（已等待时间＋要求运行时间）／要求运行时间＝1＋已等待时间／要求运行时间
• HRRN 算法实际上是 FCFS 算法和 SJF 算法的折衷
• 优点：
  等待时间相同，则 SJF；
  要求的服务时间相同，则 FCFS；
  长作业的优先级随着等待时间的增加而提高，不会出现得不到响应的情况。
• 缺点:
  作业调度程序要统计作业的等待时间，作浮点运算（这是系统程序最忌讳的）浪费大量的计算时间

# Multiple-Processor Scheduling （多处理器调度）

• 多个 CPU 可用时，CPU 调度将更为复杂
• 多处理器内的同类处理器
• 负载共享 - 设置一个公共的就绪队列
• 对称多处理器 (Symmetric Multiprocessing SMP) – 每个处理器决定自己的调度方案。每个 CPU 自己到公共就绪队列去取进程来执行。这需保证多个 CPU 对公共就绪队列的互斥访问
• 非对称多处理器 – 仅一个处理器能处理系统数据结构，这就减轻了对数据的共享需求
• 当进程从一个 CPU 迁移到另外一个 CPU 时，其 CACHE 的内容也必须随之更新–代价很高
  多数 SMP 系统不支持进程在不同 CPU 间迁移，而是试图使进程一直在同一个 CPU 上运行 -- Processor affinity
• Processor affinity – process has affinity for processor on which it is currently running
  • soft affinity: 试图使进程一直在同一个 CPU 上运行，但不保证
  • hard affinity: 不允许进程在不同 CPU 间迁移

# Real-Time Scheduling （实时调度）

• 实时调度是为了完成实时处理任务而分配计算机处理器的调度方法。
• 实时处理任务要求计算机在用户允许的时限范围内给出响应信号。
• 实时处理任务可分为
  • 硬实时任务（hard real-time task）
  • 软实时任务（soft real-time task
• 硬实时系统 – 用于实现要求在给定的时间内执行完紧急进程的场合）
• 这种进程在提交时会明确指出需在什么时间内完成
• 系统则会通过资源预留以保证这个任务的及时完成，或者在资源不能保证的情况下拒绝执行
• 硬实时系统通常由实现紧急任务的具有特殊目的软件组成，而不一定具备现代 OS 和计算机的完整功能
• 软实时计算 – 要求紧急进程得到比其他进程更高的优先级
• 对 OS 的调度程序及其他相关方面提出了要求。首先，系统要实现基于优先级的调度，实时进程须具有最高优先级，且不能随着时间的推移降低优先级；其次，调度延迟必须很小.

# Dispatch Latency

为降低分派延迟，需要允许系统调用被抢占

1. 一种方法是在长系统调用中插入抢占点
2. 一种方法是使得整个内核可被抢占，但所有内核数据结构必须通过各种同步机制加以保护

• 如果较高优先级进程需读或修改正在被另一个低优先级进程所访问的内核数据，高优先级进程需要等待低优先级进程的完成。这种现象称为优先级倒置
• 优先级继承：(正在访问高优先级进程所需资源的) 低优先级进程继承高优先级，直到相关资源处理完毕，它们的优先级再返回原来的值.

# 操作系统例子

# Thread Scheduling

• 用户级线程要运行的话，需通过 LWP 映射到某个内核级线程
• 局部调度– 线程库怎样决定将哪个线程列入有效的轻量级线程
• 全局调度 – 内核怎样决定下一个运行的内核线程

# Solaris scheduling

• 采用基于优先级的进程调度
• 按调度的优先级定义了 4 类：实时、系统、分时、交互，对每一类有不同的优先级和调度算法
  • 默认的调度类是分时。分时调度动态地改变线程的优先级，赋予不同的时间片长度（多级反馈队列）
  • 分时和交互采用相同的调度策略，但交互式线程有较高的优先级
  • 系统类的优先级是不会改变的，其调度策略是不分时的
  • 实时类具有最高的优先级
  • 每一类有一组优先级，然而调度程序需先将其转换成全局优先级，然后选择全局优先级最高的线程运行。

# Windows XP scheduling

• Priority-driven, preemptive scheduling system 基于优先级的，可抢占的调度算法
• Thread runs for time amount of quantum 线程按时间片来使用 CPU
• Dispatcher routines triggered by the following events: 当发生以下事件时，分派程序进行 CPU 调度
  • Thread becomes ready for execution
  • Thread leaves running state (quantum expires, wait state)
  • Thread‘s priority changes (system call/NT activity)

# Windows Scheduling Principles

• 32 priority levels 使用 32 个优先级来确定线程的执行顺序
• Threads within same priority are scheduled following the Round-Robin policy 优先级相同的线程按 RR 调度
• Non-Realtime Priorities are adjusted dynamically 非实时优先级是动态调整的
  • 当线程从等待操作被唤醒时，提高其优先级 (如 I/O 结束)
  • 延长时间片：给前台任务更长的时间片，以提高响应速度
• Real-time priorities (i.e.;> 15) are assigned statically to threads 实时优先级是固定不变的

# Linux scheduling

• Linux 提供二种进程调度算法
  • 分时：实现进程间的公平可抢占调度
  • 实时：按优先级调度
• Linux 支持 SMP, 每个 CPU 有自己的 runqueue, 并各自独立进行调度.
• 每个 runqueue 有:
  • Active: contains all tasks with time remaining in their time slices
  • Expired: contains all expired tasks
• 调度程序从 Active array 中选取优先级最高的进程使用 CPU, 当所有进程都用尽了自己的时间片，交换 Active array 与 expired array

# Java Thread Scheduling

• JVM 使用的是抢占式的、基于优先级的调度算法
• 对多个相同优先级的进程将使用 FIFO 队列来调度
• JVM 调度线程运行，当
  • 当前运行进程退出运行状态时
  • 有更高优先级的进程进入可运行状态时
• 注意 – JVM 并未指定线程是否是指定时间片的

# Time-Slicing

鉴于 JVM 不指定时间片，将使用 yield () 方法）:

1
2
3
4
5

while (true) {
	// perform CPU-intensive task
	. . .
	Thread.yield(); ();//relinquishes control of the cpu allowing another thread of equal priority to run
}

This Yields Control to Another Thread of Equal Priority（这将把控制权转给另一个相同优先级的线程）.

# Thread Priorities

• Thread Priorities: 线程类定义了三类优先级：

1
2

Priorities May Be Set Using setPriority() method:
setPriority(Thread.NORM_PRIORITY + 2);

• 当线程创建的时候就给定一个默认的优先级，但优先级可以通过在程序中使用 setPriority（）方法来修改

# Algorithm Evaluation （算法评估）

• 首先定义一个标准 (根据要实现的系统所追求的目标，如 CPU 利用率 \ 系统吞吐量 \ 平均周转时间 \ 响应时间等)
• 然后根据标准来选择适当的算法
• 采用相应的模型来评价算法
• 确定模型法 – 精确预定作业量，并定义该作业量在每个算法上执行的情况
• 确定模型法主要用于描述调度算法和提供例子，它要求有准确的输入数据，如进程的数目、到达时间、预定执行时间等。在某些情况下，可以用确定模型法来选择调度算法。

# 等待队列模型

• queueing-network analysis
• 计算机系统可描述为服务器网络，每个服务器都有一个进程队列.
• CPU 是具有就绪进程队列的服务器，而 I/O 系统具有设备队列，知道了到达率和服务率，就可以计算使用率 \ 平均队列长度 \ 平均等待时间等
• 设 n 为平均队列长度，W 为队列的平均等待时间，λ 为新进程到达队列的平均到达率。存在如下公式：如果系统处于稳定状态，那么离开队列的进程数量必定等于到达进程的数量。

# Simulations

是一种更准确的方法。通过编程给计算机系统建模。用软件数据结构表示计算机的主要部件，有一个变量来表示时钟，随着这个变量的值的增加，仿真器修改系统的状态来反映外设、进程和调度程序的活动。当这个仿真器运行时，指明算法性能的统计数据会被收集并打印。

# Implementation（实现）

完全准确的方法。编写一个调度算法，把它放到真实的 OS 中去运行，来看它是如何工作的。