[c++ pthread] probleem met broadcasten van een signal

[Arjan]

Ik heb er nu lang genoeg mee zitten stoeien, ik kom er niet uit..

zoals wel meerdere hier op GoT ben ik bezig met een programma voor Programming Contest Nieuwe Stijl: Contest 4

Ik heb echter een probleem dat niet direct met de contest zelf te maken heeft, dus ik hoop dat jullie mij kunnen helpen

Het idee is dat de main thread enkele worker-threads start.
Als er dan werk is, dan word er een signal gebroadcast waardoor de workers kunnen gaan vechten om de data te verwerken.

Het probleem is echter dat er steeds maar 1 thread reageert op het signal.. Ik heb de betreffende calls wat info laten printen voor de duidelijkheid.

void* handleJobs(void*):89 Wait for signal 0x8051560 0x9f84038
void* handleJobs(void*):89 Wait for signal 0x8051560 0x9f84008
void* handleJobs(void*):89 Wait for signal 0x8051560 0x9f84050
void* handleJobs(void*):89 Wait for signal 0x8051560 0x9f840c8
void* handleJobs(void*):89 Wait for signal 0x8051560 0x9f84068
void* handleJobs(void*):89 Wait for signal 0x8051560 0x9f84080
void* handleJobs(void*):89 Wait for signal 0x8051560 0x9f84098
void* handleJobs(void*):89 Wait for signal 0x8051560 0x9f840b0
void* handleJobs(void*):89 Wait for signal 0x8051560 0x9f84020
void* handleJobs(void*):89 Wait for signal 0x8051560 0x9f840e0

Hier zie je dat er 10 threads gemaakt worden en dat ze elk staan te wachten op een signal ( 0x8051560 )
Het tweede adres wat geprint wordt geeft aan welke mutex er gebruikt wordt.

size_t JobList::run():202 Broadcas signal sent 0x8051560
size_t JobList::run():217 Wait for signal 0x80515a0 0x8051534

Hier geeft de main thread de opdracht om werk te gaan verzetten.
Je kan zien dat het juiste signal, namelijk 0x8051560 gebroadcast wordt. ( pthread_cond_broadcast )
Daarna gaat de main thread wachten tot er een signal komt die aangeeft dat de workers klaar zijn.

void* handleJobs(void*):89 Signal received 0x8051560 0x9f84008
void* handleJobs(void*):89 Wait for signal 0x8051560 0x9f84008

Hier zie je de eerste thread, namelijk die met het laagste mutex adres, 0x9f84008, het signal ontvangt.
Deze gaat vervolgens aan de slag totdat ie klaar is en weer opnieuw op een signal gaat staan wachten.

size_t JobList::run():217 Signal received 0x80515a0 0x8051534
size_t JobList::run():202 Broadcas signal sent 0x8051560
size_t JobList::run():217 Wait for signal 0x80515a0 0x8051534
void* handleJobs(void*):89 Signal received 0x8051560 0x9f84008
void* handleJobs(void*):89 Wait for signal 0x8051560 0x9f84008
size_t JobList::run():217 Signal received 0x80515a0 0x8051534
size_t JobList::run():202 Broadcas signal sent 0x8051560

Zoals je ziet gaat dit zo verder. De negen andere threads worden dus nooit aangetrapt!

opsomming in pseudo code:

code:

thread {
    while(running) {
        
        wacht op signal A

        doe iets met data

        stuur signal B
    }
}

main {

    creëer enkele threads

    prepareer data

    stuur signal A

    wacht op signal B
}

Het hele systeem werkt zoals verwacht, met als uitzondering dat er dus maar 1 thread gebruikt wordt, waardoor het hele idee een beetje teniet gedaan wordt.

Als iemand enig idee heeft waarom er maar 1 thread gebruikt wordt, hoor ik het graag

Voor wie het intereseert, ik test deze code op een MBP 5.1 met Ubuntu 8.10

[.oisyn]

Aan je pseudocode is het vrij simpel. De main thread kickt een job en wacht vervolgens op z'n output. In de tussentijds doet ie niets, en worden er ook geen andere signals gestuurd. Maar wellicht mist er een loopje in je pseudocode?

[Arjan]

.oisyn schreef op maandag 15 december 2008 @ 18:33:
Aan je pseudocode is het vrij simpel. De main thread kickt een job en wacht vervolgens op z'n output. In de tussentijds doet ie niets, en worden er ook geen andere signals gestuurd. Maar wellicht mist er een loopje in je pseudocode?

