Sop_09_wyk_1.0.pdf

Systemy Operacyjne

System plików – warstwa fizyczna

Systemy operacyjne

System plików —warstwa fizyczna

Wykład prowadzą:

Jerzy Brzeziński

Dariusz Wawrzyniak

System plików —warstwa fizyczna

Celem wykładu jest prezentacja różnych podejść do implementacji systemu

plików. Podejścia opierają się na założeniu, że urządzeniem składowania danych

jest dysk i dotyczą one przede wszystkim organizacji przestrzeni dyskowej.

Podkreślane są wady i zalety tych podejść w kontekście różnych form dostępu do

danych w plikach.

Systemy Operacyjne

System plików – warstwa fizyczna

Systemy operacyjne

Plan wykładu

• Przydziałmiejsca na dysku

• Zarządzanie wolnąprzestrzenią

• Implementacja katalogu

• Przechowywanie podręczne

• Integralnośćsystemu plików

• Semantyka spójności

System plików —warstwa fizyczna (2)

Zasadniczą kwestią, przedstawianą w ramach wykładu, jest organizacja

przestrzeni dyskowej, obejmująca powiązanie pliku z blokami dyskowymi oraz

zarządzanie blokami wolnymi. Poruszona jest też implementacja katalogu. W

kolejnej części omawiany jest sposób realizacji operacji plikowych oraz

wynikający z tego problem integralności danych. Na koniec zasygnalizowana jest

problematyka współbieżnego dostępu do pliku.

Systemy Operacyjne

System plików – warstwa fizyczna

Systemy operacyjne

Organizacja fizyczna systemu plików

• Przydziałmiejsca na dysku

– przydziałciągły, przydziałlistowy, przydział

indeksowy

• Zarządzanie wolnąprzestrzenią

– wektor bitowy, lista powiązana, grupowanie, zliczanie

• Implementacja katalogu

– lista liniowa, tablica haszowa, struktura indeksowa

System plików —warstwa fizyczna (3)

Przestrzeń dyskowa na potrzeby systemu plików zorganizowana jest w jednostki

alokacji, zwane krótko blokami. Blok jest wielokrotnością sektora dysku.

W zakresie przydziału miejsca dla pliku na dysku, czyli powiązania bloków z

plikiem, omówione są trzy podejścia: przydział ciągły, listowy i indeksowy, przy

czym ten ostatni wymaga dodatkowo określenia sposobu powiązania bloków

indeksowych. Podejściem opartym na idei przydziału listowego jest tablica

alokacji plików (FAT).

Wolna przestrzeń jest dopełnieniem przestrzeni przydzielonej dla plików w

ramach danej strefy dysku. Jednak efektywna identyfikacja wolnych bloków na

potrzeby tworzenia nowych plików lub rozszerzania istniejących wymaga

utrzymywania komplementarnej informacji. Wyróżnia się cztery rodzaje takich

struktur: wektor bitowy, lista powiązana, grupowanie, zliczanie, przy czym idee

niektórych podejść można łączyć.

Dla katalogu przydzielane są bloki tak, jak dla innych plików dyskowych. Jest to

zatem również plik, ale jego struktura jest odpowiednio definiowana przez

system. Specyficzne są również operacje dostępu. W przypadku niewielkiej

liczby wpisów katalog może być zwykłą listą (czy tablicą). Czas wyszukiwania

zależy wówczas liniowo do liczby wpisów, co staje się nie akceptowalne w

przypadku rozrastających się katalogów. Dla dużych katalogów lepiej jest

zastosować jakąś strukturę przyspieszającą wyszukiwanie informacji, np. B/B + -

drzewo lub tablicę haszową.

Systemy Operacyjne

System plików – warstwa fizyczna

Systemy operacyjne

Przydziałmiejsca na dysku

• Przydziałciągły (ang. contiguous allocation) —cały plik

zajmuje ciąg kolejnych bloków

• Przydziałlistowy (łańcuchowy, ang. linked allocation,

chained allocation) —bloki pliku tworząlistępowiązaną

• Przydziałindeksowy (ang. indexed allocation) —bloki z

danymi wskazywane sąprzez bloki indeksowe, które

mogąbyćzorganizowane w:

– schemat listowy

– schemat wielopoziomowy

– schemat kombinowany

System plików —warstwa fizyczna (4)

Przydział ciągły oznacza, że zawartość pliku umieszczona jest w kolejnych

według jakieś jednoznacznej numeracji blokach (jednostkach alokacji).

Numeracja związana jest z fizycznym położeniem bloku na urządzeniu.

W przydziale listowym poszczególne bloki powiązane są wskaźnikami. W

przypadku listy jednokierunkowej w każdym bloku przechowywany jest

wskaźnik (czyli numer, indeks) bloku następnego. Dzięki temu zawartości pliku

może być rozmieszczona w blokach, dowolnie rozproszonych w dostępnej

przestrzeni dyskowej.

W przydziale indeksowym numery bloków dyskowych z danymi skupione są w

jednym miejscu, w tzw. bloku indeksowym. Jeśli jeden blok indeksowy jest zbyt

mały, żeby pomieścić numery wszystkich bloków z danymi, tworzone są kolejne

bloki indeksowe i organizowane w schemat listowy, wielopoziomowy lub

kombinowany.

Systemy Operacyjne

System plików – warstwa fizyczna

Systemy operacyjne

Przydziałciągły

Katalog:

7 blok początkowy: 1

rozmiar: 10 bloków

blok początkowy: 13

rozmiar: 11 bloków

blok początkowy: 27

rozmiar: 9 bloków

System plików —warstwa fizyczna (5)

W przedstawionym przykładzie przydziału ciągłego atrybut lokalizacja pliku

implementowany jest za pomocą dwóch wartości: numeru (indeksu) pierwszego

bloku oraz liczby bloków, która wynika z rozmiaru pliku. Pierwszy plik (zielony)

zajmuje więc 10 bloków począwszy od bloku 1, drugi plik (czerwony) zajmuje

11 bloków począwszy od bloku nr 13 (czyli do 23 włącznie), a trzeci plik (żółty)

zajmuje 9 bloków od bloku nr 27.

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: