第五章

事務處理、并發控制與故障恢復技術5.1事務處理35.1事務處理5.1.1事務5.1.2事務的性質5.1.3事務活動5.1.4有關事務的語句5.1.5事務的組成45.1.1事務事務（transaction）由某個用戶所執行的一個不能被打斷的對數據庫的操作序列被稱為‘事務’‘事務’是應用程序訪問數據庫的基本邏輯工作單位‘事務’通常由一組對于數據庫的訪問操作組成，在執行過程中按照預定的次序順序執行一個‘事務’的執行過程是串行的，它將數據庫從一個舊的一致性狀態轉換到一個新的一致性狀態。在‘事務’的執行過程中，數據庫中的數據可能有不一致的現象，但在‘事務’執行結束時，系統將保證數據庫中數據的一致性55.1.1事務[例]銀行的轉帳業務：根據輸入的兩個銀行存款帳號A和B，以及轉帳金額X，將帳號A的金額減去X，帳號B的金額增加X。其處理過程如下(其中READ(A)表示將帳號A的金額讀入內存變量A，WRITE(A)表示將內存變量A的值作為帳號A的金額寫入數據庫)：READ(A);IF(A>=X)THENBEGINA:=A–X;WRITE(A);READ(B);B:=B+X;WRITE(B);END

該事務的DB訪問操作為：READ(A);WRITE(A);READ(B);WRITE(B);對該事務而言，數據庫中數據的一致性就是指：帳號A和帳號B的總金額之和不變65.1.2事務的性質

事務具有四個特性，簡稱為事務的ACID

