It計算機課件 操作系統(tǒng)第三章

操作系統(tǒng)

第三章處理機調度與死鎖

3-1處理機調度的基本概念

3?2調度算法

3.3實時調度

3?4多處理機系統(tǒng)中的調度

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

3?6預防死鎖的方法

3?7死鎖的檢測與解除

3.1處理機調度的基本概念

■處理機管理的工作是對CPU資源進行

合理的分配使用，以提高處理機利用

率，并使各用戶公平地得到處理機資

源。分配處理機的任務是由處理機調

度程序完成的。

處理機管理

一個作業(yè)被提交后，必須經(jīng)過處

理機調度后得到處理機的使用權后才能

開始執(zhí)行。

對批處理作業(yè)，要經(jīng)歷“作業(yè)調

度”（高級調度）和“進程調度”（低

級調度）后才能獲得處理機；對終端型

作業(yè)，要進程調度后才能獲得獲得處理

機并執(zhí)行。

限理機管理

作業(yè)調度的功能

I■作業(yè)調度的主要任務是完成作業(yè)從后

*備狀態(tài)到執(zhí)行狀態(tài)和從執(zhí)行狀態(tài)到完

1成狀態(tài)的轉變。

-作業(yè)調度功能：

■1.記錄已進入系統(tǒng)的各作業(yè)的情況

(JCB,JobControlBlock)；

■2.按一定的調度算法，從后備作業(yè)中

選擇一個或幾個作業(yè)進入系統(tǒng)內存；

■3.為被選中的作業(yè)創(chuàng)建進程，并且為

其申請系統(tǒng)資源；

■4.作業(yè)結束后作善后處理工作?！蔡幚頇C管理

作業(yè)控制塊(JCB,JobControlBlock)

作業(yè)名每個作業(yè)進入系

估計運行時間

最迅總成時間統(tǒng)時由系統(tǒng)為其

資哪要求要求的內存量建立一個作業(yè)控

要求外設的類型及臺數(shù)制塊

要求文件量和輸出量JCB(Job

進入系統(tǒng)的時間ControlBlock),

開始運行的時間它是存放作業(yè)控

資源使用情況已運行的時間

內存地址制和管理信息的

外設臺號數(shù)據(jù)結構，主要

類型控制方式

作業(yè)類型信息見左圖。

優(yōu)先級

狀態(tài)處理機管理

出

備作業(yè)隊列空

是分配資源

按調度算法從作

業(yè)中選出一作業(yè)調用進程管理程序建

I立進程，進入就緒隊列

調用存儲、設備管理

程序，審核資源要求

放棄該否一進程調度

作業(yè)賁源要求能滿足?

作業(yè)調度和進程調度的過程

\局級、/H

組3M亂展逋度或長程調度;

又稱步

1高繪又稱為中程調度，目的是為了、

提高內存利用率和系統(tǒng)吞吐量。

2低i

將暫吐不能運行的進程調

3中級調

非搶占式：適用于批處理系統(tǒng)

搶占式：時間片原則，優(yōu)先權)

原則，短作業(yè)優(yōu)先/

機管理

二調度隊列模型

■僅有進程調度的調度隊列模型

分時系統(tǒng)正在執(zhí)行的進程可能出現(xiàn)完成、

用完時間片或阻塞三種情況。

時間片完

■具有高級和低級調度的調度隊列模型

I該模型具有兩級調度，并根據(jù)阻塞事件設置

多個阻塞隊列

■同時具有三級調度的調度隊列模型

三、選擇L作業(yè)的周轉時間:

包括

■1—Ti=tci-tsi

帶權周轉時間：平均帶權周轉時間：

_tj

Wi——-w=^Ewi

Lr

苗作業(yè)實際運行時間

3、截止麗的保證

4、優(yōu)先權準則處理機管理

面向系統(tǒng)的準則

工、系統(tǒng)吞吐量高

2、處理機利用率好

3、各類資源的平衡利用

處理機管理

32調度算法

*調度算法是指根據(jù)系統(tǒng)的資源分配

策略所規(guī)定的資源分配算法。

對于不同的系統(tǒng)和系統(tǒng)目標通常

采用不同的調度算法。這些算法有的適

用于作業(yè)調度，有的適用于進程調度，

有的兩者都適用。

處理機管理

、先來先服務和短作業(yè)(進程)優(yōu)先調度算法

先來先服務調度算法(FCFS)

作業(yè)來到的先后次序進行調度的換句話

說，調度程序每次選擇的作業(yè)是等待時間最

久的，而不管作業(yè)的運行時間的長短。

每次調度都是從后備作業(yè)隊列中，選

擇一個或多個最先進入該隊列的作業(yè)將其調

入內存，分配資源，創(chuàng)建進程，并進入就緒

隊列。

特點：優(yōu)點是實現(xiàn)簡單效率較低，有利王￡

作業(yè)，CPU繁忙型作業(yè)：處理機管理

進程到達服務開始執(zhí)完成周轉帶權周

名時間時間行時間時間時間轉時間

A010111

B110011011001

C21101102100100

D31001022021991.99

周轉時間=完成時間■提交時間，帶權周轉時間二周

轉時間/服務時間

■短作業(yè)（進程）優(yōu)先調度算法（SJF）

短作業(yè)（進程）優(yōu)先調度算法是從就緒隊

