操作系統(tǒng)期末復(fù)習(xí)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

46、，造成一萬，造成死鎖死鎖。貸不到款，客戶死貸不到款，客戶死收不回款，銀行家死收不回款，銀行家死2.4.1 死鎖的概念死鎖的定義： 在一組并發(fā)進(jìn)程中，每個(gè)進(jìn)程持有某種資源，同時(shí)又都等待著被該組進(jìn)程中其它進(jìn)程所占有的資源，最終將無限期地僵持下去。這種現(xiàn)象稱為進(jìn)程死鎖，而這一組進(jìn)程就稱為死鎖進(jìn)程。設(shè)S1=1，打印機(jī)可用；S2=1，讀卡機(jī)可用。OS中的例子 操作系統(tǒng)中的例子現(xiàn)有二個(gè)進(jìn)程P1、P2，兩個(gè)設(shè)備打印機(jī)R1、讀卡機(jī)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ù)目 要求該資源的進(jìn)程數(shù)目結(jié)論與問題：死鎖一定是由于系統(tǒng)資源不足所引起的，但系統(tǒng)資源不足是否就一定造成死鎖呢？2）聯(lián)合推進(jìn)路線非法聯(lián)合推進(jìn)路線非法w進(jìn)程推進(jìn)順序不當(dāng)2.4.2 產(chǎn)生死鎖的原因和必要條件A2B2C2D2申請r1申請r2釋放r2釋放r1A1B1C1D1申請r1申請r2釋放r1釋放r2兩進(jìn)程均占用r1兩進(jìn)程均占用r2xyP2進(jìn)展P1進(jìn)展0A 死鎖點(diǎn)2.4.2 產(chǎn)生死鎖的原因

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

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

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

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

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

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

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

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

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

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

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

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

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