I have an assignment about deadlocks for a Dining Philosophers program. I am asked to make a file called "sections1.c" that has a deadlock issue and after completing creating a deadlock, I am to copy the code and solve the deadlock condition in a file "sections2.c". My teacher is having us program with MDAT. The MDAT should run just like semaphores and pthread functions as he gave us this on the MDAT guide.
void mdat_mutex_init(const char *name, pthread_mutex_t *lock,
pthread_mutexattr_t *attr);
void mdat_mutex_lock(pthread_mutex_t *lp);
void mdat_mutex_unlock(pthread_mutex_t *lp);
void mdat_sem_init(const char *name, sem_t *sem, int pshared, int value);
void mdat_sem_wait(sem_t *sp);
void mdat_sem_post(sem_t *sp);
The MDAT supposedly takes responsibility of the scheduler and schedules the treads randomly by seeding the current time when run.
In the main file, which I am not allowed to edit, the function sectionInitGlobals runs once and sectionRunPhilosopher runs once with each pthread_create.
A problem could be that I have never used semaphores before, and am using them incorrectly.
// sections1.c: mutual exclusion model sections
#include <stdio.h>
#include <errno.h>
#include <stdlib.h>
#include <pthread.h>
#include <semaphore.h>
#include "sections.h"
#include "mdat.h"
// TODO: Declare shared variables here
int numPhils;
sem_t * sem_arr;
void sectionInitGlobals(int numPhilosophers)
{
// TODO: Complete this function
int i;
char char_arr[50];
sem_t arr[numPhilosophers];
numPhils = numPhilosophers;
for(i = 0; i < numPhilosophers; i++)
{
sprintf(char_arr,"%d", i);
mdat_sem_init(char_arr, &arr[i], 0, 0);
}
sem_arr = arr;
}
void sectionRunPhilosopher(int philosopherID, int numRounds)
{
int lChopstick = philosopherID;
int rChopstick;
int left;
int right;
int i;
int hasEaten;
int hasLeft;
int hasRight;
if(philosopherID == 0)
rChopstick = numPhils - 1;
else
rChopstick = philosopherID - 1;
for(i = 0; i < numRounds; i++)
{
hasEaten = 0;
hasLeft = 0;
hasRight = 0;
while(hasEaten == 0)
{
sem_getvalue(&sem_arr[lChopstick], &left);
if(left >= 0 || hasLeft == 1)
{
hasLeft = 1;
}
else
{
mdat_sem_wait(&sem_arr[lChopstick]);
}
sem_getvalue(&sem_arr[rChopstick], &right);
if(right >= 0 && hasLeft != 0)
{
hasRight = 1;
}
else
{
mdat_sem_wait(&sem_arr[rChopstick]);
}
if(hasLeft != 0 && hasRight != 0)
{
eat();
hasEaten = 1;
mdat_sem_post(&sem_arr[lChopstick]);
mdat_sem_post(&sem_arr[rChopstick]);
}
}
think();
}
}
When testing my code I get to run it with any number of threads and rounds that I want, however, it seems that with more threads the deadlock is guaranteed. When I run the code with 100 threads it reaches a deadlock every time, but with more threads shouldn't it have a less chance of reaching a deadlock?
Results:
With 16 threads and 10 rounds, the deadlock sometimes depending on the scheduler.
With 6 threads and 5 rounds, the deadlock occurs 0% of the time.
With 100 threads and 5 rounds, the deadlock occurs 100% of the time.
Edit:
End of trace files when no deadlock occurs and when program thinks deadlock occurs:
No Deadlock:
THREAD: 3
SECTION: DoneRounds
MESSAGE: Thread 3 has completed
*******************************************************************************
|ID |PROPERTY |LOC |SECTION |STATUS |WAITING ON |
|0 |0 |19 | |completed | |
|1 |1 |19 | |completed | |
|2 |2 |19 | |completed | |
|3 |3 |19 | |completed | |
|4 |4 |19 | |completed | |
|5 |5 |19 | |completed | |
|6 |6 |19 | |completed | |
|7 |7 |19 | |completed | |
|8 |8 |19 | |completed | |
|9 |9 |19 | |completed | |
|10 |10 |19 | |completed | |
|11 |11 |19 | |completed | |
|12 |12 |19 | |completed | |
|13 |13 |19 | |completed | |
|14 |14 |19 | |completed | |
|15 |15 |19 | |completed | |
-------------------------------------------------------------------------------
|LOCK NAME |STATUS |WAITING THREADS |
|lock_a |unlocked | |
|lock_b |unlocked | |
-------------------------------------------------------------------------------
|SEMAPHORE NAME |VALUE |WAITING THREADS |
|0 |20 | |
|1 |20 | |
|2 |20 | |
|3 |20 | |
|4 |20 | |
|5 |20 | |
|6 |20 | |
|7 |20 | |
|8 |20 | |
|9 |20 | |
|10 |20 | |
|11 |20 | |
|12 |20 | |
|13 |20 | |
|14 |20 | |
|15 |20 | |
*******************************************************************************
***** Program Trace End *****
Deadlock:
THREAD: 13
SECTION: DoneRounds
MESSAGE: Thread 13 has completed
*******************************************************************************
|ID |PROPERTY |LOC |SECTION |STATUS |WAITING ON |
|0 |0 |19 | |completed | |
|1 |1 |32 | |waiting-sem |1 |
|2 |2 |32 | |waiting-sem |2 |
|3 |3 |38 | |waiting-sem |2 |
|4 |4 |19 | |completed | |
|5 |5 |19 | |completed | |
|6 |6 |19 | |completed | |
|7 |7 |19 | |completed | |
|8 |8 |19 | |completed | |
|9 |9 |32 | |waiting-sem |9 |
|10 |10 |38 | |waiting-sem |9 |
|11 |11 |19 | |completed | |
|12 |12 |19 | |completed | |
|13 |13 |19 | |completed | |
|14 |14 |19 | |completed | |
|15 |15 |19 | |completed | |
-------------------------------------------------------------------------------
|LOCK NAME |STATUS |WAITING THREADS |
|lock_a |unlocked | |
|lock_b |unlocked | |
-------------------------------------------------------------------------------
|SEMAPHORE NAME |VALUE |WAITING THREADS |
|0 |10 | |
|1 |-1 |1 |
|2 |-2 |2 3 |
|3 |10 | |
|4 |20 | |
|5 |20 | |
|6 |20 | |
|7 |20 | |
|8 |10 | |
|9 |-2 |9 10 |
|10 |10 | |
|11 |20 | |
|12 |20 | |
|13 |20 | |
|14 |20 | |
|15 |20 | |
*******************************************************************************
ERROR! VIOLATION: No ready threads to schedule - possible DEADLOCK
***** Program Trace End *****
Thanks to mevets! Final Code: section1.c - Want deadlock
// sections1.c: mutual exclusion model sections
#include <stdio.h>
#include <errno.h>
#include <stdlib.h>
#include <pthread.h>
#include <semaphore.h>
#include "sections.h"
#include "mdat.h"
// TODO: Declare shared variables here
int numPhils;
sem_t * sem_arr;
void sectionInitGlobals(int numPhilosophers)
{
// TODO: Complete this function
int i;
char char_arr[50];
sem_t arr[numPhilosophers];
numPhils = numPhilosophers;
for(i = 0; i < numPhilosophers; i++)
{
sprintf(char_arr,"%d", i);
mdat_sem_init(char_arr, &arr[i], 0, 1);
}
sem_arr = arr;
}
void sectionRunPhilosopher(int philosopherID, int numRounds)
{
int lChop = philosopherID;
int rChop;
int i;
if(philosopherID == 0)
rChop = numPhils - 1;
else
rChop = philosopherID - 1;
for(i = 0; i < numRounds; i++)
{
mdat_sem_wait(&sem_arr[lChop]);
mdat_sem_wait(&sem_arr[rChop]);
eat();
mdat_sem_post(&sem_arr[rChop]);
mdat_sem_post(&sem_arr[lChop]);
think();
}
}
section2.c - Do NOT want deadlock
// sections1.c: mutual exclusion model sections
#include <stdio.h>
#include <errno.h>
#include <stdlib.h>
#include <pthread.h>
#include <semaphore.h>
#include "sections.h"
#include "mdat.h"
// TODO: Declare shared variables here
int numPhils;
sem_t * sem_arr;
void sectionInitGlobals(int numPhilosophers)
{
// TODO: Complete this function
int i;
char char_arr[50];
sem_t arr[numPhilosophers];
numPhils = numPhilosophers;
for(i = 0; i < numPhilosophers; i++)
{
sprintf(char_arr,"%d", i);
mdat_sem_init(char_arr, &arr[i], 0, 1);
}
sem_arr = arr;
}
void sectionRunPhilosopher(int philosopherID, int numRounds)
{
int lChop = philosopherID;
int rChop;
int i;
if(philosopherID == 0)
rChop = numPhils - 1;
else
rChop = philosopherID - 1;
for(i = 0; i < numRounds; i++)
{
if(philosopherID != numPhils - 1)
{
mdat_sem_wait(&sem_arr[lChop]);
mdat_sem_wait(&sem_arr[rChop]);
eat();
mdat_sem_post(&sem_arr[rChop]);
mdat_sem_post(&sem_arr[lChop]);
}
else
{
mdat_sem_wait(&sem_arr[rChop]);
mdat_sem_wait(&sem_arr[lChop]);
eat();
mdat_sem_post(&sem_arr[lChop]);
mdat_sem_post(&sem_arr[rChop]);
}
think();
}
}
The classic Dining Philosophers problem has N philosophers and N forks; but each needs 2 forks to eat. A given fork semaphore may have a maximum value of 1 [ available ], and a minimum value of -1 ( one has the fork, one is waiting on the fork ). Your forks have values of 10 and 20?
In your logic, you check the value of the semaphore, and if it is >= 0, you say that you “have it”, then go on to check the other one; but you don’t have it. You don’t have a semaphore until you have waited on it. After eat()ing, you post to both of them, even though you may not have ever waited on either of them. That is why you have insanely high values for the semaphores.
Secondly, by the time sem_get_value has returned, the value of the semaphore may have changed. This is a common synchronization problem, so common it has a name: TOCTOU (Time Of Check to Time Of Use). You need to use mechanisms where you make decisions based upon actions, not just checking the status.
Third, one you change this to effectively sit in a loop:
sem_wait(left);
sem_wait(right);
eat();
sem_post(right);
sem_post(left);
You will have a completely different synchronization problem, which is the one that the Dining Philosophers is meant to illustrate. Happy Hunting!