The Dining Philosophers Problem and Solution

What is the Dining Philosophers' problem?

In the Dining Philosophers problem, we have a table where five philosophers are sitting, with a bowl of noodles in the center. Each philosopher has a plate and a fork, totaling five forks. The philosophers spend their time either eating or thinking—they don't do anything else or communicate with each other.
To eat, a philosopher needs to use two forks, one on each side. The issue arises if all five philosophers try to eat at the same time; they would need a total of 10 forks, but only 5 are available. This could lead to a deadlock, where no philosopher can proceed because each is waiting for a fork that another philosopher is holding.
To prevent this deadlock, we use semaphores. Each fork is treated as a binary semaphore. In this scenario, each philosopher represents a process, and the forks represent resources. By carefully managing the semaphores, we can avoid the deadlock and ensure that the philosophers can take turns eating.

The solution to the problem
  • Wait for the First Fork: When philosopher i wants to eat, they first call wait(fork[i]). This checks if the fork on their left (fork i) is available. If it is, they pick it up (acquire the fork).
  • Wait for the Second Fork: Next, they call wait(fork[(i+1)%5]). This checks if the fork on their right (fork [(i+1)%5]) is available. If it is, they pick it up.
  • Eat: Once both forks are acquired, the philosopher can eat.
  • Signal After Eating: After finishing their meal, the philosopher releases both forks by calling signal(fork[i]) and signal(fork[(i+1)%5]), making them available for other philosophers.

The issue with this solution is that if all philosophers pick up one fork at the same time, a deadlock situation will occur. Each philosopher will be stuck waiting for the second fork, leading to an infinite loop where no one can eat. 
  • Reduce the Number of Philosophers to 4: By allowing only 4 philosophers to sit at the table instead of 5, there will always be at least one fork available for a philosopher to pick up. This prevents a situation where all philosophers are waiting for the other fork, thus avoiding a deadlock.
  • Place Lock: The second solution is to place a lock on the process of picking up both forks simultaneously. This ensures that a philosopher can only proceed if both forks are available at the same time, preventing the deadlock situation where each philosopher is waiting indefinitely for the second fork.
  • Odd-even rule: an odd philosopher picks up his left fork then his right fork and the even philosopher picks up her right fork then her left fork.





Comments

Post a Comment

Popular posts from this blog

Indexed allocation

Image
  Indexed allocation is a file allocation method used by operating systems to manage how files are stored on disk. The core idea is simple but powerful: instead of storing a file in contiguous blocks or linking blocks one-by-one, the system uses a special index block that contains a list of all the disk block addresses where the file’s data is stored. This removes many limitations of earlier methods like contiguous and linked allocation. In indexed allocation, each file has its own index block . This index block acts like a table of contents. Every entry inside it points to a data block that belongs to that file. When a file is created, the OS allocates an index block and then fills it with pointers to the actual data blocks as the file grows. These data blocks can be located anywhere on the disk , so the file does not need contiguous space. This makes storage much more flexible and avoids external fragmentation. When the system needs to access a particular part of a file, it fir...
Read more

Thrashing

Image
Thrashing occurs in a computer system when the operating system spends a significant amount of time swapping pages in and out of memory, rather than executing actual processes. This typically happens when the system's memory is overcommitted, meaning there are too many processes competing for too little physical memory, leading to frequent page faults. How Memory is Used 1. Initial State: App1 is running, and its two pages are loaded into memory: Frame 1: App1, Page 1 Frame 2: App1, Page 2 Frame 3 and 4 are free. App3's pages are present in swap memory. 2. Switch to App2: Now, you switch to App2, which also requires 2 pages: Frame 3: App2, Page 1 Frame 4: App2, Page 2 Memory is now full with both App1 and App2’s pages. App3's pages are present in swap memory. 3. Switch to App3: You decide to switch to App3, which needs 2 pages as well. Since the memory is full, the system needs to make room: App1’s pages are moved to swap memory: Swap Memory: [App1, Page 1] [App1, Page 2] F...
Read more

Basics of paging

Image
Paging is a memory management scheme that eliminates the need for contiguous allocation of physical memory and thus helps in handling fragmentation. It involves breaking down memory into fixed-size blocks called pages and frames. The OS typically decides the page size when the system is configured or during the OS design phase. This page size is constant for the entire system and is determined based on considerations such as hardware architecture, efficiency, and the type of applications running. Common page sizes are 4 KB, 8 KB, or 16 KB. Here's a simple explanation with an example: Basic Concepts Page: A fixed-size block of logical memory (virtual memory) used by a process. Frame: A fixed-size block of physical memory (RAM) where a page is mapped. Page Table: A data structure used by the operating system to keep track of the mapping between pages and frames. The Page Table Base Register (PTBR) is a special register in the CPU that holds the starting address of the page table for ...
Read more