Informatyka MIMUW

Zadanie 1

Rozważmy plik złożony ze 100 bloków. Załóżmy, że struktury danych opisujące położenie pliku na dysku są w pamięci operacyjnej. Przyjmijmy także, że blok fizyczny poprzedzający pierwszy blok pliku na dysku jest zajęty, a blok fizyczny położony za ostatnim blokiem pliku jest wolny. Ile operacji dyskowych wymaga:

1. dodanie bloku na początku
2. dodanie bloku w środku (za blokiem o numerze logicznym 50)
3. dodanie bloku na końcu
4. usunięcie pierwszego bloku
5. usunięcie środkowego bloku (o numerze logicznym 51)
6. usunięcie ostatniego bloku

1. przy alokacji ciągłej (plik zajmuje spójny obszar dysku)?
2. przy alokacji listowej (bloki pliku są powiązane w listę liniową)?
3. przy alokacji indeksowej (numery bloków pliku są pamiętane w bloku
   indeksowym, ew. w kilku blokach)?

Rozwiązanie

Zadanie 2

I-węzeł pliku w systemach ext2 i ext3 zawiera numery pierwszych 12 bloków z danymi oraz numery jednego bloku pośredniego, jednego bloku podwójnie pośredniego i jednego bloku potrójnie pośredniego (tablica i-block).

Plik o rozmiarze logicznym 15000 B został umieszczony na partycji, dla której rozmiar bloku ustalono na 1 KB.
Policz ile operacji dyskowych wymaga:

1. wczytanie
2. zapisanie

fragmentu pliku o wielkości 1000 B (uwaga: nie 1 KB) położonego:

1. począwszy od adresu logicznego 6000,
2. począwszy od adresu logicznego 14000.

W obu przypadkach plik jest otwarty, ale żaden blok danych nie został jeszcze sprowadzony do pamięci. W pamięci znajduje się jedynie i-węzeł pliku. Możemy założyć, że wszystkie bloki pliku są zapisane (plik nie jest dziurawy).

Jak zmienią się odpowiedzi bez ostatniego założenia?
W jakiej sytuacji uzyskamy najmniejszą liczbę operacji dyskowych?

Rozwiązanie

1. 1. Blok o adresie logicznym 6000 jest adresowany przez indeks bezpośredni, leży w blokach o numerach 5 i 6 (przy założeniu, że bloki pliku numerujemy od 0). Trzeba więc wczytać 2 bloki dyskowe z danymi.
   2. Blok o adresie logicznym 14000 jest adresowany przez indeks pojedynczo pośredni. Leży w blokach o numerach 13 i 14. Trzeba więc wczytać 1 blok indeksowy pojedynczo pośredni i 2 bloki dyskowe z danymi, czyli łącznie wykonać 3 operacje dyskowe.
2. 1. W przypadku operacji pisania, jeśli zapisujemy niepełny blok, to najpierw trzeba go wczytać, a dopiero wówczas można modyfikować. Zatem będą to 4 operacje (2 odczyty i 2 zapisy).
   2. Aby zapisać blok o adresie logicznym 14000 potrzebujemy 5 operacji (odczyt bloku pojedynczo pośredniego, 2 odczyty i 2 zapisy bloków z danymi).

Gdyby był to pierwszy zapis do bloku o numerze 14 (na przykład w sytuacji, gdy dopisywane jest 1000B na końcu pliku), to jeszcze doszedłby zapis bloku pojedynczo pośredniego, bo trzeba by przydzielić blok fizyczny na ten blok logiczny i wstawić jego adres do bloku indeksowego. Nie potrzeba natomiast odczytywać wcześniej bloku o numerze 14, więc liczba operacji dyskowych również wyniosłaby 5 (2 odczyty i 3 zapisy).

Najmniejsza liczba operacji odczytu i zapisu będzie w sytuacji, w której dokonujemy pierwszego zapisu do obydwu bloków i nie został jeszcze przydzielony blok z adresami pośrednimi (tylko 3 operacje zapisu). W tej sytuacji trzeba jednak przydzielić 3 nowe bloki dyskowe.

Zadanie 3

