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

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

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

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

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

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

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

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

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

13、了采用非抢占式轮转调度算法、非抢占式优先权调度算法、基于时钟中断抢占转调度算法、非抢占式优先权调度算法、基于时钟中断抢占的优先权调度算法和立即抢占的优先权调度算法四种情况的的优先权调度算法和立即抢占的优先权调度算法四种情况的调度时间。调度时间。 第三章处理机调度与死锁 图图3-8 实时进程调度实时进程调度 第三章处理机调度与死锁 3.5产生死锁的原因和必要条件产生死锁的原因和必要条件 3.5.13.5.1产生死锁的原因产生死锁的原因产生死锁的原因可归结为如下两点：产生死锁的原因可归结为如下两点：(1) (1) 竞竞争争资资源源。当当系系统统中中供供多多个个进进程程共共享享的的资资源源如如打打印

14、印机机、公公用用队队列列等等，其其数数目目不不足足以以满满足足诸诸进进程程的的需需要要时时，会会引引起诸进程对资源的竞争而产生死锁。起诸进程对资源的竞争而产生死锁。(2) 进程间推进顺序非法。进程在运行过程中，请求和释进程间推进顺序非法。进程在运行过程中，请求和释放资源的顺序不当，也同样会导致产生进程死锁。放资源的顺序不当，也同样会导致产生进程死锁。 (3) wait操作顺序不当操作顺序不当 第三章处理机调度与死锁 1 1竞争资源引起进程死锁竞争资源引起进程死锁1) 1) 可剥夺和非剥夺性资源可剥夺和非剥夺性资源可把系统中的资源分成两类，一类是可剥夺性资源，是可把系统中的资源分成两类，一类是可

15、剥夺性资源，是指某进程在获得这类资源后，该资源可以再被其他进程或系指某进程在获得这类资源后，该资源可以再被其他进程或系统剥夺。例如，优先权高的进程可以剥夺优先权低的进程的统剥夺。例如，优先权高的进程可以剥夺优先权低的进程的处理机。又如，内存区可由存储器管理程序把一个进程从一处理机。又如，内存区可由存储器管理程序把一个进程从一个存储区移到另一个存储区，此即剥夺了该进程原来占有的个存储区移到另一个存储区，此即剥夺了该进程原来占有的存储区。甚至可将一个进程从内存调出到外存上。可见，存储区。甚至可将一个进程从内存调出到外存上。可见，CPU和主存均属于可剥夺性资源。和主存均属于可剥夺性资源。另一类资源是

16、另一类资源是不可剥夺性不可剥夺性资源资源，当系统把这类资源分配给某进程后，再不能强行收回，当系统把这类资源分配给某进程后，再不能强行收回，只能在进程用完后自行释放，如只能在进程用完后自行释放，如磁带机、打印机磁带机、打印机等。等。 第三章处理机调度与死锁 2) 竞争非剥夺性资源竞争非剥夺性资源在系统中所配置的非剥夺性资源，由于它们的数量不能满足在系统中所配置的非剥夺性资源，由于它们的数量不能满足诸进程运行的需要，会使进程在运行过程中，因争夺诸进程运行的需要，会使进程在运行过程中，因争夺非剥夺性资非剥夺性资源源而陷入僵局。而陷入僵局。图图3-13I/O设备共享时的死锁情况设备共享时的死锁情况 第

17、三章处理机调度与死锁 2进程推进顺序不当引起死锁 P1： P2： Request(R1)； Request(R2)； Request(R2)； Request(R1)；进程推进顺序非法：进程推进顺序非法： P1： Request(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);unti

18、l false; P(mutex);P(empty);P操作顺序不当引起死锁操作顺序不当引起死锁 Consumer process repeat P(full) P(mutex); remove an item from buffer to nextc V(mutex); V(empty); consume the item in nextc until false;P(mutex);P(full);第三章处理机调度与死锁 3.5.23.5.2产生死锁的必要条件产生死锁的必要条件虽虽然然进进程程在在运运行行过过程程中中可可能能发发生生死死锁锁，但但死死锁锁的的发发生生也也必必须具备一定的条件须

19、具备一定的条件, ,四个必要条件四个必要条件: :(1) (1) 互互斥斥条条件件：指指进进程程对对所所分分配配到到的的资资源源进进行行排排它它性性使使用用，即即在在一一段段时时间间内内某某资资源源只只由由一一个个进进程程占占用用。如如果果此此时时还还有有其其它它进进程程请请求求该该资资源源，则则请请求求者者只只能能等等待待，直直至至占占有有该该资资源源的的进进程程用毕释放。用毕释放。(2) 请求和保持条件：指进程已经保持了至少一个资源，请求和保持条件：指进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又已被其它进程占有，此但又提出了新的资源请求，而该资源又已被其它进程占有，此时请

20、求进程阻塞，但又对自己已获得的其它资源保持不放。时请求进程阻塞，但又对自己已获得的其它资源保持不放。 第三章处理机调度与死锁 (3) 不不剥剥夺夺条条件件：指指进进程程已已获获得得的的资资源源，在在未未使使用用完完之之前前，不能被剥夺，只能在使用完时由自己释放。不能被剥夺，只能在使用完时由自己释放。(4) 环路等待条件：指在发生死锁时，必然存在一个进程环路等待条件：指在发生死锁时，必然存在一个进程资源的环形链，即进程集合资源的环形链，即进程集合P0，P1，P2，Pn中的中的P0正在等待一个正在等待一个P1占用的资源；占用的资源； P1正在等待正在等待P2占用的资源，占用的资源，Pn正在等待已被

