淺析計算機系統中并發調度的可串行性

【摘 要】 計算機系統對并發事務中并發操作的調度是隨機的，而不同的調度可能會產生不同的結果。

【關鍵詞】 并發事務 并發控制 可串行性

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

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

計算機系統對并發事務中并發操作的調度是隨機的，而不同的調度可能會產生不同的結果，那么哪個結果是正確的，哪個是不正確的呢？

如果一個事務運行過程中沒有其他事務同時運行，也就是說它沒有受到其他事務的干擾，那么就可以認為該事務的運行結果是正常的或者預想的。因此將所有事務串行起來的調度策略一定是正確的調度策略。雖然以不同的順序串行執行事務可能會產生不同的結果，但由于不會將數據庫置于不一致狀態，所以都是正確的。

定義 多個事務的并發執行是正確的，當且僅當其結果與按某一次序串行地執行它們時的結果相同，我們稱這種調度策略為可串行化（Serializable）的調度。

可串行性（Serializability）是并發事務正確性的準則。按這個準則規定，一個給定的并發調度，當且僅當它是可串行化的，才認為是正確調度。

例如，現在有兩個事務，分別包含下列操作：

事務T1：讀B；A=B+1；寫回A；

事務T2：讀A；B=A+1；寫回B；

假設A，B的初值均為2。按T1→T2次序執行結果為A=3，B=4；按T2→T1次序執行結果為B=3，A=4。

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

一致性要求事務執行完成后，將數據庫從一個一致狀態轉變到另一個一致狀態。它是一種以一致性規則為基礎的邏輯屬性，例如在轉賬的操作中，各賬戶金額必須平衡，這一條規則對于程序員而言是一個強制的規定，由此可見，一致性與原子性是密切相關的。

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

（1）甲售票員讀出某航班的機票張數余額A，設A=16；

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

（3）甲售票員賣出一張機票，修改機票張數余額A=A-1=15，把A寫回數據庫；

（4）乙售票員也賣出一張機票，修改機票張數余額A=A-1=15，把A寫回數據庫。

結果明明賣出兩張機票，數據庫中機票余額只減少1。

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

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

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

因此，如果在一個系統中同時存在不同大小的封鎖單元供不同的事務選擇使用是比較理想的。而選擇封鎖粒度時必須同時考慮封鎖機構和并發度兩個因素，對系統開銷與并發度進行權衡，以求得最優的效果。一般說來，需要處理大量元組的用戶事務可以以關系為封鎖單元；需要處理多個關系的大量元組的用戶事務可以以數據庫為封鎖單位；而對于一個處理少量元組的用戶事務，可以以元組為封鎖單位以提高并發度。

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

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

參考文獻：

[1]《數據庫系統概論》（第三版）（第三篇 系統篇 第八章 并發控制） 作者：薩師煊 王珊.

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

（作者單位：大慶職業學院計算機系）