Giáo trình Cơ sở dữ liệu phân bổ

c), mặc dù có một số lần giao dịch này có cơ hội nhận khoá 
trên mục đó. Rất nhiều giải pháp đã được các nhà thiết kế hệ điều hành đề xuất vấn đề 
 84 
giải quyết khoá sống. Có thể sử dụng một chiến lược đơn giản “đến trước, phục vụ trước” 
để loại bỏ được khoá sống. 
 Bế tắc hay khoá gài (deadlock) là tình huống mà trong đó mỗi giao dịch trong một 
tập hay nhiều giao dịch đang đợi nhận khoá của một mục hiện đang bị khoá bởi một giao 
dịch khác trong một tập giao dịch đó và ngược lại (một mục trong giao dịch này bị gài 
bởi giao dịch khác và ngược lại). 
 Ví dụ Giả sử có hai giao dịch đồngthời T1 và T2 như sau: 
 T1 : Lock A ; Lock B ; Unlock A ; Unlock B; 
 T2 : Lock B ; Lock A ; Unlock B ; Unlock A; 
 T1 và T2 cùng có thể thực hiện một số tác vụ nào đó trên A và B. Giả sử T1 và T2 
được thực hiện cùng lúc. T1 yêu cầu và được trao khoá trên A, còn T2 yêu cầu và được 
trao khoá trên B. Do đó khi T1 yêu cầu khoá trên B nó sẽ phải đợi vì T2 đã khoá B. Tương 
tự T2 yêu cầu khoá trên A nó sẽ phải đợi vì T1 đã khoá A. Kết quả là không một giao dịch 
nào tiếp tục hoạt động được: mỗi giao dịch đều phải đợi giao dịch kia mở khoá, và chúng 
đều phải đợi nhưng chẳng bao giờ nhận được khoá như yêu cầu. 
 Để tránh bế tắc có thể sử dụng các giải pháp: 
 (i) Buộc các giao dịch phải đưa ra tất cả các yêu cầu khoá cùng một lúc và bộ quản 
lý khoá trao tất cả các khoá cho chúng nếu được, hoặc không trao và cho giao dịch này 
đợi nếu một hay nhiều khoá được yêu cầu đang bị giữ bởi một giao dịch khác. 
 (ii) Gán một thứ tự tuyến tính cho các mục và yêu cầu tất cả các giao dịch phải xin 
khoá theo đúng thứ tự này. 
 (iii) Một cách khác để xử lý bế tắc là định kỳ kiểm tra yêu cầu khoá và phát hiện có 
xảy ra bế tắc không. Bằng cách dùng đồ thị chờ, với các nút biểu diễn các giao dịch và 
các cung Ti Tj biểu thị Tj đang đợi nhận khoá trên một mục đang được Ti giữ. Nếu 
trong đồ thị có chu trình, sự bế tắc sẽ xảy ra, và nếu không có chu trình thì kết luận không 
có khoá gài hay bế tắc. Nếu một khoá gài bị phát hiện, khi đó hệ thống sẽ buộc một trong 
các giao dịch bị bế tắc phải khởi động lại và tác dụng của giao dịch đó trên cơ sở dữ liệu 
phải được hoàn toàn trả lại. 
4. 2. Mô hình khoá cơ bản 
 Khoá (Lock) là một đặc quyền truy cập trên một mục dữ liệu mà bộ quản lý khoá 
(lock manager) có thể trao cho một giao dịch hoặc thu hồi lại. Trong các mô hình giao 
dịch có sử dụng khoá không chỉ có các thao tác đọc và ghi các mục mà còn có thao tác 
 85 
khoá (lock) và mở khoá (unlock) chúng. Mỗi mục được khoá phải được mở khoá sau đó. 
Với một mục A, giữa bước lock A và unlock A kế tiếp của một giao dịch, giao dịch này 
phải được coi là đang giữ một khoá trên A. 
 Trong mô hình này, chúng ta dựa trên các giả định sau: 
 - Một khoá phải được đặt trên một mục trước khi đọc hay ghi mục đó. 
 - Các thao tác khoá hoạt động trên cơ sở đồng bộ hoá, nghĩa là nếu một giao dịch 
