操作系统：第3章进程调度与死锁3

《操作系统：第3章进程调度与死锁3》由会员分享，可在线阅读，更多相关《操作系统：第3章进程调度与死锁3（62页珍藏版）》请在装配图网上搜索。

1、第三章处理机调度与死锁 第三章处理机调度与死锁 3.1 处理机调度的层次处理机调度的层次3.2 调度队列模型和调度准则调度队列模型和调度准则3.3 调度算法调度算法 3.4 实时调度实时调度 3.5 产生死锁的原因和必要条件产生死锁的原因和必要条件3.6 预防死锁的方法预防死锁的方法3.7 死锁的检测与解除死锁的检测与解除 第三章处理机调度与死锁 3.4实实 时时 调调 度度 3.4.13.4.1实现实时调度的基本条件实现实时调度的基本条件1 1提供必要的信息提供必要的信息为了实现实时调度，系统应向调度程序提供有关任务的下述为了实现实时调度，系统应向调度程序提供有关任务的下述一些信息：一些信息

2、：1.1.就绪时间。这是该任务成为就绪状态的起始时间。就绪时间。这是该任务成为就绪状态的起始时间。2.开始截止时间和完成截止时间。对于典型的实时应用，只开始截止时间和完成截止时间。对于典型的实时应用，只须知道开始截止时间，或者知道完成截止时间。须知道开始截止时间，或者知道完成截止时间。3.处理时间。这是指一个任务从开始执行直至完成所需的时处理时间。这是指一个任务从开始执行直至完成所需的时间。在某些情况下，该时间也是系统提供的。间。在某些情况下，该时间也是系统提供的。4.资源要求。这是指任务执行时所需的一组资源。资源要求。这是指任务执行时所需的一组资源。5.优先级。优先级。第三章处理机调度与死锁

3、 2 2系统处理能力强系统处理能力强在实时系统中，通常都有着多个实时任务。若处理机的在实时系统中，通常都有着多个实时任务。若处理机的处理能力不够强，则有可能因处理机忙不过来而使某些实时处理能力不够强，则有可能因处理机忙不过来而使某些实时任务不能得到及时处理，从而导致发生难以预料的后果。假任务不能得到及时处理，从而导致发生难以预料的后果。假定系统中有定系统中有m个周期性的硬实时任务，它们的处理时间可表个周期性的硬实时任务，它们的处理时间可表示为示为Ci，周期时间表示为，周期时间表示为Pi，则在单处理机情况下，必须满，则在单处理机情况下，必须满足下面的限制条件足下面的限制条件,系统才是可调度的：系

4、统才是可调度的：11miiiPC第三章处理机调度与死锁 假如系统中有假如系统中有6 6个硬实时任务，它们的周期时间都是个硬实时任务，它们的周期时间都是 50 50 msms，而每次的处理时间为，而每次的处理时间为 10 ms10 ms，则不难算出，此时是不能，则不难算出，此时是不能满足上式的，因而系统是不可调度的。满足上式的，因而系统是不可调度的。解决的方法是提高系统的处理能力，其途径有二：解决的方法是提高系统的处理能力，其途径有二：其一仍是采用单处理机系统，但须增强其处理能力，以显著其一仍是采用单处理机系统，但须增强其处理能力，以显著地减少对每一个任务的处理时间；地减少对每一个任务的处理时间

5、；其二是采用多处理机系统。假定系统中的处理机数为其二是采用多处理机系统。假定系统中的处理机数为N，则，则应将上述的限制条件改为：应将上述的限制条件改为：NPCmiii1第三章处理机调度与死锁 3 3采用抢占式调度机制采用抢占式调度机制在含有硬实时任务的实时系统中，广泛采用抢占机制。在含有硬实时任务的实时系统中，广泛采用抢占机制。当一个优先权更高的任务到达时，允许将当前任务暂时挂起，当一个优先权更高的任务到达时，允许将当前任务暂时挂起，而令高优先权任务立即投入运行，这样便可满足该硬实时任而令高优先权任务立即投入运行，这样便可满足该硬实时任务对截止时间的要求。务对截止时间的要求。第三章处理机调度与

6、死锁 4 4具有快速切换机制具有快速切换机制为保证要求较高的硬实时任务能及时运行，在实时系统中为保证要求较高的硬实时任务能及时运行，在实时系统中还应具有快速切换机制，以保证能进行任务的快速切换。该机还应具有快速切换机制，以保证能进行任务的快速切换。该机制应具有如下两方面的能力：制应具有如下两方面的能力：(1)(1)对外部中断的快速响应能力。为使在紧迫的外部事件对外部中断的快速响应能力。为使在紧迫的外部事件请求中断时系统能及时响应，要求系统具有快速硬件中断机构，请求中断时系统能及时响应，要求系统具有快速硬件中断机构，还应使禁止中断的时间间隔尽量短，以免耽误时机还应使禁止中断的时间间隔尽量短，以免

7、耽误时机(其它紧迫其它紧迫任务任务)。(2)快速的任务分派能力。在完成任务调度后，便应进行快速的任务分派能力。在完成任务调度后，便应进行任务切换。为了提高分派程序进行任务切换时的速度，应使系任务切换。为了提高分派程序进行任务切换时的速度，应使系统中的每个运行功能单位适当地小，以减少任务切换的时间开统中的每个运行功能单位适当地小，以减少任务切换的时间开销。销。第三章处理机调度与死锁 3.4.23.4.2实时调度算法的分类实时调度算法的分类1 1非抢占式调度算法非抢占式调度算法1)1)非抢占式轮转调度算法非抢占式轮转调度算法该算法常用于工业生产的群控系统中，由一台计算机控制该算法常用于工业生产的群

8、控系统中，由一台计算机控制若干个相同的若干个相同的(或类似的或类似的)对象，为每一个被控对象建立一个实对象，为每一个被控对象建立一个实时任务，并将它们排成一个轮转队列。调度程序每次选择队列时任务，并将它们排成一个轮转队列。调度程序每次选择队列中的第一个任务投入运行。当该任务完成后，便把它挂在轮转中的第一个任务投入运行。当该任务完成后，便把它挂在轮转队列的末尾，等待下次调度运行，而调度程序再选择下一个队列的末尾，等待下次调度运行，而调度程序再选择下一个(队首队首)任务运行。这种调度算法可获得任务运行。这种调度算法可获得数秒至数十秒的响应时数秒至数十秒的响应时间，可用于要求不太严格的实时控制系统中

