分布式操作系統(tǒng)-講義第4章分布式同步控制-資料下載頁
2024-10-09 15:51本頁面
【正文】 kstra,1965] ? Phas,max, free 202269 東北大學(xué)軟件所 于戈 第三章 分布式同步控制 43 集中式檢測 方法 ?進(jìn)程 資源等待圖 – 節(jié)點(diǎn)：進(jìn)程 P、資源 R – 有向邊 :(1)P?R請(qǐng)求關(guān)系 。 (2) R ? P擁有關(guān)系 。 ?死鎖檢測協(xié)調(diào)者 – 負(fù)責(zé)檢測死鎖 ?資源圖的維護(hù)策略： – 當(dāng)資源圖中，有一條邊加入 /刪除時(shí)，通知協(xié)調(diào)者 – 每個(gè)進(jìn)程周期性地向協(xié)調(diào)者發(fā)送圖的更新消息 – 協(xié)調(diào)者在需要時(shí)，向參入者請(qǐng)求 202269 東北大學(xué)軟件所 于戈 第三章 分布式同步控制 44 ?假死鎖問題： B釋放 R,請(qǐng)求 T。若 請(qǐng)求 T消息 先到達(dá) 協(xié)調(diào)者 ?解決方案一 ：協(xié)調(diào)者確認(rèn)（消息的全局時(shí)序） 集中式檢測 方法舉例 202269 東北大學(xué)軟件所 于戈 第三章 分布式同步控制 45 分布式檢測方法 ?Chandy－ Misra－ Haas分布式死鎖檢測算法， ?探測消息： 〈 阻塞 Pid，請(qǐng)求 Pid ，接收 Pid 〉 ? . （ 0,2,3） ,（ 0,4,6） ,（ 0,5,7 ） ,（ 0,8,0）構(gòu)成死鎖 202269 東北大學(xué)軟件所 于戈 第三章 分布式同步控制 46 分布式深度限制算法（ DWDL） ? 90%的死鎖發(fā)生在兩個(gè)進(jìn)程之間 ?算法： // p1為請(qǐng)求者 。 L(p1)為 p1的壽命 1) if ( waitQueue = p2p1p0 ) then if ( L(p1)L(p2) or L(p1))L(p0) then restart p1。 else restart p0。 2) if (waitQueue = p1p139。p0 ) then if ( L(p39。1)L(p1) or L(p39。1)L(p0)) then restart p39。1。 else restart p0。 3) if (waitQueue = p2p1p39。1p0 ) then if ( L(p1)L(p2) or L(p1)L(p0)) then restart p1。 else restart p39。1。 202269 東北大學(xué)軟件所 于戈 第三章 分布式同步控制 47 ?等待 死亡 算法 (waitdie) – 設(shè)請(qǐng)求進(jìn)程 0的時(shí)間印 t0, 擁有資源的進(jìn)程 1的時(shí)間印 t1 – 如果 t0t1, 0等待 。 – 否則，撤銷 0 分布式死鎖預(yù)防 202269 東北大學(xué)軟件所 于戈 第三章 分布式同步控制 48 分布式死鎖的預(yù)防 ?負(fù)傷 等待 算法 （ woundwait) – 設(shè)請(qǐng)求進(jìn)程 0的時(shí)間印 t0,擁有資源的進(jìn)程 1的時(shí)間印 t1 – 如果 t0t1，撤銷 1。 – 否則， 0等待 202269 東北大學(xué)軟件所 于戈 第三章 分布式同步控制 49 習(xí) 題 1. 在右圖中加入一條與 A并發(fā)的新消息。它既不在 A之前，也不在 A之后。 2. 假定有兩臺(tái)機(jī)器 A和 B， 它們的時(shí)鐘都是每毫秒滴答1000次。但實(shí)際上 B每毫秒滴答 900次。如果每分鐘根據(jù) UTC時(shí)間校正一次時(shí)鐘，那么 A和 B之間的最大時(shí)鐘偏差是多少？ 202269 東北大學(xué)軟件所 于戈 第三章 分布式同步控制 50 習(xí) 題 3. 假定 A和 B是相互獨(dú)立的兩個(gè)臨界區(qū)，進(jìn)程0要進(jìn)入 A，進(jìn)程 1要進(jìn)入 B， RA分布式互斥算法會(huì)導(dǎo)致死鎖嗎？說明理由。 4. 對(duì)所介紹的 bully選舉算法，進(jìn)行優(yōu)化。 5. 事務(wù)時(shí)間戳為 50的進(jìn)程申請(qǐng)事務(wù)時(shí)間戳為100的進(jìn)程占用的資源。按以下兩種策略，結(jié)果會(huì)如何 ?(1)等待 死亡；（ 2）負(fù)傷 等待。 更多資料請(qǐng)?jiān)L問：
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1