Question? Leave a message!




Classical Problems of Synchronization

Classical Problems of Synchronization
Classical Problems of Synchronization ● Bounded Buffer Problem ● ReadersWriters Problem ● DiningPhilosophers Problem 45 45Bounded Buffer Problem ● Shared data ● Shared data type item = ….; ● n buffers, each can hold one item var buffer: array0..n1 of item; ● Semaphore mutex initialized to the value 1 full, empty, mutex : semaphore; ● Semaphore full initialized to the value 0 nextp, nextc :item; full := 0; empty := n; mutex := 1; ● Semaphore empty initialized to the value n 46 46Bounded Buffer Problem ● Producer process creates filled buffers ● Producer process creates filled buffers do repeat … ... / produce an item in nextproduced / produce an item in nextp ... … wait(empty); wait (empty); wait (mutex); wait(mutex); … ... / add next produced to the buffer / add nextp to buffer … ... signal (mutex); signal(mutex); signal (full); signal(full); until false; while (true); 47 47Bounded Buffer Problem ● Consumer process Empties filled buffers ● Consumer process Empties filled buffers do repeat wait (full ); wait(full); wait (mutex); wait(mutex); … ... remove an item from buffer to nextc / remove an item from buffer to nextconsumed / ... ... signal (mutex); signal(mutex); signal (empty); signal(empty); … consume the next item in nextc ... … / consume the item in next consumed / until false; ... while (true); 48 48Discussion ● ASymmetry ● Producer does: P(empty), V(full) ● Consumer does: P(full), V(empty) ● Is order of P’s important ● Yes Can cause deadlock ● Is order of V’s important ● No, except that it might affect scheduling efficiency 49 49ReadersWriters Problem W R R R ● Motivation: Consider a shared database ● Two classes of users: ● Readers – never modify database ● Writers – read and modify database ● Is using a single lock on the whole database sufficient ● Like to have many readers at the same time ● Only one writer at a time 50ReadersWriters Problem ● Shared Data ● Shared Data ● Data set var mutex, wrt: semaphore (=1); readcount: integer (= 0); ● Semaphore rwmutex initialized to 1 ● Writer Process ● Semaphore mutex initialized to 1 wait(wrt); ● Integer readcount initialized to 0 … writing is performed ● The structure of a writer process ... do signal(wrt); wait(rwmutex); ... / writing is performed / ... signal(rwmutex); while (true); 51 51ReadersWriters Problem ● The structure of a reader process ● Reader process do wait(mutex); wait(mutex); readcount := readcount +1; readcount++; if readcount = 1 then wait(wrt); if (readcount == 1) signal(mutex); wait(rwmutex); ... signal(mutex); reading is performed ... ... / reading is performed / wait(mutex); readcount := readcount 1; ... if readcount = 0 then signal(wrt); wait(mutex); signal(mutex); read count; if (readcount == 0) signal(rwmutex); signal(mutex); while (true); 52 52 DiningPhilosophers Problem ● Philosophers spend their lives alternating thinking and eating ● Don’t interact with their neighbors, occasionally try to pick up 2 chopsticks (one at a time) to eat from bowl ● Need both to eat, then release both when done ● In the case of 5 philosophers ● Shared data Bowl of rice (data set) Semaphore chopstick 5 initialized to 1 53Dining Philosophers Problem ● The structure of Philosopher i: ● Philosopher i : do repeat wait (chopsticki ); wait (chopsticki); wait (chopsticki+1 mod 5); wait (chopStick (i + 1) 5 ); … eat // eat ... signal (chopsticki); signal (chopsticki ); signal (chopsticki+1 mod 5); signal (chopstick (i + 1) 5 ); … think // think … until false; while (TRUE); ● What is the problem with this algorithm 54 54Dining Philosophers Problem ● Deadlock handling ● Philosopher i : repeat ● Allow at most 4 philosophers to be sitting simultaneously at the table. wait (chopsticki); ● Allow a philosopher to pick up the forks only if both are available wait (chopsticki+1 mod 5); (picking must be done in a critical section. … ● Use an asymmetric solution an oddnumbered philosopher picks eat up first the left chopstick and then the right chopstick. Evennumbered ... philosopher picks up first the right chopstick and then the left signal (chopsticki); chopstick. signal (chopsticki+1 mod 5); … think … until false; 55 55Problems with Semaphores ● Incorrect use of semaphore operations: ● signal (mutex) …. wait (mutex) ● wait (mutex) … wait (mutex) ● Omitting of wait (mutex) or signal (mutex) (or both) ● Deadlock and starvation are possible. Monitors ● A highlevel abstraction that provides a convenient and effective mechanism for process synchronization ● Abstract data type, internal variables only accessible by code within the procedure ● Only one process may be active within the monitor at a time ● But not powerful enough to model some synchronization schemes monitor monitorname // shared variable declarations procedure P1 (…) …. procedure Pn (…) …… Initialization code (…) … Schematic view of a MonitorCondition Variables ● condition x, y; ● Two operations are allowed on a condition variable: ● x.wait() – a process that invokes the operation is suspended until x.signal() ● x.signal() – resumes one of processes (if any) that invoked x.wait() If no x.wait() on the variable, then it has no effect on the variable Monitor with Condition VariablesCondition Variables Choices ● If process P invokes x.signal(), and process Q is suspended in x.wait(), what should happen next ● Both Q and P cannot execute in parallel. If Q is resumed, then P must wait ● Options include ● Signal and wait – P waits until Q either leaves the monitor or it waits for another condition ● Signal and continue – Q waits until P either leaves the monitor or it waits for another condition ● Both have pros and cons – language implementer can decide Monitor Solution to Dining Philosophers monitor DiningPhilosophers enum THINKING; HUNGRY, EATING) state 5 ; condition self 5; void pickup (int i) statei = HUNGRY; test(i); if (statei = EATING) selfi.wait; void putdown (int i) statei = THINKING; // test left and right neighbors test((i + 4) 5); test((i + 1) 5); Solution to Dining Philosophers (Cont.) void test (int i) if ((state(i + 4) 5 = EATING) (statei == HUNGRY) (state(i + 1) 5 = EATING) ) statei = EATING ; selfi.signal () ; initializationcode() for (int i = 0; i 5; i++) statei = THINKING; Solution to Dining Philosophers (Cont.) ● Each philosopher i invokes the operations pickup() and putdown() in the following sequence: DiningPhilosophers.pickup(i); EAT DiningPhilosophers.putdown(i); ● No deadlock, but starvation is possible Monitor Implementation Using Semaphores ● Variables semaphore mutex; // (initially = 1) semaphore next; // (initially = 0) int nextcount = 0; ● Each procedure F will be replaced by wait(mutex); … body of F; … if (nextcount 0) signal(next) else signal(mutex); ● Mutual exclusion within a monitor is ensuredMonitor Implementation – Condition Variables ● For each condition variable x, we have: semaphore xsem; // (initially = 0) int xcount = 0; ● The operation x.wait can be implemented as: xcount++; if (nextcount 0) signal(next); else signal(mutex); wait(xsem); xcount; Monitor Implementation (Cont.) ● The operation x.signal can be implemented as: if (xcount 0) nextcount++; signal(xsem); wait(next); nextcount;
Website URL
Comment