Läs-kopiera-uppdatering

Läs-Kopiera-Uppdatera, RCU (Read-Modify-Write[ clarify ] , read-copy-update, read-copy-update [1] , Read-Copy-Update [2] ) är en synkroniseringsmekanism i flertrådade system. Implementerar icke-blockerande synkronisering för alla läsare av datastrukturen. Skriver kan vara parallella med läsningar, men bara en skribent kan vara aktiv åt gången.

Beskrivning

Grundidén är att istället för att ändra befintliga data, skapar författaren en kopia av den, ändrar den och uppdaterar sedan pekaren till datastrukturen. Samtidigt behåller alla läsare som hade tillgång till strukturen före uppdateringen åtkomst till sin föråldrade kopia av data, som kommer att förbli oförändrad. Ändå kommer nya läsare att ha tillgång till den redan uppdaterade strukturen. Läs i det här fallet är en kritisk sektion som tillåter samtidig läsning av flera trådar, men tillåter inte att tråden avbryts i processen.

Ändra ett objekt i en lista

Tänk till exempel på hur man ändrar ett element i en enkellänkad lista med denna synkroniseringsmekanism.

Den globala pekarens roll kommer i detta fall att utföras av pekaren till det första elementet. När du skriver måste du skapa en kopia av hela listan, uppdatera elementet av intresse för den och sedan atomiskt uppdatera den globala pekaren så att den pekar på det första elementet i den nya listan. Alla läsoperationer som fick åtkomst till listan innan den uppdaterades kommer att få den gamla kopian, som förblir oförändrad; efter uppdateringen kommer den nya kopian att läsas.

Denna metod kan inte kallas effektiv på grund av behovet av att kopiera hela listan. Men om det kan garanteras att endast ett element i listan kan läsas och låset uppdateras när du flyttar till nästa , då när du skriver, kan du lämna behovet av att kopiera och ändra endast ett element, varefter atomiskt uppdatera pekaren till det föregående elementet i listan (eller pekaren till det första elementet).

Att lägga till ett objekt i en lista är mycket likt att ändra, men eftersom det inte finns några data att komma åt när det nya objektet skapas, behöver du inte vara försiktig med när du ska radera den gamla kopian av datan.

Frigör minne

Efter att ett nytt element har skapats och pekaren har uppdaterats finns den gamla kopian av elementet fortfarande kvar i minnet och kan inte tas bort förrän alla läsartrådar som har tillgång till det har låst upp det. För att göra detta kan du använda blockerande synkroniseringsmekanismer. Ett alternativ är att ta hänsyn till att läsningen är ett kritiskt avsnitt. Sedan schemalägger skrivtråden sig själv i tur och ordning efter var och en av lästrådarna med ett systemanrop. I det här fallet kommer alla lästrådar garanterat att gå igenom en kontextväxling och därför sluta använda en referens till en föråldrad version av datastrukturen.

Läsning i det kritiska området

När du använder läs-modifiera-skriv-algoritmen kan inga antaganden göras om vad som kommer att hända med datastrukturen för varje tråd som läser data. Detta innebär att lagring av en strukturpekare och användning av den utanför en kritisk sektion, och även när du anger en ny läskritisk sektion, kan resultera i ett fel. All åtkomst till datastrukturen bör endast utföras i den kritiska delen, och lästråden kan vid behov kopiera data till sig själv under denna period, varefter den kan arbeta med sin lokala kopia, släppa låset och utan att riskera att försöka komma åt en redan avlägsen tråd, som tidigare öppnats för skrivning.

Läs-modifiera-skriv i Linux

RCU-stöd har funnits i operativsystemet Linux sedan kärnversion 2.5 [3] . Huvudfunktioner för RCU API:

1. rcu_read_lock()  - meddelar att en ström har kommit in i den kritiska delen för läsning;
2. rcu_read_unlock()  - tillkännager utgången av lästråden från den kritiska sektionen;
3. synchronize_rcu()  - Genom att anropa den här funktionen väntar en tråd som öppnas för skrivning tills alla läsoperationer som hade tillgång till den gamla versionen av datastrukturen har avslutats. Efter det är en skrivbar ström gratis att radera den föråldrade kopian.

Dessutom, för att skydda mot kompilatoroptimeringar som ändrar exekveringssekvensen av instruktioner, definieras makron för att säkert erhålla och uppdatera en pekare till datastrukturen rcu_dereference() respektive rcu_assign_pointer() .

Åtgärder före och efter inspelning

Först måste du läsa datastrukturen, sedan ändra dess kopia och sedan skriva pekaren till den uppdaterade datastrukturen atomically .

Alternativ

På vissa plattformar (t.ex. RISC ) är denna instruktion inte tillgänglig. Likvärdiga resultat kan uppnås med hjälp av instruktionerna:

1. lastning med ett märke (LL - last länkad);
2. skrivförsök (SC - lagra villkorlig).

Se även

• blockering
• Synkronisering

Anteckningar

1. ↑ https://books.google.ru/books?id=zA7ECwAAQBAJ&pg=PA177&lpg=PA177&dq= "Read-Copy-Update"+read+copy
2. ↑ LDD
3. ↑ Arkiverad kopia . Hämtad 24 februari 2017. Arkiverad från originalet 11 januari 2017. (obestämd)

Litteratur

• Paul E. McKenney, John D. Slingwine. Read-Copy_update: använder exekveringshistorik för att lösa samtidighetsproblem . (obestämd)
• Vad är RCU? . (obestämd)
• Paul E. McKenney, Jonathan Walpole. Vad är RCU i grunden? . (obestämd)

Länkar