Załóżmy, że rozmiar bloku w systemie plików ext3 został ustalony na 1KB. Ile maksymalnie, a ile minimalnie bloków dyskowych może być potrzebne do zapamiętania pliku o rozmiarze 2GB?

Wskazówka: Pliki mogą być rozrzedzone (dziurawe).

Rozwiązanie

Przypadek maksymalnej liczby bloków dyskowych odpowiada np. plikowi całkowicie zapisanemu. Dla takiego pliku trzeba alokować wszystkie bloki z danymi, a więc także wszystkie bloki indeksowe.

Plik ma rozmiar 2 GB, co daje 2GB /1KB = 2M bloków z danymi.

Każdy blok pośredni może pomieścić 1024/4=256 numerów bloków.

Gdyby wszystkie bloki były indeksowane przez bloki pośrednie, to potrzeba na to 2M /256 = 8 K bloków pośrednich. Ponieważ adresy pierwszych 12 bloków znajdują się w i-węźle ostatni z tych bloków będzie indeksował 256 - 12 = 244 bloki z danymi.

Bloki pośrednie dzielą się na 1 blok samodzielny i 31 * 256 + 255 bloków indeksowanych przez bloki podwójnie pośrednie (ostatni niepełny). Te ostatnie z kolei dzielą się na 1 blok samodzielny i 31 bloków indeksowanych przez blok potrójnie pośredni (oczywiście niepełny).

Łącznie potrzeba: 2 M bloków z danymi, 8 K bloków pośrednich, 32 bloki podwójnie pośrednie i 1 blok potrójnie pośredni.

Przypadek minimalnej liczby bloków dyskowych odpowiada np. plikowi, który powstał przez zapisanie jednego bajtu pod adresem 2^31-1 (za pomocą operacji lseek()). W tym przypadku trzeba alokować po jednym bloku pośrednim każdego poziomu i jeden na blok danych (łącznie 3 + 1 = 4 bloki).

Zadanie 4

Kiedy rozmiar pliku w i-węźle systemu ext2 był opisywany liczbą 32-bitową i jej najstarszy bit był zarezerwowany, plik mógł mieć wielkość co najwyżej 2GB. We współczesnych systemach ext2 i ext3 32-bitowe pole i-węzła o nazwie i-blocks przechowuje rozmiar pliku wyrażony w liczbie 512 bajtowych porcji. Rozmiar bloków na dysku zależy od konfiguracji. Dopuszczalne są bloki o wielkości 512 B, 1KB, 2KB, 4KB, a nawet 8KB (o ile architektura na to pozwala). Numery bloków fizycznych są 32-bitowe.

Wiedząc to wszystko i biorąc pod uwagę sposób adresowania bloków uzupełnij poniższą tabelkę dla systemów ext2/3:

Rozwiązanie

Maksymalny rozmiar pliku jest ograniczony przez:
min(((b/4)³ + (b/4)² + b/4 + 12)*b, 2⁴¹),
gdzie b jest rozmiarem bloku.

Pierwsza część ograniczenia wynika ze sposobu adresowania, czyli maksymalnej liczby bloków jaką możemy zaadresować mając
3 poziomowe indeksowanie.

Druga część to ograniczenie wynikające z 32-bitowej postaci i-blocks oznaczającej liczbę 512 bajtowych porcji pliku:
2³² * 2⁹ = 2⁴¹, czyli 2TB.

Dla b=2¹⁰ maksymalny rozmiar pliku to
min(((2⁸)³ + ...) * 2¹⁰, 2⁴¹)= w przybliżeniu 2³⁴

Dla b=2¹¹ maksymalny rozmiar pliku
to min(((2⁹)³ + ...) * 2¹¹, 2⁴¹)= w przybliżeniu 2³⁸

Dla b=2¹² maksymalny rozmiar pliku
to min(((2¹⁰)³ + ...) * 2¹², 2⁴¹) =2⁴¹

Maksymalny rozmiar partycji jest zdeterminowany przez 32-bitowe numery bloków na dysku. Na przykład dla bloku o rozmiarze 1 KB:
2³² * 2¹⁰=2⁴², czyli partycja może mieć wielkość co najwyżej 4 TB.

