Read-copy-update
Read-copy-update (RCU) je v informatice jedno ze synchronizačních primitiv používaných pro vzájemné vyloučení[pozn. 1] a může být někdy využito jako alternativa k zámkům čtenářů–zapisovatelů. RCU zajišťuje velmi nízkou režii a neblokující čtení, avšak může být náročné na prostor, protože musí pro již existující čtenáře zachovat původní kopii dat (pouze do chvíle, než poslední čtení původních dat skončí).
Princip použití
[editovat | editovat zdroj]Název je odvozen ze způsobu, jakým se RCU používá pro aktualizaci spojové struktury na místě. Vlákno, které potřebuje strukturu modifikovat musí provést následující kroky:
- vytvořit novou strukturu,
- zkopírovat data ze staré struktury do nové, a uložit si ukazatel na starou strukturu,
- upravit novou (zkopírovanou) strukturu,
- aktualizovat globální ukazatel, aby ukazoval na novou strukturu,
- uspat se, dokud jádro operačního systému nezjistí, že žádný proces nečte starou strukturu, např. pomocí
synchronize_rcu()v linuxovém jádře, - po probuzení jádrem uvolnit starou strukturu.
Aby vlákno mohlo modifikovat strukturu, musí vytvořit její kopii, proto se metoda nazývá „read-copy update“. Zkratka „RCU“ byla jedním z mnoha příspěvků linuxové komunity. Jinými názvy pro podobné techniky je „pasivní serializace“ a „MP defer“ od programátorů VM/XA a „generace“ od programátorů K42 a Tornado.
Odkazy
[editovat | editovat zdroj]Poznámky
[editovat | editovat zdroj]- ↑ RCU neimplementuje vzájemné vyloučení v běžném významu: díky RCU probíhá čtení paralelně se zápisem (změnou/aktualizací sdílených dat). RCU používá mechanismus prostoru místo tradičního mechanismu času, který je používán tradičními prostředky vzájemného vyloučení (tj. např. zámky). Mechanismus prostoru funguje na principu přístupu ke starší verzi dat, zatímco probíhá jejich aktualizace (v jiném místě).
Reference
[editovat | editovat zdroj]V tomto článku byl použit překlad textu z článku Read-copy-update na anglické Wikipedii.
- Method and apparatus for retrieving network quality of service policy information from a directory in a quality of service policy management system. US. Patentový spis 7099932.
- BAUER, R.T. Operational Verification of a Relativistic Program; PSU Tech Report TR-09-04 [online]. Červen 2009. Dostupné v archivu pořízeném z originálu dne 2015-06-18.
Související články
[editovat | editovat zdroj]Externí odkazy
[editovat | editovat zdroj]- Paul E. McKenney, Mathieu Desnoyers, and Lai Jiangshan: User-space RCU. Linux Weekly News
- Paul E. McKenney and Jonathan Walpole: What is RCU, Fundamentally?, What is RCU? Part 2: Usage, a RCU part 3: the RCU API. Linux Weekly News.
- Paul E. McKenney's RCU web page
- Hart, McKenney, a Demke Brown (2006). Making Lockless Synchronization Fast: Performance Implications of Memory Reclamation An IPDPS 2006 Best Paper porovnávání výkonnosti RCU s jinými bezzámkovými synchronizačními mechanismy. Journal version (včetně Walpole jako autor).
- Apparatus and method for achieving reduced overhead mutual exclusion and maintaining coherency in a multiprocessor system utilizing execution history and thread monitoring. US. Patentový spis 5442758.
- Paul McKenney: Sleepable RCU. Linux Weekly News
