[C++] Geheugen managen over meerdere threads

[Arjan]

Ik loop op m'n werk nu tegen een probleem aan waarbij ik mij afvraag of er een elegante oplossing is voor een lastig probleem

Het probleem is als volgt;

Ik heb een memorypool, die adressen uit kan geven. Deze pool kan echter groeien, hetgeen ervoor zorgt dat de uitgegeven adressen ongeldig zijn.

Dit probleem is relatief eenvoudig aan te pakken en ik heb dit gedaan door middel van een klasse die de toegang verleent.

Het probleem dat nu ontstaat is dat er meerdere threads met de data aan de slag kunnen. Dit betekend dat het verlenen van toegang nu afgeschermd moet worden met een mutex, omdat anders het risico bestaat dat er niet correct opgeslagen wordt hoeveel instanties er met de data bezig zijn.

In de praktijk blijkt dit een redelijke performance-hit te vormen aangezien er heel vaak ge(un)lockt moet worden.

Aangezien de memorypool maar weinig van grootte veranderd zou het mogelijk moeten zijn om het locken tot een minimum te beperken. *

Graag zou ik met jullie discussiëren of er een methode bestaat om correct deterministisch gedrag te houden, maar niet voor elke toegang naar een adres uit de pool een lock te zetten.

Als er vragen of onduidelijkheden zijn hoor ik dat graag

* dit is een aanname die ik graag bevestigd/ontkracht zie

[Sebazzz]

Sowieso, als ik mij niet vergis is een mutex system-wide, dus dat is waarschijnlijk ook een dure iets om aan te maken. Zijn er geen andere vormen van locking die je kan gebruiken, procesbreed?

[Arjan]

Sebazzz schreef op maandag 06 september 2010 @ 22:59:
Sowieso, als ik mij niet vergis is een mutex system-wide, dus dat is waarschijnlijk ook een dure iets om aan te maken. Zijn er geen andere vormen van locking die je kan gebruiken, procesbreed?

Volgens mij is dit implementatie afhankelijk, en zijn system-wide mutexen eerder uitzondering dan regel.
Daarnaast worden de mutexen natuurlijk aangemaakt per pool, niet per accessor-instance.

[l1dert]

Arjan schreef op maandag 06 september 2010 @ 22:52:

Ik heb een memorypool, die adressen uit kan geven. Deze pool kan echter groeien, hetgeen ervoor zorgt dat de uitgegeven adressen ongeldig zijn.

[...]

Het probleem dat nu ontstaat is dat er meerdere threads met de data aan de slag kunnen. Dit betekend dat het verlenen van toegang nu afgeschermd moet worden met een mutex, omdat anders het risico bestaat dat er niet correct opgeslagen wordt hoeveel instanties er met de data bezig zijn.

Als ik het dus goed begrijp allokeer je eerst een blok geheugen, dan geef je adressen uit binnen dat blok. Wanneer het blok vol is allokeer je een nieuw groter blok en kopieer je alles wat in het eerste blok stond en geef je die vrij?

Wat bedoel je met dat meerdere threads met de data aan de slag gaan. Het maakt nogal uit of al die threads de data alleen lezen of ook bewerken. Als er alleen gelezen wordt hoeft dat niet thread safe, maar zodra er ook geschreven wordt moet dat wel thread safe gebeuren.

De mutex houd niet bij hoeveel instanties er met data bezig zijn, maar geeft alleen 1 thread tegelijk toegang tot die data. Alle andere threads moeten dus wachten. Wat me nu niet duidelijk is of je een mutex gebruikt voor alle data of dat je per deel van je grote memory blok een mutex toekent. Dat laatste lijkt me efficiënter, mits die delen niet te klein zijn.

[Arjan]

l1dert schreef op maandag 06 september 2010 @ 23:13:
[...]


Als ik het dus goed begrijp allokeer je eerst een blok geheugen, dan geef je adressen uit binnen dat blok. Wanneer het blok vol is allokeer je een nieuw groter blok en kopieer je alles wat in het eerste blok stond en geef je die vrij?

klopt

