計(jì)算機(jī)操作系統(tǒng) 第三章

第三章處理機(jī)調(diào)度與死鎖

hedulingand

處理機(jī)是最重要的計(jì)算機(jī)資源，提高處理

機(jī)的利用率及改善系統(tǒng)性能，在很大程度上也

決于處理機(jī)調(diào)度性能的好壞，因而，處理機(jī)調(diào)

度成為操作系統(tǒng)設(shè)計(jì)的中心問(wèn)題之一。

本章主要內(nèi)容

/處理機(jī)調(diào)度的基本概念

/調(diào)度算法

/實(shí)時(shí)系統(tǒng)中的調(diào)度

/多處理機(jī)系統(tǒng)

/產(chǎn)生死鎖的原因和必要條件

曹死鎖的預(yù)防和避免

■死鎖的檢測(cè)和解除

2

作業(yè)的概念

■作業(yè)（job）：由用戶提交給系統(tǒng)處理的一個(gè)計(jì)算

任務(wù)，稱為作業(yè)。它包括用戶程序、數(shù)據(jù)，以及

對(duì)程序運(yùn)行進(jìn)行控制和處理的有關(guān)信息。一般，

可把作業(yè)分成批處理型作業(yè)和終端型作業(yè)兩類。

■作業(yè)從進(jìn)入系統(tǒng)到運(yùn)行結(jié)束，一般要經(jīng)歷進(jìn)入、

收容、運(yùn)行、完成四個(gè)階段。相應(yīng)地，我們說(shuō)此

作業(yè)處于進(jìn)入、后備、執(zhí)行、完成四個(gè)不同的狀

0

3

作業(yè)的狀態(tài)

■進(jìn)入狀態(tài)即提交狀態(tài)，作業(yè)從輸入設(shè)備進(jìn)入輸入

井°

■后備狀態(tài)操作員把作業(yè)輸入到直接存取的后援存

取器后，為進(jìn)入系統(tǒng)的作業(yè)建立作業(yè)控制塊，并

把它加入到后備作業(yè)隊(duì)列中，等候作業(yè)調(diào)度程序

調(diào)度。這一過(guò)程也稱為作業(yè)注冊(cè)。

■運(yùn)行狀態(tài)作業(yè)被作業(yè)調(diào)度程序選中，且分配了必

要的資源，建立一組相應(yīng)的進(jìn)程后，該作業(yè)就進(jìn)

入了運(yùn)行狀態(tài)。它分為三種狀態(tài)：即就緒狀態(tài)、

執(zhí)行狀態(tài)、阻塞狀態(tài)。

■完成狀態(tài)當(dāng)作業(yè)正常運(yùn)行結(jié)束或因發(fā)生錯(cuò)誤而終

J止時(shí)，作業(yè)進(jìn)入完成階段。

g

i5

§3.1處理機(jī)調(diào)度的基本概念

Thebasicconceptsofprocessorscheduling

一、處理機(jī)調(diào)度的層次

6

一個(gè)作業(yè)從提交開始，往往要經(jīng)歷三級(jí)調(diào)度：高級(jí)調(diào)度、

低級(jí)調(diào)度、中級(jí)調(diào)度。

1IWJ級(jí)調(diào)度(HighLevelScheduling)：作業(yè)調(diào)度/長(zhǎng)程調(diào)度/接納調(diào)度。

□按一定調(diào)度算法，外存后備隊(duì)列中選擇作業(yè)調(diào)入內(nèi)存，

創(chuàng)建PCB等，插入就緒隊(duì)列。

O一般用于批處理系統(tǒng)，分/實(shí)時(shí)系統(tǒng)一般直接入內(nèi)存，無(wú)

此環(huán)節(jié)。

?調(diào)度特性：

*接納作業(yè)數(shù)：取決于多道程序度。

作業(yè)多一影響服務(wù)質(zhì)量(周轉(zhuǎn)時(shí)間長(zhǎng))；

作業(yè)少—資源利用率和系統(tǒng)吞吐量低。

接納策略：即采用何種調(diào)度算法。

7

2低級(jí)調(diào)度(LowLevelScheduling)：進(jìn)程調(diào)度/短程調(diào)度

■在多道程環(huán)境下，進(jìn)程數(shù)目往往多于處理機(jī)數(shù)目,

致使它們爭(zhēng)用處理機(jī)。這就要求系統(tǒng)能按某種算

法，動(dòng)態(tài)地把處理機(jī)分配給就緒隊(duì)列中的一個(gè)進(jìn)

程，使之執(zhí)行。分配處理機(jī)的任務(wù)是由進(jìn)程調(diào)度

程序完成的。它是操作系統(tǒng)設(shè)計(jì)的中心問(wèn)題之一。

■低級(jí)調(diào)度就是按某種原則，決定就緒隊(duì)列中的某

個(gè)進(jìn)程獲得處理機(jī)，由分派程序(Dispatcher)

實(shí)施處理機(jī)分派。

8

進(jìn)程調(diào)度要解決的問(wèn)題

WHAT：按什么原則分配CPU

—進(jìn)程調(diào)度算法

WHEN：何時(shí)分配CPU

—進(jìn)程調(diào)度的時(shí)機(jī)

HOW：如何分配CPU

—CPU調(diào)度過(guò)程（進(jìn)程的上下文切換）

9

■進(jìn)程調(diào)度可有兩種方式：非搶占方式、搶占方式。

1)非搶占方式(Non-PreemptiveMode)

優(yōu)點(diǎn)：實(shí)現(xiàn)簡(jiǎn)單，系統(tǒng)開銷小。

缺點(diǎn)：不能滿足緊急任務(wù)的要求。

2)搶占方式(PreemptiveMode)

搶占原則：

(1)時(shí)間片原則(time-sliceprinciple)；

(2)優(yōu)先權(quán)原貝ij[priorityprinciple)；

(3)短進(jìn)程優(yōu)先原貝1"shortestjobfirstprinciple)；

■3中級(jí)調(diào)度(Intermediate-LevelScheduling)：中程調(diào)度

□對(duì)象：

■外存中因暫時(shí)不能運(yùn)行而被掛起的進(jìn)程

□動(dòng)作：

■將外存掛起的進(jìn)程激活，調(diào)入內(nèi)存，進(jìn)入就緒隊(duì)列

口目的：

■提高內(nèi)存的利用率和系統(tǒng)吞吐量

?:?三種調(diào)度運(yùn)行頻率：低＞中＞高

。進(jìn)程調(diào)度在操作系統(tǒng)中必不可少

11

二、調(diào)度隊(duì)列模型

每一種調(diào)度都涉及到進(jìn)程隊(duì)列。根據(jù)具有的調(diào)度類型,

形成三種類型的調(diào)度隊(duì)列模型。

1只有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型（如分時(shí)系統(tǒng)）

