SYSTEMY ROZPROSZONE

1. Procesy i wątki.

1.1 Procesy.

 

Procesem nazywamy program sekwencyjny, który jest wykonywany (jest w trakcie wykonywania). Proces jest sekwencją zmian systemu komputerowego, które zachodzą zgodnie z algorytmem zapisanym w programie. Aby zaistniała możliwość wykonywania procesu, niezbędne są dwa urządzenia, tj. procesor, którego zadaniem jest wykonywanie operacji zgodnych z algorytmem oraz pamięć operacyjna, w której przechowywany jest kod (algorytm) programu. Przykładem procesu skończonego może być np. rozwiązanie równania matematycznego, a zakończenie procesu następuje w chwili uzyskania wyniku (zgodnie z algorytmem). Natomiast przykładem procesu nieskończonego może być system operacyjny, którego podstawową cechą jest praca ciągła i nie może dojść do sytuacji, kiedy nagle system operacyjny przestanie działać i zaprzestanie przyjmowania komend od użytkownika. W przypadku, kiedy jeden proces jest wykonywany przed rozpoczęciem drugiego, mówimy o procesach współbieżnych. Doskonałym przykładem jest właśnie system operacyjny, w którym procesy składające się na działanie systemu operacyjnego wykonywane są współbieżnie z procesami inicjowanymi przez użytkownika. Procesy mogą ze sobą współpracować lub być niezależne. Aby działanie wielu procesów możliwe było na maszynie posiadającej jeden procesor, konieczny jest przydział czasu, w jakim może być dany proces wykonywany. Dzieje się tak dlatego, że w danej chwili procesor jest w stanie wykonywać jeden proces. Przydzielanie czasu umożliwia wykonywanie procesów sekwencyjnie, niejako po kawałku procesu, w ustalonych przedziałach czasu przypadających na dany proces. W ten sposób możliwa jest praca wieloprocesowa na maszynie jednoprocesowej. Działanie współbieżne bezpośrednio wiąże się ze wzrostem wydajności. Na stacjach wieloprocesorowych każdy proces wykonywany jest na innym procesorze i jeśli ilość procesów nie przekracza ilości procesorów, wówczas nie ma potrzeby stosowania przydziału czasu.

Stan procesu określa się następująco:

ü  running - wykorzystywany jest kod procesu, proces jest w trakcie wykonywania

ü  waiting – oczekiwanie (zablokowanie), proces czeka na wystąpienie ustalonego zdarzenia

ü  ready – proces czeka na przydział procesora, resztę zasobów ma przydzielone

W danym momencie tylko jeden proces może być aktywny, natomiast może istnieć wiele procesów oczekujących lub gotowych. Możliwość wykonywania współbieżnego procesów pociąga za sobą konieczność zbudowania jednostki odpowiedzialnej za tworzenie i kończenie procesów. Proces może utworzyć nowy proces. Jest to możliwe za pomocą funkcji systemowej create. Proces taki nazywa się procesem macierzystym, natomiast proces przez niego utworzony nazywamy procesem potomnym. Proces macierzysty może pracować równocześnie ze swymi procesami potomnymi (które zresztą również mogą tworzyć swoje procesy potomne) lub oczekiwać na wykonanie wszystkich czynności, które miały wykonać podprocesy i dalej kontynuować działanie. Tworzenie procesów potomnych wiąże się jednak z koniecznością przydzielania nowych zasobów, które może otrzymać od systemu operacyjnego lub od procesu macierzystego. Ilość zasobów jest więc ograniczona. Ponadto ilość procesów ograniczona zostaje poprzez rozmiar tablicy rozkazów. Proces potomny nie może zostać zakończony dopóki, dopóty nie wykona wszystkich zaprogramowanych czynności. Następnie proces potomny przekazuje swoje informacje swojemu „przodkowi” poprzez wywołanie funkcji exit. Ten z kolei wywołując funkcję abort powoduje zakończenie procesu potomnego. Istnieją również inne możliwości zakończenia działania procesu potomnego. Ma to miejsce w przypadku, kiedy podproces nadużył przydzielonych zasobów, bądź stwierdzono, że jego działanie jest już zbędne. Współczesne systemy operacyjne zapewniają ponadto automatyczne zakończenie procesów potomnych, jeśli nie działa już proces macierzysty (zakończenie kaskadowe).

Wspomniany wcześniej proces niezależny charakteryzuje się tym, że wyniki działania innych procesów nie wpływają w żaden sposób na jego działanie. W takim przypadku stan procesu nie jest w żaden sposób współdzielony z innymi procesami. Wynik działania takiego procesu jest zależny wyłącznie od jego danych początkowych, czyli wielokrotne działanie procesu z identycznymi danymi wejściowymi spowoduje uzyskanie zawsze takich samych danych wynikowych. Ponadto zatrzymywanie i ponowne uruchamianie procesu nie powoduje żadnych zmian.

Proces współpracujący charakteryzuje się tym, iż może wpływać na działanie innych procesów, bądź sam jest zależny od innych procesów. Stan takiego procesu może być współdzielony i innymi procesami. Nie można przewidzieć wyniku działania takiego procesu, ponieważ jest on zależny od innych procesów, ponadto nawet przy tych samych danych wejściowych można uzyskać różne wyniki (nie można przewidzieć działanie innych procesów, z którymi dzielone są zasoby).

1.2 Wątki.

 

Wątek to podstawowa jednostka wykorzystująca procesor (inaczej nazywany lekkim procesem). Wątkami nazywa się takie procesy, które są wykonywane we wspólnej przestrzeni adresowej. Jest dynamiczną częścią procesu, która zawiera licznik rozkazów, rejestry oraz stos. Wątki współdzielą pomiędzy sobą przestrzeń adresową, kod i zasoby systemu operacyjnego. W systemach wieloprocesorowych wątki umożliwiają wykorzystanie przez proces wszystkich procesorów. Stosowanie wątków w programach owocuje zwiększona efektywnością działania a także pozwala na uproszczenie struktury programu. Używanie wątków przyśpiesza działanie programu, ponieważ przełączanie pomiędzy wątkami jest szybsze niż pomiędzy procesami wykorzystującymi jeden wątek, co wiąże się z obniżeniem kosztów.

Wątki charakteryzują się następującymi cechami:

ü  wykonywane są sekwencyjnie

ü  każdy wątek posiada własny licznik rozkazów i stos

ü  w systemach jednoprocesorowych podobnie jak procesy dzielą pomiędzy sobą czas przydziału do procesora

ü  w systemach wieloprocesorowych wykonywane są równolegle (jeden wątek na jednym procesorze)

ü  podobnie jak procesy mogą tworzyć wątki pochodne

ü  posiada dostęp do dowolnego adresu w zakresie procesu, więc może pracować na stosie innego wątku

ü  informacja o stanie wątku zajmuje niewielką ilość pamięci

ü  wątki mogą znajdować się w jednym z trzech stanów: zawieszony, wykonywany, zakończony

ü  wątki nie współzawodniczą między sobą

 

1.3 Wątki a zdalne wywoływanie procedur.

