opracowanie

ZAGADNIENIA NA KOLOKWIUM Z QNX’a - 31.05.2007

(na podstawie PDF-ów dr Ułasiewicza)

1. Podstawowe pojęcia współbieŜności: bezpieczeństwo, Ŝywotność, bloka-
da, zagłodzenie.

Bezpieczeństwo - aplikacja jest bezpieczna, jezeli utrzymuje system w pozadanym
stanie. W odniesieniu do modelu klient–serwer bezpieczenstwo oznacza ze klienci sa
obslugiwani w zadowalający sposób:

1. Serwer nie zaprzestal obslugi zlecen.
2. Na zlecenia odpowiadal w prawidlowy sposób.

Pierwszy  z  warunków  nie  bedzie  spelniony  gdy  wystapi  blokada  serwera  (ang.
dealock).  Drugi  warunek  bedzie  zagrozony  gdy  nie  zostanie  zachowany  warunek
wzajemnego  wykluczania  procesów  przy  dostepie  do  niepodzielnego  z  natury  za-
sobu. Wzajemne wykluczanie musi byc zapewnione gdy kilka procesów ma dostep
do wspólnego obszaru pamieci i przynajmniej jeden z nich modyfikuje ten obszar.

Zywotnosc - aplikacja jest zywotna, jezeli kazde pozadane zdarzenie w koncu zaj-
dzie. W modelu klient–serwer zywotnosc oznacza ze kazdy klient zostanie w koncu
obsluzony.

Uczciwosc - Aplikacja jest uczciwa, jezeli zadajace obslugi procesy sa traktowane
jednakowo lub zgodnie ze swoimi priorytetami.
W modelu klient–serwer uczciwosc oznacza ze kazdy klient zostanie obsluzony
zgodnie z kolejnoscia zgloszen lub priorytetem.
Wyróznia sie nastepujace rodzaje uczciwosci:

1. Uczciwosc mocna – jesli proces zglasza zadanie nieskonczenie wiele razy to w

koncu zostanie ono obsluzone.

2. Uczciwosc liniowa – jesli proces zglasza zadanie bedzie ono obsluzone zanim do-

wolny inny proces bedzie obsluzony wiecej niz raz.

3. Uczciwosc typu FIFO – zadania procesów sa obslugiwane zgodnie z kolejnoscia

ich zglaszania. (FIFO – ang. First-In First-Out)

Blokada  -  Z  blokada  mamy  do  czynienia  gdy  kazdy  z  zablokowanych  procesów
oczekuje  na  zdarzenie  które  moze  byc  wygenerowane  tylko  przez  którys  z  zabloko-
wanych  procesów.  Blokada  zwana  tez  zakleszczeniem  jest  typowym  zagrozeniem
aplikacji wspólbieznych.

Zagłodzenie - sytuacja, w której dany proces nie jest w stanie zakończyć  działania,
poniewaŜ  nie  ma  dostępu  do  procesora  lub  innego  współdzielonego  zasobu.  Wystę-
puje  najczęściej  na  skutek  niewłaściwej  pracy  algorytmu  szeregowania,  którego  za-
daniem jest sprawiedliwy przydział zasobów, lub nadmiernego obciąŜenia systemu.

2. Powody stosowania aplikacji współbieŜnych.

Korzysci wynikajace z zastosowania wspólbieznosci:

1. Polepszenie wykorzystania zasobów. Gdy jakis proces czeka na niedostepny w

danej chwili zasób, procesor moze wykonywac inny proces.

2. Podzial zadania na procesy umozliwia wykonywanie ich na oddzielnych maszy-

nach. Prowadzi to do zrównoleglenia przetwarzania.

3. Podzial duzego zadanie na wiele mniejszych komunikujacych sie procesów pro-

wadzi do dekompozycji problemu. Ulatwia to ich implementacje, uruchamianie i
testowanie przez wielu niezaleznych programistów.

Trudnosci powstajace przy implementacji aplikacji wspólbieznych:
1.  problem sekcji krytycznej
2.  problem synchronizacji procesów
3.  problem zakleszczenia

3. Architektura komputera klasy PC. Metody ochrony pamięci (segmenta-
cja, stronicowanie), metody ochrony procesora (tryby system / uŜytkow-
nik).

Podstawowe architektury systemów komputerowych

1.  Komputery jednoprocesorowe
2.  Komputery wieloprocesorowe ze wspólna pamiecia.
3.  Komputery równolegle
4.  Systemy rozproszone

Systemy jednoprocesorowe
Wiekszosc  tradycyjnych  komputerów  posiada  wlasnie  taka  architekture.  System
sklada sie z procesora, pamieci i róznych urzadzen wejscia / wyjscia (dysków, nape-
dów  dyskietek,  kart  sieciowych,  portów  szeregowych  i  równoleglych  itd.).  Urzadze-
nia  wejscia  /  wyjscia  sa  podlaczone  do  szyny  komputera  za  pomoca  kontrolerów
tych urzadzen.

4. Pojęcie procesu, stany procesów, graf stanu procesów, fazy wykonania

procesów, dziedziczenie atrybutów.

Proces  -  wykonujacy  sie  program.  Proces  jest  wiec  aktywna  struktura  dynamiczna
istniejaca  tylko  w  srodowisku  dzialajacego  komputera.  Aby  proces  mógl  sie  wyko-
nywac potrzebne sa co najmniej nastepujace zasoby:
  procesor
  pamiec operacyjna
  urzadzenia wejscia / wyjscia

Rodzaje procesów

Procesy sekwencyjne (ang. Sequential processes)
Procesy sa sekwencyjne jezeli nastepny proces ze zbioru procesów rozpoczyna sie
po zakonczeniu procesu poprzedniego.
Procesy wspólbiezne (ang. Concurrent processes)
Dwa procesy sa wspólbiezne jezeli jeden z nich rozpoczyna sie przed zakonczeniem
drugiego.
Procesy równolegle (ang.Paralell processes)
Dwa procesy sa równolegle jezeli jeden z nich rozpoczyna sie przed zakonczeniem
drugiego i wykonywane sa jednoczesnie na oddzielnych procesorach.

Kanoniczne stany procesów
Proces moze byc w jednym z trzech podstawowych stanów:
- wykonywany (ang. Running),
- gotowy (ang. Ready)
- zablokowany (ang. Blocked).

Pokazane na rysunku przejscia maja miejsca w nastepujacych sytuacjach.
1. Proces zada zasobu który nie jest dostepny.
2.  Wystapilo  przerwanie  (proces  zostal  wywlaszczony)  lub  tez  proces  dobrowolnie
zwolnil procesor.
3. Procedura szeregujaca zdecydowala ze ten proces ma byc wykonywany.
4.  Zasób,  którego  brakowalo  do  kontynuacji  procesu stal sie dostepny. Przejscie zo-
stalo  zainicjowane  przez  przerwanie  od  urzadzenia  wejscia  /  wyjscia  lub  tez  proces
aktualnie wykonywany.

Atrybuty procesu sa to informacje wykorzystywane przez system do zarzadzania
procesami a wiec do ich identyfikacji, szeregowania, utrzymywania bezpieczenstwa i
uruchamiania. Najwazniejsze atrybuty procesu:

- PID - identyfikator procesu,
- PPID - PID procesu macierzystego,
- UID - identyfikator uzytkownika
- GID - identyfikator grupy do której nalezy uzytkownik
- SID - identyfikatory sesji
- PGRP - identyfikatory grupy procesów,
- priorytet procesu,
- CWD - katalog biezacym
- katalog glówny
- otoczenie procesu

Fazy wykonania procesu

1. Tworzenie :
- Alokacja deskryptora procesu, przydzial PID
- Ustalenie zmiennych otoczenia – zwykle dziedziczone z procesu macierzystego
2. Ladowanie
Zaladowanie  segmentu  kodu  i  danych  oraz  inicjacji  stosu.  Ladowanie  wykonywane
jest przez oddzielny watek ladujacy aby nie blokowac administratora procesu Proc.
3. Faza wykonania
Po  zaladowaniu  nowy  proces  jest  umieszczany  w  kolejce  procesów  gotowych,  uru-
chamiany i zaczyna wspólzawodniczyc o zasoby.
4. Faza zakonczenia
Zakonczenie procesu moze byc zainicjowane przez sam proces – gdy wykona on
funkcje exit, lub poprzez wyslany z zewnatrz sygnal. Zakonczenie sklada sie z
dwu etapów.
a)  Zwolnienie  zasobów  -  proces  zwalnia  wszystkie  zajmowane  zasoby  jak  pamiec,
nazwy,  itd.  oraz  likwiduje interakcje z  innymi procesami. Po wykonaniu  tej fazy zaj-
muje tylko deskryptor.
b) Zawiadomienie procesu macierzystego o zakonczeniu. Dopóki proces macierzysty
nie  wykona  funkcji  wait  lub  waitpid  konczony  proces  pozostaje  w  stanie  „zombie”.
Aby  uniknac  pozostawania  procesów  w  stanie  „zombie”  mozna  ustawic  reakcje  na
sygnal SIGCHLD w funkcji signal na SIG_IGN.

Stany procesu w systemie QNX

READY
Proces posiada wszystkie potrzebne zasoby oprócz procesora.
BLOCKED
Proces zablokowany na pewnej operacji komunikacji miedzyprocesowej:
SEND_BLOCKED, RECEIVE_BLOCKED, REPLY_BLOCKED, SIGNAL_BLOCKED.
HELD
Proces otrzymal sygnal SIGSTOP I przebywa w stanie HELD. Gdy otrzyma sygnal
SIGCONT bedzie wznowiony a gdy inny sygnal zakonczy sie.
WAIT
Proces wykonal funkcje wait ale zaden z procesów potomnych nie zakonczyl sie.
DEAD
Stan zwany tez „zombie”. Proces sie zakonczyl ale jego proces macierzysty nie wy-
konal funkcji wait.

Przejscia pomiedzy stanami procesu w systemie QNX

Wykonanie funkcji exec powoduje zastapienie starego segmentu kodu, danych i
stosu nowymi. Nowy proces dziedziczy ze starego PID, PPID, priorytet, srodowisko,
katalog biezacy.

5. Tworzenie procesów, deskryptor procesu, funkcje fork, exec, wait, wait-
pid, exit. Makra WEXITSTATUS, WTERMSIG, WIFEXITED, WIFSIGNAL.

Utworzenie procesu
Operacja powoduje utworzenie deskryptora i alokacje pamieci niezbednej dla proce-
su.
Deskryptor (ang. descriptor) - struktura definiująca określony obiekt w pamięci.
Deskryptor procesu zawiera informacje o zmiennych dzielonych wykorzystywanych
przez proces.

Tworzenie kopii procesu biezacego – funkcja fork()
Funkcja ta tworzy kopie procesu biezacego czyli tego procesu który wykonuje funk-
cje fork(). Utworzony proces potomny rózni sie od macierzystego pod nastepujacy-
mi wzgledami:
1. Ma inny PID.
2 .Ma inny PID procesu macierzystego (ang. parent PID).
3. Proces potomny zachowuje otwarte pliki procesu macierzystego ale tworzy wla-
sne kopie ich deskryptorów.

Dzialanie funkcji fork – procesy macierzysty i potomny wykonywane sa wspólbieznie.
Funkcja fork tworzy deskryptor nowego procesu oraz kopie segmentu danych i stosu
procesu macierzystego.
1. Wartosci zmiennych w procesie potomnym sa takie jak w procesie macierzystym
bezposrednio przed wykonaniem funkcji fork.

2. Modyfikacje zmiennych danych dokonywane w procesie macierzystym nie sa widocz-
ne w procesie potomnym (i odwrotnie) gdyz kazdy z procesów posiada wlasna kopie
segmentu danych.

Funkcja exec
Kazda funkcja z rodziny exec przeksztalca biezacy proces w nowy proces tworzony
z  pliku  wykonywalnego  bedacego  jednym  z  parametrów  funkcji  exec.  Wykonanie
funkcji  exec  powoduje  zastapienie  starego  segmentu  kodu,  danych  i  stosu  nowymi
Nowy  proces  dziedziczy  ze  starego  PID,  PPID,  priorytet,  srodowisko,  katalog  bieza-
cy.

Funkcja exit
Wykonanie  funkcji  exit(x)  powoduje  zakonczenie  sie  procesu  biezacego.Wszystkie
zasoby  zajmowane  przez  proces  z  wyjatkiem  jego  deskryptora  sa zwalniane. Dodat-
kowo wykonywane sa nastepujace akcje:
1. Otwarte pliki i strumienie sa zamykane.
2.  Najmlodszy  bajt  (8  bitów)  z  kodu  powrotu  x  jest  przekazywane  do  zmiennej  sta-
tus  odczytywanej  przez  funkcje

wait() wykonana w procesie macierzystym. Kod

powrotu przechowywany jest w deskryptorze procesu.
3. Gdy  proces macierzysty wykonal wczesniej funkcje wait()  albo  waitpid()  i jest
zablokowany, nastepuje jego odblokowanie i usuniecie deskryptora.
4.  Gdy  proces  macierzysty  nie  wykonal  wczesniej  funkcje  wait()  albo  waitpid()
kod  powrotu  przechowywany  jest  w  deskryptorze  procesu  a  proces  przechodzi  do
stanu „zoombie”.
5.  Jezeli  konczony  proces  posiada  jakies  procesy  potomne,  wysylany  jest  do  nich
sygnal  SIGHUP.  Procesy  te  sa  adoptowane  przez  inny  proces.  Zwykle  jest  to  naj-
wyzszy proces w hierarchii.
6. Do procesu macierzystego wysylany jest sygnal SIGCHLD.

Funkcja wait
Funkcja wait() powoduje ze proces macierzysty bedzie czekal na zakończenie pro-
cesu potomnego. Dzialanie funkcji wait jest nastepujace:
1. Gdy proces potomny nie zakonczyl sie funkcja wait powoduje zablokowanie pro-
cesu  macierzystego  az  do  zakonczenia  sie  procesu  potomnego.  Gdy  ten  się  zakon-
czy zwracany jest jego PID oraz status.
2.  Gdy  proces  potomny  zakonczyl  sie  zanim  wykonano  funkcje  wait  nie  wystepuje
blokada  procesu  macierzystego.  Funkcja  zwraca  PID  zakonczonego  procesu  oraz
jego status.
3. Gdy brak jakichkolwiek procesów potomnych funkcja wait zwraca –1,

Funkcja waitpid
Funkcja waitpid wstrzymuje proces wywołujący do momentu, aŜ potomek określony
przez pid przestanie działać.

Testowanie statusu zakonczonego procesu.
Status zakonczonego procesu udostepniany jest przez funkcje wait
pid = wait(&status)
Wartosc zmiennej status zalezy od:
1. Systemu operacyjnego, który umieszcza tam informacje o przyczynach i sposobie

zakonczenie procesu.
2. Zakonczonego procesu potomnego, który umieszcza tam wartosc kodu powrotu –
jest to parametr funkcji exit.

Makra WIFEXITED, WEXITSTATUS, WIFSIGNALED, WTERMSIG

Inicjowanie zakonczenia procesu
Zakonczenie sie procesu nastepuje w podanych nizej przypadkach:
1. W dowolnym miejscu kodu procesu wykonana zostanie funkcja

exit

2. Funkcja

main

procesu wykona instrukcje

return

3. Funkcja main procesu wykona ostatnia instrukcje kodu.
4. Proces zostanie zakonczony przez system operacyjny lub inny proces.
Preferowanym sposobem zakonczenia procesu jest wykonanie funkcji exit

6. Tworzenie procesów za pomocą funkcji spawn. Tworzenie procesów na
innym węźle.

Tworzenie nowego procesu za pomoca funkcji spawn
Kazda funkcja z rodziny spawn tworzy nowy proces potomny na podstawie pliku
wykonywalnego okreslonego w jednym z parametrów funkcji .
Srodowisko (ang. Enviroment) jest dziedziczone z procesu macierzystego. Funkcja
zwraca:
> 0 - pid utworzonego procesu potomnego
- 1 - blad gdy proces nie moze byc utworzony

Tryby wykonania procesu:

Uruchamianie procesów na innym wezle niz biezacy.
Aby uruchomic proces na innym wezle nalezy zmodyfikowac zmienna globalna
qnx_spawn_options typu _qnx_spawn_globs. Zmienna i jej typ zdefiniowane
sa w plikach naglówkowych <sys/qnx_glob.h> i <sys/qnx_types.h>. O szczególach
uruchamianego procesu decyduja pola zmiennej qnx_spawn_options .

struct _qnx_spawn_globs {
nid_t node; // Numer wezla na którym uruchamiamy proces
char priority; // Priorytet procesu
char sched_alg; // Algorytm szeregowania
char flags; // Flagi
…
} qnx_spawn_options ;

7. Łacza nienazwane (unnamed pipes) i ich wykorzystanie. Funkcje pipe,
open, read, write, close.

Łącza nienazwane (ang. Unnamed Pipes) i nazwane (ang. Unnamed Pipes) - jedna z
historycznie pierwszych metod komunikacji międzyprocesowej. Wywodzą się z sys-
temu UNIX.
Łącze nienazwane (ang. Pipe) moŜna wyobrazić sobie jako rodzaj „rury bitowej” łą-
czącej dwa procesy. Łącze nienazwane implementowane jest jako bufor cykliczny.

Do pisania i czytania z łącza uŜywa się mechanizmu plików i standardowych funkcji
read i write. Plików nie otwiera się za pomocą funkcji open. Stosownych uchwytów
dostarcza funkcja

pipe w tablicy fildes.

Własności łącz nienazwanych:
1. Kanał  jest jednokierunkowy dla danego procesu i nieuŜywany w tym procesie plik
powinien być  zamknięty.
2. Metoda komunikacji moŜe być  uŜyta tylko dla procesów związanych – będących w
relacji macierzysty / potomny.
3. Jako Ŝe łącze jest buforem typu FIFO utrzymywanym w pamięci operacyjnej ma
ono ograniczoną  pojemność.
4. Operacje zapisu odczytu do łącza są  operacjami atomowymi.

cze nienazwane tworzy si

poprzez wykonanie funkcji pipe:

int pipe(int fildes[2]);
fildes Tablica dwuelementowa na uchwyty plików do odczytu I zapisu
Funkcja tworzy ł

cze nienazwane i umieszcza w tablicy fildes uchwyty plików:

fildes[0] – uchwyt pliku do odczytu.
fildes[1] – uchwyt pliku do zapisu.
Funkcja zwraca: 0 – sukces, -1 – bł

Odczyt z pliku – funkcja read
int read(int fdes, void *bufor, int nbytes)
fdes Uchwyt do pliku zwracany przez funkcję  open
bufor Bufor w którym umieszczane są  przeczytane bajty
nbytes Liczba bajtów którą  chcemy przeczytać.
Funkcja powoduje odczyt z pliku identyfikowanego przez fdes, nbytes bajtów i u-
mieszczenie ich w buforze. Funkcja zwraca:
> 0 – liczbę  rzeczywiście przeczytanych bajtów,
- 1 – gdy błąd.

Zapis do pliku – funkcja write
int write(int fdes, void *bufor, int nbytes)
fdes Uchwyt do pliku zwracany przez funkcję  open
bufor Bufor w którym umieszczane są  bajty przeznaczone do zapisu
nbytes Liczba bajtów którą  chcemy zapisać
Funkcja powoduje zapis do pliku identyfikowanego przez fdes nbytes bajtów znajdu-
jących buforze. Funkcja zwraca:
> 0 – liczbę  rzeczywiście zapisanych bajtów,
- 1 – gdy błąd.

Zamknięcie pliku – funkcja close
int close(int fdes)
fdes Uchwyt do pliku zwracany przez funkcję  open
Funkcja powoduje zamknięcie pliku identyfikowanego przez fdes. NaleŜy ją  wyko-
nać, gdy nie będą  juŜ  wykonywane operacje na danym pliku .

Zamykanie łącz

Co stanie si

gdy deskryptor reprezentuj

cy ł

cze zostanie zamkni

ty?

1. Zamkni

cie deskryptora pliku do zapisu. Gdy istniej

inne procesy które maj

otwarte

te ł

cze dla zapisu nie dzieje si

