168 lines
4.8 KiB
Plaintext
168 lines
4.8 KiB
Plaintext
|
//**************************************************************//
|
||
|
|
// //
|
||
|
|
// Program: Dining Philosopher Problem //
|
||
|
|
// Filename: dine.cm //
|
||
|
|
// Original author: Neil Bergmann //
|
||
|
|
// Modification: Tracy Camp //
|
||
|
|
// //
|
||
|
|
// This program implements the dining philosopher problem. //
|
||
|
|
// This version occasionally results in deadlock. //
|
||
|
|
// //
|
||
|
|
//**************************************************************//
|
||
|
|
|
||
|
|
|
||
|
|
//**************************************************************//
|
||
|
|
// GLOBAL DECLARATIONS //
|
||
|
|
|
||
|
|
const int number= 5; //number of diners//
|
||
|
|
|
||
|
|
const int true = 1; // logical true
|
||
|
|
const int false= 0; // logical false
|
||
|
|
const int none = -1; // indicates nobody has a fork
|
||
|
|
|
||
|
|
semaphore fork[number];
|
||
|
|
//fork provides mutual exclusion on forks - only one diner can //
|
||
|
|
//grab a fork at a time//
|
||
|
|
|
||
|
|
int hasfork[number];
|
||
|
|
//hasfork keeps a record of which diner currently has a particular fork//
|
||
|
|
|
||
|
|
int dinerseaten[number];
|
||
|
|
//records which diners have eaten so far//
|
||
|
|
|
||
|
|
//YOU CAN ADD DECLARATIONS HERE//
|
||
|
|
|
||
|
|
//**************************************************************//
|
||
|
|
int left (int diner)
|
||
|
|
//returns index of fork to the left of 'diner'//
|
||
|
|
//DO NOT CHANGE THIS FUNCTION//
|
||
|
|
{
|
||
|
|
return diner;
|
||
|
|
} //left//
|
||
|
|
|
||
|
|
int right (int diner)
|
||
|
|
//returns index of fork to the right of 'diner'//
|
||
|
|
//DO NOT CHANGE THIS FUNCTION//
|
||
|
|
{
|
||
|
|
if (diner < number-1 )
|
||
|
|
return (diner+1);
|
||
|
|
else return 0; //fork to right of last diner is #0//
|
||
|
|
} //right//
|
||
|
|
|
||
|
|
|
||
|
|
//**************************************************************//
|
||
|
|
void initialize ()
|
||
|
|
|
||
|
|
//YOU CAN ADD ANY INITIALIZATIONS HERE//
|
||
|
|
{
|
||
|
|
int count;
|
||
|
|
for (count=0; count<number; count++)
|
||
|
|
{
|
||
|
|
dinerseaten[count] = false; //no diners have eaten yet//
|
||
|
|
hasfork[count] = none; //nobody has forks yet//
|
||
|
|
initialsem(fork[count],1); //only one diner per fork at once//
|
||
|
|
|
||
|
|
}
|
||
|
|
} //initialize//
|
||
|
|
|
||
|
|
|
||
|
|
|
||
|
|
//**************************************************************//
|
||
|
|
void takefork(int forknum, int diner)
|
||
|
|
//diner tries to take a fork, blocking until it is available//
|
||
|
|
//mark which diner has the fork//
|
||
|
|
//DO NOT CHANGE THIS PROCEDURE//
|
||
|
|
|
||
|
|
{
|
||
|
|
p(fork[forknum]);
|
||
|
|
hasfork[forknum] = diner;
|
||
|
|
} //takefork//
|
||
|
|
|
||
|
|
//**************************************************************//
|
||
|
|
void replacefork(int forknum, int diner)
|
||
|
|
//diner replaces a fork after eating//
|
||
|
|
//DO NOT CHANGE THIS PROCEDURE//
|
||
|
|
|
||
|
|
{
|
||
|
|
//check if this diner really had this fork, if not complain//
|
||
|
|
if (hasfork[forknum] == diner)
|
||
|
|
{
|
||
|
|
hasfork[forknum] = none; //nobody has this fork now//
|
||
|
|
v(fork[forknum]); //signal that fork is available//
|
||
|
|
} else
|
||
|
|
cout << "ERROR: Diner # " << diner <<
|
||
|
|
" did not have fork number" << forknum << endl;
|
||
|
|
} //replacefork//
|
||
|
|
|
||
|
|
//**************************************************************//
|
||
|
|
void eat(int diner)
|
||
|
|
// Checks that diner has correct forks to left and right //
|
||
|
|
// Prints out message and sets 'dinerseaten' flag //
|
||
|
|
// DO NOT CHANGE THIS PROGRAM EXCEPT TO CHANGE OUTPUT //
|
||
|
|
|
||
|
|
{
|
||
|
|
//now check diner has correct forks, and let him or her eat//
|
||
|
|
if ((hasfork[left(diner)] == diner) &&
|
||
|
|
(hasfork[right(diner)] == diner) )
|
||
|
|
{
|
||
|
|
cout << "Diner # " << diner << "has eaten "<< endl;
|
||
|
|
dinerseaten[diner] = true;
|
||
|
|
} else
|
||
|
|
cout << "Diner # " << diner << " did not have correct forks" << endl;
|
||
|
|
} //eat//
|
||
|
|
|
||
|
|
//**************************************************************//
|
||
|
|
void success ()
|
||
|
|
//This procedure checks that all diners have eaten//
|
||
|
|
// DO NOT CHANGE THIS PROGRAM EXCEPT TO CHANGE OUTPUT //
|
||
|
|
{
|
||
|
|
int alldone;
|
||
|
|
int count;
|
||
|
|
|
||
|
|
alldone = true;
|
||
|
|
for (count=0; count<number; count++)
|
||
|
|
alldone = alldone && dinerseaten[count];
|
||
|
|
if (alldone)
|
||
|
|
cout << "SUCCESS" << endl;
|
||
|
|
else
|
||
|
|
cout << "FAILURE" << endl;
|
||
|
|
|
||
|
|
} //success//
|
||
|
|
|
||
|
|
|
||
|
|
//**************************************************************//
|
||
|
|
void dine(int diner)
|
||
|
|
//This procedure is started concurrently for each diner //
|
||
|
|
//This version of program occaisionally deadlocks //
|
||
|
|
|
||
|
|
{
|
||
|
|
|
||
|
|
takefork (left(diner), diner);
|
||
|
|
takefork(right(diner), diner);
|
||
|
|
eat(diner);
|
||
|
|
replacefork(left(diner), diner);
|
||
|
|
replacefork(right(diner), diner);
|
||
|
|
} //dine//
|
||
|
|
|
||
|
|
|
||
|
|
//**************************************************************//
|
||
|
|
// main program //
|
||
|
|
// DO NOT CHANGE THIS PROGRAM EXCEPT TO CHANGE NUMBER OF DINERS //
|
||
|
|
|
||
|
|
main ()
|
||
|
|
{
|
||
|
|
initialize();
|
||
|
|
cobegin
|
||
|
|
{ dine(0);
|
||
|
|
dine(1);
|
||
|
|
dine(2);
|
||
|
|
dine(3);
|
||
|
|
dine(number-1);
|
||
|
|
//add/delete more lines if number of diners changes...//
|
||
|
|
//note baci can only handle about 10 threads at a time//
|
||
|
|
}
|
||
|
|
success();
|
||
|
|
|
||
|
|
}
|
||
|
|
|