EGZAMIN SYSTEMY ROZPROSZONE - opracowanie zagadnień

1. Co to jest system rozproszony?

System rozproszony jest zbiorem samodzielnych komputerów, połączonych za pomocą sieci i wyposażonych w rozproszone oprogramowanie systemowe. Użytkownicy powinni go odbierać jako jedno zintegrowane środowisko obliczeniowe.

2. Jakie podstawowe cele realizuje system rozproszony?

Łączenie użytkowników i zasobów, otwartość, skalowalność, współbieżność, tolerowanie uszkodzeń, heterogeniczność, przezroczystość - Przemieszczanie danych, obliczeń i procesów

3. Co oznacza termin „otwartość” systemu rozproszonego?

Oferowanie usług zgodnie ze standardowymi regułami opisującymi ich składnię i semantykę

4. Co oznacza „przenośność” systemu rozproszonego?

Możliwość wykorzystywania w jednym systemie, aplikacji opracowanej dla innego systemu realizującego te same interfejsy

5. Co oznacza „elastyczność” systemu rozproszonego?

Łatwość konfigurowania systemu z różnych składowych pochodzących od różnych producentów, oddzielenie polityki od mechanizmu.

6. Co oznacza termin „heterogeniczność” systemu rozproszonego?

Heterogeniczność - użycie różnych technologii przy realizacji
usług, kontroli danych i platform sprzętowych. Przyczynami
heterogeniczności są również projektowa niezależność komponentów
(różne czasy konstrukcji komponentów) lub kombinacje technologii
zastosowane do danego komponentu.

7. Do czego służą i jakie są ogólne właściwości języków definiowania interfejsów (IDL)?

Są to języki do opisu programowych komponentów interfejsów (opis jest neutralny językowo - umożliwia realizację „przenośności” np. komunikację komponentów napisanych w C++ z Javą). Występuje formalna definicja składni i nieformalna definicja semantyki.

8. Co oznacza termin „skalowalność” systemu rozproszonego? DKO

Cecha systemu umożliwiająca zachowanie podobnej wydajności systemu przy zwiększaniu skali systemu (np. liczby procesów, komputerów, itp.).

9. W czym wyraża się brak skalowalności systemu rozproszonego?

W centralizacji usług, danych, algorytmów. Znaczny wzrost trudności zarządzania przy wzroście ilości i/lub rozmiaru jednostek administrowanych.

10. Scharakteryzować podstawowe metody zapewniania skalowalności systemu rozproszonego. DKO

− ukrywanie opóżnień komunikacji (stosowanie komunikatów asynchronicznych oraz

przeniesienie części obliczeń na stronę klienta);

− zwielokrotnienie (zwiększenie dostępności, równoważenie obciążenia, zwiększenie

niezawodności, przechowywanie podręczne);

11. Co oznacza termin „przezroczystość” systemu rozproszonego? DKO

System przezroczysty to taki, który sprawia wrażenie systemu scentralizowanego (dla

użytkowników i aplikacji).

12. Jakie rodzaje „przezroczystości” w systemie rozproszonym określają modele wzorcowe ANSA i ISO?

Przezroczystość dostępu, położenia, wędrówki, przemieszczenia, zwielokrotnienia, współbieżności, awarii, wydajności i skalowalności.

13. Czym charakteryzują się poszczególne rodzaje „przezroczystości” w systemie rozproszonym określane przez modele wzorcowe ANSA i ISO?

Przezroczystość dostępu - ukrywanie różnic w reprezentacji danych i metodach udostępniania zasobów, położenia - uniemożliwienie użytkownikom określenia fizycznej lokalizacji zasobów, wędrówki - możliwość przemieszczania zasobów bez wpływania na sposób kontaktowania się z nimi, przemieszczania - możliwość przemieszczania zasobów podczas ich używania, zwielokrotnienia - ukrywanie faktu istnienia wielu kopii zasobów, współbieżności - współbieżność dostępu powinna skutkować pozostawieniem zasobów w stanie spójności, awarii - zapewnienie, że użytkownik nie zauważy awarii ani skutków jej usuwania, rekonstrukcji, wydajności - umożliwienie rekonfigurowania systemu w celu poprawy jego wydajności przy zmianie obciążenia, skalowalności - umożliwienie zmiany skali systemu bez zmiany struktury lub algorytmów użytkowych

14. Co oznacza termin „przemieszczanie danych” w systemie rozproszonym? DKO

Przemieszczanie danych w systemie rozproszonym oznacza ulokowanie całych plików lub ich fragmentów na różnych częściach systemu rozproszonego.

15. Co oznacza termin „przemieszczanie obliczeń” w systemie rozproszonym? DKO

Przemieszczanie obliczeń w systemie rozproszonym oznacza wykonywanie obliczeń na więcej niż jednym węźle systemu rozproszonego.

16. Co oznacza termin „przemieszczanie procesów” w systemie rozproszonym?

Model klient-serwer, klient zleca wykonanie pewnych operacji serwerowi (uruchamia procesy serwera dla swoich potrzeb i oczekuje na ich wynik).

17. Jakie są przesłanki „przemieszczania procesów” w systemie rozproszonym?

Równoważenie załadowania, przyspieszenie obliczeń, preferencje sprzętowe, preferencje oprogramowania.

18. Jakie podstawowe komponenty wyróżnia się w modelu klient-serwer?

Usługa- abstrakcyjne dobro, które może być dostarczane potrzebującym usługobiorcom, Serwer (usługodawca) - proces, który realizuje pewną usługę, Klient (usługobiorca) - proces, który zamawia pewną usługę u serwera, wysyła zamówienie i oczekuje na odpowiedź.

