操作系統(tǒng)整合復(fù)習(xí)題

1、第1章 ：引論1. 操作系統(tǒng)的定義：操作系統(tǒng)是計算機(jī)系統(tǒng)中的系統(tǒng)軟件，是能有效地組織和管理計算機(jī)系統(tǒng)中的硬件和軟件資源，合理地組織計算機(jī)工作流程，控制程序的執(zhí)行，并向用戶提供各種服務(wù)功能，使得用戶能夠合理，方便，有效地使用計算機(jī)，使整個計算機(jī)系統(tǒng)高效運(yùn)行的一組程序模塊的集合。2. 操作系統(tǒng)的發(fā)展史： 人工操作方式 缺點：用戶獨占全機(jī)，處理機(jī)等待人工操作。脫機(jī)I/0方式 為了解決人機(jī)矛盾及處理機(jī)和I/O設(shè)備之間速度不匹配的矛盾。 （外圍機(jī)是核心）單道批處理操作系統(tǒng) 自動地將一個作業(yè)一個作業(yè)的進(jìn)行處理，直至磁盤上的作業(yè)全部 完成。單道批處理操作系統(tǒng) 好處：提高處理機(jī)的利用率（可同時把若干道程序裝入

2、內(nèi)存，并且交 替地執(zhí)行。） 提高內(nèi)存和I/O的設(shè)備利用率（內(nèi)存中裝入多道程序，并允許 并發(fā)執(zhí)行。） 增加系統(tǒng)吞吐量 特征：多道性（允許并發(fā)，提高了資源利用率和增加系統(tǒng)吞吐量） 無序性 調(diào)度性3. 分時系統(tǒng)與實時系統(tǒng)的比較：分時系統(tǒng)實時系統(tǒng)多路性為多個終端用戶服務(wù)。對多路的現(xiàn)場信息進(jìn)行采集以及對多個對象或多個執(zhí)行機(jī)構(gòu)進(jìn)行控制。獨立性每個用戶各占一個終端，彼此獨立操作。信息的采集和對對象的控制也彼此互不干擾。及時性用戶的請求時間通常是2-3 S及時性由控制對象所要求的開始截止時間或完成截止時間來確定的。交互性用戶可以請求系統(tǒng)提供各方面的服務(wù)，如文件編輯，數(shù)據(jù)處理和資源共享。僅限于訪問系統(tǒng)中某些特定

3、的專業(yè)服務(wù)程序?？煽啃砸罂煽?。要求高度可靠。通常采取了多級容錯措施保證數(shù)據(jù)的安全。4. 操作系統(tǒng)的幾種觀點：操作系統(tǒng)軟件的觀點有作為軟件的外在和內(nèi)在特性。外在特性：即操作命令定義集和界面，完全確定了操作系統(tǒng)這個軟件的使用方式。內(nèi)在特性：具有一般軟件的結(jié)構(gòu)特點，但又具有一般軟件不具備的特殊結(jié)構(gòu)。計算機(jī)系統(tǒng)資源管理的觀點提供一些機(jī)制去協(xié)調(diào)程序間的競爭與同步，提供機(jī)制對資源進(jìn)行合理使用。處理機(jī)管理：用于分配和控制處理機(jī)。存儲器管理：負(fù)責(zé)內(nèi)存的分配和回收。I/O設(shè)備管理：負(fù)責(zé)I/O設(shè)備的分配和操縱。文件管理：負(fù)責(zé)文件的存取，共享和保護(hù)。進(jìn)程的觀點操作系統(tǒng)=若干個可以同時獨立運(yùn)行的程序(進(jìn)程)+一個對

4、這些程序進(jìn)行協(xié)調(diào)的核心（進(jìn)程完成任務(wù)，核心則控制盒協(xié)調(diào)這些進(jìn)程的運(yùn)行，解決進(jìn)程之間的通信。）用戶與計算機(jī)硬件系統(tǒng)之間接口的觀點注意這個接口是軟件接口。用戶可以使用兩種方式來使用計算機(jī)：（1） 命令方式（2） 系統(tǒng)調(diào)用方式虛機(jī)器的觀點用戶不直接使用硬件計算機(jī)，而是通過操作系統(tǒng)來控制盒使用計算機(jī)。服務(wù)提供者觀點從用戶角度看，操作系統(tǒng)為用戶提供功能更強(qiáng)，服務(wù)質(zhì)量更高，使用戶更方便，靈活的虛擬計算機(jī)。包括：程序執(zhí)行，I/0操作，文件系統(tǒng)操作，通信，差錯檢測（在多道程序環(huán)境下，處理器的分配和運(yùn)行以進(jìn)程為單位，故可歸結(jié) 為對進(jìn)程的管理。）進(jìn)程控制：負(fù)責(zé)進(jìn)程的創(chuàng)建，撤銷及狀態(tài)轉(zhuǎn)換。進(jìn)程同步：對并發(fā)執(zhí)行的進(jìn)程

5、進(jìn)行協(xié)調(diào)。進(jìn)程通信：負(fù)責(zé)完成進(jìn)程間的信息交換。進(jìn)程調(diào)度：按一定算法進(jìn)行處理器分配。5. 操作系統(tǒng)的功能：處理器管理 (1)設(shè)備分配。(2)設(shè)備傳輸控制：實現(xiàn)物理的輸入輸出操作，即啟動設(shè)備，中斷 處理，結(jié)束處理。(3)設(shè)備獨立性：用戶程序之間的設(shè)備與物理設(shè)備無關(guān)。文件管理設(shè)備管理(1)內(nèi)存分配：按一定的策略為每道程序分配內(nèi)存。(2)內(nèi)存保護(hù)：保證各程序在自己的內(nèi)存區(qū)域內(nèi)運(yùn)行而互不干擾。(3)內(nèi)存擴(kuò)充存儲器管理 有效的支持文件的存儲，檢索和修改，解決文件的共享，保密和保護(hù)問題。(1) 文件存儲空間的管理。(2) 目錄管理。(3) 文件操作管理。(4) 文件保護(hù)。三種用戶接口：(1) 命令接口。(2

6、) 程序接口：也稱為系統(tǒng)調(diào)用。(3) 圖形接口：是命令接口的圖形化。用戶接口6. 操作系統(tǒng)的特征:并發(fā)性注意并行性跟并發(fā)性的區(qū)別：并行性：兩個或多個時間在同一時刻發(fā)生。并發(fā)性：兩個或多個事件在同一時間間隔內(nèi)發(fā)生。共享性系統(tǒng)中的資源可以供多個并發(fā)執(zhí)行的進(jìn)程共同使用。互斥共享：例如打印機(jī)，磁帶機(jī)。同時訪問：例如磁盤以及一些重入碼編寫的文件。虛擬性通過某種技術(shù)把一個物理實體變成若干個邏輯上的對應(yīng)物。異步性在多道程序環(huán)境下，由于資源等因素的限制，程序是以走走停停的方式運(yùn)行的。系統(tǒng)中的每道程序何時執(zhí)行，多道程序間的執(zhí)行順序以及完成每道程序所需的時間都是不確定的，因而也是不可未知的。7. 微內(nèi)核特點：（1

