操作系統(tǒng)期末復習

1、操作系統(tǒng)期末復習1 操作系統(tǒng)的類型和功能 馮諾曼機又稱“存儲程序式計算機”，由控制器、運算器、存儲器、輸入裝置、輸出裝置組成。如圖所示。1.1 操作系統(tǒng)的地位 現(xiàn)代計算機系統(tǒng)由硬件和軟件兩部分組成。硬件由中央處理機、存儲器和外部設(shè)備組成，又稱為裸機。軟件由程序、數(shù)據(jù)和文檔資料組成，如下圖所示。1.2 操作系統(tǒng)的類型 自世界上第一臺計算機ENIAC于1946年問世以來，計算機在運算速度、存儲容量、外設(shè)功能、元件工藝及系統(tǒng)結(jié)構(gòu)等方面都有了驚人的發(fā)展。 通常，人們按照計算機元件工藝的演變過程，將其發(fā)展劃分為四個時代。操作系統(tǒng)的歷史操作系統(tǒng)的歷史 操作系統(tǒng)的發(fā)展和計算機的組成與體系結(jié)構(gòu)相關(guān)，經(jīng)歷了四個

2、發(fā)展階段： 1946年50年代末：第一代，電子管時代，無操作系統(tǒng)。 1950年代末60年代中期：第二代，晶體管時代，批處理系統(tǒng)。 操作系統(tǒng)的歷史操作系統(tǒng)的歷史1960年代中期-70年代中期：第三代，集成電路時代，多道程序設(shè)計。1970年代中期至今：第四代，大規(guī)模和超大規(guī)模集成電路時代，分時系統(tǒng)。現(xiàn)代計算機正向著并行化、分布式、網(wǎng)絡(luò)化和智能化幾個方面發(fā)展。一、手工操作階段一、手工操作階段 手工操作過程：手工操作過程： 先把程序紙帶（或卡片）裝上計算機。 然后啟動輸入機把程序和數(shù)據(jù)送入計算機。 接著通過控制臺開關(guān)啟動程序運行。 計算完畢，打印機輸出計算結(jié)果，用戶卸下并取走紙帶（或卡片）。 第二個用

3、戶上機，重復同樣的步驟。 5050年代早期出現(xiàn)了穿孔卡片，程序?qū)懩甏缙诔霈F(xiàn)了穿孔卡片，程序?qū)懺诳ㄆ?，然后讀入計算機，但計算在卡片上，然后讀入計算機，但計算過程則依然如舊過程則依然如舊嚴重缺點：嚴重缺點：用戶一個個、一道道地串行算題，當一個用戶上機時，他獨占了全機資源，造成計算機資源利用率不高，計算機系統(tǒng)效率低下。許多操作要求程序員人工干預，如裝紙帶或卡片、按下開關(guān)等等，手工操作多了，不但浪費處理機時間，而且也極易發(fā)生差錯。由于數(shù)據(jù)的輸入、程序的執(zhí)行、結(jié)果的輸出均是聯(lián)機進行的，因而每個用戶從上機到下機的時間拉得非常長。手工操作存在的問題：手工操作存在的問題：手工操作存在的問題：手工操作存在的

4、問題： 這種人工操作方式在低速機器上還能容忍，但隨著計算機速度的提高，其缺點就都暴露出來了。譬如下圖所示：機器速度作業(yè)在機器上所運行的時間人工操作時間手工操作時間占總運行時間百分比1萬次/秒1小時3分鐘3/(60+3)=4.7%60萬次/秒1分鐘3分鐘3/(1+3)=75% 二、單道批處理系統(tǒng)二、單道批處理系統(tǒng)(simple batch processing)(simple batch processing) 計算機發(fā)展的早期，沒有任何用于管理功能的軟件，所有的運行管理和具體操作都由用戶自己承擔，任何操作出錯都要重做作業(yè)，CPU的利用率甚低。 解決的方法有兩個：單道批處理系統(tǒng)的解決方案單道批處

5、理系統(tǒng)的解決方案: : 首先配備專門的計算機操作員配備專門的計算機操作員，程序員不再直接操作機器，減少操作機器的錯誤。 另一個是進行批處理批處理，操作員把用戶提交的作業(yè)分類，把一批中的作業(yè)編排成一個作業(yè)執(zhí)行序列，每一批作業(yè)將有專門編制的監(jiān)督程序（監(jiān)督程序（monitormonitor）自動依次處理。 批處理中作業(yè)的組成批處理中作業(yè)的組成 包括用戶程序、數(shù)據(jù)和作業(yè)說明書(作業(yè)控制語言)。 “批”的含義：供一次加載的磁帶或磁盤，通常由若干個作業(yè)組裝而成，在處理中使用一組相同的系統(tǒng)軟件(系統(tǒng)帶)。 說明：通常把計算機完成用戶算題任務(wù)所需進行的各項工作稱為一道作業(yè)。Simple Batch Syste

6、m早期批處理方式早期批處理分為兩種：1.1.聯(lián)機批處理聯(lián)機批處理(on line)(on line)2.2.脫機批處理脫機批處理(off line)(off line)1.1.聯(lián)機批處理聯(lián)機批處理在這種批處理方式中，低速的輸入輸出(I/O)處理仍直接由主機來完成。執(zhí)行過程： u 用戶提交作業(yè)：對于作業(yè)、數(shù)據(jù)，可用作業(yè)控制語言編寫作業(yè)說明書； u 作業(yè)以紙帶或卡片為保存介質(zhì)； u 操作員合成批作業(yè)，通過輸入設(shè)備（紙帶輸入機或讀卡機）存入磁帶； u 監(jiān)督程序根據(jù)系統(tǒng)資源情況讀入一個作業(yè)； u 從磁帶讀入?yún)R編或編譯程序，將用戶作業(yè)源程序生成目標代碼； u 連接裝配程序?qū)⒛繕舜a變?yōu)榭蓤?zhí)行程序； u

7、啟動執(zhí)行； u 執(zhí)行完畢，執(zhí)行結(jié)果輸出； a. 讀入另一個作業(yè)，重復過程e-i，直到一批作業(yè)完成。聯(lián)機批處理的優(yōu)缺點聯(lián)機批處理的優(yōu)缺點 聯(lián)機批處理主要優(yōu)點：聯(lián)機批處理主要優(yōu)點：解決了作業(yè)自動轉(zhuǎn)接，減少了作業(yè)建立和手工操作時間。 聯(lián)機批處理存在問題：聯(lián)機批處理存在問題：CPU與I/O之間的串行操作，導致輸入輸出時CPU處于等待狀態(tài)。 2.2.脫機批處理脫機批處理（緩沖技術(shù)的一種）脫機批處理技術(shù)：脫機批處理技術(shù)： 為了解決低速輸入設(shè)備與CPU速度不匹配的問題，可將用戶程序和數(shù)據(jù)，在一臺衛(wèi)星機(又稱外圍計算機)的控制下，預先通過低速輸入設(shè)備輸入到磁帶上。 當CPU需要這些程序和數(shù)據(jù)時，再直接通過磁帶

