Co to jest semafor?

Semafor to koncepcja programowania, która jest często używana do rozwiązywania problemów związanych z wielowątkowością. Moje pytanie do społeczności:

Co to jest semafor i jak go używasz?

Pomyśl o semaforach jako bramkarzach w nocnym klubie. Istnieje specjalna liczba osób, które mogą przebywać w klubie jednocześnie. Jeśli klub jest pełny, nikt nie może wejść, ale jak tylko jedna osoba opuści inną osobę, może wejść.

Jest to po prostu sposób na ograniczenie liczby konsumentów dla określonego zasobu. Na przykład, aby ograniczyć liczbę jednoczesnych wywołań do bazy danych w aplikacji.

Oto bardzo pedagogiczny przykład w C # :-)

using System;
using System.Collections.Generic;
using System.Text;
using System.Threading;

namespace TheNightclub
{
    public class Program
    {
        public static Semaphore Bouncer { get; set; }

        public static void Main(string[] args)
        {
            // Create the semaphore with 3 slots, where 3 are available.
            Bouncer = new Semaphore(3, 3);

            // Open the nightclub.
            OpenNightclub();
        }

        public static void OpenNightclub()
        {
            for (int i = 1; i <= 50; i++)
            {
                // Let each guest enter on an own thread.
                Thread thread = new Thread(new ParameterizedThreadStart(Guest));
                thread.Start(i);
            }
        }

        public static void Guest(object args)
        {
            // Wait to enter the nightclub (a semaphore to be released).
            Console.WriteLine("Guest {0} is waiting to entering nightclub.", args);
            Bouncer.WaitOne();          

            // Do some dancing.
            Console.WriteLine("Guest {0} is doing some dancing.", args);
            Thread.Sleep(500);

            // Let one guest out (release one semaphore).
            Console.WriteLine("Guest {0} is leaving the nightclub.", args);
            Bouncer.Release(1);
        }
    }
}

Artykuł Mutexes and Semaphores Demystified by Michael Barr jest doskonałym krótkim wprowadzeniem do tego, co odróżnia muteksy i semafory od tego, kiedy i kiedy powinny i nie powinny być używane. Fragment kilku kluczowych akapitów tutaj.

Kluczową kwestią jest to, że do ochrony wspólnych zasobów należy używać muteksów, a do sygnalizowania należy używać semaforów. Zasadniczo nie należy używać semaforów do ochrony wspólnych zasobów ani muteksów do sygnalizowania. Istnieją na przykład problemy z analogią bouncera pod względem używania semaforów do ochrony współdzielonych zasobów - możesz z nich korzystać w ten sposób, ale może to utrudniać zdiagnozowanie błędów.

Chociaż muteksy i semafory mają pewne podobieństwa w ich implementacji, zawsze należy ich używać inaczej.

Najczęstszą (ale jednak niepoprawną) odpowiedzią na pytanie postawione na górze jest to, że muteksy i semafory są bardzo podobne, z tą jedyną znaczącą różnicą, że semafory mogą liczyć się więcej niż jeden. Prawie wszyscy inżynierowie wydają się właściwie rozumieć, że muteks jest flagą binarną używaną do ochrony współdzielonego zasobu poprzez zapewnienie wzajemnego wykluczenia w krytycznych sekcjach kodu. Ale gdy poproszono ich o rozwinięcie sposobu korzystania z „liczącego semafora”, większość inżynierów - różniących się jedynie stopniem pewności - wyraża pewien gust podręcznika, że ​​są one wykorzystywane do ochrony kilku równoważnych zasobów.

...

W tym miejscu powstaje interesująca analogia, wykorzystująca ideę kluczy do łazienki jako ochrony wspólnych zasobów - łazienki. Jeśli sklep ma jedną łazienkę, wystarczy jeden klucz, aby chronić ten zasób i uniemożliwić korzystanie z niego wielu osobom jednocześnie.

Jeśli jest wiele łazienek, można pokusić się o ich równe wprowadzenie i zrobienie wielu kluczy - jest to podobne do niewłaściwego użycia semafora. Kiedy już zdobędziesz klucz, nie wiesz, która łazienka jest dostępna, a jeśli pójdziesz tą ścieżką, prawdopodobnie skończysz z użyciem muteksów, aby dostarczyć te informacje i upewnić się, że nie weźmiesz łazienki, która jest już zajęta. .

