110 - 123, WAT, SEMESTR VIII, Systemy rozproszone, egzamin

110. Scharakteryzować zastosowanie nadmiarowości w maskowaniu awarii

Są 3 rodzaje nadmiarowości : informacji, czasu, fizyczna.

Nadmiarowość informacji tworzą dodatkowe bity umożliwiające odtwarzanie zniekształconych bitów (np. dodanie kodu Hamminga do danych przesyłowych).

Nadmiarowość czasu – wykonanie działania i – w razie potrzeby – jego powtórzenie (np. użycie transakcji).

Nadmiarowość fizyczna powstaje przez dodanie specjalnego wyposażenia, aby system jako całość mógł tolerować utratę pewnych składowych lub ich wadliwe działanie. Nf możemy realizować sprzętowo i programowo.

111. Scharakteryzować algorytm wykrywania awarii procesu

Z praktycznego punktu widzenia, zawodny rozproszony detektor awarii (ang.  failure detector) można

definiować jako zbiór „wyroczni”, które są powiązane z poszczególnymi procesami biorącymi udział w

przetwarzaniu rozproszonym. Zadaniem tych wyroczni jest dostarczanie listy procesów

podejrzewanych o niepoprawne działanie (czyli takich, które uległy awarii). 

Wyrocznie te mogą być omylne, co oznacza, że mogą podejrzewać o awarię procesy poprawne, lub

też odwrotnie – nie podejrzewać procesów niepoprawnych. Błędne podejrzenia są oczywiście

niepożądane, ale w praktyce są akceptowalne, o ile nie powstrzymują poprawnych procesów przed

zachowaniem się zgodnie z ich specyfikacją. Dlatego też mówi się,  że detektor podejrzewa, a nie

wykrywa proces niepoprawny.

Ponadto, w momencie stwierdzenia przez wyrocznię awarii procesu, proces ten powinien znaleźć się

na liście procesów podejrzanych. Natomiast w przypadku odwrotnym, gdy wyrocznia stwierdzi,  że

proces jest poprawny, proces ten powinien być usunięty z listy procesów podejrzewanych.

Informacje dostarczane przez detektor są tym dokładniejsze, im większy synchronizm systemu

rozproszonego. Właściwości detektorów możliwych do zaimplementowania w systemie określają

stopień jego synchroniczności.

112. Scharakteryzować typowe błędy powstające przy stosowaniu komunikacji poprzez wywoływanie procedur zdalnych

Klient nie potrafi znaleźć serwera

Serwer może być wyłączony lub w oprogramowaniu klienta została skompilowana namiastka pewnej starej wersji, a na serwerze zainstalowano nową wersję interfejsu, wygenerowano i dołączono nowe namiastki. Po ponownym uruchomienia klienta łącznik nie będzie mógł dopasować go do serwera i zasygnalizuje błąd.

Komunikat z zamówieniem od klienta do serwera zaginął

Serwer ulega awarii po odebraniu zamówienia

Serwer może ulec awarii po wykonaniu zamówienia, a przed wysłaniem odpowiedzi lub też zaraz po odebraniu zamówienia, przed jego wykonaniem.

Komunikat z odpowiedzią serwera dla klienta zaginął

Klient ulega załamaniu po wysłaniu zamówienia

113. Wyjaśnić terminy: punkt kontrolny, odcięcie, linia odtwarzania

Punkt kontrolny – zapisany stan systemu, z którego można go odtworzyć w razie awarii.

Odcięcie – graficzne przedstawienie stanu globalnego (stan lokalny każdego procesu + aktualnie kursujące komunikaty). Rozróżniamy obcięcie spójne i niespójne

Linia odtwarzania – najnowsza migawka rozproszona (spójny stan globalny). Odpowiada najnowszemu obcięciu spójnemu.

114. Scharakteryzować zastosowanie rejestratora komunikatów podczas odtwarzania stanu systemu