7、） 足夠小的內(nèi)核：微內(nèi)核紙包括操作系統(tǒng)中最基本的部分，是操作系統(tǒng)的小核心，它將各種操作系統(tǒng)共同需要的核心功能提煉出來，形成微內(nèi)核的基本功能。這些基本功能包括：進(jìn)程管理，低級存儲器管理，中斷和陷入的處理。（2） 基于客戶/服務(wù)器模式：操作系統(tǒng)最基本的部分放入內(nèi)核中，大部分放在內(nèi)核外的一組服務(wù)器（進(jìn)程）中實現(xiàn)。（3） 應(yīng)用機(jī)制和策略分離的技術(shù)：機(jī)制是實現(xiàn)某一功能的具體執(zhí)行機(jī)構(gòu)，而策略處于系統(tǒng)的高層。（4） 面向?qū)ο蟮募夹g(shù)：微內(nèi)核是操作系統(tǒng)發(fā)展的最新成果，具有提高系統(tǒng)的擴(kuò)展性，增強(qiáng)系統(tǒng)的可靠性，可移植性和可以支持分布式系統(tǒng)，采用面向?qū)ο蠹夹g(shù)等特點。主要思想：在操作系統(tǒng)內(nèi)核中只留下一些最基本的功能，而

8、將其他服務(wù)盡可能地從內(nèi)核中分離出去，用若干個運(yùn)行在用戶態(tài)下的進(jìn)程來實現(xiàn)。優(yōu)點：（1） 每個服務(wù)進(jìn)程運(yùn)行在獨立的用戶進(jìn)程中，即某個服務(wù)器失敗或產(chǎn)生問題時不會引起系統(tǒng)其他服務(wù)器和其他組成部分的崩潰，可靠性好。（2） 系統(tǒng)具有很好的靈活性，只要接口規(guī)范，操作系統(tǒng)可以方便地增刪服務(wù)功能。（3） 便于維護(hù)，即修改服務(wù)器的代碼不會影響、（4） 系統(tǒng)其他部分。缺點：效率不高，因為所有的用戶進(jìn)程都要通過微內(nèi)核相互通信，所以微內(nèi)核本身就成了系統(tǒng)的瓶頸，尤其是通信頻繁的系統(tǒng)。8. 客戶/服務(wù)器模式即C/S模式，普通用戶進(jìn)程可以通過內(nèi)核像服務(wù)器進(jìn)程發(fā)送請求，以取得操作系統(tǒng)的服務(wù)。優(yōu)點：既允許數(shù)據(jù)的分布處理和存儲，又

9、便于集中管理，靈活性和可擴(kuò)充性強(qiáng)，容易修改。缺點：存在不可靠性和瓶頸問題。（服務(wù)器是瓶頸）9. 操作系統(tǒng)的硬件環(huán)境：（1）特權(quán)指令和非特權(quán)指令特權(quán)指令在指令系統(tǒng)中那些只能由操作系統(tǒng)使用的指令。非特權(quán)指令用戶只能使用的指令。問題：如果用戶想要使用特權(quán)指令，只能通過系統(tǒng)調(diào)用來實現(xiàn)，否則會使系統(tǒng)陷入混亂。（2） 處理機(jī)的狀態(tài)：核心態(tài)（管態(tài)，系統(tǒng)態(tài)）全部指令可以執(zhí)行，可以使用所有資源并具有改變處理機(jī)狀態(tài)的能力。用戶態(tài)（目態(tài)）只有非特權(quán)指令能執(zhí)行。注意：在系統(tǒng)調(diào)用時，將由用戶態(tài)轉(zhuǎn)到核心態(tài)。（3）存儲器的類型：分類定義作用（舉例）讀/寫存儲器可以把數(shù)據(jù)存入其中任一地址單元，并且可在以后的任何時候把數(shù)據(jù)讀出

10、來或者重新存入別的數(shù)據(jù)。通常被稱為隨機(jī)訪問存儲器（RAM）用于存放隨機(jī)存取的程序和數(shù)據(jù)。只讀型存儲器只能從其中讀取數(shù)據(jù)。通常被稱為只讀存儲器（ROM）磁帶機(jī)（4） 存儲器的層次結(jié)構(gòu)：光盤存儲器硬盤存儲器內(nèi)存儲器高速緩存寄存器 （存儲裝置）達(dá)到提高存儲系統(tǒng)效能的關(guān)鍵在于：程序的存儲訪問局部性原理。注意：按層次結(jié)構(gòu)來設(shè)計操作系統(tǒng)，就是將操作系統(tǒng)的所有功能模塊按功能的調(diào)用次序排列成若干層，使得功能模塊之間只存在單向調(diào)用和單向依賴。優(yōu)點：模塊間的組織和依賴關(guān)系清晰明了。缺點：個功能模塊應(yīng)該放在哪一層，如何有效地進(jìn)行分層式必須考慮的問題。（5） 常用存儲保護(hù)機(jī)制：界地址寄存器比較簡單，易于實現(xiàn)。在處理機(jī)

