1 Multiprocessor Synchronization AlgorithmsRehearsal for final exam fall 2015/2016 Lecturer: Danny Hendler

2 Leader election questionSolution intuition Choose unique ID as leader Send ID to right and left Receive neighbor IDs. If one of them equals myID – not leader Otherwise, have to verify this is not a 2-process ring Send leader-candidate message with ID Leader-candidate with bigger ID is selected.

3 Solution left, right initially null Upon start signalSend ID-msg(myID) to left and right Upon receiving ID-msg(id) from left/right if id = myID left/right=equal else if id < myID left/right=smaller else left/right=bigger if (left <> null) and (right <> null) if left < > equal AND right < > equal leader=maybe send leader-candidate(myID) to left else leader=false Upon receiving leader-candidate(id) from right if leader=false send message to left else if id > myID leader=false send message to left else if id=myID leader=true

4 Mutual exclusion questionהוכיחו באופן מדויק ופורמלי את הטענה הבאה עבור מודל cache-coherent: בכל אלגוריתם חסר-קיפאון deadlock-free) ) למניעה הדדית עבור n תהליכים מ-single-writer-multi-reader registers , יש ריצה בה תהליך צריך לבצע O(n) גישות לא מקומיות (remote memory references) במהלך קטע הכניסה. נניח בשלילה שקיימת ריצה E בסופה תהליך כלשהו, בה"כ p0, נכנס לקטע הקריטי בריצה סולו בה הוא מבצע פחות מn-1 גישות, אזי ישנו תהליך אחר pi כך ש-p0 אינו קורא שום רגיסטר של pi. תהא F ריצה של pi בסופה הוא נכנס לקטע הקריטי. מאחר ו-p0 אינו קורא ב-E שום רגיסטר אליו pi כתב ב-F, הריצה FE חוקית ו-p0 אינו יכול להבחין בינה ובין הריצה E ולפיכך יכנס לקטע הקריטי גם בסופה. נובע ששני התהליכים נמצאים בקטע הקריטי בסוף הריצה FE, סתירה. הראינו שתהליך חייב לבצע לפחות n-1 גישות למשתנים שונים – לפחות משתנה אחד של כל אחד משאר התהליכים. במודל ה-CC גישה ראשונה למשתנה היא תמיד RMR ומכאן נובעת הטענה.

5 A question from assignment 3

6 Solution הוכחה: נבנה בהדרגה ריצה בה מספר הולך וגדל של משתנים (משותפים) שונים מכוסים, כלומר עומדים להכתב ע"י תהליכים שונים, וכך נגיע לחסם הנדרש. בסיס: תהליך p1 מבצע פעולה של Write(1) על אובייקט ה-max. נריץ את p1 עד אשר הוא עומד לכתוב לאיזשהו משתנה או עד אשר הוא מסיים, תהא E1 הריצה המתקבלת. לא יתכן ש-p1 מסיים את פעולת ה-Write מבלי לכתוב, שכן במקרה כזה פעולת Read על האובייקט תחזיר 0, ולכן בסוףE1 תהליך p1 עומד לכתוב למשתנה כלשהו, נסמנו ב-R1. אינדוקציה: בנינו ריצה E1 E2 … Ek בסופה תהליכים p1,…,pk מכסים את המשתנים R1,...,Rk. אם k

7 Mutual exclusion question

