Scenariusz do ćwiczeń 8
Pliki: struktury danych, system plików ext2

Ćwiczenie 1

Załóżmy, że mamy w systemie jeden proces. Korzysta on z n otwartych plików przy czym wszystkie one są różne (odpowiadają im różne i-węzły). Czy jest możliwa sytuacja, że liczba deskryptorów otwartych plików dla procesu (liczba jedynek w mapie bitowej files->open_fds) jest:

• mniejsza ostro od n?
• większa ostro od n?

Jeśli taka sytuacja jest możliwa, to opisz 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 otwartych plików dla procesu (sytuacja wysoce hipotetyczna; zakładamy, że w momencie wykrywania na obiektach plików nie są wykonywane żadne funkcje systemowe).

Rozwiązanie

• Sytuacja ta jest niemożliwa. Jeśli proces korzysta z jakiegoś pliku, to musi znać jego deskryptor, czyli indeks w tablicy wskaźników do obiektów pliku (jeden deskryptor nie może dotyczyć dwóch różnych plików).

• Ta sytuacja jest możliwa. Kilka deskryptorów może odnosić się do tego samego obiektu pliku. Sytuacja taka może wystąpić np. po użyciu wywołań systemowych takich jak dup(). Znając jedynie zbiór obiektów plików file wystarczy dla każdego obiektu sprawdzać, czy pole file->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, co przy podanych warunkach implikuje, ze zachodzi opisana sytuacja.

  Tak jest oczywiscie przy założeniu, że nasz jedyny proces nie wykona fork().

Ćwiczenie 2

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

Jak będzie wyglądała tablica deskryptorów plików i tablica plików dla procesu P i jego potomków? W szczególności jakie wartości będą miały pola file->f_count?

Rozwiązanie

Dzieci dziedziczą deskryptory ojca.

Ćwiczenie 2b (trudniejszy wariant ćwiczenia 2, egz. 2002/03)

Opisz przeznaczenie pola tt count w strukturze files_struct, pola f_count w strukturze file i pola i_count w strukturze inode.

Dany jest proces P, który działa wg następującego kodu (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] w tablicy deskryptorów procesu P, tablicy otwartych plików i tablicy i-węzłów (ponumeruj te pozycje i posługuj się tymi numerami w dalszej części odpowiedzi)?

Jakie będą wartości wymienionych liczników w tablicy deskryptorów procesu P, w tablicy otwartych plików na pozycjach odpowiadających plikom plik[0], ..., plik[4] i w i-węzłach plików plik[0], ..., plik[4]?

Przedstaw odpowiedź na rysunku ilustrującym opisane struktury.

Rozwiązanie

Liczba pozycji:

Wartości liczników:

• Tablica deskryptorów: 1
• Tablica otwartych plików: 5, 5, 8, 4, 6, 3, 4, 2, 2
• Tablica i-węzłów: 2, 2, 2, 2, 1

Ćwiczenie 3

Dla partycji ext2 wielkości 4 GB ustalamy rozmiar bloku równy 4 KB. Zakładamy, ż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. Ile kopii superbloku będzie przechowywanych na partycji?
6. 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 div 128 MB = 32 (rozmiar partycji dzielony przez rozmiar danych trzymany w bloku)
5. Bedą przechowywane 32 kopie superbloku (po jednej w każdej grupie).
6. 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 div 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, tzn. zakładamy że dysk nie jest bootowalny)

Ćwiczenie 3b (wariant ćwiczenia 3, egz. 2002/03)

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

1. i-węzeł zajmuje 128 bajtów,
2. deskryptor grupy zajmuje 32 bajty,
3. blok na dysku ma rozmiar 4K bajty,
4. 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 systemowy (bootblock) 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 4KB mieszczą się 4KB/128B = 32 i-węzły. (Pełne wykorzystanie mapy bitowej na i-węzły daje nam 4K * 8 = 32K i-węzłów, czyli zajmą one 32K/32=1024 bloki.)
• Struktura grupy:
  1. 1 blok na superblok,
  2. 1 blok na deskryptory grup (zmieści się 4 KB / 32 = 128 deskryptorów - więcej niż potrzeba),
  3. 1 blok na bitmapę bloków,
  4. 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 grupy] * 4KB/8GB = (4+x)*32/1M < 2%=2/100
       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 4K*8=32K)

• Jeśli przeznaczy się 1024 bloki na i-węzły, to na pliki pozostają:

   32*1024 - (1+1+1+1+1024) = (31*1024 - 4) bloki.

  Czyli średni rozmiar pliku: (31*1024-4)/8*4*1024 = 1 blok na plik!

