# Verkettete Liste



## renek (2. Okt 2008)

Hallo zusammen

Ich habe folgendes Problem. Ich habe mir eine Klasse (buffer) gebastelt, die mir eine einfach verkettete Liste erzeugt. Soweit geht auch noch alles.

Ich lege 2 Listen an ( new buffer() ). Diese 2 Listen übergebe ich 3 Threads. Dem ersten beide Zeiger auf die Listen und den anderen beiden jeweils nur einen Zeiger. Der erste Thread schreibt abwechselnd Daten in einen der beiden Listen. Sobald in einer Liste Daten da sind, holen die entsprechenden Threads die Daten aus der Liste und zeigen sie an. Leider kommt es bei mir vor, das falsche Daten ausgelesen werden.
Wie kann ich sicherstellen, dass immer nur ein Thread auf die Listen zugreift? Bei mir kommt immer ein Error wenn Thread2b auf die Liste zugreifen will.



> E:\testing java>java TextThreadDemo
> Ende TextThreadDemo
> Thread1 in b1 (1/0): test b1
> Thread1 in b2 (0/1): test b2
> ...





```
public class data_test {
	data_test next_data;			// Referenz auf nächstes Objekt

	String command;
    
	
	public data_test () {
		this.next_data = null;
		this.command = "";
	}
}
```


```
class buffer_test {
	data_test first_data;
	data_test last_data;

    volatile int length = 0;
	
	public buffer_test () {
		first_data = null;
		last_data = null;
	}
	
	public synchronized void write_data (data_test daten) {
		if (first_data == null) {
			// Noch kein Element vorhanden
			first_data = daten;
			last_data = daten;
		}
		else {
			last_data.next_data = daten;		// altes letztes Element verketten
			last_data = daten;					// neues letztes Element setzen
    	        }
	        length++;
	}

	public synchronized data_test read_data () {
	   // Erstes Element löschen
	    data_test daten;

		if (first_data != null) {
			// Es ist mind. noch 1 Element in der Kette vorhanden
			daten = first_data;
			if (first_data.next_data == null) {
				// Nur noch 1 Element in der Kette vorhanden
				first_data = null;
				last_data = null;
			}
			else {
				// Es sind noch mehr Elemente in der Kette
				first_data = first_data.next_data;
			}
		    length--;

		    return daten;
		}
	    return null;
	}


    public synchronized int length() {
    	return length;
    }
}
```


```
public class TextThreadDemo {
	public static void main(String args[]) {
		
		TextThread1 output;
		TextThread2a input1;
		TextThread2b input2;
		
		buffer_test buf1 = new buffer_test();
   		buffer_test buf2 = new buffer_test();
		
		output = new TextThread1(buf1,buf2);
		input1 = new TextThread2a(buf1);
                input2 = new TextThread2b(buf2);

		output.start();
		input1.start();
   		input2.start();
		
		System.out.println ("Ende TextThreadDemo");
	}
}
```


```
class TextThread1 extends Thread {
    buffer_test b1,b2;
    data_test daten;
    public String name1 = "test_";
    
    public TextThread1(buffer_test buf1, buffer_test buf2) {
		super("TextThread1");
		b1 = buf1;
	    b2 = buf2;
    }

	public void run() {
	    for(int i = 0; i < 50; i++) {
			try {
				if (i % 2 == 0) {
					daten = new data_test();
				    daten.command = "test b1";
				    
					b1.write_data (daten);
				    System.out.println ("Thread1 in b1 (" + b1.length() + "/" + b2.length() + "): " + daten.command);
			    }
			    else {
			    	daten = new data_test();
				    daten.command = "test b2";
				    
					b2.write_data (daten);
				    System.out.println ("Thread1 in b2 (" + b1.length() + "/" + b2.length() + "): " + daten.command);

			    }
		    }
		    catch (IllegalMonitorStateException e) {
		    	System.out.println ("Fehler(1): b Monitor war besetzt");
		    }
		}
		daten = new data_test();
	    daten.command = "ENDE";
    	b1.write_data (daten);

	    daten = new data_test();
	    daten.command = "ENDE";
    	b2.write_data (daten);

	    System.out.println ("Thread 1 Ende");
	}
}
```