9、。间，可用于要求不太严格的实时控制系统中。第三章处理机调度与死锁 2)2)非抢占式优先调度算法非抢占式优先调度算法如果在实时系统中存在着要求较为严格如果在实时系统中存在着要求较为严格(响应时间为数百响应时间为数百毫秒毫秒)的任务，则可采用非抢占式优先调度算法为这些任务赋的任务，则可采用非抢占式优先调度算法为这些任务赋予较高的优先级。当这些实时任务到达时，把它们安排在就予较高的优先级。当这些实时任务到达时，把它们安排在就绪队列的队首，等待当前任务自我终止或运行完成后才能被绪队列的队首，等待当前任务自我终止或运行完成后才能被调度执行。这种调度算法在做了精心的处理后，有可能获得调度执行。这种调度算法

10、在做了精心的处理后，有可能获得仅为数秒至数百毫秒级的响应时间，因而仅为数秒至数百毫秒级的响应时间，因而可用于有一定要求可用于有一定要求的实时控制系统中。的实时控制系统中。第三章处理机调度与死锁 2 2抢占式调度算法抢占式调度算法在要求较严格的在要求较严格的(响应时间为数十毫秒以下响应时间为数十毫秒以下)的实时系统中，的实时系统中，应采用应采用抢占式优先权调度算法。抢占式优先权调度算法。可根据抢占发生时间的不同而可根据抢占发生时间的不同而进一步分成以下两种调度算法。进一步分成以下两种调度算法。1)1)基于时钟中断的抢占式优先权调度算法基于时钟中断的抢占式优先权调度算法在某实时任务到达后，如果该任

11、务的优先级高于当前任务在某实时任务到达后，如果该任务的优先级高于当前任务的优先级，这时并不立即抢占当前任务的处理机，而是的优先级，这时并不立即抢占当前任务的处理机，而是等到时等到时钟中断到来时，调度程序才剥夺当前任务的执行，钟中断到来时，调度程序才剥夺当前任务的执行，将处理机分将处理机分配给新到的高优先权任务。这种调度算法能获得较好的响应效配给新到的高优先权任务。这种调度算法能获得较好的响应效果，其果，其调度延迟可降为几十毫秒至几毫秒调度延迟可降为几十毫秒至几毫秒。因此，此算法可用。因此，此算法可用于大多数的实时系统中。于大多数的实时系统中。第三章处理机调度与死锁 2)立即抢占立即抢占(Imm

12、ediate Preemption)的优先权调度算法的优先权调度算法在这种调度策略中，要求操作系统具有快速响应外部事在这种调度策略中，要求操作系统具有快速响应外部事件中断的能力。一旦出现外部中断，只要当前任务未处于临件中断的能力。一旦出现外部中断，只要当前任务未处于临界区，便立即剥夺当前任务的执行，把处理机分配给请求中界区，便立即剥夺当前任务的执行，把处理机分配给请求中断的紧迫任务。这种算法能获得非常快的响应，可把调度延断的紧迫任务。这种算法能获得非常快的响应，可把调度延迟降低到迟降低到几毫秒至几毫秒至100100微秒，微秒，甚至更低。甚至更低。图图3-8中的中的(a)、(b)、(c)、(d)

13、分别示出了采用非抢占式轮分别示出了采用非抢占式轮转调度算法、非抢占式优先权调度算法、基于时钟中断抢占转调度算法、非抢占式优先权调度算法、基于时钟中断抢占的优先权调度算法和立即抢占的优先权调度算法四种情况的的优先权调度算法和立即抢占的优先权调度算法四种情况的调度时间。调度时间。第三章处理机调度与死锁 图图3-8 实时进程调度实时进程调度(a)非抢占式轮转调度当前进程实时进程实时进程请求调度实时进程抢占当前进程并立即执行(d)立即抢占的优先权调度调度时间进程 1进程 2实时进程要求调度进程 n实时进程调度实时进程运行(b)非抢占式优先权调度当前进程实时进程实时进程请求调度当前进程运行完成调度时间当

14、前进程实时进程请求调度时钟中断到来时调度时间(c)基于时钟中断抢占的优先权抢占调度调度时间实时进程第三章处理机调度与死锁 3.5产生死锁的原因和必要条件产生死锁的原因和必要条件 3.5.13.5.1产生死锁的原因产生死锁的原因产生死锁的原因可归结为如下两点：产生死锁的原因可归结为如下两点：(1)(1)竞争资源。当系统中供多个进程共享的资源如打印竞争资源。当系统中供多个进程共享的资源如打印机、公用队列等，其数目不足以满足诸进程的需要时，会引机、公用队列等，其数目不足以满足诸进程的需要时，会引起诸进程对资源的竞争而产生死锁。起诸进程对资源的竞争而产生死锁。(2)进程间推进顺序非法。进程在运行过程中

15、，请求和释进程间推进顺序非法。进程在运行过程中，请求和释放资源的顺序不当，也同样会导致产生进程死锁。放资源的顺序不当，也同样会导致产生进程死锁。(3)wait操作顺序不当操作顺序不当 第三章处理机调度与死锁 1 1竞争资源引起进程死锁竞争资源引起进程死锁1)1)可剥夺和非剥夺性资源可剥夺和非剥夺性资源可把系统中的资源分成两类，一类是可剥夺性资源，是可把系统中的资源分成两类，一类是可剥夺性资源，是指某进程在获得这类资源后，该资源可以再被其他进程或系指某进程在获得这类资源后，该资源可以再被其他进程或系统剥夺。例如，优先权高的进程可以剥夺优先权低的进程的统剥夺。例如，优先权高的进程可以剥夺优先权低的

16、进程的处理机。又如，内存区可由存储器管理程序把一个进程从一处理机。又如，内存区可由存储器管理程序把一个进程从一个存储区移到另一个存储区，此即剥夺了该进程原来占有的个存储区移到另一个存储区，此即剥夺了该进程原来占有的存储区。甚至可将一个进程从内存调出到外存上。可见，存储区。甚至可将一个进程从内存调出到外存上。可见，CPU和主存均属于可剥夺性资源。和主存均属于可剥夺性资源。另一类资源是另一类资源是不可剥夺性不可剥夺性资源资源，当系统把这类资源分配给某进程后，再不能强行收回，当系统把这类资源分配给某进程后，再不能强行收回，只能在进程用完后自行释放，如只能在进程用完后自行释放，如磁带机、打印机磁带机、

