Programowanie współbieżne i rozproszone/PWR Ćwiczenia 9

Scenariusz zajęć

Co to s± w±tki

W±tki s± często nazywane lekkimi procesami, ponieważ s± podobne do procesów unixowych.

Aby wyja¶nić różnicę między procesem i w±tkiem należy zdefiniować pojęcie procesu. Proces zawiera wykonywalny program (kod programu), grupę zasobów takich jak deskryptory plików, zarezerwowane bloki pamięci etc. oraz kontekst czyli pozycję wskaĽnika stosu oraz warto¶ć licznika rozkazów.

W±tki mog± współdzielić zasoby w obrębie jednego procesu. Mog± korzystać z tych samych obszarów pamięci, pisać do tych samych plików. Jedyne co charakteryzuje w±tek to jego kontekst. Na program napisany z użyciem w±tków można spojrzeć jak na grupę zasobów dzielon± przez kilka mini-procesów.

W zwi±zku z tym, że w±tki s± "małe" w porównaniu do procesów, ich obsługa jest mniej kosztowna dla systemu operacyjnego. Mniej pracochłonne jest utworzenie nowego w±tku, bo nie trzeba przydzielać dla niego zasobów, mniej czasu zabiera też zakończenie w±tku, bo system operacyjny nie musi po nim "sprz±tać". Jednak główny zysk polega na zmniejszeniu kosztu przeł±czania między w±tkami w obrębie jednego procesu.

Przeł±czenie kontekstu, które normalnie odbywa się wiele razy na sekundę w j±drze systemu operacyjnego, jest operacj± kosztown±. Wi±że się ono ze zmian± struktur systemowych, wczytaniem odpowiednich warto¶ci do rejestrów procesora. Dlatego wła¶nie wymy¶lono mechanizm w±tków, aby zredukować koszt pojedynczego przeł±czenia.

Implementacja w±tków

Ze względu na sposób implementacji, wyróżniamy dwa typy w±tków: w±tki poziomu użytkownika (user-space threads) i w±tki poziomu j±dra (kernel-space threads).

W±tki poziomu użytkownika

W±tki poziomu użytkownika rezygnuj± z zarz±dzania wykonaniem przez j±dro i robi± to same. Często jest to nazywane "wielow±tkowo¶ci± spółdzielcz±", gdyż proces definiuje zbiór wykonywalnych procedur, które s± "wymieniane" przez operacje na wskaĽniku stosu. Zwykle każdy w±tek "rezygnuje" z procesora przez bezpo¶rednie wywołanie ż±dania wymiany (wysłanie sygnału i zainicjowanie mechanizmu zarz±dzaj±cego) albo przez odebranie sygnału zegara systemowego.

Implementacje w±tków poziomu użytkownika napotykaj± na liczne problemy, które trudno obej¶ć, np.:

• problem "kradzenia" czasu wykonania innych w±tków przez jeden w±tek
• brak sposobu wykorzystania możliwo¶ci SMP (ang. symetric multiprocessing, czyli obsługa wielu procesorów)
• oczekiwanie jednego z w±tków na zakończenie blokuj±cej operacji wej¶cia/wyj¶cia powoduje. że inne w±tki tego procesu też trac± swój czas wykonania.

Obecnie w±tki poziomu użytkownika mog± szybciej dokonać wymiany niż w±tki poziomu j±dra, ale ci±gły rozwój tych drugich powoduje, że ta różnica jest bardzo mała.

W±tki poziomu j±dra

W±tki poziomu j±dra s± często implementowane poprzez doł±czenie do każdego procesu tabeli/listy jego w±tków. W tym rozwi±zaniu system zarz±dza każdym w±tkiem wykorzystuj±c kwant czasu przyznany dla jego procesu-rodzica.

