Buforowanie przy czytaniu bitmap zajęto¶ci bloków
dyskowych.

    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