11、中設(shè)置一對界限寄存器用來存放概用戶作業(yè)內(nèi)存中的下限和上限地址。當(dāng)處理機(jī)要訪問內(nèi)存時，如果越界就將程序中斷。存儲鍵每個存儲塊都有一個與其相關(guān)的由二進(jìn)制組成的內(nèi)存保護(hù)鍵附加在每個存儲塊上。（6） 緩沖技術(shù)：緩沖區(qū)：是硬件設(shè)備之間進(jìn)行數(shù)據(jù)傳輸時，專門用來暫存這些數(shù)據(jù)的一個存儲區(qū)域。緩沖技術(shù)的用途：處理機(jī)與內(nèi)存之間處理機(jī)與其他外部設(shè)備之間設(shè)備與設(shè)備之間目的：解決部件之間速度不匹配的問題。（7） 中斷：含義：指處理機(jī)對系統(tǒng)中或者系統(tǒng)外發(fā)生的異步事件的響應(yīng)。分類：可屏蔽中斷（I/O中斷） 不可屏蔽中斷（機(jī)器內(nèi)部故障，掉電中斷） 程序錯誤中斷（溢出，除法錯等中斷） 軟件中斷（Trap指令或者終端指令I(lǐng)NT）

12、中斷與異常的區(qū)別：中斷時系統(tǒng)正常功能的一部分，在系統(tǒng)處理完其他事情之后會繼續(xù)執(zhí)行中斷前的進(jìn)程。異常是由錯誤引起的。（通常異常會引起中斷，而中斷未必是由異常引起的）（8） 系統(tǒng)調(diào)用：系統(tǒng)調(diào)用時操作系統(tǒng)提供的用戶接口之一，是由操作系統(tǒng)實現(xiàn)的所有系統(tǒng)調(diào)用所構(gòu)成的集合，即程序接口或應(yīng)用編程接口，是應(yīng)用程序同系統(tǒng)之間的接口。系統(tǒng)調(diào)用把應(yīng)用程序的請求傳給內(nèi)核，調(diào)用相應(yīng)的內(nèi)核函數(shù)完成所需的處理，將處理結(jié)果返回給應(yīng)用程序。組成：進(jìn)程控制、文件系統(tǒng)控制、系統(tǒng)控制、內(nèi)存管理、網(wǎng)絡(luò)管理、socket控制、用戶管理、 進(jìn)程間通信（9） 作業(yè)狀態(tài)：提交狀態(tài) 通過各種輸入設(shè)備將作業(yè)從外部送入計算機(jī)系統(tǒng)的輔助存儲設(shè)備。后備

13、狀態(tài) 等待作業(yè)調(diào)度程序調(diào)度。 運(yùn)行狀態(tài) 被分配所需資源，然后調(diào)入內(nèi)存，并為其創(chuàng)建進(jìn)程。完成狀態(tài) 作業(yè)調(diào)度程序收回其占用的所有資源，做必要的善后處理。第3章 ：進(jìn)程與進(jìn)程管理1. 前趨圖（有向無循環(huán)圖） 圖中每個節(jié)點可以表示一條語句，一個程序段或者一個進(jìn)程，節(jié)點間的有向邊表示兩個節(jié)點之間存在的偏序或前趨關(guān)系“ ”2. 程序的順序執(zhí)行：一個程序中的程序段必須按照某種先后順序執(zhí)行，僅當(dāng)一個操作執(zhí)行完之后才能執(zhí)行后續(xù)操作。特征：順序性嚴(yán)格按照程序所規(guī)定的順序執(zhí)行封閉性程序一旦開始運(yùn)行，執(zhí)行結(jié)果不受外界因素影響。可再現(xiàn)性只要程序執(zhí)行的初始狀態(tài)和執(zhí)行環(huán)境相同，當(dāng)程序重復(fù)執(zhí)行時，都將獲得相同的結(jié)果。3. 程

14、序的并發(fā)執(zhí)行：注意并發(fā)跟并行的區(qū)別：并行兩個或多個事件在同一時刻發(fā)生。并發(fā)兩個或多個事件在同一時間間隔內(nèi)發(fā)生。特征：（相比順序執(zhí)行）間斷性由共享資源而產(chǎn)生的間接制約關(guān)系，這種制約關(guān)系將導(dǎo)致并發(fā)程序具有“執(zhí)行暫停執(zhí)行執(zhí)行”這種間接性的活動規(guī)律。失去封閉性程序并發(fā)執(zhí)行時，多個程序共享系統(tǒng)資源，故這些資源的狀態(tài)將由多個程序來改變，致使程序的運(yùn)行失去封閉性。不可再現(xiàn)性程序并發(fā)執(zhí)行時，由于失去了封閉性，將導(dǎo)致也失去其運(yùn)行結(jié)果的可再現(xiàn)性。程序和計算不再一一對應(yīng)在并發(fā)執(zhí)行時，一個共享程序可為多個用戶作業(yè)調(diào)用，而使該程序處于多個執(zhí)行中，因而形成了多個“計算”。注意：引入并發(fā)的目的是為了提高資源的利用率，從而提

15、高系統(tǒng)的效率。程序并發(fā)執(zhí)行，雖然能有效地提高資源利用率和系統(tǒng)吞吐量，但必須采取某種措施使并發(fā)程序保持“可再現(xiàn)性”。4. 多道程序設(shè)計：注意一點：核心是并發(fā)。5. 進(jìn)程（1） 定義：進(jìn)程是一個程序?qū)δ硞€數(shù)據(jù)集的一次運(yùn)行活動。（進(jìn)程是動態(tài)的概念，程序是靜態(tài)的概念）（2） 特征：動態(tài)性進(jìn)程是程序在處理器上的一次執(zhí)行過程過程。并發(fā)性多個進(jìn)程同時存在于內(nèi)存中，能在一段時間內(nèi)同時運(yùn)行。引入進(jìn)程的目的是使程序能于其他程序并發(fā)執(zhí)行，以提高資源利用率。獨立性進(jìn)程是一個能獨立運(yùn)行運(yùn)行的基本單位，也是系統(tǒng)進(jìn)行資源分配和調(diào)度的獨立單位。異步性進(jìn)程以各自獨立的，不可預(yù)知的速度向前推進(jìn)。結(jié)構(gòu)特征為了描述和記錄進(jìn)程的運(yùn)動變