8、機高速輸入到內(nèi)存，從而大大加快了程序的輸入過程，減少了CPU等待輸入的時間。脫機批處理技術(shù)脫機批處理技術(shù) 當程序運行完畢或告一段落，CPU需要輸出時，也無須等待，直接把計算結(jié)果送至低速輸出設(shè)備，然后在外圍機的控制下，把磁帶上的計算結(jié)果由相應的輸出設(shè)備輸出，這樣大大加快了程序的輸出過程。其示意圖如下圖所示：Operation of I/O DevicesSpooling(假脫機)Spooling實例 Spooling in modern OSMultiple printing tasks in Windows脫機批處理的優(yōu)缺點脫機批處理的優(yōu)缺點脫機批處理主要優(yōu)點：1.主機擺脫了低速I/O的影響，

9、可以較充分地發(fā)揮它的高速計算的能力，提高了CPU的利用率。2.同時，由于主機和衛(wèi)星機可以并行操作，因此相比早期的聯(lián)機批處理系統(tǒng)而言，脫機批處理系統(tǒng)大大提高了系統(tǒng)的處理能力。脫機批處理存在問題：磁帶需要手工拆裝，系統(tǒng)的保護措施不夠。批處理系統(tǒng)小結(jié) 在批處理系統(tǒng)中，操作人員把作業(yè)成批地裝入計算機中。由操作系統(tǒng)在計算機中某個特定區(qū)域（一般稱為輸入井）將其組織好，并按一定的算法選擇其中的一個或幾個作業(yè)，將其調(diào)入內(nèi)存中使其運行。運行結(jié)束后，把結(jié)果放入“輸出井”，由計算機統(tǒng)一輸出交給用戶。 批處理系統(tǒng)的主要優(yōu)點是系統(tǒng)吞吐量大，資源利用率高，主要缺點就是交互性差，一旦作業(yè)提交，其中間過程就很難控制。一道考研

10、題 批處理系統(tǒng)的主要缺點是：(清華大學1996年試題)ACPU利用率低。 B不能并發(fā)執(zhí)行。C缺少交互性。 D以上都不是。 【解答】選擇C。三、多道程序系統(tǒng)三、多道程序系統(tǒng)(multiprogramming system)(multiprogramming system)早期的批處理可能出現(xiàn)兩種情況：早期的批處理可能出現(xiàn)兩種情況： 對于以計算為主的作業(yè)，輸入輸出量少，外圍設(shè)備空閑外圍設(shè)備空閑； 對于以輸入輸出為主的作業(yè)，計算量少，主機空閑。問題的提出 中斷和通道中斷和通道技術(shù)出現(xiàn)以后，I/O設(shè)備和主機可以并行操作，初步解決了高速處理機和低速外設(shè)的矛盾，并提高了計算機的可靠性。 但不久后又發(fā)現(xiàn)這種

11、并行是有限的，并不能完全消除中央處理機對外部傳輸?shù)牡却?。問題的提出 例：一個作業(yè)在運行過程中依次輸入N批數(shù)據(jù)，每批輸入1000個字符。輸入機每輸入1000個字符需用1000ms，而處理機處理這些數(shù)據(jù)則需300ms。 可見：盡管處理機具有和外部設(shè)備并行處理的能力，但是在這種情況下，無法讓處理機多做工作，處理機仍然有空閑等待現(xiàn)象！問題的提出 在早期的單道批處理系統(tǒng)中，內(nèi)存中僅有單個作業(yè)在運行，致使系統(tǒng)中仍有許多資源空閑，設(shè)備利用率低，系統(tǒng)性能較差。 如下圖所示，當CPU工作時，外部設(shè)備處于等待；而外部設(shè)備工作時，CPU處于等待。 單道程序運行圖示 右圖所示為單道程序工作情況，在輸入操作結(jié)束之前，處

12、理機空閑。其原因是本道程序與I/O處理有關(guān)，所以就提出了多道程序的概念。t1t2t用戶程序計算繼續(xù)計算結(jié)束I/OCPU空閑I/O操作monitorI/O請求啟動I/OI/O完成多道程序設(shè)計技術(shù)（多道程序設(shè)計技術(shù)（multiprogrammingmultiprogramming） 若當前作業(yè)因等待若當前作業(yè)因等待I/OI/O而暫停，則而暫停，則CPUCPU只能踏步直至只能踏步直至該該I/OI/O完成。完成。 對于對于CPUCPU操作密集的科學計算問題，操作密集的科學計算問題，CPUCPU浪費時間較浪費時間較少；而對于商業(yè)數(shù)據(jù)處理，少；而對于商業(yè)數(shù)據(jù)處理，I/OI/O等待時間常常占到等待時間常常占

13、到80809090。 解決辦法：解決辦法： 將內(nèi)存分為幾個部分將內(nèi)存分為幾個部分，每部分存放不同的作業(yè)，每部分存放不同的作業(yè)， 當一個作業(yè)等待當一個作業(yè)等待I/OI/O時，另一個作業(yè)可以使用時，另一個作業(yè)可以使用CPUCPU。 在主存中同時駐留多個作業(yè)在主存中同時駐留多個作業(yè)需要硬件進行保護需要硬件進行保護， 以避免信息被竊取或攻擊以避免信息被竊取或攻擊Multiprogramming system three jobs in memory(3rd generation)多道程序設(shè)計(Multiprogramming) 多道程序設(shè)計(Multiprogramming)是指允許多個程序同時進入一

14、個計算機系統(tǒng)的主存儲器，并啟動進行計算的方法。 多道程序合理搭配，輸入輸出為主與計算為主的程序交替地運行，充分利用資源，提高系統(tǒng)效率。多道程序的運行特點多道程序的運行特點多道程序系統(tǒng)的運行特點：多道程序系統(tǒng)的運行特點： 多道：多道：計算機內(nèi)存中同時存放多道相互獨立的程序。 宏觀上并行運行：宏觀上并行運行：同時進入系統(tǒng)的幾道程序都處于運行狀態(tài)，但都未運行完。 微觀上串行運行：微觀上串行運行：各作業(yè)輪流使用CPU，交替執(zhí)行。 此處的并行運行只是邏輯上的并行此處的并行運行只是邏輯上的并行，與物理上的并行是有區(qū)別的。兩道考研題填空題： 1.多道程序的特征之一就是宏觀并行，它的含義是（ ）（2000年，

15、華中科技大學） 2.多道程序設(shè)計的特點是多道、（ ）和（ ）（2000年西安電子科技大學） 答案：1.計算機內(nèi)存中同時存放幾道相互獨立的 程序 2.宏觀上并行、微觀上串行單、多道程序運行示意圖對比單、多道程序運行示意圖對比單道處理與多道處理思考作業(yè)思考作業(yè)例題：有兩道程序例題：有兩道程序A、B，按下圖以多道程序方式運行，按下圖以多道程序方式運行，要求在右圖畫出它們的運行軌跡，并計算在要求在右圖畫出它們的運行軌跡，并計算在60ms內(nèi)，內(nèi)，CPU的利用率的利用率。假設(shè)起始時首先運行假設(shè)起始時首先運行B，并允許忽略監(jiān)督并允許忽略監(jiān)督程序切換程序切換A、B的時間（不考慮的時間（不考慮I/O的沖突）。的