19. Jakie są główne właściwości podstawowych komponentów w modelu klient-serwer?

Serwer może jednocześnie działać jako klient, kierując dalej zamówienia do innych serwerów, Serwer może działać iteracyjne lub współbieżnie, mogą być wykorzystywane protokoły bezpołączeniowe (wydajność) lub połączeniowe (niezawodność).

20. Jakie są podstawowe cechy serwera iteracyjnego?

Serwer iteracyjny samodzielnie obsługuje zlecenia klientów zwracając im ewentualnie wyniki. Innymi słowy serwer zmuszony jest do obsługi zleceń jedno po drugim, przy czym zanim rozpocznie kolejne zadanie musi zakończyć wykonywanie poprzedniego.

21. Jakie są podstawowe cechy serwera współbieżnego?

Serwer współbieżny pozbawiony jest niedogodności powodującej, że każde kolejne żądanie musi oczekiwać w kolejce do momentu gdy zostaną obsłużone poprzednie. W tym przypadku serwer po odebraniu zlecenia od klienta przekazuje wykonanie zlecenia innemu wątkowi lub procesowi. Po tym jak przekaże zlecenie może natychmiast przystąpić do obsługi innych zleceń.

22. Jakie elementy wyróżnia się w wielopoziomowym modelu klient-serwer i jakie są ich właściwości?

Poziom interfejsu - wszystko co jest niezbędne do bezpośredniego kontaktu z użytkownikiem, interfejsy tekstowe, graficzne. Poziom przetwarzania - aplikacje, a zwłaszcza jej zasadnicze funkcje, często implementowanie wyrafinowanych algorytmów. Poziom danych - programy utrzymujące dane, na których działają aplikacje. Pożądane zapewnienie trwałości danych nawet, kiedy aplikacja nie działa.

23. Co oznacza termin „rozproszenie pionowe” w systemie rozproszonym?

Rozmieszczenie logicznie odmiennych składowych na różnych komputerach.

24. Co oznacza termin „rozproszenie poziome” w systemie rozproszonym?

Klient lub serwer może być fizycznie podzielony na logicznie równoważne części. Każda część przetwarza własną porcję całego zbioru danych, równoważąc w ten sposób obciążenie. (Różne fragmenty danych przetwarzane są przez te same funkcjonalne jednostki).

25. Co oznacza termin „rozproszenie partnerskie” w systemie rozproszonym?

Wzajemna współpraca komponentów - serwer może nie występować (peer-to-peer).

26. Co oznacza termin „paradygmat producent-konsument”?

Paradygmat dla współdziałania procesów, producent produkuje informacje, które są konsumowane przez klienta. (Producent/Konsument (ang. producer/consumer), gdzie producent generuje strumień danych, które są wykorzystywane (konsumowane) przez konsumenta. Strumień ten stanowi wspólny zasób, wątki muszą być zatem synchronizowane.)

27. Co to jest sekcja krytyczna?

W programowaniu współbieżnym fragment kodu programu, który w danej chwili powinien być wykonywany przez nie więcej niż jeden wątek. Brak wzajemnego wykluczania się wykonywania sekcji krytycznych może spowodować błędy wykonania, np. dwukrotne zapisanie danej albo niepoprawna modyfikacja.

28. Jakie są warunki rozwiązanie problemu sekcji krytyczne?

Wzajemne wykluczanie. W danej chwili tylko jeden proces może być w sekcji

krytycznej.

Postęp Proces który nie wykonuje sekcji krytycznej nie może blokować procesów chcących wejść do sekcji.

Ograniczone czekanie Proces nie może czekać na wejście do sekcji krytycznej w nieskończoność.

Niezależność Zachowanie sie procesów poza sekcja krytyczna nie powinno być w żaden sposób ograniczane.

29. Na czym polega wzajemne wyłączanie (wykluczanie) procesów?

Wzajemne wykluczenie zapewnia procesom ochronę przy dostępie do zasobów, daje im np. gwarancję, że jako jedyne będą mogły z niego korzystać.

30. Jakie usługi synchronizacji czasu można spotkać w systemach operacyjnych?

Windows -Czas Systemu Windows - usługa NTP (Network Time Protocol)

Linux - usługa NTP (Network Time Protocol) i SNTP (Simple Network Time Protocol)

31. Co oznacza termin “międzynarodowy czas atomowy”?

W zegarze atomowym - pojęcie sekundy jako liczba przejść w atomie cezu 133. Przy użyciu takich zegarów liczony jest międzynarodowy czas atomowy (ang. International Atomic Time -TAI), który ustanawiany jest poprzez uśrednienie pomiarów z różnych laboratoriów.

32. Co oznacza termin „uniwersalny czas skoordynowany (UTC)”?

Ponieważ średni dzień słoneczny trwa coraz dłużej pojawia się rozbieżność z międzynarodowym czasem atomowym. W celu rozwiązania tego problemu wprowadzono sekundy przestępne. System pomiaru czasu, który uwzględnia to ulepszenie nazywamy uniwersalnym czasem koordynowanym (ang. Universal Coordinated Time - UTC). UTC jest podstawą dzisiejszego pomiaru czasu wśród cywilnych zastosowań. Wskazania UTC udostępniono również osobom, które chcą znać dokładny czas. W tym celu Narodowy Instytut Czasu Standardowego (ang. National Institute of Standard Time -NIST) posiada nadajnik radiowy o literach wywoławczych WWV, który co sekundę wysyła impuls.

33. Co oznacza termin sieciowe źródła czasu?

