ברוכים הבאים ליחידה מרכזית וקריטית בקורס "מערכות הפעלה" – מבוי סתום (Deadlock). מצב של מבוי סתום הוא תרחיש לא רצוי שבו שתי תוכניות או יותר חוסמות זו את זו, וכל אחת ממתינה למשאב המוחזק על ידי אחרת, כך שאף אחת מהן אינה יכולה להתקדם. הבנה מעמיקה של הגורמים למבוי סתום ושל האסטרטגיות השונות לטיפול בו היא חיונית לתכנון ופיתוח מערכות הפעלה יציבות ויעילות. שיעור זה יסקור את ארבעת התנאים ההכרחיים לקיומו של מבוי סתום, ויציג את הגישות המרכזיות לטיפול בו: מניעה, הימנעות (עם דגש על אלגוריתם הבנקאי), זיהוי ושחזור. הידע שתצברו כאן יהיה קריטי להצלחתכם במבחן ובפיתוח מערכות אמיתיות.
מהו מבוי סתום (Deadlock)?
מבוי סתום הוא בעיה נפוצה במערכות מרובות משימות (multitasking systems) ובמערכות מבוזרות, והוא דורש טיפול מיוחד על מנת להבטיח את תקינות המערכת.
ארבעת התנאים ההכרחיים למבוי סתום
מבוי סתום יכול להתרחש רק אם מתקיימים בו זמנית ארבעה תנאים. אם אחד מהם אינו מתקיים, מבוי סתום אינו אפשרי.
הדדיות (Mutual Exclusion)
משאב יכול להיות מוחזק על ידי תהליך אחד בלבד בכל רגע נתון. אם תהליך אחר מבקש את המשאב, עליו להמתין עד שהמשאב ישוחרר. זהו תנאי בסיסי לכל משאב שאינו ניתן לשיתוף (non-sharable).
החזק והמתן (Hold and Wait)
תהליך מחזיק במשאב אחד לפחות ובמקביל ממתין למשאב נוסף המוחזק על ידי תהליך אחר.
אי-הפקעה (No Preemption)
משאבים אינם ניתנים להפקעה (לא ניתן לקחת אותם בכוח) מתהליך המחזיק בהם, אלא רק משוחררים מרצון על ידי התהליך לאחר שסיים את השימוש בהם.
המתנה מעגלית (Circular Wait)
קיימת שרשרת מעגלית של שני תהליכים או יותר, כאשר כל תהליך בשרשרת ממתין למשאב המוחזק על ידי התהליך הבא בשרשרת.
אסטרטגיות לטיפול במבוי סתום
קיימות ארבע גישות עיקריות לטיפול במבוי סתום:
1. מניעת מבוי סתום (Deadlock Prevention)
גישה זו מבטיחה שמבוי סתום לעולם לא יתרחש על ידי ביטול אחד או יותר מארבעת התנאים ההכרחיים. החיסרון הוא שהיא עלולה להוביל לניצול משאבים נמוך ולירידה בביצועים.
ביטול הדדיות
לא ניתן לבטל תנאי זה עבור משאבים שאינם ניתנים לשיתוף (כמו מדפסת). עבור משאבים ניתנים לשיתוף (כמו קובץ לקריאה בלבד), אין בעיית הדדיות.
ביטול החזק והמתן
אחת משתי שיטות: 1. תהליך חייב לבקש את כל המשאבים הדרושים לו בתחילת הדרך. 2. תהליך יכול לבקש משאבים רק כאשר הוא אינו מחזיק באף משאב אחר.
ביטול אי-הפקעה
אם תהליך שמחזיק במשאבים מבקש משאב נוסף ואינו יכול לקבלו, יש להפקיע ממנו את כל המשאבים שהוא מחזיק כרגע. הוא יתחיל מחדש כשיקבל את כל המשאבים.
ביטול המתנה מעגלית
יש להטיל סדר כולל (total ordering) על כל סוגי המשאבים. תהליך יכול לבקש משאבים רק בסדר עולה לפי מספריהם. אם הוא זקוק למשאב בעל מספר נמוך יותר, עליו לשחרר את כל המשאבים בעלי מספר גבוה יותר.
2. הימנעות ממבוי סתום (Deadlock Avoidance)
גישה זו דורשת מהמערכת מידע מראש על דרישות המשאבים של התהליכים. המערכת מקצה משאבים רק אם היא יכולה להבטיח שהקצאה זו לא תוביל למצב לא בטוח (unsafe state), כלומר מצב שעלול להוביל למבוי סתום.
3. זיהוי ושחזור ממבוי סתום (Deadlock Detection and Recovery)
בגישה זו, המערכת מאפשרת למבוי סתום להתרחש, אך מפעילה מנגנונים לזיהויו ולשחזור ממנו.
זיהוי (Detection)
המערכת בודקת מעת לעת האם קיים מבוי סתום. ניתן לעשות זאת באמצעות:
- גרף הקצאת משאבים (Resource-Allocation Graph): כלי גרפי המייצג תהליכים, משאבים ובקשות/הקצאות. אם הגרף מכיל מעגל (cycle) וכל המשאבים הם מסוג יחיד (single instance), קיים מבוי סתום. אם המשאבים הם מסוגים מרובים (multiple instances), מעגל אינו מספיק להוכחת מבוי סתום, ויש להשתמש באלגוריתם מורכב יותר (דומה לבנקאי).
- גרף המתנה-ל- (Wait-For Graph): גרף פשוט יותר, שבו צמתים מייצגים תהליכים בלבד, וקשת מ-Pi ל-Pj פירושה ש-Pi ממתין למשאב ש-Pj מחזיק. מעגל בגרף זה מעיד על מבוי סתום.
שחזור (Recovery)
לאחר זיהוי מבוי סתום, יש לנקוט בצעדים לשחרור המערכת ממנו:
- הפקעת משאבים (Resource Preemption): לקיחת משאב מתהליך אחד והקצאתו לאחר. יש לבחור "קורבן" (תהליך או משאב) ולהפקיע ממנו משאבים.
- החזרה לאחור (Rollback): החזרת תהליכים למצב קודם בטוח, שבו הם לא היו חלק ממבוי סתום, ושחרור המשאבים שהחזיקו.
- סיום תהליכים (Process Termination):
- סיום כל התהליכים המעורבים במבוי סתום.
- סיום תהליך אחד בכל פעם עד שהמבוי סתום נפתר. יש לבחור את התהליך "הקורבן" בקפידה (למשל, תהליך עם זמן ריצה קצר, מעט משאבים, עבודה שכבר בוצעה וכו').
שאלות לדיון
- הסבר כיצד ביטול התנאי "החזק והמתן" יכול למנוע מבוי סתום, ומהם החסרונות הפוטנציאליים של גישה זו?
- מה ההבדל העיקרי בין מניעת מבוי סתום להימנעות ממבוי סתום? תן דוגמה לתרחיש שבו אחת הגישות עדיפה על השנייה.
- תיאר את אלגוריתם הבנקאי. אילו נתונים הוא דורש מראש, וכיצד הוא משתמש בהם כדי להבטיח מצב בטוח?
- האם מעגל בגרף הקצאת משאבים תמיד מעיד על מבוי סתום? הסבר והדגם.
- אילו שיקולים יש לקחת בחשבון בעת בחירת "קורבן" לשחזור ממבוי סתום באמצעות סיום תהליכים?
נקודות לתשובת מודל
- הגדרה ברורה של מבוי סתום והסבר חשיבותו במערכות הפעלה.
- פירוט והסבר של ארבעת התנאים ההכרחיים למבוי סתום (הדדיות, החזק והמתן, אי-הפקעה, המתנה מעגלית).
- הצגת שלוש הגישות העיקריות לטיפול במבוי סתום: מניעה, הימנעות, זיהוי ושחזור.
- עבור מניעה: הסבר כיצד ניתן לבטל כל אחד מארבעת התנאים, יחד עם היתרונות והחסרונות של כל שיטה.
- עבור הימנעות: הסבר את הרעיון של מצב בטוח/לא בטוח, ופירוט מעמיק של אלגוריתם הבנקאי (כולל דרישותיו ופעולתו).
- עבור זיהוי ושחזור: הסבר שיטות זיהוי (גרף הקצאת משאבים, גרף המתנה-ל-) ושיטות שחזור (הפקעת משאבים, החזרה לאחור, סיום תהליכים).
- השוואה ביקורתית בין הגישות השונות, תוך התייחסות למורכבותן, יעילותן והשפעתן על ביצועי המערכת וניצול המשאבים.
- הדגמה באמצעות דוגמאות קצרות או תרחישים רלוונטיים, במיוחד עבור אלגוריתם הבנקאי וגרפי הקצאת משאבים.