列中選出估計運行時間最短的進程，將處理機

分配給它，使其執(zhí)行到完成，或發(fā)生某事件而

被阻塞放棄處理機，再重新調度。

算法缺點：

1、對長作業(yè)不利；

2、未考慮作業(yè)的緊迫程度；

3、算法有可能做不到短作業(yè)優(yōu)先調頤理機/

進程名ABCDE平均

情況

到達時間01234

調度算屋、

服務時間43524

完成時間47121418

FCFS周轉時間461011149

帶權周轉時間1225.53.52.8

完成時間4918613

SJF周轉時間4816398

帶權周轉時間12.673.11.52.252.1

■先來先服務和短作業(yè)優(yōu)先算法都有

其片面性;先來先服務調度算法只

考慮作業(yè)的等待時間，而忽視了作

業(yè)的運行時間，短作業(yè)優(yōu)先算法則

相反，只考慮了作業(yè)的運行時間，

而忽視了作業(yè)的等待時間。

二，高優(yōu)先權(FPF)優(yōu)先調度算法

“最高優(yōu)先權作業(yè)調度算法,是從后備隊

列中選援若干個優(yōu)先權最高的作業(yè)，并裝入

內在運行；

最高優(yōu)先權進程調度算法，是把處理機

分配給就緒隊列中優(yōu)先權最高的進程，此時

可將該算法分成如下兩種：

1、非搶占式優(yōu)先權算法

2、搶占式優(yōu)先權調度算法處理機管理

1、非搶占式優(yōu)先權算法

裝統(tǒng)一旦將處埋機（CPU）分配給運行隊

列中優(yōu)先權最高的進程后，該進程便一直

執(zhí)行下去，直至完成或因發(fā)生某事件使該

進程放棄處理機時，系統(tǒng)方可將處理機分

配給另一個優(yōu)先權高的進程。這種調度算

法主要用于批處理系統(tǒng)中，也可用于某些

對實時性要求不嚴的實時系統(tǒng)中。Li、

:處理機管理

2、搶占式優(yōu)先權調度算法又稱可剝奪調度

■*算法的本質就是系統(tǒng)中當前運行的進程永

遠是可運行進程中優(yōu)先權最高的那個。

-在這種方式下，系統(tǒng)同樣是把處理機分配給

優(yōu)先權最高的進程，使之執(zhí)行。但是只要一

出現(xiàn)了另一個優(yōu)先權更高的進程時，調度程

序就暫停原最高優(yōu)先權進程的執(zhí)行，而將處

理機分配給新出現(xiàn)的優(yōu)先權最高的進%

剝奪當前進程的運行?！柑幚頇C管理

1因此，在采用這種調度算法時,每當出

I現(xiàn)一新的可運行進程,就將它和當前運

行進程進行優(yōu)先權比較，如果高于當前

進程，將觸發(fā)進程調度。

-這種方式的優(yōu)先權調度算法，能更好的

滿足緊迫進程的要求，故而常用于要求

比較嚴格的實時系統(tǒng)中，以及對性能要

求較高的批處理和分時系統(tǒng)中。廠i'

（處理機管理

優(yōu)先權類型：

靜態(tài)優(yōu)先權：進程在創(chuàng)建時確定，在進程

的整個運行期間保持不變；

確定進程優(yōu)先權的三個依據(jù)：進程類型、

進程對資源的要求、用戶要求

優(yōu)缺點：簡單易行，系統(tǒng)開銷??；不夠精

確，有可能出現(xiàn)優(yōu)先權低的作業(yè)長期沒有被調

度O

動態(tài)優(yōu)先權：在創(chuàng)建進程時所賦予的優(yōu)先

權可以隨進程的推進或隨其等待時間的增加而

改變，以便獲得更好的調度性能。

高響應比優(yōu)先調度算法：即動態(tài)改變

作業(yè)的優(yōu)先權，使作業(yè)的優(yōu)先級隨等待時

間的增長而以速度C提高，則長作業(yè)在

等待一定的時間后就會有機會得到處理機。

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

等待時間+要求服務時間

優(yōu)先權

要求服務時間

d等待時間+要求服務時間響應時間

響應比R=------------------------------=-------------

'要求服務時間要求服務時間

(1)如果作業(yè)的等待時間相同，則要求服

務的時間愈短，其優(yōu)先權愈高，因而該算法有

(2)當要求服務的時間相同時，作業(yè)的優(yōu)先權

決定于其等待時間，等待時間愈長，其優(yōu)先權

愈高，因而它實現(xiàn)的是先來先服務。

(3)對于長作業(yè)，作業(yè)的優(yōu)先級可以隨等

待時間的增加而提高，當其等待時間足夠長時，

其優(yōu)先級便可升到很高，從而也可獲彳I處理心

:處理機管理

三、基于時間片的輪轉調度算法

［時間片輪轉法

*~具體實現(xiàn):

每次調度時，把CPU分配給隊首進程，

并令其執(zhí)行一個時間片。

當時間片用完后，由計時器發(fā)出中斷

請求，調度程序便終止該進程的執(zhí)行，并將

其放在就緒隊列末尾。

然后，再把處理機分配給就緒隊列甲f

新的隊首進程。塞理機管理

■多級反饋隊列調度算法

上施過程：

iH設置多個就緒隊列T時為各個隊列賦予不