Wat bedoel je met dat meerdere threads met de data aan de slag gaan. Het maakt nogal uit of al die threads de data alleen lezen of ook bewerken. Als er alleen gelezen wordt hoeft dat niet thread safe, maar zodra er ook geschreven wordt moet dat wel thread safe gebeuren.

Helaas maakt lezen/schrijven niet uit, stel je maar eens voor wat er gebeurt als je vrolijk blijft lezen uit een blok data dat reeds is teruggegeven aan het OS...

De mutex houd niet bij hoeveel instanties er met data bezig zijn, maar geeft alleen 1 thread tegelijk toegang tot die data. Alle andere threads moeten dus wachten. Wat me nu niet duidelijk is of je een mutex gebruikt voor alle data of dat je per deel van je grote memory blok een mutex toekent. Dat laatste lijkt me efficiënter, mits die delen niet te klein zijn.

Momenteel heb ik een setup waarbij er twee mutexen per pool zijn.
Een mutex wordt gelockt zodra er een adres uitgegeven is, de ander wordt gebruikt om een counter te locken zodat deze kan bijhouden hoeveel adressen er uitgegeven zijn. Zodra er geen uitgegeven adressen meer zijn wordt de eerste mutex vrijgegeven.

[l1dert]

Maar de adressen die je uitgeeft zijn dat pointers naar je memorypool of pointers naar delen binnen die memorypool? Als ze allemaal naar het begin van de pool verwijzen heb je dus een vorm van reference counting toegepast zoals ook in objective c gedaan wordt.

Dat je een mutex toepast op de counter snap ik, je wilt niet dat twee threads tegelijk een min of plus operatie doen, maar die ander snap ik niet. Het lijkt me logischer dat je een mutex over je data toepast. Dus dat een thread bij toegang een lock toepast en aan het eind de data weer vrijgeeft.

[Arjan]

l1dert schreef op maandag 06 september 2010 @ 23:31:
Maar de adressen die je uitgeeft zijn dat pointers naar je memorypool of pointers naar delen binnen die memorypool? Als ze allemaal naar het begin van de pool verwijzen heb je dus een vorm van reference counting toegepast zoals ook in objective c gedaan wordt.

De pointers wijzen naar delen in de memorypool.

Dat je een mutex toepast op de counter snap ik, je wilt niet dat twee threads tegelijk een min of plus operatie doen, maar die ander snap ik niet. Het lijkt me logischer dat je een mutex over je data toepast. Dus dat een thread bij toegang een lock toepast en aan het eind de data weer vrijgeeft.

Als je de data lockt dan kan er maar een thread tegelijk aan werken. Terwijl er misschien wel meerdere bitmaps in de pool staan die tegelijk benaderd mogen worden.

[HMS]

Waarom gebruik je 2 mutexen? Als een thread de eerste mutex locked, dan is de hele pool toch gelocked en moeten alle andere threads wachten?

Of is de eerste mutex alleen voor een acquire van de data en de tweede om de counter bij te houden?

Dan nog is er altijd maar 1 thread die bij de pool kan en heeft het geen zin om meerdere threads te gebruiken.

Het klinkt alsof je de volgende constructie hebt:

code:

Thread1 -> Mutex_1.lock -> success
Thread1 -> Acquire pointer
Thread2 -> Mutex_1.lock -> blocked
Thread1 -> Mutex_2.lock / increment counter / unlock
Thread1 -> Operatie op pointer
Thread1 -> Mutex_2.lock / decrement counter / unlock
Thread1 -> Mutex_1.unlock
Thread2 -> wake up

Voor de duidelijkheid de threads er maar bij gezet ;-)

[Arjan]

De threads blokkeren elkaar niet, een mogelijk scenario is als volgt.

code:

T1: m1.lock
T1: count++ == 0 dan m2.lock
T1: m1.unlock
T1: m2 is gelockt en de teller is op de hoogte van T1 dus mag T1 nu pointers opvragen
T2: m1.lock
T2: count++ != 0 dus geen verandering aan m2
T2: m1.unlock
T2: de teller is op de hoogte van T2 en m2 is nog gelockt dus ook T2 mag nu pointers opvragen

Als de threads de pointers weer gaan teruggeven dan telt de counter weer af. Zodra deze op 0 staat wordt m2 vrijgegeven. Zodra dit is gebeurd mag de memorypool haar geheugen gaan aanpassen

