Hình 3.13 Monitor và các biến điều kiện
Cài đặt: trình biên dịch chịu trách nhiệm thực hiện việc truy xuất độc quyền đến dữ liệu trong monitor. Để thực hiện điều này, một semaphore nhị phân thường được sử dụng. Mỗi monitor có một hàng đợi toàn cục lưu các tiến trình đang chờ được vào monitor, ngoài ra, mỗi biến điều kiện c cũng gắn với một hàng đợi f(c) và hai thao tác trên đó được định nghĩa như sau:
Wait(c) :
status(P)= blocked;enter(P,f(c)); Signal(c) :
if (f(c) != NULL){
Có thể bạn quan tâm!
-
Các Socket Và Port Trong Mối Nối Tcp. -
Cấu Trúc Một Chương Trình Sử Dụng Biến Khóa Để Đồng Bộ -
Cấu Trúc Các Tiến Trình Trong Giải Pháp Kiểm Tra Luân Phiên -
Hệ điều hành - Lê Khắc Nhiên Ân - 12 -
Hệ điều hành - Lê Khắc Nhiên Ân - 13 -
Cơ Chế Phần Cứng Hổ Trợ Kĩ Thuật Phân Đoạn
Xem toàn bộ 262 trang tài liệu này.
exit(Q,f(c)); //Q là tiến trình chờ trên cstatusQ) = ready;enter(Q,ready-list);
}
Sử dụng: Với mỗi nhóm tài nguyên cần chia sẻ, có thể định nghĩa một monitor trong đó đặc tả tất cả các thao tác trên tài nguyên này với một số điều kiện nào đó.:
monitor <tên monitor >
condition <danh sách các biến điều kiện>;
<déclaration de variables>; procedure Action1();
{
}
....
procedure Actionn();
{
}
end monitor;
Hình 3.14 Cấu trúc một monitor
Các tiến trình muốn sử dụng tài nguyên chung này chỉ có thể thao tác thông qua các thủ tục bên trong monitor được gắn kết với tài nguyên:
while (TRUE) {
Noncritical-section ();<monitor>.Actioni; //critical-section();Noncritical-section ();
}
Hình 3.15 Cấu trúc tiến trình Pitrong giảipháp monitor
Thảo luận: Với monitor, việc truy xuất độc quyền được bảo đảm bởi trình biên dịch mà không do lập trình viên, do vậy nguy cơ thực hiện đồng bộ hóa sai giảm rất nhiều. Tuy nhiên giải pháp monitor đòi hỏi phải có một ngôn ngữ lập trình định nghĩa khái niệm monitor, và các ngôn ngữ như thế chưa có nhiều.
Trao đổi thông điệp
Tiếp cận: giải pháp này dựa trên cơ sở trao đổi thông điệp với hai primitive Send và Receive để thực hiện sự đồng bộ hóa:
Send(destination, message): gởi một thông điệp đến một tiến trình hay gởi vào hộp thư.
Receive(source,message): nhận một thông điệp thừ một tiến trình hay từ bất kỳ một tiến trình nào, tiến trình gọi sẽ chờ nếu không có thông điệp nào để nhận.
Sử dụng: Có nhiều cách thức để thực hiện việc truy xuất độc quyền bằng cơ chế trao đổi thông điệp. Đây là một mô hình đơn giản: một tiến trình kiểm soát việc sử dụng tài nguyên và nhiều tiến trình khác yêu cầu tài nguyên này. Tiến trình có yêu cầu tài nguyên sẽ gởi một thông điệp đến tiến trình kiểm soát và sau đó chuyển sang trạng thái blocked cho đến khi nhận được một thông điệp chấp nhận cho truy xuất từ tiến trình kiểm soát tài nguyên.Khi sử dụng xong tài nguyên , tiến trình gởi một thông điệp khác đến tiến trình kiểm soát để báo kết thúc truy xuất. Về phần tiến trình kiểm soát , khi nhận được thông điệp yêu cầu tài nguyên, nó sẽ chờ đến khi tài nguyên sẵn sàng để cấp phát thì gởi một thông điệp đến tiến trình đang bị khóa trên tài nguyên đó để đánh thức tiến trình này.
while (TRUE) {
Send(process controler, request message);Receive(process controler, accept message);critical-section ();Send(process controler, end message);Noncritical-section ();
}
Hình 3.16 Cấu trúc tiến trình yêu cầu tài nguyên trong giải pháp message
Thảo luận: Các primitive semaphore và monitor có thể giải quyết được vấn đề truy xuất độc quyền trên các máy tính có một hoặc nhiều bộ xử lý chia sẻ một vùng nhớ chung. Nhưng các primitive không hữu dụng trong các hệ thống phân tán, khi mà mỗi bộ xử lý sỡ hữu một bộ nhớ riêng biệt và liên lạc thông qua mạng. Trong những hệ thống phân tán như thế, cơ chế trao đổi thông điệp tỏ ra hữu hiệu và được dùng để giải quyết bài toán đồng bộ hóa.
Các vấn đề cổ điển của đồng bộ hoá
Vấn đề Người sản xuất – Người tiêu thụ (Producer-Consumer)
Vấn đề: hai tiến trình cùng chia sẻ một bộ đệm có kích thước giới hạn. Một trong hai tiến trình đóng vai trò người sản xuất – tạo ra dữ liệu và đặt dữ liệu vào bộ đệm- và tiến trình kia đóng vai trò người tiêu thụ – lấy dữ liệu từ bộ đệm ra để xử lý.
Hình 3.17 Producer và Consumer
Để đồng bộ hóa hoạt động của hai tiến trình sản xuất tiêu thụ cần tuân thủ các quy định sau :
Tiến trình sản xuất (producer) không được ghi dữ liệu vào bộ đệm đã đầy.(synchronisation)
Tiến trình tiêu thụ (consumer) không được đọc dữ liệu từ bộ đệm đang trống.(synchronisation)
Hai tiến trình sản xuất và tiêu thụ không được thao tác trên bộ đệm cùng lúc . (exclusion mutuelle)
Giải pháp:
Semaphore
Sử dụng ba semaphore : full, đếm số chỗ đã có dữ liệu trong bộ đệm; empty, đếm số chỗ còn trống trong bộ đệm; và mutex, kiểm tra việc Producer và Consumer không truy xuất đồng thời đến bộ đệm.
BufferSize = 3; // số chỗ trong bộ đệm
semaphore mutex = 1; // kiểm soát truy xuất độc quyền semaphore empty = BufferSize; // số chỗ trống semaphore full = 0; // số chỗ đầy
Producer()
{
int item;
while (TRUE) {
produce_item(&item); // tạo dữ liệu mới down(&empty); // giảm số chỗ trống down(&mutex); // báo hiệu vào miền găng enter_item(item); // đặt dữ liệu vào bộ đệm up(&mutex); // ra khỏi miền găng up(&full); // tăng số chỗ đầy
}
}
Consumer()
{
int item;
while (TRUE) {
down(&full); // giảm số chỗ đầy down(&mutex); // báo hiệu vào miền găng
remove_item(&item); // lấy dữ liệu từ bộ đệm up(&mutex); // ra khỏi miền găng up(&empty); // tăng số chỗ trống consume_item(item); // xử lý dữ liệu
}
}
Monitor
Định nghĩa một monitor ProducerConsumer với hai thủ tục enter và remove thao tác trên bộ đệm. Xử lý của các thủ tục này phụ thuộc vào các biến điều kiện full và empty.
monitor ProducerConsumer
condition full, empty;
int count;
procedure enter();
{
if (count == N)
wait(full); // nếu bộ đệm đầy, phải chờ enter_item(item); // đặt dữ liệu vào bộ đệm count ++; // tăng số chỗ đầy
if (count == 1) // nếu bộ đệm không trống signal(empty); // thì kích hoạt Consumer
}
procedure remove();
{
if (count == 0)
wait(empty) // nếu bộ đệm trống, chờ remove_item(&item); // lấy dữ liệu từ bộ đệm count --; // giảm số chỗ đầy
if (count == N-1) // nếu bộ đệm không đầy signal(full); // thì kích hoạt Producer
}
count = 0; end monitor; Producer();
{
while (TRUE)
{
produce_item(&item); ProducerConsumer.enter;
}
}
Consumer();
{
while (TRUE)
{
ProducerConsumer.remove;
consume_item(item);
}
}
Trao đổi thông điệp
Thông điệp empty hàm ý có một chỗ trống trong bộ đệm. Tiến trình Consumer bắt đầu công việc bằng cách gởi 4 thông điệp empty đấng Producer. Tiến trình Producer tạo ra một dữ liệu mới và chờ đến khi nhận được một thông điệp empty thì gởi ngược lại cho Consumer một thông điệp chứa dữ liệu . Tiến trình Consumer chờ nhận thông điệp chứa dữ liệu, và sau khi xử lý xong dữ liệu này, Consumer sẽ lại gởi một thông điệp empty đến Producer, ...
BufferSize = 4; Producteur()
{
int item;
message m; // thông điệp while (TRUE) { produce_item(&item);
receive(consumer,&m); // chờ thông điệp empty create_message(&m, item); // tạo thông điệp dữ liệu send(consumer,&m); // gởi dữ liệu đến Consumer
}
}
Consumer()
{
int item;