0.6 Đồng bộ hóa quá trình  (Page 5/15)

Để chứng minh thuộc tính 2 và 3, chúng ta chú ý rằng một quá trình Pi có thể được ngăn chặn từ việc đi vào miền tương truc chỉ nếu nó bị kẹt trong vòng lặp while với điều kiện flag[j] == true và turn == j. Nếu Pj không sẳn sàng đi vào miền tương trục thì flag[j]== false và Pi có thể đi vào miền tương trục của nó. Nếu Pj đặt flag[j] là true và nó cũng đang thực thi trong câu lệnh while của nó thì turn == i hay turn == j. Nếu turn == ithì Pi sẽ đi vào miền tương trục. Nếu turn ==j thì Pj sẽ đi vào miền tương trục. Tuy nhiên, một khi Pj ở trong vùng tương trục của nó thì nó sẽ đặt lại flag[j] tới false, cho phép Pi đi vào miền tương trục của nó. Nếu Pj đặt lại flag[j]tới true, nó cũng phải đặt turn tới i. Do đó, vì Pi không thay đổi giá trị của biến turn trong khi thực thi câu lệnh while, nên Pi sẽ đi vào miền tương trục (tiến trình) sau khi nhiều nhất chỉ Pj đi vào (chờ có giới hạn).

Giải pháp nhiều quá trình

Giải thuật 3 giải quyết vấn đề miền tương trục cho hai quá trình. Bây giờ chúng ta phát triển một giải thuật để giải quyết vấn đề miền tương trục cho n quá trình. Giải thuật này được gọi là giải thuật Bakery và nó dựa trên cơ sở của giải thuật định thời thường được dùng trong cửa hiệu bánh mì, cửa hàng kem,..nơi mà thứ tự rất hỗn độn. Giải thuật này được phát triển cho môi trường phân tán, nhưng tại thời điểm này chúng ta tập trung chỉ những khía cạnh của giải thuật liên quan tới môi trường tập trung.

Đi vào một cửa hàng, mỗi khách hàng nhận một số. Khách hàng với số thấp nhất được phục vụ tiếp theo. Tuy nhiên, giải thuật Bakery không thể đảm bảo hai quá trình (khách hàng) không nhận cùng số. Trong trường hợp ràng buộc, một quá trình với tên thấp được phục vụ trước. Nghĩa là, nếu Pi và Pj nhận cùng một số và nếu (i<j) thì Pi được phục vụ trước. Vì tên quá trình là duy nhất và được xếp thứ tự nên giải thuật là hoàn toàn mang tính “may rủi” (deterministic).

Cấu trúc dữ liệu chung là

booleanchoosing[n];

intnumber[n];

Đầu tiên, các cấu trúc dữ liệu này được khởi tạo tới false và 0 tương ứng. Để tiện dụng, chúng ta định nghĩa các ký hiệu sau:

• (a, b)<(c, d) nếu a<c hay nếu a==c và b<d
• max(a0,…,an-1) là số k  ai với i = 0,…,n-1

Cấu trúc của quá trình Pi được dùng trong giải thuật Bakery, được hiển thị trong hình dưới đây.

Hình V‑6 Cấu trúc của giải thuật Pi trong giải thuật Bakery

Kết quả được cho này thể hiện rằng loại trừ hỗ tương được tuân theo. Thật vậy, xét Pi trong vùng tương trục của nó và Pk cố gắng đi vào vùng tương trục Pk­. Khi quá trình Pk thực thi câu lệnh while thứ hai cho j==i, nhận thấy rằng

• number[ i ] != 0
• (number[ i ], i )<(number[k], k).

Do đó, nó tiếp tục vòng lặp trong câu lệnh while cho đến khi Pi rời khỏi vùng tương trục Pi.