分時(shí)系統(tǒng)中，用戶鍵入的命令和數(shù)據(jù)，直接送入內(nèi)存。

由OS為命令建立一個(gè)進(jìn)程，并將它排在就緒隊(duì)列的末尾，然

后按時(shí)間片輪轉(zhuǎn)方式運(yùn)行。

該模型如圖3?1所示。

12

僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型

時(shí)間片完/被中斷

交互用戶

□□□□□結(jié)束

就緒隊(duì)列

進(jìn)程調(diào)度

喚醒阻塞

阻塞隊(duì)列

13

2有作業(yè)和進(jìn)程調(diào)度的調(diào)度隊(duì)列模型（批處理系統(tǒng)）

時(shí)間片完/被中斷

結(jié)束

口|「1口|口|/CPU

后備隊(duì)列

作業(yè)調(diào)度進(jìn)程調(diào)度

喚醒阻塞

阻塞隊(duì)列2

阻塞隊(duì)列

114

3有三級(jí)調(diào)度的調(diào)度隊(duì)列模型

當(dāng)在OS中引入中級(jí)調(diào)度后，我們可把進(jìn)程的就緒狀態(tài)分

為內(nèi)存就緒狀態(tài)（表示進(jìn)程在內(nèi)存中就緒）、外存就緒狀態(tài)。

也可把阻塞狀態(tài)進(jìn)一步分成內(nèi)存阻塞和外存阻塞狀態(tài)。

在調(diào)出操作的作用下，可使內(nèi)存就緒轉(zhuǎn)變?yōu)橥獯婢途w、

內(nèi)存阻塞轉(zhuǎn)變?yōu)橥獯孀枞?/p>

在中級(jí)調(diào)度的作用下，可使外存就緒轉(zhuǎn)變?yōu)閮?nèi)存就緒。

15

作業(yè)調(diào)度

時(shí)間片完

批量作業(yè)后備隊(duì)列

交互型作業(yè)

事

件

出

現(xiàn)

圖3-3具有三級(jí)調(diào)度時(shí)的調(diào)度隊(duì)列模型

16

三、選擇調(diào)度方式和算法的若干準(zhǔn)則

Somecriteriaforchoosingschedulingwayandalgorithm

一般和OS的類型和目標(biāo)有關(guān)

1面向用戶的準(zhǔn)則（User-orientedcriterion）

（注重滿足用戶需求）

1）周轉(zhuǎn)時(shí)間短（shortturnaroundtime）針對(duì)批處理系統(tǒng)

周轉(zhuǎn)時(shí)間（從作業(yè)提交系統(tǒng)到完成為止）包括：

□駐外存等待作業(yè)調(diào)度的時(shí)間；

□駐內(nèi)存等待進(jìn)程調(diào)度的時(shí)間；

□執(zhí)行時(shí)間；

□阻塞時(shí)間。

一后三步可能有多次。

17

計(jì)算機(jī)系統(tǒng)要求的是平均周轉(zhuǎn)時(shí)間最短。

平均周轉(zhuǎn)時(shí)間(meanturnaroundtime)為：

1〃

7一0覃

平均帶權(quán)周轉(zhuǎn)時(shí)間：作業(yè)的周轉(zhuǎn)時(shí)間T與系統(tǒng)為它提供

的實(shí)際服務(wù)時(shí)間Ts之比。

1」.T

帶權(quán)周轉(zhuǎn)時(shí)間越小越好。

18

2）響應(yīng)時(shí)間快（quickresponsetime）（針對(duì)分時(shí)系統(tǒng)）

響應(yīng)時(shí)間指從用戶通過(guò)鍵盤提交一個(gè)請(qǐng)求開始，直至系統(tǒng)

首次產(chǎn)生響應(yīng)（屏幕顯示結(jié)果）為止的時(shí)間。包括：

。輸入傳送到CPU的時(shí)間；

。處理的時(shí)間；

。結(jié)果回送到顯示器的時(shí)間。

3）截止時(shí)間的保證（guaranteeddeadline）（針對(duì)實(shí)時(shí)系統(tǒng)）

調(diào)度算法應(yīng)保證實(shí)時(shí)任務(wù)必須開始執(zhí)行的最遲時(shí)間和必須

完成的最遲時(shí)間。

4）優(yōu)先權(quán)原則（priorityprinciple）（適用于各種OS）

進(jìn)程調(diào)度中，往往還須選擇搶占調(diào)度方式，才能保證緊急

業(yè)得到及時(shí)處理。

19

2面向系統(tǒng)的準(zhǔn)則(System-orientedcriterion)

1)系統(tǒng)吞吐量高(highsystemthroughput)(對(duì)批處理OS)

-與批處理作業(yè)的平均長(zhǎng)度有密切關(guān)系。

2)處理機(jī)利用率好(goodprocessorutilization)(主要對(duì)大、

中型機(jī)多用戶系統(tǒng)一由于CPU價(jià)格昂貴)

3)各類資源平衡利用(balanceduseofvariousresource)

調(diào)度算法最優(yōu)準(zhǔn)四

最大的CPU利用率最短的等待時(shí)間

?最大的吞吐量最短的響應(yīng)時(shí)間

?最短的周轉(zhuǎn)時(shí)間最公平

20

§3.2調(diào)度算法SchedulingAlgorithm）

調(diào)度實(shí)質(zhì)是一種資源分配。（如作業(yè)調(diào)度可看成是內(nèi)存的

分配、進(jìn)程調(diào)度看成是CPU的分配）

調(diào)度算法：由系統(tǒng)資源分配策略所規(guī)定的資源分配算法。

一、先來(lái)先服務(wù)和短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法（First-Come-

First-ServedandShortestJobFirstschedulingalgorithm）

1、先來(lái)先服務(wù)（FCFS）調(diào)度算法

思想：每次調(diào)度總是選擇最先進(jìn)入隊(duì)列的作業(yè)（進(jìn)程）。

同時(shí)適用于作業(yè)調(diào)度和進(jìn)程調(diào)度。

FCFS應(yīng)用于進(jìn)程調(diào)度是一種非搶占的調(diào)度算法。他一

手點(diǎn)：簡(jiǎn)單，有利于長(zhǎng)作業(yè)（進(jìn)程）即CPU繁忙性作業(yè)。

21

開始執(zhí)帶權(quán)周

進(jìn)程名到達(dá)時(shí)間服務(wù)時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間

行時(shí)間轉(zhuǎn)時(shí)間

A010111

B.1■1001101'1001

C21：101102.100100'

3)

D:100，102202’1991.99

22

2、短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法（SJF、SPF）

（ShortestJobFirstschedulingalgorithm）

思想：從隊(duì)列中選擇估計(jì)運(yùn)行時(shí)間最短的作業(yè)（進(jìn)程），對(duì)它執(zhí)行

