Hệ điều hành - Lê Khắc Nhiên Ân

message m;

for(0 to N)

send(producer, &m); // gởi N thông điệp empty

while (TRUE) {

receive(producer, &m); // chờ thông điệp dữ liệu remove_item(&m,&item);// lấy dữ liệu từ thông điệp send(producer, &m); // gởi thông điệp empty consumer_item(item); // xử lý dữ liệu

}

Có thể bạn quan tâm!

Xem toàn bộ 262 trang tài liệu này.

}

Mô hình Readers-Writers

Vấn đề : Nhiều tiến trình đồng thời sử dụng một cơ sở dữ liệu. Các tiến trình chỉ cần lấy nội dung của cơ sở dữ liệu được gọi là các tiến trình Reader, nhưng một số tiến trình khác lại có nhu cầu sửa đổi, cập nhật dữ liệu trong cơ sở dữ liệu chung này, chúng được gọi là các tiến trình Writer. Các quy định đồng bộ hóa việc truy xuất cơ sỡ dữ liệu cần tuân thủ là :

Không cho phép một tiến trình Writer cập nhật dữ liệu trong cơ sở dữ liệu khi các tiến trình Reader khác đang truy xuất nội dung cơ sở dữ liệu.. (synchronisation)

Tại một thời điểm , chỉ cho phép một tiến trình Writer được sửa đổi nội dung cơ sở dữ liệu. (mutuelle exclusion).

Giải pháp:

Semaphore

Sử dụng một biến chung rc để ghi nhớ số lượng các tiến trình Reader muốn truy xuất cơ sở dữ liệu. Hai semaphore cũng được sử dụng : mutex, kiểm soát sự truy cập đến rc;và db, kiểm tra sự truy xuất độc quyền đến cơ sở dữ liệu.

semaphore mutex = 1; // Kiểm tra truy xuất rc

semaphore db = 1; // Kiểm tra truy xuất cơ sở dữ liệu

int rc; // Số lượng tiến trình Reader Reader()

