Process synchronization ppt

problem syncing wii remote and synchronization in digital communication ppt
Dr.SamuelHunt Profile Pic
Dr.SamuelHunt,United Arab Emirates,Teacher
Published Date:21-07-2017
Your Website URL(Optional)
Comment
Classical Problems of Synchronization ● Bounded Buffer Problem ● Readers-Writers Problem ● Dining-Philosophers Problem 45 45Bounded Buffer Problem ● Shared data ● Shared data type item = ….; ● n buffers, each can hold one item var buffer: array0..n-1 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 next_produced / 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 next_consumed / ... ... 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 49Readers-Writers 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 50Readers-Writers Problem ● Shared Data ● Shared Data ● Data set var mutex, wrt: semaphore (=1); readcount: integer (= 0); ● Semaphore rw_mutex initialized to 1 ● Writer Process ● Semaphore mutex initialized to 1 wait(wrt); ● Integer read_count initialized to 0 … writing is performed ● The structure of a writer process ... do signal(wrt); wait(rw_mutex); ... / writing is performed / ... signal(rw_mutex); while (true); 51 51Readers-Writers Problem ● The structure of a reader process ● Reader process do wait(mutex); wait(mutex); readcount := readcount +1; read_count++; if readcount = 1 then wait(wrt); if (read_count == 1) signal(mutex); wait(rw_mutex); ... 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 (read_count == 0) signal(rw_mutex); signal(mutex); while (true); 52 52 Dining-Philosophers 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 odd-numbered philosopher picks eat up first the left chopstick and then the right chopstick. Even-numbered ... 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 high-level 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 monitor-name // 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 () ; initialization_code() 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