【文章內(nèi)容簡介】 崩潰，那么在恢復(fù)時(shí)只需要從停止的地方開始繼續(xù)工作就可以了。 ? 如果在響應(yīng)第一條消息之前某個(gè)下屬崩潰了，那么協(xié)調(diào)者將會(huì)給它不斷地發(fā)送消息。 ? 如果協(xié)調(diào)者以后崩潰了，那么它就可以從日志中看出自己所處的位置，并能決定該作些什么。 陳香蘭 41 分布式系統(tǒng)同步（續(xù)） 并發(fā)控制 ? 當(dāng)多個(gè)事務(wù)在不同的進(jìn)程（在不同的處理機(jī)上）中同時(shí)執(zhí)行時(shí)，需要一些機(jī)制以保證它們互不干擾。這種機(jī)制稱為并發(fā)控制算法。 ? 本節(jié)將研究三個(gè)不同的算法 1）加鎖法 2）樂觀并發(fā)控制 3）時(shí)間戳 陳香蘭 42 分布式系統(tǒng)同步（續(xù)） 加鎖法 ? 最古老而且使用最廣泛的并發(fā)控制算法是加鎖法。 ? 最簡單形式是： ? 作為一個(gè)事務(wù)的一部分 ，當(dāng)一個(gè)進(jìn)程需要讀或?qū)懸粋€(gè)文件（或其他對(duì)象）時(shí)，它首先將這個(gè)文件加鎖。 ? 由于正常的進(jìn)程在一個(gè)文件被加鎖前不會(huì)試圖去存取它，因此對(duì)文件加鎖可以防止其他進(jìn)程對(duì)文件的訪問，這就保證了一個(gè)事務(wù)的生存期內(nèi)文件不會(huì)被改變。 ? 鎖一般由事務(wù)系統(tǒng)請(qǐng)求和釋放 ，不需要編程人員的操作。 陳香蘭 43 分布式系統(tǒng)同步（續(xù)） 加鎖法實(shí)現(xiàn) 1. 可以使用一個(gè) 集中式加鎖管理程序 來實(shí)現(xiàn) 2. 可以在每臺(tái)機(jī)器上有一個(gè) 本地加鎖管理程序 來管理本地文件。 ? 兩種情況下 加鎖管理程序 都擁有一個(gè) 鎖定的文件列表 ， 所有對(duì)已加鎖文件進(jìn)行的加鎖嘗試都將被拒絕 。 陳香蘭 44 分布式系統(tǒng)同步（續(xù)） 讀鎖和寫鎖 ? 上述方案的限制過于嚴(yán)格，可以通過區(qū)分讀鎖和寫鎖來加以改進(jìn)。 ? 如果在一個(gè)文件上設(shè)置了讀鎖，那么在它上面設(shè)置其他的讀鎖也是允許的，寫鎖是禁止的。 ? 讀鎖用來確保文件不會(huì)被改寫（也即排斥所有的寫入者），但不禁止其他讀取文件的事務(wù)。 ? 與此相反，當(dāng)一個(gè)文件被設(shè)置寫鎖時(shí)，其他任何類型的鎖都被禁止。 ? 所以說 讀鎖是可以共享的，而寫鎖必須是互斥的 。 陳香蘭 45 分布式系統(tǒng)同步（續(xù)） 鎖的粒度 ? 為簡單起見，我們?cè)?jīng)假設(shè)加鎖的單位是整個(gè)文件。但在實(shí)際中， ? 可能是更小一些的單位，比如 記錄 或 頁面 ， ? 也可能是大一些，比如 整個(gè)數(shù)據(jù)庫 。 ? 一個(gè)加鎖單位究竟取多大 的問題稱為鎖的粒度。 ? 粒度越細(xì)，加鎖就可以越精確，也就能實(shí)現(xiàn)更大的并發(fā)度（例如，并不因?yàn)槟硞€(gè)進(jìn)程正在使用文件的開頭就阻塞另一個(gè)試圖使用該文件末尾的進(jìn)程）。 ? 另一方面， 鎖分得越細(xì)致，也就越需要更多的鎖，這樣的開銷也就越大，也就更容易導(dǎo)致死鎖 。 陳香蘭 46 分布式系統(tǒng)同步（續(xù)） 兩階段加鎖法 ? 在需要或不再需要鎖時(shí)去請(qǐng)求或釋放鎖可能會(huì)導(dǎo)致 不一致和死鎖 。因此，常用的加鎖方法是兩階段加鎖法。 ? 在兩階段加鎖法中， 進(jìn)程在增長階段先請(qǐng)求它需要的所有鎖，然后在收縮階段釋放它們 。 陳香蘭 47 分布式系統(tǒng)同步（續(xù)） ? Eswaran等人在 1976年證明：如果所有的事務(wù)都使用兩階段加鎖法，那么通過交錯(cuò)事務(wù)進(jìn)行的所有調(diào)度都是串行的。這也是兩階段加鎖法廣泛使用的原因。 陳香蘭 48 分布式系統(tǒng)同步（續(xù)） 死鎖 ? 加鎖即使兩階段加鎖都可能會(huì)導(dǎo)致死鎖。 ? 若兩個(gè)進(jìn)程都試圖以相反的順序請(qǐng)求同一對(duì)鎖，那么就會(huì)發(fā)生死鎖。 ? 解決方法： 1）采用以某種順序請(qǐng)求所有鎖的方法來防止保持 等待循環(huán)的出現(xiàn)。 2）通過對(duì)一張描述哪個(gè)進(jìn)程可以擁有哪個(gè)鎖，它還想請(qǐng)求哪個(gè)鎖的圖進(jìn)行死鎖掃描，以便檢查是否有環(huán)路出現(xiàn)，以防止死鎖。 3）如果事先知道一個(gè)鎖的擁有時(shí)間不會(huì)超過 T秒，也可以采用一個(gè)超時(shí)方案：如果某個(gè)擁有者連續(xù)擁有同一個(gè)鎖超過了 T秒，那么一定是出現(xiàn)了死鎖。 陳香蘭 49 分布式系統(tǒng)同步（續(xù)） 樂觀并發(fā)控制 ? 處理同時(shí)運(yùn)行多個(gè)事務(wù)的第二種方法是樂觀并發(fā)控制法（ Kung and Robinson， 1981）。 ? 這種方法的思想比較簡單： ? 盡管放心去做你想做的，不用在意其他人正在做什么。如果有問題出現(xiàn)，那么以后再考慮吧 。 ? 在實(shí)際情況中， 沖突相對(duì)來說非常少 ，所以這個(gè)策略大部分時(shí)間都可以正常工作。 陳香蘭 50 分布式系統(tǒng)同步（續(xù)） 樂觀并發(fā)控制 — 沖突的處理 ? 盡管沖突會(huì)非常少，但存在的可能性還是有的，因此還需要一些處理沖突的方法。 ? 樂觀并發(fā)控制算法： ? 記錄下有哪些文件曾經(jīng)被讀寫過。 ? 在提交時(shí)刻，檢測(cè)其他的事務(wù)以判斷在本事務(wù)開始后它的文件是否被其他事務(wù)修改過。 ? 如果被修改過，那么本事務(wù)將被中止。 ? 如果沒有修改過，那么本事務(wù)就可以提交了。 陳香蘭 51 分布式系統(tǒng)同步（續(xù)） ? 樂觀并發(fā)控制算法 最適合于基于私有工作空間 的情況。 ? 每個(gè)事務(wù)都獨(dú)立地修改各自的文件，不會(huì)涉及其他的事務(wù)。 ? 在結(jié)束的時(shí)候，新的文件要么被提交要么被釋放。 ? 樂觀并發(fā)控制算法的優(yōu)點(diǎn) : ? 避免了死鎖，而且允許最大限度的并行度（進(jìn)程不需要去等待一個(gè)鎖） ? 缺點(diǎn) : ? 有時(shí)可能會(huì)失效，這時(shí)，所有事務(wù)都必須退回重新運(yùn)行 ? 在重負(fù)載的情況下，算法失效的可能性將會(huì)直線上升。 陳香蘭 52 分布式系統(tǒng)同步（續(xù)） 時(shí)間戳 ? 一個(gè)完全不同的并發(fā)控制方法是： 在一個(gè)事務(wù)開始做 BEGIN_TRANSACTION的時(shí)候給它分配一個(gè)時(shí)間戳 （ Reed， 1983） ? 通過使用 Lamport的算法，我們可以確保時(shí)間戳是唯一的 ? 系統(tǒng)中， 每個(gè)文件都擁有一個(gè)讀取時(shí)間戳和寫入時(shí)間戳 ，以判斷哪個(gè)已提交的進(jìn)程最近一次讀取或?qū)懭脒^該文件。 陳香蘭 53 分布式系統(tǒng)同步（續(xù)） 時(shí)間戳（ cont’ d） ? 若事務(wù)都很短小且在時(shí)間間隔上比較大，那么一般來說當(dāng)一個(gè)進(jìn)程試圖訪問某個(gè)文件時(shí)，該文件的讀寫時(shí)間戳將早于當(dāng)前事務(wù)的時(shí)間戳。 ? 這種次序意味著事務(wù)正在以正確的順序進(jìn)行處理。 陳香蘭 54 分布式系統(tǒng)同步（續(xù)） 時(shí)間戳（ cont’ d） ? 當(dāng)次序不正確的時(shí)候，就表明一個(gè)晚于當(dāng)前事務(wù)開始的事務(wù)試圖插入、訪問文件并提交。 ? 這種情況意味著當(dāng)前事務(wù)開始得過早了，因此需要中止。 2 0 0 6 年3 月 1 日2 0 0 6 年3 月 2 日2 0 0 6 年3 月 3 日2 0 0 6 年3 月 4 日2 0 0 6 年3 月 2 7 日2 0 0 6 年3 月 2 1 日需要中止 陳香蘭 55 分布式系統(tǒng)同步（續(xù)） 時(shí)間戳（ cont’ d） ? 在某種意義上，這種方案同 Kung和 Robinson的方案一樣，也是樂觀的，盡管兩者的細(xì)節(jié)完全不同。 ? 在 Kung和 Robinson的方法中，我們希望并發(fā)事務(wù)不使用同一個(gè)文件。 ? 在時(shí)間戳方法中，我們不介意并發(fā)事務(wù)是否使用同一個(gè)文件，只要郵戳小的事務(wù)總是先執(zhí)行就可以了。 陳香蘭 56 分布式系統(tǒng)同步（續(xù)） ? 同加鎖法相比，時(shí)間戳有著不同的特性。 ? 當(dāng)一個(gè)事務(wù)碰到了更晚的時(shí)間戳?xí)r，就要中止， ? 加鎖法在相同的情況下要么等待要么立即執(zhí)行。 ? 另一方面，時(shí)間戳方法不會(huì)出現(xiàn)死鎖，這是極大的改進(jìn)。 ? 總而言之 ? 事務(wù)具備許多優(yōu)點(diǎn)，因此對(duì)構(gòu)造可靠的分布式系統(tǒng)而言它就成為了一種比較好的技術(shù)。 ? 它的主要問題在于實(shí)現(xiàn)的復(fù)雜性，這將導(dǎo)致降低性能。 陳香蘭 57 分布式系統(tǒng)同步（續(xù)） 分布式系統(tǒng)中的死鎖 ? 分布式系統(tǒng)中的死鎖類似單處理機(jī)系統(tǒng)中的死鎖，只是情況更壞。 ? 它們更難于避免、預(yù)防或者檢測(cè)，即使在檢測(cè)到以后也很難處理，因?yàn)樗械南嚓P(guān)信息都分散在多臺(tái)機(jī)器上。 ? 在分布式數(shù)據(jù)庫系統(tǒng)中，死鎖的問題可能會(huì)相當(dāng)嚴(yán)重。 陳香蘭 58 分布式系統(tǒng)同步（續(xù)） 關(guān)于死鎖的分類 ? 有人將分布式死鎖分成了兩類： 通信死鎖和資源死鎖。例如，進(jìn)程 A試圖發(fā)送消息給進(jìn)程 B，進(jìn)程 B給進(jìn)程 C發(fā)送消息，而 C又試圖給 A發(fā)送消息，那么就會(huì)發(fā)生死鎖。在這種情況下導(dǎo)致死鎖的原因可能有多種，例如無法得到緩沖區(qū)。 ? 當(dāng)多個(gè)進(jìn)程為了互斥訪問 IO設(shè)備、文件、鎖或其他資源時(shí)就會(huì)發(fā)生資源