Zalet± takiej implementacji jest zniknięcie zjawiska "kradzenia" czasu wykonania innych w±tków przez "zachłanny" w±tek, bo zegar systemowy tyka niezależnie i system wydziedzicza "niesforny" w±tek. Także blokowanie operacji wej¶cia/wyj¶cia nie jest już problemem. Ponadto przy poprawnym zakodowaniu programu, proces może automatycznie wyci±gn±ć korzy¶ci z istnienia SMP przy¶pieszaj±c swoje wykonanie przy każdym dodatkowym procesorze.

Tworzenie wątków

Do tworzenia w±tków służy funkcja pthread_create.

  int pthread_create( pthread_t *thread, pthhread_attr_t *attr,
                      void (* func)(void *), *arg)

Funkcja ta tworzy w±tek, którego kod wykonywalny znajduje się w funkcji podanej jako argument func. W±tek jest uruchamiany z parametrem arg, a informacja o w±tku (deskryptor w±tku) jest umieszczana w strukturze thread.

Podczas wywołania funkcji pthread_create tworzony jest w±tek, który działa do chwili gdy funkcja będ±ca tre¶ci± w±tku zostanie zakończona przez return, wywołanie funkcji pthread_exit lub po prostu zostanie wykonana ostatnia instrukcja funkcji.

Czekanie na zakończenie w±tku

Podobnie jak w przypadku procesów program główny może oczekiwać na zakończenie się w±tków, które stworzył - służy do tego funkcja pthread_join.

  int pthread_join( pthread_t *thread, void *status)
  

Je¶li więcej niż jeden w±tek czeka na zakończenie jakiego¶ w±tku to tylko dla jednego z oczekuj±cych funkcja nie zakończy się błędem.

Każdy w±tek ma przypisany atrybut, który okre¶la, czy można oczekiwać na jego zakończenie. Aby udało się oczekiwanie na zakończenie w±tku warto¶ci± tego atrybutu (zwanego detachstate) musi być PTHREAD_CREATE_JOINABLE. Atrynuty s± przekazywane do w±tku w chwili jego tworzenia jako warto¶ć parametru attr funkcji pthread_create. Do ustawienia tego atrybutu służy funkcja:

  int pthread_attr_setdetachstate( pthread_attr_t *attr, int *state)

Po uruchomieniu w±tku można jeszcze zmienić warto¶ć tego atrybutu poprzez wywołanie funkcji pthread_detach, która powoduje, że na w±tek nie można będze oczekiwać. Taki w±tek będziemy nazywać "odł±czonym".

  int pthread_detach( pthread_t *thread)

Je¶li w±tek przejdzie w stan odł±czony to zaraz po zakończeniu tego w±tku czyszczone s± wszystkie zwi±zane z nim struktury w pamięci. Je¶li jednak w±tek nie przejdzie do stanu odł±czony to informacja o jego zakończeniu pozostanie w pamięci do czasu,

aż inny w±tek wykona funkcję pthread_join dla zakończonego w±tku.

Synchronizacja w±tków

  Do synchronizacji w±tków niezbyt dobrze nadaj± się dotychczas poznane mechanizmy, 
  dlatego istniej± osobne dla nich mechanizmy synchronizacyjne.

  Muteksy
  -------
  Aby zainicjować muteks należy użyć funkcji pthread_mutex_init.
  Muteks w działaniu przypomina semafory. S± na nim dostępne trzy operacje: 
  pthread_mutex_lock
  pthread_mutex_unlock
  pthread_mutex_trylock

  Muteks może być w dwóch stanach: może być wolny albo może być w posiadaniu 
  pewnego watku. Proces, który chce zdobyć muteks wykonuje operację lock. Je¶li muteks 
  jest wolny, to operacja konczy sie powodzeniem i w±tek staje się wła¶cicielem muteksa. 
  Je¶li jednak muteks jest w posiadaniu innego watku, to operacja powoduje wstrzymanie 
  watku aż do momentu kiedy muteks bedzie wolny. Przypomina to zatem operacje wej¶cia
  do monitora.
  W±tek, który jest w posiadaniu muteksa może go oddać wykonuj±c operację unlock.
  Powoduje to obudzenie pewnego w±tku oczekuj±cego na operacji lock, je¶li taki jest i 
  przyznanie mu muteksa. Je¶li nikt nie czeka, to mutekst staje się wolny. 
  Przypomina to zatem operację wyj¶cia z monitora. Zwróćmy uwagę, że 
  unlock może wykonać tylko ten proces, który posiada muteks.
  
  Implementacja w Linuksie nie narzuca powyższego wymogu, ale używanie operacji lock
  i unlock w inny sposób powoduje nieprzeno¶no¶ć programu. 

  S± trzy rodzaje muteksów opisane na stronach podręcznika. Zapoznaj się z nimi.