16、沖突）。思考作業(yè)思考作業(yè)非剝奪式多道程序系統(tǒng)的技術(shù)問題多道程序系統(tǒng)的技術(shù)問題（1）并行程序的運行需要共享軟硬件資源，需要同步和互斥機制。（2）多道程序需要提高內(nèi)存的使用效率，需要交換技術(shù)、虛擬存儲等技術(shù)。（3）多道程序在內(nèi)存中要保證系統(tǒng)程序存儲區(qū)和用戶程序存儲區(qū)的安全可靠，需要內(nèi)存保護。 說明：在后續(xù)節(jié)會詳細講到以上技術(shù)一道考研題填空題：為了支持多道程序運行，存儲管理必須要實現(xiàn)的主要功能有（ ）、（ ）和主存擴充。(華中科技大學1997年試題) 【分析】在多道程序的運行環(huán)境下，程序員無法預知存儲管理模塊將把他們的程序分配到主存的什么地方，而且程序員也希望擺脫存儲地址、存儲空間大小等細節(jié)問題，因

17、此存儲管理模塊應該提供地址重定位能力。另外，由于主存中可同時存放多道程序，為了防止程序間相互干擾，存儲管理模塊必須提供存儲保護手段。 【解答】存儲無關(guān)性、存儲保護 四、分時系統(tǒng)(time-sharing system) 分時分時(Time Sharing)(Time Sharing)是把計算機的系統(tǒng)資源（尤其是CPU時間）進行時間上的分割，每個時間段稱為一個時間片(Time Slice)，每個用戶可以依次輪流使用時間片。 分時技術(shù)：分時技術(shù)：把處理機的運行時間分為很短的時間片，按時間片輪流把處理機分配給各個作業(yè)使用。分時系統(tǒng)的定義 分時操作系統(tǒng)（分時操作系統(tǒng)（Time-Sharing Oper

18、ating Time-Sharing Operating SystemSystem）是一種聯(lián)機的多用戶交互式的操作系統(tǒng)。一般采用時間片輪轉(zhuǎn)的方式，使一臺計算機為多個終端服務(wù)，對每個用戶都能夠保證足夠快的響應時間，并提供交互會話的能力。 如下圖所示：分時系統(tǒng)示意圖經(jīng)典案例之一：超市的收銀機分時系統(tǒng)的特點分時系統(tǒng)的特點 交互性：交互性：系統(tǒng)能及時對多個用戶的操作進行響應，縮短了周轉(zhuǎn)時間。 多用戶同時性：多用戶同時性：多個用戶同時工作，共享系統(tǒng)資源，提高了資源利用率。 獨立性：獨立性：各用戶獨立操作，互不干擾。一道考研題 填空題：批處理系統(tǒng)主要解決（ ）問題，分時系統(tǒng)主要解決（ ）問題。(華中科技大

19、學2002) 答案：吞吐量 交互性五、實時系統(tǒng)(real-time system) 產(chǎn)生背景：雖然多道批處理操作系統(tǒng)和分時操作系統(tǒng)獲得了較佳的資源利用率和快速的響應時間，從而使計算機的應用范圍日益擴大，但它們難以滿足實時控制和實時信息處但它們難以滿足實時控制和實時信息處理領(lǐng)域的需要理領(lǐng)域的需要。 于是，便產(chǎn)生了實時操作系統(tǒng)，目前有三種典型的實時系統(tǒng)：過程控制系統(tǒng)、信息查詢過程控制系統(tǒng)、信息查詢系統(tǒng)和事務(wù)處理系統(tǒng)系統(tǒng)和事務(wù)處理系統(tǒng)。 什么是實時系統(tǒng)？ 實時操作系統(tǒng)（Real-Time Operating System）是指當外界事件或數(shù)據(jù)產(chǎn)生時，能夠接收并以足夠快的速度予以處理，其處理的結(jié)果又可

20、在規(guī)定的時間內(nèi)控制監(jiān)控的生產(chǎn)過程或?qū)μ幚硐到y(tǒng)作出快速響應的操作系統(tǒng)。 實時系統(tǒng)要求有高可靠性和安全性，系統(tǒng)的效率則放在第二位。實時系統(tǒng)的重要特征 實時操作系統(tǒng)的一個最重要的特征就是必須滿足控制對象的截止期限的要求，若不能滿足這一時間約束則一般認為系統(tǒng)失敗。 實時操作系統(tǒng)的另一個重要特征是可預測性分析，操作系統(tǒng)功能應該具有有限的、已知的執(zhí)行時間。六、操作系統(tǒng)的進一步發(fā)展 從20世紀80年代以來，操作系統(tǒng)得到了進一步的發(fā)展。促使其發(fā)展的原因有兩個：一是微電子技術(shù)、計算機技術(shù)的迅速發(fā)展，二是用戶的需求不斷提高。 主要包括：個人計算機操作系統(tǒng)，網(wǎng)絡(luò)操作系統(tǒng)，分布式操作系統(tǒng)，嵌入式操作系統(tǒng)，智能化操作系

21、統(tǒng)。1.3 操作系統(tǒng)的資源管理功能操作系統(tǒng)的核心任務(wù)就是系統(tǒng)資源的分配和管理，其目標是要提高系統(tǒng)資源的利用率和方便用戶使用。操作系統(tǒng)具有如下幾個資源管理功能：l處理機管理l存儲管理l設(shè)備管理l文件系統(tǒng)（一）處理機管理（即進程管理） 在多道程序或多用戶的情況下，需要組織多個作業(yè)同時運行，必須要解決對處理機分配調(diào)度、分配實施和資源回收等問題。 調(diào)度策略：確定多個用戶/程序使用處理機的原則，各自占用處理機的時間；給出調(diào)度算法，并實施具體的處理機分派。 （二）存儲管理存儲管理的主要任務(wù)是管理存儲器資源，為多道程序運行提供有力的支撐。存儲管理的主要功能包括： (1)存儲分配與回收：存儲管理將根據(jù)用戶程序

22、需要給它分配存儲器資源，并在其使用完畢后回收。 (2)存儲保護：存儲管理要把各個用戶程序相互隔離起來互不干擾，更不允許用戶程序訪問操作系統(tǒng)中的程序和數(shù)據(jù)，從而保護用戶程序存放在存儲器中的信息不被破壞。 （二）存儲管理(3) 地址映射（變換）：負責進程邏輯地址到內(nèi)存物理地址的映射。這樣程序員無需知道自己的程序被分配到內(nèi)存的什么具體物理地址，僅要知道自己的邏輯地址即可，體現(xiàn)了存儲的無關(guān)性。(4) 內(nèi)存擴充：由于物理內(nèi)存容量有限，難于滿足用戶程序的需求，存儲管理還應該能從邏輯上來擴充內(nèi)存儲器，為用戶提供一個比實際內(nèi)存容量大得多的空間，方便用戶的使用，實現(xiàn)虛擬內(nèi)存。（三）設(shè)備管理設(shè)備管理的主要任務(wù)是：

