调度算法小结

悠悠 2022-06-13 14:38 284阅读 0赞

处理机管理的工作是对CPU进行合理的分配使用，以提高处理机利用率，并使各用户公平地得到处理机资源。

CPU可分配的资源是在处理器上的执行时间，分配的途径是调度。

处理机调度的层次**：**高级调度、低级调度、中级调度

调度算法就是一种资源分配算法。

有的算法适用于作业调度，有的算法适用于进程调度，有的两者都适应。

**1) 先来先服务(FCFS/first come first serve)**

**2) 短作业优先(SPF/Shortest Process First)**

**3) 时间片轮转算法(Round Robin)**

**4) 优先级算法(PS/priority Scheduling)**

**5) 高响应比优先调度算法(HRNN/Highest Response Ratio Next)**

**6) 多级队列算法**

**7) 多级反馈队列算法(FB/Multilevel Feedback-Queue scheduling)**

以下为转载内容，转载地址：[http://blog.csdn.net/leves1989/article/details/3305599][http_blog.csdn.net_leves1989_article_details_3305599]

**【例1】**下表给出作业l，2，3的提交时间和运行时间。采用先来先服务调度算法和短作业优先调度算法，试问作业调度次序和平均周转时间各为多少？（时间单位：小时，以十进制进行计算。）

**分析** 解这样的题关键是要根据系统采用的调度算法，弄清系统中各道作业随时间的推进情况。我们用一个作业执行时间图来形象地表示作业的执行情况，帮助我们理解此题。

采用先来先服务调度算法，是按照作业提交的先后次序挑选作业，先进入的作业优先被挑选。然后按照“排队买票”的办法，依次选择作业。其作业执行时间图如下：

采用短作业优先调度算法，作业调度时根据作业的运行时间，优先选择计算时间短且资源能得满足的作业。其作业执行时间图如下：

由于作业1，2，3是依次到来的，所以当开始时系统中只有作业1，于是作业1先被选中。在8.0时刻，作业1运行完成，这时系统中有两道作业在等待调度，作业2和作业3，按照短作业优先调度算法，作业3只要运行1个时间单位，而作业2要运行4个时间单位，于是作业3被优先选中，所以作业3先运行。待作业3运行完毕，最后运行作业2。作业调度的次序是1，3，2。

另外，要记住以下公式：  
作业i的周转时间Ti＝作业完成时间－作业提交时间  
    系统中n个作业的平均周转时间![f1.htm3.gif][] ，其中Ti为作业i的周转时间。

**解**：采用先来先服务调度策略，则调度次序为1、2、3。

作业号       提交时间      运行时间        开始时间        完成时间          周转时间  
1               0.0                            8.0                       0.0                   8.0                8.0  
2               0.4                            4.0                       8.0                  12.0                11.6  
3               1.0                            1.0                      12.0                 13.0               12.0

平均周转时间T＝（8＋11.6＋12）/3＝10.53

采用短作业优先调度策略，则调度次序为1、3、2。

作业号       提交时间            运行时间            开始时间            完成时间            周转时间  
1              0.0                           8.0                      0.0                      8.0                      8.0  
3              1.0                           1.0                      8.0                      9.0                       8.0  
2              0.4                           4.0                      9.0                      13.0                    12.6

平均周转时间T＝（8＋8＋12.6）/3＝9.53

**思考题1**  
请同学们判断这句话：作业一旦被作业调度程序选中，即占有了CPU。（  错  ）  
提示：需要清楚作业调度和进程调度的区别。

**【例2】**在一个单道的程序设计系统中，有3个作业J1、J2、J3，它们到达输入井的时间分别为8：50、9：00、9：30，它们需要执行的时间分别为1.5小时、0.4小时、1小时。系统在10：00按响应比高者优先算法对它们进行调度，请回答：（1）作业被选中执行的次序是什么？ （2）每个作业被选中时的响应比分别是多少？  
**分析 **响应比＝作业周转时间/作业运行时间 ＝1＋作业等待时间/作业运行时间  
系统在10：00，计算作业的响应比：  
    以J1为例，它的作业计算时间是1.5小时，即90分钟；J1从8：50到达输入井，在10：00时刻，J1的等待时间为70分钟，因此作业J1的响应比为：1＋70分钟/90分钟=1.77    
同理，J2：1＋60分钟/24分钟=3.5    J3：1＋30分钟/60分钟=1.5  
因此按照响应比高者优先算法，优先调度J2。  
在10：24，J2完成。这时计算J1、J3的响应比：  
     J1：1＋（70＋24）分钟/90分钟=2.04    J3：1＋（30＋24）分钟/60分钟=1.9    
   按照响应比高者优先算法，优先调度J1。  
    在11：54，J1完成，系统调度J3，J3的响应比为1＋（30＋24＋90）分钟/60分钟=3.4 因此，作业被选中执行的次序是J2、J1、J3。  
    三个作业被选中时的响应比分别是：J1，2.04；J2，3.5；J3，3.4。

**解**：（1）作业被选中执行的次序是J2、J1、J3。  
         （2）三个作业被选中时的响应比分别是：J1，1.04；J2，2.5；J3，2.4。

**思考题2  
       **某作业的提交时间为10：30，需要运行的时间为1小时，假设11：00开始调度，它的响应比是     1.5        。

**【例3】**设有进程A、B、C、D依次进入就绪队列（相隔一个时间单位），它们的优先级（优先数大的优先级较高）如下表所示：

<table> 
 <tbody> 
 <tr> 
 <td> 进程 </td> 
 <td> CPU时间 </td> 
 <td> 优先数 </td> 
 </tr> 
 <tr> 
 <td> A </td> 
 <td> 20 </td> 
 <td> 3 </td> 
 </tr> 
 <tr> 
 <td> B </td> 
 <td> 15 </td> 
 <td> 1 </td> 
 </tr> 
 <tr> 
 <td> C </td> 
 <td> 8 </td> 
 <td> 4 </td> 
 </tr> 
 <tr> 
 <td> D </td> 
 <td> 10 </td> 
 <td> 3 </td> 
 </tr> 
 </tbody> 
</table>

试问采用“先来先服务”、“静态优先数法”调度算法（注：优先数大的优先级高），选中进程的执行次序。  
**解**：采用先来先服务调度算法，按照进程进入就绪队列的先后次序占有CPU，其执行次序是A-B-C-D。  
采用静态优先数法，进程A最先就绪，在0时刻先占有CPU运行，随后1时刻进程B进入就绪队列，2时刻进程C进入就绪队列，3时刻进程D进入就绪队列。由于采用静态优先数法，不容许随时间的推移改变进程的优先级，所以当进程A运行结束时，系统的就绪队列中有B、C、D三个进程，而进程C优先级最高，于是选中C；这样分析下去，进程的执行次序是A-C-D-B。

**思考题3  
    **时间片轮转调度算法是为了（  A  ）。  
   A．多个终端都能得到系统的及时响应     B．先来先服务  
   C．优先级高的进程先使用CPU           D．紧急事件优先处理

[http_blog.csdn.net_leves1989_article_details_3305599]: http://blog.csdn.net/leves1989/article/details/3305599
[f1.htm3.gif]: http://www.webpx.net/oldxul/czxt/files/f1.htm3.gif