Zuverlässigkeitsanalyse: Ganz nebenläufig

Ganz nebenläufig

Open-Source-Fallstudie: Sperrkonflikte mit SQLite

Jobangebote+ passend zum Thema

MACNICA ATD EUROPE - Ihre berufliche Zukunft

MACNICA ATD Europe GmbH, Ingolstadt

---

Alle Jobangebote im Elektroniknet Karrierebereich anzeigen

Die Entwickler des großartigen Open-Source-Projektes »SQLite« hatten sich 2006 lange mit bei der Ausführung der Datenbank gemeldeten Deadlocks befasst (Bild 3).

Dieser konnte schließlich auf Code zurückgeführt werden, der eigentlich die spezifische Aufgabe hatte, Schutz vor derartigen Zwischenfällen zu bieten (wie dies ja oft der Fall ist).

Dieser Fehler war schwierig zu verstehen und zu dessen Lösung war es notwendig, praktisch das gesamte problematische Modul umzuschreiben - was Tage oder gar Wochen an intensiver manueller Programmfehler-Behebung, sowie Gedankenmodellierungen ohne Quellcode-Analysetool notwendig machte (Bild 4).

Dennoch wurde der äußerst unangenehme Programmfehler identifiziert und in einer Analyse, die bloß einige Minuten dauerte, korrekt beschrieben.

Man stelle sich die Anforderungen an die Implementierung einer sehr einfachen rekursiven Singleton-Sperre in einer Umgebung vor, die derartige Konstruktionen nicht unterstützt.

Unter Verwendung von Referenzzählern lässt sich ziemlich einfach die darunterliegende nichtrekursive Sperre überwachen und ihre Laufzeit effizient managen.

In dieser »parallelen« Welt ist natürlich eine weitere Sperre nötig, um die Referenzzähler zu beobachten, welche die tatsächliche Sperre überwachen.

Dies verkompliziert die Implementierung nur ein kleines bisschen. Das entsprechende Design könnte ungefähr wie folgt aussehen:

lock_t lock1, lock2;
int refCount = 0;

void enter() {
reserve_lock(lock1);
if( refCount == 0 )
reserve_lock(lock2);
release_lock(lock1);
refCount++;
}
void leave()
{
reserve_lock(lock1);
refCount--;
if( refCount == 0 )
release_lock(lock2);
release_lock(lock1);
}

Nun kann man enter() mehrfach aufrufen und damit einige der Möglichkeiten einer echten rekursiven Sperre simulieren. Solange der Programmierer nicht vergisst, leave() genau gleich oft aufzurufen, wird die Laufzeit der darunterliegenden nichtrekursiven Sperre korrekt gemanagt:

void foo()
{
// real lock is reserved
enter();
if(i-really-want-to)
{
// only the reference count is affected
enter();
…
leave();
}
// now the real lock is released
leave();
}

Stellen Sie sich nun die Anforderung vor, eine Abstrahierung über Thread-spezifische Datenspeicherung zu implementieren. Damit die Sicherheit bei der Zuordnung einer derartigen Struktur gewährleistet ist, verwendet die Datenbank die zuvor beschriebene rekursive Singleton-Sperre, um ihre Aktivitäten durch eine Implementierung zu schützen, die vereinfacht so lauten kann:

int tlsCreated = 0;

data_t* create_data()
{
static data_t* tls;
enter();
if(tlsCreated==0)
tls = create_thread_data();
tlsCreated = 1;
leave();
init_data(tls);
return tls;
}

Bei oberflächlicher Betrachtung scheint dies einigermaßen korrekt, da leave() gleich oft aufgerufen wird wie enter(). Leider ist das Leben in der Parallelwelt selten einfach zu analysieren, und dieser Fall ist sicherlich komplizierter, als es zunächst scheinen mag. Wenn eine Doppelkern-CPU zwei Threads ausführt, die beide create_data in sehr geringen Zeitabständen aufrufen, geschieht Folgendes: Der erste Thread beginnt create_data() auszuführen und ruft erfolgreich die enter()-Funktion auf. Dies führt dazu, dass das darunterliegende lock, lock 2, für Thread 1 reserviert ist:
Thread 1