Zewnętrzne źródło czasu zapewniające dostępność dokładnego czasu wszystkim urządzeniom w sieci. Źródło może znajdować się w sieci wewnętrznej lub w Internecie, ale musi korzystać z protokołu Network Time Protocol (NTP).

34. Na czym polega synchronizacja zegara opóźnionego?

Przy wykorzystaniu protokołu NTP - na przyśpieszeniu zegara aż do osiągnięcia oczekiwanego czasu (wydłużyć jednostkę czasu).

35. Na czym polega synchronizacja zegara przyśpieszonego?

Przy wykorzystaniu protokołu NTP - na zwolnieniu zegara aż do osiągnięcia oczekiwanego czasu (skrócić jednostkę czasu)

36. Na czym polega synchronizacja czasu wykorzystująca algorytm Cristiana?

Algorytm przeznaczony głównie dla systemów, w których jedna maszyna jest serwerem czasu, a reszta maszyn powinna być z nim zsynchronizowana. Okresowo każda maszyna wysyła komunikat do serwera czasu, pytając o bieżący czas. Serwer odsyła, jak szybko może wiadomość ze swoim aktualnym czasem Gdy nadawca otrzyma odpowiedź od serwera może: ustawić swój zegar na czas serwera, powiększyć czas z wiadomości o czas propagacji wiadomości, zastosować dodatkowo czas przetwarzania.

37. Na czym polega synchronizacja czasu wykorzystująca algorytm z Berkley?

Serwer czasu jest aktywny. Serwer czasu okresowo wypytuje każdą maszynę, aby poznać jej czas. Na podstawie odpowiedzi serwer wylicza średni czas i wysyła komunikaty do innych maszyn, aby odpowiednio zmieniły swój czas lub zwolniły zegar do momentu, aż zostanie osiągnięta właściwa jego wartość.

38. Jakie tryby pracy dostępne są w protokole NTP i w jakich warunkach powinno się je stosować? MMO

Tryby pracy protokołu NTP:

• Tryb rozsyłania (multicast mode)

• Tryb wywoływania procedur (procedure-call mode)

• Tryb symetryczny

Pojęcia związane z NTP

NTP (ang. Network Time Protocol) - protokół synchronizacji czasu umożliwiający

precyzyjną synchronizację czasu pomiędzy komputerami. Wzorcowy czas

UTC może pochodzić bezpośrednio z zegarów atomowych lub pośrednio ze

specjalizowanych serwerów czasu (ang. Time Server NTP). Protokół NTP jest coraz

powszechniej uznawany za światowy standard synchronizacji czasu w urządzeniach

teleinformatycznych i telekomunikacyjnych. Ma swoją implementację dla większości

współczesnych systemów operacyjnych, z Microsoft Windows NT/2K/XP/2003/

VISTA/7 włącznie.

Stratum - poziom w hierarchii podsieci synchronizacji wyznaczony przez odległość

węzła od źródła czasu

Struktura warstw STRATUM, Zasada przekazywania informacji o czasie

• Wszystkie komputery uczestniczące w procesie synchronizacji NTP można

uporządkować w strukturze gałęziowej STRATUM.

• Zasada przekazywania informacji o czasie jest następująca:

o komputery warstwy STRATUM N mogą być serwerami czasu dla warstwy

STRATUM N+1, ale nie na odwrót.

o Komputery STRATUM N mogą być jednocześnie klientami komputerów warstwy

STRATUM N-1 itd.

o Wielowarstwowa struktura STRATUM ma na celu uporządkowanie i

wprowadzenie pewnej hierarchii ważności komputerów, zgodnie z ich

rzeczywistym przeznaczeniem i funkcją.

o Aby ograniczyć dodatkowe opóźnienia w propagacji czasu, wynikające z

rozgałęzionej struktury NTP, wprowadzono ograniczenie łącznej liczby warstw do

16 (STRATUM 0-15).

• Niektórym warstwom przypisano specjalne znaczenie.

o Warstwa STRATUM 0 jest zarezerwowana wyłącznie dla pierwotnych wzorców

czasu, którymi są bezpośrednio zegary czasu UTC.

o Warstwy STRATUM 1 i STRATUM 2 stanowią wierzchołek drzewa NTP i

powinny być zarezerwowane dla dużych serwerów korporacyjnych, wysokiej

jakości serwerów, superkomputerów lub dedykowanych sprzętowych serwerów

czasu.

o Warstwy STRATUM 3 i kolejne są przeznaczone dla lokalnych serwerów i

komputerów komunikujących się z nimi.

• Numer STRATUM informuje nas o tym, jak bardzo odległy jest synchronizowany

komputer od zegara wzorcowego w strukturze synchronizacji NTP. W sieci o bardzo

dużej liczbie komputerów poziom STRATUM nie ma znaczącego wpływu na jakość

synchronizacji i precyzję uzyskiwanego czasu.

39. Jakie są właściwości relacji uprzedniości zdarzeń Lamporta?

W podejściu Lamporta wykorzystano bezpośrednio koncepcję relacji uprzedniości zdarzeń. Każdy wysłany komunikat zawiera czas swojego nadania. Odbiorca, który odbierze wiadomość porównuje czas jej nadania z własnym czasem. Jeśli zegar odbiorcy wskazuje czas mniejszy od czasu nadania komunikatu, przesuwa swój zegar w przód do wartości równej czasowi nadania powiększonej o pewną wartość d. Dodanie d wymusza postęp czasu pomiędzy każdą parą zdarzeń.

40. Co to są zegary logiczne Lamporta i jakie są zasady ich funkcjonowania?

