Wykład 7
Pamięć pomocnicza
W większości systemów komputerowych istnieje pamięć pomocnicza jako rozszerzenie
pamięci podstawowej, (zwanej pamięcią główną lub operacyjną). Podstawowym zadaniem
systemu komputerowego jest wykonywanie programów. Ideałem byłoby przechowywanie
programu i jego danych w pamięci głównej. Nie jest to możliwe z dwu przyczyn:
żð Pamięć główna jest za maÅ‚a, aby mogÅ‚a nieustannie przechowywać wszystkie
potrzebne programy i dane
żð Pamięć główna jest tzw. medium ulotnym, co powoduje utratÄ™ danych w przypadku
zaniku napięcia
Od pamięci pomocniczej zatem wymaga się, aby można w niej trwale było przechowywać
olbrzymie ilości danych.
TrochÄ™ historii:
żð Jako pierwsza stosowana byÅ‚a taÅ›ma magnetyczna. Ma ona pewne zalety: wzglÄ™dna
trwałość, duża ilość danych. Jednak jest ona powolna i co najważniejsze, dostęp do
danych mógł być wyłącznie sekwencyjny. Toteż jest nieprzydatna do organizacji
dostępu swobodnego, niezbędnego w pamięci wirtualnej. Obecnie taśm używa się
wyłącznie do składowania i przechowywania rzadko potrzebnych informacji.
żð We współczesnych systemach komputerowych rolÄ™ masowej pamiÄ™ci pomocniczej
spełniają dyski - głównie magnetyczne, choć dyski optyczne z możliwością operacji
zapisu sÄ… do nich funkcjonalnie podobne.
żð
Struktura dysku
Konstrukcja fizyczna dysków przedstawia się względnie prosto (zobacz rysunek). Każdy dysk
ma kształt płaski i okrągły i przypomina płytę gramofonową. Obie jego powierzchnie są
pokryte materiałem magnetycznym, podobnym do nośnika taśmy magnetycznej. Na
powierzchniach tych jest zapisywana informacja.
Tak w rzeczywistości wygląda twardy dysk, urządzenie
najczęściej używane jako pamięć pomocnicza w systemach
komputerowych.
Struktura fizyczna dysku
Kiedy dysk pracuje, wtedy napędzający go silnik wprawia go w ruch wirowy o dużej
prędkości (np. 60 obrotów na sekundę). Tuż nad powierzchnią dysku znajduje się głowica
czytająco-pisząca. Zasadniczo rozróżniamy dwa typy dysków:
" Dysk o nieruchomych głowicach szybkie przy pomocy układów elektronicznych
przełączanie się ze ścieżki na ścieżkę, urządzenie bardzo drogie.
" Dysk z ruchomą głowicą - jedna głowica, co znacznie polania system.
Podstawowe parametry dysku
" Sektor: najmniejszy blok, który można zapisać/odczytać z dysku
" Ścieżka: zbiór wszystkich sektorów na pojedynczej powierzchni leżących w tej samej
odległości od osi obrotu
" Cylinder: zbiór wszystkich ścieżek leżących w tej samej odległości od osi obrotu
dysku na dysku w wieloma talerzami
" Adres dyskowy: nr napędu, nr powierzchni, nr ścieżki (cylindra), nr sektora
" Czas przeszukiwania (ang. seek time): czas przesunięcia głowicy na właściwą
ścieżkę (nast. elektronicznie wybiera się właściwą powierzchnię)
" Czas oczekiwania (ang. latency time): czas oczekiwania aż głowica znajdzie się nad
właściwym sektorem (to dysk się kręci!); określony przez prędkość rotacji dysku
" Czas transmisji - czas potrzebny na odczytanie/zapisanie danych
" Jednostka transmisji: sektor lub grupa sektorów. SO traktuje dysk jak
jednowymiarową tablicę: numery bloków rosną wzdłuż sektorów na ścieżce, następnie
wzdłuż ścieżek w cylindrze, następnie od cylindra 0 do ostatniego.
Dyski charakteryzują się dwiema ważnymi cechami, które czynią z nich wygodny środek
przechowywania plików:
żð Informacje mogÄ… być uaktualniane bez zmiany miejsca; można przeczytać blok z
dysku, wprowadzić do niego zmiany i zapisać go z powrotem na tym samym miejscu
na dysku.
żð Dowolny blok informacji na dysku można zaadresować bezpoÅ›rednio. Zatem
zarówno sekwencyjny jak i swobodny dostęp do dowolnego pliku jest łatwy do
osiągnięcia, a przełączanie od jednego pliku do drugiego wymaga tylko przesunięcia
głowic czytająco-piszących i zaczekania na obrót dysku.
Katalog urzÄ…dzenia
Na dysku z reguły znajduje się katalog urządzenia dyskowego informujący o
przechowywanych na nim plikach. Katalog najczęściej zawiera:
" wykaz nazw plików
" informacje o rozmieszczeniu pliku na dysku,
" długości pliku,
" jego typie,
" właścicielu,
" czasie utworzenia,
" czasie ostatniego użycia,
" trybach ochrony itd.
Katalog można wedle potrzeby czytać, uaktualniać i zapisywać ponownie bez
konieczności kopiowania reszty dysku. Każda fizyczna jednostka dyskowa - pakiet dysków
lub dyskietka - ma własny katalog urządzenia.
Katalog urządzenia jest przechowywany na danym urządzeniu, często pod pewnym stałym
adresem, takim jak adres dyskowy 00001. (Adres 00000 na ogół jest przeznaczony dla
procedury Å‚adujÄ…cej system).
Organizacja ta jest szczególnie przydatna w przypadku wymiennych nośników informacji, w
rodzaju dyskietek lub wyjmowalnych zestawów dysków. Jeśli nośnik będzie zdemontowany,
przechowany i ponownie zamontowany - być może na innym napędzie - to możliwość
odnalezienia póz
niej na nim plików jest zapewniona.
Logiczny system plików używa struktury katalogowej, aby na podstawie symbolicznej nazwy
pliku dostarczać informacji potrzebnych procesowi wykorzystującemu plik.
Aby utworzyć nowy plik system czyta odpowiiedni katalog do pamięci, uaktualnia go,
dodajÄ…c nowy wpis i zapisuje na dysku.
Aby użyć pliku należy go otworzyć. Otwarcie to odszukanie odpowiedniego wpisu w
katalogu i przekopiowanie do tablicy nazywanej tablicą otwartych plików , znajdującej się
w pamięci operacyjnej.
Do programu użytkownika zostaje przekazany indeks do tej tablicy, zwany:
a) deskryptorem pliku (UNIX)
b) uchwytem plikowym (WINDOWS NT)
c) blokiem kontrolnym pliku
Typowa tablica plików otwartych wygląda następująco:
Indeks Nazwa pliku Prawa dost. Daty dost. Wskaz. do bloku dysk
0 TEST.C rw rw rw 236
1 MAIL.TXT rw 94
2 AAA.TXT 432
Metody przydziału miejsca na dysku
Podstawową kwestią jest wybór takiego sposobu przydziału miejsca dla plików, aby obszar
dysku był zagospodarowany efektywnie, a dostęp do plików szybki.
Powszechnie używa się trzech głównych metod przydziału miejsca na dysku: ciągłej, listowej
i indeksowej.
Przydział ciągły
W metodzie przydziału ciągłego każdy plik musi zajmować ciąg kolejnych adresów
blokowych na dysku.
Tak więc liczba operacji przeszukiwania dysku wymaganych przy rozmieszczeniu plików na
dysku metodą ciągłą jest minimalna; dotyczy to także czasu przeszukiwania, jeśli jest ono
nieuniknione.
Przydział ciągły pliku jest określony za pomocą adresu dyskowego pierwszego bloku i
długości. Jeśli plik składa się z n bloków i zaczyna się od adresu bloku b, to zajmuje bloki b,
b + 1, b + 2,..., b + n - 1.
Pozycja każdego pliku w katalogu zawiera adres bloku początkowego i długość obszaru
przydzielonego danemu plikowi. Dostęp do pliku, któremu przydzielono miejsce w sposób
ciągły, jest dość łatwy. Przy dostępie sekwencyjnym system plików pamięta adres dyskowy
ostatniego bloku, do którego było odniesienie i w razie potrzeby czyta następny blok.
W celu bezpośredniego dostępu do bloku i w pliku zaczynającym się od bloku b, można
odnieść się wprost do bloku b + i. Tak więc za pomocą przydziału ciągłego można
implementować zarówno dostęp sekwencyjny, jak i swobodny.
SumujÄ…c:
" minimalna liczba operacji dyskowych (przesuwu głowicy)
" przydział określony za pomocą adresu początku i liczby bloków
" prosta implementacja dostępu sekwencyjnego i bezpośredniego
" trudno znalez
ć miejsce na nowy plik (strategie: pierwszy pasujący, najlepszy pasujący;
fragmentacja zewnętrzna)
" trudno rozszerzać plik (ew. trzeba z góry podać rozmiar pliku)
" konieczność kompresji
Przydział listowy
W przydziale listowym każdy plik stanowi listę powiązanych ze sobą bloków dyskowych;
bloki te mogą znajdować się gdziekolwiek na dysku.
Katalog zawiera wskaz
nik do pierwszego i ostatniego bloku pliku. Na przykład plik złożony z
pięciu bloków może zaczynać się w bloku 9, jego dalszy ciąg może znajdować się w bloku
16, potem w bloku 1, 10 i kończyć się w bloku 25.
Każdy blok zawiera wskaz
nik do następnego bloku. Wskaz
niki te nie są dostępne dla
użytkownika. Toteż jeśli każdy sektor ma 512 słów, a adres dyskowy (wskaz
nik) zajmuje dwa
słowa, to użytkownik widzi bloki o długości 510 słów.
Tworzenie pliku jest Å‚atwe. Po prostu tworzy siÄ™ nowÄ… pozycjÄ™ w katalogu urzÄ…dzenia. W
przydziale listowym każda pozycja w katalogu ma wskaz
nik do pierwszego bloku pliku.
Początkową wartością tego wskaz
nika jest nil (wartość wskazująca koniec listy) w celu
zaznaczenia, że plik jest pusty. Pole rozmiaru również przyjmuje wartość zero.
Operacja pisania do pliku usuwa pierwszy wolny blok z listy wolnych obszarów i wypełnia
go zapisywaną informacją. Ów nowy blok zostanie następnie dowiązany do końca pliku.
Czytanie pliku odbywa się po prostu według wskaz
ników zapamiętanych w blokach. W
przydziale listowym nie ma zewnętrznej fragmentacji pamięci. Każdy blok z listy wolnych
obszarów może być użyty przy spełnianiu zamówienia, ponieważ wszystkie bloki są ze sobą
powiązane. Zauważmy też, że nie ma żadnego powodu, by deklarować rozmiar pliku w chwili
jego tworzenia. Plik może rosnąć dopóty, dopóki są wolne bloki. W konsekwencji, nie ma
nigdy potrzeby upakowywania dysku.
Przydział indeksowy
Przydział listowy nie może służyć do organizacji dostępu bezpośredniego, gdyż bloki są
rozrzucone po całym dysku. Równie przykry jest fakt, iż po całym dysku są rozrzucone
wskaz
niki do bloków. Przydział indeksowy rozwiązuje ten problem przez skupienie
wskaz
ników w jednym miejscu - w bloku indeksowym.
Każdy plik ma własny blok indeksowy, będący tablicą adresów bloków dyskowych.
Pozycja o numerze i w bloku indeksowym wskazuje na blok i danego pliku. Katalog zawiera
adres bloku indeksowego. Aby przeczytać blok i, używa się wskaz
nika z pozycji o numerze i
w bloku indeksowym, za którego pomocą znajduje się odpowiedni blok do czytania.
Podczas tworzenia pliku wszystkie wskaz
niki w bloku indeksowym otrzymują wartość nil.
Gdy blok i jest po raz pierwszy zapisywany, wówczas usuwa się go z listy wolnych
przestrzeni; jego adres zostaje umieszczony w pozycji o numerze i w bloku indeksowym.
Przydział indeksowy umożliwia dostęp bezpośredni bez powodowania zewnętrznej
fragmentacji pamięci.
Zamówienie na dodatkowy obszar może spełnić wolny blok znajdujący się gdziekolwiek na
dysku. Przydział indeksowy powoduje natomiast marnowanie miejsca na dysku. Nakład na
wskaz
niki bloku indeksowego jest na ogół większy niż nakład na wskaz
niki przy przydziale
listowym.
Planowanie dostępu do dysku
Jest ważne, aby usługi dyskowe były możliwie jak najszybsze, ponieważ wiele zadań jest
mocno uzależnionych od dysku ze względu na konieczność czytania i zapisywania plików na
dysku (operacje we/wy).
Prędkość dysku zależy od trzech czynników.
Aby dotrzeć do bloku na dysku, system musi najpierw przesunąć głowicę do odpowiedniej
ścieżki lub cylindra. Ruch głowicy nazywa się przeszukiwaniem, a czas potrzebny na jego
ukończenie zwie się czasem przeszukiwania.
Gdy głowica czytająco-pisząca znajdzie się nad właściwą ścieżką, wówczas musi zaczekać,
aż przemieści się pod nią potrzebny blok danych. To opóz
nienie nazywa siÄ™ czasem
oczekiwania (ang. latency time).
W końcu może nastąpić właściwe przesyłanie danych między dyskiem a pamięcią główną. Tę
ostatnią część określa czas przesyłania.
A
ączny czas obsługi zamówienia dyskowego jest sumą czasu przeszukiwania, oczekiwania
i przesyłania:
czas obsługi żądania = czas przeszukiwania + czas oczekiwania + czas transmisji
Zazwyczaj czas przeszukiwania odgrywa główną rolę w porównaniu pozostałymi dwoma
czasami. O ile opóz
nienie obrotowe i szybkość przesyłu informacji zależą tylko od
konstrukcji dysku, to czas przeszukiwania zależy również od systemu operacyjnego. Jeżeli
oczekuje na wykonanie kilka operacji dyskowych, to czas przeszukiwania zależy od sposobu
szeregowania odwołań do dysku.
Strategie szeregowania odwołań do dysku
Wyobraz
my sobie sytuację, w której wiele odwołań do różnych miejsc na dysku oczekuje na
wykonanie. Jest jasne że kolejność, w której je wykonamy ma znaczenie.
Możemy założyć, że czas przeszukiwania jest proporcjonalny do dystansu, jaki musi
przebyć głowica. Tak więc zadanie optymalnego szeregowania odwołań dyskowych
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 200 cylindrów, ponumerowanych od 0 do 199.
GÅ‚owica znajduje siÄ™ nad cylindrem nr 65. W systemie operacyjnym oczekujÄ… na wykonanie
odwołania do cylindrów nr: 65, 103 186, 44, 122, 18, 124, 71 (zgłoszone właśnie w tej
kolejności).
Planowanie metodÄ… FCFS
Najprostszą metodą planowania dostępu do dysku jest - oczywiście - planowanie na zasadzie
pierwszy nadszedł - pierwszy obsłużony (FCFS).
Algorytm ten jest łatwy do zaprogramowania i wewnętrznie poprawny. Jednak przy jego
zastosowaniu średni czas obsługi może nie być najlepszy.
Jeśli głowica czytająco-pisząca znajduje się początkowo przy ścieżce 53, to przemieści się
najpierw od ścieżki 53 do ścieżki 65, następnie do ścieżek: 103, 186, 44, 122, 18, 124 i
wreszcie do 71, przechodząc łącznie nad około 640 ścieżkami (patrz rysunek).
18 44 65 71 103 122 124 186
Planowanie metodÄ… SSTF (ang. shortest seek-time-first-SSTF)
Wydaje się uzasadnione, aby dążyć do łącznej obsługi wszystkich zamówień sąsiadujących z
bieżącym położeniem głowicy, zanim nastąpi jej przemieszczenie w odleglejszy rejon w celu
realizacji innego zamówienia.
To założenie stanowi podstawę dyskowego algorytmu planowania, noszącego nazwę
najpierw najkrótszy czas przeszukiwania (ang. shortest seek-time-first-SSTF).
Algorytm SSTF wybiera zamówienie z minimalnym czasem przeszukiwania względem
bieżącej pozycji głowicy. Ponieważ czas przeszukiwania jest ogólnie biorąc proporcjonalny
do różnicy numerów ścieżek między zamówieniami, algorytm ten implementuje się za
pomocą przesuwania głowicy do najbliższej ścieżki z kolejki zamówień.
18 44 65 71 103 122 124 186
Najbliższe zamówienie wobec początkowego położenia głowicy dotyczy ścieżki 71.
Z tego miejsca odległość do ścieżki 44 wynosi 25, a odległość do 103 wynosi 32. Wobec tego
zamówienie na ścieżkę 44 jest bliższe i będzie obsłużone w pierwszej kolejności. W dalszym
ciągu wybiera się w ten sposób ścieżkę 18, potem 103, 122, 124 i na koniec 186 (rysunek).
Ta metoda planowania owocuje łącznym przemieszczeniem głowicy nad zaledwie 236
ścieżkami, o ponad jedną trzecią mniej od odległości koniecznej przy planowaniu metodą
FCFS.
Strategia ta jest dobra, jeżeli dysk nie jest 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ą wykonywane inne odwołania,
które będą bliżej aktualnej pozycji głowicy.
Planowanie metodÄ… SCAN
Rozpoznanie właściwości dynamicznych kolejki zamówień prowadzi nas do zastosowania
algorytmu SCAN.
Głowica czytająco-pisząca startuje od jednego końca dysku i przemieszcza się w kierunku
przeciwległego końca, obsługując zamówienia, które napotyka przechodząc nad kolejnymi
ścieżkami, aż dotrze do drugiego końca dysku. Na drugim końcu zmienia się kierunek ruchu
głowicy i obsługa jest kontynuowana. Głowica nieprzerwanie przeszukuje dysk od końca do
końca.
Znów posłużymy się naszym przykładem. Przed zastosowaniem algorytmu SCAN do
zaplanowania kolejki : 65, 103 186, 44, 122, 18, 124, 71
Oprócz pozycji głowicy, jest nam potrzebna znajomość kierunku ruchu głowicy. Jeśli głowica
poruszałaby się w kierunku ścieżki 0, to podczas jej przemieszczenia się nastąpiłyby
realizacje zamówień na ścieżki 44 i 18.
Przy ścieżce 0 głowica zmieniłaby kierunek ruchu i rozpoczęłaby przemieszczanie do
przeciwległego końca dysku, obsługując zamówienia na ścieżki: 71, 103, 122, 124 i 183 (zob.
rysunek).
18 44 65 71 103 122 124 186
Jeśli w kolejce pojawiłoby się zamówienie odnoszące się do ścieżki tuż przed głowicą, to
zostałoby realizowane niemal natychmiast, natomiast zamówienie pojawiające się tuż za
głowicą musiałoby poczekać na obsługę, aż głowica dojdzie do końca dysku, zmieni kierunek
i wróci.
Algorytm SCAN bywa czasami nazywany algorytmem windy, ponieważ przypomina
zachowanie wind obsługujących zgłoszenia na zasadzie wahadłowego ruchu między piętrami
budynku.
Inną analogią jest tu odgarnianie śniegu z autostrady podczas zadymki. Rozpoczynając od
jednego końca usuwamy śnieg jadąc w kierunku drugiego końca. Po przejechaniu, za naszymi
plecami zdążył już napadać nowy śnieg. Zawracamy więc, i usuwamy ten nowo spadły śnieg.
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.
Jest to wada tego algorytmu.
 Planowanie metodÄ… C-SCAN
