中北大学第三章

《中北大学第三章》由会员分享，可在线阅读，更多相关《中北大学第三章（102页珍藏版）》请在金锄头文库上搜索。

1、计算机操作系统,课程主要内容,操作系统引论（1章） 进程管理（2-3章） 存储管理（4章） 设备管理（5章） 文件管理（6章） 操作系统接口（7章） 系统安全性（9章） *分布式操作系统,Process Management 进程管理,进程的基本概念与控制 进程的基本概念 进程控制 线程的基本概念 UNIX中进程的描述与控制 进程同步与通信 进程同步 经典进程的同步问题 管程机制 进程通信 UNIX中进程的同步与通信 处理机调度与死锁（第3章）,第3章 处理机调度与死锁,在多道程序环境下，一个作业从提交到执行，通常都要经历多级调度，如高级调度、低级调度、中级调度等。而系统的运行性能在很大程序上

2、取决于调度，因此调度便成为多道程序的关键。在多道程序环境下，由于多个进程的并发执行，改善了系统资源的利用率并提高了系统的处理能力，然而，多个进程的并发执行也带来了新的问题-死锁。,第3章 处理机调度与死锁,处理机调度的基本概念 调度算法 *实时调度 UNIX系统中进程的调度,产生死锁的原因和必要条件 预防死锁的方法 死锁的检测与解除 本章作业,3.1 处理机调度的基本概念,在多道程序环境下，一个作业从提交直到完成，往往要经历多级调度。但在不同操作系统中所采用的调度层次不完全相同。在有的系统中仅采用一级调度，而在另一些系统中则可能采用两级或三级调度，在执行调度时所采用的调度算法也可能不同。 调度

3、的层次 调度队列模型 选择调度方式和算法的若干准则,返回目录,一、调度的层次,如图所示。,一、调度的层次,一个作业从提交开始，往往要经历三级调度：高级调度、低级调度、中级调度。 1、高级调度（长程/作业/宏观调度）(1) 作业(Job)。作业是一个比程序更为广泛的概念，它不仅包含了通常的程序和数据，而且还应配有一份作业说明书，系统根据该说明书来对程序的运行进行控制。在批处理系统中，是以作业为基本单位从外存调入内存的。 (2) 作业步(Job Step)。通常，在作业运行期间，每个作业都必须经过若干个相对独立，又相互关联的顺序加工步骤才能得到结果，我们把其中的每一个加工步骤称为一个作业步，各作业

4、步之间存在着相互联系，往往是把上一个作业步的输出作为下一个作业步的输入。例如，一个典型的作业可分成三个作业步： “编译”作业步，通过执行编译程序对源程序进行编译，产生若干个目标程序段； “连结装配”作业步，将“编译”作业步所产生的若干个目标程序段装配成可执行的目标程序； “运行”作业步，将可执行的目标程序读入内存并控制其运行。 (3) 作业流。若干个作业进入系统后，被依次存放在外存上，这便形成了输入的作业流；在操作系统的控制下，逐个作业进行处理，于是便形成了处理作业流。,2作业控制块JCB(Job Control Block)为了管理和调度作业，在多道批处理系统中为每个作业设置了一个作业控制块

5、，如同进程控制块是进程在系统中存在的标志一样，它是作业在系统中存在的标志，其中保存了系统对作业进行管理和调度所需的全部信息。在JCB中所包含的内容因系统而异，通常应包含的内容有：作业标识、用户名称、用户帐户、作业类型(CPU 繁忙型、I/O 繁忙型、批量型、终端型)、作业状态、调度信息(优先级、作业已运行时间)、资源需求(预计运行时间、要求内存大小、要求I/O设备的类型和数量等)、进入系统时间、开始处理时间、作业完成时间、作业退出时间、资源使用情况等。,3作业调度作业调度的主要功能是根据作业控制块中的信息，审查系统能否满足用户作业的资源需求，以及按照一定的算法，从外存的后备队列中选取某些作业调

6、入内存，并为它们创建进程、分配必要的资源。然后再将新创建的进程插入就绪队列，准备执行。因此，有时也把作业调度称为接纳调度(Admission Scheduling)。,（1）从外存后备队列中选择作业进入就绪队列或挂起就绪. （2）在批处理系统中,大多配有作业调度,但在分时系统及实时系统中,一般不配置. （3）作业调度执行频率很低,通常为几分钟一次,甚至更久。,一、调度的层次-高级调度（长程/作业/宏观调度）,高级调度需解决的问题 （1）主要任务是从外存后备队列中选择多少作业进入就绪队列或挂起就绪，即允许多少作业同时在内存中运行，它控制着多道程序的“道或度” 。若作业太多，则可能会影响系统的服务

