1
1
SYSTEMY
SYSTEMY
PLIKOWE
PLIKOWE
2
Agenda
Koncepcja systemu plików
Struktura systemu plików
Metody alokacji pami ci pomocniczej
Zarz dzanie wolnymi obszarami
Kontrola dost pu
Implementacja katalogów
Odtwarzanie
2
3
Przechowywanie danych
Pami główna: zwykle za mała, ulotna
Pami pomocnicza: słu y do trwałego przechowywania
du ych ilo ci danych
No niki: ta ma, dysk magnetyczny, dysk optyczny
msExchServersContainer4
msExchStorageGroup
4
Podstawowe poj cia (1)
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
dysku
Cylinder: zbiór wszystkich cie ek le cych w tej samej
odległo ci od osi obrotu dysku na dysku w wieloma
talerzami
3
5
Podstawowe poj cia (2)
Czas przeszukiwania (ang. seek time): czas przesuni cia
głowicy na wła ciw cie k (nast pnie 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
6
Dyski (1)
Disk parameters for the original IBM PC floppy disk and a
Western Digital WD 18300 hard disk
4
7
Dyski (2)
8
Dyski (2)
Fizyczne parametry geometrii dysku o dwóch strefach
Mo liwe parametry logiczne dla tego dysku
5
9
Urz dzenia wielokrotne - RAID
(Redundant Array of Inexpensive Disks )
RAID poziomu od 0 do 2.
RAID 0 - dane rozmieszczone na dyskach poł czonych w
przestrze ci gł . Brak kontroli bł dów.
Najlepsza przepustowo danych w ród systemów RAID.
Przezroczysty dla oprogramowania.
Brak kontroli bł dów i redundancji. Uszkodzenie jednego dysku w
macierzy powoduje utrat wszystkich danych w całej macierzy.
Wszystkie parametry MTBF koniecznie trzeba przeliczy ponownie.
RAID 1 - lustrzane kopie dysków.
Brak przestojów w zapisie. 100% redundancja dysku. Uszkodzenie
nie obni a wydajno ci.
Wymaga podwojonej przestrzeni dyskowej i energii w porównaniu
do systemu bez macierzy.
RAID 2 – redundancja z zastosowaniem kodów Hamming
10
Macierze dyskowe (1)
6
11
RAID 0 (brak redundancji)
12
RAID 1 (lustrzane kopie)
7
13
RAID 2 (redundancja z kodowaniem
Hamminga)
14
Macierze dyskowe (2)
RAID poziomu od 3 do 6.
RAID 3 – parzysto z przeplotem bitów
RAID 4 – parzysto na poziomie bloków
RAID 5 - sektorowe rozmieszczenie pasmowe danych i informacji o
parzysto ci.
Dobra wydajno przy systemach przetwarzaj cych transakcje. Brak
nadwy ki zapisu jak w RAID 4. Nadwy ka przestrzeni dyskowej nie
przekracza jednego dysku. Mo liwy równoległy odczyt w całej macierzy.
Spadek wydajno ci przy rekonstrukcji danych.
RAID 6 - macierz RAID 0 z kopi lustrzan .
Przepustowo danych porównywalna do RAID-0. 100% redundancja
danych. Nie ma spadku wydajno ci po uszkodzeniu.
Wymaga dwukrotnie wi kszej przestrzeni dyskowej i zasilania w
porównaniu do systemu bez macierzy.
8
15
Macierze RAID (2)
16
RAID 3 (parzysto z przeplotem bitów)
9
17
RAID 4 (parzysto na poziomie bloków)
18
RAID 5 (rozproszona parzysto na
poziomie bloków)
10
19
RAID 6 (redundancja dualna)
20
Formatowanie dysku (1)
Sektor dysku (ECC -
E
rror
C
orrection
C
ode (
E
rror
C
hecking and
C
orrection) )
11
21
Formatowanie dysku (2)
Ilustracja odchyle w wielko ci cylindrów
22
Formatowanie dysku (3)
Bez przeplotu
Pojedynczy przeplot
Podwójny przeplot
12
23
Hierarchia danych
Od najmniejszych do najwi kszych
Bit (cyfra binarna)
1 lub 0
Wszystko w komputerze i tak w rezultacie reprezentowane jest jako ci g
bitów
Niedogodne w u yciu przez człowieka
Zbiór znaków
– Cyfry, litery, symbole stosowane do przedstawienia danych
– Ka dy znak reprezentowany jets jako ci g 1 i 0
Bajt: 8 bitów
Mo e przechowywa znak
24
Hierarchia danych
Od najmniejszych do najwi kszych (cd.)
Pole: grupa znaków o pewnym znaczeniu
Twoje imi
Rekord: grupa pól
struct
lub class in C++
W systemie płacowym mo e to by np.. Nazwisko, identyfikator, adres,
płaca
Ka de pole zwi zane jest z tym samym pracownikiem
Klucz rekordu: pole stosowane do jednoznacznej identyfikacji pola
Plik: grupa powi zanych rekordów
System płacowy dla całej firmy
Zbiór sekewncyjny: rekordy przechowywane wg klucza
Baza dancyh: grupa powi zanych plików
Płace, numery kont, bilans, itp.
13
25
Hierarchia danych
1
01001010
Judy
Judy
Green
Sally
Black
Tom
Blue
Judy
Green
Iris
Orange
Randy Red
Plik
Rekord
Pole
Bajt (znak J w kodzie ASCII)
26
Struktura systemu plikowego
Struktura pliku:
Logiczna jednostka pami ci przechowywania danych
Kolekcja powi zanych danych
System plikowy znajduje si w pami ci pomocniczej (dysku).
Dysk mo e by zapisywany wielokrotnie
Mo liwy jest bezpo redni dost p do dowolnego bloku informacji na
dysku
Dysk podzielony jest na bloki (32 - 4096 bajty; zwykle 512)
System plikowy ma struktur warstwow .
Blok kontrolny pliku – przechowuje struktur zawieraj c informacje
o pliku.
14
27
Organizacja systemu pliku
System plików dostarcza efektywnego i wygodnego sposobu
dost pu do dysku.
Jak system plikowy postrzegany jest przez u ytkownika?
Definicja pliku, jego atrybutów, dopuszczalnych operacji, struktury
katalogu
W jaki sposób logiczny system plikowy jest odwzorowywany w
fizyczn struktur urz dze pomocniczych.
Jakie s stosowane algorytmy i struktury danych?
28
Struktura pliku
Trzy rodzaje plików
ci g bajtów
ci g rekordów
drzewo
15
29
Typy plików
(a) Plik wykonywalny (b) Archiwum
30
Tryby dost pu do pliku
Dost p sekwencyjny
wymaga odczytu wszystkie bajty/rekordy od pocz tku pliku
nie mo na przeskakiwa z powrotem, nale y przewin lub wrócic
do pocz tku
wygodny wtedy, gdy nosnikiem były tasmy magnetyczne
Dost p swobodny (ang. random access)
odczyt bajtu/rekordu w dowolnym porz dku
istotny w przypadku systemów bazodanowych
odczyt mo e nast powa …
po przemieszczeniu markera pliku (przeszukiwanie), nastepnie odczyt
lub …
odczyt i dopiero przemieszczenie markra pliku
16
31
Atrybuty pliku (mo liwe)
32
Implementacja systemu plikowego -
przykład
17
33
Projektowanie warstwowe
Oprogramowanie aplikacyjne
Logiczny system plikowy
Moduły organizacji pliku
Podstawowy system plikowy
Kontrola I/O
Urz dzenia
34
Oprogramowanie aplikacyjne
Logiczny system plikowy
Moduły organizacji pliku
Podstawowy system plikowy
Kontrola I/O
Urz dzenia
Projektowanie warstwowe
18
35
Projektowanie warstwowe
Kontrola I/O
Sterowniki urz dze i program obsługi przerwa
Przesyła do urz dzenia specyficzne dla niego instrukcje
niskopoziomowe
Zapisuje charakterystyczne wzorce steruj ce urz dzeniem w okre lone
miejsce pami ci kontrolera I/O
Przesyła informacje pomi dzy pami ci a systemem dyskowym
36
Projektowanie warstwowe
Oprogramowanie aplikacyjne
Logiczny system plikowy
Moduły organizacji pliku
Podstawowy system plikowy
Kontrola I/O
Urz dzenia
19
37
Projektowanie warstwowe
Podstawowy system plikowy
Dostarcza polece ogólnego przeznaczenia, które wysyłane do
odpowiedniego sterownika urz dzenia pozwalaj na odczyt i zapis
fizycznych bloków z/na dysk.
Ka dy fizyczny blok identyfikowany jest za pomoc jego
numerycznego adresu dyskowego
Adres dyskowy: nr nap du, nr powierzchni, nr cie ki (cylindra), nr
sektora (np. nap d-sterownik 1, cylinder 73, cie ka 2, sektor 10)
38
Projektowanie warstwowe
Oprogramowanie aplikacyjne
Logiczny system plikowy
Moduły organizacji pliku
Podstawowy system plikowy
Kontrola I/O
Urz dzenia
20
39
Projektowanie warstwowe
Moduły organizacji pliku
Posiada informacje o plikach oraz ich blokach logicznych i
fizycznych
Transluje adresy bloków logicznych w adresy bloków fizycznych
Bloki logiczne s numerowane od 0 do N; bloki fizyczne nie pokrywaj
si z numerami logicznymi.
Przesyła adresy fizyczne do podstawowego systemu plikowego
Ten moduł zawiera tak e mened era wolnej przestrzeni
ledzi niezaalokowane bloki i dostarcza te bloki modułowi organizacji
pliku
40
Projektowanie warstwowe
Oprogramowanie aplikacyjne
Logiczny system plikowy
Moduły organizacji pliku
Podstawowy system plikowy
Kontrola I/O
Urz dzenia
21
41
Projektowanie warstwowe
Logiczny system plikowy
Zna format struktury katalogowej
Tworzy nowe pliki
Czyta i umieszcza wła ciwy katalog w pami ci
Aktualizuje jego zawarto o nowe zapisy
Zapisuje z powrotem na dysku
42
Projektowanie warstwowe
Logiczny system plikowy
Unix traktuje katalog tak samo jak ka dy inny plik
Posiada pole typu wskazuj ce, e plik jest katalogiem
Logiczny system plikowy musi tłumaczy odwołania do katalogu na
odwołania do no nika przechowuj cego plik.
W Windows NT/2000/XP zaimplementowano oddzielne odwołania
do plików i katalogów
Katalogi s traktowane jako elementy inny ni (oddzielne) pliki
Logiczny system plikowy mo e nast pnie wywoływa moduł
organizacji pliku i odwzorowywa katalogowe operacje I/O na adresy
bloków dyskowych
22
43
Projektowanie warstwowe
Logiczny system plikowy
dla ka dej operacji I/O mo e
poszukiwa struktury blokowej
sprawdza parametry operacji
wykona operacj
niezb dny do otwierania pliku i zapisywania odpowiedniej informacji
kopiuje informacje o pliku do tabeli w pami ci
Informacja ta nazywana jest tabel otwartych plików lub
tabel deskryptorów
pliku
gdy plik jest otwarty,
przeszukuje katalog
kopiuje informacje o katalogu i inne informacje do tabeli
zwraca indeks pliku w tabeli
indeks ten jest
deskryptorem pliku (Unix) lub uchwytem pliku (Windows XP)
lub
blokiem kontrolnym pliku (inne systemy operacyjne).
44
Projektowanie warstwowe
Logiczny system plikowy
Niektóre systemy operacyjne posiadaj dwupoziomowe systemy
plików (np. Unix)
ka dy wpis w tabeli na poziomie ka dego procesu wskazuje na globaln
systemow tabel otwartych plików.
Globalna tabela systemowa zawiera informacje, które s niezale ne od
procesu
– lokalizacj pliku na dysku
– czas dost pu,
– wielko plikiu, etc.
Je li plik jest otwarty przez dwa niezale ne procesy, to
– nowy proces dodaje wpis do swojej tabeli deskryptorów
– wskazuje na wła ciwy wpis w globalnej tabeli plików
– tabela otwartych plików zwi ksza licznik dowi za do otwartego pliku.
23
45
Dwupoziomowy system plików
Proces
Kernel
Dysk
46
Montowanie systemu plików
W systemie Unix, przed u yciem system plików musi zosta
zamontowany.
Procedura:
systemowi operacyjnego przekazywana jest nazwa nap du i miejsce
w strukturze pliku, w którym nale y podpi system plikowy (
punkt
montowania)
Przykład: punktem montowania u ytkowników systemu Linux jest
katalog /home
System operacyjne sprawdza czy urz dzenie zawiera wła ciwy
system plikowy.
odpytuje sterownik urz dzenia i odczytuje katalog urz dzenia
sprawdza czy katalog ma oczekiwany format
System operacyjny odnotowuje w swojej strukturze katalogowej, e
system plików został zamontowany w punkcie montowania.
24
47
Metody alokacji pami ci na dysku
Na jednym dysku mo e by zapisanych wiele plików.
dyski pozwalaj na dost p bezpo redni – pliki mo na zapisywa
gdziekolwiek na dysku
Problem: jak alokowa miejsce dla tych plików
przestrze dyskowa musi by zarz dzana efektywnie
dost p do pliku musi by szybki
Istniej trzy główne metody alokacji (przydziału) przestrzeni
dyskowej
alokacja ci gła
alokacja listowa
alokacja indeksowa.
48
Alokacja ci gła
Ka dy plik zajmuje ci gły obszar na dysku.
Prostota – niezb dna jest znajmo jedynie lokalizacja
pocz tkowego bloku (blok #) i długo pliku (liczba
bloków).
dost p do bloku
b + 1 bezpo rednio po bloku b nie wymaga zwykle
adnego ruchu głowicy
je li konieczne jest przemieszczenie głowicy, to tylko o jedna
cie k .
st d liczba przeszukiwa dysku jest minimalna.
Stosowana w systemach IBM VM/CMS ze wzgl du na jej
dobre własno ci
Alokacja pliku wymaga zdefiniowania adresu dyskowego
i długo ci (w blokach).
25
49
Alokacja ci gła
Opis pliku w katalogu wskazuje adres bloku pocz tkowego
oraz długo obszaru przydzielonego plikowi.
2
6
f
4
28
list
6
19
3
14
tr
2
0
count
długo
start
Plik
50
Alokacja ci gła
Prosta implementacja dost pu sekwencyjnego i bezpo redniego
Dost p swobodny
aby odwoła si do j-tego bloku pliku, który rozpoczyna si od adresu b,
nale y poda adres b + j
Marnotrawienie pami ci (problem z dynamiczn alokacj pami ci).
problem podobny do problemu alokacji pami ci o ustalonej wielko ci
trudno znale miejsce na nowy plik (strategie: pierwszy pasuj cy, najlepszy
pasuj cy)
fragmentacja zewn trzna – niezb dna okresowa kompresja
Pliki nie mog zwi ksza wielko ci.
Alokowana przestrze okre lana jest w momencie tworzenia pliku.
Zaalokujemy wi cej ni potrzeba: fragmentacja wewn trzna
Zaalokujemy za mało: kosztowne rozszerzenie pliku.
Cz sto alokowana w porcjach nazywanych obszarami.
26
51
Alokacja ci gła
Odwzorowanie adresu logicznego (LA) w fizyczny:
Udost pniany blok = Q + adres pocz tkowy
Przemieszczenie w obr bie bloku = R
LA/512
Q
R
52
Alokacja ci gła (przed kompresj )
27
53
Alokacja ci gła (po kompresji)
54
Alokacja listowa
Ka dy plik jest list powi zanych bloków dyskowych: bloki
mog by rozrzucone po całym dysku.
wska nik do
pierwszego bloku
katalog
=
wska nik do
ostatniego bloku
wska nik do
nast pnego bloku
blok =
28
55
Alokacja listowa
56
Alokacja listowa (przed kompresj )
29
57
Alokacja listowa (po kompresji)
58
Alokacja listowa
Tworzenie nowego pliku
Tworzenie nowego wpisu w katalogu
Nie jest wymagane deklarowanie rozmiaru pliku w momencie jego
definiowania
Inicjowanie pierwszego/ostatniego bloku na NULL
Brak fragmentacji zewn trznej
Zastosowany mo e by dowolny blok z listy bloków
wolnych
Pliki mog rozrasta si do dowolnych rozmiarów
(oczywi cie w ramach dost pnej przestrzeni dyskowej).
Nie jest wymagana kompresja.
30
59
Alokacja listowa
Brak dost pu swobodnego
aby znale j-ty wpis nale y rozpocz o pocz tku pliku i i w lad za
wska nikami
ka dy dost p wymaga odczytu dysku, czasami przeszukiwania dysku.
Wska niki zabieraj miejsce: je li wska nik jest 4 bajtowy, a blok ma
rozmiar 512 bajtów, to starta wynosi 0.78% pojemno ci dysku.
Rozwi zanie:
gromadzi bloki w ich wielokrotno nazywan
klastrami.
alokowa raczej klaster ni bloki.
wska niki zabieraj teraz procentowo znacznie mniej przestrzeni dyskowej
zwi ksza si fragmentacja wewn trzna
klastry polepszaj czas dost p do dysku tak e w przypadku innych
rozwi za (algorytmów dost pu); stosowane w wi kszo ci OS.
60
Alokacja listowa
Problem: niezawodno . Co zdarzy si w przypadku, gdy
utracony zostanie wska nik?
mo na stosowa podwójne listy, ale jest to kosztowne
Odwzorowanie (jeden bajt na wska nik)
dany blok jest Q-tym blokiem w powi zanej li cie
bloków, reprezentuj cych blok.
Przemieszczenie w bloku = R + 1
LA/511
Q
R
31
61
Alokacja listowa
Tablica alokacji pliku (ang. file-allocation table, FAT) –
zaalokowana przestrze dyskowa stosowana w systemach
MS-DOS i OS/2.
Sekcja dysku na pocz tku ka dej partycji dysku jest rezerwowana na
tabel
FAT wykorzystuje struktury listy
Wpis w katalogu zawiera numer pierwszego bloku pliku.
Wpis w tabeli indeksowanej przez ten numer bloku zawiera numer
nast pnego numeru bloku.
Ten ci g kontynuowany jest a do ostatniego bloku pliku
ostatni blok ma specjalny znacznik ko ca pliku (EOF).
Nieu ywane bloki maj wpisane 0 w tabeli.
62
Alokacja listowa
Przykład FAT: plik składa si z
bloków dyskowych numer 217,
618 i 339
217
…
test
339
end-of-
file
618
wpis w katalogu
nazwa
blok pocz.
217
618
339
0
-1
32
63
Alokacja listowa
Aby zaalokowa nowy blok: znajd pierwszy wpis w tabeli o warto ci 0
zast p poprzedni warto EOF adresem nowego bloku
zast p 0 w nowym bloku warto ci EOF.
FAT mo e powodowa wiele przemieszcze głowicy dysku
w celu odczytu FAT głowica dysku musi przemie ci si do pocz tku
partycji i odszuka miejsce potrzebnego bloku
nast pnie głowica przemieszcza si do poło enia samego bloku.
najgorszy przypadek: oba ruchy wyst puj dla ka dego odczytu/zapisu bloku
rozwi zanie: FAT w pami ci podr cznej
FAT jest dobrym rozwi zaniem w przypadku dost pu swobodnego
korzystaj c z FAT głowica dysku mo e odszuka lokalizacj dowolnego
bloku dyskowego.
64
Alokacja indeksowa
Problem z alokacja listow : wska niki s rozrzucone
wsz dzie
Alokacja indeksowa ł czy wszystkie wska niki w jeden
blok indeksów.
Ka dy plik ma własny blok indeksów: tablica adresów
boków dyskowych
j-ty wpis wskazuje na j-ty blok pliku
katalog zawiera adres bloku indeksów
Widok:
Tabela indeksów
33
65
Przykład alokacji indeksowej
66
Alokacja indeksowa z przydziałem
blokowym
34
67
Alokacja indeksowa z przydziałem
o zmiennej długo ci
68
Alokacja indeksowa
Pozwala na dost p swobodny
Dynamiczny dost p bez fragmentacji zewn trznej, ale wymaga
globalnego bloku indeksów
nale y zawsze alokowa cały blok indeksów nawet je li potrzebny jest tylko
przydział jednego bloku
Blok zajmuje rednio wi cej ni w przypadku alokacji listowej
Problem: jak du y powinien by blok indeksów?
Odwzorowanie z adresów logicznych w fizyczne w pliku o
maksymalnym rozmiarze 256K słów i bloku o rozmiarze 512 słów.
Potrzebny jest tylko jeden blok na tabel indeksów.
Q = przemieszczenie w tablicy indeksów
R = przemieszczenie w bloku
LA/512
Q
R
35
69
Alokacja indeksowa – odwzorowanie
Odwzorowanie z adresów logicznych w fizyczne w pliku o
nieograniczonej długo ci (rozmiar bloku 512 słów).
Schemat listowy
– ł czenie bloków tabeli indeksów (brak
ograniczenia na rozmiar). Ostatni blok indeksu jest wska nikiem
na nast pny blok indeksu.
LA / (512 x 511)
Q
1
R
1
Q
1
= blok tabeli indeksów
R
1
ma posta :
R
1
/ 512
Q
2
R
2
Q
2
= przemieszczenie w bloku tabeli indeksów
R
2
przemieszczenie w bloku pliku.
70
Alokacja indeksowa – odwzorowanie
Indeks dwupoziomowy
(maksymalny rozmiar pliku 512
3
).
Pierwszy poziom bloku indeksów wskazuje na zbiór bloków
indeksów drugiego poziomu. Wskazuj one bloki plików.
LA / (512 x 512)
Q
1
R
1
Q
1
= przemieszczenie w zewn trznym indeksie
R
1
ma posta :
R
1
/ 512
Q
2
R
2
Q
2
= przemieszczenie w bloku tabeli indeksów
R
2
przemieszczenie w bloku pliku.
36
71
Alokacja indeksowa – odwzorowanie
Indeks wielopoziomowy
(maksymalna wielko pliku
wynosi 512
x
).
Podobny jak w przypadku do tabeli stron.
Mo e posiada tyle poziomów ile tylko potrzeba.
72
Alokacja indeksowa – odwzorowanie
Indeks zewn trzny
Tabela indeksów
Plik
37
73
Alokacja indeksowa – schemat ł czony
Schemat ł czony (BSD Unix).
Przechowuje 15 pierwszych wska ników bloku indeksów w bloku indeksów
pliku (i-w le)
Pierwszych 12 indeksów wskazuje na bezpo rednio na bloki.
Niedu e pliki nie potrzebuj wi c oddzielnych bloków indeksów.
Je li wielko bloku wynosi 4K, wtedy bezpo rednio mo na adresowa pliki o
rozmiarze do 48K.
Nast pne 3 wska niki wskazuj na bloki po rednio
Wska nik pierwszego bloku po redniego jest adresem pojedynczego bloku
po redniego
Blok ten jest blokiem indeksów, zawieraj cym adresy bloków, które zawieraj
dane.
Drugi blok po redni jest podwójnym po rednim blokiem wska ników
Zawiera adresy bloku, który zawiera adresy bloków, które zawieraj wska niki
na aktualne bloki danych.
Ostatni wska nik zawiera adres potrójnego bloku po redniego.
Liczba bloków, która mo e by przydzielona do pliku przekracza wielko
obszaru adresowalnego za pomoc 32 bitów.
74
Schemat ł czony: UNIX (4KB na blok)
38
75
Zarz dzanie plikami w systemie UNIX
Typy plików
zwykły (regularny)
katalog
specjalny (urz dzenia)
nazwany (ł cze nazwane)
76
System plików Windows 2000
Główne cechy NTFS
Odtwarzalno
Bezpiecze stwo
Du e dyski i du e pliki
Wiele strumieni danych
Udogodnienia wynikaj ce z indeksowania plików
39
77
System plików Windows 2000
78
Zarz dzanie obszarami wolnymi
Bloki musz by u ywane wielokrotnie.
OS musi zarz dza list wolnych bloków dyskowych
Aby utworzy plik, OS musi przeszuka list wolnych
obszarów dyskowych i wybra odpowiednia liczb wolnych
bloków
Problem: jak zarz dza taka list ?
40
79
Zarz dzanie obszarami wolnymi
Mapa bitowa (n bloków). Ka dy bit reprezentuje blok.
…
0 1
2
n-1
bit[
i
] =
0
blok[
i
] wolny
1
blok[
i
] zaj ty
Intel (pocz wszy od 80380 i Motorola (pocz wszy
starting with 68020) posiadaj specjalne instrukcje
na poziomie j zyka wewn trznego, które zwracaj
offsest w słowach do pierwszego bitu o warto ci 1.
80
Zarz dzanie obszarami wolnymi
Wymaga ochrony:
Wska nik do listy wolnych bloków
Mapa bitowa
Musi by przechowywana na dysku
Kopia w pami ci i oryginał na dysku mog si ró ni .
OS nie mo e dopu ci do sytuacji, gdy bit[i] = 1 w pami ci
i bit[i] = 0 na dysku.
Rozwi zanie:
Ustaw bit[i] = 1 na dysku.
Przydziel blok[i]
Ustaw bit[i] = 1 w pami ci.
41
81
Zarz dzanie obszarami wolnymi
Mapa bitowa wymaga dodatkowego obszaru pami ci.
Przykład:
Rozmiar bloku = 2
12
bajtów
Rozmiar dysku = 2
30
bytes (1 gigabajt)
n = 2
30
/2
12
= 2
18
bitów (lub 32KB)
Mo na łatwo przydzieli mapie bitowej ci gły obszar
plikowy
Lista wi zana (lista wolnych bloków)
Ka dy wolny blok zawiera wska nik do nast pnego wolnego bloku
Mało wydajna - aby przejrze list , trzeba odczyta ka dy blok
FAT posiada wbudowan list wolnych bloków w przydzielon mu
struktur alokacji.