21、正在等待已被P0占用的资源。占用的资源。 第三章处理机调度与死锁 3.5.3处理死锁的基本方法处理死锁的基本方法执行前执行前开始执行开始执行发生死锁发生死锁死锁解除死锁解除死锁预防死锁预防死锁避免死锁避免死锁检测死锁检测解除死锁解除死锁第三章处理机调度与死锁 (1) 预预防防死死锁锁。这这是是一一种种较较简简单单和和直直观观的的事事先先预预防防的的方方法法。该该方方法法是是通通过过设设置置某某些些限限制制条条件件，去去破破坏坏产产生生死死锁锁的的四四个个必必要要条条件件中中的的一一个个或或几几个个条条件件，来来预预防防发发生生死死锁锁。预预防防死死锁锁是是一一种种较较易易实实现现的的方方法法，

22、已已被被广广泛泛使使用用。但但由由于于所所施施加加的的限限制制条条件件往往往往太太严严格格，因因而而可可能能会会导导致致系系统统资资源源利利用用率率和和系系统吞吐量降低。统吞吐量降低。 (2) 避避免免死死锁锁。该该方方法法同同样样是是属属于于事事先先预预防防的的策策略略，但但它它并并不不须须事事先先采采取取各各种种限限制制措措施施去去破破坏坏产产生生死死锁锁的的四四个个必必要要条条件件，而而是是在在资资源源的的动动态态分分配配过过程程中中，用用某某种种方方法法去去防防止止系系统统进进入入不不安安全全状状态态，从从而而避避免免发发生生死死锁锁。这这种种方方法法只只需需事事先先施施加加较较弱弱的

23、的限限制制条条件件，便便可可获获得得较较高高的的资资源源利利用用率率及及系系统统吞吞吐吐量，但在实现上有一定的难度。量，但在实现上有一定的难度。第三章处理机调度与死锁 (3) 检测死锁。这种方法并不须事先采取任何限制性措施，检测死锁。这种方法并不须事先采取任何限制性措施，也不必检查系统是否已经进入不安全区，而是允许系统在运行也不必检查系统是否已经进入不安全区，而是允许系统在运行过程中发生死锁。但可通过系统所设置的检测机构，及时地检过程中发生死锁。但可通过系统所设置的检测机构，及时地检测出死锁的发生，并精确地确定与死锁有关的进程和资源；测出死锁的发生，并精确地确定与死锁有关的进程和资源； 然后，

24、采取适当措施，从系统中将已发生的死锁清除掉。然后，采取适当措施，从系统中将已发生的死锁清除掉。 (4) 解除死锁。这是与检测死锁相配套的一种措施。当检解除死锁。这是与检测死锁相配套的一种措施。当检测到系统中已发生死锁时，须将进程从死锁状态中解脱出来。测到系统中已发生死锁时，须将进程从死锁状态中解脱出来。常用的实施方法是撤消或挂起一些进程，以便回收一些资源，常用的实施方法是撤消或挂起一些进程，以便回收一些资源，再将这些资源分配给已处于阻塞状态的进程，使之转为就绪状再将这些资源分配给已处于阻塞状态的进程，使之转为就绪状态，以继续运行。死锁的检测和解除措施有可能使系统获得较态，以继续运行。死锁的检测

25、和解除措施有可能使系统获得较好的资源利用率和吞吐量，但在实现上难度也最大。好的资源利用率和吞吐量，但在实现上难度也最大。第三章处理机调度与死锁 3.6预防死锁的方法预防死锁的方法 3.6.13.6.1预防死锁预防死锁 死锁的预防一般是从破坏导致发生死锁的必要条件着手，只要死锁的预防一般是从破坏导致发生死锁的必要条件着手，只要能使四个必要条件其中的任何一个不成立，就可防止死锁。能使四个必要条件其中的任何一个不成立，就可防止死锁。 1 1摒弃摒弃“请求和保持请求和保持”条件。动态分配条件。动态分配静态分配静态分配系统规定所有进程在开始运行之前，都必须一次性地申请系统规定所有进程在开始运行之前，都必

26、须一次性地申请其在整个运行过程所需的全部资源。此时，若系统有足够的资其在整个运行过程所需的全部资源。此时，若系统有足够的资源分配给某进程，便可把其需要的所有资源分配给该进程，这源分配给某进程，便可把其需要的所有资源分配给该进程，这样，该进程在整个运行期间便不会再提出资源要求，从而摒弃样，该进程在整个运行期间便不会再提出资源要求，从而摒弃了请求条件。但在分配资源时，只要有一种资源不能满足某进了请求条件。但在分配资源时，只要有一种资源不能满足某进程的要求，即使其它所需的各资源都空闲，也不分配给该进程，程的要求，即使其它所需的各资源都空闲，也不分配给该进程，而让该进程等待。由于在该进程的等待期间，它

