בעיית הפילוסופים הסועדים
במדעי המחשב, בעיית הפילוסופים הסועדים היא המחשה לבעיות תזמון וסנכרוניזציות שמופיעות בהקשרים של עיבוד מקבילי - מספר תוכניות שרצות יחד וחולקות משאבים משותפים. בשל פשטותה היחסית, הבעיה מוצגת לעתים קרובות בקורסים בסיסיים העוסקים בנושאים הללו.
מקור הבעיה בשנת 1971, בשאלה שנוסחה בידי אדסחר דייקסטרה, ולאחר מכן תוארה באמצעות הסיפור הציורי של הפילוסופים.
תוכן עניינים |
[עריכה] תאור הבעיה
חמישה פילוסופים יושבים סביב שולחן עגול ומבלים את זמנם בחשיבה ובאכילה. במרכז השולחן ישנה קערת ספגטי גדולה, ולכל אחד מהפילוסופים יש צלחת. בנוסף, בין כל שתי צלחות נמצא מזלג, כך שישנם בסך הכול חמישה מזלגות.
על מנת לאכול את הספגטי, כל פילוסוף זקוק לשני מזלגות (בניסוחים אחרים של הבעיה המזלגות מוחלפים במקלות אכילה). כל פילוסוף יכול להרים רק את שני המזלגות הקרובים אליו (אלו שמימין ומשמאל לצלחת שלו) והוא אינו יכול להרים את שניהם בו זמנית - כלומר, עליו להרים אחד מהם ורק לאחר מכן את השני.
פתרון לבעיה הוא דרך פעולה שבה על הפילוסופים לנהוג (אלגוריתם) כדי למנוע בעיות. מכיוון שהפילוסופים לא מדברים זה עם זה, על דרך הפעולה הזו לעבוד מבלי שתתבסס על תקשורת בין הפילוסופים.
שתי הבעיות הבסיסיות שעלולות להתהוות הן קיפאון והרעבה. מצב של קיפאון מתרחש כאשר כל הפילוסופים נתקעים במצב כלשהו ממנו אינם יכולים לצאת. למשל, אם הכלל שעל פיו הפילוסופים פועלים אומר כי כאשר הם רוצים לאכול עליהם להרים את המזלג שמימינם ולחכות עד שהמזלג משמאלם יתפנה, עלול להיווצר קיפאון אם כל הפילוסופים ירצו לאכול בו זמנית - כולם ירימו את המזלג שמימינם ולאחר מכן יחכו לנצח למזלג שמצד שמאל (שכן מזלג זה מוחזק בידי פילוסוף אחר, שגם הוא מחכה שיתפנה המזלג משמאלו, וכן הלאה בצורה מעגלית).
מצב של הרעבה מתרחש כאשר אחד או יותר מהפילוסופים אף פעם אינו מצליח לאכול. למשל, אם דרך הפעולה של הפילוסופים היא להרים את המזלג שמצד ימין, לחכות חמש דקות למזלג שמצד שמאל, ואם הוא טרם התפנה - להניח את המזלג שבצד ימין ולחכות עוד חמש דקות לפני הנסיון הבא, המצב שמתקבל אינו קיפאון (שכן הפילוסופים כל הזמן מורידים ומרימים את המזלגות, ולא נתקעים במצב בודד) אך הוא בבירור הרעבה כי אף פילוסוף אינו מצליח לאכול.
הפילוסופים שבסיפור הם אנלוגיה לתהליכים ולתהליכונים שרצים במקביל - ייתכן שעל מעבדים שונים, וייתכן שעל אותו המעבד. המזלגות שבבעיה הם אנלוגיה למשאבים משותפים - זיכרון מחשב, קבצים וכדומה.
[עריכה] פתרון הבעיה
[עריכה] פתרון ראשון
כל פילוסוף ירים את המזלג הימני ורק אז את המזלג השמאלי. הפתרון לא נכון, כיוון שיווצר קיפאון.
[עריכה] פתרון textbook
נאפשר לפילוסוף להרים את המזלג שלו באופן אוטומטי. נשים צלחת מרכזית על השולחן, כל פילוסוף שירצה להרים את המזלג שלו קודם יצטרך לתפוס את הצלחת המרכזית המשותפת לכל הפילוסופים . הבעיה בפתרון זה שהריצה יכולה לקחת הרבה זמן אם כולם נהפכים להיות רעבים בו זמנית. חסרונות נוספים: לא יעיל כי הוא מוריד את רמת ה mutual exclusion ואין מספיק מקביליות. בנוסף יכולה להיות הרעבה.
[עריכה] פתרון דומה בעזרת מנעולים
לפילוסוף 3 מצבים : hungry ,thinking-המהווה מצב ביניים בין חשיבה לאכילה ו eating. מנעול – עליו ה"פילוסופים" ישנים אם לא הצליחו לתפוס את "הצלחת המרכזית". [S[i הינו סמאפור עליו פילוסוף i ישן אם אחד ממזלגותיו תפוס. מובטח כי לא יהיה קיפאון מאחר שאין hold & wait וגם כי ישנה תמיד התקדמות מאחר שפילוסופים חדשים כל הזמן מתחילים לאכול. אבל יש כאן הרעבה. ניתן כמובן למנוע הרעבה על ידי שינויים קטנים באלגוריתם, כמו למשל: שמירת מידע של מי אכל אחרון ומתי.
[עריכה] פתרון AN
הרעיון: יצירת הכרעה על כל מזלג (=משאב) בין פילוסופים (=תהליכים). כל מזלג יהיה או בחירה ראשונה של שני הפילוסופים (תהליכים) שחולקים אותו או הבחירה השנייה עבור שניהם. יהיו לנו 2 תתי קבוצות: תת-קבוצה א' – תנסה תמיד להרים את המזלג השמאלי ורק אחר כך את הימני. תת-קבוצה ב' – תנסה תמיד לעשות ההפך, קודם הימני ואז השמאלי. הקבוצות יהיו משולבות זו בזו בסדר ישיבתן כלומר שכניו של פילוסוף מקבוצה א' תמיד יהיו שני פילוסופים מקבוצה ב' וכן ההפך. כך תמיד נוכל להיות בטוחים שתמיד מישהו יצליח לאכול ולא יווצר קיפאון.
היתרון בשיטה זו שבניגוד לקודמת אין לנו צוואר בקבוק. במידה ומזלג הוא פייר, כלומר אם תהליך א' ביקש לפני תהליך ב' את המזלג הוא גם יקבלו לפניו, אז לא תהיה הרעבה, מאחר שכל מזלג נלקח לפי מספורו בסדר עולה זה מבטל את דרישת ה – circular wait (סוג של מספור משאבים) ולכן לא יהיה קיפאון.
[עריכה] מספר התהליכים המקסימלי
מהו המספר המקסימלי של תהליכים שיכולים לאכול יחדיו, עבור כל פתרון, כאשר מדובר במקרה הגרוע ביותר? בפתרון הראשון 0 תהליכים יכולים לאכול בו זמנית במקרה הגרוע ביותר. מאחר שכולם מרימים את המזלג הימני ואף אחד לא יכול להרים את מזלגו השמאלי (קיפאון).
בפתרון השני (Textbook) במקרה הכי גורע חוסם כל תהליך את שני שכניו ולכן N/3 הוא מספר התהליכים שיכולים לאכול במקרה הגרוע ביותר (לעומת N/2 במקרה הטוב ביותר).
בפתרון השלישי (AN) במקרה הגרוע ביותר תהליך חוסם 4 תהליכים אחרים, 2 שכניו ואחד מהשכנים שלהם, ולכן יכולים לאכול בו זמנית N/4 תהליכים. הניתוח נובע מכך שהמזלגות מורמים באופן שאיננו אוטומטי.