[.oisyn]

Sowieso hoeft er geen lock om de count, die kun je gewoon lockless threadsafe aanpassen. Maar je moet toch echt even duidelijker beschrijven wat de aard is van de allocaties. Kun je niet wat pseudocode plaatsen? En wordt een blok binnen een pool ook weer vrijgegeven?

[BoAC]

.oisyn schreef op dinsdag 07 september 2010 @ 12:53:
Sowieso hoeft er geen lock om de count, die kun je gewoon lockless threadsafe aanpassen. Maar je moet toch echt even duidelijker beschrijven wat de aard is van de allocaties. Kun je niet wat pseudocode plaatsen? En wordt een blok binnen een pool ook weer vrijgegeven?

Ook op systemen met meerdere cores? Op een singlecore machine is dit geen probleem idd

[Arjan]

.oisyn schreef op dinsdag 07 september 2010 @ 12:53:
Sowieso hoeft er geen lock om de count, die kun je gewoon lockless threadsafe aanpassen.

Hoe gaat dat in z'n werk? Zou wel een hoop schelen...

Maar je moet toch echt even duidelijker beschrijven wat de aard is van de allocaties.

Het is gewoon een geheugenmanager, verder niet heel spannend.

Kun je niet wat pseudocode plaatsen? En wordt een blok binnen een pool ook weer vrijgegeven?

Het locken zorgt er alleen maar voor dat het resizen van de pool (thread)safe gebeurt!

alle uitgegeven pointers mogen dus kris kras door elkaar heen gebruikt worden. Wanneer het echter tijd is om de pool te resizen zullen eerst alle pointers teruggegeven moeten worden, dit om te voorkomen dat pointers naar data die niet meer bestaat gebruikt worden

[.oisyn]

BoAC schreef op dinsdag 07 september 2010 @ 13:48:
[...]

Ook op systemen met meerdere cores? Op een singlecore machine is dit geen probleem idd

Je moet natuurlijk niet gewoon "count++" doen, maar alle multi-CPU systemen hebben wel functionaliteit voor atomaire operaties (moet ook wel, anders kunnen ze iets als een mutex nooit ondersteunen). Zie bijvoorbeeld InterlockedIncrement() als je voor win32 programmeert.

Arjan schreef op dinsdag 07 september 2010 @ 13:51:
Het is gewoon een geheugenmanager, verder niet heel spannend.

Nou ja, als je bijvoorbeeld alleen maar alloceert (en nooit individuele blokken dealloceert, alleen maar alles tegelijk) dan is dat ook vrij gemakkelijk lockless te implementeren. Ik vroeg me dus af wat je allemaal precies doet bij het alloceren/dealloceren. Moet je echt een blok gaan zoeken, of ophoog je alleen een pointer, of...

[ Voor 34% gewijzigd door .oisyn op 07-09-2010 14:46 ]

[Arjan]

.oisyn schreef op dinsdag 07 september 2010 @ 14:39:
[...]

Je moet natuurlijk niet gewoon "count++" doen, maar alle multi-CPU systemen hebben wel functionaliteit voor atomaire operaties (moet ook wel, anders kunnen ze iets als een mutex nooit ondersteunen). Zie bijvoorbeeld InterlockedIncrement() als je voor win32 programmeert.

Via je suggestie ben ik bij __sync_fetch_and_add en zijn vriendjes uitgekomen, ik ga er eens mee spelen

Nou ja, als je bijvoorbeeld alleen maar alloceert (en nooit individuele blokken dealloceert, alleen maar alles tegelijk) dan is dat ook vrij gemakkelijk lockless te implementeren. Ik vroeg me dus af wat je allemaal precies doet bij het alloceren/dealloceren. Moet je echt een blok gaan zoeken, of ophoog je alleen een pointer, of...

De blokken kunnen individueel uitgedeeld worden, het lijkt mij dat ik tenminste één lock nodig heb om alle blokken te informeren dat de pool gaat herorganiseren

[MSalters]

Het probleem is vermoedelijk dat je (alleen) een exclusive lock (mutex = mutually exclusive) gebruikt. Elke thread die de mutex wil locken, ook al is het maar voor een simpele read, sluit dan meteen alle andere threads uit.

