Przetestuj i ustaw

W informatyce instrukcja test-and-set jest instrukcją używaną do zapisania (ustawienia) 1 w komórce pamięci i zwrócenia jej starej wartości jako pojedynczej niepodzielnej (tj. nieprzerywalnej ) operacji. Osoba dzwoniąca może następnie „przetestować” wynik, aby sprawdzić, czy stan został zmieniony przez wywołanie. Jeśli wiele procesów może uzyskiwać dostęp do tej samej lokalizacji pamięci i jeśli proces aktualnie wykonuje testowanie i ustawianie, żaden inny proces nie może rozpocząć kolejnego testowania i ustawiania, dopóki nie zakończy się testowanie i ustawianie pierwszego procesu. Jednostka centralna (CPU) może wykorzystywać instrukcję testowania i ustawiania oferowaną przez inny komponent elektroniczny, taki jak dwuportowa pamięć RAM ; sam procesor może również oferować instrukcję test-and-set.

Zamek można zbudować za pomocą atomowej instrukcji test-and-set w następujący sposób :

Ten kod zakłada, że ​​lokalizacja pamięci została zainicjowana na 0 w pewnym momencie przed pierwszym testem i ustawieniem. Proces wywołujący uzyskuje blokadę, jeśli stara wartość wynosiła 0, w przeciwnym razie pętla while obraca się, czekając na uzyskanie blokady. Nazywa się to spinlockiem . W dowolnym momencie posiadacz blokady może po prostu ustawić lokalizację pamięci z powrotem na 0, aby zwolnić blokadę do przejęcia przez inną osobę - nie wymaga to żadnej specjalnej obsługi, ponieważ posiadacz „jest właścicielem” tej lokalizacji pamięci. „ Testuj i testuj i ustawiaj ” to kolejny przykład.

Maurice Herlihy (1991) udowodnił, że testowanie i ustawianie (porównanie 1-bitowe) ma skończoną liczbę konsensusu i może rozwiązać problem konsensusu bez oczekiwania dla co najwyżej dwóch współbieżnych procesów. W przeciwieństwie do tego, porównanie i zamiana (porównanie 32-bitowe) oferuje bardziej ogólne rozwiązanie tego problemu, aw niektórych implementacjach porównanie-podwójne i zamiana (porównanie 64-bitowe) jest również dostępne dla rozszerzonej użyteczności.

Implementacja sprzętowa testu i zestawu

DPRAM mogą działać na wiele sposobów. Oto dwie odmiany, z których obie opisują DPRAM, który zapewnia dokładnie 2 porty, umożliwiając 2 oddzielnym komponentom elektronicznym (takim jak 2 procesory) dostęp do każdej lokalizacji pamięci w DPRAM.

Odmiana 1

Kiedy CPU 1 wydaje instrukcję test-and-set, DPRAM najpierw robi „wewnętrzną notatkę” o tym, przechowując adres lokalizacji pamięci w specjalnym miejscu. Jeśli w tym momencie CPU 2 wyda instrukcję test-and-set dla tej samej lokalizacji pamięci, DPRAM najpierw sprawdza swoją „notatkę wewnętrzną”, rozpoznaje sytuację i wysyła przerwanie BUSY, które mówi CPU 2, że musi poczekaj i spróbuj ponownie. Jest to implementacja zajętego oczekiwania lub spinlocka przy użyciu mechanizmu przerwań. Ponieważ wszystko to dzieje się przy prędkościach sprzętowych, czas oczekiwania procesora 2 na wyjście z blokady jest bardzo krótki.

Niezależnie od tego, czy CPU 2 próbował uzyskać dostęp do lokalizacji pamięci, DPRAM wykonuje test zadany przez CPU 1. Jeśli test się powiedzie, DPRAM ustawia lokalizację pamięci na wartość podaną przez CPU 1. Następnie DPRAM usuwa swoją „wewnętrzną uwaga”, że pisał tam CPU 1. W tym momencie CPU 2 może wykonać test-and-set, który zakończy się sukcesem.

Odmiana 2

