Zarządzanie dyskiem

Streszczenie

W niniejszym wykładzie zajmiemy się zarządzaniem dostępu do dysków magnetycznych. Przedstawiamy podstawowe pojęcia dotyczące dysków, oraz strategie szeregowania odwołań do dysku.

Wprowadzenie

Dyski magnetyczne stanowią najpopularniejszy rodzaj masowej pamięci trwałej. W punkcie tym przedstawiamy zasadę działania dysku oraz podstawowe pojęcia dotyczące dysków magnetycznych.

Poniższy rysunek przedstawia schematycznie budowę typowego dysku magnetycznego. Dysk składa się z kilku talerzy osadzonych sztywno na wspólnej osi i wirujących z dużą prędkością. Każdy z talerzy pokryty jest z obu stron warstwą magnetyczną, na której można zapisywać informacje. Powierzchnie talerzy są podzielone na koncentrycznie ułożone ścieżki. Ścieżki są dalej podzielone na sektory. Sektor to podstawowa jednostka zapisu/odczytu z dysku. Typowa wielkość sektora, to 512B. Informacje są zapisywane i odczytywane przez głowice unoszące się tuż nad powierzchnią talerzy. Głowice są przymocowane do ramion osadzonych sztywno na wspólnej osi. Przesuwając ramiona, przesuwamy głowice między ścieżkami. Zestaw ścieżek ze wszystkich powierzchni talerzy, tak samo odległych od osi talerzy nazywamy cylindrem. Wszystkie sektory w cylindrze mogą być odczytywane/zapisywane bez konieczności przesuwania głowic.

Powierzchnię talerzy można przyrównać do kartki papieru. Oprócz informacji przechowywanych na dysku, na talerzach zapisane są dodatkowe informacje wyznaczające podział dysku na sektory. Informacje te można porównać do kratek na papierze w kratkę. Proces nagrywania tych informacji organizacyjnych nazywany jest formatowaniem (niskopoziomowym). Terminu formatowanie (wysokopoziomowe) używa się również w odniesieniu do utworzenia na nowym dysku systemu plików. Fabrycznie nowe dyski są już zwykle sformatowane niskopoziomowo.

Chcąc określić, którego sektora ma dotyczyć operacja dyskowa, musimy podać jego współrzędne: powierzchnię talerza, ścieżkę i pozycję sektora na ścieżce. We współczesnych napędach dyskowych fizyczne współrzędne sektorów są ukryte przed resztą systemu komputerowego. Dysk udostępnia linową logiczną tablicę sektorów (ang. linear block addressing). Dzięki temu, na ścieżkach zewnętrznych może być więcej sektorów niż na ścieżkach wewnętrznych i jest to zrealizowane w sposób niewidoczny dla systemu operacyjnego.

Dyski magnetyczne są precyzyjnymi urządzeniami podatnymi na uszkodzenia. Jedno z takich uszkodzeń polega na uszkodzeniu sektora. Czasami takie błędy można naprawić. Informacje są zapisywane w sektorach z użyciem kodu korygującego błędy. Zapisanej informacji towarzyszy rodzaj sumy kontrolnej, która w przypadku przekłamania ograniczonej ilości informacji (1-2 bity) pozwala na wykrycie przekłamania oraz odtworzenie oryginalnej zawartości. Jeżeli nośnik magnetyczny uległ w danym miejscu uszkodzeniu, to mamy do czynienia z tzw. uszkodzonym sektorem. Systemy plików zwykle potrafią radzić sobie z uszkodzonymi sektorami. Blok dyskowy zawierający taki sektor jest zaznaczany jako uszkodzony i nie jest więcej wykorzystywany. Jeżeli udało się odtworzyć zawartość uszkodzonego sektora, to jest ona przenoszona w inne miejsce na dysku. Współczesne dyski potrafią również same radzić sobie z uszkodzonymi sektorami. Każdy cylinder zawiera pewną pulę zapasowych sektorów. Sektory zapasowe nie są widoczne dla reszty systemu komputerowego. W przypadku wykrycia uszkodzonego sektora jest on automatycznie zastępowany przez sektor zapasowy.

O prędkości dysku decyduje kilka parametrów:

