Czytaj-kopiuj-aktualizuj

W informatyce , odczyt-kopiowanie-aktualizacja ( RCU ) jest mechanizmem synchronizacji , który pozwala uniknąć użycia prymitywów blokujących , podczas gdy wiele wątków jednocześnie odczytuje i aktualizuje elementy, które są połączone za pomocą wskaźników i które należą do współdzielonych struktur danych (np. połączone listy , drzewa , tablice mieszające ).

Zawsze, gdy wątek wstawia lub usuwa elementy struktur danych w pamięci współdzielonej , wszyscy czytelnicy mają gwarancję, że zobaczą starszą lub nową strukturę i przejdą przez nią, unikając w ten sposób niespójności (np. wyłuskiwania zerowych wskaźników ).

Jest używany, gdy wydajność odczytów jest kluczowa i jest przykładem kompromisu czasoprzestrzennego , umożliwiającego szybkie operacje kosztem większej przestrzeni. To sprawia, że wszystkie czytniki działają tak, jakby nie było synchronizacji , stąd będą szybkie, ale także utrudniają aktualizacje.

Nazwa i przegląd

Nazwa pochodzi od sposobu, w jaki RCU jest używany do aktualizowania połączonej struktury na miejscu. Wątek, który chce to zrobić, wykonuje następujące kroki:

stworzyć nową strukturę,
skopiuj dane ze starej struktury do nowej i zapisz wskaźnik do starej struktury,
modyfikować nową, skopiowaną strukturę,
zaktualizuj globalny wskaźnik, aby odnosił się do nowej struktury,
spać, dopóki jądro systemu operacyjnego nie ustali, że nie ma już czytników korzystających ze starej struktury, na przykład w jądrze Linuksa, za pomocą synchronize_rcu() ,
po przebudzeniu przez jądro, usuń starą strukturę.

Tak więc struktura jest odczytywana równolegle z kopiowaniem wątku w celu wykonania aktualizacji , stąd nazwa „aktualizacja odczytu i kopiowania”. Skrót „RCU” był jednym z wielu wkładów społeczności Linuksa. Inne nazwy podobnych technik obejmują pasywną serializację i odroczenie MP przez programistów VM / XA oraz generacje przez programistów K42 i Tornado .

Szczegółowy opis

Procedura wstawiania odczytu-kopiowania-aktualizacji. Wątek przydziela strukturę z trzema polami, a następnie ustawia globalny wskaźnik gptr , aby wskazywał na tę strukturę.

Kluczową właściwością RCU jest to, że czytelnicy mogą uzyskać dostęp do struktury danych nawet wtedy, gdy jest ona w trakcie aktualizacji: aktualizatory RCU nie mogą blokować czytników ani zmuszać ich do ponawiania prób dostępu. To omówienie rozpoczyna się od pokazania, w jaki sposób dane mogą być bezpiecznie wstawiane do połączonych struktur i usuwane z nich pomimo współbieżnych czytników. Pierwszy diagram po prawej stronie przedstawia czterostanową procedurę wstawiania, z upływem czasu od lewej do prawej.

Pierwszy stan pokazuje globalny wskaźnik o nazwie gptr , który początkowo ma wartość NULL i ma kolor czerwony, aby wskazać, że czytelnik może uzyskać do niego dostęp w dowolnym momencie, co wymaga od aktualizatorów zachowania ostrożności. Alokacja pamięci dla nowej struktury przechodzi do drugiego stanu. Struktura ta ma stan nieokreślony (oznaczony pytajnikami), ale jest niedostępna dla czytelników (oznaczony kolorem zielonym). Ponieważ struktura jest niedostępna dla czytników, aktualizator może wykonać dowolną operację bez obawy o zakłócenie pracy czytników równoczesnych. Inicjowanie tej nowej struktury powoduje przejście do trzeciego stanu, w którym są wyświetlane zainicjowane wartości pól struktury. Przypisanie odniesienia do tej nowej struktury do gptr przechodzi do czwartego i ostatniego stanu. W tym stanie struktura jest dostępna dla czytelników i dlatego jest zabarwiona na czerwono. Operacja rcu_assign_pointer jest używana do wykonania tego przypisania i zapewnia, że przypisanie jest atomowe w tym sensie, że współbieżni czytelnicy zobaczą albo wskaźnik NULL , albo prawidłowy wskaźnik do nowej struktury, ale nie połączenie tych dwóch wartości. Dodatkowe właściwości rcu_assign_pointer opisano w dalszej części tego artykułu.

