SYSTEMY OPERACYJNE – II Semestr (do Dariusza Majki)

wykład

4. Pamięć operacyjna

Pamięć – podstawowy zasób do przechowywania danych i programów

• o strukturze hierarchicznej – rejestr procesora, pamięć podręczna, pamięć główna, pamięć masowa

• na wyższym poziomie przechowywane dane stanowiące fragment zawartości poziomu niższego

• tablica bajtów, w której adresy są indeksami

• pamięć mniej oddalona jest szybsza

Trafienie żądane dane zostały znalezione w pamięci określonego poziomu

Współczynnik trafień procentowa wartość operacji dostępu do pamięci znajdującej się na określonym poziomie, które zakończyły się pobraniem danych

Czas trafienia czas wymagany do pobrania żądanych danych z pamięci znajdującej się na określonym poziomie

Chybienie żądane dane nie zostały znalezione w pamięci określonego poziomu

Współczynnik chybień procentowa wartość operacji dostępu do pamięci znajdującej się na określonym poziomie, które nie zakończyły się pobraniem danych

Czas chybienia czas wymagany na przetworzenie chybienia, który jest sumą czasu potrzebnego na zastąpienie bloku pamięci znajdującej się na wyższym poziomie i dodatkowego czasu związanego z dostarczeniem żądanych danych do procesora. Czas wymagany na przetworzenie chybienia zazwyczaj jest znacznie dłuższy niż w przypadku przetwarzania trafienia

Hierarchia pamięci

• malejący koszt na bit

• rosnąca pojemność

• rosnący czas dostępu

• malejąca częstotliwość dostępu do pamięci przez procesor

RAM

• pamięć o dostępie swobodnym

• odczytywanie/zapisywanie danych z/do pamięci za pomocą sygnałów elektrycznych

• ulotność

• statyczne i dynamiczne

Dynamiczne:

• przechowują ładunek elektryczny (1 lub 0)

• wymagają okresowego odświeżania ładunku w celu zachowania danych

• ulotne

• prostsza konstrukcja i bardziej upakowana niż statyczna

• coraz większa pojemność

• malejące koszty

• zastosowanie: pamięć główna

Statyczne

• wartości przechowywane za pomocą konfiguracji bramek logicznych

• ulotne

• droższe niż dynamiczne

• nie wymagają odświeżania

• szybsze niż dynamiczne

• zastosowanie: pamięć podręczna

Pamięć operacyjna (PAO) – jeden wielki obszar pamięci dostępny dla procesora w którym znajdują się programy wykonywane.

• Tworzy tablicę słów lub bajtów; Każde słowo ma własny adres

• Jednostka centralna pobiera rozkazy z PAO stosownie do wartości licznika rozkazów

Dzielenie pamięci przechowywanie w PAO wielu procesów jednocześnie

Kolejka wejściowa zbiór procesów oczekujących na dysku w celu wprowadzenia do pamięci operacyjnej

Czas kompilacji generowanie kodu bezwzględnego, jeżeli na etapie kompilacji znane jest miejsce przebywanie procesu w pamięci. W systemie MS-DOS są to pliki *.COM

Czas ładowania wygenerowanie przez kompilator kodu przemieszczalnego, gdy podczas kompilacji nie wiadomo gdzie będzie umieszczony proces w pamięci

Czas wykonywania jeżeli proces może ulegać przemieszczeniom w pamięci operacyjnej podczas wykonywania, to z wiązaniem adresów należy poczekać, aż do czasu wykonania

Ładowanie dynamiczne

• Program nie jest wprowadzany do pamięci, dopóki nie zostanie wywołany.

• Ładowanie poprzez wywołanie programu łączącego i ładującego moduły przemieszczalne

• nigdy nie zostanie załadowany podprogram, którego się nie używa

Konsolidacja dynamiczna

• umieszczenie w obrazie binarnym namiastki procedury, która jest małym fragmentem kodu, wskazującym jak odnaleźć odpowiedni, rezydujący w pamięci podprogram lub jak załadować bibliotekę

• konsolidacja dynamiczna wymaga wsparcia ze strony systemu operacyjnego

Nakładki stosowane są w celu umożliwienia zwiększenia wymiarów procesów ponad ilość przydzieloną w pamięci. W pamięci przechowywane są tylko te rozkazy i dane, które są stale potrzebne.

Adres logiczny (adres wirtualny) adres wytworzony przez procesor. Zbiór wszystkich adresów logicznych wytworzonych przez program nazywa się logiczną przestrzenią adresową.

Adres fizyczny adres oglądany przez jednostkę pamięci. Zbiór wszystkich adresów fizycznych odpowiadających adresom logicznym nazywa się fizyczną przestrzenią adresową.

Wytaczanie, wtaczanie wariant wymiany stosowany w algorytmach planowania priorytetowego. Dochodzi do wymiany procesu o niższym priorytecie na rzecz procesu o wyższym priorytecie.

Przydział ciągły

• Pamięć operacyjna zawiera zarówno system operacyjny jak i procesy użytkownika.

• konieczność zabezpieczenia kodu i danych systemu operacyjnego przed zmianami

  • Rejestr przemieszczenia - zawiera wartość najmniejszego adresu fizycznego

  • Rejestr graniczny - zawiera zakres adresów logicznych

Dynamiczny przydział pamięci polega na rozstrzygnięciu, w jaki sposób na podstawie listy o wolnych dziurach spełnić zapotrzebowanie za obszar o rozmiarze N

• Pierwsze dopasowanie (ang. First fit) przydziela pierwszą dziurę o wystarczających rozmiarach. Szukanie odbywa się od początku listy lub od miejsca, w którym je ostatnio zakończono.

• Najlepsze dopasowanie (ang. Best fit) przydziela się najmniejszą z dostatecznie dużych dziur. Należy przejrzeć cała listę, chyba że jest ona uporządkowana według rozmiarów.

• Najgorsze dopasowane (ang. Worst fit) przydziela się największą z dostatecznie dużych dziur. Należy przejrzeć cała listę, chyba że jest ona uporządkowana według rozmiarów.

Fragmentacja zewnętrzna suma wolnych obszarów w pamięci wystarcza na spełnienie zamówienia, ale nie tworzą one spójnego obszaru.

Fragmentacja wewnętrzna bezużyteczny kawałek pamięci wewnątrz przydzielonego obszaru

Upakowanie pamięci rozwiązanie problemu zewnętrznej fragmentacji

Stronicowanie zezwolenie na to, aby procesowi można było przydzielać dowolne dostępne miejsca w pamięci.

• Pamięć fizyczna podział na bloki stałej długości zwane ramkami

• Pamięć logiczna podział na bloki takiego samego rozmiaru zwane stronami

• Przy wykonywaniu procesu, strony z pamięci pomocniczej wprowadzane są w odpowiednie ramki pamięci operacyjnej.

• Rozmiary stron i ramek są identyczne.

• Do ochrony pamięci w środowisku stronicowanym służą bity ochrony. Jeden bit określa, czy dana strona jest dostępna do czytania, czy też również do pisania.

Segmentacja schemat zarządzania pamięcią, który urzeczywistnia opisany dotychczas sposób widzenia pamięci przez użytkownika

• Użytkownik określa adres za pomocą dwu wielkości: nazwy segmentu i odległości.

• Adres logiczny: <numer segmentu, odległość>

• Każdy proces otrzymuje swój własny obszar pamięci, realizowany poprzez rejestry segmentowe

5. Pamięć wirtualna

Pamięć wirtualna

• technika umożliwiająca wykonywanie procesów, chociaż nie są one w całości przechowywane w PAO

• Pozwala na odseparowanie pamięci logicznej od pamięci fizycznej

  • żeby program mógł być wykonany potrzebne jest przechowywanie w PAO tylko pewnych części programu (np. fragmenty programów do obsługi błędów).

  • logiczna przestrzeń adresowa (niezbędna do wykonania programu) może być znacznie większa od dostępnej fizycznej przestrzeni adresowej

• realizowana przez:

  • stronicowanie na żądanie

  • segmentację na żądanie

Stronicowanie na żądanie

• Procesy przebywają w pamięci pomocniczej

• Proces traktujemy jako ciąg stron (procedura wymiany operuje całymi procesami, a poszczególnymi stronami procesu zajmuje się procedura stronicująca)

• Procedura stronicująca sprowadza do pamięci tylko strony niezbędne wykorzystując tzw. bit poprawności:

  • wartość poprawne - odwołanie do strony jest dozwolone (strona jest w PAO)

  • wartość niepoprawne:

    • dana strona jest niedozwolona (nie należy do logicznej przestrzeni adresowej procesu)

    • dana strona jest dozwolona (w tej chwili znajduje się na dysku), tzw. brak strony

Problem - brak stron (nadprzydział pamięci)

Zastępowanie stron

• zlokalizowanie potrzebnej strony na dysku

• odnalezienie wolnej ramki

  • jeżeli istnieje wolna ramka, to zostanie użyta

  • w przeciwnym razie algorytm zastępowania stron

  • stronę ofiarę zapisuje się na dysku, towarzyszy temu stosowna zmiana stron i tablic

