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