Jedną z najpopularniejszych form usługi zdalnej jest wzorzec postępowania określany jako RPC, czyli zdalne wywoływanie procedury. Wywołanie RPC zaprojektowano jako sposób uogólnienia mechanizmu wywołania procedury na użytek systemów połączonych siecią. Pod wieloma względami jest ono podobne do mechanizmu komunikacji międzyprocesowej. W przeciwieństwie do komunikacji międzyprocesowej komunikaty wymieniane w trybie RPC mają ściśle określoną budowę i nie są już zwykłymi pakietami danych. Są one adresowane do demona RPC, który prowadzi nasłuch portu RPC w odległym systemie i zawierają identyfikator funkcji do wykonania, jak również parametry, które należy jej przekazać. Funkcja taka zostanie następnie wykonana zgodnie z życzeniem, a wszystkie wyniki będą odesłane do zamawiającego w oddzielnym komunikacie. System zazwyczaj posiada tylko jeden adres sieciowy, ale może pod tym adresem udostępniać wiele portów (port jest numerem umieszczonym na początku pakietu z komunikatem), aby rozróżniać swoje liczne usługi sieciowe. Jeśli proces zdalny potrzebuje obsługi, to adresuje komunikat do właściwego portu. Mechanizm RPC jest powszechnie stosowany w systemach sieciowych. Jednym z istotnych związanych z nim zagadnień jest semantyka wywołania. Procedura lokalna ulega awarii jedynie w wyjątkowych sytuacjach, natomiast wywołania RPC mogą zawodzić albo być podwajane i wykonywane więcej niż jednokrotnie z powodu typowych niedomagań sieci. Ponieważ często mamy do czynienia z przesyłaniem komunikatów przez zawodne łącza komunikacyjne, więc z tego powodu łatwiej jest zapewniać w systemie operacyjnym co najwyżej jednokrotne wystąpienie danego komunikatu, niż gwarantować, że komunikat pojawi się dokładnie jeden raz. Inne ważne zagadnienie dotyczy komunikacji między serwerem a klientem. W standardowych wywołaniach procedur dochodzi do wiązań podczas konsolidacji, ładowania lub wykonywania, co powoduje, że nazwa wywołania procedury jest zastępowana przez adres wywołania danej procedury w pamięci.

W systemach rozproszonych równie częste zastosowanie jak zdalne wywołania procedur znajdują wątki. Nadają się one do wysyłania i przyjmowania komunikatów w sposób umożliwiający asynchroniczne wykonywanie innych operacji w zadaniu. Ułatwiają one zaprogramowanie i zwiększenie wydajności docelowego procesu, co z kolei pozwala na obsługiwanie zamówienia od początku do końca w jednym wątku i jednoczesne wykonywanie przez jego sąsiadów tych samych czynności w odniesieniu do innych zamówień.   

 

1.4 Szeregowanie procesów, podstawowe algorytmy szeregowania
i ich własności.

 

Właściwe przydzielanie procesorów i decydowanie o kolejności wykonywania procesów należy do podstawowych zadań systemu operacyjnego. System operacyjny posiada odpowiednie moduły rozwiązujące ten problem. Procesy, których status jest określony jako gotowy umieszczane są w kolejce. Z reguły to procesy systemowe obsługiwane są niejako „poza kolejnością”, natomiast konkurujące między sobą procesy użytkowników obsługiwane zostają zgodnie z pewnymi regułami.

Istnieją trzy podstawowe etapy szeregowania:

ü  wysoki – określa kolejkę zadań, które chcą skorzystać z zasobów systemu

ü  pośredni – obsługa procesów, które posiadają status gotowy lub zawieszony

ü  niski – decyduje któremu procesowi będącemu w stanie gotowości zostaje przydzielony procesor

Podstawą procesu szeregowania są tzw. kolejki zadań, do których trafiają zadania lub procesy. Proces po wprowadzeniu do systemu trafia do kolejki zadań. Kolejka zawiera wszystkie procesy oczekujące na przydział pamięci. Jest on następnie w odpowiedni sposób porządkowana. Kolejka ta związana jest wysokim poziomem szeregowania.
W kolejnym kroku tworzona jest kolejka procesów gotowych (poziom niski). W tej kolejce zapada decyzja, któremu z gotowych procesów przydzielony zostanie procesor.

Algorytmy szeregowania dzielą się pod względem cech ich działania:

ü  efektywność – utrzymywanie pełnego obciążenia procesora

ü  przepustowość – polega na wymuszeniu wykonania jak największej ilości obliczenie w jednostce czasu

ü  czas oczekiwania – minimalizowanie czasu oczekiwania użytkownika na wyniki działania ich zadań

ü  czas odpowiedzi – minimalizacja czasu odpowiedzi dla użytkowników interakcyjnych

Algorytmy przydziału procesora podzielić można również na algorytmy z wywłaszczaniem i bez wywłaszczania. Pierwszy z nich charakteryzuje się tym, iż procesor może zostać odebrany procesowi nawet w trakcie jego wykonywania, natomiast w drugim przypadku proces utrzymuje procesor aż do jego zakończenia

Algorytm FCFS (First Come First Served).

Jak wskazuje nazwa obsługuje najpierw te procesy, które zostały w pierwszej kolejności wprowadzone do kolejki. Nie jest dobrym algorytmem, ponieważ w przypadku, kiedy w kolejce znajduje się jakiś duży proces, który będzie wymagał długiego czasu na jego zrealizowanie, powstanie blokada na czas wykonywania tego procesu, więc inne procesy w kolejce będą musiały długo czekać. Jest nieprzydatny w systemach interakcyjnych z podziałem czasu, natomiast jest często stosowany w systemach, w których procesy posiadają taki sam priorytet. Jest algorytmem bez wywłaszczania.

Algorytm SJF (Shortest Job First) - szereguje zadania zgodnie z porządkiem określonym przez czasy ich wykonywania - najpierw wykonywane jest zadanie najkrótsze. Algorytm więc faworyzuje zadania krótkie. Udowodniono, że jest to algorytm optymalny ze względu na średni czas przebywania procesów w systemie. Wadą tego algorytmu jest to, iż zadanie wymagające długiego obsługiwania przez procesor długo czekają na swoje wykonanie.

Algorytmy priorytetowe - każdemu procesowi przydziela się pewien priorytet, po czym procesor przydziela się temu procesowi, którego priorytet jest najwyższy. Procesy o równych priorytetach są porządkowane na ogól według algorytmu FCFS. Priorytety mogą być definiowane w sposób statyczny lub dynamiczny oraz mogą być przydzielane dynamicznie po to, aby osiągnąć określone cele systemowe, np. jeśli specjalny proces zażąda przydziału procesora, powinien go otrzymać natychmiast. Planowanie priorytetowe może być wywłaszczające lub niewywłaszczające. Podstawowym problemem w planowaniu priorytetowym jest stałe blokowanie (ang. indefinite blocking, starvation, livelock).

Algorytm rotacyjny - procesor jest przydzielany zadaniom kolejno na określony odcinek czasu (kwant). Kwant czasu przydziału procesora jest najczęściej rzędu 10 do 100 msek. Kolejka procesów gotowych jest traktowana jak kolejka cykliczna - nowe procesy są dołączane na koniec kolejki procesów gotowych. W przypadku, kiedy proces ma fazę procesora krótszą niż przydzielony kwant czasu, to wówczas z własnej inicjatywy zwalnia procesor. Jeśli faza procesora procesu jest dłuższa niż przydzielony kwant czasu, to nastąpi przerwanie zegarowe i przełączenie kontekstu, a proces przerwany trafia na koniec kolejki. Podstawowym problemem przy konstrukcji algorytmu RR jest określenie długości kwantu czasu. (jeśli kwant czasu jest bardzo mały to algorytm RR nazywa się dzieleniem procesora).

Algorytm wielopoziomowego planowania

Kolejkę procesów gotowych rozdziela się na kilka kolejek, z reguły w zależności od procesu. Procesy zostają na stałe przydzielone są do tych kolejek. Każda kolejka ma własny alg. planowania. Najczęściej jest to implementowane jako dwie kolejki: procesy pierwszoplanowe (alg. rotacyjny) i drugoplanowe (alg. FCFS). Musi istnieć alg. planowania między kolejkami. Stałopriorytetowe planowanie wywłaszczające: każda kolejka ma bezwzględne pierwszeństwo przed kolejkami o niższych priorytetach tzn., że żaden z procesów z kolejki o danym priorytecie nie może pracować dopóki kolejki znajdujące się nad tą kolejką nie są puste. Jeśli podczas wykonywania procesu do systemu zostanie wprowadzony nowy proces o wyższym priorytecie, to aktualnie wykonywany proces zostanie wywłaszczony; Planowanie ze sprzężeniem zwrotnym: pomiędzy kolejki rozdziela się procesy o różnych fazach procesora. Jeśli proces używa zbyt dużo czasu procesora, to zostaje przesunięty do kolejki o niższym priorytecie. Proces zbyt długo oczekujący w kolejce i niskim priorytecie może zostać przeniesiony do kolejki o wyższym priorytecie. Rozwiązuje to problem głodzenia procesów.

