ćwiczenia 13: System plików - struktura partycji

Linuksowe struktury danych procesu związane z systemem plików

Związek między procesem a systemem plików opisany jest przez dwa pola w strukturze danych procesu (task_struct):

• struct fs_struct *fs zawiera informacje o systemie plików,
• struct files_struct *files zawiera informacje o otwartych przez proces plikach.

W strukturze files_struct znajduje się tablica indeksowana liczbami naturalnymi, które odpowiadają deskryptorom otwartych plików. Wartościami poszczególnych pozycji w tej tablicy są dowiązania do systemowej tablicy otwartych plików.

Systemowa tablica otwartych plików

Każde wywołanie funkcji open() powoduje utworzenie nowej pozycji w systemowej tablicy otwartych plików. Natomiast wywołanie funkcji dup() i fork() powoduje, że do jednej pozycji mogą odnosić się różne deskryptory. Pozycja w systemowej tablicy otwartych plików jest opisana przez strukturę file. Pole f_count tej struktury odpowiada liczbie dowiązań do danej pozycji.

I-węzeł pliku

I-węzeł każdego otwartego pliku znajduje się w pamięci operacyjnej. Dla każdego pliku jest tylko jedna kopia i-węzła w pamięci niezależnie od tego ile razy dany plik był otwierany. Pole i_count w i-węźle informuje ile razy dla danego pliku wykonano funkcję open().

Uwaga: Przedstawiony tutaj opis jest oczywiście niepełny. Zawiera tylko wyrywkowe informacje pomocne przy wykonywaniu poniższych zadań.

Zadanie 1

Załóżmy, że pewien proces, który nie tworzył procesów potomnych, korzysta z n otwartych plików przy czym wszystkie one są różne (odpowiadają im różne i-węzły). Załóżmy również, że ten proces jest jedynym procesem w systemie posiadającym otwarte pliki. Czy jest możliwa sytuacja, w której liczba deskryptorów otwartych plików dla tego procesu jest:

1. mniejsza ostro od n?
2. większa ostro od n?

Jeśli taka sytuacja jest możliwa, to kiedy może wystąpić? Opisz jak można taką sytuację wykryć znając jedynie zbiór obiektów plików file dla danego procesu, a nie wiedząc nic o liczbie deskryptorów plików otwartych przez ten proces.

Rozwiązanie

1. Sytuacja ta jest niemożliwa. Jeśli proces korzysta z jakiegoś pliku, to musi znać jego deskryptor, a jeden deskryptor nie może dotyczyć dwóch różnych plików.
2. Ta sytuacja jest możliwa. Kilka deskryptorów może odnosić się do tego samego obiektu pliku np. po wywołaniu funkcji dup(). Znając jedynie zbiór obiektów plików file wystarczy dla każdego obiektu sprawdzać, czy pole f_count jest ostro większe od 1. Jeśli tak jest, to znaczy, że do danego obiektu pliku istnieje więcej niż jedno odwołanie.

Zadanie 2

Proces P działa według następującego schematu (tablica plik[0..5] zawiera nazwy ścieżkowe plików):

  fd=open(plik[0], ...);
  for i in 1..5 do
  {
      if (!fork()) break;
      fd=open(plik[i], ...);
  }

Jak będą wyglądały tablice deskryptorów plików procesu P i jego potomków?
Jak będzie wyglądała systemowa tablica otwartych plików (jakie wartości będą miały pola f_count)?

Rozwiązanie

Procesy potomne dziedziczą otwarte deskryptory ojca. Pierwszy proces potomny dziedziczy otwarty plik[0]. W momencie tworzenia drugiego procesu otwarte są pliki plik[0] i plik[1] itd.

Tablica deskryptorów procesu ojca:

Tablica deskryptorów pierwszego potomka:

Tablica deskryptorów piątego potomka:

Systemowa tablica otwartych plików:

Zadanie 3

(trudniejszy wariant poprzedniego zadania)

