Overview of Mutual Exclusion and Memory Models in Distributed Systems

Discussion on fast, randomized mutual exclusion techniques by George Giakkoupis and Philipp Woelfel. Exploring asynchronous shared memory systems with atomic operations. Understanding mutual exclusion principles as outlined by Dijkstra in 1965 and measuring time efficiency in critical sections. Delving into distributed shared memory and cache coherent models. Lastly, examining complexity measurements of remote memory references in mutual exclusion algorithms and the concept of randomized algorithms in a distributed system environment.

• Mutual Exclusion
• Memory Models
• Distributed Systems
• Randomized Algorithms
• Asynchronous Memory

pcol Follow

Uploaded on Sep 06, 2024 | 2 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. Fast Randomized Mutual Exclusion George Giakkoupis Philipp Woelfel

2. Asynchronous Shared Memory ? Atomic operations: read & write 4 9 Zzz 1 Shared Memory 7 Zzz 2 Zzz 6 3 ?processes, with IDs 1, ,? No clocks; process run at different speeds Read/writes to shared atomic registers Displexity, Aussois, March 2015 2

3. Mutual Exclusion (Dijkstra, 1965) Synchronize access to a shared resource Mutual Exclusion: At most 1 process in the CS at any time Deadlock-Freedom: If all processes that are not in the Remainder Section take enough steps, some process eventually enters the CS Zzzz 4 3 7 1 6 Remainder Section Entry Section Critical Section (CS) Exit Section Displexity, Aussois, March 2015 3

4. Measuring Time Efficiency To determine that CS is free, processes have to busy-wait (spin on register) Number of steps can be unbounded Count RMRs (Remote Memory References) instead shared memory ? Wait until ? = ? Write ? ? Zzzz 4 3 1 6 Remainder Section Entry Section Critical Section (CS) Exit Section Displexity, Aussois, March 2015 4

5. Distributed Shared Memory Model (DSM) network mem mem mem mem mem Each process has its own locally accessible memory segment Shared memory = union of all local memory segments RMR: remote memory reference Displexity, Aussois, March 2015 5

6. Cache Coherent Model (CC) Main Memory Shared bus cache cache cache cache cache Each process has a local cache RMRs: Cache misses Displexity, Aussois, March 2015 6

7. RMR Complexity [Anderson, 1990]: Avoid RMRs when busy waiting (Local Spin algorithms) Standard complexity measure for mutual exclusion: # RMRs per passage through CS Displexity, Aussois, March 2015 7

8. Randomized Algorithms Processes can flip (private) coins Adversary decides who will take the next step Two extreme adversary models: Strong (adaptive) adversary: Sees all past coin-flips Oblivious adversary: Knows algorithm, but not coin-flips Displexity, Aussois, March 2015 8

9. RMR Complexity of Mutual Exclusion Deterministic, worst-case RMRs per passage ?(????) (CC & DSM) [Yang, Anderson, 1996] ?(????) (CC & DSM) [Attiya, Hendler, Woelfel, 2008] Random., strong adaptive adv., expected RMRs p. passage ?(????/???????) (CC & DSM) [Hendler, Woelfel, 2009] ?(????/???????) (CC & DSM) [Giakkoupis, Woelfel, 2012] Random., oblivious adv., expected RMRs amortized ?((???????)?) (CC) [Bender, Gilbert, 2011] Processes may deadlock with small probability. Displexity, Aussois, March 2015 9

10. New Algorithm Expected RMRs amortized: ?(?)per passage DSM Deterministically deadlock-free Against natural weakadaptive adversary for DSM. Information about past steps and each process next step. Knows whether an operation is an RMR or local and the type (read/write) . Does not learn the exact location of memory accesses or their value. Simple Displexity, Aussois, March 2015 10

11. Sketch of the Algorithm Assumptions Each process goes through CS at most once Atomic CAS objects are available (in addition to registers). Displexity, Aussois, March 2015 11

12. Compare&Swap (CAS) Compare&Swap Object ? C.CAS(old,new) Atomically: If (old = value of C) then C:=new; return old else return value of C Implementations from registers with ?(?)worst-case RMR complexity. [Golab, Hadzilacos, Hendler, Woelfel, 2007] Can be used to replace CAS objects in our algorithm without increasing expected RMR complexity Displexity, Aussois, March 2015 12