特性，也被稱為事務的執行過程必須滿足的四條準則原子性（Atomicity）一致性（Consistency）隔離性（Isolation）持久性（Durability）75.1.2事務的性質原子性（Atomicity）在一個事務中，所有的數據庫訪問操作構成一個不可分割的操作序列，這些操作要么全部執行結束，要么一個都不要執行。(例：銀行轉帳）數據庫管理系統會自動維護用戶事務執行的原子性事務管理子系統事務日志85.1.2事務的性質2．一致性（Consistency）一個事務的成功執行總是將數據庫從一個一致的狀態轉換到另一個一致的狀態數據庫的‘狀態’：指數據庫中所有數據對象的當前取值情況數據庫的一致的狀態可以理解為數據庫中所有數據的正確性，它要求數據庫中的數據必須滿足：在數據庫中顯式定義的各種完整性約束用戶心目中的隱式數據約束95.1.2事務的性質2．一致性（續）事務執行的‘一致性’原則基于這樣一個假設：在一個事務開始執行之前數據庫處于一個一致的狀態，如果沒有‘其它事務的干擾和系統故障’，那么當該事務執行結束時數據庫仍然處于一致的狀態事務的‘一致性’特性由兩方面完成DBMS中的‘數據完整性保護’子系統編寫事務的應用程序員105.1.2事務的性質3．隔離性（Isolation）一個事務的執行與并發執行的其它事務之間是相互獨立的，互不干擾，這被稱為事務執行的‘隔離性’事務執行的‘隔離性’要求：多個事務并發執行的最終結果，應該與它們的某種串行執行的最終結果相等，這被稱為并發事務的可串行化115.1.2事務的性質3．隔離性（續）事務執行的‘隔離性’是由DBMS的并發控制子系統來實現的。在數據庫系統中，當多個事務并發執行時，每個事務都可以看成只有自己在執行，只有當它與其它事務發生封鎖沖突時，才會感覺到其它事務的存在例如：12306聯網售票系統125.1.2事務的性質4．持久性（Durability）一個事務一旦完成其全部操作后，它對數據庫的所有更新應永久地反映在數據庫中，即使以后系統發生故障也應該能夠通過故障恢復來保留這個事務的執行結果事務的‘持久性’是由DBMS的恢復管理子系統實現的數據庫管理系統通過其‘事務管理’子系統（含‘并發控制’子系統）、‘恢復管理’子系統、‘數據完整性保護’子系統來實現事務的原子性(A)、一致性(C)、隔離性(I)和持久性(D)135.1.3事務活動事務開始事務執行正常結束提交Read/Write回滾非正常結束圖5.1

事務活動過程圖145.1.3事務活動為了精確地描述一個事務的工作過程，我們建立了一個抽象的事務模型，以表示事務的狀態變遷情況Read/Write

活

動

Begin

失

敗

Abort

Abort

提

交

Commit

異常中止

Rollback

事務執行結束

重新啟動該事務事務的狀態變遷圖預

提

交

End

155.1.3事務活動‘活動’狀態事務在開始執行后，立即進入’活動’狀態。在’活動’狀態中，事務將執行對數據庫的訪問操作在DBMS的事務管理子系統看來，用戶事務對數據庫的訪問操作就是對數據庫中數據的讀/寫操作165.1.3事務活動(cont.)‘讀’操作將數據讀入用戶事務的私有工作區間如果該數據當前不在DBMS的系統緩沖區中，那么DBMS首先將該數據從磁盤讀入系統緩沖區，然后再將其拷貝到用戶事務的私有工作區‘寫’操作將修改后的數據‘寫入’數據庫這里的‘寫’操作并不是立即將數據永久性地寫入磁盤，很可能暫時存放在DBMS的系統緩沖區中175.1.3事務活動‘預提交’狀態當事務的最后一條訪問語句執行結束之后，事務進入‘預提交’狀態。此時事務對于數據庫的訪問操作雖然已經執行結束，但其對于數據的修改結果可能還在內存的系統緩沖區中，必須將其真正寫入數據庫的磁盤185.1.3事務活動(cont.)事務在‘預提交’階段，必須確保將當前事務的所有修改操作的執行結果被真正寫入到數據庫的磁盤中去在所有‘寫’磁盤操作執行結束后，事務就進入‘提交’狀態在‘預提交’階段，雖然事務本身的操作命令已經執行結束，但是在寫磁盤的過程中仍然會發生系統故障，從而導致當前事務的執行失敗在‘預提交’失敗后，當前事務也將被放棄(abort)，事務轉而進入‘失敗’狀態195.1.3事務活動‘失敗’狀態處于’活動’狀態的事務在順利到達并執行完最后一條語句之前就中止執行，或者在’預提交’狀態下因發生系統故障而中止執行時，我們稱事務進入’失敗’狀態事務從’活動’狀態轉變為’失敗’狀態的原因應用程序(或用戶)主動放棄(abort)當前事務因并發控制的原因而被放棄的事務，如：封鎖申請的超時等待死鎖發生系統故障事務從’預提交’狀態轉變為’失敗’狀態的原因發生系統故障205.1.3事務活動‘異常中止’狀態處于’失敗’狀態的事務，很可能已對磁盤中的數據進行了一部分修改。為了保證事務的原子性，系統應該撤消(undo操作)該事務對數據庫已作的修改。在撤消操作完成以后，事務將被打上一個放棄的標志(aborted)，轉而進入’異常中止’狀態回退(rollback)對事務的撤消操作也稱為事務的’回退’或’回滾’事務的’回退’由DBMS的’恢復子系統’實現在事務進入’異常中止’狀態后，系統有兩種選擇：作為一個新的事務，重新啟動取消事務215.1.3事務活動‘提交’狀態事務進入’預提交’狀態后，’并發控制子系統’將檢查該事務與并發執行的其它事務之間是否發生干擾現象在檢查通過以后，系統執行提交(commit)操作，把對數據庫的修改全部寫到磁盤上，并通知系統，事務已成功地結束為事務打上一個提交標志(committed)，事務就進入‘提交’狀態不論是‘提交’狀態，還是‘異常中止’狀態，都意味著一個事務的執行結束225.1.4有關事務的語句‘事務’除了由一組對于數據庫的訪問操作構成以外，通常還應該包括少量的事務控制語句，用于定義一個事務的開始和結束(包括正常結束和非正常結束)。因此，與事務有關的控制語句主要有三條：事務的開始(begintransaction)事務的結束正常結束提交事務(committransaction)非正常結束回退事務(rollbacktransaction)235.1.4有關事務的語句Begintransaction現有的關系數據庫管理系統并沒有提供一個用于定義從什么時候開始一個事務的控制語句，事務的啟動是隱式的可以通過三種方式來啟動一個新的事務：數據定義命令(DDL)將系統設為自動提交方式（打開自動提交標志）數據操縱命令(DML)245.1.4有關事務的語句事務的啟動方式數據定義命令(DDL)每一條數據定義命令都將被作為一個單獨的事務來執行在此之前的用戶事務將被提動提交將系統設為自動提交方式（打開自動提交標志）每一條數據庫訪問命令都將被作為一個單獨的事務來執行，并根據執行結果自動提交或回退數據操縱命令(DML)在當前用戶的前一個事務執行結束之后，在用戶提交的下一條數據庫訪問操作之前，數據庫管理系統將自動啟動一個新的事務255.1.4有關事務的語句Committransaction提交當前事務，事務在執行過程中對于數據庫的所有修改操作都將永久地反應到數據庫中，并且不可被取消事務的提交操作也可能失敗，其原因包括：發生系統故障在提交階段執行的數據完整性檢查在事務提交失敗后，用戶可以通過回退(Rollback)操作來取消當前事務由系統自動提交的事務，如果提交失敗，系統將自動執行事務的回退操作265.1.4有關事務的語句Rollbacktransaction取消在該事務執行過程中的所有操作，回滾該事務至事務的起點，以便重新執行或放棄（abort）該事務檢查點(savepoint)在事務的執行過程中，系統可以為該事務設置若干個檢查點用戶事務可以使用Rollback命令將當前事務回退到前面的某個檢查點sp，放棄“在檢查點sp之后，回退操作之前”執行的對數據庫的所有訪問操作，并繼續執行當前事務不帶檢查點的回退操作將結束并放棄整個事務275.1.4有關事務的語句除了上述三條事務控制語句外，數據庫管理系統通常還會提供下述幾條與事務有關的控制命令(DCL)設置事務的自動提交命令SETAUTOCOMMITON|OFF設置事務的類型SETTRANSACTIONREADONLY|READWRITE設置事務的隔離級別SETTRANSACTIONISOLATIONLEVEL READUNCOMMITTED|READCOMMITTED| READREPEATABLE|SERIALIZABLE285.1.4有關事務的語句SETTRANSACTIONREADONLY|READWRITE定義在這之后啟動的所有事務在執行過程中對數據庫的訪問方式READONLY：只讀型事務在事務的運行過程中只能執行對數據庫的‘讀’操作，而不能執行‘更新’類型的操作直到定義新的事務類型READWRITE：讀/寫型事務在事務的運行過程中可以執行對數據庫的‘讀/寫’操作這是事務的缺省類型定義295.1.4有關事務的語句SETTRANSACTIONISOLATIONLEVEL READUNCOMMITTED|READCOMMITTED| READREPEATABLE|SERIALIZABLE定義當前用戶的事務與其它并發執行事務之間的隔離級別事務的隔離級別與所采用的封鎖策略緊密相關。選擇不同的隔離級別，系統所采用的封鎖策略則不同有四種不同的隔離級別可供選擇305.1.4有關事務的語句READUNCOMMITTED：未提交讀在該方式下，當前事務不需要申請任何類型的封鎖，因而可能會‘讀’到未提交的修改結果禁止一個事務以該方式去執行對數據的‘寫’操作，以避免與其它并發事務的‘寫’沖突現象READCOMMITTED：提交讀在‘讀’數據對象A之前需要先申請對數據對象A的‘共享性’封鎖，在‘讀’操作執行結束之后立即釋放該封鎖以避免讀取到其它并發事務未提交的修改結果315.1.4有關事務的語句READREPEATABLE：可重復讀在‘讀’數據對象A之前需要先申請對數據對象A的‘共享性’封鎖，并將該封鎖維持到當前事務的結束可以避免其它的并發事務對當前事務正在使用的數據對象的修改SERIALIZABLE：可序列化(可串行化)并發事務以一種可串行化的調度策略實現其并發執行，以避免它們相互之間的干擾現象325.1.4有關事務的語句不管采用何種隔離級別，在事務‘寫’數據對象A之前需要先申請對數據對象A的‘排它性’封鎖，并將該封鎖維持到當前事務的結束。（事務的隔離級別與封鎖策略之間的關系）33三種數據不一致現象在事務的并發執行過程中，如果采用了不合理的調度方法，就會出現并發執行錯誤，破壞數據庫中數據的一致性常見的并發執行錯誤有三種：丟失修改（lostupdata）臟讀（dirtyread）不可重復讀（non-repeatableread）34例：飛機售票業務假設某個航班的剩余機票的張數保存在數據庫對象X（初始值為5）中，則出售一張該航班機票的事務的執行流程是：Read(X,t); /*t是該事務使用的內存變量*/t:=t–1;Write(X,t);35丟失修改現象：一個事務的修改結果破壞了另一個事務的修改結果原因：對多個事務并發修改同一個數據對象的情況未加控制步驟甲售票點變量t1乙售票點變量t2剩余機票X1Read(X,t1);552t1:=t1–1;43Read(X,t2);54t2:=t2–1;45Write(X,t1);46Write(X,t2);436臟讀現象：讀到了錯誤的數據(即與數據庫中的情況不相符的數據)原因：一個事務讀取了另一個事務未提交的修改結果步驟甲售票點變量t1乙售票點變量t2剩余機票X1Read(X,t1);552t1:=t1–1;43Write(X,t1);444Read(X,t2);45放棄當前的售票操作，取消對X的修改537不可重復讀現象： 在一個事務的執行過程中，前后兩次讀同一個數據對象所獲得的值出現了不一致原因： 在兩次’讀’操作之間插入了另一個事務的’寫’操作步驟甲售票點變量t1乙售票點變量t2剩余機票X1Read(X,t1);552Read(X,t2);53t2:=t2–1;44Write(X,t2);445Read(X,t1);4Example10.3.3BlindWritesT1:W1(A,50);W1(B,50);C1;T2:W2(A,80);W2(B,20);C2;H3:W1(A,50);W2(A,80);W2(B,20);W1(B,50);C1;C2;scheduleH3T1&T2T2&T1valueofA808050valueofB502050隔離級別及對應的可能或不可能出現的現象更新丟失臟讀不可重復讀幻像（phantomread）同一查詢在同一事務中多次進行，由于其他提交事務所做的插入操作，每次返回不同的結果集，此時發生幻像讀39DirtyreadNon-repeatablereadPhantomreadReadmittedPossiblePossiblePossibleReadcommittedNotpossiblePossiblePossibleRepeatablereadNotpossibleNotpossiblePossibleSerializableNotpossibleNotpossibleNotpossible405.1.5事務的組成數據對象數據對象的大小可以是一個屬性值、一個元組、一張表（元組的集合）或整個數據庫，也可以是一個磁盤塊在這里我們并不嚴格區分它們，而是簡單稱其為‘數據對象A’，或簡稱‘數據A’415.1.5事務的組成(cont.)數據對象的地址空間在用戶事務與數據庫進行數據交換時，存在三種與數據有關的地址空間概念：保存這些數據對象的磁盤空間數據庫管理系統所使用的內存緩沖區事務的局部地址空間(內存變量)同一個數據對象在不同的地方可能具有不同的值425.1.5事務的組成操作1)事務控制2)數據訪問1)事務控制操作事務的開始：STARTT0提交事務：COMMITT0回退(放棄)事物：ABORTT0435.1.5事務的組成2)數據訪問操作INPUT(A)：將數據對象A的值從磁盤中讀入內存緩沖區OUTPUT(A)：將內存緩沖區中數據對象A的值寫入磁盤READ(A,t)：將內存緩沖區中數據對象A的值讀入內存變量t在一個READ操作中，有可能隱含著一個INPUT操作WRITE(A,t)：將內存變量t的值寫入內存緩沖區中數據對象A44[例]轉帳事務(A=10000,B=20000,轉帳金額5000)5.1.5事務的組成READ(A,t);t:=t–5000;WRITE(A,t);READ(B,t);t:=t+5000;WRITE(B,t);COMMITT1;用戶事務STARTT1;READ(A,t);t:=t–5000;WRITE(A,t);READ(B,t);t:=t+5000;WRITE(B,t);OUTPUT(A);OUTPUT(B);COMMITT1;數據庫日志45[例]轉帳事務(A=10000,B=20000,轉帳金額5000)STARTT1;READ(A,t);WRITE(A,t);READ(B,t);WRITE(B,t);OUTPUT(A);OUTPUT(B);COMMITT1;5.1.5事務的組成事務的開始語句，由數據庫管理系統自動加入各自隱含一個INPUT操作將修改結果寫入數據庫緩沖進入預提交狀態，將修改結果從數據庫緩沖寫入磁盤寫磁盤結束，提交當前事務第五章事務處理、并發控制與故障恢復技術5.2并發控制技術475.2并發控制技術5.2.1事務的并發執行5.2.2封鎖5.2.3封鎖協議5.2.4兩階段封鎖協議5.2.5封鎖粒度5.2.6活鎖與死鎖485.2.1事務的并發執行并發性數據庫是一個多用戶共享系統每個用戶（或用戶程序）都是以‘事務’為單位訪問數據庫用于實現多個用戶事務的并發執行的技術被稱為并發控制(ConcurrentControl)技術495.2.1事務的并發執行多個事務的執行方式串行執行以事務為單位，多個事務依次順序執行前一個事務對數據庫的訪問操作執行結束后，再去處理下一個事務對數據庫的訪問操作并發執行按一定調度策略交替執行并發執行的可串行化(Serializability)如果一組事務并發執行的結果等價于它們之間的某種串行執行的結果，則稱其為可串行化調度并發控制的目標：實現并發事務的可串行化調度505.2.1事務的并發執行515.2.1事務的并發執行幾個概念調度(historyorschedule)串行調度(serialschedule)可串行化調度(SerializabilitySchedule)事務及其調度的表示方法沖突可串行化沖突(Conflict)優先圖沖突可串行性判斷525.2.1事務的并發執行調度一個或多個事務中的數據庫訪問操作，按照這些操作被執行的時間排序所形成的一個操作序列535.2.1事務的并發執行數據庫訪問操作用戶事務對于數據庫的訪問操作包括READ和WRITE，這是事務對數據庫緩沖區中的數據的‘讀’和‘寫’操作。(在這里我們忽略了對于磁盤的INPUT和OUTPUT操作)駐留在內存緩沖區中的同一個數據對象A，有可能同時被若干個事務‘讀’或‘寫’。我們在考慮一個‘調度’時，最關心的是這一組事務以一種什么樣的順序來‘讀/寫’內存緩沖區中的數據同一個事務的一組‘讀/寫’操作在‘調度’中的執行順序是固定不變的，但是并發事務的不同交叉執行方式就構成了不同的‘調度’545.2.1事務的并發執行串行調度如果一個調度的操作組成方式如下：首先是一個事務的所有操作，然后是另一個事務的所有操作，依此類推，則我們稱該調度是串行的，或稱為‘串行調度’每一個事務中的所有操作，都是按照其預定的順序依次執行的555.2.1事務的并發執行串行調度任何一個串行調度均具有以下性質在該調度中任意取兩個事務X和Y，如果X的某個操作在Y的某個操作之前，則X的所有操作都在Y的所有操作之前不存在不同事務之間的交叉執行現象并發事務的串行調度執行方式不會破壞數據庫狀態的一致性56調度2：T2，T1