同的優(yōu)先級。第一個隊列的優(yōu)先級最高，第

二個隊列次之，其余各隊列的優(yōu)先權逐個降

低。該算法賦予各隊列中進程執(zhí)行時間片的

大小也不同。優(yōu)先權越高，執(zhí)行的時間片就

越短。例如，第二個隊列的時間片要比第一

個隊列的時間片長一倍，……，第弁1個隊

列的時間片要比第i個隊列的時間片長二Z

處理機管理

2、當一個新進程進入內存后，首先

放入第一隊列的末尾，按FCFS原則排隊等待

調度。當輪到該進程執(zhí)行時，若在時間片內

執(zhí)行完，則準備撤出系統(tǒng)。否則便將該進程

轉入第二隊列的末尾，再同樣按FCFS原則等

待調度執(zhí)行……

當長作業(yè)（進程）從第一隊列依次降

到第n隊列后，在第n隊列中便采取按時間片

輪轉的方式運行。

3、僅當?shù)谝魂犃锌臻e時，調度程序才調

度第二隊列的進程，僅當?shù)?—(i?l)隊

列均為空時，才調度第i隊列中的進程運

行。如果處理機正在第i隊列中為某進程

服務時，又有新進程進入優(yōu)先權較高的

隊歹U(第1中的任何一個隊列)，則

此時新進程將搶占正在運行進程的處理

機，即由調度程序把正在運行的進程放

回到第i隊列的末尾，把處理機分配給新

到的高優(yōu)先權進程。

SI

S3

圖3.3多級反饋隊列調度算法

處理機管理

■多級反饋隊列調度算法的性能

具有較好的性能，能較好的滿足各種

類型用戶的要求。

終端型作業(yè)用戶;

短批處理作業(yè)用戶;

長批處理作業(yè)用戶;

處理機管理

3,3實時調度

在實時系統(tǒng)中，存在著若干個實時進

程或任務，它們用來反應或控制某個外部

事件，并且?guī)в芯o迫性。所以對實時系統(tǒng)

中的調度提出了某些特定的要求。

處理機管理

.、實時調度的基本條件

1.提供必要的信息

(1)就緒時間。

⑵開始截止時間和完成截止時間。

⑶處理時間。

(4)資源要求。

⑸優(yōu)先級。

鼠理機管理

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

.在單處理機情況下，必須滿足下列條件:

mC.

2—*L<1

i.=piP；

系統(tǒng)才是可調度的。

其中m為系統(tǒng)中周期性的硬實時任務個數(shù)，

Ci為處理時間，Pi為周期時間（m個任務執(zhí)

行一次所用的時間）/藕、

（處理機管理

若系統(tǒng)中有6個硬實時任務，它們的周期時間

:50ms,而每次的處理時間為10ms,則

:算出，此時是不能滿足上式的,因而系

S:不可調度的

解決的方法是提高系統(tǒng)的處理能力，其途

徑有二：其一仍是采用單處理機系統(tǒng)，但須

增強其處理能力，以顯著地減少對每一個任

務的處理時間；其二是采用多處理機系統(tǒng)。

假定系統(tǒng)中的處理機數(shù)為N,則應將上述的限

制條件改為：盟Q

y—L<TV

乙p處理機管理

i=lri

3.采用搶占式調度機制

—當一個優(yōu)先權更高的任務到達時，允許

,當前任務暫時掛起，而令高優(yōu)先權任務立

即投入運行，這樣便可滿足該硬實時任務對

截止時間的要求。但這種調度機制比較復雜。

對于一些小的實時系統(tǒng)，如果能預知任

務的開始截止時間，則對實時任務的調度可

采用非搶占調度機制，以簡化調度性

任務調度時所花費的系統(tǒng)開銷。'處理機管理

但在設計這種調度機制時,應使所有的

實時任務都比較小，并在執(zhí)行完關鍵性

程序和臨界區(qū)后，能及時地將自己阻塞

起來，以便釋放出處理機，供調度程序

去調度那種開始截止時間即將到達的任

務。

限理機管理

4.具有快速切換機制

J普機制應具有如下兩方面的能力：

.1）對外部中斷的快速響應能力。為使在緊迫

的外部事件請求中斷時系統(tǒng)能及時響應，要求系

統(tǒng)具有快速硬件中斷機構，還應使禁止中斷的時

間間隔盡量短，以免耽誤時機（其它緊迫任務）。

（2）快速的任務分派能力。在完成任務調度后,

便應進行任務切換。為了提高分派程序進行任務

切換時的速度，應使系統(tǒng)中的每個運行叫熊單但

適當?shù)男?，以減少任務切換的時間開銷。（處理機管理

二、實時調度算法的分類

-按實時任務性質的不同，可分為：硬實

時調度算法和軟實時調度算法;

-按調度方式的不同，可分為：非搶占調

度算法和搶占調度算法；

-按調度時間的不同，可分為：靜態(tài)調度

算法和動態(tài)調度算法；

■在多處理機環(huán)境下，調度算法可分為：

集中式調度算法和分布式調度算義—

鼠理機管理

茸調度方式的不同對調度算法進行分類：

并搶占式調度算法，可分為:

鼻￡搶占式輪轉調度算法:這是一種常用于分

時系統(tǒng)的調度算法，它只能適用于一般實時

信息處理系統(tǒng)，而不能用于實時要求嚴格的

