操作系统之进程管理:进程调度算法

梦里梦外; 2022-03-27 02:54 542阅读 0赞

## 进程调度算法 ##

不同环境的调度算法目标不同，因此需要针对不同环境来讨论调度算法。

###  ###

### 1.批处理系统 ###

> 批处理系统，又名批处理操作系统。[批处理][Link 1]是指用户将一批作业提交给操作系统后就不再干预，由操作系统控制它们自动运行。这种采用[批量处理][Link 2]作业技术的操作系统称为批处理操作系统。批处理操作系统分为单道批处理系统和[多道批处理系统][Link 3]。批处理操作系统不具有交互性，它是为了提高CPU的利用率而提出的一种操作系统。

批处理系统没有太多的用户操作，在该系统中，调度算法目标是保证吞吐量和周转时间（从提交到终止的时间）。

**1.1 先来先服务 first-come first-serverd（FCFS）**

按照请求的顺序进行调度。

有利于长作业，但不利于短作业，因为短作业必须一直等待前面的长作业执行完毕才能执行，而长作业又需要执行很长时间，造成了短作业等待时间过长。

**1.2 短作业优先 shortest job first（SJF）**

按估计运行时间最短的顺序进行调度。

长作业有可能会饿死，处于一直等待短作业执行完毕的状态。因为如果一直有短作业到来，那么长作业永远得不到调度。

**1.3 最短剩余时间优先 shortest remaining time next（SRTN）**

按估计剩余时间最短的顺序进行调度。

### 2.交互式系统 ###

> 交互式操作系统是为达到人机交互目的而为机器所编写的操作系统。人机交互是指人与计算机之间使用某种对话语言，以一定的交互方式，为完成确定任务的人与机器之间的信息交换过程。
> 
> 常见的交互式操作系统具体有Windows、DOS等，而操作系统三大类型中的分时操作系统也称为“事务处理使用的交互式操作系统”.

交互式系统有大量的用户交互操作，在该系统中调度算法的目标是快速地进行响应。

**2.1 时间片轮转**

将所有就绪进程按 FCFS 的原则排成一个队列，每次调度时，把 CPU 时间分配给队首进程，该进程可以执行一个时间片。当时间片用完时，由计时器发出时钟中断，调度程序便停止该进程的执行，并将它送往就绪队列的末尾，同时继续把 CPU 时间分配给队首的进程。

时间片轮转算法的效率和时间片的大小有很大关系：

*  因为进程切换都要保存进程的信息并且载入新进程的信息，如果时间片太小，会导致进程切换得太频繁，在进程切换上就会花过多时间。
 *  而如果时间片过长，那么实时性就不能得到保证。

![8c662999-c16c-481c-9f40-1fdba5bc9167.png][]

**2.2 优先级调度**

为每个进程分配一个优先级，按优先级进行调度。

为了防止低优先级的进程永远等不到调度，可以随着时间的推移增加等待进程的优先级。

**2.3 多级反馈队列**

一个进程需要执行 100 个时间片，如果采用时间片轮转调度算法，那么需要交换 100 次。

多级队列是为这种需要连续执行多个时间片的进程考虑，它设置了多个队列，每个队列时间片大小都不同，例如 1,2,4,8,..。进程在第一个队列没执行完，就会被移到下一个队列。这种方式下，之前的进程只需要交换 7 次。

每个队列优先权也不同，最上面的优先权最高。因此只有上一个队列没有进程在排队，才能调度当前队列上的进程。

可以将这种调度算法看成是时间片轮转调度算法和优先级调度算法的结合。

![042cf928-3c8e-4815-ae9c-f2780202c68f.png][]

### 3.实时系统 ###

实时系统要求一个请求在一个确定时间内得到响应。

分为硬实时和软实时，前者必须满足绝对的截止时间，后者可以容忍一定的超时。

[Link 1]: https://baike.baidu.com/item/%E6%89%B9%E5%A4%84%E7%90%86/1448600
[Link 2]: https://baike.baidu.com/item/%E6%89%B9%E9%87%8F%E5%A4%84%E7%90%86/4973973
[Link 3]: https://baike.baidu.com/item/%E5%A4%9A%E9%81%93%E6%89%B9%E5%A4%84%E7%90%86%E7%B3%BB%E7%BB%9F/3792844
[8c662999-c16c-481c-9f40-1fdba5bc9167.png]: https://cyc2018.github.io/CS-Notes/pics/8c662999-c16c-481c-9f40-1fdba5bc9167.png
[042cf928-3c8e-4815-ae9c-f2780202c68f.png]: https://cyc2018.github.io/CS-Notes/pics/042cf928-3c8e-4815-ae9c-f2780202c68f.png