（圖3）5.2.1事務的并發執行例1：銀行轉賬事務T1：從賬號A轉10000至賬號B事務T2

：從賬號A轉10%的款項至賬號B設帳號A與帳號B的初值都是20000，數據庫狀態的一致性要求是：A+B=40000事務T1與事務T2的串行調度如下：調度1：T1，T2

（圖2）在調度1或調度2執行結束后，數據庫的狀態是不同的，但都滿足狀態的一致性要求57調度1（初值：A=B=20000）圖2串行執行之一(結果：A=9000,B=31000)T1T2TempAB1Read(A)20000200002A:=A-100003Write(A)100004Read(B)5B:=B6Write(B)300007Read(A)8Temp:=A*0.110009A:=A-Temp10Write(A)900011Read(B)12B:=B+Temp13Write(B)3100058調度2（初值：A=B=20000）T1T2TempAB1Read(A)20000200002Temp:=A*0.120003A:=A-Temp4Write(A)180005Read(B)6B:=B+Temp7Write(B)220008Read(A)9A:=A-1000010Write(A)800011Read(B)12B:=B13Write(B)32000圖3串行執行之二(結果：A=8000,B=32000)595.2.1事務的并發執行可串行化調度每個串行調度都將保持數據庫狀態的一致性。但也存在其它的調度（非串行調度）能夠保證數據庫狀態的一致性如果一個調度對數據庫狀態的影響和某個串行調度相同，則我們稱該調度是可串行化的，或稱為‘可串行化調度’605.2.1事務的并發執行調度4（圖5）：不正確的并發調度并發調度的例子：調度3（圖4）：并發事務的可串行化調度從最后的執行結果上來看調度3等價于串行調度1，因而是一個可串行化調度調度4與調度1和調度2都不等價，因而是一個不正確的并發調度61調度3（初值：A=B=20000）T1T2xyTempAB1Read(A,x)20000-20000200002x:=x-10000100003Write(A,x)100004Read(A,y)100005Temp:=y*0.110006y:=y-Temp90007Write(A,y)90008Read(B,x)200009x:=x3000010Write(B,x)3000011Read(B,y)3000012y:=y+Temp3100013Write(B,y)31000圖4并發執行可串行化(結果：A=9000,B=31000)62調度4（初值：A=B=20000）T1T2xyTempAB1Read(A,x)20000-20000200002x:=x-10000100003Read(A,y)200004Temp:=y*0.120005y:=y-Temp180006Write(A,y)180007Read(B,y)200008Write(A,x)100009Read(B,x)2000010x:=x3000011Write(B,x)3000012y:=y+Temp2200013Write(B,y)22000圖5不正確的并發執行(結果：A=10000,B=22000)635.2.1事務的并發執行事務及調度的表示方法在事務的執行過程中，我們只關心它對數據庫中的哪些數據對象進行了讀/寫操作，并不在意每次讀/寫的值是多少，也不關心在用戶事務中對這些數據對象的值做了怎樣的處理另外，如果兩個事務對同一個數據對象進行‘寫’操作，則我們認為它們‘寫’后的值總是不相等的事務及調度的記法事務用符號T1,T2,…

