Seite 2: Locking

Inhaltsverzeichnis

Ausgesperrt

Gegenseitiger Ausschluss, gemeinhin als Locking bezeichnet, ist in der parallelen Programmierung ein notwendiges Übel. Sperrobjekte ("Locks") sind häufig einzusetzen, um Konflikte beim nebenläufigen Zugriff auf gemeinsam genutzte Datenstrukturen oder Ressourcen zu vermeiden. Diesen Schutz erkauft man sich durch weniger Parallelität aufgrund der Tatsache, dass ein Thread warten muss, bis ein anderer die Sperre aufgehoben und den kritischen Abschnitt verlassen hat. Das ist insbesondere dann ärgerlich, wenn die Sperre nur zur Sicherheit gesetzt werden muss, die Wahrscheinlichkeit eines Zugriffskonflikts aber gering ist.

Das folgende Beispiel zeigt eine einfache (und ineffiziente) Implementierung der Methoden zum Einfügen und Suchen von Paaren in einer hash_map.

template<class K, class V>
struct hash_map {
    
    hash_map() {
        omp_init_lock(&lock);
    }
    
    ~hash_map() {
        omp_destroy_lock(&lock);
    }
    
    V& find(const K& key) const {
        V* ret = 0;
        omp_set_lock(lock);
        ret = internal_find(key);
        omp_unset_lock(lock);
        return *ret;
    }
    
    void insert(const K& key, const V& value) {
        omp_set_lock(lock);
        internal_insert(key, value);
        omp_unset_lock(lock);
    }
    //...
    
private:
    mutable omp_lock_t lock;
    hash_buckets *buckets;
    // ...
};

Das verkürzte Beispiel (keine Fehlerbehandlung usw.) zeigt sofort eine Schwäche der Implementierung auf. Die Sperre wird gleich beim Eintritt in den Methoden angefordert, was dazu führt, dass jeweils nur ein Thread auf die Datenstruktur zugreifen kann. Da Hash-Datenstrukturen jedoch explizit dafür gedacht sind, Zugriffskonflikte aufzulösen, entsteht hier ein unnötiger Engpass: Es könnten sehr wohl mehrere Threads auf die Datenstruktur zugreifen, solange sie nicht auf denselben Hash-Bucket oder sogar auf denselben Eintrag zugreifen oder ihn verändern. Typischerweise geht jetzt die Optimierungsarbeit los, und die Sperren werden vom offensichtlichen Ort in die Tiefen der Implementierung verschoben. Manche versuchen sich gar an einer Lock-freien Implementierung.

OpenMP 4.5 kann hier etwas Erleichterung schaffen, indem Programmierer die neue API für Sperren nutzen. Diese wurde um zwei Funktionen (omp_init_lock_with_hint und omp_init_nest_lock_with_hint) erweitert, die ein zusätzliches Argument vom Typ omp_lock_hint_t erwarten (siehe auch folgende Tabelle).

Typ	Bedeutung
omp_lock_hint_none	Kein Typ gewünscht, OpenMP-Implementierung kann Typ der Sperre frei wählen.
omp_lock_hint_uncontended	Die Sperre erzeugt wenige Konflikte.
omp_lock_hint_contended	Die Sperre erzeugt viele Konflikte durch konkurrierende Threads.
omp_lock_hint_nonspeculative	Sperre soll nicht spekulativ ausgeführt werden; zu viel Konfliktpotenzial durch Überlappung des Working-Sets der Threads.
omp_lock_hint_speculative	Optimistisches Sperren; Konfliktpotenzial im Working-Set ist gering.

Mit dieser API ist es möglich, dass sich für jede einzelne Sperre spezifizieren lässt, auf welche Art die Sperre implementiert werden soll. Im folgenden Beispiel nutzen die Autoren das, um der OpenMP-Implementierung mitzuteilen, dass die Sperre für die hash_map spekulativ ausgeführt werden soll (omp_lock_hint_speculative).

template<class K, class V>
struct hash_map {
    
    hash_map() {
        omp_init_lock_with_hint(&lock, 
                                omp_lock_hint_speculative);
    }
    
    ~hash_map() {
        omp_destroy_lock(&lock);
    }
    
    V& find(const K& key) const {
        V* ret = 0;
        omp_set_lock(lock);
        ret = internal_find(key);
        omp_unset_lock(lock);
        return *ret;
    }
    
    void insert(const K& key, const V& value) {
        omp_set_lock(lock);
        internal_insert(key, value);
        omp_unset_lock(lock);
    }
    //...

private:
    mutable omp_lock_t lock;
    hash_buckets *buckets;
    // ...
};

Auf einem Prozessor mit Intel Transactional Synchronization Extensions führt das dazu, dass die Hardware die Sperre zunächst ignoriert und nur bei einem Konflikt zwischen zwei Threads die betroffenen Rechenkerne zurücksetzt. Darauf wiederholen die Kerne die Ausführung mit vollständigem gegenseitigem Ausschluss.