Java 多线程学习总结6

                                                        哲学家进餐问题

 

http://users.rcn.com/ziring/java.html牛人网址，原版

 

由于这个问题比较复杂，本人也没细细分析，在网上搜出一个正确的解答，还有一些论文，给大家学习。

package Power.Thread.jincan2;

import java.applet.*;
import java.awt.*;
import java.awt.event.*;
import java.util.*;

/**
 * A simple graphical applet to demonstrate a multi-thread solution
 * to the N dining philosophers problem.
 */

public class DiningApplet extends Applet 
    implements Observer, ActionListener, ItemListener {
    // GUI member variables
    DiningCanvas picture;
    TextArea  logarea;
    Label     legend;
    Label     caption;
    Label     status;
    Checkbox  fastBox;
    TextField counterField;
    Button    startButton;
    Polygon   chopstickPics[];
    Point     philPics[];
    double    rad, philrad, stickrad;
    int       runningthreads;
    boolean   eatfast;

    // Constants - change these to adjust the simulation
    public static final int BASIC_DELAY = 2000;
    public static final int BASIC_APPETITE = 4;
    public static final int DEFAULT_PHILOSOPHERS = 5;

    // functional members, don't mess with these
    int count;
    Philosopher diners[];
    Utensil chopsticks[];

    public void init() {
	count = DEFAULT_PHILOSOPHERS;
	diners = null;
	chopsticks = null;

	// GUI stuff
	setLayout(new GridLayout(2,1));
	picture = new DiningCanvas();
	add(picture);

	Panel bottompanel = new Panel();
	bottompanel.setLayout(new BorderLayout());

	logarea = new TextArea();
	bottompanel.add("Center", logarea);

	Panel controlpanel = new Panel();
	legend = new Label("Legend: Blue=thinking, Yellow=hungry, Green=eating, Gray=done", Label.CENTER);
	legend.setBackground(Color.pink);
	caption = new Label("Philosophers:", Label.RIGHT);
	counterField = new TextField("" + count, 3);
	startButton = new Button("START");
	fastBox = new Checkbox("Slow  ", false);
	status = new Label("                          Initializing", Label.RIGHT);
	startButton.addActionListener(this);
	fastBox.addItemListener(this);
	controlpanel.add(caption);
	controlpanel.add(counterField);
	controlpanel.add(startButton);
	controlpanel.add(fastBox);
	controlpanel.add(status);
	bottompanel.add("North",legend);
	bottompanel.add("South", controlpanel);
	add(bottompanel);
	runningthreads = 0;
    }

    public void start() {
	status.setText("Click on START to start");
    }

    public void beginSimulation() {
	int i;

	if (runningthreads > 0) {
	    logarea.append("Aborting simulation before completion.\n");
	    for(i = 0; i < diners.length; i++) {
		diners[i].stop();
	    }
	    runningthreads = 0;
	}
	picture.clear();
	String cntString = counterField.getText();
	try {
	    count = Integer.parseInt(cntString); 
	}
	catch (NumberFormatException nfe) {
	    count = DEFAULT_PHILOSOPHERS;
	    counterField.setText("" + count);
	}
	logarea.append("\nBeginning simulation with " + count + " philosophers\n");

	synchronized (picture) {
	    diners = new Philosopher[count];
	    chopsticks = new Utensil[count];
	}

	Dimension psize = picture.getSize();
	Point center = new Point(psize.width / 2, psize.height / 2);
	rad = ((psize.width < psize.height)?
	       ((psize.width * 4)/5):((psize.height * 4) / 5)) / 2.0;
	philrad = (rad/count) * 2.1;
	stickrad = rad - philrad;
	philPics = new Point[count];
	int csx[] = new int[4];
	int csy[] = new int[4];
	chopstickPics = new Polygon[count];
	double phi;
	double div = (2 * Math.PI)/(count * 2);
	double swdiv = Math.PI / 90;
	int c;
	for(c = 0, phi = 0.0; c < count; c++, phi += div) {
	    philPics[c] = new Point((int)(rad * Math.sin(phi)) + center.x,
				    (int)(rad * Math.cos(phi)) + center.y);
	    phi += div;
	    csx[0] = (int)(rad * Math.sin(phi)) + center.x;
	    csy[0] = (int)(rad * Math.cos(phi)) + center.y;
	    csx[1] = (int)(stickrad * Math.sin(phi)) + center.x;
	    csy[1] = (int)(stickrad * Math.cos(phi)) + center.y;
	    csx[2] = (int)(stickrad * Math.sin(phi + swdiv)) + center.x;
	    csy[2] = (int)(stickrad * Math.cos(phi + swdiv)) + center.y;
	    csx[3] = (int)(rad * Math.sin(phi + swdiv)) + center.x;
	    csy[3] = (int)(rad * Math.cos(phi + swdiv)) + center.y;
	    chopstickPics[(c + 1) % count] = new Polygon(csx,csy,4);
	}

	for(i = 0; i < count; i++) {
	    chopsticks[i] = new Utensil("Chopstick " + i, chopstickPics[i]);
	    chopsticks[i].addObserver(picture);
	}

	for(i = 0; i < count; i++) {
	    diners[i] = new Philosopher("Diner " + i, 
					chopsticks[i],
					chopsticks[(i + 1) % count],
					philPics[i]);
	    diners[i].setEatFast(eatfast);
	    diners[i].addObserver(this);
	    diners[i].addObserver(picture);
	}
	for(runningthreads = 0; runningthreads < count; runningthreads++) {
	    diners[runningthreads].start();
	}
	picture.repaint();
	status.setText("Simulated philosophers: " + count);
    }

    public void actionPerformed(ActionEvent evt) {
	beginSimulation();
    }
    public void itemStateChanged(ItemEvent evt) {
	eatfast = (!(fastBox.getState()));
	if (diners != null) synchronized (this) {
	    for(int i = 0; i < count; i++) {
		diners[i].setEatFast(eatfast);
	    }
	}
	return;
    }

    public void stop() {
	if (runningthreads > 0) {
	    for(int i = 0; i < diners.length; i++) {
		diners[i].stop();
	    }
	    runningthreads = 0;
	}
	return;
    }

    public void update(Observable obj, Object r) {
	if (r instanceof String) synchronized(this) {
	    logarea.append("\n");
	    logarea.append(r.toString());
	    if (obj instanceof Philosopher) {
		Philosopher p = (Philosopher)obj;
		if (p.status == Philosopher.STATUS_DONE) {
		    runningthreads--;
		}
		if (runningthreads <= 0) {
		    status.setText("Simulation done.");
		}
	    }
	}
	return;
    }

    class DiningCanvas extends Canvas implements Observer {
	Color bg;
	Color statColors[];
	Color stickColor;
	Color textColor;

	public DiningCanvas() {
	    bg = Color.pink;
	    setBackground(bg);
	    stickColor = new Color(0x33, 0x66, 0x33);
	    textColor = Color.black;
	    statColors = new Color[8];
	    statColors[Philosopher.STATUS_DONE] = Color.darkGray;
	    statColors[Philosopher.STATUS_THINKING] = Color.blue;
	    statColors[Philosopher.STATUS_GRABBING] = Color.yellow;
	    statColors[Philosopher.STATUS_EATING] = Color.green;

	}

	public void clear() {
	    Graphics g = getGraphics();
	    g.setColor(bg);
	    Dimension d = getSize();
	    g.fillRect(0, 0, d.width, d.height);
	}

	public void paintItem(Object o, Graphics g) {
	    if (o instanceof Utensil) {
		Utensil u = (Utensil)o;
		g.setColor((u.isAvailable())?(stickColor):(bg));
		g.fillPolygon((Polygon)(u.observerRef));
	    }
	    else if (o instanceof Philosopher) {
		Philosopher p = (Philosopher)o;
		g.setColor(statColors[p.status]);
		Point pp = (Point)(p.observerRef);
		int pr = (int)philrad;
		g.fillOval(pp.x - ((int)(pr/2)),
			   pp.y - ((int)(pr/2)),
			   pr, pr);
		g.setColor(textColor);
		g.drawOval(pp.x - ((int)(pr/2)),
			   pp.y - ((int)(pr/2)),
			   pr, pr);
		// paintItem(p.sticks[0], g);
		// paintItem(p.sticks[1], g);
	    }
	    return;
	}

	public void paint(Graphics g) {
	    int i;
	    Utensil u;
	    Philosopher p;
	    if (diners != null && diners.length > 1) synchronized (this) {
		for(i = 0; i < count; i++) {
		    u = chopsticks[i];
		    paintItem(u,g);
		}
		for(i = 0; i < count; i++) {
		    p = diners[i];
		    paintItem(p,g);
		}
	    }
	    return;
	}

	public void update(Observable obj, Object r) {
	    if (!(r instanceof String))
		paintItem(obj, getGraphics());
	}
		
    }

}

 

 

