事務(wù)并發(fā)調(diào)度問(wèn)題
?
??? 昨天看模擬題，有一道關(guān)于數(shù)據(jù)庫(kù)并發(fā)的題目，不是很明白，所以今天特地到網(wǎng)上查了一下，在這里做一個(gè)記錄：
?
??? 題目是數(shù)據(jù)庫(kù)系統(tǒng)工程師考試06年5月下午卷的第5題，具體的題目是這樣的：
******************************************************************************
【說(shuō)明】
現(xiàn)有一個(gè)事務(wù)集｛T1,T2,T3,T4｝，其中這四個(gè)事務(wù)在運(yùn)行過(guò)程中需要讀寫(xiě)X、Y和Z。設(shè)Ti對(duì)X的讀操作記作TiR(X)，Ti對(duì)X的寫(xiě)操作記作TiW(X)。
事務(wù)對(duì)XYZ的訪問(wèn)情況如下：
T1：T1R(x)
T2：T2R(Y)，T2W(X)
T3：T3W(Y)，T3W(X)，T3W(Z)
T4：T4R(Z)，T4W(X)
?
【問(wèn)題1】試述事務(wù)并發(fā)高(調(diào))度的正確性準(zhǔn)則及其內(nèi)容(4分)
【問(wèn)題2】請(qǐng)判斷如下高(調(diào))度是否正確。(4分)
T3W(Y)，T1R(X)，T2R(Y)，T3W(X)，T2W(X)，T3W(Z)，T4R(Z)，T4W(X)
按這種調(diào)度產(chǎn)生的事務(wù)依賴關(guān)系圖如下：
??? 
【問(wèn)題3】給出與【問(wèn)題2】中調(diào)度等價(jià)的一串行調(diào)度序列。(3分)
?
(注：嚴(yán)重質(zhì)疑題目里的“高度”應(yīng)該是錯(cuò)別字，改成“調(diào)度”才可以理解)
******************************************************************************
?
??? 首先關(guān)于【問(wèn)題1】，我的理解是這樣的：事務(wù)的并發(fā)調(diào)度的正確性，取決于這個(gè)并發(fā)調(diào)度是不是可以等價(jià)得轉(zhuǎn)換為串行調(diào)度。只有當(dāng)一個(gè)并行調(diào)度可以與某一次的串行調(diào)度轉(zhuǎn)化時(shí)，這個(gè)并發(fā)調(diào)度才是正確的。
?
??? 然后對(duì)于【問(wèn)題2】，可能對(duì)題目本身比較難以理解。其實(shí)對(duì)于并行調(diào)度的正確性判斷不需要考慮讀寫(xiě)一致性和鎖定/解鎖的問(wèn)題，雖然事務(wù)T1/T2/T3/T4中的每一個(gè)子項(xiàng)都是原子性的，在啟動(dòng)前鎖定，完成后解鎖，但是如果不是按照整個(gè)事務(wù)的串行化執(zhí)行，其最后的結(jié)果是會(huì)發(fā)生錯(cuò)誤的。所以我們只能從事務(wù)對(duì)于X/Y/Z的依賴性的角度來(lái)進(jìn)行分析，例如：
?
??? 數(shù)據(jù)項(xiàng)X:T1R(X),T3W(X),T2W(X),T4W(X)
??? 相對(duì)于X的事物依賴圖為:T1--->T3,T1--->T2,T1--->T4,T3--->T2,T3--->T4,T2--->T4
?
??? 數(shù)據(jù)項(xiàng)Y:T3W(Y),T2R(Y)
??? 相對(duì)于Y的事物依賴圖為:T3--->T2
?
??? 數(shù)據(jù)項(xiàng)Z:T3W(Z),T4R(Z)
??? 相對(duì)于Z的事物依賴圖為T(mén)3--->T4
?
??? 綜合X,Y,Z的事物依賴圖得到題目已知的事物調(diào)度依賴圖。
??? 在事物調(diào)度依賴圖中,沿箭頭方向不產(chǎn)生回路(要包含所有事務(wù))的一條路徑就是與該并發(fā)調(diào)度等價(jià)的串行調(diào)度,假設(shè)在事務(wù)依賴圖中有回路產(chǎn)生,則該并發(fā)調(diào)度是不可串行化的。而本題按照T1--->T3--->T2--->T4的順序是滿足條件的，所以題中的并行調(diào)度順序是正確的。
?
?
??? 如果是不可串行化的調(diào)度，則可能是發(fā)生了死鎖。例如...,T2R(Y),T3W(X),...T2W(X),T3W(Y),...
??? 如果出現(xiàn)這種情況，則改換成串行模式時(shí)，對(duì)于Y，T3在等待T2結(jié)束后對(duì)Y解鎖，而對(duì)于X，T2在等待T3結(jié)束后對(duì)X解鎖，這樣就造成了互相等待的死鎖情況而無(wú)法進(jìn)行下去。
?
??? 需要特別注意的是：在事物依賴有向圖中，選取的路徑是不可以包括回路(多方死鎖)，或者雙向路徑的。
?
??? 對(duì)于【問(wèn)題三】，只要搞明白上面的原理，就很簡(jiǎn)單了，答案就是 T1--->T3--->T2--->T4
?
?