操作系統(tǒng)知識(shí)點(diǎn)

PAGEPAGE1操作系統(tǒng)書本知識(shí)點(diǎn)第一章操作系統(tǒng)引論主要內(nèi)容操作系統(tǒng)的目標(biāo)、作用和模型操作系統(tǒng)的發(fā)展過程操作系統(tǒng)的基本特征OS（OperatingSystems)的主要功能OS的結(jié)構(gòu)設(shè)計(jì)本章要點(diǎn)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)：了解操作系統(tǒng)的地位什么是操作系統(tǒng)：3種基本觀點(diǎn)現(xiàn)代操作系統(tǒng)的功能、特性、類型基本概念：批處理、多道程序、作業(yè)、進(jìn)程、任務(wù)、虛擬技術(shù)、并發(fā)性、異步性操作系統(tǒng)的作用(1)作為用戶與計(jì)算機(jī)硬件系統(tǒng)之間的接口作為計(jì)算機(jī)系統(tǒng)資源的管理者處理機(jī)管理：分配和控制處理機(jī)存儲(chǔ)器管理：分配及回收內(nèi)存I/O(Input/Output)設(shè)備管理：I/O分配與操作文件管理：文件存取、共享和保護(hù)監(jiān)視這些資源實(shí)施某種資源分配策略分配這種資源回收這種資源OS實(shí)現(xiàn)了對(duì)計(jì)算機(jī)資源的抽象操作系統(tǒng)的發(fā)展過程1.2.1無操作系統(tǒng)時(shí)的計(jì)算機(jī)系統(tǒng)人工操作方式如紙帶輸入機(jī)。特點(diǎn)是用戶獨(dú)占全機(jī)及CPU等待人工操作。脫機(jī)I/O方式（圖1.3）引入I/O機(jī)的概念，解決前者的缺點(diǎn)。特點(diǎn)是減少了CPU的空閑時(shí)間且提高I/O速度。單道批處理系統(tǒng)處理過程（圖1.4）概念：系統(tǒng)對(duì)作業(yè)的處理都是成批進(jìn)行的、且內(nèi)存中始終只保持一道作業(yè)，稱為單道批處理系統(tǒng)（simplebatchsystem）。批處理系統(tǒng)的引入是為了提高系統(tǒng)資源的利用率和吞吐量概念：運(yùn)行控制權(quán)特征自動(dòng)性、順序性、單道性多道批處理系統(tǒng)（1）優(yōu)點(diǎn)資源利用率高系統(tǒng)吞吐量大平均周轉(zhuǎn)時(shí)間長無交互能力缺點(diǎn)平均周轉(zhuǎn)時(shí)間長、無交互能力分時(shí)系統(tǒng)分時(shí)系統(tǒng)的產(chǎn)生概念：指一臺(tái)主機(jī)上連接了多個(gè)帶有顯示器和鍵盤的終端，同時(shí)允許多個(gè)用戶共享主機(jī)中的資源，各個(gè)用戶都可通過自己的終端以交互方式使用計(jì)算機(jī)。分時(shí)系統(tǒng)在實(shí)現(xiàn)中的關(guān)鍵問題及時(shí)接收：多終端卡、輸入緩沖區(qū)及時(shí)處理：交互作業(yè)應(yīng)在內(nèi)存、響應(yīng)時(shí)間應(yīng)短分時(shí)系統(tǒng)的特征多路性獨(dú)立性及時(shí)性交互性可靠性類型實(shí)時(shí)控制實(shí)時(shí)信息處理實(shí)時(shí)系統(tǒng)(2)實(shí)時(shí)任務(wù)類型按任務(wù)執(zhí)行是否呈現(xiàn)周期性來劃分周期性的（聯(lián)系周期）；非周期性的（聯(lián)系開始或完成截止時(shí)間）根據(jù)對(duì)截止時(shí)間的要求來劃分硬實(shí)時(shí)任務(wù)軟實(shí)時(shí)任務(wù)實(shí)時(shí)、分時(shí)的比較多路性：相同獨(dú)立性：相同及時(shí)性：實(shí)時(shí)系統(tǒng)要求更高交互性：分時(shí)系統(tǒng)交互性更強(qiáng)可靠性：實(shí)時(shí)系統(tǒng)要求更高思考試在交互性、及時(shí)性和可靠性方面，將分時(shí)系統(tǒng)和實(shí)時(shí)系統(tǒng)進(jìn)行比較。操作系統(tǒng)的基本特征(1)并發(fā)性并行是指兩或多個(gè)事件在同一時(shí)刻發(fā)生。并發(fā)是兩或多個(gè)事件在同一時(shí)間間隔內(nèi)發(fā)生。進(jìn)程：系統(tǒng)中能獨(dú)立運(yùn)行并作為資源分配的基本單位。引入線程后，獨(dú)立運(yùn)行的單位變?yōu)榫€程。共享性系統(tǒng)中資源可供內(nèi)存中多個(gè)并發(fā)執(zhí)行的進(jìn)程共同使用互斥共享：一段時(shí)間只允許一個(gè)進(jìn)程訪問該資源同時(shí)訪問：微觀上仍是互斥的虛擬性通過某種技術(shù)把一個(gè)物理實(shí)體變?yōu)槿舾蓚€(gè)邏輯上的對(duì)應(yīng)物。若n是某一物理設(shè)備所對(duì)應(yīng)的虛擬的邏輯設(shè)備數(shù)，則虛擬設(shè)備的速度必然是物理設(shè)備速度的1/n。異步性運(yùn)行進(jìn)度不可預(yù)知。操作系統(tǒng)的功能處理器管理功能(1)進(jìn)程和作業(yè)調(diào)度進(jìn)程：指在系統(tǒng)中能獨(dú)立運(yùn)行并作為系統(tǒng)資源分配的基本單位，它是由一組機(jī)器指令、數(shù)據(jù)和堆棧等組成的，是一個(gè)活動(dòng)實(shí)體。作業(yè)調(diào)度（又稱高級(jí)調(diào)度或長程調(diào)度）：用于把外存上處于后備隊(duì)列中的哪些作業(yè)調(diào)入內(nèi)存，并為它們創(chuàng)建進(jìn)程、分配必要的資源，然后再將新創(chuàng)建的進(jìn)程排在就緒隊(duì)列上，準(zhǔn)備執(zhí)行。2）進(jìn)程控制為作業(yè)創(chuàng)建進(jìn)程，撤消已結(jié)束的進(jìn)程、阻塞進(jìn)程和喚醒進(jìn)程。（3）進(jìn)程同步使并發(fā)執(zhí)行的諸進(jìn)程之間能有效的共享資源和相互合作，從而使程序的執(zhí)行具有可再現(xiàn)性。 可能存在兩種制約關(guān)系：間接相互制約關(guān)系、直接相互制約關(guān)系。（4）進(jìn)程通信進(jìn)程間信息的交換存儲(chǔ)器管理功能主要指內(nèi)存管理，即如何分配內(nèi)存空間，如何提高存儲(chǔ)器的利用率以及能從邏輯上擴(kuò)充內(nèi)存。（1）內(nèi)存的分配靜態(tài)分配方式：每個(gè)作業(yè)的內(nèi)存在作業(yè)裝入時(shí)確定；在作業(yè)裝入后的整個(gè)運(yùn)行期間，不允許該作業(yè)再申請(qǐng)新的內(nèi)存空間，也不允許作業(yè)在內(nèi)存中“移動(dòng)”。動(dòng)態(tài)分配方式：允許作業(yè)在內(nèi)存中“移動(dòng)”。為此，需內(nèi)存分配的數(shù)據(jù)結(jié)構(gòu)及內(nèi)存分配和回收功能2）存儲(chǔ)保護(hù)指存儲(chǔ)管理應(yīng)確保每道用戶程序都只在自己的內(nèi)存空間內(nèi)運(yùn)行，彼此互不干擾。例：設(shè)置上、下界寄存器，每條指令進(jìn)行越界檢查（一般是硬件實(shí)現(xiàn)）（3）地址映射完成邏輯地址到物理地址的轉(zhuǎn)換（4）內(nèi)存擴(kuò)充采用虛擬技術(shù)實(shí)現(xiàn)內(nèi)存擴(kuò)充，具有請(qǐng)求調(diào)入和頁面置換功能。設(shè)備管理功能完成設(shè)備的分配和回收，設(shè)備的控制和信息傳輸，提高CPU和I/O設(shè)備的并行程度和利用率，方便、快捷地完成用戶提出的I/O請(qǐng)求。 如：CPU快則應(yīng)多創(chuàng)建緩沖區(qū)（1）緩沖管理 有效地緩和CPU和I/O設(shè)備速度不匹配問題，提高CPU利用率，提高系統(tǒng)吞吐量。 常見的緩沖區(qū)機(jī)制有：單緩沖機(jī)制、雙緩沖機(jī)制（2）設(shè)備分配包括：設(shè)備，設(shè)備控制器，I/O通信的分配和回收（3）設(shè)備處理指控制設(shè)備進(jìn)行實(shí)際的操作，包括讀、寫等以及向CPU發(fā)中斷。設(shè)備處理/驅(qū)動(dòng)程序應(yīng)能根據(jù)用戶的I/O請(qǐng)求，自動(dòng)地構(gòu)成通道程序。4）設(shè)備獨(dú)立性獨(dú)立性，即program與設(shè)備無關(guān)性，使program易于重定向，增加了可移植性。（5）虛擬設(shè)備管理文件管理功能對(duì)用戶文件和系統(tǒng)文件進(jìn)行管理，以方便用戶使用，并保證文件的安全性。（1）文件存儲(chǔ)空間的管理（2）目錄管理使用戶按名存取，提高速度。（3）文件的讀/寫管理和保護(hù)用戶接口一、命令接口由一組“命令”集組成，分為聯(lián)機(jī)和脫機(jī)用戶接口1.聯(lián)機(jī)用戶接口由一組鍵盤操作命令及命令解釋程序所組成2.脫機(jī)（批處理用戶接口）用JCL寫作業(yè)說明書二、程序接口系統(tǒng)調(diào)用高級(jí)語言的庫函數(shù)三、圖形接口如win的copy文件，采用“拖”來完成，生動(dòng)，不需記憶OS的結(jié)構(gòu)設(shè)計(jì)無結(jié)構(gòu)操作系統(tǒng)模塊化結(jié)構(gòu)操作系統(tǒng)分層式結(jié)構(gòu)操作系統(tǒng)微內(nèi)核操作系統(tǒng)結(jié)構(gòu)1.無結(jié)構(gòu)操作系統(tǒng)一組過程集，各過程可相互調(diào)用，也叫整體系統(tǒng)結(jié)構(gòu)。缺點(diǎn)：邏輯復(fù)雜，維護(hù)困難.2、模塊化操作系統(tǒng)通過分解來控制大型軟件復(fù)雜度。如：進(jìn)程模塊、內(nèi)存模塊…，各模塊內(nèi)進(jìn)一步劃分子模塊。優(yōu)點(diǎn)：提高了OS設(shè)計(jì)的可維護(hù)性增強(qiáng)的OS的可適應(yīng)性加速了OS的開發(fā)過程：并行開發(fā)模塊缺點(diǎn)：接口不易確定模塊依賴關(guān)系可能復(fù)雜（對(duì)于大型軟件而言）3、分層式操作系統(tǒng)有序分層的基本概念可簡化設(shè)計(jì)的復(fù)雜度下層為上層提供服務(wù)層次的設(shè)置應(yīng)考慮的因素程序嵌套：各模塊間嵌套關(guān)系復(fù)雜運(yùn)行頻率：隨層次的增高，相應(yīng)軟件的運(yùn)行速度就隨之下降公用模塊：低層用戶接口：高層微內(nèi)核操作系統(tǒng)結(jié)構(gòu)（1）提高了系統(tǒng)的靈活性和可擴(kuò)充性提高了軟件的可靠性適合于分布式系統(tǒng)微內(nèi)核操作系統(tǒng)結(jié)構(gòu)（2）面向?qū)ο蟮某绦蛟O(shè)計(jì)技術(shù)概念：優(yōu)點(diǎn)：a.可擴(kuò)展性b.繼承性微內(nèi)核技術(shù)引入：提高系統(tǒng)的靈活性；采用C/S模式基本功能進(jìn)程、內(nèi)存、IPC等基本管理功能第二章進(jìn)程管理程序順序執(zhí)行時(shí)的特征(1)順序性(2)封閉性程序是在封閉的環(huán)境下運(yùn)行的。即程序在運(yùn)行時(shí)，它獨(dú)占全機(jī)資源。一旦運(yùn)行,不受外界影響.(3)可再現(xiàn)性只要程序執(zhí)行時(shí)的環(huán)境和初始條件相同，當(dāng)程序多次重復(fù)執(zhí)行時(shí)，不論它是從頭到尾不停頓地執(zhí)行，還是“停停走走”地執(zhí)行，都將獲得相同的結(jié)果。進(jìn)程的特征(1)動(dòng)態(tài)性進(jìn)程是程序的一次執(zhí)行過程，因此，屬于動(dòng)態(tài)概念，是進(jìn)程的最重要的特征。動(dòng)態(tài)性還表現(xiàn)為:“它由創(chuàng)建而產(chǎn)生，由調(diào)度而執(zhí)行，因得不到資源而暫停執(zhí)行，以及由撤消而消亡”?？梢?進(jìn)程有一定的生命期。而程序只是一組有序指令的集合，并長期存放在某種介質(zhì)上，本身并無運(yùn)動(dòng)的含義，因此，程序是個(gè)靜態(tài)實(shí)體。進(jìn)程和程序不是一一對(duì)應(yīng)的，如幾個(gè)進(jìn)程可同時(shí)執(zhí)行一個(gè)程序。(2)并發(fā)性這是指多個(gè)進(jìn)程實(shí)體，同存于內(nèi)存中，能在一段時(shí)間內(nèi)同時(shí)運(yùn)行。并發(fā)性是進(jìn)程的第二個(gè)最重要特征。引人進(jìn)程的目的也正是為了使其程序能并發(fā)執(zhí)行，而程序是不能并發(fā)執(zhí)行的。(3)獨(dú)立性這是指進(jìn)程實(shí)體是一個(gè)能獨(dú)立運(yùn)行的基本單位，同時(shí)也是系統(tǒng)中獨(dú)立獲得資源和獨(dú)立調(diào)度的基本單位。凡未建立進(jìn)程的程序，都不能作為一個(gè)獨(dú)立的單位參加運(yùn)行。(4)異步性這是指進(jìn)程按各自獨(dú)立的、不可預(yù)知的速度向前推進(jìn)；或者說，進(jìn)程按異步方式運(yùn)行。正是這一特征，將導(dǎo)致程序執(zhí)行的不可再現(xiàn)性。因此，在OS中必須采取某種措施來保證各程序之間能協(xié)調(diào)運(yùn)行。(5)結(jié)構(gòu)特征從結(jié)構(gòu)上看，進(jìn)程實(shí)體是由程序段、數(shù)據(jù)段及進(jìn)程控制塊三部分組成。進(jìn)程的三種基本狀態(tài)注意：*可逆：僅就緒à?執(zhí)行*主動(dòng)：僅執(zhí)行阻塞*微觀上：執(zhí)行狀態(tài)時(shí)，程序在運(yùn)行*宏觀上：進(jìn)程建立后直至撤消，程序都在運(yùn)行。1)就緒(Ready)狀態(tài)一個(gè)剛被創(chuàng)建的進(jìn)程，它的初始狀態(tài)是就緒。進(jìn)程所請(qǐng)求的一次打印輸出結(jié)束后，將使進(jìn)程狀態(tài)從等待態(tài)變?yōu)榫途w態(tài)。2)執(zhí)行狀態(tài)單CPU系統(tǒng)中,最多只有一個(gè)進(jìn)程處于運(yùn)行狀態(tài)。分配到必要的資源并獲得處理機(jī)時(shí)的進(jìn)程狀態(tài)是執(zhí)行狀態(tài)。如：某進(jìn)程已獲得運(yùn)行所需的其它資源(CPU除外)，將處于就緒，當(dāng)它獲得CPU時(shí)，就將處于運(yùn)行（執(zhí)行）狀態(tài)。進(jìn)程從運(yùn)行狀態(tài)進(jìn)入就緒狀態(tài)的原因可能是時(shí)間片用完。3)阻塞狀態(tài)進(jìn)程管理中，在等待的事件發(fā)生情況下，進(jìn)程將從阻塞狀態(tài)變?yōu)榫途w狀態(tài)。一個(gè)進(jìn)程狀態(tài)轉(zhuǎn)換的發(fā)生是否一定會(huì)導(dǎo)致另一個(gè)狀態(tài)的轉(zhuǎn)換發(fā)生，列出所有可能：進(jìn)程同步基本概念（1）進(jìn)程同步的兩種形式的制約關(guān)系：間接相互制約關(guān)系。此時(shí)進(jìn)程同步的主要任務(wù)是保證諸進(jìn)程能互斥的訪問臨界資源。因此，資源應(yīng)由系統(tǒng)同一分配。直接相互制約關(guān)系。此時(shí)此時(shí)進(jìn)程同步的主要任務(wù)是保證相互合作的進(jìn)程在執(zhí)行次序上的協(xié)調(diào)，避免出現(xiàn)與時(shí)間有關(guān)的錯(cuò)誤。臨界資源一次僅允許一個(gè)進(jìn)程使用的資源叫臨界資源。?屬于臨界資源的物理設(shè)備，如輸入機(jī)、打印機(jī)、磁帶機(jī)等。?屬于臨界資源的軟件資源，如多個(gè)進(jìn)程共享的變量、數(shù)據(jù)、隊(duì)列等。兩個(gè)交往的并發(fā)進(jìn)程，其中一個(gè)進(jìn)程對(duì)另一個(gè)進(jìn)程的影響常常是不可預(yù)期的，甚至是無法再現(xiàn)，因?yàn)閮蓚€(gè)并發(fā)進(jìn)程執(zhí)行的相對(duì)速度無法控制，所以一個(gè)進(jìn)程的速率通常無法為另一個(gè)進(jìn)程所知。如：兩個(gè)進(jìn)程P1，P2共享變量counter（初值5）： P1P2 registerl＝counter； register2＝counter； registerl＝registerl+1； register2＝register2–1； Counter=register1 Counter=register2；如果一個(gè)進(jìn)程先執(zhí)行，然后另一進(jìn)程再執(zhí)行，則counter的值仍為5。如改變執(zhí)行次序，counter可能為4或6。原因：兩個(gè)進(jìn)程共享了變量counter.解決方法：把counter作為臨界資源處理。臨界區(qū)程序上如何實(shí)現(xiàn)互斥使用臨界資源呢？只要把進(jìn)程中訪問臨界資源的那段代碼分離出來（它被稱為臨界區(qū)），諸進(jìn)程互斥地進(jìn)入自己的臨界區(qū)即可。信號(hào)量機(jī)制1965年，荷蘭學(xué)者dijkitra提出的信號(hào)量機(jī)制是一種卓有成效的進(jìn)程同步工具?，F(xiàn)在信號(hào)量機(jī)制已被廣泛地應(yīng)用于單處理機(jī)和多處理機(jī)系統(tǒng)，以及計(jì)算機(jī)網(wǎng)絡(luò)中。P、V操作操作系統(tǒng)利用信號(hào)量實(shí)現(xiàn)對(duì)進(jìn)程和資源的控制和管理。信號(hào)量的值僅由P、V操作來改。P、V操作是能夠?qū)崿F(xiàn)對(duì)臨界區(qū)管理要求的兩條原語，P操作起到了限制一次只有一個(gè)進(jìn)程進(jìn)入臨界區(qū)的作用，而V操作將喚醒位于阻塞隊(duì)列中的頭一個(gè)進(jìn)程，使其可以進(jìn)入臨界區(qū)，保證了進(jìn)程在臨界區(qū)內(nèi)逗留有限時(shí)間。P原語操作的主要?jiǎng)幼魇牵篠emaphore減1；若Semaphore減1后仍>=0,則進(jìn)程繼續(xù)執(zhí)行。若Semaphore減1后<0,則進(jìn)程被阻塞在與該信號(hào)相對(duì)應(yīng)的隊(duì)列中，然后轉(zhuǎn)進(jìn)程調(diào)度。V原語操作的主要?jiǎng)幼魇牵篠emaphore加1；若Semaphore加1后仍>0,則進(jìn)程繼續(xù)執(zhí)行。若Semaphore加1后<=0,則從信號(hào)的等待隊(duì)列中喚醒一等待進(jìn)程，然后再返回原進(jìn)程繼續(xù)執(zhí)行或轉(zhuǎn)進(jìn)程調(diào)度。利用信號(hào)量實(shí)現(xiàn)前驅(qū)關(guān)系T1T1T2T3T4Vara,b,c,d,e,f,g:semaphore:=0;Beginparbegins1:v(a);v(b);p(a);s2;v(c);v(d);p(b);s3;v(e);p(c);s4;v(f);p(d);s5;v(g);p(e);p(f);p(g);s6;end;Parendend設(shè)有一個(gè)作業(yè)由4個(gè)進(jìn)程組成，這4個(gè)進(jìn)程必須按下圖所示的次序運(yùn)行，試用P、V操作表達(dá)4個(gè)進(jìn)程的同步關(guān)系。2.4經(jīng)典進(jìn)程同步問題在多道程序環(huán)境個(gè)，進(jìn)程同步問題是十分重要的，也是相當(dāng)有趣的問題，因而吸引了不少學(xué)者對(duì)它進(jìn)行研究，由此而產(chǎn)了一系列經(jīng)典的進(jìn)程同步問題，其中“生產(chǎn)者—消資者問題”、“讀者—寫者問題”、“哲學(xué)家進(jìn)餐問題”很具有代表性，是許多實(shí)際的進(jìn)程同步問題的抽象，具有實(shí)用價(jià)值。1、生產(chǎn)者－消費(fèi)者問題生產(chǎn)者－消費(fèi)者問題是一個(gè)著名的同步問題。其描述的是：有一群生產(chǎn)者進(jìn)程在生產(chǎn)產(chǎn)品，并將這些產(chǎn)品提供給消費(fèi)者進(jìn)程去消費(fèi)。為使生產(chǎn)者進(jìn)程和消費(fèi)者進(jìn)程能并發(fā)執(zhí)行，在兩者之間設(shè)置了一個(gè)具有n個(gè)緩沖區(qū)的緩沖池，生產(chǎn)者進(jìn)程將它所生產(chǎn)的產(chǎn)品放入一個(gè)緩沖區(qū)中，消費(fèi)者可從一個(gè)緩沖區(qū)中拿走產(chǎn)品去消費(fèi)。生產(chǎn)者與消費(fèi)者是等效的，只要有空時(shí)，生產(chǎn)者可送入，只要有滿buf，消費(fèi)者可取走。這是多個(gè)進(jìn)程相互合作的一種抽象，如輸出時(shí)：計(jì)算進(jìn)程是生產(chǎn)者，打印進(jìn)程是消費(fèi)者。分析：從資源的觀點(diǎn)很容易解這個(gè)問題。1.有空buf生產(chǎn)者才能送數(shù)據(jù)，可設(shè)計(jì)數(shù)信號(hào)量empty，初值為n。2.有裝滿數(shù)據(jù)的buf，消費(fèi)者才能取數(shù)據(jù)，故設(shè)數(shù)信號(hào)量full，初值為0。3.對(duì)某個(gè)buf應(yīng)互斥使用，設(shè)互斥信號(hào)量mutex，初值為1。如何用P.V操作同步：此處可以看到：1.P.V操作必須成對(duì)出現(xiàn)2.兩個(gè)P操作次序不可顛倒，為什么？對(duì)于n個(gè)環(huán)行buf的生產(chǎn)者—消費(fèi)者問題的進(jìn)程同步算法描述：varmutex,empty,ful1：semaphore:＝1,n,0;buffer：array[0,…,n-1]ofitem;in,out:integer:=0,0;beginparbeginproducer:beginrepeatproduceraniteminnextp;wait(empty);wait(mutex);buffer(in):=nextp;in:=(in+1)modn;signal(mutex);signal(full);untilfalse endconsumer:beginrepeatwait(full);wait(mutex);nextc:=buffer(out);out:=(out+1)modn;signal(mutex);signal(empty);consumertheiteminnextc;untilfalseendparendend2哲學(xué)家進(jìn)餐問題哲學(xué)家進(jìn)餐問題是典型的同步問題。它是由Dijkstra提出并解決的。該問題是描述有五個(gè)哲學(xué)家，它們的生活方式是交替地進(jìn)行思考和進(jìn)餐。哲學(xué)家們共用一張圓桌，分別坐在周圍的五張椅子上。在圓桌上有五個(gè)碗和五支筷子，平時(shí)一個(gè)哲學(xué)家進(jìn)行思考，饑餓時(shí)便試圖取用其左、右最靠近他的筷子，只有在他拿到兩支筷子時(shí)才能進(jìn)餐。進(jìn)餐畢，放下筷子又繼續(xù)思考。利用記錄型信號(hào)量解決哲學(xué)家進(jìn)餐問題經(jīng)分析可知，筷子是臨界資源，用如下信號(hào)量數(shù)組實(shí)現(xiàn)互斥：varchopstick：array［0，…，4］ofsemaphore；所有信號(hào)量被初始化為1，第i個(gè)哲學(xué)家的活動(dòng)可描述為：repeatwait(chopstick[i])；先拿左邊的筷子wait(chopstick[(i+1)mod5])；再拿右邊的筷子eat;signal(chopstick[i])；signal(chopstick[(i＋l)mod5])；think;untilfalse；問題：哲學(xué)家如各自拿起左邊的筷子時(shí)，就會(huì)產(chǎn)生死鎖。對(duì)于這樣的死鎖問題可采取以下幾種解決方法：(1)至多只允許四個(gè)哲學(xué)家同時(shí)進(jìn)餐，以保證至少有一個(gè)哲學(xué)家能夠進(jìn)餐，最終總會(huì)釋放出他所使用過的兩支筷子，從而可使更多的哲學(xué)家進(jìn)餐。(2)僅當(dāng)哲學(xué)家的左、右兩支筷子均可用時(shí)，才允許他拿起筷子進(jìn)餐。(3)規(guī)定奇數(shù)號(hào)哲學(xué)家先拿他左邊的筷子，然后再去拿他右邊的筷子；而偶數(shù)號(hào)哲學(xué)家則相反。按此規(guī)定，將是1、2號(hào)哲學(xué)家競爭1號(hào)筷子；3、4號(hào)哲學(xué)家競爭3號(hào)筷子。即五個(gè)哲學(xué)家都先競爭奇數(shù)號(hào)筷子，獲得后，再去競爭偶數(shù)號(hào)筷子，最后總會(huì)有一個(gè)哲學(xué)家能獲得兩支筷子而進(jìn)餐。3、讀者一寫者問題一個(gè)數(shù)據(jù)文件和記錄，可以被多個(gè)進(jìn)程共享，我們把只要求讀該文件的進(jìn)程稱為reader進(jìn)程，把其他進(jìn)程稱為writer進(jìn)程。允許多個(gè)進(jìn)程同時(shí)讀一個(gè)共享對(duì)象，因?yàn)樽x操作不會(huì)使數(shù)據(jù)文件混亂。但不允許一個(gè)writer進(jìn)程和其他reader進(jìn)程或writer進(jìn)程同時(shí)訪問共享對(duì)象。一.利用信號(hào)量機(jī)制解法：設(shè)置兩個(gè)信號(hào)量，一個(gè)整型變量。?寫互斥信號(hào)量wmutex：用于實(shí)現(xiàn)一個(gè)寫者與其它讀寫者互斥訪問共享對(duì)象，事實(shí)上，它被第一個(gè)進(jìn)入的讀者和最后一個(gè)離去的讀者使用，中間讀者不用。?讀互斥信號(hào)量rmutex：使讀者互斥訪問readcount——當(dāng)前讀者進(jìn)程數(shù)。?一個(gè)整型變量：readcount初值為0。讀者—寫者問題可描述如下：semaphorermutex=1，wmutex=1;Intreadcount=0;While(true)wait(rmutex);(rmutex代表的是讀進(jìn)程互斥訪問readcount)ifreadcount==0wait(wmutex);readcount=readcount+1;signal(rmutex);Performreadoperation；wait(rmutex)；readcount=readcount一1；ifreadcount=0signal(wmutex);signal(rmutex)；writer：repeatwait(wmutex);Performwriteoperation；signal(wmutex)；untilfalse;end進(jìn)程通信進(jìn)程的互斥與同步就是一種進(jìn)程間的通信方式。由于進(jìn)程互斥與同步交換的信息量較少且效率較低，因此稱這種通信方式為低級(jí)進(jìn)程通信方式，相應(yīng)的也將P、V原語稱為兩條低級(jí)進(jìn)程通信原語。第3章處理機(jī)調(diào)度與死鎖高級(jí)調(diào)度作業(yè)控制塊JCB過程每當(dāng)作業(yè)進(jìn)入系統(tǒng)時(shí)，系統(tǒng)便為每個(gè)作業(yè)建立一個(gè)JCB，根據(jù)作業(yè)類型將它插入相應(yīng)后備隊(duì)列中。作業(yè)調(diào)度程序依據(jù)一定的調(diào)度算法來調(diào)度它們，被調(diào)度到的作業(yè)將會(huì)裝入內(nèi)存。在作業(yè)運(yùn)行期間，系統(tǒng)就按照J(rèn)CB中的信息對(duì)作業(yè)進(jìn)行控制。當(dāng)一個(gè)作業(yè)執(zhí)行結(jié)束進(jìn)入完成狀態(tài)時(shí)，系統(tǒng)負(fù)責(zé)回收分配給它的資源，撤銷它的作業(yè)控制塊。低級(jí)調(diào)度進(jìn)程調(diào)度可采用下述兩種方式：1．非搶占方式(Non-PreemptiveMode)采用這種調(diào)度方式時(shí)，一旦把處理機(jī)分配給某進(jìn)程后，便讓該進(jìn)程一直執(zhí)行，直至該進(jìn)程完成或發(fā)生某事件而被阻塞時(shí)，才再把處理機(jī)分配給其它進(jìn)程，決不允許某進(jìn)程搶占已經(jīng)分配出去的處理機(jī)。優(yōu)點(diǎn)是實(shí)現(xiàn)簡單、系統(tǒng)開銷小，適用于大多數(shù)的批處理系統(tǒng)環(huán)境。但它難于滿足緊急任務(wù)的要求：立即執(zhí)行，因而可能造成難以預(yù)料的后果。顯然，在要求比較嚴(yán)格的實(shí)時(shí)系統(tǒng)中不宜采用這種調(diào)度方式。2．搶占方式(PreemptiveMode)這種調(diào)度方式，允許調(diào)度程序根據(jù)某種原則，去停止某個(gè)正在執(zhí)行的進(jìn)程，將已分配給該進(jìn)程的處理機(jī)，重新分配給另一進(jìn)程；搶占的原則有：(1)時(shí)間片原則。各進(jìn)程按時(shí)間片運(yùn)行，當(dāng)一個(gè)時(shí)間片用完后，便停止該進(jìn)程的執(zhí)行而重新進(jìn)行調(diào)度。這種原則適用于分時(shí)系統(tǒng)、大多數(shù)實(shí)時(shí)系統(tǒng)，以及要求較高的批處理系統(tǒng)。(2)優(yōu)先權(quán)原則。通常是對(duì)一些重要的和緊急的作業(yè)賦予較高的優(yōu)先權(quán)。當(dāng)這種作業(yè)到達(dá)時(shí)，如果其優(yōu)先權(quán)比正在執(zhí)行進(jìn)程的優(yōu)先權(quán)高便停止正在執(zhí)行的進(jìn)程，將處理機(jī)分配給優(yōu)先權(quán)高的進(jìn)程，使之執(zhí)行(3)短作業(yè)(進(jìn)程)優(yōu)先原則，當(dāng)新到達(dá)的作業(yè)(進(jìn)程)比正在執(zhí)行的作業(yè)(進(jìn)程，明顯地短時(shí)，將剝奪長作業(yè)(進(jìn)程)的執(zhí)行，將處理機(jī)分配給短作業(yè)(進(jìn)程)，使之優(yōu)先執(zhí)行。中級(jí)調(diào)度中級(jí)調(diào)度又稱為中程調(diào)度(Medium-TermScheduling)。引入中級(jí)調(diào)度的主要目的，是為了提高內(nèi)存的利用率和系統(tǒng)吞吐量。為此，應(yīng)使那些暫時(shí)不能運(yùn)行的進(jìn)程不再占用寶貴的內(nèi)存空間，而將它們調(diào)至外存上去等待，稱此時(shí)的進(jìn)程狀態(tài)為就緒駐外存狀態(tài)或掛起狀態(tài)。當(dāng)這些進(jìn)程重又具備運(yùn)行條件且內(nèi)存又稍有空閑時(shí)，由中級(jí)調(diào)度決定，將外存上的那些重又具備運(yùn)行條件的就緒進(jìn)程重新調(diào)入內(nèi)存，并修改其狀態(tài)為就緒狀態(tài)，掛在就緒隊(duì)列上，等待進(jìn)程調(diào)度。中級(jí)調(diào)度實(shí)際上就是存儲(chǔ)器管理中的對(duì)換功能。調(diào)度算法先來先服務(wù)調(diào)度算法(FCFS)作業(yè)調(diào)度和進(jìn)程調(diào)度都可使用，最簡單，本質(zhì)上屬于非剝奪方式。有利于長作業(yè)/進(jìn)程。顯然有利于CPU繁忙型的作業(yè)(如通常的科學(xué)計(jì)算)，而不利于I／O繁忙阻的作業(yè)/進(jìn)程（如大多數(shù)的事務(wù)處理)。短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法(SJF/SPF)有利于短作業(yè)/進(jìn)程。平均周轉(zhuǎn)時(shí)間短，系統(tǒng)吞吐量高。缺點(diǎn)：長作業(yè)可能發(fā)生“饑餓”現(xiàn)象，也不能保證緊迫性作業(yè)(進(jìn)程)會(huì)得到及時(shí)處理，用戶可能會(huì)有意或無意地縮短其作業(yè)的估計(jì)執(zhí)行時(shí)間。優(yōu)先權(quán)調(diào)度算法一、優(yōu)先權(quán)調(diào)度算法的類型為了照顧到緊迫型作業(yè)在進(jìn)入系統(tǒng)后便能獲得優(yōu)先處理引入最高優(yōu)先權(quán)調(diào)度算法，它常被用于批處理系統(tǒng)中作為作業(yè)調(diào)度算法，也是最常用的進(jìn)程調(diào)度算法。用于進(jìn)程調(diào)度時(shí)，又可分成兩種方式：非搶占式優(yōu)先權(quán)算法和搶占式優(yōu)先權(quán)算法，差別在于：一旦出現(xiàn)了另一個(gè)優(yōu)先權(quán)更高的進(jìn)程時(shí)，對(duì)搶占式，其可搶先運(yùn)行。二、優(yōu)先權(quán)的類型1．靜態(tài)優(yōu)先權(quán)優(yōu)先權(quán)是在創(chuàng)建進(jìn)程時(shí)確定的，在進(jìn)程的整個(gè)運(yùn)行期間保持不變。確定進(jìn)程優(yōu)先權(quán)的依據(jù)有： (1)進(jìn)程類型，系統(tǒng)進(jìn)程高于用戶進(jìn)程，I/O繁忙進(jìn)程高于CPU繁忙進(jìn)程，前臺(tái)（交互型用戶進(jìn)程）高于后臺(tái)（批處理進(jìn)程）。 (2)進(jìn)程對(duì)資源的需求。估計(jì)執(zhí)行時(shí)間及內(nèi)存需要量少 (3)根據(jù)用戶要求。靜態(tài)優(yōu)先權(quán)法簡單易行、系統(tǒng)開銷小，但某些進(jìn)程可能長期等待.2．動(dòng)態(tài)優(yōu)先權(quán)優(yōu)先權(quán)是可以隨進(jìn)程的推進(jìn)而改變，以便獲得更好的調(diào)度性能。例如，我們可以規(guī)定，在就緒隊(duì)列中的進(jìn)程，隨其等待時(shí)間的增長，其優(yōu)先權(quán)以速率a增加。若所有的進(jìn)程都具有相同的優(yōu)先權(quán)初值，則顯然是最先進(jìn)入就緒隊(duì)列的進(jìn)程，將最先獲得處理機(jī)。此即FCFS算法；若所有的就緒進(jìn)程具有各不相同的優(yōu)先權(quán)初值，對(duì)于優(yōu)先權(quán)初值低的進(jìn)程，在等待足夠的時(shí)間后，其優(yōu)先權(quán)便可能升為最高，從而可以獲得處理機(jī)執(zhí)行。當(dāng)采用搶占式優(yōu)先權(quán)調(diào)度算法時(shí)，如果再規(guī)定正在執(zhí)行的進(jìn)程，其優(yōu)先權(quán)以速率b下降，于是便可防止一個(gè)長作業(yè)長期地壟斷處理機(jī)。高響應(yīng)比優(yōu)先調(diào)度算法時(shí)間片輪轉(zhuǎn)調(diào)度算法本質(zhì)上屬于剝奪方式,分時(shí)系統(tǒng)中無例外采用(為確保響應(yīng)時(shí)間)系統(tǒng)使每個(gè)進(jìn)程依次按時(shí)間片q輪流的方式執(zhí)行，q的大小從幾ms到幾百ms。當(dāng)時(shí)間片用完時(shí)，計(jì)時(shí)器觸發(fā)一個(gè)中斷，重新調(diào)度，從而讓就緒隊(duì)列中的所有進(jìn)程，在一給定的時(shí)間內(nèi)，均能獲得一時(shí)間片的處理機(jī)執(zhí)行時(shí)間。時(shí)間片大小是關(guān)鍵問題太大，大到每個(gè)進(jìn)程部能在一個(gè)時(shí)間片內(nèi)執(zhí)行完畢，則退化為FCFS算法，過小，進(jìn)程切換時(shí)間比重過大影響CPU使用率。通常要考慮到以下幾個(gè)因素：1.對(duì)響應(yīng)時(shí)間的要求與就緒隊(duì)列中進(jìn)程數(shù)目響應(yīng)時(shí)間T直接與用戶(進(jìn)程)數(shù)目N和時(shí)間片q成比例,即T=Nq。q正比與響應(yīng)時(shí)間，反比與就緒隊(duì)列中進(jìn)程數(shù)目。2.計(jì)算機(jī)的處理能力。速度快，q可小些。通常q值是這樣決定的：批處理系統(tǒng)：80%的CPU周期在一個(gè)時(shí)間片內(nèi)完成。分時(shí)系統(tǒng)：q=T/NmaxT-響應(yīng)時(shí)間上限Nmax-最大進(jìn)程數(shù)多級(jí)反饋隊(duì)列調(diào)度算法實(shí)時(shí)調(diào)度2.最低松弛優(yōu)先算法算法（LLF）該算法是根據(jù)任務(wù)的緊急的程序，來確定任務(wù)的優(yōu)先級(jí)；任務(wù)的緊急程序越高，為該任務(wù)所賦予的優(yōu)先級(jí)就愈高，以使之優(yōu)先執(zhí)行該算法主要用于可搶占調(diào)度方式中某一進(jìn)城的松弛度=必要完成時(shí)間-其本身運(yùn)行時(shí)間-當(dāng)前時(shí)間死鎖的基本概念所謂死鎖(Deadlock)，是指一組進(jìn)程因競爭資源