Global Interpreter Lock – programowanie współbieżne #2

by Posted on

Rozpoczynając przygodę z programowaniem współbieżnym w Pythonie można natrafić na opinie, według których to nie najlepszy wybór, gdyż Python po prostu się do tego nie nadaje. Jak to w ogóle możliwe, że współczesny i bądź co bądź bardzo popularny język programowania może być w ogóle podejrzany o tego rodzaju dysfunkcje?! Czy jest to prawda i kto (lub co) jest winne takiemu obrotowi sprawy? Ława przysięgłych w komplecie, sędzia gotowy. Dzisiaj rozpatrzymy zarzut działania przeciw wolności wątków. Oskarżony: GIL.

GIL – historia

GIL – czyli Global Interpreter Lock – to nic innego jak… lock zabezpieczający globalny stan interpretera Pythona. Aby lepiej zrozumieć zasady jego działania oraz wynikające z tego konsekwencje cofnijmy się do roku 1992, w którym to Guido van Rosum, twórca Pythona dodał commita, zawierającego taki oto fragment kodu:

static type_lock
interpreter_lock;

W tym czasie Python był technologią bardzo świeżą i jeszcze nie całkowicie dojrzałą, zaś sam świat informatyczny wyglądał zupełnie inaczej. W branży IT kilka lat to pokolenie, więc liczba zmian jakie zaszły w ciągu ponad ćwierć wieku jest ogromna. W roku 1992, kiedy taktowanie procesorów było na poziomie 50 MHz, nikt nie myślał jeszcze o wielordzeniowych jednostkach w komputerach, laptopach czy tym bardziej telefonach. Niemniej jednak koncepcja programowania współbieżnego była już znana i możliwa do realizacji np. z wykorzystaniem zarządzanych przez system operacyjny wątków przetwarzania. Instrukcje były realizowane fizycznie na jednym mikroprocesorze, więc pojedynczy komputer był w stanie realizować operacje współbieżnie ale nie równolegle. Umożliwienie bezpiecznego korzystania z wielu wątków w Pythonie wymagało dostosowania samego interpretera i odpowiedniego zabezpieczenia go przed komplikacjami wynikającymi ze współbieżnego dostępu. Do zrozumienia przyczyny tych zagrożeń konieczne jest poznanie pojęcia wyścigu.

Wyzwania współbieżności – wyścigi

Wyścig (race condition) w kontekście programowania współbieżnego, to sytuacja, w której wykonanie programu jest zależne od tego w jakiej kolejności system operacyjny „przełączy” procesor do wykonania tego lub innego wątku (w ogólności problem ten nie dotyczy tylko wątków ale np. dla procesów jego geneza jest analogiczna, zaś wątki działające na wielu rdzeniach fizycznych również mogą wykonywać swoje operacje w różnym „tempie”). Jako programiści nie mamy kontroli nad tym zachowaniem, gdyż zależy ono od bardzo wielu czynników i z naszej perspektywy przełączanie pomiędzy wątkami jest praktycznie losowe. (dokładniej o tym czym są wątki i jak działają w Pythonie opowiem w oddzielnym wpisie z cyklu 😉 ) Oznacza to, że program, w którym występują wyścigi może dawać różne rezultaty w zależności od… no właśnie – losowo. Patrząc na to w kontekście np. sprzedaży internetowej, raz na jakiś czas mogłaby wydarzyć się sytuacja, kiedy kilka osób kupiłoby i zapłaciło za ten sam produkt, a ktoś nie otrzymałby swojego zamówienia. Załóżmy, że sklep ten sprzedaje bardzo drogie samochody. Jest to wersja kolekcjonerska modelu i zostało wyprodukowanych tylko 10 sztuk. 9 udało się już sprzedać, aktualnie dostępny jest jeszcze jeden samochód. Kod obsługujący ten kawałek systemu mógłby, w dużym uproszczeniu, wyglądać w ten sposób:

if number_of_cars > 0:
    number_of_cars -= 1
    confirm_transaction()