```
class TextThread2a extends Thread {
    String text = "Thread 2";
    buffer_test b;
	data_test daten;
	String com = "";
    
    public TextThread2a(buffer_test buf) {
		super("TextThread2");
		b = buf;
    }
  
	public void run() {
		
		String com = null;

		try {
			daten = b.read_data();
		    if (daten != null) {
		    	com = daten.command;
		    }

	    }
	    catch (IllegalMonitorStateException e) {
			System.out.println ("Fehler(2): b Monitor war besetzt");
		}
		while (com != "ENDE") {
			try {
				//b.show_data();			
				daten = b.read_data();
    		    if (daten != null) {
			    	com = daten.command;
				    if (com.equals("test b1")) {
					    System.out.println ("Thread2a Länge: " + b.length() + " --- Daten: " + com);
				    }
				    else {
				    	System.out.println ("Thread2a: (" + com + ") !!!!!!!!!!!!!!!!!!!! ERROR !!!!!!!!!!!!!!!!!!!!!!!");
				    }
			    }
			    else {
			    	com = "";
			    }

			try {
				sleep(100);
			}
				catch(InterruptedException e) {
			}
			    
		    }
		    catch (IllegalMonitorStateException e) {
		    	System.out.println ("Fehler(2): b Monitor war besetzt");
		    }
			

		}	// Ende while

		System.out.println("Thread 2a Ende");
	}
}
```


```
class TextThread2b extends Thread {
    String text = "Thread 2";
    buffer_test b;
	data_test daten;
	String com = "";
    
    public TextThread2b(buffer_test buf) {
		super("TextThread2");
		b = buf;
    }
  
	public void run() {
		
		String com = null;

		try {
			daten = b.read_data();
		    if (daten != null) {
		    	com = daten.command;
		    }

	    }
	    catch (IllegalMonitorStateException e) {
			System.out.println ("Fehler(2): b Monitor war besetzt");
		}
		while (com != "ENDE") {
			try {
				//b.show_data();			
				daten = b.read_data();
    		    if (daten != null) {
					if (com.equals("test b2")) {
					    System.out.println ("Thread2b Länge: " + b.length() + " --- Daten: " + com);
				    }
				    else {
				    	System.out.println ("Thread2b: (" + com + ") !!!!!!!!!!!!!!!!!!!! ERROR !!!!!!!!!!!!!!!!!!!!!!!");
				    }			    }
			    else {
			    	com = "";
			    }

			try {
				sleep(100);
			}
				catch(InterruptedException e) {
			}
			    
		    }
		    catch (IllegalMonitorStateException e) {
		    	System.out.println ("Fehler(2): b Monitor war besetzt");
		    }
		}	// Ende while

		System.out.println("Thread 2b Ende");
	}
}
```


----------



## Marco13 (2. Okt 2008)

Hab's nur überflogen (unübsichtlich, schlecht eingerückt, scheußliche Variablen- und Klassennamen (Klassennamen Groß schreiben, Veriablennamen OHNE "_" Unterstrich), fehlerhafte Abfragen (while (com != "ENDE") is böse - Strings muss man mit "equals" vergleichen: while (!"ENDE".equals(com)), überflüssige Exceptions gefangen (eine IllegalMonitorStateException ist eigentlich ein Programmierfehler, und sollte nicht gefangen werden müssen)), aber .... zum eigentlichen Problem:

Kann es sein, dass du davon ausgehst, dass die beiden Threads sich die Daten _abwechselnd_ abholen? Und kann es sein, dass die Threads immer davon ausgehen, dass Daten _vorhanden_ sind? Es gibt (wenn ich das richtig überflogen habe) keinen Mechanismus, der das eine oder das andere sicherstellt....


