Läs-kopiera-uppdatering

Inom datavetenskap är read-copy-update ( RCU ) en synkroniseringsmekanism som undviker användningen av låsprimitiver medan flera trådar samtidigt läser och uppdaterar element som är länkade via pekare och som tillhör delade datastrukturer (t.ex. länkade listor , träd , hashtabeller ).

Närhelst en tråd infogar eller tar bort element av datastrukturer i delat minne , garanteras alla läsare att se och gå igenom antingen den äldre eller den nya strukturen, och därför undviker inkonsekvenser (t.ex. avläsning av nollpekare ).

Den används när prestanda för läsningar är avgörande och är ett exempel på rum-tid-avvägning , vilket möjliggör snabba operationer till priset av mer utrymme. Detta gör att alla läsare fortsätter som om det inte vore någon synkronisering inblandad, därför kommer de att vara snabba, men också försvåra uppdateringar.

Namn och översikt

Namnet kommer från det sätt som RCU används för att uppdatera en länkad struktur på plats. En tråd som vill göra detta använder följande steg:

  • skapa en ny struktur,
  • kopiera data från den gamla strukturen till den nya och spara en pekare till den gamla strukturen,
  • ändra den nya, kopierade, strukturen,
  • uppdatera den globala pekaren för att hänvisa till den nya strukturen,
  • vila tills operativsystemets kärna bestämmer att det inte finns några läsare kvar med den gamla strukturen, till exempel i Linux-kärnan, genom att använda synchronize_rcu() ,
  • en gång väckt av kärnan, avallokera den gamla strukturen.

Så strukturen läses samtidigt med en trådkopiering för att göra en uppdatering , därav namnet "läs-kopia-uppdatering". Förkortningen "RCU" var ett av många bidrag från Linux-gemenskapen. Andra namn för liknande tekniker inkluderar passiv serialisering och MP defer av VM/XA -programmerare och generationer av K42- och Tornado -programmerare.

Detaljerad beskrivning

Läs-kopia-uppdatera infogningsprocedur. En tråd tilldelar en struktur med tre fält och ställer sedan in den globala pekaren gptr att peka på denna struktur.

En nyckelegenskap hos RCU är att läsare kan komma åt en datastruktur även när den håller på att uppdateras: RCU-uppdaterare kan inte blockera läsare eller tvinga dem att försöka igen. Denna översikt börjar med att visa hur data säkert kan infogas i och raderas från länkade strukturer trots samtidiga läsare. Det första diagrammet till höger visar en insättningsprocedur i fyra tillstånd, med tiden som går framåt från vänster till höger.

Det första tillståndet visar en global pekare med namnet gptr som initialt är NULL , färgad röd för att indikera att den kan nås av en läsare när som helst, vilket kräver att uppdaterare tar hand om den. Allokering av minne för en ny struktur övergår till det andra tillståndet. Denna struktur har obestämt tillstånd (indikeras med frågetecknen) men är otillgänglig för läsare (indikeras av den gröna färgen). Eftersom strukturen är otillgänglig för läsare, kan uppdateraren utföra vilken åtgärd som helst utan rädsla för att störa samtidiga läsare. Initiering av denna nya struktur övergår till det tredje tillståndet, som visar de initialiserade värdena för strukturens fält. Att tilldela en referens till denna nya struktur till gptr övergår till det fjärde och sista tillståndet. I detta tillstånd är strukturen tillgänglig för läsare och färgas därför röd. Primitivet rcu_assign_pointer används för att utföra denna uppgift och säkerställer att tilldelningen är atomär i den meningen att samtidiga läsare antingen kommer att se en NULL- pekare eller en giltig pekare till den nya strukturen, men inte någon sammanblandning av de två värdena. Ytterligare egenskaper för rcu_assign_pointer beskrivs längre fram i den här artikeln.

Läs-kopiera-uppdatera borttagningsprocedur