1.4 Projekt laboratoryjny - Budowa prostej aplikacji wielowątkowej w języku C.

 

 

 

2. Problem wzajemnego wykluczania.

2.1 Pojęcie sekcji krytycznej, protokół wstępny i protokół końcowy.

 

Procesy współbieżne mogą ze sobą współzawodniczyć o dostęp do wspólnie użytkowanych zasobów. Chodzi tu o takie zasoby, które w danej chwili mogą być wykorzystywane tylko przez jeden proces (lub ograniczoną ich liczbę, mniejszą od liczby chętnych). Jest to sytuacja dość często spotykana w życiu. Każdemu zdarzyło się, że chciał skorzystać z łazienki właśnie wtedy, gdy była ona zajęta, zadzwonić, gdy ktoś już rozmawiał przez telefon. Skądinąd wiadomo, że w każdej takiej sytuacji trzeba po prostu zaczekać (na zwolnienie łazienki, zakończenie rozmowy). Natomiast wtedy, gdy dwie osoby jednocześnie chcą wejść do pustej łazienki, zadzwonić z tego samego telefonu, trzeba zastosować zasadę uprzejmości i dobrych obyczajów. W teorii procesów współbieżnych wspólny obiekt, z którego może korzystać w sposób wyłączny wiele procesów (np. łazienka, telefon) nazywa się zasobem dzielonym, natomiast fragment procesu, w którym korzysta on z obiektu dzielonego (mycie się, telefonowanie), nazywa się sekcją krytyczną tego procesu. Ponieważ w danej chwili z obiektu dzielonego może korzystać tylko jeden proces, wykonując swoją sekcję krytyczną uniemożliwia on wykonanie sekcji krytycznych innym procesom. Problem wzajemnego wykluczania definiuje się następująco: zsynchronizować N procesów, z których każdy w nieskończonej pętli na przemian zajmuje się własnymi sprawami i wykonuje sekcję krytyczną, w taki sposób, aby wykonanie sekcji krytycznych jakichkolwiek dwóch lub więcej procesów nie pokrywało się w czasie. Aby ten problem rozwiązać, należy do treści każdego procesu wprowadzić, dodatkowe instrukcje poprzedzające sekcję krytyczną (nazywa się je protokołem wstępnym - przy wejściu do sekcji proces wykonuje protokół wejścia w którym sprawdza czy może wejść do sekcji krytycznej.) i instrukcje następujące bezpośrednio po sekcji krytycznej (protokół końcowy - po wyjściu z sekcji wykonuje protokół wyjścia aby poinformować inne procesy ze opuścił już sekcje krytyczna i inny proces może ja zająć.). Protokół wstępny i końcowy to po prostu programowa realizacja czekania i stosowanej w życiu zasady uprzejmości.

2.2 Blokada i zagłodzenie procesu.

Blokada.

Powiemy, że zbiór procesów znajduje się w stanie blokady, jeśli każdy z tych procesów jest wstrzymany w oczekiwaniu na zdarzenie, które może być spowodowane tylko przez jakiś inny proces z tego zbioru. Zjawisko blokady, zwane także zastojem, zakleszczeniem lub martwym punktem, jest przejawem braku bezpieczeństwa programu, jest to bowiem stan niepożądany. Zjawisko to może wystąpić również w systemie złożonym z procesów, które są powiązane jedynie przez to, że korzystają z tych samych zasobów komputera. Zauważmy, że jeśli w jakimś programie współbieżnym może wystąpić blokada, nie oznacza to, że wystąpi ona przy każdym wykonaniu tego programu. Dlatego testowanie nie jest dobrą metodą stwierdzania, czy dany zbiór procesów może się zablokować. Czasami unikanie blokady może być bardzo kosztowne. Jeśli jej wystąpienie jest mało prawdopodobne, lepiej godzić się na nią, ale trzeba uruchomić mechanizmy jej wykrywanie i usuwania.

 

Zagłodzenie.

Specyficznym przypadkiem nieskończonego wstrzymywania procesu jest zjawisko zagłodzenia zwane także wykluczenie. Jeśli komunikat lub sygnał synchronizacyjny może być odebrany tylko przez jeden z nań procesów, powstaje problem, który z procesów wybrać. Zjawisko zagłodzenia występuje wówczas, gdy proces nie zostaje wznowiony, mimo że zdarzenie, na które czeka, występuje dowolną liczbę razy. Za każdym razem, gdy proces ten mógłby być wznowiony, jest wybierany jakiś inny czekający proces. Zagłodzenie jest przejawem braku żywotności programu. Zależy ono od strategii wznawiania procesów. Jeśli procesy będą wznawiane zawsze w kolejności, w jakiej zostały wstrzymane (kolejka prosta), to zjawisko zagłodzenia nie wystąpi. Jeśli jednak o kolejności wznawiania decydują priorytety procesów (kolejka priorytetowa), to jest możliwe, że procesy o niższym priorytecie zostaną zagłodzone przez procesy o wyższym priorytecie. O ile istnieją algorytmy pozwalające wykrywać zjawisko blokady w trakcie wykonywania programu, o tyle wykrycie zagłodzenia jest praktycznie niemożliwe. Łatwo, co prawda zaobserwować, że pewien proces czeka bardzo długo na jakieś zdarzenie, które wystąpiło już wiele razy, ale nie wiadomo, jak system zachowa się w przyszłości. Można natomiast wykazać, że w programie współbieżnym jest możliwe zagłodzenie, przez pokazanie nieskończonego ciągu zdarzeń w tym programie, w wyniku którego jeden proces (lub więcej) pozostanie na zawsze wstrzymany.

2.3 Wzajemne wykluczanie dla dwóch procesów (N procesów) – operacje czytaj – zapisz do wspólnej pamięci.

Wzajemne wykluczanie - wymaganie aby ciąg operacji na pewnym zasobie (zwykle pamięci) był wykonany w trybie wyłącznym przez tylko jeden z potencjalnie wielu procesów. Problem wzajemnego wykluczania pojawia się w systemie w momencie gdy istnieje w nim choć jeden zasób niepodzielny; to znaczy, że zasobu tego może używać w danym czasie tylko jeden proces. Jeżeli inny proces zamawia dany zasób, to proces ten musi być opóźniany do czasu, aż zasób zostanie zwolniony. Najszybszym sposobem wymieniania danych pomiędzy procesami jest współdzielenie przez nie pewnego obszaru pamięci. W ten sposób dane umieszczone przez nadawcę są natychmiast dostępne dla odbiorcy. Jednak by zapewnić, prawidłowe odczytywanie
i zapisywanie współdzielonych danych należy wprowadzić mechanizmy, które ograniczą do nich dostęp tak by w jednym momencie operacje na danych wykonywał wyłącznie jeden proces. Jest to jeden z przykładów problemu wzajemnego wykluczania. Dany jest zbiór procesów sekwencyjnych komunikujących się przez wspólną pamięć. Każdy z procesów zawiera sekcję krytyczną , w której następuje dostęp do wspólnej pamięci. Procesy te są procesami cyklicznymi. Zakłada się ponadto:

ü  zapis i odczyt wspólnych danych jest operacją niepodzielną, a próba jednoczesnych zapisów lub odczytów realizowana jest sekwencyjnie w nieznanej kolejności

ü  sekcje krytyczne nie mają priorytetu

ü  względne prędkości wykonywania procesów są nieznane

ü  proces może zostać zawieszony poza sekcją krytyczna

ü  procesy realizujące instrukcje poza sekcją krytyczną nie mogą uniemożliwiać innym procesom wejścia do sekcji krytycznej

ü  procesy powinny uzyskać dostęp do sekcji krytycznej w skończonym czasie

 

 

2.4 Projekt laboratoryjny – Algorytm Petersona.

