Snel tellen van semafoor op Windows?

Allereerst weet ik dat het kan worden geïmplementeerd met een mutex- en conditievariabele, maar ik wil de meest efficiënte implementatie mogelijk maken. Ik zou graag een semafoor met een snel pad willen wanneer er geen geschil is. Op Linux is dit eenvoudig met een futex; hier is bijvoorbeeld een wachttijd:

if (AtomicDecremenIfPositive(_counter) > 0) return;//Uncontended
AtomicAdd(&_waiters, 1);
do
{
    if (syscall(SYS_futex, &_counter, FUTEX_WAIT_PRIVATE, 0, nullptr, nullptr, 0) == -1)//Sleep
    {
        AtomicAdd(&_waiters, -1);
        throw std::runtime_error("Failed to wait for futex");
    }
}
while (AtomicDecrementIfPositive(_counter) <= 0);
AtomicAdd(&_waiters, -1);

en post:

AtomicAdd(&_counter, 1);
if (Load(_waiters) > 0 && syscall(SYS_futex, &_counter, FUTEX_WAKE_PRIVATE, 1, nullptr, nullptr, 0) == -1) throw std::runtime_error("Failed to wake futex");//Wake one

In eerste instantie dacht ik dat Windows alleen NtWaitForKeyedEvent() zou gebruiken. Het probleem is dat het geen directe vervanging is omdat het de waarde at _counter niet atoommatig controleert voordat het de kernel ingaat, en dus het ontwaken kan missen van NtReleaseKeyedEvent (). Erger nog, dan zou NtReleaseKeyedEvent() blokkeren. Wat is de beste oplossing?

1
Semaforen. Mutexen worden verondersteld te zijn ontgrendeld door de thread die hen heeft vergrendeld. Ik heb threads nodig die wachten op semaforen die anderen plaatsen.
toegevoegd de auteur Display Name, de bron
@MartinJames, een plaats waar ik semaforen gebruik, is voorwaardelijke slaap van producenten in een systeem met een niet-blokkerende consument (de consument heeft andere dingen te doen, maar zal een bijgewerkt resultaat van een producent gebruiken, indien beschikbaar). Producenten blokkeren zichzelf met een sem_wait() wanneer ze de buffer vullen, en de consument zal sem_post() gebruiken wanneer een nieuw resultaat uit de buffer nodig is. In dit geval zou een binaire seamphore volstaan, maar ik kan geen mutex gebruiken omdat een mutex verondersteld wordt te zijn ontgrendeld door de thread die het bezit.
toegevoegd de auteur Display Name, de bron
@Damon, ik dacht dat dit de reden was dat ze het releasebeefblok maakten. Maar ik denk niet dat een mutex-ontgrendeling, of een semafoorpost of een condvar-signaal ooit de kans moet krijgen om te blokkeren. Ook is het op deze manier omgaan met gemiste wakes waarschijnlijk minder efficiënt dan de manier waarop het wordt behandeld in de snelle mutex van locklessinc.com/articles/keyed_events/ Het is jammer dat dit deel van de API niet gedocumenteerd is, maar ik heb de NtWaitForKeyedEvent-crash nooit gehad.
toegevoegd de auteur Display Name, de bron
Merk op dat NTReleaseKeyedEvent blokken zodat u geen miss-out kunt missen. Dat is de bedoeling erachter. Keyed events hebben een veel groter probleem, voor zover ze nog minder gedocumenteerd zijn dan de onleesbaar gedocumenteerde futexes (dat wil zeggen helemaal niet). Toen ik probeerde exact hetzelfde te implementeren dat je nu een paar weken geleden probeerde, had ik elke keer een NtWaitForKeyedEvent segfault, hoewel er echt niet zo veel is wat je fout zou kunnen doen, of zo zou denken.
toegevoegd de auteur Damon, de bron
Hmm ... eerste gedachten: als het aantal semaforen wordt weergegeven door een geheel getal, geeft een atoomafname op de sema die resulteert in een negatief getal aan dat de beller moet wachten. Een atomaire toename van de sema die resulteert in nul of een negatief resultaat, geeft aan dat er een wachtende thread is die moet worden vrijgegeven. Zou dit, samen met een van je 'super-CS' om lijsten met gebeurtenissen te beschermen voor threads om op te wachten, in sommige gevallen een betere semafoor maken met een sneller 'geen kernel'-pad?
toegevoegd de auteur Martin James, de bron
Oh .. gebruik je de semafoor voor communicatie met stuurprogramma's, dat wil zeggen. beperkte systeemoproepen toch, of alleen voor inter-thread comms in user-space?
toegevoegd de auteur Martin James, de bron
Een semafoor beperkt het aantal gelijktijdige toegang tot een gedeelde bron. Een mutex serialiseert de toegang zodat gelijktijdige gebruikers moeten wachten. Welke wil je?
toegevoegd de auteur AJG85, de bron
Ja, het is een beetje raar om een ​​semafoor postblok te hebben. Maar gezien de veronderstelde manier om de ingetoetste gebeurtenissen te gebruiken, gebeurt dat alleen als de ober precies is tussen zijn fastpath (CAS) en de aanroep naar NtWaitForKeyedEvent, wat een venster zou moeten zijn van slechts een paar klokken. cycli.
toegevoegd de auteur Paolo Bonzini, de bron

