[globaal, C++] Non blocking thread synchronisatie

[Verwijderd]

Hallo,

Ik ben op zoek naar informatie over het onderwerp "Non blocking thread synchronisatie".

Ik zit met een linked list die door meerdere treads benaderd kan worden. Deze communicatie moet dus gesynchroniseerd worden. Het probleem is dat 1 thread critisch is en dus onder geen geval geblokkeerd mag worden door de ander.

Nou blijken er methoden voor te bestaan die dit oplossen. CAS / CAS2 Alleen kan ik erg weinig informatie vinden over deze methoden. Ik zie nergens een voorbeeldje hoe het gebruikt word in c++ bijvoorbeeld.

Wat is dit CAS / CAS2 precies? In de MSDN vind ik er in ieder geval niets over...

mzzls

[MSalters]

MSDN? Dan is dit is fundamenteel onmogelijk, sorry. Als een niet-critische thread bezig is met de list dan wordt de list geblokeerd gedurende de operatie. Aangezien Windows geen atomaire operaties heeft voor linked lists zal er een mutex moeten worden gebruikt. Die kan gelockt zijn, en dan blokkeert de critische thread.

Nou geloof ik er niks van dat je een critische thread hebt die niet geblokkeerd mag worden. Kom op, onder Windows? Zoiets doe je met een RTOS.

[Akerboom]

ik zou het gewoon met twee seinpalen doen. 1 voor de belangrijke thread en 1 voor de linked list.
Als de belangrijke thread weer actief wordt zal deze seinpaal 1 aanzetten... alle andere threads moeten nu wachten op deze seinpaal. De tweede seinpaal voor de linked list.

Zo is de kans weer een beetje kleiner dan bij slechts 1 mutex voor de linked list.

Probeer de operatie door de andere threads zo kort mogelijk te houden en bijvoorbeeld diskoperaties te doen voordat je de linked list aanspreekt.

[Verwijderd]

Nou het lijkt me gewoon een interessante techniek, zou mooi staan bij mijn afstuderen

deze link omschrijft precies wat ik wil maar kom er niet op

http://portal.acm.org/cit...tal&CFID=11111111&CFTOKEN

Niemand info over "Compare And Swap"???

De critische thread is een Callback van de ASIO driver van een geluidskaart. er zijn situaties te bedenken dat de functie binnen 4 milisec terug moet zijn. Das wel een poos maaja je weet het maar nooit met windows he...

[Infinitive]

Voor de geïnteresseerden: download het diktaat (postscript) van het vak Gedistribueerd Programmeren en check de laatste hoofdstukken.

Bedenk wel dat je systeem bepaalde atomaire instructies moet aanbieden (zoals bijv. compare&swap), anders heeft het nog geen zin.

Ander probleem is dat je thread zo wie zo door windows onderbroken wordt voor onbepaalde tijd, dus ja... tenzij je code op kernel niveau uitvoert, dan zou ik het niet weten.

[ Voor 50% gewijzigd door Infinitive op 27-05-2004 16:37 ]

[.oisyn]

MSalters schreef op 27 mei 2004 @ 16:15:
Aangezien Windows geen atomaire operaties heeft voor linked lists zal er een mutex moeten worden gebruikt.

Er is wel (gelimiteerde) support voor gesynchronizeerde linked lists vanaf windows XP

InitialiseSList, InterlockedPushEntrySList, InterlockedPopEntrySList, InterlockedFlushList

Infinitive schreef op 27 mei 2004 @ 16:33:
Bedenk wel dat je systeem bepaalde atomaire instructies moet aanbieden (zoals bijv. compare&swap), anders heeft het nog geen zin.

Windows heeft daar functies voor, zoals bijvoorbeeld InterlockedCompareExchange

[ Voor 30% gewijzigd door .oisyn op 28-05-2004 15:39 ]

[curry684]

MSalters schreef op 27 mei 2004 @ 16:15:
Aangezien Windows geen atomaire operaties heeft voor linked lists zal er een mutex moeten worden gebruikt.

Oh?

Ik heb hier toch echt InterlockedPopEntrySList en z'n kornuiten in mijn MSDN library staan:

The InterlockedPushEntrySList function inserts an item at the front of a singly linked list. Access to the list is synchronized on a multiprocessor system.

Om volledig te zijn:

Interlocked Singly Linked Lists