Jest to rozwiązanie programowe pozbawione wad i można je stosować w systemach rozproszonych. Procesy korzystają z dwóch procedur: wchodzę i wychodzę odnoszących się do sekcji krytycznej. Przed wejściem do sekcji krytycznej proces wywołuje procedurę enter_region z własnym numerem jako parametrem, pokazując w ten sposób innym procesom, że współdzielony zasób jest zajęty. Po wyjściu z sekcji krytycznej proces wywołuje procedurę leave_region z własnym numerem jako parametrem, pokazując w ten sposób innym procesom, że zasób jest wolny. Załóżmy, że proces 0 wywołuje procedurę enter_region i nadaje zmiennej interested wartość true. Proces wskazuje tym samym, że jest zainteresowany wejściem do sekcji krytycznej. Zmienna turn przyjmuje wartość 0 - identyfikator procesu wchodzącego do sekcji krytycznej. Następnie proces wchodzi w pętlę testującą możliwość wejścia do sekcji krytycznej. Testowanie polega na sprawdzeniu, czy konkurencyjny proces nie jest zainteresowany wejściem do sekcji krytycznej. Jeśli nie, to proces 0 wchodzi do sekcji krytycznej. Wychodząc z niej proces wywołuje procedurę leave_region, która ustawia odpowiadającą procesowi zmienną interested na false.

 

 

3. Synchronizacja procesów i wątków.

3.1 Pojęcie sekcji krytycznej.

 

Sekcja krytyczna (SK) to sekwencja rozkazów, której wykonanie, jeśli zostanie rozpoczęte, musi być doprowadzone do końca zanim inny proces wystąpi z żądaniem dostępu do tego wspólnego zasobu. Jeśli jesteśmy w stanie tak zorganizować wykonywanie wielu procesów, że nigdy jednocześnie nawet dwa nie znajdą się w swoich sekwencjach krytycznych, to jesteśmy w stanie ominąć problem sytuacji hazardowej. Instrukcje sekcji krytycznej muszą być ujęte w jakieś „ogrodzenie” gwarantujące spełnienie warunków wzajemnego wykluczania. Ponieważ w danej chwili z obiektu dzielonego może korzystać tylko jeden proces, wykonując swoją sekcję krytyczną uniemożliwia on wykonanie sekcji krytycznych innym procesom.

Mechanizm realizacji sekcji krytycznej powinien spełniać poniższe założenia: 

ü  wewnątrz SK może przebywać tylko jeden proces,

ü  jakikolwiek proces znajdujący się poza SK, nie może zablokować innego procesu chcącego wejść do SK,

ü  każdy proces oczekujący na wejście do SK powinien otrzymać prawo dostępu w rozsądnym czasie

3.2 Narzędzia umożliwiające synchronizację procesów i wątków.

Semafory.

Semafor jest zmienną całkowitą, która z punktu widzenia programisty przyjmuje wartości nieujemne (.0) lub — w przypadku semaforów binarnych — logiczne. Zmienna semaforowa musi mieć nadaną początkową wartość (oczywiście nieujemną). Po nadaniu początkowej wartości zmiennej semaforowej można na niej wykonywać tylko dwie operacje:

P — opuszczanie semafora (hol. proberen testować)

V — podnoszenie semafora (hol. verhogen zwiększać)

Synchronizacja za pomocą semaforów polega na blokowaniu procesu w operacji opuszczania semafora, gdy wartość zmiennej semaforowej jest 0 (false w przypadku semaforów binarnych) do czasu, aż wartość ta zostanie zwiększona.

Rodzaje semaforów:

ü  semafory binarne — zmienna semaforowa przyjmuje tylko wartości true (stan podniesienia) lub false (stan opuszczenia).

ü  semafory ogólne — zmienna semaforowa przyjmuje wartości całkowite nieujemne, a jej bieżąca wartość jest zmniejszana lub zwiększana o 1 w wyniku wykonania odpowiednio operacji opuszczenia lub podniesienia semafora.

ü  semafory uogólnione — semafory ogólne, w których zmienną semaforową można zwiększać lub zmniejszać o dowolną wartość

ü  semafory dwustronnie ograniczone — zmienna semaforowa ma górne ograniczenia po osiągnięciu którego następuje blokowanie procesu również w operacji podnoszenia.

Wady semaforów:

ü  semafor jest wysokopoziomową abstrakcją opartą na niskopoziomowych

mechanizmach elementarnych, które dostarczają niepodzielność i mechanizmy wstrzymywania

ü  wstrzymywanie i wznawianie wymaga przełączania kontekstu i zmian
w kolejkach modułu szeregowania i kolejkę wątków wstrzymanych; operacje na semaforze są powolne

Monitory.

Monitory to konstrukcje zdefiniowane przez programistę w języku wysokiego poziomu służące do synchronizacji procesów. Z tej konstrukcji nie mogą bezpośrednio korzystać dowolne procesy. Mają one tylko dostęp do swych zmiennych lokalnych i wartości parametrów formalnych.

ü  nie wykorzystuje się funkcji systemowych;

ü  nie wykorzystuje się żadnych zmiennych;

ü  jest to technika odpowiedniego oprogramowywania procesów;

ü  podstawowa wada: większość języków wysokiego poziomu nie rozpoznaje konstrukcji monitora;

Konstrukcja monitora gwarantuje, że w jego wnętrzu może być aktywny w jednym czasie tylko jeden proces. W związku z tym programista nie musi kodować barier synchronizacyjnych w sposób jawny. Pozostaje jednak problem synchronizacji wielu monitorów. Mechanizm ich synchronizacji dostarcza konstrukcja pod nazwą warunek. Mianowicie programista może zdefiniować jedną lub kilka zmiennych tego typu. Jedynymi operacjami które mogą dotyczyć warunku są: wait(x) i signal(x). Operacja x.wait oznacza, że proces ją wywołujący zostaje zawieszony aż do chwili gdy inny proces wykona operację x.signal. Operacja x.signal wznawia jeden z zawieszonych procesów, a jeśli żaden z procesów nie jest zawieszony, to operacja ta nie ma żadnych skutków.

W implementacji monitorów konieczne jest posłużenie się wstawkami assemblerowymi i instrukcją TSL lub semaforami aby zagwarantować atomowość operacji wait i signal. Procedury te należy dołączyć do monitorów w trakcie ich kompilacji.

 

3.3 Pojęcie zakleszczenia oraz warunki konieczne, aby zjawisko zakleszczenia wystąpiło.

 

Definicja klasyczna zakleszczenia: (zakleszczenie dotyczy zasobów nieprzywłaszczalnych). Zakleszczenie jest konfliktem zasobowym, który może powstać przy rozdziale zasobów nieprzywłaszczalnych i definiowany jest jako stan rozdziału zasobów w systemie, w którym dokończenie wykonywania pewnych procesów jest niemożliwe ze względu na to, że każdy z nich żąda przydziałów zasobów nieprzywłaszczalnych przydzielonych innemu procesowi.

Definicja uniwersalna zakleszczenia: Zbiór procesów znajduje się 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 procesów - zdarzeniami tymi są najczęściej zwalnianie i przydzielanie zasobów.

Martwy punkt może wystąpić wtedy i tylko wtedy gdy w systemie wystąpią jednocześnie 4 następujące warunki.

Warunki Coffmana zaistnienia stanu zakleszczenia:

1.     Wzajemne wykluczanie (mutual exclusion). W danej chwili czasu jednostka zasobu może być przydzielona tylko do jednego procesu.

2.     Przytrzymywanie w stanie zawieszenia (hold and wait). Proces oczekuje na zwolnienie potrzebnych mu jednostek zasobów, które są przydzielone do innych procesów. Podczas tego oczekiwania proces nie zwalnia dotychczas przydzielonych mu jednostek zasobów.

3.     Bez wywłaszczenia (no preemption). Jednostka zasobu przydzielona do danego procesu może być zwolniona tylko przez ten proces. Inaczej mówiąc proces nie może zostać wywłaszczony wbrew swej woli.

4.     Cykliczne oczekiwanie (circular wait). Łańcuch procesów oczekujących wzajemnie na uwolnienie przydzielonych do nich jednostek zasobów musi się zamknąć, tzn. musi istnieć zbiór {P₀, P₁, ... , P_n} czekających procesów takich, że P_o czeka na zasób przydzielony do P₁, P₁ czeka na zasób przydzielony do P₂, itd., P_n-1 czeka na zasób przydzielony do P_n, a P_n czeka na zasób przydzielony do P₀.

 