Znaczniki czasu Lamporta zostały opracowane jako sposób pomiaru czasu logicznego. Każdemu zdarzeniu a przypisana jest pewna wartość czasu C(a). Jeżeli weźmiemy dwa zdarzenia a i b, przy czym a poprzedza zdarzenie b, to powinna zachodzić nierówność C(a)<C(b). Zegar Lamporta spełnia kilka ważnych warunków. Jeżeli a poprzedza b, to C(a)<C(b). Należy pamiętać, że implikacja taka nie zachodzi w odwrotną stronę. Algorytm Lamporta całkowicie porządkuje wszystkie zdarzenia w systemie.

41. Scharakteryzować algorytm wzajemnego wyłączania procesów w systemie rozproszonym (podejście scentralizowane).

Spośród dostępnych procesów jeden wybierany jest jako koordynator. Kiedykolwiek proces chce wejść do sekcji krytycznej wysyła informację z żądaniem do koordynatora, określając do której sekcji krytycznej chce wejść i pytając zarazem o pozwolenie. Jeżeli w danej chwili żaden z procesów nie jest w tej sekcji krytycznej, koordynator odsyła odpowiedź udzielającą pozwolenia. Kiedy odpowiedź dotrze, proces, który ubiegał się o wejście do sekcji krytycznej, uruchamia ją. Natomiast gdy inny proces zapyta o pozwolenie na wejście do tej samej sekcji krytycznej, koordynator po prostu wstrzymuje się z odpowiedzią, blokując w ten sposób proces, który czeka na odpowiedź. Ewentualnie może np. odesłać odpowiedź z odmową wejścia do sekcji krytycznej.

42. Scharakteryzować algorytm wzajemnego wyłączania procesów w systemie rozproszonym (podejście rozproszone).

Brak koordynatora - rozwiązanie np. algorytm Lamporta: Wykorzystuje mechanizm synchronizacji zegarów Lamporta. Zbiór żądań - zbiór procesów, od których wymagane są pozwolenia na wejście do sekcji krytycznej. Zbiór żądań w algorytmie Lamporta jest zbiorem wszystkich procesów. Każdy proces przechowuje kolejkę żądań sekcji krytycznej uszeregowanych według znaczników czasowych. Gdy proces Pi zamierza wejść do sekcji krytycznej, wysyła wiadomość z żądaniem do wszystkich procesów, które znajdują się wewnątrz jego zbioru żądań Ri. Następnie umieszcza żądanie w swojej kolejce żądań (ts(i) jest znacznikiem czasowym żądania procesu Pi). Gdy proces Pj otrzyma żądanie od procesu Pi, odsyła ODPOWIEDŹ oznaczoną znacznikiem czasowym do procesu Pi i umieszcza żądanie procesu Pi w swojej kolejce żądań. Proces Pi rozpoczyna wykonywanie sekcji krytycznej, gdy spełnione są dwa następujące warunki: 1) proces Pi otrzymał wiadomość ze znacznikiem czasowym większym niż (ts(i), i) od wszystkich innych procesów oraz 2) żądanie procesu Pi jest na początku jego własnej kolejki żądań.

Inne algorytmy: Algorytm Ricarta i Agrawali (podobny do Lamporta) , Algorytm Maekawy (zbiór żądań nie jest zbiorem wszystkich procesów), Algorytm Suzuki-Kasami (żeton), algorytm Raymonda (drzewo).

43. Scharakteryzować algorytm wzajemnego wyłączania procesów w systemie rozproszonym (podejście pierścieniowe).

BRAK

44. Na czym polega zakleszczanie procesów?

Zakleszczenia pojawiają się, gdy proces chce mieć na wyłączność dostęp do pewnego zasobu, ale nie może go otrzymać i w wyniku tego zostaje zablokowany.

45. Scharakteryzować graf oczekiwań do wykrywania zakleszczeń procesów.

Do ilustracji i analizy zakleszczeń można posłużyć się tzw. grafami przydziału zasobów (ang. system resorce-allocation graph). Zbiór wierzchołków takiego grafu podzielony jest na dw zbiory: zbiór procesów oraz zbiór zasobów. Łuk, który biegnie od procesu Pi do zasobu Z oznacza że proces chce użyć tego zasobu i czeka na niego. Jeżeli natomiast łuk biegnie od zasobu Zj do procesu Pi, oznacza to, że zasób został przydzielony procesowi. Stąd też krawędzie tego typu zwaną są odpowiednio: krawędzią zamówienia (ang. request edge) oraz krawędzią przydziału (ang. assignment edge). Na podstawie grafu przydziału zasobó można wykazać, że jeżeli w grafie nie występują cykle, to w systemie reprezentowanym przez ten graf nie ma zakleszczeń. W przeciwnym wypadku może pojawić się zakleszczenie.

46. Scharakteryzować algorytm wykrywania zakleszczeń w systemie rozproszonym (podejście scentralizowane). MDO

- Kontrolę nad systemem sprawuje koordynator wykrywania zakleszczeń

- Zadaniem koordynatora jest konstruowanie globalnego grafu oczekiwania na podstawie

informacji o lokalnych grafach oczekiwania i wykrywanie zakleszczeń

- Sposoby konstruowania globalnego grafu oczekiwani

- przy każdej zmianie grafów lokalnych

- po uzbieraniu odpowiedniej liczby zmian w grafach lokalnych

- przy uruchamianiu algorytmu wykrywania zakleszczeń

- Problem fałszywych cykli i niepotrzebnych wycofań