package Power.Thread.jincan2;

import java.util.*;

public class Utensil extends Observable {
    String name;
    private boolean inuse;
    public Object observerRef;

    public Utensil(String n, Object r) {
	name = n;
	inuse = false;
	observerRef = r; 
    }
    public synchronized boolean isAvailable() { return !inuse; }
    public synchronized void pick_up() { 
    	System.out.println("qu na@@@@@@@"+Thread.currentThread());
	inuse = true; 
	setChanged();
	notifyObservers(observerRef);
    }
    public synchronized void put_down() { 
	inuse = false; 
	// when chopstick is dropped, do a notify
	System.out.println("qu fang#####"+Thread.currentThread());
	notify();
	setChanged();
	notifyObservers(observerRef);
    }
}

 

package Power.Thread.jincan2;

import java.util.*;

public class Philosopher extends Observable implements Runnable {
    public static final int STATUS_DONE = 0;
    public static final int STATUS_THINKING = 1;
    public static final int STATUS_GRABBING = 2;
    public static final int STATUS_EATING = 3;

    String name;
    int status;
    Utensil sticks[];
    Object observerRef;
    int appetite;
    int eaten;
    Thread myThread;
    boolean abort = false;
    boolean eatfast = false;

    public Philosopher(String n, Utensil r, Utensil l, Object ref) {
	name = n;
	sticks = new Utensil[2];
	sticks[0] = l;
	sticks[1] = r;
	eaten = 0;
	appetite = rand(DiningApplet.BASIC_APPETITE - 2, DiningApplet.BASIC_APPETITE + 2);
	observerRef = ref;
	myThread = new Thread(this, n);
	status = STATUS_THINKING;
    }