Procedura usuwania odczytu-kopiowania-aktualizacji

Ta procedura pokazuje, w jaki sposób nowe dane mogą być wstawiane do połączonej struktury danych, nawet jeśli czytniki jednocześnie przechodzą przez strukturę danych przed, w trakcie i po wstawieniu. Drugi diagram po prawej przedstawia procedurę usuwania czterech stanów, ponownie z upływem czasu od lewej do prawej.

Pierwszy stan pokazuje połączoną listę zawierającą elementy $A$ , $B$ i $C$ . Wszystkie trzy elementy są koloru czerwonego, aby wskazać, że czytnik RCU może odwołać się do dowolnego z nich w dowolnym momencie. Użycie list_del_rcu do usunięcia elementu $B$ z tej listy powoduje przejście do drugiego stanu. Zwróć uwagę, że link z elementu B do C pozostaje nienaruszony, aby umożliwić czytelnikom, którzy aktualnie odwołują się do elementu $B$ , przeglądanie pozostałej części listy. Czytelnicy uzyskujący dostęp do łącza z elementu $A$ otrzymają odniesienie do elementu $B$ lub element $C$ , ale tak czy inaczej, każdy czytelnik zobaczy prawidłową i poprawnie sformatowaną połączoną listę. Element $B$ jest teraz w kolorze żółtym, aby wskazać, że chociaż istniejący czytelnicy mogą nadal mieć odniesienie do elementu $B$ , nowi czytelnicy nie mają możliwości uzyskania odniesienia. Operacja oczekiwania na czytniki przechodzi do stanu trzeciego. Należy zauważyć, że ta operacja oczekiwania na czytniki musi czekać tylko na wcześniej istniejących czytelników, ale nie na nowych czytelników. Element $B$ ma teraz kolor zielony, aby wskazać, że czytelnicy nie mogą się już do niego odwoływać. Dlatego aktualizator może teraz bezpiecznie zwolnić element $B$ , przechodząc w ten sposób do czwartego i końcowego stanu.

Ważne jest, aby powtórzyć, że w drugim stanie różni czytelnicy mogą zobaczyć dwie różne wersje listy, z elementem $B lub bez niego$ . Innymi słowy, RCU zapewnia koordynację zarówno w przestrzeni (różne wersje listy), jak iw czasie (różne stany w procedurach usuwania). Stoi to w wyraźnej sprzeczności z bardziej tradycyjnymi prymitywami synchronizacji, takimi jak blokowanie lub transakcje , które koordynują w czasie, ale nie w przestrzeni.

Ta procedura pokazuje, jak stare dane można usunąć z połączonej struktury danych, nawet jeśli czytelnicy jednocześnie przeglądają strukturę danych przed, w trakcie i po usunięciu. Biorąc pod uwagę wstawianie i usuwanie, za pomocą RCU można zaimplementować szeroką gamę struktur danych.

