9.处理机调度与死锁 原

一个批处理型的作业，从进入系统并驻留在外存的后备队列上开始，直至作业运行完毕，可能要经历的三级调度：

• 高级调度

又称作业调度、长程调度、接纳调度

作用：把外存上处于后备队列中的作业调入内存，并为它们创建进程、分配资源、排在就绪队列上，准备执行。

分时系统、实时系统，通常不需要作业调度。

• 中级调度

又称中程调度。

目的：提高内存利用率和系统吞吐率。

作用：使暂时不能运行的进程从内存调至外存，进入就绪驻外存状态或挂起状态。把外存上又具备运行条件的就绪进程，重新掉入内存，并修改为就绪状态，挂在就绪队列上。

又称对换。

• 低级调度

也称为进程调度、短程调度。

作用：决定就绪队列中的哪个进程应获得处理机，然后由分派程序执行把处理机分配给该进程的具体操作。

在OS中都必须配置。

进程调度的两种调度方式

• 非抢占方式
• 抢占方式

非抢占方式

一旦处理机分配给某进程后，便让该进程一直执行，直至该进程完成或阻塞时，才把处理机分配给其他进程。

非抢占方式引起进程调度的因素

（1） 进程执行完毕，或因发生某种事件而不能继续执行；

（2）执行中的进程因提出I/O请求而暂停执行

（3）在进程通信或同步过程中执行类某种原语操作，如P操作（WAIT操作）、BLOCK原语、WAKEUP原语等。

抢占方式

允许暂停某个正在执行的进程，将已分配给该进程的处理机重新分配给另一进程。

抢占原则

（1）优先权原则。优先权高的进程抢占处理机。

（2）短作业优先原则。短作业（进程）抢占当前较长作业（进程）的处理机。

（3）时间片原则。各进程按时间片运行，当一个时间片用完后重新调度。

调度队列模型

• 仅有进程调度的调度队列模型
• 有高级和低级调度的调度队列模型
• 同时有三级调度的调度队列模型

仅有进程调度的调度队列模型

• 通常，把就绪进程组织成FIFO队列，每当创建新进程时排在就绪队列的末尾，按时间片轮转方式进行。

进程在执行时，出现三种情况：

（1）任务在时间片内完成，进程便在释放处理机后进入完成状态。

（2）任务在时间片内未完成，OS便将该任务再放入就绪队列的末尾。

（3）在执行期间，进程因为某事件而被阻塞后，被OS放入阻塞队列。

有高级和低级调度的调度队列模型

高级调度是作业调度

与前一模型的差别：

（1）就绪队列的形式。批处理系统中最常用的是优先权队列。也可采用无序链表方式。

（2）设置多个阻塞队列。

有三级调度的调度队列模型

• 调出时，可使进程状态由内存就绪转变为外存就绪，由内存阻塞转变为外存阻塞。
• 在中级调度使外存就绪转变为内存就绪。

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

• 面向用户的准则

（1）周转时间短

（2）响应时间快

（3）截止时间的保证

（4）优先权准则

• 面向系统的准则

（1）系统吞吐量高

（2）处理机利用率好

（3）资源的平衡利用

周转时间

从作业被提交给系统开始，到作业完成为止的这段时间间隔称为作业周转时间。包括四部分时间：

• 在外存后备队列上等待调度的时间
• 进程在就绪队列上等待调度的时间
• 进程在CPU上执行的时间
• 进程等待i/O操作完成的时间

平均周转时间

对n个作业来讲，n个作业的周转时间累加求和，除以n的结果就是平均周转时间。

带权周转时间

W= T / Ts

T:作业的周转时间

Ts：系统为它提供服务的时间（真正运行时间，就是占用处理机的时间）

平均带权周转时间

就是n个W求和并除以n

例子

有如下三道作业。系统为它们服务的顺序是：1，2，3.求平均周转时间和平均带权周转时间。

解答：

平均周转时间：(2+2.9+3)/3=2.63h

平均带权周转时间：(1+2.9+12)/3=5.3h

响应时间

响应时间是从用户通过键盘提交一个请求开始直至系统首次产生响应为止的时间间隔。它包括三部分时间：

• 从键盘输入的请求信息传送到处理机的时间
• 处理机对请求信息进行处理的时间
• 将响应信息回送到终端显示器的时间

响应时间是分时系统中的重要原则。

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

对于严格的实时系统，其调度方式和调度算法必须能保证这一点。

吞吐量

• 吞吐量是指单位时间内系统所完成的作业数。
• 评价批处理系统性能的重要指标。
• 与作业的平均长度有关。对于大型作业，一般吞吐量约为每小时一道作业。对于中、小型作业，其吞吐量可达到数十道作业。

(adsbygoogle = window.adsbygoogle || []).push({});