Programowanie współbieżne i wielowątkowe: procesy, synchronizacja oraz unikanie zakleszczeń

Współbieżność a zrównoleglenie

Współbieżność to właściwość systemu komputerowego, która umożliwia obsługę wielu zadań w tym samym przedziale czasowym, choć niekoniecznie w tej samej chwili fizycznej. Polega ona na szybkim przełączaniu się procesora między różnymi zadaniami (ang. context switching), co użytkownik odbiera jako jednoczesne działanie programów, nawet jeśli system posiada tylko jeden rdzeń. Celem współbieżności jest maksymalizacja wykorzystania procesora oraz zapewnienie responsywności systemu, aby np. długotrwała operacja zapisu na dysku nie blokowała interfejsu użytkownika. Główne zastosowania obejmują systemy operacyjne, serwery internetowe obsługujące tysiące zapytań klientów „jednocześnie” oraz aplikacje z interfejsem graficznym, które muszą reagować na kliknięcia myszką podczas wykonywania obliczeń w tle.

Zrównoleglenie to technika polegająca na fizycznym, jednoczesnym wykonywaniu wielu instrukcji lub zadań w dokładnie tym samym momencie czasu. W przeciwieństwie do współbieżności, która dotyczy struktury programu i radzenia sobie z wieloma zadaniami, zrównoleglenie wymaga wsparcia sprzętowego w postaci procesorów wielordzeniowych lub systemów wieloprocesorowych. Zadanie główne jest tu zazwyczaj dzielone na mniejsze, niezależne podzadania, które są przetwarzane równolegle przez różne rdzenie. Zastosowania obejmują przede wszystkim zadania wymagające ogromnej mocy obliczeniowej (CPU-bound), takie jak rendering grafiki 3D, symulacje naukowe, trenowanie sieci neuronowych czy przetwarzanie dużych zbiorów danych (Big Data), gdzie celem jest drastyczne skrócenie czasu potrzebnego na uzyskanie wyniku.

Hierarchia jednostek wykonawczych: proces, wątek i zadanie

Te trzy pojęcia tworzą hierarchię jednostek wykonawczych w systemie komputerowym:

• Proces: instancja uruchomionego programu, która posiada własną, w pełni izolowaną przestrzeń adresową pamięci oraz przydzielone zasoby systemowe (np. otwarte pliki); jest to jednostka „ciężka”, a komunikacja między procesami jest kosztowna.
• Wątek: lżejsza jednostka wykonawcza działająca w obrębie jednego procesu; wątki współdzielą tę samą pamięć (stertę) i zasoby procesu macierzystego, co pozwala na bardzo szybką komunikację, ale wymaga synchronizacji, aby uniknąć błędów.
• Zadanie (Task): pojęcie wyższego poziomu abstrakcji, oznaczające logiczną jednostkę pracy do wykonania (np. „pobierz plik”), która jest odseparowana od mechanizmu jej realizacji – zadanie może zostać przydzielone do wykonania przez jeden wątek, pulę wątków lub nawet proces, w zależności od decyzji planisty lub frameworka.

Przydział procesorów do zadań przez jądro systemu operacyjnego

Jądro systemu operacyjnego realizuje przydział procesorów do zadań za pomocą kluczowego modułu zwanego planistą (ang. scheduler), który zarządza kolejką wątków gotowych do wykonania. W nowoczesnych systemach najczęściej stosuje się model wielozadaniowości z wywłaszczaniem, gdzie planista przydziela procesor wątkowi na ściśle określony, krótki odcinek czasu zwany kwantem czasu. Po upływie tego czasu, lub w momencie gdy wątek zablokuje się (np. czekając na operację wejścia/wyjścia), następuje przerwanie sprzętowe i wymuszone przełączenie kontekstu, podczas którego stan obecnego wątku jest zapisywany, a procesor zostaje przekazany innemu zadaniu wybranemu przez algorytm planowania (np. uwzględniający priorytety).

Stan wyścigu (Race Condition)

Race condition, czyli stan wyścigu (lub wyścig), to błąd w systemie współbieżnym, który występuje, gdy dwa lub więcej wątków uzyskuje jednoczesny dostęp do współdzielonego zasobu (np. zmiennej w pamięci), przy czym przynajmniej jeden z nich próbuje ten zasób zmodyfikować bez odpowiedniej synchronizacji. Ponieważ system operacyjny może w dowolnym momencie przełączać procesor między wątkami, ostateczny wynik operacji staje się zależny od przypadkowej, niedeterministycznej kolejności wykonania instrukcji (przeplotu) przez poszczególne wątki. Prowadzi to do utraty spójności danych, na przykład w sytuacji read-modify-write, gdy jeden wątek nadpisuje zmiany dokonane ułamek sekundy wcześniej przez inny wątek, ponieważ oba operowały na nieaktualnej kopii danych.

Sekcja krytyczna i wzajemne wykluczanie

