【文章內(nèi)容簡介】 Status(r):=ready。 并將其狀態(tài)改為就緒 Insert(RL,r)。 插入到就緒隊(duì)列 end。 Unlock interrupts。 開中斷End。162。 V原語V（S）釋放一個單位的資源，執(zhí)行一次V操作，信號量的值就加1進(jìn)程互斥進(jìn)入臨界區(qū)信號量的特征信號量的特征162。 信號量的值=信號量的初始值P操作的次數(shù)+V操作的次數(shù)162。 執(zhí)行V操作表示釋放一個單位的資源。若S=0，表示信號量請求隊(duì)列中仍有請求該資源而被阻賽的進(jìn)程，因此應(yīng)將該隊(duì)列的第一個進(jìn)程喚醒，使之狀態(tài)轉(zhuǎn)換為就緒。162。 操作系統(tǒng)內(nèi)核以系統(tǒng)調(diào)用形式提供P、V原語，應(yīng)用程序通過該系統(tǒng)調(diào)用實(shí)現(xiàn)進(jìn)程互斥。162。 工程實(shí)踐證明。利用信號量方法實(shí)現(xiàn)進(jìn)程互斥是高效的，一直被廣泛采用。利用信號量實(shí)現(xiàn)進(jìn)程互斥利用信號量實(shí)現(xiàn)進(jìn)程互斥首先寫出能實(shí)現(xiàn)文件共享的程序：寫進(jìn)程首先寫出能實(shí)現(xiàn)文件共享的程序：讀進(jìn)程一個問題？？162。 多個讀者并發(fā)問題162。 假設(shè)三個讀者進(jìn)程并發(fā)162。 每執(zhí)行一句一個中斷162。 rc1 P(S) 162。 多個讀者共享的計(jì)數(shù)器rc162。 互斥使用！前情回顧162。 信號量161。170。161。170。表示資源的實(shí)體，變量? 公用信號量、私用信號量? 互斥信號量、資源信號量162。 P（s）、V（s）162。 信號量的特征162。 讀者寫者問題進(jìn)程互斥進(jìn)入臨界區(qū)162。 進(jìn)程同步的規(guī)則：162。 計(jì)算進(jìn)程計(jì)算出數(shù)據(jù)后，打印進(jìn)程才能執(zhí)行162。 打印進(jìn)程取走數(shù)據(jù)后，計(jì)算進(jìn)程才能執(zhí)行單緩沖區(qū)162。 兩個私有信號量：? Sc：是否有可供打印的結(jié)果? Sp：緩沖區(qū)的計(jì)算結(jié)果是否取走162。 初始值： Sc：=0； Sp：=0162。 同步和互斥162。 計(jì)算進(jìn)程：結(jié)果輸入緩沖區(qū)162。 計(jì)算進(jìn)程：喚醒打印進(jìn)程162。 計(jì)算進(jìn)程：數(shù)據(jù)未取走，阻塞自己162。 打印進(jìn)程：申請數(shù)據(jù)162。 打印進(jìn)程：打印，喚醒計(jì)算進(jìn)程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)者和消費(fèi)者問題162。 多緩沖區(qū)162。 同步規(guī)則：162。 生產(chǎn)者企圖將一個消息放入一個已經(jīng)滿的緩沖區(qū)時要等消費(fèi)者取走一個消息162。 消費(fèi)者企圖從空的緩沖區(qū)取走消息時，要等生產(chǎn)者放入一個消息之后162。 互斥：緩沖區(qū)生產(chǎn)者和消費(fèi)者問題162。 多緩沖區(qū)? 生產(chǎn)者進(jìn)程：有空輸入，滿時等待 empty? 消費(fèi)者進(jìn)程：有數(shù)消費(fèi)，空時等待full162。 full：消息數(shù)量162。 empty：空緩沖區(qū)數(shù)量162。 初始值：empty：=n；full：=0162。 對緩沖區(qū)的互斥使用：? mutex:=1161。170。161。170?；コ庑盘柫可a(chǎn)者和消費(fèi)者問題162。 生產(chǎn)者進(jìn)程：162。 先看緩沖區(qū)是否有空，P(empty)162。 如果有空，申請互斥使用緩沖區(qū)P(mutex)162。 如果獲得緩沖區(qū)使用權(quán)，將數(shù)據(jù)輸入緩沖區(qū)162。 釋放緩沖區(qū)使用權(quán)，V(mutex)162。 發(fā)送消息，有新的數(shù)據(jù)輸入，V(full)生產(chǎn)者和消費(fèi)者問題162。 消費(fèi)者進(jìn)程：162。 先看緩沖區(qū)是否有數(shù)據(jù)，P(full)162。 如果有數(shù)據(jù)，申請互斥使用緩沖區(qū)P(mutex)162。 如果獲得緩沖區(qū)使用權(quán)，將數(shù)據(jù)消費(fèi)162。 釋放緩沖區(qū)使用權(quán)，V(mutex)162。 有新的空間，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利用信號量實(shí)現(xiàn)進(jìn)程同步162。 分析：216。 司機(jī)和售票員要互通消息：是否啟動車輛？能否開車門？分別用S1，S2表示。假設(shè)初始狀態(tài)車停在始發(fā)站，車門關(guān)著，則S1=0,S2=1,售票員工作流程的起點(diǎn)是開車門。 進(jìn)程通信162。 進(jìn)程通信161。170。161。170?；コ馀c同步162。 信號通信和信件通信162。 低級通信原語：開鎖、關(guān)鎖、P、V操作原語162。 高級通信原語：較高的傳輸效率傳輸大批量的信息? 消息緩沖和信箱實(shí)例162。 幼兒園小朋友喂飯162。 喂飯方法設(shè)計(jì)的目標(biāo)？原則？162。 調(diào)度161。170。161。170。在一個隊(duì)列中，按照某種方法或者算法，選擇一個適合的個體的過程。162。 關(guān)鍵161。170。161。170。算法162。 如何設(shè)計(jì)一個好的算法？調(diào)度目標(biāo)162。 公平性162。 處理機(jī)利用率162。 提高系統(tǒng)吞吐量162。 盡量減少響應(yīng)時間為什么引進(jìn)進(jìn)程調(diào)度？216。 在分時系統(tǒng)中，分配給該進(jìn)程運(yùn)行的時間片已經(jīng)用完216。 在執(zhí)行完系統(tǒng)調(diào)用，當(dāng)系統(tǒng)程序返回用戶進(jìn)程時，可認(rèn)為系統(tǒng)進(jìn)程執(zhí)行完畢，從而可以調(diào)度選擇一個新的用戶進(jìn)程執(zhí)行216。 在可剝奪方式下，就緒隊(duì)列中的某進(jìn)程的優(yōu)先級變得高于當(dāng)前執(zhí)行進(jìn)程的優(yōu)先級時會引起進(jìn)程調(diào)度進(jìn)程調(diào)度的方式162。 長程調(diào)度161。170。161。170。作業(yè)調(diào)度162。 短程調(diào)度161。170。161。170。進(jìn)程調(diào)度 進(jìn)程調(diào)度算法162。 先來先服務(wù)（FCFS）? 按照作業(yè)來到的先后順序排隊(duì)，每次調(diào)度隊(duì)首的作業(yè)（進(jìn)程）。? 非搶占（剝奪），實(shí)現(xiàn)簡單，看似公平? 對于后進(jìn)入隊(duì)列，運(yùn)行時間較短的作業(yè)或I/O型的作業(yè)要長時間等待。162。 先來先服務(wù)（FCFS）? 對短作業(yè)不公平。如果長作業(yè)排在隊(duì)首，那么后邊的短作業(yè)就會等待很長時間，增加了平均周轉(zhuǎn)時間。? 不利于I/O型作業(yè)? 混合使用，例如加入優(yōu)先級 進(jìn)程調(diào)度算法162。 短作業(yè)（進(jìn)程）優(yōu)先? 通過計(jì)算判斷就緒隊(duì)列中哪個作業(yè)的預(yù)期執(zhí)行時間最短，就調(diào)度誰。? 非搶占（剝奪）162。 短作業(yè)（進(jìn)程）優(yōu)先? 與FCFS算法相比，改善的系統(tǒng)性能，降低了平均等待時間，提高了系統(tǒng)的吞吐量。? 也可能讓長作業(yè)長時間等待? 如何預(yù)測執(zhí)行時間？162。 最高優(yōu)先級優(yōu)先（HPF）調(diào)度算法216。 優(yōu)先級調(diào)度算法（priorityscheduling algorithm）是指每個進(jìn)程都有一個優(yōu)先級與其相關(guān)聯(lián)，具有最高優(yōu)先級的就緒進(jìn)程會被分派到CPU。具有相同優(yōu)先級的進(jìn)程按FCFS順序調(diào)度。162。 作業(yè)調(diào)度、進(jìn)程調(diào)度162。 搶占式和非搶占式優(yōu)先級的確定161。170。161。170?？紤]因素162。 進(jìn)程的類型（性質(zhì)）? 系統(tǒng)進(jìn)程、用戶進(jìn)程? I/O繁忙〉CPU繁忙：充分利用資源? 交互性〉批量性：響應(yīng)時間162。 進(jìn)程要求的資源? 短作業(yè)優(yōu)先162。 外部優(yōu)先級和作業(yè)到達(dá)時間162。 進(jìn)程完成功能的重要性和急迫性優(yōu)先級的確定161。170。161。170。方法162。 靜態(tài)優(yōu)先級162。 進(jìn)程創(chuàng)建初給他一個優(yōu)先級，不再改變。162。 調(diào)度方法簡單，但是隨著進(jìn)程的推進(jìn)，原來確定優(yōu)先級的特性可能在改變。162。 那么為了改善調(diào)度性能161。170。161。170。動態(tài)優(yōu)先級動態(tài)優(yōu)先級162。 典型的動態(tài)優(yōu)先級變化方式為：? 優(yōu)先級隨著進(jìn)程運(yùn)行的剩余時間的減少而上升，使將要執(zhí)行結(jié)束的進(jìn)程盡快完成；? 或者隨著進(jìn)程排隊(duì)等待時間的增長而上升，使等待時間越長的進(jìn)程優(yōu)先得到調(diào)度，不至于長時間饑餓。162。 具體實(shí)現(xiàn)方法，在每個時鐘中斷時，或者需要進(jìn)程切換時，重新計(jì)算隊(duì)列中各進(jìn)程的優(yōu)先級，并優(yōu)先調(diào)度優(yōu)先級高的進(jìn)程。162。 剩余時間最短者優(yōu)先，響應(yīng)比高者優(yōu)先 進(jìn)程調(diào)度算法162。 響應(yīng)比高者優(yōu)先? 作業(yè)（進(jìn)程）的響應(yīng)時間=作業(yè)（進(jìn)程）等待時間+運(yùn)行時間? 作業(yè)（進(jìn)程）的響應(yīng)比=作業(yè)的響應(yīng)時間/運(yùn)行時間? 既考慮了等待時間，又考慮了運(yùn)行時間? 非搶占（剝奪）? 作業(yè)雖然長，但是隨著等待時間的增加，其響應(yīng)比增加? 運(yùn)行時間越短，響應(yīng)比越高? 很難預(yù)估作業(yè)的運(yùn)行時間? 增加了系統(tǒng)開銷前情回顧162。 進(jìn)程同步162。 進(jìn)程調(diào)度? 調(diào)度目標(biāo)? 調(diào)度的原因? 調(diào)度的方式：搶占式和非搶占式? 調(diào)度算法：FCFS、短進(jìn)程優(yōu)先、最高優(yōu)先級優(yōu)先（動態(tài)優(yōu)先級，響應(yīng)比高者優(yōu)先）輪轉(zhuǎn)法162。 實(shí)例：162。 在一個分時聯(lián)機(jī)系統(tǒng)中，同時有n個人通過各自的終端共享一臺主機(jī)（服務(wù)器）。終端完成輸入/輸出操作，主機(jī)負(fù)責(zé)處理從終端發(fā)來的請求，為之建立進(jìn)程并協(xié)調(diào)各進(jìn)程的運(yùn)行、調(diào)度各個進(jìn)程等，并盡量滿足每個終端用戶對響應(yīng)時間的要求。162。 在分時系統(tǒng)中，n個進(jìn)程循環(huán)地獲得時間片而執(zhí)行。從系統(tǒng)中來看他們是交替執(zhí)行的，但每個終端用戶而言，都感覺是在獨(dú)占主機(jī)，不受其他用戶的影響，這是通過進(jìn)程并發(fā)執(zhí)行實(shí)現(xiàn)的。162。 如果用戶數(shù)太多，進(jìn)程急劇增加，進(jìn)程的響應(yīng)時間也可能增長，用戶將明顯感覺到主機(jī)的速度慢而不滿意。162。 時間片的大小也會影響到進(jìn)程的響應(yīng)時間。簡單輪轉(zhuǎn)法162。 調(diào)度程序每次把CPU分配給就緒隊(duì)列首進(jìn)程使用一個時間片，例如100ms，就緒隊(duì)列中的每個進(jìn)程輪流地運(yùn)行一個時間片。當(dāng)這個時間片結(jié)束時，強(qiáng)迫一個進(jìn)程讓出處理器，讓它排列到就緒隊(duì)列的尾部，等候下一輪調(diào)度。162。 搶占式（剝奪式）162。 循環(huán)得為每個進(jìn)程分配時間片，對每個進(jìn)程都是公平的。162。 對于短進(jìn)程和大量I/O操作的進(jìn)程不利162。 交互161。170。161。170。對于時間要求緊迫的進(jìn)程不能及時處理162。 時間片161。170。161。170?？勺?62。 優(yōu)先級161。170。161。170。多隊(duì)列可變時間片輪轉(zhuǎn)法162。 時間片設(shè)置162。 響應(yīng)時間162。 就緒隊(duì)列中進(jìn)程數(shù)目（最大用戶數(shù)）162。 進(jìn)程轉(zhuǎn)換時間162。 系統(tǒng)效率等可變時間片輪轉(zhuǎn)法162。 時間片162。 進(jìn)程數(shù)162。 響應(yīng)時間多隊(duì)列輪轉(zhuǎn)法162。 建立多個就緒隊(duì)列162。 每個隊(duì)列有不同的優(yōu)先級162。 每個隊(duì)列又分別采用時間片輪轉(zhuǎn)法調(diào)度調(diào)度算法小結(jié)162。 先來先服務(wù)162。 短進(jìn)程（作業(yè)）優(yōu)先162。 最高優(yōu)先級優(yōu)先? 剩余時間最短者優(yōu)先? 響應(yīng)比高者優(yōu)先162。 輪轉(zhuǎn)調(diào)度法? 簡單輪轉(zhuǎn)法? 可變時間片輪轉(zhuǎn)法? 多隊(duì)列輪轉(zhuǎn)法162。 如何選擇進(jìn)程調(diào)度算法跟系統(tǒng)設(shè)計(jì)的目標(biāo)有關(guān)162。 交互式多任務(wù)系統(tǒng)，主要考慮聯(lián)機(jī)用戶對響應(yīng)時間的要求，一般采用基于時間片輪轉(zhuǎn)調(diào)度算法，同時根據(jù)進(jìn)程性質(zhì)設(shè)置不同的優(yōu)先級162。 批處理系統(tǒng)往往以作業(yè)的平均周轉(zhuǎn)時間來衡量調(diào)度性能，常選用基于優(yōu)先級的短進(jìn)程（作業(yè)）優(yōu)先調(diào)度算法。 死鎖銀行家算法假設(shè)某銀行擬將一定數(shù)量的資金供給一定數(shù)量的顧客共享使用。規(guī)定：p 每個顧客必須預(yù)先 申請對資金的最大需求量，但不得超過銀行共享資金的總和；p 每個顧客的借款方式是以161。176。一個資金單位161。177。為單位p 銀行對顧客提出的每次交易，將根據(jù)當(dāng)時的資金數(shù)量，依照一定的原則，或立即成交或推遲成交，但必須保證客戶等待的時間是有限的，每個顧客的借款總額不得超過其最大申請量p 當(dāng)且僅當(dāng)每個顧客的借款總額達(dá)到最大申請量后，才能且必須在有限時間內(nèi)歸還其全部借款假設(shè)銀行有10個資金單位，有甲、乙、丙三個顧客與銀行進(jìn)行交易，三個顧客的最大申請額分別為9個資金單位。死鎖162。 并發(fā)控制中出現(xiàn)的問題162。 多個進(jìn)程競爭系統(tǒng)資源162。 進(jìn)程的并發(fā)控制不僅要控制若干進(jìn)程的同步與互斥，確保進(jìn)程之間的正常通信，還需要解決進(jìn)程死鎖的問題。162。 一旦出現(xiàn)進(jìn)程死鎖，相應(yīng)的進(jìn)程將無法向前推進(jìn)。如果系統(tǒng)內(nèi)的絕大多數(shù)進(jìn)程或全部進(jìn)程死鎖，那么，整個系統(tǒng)將處于癱瘓狀態(tài)，造成系統(tǒng)的161。176。死機(jī)161。177。162。 交通中的死鎖現(xiàn)象162。 進(jìn)程競爭引起死鎖162。 改進(jìn)（推進(jìn)順序）死鎖定義216。 當(dāng)某進(jìn)程提出資源申請后，使得若干進(jìn)程在無外力作用下，永遠(yuǎn)不能再繼續(xù)前進(jìn)，稱這種情況為系統(tǒng)發(fā)生了死鎖或僵局。216。 競爭資源216。 推進(jìn)順序不當(dāng)216。 相互通信而永久阻塞216。 Eg：兩個進(jìn)程都在等待著對方占有的而不不能為自己使用的資源，這時就發(fā)生了死鎖。162。 若系統(tǒng)出現(xiàn)死鎖，必須有相應(yīng)的措施進(jìn)行解除。162。 當(dāng)然，如果能提前預(yù)防和避免死鎖的出現(xiàn)，將能夠提高系統(tǒng)的運(yùn)行效率。引起死鎖的原因162。 主要原因，競爭資源。而進(jìn)程對資源的總需求量超過系統(tǒng)能提供的最大資源量。162。 永久性資源（可重用資源）162。 消耗型資源162。 永久性資源，某一時刻僅允許一個進(jìn)程使用、不能被進(jìn)程消耗的、釋放以后還可以被其他進(jìn)程使用的資源。162。 處理機(jī)、I/O通道和設(shè)備、存儲器、文件、數(shù)據(jù)庫、信號量之類的162。 競爭永久性資源可能引起死鎖162。 消耗性資源，可以創(chuàng)造（生產(chǎn)）和撤銷（消耗）的資源，其數(shù)量不限。162。 中斷、信號、消息、Buffer中的數(shù)據(jù)162。 進(jìn)程競爭消耗性資源也可能產(chǎn)生死鎖。162。 程序設(shè)計(jì)引起162。 死鎖：預(yù)防或者解除162。 什么情況造成出現(xiàn)死鎖162。 死鎖產(chǎn)生的條件產(chǎn)生死鎖的條件162。 互斥：競爭的資源一次只能被一個進(jìn)程使用162。 請求和保持：當(dāng)一個進(jìn)程占有一些資源，同時又申請新的資源。如果新資源申請失敗，進(jìn)程將占有資源且阻塞等待。162。 非剝奪：進(jìn)程已經(jīng)占有的資源不能被其他進(jìn)程強(qiáng)行剝奪。162。 循環(huán)等待：在系統(tǒng)中存在一個由若干進(jìn)程形成的循環(huán)請求鏈，其中的每一個進(jìn)程均占有一些資源，同時又申請環(huán)形請求鏈中下一個進(jìn)程所占有的資源。162。 四個條件必要條件162。 第四個條件實(shí)際上是前三個條件的可能導(dǎo)致的結(jié)果，即只有存在互斥、請求和保持、非剝奪條件，就可能出現(xiàn)循環(huán)等待。162。 只要系統(tǒng)出現(xiàn)循環(huán)等待，一定出現(xiàn)死鎖。解決死鎖的方法162。 按照解決死鎖的時機(jī)：162。 預(yù)防死鎖162。 死鎖檢測（避免死鎖）16