Bài toán năm triết gia ăn tối
- Bài toán được đưa ra bởi nhà toán học E. W. Dijkstra vào năm 1965. Bài toán được phát biểu như sau: “Có năm nhà triết gia, vừa suy nghĩ vừa ăn tối cùng với nhau trên một chiếc bàn tròn. Trước mặt các triết gia là các đĩa thức ăn, mỗi người một đĩa và có 5 chiếc đũa được đặt xen kẽ giữa các triết gia. Mỗi triết gia dành toàn bộ thời gian để suy nghĩ hoặc ăn khi đói. Mỗi triết gia chỉ có thể ăn khi có được 2 chiếc đũa bên cạnh mình. Khi triết gia ăn xong, ông ta đặt đũa xuống và bắt đầu suy nghĩ tiếp”.
- Chú ý, triết gia không thể lấy chiếc đũa mà nó đang được dùng bởi người láng giềng. Khi một triết gia đói và có hai chiếc đũa cùng một lúc, ông ta ăn mà không đặt đũa xuống.
- Yêu cầu của bài toán đó là tìm ra thuật toán sao cho khi một triết gia bị đói thì ông ta sẽ được ăn và đảm bảo không có triết gia nào bị chết đói. Giải pháp được đưa ra để giải quyết vấn đề này là giải pháp Semaphore.