בעיית הפילוסופים הסועדים
 |
ערך זה זקוק לעריכה: ייתכן שהערך סובל מפגמים טכניים כגון מיעוט קישורים פנימיים, סגנון טעון שיפור או צורך בהגהה, או שיש לעצב אותו. | ||
| אתם מוזמנים לסייע ולתקן את הבעיות, אך אנא אל תורידו את ההודעה כל עוד לא תוקן הדף. אם אתם סבורים כי אין בדף בעיה, ניתן לציין זאת בדף השיחה. | |||
במדעי המחשב, בעיית הפילוסופים הסועדים היא המחשה לבעיות תזמון ותיאום שמופיעות בהקשרים של עיבוד מקבילי - מספר תוכניות שרצות יחד וחולקות משאבים משותפים. בשל פשטותה היחסית, הבעיה מוצגת לעתים קרובות בקורסים בסיסיים העוסקים בנושאים הללו.
את הבעיה הציפה שאלה שנוסחה בשנת 1971 על ידי אדסחר דייקסטרה, ולאחר מכן הומחשה באמצעות הסיפור הציורי של הפילוסופים.
תוכן עניינים |
תיאור הבעיה [עריכה]
חמישה פילוסופים יושבים סביב שולחן עגול ומבלים את זמנם בחשיבה ובאכילה. במרכז השולחן ישנה קערת ספגטי גדולה, ולכל אחד מהפילוסופים יש צלחת. בין כל שתי צלחות נמצא מזלג, כך שישנם בסך הכול חמישה מזלגות.
על מנת לאכול את הספגטי, כל פילוסוף זקוק לשני מזלגות (בניסוחים אחרים של הבעיה המזלגות מוחלפים במקלות אכילה). כל פילוסוף יכול להרים רק את שני המזלגות הקרובים אליו (אלו שמימין ומשמאל לצלחת שלו) ואינו יכול להרים את שניהם בו-זמנית - כלומר, עליו להרים אחד מהם, ורק לאחר מכן את השני. תנאי נוסף הוא שלא מתקימת כל תקשורת בין הפילוסופים.
שתי הבעיות הבסיסיות שעלולות להתהוות הן קיפאון והרעבה. מצב של קיפאון מתרחש כאשר כל הפילוסופים נתקעים במצב כלשהו ממנו אינם יכולים לצאת. למשל, אם הכלל שעל פיו הפילוסופים פועלים אומר כי כאשר הם רוצים לאכול עליהם להרים את המזלג שמימינם ולחכות עד שהמזלג משמאלם יתפנה, עלול להיווצר קיפאון אם כל הפילוסופים ירצו לאכול בו זמנית - כולם ירימו את המזלג שמימינם ולאחר מכן יחכו לנצח למזלג שמצד שמאל (שכן מזלג זה מוחזק בידי פילוסוף אחר, שגם הוא מחכה שיתפנה המזלג משמאלו, וכן הלאה בצורה מעגלית).
מצב של הרעבה מתרחש כאשר אחד או יותר מהפילוסופים אף פעם אינו מצליח לאכול. למשל, אם דרך הפעולה של הפילוסופים היא להרים את המזלג שמצד ימין, לחכות חמש דקות למזלג שמצד שמאל, ואם הוא טרם התפנה - להניח את המזלג שבצד ימין ולחכות עוד חמש דקות לפני הנסיון הבא, המצב שמתקבל אינו קיפאון (שכן הפילוסופים כל הזמן מורידים ומרימים את המזלגות, ולא נתקעים במצב בודד) אך הוא בבירור הרעבה כי אף פילוסוף אינו מצליח לאכול. דוגמה נוספת להרעבה מתרחשת כאשר מוסיפים למערכת אלמנט של עדיפות. פתרון אפשרי, למשל, למצב הקיפאון שתואר לעיל תספק החלטה שפילוסוף האוחז מזלג ומחכה למזלג אחר, ישחרר את המזלג שבידו אם שכנו מבוגר ממנו וגם הוא מחזיק מזלג. זהו פתרון טוב למדי, אך הוא יכול להביא למצב שבו הפילוסוף הצעיר ביותר אינו מספיק אף פעם לאכול, בעוד הפילוסופים משני צדדיו אוכלים לסרוגין.
הפילוסופים מיצגים תהליכים ותהליכונים שרצים במקביל על מעבדים שונים או על מעבד יחיד. המזלגות מיצגים משאבים משותפים - זיכרון מחשב, קבצים וכדומה.
פתרון הבעיה [עריכה]
פתרון המלצר (פתרון המנצח) [עריכה]
פתרון פשוט יחסית מושג על ידי הפעלה של "מלצר" בשולחן. פילוסוף חייב לבקש רשות להרים מזלג. בגלל שהמלצר מודע למצב המזלגות, הוא מסוגל להכריע ולמנוע מצב של Deadlock. כאשר ארבעה מזלגות בשימוש, הפילוסוף הבא שמעוניין לבקש מזלג, צריך לחכות לרשות המלצר, שכמובן לא תינתן עד אשר המזלג יתפנה. הלוגיקה פשוטה על ידי הקביעה שפילוסופים קודם כל מרימים את המזלג השמאלי ואחר כך את הימני (או להיפך). המלצר מתנהג כסמפור, רעיון שהוצג על ידי דייקסטרה ב 1965.
כדי לדמות איך הדבר עובד, יש לדמיין שהפילוסופים מתוייגים על ידי האותיות A-E עם כיוון השעון. אם A ו-C אוכלים, משמעות הדבר שארבעה מזלגות בשימוש. B יושב בין C ל-A ולכן לא מחזיק באף מזלג, בעוד שבין D ו-E יש מזלג אשר אינו בשימוש אף פילוסוף. נניח ש-D רוצה לאכול. כאשר הוא רוצה להרים את המזלג החמישי, סביר להניח שיווצר מצב של Deadlock. אם במקום זה הוא מבקש את רשות המלצר והמלצר אומר לו לחכות, אפשר להיות בטוחים שכאשר ארבעת המזלגות יתפנו, יהיה לפחות פילוסוף אחד שיבקש את שני המזלגות שנמצאים בשני צדדיו ויקבלם בהצלחה.
פתרון ראשון [עריכה]
כל פילוסוף ירים את המזלג הימני ורק אז את המזלג השמאלי. הפתרון לא נכון, כיוון שיווצר קיפאון.
פתרון 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 תהליכים. הניתוח נובע מכך שהמזלגות מורמים באופן שאיננו אוטומטי.
