【正文】 死鎖 –如果資源分配圖中有環(huán)路，但涉及的資源類中有多個資源實例，則對該圖進(jìn)行簡化，直至所有進(jìn)程成為孤立點，稱該有向圖可完全化簡。 –進(jìn)程對共享文件互斥使用，即一個進(jìn)程正在讀或?qū)憰r，另一個進(jìn)程必須等待。 if (state[i] eating) then wait(self[i], scount[i], IM)。 define pickup, putdown。 } void signal(semaphore x_sem, int x_count, interf IM) { if (x_count 0) { ++。 end。 理發(fā)； end else V(mutex)。 V(mutex)。 customers := 0。 if ( = 0) { BV()。 Semaphore S。 ++ 。 }。 end。 procedure read begin P(mutex)。 … coend. 信號量與 PV操作 五個哲學(xué)家吃通心面（面條）問題 – 有五個哲學(xué)家圍坐在一圓桌旁，桌子中央有一盤通心面，每人面前有一只空盤子，每兩人之間放一把叉子。 Xi := A[j]。 goto L1。 begin L1: 按旅客要求找到對應(yīng)的 A[j]。 cobegin … process Pi begin … P(mutex)。 procedure V (var s: semaphore)。 – V(s)：將信號量 s加一 描述： s := s + 1。 process consumer while (TRUE) begin if (counter = 0) sleep()。 in, out: integer := 0。 repeat Swap(lock, pi ) until pi = false。 end。 coend. 臨界區(qū)管理 實現(xiàn)臨界區(qū)管理的硬件方法 – 關(guān)中斷（阻止進(jìn)程交替執(zhí)行） – 測試并建立指令， TS （測試與上鎖不能分離） TS(x): 若 x = true, 則 x := false。 ③ while (inside[2] and turn = 2) do begin end。 算法滿足臨界區(qū)管理的三個條件。 process P2 begin inside[2]:=true。 inside[2]:=false。 ② while inside1 do begin end。 coend 臨界區(qū)管理 臨界區(qū)管理的嘗試 (2) inside1,inside2:Boolean inside1 := false。 ③ 臨界區(qū) 。 ② {修改主存分配表 } ③ {釋放等主存資源的進(jìn)程 } end。一個進(jìn)程的執(zhí)行依賴于其協(xié)作進(jìn)程的消息或信號，當(dāng)沒有得到該消息或信號時需要等待，直到消息或信號到達(dá)時被喚醒 –進(jìn)程的互斥關(guān)系是一種特殊的進(jìn)程同步關(guān)系 并發(fā)進(jìn)程概述 并發(fā)程序設(shè)計的優(yōu)點： –對于單處理器系統(tǒng)，可讓處理器和個 I/O設(shè)備同時工作，發(fā)揮硬件的并行能力 –對于多處理器系統(tǒng)，可讓各進(jìn)程在不同的處理器上并行執(zhí)行，加快計算速度 –簡化程序設(shè)計任務(wù) 并發(fā)進(jìn)程概述 采用并發(fā)程序設(shè)計的目的 –充分發(fā)揮硬件的并行工作能力，提高系統(tǒng)效率 –是多道程序設(shè)計的基礎(chǔ) 并發(fā)進(jìn)程概述 有交互關(guān)系的并發(fā)進(jìn)程執(zhí)行時帶來的問題 –由于一組有交互關(guān)系的并發(fā)進(jìn)程，其執(zhí)行的相對速度無法控制，導(dǎo)致出現(xiàn)多種與時間有關(guān)的錯誤出現(xiàn) –與時間有關(guān)錯誤的表現(xiàn)形式： 結(jié)果不唯一 永遠(yuǎn)等待 并發(fā)進(jìn)程概述 結(jié)果不唯一錯誤舉例，訂票問題 process Ti ( i = 1, 2 ) var Xi:integer。}。 send。 –特點： （程序與程序的執(zhí)行一一對應(yīng)） 執(zhí)行的順序性 – 內(nèi)部順序性、外部順序性 環(huán)境的封閉性 執(zhí)行結(jié)果的確定性 計算過程的可再現(xiàn)性 并發(fā)進(jìn)程概述 順序程序設(shè)計舉例 –某程序需要循環(huán)執(zhí)行輸入、計算、輸出三個過程 – while(TRUE) {input。 process。 P2: b = z + 1。 ④ Aj:=Xi。 region Y do {…}。 process P2 Begin ① while inside1 do begin end。 ② while inside2 do begin end。 end。 while turn=2 do begin end。 inside[2]:=true。 turn := 1 or 2。 process P2 begin ① inside[2] := true。 實現(xiàn)： var s: boolean。 b := temp。 信號量與 PV操作 同步問題 –生產(chǎn)者 消費者問題是計算機操作系統(tǒng)中并發(fā)進(jìn)程內(nèi)在關(guān)系的一種 抽象 ，是 典型 的進(jìn)程同步問題 生產(chǎn)者（如，計算進(jìn)程、發(fā)送進(jìn)程） 消費者（如，打印進(jìn)程、接收進(jìn)程） –問題描述 （有界緩沖問題） 有 n個生產(chǎn)者和 m個消費者，連接在一個有 k個單位緩沖區(qū)的有界環(huán)形緩沖上。 if (counter = k) sleep()。 counter := counter – 1。 end。 end。 … coend。 if Xi = 1 then begin Xi := Xi 1。 s: Array[1..m] of semaphore。 V(s[j])。 –引入一個計數(shù)器和兩個信號量解決此問題 int rc, 讀進(jìn)程計數(shù)器 W，允許寫信號量，初值為 1 mutex，互斥訪問 rc計數(shù)器信號量，初值為 1 讀者優(yōu)先的讀者 寫者問題 var rc: integer。 V(mutex)。 end。 。 二元信號量實現(xiàn)一般信號量（正確） typedef struct semaphore { int value。 if ( 0) { BV()。如果沒有顧客，理發(fā)師就在理發(fā)椅上睡覺。 waiting := 0。 procedure customer begin P(mutex)。 –代表共享資源的數(shù)據(jù)結(jié)構(gòu)及其上操作的一組過程構(gòu)成了管程 –管程是一種程序設(shè)計語言結(jié)構(gòu)成分，和信號量有同等的表達(dá)能力 管程 管程的基本結(jié)構(gòu) TYPE 管程名 = MONITOR 管程變量說明 。 Hoare方法實現(xiàn)管程 每個管程需要引入兩個信號量和一個計數(shù)器 – TYPE interf = RECORD semaphore mutex = 1，用于互斥方式調(diào)用管程過程 semaphore next = 0, 用于發(fā)出 signal的進(jìn)程掛起自己 int next_count = 0, 在 next上等待的進(jìn)程數(shù) END。 。 signal(self[k], scount[k], IM)。 test((i – 1) mod 5)。 –兩個基本的消息傳遞原語： send, receive – send, receive可以實現(xiàn)為同步操作也可實現(xiàn)為異步操作（一般實現(xiàn)為異步 send，同步 receive） 死鎖 死鎖的產(chǎn)生 死鎖的定義 死鎖的防止 死鎖的避免 死鎖的檢測和解除 死鎖 死鎖的產(chǎn)生 –計算機系統(tǒng)中存在許多獨占資源，如 硬件資源：磁帶機、繪圖儀等 軟件資源：進(jìn)程表、臨界區(qū)等 –為保證有效管理，獨占資源的使用必須經(jīng)歷： 申請資源，若資源不可用，則申請者進(jìn)入等待狀態(tài) 使用資源 歸還資源 –當(dāng)一個進(jìn)程需要獨占多個資源，而操作系統(tǒng)允許多個進(jìn)程并發(fā)執(zhí)行共享系統(tǒng)資源時，可能會出現(xiàn)進(jìn)程永遠(yuǎn)處于等待狀態(tài)的現(xiàn)象（死鎖） 死鎖 死鎖舉例 –進(jìn)程推進(jìn)順序不當(dāng)產(chǎn)生死鎖 進(jìn)程 P ① 請求讀卡機 ② 請求打印機 … ③ 釋放讀卡機 ④ 釋放打印機 進(jìn)程 Q ① 請求打印機 ② 請求讀卡機 … ③ 釋放讀卡機 ④ 釋放打印機 產(chǎn)生死鎖的執(zhí)行序列 P① Q① P② Q② 死鎖 死鎖舉例 – PV操作使用不當(dāng)產(chǎn)生死鎖（與前例類似） 死鎖也可能在不包括資源的情況下產(chǎn)生 – 同類資源分配不當(dāng)引起死鎖 5個同類資源， 5個請求進(jìn)程，每個進(jìn)程需要請求 2個資源才能繼續(xù)執(zhí)行，并最終運行結(jié)束 按照輪流分配，每次分配一個資源的分配方式將導(dǎo)致死鎖 – 對臨時性資源使用不加限制引起死鎖 進(jìn)程通信中，信件是臨時性資源，使用不當(dāng)出現(xiàn)死鎖 – P1等 P3的信件 S3到達(dá)后向 P2發(fā)送信件 S1 – P2等 P1的信件 S1到達(dá)后向 P3發(fā)送信件 S2 – P3等 P2的信件 S2到達(dá)后向 P1發(fā)送信件 S3 P1 P3 P2 S1 S2 S3 死鎖 死鎖產(chǎn)生的因素 –系統(tǒng)擁有資源的數(shù)量 –資源分配策略 –進(jìn)程對資源的要求 –并發(fā)進(jìn)程的推進(jìn)順序 死鎖 死鎖的定義 – 為避免與硬件故障以及其他程序性錯誤混淆，在定義死鎖前給定六個假設(shè)： 任意一個進(jìn)程要求資源的最大數(shù)量不超過系統(tǒng)能提供的最大量 如果一個進(jìn)程要求的資源均得到滿足，那么，它一定能夠在有限時間內(nèi)結(jié)束 一個資源在任何時間最多只被一個進(jìn)程所占有 一個進(jìn)程一次申請一個資源，且只有在申請資源得不到滿足時才處于等待狀態(tài) 一個進(jìn)程結(jié)束時釋放它占有的全部資源 系統(tǒng)具有有限個進(jìn)程和有限個資源 – 一組進(jìn)程處于死鎖狀態(tài)是指：如果在一個進(jìn)程集合中得每個進(jìn)程都在等待只能由該集合中其他一個進(jìn)程才能引發(fā)的事件，則稱一組進(jìn)程或系統(tǒng)此時發(fā)生了