nic. Gdy nie gdy nie w ł

czu danych procesy zabloko-

wane na odczycie zwracaj

zero.

2. Zamkni

cie deskryptora pliku do odczytu. Gdy istniej

inne procesy które maj

otwar-

te te ł

cze dla odczytu nie dzieje si

nic. Gdy nie do wszystkich procesów zablokowa-

nych na zapisie wysłany zostanie sygnał

SIGPIPE.

8. Łacza nazwane (ang. Named Pipes) i ich wykorzystanie. Funkcja mkfifo.

Pliki FIFO:
- tworzone są  w pamięci operacyjnej,
- widziane są  jednak w przestrzeni nazw plików
- posiadają  zwykłe atrybuty pliku w tym prawa dostępu.

Plik FIFO tworzy się przy pomocy funkcji:
int mkfifo(char * path, mode_t mode)
path Nazwa pliku FIFO (ze ścieŜką)
mode Prawa dostępu do pliku .
Funkcja zwraca: 0 – sukces, -1 – błąd.

Aby proces mógł  uŜyć  pliku FIFO naleŜy:
1. Utworzyć  plik FIFO za pomocą  funkcji mkfifo o ile wcześniej nie został  utworzo-
ny.
2. Otworzyć  plik FIFO za pomocą  funkcji open.
3. Pisać  lub czytać  do / z pliku uŜywając funkcji read lub write.
4. Zamknąć  plik przy pomocy funkcji close.

Własności plików FIFO.
1.  Pliki  FIFO  są  plikami  specjalnymi  tworzonymi  w  pamięci  operacyjnej  ale  widzia-
nymi  w  systemie  plików  komputera.  Stąd  procesy  mające  dostęp  do  tego  samego
systemu plików mogą  się  komunikować  przez pliki FIFO.
2. Operacje zapisu odczytu do / z pliku FIFO są  operacjami atomowymi.
3. Bajty odczytane z pliku FIFO są  stamtąd usuwane.
4.  Zachowanie  się  procesu  przy  próbie  odczytu  z  pustego  pliku  FIFO  lub  zapisu  do
pełnego zaleŜą  od flagi O_NONBLOCK.
5. Informacje w pliku FIFO są  pozbawione struktury.
6. Plik FIFO i jego zawartość  ginie przy wyłączeniu komputera.

9. Model komunikujących się procesów, komunikaty synchroniczne i asyn-
chroniczne, buforowanie, adresowanie, obsługa błędów, rola systemu ope-
racyjnego.

Model procesów procesów komunikatów
Model procesów i komunikatów skonstruowany jest w oparciu o następujące reguły:
Aplikacja składa się ze zbioru procesów sekwencyjnych.
Procesy mogą być wykonywane równolegle. Proces wykonuje się sekwencyjnie i

uŜywa swej pamięci lokalnej.

Proces komunikuje się z otoczeniem za pomocą komunikatów. Są dwie podsta-

wowe operacje komunikacyjne: wysłanie komunikatu i odbiór komunikatu.

Procesy mogą być przydzielone do procesorów w róŜny sposób. Poprawność

działania aplikacji nie powinna zaleŜeć od tego podziału.

Komunikaty
MoŜliwość   przekazywania  komunikatów  pomiędzy  procesami  jest  fundamentalną
własnością   większości  systemów  operacyjnych.  Jeśli  pomiędzy  dwoma  maszynami
istnieje  jakikolwiek  sposób  komunikacji  (sieć   lokalna,  sieć   rozległa,  bezpośrednie
łącze,  wspólna pamięć,  itd.) na pewno daje się  przesłać  komunikat pomiędzy proce-
sami  wykonywanymi  na  tych  maszynach.  Przesłanie  komunikatu  pomiędzy  proce-
sami  jest  przesłaniem  pomiędzy  nimi  pewnej  liczby  bajtów  według  ustalonego  pro-
tokołu.  Przesłanie  komunikatu  jest  operacją  atomową.  Z  przesyłaniem  komunikatów
wiąŜą  się  następujące problemy:
  problem synchronizacji nadawcy i odbiorcy (kto i kiedy czeka),
  problem adresowania (jaki system adresacji),
  problem identyfikacji (czy procesy znają swoje identyfikatory),
  problem przepływu danych (w jedną  czy dwie strony),
  problem  zapewnienia  niezawodnego  przesłania  przez  zawodny  kanał  komunika-

cyjny.

Do zapewnienia komunikacji potrzebne są przynajmniej dwie funkcje interfejsowe –
wysyłająca (send) i odbierająca komunikat (receive).

Komunikacja synchroniczna
Proces wysyłający jest blokowany do czasu otrzymania potwierdzenia Ŝe proces

docelowy otrzymał wysyłany komunikat

Gdy w momencie wykonania funkcji receive brak jest oczekującego komunikatu,

proces odbierający jest wstrzymywany do czasu nadejścia jakiegoś komunikatu.
Gdy jakiś komunikat oczekuje, proces odbierający nie jest blokowany.

Komunikacja synchroniczna pomiędzy procesami P1 i P2

Adresowanie
Do adresowania procesu docelowego stosuje się  następujące rozwiązania:
1. PID procesu
2. IP maszyny + numer portu
3. Nazwy symboliczne procesów
Aby zastosować  nazwy symboliczne konieczny jest serwer nazw (ang. name server).
Skąd znana jest lokalizacja serwera nazw?
1. Lokalizacja serwerów nazw jest ustalona i podana jako parametr instalacyjny sys-
temu
2. Serwery nazw rozgłaszają  swą  lokalizację  innym węzłom.

Rola systemu operacyjnego
Przesyłanie komunikatów realizowane jest przez system operacyjny. Funkcje syste-
mu operacyjnego:
1. Zapewnienie transmisji komunikatu pomiędzy komputerami i ukrycie szczegółów
tej transmisji.
2. Wykrywanie i korygowanie błędów transmisji.
3. Składanie i rozkładanie komunikatów w pakiety transmitowane przez sieć.

10. Przesyłanie komunikatów w systemie QNX. Funkcje Send, Receive, Re-
ply, Creceive. Administrowanie

nazwami, funkcje qnx_name_attach,

qnx_name_detach,

Przesyłanie komunikatów
Przesłanie  komunikatu  pomiędzy  procesami  jest  przesłaniem  pewnej  liczby  bajtów
pomiędzy  tymi  procesami  według  ustalonego  protokołu.  Przesłanie  komunikatu  jest
operacją  atomową.  MoŜliwość  przekazywania  komunikatów  pomiędzy  procesami jest
fundamentalną  własnością  systemu QNX.

W systemie QNX wyróŜniamy następujące akcje związane z przesyłaniem komunika-
tów pomiędzy procesami P1 i P2:
1) Wysłanie komunikatu przez P1 do P2
2) Odbiór komunikatu przez P2
3) Przesłanie odpowiedzi zwrotnej od P2 do P1.

Wysłanie komunikatu
Komunikat do procesu P wysyła się wykonując funkcję Send.

int Send(pid_t pid, void * smsg, void * rmsg, unsigned
sbytes,unsigned rbytes)
Znaczenie parametrów powyŜszej funkcji jest następujące:
pid PID procesu docelowego P
smsg adres bufora danych wysyłanych
rmsg adres bufora danych odbieranych
sbytes liczba bajtów wysyłanych
rbytes max. liczba bajtów odbieranych

Działanie funkcji Send jest następujące:

1) Komunikat smsg wysyłany jest do procesu docelowego po czym proces bieŜący
ulega zablokowaniu.
2) Proces wysyłający jest zablokowany do czasu gdy proces docelowy nie odbierze
wysłanego komunikatu i nie prześle odpowiedzi.
3) Po otrzymaniu odpowiedzi jest ona umieszczana w buforze rmsg i proces bieŜący
jest wznawiany.

Odbiór komunikatu
Do odbioru komunikatów przez proces P słuŜy funkcja Receive. Gdy zachodzi po-
trzeba odbioru komunikatu naleŜy wykonać funkcję Receive.

pid_t Receive(pid_t pid, void * msg, unsigned rbytes)
Znaczenie parametrów powyŜszej funkcji Receive jest następujące:
pid PID procesu nadającego lub 0 – gdy odbiór od wszystkich procesów
rmsg adres bufora danych odbieranych
rbytes max. liczba bajtów odbieranych
Funkcja zwraca: > 0 – PID procesu który nadał komunikat, - 1 - błąd

Zwykle  jako  parametr  pid  w  funkcji  Receive  wstawiamy  0  co  oznacza  Ŝe  odbierane
będą  komunikaty  od  wszystkich  procesów.  Działanie  funkcji  Receive  zaleŜy  od  tego
czy  istnieją  komunikaty  które  zostały  wcześniej  wysłane  do  procesu  P  przez  inne
procesy.  Jeśli  tak  było  to  muszą  one  oczekiwać  w  kolejce  Q  nieodebranych  komuni-
katów. Działanie funkcji jest następujące:
1.  Gdy  w  kolejce  Q  są  nieodebrane  komunikaty  pierwszy  z  nich  usuwany  jest  z  ko-
lejki  Q  i  umieszczany  w  buforze  msg.  Funkcja  zwraca  PID  procesu  który  wysłał  ten
komunikat.  System  powoduje  odblokowanie  procesu  wysyłającego  komunikat.  Pro-
ces bieŜący nie ulega zablokowaniu.
2. Gdy kolejka Q jest pusta proces P ulega zablokowaniu do czasu nadejścia takiego
komunikatu. Zablokowany proces jest w stanie RECEIVE_BLOCKED.
Istnieje  moŜliwość  zmiany  uporządkowania  tej  kolejki  na  uporządkowanie  według
priorytetów  procesów  przysyłających  komunikaty.  NaleŜy  w  tym  przypadku  uŜyć
funkcji qnx_pflags(…). Priorytetowa organizacja kolejki pociąga za sobą  moŜliwość
zagło

dzenia procesów.

Wysłanie odpowiedzi na komunikat
pid_t Reply(pid_t pid, void * msg, unsigned sbytes)
pid PID procesu nadającego lub 0 – odbiór od wszystkich
msg adres bufora danych wysyłanych
sbytes maksymalna liczba bajtów wysyłanych
Funkcja zwraca: > 0 – PID procesu który nadał komunikat, 1 - błąd

Warunkowy odbiór komunikatu
pid_t Creceive(pid_t pid, void * msg, unsigned rbytes)
Funkcja nie powoduje zablokowania procesu bieŜącego gdy brak
komunikatów.
pid > 0 - PID procesu nadającego
0 - odbiór od wszystkich procesów
rmsg adres bufora danych odbieranych
rbytes max. liczba bajtów odbieranych

Funkcja zwraca:
> 0 – PID procesu który nadał komunikat
- 1 - błąd

Wymiana komunikatów
Na poniŜszym rysunku za pomocą sieci Petriego przedstawiono wymianę komunika-
tów pomiędzy procesami P1 i P1.

Nazwy
Proces  P1  moŜe  wysłać  komunikat  do  P2  o  ile  zna  jego  PID.  Bez  dodatkowych  me-
chanizmów  tylko  procesy  będące  w  relacji  macierzysty  /  potomny  mogą  się  w  ten
sposób komunikować. Aby umoŜliwić  komunikowanie się  procesów niezwiązanych, w
systemie QNX wprowadzono mechanizm  nazw. Procesy mogą  rejestrować  swoje na-
zwy  w  systemie.  Nazwy  są  zwykłymi  łańcuchami. Inne procesy mogą  zwrócić  się  do
systemu o PID procesu podając jego nazwę. Mechanizm ten działa takŜe przez sieć  i
nosi nazwę  lokalizacji.

Rejestracja nazwy
Proces rejestruje się  poprzez wykonanie funkcji:
int qnx_name_attach(nid_t nid, char * name)
nid Identyfikator węzła na którym nazwa jest rejestrowana (0 – węzeł  bieŜący)
name Nazwa rejestrowanego procesu
Gdy nazwa zaczyna się  od znaku / jest widoczna w całej sieci. Nazwa moŜe być  teŜ
zarejestrowana na określonym węźle. Funkcja zwraca:
> 0 - identyfikator nazwy (ang. name ID) – liczba typu int uŜywana w innych
funkcjach.
-1 - gdy rejestracja się  nie udała.

Lokalizacja nazwy
PID procesu o znanej nazwie uzyskuje się poprzez wywołanie funkcji:
pid_t qnx_name_locate(nid_t nid, char * name, unsigned
size, NULL)
nid Identyfikator węzła na którym nazwa jest rejestrowana (0 – węzeł bieŜący)
name Nazwa lokalizowanego procesu

size Długość  komunikatu który będzie przesyłany pomiędzy procesami
Funkcja zwraca:
> 0 - identyfikator procesu
-1 - gdy lokalizacja się  nie udała.
Gdy nid = 0 proces będzie lokalizowany najpierw na bieŜącym węźle a potem w sie-
ci. Gdy nid # 0 proces będzie lokalizowany tylko na węźle o numerze nid. Gdy loka-
lizowany  proces  leŜy  na  innym  węźle  automatycznie  tworzone  jest  połączenie  wirtu-
alne (ang. Virtual Circuit) pomiędzy węzłami.

Wyrejestrowanie nazwy
Nazwa kasowana jest się  poprzez wywołanie funkcji:
int qnx_name_detach(nid_t nid, int name_id)
nid Identyfikator węzła na którym nazwa jest kasowana (0 – węzeł  bieŜący)
name_id Identyfikator kasowanej nazwy – liczba zwracana przez funkcję
qnx_name_attach
Funkcja powoduje usuniecie nazwy o identyfikatorze name_id z bazy nazw.
Funkcja zwraca:
0 - gdy wyrejestrowanie się  udało
-1 - gdy operacja się  nie udała.

11. Mechanizm

przesyłania depozytów

w systemie

QNX.

Funkcje

qnx_proxy_attach, Trigger. Depozyt jako mechanizmu reagowania na zda-
rzenia z wielu źródeł.

Depozyty
Depozyty  są  rodzajem  komunikatów  o  ustalonej  treści  (zwykle  zerowej)  nie  wyma-
gającym  potwierdzenia.  W  aplikacjach  współbieŜnych  potrzebny  jest  często  nieblo-
kujący  mechanizm  powiadamiania  procesów  o  pewnych  zdarzeniach.  W  systemie
QNX  taki  mechanizm  jest  zaimplementowany  i  nosi  tam  nazwę   depozytu  (ang.
proxy).  Depozyty  mogą  być  przesyłane  przez  sieć. Depozyty są  stosowane w nastę-
pujących sytuacjach:
1. Proces chce powiadomić  inny proces o zdarzeniu, ale nie moŜe sobie pozwolić  na
zablokowanie się.
2.  Proces  chce  powiadomić  inny  proces  o  zdarzeniu,  ale  nie  potrzebuje  informacji
zwrotnej.
3. UŜywane są  w procedurach obsługi przerwań  (ang. interrupt handler).

Depozyt tworzony jest za pomocą  funkcji:
int qnx_proxy_attach(pid_t pid, char * data, int nbytes,
int priority)
pid PID procesu będącego właścicielem depozytu (0 gdy jest to proces wykonujący
funkcję).
data Zawartość  depozytu – zwykle 0.
nbytes Długość  informacji zawartej w depozycie – zwykle 0;
priority Priorytet depozytu (gdy –1 – będzie on taki jak priorytet procesu wykonu-
jącego funkcję).
Funkcja zwraca:
> 0 - identyfikator depozytu
-1 - błąd

Wysłanie depozytu:
Depozyt wysyłany jest za pomocą funkcji:
pid_t Trigger(pid_t proxy)
proxy Identyfikator depozytu – wartość zwracana przez funkcję
qnx_proxy_attach.
Wykonanie funkcji Trigger powoduje wysłanie depozytu proxy do procesu który jest
jego właścicielem.
Funkcja zwraca:
> 0 - identyfikator procesu który jest właścicielem depozytu
-1 - błąd

Odbiór depozytu:
Odbiór depozytu następuje poprzez wykonanie funkcji Receive. JeŜeli proces jest
zablokowany na funkcji Receive i do procesu tego zostanie dostarczony depozyt,
proces ulega odblokowaniu i funkcja Receive zwraca identyfikator depozytu.

Kasowanie depozytu
Depozyt jest kasowany za pomocą funkcji:
int qnx_proxy_detach(pid_t proxy)
proxy Identyfikator kasowanego depozytu – wartość zwracana przez funkcję
qnx_proxy_attach.
Funkcja zwraca:
0 – sukces
-1 błąd

Własności depozytów:
1. Wysłane depozyty nie wymagają  potwierdzenia.
2.  Nieodebrane  depozyty  są  kolejkowane  (w  ilości  do  65535).  Zostaną  odebrane
przy kolejnym wywołaniu funkcji Receive.
3. KaŜdy depozyt naleŜy do procesu który go utworzył.
4.  Depozyt  moŜe  być  wysłany  z  dowolnego  procesu,  ale  zawsze  trafia  do  procesu
który jest jego właścicielem.

12. Tworzenie aplikacji klient/serwer, serwer stanowy–bezstanowy, se-
kwencyjny-współbieŜny.

Architektura  klient  /  serwer  to  sposób  przetwarzania  informacji  gdzie  proces  Ŝą-
dający  usług  i  proces  dostarczający  usług  są  wyodrębnione.  Jest  ona  szczególnie
wygodna w systemach sieciowych i rozproszonych.
Klient – proces potrzebujący pewnej usługi i zlecający ja serwerowi.
Serwer – proces dostarczający usługi zlecanej przez klienta.
Procesy  klientów  i  serwerów  mogą  być  zlokalizowane  na  tych  samych  bądź  innych
komputerach. Proces serwera moŜe być  klientem serwera innej usługi.

Rodzaje architektury klient serwer:
1. Serwer połączeniowy / bezpołączeniowy
2. Serwer sekwencyjny / współbieŜny
3. Serwer stanowy / bezstanowy

Prosty serwer sekwencyjny w systemie QNX
Serwer sekwencyjny to serwer składający się z jednego tylko procesu. W danej
chwili moŜe on obsługiwać tylko jednego klienta.

Kroki klienta:
1. Lokalizacja serwera
2. Utworzenie komunikatu specyfikującego Ŝądanie
3. Wysłanie komunikatu do procesu serwera
4. Odbiór odpowiedzi.
5. Wykorzystanie wyniku.

Kroki serwera:
1. Rejestracja nazwy własnej w serwerze nazw.
2. Odbiór zlecenia.
3. Identyfikacja zlecenia
4. Realizacja zlecenia.
5. Wysłanie odpowiedzi do klienta

Zlecenia do serwera musza być kolejkowane.

Metody kolejkowania nie obsłuŜonych klientów.

Serwer iteracyjny / współbieŜny

Serwer iteracyjny
Serwer iteracyjny – serwer zdolny do obsługi jednego zlecenia klienta w danym od-
cinku czasu
t – czas obsługi jednego zlecenia
N – liczba zleceń klientów
T - Czas obsługi N zleceń

Serwer współbieŜny
Serwer współbieŜny – serwer zdolny do współbieŜnej obsługi zleceń wielu
klientów. Składa się z pewnej liczby procesów lub wątków realizujących
zlecenia klientów.

- PID nie obsłuŜonego klienta umieszcza się  w kolejce KQ.
4. Gdy do procesu SG przychodzi komunikat od procesu usługowego Sj Ŝe zakończył
on obsługę  klienta Ki to:
- PID procesu obsługowego Sj dodawany jest do kolejki SQ.
- PID procesu klienta Ki usuwany jest z kolejki KQ.
- Wynik dostarczony przez proces usługowy odbierany jest z bufora funkcji Receive.
-  Procesowi  klienta  Ki  udzielana  jest  odpowiedź  za  pomocą  funkcji  Reply  a  wyniki
przekazywane jako parametry .
- Proces klienta Ki jest odblokowany na czym kończy się  jego obsługa.

Serwer bezstanowy / stanowy

