Bài toán triết gia ăn tối

Vấn đề triết gia ăn tối (tiếng Anh: Dining philosophers problem) là một bài toán kinh điển trong khoa học máy tính và hệ điều hành dùng để minh họa các vấn đề đồng bộ hóa, bế tắc, đói tài nguyên và thiết kế thuật toán phối hợp giữa tiến trình/luồng.
Bài toán gốc được Edsger W. Dijkstra nêu trong ghi chú Hierarchical ordering of sequential processes năm 1965 và sau đó được phổ biến rộng rãi dưới dạng hiện nay.
Các phương pháp giải tiêu biểu gồm: quy tắc thứ tự tài nguyên, semaphore kiểu "bồi bàn" (waiter), cơ chế monitor (Dijkstra) và giải pháp phân tán của Chandy–Misra.

Mô tả chính thức
Trong mô tả cổ điển:
Có N triết gia (thường N = 5) ngồi quanh một bàn tròn.
Giữa mỗi hai triết gia liền kề có một cái nĩa — tổng cộng N nĩa.
Mỗi triết gia luân phiên giữa hai trạng thái: suy nghĩ (thinking) và ăn (eating). Để ăn, triết gia cần đồng thời giữ cả hai nĩa bên trái và bên phải.
Mục tiêu: thiết kế cơ chế đồng bộ sao cho hệ không rơi vào deadlock và, nếu có thể, không gây starvation.

Mô hình toán học
Bài toán có thể tổng quát hóa bằng đồ thị G = (V, E):
Mỗi đỉnh v ∈ V tương ứng một triết gia.
Mỗi cạnh {u, v} ∈ E tương ứng một nĩa dùng chung.
Một triết gia có thể ăn khi và chỉ khi anh ta đang giữ tất cả các nĩa incident với đỉnh đó. Trong trường hợp bàn tròn cổ điển, G là một chu trình bậc đều 2.

Các vấn đề quan trọng
Deadlock (bế tắc): trạng thái không tiến trình nào có thể tiến hành vì tất cả đều chờ tài nguyên do tiến trình khác giữ.
Starvation (đói): một tiến trình có thể bị chờ vô hạn nếu không được cấp tài nguyên mặc dù hệ vẫn tiến triển.
Livelock: các tiến trình liên tục thay đổi trạng thái (nhặt/đặt nĩa) nhưng không tiến triển.
Coffman đã nêu bốn điều kiện cần để xảy ra deadlock: mutual exclusion, hold-and-wait, no preemption, circular wait.

Tính chất đồng thời tối đa
Trong chu trình N đỉnh, số triết gia tối đa có thể ăn cùng lúc bằng ⌊N/2⌋. (Mỗi triết gia ăn chiếm hai nĩa kề nhau, tức là tập triết gia đang ăn tạo thành một matching trên đồ thị; matching cực đại của chu trình có kích thước ⌊N/2⌋.)

Các phương pháp giải
; Giải pháp cơ bản (dễ deadlock)
Mỗi triết gia lấy nĩa bên trái trước rồi nĩa bên phải. Nếu tất cả cùng làm vậy → deadlock.

; Waiter / N−1 rule
Có một semaphore "bồi bàn" cho phép tối đa N−1 triết gia đồng thời xin ăn. Nếu ≤ N−1 triết gia được phép, luôn có ít nhất một người lấy được cả hai nĩa → tránh deadlock. Ưu: đơn giản; nhược: cần trung tâm.

; Resource ordering
Gán thứ tự toàn cục cho các nĩa. Mỗi triết gia luôn lấy nĩa nhỏ trước rồi lớn. Loại bỏ chu trình chờ → không deadlock.

; Quy tắc chẵn–lẻ
Triết gia chẵn lấy nĩa phải trước, triết gia lẻ lấy nĩa trái trước. Phá đối xứng, giảm nguy cơ deadlock.

; Monitor (Dijkstra)
Dùng monitor lưu trạng thái THINKING/HUNGRY/EATING của từng triết gia. Khi một triết gia muốn ăn, monitor chỉ cho phép nếu hai láng giềng không ăn, và sẽ đánh thức tiến trình chờ khi có thể. Giải pháp tránh deadlock và starvation nếu semaphore/condition công bằng.

; Chandy–Misra (phân tán)
Mỗi cạnh có một token (fork) với trạng thái dirty/clean. Triết gia cần token để ăn; sau khi ăn xong, token trở lại dirty và có thể chuyển cho láng giềng theo yêu cầu. Bit dirty/clean giúp ưu tiên những triết gia chưa ăn lâu, giảm starvation. Thuật toán này hoàn toàn phân tán và áp dụng cho đồ thị bất kỳ.

Ví dụ mã (Python)
Các đoạn mã sau chỉ minh họa ý tưởng.

Deadlock demo

import threading, time, random
N = 5
forks = [threading.Lock() for _ in range(N)]

def philosopher(i):
left, right = i, (i+1)%N
while True:
time.sleep(random.uniform(0.1,0.5))
forks[left].acquire()
forks[right].acquire()
time.sleep(random.uniform(0.1,0.3))
forks[right].release()
forks[left].release()

Waiter (N−1)

import threading, time, random
N = 5
forks = [threading.Lock() for _ in range(N)]
waiter = threading.Semaphore(N-1)

def philosopher(i):
left, right = i, (i+1)%N
while True:
time.sleep(random.uniform(0.1,0.5))
waiter.acquire()
forks[left].acquire()
forks[right].acquire()
time.sleep(random.uniform(0.1,0.3))
forks[right].release()
forks[left].release()
waiter.release()

Resource ordering

import threading, time, random
N = 5
forks = [threading.Lock() for _ in range(N)]

def philosopher(i):
a, b = i, (i+1)%N
first, second = (a,b) if a

Phân tích
Safety: không có hai triết gia kề nhau ăn cùng lúc.
Liveness: waiter, resource ordering, monitor, Chandy–Misra loại trừ deadlock.
Fairness: monitor (nếu semaphore công bằng) và Chandy–Misra hạn chế starvation.

Biến thể
N triết gia bất kỳ.
Đồ thị tài nguyên tổng quát.
Phiên bản phân tán.
Có ưu tiên hoặc nhiều loại tài nguyên.

Xem thêm
Deadlock (khoa học máy tính)
Thuật toán đồng bộ hóa
Drinking philosophers problem

Tham khảo

Liên kết ngoài
EWD310 của Dijkstra
Bài báo Chandy–Misra 1984 (PDF)