zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Công Nghệ Thông Tin

» Cơ sở dữ liệu

Bài giảng Cơ sở dữ liệu phân tán: Chương 6 - Nguyễn Mậu Hân

Chia sẻ: Nguyễn Minh | Ngày: | Loại File: PPT | Số trang:36

Báo xấu

162
lượt xem 36
download

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

Chương 6 Điều khiển tương tranh phân tán thuộc bài giảng Cơ sở dữ liệu phân tán. Nội dung chương này trình bày về: một số vấn đề điều khiển đồng thời, một số tính chất khi thao tác trên đơn vị dữ liệu, lịch tuần tự và lịch khả tuần tự, sắp xếp các giao tác bằng nhãn thời gian, điều khiển tương tranh bằng cơ chế khóa.

Chủ đề:

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

Lưu

Nội dung Text: Bài giảng Cơ sở dữ liệu phân tán: Chương 6 - Nguyễn Mậu Hân

CHƯƠNG 6: ĐIỀU KHIỂN TƯƠNG TRANH NGUYỄN MẬU HÂN, PhD. HUE COLLEGE OF SCIENCES HUE UNIVERSITY
CONTENTS  1. Một số vấn đề điều khiển đồng thời  2. Một số tính chất khi thao tác trên đơn vị dữ liệu  3. Lịch tuần tự và lịch khả tuần tự  4. Sắp xếp các giao tác bằng nhãn thời gian  5. Điều khiển tương tranh bằng cơ chế khóa
CHƯƠNG 6: ĐiỀU KHIỂN TƯƠNG TRANH MỤC ĐÍCH 3
Giới thiệu  Giao tác là một tập hợp các thao tác có thứ tự truy xuất dữ liệu trên CSDL thành một đơn vị công việc logic (xem là một thao tác nguyên tố), chuyển CSDL từ trạng thái nhất quán này sang trạng thái nhất quán khác.  Nguyên lý điều khiển tương tranh: Là quá trình điều khiển giúp cho nhiều giao tác diễn ra đồng thời mà không xảy ra tranh chấp.
Giới thiệu Mất dữ liệu (Lost ảy ra khi Điều gì x update) có sự đụng (Livelock) Khóa chờ độ? Khóa chết (Deadlock)
Giới thiệu Để ghi nhận sự hoàn tất hay không của một thao tác người ta sử dụng các lệnh sau: BEGIN TRANSACTION Bắt đầu giao tác COMMIT TRANSACTION Kết thúc một giao tác thành công Kết thúc một giao tác không thành công, những thao tác làm ảnh hưởng CSDL trước ROLLBACK TRANSACTION đó được undo, CSDL được trả về tình trạng trước khi thực hiện giao tác. Chỉ mạng ý nghĩa hình thức, thường không END TRANSACTION sử dụng
1. Một số vấn đề điều khiển đồng thời 1. 1. Mất dữ liệu cập nhật (lost update)ụ: Cho quan hệ HANGHOA (MaHH, Tên Ví d HH, ĐVT, SLTon) Giả sử: SLTon =20 Transaction Gía trị T1 (bán hàng) T2 (bán hàng) x1 x2 SLTon Begin Transaction Begin Transaction 20 Read(SLTon)→x1 20 20 Read(SLTon)→x2 20 20 20 x1 - 10→x1 10 20 20 x2 - 3→x2 10 17 20 Write x1→SLTon 10 17 10 Write x2→SLTon 10 17 17 Commit T1 Commit T2 17  Lost Update: Thao tác cập nhật của T1 xem như bị mất, không được ghi nhận (do những thay đổi của các giao tác khác ghi đè lên).
1. Một số vấn đề điều khiển đồng thời 1.2. Đọc dữ liệu chưa commit (uncommitted data) Ví dụ: Cho quan hệ HANGHOA ( MaHH,TenHH, ĐVT, SLTon) SLton = 20  Transaction Transaction Giá trị T1 sửa đổi dòng T1(nhập hàng) T2 (bán hàng) x1 x2 SLton X nhưng chưa commit, Begin transaction 20 Read (SLton)→ x1 20 20 transaction T2 x1 + 100 → x1 120 20 đọc dòng X. Write x1 → SLton 120 120 Transaction T1 Begin transaction 120 rollback những Read (SLton)→ x2 120 120 gì thay đổi trên x2 – 5 → x2 120 dòng X → dữ Write x2 → SLton 120 115 liệu mà Commit T2 120 Transaction T2 Rollback T1 20 đang đọc chưa hề tồn tại.
1. Một số vấn đề điều khiển đồng thời 1.3. Thao tác đọc không thể lập lại (unrepeatable data) Ví dụ: Xét 2 giao tác sau: T1 T2 Read(A) Read(A) A = A + 10 Print (A) Write (A) Read (A) Print (A) Giả sử A = 20 và 2 giao tác này thực hiện đồng th ời theo th ứ tự sau:
1. Một số vấn đề điều khiển đồng thời 1.3. Thao tác đọc không thể lập lại (unrepeatable data) Transaction Giá trị T1 T2 x1 x2 A Begin transaction 20 Read (A) → x1 20 20 Begin transaction Read (A) → x2 20 20 20 x1 +10 → x1 30 20 Print (x2) 30 20 Write x1 → A 30 30 Read (A) → x2 30 30 Commit T2 30 Commit T1
1. Một số vấn đề điều khiển đồng thời 1.4. Vấn đề bóng ma (phantom) Ví dụ: T1 Transaction thực hiện việc T1 T2 chuyển tiền từ tài Begin transaction khoản A sang tài Read (A) khoản B. Khi T1 A = A – 50 mới chỉ thực hiện Write (A) thao tác trừ số Begin transaction tiền ở tài khoản Read (A) A (chưa cộng số Read (B) tiền vào tài Print (A+B) khoản B) thì T2 Commit T2 Read (B) muốn xem tổng B = B+50 số tiền ở 2 tài Write (B) khoản → Tổng Commit T1 số tiền không chính xác.
1. Một số vấn đề điều khiển đồng thời Như vậy:  Một tiêu chuẩn để lập lịch các giao tác là việc thực hiện đồng thời các giao tác cho kết quả như khi thực hiện tuần tự các giao tác.  Để giải quyết đụng độ thì phải có “Cơ chế điều khiển tương”.
2. Một số tính chất khi thao tác trên đơn vị dữ liệu 2.1. Hai thao tác tương thích Hai thao tác Oi và Oj (Oi € Ti, Oj € Tj) gọi là tương thích nếu và chỉ nếu kết quả của việc thực hiện đồng thời Oi và Oj giống như kết quả của việc thực hiện tuần tự Oi rồi đến Oj hoặc Oj rồi đến Oi. T1 T2 Read A→ a1 Read A→ a2 O11 và O21 là O11 a1 + 1 → a1 a2*2 → a2 O21 tương thích Print a1 Print a2 O12 và O22 không Read A→ a1 Read A→ a2 O12 a1 + 5 → a1 a2*2 → a2 O22 tương thích Write a1→ A Write a2→ A O13 và O23 không Read A→ a1 Read A→ a2 O13 a1 + 2 → a1 a2 + 7 → a2 O23 tương thích Write a1→ A Write a2→ A O14 tương thích với Read B→ b1 các thao tác còn lại O14 b1 + 1 → b1
2. Một số tính chất khi thao tác trên đơn vị dữ liệu 2.2. Hai thao tác khả hoán vị  Hai thao tác Oi và Oj (Oi thuộc Ti, Oj thuộc Tj) là khả hoán vị nếu kết quả thực hiện Oi ,Oj hay Oj, Oi là như nhau. T1 T2 Read A→ a1 Read A→ a2 O11 a1 + 1 → a1 a2*2 → a2 O21 O11 và O21 là khả Print a1 Print a2 hoán vị O12 và O22 không Read A→ a1 Read A→ a2 khả hoán vị O12 a1 + 5 → a1 a2*2 → a2 O22 O13 và O23 là khả Write a1→ A Write a2→ A hoán vị Read A→ a1 Read A→ a2 O14 khả hoán vị O13 a1 + 2 → a1 a2 + 7 → a2 O23 với các thao tác còn Write a1→ A Write a2→ A lại Read B→ b1 O14 b1 + 1 → b1 Write b1→ B
2. Một số tính chất khi thao tác trên đơn vị dữ liệu Nhận xét: ao tác truy xuất các đơn vị dữ liệu khác nhau là t ương thích và kh ả h Các thao tác truy xuất trên cùng đơn vị dữ liệu: •Nếu có liên quan đến phép cộng, trừ thì khả hoán vị •Read – Read → khả hoán vị •Write – Write → không có tính khả hoán vị •Read – Write → không có tính khả hoán vị •Write – Read → không có tính khả hoán vị Chú ý: Hai thao tác không khả hoán vị thì gọi là xung đột
3. Lịch tuần tự và lịch khả tuần tự 3.1. Lịch tuần tự (serial schedule)  Một lịch S được lập từ n giao tác T1, T2,….,Tn xử lí đồng thời gọi là lịch tuần tự nếu các thao tác của từng giao tác được thực hiện liên tiếp nhau. Ti Tj Tk Ti Tj Tk R(x) R(x) W(x) R(x) R(y) W(y) R(x) R(y) W(y) W(x) R(y) Tuần tự W(x) Không tuần tự
3. Lịch tuần tự và lịch khả tuần tự 3.2. Lịch khả tuần tự (serializable schedule)  Một lịch S được lập từ n giao tác T1, T2,….,Tn xử lí đồng thời gọi là lịch khả tuần tự nếu nó cho cùng kết quả với một lịch tuần tự được lập từ n giao tác trên.
3. Lịch tuần tự và lịch khả tuần tự 3.2. Lịch khả tuần tự (serializable schedule)  Ví dụ 1: Lịch 1 (A = 1, B = 2) Lịch 2 tuần tự (A = 1, B = 2) T1 T2 T1 T2 Read A→ a1 Read A→ a1 a1 + 1 → a1 a1 + 1 → a1 Write a1→ A Write a1→ A Read A→ a2 Read B→ b1 a2*2 → a2 b1 + 1 → b1 Write a2→ A Write b1→ B Read B→ b1 Read A→ a2 b1 + 1 → b1 a2*2 → a2 Write b1→ B Write a2→ A Read B→ b2 Read B→ b2 b2*2 → b2 b2*2 → b2 Write b2→ B Write b2→ B 1 ịch 1 có tính Kết quả Lịch L(A = 4, B = 6) khả tuầtn tự ịch 2 (A = 4, B = 6) Kế quả L
3. Lịch tuần tự và lịch khả tuần tự 3.2. Lịch khả tuần tự (serializable schedule)  Ví dụ 2: Lịch 1 (A = 1, B = 2) Lịch 2 (A = 1, B = 2) T1 T2 T1 T2 Read A→ a1 Read A→ a2 a1 + 1 → a1 a2*2 → a2 Write a1→ A Read A→ a1 Read B→ b1 a1 + 1 → a1 b1 + 1 → b1 Write a2→ A Write b1→ B Read B→ b2 Read A→ a2 b2*2 → b2 a2*2 → a2 Write a1→ A Write a2→ A Read B→ b1 Read B→ b2 b1 + 1 → b1 b2*2 → b2 Write b1→ B Write b2→ B Write b2→ B Kết quả LịLị1 (A 2 4, B = 6) ch ch = không có tính kht quả Lịch 2 ự = 2, B = 4) Kếả tuần t (A
3. Lịch tuần tự và lịch khả tuần tự Như vậy Tính khả tuần tự của các giao tác là điều kiện đủ để tránh đụng độ trong việc truy xuất đồng thời (Một lịch nếu khả tuần tự thì không đụng độ, nếu không có khả tuần tự thì chưa chắc đụng độ) Bộ lập lịch (schedule): Là một bộ phận của DBMS chịu trách nhiệm lập lịch khả tuần tự từ n giao tác xử lí đồng thời, sẽ tiến hành lập lịch các thao tác (thao tác nào sẽ được thực hiện trước, thao tác nào sẽ được thực hiện sau).

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.