进程的执行是 CPU 区间和 I/O 区间交替发生的过程。

  • CPU 区间(CPU Burst):用于执行指令
  • I/O 区间(I/O Burst):用于等待 I/O

操作系统从就绪队列选择下一个要执行的进程的过程称为调度。

就绪队列可以是:FIFO 队列、优先队列、树等各种实现。队列中的记录称为进程控制块(PCB)

何时调度?

下面是进程的状态转移:

@startuml
[*] -> 创建
创建 --> 就绪
就绪 --> 执行
执行 -> 阻塞 : (调度)
执行 -> 就绪 : (调度)
阻塞 -> 就绪 : (调度)
执行 --> 终止 : (调度)
终止 -> [*]
@enduml

调度的发生时机

可以看到,除了 $ 就绪 \to 执行 $ 的时候是程序被调度到,因而正在执行,其它时候都可能发生调度。

分派程序:负责:

  1. 切换上下文
  2. 切换到用户模式
  3. 启动用户程序使之继续执行

非抢占式调度:一旦 CPU 被分配给某进程,只要某进程不释放,就可以一直占用。

什么是 CPU burst and IO burst?

連續 CPU 使用期、連續 IO 使用期

调度准则(Scheduling Criteria)

CPU 利用率:越高越好。

吞吐量:单位时间内完成进程的数量,越高越好。

周转时间(turnaround time):从进程提交到完成的时间。包括等待。越短越好。

等待时间:在就绪队列中等待的时间之和。

响应时间:对于交互式系统,应该在计算完成之前先响应用户的操作。

各个准则的重要性依据情景而不尽相同。对于交互系统,最小化响应时间的方差比最小化平均响应时间更重要。

调度算法

FCFS

先到先服务(first-come, first)。进程正常排队,不允许插队。

抢占:否

SJF

最短作业优先(Shortest job first)。就是谁事儿多谁靠后,让快的先办。

抢占式 SJF 称为最短剩余时间优先(SRTF)

优先级调度

根据权重调度。例如 SJF 的权重是区间时间。可以引入各种指标作为优先级计算的因子。

缺点:无穷阻塞(饥饿)。

比如你在 B 站发了个视频,由于屑站的算法有问题,你的优先级很低,导致你的视频根本没人看。这就是一种饥饿现象。

老化技术:一种用于避免饥饿的技术。每隔几分钟将所有等待进程的优先级提高,从而保证所有进程最终都能被执行。

轮转法调度

引入了时间片。将就绪队列作为循环队列。CPU 调度程序循环就绪队列,为每个进程分配一个时间片的 CPU。

进程若在时间片内执行完毕,则自动释放 CPU。调度器处理下一进程。

多层队列调度

多层队列调度算法(multilevel queue scheduling algorithm)将就绪队列分成多个独立队列。一个进程被永久地分配到一个队列中。每个队列都有自己的调度算法。

队列之间通常采用固定优先级抢占调度。也就是有的队列生来拥有特权,可以先被执行。

也可以在队列之间划分时间片。每个队列都有一定的 CPU 时间。

多级反馈队列调度

通常在使用多级队列调度算法时,进程进入系统时被永久地分配到一个队列。例如,如果前台进程和后台进程分别有独立队列,进程并不从队列转移到另一个队列,这是因为进程并不改变前台或后台性质。这种设置的优点是低调度开销,缺点是不够灵活。

多级反馈队列调度算法(multilevel feedback queue scheduling algorithm)**允许进程在队列之间移动。**主要思想是根据不同 CPU 区间的特点以区分进程。如果进程使用过多的 CPU 时间,那么它会被转移到更低优先级队列。

多级反馈队列调度程序可由下列参数来定义:

  1. 队列数量
  2. 每个队列的调度算法
  3. 用以确定何时升级到更高优先级队列的方法
  4. 用以确定何时降级到更低优先级队列的方法
  5. 用以确定进程在需要服务时应进入哪个队列的方法

操作系统导论:多级反馈队列 - 知乎 (zhihu.com)

高响应比优先调度

响应比 =(等待时间 + 要求服务时间)/ 要求服务时间

多处理器调度

非对称多处理器(asymmetric multiprocessing)方法:让一个处理器(主服务器)处理所有的调度决定、I/O 处理以及其他系统活动,其他的处理器只执行用户代码。

处理器亲和性:避免将进程从一个处理器移至另一个处理器,而是努力使一个进程在同一处理器上运行

硬亲和性(hard affinity):进程可以要求不允许把自己移至其他处理器上。

软亲和性:操作系统会尽力,但是不保证一定一直在一个内核运行。

负载均衡:设法将工作负载平均地分配到 SMP 系统中的所有处理器上。