Zadanie 5

Napisz funkcję int bmap(struct inode *inode, int block), która tłumaczy logiczny numer bloku w pliku na fizyczny numer bloku na dysku, w systemach plików ext2/3.
Dane: wskaźnik do i-węzła pliku i logiczny numer bloku w pliku.
Wynik: fizyczny numer bloku na dysku w przypadku sukcesu lub 0, gdy nie znaleziono bloku.

Załóżmy, że są dostępne następujące makrodefinicje:

#define EXT2_BLOCK_SIZE       4096
#define EXT2_NDIR_BLOCKS      12
#define EXT2_IND_BLOCK        EXT2_NDIR_BLOCKS
#define EXT2_DIND_BLOCK       (EXT2_IND_BLOCK + 1)
#define EXT2_TIND_BLOCK       (EXT2_DIND_BLOCK + 1)
#define EXT2_N_BLOCKS         (EXT2_TIND_BLOCK + 1)

Ponadto można założyć, że są dostępne następujące funkcje pomocnicze:

• inode_bmap(inode, nr)

  Jest to makro, które przekazuje numer bloku zapisany na pozycji nr w tablicy bloków pliku w i-węźle wskazywanym przez inode. Parametr nr powinien zatem należeć do przedziału [0..EXT2_N_BLOCKS-1] (czyli [0..14]). Makro to jest używane przy pobieraniu adresu fizycznego jednego z bloków bezpośrednich, bloku pojedynczego, podwójnego bądź potrójnego pośredniego.

• struct buffer_head * bread(kdev_t dev, int i)

  Funkcja ta przekazuje wskaźnik do nagłówka bufora, do którego wczytano blok o numerze fizycznym i z urządzenia dev.

• int block_bmap(struct buffer_head *bh, int nr)

  Funkcja ta przekazuje liczbę zapisaną w bloku z bufora o nagłówku bh, w komórce o numerze nr. Po odczytaniu zwalnia bufor (wykonując brelse()). Jest używana przy odczytywaniu adresów w blokach pojedynczych, podwójnych i potrójnych pośrednich.

Rozwiązanie

Warto wprowadzić dwie zmienne pomocnicze:

• N

  Jej wartością jest stale liczba adresów mieszczących się w bloku (czyli rozmiar_bloku/rozmiar_adresu).

• N_bits

  Jej wartością jest stale logarytm przy podstawie 2 z wartości zmiennej N. Zmienna ta jest wykorzystywana przy wykonywaniu różnych operacji na bitach.

Przy przekształcaniu adresów zachodzi potrzeba obliczenia liczby bloków, które mieszczą się w poszczególnych strefach pośredniości. Oto jak radzi sobie z tym problemem algorytm bmap():

• liczba bloków bezpośrednich = EXT2_NDIR_BLOCKS
• liczba bloków dostępnych poprzez blok pojedynczy pośredni = N
• liczba bloków dostępnych poprzez blok podwójny pośredni =
  1 << (N_bits*2) (czyli wartość zmiennej N do kwadratu)

• liczba bloków dostępnych poprzez blok potrójny pośredni =
  (1 << (N_bits * 2)) << N_bits
  (czyli wartość zmiennej N do potęgi trzeciej)

Maksymalna liczba bloków dająca się zaadresować w i-węźle jest sumą wymienionych czterech liczb.

Implementacja funkcji bmap():