Semafor jest niewłaściwym narzędziem do ochrony kilku zasadniczo takich samych zasobów, ale tyle osób o nim myśli i używa go. Analogia bramkarza jest wyraźnie inna - nie ma kilku zasobów tego samego typu, zamiast tego istnieje jeden zasób, który może przyjąć wielu użytkowników jednocześnie. Przypuszczam, że w takich sytuacjach można zastosować semafor, ale rzadko zdarzają się sytuacje w świecie rzeczywistym, w których analogia faktycznie się utrzymuje - częściej występuje kilka tego samego typu, ale wciąż pojedyncze zasoby, takie jak łazienki, których nie można użyć tą drogą.

...

Prawidłowe użycie semafora służy do sygnalizowania jednego zadania do drugiego. Muteks ma być pobierany i zwalniany, zawsze w tej kolejności, przez każde zadanie korzystające z chronionego zasobu udostępnionego. Natomiast zadania wykorzystujące semafory albo sygnalizują, albo czekają, a nie oba jednocześnie. Na przykład Zadanie 1 może zawierać kod do wysłania (tj. Sygnału lub przyrostu) określonego semafora po naciśnięciu przycisku „zasilania”, a Zadanie 2, które wybudza wyświetlacz, czeka na tym samym semaforze. W tym scenariuszu jednym z zadań jest producent sygnału zdarzenia; drugi konsument.

...

Tutaj ważna jest uwaga, że ​​muteksy źle wpływają na systemy operacyjne w czasie rzeczywistym, powodując odwrócenie priorytetu w przypadku, gdy mniej ważne zadanie może zostać wykonane przed ważniejszym zadaniem z powodu współdzielenia zasobów. Krótko mówiąc, dzieje się tak, gdy zadanie o niższym priorytecie wykorzystuje muteks do pobrania zasobu A, a następnie próbuje złapać B, ale zostaje wstrzymany, ponieważ B jest niedostępny. W trakcie oczekiwania pojawia się zadanie o wyższym priorytecie, które potrzebuje A, ale jest już powiązane i przez proces, który nawet nie działa, ponieważ czeka na B. Istnieje wiele sposobów rozwiązania tego problemu, ale najczęściej jest to naprawione zmieniając mutex i menedżera zadań. Muteks jest w tych przypadkach znacznie bardziej złożony niż semafor binarny,

...

Przyczyna powszechnego współczesnego pomieszania muteksów i semaforów ma charakter historyczny, ponieważ sięga aż do wynalezienia w 1974 roku semafora (wielka litera „S” w tym artykule) autorstwa Djikstry. Przed tą datą żaden z bezpiecznych dla przerwania mechanizmów synchronizacji i sygnalizacji znanych komputerowcom nie był efektywnie skalowalny do wykorzystania przez więcej niż dwa zadania. Rewolucyjny, bezpieczny i skalowalny semafor Dijkstry został zastosowany zarówno do ochrony sekcji krytycznej, jak i sygnalizacji. I tak zaczęło się zamieszanie.

Później stało się jednak oczywiste dla twórców systemów operacyjnych, po pojawieniu się opartego na priorytetach prewencyjnego systemu RTOS (np. VRTX, ok. 1980 r.), Publikacji artykułów naukowych ustanawiających RMA i problemów spowodowanych odwróceniem priorytetu oraz publikacji na temat priorytetu protokoły dziedziczenia w 1990 r.3 okazało się, że muteksy muszą być czymś więcej niż tylko semaforami z licznikiem binarnym.

Mutex: udostępnianie zasobów

Semafor: sygnalizacja

Nie używaj jednego do drugiego bez dokładnego rozważenia skutków ubocznych.

Mutex: wyłączny dostęp członka do zasobu

Semafor: dostęp n-członka do zasobu

Oznacza to, że mutex może być używany do synchronizacji dostępu do licznika, pliku, bazy danych itp.

Sempahore może robić to samo, ale obsługuje stałą liczbę jednoczesnych rozmówców. Na przykład mogę zawinąć wywołania bazy danych w semafor (3), aby moja aplikacja wielowątkowa trafiła do bazy danych z maksymalnie 3 jednoczesnymi połączeniami. Wszystkie próby zostaną zablokowane, dopóki nie otworzy się jedno z trzech miejsc. Sprawiają, że wykonywanie naiwnego dławienia jest naprawdę bardzo łatwe.

Rozważ taksówkę, która może pomieścić łącznie 3 (z tyłu ) +2 (z przodu ) osób, w tym kierowcę. A zatem, semaphorepozwala tylko 5 osobom w samochodzie na raz. I mutexpozwala tylko 1 osobie na jednym siedzeniu samochodu.

