Pamięć pomocnicza dr inż. Krzysztof Patan Instytut Sterowania i Systemów Informatycznych Uniwersytet Zielonogórski k.patan@issi.uz.zgora.pl Pamięć pomocnicza 1 WSTP Struktury danych oraz algorytmy do implementacji interfejsu systemu plików " implementacja plików " implementacja katalogów " zarządzanie wolnymi obszarami Struktura pamięci pomocniczej " algorytmy planowania ruchu głowic porządek dyskowych operacji wej-wyj " formatowanie dysku " zarządzanie blokami rozruchowymi, blokami uszkodzonymi " zarządzanie obszarem wymiany " niezawodność dysków Pamięć pomocnicza 2 STRUKTURA DYSKU Napędy dyskowe adresowane są jako wielkie jednowymiarowe tablice bloków logicznych sektory cylinder Scieżki płyta Sektor 0 jest pierwszym sektorem na pierwszej ścieżce pierwszego (zewnętrznego) cylindra Dalsze odwzorowanie odbywa się po kolei wzdłuż tej ścieżki, następnie wzdłuż pozostałych ścieżek cylindra, potem w głąb następnych cylindrów Pamięć pomocnicza 3 PLANOWANIE DOSTPU DO DYSKU Ekonomiczne użytkowanie sprzętu, szybki dostęp do dysku, szybsze przesyłanie danych Na czas dostępu mają wpływ: 1. czas szukania czas potrzebny na przemieszczenie ramienia dysku do pozycji w której głowice ustawiają się w cylindrze zawierającym potrzebny sektor 2. opóznienie obrotowe czas zużywany na obrót dysku do pozycji, w której potrzebny sektor trafia pod głowicę dysku Szerokość pasma łączna liczba przesłanych bajtów, podzielona przez łączny czas jaki upływa od pierwszego zamówienia na usługę dyskową do chwili zakończenia ostatniego przesłania Wykonując operacje dyskowe w odpowiednim porządku można polepszyć zarówno czas dostępu jak i szerokość pasma Pamięć pomocnicza 4 Proces zamawiając operację wej-wyj określa: " czy jest to operacja wejścia czy wyjścia " dyskowy adres przesyłania " adres pamięci operacyjnej dotyczący przesyłania " liczbę bajtów do przesłania Gdy napęd i jego sprzętowy sterownik są gotowe do pracy to zamówienie może zostać spełnione natychmiast Jeśli napęd czy sterownik są zajęte, to każde nowe zamówienie jest ustawiane w kolejce zamówień oczekujących na usługę Problem wyboru zamówienia z kolejki Pamięć pomocnicza 5 Planowanie metodą FCFS " najprostsza metoda dostępu do dysku pierwszy zgłoszony pierwszy obsłużony " algorytm jest sprawiedliwy, lecz nie zapewnia szybkiej obsługi Przykład 1. Rozważmy dyskową kolejkę zamówień na operacje wej-wyj odnoszące się do sektorów w następujących cylindrach: 98, 183, 37, 122, 14, 124, 65 i 67. Zastosować metodę FCFS. Pamięć pomocnicza 6 Bieżące położenie głowicy: cylinder 53 Kolejka: [98,183,37,122,14,124,65,67] cylindry 1 20 60 100 140 180 Planowanie dostępu do dysku metodą FCFS Wady: " Liczba przewiniętych cylindrów = 640 " Gwałtowne wychylenia głowicy 122-14-124 Pamięć pomocnicza 7 Planowanie metodą SSTF " dąży się do tego, aby w pierwszej kolejności obsługiwać zamówienia sąsiadujące z bieżącym położeniem głowicy " metoda SSTF najpierw najkrótszy czas przeszukiwania (ang. shortest seek time first) " wybiera się zamówienie z minimalnym czasem przeszukiwania względem bieżącej pozycji głowicy Przykład 2. Rozważmy dyskową kolejkę zamówień z przykładu 1. Rozplanować dostęp do dysku metodą SSTF. Pamięć pomocnicza 8 Bieżące położenie głowicy: cylinder 53 Kolejka: [98,183,37,122,14,124,65,67] cylindry 1 20 60 100 140 180 Planowanie dostępu do dysku metodą SSTF " Liczba przewiniętych cylindrów = 236 Pamięć pomocnicza 9 Zalety " znaczne polepszenie wydajności 640 = 2, 71 236 Algorytm SSTF jest odmianą planowania metodą najpierw najkrót- sze zadanie (SJF) Wady " metoda może doprowadzić do zagłodzenia niektórych zamówień Algorytm SSTF choć wyraznie poprawia wydajność nie jest jednak algorytmem optymalnym Pamięć pomocnicza 10 Planowanie metodą SCAN " w metodzie SCAN ramię dysku rozpoczyna pracę od jednej krawędzi dysku i przemieszcza się w kierunku krawędzi przeciwległej obsługując zamówienia z kolejki " po dotarciu do krawędzi dysku zmienia się kierunek ruchu głowicy " głowica nieustannie przeszukuje (skanuje) dysk tam i z powrotem Przykład 3. Rozważmy dyskową kolejkę zamówień z przykładu 1. Rozplanować dostęp do dysku metodą SCAN. Pamięć pomocnicza 11 Bieżące położenie głowicy: cylinder 53 Kolejka: [98,183,37,122,14,124,65,67] Kierunek ruchu głowicy ! cylindry 1 20 60 100 140 180 Planowanie dostępu do dysku metodą SCAN " Liczba przewiniętych cylindrów = 234 " Ważny jest kierunek skanowania; jeśli przyjmiemy kierunek przeciwny do rozważanego w przykładzie 3 to liczba przewiniętych cylindrów wzrośnie do 333 Pamięć pomocnicza 12 " Jeśli w kolejce pojawi się zamówienie odnoszące się do cylindra znajdującego się tuż przed głowicą, to zostałoby zrealizowane natychmiast " Jeśli w kolejce pojawi się zamówienie odnoszące się do cylindra znajdującego się tuż za głowicą, to zamówienie to musi poczekać, aż głowica dojdzie do końca, zmieni kierunek i wróci " Algorytm SCAN nazywany jest czasami algorytmem windy winda jedzie do góry i realizuje po kolei wszystkie zamówienia winda jedzie w dół realizując napotkane zamówienia Pamięć pomocnicza 13 Planowanie metodą C-SCAN " zakłada się równomierne rozkład zamówień na cylindry " kiedy głowica osiąga skrajne położenie i zmienia kierunek to w pobliżu głowicy będzie względnie mało zamówień " największe zagęszczenie zamówień będzie dotyczyć przeciwległego końca dysku Pomysł: może przemieścić głowicę w okolice największego zagęszczenia zamó- wień? " algorytm C-SCAN (ang. circular SCAN skanowanie cykliczne) jest odmianą algorytmu SCAN " algorytm działa podobnie jak metoda SCAN z tą różnicą, że po dojściu głowicy do skrajnego położenia wraca ona natychmiast do przeciwległego położenia (bez obsługi zamówień znajdujących się po drodze) Pamięć pomocnicza 14 Przykład 4. Rozplanować kolejkę zamówień z przykładu 1 metodą C-SCAN. Bieżące położenie głowicy: cylinder 53 Kolejka: [98,183,37,122,14,124,65,67] Kierunek ruchu głowicy cylindry 1 20 60 100 140 180 Planowanie dostępu do dysku metodą C-SCAN " liczba przewiniętych cylindrów = 383 " cylindry traktowane są jako lista cykliczna, w której ostatni cylinder spotyka się z pierwszym Pamięć pomocnicza 15 Planowanie metodą LOOK " w metodach SCAN i C-SCAN głowica przemieszcza się z jednego końca dysku do drugiego " prosta modyfikacja tych metod polega na tym, że nie czeka się aż głowica dojdzie do skraju dysku, czeka się aż głowica osiągnie skrajne zamówienie. " po zrealizowaniu skrajnego zamówienia głowica natychmiast wykonuje zwrot kierując się w przeciwnym kierunku " wersje tego algorytmu noszą nazwy odpowiednio LOOK i C-LOOK (metody patrzą czy w danym kierunku są jeszcze jakieś zamówienia) Przykład 5. Rozważmy dyskową kolejkę zamówień z przykładu 1. Rozplanować dostęp do dysku metodami LOOK i C-LOOK. Pamięć pomocnicza 16 Bieżące położenie głowicy: cylinder 53 Bieżące położenie głowicy: cylinder 53 Kolejka: [98,183,37,122,14,124,65,67] Kolejka: [98,183,37,122,14,124,65,67] Kierunek ruchu głowicy ! Kierunek ruchu głowicy cylindry cylindry 1 20 60 100 140 180 1 20 60 100 140 180 Planowanie dostępu do dysku metodą LOOK Planowanie dostępu do dysku metodą C-LOOK Pamięć pomocnicza 17 WYBÓR ALGORYTMU PLANOWANIA Jak wybrać najlepszy algorytm planowania dostępu do dysku spośród wielu dostępnych? metoda SSTF powszechnie stosowana i naturalna metody SCAN i C-SCAN są odpowiedniejsze w systemach z wielką liczbą zamówień na operacje dyskowe wydajność każdego algorytmu planowania zależy od liczby i rodzaju zamówień. Jeżeli kolejka ma jedno nie obsłużone zamówienie wtedy wszystkie algorytmy wygenerują ten sam rezultat. Wszystkie algorytmy sprowadzają się do planowania metodą FCFS Pamięć pomocnicza 18 metody planowania mogą zależeć od metody przydziału pliku " dla pliku o przydziale ciągłym generowany jest ciąg zamówień odnoszących się do sąsiednich miejsc na dysku ograniczony ruch głowicy " dla pliku o przydziale listowym bądz indeksowym generowany jest ciąg zamówień odnoszący się do rozrzuconych miejsc na dysku większy ruch głowic równie ważna jest lokalizacja katalogów i bloków indeksowych; przechowywanie katalogów i bloków indeksowych w pamięci operacyjnej pomaga zmniejszyć ruchy ramienia dysku algorytm planowania dostępu do dysku powinien być napisany jako osobny moduł systemu operacyjnego, który można w razie konieczności podmienić Pamięć pomocnicza 19 Problem opóznienia obrotowego nowoczesne dyski nie ujawniają fizycznego położenia bloków logicznych producenci dysków implementują algorytmy planowania w sterownikach wbudowanych w sprzęt napędu dysków sprzęt realizuje zamówienia przesłane przez system operacyjny w sposób poprawiający zarówno czas szukania i opóznienie obrotowe system operacyjny odpowiada za przekazywanie zamówień na operacje dyskowe system operacyjny posiada własne algorytmy planowania i dawkuje sterownikowi dysku zamówienia, zaś dysk realizuje je tak, aby opóznienie obrotowe było jak najmniejsze Pamięć pomocnicza 20 ZARZDZANIE DYSKIEM Oprócz planowania dostępu do dysku, system operacyjny odpowiada także za: przygotowanie dysku do pracy rozruch systemu postępowanie blokami błędnymi Formatowanie dysku " nowy dysk twardy nie zapisana tablica krążki z materiału magnetycznego " formatowanie niskiego poziomu (ang. low level formatting) Podział dysku na sektory, które sterownik dysku potrafi odczytywać i zapisywać oraz umieszczeniu w każdym sektorze specjalnej struktury danych Pamięć pomocnicza 21 Struktura danych sektora: " nagłówek " obszar danych " zakończenie Informacje zawarte w nagłówku i zakończeniu " numer sektora " kod korygujący ECC (ang. error correcting code) Pamięć pomocnicza 22 Przetwarzanie ECC " podczas zapisu kod korygujący zostaje uaktualniony za pomocą wartości obliczonej na podstawie bajtów zapisanych w sektorze " podczas czytania sektora kod korygujący jest obliczany ponownie i porównywany z wartością zapamiętaną " jeżeli wartości zapamiętana i obliczona są różne podejrzenie uszkodzenia sektora " kod ECC jest samokorygujący w przypadku gdy 1 lub 2 bity danych są uszkodzone to kod potrafi je wyszukać oraz obliczyć ich poprawną wartość " przetwarzanie ECC jest wykonywane automatycznie przez sterownik podczas każdego pisania czy czytania sektora Pamięć pomocnicza 23 Rozmiar obszaru danych " najczęściej wybierane rozmiary: 256, 512, 1024B " używanie większych rozmiarów obszaru danych oznacza że na każdej ścieżce znajdować się będzie mniej sektorów " mniejsza liczba sektorów oznacza także mniej nagłówków oraz zakończeń sektorów więcej miejsca dla danych Aby zastosować dysk do przechowywania danych w postaci plików system operacyjny musi na nim umieścić swoje struktury danych I. Dzielenie dysku na jedną lub więcej grup cylindrów Każda tak powstała grupa jest tzw. strefą (partycją), którą system operacyjny traktuje jak osobny dysk II. Formatowanie logiczne System operacyjny zapisuje na dysku początkowe struktury danych systemu plików: mapa wolnych i przydzielonych obszarów (tablica alokacji plików), początkowy, pusty katalog Pamięć pomocnicza 24 Blok rozruchowy " Komputer zaczynając pracę wykonuje tzw. program wstępny " Program rozruchowy (ang. bootstrap) ustawia stan początkowy wszystkich elementów systemu komputerowego: procesora, sterowników urządzeń, zawartości pamięci. Następnie uruchamia system operacyjny program rozruchowy znajduje jądro systemu na dysku, umieszcza je w pamięci oraz wykonuje skok pod adres początkowy w celu wykonania systemu operacyjnego " program rozruchowy przechowuje się w specjalnej części dysku, w strefie nazywanej blokiem rozruchowym (ang. boot block) " dysk ze strefą rozruchową dysk rozruchowy (ang. boot disk) Pamięć pomocnicza 25 Przykład 6. Blok rozruchowy z systemie MS-DOS zawiera tylko 512B Blok rozruchowy Sektor 0 Tablica FAT Sektor 1 Katalog główny Bloki danych Bloki uszkodzone " Dyski to delikatne urządzenia bardzo wrażliwe na awarie " W przypadku awarii zupełnej wymiana dysku i rekonstrukcja danych z nośników awaryjnych " W większości przypadków występują awarie częściowe jeden lub więcej sektorów ulega uszkodzeniu Pamięć pomocnicza 26 Postępowanie z blokami uszkodzonymi " eliminacja ręczna dyski IDE polecenieformat: formatowanie logiczne i analiza dysku w poszukiwaniu wadliwych bloków polecenieverb: szukanie wadliwych bloków i blokowanie dostępu do nich " eliminacja automatyczna dyski SCSI sterownik dysku utrzymuje wykaz uszkodzonych bloków; wykaz jest uaktualniany przez cały czas eksploatacji dysku sterownikowi można nakazać logiczne zastąpienie każdego uszkodzonego sektora za pomocą sektora zapasowego Pamięć pomocnicza 27 ZARZDZANIE OBSZAREM WYMIANY Pamięć wirtualna korzysta z przestrzeni dyskowej jako rozszerzenia pamięci głównej Dostęp do dysku jest znacznie wolniejszy niż do pamięci głównej, więc zastosowanie obszaru wymiany ma duży wpływ na wydajność systemu Cel: Umożliwienie najlepszej przepustowości systemowej pamięci wirtual- nej Umiejscowienie obszaru wymiany Obszar wymiany może znajdować się w dwu miejscach: 1. w systemie plików 2. w oddzielnej strefie dyskowej Pamięć pomocnicza 28 Obszar wymiany jako jeden wielki plik w systemie plików Do utworzenia pliku wymiany, nazwania, przydzielenia mu miejsca na dysku można użyć zwykłych procedur systemu plików Zalety: " podejście łatwe do realizacji Wady: " mała wydajność; praca z systemem plików, przeszukiwanie katalogu oraz struktur danych jest czasochłonne i wymaga dodatkowych operacji dyskowych " fragmentacja zewnętrzna może znacznie wydłużyć czas wymiany wielokrotne przeszukiwanie podczas czytania lub zapisywania procesu Poprawa wydajności przechowywanie podręczne w pamięci operacyjnej informacji o położeniu bloków wymiany w odrębnej strefie dyskowej Pamięć pomocnicza 29 Obszar wymiany w oddzielnej strefie dyskowej W strefie przeznaczonej na obszar wymiany nie montuje się żadnego systemu plików, ani nie buduje struktury katalogów Do przydzielania i zwalniania bloków stosuje się zarządcę pamięci obszaru wymiany Zarządca pamięci nie optymalizuje zużycia pamięci, lecz korzysta z algorytmów optymalizujących czas przesyłania danych pomiędzy dyskiem a pamięcią operacyjną Wzrasta fragmentacja wewnętrzna, lecz jest to do przyjęcia gdyż w obszarze wymiany dane pozostają znacznie krócej niż pliki w zwykłym systemie plików Podejście powoduje utworzenie obszaru wymiany o stałym rozmiarze " zwiększenie obszaru wymiany wymaga powtórnego podziału dysku na strefy " przemieszczenie i zniszczenie danych z innych stref; odtwarzanie danych tych stref z kopii zapasowych