CS 105 Tour of the Black Holes of Computing Synchronization Methods Topics Mutual exclusion methods Producer consumer problem Readers writers problem semaphores ppt 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 Hardware Mutex Support Test and Set Read word set it nonzero and set condition codes All in one indivisible operation Compare and Swap 3 Read word compare to register store other 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 4 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 5 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 6 P s and V s must be matched Single extra V blows mutual exclusion entirely compare TSL 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 7 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 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 9 Can be done with just load store but tricky We have seen simple semaphore based solution Perfect application for monitors CS 105 Producer Consumer with Semaphores semaphore mutex 1 full 0 empty N void producer while 1 message nextItem produceItem P empty P mutex enterInBuffer nextItem V mutex V full 10 CS 105 Producer Consumer with Semaphores continued void consumer while 1 P full P mutex message nextItem removeFromBuffer V mutex V empty consumeItem nextItem 11 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 12 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 13 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 14 Shared access to file Multiple producers multiple consumers 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 pause P mutex nreaders V mutex read P mutex nreaders V mutex 15 CS 105 Readers Writers with Semaphores Polling continued void writer while 1 P mutex while nreaders nwriters 0 V mutex pause P mutex nwriters V mutex read P mutex nwriters V mutex 16 CS 105 Readers Writers with Semaphores Polling continued What are the drawbacks of this approach How can we write a non polling version 17 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 18 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 19 CS 105 Readers Writers with Monitors Characteristics of solution 20 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 Deadlock Consider following program semaphore a 1 b 1 void func1 P a P b do something V a V b void func2 P b P a do something else V b V a 21 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
View Full Document
Unlocking...