Loại trừ lẫn nhau

Chia sẻ: Cao Thi Thao | Ngày: | Loại File: DOC | Số trang:4

Thêm vào BST

Báo xấu

122
lượt xem 6
download

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

Cho giải thuật sau với mục đích giải quyết vấn đề loại trừ lẫn nhau cho hai bộ xử lý p0 và p1 Giải thuật 1 Biến chung phần Turn có giá trị ban đầu là 0 Với mỗi bộ xử lý pi Đoạn vào wait until Turn = i Đoạn ra Turn := 1 - i Giải thuật trên thỏa mãn những tính chất nào sau đây : loại trừ lẫn nhau, không có khóa chết, không có khóa đóng, có cận chờ ? Giải thích vì sao.

Chủ đề:

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

Lưu

Nội dung Text: Loại trừ lẫn nhau

Loại trừ lẫn nhau Cho giải thuật sau với mục đích giải quyết vấn đề loại trừ lẫn nhau cho hai bộ xử lý p0 và p1 Giải thuật 1 Biến chung phần Turn có giá trị ban đầu là 0 Với mỗi bộ xử lý pi Đoạn vào wait until Turn = i Đoạn ra Turn := 1 - i Giải thuật trên thỏa mãn những tính chất nào sau đây : loại trừ lẫn nhau, không có khóa chết, không có khóa đóng, có cận chờ ? Giải thích vì sao.
Giải thuật 1: - Có tính chất loại trừ lẫn nhau: do tại bất kỳ thời điểm nào chỉ có một BXL trong đoạn vào và có ID = Turn nên sẽ vào được đoạn găng - Có khóa chết: vì ta giả thiết BXL i vừa ở trong đoạn găng và ra ngoài, khi đó tại đoạn ra, giá trị Turn = 1-i. Do đó chỉ có BXL 1-i mới có thể vào được đoạn vào (vì Turn lúc này có giá trị là 1-i). Tuy nhiên nếu BXL 1-i không có nhu cầu sử dụng tài nguyên trong khi BXL i lại tiếp tục muốn sử dụng tài nguyên thì BXL i sẽ không bao giờ vào được đoạn vào. Hệ thống sẽ bị deadlock. Do giải thuật có khóa chết nên giải thuật có khóa đóng và không có cận chờ
Giải thuật 2 Biến chung phần Flag[0] và Flag[1] có giá trị ban đầu là true Turn có giá trị ban đầu là 0 Với mỗi bộ xử lý pi Đoạn vào wait until Flag[1 - i] = false or Turn = i Đoạn ra Flag[i] := false Giải thuật trên thỏa mãn những tính chất nào sau đây : loại trừ lẫn nhau, không có khóa chết, không có khóa đóng, có cận chờ ? Giải thích vì sao.
Giải thuật 2 không có tính chất loại trừ lẫn nhau do - Đầu tiên, BXL 0 ở đoạn vào do lúc đầu Turn = 0 - Vì BXL 0 ở đoạn vào nên nếu nó vào đoạn găng và ở đoạn ra thì nó sẽ thiết lập Flag[0] = false, còn Turn = 0 - Tiếp theo, cả hai BXL 0 và 1 đều thỏa mãn điều kiện chờ là wait until Flag[1 - i] = false or Turn = i nên sẽ đều ở đoạn vào và do đó sẽ cùng ở đoạn găng một lúc, vi phạm tính loại trừ lẫn nhau Có khóa chết: Do một BXL đang ở trong đoạn vào thì BXL còn lại chưa chắc sẽ ở trong đoạn găng do giải thuật không có tính chất loại trừ lẫn nhau nên có thể cả hai BXL đều ở trong đoạn vào Vì giải thuật có khóa chết nên có khóa đóng và không có cận chờ