分布式操作系統(tǒng)-講義第4章分布式同步控制-在線瀏覽
2024-11-10 15:51本頁面
【正文】 發(fā)送 E消息 2. 每個(gè)進(jìn)程繼續(xù)向后傳遞 E消息，直到返回 P 3. P在將新確定的協(xié)調(diào)者C’傳給所有進(jìn)程 5 2 202269 東北大學(xué)軟件所 于戈 第三章 分布式同步控制 20 互 斥 ?基本概念 – 當(dāng)一個(gè)進(jìn)程使用某個(gè)共享資源，其他進(jìn)程不允許對(duì)這個(gè)資源操作 ?臨界區(qū)： – 對(duì)共享資源進(jìn)行操作的程序段 ?基本方法： – 信號(hào)量、管程 ?問題： – 死鎖 – 饑餓 202269 東北大學(xué)軟件所 于戈 第三章 分布式同步控制 21 集中式算法 ?協(xié)調(diào)者：確定那個(gè)進(jìn)程可進(jìn)入臨界區(qū) ?通信量： 3個(gè)消息：請(qǐng)求 許可 釋放 ?缺點(diǎn)：?jiǎn)吸c(diǎn)失敗 C C C 202269 東北大學(xué)軟件所 于戈 第三章 分布式同步控制 22 分布式算法（ RicartAgrawala算法 ） 1. 在一個(gè)進(jìn)程 P打算進(jìn)入臨界區(qū) R之前，向所有其他進(jìn)程廣播消息 臨界區(qū) R名、進(jìn)程號(hào)、時(shí)間印 2. 當(dāng)一個(gè)進(jìn)程 P’收到消息后，做如下決定： ? 若 P’不在臨界區(qū) R中，也不想進(jìn)入 R，它就向 P發(fā)送 OK消息； ? 若 P’已經(jīng)在臨界區(qū) R中 ， 則不回答 ， 并將 P放入請(qǐng)求隊(duì)列； ? 若 P’也同時(shí)要進(jìn)入臨界區(qū) R，但是還沒有進(jìn)入時(shí)，則將發(fā)來的消息和它發(fā)送給其余進(jìn)程的時(shí)間戳對(duì)比。否則，不回答，并將 P放入請(qǐng)求隊(duì)列 ； 3. 當(dāng) P收到所有的 OK消息后，進(jìn)入 R。 4. 當(dāng) P退出 R時(shí)，如果存在等待隊(duì)列，則取出一個(gè)請(qǐng)求者，向其發(fā)送 OK消息。 進(jìn)程 0， 2申請(qǐng)進(jìn)入臨界 區(qū) 0 2 0 0 2 2 202269 東北大學(xué)軟件所 于戈 第三章 分布式同步控制 24 分布式算法評(píng)價(jià) ? 缺點(diǎn)： ? n點(diǎn)失敗 ? n點(diǎn)瓶頸 ? 2（ n1)個(gè)消息 ? 改進(jìn)方案： – 超時(shí)重發(fā) – 組通信 – 簡(jiǎn)單多數(shù)同意 202269 東北大學(xué)軟件所 于戈 第三章 分布式同步控制 25 令牌環(huán)算法 ? 構(gòu)造一個(gè)邏輯環(huán)， 得到令牌才可進(jìn)入臨界區(qū) 3 202269 東北大學(xué)軟件所 于戈 第三章 分布式同步控制 26 三種互斥算法的比較 算法 每次進(jìn)出 需要的消息 進(jìn)入前的延遲（按消息次數(shù)） 存在問題 集中式 3 2 協(xié)調(diào)者崩潰 分布式 2（ n1） 2（ n1） 任何一個(gè)進(jìn)程崩潰 令牌環(huán) 1到 ∞ 0到 n1 丟失令牌，進(jìn)程崩潰 202269 東北大學(xué)軟件所 于戈 第三章 分布式同步控制 27 原子性事務(wù) ?原子性： 組成原子事 務(wù) 的一組操作要么全部執(zhí)行，要么一個(gè)也不執(zhí)行，并且事 務(wù) 失敗后能返回到最初狀態(tài) ?例 1： 老式磁帶系統(tǒng)（備份） ?例 2：匯款（提款 ?存款） 202269 東北大學(xué)軟件所 于戈 第三章 分布式同步控制 28 事務(wù)的性質(zhì) 1. 原子性（ Atomic） ：對(duì)外部世界來說，事務(wù)的發(fā)生是不可分割的； 2. 一致性（ Consistent） ：事務(wù)不會(huì)破壞系統(tǒng)的恒定； 3. 隔離性（ Isolated） ：并發(fā)的事務(wù)之間不會(huì)互相干擾； 可串行性（ Serializable） :多個(gè)事務(wù)并發(fā)執(zhí)行的結(jié)果，與它們順序地執(zhí)行效果相同。 202269 東北大學(xué)軟件所 于戈 第三章 分布式同步控制 29 事務(wù)模型 ?穩(wěn)定存儲(chǔ)器（ Stable Storage）： – 通過一對(duì)雙工磁盤實(shí)現(xiàn) 202269 東北大學(xué)軟件所 于戈 第三章 分布式同步控制 30 事務(wù)原語 （ 1） BEGIN_TRA NSACTION：標(biāo)記一個(gè)事務(wù)的開始； （ 2） END_TRANSACTION：結(jié)束事務(wù)并設(shè)法提交； （ 3） ABORT_TRANSACTION
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1