Strategy 1: Concurrency Limitation via Counting Semaphore

In the classic scenario with N philosophers and N chopsticks, a deadlock occurs if every philosopher picks up one chopstick and waits for the other. To prevent this, we can introduce a counting semaphore initialized to N-1. This ensures that at most N-1 philosophers can attempt to sit down concurrently. By limiting the number of competing processes, at least one philosopher will always have acces to two chopsticks, allowing them to eat and release resources.

#include <iostream>
#include <semaphore.h>
#include <unistd.h>
#include <sys/wait.h>
#include <fcntl.h>
#include <cstring>
#include <cerrno>

#define PHILOSOPHERS 5

using namespace std;

// Helper to create or open a semaphore
sem_t* create_semaphore(const char* name, unsigned int value) {
    sem_t* sem = sem_open(name, O_CREAT | O_EXCL, 0666, value);
    if (sem == SEM_FAILED) {
        if (errno == EEXIST) {
            sem_unlink(name);
            sem = sem_open(name, O_CREAT | O_EXCL, 0666, value);
        }
    }
    return sem;
}

int main() {
    int count = PHILOSOPHERS;
    pid_t pid;

    // Global limit: only N-1 philosophers can compete
    const char* limit_name = "/dining_limit";
    sem_t* limit_sem = create_semaphore(limit_name, count - 1);

    // Individual semaphores for each chopstick
    sem_t* chopsticks[PHILOSOPHERS];
    char chop_name[32];
    
    for (int i = 0; i < count; i++) {
        snprintf(chop_name, 32, "/chop_%d", i);
        chopsticks[i] = create_semaphore(chop_name, 1);
    }

    // Create philosopher processes
    for (int i = 0; i < count; i++) {
        pid = fork();
        if (pid == 0) {
            // Philosopher logic
            // 1. Acquire permission to sit
            sem_wait(limit_sem);

            // 2. Define chopstick indices
            int left_idx = i;
            int right_idx = (i + 1) % count;

            // 3. Pick up chopsticks
            sem_wait(chopsticks[left_idx]);
            sem_wait(chopsticks[right_idx]);

            // 4. Eat
            sleep(1);
            cout << "Philosopher " << i << " has finished eating." << endl;

            // 5. Put down chopsticks
            sem_post(chopsticks[right_idx]);
            sem_post(chopsticks[left_idx]);

            // 6. Stand up
            sem_post(limit_sem);

            if (sem_close(limit_sem) == -1) exit(1);
            if (sem_close(chopsticks[i]) == -1) exit(1);
            exit(0);
        }
        if (pid < 0) perror("fork failed");
    }

    // Wait for all children
    while (wait(NULL) > 0);
    cout << "All philosophers have dined." << endl;

    // Cleanup
    sem_close(limit_sem);
    sem_unlink(limit_name);
    for (int i = 0; i < count; i++) {
        snprintf(chop_name, 32, "/chop_%d", i);
        sem_close(chopsticks[i]);
        sem_unlink(chop_name);
    }

    return 0;
}

Strategy 2: Asymmetric Resoruce Acquisition

This approach avoids deadlock by breaking the cycle of resource requests. We establish a rule based on the philosopher's ID. Philosophers with even indices pick up their left chopstick first, followed by the right. Conversely, philosophers with odd indices pick up their right chopstick first, then the left. This asymmetry prevents the formation of a circular wait chain.

#include <iostream>
#include <semaphore.h>
#include <unistd.h>
#include <sys/wait.h>
#include <fcntl.h>
#include <cstring>
#include <cerrno>

#define PHILOSOPHERS 5

using namespace std;

sem_t* create_semaphore(const char* name, unsigned int value) {
    sem_t* sem = sem_open(name, O_CREAT | O_EXCL, 0666, value);
    if (sem == SEM_FAILED) {
        if (errno == EEXIST) {
            sem_unlink(name);
            sem = sem_open(name, O_CREAT | O_EXCL, 0666, value);
        }
    }
    return sem;
}

