hobbielektronika / Mbed 2 deprecated 10_rtos_dpp_mutex

Dining Philosophers Problem solved by the help of mutexes

Dependencies:   mbed-rtos mbed

main.cpp@0:1424c0020312, 2016-02-10 (annotated)

Committer:
icserny
Date:
Wed Feb 10 12:58:14 2016 +0000
Revision:
0:1424c0020312
First version

Who changed what in which revision?

UserRevisionLine numberNew contents of line
icserny 0:1424c0020312 1 /** 10_rtos_dpp_mutex
icserny 0:1424c0020312 2 * The dining philosophers problem is invented by E. W. Dijkstra.
icserny 0:1424c0020312 3 * Imagine that five philosophers sitting around a round table with five chairs,
icserny 0:1424c0020312 4 * who spend their lives alternating between thinking and eating
icserny 0:1424c0020312 5 * from a large bowl of rice at random intervals.
icserny 0:1424c0020312 6 * However, there are only five chopsticks available at the right hand and
icserny 0:1424c0020312 7 * left hand of each philosopher. Each philosopher thinks. When he gets hungry,
icserny 0:1424c0020312 8 * he picks up the two chopsticks that are closest to him. If a philosopher can pick
icserny 0:1424c0020312 9 * up both chopsticks, he eats for a while. After a philosopher finishes eating,
icserny 0:1424c0020312 10 * he puts down the chopsticks and starts to think again.
icserny 0:1424c0020312 11 *
icserny 0:1424c0020312 12 * Since the chopsticks are shared between the philosophers, access to the chopsticks
icserny 0:1424c0020312 13 * must be protected, but if care isn't taken, concurrency problems arise. Most notably,
icserny 0:1424c0020312 14 * starvation via deadlock can occur: if each philosopher picks up a chopstick as soon
icserny 0:1424c0020312 15 * as it is available and waits indefinitely for the other, eventually they will all end
icserny 0:1424c0020312 16 * up holding only one chopstick with no chance of acquiring another.
icserny 0:1424c0020312 17 *
icserny 0:1424c0020312 18 * In this solution we instruct our philosophers to cooperate: to put down the
icserny 0:1424c0020312 19 * acquired chopstick, if the second is not available, and wait for a (short) random interval.
icserny 0:1424c0020312 20 * This is the same techniqe used by the network cards when they detected packet collision.
icserny 0:1424c0020312 21 *
icserny 0:1424c0020312 22 * The five chopsticks are represented by five mutexes.
icserny 0:1424c0020312 23 * The philosophers are represented as threads.
icserny 0:1424c0020312 24 *
icserny 0:1424c0020312 25 * Hardware requirements:
icserny 0:1424c0020312 26 * - FRDM-KL25Z board
icserny 0:1424c0020312 27 */
icserny 0:1424c0020312 28 #include "mbed.h"
icserny 0:1424c0020312 29 #include "rtos.h"
icserny 0:1424c0020312 30
icserny 0:1424c0020312 31 Mutex stdio_mutex;
icserny 0:1424c0020312 32 Mutex chopstick[5]; //Array of mutexes representing the 5 chopsticks
icserny 0:1424c0020312 33
icserny 0:1424c0020312 34 void notify(int num, int state)
icserny 0:1424c0020312 35 {
icserny 0:1424c0020312 36 stdio_mutex.lock();
icserny 0:1424c0020312 37 if(state) {
icserny 0:1424c0020312 38 printf("Philospher %d is EATING \n\r", num);
icserny 0:1424c0020312 39 }
icserny 0:1424c0020312 40 else {
icserny 0:1424c0020312 41 printf("Philospher %d is thinking \n\r", num);
icserny 0:1424c0020312 42 }
icserny 0:1424c0020312 43 stdio_mutex.unlock();
icserny 0:1424c0020312 44 }
icserny 0:1424c0020312 45
icserny 0:1424c0020312 46 void philosopher(void const *args)
icserny 0:1424c0020312 47 {
icserny 0:1424c0020312 48 while (true) {
icserny 0:1424c0020312 49 if(chopstick[(int)args-1].trylock()) {
icserny 0:1424c0020312 50 if(chopstick[(int)args%5].trylock()) {
icserny 0:1424c0020312 51 notify((int)args,1); //Start EATING
icserny 0:1424c0020312 52 Thread::wait(1000+rand()%1000);
icserny 0:1424c0020312 53 chopstick[(int)args%5].unlock(); //Release chopsticks
icserny 0:1424c0020312 54 chopstick[(int)args-1].unlock();
icserny 0:1424c0020312 55 notify((int)args,0); //Start Thinking
icserny 0:1424c0020312 56 Thread::wait(2000+rand()%2000); //Get's hungry after this time...
icserny 0:1424c0020312 57 }
icserny 0:1424c0020312 58 else {
icserny 0:1424c0020312 59 chopstick[(int)args-1].unlock();
icserny 0:1424c0020312 60 Thread::wait(100+rand()%100); //Wait for random time if failed
icserny 0:1424c0020312 61 }
icserny 0:1424c0020312 62 }
icserny 0:1424c0020312 63 else {
icserny 0:1424c0020312 64 Thread::wait(100+rand()%100); //Wait for random time if failed
icserny 0:1424c0020312 65 }
icserny 0:1424c0020312 66
icserny 0:1424c0020312 67 }
icserny 0:1424c0020312 68 }
icserny 0:1424c0020312 69
icserny 0:1424c0020312 70 int main()
icserny 0:1424c0020312 71 {
icserny 0:1424c0020312 72 Thread t2(philosopher, (void *)2U);
icserny 0:1424c0020312 73 Thread t3(philosopher, (void *)3U);
icserny 0:1424c0020312 74 Thread t4(philosopher, (void *)4U);
icserny 0:1424c0020312 75 Thread t5(philosopher, (void *)5U);
icserny 0:1424c0020312 76 philosopher((void *)1U);
icserny 0:1424c0020312 77 }