4 antwoord

Windows heeft native semaforen met CreateSemaphore . Totdat en tenzij je een soort gedocumenteerd prestatieprobleem hebt op de normale manier, moet je zelfs geen rekening houden met optimalisaties die kwetsbaar of hardware-specifiek zijn.

3
toegevoegd
Ik heb een orde van grootte prestatiewinst geboekt door de aangepaste manier voor mutexen te gebruiken in plaats van Windows-kritieke secties (en het is iets sneller dan de slanke RW-vergrendelingen), en dus verwacht ik een aanzienlijke verbetering voor semaforen. . De native semaforen zijn zwaargewicht kerneloproepen, zelfs in het niet-betwiste geval, wat vrij gebruikelijk is. Een onnodige kerneloproep is ~ 10x langzamer dan een atomische bewerking die controleert of het nodig is.
toegevoegd de auteur Display Name, de bron
Het is het laatste. En ik heb er geen probleem mee dat ik specifiek ben voor x86 en x86-64, omdat ik de specificaties van de implementatiemachines beheer. Ik wil in ieder geval graag teruggaan naar mijn oorspronkelijke vraag.
toegevoegd de auteur Display Name, de bron
Als u zoveel oproepen naar synchronisatiefuncties hebt dat hun overheadkosten niet verloren gaan in de ruis, schrijft u ofwel zeer low-level code of gebruikt u synchronisatiefuncties totaal verkeerd.
toegevoegd de auteur David Schwartz, de bron

Ik denk dat zoiets als dit zou moeten werken:

// bottom 16 bits: post count
// top 16 bits: wait count
struct Semaphore { unsigned val; }

wait(struct Semaphore *s)
{
retry:
    do
        old = s->val;
        if old had posts (bottom 16 bits != 0)
            new = old - 1
            wait = false
        else
            new = old + 65536
            wait = true
    until successful CAS of &s->val from old to new

    if wait == true
        wait on keyed event
        goto retry;
}

post(struct Semaphore *s)
{
    do
        old = s->val;
        if old had waiters (top 16 bits != 0)
           //perhaps new = old - 65536 and remove the "goto retry" above?
           //not sure, but this is safer...
            new = old - 65536 + 1
            release = true
        else
            new = old + 1
            release = false
    until successful CAS of &s->val from old to new

    if release == true
        release keyed event
}

edit: that said, I'm not sure this would help you a lot. Your thread pool usually should be big enough that a thread is always ready to process your request. This means that not only waits, but also posts will always take the slow path and go to the kernel. So, counting semaphores are probably the one primitive where you do not really care about a userspace-only fastpath. Stock Win32 semaphores should be good enough. That said, I'm happy to be proven wrong!

2
toegevoegd

Ik stem op je eerste idee, bijvoorbeeld kritieke sectie- en conditievariabele. Kritieke sectie is snel genoeg en het maakt gebruik van vergrendelde werking voordat het gaat slapen. Of u kunt experimenteren met SRWLocks in plaats van een kritieke sectie. Conditie variabelen (en SRWLocks) zijn erg snel - hun enige probleem is dat er geen voorwaarden zijn voor XP, maar misschien hoeft u dit platform niet te targeten.

1
toegevoegd

Qt heeft van alles, zoals QMutex, QSemaphore, die in dezelfde geest worden geïmplementeerd als wat je in je vraag hebt gepresenteerd.

Eigenlijk zou ik willen voorstellen het futex-materiaal te vervangen door de gebruikelijke door OS geleverde synchronisatieprimitieven; het zou niet veel uit moeten maken, want dat is sowieso het langzame pad.

0
toegevoegd
Ik moet hieraan toevoegen dat Qt ook de nodige atomaire bewerkingen levert die nodig zijn voor het bouwen van uw eigen synchronisatiemechanisme (het meest opvallend vergelijken en verwisselen).
toegevoegd de auteur Ringding, de bron