U podstaw rejestrowania komunikatów leży pomysł, że możliwość powtórzenia transmisji komunikatów zapewni osiągnięcie stanu globalnie spójnego bez konieczności odtwarzania go z pamięci trwałej. Zamiast tego pobieramy stan z punktu kontrolnego, przyjmując go za początkowy, i odpowiednio retransmitujemy wszystkie komunikaty wysłane już po tym punkcie.

115. Wyjaśnić termin „rozproszona pamięć dzielona”

DSM (distributed shared memory) – pamięć wykorzystująca możliwości pamięci wirtualnej poszczególnych węzłów.

Inna definicja:

Rozproszona pamięć dzielona (ang. distributed shared memory, w skrócie DSM) jest abstrakcją używaną do określenia wspólnego użytkowania danych przez procesy, które nie dzielą pamięci fizycznej. Pamięć dzielona stanowi część przestrzeni adresowej procesów i mogą one z niej korzystać w standardowy sposób. Zadaniem systemu operacyjnego ew. systemu wykonawczego jest zapewnienie w sposób przezroczysty dostępu do wspólnych danych (emulowanie wspólnej pamięci fizycznej).

116. Scharakteryzować metody implementacji rozproszonej pamięci dzielonej

Wsparcie przez stronicowanie. Systemy Ivy, Munin, Clouds realizują pamięć DSM jako obszar pamięci wirtualnej zajmujący ten sam przedział adresów w przestrzeni adresowej każdego z uczestniczących procesów. Spójność danych jest utrzymywana przez jądro jako część procedury obsługi błędów strony.

Wsparcie biblioteczne. Języki programowania takie jak Linda i Orca dostarczają DSM w postaci współdzielonych obiektów. Ich obsługą zajmują się systemy wykonawcze (ang. runtime system) tych języków. Procesy korzystają z obiektów za pomocą wywołań bibliotecznych wstawionych przez kompilator. Procedury biblioteczne korzystają z lokalnych obiektów, komunikując się ze zdalnymi systemami w niezbędnych przypadkach utrzymania spójności.

117. Scharakteryzować metody zapewniania spójności stronicowanej rozproszonej pamięci dzielonej

Jeśli strony nie są zwielokrotniane, to problem osiągania spójności nie istnieje. Każda strona występuje dokładnie w jednym egzemplarzu i jest przemieszczana gdzie trzeba, stosownie do potrzeb. Zwielokrotnienie stron przeznaczonych tylko do czytania również nie powoduje kłopotów. Strony takie nigdy nie są zmieniane, więc wszystkie kopie są zawsze takie same. Strony do czytania i zapisywania utrzymuje się w pojedynczych egzemplarzach, więc również one nie mogą stać się przyczyną niespójności. W wielu systemach DSM próba przeczytania przez proces zdalnej strony powoduje utworzenie lokalnej kopii, ponieważ system nie wie, co znajduje się na strome lub czy jest ona do zapisywania.. Dopóki wszystkie odwołania są operacjami czytania, dopóty wszystko jest w porządku. Jednak gdy jakikolwiek proces spróbuje zapisać zwielokrotnioną stronę, powstaje problem ewentualnej niespójności, gdyż zmiana jednej kopii i pozostawienie innych swojemu losowi jest nie do przyjęcia.Ogólnie biorąc, w wieloprocesorach stosuje się dwa podejścia: aktualizowanie i unieważnianie. Przy aktualizowaniu dopuszcza się lokalne zapisy, lecz w tej samej chwili adres oraz nowa wartość zmodyfikowanego słowa zostają rozgłoszone wszystkim innym pamięciom podręcznym. Każda z pamięci podręcznych, przechowująca słowo o danym adresie, spostrzegłszy jego zmianę, aktualizuje je, zastępując starą wartość nową, pobraną z szyny. W efekcie wszystkie pamięci podręczne, które przechowywały słowo przed jego aktualizacją, przechowują je również potem, nabywając nową jego wartość. Wieloprocesory mogą także dokonywać unieważnień. Strategia ta polega na rozgłaszaniu w szynie samego adresu aktualizowanego słowa bez jego nowej wartości. Jeśli pamięć podręczna stwierdzi. że któreś z jej słów podlega aktualizacji, to unieważnia swój blok zawierający to słowo, co jest równoznaczne z jego usunięciem. W efekcie doprowadza się do tego, że tylko jedna pamięć podręczna przechowuje zmodyfikowane słowo, dzięki czemu unika się problemu spójności. Jeżeli któryś z procesorów obecnie utrzymujących unieważnioną kopię bloku pamięci podręcznej spróbuje go użyć, to dostanie sygnał o braku danych w pamięci podręcznej i sprowadzi blok z procesora, który przechowuje ważną kopię. Podczas wykonywania programu stan strony może się zmieniać. W dowolnej chwili może być ona w stanieR (zdatna do czytania) albo w stanie W (zdatna do czytania i zapisu). Każda strona ma właściciela, tj. proces, który ostatnio ją zapisywał. Gdy strona jest w stanie W, wówczas istnieje tylko jedna jej kopia, odwzorowana w przestrzeni adresowej właściciela w trybie pisanie-czytanie. Kopia strony w stanie R znajduje się u właściciela (odwzorowana jako zdatna tylko do czytania), lecz mogą ją mieć także inne procesy.

