操作系统中作业的调度算法

待我称王封你为后i 2023-02-12 05:40 31阅读 0赞

选择调度方式和调度算法的若干准则

## 1．面向用户的准则 ##

(1) 周转时间短。 周转时间是指从作业被提交给系统开始，到作业完成为止的这段时间间隔(称为作业周转时间)。

包括四部分：

1、作业在外存后备队列上等待(作业)调度的时间

2、进程在就绪队列上等待进程调度的时间

3、进程在CPU上执行的时间

4、进程等待I/O操作完成的时间。

（a）周转时间 = 完成时刻 － 提交时刻（到达时间）

= 等待时间 + 运行时间(CPU)

对于进入系统的n个作业而言，平均周转时间T为:

![20200524170334473.png][]

用于衡量不同调度算法对同一作业流的调度性能： 平均周转时间越小，该作业调度算法的性能越好。

b)带权周转时间 W = 作业周转时间T／提供服务时间（CPU) 它能说明作业i的相对等待时间。

平均带权周转时间 ：

![2020052417083362.png][]

用于衡量同一调度算法对不同作业流的调度性能(长短任务差别)： 平均带权周转时间越小，作业调度算法对该作业流的调度性能越好。

对于批处理系统，主要依据平均周转时间和平均带权周转时间来作为衡量调度算法性能的指标；而对于分时系统和实时系统，外加平均响应时间作为衡量调度算法性能的指标。

(2) 响应时间快。评价分时系统的性能。

响应时间: 是从用户通过键盘提交一个请求开始，直至系统首次产生响应为止的时间。

包括三部分：

1、从键盘输入的请求信息传送到处理机的时间。

2、处理机对请求信息进行处理的时间。

3、响应信息回送到终端显示器的时间。

(3) 截止时间的保证。 评价实时系统。

(4) 优先权准则。 批处理、分时、实时系统中都可遵循。

# 2.面向系统的准则 #

### 系统吞吐量高； 处理机利用率好； 各类资源的平衡利用; ###

\---------------------------------------------------------------------------------------调度算法-----------------------------------------------------------------

## 一、先来先服务调度算法(FCFS) ##

算法: 也称为先进先出（FIFO），或严格排队方式。

对于作业调度：从后备作业队列中（按进入的时间顺序排队）选择队首一个或几个作业，调入内存，创建进程，放入就绪队列。 对于进程调度：从就绪队列中选择一个最先进入队列的进程，将CPU分配于它。

适用：进程调度、作业调度

优点: 实现简单

缺点: 没考虑进程的优先级

例1：有四个作业（或进程），他们相应的时间见下表：

