Wyścig o dostęp

6 Października 2016

Zaczął się nowy rok akademicki i dostałem zastrzyk informacji. Za nim podążył strzał ze strzelby zadaniami domowymi. Takie życie studenta. W każdym razie, wspomiany w tytule wyścig o dostęp to problem, który opiewa przedmiot Programowanie Współbieżne. O co tu chodzi?

Odrobinka historii

Na początku komputery były proste i wykonywały wszystkie zadania liniowo. Czyli przychodził człowiek z kartą perforowaną, wkładał, komputer to przerabiał i coś wypluwał. Potem przeszliśmy z kart na cyfrowe nośniki pamięci, ale idea była taka sama. Uruchamiając program, był on ładowany do pamięci i wykonywany liniowo do końca, a potem kolejny program był uruchamiany. Ale ze wzrostem szybkości komputerów, powstał pomysł stworzenia pozornej wielozadaniowości kopmputera. Procesory nie były jeszcze w stanie wykonywać dwóch operacji na raz, ale można było przełączać się między procesami, raz ten, raz tamten, tak aby użytkownikowi się wydawało, że kilka rzeczy wykonuje się na raz.

No i super, wszystko śmiga, użytkownik też zadowolony, więc w czym problem? Otóż gdyby każdy program pracował na swoim kawałku pamięci i nie dotykał innych to nie byłoby problemu. Ale zdarza się, że do jakiegoś zasobu dostęp chcą uzyskać dwa programy na raz i go zmodyfikować. Pytanie jest proste: co się wydarzy?

Spójrzmy na prosty przykład:

static int y = 0; //zmienna globalna

void run()
{
    for(int i = 0; i < 10; i++)
    {
        int x = y;
        x++;
        y = x;
    }
}

Mamy teraz dwa wątki wykonujące metodę run() uruchomione jednocześnie. Jeśli zostanie najpierw wykonany kod z pierwszego wątka, a potem z drugiego to y wyniesie 20, jeśli mamy wielordzeniowy procesor i oba wątki wykonają się jednocześnie (dla każdej instrukcji), to y wyniesie 10. A co jeśli po przypisaniu int x wątek zostanie zatrzymany, a drugi nie? Wtedy wynik będzie inny. Patrząc na możliwie przypadki brzegowe dojdziemy do wniosku, że y >= 2 && y <= 20. Tak czy siak, program jest niedeterministyczny, a to jest nie fajnie, bo jeśli kod raz działa, a raz nie to jest to zły kod.

Dlatego zostały stworzone różne mechanizmy kontroli. Monitor jest to system dający dostęp tylko jednemu wątkowi na raz. W C# uproszczoną składnią na używanie Monitora jest lock. Ustalamy jakiś obiekt i na nim blokujemy dostęp. Jeśli dostęp jest już zablokowany to czekamy, aż zostanie odblokowany.

Poprawiony kod jest już deterministyczny i zawsze daje wynik y = 20.

static int y = 0; //zmienna globalna

void run()
{
    for(int i = 0; i < 10; i++)
    {
        lock(y)
        {
            int x = y;
            x++;
            y = x;
        }
    }
}

Innym systemem kontroli, bardziej nisko poziomowym jest Semafor, który oparty jest o licznik. Jeśli obiekt chce wejść do sekcji krytycznej (tej, w której wielodostęp psuje) wykonuje procedurę wejścia. Jeśli licznik jest dodatni to zostaje zmniejszony o 1 i obiekt dostaje dostęp, a jeśli licznik wynosi 0, to blokuje obiekt dopóki inny nie zwiększy licznika wykonując procedurę wyjścia.

Ciekawe porównanie Semaforów i Monitorów na Stack Overflow.

Mam nadzieję, że nieco przybliżyłem Ci, czytelniku, problem współbieżności.