Implementacija mutex-a

Zna li neko kako OS implementira mutex-e?

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Mi smo na fakultetu pominjali Dekerov i Pitersonov softverski algoritam.

U hardveru pak najčešće imaš CAS (Compare and swap) ili TAS (Test and set) instrukcije koje ti garantuju atomičnost i onda ih koristiš da implementiraš Spinlock. Sa tim dalje možeš da praviš veću egzotiku.

Potpis

http://sr.libreoffice.org — slobodan kancelarijski paket, obrada teksta, tablice,
prezentacije, legalno bez troškova licenciranja

Super. Sada me zanima jos nesto. Zamislimo sledeci scenario:

1. Nit A je zakljucala neki mutex mutex.
2. Nit A nesto radi.
3. Nit B pokusava da zakljuca mutex, ali je on vec zakljucan, tako da mora da saceka otkljucavanje.
4. Nit A nesto radi.
5. Nit A otkljucava mutex.
6. Nit B uspeva da zakljuca mutex
7. Nit B nesto radi.

Sta se u OS-u desava izmedju koraka 5 i 6, tj. koliko vremena treba niti B da ukapira da WC nije vise zauzet?

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Ako ja dobro razumem, onda to zavisi od toga kako kernel radi scheduling, tj. kako se uopšte menja kontekst sa niti A na nit B. U običnoj kvantifikaciji, čekaćeš dok nit B ne dođe na red i u prvoj instrukciji nastavi dalje i uđe u kritičnu sekciju. Sa naprednijim (dinamičkijim) raspoređivanjem procesa verovatno ćeš u koraku 3 niz B izbaciti iz reda za čekanje dok se ne oslobodi uslov. Onda se u lock-free maniru nit B u koraku 5 ubacuje nazad u listu i čeka na rescheduling.

Potpis

http://sr.libreoffice.org — slobodan kancelarijski paket, obrada teksta, tablice,
prezentacije, legalno bez troškova licenciranja

Da, to se radi preko scheduler-a koji je uvezan sa sync objektima. Spinlock se koristi samo jedno veoma kratko vreme u svakom threadu da bi se usao u sistemski critical section u cilju serijalizacije pristupa unutrasnjoj strukturi koja je u jezgru mutex (i ostalih wait) objekta; na x86 platformi najcesce kroz XCHG instrukciju, koliko znam ne koristi se CAS, samo Swap. Ono sto se posle desava nije vise spinlock vec high-level hibrid koji se zove sleeplock i koji je uvezan sa schedulerom. Efektivno u tacki 3 thread B se prebacuje iz "running" u "waiting" state i "izbacuje" iz thread schedula ili kompletno ili tajmirano tako sto ce ga scheduler ignorisati kad na njega dodje red, tako da se ne drzi thread u mrtvoj petlji (sto bi bila posledica spinlocka).
Izmedju tacke 5 i 6 moze proci varijabilno vremena zato sto tacka 5 otkljucava mutex, zatim ga zakljuca za sledeceg iz reda (i time ga odmrzne) ako neki ceka i izadje iz koraka, ne prabacuje kontrolu u B, ako ni zbog cega drugog onda zato sto bi to prekrsilo preemtive mehanizam. Scheduler onda nastavlja svoj prirodni ciklus i kad dodje do threada B isti vise nije zamrznut i izlazi iz wait funkcije sa obezbedjenim mutex lockom. Tako da je B ukapirao jos u 5. samo nije jos imao priliku da to iskaze Naravno, ja sam ovde prikazao scheduler kao da je neka monolitna rutina u srcu OS-a sto on nije, ali u kontekstu ove price razumljivije ako se tako posmatra.

U principu za ovakve stvari vezano za WIndows OS potrazis clanke od Mark Russinovich-a (ex sysinternals), taj covek zna bolje kako radi windows kernel nego bilo ko drugi. Na ovom linku ima njegov skoriji intervju:
http://channel9.msdn.com/shows...-Russinovich-Inside-Windows-7/

