【導(dǎo)讀】眾所周知，計算機系統(tǒng)由硬件和軟件組成。多的計算機軟件中，操作系統(tǒng)占有特殊重要的地位。圖5-1簡明地顯示了計算機系統(tǒng)的基本構(gòu)成。理器)和軟件開發(fā)工具都是建立在操作系統(tǒng)的基礎(chǔ)之上，它們的運行全都需要操作系統(tǒng)的支持。操作系統(tǒng)是用戶與計算機硬件之間的接口。操作和使用將變得非常低效和困難。+裸機=虛擬計算機，如圖5-2所示。換句話說，一臺純。的功能或操作方面都將面目一新。有了操作系統(tǒng)，才能使這一能力更有效、更方便。般的最終用戶——都需要不同程度地了解它。為用戶提供良好的界面。計算機系統(tǒng)管理員、應(yīng)用軟件的設(shè)計人員等。的一身二任的角色。CPU管理指操作系統(tǒng)根據(jù)一定的調(diào)度算法對。為了提高CPU的利用率，采用了多道程序技術(shù)。后者應(yīng)能搶占CPU?；厥盏葐栴}，以使CPU資源得到最充分的利用?？椊Y(jié)構(gòu)密切相關(guān)。設(shè)備管理主要是對設(shè)備進行分配、回收與控制。備外，還包括諸如控制器、通道等支持設(shè)備。盡可能發(fā)揮設(shè)備和主機的并行工作能力。

　　