表示用ri(X)表示事務Ti讀數據庫對象X用wi(X)表示事務Ti寫數據庫對象X645.2.1事務的并發執行事務及調度的表示方法（續）例1中的兩個事務可以分別表示為：事務T1：r1(A);w1(A);r1(B);w1(B);事務T2：r2(A);w2(A);r2(B);w2(B);調度1(圖2)可以表示為：r1(A);w1(A);r1(B);w1(B);r2(A);w2(A);r2(B);w2(B);該串行調度可以簡化表示為：T1,T2調度2(圖3)可以表示為：r2(A);w2(A);r2(B);w2(B);r1(A);w1(A);r1(B);w1(B);該串行調度可以簡化表示為：T2,T1655.2.1事務的并發執行事務及調度的表示方法（續）事務T1：r1(A);w1(A);r1(B);w1(B);事務T2：r2(A);w2(A);r2(B);w2(B);調度3(圖4)可以表示為：r1(A);w1(A);r2(A);w2(A);r1(B);w1(B);r2(B);w2(B);調度4(圖5)可以表示為：r1(A);r2(A);w2(A);r2(B);w1(A);r1(B);w1(B);w2(B);66T1T2xyTempAB1Read(A,x)20000-20000200002x:=x-10000100003Write(A,x)100004Read(A,y)100005Temp:=y*0.110006y:=y-Temp90007Write(A,y)90008Read(B,x)200009x:=x3000010Write(B,x)3000011Read(B,y)3000012y:=y+Temp3100013Write(B,y)31000調度3(圖4)可以表示為：r1(A);w1(A);r2(A);w2(A);r1(B);w1(B);r2(B);w2(B);67T1T2xyTempAB1Read(A,x)20000-20000200002x:=x-10000100003Read(A,y)200004Temp:=y*0.120005y:=y-Temp180006Write(A,y)180007Read(B,y)200008Write(A,x)100009Read(B,x)2000010x:=x3000011Write(B,x)3000012y:=y+Temp2200013Write(B,y)22000調度4(圖5)可以表示為：r1(A);r2(A);w2(A);r2(B);w1(A);r1(B);w1(B);w2(B);685.2.1事務的并發執行沖突可串行化沖突是指調度中的一對連續操作(op1;op2)，它們滿足如下的條件：如果交換它們兩者的執行順序，那么涉及的事務中至少有一個的行為會改變符合上述條件的一對連續的操作(op1;op2)被稱為‘沖突’69沖突的判斷假設Ti和Tj是兩個不同的事務(即i

j)，則：ri(X);rj(Y)不是沖突(即使X=Y也不會是沖突)如果X

Y，則ri(X);wj(Y)不會是沖突如果X

Y，則wi(X);rj(Y)不會是沖突如果X

