Next: The event class Up: The event-based approach Previous: The event-based approach

### The Dining Philosophers

The problem is as follows. Five philosophers sit around a table with five chopsticks in between. They think and if they are hungry and if two chopsticks are available, they eat. If a philosopher gets hungry and s/he can not acquire a chopstick, the philosopher waits until s/he can. The philosopher does not think, if s/he is waiting or eating. We are interested in the fraction of the time, that a philosopher actually thinks.

To model this problem, three events can be identified, eat, think and await. The corresponding classes are derived from the class event. Furthermore we need a chopstick for every philosopher. These are represented as a resource. The thinking times are gathered in an instance of the class histogram and the generator takes care of the variations in the time needed to think and eat.

We develop this program in the following steps. First, the library is included as sim.h. The declarations of the global variables and constants follow after that. The time unit in this simulation is an hour, so a philosopher has a mean eating time of two hours and a mean thinking time of five hours. The duration of the simulation is a year. Finally, we define the various events.

```   #include <sim/sim.h>

const double duration = 52*7*24.0;       // a year
const int number = 5;                    // philosophers
const int eatingtime = 2;                // 2 hours
const int thinkingtime = 5;              // 5 hours
simulation* sim;
generator* g;
resource* chopstick[number];
histogram* thinking;

class eat : public event
{
public :
eat(int i);                 // constructor, taking identity
virtual int operator()();   // function operator
private :
int id;                     // identity of the philosopher
};

class think : public event
{
public :
think(int i);               // constructor, taking identity
virtual int operator()();   // function operator
private :
int id;                     // identity of the philosopher
};

class await : public event
{
public :
await(int i);               // constructor, taking identity
virtual int operator()();   // function operator
private :
int id;                     // identity of the philosopher
};
```

Next, we implement the various events. An event is given its functionality by deriving it from the class event and overriding its function operator.

The logic of the eat event is that the philosopher eats for a random time, exponentially distributed with a mean eating time. So, we first determine the actual eating time and schedule a think event to be activated after this eating time. The eat event can be terminated.

```   eat::eat(int i) : event()
{
id = i;                                  // set identity
}

int eat::operator()()
{
double t = g -> exponential(eatingtime); // determine eating time
think* th = new think(id);               // create a thinking event
sim -> schedule(th,t);                   // schedule thinking
sim -> terminate(this);                  // terminate this eat event
return OK;
}
```

If a philosopher starts to think, the philosopher first releases both chopsticks. The thinking time is determined and a sample is made of the percentage of this thinking time towards the total time. An await event is scheduled and the think event is terminated.

```   think::think(int i) : event()
{
id = i;                                // set identity
}

int think::operator()()
{
chopstick[id] -> release();            // release left chopstick
chopstick[(id+1)%number] -> release(); // release right
double t = g -> exponential(thinkingtime);    // determine thinking time
thinking -> sample(id,t/duration*100); // add a sample (%)
await* aw = new await(id);             // create await event
sim -> schedule(aw,t);                 // schedule waiting
sim -> terminate(this);                // terminate thinking
return OK;
}
```

The await event acquires the left and right chopstick and schedules an eat event immediately, if both chopsticks are available. The await event is passivated as it could be on the conditional list. If no chopsticks are available, the await event stays on the conditional list or, if it was not conditional as is the case the first time it is activated, it is added to the conditional list.

```   await::await(int i) : event()
{
id = i;                                 // set identity
}

int await::operator()()
{
if ( (chopstick[id] -> available()) &&      // available ?
(chopstick[(id+1)%number] -> available()) )
{
chopstick[id] -> acquire();               // acquire left
chopstick[(id+1)%number] -> acquire();    // acquire right
eat* e = new eat(id);
sim -> passivate(this);      // extract from conditional list
sim -> schedule(e,0);        // schedule eat event immediately
sim -> terminate(this);      // terminate await event
}
else if (!conditional())       // not on conditional list
sim -> hold(this);           // add to conditional list
return OK;
}
```

The following step is the definition and implementation of an application, that is derived from session. The application::main function first creates the simulation object. Furthermore, a frequency histogram and five resources that represent the chopsticks are created. The histogram is created with its widget path and with its (default) options. Afterwards it is packed to the display. The simulation starts with all philosophers waiting and runs for a year (52*7*24 hours). After running the simulation, the resulting histogram is printed.

```   class application : public session
{
public :
application(int argc,char** argv);
int main();                        // must be defined
};

application::application(int argc,char** argv) : session(argc,argv,"philosophers")
{}

int application::main()   // tk is an instance variable of session
{
sim = new simulation();
g = new generator(80,20,19);          // gets three seeds
thinking = new histogram(".h","-columns 5 -title thinkingtime");
tk -> pack(thinking);                 // add to display;
tk -> update();                       // update display;
for (int i=0;i<number;i++)
{
chopstick[i] = new resource(1);     // create chopsticks
await* aw = new await(i);           // schedule each
sim -> schedule(aw,0);              // philosopher waiting
}
sim -> run(duration);                 // run for duration time units
cout << (*thinking) << endl;          // print resulting histogram
delete thinking;
delete sim;
return 0;                             // successful termination
}
```

The main function then creates and starts the application.

```   main(int argc,char** argv)
{
session* s = new application(argc,argv);        // create the session
return s -> run();                              // start the session
}
```

Next: The event class Up: The event-based approach Previous: The event-based approach

A Eliens
Tue Oct 31 09:27:21 MET 1995