16、化過程，引入了進(jìn)程控制模塊PCB。從結(jié)構(gòu)上看，進(jìn)程=程序段+數(shù)據(jù)段+PCB（3）3種基本狀態(tài)：就緒狀態(tài)進(jìn)程已獲得除了處理器以外的其他所有資源。執(zhí)行狀態(tài)獲得必要資源在CPU上面執(zhí)行。阻塞狀態(tài)正在執(zhí)行的進(jìn)程，由于發(fā)生某事件而暫時無法執(zhí)行下去。（注意：當(dāng)進(jìn)程處于阻塞狀態(tài)時，即使把處理器分配給該進(jìn)程，也無法運(yùn)行）執(zhí)行狀態(tài)就緒狀態(tài)阻塞狀態(tài)三個狀態(tài)相互轉(zhuǎn)換： ：進(jìn)程分配到處理機(jī)。：在分時系統(tǒng)中，正在執(zhí)行的進(jìn)程由于時間片用完而暫時被暫停執(zhí)行。在搶占調(diào)度方式中，一個優(yōu)先級高的進(jìn)程可以搶占一個正在進(jìn)行的優(yōu)先級低的進(jìn)程的處理機(jī)。：因為某事件而無法執(zhí)行。例如：臨界資源被其他進(jìn)程訪問。：進(jìn)程等待的事件發(fā)生而被喚醒。執(zhí)

17、行狀態(tài)就緒狀態(tài)阻塞狀態(tài)靜止就緒靜止阻塞（4） 引入掛起狀態(tài)： 條件激活 掛起 掛 激 掛 激 起 活 起 活 在上面三個狀態(tài)轉(zhuǎn)換的基礎(chǔ)上加入一個掛起狀態(tài)。（5）為什么說PCB是進(jìn)程存在的唯一標(biāo)識？首先看PCB的作用：是系統(tǒng)為每個進(jìn)程定義的一個數(shù)據(jù)結(jié)構(gòu)，是為了使程序能獨立運(yùn)行。PCB是為了保 證程序的并發(fā)執(zhí)行。創(chuàng)建進(jìn)程實質(zhì)是創(chuàng)建PCB，撤銷進(jìn)程，實質(zhì)上是撤銷PCB.接下來：PCB保存著處理機(jī)的狀態(tài)信息，系統(tǒng)總是通過PCB對進(jìn)程進(jìn)行控制。（6） 進(jìn)程的創(chuàng)建：一個進(jìn)程可以創(chuàng)建若干個新的進(jìn)程，新的進(jìn)程又可以創(chuàng)建子進(jìn)程。（一般用前趨圖表示）過程：申請空白進(jìn)程控制塊 為新進(jìn)程分配資源 初始化進(jìn)程控制塊 將

18、新進(jìn)程插入就緒隊列（7） 進(jìn)程的終止：引起終止事件：正常結(jié)束 越界錯誤：程序所訪問的存儲區(qū)已越出該進(jìn)程的區(qū)域。 保護(hù)錯誤：以不適當(dāng)?shù)姆椒ㄟM(jìn)行訪問。 特權(quán)指令錯誤：用戶進(jìn)程試圖去執(zhí)行一條只允許操作系統(tǒng)執(zhí)行的指令。 異常結(jié)束： 非法指令錯：試圖去執(zhí)行一條不存在的指令。 運(yùn)行超時：執(zhí)行時間超出指定的最大值。 等待超時 算數(shù)運(yùn)算錯：進(jìn)程試圖去執(zhí)行一個被禁止的計算 I/0故障 外界干預(yù)過程：從PCB中讀出進(jìn)程的狀態(tài) 終止進(jìn)程執(zhí)行并設(shè)置調(diào)度標(biāo)志為真 如進(jìn)程還有子孫進(jìn)程，也予以終止歸還進(jìn)程的資源給系統(tǒng) 將被終止的進(jìn)程的PCB從所在隊列移除（8） 進(jìn)程的阻塞和喚醒：阻塞原語：執(zhí)行狀態(tài) 阻塞狀態(tài) （進(jìn)程自己調(diào)用

19、）過程：停止當(dāng)前進(jìn)程的運(yùn)行 保存該進(jìn)程的CPU現(xiàn)場 停止運(yùn)行該進(jìn)程 轉(zhuǎn)到進(jìn)程調(diào)度程序喚醒原語：阻塞狀態(tài) 就緒狀態(tài) （另一個發(fā)現(xiàn)者調(diào)用）過程：將被喚醒進(jìn)程從相應(yīng)的等待隊列中移除 將狀態(tài)改為就緒并插入相應(yīng)的就緒隊列（9） 調(diào)度方式：非剝奪方式（非搶占方式）即使有優(yōu)先級高的進(jìn)程進(jìn)入就緒隊列，也直到正在進(jìn)行的進(jìn)程完成或者因某事件而進(jìn)入阻塞時，才讓優(yōu)先級高的進(jìn)程執(zhí)行。剝奪方式（搶占方式）當(dāng)有某個優(yōu)先級更高的進(jìn)程進(jìn)入就緒隊列，則立即暫停正在執(zhí)行的進(jìn)程，將處理器分配給優(yōu)先級高的進(jìn)程。（10）進(jìn)程調(diào)度算法：先來先服務(wù)（最簡單）：按照進(jìn)入就緒隊列的先后次序來分配處理器。短作業(yè)優(yōu)先（SJF）：把處理器分配給最快完