CPU 1 wydaje instrukcję test-and-set, aby zapisać w „lokalizacji pamięci A”. DPRAM nie zapisuje natychmiast wartości w komórce pamięci A, ale zamiast tego jednocześnie przenosi bieżącą wartość do specjalnego rejestru, ustawiając zawartość komórki pamięci A na specjalną „wartość flagi”. Jeśli w tym momencie CPU 2 wykona polecenie test-and-set w komórce pamięci A, DPRAM wykryje specjalną wartość flagi i podobnie jak w Wariacji 1 wyśle ​​przerwanie BUSY.

Niezależnie od tego, czy CPU 2 próbował uzyskać dostęp do lokalizacji pamięci, DPRAM przeprowadza teraz test CPU 1. Jeśli test się powiedzie, DPRAM ustawia komórkę pamięci A na wartość określoną przez CPU 1. Jeśli test się nie powiedzie, pamięć DPRAM kopiuje wartość z powrotem z rejestru specjalnego do komórki pamięci A. Każda operacja kasuje specjalną wartość flagi. Jeśli CPU 2 wyda teraz test-and-set, zakończy się sukcesem.

Implementacja oprogramowania metodą test-and-set

Niektóre zestawy instrukcji mają atomową instrukcję języka maszynowego typu test-and-set. Przykłady obejmują x86 i IBM System/360 oraz ich następców (w tym z/Architecture ). Te, które tego nie robią, nadal mogą implementować atomowe testy i ustawiania za pomocą instrukcji odczytu, modyfikacji, zapisu lub porównania i zamiany .

Instrukcja test i set, gdy jest używana z wartościami boolowskimi, wykorzystuje logikę podobną do pokazanej w poniższej funkcji, z tą różnicą, że funkcja musi być wykonywana niepodzielnie . Oznacza to, że żaden inny proces nie może być w stanie przerwać funkcji w trakcie wykonywania, a tym samym zobaczyć stan, który istnieje tylko podczas wykonywania funkcji. To wymaga wsparcia sprzętowego; nie można go zaimplementować, jak pokazano. Niemniej jednak pokazany kod pomaga wyjaśnić zachowanie testu i zestawu. UWAGA: W tym przykładzie zakłada się, że „lock” jest przekazywany przez referencję (lub przez nazwę), ale przypisanie do „initial” tworzy nową wartość (a nie tylko kopiowanie referencji). 

 funkcja  TestAndSet(boolean_ref blokada) { wartość boolowska początkowa = blokada; blokada = prawda;   zwróć  inicjał; }

Pokazany kod nie tylko nie jest atomowy w sensie instrukcji test-and-set, ale także różni się od opisów sprzętu DPRAM test-and-set powyżej. W tym przypadku ustawiana wartość i test są stałe i niezmienne, a wartość jest aktualizowana niezależnie od wyniku testu, podczas gdy w przypadku testowania i ustawiania pamięci DPRAM pamięć jest ustawiana tylko wtedy, gdy test się powiedzie, a wartość do ustawienia, a warunki testowe są określane przez CPU. Tutaj wartość do ustawienia może wynosić tylko 1, ale jeśli 0 i 1 są uważane za jedyne prawidłowe wartości dla lokalizacji pamięci, a „wartość jest różna od zera” jest jedynym dozwolonym testem, to jest to równoznaczne z przypadkiem opisanym dla sprzętu DPRAM ( lub, dokładniej, przypadek DPRAM ogranicza się do tego przy tych ograniczeniach). Z tego punktu widzenia można to słusznie nazwać „testem i zestawem” w pełnym, konwencjonalnym znaczeniu tego terminu. Istotną kwestią, na którą należy zwrócić uwagę, jest ogólna intencja i zasada testowania i ustawiania: wartość jest zarówno testowana, jak i ustawiana w jednej niepodzielnej operacji, tak że żaden inny wątek ani proces programu nie może zmienić docelowej lokalizacji pamięci po przetestowaniu, ale przed jest ustawiony. (Dzieje się tak, ponieważ lokalizację należy ustawić tylko wtedy, gdy ma ona obecnie określoną wartość, a nie, jeśli miała tę wartość jakiś czas wcześniej).

