CRuntimeJavalike - Container

Topic:.ContainerJc.

pStyle=std tableStyle=stdTable

Container gehören zu einer Standardlibrary. Die einfachsten Container sind Arrays definierter Größe, die in der C-Standard-Syntax bereits definiert sind. Andere Container sind

• Arrays variabler Größe

• Queues, Listen

• Sortierte Container

Eine C++-Standard-Template-Library (STL) definiert bestimmte Container im C++-Umfeld. Für die Verwaltung der Container ist allerdings meist dynamisch allokierter Speicherplatz notwendig. Zudem arbeitet die STL nicht mit C, es wird das Konzept der C++-Templates benutzt. Daher können die STL-Container für C-Programmierung nicht genutzt werden.

Java bietet in etwa folgende Container im Standard-Sprachumfang, die wichtigsten Vertreter für die verschiedenen Anwendungsgebiete seien hier genannt:

• sunJavadoc/java/util/LinkedList: Eine verlinkte Liste von Objekten, als Queue, Lifo oder Fifo verwendbar.

• sunJavadoc/java/util/ArrayList: Ein Array von Objekten, die Größe ist änderbar.

• sunJavadoc/java/util/TreeMap: Eine baumartige Anordnung von Objekten sortiert mit einem Schlüssel, für die schnelle Suche.

• sunJavadoc/java/util/concurrent/ConcurrentLinkedQueue: Eine verlinkte Liste von Objekten, als Queue, Lifo oder Fifo verwendbar, für schnelle threadsichere Zugriffe.

Diese Container sind in der CRuntimeJavalike implementiert und bieten für die C- oder C++-Programmierung eine adäquate Möglichkeit des Verzeichnisses von Informationen. In reinem C sind ansonsten die handprogrammierten Lösungen, meist auf der Basis einfacher Arrays, verbreitet. Die Anwendung der Listen vereinfacht den Anwender-Programmieranteil.

Topic:.ContainerJc..

pStyle=std tableStyle=stdTable

In einer Software, die unbeobachtet monatelang laufen muss, wird die Verwendung von dynamischen Speicherplatz meist vermieden oder ist aus Gründen der sicherheitsrelevanten Programmierrung verboten. Die Container der CRuntimeJavalike kommen ohne dynamischen Speicher aus, wenn die maximale Anzahl der Daten beschränkt ist. Letzteres ist meist der Fall. Man kann nicht allgemein die Verwendung von dynamischen Speicher verbieten aber keine Obergrenze für Instanzen festlegen. Es ist aber möglich, die Objekte verschiedenen Listen zuzuordnen. Insbesondere kann man eine emptyList für die Haltung der freien Instanzen anlegen, aus der man sich dann bedient um die Instanzen in je nach Anforderung in verschiedenen Listen zu speichern. Die emptyList ist also der Pool der freien Instanzen.

Für die Verwaltung von Listen ist Speicherplatz dynamisch notwendig für sogenannte Nodes (Knoten). Eine einfache Verkettung würde man erreichen, indem man in den Daten selbst entsprechende Zeiger auf die Folge- und Vorgänger-Instanz vorsieht und benutzt. Dann können aber die Instanzen nur je einer Liste zugeordnet werden. Die Grundidee der Container ist aber eher nicht das BeInhalten der Daten sondern die sogenannten Container stellen Verzeichnisse auf Daten dar. Verzeichnisse kann man auch als Index bezeichnen (etwa Index der verbotenen Bücher). Diese Wortbedeutung des Index ist in der Softwaretechnologie verbreitet, beispielsweise in Datenbanken. Man versteht aber unter Index auch die einfache Nummer auf ein Arrayelement, das ist weit weniger.

Man hat also mit den Containern Indices auf die Daten, sortiert nach verschiedenen Kriterien. Beispielsweise alle Daten, die für Zweck A verwendet werden, alle Daten für Zweck B, wobei es die selben Daten wie für A sein können, dann die Daten nach einem Schlüssel für schnelles Suchen sortiert.

Die Nodes der Listen können als ein großer Speicherplatz initial allokiert werden und dann mehreren Listen als Pool übergeben werden. Hat man beispielsweise 5 Listen, die Daten gleichzeitig enthalten können, und 100 Datenplätze, dann braucht man Speicher für 500 Nodes. Eine Node benötigt 24 Bytes.

Topic:.ContainerJc..

pStyle=std tableStyle=stdTable

