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