so:wolna_przestrzen

Pytanie: “Metody zarządzania wolną przestrzenią na dysku; omów metodę stosowaną w systemie Linux”

# Wstęp

W zarządzaniu wolną przestrzenia powszechnie wykorzystywane są 4 metody:

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

# Wektor bitowy

Każdy blok dyskowy (jednostka alokacji) jest reprezentowany przez jeden bit w wektorze. Wartość „1” bitu oznacza, że dany blok jest wolny.

Przykład:

# Lista powiązana

Dla listy powiązanej wszystkie wolne bloki są powiązane w taki sposób, że w bloku poprzednim znajduje się indeks bloku następnego. Indeks pierwszego bloku znajduje się w specjalnym miejscu w systemie plików.

Przykład:

# Grupowanie

Pierwszy wolny blok zawiera indeksy n innych wolnych bloków, z których n-1 dotyczy bloków do alokacji przez pliki, a n-ty blok zawiera znowu n kolejnych indeksów kolejnych wolnych bloków.

Przykład:

# Zliczanie

W przypadku kilku kolejnych, przylegających do siebie wolnych bloków pamiętany jest tylko indeks pierwszego z nich oraz liczba wolnych bloków znajdujących się bezpośrednio za nim. Wykaz wolnych obszarów jest ciągiem wpisów , składających się z indeksu bloku oraz licznika.

Przykład:

# Zarządzanie wolną przestrzenia w Linuksie

Przydzielanie wolnych zasobów oraz zarządzanie nimi oparte jest o system plików. Najpowszechniejszymi z nich są systemy ext2, ext3 i na nich się skoncentruję.

System pików Ext2 podzielony jest na bloki o rozmiarze 1024, 2048 lub 4096 bajtów, przy czym pojedynczy blok uważamy za podstawową fizyczną jednostkę objętościową danych. Kolejne bloki połączone są w grupy, których rozmiar zależy od wybranego rozmiaru bloku. Podział na grupy zwiększa lokalność danych związanych z jednym plikiem, a co za tym idzie, przyspiesza dostęp do nich. Grupy zostają ustalone statycznie podczas tworzenia systemu plików.

W skład grupy bloków wchodzą:

- superblok
- tablica deskryptorów grup
- bitmapa bloku
- bitmapa i-węzłów
- tabela i-węzłów
- bloki danych

Optymalny zapis danych jest uzyskiwany poprzez algorytmy przydziału nowych i-węzłów i bloków dyskowych. Podczas przydziału i-węzła plikowi, który jest katalogiem wyszukiwana jest grupa z największą liczbą wolnych i-węzłów. Jeżeli nie jest to katalog to zaczyna się szukać wolnego i-węzła od grupy w której znajduję się i-węzeł katalogu tego pliku. Dzięki temu zwiększa się prawdopodobieństwo, że i-węzły plików z danego katalogu leżą w tej samej grupie a przez to prawdopodobieństwo położenia bloków danych plików z danego katalogu w jednej grupie bloków. Algorytmy przydziału i-węzłów i bloków danych powodują więc ich równomierne rozłożenie w grupach oraz w miarę możliwości spójne położenie bloków danych plików.

## Linki

http://ie.ae.krakow.pl/~kluska3k/index.php?id=4&uid=99c9b05926d9fc736abfd41132bfbad1&PHPSESSID=b629627b4b448c8fb225c408dee070b6