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