實時控制系統(tǒng)。

非搶占式優(yōu)先調度算法：常用于多道批處理

系統(tǒng)的調度算法，也可用于實時要求不太嚴

格的實時控制系統(tǒng)

鼠理機管理

-搶占式調度算法，可分為:

基于時鐘中斷的搶占式優(yōu)先權調度算法：

用于大多數(shù)的實時系統(tǒng)中。

立即搶占的優(yōu)先權調度算法：

這種算法適用于實時要求比較嚴格的實時

控制系統(tǒng)。

限理機管理

實時進程要求調度調度實時進程運行實時進程請求調度時鐘中斷到來時

進程1進程2進程“實時進程當前進程實時進程

3■-———二——--------.，■調度時間，

------調度時間--------------5

⑹基于時鐘中斷搶占的優(yōu)先權搶占調度

⑷非搶占輪轉調度

實時進程請求調度當前進程運行完成

1實畔程請求調度1實時進程槍占當前

11

i[進程，并立即執(zhí)行

1[______

當前進程實時進程當前進程實時進程

<-----調度時間——>，-調度時間-?

①）非搶占優(yōu)先權調度M）立即搶占的優(yōu)先MSr------

圖3.4實時進程調度理機管理

三常用的幾種實時調度算法

勻章早截止時間優(yōu)先算法即EDF(EarIiest

?eadlineFirst)算法

截止時間愈早，其優(yōu)先級愈高。

該算法要求系統(tǒng)中保持一個實時任務就

緒隊列，該隊列按各任務截止時間的早晚排

序，具有最早截止時間的任務排在隊首。調

度時，總選擇隊首的第一個任務，分配處理

機，并運行。，一^

%理機管理

342

八44八

開始截止時間排序

任務執(zhí)行1342

任務到達

1234

系統(tǒng)首先調度任務1執(zhí)行，在任務工執(zhí)行期間,

任務2、3先后到達，由于任務3的截止時間早于

任務2的，故系統(tǒng)在任務1后將調度任務3執(zhí)行。

■最低松弛度優(yōu)先算法即LLF(LeastLaxity

First)算法

艮據(jù)任務的緊急程度，來確定任務的優(yōu)

曇級。緊急程度愈高,所賦予的優(yōu)先級愈高

算法實現(xiàn)時，要求系統(tǒng)中有一個按松弛

度排序的實時任務就緒隊列，松弛度最低的任

務排在隊列最前面，調度時總是選擇就緒隊列

中的隊首任務執(zhí)行。

任務A的松弛度=必須完成時間-本身運行時間-當前時間

該算法主要可用于搶占式任務。flbaWS

■例如，一個任務在200ms時必須完成，

FT它本身所需的運行時間就有100ms,

因此，調度程序必須在100ms之前調度

執(zhí)行，該任務的緊急程度（松弛程度）為

100mSo又如，另一任務在400ms時

必須完成，它本身需要運行150ms,

則其松弛程度為250mso

處理機管理

例題：假如在一個實時系統(tǒng)中，有兩個周

期性實時任務A和B,任務A要求每20

ms執(zhí)行一次，執(zhí)行時間為10ms；任

務B只要求每50ms執(zhí)行一次，執(zhí)行時間

為25mSo

處理機管理

圖3.5A和B任務每次必須完成的時間

處理機管理

在剛開始時。1=0),Al必須在20ms時完成,

去它本身運行又需10ms,可算出A1的松弛

同/10ms；Bi必須在501ns時完成,而它本

身運行就需25ms,可算出Bi的松弛度為25

ms,故調度程序應先調度A1執(zhí)行。在，2=10

ms時，A2的松弛度可按下式算出：

A2的松弛度=必須完成時間■其本身的運

行時間-當前時間=40ms-10ms-10ms=20ms

(處理機管理

類似地，可算出B1的松弛度為15ms,故調

度程序應選擇B1運行。在，3=30ms時，A2的松

弱隙已減為0(即4010-30),而B1的松弛度為15

ms(即50?5?30),于是調度程序應搶占的處理

機而調度A2運行。在t4=40ms時，A3的松弛度

為10ms(BP60-10-40),而的松弛度僅為5ms(

即50-5-40),故又應重新調度Bi執(zhí)行。在ts=45

ms時，Bi執(zhí)行完成，而此時A3的松弛度已減為

5ms(即60-10-45),而B2的松弛度為30ms(即

100-25-45),于是又應調度A3執(zhí)行。丁女錦

J處理機官理

產(chǎn)6=55ms時,任務A尚未進入第4周期,

施任務B已進入第2周期,故再調度B2執(zhí)

行。在t7=70ms時，A4的松弛度已減

至0ms(即80-10-70),而B2的松弛度

為20nls(即100-10-70),故此時調度

又應搶占B2的處理機而調度A4執(zhí)行。

圖3-9利用ELLF算法進行調度的情況

處理機管理

3.4多處理機系統(tǒng)中的調度

提高計算機系統(tǒng)的兩種途徑:

?、提高構成計算機的元器件的運行速度；

.、改進計算機系統(tǒng)的體系結構，特別是在系統(tǒng)

中引入多個處理器或多臺計算機，以實現(xiàn)對信

息的高度并行處理，達到提高系統(tǒng)吞吐量和可

靠性的目的。

處理機管理

一、什么是多處理機系統(tǒng)

概念：是一個具有兩個或多個處理機并能相互

進行通信以協(xié)同一個大的給定問題求解的計算

機系統(tǒng)。

特點：1）有兩個或多個處理機

2）共享主存或高速通信網(wǎng)絡

3）共享輸入輸出子系統(tǒng)

4）有單一完整的操作系統(tǒng)

5）各級硬件和軟件相互作用

主要功能：

?進程分配

更好的利用多機硬件

資源在處理機之間的分配

改善程序的響應時間

更好地處理處理機的負載平衡

處理機間的協(xié)調和同步

因處理機故障引起的系統(tǒng)重組

處理機管理

]■廣義上說，使用多處理機協(xié)調工作,來完

疆戶所要求任務的計算機系統(tǒng),這包括了并

行處理系統(tǒng)，也包括了分布式系統(tǒng)，以及在同

一計算機系統(tǒng)里共享內存的多處理機系統(tǒng)。

廣義的計算機系統(tǒng)的一個共同的特點是有

n個處理器(n>l),能做到真正的并行處理，也就

是能同時執(zhí)行n條指令.

處理機管理

二多處理器系統(tǒng)的類型

密耦合MPS和松弛耦合MPS(MultiProcessor

System

系統(tǒng)中包含的在處,在

系統(tǒng)中有多個類型的處理器單元〕

其功能和結構各不相同，其中有一4

主處理器，有多個從處理器。

管理

三、進程,

對稱

多采用主一從式OS,即OS的核心部

分駐留在一臺主機上，從機上是用戶'

程序，進程調度由主機執(zhí)行。當一臺從機

空閑時，便向主機發(fā)送信號，等待主機/

為其分配進程。

池一個空

/處理器上。所以一個進程

靜態(tài)分配?

的運行，可能被隨機地分配?

動態(tài)分配q

當時是空閑的某一處理矍（

非對稱MPS加

管理

四、進程(線程)調度方式

■自調度(Self-Scheduling)方式

自調度機制

自調

1、瓶頸問題；多處理器只能互

訪問該隊列2、低效性；一旦阻塞因

更換處理機就要頻繁的拷貝數(shù)據(jù)

3、線程切換頻繁

管理

T成組調度(GangScheduling)方式

注也人出鋰出的

土調…度方法：將一個進程中的一

組線程分配到一組處理器上去。

在成組調度時，如何為應用程序分配處理器時間?

1)面向所有應用程序平均分配處理器時間

2)面向所有線程平均分配處理器時間

