Bài giảng "Lập trình đồng thời và phân tán - Bài 7: Bài toán sắp thứ tự thông điệp" cung cấp cho người học các kiến thức: Thứ tự FIFO, thứ tự nhân quả, thứ tự đồng bộ, thứ tự toàn bộ cho thông điệp multicast. . | Bài giảng Lập trình đồng thời và phân tán: Bài 7 - Lê Nguyễn Tuấn Thành LẬP TRÌNH BÀI 7: ĐỒNG BÀI TOÁN SẮP THỨ THỜI TỰ THÔNG ĐIỆP & 1 PHÂN TÁN Giảng viên: Lê Nguyễn Tuấn Thành Email: thanhlnt@ Tính không xác định (1) ▪ Các chương trình phân tán khó thiết kế và kiểm thử bởi tính chất không xác định của nó ▪ Nguyên nhân: do thứ tự khác nhau của các thông điệp trong mỗi lần thực thi ▪ Một tính toán bất đồng bộ hoàn toàn không có bất kỳ giới hạn nào về thứ tự thông điệp ▪ Cho phép tối đa sự đồng thời ▪ Tuy nhiên: KHÓ thiết kế những thuật toán cho thứ tự giao tiếp bất đồng bộ hoàn toàn ▪ Do các thuật toán này phải tính đến tất cả thứ tự có thể có trong việc truyền thông điệp 2 Tính không xác định (2) Mong muốn: kiểm soát tính chất không xác định của các chương trình phân tán ▪ Bằng cách kiểm soát các kiểu thứ tự thông điệp có thể có trong hệ thống phân tán 3 NỘI DUNG ▪ Thứ tự FIFO ▪ Thứ tự nhân quả ▪ Thứ tự đồng bộ ▪ Thứ tự toàn bộ cho thông điệp multicast ▪ Thuật toán tập trung ▪ Thuật toán của Lamport ▪ Thuật toán của Skeen Bài giảng có sử dụng hình vẽ trong cuốn sách “Concurrent and Distributed Computing in Java, Vijay K. Garg, 4 University of Texas, John Wiley & Sons, 2005” 5 Thứ tự FIFO FIFO ordering Thứ tự FIFO ▪ Nhiều hệ thống phân tán giới hạn việc phân phối thông điệp theo thứ tự FIFO ▪ Giúp đơn giản hoá thiết kế thuật toán ▪ Ví dụ: chúng ta đã sử dụng giả thiết thứ tự FIFO trong thuật toán của Lamport cho bài toán truy cập tài nguyên chia sẻ ▪ Tuy nhiên: chương trình sẽ mất đi một vài tính chất đồng thời ▪ Khi nhận được một thông điệp không tuân theo thứ tự FIFO, việc xử lý phải bị trì hoãn 6 Thứ tự FIFO Định nghĩa ▪ 7 Thứ tự FIFO Thuật toán (1) ▪ Mỗi tiến trình lưu một ma trận M[1N, 1N] ▪ Phần tử M[j,k] tại tiến trình Pi lưu lại số lượng thông điệp được gửi từ tiến trình Pj cho tiến trình Pk, được biết bởi tiến trình Pi 8 Thứ tự FIFO Thuật toán .