調(diào)度。

同時(shí)適用于作業(yè)調(diào)度和進(jìn)程調(diào)度。

該算法有利于短作業(yè)（進(jìn)程），可提高系統(tǒng)的吞吐量、降

低作業(yè)平均等待時(shí)間。

例：

缺點(diǎn)：1）不利于長(zhǎng)作業(yè)，“饑餓”；

2）未考慮作業(yè)（進(jìn)程）的緊迫程度；

3）長(zhǎng)、短只能是一個(gè)估算的時(shí)間，不一定確切。

23

“饑餓”狀態(tài)

■在預(yù)計(jì)時(shí)間內(nèi)，某個(gè)或某些進(jìn)程永遠(yuǎn)得不到完成工作的

機(jī)會(huì)，因?yàn)樗麄兯璧馁Y源總是被別的進(jìn)程占有或搶占。

這種狀況稱作“饑餓”或者“餓死”

(Starvation)o

■饑餓不同于死鎖，但與死鎖相近。死鎖進(jìn)程必定處

于阻塞狀態(tài)，饑餓進(jìn)程不一定被阻塞，可以在就緒

狀態(tài)。

■利用先來(lái)先服務(wù)的資源分配策略可以避免饑餓現(xiàn)象。

24

二、高優(yōu)先權(quán)優(yōu)先調(diào)度算法(Priorityschedulingalgorithm)

1、優(yōu)先權(quán)調(diào)度算法的類型

口優(yōu)先權(quán)調(diào)度算法是為了照顧緊迫性作業(yè)(進(jìn)程)。

□可用于作業(yè)調(diào)度和進(jìn)程調(diào)度。

□根據(jù)按優(yōu)先權(quán)調(diào)度時(shí)是否允許搶占，可分為兩種：

1)非搶占式(Nonnpreemptive)優(yōu)先權(quán)算法

主要用于批處理或要求不高的實(shí)時(shí)系統(tǒng)中。

2)搶占式優(yōu)先權(quán)調(diào)度算法

■當(dāng)就緒隊(duì)列中有新進(jìn)程出現(xiàn)時(shí)，應(yīng)比較新進(jìn)程和正運(yùn)行進(jìn)

程的優(yōu)先權(quán)。若小于、等于，則繼續(xù)運(yùn)行，否則，重新調(diào)

度、切換。

125

非搶占式優(yōu)先權(quán)算法一例

EG：進(jìn)程到達(dá)時(shí)間服務(wù)時(shí)間優(yōu)先權(quán)

Pi0.073

2.042

P2

P34.014

P45.041

■Gantt圖

07111516

平均周轉(zhuǎn)時(shí)間=((7?0)+(15?2)+(16?4)+(11?5))/4=8.5

26

搶占式優(yōu)先權(quán)算法一例

EG：進(jìn)程到達(dá)時(shí)間服務(wù)時(shí)間優(yōu)先權(quán)

Pi0.073

2.042

P2

P34.014

P45.041

■Gantt圖

Pi

PPP2P3

2|4,

0259101516

平均周轉(zhuǎn)時(shí)間=((15-0)+(10-2)+(16-4)+(9-5))/4=9.75

27

練習(xí)

5個(gè)進(jìn)程Pi，P2,P3,P4,P5,見表，規(guī)定進(jìn)程優(yōu)先數(shù)越小，優(yōu)先級(jí)越

高，試描述在采用下述調(diào)度算法時(shí)各個(gè)進(jìn)程運(yùn)行過(guò)程，并計(jì)算采用每

種算法時(shí)進(jìn)程平均周轉(zhuǎn)時(shí)間。假設(shè)忽略進(jìn)程的調(diào)度時(shí)間。

1）先來(lái)先服務(wù)調(diào)度算法；2）短進(jìn)程優(yōu)先調(diào)度算法；

3）非剝奪式優(yōu)先級(jí)調(diào)度算法；4）剝奪式優(yōu)先級(jí)調(diào)度算法。

進(jìn)程創(chuàng)建時(shí)刻ms運(yùn)行時(shí)間ms優(yōu)先數(shù)

P]035

263

p2

P3441

P4654

P5822

28

2優(yōu)先權(quán)的類型(Thetypeofpriority)：

有兩種類型的優(yōu)先權(quán)一靜態(tài)優(yōu)先權(quán)和動(dòng)態(tài)優(yōu)先權(quán)。

1)靜態(tài)優(yōu)先權(quán)(staticpriority)：優(yōu)先權(quán)在創(chuàng)建進(jìn)程時(shí)就確

定好，且在進(jìn)程的整個(gè)運(yùn)行期間保持不變。

優(yōu)先權(quán)常用某范圍內(nèi)的整數(shù)表示，又稱優(yōu)先數(shù)。UNIX系

統(tǒng)中，整數(shù)值越小，優(yōu)先級(jí)越高。又如：

確定進(jìn)程優(yōu)先數(shù)的依據(jù)：

?進(jìn)程類型：通常系統(tǒng)進(jìn)程的優(yōu)先權(quán)高于用戶進(jìn)程；

?對(duì)資源的需求：需求越少，優(yōu)先權(quán)越高；

?用戶要求：緊迫程度、交費(fèi)多少等。

優(yōu)點(diǎn)：簡(jiǎn)單。

缺點(diǎn)：出現(xiàn)“饑餓”現(xiàn)象。

29

2）動(dòng)態(tài)優(yōu)先權(quán)（dynamicpriority）：優(yōu)先權(quán)在創(chuàng)建進(jìn)程時(shí)規(guī)定,

但可以隨著進(jìn)程的運(yùn)行而改變。

3高響應(yīng)比優(yōu)先調(diào)度算法（HighestResponseRatioFirst

Schedulingalgorithm）

對(duì)每一個(gè)作業(yè)（進(jìn)程）計(jì)算一個(gè)優(yōu)先數(shù)，稱為響應(yīng)比。挑

選響應(yīng)比高的進(jìn)行調(diào)度。（短作業(yè)與優(yōu)先權(quán)調(diào)度的組合）

優(yōu)先權(quán)的變化規(guī)律可描述為：

D等待時(shí)間+要求服務(wù)時(shí)間響應(yīng)時(shí)間

K---------------------------------

夕一要求服務(wù)時(shí)間—要求服務(wù)時(shí)間

例如

30

■如等待時(shí)間相同，則要求服務(wù)時(shí)間愈短，優(yōu)先權(quán)愈高一SPF。

■如要求服務(wù)時(shí)間相同，優(yōu)先權(quán)決定于等待時(shí)間一FCFS。

■長(zhǎng)作業(yè)，等待一定時(shí)間后，則響應(yīng)比增加，利于調(diào)度。

，每次調(diào)度，計(jì)算響應(yīng)比，增大了系統(tǒng)開銷。

