README.rst
1.. _dining-philosophers-sample:
2
3Dining Philosophers
4###################
5
6Overview
7********
8
9An implementation of a solution to the Dining Philosophers problem (a classic multi-thread
10synchronization problem). This particular implementation demonstrates the usage of multiple
11preemptible and cooperative threads of differing priorities, as well as dynamic mutexes and thread
12sleeping.
13
14The philosopher always tries to get the lowest fork first (f1 then f2). When done, he will give
15back the forks in the reverse order (f2 then f1). If he gets two forks, he is ``EATING``.
16Otherwise, he is ``THINKING``. Transitional states are shown as well, such as ``STARVING`` when the
17philosopher is hungry but the forks are not available, and ``HOLDING ONE FORK`` when a philosopher
18is waiting for the second fork to be available.
19
20Each Philosopher will randomly alternate between the ``EATING`` and ``THINKING`` states.
21
22It is possible to run the demo in `coop-only` or `preempt-only` mode. To achieve this, set these
23values for ``CONFIG_NUM_COOP_PRIORITIES`` and ``CONFIG_NUM_PREEMPT_PRIORITIES`` in :file:`prj.conf`:
24
25preempt-only
26 .. code-block:: cfg
27
28 CONFIG_NUM_PREEMPT_PRIORITIES=6
29 CONFIG_NUM_COOP_PRIORITIES=0
30
31
32coop-only
33 .. code-block:: cfg
34
35 CONFIG_NUM_PREEMPT_PRIORITIES=0
36 CONFIG_NUM_COOP_PRIORITIES=6
37
38In these cases, the philosopher threads will run with priorities 0 to 5 (preempt-only) and -7 to -2
39(coop-only).
40
41Building and Running
42********************
43
44This project outputs to the console. It can be built and executed on QEMU as follows:
45
46.. zephyr-app-commands::
47 :zephyr-app: samples/philosophers
48 :host-os: unix
49 :board: qemu_x86
50 :goals: run
51 :compact:
52
53Sample Output
54=============
55
56.. code-block::
57
58 Philosopher 0 [P: 3] HOLDING ONE FORK
59 Philosopher 1 [P: 2] HOLDING ONE FORK
60 Philosopher 2 [P: 1] EATING [ 1900 ms ]
61 Philosopher 3 [P: 0] THINKING [ 2500 ms ]
62 Philosopher 4 [C:-1] THINKING [ 2200 ms ]
63 Philosopher 5 [C:-2] THINKING [ 1700 ms ]
64
65Exit QEMU by pressing :kbd:`CTRL+A` :kbd:`x`.
66
67Debug Threads
68*************
69
70The philosophers sample by default enables :kconfig:option:`CONFIG_DEBUG_THREAD_INFO`. This allows
71tools like OpenOCD and J-link to inspect thread data using ``info threads``.
72
73.. zephyr-app-commands::
74 :zephyr-app: samples/philosophers
75 :host-os: unix
76 :board: <board_name>
77 :goals: debug
78 :compact:
79
80
81OpenOCD Sample Output
82=====================
83
84.. code-block::
85
86 Thread 1 received signal SIGINT, Interrupt.
87 [Switching to Thread 537003160]
88 arch_cpu_idle () at zephyr/mainline/zephyr/arch/arm/core/cpu_idle.S:107
89 107 cpsie i
90 (gdb) i threads
91 Id Target Id Frame
92 * 1 Thread 537003160 (Name: idle 00, prio:40,useropts:1) arch_cpu_idle () at zephyr/mainline/zephyr/arch/arm/core/cpu_idle.S:107
93 Info : Getting thread 537002984 reg list
94 2 Thread 537002984 (Name: Philosopher 5, prio:-2,useropts:4) 0x08001404 in arch_irq_unlock (key=0) at zephyr/mainline/zephyr/include/arch/arm/asm_inline_gcc.h:95
95 Info : Getting thread 537002808 reg list
96 3 Thread 537002808 (Name: Philosopher 4, prio:-1,useropts:4) 0x08001404 in arch_irq_unlock (key=0) at zephyr/mainline/zephyr/include/arch/arm/asm_inline_gcc.h:95
97 Info : Getting thread 537002632 reg list
98 4 Thread 537002632 (Name: Philosopher 3, prio:0,useropts:4) 0x08001404 in arch_irq_unlock (key=0) at zephyr/mainline/zephyr/include/arch/arm/asm_inline_gcc.h:95
99 Info : Getting thread 537002456 reg list
100 5 Thread 537002456 (Name: Philosopher 2, prio:1,useropts:4) 0x08001404 in arch_irq_unlock (key=0) at zephyr/mainline/zephyr/include/arch/arm/asm_inline_gcc.h:95
101 Info : Getting thread 537002280 reg list
102 6 Thread 537002280 (Name: Philosopher 1, prio:2,useropts:4) 0x08001404 in arch_irq_unlock (key=0) at zephyr/mainline/zephyr/include/arch/arm/asm_inline_gcc.h:95
103 Info : Getting thread 537002104 reg list
104 7 Thread 537002104 (Name: Philosopher 0, prio:3,useropts:4) 0x08001404 in arch_irq_unlock (key=0) at zephyr/mainline/zephyr/include/arch/arm/asm_inline_gcc.h:95
105
106.. code-block::
107
108 Philosopher 0 [P: 3] STARVING
109 Philosopher 1 [P: 2] HOLDING ONE FORK
110 Philosopher 2 [P: 1] EATING [ 400 ms ]
111 Philosopher 3 [P: 0] THINKING [ 525 ms ]
112 Philosopher 4 [C:-1] HOLDING ONE FORK
113 Philosopher 5 [C:-2] EATING [ 625 ms ]
114
115
116J-Link Sample Output
117====================
118
119.. code-block::
120
121 Thread 2 received signal SIGTRAP, Trace/breakpoint trap.
122 [Switching to Thread 537920592]
123 arch_cpu_idle () at zephyr/mainline/zephyr/arch/arm/core/cpu_idle.S:107
124 107 cpsie i
125 (gdb) i threads
126 Id Target Id Frame
127 * 2 Thread 537920592 (idle 00 UNKNOWN PRIO 40) arch_cpu_idle () at zephyr/mainline/zephyr/arch/arm/core/cpu_idle.S:107
128 3 Thread 537919536 (Philosopher 0 PENDING PRIO 3) arch_swap (key=0) at zephyr/mainline/zephyr/arch/arm/core/swap.c:53
129 4 Thread 537919712 (Philosopher 1 SUSPENDED PRIO 2) arch_swap (key=key@entry=0) at zephyr/mainline/zephyr/arch/arm/core/swap.c:53
130 5 Thread 537919888 (Philosopher 2 SUSPENDED PRIO 1) arch_swap (key=key@entry=0) at zephyr/mainline/zephyr/arch/arm/core/swap.c:53
131 6 Thread 537920064 (Philosopher 3 SUSPENDED PRIO 0) arch_swap (key=key@entry=0) at zephyr/mainline/zephyr/arch/arm/core/swap.c:53
132 7 Thread 537920240 (Philosopher 4 PENDING PRIO 255) arch_swap (key=0) at zephyr/mainline/zephyr/arch/arm/core/swap.c:53
133 8 Thread 537920416 (Philosopher 5 SUSPENDED PRIO 254) arch_swap (key=key@entry=0) at zephyr/mainline/zephyr/arch/arm/core/swap.c:53
134
135.. code-block::
136
137 Philosopher 0 [P: 3] STARVING
138 Philosopher 1 [P: 2] EATING [ 475 ms ]
139 Philosopher 2 [P: 1] THINKING [ 700 ms ]
140 Philosopher 3 [P: 0] THINKING [ 525 ms ]
141 Philosopher 4 [C:-1] HOLDING ONE FORK
142 Philosopher 5 [C:-2] EATING [ 625 ms ]
143