khoá một mục đã bị khoá trước đó bởi một giao dịch khác, nó không thể thao tác trên mục 
này cho đến khi khoá này được giải phóng bằng lệnh mở khoá do giao dịch đang giữ khoá 
trước đó thực hiện. 
 - Mỗi giao dịch đều có thể mở được mọi khoá do chính nó khoá. 
 - Một giao dịch sẽ không yêu cầu khoá một mục nếu nó đang hiện giữ khoá của mục 
đó, hoặc mở khoá một mục mà nó hiện không giữ khoá trên mục đó. 
 Các lịch biểu tuân theo quy tắc này được gọi là hợp lệ . 
 Ví dụ : Xét hai giao dịch đồng thời T1 và T2 cùng truy xuất đến mục dữ liệu A theo 
mô hình này sẽ là: 
 T1 Lock A T2 Lock A 
 Read A Read A 
 A:=A+1 A:=A+1 
 Write A Write A 
 Unlock A Unlock A 
 Nếu T1 bắt đầu trước T2, nó sẽ yêu cầu khoá trên mục A. Giả sử không có giao dịch 
nào đang khoá A, bộ quản lý khoá sẽ cho nó khoá mục này. Khi đó chỉ có T1 mới được 
truy xuất đến mục này. Nếu T2 bắt đầu trước khi T1 chấm dứt thì T2 thực hiện Lock A, hệ 
thống buộc T2 phải đợi. Chỉ đến khi T1 thực hiện lệnh Unlock A, hệ thống mới cho phép 
T2 tiến hành. Như vậy, T1 hoàn thành trước khi T2 bắt đầu và kết quả là sau hai giao dịch, 
giá trị của A sẽ là 32 
 Với mô hình này, để kiểm tra tính khả tuần tự của một lịch biểu, ta sẽ xem xét thứ tự 
mà các giao dịch khoá một mục đã cho. Thứ tự này phải thống nhất với thứ tự trong lịch 
biểu tuần tự tương đương. Đây thực chất là việc kiểm tra một đồ thị có chu trình hay 
không. 
 Thuật toán 2.1: Kiểm tra tính khả tuần tự của một lịch biểu. 
 Nhập: Một lịch biểu S cho một tập các giao dịch T1, T2 , ... , Tk. 
 86 
 Xuất: Khẳng định S có khả tuần tự hay không? Nếu có thì đưa ra một lịch biểu tuần 
tự tương đương với S. 
 Phương pháp: 
 Bước 1: Tạo ra một đồ thị có hướng G (gọi là đồ thị tuần tự hoá), có các nút là các 
giao dịch, các cung của đồ thị này được xác định như sau: 
 Gọi S là a1, a2, ... an 
 trong đó mỗi ai là một thao tác của một giao dịch có dạng 
 Tj : Lock Am hoặc Tj : Unlock Am 
 với Tj là giao dịch thực hiện thao tác khoá hoặc mở mục Am. 
 Nếu ai là Tj : Unlock Am 
 thì hành động ap kế tiếp ai có dạng Ts : Lock Am. Nếu s j thì vẽ một cung từ Tj đến 
Ts. Cung này có nghĩa là trong lịch biểu tuần tự tương đương, Tj phải đi trước Ts. 
 Bước 2: Kiểm tra, G có chu trình thì S bất khả tuần tự. Nếu G không có chu trình thì 
ta tìm một thứ tự tuyến tính cho các giao dịch, trong đó Ti đi trước Tj khi có một cung đi 
từ Ti Tj. Để tìm thứ tự tuyến tính đó, ta thực hiện quá trình sắp xếp topo như sau. Đầu 
tiên ta xuất phát từ một nút Ti không có cung vào (ta luôn tìm thấy một nút như thế, nếu 
không thì G là một đồ thị có chu trình), liệt kê Ti rồi loại bỏ Ti ra khỏi G. Sau đó lặp lại 
quá trình trên cho đến khi đồ thị không còn nút nào nữa. Khi đó, thứ tự các nút được liệt 
kê là thứ tự tuần tự của các giao dịch. 
 Ví dụ 2.3: Giả sử ta có lịch biểu của ba giao dịch T1, T2, T3 như sau 
 T1 : Lock A 
 T2 : Lock B 
 T2 : Lock C 
 T2 : Unlock B 
 T1 : Lock B 
 T1 : Unlock A 
 T2 : Lock A 
 T2 : Unlock C 
 T2 : Unlock A 
 T3 : Lock A 
 87 
 T3 : Lock C 
 T1 : Unlock B 
 T3 : Unlock C 
 T3 : Unlock A 
 T1 T2 T3 
 Hình 2.4 Đồ thị thứ tự các giao dịch 
 Đồ thị có 3 nút T1, T2 và T3. Các cung được xây dựng như sau: 
 ở bước (4) ta có T2 : Unlock B, bước tiếp theo có lệnh Lock B là bước (5) T1: Lock 
