学习笔记——OS处理机调度

淩亂°似流年 2023-07-24 09:03 19阅读 0赞

在多道程序环境下，内存中存在着多个进程。要求系统按照某种算法，动态地将处理机分配给处于就绪状态的一个进程，使之执行。

问题：为什么进行处理机调度？

若没有处理机调度，意味着当前进程运行完后，才能进行下一进程，而当前进程有可能进行I/O操作，从而占用CPU空闲时

间。引进处理机调度，则可在这段时间，将处理机分配给其它进程，提高CPU利用率。

### 一、调度的基本概念及层次 ###

**1.调度的实质**就是一种资源分配，处理机调度是对处理机资源进行分配。

**2.处理机调度的层次**

**1)高级调度(长程调度、作业调度)**  
 根据某种算法，决定将外存上处于后备队列中的哪几个作业调入内存；

为他们创建进程、分配必要的资源，并将它们放入就绪队列。

高级调度主要用于批处理系统中，分时系统和实时系统不设置高级调度，因为对时间要求较高。

**2)低级调度(进程调度、短程调度)**  
根据某种算法，决定就绪队列中的哪个进程获得处理机，将处理机分配给被选中的进程。是最基本的一种调度，运行频率 高。

**3)中级调度(内存调度)**  
引入目的：提高内存利用率和系统吞吐量。

将暂时不能运行的进程（就绪状态）调入外存等待（挂起状态）。当环境合适时，再调入内存（就绪状态）。

中级调度实质上就是存储器管理中的对换功能。

**3.三级调度的联系**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xZXzYyNA_size_16_color_FFFFFF_t_70][]

作业调度从外存中选择一批作业调入内存，为它们创建进程，送入就绪队列；进程调度从就绪队列中选择一个进程，为它 分配CPU及所需的资源。

三者使用频率：进程调度>中级调度>作业调度

### 二、调度算法的基本准则 ###

**1.共同目标**

1)资源利用率

![20200410164941270.PNG][]

2)公平性：诸进程都可以获得相对合理的CPU时间，不会发生进程饥饿现象。

3)平衡性：每个系统中有多种进程，不要只有I/O，或者只做计算。

4)策略强制执行：如安全策略，即使降低利用率，也要强制执行。

**2.批处理系统目标**

1)平均周转时间短。是指从作业被提交给系统开始，到作业完成为止。

作业外存后备队列等待时间+进程就绪队列排队时间+进程CPU执行时间+进程等待I/O操作完成时间

2)系统吞吐量高。是指单位时间内系统完成的作业数。

3)处理机利用率高。

**3.分时系统目标**

1)响应时间块。是指从用户通过键盘提交一个请求开始，到屏幕上显示出处理结果为止的一段时间间隔。

请求信息传给处理机时间+处理机对请求信息处理时间+响应信息送给终端显示器。

2)均衡性。系统响应时间英语用户请求服务的复杂性相适应。

**4.实时系统目标**

1)截止时间保证。是指某任务必须开始执行的最迟时间，或必须完成的最迟时间。

2)可预测性。比如多媒体系统，视频的连续播放。

### 三、调度的时机 ###

现代操作系统，不能进行进程调度与切换的情况：

1)在处理中断的过程中：中断比较复杂，是系统工作的一部分

2)进程在OS内核程序临界区：进入临界区，需独占数据，理论上应加锁，防止其他程序进入

3)其他需屏蔽中断的原子操作过程中：加锁、解锁、中断现场保护、恢复等

### 四、作业与作业调度 ###

**1.作业基本概念**

一个典型的作业分为：编译—>链接配置—>运行

作业控制块(JCB)：作业在系统中存在的标志，保存了系统对作业进行管理和调度所需的全部信息。

JCB内容：作业标识、用户名称、作业类型（I/O繁忙型、终端型、CPU繁忙型）、作业状态、调度信息（优先级、运行时 间）等

**2.作业的状态及转换**

三个状态：收容、运行和完成。

1)收容阶段：“后备状态”用户提交，建立JCB，放入后备队列。

2)运行阶段：“运行状态”被作业调度选中，分配资源，放入就绪队列，直到运行结束。

3)完成阶段：“完成状态”作业完成或异常提前结束，回收分配的资源，输出运行结果。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xZXzYyNA_size_16_color_FFFFFF_t_70 1][]

**3.作业调度的主要任务**

根据JCB的信息，检查系统资源是否满足作业需求，按照一定的调度算法，从外存后备队列选取作业调入内存，为它们创建 进程，分配资源，放入就绪队列等待调度。

每次调度作业考虑两个问题：

1)接纳多少个作业：取决于多道程序度，即允许多少个作业同时在内存中运行。

2)接纳哪写作业：取决于调度算法。

**4.作业调度的几个算法**

1)先来先服务调度算法（first-come first-served，FCFS）

既可用于作业调度，也可用于进程调度。

按照作业到达的先后次序进行调度，或者说优先考虑系统中等待时间最长的作业。

