The Dining-Philosophers Problem

an Operating System Perspective

This could be an exercise on Application-Orientation, but indeed it's only an invitation for students to compare the implementation of Dijkstra's classic process coordination problem "The Dining-Philosophers" for some operating systems.

EPOS: Embedded Parallel Operating System

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50. 		#include <iostream>
#include <thread.h>
#include <synchronizer.h>

using namespace std;
using namespace System;

const int ITERATIONS = 100;

Semaphore chopstick[5];

int philosopher(int n)
{
    cout << "Philosopher " << n << " was born!\n";

    int first = (n < 4)? n : 0; // left for phil 0 .. 3, right for phil 4
    int second = (n < 4)? n + 1 : 4; // right for phil 0 .. 3, left for phil 4

    for(int i = 0; i < ITERATIONS; i++) {
        cout << "Philosopher " << n << " thinking ...\n";
        chopstick[first].p();   // get first chopstick
        chopstick[second].p();   // get second chopstick

        cout << "Philosopher " << n << " eating ...\n";
        chopstick[first].v();   // release first chopstick
        chopstick[second].v();   // release second chopstick
    }

    return n;
}

int main()
{
    cout << "The Dining-Philosophers Problem\n";

    Thread * phil[5];
    for(int i = 0; i < 5; i++)
        phil[i] = new Thread(&philosopher, i);

    int status;
    for(int i = 0; i < 5; i++) {
        phil[i]->join(&status);
        if(status == i)
            cout << "Philosopher " << i << " went to heaven!\n";
        else
            cout << "Philosopher " << i << " went to hell!\n";
    }

    return 0;
}

Line 8 creates five Semaphore objects, which are initialized by the default constructor to "1".

Lines 10-23 describe the philosophers' live: thinking and eating. In order to eat, each philosopher must take both nearby chopsticks. Philosophers 0 through 3 take first the chopstick to their left and then the one to their right. Philosopher 4 does do opposite, thus avoiding deadlocks.

Line 29 declares an array of pointers to Threads objects, each of which corresponds to a philosopher. Lines 30-31 create a thread for each philosopher, setting function philosopher as entry point and passing the creation order as argument.

UNIX System V IPC

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72. 		#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <sys/wait.h>
#include <sys/ipc.h>
#include <sys/sem.h>

const int ITERATIONS = 5;

int chopstick[5];

int philosopher(int n)
{
    int i, j, first, second;
    struct sembuf op;
    op.sem_num = 0;
    op.sem_flg = 0;

    printf("Philosopher %d was born!\n", n);

    first = (n < 4)? n : 0; /* left for phil 0 .. 3, right for phil 4 */
    second = (n < 4)? n + 1 : 4; /* right for phil 0 .. 3, left for phil 4 */

    for(i = 0; i < ITERATIONS; i++) {
        printf("Philosopher %d is thinking ...\n", n);
        /* get first chopstick */
        op.sem_op = -1; semop(chopstick[first], &op, 1);
        /* get second chopstick */
        op.sem_op = -1; semop(chopstick[second], &op, 1);

        printf("Philosopher %d is eating ...\n", n);
        /* release first chopstick */
        op.sem_op = +1; semop(chopstick[first], &op, 1);
        /* release second chopstick */
        op.sem_op = +1; semop(chopstick[second], &op, 1);
    }

    exit(n);
}

int main()
{
    int i, status;
    pid_t phil[5];

    printf("The Dining-Philosophers Problem\n");

    for(i = 0; i < 5; i++) {
        if((chopstick[i] = semget(IPC_PRIVATE, 1, IPC_CREAT | 0600)) < 0)
            return -1;
        if(semctl(chopstick[i], 0, SETVAL, 1) < 0)
            return -1;
    }

    for(i = 0; i < 5; i++)
        if((phil[i] = fork()) == 0) /* child */
            exit(philosopher(i));

    for(i = 0; i < 5; i++) {
        waitpid(phil[i], &status, 0);
        if(WEXITSTATUS(status) == i)
            printf("Philosopher %d went to heaven!\n", i);
        else
            printf("Philosopher %d went to hell!\n", i);
    }

    for(i = 0; i < 5; i++)
        semctl(chopstick[i], 0, IPC_RMID, 0);

    return 0;
}

POSIX Threads

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60. 		#include <unistd.h>
#include <stdio.h>
#include <pthread.h>
#include <signal.h>
#include <semaphore.h>

const int ITERATIONS = 5;

sem_t chopstick[5];

int philosopher(int n)
{
    int i, j, first, second;

    printf("Philosopher %d was born!\n", n);

    first = (n < 4)? n : 0; /* left for phil 0 .. 3, right for phil 4 */
    second = (n < 4)? n + 1 : 4; /* right for phil 0 .. 3, left for phil 4 */

    for(i = 0; i < ITERATIONS; i++) {
        printf("Philosopher %d is thinking ...\n", n);
        sem_wait(&chopstick[first]);  /* get first chopstick */
        sem_wait(&chopstick[second]); /* get second chopstick */

        printf("Philosopher %d is eating ...\n", n);
        sem_post(&chopstick[first]);  /* release first chopstick */
        sem_post(&chopstick[second]); /* release second chopstick */
    }

    pthread_exit((void *)n);
}

int main()
{
    int i, status;
    pthread_t phil[5];

    printf("The Dining-Philosophers Problem\n");

    for(i = 0; i < 5; i++)
        sem_init(&chopstick[i], 0, 1);

    for(i = 0; i < 5; i++)
        if(pthread_create(&phil[i], 0, (void*(*)(void*))philosopher,
                          (void *)i))
            return -1;

    for(i = 0; i < 5; i++) {
        pthread_join(phil[i], (void **)&status);
        if(status == i)
            printf("Philosopher %d went to heaven!\n", i);
        else
            printf("Philosopher %d went to hell!\n", i);
    }

    for(i = 0; i < 5; i++)
        sem_destroy(&chopstick[i]);

    return 0;
}