Pamięć pomocnicza

dr inż. Krzysztof Patan

Instytut Sterowania i Systemów Informatycznych

Uniwersytet Zielonogórski

[e-mail]

Pamięć pomocnicza

1

WSTĘP

 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

œcie¿ki

sektory

cylinder

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 DOSTĘPU 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óźnienie 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]

1

cylindry

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]

1

cylindry

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

236

= 2, 71

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ć wyraźnie 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 ←

1

cylindry

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 →

1

cylindry

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

Kolejka: [98,183,37,122,14,124,65,67]

Kierunek ruchu głowicy ←

1

cylindry

20

60

100

140

180

Planowanie dostępu do dysku metodą LOOK

Bieżące położenie głowicy: cylinder 53

Kolejka: [98,183,37,122,14,124,65,67]

Kierunek ruchu głowicy →

1

cylindry

20

60

100

140

180

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ądź 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óźnienia 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óźnienie 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óźnienie obrotowe było jak

najmniejsze

Pamięć pomocnicza

20

ZARZĄDZANIE 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

Sektor 1

Tablica FAT

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

 polecenie format: formatowanie logiczne i analiza dysku w poszukiwaniu

wadliwych bloków

 polecenie verb: 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

ZARZĄDZANIE 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