13. Backpacking Idea Elect a leader ?: ?.CAS( ,myID) Unbounded RMRs 1. Scan through ?? and collect processes 2. Coordinate processes found through CS 3. Go through CS 4. Reset ?: ?.CAS(?, ) O(1) RMRs per passage 1. Try to notify ?: ??[?].Write(1) 2. Handshake with ? ? saw me; spin in ??[?] until ? lets me enter CS Start over O(1) RMRs per attempt ? 4 3 2 5 1 2 3 1 4 5 Zzzz ?? 6 1 Displexity, Aussois, March 2015 13

14. () Announce trying: [TBD] Elect a leader ?: ?.CAS( ,myID) 1. Scan through ?? and collect processes 2. Coordinate processes found through CS 3. Go through CS 4. Reset ?: ?.CAS(?, ) 1. Try to notify ?: ??[?].Write(1) 2. Handshake with ? ? saw me; spin in ??[?] until ? lets me enter CS Start over Let ?: set of processes that execute ( ) after? is reset by previous leader and before next leader ? scans ?? GOAL:? coordinates ?(|?|) processes through CS, in expectation Displexity, Aussois, March 2015 14

15. If We Had an Oracle Tell me a random proc. from ? 3 5 5 2 ? 5 Zzzz 1 6 Displexity, Aussois, March 2015 15

16. () Announce trying: [TBD] Elect a leader ?: ?.CAS( ,myID) 1. Scan through ?? and collect processes 2. Coordinate processes found through CS 3. Go through CS 4. Reset ?: ?.CAS(?, ) 1. Try to notify ?: ??[?].Write(1) 2. Handshake with ? ? saw me; spin in ??[?] until ? lets me enter CS Start over Let ?: set of processes that execute ( ) after? is reset by previous leader and before next winner ? executes line 0a GOAL:? coordinates ?(|?|) processes through CS, in expectation ? /? Displexity, Aussois, March 2015 16

17. Instead of the Oracle Choose rand. ? s.t: ?? ? = ? = Write ID to ?[?] ?(?) proc. write to ?? bef. ? is done waiting All ???? first entries are w.c.p. Each proc. wrote to ?[????] w.p. ?(?/?) ? ?? 7 19 5 Scan ?until first For all IDs ? found, wait until ??? = ? 3 11 12 16 ? 19 14 2 8 13 log? ? processes log ? 1 5 2 7 3 4 ... 3 ? Zzzz 1 6 ? ? ? 1 0 0 8 2 4 Displexity, Aussois, March 2015 17

18. () Announce trying: [TBD] ( ) Write ID to ?[?] for rand. ? Use seq.# to distinguish old/current writes to ? Elect a leader ?: ?.CAS( ,myID) O(1) RMRs per attempt 1. Scan through ?? and collect processes 2. Coordinate processes found through CS 3. Go through CS 4. Reset ?: ?.CAS(?, ) 1. Try to notify ?: ??[?].Write(1) 2. Handshake with ? O(1) RMRs per passage ? saw me; spin in ??[?] until ? lets me enter CS Start over Let ?: set of processes that execute ( ) after? is reset by previous leader and before next winner ? scans ? GOAL:? coordinates ?(|?|) processes through CS, in expectation Displexity, Aussois, March 2015 18

19. An Issue ?? wins ? ?? ?? ?? wins ? ?? ?? scans ? resets ? scans ? resets ? time Bad Bad Good Good Good If ? processes write to ? during a good interval then ?(?) go through CS before ? is reset Writes to ? during a bad interval are wasted Displexity, Aussois, March 2015 19

20. Using Two Copies Use two copies of the same data structure, e.g. CAS objects ??and ?? for leader election Arrays ?? and ?? for oracle In each attempt, a proc. chooses a random side ? {?,?} The two leaders of both sides sync. using a 2-process lock ? A leader of side ? must Win ? before it scans ?? Release ? after it resets ?? Displexity, Aussois, March 2015 20

21. ?? wins ?? ?? wins ? ?? scans ?? ?? resets ?? ?? rel. ? side 2 ?? wins ?? ?? wins ? ?? scans ?? ?? resets ?? ?? rel. ? ?? wins ?? ?? wins ? ?? scans ?? side 1 time Good on side 1 Good on side 1 Good on side 2 Good on side 2 Each process chooses a good side w.p. Half of the processes write on ? during a good interval on their chosen side ? ? FOCS'14, Philadelphia 21

22. Remarks Algorithm slightly more complicated Need careful handshaking / use of seq. numbers Sequence numbers can be bounded Starvation-freedom easy to achieve Displexity, Aussois, March 2015 22

23. Open Problems Expected amortized ?(?) RMRs in the CC Model? Non-amortized ?(?) RMRs? Abortable? Thank you ! Displexity, Aussois, March 2015 23