in het gedeelte 'doe iets met data' zit een loop die de data afhandeld, als ik deze wat laat printen dan blijkt ook hier dat maar een van de threads er echt langskomt.

Er zijn N+1 mutexen en 2 signals verder zit er voor zover ik kan zien niks in wat de boel zou kunnen verpesten

[Patriot]

Wat .oisyn probeert te zeggen is dat het logisch is dat er maar één thread aan het werk is. Main verstuurd een signaal, dat pakt Thread1 op. Als Main dan nog een signaal stuurt dan moet die bij Thread2 aankomen. Het probleem is nu dat je Main eerst laat wachten op Thread1. Tegen de tijd dat Main dan weer een signaal stuurt is Thread1 al klaar dus die pakt meteen dat signaal weer. Je moet ervoor zorgen dat Main alweer een signaal stuurt nog voordat Thread1 klaar is.

[Arjan]

Patriot schreef op maandag 15 december 2008 @ 19:15:
Wat .oisyn probeert te zeggen is dat het logisch is dat er maar één thread aan het werk is. Main verstuurd een signaal, dat pakt Thread1 op. Als Main dan nog een signaal stuurt dan moet die bij Thread2 aankomen. Het probleem is nu dat je Main eerst laat wachten op Thread1. Tegen de tijd dat Main dan weer een signaal stuurt is Thread1 al klaar dus die pakt meteen dat signaal weer. Je moet ervoor zorgen dat Main alweer een signaal stuurt nog voordat Thread1 klaar is.

Dit is de reden dat ik pthread_cond_broadcast gebruik

code:

int pthread_cond_broadcast(pthread_cond_t *cond);

The pthread_cond_broadcast() function shall unblock all threads currently blocked on the specified condition variable cond.

[MLM]

wat me even opvalt aan je pseudocode:

vergeet niet dat als main A raised voor 10 threads en daarna op B blokt die geraised word door de eerste de beste thread, main mogelijk te vroeg klaar is.
Dus, zorg dat main op 10x B wacht

ik ben verder niet bekend met pthread, dus exact weet ik het ook niet

[Arjan]

MLM schreef op maandag 15 december 2008 @ 19:27:
wat me even opvalt aan je pseudocode:

vergeet niet dat als main A raised voor 10 threads en daarna op B blokt die geraised word door de eerste de beste thread, main mogelijk te vroeg klaar is.
Dus, zorg dat main op 10x B wacht

ik ben verder niet bekend met pthread, dus exact weet ik het ook niet

Hierin schiet mijn pseudo code inderdaad wat te kort.
In m'n echte code zal alleen de laatste thread een signal sturen

[H!GHGuY]