Denna procedur visar hur ny data kan infogas i en länkad datastruktur trots att läsare samtidigt går igenom datastrukturen före, under och efter infogningen. Det andra diagrammet till höger visar en raderingsprocedur i fyra tillstånd, återigen med tiden som går framåt från vänster till höger.

Det första tillståndet visar en länkad lista som innehåller elementen A , B och C . Alla tre element är färgade röda för att indikera att en RCU-läsare kan referera till någon av dem när som helst. Att använda list_del_rcu för att ta bort element B från denna lista övergår till det andra tillståndet. Observera att länken från element B till C lämnas intakt för att tillåta läsare som för närvarande refererar till element B att gå igenom resten av listan. Läsare som kommer åt länken från element A kommer antingen att få en referens till element B eller element C , men hur som helst kommer varje läsare att se en giltig och korrekt formaterad länkad lista. Element B är nu färgat gult för att indikera att även om redan existerande läsare fortfarande kan ha en referens till element B , har nya läsare inget sätt att få en referens. En vänta-på-läsare-operation övergår till det tredje tillståndet. Observera att denna vänta-på-läsare-operation bara behöver vänta på redan existerande läsare, men inte nya läsare. Element B är nu färgat grönt för att indikera att läsare inte längre kan referera till det. Därför är det nu säkert för uppdateringsprogrammet att frigöra element B och därmed övergå till det fjärde och sista tillståndet.

Det är viktigt att upprepa att i det andra tillståndet kan olika läsare se två olika versioner av listan, antingen med eller utan element B . Med andra ord ger RCU koordination i rymden (olika versioner av listan) såväl som i tiden (olika tillstånd i raderingsprocedurerna). Detta står i skarp kontrast till mer traditionella synkroniseringsprimitiver som låsning eller transaktioner som koordinerar i tid, men inte i rymden.

Denna procedur visar hur gammal data kan tas bort från en länkad datastruktur trots att läsare samtidigt går igenom datastrukturen före, under och efter raderingen. Med tanke på infogning och radering kan en mängd olika datastrukturer implementeras med hjälp av RCU.

RCU:s läsare körs inom kritiska sektioner på lässidan , som normalt är avgränsade av rcu_read_lock och rcu_read_unlock . Alla uttalanden som inte finns inom en kritisk sektion för RCU-lässidan sägs vara i ett vilande tillstånd , och sådana uttalanden tillåts inte innehålla referenser till RCU-skyddade datastrukturer, och det krävs inte heller vänta-på-läsare-operationen för att vänta för trådar i vila tillstånd. Varje tidsperiod under vilken varje tråd befinner sig minst en gång i ett viloläge kallas en respitperiod . Per definition måste alla kritiska avsnitt på RCU-lässidan som finns i början av en given respitperiod slutföras före utgången av den respitperioden, vilket utgör den grundläggande garantin som tillhandahålls av RCU. Dessutom måste vänta-på-läsare-operationen vänta tills minst en respitperiod löper ut. Det visar sig att denna garanti kan tillhandahållas med extremt små lässideskostnader, i själva verket, i det begränsade fallet som faktiskt realiseras av serverklass Linux-kärnbyggen, är lässidans overhead exakt noll.

RCU:s grundläggande garanti kan användas genom att dela upp uppdateringar i borttagnings- och återvinningsfaser . Borttagningsfasen tar bort referenser till dataposter inom en datastruktur (möjligen genom att ersätta dem med referenser till nya versioner av dessa dataposter), och kan köras samtidigt med RCU lässida kritiska sektioner. Anledningen till att det är säkert att köra borttagningsfasen samtidigt med RCU-läsare är semantiken hos moderna processorer som garanterar att läsare kommer att se antingen den gamla eller den nya versionen av datastrukturen snarare än en delvis uppdaterad referens. När en respitperiod har förflutit kan det inte längre finnas några läsare som hänvisar till den gamla versionen, så det är säkert för återvinningsfasen att frigöra ( återta ) de dataobjekt som utgjorde den gamla versionen.