Co jednak wydarzyłoby się gdyby powyższy program wykonywany był na wielu wątkach? Otóż możliwy byłby scenariusz, w którym wątek A sprawdza warunek i jest on prawdziwy. Następnie sterowanie zostaje przekazane do wątku B, który również sprawdza warunek – prawdziwy. Potem sterowanie wraca do wątku A. Następuje zmniejszenie liczby dostępnych samochodów do 0 i potwierdzenie transakcji z kupującym A. Ułamek sekund później sterowanie wraca do wątku B, ten kontynuuje pracę od miejsca, w którym przerwał ją wcześniej, zmniejsza wartość zmiennej number_of_cars (uwaga mamy teraz na stanie -1 samochodów!) oraz potwierdza transakcję z drugim kupującym. Właśnie sprzedaliśmy coś, czego nie ma…

Przyczyną występowania wyścigów jest istnienie współdzielonego stanu, który poszczególne wątki na wzajem odczytują ale i modyfikują. W tym przypadku współdzielonym stanem była zmienna reprezentująca liczbę dostępnych w sprzedaży samochodów. Jedną z możliwości zabezpieczenia współdzielonych zasobów jest zastosowanie mechanizmu locka. W takim przypadku wątek, chcąc dostać się do zasobu współdzielonego, powinien najpierw pozyskać locka. Drugi wątek zablokuje się na żądaniu dostępu do locka, do czasu jego zwolnienia przez pierwszy. W ten sposób zasób współdzielony będzie bezpiecznie używany tylko przez jeden wątek i będzie miał on szansę pozostawić go w spójnym stanie, dostępnym do odczytu lub dalszych modyfikacji dla innych. Sam mechanizm locków jest bardziej skomplikowany niż omówiony tu przeze mnie przykład, jednak na potrzeby tego artykułu nie będziemy zagłębiać się w dalsze szczegóły.

Globalny stan interpretera i liczenie referencji

Tak więc GIL zabezpiecza globalny stan interpretera przed wyścigami i niespójnością. Co zatem znajduje się pod ochroną GILa? Są to: globalne zmienne (np. współdzielone pomiędzy wątkami pojedyncze instancje stringów) oraz informacje o liczbie referencji na dany obiekt. Liczenie referencji to jeden z mechanizmów stosowanych przez interpreter do zarządzania pamięcią. Polega on na zliczaniu każdej referencji (odwołania do obiektu), aby móc wykryć moment, w którym nikt nie posiada do niego odwołania i bezpiecznie zwolnić odpowiedni fragment pamięci. Poniższe wywołanie:

my_variable = ["hello"]

Spowoduje ustawienie licznika referencji dla obiektu listy na 1. Jeżeli poniżej dodamy:

other_variable = my_variable

To wartość referencji będzie wynosić 2. Bezpośrednio w kodzie programu możemy zweryfikować stan licznika za pomocą funkcji z modułu sys:

import sys

my_variable = ["hello"]
other_variable = my_variable
sys.getrefcount(my_variable)

>> 3

Skąd wzięła się trójka, skoro referencję na listę przechowują tylko dwie zmienne? Otóż tylko na czas wykonania funkcji pojawił się dodatkowy „zainteresowany” listą – sama funkcja. Dlatego zaraz po jej zakończeniu wartość spada do 2. Chcąc poznać liczbę referencji na obiekt, bez uwzględniania tych dołożonych przez sam proces sprawdzania, powinniśmy od wyniku getrefcount odjąć 1.
Wykonując komendy:

my_variable = "something"
other_variable = "other"

Usuniemy wszystkie istniejące odwołania do obiektu listy, tym samym skazując ją na zapomnienie i usunięcie z pamięci programu. Warto zaznaczyć tutaj, że liczenie referencji ma wiele zalet (jest proste w implementacji i pozwala natychmiast zwolnić zajmowaną pamięć) jednak wymaga dodatkowego narzutu na przechowywanie samej wartości, odpowiedniego obsłużenia dostępu współbieżnego oraz nie rozwiązuje tzw. cykli referencji. W celu poradzenia sobie z tym ostatnim problemem Python wykorzystuje garbage-collector, jednak szczegóły mechanizmu zarządzania pamięcią to materiał na oddzielny artykuł 😉

Wracając do tematu globalnego stanu interpretera zajrzymy nieco „pod maskę” czyli do kodu CPythona. Pierwszym interesującym fragmentem jest struktura będąca definicją Pythonowego obiektu:

typedef struct _object {
    _PyObject_HEAD_EXTRA
    Py_ssize_t ob_refcnt;
    struct _typeobject *ob_type;
} PyObject;