Proces P działa według następującego schematu (tablica plik[0..4] zawiera nazwy ścieżkowe plików):

  fd=open(plik[0], ...);
  for i in 1..4 do
  {
      fd=open(plik[i-1]);
      if (!fork()) break;
      fd=open(plik[i], ...);
      dup(fd);
  }

Ile będzie pozycji odpowiadających plikom: plik[0], ..., plik[4]:

1. w tablicy deskryptorów procesu P,
2. w tablicy otwartych plików,
3. w tablicy i-węzłów?

Jakie będą wartości liczników:

1. f_count w strukturach file odpowiadającym poszczególnym plikom w systemowej tablicy otwartych plików,
2. i_count w i-węzłach tych plików?

Rozwiązanie

Liczba pozycji odpowiadających poszczególnym plikom:

Wartości liczników w tablicy otwartych plików:

Wartości liczników w tablicy i-węzłów:

Struktura partycji w systemach plików ext2/ext3/ext4

W omawianych systemach plików pierwszy blok partycji jest zarezerwowany dla sektora startowego. Reszta partycji jest podzielona na grupy bloków tego samego rozmiaru o ustalonej strukturze. Liczba grup zależy od rozmiaru partycji i od wielkości bloku. Głównym ograniczeniem jest to, że mapa bitowa opisująca stan zajętości bloków wewnątrz grupy musi zmieścić się w jednym bloku.

Rysunek - struktura partycji.

Jak widać na rysunku również mapa bitowa opisująca zajętość i-węzłów oraz superblok zajmują po jednym bloku. Pozostałe struktury są zmiennej długości.

Superblok zawiera informacje o całym systemie plików (m. in rozmiar bloku, łączną liczbę bloków i i-węzłów, łączną liczbę wolnych bloków i i-węzłów). Deskryptor grupy przechowuje podstawowe informacje dotyczące grupy, takie jak liczbę wolnych bloków oraz i-węzłów w danej grupie, numery bloków map bitowych i numer pierwszego bloku tablicy i-węzłów.

Tablica i-węzłów to zbiór bloków, w ramach których przydzielane są i-węzły. Ich liczba jest ustalana podczas tworzenia systemu plików.

Różnice w strukturze partycji pomiędzy kolejnymi wersjami systemu plików od ext2 do ext4 są niewielkie. W oryginalnej wersji systemu ext2, kopia superbloku oraz deskryptory grup znajdowały się w każdej grupie (redundacja miała na celu zabezpieczenie danych przed awarią). W nowszych wersjach wprowadzono możliwość pominięcia kopii w niektórych grupach. Kopie superbloku i deskryptorów grup znajdują się wtedy w grupach o numerach 0, 1 oraz będących potęgą 3, 5 lub 7.

Zauważmy, że dla bardzo dużych partycji taki sposób organizacji staje się nieefektywny, ponieważ zbyt wiele miejsca jest przeznaczone na (redundantne) metadane. Chodzi tutaj przede wszystkim o deskryptory grup, których liczba rośnie wraz z rozmiarem partycji (szczegółowe wyjaśnienie w zadaniu 7). Dlatego w późniejszych wersjach systemu ext3 i w systemie ext4 wprowadzono tak zwane metagrupy. Metagrupa jest zbiorem grup, o tak dobranym rozmiarze, aby deskryptory grup w obrębie jednej metagrupy mieściły się w pojedynczym bloku dyskowym. Deskryptory grup danej metagrupy są przechowywane w jej pierwszej grupie i dodatkowo - w drugiej i w ostatniej.

Zadanie 4

Dla partycji ext2 o wielkości 4 GB rozmiar bloku został ustalony na 4 KB. Załóżmy, że rozmiar deskryptora grupy wynosi 48 B, rozmiar i-węzła na dysku wynosi 128 B, a na grupę przypada 4096 i-węzłów.