{
   /* Sprawdz czy parametr wywołania, block, jest poprawny */
 
   if (block < 0) return 0; /* Nie znaleziono bloku */
   if (block >= maksymalna liczba bloków możliwa do zaadresowania 
      w i-węźle) return 0;
 
   /* Numer block jest poprawny; dalsze działanie zależy od 
      poziomu pośredniości, w którym znajduje się block */
 
DIR: 
   /* Poziom bezpośredni */
 
   /* Blok jest w poziomie bezpośrednim, gdy jego numer jest 
      mniejszy od liczby blokow bezpośrednich */
 
   if (block < EXT2_NDIR_BLOCKS) return inode_bmap(inode,block);
 
   /* Blok jest w strefach pośrednich;pomijamy bloki bezpośrednie*/
   block -= EXT2_NDIR_BLOCKS;
 
IND:
   /* Pierwszy poziom pośredniości */
 
   /* Blok jest w pierwszym poziomie pośredniości, gdy zmienna 
      block w tej chwili jest mniejsza od liczby bloków 
      dostępnych poprzez pojedynczy blok pośredni */
 
   if (block < N)
   {
      /* Pobierz numer bloku pojedynczego pośredniego */
 
      i = inode_bmap(inode, EXT2_IND_BLOCK);
 
      if (i == 0) return 0;
 
      /* Wczytaj blok o numerze i ( bread(inode->i_dev, i) ),
         a nastepnie przekaż go jako pierwszy argument 
         do funkcji pomocniczej block_bmap */
 
      return block_bmap( bread(inode->i_dev, i), block );
   }
 
   /* Blok jest w poziomie pośredniości wyższym od pierwszego;
      pomijamy bloki w pierwszym poziomie pośredniości */
 
   block -= N;
 
DIND:
   /* Drugi poziom pośredniości */
 
   if (block < liczba bloków dostępnych poprzez blok 
                  podwójny pośredni)
   {
      /* Blok jest w drugim poziomie pośredniości */
      /* Pobierz numer bloku podwójnego pośredniego */
 
      i = inode_bmap(inode, EXT2_DIND_BLOCK);
 
      if (i == 0) return 0;
 
      /* Pobierz numer bloku pojedynczego pośredniego,
         w którym znajduje się szukany blok; ten blok pojedynczy
         pośredni ma numer block/N (część całkowita
         ilorazu */
 
      i = block_bmap(bread(inode->i_dev,i), block >> N_bits);
 
      if (i == 0) return 0;
 
      /* W bloku o numerze i, na pozycji (block mod N)
         znajduje się szukany adres bloku */
 
      return block_bmap(bread(inode->i_dev,i), block & (N - 1));
   }
   /* Pomijamy bloki w strefie drugiej pośredniości */
 
   block -= liczba bloków dostępnych poprzez podwójny blok pośredni;
 
TIND:
   /* Trzeci poziom pośredniości */
   /* Pobierz numer bloku potrójnego pośredniego */
 
   i = inode_bmap(inode, EXT2_TIND_BLOCK);
 
   if (i == 0) return 0;
 
   /* Pobierz numer bloku podwójnego pośredniego, w którym  znajduje się szukany blok; 
       ten blok podwójny pośredni ma numer równy całości z dzielenia liczby block przez 
       kwadrat liczby N */
 
   i = block_bmap( bread(inode->i_dev, i), block >> (N_bits * 2));
 
   if (i == 0) return 0;
 
   /* Z bloku i pobierz numer bloku pojedynczego pośredniego, w 
      którym znajduje się szukany blok; ten numer można otrzymać 
      biorąc część całkowitą z ilorazu block przez N, 
      a następnie z tego wyniku resztę modulo N */
 
   i = block_bmap( bread(inode->i_dev,i), (block >> N_bits) & (N - 1) );
 
   if (i == 0) return 0;
 
   /* Teraz w bloku i na pozycji block mod N znajduje
      się szukany adres bloku */
 
   return block_bmap(bread(inode->i_dev, i), block & (N - 1))
}

Jak widać ten klasyczny w świecie uniksowym sposób adresowania jest dobrze przystosowany do niewielkich plików lub plików rozrzedzonych. Jego zastosowanie w przypadku dużych plików wiąże się ze wzrastającymi nakładami. Konwersja numeru bloku o wysokim numerze, korzystająca z bloków
pośrednich (zwłaszcza podwójnie i potrójnie) jest dosyć kosztowna, wymaga od jądra kilku dostępów do bloków dyskowych (to może prowadzić do oczekiwania w stanie uśpienia podczas wykonania funkcji bmap).

System plików ext4