31

三、基于時(shí)間片輪轉(zhuǎn)調(diào)度算法(只應(yīng)用于進(jìn)程調(diào)度)Round-

robinschedulingalgorithmbasedontime-slice

1時(shí)間片輪轉(zhuǎn)法(time-sliceRound-robinmethod)

1)思想：和分時(shí)系統(tǒng)類似。翳所有的就緒進(jìn)程按先來(lái)先服務(wù)的

原則排成隊(duì)列，每次調(diào)度隊(duì)首進(jìn)程，執(zhí)行一個(gè)時(shí)間片后，將

其排入隊(duì)尾，再重新調(diào)度。例如：

2)時(shí)間片大小的確定(Determinationoftime-slicesize)

口q過(guò)長(zhǎng)large—＞退化為FCFS算法，進(jìn)程在一個(gè)時(shí)間片內(nèi)

都執(zhí)行完，響應(yīng)時(shí)間長(zhǎng)。

□q過(guò)短small一〉用戶的一次請(qǐng)求需要多個(gè)時(shí)間片才能處

理完，上下文切換次數(shù)增加，響應(yīng)時(shí)間長(zhǎng)。

根據(jù)系統(tǒng)的處理能力，應(yīng)讓用戶鍵入的常用命令在一個(gè)時(shí)間片內(nèi)

I完。時(shí)間片的大小從幾ms到幾百ms,通?？勺層脩舻?/p>

6?80%的作業(yè)在一個(gè)時(shí)間片內(nèi)完成。32

現(xiàn)有5個(gè)進(jìn)程，需要運(yùn)行的時(shí)間分別為(4,3,4,2,4),那么在

時(shí)間片q=l和q=4的情況下，諸進(jìn)程的運(yùn)行情況如下圖所示:

33

2多級(jí)反饋隊(duì)列調(diào)度算法(multi-levelfeedbackqueue

schedulingalgorithm)

口基本思想：

多級(jí)反饋隊(duì)列調(diào)度算法是時(shí)間片輪轉(zhuǎn)算法和優(yōu)先級(jí)調(diào)

度算法的綜合和發(fā)展，動(dòng)態(tài)調(diào)整進(jìn)程優(yōu)先級(jí)和時(shí)間片大小

,是目前公認(rèn)的一種較好的進(jìn)程調(diào)度算法。

設(shè)置多個(gè)就緒隊(duì)列；

□各隊(duì)列優(yōu)先級(jí)不一樣；

分配的時(shí)間片也不同，高優(yōu)先權(quán)隊(duì)列進(jìn)程時(shí)間片較小。

34

Thestepsofmulti-levelfeedbackqueueschedulingalgorithm

(1)在選取進(jìn)程時(shí)，短時(shí)間片

選取高優(yōu)先權(quán)隊(duì)列里的

進(jìn)程。優(yōu)先級(jí)調(diào)度按

照FCFS分配給相應(yīng)的時(shí)

間片。時(shí)間片輪轉(zhuǎn)

(2)進(jìn)程使用完時(shí)間片后,

進(jìn)入低一級(jí)優(yōu)先權(quán)隊(duì)列，

動(dòng)態(tài)優(yōu)先權(quán)、不等時(shí)間片

隊(duì)列n按RR算法調(diào)度執(zhí)行。

長(zhǎng)時(shí)間片

(3)當(dāng)高優(yōu)先權(quán)隊(duì)列里沒(méi)

有進(jìn)程時(shí)，才調(diào)度低優(yōu)先

權(quán)隊(duì)列進(jìn)程。

進(jìn)程創(chuàng)建后進(jìn)入最高優(yōu)先權(quán)隊(duì)列，搶占低優(yōu)先權(quán)進(jìn)程

35

多級(jí)反饋隊(duì)列調(diào)度算法的性能

Theperformanceofmulti-levelfeedbackqueue

多級(jí)反饋隊(duì)列調(diào)度算法具有較好的性能，能較好地滿足各種類型用戶

的需要：

■對(duì)于終端型作業(yè)用戶：一般終端型作業(yè)較小，通?？稍诘谝魂?duì)列中的一

個(gè)時(shí)間片內(nèi)完成，有較好的響應(yīng)時(shí)間。

■對(duì)短批處理作業(yè)用戶：批處理作業(yè)一開始也是送入第一隊(duì)列，或一個(gè)時(shí)

間片完成，或進(jìn)入第二、第三隊(duì)列，在某個(gè)時(shí)間片完成，仍然有較短的響

應(yīng)時(shí)間。

■對(duì)長(zhǎng)批處理作業(yè)用戶：依次在各隊(duì)列中運(yùn)行，直到最后一個(gè)隊(duì)列。而最

后一個(gè)隊(duì)列常用時(shí)間片輪轉(zhuǎn)法，也可以較及時(shí)的得到處理。

36

幾種常見調(diào)度算法的比較

FCFSRRSJFHRRFMFQ

選擇依捌Max[w]常量Min[s]Max[(w+s)/s]

非搶占非搶占

調(diào)度方式非搶占搶占搶占

搶占搶占

時(shí)間片小，

吞吐量不突出高高不突出

可能變低

短進(jìn)程提供

短進(jìn)程（作業(yè)）

響應(yīng)時(shí)間不突出良好的響應(yīng)較好不突出

響應(yīng)時(shí)間好

時(shí)間

開銷最小低可能高可能高可能高

不利于短不利于長(zhǎng)作可能偏愛(ài)I/O

對(duì)進(jìn)程作用公平對(duì)待良好的均衡

作業(yè)業(yè)（進(jìn)程）繁忙型作業(yè)

“饑餓”問(wèn)題無(wú)無(wú)可能無(wú)可能

37

四、彩票調(diào)度算法(lotteryschedulingalgorithm)

基本思想：為進(jìn)程發(fā)放針對(duì)系統(tǒng)各種資源(如CPU

時(shí)間)的彩票。當(dāng)調(diào)度程序需作出決策時(shí)，隨機(jī)選擇一

張彩票，持有該彩票的進(jìn)程將獲得系統(tǒng)資源。

如CPU調(diào)度，系統(tǒng)可每秒種抽50次彩票，每次的中

獎(jiǎng)?wù)攉@得20ms的運(yùn)行時(shí)間。

對(duì)于重要的進(jìn)程，可被給予更多的額外彩票，以增

加其中獎(jiǎng)機(jī)會(huì)。

38

§3.3實(shí)時(shí)系統(tǒng)中的調(diào)度

Real-timeScheduling

一、實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件(Thebasicconditionsto

implementreal-timescheduling)

實(shí)時(shí)調(diào)度必須滿足實(shí)時(shí)任務(wù)對(duì)截止時(shí)間的要求，因此實(shí)時(shí)

系統(tǒng)必須：

