操作系統(tǒng)-資源分配與調(diào)

會(huì)計(jì)學(xué)1操作系統(tǒng)—資源分配與調(diào)5.1資源管理概述5.1.1資源管理的目的和任務(wù)什么是資源？資源包括硬件資源和軟件資源。是指執(zhí)行一個(gè)用戶程序所需要的全部硬件設(shè)備、軟件設(shè)施和數(shù)據(jù)。第1頁(yè)/共35頁(yè)5.1資源管理概述5.1.1資源管理的目的和任務(wù)什么是資源管理？根據(jù)不同資源的不同特點(diǎn)，按用戶要求對(duì)資源實(shí)行合理的分配，監(jiān)察資源的使用情況，回收空閑資源，并保護(hù)資源不受非法使用。第2頁(yè)/共35頁(yè)5.1資源管理概述5.1.1資源管理的目的和任務(wù)資源管理的目標(biāo)（從它的反面談起）高效（例：CPU的利用）合理（例：內(nèi)存的分配）安全（例：網(wǎng)絡(luò)訪問(wèn)，死鎖）

第3頁(yè)/共35頁(yè)5.1資源管理概述5.1.1資源管理的目的和任務(wù)資源管理的任務(wù)資源數(shù)據(jù)結(jié)構(gòu)的描述確定資源的分配原則和調(diào)度原則執(zhí)行資源分配存儲(chǔ)控制和安全保護(hù)

第4頁(yè)/共35頁(yè)5.1資源管理概述5.1.2資源的分類方法（p120）物理資源與程序資源單一訪問(wèn)入口資源和多訪問(wèn)入口的資源等同資源虛擬資源第5頁(yè)/共35頁(yè)5.1資源管理概述5.1.3資源管理的機(jī)構(gòu)和策略（p121）機(jī)構(gòu)：操作系統(tǒng)實(shí)現(xiàn)資源管理的部分策略：關(guān)于這部分操作系統(tǒng)的具體設(shè)計(jì)注意：由于每種資源具有各自的特點(diǎn)，分配的機(jī)制和策略不盡相同，本章主要從資源的一般共性出發(fā)，著重討論資源分配的一般機(jī)制和策略，具體的實(shí)施將在后續(xù)各章中陸續(xù)展開(kāi)討論。第6頁(yè)/共35頁(yè)5.2資源分配機(jī)制5.2.1資源描述器（resourcedescriptor，RD）資源描述器（表5.1，p121）：描述資源的數(shù)據(jù)結(jié)構(gòu)。操作系統(tǒng)通過(guò)這些數(shù)據(jù)結(jié)構(gòu)而感知到資源的存在，并對(duì)資源進(jìn)行管理。最小分配單位：某一類資源根據(jù)需要?jiǎng)澐譃椴豢稍俜指畹幕痉峙鋯挝弧Ｒ粋€(gè)最小分配單位通過(guò)一個(gè)資源描述器加以描述。第7頁(yè)/共35頁(yè)5.2資源分配機(jī)制5.2.1資源描述器資源描述器的組織方式：表：適合于分配單位數(shù)量固定不變隊(duì)列：適合于分配單位數(shù)量是變化的最大數(shù)組法：適合于分配單位的最大數(shù)量是已知的。如一個(gè)硬盤(pán)空間是不變的，當(dāng)確定最小分配單位后，便可生成所有的資源描述器。第8頁(yè)/共35頁(yè)5.2資源分配機(jī)制5.2.2資源信息塊（rib）（p122，圖5.1）資源信息塊包含如下內(nèi)容：等待進(jìn)程隊(duì)列可利用資源隊(duì)列資源分配程序入口地址第9頁(yè)/共35頁(yè)5.3資源分配策略5.3.1概述資源分配的兩個(gè)目標(biāo)：吞吐率：在單位時(shí)間內(nèi)完成工作量的量度。響應(yīng)時(shí)間：提交請(qǐng)求和返回該請(qǐng)求的響應(yīng)之間所使用的時(shí)間。吞吐率和響應(yīng)時(shí)間是服務(wù)系統(tǒng)（如：數(shù)據(jù)庫(kù)服務(wù)器、web服務(wù)器等）的兩個(gè)最為重要的評(píng)價(jià)指標(biāo)，所追求的目標(biāo)就是高吞吐率和短響應(yīng)時(shí)間。第10頁(yè)/共35頁(yè)5.3資源分配策略5.3.1概述在其他條件不變的情況下，吞吐率與響應(yīng)時(shí)間往往存在矛盾的，即以犧牲響應(yīng)時(shí)間來(lái)獲取高吞吐率，或以犧牲吞吐率來(lái)獲取短響應(yīng)時(shí)間。系統(tǒng)設(shè)計(jì)時(shí)需要根據(jù)應(yīng)用環(huán)境作出平衡。ABAABAB第11頁(yè)/共35頁(yè)5.3資源分配策略5.3.2先請(qǐng)求先服務(wù)

