1 /*
2 * Copyright (c) 2018 Intel Corporation
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 SEMAPHORES or MUTEXES as object types for its
13 * synchronization. To configure a specific object, set the value of FORKS to one
14 * of these.
15 *
16 * By default, the demo uses MUTEXES.
17 *
18 * The demo can be configured to work with threads of the same priority or
19 * not. If using different priorities of preemptible threads; if using one
20 * priority, there will be six preemptible threads of priority normal.
21 *
22 * By default, the demo uses different priorities.
23 *
24 * The number of threads is set via NUM_PHIL. The demo has only been tested
25 * with six threads. In theory it should work with any number of threads, but
26 * not without making changes to the thread attributes and corresponding kernel
27 * object attributes array in the phil_obj_abstract.h
28 * header file.
29 */
30 #include <zephyr/kernel.h>
31 #include <cmsis_os.h>
32
33 #if defined(CONFIG_STDOUT_CONSOLE)
34 #include <stdio.h>
35 #else
36 #include <zephyr/sys/printk.h>
37 #endif
38
39 #include <zephyr/sys/__assert.h>
40
41 #include "phil_obj_abstract.h"
42
43 #define SEMAPHORES 1
44 #define MUTEXES 2
45
46 /**************************************/
47 /* control the behaviour of the demo **/
48
49 #ifndef DEBUG_PRINTF
50 #define DEBUG_PRINTF 0
51 #endif
52
53 #ifndef FORKS
54 #define FORKS MUTEXES
55 #if 0
56 #define FORKS SEMAPHORES
57 #endif
58 #endif
59
60 #ifndef SAME_PRIO
61 #define SAME_PRIO 0
62 #endif
63
64 #ifndef NUM_PHIL
65 #define NUM_PHIL 6
66 #endif
67
68 /* end - control behaviour of the demo */
69 /***************************************/
70 osSemaphoreId forks[NUM_PHIL];
71
72 #define fork(x) (forks[x])
73
74 /*
75 * CMSIS limits the stack size, but qemu_x86_64, qemu_xtensa (all),
76 * qemu_leon3 and the boards such as up_squared, intel_ehl_crb,
77 * acrn_ehl_crb need 1024 to run this.
78 * For other arch and boards suggested stack size is 512.
79 */
80 #define STACK_SIZE CONFIG_CMSIS_THREAD_MAX_STACK_SIZE
81
82 #if DEBUG_PRINTF
83 #define PR_DEBUG printk
84 #else
85 #define PR_DEBUG(...)
86 #endif
87
88 #include "phil_obj_abstract.h"
89
set_phil_state_pos(int id)90 static void set_phil_state_pos(int id)
91 {
92 #if !DEBUG_PRINTF
93 printk("\x1b[%d;%dH", id + 1, 1);
94 #endif
95 }
96
97 #include <stdarg.h>
print_phil_state(int id,const char * fmt,int32_t delay)98 static void print_phil_state(int id, const char *fmt, int32_t delay)
99 {
100 int prio = osThreadGetPriority(osThreadGetId());
101
102 set_phil_state_pos(id);
103 #define STATE_LEN 80
104 char state[STATE_LEN];
105 int p = 0;
106
107 p += snprintk(state + p, STATE_LEN - p, "Philosopher %d [%s:%s%d] ",
108 id, prio < 0 ? "C" : "P",
109 prio < 0 ? "" : " ",
110 prio);
111
112 if (delay) {
113 p += snprintk(state + p, STATE_LEN - p, fmt,
114 delay < 1000 ? " " : "", delay);
115 } else {
116 p += snprintk(state + p, STATE_LEN - p, fmt, "");
117 }
118
119 p += snprintk(state + p, STATE_LEN - p, "\n");
120 printk("%s", state);
121 }
122
get_random_delay(int id,int period_in_ms)123 static int32_t get_random_delay(int id, int period_in_ms)
124 {
125 /*
126 * The random delay is unit-less, and is based on the philosopher's ID
127 * and the current uptime to create some pseudo-randomness. It produces
128 * a value between 0 and 31.
129 */
130 int32_t delay = (k_uptime_get_32() / 100 * (id + 1)) & 0x1f;
131
132 /* add 1 to not generate a delay of 0 */
133 int32_t ms = (delay + 1) * period_in_ms;
134
135 return ms;
136 }
137
is_last_philosopher(int id)138 static inline int is_last_philosopher(int id)
139 {
140 return id == (NUM_PHIL - 1);
141 }
142
philosopher(void const * id)143 void philosopher(void const *id)
144 {
145 fork_t fork1;
146 fork_t 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 fork1 = fork(0);
153 fork2 = fork(my_id);
154 } else {
155 fork1 = fork(my_id);
156 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(fork1);
164 print_phil_state(my_id, " HOLDING ONE FORK ", 0);
165 take(fork2);
166
167 delay = get_random_delay(my_id, 25);
168 print_phil_state(my_id, " EATING [ %s%d ms ] ", delay);
169 osDelay(delay);
170
171 drop(fork2);
172 print_phil_state(my_id, " DROPPED ONE FORK ", 0);
173 drop(fork1);
174
175 delay = get_random_delay(my_id, 25);
176 print_phil_state(my_id, " THINKING [ %s%d ms ] ", delay);
177 osDelay(delay);
178 }
179
180 }
181
182 osThreadDef(philosopher, osPriorityLow, 6, STACK_SIZE);
183
new_prio(int phil)184 static int new_prio(int phil)
185 {
186 #if SAME_PRIO
187 return osPriorityNormal;
188 #else
189 return osPriorityLow + phil;
190 #endif
191 }
192
start_threads(void)193 static void start_threads(void)
194 {
195 osThreadId id;
196
197 for (int i = 0; i < NUM_PHIL; i++) {
198 int prio = new_prio(i);
199 id = osThreadCreate(osThread(philosopher), INT_TO_POINTER(i));
200 osThreadSetPriority(id, prio);
201 }
202 }
203
204 #define DEMO_DESCRIPTION \
205 "\x1b[2J\x1b[15;1H" \
206 "Demo Description\n" \
207 "----------------\n" \
208 "An implementation of a solution to the Dining Philosophers\n" \
209 "problem (a classic multi-thread synchronization problem) using\n" \
210 "CMSIS RTOS V1 APIs. This particular implementation demonstrates the\n" \
211 "usage of multiple preemptible threads of differing\n" \
212 "priorities, as well as %s and thread sleeping.\n", fork_type_str
213
display_demo_description(void)214 static void display_demo_description(void)
215 {
216 #if !DEBUG_PRINTF
217 printk(DEMO_DESCRIPTION);
218 #endif
219 }
220
main(void)221 int main(void)
222 {
223 display_demo_description();
224 start_threads();
225 return 0;
226 }
227
