操作系统中的CPU调度-yiteyi-C++库

安排流程/工作以按时完成工作。

null

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

到达时间： 进程到达就绪队列的时间。 完成时间： 进程完成执行的时间。 突发时间： 进程执行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和最短剩余时间优先算法都可能导致饥饿。考虑一个情况，当长进程在就绪队列中时，更短的进程不断出现。

如果循环调度的时间量非常大，则其行为与FCFS调度相同。

就给定一组流程的平均等待时间而言，SJF是最优的，即该调度的平均等待时间是最小的，但问题是，如何知道/预测下一个作业的时间。

练习：

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

关于SJF，以下哪项是错误的？ S1：平均等待时间最短 S2：它会导致饥饿（A）只有S1 （B）只有S2 （C） S1和S2 （D）既不是S1也不是S2 答复（D） S1是真的，SJF总是给出最小的平均等待时间。 S2是真的SJF会导致饥饿。

考虑三个进程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毫秒（C） 6.33 （D） 7.33 解决方案：答：–（A）进程P0在0毫秒时分配给处理器，因为就绪队列中没有其他进程。当P1到达1ms时，P0在1ms后被抢占，P1的突发时间小于P0的剩余时间。P1运行4ms。P2到达2毫秒，但P1继续，因为P2的突发时间比P1长。P1完成后，由于P0的剩余时间小于P2的突发时间，因此再次调度P0。 P0等待4毫秒，P1等待0毫秒，P2等待11毫秒。因此平均等待时间为（0+4+11）/3=5。

考虑下面的一组过程，以毫秒为单位的到达时间和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点（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）五, （B） 15 （C） 40 （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_调度。html

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

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

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章