Dining Philosophers starvation problem using mutex locks

Question

The solution provided here for the dining philosopher problem states that: A philosopher must be allowed to pick up the chopsticks only if both the left and right chopsticks are available. I am using the following code for that solution. However, the only problem is that there is a possibility of starvation. What could be the most efficient solution to solve this issue?

main.c

/*Solution to dining philosophers using POSIX mutexes and condition varaibles.*/
 
#include <pthread.h>
#include <stdio.h>
#include "dp.h"
 
pthread_t tid[NUMBER];
 
/**
 * Initialize all relevant data structures and
 * synchronization objects.
 */
void init()
{
int i;
 
    for (i = 0; i < NUMBER; i++) {
        state[i] = THINKING;
        thread_id[i] = i;
        pthread_cond_init(&cond_vars[i],NULL);
    }
 
    pthread_mutex_init(&mutex_lock, NULL);
}
 
void create_philosophers()
{
int i;
 
    for (i = 0; i < NUMBER; i++) {
        pthread_create(&tid[i], 0, philosopher, (void *)&thread_id[i]);
    }
}
 
int main(void)
{
int i;
 
    init();
 
    create_philosophers();
 
    for (i = 0; i < NUMBER; i++)
        pthread_join(tid[i],NULL);
 
    return 0;
}

eating.c

/*simulate eating*/
 
#include <stdio.h>
 
void eating(int sleep_time) 
{
    //printf("eating for %d seconds\n",sleep_time);
    sleep(sleep_time);
}

philoshoher.c

/*General structure of a dining philosopher*/
 
#include <pthread.h>
#include <stdio.h>
#include <time.h>
#include "dp.h"
 
void *philosopher(void *param)
{
    int *lnumber = (int *)param;
    int number = *lnumber;
    int sleep_time;
    int times_through_loop = 0;
 
    srandom((unsigned)time(NULL));
 
    while (times_through_loop < 5) {
        sleep_time = (int)((random() % MAX_SLEEP_TIME) + 1);
        thinking(sleep_time);
 
        pickup_forks(number);
 
        printf("Philosopher %d is eating\n",number);
 
        sleep_time = (int)((random() % MAX_SLEEP_TIME) + 1);
        eating(sleep_time);
 
        printf("Philosopher %d is thinking\n",number);
        return_forks(number);
         
        ++times_through_loop;
    }
}

thinking.c

/*simulate thinking*/
 
#include <stdio.h>
 
void thinking(int sleep_time) 
{
    //printf("thinking for %d seconds",sleep_time);
    sleep(sleep_time);
}

dining.c

/*Solution to dining philosophers using POSIX mutexes and condition varaibles.*/
 
#include <pthread.h>
#include <stdio.h>
#include "dp.h"
 
/* return the left neighbor */
int left_neighbor(int number)
{
    if (number == 0)
        return NUMBER - 1;
    else
        return number - 1;
}
 
/* return the right neighbor */
int right_neighbor(int number)
{
    if (number == NUMBER - 1)
        return 0;
    else
        return number + 1;
}
 
void test(int i)
{
    /** 
     * Basic idea is this:
     * If I'm hungry, and my left and right neighbors aren't eating, then let me eat.
     */
    if ( (state[left_neighbor(i)] != EATING) && (state[i] == HUNGRY) && (state[right_neighbor(i)] != EATING) ) {
        state[i] = EATING;
        pthread_cond_signal(&cond_vars[i]);
    }
}
 
/* A philosopher calls this when it wants to pick up its forks./
 
void pickup_forks(int number)
{
    pthread_mutex_lock(&mutex_lock);
 
    state[number] = HUNGRY;
    test(number);
 
    while (state[number] != EATING) {
        pthread_cond_wait(&cond_vars[number], &mutex_lock);
    }
 
    pthread_mutex_unlock(&mutex_lock);
}
 
/* A philosopher calls this when it wants to return its forks./
 
void return_forks(int number)
{
    pthread_mutex_lock(&mutex_lock);
 
    state[number] = THINKING;
    test(left_neighbor(number));
    test(right_neighbor(number));
 
    pthread_mutex_unlock(&mutex_lock);
}

dp.h

/*Header file for dining philosophers*/
 
#include <pthread.h>
 
// the number of philosophers
#define NUMBER      5
 
// the maximum time (in seconds) to sleep
#define MAX_SLEEP_TIME  5
 
// different philosopher states
//#define THINKING      0
//#define HUNGRY            1
//#define EATING            2
 
// the state of each philosopher (THINKING, HUNGRY, EATING)
//int state[NUMBER];
enum {THINKING, HUNGRY, EATING} state[NUMBER];
 
// the thread id of each philosopher (0 .. NUMBER - 1)
int thread_id[NUMBER];
 
// condition variables and associated mutex lock
pthread_cond_t      cond_vars[NUMBER];
pthread_mutex_t     mutex_lock;
 
void *philosopher(void *param);

Makefile

# To run, enter
# make all
 
all: diningphilosophers
 
diningphilosophers: main.o dining.o eating.o thinking.o philosopher.o
    gcc -lpthread -o diningphilosophers main.o dining.o thinking.o eating.o philosopher.o
 
main.o: main.c dp.h
    gcc -lpthread -c main.c
 
dining.o: dining.c dp.h
    gcc -lpthread -c dining.c
 
philosopher.o: philosopher.c dp.h
    gcc -lpthread -c philosopher.c
 
eating.o: eating.c
    gcc -lpthread -c eating.c
 
thinking.o: thinking.c
    gcc -lpthread -c thinking.c

``