Do opisywania martwego punktu powszechnie stosuje się metodę grafów. Zakleszczenie może być opisane precyzyjnie z wykorzystaniem pojęcia grafu skierowanego nazywanego w tym przypadku grafem alokacji zasobów. Graf G = (V,E) składa się ze zbioru wierzchołków V i zbioru krawędzi E. Zbiór wierzchołków jest podzielony na dwa typy.

1.     P = {P₁, P₂, ... , P_n} oznacza zbiór wszystkich procesów wykonywanych aktualnie w systemie.

2.     R = {R₁, R₂, ... , R_m} oznacza zbiór wszystkich typów zasobów występujących w systemie.

Krawędź skierowaną P_i ® R_j będziemy nazywać krawędzią żądań. Oznacza ona, że proces P_i żąda przydziału jednostki zasobu typu R_j. Inaczej mówiąc proces ten aktualnie czeka na przydział tej jednostki. Krawędź skierowaną R_i ® P_j będziemy nazywać krawędzią przydziału. Oznacza ona, że pewna jednostka zasobu typu R_i jest przydzielona aktualnie do procesu P_j. Biorąc pod uwagę definicję grafu oraz teorię grafów można łatwo wykazać, że jeśli graf alokacji zasobów nie zawiera cykli, to wówczas żaden proces w systemie nie znajduje się w stanie zakleszczenia. Z drugiej strony, jeśli graf alokacji zasobów zawiera cykle, to martwy punkt może zaistnieć . Jeśli każdy z typów zasobów zawiera tylko po jednej jednostce danego zasobu, oraz w grafie występują cykle, to oznacza to wystąpienie martwego punktu. Cykl, zgodnie z warunkami Coffmana, jest warunkiem niezbędnym do zaistnienia martwego punktu, natomiast nie jest warunkiem wystarczającym. Jeśli bowiem cykl istnieje, a każdy typ zasobu posiada kilka jednostek, to prawdopodobieństwo wystąpienia martwego punktu gwałtownie spada.

3.4 Projekt laboratoryjny – Problem pięciu filozofów – rozwiązanie za pomocą semaforów i monitora. Analiza przypadku 2, 3 i 4 filozofów.

 

Problem jedzących filozofów jest jednym z najbardziej znanych przykładów nieustającej współbieżności. Mamy stół, wokół którego posadzono pięciu filozofów, których cykl życia składa się z myślenia i jedzenia. Pośrodku stołu stoi duży talerz z nieograniczona ilością spagetti. W połowie odległości pomiędzy dwoma talerzami leży jeden widelec. I tu powstaje problem, ponieważ żaden filozof nie może jeść spagetti jednym widelcem. Gdy zgłodnieje, podnosi widelec, jeśli jest wolny, następnie podnosi drugi. Jeżeli któryś z widelców jest zajęty, filozof czeka. Jedzenie można potraktować, jako rodzaj sekcji krytycznej, gdyż dwóch sąsiadów nie może jeść jednocześnie. W przypadku, kiedy pozwolimy filozofom samowolnie podnosić widelce może się zdarzyć, ze wszystkich pięciu podniesie jeden widelec i będą czekać w nieskończoność. Można zdecydować się na inne rozwiązanie każące filozofowi sprawdzać, czy oba widelce są wolne i dopiero wówczas je podnosić. Może się jednak zdarzyć, że będzie on miął wyjątkowo żarłocznych sąsiadów jedzących na przemian i dojdzie do zagłodzenia. Rozwiązaniem poprawnym jest zatrudnienie lokaja, który będzie pilnował, aby przy stole siedziało tylko czterech filozofów, a pozostały czekał na swoją kolej. Jak któryś z nich skończy, musi opuścić pokój, aby ponownie ustawić się w kolejce. Dowód poprawności rozwiązania opiera się na zasadzie szufladkowej Dirichleta: ponieważ mamy czterech filozofów przy stole, a jest piec widelców, to jeden z nich dostanie dwa widelce. Ponieważ proces jedzenia jest skończony, a potem najedzony filozof musi opuścić stół, jest gwarancja, że czekający w kolejce także zasiądzie do stołu.

 

4. Budowa aplikacji klient – serwer wykorzystującej protokół TCP.

4.1 Architektura systemów rozproszonych, architektura systemów sieciowych – struktura i własności.

Coraz częściej mamy do czynienia z rozdzielaniem obliczeń między wieloma fizycznymi procesorami. Możemy wyróżnić dwa podstawowe schematy budowy takich systemów. Pierwszym z nich jest system wieloprocesorowy, czyli ściśle powiązany, w którym procesory dzielą pamięć i zegar, co powoduje, że komunikacja w nim odbywa się najczęściej poprzez pamięć dzieloną. Drugim z nich jest system rozproszony. Jest to system luźno powiązany, w którym procesory nie dzielą pamięci ani zegara -  każdy procesor posiada własną pamięć lokalną, a komunikowanie między procesorami odbywa się za pomocą różnych sieci komunikacyjnych, takich jak szyny szybkiego przesyłania danych lub linie telefoniczne.   

System rozproszony jest to zbiór luźno powiązanych ze sobą procesorów połączonych za pomocą sieci komunikacyjnej. Dla danego procesora wchodzącego w skład systemu rozproszonego pozostałe procesy i ich zasoby są zdalne, natomiast jego własne zasoby są lokalne. Procesory w systemie rozproszonym mogą różnić się mocą obliczeniową i funkcjami. Mogą znajdować się wśród nich małe mikroprocesory, stacje robocze i wielkie systemy komputerowe ogólnego przeznaczenia. Takie procesory określa się za pomocą kilku różnych nazw, takich jak stanowiska, węzły, komputery, maszyny, komputery sieciowe lub macierzyste. W momencie kiedy zwracamy uwagę na położenie maszyn, wtedy najczęściej używamy terminu stanowisko, gdy odnosimy się do konkretnego systemu w danym miejscu, używamy zaś nazwy komputer (sieciowy). Pewien proces na jakimś stanowisku, który nazywamy serwerem, dysponuje zasobem, którego potrzebuje inny proces na innym stanowisku – klient. Zadanie jakie stawiamy przed systemem rozproszonym jest stworzenie wydajnego i wygodnego środowiska umożliwiającego ten sposób dzielenia zasobów. Rozproszony system operacyjny powinien umożliwić użytkownikom dostęp do różnych zasobów, nad którymi sprawuje nadzór. Poprzez  zasób należy rozumieć zarówno urządzenia sprzętowe, np. drukarki, jak i oprogramowanie – np. pliki, programy, a dostęp do tych zasobów jest nadzorowany przez system operacyjny. Możemy wyróżnić dwa zasadnicze, uzupełniające się schematy dostarczania takich usług:

Sieciowe systemy operacyjne - użytkownicy są świadomi ilości maszyn. W celu dostępu do zasobów są zmuszeni rejestrować się na zdalnych maszynach lub przesyłać dane z odległych maszyn do swoich.

Rozproszone systemy operacyjne - tym systemie użytkownicy nie muszą być świadomi ilości  maszyn, a dostęp do zasobów zdalnych uzyskują oni tak samo jak do zasobów lokalnych.

Możemy wyróżnić cztery główne powody, które przemawiają za budową systemów rozproszonych. Należą do nich: dzielenie zasobów, przyspieszenie obliczeń, niezawodność i komunikacja.  

ü  dzielenie zasobów – jest to mechanizm pozwalający na wspólne korzystanie z plików na zdalnych stanowiskach, przetwarzanie informacji w rozproszonych bazach danych, drukowanie plików na zdalnych stanowiskach, używanie zdalnych wyspecjalizowanych urządzeń oraz wykonywanie innych operacji (dla przykładu użytkownik stanowiska A może korzystać z drukarki dostępnej tylko na stanowisku B, a w tym samym czasie użytkownik stanowiska B może sięgać po plik rezydujący w A).