za celu ovu pricu gore ono sto je zanimljivo je od drugog do sedmog minuta gde prica kako Win7 vise nema globalni dispatcher spinlock (fancy ime za XCHG blokadu) tako da ce se multi-core i CPU sistemi ubrazati i Win7 kernel biti skalabilan do 256 jezgara, inace ceo intervju je odlican jer prica i o drugim unapredjenjima za WIn7. Jedva cekam da izadje Inside Windows 5th edition da vidim kako su to izveli.

PS: Mala ispravka, inside windows je druga knjiga, ona koja je interesanta je Microsoft Windows Internals.

Potpis

Sloba je za 12 godina promenio antropološki kod srpskog naroda. On je od jednog
naroda koji je bio veseo, pomalo površan, od jednog naroda koji je bio znatiželjan, koji
je voleo da vidi, da putuje, da upozna,
od naroda koji je bio kosmopolitski napravio narod koji je namršten, mrzovoljan,
sumnjicav, zaplašen, narod koji se stalno nešto žali, kome je stalno neko kriv - Z.Đinđić

Kratkim vremenom zakljucanosti mutex-a se postize da verovatnoca da nit pokusa da zakljuca mutex koji je vec zakljucan bude mala. Recimo da treba da napisem program koji j ispalio odredjen broj niti za paralelizaciju nekog slozenog izracunavanja, ali da metoda nije takva da dopusta da svaka nit radi sa odvojenim podacima, vec da je sinhronizacija neophodna. Po ovoj prici je isplativo koristiti konstrukciju if (mutex.trylock()) { idi u WC; } else { radi nesto drugo da ubijes vreme dok se ne ycepesh; }.

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

To sa trylock je naravno validna konstrukcija, samo sto se retko koristi. Threadove obicno kreiras da bi odradili neki specificni "jednosmerni" zadatak i ako je takav ti obicno nemas sta da radis u else varijanti pa je najjednostavnije da pustis thread da se zamrzne dok ne dobije ono sto mu treba, leba ne jede. Imaj takodje u vidu da ovde vaze ista pravila kao i u redu za mleko , ako stanes da cekas u redu pre ces ga dobiti od onog koji svaki pet minuta dolazi da proveri dal se red ispraznio.

PS: mala ispravka nisam dobro procitao prvu konstataciju... I da, pise se ycepecx

Potpis

Sloba je za 12 godina promenio antropološki kod srpskog naroda. On je od jednog
naroda koji je bio veseo, pomalo površan, od jednog naroda koji je bio znatiželjan, koji
je voleo da vidi, da putuje, da upozna,
od naroda koji je bio kosmopolitski napravio narod koji je namršten, mrzovoljan,
sumnjicav, zaplašen, narod koji se stalno nešto žali, kome je stalno neko kriv - Z.Đinđić

Ukoliko obe niti trce na jednom jezgru, minimalno vreme je jedan "kvant" - kvant je jedinica vremena kojom barata thread scheduler. Windows NT Kernel obicno koristi kvante od 10ms ili 15ms (mada se to moze programski smanjiti na min. 1 ms)

Ukoliko niti trce na dva jezgra - minimalno vreme je u stvari vreme za koje ce OS kernel "otkociti" spinlock u mutex objektu/strukturi/cemugod. To vec zavisi od same implementacije OS-a.

U slucaju Windowsa, to vreme je u stvari vreme od kada tvoj thread "otkljuca" mutex pa do vremena kada drugi thread izadje iz Wait funkcije. Ukoliko je tvoja aplikacija u User modu, to vreme ukljucuje "switch" izmedju User i Kernel moda + deblokazu spinlocka + skok drugog thread-a (koji je u wait-u) iz kernel u user mod.

