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