23、管理分配各類外圍設(shè)備，完成用戶提出的I/O請求，加快I/O信息的傳送速度，發(fā)揮I/O設(shè)備的并行性，提高I/O設(shè)備的利用率； 提供各種設(shè)備的驅(qū)動程序和中斷處理程序，向用戶屏蔽硬件使用細節(jié)。（四）文件系統(tǒng) 上述三種管理都是針對計算機硬件資源的管理，文件系統(tǒng)則是對計算機軟件資源的管理。 在現(xiàn)代計算機中，通常把程序和數(shù)據(jù)以文件形式存儲在外存儲器上，供用戶使用。這樣外存儲器上保存了大量文件，對這些文件如不能采取良好的管理方式，就會導致混亂或破壞，造成嚴重后果。（四）文件系統(tǒng)為此，在操作系統(tǒng)中配置了文件系統(tǒng)，它的主要任務(wù)是：u 對用戶文件和系統(tǒng)文件進行有效管理，以實現(xiàn)按名存取；u 提供給用戶一套能方便使用

24、文件的操作和命令。 實現(xiàn)文件的共享、保護和保密，保證文件的安全性；補充解釋幾個重要術(shù)語1.什么是進程 進程的定義：一個具有一定獨立功能的程序在某個數(shù)據(jù)集合上的一次動態(tài)執(zhí)行過程。進程與程序的區(qū)別進程是一個動態(tài)的概念，而程序則一個是靜態(tài)的概念。程序是指令的有序集合，沒有任何執(zhí)行的含義。而進程則強調(diào)執(zhí)行過程，它動態(tài)地被創(chuàng)建，并被調(diào)度執(zhí)行后消亡。進程是一個能獨立運行的單位，能與其它進程并行活動，具有并行特性，而程序沒有。進程是競爭計算機系統(tǒng)資源的基本單位，也是進也是進行處理機調(diào)度的單位行處理機調(diào)度的單位。同一個程序同時運行于若干不同的數(shù)據(jù)集合上，它將屬于若干個不同的進程。2.什么是線程線程 早期，進程

25、是操作系統(tǒng)中資源分配以及系統(tǒng)調(diào)度的獨立單位。 由于每個進程擁有自己獨立的存儲空間和運行環(huán)境，進程和進程之間并發(fā)性粒度較粗，通信和切換的開銷相當大。 要更好地發(fā)揮硬件提供的能力（如多CPU），以及實現(xiàn)復雜的各種并發(fā)應用，單靠進程是無能為力的，于是近年來開始流行多線程（結(jié)構(gòu)）進程（Multithreaded process），也稱多線程。2.什么是線程線程 線程是進程中一條執(zhí)行路徑，每個進程中允許有多個并行執(zhí)行的路徑。 在一個多線程環(huán)境中，進程是進行系統(tǒng)保護和資源分配的單位，而線程才是進行系統(tǒng)調(diào)度的單位。 在一個進程中包含有多個可并發(fā)執(zhí)行的控制流，而不是把多個控制流一一分散在多個進程中，這是并發(fā)多

26、線程程序設(shè)計與并發(fā)多進程程序設(shè)計的主要不同之處。3.什么是原語？ 所謂原語（service primitive），是操作系統(tǒng)內(nèi)核中，由若干條指令構(gòu)成、用于完成某一特定功能的一個過程，該過程在執(zhí)行時是不可中斷的。 例如，創(chuàng)建進程原語create(n)，撤銷進程原語kill(n)，阻塞進程原語susp(n)，喚醒進程原語wakeup(n)。 4.中斷機制 中斷(interrupt)(interrupt)是指程序執(zhí)行過程中，當發(fā)生某個事件(例如電源掉電、定點加法溢出或I/O傳輸結(jié)束等)時，中止CPUCPU對現(xiàn)行程序的運行，引出處理該事件的服務(wù)程序的執(zhí)行過程，處理完畢后再返回斷點繼續(xù)執(zhí)行。中斷技術(shù) 這

27、種處理突發(fā)事件的能力是由硬件和軟件協(xié)作完成的。 首先，由硬件的中斷裝置發(fā)現(xiàn)產(chǎn)生的中斷事件，然后，中斷裝置中止現(xiàn)行程序的執(zhí)行，引出處理該事件的程序來處理。中斷技術(shù)在不同的硬件結(jié)構(gòu)中，通常有不同的中斷源和中斷裝置，但它們都有一個共性： 當中斷事件發(fā)生后，中斷裝置能改變處理器內(nèi)操作執(zhí)行的順序。由此可見，中斷是現(xiàn)代操作系統(tǒng)實現(xiàn)并發(fā)性和自動化的基礎(chǔ)之一。整個中斷處理流程的軟硬件分工圖2 處理機管理2.1 進程的概念 在多道程序設(shè)計的環(huán)境下，為了描述程序在計算機系統(tǒng)內(nèi)的執(zhí)行情況，必須引人新的概念進程。 進程的概念來自于麻省理工的MULTICS、IBM的TSS/360，在IBM的OS/360/370系統(tǒng)中也

28、曾稱作任務(wù)（task)。一、進程的定義 行為的一個規(guī)則叫做程序，程序在處理機上執(zhí)行時所發(fā)生的活動稱為進程（Dijkstra)。 進程是這樣的計算部分，它是可以和其它計算并行的一個計算。(Donovan) 進程（有時稱為任務(wù)）是一個程序與其數(shù)據(jù)一道通過處理機的執(zhí)行所發(fā)生的活動。（Alan.C. Shaw) 進程是執(zhí)行中的程序。（Ken Thompson and Dennis Ritchie ) 進程是指一個具有一定獨立功能的程序關(guān)于某個數(shù)據(jù)集合的一次運行活動。進程與程序的區(qū)別與聯(lián)系： 程序是指令的集合，是靜態(tài)的概念。進程是程序在處理機上的一次執(zhí)行的過程，是動態(tài)的概念。程序可以作為軟件資料長期保存

29、，而進程是有生命周期的。 進程是一個能獨立運行的單位，且能與其它進程并行（并發(fā)）活動，而程序則不是。 進程是競爭計算機系統(tǒng)有限資源的基本單位，也是進行處理機調(diào)度的基本單位。 一個程序可以作為多個進程的運行程序，一個進程也可以運行多個程序。二、進程的狀態(tài)進程在系統(tǒng)中的活動規(guī)律是：執(zhí)行暫停執(zhí)行進程的三種基本狀態(tài)：就緒狀態(tài)運行狀態(tài)等待狀態(tài)（又稱阻塞、掛起、睡眠）進程的基本狀態(tài)1、就緒狀態(tài)（Ready) 存在于處理機調(diào)度隊列中的那些進程，它們已準備就緒，一旦得到CPU控制權(quán)，就可以立即運行，這些進程所處狀態(tài)為就緒狀態(tài)。（可有多個進程處于此狀態(tài)）2、運行狀態(tài)(Run） 當進程由調(diào)度/分派程序分派后，得到

30、CPU控制權(quán)，它的程序正在運行，該進程所處的狀態(tài)為運行狀態(tài)。（在系統(tǒng)中，某一時刻只有一個進程處于此狀態(tài)，這也就是所謂的微觀上串行。）3、等待狀態(tài)（Wait) 若一個進程正在等待某個事件的發(fā)生（如等待I/O的完成）而暫停執(zhí)行，這時即使給它CPU運行時間，它也無法執(zhí)行，則稱該進程處于等待狀態(tài)，又稱為阻塞狀態(tài)。進程狀態(tài)變遷圖 進程狀態(tài)不是固定不變的，而是在不斷變換。如下圖所示：A Three-state Process ModelReadyRunningBlockedEventOccursDispatchTime-outEventWait在進程運行過程中，由于進程自身進展情況及外界環(huán)境的變化，這三種