27、并未占有任何而让该进程等待。由于在该进程的等待期间，它并未占有任何资源，因而也摒弃了保持条件，从而可以避免发生死锁。资源，因而也摒弃了保持条件，从而可以避免发生死锁。 第三章处理机调度与死锁 这种预防死锁的方法其优点是简单、易于实现且很安全。这种预防死锁的方法其优点是简单、易于实现且很安全。但其但其缺点缺点却也极其明显：却也极其明显：1.1.首先表现为资源被严重浪费，因为一个进程是一次性地获首先表现为资源被严重浪费，因为一个进程是一次性地获得其整个运行过程所需的全部资源的，且独占资源，其中得其整个运行过程所需的全部资源的，且独占资源，其中可能有些资源很少使用，甚至在整个运行期间都未使用，可能有

28、些资源很少使用，甚至在整个运行期间都未使用，这就严重地恶化了系统资源的利用率；这就严重地恶化了系统资源的利用率；2.2.其次是使进程延迟运行，仅当进程在获得了其所需的全部其次是使进程延迟运行，仅当进程在获得了其所需的全部资源后，才能开始运行，但可能因有些资源已长期被其它资源后，才能开始运行，但可能因有些资源已长期被其它进程占用而致使等待该资源的进程迟迟不能运行。进程占用而致使等待该资源的进程迟迟不能运行。 第三章处理机调度与死锁 2 2摒弃摒弃“不剥夺不剥夺”条件条件在采用这种方法时系统规定，进程是逐个地提出对资源在采用这种方法时系统规定，进程是逐个地提出对资源的要求的。当一个已经保持了某些资

29、源的进程，再提出新的的要求的。当一个已经保持了某些资源的进程，再提出新的资源请求而不能立即得到满足时，必须释放它已经保持了的资源请求而不能立即得到满足时，必须释放它已经保持了的所有资源，待以后需要时再重新申请。这意味着某一进程已所有资源，待以后需要时再重新申请。这意味着某一进程已经占有的资源，在运行过程中会被暂时地释放掉，也可认为经占有的资源，在运行过程中会被暂时地释放掉，也可认为是被剥夺了，从而摒弃了是被剥夺了，从而摒弃了“不剥夺不剥夺”条件。条件。 缺点：缺点：这种预防死锁的方法实现起来比较复杂且要付出这种预防死锁的方法实现起来比较复杂且要付出很大的代价。此外，这种策略还可能因为反复地申请

30、和释放很大的代价。此外，这种策略还可能因为反复地申请和释放资源，致使进程的执行被无限地推迟，这不仅延长了进程的资源，致使进程的执行被无限地推迟，这不仅延长了进程的周转时间，而且也增加了系统开销，降低了系统吞吐量。周转时间，而且也增加了系统开销，降低了系统吞吐量。第三章处理机调度与死锁 3 3摒弃摒弃“环路等待环路等待”条件：资源有序分配条件：资源有序分配这种方法中规定，系统将所有这种方法中规定，系统将所有资源按类型进行线性排队资源按类型进行线性排队，并赋予不同的序号并赋予不同的序号。例如，令输入机的序号为。例如，令输入机的序号为1，打印机的序，打印机的序号为号为2，磁带机为，磁带机为3，磁盘为

31、，磁盘为4。所有进程对资源的请求必须严所有进程对资源的请求必须严格按照资源序号递增的次序提出，格按照资源序号递增的次序提出，这样，在所形成的资源分这样，在所形成的资源分配图中，不可能再出现环路，因而摒弃了配图中，不可能再出现环路，因而摒弃了“环路等待环路等待”条件。条件。事实上，在采用这种策略时，总有一个进程占据了较高序号事实上，在采用这种策略时，总有一个进程占据了较高序号的资源，此后它继续申请的资源必然是空闲的，因而进程可的资源，此后它继续申请的资源必然是空闲的，因而进程可以一直向前推进。以一直向前推进。 第三章处理机调度与死锁 系统资源进行统一编号。进程申请使用资源时，必须严格按照系统资源

32、进行统一编号。进程申请使用资源时，必须严格按照编号的升序进行。编号的升序进行。 进进 程程资资 源源ABC1、卡片输入机、卡片输入机 （3台）台） 2、行式打印机、行式打印机 （2台）台）*3、卡片输入机、卡片输入机 （1台）台）*4、磁带机、磁带机 （1台）台）第三章处理机调度与死锁 这这种种预预防防死死锁锁的的策策略略与与前前两两种种策策略略比比较较，其其资资源源利利用用率率和和系系统统吞吐量都有较明显的改善。但也存在下述严重问题：吞吐量都有较明显的改善。但也存在下述严重问题：首首先先是是为为系系统统中中各各类类资资源源所所分分配配( (确确定定) )的的序序号号必必须须相相对对稳稳定定，