• wczytanie potrzebnej strony do (świeżo) zwolnionej ramki i zmiana tablicy stron i ramek

• wznowienie działania procesu

Algorytmy zastępowania stron

• Algorytm FIFO (first-in first-out)

• Algorytm optymalny (nazywany OPT lub MIN) - zastąp tę stronę, która najdłużej nie będzie używana

• Algorytm LRU (Least Recently Used) - zastępowanie najdawniej używanych stron

• Algorytmy przybliżające metodę LRU

  • algorytm dodatkowych bitów odwołań - wykorzystujący 8-bitowy bajt w tablicy w PAO odzwierciedlający historię odwołań do strony

  • algorytm drugiej szansy - FIFO + bit odniesienia (przyjmujący wartość 1 gdy strona była używana)

  • ulepszony algorytm drugiej szansy - FIFO + bit odniesienia (przyjmujący wartość 1 gdy strona była używana) + bit modyfikacji (przyjmujący wartość 1 gdy strona była modyfikowana)

• Algorytmy zliczające ilość odwołań do stron:

  • algorytm LFU (least frequently used) - strona najrzadziej używana

  • algorytm MFU (most frequently used) - strona najczęściej używana

• Algorytmy buforowania stron - uzupełnienie ww. algorytmów utrzymujące pulę wolnych ramek do której trafiają strony zanim znajdą się na dysku

Przydział ramek

• Algorytmy przydziału:

  • przydział równy

  • przydział proporcjonalny

• Zastępowanie ramek:

  • zastępowanie globalne

  • zastępowanie lokalne

Szamotanie Gdy proces spędza więcej czasu na stronicowaniu niż na wykonywaniu

6. Struktura pamięci pomocniczej

Struktura dysku

• wielkie, jednowymiarowe tablice bloków logicznych

• jednowymiarowa tablica bloków logicznych sekwencyjnie odwzorowana na sektory na dysku

• sektor 0 jest pierwszym sektorem na pierwszej ścieżce najbardziej zewnętrznego cylindra

• dalsze odwzorowanie odbywa się wzdłuż tej ścieżki, następnie wzdłuż pozostałych ścieżek i w głąb cylindrów (od zewnętrznego o wewnętrznego)

• nowoczesne dyski organizowane są w grupy cylindrów

• liczba sektorów na ścieżce jest stała w obrębie grupy (wzrasta liczba sektorów przypadających na ścieżkę przy przemieszczeniu się od grup wewnętrznych ku zewnętrznym)

Planowanie dostępu do dysku

• prędkość obrotowa

• szybkość dysku

• szerokość pasma dysku – łączna liczba przesyłanych bajtów podzielona przez łączny czas, jaki upływa od pierwszego zamówienia a usługę dyskową do chwili zakończenia ostatniego przesłania

Kolejka 98, 183, 37, 122, 14, 124, 65, 67 (początek na 53)

• FCFS – first-come, first-served) 53, 98, 183, 37, 122, 14, 124, 65, 67

• SSTF (shortest seek time first) 53, 65, 67, 37, 14, 98, 122, 124, 183, 199

• SCAN 53, 37, 14, 0, 65, 67, 98, 122, 124, 183, 199

• C-SCAN 53, 65, 67, 98, 122, 124, 183, 199, 0, 14, 37

• LOOK

• C-LOOK 53, 65, 67, 98, 122, 124, 183, 14, 37

Zarządzanie dyskiem / Zarządzanie obszarem wymiany

Formatowanie dysku:

• formatowanie fizyczne (niskiego poziomu) umieszczenie specjalnej struktury danych we wszystkich miejscach na dysku dpowiadających sektorom (nagłówek, obszar danych, zakończenie)

  • nagłówek i zakończenie zawierają ECC (error-correcting code)

• formatowanie logiczne czyli tworzenie systemu plików

Bloki uszkodzone:

• format, chkdsk, scandisk, fsck

• metoda sektorów zapasowych (przenoszenie sektorów)

• metoda przeciągania sektorów

Obszar wymiany

Niezawodność dysku

• wiele dysków pracujących niezależnie i równolegle

• poprawa niezawodności przez wykorzystanie nadmiarowości (redundancji)

• RAID - Redundant Array of Independent Disks - redundancja tablica niezależnych dysków

• sześć poziomów (od 0 do 5)

• brak zależności hierarchicznej

RAID 0

• nie przewiduje redundancji

• dane użytkownika i dane systemowe są rozproszone na wszystkich dyskach

• dane są układane w postaci pasków na dostępnych dyskach

• wzrasta szybkość:

  • jeśli dwa różne żądania we/wy dotyczą dwóch różnych bloków danych istnieje duże prawdopodobieństwo że potrzebne bloki znajdują się na różnych dyskach

  • równoległe przeszukiwanie dysków

  • skraca oczekiwanie w kolejkach (transferu we/wy)

  • oprogramowanie zarządzania tablicą musi być uruchamiane w podsystemie dyskowym lub komputerze macierzystym

RAID 1

• zwierciadlane dyski (duplikowanie wszystkich danych)

• wykorzystywane jest paskowanie danych jak w RAID 0

• każdy pasek logiczny odwzorowywany jest na dwóch oddzielnych dyskach fizycznych

• czytanie z dowolnego dysku (z tego który ma krótszy czas dostępu)

• zapisywanie do obydwu

• w przypadku awarii odtwarzanie danych z drugiego dysku

• rozwiązanie droższe w stosunku do poprzedniego

RAID 2

• dyski są synchronizowane - metoda dostępu równoległego (każda głowica znajduje się w tej samej pozycji nad każdym dyskiem)

• wszystkie dyski uczestniczą w realizacji każdego żądania we/wy

• wykorzystywane jest paskowanie danych (paski bardzo małe, 1 bajt, 1 słowo)

• kod korekcji błędów jest obliczany na podstawie odpowiednich bitów na każdym dysku

• bity kodu są przechowywane w odpowiednich pozycjach bitowych zlokalizowanych na wielu dyskach parzystości

• zwykle wykorzystywany kod Hamminga

• duża redundancja

  • rozwiązanie drogie

  • nie wykorzystywane

RAID 3

• podobny do RAID 2

• wymaga tylko jednego dysku redundancyjnego, niezależnie od wielkości matrycy dysków

• wykorzystuje się dostęp równoległy

• dane są rozmieszczane w postaci małych dysków

• zamiast kodu korekcyjnego jest obliczany bit parzystości dla zespołu indywidualnych bitów znajdujących się w tej samej pozycji na wszystkich dyskach danych

• w przypadku uszkodzenia dysku wszystkie dane są nadal dostępne w tzw. trybie zredukowanym

• powrót do pełnego działania wymaga wymiany uszkodzonego dysku

• bardzo duże szybkości transferu danych

• wydajność gorsza (w określonym czasie może być realizowane tylko jedno żądanie we/wy)

RAID 4

• metoda dostępu niezależnego (każdy dysk działa niezależnie)

• żądania we/wy mogą być obsługiwane równolegle

• zastosowanie bardziej przydatne tam gdzie wymaga się szybkiej odpowiedzi na żądania we/wy

• mało przydatne w zastosowaniach wymagających dużych szybkości transferu danych

• wykorzystywane paskowanie danych (duże paski)

• pasek parzystości tworzony bit po bicie jest obliczany na podstawie odpowiednich pasków na każdym dysku danych

• bity parzystości są przechowywane w odpowiednim pasku na dysku parzystości

• nie stosowany komercyjnie

RAID 5

• Podobny do RAID 4

• paski parzystości są rozproszone na wszystkich dyskach

• wykorzystuje się schemat cykliczny

• przypadku tablicy n-dyskowej pasek parzystości jest umieszczany na różnych dyskach w odniesieniu do pierwszych n pasków danych

• rozproszenie pasków parzystości na wszystkich napędach zapobiega ewentualnemu występowaniu wąskich gardeł

• powszechnie stosowany w serwerach sieciowych

7. Pamięć podręczna – Cache

Własności systemów pamięciowych

• Położenie

• Pojemność

• Jednostka transferu

• Sposób dostępu

• Wydajność

• Rodzaj fizyczny

• Własności fizyczne

• Organizacja

• Korekcja błędów

Pamięć podręczna

• Pojemność pamięci

• Rodzaj odwzorowywania

• Algorytm wymiany

• Sposób zapisu

• Rozmiar bloku

• Liczba pamięci podręcznych

• Przykłady

Położenie:

• Procesor (rejestry)

• Wewnętrzna (główna)

• Zewnętrzna (pomocnicza, pamięci dyskowe i taśmowe)

Pojemność dla pamięci wewnętrznej wyrażona w bajtach (8 bitów) lub w słowach (8, 16 i 32 bity), a dla pamięci zewnętrznej wyrażona w bajtach.

Jednostka transferu

• pamięć wewnętrzna

  • równa liczbie linii danych doprowadzonych do modułu pamięci i wychodzących z niego (często równa długości słowa)