17、打印机等。等。第三章处理机调度与死锁 2)竞争非剥夺性资源竞争非剥夺性资源在系统中所配置的非剥夺性资源，由于它们的数量不能满足在系统中所配置的非剥夺性资源，由于它们的数量不能满足诸进程运行的需要，会使进程在运行过程中，因争夺诸进程运行的需要，会使进程在运行过程中，因争夺非剥夺性资非剥夺性资源源而陷入僵局。而陷入僵局。R1R2P1P2图图3-13I/O设备共享时的死锁情况设备共享时的死锁情况 第三章处理机调度与死锁 2进程推进顺序不当引起死锁 P1：P2：Request(R1)；Request(R2)；Request(R2)；Request(R1)；进程推进顺序非法：进程推进顺序非法：P1：Re

18、quest(R1)；P2：Request(R2)；P1：Request(R2)；P2：Request(R1)；第三章处理机调度与死锁 Producer process repeat produce an item in nextp;P(empty);P(mutex);.put nextp into buffer;.V(mutex);V(full);until false;P(mutex);P(empty);P操作顺序不当引起死锁操作顺序不当引起死锁 Consumer process repeat P(full)P(mutex);remove an item from buffer to nex

19、tc V(mutex);V(empty);consume the item in nextc until false;P(mutex);P(full);第三章处理机调度与死锁 3.5.23.5.2产生死锁的必要条件产生死锁的必要条件虽然进程在运行过程中可能发生死锁，但死锁的发生也必虽然进程在运行过程中可能发生死锁，但死锁的发生也必须具备一定的条件须具备一定的条件,四个必要条件四个必要条件:(1)(1)互斥条件：指进程对所分配到的资源进行排它性使用，互斥条件：指进程对所分配到的资源进行排它性使用，即在一段时间内某资源只由一个进程占用。如果此时还有其它即在一段时间内某资源只由一个进程占用。如果此时

20、还有其它进程请求该资源，则请求者只能等待，直至占有该资源的进程进程请求该资源，则请求者只能等待，直至占有该资源的进程用毕释放。用毕释放。(2)请求和保持条件：指进程已经保持了至少一个资源，请求和保持条件：指进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又已被其它进程占有，此但又提出了新的资源请求，而该资源又已被其它进程占有，此时请求进程阻塞，但又对自己已获得的其它资源保持不放。时请求进程阻塞，但又对自己已获得的其它资源保持不放。第三章处理机调度与死锁(3)不剥夺条件：指进程已获得的资源，在未使用完之前，不剥夺条件：指进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时由自

21、己释放。不能被剥夺，只能在使用完时由自己释放。(4)环路等待条件：指在发生死锁时，必然存在一个进环路等待条件：指在发生死锁时，必然存在一个进程程资源的环形链，即进程集合资源的环形链，即进程集合P0，P1，P2，Pn中的中的P0正在等待一个正在等待一个P1占用的资源；占用的资源；P1正在等待正在等待P2占用的资占用的资源，源，Pn正在等待已被正在等待已被P0占用的资源。占用的资源。第三章处理机调度与死锁 3.5.3处理死锁的基本方法处理死锁的基本方法执行前执行前开始执行开始执行发生死锁发生死锁死锁解除死锁解除死锁预防死锁预防死锁避免死锁避免死锁检测死锁检测解除死锁解除死锁第三章处理机调度与死锁(

22、1)预防死锁。这是一种较简单和直观的事先预防的方预防死锁。这是一种较简单和直观的事先预防的方法。该方法是通过设置某些限制条件，去破坏产生死锁的四法。该方法是通过设置某些限制条件，去破坏产生死锁的四个必要条件中的一个或几个条件，来预防发生死锁。预防死个必要条件中的一个或几个条件，来预防发生死锁。预防死锁是一种较易实现的方法，已被广泛使用。但由于所施加的锁是一种较易实现的方法，已被广泛使用。但由于所施加的限制条件往往太严格，因而可能会导致系统资源利用率和系限制条件往往太严格，因而可能会导致系统资源利用率和系统吞吐量降低。统吞吐量降低。(2)避免死锁。该方法同样是属于事先预防的策略，但它避免死锁。该

23、方法同样是属于事先预防的策略，但它并不须事先采取各种限制措施去破坏产生死锁的四个必要条并不须事先采取各种限制措施去破坏产生死锁的四个必要条件，而是在资源的动态分配过程中，用某种方法去防止系统件，而是在资源的动态分配过程中，用某种方法去防止系统进入不安全状态，从而避免发生死锁。这种方法只需事先施进入不安全状态，从而避免发生死锁。这种方法只需事先施加较弱的限制条件，便可获得较高的资源利用率及系统吞吐加较弱的限制条件，便可获得较高的资源利用率及系统吞吐量，但在实现上有一定的难度。量，但在实现上有一定的难度。第三章处理机调度与死锁(3)检测死锁。这种方法并不须事先采取任何限制性措施，检测死锁。这种方法

24、并不须事先采取任何限制性措施，也不必检查系统是否已经进入不安全区，而是允许系统在运行也不必检查系统是否已经进入不安全区，而是允许系统在运行过程中发生死锁。但可通过系统所设置的检测机构，及时地检过程中发生死锁。但可通过系统所设置的检测机构，及时地检测出死锁的发生，并精确地确定与死锁有关的进程和资源；测出死锁的发生，并精确地确定与死锁有关的进程和资源；然后，采取适当措施，从系统中将已发生的死锁清除掉。然后，采取适当措施，从系统中将已发生的死锁清除掉。(4)解除死锁。这是与检测死锁相配套的一种措施。当检解除死锁。这是与检测死锁相配套的一种措施。当检测到系统中已发生死锁时，须将进程从死锁状态中解脱出来