Dlatego Mutexma umożliwić wyłączny dostęp do zasobu ( takiego jak wątek systemu operacyjnego ), podczas gdy a Semaphorema umożliwić dostęp dla n liczby zasobów jednocześnie.

@Craig:

Semafor to sposób na zablokowanie zasobu, aby zagwarantować, że podczas wykonywania fragmentu kodu tylko ten fragment ma dostęp do tego zasobu. Dzięki temu dwa wątki nie będą jednocześnie uzyskiwać dostępu do zasobu, co może powodować problemy.

Nie jest to ograniczone tylko do jednego wątku. Semafor można skonfigurować tak, aby zezwalał na dostęp do zasobu określonej liczbie wątków.

Semafor może być również użyty jako ... semafor. Na przykład, jeśli masz wiele procesów kolejkujących dane do kolejki i tylko jedno zadanie zużywa dane z kolejki. Jeśli nie chcesz, aby Twoje zadanie konsumenckie stale odpytywało kolejkę w poszukiwaniu dostępnych danych, możesz użyć semafora.

W tym przypadku semafor nie jest wykorzystywany jako mechanizm wykluczający, ale jako mechanizm sygnalizacyjny. Zadanie konsumujące czeka na semaforze Zadanie produkcyjne publikuje w semaforze.

W ten sposób zadanie konsumujące jest uruchamiane tylko wtedy, gdy istnieją dane do usunięcia z kolejki

Istnieją dwie podstawowe koncepcje budowy współbieżnych programów - synchronizacja i wzajemne wykluczanie. Zobaczymy, jak te dwa rodzaje zamków (semafory są bardziej rodzajem mechanizmu blokującego) pomagają nam osiągnąć synchronizację i wzajemne wykluczenie.

Semafor jest konstrukcją programistyczną, która pomaga nam osiągnąć współbieżność, realizując zarówno synchronizację, jak i wzajemne wykluczanie. Semafory są dwojakiego rodzaju, binarne i zliczające.

Semafor składa się z dwóch części: licznika i listy zadań oczekujących na dostęp do określonego zasobu. Semafor wykonuje dwie operacje: poczekaj (P) [to jak uzyskanie blokady] i zwolnij (V) [podobnie do zwolnienia blokady] - są to jedyne dwie operacje, które można wykonać na semaforze. W semaforze binarnym licznik logicznie przechodzi między 0 a 1. Można go uznać za podobny do zamka z dwiema wartościami: otwarta / zamknięta. Semafor zliczający ma wiele wartości dla zliczania.

Ważne jest, aby zrozumieć, że licznik semaforów śledzi liczbę zadań, które nie muszą być blokowane, tzn. Mogą robić postępy. Zadania blokują się i dodają się do listy semaforów tylko wtedy, gdy licznik wynosi zero. Dlatego zadanie jest dodawane do listy w procedurze P (), jeśli nie może się rozwijać, i „uwalniane” za pomocą procedury V ().

Teraz dość oczywiste jest, jak semafory binarne można wykorzystać do rozwiązania synchronizacji i wzajemnego wykluczenia - są to zasadniczo blokady.

dawny. Synchronizacja:

