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

Để hiển thị điều này, chúng ta xét một hệ thống chứa hai quá trình P0 và P1, mỗi truy xuất hai semaphore, S và Q, được đặt giá trị 1.

Giả sử rằng P0 thực thi wait(S) và sau đó P1 thực thi wait(Q). Khi P0 thực thi wait(Q), nó phải chờ cho đến khi P1 thực thi signal(Q). Tương tự, khi P1 thực thi wait(S), nó phải chờ cho tới khi P0 thực thi signal(S). Vì các thao tác signal này không thể được thực thi nên P0 và P1 bị khoá chết.

Chúng ta nói rằng một tập hợp các quá trình trong trạng thái khoá chết khi mọi quá trình trong tập hợp đang chờ một sự kiện được gây ra chỉ bởi một quá trình khác trong tập hợp. Những sự kiện mà chúng ta quan tâm chủ yếu ở đây là việc chiếm tài nguyên và giải phóng tài nguyên. Tuy nhiên, các loại sự kiện khác cũng có thể dẫn đến việc khoá chết. Chúng ta sẽ xem trong chương VI. Trong chương đó, chúng ta sẽ mô tả các cơ chế khác nhau để giải quyết vấn đề khoá chết.

Một vấn đề khoá chết liên quan tới khoá chết là nghẽn hay đói tài nguyên không hạn định (indefinite blocking or starvation), ở đó các quá trình chờ đợi không hạn định trong semaphore. Nghẽn không hạn định có thể xảy ra nếu chúng ta thêm vào và lấy ra các quá trình từ danh sách được nối kết với một semaphore trong thứ tự vào sau ra trước (LIFO).

Semaphore nhị phân

Xây dựng semaphore được mô tả trong phần trước được gọi là semaphore đếm (counting semaphore) vì giá trị nguyên có thể trãi dài một phạm vi không giới hạn. Một semaphore nhị phân (binary semaphore) là một semaphore với một giá trị nguyên mà trải dài từ 0 và 1. Semaphore nhị phân có thể đơn giản hơn trong cài đặt so với semaphore đếm và phụ thuộc vào kiến trúc phần cứng nằm bên dưới. Chúng sẽ hiển thị cách một semaphore đếm có thể được cài đặt sử dụng semaphore nhị phân dưới đây:

Giả sử S là một semaphore đếm. Để cài đặt nó trong dạng semaphore nhị phân chúng ta cần các cấu trúc dữ liệu như sau:

Binary-semaphore S1, S2;

int C;

Khởi tạo S1 = 1, S2 = 0 và giá trị nguyên C được đặt tới giá trị khởi tạo của semaphore đếm S.

Thao tác wait trên semaphore đếm S có thể được cài đặt như sau:

wait(S);

C--;

If (C<0) {

signal(S1);

wait(S2);

}

signal(S1);

Thao tác signal trên semaphore đếm S có thể được cài đặt như sau:

wait(S1);

C++;

if (C<=0)

signal(S2);

else

signal(S1);

Monitors

Để có thể dễ viết đúng các chương trình đồng bộ hoá hơn, Hoare (1974) và Brinch&Hansen (1975) đề nghị một cơ chế đồng bộ hoá cấp cao hơn được cung cấp bởi ngôn ngữ lập trình là monitor. Một monitor được mô tả bởi một tập hợp của các toán tử được định nghĩa bởi người lập trình. Biểu diễn kiểu của một monitor bao gồm việc khai báo các biến mà giá trị của nó xác định trạng thái của một thể hiện kiểu, cũng như thân của thủ tục hay hàm mà cài đặt các thao tác trên kiểu đó. Cú pháp của monitor được hiển thị trong hình dưới đây:

Monitor<tên monitor>

{

khai báo các biến được chia sẻ

procedure P1 (…){

…

}

procedure P2 (…){

…

}

.

.

.

procedure Pn (…){

…

}

{

mã khởi tạo

}

}

Hình V‑14 Cú pháp của monỉtor

Biểu diễn kiểu monitor không thể được dùng trực tiếp bởi các quá trình khác nhau. Do đó, một thủ tục được định nghĩa bên trong một monitor chỉ có thể truy xuất những biến được khai báo cục bộ bên trong monitor đó và các tham số chính thức của nó. Tương tự, những biến cục bộ của monitor có thể được truy xuất chỉ bởi những thủ tục cục bộ.