<table> 
 <tbody> 
 <tr> 
 <td style="border-color:#000000;vertical-align:top;width:66pt;"> 作业 </td> 
 <td style="border-color:#000000;vertical-align:top;width:98pt;"> 到达时间 &nbsp;&nbsp;&nbsp;Tin </td> 
 <td style="border-color:#000000;vertical-align:top;width:79pt;"> 服务 时间Tr </td> 
 <td style="border-color:#000000;vertical-align:top;width:96pt;"> 开始时间TS </td> 
 <td style="border-color:#000000;vertical-align:top;width:107pt;"> 结束时间Tc </td> 
 <td style="border-color:#000000;vertical-align:top;width:106pt;"> 周转时间T </td> 
 <td style="border-color:#000000;vertical-align:top;width:125pt;"> 带权周转时间W </td> 
 </tr> 
 <tr> 
 <td style="border-color:#000000;vertical-align:top;width:66pt;"> A </td> 
 <td style="border-color:#000000;vertical-align:top;width:98pt;"> 0 </td> 
 <td style="border-color:#000000;vertical-align:top;width:79pt;"> 1 </td> 
 <td style="border-color:#000000;vertical-align:top;width:96pt;"> 0 </td> 
 <td style="border-color:#000000;vertical-align:top;width:107pt;"> 1 </td> 
 <td style="border-color:#000000;vertical-align:top;width:106pt;"> TA=1 </td> 
 <td style="border-color:#000000;vertical-align:top;width:125pt;"> WA=1 </td> 
 </tr> 
 <tr> 
 <td style="border-color:#000000;vertical-align:top;width:66pt;"> B </td> 
 <td style="border-color:#000000;vertical-align:top;width:98pt;"> 1 </td> 
 <td style="border-color:#000000;vertical-align:top;width:79pt;"> 100 </td> 
 <td style="border-color:#000000;vertical-align:top;width:96pt;"> 1 </td> 
 <td style="border-color:#000000;vertical-align:top;width:107pt;"> 101 </td> 
 <td style="border-color:#000000;vertical-align:top;width:106pt;"> TB=100 </td> 
 <td style="border-color:#000000;vertical-align:top;width:125pt;"> WB=1 </td> 
 </tr> 
 <tr> 
 <td style="border-color:#000000;vertical-align:top;width:66pt;"> C </td> 
 <td style="border-color:#000000;vertical-align:top;width:98pt;"> 2 </td> 
 <td style="border-color:#000000;vertical-align:top;width:79pt;"> 1 </td> 
 <td style="border-color:#000000;vertical-align:top;width:96pt;"> 101 </td> 
 <td style="border-color:#000000;vertical-align:top;width:107pt;"> 102 </td> 
 <td style="border-color:#000000;vertical-align:top;width:106pt;"> TC=100 </td> 
 <td style="border-color:#000000;vertical-align:top;width:125pt;"> WC=100 </td> 
 </tr> 
 <tr> 
 <td style="border-color:#000000;vertical-align:top;width:66pt;"> D </td> 
 <td style="border-color:#000000;vertical-align:top;width:98pt;"> 3 </td> 
 <td style="border-color:#000000;vertical-align:top;width:79pt;"> 100 </td> 
 <td style="border-color:#000000;vertical-align:top;width:96pt;"> 102 </td> 
 <td style="border-color:#000000;vertical-align:top;width:107pt;"> 202 </td> 
 <td style="border-color:#000000;vertical-align:top;width:106pt;"> TD=199 </td> 
 <td style="border-color:#000000;vertical-align:top;width:125pt;"> WD=1.99 </td> 
 </tr> 
 <tr> 
 <td colspan="5" style="border-color:#000000;vertical-align:middle;width:448pt;"> 平均 </td> 
 <td style="border-color:#000000;vertical-align:middle;width:106pt;"> &nbsp;&nbsp;=&nbsp;100 </td> 
 <td style="border-color:#000000;vertical-align:middle;width:125pt;"> &nbsp;&nbsp;=&nbsp;26 </td> 
 </tr> 
 </tbody> 
</table>

问题：C的周转时间是所需要处理时间的100倍！ 作业D的周转时间近乎是C的两倍，但它的带权周转时间却低于2.0。

例2．更一般的情况，设有五个作业，见下表。