33、这就限制了新类型设备的增加。这就限制了新类型设备的增加。其次，尽管在为资源的类型分配序号时，已经考虑到大多数作其次，尽管在为资源的类型分配序号时，已经考虑到大多数作业在实际使用这些资源时的顺序，但也经常会发生这种情况：即作业在实际使用这些资源时的顺序，但也经常会发生这种情况：即作业业(进程进程)使用各类资源的顺序与系统规定的顺序不同，造成对资源使用各类资源的顺序与系统规定的顺序不同，造成对资源的浪费。例如，某进程先用磁带机，后用打印机，但按系统规定，的浪费。例如，某进程先用磁带机，后用打印机，但按系统规定，该进程应先申请打印机而后申请磁带机，致使先获得的打印机被长该进程应先申请打印机而后申请磁

34、带机，致使先获得的打印机被长时间闲置。时间闲置。 第三，为方便用户，系统对用户在编程时所施加的限制条件应第三，为方便用户，系统对用户在编程时所施加的限制条件应尽量少。然而这种按规定次序申请的方法，必然会限制用户简单、尽量少。然而这种按规定次序申请的方法，必然会限制用户简单、自主地编程。自主地编程。第三章处理机调度与死锁 3.6.23.6.2系统安全状态系统安全状态1 1安全状态安全状态在在避免死锁的方法中，允许进程动态地申请资源，避免死锁的方法中，允许进程动态地申请资源，但系但系统在进行资源分配之前，应统在进行资源分配之前，应先计算此次资源分配的安全性先计算此次资源分配的安全性。若此次分配不会

35、导致系统进入不安全状态，则将资源分配给若此次分配不会导致系统进入不安全状态，则将资源分配给进程；否则，令进程等待。进程；否则，令进程等待。 第三章处理机调度与死锁 所所谓谓安安全全状状态态，是是指指系系统统能能按按某某种种进进程程顺顺序序(P(P1 1，P P2 2，P Pn n)()(称称P P1 1，P P2 2，P Pn n序序列列为为安安全全序序列列) )，来来为为每每个个进进程程P Pi i分分配配其其所所需需资资源源，直直至至满满足足每每个个进进程程对对资资源源的的最最大大需需求求，使使每每个个进进程程都都可可顺顺利利地地完完成成。如如果果系系统统无无法法找找到到这这样样一一个个安

36、安全序列，则称系统处于不安全状态。全序列，则称系统处于不安全状态。虽然并非所有的不安全状态都必然会转为死锁状态，但虽然并非所有的不安全状态都必然会转为死锁状态，但当系统进入不安全状态后，便有可能进而进入死锁状态；当系统进入不安全状态后，便有可能进而进入死锁状态；反反之，只要系统处于安全状态，系统便可避免进入死锁状态。之，只要系统处于安全状态，系统便可避免进入死锁状态。因此，因此，避免死锁的实质在于：系统在进行资源分配时，如何避免死锁的实质在于：系统在进行资源分配时，如何使系统不进入不安全状态。使系统不进入不安全状态。 第三章处理机调度与死锁 2安全状态之例安全状态之例我们通过一个例子来说明安全

37、性。我们通过一个例子来说明安全性。假定系统中有三个进程假定系统中有三个进程P1、P2和和P3，共有，共有12台磁带机。台磁带机。进程进程P1总共要求总共要求10台磁带机，台磁带机，P2和和P3分别要求分别要求4台和台和9台。台。假设在假设在T0时刻，进程时刻，进程P1、P2和和P3已分别获得已分别获得5台、台、2台和台和2台磁台磁带机，尚有带机，尚有3台空闲未分配，如下表所示：台空闲未分配，如下表所示： 第三章处理机调度与死锁 安全状态安全状态 ： 安全序列：安全序列：P2 P3 进程号总共需求已分配还需剩余P110553P2422P3927进程号总共需求已分配还需剩余P110552P2422

38、P3936不安全状态不安全状态 无无安全序列安全序列第三章处理机调度与死锁 3.6.33.6.3利用银行家算法避免死锁利用银行家算法避免死锁l银行家算法银行家算法 一个银行家把他的固定资金借给若干客户，使这些客户一个银行家把他的固定资金借给若干客户，使这些客户在满足对资金的要求后能完成其交易，把所借资金归还给银在满足对资金的要求后能完成其交易，把所借资金归还给银行家。假定客户分成若干次进行借款，每个客户预先说明自行家。假定客户分成若干次进行借款，每个客户预先说明自己所要求的最大资金量，并每次提出部分资金量申请和获得己所要求的最大资金量，并每次提出部分资金量申请和获得分配。如果银行家满足了客户对

39、资金的最大需求量，则该客分配。如果银行家满足了客户对资金的最大需求量，则该客户在资金运作后，应在有限时间内将资金全部归还银行家。户在资金运作后，应在有限时间内将资金全部归还银行家。具体过程如下：具体过程如下： 顾客的借款操作依次顺序进行，直到全部操作完成；顾客的借款操作依次顺序进行，直到全部操作完成； 银银行行家家对对顾顾客客的的借借款款操操作作进进行行判判断断，确确定定其其安安全全性性（能否支持顾客借款，直到全部归还）；（能否支持顾客借款，直到全部归还）； 如果是安全的，则借款给顾客，否则暂不借款。如果是安全的，则借款给顾客，否则暂不借款。第三章处理机调度与死锁 银行家算法例银行家算法例 假