W języku programowania C implementacja wyglądałaby następująco: 



   
     

    
    
    
    
    
      
      #define LOCKED 1  int  test_and_set  (  int  *  lockPtr  )  {  int  oldValue  ;  // -- Początek segmentu atomowego --  // To powinno być interpretowane jako pseudokod tylko w celach ilustracyjnych.  // Tradycyjna kompilacja tego kodu nie gwarantuje atomowości,  // użycia współdzielonej pamięci (tj. wartości niebuforowanych), ochrony przed  optymalizacją // kompilatora ani innych wymaganych właściwości.  staraWartość  =  *  lockPtr  ;  *  blokada Ptr  =  
    

     
 ZABLOKOWANE  ;  // -- Koniec segmentu atomowego --  return  oldValue  ;  }

Kod pokazuje również, że tak naprawdę istnieją dwie operacje: atomowy odczyt-modyfikacja-zapis i test. Tylko odczyt-modyfikacja-zapis musi być atomowy. (Jest to prawdą, ponieważ opóźnienie porównania wartości o dowolną ilość czasu nie zmieni wyniku testu po uzyskaniu wartości do przetestowania. Gdy kod zapisze wartość początkową, wynik testu został ustalony, nawet jeśli nie zostało jeszcze obliczone — np. przez operatora ==.)

Wzajemne wykluczanie za pomocą testu i zestawu

Jednym ze sposobów wdrożenia wzajemnego wykluczania jest użycie blokady opartej na testach i ustawieniach w następujący sposób:

Implementacja blokady wirowania w pseudo-C 

    0

  
    
    
    
    
    
     ulotna  blokada  int  =  ;  voidcritical  ()  { // Spin lock: pętla w nieskończoność   ,  dopóki nie uzyskamy blokady; wiemy, że blokada została   // pomyślnie uzyskana po wyjściu z tej pętli while, ponieważ  // funkcja test_and_set() blokuje blokadę i zwraca poprzednią  // wartość blokady. Jeśli poprzednia wartość blokady wynosiła 1, blokada była **już**   // zablokowana przez inny wątek lub proces. Jednak  gdy poprzednia wartość blokady   // wynosiła 0, oznacza to, że blokada **nie** była zablokowana przed my 
    
    
         
       
      0  
 // zamknął go, ale teraz **jest** zablokowany, ponieważ my go zablokowaliśmy, co oznacza, że  ​​// zamek jest naszą własnością.  while  (  test_and_set  (  &  lock  )  ==  1  );  sekcja  krytyczna  // tylko jeden proces może znajdować się w tej sekcji w danej  chwili  =  ;  // zwolnij blokadę po zakończeniu pracy z sekcją krytyczną  }

Zmienna blokady jest zmienną współdzieloną, tzn. jest dostępna dla wszystkich procesorów/wątków. Zwróć uwagę na volatile . W przypadku braku ulotności kompilator i/lub procesor (procesory) mogą zoptymalizować dostęp do blokady i/lub użyć wartości z pamięci podręcznej, czyniąc w ten sposób błędny powyższy kod. I odwrotnie, niestety obecność volatile nie gwarantuje, że odczyty i zapisy zostaną zapisane w pamięci. Niektóre kompilatory nakładają bariery pamięci , aby zapewnić, że operacje są zapisywane w pamięci, ale ponieważ semantyka volatile w C/C++ jest dość niejasny, nie wszystkie kompilatory to zrobią. Zapoznaj się z dokumentacją kompilatora, aby ustalić, czy tak jest.

Ta funkcja spin lock może być wywołana przez wiele procesów, ale gwarantuje się, że tylko jeden proces będzie w danej chwili w sekcji krytycznej . Pozostałe procesy będą się obracać, dopóki nie uzyskają blokady. Możliwe, że procesowi nigdy nie zostanie przyznana blokada. W takim przypadku będzie się zapętlać w nieskończoność. Jest to wada implementacji spin lock, ponieważ nie zapewnia uczciwości. Kwestie te są bardziej szczegółowo omówione w części dotyczącej wydajności .

Realizacja montażu 

        

          
                     
                     
                     

    

      
                     
                     

                  
                      wprowadź_region:  ; Znacznik „skok do”;  punkt wejścia funkcji.   tsl  reg  ,  flaga  ; Przetestuj i ustaw blokadę;  flaga jest   ; wspólna zmienna;  jest kopiowany   ; do rejestru reg i flagi   ; następnie atomowo ustawione na 1.   cmp  reg  ,  # 0 ; Czy flaga była zerowa w regionie wpisu?   jnz  wprowadź region  ; Przejdź do enter_region, jeśli   ; reg jest różny od zera;  tj   .; flaga była różna od zera przy wejściu.   powrót  ; Wyjście;  tj. flaga była zerowa   ; wejście.  Jeśli tu dotrzemy, tsl  
                     
                     
                     


    
                   ; ustawi to na wartość różną od zera;  w ten sposób   ; zajęliśmy zasób   ; związany z flagą.   opuść region:  przenieś  flagę  ,  #0; zapisz 0 we fladze   ret  ; wrócić do dzwoniącego

Tutaj tsl jest instrukcją atomową, a flaga jest zmienną blokującą. Proces nie powraca, chyba że uzyska blokadę.

Ocena działania zamków typu „testuj i ustawiaj”.

Cztery główne metryki oceny blokad to ogólnie opóźnienie w uzyskaniu blokady, ruch magistrali, uczciwość i przechowywanie.

Testuj i ustawiaj niskie wyniki w dwóch z nich, a mianowicie w dużym ruchu autobusowym i niesprawiedliwości.

Gdy procesor P1 uzyskał blokadę, a procesor P2 również czeka na blokadę, P2 będzie nadal realizował transakcje magistrali w próbach uzyskania blokady. Kiedy procesor uzyskał blokadę, wszystkie inne procesory, które również chcą uzyskać tę samą blokadę, kontynuują próby uzyskania blokady poprzez wielokrotne inicjowanie transakcji magistrali, aż do uzyskania blokady. Zwiększa to znacznie wymagania dotyczące ruchu autobusowego w zakresie testowania i ustawiania. Spowalnia to cały inny ruch z pamięci podręcznej i braków spójności . Spowalnia całą sekcję, ponieważ ruch jest nasycony nieudanymi próbami przejęcia blokady. Testuj i testuj i ustawiaj jest ulepszeniem w stosunku do TSL, ponieważ nie inicjuje ciągłych żądań przejęcia blokady.

Kiedy rozważamy uczciwość, zastanawiamy się, czy procesor ma uczciwą szansę na uzyskanie blokady, gdy zostanie uwolniony. W skrajnej sytuacji procesor może się zagłodzić, tzn. może nie być w stanie uzyskać blokady przez dłuższy czas, mimo że w tym czasie został zwolniony.

Narzut na przechowywanie dla TSL jest prawie zerowy, ponieważ wymagana jest tylko jedna blokada. Niezakłócone opóźnienie jest również niskie, ponieważ potrzebna jest tylko jedna atomowa instrukcja i gałąź.

Zobacz też

  1. ^   Anderson, TE (1990-01-01). „Wydajność alternatywnych blokad spinowych dla multiprocesorów współdzielonych pieniędzy”. Transakcje IEEE w systemach równoległych i rozproszonych . 1 (1): 6–16. doi : 10.1109/71.80120 . ISSN 1045-9219 .
  2. ^   Herlihy, Maurice (styczeń 1991). „Synchronizacja bez czekania” (PDF) . ACM Trans. Program. język. Syst . 13 (1): 124–149. CiteSeerX 10.1.1.56.5659 . doi : 10.1145/114005.102808 . Źródło 2007-05-20 .
  3. ^ „BTS — test i konfiguracja bitów” . www.felixcloutier.com . Źródło 2016-11-21 .
  4. ^ „Centrum wiedzy IBM” . www.ibm.com . Źródło 2016-11-21 .
  5. ^ Remzi H. Arpaci-Dusseau i Andrea C. Arpaci-Dusseau (2015). Systemy operacyjne: trzy łatwe elementy (wyd. 0,91). Książki Arpaci-Dusseau – przez http://www.ostep.org/ . {{ cite book }} : Zewnętrzny link w |via= ( pomoc )
  6. ^   Solihin, Yan (2009). Podstawy architektury komputerów równoległych: systemy wieloukładowe i wielordzeniowe . P. 252. ISBN 9780984163007 .
  7. ^   Solihin, Yan (2016). Podstawy architektury równoległej . Boca Raton, Floryda: CRC Press. ISBN 978-1-4822-1118-4 .

Linki zewnętrzne

Pobrano z „ https://en.wikipedia.org/w/index.php?title=Test-and-set&oldid=1134364566 ”