ü  przyspieszanie obliczeń – jeśli jakieś konkretne obliczenie można podzielić na pewną liczbę obliczeń cząstkowych, które mogłyby być wykonywane współbieżnie, to system rozproszony może umożliwić rozdzielenie obliczeń między różne stanowiska w celu ich współbieżnego wykonywania. Poza tym jeśli jakieś stanowisko jest w danej chwili obciążone zbyt dużą liczbą zadań, to niektóre z tych zadań mogą zostać przesunięte do mniej obciążonych stanowisk. To przemieszenie zadań nazywamy dzieleniem obciążeń.

ü  niezawodność – jeśli system składa się z pewnej liczby dużych, autonomicznych instalacji, wówczas awaria jednego z nich nie ma wpływu na resztę. Jeśli natomiast system składa się z pewnej liczby małych maszyn, z których każda odpowiada za jakąś ważną funkcje systemu, to pojedyncze uszkodzenie może spowodować zatrzymanie całego systemu. Awaria stanowiska powinna zostać wykryta przez system, przy czym należy liczyć się z podjęciem odpowiednich działań zmierzających do usunięcia jej skutków. System powinien wstrzymać korzystanie z usług uszkodzonego stanowiska, a jeśli istnieje taka możliwość to zadanie uszkodzonego stanowiska powinno zostać przejęte przez inne stanowisko.

ü  komunikacja – w przypadku gdy wiele stanowisk jest połączonych ze sobą za pomocą sieci komunikacyjnej, wtedy użytkownicy rożnych stanowisk mają możliwość wymieniania informacji (na niskim poziomie systemy przekazują między sobą komunikaty). Zaletą systemu rozproszonego jest to, że działania mogą być wykonywane na wielkie odległości, dzięki czemu nad jednym projektem może pracować wiele osób, przesyłając sobie pliki projektu, dane, czy też wymieniając pocztę.

4.2 Pojęcie protokołu sieciowego, model warstwowy protokołu sieciowego.

Protokoły sieciowe.

Zapewniają usługi łączy dla systemów komunikacyjnych, obsługują adresowanie
i informację routingu, weryfikację błędów oraz żądania retransmisji. Obejmują również procedury dostępu do sieci określone przez wykorzystywany rodzaj sieci (IP, IPX);

Protokół jest realizowany przez parę modułów programowych zlokalizowaną w komputerach nadawczych i odbiorczych. Na przykład protokół transportu służy do przesyłania dowolnej długości komunikatów od procesu nadawczego do procesu odbiorczego. Proces chcący wysłać wiadomość do innego procesu wywołuje moduł protokołu transportu, przekazując mu komunikat w określonym formacie. Odtąd obowiązek przesłania komunikatu do celu przejmuje na siebie oprogramowanie transportowe, dzieląc ten komunikat na pakiety ustalonego rozmiaru i formatu. zdalne do przesyłania do celu za pomocą protokołu sieciowego czyli innego protokołu niższego poziomu. Odpowiedni protokół transportu w komputerze odbiorczym przyjmuje pakiety i wykonuje działania odwrotne w celu odtworzenia komunikatu przed przekazaniem go do procesu odbiorczego.

Model warstwowy protokołu sieciowego.

Programowanie sieciowe ma posiać hierarchii warstw. Każda warstwa jest interfejsem dla warstw leżących ponad nią. rozszerzającym i uogólniającym pewne właściwości systemu komunikacyjnego będącego jej podłożem. W każdym komputerze przyłączonym do sieci warstwa jest reprezentowana przez moduł oprogramowania. Tak więc każda warstwa dostarcza usług warstwie leżącej ponad nią i rozszerza usługi przez warstwę leżąca, od niej niżej. Na spodzie znajduje się warstwa fizyczna, stanowią ją środki komunikacyjne (kable miedziane lub światłowodowe, łącza satelitarne lub radiowe) oraz odpowiednie układy w każdym komputerze, transmitujące sygnały przez środki komunikacji. Porcje danych są odbierane w miejscu przeznaczenia i przekazywane w górę hierarchii modułów programowych, ulegając na każdym etapie transformacjom aż przyjmą postać zdatną do przekazania docelowemu procesowi odbiorczemu

4.3 Protokół OSI oraz protokół TCP/IP.

 

Protokół OSI.

Ogólnie przyjętym modelem sieci jest model warstwowy. Wymienione wyżej funkcje dzieli się na rozłączne podzbiory i powierza poszczególnym warstwom. Najwyższa warstwa jest odpowiedzialna za konwersje protokółów użytkownika lub funkcje zarządzania urządzeniami, najniższa warstwa za sterowanie fizycznym medium transmisji danych. W modelu warstwowym pełny zbiór funkcji komunikacyjnych zostaje podzielony na podzbiory w taki sposób, by było możliwe traktowanie każdego podzbioru jako pewnej całości wykonującej autonomiczne zadanie. Wyodrębnione podzbiory funkcji są powiązane ze sobą tak, że tworzą strukturę hierarchiczna w postaci uporządkowanych warstw. Każda warstwa składa się z w obiektach rozproszonych w różnych urządzeniach sieci komputerowej. Podstawowa zasada jest to, ze komunikują się ze sobą tylko równorzędne pary obiektów jednej warstwy korzystając jedynie z usług transmisji danych oferowanych przez warstwy niższe. Każda warstwa modelu jest opisana przez protokół wymiany informacji pomiędzy równorzędnymi obiektami warstwy oraz przez zbiór usług komunikacyjnych pełnionych dla warstwy znajdującej się bezpośrednio nad nią.

Warstwy OSI.

 

Warstwa fizyczna: (physical layer)

Jest odpowiedzialna za transmisję strumienia bitów między węzłami sieci. Definiuje protokoły opisujące interfejsy fizyczne, to jest ich aspekty: mechaniczny, elektryczny, funkcjonalny i proceduralny. Do funkcji tej warstwy należą: sprzęgniecie z medium transmisji danych, dekodowanie sygnałów, określanie zakresu amplitudy prądu lub napięcia i określanie parametrów mechanicznych łączówek (kształtu, wymiarów i liczby styków) oraz inne kwestie związane z transmisją bitów.

Warstwa łącza danych: (data link layer)

Zapewnia niezawodne łącze pomiędzy sąsiednimi węzłami. Nadzoruje przepływ informacji przez łącze i w związku z podatnością warstwy fizycznej na zakłócenia i wynikające stąd błędy oferuje własne mechanizmy kontroli błędów w przesyłanych ramkach lub pakietach (CRC - Cyclic Redundancy Check).

 

 

Warstwa sieciowa: (network layer)

Dostarcza środków do ustanawiania, utrzymania i rozłączania połączeń sieciowych miedzy systemami otwartymi, w których rezydują komunikujące się aplikacje, i odpowiada, za obsługę błędów komunikacji. Ponadto warstwa sieciowa jest odpowiedzialna za funkcje routingu, który wyznacza optymalną pod względem liczby połączeń drogę przesyłania pakietu przez sieć.

Warstwa transportowa: (transport layer)

Zapewnia przezroczysty transfer danych między stacjami sesyjnymi, odciąża je od zajmowania się problemami niezawodnego i efektywnego pod względem kosztów transferu danych. Warstwa ta zapewnia usługi połączeniowe. Wszystkie protokoły w warstwie transportowej są typu “od końca do końca”(end-to-end). Oznacza to, że działają one tylko między końcowymi systemami otwartymi.

Warstwa sesji: (session layer)

Umożliwia aplikacjom organizację dialogu oraz wymianę danych między nimi. Do najważniejszych usług warstwy sesji należą: sterowanie wymianą danych, ustalanie punktów synchronizacji danych (dla celów retransmisji w wypadku przemijających przekłamań na łączach) oraz umożliwienie odzyskania danych (utraconych w wyniku przerwy w łączności) przez ponowne ich przesłanie.

Warstwa prezentacji: (presentation layer)

Zapewnia możliwość reprezentowania informacji, którą się posługują stacje aplikacyjne podczas komunikacji Zapewnia tłumaczenie danych, definiowanie ich formatu oraz odpowiednią składnię.

Warstwa aplikacji: (application layer)