Y，則wi(X);wj(Y)不會是沖突同一事務的任意兩個相鄰的操作都是沖突，如：(ri(X);wi(Y))、(wi(X);ri(Y))、(ri(X);ri(Y))等不同事務對同一數據對象的‘寫’沖突：wi(X);wj(X)不同事務對同一數據對象的‘讀-寫’沖突：

ri(X);wj(X) wi(X);rj(X)705.2.1事務的并發執行概括起來講同一事務中的任意兩個操作不可以交換它們的執行順序(是沖突)不同事務中的任何兩個操作在執行順序上是可以交換的，除非：它們涉及同一個數據對象；并且至少有一個是‘寫’操作對于初始給定的一個調度，如果通過一組‘非沖突’操作的交換，能夠將該調度轉換為一個串行調度，則我們認為最初的調度就是一個可串行化調度715.2.1事務的并發執行沖突等價如果通過一系列相鄰操作的非沖突交換能夠將一個調度轉換為另一個調度，則我們稱這兩個調度是沖突等價的沖突可串行化如果一個調度S沖突等價于一個串行調度，則我們稱調度S是“沖突可串行化”的‘沖突可串行化’是‘可串行化’的一個充分條件，而非必要條件‘沖突可串行化’調度必定也是一個’可串行化’調度一個’可串行化’調度并不一定是’沖突可串行化’的725.2.1事務的并發執行例：將調度3通過一系列非沖突交換可以轉換成一個串行調度（調度1）（事務T2中的操作被標上下劃線）步驟1(原調度3)r1(A);w1(A);r2(A);w2(A);r1(B);w1(B);r2(B);w2(B);步驟2：r1(A);w1(A);r2(A);r1(B);w2(A);w1(B);r2(B);w2(B);步驟3：r1(A);w1(A);r1(B);r2(A);w2(A);w1(B);r2(B);w2(B);步驟4：r1(A);w1(A);r1(B);r2(A);w1(B);w2(A);r2(B);w2(B);步驟5(串行調度1)r1(A);w1(A);r1(B);w1(B);r2(A);w2(A);r2(B);w2(B);T2T1735.2.1事務的并發執行優先圖思想：沖突操作反映了給定事務在沖突等價的串行調度（如果存在的話）中的執行順序定義：已知在調度S中存在兩個事務T1和T2，如果有T1的一個動作A1和T2的一個動作A2滿足：在調度S中A1在A2前A1和A2涉及數據庫中的同一數據對象，且至少有一個是‘寫’動作則我們稱T1優先于T2，記為T1

<s

T2在上述情況下，A1和A2是兩個不能交換的動作，如果存在一個沖突等價于S的串行調度，則在該串行調度中T1必在T2之前745.2.1事務的并發執行優先圖【定義】以調度S中的事務作為優先圖中的結點（事務Ti可簡記為i），如果Ti<sTj，則從結點i到結點j引一條有向邊。依此類推構成的一個有向圖被稱為調度S的事務優先圖。例：r2(A);r1(B);w2(A);r3(A);w1(B);w3(A);r2(B);w2(B)例：r2(A);r1(B);w2(A);r2(B);r3(A);w1(B);w3(A);w2(B)其優先圖是：1→2→3其優先圖是：

1→2→3755.2.1事務的并發執行沖突可串行化的判斷規則構造調度S的事務優先圖，如果該圖是無環的，則調度S是沖突可串行化的。如果有環，則調度S不是沖突可串行化的例：r2(A);r1(B);w2(A);r3(A);w1(B);w3(A);r2(B);w2(B)例：r2(A);r1(B);w2(A);r2(B);r3(A);w1(B);w3(A);w2(B)其優先圖是：

1→2→3（存在環狀結構），因此該調度不是沖突可串行化的其優先圖是：1→2→3（無環），因此該調度是沖突可串行化的76[結論1]如果在優先圖中存在環，則該調度不是沖突可串行化的。證明（反證法）：設有一個由T1,T2,…,Tn等n個事務構成的調度H，其優先圖中存在一個涉及這n個事務的環狀結構：T1→T2→…→Tn→T1。假設存在一個與調度H沖突等價的串行調度S∵在優先圖中T1優先于T2的前提條件是存在T1的一個動作A1和T2的一個動作A2，在調度H中A1先于A2，且A1與A2不可交換（沖突）∴在調度S中，A1也應先于A2。即在串行調度S中T1應該先于T2執行。依此類推：T1先于T2，T2先于T3，…，Tn-1先于Tn，Tn先于T1∴得到一對矛盾的關系：T1先于Tn，Tn先于T1∴假設不成立，不可能存在一個與調度H沖突等價的串行調度，即不是沖突可串行化的77[結論2]如果調度S的優先圖中無環，則調度S是沖突可串行化的。證明(歸納法)設由n個事務T1,T2,……,Tn構成一個調度Hn當n=1時，調度H1只有一個事務組成，因此H1是一個串行調度，因而也是沖突可串行化的假設n=(k-1)時結論成立，即：如果存在一個由(k-1)個事務T1,T2,……,Tk-1所構成的調度Hk-1，其事務優先圖是無環的，則調度Hk-1是沖突可串行化的，即調度Hk-1沖突等價于它們的某個串行調度Sk-1當n=k時，如果由k個事務T1,T2,……,Tk所構成的調度Hk的事務優先圖G是無環的，則有如下結論：∵優先圖G是一個有向無環圖∴在圖G中至少存在一個結點i(事務Ti所對應的結點)，不存在指向該結點的有向邊∴在調度Hk中不存在這樣一個動作A：是Ti之外的某個事務Tj的動作動作A位于Ti的某個動作Ai之前動作A與動作Ai是沖突∴可以通過非沖突動作的交換將事務Ti的所有動作交換到調度的最前面，并保持它們的原有順序不變。即將調度Hk轉換成下述的調度Sk：(Ti的所有動作)(其它k-1個事務的動作)且調度Hk與調度Sk是沖突等價的78結論2的證明(續)79考慮調度Sk的后半部分：(Ti的所有動作)(其它k-1個事務的動作)由Ti之外的其它(k-1)個事務中的動作所構成的調度Hk-1∵調度Hk-1中的所有動作均保持了它們在調度Hk中的排列順序∴從優先圖G中去刪除結點i以及與其相關的所有有向邊，就構成了調度Hk-1的事務優先圖G’(即：圖G’是圖G的一個子圖)∵圖G是有向無環圖∴圖G’也是一個有向無環圖Hk-1結論2的證明(續)80 根據步驟2的假設：如果由(k-1)個事務所構成的調度的事務優先圖是無環的，則該調度是沖突可串行化的∴上述的調度Hk-1是沖突可串行化的，即調度Hk-1沖突等價于這(k-1)個事務的某個串行調度Sk-1∵調度Sk等于：(事務Ti的所有動作)+調度Hk-1

