《精品课件教案ppt chapter3 处理机调度与死锁》由会员分享，可在线阅读，更多相关《精品课件教案ppt chapter3 处理机调度与死锁（90页珍藏版）》请在金锄头文库上搜索。
1、Chapter3 处理机调度与死锁,3.1 处理机调度的基本概念3.2 调度算法3.3 实时调度3.4 产生死锁的原因和必要条件3.5 预防死锁的方法3.6 死锁的监测与解除,3.1 处理机调度的基本概念,在多道程序系统中，一个作业被提交后，必须经过处理机调度后，方能因获得处理机而执行。 对于批量型作业而言，通常需要经历作业调度（高级调度）和进程调度（低级调度）两个过程后，方能获得处理机。 对于终端型作业，则通常只须经过进程调度。在较完善的操作系统中，往往还设置了中级调度。对于上述的每一级调度，又都可采用不同的调度方式和调度算法。本节主要是对处理机调度的基本概念做较详细的阐述。,3.1.1 高
2、级、中级和低级调度,高级调度又称为作业调度或长程调度(Long-Term scheduling),用于决定把外存上处于后备队列中的哪些作业调入内存，并为它们创建进程、分配必要的资源，然后，再将新创建的进程排在就绪队列上，准备执行。在批处理系统中，作业进入系统后，是先驻留在外存上的，因此需要有作业调度的过程，以便将它们分批地装入内存。 在分时系统和实时系统中，通常不需要作业调度。,高级调度(续),高级调度(续)在每次执行作业调度时，都须做出以下两个决定。 接纳多少个作业作业调度每次要接纳多少个作业进入内存，取决于多道程序度。即允许多少个作业同时在内存中运行。 数目太多时，可能会影响到系统的服务质
3、量，比如，使周转时间太长。 数量太少时，又会导致系统的资源利用率和系统吞吐量太低， 接纳哪些作业应将哪些作业从外存调入内存，将取决于所采用的调度算法。,低级调度,低级调度 用来决定就绪队列中的哪个进程应获得处理机，然后再由分派程序执行把处理机分配给该进程的具体操作。 进程调度方式是指当某一进程正在处理机上执行时，若有某个更为重要或紧迫的进程需要进行处理，即有优先权更高的进程进入就绪队列，此时应如何分配处理机。 进程调度是最基本的一种调度，在三种类型的OS中，都必须配置这级调度。,低级调度(续),低级调度（续） - 两种调度方式非抢占方式指当某一进程正在处理机上执行时，即使有某个更为重要或紧迫的
4、进程进入就绪队列，仍然让正在执行的进程继续执行，直到该进程完成或发生某种事件而进入完成或阻塞状态时，才把处理机分配给更为重要或紧迫的进程。非剥夺方式又称非抢占方式、不可剥夺方式。,低级调度(续2),引起进程调度的因素可归结为这样几个： 正在执行的进程执行完毕，或因发生某事件而不能再继续执行； 执行中的进程因提出I/O请求而暂停执行； 在进程通信或同步过程中执行了某种原语操作，如wait操作（P操作）、Block原语、Wakeup原语等。 特点：实现简单、系统开销小，适用于大多数的批处理系统环境。但它难以满足紧急任务的要求。,低级调度（续3）,低级调度 - 两种调度方式 抢占方式指当一个进程正在
5、处理机上执行时，若有某个更为重要或紧迫的进程需要使用处理机，则立即暂停正在执行的进程，将处理机分配给这个更重要或紧迫的进程。剥夺方式又称抢占方式、可剥夺方式。,低级调度（续4）,抢占的原则： 优先权原则当高优先权作业到达时，如果其优先权比正在执行进程的优先权高，便停止正在执行（当前）的进程，将处理机分配给优先权高的进程，使之执行。 短作业（进程）优先原则当新到达的作业（进程）比正在执行的作业（进程）明显短时，将暂停当前长作业（进程）的执行，将处理机分配给新到的短作业（进程），使之优先执行。 时间片原则各进程按时间片运行，当一个时间片用完后，便停止该进程的执行而重新进行调度。这种原则适用于分时系
6、统、大多数的实时系统，以及要求较高的批处理系统。,中级调度,中级调度引入中级调度的主要目的，是为了提高内存利用率和系统吞吐量。应使那些暂时不能运行的进程不再占用宝贵的内存资源，而将它们调至外存上去等待，把此时的进程状态称为就绪驻外存状态或挂起状态。当这些进程重又具备运行条件、且内存又稍有空闲时，由中级调度来决定把外存上的哪些进程，重新调入内存，并修改其状态为就绪状态，挂在就绪队列上等待进程调度。中级调度实际上是存储器管理中的对换功能。,三种调度总结,三种调度总结 进程调度的运行频率最高，分时系统中通常是10-100ms 进行一次进程调度，因而进程调度算法不能太复杂，以免占用太多的CPU时间。
7、作业调度往往是发生在一个（批）作业运行完毕，退出系统，而需要重新调入一个（批）作业进入内存时，故作业调度的周期较长，大约几分钟一次。因而也允许作业调度算法花费较多的时间。 中级调度的运行频率，基本上介于上述两种调度之间。,3.1.2 调度队列模型,仅有进程调度的调度队列模型在分时系统中，通常仅设置了进程调度，用户键入的命令和数据，都直接送入内存对于命令，是由OS为之建立一个进程。系统可以把处于就绪状态的进程组织成栈、树或一个无序链表，至于到底采用其中哪种形式，则与OS类型和所采用的调度算法有关。,具有高级和低级调度的调度队列模型,在批处理系统中，不仅需要进程调度，而且还需有作业调度，由后者按一
8、定的作业调度算法，从外存的后备队列中选择一批作业调入内存，并为它们建立进程，送入就绪队列，然后才由进程调度按照一定的进程调度算法，选择一个进程，把处理机分配给该进程。,就绪队列的形式。最常用的就绪队列形式是优先权队列。 设置多个阻塞队列。在大、中型系统中，通常都设置了若干个阻塞队列，每个队列对应于某一种进程阻塞事件。,同时具有三级调度的调度队列模型,当在OS中引入中级调度后，人们可把进程的就绪状态分为内存就绪（表示进程在内存中就绪）和外存就绪（进程在外存中就绪）。类似地，也可把阻塞状态进一步分成内存阻塞和外存阻塞两种状态。在调出操作的作用下，可使进程状态由内存就绪转变为外存就绪，由内存阻塞转变
9、为外存阻塞在中级调度的作用下，又可使外存就绪转变为内存就绪。,3.1.3 选择调度方式和调度算法的若干准则,面向用户的准则 - 为了满足用户需求。 周转周期短；（常用来评价批处理系统） 响应时间快；（常用来评价分时系统） 截止时间的保证；（常用来评价实时系统） 先后权准则；（批处理、实时、分时系统中都可采用）,选择调度方式和调度算法的若干准则（续）,面向系统的准则 - 为了满足系统需求。 系统吞吐量高；（常用来评价批处理系统） 处理机利用率高；（在大中型设备中常考虑） 各类资源平衡利用；（在大中型设备中常考虑）,3.2 调度算法,实质是一种资源分配，因而调度算法是指：根据系统的资源分配策略所规
10、定的资源分配算法。 对于不同的系统和系统目标，通常采用不同的调度算法，例如，在批处理系统中，为了照顾为数众多的短作业，应采用短作业优先的调度算法又如在分时系统中，为了保证系统具有合理的响应时间，应采用轮转法进行调度。 目前存在的多种调度算法中，有的算法适用于作业调度，有的算法适用于进程调度；但也有些调度算法既可用于作业调度，也可用于进程调度。,3.2.1 FCFS和短作业(进程)优先调度算法,先来先服务调度算法先来先服务(FCFS)调度算法是一种最简单的调度算法，该算法既可用于作业调度，也可用于进程调度。当在作业调度中采用该算法时，每次调度都是从后备作业队列中，选择一个或多个最先进入该队列的作
11、业，将它们调入内存，为它们分配资源、创建进程，然后放入就绪队列。在进程调度中采用FCFS算法时，则每次调度是从就绪队列中，选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。该进程一直运行到完成或发生某事件而阻塞后，才放弃处理机。,先来先服务调度算法之例一,Process 运行时间P1 24P2 3P3 3 假设进程到达的顺序为: P1 , P2 , P3 用Gantt图表示的调度顺序为:,等待时间： P1 = 0; P2 = 24; P3 = 27 平均等待时间: (0 + 24 + 27)/3 = 17,先来先服务调度算法之例一（续）,假设进程到达的顺序为: P2 , P3 , P
12、1 用Gantt图表示的调度顺序为:,等待时间： P1 = 6；P2 = 0；P3 = 3 平均等待时间: (6 + 0 + 3)/3 = 3 好于前一个例子 系统性能与作业长度和运行顺序密切相关,先来先服务调度算法之例二,先来先服务调度算法下表列出了A、B、C 、D四个作业分别到达系统的时间、要求服务的时间、开始执行的时间及各自的完成时间，并计算出各自的周转时间和带权周转时间。,从表上可以看出，其中短作业C的带权周转时间竞高达100,这是不能容忍的，而长作业D的带权周转时间仅为1.99。,先来先服务调度算法总结,先来先服务调度算法 FCFS调度算法有利于CPU繁忙型的作业，而不利于I/O繁忙
13、型的作业（进程）。 CPU繁忙型作业，是指该类作业需要大量的CPU时间进行计算，而很少请求I/O。通常的科学计算便属于CPU繁忙型作业。 I/O繁忙型作业，是指CPU进行处理时，需频繁地请求I/O。目前的大多数事务处理都属于I/O繁忙型作业。,短作业(进程)优先调度算法,指对短作业或短进程优先调度的算法,可以分别用于作业调度和进程调度。 短作业优先(SJF)的调度算法，是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。 短进程优先(SPF)调度算法，则是从就绪队列中选出一估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理
14、机时，再重新调度。,SJF(SPF)优先调度算法之例(非抢占式),Process Arrival Time 运行时间P1 0.0 7P2 2.0 4P3 4.0 1P4 5.0 4SJF (非抢占式),平均等待时间 (0 + 6 + 3 + 7)/4 = 4,SJF(SPF)优先调度算法之例(抢占式),Process Arrival Time 运行时间P1 0.0 7P2 2.0 4P3 4.0 1P4 5.0 4SJF (抢占式),平均等待时间 (9 + 1 + 0 +2)/4 = 3,SJ(P)F调度算法缺点,SJ(P)F调度算法也存在不容忽视的缺点： 该算法对长作业不利。 该算法完全未考
15、虑作业的紧迫程度，因而不能保证紧迫性作业（进程）会被及时处理。 由于作业（进程）的长短只是根据用户所提供的估计执行时间而定的，而用户又可能会有意或无意地缩短其作业的估计运行时间，致使该算法不一定能真正做到短作业优先调度。,3.2.2 高优先权优先调度算法,目 的为了照顾紧迫型作业，使之在进入系统后便获得优先处理，引入了最高优先权优先(FPF)调度算法。此算法常被用于批处理系统中，作为作业调度算法，也作为多种操作系统中的进程调度算法，还可用于实时系统中。Mapping of Win32 priorities to Windows 2000 priorities,Windows 2000支持32级
16、线程优先级,算法分类,用于作业调度时，系统将从后备队列中选择若干个优先权最高的作业，装入内存。 用于进程调度时，该算法是把处理机分配给就绪队列中优先权最高的进程。分为非抢占式优先权算法和抢占式优先权调度算法。,优先权的确定,优先权的确定 进程类型通常，系统进程(如接收进程、对换进程、磁盘I/O进程)的优先权高于一般用户进程的优先权。 进程对资源的需求如进程的估计执行时间及内存需要量的多少，对这些要求少的进程应赋予较高的优先 用户要求由用户进程的紧迫程度及用户所付费用的多少来确定优先权,优先权分类,静态优先权在创建进程时确定的，且在进程的整个运行期间保持不变。一般优先权利用某一范围内的一个整数来表示的，例如，07或0255中的某一整数。有的系统用“0”表示最高优先权，当数值愈大时，其优先权愈低，而有的系统恰恰相反。简单易行，系统开销小，但不够精确，很可能出现优先权低的作业（进程）长期没有被调度的情况。因此，仅在要求不高的系统中，才使用静态优先权.,