%:理機管理

?1ftSSl

ft?2MS2

MS3

W4處螂4

⑷期37.5%(b)據(jù)費15%

處理機管理

成組調度方式的主要優(yōu)點：若一組相互合

作的進程或線程，能并行執(zhí)行，則可有效地減

少線程（進程）阻塞情況的發(fā)生，從而減少線

程的切換，改善系統(tǒng)的性能。

止匕外，也相應地減少了處理器分配和調度

的頻率，所以也減少了開銷。

處理機管理

■專用處理器分配方式

■為進程中的每個線程都固定分配一個CPU,

直到該線程執(zhí)行完成。

缺點：線程阻塞時，造成CPU的閑置。

優(yōu)點：線程執(zhí)行時不需切換，相應的開銷

可以大大減小，推進速度更快。適用場合：

CPU數(shù)量眾多的高度并行系統(tǒng)，單個CPU

利用率已不太重要。廠、

I處理機管理

圖3?11線程數(shù)對加速比的影響

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

&多道程序環(huán)境卜，我們可借助多個并發(fā)程

序并發(fā)執(zhí)行，來改善系統(tǒng)的資源利用率，提

高系統(tǒng)的吞吐量，但也可能出現(xiàn)問題一死鎖。

死鎖是指多個進程在運行過程中，因爭奪

資源而導致每個進程都無法執(zhí)行的一種僵局。

此時若不對其干涉，則這些進程都無法向前

推進。

（處理機管理

死鎖簡單的定義：

密就是兩個或兩個以上的進程等候著一個永

般、會發(fā)生的事件時所取的一種系統(tǒng)狀態(tài)。

教材上關于死鎖的定義：

兩個或兩個以上并發(fā)進程，如果每個進程持有

某種資源，而又等待著別的進程釋放它或它們

現(xiàn)在保持著的資源，否則就不能向前推進。此

時，每個進程都占用了一定的資源，但又都不

能向前推進。這種現(xiàn)象稱為死鎖。尸一-

（處理機管理

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

廣生死鎖的根本原因是

1、競爭資源引起進程死鎖:當系統(tǒng)中供多

個進程所共享的資源，不足以同時滿足

他們的需要時，引起他們對資源的競爭

而引起死鎖。

2、進程推進順序不當引起死鎖：進程在運

行過程中，請求和釋放資源的順序不當,

導致了進程死鎖。晨理機管理

?競爭資源引起進程死鎖

4^可剝奪和非剝奪性資源（（consumable

resource）：可以動態(tài)生成和消耗，一般

不限制數(shù)量。如硬件中斷、信號、消息、

緩沖區(qū)內的數(shù)據(jù)。）

2）競爭非剝奪性資源（打印機，磁帶機等）

3）競爭臨時性資源

?死鎖發(fā)生：雙方都等待對方去生成資那一、

（處理機管理

-永久性資源：像打印機一樣可順序重復