负载平衡的两种方法:

  • 推转移(push migration):将进程从超载处理器移到(或推送到)空闲或不太忙的处理器

  • 拉转移(pull migration):当空闲处理器从一个忙的处理器上 pull 一个等待任务时,发送 pull migration

  • 对称多线程 SMP(超线程):通过硬件方法,将一个物理处理器对操作系统展现为多个逻辑处理器。

习题:

5.1 Why is it important for the scheduler to distinguish I/O-bound programs from CPU-bound programs?

答:因为可以提高 CPU 利用率。CPU 密集型的程序需要进行无阻塞的逻辑运算,所以 CPU 调度的时候,就要尽快让 CPU 密集型的程序运行。而 IO 密集型程序对 CPU 的需求不高,只要在 IO 开始和完成的时候分配一些算力给它够用就行。

5.2 Discuss how the following pairs of scheduling criteria conlict in certain settings.

a. CPU utilization and response time b. Average turnaround time and maximum waiting time c. I/O device utilization and CPU utilization

答:

a. CPU 利用率高,则要减小上下文切换次数,在极端假设下,必须一个进程执行完,再执行另一个进程,响应时间会变慢。

b. 平均轮转时间越小,则需要先执行区间小的程序,则存在一些程序优先级一直很低,产生饥荒现象。

c. I/O 操作对 CPU 利用不高,但是需要和设备交互,所以对上下文切换的要求高,导致 CPU 利用率下降。

5.3 Consider the exponential average formula used to predict the length ofthe next CPU burst. What are the implications of assigning the following values to the parameters used by the algorithm?

a. $\alpha = 0$ and $\tau _ 0 = 100 \text{ms}$

b. $\alpha = 0.99$ and $\tau _ 0 = 10 \text{ms}$

答:根据指数移动平均公式,a 中 $\tau _ {n+1} = \alpha t_n + (1-\alpha) \tau _n = \tau _0$ 是一个常数,则算法实际上没有预测能力。b 中的会根据上一时刻和历史数据进行预测。

5.4 Consider the following set of processes, with the length of the CPU -bursttime given in milliseconds:

$$ \begin{array}{ccc} Process & { Burst Time } & { Priority } \\ \hline P_{1} & 10 & 3 \\ P_{2} & 1 & 1 \\ P_{3} & 2 & 3 \\ P_{4} & 1 & 4 \\ P_{5} & 5 & 2 \end{array} $$

The processes are assumed to have arrived in the order $P_{1}, P_{2}, P_{3}, P_{4}, P_{5}$, all at time 0 .

a. Draw four Gantt charts illustrating the execution of these processes using FCFS , SJF , a nonpreemptive priority (a smaller priority number implies a higher priority), and RR (quantum = 1)scheduling.

FCFS 调度,先来先办:

@startgantt
[P1] lasts 10 days
[P2] lasts 1  days
    [P2] starts at [P1]'s end
[P3] lasts 2  days
    [P3] starts at [P2]'s end
[P4] lasts 1  days
    [P4] starts at [P3]'s end
[P5] lasts 5  days
    [P5] starts at [P4]'s end
@endgantt

SJF 调度,最短优先:

@startgantt
[P2] lasts 1  days
[P4] lasts 1  days
    [P4] starts at [P2]'s end
[P3] lasts 2  days
    [P3] starts at [P4]'s end
[P5] lasts 5  days
    [P5] starts at [P3]'s end
[P1] lasts 10 days
    [P1] starts at [P5]'s end
@endgantt

nonpreemptive priority,非抢占式,优先值越低优先值越高:

@startgantt
[P4(priority=4)] lasts 1  days
[P3(priority=3)] lasts 2  days
    [P3(priority=3)] starts at [P4(priority=4)]'s end
[P1(priority=3)] lasts 10 days
    [P1(priority=3)] starts at [P3(priority=3)]'s end
[P5(priority=2)] lasts 5  days
    [P5(priority=2)] starts at [P1(priority=3)]'s end
[P2(priority=1)] lasts 1  days
    [P2(priority=1)] starts at [P5(priority=2)]'s end
@endgantt

RR 轮转抢占式调度

img

b. What is the turnaround time of each process for each of thescheduling algorithms in part a?

Pn FCFS SJF Pr RR
P1 10 10 13 19
P2 11 1 19 2
P3 13 4 3 7
P4 14 2 1 4
P5 19 9 18 14

c. What is the waiting time of each process for each of the schedulingalgorithms in part a?

Pn FCFS SJF Pr RR
P1 0 9 3 9
P2 10 0 18 1
P3 11 2 1 7
P4 13 1 0 5
P5 14 4 13 9
平均 12 3.2 7 6.2

d. Which of the schedules in part a results in the minimal average waiting time (over all processes)?

结果平均 12 3.2 7 6.2,因此 SJF 的平均等待时间最短。

5.5 Which of the following scheduling algorithms could result in starvation?

a. First-come, first-served

b. Shortest job irst

c. Round robin

d. Priority

答:显然 b d。

