操作系统原理第三章 -- 处理机调度

系统管理员 2022-02-04 13:57 505阅读 0赞

计算机操作系统（第四版）

### 一、关于处理机调度的问题 ###

1.  什么是处理机三级调度
2.  处理机三级调度分别在什么情况下发生
3.  各级调度分别完成什么工作
4.  三种调度的区别

**(1) 操作系统中有三级调度：**

1.  高级调度(作业调度)
2.  中级调度(交换调度)
3.  低级调度(进程调度)

它们构成系统内的多级调度。  
不同类型的操作系统不一定完全都实现上述三种调度。

**(2) 处理机三级调度分别在如下情况下发生：**

**1，高级调度。**高级调度是根据系统内所有资源的使用情况，一旦可能便从后备作业中选择一道作业进入系统，并创建相应的进程，分配必要的系统资源，然后将进程“就绪”。

**2，低级调度。**低级调度即为CPU调度，它是根据CPU资源的使用情况及时分配CPU，即从“就绪”的进程中选择一个进程在CPU上“运行”。这种调度不仅要求调度算法本身的时间复杂度小，而且要求策略精良，因为低级调度直接影响着系统的整体效率。在多道程序系统中必须提供低级调度。

**3，中级调度。**在内存中常常有许多进程处于某种等待状态，这些进程在“等待”期间无谓地占用着内存资源，如将它们暂时换至外存，则所节省出来的内存空间可用以接纳新的进程。一旦被换至外存的进程具备运行条件，再将其重新换入内存。为此，在逻辑上将主存延伸，用一部分外存空间(称为交换区)替代主存，并且实施交换调度(中级调度)。在各种类型的操作系统中可以根据内存的配置和系统能承受的最大负载，有选择地进行中级调度，或者不实施中级调度。

**(3) 各级调度的工作：**

1，高级调度完成作业调度，使“后备”状态的作业 变为 “执行”状态；

2，中级调度完成内存和外存信息的交换调度；

3，低级调度完成进程调度，使“就绪”的进程在CPU上“运行”。

**(4) 三种调度的区别：**

1，高级调度又称作业调度，作业就是用户程序及其所需的数据和命令的集合，作业管理就是对作业的执行情况进行系统管理的程序的集合。作业调度程序的主要功能是审查系统是否能满足用户作业的资源要求以及按照一定的算法来选取作业。

2，引入中级调度的主要目的是为了提高内存的利用率和系统吞吐量，使得暂时不运行的进程从内存对换到外存上。

3，低级调度又称进程调度，其主要功能是根据一定的算法将cpu分派给就绪队列中的一个进程。进程调度是操作系统中最基本的一种调度，其调度策略的优劣直接影响整个系统的性能。

### 二、一些概念 ###

**1，进程调度：在多道批处理、分时和实时三种类型的OS中，都必须配置这级调度。**

**2，处理机调度算法的共同目标：资源利用率；公平性；平衡性；策略强制执行。**

**3，批处理系统的目标：平均周转时间短；系统吞吐量高；处理机利用率高。**

**4，周转时间： 从作业被提交给系统开始，到作业完成为止的这段时间间隔。**

**5，带权周转时间：周转时间/运行时间**

**6，JCB：作业控制块**

**7，作业状态：提交状态、后备状态、运行状态、完成状态。**

**8，进程周转时间：从进程进入就绪队列开始，到进程完成为止的时间间隔。**

**9，平均周转时间：系统中多个进程的周转时间的平均值。**

### 三、几个算法 ###

**1，先来先服务（FCFS）调度算法**

**2，短作业优先（SJF）调度算法**  
与FCFS算法比较，平均周转时间有下降，有效地降低作业的等待时间，提高了系统的吞吐量。但对长作业非常不利。

**3，优先级调度算法（PSA）**

**4，高响应比优先调度算法（HRRN）**

![20190609001240510.png][]  
优点：既照顾短作业、又考虑作业到达先后，并且还兼顾到长作业。  
缺点：每次要进行调度之前，都需要先做响应比的计算，显然会增加系统开销。

**5，时间片轮转（RR）算法**  
让就绪队列上的每个进程每次仅运行一个时间片。  
时间片小会增加系统的开销，若时间片选择得太长，RR算法退化为FCFS算法，无法满足短作业和交互式用户的需求。

**6，**★**多级反馈队列（MLFQ）调度算法**

**时间片算法和优先级算法的结合**，针对不同进程使用不同的调度算法。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2R5d182NjY2NjY_size_16_color_FFFFFF_t_70][]

### **四、选择题** ###

**【1】**分时操作系统通常采用( A )调度算法来为用户服务。  
A．时间片轮转  
B．先来先服务  
C．短作业优先  
D．优先级

\[解析\] 分时系统由于需要同时满足多个用户的需要，因此把处理器时间轮流分配给多个用户作业使用，即采用时间片轮转调度算法。