Die CRuntimeJavalike enthält mit dem BlockHeap ein Konzept der Verteilung von dynamischen Speicher, das keine Speicherlöcher verursacht (alle Blöcke sind gleich groß), und mit dem Garbage-Collector automatisch richtig freigegeben wird. Zudem können mehrere Blockheaps vorhanden sein, die verschiedenen Threads bzw. Funktionsgruppen zugeordnet werden können. So ist die Funktionalität anderer Module noch gesichert, wenn der Speicher einer bestimmten Funktionalität ausgeht. Beispielsweise kann dann eine automatische Reorganisation der Daten gestartet werden, so dass die Funktionssicherheit des Gesamtsystems immer gewährleistet ist.

Die Container können mit diesem Blockheap zusammenarbeiten. Die Nodes für die Verzeigerung der Container können aus bestimmten Intanzen eines Blockheaps genommen werden. Ob die Daten selbst aus dem selben Blockheap stammen, ist dann Sache der Anwenderprogrammierung, die die Daten allokiert. Mehrere Nodes werden in einem Block angeordnet, sonst wäre es ineffizient. Der Block wird dann freigegeben, wenn keine Nodes mehr enthalten sind. Da es sein kann das immer irgendwelche Nodes nicht freigegeben werden, werden dann im Endeffekt genausoviel Blöcke für Nodes allokiert, wie maximal notwendig sind. Diese Anzahl sollte begrenzt sein genauso wie es für die Anzahl der Blöcke insgesamt auch gilt. Ein BlockHeap kann beispielsweise 1000 Blöcke zu je 1 kByte umfassen. Dann sind maximal 200 Blöcke für 8000 Nodes notwendig, mit denen die maximal möglichen 800 Dateninstanzen maximal 10 mal in verschiedenen Listen referenziert werden. Auch hier ist das Mengengerüst begrenzt in dem Sinn, dass der Speicher begrenzt ist. Allerdings ist die Verteilung einfacher.

Softwarefehler, die zum Speicher-Overflow führen, passieren dadurch, dass Daten zwar allokiert und verzeigert, aber dann aus irgendeinem Grund dann nicht verwendet werden. Hängt ein Thread, dann ist nachfolgend ein Speicher-Overflow wahrscheinlich. Hier hilft ein Monitoring von Funktionsgruppen aus anderen Modulen, die an einem anderen Blockheap hängen oder keinen dynamischen Speicher verwenden. Diese können dann die entsprechenden Reparaturen - Rücksetzen, Neu initialisieren oder dergleichen - ausführen.

Topic:.ContainerJc..

pStyle=std tableStyle=stdTable

Die Nodes werden allokiert und dediziert freigegeben. Damit kann man grundsätzlich auch mit malloc/free bzw. new/delete arbeiten. Die entsprechenden Routinen sind vorwärtsdeklariert im Headerfile:ListMapEntryJc.h, aber in den Sources des BlockHeap für den Blockheap implementiert.

struct NodePoolJc_t* current_NodePool_ListMapEntryJc(struct ThreadContextFW_t* _thCxt);
ListMapEntryJc* alloc_ListMapEntryJc(struct NodePoolJc_t* nodePool, struct ThreadContextFW_t* _thCxt);
void free_ListMapEntryJc(struct NodePoolJc_t*, ListMapEntryJc* entry, struct ThreadContextFW_t* _thCxt);

Ein anderes Konzept für dynamischen Speicher kann die Routinen passend bei sich implementieren. Der Typ struct NodePoolJc_t* ist lediglich als Vorwärtsdeklaration definiert, es gibt keinen zugehörigen Strukturtyp. Stattdessen erfolgt in den Implementierungsroutinen ein Casting vom tatsächlichen Implementierungstyp des Nodepools zu diesem Zeigertyp und umgekehrt. Der Typ wird also nur außen benutzt und wird bei den Zuweisungen vom Compiler geprüft (void* zu verwenden wäre die einfache, aber weniger gut dokumentierte und ungetestet Variante.)

Topic:.ContainerJc..

pStyle=std tableStyle=stdTable

Die einfache LinkedList, wie sie auch aus Java: sunJavadoc/java/util/LinkedList bekannt ist, ist nicht threadsicher. Das ist kein Makel grundsätzlicher Natur, denn die threadsichere Variante ist in Java sehr einfach zu haben:

synchronized(myList){
  myList.add(data);
}

Ein mit synchronized eingeleiteter Block setzt einen Mutex zugeordnet zu den angegebenen Daten, hier myList. Wenn alle Beteiligten sich an das Schema halten, dann ist die Sache threadsicher.

Die folgende Grafik zeigt den Ablauf bei Verwendung eines Mutex:

Bild: Klassischer Mutex

