操作系统中的CPU调度详细指南

2021年4月3日17:19:10 发表评论 954 次浏览

完成了流程/工作的计划以按时完成工作。

以下是关于过程的不同时间。

到达时间：流程到达就绪队列的时间。
完成时间：流程完成其执行的时间。
突发时间：进程执行CPU所需的时间。
周转时间：完成时间与到达时间之间的时间差。
周转时间=完成时间–到达时间
等待时间(W.T)：周转时间与突发时间之间的时间差。
等待时间=周转时间–爆发时间

我们为什么需要安排时间？

一个典型的过程同时涉及I/O时间和CPU时间。在像MS-DOS这样的单编程系统中, 浪费了等待I/O的时间, 并且CPU在这段时间内是空闲的。在多编程系统中, 一个进程可以使用CPU, 而另一个进程正在等待I/O。这仅在过程计划中可行。

流程调度算法的目标

最大CPU利用率[保持CPU尽可能繁忙]
CPU的公平分配。
最大吞吐量[每个时间单位完成执行的进程数]
最小周转时间[一个进程完成执行所花费的时间]
最小等待时间[一个进程在就绪队列中等待的时间]
最小响应时间[一个进程产生第一次响应的时间]

不同的调度算法

先来先服务(FCFS):根据进程的到达时间进行调度的最简单的调度算法。先到先服务调度算法指出, 先请求CPU的进程先分配CPU。它是通过使用FIFO队列实现的。当进程进入就绪队列时, 其PCB将链接到队列尾部。当CPU空闲时, 它将分配给队列开头的进程。然后将正在运行的进程从队列中删除。 FCFS是一种非抢占式调度算法。

注意：先到先得车队效应.

最短作业优先(SJF):首先安排突发时间最短的进程, 如果两个进程的胸围时间相同, 则使用FCFS打破平局。它是一种非抢占式调度算法。

最长工作优先(LJF)：它类似于SJF调度算法。但是, 在这种调度算法中, 我们优先考虑突发时间最长的进程。这本质上是非抢占式的, 即任何进程开始执行时, 在完成执行之前都不能中断。

最短剩余时间优先(SRTF):这是SJF算法的抢占模式, 其中, 作业根据最短的剩余时间进行调度。

最长剩余时间优先(LRTF):这是LJF算法的抢占模式, 在该模式中, 我们优先考虑具有最大突发时间的进程。

循环调度:每个过程都以循环方式分配固定的时间(时间量/时间片), 这是专门为分时系统设计的。准备队列被视为循环队列。 CPU调度程序会绕过就绪队列, 将CPU分配给每个进程的时间间隔最多为1次。为了实现循环调度, 我们将就绪队列保留为进程的FIFO队列。新进程将添加到就绪队列的末尾。 CPU调度程序从就绪队列中选择第一个进程, 将计时器设置为在1次量子时间后中断, 然后分派该进程。然后将发生两件事之一。该进程的CPU突发次数可能少于1倍。在这种情况下, 进程本身将自动释放CPU。然后, 调度程序将进入就绪队列中的下一个过程。否则, 如果当前正在运行的进程的CPU突发时间超过1倍时间, 则计时器将关闭并导致操作系统中断。将执行上下文切换, 并将该过程放在就绪队列的末尾。然后, CPU调度程序将在就绪队列中选择下一个进程。

基于优先级的调度(非抢占式):在该调度中, 根据进程的优先级来调度进程, 即, 优先级最高的进程被调度。如果两个进程的优先级匹配, 则根据到达时间进行调度。在这里饥饿可能发生。

最高响应比率下一个(HRRN):在此调度中, 将调度具有最高响应率的进程。该算法避免了饥饿。

Response Ratio = (Waiting Time + Burst time)/Burst time

多级队列调度: 根据进程的优先级, 将进程放置在不同的队列中。通常, 高优先级的进程放置在顶层队列中。仅在高层队列中的进程完成后, 才调度较低层队列中的进程。它可能遭受饥饿。

多级反馈队列调度:它允许进程在队列之间移动。想法是根据CPU突发的特征来分离进程。如果某个进程占用过多的CPU时间, 则会将其移至优先级较低的队列。

