Dysk w systemie plików EXT2 podzielony zosta³ na grupy bloków. W ka¿dej grupie bloki s± zajęte kolejno przez blok identyfikacyjny (super block), blok z deskryptorami grup, blok z bitmap± zajęto¶ci bloków danej grupy, blok zajęto¶ci i-węz³ów danej grupy, tablicę i-węz³ów oraz same bloki danych.
    Taki sposów podzia³u dysku powoduje, ¿e w chwili gdy chcemy przydzielić nowy blok danych (lub i-węze³) musz± zostać zczytane z dysku informacje o zajęto¶ci bloków (lub i-węzk³ów). Aby przyspieszyć przydzielanie bloków (i-węz³ów) w pamięci znajduje się tablica z bitmapami zajęto¶ci bloków (i-węz³ów) (odzielnie oczywi¶cie dla bloków i i-węz³ów). Poniewa¿ tablica ta jest o wiele krótsza ni¿ liczba grup (mo¿e ich być kilkadziesi±t) dlatego zachodzi potrzeba częstego ³adowania bitmap z dysku do pamięci. Aby zmniejszyć liczbę odwo³ań do dysku (co jest du¿ym narzutem czasowym) wykorzystuje się algorytm wymiany LRU.

    Zadaniem jest zamiana algorytmu LRU dla blodów dyskowych na:
    a) algorytm FIFO - pierwsza która zosta³a wczytana, pierwsza zostaje wymieniona;
    b) algorytm LFU - najmniej u¿ywana bitmapa zostaje zast±piona now±;
    c) w³asny algorytm - mo¿e  to być modyfikacja lub po³±czenie znanych algorytmów lub zupe³nie nowy sposów wymiany (nale¿y uzasadnić przyjęte rozwi±zanie)

    Dla tak przygotowanych algorytmów nale¿y przygotować testy (z uzasadnieniem sensowno¶ci), przeprowadzić je, a na końcu przeanalizować i opisać wnioski z nich wynikaj±ce. Testy powinny być przeprowadzony równie¿ dla istniej±cego algorytmu. Testy powinny zawierać graficzn± prezentację wyników.

    Czę¶ć dotycz±ca przydzia³u bloków dyskowych znajduje się w pliku: /linux/fs/ext2/balloc.c

Autor zadania:
Piotr Kawczyński