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

מתוך ויקיפדיה, האנציקלופדיה החופשית

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

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

[עריכה] תאור הבעיה

איור- המחשה של בעיית הפילוסופים הסועדים
הגדל
איור- המחשה של בעיית הפילוסופים הסועדים

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

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

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

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

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

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