volgens de manpage (http://linux.die.net/man/3/pthread_cond_wait)

code:

EINVAL
    Different mutexes were supplied for concurrent pthread_cond_timedwait() or pthread_cond_wait() operations on the same condition variable.

Je mag slechts 1 mutex associeren met een condition variable.

[Zoijar]

Ik snap niet helemaal wat je precies doet. Je moet 1 en dezelfde condition variable hebben in al die threads. Die wachten daar dan op, en de main code broadcast dan dat ze allemaal mogen gaan (of signalled er eentje als er werk voor 1 is). De mutex die je meegeeft aan een cond_wait() wordt atomisch geunlocked en er wordt gewait op de conditie. Als hij dan een signal krijgt dan locked hij de mutex eerst weer. Zo kan je in een block code dat gelocked moet worden een soort van atomic "sleep" doen totdat je een wakeup krijgt.

Hoe je dat implementeert hangt af van hoe je je werk verdeeld. Ik gebruik voor bijna alles altijd een producer-consumer buffer: Wikipedia: Producer-consumer problem die kan je perfect implementeren met een pthreads condition variable. Een enkele mutex voor de class monitor die je steeds eerst locked, en die release je dan op een cond_wait. De items die je daarddan in plaatst zijn packetjes die een job description bevatten. Bijvoorbeeld block coordinaten in een plaatje waar je image processing op draait of een pointer naar een tree node van waaruit je naar beneden moet zoeken.

[ Voor 11% gewijzigd door Zoijar op 15-12-2008 20:46 ]

[Arjan]

H!GHGuY schreef op maandag 15 december 2008 @ 20:08:
volgens de manpage (http://linux.die.net/man/3/pthread_cond_wait)

code:

EINVAL
    Different mutexes were supplied for concurrent pthread_cond_timedwait() or pthread_cond_wait() operations on the same condition variable.

Je mag slechts 1 mutex associeren met een condition variable.

Ah, die had ik even gemist.. kijken of ik daar omheen kan werken


@ Zoijar, het probleem ontstaat omdat ik de threads niet steeds opnieuw wil creeeren zodra ik data heb. Aan de andere kant heb ik ook niet altijd data die verwerkt moet worden en sowieso wisselt de data bron regelmatig.
Voordat ik de bron kan wisselen moet ik zeker weten dat er geen thread aan het werken is, waardoor ik weer enkele mutexen extra nodig heb..

[Zoijar]

Arjan schreef op maandag 15 december 2008 @ 22:23:
@ Zoijar, het probleem ontstaat omdat ik de threads niet steeds opnieuw wil creeeren zodra ik data heb. Aan de andere kant heb ik ook niet altijd data die verwerkt moet worden en sowieso wisselt de data bron regelmatig.
Voordat ik de bron kan wisselen moet ik zeker weten dat er geen thread aan het werken is, waardoor ik weer enkele mutexen extra nodig heb..

Ideaal voor producer-consumer Verschillende bronnen die op onregelmatige momenten werk genereren en verschillende workers die dat afhandelen. Threads creeer je niet opnieuw, ze wachten gewoon op de buffer tot er werk is. Na een bepaalde batch van werk zet je gewoon een barrier op de producers, en eventueel een conditional wait tot de buffer leeg is.

Is een barrier niet sowieso wat je in de start post zoekt? (ik snap het nog steeds niet helemaal hoor. Zonder precies te vertellen wat je wilt doen blijft het gokken met dit soort problemen. Ik snap bv niet waarom elke thread bij jou een mutex heeft?)

Arjan schreef op maandag 15 december 2008 @ 19:33:
Hierin schiet mijn pseudo code inderdaad wat te kort.
In m'n echte code zal alleen de laatste thread een signal sturen

Hoe stuurt alleen "de laatste" een signal? Hoe weet je welke dat is? Oh en let ook nog op spurious wakeup, zeker op linux.

[ Voor 13% gewijzigd door Zoijar op 16-12-2008 09:44 ]

[Arjan]

Zoijar schreef op dinsdag 16 december 2008 @ 09:14:
[...]

Ideaal voor producer-consumer Verschillende bronnen die op onregelmatige momenten werk genereren en verschillende workers die dat afhandelen. Threads creeer je niet opnieuw, ze wachten gewoon op de buffer tot er werk is. Na een bepaalde batch van werk zet je gewoon een barrier op de producers, en eventueel een conditional wait tot de buffer leeg is.

Is een barrier niet sowieso wat je in de start post zoekt? (ik snap het nog steeds niet helemaal hoor. Zonder precies te vertellen wat je wilt doen blijft het gokken met dit soort problemen. Ik snap bv niet waarom elke thread bij jou een mutex heeft?)

ik ben niet bekend met een barrier, dus zodra m'n internet weer werkt zal ik dit zeker gaan uitzoeken

Elke thread heeft bij mij een mutex omdat ik bepaalde data moet kunnen afschermen voor alle threads, maar de threads mogen er afzonderlijk wel tegelijk bij kunnen. Dit is overigens een setup die ik inmiddels al geschrapt heb, waardoor de afzonderlijke mutexen inderdaad kunnen verdwijnen.

[...]

Hoe stuurt alleen "de laatste" een signal? Hoe weet je welke dat is? Oh en let ook nog op spurious wakeup, zeker op linux.

De laatste is niet zozeer de laatste thread, maar diegene die ontdekt dat ie t laatste item heeft afgehandeld.

Spurious wakeup voorkom ik door alleen maar te signalen vanuit een locked state, volgens mij moet dat genoeg zijn..

[.oisyn]

Ik implementeer een producer-consumer met meerdere consumers gewoon met 2 semaphores en een ringbuffer waar de job data in staat. De consumers wachten op de read-semaphore die aangeeft hoeveel jobs er in de buffer staan, en de producer wacht op de write-semaphore die het aantal lege plekken in de ringbuffer voorstelt. Uiteraard released een consumer de write-semaphore bij het pakken van een job en de producer released de read-semaphore na het toevoegen van een job.

Verder heb je nog een read- en write-mutex nodig voor de toegang tot de buffer, hoewel ik daar meestal een lockless implementatie voor gebruik.

[Zoijar]

Arjan schreef op dinsdag 16 december 2008 @ 10:53:
ik ben niet bekend met een barrier, dus zodra m'n internet weer werkt zal ik dit zeker gaan uitzoeken

Een barrier heeft een operatie "wait". Elke thread individueel roept die aan en wacht en gaat dan pas verder als elke thread wait heeft aangeroepen. Hier wait bijvoorbeeld elke worker thread voor hij begint in de barrier, en de master roept als laatste wait aan als hij klaar is met data maken. Dan begint alles op dat moment te draaien.

Elke thread heeft bij mij een mutex omdat ik bepaalde data moet kunnen afschermen voor alle threads, maar de threads mogen er afzonderlijk wel tegelijk bij kunnen. Dit is overigens een setup die ik inmiddels al geschrapt heb, waardoor de afzonderlijke mutexen inderdaad kunnen verdwijnen.

Hmm lastig ontwerp. Soort reader-writer mutex (kan je ook eens opzoeken).

Spurious wakeup voorkom ik door alleen maar te signalen vanuit een locked state, volgens mij moet dat genoeg zijn..

Nee, niet genoeg, maar dat is een kwestie van een loopje om je condition wait.

Ik zou toch eens kijken naar producer consumer. Dat is een behoorlijke standaard manier om werk te verspreiden over meerdere slaves. Het grote voordeel is dat je weet dat zo'n implementatie correct is. Dat werkt zo veel makkelijker. Alle synchronisatie staat dan ook op een plek

.oisyn schreef op dinsdag 16 december 2008 @ 11:40:
Ik implementeer een producer-consumer met meerdere consumers gewoon met 2 semaphores en een ringbuffer waar de job data in staat. De consumers wachten op de read-semaphore die aangeeft hoeveel jobs er in de buffer staan, en de producer wacht op de write-semaphore die het aantal lege plekken in de ringbuffer voorstelt. Uiteraard released een consumer de write-semaphore bij het pakken van een job en de producer released de read-semaphore na het toevoegen van een job.

Verder heb je nog een read- en write-mutex nodig voor de toegang tot de buffer, hoewel ik daar meestal een lockless implementatie voor gebruik.

Wat lijken we toch weer op elkaar, zo doe ik dat eigenlijk ook altijd (als in, zo heb ik dat ooit gedaan en dat gebruik ik nog steeds)

[Arjan]

Zoijar schreef op dinsdag 16 december 2008 @ 13:02:
[...]

Een barrier heeft een operatie "wait". Elke thread individueel roept die aan en wacht en gaat dan pas verder als elke thread wait heeft aangeroepen. Hier wait bijvoorbeeld elke worker thread voor hij begint in de barrier, en de master roept als laatste wait aan als hij klaar is met data maken. Dan begint alles op dat moment te draaien.

Dat is inderdaad wat ik probeerde te bouwen

Ik zou toch eens kijken naar producer consumer. Dat is een behoorlijke standaard manier om werk te verspreiden over meerdere slaves. Het grote voordeel is dat je weet dat zo'n implementatie correct is. Dat werkt zo veel makkelijker. Alle synchronisatie staat dan ook op een plek

Ik denk inderdaad dat dit een veel makkelijkere implementatie is van wat ik wil bereiken. Tja, soms zit je nu eenmaal met een bepaald idee in je kop dat je wil uitwerken..

en soms is dat idee gewoon slecht

[Zoijar]

Arjan schreef op dinsdag 16 december 2008 @ 13:44:
Ik denk inderdaad dat dit een veel makkelijkere implementatie is van wat ik wil bereiken. Tja, soms zit je nu eenmaal met een bepaald idee in je kop dat je wil uitwerken..

en soms is dat idee gewoon slecht

Ach, dat heb ik ook vrijwel elke dag. Het aantal keren dat ik sommige stukken code herschrijf... toch weer wat geleerd, niks mis mee Met synchronisatie kan je beter vast houden aan bestaande concepten. Zelf op laag niveau met mutexes etc gaan werken gaan bijna altijd wel ergens fout. En het testen is zo verdomd lastig. Laatste keer dat ik zelf iets had gemaakt kwam ik er pas na 3 maanden oid achter dat ik steeds een frame achter lag, en dat kwam door een soort van race conditie... toen toch maar gewoon standaard producer-consumer gebruikt