Cluster Praktikum

Blatt 8

Aufgabe 8: Queues in Java

Vorbereitungen

• Legen Sie den Ordner classes in ihrem Home-Verzeichnis an.

mkdir ~/classes

• Stellen sie sicher, dass Ihre Shell eine Java 1.4 oder 1.5 virtuelle Maschine findet:

java -version

• Wenn obiges Kommando eine Fehlermeldung ausgibt, fügen Sie folgendes in Ihrem Shell-Initialisierungsskript ~/.tcshrc

  source /ToolMan/Modules/init/tcsh
  module add jdk
  

  oder (falls Sie die Bash als Login-Shell benutzen)

  source /ToolMan/Modules/init/bash
  module add jdk
  

  in die Datei ~/.bashrc ein.
• Loggen Sie sich ggf. aus und wieder ein oder öffnen Sie ein neues Terminalfenster.
• Fügen Sie nun am Ende dieses Shell-Initialiserungsskriptes .tcshrc folgende Zeile an:

  setenv CLASSPATH ${HOME}/classes
  

  bzw. am Ende von ~/.bashrc

  export CLASSPATH=${HOME}/classes
  

Nun können Sie Java-Quelldateien übersetzen:

javac -d ~/classes HelloWorld.java

java HelloWorld

Warteschlange

Es soll eine Warteschlange implementiert werden mit einer festen, bei ihrer Konstruktion anzugebenden Größe. Die Warteschlange kann beliebige Elemente (also Objekte der Klasse Object) aufnehmen. Es gibt je eine Methode zum Einstellen und eine Methode zum Herausnehmen eines Objektes. Beide Methoden sollen blockieren, wenn sie ihre Aufgabe derzeit nicht erfüllen können, weil die Schlange voll bzw. leer ist. Zuerst eingestellte Objekte werden auch zuerst wieder entnommen. Das Einstellen von ungültigen Referenzen (null) ist ausdrücklich erlaubt.

Sie müssen für die Klasse Queue also Methoden mit ungefähr folgenden Signaturen (zuzüglich etwaiger Modifizierer und Deklarationen von geworfenen Ausnahmen) implementieren:

Queue(int size)           /* construct queue of size size */
boolean isFull()          /* true, if queue cannot accept more elements */
boolean isEmoty()         /* true, if no elements queued (anymore) */
void enqueue(Object item) /* add element */
Object dequeue()          /* remove (and return) element */

Hinweis: Benutzen Sie nicht einfach eine der Containerklassen aus java.util, sondern denken Sie sich eine eigene Implementierung aus!!

Die Warteschlange soll in einem Programm mit vier Threads verwendet werden. Zwei Producer-Threads stellen Integer-Werte von 100...199 bzw. 200..299 in die Warteschlange ein, und zwei Consumer-Threads entnehmen diese Werte wieder aus der Schlange und geben sie aus.

Das Programm sieht im Wesentlichen so aus:

package cp.sync;

class Producer implements Runnable {
    Queue queue;
    int min, max;

    public Producer(Queue queue, int min, int max) {
	this.queue = queue;
	this.min = min;
	this.max = max;
    }
    
    public void run() {
	try {
		for (int n = min; n <= max; n++) {
	    		queue.enqueue(new Integer(n));
		}
	} catch (InterruptedException ex){
		return;
	}
    }
}

class Consumer implements Runnable {
    Queue queue;

    public Consumer(Queue queue) {
	this.queue = queue;
    }

    public void run() {
        try{
	    while(true) {
	        Integer i = (Integer) queue.dequeue();
	        System.out.print(i + " ");
	    }
	} catch (InterruptedException ex){
	    return;
	}
    }
}

public class TestQueue {
    public static void main(String[] args) throws Exception {
        Queue queue = new Queue(5);

        // Create and start all threads
        Thread s = new Thread(new Producer(queue, 100, 199));
        Thread t = new Thread(new Producer(queue, 200, 299));
        Thread u = new Thread(new Consumer(queue));
        Thread v = new Thread(new Consumer(queue));

        s.start(); t.start();
        u.start(); v.start();

        // Join the producer threads
        s.join(); t.join();

        // Wait until all entries are consumed from the queue.
        synchronized(queue) {
            while (! queue.isEmpty()) {
                queue.wait();
            }
        }

        // Interrrupt and join the consumer threads.
        u.interrupt(); u.join();
        v.interrupt(); v.join();
    }
}

Kopieren Sie diesen Quelltext in eine Datei TestQueue.java im Ordner cp/sync, den Sie ggf. vorher anlegen. Sie müssen jetzt noch die Warteschlange selbst, d.h. die Klasse Queue in der Datei cp/sync/Queue.java ergänzen.

Das fertige Programm soll nicht blockieren und alle Werte (100..299) ausgeben. Testen Sie dieses für verschiedenen Größen der Warteschlage, insbesondere für eine Schlange, die nur ein Element aufnehmen kann.

Benutzen Sie zur Abgabe der Lösung wie immer den Praktomaten! Am einfachsten ist, es eine ZIP-Datei mit den beiden Quelldateien inklusive Verzeichnisstruktur einzureichen.