8 Solution: intuitions Mutual exclusionAt least one process has to block at every level l, unless there are no other processes at level l or higher. It can therefore be proven by induction that at most n-k processes pass every level k (hence just a single process passes level (n-1).

9 Intuitions (cont'd) Deadlock-freedom Starvation freedomConsider a specific configuration where some processes are active and consider the processes at the highest level l. If there is a single process at level l, it can ascend to the next level. If there are a few processes at level l, then at least one of them is not the last to execute line 3 at that level, and that process may proceed. Starvation freedom We already saw that there is global progress Assume there are stuck processes, and consider a process q stuck at the topmost level, say k. From the algorithm and assumptions, eventually all processes in higher levels terminate. Hence q will eventually be able to climb up.

10 Intuitions (cont'd) Worst-case number of RMRs Intuition“Slowest” process may be bypassed on all levels: By n-1 processes at level 1 By n-2 processes at level 2 … May therefore incur Ω(n3) RMRs altogether at the 2’nd part of line 4.

11 Detailed proofs (Vitaly…)

12 Detailed proofs (cont'd)

13 Detailed proofs (cont'd)

14 Detailed proofs (cont'd)

15 Detailed proofs (cont'd)

16 Detailed proofs (cont'd)

17 Detailed proofs (cont'd)

18 Detailed proofs (cont'd)

19 Detailed proofs (cont'd)

20 Wait-free simulation questionאובייקט CAS תומך בפעולות read ו-compare-and-swap. פעולת read מחזירה את ערכו הנוכחי של האובייקט. פעולת compare-and-swap(cur,new) פועלת באופן אטומי כך: היא משווה את ערכו הנוכחי של האובייקט עם הארגומנט cur. אם הערכים שונים, היא מחזירה ערך false ואינה משנה את ערך האובייקט. לעומת זאת, אם ערכו של האובייקט שווה ל-cur, הפעולה משנה את ערך האובייקט ל-new ומחזירה true. נגדיר אובייקט חדש בשם new-CAS. האובייקט מוגדר בדיוק כמו אובייקט CAS למעט הבדל יחיד: פעולת compare-and-swap מחזירה את ערכו של האובייקט ברגע שלפני ביצוע הפעולה במקום להחזיר ערך של true/false. לדוגמא: נניח כי ערכו של אובייקט new-CAS הוא 5 ומופעלת עליו פעולת compare-and-swap(2,3), אזי הפעולה תחזיר 5 (ולא תשנה את ערכו של האובייקט). אם ערכו של האובייקט הוא 5 ומופעלת עליו פעולת compare-and-swap(5,3), אזי הפעולה תשנה את ערך האובייקט ל-3 ותחזיר 5. ניתן להניח כי אובייקט ה-CAS יכול לשמור ערכים גדולים כרצוננו. ניתן גם להניח כי שני הארגומנטים לפעולת ה-compare-and-swap שונים תמיד זה מזה. ממשו באופן חסר המתנות (wait-free) ולינאריזבילי אובייקט New-CAS מאובייקט יחיד של CAS. (כתמיד, ניתן להשתמש ללא הגבלה במשתנים מקומיים.) מימוש המשתמש במספר אובייקטים של CAS ו/או ברגיסטרים יקנה ניקוד חלקי. ציינו מהן נקודות הלינאריזציה של פעולות ה-read וה-compare-and-swap באלגוריתם שלכם ונמקו בקצרה אך במדוייק מדוע האלגוריתם חסר-המתנות ולינאריזבילי (אין צורך בהוכחה פורמלית).

21 Solution intuitions If we only store the “regular” CAS value, not clear if we can solve the problem – we need some meta-information Store a pair of values in the CAS object: values. Sort out which to return so that linearizability is maintained.

22 Solution We assume cur, new arguments are different.Shared c: CAS initially newCAS.read( ) { =c.read( ) return c } newCAS.compare-and-swap(cur,new) { =c.read () if (c < > cur) return c else if c.compare-and-swap(, ) return cur else =compare-and-swap.read() return p } We assume cur, new arguments are different.

23 Solution (continued) Wait-freedom is trivial. Lineraization points:Shared c: CAS initially newCAS.read( ) { =c.read( ) return c } newCAS.compare-and-swap(cur,new) { =c.read () if (c < > cur) return c else if c.compare-and-swap(, ) return cur else =compare-and-swap.read() return p } In line 5, value was cur In line 8, value IS NOT cur Changed to non-cur at some point during CAS execution before it was changed to cur again (as read in line 11) Can be linearized to when p was written Wait-freedom is trivial. Lineraization points: Read operation – line 2 compare-and-swap returning in line 7 (failed CAS) – line 5 compare-and-swap returning in line 9 (successful CAS) – line 8 compare-and-swap returning in line 13 (failed CAS) – line 11 compare-and-swap returning in line 15 (failed CAS) - at what time?

24 Good luck!