Wie erreicht man lockfreies, aber blockierendes Verhalten?

Lesezeit: 8 Minuten

Ich implementiere eine lock-freie Single-Producer-Single-Consumer-Warteschlange für eine intensive Netzwerkanwendung. Ich habe eine Reihe von Worker-Threads, die Arbeit in ihren eigenen separaten Warteschlangen empfangen, die sie dann aus der Warteschlange entfernen und verarbeiten.

Das Entfernen der Sperren aus diesen Warteschlangen hat die Leistung unter hoher Last erheblich verbessert. aber sie blockieren nicht mehr, wenn die Warteschlangen leer sindwas wiederum die CPU-Auslastung in die Höhe schnellen lässt.

Wie kann ich effizient bewirken, dass ein Thread blockiert, bis er erfolgreich etwas aus der Warteschlange entfernen kann oder beendet/unterbrochen wird?

  • Hallo, können Sie mir die RPS (Anfrage pro Sekunde) mitteilen, die Sie mit dem Ansatz erreicht haben? Ich habe eine ähnliche Art von Arbeit geleistet (Implementierung eines einfachen HTTP-Servers), also bin ich daran interessiert, es zu wissen. Ich weiß nicht, wie ich dich kontaktieren soll, außer hier zu kommentieren. Tut mir leid falls ich dich belästigt habe.

    – Ajub

    28. August 2012 um 6:05 Uhr

  • @Ayub Leistung war in Ordnung. RPS ist aufgrund unterschiedlicher Hardware-Setups usw. keine gute Einheit zum Messen der Leistung. Ich habe die Anwendung so umgestaltet, dass Worker-Threads vollständig isoliert arbeiten können, und der Leistungsgewinn war ~ 10x. Weniger Daten zu teilen war wirklich der Schlüssel.

    – Eile

    28. August 2012 um 16:27 Uhr

  • Können Sie erklären, warum Sie sich für einen Ansatz mit einer Warteschlange pro Mitarbeiter entschieden haben? Klingt für mich ziemlich suboptimal. Die Ausführungszeit von Jobs in den Warteschlangen ist schwer vorhersehbar.

    – Klassenstapler

    2. Dezember 2015 um 9:29 Uhr

Benutzeravatar von Jason
Jason

Wenn Sie Linux verwenden, prüfen Sie die Verwendung von a Futex. Es bietet die Leistung einer nicht sperrenden Implementierung, indem es atomare Operationen anstelle von Kernel-Aufrufen verwendet, wie es ein Mutex tun würde, aber sollten Sie den Prozess in den Leerlauf versetzen müssen, weil eine Bedingung nicht wahr ist (z. B. Sperrkonflikt), wird es das tun Führen Sie dann die entsprechenden Kernel-Aufrufe durch, um den Prozess in den Ruhezustand zu versetzen und bei einem zukünftigen Ereignis wieder aufzuwecken. Es ist im Grunde wie eine sehr schnelle Semaphore.

  • Hilfreiche Aufklärung! Ich habe vorerst beide Futex-bezogenen Antworten positiv bewertet. Danke.

    – Eile

    22. Mai 2011 um 19:22 Uhr

  • +1 für futex. Seine Leistung ist nicht so gut wie lock-frei, aber es ist gut genug und die perfekte Wahl, wenn Mutex-Locking zu viel ist. pthread-Mutex-API verwendet futex unter den Kulissen.

    Benutzer405725

    15. Juni 2011 um 20:26 Uhr


  • Mutexe unter Linux werden mit einem short implementiert cmpxchg Spin für den Fall mit geringer Konkurrenz und Zurückfallen auf a futex Forderung. Ich verstehe nicht wirklich, warum Sie es als nicht sperrend bezeichnen, wenn es Sperren implementiert (schneller Userspace-Mutex – der Ursprung des Namens).

    – Strkat

    26. Dezember 2013 um 21:46 Uhr


  • Ich nenne es nicht sperrend wegen des Low-Conflict-Falls, der “normalerweise” auftritt, es sei denn, Sie stehen unter hoher Last …

    – Jason

    1. Januar 2014 um 17:25 Uhr

Benutzeravatar von Alexey Kukanov
Alexey Kukanov

Unter Linux, futex kann verwendet werden, um einen Thread zu blockieren. Aber seien Sie sich dessen bewusst Futexe sind knifflig!