25、。测到系统中已发生死锁时，须将进程从死锁状态中解脱出来。常用的实施方法是撤消或挂起一些进程，以便回收一些资源，常用的实施方法是撤消或挂起一些进程，以便回收一些资源，再将这些资源分配给已处于阻塞状态的进程，使之转为就绪状再将这些资源分配给已处于阻塞状态的进程，使之转为就绪状态，以继续运行。死锁的检测和解除措施有可能使系统获得较态，以继续运行。死锁的检测和解除措施有可能使系统获得较好的资源利用率和吞吐量，但在实现上难度也最大。好的资源利用率和吞吐量，但在实现上难度也最大。第三章处理机调度与死锁 3.6预防死锁的方法预防死锁的方法 3.6.13.6.1预防死锁预防死锁 死锁的预防一般是从破坏导致发生

26、死锁的必要条件着手，只要死锁的预防一般是从破坏导致发生死锁的必要条件着手，只要能使四个必要条件其中的任何一个不成立，就可防止死锁。能使四个必要条件其中的任何一个不成立，就可防止死锁。1 1摒弃摒弃“请求和保持请求和保持”条件。动态分配条件。动态分配静态分配静态分配系统规定所有进程在开始运行之前，都必须一次性地申请系统规定所有进程在开始运行之前，都必须一次性地申请其在整个运行过程所需的全部资源。此时，若系统有足够的资其在整个运行过程所需的全部资源。此时，若系统有足够的资源分配给某进程，便可把其需要的所有资源分配给该进程，这源分配给某进程，便可把其需要的所有资源分配给该进程，这样，该进程在整个运行

27、期间便不会再提出资源要求，从而摒弃样，该进程在整个运行期间便不会再提出资源要求，从而摒弃了请求条件。但在分配资源时，只要有一种资源不能满足某进了请求条件。但在分配资源时，只要有一种资源不能满足某进程的要求，即使其它所需的各资源都空闲，也不分配给该进程，程的要求，即使其它所需的各资源都空闲，也不分配给该进程，而让该进程等待。由于在该进程的等待期间，它并未占有任何而让该进程等待。由于在该进程的等待期间，它并未占有任何资源，因而也摒弃了保持条件，从而可以避免发生死锁。资源，因而也摒弃了保持条件，从而可以避免发生死锁。第三章处理机调度与死锁 这种预防死锁的方法其优点是简单、易于实现且很安全。这种预防死

28、锁的方法其优点是简单、易于实现且很安全。但其但其缺点缺点却也极其明显：却也极其明显：1.1.首先表现为资源被严重浪费，因为一个进程是一次性地获首先表现为资源被严重浪费，因为一个进程是一次性地获得其整个运行过程所需的全部资源的，且独占资源，其中得其整个运行过程所需的全部资源的，且独占资源，其中可能有些资源很少使用，甚至在整个运行期间都未使用，可能有些资源很少使用，甚至在整个运行期间都未使用，这就严重地恶化了系统资源的利用率；这就严重地恶化了系统资源的利用率；2.2.其次是使进程延迟运行，仅当进程在获得了其所需的全部其次是使进程延迟运行，仅当进程在获得了其所需的全部资源后，才能开始运行，但可能因有

29、些资源已长期被其它资源后，才能开始运行，但可能因有些资源已长期被其它进程占用而致使等待该资源的进程迟迟不能运行。进程占用而致使等待该资源的进程迟迟不能运行。第三章处理机调度与死锁 2 2摒弃摒弃“不剥夺不剥夺”条件条件在采用这种方法时系统规定，进程是逐个地提出对资源在采用这种方法时系统规定，进程是逐个地提出对资源的要求的。当一个已经保持了某些资源的进程，再提出新的的要求的。当一个已经保持了某些资源的进程，再提出新的资源请求而不能立即得到满足时，必须释放它已经保持了的资源请求而不能立即得到满足时，必须释放它已经保持了的所有资源，待以后需要时再重新申请。这意味着某一进程已所有资源，待以后需要时再重

30、新申请。这意味着某一进程已经占有的资源，在运行过程中会被暂时地释放掉，也可认为经占有的资源，在运行过程中会被暂时地释放掉，也可认为是被剥夺了，从而摒弃了是被剥夺了，从而摒弃了“不剥夺不剥夺”条件。条件。缺点：缺点：这种预防死锁的方法实现起来比较复杂且要付出这种预防死锁的方法实现起来比较复杂且要付出很大的代价。此外，这种策略还可能因为反复地申请和释放很大的代价。此外，这种策略还可能因为反复地申请和释放资源，致使进程的执行被无限地推迟，这不仅延长了进程的资源，致使进程的执行被无限地推迟，这不仅延长了进程的周转时间，而且也增加了系统开销，降低了系统吞吐量。周转时间，而且也增加了系统开销，降低了系统吞

31、吐量。第三章处理机调度与死锁 3 3摒弃摒弃“环路等待环路等待”条件：资源有序分配条件：资源有序分配这种方法中规定，系统将所有这种方法中规定，系统将所有资源按类型进行线性排队资源按类型进行线性排队，并赋予不同的序号并赋予不同的序号。例如，令输入机的序号为。例如，令输入机的序号为1，打印机的序，打印机的序号为号为2，磁带机为，磁带机为3，磁盘为，磁盘为4。所有进程对资源的请求必须严所有进程对资源的请求必须严格按照资源序号递增的次序提出，格按照资源序号递增的次序提出，这样，在所形成的资源分这样，在所形成的资源分配图中，不可能再出现环路，因而摒弃了配图中，不可能再出现环路，因而摒弃了“环路等待环路等

32、待”条件。条件。事实上，在采用这种策略时，总有一个进程占据了较高序号事实上，在采用这种策略时，总有一个进程占据了较高序号的资源，此后它继续申请的资源必然是空闲的，因而进程可的资源，此后它继续申请的资源必然是空闲的，因而进程可以一直向前推进。以一直向前推进。第三章处理机调度与死锁 系统资源进行统一编号。进程申请使用资源时，必须严格按照系统资源进行统一编号。进程申请使用资源时，必须严格按照编号的升序进行。编号的升序进行。进进 程程资资 源源ABC1、卡片输入机、卡片输入机 （3台）台）2、行式打印机、行式打印机 （2台）台）*3、卡片输入机、卡片输入机 （1台）台）*4、磁带机、磁带机（1台）台）

