1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
|
# The Dining Philosophers Problem in C
## Description
This repository carries the source code of a project similar to the Dining
Philosophers Problem.
I wrote this program to learn about C and pthreads.
There are a couple more 'features' in addition to the original requirements of
the dining philosophers problem:
- 'fork cooldown': a philosopher has to wait x numbers of milliseconds before
she can pick up a fork
- a scheduler; a heap queue with two priority methods: 'first in first out'
(fifo) or 'earliest deadline first' (edf); the priority queue lives on the
fork.
## Instructions
To compile:
$ make
To run:
$ ./philo number_of_philos time_to_starve time_to_eat time_to_reflect
time_to_think number_of_eats_required fork_cooldown scheduler
To delete ./build:
$ make clean
To delete ./build and the binaries:
$ make fclean
To delete and recompile:
$ make re
From the school subject:
- number\_of\_philos: The number of philosophers and also the number of forks.
- time\_to\_starve (in milliseconds): If a philosopher did not start eating
within time\_to\_starve milliseconds since the beginning of the last time
they ate or the beginning of the simulation, they starve.
- time\_to\_eat (in milliseconds): The time it takes for a philosopher to eat.
During that time, they must hold two forks.
- time\_to\_reflect (in milliseconds): The time a philosopher will spend
reflecting.
- time\_to\_think (in milliseconds): The time a philosopher will spend
thinking. After completing the thinking phase, the philosopher will
immediately attempt to acquire forks and start eating again.
- number\_of\_eats\_required: If all philosophers have eaten at least this many
times, the simulation stops. Otherwise, it stops when a philosopher burns
out.
- fork\_cooldown (in milliseconds): After being released, a fork is unavailable
until its cooldown has passed.
- scheduler: The arbitration policy used by forks to decide who gets them when
multiple philosophers request them. The value must be exactly one of: fifo
or edf. fifo means First In, First Out: the fork is granted to the philosopher
whose request arrived first. edf means Earliest Deadline First with deadline =
last\_eat\_start + time\_to\_burnout.
## Resources
- Advanced Programming in the UNIX Environment, third edition, W. Richard
Stevens, Stephen A. Rago, Chapter 11 on pthread
- on pthreads:
https://www.cs.cmu.edu/afs/cs/academic/class/15492-f07/www/pthreads.html
- on valgrind: https://bytes.usc.edu/cs104/wiki/valgrind/
- on valgrind: https://valgrind.org/docs/manual/mc-manual.html
- on drd: https://valgrind.org/docs/manual/drd-manual.html
- the man pages of pthread\_create, pthread\_mutex\_lock,
pthread\_cond\_and\_wait, pthread\_join, pthread\_mutex\_destroy
## Blocking cases handled
Deadlock: I use the parity solution. To prevent deadlocks, odd-numbered and
even-numbered philosophers pick up their forks in different orders.
Starvation prevention: whether it be with fifo or edf schedulers, a philosopher
may only eat when their ticket is first in the queue.
Cooldown handling: forks record the last time at which they were released.
Before a philosopher checks whether their ticket is first in queue, or attempts
to lock the mutex of a fork, a function computes how much time is left until a
fork has cooled down, that is the waiting time. usleep() is then called with
the waiting time passed as a parameter. There is also one more call of that
function after a mutex is locked to deal with a hedge-case.
Precise starving detection: to detect whether a philosopher has starved, a
monitoring thread runs. In the routine of this thread, there is a loop calling
a function check\_for\_starves which checks whether a philosopher has starves.
check\_for\_starves computes that no more than the time it takes for a
philosopher to burn out has elapsed since she last ate. If so,
check\_for\_starves updates the value of the variable philosopher\_starved
to 1. Concurrently, each time a philosopher is about to eat or each time the
log is about to print, a call to the the function
check\_if\_philosopher\_starved is made to check the value of
philosopher\_starved. If the value is equal to 1, the threads returns and
then join.
Log serialization: all prints go through the function print\_log. A mutex
guards access to printf().
## Thread synchronization mechanisms
The program uses pthread\_create, pthread\_join, pthread\_mutex\_init,
pthread\_mutex\_lock, pthread\_mutex\_unlock, pthread\_mutex\_destroy. It
creates one thread per philosopher and a monitoring thread. About
thread-safety: each variable accessed throughout the program by multiple
threads is protected by a mutex to prevent race conditions.
## To do, to improve
- the function create\_philosopher returns a pointer to a t\_philosopher. The function
could return a philosopher to reduce the number of malloc() this program
uses. However, I made create\_philosopher return a pointer because I wanted to
practice working with pointers.
- write a unique function to free all malloc
- use bzero instead of malloc to initialize all variables with 0
- think of how to refactor cooldown checks
- split h file into fork.h, philos.h and sim.h
## Troubleshooting, testing
Some commands I used to troubleshoot or test this program:
$ strace -f ./program args
$ valgrind --tool=drd ./program args
$ valgrind --tool=helgrind ./pogram args
# Ctrl + C and then 'thread apply all bt' in GDB when the program hangs
$ echo $? to see the exit value
$ addr2line -e ./codexion -f -C 0x4030F2 0x402001
$ ldd codexion to check which lib is used for compiling
## License
Copyright (C) 2026 yctct
This program is free software: you can redistribute it and/or modify it under
the terms of the GNU General Public License as published by the Free Software
Foundation, either version 3 of the License, or (at your option) any later
version.
This program is distributed in the hope that it will be useful, but WITHOUT ANY
WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A
PARTICULAR PURPOSE. See the GNU General Public License for more details.
You should have received a copy of the GNU General Public License along with
this program. If not, see <https://www.gnu.org/licenses/>.
See the file COPYING.
|