UPDATE: Bedingungsvariablen sind viel sicherer zu verwenden als Futexes und portabler. Allerdings wird eine Bedingungsvariable in Kombination mit einem Mutex verwendet, sodass das Ergebnis streng genommen nicht mehr lock-frei ist. Wenn Ihr primäres Ziel jedoch die Leistung ist (und nicht die Garantie des globalen Fortschritts) und der gesperrte Teil (dh eine Bedingung, die nach dem Aufwecken des Threads überprüft werden soll) klein ist, kann es vorkommen, dass Sie zufriedenstellende Ergebnisse erhalten, ohne darauf eingehen zu müssen Feinheiten der Integration von Futexen in den Algorithmus.

  • Das sieht sehr interessant aus. Ich werde dies in Kürze untersuchen und mit meinem Urteil zurückkommen. Danke schön.

    – Eile

    22. Mai 2011 um 19:19 Uhr

  • Der futex Anruf ist eine Implementierung von Sperren. Die Mutex-API dreht sich einfach weiter cmpxchg etwas und fällt dann wieder auf futex (Schneller Benutzerbereich mutex).

    – Strkat

    26. Dezember 2013 um 21:49 Uhr

Wenn Sie Windows verwenden, können Sie keine Futexes verwenden, aber Windows Vista verfügt über einen ähnlichen Mechanismus namens Geschlüsselte Ereignisse. Leider ist dies kein Teil der veröffentlichten API (es ist eine native NTDLL-API), aber Sie können es verwenden, solange Sie den Vorbehalt akzeptieren, dass es sich in zukünftigen Versionen von Windows ändern könnte (und Sie müssen es nicht ausführen). Pre-Vista-Kernel). Lesen Sie unbedingt den Artikel, den ich oben verlinkt habe. Hier ist ein ungetestet Skizze, wie es funktionieren könnte:

/* Interlocked SList queue using keyed event signaling */

struct queue {
    SLIST_HEADER slist;
    // Note: Multiple queues can (and should) share a keyed event handle
    HANDLE keyed_event;
    // Initial value: 0
    // Prior to blocking, the queue_pop function increments this to 1, then
    // rechecks the queue. If it finds an item, it attempts to compxchg back to
    // 0; if this fails, then it's racing with a push, and has to block
    LONG block_flag;
};

void init_queue(queue *qPtr) {
    NtCreateKeyedEvent(&qPtr->keyed_event, -1, NULL, 0);
    InitializeSListHead(&qPtr->slist);
    qPtr->blocking = 0;
}

void queue_push(queue *qPtr, SLIST_ENTRY *entry) {
    InterlockedPushEntrySList(&qPtr->slist, entry);

    // Transition block flag 1 -> 0. If this succeeds (block flag was 1), we
    // have committed to a keyed-event handshake
    LONG oldv = InterlockedCompareExchange(&qPtr->block_flag, 0, 1);
    if (oldv) {
        NtReleaseKeyedEvent(qPtr->keyed_event, (PVOID)qPtr, FALSE, NULL);
    }
}

SLIST_ENTRY *queue_pop(queue *qPtr) {
    SLIST_ENTRY *entry = InterlockedPopEntrySList(&qPtr->slist);
    if (entry)
        return entry; // fast path

    // Transition block flag 0 -> 1. We must recheck the queue after this point
    // in case we race with queue_push; however since ReleaseKeyedEvent
    // blocks until it is matched up with a wait, we must perform the wait if
    // queue_push sees us
    LONG oldv = InterlockedCompareExchange(&qPtr->block_flag, 1, 0);

    assert(oldv == 0);

    entry = InterlockedPopEntrySList(&qPtr->slist);
    if (entry) {
        // Try to abort
        oldv = InterlockedCompareExchange(&qPtr->block_flag, 0, 1);
        if (oldv == 1)
            return entry; // nobody saw us, we can just exit with the value
    }

    // Either we don't have an entry, or we are forced to wait because
    // queue_push saw our block flag. So do the wait
    NtWaitForKeyedEvent(qPtr->keyed_event, (PVOID)qPtr, FALSE, NULL);
    // block_flag has been reset by queue_push

    if (!entry)
        entry = InterlockedPopEntrySList(&qPtr->slist);
    assert(entry);

    return entry;
}

