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

פרוטוקול סנכרון barrier synchronization – `bsync` המוגדר כדלקמן : $P = \{P_1, \dots, P_n\}$ קבוצת תהליכים בגודל $n$. נסמן ב- $bsync(i,k)$ את ההפעלה ה- $k$-ית של הפרימיטיב `bsync` ע"י התהליך $P_i$ ($k > 0$). פעולת $bsync(i,k)$ איננה חוזרת עד שכל תהליך $P_j$, $1 \le j \le n$, יקרא $k$ פעמים ל- `bsync`. במילים אחרות, תהליך נתון "מסתכל" כמה פעמים התבצע `bsync` ע"י תהליכים אחרים ביחס לכמות הפעמים שהוא הפעיל את הפעולה. כל הפעלה של `bsync` מבטיחה שתהליך לא ממשיך עד ששאר התהליכים ביצעו כמות זהה של קריאות ל- `bsync`. למשל, בדוגמא הבאה שבה $n=3$, פעולה `bsync` בשורה 6 בקוד של תהליך $P_2$ לא תחזור עד שתהליך $P_1$ יקרא לפעולה `bsync` בשורה 8 ותהליך $P_3$ יקרא לפעולה `bsync` בשורה 7. | line | P3 | P2 | P1 | |---|---|---|---| | 1 | ... | bsync | ... | | 2 | ... | ... | ... | | 3 | bsync | ... | ... | | 4 | ... | ... | ... | | 5 | ... | ... | ... | | 6 | ... | bsync | ... | | 7 | bsync | ... | bsync | | 8 | ... | bsync | bsync | | 9 | bsync | ... | bsync | א. (10 נק') כתבו פסאודו-קוד ל- `bsync` למקרה שבו כל תהליך מפעיל את `bsync` פעם אחת בלבד. השתמשו ב- `test-and-set-locked` ו- `read/write` אטומיים בלבד (הניחו שהפונקציות הנ"ל נתונות לכם). ב. (20 נק') כתבו פסאודו-קוד ל- `bsync` למקרה שבו כל תהליך מפעיל את `bsync` מספר כלשהו של פעמים. השתמשו ב- `test-and-set-locked` ו- `read/write` אטומיים בלבד (הניחו שהפונקציות הנ"ל נתונות לכם).

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

פתרון: ### סעיף א': מימוש `bsync` לשימוש יחיד למימוש מחסום סנכרון לשימוש יחיד, נשתמש במונה משותף שיספור את מספר התהליכים שהגיעו למחסום, ובדגל (gate) שישחרר אותם. כדי למנוע **תנאי מרוץ** בעת עדכון המונה המשותף, נשתמש במנעול הממומש באמצעות הפרימיטיב **`test-and-set-locked`**. הלוגיקה היא כדלקמן: 1. כל תהליך שמגיע למחסום נועל מנעול, כדי להבטיח גישה בלעדית למשתנים המשותפים (להיכנס ל**קטע קריטי**). 2. התהליך מקדם מונה משותף, `count`. 3. אם התהליך הנוכחי הוא האחרון (כלומר, `count` שווה למספר התהליכים הכולל, `n`), הוא משנה את ערכו של משתנה משותף אחר, `gate`, כדי לסמן לשאר התהליכים שהם רשאים להמשיך. 4. התהליך משחרר את המנעול. 5. כל התהליכים (כולל האחרון) ממתינים בלולאת **המתנה פעילה** (busy-waiting) עד שהמשתנה `gate` יקבל ערך `true`. ברגע שזה קורה, כל התהליכים יוצאים מהמחסום וממשיכים בהרצתם. $\blacksquare$ להלן הפסאודו-קוד: ``` // משתנים גלובליים משותפים integer n = ... // מספר התהליכים הכולל integer count = 0 boolean lock = false boolean gate = false procedure bsync(): // כניסה לקטע קריטי באמצעות spinlock while test_and_set_locked(&lock) do // busy wait end while // --- קטע קריטי --- count = count + 1 if count == n then gate = true // התהליך האחרון פותח את השער לכולם end if // יציאה מהקטע הקריטי lock = false // כל התהליכים ממתינים כאן עד שהשער ייפתח while not gate do // busy wait end while ``` ### סעיף ב': מימוש `bsync` לשימוש רב-פעמי הפתרון מסעיף א' אינו בטוח לשימוש חוזר. תהליך מהיר שיסיים את המחסום ויקרא ל-`bsync` פעם נוספת עלול להתחיל לספור עבור המחסום הבא, לפני שכל התהליכים האיטיים סיימו את המחסום הנוכחי. כדי לפתור זאת, נשתמש בטכניקה הנקראת **מחסום עם חיווי מתהפך (sense-reversing barrier)**. בשיטה זו, אנו משתמשים במשתנה "חיווי" (sense) גלובלי, שערכו מתהפך בכל פעם שהמחסום הושלם. בנוסף, כל תהליך שומר משתנה חיווי מקומי משלו. תהליך יכול לעבור את המחסום רק כאשר ערך החיווי הגלובלי זהה לערך החיווי המקומי שלו. הלוגיקה היא כדלקמן: 1. בכל כניסה ל-`bsync`, התהליך הופך את ערך החיווי **המקומי** שלו (`my_sense`). 2. התהליך נכנס לקטע קריטי (באמצעות אותו מנעול `test-and-set-locked`), מקדם את המונה `count`. 3. אם התהליך הוא האחרון שהגיע (`count == n`), הוא מאפס את המונה לקראת המחסום הבא, והופך את ערך החיווי **הגלובלי** (`sense`) כך שיהיה זהה לחיווי המקומי של התהליכים בסיבוב הנוכחי. פעולה זו משחררת את כל התהליכים הממתינים. 4. התהליך יוצא מהקטע הקריטי. 5. כל תהליך ממתין בלולאת המתנה פעילה עד שערך החיווי הגלובלי יהפוך זהה לערך החיווי המקומי שלו. היפוך החיווי בכל מחזור מבטיח שתהליכים ממחזור `k` לא יתערבבו עם תהליכים ממחזור `k+1`. $\blacksquare$ להלן הפסאודו-קוד: ``` // משתנים גלובליים משותפים integer n = ... // מספר התהליכים הכולל integer count = 0 boolean lock = false boolean sense = true // החיווי הגלובלי // משתנה מקומי לכל תהליך (thread-local) // הערך נשמר בין קריאות לפונקציה עבור אותו תהליך thread_local boolean my_sense = true procedure bsync(): // היפוך החיווי המקומי של התהליך my_sense = not my_sense // כניסה לקטע קריטי while test_and_set_locked(&lock) do // busy wait end while // --- קטע קריטי --- count = count + 1 if count == n then count = 0 // איפוס המונה למחסום הבא sense = my_sense // היפוך החיווי הגלובלי לשחרור התהליכים end if // יציאה מהקטע הקריטי lock = false // המתן עד שהחיווי הגלובלי יתאים לחיווי המקומי while sense != my_sense do // busy wait end while ```