B. Vậy ta vẽ một cung từ T2 T1. 
 ở bước (6) ta có T1 : Unlock A, bước tiếp theo có lệnh Lock A là bước (7) T2: Lock 
A. Vậy ta vẽ một cung từ T1 T2. 
 ở bước (8) ta có T2 : Unlock C, bước tiếp theo có lệnh Lock C là bước (11) T3: Lock 
C. Vậy ta vẽ một cung từ T2 T3. 
 ở bước (9) ta có T2 :Unlock A, bước tiếp theo có lệnh Lock A là bước (10) có T3: 
Lock A. Vậy ta vẽ một cung từ T2 T3. 
 Đồ thị này có một chu trình nên lịch biểu đã cho bất khả tuần tự. 
 Ví dụ : Lịch biểu của ba giao dịch T1, T2, T3 
 (1) T2 : Lock A 
 (2) T2 : Unlock A 
 (3) T3 : Lock A 
 (4) T3 : Unlock A 
 (5) T1 : Lock B 
 (6) T1 : Unlock B 
 (7) T2 : Lock B 
 (8) T2 : Unlock B 
 88 
 T1 T2 T3 
 Hình 2.5. Đồ thị tuần tự cho ba giao dịch 
4.3. Mô hình khoá đọc và khoá ghi 
 Trong mô hình khoá cơ bản, ta giả sử rằng khi khoá một mục có thể thay đổi mục đó. 
Trên thực tế, có những trường hợp một giao dịch truy cập một mục theo nghĩa chỉ đọc giá 
trị của mục đó không thay đổi giá trị của mục đó. Vì vậy nếu ta phân biệt hai loại truy 
cập: chỉ đọc (read only) và đọc ghi (read write), thì ta có thể tiến hành được một số thao 
tác đồng thời bị cấm trong mô hình khoá cơ bản. Khi đó, ta phân biệt hai loại khoá như 
sau: 
 Khoá đọc (read lock or shared lock) ký hiệu RLock hoạt động như sau: một giao dịch 
T chỉ muốn đọc một mục A sẽ thực hiện lệnh RLock A, ngăn không cho bất kỳ giao dịch 
khác ghi giá trị mới vào A trong khi T đã khoá A, nhưng các giao dịch khác vẫn có thể 
giữ một khoá đọc trên A cùng lúc với T. 
 Khoá ghi (write lock) ký hiệu WLock hoạt động như trong mô hình khoá cơ bản, 
nghĩa là một giao dịch muốn thay đổi giá trị của mục A sẽ thực hiện lệnh WLock A. Khi 
đó không một giao dịch nào được lấy khoá đọc hoặc khoá ghi trên mục đó. 
 Cả khoá đọc và khoá ghi đều được mở bằng lệnh Unlock. Ngoài các giả định như mô 
hình khoá cơ bản, ta có thêm giả định rằng một giao dịch có thể yêu cầu một khoá ghi 
trên mục mà nó đang giữ khoá đọc. 
 Hai lịch biểu là tương đương nếu: 
 - Chúng sinh ra cùng một giá trị cho mỗi mục, và 
 - Mỗi khoá đọc được áp dụng bởi một giao dịch xảy ra trong cả hai lịch biểu vào 
những lúc mục bị khoá có cùng giá trị. 
 Thuật toán 2.2: Kiểm tra tính khả tuần tự của các lịch biểu với các khoá 
đọc / ghi 
 Nhập: Một lịch biểu S cho một tập các giao dịch T1, T2 , ... , Tk. 
 Xuất: Khẳng định S có khả tuần tự hay không? Nếu có thì đưa ra một lịch biểu tuần 
tự tương đương với S. 
 89 
 Phương pháp: 
 Bước 1: Chúng ta xây dựng một đồ thị có hướng G (gọi là đồ thị tuần tự hoá), có các 
nút là các giao dịch. Các cung của đồ thị được xác định bằng quy tắc sau: 
 Giả sử trong S, Ti nhận khoá đọc hoặc khoá ghi mục A, Tj là giao dịch kế tiếp khoá 