Czytniki RCU działają w sekcjach krytycznych po stronie odczytu , które zwykle są ograniczone przez rcu_read_lock i rcu_read_unlock . Mówi się, że każda instrukcja, która nie znajduje się w sekcji krytycznej po stronie odczytu RCU, znajduje się w stanie spoczynku , a takie instrukcje nie mogą zawierać odniesień do struktur danych chronionych przez RCU, ani operacja oczekiwania na czytniki nie jest wymagana do czekania dla wątków w stanie spoczynku. Każdy okres, w którym każdy wątek znajduje się co najmniej raz w stanie spoczynku, nazywany jest okresem prolongaty . Z definicji każda sekcja krytyczna po stronie odczytu RCU istniejąca na początku danego okresu karencji musi zostać zakończona przed końcem tego okresu prolongaty, co stanowi podstawową gwarancję zapewnianą przez RCU. Ponadto operacja oczekiwania na czytniki musi czekać na upłynięcie co najmniej jednego okresu prolongaty. Okazuje się, że ta gwarancja może być zapewniona przy bardzo małych narzutach po stronie odczytu, w rzeczywistości w przypadku ograniczającym, który jest faktycznie realizowany przez kompilacje jądra Linuksa klasy serwerowej, narzut po stronie odczytu wynosi dokładnie zero.

Podstawową gwarancję RCU można wykorzystać, dzieląc aktualizacje na fazy usuwania i odzyskiwania . Faza usuwania usuwa odniesienia do elementów danych w strukturze danych (być może poprzez zastąpienie ich odniesieniami do nowych wersji tych elementów danych) i może przebiegać równolegle z sekcjami krytycznymi po stronie odczytu RCU. Powodem, dla którego bezpieczne jest uruchamianie fazy usuwania równolegle z czytnikami RCU, jest semantyka nowoczesnych procesorów, która gwarantuje, że czytelnicy zobaczą albo starą, albo nową wersję struktury danych, a nie częściowo zaktualizowaną referencję. Po upływie okresu karencji nie może już być żadnych czytelników odwołujących się do starej wersji, więc można bezpiecznie zwolnić fazę odzyskiwania ( reclaim ) elementy danych, które tworzyły tę starą wersję.

Podział aktualizacji na fazy usuwania i odzyskiwania umożliwia aktualizatorowi natychmiastowe wykonanie fazy usuwania i odroczenie fazy odzyskiwania do czasu zakończenia wszystkich czytników aktywnych w fazie usuwania, innymi słowy do upływu okresu karencji.

Typowa sekwencja aktualizacji RCU wygląda następująco:

Upewnij się, że wszystkie czytniki uzyskujące dostęp do struktur danych chronionych przez RCU wykonują swoje odwołania z sekcji krytycznej po stronie odczytu RCU.
Usuń wskaźniki do struktury danych, aby kolejni czytelnicy nie mogli uzyskać do niej odniesienia.
Poczekaj, aż upłynie okres prolongaty, aby wszystkie poprzednie czytniki (które mogą nadal mieć wskaźniki do struktury danych usunięte w poprzednim kroku) ukończyły krytyczne sekcje RCU po stronie odczytu.
W tym momencie nie może być żadnych czytników, które nadal przechowują odniesienia do struktury danych, więc teraz można ją bezpiecznie odzyskać (np. zwolnić).

W powyższej procedurze (która jest zgodna z wcześniejszym diagramem) aktualizator wykonuje zarówno krok usuwania, jak i odzyskiwania, ale często pomocne jest, aby całkowicie inny wątek wykonał odzyskanie. Zliczanie odwołań może być wykorzystane do umożliwienia czytelnikowi usunięcia, więc nawet jeśli ten sam wątek wykonuje zarówno krok aktualizacji (krok (2) powyżej), jak i krok odzyskiwania (krok (4) powyżej), często warto o nich pomyśleć osobno.

RCU jest prawdopodobnie najbardziej powszechnym algorytmem nieblokującym dla współdzielonej struktury danych. RCU jest całkowicie wolny od oczekiwania dla dowolnej liczby czytników. Implementacje RCU z jednym pisarzem są również wolne od blokad dla pisarza. Niektóre implementacje RCU z wieloma zapisami są wolne od blokad. Inne wielozadaniowe implementacje pisarzy RCU serializują z blokadą.

Używa

