I'm trying to implement a simple solution for Dining philosophers problem (with five philosophers) and my solution is based on this logic :
sem_t S[philosophers_number]
for each philosopher
{
while(TRUE)
{
if(current philosopher number != last philosopher)
{
thinking()
//i is number of current philosopher
sem_wait(take_chopstick(S[(i 1) % philosophers_number])) // right chopstick
sem_wait(take_chopstick(S[i])) // left chopstick
eat()
sem_post(put_chopstick(S[(i 1) % philosophers_number]))
sem_post(put_chopstick(S[i]))
}
else
{
thinking()
//i is number of current philosopher
sem_wait(take_chopstick(S[i])) // left chopstick
sem_wait(take_chopstick(S[(i 1) % philosophers_number])) // right chopstick
eat()
sem_post(put_chopstick(S[i]))
sem_post(put_chopstick(S[(i 1) % philosophers_number]))
}
}
Each philosopher first think for less than three seconds
Then if right chopstick is available philosopher will take it, and if also left one is available philosopher will take that too and start eating for less than three seconds
Then philosopher will put down chopsticks and make them available for other philosophers
To avoid cyclic wait, for last philosopher I will first pick left chopstick then right one and go on the same process
Here is the code I implemented based on this logic :
#include <stdio.h>
#include <string.h>
#include <pthread.h>
#include <semaphore.h>
#include <unistd.h>
#include <stdlib.h>
#define THREADS 5
sem_t chopstick[THREADS];
void thinking(int ph_num)
{
printf("philosopher %d is thinking\n", ph_num);
int t = rand() % 3;
sleep(t);// up to 3 secs thinking
}
void eat(int ph_num)
{
printf("philosopher %d is eating\n", ph_num);
int t = rand() % 3;
sleep(t);// up to 3 secs eating
}
void *philosopher(void * ph_num )
{
int num=(int)ph_num;
while(1)
{
if(num < THREADS - 1)
{
thinking(num);
//pick up right chopstick
sem_wait(&chopstick[(num 1) % THREADS]);
//to make deadlocks absolutly happen, wait 1 sec then pickup left chopstick
sleep(1);
//pick up left chopstick
sem_wait(&chopstick[num]);
eat(num);
//put down right chopstick
sem_post(&chopstick[(num 1) % THREADS]);
//put down left chopstick
sem_post(&chopstick[num]);
}
else // last one pick left chopstick first, instead of right one to avoid cyclic wait
{
thinking(num);
//pick up left chopstick
sem_wait(&chopstick[num]);
//to make deadlocks absolutly happen, wait 1 sec then pickup left chopstick
sleep(1);
//pick up right chopstick
sem_wait(&chopstick[(num 1) % THREADS]);
eat(num);
//put down left chopstick
sem_post(&chopstick[num]);
//put down right chopstick
sem_post(&chopstick[(num 1) % THREADS]);
}
}
pthread_exit((void *)num);
}
int main ()
{
for(int i = 0; i < THREADS; i )
{
sem_init(&chopstick[i],0,1);
}
pthread_t threads[THREADS];
for(int i = 0; i < THREADS; i )
pthread_create(&threads[i], NULL, philosopher, (void *)i);
for(int i = 0; i < THREADS; i )
pthread_join(threads[i],NULL);
return 0;
}
But during debugging this code a problem happened, where chopstick[i] was 0 before sem_wait(&chopstick[num]) instead of blocking current thread, until a chopstick is available sem_wait() carried on, so a philosopher started eating without an actual chopstick.
Can anyone help me figure out where is my problem?
CodePudding user response：
Your implementation is correct, the problem you have is in the method of debugging. If you use gdb, you will be stopped on only one thread, while the rest of the thread will continue the execution, so between the time you have inspected the semaphore and the time you stepped to the next line, other thread will progress the execution and can change the value you had inspected.
To be effective in debugging the threads, you need to assure that only the thread which is currently observed is scheduled and the rest of the threads are blocked. To do so, you need to change the scheduler-locking after you stop on the thread. You can set it to on or step, depending if you want the threads to by fully stopped, or only stopped during the singe-step operations (see help set scheduler-locking for more details).
Once the threads are locked you can use info threads to check what the rest of the threads are doing at the time. You can use thread <<n>> to change to the n-th thread and use where to check the thread stack.
Here is example with the scheduler set to step. You can see that only one thread had progressed on the next command.
(gdb) b 37
Breakpoint 1 at 0x1388: file test003.c, line 37.
(gdb) r
Starting program: /home/jordan/Development/tmptest/a.out
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/lib/x86_64-linux-gnu/libthread_db.so.1".
[New Thread 0x7ffff7d90700 (LWP 4002538)]
philosopher 0 is thinking
[New Thread 0x7ffff758f700 (LWP 4002539)]
philosopher 1 is thinking
[New Thread 0x7ffff6d8e700 (LWP 4002540)]
philosopher 2 is thinking
[2] picking 3
[New Thread 0x7ffff658d700 (LWP 4002541)]
[Switching to Thread 0x7ffff6d8e700 (LWP 4002540)]
Thread 4 "a.out" hit Breakpoint 1, philosopher (ph_num=0x2) at test003.c:37
37 sem_wait(&chopstick[(num 1) % THREADS]);
(gdb) set scheduler-locking step
(gdb) info threads
Id Target Id Frame
1 Thread 0x7ffff7d91740 (LWP 4002534) "a.out" clone () at ../sysdeps/unix/sysv/linux/x86_64/clone.S:78
2 Thread 0x7ffff7d90700 (LWP 4002538) "a.out" 0x00007ffff7e743bf in __GI___clock_nanosleep (clock_id=clock_id@entry=0, flags=flags@entry=0,
req=req@entry=0x7ffff7d8fe60, rem=rem@entry=0x7ffff7d8fe60) at ../sysdeps/unix/sysv/linux/clock_nanosleep.c:78
3 Thread 0x7ffff758f700 (LWP 4002539) "a.out" 0x00007ffff7e743bf in __GI___clock_nanosleep (clock_id=clock_id@entry=0, flags=flags@entry=0,
req=req@entry=0x7ffff758ee60, rem=rem@entry=0x7ffff758ee60) at ../sysdeps/unix/sysv/linux/clock_nanosleep.c:78
* 4 Thread 0x7ffff6d8e700 (LWP 4002540) "a.out" philosopher (ph_num=0x2) at test003.c:37
5 Thread 0x7ffff658d700 (LWP 4002541) "a.out" clone () at ../sysdeps/unix/sysv/linux/x86_64/clone.S:78
(gdb) n
38 printf("[%i] picked %i\n", num, (num 1) % THREADS);
(gdb) info threads
Id Target Id Frame
1 Thread 0x7ffff7d91740 (LWP 4002534) "a.out" clone () at ../sysdeps/unix/sysv/linux/x86_64/clone.S:78
2 Thread 0x7ffff7d90700 (LWP 4002538) "a.out" 0x00007ffff7e743bf in __GI___clock_nanosleep (clock_id=clock_id@entry=0, flags=flags@entry=0,
req=req@entry=0x7ffff7d8fe60, rem=rem@entry=0x7ffff7d8fe60) at ../sysdeps/unix/sysv/linux/clock_nanosleep.c:78
3 Thread 0x7ffff758f700 (LWP 4002539) "a.out" 0x00007ffff7e743bf in __GI___clock_nanosleep (clock_id=clock_id@entry=0, flags=flags@entry=0,
req=req@entry=0x7ffff758ee60, rem=rem@entry=0x7ffff758ee60) at ../sysdeps/unix/sysv/linux/clock_nanosleep.c:78
* 4 Thread 0x7ffff6d8e700 (LWP 4002540) "a.out" philosopher (ph_num=0x2) at test003.c:38
5 Thread 0x7ffff658d700 (LWP 4002541) "a.out" clone () at ../sysdeps/unix/sysv/linux/x86_64/clone.S:78
As you can see, after executing next, I am remaining on the same thread and other threads had not progressed.
I have used modified the code to make more visible what is happening, here is the code I used:
#include <stdio.h>
#include <string.h>
#include <pthread.h>
#include <semaphore.h>
#include <unistd.h>
#include <stdlib.h>
#define THREADS 5
sem_t chopstick[THREADS];
void thinking(int ph_num)
{
printf("philosopher %d is thinking\n", ph_num);
int t = rand() % 3;
sleep(t);// up to 3 secs thinking
}
void eat(int ph_num)
{
printf("philosopher %d is eating\n", ph_num);
int t = rand() % 3;
sleep(t);// up to 3 secs eating
}
void *philosopher(void * ph_num )
{
int num=(int)ph_num;
while(1)
{
if(num < THREADS - 1)
{
thinking(num);
//pick up right chopstick
printf("[%i] picking %i\n", num, (num 1) % THREADS);
sem_wait(&chopstick[(num 1) % THREADS]);
printf("[%i] picked %i\n", num, (num 1) % THREADS);
//to make deadlocks absolutly happen, wait 1 sec then pickup left chopstick
//sleep(1);
//pick up left chopstick
printf("[%i] picking %i\n", num, num);
sem_wait(&chopstick[num]);
printf("[%i] picked %i\n", num, num);
eat(num);
//put down right chopstick
printf("[%i] put %i\n", num, (num 1) % THREADS);
sem_post(&chopstick[(num 1) % THREADS]);
//put down left chopstick
printf("[%i] put %i\n", num, num);
sem_post(&chopstick[num]);
}
else // last one pick left chopstick first, instead of right one to avoid cyclic wait
{
thinking(num);
//pick up left chopstick
printf("[%i] picking %i\n", num, num);
sem_wait(&chopstick[num]);
printf("[%i] picked %i\n", num, num);
//to make deadlocks absolutly happen, wait 1 sec then pickup left chopstick
//sleep(1);
//pick up right chopstick
printf("[%i] picking %i\n", num, num 1);
sem_wait(&chopstick[(num 1) % THREADS]);
printf("[%i] picked %i\n", num, num 1);
eat(num);
//put down left chopstick
printf("[%i] put %i\n", num, num);
sem_post(&chopstick[num]);
//put down right chopstick
printf("[%i] put %i\n", num, (num 1) % THREADS);
sem_post(&chopstick[(num 1) % THREADS]);
}
}
pthread_exit((void *)num);
}
int main ()
{
for(int i = 0; i < THREADS; i )
{
sem_init(&chopstick[i],0,1);
}
pthread_t threads[THREADS];
for(int i = 0; i < THREADS; i )
pthread_create(&threads[i], NULL, philosopher, (void *)i);
for(int i = 0; i < THREADS; i )
pthread_join(threads[i],NULL);
return 0;
}