ghi A, và i j, thì ta sẽ đặt một cung từ Ti Tj. 
 Giả sử trong S, giao dịch Ti khoá ghi A, Tm là khoá đọc A sau khi Ti mở khoá A 
nhưng trước các giao dịch khác khoá ghi A, và i m, thì ta sẽ đặt một cung từ Ti Tm . 
 Bước 2: Kiểm tra, nếu G có chu trình thì S bất khả tuần tự. Nếu G không có chu 
trình thì một sắp xếp topo của G là thứ tự tuần tự của các giao dịch này. 
Ví dụ 2.5: Một lịch biểu của bốn giao dịch : 
 (1) T2 : RLock A 
 (2) T3 : RLock A 
 (3) T2 : WLock B 
 (4) T2 : Unlock A 
 (5) T3 : WLock A 
 (6) T2 : Unlock B 
 (7) T1 : RLock B 
 (8) T3 : Unlock A 
 (9) T4 : RLock B 
 (10) T1 : RLock A 
 (11) T4 : Unlock B 
 (12) T1 : WLock C 
 (13) T1 : Unlock A 
 (14) T4 : WLock A 
 (15) T4 : Unlock A 
 (16) T1 : Unlock B 
 (17) T1 : Unlock C 
 Đồ thị tuần tự hoá của lịch biểu này được trình bày trong hình 2.6. 
 Các nút là bốn giao dịch T1 , T2 , T3 , T4. Các cung được xác định như sau: 
 ở bước (4) T2 mở khoá mục A 
 Bước (5) T3 khoá ghi mục A, T3 phải đi sau T2, có một cung từ T2 đến T3. 
 ở bước (6) T2 mở khoá mục B 
 90 
 Bước (7) T1 các khoá đọc mục B và T4 ở bước (9). Như vậy T1 và T4 phải đi sau T3, 
có một cung từ T2 đến các nút này. 
 ở bước (8) T3 mở khoá mục A, 
 Bước (10) T1 là khoá đọc mục A và khoá ghi mục A của T4 ở bước (14). Như vậy T1 
và T4 phải đi sau T3, có một cung từ T3 đến các nút này. 
 ở bước (13) T1 mở khoá mục A, bước (14) T4 khoá ghi mục A, T4 phải đi sau T1, có 
một cung từ T1 đến T4. 
 T1 T2 
 T4 T3 
 Sắp xếp topo cho đồ thị ta được thứ tự các giao dịch là: T1 T2 T3 T4 
 Giao thức hai pha của mô hình trước cũng có thể áp dụng cho mô hình này. Các khoá 
đọc và khoá ghi đều đi trước bước mở khoá, và điều đó sẽ đảm bảo tính khả tuần tự của 
lịch biểu. 
 Trong mô hình này ta cũng rút ra được qui tắc liên quan đến việc trao khoá như sau: 
 Một khoá đọc trên một mục có thể được trao cho một giao dịch nếu không có khoá ghi 
nào đang được một giao dịch khác giữ trên nó. 
Một khoá ghi trên một mục chỉ có thể được trao cho một giao dịch nếu không có khoá 
đọc hoặc khoá ghi nào đang được một giao dịch khác giữ trên mục đó. 
4.4. Thuật toán điều khiển tương tranh bằng nhãn thời gian 
 Để đảm bảo tính khả tuần tự của các lịch biểu, ngoài các mô hình sử dụng khoá như 
đã trình bày ở trên. Ta còn sử dụng nhãn thời gian (timestamp). ý tưởng chính là gán cho 
mỗi giao dịch một nhãn thời gian, đó chính là điểm bắt đầu của giao dịch. 
 Thiết lập nhãn thời gian 
 Nếu tất cả các giao dịch đều được bộ lập lịch gán nhãn thời gian thì bộ lập lịch sẽ duy 
trì bộ đếm số lượng các giao dịch đã được lập lịch. Khi có một giao dịch mới yêu cầu 
được lập lịch, bộ lập lịch sẽ tăng bộ đếm số lượng này lên một đơn vị và gán trị số đó cho 
giao dịch có yêu cầu. Như vậy, không thể xảy ra trường hợp hai giao dịch có cùng nhãn 
 91 
thời gian, và thứ tự tương đối giữa các nhãn thời gian của các giao dịch cũng chính là thứ 
tự mà các giao dịch được thực hiện. 
 Một cách gán nhãn thời gian khác cho các giao dịch là dùng giá trị của đồng hồ hệ 