118. Scharakteryzować metody zastępowania stron w stronicowanej rozproszonej pamięci dzielonej

W systemie DSM, jak w każdym systemie z pamięcią wirtualną, może się zdarzyć, że w pamięci brakuje wolnej ramki na przechowanie potrzebnej strony. W celu zrobienia dla niej miejsca należy w takiej sytuacji wyrzucić jakąś stronę. Rodzi to natychmiast dwa podproblemy: którą stronę wyeksmitować i dokąd. Wyboru strony do wyrzucenia można w większości przypadków dokonać za pomocą tradycyjnych algorytmów pamięci wirtualnej, zbliżonych do algorytmu najdawniej używanych stron (LRU). W systemie rozproszonej pamięci dzielonej (DSM) utrudnieniem są wystąpienia spontanicznych unieważnień stron (będących wynikiem działania innych procesów). Podobnie jak w konwencjonalnych algorytmach, warto utrzymywać informacje o "czystości" lub "zabrudzeniu" stron. W kontekście systemu DSM zawsze pierwsza do usunięcia jest strona zwielokrotniona, będąca własnością innego procesu, ponieważ wiadomo, że istnieje jej kopia. Jeżeli do utrzymywania informacji o kopiach używa się schematu katalogowego, to właściciel lub zarządca stron musi być o tym poinformowany. Jeżeli strony lokalizuje się za pomocą rozgłaszania, to stronę można po prostu usunąć. Drugą bardzo dobrą możliwością wyboru strony do wyeksmitowania jest wytypowanie zwielokrotnionej strony będącej własnością wyrzucającego procesu. Wystarczy przekazać prawo własności jednej z innych kopii, informując o tym dany proces, zarządcę stron lub obu - zależnie od implementacji. Nie trzeba przenosić samej strony i dzięki temu komunikat jest krótszy. Jeżeli nie można wybrać odpowiedniej kandydatki spośród stron zwielokrotnionych, to trzeba dokonać wyboru strony nie zwielokrotnionej, na przykład najdawniej używanej i ważnej. Można się jej pozbyć dwoma sposobami. Pierwszy polega na zapisaniu jej na dysku, jeśli taki istnieje. Drugi sposób polega na przekazaniu strony innemu procesorowi.

119. Scharakteryzować metody odnajdowania kopii w stronicowanej rozproszonej pamięci dzielonej

.

Istnieje kilka możliwości. Pierwszą z nich jest ogłoszenie komunikatu podającego numer strony i proszącego wszystkie procesory utrzymujące stronę o tym numerze o jej unieważnienie. Można to zastosować tylko wówczas, gdy wszystkie komunikaty są przesyłane niezawodnie i nigdy nie giną.