40、定银行可以分期贷款假定银行可以分期贷款10法郎给顾客，法郎给顾客，P,Q,R 顾客顾客 目前已贷法郎目前已贷法郎 所需最大法郎所需最大法郎 P 9 Q 5 R 3 522当前还剩几个？当当前还剩几个？当P申请一个法郎时，银行能满足他的要求吗？申请一个法郎时，银行能满足他的要求吗？R申请一个呢？申请一个呢？第三章处理机调度与死锁 1 1银行家算法中的数据结构银行家算法中的数据结构(1) (1) 可可利利用用资资源源向向量量AvailableAvailable。这这是是一一个个含含有有m m个个元元素素的的数数组组，其其中中的的每每一一个个元元素素代代表表一一类类可可利利用用的的资资源源数数目目，

41、其其初初始始值值是是系系统统中中所所配配置置的的该该类类全全部部可可用用资资源源的的数数目目，其其数数值值随随 该该 类类 资资 源源 的的 分分 配配 和和 回回 收收 而而 动动 态态 地地 改改 变变 。 如如 果果Availablej=KAvailablej=K，则表示系统中现有，则表示系统中现有R jR j类资源类资源K K个。个。(2) (2) 最最大大需需求求矩矩阵阵MaxMax。这这是是一一个个n nm m的的矩矩阵阵，它它定定义义了了系系统统中中n n个个进进程程中中的的每每一一个个进进程程对对m m类类资资源源的的最最大大需需求求。如如果果Maxi,j=KMaxi,j=K，

42、则表示进程，则表示进程i i需要需要RjRj类资源的最大数目为类资源的最大数目为K。 第三章处理机调度与死锁 (3) 分分配配矩矩阵阵Allocation。这这也也是是一一个个nm的的矩矩阵阵，它它定定义义了了系系统统中中每每一一类类资资源源当当前前已已分分配配给给每每一一进进程程的的资资源源数数。如如果果Allocationi,j=K，则则表表示示进进程程i当当前前已已分分得得R j类类资资源源的的数数目目为为K。(4) 需需求求矩矩阵阵Need。这这也也是是一一个个nm的的矩矩阵阵，用用以以表表示示每每一一个个进进程程尚尚需需的的各各类类资资源源数数。如如果果Needi,j=K，则则表表示

43、示进进程程i还需要还需要R j类资源类资源K个，个，方能完成其任务。方能完成其任务。上述三个矩阵间存在下述关系：上述三个矩阵间存在下述关系：Needi, j=Maxi, j- -Allocationi, j 第三章处理机调度与死锁 2银行家算法银行家算法设设Request i是进程是进程Pi的请求向量，如果的请求向量，如果Request ij=K，表示进程表示进程P i需要需要K个个R j类型的资源。当类型的资源。当P i发出资源请求后，发出资源请求后，系统按下述步骤进行检查：系统按下述步骤进行检查：(1) 如果如果Request ijNeedi,j，便转向步骤，便转向步骤(2)；否则认；否则

44、认为出错，因为它所需要的资源数已超过它所宣布的最大值。为出错，因为它所需要的资源数已超过它所宣布的最大值。(2) 如果如果RequestijAvailablej，便转向步骤，便转向步骤(3)；否则，；否则，表示尚无足够资源，表示尚无足够资源，Pi须须等待。等待。 第三章处理机调度与死锁 (3) 系系统统试试探探着着把把资资源源分分配配给给进进程程P i，并并修修改改下下面面数数据据结结构中的数值：构中的数值：Availablej:= Availablej- -Request ij；Allocationi,j:= Allocationi,j+Request ij；Needi,j:= Needi,

45、j- -Request ij；(4) 系统执行安全性算法，检查此次资源分配后系统是否系统执行安全性算法，检查此次资源分配后系统是否处于安全状态。若安全，才正式将资源分配给进程处于安全状态。若安全，才正式将资源分配给进程Pi，以完，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程源分配状态，让进程Pi等待。等待。 第三章处理机调度与死锁 3 3安全性算法安全性算法系统所执行的安全性算法可描述如下：系统所执行的安全性算法可描述如下：(1) (1) 设置两个向量：设置两个向量： 工工作作向向量量WorkWork，它它表表示

46、示系系统统可可提提供供给给进进程程继继续续运运行行所所需需的的各各类类资资源源数数目目，它它含含有有m m个个元元素素，在在执执行行安安全全算算法法开开始时，始时，Work:=AvailableWork:=Available。 进程完成向量进程完成向量Finish，它表示系统是否有足够的资源，它表示系统是否有足够的资源分配给进程，使之运行完成。开始时分配给进程，使之运行完成。开始时Finishi:=false；当有；当有足够资源分配给进程时，再令足够资源分配给进程时，再令Finishi:=true。 第三章处理机调度与死锁 (2) (2) 从进程集合中找到一个能满足下述条件的进程：从进程集合中

47、找到一个能满足下述条件的进程： Finishi=falseFinishi=false； NeediWorkNeediWork； 若找到，执行步骤若找到，执行步骤(3)(3)，否则，执行步骤，否则，执行步骤(4)(4)。(3) (3) 当当进进程程PiPi获获得得资资源源后后，可可顺顺利利执执行行，直直至至完完成成，并并释释放放出出分分配给它的资源，故应执行：配给它的资源，故应执行：Work:= Work+AllocationiWork:= Work+Allocationi；Finishi:=trueFinishi:=true；go to step 2； (4) 如果所有进程的如果所有进程的Fi

