【正文】 原語(yǔ)發(fā)送消息時(shí)，若沒(méi)有空閑的消息緩沖區(qū)，則發(fā)送進(jìn)程塞阻；當(dāng)接收進(jìn)程調(diào)用 Receive原語(yǔ)接收消息時(shí)，如果沒(méi)有消息可接收，則接收進(jìn)程阻塞，直到一條消息到達(dá)。即，每當(dāng)進(jìn)程需要打印時(shí)，都可以以消息形式發(fā)出請(qǐng)求，然后繼續(xù)執(zhí)行。無(wú)限發(fā)送消息會(huì)消耗處理機(jī)時(shí)間，且由于消息需要占用內(nèi)存的消息緩沖區(qū)，無(wú)限發(fā)送消息也會(huì)消耗其它系統(tǒng)資源。 阻塞接收 ? 并發(fā)程序設(shè)計(jì)中常采用該方式； ? 當(dāng)接收消息的進(jìn)程未收到期望的消息時(shí)，常需要阻塞等待，直到消息到來(lái)。 ? 如果采用“不阻塞接收”方式，則可能因?yàn)榻邮辗降木壒剩瑏G失消息。 ? 若采用直接尋址， send原語(yǔ)中必須指定目標(biāo)進(jìn)程的具體標(biāo)識(shí)號(hào) ? receive原語(yǔ)中的 source地址有兩種處理方法： 接收進(jìn)程顯式地指定發(fā)送方進(jìn)程標(biāo)識(shí)號(hào)，這就要求接收進(jìn)程必須事先清楚將接收哪個(gè)進(jìn)程發(fā)來(lái)的消息 接收進(jìn)程可以不必指定接收哪個(gè)進(jìn)程的消息 間接尋址 ? 采用間接尋址傳遞消息時(shí)，消息不再?gòu)陌l(fā)送方直接發(fā)送到接收方，而是通過(guò)發(fā)送進(jìn)程與接收進(jìn)程共享的一個(gè)數(shù)據(jù)結(jié)構(gòu)進(jìn)行中轉(zhuǎn)，該數(shù)據(jù)結(jié)構(gòu)通常稱為 郵箱 。 郵箱 ? 郵箱不限制進(jìn)程數(shù)，允許多個(gè)發(fā)送進(jìn)程想郵箱發(fā)送消息，同時(shí)，也允許多個(gè)接收進(jìn)程從郵箱接收消息。 ? 當(dāng)?shù)谝粋€(gè)希望進(jìn)入臨界區(qū)的進(jìn)程執(zhí)行receive(mutex,msg)語(yǔ)句時(shí)，從郵箱 mutex中接收了這條“空”消息，進(jìn)入臨界區(qū)執(zhí)行。其后執(zhí)行receive(mutex,msg)語(yǔ)句希望進(jìn)入臨界區(qū)的進(jìn)程被阻塞。 ? 可見，控制進(jìn)程互斥進(jìn)入臨界區(qū)的這條消息本身可以不含任何有用的內(nèi)容，它僅被當(dāng)作進(jìn)程能否進(jìn)入臨界區(qū)的一種憑證，或令牌。 在銀行家算法中，若出現(xiàn)以下資源分配情況： 進(jìn)程 Allocation Need Available R1 R2 R3 R4 R1 R2 R3 R4 R1 R2 R3 R4 P0 0 0 3 2 0 0 1 2 1 6 2 2 P1 1 0 0 0 1 7 5 0 P2 1 3 5 4 2 3 5 6 P3 0 3 3 2 0 6 5 2 P4 0 0 1 4 0 6 5 6 試問(wèn)：（ 1）該狀態(tài)是否安全？ （ 2）如果進(jìn)程 P2申請(qǐng)資源（ 1， 2， 2， 2）后，系統(tǒng)能否將資源分配給它？ 為什么？ 設(shè)有四道作業(yè)，它們的提交時(shí)間和運(yùn)行時(shí)間如下表： 作業(yè)號(hào) 提交時(shí)刻 運(yùn)行時(shí)間 (分鐘 ) 1 1:10 100 2 1:30 30 3 2:10 10 4 2:40 5 求：試給出下面兩種調(diào)度算法下，作業(yè)的平均周轉(zhuǎn)時(shí)間和帶權(quán)平均周轉(zhuǎn)時(shí)間。要求寫出作業(yè)的開始執(zhí)行時(shí)間，完成時(shí)間， 周轉(zhuǎn)時(shí)間和帶權(quán)周轉(zhuǎn)時(shí)間，調(diào)度時(shí)間忽略不計(jì)，保留小數(shù)點(diǎn)后兩位） （ 1）先來(lái)先服務(wù) FCFS調(diào)度算法。 某系統(tǒng)的進(jìn)程狀態(tài)轉(zhuǎn)換如下圖所示。在什么情況下，當(dāng)一個(gè)進(jìn)程發(fā)生轉(zhuǎn)換 3時(shí)能立即引起另一個(gè)進(jìn)程發(fā)生轉(zhuǎn)換 1？ ? 試說(shuō)明是否會(huì)發(fā)生下述因果轉(zhuǎn)換： 2 1 3 2 4 1 a b c 3 4 1 2 總結(jié) 第二章 關(guān)于現(xiàn)代操作系統(tǒng)的四種基本觀點(diǎn) ? 從外部看操作系統(tǒng) 計(jì)算機(jī)用戶的觀點(diǎn)： 用戶環(huán)境觀點(diǎn) 是計(jì)算機(jī)用戶使用計(jì)算機(jī)系統(tǒng)的接口 應(yīng)用程序員的觀點(diǎn)： 虛擬機(jī)器觀點(diǎn) 是建立在計(jì)算機(jī)硬件平臺(tái)上的虛擬機(jī)器 .操作系統(tǒng)在虛擬機(jī)中充當(dāng)管理員和協(xié)調(diào)員的角色 ,管理計(jì)算機(jī)的軟硬件資源 ,并協(xié)調(diào)多任務(wù)、多進(jìn)程的運(yùn)行。 OS開發(fā)者觀點(diǎn)之二： 作業(yè)組織觀點(diǎn) 是計(jì)算機(jī)系統(tǒng)工作流程的組織者 ， 它負(fù)責(zé)協(xié)調(diào)在系統(tǒng)中運(yùn)行的各個(gè)應(yīng)用軟件的運(yùn)行次序 。 單道批處理系統(tǒng)的處理流程 把下一個(gè)作業(yè)的源程序轉(zhuǎn)換為目標(biāo)程序源程序有錯(cuò)嗎？否裝 配目標(biāo)程序還有下一個(gè)作業(yè)？是否停止運(yùn) 行目標(biāo)程序是開始多道批處理系統(tǒng) ? 多道 是指，允許多個(gè)程序同時(shí)存在于主存中，按照某種原則分派處理機(jī)，逐個(gè)執(zhí)行這些程序。然后，由作業(yè)調(diào)度程序按照一定的算法從該隊(duì)列中一次選取一個(gè)或若干個(gè)作業(yè)裝入內(nèi)存執(zhí)行。引入進(jìn)程后，邏輯上可并行的作業(yè)步可在不同的進(jìn)程中運(yùn)行；處理器能在進(jìn)程間切換；原多道程序設(shè)計(jì)系統(tǒng)中的作業(yè)可看做只有一個(gè)進(jìn)程的作業(yè)。進(jìn)程是擁有資源的最小實(shí)體 ,在傳統(tǒng) OS中，進(jìn)程同時(shí)也是系統(tǒng)調(diào)度的最小單位。 進(jìn)程的結(jié)構(gòu) ? 組成（進(jìn)程映像） : 程序、數(shù)據(jù)集合、進(jìn)程控制塊 PCB (Process Control Block ) ? PCB是進(jìn)程存在的唯一標(biāo)志。 PCB ? 進(jìn)程標(biāo)識(shí)信息 ：進(jìn)程的內(nèi)部和外部標(biāo)識(shí)符 ? 處理機(jī)狀態(tài)信息 ：通用寄存器值 、 指令計(jì)數(shù)器值 、程序狀態(tài)字 PSW值 、 用戶棧指針值 ? 進(jìn)程調(diào)度信息 ：進(jìn)程狀態(tài) 、 進(jìn)程優(yōu)先權(quán) 、 進(jìn)程調(diào)度的其它信息 ? 其它信息 ：程序及數(shù)據(jù)地址 、 進(jìn)程同步和通訊機(jī)制 、 資源清單 、 鏈接指針 進(jìn)程的五狀態(tài) ? 執(zhí)行狀態(tài)（ Running） ? 就緒狀態(tài)（ Ready） ? 阻塞狀態(tài)（ Blocked） ? 新狀態(tài)（ New） ? 終止?fàn)顟B(tài)（ Terminated） 1. 新狀態(tài)： 進(jìn)程已經(jīng)創(chuàng)建，但未被 OS接納為可執(zhí)行進(jìn)程 2. 就緒狀態(tài)： 準(zhǔn)備執(zhí)行 3. 執(zhí)行狀態(tài)： 占用處理機(jī)（單處理機(jī)環(huán)境中，某一時(shí)刻僅一個(gè)進(jìn)程占用處理機(jī)） 4. 阻塞狀態(tài)： 等待某事件發(fā)生才能執(zhí)行，如等待 I/O完成等 5. 終止?fàn)顟B(tài)： 因停止或取消，被 OS從執(zhí)行狀態(tài)釋放 新建 就緒 執(zhí)行 阻塞 終止 接納 分派 /調(diào)度 時(shí)間片完 事件發(fā)生 事件等待 完成 圖 五狀態(tài)進(jìn)程模型 ? 為什么引入進(jìn)程？ ?進(jìn)程的概念 、結(jié)構(gòu)、狀態(tài)及其轉(zhuǎn)換 ? 為什么需要對(duì)換技術(shù)？ ? 進(jìn)程的控制 ，控制什么？如何實(shí)現(xiàn)？（執(zhí)行模式、操作系統(tǒng)內(nèi)核、原語(yǔ)） 問(wèn)題： 多個(gè)進(jìn)程競(jìng)爭(zhēng)內(nèi)存資源 ? 內(nèi)存資源緊張 ? 無(wú)就緒進(jìn)程，處理機(jī)空閑： I/O的速度比處理機(jī)的速度慢得多，可能出現(xiàn)全部進(jìn)程阻塞等待 I/O 解決方法 ? 采用交換技術(shù)：換出一部分進(jìn)程到外存，以騰出內(nèi)存空間 ? 采用虛擬存儲(chǔ)技術(shù)：每個(gè)進(jìn)程只能裝入一部分程序和數(shù)據(jù)（存儲(chǔ)管理部分） 對(duì)換技術(shù) ,交換技術(shù) (Swapping ） 將內(nèi)存中暫時(shí)不能運(yùn)行的進(jìn)程，或暫時(shí)不用的數(shù)據(jù)和程序， 換出 到外存，以騰出足夠的內(nèi)存空間，把已具備運(yùn)行條件的進(jìn)程，或進(jìn)程所需要的數(shù)據(jù)和程序， 換入 內(nèi)存。 ? 用戶通過(guò)系統(tǒng)調(diào)用訪問(wèn)操作系統(tǒng)的功能，這些功能最終都通過(guò)操作系統(tǒng)內(nèi)核實(shí)現(xiàn)。 ? 調(diào)度的關(guān)鍵是需要某種方法或算法，好的調(diào)度算法有利于選擇到合適的個(gè)體。 ? 盡量減少進(jìn)程的響應(yīng)時(shí)間 調(diào)度原則 ? 滿足用戶的要求 :響應(yīng)時(shí)間、周轉(zhuǎn)時(shí)間、 ? 滿足系統(tǒng)的需求 ：系統(tǒng)吞吐量、處理機(jī)利用率、各類資源的平衡使用、公平性及優(yōu)先級(jí) 進(jìn)程調(diào)度方式 根據(jù)執(zhí)行進(jìn)程的處理機(jī)是由進(jìn)程自己釋放 ， 還是被強(qiáng)行剝奪 ， 可以將進(jìn)程調(diào)度方式分為 非剝奪方式 和 剝奪方式 兩種 。 ? FCFS算法屬于非剝奪調(diào)度方式 ， 實(shí)現(xiàn)簡(jiǎn)單 ，看似公平 。 進(jìn)程調(diào)度算法 先來(lái)先服務(wù)（ FCFS） ? 對(duì) 短進(jìn)程不公平 。 ? 不利于 I/O型進(jìn)程，未有效利用系統(tǒng)資源。例如，系統(tǒng)可以按照不同的優(yōu)先級(jí)維護(hù)多個(gè)就緒隊(duì)列，每個(gè)隊(duì)列內(nèi)部按照 FCFS算法調(diào)度。 短進(jìn)程優(yōu)先 ? 當(dāng)需要調(diào)度進(jìn)程 （ 或作業(yè) ） 時(shí) ， 通過(guò)計(jì)算判斷就緒進(jìn)程隊(duì)列中哪一個(gè)進(jìn)程的預(yù)期執(zhí)行時(shí)間最短 ， 或后備作業(yè)隊(duì)列中哪一個(gè)或幾個(gè)作業(yè)的預(yù)期執(zhí)行時(shí)間最短 ， 就調(diào)度誰(shuí) 。當(dāng)某進(jìn)程獲得處理機(jī)，直到其執(zhí)行完成，或需要等待某事件而阻塞時(shí)，才自動(dòng)釋放處理機(jī)。 短進(jìn)程優(yōu)先 ? 與 FCFS算法比較 ， 短進(jìn)程優(yōu)先調(diào)度算法改善了系統(tǒng)的性能 ， 降低了系統(tǒng)的平均等待時(shí)間 ， 提高了系統(tǒng)的吞吐量 。 時(shí)間片輪轉(zhuǎn)調(diào)度法 ? 采用基于時(shí)間片輪轉(zhuǎn)調(diào)度算法調(diào)度上例的 4個(gè)進(jìn)程，并分別按照兩種時(shí)間片大小輪轉(zhuǎn)調(diào)度（ 1個(gè)單位時(shí)間和 4和單位時(shí)間），分析該算法的性能。從隊(duì)首開始調(diào)度，首先調(diào)度 P1，執(zhí)行一個(gè)時(shí)間片，強(qiáng)行中斷 P1， P1回到就緒隊(duì)列隊(duì)尾排隊(duì)；切換到 P2，執(zhí)行一個(gè)時(shí)間片，強(qiáng)行中斷P2， P2回到就緒隊(duì)列隊(duì)尾排隊(duì)（排在 P1之后） … 時(shí)間片輪轉(zhuǎn)調(diào)度法 ? 采用基于時(shí)間片輪轉(zhuǎn)調(diào)度法，進(jìn)程的周轉(zhuǎn)時(shí)間和平均周轉(zhuǎn)時(shí)間并不比采用 FCFS和短進(jìn)程優(yōu)先調(diào)度算法小。 時(shí)間片輪轉(zhuǎn)調(diào)度法 ? 常用于分時(shí)系統(tǒng)及事務(wù)處理系統(tǒng) ， 合理的時(shí)間片大小將帶來(lái)滿意的響應(yīng)時(shí)間 。 ? 對(duì)于短的 、 計(jì)算型的進(jìn)程較有利 。 ? 改進(jìn)的方法之一 ， 可以將 I/O阻塞事件完成的進(jìn)程單獨(dú)組織一個(gè)就緒隊(duì)列 ， 該隊(duì)列進(jìn)程的時(shí)間片可以設(shè)置的小一些 ， 且優(yōu)先調(diào)度 。 令 w表示等待時(shí)間 ， s表示預(yù)期執(zhí)行時(shí)間 ， 則響應(yīng)比： 響應(yīng)比高者優(yōu)先 ? 調(diào)度方法：若當(dāng)前執(zhí)行進(jìn)程執(zhí)行完畢，或需要阻塞等待某事件而釋放處理機(jī)，調(diào)度程序選擇就緒隊(duì)列中響應(yīng)比最大的進(jìn)程執(zhí)行。若進(jìn)程的預(yù)期執(zhí)行時(shí)間相同，則等待時(shí)間長(zhǎng)的進(jìn)程優(yōu)先調(diào)度，相當(dāng)于 FCFS。 響應(yīng)比高者優(yōu)先 ? 同短進(jìn)程優(yōu)先和剩余時(shí)間最短者優(yōu)先調(diào)度算法一樣，很難準(zhǔn)確估計(jì)進(jìn)程的預(yù)期執(zhí)行時(shí)間。 線程 ? 多線程 ? 進(jìn)程與線程 ? 線程的類型：用戶