Druga możliwość polega na utrzymywaniu przez właściciela lub zarządcę stron wykazu lub zbioru kopii (ang. copyset) określającego, które procesory przechowują które strony.

120. Scharakteryzować mechanizmy zastosowane w systemie Munin

Munin jest systemem rozproszonej pamięci dzielonej opartym na obiektach programowych, z których każdy może być umieszczony na osobnej stronie, więc do wykrywania dostępów do obiektów dzielonych można wykorzystać sprzętową jednostkę zarządzania pamięcią. Podstawowy model zastosowany w systemie Munin składa się z wielu procesorów, a każdy z nich jest wyposażony w stronicowaną, liniową przestrzeń adresową, w której jeden lub więcej wątków wykonuje nieco zmodyfikowany program wieloprocesorowy. W projekcie systemu Munin przyjęto za cel, aby po wykonaniu niewielkich adaptacji można było wydajnie wykonywać istniejące programy wieloprocesorowe w systemach multikomputerowych przy użyciu pewnej formy rozproszonej pamięci dzielonej. Dobre działanie osiąga się za pomocą rozmaitych technik. W celu wykonania programu na jednym z procesorów rozpoczyna działanie proces główny. Proces ten może generować nowe procesy na innych procesorach, które odtąd działają równolegle z procesem głównym, komunikując się z nim i między sobą za pomocą zmiennych dzielonych, tak jak to robią zwykłe programy wieloprocesorowe. Proces raz rozpoczęty na pewnym procesorze nie może być z niego przeniesiony.

Zmienne dzielone są osiągalne za pomocą zwykłych instrukcji czytania i pisania z listy rozkazów jednostki centralnej. Nie stosuje się żadnych specjalnych metod ochrony. Próba użycia nieobecnej zmiennej dzielonej powoduje wystąpienie błędu braku strony i przejęcie sterowania przez system Munin.

Synchronizacja wzajemnego wyłączania jest wykonywana w specjalny sposób, pozostający w ścisłym związku z modelem spójności pamięci. Można deklarować zmienne zamykające, jak również korzystać z bibliotecznych procedur ich domykania (zajmowania) i otwierania. Istnieje również możliwość wykorzystania zapór, zmiennych warunkowych i innych zmiennych synchronizujących.

121. Scharakteryzować mechanizmy zastosowane w systemie Midway

Midway jest systemem rozproszonej pamięci dzielonej opartym na dzieleniu poszczególnych struktur danych. Pod pewnymi względami przypomina system Munin, lecz ma także sporo nowych właściwości. Jego zadaniem jest umożliwienie wykonywania na multikomputerach istniejących i nowych programów wieloprocesorowych przy niewielkich zmianach kodu.

Programy w systemie Midway to w zasadzie konwencjonalne programy wzbogacone przez programistę pewnymi uzupełniającymi informacjami. Do wyrażania równoległości programy w systemie Midway używają pakietu wątków C systemu Mach. Wątek może się rozwidlać w dwa lub więcej wątków. Wątki pochodne (dzieci) wykonują się równolegle z wątkiem rodzicielskim oraz ze sobą nawzajem, nie wykluczone, że na osobnych maszynach (tj. każdy wątek jako osobny proces). Wszystkie wątki dzielą tę samą, liniową przestrzeń adresową, która zawiera zarówno dane prywatne, jak i dane dzielone. Zadaniem systemu Midway jest utrzymywanie spójności zmiennych dzielonych.

122. Scharakteryzować mechanizmy zastosowane w systemie Linda

Rozproszona pamięć dzielona oparta na obiektach.  Abstrakcyjna przestrzeń krotek. System wolny od szczegółów stronicowania.

123. Scharakteryzować mechanizmy zastosowane w systemie Orca

Współdzielone obiekty.

System Orca dostarcza modelu, w którym na wielu maszynach są zwielokrotniane obiekty danych, a dostęp do nich odbywa się za pomocą chronionych metod, które sprawiają, że obiekty stają się dla programisty spójne sekwencyjnie