Các vấn đề cổ điển của đồng bộ hoá

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;

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

}

}

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); }

}