47. Na czym polega zjawisko fałszywych cykli podczas wykrywania zakleszczeń w systemach rozproszonych? MDO

Fałszywe cykle pojawiają się na skutek niedoinformowania koordynatora o aktualnie

zwolnionych i przydzielonych zasobach. W ten sposób w grafie oczekiwania istnieje

czasami łuk, którego nie ma w rzeczywistym grafie oczekiwania, a który to powoduje

wykrycie nieistniejącego zakleszczenia. Niepotrzebne wycofania mogą się również pojawić,

gdy procesy, które wcześniej powodowały zakleszczenie, są nagle usuwane bez wiedzy

koordynatora.

48. Scharakteryzować algorytm wykrywania zakleszczeń w systemie rozproszonym (podejście hierarchiczne). MDO

- Węzły tworzą hierarchię

- Każdy węzeł może wykryć zakleszczenie

-węzeł Deadlock Detector

- każdy węzeł niżej w hierarchii wysyła WFG do węzła nadrzędnego

- cechy:

- większa niezawodność

- trudniejsza implementacja

49. Scharakteryzować algorytm wykrywania zakleszczeń w systemie rozproszonym (podejście rozproszone). MDO

- Do wykrywania zakleszczeń używa się grafu oczekiwania (WFG), który reprezentuje stan

przydziału zasobów

- Jeżeli stan przedstawiany przez graf dotyczy całego systemu rozproszonego mówimy o

globalnym grafie oczekiwania

- Jeżeli stan, który reprezentuje graf dotyczy tylko danego stanowiska, stanowiska to jest to

lokalny graf oczekiwania

50. Scharakteryzować algorytm tyrana stosowany podczas elekcji. MDO

- Proces Pi wykrył awarię koordynatora i próbuje siebie obrać nowym koordynatorem

- Proces Pi wysyła komunikat o elekcji do wszystkich procesów z wyższymi priorytetami.

Czeka określony czas na nadejście przynajmniej jednej odpowiedzi

- Jeżeli brak jest odpowiedzi to proces siebie wybiera na koordynatora

- Wznawia kopię koordynatora

- Wysyła komunikat informujący o swoim wyborze do wszystkich procesów z mniejszymi od niego priorytetami

- Koniec

- Jeżeli odpowiedz nadejdzie, to proces Pi rozpoczyna czekanie przez określony czas na

komunikat o wyborze koordynatora

- Jeżeli komunikat o wyborze nie nadejdzie to powinien wznowić algorytm

- Jeżeli komunikat o wyborze nadejdzie, to powinien odnotować tą informację

- Koniec

- Jeżeli jakikolwiek proces Pi otrzyma od procesu Pj (j<i) komunikat o rozpoczęciu elekcji, to

wysyła odpowiedz do Pi i zaczyna wykonywać swój algorytm elekcji

- Każdy proces, który wrócił do działania po awarii również rozpoczyna procedurę elekcji

- Jeżeli odpowiedź nadejdzie, to proces Pi rozpoczyna czekanie przez określony czas na

komunikat o wyborze nowego koordynatora

- Jeżeli komunikat o wyborze nie nadejdzie, to powinien wznowić algorytm

- Jeżeli komunikat o wyborze nadejdzie, to powinien odnotować tę informację i KONIEC

- Jeżeli jakikolwiek proces Pi otrzyma od procesu Pj (j<i) komunikat o rozpoczęciu elekcji, to

wysyła odpowiedz do Pi i zaczyna wykonywać swój algorytm elekcji

- Każdy proces, który wrócił do działania po awarii również rozpoczyna realizację algorytmu

Elekcji

51. Scharakteryzować algorytm pierścieniowy stosowany podczas elekcji. MDO

- Jeżeli proces Pi wykryje awarię koordynatora, tworzy nową listę aktywną (pusta). Wysyła

komunikat elekcja (i) do sąsiada a swój identyfikator dodaje do swojej listy aktywnej

- Jeżeli proces Pi otrzyma komunikat elekcja (j) to:

- Jeśli jest to pierwszy komunikat o elekcji, to tworzy nową listę aktywną z numerami

i oraz j. Wysyła komunikat elekcja (i) a potem elekcja (j)

- Jeśli i != j, to proces Pi dodaje j do swojej listy aktywnej i przekazuje komunikat

dalej

- Jeżeli i = j to koniec

52. Co to jest transakcja ? KPI

transakcja (działanie niepodzielne) to wysokopoziomowa abstrakcja synchronizacji

procesów w systemach rozproszonych, ukrywająca kwestie techniczne synchronizacji,

takie jak zapobieganie blokadom i rekonstrukcje po awarii. Jest to niepodzielna operacja

wykonywana przez serwer na zamówienie klienta. Przykładem transakcji są bankowe

operacje wpłaty lub wypłaty, sprawdzania stanu konta.

53. Jakie podstawowe właściwości powinna posiadać transakcja i co one oznaczają? KPI

Atomowość (niepodzielność) - każda transakcja jest niepodzielną operacją z punktu

widzenia użytkownika: albo wszystkie akcje wchodzące w skład transakcji są wykonywane

albo żadna z nich.

Spójność - po wykonaniu zbioru transakcji stan bazy danych powinien być spójny

(pod warunkiem, że przy rozpoczynaniu transakcji stan bazy danych był spójny oraz że każda

z wykonywanych transakcji jest z osobna poprawna).

Izolacja - transakcje powinny sobie wzajemnie nie przeszkadzać w działaniu.

Każdy użytkownik powinien mieć iluzję, że sam korzysta z bazy danych. Przy najwyższym

(zalecanym) stopniu izolacji wymaga się aby transakcja działała na spójnym, nie zmienianym

