Valid HTML 4.01!

Scenariusz do ćwiczeń 7
Pliki: I-węzeł, algorytm bmap


Ćwiczenie 1

I-węzeł pliku w pewnym systemie uniksowym zawiera numery pierwszych 10 bloków z danymi oraz numery jednego bloku pośredniego, jednego bloku podwójnie pośredniego i jednego bloku potrójnie pośredniego. Pole rozmiaru pliku w i-węźle zajmuje 4 bajty. Rozmiar bloku jest równy 1 KB. Każdy blok pośredni może pomieścić 256 numerów.

Jaki jest maksymalny rozmiar (logiczny) pliku w tym systemie? Ile maksymalnie, a ile minimalnie bloków dyskowych może być potrzebne do zapamiętania takiego pliku?

Uwaga: W Uniksie pliki mogą być "dziurawe"!

Zadanie domowe: Sformułuj treść tego zadania (wskaż właściwe wartości) i rozwiąż je dla Linuksa w wersji 2.4.18.

Zadanie domowe: Sformułuj treść tego zadania (wskaż właściwe wartości) i rozwiąż je dla Linuksa w wersji 2.6.17.

Rozwiązanie

Największy możliwy plik może mieć wielkość 2^32 B = 4 GB, co daje 4 MB bloków z danymi.

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.

Gdyby wszystkie bloki były indeksowane przez pewien blok pośredni, to trzeba by na to 4 MB/256 = 16 K bloków pośrednich, całkowicie wykorzystanych. W istocie ostatni z tych bloków będzie indeksował 256 - 10 = 246 bloków z danymi.

Bloki pośrednie dzielą się na 1 blok samodzielny i 63 * 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 63 bloki indeksowane przez blok potrójnie pośredni (oczywiście niepełny).

Łącznie potrzeba: 4 M bloków z danymi, 16 K bloków pośrednich, 64 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^32-1 (za pomocą operacji lseek()). W tym przypadku trzeba alokować po jednym bloku pośrednim każdego poziomu i jeden na blok (łącznie 3 + 1 = 4).

Rozwiązanie dla Linuksa 2.4.18

W Ext2 12 pierwszych bloków jest adresowanych bezpośrednio. Pole rozmiaru pliku w i-węźle Ext2 to 4 bajty, ale najstarszy bit nie jest wykorzystywany więc maksymalny rozmiar pliku to 2GB (Bovet, Cesati, wydanie drugie, str. 582). Rozmiar bloku dyskowego to 1-4KB (przyjmijmy 1KB). Numer bloku zajmuje 4B.

Maksymalny rozmiar pliku to 2^31=2GB. Maksymalna liczba bloków dyskowych to:

2M/256=8K bloków pośrednich (ostatni blok będzie indeksował 256-12=244 bloków 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).

Bloki podwójnie pośrednie dzielą się na 1 blok samodzielny i 31 bloków indeksowanych przez blok potrójnie pośredni (używane jest 31 pozycji z 256).

Łącznie potrzeba: 2M bloków z danymi, 8K 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 na dane (łącznie 3 + 1 = 4).


Ćwiczenie 2

Plik o rozmiarze logicznym 13000 B został umieszczony na dysku z pewnym uniksowym systemem plików (wielkość bloku 1 KB, liczba pozycji w tablicy indeksowej w i-węźle równa 13).

Zakładając, że bloki są rozmieszczone w sposób losowy policz ile operacji dyskowych wymaga wczytanie bloku logicznego wielkości 1000 B (uwaga: NIE 1 KB) położonego w ramach pliku:

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

Jak będzie odpowiedź dla operacji pisania?

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.

Zadanie domowe: Jaka będzie sformułowane zadanie i jak będzie odpowiedź dla Linuksa w wersji 2.4.18?

Rozwiązanie

Blok o adresie logicznym 6000 jest adresowany przez indeks bezpośredni, leży na granicy bloków o numerach 5 i 6 (przy założeniu, że bloki pliku numerujemy od 0). Trzeba więc wczytać dwa bloki dyskowe z danymi.

Blok o adresie logicznym 12000 jest adresowany przez indeks pojedynczo pośredni. Leży na granicy bloków o numerach 11 i 12. Trzeba więc wczytać dwa bloki dyskowe z danymi i jeden blok indeksowy pojedynczo pośredni.