Dostarcza procesom aplikacyjnym metod dostępu do środowiska OSI, pełni rolę okna między współdziałającymi procesami aplikacyjnymi.

 

Protokół TCP/IP.

Architektura protokołów.

Zestaw protokołów został opracowany w celu umożliwienia komunikacji miedzy różnymi typami systemów komputerowych, jak również pomiędzy różnymi sieciami. Agencja DARPA oraz Stanford University rozpoczęły pracę nad protokołem TCP
w 1973 r. Badania prowadzone w ciągu pięciu lat doprowadziły do opracowania dwóch wzajemnie uzupełniających się protokołów. Pierwszy z nich TCP jest protokołem połączeniowym, natomiast drugi protokółem bezpołączeniowy IP (stąd nazwa TCP/IP). Protokoły TCP/IP wykorzystywane są obecnie w systemach UNIX-owych, sieciach lokalnych (LAN) oraz w sieciach rozległych (WAN). Pozwalają również na łączenie oddzielnych sieci fizycznych w jedną logiczną.

Zalety protokołów TCP/IP:

ü  uniwersalność pod względem specyfikacji systemów komputerowych

ü  integracja różnych rodzajów sieci komputerowych

ü  przydzielenie unikatowego adresu każdej maszynie dzięki wspólnemu schematowi adresacji

ü  standardowe protokoły warstw wyższych

Protokół TCP/IP umożliwia realizację wielu usług, oto niektóre z nich:

ü  transfer danych (IP, TCP, UDP)

ü  kontrola poprawności połączeń (ICMP)

ü  zarządzanie siecią (SNMP)

ü  zdalne łączenie (TELNET, SSH)

ü  przesyłanie plików (FTP)

Architektura protokołu TCP/IP składa się z czterech warstw ułożonych hierarchicznie

 

 

Dane generowane przez programy aplikacyjne są przekazywane w dół stosu, jeśli maja być przesyłane w sieć i w górę stosu w przypadku odbioru. Każda warstwa stosu dodaje do danych przekazywanych z warstwy wyższej informacje sterujące w postaci nagłówków (headers). Nagłówek dodany w warstwie wyższej jest traktowany jako dane w warstwie niższej. Warstwy protokołów TCP/IP używają różnych nazw do określenia przekazywanych danych. Aplikacje stosujące w warstwie transportowej protokół TCP nazywają swoje dane strumieniem. Protokół TCP nazywa swoje dane segmentem. Aplikacje wykorzystujące w warstwie transportowej protokół UDP określają swoje dane jako wiadomości, a dane protokołu UDP to pakiety. W warstwie Internet protokół IP traktuje swoje dane jako bloki zwane inaczej datagramami. W najniższej warstwie bloki danych to ramki lub pakiety w zależności od używanego protokołu.

Warstwa dostępu do sieci.

Najniższą warstwą w hierarchii architektury TCP/IP jest warstwa dostępu do sieci. W warstwie tej do datagramów IP dodaje się nagłówki oraz zakończenie i w ten sposób otrzymuje się ramki przesyłane w sieci. Funkcje tej warstwy odpowiadają w przybliżeniu funkcjom trzech najniższych warstw modelu ISO/OSI. Do komunikacji w sieciach rozległych lub przez łącza szeregowe mogą byś stosowane takie protokoły jak X25, PPP lub SLIP. Te dwa ostatnie protokoły zostały opracowane specjalnie do przesyłania datagramów pomiędzy dwoma punktami łączem szeregowym. W sieciach rozległych stosuje się protokołu PPP, natomiast protokół SLIP używa się do prostego połączenia dwóch komputerów łączem szeregowym.

Warstwa Internet.

Zasadniczym protokołem w tej warstwie jest protokół IP. Odpowiedzialny jest on za przesyłanie pakietów zwanych datagramami, pomiędzy użytkownikami sieci. Jest to protokół bezpołączeniowy, co oznacza, że datagramy są przesyłane przez się bez kontroli poprawności i dostarczenia. W tym przypadku może dojść do sytuacji, kiedy
datagram może ulec przekłamaniu lub zostanie zagubiony w sieci. Dlatego protokół IP przeznaczony jest do używania w sieciach bardzo dobrej jakości i niezawodnych łączach transmisyjnych. Drugim protokołem tej warstwy jest ICMP, związany ściśle
z IP. Zadaniem jego jest informowanie o nieprawidłowościach w pracy sieci. Pozwala na przesyłanie komunikatów sterujących między węzłami sieci, które umożliwiają sterowanie przepływem, testowanie urządzeń, wskazywanie alternatywnych połączeń także wykrywanie niedostępnych użytkowników.

 

Warstwa transportowa.

Zapewnia bezpośrednie połączenie między końcowymi użytkownikami (systemami) wymieniającymi informacje. Do najważniejszych protokołów w tej warstwie zalicza się protokół TCP oraz UDP. Protokół TCP jest typu połączeniowego, umożliwia wykrywanie błędów na obu końcach połączenia. Ma on możliwość ustanowienia i utrzymania połączenia wirtualnego między dwoma użytkownikami w celu przesyłania danych, sterowania przepływem, przesyłania potwierdzeń oraz kontroli i korekcji błędów (CRC). Protokół UDP jest protokołem bezpołączeniowym, nie posiada mechanizmów korekcyjnych. Segmenty TCP oraz pakiety UDP w celu dalszego przesłania umieszczane są wewnątrz datagramu IP.

Warstwa aplikacji.

Warstwa ta zawiera procesy wykorzystujące protokoły TCP lub UDP. Protokoły tej warstwy dostarczają użytkownikom różnych usług. Do najbardziej znanych i rozpowszechnionych aplikacji korzystających z TCP należą:

ü  TELNET, SSH – dla usług terminalowych, pozwalają na rozpoczęcie sesji poprzez sieć

ü  TFTP – dla prostych usług transferu plików (uproszczona wersja FTP)

ü  FTP – umożliwia interakcyjne przesyłanie plików

ü  SMTP – poczta elektroniczna, działa na zasadzie „zapamiętaj i prześlij” między systemami poczty korzystającymi z serwerów pocztowych

Do bardziej znanych usług protokołu UDP należą:

ü  DNS – serwery przechowujące dane o domenach i przypadających im adresach sieciowych

ü  RIP – służy do wymiany informacji związanych z aktualizacją reguły doboru tras w węzłach sieci

ü  NFS – umożliwia współdzielenie plików przez wiele komputerów dołączonych do sieci, jest to rozproszony system plików działających według modelu „klient – serwer”

Protokoły TCP/IP wyróżniają dwa typy urządzeń sieciowych: routery (lub gatewaye) oraz hosty (komputery). Routery służą do przesyłania pakietów między sieciami a na hostach instalowane jest oprogramowanie aplikacyjne dla użytkowników

4.4 Komunikacja strumieniowa oraz komunikacja datagramowa – własności.

Możliwe są dwa rodzaje usług transportu danych:

ü  połączeniowe, w których między procesem nadawczym a odbiorczym tworzy się „połączenie wirtualne" i używa się go do przesyłania strumienia (ang. Stream) danych;

ü  bezpołączeniowe w którym do określonych miejsc przeznaczenia przesyła się indywidualne komunikaty- nazywane datagramami (ang. Datagrames)

Komunikacja datagramowa

Datagramy przesyłane za pomocą usług bezpołączeniowych są podobne do pakietów. Są one adresowane do procesów, natomiast pakiety przesyłane przez warstwę sieci są adresowane tylko do komputerów macierzystych. Usługi bezpołączeniowe mogą być zawodne, toteż wykrywanie strat lub złego porządku datagramów oraz podejmowanie działań naprawczych należy do oprogramowania warstwy zastosowań.

Komunikacja strumieniowa

Komunikacja w trybie połączeniowym jest przydatna do wdrażania usług wymagających przesyłania strumieni danych o nieograniczonej wielkości, takich jak zdalne sesje konwersacyjne lub transmisje wielkich plików. Usługi bezpołączeniowe są prostsze i wymagają mniej zachodu. Stosuje się je często do realizacji komunikacji klient-serwer w systemach rozproszonych zbudowanych z sieci lokalnych, ponieważ ustanowienie połączenia jest dość pracochłonne,