7、质量（如周转时间太长），若太少，又将导致系统资源利用率和吞吐量的下降。 因此，应根据系统的规模和运行速度来确定，同时要求I/O型进程与CPU型进程中和调度。 （2）应将哪些作业从外存调入内存，将取决于调度算法（先来先服务、短作业优先等）。,2、低级调度（短程/CPU/进程/微观调度）,（1）主要任务就是从就绪队列中选择一个进程来执行并分配处理机。 （2）是OS中最基本的调度。 （3）调度频率非常高，一般几十毫秒一次。 （4）常采用非抢占（非剥夺）方式和抢占（剥夺）方式两种。 （5）引起进程调度的因素： 进程正常终止或导常终止 正在执行的进程因某种原因而阻塞 在引入时间片的系统中，时间片用完。

8、在抢占调度方式中，就绪队列中某进程的优先权变得比当前正执行的进程高。,低级调度的主要功能如下： (1) 保存处理机的现场信息。在进程调度进行调度时，首先需要保存当前进程的处理机的现场信息，如程序计数器、多个通用寄存器中的内容等，将它们送入该进程的进程控制块(PCB)中的相应单元。(2) 按某种算法选取进程。低级调度程序按某种算法如优先数算法、轮转法等，从就绪队列中选取一个进程，把它的状态改为运行状态，并准备把处理机分配给它。 (3) 把处理器分配给进程。由分派程序(Dispatcher)把处理器分配给进程。此时需为选中的进程恢复处理机现场，即把选中进程的进程控制块内有关处理机现场的信息装入处理

9、器相应的各个寄存器中，把处理器的控制权交给该进程，让它从取出的断点处开始继续运行。,非抢占式进程调度、抢占式进程调度,非抢占方式：一旦把处理机分配给某进程后，便让该进程一直执行，直到该进程完成或因某事件而被阻塞，才再把处理机分配给其它进程，决不允许某进程抢占已分配出去的处理机。实现简单，系统开销小，常用于批处理系统；但不利于处理紧急任务，故实时、分时系统不宜采用。 抢占方式: 允许调度程序根据某种原则（时间片、优先权、短进程优先），停止正在执行的进程，而将处理机重新分配给另一进程。有利于处理紧急任务，故实时与分时系统中常采用。开销大。,3、中级调度（中程/交换调度）,在内存和外存对换区之间按照

10、给定的原则和策略选择进程对换，以解决内存紧张问题，从而提高内存的利用率和系统吞吐量，常用于分时系统或具有虚拟存储器的系统中。,返回本节,二、调度队列模型,在OS中的任何一种调度中，都将涉及到进程队列，由此形成了三种类型的调度队列模型。 仅有进程调度的调度队列模型 具有高级和低级调度的调度队列模型 同时具有三级调度的调度队列模型,返回本节,1、仅有进程调度的调度队列模型,进程调度,时间片完,返回,2、具有高级和低级调度的调度队列模型,时间片完,返回,3、同时具有三级调度的调度队列模型,时间片完,进程调度,CPU,进程完成,等待事件,作业调度,中程调度,返回,三、选择调度方式和算法的若干准则,在一

11、个操作系统的设计中，应如何选择调度方式和算法，在很大程度上取决于操作系统的类型及其目标，选择选择调度方式和算法的准则有： 面向用户的准则 周转时间短 响应时间快 截止时间的保证 优先权准则 面向系统的准则 系统吞吐量 处理机利用率好 各类资源平衡利用,最优准则 最大的CPU利用率 最大的吞吐量 最短的周转时间 最短的等待时间 最短的响应时间,返回本节,3.2.2 选择调度方式和调度算法的若干准则1面向用户的准则(1) 周转时间短。所谓周转时间，是指从作业被提交给系统开始，到作业完成为止的这段时间间隔(称为作业周转时间)。包括四部分时间：作业在外存后备队列上等待(作业)调度的时间，进程在就绪队列