注意：不利于短作业，不利于紧急型作业。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xZXzYyNA_size_16_color_FFFFFF_t_70 2][]

2)短作业优先调度算法（short job first，SJF）

既可用于作业调度，也可用于进程调度。

按照作业的长度按计算优先级，即作业越短，越先运行。作业的长短是以作业所要求的运行时间来衡量的。

平均周转时间最短。

不足之处：必须预知作业的运行时间；长作业的周转时间增长；无法考虑紧迫度。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xZXzYyNA_size_16_color_FFFFFF_t_70 3][]

3)优先级调度算法（priority-scheduling algorithm，PSA）

既可用于作业调度，也可用于进程调度。

由外部赋予作业的优先级，按作业优先级进行调度。

FCFS：优先级为等待时间 SJF：优先级为作业运行时间

4)高响应比优先调度算法（Highest Response Ratio Next，HRRN）

![20200410183642934.png][]

Rp为响应比，即作为优先权。

即考虑作业等待时间（FCFS），又考虑作业运行时间（SJF）

由上式可以看出：

作业等待时间相同，要求服务时间越短，优先权越高，即有利于短作业；

要求服务时间相同，作业等待时间越长，优先级越高，即FCFS；

是FCFS与SJF的折中，但响应比计算会增加系统开销。

### 五、进程调度 ###

**1.进程调度任务**

保存处理机的现场信息；按某种算法选取进程；把处理器分配给进程

**2.进程调度的方式**

**1)非抢占方式**

一旦处理机分配给某进程，就会一直执行下去，绝不允许因为时钟中断或其他原因抢占当前正在运行进程的处理机。

只有出现某种问题而被阻塞时，才将处理机分配给其它进程。

**2)抢占方式**

允许调度程序根据某种原则，暂停正在执行的进程，将处理机分配给其它进程。

现代OS一般会采用，批处理系统：避免长时间一个进程占用，提高公平

分时系统：实现人机交互

实时系统：满足实时任务

“抢占”不是一种任意性行为，必须遵循一定的原则：

优先权原则：新到的进程优先权高，可抢占

短进程优先原则：新到的进程短，可抢占

时间片原则：各进程按时间片轮转运行，一个进程时间片用完后，重新调度

**3.进程调度算法**

1)轮转调度算法（round robin，RR）

基于时间片的轮转调度算法，让就绪队列上的每个进程仅运行一个时间片。通常用于分时操作系统

原理：在RR中，系统根据FCFS策略，将所有就绪进程排成一个就绪队列，每隔一段时间产生一个中断，进行进程调 度，将CPU分配给队首进程。而时间片耗尽的进程加入就绪队列末尾。

问题：时间片大小的确定，使大多数交互式进程能在一个时间片内完成，获得很小的响应时间。

若时间片太小，则会频繁进程上下文切换

若时间片太大，则退化为FCFS

2)多级反馈队列调度算法

调度机制：

设置多个就绪队列，设置不同的优先级。优先级依次降低，队列1>队列2>...

每个队列都采用FCFS算法。当新进程进入内存后，放入第1个队列的末尾；若此进程时间片内未完成，放入第2个 队列末尾；以此类推...；当进程降到n个队列，则采用RR方式。

按队列优先级调度。仅当第1~（i-1）所有队列均空时，才会调度第i个队列中的进程执行。若当前进程i正在运行， 高优先级的新进程到来，则把正在进行的进程放到第i个队列末尾，把处理机分配给优先级高的新进程。

![20200410194608954.png][]

优势：

1)终端型作业用户：短作业优先 较小，放在第一队列

2)短批处理作业用户：周转时间短 稍长的短作业，放在二、三队列

3)长批处理作业用户：不会长期得不到处理 依次在1、2、3...队列中运行

**4.各种进程调度算法的比较**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xZXzYyNA_size_16_color_FFFFFF_t_70 4][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xZXzYyNA_size_16_color_FFFFFF_t_70]: /images/20230528/afa101d7639446b7a9781b99a8bdd5ba.png
[20200410164941270.PNG]: /images/20230528/606ca782137f48c6884734874e3d0913.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xZXzYyNA_size_16_color_FFFFFF_t_70 1]: /images/20230528/4d4149a019074c87a015f3a591f11332.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xZXzYyNA_size_16_color_FFFFFF_t_70 2]: /images/20230528/dc073b82ba584964954a4830810770b3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xZXzYyNA_size_16_color_FFFFFF_t_70 3]: /images/20230528/24bfeec230064009bc1db108c04f0201.png
[20200410183642934.png]: /images/20230528/b1b7fd8d667c4137b2fef975919e0f4f.png
[20200410194608954.png]: /images/20230528/4673fb1b9c964df6abab33a42fc89612.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xZXzYyNA_size_16_color_FFFFFF_t_70 4]: /images/20230528/bff5b50b962f4694bf1ad2e5d8aa8e79.png