Serwer  bezstanowy  (ang.  stateless  server)  -  serwer,  który  nie  przechowuje  Ŝad-
nych informacji o kliencie. Zwracając się  do serwera bezstanowego, klient musi kaŜ-
dorazowo określić  komplet informacji dotyczących usługi.
Serwer  stanowy  (ang.  Stateful  server)  –  serwer  przechowuje  informacje  o  klien-
cie. Są  dwa typy informacji przechowywanej przez serwer:
- Informacja globalna
- Informacja o stanie sesji

Informacja  globalna  –  informacja  przechowywana  przez  cały  okres  aktywności
serwera.
Informacja o stanie sesji (ang. Session state information)
Dla  pewnych  protokołów  i  aplikacji  serwer  musi  przechowywać  pewne  informacje  o
stanie sesji. Informacja o stanie sesji obejmuje:
1. Nazwę  pliku,
2. bieŜący numer bloku,
3. rodzaj akcji (pobieranie, wysyłanie)
W serwerze bezstanowym informacja o stanie sesji przechowywana jest u klienta. W
serwerze stanowym informacja o stanie sesji przechowywana jest w serwerze.

Protokół FTP – serwer bezstanowy

Protokół FTP – serwer stanowy

13. Komunikacja przez wspólną pamięć w systemie Unix System V i POSIX.

Komunikacja przez pamięć  dzieloną
Metoda komunikacji przez wspólną  pamięć  moŜe być  uŜyta gdy procesy wykonywa-
ne są  na maszynie jednoprocesorowej lub wieloprocesorowej ze wspólną  pamięcią.

Procesy
Procesy  mają  rozdzielone  segmenty  danych  -  modyfikacje  wykonane  na  danych  w
jednym procesie w Ŝaden sposób nie przenoszą  się  do procesu drugiego. Aby proce-
sy mogły mieć  wspólny dostęp do tych samych danych naleŜy:
1. Utworzyć  oddzielny segment pamięci.
2. Udostępnić  dostęp do segmentu zainteresowanym procesom.
Gdy  procesy  komunikują  się  przez wspólną  pamięć  spełniony powinien być  warunek
wzajemnego  wykluczania  procesów.  Aby  warunek  ten  był  spełniony  naleŜy  zastoso-
wać  dodatkowe metody synchronizacji procesów korzystających ze wspólnej pamię-
ci.

Wątki
Wątki z natury dzielą obszar danych. Zmienne zadeklarowane jako zmienne
globalne będą dostępne dla wątków.

Funkcje operujące na wspólnej pamięci – IPC UNIX System V

Klucze mechanizmów IPC
Mechanizmy  komunikacji  międzyprocesowej  (kolejki  komunikatów,  semafory,  seg-
menty  pamięci  dzielonej)  wymagają   identyfikacji  tych  obiektów  w  obrębie  poje-
dynczego komputera. Identyfikacja ta odbywa się  za pomocą  kluczy (ang.key).

Do otrzymywania unikalnych kluczy generowanych na podstawie ścieŜki do pliku
słuŜy funkcja ftok.
key_t ftok(char *path, int id);
Gdzie:
path ScieŜka do pliku
id Numer identyfikacyjny
Funkcja zwraca klucz zaleŜny od parametrów path, id.

Tworzenie segmentu wspólnej pamięci
JeŜeli mamy korzystać z segmentu pamięci wspólnej naleŜy go najpierw utworzyć.
Segment tworzy się przy pomocy funkcji shmget.
int shmget(key_t key, size_t size, int flags)
key Klucz identyfikujący semafor
size Minimalny rozmiar obszaru wspólnego
flags Flagi specyfikujące tryb tworzenia i prawa dostępu (IP_CREAT,
IPC_EXCL)
Funkcja zwraca:
> 0 identyfikator segmentu wspólnego
-1 błąd

Dołączenie segmentu pamięci
Po  utworzeniu  segment  pamięci  wspólnej  musi  być  udostępniony  w  przestrzeni  ad-
resowej  procesu  który  ma  go  uŜywać.  Udostępnienie  to  następuje  przez  wykonanie
funkcji shmat.
void *shmat(int id, void addr , int flags)
Gdzie:
Id identyfikator segmentu zwracany przez funkcję  shmget
addr Zmienna specyfikująca adres obszaru wspólnego
flags Flagi specyfikujące tryb dostępu i przydzielania adresu
Funkcja zwraca:
> 0 - adres przydzielonego segmentu wspólnego
-1 - błąd

Gdy  wartość  zmiennej addr jest równa NULL system sam nada wartość  adresowi po
którym  widziany  jest  dołączany  segment  pamięci.  Gdy  nie  jest  równy  zeru  działanie
funkcji  zaleŜy  od  ustawienia  flag.  Gdy  flaga  SHM_RND  jest  ustawiona  system  przyj-
mie adres pod którym ma być  widziany segment wspólny jako addr ale zaokrągli go
do najbliŜszej strony. Gdy flaga  SHM_RND  jest wyzerowana system ustali adres pod
którym  ma  być  widziany  segment  wspólny  jako  dokładna  wartość  addr.  Inną  flagą
mającą  tu  zastosowanie  jest  flaga  SHM_RDONLY.  Gdy  jest  ona  ustawiona  segment
wspólny nadaje się  tylko do odczytu.

Odwzorowanie segmentu pamięci dzielonej w przestrzeni adresowej proce-
su

Dołączony  za  pomocą   funkcji  shmat  segment  pamięci  wspólnej  moŜna  odłączyć
uŜywając funkcji shmdt.
int shmdt(void *addr)
Parametr addr jest wartością  zwróconą  przez funkcję  shmat.
Funkcja shmdt zwraca:
0 gdy wykona się  poprawnie
–1 w gdy wystąpi błąd.

Funkcje operujące na wspólnej pamięci – standard Posil

Standard Posix 1003.4 - funkcje pozwalające na tworzenie i udostępnianie segmen-
tów pamięci: shm_open, ltrunc, mmap, munmap ,mprotect, shm_unlink.

Tworzenie segmentu pamięci
Tworzenie segmentu pamięci podobne jest do tworzenia pliku – segment jest pli-
kiem specjalnym.
int shm_open(char *name, int oflag, mode_t mode )
name Nazwa segmentu pamięci
oflag Flaga specyfikująca tryb utworzenia (jak dla plików), np. O_RDONLY,
O_RDWR, O_CREAT
mode Specyfikacja trybu dostępu (jak dla plików).
Gdy funkcja zwraca liczbę nieujemną jest to uchwyt identyfikujący segment w pro-
cesie. Segment widziany jest jako plik specjalny w katalogu /dev/shmem.

Ustalanie rozmiaru segmentu pamięci
off_t ltrunc(int fdes, off_t offset, int whence)
fdes Uchwyt segmentu zwracany przez poprzednią  funkcję  shm_open.
offset Wielkość  segmentu w bajtach.
whence W tym przypadku stała SEEK_SET
Funkcja zwraca wielkość  segmentu lub –1 gdy błąd.

Odwzorowanie segmentu pamięci wspólnej w obszar procesu,
void *mmap(void * addr, size_t len, int prot, int flags,
int fdes, off_t off)
addr Zmienna wskaźnikowa w procesie której wartość będzie przez funkcję

zainicjowana. MoŜe być  0.
len Wielkość  odwzorowywanego obszaru.
prot Specyfikacja dostępu do obszaru opisana w <sys/mman.h>. MoŜe być
PROT_READ | PROT_WRITE
flags Specyfikacja uŜycia segmentu, np. MAP_SHARED.
fdes Uchwyt segmentu wspólnej pamięci.
off Początek obszaru we wspólnej pamięci (musi to być  wielokrotność  strony 4K)
Funkcja zwraca adres odwzorowanego obszaru lub –1 gdy błąd.

Odłączenie się  od segmentu pamięci
shm_unlink(char *name)
name Nazwa segmentu pamięci.
KaŜde wywołanie tej funkcji zmniejsza licznik udostępnień  segmentu. Gdy osiągnie
on wartość  0 czyli segment nie jest uŜywany juŜ  przez Ŝaden proces, segment jest
kasowany.

Schemat utworzenia i udostępnienia segmentu

Sposób wykorzystania wspólnej pamięci do komunikacji między procesami

Proces macierzysty P1:
1. Deklaruje zmienną wskaźnikową buf.
2. Tworzy segment pamięci o nazwie „Bufor” - funkcja shm_open.
3. Ustala jego wielkość na B_SIZE - funkcją ltrunc.

14. Wzajemne wykluczanie, sekcja krytyczna, niesystemowe i systemowe

metody ochrony sekcji krytycznej.

Problem wzajemnego wykluczania i warunki jego rozwiązania

Operacja atomowa
Sekwencja  jednego  lub wielu działań  elementarnych  które nie  mogą  być  przerwane.
Wykonuje  się  w  całości  albo  wcale.  Działania  pośrednie  nie  mogą  być  obserwowane
przez inny proces.
Operacja atomowa drobnoziarnista (ang. fine grained)
Operacja wykonywana przez pojedynczą  atomową  instrukcję  kodu maszynowego.
Operacja atomowa gruboziarnista (ang. coarse grained)
Sekwencja operacji drobnoziarnistych której zapewniono niepodzielność  innymi me-
todami.

Zakładamy Ŝe:
- Odczyt z pamięci komórki o adresie X jest operacją atomową
- Zapis do pamięci komórki o adresie X jest operacją atomową

Instrukcje procesów P1 i P2 wykonywane w trybie przeplotu

Nie moŜemy poczynić Ŝadnych załoŜeń dotyczących momentów przełączenia pro-

cesów P1 i P2

Nie da się określić wyniku działania powyŜszych procesów.

Wynik  działania  aplikacji  współbieŜnej  nie  moŜe  być  uzaleŜniony  od  sposobu  przełą-
czania  procesów.  Musi  być  prawidłowy  dla  wszystkich  moŜliwych  przeplotów.  Gdy
procesy  współbieŜne  do  wzajemnej  komunikacji  uŜywają  wspólnej  pamięci,  wyniki
takiej  komunikacji  mogą  okazać  się  przypadkowe.  Prawidłowa  komunikacja  współ-
bieŜnych  procesów  przez  wspólny  obszar  pamięci  wymaga  dotrzymania  warunku
wzajemnego wykluczania.

Wzajemne wykluczanie - wymaganie aby ciąg operacji na pewnym zasobie (zwy-
kle pamięci) był wykonany w trybie wyłącznym przez tylko jeden z potencjalnie wie-
lu procesów.

Sekcja krytyczna – ciąg operacji na pewnym zasobie (zwykle pamięci) który musi
wykonany w trybie wyłącznym przez tylko jeden z potencjalnie wielu procesów. Przy
wejściu do sekcji proces wykonuje

protokół wejścia w którym sprawdza czy moŜe

wejść  do  sekcji  krytycznej.  Po wyjściu  z  sekcji  wykonuje  protokół  wyjścia  aby po-
informować  inne  procesy  Ŝe  opuścił  juŜ  sekcję  krytyczną  i  inny  proces  moŜe  ją  za-
jąć. W danej chwili w sekcji krytycznej moŜe przebywać  tylko jeden proces.

Model programowania z sekcją lokalną i sekcją krytyczną

Rozwiązanie problemu wzajemnego wykluczania musi spełniać  następujące warunki:
1. W sekcji krytycznej moŜe być  tylko jeden proces to znaczy instrukcje z sekcji kry-
tycznej nie mogą  być  przeplatane.
2. Nie moŜna czynić  Ŝadnych załoŜeń  co do względnych szybkości wykonywania pro-
cesów.
3.  Proces  moŜe  się  zatrzymać  w  sekcji  lokalnej  nie  moŜe  natomiast  w  sekcji  kry-
tycznej. Zatrzymanie procesu w sekcji lokalnej nie moŜe blokować  innym procesom
wejścia do sekcji krytycznej.
4. KaŜdy z procesów musi w końcu wejść  do sekcji krytycznej.

Niesystemowe metody wzajemnego wykluczania

Blokowanie przerwań
Metoda  zapewnienia  wzajemnego  wykluczania  poprzez  blokowanie  przerwań  opiera
się  na fakcie Ŝe proces moŜe być  przełączony przez:
1. Przerwanie które aktywuje procedurę  szeregującą
2.  Wywołanie  wprost  procedury  szeregującej  lub  innego  wywołania  systemowego
powodującego przełączenie procesów.
Gdy Ŝaden z powyŜszych czynników nie zachodzi procesy nie mogą  być  przełączane.

Metoda ochrony sekcji krytycznej poprzez blokowanie przerwań  opiera się  na nastę-
pujących zasadach:
1 Protokół  wejścia do sekcji – następuje zablokowanie przerwań.
2. Protokół  wyjścia z sekcji – następuje odblokowanie przerwań.

3. Wewnątrz sekcji krytycznej nie wolno uŜywać wywołań systemowych mogących
spowodować przełączenie procesów.

Ochrona sekcji krytycznej przez blokowanie przerwań
Wady metody:
1. Przełączanie wszystkich procesów jest zablokowane.
2. System nie reaguje na zdarzenia zewnętrzne co moŜe spowodować utratę da-
nych.
3. Skuteczne w maszynach jednoprocesorowych
Zastosowanie metody:
Wewnątrz systemu operacyjnego do ochrony wewnętrznych sekcji krytycznych.

Metoda zmiennej blokującej (nieprawidłowa)
Metoda polega na uŜyciu zmiennej o nazwie lock. Gdy zmienna lock = 0 sekcja jest
wolna,  gdy  lock  =  1  sekcja  jest  zajęta.  Proces  przy  wejściu  testuje  wartość   tej
zmiennej.  Gdy  wynosi  ona  1  to czeka,  gdy  zmieni  się  na  0  wchodzi do  sekcji usta-
wiając  wartość  zmiennej  lock  na  1.  Metoda  jest  niepoprawna,  gdyŜ  operacja  testo-
wania wartości zmiennej lock i ustawiania jej na 1 moŜe być  przerwana (nie jest
niepodzielna).  Dodatkową  wadą  metody  jest  angaŜowanie  procesora  w  procedurze
aktywnego czekania.

Wykorzystania wsparcia sprzętowego do ochrony sekcji krytycznej
Wiele mikroprocesorów zawiera instrukcje wspierające sprzętowo
wzajemne wykluczanie. Są  to instrukcje typu
1. Sprawdź  i Przypisz - (ang. TAS -Test And Set)
2. Sprawdź  i Zamień  - (ang. CAS – Compare And Swap)
3. Zamień  - (ang. EXCH - Exchange).
Pozwalają  one wykonać  kilka operacji w sposób nieprzerywal

Sprzętowe  wsparcie  ochrony  sekcji  krytycznej  w  systemach  multiproceso-
rowych
Gdy  wiele  procesorów  odczytuje  w  pętli  tę  samą  lokację  pamięci  zapewne  znajduje
się  ona  w  pamięci  podręcznej.  Sprzętowy  mechanizm  kontroli  pamięci  musi  dbać  o
spójność  pamięci podręcznej i głównej.
Pamięć  przepisywalna (ang. Write Througt)
1.  Gdy  procesor  czyta  dane  słowo  z  pamięci  operacyjnej,  strona  zostaje  pobrana
równieŜ  do pamięci podręcznej.
2. Gdy procesor zapisuje słowo znajdujące się  w pamięci podręcznej to:
- następuje zapis w pamięci głównej
- pamięci podręczne przechowujące zapisywaną  lokację  uniewaŜniają  zapis.
Pamięć  podglądająca (ang Snooping Cache)
Jednostka  sterująca  pamięcią  podręczną  podgląda  magistrale.  Gdy  stwierdzi Ŝe  do-
konano zapisu do pamięci operacyjnej lokacji pamiętanej w tej pamięci to aktualizu-
je swój zapis.

Programowe metody zapewnienia wzajemnego wykluczania
We  wczesnych  procesorach  nie  było  wsparcia  sprzętowego  dla  wzajemnego  wyklu-
czania.  Stąd  wzajemne  wykluczanie  realizowano  w  sposób  wyłącznie  programowy.
Obecnie metody te mają  znaczenie tylko teoretyczne i historyczne. Wymienić  moŜna

tu algorytm Dekkera, algorytm Petersona, algorytm piekarniczy.

Systemowe metody zapewnienia wzajemnego wykluczania

Niesystemowe metody stosowane są  rzadko i ich znaczenie jest raczej teoretyczne.
Powody:
1. Prawie zawsze tworzymy aplikacje działające w środowisku systemu operacyjne- go
który z reguły dostarcza mechanizmów zapewnienia wzajemnego wykluczania.
2.  Realizacja  metod  wzajemnego  wykluczania  polega  na  zawieszeniu  pewnych  pro-
cesów  a  wznowieniu  innych.  System  operacyjny  w  naturalny  sposób  zapewnia  takie
mechanizmy.  Proces  zawieszony  nie  wykonuje  czekania  aktywnego  a  zatem  nie  zu-
Ŝywa czasu procesora.
3.  Metody  systemowe  są  znacznie  prostsze  i  powiązane  z  innymi  mechanizmami  i
zabezpieczeniami.  Przykładowo  awaryjne  zakończenie  się  procesu  w  sekcji  krytycz-
nej odblokowuje tę  sekcję. MoŜna teŜ  narzucić  maksymalny limit czasowy oczekiwa-
nia na wejście do sekcji krytycznej (ang. Timeout).
Z niesystemowych metod wzajemnego wykluczania praktycznie stosowane są  meto-
dy:
1. Wirujące blokady (ang. Spin Locks) wykorzystujące sprzętowe wsparcie w postaci
instrukcji  sprawdź  i  przypisz  oraz  zamień.  Stosuje  się  je  do  synchronizacji  wątków
ze względu na mały narzut operacji systemowych.
2.  Blokowanie  przerwań   –  do  ochrony  wewnętrznych  sekcji  krytycznych  systemu
operacyjnego.

Wzajemne wykluczanie poprzez obiekty typu mutex
Mechanizm  zapewniających  wzajemne  wykluczanie  zaimplementowny  jest  w  wielu
systemach  operacyjnych.  W  systemach  standard  Posix  mechanizm  ten  nosi  nazwę
mutex.  Jest  to  skrót  od  angielskiego  terminu  Mutual  Exclusion.  PoniŜej  opisano  im-
plementację  dotyczącą  wątków POSIX z biblioteki Pthreads.

Tworzenie obiektu typu mutex
int mutex_init(mutex_t*mutex, mutexattr_t* attr )
mutex Obiekt typu mutex
attr Atrybuty określające zachowanie obiektu. Gdy NULL atrybuty zostaną przyjęte
domyślne Wykonanie funkcji pozostawia zmienną mutex w stanie niezablokowanym.

Zablokowanie sekcji krytycznej
int mutex_lock( mutex_t* mutex )
mutex Obiekt typu mutex zainicjowany poprzednio przez funkcję  mutex_init
Gdy  przynajmniej  jeden  proces  wykonał   wcześniej  funkcję   mutex_lock  zmienna
mutex  oznaczona  będzie  jako  zajęta.  Proces  bieŜący  wykonujący  tę  funkcję  zosta-
nie wstrzymany

Zwolnienie sekcji krytycznej
Proces opuszczający sekcję krytyczną powinien poinformować o
tym system (wykonać protokół wyjścia).
int mutex_unlock( pthread_mutex_t* mutex )
mutex Obiekt typu mutex

Gdy jakieś procesy czekają na wejście do sekcji to jeden z nich będzie odblokowany
i wejdzie do sekcji. Gdy brak takich procesów to sekcja zostanie oznaczona jako
wolna.

Skasowanie obiektu typu mutex
int mutex_destroy( pthread_mutex_t* mutex );

Podstawowy schemat ochrony sekcji krytycznej przy uŜyciu zmiennej mutex:

mutex_t mutex ; // Deklaracja zmiennej mutex
mutex_init(&mutex,NULL); // Inicjalizacja zmiennej
do {

............
// Zablokowanie sekcji krytycznej
mutex_lock( &mutex );
Sekcja krytyczna
// Zwolnienie sekcji krytycznej
unlock( &mutex );

} while(1),

Ochrona sekcji krytycznej przez obiekt typu mutex

15. Semafory i ich zastosowanie. Semafory Unix System V i POSIX. Sposoby
implementacji semaforów.

