lastscan11 (9)

Udostępnienie informacji w celu jej użycia może być realizowane jako

•    pobranie wymuszone

•    pobranie antycypowane

Pobranie wymuszone jest skutkiem błędu braku obiektu, strony lub segmentu Pobranie antycypowane natomiast jest realizowane na podstawie prognozy zapotrzebowania procesu na dane. Realizacja pobrania antycypowanego w przypadku segmentacji jest bardzo trudna z uwagi na małą lokalność przestrzenną co jest wynikiem tego iż segmenty są niezależnymi jednostkami logicznymi.

Strategie przydziału pamięci w stronicowaniu nic są trudne z uwagi na stały rozmiar strony Konieczna jest tylko identyfikacja wolnych stron, a po wypełnieniu obszar wolny zawsze stanowi całkowita liczba stron Jedynym problemem jest wewnętrzna fragmentacja.

W pamięci segmentowej na skutek różnych rozmiarów segmentów tworzą się nieciągłości, obszary które nic mogą być przydzielone segmentom bo ich rozmiar nie jest wystarczająco duży Obszary takie nazywamy dziurami Strategia przydziału powinna minimalizować rozmiar dziur W tym celu tworzona zostaje list dziur, po wypełnieniu pamięci lista dziur jest aktualizowana poprzez usunięcie ż listy dziury użytej a dopisanie do listy dziur dziury powstałej wskutek wypełnienia Najczęściej stosowane metody przydziału pamięci segmentowanej to,

BF - Best Fit - najlepsze wpasowanie polegające na umieszczeniu segmentu w pierwszej dziurze o wystarczającym rozmiarze, lista dziur jest uporządkowana według rosnących rozmiarów dziur a kolejność adresów na liście jest przypadkowa.

WF - Worst Fit - najgorsze wpasowanie polegające na umieszczeniu segmentu w pierwszej dziurze O wystarczającym rozmiarze, lista jest tworzona według malejących rozmiarów dziur a kolejność adresów na liście jest przypadkowa

FF - First Fit ~ pierwsze wpasowanie polegające na uporządkowaniu listy według rosnących adresów a segment jest umieszczany w pierwszej dziurze z listy o wystarczającym rozmiarze, przeszukiwanie może być wznawialne do miejsca zakończenia poprzedniego przeszukiwania lub zawsze od początku

BB - Binary Buddy - wpasowanie binarne polegające na tworzeniu listy dziur o rozmiarach |2^f",    a wpasowanie segmentu następuje metodą FF w- obrębie listy odpowiadającej

rozmiarowi segmentu zaokrąglonemu w górę do całkowitej potęgi dwójki 2\ kolejność adresów na listach jest liniowa

Strategia BF wydaje się być najlepsza lecz należy zwrócić uwagę, iż w krótkim czasie w pamięci powstaje duża ilość małych dziur. Strategia WF jest statystycznie równoważna strategii BF. Wadą strategii FF jest kumulacja dziur o małym rozmiarze na początku listy co wydłuża procedurę poszukiwania. Prostym sposobem uniknięcia tej wady jest przeszukiwanie listy od miejsca w którym skończono ostatnie poszukiwanie. Nieuchronną koniecznością stosowania tych strategii jest defragmentyzacja (scalanie) pamięci co jakiś czas Jeśli w ocenie strategii za kryterium oceny przyjmiemy łatwość defragmentyzacji to zauważymy że w strategiach BF WF komasację dziur utrudnia lxak uporządkowania adresów dziur Bardziej podatne na komasację są strategie FF i BB w których lista dziur jest uporządkowana względem rosnących adresów.

W systemie wieioprocesowym jednemu procesowi jest przydzielana tylko część dostępnej w systemie pamięci. Ponieważ rozmiar ten jest ograniczony to po pewnym czasie nastąpi intensyfikacja błędu braku bloku którego następstwem będzie wymiana. Czynnikiem wpływającym na efektywność wymian są strategie przydziału obszaru pamięci procesom. Partycja stała oznacza że rozmiar przydzielonej procesowi pamięci jest stały w czasie życia procesu. Partycja zmienna oznacza, że rozmiar pamięci przydzielonej procesowi może ulegać zmianie w czasie życia procesu Zaletą partycji stałej jest łatwa implementacja, lecz jeżeli procesy przejawiają zmienność lokalności czasowej i przestrzennej, to jest ona nieefektywna. Partycje zmienne są bardziej elastyczne, lecz znacznie trudnej jest je zaimplementować. Umożliwiają one także relokowanie części pamięci przydzielonej innemu procesowi

