Understanding Synchronization Methods in Computing

Slide Note
Embed
Share

Exploring synchronization methods like mutual exclusion, deadlock, starvation, and hardware mutex support in computing. Learn about critical sections, preventing race conditions, and the challenges of synchronization. Consider the Test and Set method, its benefits and drawbacks, and the importance of protecting critical sections for efficient and fair execution.


Uploaded on Sep 12, 2024 | 0 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.

E N D

Presentation Transcript


  1. CS 105 Tour of the Black Holes of Computing Synchronization Methods Topics Mutual-exclusion methods Producer/consumer problem Readers/writers problem

  2. Deadlock and Starvation Three bad things can happen in concurrency Inconsistency: incorrect results, e.g. from races Deadlock: Nobody can make progress Starvation:No deadlock, but somebody doesn t make progress CS 105 2

  3. Mutual Exclusion Need ways to enforce critical sections Prevent race conditions that cause errors Requirements for mutual exclusion Safety: only one process or thread at a time inside CS Progress: if nobody has access and somebody wants in, somebody gets in No starvation: if you want in, you will eventually get in Desirable properties: Efficiency: can get into CS in relatively few instructions Low load: waiting for CS doesn t waste resources Fairness: if you want in, nobody else gets in ahead of you twice CS 105 3

  4. Additional Requirements Synchronization is tricky to get right Failure to protect critical sections Incorrect use of primitives Deadlock Programmer-friendliness is big plus CS 105 4

  5. Hardware Mutex Support Test and Set Read word, set it nonzero, and set condition codes All in one indivisible operation Compare and Swap Read word, compare to register; if match then store some other register into word Again, indivisible Generalization of Test & Set Double Compare and Swap Extends CAS to two (noncontiguous) locations Turns out to not be that useful; omitted in current designs CS 105 5

  6. Example of Test and Set enter_critical_region: leaq lock, %eax .L1: tsl (%eax) jne .L1 ; We now have exclusive access ret ; Set lock NZ, set CC ; Loop if was already NZ leave_critical_region: movb $0, lock ret CS 105 6

  7. Evaluating Test and Set + Very fast entry to unlocked region + Easy to implement (except on multi-core hardware!) + Guarantees safety & progress - Wastes CPU when waiting (spin lock/busy wait) - Doesn t make it easy for other threads to run - Extremely high memory (i.e., bus) traffic - Prone to errors (e.g., forget to unlock) - Prone to unfairness and starvation For these reasons, test & set is used only to implement higher-level constructs CS 105 7

  8. Semaphores Higher-level construct, discussed previously Invented by Edsger Dijkstra P(sem) or wait(sem) decrements and possibly waits V(sem) or signal(sem) increments and lets somebody else in Usually implemented by operating system Allows scheduler to run different thread while waiting OS can guarantee fairness and no starvation Or can even enforce priority scheme More flexibility for user (e.g., can count things) Still error-prone P s and V s must be matched Single extra V blows mutual exclusion entirely (compare Test & Set) CS 105 8

  9. Monitors High-level mutual-exclusion construct Invented by C.A.R. Tony Hoare (also quicksort inventor) Difficult or impossible to use incorrectly Like Java/C++ class: combines data with functions needed to manage it Keys to monitor correctness Data is available only to functions within monitor Specific functions (gatekeepers) control access Only one process/thread allowed inside monitor at a time Queues keep track of who is waiting for monitor Turns out to be hard to do certain things with monitors Programmers wind up standing on heads or implementing things like semaphores CS 105 9

  10. Problems in Synchronization Many standard problems in concurrent programming Producer/consumer Readers/writers Dining philosophers Drinking philosophers Etc. Standard problems capture common situations Also give way to evaluate proposed synchronization mechanisms CS 105 10

  11. The Producer/Consumer Problem Two processes communicate Producer generates things (e.g., messages) into a buffer Consumer takes those things and uses them Correctness requirements Producer must wait if buffer is full Consumer must not extract things from empty buffer Order must be maintained Solutions Can be done with just load/store (but tricky) We have seen simple semaphore-based solution for one- element buffer Perfect application for monitors CS 105 11

  12. Producer/Consumer with Monitors monitor producerconsumermonitor; var buffer[0..slots-1] of message; slotsinuse: 0..slots; nexttofill, nexttoempty: 0..slots-1; bufferhasdata, bufferhasspace: condition; procedure fillslot(var data: message) begin if slotsinuse = slots; then wait(bufferhasspace); buffer[nexttofill] := data; nexttofill := (nexttofill + 1) mod slots; slotsinuse := slotsinuse + 1; signal(bufferhasdata); end; CS 105 12

  13. Producer/Consumer with Monitors (continued) procedure emptyslot(var data: message) begin if slotsinuse = 0; then wait(bufferhasdata); data := buffer[nexttoempty]; nexttoempty = (nexttoempty + 1) mod slots; slotsinuse := slotsinuse 1; signal(bufferhasspace); end; begin slotsinuse := 0; nexttofill := 0; nexttoempty := 0; end; CS 105 13

  14. Exercise: P/C with Semaphores Form a small team (2-4 people) Sketch out a producer/consumer solution Multiple slots in buffer Buffer used circularly ( ring buffer) Use only two semaphores Find a way to count with them! CS 105 14

  15. Solution: P/C with Semaphores semaphore empty_slots = N; semaphore full_slots = 0; void produce(int data) { P(empty_slots); buffer[next_empty] = data; next_empty = (next_empty + 1) % N; V(full_slots); } int consume() { P(full_slots); data = buffer[next_full]; next_full = (next_full + 1) % N; V(empty_slots); return data; } CS 105 15

  16. The Readers/Writers Problem More complex than producer/consumer Many processes accessing single resource Some read, some write (some could do both) OK for many to read at once No danger of stepping on each others feet Only one writer allowed at a time Examples: Shared access to file ATMs displaying or updating bank balance CS 105 16

  17. Readers/Writers with Semaphores (Polling Version) semaphore mutex = 1; int nreaders = 0, nwriters = 0; void reader() { while (1) { P(mutex); while (nwriters != 0) { V(mutex); wait_a_while(); P(mutex); } nreaders++; V(mutex); read(); P(mutex); nreaders--; V(mutex); } } CS 105 17

  18. Readers/Writers with Semaphores (Polling continued) void writer() { while (1) { P(mutex); while (nreaders + nwriters != 0) { V(mutex); wait_a_while(); P(mutex); } nwriters++; V(mutex); /* not really needed why? */ write(); P(mutex); /* not really needed */ nwriters--; V(mutex); } } CS 105 18

  19. Readers/Writers with Semaphores (Polling continued) What are the drawbacks of this approach? How can we write a non-polling version? CS 105 19

  20. Readers/Writers with Monitors monitor readersandwriters; var readers: integer; someonewriting: boolean; readallowed, writeallowed: condition; procedure beginreading begin if someonewriting or queue(writeallowed) then wait(readallowed); readers := readers + 1; signal(readallowed); end; procedure donereading begin readers := readers 1; if readers = 0 then signal(writeallowed); end; CS 105 20

  21. Readers/Writers with Monitors (continued) procedure beginwriting begin if readers = 0 or someonewriting then wait(writeallowed); someonewriting := true; end; procedure donewriting begin someonewriting := false; if queue(readallowed) then signal(readallowed); else signal(writeallowed); end; begin readers := 0; someonewriting := false; end; CS 105 21

  22. Readers/Writers with Monitors Characteristics of solution No starvation Arriving readers wait if writer is waiting Group of readers runs after each writer Arrival order of writer, writer, reader runs in different order Requires several auxiliary variables CS 105 22

  23. Dining Philosophers Models many important synchronization problems Most famous concurrency problem Posed by Dijkstra Characteristics Five philosophers alternate thinking and eating Only food is spaghetti Requires two forks Each philosopher has assigned seat at round table One fork between each pair of plates Problem: control access to forks, such that everyone can eat Note that pick up left, then pick up right doesn t work (why?) Solvable with semaphores or monitors CS 105 23

  24. Drinking Philosophers Extension of dining philosophers, due to K.M. Chandy Arbitrary number of philosophers Each likes own drink, mixed from bottles on table Can only mix drink when holding all necessary bottles Each drink uses different subset of bottles Problem: control access to bottles, such that there is no deadlock and no starvation Solution uses Dining Philosophers as sub-problem. CS 105 24

Related


More Related Content