Array von Objekten in Java: Links-Shift der Elemente

[Nils B. (minifriese)]

Ich hab schon wieder den nächsten Hirn-Blackout. Wenn mir mal jemand 
kurz das Licht einschalten könnte, wär ich ihm/ihr sehr verbunden...

Das Problem:
Ich habe (in Java) ein Array von Instanzen einer Klasse "DataSet". Immer 
wenn das Programm einen neuen Datensatz empfängt, soll das erste Element 
des Arrays verworfen werden. Die folgenden Elemente rücken jeweils um 
eins nach links, und in das letzte Element wird der neue Datensatz 
kopiert.

Bloß: Nach jedem Schritt (=empfangenem Datensatz) scheint in jedem 
Element des Arrays der neue Datensatz zu stehen. Das sehe ich bei der 
graphischen Ausgabe und per printf-Debugging. Beim Shiften geht also 
irgendwas schief. Und ich habe gerade ein Brett vorm Kopf und sehe 
nicht, was...

Das Array ist eine Variable des Applets display.java. Dort gibt es auch 
eine Funktion "shift", die das Verschieben der Elemente übernimmt. Die 
Funktion macht das hier:

for(int k=0;k<InitialDataBufferLength-1;k++)   GraphicsDataBuffer[k]=GraphicsDataBuffer[k+1];

Beim Suchen in Google kam stattdessen das hier raus (gleicher Effekt, 
hier lag der Fehler also wohl nicht):

System.arraycopy(GraphicsDataBuffer, 1, GraphicsDataBuffer, 0, GraphicsDataBuffer.length-1);

Das Applet startet einen ReceiveThread, der über TCP/IP die neuen 
Datensätze empfängt. Beim Eintreffen eines Datensatzes passiert dort das 
folgende:

FatherProcess.Shift();
DataSet d=new DataSet();
for(int i=0;i<5;i++)
   DataSet.Data[i]=big_to_little_endian(DIStr.readShort());
FatherProcess.GraphicsDataBuffer[FatherProcess.InitialDataBufferLength-1]=d;

Sieht jemand den Fehler?? Für mich sieht es so aus, als ob nach dem 
Shift alle Elemente (die ja sowas wie Zeiger sind) auf den neuen 
Datensatz zeigen. Aber wieso??
Macht es Sinn, das ganze statt mit einem Array lieber mit LinkedList 
aufzubauen?

Danke,
Nils

[Markus V. (Gast)]

Hallo Nils,

zuerst mal eine Antwort auf Deine letzte Frage: Ja, es macht Sinn, das 
Rad nicht jedesmal neu zu erfinden, sondern Klassen, die millionenfach 
verwendet werden und damit auch getestet sind, in der eigenen SW 
einzusetzen. :-)

Jetzt zu Deinem eigentlichen Problem. Du schreibst, daß sowohl Dein 
manuelles Kopieren als auch die Methode arraycopy jeweils Schrott 
produzieren. Die erste Annahme: arraycopy kann nicht mit überlappenden 
Arrays arbeiten. Die Doku behauptet das Gegenteil.

Da sowohl Dein Code als auch arraycopy den selben (oder auch einen 
ähnlichen) Fehler hervorrufen, liegt doch der Gedanke nahe, daß 
prinzipiell etwas falsch läuft. Für arraycopy gilt nämlich gleiches wie 
für LinkedList: weltweit millionenfach eingesetzt und daher recht 
stabil.

Wo liegt also das Problem? Beim Stichwort THREAD sollten bei einem 
SW-Entwickler sämtliche Alarmglocken schrillen!!! Nicht daß Threads 
etwas fürchterliches wären, aber hast Du schonmal was vom 
Java-Schlüsselwort "synchronized" gehört? Das soll kein Angriff sein, 
ich möchte lediglich Deinen Background kennen lernen. Die paar Zeilen 
Code lassen nämlich bislang wenig Rückschlüsse darauf zu. Ich frage vor 
allem deshalb, weil ich keine Lust habe, die Fallstricke von 
Multithreading zu erklären, wenn Du dabei gähnst und abwinkst... :-)

Grüße
Markus V.

[Nils B. (minifriese)]

> zuerst mal eine Antwort auf Deine letzte Frage: Ja, es macht Sinn, das
> Rad nicht jedesmal neu zu erfinden, sondern Klassen, die millionenfach
> verwendet werden und damit auch getestet sind, in der eigenen SW
> einzusetzen. :-)

Das ist mir schon klar. Aber hätte es hier einen konkreten Vorteil, die 
LinkedList zu verwenden und nicht das Array? Soll heißen, meinst du, 
mein Fehler liegt in der Handhabung des Arrays und würde meine Taktik 
(links-shift, neues Element hinten anfügen) bei der LinkedList 
funktionieren??