Na początku 2008 r. w jądrze Linuksa użyto prawie 2000 interfejsów API RCU, w tym stosów protokołów sieciowych i systemu zarządzania pamięcią. W marcu 2014 r. było ponad 9 000 zastosowań. Od 2006 roku badacze stosują RCU i podobne techniki do wielu problemów, w tym do zarządzania metadanymi używanymi w analizie dynamicznej, zarządzania czasem życia klastrowanych obiektów, zarządzania czasem życia obiektów w badawczym systemie operacyjnym K42 oraz optymalizowania implementacji pamięci transakcyjnej oprogramowania . Ważka BSD wykorzystuje technikę podobną do RCU, która najbardziej przypomina implementację Sleepable RCU (SRCU) w Linuksie.

Zalety i wady

Możliwość czekania, aż wszystkie czytniki zakończą pracę, pozwala czytnikom RCU na korzystanie z dużo lżejszej synchronizacji — w niektórych przypadkach w ogóle bez synchronizacji. W przeciwieństwie do tego, w bardziej konwencjonalnych schematach opartych na blokadach, czytniki muszą używać ciężkiej synchronizacji, aby uniemożliwić aktualizatorowi usunięcie struktury danych spod nich. Powodem jest to, że aktualizatory oparte na blokadach zwykle aktualizują dane na miejscu i dlatego muszą wykluczać czytniki. W przeciwieństwie do tego, aktualizatory oparte na RCU zazwyczaj wykorzystują fakt, że zapisy do pojedynczych wyrównanych wskaźników są atomowe na nowoczesnych procesorach, umożliwiając niepodzielne wstawianie, usuwanie i zastępowanie danych w połączonej strukturze bez zakłócania pracy czytników. Współbieżne czytniki RCU mogą następnie nadal uzyskiwać dostęp do starych wersji i mogą zrezygnować z atomowych instrukcji odczytu, modyfikacji i zapisu, barier pamięci i braków w pamięci podręcznej, które są tak drogie w nowoczesnych SMP , nawet w przypadku braku rywalizacji o blokadę. Lekki charakter prymitywów RCU po stronie odczytu zapewnia dodatkowe korzyści poza doskonałą wydajnością, skalowalnością i reakcją w czasie rzeczywistym. Na przykład zapewniają odporność na większość warunków impasu i livelocka.

Oczywiście RCU ma również wady. Na przykład RCU to specjalistyczna technika, która najlepiej sprawdza się w sytuacjach, w których przeważają odczyty i niewielka liczba aktualizacji, ale często jest mniej odpowiednia w przypadku obciążeń wymagających tylko aktualizacji. Dla innego przykładu, chociaż fakt, że czytniki RCU i aktualizatory mogą wykonywać jednocześnie, umożliwia lekki charakter prymitywów RCU po stronie odczytu, niektóre algorytmy mogą nie nadawać się do współbieżności odczytu/aktualizacji.

Pomimo ponad dziesięcioletniego doświadczenia z RCU, dokładny zakres jego zastosowania jest nadal przedmiotem badań.

Patenty

Technika ta jest objęta amerykańskim patentem na oprogramowanie US Patent 5,442,758 wydanym 15 sierpnia 1995 r. i przekazanym firmie Sequent Computer Systems , a także patentem US 5,608,893 (wygasł 2009-03-30), patentem US 5,727,209 (wygasł 2010-04-05 ), patent USA 6,219,690 (wygasł 2009-05-18) i patent USA 6,886,162 (wygasł 2009-05-25). Wygasły już patent US Patent US 4,809,168 obejmuje blisko spokrewnioną technikę. RCU jest również przedmiotem jednego roszczenia w sprawie SCO przeciwko IBM pozew .

Przykładowy interfejs RCU

RCU jest dostępny w wielu systemach operacyjnych i został dodany do jądra Linuksa w październiku 2002. Dostępne są również implementacje na poziomie użytkownika, takie jak liburcu .

Implementacja RCU w wersji 2.6 jądra Linuksa jest jedną z bardziej znanych implementacji RCU i zostanie wykorzystana jako inspiracja dla API RCU w dalszej części tego artykułu. Podstawowy interfejs API ( interfejs programowania aplikacji ) jest dość mały:

rcu_read_lock(): Zaznacza strukturę danych chronioną przez RCU, aby nie została odzyskana przez cały czas trwania tej krytycznej sekcji.
rcu_read_unlock(): Używany przez czytnik do informowania reclaimera, że czytnik opuszcza sekcję krytyczną po stronie odczytu RCU. Należy zauważyć, że sekcje krytyczne po stronie odczytu RCU mogą być zagnieżdżone i/lub nakładać się.
synchronize_rcu(): Blokuje, dopóki wszystkie istniejące wcześniej krytyczne sekcje RCU po stronie odczytu na wszystkich procesorach nie zostaną zakończone. Zauważ, że synchronize_rcu niekoniecznie będzie czekać na zakończenie kolejnych sekcji krytycznych po stronie odczytu RCU. Rozważmy na przykład następującą sekwencję zdarzeń:

 Procesor 0 Procesor 1 Procesor 2 ------------------ --------------------------------------- -- ------------- 1. rcu_read_lock() 2. wchodzi do synchronize_rcu() 3. rcu_read_lock() 4. rcu_read_unlock() 5. wychodzi z synchronize_rcu() 6. rcu_read_unlock()

Ponieważ synchronize_rcu jest API który musi dowiedzieć się, kiedy czytniki skończą, jego implementacja jest kluczem do RCU. Aby RCU był użyteczny we wszystkich sytuacjach z wyjątkiem najbardziej intensywnych odczytów, synchronize_rcu Koszty ogólne również muszą być dość niewielkie.

Alternatywnie, zamiast blokowania, synchronize_rcu może zarejestrować wywołanie zwrotne do wywołania po zakończeniu wszystkich trwających sekcji krytycznych po stronie odczytu RCU. Ten wariant wywołania zwrotnego nazywa się call_rcu w jądrze Linuksa.

rcu_assign_pointer(): Updater używa tej funkcji do przypisania nowej wartości do wskaźnika chronionego przez RCU, aby bezpiecznie przekazać zmianę wartości z aktualizatora do czytnika. Ta funkcja zwraca nową wartość, a także wykonuje wszelkie bariery pamięci wymagane dla danej architektury procesora. Co być może ważniejsze, służy do dokumentowania, które wskaźniki są chronione przez RCU.
rcu_dereference(): Czytnik używa rcu_dereference do pobrania wskaźnika chronionego przez RCU, który zwraca wartość, którą można następnie bezpiecznie usunąć. Wykonuje również wszelkie dyrektywy wymagane przez kompilator lub procesor, na przykład volatile cast dla gcc, memory_order_consume load dla C/C++11 lub instrukcję bariery pamięci wymaganą przez stary procesor DEC Alpha. Wartość zwrócona przez rcu_dereference jest poprawna tylko w obrębie otaczającej sekcji krytycznej po stronie odczytu RCU. Podobnie jak w przypadku rcu_assign_pointer , ważną funkcją rcu_dereference jest dokumentowanie, które wskaźniki są chronione przez RCU.

Komunikacja API RCU między czytnikiem, aktualizatorem i reclaimerem

Diagram po prawej stronie pokazuje, w jaki sposób każdy interfejs API komunikuje się między czytnikiem, aktualizatorem i reclaimerem.

Infrastruktura RCU obserwuje sekwencję czasową wywołań rcu_read_lock , rcu_read_unlock , synchronize_rcu i call_rcu w celu określenia, kiedy (1) wywołania synchronize_rcu mogą powrócić do swoich wywołujących i (2) wywołania zwrotne call_rcu mogą zostać wywołane. Wydajne implementacje infrastruktury RCU intensywnie wykorzystują przetwarzanie wsadowe w celu amortyzacji kosztów ogólnych związanych z wieloma zastosowaniami odpowiednich interfejsów API.

Prosta implementacja