20、成的作業(yè)。優(yōu)先級調(diào)度：把處理器分配給優(yōu)先級最高的進(jìn)程。 按進(jìn)程累確定（系統(tǒng)進(jìn)程>用戶進(jìn)程） 靜態(tài)優(yōu)先級 按作業(yè)的資源要求（申請資源越多，優(yōu)先級越低） 進(jìn)程優(yōu)先級 按用戶類型和要求（收費標(biāo)準(zhǔn)越高，優(yōu)先級越高） 占用CPU時間長短（時間越長，優(yōu)先級越低） 動態(tài)優(yōu)先級 等待CPU時間長短（時間越長，優(yōu)先級越高）時間片輪轉(zhuǎn)（分時系統(tǒng)）：等將所有就緒進(jìn)程按時間先后排成隊列，進(jìn)程調(diào)度選擇第一個進(jìn)程執(zhí)行，并 規(guī)定一個時間（時間片），當(dāng)一進(jìn)程執(zhí)行完規(guī)定的時間，即使沒有執(zhí)行結(jié)束， 也把它送到隊尾，輪流進(jìn)行，直到所有進(jìn)程都執(zhí)行結(jié)束。時間片的大小 系統(tǒng)響應(yīng)時間（進(jìn)程數(shù)目一定，時間片大小與系統(tǒng)響應(yīng)時間成正比）決

21、定因素： 就緒隊列中的進(jìn)程數(shù)目（響應(yīng)時間一定，時間片大小與進(jìn)程數(shù)目成反比） 系統(tǒng)的處理能力（速度越快，時間片越短）高響應(yīng)比優(yōu)先調(diào)度：綜合了先來先服務(wù)和短作業(yè)優(yōu)先（每次進(jìn)行作業(yè)調(diào)度時，先計算就緒隊列中的每 個作業(yè)的響應(yīng)比） 響應(yīng)比= 作業(yè)響應(yīng)時間 = 作業(yè)等待時間 + 估計運(yùn)行時間 估計運(yùn)行時間 估計運(yùn)行時間多級隊列調(diào)度：根據(jù)進(jìn)程的性質(zhì)或類型，將就緒隊列劃分為若干個獨立的隊列，每個進(jìn)程固定地分屬 于一個隊列。每個隊列采用一種調(diào)度算法，不同的隊列可以采用不同的調(diào)度算法。例：為交互型任務(wù)設(shè)置一個就緒隊列，該隊列采用時間片輪轉(zhuǎn)調(diào)度算法； 為批處理任務(wù)另外設(shè)置一個就緒隊列，該隊列采用先來先服務(wù)調(diào)度算法。

22、多級反饋隊列調(diào)度：綜合了時間片輪轉(zhuǎn)調(diào)度算法和優(yōu)先級調(diào)度算法。（通過調(diào)整進(jìn)程優(yōu)先級和時間片的 大小，可以兼顧多方面的系統(tǒng)目標(biāo)。）CPU就緒隊列（1）算法示意圖： 完成 優(yōu)先級逐漸降低 時間片逐漸增大CPU就緒隊列（2） 完成CPU就緒隊列（n） 完成（11）進(jìn)程與線程的比較：線程進(jìn)程調(diào)度獨立調(diào)度的基本單位。同一進(jìn)程中線程的切換不會引起進(jìn)程的切換。擁有資源的基本單位。不同的進(jìn)程中進(jìn)行線程的切換將會引起進(jìn)程的切換。擁有資源不擁有系統(tǒng)資源，但是線程可以訪問其隸屬進(jìn)程的系統(tǒng)資源。擁有資源的基本單位。并發(fā)性同一進(jìn)程內(nèi)的多個線程之間可以并發(fā)，大大提高了系統(tǒng)的吞吐量。多個進(jìn)程可以并發(fā)執(zhí)行。系統(tǒng)開銷開銷小開銷大

23、 第四章 進(jìn)程同步與通信1. 進(jìn)程間的聯(lián)系：資源共享關(guān)系共享CPU和I/O設(shè)備。進(jìn)程同步的主要任務(wù)是保證進(jìn)程能互斥的訪問臨界資源，為此，資源不允許用戶進(jìn)程直接使用，而由系統(tǒng)一一分配。相互合作關(guān)系進(jìn)程同步的主要任務(wù)是保證相互合作的諸進(jìn)程在執(zhí)行次序上的協(xié)調(diào)，不會出現(xiàn)時間與空間有關(guān)的差錯。2. 臨界資源定義： 臨界資源是指每次僅允許一個進(jìn)程訪問的資源。 屬于臨界資源的硬件有打印機(jī)、磁帶機(jī)等,軟件有消息緩沖隊列、變量、數(shù)組、緩沖區(qū)等。3. 臨界區(qū)定義： 不論是硬件臨界資源，還是軟件臨界資源，多個進(jìn)程必須互斥地對它進(jìn)行訪問。 每個進(jìn)程中訪問臨界資源的那段代碼稱為臨界區(qū)。3. 生產(chǎn)者消費者問題：（1個生產(chǎn)

24、者1個消費者）描述：一組生產(chǎn)者向一組消費者提供產(chǎn)品，他們共享一個有界緩沖區(qū)，生產(chǎn)者向其中投入產(chǎn)品，消費者從中取走產(chǎn)品。解決方法：設(shè)一個數(shù)組來表示n個緩沖區(qū)的緩沖池。 一個輸入指針in表示下一個可投放產(chǎn)品的緩沖區(qū)。 一個輸出指針out指示下一個可獲取產(chǎn)品的緩沖區(qū)。 一個整型變量counter，初始值為0。生產(chǎn)者和消費者共享下面的變量：Typedef . Item;int n;item buffern;int in,out,counter;指針in 和out 初始化為1，在生產(chǎn)者進(jìn)程使用一個局部變量nextp，用于暫存每次剛生產(chǎn)出來的產(chǎn)品。在消費者進(jìn)程中使用一個局部變量nextc用于暫存每次要消費

25、的產(chǎn)品。void producer( ) /生產(chǎn)者進(jìn)程while (1) /當(dāng)為真時porduce an item in nextp; while (counter=n) /當(dāng)counter的值為n的時候，執(zhí)行一條空操作，否則把nextpno-op; 這個局部變量賦值給指針inbufferin=nextp; /把nextp看成一個籃子，把籃子頭的東西放進(jìn)去in=（in+1）mode n; /當(dāng)生產(chǎn)者投放一個產(chǎn)品后，指針in向后移動一位counter +; /counter的值+1void consumer( ) /消費者進(jìn)程while (1) /當(dāng)為真時while (counter=0) /當(dāng)