    int rand(int min, int max) {
	return (min + (int)(Math.random() * (max - min)));
    }
    void sleepFor(int ms) {
	try { Thread.sleep(ms * (eatfast?1:6)); } 
	catch (InterruptedException e) { abort = true; }
    }
    public void setEatFast(boolean e) { eatfast = e; }

    public synchronized void start() {
	myThread.start();
    }
    public synchronized void stop() {
	abort = true;
	myThread.interrupt();
    }

    public void run() {
	message("arrived at table with appetite of " + appetite+  "    "+Thread.currentThread());
	int s1, s2;

	while(eaten < appetite && !abort) {
	    // think for a while..
	    status = STATUS_THINKING;
	    setChanged(); notifyObservers(observerRef);
	    message("thinking...");
	  //  sleepFor(rand(0,4) * DiningApplet.BASIC_DELAY);
	    message("trying to eat...");
		
		
	    // okay, philosopher has decided to have a bite
	    status = STATUS_GRABBING;
	    boolean gotboth = false;
	    setChanged(); notifyObservers(observerRef);
	    while(!gotboth && !abort) {
		// decide on a stick to acquire first, at random
		s1 = rand(0,2);
		s2 = ((s1 == 0)?(1):(0));
       
		// Attempt to acquire first stick.
		synchronized (sticks[s1]) {
		    while(!(sticks[s1].isAvailable())) {
			try {
			    sticks[s1].wait();
			} catch (Exception e) { 
			    if (abort) return;
			}
			// okay, if we get here then we own
			// stick 1
		    }
		    // okay, first stick acquired
		    sticks[s1].pick_up();
		}

		// Attempt to acquire second stick, but give up
		// immediately if we can't get it.
		synchronized (sticks[s2]) {
		    if (sticks[s2].isAvailable()) {
			sticks[s2].pick_up();
			gotboth = true;
		    }
		}
		// If we didn't manage to get second stick,
		// then put first one down.
		if (!gotboth) {
		    sticks[s1].put_down();
		}
	    }
	    if (abort) return;

	    // If we get here, we've got both sticks, so we
	    // can eat for a while.
	    status = STATUS_EATING;
	    message("Got both chopsticks, EATING!");
	    setChanged(); notifyObservers(observerRef);
	 //   sleepFor(rand(2,5) * DiningApplet.BASIC_DELAY);
	  //  eaten += 1;
	    if (abort) return;

	    // Okay, we're done eating for now, put both
	    // sticks down.
	    message("done eating for the moment...");
	    sticks[0].put_down();
	    sticks[1].put_down();
	    if (abort) return;
	}
	status = STATUS_DONE;
	setChanged(); notifyObservers(observerRef);
	message("all full, leaving the table.");
    }

    public void message(String s) {
	setChanged();
	notifyObservers(myThread.getName() + ": " + s);
    }

}

   从这个代码分析，我猜测不能从理论上保证排除“饥饿”这种现象，但是这种现象是极其罕见的，也是不可能出现的。

 

排除饥饿的原理就是随机地选择左右哪个方向为第一手。