48、nishi=true都满足，则表示系统处于安全都满足，则表示系统处于安全状态；否则，系统处于不安全状态。状态；否则，系统处于不安全状态。第三章处理机调度与死锁 4银行家算法之例银行家算法之例假定系统中有五个进程假定系统中有五个进程 P0，P1，P2，P3，P4和三类资和三类资源源A，B，C，各种资源的数量分别为，各种资源的数量分别为10、5、7，在，在T0时刻时刻的资源分配情况如图的资源分配情况如图3-16所示。所示。 第三章处理机调度与死锁 图图3-16 T0时刻的资源分配表时刻的资源分配表 ABCABC资源的数量分别为资源的数量分别为10、5、7，第三章处理机调度与死锁 (1) T0时刻的

49、安全性：利用安全性算法对时刻的安全性：利用安全性算法对T0时刻的资源分时刻的资源分配情况进行分析配情况进行分析(见图见图 3-17所示所示)可知，在可知，在T0时刻存在着一个安时刻存在着一个安全序列全序列P1，P3，P4，P2，P0，故系统是安全的。，故系统是安全的。 图3-17T0时刻的安全序列 第三章处理机调度与死锁 (2) P1请请求求资资源源：P1发发出出请请求求向向量量Request1(1，0，2)，系系统按银行家算法进行检查：统按银行家算法进行检查： Request1(1，0，2)Need1(1，2，2) Request1(1，0，2)Available1(3，3，2) 系统先假定

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

51、分配后）： 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，2，0)Need0(7，4，3)； Request0(0，2，0)Available(2，3，0)； 系统暂时先假定可为系统暂时先假定可为P0分配资源，并修改有关数据，分配资源，并修改有关数据，如图如图3-19所示。所示。 第三章处理机调度与死锁 图图3-19为为P0分配资源后的有

52、关资源数据分配资源后的有关资源数据 (5) (5) 进行安全性检查：可用资源进行安全性检查：可用资源Available(2Available(2，1 1，0)0)已不能满足任已不能满足任何进程的需要，故系统进入不安全状态，此时系统不分配资源。何进程的需要，故系统进入不安全状态，此时系统不分配资源。第三章处理机调度与死锁 3.7死锁的检测与解除死锁的检测与解除 3.7.1死锁的检测死锁的检测允许死锁发生允许死锁发生 保存有关资源的请求和分配信息；提供检测算法保存有关资源的请求和分配信息；提供检测算法检测时机检测时机 太频繁：系统效率低。太频繁：系统效率低。 选择时机：当选择时机：当CPU利用率低

53、于某一值时。利用率低于某一值时。第三章处理机调度与死锁 1资源分配图资源分配图(Resource Allocation Graph)系系统统死死锁锁可可利利用用资资源源分分配配图图来来描描述述。该该图图是是由由一一组组结结点点N和和一一组组边边E所所组组成成的的一一个个对对偶偶G=(N1E)，它它具具有有下下述述形形式式的的定义和限制：定义和限制：(1) 把把N分分为为两两个个互互斥斥的的子子集集 ，即即一一组组进进程程结结点点P=p1，p2，pn和和一一组组资资源源结结点点R=r1，r2，rn，N=PR。在在图图3-20所所示示的的例例子子中中，P=p1，p2，R=r1，r2，N=r1，r2

54、p1，p2。 第三章处理机调度与死锁 (2) 凡凡属属于于E中中的的一一个个边边eE，都都连连接接着着P中中的的一一个个结结点点和和R中中的的一一个个结结点点，e=pi，rj是是资资源源请请求求边边，由由进进程程pi指指向向资资源源rj，它它表表示示进进程程pi请请求求一一个个单单位位的的rj资资源源。e=rj，pi是是资资源源分分配配边边，由由资资源源rj指指向向进进程程pi，它它表表示示把把一一个个单单位位的的资资源源rj分分配配给给进进程程pi。图图3-13中中示示出出了了两两个个请请求求边边和和两两个个分分配配边边，即即E=(p1，r2)，(r2，p2)，(p2，r1)，(r1，p1)

55、。我们用圆圈代表一个进程，用方框代表一类资源。由于一我们用圆圈代表一个进程，用方框代表一类资源。由于一种类型的资源可能有多个，我们用方框中的一个点代表一类资种类型的资源可能有多个，我们用方框中的一个点代表一类资源中的一个资源。此时，请求边是由进程指向方框中的源中的一个资源。此时，请求边是由进程指向方框中的rj，而，而分配边则应始于方框中的一个点。图分配边则应始于方框中的一个点。图3-20示出了一个资源分配示出了一个资源分配图。图。第三章处理机调度与死锁 图图3-20每类资源有多个时的情况每类资源有多个时的情况 p1进程已经分得了两个进程已经分得了两个r1资源，资源，并又请求一个并又请求一个r2