przez innych użytkowników fragmencie bazy danych.

Trwałość - dane zatwierdzone przez transakcję powinny być dostępne nawet w

sytuacji awarii programu, komputera lub nośnika danych.

54. Co oznacza termin „szeregowa równoważność transakcji ? KPI

Transakcje są szeregowane by uniknąć nakładania się na siebie konfliktowych

transakcji

- jeśli każda z transakcji jeśli będzie wykonywana pojedynczo uzyska prawidłowy wynik to

jeśli uszeregujemy te transakcje w pewnym porządku to też uzyskamy prawidłowy wynik

- rownoważny szeregowo przeplot transakcji to taki, w ktorym

końcowy efekt jest taki sam jak w przypadku wykonywania

transakcji kolejno w pewnym określonym porządku:

• operacje odczytu zwracają te same wartości

• zmienne obiektow mają na koniec takie same wartości

55. Na czym polega, związany z przetwarzaniem transakcji, problem „utraconej aktualizacji? KPI

Problem utraconej aktualizacji występuje w przypadku, gdy dwie transakcje uzyskujące

dostęp do tych samych elementów bazy danych są związane z przeplotem ich operacji w taki sposób, iż wartości pewnych elementów bazy danych stają się błędne.

56. Na czym polega, związany z przetwarzaniem transakcji, problem „niespójnego odzyskiwania? KPI

Problem niespójnych odzyskań może pojawić się wtedy, gdy transakcja odzyskująca

działa współbieżnie z aktualizującą.

57. Na czym polega, związany z przetwarzaniem transakcji, problem ”zabrudzonego czytania”? KPI

Problem ten wynika z interakcji między operacją czytania jednej transakcji, a

wcześniejszą operacją pisania innej transakcji, odnoszących się do tego samego obiektu

danych.

Mówimy, że transakcja taka wykonała zabrudzone czytanie (dirty read). Gdy dojdzie

do wycofania wcześniejszej transakcji (T), transakcja realizowana później (U) wykonana

zostanie nieprawidłowo

58. Na czym polega, związany z przetwarzaniem transakcji, problem „przedwczesnego zapisywania”? KPI

• Problem wynika z interakcji między operacjami pisania, odnoszącymi się do tego

samego obiektu danych.

• Gdy dojdzie do wycofania wcześniejszej transakcji (T), po zatwierdzeniu transakcji

realizowanej później (U) to przywrócony zostanie stan początkowy 100 sprzed

obydwu transakcji.

• Aby zagwarantować poprawne wyniki, operacje pisania muszą zostać opóźnione aż

do czasu zatwierdzenia lub zaniechania wcześniejszych transakcji aktualizujących te

same obiekty danych.

59. Jakie są podstawowe założenia metody „optymistycznego sterowania współbieżnością” MDO

Optymistyczne sterowanie współbieżnością. Pokłada się tu nadzieję, że nie wystąpią

żadne konflikty w dostępie do danych. Jeśli dojdzie do konfliktu z innymi współbieżnymi

transakcjami, to nastąpi zaniechanie transakcji i trzeba będzie powtórzyć ją od nowa.

60. Na czym polega legalizacja transakcji w metodzie „optymistycznego sterowania współbieżnością transakcji”? MDO

Podczas legalizacji transakcji w metodzie „optymistycznego sterowania

współbieżnością transakcji” pod uwagę brane są następujące konflikty:

- Ti nie wolno czytać obiektów zapisywanych przez Tk

- Tk nie wolno czytać obiektów zapisywanych przez Ti

- Ti nie wolno zapisywać obietków zapisywanych przez Tk a Tk nie wolno zapisywać

obiektów zapisanych przez Ti

61. Na czym polega metoda blokowania związana ze sterowaniem współbieżnością transakcji? JBO

Każdy serwer nadzoruje blokowanie własnych obiektów danych. Nie może zwolnić blokady, dopóki nie dowie się, że transakcja została zatwierdzona lun zaniechana na wszystkich serwerach zaangażowanych w jej wykonanie.

62. Jakie są zasady zakładania blokad przy stosowaniu metody blokowania związanej ze sterowaniem współbieżnością transakcji? JBO

- Jeżeli operacja w transakcji sięga po obiekt danych:

A. Jeżeli obiekt danych nie jest jeszcze zablokowany to zostaje zablokowany i operacja jest

kontynuowana

B. Jeżeli obiekt jest zablokowany przez inną transakcję w sposób w sposób mogący spowodować

konflikt, to dana transakcja musi poczekać na jego zwolnienie.

C. Jeżeli inna transakcja zablokowała obiekt danych w sposób nie prowadzący do konfliktu, to blokadata podlega dzieleniu i operacja jest kontynuowana

D. Jeżeli obiekt danych został już zablokowany w tej samej transakcji i nie zachodzi pkt. B, to blokada zostaje rozszerzona i operacja jest kontynuowana.

- Gdy dochodzi do zatwierdzenia lub zaniechania transakcji, wówczas zwalniane są wszystkie obiekty danych zajmowane przez tą transakcję.

63. Na czym polega metoda porządkowania według znaczników czasowych związana ze sterowaniem współbieżnością transakcji? JBO

Każdy serwer jest zdolny do wydawania globalnie jednoznacznych znaczników czasu. Znacznik czasu transakcji jest wydawany klientowi podczas pierwszego dostępu transakcji do serwera. Jest on przekazywany każdemu serwerowi, który wykonuje działania w ramach transakcji.

64. Co oznacza termin „transakcje rozproszone proste”? JBO

