Understanding Classical Inter-Process Communication Problems
Classical Inter-Process Communication (IPC) problems such as the Dining Philosophers Problem and the Readers and Writers Problem are explored in-depth by Ali Akbar Mohammadi. The challenges, solutions, and non-solutions to these problems are discussed, shedding light on issues like starvation in concurrent programming. The content also presents a viable solution to the dining philosophers problem through the use of semaphores and proper synchronization mechanisms.
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
Classical IPC Problems Classical IPC Problems The Dining Philosophers Problem The Readers and Writers Problem Ali Akbar Mohammadi 2
The Dining Philosophers Problem The Dining Philosophers Problem Ali Akbar Mohammadi 3
Nonsolution Nonsolution to the Dining Philosophers Problem to the Dining Philosophers Problem #define N 5 void philosopher(int i) { while (TRUE) { } } think(); take_fork(i); take_fork((i+1) % N); eat(); put_fork(i); put_fork((i+1) % N); Ali Akbar Mohammadi 4
Starvation Starvation We could modify the program so that after taking the left fork, the program checks to see if the right fork is available. If it is not, the philosopher puts down the left one, waits for some time, and then repeats the whole process. This proposal too, fails, although for a different reason. With a little bit of bad luck, all the philosophers could start the algorithm simultaneously, picking up their left forks, seeing that their right forks were not available, putting down their left forks, waiting, picking up their left forks again simultaneously, and so on, forever. A situation like this, in which all the programs continue to run indefinitely but fail to make any progress is called starvation . Ali Akbar Mohammadi 5
A solution to the dining philosophers problem A solution to the dining philosophers problem #define N 5 #define LEFT (i+N-1)%N #define RIGHT (i+1)%N #define THINKING 0 #define HUNGRY 1 #define EATING 2 typedef int semaphore; int state[N]; semaphore mutex = 1; semaphore s[N]; Ali Akbar Mohammadi 6
A solution to the dining philosophers problem A solution to the dining philosophers problem void philosopher(int i) { while (TRUE) { } } think(); take_forks(i); eat(); put_forks(i); Ali Akbar Mohammadi 7
A solution to the dining philosophers problem A solution to the dining philosophers problem void take_forks(int i) { down(&mutex); state[i] = HUNGRY; test(i); up(&mutex); down(&s[i]); } Ali Akbar Mohammadi 8
A solution to the dining philosophers problem A solution to the dining philosophers problem void put_forks(i) { down(&mutex); state[i] = THINKING; test(LEFT); test(RIGHT); up(&mutex); } Ali Akbar Mohammadi 9
A solution to the dining philosophers problem A solution to the dining philosophers problem void test(i) { } if (state[i] == HUNGRY && state[LEFT] != EATING && state[RIGHT] != EATING) { state[i] = EATING; up(&s[i]); } Ali Akbar Mohammadi 10
The Readers and Writers Problem The Readers and Writers Problem The dining philosophers problem is useful for modeling processes that are competing for exclusive access to a limited number of resources, such as I/O devices. Another famous problem is the readers and writers problem which models access to a database. Imagine, for example, an airline reservation system, with many competing processes wishing to read and write it. It is acceptable to have multiple processes reading the database at the same time, but if one process is updating (writing) the database, no other process may have access to the database, not even a reader. The question is how do you program the readers and the writers? Ali Akbar Mohammadi 11
A solution to the readers and writers problem A solution to the readers and writers problem typedef int semaphore; semaphore mutex = 1; semaphore db = 1; int rc = 0; Ali Akbar Mohammadi 12
A solution to the readers and writers problem A solution to the readers and writers problem void reader(void) { while (TRUE) { down(&mutex); rc = rc + 1; if (rc == 1) down(&db); up(&mutex); read_data_base(); down(&mutex); rc = rc 1; if (rc == 0) up(&db); up(&mutex); use_data_read(); } } Ali Akbar Mohammadi 13
A solution to the readers and writers problem A solution to the readers and writers problem void writer(void) { while (TRUE) { } } think_up_data(); down(&db); write_data_base(); up(&db); Ali Akbar Mohammadi 14
A solution to the readers and writers problem A solution to the readers and writers problem In this solution, the first reader to get access to the data base does a down on the semaphore db . Subsequent readers merely have to increment a counter, rc . As readers leave, they decrement the counter and the last one out does an up on the semaphore, allowing a blocked writer, if there is one, to get in. Ali Akbar Mohammadi 15