，使用的資源；

.臨時性資源，也稱為消耗性資源，是指

由一個進程產(chǎn)生，被另一進程使用一短

暫時間后便無用的資源。

-由于進程具有異步性，這就可能使進程

按下述兩種順序向前推進：

-1）進程推進順序合法；

-2）進程推進順序非法。廠一、

:處理機管理

11.死鎖的例子

）工）設備共享

進程PI、P2,共享一臺打印機和一

臺磁帶機

時亥世工：進程P工——占用打印機

進程P2——占用磁帶機

時刻t2：進程P工——又請求磁帶機

進程P2——又請求打印機、

限理機管理

I/O設備共享時的死鎖情況

進程之間通信時的死鎖

?進程推進順序不當引起死鎖

I1）進程推進順序合法

P2Relg)

②①

P2Rel(R2)

P2ReqtR,)0

PReq(0)

2j.?4

Reqg)P1Req(0)P1Rel(RJP1Rel(R2)

進程推進順序對死鎮(zhèn)的影響

）進程推進順序非法

若并發(fā)進程P]和P2按曲線④所示的順

序推進，它們將進入不安全區(qū)D內。此時P]

保持了資源P2保持了資源R”系統(tǒng)處于

不安全狀態(tài)。因為，這時兩進程再向前推進,

便可能發(fā)生死鎖。

處理機管理

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

f互斥條件：任一時刻只允許一個進程使

i用資源

2.請求和保持條件：進程在請求其余資源

時，不主動釋放已經(jīng)占用的資源

3,非剝奪條件：進程已經(jīng)占用的資源，不

會被強制剝奪

4,環(huán)路等待條件：環(huán)路中的每一條邊是進

程在請求另一進程已經(jīng)占有的資物一^

①理機管理

;處理死鎖的基本方法

⑴預防死鎖。

(2)避免死鎖。

(3)檢測死鎖。

(4)解除死鎖。

處理機管理

3?6預防死鎖的方法

一預防死鎖和避免死鎖這兩種方法，實質

上都是通過施加某些限制條件的方法，來防

止死鎖的發(fā)生。

兩者的主要區(qū)別是：為預防死鎖所施加

的限制條件嚴格;為避免死鎖所施加的限制條

件則較寬松，它給進程的運行提供了較寬松

的環(huán)境，有利于進程的并發(fā)執(zhí)行。

限理機管理

一、預防死鎖

頁防死鎖：通過設置某些限制條件，去破壞

■鎖的四個必要條件中的一個或幾個條件,

f來防止發(fā)生死鎖。這是一種較易實現(xiàn)的方法,

被廣泛應用。但由于所施加的限制條件往往

太嚴格，可能導致資源利用率和系統(tǒng)吞吐量

的降低。預防死鎖的方法是使四個必要條件

中的第2、3、4個條件之一不能成立，來］

止發(fā)生死鎖。11.摒棄“請求和保持”條I

2.摒棄“不剝奪”條彳

3.摒棄“環(huán)路等待”5

破壞“請求與保持條件”

-這種方法的基本思想是：每個進程在運行之

前，必須預先提出自己所要使用的全部資源,

調度程序在該進程所需要的資源未得到滿足

之前，不讓它們投入運行，并且當資源一旦

分配給某個進程之后，那么在該進程的整個

運行期間相應資源一直被它占有，這就破壞

了產(chǎn)生死鎖的請求與保持條件。/一、

破壞環(huán)路條件

上座種方法的基本思想是：對系統(tǒng)提供的每一

卦資源，由系統(tǒng)設計者將它們按類型進行線

性排隊，并賦予不同的序號。例如，設卡片

輸入機為1,打印機為2,磁帶機為3,磁盤

機為4,……o

1.對進程所必須使用的而且屬于同一類的所

有資源，必須一次申請完；

2.在申請不同類資源時，必須按各類設備的

編號遞增（或遞減）的次序依次申請。

處理機管理

亦即，只有低編號的資源要求滿足后，

才能對高編號資源提出要求；釋放資源

時，應按編號遞減的次序進行。由此可

以看出，對資源請求采取了這種限制之

后，所形成的進程一資源圖不可能再產(chǎn)

生環(huán)路。

處理機管理

啜：進程PA,使用資源的順序是RI,R2；

進程PB,使用資源的順序是R2,R1；

若采用動態(tài)分配有可能形成環(huán)路條件，造成死

鎖。

采用有序資源分配法：R1的編號為1,R2的編

號為2；

PA：申請次序應是：RLR2

PB：申請次序應是：R1,R2

這樣就破壞了環(huán)路條件,避免了死鎖的

發(fā)生。履理機管理

,3.資源受控動態(tài)分配

-為了避免死鎖發(fā)生，操作系統(tǒng)必須根據(jù)

預先掌握的關于資源用法的信息控制資

源分配，使得共同進展路徑的下一步不

致于進入危險區(qū)，即只要有產(chǎn)生死鎖的

可能性，就避免把一種資源分配給一個

進程。

處理機管理

預防是采用某種策略，限制并發(fā)進程對資源的

請快，使系統(tǒng)在任何時刻都不滿足死鎖的必要

*____________

?預防死鎖的兩種策略：

-預先靜態(tài)分配法：（針對死鎖的第2個條件）

預先分配所需全部資源，保證不等待資源；

