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.

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?

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.

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.

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; }.

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

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.

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?

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.

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.

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).

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

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.

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.

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?

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

@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?

Pa mozda nije kernel mode implementacija a pride i "sece krivine" , npr:



U principu ako je pthread implementacija cisto intraprocess onda low-contention poredjenje sa windows mutexima nema smisla, onda je bolje porediti sa Win critical sections.




Ali slozices se da je to 'easy way out' isto koliko i mutexi, samo da se ne razmislja o problemu previse . U situaciji kad imas 20 threadova koji u proseku provode 80% vremena cekajuci isti critical section/mutex, onda je to dobar povod da se task reprogramira i da se contention razresi adekvatno (recimo daljom paralelizacijom i defragmentacijom posla), medjutim istina jeste da ce retko ko da se pozabavi time.

Pretpostavio sam tako nesto.

Smatram da u kodu dovolno vodim racuna o tome, tako da mi ta provera nije potrebna.



Ne mislim, nego me platform dependent resenja ne interesuju. QMutex lepo obmota kriticne sekcije na Windows platformi, na UNIX like platformi koristi mutex-e i super.

InterlockedXXX funkcije nisu skroz safe same po sebi, zbog reordering-a instrukcija, sto na nivou hardvera sto na nivou kompajlera.
Topli savet je da se koriste memory barrier-e u kombinaciji sa InterlockedXXX funkcijama da bi se dobilo ocekivano ponasanje na svim platformama.
Ovo je na nekim platformama prilicno ozbiljan problem ako se ignorise i tice se i thread safety-a i performansi koda (ako je neophodno, na primer,
upisivati u memoriju sekvencijalno).

Hmm, prvi put cujem za ovo, koliko je meni poznato Interlocked API upravo za to i sluzi.

Kako god da obrnes, interlocked operacija se na kraju svede na atomizaciju operacije unutar critical sekcije, koja na kraju zavrsi sa spinlockom kroz derivat XCHG instrukcije koja obezbedjuje memory barrier (takva je namerno po dizajnu i sprecava reordering), tako da ni kompajlerski ni hardverski reordering ne mogu da uticu na atomicnost interlocked api funkcije, kao sto ne mogu ni na critical sekcije i kernel wait objekte. Windows bar ne koristi cisto softverske locking paterne a sumnjam da i linux pati od toga.

Potpuno si u pravu, i velika većina korisnika može da ignoriše moj komentar, ali radio sam na platformi gde je jedini oblik non-kernel sinhronizacije bio "ručno" upisivanje L2 keša.

Tek sad mi nije jasno, mozda gresim ali memory barrier posledica xchg instrukcije je dokumentovani requirement za implementaciju okolnog hardvera, tj posledica toga da bus mora biti zakljucan kad je LOCK aktiviran. A tehnicka dokumentacija za intelove cipove to direktno navodi na vise mesta, npr:



Znaci ne da blokira out-of-order execution i "sece" kroz L1/L2 kes i load/store reordering nego sece i kroz magistralu zbog multi-CPU platformi. Vi ili nesto niste dobro uradili ili hardver na kome ste radili ne podrzava LOCK signal na magistrali (sto mi je jos bizarnije).