int main() {
    int count = PHILOSOPHERS;
    pid_t pid;
    char chop_name[32];
    sem_t* chopsticks[PHILOSOPHERS];

    for (int i = 0; i < count; i++) {
        snprintf(chop_name, 32, "/res_%d", i);
        chopsticks[i] = create_semaphore(chop_name, 1);
    }

    for (int i = 0; i < count; i++) {
        pid = fork();
        if (pid == 0) {
            int left_idx = i;
            int right_idx = (i + 1) % count;

            // Asymmetric pickup logic
            if (i % 2 == 0) {
                // Even: Left first, then Right
                sem_wait(chopsticks[left_idx]);
                sem_wait(chopsticks[right_idx]);
            } else {
                // Odd: Right first, then Left
                sem_wait(chopsticks[right_idx]);
                sem_wait(chopsticks[left_idx]);
            }

            // Critical section: Eating
            sleep(1);
            cout << "Philosopher " << i << " completed meal." << endl;

            // Release resources
            sem_post(chopsticks[left_idx]);
            sem_post(chopsticks[right_idx]);

            if (sem_close(chopsticks[i]) == -1) exit(1);
            exit(0);
        }
        if (pid < 0) perror("fork failed");
    }

    while (wait(NULL) > 0);
    cout << "Dining session concluded." << endl;

    for (int i = 0; i < count; i++) {
        snprintf(chop_name, 32, "/res_%d", i);
        sem_close(chopsticks[i]);
        sem_unlink(chop_name);
    }

    return 0;
}

Strategy 3: Monitored Critical Section

In this solution, the entire operation of acquiring both chopsticks is treated as a single atomic transaction using a global mutex (binary semaphore). While this guarantees that a philosopher will never hold one fork while waiting indefinitely for the other (preventing deadlock), it significantly reduces parallelism since only one philosopher can be in the process of picking up forks at any given moment.

#include <iostream>
#include <semaphore.h>
#include <unistd.h>
#include <sys/wait.h>
#include <fcntl.h>
#include <cstring>
#include <cerrno>

#define PHILOSOPHERS 5

using namespace std;

sem_t* create_semaphore(const char* name, unsigned int value) {
    sem_t* sem = sem_open(name, O_CREAT | O_EXCL, 0666, value);
    if (sem == SEM_FAILED) {
        if (errno == EEXIST) {
            sem_unlink(name);
            sem = sem_open(name, O_CREAT | O_EXCL, 0666, value);
        }
    }
    return sem;
}

int main() {
    int count = PHILOSOPHERS;
    pid_t pid;
    char chop_name[32];

    // Mutex for the pickup action itself
    const char* mutex_name = "/pickup_mutex";
    sem_t* pickup_mutex = create_semaphore(mutex_name, 1);

    // Semaphores for individual chopsticks
    sem_t* chopsticks[PHILOSOPHERS];
    for (int i = 0; i < count; i++) {
        snprintf(chop_name, 32, "/fork_%d", i);
        chopsticks[i] = create_semaphore(chop_name, 1);
    }

    for (int i = 0; i < count; i++) {
        pid = fork();
        if (pid == 0) {
            // Lock the entire pickup sequence
            sem_wait(pickup_mutex);

            int left_idx = i;
            int right_idx = (i + 1) % count;

            // Now safe to acquire both
            sem_wait(chopsticks[left_idx]);
            sem_wait(chopsticks[right_idx]);

            // Unlock the pickup sequence so others can try
            sem_post(pickup_mutex);

            // Eat
            sleep(1);
            cout << "Philosopher " << i << " finished dining." << endl;

            // Release chopsticks
            sem_post(chopsticks[left_idx]);
            sem_post(chopsticks[right_idx]);

            if (sem_close(pickup_mutex) == -1) exit(1);
            if (sem_close(chopsticks[i]) == -1) exit(1);
            exit(0);
        }
        if (pid < 0) perror("fork failed");
    }

    while (wait(NULL) > 0);
    cout << "All processes terminated." << endl;

    // Resource cleanup
    sem_close(pickup_mutex);
    sem_unlink(mutex_name);
    for (int i = 0; i < count; i++) {
        snprintf(chop_name, 32, "/fork_%d", i);
        sem_close(chopsticks[i]);
        sem_unlink(chop_name);
    }

    return 0;
}