(FIFO—FirstInFirstOut)排序原則：按請(qǐng)求的先后次序排序。即：新產(chǎn)生的請(qǐng)求均排在隊(duì)尾，分配時(shí)在隊(duì)首。適用范圍：系統(tǒng)中的一切資源。優(yōu)點(diǎn)：簡(jiǎn)單、次序不會(huì)改變、系統(tǒng)開(kāi)銷小。缺點(diǎn)：未對(duì)請(qǐng)求特征、占用資源時(shí)間長(zhǎng)短等因素加以考慮，不利于短作業(yè)，系統(tǒng)無(wú)法進(jìn)行干預(yù)。第12頁(yè)/共35頁(yè)5.3資源分配策略5.3.3優(yōu)先調(diào)度：系統(tǒng)對(duì)每個(gè)進(jìn)程(或作業(yè))，都指定一個(gè)優(yōu)先級(jí)以反映請(qǐng)求資源的緊迫程度排序原則：按優(yōu)先級(jí)的高低排序。即：新產(chǎn)生的請(qǐng)求，按其優(yōu)先級(jí)的高低插入到隊(duì)列中相應(yīng)的位置。優(yōu)點(diǎn)：系統(tǒng)可進(jìn)行干預(yù)，以優(yōu)化資源的使用方式缺點(diǎn)：插入時(shí)要搜索隊(duì)列、有時(shí)無(wú)法用隊(duì)列實(shí)現(xiàn)，另外如何合理地分配優(yōu)先級(jí)也是一個(gè)問(wèn)題。適用的資源：由于系統(tǒng)開(kāi)銷較大，主要用于系統(tǒng)中的緊缺資源(如處理機(jī)的分配)。第13頁(yè)/共35頁(yè)5.3資源分配策略資源分配策略的總原則：保證緊急事務(wù)優(yōu)先處理保證低級(jí)事務(wù)得到處理保證輕量事務(wù)及時(shí)處理第14頁(yè)/共35頁(yè)5.4死鎖5.4.1死鎖的概念死鎖是一個(gè)較為復(fù)雜的概念，在講這個(gè)概念之前，先看一些例子。例1：網(wǎng)上交易支付問(wèn)題賣方與買方談妥后，買方交付了60%的貨款，然后賣方向買方發(fā)貨。當(dāng)收到貨物后，買方不滿意貨物提出退貨，然而賣方認(rèn)為理由不合理，不予退貨。交易無(wú)法推進(jìn)下去。思考：你認(rèn)為應(yīng)該怎樣解決？第15頁(yè)/共35頁(yè)5.4死鎖例2：十字路的交通問(wèn)題（練習(xí)題P1385-7）思考：它們是如何導(dǎo)致死鎖的？第16頁(yè)/共35頁(yè)5.4死鎖例2：回顧：生產(chǎn)者－消費(fèi)者問(wèn)題消費(fèi)者在未檢查緩沖區(qū)是否為空的時(shí)候便申請(qǐng)了讀寫(xiě)許可mutex，當(dāng)緩沖區(qū)為空時(shí)，消費(fèi)者需要等生產(chǎn)者生產(chǎn)產(chǎn)品，然而生產(chǎn)者同樣因?yàn)樵诘却M(fèi)者釋放緩沖區(qū)而陷入了死鎖。

mutex=1;full=0;empty=n;

p1(

)

p2(

)