Semafory
Semafor jest obiektem abstrakcyjnym słuŜącym do kontrolowania dostępu do ogra-
niczonego zasobu. Semafory są  szczególnie przydatne w środowisku gdzie wiele
procesów lub wątków komunikuje się  przez wspólną  pamięć.
Definicja semafora
Semafor S jest obiektem abstrakcyjnym z którym związany jest licznik L zasobu
przyjmujący wartości nieujemne. Na semaforze zdefiniowane są  atomowe operacje
sem_init, sem_wait i sem_post. Podano je w poniŜszej tabeli.

Inicjacja semafora - procedura sem_init
Operacja inicjacji semafora S - sem_init(S,N):
1. Alokacja pamięci na strukturę  semafora.
2. Inicjacja pól struktury *S.
3. Inicjacja licznika L semafora na wartość  początkową  N.
Procedura sem_wait
Kroki procedury sem_wait(S)podane są  poniŜej:
1. Zablokować  przerwania.
2. Zmniejsz licznik L semafora S o 1.
3. Gdy licznik L < 0 to:
- usunąć  proces bieŜący z kolejki procesów gotowych
- umieścić  deskryptor usuniętego procesu w kolejce S->Sem_waiting semafora S
- przekazać  sterowanie do systemu operacyjnego
4. Odblokować  przerwania.
Operacja musi sem_wait być  atomowa. Zablokowanie przerwań  jest metodą  ochro-
ny sekcji krytycznej.
Procedura sem_post
Kroki procedury sem_post(S)podane są  poniŜej:
1. Zablokować  przerwania.
2. Zwiększ licznik L semafora S o 1.
3. Gdy licznik L <= 0 to:
- Usunąć  pierwszy proces z kolejki semafora
- Umieścić  deskryptor usuniętego procesu w kolejce procesów gotowych.
- Przekazać  sterowanie do procedury szeregującej systemu operacyjnego
4. Odblokować  przerwania.
Operacja musi sem_post być  atomowa.

Istotne cechy semafora:
1. Semafor nie jest liczbą całkowitą na której moŜna wykonywać operacje arytme-
tyczne.
2. Operacje na semaforach są operacjami atomowymi.

Niezmiennik semafora
Aktualna warto

ść

licznika L semafora S spełnia nast

puj

ce warunki:

1. Jest nieujemna czyli: L >= 0
2. Jego warto

ść

wynosi: L= N - Liczba_operacji(sem_wait) + Liczba_operacji(sem_post).

(N jest warto

pocz

tkow

licznika).

Semafor binarny
W semaforze binarnym wartość  licznika przyjmuje tylko dwie wartości: 0 i 1.
Rodzaje semaforów
1. Semafor ze zbiorem procesów oczekujących (ang. Blocked- set Semaphore) – Nie
jest określone który z oczekujących procesów ma być  wznowiony.
2.  Semafor  z  kolejką  procesów  oczekujących  (ang.  Blocked-  queue  Semaphore)  –
Procesy oczekujące na semaforze umieszczone są  w kolejce FIFO.
Uwaga!
Pierwszy typ semafora nie zapewnia spełnienia warunku zagłodzenia.

Przykład zastosowania semafora do ochrony sekcji krytycznej

Implementacja semaforów - kanoniczne operacje synchronizacyjne
Kanoniczne operacje synchronizacyjne Suspend i Resume:

Suspend(Queue K) – zawieszenie procesu bieŜącego w kolejce K
Kroki procedury Suspend
Stan procesu bieŜącego zapamiętywany jest w jego deskryptorze.
1. Deskryptor usuwany jest z kolejki procesów gotowych i umieszczany w kolejce K.
2. Uruchamiana jest procedura szeregująca która wybiera do wykonania pewien
proces z kolejki procesów gotowych.

Resume(Queue K) - Wznowienie pierwszego procesu z kolejki K
Kroki procedury Resume
1. Deskryptor pierwszego procesu z kolejki K jest przenoszony z tej kolejki do kolej-
ki procesów gotowych.
2. Uruchamiana jest procedura szeregująca która wybiera do wykonania pewien
proces z kolejki procesów gotowych.

Nieraz niezbędna jest procedura Resume(K,P) – wznowienie procesu P (P –
PID procesu) z kolejki K.

Semafory w IPC UNIX System V
Semafory w IPC UNIX System V tworzą tablicę. Funkcje dotyczące semaforów ope-

rują na całych tablicach. Z semaforem związane są następujące liczniki:

semval

Wartośc licznika semafora

sempid

PID procesu który ostatnio wykonywał operację na semaforze

semncnt

Liczba procesów czekających aŜ semafor osiągnie wartość
większą niŜ jego bieŜąca wartość

semzcnt

Liczba procesów czekających aŜ semafor osiągnie wartość zero

Tablica semaforów w IPC UNIX System V

Klucze mechanizmów IPC
Mechanizmy  komunikacji  międzyprocesowej  (kolejki  komunikatów,  semafory,  seg-
menty  pamięci  dzielonej)  wymagają   identyfikacji  tych  obiektów  w  obrębie  poje-
dynczego  komputera.  Identyfikacja  ta  odbywa  się  za  pomocą  kluczy  (ang.  key).  Do
otrzymywania  unikalnych  kluczy  generowanych  na  podstawie  ścieŜki  do  pliku  słuŜy
funkcja ftok (opisana w pytaniu nr 13).

Tworzenie semafora
int semget(key_t klucz, int ile, int flagi)

Klucz

Klucz identyfikujący semafor

Ile

Liczba semaforów w tablicy

Flagi

Flagi specyfikujące tryb tworzenia i prawa dostępu

Funkcja zwraca:
> 0 identyfikator semafora -1 błąd
Funkcja sprawdza czy semafor o danym kluczu istnieje. Gdy nie to go tworzy. Gdy
istnieje to dalsze działanie zaleŜy od flag.
IPC_CREAT Utwórz semafor gdy nie istnieje. Gdy istnieje zwraca identyfikator
semafora.
IPC_EXCL Gdy semafor istnieje funkcja kończy się  błędem.
Flagi zawierają  informacje o:
1.  Sposobie tworzenia semafora (IPC_CREAT, IPC_EXCL)
2.  Prawa dostępu dla właściciela, grupy i innych

Ustawianie własności semafora
int semctrl(int semid, int num_sem, int command, semun ctl_arg )
Gdzie:

semid

Identyfikator semafora zwracany przez funkcję semget

semid

Identyfikator semafora zwracany przez funkcjęsemget

Struktura specyfikująca operację

num_sem

Liczba elementów w tablicy semaforów

num_sem

Numer semafora do którego odnosi się operacja

command

Polecenie specyfikujące działanie na semaforze

sem_un

Bufor z argumentami. Postać zaleŜy od pola command

Funkcja zwraca:
>= 0 – sukces
-1 – błąd

Operacje semaforowe
int semop(int semid, struct sembuf * op, size_n num_sem)
Gdzie:

Funkcja zwraca:
>= 0 – sukces
-1 – błąd
Flagi:
IPC_NOWAIT operacja nie będzie blokująca

SEM_UNDO po zako

czeniu procesu warto

ść

licznika wszelkich operacji semaforowych

dzie zniwelowana

Operacje które maj

wykonane na semaforze zale

Ŝą

od warto

ci pola sem_op w

sposób nast

puj

cy:

Pole sem_op ujemne

Gdy  pole  sem_op  jest  <  0  to  operacja  odpowiada  operacji  sem_wait.  Z  polem
sem_op  porównywany  jest  licznik  semafora  semval  a  działanie  zgodne  jest  z  poniŜ-
szą  tabelą:
Gdy:  semval + sem_op >= 0 semval = semval -sem_op
Gdy:   semval + sem_op < 0 Proces bieŜący jest blokowany do czasu gdy semval +
sem_op >= 0
Pole sem_op dodatnie
Gdy pole sem_op jest  > 0  to  operacja  odpowiada  operacji sem_post.  Wartość  pola
semval jest modyfikowana semval = semval + sem_op.
Gdy Ŝaden proces nie czeka na semaforze to nic sięnie dzieje.
Gdy  są  procesy  czekające  na  semaforze  to  sprawdzane  jest  czy  nowa  wartość  pola
semval  jest  wystarczająca  do  wznowienia  jakiegoś  czekającego  procesu.  Gdy  tak  to
jest on wznawiany.
Pole sem_op równe zero
Gdy pole sem_op jest = 0 działanie semafora zaleŜy od wartości pola semval.
Gdy semval jest równe zeru to nic się  nie dzieje.
Gdy  semval  jest  róŜne  od  zera  to  proces  bieŜący  blokuje  się  do  czasu  gdy  pole
semval będzie równe zeru.

NaleŜy  zauwaŜyć  Ŝe  funkcja  semop(...)  działa  na  tablicy  semaforów.  Pozwala  ona
niepodzielne  wykonanie  grupy  operacji  semaforowych  zgodnie  z  zasadą„wszystko
albo  nic”.  Proces  będzie  odblokowany  gdy  pozwalają  na  to  warunki  na  wszystkich
semaforach.

Semafory w standardzie POSIX
WyróŜnione są  tu dwa typy semaforów:
1.  Semafory nienazwane
2.  Semafory nazwane
Semafory  nienazwane  nadają  się  do  synchronizacji  wątków  w  obrębie  jednego  pro-
cesu.  Dostęp  do  semafora  nienazwanego  następuje  poprzez  jego  adres.  MoŜe  on
być  takŜe uŜyty do synchronizacji procesów o ile jest umieszczony w pamięci dzielo-
nej. Dostęp do semaforów nazwanych następuje poprzez nazwę. Ten typ semaforów
bardziej nadaje się  synchronizacji procesów niŜ  wątków. Semafory nienazwane dzia-
łają  szybciej niŜ  nazwane.

Semafory nienazwane
Dostęp do semafora nienazwanego następuje po adresie semafora. Stąd nazwa se-
mafor nienazwany.

Deklaracja semafora
Przed  uŜyciem  semafora  musi  on  być  zadeklarowany  jako  obiekt  typu  sem_t  a  pa-
mięć  uŜywana przez ten semafor musi zostać  mu jawnie przydzielona.
O ile semafor ma być  uŜyty w róŜnych procesach powinien być  umieszczony w wcze-
śniej zaalokowanej pamięci dzielonej.
1.  Utworzyć  segment pamięci za pomocą  funkcji shm_open.
2.  Określić  wymiar segmentu uŜywając funkcji ltrunc.
3.  Odwzorować  obszar pamięci wspólnej w przestrzeni danych procesu - mmap.
Inicjacja semafora - funkcja sem_init
Przed uŜyciem semafor powinien być  zainicjowany.
int sem_init(sem_t *sem, int pshared, unsigned value)
sem Identyfikator semafora (wskaźnik na strukturę  w pamięci )
pshared  Gdy  wartość  nie  jest  zerem  semafor  moŜe  być  umieszczony  w  pamięci
dzielonej i dostępny w wielu procesach value Początkowa wartość  semafora
Funkcja zwraca 0 gdy sukces, -1 gdy błąd.
Pobranie zasobu – funkcja sem_wait
Funkcja  ta  odpowiada  omawianej  wcześniej  operacji  sem_wait(S).  Prototyp
funkcji jest następujący:
int sem_wait(sem_t *sem)
sem Identyfikator semafora
Gdy  licznik  semafora  jest  nieujemny  funkcja  zmniejsza  go  o  1.  W  przeciwnym
przypadku  proces  bieŜący  jest  zawieszany.  Zawieszony  proces  moŜe  być  od-
blokowany  przez  procedurę   sem_sem_post  wykonaną   w  innym  procesie  lub
sygnał. Funkcja zwraca 0 gdy sukces, -1 gdy błąd.
Zwrot zasobu – funkcja sem_post
Funkcja  ta  odpowiada  omawianej  wcześniej  operacji  sem_post(S).  Prototyp
funkcji jest następujący:

int sem_post(sem_t *sem)
sem Identyfikator semafora
Jeśli jakikolwiek proces jest zablokowany na tym semaforze przez wykonanie
funkcji

sem_wait zostanie on odblokowany. Gdy brak procesów zablokowa-

nych licznik semafora zwiększany jest o 1.
Funkcja zwraca 0 gdy sukces, -1 gdy błąd.
Kasowanie semafora – funkcja sem_destroy
Semafor kasuje sięprzy pomocy funkcji:
int  sem_destroy(sem_t  *sem)  sem  Identyfikator  semafora  Gdy  jakieś  procesy
są  zablokowane  na  tym  semaforze,  zostaną  one  odblokowane  i  operacja
sem_destroy zakończy się  błędem.

Semafory nazwane
Semafory nazwane identyfikowane są w procesach poprzez ich nazwę. Na semafo-
rze nazwanym operuje się tak samo jak na semaforze nienazwanym z wyjątkiem
funkcji otwarcia i zamknięcia semafora.

Otwarcie semafora – funkcja sem_open
Aby uŜyć  semafora nazwanego naleŜy uzyskać  do niego dostęp poprzez funkcję:
sem_t * sem_open(const char *sem_name, int oflags, ... )
sem_name Nazwa semafora, powinna się  zaczynać  od znaku „/”.
oflags  Flagi  trybu  tworzenia  i  otwarcia:  O_RDONLY,  O_RDWR,  O_WRONLY.  Gdy
semafor jest tworzony naleŜy uŜyć  flagi O_CREAT
mode  Prawa  dostępu  do  semafora  –  takie  jak  do  plików.  Parametr  jest  opcjonalny.
value  Początkowa  wartość   semafora.  Parametr  jest  opcjonalny.  Funkcja  zwraca
identyfikator  semafora.  Semafor  widoczny  jest  w  katalogu  /dev/sem.  Funkcja  two-
rzy semafor gdy nie był on wcześniej utworzony i otwiera go.
Zamykanie semafora nazwanego – funkcja sem_close
Semafor zamyka się  poprzez wykonanie funkcji:
int sem_close(sem_t * sem)
Funkcja  zwalnia  zasoby  semafora  i  odblokowuje  procesy  które  są  na  nim  zabloko-
wane. Funkcja zwraca 0 gdy sukces, -1 gdy błąd.

16. Monitory i ich zastosowanie

Monitory
Semafor  nie  jest  mechanizmem  strukturalnym.  Aplikacje  pisane  z  uŜyciem  semafo-
rów są  podatne na błędy, np. brak operacji sem_post blokuje aplikację. Monitor jest
strukturalnym narzędziem synchronizacji.
Zmienne  i  działające  na  nich  procedury  zebrane  sąw  jednym  module.  Dostęp  do
zmiennych  monitora  moŜliwy  jest  tylko  za  pomocą   procedur  monitora.  W  danej
chwili  tylko  jeden  proces  wykonywać   moŜe  procedury  monitora.  Gdy  inny  proces
wywoła  procedurę  monitora  będzie  on  zablokowany  do  chwili  opuszczenia  monitora
przez pierwszy proces.
Istnieje  moŜliwość  wstrzymania  i  wznowienia  procedur  monitora  za  pomocą  zmien-
nych  warunkowych  (ang.  conditional  variables).  Na  zmiennych warunkowych  moŜna
wykonywać  operacje Wait i Signal.

Wait(c) -Wstrzymanie procesu bieŜącego wykonującego procedurę  monitora i wsta-
wienie go na koniec kolejki związanej ze zmienną  warunkową  c. JeŜeli jakieś  proce- sy
czekają  na wejście do monitora to jeden z nich będzie wpuszczony.
Signal(c)  –  Odblokowanie  jednego  z  procesów  czekających  na  zmiennej  warunko-
wej c. Gdy brak czekających procesów operacja nie daje efektów.
Jeśli nie jest to ostatnia instrukcja procedury monitora to proces wykonujący tę  ope-
rację   jest  wstrzymany  do  chwili  gdy  wznowiony  przezeń   proces  zwolni  monitor.
Wstrzymany tak proces moŜe przebywać  w:
1.  wejściowej kolejce procesów oczekujących na wejście do monitora
2.  kolejce  uprzywilejowanej  Które  rozwiązanie  zastosowano  zaleŜne  jest  od

implementacji.

Notempty(c) – Funkcja zwraca true gdy kolejka c jest niepusta, false gdy pusta.

Operacja signal jest bezpamięciowa (nie posiada licznika).

Kolejki monitora

Rozwiązanie problemu wzajemnego wykluczania za pomocą monitorów

monitor int z1,z2;
Pisz(int x1, int x2){

z1 = x1;
z2 = x2;

};
Czytaj(int *x1, int *x2){

*x1 := z1;
*x2 := z2;

};

Procedury Czytaj lub pisz wykonane będą w sposób wyłączny co wynika z definicji
monitora.

Monitory z powiadamianiem i rozgłaszaniem
W  omawianych  poprzednio  monitorach  Hoara’a  wystąpienie  operacji  Signal(c)  musi
spowodować   natychmiastowe  wznowienie  procesu  oczekującego  na  zmiennej  wa-
runkowej c.
Monitory z powiadamianiem
Inne rozwiązanie stosowane jest w monitorach z powiadamianiem.
Notify(c)  -  odblokowanie  jednego  z  procesów  związanej  ze  zmienną  warunkową  c
ale proces ten nie musi być  natychmiast zaszeregowany.
Monitory z rozgłaszaniem
NotifyAll(c)  -  odblokowanie  wszystkich  z  procesów  związanej  ze  zmienną  warun-
kową  c.  Proces  te  będą  konkurowały  o  dostęp  do  monitora.  Będą  zaszeregowane
gdy  będzie  to  moŜliwe.  W  monitorach  z  rozgłaszaniem  naleŜy  powtórnie  sprawdzić
warunek powodujący zablokowanie.

17. Kolejki komunikatów Unix System V i POSIX. Zastosowanie kolejek ko-
munikatów.

Kolejki komunikatów
Kolejka komunikatów Q posiada następujące własności:
1.  Posiada określoną  pojemność  N komunikatów (długość  bufora komunikatów).
2.  Posiada nazwę  którą  procesy mogą  zidentyfikować.
3.  Więcej niŜ  jeden proces moŜe czytać  lub pisać  z/do kolejki.

Przebieg operacji zapisu i odczytu zaleŜy od liczby n komunikatów w kolejce i od jej
pojemności Max.

Liczba komunikatów
n w kolejce Q

Wysłanie komunikatu
Send(Q,buf,size)

Odbiór komunikatu
Receive(Q,buf,size)

n = Max

Blokada lub sygnaliza-
cja błędu

Bez blokady

0< n < Max

Bez blokady

n = 0

Bez blokady

Blokada lub sygnalizacja błędu

Tworzenie kolejki komunikatów
W IPC Unix System V kolejki komunikatów słuŜą do komunikacji lokalnej. Identyfi-
kowane są przez klucz (podobnie jak w przypadku pamięci dzielonej i semaforów).
int msgget(key_t key, int flags)

Key Klucz identyfikujący semafor
Flags Flagi specyfikują:
- tryb tworzenia kolejki (IP_CREAT, IPC_EXCL)
-prawa dostępu (9 mniej znaczących bitów)

Wysyłanie komunikatów
Komunikaty wysyła się przy pomocy funkcji msgsnd zdefiniowanej jak poniŜej.
int msgsnd(int msgid, msgbuf* msg, size_t size, int flags)

msgid

Identyfikator kolejki (zwracany przez funkcję msgget)

msg

Adres bufora z wysyłanym komunikatem

size

Długość wysyłanego komunikatu

flags

Dopuszczalna tylko flaga IPC_NOWAIT

Funkcja zwraca:
0 - sukces
-1 - błąd

Komunikat powinien być strukturą zdefiniowaną poniŜej:

typedef struc {

int typ; // Typ komunikatu
char tekst[SIZE]; // Treść komunikatu

} msgbuf

Pole typ uŜywane jest w funkcji odbierającej do selekcji komunikatu.
Pole tekst moŜe być dowolną strukturą dowolnego rozmiaru.

Działanie funkcji msgsnd:
1. Gdy jest miejsce w kolejce komunikat msg jest dołączany do tej kolejki.
2. Gdy brak miejsca w kolejce proces bieŜący blokowany jest do czasu gdy miejsce

takie się pojawi. Gdy ustawiona jest flaga IPC_NOWAIT proces nie jest blokowa-
ny a wywołanie kończy się błędem.

