Atomic

… war ein Spiel, in dem man Atome zu Molekülen zusammenführen musste.

In jener Zeit waren auf dem guten alten PC noch alle Instruktionen “atomar” und Programmierer mussten sich um den Zugriff auf Variablen nicht weiter kümmern.

Nicht einmal als präemptives Multitasking aufkam, wurde das Thema besonders populär, obwohl damit sowohl durch Linux wie auch unter Windows der unterbrochene Zugriff auf Speicherzellen möglich wurde.

Was sind atomare Zugriffe?

Wollen wir eine Variable um 1 erhöhen, finden 3 Operationen statt.

• Die Variable wird in ein CPU-Register gelesen,
• der Wert wird im Register erhöht,
• der Register-Inhalt wird in den Variablenspeicher geschrieben.

Schreibt nun ein anderer Thread zur gleichen Zeit ebenso in die Variable, kommt es zur Korruption. Unter Linux/POSIX könnten wir auch noch Signale als Szenario sehen.

Selbst auf Single-Core System passiert das, weil ein Thread während der Lese/Schreibeoperation unterbrochen werden kann. Und auf unseren heutigen Multi-Core Systemen ist das noch schlimmer. Denn alle CPU-Kerne arbeiten entkoppelt, haben ihre eigenen Caches und es ist nicht garantiert, in welcher Reihenfolge CPU-Caches mit dem Speicher synchronisiert werden.

Betriebssysteme stellen uns Mutex- und Critical-Section-Strukturen bereit, mit denen bei gemeinsamen Zugriffen nur eine CPU Code ausführen kann, während die anderen angehalten werden (Sie werden natürlich nicht angehalten, sondern dürfen was anderes rechnen ;) )

Prozessoren unterstützen aber auch eine interne Möglichkeit mit diesem Phänomen umzugehen: Atomare Zugriffe.

Ein atomarer Lese- oder Schreibzugriff besteht aus einer etwas anderen Codesequenz, die alle Kerne im System synchronisiert und Unterbrechungen (Interrupts) während der Zugriffsoperation unterbindet.

Eine atomare Operation garantiert also, dass der Wert einer Variable als ganzes gelesen und geschrieben wird, und dass alle anderen CPUs sofort ihren Cache aktualisieren müssen, wenn sie ebenfalls darauf zugreifen.

Die Windows-API stellt uns die Interlocked Funktionen zur Verfügung. Der MSVC lässt uns diese API aber auch direkt in CPU Instruktionen übersetzen.

Linux und POSIX definieren selbst meines Wissens keine eigene API, doch der GCC stellt mit seinen _sync* Funktionen alles bereit, was wir brauchen, um atomare Zugriffe zu realisieren.

Erst der C11 Standard und der C++11 Standard nehmen sich des Themas an … und das war meiner Meinung nach 10 Jahre zu spät.

Das Compare-and-swap (CAS) Schema ist die elementarste atomare Anweisung. Man kann alle Formen von Synchronisierungen und Rechenoperationen mittels CAS abbilden. In Hochsprachen manifestiert sich CAS meist so, dass der Inhalt einer Speicherstelle nur dann verändert wird, wenn ihr aktueller Wert einem bestimmten Wert entspricht.

 long pseudo_cas(long volatile* atom, 
                 long compare_with, long new_value)
 {
   long old_value = *atom;
   if(old_value == compare_with)
   {
     *atom = new_value;
   }
   return old_value;        
}

long win_cas(long volatile* atom, 
             long compare_with, long new_value)
{
  return InterlockedCompareExchange(
           atom, new_value, compare_with);
}

long gcc_cas(long volatile* atom, 
             long compare_with, long new_value)
{
  return __sync_val_compare_and_swap(
           atom, compare_with, new_value);
}

Im GATE Projekt bilden die gate_atomic_[TYPE]_xchg_if() Funktionen das CAS Feature ab. Ich setze “Atome” gerne als Statusvariablen ein, um auf Mutexe verzichten zu können.

 #define DISCONNECTED 0
 #define CONNECTED 1
 #define BUSY 2
 static gate_atomic_int32_t state = DISCONNECTED;
 
 bool connect_something()
 {
   if(DISCONNECTED != 
      gate_atomic_int32_xchg_if(&state, DISCONNECTED, BUSY))
  {
    /* Alter Zustand war NICHT DISCONNECTED -> Abbruch */
    return false;
  }

  /* Neuer Zustand ist jetzt BUSY */
        
  ...
        
  gate_atomic_int32_set(&state, CONNECTED);
  /* Neuer Zustand ist jetzt CONNECTED */
  
  return true;
}

bool do_something_with_connection()
{
  if(CONNECTED != 
     gate_atomic_int32_xchg_if(&state, CONNECTED, BUSY))
  {
    /* Alter Zustand war NICHT CONNECTED -> Abbruch */
    return false;
  }
  /* Zustand ist jetzt BUSY */
        
  ...
        
  gate_atomic_int32_set(&state, CONNECTED);        
  /* Neuer Zustand ist jetzt wieder CONNECTED */        
  
  return true;
}

bool disconnect_something()
{
  if(CONNECTED != 
     gate_atomic_int32_xchg_if(&state, CONNECTED, BUSY))
  {
    /* Alter Zustand war NICHT CONNECTED -> Abbruch */
    return false;
  }
        
  /* Zustand ist jetzt BUSY */
        
  ...
        
  gate_atomic_int32_set(&state, DISCONNECTED);  
  /* Neuer Zustand ist jetzt DISCONNECTED */        
  
  return true;        
}