Prosty ciąg operacji o własności ACID (Atomicity, Consistency, Isolation, Durability). Brak możliwości częściowego zatwierdzenia lub wycofania wyników transakcji w przypadku gdy np. trzeba długo czekać na część wyników, część transakcji się nie powiodła a mimo to chcielibyśmy zaakceptować dotychczasowy częściowy wynik.

65. Co oznacza termin „transakcje rozproszone zagnieżdżone”? JBO

W transakcjach zagnieżdżonych transakcje na tym samym poziomie mogą wykonywać się równolegle. Następuje logiczny podział na szereg podtransakcji. Mogą tworzyć bardziej rozbudowane, kilkupoziomowe hierarchie.

66. Na czym polega protokół zatwierdzania dwufazowego stosowany w czasie legalizacji transakcji rozproszonych?

Protokół zatwierdzania dwufazowego (2PC) - dwuetapowy protokół zatwierdzania transakcji , w którym proces wykonujący transakcję przejmuje funkcję koordynatora, wysyłając do wszystkich zaangażowanych procesów komunikat z pytaniem o gotowość do zatwierdzenia ich cząstkowych prac. Po zebraniu odpowiedzi koordynator informuje podwładnych, czy mogą dokonać zatwierdzeń. Jedna negatywna odpowiedź w pierwszym etapie wymusza zaniechanie transakcji. Wszystkie informacje wymieniane w protokole są skrupulatnie rejestrowane w dzienniku na wypadek awarii.

67. Co oznacza termin „zwielokrotnione usługi transakcyjne”?

(replicated transactional service) to usługi transakcyjne, w których fizyczne kopie każdego z logicznych obiektów danych są zwielokrotnione w grupie serwerów. Serwery te nazywamy zarządcami kopii. Mechanizm zwielokrotnienia musi być przezroczysty dla klientów.

68. Co oznacza termin „szeregowalność na zasadzie jednej kopii”?

(one copy serializability) Skutki transakcji wykonywanych przez różnych klientów na zwielokrotnionych obiektach danych będą takie same, jak gdyby wykonano je po kolei (pojedynczo) na pojedynczych obiektach danych.

76. Jakie są podstawowe cechy architektoniczne systemu NFS?

NFS (Network File System) - sieciowy system plików stworzony przez firmę Sun Microsystems

• Pracuje w środowisku heterogenicznym

• Oferuje wiele poziomów przeźroczystości m.in.:

- Położenia

- Dostępu

- Wędrówki

• Pozwala na importowanie i eksportowanie danych

• Każdy komputer może pełnić jednocześnie role klienta i serwera

77. Jakie są podstawowe zasady działania systemu NFS?

NFS oferuje przeźroczysty dostęp do plików, a klienci tego systemu nie są w zasadzie świadomi gdzie znajduje się plik, na którym operują. NFS należy do systemów, które bazują na modelu zdalnego dostępu. Aby zrealizować taki model dostępu posłużono się warstwą wirtualnego systemu plików, który pośredniczy pomiędzy warstwą wywołań systemowych, a rzeczywistym systemem plików, zdalnym lub lokalnym. Jeżeli okazuje się, że klient żąda dostępu do lokalnego systemu plików żądanie przekazywane jest do lokalnego systemu plików. W przeciwnym razie, gdy żądanie odwołuje się do pliku na zdalnym komputerze informacja o tym przekazywana jest do warstwy klient NFS, która komunikuje się ze zdalnym serwerem NFS. Serwer NFS poprzez warstwę wirtualnego systemu plików stara si zrealizować żądanie i odsyła ewentualny wynik do klienta.

78. Jakie są podstawowe cechy architektoniczne systemu „Andrew”?

AFS ma przewagę nad tradycyjnymi sieciowymi systemami plików, głównie w kwestiach bezpieczeństwa i skalowalności. Produkcyjne instalacje AFS nierzadko przekraczają 50 tys. klientów. AFS stosuje uwierzytelnianie protokołem Kerberos i listy kontroli dostępu na katalogach dla użytkowników i grup. Buforowanie po stronie klienta zwiększa wydajność systemu i pozwala na ograniczony dostęp w przypadku awarii serwera lub sieci.

Znaczącą cechą AFS jest wolumin, czyli drzewo plików i podkatalogów. Woluminy tworzone są przez administratorów i podłączane do poszczególnych ścieżek w komórce AFS. W stworzonym woluminie użytkownicy systemu plików mogą tworzyć katalogi i pliki w zwykły sposób, nie zajmując się jego fizyczną lokalizacją. W razie potrzeby administrator może przenieść wolumin na inny serwer lub dysk bez potrzeby informowania o tym użytkowników: operacja może przebiegać w czasie, kiedy wolumin jest używany.

Woluminy mogą być też zreplikowane do jedenastu kopii do odczytu. Kiedy aplikacja kliencka korzysta z plików tylko do odczytu, dane pobiera się z jednej z tych kopii. Jeśli w jakimś momencie przestanie być dostępna, aplikacja poszuka innej. Analogicznie, użytkownicy tych danych nie muszą się zajmować fizyczną lokalizacją tych kopii, a administratorzy mogą je tworzyć i przemieszczać w razie potrzeby. Zestaw poleceń AFS gwarantuje, że woluminy do odczytu zawierają dokładną kopię oryginalnego woluminu typu odczyt-zapis.

79. Jakie są podstawowe zasady działania systemu „Andrew”?