33、第三章处理机调度与死锁 这种预防死锁的策略与前两种策略比较，其资源利用率和系统这种预防死锁的策略与前两种策略比较，其资源利用率和系统吞吐量都有较明显的改善。但也存在下述严重问题：吞吐量都有较明显的改善。但也存在下述严重问题：首先是为系统中各类资源所分配首先是为系统中各类资源所分配(确定确定)的序号必须相对稳定，的序号必须相对稳定，这就限制了新类型设备的增加。这就限制了新类型设备的增加。其次，尽管在为资源的类型分配序号时，已经考虑到大多数作其次，尽管在为资源的类型分配序号时，已经考虑到大多数作业在实际使用这些资源时的顺序，但也经常会发生这种情况：即作业在实际使用这些资源时的顺序，但也经常会发生这

34、种情况：即作业业(进程进程)使用各类资源的顺序与系统规定的顺序不同，造成对资源使用各类资源的顺序与系统规定的顺序不同，造成对资源的浪费。例如，某进程先用磁带机，后用打印机，但按系统规定，的浪费。例如，某进程先用磁带机，后用打印机，但按系统规定，该进程应先申请打印机而后申请磁带机，致使先获得的打印机被长该进程应先申请打印机而后申请磁带机，致使先获得的打印机被长时间闲置。时间闲置。第三，为方便用户，系统对用户在编程时所施加的限制条件应第三，为方便用户，系统对用户在编程时所施加的限制条件应尽量少。然而这种按规定次序申请的方法，必然会限制用户简单、尽量少。然而这种按规定次序申请的方法，必然会限制用户简