【正文】 ，一旦 PCB撤消 ， 進程就消亡了 。 具體操作過程是：找到要被撤消進程的 PCB， 將它從所在隊列中銷去 ， 撤消屬于該進程的一切 “ 子孫進程 ” ， 釋放被撤消進程所占用的全部資源 ， 并銷去被撤消進程的 PCB。 第 5章 操作系統(tǒng) 3． 阻塞原語 某進程執(zhí)行過程中 ， 需要執(zhí)行 I/O操作 ， 則由該進程調(diào)用阻塞原語把進程從運行狀態(tài)轉(zhuǎn)換為阻塞狀態(tài) 。 具體操作過程是：由于進程正處于運行狀態(tài) ， 因此首先應(yīng)中斷 CPU執(zhí)行 ， 把 CPU的當(dāng)前狀態(tài)保存在PCB的現(xiàn)場信息中 ， 把進程的當(dāng)前狀態(tài)置為等待狀態(tài) ，并把它插入到該事件的等待隊列中去 。 第 5章 操作系統(tǒng) 4． 喚醒原語 一個進程因為等待事件的發(fā)生而處于等待狀態(tài) ， 當(dāng)?shù)却录瓿珊?， 就用喚醒原語將其轉(zhuǎn)換為就緒狀態(tài) 。 具體操作過程是：在等待隊列中找到該進程 ， 置進程的當(dāng)前狀態(tài)為就緒狀態(tài) ， 然后將它從等待隊列中撤出并插入到就緒隊列中排隊 ， 等待調(diào)度執(zhí)行 。 第 5章 操作系統(tǒng) 進程調(diào)度 進程調(diào)度即處理機調(diào)度 。 在多道程序設(shè)計環(huán)境中 ，進程數(shù)往往多于處理機數(shù) ， 這將導(dǎo)致多個進程互相爭奪處理機 。 進程調(diào)度的任務(wù)是控制 、 協(xié)調(diào)進程對 CPU的競爭 ， 按照一定的調(diào)度算法 ， 使某一就緒進程獲得CPU的控制權(quán) ， 轉(zhuǎn)換成運行狀態(tài) 。 實際上 ， 進程調(diào)度完成把一臺物理的 CPU轉(zhuǎn)變?yōu)槎嗯_虛擬的 (或邏輯的 )CPU的工作 。 第 5章 操作系統(tǒng) 1． 進程調(diào)度的時機 引起進程調(diào)度的原因與操作系統(tǒng)的類型有關(guān) ， 大體可歸結(jié)為以下幾種： (1) 正在執(zhí)行的進程運行完畢； (2) 正在執(zhí)行的進程提出 I/O請求； (3) 正在執(zhí)行的進程執(zhí)行某種原語操作 (如 P操作 )導(dǎo)致進程阻塞； (4) 在分時系統(tǒng)中時間片用完； 第 5章 操作系統(tǒng) 以上都是在 CPU為不可剝奪方式下引起進程調(diào)度的原因 。 在 CPU是可剝奪方式時 ， 還有下面的原因： (5) 就緒隊列中的某個進程的優(yōu)先級變得高于當(dāng)前運行進程的優(yōu)先級時 。 所謂可剝奪方式 ， 即指就緒隊列中一旦有優(yōu)先級高于當(dāng)前運行進程的優(yōu)先級的進程出現(xiàn)時 ， 便立即進行進程調(diào)度 ， 把 CPU分配給高優(yōu)先級的進程 。 所謂不可剝奪方式 ， 即一旦把 CPU分配給一個進程 ， 它就一直占用 CPU， 直到該進程自己因調(diào)用原語操作或等待I/O而進入阻塞狀態(tài) ， 或時間片用完時才讓出 CPU， 引起進程調(diào)度程序的執(zhí)行 。 第 5章 操作系統(tǒng) 2． 進程調(diào)度算法 進程調(diào)度程序的一項重要工作是根據(jù)一定的調(diào)度算法從就緒隊列中選出一個進程 ， 把 CPU分配給它 。因此 ， 調(diào)度算法的好壞直接影響到系統(tǒng)的設(shè)計目標(biāo)和工作效率 。 通常 ， 考慮調(diào)度算法的因素主要是有利于充分利用系統(tǒng)的資源 ， 發(fā)揮最大的處理能力；有利于公平地響應(yīng)每個用戶的服務(wù)請求；有利于操作系統(tǒng)的工作效率 。 下面介紹幾種常用的調(diào)度算法 。 第 5章 操作系統(tǒng) 1) 先來先服務(wù) 如果早就緒的進程排在就緒隊列的前面 ， 遲就緒的進程排在就緒隊列的后面 ， 那么先來先服務(wù) (FCFS，F(xiàn)irst Come First Service)總是把當(dāng)前處于就緒隊列之首的那個進程調(diào)度到運行狀態(tài) 。 也就是說 ， 它只考慮進程進入就緒隊列的先后 ， 而不考慮其它因素 。 FCFS算法簡單易行 ， 但性能卻不太好 。 第 5章 操作系統(tǒng) 2) 最短進程優(yōu)先 最短進程優(yōu)先 (SPF， Shortest Process First)的基本思想是：進程調(diào)度程序總是調(diào)度當(dāng)前就緒隊列中的下一個要求 CPU時間最短的那個進程運行 。 和先來先服務(wù)算法相比 ， SPF調(diào)度算法能有效地降低平均等待時間和提高系統(tǒng)的吞吐量 。 第 5章 操作系統(tǒng) 3) 時間片輪轉(zhuǎn)法 這種算法常用于分時系統(tǒng)中 ， 將 CPU的處理時間劃分成一個個時間片 ， 輪流地調(diào)度就緒隊列中的諸進程運行一個時間片 。 當(dāng)時間片結(jié)束時 ， 就強迫運行進程讓出 CPU， 該進程進入就緒隊列 ， 等待下一次調(diào)度 。同時 ， 進程調(diào)度程序又去選擇就緒隊列中的一個進程 ，分配給它一個時間片 ， 以投入運行 。 第 5章 操作系統(tǒng) 在這個算法中 ， 時間片長度的選擇是一個重要問題 ， 它將直接影響系統(tǒng)開銷和響應(yīng)時間 。 如果時間片長度很小 ， 則調(diào)度程序剝奪處理機的次數(shù)頻繁 ， 加重系統(tǒng)開銷；反之 ， 如果時間片長度選擇過長 ， 用戶進程將不能及時得到響應(yīng) ， 比方說一個時間片就能保證就緒隊列中所有進程都執(zhí)行完畢 ， 輪轉(zhuǎn)法就退化成先來先服務(wù)算法 。 設(shè)置時間片大小通常要考慮到系統(tǒng)的響應(yīng)時間 ， 用戶的數(shù)目以及 CPU的運算速度等因素 。 第 5章 操作系統(tǒng) 4) 優(yōu)先級法 進程調(diào)度程序總是調(diào)度當(dāng)前處于就緒隊列中優(yōu)先級最高的進程 ， 使其投入運行 。 進程的優(yōu)先級通常由進程優(yōu)先數(shù) (整數(shù) )表示 ， 數(shù)大優(yōu)先級高還是數(shù)小優(yōu)先級高取決于規(guī)定 。 例如 UNIX系統(tǒng)規(guī)定優(yōu)先數(shù)越大優(yōu)先級越低 ， 優(yōu)先數(shù)越小優(yōu)先級越高 。 進程優(yōu)先數(shù)的設(shè)置可以是靜態(tài)的 ， 也可以是動態(tài)的 。 靜態(tài)優(yōu)先數(shù)是在進程創(chuàng)建時根據(jù)進程初始特性或用戶要求而確定的 ， 而且該優(yōu)先數(shù)在進程的整個生命周期內(nèi)一直不變 。 動態(tài)優(yōu)先數(shù)則是指在進程創(chuàng)建時先確定一個初始優(yōu)先數(shù) ， 以后在進程運行中隨著進程特性的改變 ， 不斷修改優(yōu)先數(shù) 。 第 5章 操作系統(tǒng) 靜態(tài)優(yōu)先數(shù)方法雖然簡單 ， 但有可能導(dǎo)致某些低優(yōu)先級的進程無限期地等待 ， 尤其在高優(yōu)先級的進程不斷進入就緒隊列的情況下 ， 使等待 CPU的低優(yōu)先級進程更多 ， 等待時間更長 。 動態(tài)優(yōu)先數(shù)方法是按照某種原則使各進程的優(yōu)先級隨著時間而改變 ， 例如隨等待時間增長優(yōu)先級也跟著提高 、 隨著使用 CPU時間的增長優(yōu)先級跟著下降 ， 就是一種較好的策略 ， 等待了較長時間的進程 ， 總會因其優(yōu)先級不斷地提高而被調(diào)度運行 。 優(yōu)先級算法又可與不同的 CPU方式結(jié)合起來 ， 形成可剝奪式優(yōu)先級算法和不可剝奪式優(yōu)先級算法 。 第 5章 操作系統(tǒng) 進程死鎖 1． 死鎖概念 在多道程序系統(tǒng)中，雖可通過多個進程的并發(fā)執(zhí)行來改善系統(tǒng)的資源利用率和提高系統(tǒng)的處理能力，但可能發(fā)生一種危險 —— 死鎖。所謂死鎖 (Deadlock)，是指多個進程因競爭資源而形成的一種僵持局面，若無外力作用，這些進程都將永遠不能再向前推進。例如，設(shè)有 1臺打印機和 1臺磁帶機，有兩個進程 P1和 P2，它們分別占用打印機和磁帶機，當(dāng) P1申請已被 P2占用的磁帶機，而 P2申請已被 P1占用的打印機這種情況出現(xiàn)時， P1和 P2僵持不下，稱為進程死鎖。 第 5章 操作系統(tǒng) 此時操作系統(tǒng)中雖然有死鎖進程出現(xiàn) ， 但系統(tǒng)中其它進程仍然正常工作 。 如果系統(tǒng)中所有進程都進入死鎖 ，即沒有一個進程能前進的話 ， 稱為系統(tǒng)死鎖 ， 這種情況是很少見的 。 人們平常說的 “ 死鎖 ” ， 一般指進程死鎖 ， 它至少涉及兩個進程 。 產(chǎn)生死鎖的根本原因有兩個 。 原因之一是系統(tǒng)內(nèi)的資源數(shù)量不足 。 因為倘若資源數(shù)量無限的話 ， 進程之間就不會發(fā)生資源競爭 ， 當(dāng)然不會形成互不相讓的僵持局面 。 原因之二是進程推進的順序不當(dāng) 。 假如上述進程 P2在 P1已釋放了打印機后才開始運行的話 ， 則不會有競爭出現(xiàn) ， P2便能安全地運行完畢 。 第 5章 操作系統(tǒng) 顯然 ， 任何一個計算機系統(tǒng)的資源都是有限的 ， 資源競爭是不可避免的 ， 換句話說 ， 死鎖的根本原因之一是固有的 。 進程的特性之一就是異步性 ， 因此無法預(yù)知各進程的推進速度 ， 也就無法控制進程之間的推進順序 ， 所以 ， 死鎖的根本原因之二也是固有的 。 第 5章 操作系統(tǒng) 進程的死鎖問題可以用有向圖更加準(zhǔn)確而形象地描述 ， 這種有向圖稱為資源分配圖 。 有向圖中 ， 用圓圈表示進程 ， 用方框表示每類資源 ， 方框中的圓點表示該類資源的數(shù)量 。 申請邊為從進程到資源的有向邊 ，表示進程申請一個資源單位；分配邊為從資源到進程的有向邊 ， 表示有一個資源單位分配給進程 。 申請邊僅能指向方框 ， 表示申請時不具體指定該類資源的哪一個 ， 而分配邊必須由方框中的圓點引出 ， 表明哪一個資源已被占有 。 第 5章 操作系統(tǒng) 圖 57 資源分配圖 (含環(huán)路 ) P1 P2 P3R1 R3R4R2第 5章 操作系統(tǒng) 例如，對于 P={P1,P2,P3}， R={R1,R2,R3,R4}，E={P1,R1， P2,R3， R1,P2， R2,P2， R3,P3，P3,R2， R2,P1}，它的資源分配圖如圖 57所示。 可以證明 ， 如果資源分配圖中沒有環(huán)路 ， 則系統(tǒng)中沒有死鎖；如果圖中存在環(huán)路 ， 則系統(tǒng)中可能存在死鎖 。 如果每個資源類中均只包含一個資源 ， 則環(huán)路的存在即意味著死鎖的存在 ， 此時 ， 環(huán)路是死鎖的充分必要條件 。 在圖 57中 ， 有兩個環(huán)： 第 5章 操作系統(tǒng) P1→R 1→P 2→R 3→P 3→R 2→P 1 P2→R 3→P 3→R 2→P 2 環(huán)中資源類不全為 1(R2有 2個 )， P P P3均處于死鎖狀態(tài) 。 如果刪除邊 R2,P1， 就不會發(fā)生死鎖 。 進一步研究表明 ， 在一個計算機系統(tǒng)中 ， 死鎖的產(chǎn)生有如下 4個必要條件： (1) 互斥使用 。 在一段時間內(nèi) ， 1個資源只能由 1個進程獨占使用 ， 若別的進程也要求使用該資源 ， 則必須等待直至其占用者釋放 。 第 5章 操作系統(tǒng) (2) 不剝奪性 (不可搶占 )。 進程所占用的資源在未使用完之前 ， 不能被其它進程強行剝奪 ， 而只能由占用進程自身釋放 。 (3) 保持和請求 。 允許進程在不釋放其已占用資源的情況下繼續(xù)請求并等待分配新的資源 。 (4) 循環(huán)等待 。 在進程資源圖中存在環(huán)路 ， 環(huán)路中的進程形成等待鏈 。 當(dāng)且僅當(dāng)每類資源只有 1個時 ， 環(huán)路才是進程死鎖的充分必要條件 。 第 5章 操作系統(tǒng) 2． 死鎖排除 1) 死鎖預(yù)防 死鎖預(yù)防是通過破壞 4個必要條件中的 1個或多個以確保系統(tǒng)不會發(fā)生死鎖 。 為此 ， 可以采取下列 3種預(yù)防措施：采用資源的靜態(tài)預(yù)分配策略 ， 破壞 “ 保持和請求 ” 條件；允許進程剝奪使用其它進程占有的資源 ，從而破壞 “ 不剝奪性 ” 條件；采用資源有序分配法 ，破壞 “ 環(huán)路 ” 條件 。 第 5章 操作系統(tǒng) 2) 死鎖避免 死鎖預(yù)防是設(shè)法至少破壞產(chǎn)生死鎖的必要條件之一 ， 嚴(yán)格地防止死鎖的出現(xiàn) 。 而死鎖的避免則不那么嚴(yán)格地限制產(chǎn)生死鎖必要條件的存在 (因為即使死鎖必要條件成立 ， 也未必一定會發(fā)生死鎖 )， 只是在系統(tǒng)運行過程中小心地避免死鎖的最終發(fā)生 。 最著名的死鎖避免算法是 Dijkstra提出的銀行家算法 。 第 5章 操作系統(tǒng) (1) 安全狀態(tài)。在 T0時刻系統(tǒng)是安全的或系統(tǒng)處于安全狀態(tài)，僅當(dāng)存在一個由系統(tǒng)中所有進程構(gòu)成的進程序列 P1， P2， …， Pn，對于每一個進程Pi(i=1,2, …,n)滿足：它以后尚需要的資源數(shù)量不超過系統(tǒng)中當(dāng)前剩余資源與所有進程 Pj(ji)當(dāng)前占有資源數(shù)量之和。如果不存在這樣的序列，則說系統(tǒng)處于一種不安全狀態(tài)。 第 5章 操作系統(tǒng) 例如 ， 考慮一個系統(tǒng) ， 它有 1類設(shè)備 12臺磁帶機和3個進程 P0， P1， P2。 進程 P0