Sekcja krytyczna to wyodrębniony fragment kodu w programie współbieżnym, w którym następuje dostęp do zasobu współdzielonego (takiego jak zmienna globalna, bufor czy plik), i który ze względu na ryzyko wystąpienia stanu wyścigu wymaga szczególnej ochrony. Podstawową zasadą poprawności jest tutaj zagwarantowanie wzajemnego wykluczania (ang. mutual exclusion), co oznacza, że w dowolnym momencie instrukcje wewnątrz sekcji krytycznej mogą być wykonywane przez co najwyżej jeden wątek. Aby to zrealizować, programista musi otoczyć ten fragment kodu mechanizmami synchronizacji (takimi jak blokada typu mutex czy semafor), które wstrzymują inne wątki próbujące wejść do tej sekcji, dopóki bieżący wątek jej nie opuści.

Semafor binarny: działanie wersji sprawiedliwej i niesprawiedliwej

Semafor binarny to mechanizm synchronizacji przyjmujący wartości 0 lub 1, działający na zasadzie blokady (mutex):

• Wersja niesprawiedliwa: nie gwarantuje żadnej kolejności dostępu dla wątków oczekujących na zasób; w momencie zwolnienia semafora (operacja signal/up), wyścig o dostęp może wygrać dowolny wątek, nawet ten, który dopiero co nadszedł. Zwiększa to ogólną przepustowość systemu, ale stwarza ryzyko zagłodzenia wątków czekających dłużej.
• Wersja sprawiedliwa: wymusza ścisłą kolejność FIFO (First In, First Out), gdzie wątki ubiegające się o dostęp są ustawiane w kolejce i po zwolnieniu semafora budzony jest zawsze ten wątek, który czeka najdłużej. Eliminuje to problem zagłodzenia, jednak odbywa się kosztem niższej wydajności ze względu na narzut związany z zarządzaniem kolejką i częstszym przełączaniem kontekstu.

Mechanizmy implementacji sekcji krytycznych

Mechanizmy służące do implementacji sekcji krytycznych można podzielić na sprzętowe, systemowe oraz językowe:

• Poziom sprzętowy: wykorzystuje się atomowe instrukcje procesora, takie jak Test-and-Set (TAS) czy Compare-and-Swap (CAS), które stanowią fundament dla blokad typu spinlock oraz algorytmów nieblokujących.
• Poziom systemu operacyjnego: standardem są muteksy (blokady wzajemnego wykluczania) oraz semafory, które w przeciwieństwie do spinlocków usypiają oczekujące wątki, zwalniając procesor.
• Poziom języków wysokiego poziomu (Java, C#): stosuje się abstrakcję monitorów, realizowaną poprzez słowa kluczowe takie jak synchronized lub lock, które automatyzują proces zajmowania i zwalniania blokady powiązanej z obiektem.

Działanie bloku synchronized w języku Java oraz lock w C#

Blok synchronized (w Javie) lub jego odpowiednik lock (w C#) to realizacja koncepcji monitora, która zapewnia atomowość wykonywanego kodu poprzez mechanizm tzw. wewnętrznej blokady (ang. intrinsic lock) powiązanej z konkretnym obiektem. W momencie, gdy wątek napotyka początek bloku, próbuje pozyskać blokadę danego obiektu; jeśli jest ona zajęta przez inny wątek, wykonanie zostaje wstrzymane, a wątek trafia do systemowej kolejki oczekujących (stan BLOCKED) do momentu zwolnienia zasobu. Poza wzajemnym wykluczaniem mechanizm ten pełni również kluczową funkcję w modelu pamięci (Java Memory Model), wymuszając bariery pamięci, co gwarantuje, że wszystkie zmiany w zmiennych dokonane wewnątrz bloku będą natychmiast widoczne dla innych wątków po jego opuszczeniu.

Charakterystyka i zastosowanie monitorów

Monitor to wysokopoziomowy mechanizm synchronizacji procesów, który hermetyzuje dane oraz operacje na nich wewnątrz pojedynczego modułu lub obiektu, gwarantując automatyczne wzajemne wykluczanie (mutual exclusion) przy wywoływaniu jego metod. Służy do uproszczenia programowania współbieżnego poprzez zdjęcie z programisty obowiązku ręcznego zarządzania blokadami (lock/unlock); w danym momencie kod wewnątrz monitora może wykonywać tylko jeden wątek, co skutecznie chroni zasoby współdzielone przed wyścigami. Dodatkowo monitory wyposażone są w mechanizm zmiennych warunkowych (operacje wait/notify), który umożliwia wątkom bezpieczne zawieszanie swojego działania wewnątrz sekcji krytycznej w oczekiwaniu na spełnienie określonego warunku logicznego, bez zbędnego zużywania czasu procesora.

Właściwość re-entrancy: monitor a semafor

Właściwość bycia re-entrant (wielobieżnym) oznacza, że mechanizm synchronizacji potrafi zidentyfikować tożsamość wątku, który aktualnie posiada blokadę, i pozwala mu na ponowne, wielokrotne wejście do sekcji krytycznej chronionej tą samą blokadą bez ryzyka zakleszczenia. W przypadku monitora (np. w Javie), jeśli wątek będący już wewnątrz metody synchronized wywoła inną metodę synchronized tego samego obiektu, system jedynie zwiększy wewnętrzny licznik wejść, pozwalając na kontynuację pracy.

Zwykły semafor binarny nie posiada wiedzy o właścicielu („nie zna” tożsamości wątku). Jeśli wątek spróbuje wykonać operację opuszczenia (wait/P) na semaforze, który sam wcześniej zamknął, doprowadzi to do natychmiastowego samokleszczenia (ang. self-deadlock), ponieważ będzie czekał w nieskończoność na zwolnienie zasobu, który sam trzyma.

Problem czytelników i pisarzy oraz propozycja rozwiązania

Problem czytelników i pisarzy to klasyczne zagadnienie synchronizacji dostępu do bazy danych, w którym rywalizują dwie grupy wątków: czytelnicy, którzy tylko odczytują dane i mogą to robić równolegle, oraz pisarze, którzy modyfikują dane i wymagają wyłącznego dostępu do zasobu. Wyzwanie polega na zapewnieniu spójności danych przy jednoczesnej maksymalizacji wydajności (pozwoleniu wielu czytelnikom na pracę naraz) i uniknięciu zagłodzenia którejś z grup.

Przykładowe rozwiązanie (faworyzujące czytelników) wykorzystuje licznik aktywnych czytelników oraz dwie blokady: pierwszy wchodzący czytelnik blokuje dostęp dla pisarzy (zamyka „bramkę”), a każdy kolejny czytelnik swobodnie korzysta z zasobu; dopiero ostatni wychodzący czytelnik zwalnia blokadę, umożliwiając pisarzowi wejście. Wariant ten wymaga jednak dodatkowych mechanizmów, aby zapobiec sytuacji, w której ciągły napływ nowych czytelników sprawi, że pisarz nigdy nie otrzyma dostępu do danych.

Problem pięciu filozofów i unikanie zakleszczeń

Problem pięciu filozofów to klasyczny eksperyment myślowy ilustrujący zagrożenia zakleszczenia (ang. deadlock) i zagłodzenia w systemach współbieżnych. Przy okrągłym stole siedzi pięciu filozofów, a między nimi leży pięć widelców; aby zjeść posiłek, każdy filozof potrzebuje jednocześnie dwóch widelców leżących po jego bokach. Sytuacja patowa (zakleszczenie) następuje w momencie, gdy wszyscy filozofowie jednocześnie podniosą lewy widelec i będą w nieskończoność czekać na zwolnienie prawego widelca przez sąsiada.

Skutecznym rozwiązaniem jest wprowadzenie hierarchii zasobów, co polega na ponumerowaniu widelców od 1 do 5 i wymuszeniu zasady, że każdy filozof musi zawsze najpierw podnosić widelec o niższym numerze, a dopiero potem o wyższym. Dzięki temu ostatni filozof (siedzący między widelcem 5 i 1) spróbuje podnieść najpierw widelec 1 (zajęty już przez sąsiada), co przerywa cykl oczekiwania i umożliwia jednemu z filozofów skompletowanie pary i rozpoczęcie jedzenia.

Synchroniczne a asynchroniczne wywoływanie procedur

Synchroniczne wywoływanie procedur to standardowy model przepływu sterowania, w którym wątek wywołujący (caller) zostaje zablokowany w momencie wywołania funkcji i musi bezczynnie czekać aż do jej całkowitego zakończenia i zwrócenia wyniku. Sterowanie powraca do kodu wywołującego sekwencyjnie, co ułatwia analizę programu, ale może zamrażać aplikację przy czasochłonnych operacjach (np. I/O).

Z kolei asynchroniczne wywoływanie polega na zleceniu zadania do wykonania (np. w tle lub w innym wątku) i natychmiastowym powrocie sterowania do wątku wywołującego, który może kontynuować inne prace, nie czekając na wynik. Odbiór wyniku operacji asynchronicznej następuje w późniejszym czasie, co pozwala na budowanie responsywnych systemów zdolnych do równoległej obsługi wielu zdarzeń bez blokowania zasobów.

Metody implementacji asynchroniczności w języku Java

W języku Java, który posiada rozbudowane wsparcie dla współbieżności, wyróżnia się kilka głównych metod implementacji asynchroniczności:

• Pule wątków (ExecutorService): pozwalają zlecić zadanie typu Callable i otrzymać obiekt Future, służący do późniejszego odebrania wyniku lub sprawdzenia statusu obliczeń.
• Klasa CompletableFuture: nowocześniejsze i bardziej elastyczne podejście (wprowadzone w Javie 8), które umożliwia łańcuchowe łączenie zadań asynchronicznych i programowanie w stylu reaktywnym (non-blocking).
• Funkcje zwrotne (callbacks): rozwiązanie często spotykane w starszych bibliotekach lub systemach GUI (np. Swing), gdzie do metody asynchronicznej przekazuje się obiekt interfejsu (np. Listener), którego metoda zostanie wywołana automatycznie przez wątek roboczy po zakończeniu zadania.