Mình có Bài toán 5 SV ăn cơm rất hay các bạn tham khảo và cho ý kiến!!!

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

Mình có Bài toán 5 SV ăn cơm rất hay các bạn tham khảo và cho ý kiến!!!

Bài gửi  lekhanhhoa(I22B) on 6/4/2013, 08:40

Đề bài:
1. bàn ăn có 5 chén cơm dành cho 5 SV, đánh số thứ tự từ 0 - 4.
2. do thiếu đủa, chỉ có 5 chiếc được để xen kẻ giữa các chén cơm, đánh số thứ tự từ0 -4.
3. mỗi SV ăn cơm cần 1 đôi đủa. Vì lịch sự, mỗi SV chỉ được phép lấy 2 chiếc kề chén cơm của mình (chiếc bên trái và chiếc bên phải).
4. hãy tìm qui trình ăn cơm cho mỗi SV sao cho các điều kiện sau được thỏa :
- các SV ăn cơm được càng đồng thời càng tốt (hiệu quảnhất).
- các SV không được tranh chấp nhau trong việc lấy đôi đủa.
- các SV không bịdeadlock trong quá trình chờ lấy đủa
Phân tích hoạt động ăn cơm của SV :
- quá trình ăn cơm không đòi hỏi phải sởhữu liên tục đôi đủa.
- quá trình ăn cơm là hoạt động lặp, mỗi chu kỳgồm 3 công đoạn :
1. đang nhai cơm hay nói chuyện. (THINKING)
2. cốgắng chiếm hữu đôi đủa. (HUNGRY)
3. và cơm và gắp thức ăn rồi để đủa xuống bàn. (EATING)
- trong đó công đoạn 1 tốn nhiều thời gian nhất nhưng may mắn là trong công đoạn này, SV không cần đủa (tài nguyên). Còn bước 2 và 3 thì rất ngắn và cần loại trừ tương hỗ giữa các SV.
Lời giải:
Môn : Hệ điều hành
Phát họa qui trình ăn cơm cho mỗi SV :
#define N 5
void Sinhvien (int i) {
while (còn cơm) {
think(); //công đoạn 1
take_fork(i); //công đoạn 2, có thểbị kẹt 1 thời gian
take_fork((i+1)%N);
eat();
put_fork(i); //công đoạn 3 thường rất nhanh
put_fork((i+1)%N);
}
}
Qui trình ăn ởtrên dễbị deadlock, thí dụnhư 5 SV đều thực hiện lệnh take_fork(i); đồng thời và đều thành công. Bây giờ họthực hiện tiếp lệnh kế thì tất cả đều bị dừng chờ mãi mãi vì không còn đủa trên bàn.
//thuật giải cải tiến để tránh deadlock :
#define N 5
void Sinhvien (int i) {
while (còn cơm) {
think(); //công đoạn 1
L1: take_fork(i);
if (!asyn_take_fork((i+1)%5)) { //thất bại
put_fork(i); sleep(random()); goto L1; //công đoạn 2
}
eat(); //công đoạn 3
...
}
}
Qui trình ăn ởtrên tránh được deadlock, nhưng còn dựa vào yếu tố ngẫu nhiên nên chưa hiệu quả triệt để.
//thuật giải dùng semaphore để giải quyết tranh chấp và đồng bộ:
#define N 5
#define LEFT (i-1)%N
#define RIGHT (i+1)%N
#define THINKING 0
#define HUNGRY 1
#define EATING 2
typedef unsigned int semaphore;
int state[N];
semaphore mutex = 1;
semaphore s[N];
void Sinhvien (int i) {
while (còn cơm) {
think(); //công đoạn 1
take_forks(i); //công đoạn 2, có thể bị kẹt 1 thời gian
eat(); put_forks(i); //công đoạn 3
}
//thuật giải dùng semaphore để giải quyết tranh chấp và đồng bộ:
void take_forks(int i) {
down(&mutex); //đảm bảo 0 tranh chấp khi lấy đủa
state[i] = HUNGRY; //ghi nhận trạng thái đang cốgắng lấy đủa
test(i); //kiểm tra lấy được không ? nếu được s[i] →1
up(&mutex); //đánh thức các SV khác để họtruy xuất đủa
down(&s[i]); //cốgắng và cơm & gắp thức ăn, có thểbị kẹt
}
void test (int i) {
if (state[i] == HUNGRY //SV i muốn lấy đủa
&& state[LEFT] != EATING //SV bên trái chưa lấy
&& state[RIGHT] != EATING) { //SV bên phải chưa lấy
state[i] = EATING; //ghi nhận SV i đã lấy được đủa
up(&s[i]); //tăng s[i] →1
}
}
//thuật giải dùng semaphore để giải quyết tranh chấp và đồng bộ:
void put_forks (int i) {
down(&mutex); //đảm bảo 0 tranh chấp khi lấy đủa
state[i] = THINKING; //ghi nhận trạng thái không dùng đủa
test(LEFT); //kiểm tra lấy được không ? nếu được đánh thức
//SV LEFT dậy đểvà cơm và gắp thức ăn
test(RIGHT); //kiểm tra lấy được không ? nếu được đánh thức
//SV RIGHT dậy đểvà cơm và gắp thức ăn
up(&mutex); //đánh thức các SV khác đểhọtruy xuất đủa
}

lekhanhhoa(I22B)

Tổng số bài gửi : 31
Join date : 24/03/2013

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

- Similar topics

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