淺析計(jì)算機(jī)系統(tǒng)中并發(fā)調(diào)度的可串行性

【摘 要】 計(jì)算機(jī)系統(tǒng)對并發(fā)事務(wù)中并發(fā)操作的調(diào)度是隨機(jī)的，而不同的調(diào)度可能會產(chǎn)生不同的結(jié)果。

【關(guān)鍵詞】 并發(fā)事務(wù) 并發(fā)控制 可串行性

Abstract ： The paper of the serializability of the concurrent scheduling in the computer system.

加鎖與可串行化是并發(fā)控制中采取的兩個主要措施。兩段鎖協(xié)議是解決可串行化調(diào)度較好的方法之一，但滿足可串行化的調(diào)度可能會出現(xiàn)死鎖<%=。因此，如何構(gòu)造一個既滿足！.3 又不出現(xiàn)死鎖的調(diào)度，是并發(fā)控制中要研究的一個重要課題。作為模擬與分析并發(fā)、異步、分布式系統(tǒng)的一種形式化方法，已被許多文獻(xiàn)用于描述和分析數(shù)據(jù)庫系統(tǒng)中的并發(fā)控制問題。文獻(xiàn)<>=建立了并發(fā)事務(wù)的模型，并給出了系統(tǒng)狀態(tài)死鎖的充分必要條件但所建模型不遵守！.3。文獻(xiàn)<#=建立了用于檢測數(shù)據(jù)庫一致性模型，并利用不變量討論了可串行化調(diào)度問題，但沒有討論死鎖問題。文獻(xiàn)<？=通過建立并發(fā)事務(wù)的模型，探討了可串行化調(diào)度與死鎖檢測問題，但當(dāng)系統(tǒng)中涉及的事務(wù)與數(shù)據(jù)資源較多時，所構(gòu)造的模型過于復(fù)雜。該文給出的并發(fā)事務(wù)的擴(kuò)展有色模型，可使網(wǎng)結(jié)構(gòu)大為簡化，所建模型完全符合！.3。利用該模型的可達(dá)標(biāo)識圖，給出了判斷滿足兩段鎖協(xié)議的調(diào)度是否死鎖的充分必要條件，并由此構(gòu)造出并發(fā)事務(wù)的無死鎖的可串行化調(diào)度。

計(jì)算機(jī)系統(tǒng)對并發(fā)事務(wù)中并發(fā)操作的調(diào)度是隨機(jī)的，而不同的調(diào)度可能會產(chǎn)生不同的結(jié)果，那么哪個結(jié)果是正確的，哪個是不正確的呢？

如果一個事務(wù)運(yùn)行過程中沒有其他事務(wù)同時運(yùn)行，也就是說它沒有受到其他事務(wù)的干擾，那么就可以認(rèn)為該事務(wù)的運(yùn)行結(jié)果是正常的或者預(yù)想的。因此將所有事務(wù)串行起來的調(diào)度策略一定是正確的調(diào)度策略。雖然以不同的順序串行執(zhí)行事務(wù)可能會產(chǎn)生不同的結(jié)果，但由于不會將數(shù)據(jù)庫置于不一致狀態(tài)，所以都是正確的。

定義 多個事務(wù)的并發(fā)執(zhí)行是正確的，當(dāng)且僅當(dāng)其結(jié)果與按某一次序串行地執(zhí)行它們時的結(jié)果相同，我們稱這種調(diào)度策略為可串行化（Serializable）的調(diào)度。

可串行性（Serializability）是并發(fā)事務(wù)正確性的準(zhǔn)則。按這個準(zhǔn)則規(guī)定，一個給定的并發(fā)調(diào)度，當(dāng)且僅當(dāng)它是可串行化的，才認(rèn)為是正確調(diào)度。

例如，現(xiàn)在有兩個事務(wù)，分別包含下列操作：

事務(wù)T1：讀B；A=B+1；寫回A；

事務(wù)T2：讀A；B=A+1；寫回B；

假設(shè)A，B的初值均為2。按T1→T2次序執(zhí)行結(jié)果為A=3，B=4；按T2→T1次序執(zhí)行結(jié)果為B=3，A=4。

數(shù)據(jù)庫是一個共享資源，可以提供多個用戶使用。這些用戶程序可以一個一個地串行執(zhí)行，每個時刻只有一個用戶程序運(yùn)行，執(zhí)行對數(shù)據(jù)庫的存取，其他用戶程序必須等到這個用戶程序結(jié)束以后方能對數(shù)據(jù)庫存取。但是如果一個用戶程序涉及大量數(shù)據(jù)的輸入/輸出交換，則數(shù)據(jù)庫系統(tǒng)的大部分時間處于閑置狀態(tài)。因此，為了充分利用數(shù)據(jù)庫資源，發(fā)揮數(shù)據(jù)庫共享資源的特點(diǎn)，應(yīng)該允許多個用戶并行地存取數(shù)據(jù)庫。但這樣就會產(chǎn)生多個用戶程序并發(fā)存取同一數(shù)據(jù)的情況，若對并發(fā)操作不加控制就可能會存取和存儲不正確的數(shù)據(jù)，破壞數(shù)據(jù)庫的一致性，所以數(shù)據(jù)庫管理系統(tǒng)必須提供并發(fā)控制機(jī)制。

