Dining Philosophers Problem and Mutual Exclusion Solutions Review
Lecture 15: Dining Philosophers
Problem
1
Review: Mutual Exclusion
Solutions
2
•
Software solution
–
Disabling interrupts
–
Strict alternation
–
Peterson’s solution
•
Hardware solution
–
TSL/XCHG
•
Semaphore
•
Conditional variables
•
POSIX standards
Review: Pthreads APIs for condition
variables
3
4
Review:
Using condition
variables
int thread1_done = 0;
pthread_cond_t cv;
pthread_mutex_t mutex;
Thread 1:
printf(“hello “);
pthread_mutex_lock(&mutex);
thread1_done = 1;
pthread_cond_signal(&cv);
pthread_mutex_unlock(&mutex);
Thread 2:
pthread_mutex_lock(&mutex);
while (thread1_done == 0) {pthread_cond_wait(&cv,
&mutex);
}
printf(“ world\n“);
pthread_mutex_unlock(&mutex);
5
Review: Deadlock
proc1( ) {pthread_mutex_lock(&m1);
/* use object 1 */
pthread_mutex_lock(&m2);
/* use objects 1 and 2 */
pthread_mutex_unlock(&m2);
pthread_mutex_unlock(&m1);
}
proc2( ) {pthread_mutex_lock(&m2);
/* use object 2 */
pthread_mutex_lock(&m1);
/* use objects 1 and 2 */
pthread_mutex_unlock(&m1);
pthread_mutex_unlock(&m2);
}
thread a
thread b
In this lecture
•
Dining Philosophers Problem
•
Readers-Writers Problem
6
7
Dining Philosophers
•
Classic Synchronization Problem
•
Philosopher
–
eat, think
–
eat, think
–
……..
•
Philosopher = Process
•
Eating needs two resources (chopsticks)
8
Problem: need
two chopsticks
to eat
9
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);
}
10
11
12
DEADLOCK
13
One Possible Solution
•
Use a mutex for the whole dinner-table
•
Philosopher i:
lock(table);
Eat();
Unlock(table);
Performance
problem!
14
Another Solution
Philosopher i:
Think();
unsuccessful = 1;
while (unsuccessful) {lock(left_chopstick);
if (try_lock(right_chopstick)) /* try_lock returns immediately if
unable to grab the lock */
unsuccessful = 0;
else
unlock(left_chopstick);
}
Eat();
unlock(left_chopstick);
unlock(right_chopstick);
Problem: starvation if
unfavorable scheduling!
15
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
16
Solution with Random Delays
Philosopher i:
Think();
while (unsuccessful) {wait(random());
lock(left_chopstick);
if (trylock(right_chopstick))
unsuccessful = 0;
else
unlock(left_chopstick);
}
Eat();
unlock(left_chopstick);
unlock(right_chopstick);
17
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
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
