Dining Philosophers without Deadlock

PublishedJanuary 10, 2024

I am Jyotiprakash, a deeply driven computer systems engineer, software developer, teacher, and philosopher. With a decade of professional experience, I have contributed to various cutting-edge software products in network security, mobile apps, and healthcare software at renowned companies like Oracle, Yahoo, and Epic. My academic journey has taken me to prestigious institutions such as the University of Wisconsin-Madison and BITS Pilani in India, where I consistently ranked among the top of my class.

At my core, I am a computer enthusiast with a profound interest in understanding the intricacies of computer programming. My skills are not limited to application programming in Java; I have also delved deeply into computer hardware, learning about various architectures, low-level assembly programming, Linux kernel implementation, and writing device drivers. The contributions of Linus Torvalds, Ken Thompson, and Dennis Ritchie—who revolutionized the computer industry—inspire me. I believe that real contributions to computer science are made by mastering all levels of abstraction and understanding systems inside out.

In addition to my professional pursuits, I am passionate about teaching and sharing knowledge. I have spent two years as a teaching assistant at UW Madison, where I taught complex concepts in operating systems, computer graphics, and data structures to both graduate and undergraduate students. Currently, I am an assistant professor at KIIT, Bhubaneswar, where I continue to teach computer science to undergraduate and graduate students. I am also working on writing a few free books on systems programming, as I believe in freely sharing knowledge to empower others.

Comments

Join the discussion

No comments yet. Be the first to comment.

More from this blog

Computer Arithmetic: From Fast Adders to Floating-Point

Arithmetic is the beating heart of every processor. Whether your machine is rendering 3-D graphics, training a neural network, or simply incrementing a loop counter, the ALU (Arithmetic Logic Unit) is doing the heavy lifting. In this deep-dive, I wan...

Feb 12, 202629 min read

The Complete Memory Hierarchy: From Semiconductor RAM to Virtual Memory

The performance gap between processors and main memory has been widening for decades. Modern processors can execute billions of instructions per second, but accessing data from main memory takes hundreds of processor cycles. This disparity creates a ...

Jan 7, 202670 min read

The Ultimate Spring Boot Guide: From Fundamentals to Production-Ready REST APIs

Introduction Welcome to the most comprehensive Spring Boot guide you'll find! This isn't just another tutorial that skims the surface. We're going to dive deep into every concept, explain every annotation, walk through every line of code, and underst...

Dec 26, 2025125 min read

Understanding Functions, Memory, and Pointers in C: A Complete Guide

Part 1: Functions and the Call Stack Before we can understand pointers and memory management in C, we need to understand how functions work and what happens behind the scenes when your program runs. This foundation will make everything else click int...

Dec 16, 202583 min read

Datapath and Control

The Basic Processing Unit is the brain of every computer. It fetches instructions from memory, decodes them, and executes the operations they specify. Whether you're running a simple addition or a complex algorithm, every operation flows through this...

Dec 10, 202534 min read

Jyotiprakash's Blog

251 posts

I'm Jyotiprakash, a software dev and professor at KIIT, with expertise in system programming.

The Dining Philosophers problem is a classic synchronization problem in computer science. It involves a number of philosophers seated around a table, alternating between thinking and eating. The challenge is to devise a strategy that allows all philosophers to eat without facing a deadlock (where everyone is waiting and no one can proceed).

Using monitors for solving the Dining Philosophers problem can avoid deadlocks that are common with semaphore-based solutions. Here's how a monitor-based solution can be structured:

Monitor Structure

Shared Resources: Each philosopher needs access to two forks (or chopsticks) to eat. These forks are the shared resources.
States: Each philosopher can be in one of three states: thinking, hungry (wants to eat but doesn’t have forks), or eating.
Synchronization: The monitor will control the access to forks to ensure that only one philosopher can try to pick them up or put them down at a time.

Monitor Implementation

monitor DiningPhilosophers
    enum State { THINKING, HUNGRY, EATING }
    State[] state = new State[5] // Assuming five philosophers
    condition[] self = new condition[5] // Condition variables for each philosopher

    initialize() {
        for i from 0 to 4:
            state[i] = THINKING
    }

    // Entry Procedure for a philosopher who wants to eat
    pickupForks(int i) {
        state[i] = HUNGRY
        test(i) // Try to acquire two forks
        if state[i] != EATING
            self[i].wait() // Block if forks not available

    // Exit Procedure for a philosopher who has finished eating
    putdownForks(int i) {
        state[i] = THINKING
        // Test left and right neighbors
        test((i + 4) % 5)
        test((i + 1) % 5)

    // Test if the i-th philosopher can eat
    test(int i) {
        if state[(i + 4) % 5] != EATING and state[i] == HUNGRY and state[(i + 1) % 5] != EATING:
            state[i] = EATING
            self[i].signal() // Wake up the hungry philosopher

end monitor

Explanation

Initialization: All philosophers start in the THINKING state.
Pick Up Forks: When a philosopher wishes to eat, they transition to the HUNGRY state and attempt to pick up the forks (by calling pickupForks). The test(i) function checks if the forks are available.
Test Function: This function checks if a philosopher can transition to the EATING state. A philosopher can eat if both the left and the right neighbors are not eating. If the conditions are met, the philosopher's state is set to EATING, and they are signaled to start eating.
Put Down Forks: After eating, a philosopher will put down the forks and return to the THINKING state. The putdownForks function then calls test on the left and right neighbors, potentially allowing them to start eating if they were waiting.
Avoiding Deadlock: This solution avoids deadlock by ensuring that a philosopher can only pick up both forks or none. If a philosopher picks up one fork but the other is unavailable, they will release the fork and wait. This approach ensures that there is no circular wait condition, effectively preventing deadlock.
Fairness: The use of condition variables ensures that no philosopher is starved. When a philosopher puts down their forks, they signal their neighbors, giving them a chance to eat if they were waiting.

This monitor-based solution ensures mutual exclusion, prevents deadlock, and avoids starvation, making it an effective approach for solving the Dining Philosophers problem.

Command Palette

Comments

More from this blog

Monitor Structure

Monitor Implementation

Explanation