| << Chapter < Page | Chapter >> Page > |
Chúng ta có thể sử dụng semaphores để giải quyết vấn đề miền tương trục với n quá trình. N quá trình chia sẻ một biến semaphore, mutex (viết tắt từ mutual exclusion) được khởi tạo 1. Mỗi quá trình Pi được tổ chức như được hiển thị trong hình dưới đây.
| do{ | ||
| Wait(mutex) | ||
| critical section | ||
| Signal(mutex) | ||
| remainder section | ||
| }while(1); |
Hình V‑13 Cài đặt loại trừ hỗ tương với semaphores
Chúng ta cũng sử dụng semaphores để giải quyết các vấn đề đồng bộ khác nhau. Thí dụ, để xem xét hai quá trình đang thực thi đồng hành: P1 với câu lệnh S1 và P2 với câu lệnh S2. Giả sử chúng ta yêu cầu rằng S2 được thực thi chỉ sau khi S1 hoàn thành. Chúng ta có thể hoàn thành cơ chế này một cách dễ dàng bằng cách P1 và P2 chia sẻ một semaphore chung synch, được khởi tạo 0 và bằng cách chèn các câu lệnh:
S1;
signal(sync);
vào quá trình P1 và các câu lệnh:
wait(synch);
S2;
vào trong quá trình P2. Vì synch được khởi tạo 0. P2 sẽ thực thi S2 chỉ sau khi P1 nạp signal(synch) mà sau đó là S1;
Nhược điểm chính của các giải pháp loại trừ hỗ tương trong phần V.-5.1 và của semaphore được cho ở đây là tất cả chúng đều đòi hỏi sự chờ đợi bận.Để giải quyết yêu cầu cho việc chờ đợi bận, chúng ta có thể hiệu chỉnh định nghĩa của các thao tác wait và signal của semaphore. Khi một quá trình thực thi thao tác wait và nhận thấy rằng nếu giá trị của semaphore không dương, nó phải chờ. Tuy nhiên, thay vì chờ đợi bận, quá trình có thể nghẽn chính nó. Thao tác nghẽn đặt quá trình vào một hàng đợi gắn liền với semaphore và trạng thái quá trình được chuyển tới trạng thái chờ. Sau đó, điều khiển được chuyển tới bộ định thời biểu và bộ định thời biểu chọn một quá trình khác để thực thi.
Một quá trình bị nghẽn chờ trên biến semaphore nên được khởi động lại khi quá trình khác thực thi thao tác signal. Quá trình được khởi động lại bởi thao tác wakeup và chuyển quá trình từ trạng thái chờ sang trạng thái sẳn sàng. Sau đó, quá trình này được đặt vào hàng đợi sẳn sàng. (CPU có thể hay không thể được chuyển từ quá trình đang chạy tới quá trình sẳn sàng mới nhất phụ thuộc vào giải thuật định thời biểu CPU).
Để cài đặt semaphore dưới định nghĩa này, chúng ta định nghĩa một semaphore như một cấu trúc được viết bằng C như sau:
typedef struct{
int value;
struct process *L;
} semaphore;
Mỗi semaphore có một số integer value và một danh sách các quá trình L. Khi một quá trình phải chờ trên một semaphore, nó được thêm vào danh sách các quá trình L. Một thao tác signal xoá một quá trình ra khỏi danh sách các quá trình đang chờ và đánh thức quá trình đó.
Thao tác semaphore wait bây giờ được định nghĩa như sau:
void wait(semaphore S){
S.value--;
If (S.value<0){
Thêm quá trình này tới danh sách các quá trình S.L;
block();
}
}
Thao tác semaphore signal bây giờ có thể được định nghĩa như sau:
void signal(semaphore S){
S.value++;
if(S.value<= 0){
xoá một quá trình ra khỏi hàng đợi S.L;
wakeup(P);
}
}
Thao tác block() tạm dừng quá trình gọi thao tác đó. Thao tác wakeup(P) tiếp tục thực thi quá trình bị nghẽn P. Hai thao tác này được cung cấp bởi hệ điều hành như những lời gọi hệ thống cơ bản.
Notification Switch
Would you like to follow the 'Hệ điều hành' conversation and receive update notifications?
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|