35、单、自主地编程。自主地编程。第三章处理机调度与死锁 3.6.23.6.2系统安全状态系统安全状态1 1安全状态安全状态在在避免死锁的方法中，允许进程动态地申请资源，避免死锁的方法中，允许进程动态地申请资源，但系但系统在进行资源分配之前，应统在进行资源分配之前，应先计算此次资源分配的安全性先计算此次资源分配的安全性。若此次分配不会导致系统进入不安全状态，则将资源分配给若此次分配不会导致系统进入不安全状态，则将资源分配给进程；否则，令进程等待。进程；否则，令进程等待。第三章处理机调度与死锁 所谓安全状态，所谓安全状态，是指系统能按某种进程顺序是指系统能按某种进程顺序(P(P1 1，P P2 2，P

36、 Pn n)()(称称P P1 1，P P2 2，P Pn n序列为安全序列序列为安全序列)，来为每个进程，来为每个进程P Pi i分配其所需资源，直至满足每个进程对资源的最大需求，使分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。每个进程都可顺利地完成。如果系统无法找到这样一个安全如果系统无法找到这样一个安全序列，则称系统处于不安全状态。序列，则称系统处于不安全状态。虽然并非所有的不安全状态都必然会转为死锁状态，但虽然并非所有的不安全状态都必然会转为死锁状态，但当系统进入不安全状态后，便有可能进而进入死锁状态；当系统进入不安全状态后，便有可能进而进入死锁状态；反反

37、之，只要系统处于安全状态，系统便可避免进入死锁状态。之，只要系统处于安全状态，系统便可避免进入死锁状态。因此，因此，避免死锁的实质在于：系统在进行资源分配时，如何避免死锁的实质在于：系统在进行资源分配时，如何使系统不进入不安全状态。使系统不进入不安全状态。第三章处理机调度与死锁 2安全状态之例安全状态之例我们通过一个例子来说明安全性。我们通过一个例子来说明安全性。假定系统中有三个进程假定系统中有三个进程P1、P2和和P3，共有，共有12台磁带机。台磁带机。进程进程P1总共要求总共要求10台磁带机，台磁带机，P2和和P3分别要求分别要求4台和台和9台。台。假设在假设在T0时刻，进程时刻，进程P1

38、、P2和和P3已分别获得已分别获得5台、台、2台和台和2台磁台磁带机，尚有带机，尚有3台空闲未分配，如下表所示：台空闲未分配，如下表所示：第三章处理机调度与死锁 安全状态安全状态：安全序列：安全序列：P2 P3 进程号总共需求已分配还需剩余P110553P2422P3927进程号总共需求已分配还需剩余P110552P2422P3936不安全状态不安全状态 无无安全序列安全序列第三章处理机调度与死锁 3.6.33.6.3利用银行家算法避免死锁利用银行家算法避免死锁l 银行家算法银行家算法 一个银行家把他的固定资金借给若干客户，使这些客户一个银行家把他的固定资金借给若干客户，使这些客户在满足对资金

39、的要求后能完成其交易，把所借资金归还给银在满足对资金的要求后能完成其交易，把所借资金归还给银行家。假定客户分成若干次进行借款，每个客户预先说明自行家。假定客户分成若干次进行借款，每个客户预先说明自己所要求的最大资金量，并每次提出部分资金量申请和获得己所要求的最大资金量，并每次提出部分资金量申请和获得分配。如果银行家满足了客户对资金的最大需求量，则该客分配。如果银行家满足了客户对资金的最大需求量，则该客户在资金运作后，应在有限时间内将资金全部归还银行家。户在资金运作后，应在有限时间内将资金全部归还银行家。具体过程如下：具体过程如下：顾客的借款操作依次顺序进行，直到全部操作完成；顾客的借款操作依次

40、顺序进行，直到全部操作完成；银行家对顾客的借款操作进行判断，确定其银行家对顾客的借款操作进行判断，确定其安全性安全性（能否支持顾客借款，直到全部归还）；（能否支持顾客借款，直到全部归还）；如果是安全的，则借款给顾客，否则暂不借款。如果是安全的，则借款给顾客，否则暂不借款。第三章处理机调度与死锁 银行家算法例银行家算法例 假定银行可以分期贷款假定银行可以分期贷款10法郎给顾客，法郎给顾客，P,Q,R 顾客顾客 目前已贷法郎目前已贷法郎 所需最大法郎所需最大法郎 P 9 Q 5 R 3 522当前还剩几个？当当前还剩几个？当P申请一个法郎时，银行能满足他的要求吗？申请一个法郎时，银行能满足他的要求

41、吗？R申请一个呢？申请一个呢？第三章处理机调度与死锁 1 1银行家算法中的数据结构银行家算法中的数据结构(1)(1)可利用资源向量可利用资源向量AvailableAvailable。这是一个含有这是一个含有m m个元素个元素的数组，其中的每一个元素代表一类可利用的资源数目，其的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值初始值是系统中所配置的该类全部可用资源的数目，其数值随 该 类 资 源 的 分 配 和 回 收 而 动 态 地 改 变。如 果随 该 类 资 源 的 分 配 和 回 收 而 动 态 地 改 变。如 果Availablej

42、=KAvailablej=K，则表示系统中现有，则表示系统中现有R jR j类资源类资源K K个。个。(2)(2)最大需求矩阵最大需求矩阵MaxMax。这是一个这是一个n nm m的矩阵，它定义了的矩阵，它定义了系统中系统中n n个进程中的每一个进程对个进程中的每一个进程对m m类资源的最大需求。如果类资源的最大需求。如果Maxi,j=KMaxi,j=K，则表示进程，则表示进程i i需要需要RjRj类资源的最大数目为类资源的最大数目为K。第三章处理机调度与死锁(3)分配矩阵分配矩阵Allocation。这也是一个这也是一个nm的矩阵，它定的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资

43、源数。如义了系统中每一类资源当前已分配给每一进程的资源数。如果果Allocationi,j=K，则表示进程，则表示进程i当前已分得当前已分得R j类资源的数类资源的数目为目为K。(4)需求矩阵需求矩阵Need。这也是一个这也是一个nm的矩阵，用以表示的矩阵，用以表示每一个进程尚需的各类资源数。如果每一个进程尚需的各类资源数。如果Needi,j=K，则表示进，则表示进程程i还需要还需要R j类资源类资源K个，个，方能完成其任务。方能完成其任务。上述三个矩阵间存在下述关系：上述三个矩阵间存在下述关系：Needi,j=Maxi,j-Allocationi,j 第三章处理机调度与死锁 2银行家算法银行

44、家算法设设Request i是进程是进程Pi的请求向量，如果的请求向量，如果Request ij=K，表示进程表示进程P i需要需要K个个R j类型的资源。当类型的资源。当P i发出资源请求后，发出资源请求后，系统按下述步骤进行检查：系统按下述步骤进行检查：(1)如果如果Request ijNeedi,j，便转向步骤，便转向步骤(2)；否则认；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。为出错，因为它所需要的资源数已超过它所宣布的最大值。(2)如果如果RequestijAvailablej，便转向步骤，便转向步骤(3)；否则，；否则，表示尚无足够资源，表示尚无足够资源，Pi须须等

45、待。等待。第三章处理机调度与死锁(3)系统试探着把资源分配给进程系统试探着把资源分配给进程P i，并修改下面数据结，并修改下面数据结构中的数值：构中的数值：Availablej:=Availablej-Request ij；Allocationi,j:=Allocationi,j+Request ij；Needi,j:=Needi,j-Request ij；(4)系统执行安全性算法，检查此次资源分配后系统是否系统执行安全性算法，检查此次资源分配后系统是否处于安全状态。若安全，才正式将资源分配给进程处于安全状态。若安全，才正式将资源分配给进程Pi，以完，以完成本次分配；否则，将本次的试探分配作废

46、，恢复原来的资成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程源分配状态，让进程Pi等待。等待。第三章处理机调度与死锁 3 3安全性算法安全性算法系统所执行的安全性算法可描述如下：系统所执行的安全性算法可描述如下：(1)(1)设置两个向量：设置两个向量：工作向量工作向量WorkWork，它表示系统可提供给进程继续运行，它表示系统可提供给进程继续运行所需的所需的各类资源数目，各类资源数目，它含有它含有m m个元素，在执行安全算法开个元素，在执行安全算法开始时，始时，Work:=AvailableWork:=Available。进程完成向量进程完成向量Finish，它表示系统

47、是否有足够的资源，它表示系统是否有足够的资源分配给进程，使之运行完成。开始时分配给进程，使之运行完成。开始时Finishi:=false；当有；当有足够资源分配给进程时，再令足够资源分配给进程时，再令Finishi:=true。第三章处理机调度与死锁 (2)(2)从进程集合中找到一个能满足下述条件的进程：从进程集合中找到一个能满足下述条件的进程：Finishi=falseFinishi=false；NeediWorkNeediWork；若找到，执行步骤若找到，执行步骤(3)(3)，否则，执行步骤，否则，执行步骤(4)(4)。(3)(3)当进程当进程PiPi获得资源后，可顺利执行，直至完成，并释

48、放出分获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：配给它的资源，故应执行：Work:=Work+AllocationiWork:=Work+Allocationi；Finishi:=trueFinishi:=true；go to step 2；(4)如果所有进程的如果所有进程的Finishi=true都满足，则表示系统处于安全都满足，则表示系统处于安全状态；否则，系统处于不安全状态。状态；否则，系统处于不安全状态。第三章处理机调度与死锁 4银行家算法之例银行家算法之例假定系统中有五个进程假定系统中有五个进程 P0，P1，P2，P3，P4和三类资和三类资源源A，B，C，各

49、种资源的数量分别为，各种资源的数量分别为10、5、7，在，在T0时刻时刻的资源分配情况如图的资源分配情况如图3-16所示。所示。第三章处理机调度与死锁 图图3-16 T0时刻的资源分配表时刻的资源分配表 ABCABC资源的数量分别为资源的数量分别为10、5、7，第三章处理机调度与死锁(1)T0时刻的安全性：利用安全性算法对时刻的安全性：利用安全性算法对T0时刻的资源分时刻的资源分配情况进行分析配情况进行分析(见图见图 3-17所示所示)可知，在可知，在T0时刻存在着一个安时刻存在着一个安全序列全序列P1，P3，P4，P2，P0，故系统是安全的。，故系统是安全的。图3-17T0时刻的安全序列 第

50、三章处理机调度与死锁(2)P1请求资源：请求资源：P1发出请求向量发出请求向量Request1(1，0，2)，系，系统按银行家算法进行检查：统按银行家算法进行检查：Request1(1，0，2)Need1(1，2，2)Request1(1，0，2)Available1(3，3，2)系统先假定可为系统先假定可为P1分配资源，并修改分配资源，并修改Available，Allocation1和和Need1向量，向量，由此形成的资源变化情况如图由此形成的资源变化情况如图3-16中的圆括号所示。中的圆括号所示。第三章处理机调度与死锁 再利用安全性算法检查此时系统是否安全。如图再利用安全性算法检查此时系统

51、是否安全。如图3-18所示。所示。图图3-18P1申请资源时的安全性检查申请资源时的安全性检查 第三章处理机调度与死锁(3)P4请求资源：请求资源：P4发出请求向量发出请求向量Request4(3，3，0)，系，系统按银行家算法进行检查（统按银行家算法进行检查（图图3-16，P1分配后）分配后）：Request4(3，3，0)Need4(4，3，1)；Request4(3，3，0)Available(2，3，0)，让让P4等待。等待。(4)P0请求资源：请求资源：P0发出请求向量发出请求向量Requst0(0，2，0)，系，系统按银行家算法进行检查：统按银行家算法进行检查：Request0(0

52、，2，0)Need0(7，4，3)；Request0(0，2，0)Available(2，3，0)；系统暂时先假定可为系统暂时先假定可为P0分配资源，并修改有关数据，分配资源，并修改有关数据，如图如图3-19所示。所示。第三章处理机调度与死锁 图图3-19为为P0分配资源后的有关资源数据分配资源后的有关资源数据(5)(5)进行安全性检查：可用资源进行安全性检查：可用资源Available(2Available(2，1 1，0)0)已不能满足任已不能满足任何进程的需要，故系统进入不安全状态，此时系统不分配资源。何进程的需要，故系统进入不安全状态，此时系统不分配资源。第三章处理机调度与死锁 3.7

53、死锁的检测与解除死锁的检测与解除 3.7.1死锁的检测死锁的检测 允许死锁发生允许死锁发生 保存有关资源的请求和分配信息；提供检测算法保存有关资源的请求和分配信息；提供检测算法 检测时机检测时机 太频繁：系统效率低。太频繁：系统效率低。选择时机：当选择时机：当CPU利用率低于某一值时。利用率低于某一值时。第三章处理机调度与死锁 1资源分配图资源分配图(Resource Allocation Graph)系统死锁可利用资源分配图来描述。该图是由一组结点系统死锁可利用资源分配图来描述。该图是由一组结点N和一组边和一组边E所组成的一个对偶所组成的一个对偶G=(N1E)，它具有下述形式的，它具有下述形

54、式的定义和限制：定义和限制：(1)把把N分为两个互斥的子集分为两个互斥的子集，即一组进程结点，即一组进程结点P=p1，p2，pn和一组资源结点和一组资源结点R=r1，r2，rn，N=PR。在图在图3-20所示的例子中，所示的例子中，P=p1，p2，R=r1，r2，N=r1，r2p1，p2。第三章处理机调度与死锁(2)凡属于凡属于E中的一个边中的一个边eE，都连接着，都连接着P中的一个结点和中的一个结点和R中的一个结点，中的一个结点，e=pi，rj是资源请求边，由进程是资源请求边，由进程pi指向资源指向资源rj，它表示进程，它表示进程pi请求一个单位的请求一个单位的rj资源。资源。e=rj，pi

55、是资源分是资源分配边，由资源配边，由资源rj指向进程指向进程pi，它表示把一个单位的资源，它表示把一个单位的资源rj分配分配给进程给进程pi。图。图3-13中示出了两个请求边和两个分配边，即中示出了两个请求边和两个分配边，即E=(p1，r2)，(r2，p2)，(p2，r1)，(r1，p1)。我们用圆圈代表一个进程，用方框代表一类资源。由于一我们用圆圈代表一个进程，用方框代表一类资源。由于一种类型的资源可能有多个，我们用方框中的一个点代表一类资种类型的资源可能有多个，我们用方框中的一个点代表一类资源中的一个资源。此时，请求边是由进程指向方框中的源中的一个资源。此时，请求边是由进程指向方框中的rj

56、，而，而分配边则应始于方框中的一个点。图分配边则应始于方框中的一个点。图3-20示出了一个资源分配示出了一个资源分配图。图。第三章处理机调度与死锁 图图3-20每类资源有多个时的情况每类资源有多个时的情况 P1P2r1r2p1进程已经分得了两个进程已经分得了两个r1资源，资源，并又请求一个并又请求一个r2资源；资源；p2进程分进程分得了一个得了一个r1和一个和一个r2资源，并又资源，并又请求请求r1资源。资源。第三章处理机调度与死锁 2 2死锁定理死锁定理我们可以利用把资源分配图加以简化的方法我们可以利用把资源分配图加以简化的方法(图图3-21)3-21)，来检测当系统处于来检测当系统处于S