Ćwiczenie 4

Mamy partycję ext2 zawierającą 32 bloki. Zakładamy że w pamięci podręcznej superbloku trzymamy 8 map bitowych (standardowo). Jak będzie się zmieniała zawartość pamięci podręcznej map bitowych przy założeniu że:

• Na początku jest pusta.
• Ma miejsce ciąg odwołań do następujących map bitowych:

  
  1, 2, 2, 10, 22, 1, 2, 5, 9, 1, 12, 31, 2, 1, 5, 8, 10, 22
  

Ile razy przy powyższym ciągu trzeba będzie odczytać mapę bitową z dysku?

Rozwiązanie

Zwykły algorytm LRU, przy pamięci podręcznej z buforami na 8 map bitowych. Oto zawartość pamięci podręcznej w kolejnych krokach (+ oznacza ściąganie bitmapy z dysku):

	+1
	+2 1
	2 1
	+10 2 1
	+22 10 2 1
	1 22 10 2
	2 1 22 10
	+5 2 1 22 10
	+9 5 2 1 22 10
	1 9 5 2 22 10
	+12 1 9 5 2 22 10
	+31 12 1 9 5 2 22 10
	2 31 12 1 9 5 22 10
	1 2 31 12 9 5 22 10
	5 1 2 31 12 9 22 10
	+8 5 1 2 31 12 9 22 
	+10 8 5 1 2 31 12 9 
	+22 10 8 5 1 2 31 12 

Miało miejsce 11 operacji ściągania mapy bitowej z dysku.

Ćwiczenie 5

Przypuśćmy, że mamy 10 grup w systemie plików ext2 oraz przydzielamy algorytmem ialloc i-węzeł dla pliku w katalogu /tmp. I-węzeł tego katalogu znajduje się w grupie 6. Zakładając, że w grupie nr 0 jest 195 wolnych i-węzłów, a w każdej z pozostałych grup jest dokładnie jeden wolny i-węzeł, podaj numer grupy, w której zostanie zaalokowany i-węzeł dla tego pliku.

Rozwiązanie

Będzie to grupa katalogu, w którym jest dany plik, czyli grupa nr 6.

Wprowadzenie

Oto najciekawsze komentarze z kodu źródłowego funkcji ext2_new_block(), które będą pomocne w kolejnych zadaniach dotyczących alokowania na dysku bloku dla pliku. Oczywiście nie należy tego przepisywać na tablicę - umieszczam w materiałach, żeby ułatwić studentom analizę przykładów.

/*
 * Define EXT2_PREALLOCATE to preallocate data blocks for expanding files
 */
#define EXT2_PREALLOCATE
#define EXT2_DEFAULT_PREALLOC_BLOCKS    8

/*
 * ext2_new_block uses a goal block to assist allocation.  If the goal is
 * free, or there is a free block within 32 blocks of the goal, that block
 * is allocated.  Otherwise a forward search is made for a free block; within 
 * each block group the search first looks for an entire free byte in the block
 * bitmap, and then for any free bit if that fails.

 * First, test whether the goal block is free.

 * The goal was occupied; search forward for a free 
 * block within the next XX blocks.
 *
 * end_goal is more or less random, but it has to be
 * less than EXT2_BLOCKS_PER_GROUP. Aligning up to the
 * next 64-bit boundary is simple..

 * There has been no free block found in the near vicinity
 * of the goal: do a search forward through the block groups,
 * searching in each group first for an entire free byte in
 * the bitmap and then for any free bit.
 * 
 * Search first in the remainder of the current group; then,
 * cyclicly search through the rest of the groups.
 
 * We have succeeded in finding a free byte in the block
 * bitmap.  Now search backwards up to 7 bits to find the
 * start of this group of free blocks.
 */

Ćwiczenie 6

Załóżmy że dysponujemy uproszczoną partycją ext2 zawierającą 4 grupy po 16 bloków każda. Są na niej trzy pliki: A, B i C wszystkie otwarte do zapisu. Zakładamy że prealokacja jest włączona.

Przyjmijmy następujące oznaczenia:

• A, B, C - blok zajęty przez odpowiedni plik
• a, b, c - blok prealokowany dla odpowiedniego pliku
• . - blok wolny
• Alloc D x - alokujemy dla pliku D nowy blok, zmienna goal jest ustawiona na x (funkcja ext2_alloc_block)
• Free A x, y - zwalniamy y bloków, zaczynając od x (funkcja ext_free_blocks)

Ma miejsce ciąg następujących operacji:

