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.