os之分布式系統(tǒng)中的同步問(wèn)題-全文預(yù)覽
【正文】 ? 算法的缺點(diǎn) ， 協(xié)調(diào)者是一個(gè)單點(diǎn)失效的機(jī)制 如果協(xié)調(diào)者垮臺(tái)了 ， 是 “ 不允許 ” 呢 ， 還是它自身垮臺(tái)了呢 ？ 2. 分布式算法 (1) ? Richart與 Agrawala(Ramp。 保留 JFKNairobi。 y = 0。 End_transcation x = 0/1 日志 x = 0/1 日志 y = 0/2 x = 0/1 日志 y = 0/2 x = 0/4 (a) (b) (c) (d) 寫(xiě)前日志 原子事務(wù)實(shí)現(xiàn) 寫(xiě)前日志 (1) ? 事務(wù)成功地執(zhí)行完畢并被提交之后 ? 要在日志中寫(xiě)入一個(gè)提交記錄 ? 如果終止事務(wù) ， 就可以利用日志恢復(fù)系統(tǒng)的原始狀態(tài) ? 回溯 : 從最后一條日志記錄開(kāi)始向前 ，讀出每條記錄 ， 取消該記錄中描述的操作 ? 日志還可以用于從系統(tǒng)崩潰中恢復(fù)執(zhí)行 兩段提交協(xié)議 (1) ? 兩段提交協(xié)議 (Gray, 1978)使用最廣泛的一種協(xié)議 ? 包含有關(guān)功能的一個(gè)進(jìn)程作為協(xié)調(diào)者 ? 通常是執(zhí)行事務(wù)的進(jìn)程 兩段提交協(xié)議 (2) ? 協(xié)調(diào)者寫(xiě)一條日志記錄 ? 說(shuō)明它要開(kāi)始提交協(xié)議 ? 然后向事務(wù)中包含的其它進(jìn)程 （ 從屬 ）發(fā)送消息 ? 通知這些進(jìn)程準(zhǔn)備提交 在日志文件中寫(xiě)“ prepare” 發(fā)送“ prepare”消息 收錄所有回答 寫(xiě)日志記錄 發(fā)送“ Commit”消息 第一階段 第 二 階段 在日志文件中寫(xiě)“ Ready” 發(fā)送“ Ready”消息 發(fā)送“ Finished”消息 在日志文件中寫(xiě)“ Commit” 承諾 成功執(zhí)行的兩段提交協(xié)議 協(xié)調(diào)者 子協(xié)調(diào) 兩段提交協(xié)議 (3) ? 從屬進(jìn)程接到消息后 ? 檢查自己是否就緒 ? 將結(jié)果寫(xiě)入日志 ? 并發(fā)送它的決定 ? 協(xié)調(diào)者接收到所有從屬進(jìn)程的響應(yīng)后 ? 就可以確定提交還是終止事務(wù) 兩段提交協(xié)議 (4) ? 如果所有進(jìn)程都已準(zhǔn)備好提交 ? 那么事務(wù)就提交 ? 如果有一個(gè)或幾個(gè)進(jìn)程不能提交 ? 事務(wù)中止 兩段提交協(xié)議 (5) ? 無(wú)論提交或終止 ， 協(xié)調(diào)者要寫(xiě)日志記錄 ? 將其決定知所有的從屬 ? 在寫(xiě)了這條日志記錄之后 ， 才真正地提交事務(wù) ? 使用穩(wěn)定存儲(chǔ)器中的日志 ， 協(xié)議在崩潰時(shí)有較大的彈性 八、并發(fā)控制 ? 三種不同的并發(fā)控制算法 加鎖 ? 最古老也是最廣泛使用的并發(fā)控制算法 最簡(jiǎn)單的加鎖形式 ? 當(dāng)進(jìn)程在事務(wù)中要讀或?qū)懩硞€(gè)文件時(shí) ? 首先就為讀文件加鎖 ? 加鎖可以由單個(gè)集中式的鎖管理器完成 ? 也可以在每臺(tái)機(jī)器上利用本地的鎖管理器管理本地文件 ? 鎖管理器都維護(hù)一個(gè)被鎖定文件的列表 ? 用于拒絕其它進(jìn)程試圖鎖定已加鎖文件 ? 文件的鎖通常由事務(wù)系統(tǒng)獲取和釋放 ， 不需要編程人員的處理 并發(fā)控制 加鎖的改進(jìn) ? 方案太嚴(yán)格 ? 可以通區(qū)分讀操作鎖和寫(xiě)操作鎖 改進(jìn) 讀操作鎖 ? 為某文件設(shè)置了讀操作鎖 ? 仍允許為該文件設(shè)置其它的讀操作鎖 ? 讀操作鎖用于保證讀文件的過(guò)程中文件不會(huì)被修改 ? 但是沒(méi)有理由拒絕其它事務(wù)讀這個(gè)文件 寫(xiě)操作鎖 ? 鎖定一個(gè)文件執(zhí)行寫(xiě)操作時(shí) ? 不允許再為該文件設(shè)置任何類(lèi)型的鎖 ? 讀操作鎖是共享的 ， 而寫(xiě)操作鎖是互斥的 加鎖的粒度 ? 加鎖的單位大小稱(chēng)為粒度 ? 加鎖的單位可是更小的單位 ? 如單個(gè)的記錄或頁(yè) ? 可能是更大的單位 ， 如整個(gè)數(shù)據(jù)庫(kù) ? 粒度越細(xì) ， 加鎖的準(zhǔn)確度越高 ， 能夠達(dá)到的并行性也更好 ， ? 細(xì)粒度的加鎖操作需要更多的鎖 ， 代價(jià)更高 ? 而且更容易引起死鎖 2. 兩段加鎖方法 ? 進(jìn)程在它的成長(zhǎng)階段獲取所需的全部鎖 ? 在收縮階段釋放這些鎖 ? 如果進(jìn)程在到達(dá)收縮階段前不允許修改任何文件 ? 那么在獲取某些鎖失敗時(shí) ， 可以直接釋放所有的鎖 ? 稍待片刻后 ， 再重?cái)嚅_(kāi)始 兩段加鎖 鎖的數(shù)量 時(shí)間 成長(zhǎng)階段 收縮階段 鎖點(diǎn)峰 兩段加鎖方法被廣泛應(yīng)用的原因 ? 可以證明 ， 如果所有事務(wù)都使用兩段加鎖方法 ? 那么將這些事務(wù)交叉后形成的時(shí)間表是序列化的 嚴(yán)格的兩段加鎖機(jī)制 ? 收縮階段在事務(wù)結(jié)束運(yùn)行 ? 而提交或終止之后才發(fā)生 兩段加鎖的優(yōu)點(diǎn) ? 每個(gè)事務(wù)讀到的值都是由已經(jīng)提交的事務(wù)修改過(guò)的值 ? 不會(huì)因?yàn)榛谝粋€(gè)還不能使用的文件的原因 ，而終止該事務(wù) ? 所有鎖的分配和釋放都由系統(tǒng)處理 ? 不需要事務(wù)了解這些過(guò)程： ? 文件被訪問(wèn)時(shí) ， 系統(tǒng)為它加鎖； ? 事務(wù)結(jié)束時(shí) ， 釋放相關(guān)的鎖 ? 避免了級(jí)連式的事務(wù)終止的情況發(fā)生： ? 由于使用了不該使用的文件而必須中止事務(wù) 九、常用的避免死鎖的方法 (1) ? 以某種規(guī)范的順序分配鎖 ， 避免出現(xiàn)占有一等待循環(huán) ? 明確地維護(hù)一張圖 ， 說(shuō)明哪個(gè)進(jìn)程占有哪些鎖 ， 等待哪些鎖 ? 然后通過(guò)檢查該圖中是否有回路就可以確定是否發(fā)生了死鎖 常用的避免死鎖的方法 (2) ? 超時(shí)方案 ? 限定鎖的占有時(shí)間不超過(guò) T秒 ? 如果某個(gè)鎖連續(xù)被同一事務(wù)占有的時(shí)間超過(guò) T秒 ? 斷定發(fā)生了死鎖 并發(fā)控制優(yōu)化 ? 隱含的技術(shù)思想驚人地簡(jiǎn)單： 盡管繼續(xù)做自己的事務(wù) ， 不必關(guān)心別人正在做什么 如果有問(wèn)題 ， 以后再處理 ? 實(shí)際上 , 沖突很少發(fā)生 ? 因此大多數(shù)時(shí)間這種策略的效果很好 優(yōu)化的并發(fā)控制方法 (1) ? 通過(guò)記錄被事務(wù)讀過(guò)和寫(xiě)過(guò)的文件處理沖突 ? 提交某個(gè)事務(wù)時(shí) ， 先檢查所有其它事務(wù) ? 確定事務(wù)啟動(dòng)之后 ， 它的文件是否被修改過(guò) ? 如果有 ， 事務(wù)終止 如果沒(méi)有 ， 事務(wù)提交 優(yōu)化的并發(fā)控制方法 (2) ? 優(yōu)化的并發(fā)控制最適合基于私有空間的實(shí)現(xiàn)方式 ? 每個(gè)事務(wù)以私有方式修改文件 ， 不會(huì)互相干擾 ? 結(jié)果 ， 新文件或者被提交 ， 或者被釋放 ? 優(yōu)點(diǎn) ， 它不會(huì)引起死鎖 所有的進(jìn)程不必等待所需要的鎖 ， 達(dá)到最大的并行度 ? 缺點(diǎn)是 ， 有時(shí)會(huì)失敗 ， 要重新執(zhí)行事務(wù) 在負(fù)載較重的情況下 ， 失敗可能性聚增 1. 時(shí)間戳 (1) ? 系統(tǒng)中每個(gè)文件都有相關(guān)的一個(gè)讀時(shí)間戳和一個(gè)寫(xiě)時(shí)間戳 ? Lamport算法可以保證這個(gè)時(shí)間戳是唯一的 ? 它們分別說(shuō)明是哪個(gè)已提交的事務(wù)最后讀 ， 寫(xiě)了該文件 時(shí)間戳 (2) ? 某個(gè)進(jìn)程試圖訪問(wèn)文件時(shí) ? 文件的讀時(shí)間戳和寫(xiě)時(shí)間戳應(yīng)比當(dāng)前事務(wù)的時(shí)間戳更早 （ 老 ） ? 順序關(guān)系說(shuō)明事務(wù)正按照正常的次序執(zhí)行 ， 一切正常 ? 時(shí)間戳方法并不關(guān)心并發(fā)事務(wù)是否使用相同的文件 ? 只要有較小數(shù)字的事務(wù)總是在先即可 利用時(shí)間戳進(jìn)行并發(fā)控制 利
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1