【文章內(nèi)容簡介】 ? 進程只能在臨界區(qū)內(nèi)等待有限時間，不能使其他進程在臨界區(qū)外無限等待。（ 有限等待 ） ? 進入臨界區(qū)的進程不能在臨界區(qū)內(nèi)長時間阻塞等待某事件，必須在一定期限內(nèi)退出臨界區(qū)。（ 讓權(quán)等待 ） 進程互斥 161。170。161。170。實現(xiàn)方法 ? 軟件方法 ? 硬件方法 ? 信號量方法 ? 管程方法 ? 消息傳遞方法 ? 軟件的方法是指由進程自己，通過執(zhí)行相應(yīng)的程序指令，實現(xiàn)與別的進程的同步與互斥，無需專門的程序設(shè)計語言或者操作系統(tǒng)的支持 ? 實踐證明，該方法很那正確控制進程間的同步與互斥，而且可能會大大地增加系統(tǒng)的額外開銷。 ? 為了解決軟件方法的不足，有人提出了硬件解決方法，通過 屏蔽中斷 或采用 專門的機器指令 控制同步與互斥。 ? 減 少了系統(tǒng)額外開銷 ? 硬件約束條件太強，可能導(dǎo)致進程饑餓與死鎖現(xiàn)象 ? 一直沒能成為通用的解決方法。 有如千軍萬馬過獨木橋。資源只能互斥地使用，而不能同步使用。 ? 利用加鎖實現(xiàn)進程互斥 ? 當(dāng)某個進程進入臨界區(qū)后，為了阻止其他進程進入臨界區(qū)，它將鎖上臨界區(qū)，直到退出臨界區(qū)為止。 ? 并發(fā)進程在申請進入臨界區(qū)時，首先測試該臨界區(qū)是否是上鎖，若是，則該進程要等到臨界區(qū)開鎖之后才能進入臨界區(qū)。 ? 缺點：系統(tǒng)開銷大、不公平。 前情回顧 ? 進程控制塊（ PCB） ? 操作系統(tǒng)內(nèi)核 ? 原語操作 ? 臨界資源與臨界區(qū) ? 進程互斥實現(xiàn)方 法 ? 互斥的加鎖實現(xiàn) 信號量和 P、 V操作 ? 紅綠燈 ? 阻塞，死鎖 ? 紅燈 161。170。161。170。阻塞等待 ? 綠燈 161。170。161。170。進入臨界區(qū) 基本原理 ? 兩個或者多個進程可以通過傳遞信號進行合作，可以迫使進程在某個位置暫時停止執(zhí)行（阻塞等待），直到它收到一個可以 161。176。向前推進 161。177。 的信號（被喚醒） ? 實現(xiàn)信號燈作用的變量稱為 信號量 ，常被定義為 記錄型變量 s，其中一個域為 整型 ，另一個域為 隊列 ，其元素為等待該信號量的阻塞進程。 利用信號量實現(xiàn)進程互斥 ? 信號量：表示資源的物理實體，是一個與隊列有關(guān)的整數(shù)變量， OS系統(tǒng)利用它的狀態(tài)對進程和資源進行管理。 ? 原語 操作： P操作和 V操作 ? wait（ s） ? signal（ s） ? 公用信號量：聯(lián)系著一組并行進程，初始值為 1，每個進程都可以對它進行 P和 V操作，通常它為實現(xiàn)進程的互斥而設(shè)置。（ 互斥信號量 ） ? 私用信號量：聯(lián)系著一組共行進程，初始值為 0或者某個整數(shù)，僅允許擁有它的進程對他進行 P和 V操作，通常用來實現(xiàn)進程的同步。（ 資源信號量 ） Procedure P(S) Begin Lock out interrupts。 關(guān)中斷 S:=S1。 信號量的值減 1 If S0 then begin 如果 S0，說明已經(jīng)沒有此類資源 Status(q):=block。 q的申請得不到滿足，將其阻賽 Insert(Q,q)。 將 q插入到該資源的等待隊列中 end Unlock interrupts。 開中斷 End。 ? P原語 P（ S） 申請一個單位的資源，執(zhí)行一次 P操作，信號量的值就減 1。 Procedure V(S) Begin Lock out interrupts。 關(guān)中斷 S:=S+1。 信號量的值加 1 If S=0 then begin 如果 S=0，說明有等待該資源的進程 Remove(Q,r)。 則將進程 r從等待隊列中移出 Status(r):=ready。 并將其狀態(tài)改為就緒 Insert(RL,r)。 插入到就緒隊列 end。 Unlock interrupts。 開中斷 End。 ? V原語 V（ S） 釋放一個單位的資源， 執(zhí)行一次 V操作，信號量的值就加 1 進程互斥進入臨界區(qū) 信號量的特征 信號量的特征 ? 信號量的值 =信號量的初始值 P操作的次數(shù) +V操作的次數(shù) ? 執(zhí)行 V操作表示釋放一個單位的資源。若 S=0，表示信號量請求隊列中仍有請求該資源而被阻賽的進程，因此應(yīng)將該隊列的第一個進程喚醒，使之狀態(tài)轉(zhuǎn)換為就緒。 ? 操作系統(tǒng)內(nèi)核以系統(tǒng)調(diào)用形式提供 P、 V原語，應(yīng)用程序通過該系統(tǒng)調(diào)用實現(xiàn)進程互斥。 ? 工程實踐證明。利用信號量方法實現(xiàn)進程互斥是高效的，一直被廣泛采用。 利用信號量實現(xiàn)進程互斥 利用信號量實現(xiàn)進程互斥 首先寫出能實現(xiàn)文件共享 的程序：寫進程 首先寫出能實現(xiàn)文件共享的程序：讀進程 一個問題？？ ? 多個讀者并發(fā)問題 ? 假設(shè)三個讀者進程并發(fā) ? 每執(zhí)行一句一個中斷 ? rc1 P(S) ? 多個讀者共享的計數(shù)器 rc ? 互斥使用！ 前情回顧 ? 信號量 161。170。161。170。表示資源的實體，變量 ? 公用信號量、私用信號量 ? 互斥信號量、資源信號量 ? P（ s）、 V（ s） ? 信號量的特征 ? 讀者寫者問題 進程互斥進入臨界區(qū) 不同進程之間的協(xié)作過程 ? 進程同步的規(guī)則： ? 計算進程計算出數(shù)據(jù)后，打印進程才能執(zhí)行 ? 打印進程取走數(shù)據(jù)后，計算進程才能執(zhí)行 單 緩沖區(qū) ? 兩個私有信號量： ? Sc：是否有可供打印的結(jié)果 ? Sp：緩沖區(qū)的計算結(jié)果是否取走 ? 初始值： Sc： =0； Sp： =0 ? 同步和互斥 ? 計算進程：結(jié)果輸入緩沖區(qū) ? 計算進程：喚醒打印進程 ? 計算進程：數(shù)據(jù)未取走，阻塞自己 ? 打印進程：申請數(shù)據(jù) ? 打印進程：打印，喚醒計算進程 Begin semaphore Sc,Sp。 Sc:=0。Sp:=0。 Cobegin CP:begin LA:puter next number。 Add to buffer。 V(Sc)。 P(Sp)。 Goto LA end 生產(chǎn)者和消費者問題 ? 多緩沖區(qū) ? 同步規(guī)則： ? 生產(chǎn)者企圖將一個消息放入一個已經(jīng)滿的緩沖區(qū)時要等消費者取走一個消息 ? 消費者企圖從空的緩沖區(qū)取走消息時，要等生產(chǎn)者放入一個消息之后 ? 互斥：緩沖區(qū) 生產(chǎn)者和消費者問題 ? 多緩沖區(qū) ? 生產(chǎn)者進程：有空輸入，滿時等待 empty ? 消費者 進程：有數(shù)消費，空時等待 full ? full：消息數(shù)量 ? empty：空緩沖區(qū)數(shù)量 ? 初始值： empty： =n； full： =0 ? 對緩沖區(qū)的互斥使用： ? mutex:=1161。170。161。170。互斥信號量 生產(chǎn)者和消費者問題 ? 生產(chǎn)者進程： ? 先看緩沖區(qū)是否有空， P(empty) ? 如果有空，申請互斥使用緩沖區(qū) P(mutex) ? 如果獲得緩沖區(qū)使用權(quán)，將數(shù)據(jù)輸入緩沖區(qū) ? 釋放緩沖區(qū)使用權(quán)， V(mutex) ? 發(fā)送消息，有新的數(shù)據(jù)輸入， V(full) 生產(chǎn)者和消費者問題 ? 消費者進程： ? 先看緩沖區(qū)是否有數(shù)據(jù)， P(full) ? 如果有數(shù)據(jù)，申 請互斥使用緩沖區(qū) P(mutex) ? 如果獲得緩沖區(qū)使用權(quán)，將數(shù)據(jù)消費 ? 釋放緩沖區(qū)使用權(quán)， V(mutex) ? 有新的空間， V(empty) begin semaphore mutex,empty,full。 mutext:=1。empty:=n。full:=0。 Cobegin producer:begin L1:produce next message。 P(empty)。 P(mutext)。 add to buffer。 V(mutex)。 V(full)。 goto L1。 end 利用信號量實現(xiàn)進程同步 ?分析： ?司機和售票員要互通消息：是否啟 動車輛？能否開車門？分別用 S1， S2表示。假設(shè)初始狀態(tài)車停在始發(fā)站，車門關(guān)著，則 S1=0,S2=1,售票員工作流程的起點是開車門。 進程通信 ? 進程通信 161。170。161。170?；コ馀c同步 ? 信號通信和信件通信 ? 低級通信原語：開鎖、關(guān)鎖、 P、 V操作原語 ? 高級通信原語：較高的傳輸效率傳輸大批量的信息 ? 消息緩沖和信箱 實例 ? 幼兒園小朋友喂飯 ? 喂飯方法設(shè)計的目標(biāo)？原則？ ? 調(diào)度 161。170。161。170。在一個隊列中，按照某種方法或者算法，選擇一個適合的個體的過程。 ? 關(guān)鍵 161。170。161。170。算法 ? 如何設(shè)計一個好的算法？ 調(diào)度目標(biāo) ? 公平性 ? 處理機利用率 ? 提高系統(tǒng)吞吐量 ? 盡量減少響應(yīng)時間 為什么引進進程調(diào)度？ ? 在分時系統(tǒng)中，分配給該進程運行的時間片已經(jīng)用完 ? 在執(zhí)行完系統(tǒng)調(diào)用，當(dāng)系統(tǒng)程序返回用戶進程時，可認(rèn)為系統(tǒng)進程執(zhí)行完畢，從而可以調(diào)度選擇一個新的用戶進程執(zhí)行 ? 在可剝奪方式下，就緒隊列中的某進程的優(yōu)先級變得高于當(dāng)前執(zhí)行進程的優(yōu)先級時會引起進程調(diào)度 進程調(diào)度的方式 ? 長程調(diào)度 161。170。161。170。作業(yè)調(diào)度 ? 短程調(diào)度 161。170。161。170。進程調(diào)度 進程調(diào)度算法 ? 先來先服務(wù)（ FCFS） ? 按照作業(yè)來到的 先后順序排隊，每次調(diào)度隊首的作業(yè)（進程）。 ? 非搶占（剝奪），實現(xiàn)簡單，看似公平 ? 對于后進入隊列，運行時間較短的作業(yè)或 I/O型的作業(yè)要長時間等待。 ? 先來先服務(wù)（ FCFS） ? 對短作業(yè)不公平。如果長作業(yè)排在隊首，那么后邊的短作業(yè)就會等待很長時間，增加了平均周轉(zhuǎn)時間。 ? 不利于 I/O型作業(yè) ? 混合使用，例如加入優(yōu)先級 進程調(diào)度算法 ? 短作業(yè)（進程）優(yōu)先 ? 通過計算判斷就緒隊列中哪個作業(yè)的預(yù)期執(zhí)行時間最短，就調(diào)度誰。 ? 非搶占（剝奪） ? 短作業(yè)（進程）優(yōu)先 ? 與 FCFS算法相比，改善的系統(tǒng)性能，降低了平均等待時間， 提高了系統(tǒng)的吞吐量。 ? 也可能讓長作業(yè)長時間等待 ? 如何預(yù)測執(zhí)行時間？ ? 最高優(yōu)先級優(yōu)先（ HPF）調(diào)度算法 ? 優(yōu)先級調(diào)度算法（ priorityscheduling algorithm）是指每個進程都有一個優(yōu)先級與其相關(guān)聯(lián)，具有最高優(yōu)先級的就緒進程會被分派到 CPU。具有相同優(yōu)先級的進程按 FCFS順序調(diào)度。 ? 作業(yè)調(diào)度、進程調(diào)度 ? 搶占式和非搶占式 優(yōu)先級的確定 161。170。161。170?？紤]因素 ? 進程的類型（性質(zhì)） ? 系統(tǒng)進程、用戶進程 ? I/O繁忙〉 CPU繁忙：充分利用資源 ? 交互性〉批量性：響應(yīng)時間 ? 進程要求的資源 ? 短作業(yè)優(yōu)先 ? 外部優(yōu)先級 和作業(yè)到達(dá)時間 ? 進程完成功能的重要性和急迫性 優(yōu)先級的確定 161。170。161。170。方法 ? 靜態(tài)優(yōu)先級 ? 進程創(chuàng)建初給他一個優(yōu)先級，不再改變。 ? 調(diào)度方法簡單，但是隨著進程的推進，原來確定優(yōu)先級的特性可能在改變。 ? 那么為了改善調(diào)度性能 161。170。161。170。動態(tài)優(yōu)先級 動態(tài)優(yōu)先級 ? 典型的動態(tài)優(yōu)先級變化方式為： ? 優(yōu)先級隨著進程運行的剩余時間的減少而上升，使將要執(zhí)行結(jié)束的進程盡快完成； ? 或者隨著進程排隊等待時間的增長而上升，使等待時間越長的進程優(yōu)先得到調(diào)度，不至于長時間饑餓。 ? 具體實現(xiàn)方法，在每個時鐘中斷時，或者需要進程切換時，重新計算隊列中各進程 的優(yōu)先級，并優(yōu)先調(diào)度優(yōu)先級高的進程。 ? 剩余時間最短者優(yōu)先，響應(yīng)比高者優(yōu)先 進程調(diào)度算法 ? 響應(yīng)比高者優(yōu)先 ? 作業(yè)（進程）的響應(yīng)時間 =作業(yè)（進程）等待時間 +運行時間 ? 作業(yè)（進程）的響應(yīng)比 =作業(yè)的響應(yīng)時間 /運行時間 ? 既考慮了等待時間，又考慮了運行時間 ? 非搶占（剝奪） ? 作業(yè)雖然長，但是隨著等待時間的增加，其響應(yīng)比增加 ? 運行時間越短，響應(yīng)比越高 ? 很難預(yù)估作業(yè)的運行時間 ? 增加了系統(tǒng)開銷 前情回顧 ? 進程同步 ? 進程調(diào)度 ? 調(diào)度目標(biāo) ? 調(diào)度的原因 ? 調(diào)度的方式：搶占式和非搶占式 ? 調(diào)度算法： FCFS、短進程優(yōu)先、最高 優(yōu)先級優(yōu)先（動態(tài)優(yōu)先級，響應(yīng)比高者優(yōu)先） 輪轉(zhuǎn)法 ? 實例： ? 在一個分時聯(lián)機系統(tǒng)中，同時有 n