31、基本狀態(tài)可以依據(jù)一定的條件相互轉(zhuǎn)換：就緒運行（進程調(diào)度）運行就緒（時間片到、某高優(yōu)先級進程處于就緒狀態(tài)等）運行等待（服務(wù)請求，如請求I/O等）等待就緒（服務(wù)完成/事件來到）進程狀態(tài)轉(zhuǎn)換2.2 進程控制塊(1)什么是進程控制塊？ 描述進程與其他進程、系統(tǒng)資源的關(guān)系，以及進程在各個不同時期所處狀態(tài)的數(shù)據(jù)結(jié)構(gòu)，稱為進程控制塊pcb(process control block)或稱為進程描述器(process descriptor)。2.2 進程控制塊 系統(tǒng)利用PCB來控制和管理進程，所以PCB是系統(tǒng)感知進程存在的唯一標志。 進程與PCB是一一對應的。進程控制塊 進程控制塊PCB集中反映了一個進程的動

32、態(tài)特征。 在進程并發(fā)執(zhí)行時，由于資源共享，帶來各進程之間的相互制約。 顯然，為了反映這些制約關(guān)系和資源共享關(guān)系，在創(chuàng)建一個進程時，應首先創(chuàng)建其PCB，然后才能根據(jù)PCB中的信息對進程實施有效的管理和控制。 當一個進程完成其功能后，系統(tǒng)便釋放PCB，進程也隨之消亡。PCB的結(jié)構(gòu)PCB的結(jié)構(gòu)說明 進程標識符 name：每個進程都必須有一個唯一的標識符，可以是字符串，也可以是一個數(shù)字。（標識信息）UNIX系統(tǒng)中就是一個整型數(shù)，在進程創(chuàng)建時由系統(tǒng)賦予。 進程當前狀態(tài) status：說明本進程目前處于何種狀態(tài)（運行、就緒、等待），以作為進程調(diào)度/分配時的主要依據(jù)。（說明信息）PCB的結(jié)構(gòu)說明 當前隊列指

33、針 next： 登記與本進程處于同一隊列的下一個進程的PCB的地址。PCB的結(jié)構(gòu)說明 總鏈指針 all-q-next：登記在系統(tǒng)總鏈隊列中的下一個進程的pcb地址。 執(zhí)行程序開始地址 start-addr：該進程的程序?qū)拇说刂烽_始執(zhí)行。 進程優(yōu)先級 priority： 進程的優(yōu)先級反映了進程的緊迫程度，通常由用戶指定和系統(tǒng)設(shè)置。（管理信息） PCB的結(jié)構(gòu)說明 CPU現(xiàn)場保護區(qū) cpustatus：當進程由于某種原因釋放處理機時，CPU現(xiàn)場信息被保存在pcb的該區(qū)域中，以便該進程重新獲得處理機后可繼續(xù)執(zhí)行。（現(xiàn)場信息）通常被保護的信息有：工作寄存器、指令計數(shù)器以及程序狀態(tài)字等。2.3 進程的通

34、信控制 在多道程序的環(huán)境中，系統(tǒng)中的多個進程可以并發(fā)執(zhí)行，同時它們又要共享系統(tǒng)中的資源。這些資源有些是可共享使用的，如磁盤，有些是以獨占方式使用的，如打印機。由此可能會引起一系列的矛盾，產(chǎn)生錯綜復雜的相互制約關(guān)系。 產(chǎn)生這種錯綜復雜的相互制約關(guān)系的原因：資源共享，即由于競爭系統(tǒng)資源而引起的間接相互制約關(guān)系；進程合作，即由于進程之間存在共享數(shù)據(jù)而引起的直接相互制約關(guān)系。進程間的關(guān)系 進程之間的直接相互制約是通過進程通信來實現(xiàn)的，它們之間需要交換信息以便達到協(xié)作的目的。進程通信關(guān)系又可細分為：進程互斥、進程同步和進程間的直接通信。 進程的互斥(Mutual Exclusion)是指若干個進程要使用

35、同一共享資源時，任何時刻最多允許一個進程去使用，其它要使用該資源的進程必須等待，直到占有資源的進程釋放該資源。進程間的關(guān)系 進程的同步(Synchronization)是解決進程間協(xié)作關(guān)系的手段。指一個進程的執(zhí)行依賴于另一個進程的消息，當一個進程沒有得到來自于另一個進程的消息時需要等待，直到消息到達才被喚醒。 不難看出，進程互斥關(guān)系是一種特殊的進程同步關(guān)系。一、進程互斥引例：宿舍固定電話的使用打印機的使用1. 內(nèi)存變量、指針、數(shù)組等等也是臨界資源臨界資源說明例1：現(xiàn)有兩個進程A、B共享一臺打印機，若不加以控制，兩個進程的輸出結(jié)果可能交織在一起，很難區(qū)分。 臨界資源說明 例2：現(xiàn)有兩個進程共享一

36、個變量x，假設(shè)x為某航班機座號，p1和p2為兩個售票進程，售票工作是對變量x加1。 這兩個進程在一個處理機上并發(fā)執(zhí)行，分別具有內(nèi)部寄存器r1和r2，兩個進程共享一個變量x時，有兩種可能的執(zhí)行次序： 情況B為 x = 10+1 臨界資源說明 上述問題稱之為與時間有關(guān)的錯誤，其實就是因為共享變量，這個共享的變量就是臨界資源。 如果不對臨界資源加以控制，那么就可能出現(xiàn)錯誤，這就是本小節(jié)要解決的問題。什么是臨界資源 特點：當兩個進程共用一個變量時，它們必須順序地使用，一個進程對公用變量操作完畢后，另一個進程才能去訪問和修改這一變量。 一次僅允許一個進程使用的資源稱為臨界資源。 哪些是臨界資源臨界資源：

37、物理設(shè)備，如輸入機、打印機、磁帶機等都具有這種性質(zhì)。 1. 軟件資源，如公用變量、數(shù)據(jù)、表格等也都具有這一特點。什么是臨界區(qū) 臨界區(qū)：在每個進程中，訪問臨界資源的那段程序能夠從概念上分離出來，稱之為臨界區(qū)或臨界段。 它就是進程中對公共變量(或存儲區(qū))進行審查與修改的程序段，稱為相對于該公共變量的臨界區(qū)。什么是臨界區(qū)什么是臨界區(qū)什么是互斥 互斥：在操作系統(tǒng)中，當某一進程正在訪問某一存儲區(qū)域時，就不允許其他進程來讀出或修改該存儲區(qū)的內(nèi)容，否則就會發(fā)生無法估計的錯誤。 進程間的這種相互制約關(guān)系稱為互斥。 如上圖所示，進程A正在執(zhí)行csa段時，進程B就不能進入csb段執(zhí)行。進入臨界區(qū)的準則進入臨界區(qū)的