*ob_type to wskaźnik na strukturę zawierającą „właściwe” informacje na temat danego obiektu. Z perspektywy poruszanego tematu, ważniejsze jest jednak pole ob_refcnt. To właśnie licznik referencji. Szukając odwołań do ob_refcnt znajdziemy makra odpowiedzialne za inkrementację i dekrementację wartości licznika:

#define Py_INCREF(op) (                         \
    _Py_INC_REFTOTAL  _Py_REF_DEBUG_COMMA       \
    ((PyObject *)(op))->ob_refcnt++)
#define Py_DECREF(op)                                   \
    do {                                                \
        PyObject *_py_decref_tmp = (PyObject *)(op);    \
        if (_Py_DEC_REFTOTAL  _Py_REF_DEBUG_COMMA       \
        --(_py_decref_tmp)->ob_refcnt != 0)             \
            _Py_CHECK_REFCNT(_py_decref_tmp)            \
        else                                            \
            _Py_Dealloc(_py_decref_tmp);                \
    } while (0)

Wracając do przykładu z my_variable oraz other_variable, przeanalizujmy co mogłoby się stać, gdyby dwa wątki w tym samym czasie przetwarzały te zmienne, początkowo wskazujące na listę [„hello”]. Załóżmy, że po początkowym przypisaniu do tych zmiennych listy, w bardzo zbliżonym momencie czasu, wykonany został następujący kod – w wątku A:

my_variable = "something"

W wątku B:

other_variable = "other"

Należy przy tym pamiętać, że wątki współdzieląc pomiędzy sobą zmienne w programie, współdzielą również związany z obiektami kontekst, w tym licznik referencji. Tak więc, w bardzo zbliżonym czasie zarówno wątek A jak i B próbują zmniejszyć wartość licznika referencji obiektu listy, wykonując opisane wyżej makro. Na pierwszy rzut oka wszystko wydaje się być bezpieczne – w końcu najpierw zmniejszana jest wartość licznika:

--(_py_decref_tmp)->ob_refcnt

a dopiero potem następuje sprawdzenie czy jest on różny od zera. Biorąc jednak pod uwagę fakt, że operacja – – nie jest atomowa i przekłada się ona na:

  • wczytanie wartości zmiennej do rejestru procesora
  • zmniejszenie wartości o 1
  • zapisanie do pamięci wyniku z rejestru procesora

Łatwo możemy dostrzec niebezpieczeństwo potencjalnego wyścigu. Wystarczy, że po wykonaniu kroku pierwszego przez wątek A, a przed wykonaniem trzeciego, wątek B zdąży wczytać zmienną do rejestru. Wątek A zmniejszy wartość o 1 i zapisze wynik (1) w pamięci. Po chwili ten sam wynik (2 – 1 = 1) zapisze wątek B. Doszło więc do sytuacji, w której nie istnieje referencja na listę, a jednak licznik wynosi 1.

GIL na ratunek

Na szczęście do powyższej, oraz innych potencjalnie jeszcze gorszych sytuacji nie dojdzie. Jesteśmy bezpieczni dlatego, że jakakolwiek interakcja z interpreterem Pythona wymaga posiadania GILa, który w danym momencie czasu może należeć tylko do jednego wątku. Taka zasada ma kilka bardzo wyraźnych zalet:

  • Zdecydowanie rozwiązuje problem z dostępem do zasobów współdzielonych
  • Jest prosta w implementacji
  • Nie pociąga za sobą ryzyka wystąpienia deadlocków, które pojawia się podczas stosowania wielu „małych” locków rozsianych po całym programie

Dodatkowo ograniczenie do jednego wątku dotyczy tylko dostępu do interpretera Pythona. Nie jest on konieczny np. do zapisania/odczytania pliku albo odebrania jakiś danych z sieci. Moduły realizujące te funkcjonalności zwalniają GILa w odpowiednim momencie, pozwalając na wykonanie w międzyczasie pracy przez inny wątek. W związku z tym, GIL nie przeszkodzi w zwiększeniu efektywności działania programu którego większość zadań związanych jest z operacjami i/o (i/o bounded). Gorzej natomiast wygląda sytuacja z programami cpu bounded, których głównym zadaniem jest wykonywanie różnego rodzaju obliczeń. Niektóre biblioteki (np. numpy) rozwiązują ten problem zwalniając GILa i wykonując skomplikowane obliczenia bez ingerencji w obiekty Pythonowe. Niestety, pomijając specyficzne przypadki dotyczące odpowiednio przygotowanych modułów, programista Pythona nie będzie mógł za pomocą wątków zaangażować do pracy większej liczby rdzeni swojego procesora.