sytuacja początkowa:
AAAAAAACCAAAAAAA  AAAAAa..........  ................  B............BBB 

ciąg operacji:
   Alloc A 21
   Free A 14, 8
   Alloc C 9
   Alloc C 15
   Alloc C 16
   Zamykamy plik C
   Alloc A 14
   Alloc A 18
   Usuwamy plik A
   Alloc B 63
   Alloc B 50
   Alloc B 51..56
   Alloc B 57 
   Alloc B 58..60
   Alloc B 61
   Zamykamy plik B

Opisz zawartość dysku po każdej operacji.

Rozwiązanie

1. sytuacja początkowa:

   AAAAAAACCAAAAAAA AAAAAa.......... ................ B............BBB

2. Alloc A 21

   AAAAAAACCAAAAAAA AAAAAA.......... ................ B............BBB

   (alokujemy blok, który wcześniej był już prealokowany)
3. Free A 14,8

   AAAAAAACCAAAAA.. ................ ................ B............BBB

   (zwalniamy 8 kolejnych bloków, rozpoczynając od 14)
4. Alloc C 9

   AAAAAAACCAAAAACc ................ ................ B............BBB

   (alokujemy blok, w tej samej grupie co 8, udaje nam się prealokować jedynie jeden)
5. Alloc C 15

   AAAAAAACCAAAAACC ................ ................ B............BBB

   (alokujemy blok, który wcześniej był już prealokowany)
6. Alloc C 16

   AAAAAAACCAAAAACC Cccccccc........ ................ B............BBB

7. Zamykamy plik C

   AAAAAAACCAAAAACC C............... ................ B............BBB

   (przy zamykaniu zwalniamy wszystkie prealokowane bloki)
8. Alloc A 14

   AAAAAAACCAAAAACC CAaaaaaaa....... ................ B............BBB

   (nie można zaalokować bloku w grupie 0, bo jest już pełna, alokujemy więc jeden blok w grupie 1 i prealokujemy siedem)
9. Alloc A 18

   AAAAAAACCAAAAACC CAAaaaaaa....... ................ B............BBB

   (alokujemy blok, który wcześniej był już prealokowany)
10. Usuwamy plik A

    .......CC...CCCC C............... ................ B............BBB

    (zwalniamy wszystkie bloki zajmowane przez A)
11. Alloc B 63

    .......CC...CCCC C............... ................ BBbbbbbbb....BBB

12. Alloc B 50

    .......CC...CCCC C............... ................ BBBbbbbbb....BBB

13. Alloc B 51..56

    .......CC...CCCC C............... ................ BBBBBBBBB....BBB

14. Alloc B 57

    .......CC...CCCC C............... ................ BBBBBBBBBBbbbBBB

15. Alloc B 58..60

    .......CC...CCCC C............... ................ BBBBBBBBBBBBBBBB

16. Alloc B 61

    BbbbbbbCC...CCCC C............... ................ BBBBBBBBBBBBBBBB

    (ostatnia grupa pełna, alokujemy w kolejnej, czyli pierwszej)
17. Zamykamy plik B

    B......CC...CCCC C............... ................ BBBBBBBBBBBBBBBB

Ćwiczenie 7

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

5. Dla każdej z podanych map bitowych bieżącej grupy odpowiedz jaką wartość przekaże funkcja ext2_new_blok oraz jaką wartość będą miały zmienne prealloc_count i prealloc_block, jeżeli jako parametr goal przekażemy 14 (zakładamy, że algorytm nie będzie przeszukiwał "niedalekiego sąsiedztwa")

   1111 1111 1111 1100 0000 0000 0000 0000 
   
   1111 0000 0000 0100 0000 0000 0000 0000 
   
   1111 1111 1110 0000 0000 0000 0000 0000 
   
   1111 0000 0000 0001 0000 0000 0000 0000 
   
   1111 0000 0000 0000 0001 0000 0000 0000 
   
   1111 1111 1110 1111 1111 1000 0011 1111 
   
   1111 1111 1111 1110 0000 0001 0000 0000 
   
   1111 1111 1111 1110 0000 0001 0000 0001 
   

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. Przyjmujemy, że x to rozmiar bloku. Musi wtedy zachodzić taka równość:
   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 jest zajętych. Wniosek: blok mapy bitowej zajętości bloków odpowiada dwunastemu bitowi w tej mapie (bitowi o numerze 11)..
4. • Bit odpowiadający superblokowi nie jest zapalony.
   • 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.
   • 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.