Sie könnten auch ein ähnliches Protokoll verwenden Schlank lesen und schreiben Schlösser u Bedingungsvariablen, mit einem lockless schnellen Pfad. Dies sind Wrapper für Schlüsselereignisse, sodass sie möglicherweise mehr Overhead verursachen als die direkte Verwendung von Schlüsselereignissen.

  • Ja, aber die Futex-Antworten waren bereits vergeben und ich dachte, es könnte für jemand anderen nützlich sein, der später nach dem Thema sucht 🙂

    – bdonlan

    23. Mai 2011 um 13:12 Uhr

  • Der Vollständigkeit halber ist dies interessant – ich entwickle gelegentlich für Windows. 🙂

    – Eile

    23. Mai 2011 um 14:29 Uhr

  • +1, Auch verschlüsselte Ereignisse funktionieren auch unter Pre-Vista einwandfrei (sie wurden ursprünglich als Single-Global-Handle-for-All-Backoff für eine Out-of-Handle-Deadlock-Situation mit kritischen Abschnitten unter 2k implementiert). Der einzige Unterschied zwischen 2k/XP und Vista/7/8 ist ein Implementierungsdetail (verknüpfte Liste vs. Hash), das Vista und spätere KEs viel effizienter macht, wenn Sie viele Speicherorte mit einem einzigen Griff überwachen (kein praktischer Unterschied für 99% aller Bewerbungen).

    – Dämon

    22. August 2013 um 15:49 Uhr

Hast du es mal mit bedingtem Warten versucht? Wenn die Warteschlange leer wird, warten Sie einfach auf einen neuen Job. Der Thread, der Jobs in die Warteschlange stellt, sollte das Signal auslösen. Auf diese Weise verwenden Sie Sperren nur, wenn die Warteschlange leer ist.

https://computing.llnl.gov/tutorials/pthreads/#ConditionVariables

Sie können einen Thread in den Ruhezustand versetzen, indem Sie die Funktion sigwait() verwenden. Sie können den Thread mit pthread_kill aufwecken. Dies ist viel schneller als Bedingungsvariablen.

  • 1) Bitte geben Sie eine Referenz für Ihre Behauptung an, dass ein signalbasierter Mechanismus “viel schneller” ist als eine Bedingungsvariable. Für den Fall, dass der Thread aufwachen muss, spielen in beiden Fällen die Planungs- und Cache-Aspekte eine große Rolle. 2) Bitte geben Sie einen Überblick darüber, wie Race-Bedingungen gehandhabt werden, und den Fall, dass der Thread nicht schlafen geht, sondern stattdessen einen Eintrag aus der nicht leeren Warteschlange aufnimmt. In der Praxis ist dieser schnelle Weg der Schlüsselfaktor für Skalierbarkeit/Performance unter Last. Und es wird ein bisschen schwierig, wenn Sie ein gemischtes Konzept haben.

    – Klassenstapler

    2. Dezember 2015 um 9:08 Uhr

Benutzeravatar von Brendan Long
Brenda Lang

Sie könnten schlafen hinzufügen, während es wartet. Wählen Sie einfach die größte Wartezeit aus, zu der Sie bereit sind, und tun Sie dann so etwas (Pseudocode, weil ich mich nicht an die pthread-Syntax erinnere):

WAIT_TIME = 100; // Set this to whatever you're happy with
while(loop_condition) {
   thing = get_from_queue()
   if(thing == null) {
       sleep(WAIT_TIME);
   } else {
       handle(thing);
   }
}

Selbst etwas kurzes wie ein 100-ms-Schlaf sollte die CPU-Auslastung erheblich senken. Ich bin mir nicht sicher, an welchem ​​​​Punkt der Kontextwechsel es schlimmer machen wird als das geschäftige Warten.

  • 1) Bitte geben Sie eine Referenz für Ihre Behauptung an, dass ein signalbasierter Mechanismus “viel schneller” ist als eine Bedingungsvariable. Für den Fall, dass der Thread aufwachen muss, spielen in beiden Fällen die Planungs- und Cache-Aspekte eine große Rolle. 2) Bitte geben Sie einen Überblick darüber, wie Race-Bedingungen gehandhabt werden, und den Fall, dass der Thread nicht schlafen geht, sondern stattdessen einen Eintrag aus der nicht leeren Warteschlange aufnimmt. In der Praxis ist dieser schnelle Weg der Schlüsselfaktor für Skalierbarkeit/Performance unter Last. Und es wird ein bisschen schwierig, wenn Sie ein gemischtes Konzept haben.

    – Klassenstapler

    2. Dezember 2015 um 9:08 Uhr

1443910cookie-checkWie erreicht man lockfreies, aber blockierendes Verhalten?

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy