java
Questions
- What is the difference between deadlock and starvation?
- Explain in a sentence or two how you prevented deadlock in your implementation.
- In a sentence or two, explain, how do you start a thread in Java?
- How do threads terminate in Java?
- What is a monitor? Explain in a couple of sentences.
- How does Java use monitors? Explain in two or three sentences.
- How does this problem illustrate the use of a finite state graph?
Description
The dining philosopher problem consists of five philosophers that spend their entire life either thinking or eating. There are five states that a philosopher can be in. These are thinking, eating, hungry, famished, or starved. After a random time period of thinking, a philosopher will try to pick up two chopsticks (on the right and left of him). If he succeeds, he goes into the eating state. If he fails (because other philosophers have one (or both) of the chopsticks), he waits and then tries again. After a certain number of waits and unsuccessful tries (your choice of how many), he switches to the hungry state. If he waits and unsuccessfully tries a number of more times, he switches to the famished state. Finally, if he still cannot get a pair of chopsticks, he'll die and go to the starve state. After eating, a philosopher releases the two chopsticks and goes back to thinking. The philosophers are greedy; they will never release a chopstick that they pick up if they are waiting to eat.
To program this problem, we need three classes. These are: (i) The main class that extends Applet, (ii) the philosopher class, and (iii) the chopstick class. The philosopher class needs two methods. The first draws the philosopher in an appropriate place on the display; the second changes his current status according to rules described above. The chopstick class needs three methods: pick up a chopstick for a philosopher; release the chopstick after eating, and drawing the chopstick.
I've provided the two draw methods below to insert into the philosopher and chopstick class. Your job is to complete the philosopher and chopstick classes, and to write the methods for the applet.
The draw() method that I provided that relates to the philosopher class, the referenced constants represent the various philosopher states and are declared as integers. The variable location is an instance of Point that is to be declared as ainstance variables. Similarly, the current state is maintained in an integer called status. Instance variables need to be referenced and instantiated for each color that is used. SIZE is a constant that I've set to 50 in my implementation.
The draw method for the chopstick class (at the bottom of this document) references a integer variable called available to indicate which philosopher has the chopstick (or a value of -1 indicates to that the chopstick is available). The chopstick class also needs a location instance variable that indicates where on the display the chopstick should be drawn. The chopstick class location variable is an instance of a Rectangle object (startX, startY, dX, dY). Note that the ending X and Y values is startX+dX and startY+dY respectively.
The method fatLine should be implemented in your main applet class since methods in both the philosopher and the chopstick classes use it.
The functionality of the main applet class includes code for the following: (i) Instantiate five chopsticks at appropriate locations on the display, (ii) Instantiate five philosophers at appropriate locations on the display, (iii) Set the applet size, (iv) Paint the display with the chopsticks and philosophers in their current state, (v) Start one thread per philosopher, (vi) Each thread Delays a random amount of time and then calls the philosopher's change status method until the philosopher dies. The applet methods that you will have to write are init(), paint(), update(), start(), and run().
Remember to specifiy implements Runnable on the signature line of your applet. Also, watch out for deadlock and thread conflicts. You'll have to use the synchronized keyword to protect your critical sections and to prevent deadlock.
A sample display of my running applet is shown below. It's a good idea to draw the chopsticks and philosophers with graph paper so you can position them correctly on the display.
10.Answer the synthesis questions in an rtf or doc file (answers.rtf or answers.doc). Type your name and the lab number on this file and include the questions with the answers.
Sample Output
Drawing methods
public static void fatLine(Graphics page, Rectangle r, Dimension d)
{ int[] x = {r.x, r.x+d.width, r.x+r.width+d.width, r.x+r.width};
int[] y = {r.y, r.y, r.y+r.height+d.width, r.y+r.height+d.width};
page.fillPolygon(x, y, 4);
}
public void draw(Graphics page)
{ int startX, startY, height, width;
Rectangle spot;
// Draw face.
page.setColor(faceColor);
page.fillOval(location.x, location.y, SIZE, SIZE );
// Draw eyes.
startX = location.x + SIZE/5;
startY = location.y + SIZE/5;
width = SIZE/5;
height = SIZE/5;
page.setColor(eyeColor);
page.fillOval(startX, startY, width, height );
startX = location.x + 3*SIZE/5;
page.fillOval(startX, startY, width, height);
// Draw nose.
startX = location.x + SIZE/2-3;
startY = location.y + SIZE/5+5;
height = 10;
width = 6;
page.setColor(noseColor);
page.fillRoundRect(startX, startY,width,height,3,3);
// Draw mouth.
startX = location.x + SIZE/5;
startY = location.y + 3 * SIZE /5;
page.setColor(mouthColor);
height = 3;
if (status == HUNGRY) height = 5;
if (status == FAMISHED) height = 8;
page.fillRoundRect(startX, startY, 3*SIZE/5, height, 3, 3);
switch (status)
{ case EAT:
page.setColor(YourAppletClassName.chopStickColor);
startX = location.x + 2*SIZE/5;
startY = location.y + 7*SIZE/10;
width = -10;
height = 30;
spot = new Rectangle(startX,startY,width,height);
YourAppletClassName.fatLine(page,spot,new Dimension(3,3));
startX = location.x + 3*SIZE /5;
width = 10;
height = 30;
spot = new Rectangle(startX,startY,width,height);
YourAppletClassName.fatLine(page,spot,new Dimension(3,3));
case THINK:
startX = location.x + SIZE/4; // Draw pupils.
startY = location.y + SIZE/4;
width = SIZE/10;
height = SIZE/10;
page.setColor(pupilColor);
page.fillOval(startX, startY, width, height );
startX = location.x + 2*SIZE/5+SIZE/4;
page.fillOval(startX, startY, width, height );
break;
case STARVE:
startX = location.x + SIZE/5; // Draw x for pupils.
startY = location.y + SIZE/5;
width = SIZE/5;
height = SIZE/5;
page.setColor(pupilColor);
page.drawLine(startX,startY,startX+width,startY+height);
page.drawLine(startX+width,startY,startX,startY+height);
startX = location.x + 3*SIZE/5;
page.drawLine(startX,startY,startX+width,startY+height);
page.drawLine(startX+width,startY,startX,startY+height);
break;
case HUNGRY:
startX = location.x + SIZE/4; // Draw pupils.
startY = location.y + 3*SIZE/10;
width = SIZE/7;
height = SIZE/7;
page.setColor(pupilColor);
page.fillOval(startX, startY, width, height );
startX = location.x + 2*SIZE/5+SIZE/4;
page.fillOval(startX, startY, width, height );
break;
case FAMISHED:
startX = location.x + 5*SIZE/16; // Draw pupils.
startY = location.y + 4*SIZE/24;
width = SIZE/7;
height = SIZE/7;
page.setColor(pupilColor);
page.fillOval(startX, startY, width, height );
startX = location.x + 6*SIZE/16+SIZE/4;
page.fillOval(startX, startY, width, height );
break;
default:
System.out.println("Illegal philosopher status");
System.exit(0);
}
}
public void draw(Graphics page)
{ if (available<0)
{ page.setColor(YourAppletClassName.chopStickColor);
YourAppletClassName.fatLine(page, location, new Dimension(5,5));
} }