Ć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:
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:
Rozwiązanie
| alokacja ciągła | alokacja listowa | alokacja indeksowa |
| 201=100+100+1 | 1 | 1 |
| 101=50+50+1 | 52=50+1+1 | 1 |
| 1 | 102=100+1+1 | 1 |
| 198=99+99 ew. 0 | 1 | 0 |
| 98=49+49 | 52=50+1+1 | 0 |
| 0 | 100 | 0 |
Ć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:
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.
Funkcja ta przekazuje liczbę zapisaną w bloku z bufora o nagłówku bh, w komórce o numerze nr. Po odczytaniu zwalnia bufor (wykonujac brelse()). Jest używana przy odczytywaniu adresów w blokach pojedynczych, podwójnych i potrójnych pośrednich.
Funkcja ta przekazuje wskaźnik do nagłówka bufora, do którego wczytano blok o numerze fizycznym i z urządzenia dev.
Rozwiązanie
Warto wprowadzić dwie zmienne pomocnicze:
Jej wartością jest stale liczba adresów mieszczacych się w bloku (czyli rozmiar_bloku/rozmiar_adresu).
Jej wartością jest stale logarytm przy podstawie 2 z wartości zmiennej addr_per_block. 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 ext2_bmap():
1 << (addr_per_block_bits*2)(czyli wartość zmiennej addr_per_block do kwadratu.
(1 << (addr_per_block_bits * 2)) << addr_per_block_bits(czyli wartość zmiennej addr_per_block do potęgi trzeciej)
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 |