Lue-kopioi-päivitys

Lue-kopioi-päivitä, RCU (lue-muokkaa-kirjoita[ selventää ] , lue-kopioi-päivitys, lue-kopioi-päivitys [1] , Read-Copy-Update [2] ) on synkronointimekanismi monisäikeisissä järjestelmissä . Toteuttaa estävän synkronoinnin kaikille tietorakenteen lukijoille. Kirjoitukset voivat olla rinnakkaisia ​​lukujen kanssa, mutta vain yksi kirjoittaja voi olla aktiivinen kerrallaan.

Kuvaus

Perusajatuksena on, että sen sijaan, että muuttaisi olemassa olevaa dataa, kirjoittaja luo siitä kopion, muuttaa sitä ja päivittää sitten atomisesti osoittimen tietorakenteeseen. Samanaikaisesti kaikki lukijat, jotka käyttivät rakennetta ennen päivitystä, säilyttävät pääsyn vanhentuneeseen tietokopioonsa, joka säilyy ennallaan. Uudet lukijat pääsevät kuitenkin käyttämään jo päivitettyä rakennetta. Luku on tässä tapauksessa kriittinen osa, joka sallii useiden säikeiden samanaikaisen lukemisen, mutta ei salli säiettä keskeytyä prosessissa.

Kohteen muuttaminen luettelossa

Harkitse esimerkiksi, kuinka voit muuttaa elementtiä erikseen linkitetyssä luettelossa käyttämällä tätä synkronointimekanismia.

Yleisen osoittimen roolia suorittaa tässä tapauksessa osoitin ensimmäiseen elementtiin. Kun kirjoitat, sinun on luotava kopio koko luettelosta, päivitettävä sitä kiinnostava elementti ja päivitettävä sitten globaali osoitin niin, että se osoittaa uuden luettelon ensimmäiseen elementtiin. Kaikki lukutoiminnot, jotka pääsivät luetteloon ennen sen päivitystä, saavat vanhan kopion, joka säilyy ennallaan; päivityksen jälkeen luetaan uusi kopio.

Tätä menetelmää ei voida kutsua tehokkaaksi, koska koko luettelo on kopioitava. Jos kuitenkin voidaan taata, että vain yksi listan elementti on luettavissa ja lukko päivittyy siirryttäessä seuraavaan , niin kirjoitettaessa voidaan jättää tarve kopioida ja muuttaa vain yksi elementti, jonka jälkeen päivitetään atomisesti osoitin luettelon edelliseen elementtiin (tai osoitin ensimmäiseen elementtiin).

Kohteen lisääminen luetteloon on hyvin samankaltainen kuin muuttaminen, mutta koska uutta kohdetta luotaessa ei ole käytettävissä tietoja, joihin ei ole pääsyä, sinun ei tarvitse olla varovainen sen suhteen, milloin tiedoista vanha kopio poistetaan.

Muistin vapauttaminen

Kun uusi elementti on luotu ja osoitin on päivitetty, elementin vanha kopio säilyy edelleen muistissa, eikä sitä voida poistaa ennen kuin kaikki lukijan säikeet, joilla on pääsy siihen, ovat avanneet sen. Voit tehdä tämän käyttämällä estäviä synkronointimekanismeja. Vaihtoehtona on ottaa huomioon se tosiasia, että lukeminen on kriittinen osa. Sitten kirjoitussäie ajoittaa itsensä vuorotellen jokaisen lukusäikeen jälkeen järjestelmäkutsulla. Tässä tapauksessa kaikki lukusäikeet käyvät taatusti kontekstinvaihdon läpi ja päätyvät siten käyttämään viittausta tietorakenteen vanhentuneeseen versioon.

Lukeminen kriittisellä alueella

Käytettäessä luku-muokkaa-kirjoitusalgoritmia ei voida tehdä oletuksia siitä, mitä tapahtuu kunkin dataa lukevan säikeen tietorakenteelle. Tämä tarkoittaa, että rakenneosoittimen tallentaminen ja käyttäminen kriittisen osan ulkopuolella ja jopa uuteen lukukriittiseen osioon syötettäessä voi johtaa virheeseen. Kaikki pääsy tietorakenteeseen tulee suorittaa vain kriittisessä osiossa, ja lukusäie voi tarvittaessa kopioida tietoja itselleen tänä aikana, minkä jälkeen se voi työskennellä paikallisella kopiollaan vapauttaen lukon ja vaarantamatta yrittää käyttää jo etäketjua, joka on aiemmin avattu kirjoittamista varten.

Lue-muokkaa-kirjoita Linuxissa

RCU-tuki on ollut Linux - käyttöjärjestelmässä ytimen versiosta 2.5 lähtien [3] . RCU API:n päätoiminnot:

1. rcu_read_lock()  - ilmoittaa, että virta on tullut kriittiseen osaan lukemista varten;
2. rcu_read_unlock()  - ilmoittaa lukusäikeen poistumisesta kriittisestä osasta;
3. synchronize_rcu()  - Kutsumalla tätä funktiota kirjoittamista varten avattu säie odottaa, kunnes kaikki lukutoiminnot, joilla oli pääsy tietorakenteen vanhaan versioon, ovat päättyneet. Sen jälkeen kirjoitettava stream voi poistaa vanhentuneen kopion ilmaiseksi.

Lisäksi suojatakseen kääntäjien optimointeja, jotka muuttavat käskyjen suoritusjärjestystä, makrot on määritelty tietorakenteeseen rcu_dereference() ja rcu_assign_pointer() johtavan osoittimen turvallista hankkimista ja päivittämistä varten.

Toiminnot ennen ja jälkeen tallennuksen

Ensin sinun on luettava tietorakenne, muokattava sen kopiota ja kirjoitettava sitten osoitin päivitettyyn tietorakenteeseen atomisesti .

Vaihtoehdot

Joillakin alustoilla (esim . RISC ) tämä ohje ei ole saatavilla. Vastaavia tuloksia voidaan saavuttaa seuraavien ohjeiden avulla:

1. lastaus merkillä (LL - kuorma linkitetty);
2. kirjoitusyritys (SC - tallenna ehdollinen).

Katso myös

• esto
• Synkronointi

Muistiinpanot

1. ↑ https://books.google.ru/books?id=zA7ECwAAQBAJ&pg=PA177&lpg=PA177&dq= "Lue-Kopioi-Päivitä"+read+copy
2. ↑ LDD
3. ↑ Arkistoitu kopio . Haettu 24. helmikuuta 2017. Arkistoitu alkuperäisestä 11. tammikuuta 2017. (määrätön)

Kirjallisuus

• Paul E. McKenney, John D. Slingwine. Read-Copy_update: suoritushistorian käyttäminen samanaikaisuusongelmien ratkaisemiseen . (määrätön)
• Mikä on RCU? . (määrätön)
• Paul E. McKenney, Jonathan Walpole. Mikä on RCU pohjimmiltaan? . (määrätön)

Linkit