一致性要求事務(wù)執(zhí)行完成后，將數(shù)據(jù)庫從一個一致狀態(tài)轉(zhuǎn)變到另一個一致狀態(tài)。它是一種以一致性規(guī)則為基礎(chǔ)的邏輯屬性，例如在轉(zhuǎn)賬的操作中，各賬戶金額必須平衡，這一條規(guī)則對于程序員而言是一個強(qiáng)制的規(guī)定，由此可見，一致性與原子性是密切相關(guān)的。

如果沒有鎖定且多個用戶同時訪問一個數(shù)據(jù)庫，則當(dāng)他們的事務(wù)同時使用相同的數(shù)據(jù)時可能會發(fā)生問題，導(dǎo)致數(shù)據(jù)庫中的數(shù)據(jù)的不一致性。一個最常見的并發(fā)操作的例子是火車/飛機(jī)訂票系統(tǒng)中的訂票操作。例如，在該系統(tǒng)中的一個活動序列：

（1）甲售票員讀出某航班的機(jī)票張數(shù)余額A，設(shè)A=16；

（2）乙售票員讀出同一航班的機(jī)票張數(shù)余額A，也是16；

（3）甲售票員賣出一張機(jī)票，修改機(jī)票張數(shù)余額A=A-1=15，把A寫回?cái)?shù)據(jù)庫；

（4）乙售票員也賣出一張機(jī)票，修改機(jī)票張數(shù)余額A=A-1=15，把A寫回?cái)?shù)據(jù)庫。

結(jié)果明明賣出兩張機(jī)票，數(shù)據(jù)庫中機(jī)票余額只減少1。

這種情況稱為數(shù)據(jù)庫的不一致性。這種不一致性是由甲、乙兩個售票員并發(fā)操作引起的。在并發(fā)操作情況下，對甲、乙兩個事務(wù)操作序列的調(diào)度是隨機(jī)的。若按上面的調(diào)度序列行，甲事務(wù)的修改就被丟失。這是由于第4步中乙事務(wù)修改A并寫回覆蓋了甲事務(wù)的修改。

當(dāng)兩個或多個事務(wù)選擇同一數(shù)據(jù)，并且基于最初選定的值更新該數(shù)據(jù)時，會發(fā)生丟失更新問題。每個事務(wù)都不知道其它事務(wù)的存在。最后的更新將重寫由其它事務(wù)所做的更新，這將導(dǎo)致數(shù)據(jù)丟失。上面預(yù)定飛機(jī)票的例子就屬于這種并發(fā)問題。事務(wù)1與事務(wù)2先后讀入同一數(shù)據(jù)A=16，事務(wù)1執(zhí)行A-1，并將結(jié)果A=15寫回，事務(wù)2執(zhí)行A-1，并將結(jié)果A=15寫回。事務(wù)2提交的結(jié)果覆蓋了事務(wù)1對數(shù)據(jù)庫的修改，從而使事務(wù)1對數(shù)據(jù)庫的修改丟失了。

封鎖粒度與系統(tǒng)的并發(fā)度和并發(fā)控制的開銷密切相關(guān)。封鎖的粒度越大，系統(tǒng)中能夠被封鎖的對象就越小，并發(fā)度也就越小，但同時系統(tǒng)開銷也越小；相反，封鎖的粒度越小，并發(fā)度越高，但系統(tǒng)開銷也就越大。

因此，如果在一個系統(tǒng)中同時存在不同大小的封鎖單元供不同的事務(wù)選擇使用是比較理想的。而選擇封鎖粒度時必須同時考慮封鎖機(jī)構(gòu)和并發(fā)度兩個因素，對系統(tǒng)開銷與并發(fā)度進(jìn)行權(quán)衡，以求得最優(yōu)的效果。一般說來，需要處理大量元組的用戶事務(wù)可以以關(guān)系為封鎖單元；需要處理多個關(guān)系的大量元組的用戶事務(wù)可以以數(shù)據(jù)庫為封鎖單位；而對于一個處理少量元組的用戶事務(wù)，可以以元組為封鎖單位以提高并發(fā)度。

封鎖的目的是為了保證能夠正確地調(diào)度并發(fā)操作。為此，在運(yùn)用X鎖和S鎖這兩種基本封鎖，對一定粒度的數(shù)據(jù)對象加鎖時，還需要約定一些規(guī)則，例如，應(yīng)何時申請X鎖或S鎖、持鎖時間、何時釋放等。我們稱這些規(guī)則為封鎖協(xié)議（locking protocol）。對封鎖方式規(guī)定不同的規(guī)則，就形成了各種不同的封鎖協(xié)議，它們分別在不同的程度上為并發(fā)操作的正確調(diào)度提供一定的保證。本節(jié)介紹保證數(shù)據(jù)一致性的三級封鎖協(xié)議和保證并行調(diào)度可串行性的兩段鎖協(xié)議，下一節(jié)將介紹避免死鎖的封鎖協(xié)議。

并發(fā)操作的不正確調(diào)度可能會帶來四種數(shù)據(jù)不一致性：丟失或覆蓋更新、臟讀、不可重復(fù)讀和幻想讀。三級封鎖協(xié)議分別在不同程度上解決了這一問題。

參考文獻(xiàn)：

[1]《數(shù)據(jù)庫系統(tǒng)概論》（第三版）（第三篇 系統(tǒng)篇 第八章 并發(fā)控制） 作者：薩師煊 王珊.

[2]高等教育出版社 2000年2月第三版.

（作者單位：大慶職業(yè)學(xué)院計(jì)算機(jī)系）