26、counter的值為0的時候，執(zhí)行一條空操作no-op;nextc=bufferout; /把緩沖池上的東西放到籃子頭去，再拿去消費out=(out+1)mode n; /消費者取走一個產(chǎn)品后，輸入指針out向后移動一位counter-; /ounter的值-1consume the item in nextc;問題：關(guān)鍵在于counter的值失去了可再現(xiàn)性，如果兩個進(jìn)程并發(fā)執(zhí)行時，就會使counter的值不同。4. 同步機(jī)制應(yīng)該遵循的準(zhǔn)則：空閑讓進(jìn)當(dāng)臨界資源處于空閑狀態(tài)時，可以允許一個要求進(jìn)入臨界區(qū)的進(jìn)程進(jìn)入自己的臨界區(qū)，有效地利用臨界資源。忙則等待當(dāng)已經(jīng)有進(jìn)程處于自己的臨界區(qū)時，其他所有想

27、要進(jìn)入臨界區(qū)的進(jìn)程都必須等待，以保證進(jìn)程互斥。有限等待對要求訪問臨界資源的進(jìn)程，應(yīng)保證該進(jìn)程能在有效地時間內(nèi)進(jìn)入自己的臨界區(qū)，以免陷入“死等”的狀態(tài)。讓權(quán)等待當(dāng)進(jìn)程不能進(jìn)入自己的臨界資源，應(yīng)立即釋放處理機(jī)，以免陷入“忙等”狀態(tài)。（處理機(jī)本身是臨界資源）5. 軟件方法解決互斥問題：算法1：（強(qiáng)行輪流法）設(shè)置一個公用變量turn，用于指被允許進(jìn)入臨界區(qū)的進(jìn)程的編號。進(jìn)程p1和p2，p3訪問臨界資源，turn=1表示p1可以訪問，訪問完之后trun變成2，p2可以訪問。問題：如果p2暫時不想訪問，p3想訪問,就必須等到p2訪問完之后才能訪問。算法2：（查看標(biāo)志法）設(shè)置一個數(shù)組，p1的flag0=1表

28、示p1正在訪問，p2的flag1=1表示p2正在訪問，p3的flag2=1表示p3正在訪問。問題：如果3個進(jìn)程都要訪問，都發(fā)現(xiàn)對方的flag為0，所以3個進(jìn)程都進(jìn)入臨界區(qū)，違背了要互斥訪問臨界資源的原則了。算法3：（先標(biāo)記，再看別人）設(shè)置一個數(shù)組，flag0=1表示p1希望進(jìn)入臨界區(qū)，然后去查看p2的flag1=1，表示p2也想進(jìn)入或者p2已經(jīng)進(jìn)入了臨界區(qū)，那么p1等待。問題：當(dāng)3個進(jìn)程都要進(jìn)入臨界區(qū)，當(dāng)檢查到對方的flag為1，每個進(jìn)程都等待，結(jié)果每個人沒有訪問到臨界資源。算法4：（君子裁判法模式，算法1+算法3）設(shè)置一個數(shù)組和一個turn變量。Flag0=1表示p1要求進(jìn)入臨界區(qū)或者正在臨

29、界區(qū)中執(zhí)行。While (1)Flag0=1;turn=2; /p1想進(jìn)入臨界區(qū)，就先把flag0=1，然后將turn變成2，去While (flag1=1&&turn=2) 試探進(jìn)程p2。flag1=1&&turn=2的反義詞就是flag1=0No-op; or turn=1Critical section;Flag0=0;6. 用硬件方法解決進(jìn)程互斥：P102（1） 利用Test-and-set指令實現(xiàn)互斥（2） 利用Swap指令實現(xiàn)進(jìn)程互斥主要思想：用一條指令完成標(biāo)志的檢查和修改兩個操作，因而保證了檢查操作與修改操作不被打斷；或者通過中斷屏蔽的方法來保證檢

30、查和修改作為一個整體執(zhí)行。優(yōu)點：適用范圍廣；簡單；支持多個臨界區(qū)。缺點：不能實現(xiàn)讓權(quán)等待（需要軟件配合進(jìn)行判斷）。7. 信號量機(jī)制：（1）基本思想：在多個相互合作的進(jìn)程之間使用簡單的信號來同步。（2）PV操作：信號量是一個確定的二元組（s,q）,其中s是一個具有非負(fù)初值的整型變量，設(shè)s為一個信號量；q是一個初始狀態(tài)為空的隊列。P(s)完成以下動作：先執(zhí)行s=s-1，若執(zhí)行后的s>=0,則進(jìn)程繼續(xù)執(zhí)行；若執(zhí)行后的s<0，則阻塞該進(jìn)程，并插入到信號量的等待隊列中。（申請資源wait）V(s)完成以下動作：先執(zhí)行s=s+1，若執(zhí)行后的s>0,則進(jìn)程繼續(xù)執(zhí)行；若執(zhí)行后的s<=0

31、，則從該信號量等待隊列中移除第一個進(jìn)程，并插入到信號量的等待隊列中。（釋放資源signal）（3）記錄型信號量機(jī)制 ：有一個用于代表資源數(shù)目的整型變量vlaue和一個進(jìn)程鏈表L，用于鏈接所有等待該信號量代表資源的進(jìn)程。描述如下：typedef structint value;/代表資源數(shù)目list of process *L; /進(jìn)程鏈表L(記錄所有需要資源的進(jìn)程)semaphore（4）利用信號量實現(xiàn)進(jìn)程互斥為臨界資源設(shè)置一個信號量mutex，并且初值為1，然后將個進(jìn)程的臨界區(qū)放在wait(mutex)和signal(mutex)之間。（5）利用信號量描述程序或者語句的前趨關(guān)系( P105

32、)8. 信號量集機(jī)制（1）And信號量集機(jī)制p105基本思想：將進(jìn)程在整個運(yùn)行過程中所需要的所有臨界資源一次性全部分配給進(jìn)程，使用完之后再一起釋放。對若干個臨界資源的分配采取原子操作，要么全部分配到進(jìn)程，要么一個也得不到。（2）一般信號量集機(jī)制p106基本思想：當(dāng)一次需要n個某類資源時，便需要進(jìn)行n次wait操作，顯然是低效的。所以需要進(jìn)行判斷：當(dāng)資源數(shù)量低于某一下限時便不予分配。幾種特殊情況：Wait(s,d,d)只有一個信號量，但是允許每次申請d個資源，當(dāng)現(xiàn)有資源數(shù)少于d時，不予分配。Wait(s,1,1)一般記錄型信號量。Wait(s,1,0)當(dāng)s>=1時，允許多個進(jìn)程進(jìn)入某個特定