1提供必要的調(diào)度信息：

就緒時(shí)間(readytime);

開始和完成截止時(shí)間(beginandenddeadline);

處理時(shí)間(processingtime);

資源要求(resourcerequirement);

——,優(yōu)先級(jí)(priority)。

39

2.系統(tǒng)處理能力(Strongsystemprocessingability)

口采用單處理機(jī)系統(tǒng)，但須增強(qiáng)其處理能力，以顯著地減

少對(duì)每一個(gè)任務(wù)的處理時(shí)間；

□是采用多處理機(jī)系統(tǒng)。

3.米川搶占式調(diào)度方式(Takepreemptiveschedulingmechanism)

4.具有快速切；(quickswitchingmechanism)

e對(duì)外部中斷的快速響應(yīng)能力。

e快速的任務(wù)分派能力。

40

二、實(shí)時(shí)調(diào)度算法(real-timeschedulingAlgorithm)

1、非搶占式調(diào)度算法

時(shí)間片輪轉(zhuǎn)調(diào)度算法：響應(yīng)時(shí)間以秒為級(jí)別，只適合于

一般實(shí)時(shí)信息處理系統(tǒng)

口非搶占優(yōu)先權(quán)調(diào)度算法：響應(yīng)時(shí)間可做到以秒或百毫秒

為級(jí)別。適應(yīng)于要求不高的實(shí)時(shí)控制系統(tǒng)。

2、搶占式調(diào)度算法

□基于時(shí)鐘中斷搶占的優(yōu)先權(quán)調(diào)度算法：響應(yīng)時(shí)間可做到

幾十毫秒至幾毫秒。適合大多數(shù)實(shí)時(shí)系統(tǒng)。

□立即搶占的優(yōu)先權(quán)調(diào)度：一旦外部中斷出現(xiàn)，只要當(dāng)前

任務(wù)未處于臨界區(qū)，即能被剝奪處理機(jī)，響應(yīng)時(shí)間可做到

「幾毫秒至100微秒。

41

實(shí)時(shí)進(jìn)程要求調(diào)度調(diào)度實(shí)時(shí)進(jìn)程運(yùn)行實(shí)時(shí)進(jìn)程請(qǐng)求調(diào)度時(shí)鐘中斷到來(lái)時(shí)

1111

1111

,H____________VV_______________

進(jìn)程1進(jìn)程2進(jìn)程“實(shí)時(shí)進(jìn)程當(dāng)前進(jìn)程實(shí)時(shí)進(jìn)程

卜?調(diào)度時(shí)間―

<---------------調(diào)度時(shí)間-----------------A

（c）基于時(shí)鐘中斷搶占的優(yōu)先權(quán)搶占調(diào)度

（。）非搶占輪轉(zhuǎn)調(diào)度

實(shí)時(shí)進(jìn)程請(qǐng)求調(diào)度當(dāng)前進(jìn)程運(yùn)行完成實(shí)時(shí)等程請(qǐng)求調(diào)度1實(shí)時(shí)進(jìn)程槍占當(dāng)前

11

11'進(jìn)程，并立即執(zhí)行

,V[_________

當(dāng)前進(jìn)程實(shí)時(shí)進(jìn)程當(dāng)前進(jìn)程實(shí)時(shí)進(jìn)程

<-----調(diào)度時(shí)間一A--調(diào)度時(shí)間+

@）非搶占優(yōu)先權(quán)調(diào)度M）立即搶占的優(yōu)先權(quán)調(diào)度

圖3-5實(shí)時(shí)進(jìn)程調(diào)度

42

二、常用的幾種實(shí)時(shí)調(diào)度算法(Severalcommonreal-

timeschedulingAlgorithm)

常用的幾種實(shí)時(shí)調(diào)度算法，均基于任務(wù)的優(yōu)先權(quán)，根據(jù)確

定優(yōu)先級(jí)方法的不同形成了不同的實(shí)時(shí)調(diào)度算法。

1.最早截止時(shí)間優(yōu)先EDF(EarliestDeadlineFirst)算法(根

據(jù)任務(wù)的開始截止時(shí)間確定優(yōu)先級(jí))

該算法即可用于搶占式調(diào)度，也可用于非搶占式調(diào)度。

1342

開始截止時(shí)間

任務(wù)執(zhí)行11I3|42

-iI41一

任務(wù)到達(dá)

1234

圖3-6EDF算法用于非搶占調(diào)度方式

43

2.最低松弛度優(yōu)先LLF(LeastLaxityFirst)算法

該算法根據(jù)任務(wù)緊急(或松弛)的程度，確定任務(wù)優(yōu)

先級(jí)。任務(wù)的緊急程度愈高，為該任務(wù)所賦予的優(yōu)先級(jí)

就愈高，以使之優(yōu)先執(zhí)行。主要用于可搶占調(diào)度方式。

與任務(wù)的完成截止時(shí)間密切相關(guān)。

任務(wù)的松弛度=必須完成時(shí)間■其本身的運(yùn)行時(shí)間■當(dāng)前時(shí)間

系統(tǒng)中有一個(gè)按松弛度排序的實(shí)時(shí)任務(wù)就緒隊(duì)列，

松弛度最低的任務(wù)排在最前面，調(diào)度程序總是選擇就緒

隊(duì)列中的隊(duì)首任務(wù)執(zhí)行。

A]A2A3A4A5A6A7A8

020406080100120140160

0任務(wù)A每20ms執(zhí)行

B2一次，執(zhí)行時(shí)間為

圖3?7A和B任務(wù)每次必須完成I10ms；住務(wù)B每

A2的臚，A4松弛度減至0(50ms執(zhí)行一次，執(zhí)2

50ms完"40ms-10msJ20(100-10-70),A4搶【行時(shí)間為25ms。

A

68

01020304050-607080

￡1=0

B/20)B"5)B2(l5)B2(l0)

圖3-8利用LLF算法進(jìn)行調(diào)度的情況

45

§3.4多處理機(jī)中的調(diào)度

SchedulinginMulti-ProcessorSystem

/提高計(jì)算機(jī)系統(tǒng)性能的主要途徑有兩條：

?提高構(gòu)成計(jì)算機(jī)的元器件的運(yùn)行速度;

?改進(jìn)計(jì)算機(jī)系統(tǒng)的體系結(jié)構(gòu)；

/20世紀(jì)70年代開始出現(xiàn)的多處理器系統(tǒng)，可

以實(shí)現(xiàn)對(duì)信息的高度并行處理，提高系統(tǒng)吞吐

量和可靠性。

46

-、多處理器系統(tǒng)的類型(ThetypeofMPS)

1.根據(jù)多處理器之間的耦合程度劃分

(1)緊密耦合(TightlyCoupted)MPS

通過(guò)高速總線或高速交叉開關(guān)互連多個(gè)處理器之間。它