• pamięć zewnętrzna

  • zwykle są przekazywane w jednostkach o wiele większych niż słowo określanych jako bloki

Sposób dostępu (I)

• Sekwencyjny (pamięci taśmowe)

  • pamięć zorganizowana za pomocą jednostek zwanych rekordami

  • dostęp jest możliwy w określonej sekwencji liniowej

  • czas dostępu do różnych rekordów jest różny

• Bezpośredni (pamięci dyskowe)

  • poszczególne bloki lub rekordy mają unikatowy adres oparty na lokacji fizycznej

  • dostęp jest realizowany przez bezpośredni dostęp do najbliższego otoczenia

  • czas dostępu jest zmienny

Sposób dostępu (II)

• Swobodny (pamięć główna)

  • każda adresowalna lokacja w pamięci ma unikatowy, fizycznie wbudowany mechanizm adresowania

  • czas dostępu nie zależy od sekwencji poprzednich operacji dostępu i jest stały

  • dowolna lokacja może być wybierana swobodnie i jest adresowana i dostępna bezpośrednio

• Skojarzeniowy (pamięć podręczna)

  • rodzaj dostępu swobodnego umożliwiający porównywanie i specyficzne badanie zgodności wybranych bitów wewnątrz słowa

  • słowo jest wyprowadzane na podstawie części swojej zawartości

  • czas dostępu jest stały i niezależny od poprzednich operacji dostępu

Wydajność

• czas dostępu

  • dostęp swobodny - czas niezbędny do zrealizowania operacji odczytu lub zapisu (od chwili doprowadzenia adresu do chwili zmagazynowania lub udostępnienia danych)

  • dostęp nieswobodny - czas potrzebny na umieszczenie mechanizmu odczytu-zapisu w pożądanym miejscu

• czas cyklu pamięci

  • czas dostępu plus dodatkowy czas, który musi upłynąć, zanim będzie mógł nastąpić kolejny dostęp

• szybkość transferu

  • szybkość z jaką dane mogą być wprowadzane do jednostki pamięci lub z niej wyprowadzane

Rodzaj fizyczny

• półprzewodnikowa

• magnetyczna

• optyczna

Własności fizyczne

• ulotna/nieulotna

• wymazywalna/niewymazywalna

Organizacja pamięci

• fizyczne uporządkowanie bitów w celu uformowania słów

Korekcja błędu

• Błąd stały

  • permanentny defekt fizyczny

• Błąd przypadkowy

  • losowe, nieniszczące zjawisko zmieniające zawartość jednej lub wielu komórek pamięciowych bez uszkadzanie samej pamięci

• najprostszy kod korekcyjny - kod Hamminga

Pamięć podręczna (Cache)

• Cel uzyskanie pamięci o takiej szybkości, jaką mają najszybsze osiągalne pamięci, z jednoczesnym uzyskaniem dużego rozmiaru

• ulokowana pomiędzy pamięcią główną a CPU

Działanie

• Cache zawiera kopię części zawartości pamięci głównej

• gdy CPU zamierza odczytać słowo w pamięci, najpierw następuje sprawdzenie, czy słowo to nie znajduje się w Cache

• jeśli tak, to słowo jest dostarczane do CPU

• jeśli nie, to blok pamięci głównej zawierający ustaloną liczbę słów jest wczytywany do Cache

• następnie słowo jest dostarczane do CPU

Rozmiar

• Rozmiar na tyle mały aby ogólny przeciętny koszt na bit zbliżony był do tego kosztu samej pamięci głównej

• Rozmiar na tyle duży, żeby ogólny przeciętny czas dostępu był zbliżony do czasu dostępu samej pamięci podręcznej

• rozmiar optymalny: między 1 K a 512 K słów

Funkcja odwzorowywania

• odwzorowywanie bloków pamięci głównej w wiersze pamięci podręcznej

• typy odwzorowań:

  • bezpośrednie

  • skojarzeniowe

  • sekcyjno-skojarzeniowe

Odwzorowanie bezpośrednie

• każdy blok pamięci głównej odwzorowywany jest na tylko jeden możliwy wiersz pamięci podręcznej

• adres składa się z dwóch części

• mniej znaczące bity w identyfikują słowo lub bajt w bloku pamięci głównej

• bardziej znaczące bity s specyfikują blok pamięci głównej (jeden z 2^s)

• układy logiczne pamięci podręcznej interpretują te s bitów jako znaczniki w postaci s-r bitów (najbardziej znacząca część) oraz pole linii złożone z r bitów (które identyfikuje jeden z m=2^r wierszy pamięci podręcznej)

s-r 8

r 14

w 2

• system pamięci podręcznej jest prezentowany za pomocą adresów 24 bitowych

• 2 bity określające słowo (4 bajtowe bloki)

• 22 bitowy blok zawiera:

  • znacznik - 8 bitów (=22-14) - jeżeli jest zgodny ze znacznikiem aktualnie przechowywanym w tym wierszu to 2-bitowy numer słowa służy do wyboru jednego z 4 bajtów w tym wierszu, w przeciwnym razie 22-bitowe pole obejmujące znacznik i wiersz jest wykorzystywane do pobrania bloku z pamięci głównej

  • 14-bitowy numer wiersza jest wykorzystywany jako indeks dostępu do określonego wiersza w Cache

• żadne 2 bloki odwzorowywane w tym samym wierszu nie mają takiego samego znacznika

Zalety:

• proste i tanie przy wdrażaniu

Wady:

• dla danego bloku istnieje stała lokalizacja w pamięci podręcznej

• jeżeli program będzie się często odwoływał do słów z dwóch różnych bloków przypisanych do tego samego wiersza, to bloki te będą ciągle przenoszone do pamięci podręcznej, co obniży ogólną szybkość

Odwzorowywanie skojarzeniowe

• eliminuje wady odwzorowywania bezpośredniego umożliwiając ładowanie każdego bloku pamięci głównej do dowolnego wiersza pamięci podręcznej

• sterujące układy logiczne pamięci podręcznej interpretują adres pamięci jako znacznik i pole słowa

• pole znacznika jednoznacznie określa blok pamięci głównej

• w celu stwierdzenia, czy blok znajduje się w pamięci podręcznej, sterujące układy logiczne pamięci podręcznej muszą jednocześnie zbadać zgodność znacznika każdego wiersza

• wada: złożone układy wymagane do równoległego badania znaczników wszystkich wierszy pamięci podręcznej

• adres pamięci głównej składa się z 22-bitowego znacznika i 2-bitowego numeru bajtu

• 22-bitowy znacznik musi być przechowywany razem z 32-bitowym blokiem danych

• porównywane są znaczniki w celu wybrania bloku do zastąpienia

• mniej znaczące 2-bity adresu identyfikują które 16-bitowe słowo jest wymagane z 32-bitowego bloku danych

Odwzorowywanie sekcyjno – skojarzeniowe

• Cache jest dzielona na v sekcji, z których każda składa się z k wierszy

• blok Bi może być odwzorowywany na dowolny wiersz sekcji i

• sterujące układy logiczne pamięci podręcznej interpretują adres pamięci jako 3 pola:

  • znacznik 9

  • sekcja 13

  • słowo 2

• 13-bitowy numer sekcji identyfikuje jednoznacznie określoną sekcjęzłożoną z 2 wierszy wewnątrz pamięci skojarzeniowej

• określa się numer bloku w pamięci głównej - modulo 2^13- co umożliwia odwzorowanie bloków na wierszach

• numer sekcji wykorzystywany jest do określenia, która sekcja ma być badana

• sprawdzana jest zgodność obu wierszy sekcji z numerem znacznika adresu, do którego chcemy uzyskać dostęp

Algorytmy zastępowania –odwzorowanie bezpośrednie

• gdy do pamięci podręcznej wprowadzany jest nowy blok, jeden z istniejących bloków musi być zastąpiony

• wybór nie jest możliwy

• istnieje tylko jeden możliwy wiersz dla każdego określonego bloku

Algorytmy zastępowania – odwzorowanie skojarzeniowe i sekcyjno-skojarzeniowe

• aby uzyskać dużą szybkość, algorytm musi być wbudowany w postaci sprzętowej

• LRU (Least Recently Used) - najmniej ostatnio używany

  • zastąp ten blok w sekcji, który pozostawał w pamięci podręcznej najdłużej bez odwoływania się do niego

  • w przypadku dwudrożnego odwzorowywania sekcyjno-skojarzeniowego każdy wiersz zawiera bit wykorzystania (USE)

• FIFO (First In First Out) - pierwszy wchodzi - pierwszy wychodzi

  • zastąpienie tego bloku w sekcji, który najdłużej pozostawał w pamięci podręcznej (metoda cyklicznego buforowania)

• LFU (Least Frequently Used) - najrzadziej używany

  • zastępowany jest ten blok w sekcji, którego dotyczyło najmniej odniesień (skojarzenie licznika z wierszem)

• Random – przypadkowy

Sposób zapisu