調度Hk-1沖突等價于某個串行調度Sk-1∴調度Sk沖突等價于一個串行調度(Ti,Sk-1)∵調度Hk沖突等價于調度Sk

調度Sk沖突等價于串行調度(Ti,Sk-1)∴調度Hk沖突等價于串行調度(Ti,Sk-1)∴調度Hk是沖突可串行化的。 證畢結論2的證明(續)815.2.1事務的并發執行三種數據不一致現象在事務的并發執行過程中，如果采用了不合理的調度方法，就會出現并發執行錯誤，破壞數據庫中數據的一致性。常見的并發執行錯誤有三種：丟失修改（lostupdata）臟讀（dirtyread）不可重復讀（non-repeatableread）825.2.1事務的并發執行例：飛機售票業務假設某個航班的剩余機票的張數保存在數據庫對象X（初始值為5）中，則出售一張該航班機票的事務的執行流程是：Read(X,t); /*t是該事務使用的內存變量*/t:=t–1;Write(X,t);83丟失修改現象：一個事務的修改結果破壞了另一個事務的修改結果原因：對多個事務并發修改同一個數據對象的情況未加控制步驟甲售票點變量t1乙售票點變量t2剩余機票X1Read(X,t1);552t1:=t1–1;43Read(X,t2);54t1:=t2–1;45Write(X,t1);46Write(X,t2);484臟讀現象：讀到了錯誤的數據(即與數據庫中的情況不相符的數據)原因：一個事務讀取了另一個事務未提交的修改結果步驟甲售票點變量t1乙售票點變量t2剩余機票X1Read(X,t1);552t1:=t1–1;43Write(X,t1);444Read(X,t2);45放棄當前的售票操作，取消對X的修改585不可重復讀現象： 在一個事務的執行過程中，前后兩次讀同一個數據對象所獲得的值出現了不一致原因： 在兩次’讀’操作之間插入了另一個事務的’寫’操作步驟甲售票點變量t1乙售票點變量t2剩余機票X1Read(X,t1);552Read(X,t2);53t2:=t2–1;44Write(X,t2);445Read(X,t1);4Example10.3.3BlindWritesT1:W1(A,50);W1(B,50);C1;T2:W2(A,80);W2(B,20);C2;H3:W1(A,50);W2(A,80);W2(B,20);W1(B,50);C1;C2;scheduleH3T1&T2T2&T1valueofA808050valueofB502050875.2.1事務的并發執行出現上述三種數據不一致現象的原因在于：多個并發執行的事務反復交叉使用同一個數據庫（數據對象），而數據庫管理系統又沒有提供必要的控制手段合理組織調度多個用戶的并發操作，避免產生數據不一致現象的工作也被稱為‘并發控制’常用的并發控制技術是：封鎖885.2并發控制技術5.2.1事務的并發執行5.2.2封鎖5.2.3封鎖協議5.2.4兩階段封鎖協議5.2.5封鎖粒度5.2.6活鎖與死鎖895.2.2封鎖主要內容封鎖（lock）封鎖類型常用的兩種類型封鎖鎖相容矩陣申請封鎖和釋放封鎖的處理過程使用封鎖技術實現并發控制的方法905.2.2封鎖封鎖（lock）使用封鎖技術的前提在一個事務訪問數據庫中的數據時，必須先獲得被訪問的數據對象上的封鎖，以保證數據訪問操作的正確性和一致性。封鎖的作用在一段時間內禁止其它事務在被封鎖的數據對象上執行某些類型的操作（由封鎖的類型決定）同時也表明：持有該封鎖的事務在被封鎖的數據對象上將要執行什么類型的操作（由系統所采用的封鎖協議來決定）‘封鎖’是多用戶環境中最常采用的一種并發控制技術915.2.2封鎖封鎖類型常用的封鎖類型有兩種排它鎖

eXclusivelock，又簡稱為：X鎖共享鎖

Sharinglock，又簡稱為：S鎖92排它鎖（X鎖）特性只有當數據對象A沒有被其它事務封鎖時，事務T才能在數據對象A上施加‘X鎖’如果事務T對數據對象A施加了’X鎖’，則其它任何事務都不能在數據對象A上再施加任何類型的封鎖作用如果一個事務T申請在數據對象A上施加‘X鎖’并得到滿足，則：事務T自身可以對數據對象A作讀、寫操作，而其它事務則被禁止訪問數據對象A這樣可以讓事務T獨占該數據對象A，從而保證了事務T對數據對象A的訪問操作的正確性和一致性缺點：降低了整個系統的并行性‘X鎖’必須維持到事務T的執行結束93共享鎖（S鎖）特性如果數據對象A沒有被其它事務封鎖，或者其它事務僅僅以‘S鎖’的方式來封鎖數據對象A時，事務T才能在數據對象A上施加‘S鎖’作用如果一個事務T申請在數據對象A上施加‘S鎖’并得到滿足，則：事務T可以對‘讀’數據對象A，但不能‘寫’數據對象A不同事務所申請的‘S鎖’可以共存于同一個數據對象A上，從而保證了多個事務可以同時‘讀’數據對象A，有利于提高整個系統的并發性在持有封鎖的事務釋放數據對象A上的所有‘S鎖’之前，任何事務都不能‘寫’數據對象A‘S鎖’不必維持到事務T的執行結束(依封鎖協議而定)94‘排它鎖’與‘共享鎖’的相互關系可以用如下圖所示的‘鎖相容矩陣’來表示合適(wellformed)事務如果一個事務在訪問數據庫中的數據對象A之前按照要求申請對A的封鎖，在操作結束后釋放A上的封鎖，這種事務被稱為合適事務‘合適事務’是保證并發事務的正確執行的基本條件當前事務申請的鎖其它事務已持有的鎖YesYesNoS鎖YesNoNoX鎖-S鎖X鎖圖5.8