們共享主存儲(chǔ)器系統(tǒng)和I/O設(shè)備，將主存劃分成若干能獨(dú)立訪

間的存儲(chǔ)器模塊，便于多個(gè)處理器同時(shí)對(duì)主存訪問(wèn)，系統(tǒng)中

所有資源由操作系統(tǒng)實(shí)施統(tǒng)一控制和管理。

(2)松散耦合(LooselyCoupled)MPS

通過(guò)通道或通信線路，來(lái)實(shí)現(xiàn)多臺(tái)計(jì)算機(jī)之間的互連。

每臺(tái)計(jì)算機(jī)都有自己的存儲(chǔ)器和I/O設(shè)備，配置OS管理本地

資源和在本地運(yùn)行的進(jìn)程。通過(guò)通信線路與其它計(jì)算機(jī)交換

信息，以及協(xié)調(diào)它們之間的工作。

47

2,根據(jù)所用處理器的相同與否劃分

(1)對(duì)稱多處理器系統(tǒng)SMPS(Symmetric

MultiProcessorSystem)。在系統(tǒng)中所包含的各處

理器單元，在功能和結(jié)構(gòu)上都是相同的，當(dāng)前的

絕大多數(shù)MPS都屬于SMP系統(tǒng)。

(2)非對(duì)稱多處理器系統(tǒng)。處理單元的功能和

結(jié)構(gòu)各不相同，其中只有一個(gè)主處理器，有多個(gè)

從處理器。

48

二、進(jìn)程分配方式（ProcessAssignmentWay）

1.對(duì)稱多處理器系統(tǒng)中的進(jìn)程分配方式

SMP系統(tǒng)中，把所有處理器作為一個(gè)處理池，由調(diào)度程

序，將任一個(gè)進(jìn)程分配給池中任一處理器。

1）靜態(tài)分配：進(jìn)程從開始到完成，被固定地分配到一臺(tái)處理

機(jī)上。每一臺(tái)處理機(jī)有自己的專用就緒隊(duì)列。

優(yōu)點(diǎn)：進(jìn)程調(diào)度簡(jiǎn)單、開銷小。

缺點(diǎn)：整個(gè)系統(tǒng)中各處理機(jī)忙、閑不均。

2）動(dòng)態(tài)分配：系統(tǒng)中僅設(shè)置一個(gè)公共就緒隊(duì)列，由所有處理

機(jī)共享。某一進(jìn)程可分配到任一臺(tái)處理機(jī)上運(yùn)行。某進(jìn)程在其

生命周期中可能會(huì)在多臺(tái)處理機(jī)上運(yùn)行。

優(yōu)點(diǎn)：各處理機(jī)使用平均。

缺點(diǎn)：調(diào)度的開銷較大（如對(duì)就緒隊(duì)列的使用、進(jìn)程切換

學(xué)的開銷等）。

49

2.非對(duì)稱多處理器系統(tǒng)中的進(jìn)程分配方式

非對(duì)稱MPS,OS大多是采用E—M(Master/Slave)

式OS,即OS的核心部分駐留在主機(jī)(master)上，從機(jī)

(slave)只是執(zhí)行用戶程序，進(jìn)程調(diào)度只由主機(jī)執(zhí)行。每

當(dāng)從機(jī)空閑時(shí)，請(qǐng)求主機(jī)為它分配進(jìn)程，主機(jī)便從一

公用的就緒隊(duì)列中(隊(duì)首)取下一個(gè)進(jìn)程分配。

優(yōu)點(diǎn)：系統(tǒng)處理比較簡(jiǎn)單。

缺點(diǎn)：主機(jī)是系統(tǒng)瓶頸。

克服缺點(diǎn)的方法：用多臺(tái)而非一臺(tái)處理機(jī)來(lái)管理各

個(gè)系統(tǒng)。

50

二、進(jìn)程（線程）調(diào)度方式（Process（thread）SchedulingWay）

1）自調(diào)度（Self6chedulingWay）：各個(gè)CPU采用一個(gè)公

共就緒隊(duì)列，每個(gè)處理機(jī)都可以從隊(duì)列中選擇適當(dāng)進(jìn)程

（采用FCFS、SPF等算法）來(lái)執(zhí)行。

□需要對(duì)就緒隊(duì)列進(jìn)行互斥訪問(wèn)控制。

是最常用的算法，實(shí)現(xiàn)時(shí)易于移植采用單處理機(jī)的調(diào)

度技術(shù)。

□優(yōu)點(diǎn)：

1）只要有工作，就不會(huì)有空閑處理機(jī)；

2）就緒隊(duì)列的組織，調(diào)度算法可延用單處理機(jī)系統(tǒng)中的

方法。

51

。缺點(diǎn)：

?瓶頸問(wèn)題（公共的就緒隊(duì)列形成瓶頸）；

?低效性（線程在運(yùn)行中可能會(huì)更換多個(gè)處理機(jī),

有些內(nèi)容如高速緩存中的信息丟失，需多次設(shè)

置）；

?線程切換頻繁（相互合作的進(jìn)程的同步關(guān)系難

以保證）

52

2）成組調(diào)度（GangScheduling）:將一^個(gè)進(jìn)程中的一^組

線程，分配到一組處理機(jī)上去執(zhí)行。

■優(yōu)點(diǎn)：1）合作的線（進(jìn)）程能并行執(zhí)行，則可減

小阻塞，從而減少切換。

2）每次調(diào)度解決一組線（進(jìn)）程的處理機(jī)分配，

可減少總的調(diào)度次數(shù)。

■成組調(diào)度可有兩種方式：

1）面向所有應(yīng)用程序平均分配處理機(jī)

2）面向所有線程平均分配處理機(jī)

第二種方式更合理、有效

53

3)專用處理機(jī)分酉己(DedicatedProcessorAssignment):

在一個(gè)應(yīng)用程序執(zhí)行期間，專門為該應(yīng)用程序

分配一組處理機(jī)，每一個(gè)線程一個(gè)。這組處理機(jī)供

該應(yīng)用程序?qū)Ｓ?，直到?yīng)用程序完成。

§3.5產(chǎn)生死鎖的原因和必要條件

Thereasonsandnecessaryconditionsforcreatingdeadlock

55

、死鎖(deadlock)

指多個(gè)進(jìn)程在運(yùn)行過(guò)程中因爭(zhēng)奪資源而造成的一種僵

局(deadly-Embrace),若無(wú)外力作用，這些進(jìn)程都將無(wú)法

向前推進(jìn)。

申請(qǐng)打印機(jī)申請(qǐng)掃描儀

申請(qǐng)掃槍必、請(qǐng)打印機(jī)

使用陛

釋放打印機(jī)’

釋放掃描儀釋放掃描儀

56

關(guān)于死鎖的一些結(jié)論

