CU-Boulder CSCI 3753 - Dining Philosophers, Monitors, and Condition Variables (88 pages)

Previewing pages 1, 2, 3, 4, 5, 6, 41, 42, 43, 44, 45, 46, 83, 84, 85, 86, 87, 88 of 88 page document View the full content.
View Full Document

Dining Philosophers, Monitors, and Condition Variables



Previewing pages 1, 2, 3, 4, 5, 6, 41, 42, 43, 44, 45, 46, 83, 84, 85, 86, 87, 88 of actual document.

View the full content.
View Full Document
View Full Document

Dining Philosophers, Monitors, and Condition Variables

85 views

Lecture Notes


Pages:
88
School:
University of Colorado at Boulder
Course:
Csci 3753 - Operating Systems

Unformatted text preview:

Dining Philosophers Monitors and Condition Variables CSCI 3753 Operating Systems Spring 2005 Prof Rick Han Announcements HW 3 is due Friday Feb 25 a week from now submitting graphic doc OK will post an answer extra office hours Thursday 1 pm post this TA finished regrading some HWs that were cut off by moodle Slides on synchronization online PA 2 is coming assigned around Tuesday night Midterm is tentatively Thursday March 10 Read chapters 9 and 10 From last time We discussed semaphores Deadlock Classic synchronization problems Bounded Buffer Producer Consumer Problem First Readers Writers Problem Dining Philosophers Problem Dining Philosophers Problem N philosophers seated around a circular table There is one chopstick between each philosopher A philosopher must pick up its two nearest chopsticks in order to eat A philosopher must pick up first one chopstick then the second one not both at once Devise an algorithm for allocating these limited resources chopsticks among several processes philosophers in a manner that is deadlock free and starvation free P2 P3 P1 P4 P5 Dining Philosophers Problem A simple algorithm for protecting access to chopsticks each chopstick is governed by a mutual exclusion semaphore that prevents any other philosopher from picking up the chopstick when it is already in use by another philosopher semaphore chopstick 5 initialized to 1 Each philosopher grabs a chopstick i by P chopstick i Each philosopher releases a chopstick i by V chopstick i Dining Philosophers Problem Pseudo code for Philosopher i while 1 obtain the two chopsticks to my immediate right and left P chopstick i P chopstick i 1 N eat release both chopsticks V chopstick i 1 N V chopstick i Guarantees that no two neighbors eat simultaneously i e a chopstick can only be used by one its two neighboring philosophers Dining Philosophers Problem Unfortunately the previous solution can result in deadlock each philosopher grabs its right chopstick first causes each semaphore s value to



View Full Document

Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view Dining Philosophers, Monitors, and Condition Variables and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Dining Philosophers, Monitors, and Condition Variables and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?