Dat is natuurlijk niet wat je wil. De memory manager moet bij een herallocatie wel een exclusive lock nemen. Alle andere gebruikers nemen alleen shared locks. Op die manier blokkeren je worker threads alleen bij een herallocatie, en niet op elkaar.

Op Windows (vanaf Vista) doe je dit met behulp van een slim reader/writer (SRW) lock.

[Arjan]

MSalters schreef op woensdag 08 september 2010 @ 13:15:
[...]
Op Windows (vanaf Vista) doe je dit met behulp van een slim reader/writer (SRW) lock.

Dat klinkt leuk, zo'n SRW lock, maar mijn code moet werken op windows xp/vista/7, osx, en linux

ik heb de volgende implementatie gemaakt:

C++:

class SharedLock
{
    public:

        void lock()
        {
            if ( ! __sync_fetch_and_add( &_lockCount, 1 ) )
            {
                _mutex.lock();
            }
        }

        void unlock()
        {
            if ( ! __sync_sub_and_fetch( &_lockCount,1 ) )
            {
                _mutex.unlock();
            }
        }

        void lockExclusive()
        {
            _mutex.lock();
        }

        void unlockExclusive()
        {
            _mutex.unlock();
        }

    private:

        unsigned int _lockCount;
        Mutex _mutex;
};

Ik zie hier het volgende nadeel, wat ik graag indien mogelijk nog zou optimaliseren;

C++:

SharedLock sharedLock;

thread1
{
    while( vaak )
    {
        sharedLock.lock()
        // doe iets
        sharedLock.unlock()
    }
}

main
{
    while( af en toe )
    {
        sharedLock.lockExclusive();
        // doe iets
        sharedLock.unlockExclusive()
    }
}

In deze situatie zal de SharedLock::lock/unlock heel vaak effectief een call naar Mutex::lock/unlock zijn, hetgeen de prestaties niet ten goede komt.

Deze implementatie zal dus sneller werken als er vaker door meerdere threads een shared lock gehouden wordt.

Is er een manier om dit nog te optimaliseren? Double checked locking is geen optie aangezien dat volgens mij niet veilig te krijgen is in C++.

[.oisyn]

Sowieso klopt dat niet. Als iemand een exclusive lock heeft, dan moet lock() daar op wachten, ongeacht de waarde van lockCount.

[Arjan]

.oisyn schreef op donderdag 09 september 2010 @ 11:04:
Sowieso klopt dat niet. Als iemand een exclusive lock heeft, dan moet lock() daar op wachten, ongeacht de waarde van lockCount.

Zodra lockCount > 0 dan zal de mutex gelockt zijn, waardoor exclusive lock moet wachten.
Als exclusive lock de boel gelockt heeft, moet lockCount dus 0 zijn, hetgeen betekend dat een volgende call naar lock de mutex probeert te locken ( want lockCount is niet langer 0 ) waardoor lock gaat wachten op exclusive lock

[.oisyn]

Ah wacht ik zie wat je bedoelt, je lockt sowieso altijd de mutex, ook voor een reader, maar de unlocker is potentieel niet dezelfde thread als de locker. Mag dat zomaar? Onder Windows mag alleen de thread die de lock heeft verkregen een mutex of critical section releasen. Met een semaphore kan het weer wel. Ik weet niet wat voor library je gebruikt, maar dat is dus even iets om naar te kijken.

[ Voor 18% gewijzigd door .oisyn op 09-09-2010 11:31 ]

[Arjan]

.oisyn schreef op donderdag 09 september 2010 @ 11:28:
Ah wacht ik zie wat je bedoelt, je lockt sowieso altijd de mutex, ook voor een reader, maar de unlocker is potentieel niet dezelfde thread als de locker. Mag dat zomaar? Onder Windows mag alleen de thread die de lock heeft verkregen een mutex of critical section releasen. Met een semaphore kan het weer wel. Ik weet niet wat voor library je gebruikt, maar dat is dus even iets om naar te kijken.

Haha, ja daar was ik een tijdje geleden ook al achter gekomen... na veel debuggen.

Onder windows gebruik ik voor deze specifieke lock idd. een semaphore.
pthread maakt er verder geen problemen van.