<table> 
 <tbody> 
 <tr> 
 <td style="border-color:#000000;vertical-align:top;width:65pt;"> 作业 </td> 
 <td style="border-color:#000000;vertical-align:top;width:107pt;"> 到达时间Tin </td> 
 <td style="border-color:#000000;vertical-align:top;width:78pt;"> 服务时间Tr </td> 
 <td style="border-color:#000000;vertical-align:top;width:100pt;"> 开始时间Ts&nbsp; </td> 
 <td style="border-color:#000000;vertical-align:top;width:100pt;"> 结束时间Tc </td> 
 <td style="border-color:#000000;vertical-align:top;width:97pt;"> 周转时间T </td> 
 <td style="border-color:#000000;vertical-align:top;width:124pt;"> 带权周转时间W </td> 
 </tr> 
 <tr> 
 <td style="border-color:#000000;vertical-align:top;width:65pt;"> A </td> 
 <td style="border-color:#000000;vertical-align:top;width:107pt;"> 0 </td> 
 <td style="border-color:#000000;vertical-align:top;width:78pt;"> 3 </td> 
 <td style="border-color:#000000;vertical-align:top;width:100pt;"> 0 </td> 
 <td style="border-color:#000000;vertical-align:top;width:100pt;"> 3 </td> 
 <td style="border-color:#000000;vertical-align:top;width:97pt;"> TA=3 </td> 
 <td style="border-color:#000000;vertical-align:top;width:124pt;"> WA=1 </td> 
 </tr> 
 <tr> 
 <td style="border-color:#000000;vertical-align:top;width:65pt;"> B </td> 
 <td style="border-color:#000000;vertical-align:top;width:107pt;"> 2 </td> 
 <td style="border-color:#000000;vertical-align:top;width:78pt;"> 6 </td> 
 <td style="border-color:#000000;vertical-align:top;width:100pt;"> 3 </td> 
 <td style="border-color:#000000;vertical-align:top;width:100pt;"> 9 </td> 
 <td style="border-color:#000000;vertical-align:top;width:97pt;"> TB=7 </td> 
 <td style="border-color:#000000;vertical-align:top;width:124pt;"> WB=1.17 </td> 
 </tr> 
 <tr> 
 <td style="border-color:#000000;vertical-align:top;width:65pt;"> C </td> 
 <td style="border-color:#000000;vertical-align:top;width:107pt;"> 4 </td> 
 <td style="border-color:#000000;vertical-align:top;width:78pt;"> 4 </td> 
 <td style="border-color:#000000;vertical-align:top;width:100pt;"> 9 </td> 
 <td style="border-color:#000000;vertical-align:top;width:100pt;"> 13 </td> 
 <td style="border-color:#000000;vertical-align:top;width:97pt;"> TC=9 </td> 
 <td style="border-color:#000000;vertical-align:top;width:124pt;"> WC=2.25 </td> 
 </tr> 
 <tr> 
 <td style="border-color:#000000;vertical-align:top;width:65pt;"> D </td> 
 <td style="border-color:#000000;vertical-align:top;width:107pt;"> 6 </td> 
 <td style="border-color:#000000;vertical-align:top;width:78pt;"> 5 </td> 
 <td style="border-color:#000000;vertical-align:top;width:100pt;"> 13 </td> 
 <td style="border-color:#000000;vertical-align:top;width:100pt;"> 18 </td> 
 <td style="border-color:#000000;vertical-align:top;width:97pt;"> TD=12 </td> 
 <td style="border-color:#000000;vertical-align:top;width:124pt;"> WD=2.40. </td> 
 </tr> 
 <tr> 
 <td style="border-color:#000000;vertical-align:top;width:65pt;"> E </td> 
 <td style="border-color:#000000;vertical-align:top;width:107pt;"> 8 </td> 
 <td style="border-color:#000000;vertical-align:top;width:78pt;"> 2 </td> 
 <td style="border-color:#000000;vertical-align:top;width:100pt;"> 18 </td> 
 <td style="border-color:#000000;vertical-align:top;width:100pt;"> 20 </td> 
 <td style="border-color:#000000;vertical-align:top;width:97pt;"> TE=12 </td> 
 <td style="border-color:#000000;vertical-align:top;width:124pt;"> WE=6 </td> 
 </tr> 
 <tr> 
 <td colspan="5" style="border-color:#000000;vertical-align:middle;width:452pt;"> 平均 </td> 
 <td style="border-color:#000000;vertical-align:middle;width:97pt;"> &nbsp;&nbsp;=8.60 </td> 
 <td style="border-color:#000000;vertical-align:middle;width:124pt;"> &nbsp;&nbsp;&nbsp;=&nbsp;2.56 </td> 
 </tr> 
 </tbody> 
</table>

同样，看到作业E的不利情况。

结论：有利于长作业(进程)，不利于短作业(进程)。 即：有利于CPU繁忙型的作业，不利于I/O繁忙型的作业(进程)。

## 二、短作业(进程)优先调度算法（SJ(P)F） ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dhbmdoYW9kcmVhbQ_size_16_color_FFFFFF_t_70][]

两种算法对比：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dhbmdoYW9kcmVhbQ_size_16_color_FFFFFF_t_70 1][]

适用：进程调度、作业调度 优点：易于实现，效率比较高，降低作业的平均等待时间。

缺点：1、只照顾短作业而不考虑长作业的利益，长作业长时间等待而“饿死”。

2、未考虑作业的紧迫程度

3、估计执行时间不足，算法无法真正实现

## 三、高优先权优先调度算法（HPF） ##

算法：总是把处理机分配给就绪队列中具有最高优先权的进程。

适用：作业调度、进程调度

分类： 1) 非抢占式优先权算法

用于批处理系统中、实时性不高的实时系统中。

2）抢占式优先权调度算法

优先权的类型

1) 静态优先权

静态优先权是在创建进程时确定的，且在进程的整个运行期间保持不变。如: 0～7或0～255中的某一整数表示优先权。 依据：

(1) 进程类型。系统进程（接收进程）：高；用户进程：低。

(2) 进程对资源的需求。进程估计CPU时间、内存需要量少：高。

(3) 用户要求。进程紧迫程度、用户所付费用确定。

优点：简单易行，系统开销小；