• zanim blok pozostający w pamięci podręcznej będzie mógł być zastąpiony, konieczne jest rozważenie, czy musi on być zmieniony w pamięci podręcznej, a nie w pamięci głównej

  • nie musi - stary blok w pamięci podręcznej może być nadpisany

  • musi - na słowie zawartym w tej linii pamięci podręcznej musi być przeprowadzona przynajmniej jedna operacja zapisu, a pamięć główna musi być odpowiednio zaktualizowana

• Problemy:

  • konfiguracje wieloprocesorowe podłączone do tej samej magistrali, posiadające własną pamięć

  • moduł I/O może być zdolny do odczytu/zapisu bezpośrednio w pamięci

Sposób zapisu - zapis jednoczesny

• wszystkie operacje zapisu są prowadzone jednocześnie zarówno do pamięci głównej, jak i do pamięci podręcznej (zapewnia to stałą aktualność danych w pamięci głównej)

• inny procesor może monitorować przesyłanie do pamięci głównej w celu zachowania spójności swej pamięci podręcznej

• wady:

  • generuje ona znaczny przepływ danych do pamięci

  • może powodować występowanie wąskich gardeł

Sposób zapisu - zapis opóźniony

• minimalizuje ilość operacji zapisu do pamięci

• aktualizuje się tylko pamięć podręczną

• gdy następuje aktualizacja, określana jest wartość bitu aktualizacji (UPDATE) skojarzonego z wierszem pamięci podręcznej

• jeżeli następnie blok jest zastępowany, to podlega on wpisaniu do pamięci głównej tylko wtedy, gdy jest ustanowiony bit UPDATE

• wady:

  • część zawartości pamięci głównej jest nieaktualna, przez co dostęp do modułów I/O jest możliwy tylko za pośrednictwem pamięci podręcznej (możliwość powstania wąskich gardeł)

• udział zapisów w operacjach dostępu do pamięci – 15%

Rozmiar bloku

• gdy blok danych jest pobierany i umieszczany w pamięci podręcznej, pobierane jest nie tylko słowo, lecz również pewna liczba sąsiednich słów

  • współczynnik trafień

• użycie większych bloków powoduje zmniejszenie liczby bloków, które mieszczą się w pamięci podręcznej (dane są usuwane niedługo po ich pobraniu)

• gdy blok staje się większy, każde dodatkowe słowo jest dalsze od potrzebnego słowa, staje się mniej prawdopodobne jego użycie w niedalekiej przyszłości

• związek między rozmiarem bloku a współczynnikiem trafień jest złożony i uzależniony od stopnia lokalności programu (od 4 do 8 jednostek adresowalnych)

Zasady projektowania pamięci podręcznych

• Część systemu komputerowego zajmująca się buforowaniem danych powinna charakteryzować się następującymi właściwościami:

  • powinna być jak najbardziej automatyczna

  • jej działanie nie powinno wpływać na semantykę pozostałych części systemu

  • powinna w jak największym stopniu poprawiać wydajność systemu w warunkach rzeczywistej pracy

Temperatura danych

Przy rozpatrywaniu systemu pamięci podręcznej przydatne jest pojęcie "temperatury" - czyli prawdopodobieństwa, że w najbliższym czasie wpłynie żądanie dostępu do tego obiektu (jeśli obiekt jest duży, temperatura poszczególnych części może się różnić). Jest oczywiste, że powinniśmy w szybkiej pamięci trzyma obiekty o możliwie wysokiej temperaturze. Jednak temperatura obiektu nie jest znana i musimy jakoś ją oszacować. Typowe heurystyki to:

• lokalność czasowa - jeśli obiekt był ostatnio żądany, to jest duże prawdopodobieństwo, że będzie żądany ponownie w najbliższym czasie

• lokalność przestrzenna - jeśli obiekt był ostatnio żądany, to prawdopodobnie będą też żądane obiekty leżące blisko niego. Położenie w wypadku pamięci komputera oznacza zwykle adres maszynowy. W przypadku plików na stronie internetowej, pliki linkujące do siebie leżą blisko siebie.

• niektórych typach obiektów wiemy, że ich średnia temperatura jest wyższa niż innych typów - np. temperatura pliku (z grubsza proporcjonalna do liczby ściągnięć) xhtml/html na stronie internetowej jest zazwyczaj wyższa niż temperatura pliku pdf.

Pamięć podręczna procesora (ang. CPU cache)

• pamięć typu SRAM, statyczna o krótkim czasie dostępu;

• zlokalizowana często bezpośrednio w jądrze procesora;

• Pod względem budowy można wyróżnić 3 podstawowe typy organizacji pamięci:

  • pamięć całkowicie skojarzeniowa (ang. fully associative)

  • pamięć z odwzorowaniem bezpośrednim (ang. direct-mapped)

  • pamięć wielodrożna (set-associative)

Pamięć podręczna dysku twardego

• Pamięć podręczna dysku twardego przyspiesza dostęp do bardzo wolnej pamięci masowej (w porównaniu do pamięci RAM, do której dane są pobierane).

• Pamięć podręczna o wielkości od 128 KB do 64 MB jest zazwyczaj podzielony na dwie części: obszar podsystemu odpowiedzialnego za podzielony na dwie części: obszar podsystemu odpowiedzialnego za odczyt z wyprzedzeniem i buforowanie odczytu oraz mniejszy obszar opóźnionego zapisu.

• Dysk z kontrolerem komunikuje się magistralą szybszą niż najszybsze budowane dyski twarde - daje to możliwość przechowania danych w buforze i wysłania do kontrolera bez wykonywania cyklu dostępu do nośnika oraz wpływa pozytywnie na szybkość całego systemu.

Pamięć podręczna systemu plików

Pamięć podręczna przeglądarki

8. Systemy wejścia – wyjścia

Urządzeń wejścia-wyjścia (I/O) nie łączy się bezpośrednio z magistralą systemową. Powodem jest duża różnorodność urządzeń peryferyjnych:

• różne sposoby pracy

• różne prędkości

• różne formaty danych i długości słowa niż komputery

• wszystkie urządzenia są wolniejsze niż CPU i RAM

• potrzebny jest moduł I/O

Dwa podstawowe zadania modułu I/O:

• interfejs z procesorem i z pamięci poprzez magistralę systemową lub centralny przełącznik

• interfejs z jednym lub wieloma urządzeniami peryferyjnymi przez dostosowanie łącza danych

Magistrala systemowa:

• linie adresowe

• linie danych

• linie sterowania

Urządzenia zewnętrzne

• Przeznaczone do odczytywania przez człowieka (monitor, drukarka, klawiatura)

• Przeznaczone do odczytywania przez maszynę (dyski magnetyczne, czujniki, urządzenia wykonawcze wykorzystywane w robotach)

• Komunikacyjne (modem, urządzenia umożliwiające komputerowi wymianę danych z odległymi urządzeniami)

układy logiczne sterowania sterują pracą urządzenia w odpowiedzi na polecenia płynące z modułu I/O

przetwornik dokonuje konwersji danych z postaci elektrycznej na inną formę w przypadku wyjścia, zaś z innych form na elektryczną podczas wejścia

bufor umożliwia czasowe przechowywanie danych przenoszonych miedzy modułem I/O a otoczeniem zewnętrznym

Funkcje modułu I/O

Sterowanie i taktowanie

Sekwencja sterowania transferem danych z urządzenia zewnętrznego do procesora:

1. procesor żąda od modułu I/O sprawdzenia stanu dołączonego urządzenia

2. moduł I/O udziela odpowiedzi o stanie urządzenia

3. jeśli urządzenie działa i jest gotowe do transmitowania, procesor zgłasza zapotrzebowanie na przesłanie danych, posługując się rozkazem do modułu I/O

4. moduł I/O otrzymuje jednostkę danych z urządzenia zewnętrznego

5. dane są przenoszone z modułu I/O do procesora

Komunikacja z procesorem

• Dekodowanie rozkazu wysyłanych w postaci sygnałów na magistrali sterowania

• Przesyłanie danych przez magistralę danych

• Przesyłanie informacji o stanie modułu I/O za pomocą sygnału stanu (zwykle sygnały zajętości i gotowości)

• Rozpoznawanie adresu każdego spośród urządzeń peryferyjnych którym steruje

Komunikacja z urządzeniem

• Rozkazy

• Informacje o stanie

• Dane

Buforowanie danych

Wynika z różnicy szybkości transferu danych z/do pamięci głównej oraz procesora w stosunku do większości urządzeń peryferyjnych

• dane nadchodzące z pamięci głównej są przesyłane do modułu I/O w postaci zwartego pakietu

• następnie są one buforowane w module I/O

• później wysyłane do urządzenia peryferyjnego z szybkością dostosowaną do tego urządzenia

• przy przesyłaniu w przeciwnym kierunku dane są buforowane, żeby nie angażować pamięci w operacje powolnego transferu

Wykrywanie błędów

Błędy:

• mechaniczne i elektryczne

• niezamierzone zmiany wzoru bitowego danych transmitowanych z urządzenia do modułu I/O

Do wykrywania stosuje się:

• kody detekcyjne

