Protokol MESIManuál pro začátečníky
Štěpán Rezek, 2007 rev 1.1
Co to je?• Protokol MESI (někdy nazýván Illinois
protocol) je protokol široce používaný pro zajištění paměťové koherence. Poprvé se objevil u procesorů Intel Pentium.
Stavy MESITzn. v jakém stavu mohou být kopie
proměnných v lokálním bloku
M – modified
E – exclusive
S – shared
I – invalid
Stav M• Blok cache je přítomen pouze v lokální
cache• Kopie byla změněna, tzn. hodnota je jiná než
hodnota v hlavní paměti• Cache musí tento blok zapsat do hlavní
paměti dříve, než kterákoliv jiná cache přečte (v tuto chvíli již neplatnou) hodnotu z hlavní paměti
Stav E• Blok je přítomen pouze v lokální cache, ale
je clean (čistý) – jeho hodnota je stejná, jako hodnota v hlavní paměti
Stav S• Blok je platný a může být sdílen jinou cache
Stav I• Blok v cache je neplatný
• Cache může vrátit hodnotu, když je blok ve stavu M, E nebo S.
• Pokud je ve stavu I, musí nejdříve získat platnou hodnotu proměnné, aby uspokojila čtení. Poté se může přepnout do stavu S nebo E.
Takže to shrňme:Stav hodnoty v
cache:M Modified E Exclusive S Shared I Invalid
Je hodnota v cache platná?
ANO ANO ANO NE
Hodnota v hlavní paměti je…
…zastaralá …platná …platná —
Existují nějaké kopie v cache ostatních
procesorů?NE NE Možná možná
Zapsání (write) do takového bloku …
…nejde na sběrnici
…nejde na sběrnici
…jde na sběrnici a aktualizuje cache
…jde přímo na sběrnici, změna hodnoty jen v cache
Transakce (události) na sběrnici• BusRd: Po lokálním Read miss, použit S/S – signalizuje,
jestli existují sdílené kopie• BusRdX: po lokálním Write miss, žádost o nový blok +
zneplatnění• BusUpgr: po lokálním Write hit nad blokem se stavem S
(zneplatnění)Odpověď na čtení (BusRd nebo BusRdX):• MemSup: hlavní paměť dodává požadovaný blok do cache• CacheFlush: zdrojem dat je cache, kde je blok ve stavu.
Data jsou vypláchnuta na sběrnici a uložena do hl. paměti i předána žádající cache.
S/S signál• Pokud by neexistoval, máme protokol MSI ->
neodlišitelnost stavu E od S• => Kontrolery všech cache provádí snooping
(číhají) na BusRd• Implementováno jako kus drátu, realizující
log. funkci OR -> není to sběrnice
Jak spolu souvisí stavy bloků a operace na sběrnici?
procesor zapisuje +na sběrnici půjde operace
BusRdX
procesor čte +na sběrnici půjde operace BusRd,
na S/ S je hodnota 0 (S)
PrWr/BusRdX
PrWr/—
BusRd/Flush
PrRd/
BusRdX/Flush
PrWr/-
PrRd/—
PrRd/—
E
M
I
S
PrRd
BusRd(S)
BusRdX/MemSup
BusRdX/Flush
BusRd/MemSup
PrWr/BusUpgr
PrRd/BusRd (S)
BusRd/MemSup BusRdX/MemSup
BusUpgr/-
Přechod vyvolaný právě aktivním procesorem
Přechod vyvolaný Okolním světem
Hlavní paměť
P0 P1 Pn
Stav, v němž jeblok cache
Blok (kopie hodnoty z hlavní paměti)
Procesor n
S/S - sdílený signál,log. OR
Nutný kvůli stavu EDatová sběrniceCache (skrytá paměť)
Systém používající MESI:
5
P0 P1 P2
I I I
Na začátku jsou všechny bloky ve stavu Invalid
? ? ?
Procesor 0 chce číst hodnotu
BusRd
Read Miss, ostatní procesory neoznamují po S/S, že mají kopii (stav sběrnice = S, tedy log. 0)
-> Čtení z hlavní paměti (MemSup), stav Exclusive
E 5
5
P0 P1 P2
I I? ?
Procesor 2 chce číst hodnotu
E 5
BusRd
Operaci BusRd zachytí kontroler cache 0……a nastaví S=1 na S/S
Čímž se u obou nastaví stav Shared, a P2 načte hodnotuz hlavní paměti (MemSup)
5S S
5
P0 P1 P2
S I S5 ? 5
Procesor 2 chce zapsat hodnotu 9…
PrWr(9)
… bingo! Už mám platnou hodnotu v cache. Kontrolernejprve musí zneplatnit kopie v ostatních cache…
M 9
BusUpgr(x)
I
…a potom teprve uvede blok do stavu M
5
P0 P1 P2
I I M? 95
Procesor 0 chce číst hodnotu. Problém – blok je Invalid.
-> Na sběrnici se vyšle operace BusRd
BusRd
Ten je zachycen kontrolerem cache 2 -> vyšle S=1 na S/S… a zároveň CacheFlush, s hodnotou 9
CacheFlush(9)
SS
9
9
9
P0 P1 P2
S I S? 99
PrWr(11)
Procesor 1 chce zapsat hodnotu, která není v cache
Tato hodnota je vrácena zpátky – stav Exclusive
M 9
BusRdXBusRdX
Kontroler cache vyšle operaci BusRdX, kterou zneplatní ostatní kopie bloku a vezme hodnotu z hlavní paměti
I I11E
a následně změněna procesorem na zapsanou –stav Modified
Poznámka• Existuje ještě vylepšení protokolu MESI, nazvané
MOESI– Ten je využíván např. u procesorů AMD64
• Owned -> blok v tomto stavu drží nejčerstvější správnou kopii hodnoty z hlavní paměti. Narozdíl od stavu Shared, hodnota v hlavní paměti může být neplatná.
• Pouze jeden procesor může mít blok ve stavu O, všechny ostatní musí mít bloky ve stavu S.
Nastal čas na přestávku a přípravu čaje…
Transakce na sběrnici, ještě jednou• BusRd: Po lokálním Read miss, použit S/S – signalizuje,
jestli existují sdílené kopie• BusRdX: po lokálním Write miss, žádost o nový blok +
zneplatnění• BusUpgr: po lokálním Write hit nad blokem se stavem S
(zneplatnění)Reakce na čtení (BusRd nebo BusRdX):• MemSup: hlavní paměť dodává požadovaný blok do cache• CacheFlush: zdrojem dat je cache, kde je blok ve stavu.
Data jsou vypláchnuta na sběrnici a uložena do hl. paměti i předána žádající cache.
Kritické sekce & MESI• Implementuje se pomocí sdílené proměnné
Lock - zámek• Postup:
1. Zamkni zámek
2. Něco vykonej
3. Odemkni zámek
Toto musí být atomické
Několik atomických metod• Test & Set• Swap• Fetch & Increment• Compare & Swap
Test & Set
Pseudo C++:int TestAndSet(boolean &zamek) {
boolean predchoziStav = zamek;
zamek = true;
return predchoziStav;
}
Pseudo ASM:Load r, zamek
Store zamek, #1
Ret
int zamek = false;
void KritickaSekce() {
while(TestAndSet(zamek) == true);
// kod kriticke sekce
zamek = false;
}
Z: TestAndSet r, zamek
Bnz r,Z
; kod kriticke sekce
Ret
DefiniceDefinice
PoužitíPoužití
Opuštění kritické sekce = nastavení zámku na false (0)Opuštění kritické sekce = nastavení zámku na false (0)
Musí celá proběhnout atomicky, tzn. v průběhu Read,Modify,Write nesmí ostatní procesy/ory přistoupit do místa v paměti, které je modifikováno
0
P0 P1 P2
I I ??
P3
I ?zámek= zámek= zámek= zámek=
zámek=
Test & Set + MESI:Load r, zámek
Store zámek, #1
Bnz r, Z
Procesor 2 chce vstoupit do kritické sekce
Load r, zámek
Store zámek, #1
Bnz r, Z
BusRd
0
Load r, zámek
Store zámek, #1
Bnz r, Z
E
Žádná jiná cache nesdílí zámek -> na sběrnici zůstává S=0
I ?
01
Procesor nyní zamyká zámek...
M 1
… a nyní P2 může nerušeně vykonávat kód v kritické sekci.
Load r, zámek
Store zámek, #1
Bnz r, Z ;projde
C2 neposílá BusUpgr, protože je v M…
0
P0 P1 P2
I I M? 1?
P3
I ?zámek= zámek= zámek= zámek=
zámek=
Store zámek, #0
Nakonec P2 kritickou sekci opustí….
0
0
a cache pošle BusUpgr.
BusUpgr
0
P0 P1 P2
I I M? 0?
P3
I ?zámek= zámek= zámek= zámek=
zámek=
Load r, zámek
Store zámek, #1
Bnz r, Z
Procesor P0 chce vstoupit do kritické sekce
BusRd
a Cache0 pošle BusRd.To zachytí Cache2 a nastaví S=1, načež pošle CacheFlush(0) .
SS
CacheFlush(0)
1
Nyní chce P0 uzamknout zámek
01
=> Změna stavu Cache0 na M a poslání BusUpgr
BusUpgr
0M I
0
P0 P1 P2
M I I? 01
P3
I ?zámek= zámek= zámek= zámek=
zámek=
Load r, zámek
Store zámek, #1
Bnz r, Z
Teď chce P1 uzamknout zámek.
BusRd
Cache0 zjistí, že někdo chce číst zámek, a tak pošle na S/S jedničku a zároveň CacheFlush(1) na sběrnici.
CacheFlush(1)
S S 1
1
1
Procesor 1 tedy načte hodnotu r=1.
1
P1 poté uloží do cache jedničku a pošle BusUpgr.
BusUpgr
MI
Test ovšem neprojde, jelikož r=1 => zpátky na Začátek
1
P0 P1 P2
I M I1 01
P3
I ?zámek= zámek= zámek= zámek=
zámek=
Load r, zámek
Store zámek, #1
Bnz r, Z
Procesor 3 chce taky vstoupit do kritické sekce.Na sběrnici se objeví BusRead od Cache3, následně Cache1 Nastaví S/S na 1 a pošle CacheFlush. Výsledná hodnota r=1.
S S 1
Nakonec P3 nastaví svůj blok na jedničku a dopadne stejně,jako P1 v minulém slidu -> znovu na začátek. P0 je zabarikádovánv kritické sekci
I M
Co dál?• Protokol MESI se také dá použít, mimo jiné, i
s jinými technikami přístupu do kritických sekcí, např. LLSC (Load Linked & Store Conditional), nicméně princip je v základu stejný.
To je vše, mnoho štěstí při zkoušce!
I když, no, pro jistotu, ještě chvilku zůstaňte….
PříkladV systému je 5 procesorů v SMP na sběrnici s
protokolem MESI. Určete, které transakce a kolikrát se objeví na sběrnici, když:
1. každý procesor se snaží 1x dostat do CS
2. každý zbývající procesor se jednou zkusí dostat do CS, která je zamčená.
3. na začátku mají všechny bloky stav I
Ugh…
0
P0 P1 P2
I I ??
P3
I ?zámek= zámek= zámek= zámek=
zámek=
I ?
P4
zámek=
I ?
Simulace, jak by to mohlo vypadat:
0
P0 P1 P2
I I ??
P3
I ?zámek= zámek= zámek= zámek=
zámek=
I ?
P4
zámek=
I ?
BusRd BusRdX BusUpgr
P0
P1
P2
P3
P4
ReadWrite
ReadWrite
ReadWrite
ReadWrite
ReadWrite
P0 se zamkne v CS, ostatní se budou neúspěšně pokoušet o totéž
01M
1
S S 1MI S S 1MI
Zbytek už je asi zřejmý…
E
Tak to už je skutečně vše
Odkazy• https://www.cs.tcd.ie/Jeremy.Jones/vivio/cach
es/MESI.htm– Vynikající simulátor protokolu MESI (WIN only)
• http://cs.felk.cvut.cz/~brabect1/X36APS/pdf/aps_cv12.pdf– WTWNA - Manuál pro začátečníky
• http://service.felk.cvut.cz/courses/X36APS/– Manuál pro pokročilé
Formality• Dílo uvolňuji pod licencí Creative Commons
Attribution 2.5 License • Zříkám se jakékoli odpovědnosti za škody
způsobené tímto textem (třeba 4 u zkoušky… )
• A za správnost tohoto textu (chyby ale samozřejmě rád opravím)
• Drobné nepřesnosti upravil Ing. Miloš Bečvář