缺点：不够精确，优先权低的长作业长期没有被调度的情况。

适用：要求不高的系统中。

2) 动态优先权

在进程创建时创立一个优先权，但在其生命周期内优先数可以动态变化。 如: 等待时间长优先数可改变。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dhbmdoYW9kcmVhbQ_size_16_color_FFFFFF_t_70 2][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dhbmdoYW9kcmVhbQ_size_16_color_FFFFFF_t_70 3][]

## 四、高响应比优先调度算法（ HRP ） ##

响应比是指作业的响应时间与作业估计运行时间的比值。

![20200524171937662.png][]

![20200524171956637.png][]

![20200524172018276.png][]

选择原则： 优先选取响应比值最大的作业。即兼顾等待时间长和运行时间短的作业，它是FCFS和SJF算法的结合。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dhbmdoYW9kcmVhbQ_size_16_color_FFFFFF_t_70 4][]

## 五、基于时间片的轮转调度算法（RR ##

在分时系统中，为了满足系统对响应时间的要求，通常采用时间片轮转调度算法。

1. 简单轮转法(固定时间片轮转法）--早期 1）原理：系统把所有就绪进程按到达的先后顺序（ FIFO ）形成一个就绪队列，就绪队列中的所有进程按时间片依次轮流获得处理机。系统能在给定的时间内响应所有用户的请求。

2) 时间片大小的确定 a.对系统性能有很大影响： 如：时间片很小：有利短作业、频繁地发生中断、进程上下文的切换。 时间片太长，每个进程都能在一个时间片内完成，退化为FCFS算法，无法满足交互式用户的需求。 b.可行选取： 时间片略大于一次典型的交互所需要的时间，可使大多数进程在一个时间片内完成。 时间片的大小应根据进程要求系统给出应答的时间和进入系统的进程数来决定。可以表示为：

![20200524172408266.png][]

其中，q是时间片的大小，T是系统的响应时间，N是进入系统的进程数。

例： 有五个任务A, B, C, D, E，它们几乎同时先后到达，预计它们运行时间为10，6，2，4，8min，采用时间片轮转算法，令时间片为2min，计算其平均进程周转时间。（进程切换可不考虑）

解：5个任务轮流执行的情况为：

第1轮 (A, B, C, D, E)

第2轮 (A, B, D, E)

第3轮 (A, B, E)

第4轮 (A, E)

第5轮 (A)

平均周转时间 T=(30+22+6+16+28)/5=20.4min

3) 简单轮转法的优缺点:

优点：简单、方便。

缺点：

a.由于采用固定时间片的方式，调度欠灵活。

b.服务质量不够理想。

改进：

a.将固定时间片方式改为可变时间片方式；

ⅰ. 固定周期轮转法: 每一轮调度中所得的时间片q值的大 小仅在这一轮调度中有效。系统的响应时间T固定，在 每一轮调度中，根据当前就绪队列中的进程数n计算这 一轮调度。

ⅱ. 时间片的大小取决于优先级的高低，优先级高的进程分得的时间片较大，优先级低的进程分得的时间片较小。 ⅲ. 短作业的时间片较小，长作业的时间片较大。

b.将单就绪队列改为多就绪队列。

[20200524170334473.png]: https://img-blog.csdnimg.cn/20200524170334473.png
[2020052417083362.png]: https://img-blog.csdnimg.cn/2020052417083362.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dhbmdoYW9kcmVhbQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2020052417111729.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dhbmdoYW9kcmVhbQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dhbmdoYW9kcmVhbQ_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/2020052417142674.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dhbmdoYW9kcmVhbQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dhbmdoYW9kcmVhbQ_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/2020052417174819.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dhbmdoYW9kcmVhbQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dhbmdoYW9kcmVhbQ_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200524171831896.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dhbmdoYW9kcmVhbQ==,size_16,color_FFFFFF,t_70
[20200524171937662.png]: https://img-blog.csdnimg.cn/20200524171937662.png
[20200524171956637.png]: https://img-blog.csdnimg.cn/20200524171956637.png
[20200524172018276.png]: https://img-blog.csdnimg.cn/20200524172018276.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dhbmdoYW9kcmVhbQ_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200524172240645.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dhbmdoYW9kcmVhbQ==,size_16,color_FFFFFF,t_70
[20200524172408266.png]: https://img-blog.csdnimg.cn/20200524172408266.png