• bity parzystości

Sposoby realizacji operacji wejścia-wyjścia

• Programowanie

• Sterowanie przerwami

• Bezpośredni dostęp do pamięci (DMA – Direct Memory Access)

Programowane wejście-wyjście

• CPU wykonuje program, który umożliwia mu bezpośrednie sterowanie operacją I/O

  • rozpoznawanie stanu urządzenia

  • wysyłanie rozkazu odczytu i zapisu

  • transfer danych

• CPU wydając rozkaz modułowi I/O czeka na zakończenie operacji I/O powoduje to stratę czasu procesora

• CPU realizując program napotyka instrukcję odnoszącą się do I/O

• CPU wykonuje tę instrukcję wydając rozkaz odpowiedniemu modułowi I/O

• I/O wykonuje wymagane działanie

• I/O ustawia odpowiednie bity w rejestrze stanu

• CPU okresowo sprawdza stan modułu I/O, czy operacja została zakończona (moduł I/O nie informuje CPU o przebiegu działań i nie przerywa pracy procesora)

Rozkazy wejścia-wyjścia

W celu wykonania instrukcji odnoszącej się do wejścia-wyjścia procesor podaje adres określający moduł I/O i urządzenie zewnętrzne oraz rozkaz wejścia-wyjścia:

• sterowanie - w celu aktywowania (uruchomienia) urządzenia peryferyjnego i przekazania mu, co ma robić

• testowanie - w celu zbadania różnych warunków stanu związanych z modułem I/O i jego urządzeniami peryferyjnymi

• odczyt - do pobrania danych z urządzenia peryferyjnego oraz umieszczenia ich w wewnętrznym buforze (rejestr danych)

• zapis - do pobrania danych (bajta lub słowa) z szyny danych i przekazania ich do urządzenia peryferyjnego

Tryby adresowania

• Odwzorowane w pamięci

  • ta sama przestrzeń adresowa jest przeznaczona dla komórek pamięci i urządzeń wejścia-wyjścia

  • CPU traktuje rejestry stanu i rejestry danych modułów I/O jako komórki pamięci

  • CPU wykorzystuje takie same instrukcje maszynowe w celu uzyskania dostępu zarówno do pamięci, jak i urządzeń I/O

• Izolowane wejście-wyjście

  • przestrzeń adresowa wejścia-wyjścia jest odizolowana od przestrzeni adresowej pamięci

  • wymaga oddzielnych instrukcji dla I/O

Wejście-wyjście sterowane przerwaniami

• Ogranicza czekanie procesora

• Procesor nie potrzebuje sprawdzania urządzenia

• Moduł I/O może przerwać pracę procesora żądaniem obsługi (gdy jest gotów do wymiany danych)

Podstawowe operacje z punktu widzenia modułu I/O

• Moduł I/O otrzymuje od procesora rozkaz CZYTAJ

• Moduł I/O przystępuje do odczytania danych z urządzenia peryferyjnego

• Gdy dane znajdują się już w rejestrze danych modułu, sygnalizuje on procesorowi przerwanie poprzez linię sterowania

• I/O czeka aż CPU zażąda danych

• I/O umieszcza dane na magistrali danych

Podstawowe operacje z punktu widzenia procesora

• CPU wydaje rozkaz CZYTAJ (i przechodzi do innej czynności)

• Na końcu każdego cyklu rozkazu sprawdza, czy nie nastąpiło przerwanie

• Gdy następuje przerwanie ze strony modułu I/O, procesor zachowuje kontekst bieżącego programu i przetwarza przerwanie

• Odczytuje słowo danych z modułu I/O i kieruje je do pamięci

• Odnawia kontekst i wznawia pracę

Problemy projektowania

• W przypadku wielu modułów I/O

  • w jaki sposób procesor określa, które urządzenie wysłało przerwanie

• Jeśli wystąpiło wiele przerwań

  • w jaki sposób procesor decyduje, które z nich ma być przetwarzane

Metody identyfikacji urządzenia

• Wiele linii przerwań - między CPU a modułami I/O

  • wada: mało praktyczne poświęcanie więcej niż kilku linii na linie przerwań

• Odpytywanie za pomocą oprogramowania - gdy CPU wykryje przerwanie przechodzi do procedury obsługi przerwania i odpytuje (za pomocą oddzielnej linii sterowania) każdy moduł I/O

  • wada: czasochłonność

• Odpytywanie za pomocą sprzętu (łańcuchowe, wektorowe)

  • wszystkie modułu I/O są połączone wspólną linią żądania przerwania, linia potwierdzenia przerwania przechodzi łańcuchowo przez moduły

  • gdy CPU wykrywa przerwanie, wysyła potwierdzenie przerwania, które przechodzi przez moduły I/O aż trafi na moduł żądający przerwania, który w celu potwierdzenia umieszcza słowo (określane jako wektor) na liniach danych

• Arbitraż za pomocą magistrali (wektorowy)

  • zanim moduł I/O pobudzi linię zapotrzebowania na przerwanie, musi najpierw przejąć sterowanie magistralą (w danej chwili tylko jeden moduł może pobudzić linię)

  • gdy CPU wykrywa przerwanie, odpowiada posługując się linią potwierdzenia przerwania, moduł I/O umieszcza swój wektor na liniach danych

Przerwania wielokrotne

• Wymienione metody służą do identyfikacji modułu żądającego przerwania, umożliwiają one również przypisywanie priorytetów

  • w przypadku wielu linii CPU wybiera linię przerwania o najwyższym priorytecie

  • przy wykorzystaniu odpytywania za pomocą oprogramowania priorytet wynika z kolejności odpytywania modułów

  • kolejność modułów w łańcuchu określa ich priorytet

Bezpośredni dostęp do pamięci (DMA)

• Programowane I/O i I/O sterowane przerwaniami wymagają aktywnej interwencji CPU przy przesyłaniu danych między pamięcią a modułem I/O, każdy transfer danych musi wędrować przez CPU, więc obie te formy mają wady:

  • szybkość transferu I/O jest ograniczona szybkością, z jaką CPU może testować i obsługiwać urządzenie

  • CPU jest zajęty zarządzaniem przesyłaniem z wejścia i na wyjście

Rozwiązaniem eliminującym ww. wady jest DMA.

• DMA wymaga dodatkowego modułu na magistrali systemowej

• Moduł DMA przejmuje od CPU sterowanie systemem (w operacjach dotyczących I/O)

Szczegóły:

• gdy CPU życzy sobie odczytania lub zapisania bloku danych, wydaje rozkaz modułowi DMA, wysyłając następujące informacje:

  • czy wymagany jest odczyt, czy zapis

  • adres niezbędnego urządzenia I/O

  • adres początkowej komórki pamięci przewidzianej do odczytania lub do zapisania

  • liczbę słów, które mają być odczytane lub zapisane

• CPU następnie kontynuuje inne prace

• DMA przenosi cały blok danych bezpośrednio z/do pamięci, bez przechodzenia przez CPU

• DMA wysyła sygnał przerwania do CPU gdy transfer jest zakończony

Działanie DMA – wykradanie cyklu

• DMA wymaga przejęcia sterowania magistralą

  • w tym celu moduł DMA może używać magistrali tylko wtedy, gdy nie potrzebuje jej CPU lub

  • wymusić czasowe zawieszenie operacji CPU (wykradanie cyklu) - moduł DMA zajmuje cykl magistrali

Konfiguracje modułu DMA

• Pojedyncza magistrala, odłączalne DMA

• Każdy transfer używa dwukrotnie magistrali (dwa cykle)

  • I/O do DMA, później DMA do pamięci

• CPU jest zawieszany dwukrotnie

• Pojedyncza magistrala, zintegrowane DMA-I/O

• DMA może sterować > 1 modułem I/O

  • każdy transfer używa magistrali tylko raz: DMA do pamięci

• CPU jest zawieszany tylko raz

• oddzielna magistrala I/O

• każdy transfer używa magistrali tylko raz: DMA do pamię

• CPU jest zawieszany tylko raz

Kanały I/O

Rozszerzenie koncepcji DMA, może wykonywać rozkazy I/O i w pełni sterować operacjami I/O (procesor o wyspecjalizowanej liście rozkazów dostosowanej do zadań I/O)

Jednostka centralna tylko inicjuje transfer, przekazując kanałowi I/O rozkaz wykonania programu zawartego w pamięci

Rodzaje:

• kanał wybiórczy - steruje wieloma urządzeniami i w określonym czasie zajmuje się transferem danych z jednego spośród tych urządzeń

• kanał multiplekserowy - jednocześnie może współpracować z wieloma urządzeniami I/O

Podsystem wejścia – wyjścia w jądrze

• Planowanie wejścia – wyjścia

  • Określenie porządku wykonywania zbioru zamówień na operacje we/we

  • Ma:

    • Poprawić wydajność systemu

    • Polepszyć wspólne korzystanie z urządzeń przez procesy

    • Zmniejszyć średni czas oczekiwania na zakończenie operacji we/wy

  • Implementuje się przez utrzymanie kolejek zamówień do każdego urządzenia (planiści)