?降低了對資源的利用率，降低進程的并

發(fā)程度；

?有可能無法預先知道所需資源；

限理機管理

-有序資源使用法：（針對死鎖的第4個

條件）把資源分類按順序排列，保證

不形成環(huán)路；

?限制進程對資源的請求；

?資源的排序占用系統(tǒng)開銷；

處理機管理

二、系統(tǒng)安全狀態(tài)

1.安全狀態(tài)_

避免死鎖：并不需事先采取各種限制

措施去破壞產(chǎn)生死鎖的必要條件，而

是在資源的動態(tài)分配過程中，用某種

方法防止系統(tǒng)進入不安全狀態(tài)，從而

避免發(fā)生死鎖。

處理機管理

所謂安全狀態(tài)，是指系統(tǒng)能按某種進程

順序(Pl,P,…，Pn)(稱〈Pl,P"…，Pn>序

列為安全序列)，來為每個進程p分配其所需

資源，直至滿足每個進程對資源的最大需求，

使每個進程都可順利地完成。

如果系統(tǒng)無法找到這樣一個安全序列，

則稱系統(tǒng)處于不安全狀態(tài)。【處理機管理

I2.安全狀態(tài)之例

*假定系統(tǒng)中有三個進程Pl、P2和P3,共有

12臺磁帶機。假設在1時刻，如下表所示：

進程最大需求已分配可用

Pi1053

42

p2

P392

處理機管理

由安全狀態(tài)向不安全狀態(tài)的轉換

如果不按照安全序列分配資源，則系

統(tǒng)可能會由安全狀態(tài)進入不安全狀態(tài)。

■1.銀行家算法(Dijkstra,1965)

問題

■一個銀行家把他的固定資金（capital）

貸給若干顧客。只要不出現(xiàn)一個顧客借

走所有資金后還不夠的情況，銀行家的

資金應是安全的。銀行家需一個算法保

證借出去的資金在有限時間內可收回。

限理機管理

我們可以把操作系統(tǒng)看作是銀行家，

操作系統(tǒng)管理的資源相當于銀行家管理的

資金，進程向操作系統(tǒng)請求分配資源相當

于用戶向銀行家貸款。操作系統(tǒng)按照銀行

家制定的規(guī)則為進程分配資源，當進程首

次申請資源時，要測試該進程對資源的最

大需求量，如果系統(tǒng)現(xiàn)存的資源可以滿足

它的最大需求量則按當前的申請量分配資

源，否則就推遲分配。：處理機管理

進程在執(zhí)行中繼續(xù)申請資源時，先測試

該進程已占用的資源數(shù)與本次申請的資

源數(shù)之和是否超過了該進程對資源的最

大需求量。若超過則拒絕分配資源，若

沒有超過則再測試系統(tǒng)現(xiàn)存的資源能否

滿足該進程尚需的最大資源量，若能滿

足則按當前的申請量分配資源，否則也

要推遲分配。廠一、

（處理機管理

2.銀行家算法

點段定貸款分成若干次進行；并且客戶在第一

融借款時,能說明他的最大借款額。

?具體算法：

一客戶的借款操作依次順序進行，直到全部

操作完成；

-銀行家對當前客戶的借款操作進行判斷，

以確定其安全性（能否支持客戶借款，直

到全部歸還）；

-安全時，貸款；否則，暫不貸款。^^）1^^

3.銀行家算法的特點

?允許互斥、部分分配和不可搶占，可提高

資源利用率；

?要求事先說明最大資源要求，在現(xiàn)實中很

困難；

處理機管理

4.解決死鎖問題的綜合方法

g資源歸類：將各種資源歸入若干個不同的資

源類（resourcegroup）中，如：外存交換區(qū)

空間，進程資源（可分配的設備，如磁帶機,

文件），主存空間，內部資源（如I/O通道）

?資源排序：在不同資源類之間規(guī)定次序，對

不同資源類中的資源采用線性按序申請的方

法

限理機管理

?針對性優(yōu)化：可對同一資源類中的資

源進行針對性處理，采用不同的適當

方法。例如，使用避免方法處理外設

資源分配，而對存儲資源則采用預防

方法。

處理機管理

三、利用銀行家算法避免死鎖

1.1.銀行家算法中的數(shù)據(jù)結構

(1)可利用資源向量Available

是個含有用個元素的數(shù)組，其中的每一個元

素代表一類可利用的資源數(shù)目。如果Available

：j]=K,則表示系統(tǒng)中現(xiàn)有Rj類資源或個。

處理機管理

(2)最大需求矩陣Max

這是一個〃義陽的矩陣，它定義了系統(tǒng)中

〃個進程中的每一個進程對冽類資源的最大

需求。如果Max[i,j]=K,則表示進程i需

要R1類資源的最大數(shù)目為K。

處理機管理

(3)分配矩陣Allocation

這也是一個〃義切的矩陣，它定義了系統(tǒng)

中每一類資源當前已分配給每一進程的資源數(shù)。

如果Allocation[ij]=K,則表示進程i當前

已分得勺類資源的數(shù)目為《

處理機管理

(4)需求矩陣Need。

這也是一個〃X/M的矩陣，用以表示每一

個進程尚需的各類資源數(shù)。如果Need[i,j]

=K,則表示進程i還需要Rj類資源K個，方能

完成其任務。