Partycje stale są sprzeczne z koncepcją pamięci segmentowanej gdzie rozmiar segmentu może być dowolny i trudno sobie wyobrazić sztywny przydział pamięci procesowi, tym bardziej, że zwykle dopuszczalny jest rozmiar segmentu równy całkowitej przestrzeni adresowej procesora Należy zauważyć, że problem tai nie istnieje w segmentacji stronicowanej gdzie nie ma konieczności odwzorowywania w pamięci wszystkich stron segmentu Oczywiste jest natomiast stosowanie stałych partycji przy pamięci stronicowanej gdzie jednostką wymiany jest strona o ustalonym rozmiarze i jej wymiana nie nastręcza trudności bo bloki wymieniane są tego samego rozmiaru Najczęściej stosowanymi strategiami wymian dla stałych partycji są strategie:

•    Losowa używana wyłącznie w środowiskach gdzie lokalność jest niewielka, np : bazy danych

•    FIFO - First In Firs Out - kolejka bloków do wymiany jest umieszczona zgodnie z kolejnością umieszczania w pamięci, nie uwzględnia się częstości użycia bloków najdawniej alokowany może być najczęściej wykorzystywany

•    F1NUFO - First In Not Used First Out - każda pozycja w kolejce ma dodatkowo znacznik używalności, kolejka przesuwa się cyklicznie początkiem jest wskaźnik ostatnio wymienionego bloku

•    LRU Last Recenilu Used - wymienia 3ię blok najdawniej uźyurany, niezbędny jest znacznik częstości użycia.

Jak łatwo się domyślić najlepszą strategią będzie ta która będzie wymieniać bloki które będą użyte najpóźniej Strategia ta niemożliwa do zaimplementowania z uwagi na konieczność przewidywania który blok będzie użyty najpóźniej, zwana MIN jest używana do szacowania efektywności innych strategii.

Partycja zmienna umożliwia rozszerzenie przydzielonego obszaru pamięci zamiast wymiany bloku Procedury wymian muszą być rozpatrywane osobno, gdyż brak wystarczającej pamięci (w obszarze pamięci przydzielonej procesowi) nie oznacza konieczności wymiany bloku.

Dla partycji zmiennych przy stronicowaniu stosuje się dwie strategie wymiany:    3

•    WS polegającą na wymianie całego zbioru roboczego

•    PFF polegającą na dopasowaniu zbioru roboczego do częstości występowania błędu braku strony. Ustala się wartość progową PFF (Page Fault Frequency) i jeżeli częstość błędu braku strony pff<PFF to wymieniane są wszystkie strony nieużywane od osiami ej wymiany, jeśli zas pfr>PFF to nie dokonywana jest wymiana, lecz zwiększany jest rozmiar partycji (znaczy to bowiem iż przyznany procesowi obszar pamięci jest za mały i następują częste wymiany stron, afcy zmniejszyć ilość błędów braku strony należy więc przydzielić procesowi większą ilość pamięci)

Strategią odniesienia jest strategia VMJN zdefiniowana podobnie jak MIN lecz z uwzględnieniem zmiany rozmiaru partycji.

W segmentacji strategie wymiany są odniesione do częstości użycia segmentów Miaią efektywności strategii jest częstość występowania błędu braku strony (pff) lub błędu braku segmentu

(sfT)

Wykład 8 - Systemy magistral

Na poziomie połączeń wymiennych modułów obowiązuje standard przesyłania sygnałów elektrycznych, zwany magistralą systemową, zapewniający jednolity sposób łączenia modułów (np. VME. Multibus)

Przyłączenie pamięci masowych i urządzeń we/wy za pośrednictwem sterowników realizują magistrale sprzęgu Przykładem takiej magistrali jest SCSI (Smali Computer System Ittterconneci).

Ze względu na realizowane funkcje wyróżnia się

•    magistrale dedykowane.

•    ogólnego przeznaczenia