Des te meer reden om te proberen bovenstaand scenerio te verbeteren, aangezien een semaphore op windows altijd een tripje naar de kernel maakt als ik me niet vergis

[H!GHGuY]

Wat je nodig hebt is een MRSW lock: Multi-Reader Single-Writer lock.
Die laat meerdere readers tegelijk _of_ 1 enkele writer.
De readers zijn dus de normale pointer users, de writer is de code die de herallocatie doet.

Interessant leesvoer:
http://www.drdobbs.com/184401515
http://www.codeproject.co...testing_spin_rwlocks.aspx
http://stackoverflow.com/.../reader-writer-locks-in-c

[ Voor 30% gewijzigd door H!GHGuY op 09-09-2010 21:09 ]

[Soultaker]

pthread biedt zelf al een read/write lock (man pthread_rwlock_init b.v.) dus die kun je onder Linux, OS X en andere POSIX-systemen waarschijnlijk het beste direct gebruiken. Die maakt (onder Linux in ieder geval) gebruik van een futex waardoor er geen system calls plaatsvinden zolang er geen contentie is.

Onder Windows kun je sinds Vista de eerder genoemde slim read/write lock gebruiken die vergelijkbare functionaliteit en performance biedt.

Dan blijft Win32 over en die is lastig. Voor zover ik weet (maar ik weet niet veel van de Win32 API) is er geen futex-achtige primitieve. Misschien kun je handmatig iets knutselen met critical sections en events, maar ik zou niet zo 1-2-3 weten hoe precies. Klopt het dat critical sections de enige synchronisatieprimitieve zijn die in user-space werken?

[ Voor 4% gewijzigd door Soultaker op 09-09-2010 22:07 ]

[.oisyn]

Ja dat klopt. Maar voor een wait moet je natuurlijk sowieso de kernel in (task switch), belangrijk is dat een uncontended lock zelf niet veel kost, en dat is op zich wel te knutselen met de atomaire operaties die win32 / x86 biedt.

.Net heeft trouwens de ReadersWriterLock die wel gewoon werkt onder XP.

[ Voor 13% gewijzigd door .oisyn op 09-09-2010 21:53 ]

[Arjan]

H!GHGuY schreef op donderdag 09 september 2010 @ 21:06:
Wat je nodig hebt is een MRSW lock: Multi-Reader Single-Writer lock.
Die laat meerdere readers tegelijk _of_ 1 enkele writer.
De readers zijn dus de normale pointer users, de writer is de code die de herallocatie doet.
[...]

duidelijk

Soultaker schreef op donderdag 09 september 2010 @ 21:25:
[...]
Dan blijft Win32 over en die is lastig. Voor zover ik weet (maar ik weet niet veel van de Win32 API) is er geen futex-achtige primitieve. Misschien kun je handmatig iets knutselen met critical sections en events, maar ik zou niet zo 1-2-3 weten hoe precies. Klopt het dat critical sections de enige synchronisatieprimitieve zijn die in user-space werken?

Ik zie zo snel niet of de critical sections er problemen van maken dat ze uit een andere thread (un)lockt kunnen worden. Als dit geen probleem is dan lijkt me dit de snelste oplossing inderdaad.

[.oisyn]

Dat doen ze dus wel

If a thread calls LeaveCriticalSection when it does not have ownership of the specified critical section object, an error occurs that may cause another thread using EnterCriticalSection to wait indefinitely.

[Arjan]

Spijtig, want mijn huidige implementatie is echt extreem traag onder win7 (mingw compiled)

Komt het topic effectief dus neer op: verzin een snelle MRSW lock onder win32..

[H!GHGuY]

In de linkjes die ik je gaf staan ook enkele codevoorbeeldjes.
Als je je even kort verdiept in de materie, kun je ongetwijfeld een degelijke implementatie verzinnen.

Tip: kijk ook even naar de pthreads implementatie in glibc:
http://sourceware.org/git/?p=glibc.git;a=tree;f=nptl

[MSalters]

Idd, gebruik gewoon boost::shared_lock / unique_lock en je hoeft je zelf niet meer druk te maken over portabiliteit.

[Soultaker]