33、區(qū)，當(dāng)s變?yōu)?時，阻止任何進(jìn)程進(jìn)入特定區(qū)。9. 經(jīng)典同步問題：（1）生產(chǎn)者消費者問題：利用記錄型信號量解決生產(chǎn)者消費者問題。（P107-P109）描述：在生產(chǎn)者和消費者之間的公用緩沖池中有n個緩沖區(qū)，設(shè)置一個互斥信號量mutex。 一個輸入指針in表示下一個可投放產(chǎn)品的緩沖區(qū)。 一個輸出指針out指示下一個可獲取產(chǎn)品的緩沖區(qū)。（指針in 和out 初始化為1） 在生產(chǎn)者進(jìn)程使用一個局部變量nextp，用于暫存每次剛生產(chǎn)出來的產(chǎn)品。 在消費者進(jìn)程中使用一個局部變量nextc用于暫存每次要消費的產(chǎn)品。 資源信號量empty和full分別表示空緩沖區(qū)數(shù)量和滿緩沖區(qū)數(shù)量。代碼描述：semaphore

34、mutex=1;/緩沖區(qū)進(jìn)行操作的互斥信號量semaphore empty=n;/空緩沖區(qū)的數(shù)量為nsemaphore full=0;/ 滿緩沖區(qū)的數(shù)量為0item buffern;/數(shù)組表示緩沖區(qū)個數(shù)int out=in=0;void producer( )while (1)produde an item in nextp;/nextp是一個臨時緩沖區(qū)，比喻成一個籃子。wait(empty);/ 申請一個空的緩沖區(qū)(保證要有一個空的緩沖區(qū))wait(mutex);/申請使用緩沖池bufferin=nextp;/將產(chǎn)品放入緩沖池。把nextp看成一個籃子，把籃子頭的東西放進(jìn)去in=(in+1)

35、mod n; /當(dāng)生產(chǎn)者投放一個產(chǎn)品后，指針in向后移動一位signal(mutex);/緩沖池使用完畢，釋放互斥信號量signal(full);/增加一個滿緩沖池void consumer( )while(1)wait(full);/申請一個滿緩沖池（保證要有個一個滿的緩沖區(qū)）wait(mutex);/申請使用緩沖池nextc=bufferout; /把緩沖池上的東西放到籃子頭去，再拿去消費out=(out+1) mod n; /消費者取走一個產(chǎn)品后，輸入指針out向后移動一位signal(mutex); /緩沖池使用完畢，釋放互斥信號量signal(empty); /增加一個空的緩沖池ma

36、in( )cobeginproducer( );consumer( );利用AND信號量集機(jī)制解決生產(chǎn)者消費者問題：P109-110描述：只有緩沖區(qū)全滿或者全空的時候，指針in 和out才會指向同一緩沖區(qū)，所以可以設(shè)置兩個互斥信號量mutex1和mutex2。代碼描述：semaphore mutex1=mutex2=1;/緩沖區(qū)進(jìn)行操作的互斥信號量semaphore empty=n;/空緩沖區(qū)的數(shù)量為nsemaphore full=0;/ 滿緩沖區(qū)的數(shù)量為0item buffern;/數(shù)組表示緩沖區(qū)個數(shù)int out=in=0;void producer( )while (1)produde

37、an item in nextp;/nextp是一個臨時緩沖區(qū)，比喻成一個籃子。Swait(empty,mutex1)/ 申請一個空的緩沖區(qū)(保證要有一個空的緩沖區(qū))和申請使用緩沖池bufferin=nextp;/將產(chǎn)品放入緩沖池。把nextp看成一個籃子，把籃子頭的東西放進(jìn)去in=(in+1)mod n; /當(dāng)生產(chǎn)者投放一個產(chǎn)品后，指針in向后移動一位Ssignal(mutex1,full)/緩沖池使用完畢，釋放互斥信號量和增加一個滿緩沖池void consumer( )while(1)Swait(full,mutex2)/申請一個滿緩沖池（保證要有個一個滿的緩沖區(qū)）和申請使用緩沖池next

38、c=bufferout; /把緩沖池上的東西放到籃子頭去，再拿去消費out=(out+1) mod n; /消費者取走一個產(chǎn)品后，輸入指針out向后移動一位Ssignal(mutex2,empty)/緩沖池使用完畢，釋放互斥信號量并且增加一個空的緩沖池main( )cobeginproducer( );consumer( );利用管程解決生產(chǎn)者消費者問題：P117描述：建立一個管程命名為P-C，其中包含兩個過程：（1）put(item)生產(chǎn)者將自己生產(chǎn)的產(chǎn)品投放到緩沖池，并用count來表示在緩沖池已有的產(chǎn)品數(shù)目。（2）get(item)消費者從緩沖池取得一個產(chǎn)品。P-C代碼描述：monito

39、r P-Cint in,out,count;item buffern;condition notfull,notempty;entry put(item) /生產(chǎn)者生產(chǎn)產(chǎn)品if(count>=n)notfull.wait;/生產(chǎn)者需要等待一個空的緩沖區(qū)。bufferin=nextp;/否則，將籃子里面的產(chǎn)品放到空的緩沖區(qū)in=（in+1）mod n;/指針in向后移動一位count+;/count的值+1notempty.signal;/釋放之后，多了一個滿的緩沖區(qū)entry get(item)/消費者消費產(chǎn)品if(count<=0)notempty.wait;/消費者需要等待一個

