Grzegorz Marczynski

Watki w Linuxie i nie tylko

O czym bedzie?

1. Co to jest watek?
   • Watek to sekwencyjny przeplyw sterowania. W wielowatkowym programie moze dzialac na raz wiele (zero lub wiecej) watkow z tym, ze na prawde wspolbierznie pracuje nie wiecej niz liczba procesorow w systemie.
   • Przelacznie kontekstu pomiedzy watkami jest tansze niz miedzy procesami.
   • Wszystkie dane poza stosem i rejestrami sa dzielone miedzy watkami.
   • Terminologia:
     • Async safety:
       Ta czesc kodu, ktora moze byc wywolywana z poziomu obslugi sygnalow jest async-safe. Watek wykonujacy kod async-safe, przerwany przez obsluge sygnalu, nie zablokuje sie (deadlock).
     • Asynchroniczne i blokujace wywolania systemowe:
       Wiekszosc normalnych wywolan systemowych pod Unixem blokuje (usypia) watek je wykonujacy az do zakonczenia wykonania i wznawia tuz po. Moga istniec (i istnieja) asynchroniczne (nie blokujace) wywolania tych procedur, ktore zwracaja sterowanie do watku zaraz po wywolaniu i w jakis inny sposob informuja go pozniej o zakonczeniu akcji systemowych.
     • Lekki proces (lightweight process):
       Lekki proces (czasem blednie nazywany watkiem na poziomie jadra) jest jednostka wykonania, ktorej istnienia jadro sytemu jest "swiadome". Sklada sie z kontekstu wykonania i pewnych dodatkowych informacji (jednak z duzo mniejszej ilosci niz pelny proces). Czasem, w wieloprocesowych systemach, lekkie procesy sa przypisywane pewnym procesorom i tylko na nich moga dzialac.
     • Bezpieczenstwo MT (MT safety):
       Jesli jakis kod jest MT safe, to znaczy, ze mozy byc wykonywany przez program wielowatkowy (nie uzywa danych globalnych lub/i statycznych) i, ze zapewnia jakis przyzwoity poziom wspolbierznosci.
     • Granica ochrony:
       Granica ochrony chroni jeden podsystem programowy przed drugim. Zapewnia, ze jedynie jawnie wymienione elementy obu systemow moga byc dzielone. Przykladem moze byc releacja miedzy procesami i jadrem w Unixie, ktore pozwala zmieniac procesom swoj stan jedynie w okreslony sposob i w dosc ograniczonym zakresie. Przejscie sterowania przez granice ochrony jest bardzo "drogie"
2. Watki standardu POSIX (na podst. IEEE POSIX 1003.1c-1995 lub ISO/IEC 9945-1:1996)
3. Watki na poziomie uzytkownika (user-level)
   Watki uzytkownika istnieja, bez wspolpracy z jadrem systemu, w przestrzeni uzytkowanika i nie sa rozroznialne (jako poszczegolne przbiegi) nigdzie indziej.
   Zalety:
   • Ze wzgledu na czas przelaczania kontekstu sa najszybsze ze wszystkich rodzajow watkow.
   Wady:
   • Jadro nic nie wie o istnieniu poszczegolnych watkow, dlatego istnieje niebezpieczenstwo, ze jeden zablokowany watek (np. na blokujacym wywolaniu systemowym) zablokuje caly proces.
   • W systemie wieloprocesorowym watki uzytkownika nie moga byc przypisywane roznym procesorom i dzialac "rownolegle".
4. Watki na poziomie jadra (kernel-level)
   Kazdy watek jest osobnym unixowym procesem, dzieli przestrzen adresowa z innymi watkami przez wywolanie clone() (w implementacji LinuxThreads). Za przelaczanie kontekstu miedzy watkami odpowiedzialne jest jadro analogicznie do zarzadzania "normalnymi" procesami.
   Zalety:
   • mozliwosc efektywnego wykorzystania systemu wieloprocesowego
   • plynniejsze przelaczanie ze wzgledu na fakt, ze procesy i watki sa zarzadzane przez jeden mechanizm
   • nie ma potrzeby definiowania nowych nieblokujacych wersji wywolan systemowych jak w watkach user-space (blokowany moze byc tylko pojedynczy watek, reszta zas dzialac bez zaklucen)
   • jako konsekwencja poprzedniego punktu, wydajniejsze operacje wejscia/wyjscia i zegarowe
   Wady:
   • "najdrozsze" (ze wzgledu na czas) przelaczanie miedzy watkami spowodowane koniecznoscia przelaczenia procesora w tryb jadra, przynajmniej przy blokowaniu na warunkach i mutexach
   • tworzenie watkow jest rowniez "drozsze"
