Bartek\Tekst\Szkola\ProjektSO\Zadanko




Bartłomiej Kalinka

Zadanie dotyczące podręcznej pamięci buforowej.
Strategia "najrzadziej używany"

    W podręcznej pamięci buforowej stosuje się kolejki
LRU.  Ten skrót oznacza strategię "least recently used" - "najdłużej
nieużywany".  Oznacza to, że im dłużej nieużywany jest bufor, tym
większa szansza, że zostanie on opróżniony i przeniesiony do kolejki wolnych
buforów (a później użyty ponownie).  Proponowane przeze mnie zadanie
polega na zmianie tej strategii na strategię "najrzadziej używany". 
Dokładne zaimplementowanie tej strategii byłoby bardzo kłopotliwe (wymagałoby
zatrudnienia demona, który powiedzmy co sekundę aktualizowałby struktury
danych, a w dodatku konieczne byłoby zapamiętywanie czasu każdego odwołania
do bufora).  Należy więc zrealizować przybliżoną wersję tej strategii. 
Może ona wyglądać następująco.  Zamiast w kolejce LRU, bufory są uporządkowane
według liczby odwołań do każdego z nich.  Dodatkowo należy też zapamiętywać
tą liczbę odwołań w strukturze danych związaną z każdym buforem, gdyż może
być ona identyczna dla dwóch buforów lub różnić się o więcej niż 1 i wtedy
samo uporządkowanie w kolejce byłoby niejednoznaczne.  Co pewien czas
(oznaczmy go t) zerujemy liczbę odwołań do wszystkich buforów i zaczynamy
zliczanie od początku.  Na dobrą sprawę przybliża to strategię "najrzadziej
używany" z wyjątkiem momentu tuż po wyzerowaniu (wtedy wszystkie bufory
są mniej więcej równo (nie)używane).  Aby temu zapobiec stosujemy
dodatkowo dla każdej kolejki buforów drugą, zamienną kolejkę.  Działa
ona na tej samej zasadzie, a tylko jej zliczanie jest startowane (liczby
odwołań do buforów są zerowane) w połowie cyklu t drugiej kolejki. 
Gdy startuje zliczanie jednej kolejki, druga kolejka wchodzi w drugą połowę
swego cyklu, a więc na podstawie tej drugiej kolejki (nazwijmy ją "ważną")
powinny być podejmowane decyzje o przenoszeniu buforów do kolejki wolnych. 
I odwrotnie, gdy ta kolejka zostanie wyzerowana, odpowiedni wskaźnik powinien
zacząć wskazywać na tą pierwszą.  W ten sposób nigdy nie korzystamy
z dopiero co wyzerowanej kolejki.
    Należy zmodyfikować odpowiednie struktury danych
(nagłówek bufora).  Każde odwołanie się do bufora, czyli wywołanie
funkcji getblk(), zamiast wstawiania bufora na koniec kolejki LRU, powinno
zwiększać licznik odwołań w obu naszych kolejkach i ewentualnie przesuwać
bufor do tyłu (w kierunku końca).  Dodatkowo należy sprawdzać, czy
nie minął czas t, w razie czego zerując odpowiednią kolejkę i ustawiając
wskaźnik do aktualnie "ważnej" kolejki na tą drugą.  Konieczna jest
też modyfikacja funkcji refill_free_list(), a konkretnie jej fragmentu
dotyczącego wyboru z każdej kolejki LRU kandydata do usunięcia.  Tym
kandydatem będzie bufor o najmniejszej liczbie odwołań w aktualnie "ważnej"
kolejce (jednej z dwóch), czyli bufor znajdujący się na jej początku. 
Należy zadbać, aby wszystkie odwołania do kolejek LRU zostały dostosowane
do aktualnych struktur (np. remove_from_queues() - usuwanie z kolejek). 
Zastanów się także, co uczynić, gdy funkcja getblk() pobiera z kolejki
wolnych buforów nowy bufor, a dzieje się to w trakcie cyklu t - jak zadbać
o to, aby ten bufor nie był pokrzywdzony (liczba odwołań do niego w tym
cyklu t będzie znacznie niższa, niż dla innych buforów - on nie zaczynał
od początku).  Być może należy pamiętać dla każdego bufora, czy był
on obecny na początku cyklu t, czy został dopiero co przydzielony i zwalniać
tylko te bufory, które miały okazję sprawdzić się przez cały cykl t. 
Można też przy przydzielaniu bufora liczyć (znać) przeciętną liczbę odwołań
do każdego bufora w tym cyklu t i przydzielać mu tę liczbę jako startową
liczbę odwołań, zamiast zera.
    Aby zadanie miało sens, trzeba zbadać, jak poczynione
zmiany wpłynęly na zachowanie systemu.  Należy w tym celu przeprowadzić
odpowiednie testy.  Najistotniejsze jest tutaj porównanie nowej strategii
ze strategią LRU.  Należy też eksperymentować z czasem zliczania t,
w celu znalezienia optymalnej konfiguracji.
    Pliki źródłowe, których dotyczy to zadanie:
    fs.h - definicje struktur danych, prototypy funkcji,
stałe.
    buffer.c - funkcje obsługujące podręczną pamięć
buforową.