Quản Lý Dữ Liệu - Cơ Sở Dữ Liệu phần 7

Chia sẻ: Qwdqwgferhrt Verbnrtjheth | Ngày: | Loại File: PDF | Số trang:12

Thêm vào BST

Báo xấu

68
lượt xem 9
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tham khảo tài liệu 'quản lý dữ liệu - cơ sở dữ liệu phần 7', công nghệ thông tin, cơ sở dữ liệu phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Quản Lý Dữ Liệu - Cơ Sở Dữ Liệu phần 7

71 Bài gi ng tóm t t H qu n tr cơ s d li u nh ng ho t ng nào c a các giao d ch tác ng l n nhau. Vì lý do này, ta s không gi i thích ki u ho t ng mà m t giao d ch có th th c hi n trên m t m c d li u. Thay vào ó, ta ch xét hai ho t ng: Read và Write. Ta cũng gi thi t r ng gi a m t ch th Read(Q) và m t ch th Write(Q) trên m t m c d li u Q, m t giao d ch có th th c hi n m t dãy tuỳ ý các ho t ng trên b n sao c a Q ư c lưu trú trong buffer c c b c a giao d ch. Vì v y ta s ch nêu các ch th Read và Write trong th i l ch, n u bi u di n v i quy ư c như v y c a th i l ch 3 s là: T1 T2 Read(A); Write(A); Read(A); Write(A); Read(B); Write(B); Read(B); Write(B); Tu n t xung t (Conflict Serializability) Xét th i l ch S trong ó có hai ch th liên ti p Ii và Ij c a các giao d ch Ti , Tj tương ng (i ≠ j). N u Ii và Ij tham kh o n các m c d li u khác nhau, ta có th i ch Ii và Ij mà không làm nh hư ng n k t qu c a b t kỳ ch th nào trong th i l ch. Tuy nhiên, n u Ii và Ij tham kh o cùng m t m c d li u Q, khi ó th t c a hai bư c này có th r t quan tr ng. Do ta ang th c hi n ch các ch th Read và Write, nên ta có b n trư ng h p c n ph i xét sau: 1. Ii = Read(Q); Ij = Read(Q): Th t c a Ii và Ij không gây ra v n nào, do Ti và Tj c cùng m t giá tr Q b t k n th t gi a Ii và Ij. 2. Ii = Read(Q); Ij = Write(Q): th t th c hi n c a Ii và Ij là quan tr ng. 3. Ii = Write(Q); Ij = Read(Q): th t th c hi n c a Ii và Ij là quan tr ng. 4. Ii = Write(Q); Ij = Write(Q): C hai ch th là ho t ng Write, th t c a hai ch th này không nh hư ng n c hai giao d ch T và T . Tuy nhiên, giá tr nh n i j ư c b i ch th Read k trong S s b nh hư ng do k t qu ph thu c vào ch th Write ư c th c hi n sau cùng trong hai ch th Write này. N u không còn ch th Write nào sau Ii và Ij trong S, th t c a th t th c hi n c a Ii và Ij s nh hư ng tr c ti p n giá tr cu i c a Q trong tr ng thái CSDL k t qu (c a th i l ch S).
72 Bài gi ng tóm t t H qu n tr cơ s d li u Như v y ch trong trư ng h p c I và I là các ch th Read, th t th c hi n c a hai i j ch th này (trong S) là không gây ra v n . Ta nói Ii và Ij xung t n u các ho t ng này n m trong các giao d ch khác nhau, ti n hành trên cùng m t m c d li u và có ít nh t m t ho t ng là Write. Ví d , trong th i l ch schedule - 3: Ch th Write(A) trong T1 xung t v i Read(A) trong T2. Tuy nhiên, ch th Write(A) trong T2 không xung t v i ch th Read(B) trong T1 do các ch th này truy xu t các m c d li u khác nhau. Ii và Ij là hai ch th liên ti p trong th i l ch S. N u Ii và Ij là các ch th c a các giao d ch khác nhau và không xung t, khi ó ta có th i th t c a chúng mà không làm nh hư ng gì n k t qu x lý và như v y ta nh n ư c m t th i l ch m i S’ tương ương v i S. Ch ng h n, do ch th Write(A) c a T2 không xung t v i ch th Read(B) c a T1, ta có th i ch các ch th này ư c m t th i l ch tương ương – th i l ch 5 dư i ây T1 T2 Read(A); Write(A); Read(A); Read(B); Write(A); Write(B); Read(B); Write(B); Th i l ch 5 Ta ti p t c i ch các ch th không xung t như sau: i ch ch th Read(B) c a T1 v i ch th Read(A) c a T2 • i ch ch th Write(B) c a T1 v i ch th Write(A) c a T2 • i ch ch th Write(B) c a T1 v i ch th Read(A) c a T2 • K t qu cu i cùng c a các bư c i ch này là m t th i l ch m i (th i l ch 6 –th i l ch tu n t ) tương ương v i th i l ch ban u (th i l ch 3):
73 Bài gi ng tóm t t H qu n tr cơ s d li u T1 T2 Read(A); Write(A); Read(B); Write(B); Read(A); Write(A); Read(B); Write(B); Th i l ch 6 S tương ương này cho ta th y: b t ch p tr ng thái h th ng ban u, th i l ch-3 s sinh ra cùng tr ng thái cu i như m t th i l ch tu n t nào ó. Tương ương xung t (conflict equivalent):N u m t th i l ch S có th bi n i thành m t th i l ch S’ b i m t dãy các thao tác i ch các ch th không xung t, ta nói S và S’ là tương ương xung t. Ví d , trong các th i l ch ã ư c nêu trên, ta th y th i l ch-1 tương ương xung tv i th i l ch-3. Kh tu n t xung t (conflict serializable): M t th i l ch S là kh tu n t xung t (conflict serializable) n u nó tương ương xung t v i m t th i l ch tu n t . Ví d , th i l ch 3 là kh tu n t xung t còn th i l ch 7 dư i ây không tương ương xung t v i m t th i l ch tu n t nào do v y nó không là kh tu n t xung t: T3 T4 Read(Q); Write(Q); Write(Q); Th i l ch 7 Có th có hai th i l ch sinh ra cùng k t qu , nhưng không tương ương xung t. Ví d , giao d ch T5 chuy n 10$ t tài kho n B sang tài kho n A. Ta xét th i l ch 8 như dư i ây, th i l ch này không tương ương xung t v i th i l ch tu n t < T1, T5 > do trong th i l ch 8 ch th Write(B) c a T5 xung t v i ch th Read(B) c a T1 như v y ta không th di chuy n t t c các ch th c a T1 v trư c các ch th c a T5 b i vi c hoán i liên ti p các ch th không xung t. Tuy nhiên, các giá tr sau cùng c a tài kho n A và B sau khi th c hi n th i l ch 8 ho c sau khi th c hi n th i l ch tu n t là như nhau A là
74 Bài gi ng tóm t t H qu n tr cơ s d li u 960 và B là 2040 tương ng. Qua ví d này ta th y c n thi t ph i phân tích c s tính toán ư c th c hi n b i các giao d ch mà không ch các ho t ng Read và Write. Tuy nhiên s phân tích như v y s n ng n và ph i tr m t giá tính toán cao hơn. T1 T5 Read(A); A:=A-50; Write(A); Read(B); B:=B-10; Write(B); Read(B); B:=B+50; Write(B); Read(A); A:=A+10 Write(A); Schedule - 8 Tu n t View (View Serializability) Xét hai th i l ch S và S’, trong ó cùng m t t p h p các giao d ch tham gia vào c hai th i l ch. Các th i l ch S và S’ ư c g i là tương ương view n u ba i u ki n sau ư c th a mãn: 1. i v i m i m c d li u Q, n u giao d ch Ti c giá tr kh i u c a Q trong th i l ch S, thì giao d ch Ti ph i cũng c giá tr kh i u c a Q trong th i l ch S’. i v i m i m c d li u Q, n u giao d ch Ti th c hi n Read(Q) trong th i l ch S và 2. giá tr ó ư c s n sinh ra b i giao d ch Tj thì Ti cũng ph i c giá tr c a Q ư c sinh ra b i giao d ch Tj trong S’. i v i m i m c d li u Q, giao d ch th c hi n ho t ng Write(Q) sau cùng trong 3. th i l ch S, ph i th c hi n ho t ng Write(Q) sau cùng trong th i l ch S’. i u ki n 1 và 2 m b o m i giao d ch c cùng các giá tr trong c hai th i l ch và do v y th c hi n cùng tính toán. i u ki n 3 i c p v i các i u ki n 1 và 2 m b o c hai th i l ch cho ra k t qu là tr ng thái cu i cùng c a h th ng như nhau. Trong các ví d trư c, th i l ch-1 là không tương ương view v i th i l ch 2 do trong th i l ch-1, giá tr
75 Bài gi ng tóm t t H qu n tr cơ s d li u c a tài kho n A ư c c b i giao d ch T2 ư c sinh ra b i T1, trong khi i u này không x y ra trong th i l ch-2. Th i l ch-1 tương ương view v i th i l ch-3 vì các giá tr c a các tài kho n A và B ư c c b i T2 ư c sinh ra b i T1 trong c hai th i l ch. Quan ni m tương ương view ưa n quan ni m tu n t view. Ta nói th i l ch S là kh tu n t view (view serializable) n u nó tương ương view v i m t th i l ch tu n t . Ta xét th i l ch sau: T3 T4 T6 Read(Q); Write(Q); Write(Q); Write(Q); Th i l ch 9 Nó tương ương view v i th i l ch tu n t < T3, T4, T6 > do ch th Read(Q) c giá tr kh i u c a Q trong c hai th i l ch và T6 th c hi n Write sau cùng trong c hai th i l ch như v y th i l ch 9 kh tu n t view. M i th i l ch kh tu n t xung t là kh tu n t view, nhưng có nh ng th i l ch kh tu n t view không kh tu n t xung t (ví d th i l ch 9). Trong th i l ch 9 các giao d ch T4 và T6 th c hi n các ho t ng Write(Q) mà không th c hi n ho t ng Read(Q), Các Write d ng này ư c g i là các Write m (blind write). Các Write m xu t hi n trong b t kỳ th i l ch kh tu n t view không kh tu n t xung t. Tính kh ph c h i (Recoverability) Ta ã nghiên c u các th i l ch có th ch p nh n dư i quan i m s nh t quán c a CSDL v i gi thi t không có giao d ch nào th t b i. Ta s xét hi u qu c a th t b i giao d ch trong th c hi n tương tranh. N u giao d ch Ti th t b i vì lý do nào ó, ta c n h y b hi u qu c a giao d ch này m b o tính nguyên t c a giao d ch. Trong h th ng cho phép th c hi n tương tranh, cũng c n thi t m b o r ng b t kỳ giao d ch nào ph thu c vào Ti cũng ph i b b . th c hi n s ch c ch n này, ta c n b trí các h n ch trên ki u th i l ch ư c phép trong h th ng. Th i l ch kh ph c h i (Recoverable Schedule) Xét th i l ch 10 trong ó T9 là m t giao d ch ch th c hi n m t ch th Read(A). Gi s h th ng cho phép T9 bàn giao ngay sau khi th c hi n ch th Read(A). Như v y T9 bàn
76 Bài gi ng tóm t t H qu n tr cơ s d li u giao trư c T8. Gi s T8 th t b i trư c khi bàn giao, vì T9 ã c giá tr c a m c gi li u A ư c vi t b i T8 , ta ph i b d T9 m b o tính nguyên t giao d ch. Tuy nhiên T9 ã ư c bàn giao và không th b d ư c. Ta có tình hu ng trong ó không th khôi ph c úng sau th t b i c a T8. T8 T9 Read(A); Write(A); Read(A); Read(B) Th i l ch 10 Th i l ch 10 là m t ví d v th i l ch không ph c h i ư c và không ư c phép. H u h t các h CSDL òi h i t t c các th i l ch ph i ph c h i ư c. M t th i l ch kh ph c h i là th i l ch trong ó, i v i m i c p giao d ch Ti , Tj , n u Tj c m c d li u ư c vi t b i Ti thì ho t ng bàn giao c a Tj ph i x y ra sau ho t ng bàn giao c a Ti . Th i l ch cascadeless (Cascadeless Schedule) Ngay c khi th i l ch là kh ph c h i, ph c h i úng sau th t b i c a m t giao d ch Ti ta ph i cu n l i m t vài giao d ch. Tình hu ng như th x y ra khi các giao d ch c d li u ư c vi t b i Ti . Ta xét th i l ch 11 sau T10 T11 T12 Read(A); Read(B) Write(A); Read(A); Write(A); Read (A) Th i l ch 11 Giao d ch T10 vi t m t giá tr ư c c b i T11. Giao d ch T12 c m t giá tr ư c vi t b i T11. Gi s r ng t i i m này T10 th t b i. T10 ph i cu n l i, do T11 ph thu c vào T10 nên T11 cũng ph i cu n l i và cũng như v y v i T12. Hi n tư ng trong ó m t giao d ch th t b i kéo theo m t dãy các giao d ch ph i cu n l i ư c g i là s cu n l i hàng lo t (cascading rollback). Cu n l i hàng lo t d n n vi c hu b m t kh i lư ng công vi c áng k . Ph i h n ch các th i l ch vi c cu n l i hàng lo t không th x y ra. Các th i l ch như v y ư c g i là các th i l ch cascadeless.
77 Bài gi ng tóm t t H qu n tr cơ s d li u M t th i l ch cascadeless là m t th i l ch trong ó m i c p giao d ch Ti , Tj n u Tj c m t m c d li u ư c vi t trư c ó b i Ti, ho t ng bàn giao c a Ti ph i xu t hi n trư c ho t ng c c a Tj . M t th i l ch cascadeless là kh ph c h i. Th c thi cô l p (Implementation of Isolation) Có nhi u sơ i u khi n tương tranh có th ư c s d ng m b o các tính ch t m t th i l ch ph i có (nh m gi CSDL tr ng thái nh t quán, cho phép qu n lý các giao d ch...), ngay c khi nhi u giao d ch th c hi n tương tranh, ch các th i l ch có th ch p nh n ư c sinh ra, b t k h i u hành chia s th i gian tài nguyên như th nào gi a các giao d ch. Ví d ta xét m t sơ i u khi n tương tranh sau: m t giao d ch ư c c p m t khóa (lock) trên toàn b CSDL trư c khi nó kh i ng và tháo khóa khi nó ã bàn giao. Trong khi giao d ch này gi khóa, không giao d ch nào khác ư c c p khóa và như v y ph i ch n t n khi khóa ư c tháo. Trong cơ ch khóa, ch m t giao d ch ư c th c hi n t i m t th i i m và như v y ch th i l ch tu n t ư c sinh ra. Sơ i u khi n tương tranh này cho ra m t hi u năng tương tranh th p. Ta nói nó cung c p m t b c tương tranh th p (poor degree of concurrency). M c ích c a các sơ i u khi n tương tranh là cung c p m t b c c nh tranh cao trong khi v n m b o các th i l ch ư c sinh ra là kh tu n t xung t ho c kh tu n t view và cascadeless. 2. Thu t toán ki m tra tính kh tu n t Thu t toán ki m tra xung t tương ương (Tính kh tu n t xung t) Cho S là m t th i l ch. Ta dùng m t th nh hư ng, ư c g i là th trình t (precedence graph), bi u di n t S=(V, E). Trong ó: V là t p các nh và E là t p các cung. T p các nh V bao g m t t c các giao d ch tham gia vào th i l ch. T p các cung E bao g m t t c các cung d ng Ti → Tj sao cho m t trong các i u ki n sau ư c tho mãn: Ti th c hi n Write(Q) trư c Tj th c hi n Read(Q). (i). Ti th c hi n Read(Q) trư c khi Tj th c hi n Write(Q). (ii). Ti th c hi n Write(Q) trư c khi Tj th c hi n Write(Q). (iii). N u m t cung Ti → Tj t n t i trong th trình t , thì trong b t kỳ th i l ch tu n t S’ nào tương ương v i S, Ti ph i xu t hi n trư c Tj.
78 Bài gi ng tóm t t H qu n tr cơ s d li u Ví d : Th i l ch 1 ư c bi u di n b ng th vì t t c các ch th c a T1 ư c th c hi n trư c ch th u tiên c a T2. Th i l ch 2 ư c bi u di n b ng th vì t t c các ch th c a T2 ư c th c hi n trư c ch th u tiên c a T1. th ch a các cung T1 → T2 vì T1 th c hi n Read(A) Th i l ch 4 ư c bi u di n b ng trư c T2 th c hi n Write(A). Nó cũng ch a cung T2→ T1 vì T2 th c hi n Read(B) trư c khi T1 th c hi n Write(B): Nu th trình t i v i S có chu trình, khi ó th i l ch S không là kh tu n t xung t. Như v y bài toán ki m tra tính kh tu n t xung t c a th i l ch S ưa v bài toán ki m tra chu trình trên th trình t bi u di n c a S. Thu t toán ki m tra kh tu n t view Không có thu t toán nào hi u qu ki m tra tính kh tu n t view c a m t th i l ch. M t cách ti p c n là c i ti n thu t toán ki m tra xung t tương ương ki m tra tính kh tu n t view. Gi s S là th i l ch g m các giao d ch {T1 , T2 , ... , Tn}. Tb và Tf là hai giao d ch gi sao cho: Tb b t ngu n l nh Write(Q) i v i m i m c d li u Q ư c truy xu t trong S, Tf b t ngu n l nh Read(Q) i v i m i m c d li u Q ư c truy xu t trong S. Ta xây d ng th i l ch m i S’ t S b ng cách xen Tb b t u c a S và Tf cu i c a S. Bi u di n S’ b ng th trình t có gán nhãn trên cung ư c xây d ng d a trên các quy t c: 1. Gán nhãn 0 cho cung Ti → Tj , n u Tj c giá tr c a m c d li u Q ư c vi t b i Ti 2. Xóa t t c các cung liên quan t i các giao d ch không dùng. M t giao d ch Ti ư c g i là không dùng n u không có con ư ng nào trong th trình t d n t Ti n Tf . 3. i v i m i m c d li u Q sao cho Tj c giá tr c a Q ư c vi t (Write) b i Ti và Tk th c hi n Write(Q), Tk ≠ Tb ti n hành các bư c sau : a. N u Ti = Tb và Tj ≠ Tf, gán nhãn 0 cho cung Tj →Tk trong th trình t gán
79 Bài gi ng tóm t t H qu n tr cơ s d li u nhãn b. N u Ti ≠ Tb và Tj = Tf gán nhãn 0 cho cung Tk → Ti trong th trình t gán nhãn c. N u Ti ≠ Tb và Tj ≠ Tf gán nhãn p cho c hai cung Tk → Ti và Tj → Tk trong th trình t gán nhãn, trong ó p là m t s nguyên duy nh t > 0 mà chưa ư c s d ng trư c ó gán nhãn cung. Quy t c 3c ph n ánh r ng n u Ti vi t m c d li u ư c c b i Tj thì m t giao d ch Tk vi t cùng m c d li u này ph i ho c i trư c Ti ho c i sau Tj. Quy t c 3a và 3b là trư ng h p c bi t là k t qu c a s ki n Tb và Tf c n thi t là các giao d ch u tiên và cu i cùng tương ng. Ví d : xét th i l ch 9 T3 T4 T6 Read(Q); Write(Q); Write(Q); Write(Q); Th i l ch 9 Bi u di n th c a S như sau: Và th trình t có gán nhãn bi u di n S’ như sau:
80 Bài gi ng tóm t t H qu n tr cơ s d li u Nu th trình t gán nhãn không ch a chu trình, th i l ch tương ng là kh tu n t view, như v y th i l ch 9 là kh tu n t view. Tuy nhiên, n u th S’ ch a chu trình, i u ki n này không kéo theo th i l ch tương ng không là kh tu n t view. Bây gi ta gi s r ng có n c p cung tách bi t, ó là do ta ã áp d ng n l n quy t c 3c trong s xây th trình t . Khi ó có 2n th khác nhau, m i m t th ch a úng m t cung d ng trong m i c p. N u m t th nào ó trong các th này là phi chu trình, khi ó th i l ch tương ng là kh tu n t view. Thu t toán này òi h i m t phép ki m th vét c n các th riêng bi t, và như v y thu c v l p bài toán NP- y . 3. i u khi n tương tranh d a trên khóa M t phương pháp m b o tính kh tu n t là yêu c u vi c truy xu t n m c d li u ư c ti n hành theo ki u lo i tr tương h ; có nghĩa là trong khi m t giao d ch ang truy xu t m t m c d li u, không m t giao d ch nào khác có th s a i m c d li u này. Phương pháp chung nh t ư c dùng th c thi yêu c u này là cho phép m t giao d ch truy xu t m t m c d li u ch n u nó ang gi khóa trên m c d li u ó. Khóa (Lock) Có nhi u phương th c khóa m c d li u. Ta h n ch vi c nghiên c u trên hai phương th c: 1. Shared: N u m t giao d ch Ti nh n ư c m t khóa phương th c shared (ký hi u là S) trên m c Q, khi ó Ti có th c, nhưng không ư c vi t Q. 2. Exclusive. N u m t giao d ch Ti nh n ư c m t khóa phương th c Exclusive (ký hi u là X), khi ó Ti có th c c l n vi t Q. Hàm tương thích
81 Bài gi ng tóm t t H qu n tr cơ s d li u M i giao d ch òi h i m t khóa m t phương th c thích h p trên m c d li u Q, ph thu c vào ki u ho t ng mà nó s th c hi n trên Q. Gi s m t giao d ch Ti òi h i m t khóa phương th c A trên m c Q mà trên nó giao d ch Tj (Tj ≠ Ti) hi n ang gi m t khóa phương th c B. N u giao d ch Ti có th ư c c p m t khóa trên Q ngay, b t ch p s hi n di n c a khóa phương th c B, khi ó ta nói phương th c A tương thích v i phương th c B. Hàm tương thích gi a hai phương th c khóa ư c bi u di n b i m t ma tr n. Quan h cho b i ma tr n comp sau: S X S True False X False False Comp(A, B) = True có nghĩa là các phương th c A và B tương thích. Các th t c c p và thu h i khóa như sau: • lock-S(Q): yêu c u m t khóa shared trên m c d li u Q. • lock-X(Q): yêu c u m t khóa exclusive trên m c d li u Q. • unlock(Q): thu h i khóa trên m c d li u Q truy xu t m t m c d li u, giao d ch Ti u tiên ph i khóa m c này. N u m c này ã b khóa b i m t giao d ch khác phương th c không tương thích, b i u khi n tương tranh s không c p khóa cho n t n khi t t c các khóa không tương thích b gi b i các giao d ch khác ư c tháo. Như v y Ti ph i ch n t n khi t t c các khóa không tương thích b gi b i các giao d ch khác ư c gi i phóng. Giao d ch Ti có th tháo khóa m t m c d li u mà nó ã khóa trư c ây. M t giao d ch c n thi t ph i gi m t khóa trên m t m c d li u ch ng nào mà nó còn truy xu t m c này. Hơn n a, i v i m t giao d ch vi c tháo khóa ngay sau truy xu t cu i cùng n m c d li u không luôn luôn là i u mong mu n vì như v y tính kh tu n t có th không ư c m b o. minh ho cho tình hu ng này, ta xét ví d sau: A và B là hai tài kho n có th ư c truy xu t b i các giao d ch T1 và T2 . Giao d ch T1 chuy n 50$ t tài kho n B sang tài kho n A và ư c xác nh như sau: T1 : Lock-X(B); Read(B); B:=B-50; Write(B); Unlock(B); Lock-X(A); Read(A);
82 Bài gi ng tóm t t H qu n tr cơ s d li u A:=A+50; Write(A); Unlock(A); Giao d ch T2 hi n th t ng s lư ng ti n trong các tài kho n A và B (A + B) và ư c xác nh như sau: T2 : Lock-S(A); Read(A); Unlock(A); Lock-S(B); Read(B); Unlock(B); Display(A+B); Gi s giá tr c a tài kho n A và B tương ng là 100$ và 200$. N u hai giao d ch này th c hi n tu n t , ho c theo th t T1, T2 ho c theo th t T2 , T1 , và khi dó T2 s hi n th giá tr 300$. Tuy nhiên n u các giao d ch này th c hi n tương tranh, gi s theo th i l ch schedule-1, trong trư ng h p như v y giao d ch T2 s hi n th giá tr 250$, m t k t qu không úng vì giao d ch T1 ã tháo khóa m c B quá s m và T2 ã tham kh o m t tr ng thái không nh t quán. Th i l ch 12 cho th y các ho t ng ư c th c hi n b i các giao d ch cũng như các th i i m khi các khóa ư c c p b i b qu n tr i u khi n tương tranh. Giao d ch ưa ra m t yêu c u khóa không th th c hi n hành ng k c a mình n t n khi khóa ư c c p b i b qu n tr i u khi n tương tranh; do ó, khóa ph i ư c c p trong kho ng th i gian gi a ho t ng yêu c u khóa và hành ng sau c a giao d ch. Sau này ta s luôn gi thi t khóa ư c c p cho giao d ch ngay trư c hành ng k và như v y ta có th b qua c t b qu n tr i u khi n tương tranh trong b ng. T1 T2 B qu n tr i u khi n tương tranh Lock-X(B) Grant-X(B,T ) 1 Read(B) B:=B-50 Write(B) Unlock(B) Lock-S(A) Grant-S(A,T ) 2 Read(A)