Bài toán Hiền triết cùng ăn.

Bài này tuy thầy nói là không ra thi, nhưng mình thấy khá hay. Post lên cho mọi người cùng tham khảo.

bài toán hiền triết cùng ăn

- Năm nhà hiền triết ngồi quanh một chiếc bàn tròn
- Trên bàn, giữa họ là những chiếc đũa.
- Các nhà hiền triết độc lập với nhau và trầm tư suy nghĩ.
- Khi đói, mỗi người nhấc đũa 2 bên và nếu được cả đôi thì bắt đầu ăn, sau đó đặt từng chiếc đũa về vị trí cũ.
- Cần lập trình hành vi của mỗi hiền triết để không xảy ra Deadlock.
- Deadlock xảy ra khi: Các hiền triết cùng một lúc nhấc đũa bên trái hoặc đũa bên phải. Cứ thế chờ nhau mà không ai được ăn cả. Đó là hiện tượng Chờ xoay vòng (Circular Waiting).
- Thuật giải chính: Mỗi hiền triết tìm cách lấy đủ 2 đũa hai bên. Không đủ 2 đũa, không lấy.

Các ký hiệu:
‘d’ : đói.
‘a’ : đang ăn
‘-‘ : đang suy nghĩ.

Chopsticks[]: mảng đèn hiệu các cây đũa, chopstick[i]=TRUE, đũa rảnh có thể lấy.

Mảng cs[2]: trạng thái cây đũa bên trái và bên phải

WaitForMultipleObjects(2, cs, TRUE, INFINITE); chờ cho tới khi cs[0],cs[1] đều có giá trị là TRUE.

ReleaseMutex(chopsticks[LEFT]): nhả đèn hiệu của 1 cây đũa.

#define numPhilosophers 5

#define LEFT id
#define RIGHT (id+1)%numPhilosophers

HANDLE chopsticks[numPhilosophers]; // mang(den hieu)
char chState[numPhilosophers+1]; // mang trang thai cac cay dua
char phState[numPhilosophers+1]; // mang trang thai cac nha hien triet

void PhilosopherThread(int id){
HANDLE cs[2];
while (1) {
// Suy nghi ...
Sleep(GetTickCount()%1000);
// Doi, do vay tim cach lay du 2 dua Trai-Phai
phState[id]='d';
cs[0]=chopsticks[LEFT];
cs[1]=chopsticks[RIGHT];
// Cho den khi co du 2 dua Trai-Phai
WaitForMultipleObjects(2, cs, TRUE, INFINITE); // chờ cho toi khi cs[0],cs[1] cung co gia tri la TRUE.
chState[LEFT]='0'; // Khi cho xong xét trang thái dua bận
chState[RIGHT]='0';
// Bat dau an ...
phState[id]='a';
printf("- Chopsticks:\\t%s\\n Philosophers:\\t%s\\n\\n", chState, phState);
Sleep(GetTickCount()%1000);

// An xong trở lại trạng thái suy nghĩ

phState[id]='-';
chState[LEFT]='1'; ReleaseMutex(chopsticks[LEFT]); // Dat dua Trai xuong
chState[RIGHT]='1'; ReleaseMutex(chopsticks[RIGHT]);// Dat dua Phai xuong
}
}

void main(){
HANDLE handles[numPhilosophers];
DWORD threadID; int i;

// khởi tạo trạng thái ban đầu, tất cả hền triết đều đang suy nghĩ.

chState[numPhilosophers]='\\0'; phState[numPhilosophers]='\\0';

for (i=0; i<numPhilosophers; i++){
chState[i]='1'; phState[i]='-';
}
for (i=0; i<numPhilosophers; i++) // trạng thái đèn hiệu
chopsticks[i]=CreateMutex(0, FALSE, 0);

printf("- Chopsticks:\\t%s\\n Philosophers:\\t%s\\n\\n", chState, phState);

for (i=0; i<numPhilosophers; i++)
// tạo tiến trình các nhà hiền triết. chạy hàm PhilosopherThread.
handles[i]=CreateThread(0,0,(LPTHREAD_START_ROUTINE)PhilosopherThread,(void *)i,0,&threadID);
WaitForMultipleObjects(numPhilosophers, handles, TRUE, INFINITE);
for (i=0; i<numPhilosophers; i++) CloseHandle(chopsticks[i]);
}

Bạn có biết bài này do ai nghĩ ra ko? Thầy có nói nhưng mình quên mất tên rồi!

thanhvu(I92C) đã viết:Bạn có biết bài này do ai nghĩ ra ko? Thầy có nói nhưng mình quên mất tên rồi!

Hj. Mình cũng không nhớ nữa. bạn hỏi lại thầy nha,

Edsger Dijkstra năm 1965 đó bạn

Admin
Sao bạn này có trí nhớ tốt đến thế nhỉ ?

ngocdangI83C đã viết:Edsger Dijkstra năm 1965 đó bạn

Admin
Sao bạn này có trí nhớ tốt đến thế nhỉ ?

Edsger Wybe Dijkstra
-Sinh 11 tháng 5, 1930(1930-05-11)
Rotterdam, Hà Lan
-Mất 6 tháng 8, 2002 (72 tuổi)
Nuenen, Hà Lan
-Ngành: Khoa học máy tính
: Nổi tiếng vì +Giải thuật Dijkstra
+Goto là rất nguy hiểm[1]
+Hệ đa lập trình THE
+Semaphore
-Giải thưởng: +Giải Turing
+Hiệp hội máy tính toán
các bạn xem them tại :http://vi.wikipedia.org/wiki/Edsger_Dijkstra

ngocdangI83C đã viết:Edsger Dijkstra năm 1965 đó bạn

Admin
Sao bạn này có trí nhớ tốt đến thế nhỉ ?

Ủa? Vậy cho mình hỏi. 1965 là năm ông Dijkstra ra bài toán này à?

ngocdangI83C đã viết:Edsger Dijkstra năm 1965 đó bạn

Admin
Sao bạn này có trí nhớ tốt đến thế nhỉ ?

Thầy ơi, em tìm trên "Google". Tiện đây thầy cho em hỏi làm sao biết được thầy đã "Quote" bài của em để em kịp xem và hồi đáp.

Admin
Chỉ có cách... thường xuyên xem lại những gì đã đưa lên !

thanhvu(I92C) đã viết:

ngocdangI83C đã viết:Edsger Dijkstra năm 1965 đó bạn

Admin
Sao bạn này có trí nhớ tốt đến thế nhỉ ?

Ủa? Vậy cho mình hỏi. 1965 là năm ông Dijkstra ra bài toán này à?

Đúng rồi bạn, nhưng nếu mình nhớ không lầm thì vấn đề gốc không phải xuất phát từ 5 nhà hiền triết mà từ 5 cái PC nối mạng vòng tròn và cùng chia sẻ tài nguyên hạn chế, giống với 5 ông hiền triết ngồi cùng bàn ăn, nhưng đũa thì không đủ 5 đôi. Bạn có thể tìm thêm trên Google hay Wiki, mình cũng xem trên đấy

Hồi còn đi học Cao Đẳng, mình có gặp cái kiểu 5 ông hiền triết cùng ăn. Nhưng do ko học nhiều nên chẳng nhớ. Giờ đưa lên diễn đàn bàn luận làm mình nhớ nhiều hơn..do có sự hỗ trợ của thầy và các bạn.

Bài toán này thất bổ ích quá,lại rất hay nữa,học hệ diều hành thật là thú vị