create_data()
enter()
refCount = 0
reserve(lock1)
reserve(lock2)
release(lock1)
refCount = 1

Im Kasten »Gegenseitige Blockade, Teil 1« ist nun gezeigt, was passiert, wenn Thread 2 mit seiner Ausführung von create_data() beginnt, während Thread 1 aktiv ist und bevor lock 1 entsperrt wird. Eine weitere Annahme vervollständigt schließlich das Szenario: Thread 1 wird in diesem Moment unterbrochen, er verliert seine Zeit auf der CPU. Entscheidenderweise geschieht dies, bevor der Referenzzähler aktualisiert wird.

Dies ist im Kasten »Gegenseitige Blockade, Teil 2« dargestellt. Überprüft man die Implementierung von enter(), wird klar, dass der Autor das Update der Referenzzähler leider außerhalb dessen gelassen hat, was eigentlich den Zugang zu ihm überwachen müsste. Weil der Referenzzähler deshalb weiterhin den Wert Null für Thread 2 lesen wird, wird er versuchen, lock 2 zu reservieren, was dazu führt, dass Thread 2 blockiert (da lock 2 bereits von Thread 1 besetzt ist).

Nach Rückkehr von der Unterbrechung wird Thread 1 freigegeben und nimmt die Ausführung dort wieder auf, wo er aufgehört hat, indem er den Referenzzähler inkrementiert und von der enter()-Funktion zurückkehrt. Er setzt seine Ausführung von create_data() fort, was zu einem Aufruf der leave()-Funktion führt, die leider versucht, lock 1 zu reservieren, bevor sie irgend-etwas anderes tut. Aufgrund der Tatsache, dass Thread 2 jetzt blockiert ist, auf lock 2 wartet und momentan lock 1 besetzt, wird Thread 1 seinen eigenen Versuch blockieren, lock 1 zu reservieren.

Zusammengefasst handelt es sich hier um eine »lock-order inversion contention«, verursacht durch ein schlecht überwachtes Datenelement, das, wenn es zu einer Race-Condition kommt, einen Thread dazu bringt, Sperren in Abfolge zu reservieren, während der andere Thread versucht, sie aus der Abfolge heraus zu reservieren, was in einem Deadlock resultiert.

Wird die Race-Condition behoben, wird dieser Singleton korrekt funktionieren, obwohl der Autor sich - wie erwähnt - in Wirklichkeit dafür entschieden hat, dieses Modul vollständig neu zu schreiben und eine nützlichere, ablaufinvariante gegenseitige Ausschlussfunktion für mehrere Threads zu schaffen, d.h. die Singleton-Semantik zu entfernen.

Generell ist das Komplexitätsniveau auf diesem Gebiet sehr hoch, was bedeutet, dass nicht alle Probleme mit einer einzigen Lösung, einem einzigen Tool oder einer einzigen Herangehensweise gelöst werden können. Software-Entwicklerteams benötigen brauchbare Tools, kluge Programmierannahmen und noch klügere Entwickler, um den vom Markt verlangten Wettlauf um Funktionen und die damit zusammenhängende Komplexität der darunterliegenden Plattformen unter einen Hut zu bringen.

Bei der Auswahl eines Werkzeugs sollte der Entwickler auf jeden Fall die Quellcodeanalyse in Betracht ziehen, da diese eine überwältigende Kombination von Skalierbarkeit und Flexibilität einerseits bietet und andererseits die Fähigkeit, viele Probleme anzugehen. Dies hilft dabei, die Gesamtqualität und Gesamtqualität und Sicherheit des Codes sicherzustellen.

Über den Autor:

Gwyn Fisher ist Chief Technology Officer von Klocwork.

1. Zuverlässigkeitsanalyse: Ganz nebenläufig
2. Ganz nebenläufig