tailieunhanh - Bài giảng Lập trình đồng thời và phân tán: Bài 2 - Lê Nguyễn Tuấn Thành

Bài giảng "Lập trình đồng thời và phân tán - Bài 2: Bài toán loại trừ lẫn nhau" cung cấp cho người học các kiến thức: Bài toán loại trừ lẫn nhau trong những hệ thống chia sẻ bộ nhớ, giải pháp cho bài toán loại trừ lẫn nhau. . | Bài giảng Lập trình đồng thời và phân tán: Bài 2 - Lê Nguyễn Tuấn Thành LẬP TRÌNH ĐỒNG BÀI 2: BÀI TOÁN LOẠI THỜI TRỪ LẪN NHAU & 1 PHÂN TÁN Giảng viên: Lê Nguyễn Tuấn Thành Email: thanhlnt@ NỘI DUNG 1. Bài toán loại trừ lẫn nhau trong những hệ thống chia sẻ bộ nhớ 2. Giải pháp cho bài toán loại trừ lẫn nhau Bài giảng có sử dụng hình vẽ trong cuốn sách “Concurrent and Distributed Computing in Java, Vijay K. 2 Garg, University of Texas, John Wiley & Sons, 2005” Thách thức trong các chương trình đồng thời ▪ Đồng bộ sự thực thi của các luồng khác nhau ▪ Cho phép các luồng giao tiếp với nhau thông qua bộ nhớ chia sẻ 3 Phần 1. 4 Bài toán loại trừ lẫn nhau Mutual Exclusion Problem - Mutex “Lost update” Problem (1) ▪ Nguyên nhân: Race condition ▪ Xét tình huống: ▪ Có một biến chia sẻ x với giá trị ban đầu là 0 ▪ Có hai luồng T0 và T1 đều tăng giá trị của x lên 1 ▪ Liệu giá trị của x sau khi thực thi T0 và T1 sẽ là 2? 5 Luồng T0 Luồng T1 “Lost update” Đọc giá trị x vào một thanh Problem (2) ghi (giá trị được đọc: 0) Tăng thanh ghi (1) Ghi giá trị trong thanh ghi ngược lại x (x=1) Đọc giá trị x vào một thanh ghi (giá trị được đọc: 1) Tăng thanh ghi (2) Ghi giá trị trong thanh ghi ngược lại x (x=2) 6 Luồng T0 Luồng T1 “Lost update” Đọc giá trị x vào một thanh Problem (3) ghi (giá trị được đọc: 0) Tăng thanh ghi (1) Đọc giá trị x vào một thanh ghi (giá trị được đọc: 0) Tăng thanh ghi (1) Ghi giá trị trong thanh ghi ngược lại x (x=1) Ghi giá trị trong thanh ghi ngược lại x (x=1) 7 Làm sao để tránh vấn đề mất mát dữ liệu? ▪ Câu lệnh x = x +1 phải được thực thi một cách nguyên tử (atomically) ▪ Mở rộng ra, nếu một phần mã cần được thi thực một cách nguyên tử thì phần mã đó được gọi là: khu vực quan trọng (Critical Region - CR) hay phần quan trọng (Critical Section - CS) ▪ Cho ví dụ về CS ??? 8 Bài toán loại trừ lẫn nhau (Mutex) ▪ Là bài toán nhằm