czas szukania (ang. seek time) -- jest to czas potrzebny na przemieszczenie ramienia z głowicami nad wybrany cylinder,
opóźnienie obrotowe (ang. rotation latency) -- jest to czas potrzebny na to, aby wybrany sektor przejechał pod głowicami; czas ten zależy od prędkości obrotowej talerzy,
szybkość przesyłu informacji z/do napędu dyskowego.

O ile opóźnienie obrotowe i szybkość przesyłu informacji zależą tylko od konstrukcji dysku, to czas szukania zależy również od systemu operacyjnego. Często operacje dyskowe nie dotyczą losowo wybranych sektorów dysku, lecz sektorów tworzących kolejne bloki pliku. System operacyjny powinien starać się tak rozmieszczać pliki na dysku, aby kolejne bloki pliku były zapisane w miarę po kolei na dysku. Wówczas często kolejna operacja dyskowa będzie odnosić się do tego cylindra, nad którym akurat znajdują się głowice. W ten sposób minimalizuje się czas szukania. Nawet jeżeli chcemy wykonać operację w innym cylindrze, to system operacyjny może starać się minimalizować czas szukania. Jeżeli oczekuje na wykonanie kilka operacji dyskowych, to czas szukania zależy od sposobu szeregowania odwołań do dysku. Temat ten omawiamy szczegółowo poniżej.

Strategie szeregowania odwołań do dysku

Wyobraźmy sobie sytuację, w której kilka odwołań do różnych miejsc na dysku oczekuje na wykonanie. Czy kolejność, w której je wykonamy ma znaczenie? Okazuje się że tak. Ma ona wpływ na czas szukania na dysku. Im większą drogę muszą przebyć głowice, tym dłuższy czas szukania.

Na potrzeby tego punktu założymy dla uproszczenia, że czas szukania jest proporcjonalny do dystansu, jaki muszą przebyć głowice. Tak więc nasze zadanie sprowadza się do znalezienia takiej strategii, która będzie minimalizować dystans przebywany przez głowice.

Wszystkie przedstawione poniżej strategie będziemy ilustrować następującym przykładem: Załóżmy, że dysk ma 100 cylindrów, ponumerowanych od 0 do 99. Głowice znajdują się nad cylindrem nr 42. W systemie operacyjnym oczekują na wykonanie odwołania do cylindrów nr: 51, 21, 45, 75, 12, 84, 36, 69, 80 (zgłoszone właśnie w tej kolejności).

Strategia FCFS

Strategia FCFS (ang. first-come first-served) to najprostsza z możliwych strategii. Polega ona na wykonywaniu odwołań do dysku w takiej kolejności, w jakiej się one pojawiają. Poniższy rysunek przedstawia przebieg głowicy dla podanych powyżej odwołań. Jak widać można by trochę zaoszczędzić.

Strategia SSTF

Strategia SSTF (ang. shortest seek time first) polega na tym, że w pierwszej kolejności obsługiwane jest to odwołanie do dysku, które jest najbliżej aktualnej pozycji głowicy. Poniższy rysunek przedstawia przebieg głowicy dla podanych powyżej odwołań. Strategia ta jest dobra, jeżeli dysk nie intensywnie używany przez wiele procesów. W przeciwnym przypadku jest ona podatna na zagłodzenie. Może się zdarzyć, że pewne odwołanie będzie oczekiwać na wykonanie, ale cały czas będą spływać inne odwołania, które będą bliżej aktualnej pozycji głowicy.

Strategia scan

W strategii scan głowice poruszają się wahadłowo od skrajnie zewnętrznego do skrajnie wewnętrznego cylindra i z powrotem. Po drodze zatrzymują się wykonując odwołania do napotykanych cylindrów. Poniższy rysunek przedstawia przebieg głowicy dla przykładowych odwołań.

Strategia ta jest lepsza niż FCFS i nie występuje w niej zagłodzenie. Ma jednak pewne wady. W strategii tej średni czas oczekiwania na odwołanie do dysku zależy od miejsca na dysku. Głowice dwa razy częściej przesuwają się nad środkowymi cylindrami, niż nad skrajnymi. Wady tej pozbawione są strategie c-scan i c-look, opisane poniżej. Inna wada polega na tym, że głowice niepotrzebnie przesuwają się aż do skrajnych cylindrów. Tej wady pozbawione są strategie look i c-look.