Przy wysyłaniu sprawdzane są prawa dostępu do kolejki komunikatów. Gdy proces
nie ma stosownych praw do uŜycia kolejki wywołanie kończy się błędem.

Odbiór komunikatów
Komunikaty odbiera się przy pomocy funkcji msgrcv zdefiniowanej jak poniŜej.
int msgrcv(int msgid, msgbuf* msg, size_t size, long mtyp, int flags)

msgid

Identyfikator kolejki (zwracany przez funkcję msgget)

msg

Adres bufora na odbierany komunikat

size

Maksymalna długość odbieranego komunikatu

mtyp

Typ komunikatu

flags

Dopuszczalne są flagi IPC_NOWAIT, MSG_NOERROR

Funkcja zwraca: > 0 -liczba odebranych bajtów -1- błąd

Działanie funkcji msgrcv zaleŜy od:
1. Parametru mtyp – od parametru tego zaleŜy które komunikaty z kolejki będą

odebrane.

2. Stanu kolejki i flag – czynniki te decydują o synchronizacji procesów.

ZaleŜność  od parametru mtyp:
1.  Gdy mtyp > 0 z kolejki odbierane są  komunikaty danego typu (typ = mtyp).
2.  Gdy mtyp = 0 to odbierane są  wszystkie komunikaty
3.  Gdy  mtyp  <  0  odbierane  są  komunikaty  których  typ  jest  mniejszy  od  wartości

bezwzględnej parametru mtyp. Komunikaty odbierane są w kolejności od naj-
mniejszego pola typ do największego.

ZaleŜność od stanu kolejki:
1. Gdy w kolejce jest komunikat Ŝądanego typu proces bieŜący kopiuje ten komuni-

kat do bufora msg, usuwa go z kolejki i biegnie dalej.

2. Gdy w kolejce brak komunikatu Ŝądanego typu proces bieŜący ulega zablokowa-

niu do czasu gdy taki proces się pojawi. Gdy ustawiona jest flaga IPC_NOWAIT
proces nie jest blokowany a wywołanie kończy się błędem.

Gdy  w  kolejce  znajduje  się  komunikat  którego  długość  przekracza  parametr  size  to
działanie  zaleŜy  od  flagi MSG_NOERROR. Gdy  flaga  będzie  ustawiona  komunikat  zo-
stanie obcięty. Gdy flaga nie jest ustawiona wywołanie skończy się  błędem.

Testowanie i ustawianie parametrów kolejki
Do testowania i ustawiania parametrów kolejki słuŜy funkcja msgctl. NajwaŜniejsze
polecenia to testowanie statusu kolejki, ustawianie jej parametrów oraz usunięcie
całej kolejki z systemu.
int msgctl(int msgid, int command, struct msqid_ds *stat)

msgid

Identyfikator kolejki (zwracany przez funkcję msgget)

command

Polecenie

stat

Bufor na dane lub polecenia

Funkcja zwraca: > 0 -sukces -1- błąd

Testowanie statusu kolejki – polecenie IPC_STAT
Gdy pole command przyjmuje wartość IPC_STAT do struktury stat system kopiuje
informacje o stanie kolejki.

Ustawianie parametrów kolejki – polecenie IPC_SET
Aby ustawić  parametry kolejki komunikatów uŜywa siępolecenia IPC_SET. Zmieniać
moŜna:
  prawa dostępu (moŜna je teŜ  ustawić  przy tworzeniu)
  maksymalną  długość  kolejki.
Następuje to poprzez ustawienia pola msg_qbytes struktury stat. Domyślnie wartość
tego pola wynosi 16 KB.

Kasowanie kolejki komunikatów
Aby skasować kolejkę komunikatów uŜywa się polecenia IPC_RMID. Polecenie to
moŜe być wykonane przez administratora i właściciela kolejki.

Kolejki komunikatów - POSIX
Dwa procesy piszą do jednej kolejki:

Podstawowe cechy kolejek komunikatów:
1. W przypadku komunikatów komunikacja zachodzi bezpośrednio pomiędzy proce-

sami. Kolejki komunikatów są pośrednim obiektem komunikacyjnym widzianym
jako plik specjalny. Komunikujące się procesy nie muszą znać swoich identyfika-
torów.

2. Komunikaty odczytywane z kolejki zachowują strukturę– są separowane. W ko-

lejce mogą znajdować się komunikaty róŜnej długości. Własności tej nie mają ko-
lejki FIFO.

3. MoŜna zadać maksymalną długość kolejki komunikatów. Gdy zostanie ona prze-

kroczona, proces piszący do kolejki komunikatów będzie zablokowany.

4. Kolejka widziana jest w systemie plików jako plik specjalny. Operacje zapisu /

odczytu mogą być zabezpieczane prawami dostępu tak jak w przypadku plików
regularnych.

5. MoŜna testować status kolejki (np. liczbę komunikatów w kolejce). Nie jest to

moŜliwe w przypadku kolejek FIFO.

6. Komunikatom moŜna nadać priorytet. Komunikaty wyŜszym priorytecie będą

umieszczane na początku kolejki.

Zastosowanie  kolejki  komunikatów  jest  wygodnym  rozwiązaniem  w  następujących
przypadkach:
1.  Proces wysyłający komunikaty nie moŜe być  wstrzymany.
2.  Proces wysyłający komunikaty nie potrzebuje szybkiej informacji zwrotnej o tym

czy komunikat dotarł do adresata.

3. Zachodzi potrzeba przekazywania danych z procesu w którym one powsta-

ją(producent) do procesu w którym są one przetwarzane (konsument)

Podstawowe typy i plik nagłówkowy
Kolejka komunikatów jest typu mqd_t. Typ ten jest zdefiniowany w pliku nagłów-
kowym <mqueue.h>. Modyfikowalne atrybuty kolejki komunikatów zdefiniowane są
w strukturze mq_attr.

struct mq_attr {

long mq_maxmsg; // Maksymalna liczba komunikatów w kolejce long
mq_msgsize; // Maksymalna wielkość pojedynczego komunikatu long

mq_curmsg; // Aktualna liczba komunikatów w kolejce long mq_flags; // Flagi
long mq_sendwait; // Liczba procesów zablok. na operacji zapisu long
mq_recvwait; // Liczba procesów zablok. na operacji odczytu

}

Utworzenie i otwarcie kolejki komunikatów
Kolejkę  komunikatów tworzy się  za pomocą  funkcji:
mqd_t mq_open(char *name,int oflag,int mode,mq_attr*attr)
name Łańcuch identyfikujący kolejkę  komunikatów. Kolejki tworzone są  w katalogu
/dev/mqueue
oflag Tryb tworzenia kolejki. Tryby te są  analogiczne jak w zwykłej funkcji open. mode

Prawa dostępu do kolejki (r -odczyt, w -zapis) dla właściciela pliku, grupy i innych,
analogicznie jak w przypadku plików regularnych. Atrybut x -wykonanie jest
ignorowany.

attr Atrybuty kolejki
Funkcja mq_open zwraca:
1. W przypadku pomyślnego wykonania wynik jest nieujemny – jest to identyfikator

kolejki komunikatów

2. W przypadku błędu funkcja zwraca –1.

Wysłanie komunikatu do kolejki
Wysłanie komunikatu do kolejki komunikatów odbywa się  za pomocą  funkcji:
int   mq_send(mqd_t   mq,   char   *msg,   size_t   len,   unsigned   int   mprio)
Znaczenie parametrów:
mq identyfikator kolejki komunikatów,
*msg adres bufora wysyłanego komunikatu,
len długość  wysyłanego komunikatu,
mprio priorytet komunikatu (od 0 do MQ_PRIORITY_MAX).
Wywołanie  funkcji  powoduje  przekazanie  komunikatu  z  bufora  msg  do  kolejki  mq.
MoŜna wyróŜnić  dwa zasadnicze przypadki:
1.  W  kolejce  jest  miejsce  na  komunikaty.  Wtedy  wykonanie  funkcji  nie  spowoduje

zablokowania procesu bieŜącego.

2. W kolejce brak miejsca na komunikaty. Wtedy wykonanie funkcji spowoduje za-

blokowania procesu bieŜącego. Proces ulegnie odblokowaniu gdy zwolni się miej-
sce w kolejce.

Zachowanie się funkcji uzaleŜnione jest od stanu flagi O_NONBLOCK. Flaga ta jest
domyślnie wyzerowana. W ogólności funkcja zwraca: 0 Sukces -1 Błąd

Pobieranie komunikatu z kolejki
Pobieranie komunikatu z kolejki komunikatów odbywa się za pomocą funkcji
mq_receive.
int mq_receive(mqd_t mq, char *msg, size_t len, unsigned int *mprio)
Znaczenie parametrów:
mq identyfikator kolejki komunikatów,
*msg Adres bufora na odbierany komunikat,
len maksymalna długość odbieranego komunikatu,
mprio priorytet odebranego komunikatu.

1. Gdy w kolejce znajduje się przynajmniej jeden komunikat wywołanie funkcji

mq_receive nie spowoduje zablokowania procesu bieŜącego.

2. Gdy w kolejce brak komunikatów wywołanie funkcji mq_receive spowoduje za-

blokowania procesu bieŜącego. Proces ulegnie odblokowaniu gdy w kolejce poja-
wi się jakiś komunikat.

W  przypadku  gdy  więcej  niŜ  jeden  proces  czeka  na  komunikat  –  odblokowany  bę-
dzie  proces  który  najdłuŜej  czekał.  Zachowanie  się  funkcji  uzaleŜnione  jest  takŜe  od
stanu flagi O_NONBLOCK. Funkcja mq_receive zwraca:
>0 Rozmiar odebranego komunikatu gdy wynik jest większy od 0.
–1 Gdy wystąpił  błąd.

Testowanie statusu kolejki komunikatów
Testowanie statusu kolejki komunikatów odbywa się poprzez wykonanie funkcji:
int mq_getattr(mqd_t mq, struct mq_attr *attr)
Znaczenie parametrów:
mq Iidentyfikator kolejki komunikatów,
*attr Adres bufora ze strukturą zawierającą atrybuty kolejki komunikatów
UŜyteczne elementy struktury atrybutów:
mq_curmsg Aktualna liczba komunikatów w kolejce
mq_sendwait Liczba procesów zablokowanych na operacji zapisu
mq_recvwait Liczba procesów zablokowanych na operacji odczytu

Zawiadamianie procesu o pojawieniu się  komunikatu w kolejce
MoŜna  spowodować  aby  pojawienie  się  komunikatu  w  pustej kolejce (a wiec zmiana
stanu  kolejki  z  „pusta”  na  „niepusta”)  powodowało  zawiadomienie  procesu  bieŜące-
go. Zawiadomienie moŜe mieć  postać  sygnału lub depozytu (ang. Proxy).
int mq_notify(mqd_t mq, struct sigevent *notif)
Znaczenie parametrów:
mq Identyfikator kolejki komunikatów,

*notif Adres struktury typu sigevent specyfikuj

cego sposób zawiadomienia.

Gdy pole sigev_signo > 0 interpretowane jest ono jako numer sygnału który

będzie wysłany gdy w kolejce pojawi się komunikat. W procesie naleŜy zdefinio-
wać sposób obsługi tego sygnału.

Gdy pole sigev_signo < 0 jego wartość bezwzględna interpretowana jest jako

numer depozytu generowanego gdy w kolejce pojawi się komunikat.

Zamknięcie i skasowanie kolejki komunikatów
Gdy proces przestanie korzystać z kolejki komunikatów powinien ją zamknąć. Do
tego celu słuŜy funkcja:
int mq_close(mqd_t mq)
Kolejkę kasuje się za pomocą polecenia:
int mq_unlink(char *name)

18. Problem producenta / konsumenta, czytelników i pisarzy i ich rozwią-
zanie za pomocą komunikatów, semaforów, monitorów, kolejek komunika-
tów.

Problem producenta i konsumenta

Zagadnienie kontroli uŜycia jednostek zasobu
W systemie istnieje pula N jednostek zasobu pewnego typu. Procesy mogą  pobierać
z puli zasoby i je zwracać. Gdy brak jest zasobu a pewien proces będzie próbował  go
pobrać  ulega  on  zablokowaniu. Proces  zostanie odblokowany gdy inny proces zwróci
jednostkę  zasobu.
1. W systemie istnieją  dwie grupy procesów – producenci i konsumenci oraz bufor
na elementy.
2. Producenci produkują  pewne elementy i umieszczają  je w buforze.
3. Konsumenci pobierają  elementy z bufora i je konsumują.
4. Producenci i konsumenci przejawiają  swą  aktywność  w nie dających się  określić
momentach czasu.
5. Bufor ma pojemność  na N elementów.

NaleŜy prawidłowo zorganizować  pracę  systemu.
1.  Gdy  są  wolne  miejsca  w  buforze  producent  moŜe  tam  umieścić  swój  element.
Gdy w buforze brak miejsca na elementy producent musi czekać. Gdy wolne miejsca
się  pojawią  producent zostanie odblokowany.
2.  Gdy  w  buforze  są  jakieś  elementy  konsument  je  pobiera.  Gdy  brak  elementów  w
buforze  konsument  musi  czekać.  Gdy  jakiś  element  się  pojawi,  konsument  zostanie
odblokowany.
Bufor zorganizowany moŜe być  na róŜnych zasadach.
1. Kolejka FIFO (bufor cykliczny).
2. Kolejka LIFO (stos).
Umieszczanie / pobieranie elementu z bufora jest sekcją  krytyczną.

Problem czytelników i pisarzy
W  systemie  istnieją  dwie  grupy  procesów  –  czytelnicy  i  pisarze.  Czytanie  moŜe  się
odbywać   współbieŜnie  z  innymi  procesami  natomiast  pisanie,  w  celu  zapewnienia
spójności danych, musi się  odbywać  na zasadzie wyłączności.

Czytelnik moŜe wejść do czytelni gdy jest ona pusta lub gdy są tam inni czytelni-

Pisarz moŜe wejść do czytelni gdy jest ona pusta

Problem jest uogólnieniem problemu dostępu wielu procesów do bazy danych.

Rozwiązanie problemu producenta i konsumenta za pomocą komunikatów
Struktura rozwiązania:
1. Zarządzanie buforami leŜy w gestii procesu administratora
2. Procesy producentów i konsumentów komunikują się z procesem administratora.

Administrator zasobu
Problemy:
1. Jak wstrzymać  procesy producentów gdy brak miejsca w buforze?
2. Jak wstrzymać  procesy konsumentów gdy brak elementów w buforze?
Rozwiązanie:
1. Procesom które mają  być  wstrzymane nie udziela się  odpowiedzi Reply.
2.  Aby  moŜna  było  tak  wstrzymany  proces  potem  odblokować  naleŜy  przechować
jego pid.

Rozwi

zanie problem czytelników i pisarzy za pomoc

semaforów

Rozwiązanie z moŜliwością  zagłodzenia pisarzy
- Czytelnik moŜe wejść  do czytelni gdy jest ona pusta lub gdy są  tam inni czytelnicy
- Pisarz moŜe wejść  do czytelni gdy jest ona pusta
MoŜe się  tak zdarzyć  Ŝe zawsze jakiś  czytelnik jest w czytelni co doprowadzi do za-
głodzenia pisarzy.
Rozwiązanie z moŜliwością  zagłodzenia czytelników
- Czytelnik musi czekać  gdy są  w czytelni lub czekają  jacykolwiek pisarze
Rozwiązanie poprawne
- Wpuszczać  na przemian czytelników i pisarzy
- Gdy wchodzi jeden z czytelników, to wpuszcza on wszystkich czekających czytelni-
ków
Rozwiązanie  poprawne  nie  dopuszcza  do  zagłodzenia  czy  to  czytelników  czy  teŜ  pi-
sarzy.

#define PLACES 8 // Liczba wolnych miejsc w czytelni
semaphore wolne ; // Liczba wolnych miejsc w czytelni