----------



## renek (2. Okt 2008)

Hi Marco

Also über Namensgebung kann man streiten. Ich will ja kein Literaturnobelpreis  :wink: bekommen . Die Listings sind nur Testprogramme. Die Einrückungen sind durchs kopieren gekommen. Das Formular hier kennt irgendwie kein Tab  :?.
Das mit EQUALS hab ich übersehen. Ist bei mir auch schon geändert.
Das mit der IllegalMonitorStateException kommt daher, da ich auf einem Java-Controller programmiere und da zu Beginn SEHR viele Bugs in der Firmware waren. Man konnte nicht sagen, ob es ein Programmfehler war oder ein Firmwarefehler  :? . Am Angang ging nicht mal "synchronized" richtig.

Ich gehe von eigentlich von nichts aus. Die 3 Threads können laufen wann sie wollen. Ich schreibe nur abwechselnd in die beiden Listen, das die beiden anderen Threads was haben. Aber wann sie die Daten von den Listen abholen ist nicht festgelegt. 

Was das vorhandensein von Elementen angeht. Die Threads versuchen einfach ein Element zu lesen und wenn NULL zurückkommt war halt keins da.

Wenn ich nur eine Liste benutze in die ein Thread reinschreibt und ein andere Thread ausliest klappt alles wunderbar. Nur bei zwei oder mehr Listen kommen die Fehler. Sind die Listen intern irendwie verknüpft?

gruß

renek


----------



## GastsaG (2. Okt 2008)

Setze doch die beiden Attribute deiner data-Klasse auf private und mach synchronized getter und setter darauf. Hilft vielleicht. 

und zum Thema Namensgebung: die Namensgebung und Einrückung ist nicht für den Literaturnobelpreis wichtig, sondern dafür, dass man deinen Quellcode hier liest und so schnell wie möglich versteht. Ich hatte nämlich auch keine Lust das Zeug grossartig zu analysieren.


----------



## renek (2. Okt 2008)

Hi GastsaG

Dein Tipp mit Setter und Getter hat geholfen. Meine ersten Tests verliefen gut  . Im nachhinein erscheint es auch logisch. Meine data Klasse war nicht geschützt. Ich dachte weil ich nur über die buffer Klasse zugreife würden sich da keine Probleme ergeben. 
Habe jetzt die Variablen auf private gesetzt und greife nur noch über synchronized Methoden darauf zu.

Muss jetzt die Änderung nur noch im Projekt umsetzen. Wird aber eine Weile dauern. Dort sind es immerhin 7 Threads die auf insgesamt 5 Listen zugreifen.

Danke allen noch für die Tipps.

Gruß renek


----------



## renek (7. Okt 2008)

Morgen zusammen

Nach Umbau des ganzen Projekts kam die Ernüchterung. Es treten immernoch Fehler auf. Jetzt habe ich aber ein genaueres Fehlerbild.

Wenn der Aufbau folgendermassen ist

```
T1 ---> Buffer1 ---> T2
   |
   ---> Buffer2 ---> T3
```
Also ein Thread reinschreibt und zwei rausholen geht alles. Aber wenn es so ist,


```
T1 ---> Buffer 1 ---> T2  ---> Buffer2 ---> T3
                          |
                          ---> Buffer3 ---> T4
```
dass ein Thread in einen Buffer schreibt, ein anderes es rausholt und dann die Daten in zwei andere Buffer verteilt, geht was bei T2 schief. Bei T3/T4 kommen hin und wieder Daten an, die noch von T1 stammen. Es scheint fast so, als ob die 3 Buffer verbunden wären. Es gibt wohl irgendwo ein Pointerquerverweis.
Es scheint mir ein Systematischer Fehler zu sein. Vielleicht hat ja jemand eine Idee, warum die 3 Listen trotzdem irgendwie verbunden sind.
Die data-Klasse habe ich wie oben beschrieben abgeändert.

Gruß renek


----------