{while(生產(chǎn)未完成)

{while(還要繼續(xù)消費(fèi))

{．．．{p(mutex)；生產(chǎn)一個(gè)產(chǎn)品；p(full)；

p(empty)；從緩沖區(qū)中取產(chǎn)品；

p(mutex)；

v(mutex)；送一個(gè)產(chǎn)品到緩沖區(qū)；v(empty)；

v(mutex)；．．．

v(full)；消費(fèi)一個(gè)產(chǎn)品；

}}

}}第17頁(yè)/共35頁(yè)5.4死鎖5.4.1死鎖的概念例3：設(shè)系統(tǒng)只有一臺(tái)打印機(jī)(R1)，和一臺(tái)光標(biāo)記閱讀機(jī)(R2)，由進(jìn)程p1、p2共享。用信號(hào)燈的P、V操作，控制資源的申請(qǐng)和釋放。其信號(hào)燈的設(shè)置為：

s1：表示R1是否可用，初值為1。

s2：表示R2是否可用，初值為1。

進(jìn)程P1

進(jìn)程P2

p(s1)；申請(qǐng)R1

p(s2)；申請(qǐng)R2

p(s2)；又申請(qǐng)R2

p(s1)；又申請(qǐng)R1．．．．．．

v(s1)；釋放R1

v(s2)；釋放R2．．．．．．

v(s2)；釋放R2

v(s1)；釋放R1第18頁(yè)/共35頁(yè)5.4死鎖5.4.1死鎖的概念在兩個(gè)或多個(gè)并發(fā)進(jìn)程中，如果每個(gè)進(jìn)程都持有某種資源，而又都同時(shí)等待著別的進(jìn)程釋放它們保持著的資源否則就不能向前推進(jìn)。稱這一組進(jìn)程產(chǎn)生了死鎖。思考：是什么導(dǎo)致了死鎖？是因?yàn)檫M(jìn)程間的競(jìng)爭(zhēng)嗎？第19頁(yè)/共35頁(yè)5.4死鎖5.4.2死鎖的起因

(1)系統(tǒng)的資源總數(shù)＜∑各進(jìn)程的資源總需求

(2)進(jìn)程推進(jìn)的順序不合理

(資源的使用方式、及占有資源的順序)練習(xí)：p137，5-4第20頁(yè)/共35頁(yè)5.4死鎖5.4.2死鎖的起因例：對(duì)打印機(jī)（R1）-輸出機(jī)（R2）死鎖問(wèn)題的解釋p1p2R1R2分配申請(qǐng)申請(qǐng)分配第21頁(yè)/共35頁(yè)5.4死鎖5.4.2死鎖的起因死鎖的必要條件：互斥條件：涉及的資源為臨界資源部分分配：進(jìn)程每次僅申請(qǐng)所需資源的一部分，在占有資源以后，還會(huì)繼續(xù)申請(qǐng)新的資源，只有不滿足才等待。不剝奪條件：進(jìn)程占有的資源，不能被其他進(jìn)程強(qiáng)行剝奪環(huán)路條件：在進(jìn)程與資源有向圖中，存在有向環(huán)。只要其中一條不成立，死鎖就不會(huì)發(fā)生第22頁(yè)/共35頁(yè)5.4死鎖5.4.4解決死鎖的策略基本點(diǎn)：破壞死鎖的某一個(gè)必要條件

思考：破壞哪些必要條件是可行的呢？互斥條件不剝奪條件部分分配環(huán)路條件第23頁(yè)/共35頁(yè)5.4死鎖5.4.3解決死鎖的策略互斥條件：由硬件本身性質(zhì)決定了難于否定該條件。第24頁(yè)/共35頁(yè)5.4死鎖5.4.3解決死鎖的策略2．不剝奪條件：很容易否定。但是：（1）否定該條件是在發(fā)生了死鎖之后。（2）并且需要保護(hù)和恢復(fù)被剝奪的進(jìn)程現(xiàn)場(chǎng)。（3）不是所有資源都可以剝奪的（如正在打印的打印機(jī)）思考：更重要的是，要防死鎖于未然。第25頁(yè)/共35頁(yè)5.4死鎖3．部分分配：很容易否定，由此得到靜態(tài)預(yù)防死鎖。4．環(huán)路條件：可以否定。由此得到有序資源分配法。第26頁(yè)/共35頁(yè)5.4死鎖5.4.5死鎖的預(yù)防和避免靜態(tài)預(yù)防死鎖：在作業(yè)調(diào)度時(shí)，為選中的作業(yè)分配它所需要的所有臨界資源在該作業(yè)的整個(gè)運(yùn)行期間，這些資源都為它獨(dú)占。實(shí)質(zhì)：破壞了死鎖必要條件中的部分分配缺點(diǎn)：降低了設(shè)備的利用率(只用很短時(shí)間，或根本不用)造成不必要的等待用戶可能提不出所需的全部資源第27頁(yè)/共35頁(yè)5.4死鎖5.4.5死鎖的預(yù)防和避免有序資源分配法(避免死鎖，p134)：所有的資源類都給定一個(gè)唯一的序號(hào)（如打印機(jī)為1，閱讀機(jī)為2），分配請(qǐng)求必須以上升的次序進(jìn)行；而且同一類型的資源必須一次申請(qǐng)完。優(yōu)點(diǎn)：提高了資源利用率（p1使用完打印機(jī)后p2便可申請(qǐng)占用）缺點(diǎn)：進(jìn)程實(shí)際需要資源未必與編號(hào)一致。

