שאלת מבחן במערכות הפעלה - האוניברסיטה הפתוחה 2016 - קיפאון

מערכת כוללת $p$ תהליכים, שכל אחד מהם זקוק ל-$m$ יחידות של משאב, לכל היותר, והמערכת כוללת בסך הכול $r$ יחידות. נסחו תנאי מספיק לכך שהמערכת לא תגיע ל-deadlock בשום סדרת הקצאות. א. $r > (m-1)p + 1$ ב. $m > (r-1)p + 1$ ג. $p > (m-1)r + 1$ ד. $r > (p-1)p + m$

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

פתרון: התשובה הנכונה היא א'. **קיפאון (deadlock)** במערכת עם סוג משאב יחיד בעל מספר יחידות מתרחש כאשר כל התהליכים במעגל המתנה מחזיקים במשאבים ומבקשים נוספים, ואין מספיק משאבים פנויים כדי לספק אף אחת מהבקשות. כדי למצוא **תנאי מספיק** למניעת קיפאון, עלינו לבחון את **מקרה הגרוע ביותר** שבו קיפאון עלול להתרחש. מקרה זה קורה כאשר כל אחד מ-$p$ התהליכים מחזיק במספר המרבי של משאבים האפשרי מבלי שיוכל לסיים את ריצתו, ובמקביל מבקש משאב נוסף. מכיוון שכל תהליך זקוק לכל היותר ל-$m$ יחידות משאב כדי לסיים, המצב המסוכן ביותר הוא כאשר כל תהליך הצליח לקבל $m-1$ יחידות משאב. במצב זה, אם כל $p$ התהליכים מחזיקים ב-$m-1$ יחידות משאב כל אחד, מספר המשאבים הכולל המוקצה במערכת הוא $p(m-1)$. כדי שייווצר קיפאון, כל $p$ התהליכים יבקשו כעת יחידת משאב נוספת, אך לא יהיו מספיק משאבים פנויים במערכת כדי לספק אפילו בקשה אחת. מצב זה יקרה אם מספר המשאבים הכולל במערכת, $r$, שווה למספר המשאבים המוקצים, כלומר $r = p(m-1)$. כדי להבטיח שלעולם לא יתרחש קיפאון, עלינו להבטיח שגם במקרה הגרוע ביותר שתואר, יישאר לפחות משאב אחד פנוי. אם יש לפחות משאב אחד פנוי, ניתן להקצות אותו לאחד התהליכים הממתינים. אותו תהליך יקבל את המשאב ה-$m$ שלו, יסיים את ריצתו וישחרר את כל $m$ המשאבים שבהם החזיק. משאבים אלו יהפכו זמינים עבור תהליכים אחרים, וכך הקיפאון יימנע. התנאי המתמטי להבטחת קיום של לפחות משאב אחד פנוי הוא: $r > p(m-1)$ שקול לכך, עבור מספרים שלמים, הוא: $r \ge p(m-1) + 1$ כעת נבחן את התשובות המוצעות: א. $r > (m-1)p + 1$, או $r > p(m-1) + 1$. תנאי זה שקול ל-$r \ge p(m-1) + 2$ עבור מספרים שלמים. אם תנאי זה מתקיים, אז בוודאי שגם התנאי $r \ge p(m-1) + 1$ מתקיים. לכן, $r > (m-1)p + 1$ הוא **תנאי מספיק** (אף אם אינו התנאי ההדוק ביותר) למניעת קיפאון. ב, ג, ד: התנאים האחרים אינם קשורים לניתוח מקרה הגרוע ביותר של הקצאת משאבים ואינם מבטיחים מניעת קיפאון. לפיכך, התנאי בא' הוא תנאי מספיק נכון למניעת קיפאון. $\blacksquare$