hobbielektronika
/
10_rtos_dpp_mutex
Dining Philosophers Problem solved by the help of mutexes
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?
User | Revision | Line number | New 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 | } |