封鎖的相容矩陣955.2.2封鎖封鎖的申請與釋放封鎖管理器的數據結構數組LOCK(A)記錄被施加在數據對象A上的封鎖類型，其值是：Read_locked（共享鎖）Write_locked（排它鎖）Unlocked（無封鎖）數組no_of_reads(A)記錄被施加在數據對象A上的共享鎖的個數96申請對數據對象A的共享鎖(S鎖)：read_lock(A)B：ifLOCK(A)=‘Unlocked'{ LOCK(A):=‘Read_locked'; no_of_reads(A):=1; }else{ ifLOCK(A)=‘Read_locked’ no_of_reads(A):=no_of_reads(A)+1; else{ wait(untilLOCK(A)!=‘Write_locked' andthelockmanagerwakesup thetransaction); gotoB; } }97申請對數據對象A的排它鎖(X鎖)：write_lock(A)B： ifLOCK(A)=‘Unlocked’ { LOCK(A):=‘Write_locked'; } else { wait(untilLOCK(A)=‘Unlocked‘andthelock managerwakesupthetransaction); gotoB; }98釋放對數據對象A的封鎖：unlock(A)ifLOCK(A)=‘Write_locked’{ LOCK(A):=‘Unlocked'; wakeuponeofthewaitingtransaction,ifany}elseifLOCK(A)=‘Read_locked'{ no_of_reads(A):=no_of_reads(A)-1; ifno_of_reads(A)=0{ LOCK(A):=‘Unlocked' wakeuponeofthewaitingtransaction,ifany }}995.2.2封鎖使用封鎖的并發控制技術在DBMS的‘封鎖管理器’中維護著一張‘鎖表’，以記錄當前：封鎖的持有情況有哪些‘事務’在哪些‘數據對象’上持有什么類型的‘封鎖’封鎖的申請情況有哪些‘事務’正在申請哪些‘數據對象’上的什么類型的‘封鎖’DBMS對于用戶事務的數據訪問操作Op(A)的處理過程如下：100事務的數據訪問操作的處理過程將訪問操作Op(A)發送給并發控制子系統的‘調度器’‘調度器’根據系統采用的封鎖協議來決定：是否需要為該操作申請封鎖申請何種類型的封鎖 并將封鎖申請發送給‘封鎖管理器’‘封鎖管理器’根據鎖表中記載的情況來決定是否能夠立即滿足該封鎖申請，并將申請結果返回給‘調度器’如果封鎖申請得不到滿足，則‘調度器’將訪問操作Op(A)放入‘被推遲的訪問操作’隊列，否則將該操作發送給系統的執行引擎執行101事務的數據訪問操作的處理過程（圖）1025.2并發控制技術5.2.1事務的并發執行5.2.2封鎖5.2.3封鎖協議5.2.4兩階段封鎖協議5.2.5封鎖粒度5.2.6活鎖與死鎖1035.2.3封鎖協議采用‘封鎖’技術為并發事務的正確執行提供了可能性。但是要真正確保事務并發執行的正確性，還必須按照規定的方法來使用‘封鎖’技術，即規定事務使用‘封鎖’的方式。包括：何時申請封鎖？申請何種類型的封鎖？(S鎖/X鎖)何時釋放所持有的封鎖？1045.2.3封鎖協議封鎖協議（lockingprotocol）不同的封鎖方式構成了不同的封鎖規則，我們稱之為‘封鎖協議’三級封鎖協議不同級別的封鎖協議可以防止不同的并發錯誤兩階段封鎖協議105一級封鎖協議事務T在‘寫’數據對象A之前，必須先申請并獲得A上的‘X鎖’，并維持到事務T的執行結束(包括Commit與Rollback)才釋放被加在A上的‘X鎖’二級封鎖協議‘一級封鎖協議’的要求；并且事務T在’讀’數據對象A之前，必須先申請并獲得A上的’S鎖’，在’讀’操作完成后即可釋放A上的’S鎖’這里沒有規定釋放‘S鎖’的時間三級封鎖協議‘一級封鎖協議’的要求；并且事務T在‘讀’數據對象A之前，必須先申請并獲得A上的‘S鎖’，并維持到事務T的執行結束(包括Commit與Rollback)才釋放被加在A上的‘S鎖’106‘一級封鎖協議’可防止‘丟失修改’現象步驟甲售票點乙售票點剩余機票X1write_lock(X);52Read(X,t1);3write_lock(X);4t1:=t1–1;wait……5Write(X,t1);wait……46Commit;wait……7unlock(X);wait……8Read(X,t2);9t1:=t2–1;10Write(X,t2);311Commit;12unlock(X);107‘二級封鎖協議’可防止‘丟失修改、臟讀’現象步驟甲售票點變量t1乙售票點變量t2剩余機票X1write_lock(X);52Read(X,t1);53t1:=t1–1;44Write(X,t1);45read_lock(X);6wait……7Rollbackwait……58unlock(X);wait……9Read(X,t1);5……108‘三級封鎖協議’可防止‘丟失修改、臟讀、不可重復讀’現象步驟甲售票點變量t1乙售票點變量t2剩余機票X1read_lock(X);52Read(X,t1);53write_lock(X);4……wait……5Read(X,t1);5wait……6Commit;wait……7unlock(X);wait……8Read(X,t2);59……109‘三級封鎖協議’與三種數據不一致現象的關系可能出現的數據不一致現象丟失修改臟讀不可重復讀封鎖協議一級封鎖協議NoYesYes二級封鎖協議NoNoYes三級封鎖協議NoNoNo110根據對于封鎖協議的介紹我們可以得知，多個事務的并發運行之所以會破壞數據庫狀態的一致性，其原因是：事務沒有為被訪問的數據對象申請封鎖事務沒有在合適的時候釋放所持有的鎖‘三級封鎖協議’正是為解決上述問題而定義的封鎖規則1115.2并發控制技術5.2.1事務的并發執行5.2.2封鎖5.2.3封鎖協議5.2.4兩階段封鎖協議5.2.5封鎖粒度5.2.6活鎖與死鎖1125.2.4兩階段封鎖協議按照‘三級封鎖協議’的規定，事務T在其執行過程中所申請的所有‘鎖’必須在事務T結束后才能釋放。這就意味著，在一個事務執行過程中，必須把鎖的申請與釋放分為兩個階段：第一個階段：申請并獲得封鎖在此階段中，事務可以申請其整個執行過程中所需要的鎖，此階段也可稱為‘擴展階段’第二階段：釋放所有申請獲得的鎖此階段也可稱為‘收縮階段’事務一旦開始釋放封鎖，那么就不能再申請任何封鎖此種設置封鎖的方法稱為‘兩階段封鎖協議’two-phaselockingprotocol，簡稱2PL協議1135.2.4兩階段封鎖協議兩階段封鎖事務在一個事務T中，如果所有的封鎖請求都先于所有的解鎖請求，則該事務被稱為‘兩階段封鎖事務’，簡稱‘2PL事務’或者說：采用兩階段封鎖協議的事務1145.2.4兩階段封鎖協議2PL事務的例子(圖5.12)事務T：sl(A);sl(B);sl(C);……;u(B);u(A);u(C);用sl(A)表示申請對A的‘S鎖’，用xl(A)表示申請對A的‘X鎖’，用u(A)表示釋放A上的封鎖不遵守2PL協議的例子(圖5.13)事務T’：sl(A);u(A);sl(B);xl(C);……;u(C);u(B)擴展階段收縮階段1155.2.4兩階段封鎖協議基于前述的‘三級封鎖協議’和‘兩階段封鎖協議’的要求，我們歸納出有關封鎖技術的使用規定假設系統采用‘X鎖’和‘S鎖’兩種類型鎖，有關封鎖的申請與釋放操作表示如下：sli(A)：事務Ti申請數據對象A上的一個‘S鎖’xli(A)：事務Ti申請數據對象A上的一個‘X鎖’也可以用li(A)表示事務Ti申請數據對象A上的鎖ui(A)：事務Ti釋放自己在數據對象A上所持有的鎖116封鎖的使用規定在每一個事務Ti中第1點：采用如下的封鎖協議：讀動作ri(A)之前必須有sli(A)或xli(A)，而且在兩者之間沒有ui(A)寫動作wi(A)之前必須有xli(A)，而且在兩者之間沒有ui(A)每一個sli(A)或xli(A)之后必須有一個ui(A)第2點：必須遵循‘兩階段封鎖協議’在任何sli(A)或xli(A)之前不能有ui(B)A和B可以是同一個數據對象117封鎖的使用規定（續）如果事務Ti

在執行過程中重復申請同一個數據對象A上的鎖，‘封鎖管理器’的處理方法如下：如果Ti已經持有數據對象A上的鎖，則對sli(A)不作任何處理如果Ti已經持有數據對象A上的‘S鎖’，在處理xli(A)請求時，僅僅將Ti所持有的‘S鎖’改為‘X鎖’僅當只有事務Ti持有數據對象A上的‘S鎖’時，封鎖管理器才能將Ti所持有的‘S鎖’改為‘X鎖’如果Ti已經持有數據對象A上的‘X鎖’，則對xli(A)不作任何處理118封鎖的使用規定（續）上述的處理過程確保一個事務在一個數據對象上只能持有一把‘鎖’如果事務Ti在執行過程中在同一個數據對象A上執行了若干次鎖申請操作：li1(A);li2(A);…;lin(A)

并且在li1(A)和lin(A)之間沒有ui(A)，則在lin(A)之后必須有且僅有一個ui(A)封鎖的重復申請過程只能是：sli(A);……;xli(A);119封鎖的使用規定（續）第3點：保證事務調度的合法性對任意兩個不同的事務Ti和Tj，其調度必須滿足：如果xli(A)出現在調度中，那么后面不能再有slj(A)或xlj(A)，除非中間插入了ui(A)如果sli(A)出現在調度中，那么后面不能再有xlj(A)，除非中間插入了ui(A)如果一個調度以及它的每個事務都滿足上述三個方面的要求，我們稱該調度是一個‘合法調度’我們可以將前述的‘調度器’和‘封鎖管理器’合并為一個‘封鎖調度器’，DBMS正是通過‘封鎖調度器’來產生若干個并發運行事務之間的一個‘合法調度’的120封鎖的使用規定（續）T1T2xyTempAB1Read(A,x)20000-20000200002x:=x-10000100003Read(A,y)200004Temp:=y*0.120005y:=y-Temp180006Write(A,y)180007Read(B,y)200008Write(A,x)100009Read(B,x)2000010x:=x3000011Write(B,x)3000012y:=y+Temp2200013Write(B,y)22000圖5不正確的并發執行(結果：A=10000,B=22000)121封鎖的使用規定（續）圖5所示的兩個轉帳事務T1和T2的執行流程如下(只保留了對于數據庫的訪問操作)：r1(A);r2(A);

w2(A);r2(B);w1(A);r1(B);w1(B);w2(B);該操作執行流程被發送給’封鎖調度器’時，‘封鎖調度器’將首先根據前面介紹的‘封鎖協議’和‘2PL事務’的要求插入相應的封鎖申請和釋放操作，其流程如下：xl1(A);r1(A);xl2(A);r2(A);w2(A);xl2(B);r2(B);w1(A);xl1(B);r1(B);w1(B);u1(A);u1(B);w2(B);u2(A);u2(B);122封鎖的使用規定（續）xl1(A);r1(A);

xl2(A);r2(A);w2(A);xl2(B);r2(B);

w1(A);xl1(B);r1(B);w1(B);u1(A);u1(B);

w2(B);u2(A);u2(B);在上述（預想）執行流程中，’封鎖調度器’在處理事務T2的xl2(A)

請求時，因封鎖申請得不到滿足而將事務T2及其所有的后續操作請求推遲，真正的操作執行流程是(下面的xl(A)是申請并獲得A上的‘X鎖’的時間

)xl1(A);r1(A);w1(A);xl1(B);r1(B);w1(B);u1(A);u1(B);xl2(A);r2(A);w2(A);xl2(B);r2(B);w2(B);u2(A);u2(B);最終產生的是T1和T2之間的一個串行調度1235.2.4兩階段封鎖協議定理:由2PL事務所構成的任意合法調度S都是沖突可串行化的證明：當調度S僅由一個事務組成時，調度S是沖突可串行化的假設：由(n-1)個2PL事務所構成的任意一個合法調度都是沖突可串行化的設調度S涉及n個2PL事務：T1,T2,……,Tn，并且Ti是調度S中第一個有解鎖動作的事務，則我們可以得到以下結論：

可以將Ti的所有動作不經過任何沖突而移動到調度S的最前面124定理證明（續）設在Ti中有一個動作wi(A)(或ri(A))，如果調度S在該動作的前面有一個與之沖突的動作wj(A)(i

j)，那么調度S的情況必是：…;wj(A);…;u