Technologie informacyjne. Laboratorium N2. Praca sieciowa z edytorem tekstu Cel ćwiczeń: tworzenie i formatowanie dokumentów z wykorzystaniem edytora tekstów. Program zajęć 1. Przetwarzanie dokumentów z wykorzystaniem edytora tekstów 1.1. Zapis, odczyt, zmiana nazwy dokumentu na dyskach sieciowych. 1.2. Podstawowe operacje edycyjne: wprowadzanie i formatowanie tekstu, stosowanie tabulatorów, listy wypunktowane, numerowane i hierarchiczne, wstawianie i forma- towanie rysunków, obrazów; wstawianie plików, sprawdzanie poprawności ortogra- ficznej, dzielenie wyrazów, użycie pomocy, drukowanie dokumentów. 1.3. Projektowanie tabel i formularzy, spis tabel. 1.4. Formatowanie tekstów naukowo-technicznych, wykorzystanie wzorów i odnośni- ków, spis literatury. 1.5. Obsługa korespondencji seryjnej. 1.6. Praca z dużymi dokumentami tekstowymi: zastosowanie szablonów, tworzenie i modyfikacja stylów, podział dokumentu na sekcje, definiowanie nagłówka i stopki, tworzenie podpisów do rysunków i tabel, wstawianie odsyłaczy i przypisów, two- rzenie spisu treści, spisu rysunków i tabel, spisu indeksów. 2. W ramach ćwiczeń zrealizować zadanie podane na następnej stronie, polegające na sformatowaniu przykładowego (lub własnego) tekstu zgodnie z ustalonymi wymaganiami. 3. W ramach pracy własnej zapoznać się z ćwiczeniami dodatkowymi w postaci: Laboratorium N2.1. Projektowanie tabel i formularzy. Laboratorium N2.2. Projektowanie tekstów naukowo-technicznych. Laboratorium N2.3. Generowanie dokumentów w ramach korespondencji seryjnej. ROZPROSZONE SYSTEMY KOMPUTEROWE I ICH KIERUNKI ROZWOJU Adam Adamski Wojciech Kowalski Streszczenie. Streszczenie tekst. Streszczenie tekst. Streszczenie tekst. Streszczenie tekst. Streszczenie – tekst. Streszczenie – tekst. Streszczenie – tekst. Streszczenie tekst. Streszczenie – tekst. Streszczenie – tekst. Streszczenie – tekst. Streszczenie tekst. Streszczenie – tekst. Streszczenie – tekst. Streszczenie – tekst. Streszczenie tekst. Streszczenie – tekst. Streszczenie – tekst. Streszczenie – tekst. Streszczenie tekst. Streszczenie – tekst. Streszczenie – tekst. Streszczenie – tekst. Streszczenie tekst. Streszczenie – tekst. Streszczenie – tekst. Streszczenie – tekst. Streszczenie tekst. Streszczenie – tekst. Streszczenie – tekst. Streszczenie – tekst. Streszczenie tekst. Streszczenie – tekst. Streszczenie – tekst. Streszczenie – tekst. Streszczenie tekst. Streszczenie – tekst. Streszczenie – tekst. Streszczenie – tekst. Streszczenie tekst. Streszczenie – tekst. Streszczenie – tekst. Streszczenie – tekst. Streszczenie tekst. Streszczenie – tekst. Streszczenie – tekst. SPIS TREŚCI 1. System rozproszony Rozwój sieci komputerowych umożliwił łączenie ze sobą komputerów pracują- cych w rożnych systemach operacyjnych i na rożnych platformach sprzętowych. Stoso- wanie różnorodnych rozwiązań technologicznych doprowadziło do sytuacji, w której niezbędne stało się wprowadzenie standardów sieciowych. Pierwszym standardem, któ- ry uporządkował zasady komunikacji w sieci był opracowany przez ISO (ang. Interna- tional Standarisation Organisation) siedmiowarstwowy model odniesienia. Standard ten opisywał jedynie, jakie zasady muszą być spełnione, aby dwa systemy otwarte mo- gły wymieniać między sobą informacje. Wraz z szybkim rozwojem technologii infor- matycznych (między innymi zwiększeniem szybkości sieci, wzrostem wydajności kom- puterów) pojawiła się potrzeba opracowania nowych rozwiązań umożliwiających prze- twarzanie w środowisku rozproszonym. Zagadnienie przetwarzania w środowisku rozproszonym w porównaniu z przetwa- rzaniem scentralizowanym jest dość złożone. Projektując system rozproszony napotyka się na różne problemy związane między innymi z brakiem wspólnej pamięci, znacznym oddaleniem poszczególnych maszyn, przydziałem zasobów, czy synchronizacją proce- sów. W niniejszej pracy przedstawiono protokoły komunikacji umożliwiające bezkon- fliktowy dostęp do wspólnych zasobów w systemie współbieżnych procesów sekwen- cyjnych z wzajemnym wykluczaniem. Opisano ważniejsze mechanizmy koordynacji procesów stosowane w systemach rozproszonych. Szczególną uwagę zwrócono na za- gadnienie wzajemnego wykluczania procesów oraz eliminacji zagłodzeń. Zaprojekto- wano oryginalny algorytm synchronizacji procesów w środowisku rozproszonym. Przedstawiono implementację obiektową algorytmu dla przykładowego systemu proce- sów rozproszonych. Procedury komunikacji zaprojektowano w języku Java w oparciu o standard CORBA (ang. Common Object Request Broker Architecture) definiujący mo- del obiektowy komunikacji rozproszonej. W niniejszej pracy przedstawiono protokoły komunikacji umożliwiające bezkon- fliktowy dostęp do wspólnych zasobów w systemie współbieżnych procesów sekwen- cyjnych z wzajemnym wykluczaniem. Opisano ważniejsze mechanizmy koordynacji procesów stosowane w systemach rozproszonych. Szczególną uwagę zwrócono na za- gadnienie wzajemnego wykluczania procesów oraz eliminacji zagłodzeń. Zaprojekto- wano oryginalny algorytm synchronizacji procesów w środowisku rozproszonym. Przedstawiono implementację obiektową algorytmu dla przykładowego systemu proce- sów rozproszonych. Procedury komunikacji zaprojektowano w języku Java w oparciu o standard CORBA (ang. Common Object Request Broker Architecture) definiujący mo- del obiektowy komunikacji rozproszonej. 2. Komunikacja w systemach komputerowych Gwałtowny rozwój technologii informatycznych w ostatnich latach spowodował wzrost ilości komputerów oraz spadek ich cen, przez co stały się one bardziej dostępne i praktycznie wszędzie obecne. To z kolei pociągnęło za sobą konieczność łączenia komputerów w pewne struktury. Początkowo były to sieci lokalne LAN (ang. Local Area Network) umożliwiające łączenie komputerów w obrębie bu- dynków i wymianę informacji pomiędzy nimi, a później rozległe sieci komputerowe - WAN (ang. Wide Area Network), które pozwoliły połączyć miliony maszyn na całym świecie. W wyniku połączenia wielu komputerów za pomocą sieci LAN/WAN powstały systemy rozproszone (ang. distributed systems), w których poszczególne procesory nie dzielą pamięci ani zegara a wymiana danych pomiędzy nimi realizowana jest w oparciu o przesyłanie wiadomości za pomocą różnych linii komunikacyjnych. Systemy rozproszone są alternatywą dla systemów scentralizowanych (ang. cen- tralized systems), w których pojedynczy komputer realizuje wszystkie zadania związane z przetwarzaniem informacji [16]. Scentralizowany system komputerowy składa się z jednego procesora centralnego, pamięci, urządzeń zewnętrznych i pewnej liczby terminali. System rozproszony jest układem złożonym z niezależnych komputerów, które udostępniają użytkownikom swoje zasoby (np. dru- karki, dyski, itp.), w sposób sprawiający nanich wrażenie, jakby korzystali z jednego komputera [15]. Z przedstawionej definicji wynika, że procesory w systemie rozproszonym są fizycznie od siebie oddalone i posiadają własną, lokalną pamięć. Ponadto charakteryzuje je zróżni- cowanie pod względem budowy, zastosowania i zaawansowania technologicznego – mogą to być zarówno wielkie systemy komputerowe ogólnego przeznaczenia, jak i małe mikroprocesory, stacje robocze, czy minikomputery. Określa się je wspólnymi nazwami, takimi jak: stanowisko, węzeł, maszyna, komputer. W dalszej części pracy określenia te będą używane zamiennie – w zależności od potrzeb. System rozproszony stanowi zbiór przestrzennie rozproszonych komputerów połączonych siecią komunikacyjną. Układ taki cechuje: ? brak globalnego stanu – stan systemu rozproszonego nie może być dokładnie określony; ? zdalny dostęp – komponenty systemu rozproszonego mogą być rozmieszczone dowolnie w przestrzeni, a współdziałanie pomiędzy nimi może odbywać się zdalnie lub lokalnie; ? niezależność uszkodzeń – komponenty systemu rozproszonego mogą ulegać uszkodzeniom niezależnie do siebie; ? asynchroniczność - komunikacja i przetwarzanie nie są sterowane globalnym zegarem; ? równoczesność – komponenty systemu rozproszonego mogą pracować równolegle; ? heterogeniczność – komponenty systemu rozproszonego (sprzęt, systemy operacyjne, system połączeń, protokoły komunikacyjne, apli- kacje, itp. ) mogą być zbudowane w różnych technologiach; ? autonomiczność – elementy systemu rozproszonego mogą być rozmieszczane w różnych niezależnie zarządzanych miejscach; ? ewolucja – system rozproszony (podczas jego użytkowania) może ulegać wielu przemianom, które mogą być związane z rozwojem nowych technologii lub zmianami zastosowania systemu; ? mobilność – źródła informacji, węzły przetwarzające i użytkownicy mogą być mobilni; oznacza to, że programy i dane mogą być przemieszczane pomiędzy węzłami, np. w celu podniesienia wydajności systemu. Rozproszone systemy komputerowe posiadają wiele zalet. Jedną z nich jest czynnik ekonomiczny - stosowanie architektury rozpro- szonej gwarantuje uzyskanie większej wydajności pracy przy użyciu mniejszych kosztów, niż w pojedynczym systemie scentralizowanym. Wydajność osiągnięta przez odpowiednią liczbę przestrzennie rozproszonych mikroprocesorów jest nieosiągalna przez pojedynczy kompu- ter centralny. Jedną z ważniejszych zalet, która przemawia za budowaniem systemów rozproszonych jest wewnętrzne rozproszenie niektórych za- stosowań. Przykładem może być wspomagana komputerowo praca zespołowa (ang. computer-supported cooperative work). Polega ona na tym, że grupa ludzi fizycznie od siebie oddalonych pracuje razem nad wspólnym projektem. Na podobnej zasadzie działają wspomagane komputerowo gry zespołowe (ang. computer-supported cooperative games) – gracze grają razem w czasie rzeczywistym nie wiedząc, gdzie się nawzajem fizycznie znajdują. Kolejną cechą, która potwierdza wyższość systemów rozproszonych nad scentralizowanymi jest większa niezawodność. Gdy awarii ulegnie jeden komputer system nadal pracuje, gdyż obciążenie rozłożone jest na wiele maszyn. Jest to szczególnie ważne, gdy mamy do czynienia z odpowiedzialnymi zadaniami, takimi jak np. linia produkcyjna. Inne zalety systemów rozproszonych to: ? prosta, tania i teoretycznie nieograniczona skalowalność sys- temu, czyli możliwość jego rozszerzania poprzez dołączanie kolejnych komputerów; ? oszczędność komunikacji – działanie systemu można zopty- malizować pod kątem minimalizacji ruchu sieciowego; gwa- rantuje to systemom informatycznym dużą dostępność, tzn. możliwość poprawnego działania nawet po awarii sieci, np. dzięki wykorzystaniu wolniejszych połączeń zastępczych; ? możliwość udostępniania lokalnych baz danych i urządzeń zewnętrznych (np. kolorowej drukarki laserowej) zdalnym użytkownikom; ? możliwość efektywnego rozdziału zadań (obciążenia) na wszystkie dostępne maszyny; ? ułatwianie komunikacji międzyludzkiej; komunikacja ta może odbywać się na znacznych odległościach dzięki wykorzystaniu np. poczty elektronicznej, usług wymiany plików lub połączeń w czasie rzeczywistym. Obok wielu zalet systemów rozproszonych niektóre ich ce- chy staja się uciążliwe, czy wręcz niepożądane. Rozproszenie sys- temu może powodować konieczność zwiększonej wymiany da- nych oraz zwiększenia pojemności pamięci dyskowych niezbęd- nych do ich przechowywanie (z drugiej strony jednak jest to czyn- nik zmniejszający ryzyko utraty danych w przypadku awarii). Re- alizowanie rozproszonych funkcji systemu wymaga bardziej zło- żonego oprogramowania, a ponadto może prowadzić do powstania wąskiego gardła komunikacyjnego. Łatwy dostęp do wspólnych danych niesie za sobą ryzyko zawładnięcia nimi przez osoby niepowołane. Pojawia się więc problem ochrony danych. W praktyce wprowadzenie systemu za- bezpieczeń może wymagać znacznych nakładów finansowych i nie gwarantuje pełnej ochrony. W przypadku ważnych informacji bezpieczniej jest przechowywać je w odizolowanym komputerze osobistym. Mimo wymienionych wad systemów rozproszonych korzyści osiągane dzięki ich stosowaniu są znacznie większe i to, wraz z rozwojem technologii sieci komputerowych, decyduje o coraz powszechniejszym ich wykorzystywaniu. 2.1. Komunikacja międzyprocesowa Istotnym zagadnieniem w systemach rozproszonych jest komunikacja międzyprocesowa, która stanowi mechanizm umoż- liwiający procesom wzajemne informowanie się i synchronizowa- nie zadań. Od tego, w jaki sposób komunikują się ze sobą procesy zależy działanie całego systemu. Komunikacja w systemach roz- proszonych jest utrudniona, gdyż nie występuje w nich pamięć dzielona. W związku z tym wymiana danych realizowana jest za pomocą przesyłania komunikatów [4]. Komunikacja między procesami w systemach rozproszo- nych najczęściej odbywa się w oparciu o model klient/serwer. Model ten może być zaimplementowany w postaci mechanizmów, takich jak (rys.1): ? gniazdka, ? zdalne wywołanie procedury –RPC (ang. Remote Pro- cedure Call), ? system pośrednictwa usług (ang. middleware). Wymiana komunikatów w modelu klient/serwer jest moż- liwa, gdy pomiędzy procesami utworzy się łącze komunikacyjne oraz istnieje nadawca i odbiorca (klient i serwer) [7]. Model klient/serwer opiera się najczęściej na prostym, bezpołączenio- wym protokole zamówienie / odpowiedź. Klient wysyła zapytanie do serwera i otrzymuje odpowiedź, która jest jednocześnie po- twierdzeniem zamówienia. Gniazdka Podstawowym mechanizmem komunikacji międzyproceso- wej opartej na modelu klient/serwer są gniazdka. Gniazdko jest punktem końcowym łącza komunikacyjnego. Użycie gniazdka wiąże się z jego otwarciem, przeczytaniem i zapisaniem danych oraz zamknięciem połączenia. W mechanizmie tym proces serwe- ra wykonuje usługi dla procesu klienta. Gdy usługę można wyko- nać, wówczas proces serwera prowadzi nasłuch pod ogólnie zna- nym adresem, a proces klienta nawiązuje kontakt z serwerem. W systemie komunikującym się za pomocą gniazdka, klient musi wiedzieć gdzie znajduje się serwer (znać jego adres), numer portu pod którym serwer udostępnia swoje usługi oraz protokół, za po- mocą którego możliwa będzie wymiana komunikatów. Komuni- kacja może się odbywać w jedną lub w dwie strony. Ponadto, mo- że ona być połączeniowa (wymagać zestawienia łącza) lub bezpo- łączeniowa. Zdalne wywołanie procedury Inną szeroko stosowaną techniką jest pozwolenie procesom na wykonywanie procedur znajdujących się na innych maszynach. Proces wywołujący procedurę przekazuje parametry do procesu wywoływanego (znajdującego się na innej maszynie) i wstrzymuje swoje działanie do momentu wykonania procedury i zwrócenia wyników. Dlatego też metoda ta nosi nazwę zdalnego wywołania procedury – RPC (ang. remote procedure call). Mimo, że techni- ka ta jest sporym udogodnieniem w wymianie komunikatów wy- maga rozwiązania pewnych problemów, do których należą m.in.: lokalizacja odpowiedniego serwera, przekazywanie wskaźników oraz złożonych struktur danych, a także obsługa awarii procesu klienta lub procesu serwera. System pośrednictwa usług W systemach rozproszonych procesy mogą być tworzone w oparciu o różne języki programowania, działać na różnych plat- formach sprzętowych, w różnych systemach operacyjnych, komu- nikować się za pomocą różnorodnych protokołów oraz przecho- wywać dane w odmiennych formatach. Aby uprościć współdzia- łanie procesów w systemach rozproszonych opracowano koncep- cję systemu pośrednictwa usług. System ten stanowi oprogramo- wanie działające pomiędzy aplikacjami, systemem operacyjnym i siecią. Pozwala ono na ukrycie przed aplikacją środowiska siecio- wego. Dostarcza mechanizmów pozwalających na współdziałanie pomiędzy procesami na wysokim poziomie. Proces może komuni- kować się z innym procesem w sposób naturalny, tak jakby komu- nikował się z procesem działającym w tym samym komputerze. W przypadku stosowania warstwy pośrednictwa usług nie trzeba wiedzieć gdzie fizycznie znajduje się obiekt, z którego metod chce się korzystać, wystarczy tylko znać jego nazwę. Do najbardziej znanych systemów pośrednictwa usług należą: CORBA (ang. Common Object Request Broker Architecture), DCE (ang. Dis- tributed Computing Environment), DCOM (ang. Distributed Com- ponent Object Model) oraz EJB (ang. Enterprise Java Beans). 2.2. Uporządkowanie zdarzeń Z pojęciem komunikacji ściśle wiąże się zagadnienie współ- pracy i wzajemnej synchronizacji procesów. Synchronizacja pro- cesów w systemach rozproszonych jest bardziej złożona niż w systemach scentralizowanych, gdyż w systemie rozproszonym nie ma wspólnego zegara, ani pamięci dzielonej. Jednak w systemach rozproszonych na ogół nie jest istotne to, aby wszystkie procesy uzgadniały dokładnie wartość czasu, lecz by mogły uzgodnić ko- lejność występowania zdarzeń. Przy takim podejściu nie jest waż- ne, aby zegary wskazywały czas rzeczywisty, lecz istotne jest aby ich wskazania były zgodne ze sobą. W takim przypadku, w od- różnieniu do zegarów fizycznych, mówi się o tzw. zegarach lo- gicznych. W celu zsynchronizowania zegarów logicznych zdefiniowa- no relację uprzedniości zdarzeń (ang. happens-before relation) [3]. Wyrażenie a ? b (a poprzedza b) oznacza, że wszystkie procesy są zgodne co do tego, że najpierw zachodzi zdarzenie a, po czym zachodzi zdarzenie b. Relacja uprzedniości zdarzeń zachodzi bez- pośrednio w dwóch sytuacjach: Jeśli a i b są zdarzeniami w tym samym procesie i a występuje przed b, to relacja a ? b jest praw- dziwa; Jeśli a jest zdarzeniem wysłania komunikatu przez pewien proces i b jest zdarzeniem odebrania tego komunikatu przez inny proces, to relacja a ? b jest również prawdziwa. Zdarzenie ode- brania komunikatu nie może wystąpić przed zdarzeniem wysłania lub w tej samej chwili, co jego zdarzenie jego nadania, gdyż na wędrówkę pakietu z danymi niezbędny jest pewien czas. Uprzedniość zdarzeń jest relacją przechodnią: jeśli a ? b i b ? c, to a ? c. Jeśli dwa zdarzenia x i y występują w różnych pro- cesach, które nie wymieniają między sobą komunikatów (nawet uwzględniając pośredników), to ani relacja x?y, ani y?x nie jest prawdziwa. O takich dwóch zdarzeniach mówi się, że są współ- bieżne, co należy rozumieć jako niemożność ustalenia czasu ich wystąpienia lub ich kolejności. Relację uprzedniości zdarzeń ilustruje poniższy diagram czasoprzestrzenny [15]: Rys. 2.1. Diagram czasoprzestrzenny uprzedniości zdarzeń dla trzech proceso- rów współbieżnych 2.3. Blokady i zagłodzenia Istotnym problemem synchronizacji procesów w systemach rozproszonych są blokady (impasy). Blokada to sytuacja, w której kilka procesów czeka w nieskończoność na zdarzenie, które może powstać tylko wskutek działania jednego z nich. Można wyróżnić blokady komunikacyjne oraz blokady związane z oczekiwaniem na dostęp do zasobów. W dalszej części pracy kanały komunika- cyjne będą traktowane jak zasoby i opisywane za pomocą modeli blokad zasobów [5]. Postępowanie z blokadami w systemach roz- proszonych jest utrudnione, ponieważ wszystkie informacje nie- zbędne do ich rozwiązania są umieszczone w wielu różnych kom- puterach. Aby uniknąć problemów wynikających z rozproszenia, stosuje się różne strategie postępowania z blokadami: ? Algorytm strusia – zignorowanie problemu; ? Wykrywanie blokad – dopuszcza się do ich wystąpienia, a następnie wykrywa i usuwa skutki; ? Zapobieganie – struktura systemu zapewnia, że wystąpie- nie blokady nie jest możliwe; ? Unikanie – przydziały zasobowe realizowane w taki spo- sób, aby nie pojawił się stan blokady. Algorytm strusia z racji swej prostoty stosowany jest zarów- no w systemach rozproszonych jak i scentralizowanych. Wykry- wanie blokad jest jednym z najpopularniejszych algorytmów, gdyż dopuszczenie do wystąpienia blokady i późniejsze usunięcie jej skutków jest dużo prostsze, niż zapobieganie jej powstaniu. Najrzadziej stosowanym podejściem jest unikanie blokad, gdyż wymaga ono bardzo szczegółowych informacji o wielkości przyszłych zapotrzebowań każdego procesu na wszelkie zasoby. W systemie rozproszonym takie informacje są rzadko, lub w ogóle niedostępne. Podsumowując, najczęściej stosowane metody rozwiązywa- nia problemu blokad w rozproszonych systemach komputerowych to wykrywanie i likwidacja blokad oraz zapobieganie blokadom. 2.3.1. Zapobieganie blokadom rozproszonym Zapobieganie występowaniu blokad jest realizowane za po- mocą kilku mechanizmów. Na przykład można wymagać, aby proces zamawiał na początku wszystkie żądane zasoby, zezwalać na przetrzymywanie tylko jednego zasobu przez jeden proces w danym czasie, lub powodować, aby procesy zwracały wszystkie zajmowane zasoby, gdy ubiegają się o nowe [6]. Skuteczniejsze metody korzystają z zasady liniowego uporządkowania zasobów przydzielanych do procesów lub realizowania przydziałów w ko- lejności określonej przez znaczniki czasowe procesów. Mechanizm znaczników czasowych oparty jest na następu- jących regułach: o zegar logiczny procesu Pi jest początkowo ustawiany na wartość hi=0; o każda wiadomość wysyłana przez proces otrzymuje znacznik równy hi=hi+1; o każda wiadomość odebrana, posiadająca znacznik hj, otrzymuje znacznik hi=max(hi, hj)+1. Technika zapobiegania blokadom, oparta na uporządkowa- niu procesów według znaczników czasowych, polega na tym, że każdy proces w systemie, z chwilą utworzenia otrzymuje jedno- znaczny znacznik czasowy. U podstaw algorytmu leży pomysł, aby w sytuacji, gdy jakiś proces zostaje zatrzymany w oczekiwa- niu na zasób używany przez inny proces, sprawdzić, który z nich ma większy znacznik czasu, czyli jest młodszy. Wówczas można wyróżnić dwa wzajemnie uzupełniające się schematy: „czekaj albo giń” oraz „zrań albo czekaj”. W metodzie „czekaj albo giń” (ang. wait-die), jeżeli proces oczekujący na zasób jest starszy (ma mniejszy znacznik czasowy), to czeka na zwolnienie zasobu, natomiast gdy jest młodszy (więk- szy znacznik) wówczas „ginie” – jest usuwany z pamięci. W przy- kładzie przedstawionym na rys.2.3. proces żądający dostępu do zasobu ma znacznik mniejszy (10) od znacznika procesu prze- trzymującego zasób (20). Ponieważ jest procesem starszym prze- chodzi w stan oczekiwania na zasób. W sytuacji pokazanej na rys.2.4. proces zamawiający zasób jest młodszy od procesu, który korzysta z zasobu i dlatego musi zostać usunięty z pamięci. W omawianej metodzie, im proces starszy tym większa je- go tendencja do czekania. Proces młodszy mimo, że jest usuwany z pamięci powraca z tym samym znacznikiem czasowym, dzięki czemu nie występują zagłodzenie, gdyż przy kolejnych zgłosze- niach proces jest coraz starszy. W podejściu tym nie występują wywłaszczenia procesów, gdyż starszy proces musi czekać, aż młodszy zwolni zasób. Inaczej dzieje się w alternatywnej technice zapobiegania blokadom zwanej „zrań albo czekaj”. W algorytmie tym starszy proces (z mniejszym znacznikiem czasowym), jeżeli żąda dostępu do zasobu aktualnie przetrzymywanego przez młodszy proces, to wywłaszcza go. Wywłaszczony proces zostaje zakończony, po czym natychmiast jest ponownie uruchamiany. Sytuację tą przed- stawia rys.2.2. Rys. 2.2. Algorytm zapobiegania blokadzie „zrań albo czekaj” – stary proces wywłaszcza młodszy Podejście „zrań albo czekaj” opiera się na technice wy- właszczeniowej - starszy proces nigdy nie czeka na młodszy pro- ces. W metodzie tej unika się zagłodzeń, gdyż tak jak w poprzed- nim algorytmie przyjmuje się za priorytet znacznik czasowy pro- cesu – im mniejszy znacznik (starszy proces), tym wyższy priory- tet. Główną wadą obu algorytmów jest możliwość niepotrzeb- nego usuwania procesów z pamięci. 2.3.2. Wykrywanie rozproszonych blokad Algorytmy zapobiegania blokadom powodują często niepo- trzebne wywłaszczanie procesów (nawet wówczas, gdy blokada nie występuje) oraz okazują się w praktyce bardzo trudne do za- stosowania. Dlatego częściej stosuje się rozwiązania oparte na wykrywaniu i likwidacji blokad. Polegają one na tym, że dopusz- cza się do wystąpienia blokady i dopiero wtedy usuwa się ją, po- przez wymuszone zakończenie jednego lub więcej procesów. Aby wykryć blokadę konstruuje się graf oczekiwań, opisują- cy stan rozdziału zasobów. Dla każdego stanowiska tworzy się lokalny graf oczekiwań. Węzły grafu odpowiadają wszystkim tym procesom (lokalnym i nielokalnym), które zajmują dowolny zasób lokalny na danym stanowisku, albo go zamawiają. Jak z tego wy- nika ten sam proces może występować w dwóch grafach, jeśli zamówił zasoby na różnych stanowiskach. Jeśli założy się, że wy- stępują tylko pojedyncze reprezentacje poszczególnych typów zasobów, to wówczas pętla w grafie oznacza blokadę. Grafy lokalne łączą się w większe struktury. W zależności od sposobu łączenia grafów lokalnych i ich organizacji wyróżnia się scentralizowane wykrywanie blokad, podejście hierarchiczne oraz w pełni rozproszone [13]. Omawiana metoda nie jest wolna od błędów. W globalnym grafie mogą występować fałszywe cykle co może prowadzić do niepotrzebnego wycofywania procesów (gdy blokada nie wystąpi- ła a proces został zakończony). Ponadto, algorytm zawodzi w przypadku opóźnień w dostarczaniu informacji o strukturze lokal- nych grafów oczekiwań. Można temu zapobiec poprzez wprowa- dzenie jednoznacznych identyfikatorów. Do zamówień pochodzą- cych z różnych stanowisk są dodawane znaczniki czasowe. Wów- czas koordynator jest w stanie odtworzyć faktyczny stan systemu. Metoda ta eliminuje fałszywe blokady, ale wymaga znajomości znaczników czasu i przez to jest kosztowna. W przeciwieństwie do scentralizowanego algorytmu wy- krywania blokad, gdzie wymagane jest przechowywanie wszyst- kich informacji w jednym procesie, w algorytmie hierarchicz- nym występuje rozproszenie informacji między różnymi proce- sami [14]. Tak jak w poprzednim algorytmie każde stanowisko posiada swój własny lokalny graf oczekiwań. Jednak graf globalny jest rozproszony między kilka różnych kontrolerów, które to są zorganizowane w drzewo. Każdy liść drzewa zawiera własny lo- kalny graf oczekiwań pojedynczego stanowiska. Kontrolery nie będące liśćmi utrzymują grafy oczekiwań, które zawierają infor- macje pochodzące z grafów kontrolerów należących do poddrze- wa położonego poniżej. Jeśli w którymś z grafów oczekiwań ist- nieje pętla, to system jest w stanie blokady i trzeba podjąć odpo- wiednie kroki związane z wyjściem z niego. W podejściu w pełni rozproszonym do wykrywania blokad wszystkie kontrolery dzielą po równo odpowiedzialność za wy- krywanie blokad. W algorytmie tym jest wykorzystywany jeden globalny graf, złożony z lokalnych grafów oczekiwań utworzo- nych na poszczególnych stanowiskach. Jeśli pojawi się stan blo- kady, to przynajmniej w jednym z cząstkowych grafów pojawi się pętla. Obecnie istnieje wiele sposobów wykrywania blokad w sys- temach rozproszonych. Jednym z nich jest algorytm Chandy- Misra-Haasa [16], w którym pozwala się procesom na zamawianie kilku zasobów jednocześnie. Procedura wykrywania blokad jest wywoływana, gdy proces przechodzi w stan oczekiwania na za- sób. Oczekujący proces generuje specjalny komunikat próbny (ang. probe message) i przesyła go do procesu przetrzymującego żądany zasób. Komunikat składa się z trzech liczb: numeru proce- su rozpoczynającego czekanie, numeru procesu wysyłającego ko- munikat oraz numeru procesu, do którego komunikat jest kiero- wany. Po nadejściu komunikatu odbiorca sprawdza, czy sam nie czeka na jakieś procesy. Jeśli tak, to komunikat jest aktualizowany z zachowaniem pierwszego pola, lecz z zastąpieniem drugiego własnym numerem procesu i trzeciego numerem tego procesu, na który dany proces czeka. Komunikat jest następnie przesyłany do procesu będącego przyczyną blokowania się danego procesu. Jeśli proces jest zablokowany z powodu kilku procesów, to komunikat zostaje wysłany do każdego z nich (za każdym razem zmieniany). Algorytm jest kontynuowany niezależnie od tego, czy zasób jest lokalny, czy zdalny. Jeżeli komunikat przejdzie całą drogę naoko- ło i wróci do pierwotnego nadawcy (do procesu oznaczonego w pierwszym polu komunikatu), to w systemie istnieje pętla, co jest równoznaczne z blokadą. Blokadę można wówczas usunąć także na kilka sposobów. Jednym z nich jest „popełnienie samobójstwa” przez proces, który zapoczątkował próbę. Rozwiązanie takie nie sprawdza się jednak w przypadku, gdy kilka procesów wywołało algorytm równocześnie. Innym sposobem jest dodawanie do ko- munikatu próbnego przez każdy proces swojego znacznika. Wów- czas nadawca może sam zadecydować, po przejściu całego cyklu, który proces należy usunąć. Istnieje wiele algorytmów wykrywania rozproszonych blo- kad, jednak stale są one udoskonalane, a także opracowywane są nowe rozwiązania. 3. Podsumowanie Tekst podsumowania. Konstrukcja ciała polega na utworzeniu zbioru elementów ciała i wyznaczeniu tabliczek dodawania i mnożenia. W praktyce najczęściej nie korzy- stamy z tabliczek działań, lecz na bieżąco obliczamy sumy i iloczyny elementów ciała prostego. Ciała proste nie są stosowane bezpośrednio do konstrukcji kodów, ale służą do konstrukcji ciał rozszerzonych. Przykłady ciał prostych podano w następnym punk- cie. Tabliczka dodawania ciała skończonego jest kwadratem łacińskim. W kwadracie łacińskim we wszystkich ko-lumnach i wierszach każdy element ciała pojawiaja się tylko raz. Ta właściwość ta-bliczki dodawania wynika z aksjomatu zamkniętości doda- wania A1, p. 1.1.1. Podobną właściwość ma tabliczka mnożenia w części zawierającej elementy grupy multyplika-tywnej. Każdy element niezerowy ciała generuje grupę cy- kliczną. Element pierwotny ciała generuje grupę multyplikatywną ciała. W tak utwo- rzonej grupie będą wszystkie nieze-rowe elementy ciała. Elementy grupy multyplika- tywnej o rzędzie multyplikatywnym większym od 1 i mniejszym od generują podgru- py multyplikatywne. Taka pod-grupa zachowuje działania grupy. Grupę cykliczną generowaną przez dowolny element ciała skończonego otrzyma- my, biorąc kolejne potęgi tego elementu. Na przykkład element 5 ciała GF(7) generuje grupę multyplikatywną: 5, 4, 6, 2, 3, 1, gdyż kolejne potęgi elementu 5 wynoszą: 5, 5?5=4, 4?5=6, 6?5=2, 2?5=3, 3?5=1. Podobnie element 2 generuje podgrupę trzy- elementową: 2, 4, 1. Ciało GF(2) ma charakterystykę 2, ponieważ 1+1 = 0. Ciało GF(7) ma charakterystykę 7, ponieważ np. 3+3+3+3+3+3+3=0. Jeśli liczba n nie istnieje, to charakterystyka ciała jest z definicji równa zero, np. ciała liczb wymiernych, rzeczywistych i zespolonych mają charakterystykę zero. W przypadku ciał skończonych charakterystyka ciała jest liczbą pierwszą, a ciało rozszerzone zachowują charakterystykę ciała prostego, nad którym zostało skonstru- owane rozszerzenie. Każdy element niezerowy ciała generuje grupę cykliczną. Element pierwotny ciała generuje grupę multyplikatywną ciała. W tak utworzonej grupie będą wszystkie nieze-rowe elementy ciała. Elementy grupy multyplikatywnej o rzędzie mul- typlikatywnym większym od 1 i mniejszym od generują podgrupy multyplikatywne. Taka podgrupa zachowuje działania grupy. Jeśli liczba n nie istnieje, to charakterystyka ciała jest z definicji równa zero, np. ciała liczb wymiernych, rzeczywistych i zespolo- nych mają charakterystykę zero. W przypadku ciał skończonych charakterystyka ciała jest liczbą pierwszą, a ciało rozszerzone zachowują charakterystykę ciała prostego, nad którym zostało skonstruowane rozszerzenie. Każdy element niezerowy ciała generuje grupę cykliczną. Element pierwotny cia- ła generuje grupę multyplikatywną ciała. W tak utworzonej grupie będą wszystkie nie- zerowe elementy ciała. Elementy grupy multyplikatywnej o rzędzie multyplikatywnym większym od 1 i mniejszym od generują podgrupy multyplikatywne. Taka podgrupa zachowuje działania grupy. Jeśli liczba n nie istnieje, to charakterystyka ciała jest z definicji równa zero, np. ciała liczb wymiernych, rzeczywistych i zespolonych mają charakterystykę zero. W przypadku ciał skończonych charakterystyka ciała jest liczbą pierwszą, a ciało rozsze- rzone zachowują charakterystykę ciała prostego, nad którym zostało skonstruowane rozszerzenie.