【正文】 x = y * y。 Begin_transaction x = x + 1。 ENDTRANSACTION ENDTRANSACTION 事務(wù)原語(yǔ)屬性 (1) ? 三個(gè)必要屬性： ? 序列化 并發(fā)的事務(wù)互不干擾 ? 原子性 對(duì)外界來(lái)說(shuō) ， 事務(wù)的執(zhí)行是不可分割 ? 永久性 一旦事務(wù)被執(zhí)行 ， 它所做的修改就永久生效 事務(wù)原語(yǔ)屬性 (2) ? 事務(wù)第一個(gè)屬性 ， 序列化 ? 保證兩個(gè)或多個(gè)事務(wù)同時(shí)運(yùn)行時(shí) ? 對(duì)它們自己及其它進(jìn)程而言 ? 最后的結(jié)果與這些事務(wù)按照某種次序次序 ? 與系統(tǒng)有關(guān)順序運(yùn)行時(shí)的結(jié)果一致 事務(wù)原語(yǔ)屬性 (3) ? 第二個(gè)關(guān)鍵屬性 ， 原子性 ? 每個(gè)事務(wù)要么全部發(fā)生 ， 要么都不發(fā)生 ? 如果事務(wù)發(fā)生 ， 它的發(fā)生就是一個(gè)不可分割的瞬時(shí)動(dòng)作 ? 事務(wù)進(jìn)展過(guò)程中 ， 其它進(jìn)程都看不到事務(wù)發(fā)生的中間狀態(tài) 事務(wù)原語(yǔ)屬性 (3) ? 第三個(gè)屬性 ， 永久性 ? 一旦事務(wù)被提交 , 無(wú)論這時(shí)發(fā)生什么 ? 事務(wù)都會(huì)進(jìn)行下去 , 其結(jié)果永久生效 嵌套事務(wù) 事務(wù)可以包含子事務(wù) , 子事務(wù)稱為嵌套事務(wù) 假定一個(gè)事務(wù)并行啟動(dòng)多個(gè)子事務(wù) 其中一個(gè)子事務(wù)已經(jīng)提支 其操作結(jié)果在父事務(wù)中已經(jīng)生效 在繼續(xù)時(shí) ， 父事務(wù)被終止 要將整個(gè)系統(tǒng)恢復(fù)到頂層事務(wù)啟動(dòng)前的狀態(tài) 結(jié)果 : 已經(jīng)提交的子事務(wù)的結(jié)果也必須被恢復(fù) 事務(wù)永久性就只適用于頂層事務(wù)了 事務(wù)管理措施 任何事務(wù)或子事務(wù)啟動(dòng)時(shí) 提供系統(tǒng)中所有對(duì)象私存拷貝 ， 供其操作 如果事務(wù)被終止 ， 私有空間消失 ， 好象從沒(méi)存在過(guò) 如果提交事務(wù) ， 該事務(wù)私有空間代替父事務(wù)私有空間 在提交一子事務(wù)后啟動(dòng)一新的子事務(wù) 第二個(gè)子事務(wù)能看到第一個(gè)子事務(wù)執(zhí)行結(jié)果 2. 原子事務(wù)實(shí)現(xiàn) 私有工作空間 (1) ? 第一種方法：在實(shí)例啟動(dòng)事務(wù)時(shí) ? 為該進(jìn)程提供一個(gè)實(shí)際的私有工作空間 1 2 0 0 1 2 索引 自由塊 1 2 0 0‘ 3‘ 0 1 2 原始索引 0 1 2 3 1 2 0 0 1 2 3 3 私有 工作空間 磁盤 (a) (b) (c) 私有工作空間 (2) ? 優(yōu)化基礎(chǔ)：讀文件 ? 進(jìn)程讀文件 ， 不修改該文件 不需要這個(gè)文件的私有拷貝 只要使用實(shí)際的文件即可 （ 除非修改該文件 ） ? 進(jìn)程啟動(dòng)事務(wù)時(shí) ， 建立包含指向父進(jìn)程工作空間的反向指針 ，空的私有工作空間 私有工作空間 (2) ? 優(yōu)化基礎(chǔ)：寫操作 ? 不將整個(gè)文件復(fù)制到私有工作空間 ， 只復(fù)制文件的索引 ? 首次修改一個(gè)文件塊時(shí) ， 先要復(fù)制該文件塊 ， 然后將復(fù)制塊的地址插入文件索引 ? 復(fù)制后的新塊有時(shí)稱為影像塊 原子事務(wù)實(shí)現(xiàn) 寫前日志 (1) ? 修改文件前 ， 先在穩(wěn)定存儲(chǔ)器日志上寫入一個(gè)記錄 說(shuō)明是哪個(gè)事務(wù)做的修改 正在修改哪個(gè)文件夾哪個(gè)塊 修改前和修改后的值 ? 只有在正確完成日志的寫操作之后 ， 才修改文件 x = 0。 保留 NairobiMalindi。 保留 JFKNairobi。A)算法 ? 要求在系統(tǒng)中 ， 對(duì)所有事件安排一個(gè)次序 ? 進(jìn)程在進(jìn)入臨界區(qū)之前 ， 先構(gòu)造一條消息 ? 消息中包含有要進(jìn)入的臨界區(qū)的名稱 、 進(jìn)程編號(hào)以及當(dāng)前時(shí)間 ? 把該消息發(fā)給所有其他的進(jìn)程 分布式算法 (2) ? 為簡(jiǎn)單起見(jiàn) ， 假定消息的發(fā)送是可靠的 ， 每一進(jìn)程都認(rèn)可收到了此消息 ? 各個(gè)進(jìn)程依據(jù)情況 ， 發(fā)回消息 ? 如果接受方不在臨界區(qū)中并且也不想進(jìn)入 ，那么發(fā)出 OK ? 如果接受方已在臨界區(qū)內(nèi) ， 那么不應(yīng)答 ， 并把該消息放到隊(duì)列中 ? 如果接受方也想進(jìn)臨界區(qū) ， 但還沒(méi)有進(jìn)入 比較收到的消息和自己發(fā)出消息的時(shí)間戳 分布式算法 (3) ? 如果收到消息中的時(shí)間戳早 ， 則發(fā)出 OK ? 如果自己的消息較早 ， 那么不發(fā)消息 ， 并把請(qǐng)求送入隊(duì)列 ? 請(qǐng)求的進(jìn)程要等到所有其他進(jìn)程回送允許消息為止 ? 當(dāng)所有的允許消息都到達(dá)后 ， 該進(jìn)程就可以進(jìn)入申請(qǐng)的臨界區(qū) ? 退出臨界區(qū)后 ， 該進(jìn)程向在其隊(duì)列中的所有其他進(jìn)程發(fā)出 OK 分布式算法 (4) ? 算法關(guān)鍵 當(dāng)發(fā)生有沖突的申請(qǐng)時(shí) 所有進(jìn)程均同意有小時(shí)間戳一方取勝 分布式算法評(píng)價(jià) ? 算法中不存在單點(diǎn)失效 卻出來(lái)了多點(diǎn)失效 ? 一個(gè)進(jìn)程垮臺(tái)后 ， 它不響應(yīng)外來(lái)的請(qǐng)求 還阻塞了后續(xù)試圖進(jìn)入臨界區(qū)的進(jìn)程 ? 該算法僅使出錯(cuò)概率增大了 ， 而且還要占用大量網(wǎng)絡(luò)資源 分布式算法評(píng)價(jià) (2) ? 補(bǔ)救方法 ， 在發(fā)送方設(shè)置有超時(shí)的反應(yīng)機(jī)制 ? 該機(jī)制不斷詢問(wèn)直到有一個(gè)回答收到 ? 或者在經(jīng)過(guò)一段設(shè)定的時(shí)間段后 ， 得出結(jié)論 ，接收方有故障 ? 這個(gè)算法 ， 速度慢 ， 復(fù)雜 ， 開(kāi)銷也大 ? 但至少表明了 ， 分布式算法是可行的 3. 令牌環(huán)網(wǎng)算法 (1) ? 一個(gè)分布式系統(tǒng) ， 內(nèi)部的進(jìn)程構(gòu)成了一個(gè)邏輯上的環(huán)形網(wǎng) ? 所有的進(jìn)程都知道它的后續(xù)者是誰(shuí) ? 設(shè)令牌從進(jìn)程 k傳到進(jìn)程 k+1沿環(huán)傳遞 ? 當(dāng)進(jìn)程得到令牌后 ， 首先看是否需要進(jìn)入臨界區(qū) ? 如果需要 ， 進(jìn)程進(jìn)入臨界區(qū) ， 進(jìn)行所需的操作 ? 在撤出臨界區(qū)后 ， 該進(jìn)程讓令牌沿環(huán)傳遞 令牌環(huán)網(wǎng)算法 (2) ? 本算法規(guī)定 ， 進(jìn)程不允許用同一張令牌進(jìn)入第二個(gè)臨界區(qū) ? 如果一個(gè)進(jìn)程得到了令牌 ， 但不打算進(jìn)入臨界區(qū) 那么它就繼續(xù)傳遞令牌 ? 如果沒(méi)有進(jìn)程想進(jìn)入臨界區(qū) ， 令牌則沿著環(huán)路高速循環(huán) 令牌環(huán)網(wǎng)算法評(píng)價(jià) (1) ? 算法的正確性是明顯的 ? 因?yàn)槿魏螘r(shí)刻 ， 只有一個(gè)進(jìn)程持有令牌 ? 在臨界區(qū)中只可能有一個(gè)進(jìn)程 ? 由于巳經(jīng)規(guī)定好令牌傳遞次序 ， 所以不可能發(fā)生死鎖 ? 最壞情況是 ， 排在最后的進(jìn)程要等到其他進(jìn)程都進(jìn)入臨界區(qū) ， 完成操作 ， 并離開(kāi)之后 ，才輪到它 令牌環(huán)網(wǎng)算法評(píng)價(jià) (2) ? 算法的問(wèn)題 如果令牌因?yàn)槟撤N原因丟失了 ， 就必須重新生成一個(gè) ? 但是如何探測(cè)令牌是否丟失 ， 卻是一件難事 ? 令牌在一小時(shí)之內(nèi)沒(méi)有傳遞 ， 不意味著丟失了 ， 可能某個(gè)進(jìn)程還在使用它 令牌環(huán)網(wǎng)算法評(píng)價(jià) (3) ? 另一個(gè)問(wèn)題 ， 如果某個(gè)進(jìn)程垮臺(tái)了 ， 算法也會(huì)碰到麻煩 ? 補(bǔ)救方法 ， 進(jìn)程收到令牌后 ， 給予認(rèn)可 ? 在進(jìn)程試圖把令牌遞交給鄰居后 如果在規(guī)定時(shí)限內(nèi)沒(méi)有認(rèn)可回答 ， 就判定該鄰居是死進(jìn)程 ? 于是令牌越過(guò)死進(jìn)程 ， 傳到下一個(gè)進(jìn)程中 六、典型選舉算法：威力 (Bully)算法 ? 分布式系統(tǒng)需要有一個(gè)進(jìn)程擔(dān)當(dāng)協(xié)調(diào)者 ? 完成一些特別的工作任務(wù) ? 如何選擇進(jìn)程來(lái)?yè)?dān)當(dāng)協(xié)調(diào)者 威力 (Bully)算法 (1) ? 假定每臺(tái)機(jī)器只有一個(gè)進(jìn)程 每