main.cpp

00001 /** 10_rtos_dpp_mutex
00002  * The dining philosophers problem is invented by E. W. Dijkstra. 
00003  * Imagine that five philosophers sitting around a round table with five chairs,
00004  * who spend their lives alternating between thinking and eating 
00005  * from a large bowl of rice at random intervals. 
00006  * However, there are only five chopsticks available at the right hand and 
00007  * left hand of each philosopher. Each philosopher thinks. When he gets hungry, 
00008  * he picks up the two chopsticks that are closest to him. If a philosopher can pick 
00009  * up both chopsticks, he eats for a while. After a philosopher finishes eating, 
00010  * he puts down the chopsticks and starts to think again. 
00011  *
00012  * Since the chopsticks are shared between the philosophers, access to the chopsticks 
00013  * must be protected, but if care isn't taken, concurrency problems arise. Most notably, 
00014  * starvation via deadlock can occur: if each philosopher picks up a chopstick as soon 
00015  * as it is available and waits indefinitely for the other, eventually they will all end 
00016  * up holding only one chopstick with no chance of acquiring another.
00017  *
00018  * In this solution we instruct our philosophers to cooperate: to put down the
00019  * acquired chopstick, if the second is not available, and wait for a (short) random interval.
00020  * This is the same techniqe used by the network cards when they detected packet collision. 
00021  *
00022  * The five chopsticks are represented by five mutexes.
00023  * The philosophers are represented as threads.
00024  *
00025  * Hardware requirements:
00026  *  - FRDM-KL25Z board
00027  */
00028 #include "mbed.h"
00029 #include "rtos.h"
00030 
00031 Mutex stdio_mutex;
00032 Mutex chopstick[5];                                 //Array of mutexes representing the 5 chopsticks
00033 
00034 void notify(int num, int state)
00035 {
00036     stdio_mutex.lock();
00037     if(state) {
00038         printf("Philospher %d is EATING \n\r", num);
00039     } 
00040     else {
00041         printf("Philospher %d is thinking \n\r", num); 
00042     }               
00043     stdio_mutex.unlock();
00044 }
00045 
00046 void philosopher(void const *args)
00047 {
00048     while (true) {
00049         if(chopstick[(int)args-1].trylock()) {
00050             if(chopstick[(int)args%5].trylock()) {
00051                 notify((int)args,1);                //Start EATING
00052                 Thread::wait(1000+rand()%1000);
00053                 chopstick[(int)args%5].unlock();      //Release chopsticks
00054                 chopstick[(int)args-1].unlock();
00055                 notify((int)args,0);                //Start Thinking                
00056                 Thread::wait(2000+rand()%2000);     //Get's hungry after this time...
00057             } 
00058             else {
00059                 chopstick[(int)args-1].unlock();
00060                 Thread::wait(100+rand()%100);       //Wait for random time if failed
00061             }
00062         } 
00063         else {
00064             Thread::wait(100+rand()%100);           //Wait for random time if failed
00065         }
00066 
00067     }
00068 }
00069 
00070 int main()
00071 {
00072     Thread t2(philosopher, (void *)2U);
00073     Thread t3(philosopher, (void *)3U);
00074     Thread t4(philosopher, (void *)4U);
00075     Thread t5(philosopher, (void *)5U);        
00076     philosopher((void *)1U);
00077 }