5.6 Consider a variant of the RR scheduling algorithm where the entries in the ready queue are pointers to the PCBs.

a. What would be the effect of putting two pointers to the same process in the ready queue?

相当于这个进程获得更高的优先级。

b. What would be the major advantages and disadvantages of this scheme?

优点:相当于引入了优先级功能。

缺点:如果连续遇到两个相同的指针,则需要处理一下避免同一个进程还要进行上下文切换。而且优先级控制的粒度过大,可能导致某些进程相对优先级太低。

c. How would you modify the basic RR algorithm to achieve the same effect without the duplicate pointers?

可以引入一个 quantumNum 字段,表示多久以后调度到下一个进程,从而控制当前进程的优先级。或者使用多个队列进行交替轮转。

5.7 Consider a system running ten I/O-bound tasks and one CPU-bound task.

Assume that the I/O-bound tasks issue an I/O operation once for every millisecond of CPU computing and that each I/O operation takes 10 milliseconds to complete.

Also assume that the context switching overhead is 0.1 millisecond and that all processes are long-running tasks. What is the CPU utilization for a round-robin scheduler when:

a. The time quantum is 1 millisecond

b. The time quantum is 10 milliseconds

a 则产生一个 IO 请求并切换上下文的时间是 1.1ms,10 个耗时 11ms,而计算密集任务需要 10ms + 切换 10 次上下文 = 11ms,一共 22ms,而实际使用时间 1*10+10=20,利用率 20/22=91%

b. 则产生一个 IO 请求并切换上下文的时间是 1.1ms,10 个耗时 11ms,计算密集任务 + 切换上下文耗时 10.1ms,一共是 21.1ms,而实际使用时间 1*10+10=20,利用率 20/21.1=94%

5.8 Consider a system implementing multilevel queue scheduling. What strategy can a computer user employ to maximize the amount of CPU time allocated to the user’s process?

  • 规则 3:工作进入系统时,放在最高优先级(最上层队列)。
  • 规则 4a:工作用完整个时间片后,降低其优先级(移入下一个队列)。
  • 规则 4b:如果工作在其时间片以内主动释放 CPU,则优先级不变。

因此程序应当避免用完时间片,从而避免优先级变低。

5.9 Consider a preemptive priority scheduling algorithm based on dynami-cally changing priorities. Larger priority numbers imply higher priority.When a process is waiting for the CPU (in the ready queue, but not run-ning), its priority changes at a rate $\alpha$; when it is running, its prioritychanges at a rate $\beta$. All processes are given a priority of 0 when theyenter the ready queue. The parameters $\alpha$; and $\beta$ can be set to give many different scheduling algorithms.

a. What is the algorithm that results from $\beta > \alpha > 0$

FCFS

b. What is the algorithm that results from $\alpha < \beta < 0$ >

LIFO

5.10 Explain the differences in the degree to which the following scheduling algorithms discriminate in favor of short processes:

a. FCFS

对于短任务不利,因为排队时间比执行时间大于平均值。

b. RR

排队时间是公平的,但是执行时间很短。公平但不合理。

c. MLFQ

相对公平,因为在一个时间片内执行完的,能够保持优先级。

5.11 Using the Windows XP scheduling algorithm, what is the numeric priority of a thread for the following scenarios?

a. A thread in the REALTIME PRIORITY CLASS with a relative priority of HIGHEST.

b. A thread in the NORMAL PRIORITY CLASS with a relative priority of NORMAL.

c. A thread in the HIGH PRIORITY CLASS with a relative priority of ABOVE NORMAL.

img

根据资料,直接查表:

a. 26, b.8, c. 14

5.12 Consider the scheduling algorithm in the Solaris operating system fortime sharing threads:

img

a. What is the time quantum (in milliseconds) for a thread with priority 10? With priority 55?

160,40

b. Assume a thread with priority 35 has used its entire time quantumwithout blocking. What new priority will the scheduler assign thisthread?

35

c. Assume a thread with priority 35 blocks for I/O before its timequantum has expired. What new priority will the scheduler assignthis thread?

54

5.13 The traditional UNIX scheduler enforces an inverse relationship between priority numbers and priorities: The higher the number, the lower the priority. The scheduler recalculates process priorities once per second using the following function:

$$ \text { Priority }=(\text { Recent } \text { CPU usage } / 2)+\text { Base } $$

where base $=60$ and recent CPU usage refers to a value indicating how often a process has used the CPU since priorities were last recalculated. Assume that recent CPU usage for process $P_{1}$ is 40, process $P_{2}$ is 18 , and process $P_{3}$ is $10 .$ What will be the new priorities for these three processes when priorities are recalculated? Based on this information, does the traditional UNIX scheduler raise or lower the relative priority of a CPU-bound process?

直接代入得到 80, 69, 65. 对于 CPU 密集型进程,算出来的值变大,因而优先级会被降低。