Genom att dela upp en uppdatering i borttagnings- och återvinningsfaser kan uppdateraren utföra borttagningsfasen omedelbart och skjuta upp återvinningsfasen tills alla läsare som är aktiva under borttagningsfasen har slutförts, med andra ord tills en respitperiod har förflutit.

Så den typiska RCU-uppdateringssekvensen ser ungefär ut som följande:

  1. Se till att alla läsare som har åtkomst till RCU-skyddade datastrukturer utför sina referenser inifrån en kritisk sektion på RCU-lässidan.
  2. Ta bort pekare till en datastruktur så att efterföljande läsare inte kan få en referens till den.
  3. Vänta tills en respitperiod har förflutit så att alla tidigare läsare (som fortfarande kan ha pekare till datastrukturen borttagen i föregående steg) kommer att ha slutfört sina kritiska avsnitt på RCU-lässidan.
  4. Vid denna tidpunkt kan det inte finnas några läsare som fortfarande har referenser till datastrukturen, så den kan nu säkert återtas (t.ex. frigöras).

I proceduren ovan (som matchar det tidigare diagrammet) utför uppdateringsprogrammet både borttagnings- och återvinningssteget, men det är ofta till hjälp för en helt annan tråd att göra återvinningen. Referensräkning kan användas för att låta läsaren utföra borttagning, så även om samma tråd utför både uppdateringssteget (steg (2) ovan) och återvinningssteget (steg (4) ovan), är det ofta bra att tänka på dem separat.

RCU är kanske den vanligaste icke-blockerande algoritmen för en delad datastruktur. RCU är helt väntefritt för hur många läsare som helst. Enskrivarimplementationer RCU är också låsfria för skrivaren. Vissa multi-writer implementeringar av RCU är låsfria. Andra multi-writer implementeringar av RCU serialiserar writers med ett lås.

Används

I början av 2008 fanns det nästan 2 000 användningar av RCU API inom Linux-kärnan inklusive nätverksprotokollstackarna och minneshanteringssystemet. I mars 2014 fanns det mer än 9 000 användningar. Sedan 2006 har forskare tillämpat RCU och liknande tekniker på ett antal problem, inklusive hantering av metadata som används i dynamisk analys, hantering av livslängden för klustrade objekt, hantering av objektlivslängd i K42-forskningsoperativsystemet och optimering av transaktionsminnesimplementeringar av programvara . Dragonfly BSD använder en teknik som liknar RCU som mest liknar Linuxs Sleepable RCU (SRCU) implementering.

Fördelar och nackdelar

Möjligheten att vänta tills alla läsare är klara gör att RCU-läsare kan använda mycket lättare synkronisering – i vissa fall absolut ingen synkronisering alls. Däremot, i mer konventionella låsbaserade system, måste läsare använda tungviktssynkronisering för att förhindra att en uppdateringsprogram raderar datastrukturen under dem. Anledningen är att låsbaserade uppdaterare vanligtvis uppdaterar data på plats och måste därför utesluta läsare. Däremot drar RCU-baserade uppdateringar vanligtvis fördel av det faktum att skrivningar till enstaka riktade pekare är atomära på moderna processorer, vilket tillåter atominsättning, borttagning och ersättning av data i en länkad struktur utan att störa läsarna. Samtidiga RCU-läsare kan sedan fortsätta att komma åt de gamla versionerna och kan avstå från atomära läs-modifiera-skriv-instruktioner, minnesbarriärer och cachemissar som är så dyra på moderna SMP -datorsystem, även i frånvaro av låsstridigheter. Den lätta naturen hos RCU:s lässidas primitiver ger ytterligare fördelar utöver utmärkt prestanda, skalbarhet och realtidssvar. Till exempel ger de immunitet mot de flesta deadlock och livelock-förhållanden.