Need[ij]=Max[ij]-Allocation[ij_

處理機管理

2、銀行家算法

設Requestj是進程匕的請求向量，如果

Request[j]=K,表示進程居需要A個%類型的

資源。當匕發(fā)出資源請求后，系統(tǒng)按下述步驟進

行檢查：

(1)如果Request[j]《Need[i,j],便轉向

步驟2；否則認為出錯，因為它所需要的資源數(shù)

已超過它所宣布的最大值。

(2)如果Request[j]^Available[j],便

轉向步驟(3)；否則，表示尚無足夠資源，匕須

等待。

（3）系統(tǒng)試探著把資源分配給進程并修

改下面數(shù)據(jù)結構中的數(shù)值：

Available[j]:=Available[j]

-Requestj[j]；

Allocation[ijl:=AllocationLbjl

+Requesti[j]；

Need[ij]:=Need[ij]-Requestj[jl；

(4)系統(tǒng)執(zhí)行安全性算法，檢查此次資

源分配后，系統(tǒng)是否處于安全狀態(tài)。若安全,

才正式將資源分配給進程匕，以完成本次分

配；否則，將本次的試探分配作廢，恢復

原來的資源分配狀態(tài)，讓進程匕等待。

3.安全性算法

JJ1）設置兩個向量：

?工作向量Work:它表示系統(tǒng)可提供給

進程繼續(xù)運行所需的各類資源數(shù)目，它含有m

個元素，在執(zhí)行安全算法開始時，

Work:=Available;

②工作向量Finish:它表示系統(tǒng)是否有足

夠的資源分配給進程，使之運行完成。開始時

先做Finish[i]:=false;當有足夠資蹲分配紿＜

進程時，再令Finish[i]:=trueo/理機管理

(2)從進程集合中找到一個能滿足下述條

件的進程：

DFinish[i]=false;

②Need[ij]<Work[j]；若找到,

執(zhí)行步驟(3),否則，執(zhí)行步驟(4)。

(3)當進程Pi獲得資源后,可順利執(zhí)

行，直至完成，并釋放出分配給它的資

源，故應執(zhí)行：

?Work[j]：=Work[j]

+Allocation[ij];

■Finish[i]：=true;

■gotostep2;

處理機管理

(4)如果所有進程的Finish[i]=true都滿

足，則表示系統(tǒng)處于安全狀態(tài)；否則，系

統(tǒng)處于不安全狀態(tài)。

處理機管理

3、銀行家算法的優(yōu)缺點

T優(yōu)點：使用銀行家算法來分配資源是不會

%產(chǎn)生死鎖的。因為該算法保證了每次分配

?都不會使系統(tǒng)進入不安全狀態(tài)。

■缺點

-(1)要求系統(tǒng)中每類資源的數(shù)量不變，

用戶的數(shù)目也保持不變，但一些系統(tǒng)中做

不到。

■(2)本算法還要求每個進程必須事先

說明它們的最大資源需求量。

■(3)算法的實現(xiàn)本身也要增加廠些系、

統(tǒng)開銷。羋理機官理

4、銀行家算法一舉例

各種資源的數(shù)量分別為10、5、7,在丁。時刻

的資源分配情況如圖所示。

源楮MaxAllocationNeedAvailable

進程ABCABCABC：ABC

P。753010743332

(230)

■?14322：200122

(302)(020)

302600

p2902

Pa轉222211011

H433002431，

To時刻的資源分配表

(1)r時刻的安全性:

、\資源椿

Work,NeedAllocationWork+AllocationFinish

ABCABCABC*ABC

P.332122200532true

Oil211J743true

1p3532

Rj743431002745true

745600302:1047true

P2.

true

P01041743010,41057

(2)以請求資源：以發(fā)出請求向量

RequestjCl,0,2),系統(tǒng)按銀行家算法進行

檢查：

①Requesti(l,0,2)WNeedi(l,2,2)

2)Request]。，0,2)WAvailable](3,3,2)

③系統(tǒng)先假定可為Pi分配資源，并修改

Available,Allocation］和Need1向量，由此形成的

資源變化情況如圖3-15中的圓括號所示。

④再利用安全性算法檢查此時系統(tǒng)是否

安全。

Work]Need,AllocationWorkfAllocationFinish

ABCABCABC:ABC

P1230020302532true

耳■532011211743true

匕743431002745true

Po745743010755true

P27556003021057true

處理機管理

Pl申請資源時的安全性檢查

(3)請求資源：發(fā)出請求向量Request's,

3,0),系統(tǒng)按銀行家算法進行檢查:

①Request4(3,3,0)<Need4(4,3,1);

②Request#,3,0)<Available。，3,0),讓

P4等待。

處理機管理

(4)P0請求資源:P0發(fā)出請求向量Requsto(O,2

,0),系統(tǒng)按銀行家算法進行檢查：

①Requesto(O,2,0)<Need0(7,4,3);

②Request。?2,0)<Available(2,3,0);

③系統(tǒng)暫時先假定可為Po分配資源，并修

改有關數(shù)據(jù)，如下圖所示。

(5)進行安全性檢查：可用資源AvailableQ,

1,0)不能滿足任何進程的要求，所以系統(tǒng)進入不

安全狀態(tài)，此時系統(tǒng)不分配資源。

艱情AllocationNeedAvailable

進程7^

ABC?ABC.ABC