1. Jaki jest rozmiar mapy bitowej zajętości bloków?
2. Ile bloków z danymi będzie zawierać każda z grup?
3. Jaki jest rozmiar danych przechowywanych w jednej grupie bloków?
4. Ile grup bloków zostanie utworzonych?
5. Jaki jest koszt obsługi danych, tzn. ile procent przestrzeni dyskowej
   zostanie zużyte na metadane?

Rozwiązanie

1. Mapa bitowa bloków zajmuje 4 KB (mapa bitowa zajmuje zawsze jeden blok).
2. Jedna grupa zawiera 32768 bloków z danymi: 4096 * 8 = 32768
   (rozmiar mapy bitowej razy liczba bitów na bajt).
3. W jednej grupie trzymamy 128 MB danych: 32768 * 4 KB = 128 MB
   (liczba bloków razy rozmiar bloku).
4. Utworzone zostaną 32 grupy bloków: 4 GB / 128 MB = 32
   (rozmiar partycji dzielony przez rozmiar danych trzymany w bloku).
5. Liczymy straty w obrębie jednej grupy bloków:
   • kopia superbloku - 4KB (1 blok)
   • kopia deskryptorów grup - 4 KB (48 B * 32 = 1536 B < 4 KB)
     (rozmiar deskryptora razy liczba grup, zaokrąglone do pełnej liczby bloków)
   • mapa bitowa bloków - 4 KB (1 blok)
   • mapa bitowa i-węzłów - 4 KB (1 blok)
   • tablica i-węzłów - 512 KB (128 B * 4096 = 512 KB)
     (rozmiar i-węzła razy liczba i-węzłów w grupie, zaokrąglone do pełnej liczby bloków)

   W sumie 528 KB, co stanowi 0.4% rozmiaru grupy: 528 KB / 128 MB =0.4% (rozmiar metadanych dzielony przez rozmiar grupy - dane i metadane).

   W obrębie całego dysku straty będą takie same - 0.4% (pomijamy rozmiar bloku startowego).

Zadanie 5

Załóżmy, że w pewnym systemie plików ext2:

• i-węzeł zajmuje 128 bajtów,
• deskryptor grupy zajmuje 32 bajty,
• blok na dysku ma rozmiar 4K bajty,
• partycja dyskowa ma rozmiar 8G bajtów.

Jak należy skonfigurować system plików na tej partycji, żeby metadane nie zajęły więcej niż 2% partycji?

Opisz szczegółowo ile będzie grup dyskowych, ile bloków zajmie jedna grupa, co będzie się znajdowało w kolejnych blokach dyskowych partycji, jakie metadane będą przechowywane w kolejnych (ilu) blokach, ile bloków będzie przypadało średnio na jeden plik. Blok startowy można zaniedbać w rozważaniach.

Rozwiązanie

• Każda mapa bitowa opisuje: 4K * 8 = 32K bloków 4K bajtowych = 128 MB.
• Liczba grup, która zapewnia pełne wykorzystanie bitmapy bloków: 8GB/128MB = 64.
• W jednym bloku o rozmiarze 4KB mieszczą się 4KB/128B = 32 i-węzły. (Pełne wykorzystanie mapy bitowej na i-węzły dałoby 4K * 8 = 32K i-węzłów.)
• Struktura grupy:
  • 1 blok na superblok,
  • 1 blok na deskryptory grup (zmieści się 4 KB/32 = 128 deskryptorów - więcej niż potrzeba),
  • 1 blok na bitmapę bloków,
  • 1 blok na bitmapę i-węzłów.
• Załóżmy, że na i-węzły przeznaczy się x bloków. Meta-dane zajmą następujący procent powierzchni dysku:

  (4+x) * 64 * 4KB /8GB = (4+x)*32 /1M < 0.02
  x < 651.36, czyli np. x=650

  Czyli i-węzłów będzie 650*32=20 800 (w mapie bitowej da się opisać więcej, bo 32K, więc taka konfiguracja jest możliwa)