RCU ma niezwykle proste „zabawkowe” implementacje, które mogą pomóc w zrozumieniu RCU. Ta sekcja przedstawia jedną z takich „zabawkowych” implementacji, która działa w środowisku bez wywłaszczania .

   

   

      

    


 

        void  rcu_read_lock  (  void  )  {  }  void  rcu_read_unlock  (  void  )  {  }  void  call_rcu  (  void  (  *  wywołanie zwrotne  )  (  void  *  ),  void  *  arg  )  {  // dodaj parę callback/arg do listy  }  void  synchronize_rcu  (  void  )  {  int  procesor  ,  procesor  =  0

     
        

          
         
 ;  dla  każdego_procesora  (  procesora  )  harmonogram_bieżącego_zadania_do  (  procesora  );  dla  każdego  wpisu  na  liście  call_rcu  wpis  ->  wywołanie zwrotne  (  wpis  ->  arg  )  ;  }

W przykładowym kodzie rcu_assign_pointer i rcu_dereference można zignorować, nie tracąc wiele. Są one jednak potrzebne, aby powstrzymać szkodliwą optymalizację kompilatora i uniemożliwić procesorom zmianę kolejności dostępu.










 #define rcu_assign_pointer(p, v) ({ \  smp_wmb();  /* Kolejność poprzednich zapisów. */  \  ACCESS_ONCE(p) = (v); \  })  #define rcu_dereference(p) ({ \  typeof(p) _value = ACCESS_ONCE(p); \  smp_read_barrier_depends();  /* nop na większości architektur */  \  (_value); \  })

Zauważ, że rcu_read_lock i rcu_read_unlock nic nie robią. To jest wielka siła klasycznego RCU w jądrze bez wywłaszczania: narzut po stronie odczytu jest dokładnie zerowy, ponieważ smp_read_barrier_depends() jest pustym makrem na wszystkich procesorach oprócz DEC Alpha ; ^{[ nieudana weryfikacja ]} takie bariery pamięciowe nie są potrzebne w nowoczesnych procesorach. Makro ACCESS_ONCE () jest rzutowaniem nietrwałym, które w większości przypadków nie generuje dodatkowego kodu. I nie ma możliwości, aby rcu_read_lock mógł uczestniczyć w impasie cyklu, spowodować, że proces czasu rzeczywistego przekroczy termin harmonogramu, przyspieszyć odwrócenie priorytetów lub spowodować dużą rywalizację o blokadę . Jednak w tej zabawkowej implementacji RCU blokowanie w krytycznej sekcji RCU po stronie odczytu jest nielegalne, podobnie jak blokowanie z czystym spinlockiem.

Implementacja synchronize_rcu przenosi wywołującego synchronize_cpu do każdego procesora, blokując w ten sposób, dopóki wszystkie procesory nie będą w stanie wykonać przełączenia kontekstu. Przypomnijmy, że jest to środowisko bez wywłaszczania i że blokowanie w sekcji krytycznej po stronie odczytu RCU jest nielegalne, co oznacza, że w sekcji krytycznej po stronie odczytu RCU nie może być żadnych punktów wywłaszczania. Dlatego jeśli dany procesor wykonuje przełączenie kontekstu (w celu zaplanowania innego procesu), wiemy, że ten procesor musiał ukończyć wszystkie poprzednie sekcje krytyczne po stronie odczytu RCU. Gdy wszystkie procesory wykonają przełączenie kontekstu, wszystkie poprzednie krytyczne sekcje po stronie odczytu RCU zostaną zakończone.

Analogia z blokowaniem czytnika i pisarza