thread A{
semaphore &s; //locks/semaphores are passed by reference! think about why this is so.
A(semaphore &s): s(s){} //constructor
foo(){
...
s.P();
;// some block of code B2
...
}

//thread B{
semaphore &s;
B(semaphore &s): s(s){} //constructor
foo(){
...
...
// some block of code B1
s.V();
..
}

main(){
semaphore s(0); // we start the semaphore at 0 (closed)
A a(s);
B b(s);
}

W powyższym przykładzie B2 może wykonać się dopiero po zakończeniu wykonywania B1. Powiedzmy, że wątek A przychodzi jako pierwszy - przechodzi do sem.P () i czeka, ponieważ licznik ma wartość 0 (zamknięty). Nadchodzi wątek B, kończy B1, a następnie uwalnia wątek A - który następnie kończy B2. Osiągamy synchronizację.

Spójrzmy teraz na wzajemne wykluczanie za pomocą binarnego semafora:

thread mutual_ex{
semaphore &s;
mutual_ex(semaphore &s): s(s){} //constructor
foo(){
...
s.P();
//critical section
s.V();
...
...
s.P();
//critical section
s.V();
...

}

main(){
semaphore s(1);
mutual_ex m1(s);
mutual_ex m2(s);
}

Wzajemne wykluczenie jest również dość proste - m1 i m2 nie mogą jednocześnie wejść do sekcji krytycznej. Tak więc każdy wątek używa tego samego semafora, aby zapewnić wzajemne wykluczenie dla swoich dwóch krytycznych sekcji. Czy można mieć większą współbieżność? Zależy od najważniejszych sekcji. (Pomyśl, jak inaczej można użyć semaforów, aby osiągnąć wzajemne wykluczenie. Wskazówka: czy koniecznie muszę używać tylko jednego semafora?)

Liczenie semaforów: semafor z więcej niż jedną wartością. Spójrzmy na to, co to oznacza - zamek z więcej niż jedną wartością? Tak otwarte, zamknięte i ... hmm. Jaki jest pożytek z blokady wielostopniowej we wzajemnym wykluczaniu lub synchronizacji?

Weźmy łatwiejszy z dwóch:

Synchronizacja z wykorzystaniem semafora zliczającego: Załóżmy, że masz 3 zadania - nr 1 i 2, które chcesz wykonać po 3. Jak zaprojektowałbyś swoją synchronizację?

thread t1{
...
s.P();
//block of code B1

thread t2{
...
s.P();
//block of code B2

thread t3{
...
//block of code B3
s.V();
s.V();
}

Więc jeśli semafor zaczyna się zamknięty, upewniasz się, że t1 i t2 blokują, dodawane są do listy semaforów. Potem pojawia się wszystkie ważne t3, kończy swój biznes i uwalnia t1 i t2. W jakiej kolejności są uwalniane? Zależy od implementacji listy semaforów. Może to być FIFO, może mieć określony priorytet itp. (Uwaga: pomyśl o tym, jak ułożysz P i V; s, jeśli chcesz, aby t1 i t2 były wykonywane w określonej kolejności i jeśli nie byłeś świadomy implementacji semafora)

(Dowiedz się: co się stanie, jeśli liczba V jest większa niż liczba P?)

Wzajemne wykluczanie Korzystanie z liczenia semaforów: Chciałbym, abyś skonstruował w tym celu swój własny pseudokod (sprawia, że ​​rozumiesz lepiej!) - ale podstawowa koncepcja jest taka: semafor liczenia licznika = N pozwala N zadań swobodnie wchodzić do sekcji krytycznej . Oznacza to, że masz N zadań (lub wątków, jeśli chcesz), wchodzisz do sekcji krytycznej, ale zadanie N + 1 zostaje zablokowane (przechodzi na naszą ulubioną listę zablokowanych zadań) i jest przepuszczane tylko wtedy, gdy ktoś V jest semaforem przynajmniej raz. Licznik semaforów zamiast wahać się między 0 a 1, teraz przechodzi między 0 i N, umożliwiając N zadaniom swobodne wchodzenie i wychodzenie, nie blokując nikogo!

O rany, dlaczego miałbyś potrzebować tak głupiej rzeczy? Czy nie chodzi o to, by wzajemne wykluczenie nie pozwalało więcej niż jednemu facetowi na dostęp do zasobów? (Wskazówka Wskazówka ... Nie zawsze masz tylko jeden dysk w komputerze, prawda ...?)

Do przemyślenia : Czy wzajemne wykluczenie osiąga się, mając sam liczący semafor? Co się stanie, jeśli masz 10 instancji zasobu, a 10 wątków wchodzi (przez semafor zliczający) i próbujesz użyć pierwszej instancji?

Semafor to obiekt zawierający liczbę naturalną (tj. Liczbę całkowitą większą lub równą zero), na której zdefiniowane są dwie operacje modyfikujące. Jedna operacja Vdodaje 1 do naturalnego. Druga operacja Pzmniejsza liczbę naturalną o 1. Obie czynności są atomowe (tzn. Żadna inna operacja nie może być wykonana w tym samym czasie co a Vlub a P).

Ponieważ liczby naturalnej 0 nie można zmniejszyć, wywołanie Psemafora zawierającego 0 zablokuje wykonanie procesu wywołującego (/ wątku) do momentu, w którym liczba nie będzie już równa 0 i Pbędzie mogła zostać pomyślnie (i atomowo) wykonana.

Jak wspomniano w innych odpowiedziach, semaforów można użyć do ograniczenia dostępu do określonego zasobu do maksymalnej (ale zmiennej) liczby procesów.

Stworzyłem wizualizację, która powinna pomóc w zrozumieniu pomysłu. Semafor kontroluje dostęp do wspólnego zasobu w środowisku wielowątkowym.

ExecutorService executor = Executors.newFixedThreadPool(7);

Semaphore semaphore = new Semaphore(4);

Runnable longRunningTask = () -> {
    boolean permit = false;
    try {
        permit = semaphore.tryAcquire(1, TimeUnit.SECONDS);
        if (permit) {
            System.out.println("Semaphore acquired");
            Thread.sleep(5);
        } else {
            System.out.println("Could not acquire semaphore");
        }
    } catch (InterruptedException e) {
        throw new IllegalStateException(e);
    } finally {
        if (permit) {
            semaphore.release();
        }
    }
};

// execute tasks
for (int j = 0; j < 10; j++) {
    executor.submit(longRunningTask);
}
executor.shutdown();

Wynik

Semaphore acquired
Semaphore acquired
Semaphore acquired
Semaphore acquired
Could not acquire semaphore
Could not acquire semaphore
Could not acquire semaphore

Przykładowy kod z artykułu

Flaga sprzętu lub oprogramowania. W systemach wielozadaniowych semafor jest tak zmienny, że ma wartość wskazującą status wspólnego zasobu. Proces wymagający zasobu sprawdza semafor, aby określić status zasobów, a następnie decyduje, jak postępować.

Semafory działają jak ograniczniki wątków.

Przykład: Jeśli masz pulę 100 wątków i chcesz wykonać operację DB. Jeśli 100 wątków uzyskuje dostęp do DB w danym momencie, może wystąpić problem z blokowaniem w DB, więc możemy użyć semafora, który dopuszcza tylko ograniczony wątek naraz. Poniżej Przykład dopuszcza tylko jeden wątek na raz. Gdy wątek acquire()wywoła metodę, uzyska dostęp, a po wywołaniu release()metody zwolni dostęp, aby następny wątek uzyskał dostęp.

    package practice;
    import java.util.concurrent.Semaphore;

    public class SemaphoreExample {
        public static void main(String[] args) {
            Semaphore s = new Semaphore(1);
            semaphoreTask s1 = new semaphoreTask(s);
            semaphoreTask s2 = new semaphoreTask(s);
            semaphoreTask s3 = new semaphoreTask(s);
            semaphoreTask s4 = new semaphoreTask(s);
            semaphoreTask s5 = new semaphoreTask(s);
            s1.start();
            s2.start();
            s3.start();
            s4.start();
            s5.start();
        }
    }

    class semaphoreTask extends Thread {
        Semaphore s;
        public semaphoreTask(Semaphore s) {
            this.s = s;
        }
        @Override
        public void run() {
            try {
                s.acquire();
                Thread.sleep(1000);
                System.out.println(Thread.currentThread().getName()+" Going to perform some operation");
                s.release();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        } 
    }

Wyobraź sobie, że wszyscy próbują iść do łazienki, a do łazienki jest tylko pewna liczba kluczy. Teraz, jeśli nie ma wystarczającej liczby kluczy, ta osoba musi poczekać. Pomyśl więc o semaforze, który reprezentuje zestaw kluczy dostępnych dla łazienek (zasobów systemowych), do których różne procesy (osoby korzystające z łazienki) mogą poprosić o dostęp.

Teraz wyobraź sobie dwa procesy próbujące iść do łazienki w tym samym czasie. To nie jest dobra sytuacja, a semafory są używane, aby temu zapobiec. Niestety semafor jest mechanizmem dobrowolnym i procesy (nasi użytkownicy w łazience) mogą go zignorować (tzn. Nawet jeśli są klucze, ktoś może po prostu otworzyć drzwi).

Istnieją również różnice między semaforami binarnymi / muteksowymi i liczącymi.

Sprawdź notatki z wykładów na stronie http://www.cs.columbia.edu/~jae/4118/lect/L05-ipc.html .

To stare pytanie, ale jednym z najciekawszych zastosowań semaforów jest blokada odczytu / zapisu i nie została wyraźnie wymieniona.

Blokady r / w działają w prosty sposób: zużywają jedno pozwolenie dla czytelnika i wszystkie pozwolenia dla pisarzy. Rzeczywiście, trywialna implementacja blokady ar / w, ale wymaga modyfikacji metadanych podczas odczytu (właściwie dwa razy), która może stać się wąskim gardłem, wciąż znacznie lepszym niż mutex lub blokada.

Inną wadą jest to, że pisarze mogą być również uruchamiani dość łatwo, chyba że semafor jest sprawiedliwy lub zapisy uzyskują zezwolenia na wiele żądań, w takim przypadku potrzebują jawnego muteksu między sobą.

Czytaj dalej :

Semafor to sposób na zablokowanie zasobu, aby zagwarantować, że podczas wykonywania fragmentu kodu tylko ten fragment ma dostęp do tego zasobu. Dzięki temu dwa wątki nie będą jednocześnie uzyskiwać dostępu do zasobu, co może powodować problemy.