Zarzuty

Podsumowując dotychczas zebrane informacje, można wnioskować, że istnienie GILa nie ogranicza możliwości wykorzystania wątków w programach i/o bounded, a dla programów cpu bounded ogranicza ich działanie, powodując efekt wykonania zbliżony do programu jednowątkowego. Aktualnie jest to prawda (z małą gwiazdką, o czym za chwilę). Warto tu jednak wspomnieć, że nie zawsze tak było. W roku 2009 Antoine Pitrou opracował patcha nazwanego „new gil”. Patch ten poprawiał zachowanie interpretera w kontekście sprawiedliwego „udostępniania” locka różnym wątkom, zwłaszcza podczas działania na wielordzeniowym procesorze. Początkowo zakładano, że GIL powinien zmieniać właściciela co 100 kroków (krok to jedna lub kilka instrukcji na poziomie bytecode’u). Empiryczny eksperyment Davida Beazley wykazał jednak, że wygląda to zupełnie inaczej. Efektem jest zauważalnie wolniejsze (!) wykonanie tego samego kodu na wielu wątkach, w porównaniu do uruchomienia jednowątkowego, oraz potencjalnie zagłodzenie wątku i/o bounded przez intensywnie wykorzystujący procesor wątek cpu bounded. Przyczyną problemu był następujący fragment kodu:

PyThread_release_lock(interpreter_lock);

/* Other threads may run now */

PyThread_acquire_lock(interpreter_lock, 1);

Jeżeli oczekujący na GILa wątek nie zdążył „złapać locka” w krótkiej chwili po jego zwolnieniu powracał on do pierwotnego właściciela. Dla procesorów jednordzeniowych efekt ten był mniej zauważalny, gdyż wynikał z niefortunnego momentu przydzielenia procesora do jednego lub drugiego wątku (w chwili gdy GIL został zwolniony oczekujący na niego wątek nie dostał od systemu operacyjnego cykli procesora). W maszynach wielordzeniowych sytuacja sprowadzała się do trwającej non stop batalii o GILa toczonej przez wątki przetwarzane w tym samym czasie na niezależnych corach procesora.

Patch Antoine Pitrou wprowadził możliwość zażądania dostępu do locka, tak by aktualny właściciel, po zwolnieniu locka dał szansę innym, zanim ponownie go zablokuje. Jednak również ta implementacja posiada pewien mankament. W kolejnych eksperymentach David Beazley wykazał istnienie tzw. convoy effect. Polega on na długim oczekiwaniu na dostęp do interpretera przez wątek o niskich wymaganiach (i/o bounded). Efekt widoczny jest podczas wykonania na kilku rdzeniach wielowątkowego programu, zawierającego zarówno część obliczeniową jak i i/o. Za każdym razem, gdy wątek odczytujący dane otrzyma jakąś ich niewielką porcje i chciałby na krótki moment uzyskać dostęp do interpretera, po ustawieniu flagi żądania musi odczekać wymagany timeout (czas „na przekazanie” GILa). Co ciekawe opisany problem został zgłoszony na trackerze w 2010 roku, jednak ze względu na złożoność potencjalnego rozwiązania oraz niewielkie zainteresowanie społeczności pozostaje on nierozwiązany do dnia dzisiejszego (na moment powstawania artykułu 😉 )

Wyrok?

A gdyby tak znaleźć inne rozwiązanie i pozbyć się GILa? Sam Guido nie miałby nic przeciwko, o ile nie ucierpiałaby na tym wydajność aplikacji jednowątkowych oraz wielowątkowych typu i/o bounded:

„I’d welcome it if someone did another experiment along the lines of Greg’s patch (which I haven’t found online), and I’d welcome a set of patches into Py3k only if the performance for a single-threaded program (and for a multi-threaded but I/O-bound program) does not decrease.” Guido van Rossum, fragment postu It isn’t Easy to Remove the GIL, 2007

