CS 105 Tour of the Black Holes of Computing Synchronization Methods Topics Mutual exclusion methods Producer consumer problem Readers writers problem Mutual Exclusion Need ways to enforce critical sections Prevent race conditions that cause errors Requirements for mutual exclusion Safety only one process 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 2 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 Additional Requirements Synchronization is tricky to get right Failure to protect critical sections Incorrect use of primitives Deadlock Programmer friendliness is big plus 3 CS 105 Hardware Mutex Support Test and Set Read word set it nonzero and set condition codes All in one indivisible operation Compare and Swap 4 Read word compare to register if match then store second register into word Again indivisible Generalization of Test Set CS 105 Example of Test and Set enter critical region leal lock eax L1 tsl eax Set lock NZ set CC jne L1 Loop if was already NZ We now have exclusive access ret leave critical region xor eax eax movl eax lock ret 5 CS 105 Evaluating Test and Set Very fast entry to unlocked region Easy to implement 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 starvation For these reasons test set is used only to implement higher level constructs 6 CS 105 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 7 P s and V s must be matched Single extra V blows mutual exclusion entirely compare Test Set CS 105 Monitors High level mutual exclusion construct Invented by C A R Tony Hoare 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 8 Programmers wind up standing on heads or implementing things like semaphores CS 105 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 9 CS 105 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 Solutions 10 Can be done with just load store but tricky We have seen simple semaphore based solution for oneelement buffer Perfect application for monitors CS 105 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 11 CS 105 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 12 CS 105 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 13 Shared access to file ATMs displaying or updating bank balance CS 105 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 14 CS 105 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 write P mutex nwriters V mutex 15 CS 105 Readers Writers with Semaphores Polling continued What are the drawbacks of this approach How can we write a non polling version 16 CS 105 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 17 CS 105 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 18 CS 105 Readers Writers with Monitors Characteristics of solution 19 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 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 20 Solvable with semaphores or monitors CS 105 Deadlock and Starvation Three
View Full Document
Unlocking...