有关调度算法的一些有用事实：

FCFS可能导致较长的等待时间, 尤其是在第一个作业占用过多CPU时间时。
SJF和最短剩余时间优先算法都可能导致饥饿。考虑以下情况：就绪队列中有较长的进程, 而较短的进程不断出现。
如果Round Robin调度的时间量很大, 则其行为与FCFS调度相同。
对于给定的一组过程, SJF的平均等待时间是最佳的, 即, 使用此调度, 平均等待时间最短, 但是问题在于如何知道/预测下一个作业的时间。

练习：

1. 考虑一个需要40倍突发时间单位的系统。使用多级反馈队列调度, 并且时间量为顶部队列2个单位, 并且在每个级别上增加5个单位, 那么该进程将在哪个队列中终止执行？

2. 关于SJF, 以下哪项是错误的？

S1：它导致最小的平均等待时间

S2：它可能导致饥饿

(A)仅S1

(B)仅S2

(C)S1和S2

(D)S1和S2都不是

答案(D)

S1是正确的SJF将始终提供最小的平均等待时间。

S2是真的SJF会导致饥饿。

3. 考虑以下三个过程P0, P1和P2的到达时间和突发时间表。 (GATE-CS-2011)

Process   Arrival time   Burst Time
P0            0 ms          9 ms
P1            1 ms          4 ms
P2            2 ms          9 ms

使用抢先式最短作业优先调度算法。计划仅在过程到达或完成时执行。这三个过程的平均等待时间是多少？

(A)5.0毫秒

(B)4.33毫秒

(D)7.33

解决方案：

答案：–(A)

在就绪队列中没有其他进程, 因此在0 ms处为进程P0分配了处理器。由于P1到达1 ms且P1的突发时间小于P0的剩余时间, 因此1 ms之后P0被抢占。 P1运行4ms。 P2到达2毫秒, 但是P1继续, 因为P2的突发时间比P1长。在P1完成之后, 由于P0的剩余时间小于P2的突发时间, 因此再次计划P0。

P0等待4毫秒, P1等待0毫秒, P2等待11毫秒。因此平均等待时间为(0 + 4 + 11)/ 3 = 5。

4. 考虑以下一组进程, 以毫秒为单位给出到达时间和CPU突发时间(GATE-CS-2004)

Process   Arrival Time    Burst Time
    P1          0              5
    P2          1              3
    P3          2              3
    P4          4              1

抢先最短剩余处理时间优先(SRPT)算法的这些流程的平均周转时间是多少？

(A)5.50

(B)5.75

[C)6.00

(D)6.25

答案(A)

解：

以下是甘特图执行图

P1	P2	P4	P3	P1
1	4	5	8	12

周转时间=完成时间–到达时间

平均周转时间=(12 + 3 + 6 + 1)/ 4 = 5.50

操作系统使用最短剩余时间优先(SRTF)进程调度算法。考虑以下过程的到达时间和执行时间：

Process  Execution time  Arrival time
P1             20            0
P2             25            15
P3             10            30
P4             15            45

流程P2的总等待时间是多少？

(A)5

(B)15

(D)55

答案(B)

在时间0, P1是唯一的过程, P1运行15个时间单位。

在时间15, P2到达, 但是P1的剩余时间最短。因此, P1将再继续5个时间单位。

在时间20, P2是唯一的过程。因此它可以运行10个时间单位

在时间30, P3是最短的剩余时间过程。因此它可以运行10个时间单位

在时间40, P2运行, 因为它是唯一的过程。 P2运行5个时间单位。

在时间45, P3到达, 但是P2的剩余时间最短。因此, P2将再继续10个时间单位。

P2在时间55完成执行

Total waiting time for P2 = Completion time - (Arrival time + Execution time)
                          = 55 - (15 + 25)
                          = 15

请参考CPU调度测验有关更多问题。

参考文献：

http://www.cs.uic.edu/~jbell/CourseNotes/OperatingSystems/5_CPU_Scheduling.html

http://codex.cs.yale.edu/avi/os-book/OS8/os8c/slide-dir/PDF-dir/ch5.pdf

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请发表评论。