57、S状态时是否为死锁状态。状态时是否为死锁状态。S为死锁状态的充分条件是：当且仅当为死锁状态的充分条件是：当且仅当S状态的资源分配图是状态的资源分配图是不可完全简化的。该充分条件被称为死锁定理。不可完全简化的。该充分条件被称为死锁定理。简化方法如下：简化方法如下：(1)在资源分配图中，找出一个既不阻塞又非独立的进在资源分配图中，找出一个既不阻塞又非独立的进程结点程结点Pi。在顺利的情况下，。在顺利的情况下，Pi可获得所需资源而继续运行，可获得所需资源而继续运行，直至运行完毕，再释放其所占有的全部资源，这相当于消去直至运行完毕，再释放其所占有的全部资源，这相当于消去pi所求的请求边和分配边，使之成

58、为孤立的结点。所求的请求边和分配边，使之成为孤立的结点。第三章处理机调度与死锁 图图3-21资源分配图的简化资源分配图的简化(a)(b)P1(c)P1P2P1P2P2在图在图3-21(a)中，将中，将p1的两个分配边和一个请求边消去，便形的两个分配边和一个请求边消去，便形成图成图(b)所示的情况。所示的情况。第三章处理机调度与死锁(2)p(2)p1 1释放资源后，便可使释放资源后，便可使p2p2获得资源而继续运行，直获得资源而继续运行，直至至p p2 2完成后又释放出它所占有的全部资源，形成图完成后又释放出它所占有的全部资源，形成图(c)(c)所示的所示的情况。情况。(3)(3)在进行一系列的

