Dining philosophers problem with mutexes

Question

I know this dining philosophers problem has been researched a lot and there are resources everywhere. But I wrote simple code to solve this problem with C and then turned to the Internet to see if it's correct. I wrote this with mutexes only and almost all implementations on the Internet use a semaphore. Now I'm not sure about my code.

#include <stdio.h> 
#include <pthread.h>
#include <stdlib.h>
#include <unistd.h>

#define NO_OF_PHILOSOPHERS 5

pthread_t philosophers[NO_OF_PHILOSOPHERS];
pthread_mutex_t mutex_forks = PTHREAD_MUTEX_INITIALIZER;; 
int forks[NO_OF_PHILOSOPHERS];

void init()
{
    int i;
    for(i=0; i<NO_OF_PHILOSOPHERS; i++)
        forks[i] = 0;
}

void philosopher(int i)
{
    int right = i;
    int left = (i - 1 == -1) ? NO_OF_PHILOSOPHERS - 1 : (i - 1);
        int locked;
    while(1)
    {
            locked = 0;
            while(!locked)
            {
                pthread_mutex_lock(&mutex_forks);
                if(forks[right] || forks[left])
                {
                    pthread_mutex_unlock(&mutex_forks);     // give up the forks unless you can take both at once.
                    printf("Philosopher %d cannot take forks. Giving up and thinking.\n",i); 
                    usleep(random() % 1000); // think. 
                    continue;
                }
                forks[right] = 1; // take forks.
                forks[left] = 1;

                pthread_mutex_unlock(&mutex_forks);
                locked = 1; 
            }

        printf("Philosopher %d took both forks. Now eating :)\n",i);
        usleep(random() % 500);
        printf("Philosopher %d done with eating. Giving up forks.\n",i);
        pthread_mutex_lock(&mutex_forks); // give up forks. 
        forks[right] = 0;
        forks[left] = 0;
        pthread_mutex_unlock(&mutex_forks);
        usleep(random() % 1000);
    }

}

int main()
{
    init();
    int i;
    for(i=0; i<NO_OF_PHILOSOPHERS; i++)
        pthread_create( &philosophers[i], NULL, philosopher, (void*)i);
    for(i=0; i<NO_OF_PHILOSOPHERS; i++)
        pthread_join(philosophers[i],NULL);
    return 0;
} 

Now for me, the code looks like it's working fine, but people on the Internet seem to make a lot of fuss than this to write the solution for Dining Philosophers.

As such, I thought of asking these questions:

1. Can there be a deadlock in the code?
2. Can there be a starvation of a philosopher?
3. Have I missed the whole point of the Dining Philosophers Problem?

Answer 1

In the problem as I have seen it, the philosophers only take one fork at a time and can hang on to it (but they only eat when they have 2 forks). You have simplified it by having them take both or none.

There shouldn't be any deadlocks as the philosopher only has 0 or 2 forks, but there is still potential for starvation if the 2 neighbouring philosophers start eating again before the philosopher has finished thinking.

Answer 2

You should also be careful of the thread-start pattern. If you start them in a loop and they immediately reach for a fork before the other philosophers are initialized the sequencing trivializes the problem. That said, it is as much a thought experiment as an actual implementation challenge, intended to force you to think about how to deterministically break the behavior for all the philosophers without them having different code.

Answer 3

Or have I missed the whole point of dining philosophers problem?

Yes, sort of. The solution with a single global lock protecting all manipulation with forks is trivial and overly restrictive: essentially, the whole table is locked just to check if there are two free forks nearby. As the result, no two philosophers can even try to take or return forks at the same time, even if they do not share forks. Enforcing such a restriction to real people eating at a round table would be unrealistic, especially if the number of philosophers is not as small as 5 :)