@H!GHGuY: de pthread-implementatie lijkt heel sterk op wat Arjan zelf al had voorgesteld, maar dat werkt dus niet onder Windows omdat de pthread-implementatie gebaseerd is op een futex die in de ene thread gelockt en in een andere geunlockt wordt.

Zoals gezegd zou ik voor het geval van Windows zelf wat knutselen, bijvoorbeeld zoiets:

code:

lockRead() {
    enter(cs);
    while (writers > 0) {
        leave(cs);
        wait(writers_done);
        enter(cs);
    }
    ++readers;
    leave(cs):
}

unlockRead() {
    enter(cs);
    --readers;
    if (readers == 0 && writers > 0) set(readers_done);
    leave(cs);
}

lockWrite() {
    enter(cs);
    if (writers == 0) reset(writers_done);
    ++writers;
    while (readers > 0) {
        reset(readers_done);
        leave();
        wait(readers_done);
        enter();
    }
    leave(cs);
    lock(writer_mutex);
}

unlockWrite() {
    unlock(writer_mutex);
    enter(cs);
    --writers;
    if (writers == 0) set(writers_done);
    leave(cs);
}

Waarbij cs dus een critical section is, readers_done en writers_done condition variables (events in Win32?) zijn, en writer_mutex een simpele mutex is. Deze implementatie geeft voorang aan writers, wat vermoedelijk wenselijk is als je veel readers hebt, die anders een enkele writer zouden kunnen starven, en zorgt ervoor dat er geen system calls op het fast path liggen (wanneer er alleen contention onder readers is).

[ Voor 15% gewijzigd door Soultaker op 10-09-2010 22:02 ]

[Arjan]

Gebaseerd op de hier opgedane informatie heb ik de volgende implementatie gemaakt, die gebruikmaakt van een soort spinlock.

Ik heb er een compileerbaar stukje code van gemaakt, dat met g++ onder windows zou moeten compilen. Ik heb zelf alleen een virtuele machine beschikbaar met windows, maar het lijkt een snelle oplossing te zijn. Graag jullie commentaar.

C++:

#include <windows.h>
#include <vector>

class SharedLock
{
    public:

        SharedLock() :
            _readerCount( 0 ),
            _sharedLock( 0 ) { }

        void lock()
        {
            /* increase readerCount */
            if ( ! __sync_fetch_and_add( &_readerCount, 1 ) )
            {
                /* if there where no active readers lock the shared lock
                    by placing 1 as value */
                while( !__sync_bool_compare_and_swap( &_sharedLock, 0, 1 ) )
                {
                    /* give time to other threads */
                    Sleep( 0 );
                }
            }
        }

        void unlock()
        {
            /* decrease number of readers */
            if ( ! __sync_sub_and_fetch( &_readerCount, 1 ) )
            {
                /* if there are no readers left, unlock shared lock
                   by placing 0 as value */
                __sync_bool_compare_and_swap( &_sharedLock, 1, 0 );
            }
        }

        void lockExclusive()
        {
            /* try to lock the shared lock */
            while( !__sync_bool_compare_and_swap( &_sharedLock, 0, 1 ) )
            {
                /* give time to other threads */
                Sleep( 0 );
            }
        }

        void unlockExclusive()
        {
            /* unlock the shared lock */
            __sync_bool_compare_and_swap( &_sharedLock, 1, 0 );
        }

    private:

        unsigned int _readerCount, _sharedLock;
};

SharedLock lock;

#define THREADCOUNT 10
#define COUNT 1000000

volatile long collectors[ THREADCOUNT ];

void thread( void *rawID )
{
    size_t id = (int)rawID;
    int count = COUNT;

    while ( count-- )
    {
        lock.lock();
        collectors[ id ]++;
        lock.unlock();
    }
}