Magistrale dedykowane wykonują pojedyncze funkcje wymagane do połączenia procesora z elementami systemu, takie jak przesłanie adresu, przesianie poleceń, przesłanie danych pomiędzy pamięcią a procesorem, przesłanie danych do lub z urządzenia peryferyjnego. Ich zaletą jest duża przepustowość a wadami: wysoki łączny koszt wielu specjalizowanych łączy oraz duża podatność na błędy.

Magistrale ogólnego przeznaczenia są używane do wykonywania różnych funkcji i z tego powodu są nazywane również współdzielonymi lub dzielonymi Ze względu na możliwość wystąpienia konfliktu magistrale tego rodzaju wymagają arbitrażu. Ich wadą jest mała przepustowość, a zaletą niski koszt W systemach wieloprocesorowych, w celu poprawienia przepustowości, używa się równolegle kilku magistral dzielonych lub jednej magistrali dzielonej i kilku lokalnych magistral specjalizowanych Zwielokrotnienie magistral ułatwia stosowanie technik tolerowania uszkodzeń (FTC), lecz komplikuje arbitraż 7. uwagi na duży koszt rozwiązania opartego na kilku magistralach współdzielonych w małych systemach są stosowane rozwiązania hybrydowe: magistrala lokalna na poziomie zasobów pojedynczych pojedynczych procesorów oraz dzielona magistrala systemowa do realizacji tiansferów pomiędzy podsystemami

Wśród magistral dzielonych wyróżniamy:

•    magistrale dżiełone grupujące jednolite zasoby systemu,

•    magistrale dzielone grupujące jednolite funkcje systemu

Magistrale pierwszego rodzaju są zorientowane na pojedynczy procesor, który jest domniemanym zarządcą magistrali i odbiorcą przerwań, większość przesłań to przesiania typu CPU -pamięć Typowym sposobem transmisji jest przesłanie pojedynczych danych w krótkim cyklu magistrali. Zapewniają to osobne linie adresowe i danych, brak kontroli danych i prosty protokół transmisji

Magistrale dzielone funkcjonalnie są typowe dla systemów realizujących funkcje częściowo niezależne, np. systemów wieloprocesorowych Zorientowane są one na przesyłanie wiadomości (mes.tił^e), a nie pojedynczych danych. Wiadomość formowana przez inteligentne urządzenie komunikacyjne zawiera blok danych uzupełnionych informacją adresową i statusową, a zwykle również kontrolną, umożliwiającą korekcję błędów Wiadomości są bufotowanc, a żądania dostępu są szeregowane Standardy transmisji są niezależne od rodzaju procesorów, które przesyłają wiadomości. Istotną cechą takich magistral jest więc ich przepustowość

Przesianie po magistrali, zwane transakcją, ma następujące trzy fazy:

•    żądanie dostępu

•    arbitraż

•    przesianie danych

•    detekcja i sygnalizacja błędów

Magistrale nicmultiplcksowanc maia osobne linie adresowe i danych. Wyróżnia się dwa rodzaje transakcji zapis danych, przy którym zarządca magistrali wy syła w tym samym cyklu adres, i z niewielkim opóźnieniem dane: oraz odczyt danych przy którym zarządca magistrali wysyła tylko adres a czas pojawienia się danych zależy od czasu dostępu do urządzenia podrzędnego (rys. 7.1).

W transakcjach blokowych wysterowanie magistrali adresowej podczas transakcji nie zmienia się (urządzenie automatycznie wytwarza kolejne adres)), a w kolejnych cyklach zmienia się automatycznie adresowana informacja na limach danych

Na magistralach mul indeksowanych adres i dane przesyłane są tymi samymi liniami. Wyróżnia się 5 rodzajów transakcji (rys. 7 2):

•    zapis.

•    odczyt,

•    zapis po odczycie i modyfikacji

•    odczyt po zapisie

•    przesianie blokowe

Jeśli czas odczytu jest długi, to może być realizowana transakcja rozdzielona Po zainicjowaniu odczytu, zamiast blokowania magistrali oczekiwaniem na zakończenie transferu, rolę zarządcy magistrali przejmuje urządzenie podrzędne, które po skompletowaniu danych zwrotnie inicjuje ich transfer w trybie zapisu do urządzenia nadrzędnego Odczyt następuje zatem w dwóch rozdzielonych etapach: inicjacja z przesianiem adresu, a polem zapis zwrotny. Ta technika nazywa się przełączaniem komunikatów w odróżnieniu od transakcji nierozdzielonych, które charakteryzują się przełączeniem układów.

