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

הוכיחו או הפריכו את הטענות הבאות לגבי אלגוריתם הבנקאי (`banker algorithm`). א. (10 נק') מהי בעיית היפוך עדיפויות (`priority inversion problem`)? כיצד היא יכולה להתעורר? כיצד ניתן להתגבר על הבעיה? ב. (20 נק') חמישה תהליכים $A, B, C, D, E$ הגיעו למערכת בסדר א"ב-י בזמן $t$. הטבלה מטה מתארת את זמן ה CPU הנדרש לתהליכים הללו ואת עדיפותם (ערך קטן מסמל עדיפות גבוהה): | | CPU Burst | Priority | |---|---|---| | A | 3 | 3 | | B | 7 | 5 | | C | 5 | 1 | | D | 2 | 4 | | E | 6 | 2 | מלאו את הפרטים החסרים בטבלה הבאה: זמן הממנה לכל תהליך בהינתן מדיניות תזמון וזמן המתנה ממוצע לכל אחת ממדיניות התזמון: | Scheduling Policy | Waiting Time A | Waiting Time B | Waiting Time C | Waiting Time D | Waiting Time E | Average Waiting Time | |---|---|---|---|---|---|---| | First-Come-First-Served | | | | | | | | Non-Preemptive Shortest-Job First | | | | | | | | Priority | | | | | | | | Round-Robin (time quantum=2) | | | | | | |

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

פתרון: א. **היפוך עדיפויות (Priority Inversion)** **הגדרה:** היפוך עדיפויות הוא תרחיש במערכות מרובות-משימות שבו תהליך בעל עדיפות גבוהה נאלץ להמתין לתהליך בעל עדיפות נמוכה ממנו. הבעיה מחמירה כאשר תהליך בעדיפות בינונית, שאינו תלוי במשאב המשותף, מונע מהתהליך בעל העדיפות הנמוכה לרוץ, ובכך מעכב בעקיפין את התהליך בעל העדיפות הגבוהה. **אופן התרחשות:** הבעיה מתעוררת בדרך כלל בנוכחות שלושה תהליכים (או יותר) בעלי רמות עדיפות שונות (גבוהה $H$, בינונית $M$, ונמוכה $L$) ומשאב משותף המוגן על ידי **מנעול** (כגון **סמפור** או mutex). 1. תהליך $L$ (עדיפות נמוכה) רוכש את המנעול ונכנס ל**קטע קריטי**. 2. תהליך $H$ (עדיפות גבוהה) מתעורר ומוכן לריצה. מכיוון שעדיפותו גבוהה יותר, הוא מבצע **החלפת הקשר** (preemption) ומדיח את $L$. 3. תהליך $H$ מנסה לרכוש את אותו המנעול, אך הוא תפוס על ידי $L$. כתוצאה מכך, $H$ נחסם ועובר למצב המתנה. 4. המערכת מחזירה את $L$ לריצה כדי שישחרר את המנעול. 5. בשלב זה, תהליך $M$ (עדיפות בינונית) מתעורר ומוכן לריצה. עדיפותו גבוהה מזו של $L$, ולכן הוא מדיח את $L$. 6. כעת, $M$ רץ, בעוד $H$ מחכה ל-$L$, ו-$L$ מחכה ל-$M$. התהליך בעל העדיפות הגבוהה ביותר, $H$, נאלץ להמתין לסיומו של תהליך בעדיפות בינונית, $M$. **פתרונות:** 1. **ירושת עדיפויות (Priority Inheritance):** כאשר תהליך $H$ נחסם על ידי משאב שמוחזק על ידי תהליך $L$, העדיפות של $L$ "יורשת" באופן זמני את העדיפות של $H$. במקרה זה, עדיפותו של $L$ תועלה לזו של $H$, מה שימנע מתהליכים בעדיפות בינונית כמו $M$ להדיח אותו. ברגע ש-$L$ משחרר את המנעול, עדיפותו חוזרת לערכה המקורי, ו-$H$ יכול להמשיך בריצתו. 2. **תקרת עדיפויות (Priority Ceiling Protocol):** לכל משאב משותף מוגדרת "תקרת עדיפות", שהיא העדיפות הגבוהה ביותר מבין כל התהליכים שעשויים לרכוש אותו. כאשר תהליך כלשהו רוכש את המשאב, עדיפותו שלו מועלית באופן זמני לתקרת העדיפות של המשאב. שיטה זו מונעת לא רק היפוך עדיפויות אלא גם **קיפאון (deadlock)** במצבים מסוימים. ב. נחשב את זמני ההמתנה עבור כל מדיניות תזמון. **זמן המתנה** של תהליך מוגדר כזמן הכולל שהוא מבלה בתור המוכנים (ready queue). מאחר שכל התהליכים מגיעים בזמן $t=0$, זמן ההמתנה הוא: $Waiting\ Time = Completion\ Time - Burst\ Time$. **1. First-Come-First-Served (FCFS)** סדר הביצוע הוא A, B, C, D, E. דיאגרמת גנט: `| A(3) | B(7) | C(5) | D(2) | E(6) |` `0------3------10-----15-----17-----23` - A: $3 - 3 = 0$ - B: $10 - 7 = 3$ - C: $15 - 5 = 10$ - D: $17 - 2 = 15$ - E: $23 - 6 = 17$ זמן המתנה ממוצע: $\frac{0+3+10+15+17}{5} = 9$ **2. Non-Preemptive Shortest-Job First (SJF)** סדר הביצוע לפי אורך הריצה: D(2), A(3), C(5), E(6), B(7). `| D(2) | A(3) | C(5) | E(6) | B(7) |` `0------2------5------10-----16-----23` - A: $5 - 3 = 2$ - B: $23 - 7 = 16$ - C: $10 - 5 = 5$ - D: $2 - 2 = 0$ - E: $16 - 6 = 10$ זמן המתנה ממוצע: $\frac{2+16+5+0+10}{5} = 6.6$ **3. Priority (Non-Preemptive)** סדר הביצוע לפי עדיפות: C(1), E(2), A(3), D(4), B(5). `| C(5) | E(6) | A(3) | D(2) | B(7) |` `0------5------11-----14-----16-----23` - A: $14 - 3 = 11$ - B: $23 - 7 = 16$ - C: $5 - 5 = 0$ - D: $16 - 2 = 14$ - E: $11 - 6 = 5$ זמן המתנה ממוצע: $\frac{11+16+0+14+5}{5} = 9.2$ **4. Round-Robin (RR) with quantum=2** דיאגרמת גנט: `|A|B|C|D|E|A|B|C|E|B|C|E|B|` `0-2-4-6-8-10-11-13-15-17-19-20-22-23` זמני סיום: A=11, B=23, C=20, D=8, E=22. - A: $11 - 3 = 8$ - B: $23 - 7 = 16$ - C: $20 - 5 = 15$ - D: $8 - 2 = 6$ - E: $22 - 6 = 16$ זמן המתנה ממוצע: $\frac{8+16+15+6+16}{5} = 12.2$ **טבלת סיכום:** | Scheduling Policy | Waiting Time A | Waiting Time B | Waiting Time C | Waiting Time D | Waiting Time E | Average Waiting Time | |---|---|---|---|---|---|---| | First-Come-First-Served | 0 | 3 | 10 | 15 | 17 | 9.0 | | Non-Preemptive Shortest-Job First | 2 | 16 | 5 | 0 | 10 | 6.6 | | Priority | 11 | 16 | 0 | 14 | 5 | 9.2 | | Round-Robin (time quantum=2) | 8 | 16 | 15 | 6 | 16 | 12.2 |