W przypadku operacji pisania, jeśli zapisujemy niepełny blok, to najpierw trzeba go wczytać, a dopiero wówczas można modyfikować. Zatem w pierwszym przypadku będą to cztery operacje (dwa odczyty i dwa zapisy), a w przypadku drugim pięć operacji (dwa odczyty, dwa zapisy i odczyt bloku pojedynczo pośredniego). Gdyby był to pierwszy zapis do któregokolwiek z bloków o numerach 11 i 12, to jeszcze doszedłby zapis bloku pojedynczo pośredniego (bo trzeba by przydzielić bloki fizyczne na te bloki logiczne i wstawić ich adresy do bloku indeksowego).

Rozwiązanie ćwiczenia nr 2 dla Linuksa 2.4.18

W Ext2 liczba pozycji w i-węźle przeznaczonych do indeksowania bloków dyskowych to 12 + 3. Przyjmijmy rozmiar bloku 1KB.

Czytanie od adresu logicznego 6000: indeksowanie bezpośrednie, czytamy 2 bloki dyskowe (o numerach 5 i 6).

Czytanie od adresu logicznego 12000: potrzebne dane są w blokach o numerach 11 (adresowany bezpośrednio) i 12 (pierwszy blok adresowany pośrednio). Trzeba wczytać jeden blok pośredni i 2 bloki z danymi.

Pisanie 1000B od adresu logicznego 6000: czytamy 2 bloki i zapisujemy te 2 bloki.

Pisanie 1000B od adresu 12000: czytamy blok pośredni i 2 bloki z danymi, zapisujemy te 2 bloki (plus ewentualny zapis bloku pojedynczo pośredniego, jeśli jest to pierwszy zapis do bloku o numerze 12).


Ćwiczenie 3

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, blok fizyczny poprzedzający na dysku pierwszy blok pliku jest zajęty, a blok fizyczny położony za ostatnim blokiem pliku jest wolny. Ile operacji dyskowych wymaga:

  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

alokacja ciągła alokacja listowa alokacja indeksowa
201=100+100+111
101=50+50+152=50+1+11
1102=100+1+11
198=99+99 ew. 010
98=49+4952=50+1+10
01000

Ćwiczenie 4

UWAGA:
Treścią zadania jest implementacja algorytmu bmap, który tłumaczy logiczny numer bloku w pliku na fizyczny numer bloku na dysku, w systemie plików ext2. Przedstawione rozwiązanie różni się w sposobie zapisu od kodu funkcji w wersji jądra 2.6.17, ale zasada przeliczania numeru bloku jest taka sama.

Zaimplementować funkcję:


DEFINICJA: int ext2_bmap(struct inode *inode, int block)
    PARAMETRY: wskaźnik do i-węzła pliku, 
               logiczny numer bloku w pliku
    WYNIK: fizyczny numer bloku na dysku w przypadku sukcesu
           0, gdy nie znaleziono bloku

Zadanie domowe: Przeanalizować kod źródłowy implementujący algorytm bmap w Linuksie 2.6.17.

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:

Rozwiązanie

Warto wprowadzić dwie zmienne pomocnicze:

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 ext2_bmap():

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

Implementacja funkcji ext2_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 < addr_per_block)
   {
      /* 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 -= addr_per_block;

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/addr_per_block (część całkowita
         ilorazu */

      i = block_bmap(bread(inode->i_dev,i), 
                     block >> addr_per_block_bits);

      if (i == 0) return 0;

      /* W bloku o numerze i, na pozycji (block mod addr_per_block)
         znajduje się szukany adres bloku */

      return block_bmap(bread(inode->i_dev,i), block & (addr_per_block - 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 addr_per_block */

   i = block_bmap( bread(inode->i_dev,i), 
                   block >> (addr_per_block_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 addr_per_block, 
      a następnie z tego wyniku resztę modulo addr_per_block */

   i = block_bmap( bread(inode->i_dev,i), 
       (block >> addr_per_block_bits) & (addr_per_block - 1) );

   if (i == 0) return 0;

   /* Teraz w bloku i na pozycji block mod addr_per_block znajduje
      się szukany adres bloku */

   return block_bmap(bread(inode->i_dev,i), block & (addr_per_block - 1))
}

WNIOSKI:
Konwersja bajtu o wysokim numerze, korzystająca z bloków pośrednich 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 ext2_bmap). Algorytm jest optymalny dla systemu z niewielkimi plikami (np. nie korzystającymi z bloków podwójnego i potrójnego pośredniego - dla tych bloków konwersja adresu jest najkosztowniejsza).


Janina Mincer-Daszkiewicz