* man pthread_mutex_lock
* man pthread_mutex_unlock
* man pthread_mutex_trylock

  Zmienne warunkowe
  ----------------

  Zmienne warunkowe to odpowiednik kolejek w monitorze. Operacje wait() i signal()
  to odpowiednio pthread_cond_wait i pthread_cond_signal.
  
  Aby zasymulować działanie monitora należy używać muteksa broni±cego 
  wej¶cia do monitora. Operacja wej¶cia do monitora odpowiada operacji lock na muteksie, 
  a operacja wyj¶cia --- wykonaniu unlock. Zwróć uwagę, że jest to zgodne z tym,
  że unlock może wykonać jedynie proces, który jest w posiadaniu muteksa (czyli jest
  w monitorze). Operacje na zmiennych warunkowych monitora wykonuje się za pomoc± 
  pthread_cond_wait oraz pthread_cond_signal. 
  Drugim argumentem operacji pthread_cond_wait jest muteks, który jest zwalniany  
  atomowo wraz z zawieszeniem na kolejce (chwilowe wyj¶cie z monitora).

* man pthread_cond_wait

  Standardowy scenariusz użycia zmiennej warunkowej wygl±da następuj±co:

  pthread_mutex_lock(&mut)
  ...
  while( warunek ) 
      pthread_cond_wait( &cond, &mut)
  ...
  pthread_mutex_unlock(mut)

  Zwróć uwagę na użycie pętli zamiast warunku! Jest to spowodowane tym, że 
  monitory gwarantuj± zwalnianie procesów oczekuj±cych na zmiennych warunkowych
  przed wpuszczeniem nowych procesów do monitorów --- dlatego instrukcja if jest
  wystarczaj±ca. W przypadku muteksów takiej gwarancji nie ma, więc po zwolnieniu 
  muteksa do monitora może wej¶c inny proces, "zepsuć" warunek, na który oczekiwał 
  budzony proces. Obudzony proces musi zatem ponownie sprawdzić, czy warunek jest 
  spełniony --- st±d użycie pętli.

* Przeanalizuj program prod_kon.c. Zwróć uwagę na funkcje put() i get() w których odbywa
  się synchronizacja między w±tkami producenta i konsumenta.

  Oprócz powyższych operacji dostępne s± również dwie dodatkowe:
  pthread_cond_timedwait - czeka tylko przez okre¶lony czas
  pthread_cond_broadcast - budzi wszystkie w±tki czekaj±ce w kolejce
  
* man pthread_cond_broadcast

* Przeanalizuj program timeout.c zwróć uwagę na użycie funkcji pthread_cond_timedwait().

8. Jak wymusić zakończenie w±tku?

  ------------------------------
  Aby wymusić zakończenie w±tku w sztuczny sposób należy wywołać funkcję 
  pthread_cancel.
  
  int pthread_cancel( pthread_t thread)
  
* man pthread_cancel

  Aby udało się przerwać działanie w±tku musimy na to zezwolić wywołuj±c funkcję 
  pthread_setcancelstate.

  pthread_setcancelstate( int state, int * oldstate)