Chociaż RCU może być używany na wiele różnych sposobów, bardzo powszechne użycie RCU jest analogiczne do blokowania czytnika i zapisu. Poniższy obok siebie kod pokazuje, jak blisko powiązane może być blokowanie czytnika i zapisu oraz RCU.

                 

                                   
                            
                                     
                             
                                      /* blokowanie czytelnik-zapis */  /* RCU */  1  struct  el  {  1  struct  el  {  2  struct  list_head  lp  ;  2  struct  list_head  lp  ;  3  długi  klucz  ;  3  długi  klucz  ;  4  spinlock_t  muteks  ;  4  spinlock_t  muteks  ;  5  danych  int  ;  5  danych  int  ; 
                     
                                        
                          

               6  /* Inne pola danych */  6  /* Inne pola danych */  7  };  7  };                   8  DEFINE_RWLOCK  (  listmutex  );  8  DEFINE_SPINLOCK  (  listmutex  ); 
 9  LIST_HEAD  (  głowa  );  9  LIST_HEAD  (  głowa  );  1  int  search  (  długi  klucz  ,  int  *  wynik  )  1  int  search  (    
                                         
                                   
                                         
 długi  klucz  ,  int  *  wynik  )  2  {  2  {  3  struct  el  *  p  ;  3  struktura  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  ->  klucz  ==  klucz  )  {  7  if  (  p  ->  klucz  ==  klucz  )  {  8  *  wynik  =  p  ->  dane  ;  8  *  wynik  =  p  ->  dane  ;                                        
                                           
                                         
    0                               0
                                       

    9                         read_unlock  (  &  listmutex  );  9  rcu_read_unlock  (); 
 10  powrót  1  ;  10  powrót  1  ;  11  }  11  }  12  }  12  }                    13  read_unlock  (  &  listmutex  );  13  rcu_read_unlock  (); 
 14  powrót  ;  14  powrót  ;  15  }  15  }  1  wewn                         
                                         
                                   
                                         
     usuń  (  długi  klawisz  )  1  int  usuń  (  długi  klawisz  )  2  {  2  {  3  struct  el  *  p  ;  3  struktura  el  *  p  ;  4  4                       5  write_lock  (  &  listmutex  );  5  spin_lock  (  &  listmutex  ); 
 6  list_for_each_entry  (  str            
                                  
 ,  &  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  kwolne  (  p  );  11  kwolne  (  p  );  11  powrót  1  ;  12  powrót  1  ;  12  }  13  }  13                                          
    0                               0
                                        }  14  }                   14  write_unlock  (  &  listmutex  );  15  spin_unlock  (  &  listmutex  ); 
 15  powrót  ;  16  powrót  ;  16  }  17  }

Różnice między tymi dwoma podejściami są dość niewielkie. Blokowanie po stronie odczytu przenosi się do rcu_read_lock i rcu_read_unlock , blokowanie po stronie aktualizacji przechodzi z blokady czytnika-zapisu do prostej blokady spinlock, a synchronize_rcu poprzedza kfree .

Istnieje jednak jeden potencjalny haczyk: sekcje krytyczne po stronie odczytu i aktualizacji mogą teraz działać jednocześnie. W wielu przypadkach nie będzie to stanowiło problemu, ale niezależnie od tego konieczne jest dokładne sprawdzenie. Na przykład, jeśli wiele niezależnych aktualizacji list musi być postrzeganych jako pojedyncza aktualizacja niepodzielna, konwersja do RCU będzie wymagać szczególnej ostrożności.

Również obecność synchronize_rcu oznacza, że wersja RCU usuwania może teraz blokować. Jeśli stanowi to problem, można użyć call_rcu jak call_rcu (kfree, p) zamiast synchronize_rcu . Jest to szczególnie przydatne w połączeniu z liczeniem referencji.

Historia

Techniki i mechanizmy przypominające RCU były wielokrotnie niezależnie wymyślane:

HT Kung i Q. Lehman opisali użycie śmieciarek do implementacji dostępu podobnego do RCU do drzewa wyszukiwania binarnego.
Udi Manber i Richard Ladner rozszerzyli pracę Kunga i Lehmana na środowiska, w których nie są zbierane śmieci, odkładając przywracanie do czasu zakończenia wszystkich wątków uruchomionych w czasie usuwania, co działa w środowiskach, które nie mają długowiecznych wątków.
Richarda Rashida i in. opisał implementację leniwego bufora translacji (TLB), która odraczała odzyskiwanie wirtualnej przestrzeni adresowej, dopóki wszystkie procesory nie opróżniły swojego TLB, co jest podobne w duchu do niektórych implementacji RCU.
James P. Hennessy, Damian L. Osisek i Joseph W. Seigh, II otrzymali patent USA nr 4 809 168 w 1989 r. (Ponieważ wygasł). Ten patent opisuje mechanizm podobny do RCU, który najwyraźniej był używany w VM/XA na komputerach mainframe IBM .
William Pugh opisał mechanizm podobny do RCU, który polegał na wyraźnym ustawianiu flag przez czytelników.
Aju John zaproponował implementację podobną do RCU, w której aktualizatory po prostu czekają przez określony czas, przy założeniu, że wszyscy czytelnicy zakończą pracę w tym ustalonym czasie, co może być właściwe w twardym systemie czasu rzeczywistego. Van Jacobson zaproponował podobny schemat w 1993 roku (komunikacja werbalna).
J. Slingwine i PE McKenney otrzymali patent US 5 442 758 w sierpniu 1995 r., Który opisuje RCU zaimplementowane w DYNIX / ptx , a później w jądrze Linuksa.
B. Gamsa, O. Krieger, J. Appavoo i M. Stumm opisali mechanizm podobny do RCU, używany w badawczym systemie operacyjnym University of Toronto Tornado i blisko spokrewnionym badawczym systemie operacyjnym IBM Research K42 .
Rusty Russell i Phil Rumpf opisali podobne do RCU techniki obsługi rozładowywania modułów jądra Linuksa.
D. Sarma dodał RCU do wersji 2.5.43 jądra Linuksa w październiku 2002 roku.
Roberta Colvina i in. formalnie zweryfikowali leniwy współbieżny algorytm zestawu oparty na liście, który przypomina RCU.
M. Desnoyers i in. opublikował opis RCU przestrzeni użytkownika.
A. Gotsmana i in. wyprowadzona semantyka formalna dla RCU w oparciu o logikę separacji.
Ilan Frenkel, Roman Geller, Yoram Ramberg i Yoram Snir otrzymali patent USA 7 099 932 w 2006 r. Ten patent opisuje mechanizm podobny do RCU do pobierania i przechowywania informacji dotyczących zarządzania polityką jakości usług przy użyciu usługi katalogowej w sposób wymuszający odczyt / zapis spójność i umożliwia współbieżność odczytu/zapisu.

Zobacz też

Notatki

Bauer, RT, (czerwiec 2009), „Operacyjna weryfikacja programu relatywistycznego” PSU Tech Report TR-09-04 ( http://www.pdx.edu/sites/www.pdx.edu.computer-science/files/ tr0904.pdf )

Linki zewnętrzne

Paul E. McKenney, Mathieu Desnoyers i Lai Jiangshan: RCU w przestrzeni użytkownika . Cotygodniowe wiadomości o Linuksie .
Paul E. McKenney i Jonathan Walpole: Czym zasadniczo jest RCU? , Co to jest RCU? Część 2: Użycie i RCU część 3: API RCU . Cotygodniowe wiadomości o Linuksie .
Strona internetowa RCU Paula E. McKenneya
Hart, McKenney i Demke Brown (2006). Szybka synchronizacja bez blokady: implikacje wydajności odzyskiwania pamięci Najlepszy artykuł IPDPS 2006 porównujący wydajność RCU z innymi mechanizmami synchronizacji bez blokady. Wersja czasopisma (w tym Walpole jako autor).
Patent USA 5,442,758 (1995) „Urządzenie i sposób uzyskiwania wzajemnego wykluczania o zmniejszonym narzucie i utrzymywania spójności w systemie wieloprocesorowym z wykorzystaniem historii wykonania i monitorowania wątków”
Paul McKenney: Sleepable RCU . Cotygodniowe wiadomości o Linuksie .