5. Dwupoziomowy system watkow (two-level, hybrid thread system)
   Dwupoziomowy system watkow jest polaczeniem watkow uzytkownika i watkow jadra. Jadro tworzy lekkie procesy, ktore zawieraja w sobie jeden lub wiecej watkow z poziomu uzytkownika (odwzorowania: 1-1 to watki jadra, 1-n to watki uzytkownika, m-n to watki posrednie).
   Zalety:
   • Poza przypadkiem 1-n system watkow dwupoziomowych zapewnia prace na wielu procesorach rownolegle.
   • Wykonanie blokujacego wywolania systemowego moze spowodowac zablokowanie pewnej puli watkow (zaszeregowanych do jednego lekkiego procesu w jadrze) jednak nie jest az tak niebezpieczne jak w "czystych" watkach uzytkownika, gdyz w przypadku odkrycia przez system, ze wszystkie lekkie procesy danego pelnego procesu sa zablokowane, wysylany jest sygnal, przechwytywany przez biblioteke na poziomie uzytkownika, ktora tworzy nowy lekki proces aby wykonanie moglo przebiegac mimo blokady (tak jest np. w implementacji Solaris-threads).
   Wady:
   • Przelaczanie kontekstu jast wolniejsze niz w watkach uzytkownika, jednak jest szybsze niz w watkach przestrzeni jadra
6. Dostepne metody synchronizacji
7. Wzajemne wyklucznanie - Mutual Exclusion Locks (mutex)
8. Czytelnicy/Pisarz - Readers/Writer Locks (RWLock)
9. Liczace Semafory
10. Zmienne warunkowe (Condition Variables)
11. Problemy zwiazane z programowaniem wielowatkowym
    • Obsluga sygnalow. Nie ma mozliwosci ustawienia osobnej obslugi sygnalow dla kazdego z watkow. Mozna zablokowac lub odblokowac sygnaly osobno dla kazdego z nich. Istnieje mozliwosc wysylania sygnalow do poszczegolnych watkow jednak wymaga to stworzenia specjalnego (dodatkowego) watku, ktory w sposob synchroniczny czekiwalby na sygnal (sigwait) i dostarczal obsluge wszystkich sygnalow.
    • Najprostszym rozwiazaniem problemu MT-safety jest otoczenie kodu mutexem, ktory zapewni, ze tylko jeden watek na raz bedzie wykonywal dany kod. Rozwiazanie to jest niesamowicie nieefektywne i dodatkowo nie dziala na funkcjach o roznym wykonaniu przy roznych wywolaniach (np. funkcja strtok()). Dlatego tworzone sa biblioteki dostarczajace standardowe funkcje bezpieczne dla watkow (thread-safe) rozroznione od tradycyjnych przez dodanie sufiksu "_r" (od reentrant).
    • Dolaczanie do innego watku (synchroniczne konczenie pracy watkow). Ze wzgledu na fakt, ze watki, w odroznieniu od procesow w Unixie, nie sa zwiazane relacja ojciec-syn, nie wiadomo, czy watek, na ktorego zakonczenie doczekalismy sie, jest jednym z "naszych". Rozwiazaniem jest trzymanie informacji o liczbie aktywnych watkow lub tworzenie watkow "rozdzielonych" (detached threads) i zmuszenie ich do zmniejszania licznika tuz przed koncem ich wykonania.
    • dziedziczenie watkow przy fork()
    • Stosowanie priorytetow - wydziedziczanie
    • Uzywanie bibliotek skompilowanych bez opcji REENTRANT
12. Implementacja na przykladzie linuxa i dwoch wybranych bibliotek (linuxthreads, pthreads for linux)
13. Windows NT Threads (roznice z POSIX threads)
14. Biblioteki ulatwiajace programowanie:
    • ACE (Adaptive Communication Environement) UNIX, POSIX, Win32 - zorientowane obiektowo narzedzie implementujace podstawowe wzorce projektowania oprogramowania komunikacyjnego. Miedzy innymi demultiplexing (?) zdarzen,... , wielowatkowosc i controle wspolbieznosci.
    • TNF on Sun
    • QuickThreads - narzedzie do budowania pakietow uzywajacych watkow

1. comp.programming.threads news group FAQ
   http://www.best.com/~bos/threads-faq/
2. SUN POSIX threads FAQ
   http://www.sun.com/workshop/sig/threads/posix.html
3. LinuxThreads - biblioteka watkow poziomu jadra dla Linuxa.
   http://pauillac.inria.fr/~xleroy/linuxthreads/
4. PCThreads - biblioteka watkow poziomu uzytkownika dla Linuxa.
   http://www.aa.net/~mtp/PCthreads.html
5. ACE (Adaptive Communication Encironment) - oficjalna strona
   http://www.cs.wustl.edu/~schmidt/ACE.html
6. Pelna ostatnia wersja biblioteki ACE dla Linuxa (zrodla) z ICM SUNSITE FTP MIRROR.
   ftp://sunsite.icm.edu.pl/pub/programming/ace
   Uwaga! Aby skompilowac cala biblioteke wraz z testami i przykladami potrzebne bedzie ponad 150Mb wolnej przestrzeni dyskowej.