Adresowanie obiektów przyłączonych do magistrali

Wyróżnia się dwa rodzaje adresowania adresowanie logiczne i adresowanie geograficzne Adresowanie logiczne oznacza przypisanie płycie lub urządzeniu ustalonego arbitralnie identyfikatora (np ustawienie przełączników) i wymaga dodatkowych układów adresowych. Rozpoznawanie płyty na podstawie fizycznej lokalizacji (numer szczeliny/lącza) nazywa się adresowaniem geograficznym i adres urządzenia składa się z dwóch części: identyfikatora łącza i identyfikatora urządzenia (adresu lokalnego) na płycie Sposób ten umożliwia programową identyfikację urządzeń przez system operacyjny.

Adresowanie może być także zbiorowe, jeśli konieczne jest jednoczesne wykonanie tej samej funkcji. Rozgłaszanie (broadcast) polega na wysyłaniu tej samej informacji jednocześnie do wielu odbiorców. Przykładem może być zerowanie układów (RI-SET) lub aktualizacja pamięci podręcznej kilku procesorów. Wywołanie (broadcalf) ma na celu identyfikację źródła lub źródeł sygnału i polega na jednoczesnym odbiorze informacji z wiciu źródeł W jego wyniku na liniach magistrali forsowany jest stan, odpowiadający sumie lub iloczynowi logicznemu sygnałów. W celu uniknięcia konfliktu danych na magistrali wymaga się specjalnego formowania lub separowania źródeł sygnałów (na przykład każde zgłoszenie jest przypisane do jednej linii danych)

Magistrale

Magistralą nazywamy zestaw połączeń między elementami systemu cyfrowego Struktura magistrali jest zazwyczaj kompromisem wymagań dużej szybkości transferów i niskiej ceny Największą szybkość zapewniają magistrale równolegle, w których ścieżki przesyłania funkcjonalnie niezależnych sygnałów są niezależne, a wszystkie sygnały są przesyłane jednocześnie Najtańsze są magistrale szeregowe, w których poszczególne sygnały są przesyłane sekwencyjnie prze2 pojedynczą linię Magistrale równolegle są stosowane do połączeń elementów komputera, magistrale szeregowe są używane do transmisji między komputerami. Przesyłanie informacji może być synchroniczne (sygnały na poszczególnych liniach pojawiają się w ściśle określonych momentach czasu) lub asynchroniczne (transmisja może się rozpocząć w dowolnej chwili czasu).

Klasyfikacja magistral

Na najniższym poziomie konfiguracji systemu są tworzone magistrale lokalne, służące do połączenia bloków w obrębie płyty Mają one niewielką obciążalność elektryczną i tealizują bezpośrednie połączenia między procesorem 1 modułami systemu

4 Protokół magistrali

Reguła transakcji na danej magistrali nazywa się jej protokołem i obejmuje zatówno sposób przesyłania, jak i relacje czasowe sygnałów sterujących niezbędnych dla poprawnego przebiegu transakcji Typową sekwencję zdarzeń czasowych przedstawia schemat pokazany na rys. 7.3.

Oczekiwanie na ustabilizowanie danych (2) jest skutkiem opóźnienia transferu na magistrali, które mogą powodować: nadajnik linii, bufory pośredniczące lub odbiorniki danych. Aby uniknąć niepoprawnego odczytu danych, nadajnik powinien sygnalizować ustabilizowanie nadawanych danych Ponieważ czas potrzebny na odebranie danych nie jest z góry ustalony, więc niezbędne jest potwierdzenie ich odebrania (5) Dopiero wtedy nadajnik może bezpiecznie usunąć dane z magistrali (7) Aby uniknąć odczytu nieokreślonych danych (śmieci), odbiornik musi zostać powiadomiony, że na magistrali brak jest ważnych danych (8) a w odpowiedzi potwierdzić zakończenie transakcji

Ta sekw encja zdarzeń lub jej część może być realizowana jedną z trzech metod

Michał Jur