//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__:

{{:so:wektor_bitowy.png|:so:wektor_bitowy.png}}

====== 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__:

{{:so:lista_powiazana.png|:so:lista_powiazana.png}}

====== 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__:

{{:so:grupowanie.png|:so:grupowanie.png}}

====== 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__:

{{:so:zliczanie.png|:so:zliczanie.png}}

====== 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


{{http://mars.iti.pk.edu.pl/~mlynco/ext2.png|http://mars.iti.pk.edu.pl/~mlynco/ext2.png}}


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