■參與死鎖的進(jìn)程最少是兩個(gè)

（兩個(gè)以上進(jìn)程才會(huì)出現(xiàn)死鎖）

■參與死鎖的進(jìn)程至少有兩個(gè)已經(jīng)占有資源

參與死鎖的所有進(jìn)程都在等待資源

■參與死鎖的進(jìn)程是當(dāng)前系統(tǒng)中所有進(jìn)程的子集

如果死鎖發(fā)生，會(huì)浪費(fèi)大量系統(tǒng)資源，甚至導(dǎo)

致系統(tǒng)崩潰

57

.、產(chǎn)生死鎖的原因(Thereasonsfordeadlockgenerating)

■競(jìng)爭(zhēng)資源(Resourcecompetition)

■進(jìn)程推進(jìn)順序非法(Illegalprocessproceeding)

1、競(jìng)爭(zhēng)資源中起死鎖(Resourcecompetitioncausesprocessdeadlock)

(不可避免)

■資源分類

操作系統(tǒng)管理著系統(tǒng)內(nèi)所有資源，它負(fù)責(zé)分配不同類

型的資源給進(jìn)程使用，系統(tǒng)中的資源可從不同角度進(jìn)行分

類。

58

■資源的分類

□是否可剝奪

■可剝奪資源(PreemptableResources)

可以從擁有它的進(jìn)程中剝奪而不會(huì)產(chǎn)生任何副作用的資源。

例：存儲(chǔ)器

■不可剝奪資源(NonpreemptableResources)

無(wú)法在不引起相關(guān)計(jì)算失敗的情況下把它從主進(jìn)程處剝奪的

資源。例：打印機(jī)

口是否臨時(shí)性

-永久性資源：可順序重復(fù)使用權(quán)的資源(如打印機(jī))

■臨時(shí)性資源：由某個(gè)進(jìn)程產(chǎn)生，被另一個(gè)進(jìn)程使用一短暫時(shí)

間后便成為無(wú)用的資源。

59

?競(jìng)爭(zhēng)非剝奪性資源：可能導(dǎo)致死鎖。如Pl、P2都需要R1、

R2,在某一時(shí)刻資源申請(qǐng)、分配情況如圖：

圖1I/O設(shè)備共享時(shí)死鎖圖2進(jìn)程間通信時(shí)死鎖

?競(jìng)爭(zhēng)臨時(shí)性資源

■競(jìng)爭(zhēng)臨時(shí)性資源也可引起死鎖。圖2示出進(jìn)程通信形成死鎖

情況。

60

■2、進(jìn)程推進(jìn)順序不當(dāng)引進(jìn)死鎖（進(jìn)程并發(fā)的異步性）

Illegalprocessproceedingcausesprocessdeadlock

無(wú)法控制進(jìn)程之間的推進(jìn)順序（固有的），因

此死鎖是基本特征的“副作用”；可能是進(jìn)程按下

述兩種順序向前推進(jìn)。

□進(jìn)程推進(jìn)順序合法

□推進(jìn)順序非法

61

狀態(tài):就緒執(zhí)行阻塞

62

P2Rel(R2)

P2Rel(Rl)

P2Req(Rl)

P2Req(R2)

P1Req(R1)PlReq(R2)PlRel(R1)PlRel(R2)

1、2、3三條曲線的順序合法，4的順序非法

圖3-10進(jìn)程推進(jìn)順序?qū)λ梨i的影響

63

二、產(chǎn)生死鎖的必要條件(TheNecessaryConditionof

DeadlockGenerating)Coffman條件：

在同時(shí)具備下列四個(gè)必要條件時(shí)，就會(huì)產(chǎn)生死鎖：

1.互斥條件(MutualExclusioncondition)

指進(jìn)程對(duì)所分配到的資源進(jìn)行排它性使用。

2.請(qǐng)求和保持條件(Requestandholdcondition)

進(jìn)程已經(jīng)保持了至少一個(gè)資源，但又提出了新的資源

要求。當(dāng)不能滿足而阻塞時(shí)，保持原資源不釋放。

3.不剝奪條件(Nonpreemptivecondition)

進(jìn)程已獲得的資源，在未使用完之前，不能被剝奪，

只能在使用完時(shí)自己釋放。

4.環(huán)路等待條件(Loopwaitingcondition)

在發(fā)生死鎖時(shí)，必然存在一個(gè)進(jìn)程一資源的環(huán)形鏈。

環(huán)路中的進(jìn)程形成等待鏈。

64

二、處理死鎖的基本方法(BasicMethodsofDeadlock

Processing)

■1預(yù)防死鎖(DeadlockPrevention)：設(shè)置某些條件，破壞產(chǎn)生

死鎖的一個(gè)或幾個(gè)必要條件。

□優(yōu)點(diǎn)：實(shí)現(xiàn)簡(jiǎn)單；

□缺點(diǎn)：條件嚴(yán)格，降低系統(tǒng)資源利用率和吞吐量。

■2避免死鎖(DeadlockAvoidance)：不事先采取各種限制措施

去破壞產(chǎn)生死鎖的條件，在資源的動(dòng)態(tài)分配過(guò)程中，防止系

統(tǒng)進(jìn)入不安全狀態(tài)，以避免發(fā)生死鎖。

□優(yōu)點(diǎn)：條件較弱，較高資源利用率和吞吐量。

□缺點(diǎn)：實(shí)現(xiàn)難.

65

■3檢測(cè)死鎖(DeadlockDetectionandRelieving)：不采取限制

措施，不檢查系統(tǒng)是否已進(jìn)入不安全區(qū)，允許發(fā)生死鎖，但

可通過(guò)系統(tǒng)設(shè)置的檢測(cè)機(jī)構(gòu)及時(shí)檢測(cè)出，并精確的確定與死

鎖相關(guān)的進(jìn)程和資源，結(jié)合相關(guān)機(jī)制，將死鎖清除。

■4.解除死鎖(DeadlockRelieving)：與檢測(cè)配套的一種措施，

用于將進(jìn)程從死鎖狀態(tài)下解脫出來(lái)，撤銷或掛起一些進(jìn)程，

以便回收一些資源。

66

§3.6死鎖的預(yù)防和避免

DeadlockPreventionandAvoidance

一\死鎖的預(yù)防(DeadlockPrevention)

因?yàn)榈谝粋€(gè)必要條件“互斥條件”是設(shè)備的固有屬性決定

的，所以只能設(shè)法破壞另三個(gè)必要條件。

1摒棄“請(qǐng)求和保持”條件：

資源靜態(tài)分配：進(jìn)程運(yùn)行前一次性滿足它的全部資源請(qǐng)求，否

則，全部不分配。在運(yùn)行過(guò)程中，進(jìn)程不再請(qǐng)求資源。因此不

