[NSWI004] [Teachers at NSWI004] Nerozumím memory modelu

[Petr Tuma]

Dobry den,

> myslím, že chápu, co je problém, který se snažíme řešit. Kompilátor
> přeskládává každý thread sám o sobě bez kontextu ostatních, což může
> rozbít synchronizaci. Zakázat to nechci, protože optimalizace chci,
> ale potřebuji to nějak omezit.

Ano, presne tak. Plus, nejen kompilator, ale potencialne i procesor.

> Chápu to tak, že memory model garantuje, že když se zbavím data race,
> tak mi zaručí, že se to bude chovat "intuitivně" = sequentially
> consistent.

Tak. Presneji receno, tento konkretni memory model to zarucuje (Java), jine to mohou delat bud velmi podobne (C/C++) nebo uplne jinak (viz linky v diskuznich materialech).

> Netuším ale moc, jak těm data race zabránit. Je tam potom nějaká
> spousta hran, které dávají omezení na to, jak to může kompilátor
> přeskládat. Co mi přijde třeba poměrně nelogické, je jak může zámek
> jednoho atomického příkazu něco ovlivnit. Z hodiny jsem byl zmatený,
> že nevím, jestli ty hrany patří obecně do programu nebo do
> konkrétního přeuspořádání.

Pro prvni priblizeni je dobre se nejprve pohybovat na urovni akci vykonanych v nejakem urcitem behu programu. Kazdy thread bezi az na synchronizaci samostatne a akce, ktere vykonal, jsou nutne usporadane podle Program Order (jinak by to znamenalo, ze prekladac ci interpret proste nefunguje tak, jak definuje syntaxe jazyka). Nektere z akci jsou soucasne synchronizacni, a to, v jakem poradi se souviseji synchronizacni akce vykonaly v tomto urcitem behu programu, vytvari nejake urcite Synchronization Order. Tedy konkretni Synchronization Order je definovano jen pro urcity beh programu, ruzne behy mohou mit ruzne Synchronization Orders.

Usporadani akci je ze sve povahy tranzitivni. Pokud vlakno A treba nejprve zamkne L, pak zapise do X, pak odemkne L, a vlakno B pote zamkne L, precte z X, odemkne L, pak vsechny tyto udalosti jsou usporadane (prvni tri proto, ze je delalo jedno vlakno, druhe tri take proto, ze je delalo jedno vlakno, a mezi sebou proto, ze Synchronization Order usporadalo posledni akci A pred prvni akci B). Tolik tedy k tomu, jak muze zamek ovlivnovat ostatni akce v jednom urcitem behu.

A ted jak na vice behu (spravnost v jednom behu se sice hodi, ale nestaci). Vsechny behy musi byt evidentne rozumne v tom smyslu, ze prekladac ci interpret nesmi udelat neco, co by odporovalo semantice jazyka. Kdyz se vratim k tomu prikladu, kde vlakno A udela L(L)-W(X)-U(L) a vlakno B udela L(L)-R(X)-U(L), pak jsou evidentne mozne pouze dva rozumne behy - bud vlakno A stihne zamknout L driv a poradi bude jako vyse, nebo vlakno B stihne zamknout L driv a pak bude R(X) vlakna B usporadane pred W(X) vlakna A. Tak jako tak ale budou R(X) a W(X) nejak usporadane, a to je prave to, cemu se rika, ze program je Correctly Synchronized - at uz probehne jak chce, vsechny konfliktni operace v nem budou nejak usporadane, i kdyz je jedno jak presne. A memory model pak zarucuje, ze prostredi neudela nic, co by rozbilo iluzi sekvencni konzistence u Correctly Synchronized programu (coz pragmaticky v tomto prikladu muze znamenat proste jen to, ze se pres operace zamknuti a odemknuti zamku neprenasi zadne operace).

Ted trochu slozitejsi priklad. Predstavte si, ze vlakno A pocita nejaka data D, az je ma pripravena, chce nastavit booleovsky flag F pro vlakno B, ktere pak ta data D chce pouzit. Bez synchronizace by to vypadalo takto:

A:
1: D = compute ()
2: F = true

B:
1: while (!F) {}
2: use (D)

Takovyhle program neni korektne synchronizovany, protoze pristupy k promennym D ani F nejsou mezi obema vlakny synchronizovany. Program Order rika, ze A1 bude pred A2 a ze B1 bude pred B2, ale nerika nic o vzajemnem vztahu A* a B*, takze A1 a B2 nejsou usporadane, ani A2 a B1 ne, to jsou data races.

Prekladac muze takovy program rozbit napriklad tim, ze prohodi radky A1 a A2 (protoze pohledem na A* tyto dva radky nikterak nesouvisi a tak je mozne je udelat v jinem poradi nez je napsano).

Ted pojdme pridat synchronizaci, ale pro zajimavost jen kolem pristupu k F:

A:
1: D = compute ()
2: lock (L)
3: F = true
4: unlock (L)

B:
1: do {
2:   lock (L)
3:   X = F
4:   unlock (L)
5: } while (!F)
6: use (D)

Moznosti behu jsou ted omezene synchronizaci. Pokud jde o pristup k F, ten je vzdy ohranicen zamkem, takze tim data race nemuze vzniknout. Co pristup k D ? Thread B muze zpocatku iterovat pres B1-B5, ale na B6 se nedostane dokud A neudela A3, jenze A3 se vzdy deje v sekvenci A1-A4 (Program Order). Tim padem v kazdem rozumnem behu programu B6 je po B1-B5 (Program Order), kde v posledni iteraci B2 muselo nastat po A4 (Synchronization Order) a tim padem vzdy bude usporadano A1 pred B6, tedy ani na D neni data race. A tedy tento program je take korektne synchronizovan a prostredi zaruci, ze se bude chovat rozumne (opet, pragmaticky napriklad staci, aby prostredi nepresouvalo A1 pres hranice odemceni zamku (A4) a B6 pres hranice zamceni zamku (B2)).

Priklad je zajimavejsi tim, ze pristup k D neni uvnitr synchronizace. Muzete si pod nim predstavit mnohem vetsi operaci, treba vystaveni nejake struktury na heapu - tam totiz urcite take nechceme michat synchronizaci do kazde operace, to by prilis brzdilo.

Dava uz toto smysl ?

Petr Tuma