Der Prozessor setzt im zuerst laufenden Thread einen lock für einen ausschließenden Zugriff (mutial execution). Zufällig erfolgt eine Unterbrechung von einem anderen Thread, der zunächst höher prior etwas anderes ausführt. vor dem ausschließenden Zugriff auf die Daten setzt dieser höher priore Thread ebenfalls einen Mutex. Infolgedessen wird zum vorher unterbrochenen Thread zurückgeschaltet, da dieser den Mutex innehat. Wichtig ist, dass diese Ausführung mit der höheren Priorität des wartenden Thread ausgeführt wird. Das wird von Multithread-Betriebssystemen gewährleistet. Nach Freigabe des Mutex wird dann wieder zum höher prioren Thread gewechselt, der dann den Mutex bekommt.

Wozu also eine Alternative oder die nicht-threadsichere Basisimplementierung:

• Das Setzen eines Mutex benötigt eine gewisse Zeit. Wenn ein Container überhaupt gar nicht im Multithreading benutzt wird oder ein synchronisieren an anderer Stelle, übergeordnet, erfolgt, dann ist das vergeudete Zeit. Das ist der Grund, dass die Basisimplementierung nicht threadsicher ausgeführt ist.

• Die schnelle lock-freie Programmierung ist schneller als die Nutzung eines Mutex. Sie ist nicht immer anwendbar, sondern nur wenn die letztgültige Operation ein einzelnes Ändern eines wertes oder einer Referenz ist und alle vorigen Operationen keine letztgültige Änderung in den Daten verursachen, wenn die einzige letztgültige Operation fehlschlägt und daher wiederholt werden muss. Diese Voraussetzung ist aber gegeben für die auch in Java vorhandene sunJavadoc/java/util/concurrent/ConcurrentLinkedQueue. Man ist also damit schneller.

Topic:.ContainerJc...

pStyle=std tableStyle=stdTable

Grundlage ist ein Maschinenbefehl, der in den X86-Prozessoren seit dem 486 eingebaut ist. Dieser Maschinenbefehl führt ein bedingtes Setzen einer Speicherzelle aus. Die Bedingung ist eine Prüfung des bisherigen Inhaltes, der als Argument mit übergeben werden muss.

Für die Multicore-Programmierung ist es dabei wichtig, dass der Prozessor selbst dafür sorgt, dass der Inhalt des Speichers mit dem gemeinsamen Speicher abgeglichen ist und nicht etwa nur im Cache eines Cores steht. Das ist bei Multicore-Prozessoren mit entsprechenden modifizierten Befehlen möglich, diese müssen genutzt werden. Die Multicore-Problematik ist dabei also auch gleich mit beachtet.

Ein Prozessor, der diesen Befehlssatz nicht beinhaltet, kann das Verhalten mit mehreren Befehlen nachbilden, wenn aber eine vollständige Interruptsperre dabei ausgesprochen wird. Bei einfachen Prozessoren, bei denen es kein Protected-Bereich der Maschinenbefehle gibt, sollte dies möglich sein. Ein Prozessor, der einerseits Befehle mit Protected-mode schützt, andererseits aber kein compareAndSet bietet, taugt nicht für diese Arbeitsweise.

Da aus Sicht der Anwender- oder auch Basisprogrammierung in C ein Zugriff auf bestimmte Maschinenbefehle nicht erfolgen sollte, ist dieser Zugriff mit einem Funktionsaufruf oder Makro gekapselt, der im Headerfile header:os_AtomicAccess.h entweder dort plattformspezifisch mit einem Makro definiert ist oder als Funktionsprototyp plattformunabhängig angegeben ist und in os_AtomicAccess.c für die jeweilige Plattform ausprogrammiert ist. Dabei existieren folgende Funktionsprototypen, die auch Basis für das entsprechende Makro sein sollen:

void* compareAndSwap_AtomicReference(void* volatile* reference, void* expect, void* update);
int32 compareAndSwap_AtomicInteger(int32 volatile* reference, int32 expect, int32 update);

Die Befehlsfolge in Assembler, die dabei aufgerufen wird, sieht für den Microsoft-Compiler wie folgt aus:

int32 compareAndSwap_AtomicInteger(int32 volatile* reference, int32 expect, int32 update) {
 { int lastValue;
  /* The cmpxchg instruction sets the memory location edx with ecx if it is equal eax.
   * In this case eax is equal the content of [edx].
   * if the value at memory location is not equal eax, than no change is done,
   * but eax is loaded with the content of memory location at [edx].
   * In this case eax is not equal with the expect value.
   */
  _asm {
   mov eax, expect
   mov ecx, update
   mov edx, dword ptr [reference]
   lock cmpxchg dword ptr [edx], ecx
   mov lastValue, eax
 }

Die adäquate Befehlsfolge für den GNU-Compiler muss geschrieben werden in der Form:

int32 compareAndSwap_AtomicInteger(int32 volatile* reference, int32 expect, int32 update)
{ __typeof (*reference) ret;
  __asm __volatile ( "lock cmpxchgl %2, %1"
           : "=a" (ret), "=m" (*reference)
          : "r" (update), "m" (*reference), "0" (expect));
  return ret;
}

Die Schreibweisen sind unterschiedlich, der Inhalt ist derselbe.

volatile:

Die Speicherstellen für die Werte beziehungsweise die Referenzen, die in einem anderen Thread konkurrierend geändert werden können, sind mit dem Schlüsselwort volatile zu kennzeichnen. Für den Compiler bedeutet dies, dass bei jedem Zugriff auf die Speicherzelle der Wert erneut geholt werden muss, und nicht etwa optimierenderweise ein einmal geholter Wert in Prozessorregistern gespeichert wiederverwendet werden kann. Für den Zugriff auf den Speicher bedeutet dies auch, dass eine Synchronisation mit dem tatsächlichen Speicherinhalt ausgeführt werden muss, und nicht etwa die Werte aus einem Cache, der nur einem Core zugeordnet ist. Das ist wichtig für Multicore-Architekturen, bei denen ein anderer Thread in einem anderem Core laufen kann oder eine automatische Aufteilung des Programmablaufs auf die Cores erfolgt.

Die folgende Grafik zeigt den Ablauf bei Verwendung des lockfreien CompareAndSwap:

Bild: CompareAndSwap

Im Programmablauf wird auf den Wert in der betreffenden Speicherzelle zugegriffen und darauf aufbauend in den eigenen, noch nicht anderweitig sichtbaren Daten Werte gesetzt. Der letzte Zugriff auf die betreffende Speicherzelle soll dann diese Daten manifestieren, beispielsweise mit Einhängen des neuen Datensatzes in eine verkettete Liste. Zufällig erfolgt eine Unterbrechung von einem anderen Thread, der ebenfalls auf dem bisher ungeänderten Inhalt der Speicherzelle basierend neue Werte vorbereitet. Dieser Thread wird dann seine Aktion fertigstellen. Damit ist aber der Inhalt der betreffenden Speicherzelle geändert. Die zuvor darauf aufbauenden Aktionen des erten, unterbrochenen Threads sind hinfällig. Das wird dieser Thread auch feststellen, wenn er dann versucht, die Daten zu manifestieren. CompareAndSwap führt die Aktion des Setzens des neuen Wertes nicht aus und gibt als Returnwert den stattdessen vorgefundenen geänderten Wertes auf der Speicherzelle zurück.

Daraufhin muss die gesamte Aktion des ersten zwischendurch unterbrochenen Threads nochmal wiederholt werden. Das sieht konkret programmiert etwa so aus (Auschnitt aus ConcurrentLinkedQueueJc):

Topic:.ContainerJc...

pStyle=std tableStyle=stdTable

Zur Funktionsbeschreibung werden die orignalen Quellcodes der Java-Klassen herangezogen. Diese Rechte liegen bei Sun Microsystems.

Die sunJavadoc/java/util/concurrent/ConcurrentLinkedQueue enthält 2 Referenzen auf Nodes:

 /**Pointer to header node, initialized to a dummy node.  The first
  * actual node is at head.getNext().
  */
 private transient volatile Node<E> head = new Node<E>(null, null);
 /** Pointer to last node on list **/
 private transient volatile Node<E> tail = head;

Wie dem Quellcode bereits hier zu entnehmen ist, enthält die Liste immer eine dummy node, die auf kein Element zeigt.

Ein Element wird hinten angefügt mit sunJavadoc/java/util/concurrent/ConcurrentLinkedQueue#offer(E). Das sieht im Quelltext wie folgt aus:

   public boolean offer(E e) {
       if (e == null) throw new NullPointerException();
       Node<E> n = new Node<E>(e, null);
       for (;;) {
           Node<E> t = tail;
           Node<E> s = t.getNext();
           if (t == tail) {
               if (s == null) {
                   if (t.casNext(s, n)) {
                       casTail(t, n);
                       return true;
                   }
               } else {
                   casTail(t, s);
               }
           }
       }
   }

• Eine neue Node wird im Heap allokiert: new Node<E>(e, null);. Die Referenz auf das gegebene Object e wird beim Konstruktor übergeben. Der zweite Parameter null initialisiert das next-Element der Node. Hinweis: Nodes bestehend aus Anwender-Object- und next-Zeiger sind notwendig zur Verkettung. Die Anwenderobjekte selbst haben nicht die Eigenschaft, verkettet werden zu können.

• Mit t.casNext(s, n) wird an die vorgefundene letzte Node die neue Node als next angehängt. Die Abfragen zuvor sichern nur nochmals, dass mittlerweile nicht schon die Liste erweitert wurde. Diese Operation wird nur ausgeführt, wenn tail.next während der Ausführung null enthält (s ist null, zuvor getestet). Das ist die entscheidende atomic-compareAndSet-Operation. Damit ist die Liste erweitert.

• Im Erfolgsfall wird anschließend versucht, das this.tail-Element auf die nunmehr letzte Node n weiterzusetzen. Das wird ebenfalls mit atomic-compareAndSet ausgeführt, nur wenn this.tail noch unverändert ist. Ist es verändert, dann kann die Ursache nur darin liegen, dass mittlerweile ein höher priorer Thread ebenfalls offer() gerufen hat und this.tail bereits verändert hat. Dann ist die LinkedList bereits länger, das ungetestete Setzen des this.tail hier würde einen alten Zustand manifestieren. Eine Abfrage über den Erfolg des atomic-CompareAndSet ist nicht notwendig. Entweder es ist erfolgreich, oder es ist deshalb nicht erfolgreich, weil ein unterbrechender Thread bereits eine bessere Arbeit geleistet hat.

• Das Ganze wird solange wiederholt, solange die t.casNext(s, n)-Operation nicht erfolgreich ausgeführt werden konnte. Wenn ein höher priorer Thread unterbrochen hat, seinerseits vor dieser Operation die Liste erweitert hat, dann müssen die Bedingungen der Erweiterung ab Node<E> t = tail nochmals ausgeführt werden. Es ist garantiert, dass dieser Wiederholprozess nicht unendlich läuft, den ein Thread, der eben unterbrochen hat, wird niemals in Nanosekunden-Folge wieder unterbrechen. Das verhindert der Thread-Scheduler. Die maximale Anzahl der Unterbrechungen dieser Schleife ist also nicht größer als die Anzahl der statisch vorhandenen Threads.

Ein Element wird vorn ausgekettet mit sunJavadoc/java/util/concurrent/ConcurrentLinkedQueue#poll(). Das sieht im Quelltext wie folgt aus:

 public E poll() {
     for (;;) {
         Node<E> h = head;
         Node<E> t = tail;
         Node<E> first = h.getNext();
         if (h == head) {
             if (h == t) {
                 if (first == null)
                     return null;
                 else
                     casTail(t, first);
             } else if (casHead(h, first)) {
                 E item = first.getItem();
                 if (item != null) {
                     first.setItem(null);
                     return item;
                 }
                 // else skip over deleted item, continue loop,
             }
         }
     }
 }

• Die als first bezeichnete Node ist die zweite, die next der von this.head gezeigerten Node.

• Der Normalfall ist h != t, also der else-Zweig der zweiten Abfrage. Dort wird casHead(h, first) ausgeführt. Damit wird die zweite Node first von this.head referenziert, womit eine Node weniger in der LinkedList ist.

• Die entfernte Node wird aber nicht betrachtet. Die head-Node ist dummy. Sie wird, da nicht mehr referenziert, vom GarbageCollector entsorgt.

• Die Referenz zum Anwenderobject wird der first-Node entnommen, die vorher die zweite und nun die erste ist. Das sie nun die erste ist, wird sie von allen anderen Operationen in unterbrechenden Threads in Ruhe gelassen. Man kann also ungestört die Referenz auslesen und anschließend auf null setzen.

• Es gibt allerdings noch die sunJavadoc/java/util/concurrent/ConcurrentLinkedQueue#remove(java.lang.Object)-Methode. Diese löscht nicht etwa die Node des gefundenen Objects mitten heraus, sondern setzt stattdessen die item-Referenz in der Node auf null. Diese Bedingung wird dann hier vorgefunden. Bei einer null-Referenz für ein Item wird der Vorgang wiederholt, da in der ersten zu betrachteten Node also kein Item vorgefunden wurde.

• Der Sonderfall ist (h==t), was auf eine leere Liste hindeutet. Es wird nur eine einzige, die dummy-Node referenziert. Allerdings kann es sein, dass dieser Thread einen anderen Thread unterbrochen hat, der eben ein Element hineingelegt hat (offer(E)), aber noch nicht dazu gekommen ist, this.tail weiterzusetzen. Das wird eindeutig festgestellt mit first != null. Dann wird hier this.tail gesetzt und also nochmals wiederholt.