56、资源；资源；p2进程分进程分得了一个得了一个r1和一个和一个r2资源，并又资源，并又请求请求r1资源。资源。 第三章处理机调度与死锁 2 2死锁定理死锁定理我我们们可可以以利利用用把把资资源源分分配配图图加加以以简简化化的的方方法法( (图图3-21)3-21)，来检测当系统处于来检测当系统处于S S状态时是否为死锁状态。状态时是否为死锁状态。S为为死死锁锁状状态态的的充充分分条条件件是是：当当且且仅仅当当S状状态态的的资资源源分分配配图图是是不可完全简化的。该充分条件被称为死锁定理。不可完全简化的。该充分条件被称为死锁定理。 简化方法如下：简化方法如下：(1) 在资源分配图中，找出一个既不阻

57、塞又非独立的进在资源分配图中，找出一个既不阻塞又非独立的进程结点程结点Pi。在顺利的情况下，。在顺利的情况下，Pi可获得所需资源而继续运行，可获得所需资源而继续运行，直至运行完毕，再释放其所占有的全部资源，这相当于消去直至运行完毕，再释放其所占有的全部资源，这相当于消去pi所求的请求边和分配边，使之成为孤立的结点。所求的请求边和分配边，使之成为孤立的结点。第三章处理机调度与死锁 图图3-21资源分配图的简化资源分配图的简化 在图在图3-21(a)中，将中，将p1的两个分配边和一个请求边消去，便形的两个分配边和一个请求边消去，便形成图成图(b)所示的情况。所示的情况。 第三章处理机调度与死锁 (

58、2) (2) p p1 1释释放放资资源源后后，便便可可使使p2p2获获得得资资源源而而继继续续运运行行，直直至至p p2 2完完成成后后又又释释放放出出它它所所占占有有的的全全部部资资源源，形形成成图图(c)(c)所所示示的的情况。情况。(3) (3) 在在进进行行一一系系列列的的简简化化后后，若若能能消消去去图图中中所所有有的的边边，使使所所有有的的进进程程结结点点都都成成为为孤孤立立结结点点，则则称称该该图图是是可可完完全全简简化化的的；若若不不能能通通过过任任何何过过程程使使该该图图完完全全简简化化，则则称称该该图图是是不不可可完全简化的。完全简化的。第三章处理机调度与死锁 3死锁检测

59、中的数据结构死锁检测中的数据结构死锁检测中的数据结构类似于银行家算法中的数据结构：死锁检测中的数据结构类似于银行家算法中的数据结构：(1) 可可利利用用资资源源向向量量Available，它它表表示示了了m类类资资源源中中每每一一类资源的可用数目。类资源的可用数目。(2) 把不占用资源的进程把不占用资源的进程(向量向量Allocationi:=0)记入记入L表中表中.(3) 从从进进程程集集合合中中找找到到一一个个RequestiWork的的进进程程，做做如如下处理：下处理： 将将其其资资源源分分配配图图简简化化，释释放放出出资资源源，增增加加工工作作向向量量Work:=Work + Allo

60、cation i。 将它记入将它记入L表中。表中。第三章处理机调度与死锁 (4) 若不能把所有进程都记入若不能把所有进程都记入L表中，便表明系统状态表中，便表明系统状态S的的资源分配图是不可完全简化的资源分配图是不可完全简化的, ,系统状态将发生死锁。系统状态将发生死锁。Work:=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)； 第三章处理机调

61、度与死锁 3.7.23.7.2死锁的解除死锁的解除当当发发现现有有进进程程死死锁锁时时，便便应应立立即即把把它它们们从从死死锁锁状状态态中中解解脱脱出来。常采用解除死锁的两种方法是：出来。常采用解除死锁的两种方法是：(1) (1) 剥剥夺夺资资源源。从从其其它它进进程程剥剥夺夺足足够够数数量量的的资资源源给给死死锁锁进进程，以解除死锁状态。程，以解除死锁状态。(2) (2) 撤撤消消进进程程。最最简简单单的的撤撤消消进进程程的的方方法法是是使使全全部部死死锁锁进进程程都都夭夭折折掉掉；稍稍微微温温和和一一点点的的方方法法是是按按照照某某种种顺顺序序逐逐个个地地撤撤消消进程，直至有足够的资源可用

62、，使死锁状态消除为止。进程，直至有足够的资源可用，使死锁状态消除为止。在在出出现现死死锁锁时时，可可采采用用各各种种策策略略来来撤撤消消进进程程。例例如如，为为解解除除死死锁锁状状态态所所需需撤撤消消的的进进程程数数目目最最小小；或或者者，撤撤消消进进程程所所付付出出的代价最小等。的代价最小等。第三章处理机调度与死锁 小结小结概念：周转时间、带权周转时间、死锁、死锁预防、死锁避免、概念：周转时间、带权周转时间、死锁、死锁预防、死锁避免、死锁检测、死锁恢复死锁检测、死锁恢复三种调度类型的比较三种调度类型的比较调度时机、切换与过程调度时机、切换与过程 调度方式、调度的基本准则调度方式、调度的基本准