* man pthread_setcancelstate
  
  Je¶li w±tek jest w stanie, w którym nie można go przerwać to ż±danie przerwania go
  funkcj± pthread_cancel jest wstrzymywane do czasu, kiedy będzie można zakończyć 
  w±tek.

9. Dwa tryby kończenia w±tków

  --------------------------

  Wywołanie funkcji pthread_cancel powoduje różn± reakcję kończonego w±tku w zależno¶ci
  od trybu zakończenia w±tku w jakim znajduje się kończony w±tek.

  W trybie asynchronicznym w±tek jest kończony natychmiast w momencie wywołania 
  pthread_cancel przez inny w±tek.
  W trybie "deffered" w±tek nie jest kończony od razu. Kończy się on dopiero w momencie
  dotarcia do tzw. "cancellation point". Cancellation point jest większo¶ć wywołań
  funkcji systemowych, należy jednak uważać aby wykorzystywać zgodne z w±tkami 
  biblioteki. 
  Funkcje, które na pewno s± przygotowane do pracy z w±tkami to: read, write, select,
  accept, sendto, recvfrom, connect.
  
  UWAGA, funkcja pthread_mutex_lock, o której będzie mowa póĽniej, nie jest cancellation 
  point.
  
  W±tek może też sztucznie wej¶ć do cancellation point wywołuj±c funkcję 
  pthread_testcancel.

  void pthread_testcancel(void)
  
* man pthread_testcancel

10. Bloki czyszcz±ce

   ----------------

  Aby nie dopu¶cić do blokad wynikaj±cych z przerwania w±tku, który zablokował
  jakie¶ zasoby ( semafory, pliki etc. ) wymy¶lono mechanizm bloków czyszcz±cych.
  Po zablokowaniu jakiego¶ zasobu rejestruje się funkcję która powinna zostać 
  wykonana je¶li wykonanie w±tku zostanie zakłócone przy pomocy funkcji 
  pthread_cleanup_push.

  pthread_cleanup_push( void (*func)(void *), void *arg) 

* man pthread_cleanup_push
  
  Aby odrejestrować funkcję czyszcz±c± np. po odblokowaniu zasobu należy użyć 
  funkcji pthread_cleanup_pop.

  pthread_cleanup_pop( int exec)

* man pthread_cleanup_pop

  Standardowe użycie bloków czyszcz±cych mogłoby wygl±dać następuj±co:

  pthread_mutex_lock(&mut)
  pthread_cleanup_push(pthread_mutex_unlock, &mut)
  ...
  pthread_mutex_unlock(&mut)
  pthread_cleanup_pop(FALSE)   

  Dwie ostatnie operacje można poł±czyć w jedno wywołanie funkcji pthread_cleanup_pop
  z argumentem TRUE. Takie wywołanie oznacza, że podczas odrejestrowywania blok 
  zostanie wykonany, zatem w tym przykładzie zostanie odblokowany semafor.

  pthread_mutex_lock(&mut)
  pthread_cleanup_push(pthread_mutex_unlock, &mut)
  ...
  //   pthread_mutex_unlock(&mut)
  pthread_cleanup_pop(TRUE)   

  Bloki czyszcz±ce s± rejestrowane na stosie, więc nie ma przeszkód aby stosować 
  zagnieżdżone bloki czyszcz±ce. W sytuacji załamania w±tku bloki zostan± wykonane
  w kolejno¶ci odwrotnej do ich rejestrowania.

* Przeanalizuj program cancel.c. Zwróć uwagę na użycie bloków czyszcz±cych oraz ¶wiadome

 wej¶cie do cancellation point przy użyciu pthread_testcancel.

   ------------------------------------------------------------------------
  | Napisz system realizuj±cy problem pięciu filozofów przy użyciu w±tków, |
  | zmiennych warunkowych i muteksów.                                     |
  | UWAGA, chodzi o rozwi±zanie z monitorem.                               |
  | Oczywi¶cie każdy w±tek powinien wypisywać co aktualnie robi.           |
   ------------------------------------------------------------------------