**【2】**下列调度算法中，( B )调度算法是绝对可抢占的。  
A．先来先服务   
B．时间片轮转  
C．优先级   
D．短进程优先

\[解析\] 本题目考查各种调度算法的特点。  
A、先来先服务调度算法是不可抢占的。  
B、优先级调度算法和短进程优先调度算法可以分为可抢占和不可抢占两种，  
时间片轮转调度算法在时间片到达时将剥夺正在执行的进程的处理机，把处理机分配给就绪队列中的队首进程，即时间片轮转调度算法一定是可抢占的。因此应该选择B。

**【3】**进程调度算法采用固定时间片轮转调度算法，当时间片过大时，就会使时间片轮转法算法转化为( B )调度算法。  
A．高响应比优先  
B．先来先服务  
C．短进程优先  
D．以上选项都不对

\[解析\] 时间片轮转调度算法在实际运行中也是按先后顺序使用时间片，  
当时间片过大时，我们可以认为其大于进程需要的运行时间，即转变为先来先服务调度算法。

**【4】**采用时间片轮转调度算法分配CPU时，当处于运行状态的进程用完一个时间片后，它的状态是( C )状态。  
  
A．阻塞  
B．运行  
C．就绪  
D．消亡

\[解析\] 处于运行状态的进程用完一个时间片后，它的状态会变为就绪状态等待下一次处理器调度。当进程执行完最后的语句并使用系统调用exit，请求操作系统删除它或出现一些异常情况时，进程才会终止。

**【5】**若每个作业只能建立一个进程，为了照顾短作业用户，应采用( B )；为了照顾紧急作业用户，应采用( E )；为了能实现人机交互，应采用( C )；而能使短作业、长作业和交互作业用户都满意，应采用( D )。  
  
A．FCFS调度算法  
B．短作业优先调度算法  
C．时间片轮转调度算法  
D．多级反馈队列调度算法  
E．剥夺式优先级调度算法

\[解析\] 照顾短作业用户，选择短作业优先调度算法；  
照顾紧急作业用户，即选择优先级高的作业优先调度，采用基于优先级的剥夺调度算法；  
实现人机交互，要保证每个作业都能在一定时间内轮到，采用时间片轮转法；  
使各种作业用户满意，要处理多级反馈，所以选择多级反馈队列调度算法。

**【6】**既考虑作业等待时间又考虑作业执行时间的调度算法是( A )。  
A．响应比高者优先   
B．短作业优先  
C．优先级调度   
D．先来先服务

\[解析\] 响应比=(等待时间+执行时间)/执行时间

**【7】**( D )优先级是在创建进程时确定的，确定之后在整个运行期间不再改变。  
  
A．先来先服务  
B．动态  
C．短作业  
D．静态

\[解析\] 优先级调度算法分静态和动态两种。静态优先级在进程创建时确定，之后不再改变。

**【8】**现有三个同时到达的作业J1，J2和J3，它们的执行时间分别是T1，T2和T3，且T1＜T2＜T3。系统按单道方式运行且采用短作业优先算法，则平均周转时间是( C )。  
A．T1+T2+T3  
B．(T1+T2+T3)/3  
C．(3T1+2T2+T3)/3  
D．(T1+2T2+3T3)/3

\[解析\] 按照短作业优先算法，执行顺序为J1、J2、J3，三个作业完成时间分别是T1、T1+T2、T1+T2+T3，所以平均周转时间是(T1+T1+T2+T1+T2+T3)/3。

**【9】**设有4个作业同时到达，每个作业的执行时间均为2h，它们在一台处理器上按单道式运行，则平均周转时间为( B )。  
  
A．1h   
B．5h   
C．2.5h   
D．8h

\[解析\] 4个作业，各执行时间分别是2h、4h、6h、8h，所以4个作业都完成的时间为2+4+6+8=20h。  
此时，平均周转时间=各个作业完成时间之和/作业个数=20/4=5小时。

**【10】**设有三个作业，其运行时间分别是2h、5h、3h，假定它们同时到达，并在同一台处理器上以单道方式运行，则平均周转时间最小的执行顺序是( D )。  
  
A．J1，J2，J3  
B．J3，J2，J1  
C．J2，J1，J3  
D．J1，J3，J2

\[解析\] 在同一台处理器以单道方式运行，要想获得最短的平均周转时间，用短作业优先调度算法会有较好的效果。

就本题目而言：  
A选项的平均周转时间=(2+7+10)/3h=19/3h；  
B选项的平均周转时间=(3+8+10)/3h=7h；  
C选项的平均周转时间=(5+7+10)/3h=22/3h；  
D选项的平均周转时间=(2+5+10)/3h=17/3h。

[20190609001240510.png]: /images/20220204/ba4ff35b0e29497c80899886412bec69.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2R5d182NjY2NjY_size_16_color_FFFFFF_t_70]: /images/20220204/2151d148f19241969cd1527f825e1cf7.png