63、则调度算法（调度算法（先来先服务调度算法；短作业（短任务、短进程、先来先服务调度算法；短作业（短任务、短进程、短线程）优先调度算法；时间片轮转调度算法；优先级调度算短线程）优先调度算法；时间片轮转调度算法；优先级调度算法；高响应比优先调度算法；多级反馈队列调度算法。）法；高响应比优先调度算法；多级反馈队列调度算法。）产生死锁的原因、四个必要条件。产生死锁的原因、四个必要条件。进程资源图、银行家算法。进程资源图、银行家算法。死锁定理死锁定理第三章处理机调度与死锁 调度算法小结调度算法小结FCFS 适应：作业，进程（线程）适应：作业，进程（线程） 特点：实现简单，开销小，有利于长作业，适合批处理系

64、，特点：实现简单，开销小，有利于长作业，适合批处理系， 平均周转时间长平均周转时间长 SJF 特点：实现复杂，开销大，有利于短作业，适合批处理系特点：实现复杂，开销大，有利于短作业，适合批处理系统，平均周转时间短，有饥饿现象。统，平均周转时间短，有饥饿现象。 适应：作业，进程（线程）适应：作业，进程（线程） HRN(Highest Response-ratio Next,最高响应比优先）最高响应比优先） 响应比响应比RR=（等待时间（等待时间+估计运行时间）估计运行时间）/估计运行时间估计运行时间 适应：作业，进程（线程）适应：作业，进程（线程） 特点：实现复杂，开销大，公平，适合批处理系统特

65、点：实现复杂，开销大，公平，适合批处理系统平均周转时间较短平均周转时间较短第三章处理机调度与死锁 Priority 适应：作业，进程（线程）适应：作业，进程（线程） 特点：实现复杂特点：实现复杂，开销大，有利于紧迫作业，开销大，有利于紧迫作业， 适合实适合实 时系统时系统l MLQ&MLFQ 适应：进程（线程适应：进程（线程) 特点：实现特点：实现复杂复杂，开销大，响应时间较短，区分进程性质，开销大，响应时间较短，区分进程性质， 适合分时系统和通用系统。适合分时系统和通用系统。 RR 适应：进程（线程适应：进程（线程) 特点：实现特点：实现简单简单，开销大，响应时间短，不区分进程的性质，开销大

66、，响应时间短，不区分进程的性质 适合分时系统适合分时系统第三章处理机调度与死锁 1.假定某多道程序系统有供用户使用的主存空间假定某多道程序系统有供用户使用的主存空间100k,磁带机磁带机2台台,打印机打印机1台台,系统采用系统采用可变式分区管理主存可变式分区管理主存,优先分配内存的低地址部分优先分配内存的低地址部分,且作业在内存中不能移动且作业在内存中不能移动.设备设备采用静态分配技术采用静态分配技术.主存中的作业平分主存中的作业平分cpu的时间的时间.作业采用先来先服务调度算法作业采用先来先服务调度算法. I/O操作的时间忽略不计操作的时间忽略不计. 现有如下一组作业序列现有如下一组作业序列

67、: 作用号作用号 提交时间提交时间 运行时间运行时间(分分) 主存量主存量 磁带机磁带机 打印机打印机18:0025 15k1128:2010 30k0138:2020 60k1048:3020 20k1058:3515 10k11试求：试求： 1.调度程序选中作业的次序是调度程序选中作业的次序是_. (用作业号描述用作业号描述)2.最大的作业周转时间是最大的作业周转时间是_分分.3.最小的作业周转时间是最小的作业周转时间是_分分4.作业全部完成的时间是作业全部完成的时间是_(时时:分描述分描述)5.作业作业3的带权周转时间是的带权周转时间是_.作业作业第三章处理机调度与死锁 2一个计算机有一

68、个计算机有6台磁带机，由台磁带机，由n个进程竞争使用，每个进程可个进程竞争使用，每个进程可能需要两台磁带机，那么能需要两台磁带机，那么n是多少时，系统才没有死锁的危险是多少时，系统才没有死锁的危险？3. P1、P2两个进程同步算法如下：两个进程同步算法如下： 设：设：semaphore:s1=1,s2=0,s3=1;P2: begin P(s3); P(s1); V(s3); V(s1); endP1: begin P(s1); P(s2); V(s2); V(s1); end试分析试分析P1,P2是否会产生死锁。是否会产生死锁。第三章处理机调度与死锁 4设系统中有设系统中有A类资源类资源10

69、个，个，B类资源类资源6个，个，C 类资源类资源 7个。系个。系统采用银行家算法避免死锁发生，现有统采用银行家算法避免死锁发生，现有5个进程，当前状态如个进程，当前状态如下图所示。下图所示。 Allocation Max Available Need A B C A B C A B C A B C P0 0 1 0 7 5 3 3 4 2 7 4 3 P1 2 0 0 3 2 3 1 2 3P2 3 0 2 6 1 6 3 1 4P3 2 1 1 5 2 2 3 1 1P4 0 0 2 4 3 3 4 3 1问问 当进程当进程p2提出一个请求（提出一个请求（1，1， 1），系统是否可以满足），系统是否可以满足？进程？进程p3提出请求（提出请求（1，1，1）呢？以上两个请求若系统可以）呢？以上两个请求若系统可以满足，请给出系统处理过程中，判断系统是安全状态时的进满足，请给出系统处理过程中，判断系统是安全状态时的进程完成顺序。程完成顺序。