The Interlocked Singly Linked Lists (SLists) ease the task of insertion and deletion from a linked list. They are implemented using a nonblocking algorithm to provide atomic synchronization, increase system performance, and avoid problems such as priority inversion and lock convoys.

Singly linked lists (SLists) are straightforward to implement and use in 32-bit code. However, it is challenging to implement them in 64-bit code because the amount of data exchangeable by the native interlocked exchange primitives is not double the address size, as it is in 32-bit code. Therefore, SLists enable porting high-end scalable algorithms to Windows.

Applications can use SLists by calling the InitializeSListHead function to initialize the head of the list. To insert items into the list, use the InterlockedPushEntrySList function. To delete items from the list, use the InterlockedPopEntrySList function.

Enige nadeel is: WinXP of Win2k3 required

edit:
dammit oisyn kruip eens niet voor terwijl ik netjes alle docs erbij kopieer en formatteer

[ Voor 4% gewijzigd door curry684 op 28-05-2004 15:50 ]

[Olaf van der Spek]

Verwijderd schreef op 27 mei 2004 @ 16:08:
Ik zit met een linked list die door meerdere treads benaderd kan worden. Deze communicatie moet dus gesynchroniseerd worden. Het probleem is dat 1 thread critisch is en dus onder geen geval geblokkeerd mag worden door de ander.

Dat is wel erg kritisch, of duren de list operaties zo lang?
Kan die kritisch thread gewoon verder met andere taken of wil je echt toegang tot die list hebben?

[Verwijderd]

Thanx voor de reacties... Ik had net even geen zin meer in het verslag, dus ik heb me nog even verdiept in het onderwerp...

ik heb nog wat informatie erover gevonden...
486+ processoren zijn uitgerust met de instructie:

CMPXCHG

Met deze instructie kun je zo'n Compare And Swap fixen... Ik heb net ook even wat in Visual C++ geprobeerd om het te fixen maar dat wil nog niet zo lukken...

dit is de code ( N.B. ik ben geen assembly gast)

code:

int CList::CompareAndSwap(void* pvSource, void* pvDest)
{
    int result=0;
    __asm 
    {
        mov eax,pvSource
        lock cmpxchg pvSource,pvDest
        mov result,ZF
    }
    return result;
}

Helaas krijf ik de volgende error:

error C2415: improper operand type


Iemand suggesties?

mzzls

[Verwijderd]

Tot nu heb ik deze code

code:

int CList::CompareAndSwap(CNode** _pStart, CNode* _pNode)
{
    int result=0;
    CNode* tmp = *_pStart;
    __asm 
    {
        mov eax, tmp
        mov ebx, _pNode
        mov [ebx]_pNode.mpNext, eax
        
        lock cmpxchg tmp, ebx
    }
    return (*_pStart == _pNode);
}

Dit werkt op zich goed. Het enige probleem dat er nog is, is dat hij de hele tijd met een copie van de pointer zit te werken i.p.v. de echte pointer.

mpStart is een pointer naar de 1ste node van de lijst. Om deze pointer te bereiken vraag ik in de functie header **. Anders maakt hij immers een kopie van die pointer met dezelfde inhoud aan. Nou heb ik het adres dat gewijzigd moet worden " *_pStart "... Wanneer ik zoals in bovenstaande code een tijdelijke variablela maak maakt hij wederom een kopie van die pointer. ik werk dus niet met de *_pStart!!!

Mijn vraag is dan ook: Hoe kom ik in godsnaam bij de *_pStart in assembly?

B.T.W. *_pStart invullen doet het uiteraard niet...

[curry684]

Verwijderd schreef op 02 juni 2004 @ 10:53:
Thanx voor de reacties... Ik had net even geen zin meer in het verslag, dus ik heb me nog even verdiept in het onderwerp...

ik heb nog wat informatie erover gevonden...
486+ processoren zijn uitgerust met de instructie:

CMPXCHG

Met deze instructie kun je zo'n Compare And Swap fixen... Ik heb net ook even wat in Visual C++ geprobeerd om het te fixen maar dat wil nog niet zo lukken...

Waarom doe je moeilijk met assembly terwijl we al lang en breed hebben vermeld dat InterlockedCompareExchange dit ook doet zonder geklooi en als future-compatible onderdeel van de Win32 API?

[Verwijderd]

Ow... mooi,

ofja niet zo mooi, had het niet gelezen dat: InterlockedCompareExchange... maar goed als deze functie precies zo werkt vind ik het goed zal het eens testen...

thanx mzzls...