Testuj i ustawiaj - Test-and-set

W informatyce instrukcja test-and-set jest instrukcją używaną do zapisania (set) 1 w komórce pamięci i zwrócenia jej starej wartości jako pojedynczej operacji atomowej (tj. nieprzerywalnej). Dzwoniący może następnie „przetestować” wynik, aby sprawdzić, czy stan został zmieniony przez wywołanie. Jeśli wiele procesów może uzyskać dostęp do tej samej lokalizacji w pamięci, a proces aktualnie wykonuje test i zestaw, żaden inny proces nie może rozpocząć kolejnego testu i zestawu do czasu zakończenia testu i zestawu pierwszego procesu. CPU może używać test-i-Set dyspozycję oferowanego przez innego komponentu elektronicznego, takiego jak podwójnego portu 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: 

function Lock(boolean *lock) { 
    while (test_and_set(lock) == 1); 
}

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 kręci się w oczekiwaniu na uzyskanie blokady. Nazywa się to spinlockiem . W dowolnym momencie posiadacz zamka może po prostu ustawić komórkę pamięci z powrotem na 0, aby zwolnić blokadę do przejęcia przez inną - nie wymaga to żadnej specjalnej obsługi, ponieważ posiadacz "posiada" tę komórkę pamięci. Innym przykładem jest " Testuj i testuj i ustawiaj ".

Maurice Herlihy (1991) dowiódł, że funkcja test-and-set (1-bitowa wartość porównawcza) 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ównywanie podwójne i zamienienie (porównywanie 64-bitowe) jest również dostępne dla rozszerzonej użyteczności.

Sprzętowa implementacja test-and-set

Instrukcje test-and-set 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.

Wariant 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ą „wewnętrzną notatkę”, rozpoznaje sytuację i wydaje przerwanie BUSY, które mówi CPU 2, że musi poczekaj i spróbuj ponownie. Jest to implementacja zajętego oczekiwania lub spinlock przy użyciu mechanizmu przerwań. Ponieważ wszystko to dzieje się przy prędkościach sprzętowych, procesor 2 czeka na wyjście z blokady wirowania bardzo krótko.

Niezależnie od tego, czy CPU 2 próbował uzyskać dostęp do lokalizacji pamięci, DPRAM wykonuje test podany przez CPU 1. Jeśli test się powiedzie, DPRAM ustawia lokalizację pamięci na wartość podaną przez CPU 1. Następnie DPRAM wymazuje swoje „wewnętrzne uwaga”, że CPU 1 tam pisał. W tym momencie CPU 2 może wydać test-and-set, co się powiedzie.

Wariant 2

CPU 1 wydaje instrukcję test-and-set, aby zapisać w „lokalizacji pamięci A”. DPRAM nie przechowuje natychmiast wartości w komórce pamięci A, ale zamiast tego jednocześnie przenosi bieżącą wartość do specjalnego rejestru, jednocześnie ustawiając zawartość komórki pamięci A na specjalną „wartość flagową”. Jeśli w tym momencie CPU 2 wysyła test-and-set do lokalizacji pamięci A, DPRAM wykrywa specjalną wartość flagi i, jak w Wariancie 1, wysyła przerwanie BUSY.

Niezależnie od tego, czy CPU 2 próbował uzyskać dostęp do lokalizacji pamięci, DPRAM wykonuje teraz test CPU 1. Jeśli test się powiedzie, DPRAM ustawia w pamięci A wartość określoną przez CPU 1. Jeśli test się nie powiedzie, DPRAM kopiuje wartość z powrotem z rejestru specjalnego do lokalizacji w pamięci A. Każda operacja wymazuje wartość flagi specjalnej. Jeśli teraz CPU 2 wyda test-and-set, to się powiedzie.

Implementacja oprogramowania test-and-set

Niektóre zestawy instrukcji mają atomową instrukcję w języku maszynowym typu test-and-set. Przykładami są x86 i IBM System/360 oraz jego następcy (w tym z/Architecture ). Te, które tego nie robią, mogą nadal zaimplementować atomowe testowanie i ustawianie za pomocą instrukcji odczytu, modyfikacji, zapisu lub porównania i zamiany .

