CPU调度程序调度程序

作为计算机系统中的一种资源，还需要对处理器进行管理，以便调度需要分配以实现最高效率的程序，因此调度器应运而生。

1.计划程序概述

调度程序本身也是一个程序。目的是提供用于执行用户程序的资源。它包含一种算法，该算法确定一组程序中的谁将赢得CPU时钟周期。

在台式机，嵌入式设备或大型机等不同环境中，已产生了不同的调度程序。我们通常分为以下不同级别的调度程序：

高级调度程序（长期调度程序）：通常在面向批处理的多程序环境中使用，以通过平衡内存中的任务（包括CPU，内存和硬盘存储设备）来欧洲化系统资源。中期调度程序：跟踪在CPU上执行的进程的动态内存使用情况，以确定是否增加或减少“多通道程度”（争夺内存中CPU的进程数），以防止“崩溃”。脱粒意味着当前进程集合的内存需求超过了系统容量，从而导致进程在其各自的执行中变慢。低级调度程序（短期调度程序）：负责选择当前驻留在内存中的进程之一来运行。本内容中设计的算法主要针对低级调度程序。2.计划步骤

在低级调度程序中，它通常分为：非抢占式和抢占式。在非抢占式调度程序中，进程将始终执行到最后，否则它将主动放弃处理器以处理I / O请求。调度程序只是安排订单；在抢占式调度程序中，使处理器脱离当前进程并将其移交给另一个进程的调度程序具有这样的活动。无论哪种类型，调度程序的执行步骤通常如下：

获得对处理器的控制权，保存当前正在运行的进程状态（PCB，进程控制块），选择要执行的新进程，并将新选择的进程分发给处理器以运行。此步骤将把第二个状态放入该步骤中。

可以看出，在调度程序的调度过程中，过程状态非常重要。它包含很多信息：程序在何处执行（PC指针）以返回以继续执行，程序在内存中的占用空间，等等。所有信息都将在数据结构，过程控制块PCB中进行描述：

enum state_type {new, ready, running, waiting, halted};
typedef struct control_block_type {
    enum state_type state;          /* 当前状态*/
    address PC;                     /* 进程从哪里继续*/
    int reg_file[NUMBERS];          /* 通用寄存器的内容*/
    struct control_block *next_pcb; /* 链表指针 */
    int priority;                   /* 优先级等外来属性 */
    address address_space;          /* 内存位置 */
    ...;
} control_block;

PCB包含描述过程的所有必要信息。它是操作系统中非常重要的数据结构。 PCB维护通常由称为就绪队列的队列完成。就绪队列的数据结构的正确表示与调度程序的性能有关。

3.评估调度程序的性能指标

调度程序的最终目标是运行用户程序，以便可以合理地使用处理器。那么，评估调度程序算法的指标是什么？

一般的定量指标，通常我们想到的第一件事是CPU利用率。 CPU利用率可以在一定程度上解释问题。它指示CPU的繁忙程度，但由于我们不知道CPU的繁忙程度，因此不够详细。

从以系统为中心和以用户为中心，大约可以使用以下指标：

以系统为中心：

CPU利用率：CPU处理器正在运行指令的繁忙时间百分比。吞吐量：代表每单位时间完成的作业数。平均周转时间：衡量任务进入和离开系统所需的平均时间（t1 + t2 + ... + tn）/ n平均等待时间：表示系统任务的平均等待时间（w1 + w2 _... wn ）/ n

以用户为中心：

响应时间：表示特定任务的周转时间，即响应时间变化：表示给定过程的实际响应时间与其预期值之间的统计差异

除了上面介绍的量化指标外，调度程序算法的定性指标还值得一提：

饥饿：在处理作业的任何组合中，调度策略应确保所有任务始终取得进展。如果由于某种原因某个流程任务没有取得任何进展，我们称这种情况为饥饿。这种情况的定量表现是，特定任务的响应时间没有上限。传达效果：在处理作业的任何组合中，调度策略都应防止长时间运行的任务完全占用CPU。如果由于某种原因，任务调度符合固定法律（类似于陆军护送），则这种情况称为护送效果。这种现象的定量表现是任务响应时间的差异很大。4.调度算法

第二部分提到调度算法分为非抢占式和抢占式。这是一些典型的非抢先算法和抢先算法。

4.1非抢占式调度算法

1）先来先服务算法（FCFS，先来先服务）

此算法使用的属性是进程的到达时间，即启动和运行进程的时间。调度程序将首先选择第一个启动的进程，如下图所示，P1是第一个到达的进程，然后是P2，P3，因此根据先到先得的原则，调度程序将始终给予优先级到P1，然后是P2，P3。

优点：该算法具有很好的性能，即不会出现进程匮乏的情况，这意味着该算法不会返回导致任务进程拒绝服务的固有偏差。

缺点：但是由于上述性质，响应时间的差异会很大。例如，在长期任务到达之后，接着是短期任务，则短期任务被长期任务阻塞，由于效应导致CPU使用率低，其响应时间将非常糟糕。 。因此，该算法在短期内没有任何优先级。

