Tính khả tuần tự của lịch thao tác trong cơ chế Lock

- Đánh dấu tất cả lệnh Unlock.- Xét tuần tự từng lệnh Unlock:o Giả sử đang xét lệnh Unlock (A) của giao tác Ti.o Với mỗi lệnh Lock (A) của các giao tác Tj (j I ) được thực hiện sau lệnhnày, vẽ 1 cung hướng từ Ti  Tj.- Nếu đồ thị không có chu trình  Lịch S khả tuần tự.
Nội dung trích xuất từ tài liệu:
Tính khả tuần tự của lịch thao tác trong cơ chế LockTính khả tuần tự củalịch thao tác trong cơ chế Lock. 1. Cơ chế Lock 2. Cơ chế Lock 2 giai đoạn (2 Phases Locking) 3. Bài tập và hướng dẫn: CHÚ Ý:Quy ước:Để thuận lợi cho việc biểu diễn các thao tác theo thời gian, 1 thao tác được viết dưới dạng MiTj.Trong đó: - M là tên thao tác, có thể là Read, Write, Lock, Unlock, Rlock … - Với i là thứ tự theo thời gian từ trên xuống. - Với j là mã số của giao tác, ví dụ T1,T2 … Tj. TÍNH KHẢ TUẦN TỰ CỦA LỊCH THAO TÁC TRONG CƠ CHẾ LOCKI. CƠ CHẾ LOCK :1. Đặc điểm: Chỉ xét các thao tác Lock và Unlock để xét tính khả tuần tự của lịch.2. Đồ thị khả tuần tự ( cơ chế lock ) - S là tập các giao tác T1,T2,T3…Tn - Xét các thao tác Mi có dạng Lock(A) và Unlock(A). - Nếu Ti có 1 thao tác dạng Unlock(A), Tj có thao tác tiếp theo sau đó có dạng Lock(A) thì vẽ 1 cung có hướng từ Ti Tj . - Lịch thao tác khả tuần tự  đồ thị không có chu trình . Ví dụ 1: Time T1 T2 1 Lock(A) 2 Read (A)  a1 3 Unlock(A) 4 Lock(A) 5 Read(A)  a2 6 a2 + 1  a2 7 Write(a2)  A 8 Unlock(A) 9 a1 + 1  a1 10 Lock(A) 11 Write(a1) A 12 Unlock(A) Hướng dẫn: - T1 thực hiện Unlock3T1(A) sau đó T2 thực hiện Lock4T2(A)  ta có : T1  T2 - T2 thực hiện Unlock8T2(A) sau đó T1 thực hiện Lock10T1(A)  ta có: T2  T1 - Kết luận: Đồ thị có chu trình  Lịch S không khả tuần tự. 3. Cách xây dựng đồ thị khả tuần tự: - Đánh dấu tất cả lệnh Unlock. - Xét tuần tự từng lệnh Unlock: o Giả sử đang xét lệnh Unlock (A) của giao tác Ti. o Với mỗi lệnh Lock (A) của các giao tác Tj (j I ) được thực hiện sau lệnh này, vẽ 1 cung hướng từ Ti  Tj. - Nếu đồ thị không có chu trình  Lịch S khả tuần tự.Ví dụ 2: Cho lịch S như sau. Xét tính khả tuần tự của lịch S. Time T1 T2 T3 T4 1 Lock(A) 2 Lock(A) 3 Lock(B) 4 Unlock(A) 5 Unlock(B) 6 Lock(B) 7 Unlock(A) 8 Lock(B) 9 Lock(A) 10 Unlock(B) 11 Lock(C) 12 Unlock(A) 13 Lock(A) 14 Unlock(A) 15 Unlock(B) 16 Unlock(C)  HƯỚNG DẪN:B1. Đánh dấu ( tô đậm như trên hình vẽ trên)B2: Lần lượt xét các Unlock ( có dạng UnlockxTy(X) với x là thứ tự thời gian và y là thứ tự giao tác):  Xét Unlock4T2(A) của T2 trên ĐVDL là A: o Ta có: Lock9T1(A) và Lock13T4(A) thực hiện sau thao tác đó nên  Ta có 2 cung sau: T2  T1 và T2  T4  Xét Unlock5T2(B) của T2 trên ĐVDL là B: o Ta có: Lock6T1(B) và Lock8T4(B) thực hiện sau thao tác đó nên  Ta có 2 cung sau: T2 T1 và T2 T4  Xét Unlock7T3(A) của T3 trên ĐVDL là A: o Ta có: Lock9T1(A) và Lock13T4(A) thực hiện sau thao tác đó nên  Ta có 2 cung sau: T3  T1 và T3  T4  Xét Unlock10T4(B) của T4 trên ĐVDL là B: o Sau thao tác trên không có giao tác Tj nào thực hiện Lock(B) nên ta không tìm được thêm cung nào.  Xét Unlock12T1(A) của T1 trên ĐVDL là A: o Ta có: Lock13T4(A) thực hiện sau thao tác trên nên ta có cung : T1T4  Xét các Unlock14T4(A), Unlock15T1(B) và Unlock16T1(C) ta có: o Sau các thao tác này không có các giao tác khác thực hiện Lock trên ĐVDL tương ứng nên ta không tìm được thêm cung nào nữa.B3: Vẽ đồ thị.Sau bước 2 ta có các cung và đồ thị tương ứng sau: Cung ĐVDL T2T1 A,B T2T4 A,B T3T1 A T3T4 A T1T4 B Nhận xét đồ thị không có chu trình:  Lịch S khả tuần tự theo thứ tự thực hiện sau:  T2  T3  T1  T4 ...