Inace, da se nadovezem na vrlo dobar savet Mmix-a (Windows Internals trenutno 4th Edition je must-have knjiga) - ukoliko ste na univerzitetu, mozete da probate od Microsofta da zatrazite Windows Research Kernel - to je kompletan Win XP SP2 / Win Server 2003 kernel u izvornom obliku (bez HAL-a) koji je bas namenjen za proucavanje scheduling i memory management mehanizama. Taj kod je daleko pregledniji i jasniji od Linux sorsa.

Takodje, taj kod mozete sasvim lepo kompajlirati u validan kernel image (ntoskrnl.exe) i zameniti ga - sto cini eksperimentisanje sa scheduling algoritmima vrlo lakim.

Potpis

DigiCortex (ex. SpikeFun) - Cortical Neural Network Simulator:
http://www.digicortex.net/node/1 Videos: http://www.digicortex.net/node/17 Gallery: http://www.digicortex.net/node/25
PowerMonkey - Redyce CPU Power Waste and gain performance! - https://github.com/psyq321/PowerMonkey

Jesi 100% siguran u ovo, koliko znam schduler ce uradi priority boost thread-a u waiting state-u da mu da prednost ali to i dalje ne znaci da thread nece biti preemptovan threadom viseg prioriteta, zar ne?

Potpis

Sloba je za 12 godina promenio antropološki kod srpskog naroda. On je od jednog
naroda koji je bio veseo, pomalo površan, od jednog naroda koji je bio znatiželjan, koji
je voleo da vidi, da putuje, da upozna,
od naroda koji je bio kosmopolitski napravio narod koji je namršten, mrzovoljan,
sumnjicav, zaplašen, narod koji se stalno nešto žali, kome je stalno neko kriv - Z.Đinđić

Oops, da - good point. To sam zaboravio.

Onda naravno mozemo dodati i bilo koji interapt/DPC koji je veceg prioriteta - sto celu racunicu cini vrlo nepredvidljivom u slucaju Windowsa.

Pitanje je da li je to i izvodljivo - jer ISR-ovi i ostale kmode rutine u principu mogu da zadrze izvrsavanje procesora na neogranicen rok (KeStallExecutionProcessor()) tako da je nemoguce garantovati maksimum - doduse minimum vremena se moze izracunati.

Zato Windows NT i nije RTOS (niti je planirano da bude) - kod RTOS-eva obicno imas tabele gde su definisani worst-case scenariji u vremenskim jedinicama pa mozes izracunati worst-case scenario koliko je potrebno vremena od odblokiranja mutexa do nastavka izvrsavanja threada koji ceka na taj mutex.

Potpis

DigiCortex (ex. SpikeFun) - Cortical Neural Network Simulator:
http://www.digicortex.net/node/1 Videos: http://www.digicortex.net/node/17 Gallery: http://www.digicortex.net/node/25
PowerMonkey - Redyce CPU Power Waste and gain performance! - https://github.com/psyq321/PowerMonkey

Tako je. U okviru ovog "paketa" - Windows research Kernel (dostupnog svakom MSDNAA pretplatniku) dobija se i niz alata, dokumentacija itd. + nastavni materijal i pdf "Windows Internals"

Yep - i taj kod je vrlo kvalitetan i odlicno dokumentovan. Ko je imao prilike da radi sa tim kernelom, i sa - recimo, Linux kernelom uvidja "malu" razliku u jasnoci koda, strukturi i konzistentnosti u stilu programiranja. Jos jedan kvalitetni kernel je i OpenSolaris - isto jako lepo parce koda koje se moze koristiti kao dobar tutorial.

Mali kuriozitet - dokumentacija koja dolazi sa WRK-om je originalna NT dokumentacija iz 1989-te godine (sa par revizija) - interesantno je da se u NT dizajnu skoro nista bitno nije promenilo i ti dokumenti se i dan danas mogu koristiti za razumevanje rada kernela. Inace, imena autora u tim dokumentima su David Cutler, itd... ta dokumentacija je bukvalno parce istorije, jer su to originalni development design dokumenti za Windows NT :)