Nasuwa się wniosek, że system plików ext3 dochodzi do granic swoich możliwości. Maksymalna wielkość partycji, czyli 16 TB (ew. 32 TB) jest już często przekraczana (np. w macierzach RAID), a ze względu na 32-bitowe numery bloków dyskowych więcej osiągnąć się nie da. Od 2006 roku trwają prace nad dwoma zasadniczymi zmianami dla ext3 dostępnymi w postaci łat a także obecnymi w jego następcy, czyli w systemie ext4.

Pierwsza i najważniejsza zmiana polega na zwiększeniu wielkości numeru bloku do 48 bitów, a druga na zamianie mechanizmu pośredniego adresowania bloków na tzw. ekstenty (ang. extent), czyli ciągłe zbiory (zakresy) bloków danych.

struct ext4_extent {
        __le32  ee_block;       /* first logical block extent covers */
        __le16  ee_len;         /* number of blocks covered by extent */
        __le16  ee_start_hi;    /* high 16 bits of physical block */
        __le32  ee_start_lo;    /* low 32 bits of physical block */
};

Pojedynczy ekstent opisuje:

• 32-bitowy numer bloku logicznego pliku, który jest początkiem zakresu
• 15-bitową długość zakresu (najstarszy bit służy do określenia czy zestaw jest zapisany, czy nie),
• 48-bitowy numer bloku na dysku, który jest początkiem zakresu na dysku.

W strukturze i-węzła tablica i-block, która w systemach ext2/3 jest wykorzystywana do zapisywania numerów bloków, w ext4 służy do zapisania czterech ekstentów i jednego nagłówka ekstentu. W przypadku dużych plików system ext4 tworzy drzewo ekstentów. Dodatkowa struktura - indeks ekstentu - zawiera pozycję początkową ekstentu w pliku i numer bloku na dysku. Mechanizm ekstentów jest obecny także w innych popularnych systemach plików m. in w XFS, JFS, Reiser4, a nawet w NTFS.

Zadanie 6

Wiedząc, że w systemie ext4 numery logiczne bloków są 32-bitowe, a numery fizyczne bloków są 48 bitowe wypełnij tabelkę jak w zadaniu 3 dla rozmiaru bloku: 1, 2 i 4 KB.

Rozwiązanie

2³² * 2¹⁰ = 2⁴²
2³² * 2¹¹ = 2⁴³
2³² * 2¹² = 2⁴⁴
2⁴⁸ * 2¹⁰ = 2⁵⁸
2⁴⁸ * 2¹¹ = 2⁵⁹
2⁴⁸ * 2¹² = 2⁶⁰

Zadanie 7

Ustalmy, że rozmiar bloku wynosi 4KB. Porównaj, ile bloków dyskowych jest potrzebne do zapamiętania pełnego pliku (bez dziur) o rozmiarze 512MB w systemie ext3 i ext4.

Rozwiązanie

ext3:
Plik ma rozmiar 512 MB, co daje 512 MB/ 4 KB = 128 K bloków z danymi.

Każdy blok pośredni może pomieścić 4096/4=1024 numery bloków.

Gdyby wszystkie bloki były indeksowane przez pewien blok pośredni, to trzeba by na to 128 K/ 1024 = 128 bloków pośrednich. W rzeczywistości potrzeba 128 bloków pośrednich z tym, że ostatni jest niepełny i zawiera 1024 - 12 = 1012 numerów bloków z danymi. Ze 128 bloków pośrednich jeden jest wskazywany w i-węźle, a adresy pozostałych 127 bloków znajdują się w bloku podwójnie pośrednim.

Do przechowywania pliku wielkości 512MB potrzeba zatem 128 K bloków z danymi, 128 bloków pośrednich i 1 blok podwójnie pośredni. Oprócz bloków z danymi potrzeba dodatkowo 129 bloków, czyli 128 * 4KB + 4KB = 516KB.

ext4:

Jak poprzednio: 128 K bloków z danymi i w optymistycznej sytuacji (jeżeli plik nie jest pofragmentowany) nic więcej.

Za pomocą jednego ekstentu można zaadresować maksymalnie 2¹⁵ * 4 KB = 128 MB danych, a zatem 4 ekstenty mieszczące się w i-węźle adresują cały plik.