Zarządzanie pamięcią
zewnętrzną
(pomocniczą)
Systemy operacyjne -
wykład 7
Zarządzanie pamięcią
zewnętrzną
(pomocniczą)
Systemy operacyjne -
wykład 7
Zarządzanie wolnymi
obszarami dyskowymi
Informacja o wolnych obszarach jest przechowywana w
tworzonej przez S.O. liście wolnych obszarów. Przykłady
implementacji listy:
-
wektor bitowy (mapa bitowa)
- każdy blok reprezentowany
jest przez 1 bit (gdy blok jest wolny bit=0),
-
lista powiązana
(powiązanie wszystkich wolnych bloków
dyskowych i przechowywanie wskaźnika do pierwszego
wolnego bloku),
-
grupowanie
- przechowywanie adresów n wolnych bloków
w pierwszym wolnym bloku (pierwsze n-1 adresów
wskazuje na wolne bloki, ostatni adres jest adresem
dyskowym innego bloku zawierającego adresy następnych
n wolnych bloków),
-
zliczanie
- przechowywany jest adres pierwszego wolnego
bloku i liczba n wolnych bloków następujących
nieprzerwanie po pierwszym bloku.
Powiązana lista wolnych
obszarów na dysku
Metody przydziału miejsca
na dysku
Wybór odpowiedniej metody przydziału
ma na celu efektywne
zagospodarowanie miejsca na dysku i
szybki dostęp do plików.
Metody przydziału miejsca
na dysku cd
Przydział ciągły
Każdy plik musi zajmować ciąg
kolejnych adresów na dysku. Daje to
łatwy dostęp do plików.
Wady: trudno znaleźć miejsce na nowy
plik, ponadto trzeba dla tworzonego
pliku z góry określić wielkość
potrzebnego dla niego obszaru.
Przydział ciągły miejsca na
dysku
Metody przydziału miejsca
na dysku cd
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 wskaźnik do pierwszego i
ostatniego bloku pliku. Każdy blok zawiera
wskaźnik do następnego bloku. Wskaźniki te nie są
dostępne dla użytkownika.
Tworzenie pliku polega na tworzeniu nowej pozycji w
katalogu urządzenia.
Wada: taka realizacja daje efekty przy zastosowaniu
do plików o dostępie sekwencyjnym. Realizacja
dostępu bezpośredniego w plikach o przydziale
listowym jest niewydajna; dużo miejsca na dysku
zajmują wskaźniki.
Przydział listowy miejsca na
dysku
0
1 10 2
3
4
5
6
7
8
9 16 10 25 11
12
13
14
15
16 1 17
18
19
20
21
22
23
24
25 -1 26
27
28
29
30
31
Rys. Przydział listowy miejsca na dysku.
Katalog
Plik
Początek Koniec
dane
9
25
FAT
Odmianą metody przydziału listowego jest tablica
przydziału plików (file alocation table). Na dysku
wydziela się sekcję, która będzie zawierała tablicę.
Tablica ma po jednej pozycji dla każdego bloku
dyskowego i jest indeksowana za pomocą numerów
bloków. Tablicy tej używa się podobnie jak listy
powiązań.
Katalog zawiera numer pierwszego bloku pliku.
Pozycja w tablicy indeksowana przez numer tego
bloku zawiera numer następnego bloku w pliku.
(Przykład - S.O. DOS)
Tablica przydziału plików
Pozycja w katalogu
nazwa blok początkowy
Liczba bloków dyskowych
-1
0
217
618
339
symbol
końca pliku
618
339
test
...
217
Metody przydziału miejsca
na dysku cd
Przydział indeksowy
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ę wskaźnika z pozycji o
numerze i w bloku indeksowym, za pomocą którego
znajduje się odpowiedni blok do czytania. Przydział
indeksowy umożliwia dostęp bezpośredni.
Wada: Przydział indeksowy powoduje marnowanie
miejsca na dysku. Nakład na wskaźniki bloku
indeksowego jest na ogół większy niż nakład na
wskaźniki przy przydziale listowym.
Przydział indeksowy miejsca
na dysku
Metody przydziału miejsca
na dysku cd
Odmiany przydziału indeksowego
a) schemat listowy - blok indeksowy znajduje się w jednym bloku
dyskowym, a dla wielkich plików - stosuje się połączenie kilku
bloków indeksowych.
b) indeks wielopoziomowy - oddzielny blok indeksowy służy do
wskazywania bloków indeksowych, których wskaźniki wskazują
na bloki pliku.
c) schemat kombinowany (BSD Unix)
W katalogu urządzenia przechowuje się pierwsze 15 wskaźników
bloku indeksowego. Pierwsze 12 wskazuje na bloki
bezpośrednie tzn. zawierające wprost adresy bloków z danymi
pliku. Dla małych plików jest to wystarczające.
Następne trzy wskaźniki wskazują bloki pośrednie. Pierwszy
wskaźnik bloku pośredniego jest adresem bloku jednokrotnie
pośredniego. Kolejnym jest wskaźnik bloku dwukrotnie
pośredniego (który zawiera adres bloku zawierającego adresy
bloków, które zawierają wskaźniki do faktycznych bloków
danych). Ostatni wskaźnik będzie zawierać adres bloku
trzykrotnie pośredniego.
Planowanie dostępu do
dysku
Planowanie wykonywania zamówień na
dostęp do dysku ma na celu uzyskanie
szybkich usług dyskowych.
Łączny czas obsługi zamówienia dyskowego
jest sumą czasów:
przeszukiwania (dotarcie do odpowiedniej
ścieżki na dysku),
oczekiwania (dotarcie do odpowiedniego
bloku na ścieżce),
przesyłania (właściwe przesyłanie danych
między dyskiem a pamięcią główną).
Planowanie dostępu do
dysku cd.
Metody planowania dostępu do dysku:
FCFS - pierwszy nadszedł-pierwszy obsłużony (długi
średni czas obsługi).
SSTF - najpierw najkrótszy czas przeszukiwania
(shortest seek-time-first). Wybieranie zamówienia z
minimalnym czasem przeszukiwania względem
bieżącej pozycji głowicy.
SCAN - głowica startuje od jednego końca dysku do
przeciwległego i z powrotem, obsługując po drodze
zamówienia.
C-SCAN - jw. z natychmiastowym powrotem na
początek.
LOOK i C-LOOK - modyfikacje SCAN i C-SCAN. Gdy brak
zamówień w bieżącym kierunku, głowica zaczyna
przesuwać się w przeciwnym.
Najpowszechniej stosowane SSTF.