RCU har förstås också nackdelar. Till exempel är RCU en specialiserad teknik som fungerar bäst i situationer med mestadels läsningar och få uppdateringar, men som ofta är mindre tillämplig på arbetsbelastningar endast för uppdateringar. Till ett annat exempel, även om det faktum att RCU-läsare och uppdaterare kan köras samtidigt är det som möjliggör den lätta karaktären hos RCU:s lässidas primitiver, kanske vissa algoritmer inte är mottagliga för att läsa/uppdatera samtidighet.

Trots mer än ett decenniums erfarenhet av RCU är den exakta omfattningen av dess tillämpbarhet fortfarande ett forskningsämne.

Patent

Tekniken täcks av US Patent US Patent 5,442,758 , utfärdat 15 augusti 1995 och tilldelat Sequent Computer Systems, såväl som US Patent 5,608,893 (upphört 2009-03-30), US Patent 5,7027-4027-5,027-5 . ), US-patent 6 219 690 (upphörde 2009-05-18) och US-patent 6 886 162 (upphörde 2009-05-25). Det nu utgångna US-patentet US-patent 4 809 168 täcker en närbesläktad teknik. RCU är också ämnet för ett anspråk i rättegången SCO mot IBM .

Exempel på RCU-gränssnitt

RCU är tillgänglig i ett antal operativsystem och lades till i Linux-kärnan i oktober 2002. Implementeringar på användarnivå som liburcu är också tillgängliga.

Implementeringen av RCU i version 2.6 av Linux-kärnan är bland de mer kända RCU-implementeringarna och kommer att användas som inspiration för RCU API i resten av denna artikel. Kärn-API ( Application Programming Interface ) är ganska liten:

  • rcu_read_lock(): Markerar en RCU-skyddad datastruktur så att den inte kommer att återtas under hela den kritiska sektionen.
  • rcu_read_unlock(): Används av en läsare för att informera återställaren om att läsaren lämnar en kritisk sektion på RCU-lässidan. Observera att kritiska avsnitt på RCU-lässidan kan vara kapslade och/eller överlappande.
  • synchronize_rcu(): Blockerar tills alla redan existerande RCU-läs-kritiska avsnitt på alla CPU:er har slutförts. Observera att synchronize_rcu inte nödvändigtvis kommer att vänta på att några efterföljande kritiska avsnitt på RCU-lässidan ska slutföras. Tänk till exempel på följande händelseförlopp: 
 CPU 0 CPU 1 CPU 2 ------------------ -------------------------- -- ------------- 1. rcu_read_lock() 2. går in i synchronize_rcu() 3. rcu_read_lock() 4. rcu_read_unlock() 5. avslutar synchronize_rcu() 6. rcu_read_unlock()
Eftersom synchronize_rcu är API: et som måste ta reda på när läsarna är klara, dess implementering är nyckeln till RCU. För att RCU ska vara användbar i alla utom de mest läsintensiva situationerna synchronize_rcus overhead också vara ganska liten.
Alternativt, istället för att blockera, kan synchronize_rcu registrera en återuppringning som ska anropas efter att alla pågående kritiska avsnitt av RCU-lässidan har slutförts. Denna callback-variant kallas call_rcu i Linux-kärnan.
  • rcu_assign_pointer(): Uppdateraren använder denna funktion för att tilldela ett nytt värde till en RCU-skyddad pekare, för att på ett säkert sätt kommunicera ändringen i värde från uppdateraren till läsaren. Denna funktion returnerar det nya värdet och exekverar även alla minnesbarriärinstruktioner som krävs för en given CPU-arkitektur. Kanske ännu viktigare, det tjänar till att dokumentera vilka pekare som skyddas av RCU.
  • rcu_dereference(): Läsaren använder rcu_dereference för att hämta en RCU-skyddad pekare, som returnerar ett värde som sedan kan avläsas på ett säkert sätt. Den exekverar också alla direktiv som krävs av kompilatorn eller CPU:n, till exempel en flyktig cast för gcc, en memory_order_consume-belastning för C/C++11 eller minnesbarriärinstruktionen som krävs av den gamla DEC Alpha CPU. Värdet som returneras av rcu_dereference är endast giltigt inom den omslutande RCU:s kritiska sektion. Precis som med rcu_assign_pointer är en viktig funktion för rcu_dereference att dokumentera vilka pekare som skyddas av RCU.
