ClarkCheung

I'm writing something about Computer Science, especially some basic knowledges.

操作系统:调度

發布於

调度

当存在多个进程或线程同时竞争CPU的时候,CPU需要选择下一个运行的进程或线程。在操作系统中,完成选择工作的部分称作调度程序,该程序使用的算法称为调度算法。

调度的原则

我们什么时候需要调度?怎样的调度算法是好的调度算法?例如交互式程序会存在需要CPU处理的工作和I/O,在出现CPU突发(需要CPU处理的工作)时,调度程序需要给此进程分配CPU时间,而在等待I/O的时候,调度程序则选择其他需要CPU处理的进程。具体一点,在这样几种情况下,我们需要调度:

  1. 在创建一个新进程之后,决定是运行父进程还是子进程。(此时两个进程都处于就绪状态!)
  2. 当一个进程退出的时候(比如被杀死)
  3. 当一个进程阻塞的时候(比如等待I/O)
  4. 当一个I/O中断发生的时候(中断过后,是让等到I/O的进程运行,还是让原进程继续运行,或者再调度一个其他的进程?)

这种调度可能是抢占式的或者非抢占式的。非抢占的调度必须要等到正在运行的进程结束,而抢占式的调度则可以趁某个中断(时钟中断,I/O中断)抢占,此时原先运行的进程将被挂起。

那么什么样的调度是好的呢?一般来讲,我们对调度程序的评价主要基于以下方面:

  1. CPU使用率(CPU处于忙的时间和总时间的比率)
  2. 吞吐量(单位时间内完成的进程数量)
  3. 周转时间(一个进程从初始化到结束,包括所有等待花费的时间)
  4. 等待时间(进程在就绪队列中等待的总时间)
  5. 响应时间(一个请求从提交到第一次响应所花费的时间)
  6. 公平

调度算法

1.FCFS(先来先服务)

FCFS是一种最为直观的调度算法。即按进程请求的先后顺序安排进程的调度。

图1 FCFS进程调度

例如图中的三个进程P1,P2,P3,我们按照FCFS进行调度。

在第一种情况下,进程的周转时间=(12+15+18)/3 = 15。而在第二种情况下,进程的

周转时间=(3+6+18)/3 = 9。

这种调度方式的最大优点是简单。但通过上述计算,我们发现进程的平均等待时间和到达顺序关系很大,以及很明显的一点,如果让用时短的进程先运行,可以大幅缩短平均等待时间。

2.短任务优先

正如刚才所言,如果我们能够预先知道这些任务所需时间的长短(例如,类似的任务每天都要进行),那我们总是可以让所需时间短的任务先执行,以降低整体的等待时间。

但是这种算法也有缺陷。连续的短任务可能会使长任务一直得不到调度,从而陷入饥饿。以及如果短任务不是同时到达而是分批到达,这种算法的优势也会缩小。

如果我们使用抢占式的调度算法,那短任务优先就变成了最短剩余时间优先,即总是优先运行剩余时间最短的请求。在新请求到达的时候,把它的时间与队列中所有请求的时间相比较,如果它最短,则抢占,否则入队等待。

3.轮循调度

轮循调度是一种简单,公平的调度算法。操作系统给每个进程分配一个时间片(Quantum?),如果该进程在限定时间内未能完成,则阻塞该进程,并把CPU分给下一进程。若该进程提前完成或阻塞,则CPU立即进行切换。

这种设计的好处很明显,公平。但是公平往往会带来额外的开销。进程切换(或称上下文切换)也需要一定的时间。如果时间片过小(切换过于频繁),则大量的时间会被浪费。但如果时间片过大,又会引起交互时间过长——如果时间片足够大,轮循调度会退化成FCFS!因此,选择一个合适的时间片是相当重要的。前人的经验是将上下文切换的消耗控制在总时间的1%左右。

4.多级队列

上述的几个算法各有优劣,不同的算法可能适应于不同类型的进程。比如,几乎纯CPU的进程(比如高性能运算)就很适合使用FCFS。而一些需要及时反馈的可能更适用轮循调度。那么为什么不能为这些进程设立不同的队列呢?

多级队列就是这样的一个抽象。我们设立不同优先级的队列,并给每个队列分配时间片。当一个进程用完它的时间片之后,它被移到下一个队列。这样,需要CPU时间比较短的进程往往可以得到优先处理,而CPU消耗高的进程几乎必然被移到优先级低的队列中慢慢运行。这样既能够保证系统的反应速度,又能使CPU尽量少空转。

当然,复杂的设计必然带来更大的开销。以及还有一个我们一直没讨论的问题:在运行之前,我们怎么知道这个进程需要多长时间?

实时调度

现实生活中,我们对有些程序的要求除了能够完成任务,还要按时完成任务。这就引出了实时系统的概念。在实时系统的调度中,操作的正确性依赖于时间和功能两方面。这种系统又分软实时和硬实时,即期望按时和绝对按时。在这种系统中,我们可以采用RM(速率单调调度),即优先调度周期最短的进程,或者EDF(最早期限调度),优先调度Deadline最早的任务。


喜歡我的文章嗎?
別忘了給點支持與讚賞,讓我知道創作的路上有你陪伴。

CC BY-NC-ND 2.0 版權聲明

看不過癮?

一鍵登入,即可加入全球最優質中文創作社區