38、準則：(1)當有若干個進程欲進入臨界區(qū)時，應 在有限的時間內(nèi)使其進入； (2)每次最多有一個進程處于臨界區(qū)；(3)進程在臨界區(qū)內(nèi)僅逗留有限的時間。信號燈 1965年荷蘭的計算機科學家Dijkstra提出了新的同步工具信號量和P、V操作。 他將交通管制中利用多種顏色的信號燈管理交通的方法引入操作系統(tǒng)，讓兩個或多個進程通過信號量(Semaphore)展開交互。 進程在某一特殊點上停止執(zhí)行直到得到一個對應的信號量。通過信號量這一設(shè)施，任何復雜的進程交互要求都可得到滿足。信號燈的概念 信號量僅能由同步原語對其進行操作。原語是指操作系統(tǒng)中執(zhí)行時不可中斷的過程，即原子操作(Atomic Action)。

39、Dijkstra發(fā)明了兩個同步原語：P操作和V操作(荷蘭語中“測試Proberen”和“增量Verhogen” 的頭字母)。 本書采用Dijkstra最早論文中使用的符號P和V。利用信號量和P、V操作既可以解決并發(fā)進程的協(xié)作問題，又可以解決并發(fā)進程的競爭問題。信號燈的概念信號燈的定義： 信號燈是一個確定的二元組（s,q），s是一個具有非負初值的整型變量，q是一個初始狀態(tài)為空的隊列。 s代表資源的實體，在實際應用中應準確地說明s的意義和初值。而每個信號燈都有相應的一個隊列，其初始狀態(tài)為空。P、V操作信號燈的值僅能由P、V操作來改變， 對信號燈的P操作記為：P(S)，P操作是一個原子操作。 對信號

40、燈的V操作記為：V(S), V操作是一個原子操作。信號量的物理意義 信號燈是整型變量： 變量值0時，表示綠燈，進程繼續(xù)執(zhí)行。 變量值0：其數(shù)值代表可用的資源數(shù)量S=0：代表無資源可用，但也沒有等待的進程，即也沒有申請資源的進程S0：S代表可用的資源數(shù)量S=0：代表無資源可用，但也沒有等待的進程，即也沒有申請資源的進程S=0，不能為負值P和V的位置放置：對于互斥：P、V操作在同一個進程中對于同步：P、V操作在不同進程中3.生產(chǎn)者消費者問題 問題描述：若干進程通過有限的共享緩沖區(qū)交換數(shù)據(jù)。其中，“生產(chǎn)者”進程不斷寫入，而“消費者”進程不斷讀出，且任何時刻只能有一個進程可對共享緩沖區(qū)進行操作，假設(shè)共

41、享緩沖區(qū)共有N個。 即滿足如下條件：（1）消費者想接收數(shù)據(jù)時，有界緩沖區(qū)中至少有一個單元是滿的。（2）生產(chǎn)者想發(fā)送數(shù)據(jù)時，有界緩沖區(qū)中至少有一個單元是空的。生產(chǎn)者消費者例子 例1：計算進程和打印進程 計算進程cp不斷產(chǎn)生數(shù)據(jù)，是生產(chǎn)者；打印進程iop不斷打印數(shù)據(jù)，是消費者。 例2：通信問題 發(fā)消息進程send不斷產(chǎn)生消息，是生產(chǎn)者； 收消息進程receive不斷接收消息，是消費者。 生產(chǎn)者消費者問題圖示生產(chǎn)者消費者之間的關(guān)系一、同步關(guān)系：對于生產(chǎn)者進程：產(chǎn)生一個數(shù)據(jù)，當要送入緩沖區(qū)時，檢查緩沖區(qū)是否已滿，若未滿，則可將數(shù)據(jù)送入緩沖區(qū)并通知消費者進程，否則，等待；對于消費者進程：當它取數(shù)據(jù)時，要

42、看緩沖區(qū)中是否有數(shù)據(jù)可取，若有則取走一個數(shù)據(jù)，并通知生產(chǎn)者進程，否則，等待；1. 這種相互等待并互通消息就是一種典型的進程同步。生產(chǎn)者消費者之間的關(guān)系二、互斥關(guān)系：緩沖區(qū)同時又是個臨界資源。當有多個進程在生產(chǎn)產(chǎn)品時，不允許在緩沖區(qū)的某一個單元同時存放產(chǎn)品，也不允許多個進程同時消費緩沖區(qū)中的某一個單元產(chǎn)品。因此，兩者還有個互斥的問題。生產(chǎn)者消費者問題的一般解答信號燈設(shè)置： 兩個同步信號燈empty:表示空緩沖區(qū)的數(shù)目，初值為有界緩沖區(qū)的大小n； full:表示滿緩沖區(qū)的數(shù)目，初值為0； 一個互斥信號燈mutex：互斥信號燈，初值為1。生產(chǎn)者消費者問題的一般解答程序描述程序描述思考 在這個問題中，

43、P操作的次序是很重要的。如果我們把生產(chǎn)者進程中的兩個P操作次序顛倒，那么會有什么問題嗎？參見下圖的程序:分析 假設(shè)在某個時刻，生產(chǎn)者生產(chǎn)得比較快，把所有的緩沖區(qū)用完，則有empty=0，full=n，mutex=1。 接著生產(chǎn)者進程運行到1處，使得mutex=0，運行到2處，empty=-10，生產(chǎn)者進程進入等待。 接著消費者進程運行到3處，使得full=n-1，運行到4處，mutex=-10，表示有S個資源可用 S=0，表示無資源可用 S0，|S|表示S等待隊列中的進程個數(shù) P(S)：表示申請一個資源，但可能申請不成功 V(S)：表示釋放一個資源，有可能會喚醒等待 進程信號量及P、V操作總結(jié)

44、2)P、V操作必須成對出現(xiàn)，有一個P操作就一定有一個V操作：當為互斥操作時，它們處于同一進程中當為同步操作時，則分別在不同進程中出現(xiàn)如果兩個P操作在一起，那么P操作的順序就至關(guān)重要，一個同步P操作與一個互斥P操作在一起時，同步P操作須在互斥P操作之前；而兩個V操作的順序則無關(guān)緊要信號量及P、V操作總結(jié)3)P、V操作的優(yōu)缺點：優(yōu)點：簡單且表達能力強（用P、V操作可解決任何同步/互斥問題）缺點：不夠安全（P、V操作若使用不當會導致死鎖）信號量及P、V操作總結(jié)2.4 死鎖2.4.1 死鎖的概念操作系統(tǒng)的基本特征是并發(fā)與共享。系統(tǒng)允許多個進程并發(fā)執(zhí)行，并且共享系統(tǒng)的軟、硬件資源。為了最大限度地利用計算

45、機系統(tǒng)的資源，操作系統(tǒng)應采用動態(tài)分配系統(tǒng)各種資源的策略。然而采用這種策略時，若分配不當，可能出現(xiàn)進程之間互相等待資源、又都不能向前推進的情況，即造成進程相互死等的局面。2.4.1 死鎖的概念事實上，不同進程對資源的申請可能按某種先后次序得到部分滿足，這就可能造成其中的兩個或幾個進程彼此間相互封鎖的情況，即每個進程都抓住一些為其他進程所等待的資源不放，其結(jié)果是誰也得不到它所申請的全部資源，這些進程最終也都無法運行。例子：銀行家問題銀行共有資金10萬，客戶u1需貸款3萬，客戶u2需貸款8萬，客戶u3需貸款9萬。某一時刻： u2u3u1 已貸款還需資金1萬2萬2萬6萬6萬3萬銀行只剩下銀行只剩下一萬