• Jeśli przeznaczy się 650 bloków na i-węzły, to na dane pozostanie: 8*4096 - (1+1+1+1+650) = 32768 - 654 = 32114 bloków
  Średni rozmiar pliku otrzymamy dzieląc liczbę bloków z danymi przez liczbę i-węzłów. 32114/20800 daje w przybliżeniu 1,5. Zatem na jeden plik przypadać będzie średnio 1,5 bloków z danymi.

Zadanie 6

1. Załóżmy, że blok na dysku ma rozmiar 1024 bajtów. Jaki rozmiar ma grupa?
2. Załóżmy, że grupa bloków ma rozmiar 128 MB. Ile wynosi rozmiar bloku na dysku?
3. Załóżmy, że blok na dysku ma rozmiar 1024 bajty. Grup na dysku jest dokładnie 400. Deskryptor grupy zajmuje 24 bajty. Który bit w mapie bitowej zajętości bloków w grupie zawierającej wszystkie deskryptory grup odpowiada blokowi zawierającemu tę mapę?
4. Dlaczego funkcja kontrolująca spójność mapy bitowej dla każdej z tych map zakończy się błędem?

   0111 1111 1101 1010 0110 ...

   1011 0000 0000 0000 0000 ...

   1101 1111 1111 1111 1111 ...

Rozwiązanie

1. Blok mieści 1024 bajty, czyli mapa bitowa zajętości bloków będzie miała 1024 * 8 bitów, czyli tyle bloków może liczyć grupa. Odp: Grupa będzie miała rozmiar 8 MB.
2. Niech x oznacza rozmiar bloku. 128 MB = x * 8 * x, czyli rozmiar bloku to 4 KB.
3. Grup jest 400, czyli deskryptory grup zajmują 9600 bajtów (400 * 24), czyli 10 bloków. Pierwszy blok w grupie to superblok, czyli jedenaście pierwszych bloków jest zajętych. Wniosek: blok mapy bitowej zajętości bloków odpowiada dwunastemu bitowi w tej mapie (bitowi o numerze 11).
4. 1. Bit odpowiadający superblokowi nie jest zapalony.
   2. Mamy przynajmniej jedną grupę na dysku, czyli istnieje co najmniej jeden deskryptor grupy. Powinien mieć on przydzielony co najmniej jeden blok znajdujący sie bezpośrednio za superblokiem. Tymczasem drugi bit w mapie nie jest zapalony.
   3. Bit odpowiadający superblokowi jest zapalony. Bit odpowiadający pierwszemu i być może ostatniemu blokowi deskryptorów grup jest zapalony. Natomiast dalej mamy dwa przypadki: albo deskryptory zajmują więcej niż jeden blok i wtedy błąd, bo następny bit nie jest zapalony. Z drugiej strony, deskryptory grup mogą mieścić się na jednym bloku, ale wtedy następny blok powinna zajmować mapa bitowa zajętości bloków, a bit jemu odpowiadający nie jest zapalony.

Zadanie 7

Jaki jest maksymalny rozmiar partycji dla systemu plików, w którym pierwsza grupa przechowuje wszystkie deskryptory grup danej partycji. Przyjmijmy, że deskryptor grupy ma rozmiar 64B, a blok dyskowy - 4 KB. Jaki byłby w takiej sytuacji rozmiar metagrupy?

Rozwiązanie

Dla bloku o rozmiarze 4 KB grupa będzie miała rozmiar 8 * 2¹² * 2¹² = 2²⁷, czyli 128 MB.

Zatem w grupie zmieści się nie więcej niż 2²⁷/64 = 2²¹ deskryptorów grup, a więc partycja może mieć rozmiar co najwyżej 2²¹ * 2²⁷ = 2⁴⁸, czyli 256TB (a nawet jeszcze mniej, bo nie wzięliśmy pod uwagę superbloku, map bitowych i tablicy i-węzłów, które znajdują się w każdej grupie).

Wniosek: w przypadku dużych partycji konieczne staje się zastosowanie metagrup. Dla podanych założeń jedna metagrupa zawierałaby 2¹²/64 =64 grupy.