Takodje, moguce je i - do odredjene granice, objavljivati i snapshot-ove koda u naucnim radovima, doduse oni ne smeju preci vise od 60 konsekutivnih linija iz originalnog NT sorsa - mada, to je sasvim dovoljno za vecinu demonstracija algoritama, itd...

U svakom slucaju - jako poucna i vredna stvar za ucenje modernog OS kernel dizajna.

Doduse, taj Kernel je sada vec mator - posto je Vista kernel doneo promene u scheduleru i nove sinhronizacione primitive (Conditional Variables - doduse, one su 100% user-mode objekat) a Win 7 kernel ima dosta promena u scheduleru i memory manageru zbog uklanjanja globalnih spinlockova.. ali, valjda ce Microsoft uskoro izdati novi WRK sa, bar, Vista kernelom.

Potpis

DigiCortex (ex. SpikeFun) - Cortical Neural Network Simulator:
http://www.digicortex.net/node/1 Videos: http://www.digicortex.net/node/17 Gallery: http://www.digicortex.net/node/25
PowerMonkey - Redyce CPU Power Waste and gain performance! - https://github.com/psyq321/PowerMonkey

Dostupne su mi knjige Windows via C/C++ 5th edition u izdanju Wintelectt-a i Linux Kernel Development 2nd edition u izdanju Novell press-a.

No, zanima me sledece, da li su operacije citanja i postavljanja vrednosti primitivnih tipova (bool, char, int16, int32, int64, void*, float, double, long double) atomicni? Primera radi, neka promenljiva int x ima vrednost 5 u nekom trenutku i bas tada nit A pokusava da izvrsi naredbu x = 77, a nit B da izvrsi naredbu int y = x. Recimo da dok je jedna pokusavala da obavi svoj deo posla, druga ju je prekinula (ako rade na istom procesoru) i da istovremeno to pokusavaju (ako su na razlicitim procesorima). Mene zanima da li je garantovano da ce promenljiva y imati nakon naredbe int y= x jednu od vrednosti 5, 77 ili moze da se u promenljivoj y nadje neko djubre (vrednost razlicitio i od 5 i od 77).

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Ukoliko ti trebaju jednostavne operacije nad promenljivama: ind/dec, add/sub, set/reset bit, exchange ops, preporucio bih ti da pogledas Interlocked familiju funkcija; na primer InterlockedIncrement, InterlockedDecrement, InterlockdCompareExchange itd. To su sve Win API funkcije, i one su zaista atomicne i rade 32b/64b promenljivama - rade sa operandima volatile LONG. Prednost koriscenja ovih funkcija je sto nema nikakvog zakljucavanja niti - sve je atomicno na asemblerskom nivou. Pomocu ovih funkcija mogu da se formiraju kompleksnije strukture, na primer brzi cirkularni FIFO.

Pozdrav,
Milan.

Sve high-level kontrukcije koje se svode na vise od jedne CPU instrukcije su podlozne prekidanju, cak iako ima smo dve instukcije, tako da je safe-bet da je svaka high-level operacija thread unsafe zato sto ne znas kakav ce biti proizvedeni native code. Da bi ti pojasnio bolje sta je problem spusticu se na asm:

mov eax, [0x00000010]
mov [0x00000014], eax

