Luận văn:Các thuật toán điều khiển tương tranh trong cập nhật dữ liệu phân tán

Chia sẻ: Nhung Thi | Ngày: | Loại File: PDF | Số trang:26

Thêm vào BST

Báo xấu

94
lượt xem 12
download

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

Những năm của thập kỷ 70, máy tính đã có đủ khả năng xây dựng hệ thống thông tin và hệ cơ sở dữ liệu. Một mặt đã hình thành và phát triển các mô hình lý thuyết cho hệ cơ sở dữ liệu và mặt khác những nguồn phát triển hệ thống ứng dụng ngày càng có nhiều kinh nghiệm. Hệ thống thông tin hình thành trên cơ sở kết nối các máy tính khác nhau. Những năm gần đây, hệ cơ sở dữ liệu phân tán được phát triển dựa trên cơ sở dữ liệu và mạng máy...

Chủ đề:

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

Lưu

Nội dung Text: Luận văn:Các thuật toán điều khiển tương tranh trong cập nhật dữ liệu phân tán

B GIÁO D C VÀ ĐÀO T O Đ I H C ĐÀ N NG B CH NG C DƯƠNG CÁC THU T TOÁN ĐI U KHI N TƯƠNG TRANH TRONG C P NH T D LI U PHÂN TÁN Chuyên ngành: Khoa h c máy tính Mã s : 60.48.01 TÓM T T LU N VĂN TH C SĨ K THU T Đà N ng - Năm 2011
-1- Công trình ñư c hoàn thành t i Đ I H C ĐÀ N NG Ngư i hư ng d n khoa h c: PGS.TS LÊ VĂN SƠN Ph n bi n 1: TS. HUỲNH CÔNG PHÁP Ph n bi n 2: TS. TRƯƠNG CÔNG TU N Lu n văn ñư c b o v t i H i ñ ng ch m Lu n văn t t nghi p th c sĩ k thu t h p t i Đ i h c Đà N ng vào ngày 10 tháng 09 năm 2011. Có th tìm hi u lu n văn t i: - Trung tâm Thông tin - H c li u, Đ i h c Đà N ng - Trung tâm H c li u, Đ i h c Đà N ng
-1- M Đ U 1. Lý do ch n ñ tài Ngày nay, Công ngh Thông tin ñã th c s tr thành m t nhân t quan tr ng trong s n xu t và phát tri n kinh t toàn xã h i v i ph m vi toàn c u. Trong n n kinh t tri th c, Công ngh Thông tin ñóng vai trò then ch t. M ng máy tính, ñ c bi t là Internet tr thành công c ñ c l c không th thi u cho b t kỳ m t t ch c xã h i nào. Các yêu c u v lưu tr và x lý d li u phân tán t i nhi u v trí ñ a lý khác nhau nh m tăng hi u năng s d ng m ng máy tính, ñ ng th i cũng ñòi h i ph i có tính ñ ng b gi a các ti n trình xa. Lúc này, trong các h CSDL thư ng x y ra trư ng h p nhi u yêu c u truy c p ñ ng th i ñ n m t tài nguyên d li u. Ch ng h n, trong m t h th ng ñ t ch tàu h a c a m t hãng ñư ng s t, có nhi u nhà ga bán vé. T i m t th i ñi m, các ñ i lý này có th bán vé ñ ng th i. Vì v y, n u không có s ki m soát, thì tình tr ng m t gh ng i ñư c bán nhi u hơn m t l n có th x y ra. Xét m t ví d khác là h th ng báo ñi m thi ñ i h c. T i m i th i ñi m, có r t nhi u thí sinh cùng truy c p vào CSDL ñi m ñ xem k t qu thi c a mình. Vì v y truy c p c a các thí sinh trong trư ng h p này là truy c p ch ñ c; chúng không làm thay ñ i d li u. Như v y, ñ i v i các truy c p ch ñ c thì càng có nhi u thao tác th c hi n ñ ng th i càng t t, vì v y s ti t ki m ñư c th i gian. Ngư c l i, v i các truy c p có làm thay ñ i giá tr c a d li u, thì c n ki m soát các truy c p này. Cách an toàn nh t là yêu c u các truy c p ñó th c hi n m t cách tu n t . Nhưng làm như v y, hi u năng c a h th ng s kém. Trên th c t , m t giao d ch có th bao g m nhi u thao tác, có th ñ c xen k v i ghi. Do ñó, bài toán ñ t ra là, ñ tăng hi u qu ho t ñ ng c a h th ng, c n ñưa ra các phương pháp cho phép th c hi n các thao tác ñ ng th i nhưng v n ñ m b o ñư c tính toàn v n và tính nh t quán c a d li u, trong khi v n ngăn
-2- c n ñư c các thao tác tương tranh có kh năng phá h y tính toàn v n và tính nh t quán c a d li u. Mu n v y, c n ph i nghiên c u qu n lý các giao d ch và ñi u khi n tương tranh. Có nhi u thu t toán ñi u khi n tương tranh ñư c ñ xu t. Trong ñó, có nh ng thu t toán ñã ñư c cài ñ t trong các h CSDL th c t , nhưng cũng có nhi u thu t toán chưa tri n khai cài ñ t trên b t c m t h CSDL nào. Riêng Vi t Nam, chưa có nhi u các công trình liên quan ñ n v n ñ này mà ch y u là các tài li u biên d ch t các công trình c a các tác gi nư c ngoài. Do v y, vi c nghiên c u ñ tài này là c n thi t ñ hi u rõ các nguyên lý c a các h CSDL cũng như có th làm tài li u tham kh o cho các ñ i tư ng ñ c gi là sinh viên chuyên ngành Tin h c ho c nh ng ngư i có quan tâm. 2. M c tiêu và nhi m v nghiên c u M c tiêu c a ñ tài là tìm hi u t ng quan v h CSDL phân tán, các giao d ch phân tán, tìm hi u các thu t toán ñi u khi n tương tranh trong c p nh t d li u phân tán. Phân tích các thu t toán ñ ñưa ra nh ng ñánh giá, so sánh các thu t toán v i nhau; ñ xu t các trư ng h p s d ng v i t ng thu t toán. Đ ng th i, bư c ñ u ñ xu t cài ñ t mô ph ng m t thu t toán ñi u khi n tương tranh cơ b n ñ làm cơ s nghiên c u cài ñ t cho các ng d ng th c t khi có ñi u ki n. Đ tài t p trung tìm hi u ch y u các thu t toán ñi u khi n tương tranh trong c p nh t d li u phân tán. T ñó, cài ñ t chương trình minh h a thu t toán khóa 2 pha và ch ra các kh năng ng d ng có th c a chúng trong th c t . 3. Đ i tư ng và ph m vi nghiên c u H CSDL phân tán nói chung và lý thuy t v qu n lý giao d ch, các thu t toán ñi u khi n tương tranh trong c p nh t d li u phân tán nói riêng g m nhi u v n ñ l n và ph c t p. Vì v y, ñ tài này ch t p trung vào nghiên c u m t s thu t toán ñi u khi n tương tranh s
-3- d ng khóa và nhãn th i gian. Các thu t toán khác s không ñi sâu vào phân tích chi ti t. 4. Phương pháp nghiên c u Nghiên c u lý thuy t: Thu th p, phân tích các tài li u và thông tin liên quan ñ n ñ tài như: Tìm hi u t ng quan v h CSDL phân tán, tìm hi u các giao d ch phân tán, tìm hi u các thu t toán ñi u khi n tương tranh trong c p nh t d li u phân tán. Nghiên c u ng d ng: Cài ñ t chương trình minh h a thu t toán khóa 2 pha ñã tìm hi u. 5. Ý nghĩa khoa h c và th c ti n c a ñ tài K t qu nghiên c u có th làm tài li u tham kh o cho các ñ i tư ng ñ c gi là sinh viên chuyên ngành Công ngh Thông tin, các ñơn v có nhu c u xây d ng các ng d ng th c t ñòi h i ph i phân tán v m t d li u trên nhi u v trí ñ a lý khác nhau nhưng yêu c u ph i ñ m b o tính ñ ng b v d li u ho c nh ng ngư i có quan tâm. 6. C u trúc c a lu n văn Lu n văn ñư c chia thành 3 chương: Chương 1: Gi i thi u t ng quan v h qu n tr CSDL phân tán; Đánh giá ưu khuy t ñi m và các v n ñ ñ t ra ñ i v i h CSDL phân tán; Tìm hi u các ràng bu c toàn v n trong h CSDL phân tán và các lo i phân m nh d li u. Chương 2: Tìm hi u các giao d ch phân tán, tính kh tu n t và các thu t toán ki m tra tính kh tu n t . Chương 3: Nghiên c u các thu t toán ñi u khi n tương tranh trong c p nh t d li u phân tán bao g m các thu t toán d a trên cơ s khóa và nhãn th i gian. Tìm hi u cách x lý tình tr ng b t c (Deadlock), các giao th c truy n giao. Cài ñ t chương trình minh h a thu t toán khóa 2 pha.
-4- Chương 1. T NG QUAN V H CƠ S D LI U PHÂN TÁN 1.1 GI I THI U V H CSDL PHÂN TÁN 1.1.1 X lý phân tán và x lý d li u phân tán H th ng tính toán phân tán là m t s các ph n t x lý t v n hành ñư c liên k t b i m t m ng máy tính và ph i h p th c hi n các tác v mà chúng ñư c phân công. M c ñích c a vi c x lý phân tán là nh m thích ng v i vi c phân b v ñ a lý c a các công ty, thích ng v i các ng d ng trong môi trư ng phân tán và có th gi i quy t t t hơn các bài toán l n và ph c t p b ng cách s d ng quy t c “chia ñ tr ”. 1.1.2 Khái ni m h CSDL phân tán CSDL phân tán là m t t p h p nhi u CSDL có liên ñ i logic và ñư c phân b trên m t m ng máy tính. H qu n tr CSDL phân tán là m t h th ng ph n m m có ch c năng qu n lý các h CSDL phân tán và làm cho vi c phân tán tr nên “trong su t” ñ i v i ngư i s d ng. 1.1.3 Đánh giá ưu, như c ñi m c a h CSDL phân tán 1.1.3.1 Nh ng ưu ñi m và tri n v ng c a các h CSDL phân tán - Qu n lý d li u phân tán và nhân b n trong su t - Đ m b o ñ tin c y - C i thi n hi u năng - Tính d m r ng 1.1.3.2 Nh ng khuy t ñi m và khó khăn c n gi i quy t trong các h CSDL phân tán M t s v n ñ c n gi i quy t trong các h CSDL phân tán ñó là: Tính ph c t p, chi phí ñ u tư, phân tán quy n ñi u khi n và v n ñ an ninh (b o m t).
-5- 1.1.4 Các v n ñ ñ t ra ñ i v i h CSDL phân tán * Đi u khi n tương tranh phân tán Đi u khi n tương tranh cho phép nhi u giao d ch truy c p ñ ng th i ñ n m t tài nguyên trong CSDL nhưng tính toàn v n c a CSDL v n ñư c duy trì. * Đi u khi n Deadlock phân tán M t h th ng ñư c g i là trong tình tr ng Deadlock n u t n t i m t t p h p các giao d ch mà m i giao d ch trong t p này ñ u ñ i m t giao d ch khác. Có 2 phương pháp ñ gi i quy t tình tr ng Deadlock mà m i phương pháp có ưu khuy t ñi m riêng: - Giao th c ngăn ng a DeadLock: B o ñ m r ng h th ng không bao gi x y ra tình tr ng DeadLock. - Có th ñ cho h th ng x y ra tình tr ng DeadLock và tìm cách khôi ph c chúng, g i là sơ ñ tìm và khôi ph c DeadLock. 1.1.5 C u trúc c a h qu n tr CSDL phân tán 1.2 THI T K CSDL PHÂN TÁN 1.2.1 C u trúc tham kh o c a CSDL phân tán 1.2.2 Các ràng bu c toàn v n trong CSDL phân tán 1.2.3 Thi t k phân tán 1.2.3.1 Các ñi u ki n khi phân m nh 1.2.3.2 Phân m nh d li u
-6- Chương 2. CÁC GIAO D CH PHÂN TÁN 2.1 CÁC KHÁI NI M TRONG GIAO D CH PHÂN TÁN 2.1.1 Giao d ch M t giao d ch là m t ñơn v chương trình ñư c th c hi n nh m m c ñích truy c p các ñơn v d li u có th ñư c lưu tr t i nhi u v trí khác nhau. Các tính toán do giao d ch th c hi n không làm thay ñ i CSDL cho ñ n khi các giá tr m i ñư c ghi vào CSDL. Giao d ch có th th c hi n vi c ñ c, ghi, tính toán t o ra d li u m i cho CSDL, vì v y yêu c u c a giao d ch là tính nh t quán và tin c y. Các thao tác mà giao d ch có th th c hi n bao g m: Read và Write. 2.1.2 M c d li u 2.1.3 Khóa Khóa (Lock) là quy n c a m t giao d ch ñư c b qu n lý khóa trao cho ñ có th truy c p trên m t m c d li u. 2.1.4 B x p l ch và các giao th c B x p l ch và các giao th c ñư c s d ng ñ ngăn ng a b t c. B x p l ch là m t thành ph n c a h th ng CSDL ch u trách nhi m s p x p m t l ch bi u cho các thao tác c a các giao d ch. Giao th c là các quy t c mà các giao d ch ph i tuân theo. 2.1.5 Các khái ni m y thác, d li u “rác” và cu n ngư c dây chuy n 2.1.6 Các tr ng thái c a giao d ch - Active: Tr ng thái giao d ch ñang ho t ñ ng - Partially Committed: Đã commit t ng ph n - Failed: Sau khi phát hi n ra vi c th c hi n m t cách bình thư ng là không th ti p t c. - Aborted: Sau khi giao d ch khôi ph c d li u l i gi ng như tr ng thái trư c khi giao d ch b t ñ u.
-7- - Committed: Sau khi giao d ch ñã hoàn t t. 2.1.7 Chính th c hóa khái ni m giao d ch 2.1.8 Các tính ch t c a giao d ch 2.1.8.1 Tính nguyên t 2.1.8.2 Tính nh t quán 2.1.8.3 Tính riêng bi t 2.1.8.4 Tính b n v ng 2.1.9 Phân lo i giao d ch 2.2 TH C HI N S TƯƠNG TRANH 2.2.1 Tính kh tu n t c a các l ch 2.2.1.1 Đ nh nghĩa Cho n giao d ch T1, T2,…, Tn - G i m t l ch S c a 1 t p các giao d ch T1, T2,…, Tn là m t th t mà trong ñó các l nh c a các giao d ch này ñư c th c hi n l n lư t hoàn toàn. - M t l ch S ñư c g i là tu n t n u t t c các bư c c a m i giao d ch ñ u ñư c th c hi n liên ti p nhau. Như v y trong l ch tu n t m i giao d ch th c hi n toàn b các l nh c a nó và không có tương tranh. - M t l ch S ñư c là kh tu n t n u nó tương ñương v i 1 l ch tu n t nào ñó (g i 2 l ch là tương ñương n u k t qu cu i cùng trong CSDL sau khi th c hi n 2 l ch này là như nhau). 2.2.1.2 Tính kh tu n t ñ ng ñ Hai l nh là ñ ng ñ n u chúng là các l nh c a các giao d ch khác nhau tác ñ ng trên cùng m t ñơn v d li u và trong chúng có ít nh t m t thao tác Write. 2.2.1.3 Tính kh tu n t quan sát Đ nh nghĩa 1: Cho 2 l ch S và S’ trên cùng m t t p các giao d ch T1, T2,…, Tn. Ta g i S và S’ là tương ñương quan sát n u th a 3 ñi u ki n sau:
-8- 1. V i m i ñơn v d li u Q, n u Ti nh n giá tr kh i tr c a Q trong l ch S thì giao d ch Ti cũng ph i nh n giá tr kh i tr c a Q trong l ch S’. 2. V i m i ñơn v d li u Q, n u trong l ch S giao d ch Ti ñ c giá tr c a Q mà giá tr này ñư c x lý b i Tj thì trong l ch S’ giao d ch Ti cũng ph i ñ c giá tr c a Q mà giá tr này ñư c x lý b i Tj. 3. V i m i ñơn v d li u Q, n u trong l ch S giao d ch Ti th c hi n thao tác ghi sau cùng, thì trong l ch S’ giao giao d ch cũng ph i th c hi n thao tác ghi sau cùng. Đ nh nghĩa 2: L ch S ñư c g i là kh tu n t quan sát n u nó tương ñương quan sát v i m t l ch tu n t . Các l ch kh tu n t ñ ng ñ thì kh tu n t quan sát, tuy nhiên không có ñi u ngư c l i. 2.2.2 Kh năng khôi ph c d li u N u m t giao d ch Ti nào ñó b h ng thì chúng ta c n thi t Undo nh ng gì các giao d ch ñã thao tác nh m th a mãn tính ch t nguyên t (Atomicity). M t khác, trong h cho phép th c hi n tương tranh thì ph i ñ m b o r ng m i giao d ch ph thu c Ti (Ch ng h n: Tj ñ c d li u ñã ñư c Ti ghi) cũng ph i ñư c Aborted. Đ th a mãn ñư c ñi u này chúng ta c n thi t gi i h n các lo i c a l ch ñư c cho phép b i h th ng. Trong ph n ñi u khi n tương tranh chúng ta ch xét các l ch ch p nh n ñư c. Xét 2 lo i l ch th a mãn ñi u ki n trên. 2.2.2.1 L ch có th khôi ph c ñư c 2.2.2.2 L ch không gây nên h y b dây chuy n 2.3 CÁC THU T TOÁN V KI M TRA TÍNH KH TU N T 2.3.1 Ki m tra tính kh tu n t Thu t toán 2.1: Ki m tra tính kh tu n t c a l ch S. Input: L ch S c a t p các giao d ch T1, T2,…, Tk Output: Xác ñ nh xem S có kh tu n t hay không? N u có thì cho ra l ch tu n t tương ñương.
-9- Method: T o m t ñ th có hư ng (ñ th tu n t ) g m m t c p G=(V,E). Trong ñó, V là t p các ñ nh và E là t p các c nh. T p h p các ñ nh là t p h p t t c các giao d ch c a l ch S. Còn t p h p các c nh c a ñ thì có d ng: Ti → Tj n u th a mãn 1 trong các ñi u ki n sau, v i m i ñơn v d li u A ta có: 1. Ti th c hi n thao tác Read(A) trư c khi Tj th c hi n Write(A). 2. Ti th c hi n thao tác Write(A) trư c khi Tj th c hi n Write(A). 3. Ti th c hi n thao tác Write(A) trư c khi Tj th c hi n Read(A) và không có thao tác Write(A) nào gi a 2 giao d ch này. N u ñ th có hư ng G có chu trình thì l ch S không kh tu n t . N u G không có chu trình thì S kh tu n t và th t tuy n tính c a các giao d ch Ti (th t Topo) có ñư c b ng cách l n lư t g toàn b các ñ nh không có cung ñ n. Th t này c a các ñ nh là th t tu n t c a các giao d ch tương ñương. 2.3.2 Ki m tra tính kh tu n t ñ ng ñ M c ñích: Nh m ki m tra các ràng bu c v th t c a các thao tác khi có thao tác ghi, nói cách khác là c n th a 2 ñi u ki n: Đi u ki n 1: N u giao d ch T2 ñ c m t giá tr c a A ñư c ghi b i T1 thì T1 ph i trư c T2 trong m i l ch. (Luôn có 1 c nh T1 → T2). Đi u ki n 2: N u giao d ch T2 ñ c m t giá tr c a A ñư c ghi b i T1 thì n u T3 là m t giao d ch ghi vào A thì T3 không ñư c gi a T1 và T2 (ho c là T3 → T1 ho c là T2 → T3). Thu t toán 2.2: Ki m tra tính kh tu n t ñ ng ñ c a l ch S. Input: M t l ch S c a m t t p các giao d ch T1, T2, …, Tk. Output: Xác ñ nh S có kh tu n t ñ ng ñ không, n u có thì tìm l ch tu n t tương ñương v i l ch S. Method:
- 10 - 1. Thêm vào l ch S hai giao d ch gi (Dummy giao d ch) là T0 và Tf ñ u và cu i c a l ch S. Trong ñó, T0 th c hi n vi c ghi vào m i ñơn v d li u xu t hi n trong l ch S và Tf th c hi n ñ c m i ñơn v d li u trong S. 2. T o m t ña ñ th (Polygraph) P v i m i ñ nh là m t giao d ch (bao g m c T0 và Tf). N u Tj ñ c tr c ti p d li u do Ti ghi thì t o c nh Ti → Tj. 3. Tìm các giao d ch vô d ng (Useless Transation). Giao d ch ñư c g i là vô d ng n u không t n t i T → Tf. 4. V i m i giao d ch vô d ng T ta b ñi các c nh ñ n T. 5. V i m i c nh còn l i Ti → Tj và v i m i ñơn v d li u A mà Tj ñ c giá tr c a A mà Ti ghi, ta xét các giao d ch T ≠ T0 cũng ghi vào A như sau: - N u Ti = T0 và Tj = Tf thì không thêm c nh nào vào. - N u Ti = T0 và Tj ≠ Tf thì thêm c nh Tj → T. - N u Ti ≠ T0 và Tj = Tf thì thêm c nh T → Ti. - N u Ti ≠ T0 và Tj ≠ Tf thì thêm vào m t c p c nh (T → Ti, Tj → T). 6. Xác ñ nh xem ña ñ th P có chu trình hay không? - N u có t n t i 1 ñ thì G nào trong ña ñ th P này mà không có chu trình (G ñư c t o t P b ng cách ch n 1 c nh t m i c p) thì ta nói r ng l ch S là kh tu n t ñ ng ñ và th t topo c a G (ñã b ñi T0 và Tf) là bi u di n l ch tu n t tương ñương c a S. - N u ña ñ th G là luôn có chu trình thì k t lu n l ch S không kh tu n t ñ ng ñ (không có l ch tu n t nào tương ñương).
- 11 - Chương 3. CÁC THU T TOÁN ĐI U KHI N TƯƠNG TRANH TRONG C P NH T D LI U PHÂN TÁN 3.1 ĐI U KHI N TƯƠNG TRANH PHÂN TÁN 3.1.1 Các thu t toán ñi u khi n tương tranh d a trên cơ s khóa 3.1.1.1 Phân lo i thu t toán d a trên khóa Ý tư ng c a các thu t toán này là các thao tác trên m t ñơn v d li u n u có ñ ng ñ nhau thì ch cho phép 1 thao tác th c hi n t i m t th i ñi m. Đi u này ñư c th c hi n d a trên vi c khóa ñơn v d li u. D a vào vi c qu n lý khóa d li u mà các thu t toán bao g m: 1. Qu n lý khóa t p trung 2. Qu n lý khóa c a b n sao chính 3. Qu n lý khóa phân tán Khi giao d ch th c hi n vi c truy c p m t ñơn v d li u thì trư c h t ph i xin khóa d li u. Có 2 cách khóa: - Shared (S) hay ReadLock(RL): Cho ñ c nhưng không cho ghi. - Exclusive (E) hay WriteLock(WL): Cho phép ñ c và ghi. Ta g i 2 ki u khóa là tương thích v i nhau n u chúng có th th c hi n ñ ng th i trên 1 ñơn v d li u. V i 2 ki u RL và WL, ta có ma tr n tương thích nhau: RL WL RL Yes No WL No No M t giao d ch có th rơi vào trư ng h p ph i ñ i liên t c mà không th th c hi n ñư c vì ki u khóa là không tương thích. Trư ng h p này g i là khóa s ng (LiveLock).
- 12 - * V y, khi l p l ch cho các giao d ch tương tranh c n quan tâm ñ n 3 y u t sau ñây: Tính kh tu n t , không ñ x y ra tình tr ng Deadlock và không ñ x y ra tình tr ng Livelock. 3.1.1.2 Thu t toán qu n lý vi c khóa d li u Thu t toán 3.1: Thu t toán khóa d li u Repeat WAIT(Msg) Case Msg of DbOp: {T chương trình ng d ng} Op=Dop.Opn X=Dop.Data T=Dop.Tid Case Op of Read or Write: {Yêu c u khóa d li u} Tìm ñơn v d li u LU (Lock Unit) mà X ⊆ LU If (LU ñang không b khóa) or (ki u khóa c a LU là tương thích v i Op) then Set khóa trên LU theo ki u tương ng G i Dop ñ n b x lý d li u Else Đ t Dop vào 1 queue cho LU End if Abort or Commit: G i Dop ñ n b x lý d li u End case DpMsg: {T b x lý d li u yêu c u Unlock} Op=Pm.Opn Res=Pm.Res
- 13 - T=Pm.Tid Tìm ñơn v d li u LU (Lock Unit) mà x ⊆ LU Lo i b vi c khóa trên LU gi b i T If (không còn Lock nào trên LU) and (trong queue có thao tác ñang ñ i ñ Lock LU) then SOP=Thao tác ñ u tiên trong queue SOP=SOP ∪ {O: là thao tác có trên queue mà có th Lock LU trong ki u tương thích v i các thao tác hi n hành trong SOP} Thi t l p vi c Lock trên LU ñư c x lý b i các thao tác trong SOP for (t t c các thao tác trong SOP) do G i m i thao tác vào b x lý d li u End for End if End case Until H th ng d ng Thu t toán 3.2: Thu t toán khóa 2 pha Repeat WAIT(Msg) Case Msg of DbOp: G i O cho b ph n qu n lý khóa ScMsg: Op=Sm.Opn Res=Sm.Result T=Sm.Tid Case Op of Read: Return Res cho Transaction c a user
- 14 - Write: Báo cho ng d ng c a user bi t ñã hoàn thành vi c ghi Return Res cho ng d ng c a user Commit: Xóa b vùng làm vi c c a T Báo cho ng d ng c a user bi t ñã hoàn thành Transaction Abort: Báo cho ng d ng c a user bi t ñã hoàn thành vi c Abort Transaction T End case End case Until H th ng d ng Thu t toán 3.3: Thu t toán khóa 2 pha nghiêm ng t Repeat WAIT(Msg) Case Msg of DbOp: Op=Dop.Opn X=Dop.Data T=Dop.Tid Case Op of G i Dop ñ n b x lý d li u Read or Write: {Yêu c u chi m gi d li u} Tìm LU (Lock Unit) mà x ⊆ LU If (LU ñang UnLock) or (ki u khóa c a LU là không tương thích v i Op)then Set khóa trên LU theo ki u tương ng
- 15 - Gưi Dop ñ n b x lý d li u Else Đ t Dop vào 1 queue cho LU End if Abort or Commit: G i Dop ñ n b x lý d li u End case DpMsg: {T b x lý d li u có yêu c u UnLock} Op=Pm.Opn Res=Pm.Result T=Pm.Tid If (Op=Abort) or (Op=Commit) then For v i m i LU ñư c Lock b i T do Lo i b vi c Lock trên LU gi b i T If (không còn Lock nào trên LU) and (trong queue có thao tác ñang ñ i ñ Lock LU) then SOP=Thao tác ñ u tiên trong Queue SOP=SOP∪{O: là thao tác có trong queue mà có th Lock LU trong ki u tương thích v i các thao tác hi n hành trong SOP} Thi t l p vi c Lock trên LU ñư c x lý b i các thao tác trong SOP For (t t c thao tác trong (SOP) do G i m i thao tác vào b x lý d li u End for End if End case
- 16 - Until H th ng d ng Thu t toán 3.4: Khóa 2 pha trung tâm qu n lý giao d ch Repeat WAIT(Msg) Case Msg of DbOp: Op=O.Opn X=O.Data T=O.Tid Case Op of S=∅ Read: S=S∪{v trí có ch a x và chi phí truy c p ñ n nó là th p nh t} G i O ñ n LM trung tâm Write: S=S∪{Si: v i x ñư c lưu tr t i v trí Si} G i O ñ n LM trung tâm Abort or Commit: G i O ñ n LM trung tâm End case ScMsg: {Cho phép Lock trên các d li u ñã UnLock} If (yêu c u khóa ñư c cho phép) then G i O ñ n các b ph n x lý d li u trong S Else Thông báo cho user v s k t thúc c a Transaction DpMsg: Op=Pm.Opn Res=Pm.Result
- 17 - T=Pm.Tid Case Op of Read: Return Res cho ng d ng c a user Write: Thông báo cho ng d ng c a user v s hoàn t t thao tác ghi Commit: If Commit Msg nh n ñư c t t t c các v trì thành viên then - Thông báo cho ng d ng c a user Transaction ñã hoàn t t - G i Pm ñ n LM trung tâm Else {ñ i các commit Msg ñ n t t t c các v trí} Lưu vào các commit Msg ñã ñ n End if Abort: Thông báo cho ng d ng c a user ñã hoàn t t Abort T G i Pm ñ n LM trung tâm End case End case Until H th ng d ng Thu t toán 3.5: Khóa 2 pha trung tâm qu n lý khóa Repeat WAIT(Msg) {Các Msg ch có th ñ n t Coordinating TM} Op=Dop.Opn X=Dop.Data T=Dop.Tid
- 18 - Case Op of Read or Write: Tìm ñơn v d li u LU (Lock Unit) mà x ⊆ LU If (LU ñang UnLock) or (ki u khóa c a LU là tương thích v i Op) then Set khóa trên LU theo ki u tương ng Msg=”Cho phép Lock c a thao tác Dop” G i Msg ñ n TM ñi u ph i c a T Else Đ t Op vào 1 queue cho LU End if Commit or Abort: For v i m i LU ñư c khóa b i T do Lo i b vi c Lock trên LU gi b i T If trong queue có thao tác ñang ñ i Lock LU then SOP=Thao tác O ñ u tiên trong queue SOP=SOP∪{O: là thao tác có trên queue mà có th Lock LU trong ki u tương thích v i các thao tác hi n trong SOP Thi t l p vi c Lock trên LU ñư c x lý b i các thao tác trong SOP for t t c thao tác O trong SOP do Msg=Cho phép Lock c a thao tác O G i Msg ñ n t t c ñi u ph i c a TM End for End if End for Msg=”Các khóa c a T ñã ñư c b ” G i Msg ñ n TM ñi u ph i c a T