• Buforowanie

  • Konieczność radzenia sobie z dysproporcjami między szybkościami producenta i konsumenta danych (np. modem, wielokrotne buforowanie)

  • Konieczność dopasowania urządzeń o różnych rozmiarach przesyłanych jednostek danych

  • Konieczność zachowania semantyki kopii w/na we/wy aplikacji (np. wersja danych zapisana na dysku będzie wersją z chwili odwołania się przez aplikację do systemu)

• Przechowywanie podręczne

  • Nadzór nad obszarem szybkiej pamięci, w której przechowywane są kopie danych

• Spooling i rezerwowanie urządzeń

  • Użycie bufora do przechowywania danych przeznaczonych dla urządzenia, które nie dopuszcza przeplatania danych w przeznaczonym dla niego strumieniu (np. drukarka)

  • Obsługa spoolingu:

    • Spooling zarządzany przez wątek w jądrze SO

    • Spooling zarządzany przez proces systemowy demona (trwały proces systemowy na przemian pozostający w uśpieniu lub pobudzany do działania przez zdarzenie systemowe)

• Obsługa błędów

  • Przyjmuje się, że systemowe wywołanie we/wy spowoduje zwrotne przekazanie jednego bitu informacji określającej skutek wywołania: sukces lub niepowodzenie (np. w UNIX zmienna errno)

9. Systemy rozproszone

Systemy rozproszone

Co najmniej dwa zasoby, z których co najmniej jeden jest komputerem, połączone siecią, komunikujące się ze sobą i realizujące usługi jako całościowy system.

Uwagi:

• zasoby są względnie autonomiczne (posiadają własne systemy operacyjne, mogą funkcjonować także niezależnie od rozważanego systemu rozproszonego)

• wrażenie całościowego systemu ma istnieć po stronie użytkownika, dla którego fakt rozproszenia zasobów powinien pozostać w jak największym stopniu niewidzialny

• komunikacja odbywa się przez przesyłanie wiadomości

• działanie elementów systemu jest współbieżne

Przykłady systemów rozproszonych

• rozproszony system plików

• rozproszona baza danych

• system obsługi bankomatów

• systemy urządzeń mobilnych

• system GIS

• systemy gridowe

Zalety:

• Oferowanie usług niedostępnych w systemach lokalnych

  • Zwiększenie możliwości użytkowników systemów informatycznych

  • Polepszenie jakości oferowanych usług

• Zwiększenie stopnia wykorzystania sprzętu

• Wydajność

  • możliwa wysoka wydajność bezwzględna

  • bardzo często dobry stosunek wydajności do ceny

• Niezawodność

  • systemy rozproszone mogą tolerować uszkodzenia pojedynczych elementów

• Możliwość stopniowego wzrostu

Problematyka systemów rozproszonych

• Współdzielenie zasobów (z założenia współbieżne)

  • sprzętowych (komputery, sieci, rozmaite urządzenia)

  • programowych (systemy operacyjne, programy w różnych językach)

  • danych (w rozmaitych formatach, na nośnikach różnych typów)

• Rozproszenie zasobów

  • Konieczność niezawodnej komunikacji, często o dużym zasięgu

• Niejednorodność

  • Konieczność wprowadzania warstw pośrednich ujednolicających interfejsy różnych systemów operacyjnych

• Skalowalność

  • możliwość ekonomicznego wzrostu systemu i liczby użytkowników

  • efektywność w sytuacji wzrastającej liczby zasobów i klientów

• Niezawodność działania

  • dostępność – nieprzerwane dostarczanie usług mimo uszkodzeń (konieczność replikacji i nadmiarowości)

  • wykrywanie usterek i ich ”tolerowanie”

• Otwartość

  • zdolność do rozszerzania o nowe usługi, zasoby

  • pomocne oparcie na standardach i publicznych interfejsach

  • przydatne odpowiednie oprogramowanie warstwy pośredniej (middleware)

• Bezpieczeństwo

  • ochrona dostępu do przechowywanych i przesyłanych danych

  • ochrona przed szkodliwymi działaniami

Przezroczystość

• jednolity obraz systemu z punktu widzenia użytkownika

• przezroczystość:

  • dostępu – taki sam z każdego miejsca

  • lokalizacji zasobów

  • migracji zasobów

  • replikacji danych

  • współbieżności – współużytkowania systemu

  • uszkodzeń

  • wydajności – wydajność niezależna od obciążenia

Elementami systemu są zasoby (sprzętowe, programowe i danych).

Sposobami łączenia są mechanizmy (sprzętowe i programowe) wymiany komunikatów pomiędzy elementami.

Funkcjonowanie systemów rozproszonych

Można wyróżnić dwa podstawowe sposoby funkcjonowania systemów rozproszonych: synchroniczne i asynchroniczne:

• Systemy synchroniczne to takie dla których:

  • Lokalny pomiar czasu może odbiegać od rzeczywistego, w określonym, ograniczonym zakresie

  • Określono górne i dolne ograniczenia na:

    • Wykonanie pojedynczego kroku przetwarzania

    • Przesłanie pojedynczego komunikatu

• Systemy nie posiadające ograniczeń czasowych dla powyższych operacji i odstępstw lokalnego pomiaru czasu są systemami asynchronicznymi.

Niezawodność systemów rozproszonych

• Niezawodność systemów rozproszonych można określać w kategoriach dostępności (availability) świadczonych przez nie usług (wyrażanej w procentach czasu)

  • System powinien móc świadczyć dalej usługi w przypadku usterki (awarii elementów):

    • efektywność świadczenia usług może ulec zmniejszeniu

    • nie może dojść do utraty lub niespójności danych

• W celu zagwarantowania dostępności usług

  • Zasoby krytyczne (także zasoby danych), których awarie powodowałyby awarię całego systemu powinny być powielane i móc być zastępowane lub rekonstruowane

• Konieczność zarządzania powielanymi zasobami zwiększa złożoność i zmniejsza wydajność systemu

• Niezawodny system musi posiadać możliwość diagnozowania własnych usterek i podejmowania odpowiednich działań. Działania takie obejmują:

  • Maskowanie usterek (uszkodzeń)

    • całkowite ukrycie usterki, kontynuacje dalszej pracy

    • zgłoszenie jednego z dopuszczalnych wadliwych zachowań systemu

  • chwilowe lub całkowite przerwanie funkcjonowania

• w przypadku niemożności ukrycia usterki system powinien zawieść w przyjazny sposób (fail gracefully) tzn. sposób przewidywalny i ściśle określony oraz nieprowadzący do utraty lub niespójności danych

Wydajność systemów rozproszonych

• Wydajność pojedynczych zasobów

• Wydajność łączy komunikacyjnych

• Skalowalność

• Równoważenie obciążenia

• Wpływ mechanizmów bezpieczeństwa i niezawodności na wydajność

Struktury systemów rozproszonych

• Sieciowe systemy operacyjne

• Rozproszone systemy operacyjne

• Usługi zdalne

• Odporność

• Zagadnienia projektowe

Sieciowe systemy operacyjne

Tworzy środowisko w którym użytkownicy - świadomi wielkości maszyn – mają dostęp do zasobów zdalnych poprzez:

• zdalną rejestrację

  • telnet ... (hasło + nazwa)

