Tổng hợp (các khóa trước)

Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down

Tổng hợp (các khóa trước)

Bài gửi  HuynhPhuong (I11C) on 18/11/2011, 21:13

1. Phát biểu bài toán Sản xuất-Tiêu thụ với thuật giải đồng bộ hoá bằng 3 đèn hiệu semFull, semEmpty và Mutex.
Trả lời:
- Tiến trình sản xuất (Producer) tạo ra dòng thông tin để tiến trình tiêu thụ (Consumer) sử dụng.
- Ví dụ: Compiler và Assembler vừa là nhà sản xuất vừa là nhà tiêu thụ. Compiler tạo ra mã dùng cho Assembler, tiếp theo Assembler sản sinh mã máy làm đầu vào cho Loader hoặc Linkage Editor.
- Phát biểu bài toán: Bộ nhớ đệm Buffer bao gồm một số hữu hạn các khoang chứa (Items). Producer lần lượt đưa các sản phẩm S1, S2,…vào các khoang của Buffer. Consumer lấy sản phẩm ra theo đúng thứ tự. Công việc của các tiến trình phải đồng bộ với nhau: không đưa ra sản phẩm khi hết chỗ trống, không lấy được sản phẩm khi chưa có.
- Thuật giải đồng bộ hoá bằng 3 đèn hiệu: semFull (quản lý số sản phẩm có trong bộ đệm, giá trị ban đầu bằng 0), semEmpty (quản lý số khoang còn trống, giá trị ban đầu bằng số khoang của bộ đệm) và Mutex (đảm bảo tính loại trừ tương hỗ, nghĩa là mỗi thời điểm chỉ có 1 tiến trình sản xuất hay tiêu thụ được truy cập/cập nhật tài nguyên dùng chung, giá trị ban đầu bằng 1).
* Thuật giải cho Producer:
wait(semEmpty);
wait(Mutex);
// Đưa sản phẩm vào Buffer
..........................
signal(semFull);
signal(Mutex);
*Thuật giải cho Consumer:
wait(semFull);
wait(Mutex);
// Lấy sản phẩm từ Buffer
..........................
signal(semEmpty);
signal(Mutex);
avatar
HuynhPhuong (I11C)

Tổng số bài gửi : 39
Join date : 26/08/2011
Age : 26
Đến từ : Hóc Môn, Tp HCM

Xem lý lịch thành viên

Về Đầu Trang Go down

Re: Tổng hợp (các khóa trước)

Bài gửi  HuynhPhuong (I11C) on 18/11/2011, 21:15

2. Phát biểu bài toán Sản xuất-Tiêu thụ với thuật giải dùng kỹ thuật Busy-Waiting.
Trả lời:
- Tiến trình sản xuất (Producer) tạo ra dòng thông tin để tiến trình tiêu thụ (Consumer) sử dụng.
- Ví dụ: Compiler và Assembler vừa là nhà sản xuất vừa là nhà tiêu thụ. Compiler tạo ra mã dùng cho Assembler, tiếp theo Assembler sản sinh mã máy làm đầu vào cho Loader hoặc Linkage Editor.
- Phát biểu bài toán: Bộ nhớ đệm Buffer bao gồm một số hữu hạn các khoang chứa (Items). Producer lần lượt đưa các sản phẩm S1, S2,…vào các khoang của Buffer. Consumer lấy sản phẩm ra theo đúng thứ tự. Công việc của các tiến trình phải đồng bộ với nhau: không đưa ra sản phẩm khi hết chỗ trống, không lấy được sản phẩm khi chưa có.
- Thuật giải dùng kỹ thuật Busy-Waiting (chờ bận) với biến đếm count (chứa số sản phẩm trong Buffer):
+ Producer:
while(1){
while(count == BUFFER_SIZE); // Vòng lặp chờ bận
// Đưa sản phẩm vào Buffer
count++; // Tăng count lên 1
}
+ Consumer:
while(1){
while(count == 0); // Vòng lặp chờ bận
// Lấy sản phẩm từ Buffer
count--; // Giảm count đi 1
}
Ghi chú:
- Vòng lặp chờ bận phải liên tục kiểm tra giá trị biến đếm count, tốn thời gian CPU, dẫn đến giảm hiệu năng hệ thống.
- Có thể không dùng biến đếm count. Khi đó, vòng lặp chờ bận cho Producer được thực thi bằng:
Code:
while(((in+1)%BUFFER_SIZE)==out); // Vòng lặp chờ bận
Còn đối với Consumer thì dùng:
Code:
while(in==out); // Vòng lặp chờ bận
avatar
HuynhPhuong (I11C)

Tổng số bài gửi : 39
Join date : 26/08/2011
Age : 26
Đến từ : Hóc Môn, Tp HCM

Xem lý lịch thành viên

Về Đầu Trang Go down

Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang


 
Permissions in this forum:
Bạn không có quyền trả lời bài viết