Wariantem algorytmu planowania SCAN, zaprojektowanym w trosce o bardziej równomierny
czas czekania, jest algorytm planowania C-SCAN (SCAN cykliczny).
Tak jak w przypadku planowania metodÄ… SCAN, w algorytmie C-SCAN przesuwa siÄ™
głowicę od jednego końca dysku do drugiego, obsługując napotykane po drodze zamówienia.
Jednak gdy głowica osiągnie przeciwległy koniec, wówczas wraca natychmiast na początek
dysku, bez podejmowania obsługi jakiegokolwiek zamówienia w drodze powrotnej.
Planowanie C-SCAN w istocie traktuje dysk jak cykliczną powierzchnię, na której ostatnia
ścieżka przylega do ścieżki pierwszej.
Planowanie metodÄ… LOOK i C-LOOK
Zarówno w planowaniu metodą SCAN, jak i C-SCAN głowica przemieszcza się zawsze od
jednego skrajnego położenia na dysku do drugiego. W praktyce żaden z tych algorytmów nie
jest implementowany w ten sposób.
Najczęściej głowica przesuwa się do skrajnego zamówienia w każdym kierunku. Kiedy już
nie ma zamówień w bieżącym kierunku, wtedy głowica zaczyna przesuwać się w
przeciwnym kierunku.
Takie wersje metod planowania SCAN i C-SCAN zwÄ… siÄ™ odpowiednio planowaniem
LOOK ("popatrz", czy istnieje zamówienie, zanim wykonasz ruch w tym kierunku) i
planowaniem C-LOOK
Wybór algorytmu planowania dostępu do dysku
Jak, mając tyle algorytmów planowania dostępu do dysku, wybrać jeden konkretny algorytm?
Planowanie metodą SSTF jest dość powszechne i wygląda dość naturalnie.
Algorytmy planowania SCAN i C-SCAN są odpowiedniejsze w systemach, w których jest
dużo zamówień na operacje dyskowe. Zdefiniowanie algorytmu optymalnego jest możliwe,
ale wielkość obliczeń potrzebnych do planowania optymalnego może nie dać się
usprawiedliwić uzyskanymi oszczędnościami w stosunku do planowania metodami SSTF lub
SCAN.
Zachowanie każdego algorytmu planowania zależy jednak przede wszystkim od liczby i
rodzaju zamówień. Zwłaszcza gdy w kolejce rzadko znajduje się więcej niż jedno nie
obsłużone zamówienie, wówczas wszystkie algorytmy planowania są efektywnie
równoważne. W tym przypadku planowanie metodą FCFS również wydaje się właściwe.
Odnotujmy też, że zamówienia na usługi dyskowe mogą w znacznym stopniu zależeć od
metody przydziału pliku. Program czytający plik przydzielony w sposób ciągły wygeneruje
kilka zamówień odnoszących się do sąsiednich miejsc na dysku, co ograniczy ruch głowic.
Natomiast plik listowy lub indeksowy może zawierać bloki szeroko rozrzucone po dysku, z
lepszym wykorzystaniem miejsca na dysku, lecz z większym wydatkiem na ruch głowicy.
Ważna jest również lokalizacja katalogów i bloków indeksowych. Ponieważ każdy plik
musi być przed użyciem otwarty, a otwarcie pliku wymaga przeszukania struktury katalogu,
więc dostępy do katalogów będą częste.
Umieszczenie katalogów w połowie drogi między wewnętrzną a zewnętrzną krawędzią
dysku, zamiast na którymś z końców, może znacznie zredukować ruchy głowicy. Na
przykład jeśli pozycja w katalogu znajduje się w pierwszym sektorze, a dane pliku są w
ostatnim sektorze, to głowica musi przejść całą szerokość dysku. Jeśli katalog znajdowałby
się bliżej środka, to głowica musiałaby przejść co najwyżej pół tej drogi.
ZarzÄ…dzanie wolnymi obszarami dyskowymi
Ponieważ obszar pamięci na dysku jest ograniczony, jest niezbędne zagospodarowywanie dla
nowych plików przestrzeni po usuniętych plikach. Aby mieć bieżącą informację o wolnych
obszarach dyskowych, system utrzymuje listę wolnych obszarów.
Na liście wolnych obszarów są odnotowane wszystkie bloki, które są wolne (tj. nie
przydzielone do żadnego pliku). W celu utworzenia pliku sprawdza się, czy lista wolnych
obszarów wykazuje wymaganą ilość wolnego miejsca, po czym przydziela się taki obszar
nowemu plikowi.
Tym samym dany obszar zostaje usunięty z listy wolnych obszarów. Przy kasowaniu pliku,
zajmowany przez niego obszar na dysku jest dodawany do listy wolnych obszarów.
Istnieją różne metody przechowywania listy wolnych obszarów.
Wektor bitowy
Lista wolnych obszarów bywa często implementowana w postaci mapy bitowej lub wektora
bitowego. 1
Każdy blok jest reprezentowany przez 1 bit. Jeśli blok jest wolny, to bit ma wartość 0. Jeśli
blok jest przydzielony, to dany bit wynosi 1. Rozważmy na przykład dysk, którego bloki:
2, 3, 4, 5, 8, 9, 10, 11, 12, 13, 17, 18, 25, 26 i 27
są wolne, a pozostałe są przydzielone. Mapa wolnych przestrzeni przyjmie postać :
110000110000001110011111100011111...
Podstawową zaletą takiego podejścia jest to, że umożliwia względnie prosto i szybko
odnajdywać n kolejnych bloków na dysku.
Wiele komputerów ma rozkazy przeznaczone do wykonywania operacji na bitach; można w
tym celu te rozkazy efektywnie zastosować.
1
Rysunki wzięte ze strony http://www.wazniak.mimuw.edu.pl
Zastosowanie wektorów bitowych jest mało wydajne, jeśli nie można przechowywać całego
wektora w pamięci głównej (i zapisuje się go od czasu do czasu na dysku w celach
póz
niejszego odzyskania).
Przechowywanie wektora bitowego w pamięci głównej jest możliwe dla małych dysków,
takich jak stosowane w mikrokomputerach, lecz nie dla dysków wielkich.
Lista powiÄ…zana
Odmiennym podejściem jest powiązanie ze sobą wszystkich wolnych bloków dyskowych i
przechowywanie wskaz
nika do pierwszego wolnego bloku. Blok ten zawiera wskaz
nik do
następnego wolnego bloku itd.
W naszym przykładzie należałoby przechować wskaz
nik do bloku 2, jako do pierwszego
wolnego bloku. Blok 2 powinien zawierać wskaz
nik do bloku 3, który powinien zawierać
wskaz
nik do bloku 4, ten z kolei powinien wskazywać na blok 5, który wskazywałby na blok
8 itd.
Metoda ta nie jest wydajna - aby przejrzeć listę, należy odczytać każdy blok, co wymaga
znacznej ilości czasu.
Grupowanie
Modyfikacją podejścia polegającego na zakładaniu listy wolnych obszarów jest
przechowanie adresów n wolnych bloków w pierwszym wolnym bloku. Pierwsze n - l
adresów (5, 6, 15) wskazuje na wolne bloki.
Ostatni adres (na przedstawionym rysunku 9) jest adresem dyskowym kolejnego bloku
zawierającego adresy następnych n wolnych bloków (11, 16, 17, 18).
Zaletą tej implementacji jest to, że łatwo odnalez
ć adresy wielkiej liczby wolnych bloków.
Zliczanie
W tym rozwiązaniu korzysta się z faktu, że kilka przylegających do siebie bloków można na
ogół przydzielać i zwalniać jednocześnie, zwłaszcza wtedy, gdy stosuje się przydział ciągły.
Toteż zamiast listy n wolnych adresów dyskowych, można przechowywać adres pierwszego
wolnego bloku i liczbę n wolnych bloków następujących nieprzerwanie po pierwszym
bloku. Każda pozycja na liście wolnych obszarów składa się z adresu dyskowego i licznika.
Mimo iż każda pozycja na liście zajmuje więcej miejsca, niż pojedynczy adres dyskowy, cała
lista będzie krótsza, jeśli liczniki będą większe niż 1.
Zadania
1. Załóżmy, że dysk ma 1000 cylindrów, ponumerowanych od 0 do 999. Głowica znajduje się
nad cylindrem nr 68 i domyślnie porusza się w kierunku wzrastających numerów cylindrów.
W systemie oczekują odwołania do cylindrów nr: 14, 336, 285, 79, 562, 193, 402, 205, 351,
24 (zgłoszone w tej kolejności).
Dla strategii szeregowania FCFS, SSTF, SCAN i C-LOOK podaj, jaki będzie łączny dystans
przebyty przez głowice, od aktualnej pozycji, do momentu zrealizowania ostatniego
odwołania.
2. Dysk ma prędkość obrotową 7200 obr/min. Jakie jest średni czas oczekiwania tego dysku?