Strategia c-scan

Strategia c-scan jest modyfikacją strategii scan. Głowice przesuwają się w jednym kierunku po dysku realizując odwołania do mijanych cylindrów. Gdy osiągną skrajny cylinder, to natychmiast przesuwają się na drugi koniec dysku, nie realizując po drodze żadnych odwołań, po czym cały cykl jest powtarzany. Strategia ta jest nieco wolniejsza niż scan, ale za to średni czas oczekiwania na wykonanie odwołania do dysku jest taki sam dla wszystkich cylindrów.

Strategia look

Strategia look stanowi modyfikację strategii scan. Głowice nie są przesuwane do skrajnych cylindrów jeżeli nie ma takiej potrzeby. Zawracają po obsłużeniu skrajnego odwołania. Strategia ta jest czasami nazywana "windową", gdyż ruchy głowic przypominają poruszanie się windy, która jeździ w górę i w dół, zabierając oczekujących pasażerów. Podobnie jak w przypadku strategii scan, średni czas oczekiwania na realizację odwołania do dysku zależy od miejsca na dysku. Wady tej jest pozbawiona strategia c-look, opisana poniżej.

Strategia c-look

Strategia c-look stanowi modyfikację strategii look. Podobnie, jak w przypadku c-scan, odwołania do dysku są realizowane tylko gdy głowice przesuwają się w jedną stronę po dysku. Po zrealizowaniu skrajnego odwołania głowice zawracają i przesuwają się do skrajnego odwołania po drugiej stronie dysku. Strategia ta jest trochę wolniejsza niż strategia look, ale za to średni czas oczekiwania na realizację odwołania jest taki sam dla wszystkich cylindrów.

Podsumowanie

Mając tyle strategii szeregowania odwołań do dysku, którą należy wybrać? W przypadku stacji roboczych dosyć często stosowana jest strategia SSTF, a w przypadku serwerów, w których występuje dużo odwołań do dysków stosowane są raczej strategie look lub c-look. Warto pamiętać, że wybór strategii ma znaczenie tylko wtedy, gdy w systemie operacyjnym jednocześnie oczekuje na wykonanie wiele odwołań do dysku. Jeśli będziemy mieli tylko jedno odwołanie na raz, to każda strategia będzie się zachowywać jak FCFS.

Słownik

cylinder: zestaw ścieżek które mogą być równocześnie zapisywane/odczytywane bez konieczności przesuwania głowic.
formatowanie: proces nagrywania informacji organizacyjnych na dysku: formatowanie niskopoziomowe dotyczy podziału dysku na sektory, a formatowanie wysokopoziomowe utworzenia na dysku systemu plików.
sektor: podstawowa jednostka zapisu/odczytu z dysku; typowa wielkość sektora, to 512B.
ścieżka: sektory na jednej powierzchni jednego talerza, które mogą być odczytane/zapisane bez przesuwania głowicy.
talerz: fragment dysku magnetycznego; talerze w dysku magnetycznym są pokryte z obu stron warstwą magnetyczną, na której można zapisywać informacje, są osadzone sztywno na wspólnej osi i wirują z dużą prędkością.
uszkodzony sektor: sektor, w którym nośnik magnetyczny uległ uszkodzeniu; jest on zastępowany przez inny sektor.

Zadania

(8p.) Załóżmy, że dysk ma 1000 cylindrów, ponumerowanych od 0 do 999. Głowice znajdują się nad cylindrem nr 29 i domyślnie poruszają się w górę. W systemie oczekują odwołania do cylindrów nr: 17, 285, 179, 357, 186, 302, 205, 351, 24 (zgłoszone w tej kolejności). Dla każdej z przedstawionych strategii szeregowania podaj jaki będzie łączny dystans przebyty przez głowice, od aktualnej pozycji, do momentu zrealizowania ostatniego odwołania.
(2p.) Mamy dany dysk o prędkości obrotowej 7200 obr/min. Jakie jest średnie opóźnienie obrotowe tego dysku?

Strona przygotowana przez Marcina Kubicę i Krzysztofa Stencla.