RCU API-kommunikation mellan läsaren, uppdateraren och återvinningsprogrammet

Diagrammet till höger visar hur varje API kommunicerar mellan läsaren, uppdateraren och återställaren.

RCU-infrastrukturen observerar tidssekvensen för rcu_read_lock , rcu_read_unlock , synchronize_rcu och call_rcu -anrop för att bestämma när (1) synchronize_rcu -anrop kan återvända till deras anropare och (2) call_rcu -återuppringningar kan anropas. Effektiva implementeringar av RCU-infrastrukturen använder mycket batchning för att amortera deras overhead över många användningar av motsvarande API:er.

Enkel implementering

RCU har extremt enkla "leksaks"-implementationer som kan underlätta förståelsen av RCU. Det här avsnittet presenterar en sådan "leksak"-implementering som fungerar i en icke-förebyggande miljö . 

   

   

      

    


 

        0

     
        

          
         
 void  rcu_read_lock  (  void  )  {  }  void  rcu_read_unlock  (  void  )  {  }  void  call_rcu  (  void  (  *  callback  )  (  void  *  ),  void  *  arg  )  {  // add callback/arg-par till en lista  }  void  synchronize_rcu  (  void  )  {  int  cpu  ,  ncpus  =  ;  för  varje_cpu  (  cpu  )  schedule_current_task_to  (  cpu  );  för  varje  post  i  call_rcu  listposten  ->  callback  (  post  -  >  arg  )  ;  }

I kodexemplet kan rcu_assign_pointer och rcu_dereference ignoreras utan att missa mycket. De behövs dock för att undertrycka skadlig kompilatoroptimering och för att förhindra att CPU:er ordnar om åtkomster. 










 #define rcu_assign_pointer(p, v) ({ \  smp_wmb();  /* Beställ tidigare skrivningar. */  \  ACCESS_ONCE(p) = (v); \  })  #define rcu_dereference(p) ({ \  typeof(p) _value = ACCESS_ONCE(p); \  smp_read_barrier_depends();  /* nop på de flesta arkitekturer */  \  (_value); \  })

Observera att rcu_read_lock och rcu_read_unlock inte gör något. Detta är den stora styrkan hos klassisk RCU i en icke-förebyggande kärna: lässidans overhead är exakt noll, eftersom smp_read_barrier_depends() är ett tomt makro på alla utom DEC Alpha CPU:er; [ misslyckad verifiering ] sådana minnesbarriärer behövs inte på moderna processorer. Makrot ACCESS_ONCE() är en flyktig cast som inte genererar någon ytterligare kod i de flesta fall. Och det finns inget sätt att rcu_read_lock kan delta i en deadlock- cykel, orsaka att en realtidsprocess missar sin schemaläggningsdeadline, fälla ut prioritetsinversion eller resultera i hög låskonflikt . Men i denna leksaks-RCU-implementering är blockering inom en kritisk sektion på RCU-lässidan olagligt, precis som blockering när du håller ett rent spinlock.

Implementeringen av synchronize_rcu flyttar anroparen av synchronize_cpu till varje CPU, vilket blockerar tills alla CPU:er har kunnat utföra kontextväxlingen. Kom ihåg att detta är en icke-förebyggande miljö och att blockering inom en kritisk sektion på RCU-lässidan är olaglig, vilket innebär att det inte kan finnas några preemptionspunkter inom en kritisk sektion för RCU-lässidan. Därför, om en given CPU exekverar en kontextväxling (för att schemalägga en annan process), vet vi att denna CPU måste ha slutfört alla föregående RCU-läs-kritiska avsnitt. När väl alla CPU:er har utfört en kontextväxling kommer alla föregående kritiska avsnitt på RCU:n att ha slutförts.

Analogi med läsare-skrivare låsning

Även om RCU kan användas på många olika sätt, är en mycket vanlig användning av RCU analog med läsare-skrivare låsning. Följande koddisplay sida vid sida visar hur nära relaterade läsar-skrivare-låsning och RCU kan vara.

                 

                                   
                            
                                     
                             
                                     
                     
                                        
                          

                 
                                         
                                   
                                         
                                  
                                  
                                       
                                           
                                         
    0                               0
                                       

                          
                                         
                                   
                                         
               
                                  
                                     
                                       
                                           
                                         
    0                               0
                                        /* läsare-skrivarlåsning */  /* RCU */  1  struct  el  {  1  struct  el  {  2  struct  list_head  lp  ;  2  struct  list_head  lp  ;  3  långa  nyckel  ;  3  långa  nyckel  ;  4  spinlock_t  mutex  ;  4  spinlock_t  mutex  ;  5  int  data  ;  5  int  data  ;  6  /* Övriga datafält */  6  /* Övriga datafält */  7  };  7  };                   8  DEFINE_RWLOCK  (  listmutex  );  8  DEFINE_SPINLOCK  (  listmutex  ); 
 9  LIST_HEAD  (  huvud  );  9  LIST_HEAD  (  huvud  );  1  int  sökning  (  long  key  ,  int  *  resultat  )  1  int  sökning  (  long  key  ,  int  *  resultat  )  2  {  2  {  3  struct  el  *  p  ;  3  struktur  el  *  p  ;  4  4                        5  read_lock  (  &  listmutex  );  5  rcu_read_lock  (); 
                6  list_for_each_entry  (  p  ,  &  head  ,  lp  )  {  6  list_for_each_entry_rcu  (  p  ,  &  head  ,  lp  )  { 
 7  if  (  p  ->  key  ==  key  )  {  7  if  (  p  ->  key  ==  key  )  {  8  *  result  =  p  ->  data  ;  8  *  resultat  =  p  ->  data  ;                          9  read_unlock  (  &  ​​listmutex  );  9  rcu_read_unlock  (); 
 10  retur  1  ;  10  retur  1  ;  11  }  11  }  12  }  12  }                    13  read_unlock  (  &  ​​listmutex  );  13  rcu_read_unlock  (); 
 14  retur  ;  14  retur  ;  15  }  15  }  1  int  radera  (  lång  tangent  )  1  int  radera  (  lång  tangent  )  2  {  2  {  3  struct  el  *  p  ;  3  struktur  el  *  p  ;  4  4                       5  write_lock  (  &  listmutex  );  5  spin_lock  (  &  listmutex  ); 
 6  list_for_each_entry  (  p  ,  &  head  ,  lp  )  {  6  list_for_each_entry  (  p  ,  &  head  ,  lp  )  {  7  if  (  p  ->  key  ==  key  )  {  7  if  (  p  ->  key  ==  key  )  {                                 8  list_del  (  &  p  ->  lp  );  8  list_del_rcu  (  &  p  ->  lp  ); 
                        9  write_unlock  (  &  listmutex  );  9  spin_unlock  (  &  listmutex  ); 
                                                 10  synchronize_rcu  (); 
 10  kfritt  (  p  );  11  kfritt  (  p  );  11  retur  1  ;  12  retur  1  ;  12  }  13  }  13  }  14  }                   14  write_unlock  (  &  ​​listmutex)  ;  15  spin_unlock  (  &  listmutex  ); 
 15  retur  ;  16  retur  ;  16  }  17  }

Skillnaderna mellan de två tillvägagångssätten är ganska små. Låsning på lässidan flyttas till rcu_read_lock och rcu_read_unlock , låsning på uppdateringssidan flyttas från ett läsar-skrivarlås till ett enkelt spinlock, och en synchronize_rcu föregår kfree .

Det finns dock en potentiell hake: de kritiska avsnitten på lässidan och uppdateringssidan kan nu köras samtidigt. I många fall kommer detta inte att vara ett problem, men det är nödvändigt att kontrollera noggrant oavsett. Till exempel, om flera oberoende listuppdateringar måste ses som en enda atomuppdatering, kommer konvertering till RCU att kräva särskild omsorg.

Dessutom innebär närvaron av synchronize_rcu att RCU-versionen av delete nu kan blockera. Om detta är ett problem call_rcu användas som call_rcu (kfree, p) istället för synchronize_rcu . Detta är särskilt användbart i kombination med referensräkning.

Historia

Tekniker och mekanismer som liknar RCU har uppfunnits oberoende flera gånger:

  1. HT Kung och Q. Lehman beskrev användningen av sopsamlare för att implementera RCU-liknande tillgång till ett binärt sökträd.
  2. Udi Manber och Richard Ladner utökade Kungs och Lehmans arbete till icke-sopsamlade miljöer genom att skjuta upp återvinningen tills alla trådar som körs vid borttagningstidpunkten har avslutats, vilket fungerar i miljöer som inte har långlivade trådar.
  3. Richard Rashid et al. beskrev en implementering av lazy translation lookaside buffer (TLB) som skjutit upp återtagandet av virtuellt adressutrymme tills alla CPU:er har tömt sin TLB, vilket i sin anda liknar vissa RCU-implementeringar.
  4. James P. Hennessy, Damian L. Osisek och Joseph W. Seigh, II beviljades US-patent 4 809 168 1989 (sedan förfallit). Detta patent beskriver en RCU-liknande mekanism som uppenbarligen användes i VM/XA på IBM stordatorer .
  5. William Pugh beskrev en RCU-liknande mekanism som förlitade sig på explicit flagginställning av läsare.
  6. Aju John föreslog en RCU-liknande implementering där uppdaterare helt enkelt väntar på en bestämd tidsperiod, under antagandet att alla läsare skulle slutföra inom den fasta tiden, vilket kan vara lämpligt i ett hårt realtidssystem. Van Jacobson föreslog ett liknande system 1993 (verbal kommunikation).
  7. J. Slingwine och PE McKenney fick US-patent 5 442 758 i augusti 1995, som beskriver RCU som implementerad i DYNIX/ptx och senare i Linux-kärnan.
  8. B. Gamsa, O. Krieger, J. Appavoo och M. Stumm beskrev en RCU-liknande mekanism som används i Tornado-forskningsoperativsystemet vid University of Toronto och det närbesläktade forskningsoperativsystemet IBM Research K42 .
  9. Rusty Russell och Phil Rumpf beskrev RCU-liknande tekniker för att hantera avlastning av Linux-kärnmoduler.
  10. D. Sarma lade till RCU till version 2.5.43 av Linux-kärnan i oktober 2002.
  11. Robert Colvin et al. formellt verifierat en lat samtidig listbaserad uppsättningsalgoritm som liknar RCU.
  12. M. Desnoyers et al. publicerade en beskrivning av användarutrymme RCU.
  13. A. Gotsman et al. härledd formell semantik för RCU baserad på separationslogik.
  14. Ilan Frenkel, Roman Geller, Yoram Ramberg och Yoram Snir beviljades amerikanskt patent 7 099 932 2006. Detta patent beskriver en RCU-liknande mekanism för att hämta och lagra information om kvalitetspolicyhantering med hjälp av en katalogtjänst på ett sätt som upprätthåller läsning/skrivning konsistens och möjliggör läs/skriv samtidighet.

Se även

Anteckningar

Bauer, RT, (juni 2009), "Operational Verification of a Relativistic Program" PSU Tech Report TR-09-04 ( http://www.pdx.edu/sites/www.pdx.edu.computer-science/files/ tr0904.pdf )

externa länkar

Hämtad från " https://en.wikipedia.org/w/index.php?title=Read-copy-update&oldid=1101922057 "