5. • Funkcja przekaże 14, prealloc_count=7, prealloc_block=15
   • jw.
   • Funkcja przekaże 14, prealloc_count=7, prealloc_block=15. Funkcja po odkryciu, że goal jest wolny, nie przeszukuje do tyłu w celu odnalezienia początku pustego obszaru.
   • Funkcja przekaże 14, prealloc_count=0, prealloc_block=15. Funkcja nie może nic prealokować, bo już pierwszy bit po bicie zaalokowanym jest zapalony.
   • Funkcja przekaże 14, prealloc_count=4, prealloc_block=15. Funkcja tym razem prealokuje cztery bloki występujące bezpośrednio za blokiem alokowanym.
   • Funkcja przekaże 21, prealloc_count=4, prealloc_block=22. Znajdujemy pierwszy wolny bit i za nim prealokujemy co się da.
   • Funkcja przekaże 24, prealloc_count=7, prealloc_block=25. Ponieważ goal jest zajęty, znajdujemy pierwszy wolny bajt w mapie. Nie cofamy się, bo nie możemy i przydzielamy ten blok oraz alokujemy bloki bezpośrednio za nim, aż do końca mapy.
   • Funkcja przekaże 15, prealloc_count=7, prealloc_block=16. Ponieważ goal jest zajęty, szukamy pierwszego wolnego bajtu w mapie. Nie znaleźliśmy żadnego, więc szukamy pierwszego wolnego bitu i przydzielamy ten blok oraz alokujemy bloki bezpośrednio za nim, tak daleko jak się da (najwyżej siedem).

Ćwiczenie 8

Załóżmy że dysponujemy uproszczoną partycją ext2 zawierającą 4 grupy po 8 bloków każda.

Co przekaże funkcja ext2_new_block oraz co zapisze na zmiennych prealloc_block i prealloc_count dla goal = 20 i max (liczba bloków do prealokowania) = 8 dla podanych map bitowych:

11111111 11110001 00000000 01101010

11111111 00011100 00001000 11111111

11111111 00000000 11111111 11111111

11111100 00000000 00001111 11111111

11111111 01010101 00011111 11111111

Co przekaże funkcja, jeżeli goal = 40?

Rozwiązanie

goal = 20

20, 21, 3

21, 22, 2

8, 9, 7

16, 17, 3

16, 17, 2

goal = 40

12, 13, 2

8, 9, 2

8, 9, 7

6, 7, 1

8, 9, 0

Ćwiczenie 9

Zadanie domowe - nie należy go robić w trakcie zajęć, bo słabo się nadaje do przepisywania na tablicę.

Które mapy bitowe bloków grup nie sa prawidłowe i dlaczego, jeżeli blok ma rozmiar 32 B, partycja ma rozmiar 1024 bloków, deskryptor grupy zajmuje 24 B?

11111111 11111111 00000000 11111111 01010101 00000000 11111111 01010101 00000000
11111111 11111111 01010101 00000000 11111111 01010101 00000000 11111111 01010101
00000000 11111111 01010101 00000000 11111111 01010101 00000000 11111111 01010101
00000000 11111111 01010101 

01110011 10101010 10101010 00000000 11111111 01010101 00000000 11111111 01010101
00000000 11111111 01010101 00000000 11111111 11111111 01010101 00000000 11111111
01010101 00000000 11111111 01010101 00000000 11111111 11111111 01010101 00000000
11111111 01010101 00000000 11111111 01010101

11111001 10101010 10101010 00000000 11111111 01010101 00000000 11111111 01010101
00000000 11111111 01010101 00000000 11111111 11111111 01010101 00000000 11111111
01010101 00000000 11111111 01010101 00000000 11111111 11111111 01010101 00000000
11111111 01010101 00000000 11111111 01010101

11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111
11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111
11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111
11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111
11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111
11111111 11111111 11111111

11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111
11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111
11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111
11111111 11111111 11111111 11111111 11111111

Rozwiązanie

Liczba bloków w grupie = 8 * rozmiar bloku więc ta grupa powinna mieć 32 * 8 bloków.

Grup jest partycja/liczba bloków, 1024/32 * 8 = 4. Struktura deskryptora grupy zajmuje 24 B, więc deskryptory grup zajmą 3 bloki.

zły - za krótka tablica

zły - superblok oznaczony jako wolny

zły - superblok zajmuje 1 blok, deskryptory grup 3, mapy bitowe 2. Czyli 6 pierwszych bloków jest zajętych - mapa mówi co innego (a jeszcze dochodzą tablice i-węzłów

zły - za duża tablica

dobry - i pełny