【文章內(nèi)容簡介】 P（S1，S2，……Sn）SV（S1，S2，……Sn）216。 一般“信號量集”機(jī)制P（Si，ti，di） ti表示資源下限 di表示資源需求或分配數(shù)目條件：Si≥ti 分配：Si:= Si –diJ p(s,d,d) 一般信號量J p(s,1,1) (s1)一般的記錄型信號量 (s=1) 互斥信號量J p(s,1,0) 可控開關(guān)3. 經(jīng)典進(jìn)程的同步問題178。 生產(chǎn)者——消費者問題：相互合作進(jìn)程關(guān)系的抽象 公用緩沖池0 1 2 …… n1empty=n 空緩沖的數(shù)量 mutex=1 互斥信號量full=0 滿緩沖的數(shù)量生產(chǎn)者 消費者 生產(chǎn)一產(chǎn)品 p(full) 是否有產(chǎn)品可消費 p(empty) 是否有空緩沖存放產(chǎn)品 p(mutex) p(mutex) 對緩沖區(qū) 從緩沖中取產(chǎn)品 的互斥訪問產(chǎn)品放人緩沖區(qū) v(mutex)v(mutex) v(empty)v(full) 消費產(chǎn)品216。 每個程序中實現(xiàn)互斥的p(mutex)和v(mutex)必須成對出現(xiàn)。216。 對生產(chǎn)者和消費者的pv操作同樣需要成對出現(xiàn)，但它們是分別處于不同的程序中。216。 在每個程序中多個p操作順序不能顛倒。178。 讀者——寫者問題一個數(shù)據(jù)對象(數(shù)據(jù)文件或記錄)，可被多個進(jìn)程共享。允許多個reader 進(jìn)程同時讀一個共享對象，但絕不允許一個writer進(jìn)程和其它reader進(jìn)程或writer進(jìn)程同時訪問共享對象。216。 利用記錄型信號量解決讀者——寫者問題readcount=0： 讀者數(shù)目，臨界資源rmutex=1： 對readcount互斥訪問的互斥信號量wmutex=1： 寫互斥信號量流程見下圖。216。 利用信號量集機(jī)制解決讀者——寫者問題讀者： 寫者： repeat repeat sp(L,1,1) L 為讀者數(shù)(RN) sp(mx,1,1。L,RN,0) sp(mx,1,0) mx為控制開關(guān) 寫操作 ……讀操作…… sv(mx,1) sv(L,1) until false until false讀者： 寫者：p(rmutex) p(wmutex)readcount=0? Y 第一個讀者 np(wmutex) 寫操作readcount:=readcount+1v(rmutex) v(wmutex) 讀操作p(rmutex)readcount:=readcount1readcount=0? Y 最后一個讀者讀完 n v(wmutex) v(rmutex)178。 哲學(xué)家進(jìn)餐問題五. 進(jìn)程通信進(jìn)程通信是指進(jìn)程間的信息交換。進(jìn)程的同步是低級通信，效率低，對用戶不透明。高級通信是指用戶直接利用操作系統(tǒng)所提供的一組通信命令(隱藏了進(jìn)程通信的實現(xiàn)細(xì)節(jié))，高效地傳送大量數(shù)據(jù)的一種通信方式。1. 共享存儲器系統(tǒng)相互通信的進(jìn)程共享某些數(shù)據(jù)結(jié)構(gòu)或共享存儲區(qū)。178。 基于共享數(shù)據(jù)結(jié)構(gòu)的通信方式（低級）178。 基于共享存儲區(qū)的通信方式2. 消息傳遞系統(tǒng)進(jìn)程間的數(shù)據(jù)交換以消息為單位。程序員直接利用系統(tǒng)提供的一組通信命令（原語）來實現(xiàn)通信。178。 直接通信方式發(fā)送進(jìn)程利用OS所提供的發(fā)送命令，直接把消息發(fā)送給目標(biāo)進(jìn)程。要求發(fā)送進(jìn)程和接收進(jìn)程都以顯式的方式提供對方的標(biāo)識符。Send(receiver , message)Receive(sender , message)178。 間接通信方式通過中間實體（信箱）進(jìn)行通信，廣泛用于計算機(jī)網(wǎng)絡(luò)中。消息在信箱中可以安全保存，只允許核準(zhǔn)的用戶隨時讀取。系統(tǒng)為信箱提供了創(chuàng)建、撤消、消息發(fā)送、接收等原語。信箱的種類：私用信箱——用戶進(jìn)程自己創(chuàng)建，作為該進(jìn)程的一部分，采用單向鏈路，其他用戶發(fā)送消息，主人讀取消息。公用信箱——操作系統(tǒng)創(chuàng)建，在系統(tǒng)運行期始終存在，采用雙向通信鏈路，核準(zhǔn)用戶可發(fā)送和取出消息。共享信箱——某進(jìn)程創(chuàng)建，指明共享進(jìn)程的名字。主人和共享者都有權(quán)取走自己的消息。信箱通信，發(fā)送和接收進(jìn)程之間存在1:n:1:n（廣播）、m:n（公用信箱）的關(guān)系。3. 管道通信——共享文件的通信方式管道是指用于連接一個讀進(jìn)程和一個寫進(jìn)程，以實現(xiàn)它們之間通信的共享文件，又稱pipe文件。UNIX系統(tǒng)采用。寫進(jìn)程以字符流的形式將大量數(shù)據(jù)送入管道，讀進(jìn)程接收數(shù)據(jù)。 讀進(jìn)程 寫進(jìn)程 管道通信機(jī)制必須提供互斥、同步和確定對方的三種協(xié)調(diào)能力。六. 進(jìn)程調(diào)度1. 調(diào)度隊列模型 作業(yè)調(diào)度 時間片完CPU 后備隊列 就緒隊列 進(jìn)程調(diào)度 進(jìn)程完成批量 作業(yè) 中級調(diào)度 就緒掛起隊列 交互型作業(yè) 事件出現(xiàn) 阻塞掛起隊列 事件 出現(xiàn) 掛起 阻塞隊列 等待事件2. 調(diào)度類型178。 高級調(diào)度——作業(yè)調(diào)度批處理系統(tǒng)中使用，周期較長。178。 低級調(diào)度——進(jìn)程調(diào)度是最基本的一種調(diào)度，在三種類型的OS中都必須配置。進(jìn)程調(diào)度可采用非搶占或搶占兩種方式。其中搶占方式允許調(diào)度程序根據(jù)某種原則，例時間片原則、優(yōu)先權(quán)原則、短進(jìn)程優(yōu)先原則等去停止某個正在執(zhí)行的進(jìn)程，將已分配給該進(jìn)程的處理機(jī)，重新分配給另一進(jìn)程。進(jìn)程調(diào)度的運行頻率最高，故算法不能太復(fù)雜。178。 中級調(diào)度引入中級調(diào)度的目的是為了提高內(nèi)存的利用率和系統(tǒng)吞吐量。中級調(diào)度實際上是存儲器管理中的對換功能。3. 選擇調(diào)度方式和算法的準(zhǔn)則周轉(zhuǎn)時間（批處理）面向用戶 響應(yīng)時間（分時）的準(zhǔn)則 截止時間的保證（實時） 優(yōu)先權(quán)準(zhǔn)則面向系統(tǒng) 系統(tǒng)吞吐量高（批處理）的準(zhǔn)則 處理機(jī)利用率好 各類資源的平衡利用178。 周轉(zhuǎn)時間——指作業(yè)提交系統(tǒng)開始，到作業(yè)完成為止的時間間隔。178。 帶權(quán)周轉(zhuǎn)時間——作業(yè)的周轉(zhuǎn)時間與系統(tǒng)為它提供的實際服務(wù)時間之比。W=T/TS178。 響應(yīng)時間——從用戶通過鍵盤提交一個請求開始，直至系統(tǒng)首次產(chǎn)生響應(yīng)為止的時間。178。 截止時間——某任務(wù)必須開始執(zhí)行的最遲時間，或必須完成的最遲時間。178。 吞吐量——單位時間內(nèi)所完成的作業(yè)數(shù)。4. 調(diào)度算法（作業(yè)調(diào)度、進(jìn)程調(diào)度）178。 先來先服務(wù)調(diào)度算法（FCFS）216。 按進(jìn)入后備（或就緒）隊列的先后選擇目標(biāo)作業(yè)（或進(jìn)程）。216。 有利于長作業(yè)（進(jìn)程），不利于短作業(yè)（進(jìn)程）。178。 最短作業(yè)優(yōu)先調(diào)度算法SJ（P）F216。 從后備（或就緒）隊列中選擇估計運行時間最短的作業(yè)（或進(jìn)程） tn+1=a tn+(1a) tn tn為實際值， tn為預(yù)測值216。 SJF有效地降低作業(yè)的平均等待時間，提高了系統(tǒng)的吞吐量。216。 對長作業(yè)（或進(jìn)程）不利，可能死等，且未考慮作業(yè)的緊迫程度。178。 時間片輪轉(zhuǎn)調(diào)度算法（進(jìn)程調(diào)度）216。 系統(tǒng)將所有的就緒進(jìn)程按先來先服務(wù)原則，排成一個隊列，每次調(diào)度時把CPU分配給隊首進(jìn)程，令其執(zhí)行一個時間片。216。 就緒隊列中所有進(jìn)程，在一個給定的時間內(nèi)，均能獲得一個時間片的處理機(jī)執(zhí)行時間。T=nq178。 優(yōu)先權(quán)調(diào)度算法216。 適用于作業(yè)調(diào)度和進(jìn)程調(diào)度。216。 非搶占式、搶占式優(yōu)先權(quán)調(diào)度算法216。 優(yōu)先權(quán)類型：靜態(tài)優(yōu)先權(quán)、動態(tài)優(yōu)先權(quán)178。 高響應(yīng)比優(yōu)先調(diào)度算法（作業(yè)調(diào)度） 響應(yīng)比RP= 響應(yīng)時間/要求服務(wù)時間=（等待時間+要求服務(wù)時間）/要求服務(wù)時間 = 1+等待時間/要求服務(wù)時間216。 同時到達(dá)的作業(yè)（等待時間相同），要求服務(wù)時間越短（短作業(yè)），響應(yīng)比越高，有利于短作業(yè)。216。 要求服務(wù)時間相同的作業(yè)，等待時間越長，響應(yīng)比越高，相當(dāng)于先來先服務(wù)。216。 長作業(yè)在等待足夠長時間后，響應(yīng)比上升，也可被調(diào)度，避免長作業(yè)的死等。216。 每次調(diào)度需計算響應(yīng)比，增加系統(tǒng)的開銷。178。 多級隊列調(diào)度216。 根據(jù)作業(yè)的性質(zhì)或類型的不同，將就緒進(jìn)程隊列分成若干個子隊列，各個作業(yè)固定分屬于一個隊列。每個隊列采用各自的調(diào)度算法。178。 多級反饋隊列調(diào)度算法216。 UNIX系統(tǒng)中的進(jìn)程調(diào)度算法。216。 處理方法：J 設(shè)置多個就緒隊列，每個隊列賦予不同的優(yōu)先權(quán)(S1S2……Sn )，且各隊列中進(jìn)程執(zhí)行的時間片的大小各不相同(q，2q……nq)。J 新進(jìn)程進(jìn)入內(nèi)存，首先放在S1的末尾，按FCFS排隊調(diào)度，執(zhí)行q時間片，若未完成，該進(jìn)程轉(zhuǎn)入S2，依次類推。J 僅當(dāng)Si空閑，才會調(diào)度Si+1中進(jìn)程。216。 能較好地滿足各種類型用戶的需要。七. 死鎖1. 死鎖的概念死鎖是指多個進(jìn)程因競爭資源而造成的一種僵局，若無外力作用，這些進(jìn)程都將永遠(yuǎn)不能向前推進(jìn)。2. 死鎖產(chǎn)生的原因（1） 競爭資源——競爭非剝奪資源、競爭臨時性資源（2） 進(jìn)程推進(jìn)順序不當(dāng)3. 產(chǎn)生死鎖的必要條件（同時具備）（1） 互斥條件——進(jìn)程對所分配到的資源進(jìn)行排它性使用。（2） 請求和保持條件——請求新資源阻塞，保持其它已獲得資源不放。（3） 不剝奪條件——進(jìn)程獲得的資源在使用完之前不能被剝奪。（4） 環(huán)路等待條件——存在進(jìn)程—資源環(huán)形鏈。4. 處理死鎖的基本方法（1） 預(yù)防死鎖——設(shè)置某些限制條件，破壞必要條件中的一個或幾個。（2） 避免死鎖——在資源的動態(tài)分配過程中，防止系統(tǒng)進(jìn)入不安全狀態(tài)。（3） 檢測死鎖——通過系統(tǒng)設(shè)置的檢測機(jī)構(gòu)，及時檢測出死鎖的發(fā)生，并精確確定與死鎖有關(guān)的進(jìn)程和資源。178。 保存有關(guān)資源的請求和分配信息——資源分配圖資源分配圖由一組結(jié)點N和一組邊E組成。N被分成兩個互斥的子集，一組進(jìn)程結(jié)點P={p1，p2,……，pn}，一組資源結(jié)點R={r1，r2,……，rm}E中的邊e連接著P中的一個結(jié)點和R中的一個結(jié)點。e={pi，ri} 表示進(jìn)程pi請求一個單位的ri資源e={rj，pj} 表示把一個單位的rj資源分配給進(jìn)程pj178。 提供算法檢測系統(tǒng)是否死鎖——死鎖定理在資源分配圖上，找出一個既不阻塞又非獨立的進(jìn)程結(jié)點，簡化后使其成為孤立的結(jié)點。在進(jìn)行一系列的簡化后，若能消去圖中所有的邊，使所有結(jié)點都成為孤立的結(jié)點，則該圖是可完全簡化的。所有的簡化順序?qū)⒌玫较嗤牟豢珊喕瘓D。s為死鎖狀態(tài)的充分條件是，當(dāng)且僅當(dāng)S狀態(tài)的資源分配圖是不可完全簡化的。（4） 解除死鎖——將進(jìn)程從死鎖狀態(tài)下解脫出來。J 剝奪資源J 撤消進(jìn)程5. 銀行家算法178。 系統(tǒng)的安全狀態(tài)所謂安全狀態(tài)，是指系統(tǒng)能按某種順序，如P1,P2…Pn，來為每個進(jìn)程分配其所需資源，直至最大需求，使每個進(jìn)程都可順利完成。若系統(tǒng)不存在這樣一個安全序列，則稱系統(tǒng)處于不安全狀態(tài)。如果不按照安全序列分配資源，則系統(tǒng)可能由安全狀態(tài)進(jìn)入不安全狀態(tài)。例，系統(tǒng)共有12臺磁帶機(jī)，T0時刻的情況如下表，已分配出9臺，可用磁帶機(jī)為3臺。經(jīng)分析發(fā)現(xiàn)，T0時刻存在安全序列 P2，P1，P3，故系統(tǒng)是安全的。 進(jìn)程 最大需求 已分配 尚需要 可用 P1 10 5 5 3（2） P2 4 2 2 P3 9 2（3） 7（6）若此時P3請求1臺磁帶機(jī)，則分配情況如上表（括號內(nèi)的數(shù)據(jù)），此時系統(tǒng)不存在安全序列，進(jìn)入不安全狀態(tài)，將導(dǎo)致死鎖。178。 利用銀行家算法避免死鎖216。 數(shù)據(jù)結(jié)構(gòu)（n個進(jìn)程，m類資源）可利用資源available[1..m]最大需求矩陣(n*m) max分配矩陣(n*m) allocation需求矩陣(n*m) need[i,j]=max[i,j]allocation[i,j]216。 步驟設(shè)request[j]=k，表示進(jìn)程P需要k個j類資源。Request=need Y NRequest=available資源數(shù)超出需求 N系統(tǒng)資源不足