Linux 3.0:Futex-Lock-Deadlock-Fehler?

Question

// SubFetch(x,y) = atomically x-=y and return x (__sync_sub_and_fetch)
// AddFetch(x,y) = atomically x+=y and return x (__sync_add_and_fetch)
// CompareWait(x, y) = futex(&x, FUTEX_WAIT, y) wait on x if x == y
// Wake(x, y) = futex(&x, FUTEX_WAKE, y) wake up y waiters

struct Lock
{
Lock() : x(1) {}

void lock()
{
    while (true)
    {
        if (SubFetch(x, 1) == 0)
            return;

        x = -1;

        CompareWait(x, -1);
    }
}

void unlock()
{
    if (AddFetch(x, 1) == 1)
        return;

    x = 1;

    Wake(x, 1);
}

private:
    int x;
};

Linux 3.0 bietet einen Systemaufruf namens futex, auf dem viele Parallelitätsdienstprogramme basieren, einschließlich neuerer pthread_mutex-Implementierungen.Wenn Sie Code schreiben, sollten Sie immer darüber nachdenken, ob die Verwendung einer vorhandenen Implementierung oder das Schreiben selbst die bessere Wahl für Ihr Projekt ist.

Oben ist eine Implementierung eines Locks (Mutex, 1 Permit Counting Semaphor) basierend auf Futex und der Semantikbeschreibung in Mann futex(7)

Es scheint einen Deadlock-Bug zu enthalten, bei dem mehrere Threads, nachdem mehrere Threads ein paar tausend Mal versucht haben, es zu sperren und zu entsperren, in einen Zustand geraten können, in dem x == -1 und alle Threads in CompareWait stecken bleiben, obwohl niemand dies hält sperren.

Kann jemand sehen, wo der Fehler ist?

Aktualisieren: Ich bin ein wenig überrascht, dass futex(7)/semantics so kaputt ist.Ich habe Lock wie folgt komplett umgeschrieben ...ist das jetzt richtig?

// CompareAssign(x,y,z) atomically: if (x == y) {x = z; ret true; } else ret false;

struct Lock
{
Lock() : x(0) {}

void lock()
{
    while (!CompareAssign(x, 0, 1))
        if (x == 2 || CompareAssign(x, 1, 2))
            CompareWait(x, 2);
}

void unlock()
{
    if (SubFetch(x, 1) == 0)
        return;

    x = 0;

    Wake(x, 1);
}

private:
int x;
};

Die Idee dabei ist, dass x die folgenden drei Zustände hat:

0: unlocked
1: locked & no waiters
2: locked & waiters

Answer 1

Das Problem besteht darin, dass Sie explizit -1 zuweisen x wenn die SubFetch Es gelingt ihm nicht, die Sperre zu erhalten.Das rast mit der Freischaltung.

1. Thread 1 erhält die Sperre. x==0.
2. Thread 2 versucht, die Sperre zu erlangen.Der SubFetch Sätze x auf -1, und dann wird Thread 2 angehalten.
3. Thread 1 gibt die Sperre frei.Der AddFetch Sätze x auf 0, daher wird der Code dann explizit gesetzt x auf 1 und ruft an Wake.
4. Thread 2 wird aktiviert und eingestellt x auf -1 und ruft dann auf CompareWait.

Thread 2 steckt jetzt fest und wartet, mit x auf -1 gesetzt, aber es ist niemand da, der es aufweckt, da Thread 1 die Sperre bereits freigegeben hat.

Answer 2

Die ordnungsgemäße Implementierung eines FUTEX-basierten Mutex wird in Ulrich Drepper's Paper "Futexes sind knifflig" beschrieben.

http://people.redhat.com/drepper/futex.pdf

Es beinhaltet nicht nur den Code, sondern auch eine sehr detaillierte Erklärung, warum es richtig ist.Der Code aus dem Papier: generasacodicetagpre.

Vergleichen des Codes in der Zeitung mit Ihrem Code, ich erkennen einen Unterschied

Sie haben

if (x== 2 || comproseassign (x, 1, 2))

Verwenden des Werts des FUTEX direkt, während der Drepper den Rückgabewert von der vorherigen COMPANYASSIGN () verwendet.Dieser Unterschied wird wahrscheinlich nur die Leistung beeinträchtigen.

Ihr Freischaltcode ist auch anders, scheint jedoch semantisch gleichwertig zu sein.

In jedem Fall würde ich Sie dringend empfehlen, Drepper-Code dem Brief zu folgen.Dieses Papier hat den Test der Zeit gestanden und erhielt viel Peer-Review.Sie gewinnen nichts, wenn Sie Ihre eigenen rollen.

Answer 3

Wie wäre es mit diesem Szenario mit drei Threads, A, B und C?

Der Ausgangszustand dieses Szenarios ist:

• Faden A hält das Schloss
• Thread B kämpft noch nicht um die Sperre
• Faden C hinein CompareWait()
• x == -1 ab dem Zeitpunkt, an dem C die Sperre nicht erhalten konnte

        A                  B                C
    ==============   ================  ===============
     AddFetch()
     (so x == 0)
                       SubFetch()
                       (so x == -1)

     x = 1

                       x = -1

     Wake()

Zu diesem Zeitpunkt erhalten sie kein Ergebnis, unabhängig davon, ob B oder C entsperrt sind 0 wenn sie SubFetch().