BÀI 4: CÁC BÀI TOÁN ĐỒNG BỘ CỔ ĐIỂN
1. Bài toán Người sản xuất – Người tiêu thụ (Producer-Consumer)
Hai tiến trình cùng chia sẻ một bộ đệm có kích thước giới hạn. Một tiến trình tạo
dữ liệu, đặt dữ liệu vào bộ đệm (người sản xuất) và một tiến trình lấy dữ liệu từ
bộ đệm để xử lý (người tiêu thụ).
Hình: Producer và Consumer
Hai tiến trình cần thoả các điều kiện sau :
- Tiến trình sản xuất không được ghi dữ liệu vào bộ đệm đã đầy.
- Tiến trình tiêu thụ không được đọc dữ liệu từ bộ đệm đang trống.
- Hai tiến trình không được truy xuất bộ đệm cùng lúc.
Cách 1: dùng 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.
- mutex: kiểm tra việc không truy xuất đồng thời.
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, day thi cho
down(&mutex); // độc quyền 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, danh thuc ntt
}

remove_item(&item); // lấy dữ liệu từ bộ đệm
count --; // giảm số chỗ đầy
if (count == N-1) signal(full); // nếu bộ đệm không đầy thì kích hoạt
}
}
Producer() //Tiến trình sản xuất
{
while (TRUE) {
produce_item(&item);
ProducerConsumer.enter();
}
}
Consumer() //tiến trình tiêu thụ
{
while (TRUE) {
ProducerConsumer.remove();
consume_item(item);
45
}
}
2. Bài toán Readers-Writers
Khi truy xuất cơ sỡ dữ liệu cần thoả các điều kiện sau :
- Khi các tiến trình Reader đang đọc thì các tiến trình Writer không được ghi và
ngược lại.
- Tại một thời điểm , chỉ có thể có một Writer, nhưng có thể có nhiều Reader.
Cách 1: dùng Semaphore
Sử dụng biến chung rc để ghi nhớ số tiến trình Reader và sử dụng hai
semaphore:
- mutex: kiểm soát sự truy xuất độc quyền rc
- db: kiểm tra sự truy xuất độc quyền đến cơ sở dữ liệu.

}
}
47
Cách 2: Monitor
Sử dụng biến chung rc để ghi nhớ số các tiến trình Reader. 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;
int busy = 0;
void BeginRead()
{
if (busy) wait(OKRead); // nếu db đang bận thì chờ trên OKRead
rc++; // thêm một Reader
signal(OKRead); //đánh thức một reader cho thực thi
}
void FinishRead()
{
rc--; // bớt một Reader
if (rc == 0) signal(OKWrite); // nếu là Reader cuối cùng thì cho Writer
truy xuất db
}
void BeginWrite()
{
if (busy || rc != 0) wait(OKWrite); // nếu db đang bận, hay có Reader
đang đọc db thì chờ
busy = 1; //khong cho cac reader va writer khac truy xuat db
}