實(shí)質(zhì)：破壞了死鎖的環(huán)路條件p1p2R1R2申請(qǐng)1申請(qǐng)2申請(qǐng)1申請(qǐng)2p1p2R1R2分配申請(qǐng)申請(qǐng)分配導(dǎo)致死鎖不導(dǎo)致死鎖第28頁(yè)/共35頁(yè)5.4死鎖小結(jié)：處理死鎖的四種策略1．檢測(cè)死鎖并恢復(fù)2．靜態(tài)預(yù)防死鎖3．有序的分配資源4．忽略死鎖（鴕鳥(niǎo)算法）第29頁(yè)/共35頁(yè)5.4死鎖銀行家算法（避免死鎖）當(dāng)進(jìn)程申請(qǐng)一組資源時(shí)，需要檢查申請(qǐng)者對(duì)資源的最大需求量，如果系統(tǒng)現(xiàn)存的各類資源的數(shù)量滿足當(dāng)前它對(duì)各類資源的最大需求量時(shí)，則滿足其申請(qǐng)；否則，進(jìn)程必須等待，直到其他進(jìn)程釋放足夠的資源為止。即：僅當(dāng)申請(qǐng)者可以在一定時(shí)間內(nèi)無(wú)條件的歸還它所申請(qǐng)的全部資源時(shí)，才進(jìn)行資源分配。第30頁(yè)/共35頁(yè)5.4死鎖

假設(shè)有n個(gè)進(jìn)程m類資源，則有如下數(shù)據(jù)結(jié)構(gòu)：可利用資源向量Available。這是一個(gè)含有m個(gè)元素的數(shù)組，其中的每一個(gè)元素代表一類可利用的資源數(shù)目，其初始值是系統(tǒng)中所配置的該類全部可用資源的數(shù)目，其數(shù)值隨該類資源的分配和回收而動(dòng)態(tài)地改變。Available[j]=K，則表示系統(tǒng)中現(xiàn)有Rj類資源K個(gè)。最大需求矩陣Max。這是一個(gè)n*m的矩陣，它定義了系統(tǒng)中n個(gè)進(jìn)程中的每一個(gè)進(jìn)程對(duì)m類資源的最大需求。如果Max[i，j]=K，則表示進(jìn)程i需要Rj類資源的最大數(shù)目為K。分配矩陣Allocation。這也是一個(gè)n*m的矩陣，它定義了系統(tǒng)中每一類資源當(dāng)前已分配給每一進(jìn)程的資源數(shù)。如果Allocation[i，j]=K，則表示進(jìn)程i當(dāng)前已分得Rj類資源的數(shù)目為K。需求矩陣Need。這也是一個(gè)n*m的矩陣，用以表示每一個(gè)進(jìn)程尚需的各類資源數(shù)。如果Need[i,j]=K，則表示進(jìn)程i還需要Rj類資源K個(gè)，方能完成其任務(wù)。上述三個(gè)矩陣存在如下關(guān)系：

Need[i,j]=Max[i，j]-Allocation[i，j]第31頁(yè)/共35頁(yè)5.4死鎖

設(shè)進(jìn)程I提出請(qǐng)求Request[N]，則銀行家算法按如下規(guī)則進(jìn)行判斷。

(1)如果Request[N]<=Need[I，N]，則轉(zhuǎn)(2)；否則，出錯(cuò)。

(2)如果Request[N]<=Available，則轉(zhuǎn)(3)；否則，出錯(cuò)。

(3)系統(tǒng)試探分配資源，修改相關(guān)數(shù)據(jù)：