1 /*
2 * Copyright (c) 2011-2016 Wind River Systems, Inc.
3 *
4 * SPDX-License-Identifier: Apache-2.0
5 */
6
7 /**
8 * @file
9 *
10 * Dining philosophers demo
11 *
12 * The demo can be configured to use different object types for its
13 * synchronization: SEMAPHORES, MUTEXES, STACKS, FIFOS and LIFOS. To configure
14 * a specific object, set the value of FORKS to one of these.
15 *
16 * By default, the demo uses MUTEXES.
17 *
18 * The demo can also be configured to work with static objects or dynamic
19 * objects. The behavior will change depending if STATIC_OBJS is set to 0 or
20 * 1.
21 *
22 * By default, the demo uses dynamic objects.
23 *
24 * The demo can be configured to work with threads of the same priority or
25 * not. If using different priorities, two threads will be cooperative
26 * threads, and the other four will be preemptible threads; if using one
27 * priority, there will be six preemptible threads of priority 0. This is
28 * changed via SAME_PRIO.
29 *
30 * By default, the demo uses different priorities.
31 *
32 * The number of threads is set via NUM_PHIL. The demo has only been tested
33 * with six threads. In theory it should work with any number of threads, but
34 * not without making changes to the forks[] array in the phil_obj_abstract.h
35 * header file.
36 */
37
38 #include <zephyr/kernel.h>
39
40 #if defined(CONFIG_STDOUT_CONSOLE)
41 #include <stdio.h>
42 #else
43 #include <zephyr/sys/printk.h>
44 #endif
45
46 #include <zephyr/sys/__assert.h>
47
48 #define SEMAPHORES 1
49 #define MUTEXES 2
50 #define STACKS 3
51 #define FIFOS 4
52 #define LIFOS 5
53
54 /**************************************/
55 /* control the behaviour of the demo **/
56
57 #ifndef DEBUG_PRINTF
58 #define DEBUG_PRINTF 0
59 #endif
60
61 #ifndef NUM_PHIL
62 #define NUM_PHIL 6
63 #endif
64
65 #ifndef STATIC_OBJS
66 #define STATIC_OBJS 0
67 #endif
68
69 #ifndef FORKS
70 #define FORKS MUTEXES
71 #if 0
72 #define FORKS SEMAPHORES
73 #define FORKS STACKS
74 #define FORKS FIFOS
75 #define FORKS LIFOS
76 #endif
77 #endif
78
79 #ifndef SAME_PRIO
80 #define SAME_PRIO 0
81 #endif
82
83 /* end - control behaviour of the demo */
84 /***************************************/
85
86 #define STACK_SIZE (2048)
87
88 #include "phil_obj_abstract.h"
89
90 #define fork(x) (forks[x])
91
set_phil_state_pos(int id)92 static void set_phil_state_pos(int id)
93 {
94 #if !DEBUG_PRINTF
95 printk("\x1b[%d;%dH", id + 1, 1);
96 #endif
97 }
98
99 #include <stdarg.h>
print_phil_state(int id,const char * fmt,int32_t delay)100 static void print_phil_state(int id, const char *fmt, int32_t delay)
101 {
102 int prio = k_thread_priority_get(k_current_get());
103
104 set_phil_state_pos(id);
105
106 printk("Philosopher %d [%s:%s%d] ",
107 id, prio < 0 ? "C" : "P",
108 prio < 0 ? "" : " ",
109 prio);
110
111 if (delay) {
112 printk(fmt, delay < 1000 ? " " : "", delay);
113 } else {
114 printk(fmt, "");
115 }
116
117 printk("\n");
118 }
119
get_random_delay(int id,int period_in_ms)120 static int32_t get_random_delay(int id, int period_in_ms)
121 {
122 /*
123 * The random delay is unit-less, and is based on the philosopher's ID
124 * and the current uptime to create some pseudo-randomness. It produces
125 * a value between 0 and 31.
126 */
127 int32_t delay = (k_uptime_get_32()/100 * (id + 1)) & 0x1f;
128
129 /* add 1 to not generate a delay of 0 */
130 int32_t ms = (delay + 1) * period_in_ms;
131
132 return ms;
133 }
134
is_last_philosopher(int id)135 static inline int is_last_philosopher(int id)
136 {
137 return id == (NUM_PHIL - 1);
138 }
139
philosopher(void * id,void * unused1,void * unused2)140 void philosopher(void *id, void *unused1, void *unused2)
141 {
142 ARG_UNUSED(unused1);
143 ARG_UNUSED(unused2);
144
145 fork_t my_fork1;
146 fork_t my_fork2;
147
148 int my_id = POINTER_TO_INT(id);
149
150 /* Djkstra's solution: always pick up the lowest numbered fork first */
151 if (is_last_philosopher(my_id)) {
152 my_fork1 = fork(0);
153 my_fork2 = fork(my_id);
154 } else {
155 my_fork1 = fork(my_id);
156 my_fork2 = fork(my_id + 1);
157 }
158
159 while (1) {
160 int32_t delay;
161
162 print_phil_state(my_id, " STARVING ", 0);
163 take(my_fork1);
164 print_phil_state(my_id, " HOLDING ONE FORK ", 0);
165 take(my_fork2);
166
167 delay = get_random_delay(my_id, 25);
168 print_phil_state(my_id, " EATING [ %s%d ms ] ", delay);
169 k_msleep(delay);
170
171 drop(my_fork2);
172 print_phil_state(my_id, " DROPPED ONE FORK ", 0);
173 drop(my_fork1);
174
175 delay = get_random_delay(my_id, 25);
176 print_phil_state(my_id, " THINKING [ %s%d ms ] ", delay);
177 k_msleep(delay);
178 }
179
180 }
181
new_prio(int phil)182 static int new_prio(int phil)
183 {
184 #if defined(CONFIG_COOP_ENABLED) && defined(CONFIG_PREEMPT_ENABLED)
185 #if SAME_PRIO
186 return 0;
187 #else
188 return -(phil - (NUM_PHIL/2));
189 #endif
190 #else
191 #if defined(CONFIG_COOP_ENABLED)
192 return -phil - 2;
193 #elif defined(CONFIG_PREEMPT_ENABLED)
194 return phil;
195 #else
196 #error unpossible
197 #endif
198 #endif
199 }
200
init_objects(void)201 static void init_objects(void)
202 {
203 #if !STATIC_OBJS
204 for (int i = 0; i < NUM_PHIL; i++) {
205 fork_init(fork(i));
206 }
207 #endif
208 }
209
start_threads(void)210 static void start_threads(void)
211 {
212 /*
213 * create two coop. threads (prios -2/-1) and four preemptive threads
214 * : (prios 0-3)
215 */
216 for (int i = 0; i < NUM_PHIL; i++) {
217 int prio = new_prio(i);
218
219 k_thread_create(&threads[i], &stacks[i][0], STACK_SIZE,
220 philosopher, INT_TO_POINTER(i), NULL, NULL,
221 prio, K_USER, K_FOREVER);
222 #ifdef CONFIG_THREAD_NAME
223 char tname[CONFIG_THREAD_MAX_NAME_LEN];
224
225 snprintk(tname, CONFIG_THREAD_MAX_NAME_LEN, "Philosopher %d", i);
226 k_thread_name_set(&threads[i], tname);
227 #endif /* CONFIG_THREAD_NAME */
228 k_object_access_grant(fork(i), &threads[i]);
229 k_object_access_grant(fork((i + 1) % NUM_PHIL), &threads[i]);
230
231 k_thread_start(&threads[i]);
232 }
233 }
234
235 #define DEMO_DESCRIPTION \
236 "\x1b[2J\x1b[15;1H" \
237 "Demo Description\n" \
238 "----------------\n" \
239 "An implementation of a solution to the Dining Philosophers\n" \
240 "problem (a classic multi-thread synchronization problem).\n" \
241 "This particular implementation demonstrates the usage of multiple\n" \
242 "preemptible and cooperative threads of differing priorities, as\n" \
243 "well as %s %s and thread sleeping.\n", obj_init_type, fork_type_str
244
display_demo_description(void)245 static void display_demo_description(void)
246 {
247 #if !DEBUG_PRINTF
248 printk(DEMO_DESCRIPTION);
249 #endif
250 }
251
main(void)252 int main(void)
253 {
254 display_demo_description();
255 #if CONFIG_TIMESLICING
256 k_sched_time_slice_set(5000, 0);
257 #endif
258
259 init_objects();
260 start_threads();
261
262 #ifdef CONFIG_COVERAGE
263 /* Wait a few seconds before main() exit, giving the sample the
264 * opportunity to dump some output before coverage data gets emitted
265 */
266 k_sleep(K_MSEC(5000));
267 #endif
268 return 0;
269 }
270