46、，造成一萬，造成死鎖死鎖。貸不到款，客戶死貸不到款，客戶死收不回款，銀行家死收不回款，銀行家死2.4.1 死鎖的概念死鎖的定義： 在一組并發(fā)進程中，每個進程持有某種資源，同時又都等待著被該組進程中其它進程所占有的資源，最終將無限期地僵持下去。這種現(xiàn)象稱為進程死鎖，而這一組進程就稱為死鎖進程。設(shè)S1=1，打印機可用；S2=1，讀卡機可用。OS中的例子 操作系統(tǒng)中的例子現(xiàn)有二個進程P1、P2，兩個設(shè)備打印機R1、讀卡機R2 。 P(S1)； P(S2)； P(S2)； P(S1)； V(S1)； V(S2)； V(S2)； V(S1)； P1P2 P(S1)； P(S2)； V(S1)； V(S2

47、)； P(S2)； P(S1)； V(S2)； V(S1)； P1P2P1P2P1P2？ 兩種寫法，誰可能造成死鎖？死鎖wait 原因：原因：1）系統(tǒng)資源不足系統(tǒng)資源不足 w產(chǎn)生死鎖的根本原因是：系統(tǒng)能夠提供的資源數(shù)目 要求該資源的進程數(shù)目結(jié)論與問題：死鎖一定是由于系統(tǒng)資源不足所引起的，但系統(tǒng)資源不足是否就一定造成死鎖呢？2）聯(lián)合推進路線非法聯(lián)合推進路線非法w進程推進順序不當2.4.2 產(chǎn)生死鎖的原因和必要條件A2B2C2D2申請r1申請r2釋放r2釋放r1A1B1C1D1申請r1申請r2釋放r1釋放r2兩進程均占用r1兩進程均占用r2xyP2進展P1進展0A 死鎖點2.4.2 產(chǎn)生死鎖的原因

48、和必要條件產(chǎn)生死鎖的原因和必要條件路線1路線2tt2.4.2 產(chǎn)生死鎖的原因和必要條件 1971年Coffman總結(jié)出了系統(tǒng)產(chǎn)生死鎖的四個必要條件必要條件：互斥條件（mutual exclusion）不可剝奪條件（no preemption）占有并等待條件（hold and wait）1.循環(huán)等待條件（circular wait）互斥條件（mutual exclusion）：進程應互斥使用資源，即涉及的資源必須是非共享使用的，任一時刻一個資源僅為一個進程獨占使用。另一個進程去請求一個已被占用的資源時，將被置為等待狀態(tài)，直到占用者釋放資源。2.4.2 產(chǎn)生死鎖的原因和必要條件 不可剝奪條件，或稱

49、非搶占條件（no preemption）：任一進程不能從另一個進程那里搶奪已被占用而未使用完畢的資源，只能由占用進程自己來釋放。2.4.2 產(chǎn)生死鎖的原因和必要條件 w占有并等待條件，或稱部分分配條件（hold and wait）：進程每次只申請它當前所需要的那部分資源，且在等待另一新資源的同時繼續(xù)占用已分配的資源。2.4.2 產(chǎn)生死鎖的原因和必要條件 循環(huán)等待條件，或稱環(huán)路條件（circular wait）：存在著一個進程的循環(huán)等待鏈，其中每一個進程都在等待前一個進程所持有的資源，造成無限期等待。2.4.2 產(chǎn)生死鎖的原因和必要條件 2.4.3 解決死鎖問題的策略一、解決死鎖問題的幾個策略為

50、了不發(fā)生死鎖，必須設(shè)法破壞產(chǎn)生死鎖的四個必要條件之一。條件1（互斥條件）：難以否定，因為這是由某些資源的性質(zhì)所決定的，即使采用了虛擬設(shè)備技術(shù)，也不能完全排除非共享使用設(shè)備死鎖的可能性。條件2（不可剝奪條件）：很容易否定的，只要制定相應的規(guī)則即可，例如當一個進程（程序）申請某資源被拒絕時，則必須要釋放已占用的資源，如果需要再與其它所需資源一起申請。然而，實現(xiàn)這種策略并不容易，一方面會造成資源被搶占后交叉處理的情況，另一方面為了保護和恢復資源被搶占時的狀態(tài)將花費很大的開銷。一般只將處理機看作可被迫搶占的資源。2.4.3 解決死鎖問題的策略條件3（占有并等待條件）：容易否定，也容易實現(xiàn)，只要在分配策

51、略上規(guī)定一個進程（程序）必須一次性將所需資源申請到位，系統(tǒng)就不會出現(xiàn)死鎖。在具體的資源分配策略上，可以采取靜態(tài)資源分配的方式，一次性把所需資源全部分配到位，進程在沒有獲得全部資源之前不能投入運行。2.4.3 解決死鎖問題的策略條件4（循環(huán)等待條件）：通過有序資源分配法，可以破壞環(huán)路條件。靜態(tài)資源分配方法是一種保守的靜態(tài)預防死鎖的方法，其缺點是被分配的資源可能有的使用時間很短，但在被占用期間其它進程長時間內(nèi)不能訪問它們，使得資源利用率很低。為克服這一缺點，希望仍用動態(tài)資源分配的方法，但又要能預防死鎖的發(fā)生，于是只能從最后一個條件入手。2.4.3 解決死鎖問題的策略歸納起來，可以采用以下策略之一來

52、解決死鎖問題：采用靜態(tài)資源分配方法預防死鎖采用動態(tài)資源分配、有控分配方法來避免死鎖允許死鎖發(fā)生，當死鎖發(fā)生時能檢測出死鎖，并設(shè)法修復忽略死鎖，即鴕鳥算法，這種方法為絕大多數(shù)操作系統(tǒng)（如UNIX系統(tǒng)）所采用2.4.3 解決死鎖問題的策略為了研究解決死鎖的方法，可借助于系統(tǒng)狀態(tài)分析和資源分配圖等工具。系統(tǒng)狀態(tài)分析可以幫助確定某一時刻系統(tǒng)是否處于一個合理的狀態(tài)，只有保證系統(tǒng)狀態(tài)是合理的才能防止死鎖的發(fā)生。系統(tǒng)狀態(tài)是根據(jù)進程對資源的申請、獲得使用和釋放而改變的，故必須要說明每個時刻進程對資源的請求和占有情況；系統(tǒng)狀態(tài)分析在某一給定時刻t，系統(tǒng)狀態(tài)由資源分配矩陣a(t)和資源請求矩陣d(t)來描述，它們

53、分別表示當前已分配給各進程的各類資源數(shù)目以及這些進程在時刻t還需申請各類資源的最大需求量；系統(tǒng)的狀態(tài)只能通過申請資源、獲得使用資源和釋放資源這三種操作來改變；系統(tǒng)狀態(tài)分析在一個系統(tǒng)中，若滿足下述條件，則認為系統(tǒng)狀態(tài)是合理的，可以防止死鎖的發(fā)生。w一個給定進程，不能申請比系統(tǒng)中所擁有的該類資源數(shù)還要多的資源；w在每一時刻，每個進程都不會擁有它未曾申請的資源。w在每一時刻，所有進程所接收到的某類資源總數(shù)也不能超過系統(tǒng)所擁有的該類資源總數(shù)；系統(tǒng)狀態(tài)分析資源分配圖是一種有關(guān)系統(tǒng)資源分配的有向圖，它可以更為精確地描述死鎖現(xiàn)象。該有向圖由一個節(jié)點集合和一個邊集合組成，其中節(jié)點集合又分為系統(tǒng)活動進程集合和系

