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

למדנו אלגוריתם פטרסון המהווה פתרון סביר לבעיית קטע קריטי בין שני תהליכונים. הפתרון שלמדנו עובד על ארכיטקטורה עם זיכרון מטמון. כעת הניחו שבמחשב עבורו אתם כותבים קוד אין זיכרונות מטמון (אין cache). כלומר, כתיבה ע"י תהליכון אחד לזיכרון תראה באופן מיידי על ידי תהליכון אחר. להלן פסודו-קוד שמתאר את האלגוריתם למניעה הדדית אשר חסרים בו מספר פרטים: סימונים: $Q1$ מציין שתהליכון T1 מעוניין להיכנס לקטע הקוד הקריטי. $Q2$ מציין שחוט T2 מעוניין להיכנס לקטע הקוד הקריטי. קו תחתון (____) מציין מקום שבו עליכם להשלים את קטע הקוד ```c Q1 := false; Q2 := false; TURN = 1; // valid values for TURN are 1 and 2 protocol of T1 Q1 = true; TURN = ____ ; while( Q2 and ____ ) /*do nothing*/ ; /* here is the critical section */ Q1 := false; protocol of T2 Q2 = true; TURN = ____ ; while( Q1 and ____ ) /*do nothing*/ ; /* here is the critical section */ Q2 := false ``` א. (8 נק׳) נא השלימו את הפרטים (בטבלה לעיל) כך שמובטח שיש מניעה הדדית ואין הרעבה. ב. (8 נק׳) הסבירו מדוע האלגוריתם שהשלמתם מבטיח מניעה הדדית. ג. (8 נק׳) הסבירו מדוע האלגוריתם שהשלמתם מבטיח שאין הרעבה.

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

פתרון: א. הקוד המושלם עבור אלגוריתם פטרסון הוא כדלקמן: **פרוטוקול עבור T1:** ```c Q1 = true; TURN = 2; while( Q2 and TURN == 2 ) /*do nothing*/ ; /* here is the critical section */ Q1 := false; ``` **פרוטוקול עבור T2:** ```c Q2 = true; TURN = 1; while( Q1 and TURN == 1 ) /*do nothing*/ ; /* here is the critical section */ Q2 := false; ``` ב. **הוכחת מניעה הדדית (Mutual Exclusion)** נניח בשלילה ששני התהליכונים, T1 ו-T2, נמצאים ב**קטע הקריטי** בו-זמנית. 1. כדי ש-T1 ייכנס לקטע הקריטי, התנאי בלולאת ה-`while` שלו, `(Q2 and TURN == 2)`, היה צריך להיות שקרי בפעם האחרונה ש-T1 בדק אותו. 2. כדי ש-T2 ייכנס לקטע הקריטי, התנאי בלולאת ה-`while` שלו, `(Q1 and TURN == 1)`, היה צריך להיות שקרי בפעם האחרונה ש-T2 בדק אותו. מאחר ששני התהליכונים נמצאים בקטע הקריטי, שניהם בהכרח ביצעו את השורות שבהן הם מצהירים על כוונתם להיכנס, כלומר `Q1 = true` ו-`Q2 = true`. לכן, בזמן בדיקת התנאי, גם `Q1` וגם `Q2` היו `true`. מכאן נובע: * כדי ש-T1 ייכנס, התנאי `TURN == 2` היה חייב להיות שקרי, כלומר **`TURN` היה שווה ל-1**. * כדי ש-T2 ייכנס, התנאי `TURN == 1` היה חייב להיות שקרי, כלומר **`TURN` היה שווה ל-2**. קיבלנו סתירה: המשתנה המשותף **`TURN`** אינו יכול להיות שווה גם ל-1 וגם ל-2 באותו הזמן. הסתירה נובעת מההנחה ששני התהליכונים יכולים להיות בקטע הקריטי בו-זמנית. לכן, הנחה זו שגויה, ו**מניעה הדדית** מובטחת. המשתנה `TURN` משמש למעשה כ"שובר שוויון": התהליכון האחרון שקבע את ערכו של `TURN` הוא זה שמוותר ומאפשר לתהליכון השני להיכנס ראשון. $\blacksquare$ ג. **הוכחה לאי-קיום הרעבה (No Starvation)** נוכיח שהאלגוריתם מבטיח **המתנה מוגבלת (bounded waiting)**, תכונה חזקה יותר שממנה נובע שאין **הרעבה**. המתנה מוגבלת פירושה שתהליכון המעוניין להיכנס לקטע הקריטי ימתין לכל היותר מספר כניסות מוגבל של תהליכונים אחרים. במקרה זה, נוכיח שהוא ימתין לכל היותר כניסה אחת של התהליכון השני. נניח שתהליכון T1 מעוניין להיכנס לקטע הקריטי. הוא מבצע `Q1 = true` ו-`TURN = 2`, ונעצר בלולאת ה-`while` שלו. כדי ש-T1 יישאר תקוע בלולאה, התנאי `(Q2 and TURN == 2)` חייב להישאר אמת. כלומר, `Q2` חייב להיות `true` וגם `TURN` חייב להיות 2. אם `Q2` הוא `true`, פירוש הדבר שגם T2 מעוניין להיכנס לקטע הקריטי. אם T2 נמצא בקטע הקריטי, הוא ייצא ממנו בזמן סופי (בהנחה סבירה שהקטע הקריטי מסתיים) ויבצע `Q2 = false`. פעולה זו תגרום לתנאי הלולאה של T1 להפוך לשקרי, ו-T1 יוכל להיכנס. המקרה המעניין הוא אם T2 מנסה להיכנס שוב לקטע הקריטי מיד לאחר שיצא, לפני ש-T1 הספיק להיכנס. ננתח את הרצף האפשרי: 1. T1 ממתין. התנאי `(Q2 and TURN == 2)` הוא אמת. 2. T2 מסיים את הקטע הקריטי ומבצע `Q2 = false`. כעת התנאי של T1 הופך לשקרי. 3. נניח שהמתזמן מעביר את המעבד ל-T2 לפני ש-T1 מספיק לבדוק את התנאי שוב. T2 מנסה להיכנס שוב: הוא מבצע `Q2 = true` ואז **`TURN = 1`**. 4. כעת, כשהמתזמן מחזיר את המעבד ל-T1, T1 בודק את תנאי הלולאה שלו `(Q2 and TURN == 2)`. הוא יראה ש-`Q2` אכן חזר להיות `true`, אבל `TURN` שווה כעת ל-1. לכן, התנאי `TURN == 2` שקרי, והתנאי כולו שקרי. T1 ייכנס לקטע הקריטי. במצב זה, T2 הוא שיצטרך להמתין, מכיוון שהתנאי שלו, `(Q1 and TURN == 1)`, יהיה אמת (כי T1 עומד להיכנס ולכן `Q1` הוא `true`, ו-T2 עצמו קבע `TURN=1`). לסיכום, ברגע שתהליכון T1 מביע את רצונו להיכנס (`Q1=true`), תהליכון T2 יכול להיכנס לקטע הקריטי לכל היותר פעם אחת נוספת לפני ש-T1 יקבל את ההזדמנות להיכנס. זה מוכיח **המתנה מוגבלת**, ולכן מובטח ש**אין הרעבה**. $\blacksquare$