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
Wyszukiwarka
Podobne podstrony:
zadania 1 5 10ZADANIE (10)CAD ZADANIA 4 6 10ZADANIE (10)cw3 zadanie 10stat zadania1 10zadania 10ZADANIE (10)ZADANIE (10)Analiza Zadania 10ZADANIE (10)ZADANIE (10)ZADANIE (10)ZADANIE (10)Zadanie20 10 11Zadanie20 10 11więcej podobnych podstron