12、上等待进程调度的时间，进程在CPU上执行的时间，以及进程等待I/O操作完成的时间。其中的后三项在一个作业的整个处理过程中可能会发生多次。,对每个用户而言，都希望自己作业的周转时间最短。但作为计算机系统的管理者，则总是希望能使平均周转时间最短，这不仅会有效地提高系统资源的利用率，而且还可使大多数用户都感到满意。可把平均周转时间描述为：,作业的周转时间T与系统为它提供服务的时间Ts之比，即W = T/Ts，称为带权周转时间，而平均带权周转时间则可表示为：,(2) 响应时间快。所谓响应时间，是从用户通过键盘提交一个请求开始，直至系统首次产生响应为止的时间，或者说，直到屏幕上显示出结果为止的一段时间间

13、隔。它包括三部分时间：从键盘输入的请求信息传送到处理机的时间，处理机对请求信息进行处理的时间，以及将所形成的响应信息回送到终端显示器的时间。,(3) 截止时间的保证。所谓截止时间，是指某任务必须开始执行的最迟时间，或必须完成的最迟时间。对于严格的实时系统，其调度方式和调度算法必须能保证这一点，否则将可能造成难以预料的后果。(4) 优先权准则。在批处理、分时和实时系统中选择调度算法时，都可遵循优先权准则，以便让某些紧急的作业能得到及时处理。,2面向系统的准则这是为了满足系统要求而应遵循的一些准则。其中，较重要的有以下几点：(1) 系统吞吐量高。吞吐量是指在单位时间内系统所完成的作业数，因而它与批

14、处理作业的平均长度具有密切关系。,(2) 处理机利用率好。对于大、中型多用户系统，由于CPU价格十分昂贵，致使处理机的利用率成为衡量系统性能的十分重要的指标；而调度方式和算法对处理机的利用率起着十分重要的作用。在实际系统中，CPU的利用率一般在40%(系统负荷较轻)到90%之间。,(3) 各类资源的平衡利用。在大、中型系统中，不仅要使处理机的利用率高，而且还应能有效地利用其它各类资源，如内存、外存和I/O设备等。选择适当的调度方式和算法可以保持系统中各类资源都处于忙碌状态。但对于微型机和某些实时系统而言，该准则并不重要。,3.2 调度算法,先来先服务调度算法 短作业/进程优先调度算法 时间片轮

15、转调度算法 优先权调度算法 高响应比优先调度算法 多级队列调度算法 多级反馈队列调度算法,返回目录,进程调度的核心问题就是采用什么样的算法将处理机分配给进程，常用的进程调度算法有：,一、先来先服务调度算法FCFS,基本思想: 按照进程进入就绪队列的先后次序来分配处理机。一般采用非剥夺的调度方式。,一、FCFS调度算法（续）,FCFS调度算法有利于CPU繁忙型的作业，而不利于I/O繁忙型的作业(进程)。CPU繁忙型作业是指该类作业需要大量的CPU时间进行计算，而很少请求I/O。通常的科学计算便属于CPU繁忙型作业。 I/O繁忙型作业是指CPU进行处理时需频繁地请求I/O。目前的大多数事务处理都属

16、于I/O繁忙型作业。,FCFS调度算法存在的问题,FCFS算法比较有利于长作业(进程)，而不利于短作业(进程)。从表面上，先来先服务于所有作业是公平的，即按照它们到来的先后次序进程服务。但若一个长作业先到达系统，就会使许多短作业等待很长的时间，从而引起许多短作业用户的不满。所以，现在操作系统中，已很少用该算法作为主要调度策略，尤其是在分时系统和实时系统中。但它常被结合在其它调度策略中使用。,返回,二、短作业/进程优先调度算法SJF/SPF,短作业优先调度算法（SJF） 用于作业调度 主要任务是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。 短进程优先调度算法（SPF） 用于进程调度 主要任务是从就绪队列中选出一估计运行时间最短的进程，将处理机分配给它。 可采用抢占（剥夺）或者非抢占（非剥夺）调度方式。,二、SJ(P)F和FCFS,SF(P)F短作业/进程优先调度的优缺点,优点：1）能有效降低作业的平均等待时间； 2）提高吞吐量；3）能有效缩短进程的周转时间； 缺点：1）对长作业不利；2）不考虑作业的紧迫程度；3）作业执行时间、剩余时间仅为估计*；故SJ(P)F算法虽然是优化的，但在CPU调度中很难实现。,