int main( int argc, char **argv )
{
    std::vector< HANDLE > threads;

    for ( size_t i = 0; i < THREADCOUNT; i++ )
    {
        DWORD thread_id;
        threads.push_back( CreateThread( 0, 0, (LPTHREAD_START_ROUTINE)thread, (void*)i, 0, &thread_id ) );
    }

    long total = 0;

    while ( total < THREADCOUNT * COUNT )
    {
        int temp = 0;
        for ( size_t i = 0; i < THREADCOUNT; i++ )
        {
            temp += collectors[ i ];
        }

        if ( temp >= COUNT || total > ( ( THREADCOUNT - 1 ) * COUNT ) )
        {
            lock.lockExclusive();

            for ( size_t i = 0; i < THREADCOUNT; i++ )
            {
                total += collectors[ i ];

                collectors[ i ] = 0;
            }

            lock.unlockExclusive();
        }
    }

    for ( std::vector< HANDLE >::iterator i = threads.begin(); i != threads.end(); i++ )
    {
        WaitForSingleObject( *i, INFINITE );
    }

    return 0;
}

[ Voor 0% gewijzigd door Arjan op 11-09-2010 10:04 . Reden: verkeerde sync functie... ]

[H!GHGuY]

Soultaker schreef op vrijdag 10 september 2010 @ 21:46:
@H!GHGuY: de pthread-implementatie lijkt heel sterk op wat Arjan zelf al had voorgesteld, maar dat werkt dus niet onder Windows omdat de pthread-implementatie gebaseerd is op een futex die in de ene thread gelockt en in een andere geunlockt wordt.

Waar haal je dat de pthread implementatie over threads heen lockt en unlockt?

Arjan schreef op zaterdag 11 september 2010 @ 10:00:

C++:

Je code is fout.
Als er 2 threads een reader lock willen nemen terwijl een writer bezig is, dan zal de 2de thread langsheen de while-lus passeren.

[ Voor 36% gewijzigd door H!GHGuY op 11-09-2010 16:47 ]

[Arjan]

Hey, goed gezien.

ik zal eens kijken of ik daar een oplossing voor kan bedenken zonder een mutex in het fast-path te introduceren

[H!GHGuY]

Arjan schreef op zaterdag 11 september 2010 @ 18:36:
Hey, goed gezien.

ik zal eens kijken of ik daar een oplossing voor kan bedenken zonder een mutex in het fast-path te introduceren

Neem de code van soultaker maar eens ter harte. Ik kon er niet meteen fouten in vinden.
Het is trouwens de klassieke code voor een MRSW.

[Soultaker]

H!GHGuY schreef op zaterdag 11 september 2010 @ 16:38:
Waar haal je dat de pthread implementatie over threads heen lockt en unlockt?

Die futex wait/signal operaties vinden in verschillende threads plaats, vandaar dat ik dat dacht, maar daar wordt de futex eigenlijk als condition variable gebruikt, dus bij een vertaling naar Win32 zou je die door een event object kunnen vervangen en dan is dat geen probleem meer, en bovendien ligt die futex toch al in het slow path dus maakt het gebruik van een kernel object minder uit. Je hebt dus gelijk dat die code wel vertaalbaar is naar Win32, al moet je dus even goed kijken welke futexes welke rol vervullen.