ovo moze biti prekinuto u sred posla i lokacije 0x10 i 0x14 mogu biti promenjene u drugom thread-u dok tvoj thread ceka svoj quantum. U tvom konkrentom slucaju (y=77 i y=x) realno bi bilo pretpostaviti da se upis svodi na jednu instrukciju tako da ce y najverovatnije i biti ili 5 ili 77 ali samo zato sto je int 32 bita i os ti je >= 32bitni i dovoljna je jedna x86 mov instrukcija za upis i magistrala je dovoljno siroka da atomizuje operaciju upisa u lokaciju, tako da je ovo vise educated guess nego solidna tvrdnja. Da isto C ++ kod kompajliras na 16bit target i 16 bitni OS i imas samo 16bitnu mov instrukciju npr onda bi imao problem atomizacije tvojih operacija i mogao bi da dobijes djubre u y (zato sto bi 32 bita bilo upisivano kao 2x16bita). Ali cak i tada u tvom primeru ne bi bilo problema jer 5 i 77 sasvim lepo fituju u donjih 16 bita , pa nije ni vazno koji thread upise gornjih 16 bita kad su u oba slucaja nule.

U svakom slucaju bazirati funkcionalnost mt aplikacija na pretpostavkama je los potez, postoje razni razradjeni mehanizmi za concurrency (izmedju ostalog i InterlockedXXX api funkcije koje je madwolf dao), a neki jezici kao sto je c#/vb.net cak imaju i jezicke lock konstrukcije za critical section, jednostavno nema potrebe

Potpis

Sloba je za 12 godina promenio antropološki kod srpskog naroda. On je od jednog
naroda koji je bio veseo, pomalo površan, od jednog naroda koji je bio znatiželjan, koji
je voleo da vidi, da putuje, da upozna,
od naroda koji je bio kosmopolitski napravio narod koji je namršten, mrzovoljan,
sumnjicav, zaplašen, narod koji se stalno nešto žali, kome je stalno neko kriv - Z.Đinđić

Znam da se nit moze prekinuti nakon svake masinske instrukcije i da se jedan programski red obicno svodi na vise instrukcija, tako da jedna linija C++ koda itekako moze biti prekinuta. Medjutim, ja sam ocekivao odgovor tipa "Pa, naravno da je citanje/pisanje primitive jedna masinska instrukcija. Niko nije lud da pravi C++ kompajler drugacije.". Ako nista drugo, ocekivao sam takav odgovor barem za primitive sirine <=32 bita, ali ovako ispade da i tu mogu da procitam neko djubre (vrednost razlicitu i od 5 i od 77). Sta ces, kad mutex glavu cuva, subara je kvari.

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Zapravo, ako programiras za Windows (user mode) tu ima jos jedna "komplikacija" kod tvoje izreke - naime Mutex je u Windowsu malo kompleksniji objekat, tj. "tezi" i svako lockovanje/cekanje na Mutex zahteva skok u kernel mod i dodatni overhead koji u odredjenim slucajevima (recimo, ako imas mnogo kratkih rutina koje koriste Mutex a izvrsavaju se veliki broj puta u sekundi) moze izazvati veci pad u performansama.

Razlog za to je fakat da Windows mutex jeste globalni (system-wide) objekat koji moze biti dostupan i drugim procesima. Za takvu implementaciju je neophodno skociti u kernel mod i vezati taj mutex za nesto sto je sistemski vidljivo.

Ukoliko nemas potrebe da koristis isti mutex izmedju razlicitih procesa, vec unutar istog procesa (medju thread-ovima) - u Windowsu je daleko "jeftinije" koristiti Critical Section objekat - u vecini slucajeva ces izbeci nepotrebne skokove u kernel mod, a sa stanovista funkcionalnosti si dobio istu stvar.

Tako da "mutex glavu cuva"... moze malo da se koriguje u slucaju Windows-a ;-)

PS - Vista / Server 2008 (tj. NT Kernel 6.0+) imaju jos neke user-mode sinhronizacione primitive, poput kondicionalnih varijabli. To omogucava vecu fleksibilnost a bolje performanse (zato sto su to user-mode only objekti). Na zalost, Microsoftu ne pada na pamet da implementira te iste API-je u nekom SP-u za Windows XP, pa je koriscenje tih API-ja otezano za sve upotrebe gde se zahteva i backwards kompatibilnost.

Potpis

