Synchronization problems

classical Synchronization problems

1. Classical synchronization problem Mrs.G.Chandraprabha,M. Sc .,M.Phil., Assistant Professor, Department of Information Technology, V.V.Vanniaperumal College for Women, Virudhunagar .

2. Classical Problems of Synchronization 2 Bounded-Bu ff er Problem Readers and Writers Problem Dining-Philosophers Problem

3. Bounded-Buffer Problem (Producer/Consumer Problem ) definition CS420: Operating Systems 3 The buffer pool has a maximum size, this problem is often called the  Bounded buffer problem . This problem is generalised in terms of the  Producer Consumer problem , where a  finite  buffer pool is used to exchange messages between producer and consumer processes. Solution to this problem is, creating two counting semaphores "full" and "empty" to keep track of the current number of full and empty buffers respectively. In this Producers mainly produces a product and consumers consume the product, but both can use of one of the containers each time. The main complexity of this problem is that we must have to maintain the count for both empty and full containers that are available.

4. Bounded-Buffer Problem (Producer/Consumer Problem) CS420: Operating Systems 4 In a generalized Bounded Buffer problem, N buffers, each can hold one data item Utilize three semaphores to control access to buffer between the producer and the consumer Semaphore mutex locks access to critical region of code where bu ff er is modified Initialized to the value 1 Semaphore full keeps track of how many items are actually in the bu ff er Initialized to the value Semaphore empty keeps track of how many available slots there are in the bu ff er Initialized to the value N

5. Bounded Buffer Problem (Cont.) CS420: Operating Systems 5 an item do { .... // produce .... // inited to N wait (empty); wait (mutex); .... buffer // add .... signal signal item to the (mutex); (full); } while (TRUE); inited to do { .... wait (full); // full wait (mutex); .... // remove item from buffer .... signal (mutex); signal (empty); .... // consume the item .... } while (TRUE); Producer Process Consumer Process

6. Dining-Philosophers Problem Definition CS420: Operating Systems 6 The dining philosopher's problem involves the allocation of limited resources to a group of processes in a deadlock-free and starvation-free manner. There are five philosophers sitting around a table, in which there are five chopsticks/forks kept beside them and a bowl of rice in the centre, When a philosopher wants to eat, he uses two chopsticks - one from their left and one from their right. When a philosopher wants to think, he keeps down both chopsticks at their original place.

7. Dining-Philosophers Problem CS420: Operating Systems 7 Five philosophers spend their lives thinking and eating while sitting at a round table around a bowl of rice A chopstick is placed between each philosopher Philosophers cannot interact with their neighbors Each philosopher will think and occasionally eat When ready to eat a philosopher will try to pick up 2 chopsticks (one at a time) so he can eat some rice A philosopher needs 2 chopsticks to eat When done eating a philosopher will put down each chopstick, one at a time How can the philosophers sit and eat together without anyone starving? Think of each chopstick as a semaphore

8. Dining-Philosophers Issues CS420: Operating Systems 8 Possible Solution?? - Instruct each philosopher to behave as follows: Think until the left chopstick is available; when it is pick it up Think until the right chopstick is available; when it is pick it up Eat some rice Put the left chopstick down Put the right chopstick down Go back to thinking