Čtení-kopie-aktualizace

Čtení-kopírování-aktualizace, RCU (čtení-upravování-zápis[ objasnit ] , čtení-kopie-aktualizace, čtení-kopírování-aktualizace [1] , čtení-kopírování-aktualizace [2] ) je synchronizační mechanismus ve vícevláknových systémech. Implementuje neblokující synchronizaci pro všechny čtečky datové struktury. Zápisy mohou být paralelní se čtením, ale současně může být aktivní pouze jeden zapisovač.

Popis

Základní myšlenkou je, že místo změny existujících dat zapisovač vytvoří jejich kopii, změní je a poté atomicky aktualizuje ukazatel na datovou strukturu. Všichni čtenáři, kteří přistupovali ke struktuře před aktualizací, si zároveň zachovávají přístup ke své zastaralé kopii dat, která zůstane nezměněna. Noví čtenáři však budou mít přístup k již aktualizované struktuře. Čtení je v tomto případě kritická sekce, která umožňuje současné čtení více vlákny, ale neumožňuje přerušení vlákna v procesu.

Změna položky v seznamu

Zvažte například, jak změnit prvek v jednotlivě propojeném seznamu pomocí tohoto synchronizačního mechanismu.

Roli globálního ukazatele bude v tomto případě plnit ukazatel na první prvek. Při psaní budete muset vytvořit kopii celého seznamu, aktualizovat prvek, který vás zajímá, a poté atomicky aktualizovat globální ukazatel tak, aby ukazoval na první prvek nového seznamu. Všechny operace čtení, které přistupovaly k seznamu před jeho aktualizací, obdrží starou kopii, která zůstane nezměněna; po aktualizaci bude načtena nová kopie.

Tuto metodu nelze nazvat účinnou kvůli nutnosti zkopírovat celý seznam. Pokud však lze zaručit, že lze číst pouze jeden prvek seznamu a zámek se aktualizuje při přechodu na další , pak při zápisu můžete ponechat nutnost kopírovat a měnit pouze jeden prvek, poté atomicky aktualizujte ukazatel na předchozí prvek seznamu (nebo ukazatel na první prvek).

Přidání položky do seznamu je velmi podobné změně, ale protože při vytvoření nové položky nejsou k dispozici žádná data, není třeba dbát na to, kdy odstranit starou kopii dat.

Uvolnění paměti

Po vytvoření nového prvku a aktualizaci ukazatele zůstane stará kopie prvku stále v paměti a nelze ji odstranit, dokud ji neodemknou všechna vlákna čtečky, která k ní mají přístup. K tomu můžete použít blokovací synchronizační mechanismy. Alternativou je vzít v úvahu skutečnost, že čtení je kritickou částí. Potom se vlákno zápisu naplánuje po každém čtení vláken pomocí systémového volání. V tomto případě je zaručeno, že všechna vlákna čtení projdou přepínačem kontextu, a proto skončí pomocí odkazu na zastaralou verzi datové struktury.

Čtení v kritické oblasti

Při použití algoritmu čtení-upravování-zápisu nelze učinit žádné předpoklady o tom, co se stane s datovou strukturou pro každé vlákno, které čte data. To znamená, že uložení ukazatele struktury a jeho použití mimo kritickou sekci, a dokonce i při zadávání nové kritické sekce pro čtení, může vést k chybě. Veškerý přístup k datové struktuře by měl být prováděn pouze v kritické sekci a čtecí vlákno si v případě potřeby může během této doby zkopírovat data do sebe, poté může pracovat se svou lokální kopií, uvolnit zámek a bez rizika pokusu o přístup k již vzdálenému vláknu, dříve otevřenému pro zápis.

Čtení-upravování-zápis v Linuxu

Podpora RCU je v operačním systému Linux přítomna od verze jádra 2.5 [3] . Hlavní funkce RCU API:

1. rcu_read_lock()  - oznámí, že proud vstoupil do kritické sekce pro čtení;
2. rcu_read_unlock()  - oznámí ukončení čtecího vlákna z kritické sekce;
3. synchronize_rcu()  - Voláním této funkce vlákno otevřené pro zápis čeká na ukončení všech operací čtení, které měly přístup ke staré verzi datové struktury. Poté může zapisovatelný stream odstranit zastaralou kopii.

Pro ochranu před optimalizacemi kompilátoru, které mění sekvenci provádění instrukcí, jsou také definována makra pro bezpečné získání a aktualizaci ukazatele na datovou strukturu rcu_dereference() a rcu_assign_pointer() .

Akce před a po nahrávání

Nejprve musíte přečíst datovou strukturu, poté upravit její kopii a poté zapsat ukazatel na aktualizovanou datovou strukturu atomicky .

Alternativy

Na některých platformách (např . RISC ) tato instrukce není dostupná. Ekvivalentních výsledků lze dosáhnout pomocí pokynů:

1. zatížení se značkou (LL - load linked);
2. pokus o zápis (SC - podmíněné uložením).

Viz také

• blokování
• Synchronizace

Poznámky

1. ↑ https://books.google.ru/books?id=zA7ECwAAQBAJ&pg=PA177&lpg=PA177&dq= "Read-Copy-Update"+read+copy
2. ↑ LDD
3. ↑ Archivovaná kopie . Získáno 24. února 2017. Archivováno z originálu 11. ledna 2017. (neurčitý)

Literatura

• Paul E. McKenney, John D. Slingwine. Read-Copy_update: použití historie provádění k řešení problémů se souběžností . (neurčitý)
• Co je RCU? . (neurčitý)
• Paul E. McKenney, Jonathan Walpole. Co je to RCU Fundamentally? . (neurčitý)

Odkazy