{

while (TRUE) {

down(&mutex); // giành quyền truy xuất rc rc = rc + 1; // thêm một tiến trình Reader

if (rc == 1) // nếu là Reader đầu tiên thì down(&db); // cấm Writer truy xuất dữ liệu up(&mutex); // chấm dứt truy xuất rc read_database(); // đọc dữ liệu down(&mutex); // giành quyền truy xuất rc rc = rc - 1; // bớt một tiến trình Reader

if (rc == 0) // nếu là Reader cuối cùng thì up(&db); // cho phép Writer truy xuất db up(&mutex); // chấm dứt truy xuất rc use_data_read();

}

Writer()

{

while (TRUE) {

create_data();

down(&db); // giành quyền truy xuất db write_database(); // cập nhật dữ liệu up(&db); // chấm dứt truy xuất db

}

Monitor

Sử dụng một biến chung rc để ghi nhớ số lượng các tiến trình Reader muốn truy xuất cơ sở dữ liệu. Một tiến trình Writer phải chuyển sang trạng thái chờ nếu rc > 0. KHi ra khỏi miền găng, tiến trình Reader cuối cùng sẽ đánh thức tiến trình Writer đang bị khóa.

monitor ReaderWriter condition OKWrite, OKRead; int rc = 0;

Boolean busy = false;

procedure BeginRead()

{

if (busy) // nếu db đang bận, chờ wait(OKRead);

rc++; // thêm một Reader signal(OKRead);

}

procedure FinishRead()

{

rc--; // bớt một Reader

if (rc == 0) // nếu là Reader cuối cùng signal(OKWrite); // thì cho phép Writer

// truy xuất db

}

procedure BeginWrite()

{

if (busy || rc != 0) // nếu db đang bận, hay một wait(OKWrite); // Reader đang đọc db,chờ busy = true;

}

procedure FinishWrite()

{

busy = false;

If (OKRead.Queue) signal(OKRead); else signal(OKWrite);

}

Reader()

{

while (TRUE)

{

ReaderWriter.BeginRead(); Read_database(); ReaderWriter.FinishRead();

}

Writer()

{

while (TRUE)

{

create_data(&info); ReaderWriter.BeginWrite(); Write_database(); ReaderWriter.FinishWrite();

}

Trao đổi thông điệp

Cần có một tiến trình server điều khiển việc truy xuất cơ sở dữ liệu.

Các tiến trình Writer và Reader gởi các thông điệp yêu cầu truy xuất đến server và nhận từ server các thông điệp hồi đáp tương ứng .

Reader()

{

while (TRUE) {

send (server, RequestRead); receive (server, value); print(value); }

}

Writer()

{

while (TRUE) { create_data(&value);

send (server, RequestWrite,value); receive (server,OKWrite); }

}

Tắc nghẽn (Deadlock)‌

Định nghĩa:

Một tập hợp các tiến trình được định nghĩa ở trong tình trạng tắc nghẽn khi mỗi tiến trình trong tập hợp đều chờ đợi một sự kiện mà chỉ có một tiến trình khác trong tập hợp mới có thể phát sinh được.

Nói cách khác, mỗi tiến trình trong tập hợp đều chờ được cấp phát một tài nguyên hiện đang bị một tiến trình khác cũng ở trạng thái blocked chiếm giữ. Như vậy không có tiến trình nào có thể tiếp tục xử lý , cũng như giải phóng tài nguyên cho tiến trình khác sử dụng, tất cả các tiến trình trong tập hợp đều bị khóa vĩnh viễn !

Vấn đề Bữa ăn tối của các triết gia : 5 nhà triết học cùng ngồi ăn tối với món spaghetti nổi tiếng. Mỗi nhà triết học cần dùng 2 cái nĩa để có thể ăn spaghetti . Nhưng trên bàn chỉ có tổng cộng 5 cái nĩa để xen kẽ với 5 cái đĩa. Mỗi nhà triết học sẽ suy ngẫm các triết lý của mình đến khi cảm thấy đói thì dự định lần lượt cầm 1 cái nĩa bên trái và 1 cái nĩa bên phải để ăn. Nếu cả 5 nhà triết học đều cầm cái nĩa bên trái cùng lúc, thì sẽ không có ai có được cái nĩa bên phải để có thể bắt đầu thưởng thức spaghetti . Đây chính là tình trạng tắc nghẽn.

Hình 3.18 Bữa ăn tối của các triết gia

Điều kiện xuất hiện tắc nghẽn

Coffman, Elphick và Shoshani đã đưa ra 4 điều kiện cần có thể làm xuất hiện tắc nghẽn:

Có sử dụng tài nguyên không thể chia sẻ (Mutual exclusion): Mỗi thời điểm, một tài nguyên không thể chia sẻ được hệ thống cấp phát chỉ cho một tiến trình , khi tiến trình sử dụng xong tài nguyên này, hệ thống mới thu hồi và cấp phát tài nguyên cho tiến trình khác.

Sự chiếm giữ và yêu cầu thêm tài nguyên (Wait for): Các tiến trình tiếp tục chiếm giữ các tài nguyên đã cấp phát cho nó trong khi chờ được cấp phát thêm một số tài nguyên mới.

Không thu hồi tài nguyên từ tiến trình đang giữ chúng (No preemption): Tài nguyên không thể được thu hồi từ tiến trình đang chiếm giữ chúng trước khi tiến trình này sủ dụng chúng xong.

Tồn tại một chu kỳ trong đồ thị cấp phát tài nguyên ( Circular wait): có ít nhất hai tiến trình chờ đợi lẫn nhau : tiến trình này chờ được cấp phát tài nguyên đang bị tiến trình kia chiếm giữ và ngược lại.

Khi có đủ 4 điều kiện này, thì tắc nghẽn xảy ra. Nếu thiếu một trong 4 điều kiện trên thì không có tắc nghẽn.

Đồ thị cấp phát tài nguyên

Có thể sử dụng một đồ thị để mô hình hóa việc cấp phát tài nguyên. Đồ thị này có 2 loại nút : các tiến trình được biễu diễn bằng hình tròn, và mỗi tài nguyên được hiển thị bằng hình vuông