2）作业最短（SJF，作业最短）

由于先到先得对短任务不是很友好，因此该算法旨在为短任务获得更好的响应时间。

优点：调度程序将优先处理时间较短的任务，从而使较短的任务获得更好的响应时间；

缺点：可能使长期任务很饿。

对此缺点有一个解决方案。当工作年龄达到阈值时，调度程序将忽略SJF并选择FCFS算法。

3)优先级算法

出于调度目的，大多数操作系统将为每个进程赋予属性优先级。例如，在UNIX系统中，每个用户级进程都以固定的默认优先级开始。 “就绪队列”包含多个子队列，每个子队列都对应一个优先级。每个子队列都使用FCFS算法，如下图所示：

优势：灵活并且可以提供差异化​​的服务

缺点：会发生饥饿，并且可以根据进程的等待时间来增加优先级

4.2抢占式调度算法

抢占式和非抢占式的区别在于：当新进程或刚刚完成I / O的进程进入就绪队列时，将重新评估某些属性（例如剩余执行时间），以决定是否抢占当前正在运行的进程。原则上，以上讨论的任何非抢先算法都可以转换为抢先算法，例如FCFS算法。每次重新进入就绪队列时，调度程序都可以决定抢占当前正在执行的进程（如果有新任务到达）。时间早了），同样，SJF和优先级相同。

以下介绍了两种抢占算法：

1）最短剩余时间优先（SRTF，最短剩余时间优先）

调度程序将估计每个进程的运行时间。当进程返回就绪队列时，调度程序将计算此任务的剩余处理时间，并根据计算结果将其放入就绪队列中的适当位置。如果该进程的剩余时间少于当前进程，则调度程序将抢占当前正在运行的任务，并让该新任务首先执行。与FCFS算法相比，剩余时间最短的平均等待时间通常较低。

2） RR（Round Robin）调度程序

分时环境特别适合使用RR调度程序，也就是说，每个进程都应该获得一部分处理器时间。因此，非抢占式调度程序不适用于此环境。假设有n个就绪的进程，调度程序将CPU资源划分为多个时间片，然后将它们分配给每个进程，如下图所示。就绪队列中的每个进程都会获取处理器的时间片q。当时间片用完时，当前调度的进程将被放入就绪队列的尾部，形成一个环。但是，考虑到在不同进程之间进行切换会产生开销，因此应该考虑使用适当的时间片q进行上下文切换。

5.Linux调度程序

上面讨论了一些基本算法，那么如何在Linux中安排任务？

在这里，我们讨论Linux2. 6.x版本中采用的调度框架。 Linux尝试在调度中满足不同的环境：桌面计算和服务器。桌面计算需要很高的实时性能来满互性要求，例如键盘和鼠标输入，将有许多上下文切换，因此响应时间非常重要。服务器不同，服务器承担着大量的负载，因此上下文切换越少，可以完成的任务越多。因此，Linux尝试满足调度算法中的一些目标：

高效：调度程序本身的开销很小，这是服务器环境的重要要求。支持交互性：支持桌面级环境以避免饥饿：确保计算工作量不会影响桌面交互性。工作量实时调度：确保计算性工作量不受交互影响

Linux调度程序支持3种任务：

实时先到先服务，实时RR分时

调度程序支持140个优先级，其中0表示最高优先级。其中0-99用于实时任务，用于处理交互式工作负载，100-139用于分时任务，用于处理计算工作负载。

调度器的主要数据结构如下图所示。有一个双向链接列表，其中包含140个调度优先级：

步骤：

从活动阵列中选择优先级最高的第一个来运行。如果任务被阻止，则将其放在一边，然后运行下一个任务。如果当前计划任务的时间片用完，则将其放入到期数组中。如果阻止的任务又回来，则将其放入活动阵列中相应优先级的链接列表中，并调整其剩余时间片时间。如果活动阵列中没有更多任务，请交换活动阵列和过期阵列的指针，继续运行调度算法。

值得注意的是，1）设计中的优先级数组可确保调度程序可以在恒定时间内做出调度决策，而与进程数无关，因此也称为O（1)调度程序。 2）调度程序使用实时先到先得和实时RR调度来对交互式任务进行特殊处理，以满足实时要求。

实际上，调度程序不知道哪些任务是交互式的。它使用启发式方法根据执行历史记录确定任务的性质。调度程序监视每个任务的CPU使用率模式。如果任务经常发出阻塞的I / O请求，则它是交互式的（I / O密集型）。如果任务执行的I / O很少，则它是CPU密集型工作负载。调度程序将动态增加奖励交互的优先级，同时通过降低优先级来惩罚CPU密集型任务。

最后，为了满足避免饥饿的目标，调度程序有一个饥饿阈值。如果任务在超过阈值的时间内没有获得CPU使用机会，则饥饿的任务优先级将提高。有兴趣的学生可以看一下与Linux相关的代码~~~ p

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/shoujiruanjian/article-323485-1.html