Dining Philosophers Problem and Mutual Exclusion Solutions Review
This lecture discusses the Dining Philosophers Problem, a classic synchronization issue in computer science. It covers various solutions for achieving mutual exclusion, including software-based solutions like Peterson's algorithm and hardware-based solutions like Test-and-Set (TSL/XCHG). Additionally, the lecture explores using condition variables in pthreads APIs and addresses the issue of deadlock in concurrent programming scenarios.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Lecture 15: Dining Philosophers Problem 1
Review: Mutual Exclusion Solutions Software solution Disabling interrupts Strict alternation Peterson s solution Hardware solution TSL/XCHG Semaphore Conditional variables POSIX standards 2
Review: Pthreads APIs for condition variables 3
Review: Using condition variables int thread1_done = 0; pthread_cond_t cv; pthread_mutex_t mutex; Thread 1: Thread 2: printf( hello ); pthread_mutex_lock(&mutex); pthread_mutex_lock(&mutex); thread1_done = 1; pthread_cond_signal(&cv); pthread_mutex_unlock(&mutex); while (thread1_done == 0) { pthread_cond_wait(&cv, &mutex); } printf( world\n ); pthread_mutex_unlock(&mutex); 4
Review: Deadlock proc1( ) { pthread_mutex_lock(&m1); /* use object 1 */ pthread_mutex_lock(&m2); proc2( ) { pthread_mutex_lock(&m2); /* use object 2 */ pthread_mutex_lock(&m1); /* use objects 1 and 2 */ /* use objects 1 and 2 */ pthread_mutex_unlock(&m2); pthread_mutex_unlock(&m1); } pthread_mutex_unlock(&m1); pthread_mutex_unlock(&m2); } thread a thread b 5
In this lecture Dining Philosophers Problem Readers-Writers Problem 6
Dining Philosophers Classic Synchronization Problem Philosopher eat, think eat, think .. Philosopher = Process Eating needs two resources (chopsticks) 7
Problem: need two chopsticks to eat 8
First Pass at a Solution One Mutex for each chopstick Philosopher i: while (1) { Think(); lock(Left_Chopstick); lock(Right_Chopstick); Eat(); } unlock(Left_Chopstick); unlock(Right_Chopstick); 9
DEADLOCK 12
One Possible Solution Use a mutex for the whole dinner-table Philosopher i: lock(table); Eat(); Unlock(table); Performance problem! 13
Another Solution Philosopher i: while (unsuccessful) { lock(left_chopstick); if (try_lock(right_chopstick)) /* try_lock returns immediately if unsuccessful = 0; else unlock(left_chopstick); } Think(); unsuccessful = 1; unable to grab the lock */ Problem: starvation if unfavorable scheduling! Eat(); unlock(left_chopstick); unlock(right_chopstick); 14
In Practice Starvation will probably not occur We can ensure this by adding randomization to the system: Add a random delay before retrying Unlikely that our random delays will be in sync too many times 15
Solution with Random Delays Philosopher i: while (unsuccessful) { wait(random()); Think(); lock(left_chopstick); if (trylock(right_chopstick)) unsuccessful = 0; else unlock(left_chopstick); } Eat(); unlock(left_chopstick); unlock(right_chopstick); 16
Solution without random delay Do not try to take forks one after another Don t have each fork protected by a different mutex Try to grab both forks at the same time 17
