מהו מבוי סתום במערכת ההפעלה: תנאים ואלגוריתם איתור

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

מהו מבוי סתום במערכת ההפעלה?

הַגדָרָה: מנעול מת הוא מצב בו שניים או יותר מעבדים ממתינים לאירוע כלשהו שיקרה, אך אירועים כאלה שאינם קורים הם מצב של מבוי סתום, ועל המעבדים נאמר שהם במצב סגר. לדוגמא, נניח לתרחיש בזמן אמת, בו ישנן שתי מכוניות A & B, המונעות על ידי שני נהגים בודדים בדרך חד כיוונית. כעת נוצר המצב בו נהג רכב נהג אומר שהוא נע לכיוון צפון הוא כיוון נכון, ואילו נהג רכב B אומר שהוא נע לכיוון דרום הוא נכון. אבל אף אחד מהם לא זז אחורה כדי לאפשר למכונית אחרת להתקדם, מצב זה נקרא מצב מבוי סתום.

דוגמא לרכב

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

מעבד לדוגמא

תנאי נעילה מתה

להלן ארבעת התנאים החשובים למבוי סתום להתרחש אם כל התנאים מתרחשים בו זמנית, ישנם סיכויים מסוימים למבוי סתום להתרחש.

הרחקה הדדית

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

הרחקה הדדית

אין קדם-קבלה

לפי מַקדִים אלגוריתמים מבוססים, אם יש משימה עדיפות שמנסה להפריע למשימה הנוכחית. האלגוריתם המונע שהוא מחזיק במשימה הנוכחית ומבצע ראשית משימת עדיפות ומקבל גב למשימה הראשונה שלה. מצב שהוסבר לפי הדוגמה לעיל, כאשר תהליך מחזיק את המשאב כל עוד הוא מבוצע, כלומר P1 יכול לשחרר R1 רק לאחר ביצועו, באופן דומה P2 לשחרר R2 רק לאחר הביצוע. אם אין מניעה מראש, המבוי סתום עלול להתרחש.

דוגמה ללא מקדים

החזק וחכה

תהליך מחזיק משאבים מסוימים ומחכה למשאבים נוספים אך משאבים אלה נרכשים על ידי תהליך אחר. מהדוגמה שלעיל, P1 מחזיק R1 ומחכה ל- R2, שם R2 נרכש על ידי P2, ו- P2 מחזיק R2 ומחכה ל- R1, שם R1 נרכש על ידי P1 הוא מצב המתנה והמתנה עשוי להתרחש במערכת.

החזק-והמתן-דוגמא

המתן מעגלי

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

דוגמה מעגלית-המתנה

אלגוריתם גילוי נעילה מת

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

• מופע יחיד
• מופעים מרובים מסוג המשאבים

מקרה יחיד

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

• גרף הקצאת משאבים: התהליכים P1, P2, P3 והמשאבים R1, R2, R3 מיוצגים בגרף הקצאת המשאבים.
• המתן לגרף: רק התהליכים P1, P2, P3 מוזכרים בהמתנה לגרף.
• אם יש מצב של מחזור, שאם יש זרימה רציפה של תהליך בכיוון אחד זה אומר שיוצא מצב מחזור והמתנה לגרף במצב סגר.

דוגמה 1: הדוגמה שלהלן מראה כי אין מצב מבוי סתום מכיוון שאין זרימה רציפה שנצפה בהמתנה לגרף.

דוגמא למופע יחיד 1

דוגמה 2: מצב מבוי סתום התרחש בגלל שיש זרימה רציפה של מחזור מ- P1 ל- P4.

דוגמא למופע יחיד 2

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

מופעים מרובים מסוג משאבים

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

בואו ניקח בחשבון את הדוגמה הבאה, נניח שיש 3 תהליכים P0, P1, P2, ומשאבים מסוג A, B, C בהם A יכול להיות מעבד , B יכול להיות מדפסת ו- C יכול להיות המקלדת. הספרות '0' בעמודה מייצגות את זמינות המשאבים.

מקרה (i): נניח שאם ניקח את בקשת התנאי היא תנאי '000' הקיים ב- P0 ו- P2, עלינו לבדוק איזו בקשה מתקיימת, התהליכים P0 משחררים את התהליכים לאחר ההקצאה, ואז תהליכי ה- P2 הבאים משתחררים לאחר ההקצאה. ככה, ברצף, תהליך אחד אחד משחרר את P0, P2, P3, P1, P4 ברצף. לבסוף, אנו מקבלים משאבים זמינים כ- P7, P2, P6. הרצף הזמין הוא מצב בו אין מבוי סתום.

בנקאים-אלגוריתם-דוגמה 1

בתים (ii): נניח שאם P2 הוא 001 במקום 000, יש להחיל כעת את האלגוריתם של הבנקאי כדי לבדוק אם מצב מבוי סתום, כאשר ה- P0 היחיד מבוצע בין כל 5 התהליכים. מכאן ש- P1, P2, P3, P4 נמצאים במצב מבוי סתום למעט P0.

בנקאים-דוגמא 2

יישומים של מבוי סתום

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

יתרונות

היתרונות של מבוי סתום הם

• לא נצפתה שום מניעה בהימנעות ממתק
• אין עיכוב בתהליך

חסרונות

החיסרון של מבוי סתום הוא

• יש לדעת מראש על המשאב שיש להשתמש בו
• חסימת התהליך לאורך זמן
• הפסדי קדימה עוברים בתורשה.

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