thống tại thời điểm bắt đầu giao dịch. 
 Trong trường hợp tồn tại nhiều bộ xếp lịch do hệ thống CSDL chạy trên một máy đa 
bộ xử lý hoặc trong hệ CSDL phân bố, thì ta phải gán thêm một hậu tố duy nhất cho mỗi 
nhãn thời gian. Hậu tố này chính là định danh của bộ xử lý tương ứng. Khi đó, việc đồng 
bộ hoá các bộ đếm hoặc đồng hồ được dùng ở mỗi bộ xử lý là một yêu cầu quan trọng để 
đảm bảo tính khả tuần tự của các lịch biểu. 
 Đảm bảo tính khả tuần tự bằng nhãn thời gian 
 Qui tắc duy trì thứ tự tuần tự của nhãn thời gian như sau. Giả sử ta có một giao dịch 
có nhãn thời gian t đang muốn thực hiện một thao tác X trên một mục có thời điểm đọc tr 
và thời điểm ghi tw thì: 
a/ Cho thực hiện thao tác này nếu: 
 X = Read và t tw hoặc 
 X = Write và t tr và t tw 
 Trong trường hợp trước, đặt thời điểm đọc là t nếu t > trvà trong trường hợp sau, đặt 
thời điểm ghi là t nếu t > tw. 
b/ Không thực hiện gì nếu X = Write và tr t < tw. 
c/ Huỷ bỏ giao dịch này nếu: X = Read và t < tw hoặc 
 X = Write và t < tr 
 Ví dụ : Trong đó RLock được xem là Read, WLock được xem là Write, các bước 
Unlock không tồn tại. Các giao dịch T1, T2 , T3, T4 có các nhãn thời gian lần lượt là 100, 
200, 300, 400. 
 ở bước (1) , T2 (có nhãn thời gian là t = 200) đọc A (có WT = 0), tức t tw. Thao tác 
này là được phép, và vì t > tr (bằng 0) nên RT của A được đặt lại là 200. 
 Tương tự ở bước (2) , T3 (có nhãn thời gian là t = 300) đọc A (có WT = 0), tức t 
tw. Thao tác này là được phép, và vì t > tr (bằng 200) nên RT của A được đặt lại là 300. 
 ở bước (3) , T2 (có nhãn thời gian là t = 200) ghi B (có RT = 0 và WT = 0), tức t 
Tr và t tw. Thao tác này là được phép, vì t > tW (bằng 0) nên WT của B được đặt lại là 
200. 
 92 
 ở bước (4) , T3 (có nhãn thời gian là t = 300) ghi A (có RT = 300 và WT=0), tức t 
Tr và t tw. Thao tác này là được phép, vì t > tW (bằng 0) nên WT của A được đặt lại là 
300. 
 ở bước (5) , T1 (có nhãn thời gian là t = 100) đọc B (có WT = 200), tức 
t < tw. Vì vậy thao tác này bị huỷ bỏ. 
 TT T1 T2 T3 T4 A B C 
 100 200 300 400 RT=0 RT=0 RT=0 
 WT=0 WT=0 WT=0 
 (1) Read A RT=200 
 (2) Read A RT=300 
 (3) Write B WT=200 
 (4) Write A WT=300 
 (5) Read B 
 T1 bị huỷ bỏ 
 Trong quá trình thực hiện giao dịch CSDL có thể tạm thời không nhất quán nhưng 
CSDL phải nhất quán khi giao dịch kết thúc. Tính tin cậy dựa vào hai khả năng sau: 
 + Khả năng phục hồi nhanh của hệ thống khi nhiều kiểu lỗi xảy ra (Khi các lỗi 
xảy ra hệ thống có thể chịu đựng được và có thể tiếp tục cung cấp các dịch vụ ). 
 + Khôi phục: đạt được trạng thái nhất quán. Trở về trạng thái nhất quán trước đó 
hoặc tiếp tới trạng thái nhất quán mới sau khi xảy ra lỗi. Nhất quán về giao tác liên quan 
tới sự thực hiện các truy nhập trùng nhau. 
 Việc quản lý giao tác tiếp xúc với các vấn đề luôn giữ CSDL trong trạng thái 
nhất quán khi xảy ra các truy nhập trùng nhau và các lỗi. 
 93