"Schrott produzieren" ist vielleicht etwas zu heftig. Ich versteht halt 
nicht, warum alle meine Array-Elemente (da es Objekte sind, ist jedes 
Element ein Zeiger, oder?) nach dem Shift auf den neuen Datensatz 
zeigen. Ich lege bei jedem Datenempfang mit "new" ein neues Objekt an. 
Es sollte doch möglich sein, die alten Objekte (bzw. die Zeiger darauf) 
im Array "durchzureichen"?

"Synchronized" habe ich schonmal gehört, aber nicht benutzt. Ich glaube, 
damit kann man Objekte kennzeichnen, die dann von verschiedenen 
Prozessen bzw. Threads nicht gleichzeitig benutzt werden können, sondern 
sich mit dem Zugriff "abwechseln"?
Was ich besser kenne, sind Semaphoren, das dürfte wohl das gleiche 
Prinzip sein. Wenn ein Prozeß auf irgendwas (z.B. ein Array) zugreift, 
setzt er eine Semaphore, und andere Prozesse haben erst Zugriff auf 
dieses Array, wenn er fertig ist und die Semaphore wieder gelöscht hat.

In meinem speziellen Fall wird das Array aber nur vom ReceiveThread 
bearbeitet. Die Funktion "shift" gehört zwar zum "FatherProcess", also 
dem Applet. Aber sie wird nur (!) vom ReceiveThread aufgerufen, wenn ein 
neuer Datensatz kommt. Auch das Anfügen des neuen Datensatzes passiert 
nur dort. Das Applet greift nur lesend (beim Zeichnen der Kurve) auf das 
Array zu. Meinst du, das kann ein Problem sein?

Gruß,
Nils

[Markus V. (Gast)]

Hi Nils,

na der Vorteil von Standard-Software liegt doch auf der Hand: Die 
LinkedList bietet genau das was Du benötigst, ohne den Shift selbst 
(vielleicht fehlerhaft?) implementieren zu müssen. Du entfernst das 
erste Element und hängst das neue hinten an. Das klappt bei einer 
Single-Thread-Anwendung immer.

Das Grundproblem bei Dir liegt aber nicht an einer evtl. fehlerhaften 
Implementierung des Shifts. Der Knackpunkt dürfte vielmehr beim 
gleichzeitigen Zugriff zweier Threads auf die selben Objekte liegen. Es 
ist nämlich bei weitem nicht so, daß nur schreibende Zugriffe 
synchronisiert (über eine Semaphore abgesichert) werden müssen.

Folgendes fiktives Szenario auf einem 8-Bit-Prozessor:
Ein 16-Bit Integer der zum Startzeitpunkt auf 0x1122 gesetzt ist, soll 
von Thread A auf den Wert 0x3344 gesetzt werden. Weil die Register nur 8 
Bit breit sind, kann die Operation nicht atomar ablaufen. Das Programm 
kopiert also zuerst 0x33. Als nächstes würde der Wert 0x44 kopiert. 
Bevor dies aber durchgeführt werden kann, bekommt der lesende Thread B 
die CPU zugeteilt. Dieser liest in unserem Szenario den kompletten Wert, 
der jetzt völlig unerwartet auf 0x3322 gesetzt ist.

Generell gilt: Zugriffe auf Daten durch mehr als einem Thread müssen 
über eine Semaphore abgesichert werden, wenn einer von beiden Threads 
irgendwann die Daten ändert. Sonst geht das schief. Die Frage hierbei 
ist wirklich nicht "ob" sondern "wann".

In Java erreicht man das über das Schlüsselwort "synchronized". Es gibt 
zwei Möglichkeiten, "synchronized" zu verwenden. Beide Methoden 
unterschieden sich nur leicht. Die erste ist die Verwendung im 
Methoden-Kopf:

  public synchronized void AccessCommonData() {
      ...
  }

Hier wird als Synchronisations-Objekt "this" verwendet. Die zweite 
Möglichkeit ist die etwas allgemeinere:

  public void AccessCommonData() {
      ...
      synchronized( aSyncObject ) {
          ...
      }
  }

Damit die Threads synchronisiert werden können, muß für beide Threads 
das selbe Objekt verwendet werden, z.B. das "this"-Objekt der ersten 
Variante.

Es gibt beim Multithreading noch einige weitere Fallstricke, zum 
Beispiel die sogenannten Deadlocks. Bsp.: Thread A hat Resource 1 
gelockt und benötigt Resource 2. Diese ist von Thread B gelockt, der 
seinerseits auf Resource 1 wartet. Die Konstellation kann beliebig 
komplex sein.