semaphore wr; // Kontrola dostępu do czytelni
Reader(){

while (TRUE) {
sem_wait(wolne); // Czekanie na miejsca w czytelni
read_db(); // Czytelnik w czytelni - czyta
sem_post(wolne); // Zwolnienie miejsca w czytelni

}
Writer() {

while (TRUE) {

create_data(); // Pisarz zastanawia się
sem_wait(wr); // Zablokowanie dostępu dla pisarzy
// Wypieranie czytelników z czytelni
for(j=1;j<=places;j++)
sem_wait(wolne);
write_db(); // Pisarz w czytelni – pisze
// Wpuszczenie czytelników
for(j=1;j<= PLACES;j++)
sem_post(wolne);
sem_post(wr); // Odblokowanie pisarzy

}

}
main() {

sem_init(wolne,PLACES);
sem_init(wr,1);
....

}
Rozwiązanie problemu producenta i konsumenta – semafory nienazwane

Rozwiązanie problemu producenta i konsumenta za pomocą monitorów

Rozwiązanie problemu czytelników i pisarzy za pomocą monitorów

monitor CzytelnicyPisarzecondition Pisanie, Czytanie;// Kolejka pisarzy i czytelników
int ReaderCount = 0; // Liczba czytelników w czytelni
Boolean zajety = false; // true gdy w czytelni jest pisarz
procedure StartRead() {

if (zajety) // Gdy czytelnia zajęta - blokada
Wait(Czytanie);ReaderCount++;Signal(Czytanie); // Wpuść następnego
czytelnika

}
EndRead() {

ReaderCount-- ;if(ReaderCount == 0) // Ostatni Czyt. wpuszcza pisarzy
Signal(Pisanie);

}
StartWrite() {// Czekaj gdy w czytelni jest pisarz lub czytelnicyif(zajety

ReaderCount != 0)

Wait(Pisanie);
zajety = true;

}
EndWrite() {

zajety = false;// Gdy czekają czytelnicy to ich wpuść

// Gdy czytelnicy nie czekają – wpuść pisarzy

if (Notempty(Czytanie)) Signal(Czytanie);
else Signal(Pisanie);

}
Reader() {

while (true) {

StartRead();
Czytaj(); // Wykonaj procedurę czytaniaEndRead();

}

Writer() {

while (true) {

StartWrite();
Pisz(); // Wykonaj procedurę pisaniaEndWrite();

}

19. Obsługa zdarzeń asynchronicznych. Sygnały i ich obsługa. Funkcje sig-
nal, kill, raise, alarm, raise, pause. Zabezpieczanie operacji blokujących sy-
gnałami.

Zdarzenia i ich obsługa
Istnieją  dwie metody pozyskania informacji o zdarzeniach:
1. Cykliczne odpytywanie urządzenia czy zdarzenie zaszło (ang. polling).
2. Wykorzystanie przerwań  generowanych przez zdarzenia (ang. interrupt).
Maksymalny czas reakcji na zdarzenia powinien być  mierzony dla najmniej korzyst-
nych  warunków.  Stąd  mamy  pewność   Ŝe  w  rzeczywistej  sytuacji  czas  reakcji  na

zdarzenie nie będzie dłuŜszy od Tmax. NaleŜy tak konstruować systemy aby mak-
symalny czas reakcji na zdarzenia był jak najkrótszy.

Metoda odpytywania posiada następujące cechy.
1.  Długi  czas  reakcji  na  zdarzenie  –  maksymalnie  suma  czasów  obsługi  wszystkich
zdarzeń.
2. Trudności w uszeregowaniu obsługi zdarzeń  według priorytetów.
3. Przy braku zdarzeń  utrata czasu procesora na wykonanie jałowych czynności
4. Prostota implementacji – nie jest wymagany specjalny sprzęt.

Sygnał  –  mechanizm  asynchronicznego  powiadamiania  procesów  o  zdarzeniach  –
zwykle  awaryjnych.  Metoda  powiadamiania  procesów  za  pomocą  sygnałów  wywodzi
się  z systemu UNIX.

Sygnały mogą  być  generowane przez:
1.  System operacyjny, zwykle po wykonaniu nieprawidłowej operacji.
2.  Z konsoli operatorskiej poprzez polecenia kill i slay.
3.  Z programu aplikacyjnego poprzez funkcje kill, raise, abort, alarm oraz timery.

Proces moŜe zareagować  na sygnały w sposób następujący:
1.  ObsłuŜyć  sygnał czyli wykonać  funkcję  dostarczoną  poprzez programistę.
2.  Zignorować  sygnał– nie kaŜdy sygnał  daje się  zignorować.
3.  Zablokować  sygnał  to znaczy odłoŜyć  jego obsługę  na później.
4.  Zakończyć  się  po otrzymaniu sygnału.

Reakcja procesu na sygnałw zaleŜności od stanu w jakim znajduje się proces.
1. Gdy proces jest wykonywany lub gotowy to następuje przerwanie sekwencji

wykonania i skok do procedury obsługi sygnału.

2. Gdy proces jest zablokowany to następuje jego odblokowanie i wykonanie

procedury obsługi tego sygnału.

Obsługa sygnału dla przypadków gdy proces jest gotowy i zablokowany

Zestawienie waŜniejszych sygnałów

Sygnał

Opis sygnału

Akcja
domyślna

SIGABRT

Sygnał przerwania procesu (ang. Abort). Sygnał moŜe
być wygenerowany poprzez wykonanie funkcji abort w
procesie bieŜącym. Powoduje Ŝe proces przed zakoń-
czeniem zapisuje na dysku swój obraz (ang. core dump)

ABRT,
DMP

SIGALRM

Sygnał alarmu (ang. Alarm) wskazujący Ŝe upłynął za-
dany czas. Generacja moŜe być spowodowana poprzez
wykonanie funkcji alarm lub czasomierze (ang. Timers).

ABRT

SIGBUS

Sygnał wysyłany przez system operacyjny gdy ten
stwierdzi błąd magistrali (ang. Bus error).

ABRT

SIGCHLD

Przesyłany do procesu macierzystego gdy proces po-
tomny (ang. Child) kończy się.

IGN

SIGSTOP

Powoduje Ŝe proces który otrzymał ten sygnał ulega
zablokowaniu do czasu gdy nie otrzyma sygnału
SIGCONT

SIGCONT

Powoduje wznowienie procesu zawieszonego sygnałem
SIGCONT

SIGFPE

Generowany przez system gdy nastąpił błąd operacji
zmiennoprzecinkowej (ang. Floating point exception).

ABRT,
DMP

SIGHUP

Generowany gdy następuje zamknięcie terminala (ang.
Hangup). Sygnał otrzymują procesy dla których jest to
terminal kontrolny.

ABRT

SIGILL

Generowany gdy proces próbuje wykonać nielegalną
instrukcję (ang. Illegal instruction).

ABRT

SIGINT

Przerwanie procesu (ang. Interrupt). Sygnał wysyłany
do wszystkich procesów związanych z danym termina-
lem gdy tam naciśnięto Ctrl+Break lub Ctrl+C.

SIGKILL

Sygnał wysyłany w celu zakończenia procesu. Nie moŜe
być przechwycony ani zignorowany.

ABRT

SIGPIPE

Generowany przy próbie zapisu do łącza (ang. Pipe) lub
gniazdka gdy proces odbiorcy zakończył się.

ABRT

SIGPOLL

Sygnał generowany przez system gdy na otwarty plik
stał się gotowy do zapisu lub odczytu.

ABRT

SIGQUIT

Próba zakończenia procesu (ang. Quit). Sygnał wysyła-
ny do wszystkich procesów związanych z danym termi-
nalem gdy tam naciśnięto Ctrl+\.

ABRT,
DMP

SIGSEGV

Wysyłany przez system gdy proces naruszył mechanizm
ochrony pamięci (ang. Segment Violation)

ABRT

SIGTERM

Sygnał wysyłany w celu zakończenia procesu. Nie moŜe
być przechwycony ani zignorowany.

ABRT

SIGPWR

Generowany przez system operacyjny gdy ten stwierdzi
upadek zasilania (ang. Power Failure) sygnalizowany
przez układ dozoru zasilania.

ABRT

SIGUSR1

Sygnał moŜe być wykorzystany przez uŜytkownika do
własnych potrzeb.

ABRT

SIGUSR2

Sygnał moŜe być wykorzystany przez uŜytkownika do
własnych potrzeb.

ABRT

Wysyłanie sygnałów z programu

UŜycie funkcji  kill
Funkcja kill posiada następujący prototyp:
int kill(pid_t pid, int sig)
pid PID procesu do którego wysyłany jest sygnał
sig Numer sygnału.
Funkcja kill powoduje wysłanie sygnału sig do procesu pid.
Funkcja zwraca 0 gdy sukces, -1 gdy błąd.
Aby proces bieŜący mógł  wysłać  sygnał  do innego procesu musi być  spełniony jeden
z warunków:
1.  Efektywny  identyfikator  uŜytkownika  EUID  (ang.  Effective  User  ID)  procesu  wy-

syłającego sygnał i procesu docelowego muszą być zgodne.

2. Rzeczywisty identyfikator uŜytkownika UID (ang. User ID) procesu wysyłającego

sygnał i procesu docelowego muszą być zgodne.

3. Proces wysyłający sygnał ma prawa administratora (ang. root).
Specjalne znaczenie parametru pid:
1. Gdy pid = 0 to sygnał będzie wysyłany do wszystkich procesów naleŜących do tej

samej grupy co nadawca.

2. Gdy pid < 0 to sygnał będzie wysyłany do wszystkich procesów naleŜących do

grupy o numerze id = |pid|.

UŜycie funkcji raise
Funkcja raise posiada następujący prototyp:
int raise(int sig)
sig Numer sygnału.
Funkcja raise powoduje wysłanie sygnału sig do procesu który tę funkcję wykonał.
Gdy sig = 0 to następuje wysłanie sygnału do wszystkich procesów naleŜących do
grupy procesów. Funkcja zwraca 0 gdy sukces, -1 gdy błąd.

UŜycie funkcji  alarm
Funkcja alarm posiada następujący prototyp:
int alarm(int seconds)
Funkcja  alarm  powoduje  wygenerowanie  sygnału  SIGALRM  po  upływie  liczby  se-
kund wyspecyfikowanej jako parametr. Sygnał  wysyłany jest do procesu który funk-
cję  wywołał.
Funkcja zwraca:
> 0 to wynik jest liczbą  sekund pozostałych do wysłania sygnału.
0 znaczy Ŝe alarm nie był  wcześniej ustawiany
-1 Błąd

Wysyłanie sygnału z konsoli
Do wysłania sygnału z konsoli uŜyćmoŜna polecenia kill lub slay.

Polecenie kill ma postać:
kill  [-nazwa_sygnału  |  -numer_sygnału]  pid
pid  PID  procesu  do  którego  wysyłany  jest sygnał
numer_sygnału Numeryczne określenie sygnału
nazwa_sygnału Symboliczne określenie sygnału – moŜe być  uzyskane przez pole-
cenie:  kill –l
Uwagi:
1.  Gdy  pid  =  0  to  sygnał  będzie  wysyłany  do  wszystkich  procesów  naleŜących  do

tej samej grupy co uŜytkownik.

2. Gdy pid < 0 to sygnał będzie wysyłany do wszystkich procesów naleŜących do

grupy o numerze

id = |pid|.

Polecenie slay umoŜliwia wysłanie sygnału do procesu bez znajomości jego PID. Ja-
ko parametr podaje się nazwę procesu.
slay [-numer_sygnału] nazwa
nazwa nazwa procesu do którego wysyłany jest sygnał
numer_sygnału Numeryczne określenie sygnału – domyślnie SIGTERM

Obsługa sygnałów
Ustalenie  reakcji  procesu  na  sygnał  odbywa  się  za  pomocą  funkcji  signal.  Ma  ona
następujący prototyp:
void(*signal(int sig, void(*func)(int)))(int)
sig Numer lub symbol sygnału który ma być  obsłuŜony
func Nazwa funkcji która ma być  wykonana gdy proces odbierze sygnał  sig.
MoŜliwe są  trzy typy akcji podejmowanych w reakcji na nadejście sygnału:
1.  Zignorowanie sygnału
2.  Wykonanie  akcji  domyślnej  -działanie  określone  przez  OS  –  zwykle  zakończenie

procesu.

3.  Wykonanie funkcji dostarczonej przez programistę.
Nie jest moŜliwe obsłuŜenie sygnałów:
  SIGSTOP
  SIGKILL
Funkcja  obsługi  sygnału  powinna  być   zdefiniowana  w  programie.  Funkcja  zwraca
wskaźnik  na  poprzednią  funkcję  obsługi  sygnału.  Istnieją  dwie  pierwotnie  zdefinio-
wane funkcje obsługi sygnałów:
SIG_IGN Funkcja powodująca zignorowanie sygnału.
SIG_DFL  Domyślna  reakcja  na  sygnał-zakończenie  procesu  lub  zignorowanie  sy-
gnału.

Funkcja pause powoduje zablokowanie procesu aŜ do chwili nadejścia sygnału. Aby
proces się nie zakończył sygnał musi być obsługiwany.

Odporny interfejs sygnałowy
Funkcje sigaction pozwala na lepsze kontrolowanie obsługi sygnału niŜ zesta-
wy sygnałów.

struct sigaction {

void (*sa_handler)(int) ; // Funkcja obsługi sygnału
sigset_t sa_mask; // Sygnały blok. podczas obsługi

int sa_flags; // Flagi modyfikacji działania

}

Pole sa_mask definiuje sygnały blokowane podczas obsługi danego sygnału. Będą
one zgłoszone później. Pole sa_handler moŜe mieć  jedną  z trzech wartości:
  SIG_IGN
  SIG_DFL
  Adres handlera obsługi sygnału

Funkcja sigaction:
int sigaction(int signo, struct sigaction *act, structsigaction *oldact);
signo Numer sygnału dla którego definiowana jest akcja act.
act Definicja działania które ma być podjęte gdy przyjdzie sygnał.
oldact Definicja poprzedniej akcji lub ULL
Funkcja sigaction definiuje sposób obsługi sygnału signo.

Uwagi o obsłudze sygnałów.
1.  Blokada sygnałów.
Podczas obsługi sygnału dostarczanie innych sygnałów jest zablokowane.
2.  Sygnały i komunikaty.
Gdy proces jest zablokowany na funkcji Send lub Receive reakcja na sygnał  jest na-
stępująca:

  Proces jest odblokowywany
  Sygnał jest obsługiwany
  Funkcja Send lub Receive kończy się  błędem: kod powrotu –1 i zmienna errno

= EINTR.

3. Sygnały i funkcje systemowe.
W większości przypadków w czasie wykonania funkcji systemowych sygnały są za-
blokowane. Wyjątek stanowią:

Funkcje read, write, open w odniesieniu do terminali.
Funkcje wait, pause, sigsuspendFunkcje te będą przerywane przez sygnał.

MoŜliwe jest ustawienie flagi S.A._RESTART aby przerwane funkcje kontynu-
ować.

4. Kolejkowanie sygnałów.
Sygnały nie są kolejkowane

20. Pojęcie wątku, synchronizacja wątków, muteksy, zmienne warunkowe,

biblioteka Pthreads.

Proces – pojemnik na zasoby w ramach którego wykonują  się  watki.
Wątek – elementarna jednostka szeregowania korzystająca z zasobów procesu.
Wątki  wykonywane  w  ramach  jednego  procesu  dzielą  jego  przestrzeń  adresową  i
inne zasoby procesu.
W ramach jednego procesu moŜe się  wykonywać  wiele wątków

Atrybuty i zasoby własne wątku
1.  Identyfikator  wątka  TID  (ang.Thread  Identifier)  -  kaŜdy  watek  ma  unikalny  w
ramach  procesu  identyfikator.  Jest  to  liczba  całkowita.  Pierwszy  wątek  ma  TID  1,
następny 2 itd.
2.  Zestaw  rejestrów  (ang.  Register  set)  -  kaŜdy  wątek  posiada  własny  obszar  pa-
mięci  w  którym  pamiętany  jest  zestaw  rejestrów  procesora  (tak  zwany  kontekst
procesora). Gdy watek jest wywłaszczany lub blokowany w obszarze tym pamiętane
są  rejestry  procesora.  Gdy  watek  będzie  wznowiony  obszar  ten  jest  kopiowany  do
rejestrów procesora.
3.  Stos  (ang.  Stack) - kaŜdy wątek ma swój własny stos umieszczony w przestrzeni
adresowej  zawierającego  go  procesu.  Na  stosie  tym  pamiętane  są  zmienne  lokalne
wątku.
4. Maska sygnałów (ang. Signal mask) - kaŜdy wątek ma swą  własną  maskę  sygna-
łów.  Maska  sygnałów  specyfikuje  które  sygnały  mają  być  obsługiwane  a  które  blo-
kowane. Początkowa maska jest dziedziczona z procesu macierzystego.
5. Obszar TLS wątku (ang. Thread Local Storage) – kaŜdy wątek ma pewien obszar
pamięci  przeznaczony  na  utrzymywanie  róŜnych  danych  administracyjnych  takich
jak  TID,  PID,  początek  stosu,  kod  ewentualnego  błędu  errno  i  inne  dane.  Obszar
TLS jest odpowiednikiem deskryptora procesu.
6. Procedura zakończenia (ang. Cancellation Handler) - gdy wątek się  kończy wyko-
nywana jest procedura zakończenia w ramach której zwalniane są  zasoby wątku.

Wątek dzieli ze swym procesem macierzystym następujące zasoby:
  Dane statyczne (segment danych)
  Pliki
  Środowisko
  Katalog macierzysty
  Sesję, uŜytkownika, grupę

Własności wątków
Koszt utworzenia i przełączania wątku jest mniejszy niŜ procesu.
Dane statyczne procesu są dla wątków działających w ramach jednego procesu

wzajemnie widoczne.

Wykonanie kaŜdego wątku przebiega sekwencyjnie, kaŜdy wątek ma swój licznik

rozkazów.

Wątki mogą być wykonywane na oddzielnych procesorach co umoŜliwia przyspie-

szenie obliczeń.

PoniewaŜ wątki dzielą wspólne dane konieczna jest synchronizacja dostępu do

tych wspólnych danych.

Rodzaje wątków
WyróŜniane są  następujące typy wątków:
  Wątki poziomu jądra KLT - (ang. Kernel Level Tthreads).
  Wątki poziomu uŜytkownika ULT - (ang. User Level Threads).
  Rozwiązania mieszane

Kanoniczne stany wątku
  Wykonywany - Właśnie wykonywany przez procesor
  Gotowy - Posiadający wszyskie zasoby oprócz procesora
  Zablokowany - Brak pewnych zasobów
  Zombie - Zakończony ale nie dołączony do wątku macierzystego (wątek dołą-

czalny)

Nieistniejący - Nie utworzony lub zakończony

Diagram stanów kanonicznych w

tków

Podstawowe operacje na w

tkach

Tworzenie wątku
Nowy  wątek  tworzy  się  przy  pomocy  funkcji  pthread_create.  Funkcja  ta  tworzy
wątek,  którego  kod  znajduje  się  w  funkcji  podanej  jako  argument  func.  Wątek  jest
uruchamiany  z  parametrem  arg,  a  informacja  o  nim  jest  umieszczana  w  strukturze
thread.

int pthread_create( pthread_t *thread, pthread_attr_t *attr, void (*
func)(void *), *arg)
thread identyfikator wątku – wartość  nadawana przez funkcję
attr atrybuty wątku, gdy NULL przyjęte domyślne
func  procedura zawierająca kod wątku
arg  argument  przekazywany  do  wątku
Funkcja zwraca: 0 – sukces, -1 – błąd.

Kończenie wątku
Wątek moŜe być  zakończony w następujące sposoby:
  Następuje powrót z procedury określającej kod wątku.
  Wątek wykonuje funkcję  pthread_exit().
  Wątek jest kasowany przez inny wątek.
  Następuje zakończenie procesu macierzystego wątku.
Jawne zakończenie wątku następuje poprzez wywołanie procedury:
pthread_exit(void * status)
status Kod powrotu wątku
MoŜliwe są  dwa sposoby postępowania z kończonymi wątkami:
1. Z chwilą  zakończenia się  wątku zwalniane są  wszystkie jego zasoby.
2. Zasoby zwalniane są  z chwilą  dołączenia wątku bieŜącego do innego  wątku (wy-
konującego funkcję  pthread_join).
Postępowanie to uzaleŜnione jest od ustawienia atrybutu
PTHREAD_CREATE_JOINABLE który ustalany jest podczas tworzenia wątku.
1.  Gdy  atrybut  ten  nie  jest  ustawiony,  wątek  zwalnia  swe  zasoby  zaraz  po  zakoń-
czeniu.
2. Gdy atrybut jest  ustawiony,  wątek zwalnia zasoby po dołączeniu do  innego wąt-
ku.

Oczekiwanie na zakończenie wątku.
Proces bieŜący moŜe czekać  na zakończenie innego wątku poprzez wywołanie
funkcji pthread_join.
int pthread_join( pthread_t *thread, void *status)
thread identyfikator wątku – wartość  nadawana przez funkcję
status Kod powrotu zwracany przez zakończony wątek
Gdy  wskazany  jako  parametr  wątek  nie  zakończył  się  jeszcze,  wątek  bieŜący  jest
wstrzymywany.
Funkcja zwraca: 0 – sukces, -1 – błąd.

Inne atrybuty wątków
Oprócz sposobu zakończenia wątków moŜna ustawiać takŜe inne atrybuty wątków
jak np. stategia szeregowania (SCHED_RR, SCHED_FIFO,SCHED_OTHER).

Uzyskanie własnego identyfikatora
Wątek moŜe uzyskać własny identyfikator poprzez wywołanie funkcji:
pthread_t pthread_self(void)

Zwolnienie procesora
Wywołanie funkcji pthread_yield powoduje przekazanie sterowania do procedury
szeregującej która wybierze następny wątek do wykonania.

int pthread_yield(void)

Dostęp do wspólnych danych
Wątki  dzielą  wspólny  obszar  danych.  Stąd  współbieŜny  dostęp  do  danych  moŜe  na-
ruszyć  ich  integralność.  NaleŜy  zapewnić  synchronizację  dostępu  do  wspólnych  da-
nych.  W  bibliotece  pthreads  do  zapewnienia  wyłączności  dostępu  do  danych  stosuje
się  mechanizm  muteksu  (ang.  mutex).  Nazwa  ta  pochodzi  od  słów  Mutual  exclusion
czyli wzajemne wykluczanie.

Deklaracja muteksu

Muteks jest obiektem abstrakcyjnym który moŜe być w dwu stanach: wolny i zajęty. Na

muteksie wykonuje się dwie podstawowe operacje: zajęcie i zwolnienie. Bibliote-

ka  pthreads  definiuje  muteks  jako  typ  pthread_mutex_t.  Przed  uŜyciem  obiekt
typu muteks musi być  zadeklarowany. Przykładowo muteks o nazwie blokada dekla-
ruje się  jak poniŜej.
pthread_mutex_t blokada;

Inicjacja muteksu
Przed uŜyciem muteks musi być  zainicjowany. Inicjacja następuje poprzez wykona-
nie funkcji:
int  pthread_mutex_init(pthread_mutex_t  *mutex,  pthread_mutexattr_t
*attr)
mutex Zadeklarowana wcześniej zmienna typu pthread_mutex_t.
attr Atrybuty muteksu. Gdy attr jest równe NULL przyjęte będą  wartości domyślne.
Funkcja zwraca: 0 – sukces, -1 – błąd.
Zainicjowany muteks pozostaje w stanie odblokowania.

Zablokowanie dostępu do zasobu
Przed  dostępem  do  zasobu  naleŜy  zapewnić  sobie  wyłączność  w  korzystaniu  z  tego
zasobu. W tym celu wątek wykonuje funkcję:
int pthread_mutex_lock(pthread_mutex_t *mutex);
mutex Zadeklarowana wcześniej i zainicjowana zmienna typu
pthread_mutex_t
Działanie funkcji zaleŜy od stanu w jakim znajduje się  muteks.
1. Gdy muteks jest wolny, następuje jego zablokowanie.
2.  Gdy  muteks  jest  zajęty,  próba  jego  powtórnego  zajęcia  powoduje  zablokowanie
się  wątku który tę  próbę  podejmuje.

Odblokowanie dostępu do zasobu
UŜyty i zablokowany wcześniej zasób powinien być zwolniony. Zwolnienie zasobu
odbywa się poprzez wywołanie funkcji:
int pthread_mutex_unlock(pthread_mutex_t *mutex)

mutex Zadeklarowana wcześniej i zainicjowana zmienna typu
pthread_mutex_t
Działanie funkcji zaleŜy od tego czy inne wątki czekają  zablokowane na muteksie.
1.  Brak  wątków  zablokowanych  na  muteksie  –  stan  muteksu  zostaje  zmieniony  na
wolny.
2. Są  wątki zablokowane na muteksie – jeden z czekających wątków zostaje odblo-
kowany.

Kasowanie muteksu
Kasowanie muteksu odbywa się poprzez wywołanie funkcji:
int pthread_mutex_destroy(pthread_mutex_t *mutex)
System zwalnia zasoby zajęte przez muteks. Muteks musi być wolny gdyŜ w prze-
ciwnym razie nie będzie skasowany i funkcja zwróci kod błedu.

Gdy dwa lub więcej wątki o róŜnych priorytetach uŜywają  wspólnego muteksu moŜe
dojść  zjawiska nazywanego inwersją  priorytetów.
Inwersja priorytetów – zjawisko polegające na wykonywaniu się  wątku o niŜszym
priorytecie  mimo  Ŝe  wątek  o  wyŜszym  priorytecie  pozostaje  gotowy.  Inwersja  prio-
rytetów  moŜe  się  pojawić  gdy  wątki  o róŜnych priorytetach uŜywają  wspólnego mu-
teksu lub podobnego mechanizmu synchronizacyjnego.
Podbicie  priorytetu  –  tymczasowe  zwiększenie  priorytetu  wątku  przebywającego
w sekcji krytycznej do priorytetu wątku który oczekuje na wejście do sekcji krytycz-
nej.
Ilustracja zjawiska inwersji priorytetów

Zmienne warunkowe
Zmienna warunkowa jest narzędziem do blokowania wątku wewnątrz sekcji krytycz-
nej aŜ  do momentu gdy pewien warunek zostanie spełniony. Warunek ten moŜe być
dowolny i niezaleŜny od zmiennej warunkowej. Zmienna warunkowa musi być  uŜyta
w połączeniu z muteksem o ile konstrukcja ma zapewnić  własności monitora. Przed
uŜyciem zmienna warunkowa musi być  zadeklarowana jako zmienna typu pthre-
ads_cond_t.
NajwaŜniejsze operacje związane ze zmiennymi warunkowymi są  dane poniŜej.

Inicjacja zmiennej warunkowej
int pthread_cond_init(pthreads_cond_t *zw, pthreads_condattr_t attr)
zw Zadeklarowana wcześniej zmienna typu pthread_cond_t.
attr Atrybuty zmiennej warunkowej. Gdy attr jest równe NULL przyjęte będą war-
tości domyślne.

Zawieszenie wątku w oczekiwaniu na sygnalizację
int pthread_cond_wait(pthreads_cond_t *zw, pthread_mutex_t *mutex)
zw Zadeklarowana i zainicjowana zmienna typu pthread_cond_t.
mutex Zadeklarowana i zainicjowana zmienna typu pthread_mutex_t.
Funkcja  powoduje  zawieszenie  bieŜącego  wątku  w  kolejce  związanej  ze  zmienną
warunkową   zw.  Jednocześnie  blokada  mutex  zostaje  zwolniona.  Obie  operacje  są
wykonane  w  sposób  atomowy.  Gdy  inny  wątek  wykona  operację  pthre-
ads_cond_signal(&zw)  zablokowany  wątek  zostanie  odblokowany  a  blokada  mu-
tex zwolniona.

Wznowienie zawieszonego wątku
int pthread_cond_signal(pthreads_cond_t *zw)
zw Zadeklarowana i zainicjowana zmienna typu pthread_cond_t.
Jeden z wątków zablokowanych na zmiennej warunkowej zw zostanie zwolniony.

Wznowienie wszystkich zawieszonych wątków
int pthread_cond_brodcast(pthreads_cond_t *zw)
zw Zadeklarowana i zainicjowana zmienna typu pthread_cond_t.
Wszystkie wątki zablokowane na zmiennej warunkowej zw zostaną zwolnione.

Biblioteka pthreads
Zestaw funkcji dotyczący wątków zdefiniowany został  przez normę  POSIX P1003.4a
i nosi nazwę  pthreads  (skrót od Posix threads). Implementacja  pakietu istnieje mię-
dzy innymi w systemie Linux, QNX6, DEC OSF1. Obecnie wątki są  elementem biblio-
teki glibc (Od wersji 2).

21. Problem zakleszczenia, definicja i przykłady (zastój meksykański, pro-
blem 5 filozofów). Warunki konieczne blokady, metody wykrywania i uni-
kania blokad, graf przydziału zasobów.

W  systemach  w  których  wykonywane  jest  wiele  współbieŜnych  procesów  które  ope-
rują   na  wspólnych  zasobach  moŜe  dojść   do  niezamierzonego  wstrzymania  pracy
pewnych procesów. Mówi się  Ŝe procesy mogą  ulec zakleszczeniu.

Zakleszczenie
Zbiór procesów jest w stanie zakleszczenia jeŜeli kaŜdy proces z tego zbioru czeka
na zdarzenie które moŜe być spowodowane tylko przez inny proces z tego samego
zbioru.

Prosty przykład zakleszczenia - zastój meksykański (ang. Mexican stan-
doff)

Problem pięciu ucztujących filozofów
Przy  okrągłym  stole  siedzi  pięciu  filozofów.  Zajmują   się   oni  naprzemiennie  tylko
dwoma  czynnościami  -  myśleniem  i  jedzeniem.  Do  jedzenia  filozof  potrzebuje  dwu
widelców.  Gdy  filozof  otrzyma  dwa  widelce  je,  a  następnie  odkłada  obydwa  widelce.
Problem  polega  na  takim  zorganizowaniu  pracy  filozofów  aby  spełnione  były  warun-
ki:
- Filozof je wtedy gdy zdobędzie dwa widelce.
- Dwu filozofów nie moŜe trzymać  tego samego widelca.
- KaŜdy z filozofów musi się  w końcu najeść  (nie zostanie zagłodzony).
Dodatkowym  wymaganiem  jest  efektywność  rozwiązania.  Znaczy  to  Ŝe  nie  naleŜy
blokować  aktywności  filozofa  gdy  nie  jest  to  konieczne  dla  spełnienia  poprzednich
warunków.

A. Rozwiązanie z moŜliwością  blokady:
1. Filozof czeka aŜ  będzie wolny lewy widelec i podnosi go.
2. Filozof czeka aŜ  będzie wolny prawy widelec i podnosi go.
3. Filozof je.

4. Filozof odkłada obydwa widelce.
5. Filozof myśli.
JeŜeli w pewnej chwili kaŜdy z filozofów podniesie lewy widelec i będzie czekał na
prawy nigdy go nie otrzyma gdyŜ algorytm przewiduje zwolnienie widelców po za-
kończeniu jedzenia. Nastąpi zakleszczenie.

B. Rozwiązanie z moŜliwością  zagłodzenia:
1. Filozof czeka aŜ  będą  wolne oba widelce i podnosi je (musi to być  operacja niepo-
dzielna).
2. Filozof je.
3. Filozof odkłada obydwa widelce.
4. Filozof myśli.
MoŜe się  tak zdarzyć  Ŝe filozof będzie miał  bardzo Ŝarłocznych sąsiadów z których w
kaŜdej chwili jeden z nich je. W takim przypadku filozof zostanie zagłodzony.

C. Rozwiązanie poprawne
1. Potrzebny jest arbiter zewnętrzny (nazywany lokajem) który dba o to aby jednej
chwili najwyŜej czterech filozofów konkurowało o widelce.
2. Dalej postępujemy jak w przypadku A.

Rozwiązanie problemu pięciu filozofów za pomocą semaforów

Semaphore Widelec[5]; // Tablica pięciu semaforów
Semaphore Lokaj; // Semafor reprezentujący lokaja
// Kod wątku filozofa i, i=0,1,2,3,4
Filozof(int i){

do { // Myślenie

sem_wait(Lokaj); // Dopuszczenie najwyŜej 4 procesów
sem_wait(Widelec[i]); // Czekaj na widelec lewy
sem_wait(Widelec[(i+1)%5]);// Czekaj na widelec prawy
// Jedzenie
sem_post(Widelec[(i+1)%5]); // Oddaj widelec prawy
sem_post(Widelec[i]); // Oddaj na widelec lewy
sem_post(Lokaj);

} while(1);

}
main(void) {

int i;
for(i=0;i<5;i++) {

// Inicjacja semaforów widelec
sem_init(Widelec[i],1);

}
sem_init(Lokaj,4);
for(i=0;i<5;i++) {
// Utworzenie wątków odpowiadających filozofom
...
}
…

}

Warunki Cofmanna
Warunki  konieczne  zakleszczenia  podane  zostały  przez  Coffmana.  Do  zakleszczenia
moŜe dochodzić  gdy spełnione są  jednocześnie cztery warunki:
1. Wzajemne wykluczanie (ang. Mutual exclusion condition ) – KaŜdy z zasobów jest
albo wolny albo zajęty przez dokładnie jeden proces.
2. Przetrzymywanie i oczekiwanie (ang. Wait and hold condition) – Proces posiada-
jący jakiś  zasób moŜe Ŝądać  innego zasobu.
3.  Brak  wywłaszczeń  (ang.  No  prememption  condition)  –  Zasoby  nie  podlegają  wy-
właszczeniu,  czyli  zasób  zajęty  przez  jakiś  proces  moŜe  być  zwolniony  tylko  przez
ten proces.
4. Czekanie cykliczne (ang. Circular wait condition) – Musi istnieć  zamknięty łańcuch
procesów P = {P1, P2,...,Pm} w którym Pi czeka na zasób zajęty przez Pi+1 dla
i=1,m-1 oraz Pm czeka na na zasób zajęty przez P1.

Metody postępowania z zakleszczeniami
1. Zignorowanie problemu - nie zajmować  się  problemami zakleszczeń  na poziomie
systemu operacyjnego
2.  Zapobieganie zakleszczeniom (ang.  deadlock prevention)  - stosować  taki protokół
zamawiania  zasobów  aby  któryś  z  warunków  Coffmana  nie  był  spełniony  i  tym  sa-
mym nie doszło do zakleszczenia.
3.  Unikanie  zakleszczeń  (ang.  deadlock  avoidance)  -  stosować  taki  protokół  zama-
wiania  zasobów  aby  liczba  liczba  wolnych  zasobów  zawsze  umoŜliwiała  zakończenie
rozpoczętych zadań.
4. Dopuszczać  do moŜliwości zakleszczenia ale wykrywać  je a następnie usuwać.

Zapobieganie zakleszczeniom
Zapobieganie  zakleszczeniom  (ang.  deadlock  prevention)  opiera  się  na  niedopusz-
czeniu do spełnienia jednego z warunków Coffmana.
Negacja warunku wzajemnego wykluczania
Nie  jest  moŜliwe  uniknięcie  tego  warunku  gdyŜ  pewne  zasoby  są  z  natury  niepo-
dzielne.
Negacja warunku przetrzymywania i oczekiwania
Podejście  polega  na  unikaniu  sytuacji  gdy  proces  posiadający  juŜ  zasoby  zamawia
inne zasoby.
1. Proces moŜe zająć  zasoby tylko wtedy gdy wszystkie z nich moŜe otrzymać.
2.  Proces  moŜe  zamówić  jakieś  zasoby  tylko  wtedy  gdy  nie  posiada  zajętych  innych
zasobów.  Strategia  nazywa  się  wszystko  albo  nic  (ang.  One-shot  allocation).  Zasto-
sowanie strategii wszystko albo nic do problemu 5-ciu filozofów.
  Filozof moŜe otrzymać  albo dwa widelce albo Ŝadnego.
  Filozof 1 i 3 otrzymują  widelce – reszta czeka.
Rozwiązanie nie powoduje zakleszczenia ale moŜe prowadzić  do zagłodzenia.
Wady:
1. Małe wykorzystanie zasobów gdyŜ  być  moŜe nie wszystkie naraz są  potrzebne do
wykonania zadania.
2.  MoŜliwość  zagłodzenia  pewnych  procesów  poprzez  ciągłe  zajęcie  często  uŜywa-
nych zasobów.
Negacja warunku braku wywłaszczeń.
MoŜliwe jest zastosowanie następujących algorytmów:

1)  Gdy  proces  Ŝąda  zasobu  który  nie  jest  dostępny  sprawdza  się  czy  proces  przy-
trzymujący  te  zasoby  czeka  na  inne zasoby. Gdy  tak jest odbiera się  mu te zasoby.
Implementacja  takiej  metody  wymaga  aby  program  był  napisany  w  języku  obsługu-
jącym wyjątki.
2)  Gdy  proces  posiadający  jakieś  zasoby  Ŝąda  innych  zasobów  które  nie  mogą  być
przydzielone – traci przydzielone zasoby.
Negacja warunku czekania cyklicznego
Aby  zapobiec  czekaniu  cyklicznemu  naleŜy  ponumerować  zasoby  i  Ŝądać  aby  kaŜdy
proces  zamawiał  zasoby  we  wzrastającym  porządku  numeracji.  Gdy  tak  będzie  nie
wystąpi warunek czekania cyklicznego.