• przesyłanie odległych plików

  • ftp ...

    • położenie pliku nie jest przezroczyste dla użytkownika, który musi wiedzieć , gdzie dany plik się znajduje

    • nie ma dzielenia plików, użytkownik może tylko skopiować plik, może istnieć wiele kopii tego pliku (marnowanie miejsca, dane mogą być niespójne

• oba ww. mechanizmy wymagają od użytkownika zachowania wzorca zachowań (polecenia ftp, polecenia zdalnego systemu)

• celem projektowania rozproszonych systemów operacyjnych jest łagodzenie tego problemu

Rozproszone systemy operacyjne

• Użytkownicy nie są świadomi maszyn, dostęp do zasobów zdalnych uzyskują w taki sam sposób jak do zasobów lokalnych.

• wędrówka danych (w celu przesłania danych):

  • przesłanie całego pliku

    • po tej operacji wszystkie dostępy do pliku są lokalne,

    • po zakończeniu dostępu di pliku cała kopia pliku przesyłana jest z powrotem

    • metoda mało wydajna, system Andrew

  • przesłanie tylko tej porcji pliku, która jest niezbędna do natychmiastowego działania, itd. Zmienione części plików muszą być z powrotem przesłane

    • NFS (Network File System) firmy Sun Microsystems (teraz Oracle)

    • SMB firmy Microsoft

• wędrówka obliczeń, w pewnych warunkach wygodniejsze jest przesłanie obliczeń zamiast danych, przykłady:

  • proces P powinien mieć dostęp do pliku na stanowisku A, dostęp do pliku realizuje się na stanowisku A ale można go zainicjować za pomocą wywołania procedury zdalnej (RPC - remote procedure call), w realizacji wywołania używa się protokołu datagramowego UDP w celu wykonania podprogramu w zdalnym systemie, proces P wywołuje przygotowaną wcześniej procedurę na stanowisku A, która przekazuje wyniki procesowi P

  • proces P wysyła komunikat do stanowiska A, system operacyjny na stanowisku A tworzy nowy proces Q, który ma wykonać wyznaczone zadanie i po zakończeniu wysłać oczekiwane wyniki do procesu P za pomocą systemu komunikatów (procesy wykonują się współbieżnie na wielu stanowiskach)

• wędrówka procesów – logiczne rozszerzenie wędrówki obliczeń, korzystniejsze może się okazać wykonanie całego procesu lub jego części na innych stanowiskach ze względu na:

  • równoważenie obciążeń - procesy (podprocesy) można rozmieszczać w sieci w celu wyrównywania obciążeń poszczególnych stanowisk

  • przyspieszenie obliczeń - jeśli pojedynczy proces daje się podzielić na pewną liczbę podprocesów, to mogą one być wykonywane współbieżnie na różnych stanowiskach, łączny czas wykonania całego procesu ulega skróceniu

  • preferencje sprzętowe - proces może odznaczać się pewnymi cechami, które predysponują go do wykonania na wyspecjalizowanym procesorze

  • preferencje programowe - do wykonania procesu może być potrzebne oprogramowanie osiągalne tylko na określonym stanowisku

  • dostęp do danych - zdalne wykonanie procesu może okazać się bardziej opłacalne niż przenoszenie wszystkich danych do macierzystego komputera procesu

• dwie uzupełniające się techniki:

  • system ukrywa fakt, że proces „wyemigrował” od klienta, użytkownik nie musi w swoim programie jawnie kodować przemieszczania procesu

  • użytkownik jawnie określa jaki proces ma być przemieszczany

Usługi zdalne

• użytkownik potrzebuje dostępu do danych umieszczonych na innym stanowisku, zamówienie to będzie obsłużone przez zdalny serwer na stanowisku A, który uzyska dostęp do danych, dokona obliczeń i prześle je użytkownikowi

• jednym ze sposobów organizacji tego przesłania jest metoda usługi zdalnej (remote service)

• RPC (remote procedure call) zdalne wywołanie procedury jest najpopularniejszą formą usługi zdalnej

• usługi zdalne są udostępniane na zasadzie wymiany komunikatów, komunikaty mają ściśle określoną budowę, są adresowane do demona RPC prowadzącego nasłuch portu RPC w odległym systemie i zawierają identyfikator funkcji do wykonania oraz parametry, które należy przekazać, funkcja ta zostanie wykonana a wyniki będą odesłane do zamawiającego o oddzielnym komunikacie

• port jest numerem umieszczonym na początku pakietu z komunikatem, system może udostępniać wiele portów aby rozróżnić swoje liczne usługi sieciowe

• schemat zdalnych wywołań przydaje się do realizowania rozproszonego systemu plików

Wątki

• wątki wykorzystywane są do wysyłania i przyjmowania komunikatów w sposób umożliwiający asynchroniczne wykonywanie innych operacji w zadaniu, możliwe jest skonstruowanie demona, którego liczne wątki mogą czekać na komunikaty z zamówieniami i pobierać po jednym komunikacie w celu przetworzenia go współbieżnie z innymi wątkami wykonującymi te same czynności

• metoda odbioru niejawnego - wykorzystano fakt, że kontekst wątku serwera, który blokuje się w oczekiwaniu na nowe zamówienie, zawiera niewiele istotnych informacji, wątek znika po zakończeniu zadania. Aby obsłużyć nadchodzące zamówienie jądro tworzy nowy wątek (wpisuje również komunikat w przestrzeń adresową serwera i tworzy stos aby nowy wątek miał dostęp do komunikatu. Wątek utworzony na zasadzie „według potrzeb” jako odpowiedź na nowe zdalne wywołanie procedury nazywa się wątkiem wyskakującym.

Odporność

System rozproszony jest podatny na rozmaite rodzaje uszkodzeń (awarie łączy, stanowisk, utrata komunikatów). Należy wykrywać każde z tych uszkodzeń, zmieniać konfigurację systemu w sposób umożliwiający jego dalszą pracę oraz przywracać stanowiska do systemu po ich naprawie:

• Wykrywanie uszkodzeń:

  • procedura uzgadniania - w stałych odstępach czasu oba stanowiska wysyłają sobie wzajemnie komunikaty („jestem-czynne”, „czy-jesteś-czynne?”)

    • trudno rozstrzygnąć, co wystąpiło naprawdę (stanowisko nie działa, bezpośrednie łącze jest zepsute, alternatywna droga jest nieczynna, komunikat uległ zagubieniu)

• Rekonfigurowanie (należy uruchomić procedurę rekonfiguracji systemu)

  • jeżeli uszkodzeniu uległo bezpośrednie połączenie między stanowiskami należy ogłosić to wszystkim stanowiskom aby można było zaktualizować tablice tras)

  • jeżeli awarii uległo stanowisko wszystkie stanowiska muszą być o tym powiadomione

• Usuwanie skutków awarii - j.w. należy wszystkich powiadomić

Rozproszone systemy plików

• rozproszony system plików (DFS - Distributed file system) – rozproszona implementacja klasycznego modelu systemu plików z podziałem czasu, w którym wielu użytkowników dzieli pliki i zasoby pamięci

• zadaniem DFS jest umożliwienie tego samego rodzaju dzielenie zasobów w warunkach fizycznego rozmieszczenia plików na różnych stanowiskach systemu rozproszonego

• system rozproszony - zbiór luźno powiązanych maszyn (zarówno komputery główne jak i stacje robocze), połączonych za pomocą sieci komputerowej

• w odniesieniu do konkretnej maszyny w systemie rozproszonym reszta maszyn i należące do nich zasoby są zdalne, podczas gdy własne zasoby danej maszyny są lokalne

Struktura DFS

• Wprowadzamy następujące terminy:

  • usługa (service) – jednostka oprogramowania działająca na jednej lub wielu maszynach, wypełniająca dla nieznanego uprzednio klienta funkcję konkretnego typu

  • serwer (server) – oprogramowanie usługowe wykonywane na jednej maszynie

  • klient (client) – proces, który zamawia usługę za pomocą zbioru operacji tworzących interfejs klienta (niekiedy definiuje się interfejs niskiego poziomu do rzeczywistej współpracy między maszynami - tzw. interfejs międzymaszynowy)

• system plików dostarcza klientom usług plikowych

• interfejs klienta służący do korzystania z pliku tworzy się za pomocą elementarnych operacji plikowych (tworzenie pliku, usuwanie pliku, czytanie pliku i pisanie do pliku)

• elementarną składową sprzętową nadzorowaną przez serwer plików jest zbiór lokalnych urządzeń pamięci pomocniczej na których pliki są przechowywane i z których odzyskuje się je stosownie do potrzeb klienta.

• idealny rozproszony system plików powinien wydawać się swoim klientom zwykłym, scentralizowanym systemem plików

• mnogość i rozproszenie jego serwerów i urządzeń pamięci powinny być przezroczyste (w interfejsie klienta rozproszonego systemu plików nie powinno dać się odróżnić plików lokalnych od zdalnych

• lokalizowanie plików i organizowanie transportu danych powinno należeć do rozproszonego systemu plików, przezroczysty rozproszony system plików ułatwia użytkownikowi zmianę miejsca, przenosząc jego środowisko (osobisty katalog użytkownika) tam gdzie użytkownik rejestruje się w systemie.

• najważniejszą miarą wydajności DFS jest czas potrzebny do spełnienia rozmaitych zamówień na usługi:

  • czas dostępu do dysku + mała porcja czasu procesora (systemy konwencjonalne)

  • plus dodatkowy koszt charakterystyczny dla struktury rozproszonej obejmujący:

    • czas potrzebny na dostarczenie zamówienia do serwera

    • czas przesłania klientowi odpowiedzi przez sieć

    • w każdym kierunku dochodzi do rzeczywistego przesyłania informacji dochodzi jeszcze czas zużywany przez procesor na wykonanie zaprogramowanego protokołu komunikacji

• wydajność DFS powinna być porównywalna z działaniem zwykłego systemu plików

Nazewnictwo i przezroczystość

• nazywanie – odwzorowywanie między obiektami logicznymi a fizycznymi (użytkownicy mają do czynienia z logicznymi obiektami danych reprezentowanymi przez nazwy plików, system manipuluje fizycznymi blokami danych przechowywanymi na ściekach dyskowych

  • to wielopoziomowe odwzorowywanie tworzy dla użytkowników abstrakcję pliku, która ukrywa szczegóły związane z tym, jak i gdzie plik jest rzeczywiście przechowywany na dysku

• w przezroczystym DFS abstrakcja pliku otrzymuje nowy wymiar - jest nim ukrywanie miejsca przechowywania pliku w sieci

  • w zwykłym systemie plików dziedziną odwzorowywania nazw są adresy na dysku, w DFS dziedzina ta poszerzona jest o specyfikację maszyny, na której dysku dany plik jest przechowywany

• jeszcze jeden krok dalej w traktowaniu plików jako abstrakcji prowadzi do zwielokrotnienia pliku (do danej nazwy pliku wartością odwzorowania jest zbiór umiejscowień kopii tego pliku)

Struktury nazewnicze

• istnieją dwa powiązane ze sobą pojęcia dotyczące odwzorowywania nazw w DFS, które należy rozróżniać:

  • przezroczystość położenia – nazwa pliku nie daje jakiejkolwiek wskazówki odnośnie do fizycznego miejsca przechowywania pliku

  • niezależność położenia – nazwy pliku nie trzeba zmieniać, gdy plik zmienia swoje fizyczne umiejscowienie

• istnieje kilka aspektów różnicujących pojęcia niezależności położenia i statycznej przezroczystości położenia plików:

  • rozdział danych od ich umiejscowienia – przejawiający się w niezależności położenia pliku - polepsza abstrakcyjność plików. Nazwa pliku powinna określać najistotniejsze atrybuty pliku, do których należy jego zawartość, lecz nie położenie. Pliki niezalenie od położenia można traktować jako logiczne pojemniki danych, nie związane z żadnym szczególnym miejscem w pamięci. Jeśli istnieje tylko statyczna przezroczystość położenia, to nazwa pliku nieustannie określa specyficzny, choć ukryty, zbiór fizycznych bloków dyskowych

  • dzięki statycznej przezroczystości położenia plików użytkownicy mogą wygodnie realizować dzielenie danych. Mogą oni wspólnie korzystać ze zdalnych plików po prostu przez nazywanie ich w konwencji przezroczystej wobec ich położenia, tak jak w odniesieniu do plików lokalnych. Niemniej jednak takie dzielenie przestrzeni pamięci jest uciążliwe, gdyż nazwy logiczne są wciąż statycznie powiązane z fizycznymi urządzeniami pamięci. Niezależność położenia pozwala zarówno na dzielenie obszaru samej pamięci, jak i dzielenie obiektów danych. Jeśli pliki są mobilne, to przestrzeń pamięci całego systemu wygląda jak jeden zasób wirtualny. Potencjalną korzyścią takiego ujęcia jest możliwość równoważenia wykorzystania dysków w obrębie systemu

  • niezależność położenia oddziela hierarchię nazewniczą od hierarchii urządzeń pamięci oraz od struktury międzykomputerowej.

Schematy nazewnicze - 3 główne podejścia

• pliki są nazywane za pomocą pewnych kombinacji nazw ich stacji macierzystych i nazw lokalnych, co gwarantuje jednoznaczność nazw w obrębie całego systemu, to podejście nie jest ani przezroczyste ani niezależne od położenia

• NFS (Network File System) - wchodzi w skład pakietu sieciowego ONC+ (dostarczanego przez wielu dostawców systemu UNIX) - oferuje środki do przyłączania katalogów zdalnych do katalogów lokalnych, co daje wrażenie spójnego drzewa katalogów

• jedna globalna struktura nazw obejmuje wszystkie pliki w systemie, w idealnej sytuacji struktura połączonych systemów plików powinna być izomorficzna ze strukturą zwykłego systemu plików, jednak w praktyce istnieje wiele specjalnych plików (np. pliki urządzeń w systemie UNIX)

Zdalny dostęp do plików

• użytkownik zgłasza chęć korzystania ze zdalnego pliku, aby spełnić oczekiwania użytkownika na zdalny dostęp do danych trzeba będzie spowodować rzeczywiste przesłanie danych. Jednym ze sposobów umożliwiających to przesłanie jest metoda obsługi zdalnej

  • zamówienia na dostępy kierowane są do serwera

  • maszyna serwera wykonuje odpowiednie operacje a ich wyniki są przekazywane do użytkownika

  • najpopularniejszym sposób implementowania obsługi zdalnej jest schemat zdalnego wywołania procedury (RPC)

  • aby zapewnić zadowalające działanie systemu obsługi zdalnej można zastosować odmianę przechowywania podręcznego (aby zmniejszyć liczbę dyskowych operacji we/wy jak również ruch w sieci)

Podstawowy schemat przechowywania podręcznego – idea

• Jeśli danych potrzebnych do wykonania zamówienia nie ma jeszcze w pamięci podręcznej, to ich kopię przenosi się z serwera do systemu klienta, dostępy wykonuje się na kopii przechowywanej w pamięci podręcznej (pozostawia się ostatnio używany blok w pamięci podręcznej aby powtórny dostęp mógł odbyć się lokalnie – bez dodatkowego ruchu w sieci (np. LRU - usuwanie danych najdawniej używanych)

• problem spójności pamięci podręcznej - zapewnienie zgodności kopii przechowywanych podręcznie z plikiem głównym (można to nazwać sieciową pamięcią wirtualną)

Umiejscowienie pamięci podręcznej

• Zalety dyskowych pamięci podręcznych:

  • bardziej niezawodne

  • podczas usuwania skutków awarii dane przechowywane podręcznie na dysku pozostają tam podczas usuwania skutków awarii i nie trzeba ich sprowadzać ponownie

• Zalety pamięci podręcznych organizowanych w pamięci głównej:

  • można korzystać z bezdyskowych stacji roboczych

  • dostęp do danych jest szybszy

  • coraz większe i tańsze pamięci operacyjne

  • pamięci podręczne serwerów będą organizowane w pamięci głównej niezależnie od tego, gdzie znajdują się pamięci podręczne użytkownika (umieszczenie pamięci podręcznej w pamięci głównej również w przypadku maszyny użytkownika pozwala zbudować jeden mechanizm przechowywania podręcznego, dla serwera i użytkownika

Polityka uaktualniania

• Czyli odsyłanie zmienionych bloków danych z powrotem do głównej kopii pliku na serwerze

• Przepisywalność (Write-through) – przepisywanie danych na dysk zaraz po tym, gdy znajdą się w dowolnej pamięci podręcznej

  • zaleta – niezawodność

  • wada - przy każdym zapisie oczekiwanie na przesłanie danych do serwera, co powoduje słabą wydajność operacji pisania

• Opóźniane pisanie (Delayed-write) – opóźnianie aktualizowania kopii głównej, zmiany są wprowadzane do pamięci podręcznej a do serwera przepisywane w późniejszym czasie, zalety:

  • dostęp do pisania trwa znacznie krócej

  • dane mogą być ponownie zmienione zanim zostaną przepisane z powrotem (unika się zbędnego zapisywania ich poprzednich wersji)

  • wada - pogorszenie

Odmiany polityki opóźnionego pisania:

• przeglądanie pamięci podręcznej w regularnych odstępach czasu i wysyłanie z niej bloków zmienionych po ostatnim przeglądaniu

  • system SPRITE - polityka z odstępami 30-sekundowymi

• zapisywanie danych z powrotem w serwerze dopiero w chwili zamykania pliku (pisanie przy zamykaniu)

  • system ANDREW

Spójność

• Maszyna klienta musi sprawdzać, czy kopia danych przechowywana w lokalnej pamięci podręcznej jest spójna z kopią główną

• podejście polegające na inicjatywie klienta

  • klient inicjuje sprawdzenia ważności danych, kontaktując się z serwerem i sprawdzając, czy dane lokalne są spójne z kopią główną

  • jaka częstość sprawdzania: waha się pomiędzy sprawdzaniem przy każdym dostępie a sprawdzaniem tylko przy pierwszym dostępie do pliku (lub stałe odstępy czasu)

• podejście polegające na inicjatywie serwera

  • serwer rejestruje, dla każdego klienta z osobna, pliki które wysyła do pamięci podręcznej

  • gdy wykryje niespójność musi zareagować (gdy np. plik jest użytkowany w pamięciach podręcznych dwu klientów)

Porównanie przechowywania podręcznego i obsługi zdalnej

• znaczna liczba dostępów zdalnych może być skutecznie obsłużona za pomocą lokalnej pamięci podręcznej

  • większość dostępów zdalnych jest obsługiwana tak szybko jak dostępy lokalne

  • kontakt z serwerem jest okazjonalny, nie musi następować przy każdym dostępie do danych

  • zmniejsza się obciążenie serwera i ruch w sieci

  • wzrasta potencjalna skalowalność systemu

• całkowity koszt przesyłania siecią dużych porcji danych (przy pamięci podręcznej) jest mniejszy niż przy przesyłaniu serii odpowiedzi na poszczególne zamówienia

• procedury dostępu do dysku serwera mogą być lepiej optymalizowane, jeśli wiadomo, że zamówienia będą zawsze dotyczyć dużych ciągłych segmentów danych a nie losowo wybranych bloków dyskowych

• problem spójności pamięci podręcznej jest główną wadą przechowywania podręcznego

• aby przechowywanie podręczne przynosiło korzyść, działania powinny przebiegać w maszynach wyposażonych w lokalne dyski i duże pamięci operacyjne

Skończyłem tutaj, bo przypomniałem sobie, że nie pamiętam, do którego momentu robiliśmy i które kwestie możemy pominąć.