בעיית הפילוסופים הסועדים

במדעי המחשב, בעיית הפילוסופים הסועדים היא הדגמה לבעיות תזמון ותיאום בעיבוד מקבילי, כלומר כאשר כמה תהליכים רצים במקביל וחולקים משאבים. הבעיה הוצגה על ידי אדסחר דייקסטרה ב-1971, והוצגה כסיפור של פילוסופים כדי להמחיש את הבעיה.


חמישה פילוסופים יושבים סביב שולחן עגול. במרכז יש קערת ספגטי, ולכל פילוסוף יש צלחת. בין כל שתי צלחות יש מזלג, וסך הכל חמישה מזלגות. כדי לאכול כל פילוסוף צריך שני מזלגות (בגרסאות אחרות משתמשים במקלות אכילה). כל פילוסוף יכול להרים רק את המזלג השכונתי מימין או משמאל, ולא יכול להרים את שניהם בו-זמנית. בנוסף, אין תקשורת בין הפילוסופים.

מתודולוגית מתעוררות שתי בעיות מרכזיות: קיפאון והרעבה. קיפאון (deadlock) הוא מצב שבו כל הפילוסופים תקועים ולא יכולים להמשיך. דוגמה נפוצה: אם כולם מנסים להרים קודם את המזלג מימין, הם ימתינו למזלג מצד שמאל שנמצא אצל שכן, וכך יווצר חסם מעגלי. רעבה (starvation) היא מצב שבו פילוסוף אחד או יותר לעולם לא מצליחים לאכול. למשל, אם הפילוסופים מרים מזלג מימין, מחכים, ומורידים אותו אם לא הצליחו, ייתכן שכל אחד מנסה שוב ושוב ולא מצליח לאכול. הוספת עדיפות עלולה גם היא לגרום לכך שהחלש או הצעיר לא יאכל לעולם.

הפילוסופים מסמלים תהליכים מקבילים, והמזלגות הם משאבים משותפים כמו זיכרון או קבצים.



פתרון פשוט הוא להוסיף "מלצר" בשולחן. כל פילוסוף חייב לבקש רשות מהמלצר לפני שהוא מרים מזלג. מאחר שהמלצר יודע מי מחזיק מה, הוא יכול למנוע קיפאון על ידי מתן רשות סלקטיבית. כלל נפוץ הוא להגביל מספר מזלגות שמותר להשתמש בהם בו-זמן, כך שלפני שיורשים את המזלג הימני צריך לוודא שהמלצר מאשר. רעיון זה מקביל לשימוש בסמפור (semaphore), מנגנון שנועד לשלוט בגישה למשאבים, שאותו הציג דייקסטרה כבר ב-1965.


פתרון אחר מאפשר לפילוסוף לקבל קודם שליטה על צלחת מרכזית (אסימון), ורק אז להרים מזלגות. בכך נמנעת אפשרות לקיפאון, אך רמת המקביליות פוחתת וההמתנה מתארכת. פתרון זה אינו מונע בתכלית הרעבה, כי ייתכנו תרחישים שבהם חלק מהפילוסופים לא יקבלו את האסימון מספיק לעתים.

בעיית הפילוסופים הסועדים מסבירה בעיה במחשבים כשכמה תוכניות רוצות את אותם חפצים.


חמישה פילוסופים יושבים סביב שולחן. יש חמש צלחות וחמישה מזלגות. כל פילוסוף צריך שני מזלגות כדי לאכול. כל מזלג נמצא בין שתי צלחות. כל פילוסוף יכול לקחת רק את המזלג שמימינו או שמאלו. הוא לוקח אחד ואז מנסה לקחת את השני. הפילוסופים לא מדברים זה עם זה.

שתי בעיות יכולות לקרות: קיפאון והרעבה. קיפאון (deadlock) הוא מצב שבו אף אחד לא יכול להמשיך. לדוגמה, אם כולם לוקחים קודם את המזלג מימין, אף אחד לא יכול להשיג את המזלג הנוסף. רעבה (starvation) היא מצב שבו מישהו אף פעם לא מצליח לאכול. למשל, אם כל פעם שמישהו לא מצליח הוא מהנה את המזלג ומנסה שוב, הוא אולי לא יצליח לאכול אף פעם.



אולי יהודי מלצר עוזר: כל פילוסוף מבקש רשות מהמלצר לפני שהוא לוקח מזלג. המלצר נותן רשות רק כאשר זה בטוח. כך לא יווצר קיפאון. הרעיון דומה לסמפור (סמפור = שיטה שמגבילה מי יכול לקחת משאבים).


רעיון אחר הוא לתת לכל מי שרוצה לאכול "אסימון" (אסימון = כלי מיוחד). מי שמחזיק את האסימון יכול לקחת מזלגות. זה מונע קיפאון, אך יכול לגרום לחכות ארוך. לפעמים עדיין ייתכן שמישהו יהיה רעב ולא יאכל.