Bài giảng Hệ quản trị cơ sở dữ liệu - Chương 3: Điều khiển truy xuất đồng thời - Nguyễn Trường Sơn
HỆ QUẢN TRỊ CƠ SỞ DỮ LIỆU
Chương 3:
ĐIỀU KHIỂN TRUY
XUẤT ĐỒNG THỜI
GVLT: Nguyễn Trường Sơn
1
Nội dung trình bày
§ꢀ Phân loại các vấn đề của truy xuất đồng thời
§ꢀ Các kỹ thuật điều khiển đồng thời:
–ꢀ Kỹ thuật khoá (Locking)
–ꢀ Kỹ thuật nhãn thời gian (Timestamp)
–ꢀ Kỹ thuật xác nhận hợp lệ (Validation)
§ꢀ Vấn đề khoá chết
§ꢀ Các vấn đề khác
2
Nội dung trình bày
§ꢀ Các kỹ thuật điều khiển đồng thời:
–ꢀ Kỹ thuật khoá
–ꢀ Kỹ thuật nhãn thời gian
–ꢀ Kỹ thuật xác nhận hợp lệ
§ꢀ Vấn đề khoá chết
§ꢀ Các vấn đề khác
3
Vấn đề mất dữ liệu đã cập nhật
§ꢀ Xét 2 giao tác T1 và T2 và đơn vị dữ liệu A vốn có giá trị
ban đầu là 50:
–ꢀ T1: Read(A); A:=A+10; Write(A)
A=50
t1
T1
T2
–ꢀ T2: Read(A); A:=A+20; Write(A)
Read(A)
«ꢀNếu T1 và T2 thực hiện tuần tự
(T1 rồi T2 hoặc T2 rồi T1) thì
cuối cùng A = 80
t2
Read(A)
A:=A+20
Write(A)
t3
A:=A+10
Write(A)
t4
«ꢀNếu T1 và T2 thực hiện đồng
t5
thời như lịch bên: A = 70
t6
Nhận xét:
²ꢀDữ liệu do T1 ghi đã bị T2 làm mất
4
²ꢀLỗi: MẤT DỮ LIỆU CẬP NHẬT (LOST UPDATE)
Vấn đề không thể đọc lại
§ꢀ Xét 2 giao tác T1 và T2 và đơn vị dữ liệu A vốn có giá trị
ban đầu là 50
A=50
t1
T1
T2
«ꢀKết quả quan sát:
²ꢀ Nếu T1 và T2 thực hiện
tuần tự thì các lần đọc A của
T2 giống nhau.
Read(A)
t2
Read(A) A=50
Print(A) A=50
t3
A:=A-10
Write(A)
t4
²ꢀ Nếu T1 và T2 thực hiện
đồng thời như lịch bên à 2
lần đọc dữ liệu của T2 có
kết quả khác nhau
t5
t6
Read(A) A=40
Print(A) A=40
t7
«ꢀLỗi không đọc lại được dữ liệu:
²ꢀ Trong một giao tác mà các lần đọc cùng 1 đơn vị dữ liệu cho kết
quả khác nhau
5
Vấn đề “bóng ma”
§ꢀ Xét 2 giao tác T1 và T2 được xử lý đồng thời
–ꢀ A là một tập các đơn vị dữ liệu a1, a2, a3, a4, …
–ꢀ T1 xử lý trên toàn bộ tập A
–ꢀ Khi T1 đang xử lý, T2 thêm hay xóa một hay một số phần tử trong
tập A
T1
T2
t1
t2
t3
t4
t5
t6
Read(A)
Xử lý 1 trên A
Thêm ai vào A
Xoá aj khỏi A
Xử lý 2 trên A
Xử lý 3 trên A
6
Vấn đề đọc dữ liệu rác
§ꢀ Xét 2 giao tác T1 và T2 được xử lý đồng thời
–ꢀ T2 đã đọc dữ liệu được ghi bởi T1 nhưng sau đó T1 yêu cầu hủy
việc ghi
A=50
t1
T1
T2
Read(A)
A:=A+10
Write(A)
t2
t3
t4
Read(A)
Print(A)
t5
t6
Abort
7
Nhận xét
§ꢀ Các lỗi truy xuất đồng thời của các giao tác T1, …, Tn là do:
–ꢀ Kết quả của lịch tuần tự được lập từ các giao tác T1, …, Tn và lịch
đồng thời S từ các giao đó khác nhau: Không đảm bảo tính nhất
quán dữ liệu.
–ꢀ Lịch đồng thời S không phải là một lịch khả tuần tự.
§ꢀ Câu hỏi:
–ꢀ Làm sao bộ lập lịch có thể tạo được một lịch S khả tuần tự ?
Các kỹ thuật điều khiển đồng thời
8
Các kỹ thuật điều khiển đồng thời
§ꢀ Là những kỹ thuật cho phép bộ lập lịch sử dụng để tạo một
lịch khả tuần tự từ n giao tác thực hiện đồng thời.
T1 T2 …
Tn
Kỹ thuật khoá
Bộ lập lịch
Kỹ thuật nhãn thời gian
Kỹ thuật xác nhận hợp lệ
Lịch khả
tuần tự
9
Nội dung trình bày
§ꢀ Các vấn đề của truy xuất đồng thời
§ꢀ Vấn đề khoá chết
§ꢀ Các vấn đề khác
10
Kỹ thuật khoá đơn giản
§ꢀ Kỹ thuật khoá đơn giản còn gọi khoá nhị phân (Binary locks)
§ꢀ Bộ lập lịch với cơ chế khóa đơn giản (locking scheduler)
–ꢀ Là bộ lập lịch với thêm 2 hành động :
-ꢀLock : Phát khoá
-ꢀUnlock : Giải phóng khóa
–ꢀ Các khóa được ghi nhận trong bảng khóa (Lock Table)
T1 T2 …
Tn
Bảng
khóa
Bộ lập lịch
Lịch khả
tuần tự
11
Kỹ thuật khóa đơn giản
§ꢀ Quy định:
–ꢀ Các giao tác trước khi muốn đọc/ghi lên 1 đơn vị dữ liệu phải phát
ra 1 yêu cầu xin khóa (lock) đơn vị dữ liệu đó
-ꢀKý hiệu: Lock(A) hay l(A)
–ꢀ Yêu cầu này được bộ phận quản lý khóa xử lý (Lock Manager)
-ꢀNếu yêu cầu được chấp thuận thì giao tác mới được phép đọc/ghi lên
đơn vị dữ liệu
-ꢀYêu cầu xin khóa được bộ cấp phát chấp thuận nếu đơn vị dữ liệu chưa
bị khóa bởi một giao tác nào khác
–ꢀ Sau khi thao tác xong thì giao tác phải phát ra lệnh giải phóng đơn
vị dữ liệu (unlock)
BẢNG KHÓA
-ꢀKý hiệu: Unlock(A) hay u(A)
Element
A
Transaction
T1
Bảng khóa ghi nhận giao
tác T1 đang giữ khóa
trên đơn vị dữ liệu A
12
Kỹ thuật khóa đơn giản (tt)
§ꢀ Quy tắc:
–ꢀ 1. Giao tác đúng đắn: Việc giao tác Ti đọc hay ghi lên đơn vị dữ liệu
A phải sau khi Ti phát khoá trên A và trước khi Ti giải phóng khoá
trên A. Phát khoá và giải phóng khoá phải đi đôi với nhau (lock
trước, unlock sau)
-ꢀTi: … l(A) … r(A) / w(A) … u(A) …
–ꢀ 2. Lịch thao tác hợp lệ: Khi Ti đang giữ khoá trên một đơn vị dữ
liệu A thì không Ti nào khác được phát khoá trên A.
-ꢀS: … li(A) ……………………ui(A) …
Không được có lj(A)
13
Kỹ thuật khóa đơn giản (tt)
T1
T2
S
Lock(A)
§ꢀ Ví dụ:
Read(A, t)
t := t + 100
Write(A, t)
Unlock(A)
–ꢀ Giao tác T1 và T2 có đúng
đắn hay không ?
Lock(A)
Read(A, s)
s := s * 2
–ꢀ Lịch S có hợp lệ hay không ?
Write(A, s)
Unlock(A)
Lock(B)
Read(B, s)
s := s * 2
Write(B, s)
Unlock(B)
Lock(B)
Read(B, t)
t := t + 100
Write(B, t)
Unlock(B)
14
Kỹ thuật khóa đơn giản (tt)
§ꢀ Ví dụ
S2
T1
T2
T3
T1
T2
T3
S1
Lock(A)
Lock(B)
Read(A)
Write(B)
Lock(A)
Read(A)
Write(B)
Unlock(A)
Unlock(B)
Lock(B)
Unlock(A)
Unlock(B)
Lock(B)
Read(B)
Write(B)
Read(B)
Write(B)
Unlock(B)
Lock(B)
Read(B)
Lock(B)
Unlock(B)
Read(B)
Unlock(B)
Cho biết lịch nào hợp lệ? Giao tác nào là đúng đắn ?
15
Kỹ thuật khóa đơn giản (tt)
§ꢀ Ví dụ:
S2
T1
T2
T3
T1
T2
T3
S1
Lock(A)
Lock(B)
Read(A)
Write(B)
Lock(A)
Read(A)
Write(B)
Unlock(A)
Unlock(B)
Lock(B)
Unlock(A)
Unlock(B)
Lock(B)
Read(B)
Write(B)
Read(B)
Write(B)
Unlock(B)
ock(B)
Read(B)
Lock(B)
Read(B)
Unlock(B)
Unlock(B)
Cho biết lịch nào hợp lệ? Giao tác nào là đúng đắn ?
16
Kỹ thuật khóa đơn giản (tt)
§ꢀ Bài toán: Kiểm tra tính khả tuần tự của lịch S
–ꢀ Input: Lịch S được lập từ n giao tác xử lý đồng thời T1, T2, …, Tn theo
kỹ thuật khóa đơn giản
–ꢀ Output: S khả tuần tự hay không?
§ꢀ Phương pháp: Xây dựng 1 đồ thị có hướng G
–ꢀ B1: Mỗi giao tác Ti là 1 đỉnh của đồ thị
–ꢀ B2: Nếu một giao tác Tj phát ra Lockj(A) sau một giao tác Ti phát ra
Unlock (A) thì sẽ vẽ cung từ Ti đến Tj , i ≠ j
i
–ꢀ B3: S khả tuần tự nếu G không có chu trình
17
Kỹ thuật khóa đơn giản (tt)
T1
T2
S
Lock(A)
Lịch S có khả tuần tự hay không ?
Read(A, t)
t := t + 100
Write(A, t)
Unlock(A)
Lock(A)
Read(A, s)
s := s * 2
Write(A, s)
Unlock(A)
Lock(B)
Read(B, s)
s := s * 2
Write(B, s)
Unlock(B)
Lock(B)
Read(B, t)
t := t + 100
Write(B, t)
Unlock(B)
18
Kỹ thuật khóa đơn giản (tt)
T1
T2
S
Lock(A)
Lịch S có khả tuần tự hay không ?
Read(A, t)
t := t + 100
Write(A, t)
Unlock(A)
Lock(A)
Read(A, s)
s := s * 2
Write(A, s)
Unlock(A)
Lock(B)
B1
B2
T1
T2
G
Read(B, s)
s := s * 2
Write(B, s)
Unlock(B)
B3
G có chu trình à S không khả tuần
tự
Lock(B)
Read(B, t)
t := t + 100
Write(B, t)
Unlock(B)
19
Kỹ thuật khóa đơn giản (tt)
§ꢀ Mục tiêu: Vậy làm sao để kỹ thuật khóa cho ta lịch khả
tuần tự
§ꢀ Giải pháp : Tuân theo quy tắc sau:
–ꢀ (1) và (2): Giống như cũ
–ꢀ (3) Giao tác phải thỏa nghi thức khóa 2 giai đoạn (2PL: two
phases locking) : Trong 1 giao tác, tất cả các thao tác phát khóa
đều xảy ra trước tất cả các thao tác giải phóng khóa.
T : …………(A) l(B)…………………u(A) u(B)……………
Không có giải
phóng bất kỳ
khóa nào
Không có phát
ra bất kỳ
khóa nào
§ꢀ Định lý:
20
–ꢀ Nếu lịch S thoả nghi thức 2PL thì S conꢀlict-serializable
Tải về để xem bản đầy đủ
97 trang
17680
Free
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Hệ quản trị cơ sở dữ liệu - Chương 3: Điều khiển truy xuất đồng thời - Nguyễn Trường Sơn", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_he_quantri_co_sodulieu_chuong_3_dieu_khientruy_xua.pdf