59、简化后，若能消去图中所有的边，在进行一系列的简化后，若能消去图中所有的边，使所有的进程结点都成为孤立结点，则称该图是可完全简化使所有的进程结点都成为孤立结点，则称该图是可完全简化的；若不能通过任何过程使该图完全简化，则称该图是不可的；若不能通过任何过程使该图完全简化，则称该图是不可完全简化的。完全简化的。第三章处理机调度与死锁 3死锁检测中的数据结构死锁检测中的数据结构死锁检测中的数据结构类似于银行家算法中的数据结构：死锁检测中的数据结构类似于银行家算法中的数据结构：(1)可利用资源向量可利用资源向量Available，它表示了，它表示了m类资源中每一类资源中每一类资源的可用数目。类资源的可用

60、数目。(2)把不占用资源的进程把不占用资源的进程(向量向量Allocationi:=0)记入记入L表中表中.(3)从进程集合中找到一个从进程集合中找到一个RequestiWork的进程，做如的进程，做如下处理：下处理：将其资源分配图简化，释放出资源，增加工作向量将其资源分配图简化，释放出资源，增加工作向量Work:=Work+Allocation i。将它记入将它记入L表中。表中。第三章处理机调度与死锁(4)若不能把所有进程都记入若不能把所有进程都记入L表中，便表明系统状态表中，便表明系统状态S的的资源分配图是不可完全简化的资源分配图是不可完全简化的,系统状态将发生死锁。系统状态将发生死锁。W

61、ork:=Available；L:=Li|Allocation i=0Request i=0for all Li L dobeginfor all Request iWork dobeginWork:=Work+Allocation i；LiL；endenddeadlock:=(L=p1，p2，pn)；第三章处理机调度与死锁 3.7.23.7.2死锁的解除死锁的解除当发现有进程死锁时，便应立即把它们从死锁状态中解脱当发现有进程死锁时，便应立即把它们从死锁状态中解脱出来。常采用解除死锁的两种方法是：出来。常采用解除死锁的两种方法是：(1)(1)剥夺资源。从其它进程剥夺足够数量的资源给死锁进剥夺资

62、源。从其它进程剥夺足够数量的资源给死锁进程，以解除死锁状态。程，以解除死锁状态。(2)(2)撤消进程。最简单的撤消进程的方法是使全部死锁进撤消进程。最简单的撤消进程的方法是使全部死锁进程都夭折掉；稍微温和一点的方法是按照某种顺序逐个地撤消程都夭折掉；稍微温和一点的方法是按照某种顺序逐个地撤消进程，直至有足够的资源可用，使死锁状态消除为止。进程，直至有足够的资源可用，使死锁状态消除为止。在出现死锁时，可采用各种策略来撤消进程。例如，为解在出现死锁时，可采用各种策略来撤消进程。例如，为解除死锁状态所需撤消的进程数目最小；或者，撤消进程所付出除死锁状态所需撤消的进程数目最小；或者，撤消进程所付出的代

63、价最小等。的代价最小等。第三章处理机调度与死锁 小结小结 概念：周转时间、带权周转时间、死锁、死锁预防、死锁避概念：周转时间、带权周转时间、死锁、死锁预防、死锁避免、死锁检测、死锁恢复免、死锁检测、死锁恢复 三种调度类型的比较三种调度类型的比较 调度时机、切换与过程调度时机、切换与过程 调度方式、调度的基本准则调度方式、调度的基本准则 调度算法（调度算法（先来先服务调度算法；短作业（短任务、短进程、先来先服务调度算法；短作业（短任务、短进程、短线程）优先调度算法；时间片轮转调度算法；优先级调度短线程）优先调度算法；时间片轮转调度算法；优先级调度算法；高响应比优先调度算法；多级反馈队列调度算法。

64、）算法；高响应比优先调度算法；多级反馈队列调度算法。）产生死锁的原因、四个必要条件。产生死锁的原因、四个必要条件。进程资源图、银行家算法。进程资源图、银行家算法。死锁定理死锁定理第三章处理机调度与死锁 调度算法小结调度算法小结 FCFS 适应：作业，进程（线程）适应：作业，进程（线程）特点：实现简单，开销小，有利于长作业，适合批处理系，特点：实现简单，开销小，有利于长作业，适合批处理系，平均周转时间长平均周转时间长 SJF 特点：实现复杂，开销大，有利于短作业，适合批处理特点：实现复杂，开销大，有利于短作业，适合批处理系统，平均周转时间短，有饥饿现象。系统，平均周转时间短，有饥饿现象。适应：作

65、业，进程（线程）适应：作业，进程（线程）HRN(Highest Response-ratio Next,最高响应比优先）最高响应比优先）响应比响应比RR=（等待时间（等待时间+估计运行时间）估计运行时间）/估计运行时间估计运行时间 适应：作业，进程（线程）适应：作业，进程（线程）特点：实现复杂，开销大，公平，适合批处理系统特点：实现复杂，开销大，公平，适合批处理系统平均周转时间较短平均周转时间较短第三章处理机调度与死锁 Priority 适应：作业，进程（线程）适应：作业，进程（线程）特点：实现复杂特点：实现复杂，开销大，有利于紧迫作业，开销大，有利于紧迫作业，适合实适合实 时系统时系统l M

66、LQ&MLFQ 适应：进程（线程适应：进程（线程)特点：实现特点：实现复杂复杂，开销大，响应时间较短，区分进程性质，开销大，响应时间较短，区分进程性质，适合分时系统和通用系统。适合分时系统和通用系统。RR 适应：进程（线程适应：进程（线程)特点：实现特点：实现简单简单，开销大，响应时间短，不区分进程的性质，开销大，响应时间短，不区分进程的性质 适合分时系统适合分时系统第三章处理机调度与死锁 1.假定某多道程序系统有供用户使用的主存空间假定某多道程序系统有供用户使用的主存空间100k,磁带机磁带机2台台,打印机打印机1台台,系统采系统采用可变式分区管理主存用可变式分区管理主存,优先分配内存的低地址部分优先分配内存的低地址部分,且作业在内存中不能移动且作业在内存中不能移动.设设备采用静态分配技术备采用静态分配技术.主存中的作业平分主存中的作业平分cpu的时间的时间.作业采用先来先服务调度算作业采用先来先服务调度算法法.I/O操作的时间忽略不计操作的时间忽略不计.现有如下一组作业序列现有如下一组作业序列:作用号作用号 提交时间提交时间 运行时间运行时间(分分)主存量主存量 磁带机磁带机 打印