Graf przydziału zasobów dla problemu pięciu filozofów – rozwiązanie symetryczne
Istnieje zamknięty cykl procesów:

Graf przydziału zasobów dla problemu pi

ciu filozofów – rozwi

zanie asymetryczne

Unikanie zakleszczeń (ang. deadlock avoidance)

System bezpieczny i zagroŜony
Podejście ma zastosowanie gdy:
1.  Wymagana  jest  aprioryczna  informacja  jakich  zasobów  (i  w  jakiej  ilości)  będzie
uŜywał proces.
2.  W  trakcie  pracy  system  decyduje  czy  zrealizować  zamówienie  czy  teŜ  je  wstrzy-
mać.
ZałoŜenia - realizowalność  przydziału
1. Proces nie moŜe Ŝądać  więcej zasobu niŜ  całkowita ilość  zasobu w systemie
2. Proces nie moŜe Ŝądać  więcej zasobu niŜ  deklarował.
3. Suma przydzielonych zasobów nie moŜe być  większa niŜ  dostępna.
Stan bezpieczny
Dany  stan  przydział  zasobu  jest  bezpieczny  jeŜeli  nie  moŜe  prowadzić  do  zaklesz-
czenia. Stan systemu jest bezpieczny jeŜeli istnieje ciąg bezpieczny
Ciąg bezpieczny.
Ciąg  <P1,P2,...Pn>  jest  bezpieczny  jeŜeli  dla  kaŜdego  procesu  Pj  jego  maksymalne
zapotrzebowanie  na  zasoby  moŜe  być  zaspokojone  przez  zasoby  aktualnie  wolne  i
utrzymywane przez wszystkie procesy Pj gdzie i < j (procesy wcześniejsze w ciągu).

Stan zagroŜenia - nie istnieje ciąg bezpieczny.

Wykrywanie zakleszczeń
Zakleszczenia mogą być wykryte na podstawie analizy grafu oczekiwania (ang. wait-
for graph). Graf oczekiwania moŜna uzyskać z grafu przydziału zasobów przez usu-
nięcie wierzchołków odpowiadających zasobom.
Graf oczekiwania:
1. Wierzchołki – procesy {P1,P2,...Pn}
2. Luki - od Pi do Pj wtedy proces Pi czeka na zasoby zajęte przez proces Pj.

Otrzymywanie grafu oczekiwania z grafu przydziału zasobów

Gdy w grafie oczekiwania wystąpi cykl to system jest w stanie zakleszczenia. Aby na
bieŜąco wykrywać  zakleszczenia system musi:
1. Utrzymywać  aktualny graf oczekiwania
2. Dla grafu oczekiwania wykonywać  algorytm wykrywania cyklu

Likwidowanie zakleszczenia
Gdy zakleszczenie wystąpi i zostanie wykryte naleŜy je zlikwidować. MoŜliwe
podejścia:
Zakończenie procesów
  Wszystkich
  Niektórych aby zakleszczenie ustąpiło
Występuje  problem  które  procesy  zakończyć.  NaleŜy  minimalizować  koszty  zakoń-
czenia przedwczesnego procesów. Decyzja zaleŜy od:
  bezpieczeństwo
  priorytet procesu
  czas wykonywania procesu
  łatwość  wywłaszczenie z zasobu
Wywłaszczenia z zasobów
Przy wywłaszczaniu zasobów naleŜy rozwaŜyć  następujące kwestie
  Który z zasobów ma być  wywłaszczony
  Jak przeprowadzić  wycofanie
  Jak zapewnić  aby nie doszło do zagłodzenia procesu

22. Systemy rozproszone, sprzęt (wieloprocesory, multikomputery), kryte-
ria projektowe, zagadnienia projektowe (komunikacja, nazewnictwo, spój-
ność, struktura), typy.

Czynniki które umoŜliwiły powstanie systemów rozproszonych:
  Rozpowszechnienie tanich i wydajnych komputerów
  Rozwój sieci komputerowych
Naturalna  jest  tendencja  aby  dokonać  ściślejszego  połączenia  komputerów  co  pro-
wadzi do systemów rozproszonych.
Definicja:
System  rozproszony  jest  to  układ  niezaleŜnych  komputerów  który  sprawia  na  jego
uŜytkowniku wraŜenie Ŝe jest jednym komputerem.
Główna idea systemów rozproszonych:
Integracja zasobów sprzętowych i programowych wielu komputerów za pomocą  sieci
w celu wzajemnego udostępnienia ich uŜytkownikom.
Własności:
  Komputery połączone mniej lub bardziej ściśle
  Na wszystkich komputerach wykonywany jednego typu system operacyjny
  Komputery mogą  być  róŜnego typu
  Jednolity mechanizm komunikacji pomiędzy procesami
  System plików wszędzie wygląda jednakowo

Sprzęt systemów rozproszonych
Taksonomia Tanneubauma:
Bierze pod uwagę komunikację pomiędzy procesorami. MoŜe ona być przez:
wspólną pamięć

  Małe pamięci są  drogie
Rozwiązaniem jest zastosowanie szybkiej pamięci podręcznej (ang. cache).
Wieloprocesory przełączane – sieć  z przełącznicą  krzyŜową
Własności:
  Brak blokad - połączenie dowolnego procesora z dowolnym modułem pamięci nie

blokuje połączeń innych procesorów z pozostałymi modułami.

  DuŜy koszt – liczba elementów przełączających p2 (p – liczba procesorów)
  Stosowane wewnątrz superwęzłów (do 8 procesorów)
Maszyny  NUMA  -  Maszyny  z  niejednolitym  czasem  dostępu  do  pamięci.  (ang.Non
Uniform  Memory  Access).  Czas  dostępu  do  pamięci  zaleŜy  od  jej  lokalizacji.  Dla  pa-
mięci  lokalnej  czas  jest  krótszy,  dla  pamięci  odległej  dłuŜszy.  Stosunek  tych  czasów
moŜe  być  1:10  lub  więcej.  KaŜdy  z  procesorów  ma  własną  pamięć  lokalną  ale  ma
takŜe  dostęp  do  pamięci  lokalnych  innych  jednostek.  W  maszynach  NUMA  istnieje
jedna wspólna wirtualna przestrzeń  adresowa.
Własności maszyny NUMA
1. MoŜliwy jest dostęp tak do pamięci lokalnej jak i odległej
2. Dostęp do pamięci odległego węzła jest wolniejszy od dostępu do pamięci lokal-
nej
3. Czas dostępu do pamięci odległej nie jest ukryty przez pamięć  podręczną.

Multikomputer
Własności:
KaŜdy z procesorów ma swoją lokalną pamięć.
Komunikacja procesów odbywa się przez system wejścia / wyjścia przy

wykorzystaniu abstrakcji komunikatów.

WyróŜniamy następujące typy multikomputerów:
  multikomputery szynowe
  multikomputery przełączane