54、統(tǒng)所有資源類型集合。在系統(tǒng)資源分配的有向圖中，以方框代表資源節(jié)點、圓圈代表進程節(jié)點。由于資源類型可能有多個實例，所在在方框中還可以用圓點表示其實例數(shù)。資源分配圖從進程節(jié)點到資源類型節(jié)點的有向邊稱為資源的請求邊，表示進程已申請了資源類型的一個實例，但當前正處于阻塞狀態(tài)，等待資源變?yōu)榭捎谩馁Y源類型節(jié)點到進程節(jié)點的有向邊稱為資源的分配邊，表示資源類型的一個實例已分配給進程；資源分配圖RASBTDUC(a)進程A分配了一個資源(b)進程B請求了一個資源(c)進程C和進程D形成環(huán)路，已處于死鎖狀態(tài)資源分配圖根據(jù)上述資源分配圖的定義，不難理解：如果圖沒有環(huán)，那么系統(tǒng)就不會發(fā)生死鎖；如果圖有環(huán)，那么可能會

55、出現(xiàn)死鎖，此時需要取決于環(huán)中所涉及的每個資源類型包含的實例數(shù)目。資源分配圖2.4.4 死鎖的預防靜態(tài)分配策略所謂資源的靜態(tài)分配是指，一個進程必須在執(zhí)行前就申請所需要的全部資源，并且直到它所需要的資源都得到滿足后才開始執(zhí)行。采用資源的靜態(tài)分配策略后，進程在執(zhí)行中不再需要申請資源，因而不會出現(xiàn)進程占有某些資源還等待另一些資源的情況，即破壞了第三個必要條件占有并等待條件。2.4.4 死鎖的預防靜態(tài)分配策略靜態(tài)分配策略實現(xiàn)簡單，被許多操作系統(tǒng)采用。但這種策略嚴重地降低了資源利用率，其缺點也是明顯的：一個用戶在進程或作業(yè)運行之前很難提出將要使用的全部設(shè)備；用戶進程或作業(yè)必須等待，直到所有資源滿足時才能投

56、入運行，而實際上某些設(shè)備可能很晚的時候才使用；2.4.4 死鎖的預防靜態(tài)分配策略資源浪費太大，有些資源在進程或作業(yè)運行期間可能只有很少的時間才用到，有的甚至不會用到。例如，只有當用戶程序出錯的時候才會將錯誤從打印機上輸出，此時若采用靜態(tài)預防策略對系統(tǒng)來說是很浪費的。2.4.5 死鎖的避免動態(tài)分配+有控分配為了提高資源利用率，應采用動態(tài)資源分配的方法。但是，為了避免可能產(chǎn)生的死鎖，在進行資源分配時，還應采用某種算法來預測是否有可能發(fā)生死鎖，若存在可能性，就拒絕該資源請求。2.4.5 死鎖的避免動態(tài)分配+有控分配靜態(tài)預防死鎖和動態(tài)避免死鎖的不同處在于：n前者采用的分配策略本身就否定了死鎖的必要條件

57、之一，這樣就保證死鎖不可能發(fā)生；n而后者是在動態(tài)資源分配策略下，另外采用某種算法來避免死鎖的發(fā)生，拒絕可能引起死鎖的某個資源請求。一、有序資源分配法在這一方法中，系統(tǒng)中所有資源都給定一個唯一的序號，所有分配請求必須以上升的次序進行。系統(tǒng)要求每個進程：n對于它所必須使用的而且屬于同一類的所有資源，必須一次申請完畢；n在申請不同類的資源時，必須按各類的編號遞增順序依次申請。2.4.5 死鎖的避免動態(tài)分配+有控分配為了滿足上述系統(tǒng)要求，所以在實施分配時，分配程序必須調(diào)用一種算法，以考察本次申請的資源序號是否符合遞增規(guī)定：若符合，則在資源可用的情況下予以分配，否則，拒絕分配。不難看出，由于通過上述算法

58、對資源申請采取了某種限制，所對應的資源分配有向圖不可能形成環(huán)路，從而破壞了產(chǎn)生死鎖的環(huán)路條件，因此不會發(fā)生死鎖。2.4.5 死鎖的避免動態(tài)分配+有控分配該方案的優(yōu)點是，用戶不需要預先說明對各類資源的最大需求量，只要在申請時按類按序來申請即可。該方案的缺點是，進程實際需要資源的順序不一定與資源的序號相一致，因而仍會造成某種程度的資源浪費。2.4.5 死鎖的避免動態(tài)分配+有控分配例如：進程P1，申請資源的順序是R1，R2；進程P2，申請資源的順序是R2，R1；若單采用動態(tài)資源分配法，則有可能形成環(huán)路條件而造成死鎖；但若采用有序資源分配法，則可避免出現(xiàn)循環(huán)等待的現(xiàn)象。2.4.5 死鎖的避免動態(tài)分配+

59、有控分配2.4.5 死鎖的避免動態(tài)分配+有控分配二、銀行家算法死鎖的避免算法中最有代表性的是Dijkstra E.W于1968年提出的銀行家算法，其模型基于一個小城鎮(zhèn)的銀行系統(tǒng)?，F(xiàn)將該算法描述如下：假定一個銀行系統(tǒng)擁有資金的數(shù)量為，共被N個客戶分享。銀行家對客戶提出下列約束條件：n每個客戶必須預先說明自己所要求的最大資金量，這個數(shù)量不能超過現(xiàn)存資金量；n每個客戶每次提出部分資金量申請，然后獲得分配；n如果銀行滿足了某客戶對資金的最大需求量，那么客戶在資金運作后，應在有限時間內(nèi)全部歸還銀行。2.4.5 死鎖的避免動態(tài)分配+有控分配在銀行家算法中，客戶可看作進程，資金可看作資源，銀行家則可看作操作

60、系統(tǒng)，這里敘述的是單資源銀行家算法。2.4.5 死鎖的避免動態(tài)分配+有控分配單資源銀行家算法單資源銀行家算法在上圖a中列出了4個客戶，每個客戶都有一個貸款額度，銀行家知道不可能所有客戶同時都需要最大貸款額，所以他只保留了10個單位的資金來為客戶服務(wù)，而不是22個單位。圖b所示的狀態(tài)是客戶各自經(jīng)營，在某些時刻需要貸款，則客戶已獲得的貸款和當前可用的最大數(shù)額貸款稱為與資源分配相關(guān)的系統(tǒng)狀態(tài)。單資源銀行家算法一個狀態(tài)被稱為是安全的，其條件是存在一個狀態(tài)序列能夠使所有的客戶均得到其所有的貸款，即所有進程都能得到所需的全部資源并終止。單資源銀行家算法圖b所示的狀態(tài)是安全的，因為在尚有2個單位資金可用的情