(De pthreads code is ook wel nice omdat 'ie, voor zover ik kon zien, ook een betere fast path heeft voor writers dan wat ik in elkaar geflanst had. Of je dat echt nodig hebt in deze situatie is een tweede.)

[Arjan]

[ faal code ]

De iets geupdate lock functie, volgens mij dekt dit de eerdere mogelijheid af, en heeft het fast-path er 'slechts' twee atomic adds bij gekregen.

Ik denk inderdaad niet dat het shared locken gaat lukken zonder CS/Mutex...

edit 2

misschien dan toch, gebruikmakend van het feit dat de lock meerdere waardes mag hebben.

code voor de shared lock:

C++:

    /* check if the lock is held by the exclusive lock, if not continue */
    while( __sync_val_compare_and_swap( &_sharedLock, 0, 2 ) == 1 )
    {
        /* give time to other threads */
        Sleep( 0 );
    }

    __sync_fetch_and_add( &_readerCount, 1 );

edit 3,

de shared unlock moet ook iets aangepast worden, voor volledigheid, hier de volledige code:

C++:

class SharedLock
{
    public:

        enum
        {
            Unlocked = 0,
            Exclusive = 1,
            Shared = 2
        };

        SharedLock() :
            _readerCount( 0 ),
            _sharedLock( 0 ) { }

        void lock()
        {
            /* check if the lock is held by the exclusive lock, if not, continue */
            while( __sync_val_compare_and_swap( &_readWriteLock, Unlocked, Shared ) == Exclusive )
            {
                /* give time to other threads */
                Sleep( 0 );
            }

            /* increase lock count */
            __sync_fetch_and_add( &_lockCount, 1 );
        }

        void unlock()
        {
            /* decrease number of readers */
            if ( ! __sync_sub_and_fetch( &_readerCount, 1 ) )
            {
                /* if there are no readers left, unlock shared lock
                   by placing 0 as value */
                __sync_bool_compare_and_swap( &_sharedLock, Shared, Unlocked );
            }
        }

        void lockExclusive()
        {
            /* try to lock the shared lock */
            while( !__sync_bool_compare_and_swap( &_sharedLock, Unlocked, Exclusive ) )
            {
                /* give time to other threads */
                Sleep( 0 );
            }
        }

        void unlockExclusive()
        {
            /* unlock the shared lock */
            __sync_bool_compare_and_swap( &_sharedLock, Exclusive, Unlocked );
        }

    private:

        unsigned int _readerCount, _sharedLock;
};

[ Voor 177% gewijzigd door Arjan op 11-09-2010 21:50 . Reden: edit4, nog maar een enum erbij gegooid ]

[H!GHGuY]

Arjan schreef op zaterdag 11 september 2010 @ 21:15:
[ faal code ]

de shared unlock moet ook iets aangepast worden, voor volledigheid, hier de volledige code:

C++:

De code is te complex geworden
Ik kan niet meer in een korte tijd de correctheid evalueren. Dat wil zeggen dat jijzelf dat over 1 maand ook niet meer kan.
Je hebt trouwens geluk dat je code enkel op x86 zal draaien. Doe dit op ppc of arm en je code gaat hard op z'n bek. (omdat een __sync instructie op x86 per definitie een memory barrier inhoudt, waar dat op andere architecturen niet per definitie is)

Maak nou maar eerst eens een rwlock (volgens de code van soultaker en de vele code die ik je gaf) en gebruik die.
Heb je daarna nog scalability problemen dan moet je echt je design wijzigen.
Bijvoorbeeld mbv een global memory pool en per-thread memory-pools.

[ Voor 15% gewijzigd door H!GHGuY op 12-09-2010 12:51 ]

[.oisyn]

H!GHGuY schreef op zondag 12 september 2010 @ 12:49:
(omdat een __sync instructie op x86 per definitie een memory barrier inhoudt, waar dat op andere architecturen niet per definitie is)

Memory barriers op de x86 bestaan niet - de x86 doet nooit out of order memory operations

[Arjan]

Na wat (synthetisch) benchmarken blijkt een CriticalSection een stuk sneller dan mijn spinlock optie.
Dus H!GHGuY kan gerust ademhalen, ik ga een shared lock bouwen volgens de opzet zoals Soultaker die geschets had

Mocht je overigens de behoefte hebben om vanuit verschillende threads de writelock te lock/unlocken in Soultakers voorbeeld, dan zul je onder windows voor de writelock een semaphore moeten inzetten. Als je dat doet dan kan mijn implementatie weer een stuk sneller zijn, aangezien de semaphores bij windows behoorlijk traag zijn

[ Voor 43% gewijzigd door Arjan op 13-09-2010 11:02 ]

[H!GHGuY]

.oisyn schreef op zondag 12 september 2010 @ 22:32:
[...]

Memory barriers op de x86 bestaan niet - de x86 doet nooit out of order memory operations

Ik weet dat je x86 behoorlijk goed kent dus please enlighten me:
Wat zijn mfence, sfence en lfence dan?
Zie ook Wikipedia: Memory ordering voor ordering rules op x86.

Voor zover ik weet houden __sync operaties (die dus ook een sync instructie prefix hebben) automatisch een fence in.

[.oisyn]

M'n info is blijkbaar wat outdated, maar volgens http://www.intel.com/Assets/PDF/manual/253668.pdf sectie 8.2.2 valt het in de praktijk alsnog wel mee - er zijn alleen reads na een store die gereordered mogen worden. Maar zodra je locked writes gebruikt heb je het probleem toch al niet, want dat is een impliciete fence.