40、滿的緩沖區(qū)。nextc=bufferout;/ 把緩沖池上的東西放到籃子頭去，再拿去消費out=(out+1)mod n;/ 消費者取走一個產(chǎn)品后，輸入指針out向后移動一位count -;notfull.signal;/釋放之后，多了一個空的緩沖區(qū)int=out=0;/初始化count=0;（2）讀者寫者問題：利用記錄型信號量解決讀者寫者問題：P111 （讀者優(yōu)先）問題描述：“讀者優(yōu)先”除了某個寫者正在訪問數(shù)據(jù)之外，任何情況下讀者想要訪問數(shù)據(jù)均可以直接進(jìn)行訪問，即只要存在讀者正在訪問數(shù)據(jù)，后續(xù)到達(dá)的那些欲訪問數(shù)據(jù)的讀者就無須判斷此時是否存在等待訪問數(shù)據(jù)的寫者，均直接訪問。設(shè)置變量描述：設(shè)置互

41、斥信號量mutex，實現(xiàn)讀者與寫者的互斥，讀者與寫者之間有一個數(shù)據(jù)區(qū)。整型變量readcount表示正在讀的進(jìn)程的數(shù)目。僅當(dāng)readcount=0時，沒有讀者進(jìn)程在進(jìn)行，此時需要執(zhí)行wait(mutex)，操作成功，讀者進(jìn)程就可以進(jìn)入臨界區(qū)。相應(yīng)的，當(dāng)readcount之后的值為0，執(zhí)行signal(mutex)。為readcount設(shè)置一個互斥信號量rmutex。代碼描述：Semaphore rmutex=mutex=1;/int readcount=0;/用于記錄讀者數(shù)量void reader(int i)while(1) wait(rmutex);/讀者去申請readcount的使用權(quán)i

42、f (readcount=0)/如果readcount的值為0，那么就去申請使用數(shù)據(jù)區(qū)。否則直接readcount+1 wait(mutex);readcount+;signal(rmutex);/釋放掉rmutex，讓后面進(jìn)來的讀者可以申請到readcount，perform read operation; /開始讀的操作wait(rmutex); /再去申請rmutex使得readcount-1。readcount-;if(readcount=0) /判斷readcount的值，判斷是否是最后一個讀者然后好釋放mutex signal(mutex);signal(rmutex); Void

43、 writer(int i)While(1)Wait(mutex);Perform write operation;Signal(mutex);Main()Cobegin /并發(fā)執(zhí)行Reader(1);.Reader(n);Writer(1);.Writer(m);利用信號量集機(jī)制解決讀者寫者問題：P112 （讀者優(yōu)先）描述：增加了一條限制，即最多只允許RN個讀者進(jìn)去同時讀。所以引入了一個信號量L并賦予初值RN。代碼描述：#define RNsemaphore L=RN mx=1; /設(shè)置一個信號量L和mx(若mx=1讀者可以進(jìn)去讀，若mx=0寫者可以進(jìn)去讀)void reader( )whi

44、le()swait(L,1,1); /進(jìn)去一個讀者進(jìn)行判斷（相當(dāng)于限制房間的座位數(shù)）swait(mx,1,0); /再進(jìn)行mx的判斷，mx=1讀者可以進(jìn)去讀，mx=0寫者可以進(jìn)去寫perform read operation;signal(L,1); /釋放掉一個L（相當(dāng)于增加一個座位數(shù)）void writer( )while (1)swait(mx,1,1,L,RN,0);/當(dāng)mx=1時，mx-1=1-1=0<1(開關(guān)關(guān)閉)并且L=RN,L-RN=0(沒有讀者perform write operation; 在房間里面），寫者才進(jìn)去進(jìn)行寫的操作。signal(mx,1); /寫完之后釋

45、放掉mx使其+1，讓下一個想進(jìn)入房間的讀者或者寫著能夠打 開門。利用管程解決讀者寫者問題：P120 （寫著優(yōu)先）問題描述：在寫者訪問數(shù)據(jù)時，若后面的等待隊列里面還有等待的寫者，那么就會優(yōu)先喚醒等待的寫者，直到等待的寫者都訪問完數(shù)據(jù)，最后一個寫者訪問完數(shù)據(jù)時，就喚醒其他等待的所有讀者。變量的描述：設(shè)置兩個計數(shù)器readercount和writercount分別對讀者進(jìn)程和寫者進(jìn)程計數(shù)。 設(shè)置條件變量R和W分別表示允許讀者讀和允許寫者寫。代碼描述：monitor reader-writerint readercount,writercount;condition R,W;entry start_r

46、ead /開始讀的方法if (writercount>0)R.wait; /先判斷有沒有寫者正在訪問數(shù)據(jù)或者等待訪問數(shù)據(jù)，如果有，readercount+; 那么就R.wait 并且readercount+1R.signal; entry end_read /結(jié)束讀的方法readercount-;if(readercount=0)W.signal;entry start_write /開始寫的方法writercount+; /先讓writercount+1增加一個寫者if(readercount>0)|writercount>0) W.wait; /如果readcount&g

47、t; 0或者writercount> 0 那么W.waitentry end_write /結(jié)束寫的方法writercount-; /先讓writercount-1，少了一個寫者，再判斷-1之后的writercount的if(writercount>0)W.signal; 值，如果>0,就允許寫者寫，否則允許讀者讀。else R.signal;readercount=writercount=0;/ 初始化;（3）哲學(xué)家進(jìn)餐問題：利用管程解決哲學(xué)家進(jìn)餐問題：P118問題描述：哲學(xué)家有三種狀態(tài)：饑餓，思考，進(jìn)餐。三個過程：pickup(int i)：拿起筷子準(zhǔn)備進(jìn)餐。只要他處于饑餓狀態(tài)并且左右的兩個人都沒有進(jìn)餐的話， 就允許他進(jìn)餐，否則的話就用self(i).wait推遲自己進(jìn)餐。putdown(int i)