Przestrzeń nazw na stacji roboczej używającej AFS jest podzielona na wspólną (ang. shared) i lokalną (ang. local). Wspólna przestrzeń nazw jest identyczna na wszystkich stacjach, zaś lokalne są różne i zawierają pliki tymczasowe potrzebne podczas uruchamiania. Obie przestrzenie nazw mają strukturę hierachiczną. Każde poddrzewo w przestrzeni wspólnej jest przypisane do jednego serwera zwanego nadzorcą. Pliki z przestrzeni wspólnej są na żądanie buforowane na stacji lokalnej. Polecenia odczytu i zapisu pliki są wykonywane na lokalnej kopii. Jeśli buforowany plik został zmodyfikowany, jest kopiowany do nadzorcy po zamknięciu. Spójność bufora jest utrzymywana przez mechanizm odwołań (ang. callback). Kiedy plik jest buforowany, nadzorca odnotowuje to i informuje klienta, kiedy jest on modyfikowany przez kogoś innego.

80. Jakie są podstawowe cechy architektoniczne systemu „Coda”?

Coda jest rozproszonym systemem plików opracowanym w Carnagie Mellon University (CMU). Jednym z głównych celów systemu Coda jest uzyskanie wysokiej dostępności. Aby to osiągnąć Coda używa m.in. mechanizmu pamięci podręcznej. Poza dostępnością w systemie Coda duży nacisk położono również na skalowalność i bezpieczeństwo. System charakteryzuje się również przeźroczystością lokalizacji, nazewnictwa oraz przeźroczystością awarii. Poza tym Coda dostarcza globalnie dzielonej przestrzeni nazw.

Bardzo przydatną cechą systemu jest możliwość wykonywania operacji na danych, gdy klient jest czasowo odłączony od sieci lub odpowiednie serwery nie są dostępne.

Coda wywodzi się z wcześniejszego systemu plików AFS. Architektura systemu. Coda jest z tego względu, pod wieloma względami identyczna jak w systemie AFS. Komputery, które korzystają z systemu Coda podzielone są na dwie grupy. Pierwsza grupa nazwana Vice składa się z pewnej liczby serwerów plików. Druga grupa to komputery użytkowników określane jako Virtue. Virtue pozwalają użytkownikom na dostęp do systemu plików. W ramach każdej stacji Virtue znajduje się proces użytkownika, Venus. Venus oprócz funkcji udostępniania klientowi danych z serwera, odpowiedzialny jest za umożliwienie użytkownikowi kontynuowanie operacji na plikach nawet jeżeli niedostępne są chwilowo serwer plików.

81. Jakie są podstawowe zasady działania systemu „Coda”?

Coda jest systemem plików, który umożliwia zwielokrotnianie plików modyfikowalnych. Zanim krótko opiszemy mechanizm zwielokrotniania przedstawimy niezbędne pojęcia. Plik w systemie Coda przechowywane są w tzw. tomach (ang. volumes). Tom można porównać do fragmentu systemu plików, który udostępnia jakiś użytkownik. Zbiór serwerów, które maja kopię tomu nazywamy grupą przechowywania tomu (ang. Volume Storage Group, VSG). W wypadku gdy na skutek awarii klient będzie miał dostęp tylko do części do serwerów, grupę tych serwerów określamy jako dostępna grupa przechowywania tomu (ang. Accessible Volume Storage Group, AVSG). Jeżeli grupa AVSG jest pusta, mówimy że klient jest odłączony.

System Coda używa optymistycznej strategii zwielokrotniania. Klienci mogą jednocześnie

modyfikować ten sam plik. W ten sposób powstaje wiele wersji pliku, które przesyłane są do odpowiednich grup AVSG. Kluczowe jest tu zagadnienie wykrywania niespójności i usuwanie ich.

W tym celu Coda używa wektorów wersji Coda (ang. Coda version vector), CVV. Taki wektor wersji posiada każdy plik. Poszczególne pozycje wektora odpowiadają liczbie modyfikacji pliku wykonanych przez serwery z grupy AVSG.

105. Wyjaśnić terminy: dostępność, niezawodność, pewność, pielęgnowalność. DKO

Dostępność - gotowość systemu do natychmiastowego działania.

Niezawodność - zdolność do ciągłego działania.

Pewność - chwilowa awaria pojedynczego komponentu nie powoduje katastrofalnych

skutków.

Pielęgnowalność - łatwość naprawiania uszkodzonego systemu.

106. Wyjaśnić terminy: błąd, wada, awaria, tolerowanie awarii. DKO

Błąd - część stanu systemu wskutek którego może dojść do awarii.

Wada - przyczyna błędu.

Awaria - widoczna niezdolność do wykonywania funkcji wskutek błędu lub wady.

Tolerowanie awarii - możliwość świadczenia usług pomimo wystąpienia wad.

107. Przedstawić klasyfikację wad i scharakteryzować poszczególne grupy klasyfikacyjne DKO

Wady przejściowe - pojawiają się i znikają (powtórzenie operacji może spowodować zanik

wady).

Wady nieciągłe - pojawiają się i znikają samoistnie (nawracają - są trudne do wykrycia).

Wady trwałe - nie ustępują aż do naprawy.

108. Przedstawić klasyfikację awarii i scharakteryzować poszczególne grupy klasyfikacyjne. DKO

Załamanie - trwałe zatrzymanie systemu, który dotąd pracował poprawnie.

Awaria ominięcia - brak odpowiedzi serwera (serwer nie odbiera żądań lub nie wysyła

odpowiedzi)

Awaria odliczania czasu - odpowiedź nie pojawia się w określonym przedziale czasowym.

Awaria odpowiedzi - błędna odpowiedź na żądanie lub awaria zmiany stanu.

---