My semaphore module is not working properly(Dining philosopher)

Question

I'm implementing a semaphore methods to understand synchronization and thread things.

By using my semaphore, I tried to solve the Dining Philosophers problem.

My plan was making deadlock situation first.

But I found that just only one philosopher eat repeatedly.

And I checked that my semaphore is working quite good by using other synchronization problems. I think there is some problem with grammar.

please let me know what is the problem.

Here is my code.

dinig.c (including main function)

#include "sem.h"
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

static tsem_t *chopstick[5];
static tsem_t *updating;

static int update_status (int i, int eating)
{
  static int status[5] = { 0, };
  static int duplicated;
  int idx;
  int sum;

  tsem_wait (updating);

  status[i] = eating;

  /* Check invalid state. */
  duplicated = 0;
  sum = 0;
  for (idx = 0; idx < 5; idx++)
    {
      sum += status[idx];
      if (status[idx] && status[(idx + 1) % 5])
    duplicated++;
    }

  /* Avoid printing empty table. */
  if (sum == 0)
    {
      tsem_signal (updating);
      return 0;
    }

  for (idx = 0; idx < 5; idx++)
    fprintf (stdout, "%3s     ", status[idx] ? "EAT" : "...");

  /* Stop on invalid state. */
  if (sum > 2 || duplicated > 0)
    {
      fprintf (stdout, "invalid %d (duplicated:%d)!\n", sum, duplicated);
      exit (1);
    }
  else
    fprintf (stdout, "\n");

  tsem_signal (updating);

  return 0;
}

void *thread_func (void *arg)
{
  int i = (int) (long) arg;
  int k = (i + 1) % 5;

  do
    {
      tsem_wait (chopstick[i]);
      tsem_wait (chopstick[k]);
      update_status (i, 1);
      update_status (i, 0);
      tsem_signal (chopstick[i]);
      tsem_signal (chopstick[k]);
    }
  while (1);

  return NULL;
}

int main (int    argc,
      char **argv)
{
  int i;

  for (i = 0; i < 5; i++)
    chopstick[i] = tsem_new (1);
  updating = tsem_new (1);

  for (i = 0; i < 5; i++)
    {
      pthread_t tid;

      pthread_create (&tid, NULL, thread_func, (void *) (long) i);
    }

  /* endless thinking and eating... */
  while (1)
    usleep (10000000);

  return 0;
}

sem.c(including semaphore methods)

#include "sem.h"
.

sem.h(Header for sem.c)

#ifndef __SEM_H__
#define __SEM_H__

#include <pthread.h>

typedef struct test_semaphore tsem_t;

tsem_t *tsem_new      (int      value);
void    tsem_free     (tsem_t  *sem);
void    tsem_wait     (tsem_t  *sem);
int     tsem_try_wait (tsem_t  *sem);
void    tsem_signal   (tsem_t  *sem);

#endif /* __SEM_H__ */

compile command

gcc sem.c dining.c -pthread -o dining

Answer 1

One problem is that in tsem_wait() you have the following code sequence outside of a lock:

while(sem->count <= 0)
    continue;

There's no guarantee that the program will actually re-read sem->count - the compiler is free to produce machine code that does something like the following:

int temp = sem->count;
while(temp <= 0)
    continue;

In fact, this will likely happen in an optimized build.

Try changing your busy wait loop to something like this so the count is checked while holding the lock:

void tsem_wait (tsem_t *sem)
{
    pthread_mutex_lock(&(sem->mutexLock));

    while (sem->count <= 0) {
        pthread_mutex_unlock(&(sem->mutexLock));
        usleep(1);
        pthread_mutex_lock(&(sem->mutexLock));
    }

    // sem->mutexLock is still held here...

    sem->count--;
    pthread_mutex_unlock(&(sem->mutexLock));
}

Strictly speaking, you should do something similar for tsem_try_wait() (which you're not using yet).

Note that you might want to consider using a pthread_cond_t to make waiting on the counter changing more efficient.

Finally, your code to 'get' the chopsticks in thread_func() has the classic Dining Philosopher deadlock problem in the situation where each philosopher simultaneously acquires the 'left' chopstick (chopstick[i]) and ends up waiting forever to get the 'right' chopstick (chopstick[k]) since all the chopsticks are in some philosopher's left hand.