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

Trong giải thuật này, quá trình Pi trước tiên thiết lập flag[i] tới true, hiển thị rằng nó sẳn sàng đi vào miền tương trục. Sau đó, Pi kiểm tra rằng quá trình quá trình Pj cũng không sẳn sàng đi vào miền tương trục của nó. Nếu Pj sẳn sàng thì Pi sẽ chờ cho tới khi Pj hiển thị rằng nó không còn cần ở trong vùng tương trục nữa (nghĩa là cho tới khi flag[j]là false). Tại thời điểm này, Pi sẽ đi vào miền tương trục. Thoát ra khỏi miền tương trục, Pi sẽ đặt flag[i] là false, cho phép quá trình khác (nếu nó đang chờ) đi vào miền tương trục của nó.

Trong giải pháp này, yêu cầu loại trừ hỗ tương sẽ được thoả mãn. Tuy nhiên, yêu cầu tiến trình không được thoả mãn. Để minh hoạ vấn đề này, chúng ta xem xét thứ tự thực thi sau:

T0: P0 thiết lập flag[0] = true;

T1: P1 thiết lập flag[1] = true;

Bây giờ P0 và P1 được lập mãi mãi trong câu lệnh while tương ứng của chúng.

Giải thuật này phụ thuộc chủ yếu vào thời gian chính xác của hai quá trình. Thứ tự này được phát sinh trong môi trường nơi có nhiều bộ xử lý thực thi đồng hành hay nơi một ngắt (chẳng hạn như một ngắt định thời) xảy ra lập tức sau khi bước T0 được thực thi và CPU được chuyển từ một quá trình này tới một quá trình khác.

Chú ý rằng chuyển đổi thứ tự của các chỉ thị lệnh để thiết lập flag[i] và kiểm tra giá trị của flag[j]sẽ không giải quyết vấn đề của chúng ta. Hơn nữa chúng ta sẽ có một trường hợp đó là hai quá trình ở trong vùng tương trục cùng một lúc, vi phạm yêu cầu loại trừ hỗ tương.

Giải thuật 3

Giải thuật 3 còn gọi là giải pháp Peterson. Bằng cách kết hợp hai ý tưởng quan trọng trong giải thuật 1 và 2, chúng ta đạt được một giải pháp đúng tới với vấn đề vùng tương trục, ở đó hai yêu cầu được thoả. Các quá trình chia sẻ hai biến:

Boolean flag[2]

Int turn;

Khởi tạo flag[0] = flag[1]= false và giá trị của turn là không xác định (hoặc là 0 hay 1). Cấu trúc của quá trình Pi được hiển thị trong hình sau:

do{flag[i] = true;turn = j;while (flag[j]&&turn ==j);critical sectionflag[i] = false;remainder section} while (1);

Hình V‑4 Cấu trúc của quá trình Pi trong giải thuật 3

Để đi vào miền tương trục, quá trình Pi trước tiên đặt flag[i] là true sau đó đặt turn tới giá trị j, do đó xác định rằng nếu quá trình khác muốn đi vào miền tương trục nó. Nếu cả hai quá trình đi vào miền tương trục cùng một lúc turn sẽ đặt cả hai i và j tại xấp xỉ cùng một thời điểm. Chỉ một trong hai phép gán này là kết quả cuối cùng. Giá trị cuối cùng của turn quyết định quá trình nào trong hai quá trình được cho phép đi vào miền tương trục trước.

Bây giờ chúng ta chứng minh rằng giải pháp này là đúng. Chúng ta cần hiển thị rằng:

1. Loại trừ hỗ tương được bảo toàn
2. Yêu cầu tiến trình được thoả
3. Yêu cầu chờ đợi có giới hạn cũng được thoả

Chứng minh thuộc tính 1, chúng ta chú ý rằng mỗi Pi đi vào miền tương trục của nó chỉ nếu flag[j] ==false hay turn ==i. Cũng chú ý rằng, nếu cả hai quá trình có thể đang thực thi trong vùng tương trục của chúng tại cùng thời điểm thì flag[0]== flag[1] ==true. Hai nhận xét này ngụ ý rằng P0 và P1 không thể thực thi thành công trong vòng lặp while của chúng tại cùng một thời điểm vì giá trị turn có thể là 0 hay 1. Do đó, một trong các quá trình-Pj phải được thực thi thành công câu lệnh while, ngược lại Pi phải thực thi ít nhất câu lệnh bổ sung (“turn==j”). Tuy nhiên, vì tại thời điểm đó, flag[j]==true và turn ==j, và điều kiện này sẽ không đổi với điều kiện là Pj ở trong vùng miền tương trục của nó, kết quả sau việc loại trừ hỗ tương được bảo vệ