再占有某些資源去等待另外資源。

缺點(diǎn)：1)進(jìn)程在整個(gè)生命周期一直占用資源，減低利用率;

2)進(jìn)程延遲運(yùn)行；

67

2摒棄“不剝奪”條件

思想：某進(jìn)程申請(qǐng)新資源不能滿足時(shí)，釋放已占用的所有資源，

以后需要時(shí)再申請(qǐng)。意味著：進(jìn)程已經(jīng)占有的資源，在運(yùn)行過(guò)程

中可能會(huì)暫時(shí)的釋放，也可認(rèn)為是被剝奪了。

缺點(diǎn)：造成前段工作的失效。反復(fù)地申請(qǐng)、釋放資源使進(jìn)程的執(zhí)

行推遲；前后兩次運(yùn)行信息不連續(xù)。

3摒棄“環(huán)路等待”條件(預(yù)防死鎖較有效的方法)

有序資源分配方法：所有資源按類型進(jìn)行線性排隊(duì)，并賦予不同

的序號(hào)。進(jìn)程對(duì)資源的請(qǐng)求必須按資源序號(hào)遞增的次序提出。

如:m種資源，R1<R2<……<Rm,若Pi保持了Ri,則它只能

申請(qǐng)比Ri級(jí)別更高的Rj(RivRj),釋放時(shí)，Rj先于Ri釋放。

68

缺點(diǎn)：

>1）資源序號(hào)應(yīng)相對(duì)穩(wěn)定，限制了新設(shè)備類型的增加；

>2）進(jìn)程使用資源的順序與系統(tǒng)規(guī)定的順序不一致；例如：

打印機(jī)v磁帶機(jī)（系統(tǒng)規(guī)定）。P的過(guò)程先申請(qǐng)磁帶機(jī)，再申請(qǐng)

打印機(jī)。而申請(qǐng)過(guò)程中P先申請(qǐng)到打印機(jī)，再等待磁帶機(jī)，導(dǎo)

致打印機(jī)長(zhǎng)期閑置。

A3）對(duì)用戶增加了限制。

總之，這一做法的困難在于如何給資源類確定各方面都較

滿意的序號(hào)。

69

哲學(xué)家就餐問(wèn)題的死鎖及處理辦法

假如五個(gè)同時(shí)饑餓而各自拿起左邊的筷子時(shí)，當(dāng)他們

試圖去拿右邊筷子時(shí)，都將因無(wú)筷子可拿而無(wú)限期地等待。

對(duì)于這樣的死鎖問(wèn)題可采取以下幾種解決方法：

(1)至多只允許四個(gè)哲學(xué)家同時(shí)進(jìn)餐。

(2)僅當(dāng)哲學(xué)家的左、右兩支筷子均可用時(shí)，才允許

他拿起筷子進(jìn)餐。

(3)規(guī)定奇數(shù)號(hào)哲學(xué)家先拿起他左邊的筷子，再拿起

他右邊的筷子；而偶數(shù)號(hào)哲學(xué)家則相反。

請(qǐng)問(wèn)：上述三種辦法是怎樣防止死鎖的?

70

二、死鎖的避免(DeadlockAvoidance)

避免死鎖中，可把系統(tǒng)狀態(tài)分為安全、不安全。只要

使系統(tǒng)處于安全狀態(tài)，則可避免死鎖。

安全狀態(tài)(SafetyState)：系統(tǒng)能按某種順序(如

<P1,P2,…，Pn>)為每個(gè)進(jìn)程分配其所需資源，使每個(gè)進(jìn)

程都可順序完成，則稱此時(shí)系統(tǒng)處于安全狀態(tài)。

進(jìn)程序列PLP2,…，Pn稱為安全序列。

若不存在安全序列，則稱系統(tǒng)處于不安全狀態(tài)。

不安全狀態(tài)有可能導(dǎo)致死鎖，安全狀態(tài)則可避免死鎖。

因此，使系統(tǒng)不進(jìn)入不安全狀態(tài)則可避免死鎖。

171

安全狀態(tài)與不安全狀態(tài)

安全狀態(tài)不安全狀態(tài)

死鎖狀態(tài)

72

銀行家算法

了解死鎖的實(shí)質(zhì)

73

二、死鎖的避免

銀行家算法：

■算法描述

口銀行家擁有一筆周轉(zhuǎn)資金

□客戶要求分期貸款，如果客戶能夠得到

各期貸款，就一定能夠歸還貸款，否則

就一定不能歸還貸款

銀行家應(yīng)謹(jǐn)慎的貸款，防止出現(xiàn)壞帳

74

二、死鎖的避免

銀行家算法：

■用銀行家算法避免死鎖

□操作系統(tǒng)（銀行家）

□操作系統(tǒng)管理的資源（周轉(zhuǎn)資金）

口進(jìn)程（要求貸款的客戶）

75

二、死鎖的避免

銀行家算法：?jiǎn)畏N資源的銀行家算法

4個(gè)客戶每個(gè)都有一個(gè)貸款額度

已使用最大已使用最大已使用最大

名字J|名字||名字||

6

Andy06Andy16Andy1

Barbara05Barbara15Barbara25

Marvin04Marvin24Marvin24

Suzanne07Suzanne47Suzanne47

可用：10可用：2可用：1

(a)(b)⑹

76

二、死鎖的避免

銀行家算法：?jiǎn)畏N資源的銀行家算法

■對(duì)每個(gè)請(qǐng)求進(jìn)行檢查，是否會(huì)導(dǎo)致不安全狀態(tài)。

若是，則不滿足該請(qǐng)求；否則便滿足

■檢查狀態(tài)是否安全的方法是看他是否有足夠的

資源滿足一個(gè)距最大需求最近的客戶，如此反

復(fù)下去。如果所有投資最終都被收回，則該狀

態(tài)是安全的，最初的請(qǐng)求可以批準(zhǔn)

77

、死鎖的避免

銀行家算法：?jiǎn)畏N資源的銀行家算法

已使用最大已使用最大已使用最大

名字I(名字11名字

Andy06Andy16Andy16

一個(gè)狀態(tài)被稱為Barbara05Barbara15Barbara25

Marvin04Marvin2kMarvin24

是安全狀態(tài)Suzanne07Suzanne47Suzanne47

可用：10可用：2可用：1

(a)(b)(c)

/條件是存在一個(gè)狀態(tài)序列能夠使所有的客戶

均得到其所有的貸款。

/圖示b狀態(tài)是安全的，以使Marvin運(yùn)行結(jié)束,

釋放所有的4個(gè)單位資金。這樣下去便可滿足

Suzanna或Barbara的請(qǐng)求。

78

、死鎖的避免

銀行家算法：?jiǎn)畏N資源的銀行家算法

已使用最大已使用最大已使用最大

名字I(名字11名字

Andy06