Ein weiteres Problem ist, daß man zu viel synchronisiert. Man erreicht 
dadurch zwar, daß alle Zugriffe schön hintereinander ablaufen, de facto 
läuft die Software aber dann sequentiell und nicht mehr parallel.

Das Thema ist wirklich nicht so ohne, es gibt dazu auch recht viele 
Bücher und auch Java-Standard-Klassen in den Packages 
java.util.concurrent, java.util.concurrent.atomic und 
java.util.concurrent.locks.

Viel Spaß (das meine ich ernst!) beim Ausprobieren.

Markus V.

[Nils B. (minifriese)]

Moin moin,

Ich habe gerade mal sämtliche Zugriffe auf das Array über eine Semaphore 
abgesichert. Hat aber leider keine Änderung gebracht, soll heißen es 
steht immer noch der neue Datensatz im ganzen Array.

Daß Speicherzugriffe von verschiedenen Threads aus ein Problem sein 
können, wenn sie nicht synchronisiert sind, sehe ich natürlich ein. Aber 
ob das in diesem konkreten Fall das Problem ist? Wäre es nicht auch ein 
ziemlicher Zufall, wenn sich "überlappende Speicherzugriffe" so äußern 
würden wie bei mir? Also daß in allen Array-Elementen die Daten des neu 
zugefügten letzten Elementes liegen? Wobei es ja vermutlich eher so ist, 
daß alle Elemente auf den gleichen Platz im Speicher verweisen, wo halt 
der neue Datensatz steht.

Es wird ja nicht irgendein Speichermüll angezeigt, sondern saubere 
Daten, nur eben die aus dem neuen Datensatz im ganzen Array. Das 
"Durchreichen" durch das Array funktioniert also nicht.

Ich hätte den Fehler eher im Bereich Referenzen/Objekte/Zeiger vermutet. 
Wenn ich statt der Objekte ein Array aus chars oder bytes hätte, bin ich 
mir ziemlich sicher, daß mein Programm funktionieren würde.

Was genau passiert denn im Speicher bei der Anweisung 
array[k]=array[k+1], wenn die Array-Elemente Instanzen einer Klasse 
sind? Wenn ich das richtig verstanden habe, liegt irgendwo im Speicher 
die Instanz und in array[k+1] steht die Adresse dieses 
Speicherbereiches. Nach der obigen Anweisung steht in array[k] die 
gleiche Adresse. Wenn ich nun in die Zelle array[k+1] einen anderen Wert 
schreibe, wird die Instanz nur noch von array[k] referenziert, steht 
aber noch an der gleichen Stelle im Speicher und ist unverändert.

Würde ich statt der Adressenkopie ein clone() von array[k+1] erzeugen 
und dessen Adresse in array[k] schreiben, gäbe es die ursprüngliche 
Instanz zweimal im Speicher, die neuere würde weiterhin von array[k] 
referenziert und die alte würde vom Garbagecollector eingesammelt, 
sobald ich array[k+1] mit einem anderen Wert belege.

Ist das erstmal richtig oder habe ich da schon einen Denkfehler drin?

Nils

[Nils B. (minifriese)]

So, der Vollständigkeit halber habe ich auch mal alle Funktionen, die 
irgendwie auf mein Array zugreifen, als synchronized deklariert. Auch 
das hat keine Änderung gebracht.

Allerdings habe ich mal die tatsächlichen (Zeiger-)Werte der 
Arrayelemente (und nicht die in den Objekten enthaltenen Daten) 
ausgegeben und siehe da: Die Objekte/Zeiger machen genau das, was sie 
sollen. Das shiften funktioniert und das Anhängen des neuen Elements 
ebenso. Frage mich nur, warum dann die Daten in den Datensätzen alle dem 
jeweils neuen entsprechen.

Naja, die Nacht ist ja noch lang...

[Nils B. (minifriese)]

Auweia, das war mal ein selten dickes Brett vorm Kopf. Ich hatte in der 
Klasse Dataset

class DataSet {
   DataSet() {
      Data=new short[5];
   };

   public int tagnr;
   public char valid;
   public short Data[];
}

die Variablen aus irgendeinem wilden Grund als static deklariert. Damit 
wurde natürlich auch das Array nur einmal im Speicher abgelegt und alle 
Instanzen haben darauf zugegriffen. Und jede Änderung der Daten darin 
galt für jede Instanz. Die andern Variablen hatte ich noch gar nicht 
benutzt.
Ohne static geht alles wunderbar ;-)

Ich hatte diese Klassendefinition nicht gepostet, sorry. Sonst hätte es 
bestimmt jemand gemerkt...

Gute Nacht,

Nils