Wymaganie to postawiło poprzeczkę dla potencjalnego rozwiązania bardzo wysoko. Patch Grega, o którym mowa w cytacie, znany jest również pod nazwą „free-threading patch” i został opracowany jeszcze dla wersji 1.5! Koncepcja polegała na opakowaniu zmiennych globalnych interpretera w strukturę aby w miarę łatwo można było ją zabezpieczyć przed wyścigami (ten kawałek został wciągnięty do głównej dystrybucji) oraz otoczeniu operacji zwiększania i zmniejszania licznika referencji lockami. Z powodu bardzo częstego zakładania i zdejmowania locków (licznik referencji aktualizowany jest praktycznie bez przerwy) narzut na te operacje spowodował bardzo zauważalny spadek wydajności programu. W zależności od eksperymentu i wykorzystanego systemu operacyjnego proponowane rozwiązanie było od 2 do nawet 7 razy wolniejsze. Inna próba usunięcia GILa bazowała na wykorzystaniu atomowych operacji inkrementacji i dekrementacji (na poziomie procesora) do obsługi liczników referencji. Działania takie są wspierane przez współczesne procesory jednak również odbijają się negatywnie na wydajności programu. Zastosowanie ich w Pythonie zmniejszyło wydajność aplikacji jednowątkowej o około 30%.

Skoro liczenie referencji jest tak problematyczne, może rozwiązaniem byłaby zmiana podejścia do zarządzania pamięcią i oparcie się tylko na garbage-collectorze? Niestety, na tej drodze również piętrzą się trudności. Dość specyficzną właściwością CPythona jest fakt udostępniania C API. Elementem kontraktu w tym API jest sposób zarządzania pamięcią i fakt liczenia referencji. Zmiana wymagałaby szerokiej adaptacji we wszystkich zależnych modułach i rozszerzeniach. Nie jest to również jedyny problem. Dzięki istnieniu GILa implementujący rozszerzenia nie muszą zabezpieczać ewentualnego globalnego stanu przed wielowątkowym dostęp. Tak szerokie zmiany w C API byłyby bardzo poważnym wyzwaniem i blokerem dla przejścia na wolną od GILa wersję interpretera. Czy więc możliwe jest pozbycie się GILa przy jednoczesnym utrzymaniu oczekiwanej wydajności i kompatybilności wstecznej? Tego wyzwania podjął się Larry Hastings rozpoczynając w 2016 roku projekt Gilectomy. Jako cel wyznaczył sobie umożliwienie wykorzystania wielu rdzeni fizycznych do wykonywania programów wielowątkowych przy jednoczesnym zachowaniu wysokiej kompatybilności z aktualnym C API oraz wydajności. Jego podejście opierało się o zastosowanie atomowych operacji inkrementacji i dekrementacji oraz locków tam gdzie będzie to konieczne. Podczas trwania eksperymentu udało mu się zaimplementować bez-GILową wersję interpretera, która działała trochę wolniej od rozwiązania wyjściowego (przy czym była wolniejsza również dla większej liczby rdzeni). Projekt nie został ukończony, jednak wnioski z jego przebiegu, przedstawiane przez Larry’ego na wielu konferencjach, są bardzo pouczające.

Co ciekawe, w dokumentacji Pythona jest specjalna sekcja poświęcona informacjom o wyzwaniach związanych z usunięciem GILa.

Podsumowanie

W mojej opinii, pomimo istnienia GILa Python dobrze nadaje się do wykorzystania w bardzo szerokim spektrum zastosowań z zakresu programowania współbieżnego. Globalny lock narzuca pewne ograniczenia, jednak wiele z nich przestaje być problemem, po zastosowaniu odpowiednich do typu problemu narzędzi. Umożliwiając rozwiązanie trudnego zagadnienia w czytelny i prosty sposób, GIL z pewnością przyczynił się do rozwoju całego języka i stał się jego ważnym elementem. Czy gdzieś w przyszłości czeka na nas Python bez GILa? Być może. Najświeższym pomysłem w tej kwestii jest koncepcja subinterpreterów, której zdecydowanie należy się oddzielny artykuł. Hej! 🙂

PS: Temat omawiamy w tym artykule jest specyficzny dla CPythona i do tej właśnie wersji interpretera odnosi się post 😉
PS2: Przykłady kodu CPythona pochodzą z interpretera w wersji 3.7.4 (oprócz tych odnoszących się do historycznych wersji Pythona)

Published by Mikołaj