Najczęściej  stosuje  się   multikomputery  szynowe  chociaŜ   są   teŜ   architektury  typu
kostka  wielowymiarowa  czy  krata.  Sprzęt  moŜe  być  powiązany  ściśle  lub  luźno.  Ar-
chitektura ta nosi teŜ  nazwę  klastra.
Schemat multikomputera:

Multikomputery szynowe
Jako szyna bywa stosowana sieć  lokalna 10Mbit/s – 1000 Mbit/s. Architektura mul-
tikomputera szynowego jest podobna do sieci lokalnej.
Multikomputery przełączane
Wymiana danych pomiędzy jednostkami przetwarzającymi odbywa się  za pośrednic-
twem sieci komunikacyjnej o określonej topologii. Typowe topologie takiej sieci to:
  pierścień  (ang. ring),
  siatka (ang. mesh) dwu- lub trójwymiarowa, otwarta, zamknięta
  drzewo (ang. tree),
  gwiazda (ang. star),
  hipersześcian (ang. hypercube).
Sieć  przełączająca – łączy procesory ze sobą  albo procesory i moduły pamięci.

Porównanie multiprocesorów i multikomputerów

Problemy projektowania systemów rozproszonych
Kryteria projektowe które naleŜy spełnić  przy budowie systemów rozproszonych:
  Otwartość
  Skalowalność
  Wydajność
  Przeźroczystość
  Tolerowanie uszkodzeń
Problemy projektowe:
  Nazewnictwo
  Komunikacja
  Struktura oprogramowania
  Przydzielanie obciąŜeń
  Zapewnianie spójności

Kryteria projektowe

Otwartość
Otwartość   –  zdolność   do  rozszerzania  róŜnymi  sposobami.  MoŜliwość   dodawania
składników  sprzętowych  i  programowych  beznaruszenia  stanu  istniejącego.  Otwar-
tość   osiągana  przez  określanie,  dokumentowanie  i  upowszechnienie  zasadniczych
interfejsów.  PoŜądane  cechy  otwartości:  zupełna  i  neutralna  specyfikacja  interfej-
sów.

Zupełność  – kompletny opis interfejsu
Neutralność  - niepreferowanie określonego sposobu implementacji
Przeźroczystość
W prawdziwym systemie rozproszonym uŜytkownicy nie muszą  się  troszczy o lokali-
zację,  ochronę  i  optymalizację  uŜycia  zasobów.  WyroŜniamy  przezroczystość  dostę-
pu, połoŜenia, wędrówki, współbieŜności, awarii, równoległości.
Niezawodność
Jednym z pierwotnych celów budowy systemów rozproszonych było zwiększenie nie-
zawodności całego systemu. Aby to osiągnąć  stosuje się:
  Zwielokrotnienie sprzętu i oprogramowania
  Przechowywanie danych w wielu miejscach
  Tolerowanie awarii
  Specjalne mechanizmy ochrony przed nieautoryzowanym uŜyciem
Wydajność
Jednym  z  pierwotnych  celów  budowy  systemów rozproszonych było zwiększenie wy-
dajności  całego  systemu.  Aby  to  osiągnąć  naleŜy  wziąć  pod  uwagę  ziarnistość  obli-
czeń:
  Rozpraszanie  zadań  składających  się  z  wielu  drobnych  obliczeń  wymagających

wielu interakcji jest nieopłacalne ze względu na koszt komunikacji i koordynacji.

Rozpraszanie zadań zawierających wiele obliczeń które nie wymagają wielu

koordynacji jest opłacalne.

Skalowalność
PoŜądane jest aby po dodaniu dodatkowych węzłów do systemu następował wzrost
jego mocy przetwarzania. Nie byłoby wymagane tu przeprojektowywanie systemu.

Podstawowe zagadnienia projektowe

Usługi nazewnicze
W  systemie  rozproszonym  dostęp  do  zasobu  następuje  poprzez  jego  nazwę  która
jest niezaleŜna od fizycznego połoŜenia zasobu.
Tłumaczenie  nazwy  –  przekształcenie  na  postać  za  pomocą  której  moŜna  spowodo-
wać  działanie  na  obiekcie  lub  zasobie.  W  systemach  rozproszonych  dostęp  do  zaso-
bów następuje na podstawie identyfikatorów komunikacyjnych (np. adres IP i numer
portu). Projektując usługi nazewnicze (ang. Name Service) naleŜy:
1. Wybrać  przestrzeń  adresową  dla danego zasobu
2. PrzełoŜyć  nazwę  zasobu na identyfikator komunikacyjny
Przestrzeń  adresowa moŜe być  strukturalna (np. hierarchiczna) lub płaska
Usługi nazewnicze – przekształcanie identyfikatorów z jednej przestrzeni na inną. W
ich zakres wchodzi:
  Rejestrowanie nowych nazw
  Usuwanie nieaktualnych nazw
  Dokonywanie przekładu jednej nazwy na inną
Jest to zarządzanie bazą  danych nazw Tłumaczenie nazwy moŜe być  wielostopniowe
(jak w QNX6).
Komunikacja
Składowe  systemu  rozproszonego  są  rozdzielone  a  zatem  muszą  się  komunikować.
Zakłada  się  Ŝe  komunikacja  następuje  pomiędzy  parami  procesów.  Wydajność  sys-
temów  rozproszonych  w  decydujący  sposób  zalezy  od  jakości  systemu  komunikacji.
Komunikacja przenosi:

  Dane
  Synchronizację
  Specyfikację  działań
Podstawowa  konstrukcja  –  przekazywanie  komunikatów  (synchronicznych,  asyn-
chronicznych). W komunikacji występują  dwa podstawowe schematy:
  Model klient–serwer
  Model rozsyłania grupowego
Przekazywanie  działań  –  wysyłanie  pomiędzy  procesami  specyfikacji  działań  które
mają  być  wykonane (PosScript, Java).
Struktura oprogramowania
W systemach rozproszonych wyróŜnia się  następujące składniki oprogramowania:
  Usługi   jądra   systemu   -   zarządzanie   pamięcią,   urządzeniami,   komunikacja,

abstrakcja procesu, komunikacja.

Zaplecze programowania rozproszonego – zdalne wywoływanie procedur, komu-

nikacja grupowa

Usługi otwarte – dostęp do zasobów: pliki, urządzenia, tranzakcje, bazy danych,

nazwy

Aplikacje
Struktura oprogramowania systemu rozproszonego:

Utrzymywanie spójności
Rozproszenie zasobów powoduje trudność  w utrzymaniu ich spójności. WyróŜniamy
następujące rodzaje spójności:
  Spójność  aktualizacji
  Spójność  zwielokrotnienia
  Spójność  pamięci podręcznej
  Spójność  czasu
  Spójność  awarii

Budowa systemu rozproszonego
System ściśle powiązany
System luźno powiązany

System ściśle powiązany (ang. tightly coupled)
System globalnie zarządza wszystkimi zasobami systemu rozproszonego. Ten typ
projektowany zwykle dla wieloprocesorów i wielokomputerów homogenicznych.
KaŜdy komputer posiada lokalny system operacyjny z własnym jądrem.

Usługi warstwy pośredniej:
  Komunikacja
  Usługi nazewnicze
  Jednolity dostęp do zasobów

23. Komunikacja grupowa grupy, adresowanie grupowe, synchroniczność

wirtualna, algorytm BCAST.

Rodzaje komunikacji
Składowe  systemu  rozproszonego  są   rozdzielone  tak  logicznie  jak  fizycznie.  Aby
mogły  one  współdziałać  muszą  się  komunikować.  Istnieją  dwa  powszechnie  stoso-
wane schematy komunikacji:
  Punkt - punkt
  Rozsyłanie grupowe

Grupa  –  zbiór  procesów  działających  wspólnie  w  sposób  określony  poprzez  system
lub uŜytkownika.
  Komunikacja punkt – punkt jest powszechnie stosowana w modelu klient-serwer
  Komunikacja   grupowa   stosowana   w   systemach   rozproszonych   (tolerowanie

uszkodzeń, przetwarzanie równoległe, wyszukiwanie informacji, zwielokrotnione
aktualizacje)

Komunikacja klient serwer
Zorientowany na dostarczanie usług. WyróŜnia się  następujące etapy:
1. Klient wysyła do serwera komunikat z zamówieniem
2. Serwer realizuje zamówienie
3. Odpowiedź  przesyłana jest do klienta
Komunikacja  między  para  procesów  obejmuje  działania  po  stronie  procesu
nadawczego i odbiorczego. Są  to:
  Przenoszenie danych
  Synchronizacja
Rodzaje komunikacji ze względu na ciągłość  danych:
  Dwukierunkowy strumień  (ang. stream) – brak separacji danych, przykład: TCP
  Komunikat (ang. message) – dane są separowane, przykład: UDP

Adresowanie
W  systemach  rozproszonych  dąŜy  się  do  uzyskania  przeźroczystości  połoŜenia  adre-
sów.  Adresowanie  odbywa  się  w  sposób  symboliczny.  Odwzorowanie  adresu  symbo-
licznego  na  fizyczny  wykonywane  jest  przez  odpowiednie  warstwy  oprogramowania.
Usługi mogą  być  przemieszczane bez powiadamiania klientów.

Komunikacja połączeniowa i bezpołączeniowa

Komunikacja połączeniowa
1. Dwa procesy ustanawiają  połączenie w którym występuje informacja adresowa
2. Wymieniają  dane uŜywając tylko identyfikatora połączenia
3. Rozłączają  się
Często połączenie jest kontrolowane w sensie:
  MoŜliwości przesyłania danych
  Poprawności danych
Komunikacja bezpołączeniowa
W kaŜdym przesłaniu występuje pełna informacja adresowa

24. Komunikacja rozproszona poprzez zdalne wywoływanie procedur RPC,
zasady, łącznik, adresowanie, jezyk XDR, tworzenie aplikacji przy pomocy
makrogeneratora rpcgen.

RPC – ZDALNE WYWOŁYWANIE PROCEDUR (ang. Remote Procedure Calls)

Koncepcja
Model klient serwer pozwala na rozwiązanie szerokiej klasy problemów, posiada
jednak ograniczenia:
  Odwołanie się  do wejścia / wyjścia (receive / send)
  Występuje problem reprezentacji danych (systemy heterogeniczne)
  Model zorientowany na dane

Lokalne wywołanie procedury

Zdalne wywołanie procedury

Właściwości zdalnych wywołań procedur:
Definicja procedury powinna określić które parametry są wejściowe, które wyj-

ściowe a które przekazują dane w obydwu kierunkach. W języku C par. przeka-
zywane przez odniesienie tego nie specyfikują.

Procedura wywołująca i wywoływana działają na róŜnych maszynach w róŜnych

przestrzeniach adresowych. Występuje problem z uŜyciem wskaźników. Zmienne
globalne nie mogą być wykorzystane.

Maszyny mogą mieć róŜne systemy reprezentacji danych – naleŜy dokonać

konwersji i serializacji danych.

  Występuje problem obsługi sytuacji awaryjnych
Łącznikami aplikacji klienta i serwera są
  Stopka klienta (ang. client stub) - reprezentuje serwer po stronie klienta
  Stopka serwera (ang. server stub) - reprezentuje klienta po stronie serwera
Zdalne wywołanie procedury odbywa się  w krokach:
1. Aplikacja klienta wywołuje stopkę  klienta
2. Stopka klienta buduje komunikat i przechodzi do jądra OS
3. Jądro przesyła komunikat do jądra maszyny odległej
4. Stopka serwera rozpakowuje parametry i wywołuje serwer
5. Serwer wykonuje zdalną  procedurę  i zwraca wynik stopce serwera
6. Stopka pakuje wyniki w komunikat i przesyła do maszyny klienta
7. Jądro klienta przekazuje komunikat stopce klienta
8. Stopka klienta rozpakowuje wynik i zwraca go klientowi

Przebieg zdalnego wywołania procedury

Obsługa sytuacji wyjątkowych
System RPC jest systemem działającym w środowisku sieciowym a zatem naleŜy się
liczyć  z  trudnościami  komunikacyjnymi.  PoniewaŜ  dowolne  wywołanie  RPC  moŜe  się
skończyć  niepowodzeniem  wymagane  jest  informowanie  strony  wywołującej  o  błę-
dach i obsługa sytuacji wyjątkowych. Obsługa moŜe być  oparta o:
  Zwracanie kodu błędów przez procedury
  Obsługę  wyjątków ( konstrukcje jak np. try {...} catch {...} )
Gdy  zdalna  procedura  ma  zwrócić  jakiś  wynik  powstaje  problem  jak  odróŜnić  ten
wynik od kodu powrotu. NaleŜy zastosować  mechanizm wyjatku.
Typy awarii:
1. Klient nie moŜe zlokalizować  serwera
2. Zaginął  komunikat zamawiający od klienta do serwera
3. Zaginęła odpowiedź  od serwera do klienta
4. Serwer uległ awarii po otrzymaniu zamówienia
5. Klient uległ awarii po wysłaniu zamówienia

Wiązanie dynamiczne
Przy  zdalnym  wywoływaniu  procedur  powstaje  pytanie  jak  klient  ma  zlokalizować
procedury serwera.
Wiązanie  (ang.  binding)  –  odwzorowanie  nazwy  (procedury  RPC)  w  konkretny
obiekt  określony  identyfikatorem  komunikacyjnym.  Postać  identyfikatora  zaleŜy  od
systemu (np. adres gniazdka - IP, port).
Łącznik  (ang.  binder)  –  specjalna  usługa  RPC  utrzymująca  tablicę   odwzorowań
nazw usług (procedur RPC) na porty serwerów tych usług. Łącznik utrzymywany jest
przez serwery które udostępniają  identyfikatory portów swoim klientom.
Funkcje interfejsowe łącznika

Funkcje interfejsowe łącznika:
  void Rejestruj(NazwaUsługi, PortSerwera, Wersja)
  void Usuń(NazwaUsługi, PortSerwera, Wersja)
  int Szukaj(NazwaUsługi, PortSerwera, Wersja)

Od  usług  łącznika  zaleŜą  wszystkie  inne  usługi.  Dlatego  łączniki  tworzy  się  tak  aby
tolerowały  awarie.  Np.  tablice  odwzorowań  zapisuje  się  w  pliku  z  którego  mogą  być
one wczytane w przypadku awarii.
Lokalizowanie łącznika
Zanim klient RPC zrobi cokolwiek musi skontaktować  się  z łącznikiem. Skąd ma znać
jego lokalizację? Stosowane są  rozwiązania:
1. Łącznik działa na komputerze którego adres jest dobrze znany. Gdy jego lokaliza-
cja się  zmieni wymagana jest rekompilacja klientów.
2.  Za  dostarczanie  aktualnego  adresu  łącznika  odpowiada  system  operacyjny  kom-
putera klienta i serwera. MoŜna go utrzymywać  w postaci zmiennej środowiskowej.
3. Rozpoczynając swoje działanie programy klienta lub serwera lokalizuje łącznik za
pomocą  rozgłaszania. Komunikat rozgłaszający zawierać  moŜe numer portu łącznika
a łącznik odpowiada adresem IP komputera na którym się  znajduje.

Standard XDR - przekazywanie parametrów
ile = read(int fd, char * bufor, int ile)
Przekazywanie parametrów w języku C:
  Przez wartość  - wartość  zmiennej kopiowana na stos
  Przez odniesienie - adres zmiennej kopiowany na stos
Maszyny  mogą  się  róŜnić  sposobem  reprezentacji  danych (big  endian,  little  endian,
ASCII, EBDIC, Unicode). Stąd konieczność  konwersji do postaci kanonicznej. Pakowanie
parametrów  do  komunikatu  –  przetaczanie  danych  (ang.  Parameters Marshalling).
Jedną  z  metod  rozwiązania  problemu  jest  opracowany  w  firmie  Sun  system  XDR
(ang. eXternal Data Reprezentation).
Własności:
  XDR umoŜliwia reprezentację  danych w sposób niezaleŜny od komputera.
  Jest to język opisu danych i narzędzie do ich konwersji.
  Nie jest zaleŜny od Ŝadnego szczególnego języka.

XDR stosuje konwencje:
  Liczby całkowite kodowane jako „big Indian” – starsze bajty mają  niŜsze adresy
  Liczby rzeczywiste kodowane w formacie IEEE
  Typy danych mają zawsze wielokrotność  4 bajtów (krótsze wypełniane zerami)
  Konwersja i dekodowanie prowadzone są zawsze
  Obowiązkiem nadawcy i odbiorcy jest znać  typy przekazywanych danych

Kodowanie i dekodowanie prowadzi się za pomocą funkcji XDR

Potok XDR – ciąg bajtów w którym dane reprezentowane są  w postaci XDR. Są  trzy
typy potoków: standardowe wejście wyjście, w pamięci, komunikaty.
Filtr  XDR  –  procedura  kodująca  lub  dekodująca  określony  typ  danych  (liczba  cał-
kowita, rzeczywista, znak, tablica). Filtry XDR piszą  i czytają  dane z potoku.

Filtry XDR
Filtry proste – umoŜliwiają konwersję typów prostych: char, int, long, float, do-

uble

Filtry złoŜone - umoŜliwiają konwersję typów złoŜonych: string, opaque, bytes,

vector, array, union, reference, pointer

Język opisu interfejsu RPCGEN
RPCGEN jest językiem definiowania interfejsu i prekompilatorem. Na podstawie de-
finicji interfejsu RPCGEN tworzy następujące pliki w języku C:
1. Stopka klienta (ang. client stub)
2. Stopka serwera (ang. server stub)
3. Plik konwersji danych
4. Plik nagłówkowy

Aby utworzyć  aplikację  RPC naleŜy:
1.  Utworzyć  w  języku  RPCGEN  plik  interfejsu  opisujący  funkcje  które  mają  być  za-
implementowane. Nadać  numery programu, wersji i funkcji.
2. Skompilować  plik interfejsu za pomocą  programu rpcgen. W rezultacie utworzo- ny
zostanie plik nagłówkowy, plik filtrów XDR, stopka klienta i stopka serwera.
3.  Napisać  program  klienta  korzystając  z  definicji  funkcji  klienta  podanych  w  pliku
nagłówkowym.
4.  Utworzyć  plik  serwera  korzystając  z  definicji  funkcji  serwera  podanych  w  pliku
nagłówkowym. Dokonać  implementacji tych funkcji.
5. Skompilować  plik klienta, stopki klienta, filtrów XDR i połączyć  w program klienta.
6. Skompilować  plik serwera, stopki serwera, filtrów XDR i połączyć  w program ser-
wera.

Przekazywanie argumentów:
1. Wywołanie odległej procedury dopuszcza tylko jeden argument wywołania i zwra- ca
jeden wynik.
2. Gdy występuje więcej elementów to naleŜy umieścić je w strukturach.

3. W programach klienta i serwera argumentem lub wynikiem jest wtedy wskaźnik
na strukturę.

Tworzenie aplikacji przy pomocy prekompilatora RPCGEN

Komunikacja między klientem a serwerem
Komunikacja pomiędzy klientem a serwerem odbywa się  za pomocą  protokołów TCP
lub UDP.
Adresowanie w RPC:
  Nazwa (adres IP) komputera na którym uruchomiony jest serwer
  Numer programu
  Numer wersji
  Numer procedury
Aby móc skorzystać  z RPC naleŜy uruchomić  program łącznika portmap. Procedury
zdalne na danym komputerze są  identyfikowane przez trzy liczby:
  numer programu,
  numer wersji programu
  numer procedury.
Numer programu i wersji – identyfikuje procesy serwerowe. Numery procedur iden-
tyfikują  procedury w serwerze.
Portmapper RPC  jest serwerem, który zamienia numery programu RPC na numery
portów  protokołu  TCP  albo  UDP.  Musi  być  on  uruchomiony,  aby  móc  uŜywać  na  tej
maszynie  odwołań  RPC  do  serwerów  RPC.  Kiedy  serwer  RPC  jest  startowany,  poin-
formuje  on  portmapper  na  których  portach  nasłuchuje,  i  jakimi  numerami  progra-
mowymi RPC  moŜe  słuŜyć.  Kiedy  klient  chce  odwołać  się  przez  RPC  do  danego  nu-