dining philosophers problem using montiors

term presentation on operating systems. monitors and solution of dining philosophers using monitors

1. OPERATING SYSTEMS Presented to: Miss Najaf Khan 1

2. Presented By: 2

3. The Dining-Philosophers Problem 3

4. The Dining Philosophers Five Philosophers live in a house, where a table is laid for them. The life of each philosopher consists principally of thinking and eating. Through years of thought, all of the philosophers had agreed that the only food that contributed to their thinking is Spaghetti. Eating Spaghetti ( in most proper manner ) requires that a philosopher use both adjacent forks (simultaneously ). 4

5. The Dining Philosophers 5

6. Dining Philosopher Behavior v oid typicalPhilosopher () { while ( true ) { think(); Eat(); } // end while } // end typicalPhilosopher 6

7. Implementation of Method eat v oid Eat() { pickUpLeftFork (); pickUpRightFork (); eatForSomeTime (); putDownRightFork (); putDownLeftFork (); } // Eat 7

8. Starvation and Deadlock Starvation “A Condition in Which Process is Indefinitely Delayed Because Other Processes are always given preference.” D eadlock “Situation in Which a Process or Thread is Waiting for an Event that will Never O ccur .” 8 In this Problem, Philosophers operate asynchronously and concurrently, it is possible for each philosopher might pick up L eft Fork before any philosopher pick up R ight F ork . In this case, each Philosopher will hold exactly one fork, and no forks will remain available on the table. The philosophers will all deadlock and starve.

9. breaking Deadlock When each philosopher holds a fork a Left Fork is to force one or more philosophers to put their left fork down so that another philosopher may grab it as Right Fork . To implement this rule, pickUpRightFork () can specify that a philosopher puts down the left fork if that philosopher cannot obtain the right fork. However, in this case, it is possible that each philosopher will pick up and put down its left fork for repeatedly in tandem without ever obtaining the two forks it needs to eat spaghetti. In this case, the philosophers are not deadlocked, suffering from indefinite postponement , and they will still starve. 9

10. 10

11. Monitors 11

12. What is a Monitor? A monitor is a software module consisting of one or more procedures, an initialization sequence, and local data. The chief characteristics of monitor are: 12

13. Monitors provides Mutual Exclusion By enforcing the discipline of one process at a time, the monitor is able to provide a mutual exclusion facility. The data variables in a monitor can be accessed by only one process at a time. A shared data structure can be protected by placing it in a monitor. If the data in a monitor is representing some resource, then the monitor provides a mutual exclusion facility for accessing the resource. Mutual Exclusion: “A Condition in Which there is a set of Processes, only one of Which is able to access a given Resource or Perform a given function at any time.” 13

14. Synchronization Achieved by the use of condition variables that are contained within the monitor and accessible only within the monitor Condition variables are operated on by two functions: cwait (c): suspend execution of the calling process on condition c csignal (c): resume execution of some process blocked after a cwait on the same condition 14

15. Structure of a Monitor 15

16. Dining- Philosophers Solution Using Monitors 16

17. 17 Monitor dining_controller ; Cond forkReady [5]; /*condition variable for synchronization */ Boolean fork[5] = { true }; /*availability of each fork */ Void get_forks ( int pid ) { int left= pid ; int right = (++ pid ) % 5; /* grant the left fork */ if ( !fork(left) cwait ( ForkReady [left]); /* queue on condition variable */ fork(left) = false; /* grants the right fork */ if ( !fork(right) cwait ( ForkReady [right]); /* queue on condition variable */ fork(right) = false; }

18. 18 void release_forks ( int pid ) { int left = pid ; int right = (++ pid ) % 5 ; /* release the empty fork */ if ( empty( ForkReady [left] ) /* no one is waiting for this fork */ fork[left0 = true ; else /* awaken a process waiting for this fork */ csignal { ForkReady {left]); /* release the right fork */ if ( empty{ ForkReady [right]) /* no one is waiting for this fork */ fork(right) = true; else /* awaken a process waiting for this fork */ csignal ( ForkReady [right] ); }

19. 19 v oid philosopher[k=0 to 4 ] /* the philosopher clients */ { while( true ) { <think>; get_forks (k); /* client requests two forks via monitor */ <eat spaghetti>; release_forks (k); /* client releases forks via the monitor */ } }

20. References 20

21. 21