Instrukcja test and set, gdy jest używana z wartościami boolowskimi, wykorzystuje logikę podobną do przedstawionej w poniższej funkcji, z wyjątkiem tego, że funkcja musi być wykonywana niepodzielnie . Oznacza to, że żaden inny proces nie może być w stanie przerwać funkcji w trakcie wykonywania, w ten sposób widząc stan, który istnieje tylko podczas wykonywania funkcji. To wymaga wsparcia sprzętowego; nie można go zaimplementować, jak pokazano. Niemniej jednak przedstawiony kod pomaga wyjaśnić zachowanie funkcji test-and-set. UWAGA: W tym przykładzie zakłada się, że 'lock' jest przekazywana przez odwołanie (lub przez nazwę), ale przypisanie do 'initial' tworzy nową wartość (nie tylko kopiuje referencję). 

function TestAndSet(boolean_ref lock) {
    boolean initial = lock;
    lock = true;
    return initial;
}

Pokazany kod nie tylko nie jest atomowy, w sensie instrukcji test-and-set, ale także różni się od powyższych opisów sprzętu DPRAM test-and-set. Tutaj ustawiana wartość i test są stałe i niezmienne, a wartość jest aktualizowana niezależnie od wyniku testu, podczas gdy dla testu DPRAM test-and-set pamięć jest ustawiana tylko wtedy, gdy test się powiedzie, a wartość do ustawienia, a warunki testu są określane przez procesor. 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 niezerowa” jest jedynym dozwolonym testem, to jest to równoznaczne z przypadkiem opisanym dla sprzętu DPRAM ( lub, bardziej szczegółowo, przypadek DPRAM sprowadza 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. Istotnym punktem do odnotowania jest ogólna intencja i zasada test-and-set: wartość jest zarówno testowana, jak i ustawiana w jednej atomowej operacji, tak że żaden inny wątek programu lub proces nie może zmienić docelowej lokalizacji pamięci po jej przetestowaniu, ale przed nim jest ustawiony. (Dzieje się tak, ponieważ lokalizację należy ustawić tylko wtedy, gdy ma 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;

    // -- Start of atomic segment --
    // This should be interpreted as pseudocode for illustrative purposes only.
    // Traditional compilation of this code will not guarantee atomicity, the
    // use of shared memory (i.e., non-cached values), protection from compiler
    // optimizations, or other required properties.
    oldValue = *lockPtr;
    *lockPtr = LOCKED;
    // -- End of atomic segment --

    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 prawda, ponieważ opóźnienie porównania wartości o dowolny czas nie zmieni wyniku testu po uzyskaniu wartości do testowania. Gdy kod zapisze wartość początkową, wynik testu został ustalony, nawet jeśli nie została jeszcze obliczona — np. przez operator ==.)

Wzajemne wykluczanie za pomocą testu i zestawu

Jednym ze sposobów na zaimplementowanie wzajemnego wykluczania jest użycie blokady opartej na testowaniu i ustawianiu w następujący sposób:

Implementacja pseudo-C

volatile int lock = 0;

void critical() {
    while (test_and_set(&lock) == 1);
    critical section  // only one process can be in this section at a time
    lock = 0;  // release lock when finished with the critical section
}

Zmienna blokady jest zmienną współdzieloną, tzn. dostęp do niej mają wszystkie procesory/wątki. Zwróć uwagę na słowo kluczowe volatile . W przypadku braku niestabilności, kompilator i/lub procesor(y) mogą zoptymalizować dostęp do blokowania i/lub używania wartości z pamięci podręcznej, czyniąc powyższy kod błędnym. I odwrotnie, i niestety, obecność lotnych ma nie gwarantuje, że czyta i pisze się na pamięć. Niektóre kompilatory nakładają bariery pamięci, aby zapewnić, że operacje są umieszczane w pamięci, ale ponieważ semantyka niestabilności w C/C++ jest dość niejasna, nie wszystkie kompilatory to zrobią. Sprawdź w dokumentacji kompilatora, czy tak jest.

Ta funkcja może być wywoływana przez wiele procesów, ale gwarantuje się, że tylko jeden proces będzie znajdować się w sekcji krytycznej w danej chwili. Reszta procesów będzie się kręcić, dopóki nie dostaną blokady. Możliwe, że proces nigdy nie otrzyma blokady. W takim przypadku zapętli się w nieskończoność. Jest to wada tej implementacji, ponieważ nie zapewnia uczciwości. Zagadnienia te są szerzej omówione w części dotyczącej wydajności .

Realizacja montażu

enter_region:        ; A "jump to" tag; function entry point.

  tsl reg, flag      ; Test and Set Lock; flag is the
                     ; shared variable; it is copied
                     ; into the register reg and flag
                     ; then atomically set to 1.

  cmp reg, #0        ; Was flag zero on entry_region?

  jnz enter_region   ; Jump to enter_region if
                     ; reg is non-zero; i.e.,
                     ; flag was non-zero on entry.

  ret                ; Exit; i.e., flag was zero on
                     ; entry. If we get here, tsl
                     ; will have set it non-zero; thus,
                     ; we have claimed the resource
                     ; associated with flag.

leave_region:
  move flag, #0      ; store 0 in flag
  ret                ; return to caller

Oto tslinstrukcja atomowa i flagzmienna blokady. Proces nie powraca, chyba że uzyska blokadę.

Ocena działania zamków typu test-and-set

Ogólnie rzecz biorąc, cztery główne metryki oceny blokad to niekwestionowane opóźnienie pozyskiwania blokad, ruch magistrali, uczciwość i pamięć masowa.

Dwa z nich uzyskały niskie wyniki testu i zestawu, a mianowicie duży ruch autobusów i nieuczciwość.

Gdy procesor P1 uzyskał blokadę, a procesor P2 również czeka na blokadę, P2 będzie nadal dokonywał transakcji magistrali w próbach uzyskania blokady. Gdy procesor uzyskał blokadę, wszystkie inne procesory, które również chcą uzyskać tę samą blokadę, próbują uzyskać blokadę przez wielokrotne inicjowanie transakcji szyny, aż zdobędą blokadę. Zwiększa to znacznie wymagania dotyczące ruchu autobusów w zakresie testowania i ustawiania. Spowalnia to cały inny ruch związany z brakiem pamięci podręcznej i spójności . Spowalnia całą sekcję, ponieważ ruch jest nasycony przez nieudane próby pozyskania blokady. Test-and-test-and-set to ulepszenie w stosunku do TSL, ponieważ nie inicjuje on żądań pozyskania blokady w sposób ciągły.

Rozważając uczciwość, rozważamy, czy procesor ma uczciwą szansę na uzyskanie blokady, gdy jest ona zwolniona. W ekstremalnej sytuacji procesor może głodować, tj. może nie być w stanie uzyskać blokady przez dłuższy czas, mimo że w tym czasie stał się wolny.

Narzut pamięci masowej dla TSL to prawie nic, ponieważ wymagana jest tylko jedna blokada. Niezakłócone opóźnienie jest również niskie, ponieważ potrzebna jest tylko jedna instrukcja atomowa i gałąź.

Zobacz też

Bibliografia

  1. ^ Anderson, TE (1990-01-01). „Wydajność alternatywnych blokad spinu dla multiprocesorów na wspólne pieniądze”. 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 oczekiwania” (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 bitów i zestaw” . www.felixcloutier.com . Pobrano 21.11.2016 .
  4. ^ „Centrum wiedzy IBM” . www.ibm.com . Pobrano 21.11.2016 .
  5. ^ Remzi H. Arpaci-Dusseau i Andrea C. Arpaci-Dusseau (2015). Systemy operacyjne: Trzy łatwe kawałki (0,91 ed.). Książki Arpaciego-Dusseau – za pośrednictwem http://www.ostep.org/ .
  6. ^ Solihin Jan (2009). Podstawy architektury komputerów równoległych : systemy wielochipowe i wielordzeniowe . P. 252. Numer ISBN 9780984163007.
  7. ^ Solihin Jan (2016). Podstawy architektury równoległej . Boca Raton, FL: CRC Press. Numer ISBN 978-1-4822-1118-4.

Zewnętrzne linki