u konwersacja między klientem a serwerem może się sprowadzać do wymiany zaledwie pary komunikatów.

 

4.5 Pojęcie portu, pojęcie pary gniazdowej.

 

Każda aplikacja korzystająca z protokołów TCP/IP jest identyfikowana za pomocą numeru portu. Z kolei protokoły transportowe są określone za pomocą numerów protokołów. Pozwala to łączyć dane generowane przez różne aplikacje z kilkoma protokołami transportowymi i z kolei te protokoły z protokołem IP. Takie podejście daje możliwość multipleksacji danych, czyli np. umożliwia równoczesną komunikację wielu aplikacji z TCP. W Internecie niektóre numery portów są zarezerwowane i wstępnie przypisane do tzw. dobrze znanych usług (przyjmują numery 0 – 255). Zaliczyć można do nich takie protokoły sieciowe jak FTP, TELNET, SSH, HTTP, STMP.

Gniazdo to kombinacja adresu IP i numeru portu. W związki z tym gniazdo jednoznacznie określa proces w Internecie. Gniazdo to również zakończenie logicznego łącza komunikacyjnego pomiędzy dwoma aplikacjami. Jeśli aplikacje realizowane są na dwóch komputerach, to para odpowiadających im gniazd definiuje połączenie w protokole połączeniowym TCP.

4.6 Mechanizm ustanowienia połączenia – uzgadnianie trójfazowe.

ü  ustanawianie połączenia TCP przebiega według poniższego scenariusza.

ü  serwer musi być przygotowany na przyjęcie nadchodzącego połączenia. W tym celu zazwyczaj wywołuje funkcje: socket, bind i listen Nazywa się to otwarciem biernym (ang- passive open) połączenia.

ü  klient rozpoczyna otwarcie aktywne (ang. active open) połączenia, wywołując funkcję connect. To powoduje, że oprogramowanie TCP klienta wysyła segment danych SYN (nazwa tego segmentu pochodzi od słowa ang- synchronize), zawierający początkowy numer kolejny danych, które ten klient będzie przesyłać przez to połączenie. Zazwyczaj w tym segmencie SYN nie przesyła się danych; zawiera on tylko nagłówek IP, nagłówek TCP i ewentualne opcje TCP

ü  serwer musi potwierdzić przyjęcie segmentu SYN od klienta i wysłać własny segment SYN, zawierający początkowy numer kolejnych danych, które serwer będzie wysyłać przez to połączenie. Serwer wysyła w jednym segmencie SYN również potwierdzenie ACK (ang. acknowledgrnent).

ü  klient musi potwierdzić przyjęcie segmentu SYN od serwera.

4.7 Mechanizm zakończenia połączenia.

Podczas gdy do ustanowienia połączenia potrzeba trzech segmentów, to czterech segmentów używa się do jego zakończenia.

 

ü  jeden program użytkowy najpierw wywołuje funkcję close; mówimy wówczas, że ten punkt końcowy połączenia wykonuje zamknięcie aktywne (ang. active close).

ü  oprogramowanie TCP po tej stronie połączenia wysyła segment danych FIN (ang. finish), oznaczający zakończenie wysyłania danych.

 

ü  drugi punkt końcowy połączenia, który odbiera segment FIN, wykonuje zamknięcie bierne (ang. passive close). Oprogramowanie TCP potwierdza przyjęcie segmentu FIN. Informacja o otrzymaniu segmentu FIN jest również przesyłana do programu użytkowego jako znacznik końca pliku (po wszystkich danych, które mogą już oczekiwać w kolejce na pobranie przez program użytkowy), ponieważ odebranie segmentu FIN oznacza, że ten program użytkowy już nie otrzyma żadnych dodatkowych danych poprzez to połączenie.

 

ü  po pewnym czasie ten drugi program użytkowy, który odebrał znacznik końca pliku, wywołuje funkcję close, aby zamknąć swoje gniazdo. To powoduje/ że jego warstwa TCP wysyła segment FIN.

 

ü  oprogramowanie TCP w tym systemie, który odebrał ten ostatni segment FIN (w tym punkcie końcowym połączenia, który wykonuje zamknięcie aktywne), potwierdza przyjęcie segmentu FIN.

 

4.8 Architektura programu klienta i serwera funkcjonujących w oparciu o protokół TCP.

 

4.9 Budowa serwera iteracyjnego.

 

4.10 Budowa serwera współbieżnego opartego na:

ü  Procesach

ü  Watkach

 

4.11 Funkcje w języku C: socket, connect, accept, listen, bind, close, read, write.

socket - Funkcja socket tworzy internetowe gniazdo strumieniowe (SOCK_STREAM), czyli gniazdo obsługiwane przez warstwę TCP. Funkcja ta przekazuje małą liczbę całkowita, która służy jako deskryptor identyfikujący to gniazdo we wszystkich następnych wywołaniach funkcji systemowych (np. funkcji connect oraz read).

Connect - Stosując funkcję connect do gniazda TCP, powodujemy ustanowienie połączeniaTCP z serwerem określonym przez gniazdową strukturę adresową, wskazywaną poprzez drugi argument wywołanej funkcji. Musimy również jako trzeci argument tej funkcji określić rozmiar gniazdowej struktury adresowej; pozwalamy zawsze kompilatorowi obliczyć rozmiar struktury dla adresów gniazd internetowych, używając w tym celu operatora sizeof w języku C.

accept - Zazwyczaj funkcja accept powoduje, że proces serwera popada w stan uśpienia

w oczekiwaniu na nadejście i zaakceptowanie połączenia z klientem. W celu ustanowienia połączenia obsługiwanego zgodnie z protokołem TCP stosuje się tzw. uzgodnienie trójfazowe po czym następuje powrót z funkcji accept.

Wartością przekazywaną przez tę funkcję jest nowy deskryptor, cockfd, zwany deskryptorem gniazda połączonego ,który służy do komunikowania się z nowym klientem, Funkcja accept przekazuje nowy deskryptor odpowiadający każdemu klientowi, który łączy się z naszym serwerem.

listen - Wywołując funkcję listen, przekształcamy gniazdo w gniazdo nasłuchujące,

w którym przychodzące od klientów połączenia będą akceptowane przez jądro systemu.

 

bind - funkcja nadaje nazwę gniazdka, gdyż aby inny proces mógł zaadresować gniazdko musi ono mieć nazwę.

write - funkcje do czytania i przesyłania.

close - zakończenie połączenia. Serwer zamyka połączenie z klientem, wywołując funkcję close. Rozpoczyna to zwykłą sekwencję kończąca połączenie zgodnie z protokołem TCP: w każdym kierunku jest wysyłany segment FIN, a przyjęcie każdego segmentu FIN jest potwierdzane na drugim końcu połączenia.

read – funkcja służy do pobierania danych z gniazda TCP. Musimy zawsze wywołanie funkcji read umieścić w pętli., której wykonywanie zakończy się wtedy, kiedy funkcja read przekaże albo 0 (oznaczające zakończenie połączenia), albo liczbę ujemna (wskazującą na wystąpienie błędu).

4.12 Projekt laboratoryjny – Aplikacja klient – serwer w języku C.

 

 

 

 

 

Bibliografia:

 

1. Zbigniew Weiss , Tadeusz Gruźlewski - „Programowanie Współbieżne i Rozproszone” Wydawnictwo Naukowo – Techniczne – 1.1, 1,2, 3

2. http://www.astagor.net/putinf/data/SysOper/ - 1.4, 4

3. http://www.algorytm.cad.pl/Algorithms/51-60/algorithm55.html - 2.4

4. http://www.kik.pcz.czest.pl/so/mainpage/subject20/index20.htm - 1.3, 4.1

5.     www.ia.pw.edu.pl/~tkruk/edu/sop2a/w5.doc – 2.1, 2.2, 2.3

6.     Jędrzej Ulasiewicz - „Programownie aplikacji współbieżnych”

7.     Janina Mincer – „Systemy operacyjne”