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

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

חישוב מבוזר הוא כלי חזק וחשוב, אבל הוא מציב גם בעיות שצריך להתמודד איתן. טוני הור [2] ניסח דוגמה שממחישה את הבעיות בצורה ברורה ונגישה:

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

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

השאלה היא: איך אפשר לדאוג לכך שכל פילוסוף יקבל הזדמנויות לאכול?

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

הנה כמה פתרונות אפשריים:

•  הוספת מלצר: במקום שהפילוסופים יחליטו מתי להרים את המקלות, ימונה מלצר שיגדיר מי אוכל בכל רגע נתון. כך המלצר יוכל לפקח על מקלות האכילה ולוודא שאף אחד לא נשאר רעב. הפתרון הזה נפוץ מאוד במחשבים, שם המלצר נקרא arbiter, והוא אחראי לחלוקה הוגנת של המשאבים. החיסרון הברור בפתרון הזה הוא שהמלצר מלאכותי: צריך להוסיף אותו ולהגדיר לו איך לעבוד בצורה נכונה והוגנת. זה לא תמיד פשוט.
•  פתרון נוסף מתבסס על מספור מקלות האכילה מ-1 עד 5, ומגדיר שכל פילוסוף ירים את המקל בעל המספר הנמוך יותר משני המקלות שלידו, ואם המקל השני יישאר פנוי הוא ירים גם אותו ויאכל. במקרה זה אחד הפילוסופים לא ירים אף מקל. למשל, אם הפילוסוף שיושב בין מקל 1 ל-2 ירים את 1, והפילוסוף בין מקל 2 ל-3 ירים את 2 וכן הלאה, אז הפילוסוף בין מקלות 5 ל-1 לא יוכל להרים אף מקל, ולכן הפילוסוף בין 4 ל-5 יקבל שני מקלות ויוכל לאכול. הפתרון הזה שובר את הסימטריה. החיסרון הוא שדרוש למספר את המקלות, אבל זה חיסרון קטן יחסית, כי בדרך-כלל אפשר לקבל את המספור הזה באופן טבעי, למשל באמצעות המספר הסידורי של הרכיבים, או כתובות בזיכרון.
•  פתרון שלישי [3] הוא לאפשר לכל היותר ל-4 פילוסופים לשבת בשולחן בכל רגע נתון, ואז לאחד מהם תמיד יהיו שני מקלות. זה דומה קצת לפתרון המלצר, אבל משאיר חופש פעולה גדול יותר לפילוסופים שבשולחן.
•  קיימים פתרונות נוספים [4], שמאפשרים לפילוסופים לדבר זה עם זה. הפתרונות האלו מעט יותר מסובכים, כי צריך להגדיר במדויק מה מותר לפילוסופים להגיד, ומה החוקים שלפיהם הם מעבירים זה לזה הודעות או מקלות אכילה. עם זאת, פתרונות כאלו חשובים מאוד, למשל ברשתות תקשורת, כי שם אי אפשר להוסיף מלצר מלאכותי, אבל הנתבים ברשת בהחלט מדברים זה עם זה. 
•  פתרון אחרון לשבירת הסימטריה משתמש בהסתברות: כל פילוסוף יחכה פרק זמן אקראי לפני שינסה להרים מקל אכילה. אפשר להראות שבפתרון הזה, בהסתברות גבוהה מאוד כל פילוסוף יאכל תוך זמן סביר (אבל זה לא מובטח).

בעיית הפילוסופים הסועדים ממחישה כמה בעיות בחישוב מבוזר ומציעה להן פתרונות. עם זאת, יש עוד בעיות רבות וסבוכות בתחום הזה, הן תיאורטיות והן פרקטיות, ולהן מגוון פתרונות מרתקים מבוססי לוגיקה, הסתברות, אלגברה ועוד מגוון כלים מתמטיים [1 ,5].

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

עריכה: שיר רוזנבלום-מן

למקורות ולקריאה נוספת:

[1] Raynal, Michel, Concurrent programming: algorithms, principles, and foundations, Springer Science & Business Media, 2012.

[2] Hoare, Charles Antony Richard, "Communicating sequential processes", Communications of the ACM 21.8 (1978): 666-677.

[3] Stallings, William, and Goutam Kumar Paul, Operating systems: Internals and Design Principles. Vol. 9. New York: Pearson, 2012.

[4] Chandy, K. Mani, and Jayadev Misra, "The drinking philosophers problem", ACM Transactions on Programming Languages and Systems (TOPLAS) 6.4 (1984): 632-646.

[5] Bowman, Howard, and Rodolfo Gomez, Concurrency theory: Calculi and Automata for Modelling Untimed and Timed Concurrent Systems, Springer Science & Business Media, 2006.