Bài toán Sản xuật tiêu thụ (các ban tham khảo cho ý kiến nha)

Vấn đề Sản xuất–Tiêu thụ (Producer-Consumer Problem)

Tiến trình Sản xuất tạo ra dòng thông tin để Tiến trình Tiêu thụ sử dụng. Ví dụ: Trình Compiler tạo ra các lệnh của ngôn ngữ Assembler, Trình Assembler nhận để tạo mã đích (Object Code), Mã này được Loader hoặc Linkage Editor tiêu thụ.

Phát biểu bài toán:
– Giả sử có Bộ nhớ đệm (Buffer) bao gồm nhiều khoang (Items) được tiến trình Producer lần lượt đưa các sản phẩm S1, S2,... vào.
– Tiến trình Consumer lần lượt lấy sản phẩm ra theo đúng thứ tự.
– Công việc của Producer phải đồng bộ với Consumer: Không được đưa sản phẩm vào khi Buffer đầy, Không được lấy ra khi chưa có.


- Giả sử chỉ có 1 Producer và 1 Consumer
o Vấn đề chỉ đơn giản là kiểm tra hàng đợi nếu đầy thì ngưng sản xuất.
o Ngược lại nếu hàng đợi hết thì ngừng tiêu thụ.

Khi đó bài toán được phát biểu theo kỹ thuật busy – waiting.

Sản xuất.

item nextProduced;

while (1) { //lặp vô hạn
/* tạo 1 sản phẩm và đưa vào nextProduced */
while (((in + 1) % BUFFER_SIZE) == out)
; // Quẩn tại đây khi buffer đầy
buffer[in] = nextProduced;
in = (in + 1) % BUFFER_SIZE; // chia lấy phần dư của số nguyên

}

Tiêu thụ

item nextConsumed;
while (1) {
while (in == out); // Quẩn tại đây khi buffer rỗng
nextConsumed = buffer[out];
out = (out + 1) % BUFFER_SIZE;
// Tiêu thụ sản phảm trong nextConsumed
}

- Trường hợp có trên 2 Producer, 2 Consumer.khi đó
o Ngoài việc kiểm tra hàng đợi, ta còn phải kiểm tra vị trí tiếp theo trong hàng đợi có bị Producer khác có sử dụng hay không.
o Ngược lại nhà tiêu thụ cũng phải kiểm tra hàng đợi tiếp theo có bị Consumer khác lấy rồi hay không.
o Và cùng lúc lấy ra và đưa vào sản phảm nhưng thời gian thực thi đồng thời.


o Như vậy với hơn 2 tiến trình cùng làm 1 việc hoặc Producer hoặc Consumer thì sẽ xảy ra tình trang tranh chấp nếu 2 tiến trình đồng thời cùng hoạt động (thuật ngữ gọi là vùng tương tranh). Để giải quyết vấn đề này ta phải quản lý buffer dùng chung bằng cách tạo ra 2 vùng là vùng đăng nhập(entry section) và vùng đăng xuất(exit section) – Chương 7.

Dưới đây là cấu trúc của phần quản lý buffer

while (1) {
remainder section
entry section // Vùng đăng nhập
critical section //vùng tranh chấp
exit section // Vùng đăng xuất
remainder section
}


Cuối cùng bài toán hoàn chỉnh được giải quyết như sau:
Sản xuất.

item nextProduced;

while (1) { //lặp vô hạn
/* tạo 1 sản phẩm và đưa vào nextProduced */
entry section
while (((in + 1) % BUFFER_SIZE) == out)
; // Quẩn tại đây khi buffer đầy
buffer[in] = nextProduced;
in = (in + 1) % BUFFER_SIZE; // chia lấy phần dư của số nguyên
exit section
}

Tiêu thụ

item nextConsumed;
while (1) {


while (in == out); // Quẩn tại đây khi buffer rỗng

entry section

nextConsumed = buffer[out];
out = (out + 1) % BUFFER_SIZE;
// Tiêu thụ sản phảm trong nextConsumed
exit section
}