DigiCortex (ex. SpikeFun) - Cortical Neural Network Simulator:
http://www.digicortex.net/node/1 Videos: http://www.digicortex.net/node/17 Gallery: http://www.digicortex.net/node/25
PowerMonkey - Redyce CPU Power Waste and gain performance! - https://github.com/psyq321/PowerMonkey

Ivane, hvala, ali vec smo raspravljali o tome na ovoj temi:

http://www.elitesecurity.org/p1928764

Dakle, QMutex glavu cuva, subara je kvari.

Ipak, cini mi se da je i ovo mnogo sporije od pthread mutex-a na GNU/Linux-u, gde na pthread_mutex_init(); pthread_mutex_lock(); pthread_mutex_unlock(); pthread_mutex_destroy(); ne moras ni da mislis, bez obzira na opterecenost, sve dok su sudari (pokusavam da zakjljucam mutex koji je vec zakljucan) retki, tj. dok su mutex-i tu samo zbog sigurnosti. Da, na mutex-e sam mislio pre svega za medjunitnu komunikaciju. Za komunikaciju izmedju procesa na istoj masini moze da posluzi deljena memorija, koa ima svoje zakljucavanje/otkljucavanje.

BTW, koju biste mi referencu za ozbiljniji multithreading preporucili?

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Pa zapravo mislim da izbor zavisi od toga koliko cesto moze doci do sudaranja tj koliki je contention. Critical section sam po sebi nije kernel mode ali u slucaju sudara (po isteku spinlock pokusaja) kreira potpuno novi kernel-mode semafor da bi sinhronizovao blokirane threadove jer user mode ne moze tek tako da blokira trenutni thread (cak i sleep() poziv ukljucuje tranziciju). Daklet tada imamo pun overhead kreiranja native objekta kao i za mutex i posle kad semafor nije prazan svaki failed CS spinlock ukljucuje kernel-mode tranziciju i wait na semaforu.
Ako se to desava veoma retko (kad je contention nizak) onda je usteda ostvarena na izbegavanju user-to-kernel tranzicije velika, ali ako se vise threadova puno sudara oko istog critical sectiona i ako je semafor konstantno blokiran onda se gubi sva prednost. Programeri dosta cesto grese ovde i misle da su samim tim sto su mutex zamenili sa CS ostvarili silnu ustedu a u praksi cesto kontinualno imaju po nekoliko zamrznutih threadova koji cekaju na kernel mode semaforu. Fora je sto se spori mutexi obicno i primecuje u takvim situacijama

Potpis

Sloba je za 12 godina promenio antropološki kod srpskog naroda. On je od jednog
naroda koji je bio veseo, pomalo površan, od jednog naroda koji je bio znatiželjan, koji
je voleo da vidi, da putuje, da upozna,
od naroda koji je bio kosmopolitski napravio narod koji je namršten, mrzovoljan,
sumnjicav, zaplašen, narod koji se stalno nešto žali, kome je stalno neko kriv - Z.Đinđić

@mmix,

Tacno, u pravu si - od "contention-a" zavisi kakve ces performanse dobiti. Medjutim, problem je sto malo koji projekat ima vremena da se developeri pozabave dubljom analizom performansi koda, koja bi ukljucila i analizu sinhronizacije izmedju threadova, pa je nekako "pravilo desne ruke" da se umesto mutex-a koristi critical section, pa cak i ako u nekim slucajevima ne donosi dobitke.

@Nedeljko,



Na zalost, nemam sad vremena da pogledam Linux implementaciju pthread_mutex-a, ali me definitivno zanima zasto mislis da je ta implementacija brza od kriticnih sekcija na windows-u?

Potpis

DigiCortex (ex. SpikeFun) - Cortical Neural Network Simulator:
http://www.digicortex.net/node/1 Videos: http://www.digicortex.net/node/17 Gallery: http://www.digicortex.net/node/25
PowerMonkey - Redyce CPU Power Waste and gain performance! - https://github.com/psyq321/PowerMonkey