Do tematu Podsystem Wejścia-Wyjścia

zadanie nr 5

Szeregowanie żądań do urządzeń blokowych

Wymiana informacji i danych pomiędzy komputerem i dyskiem odbywa się
poprzez porty. Porty są to adresy w pamięci komputera. Zarówno dysk jak
i komputer potrafią zapisywać do portów dane. Potrafią również dane z portów
odczytywać. Wykonanie przez sterownik dysku operacji czytania polega na
wpisaniu do odpowiednich portów m. in. liczby sektorów, które mają zostać
wczytane oraz adresu dyskowego, od którego ma się rozpocząć czytanie. Dysk
ustawia swoje głowice we wskazanym miejscu, a następnie wysyła przerwanie,
aby poinformować procesor o gotowości do transmisji danych. Po nadejściu
przerwania od dysku, wywoływana jest funkcja, która wczytuje dane przesyłane
przez dysk.

Operacja pisania przebiega analogicznie.

Dla nas najistotniejszym założeniem jest to, że dysk nie utrzymuje bufora
z żądaniami. Następne żądanie odczytuje dopiero po zrealizowaniu poprzedniego.
Oznacza to, że zawsze ustawia swoje głowice tam, gdzie każemy mu je ustawić.
W takim przypadku zajmowanie się programowym szeregowaniem żądań do dysku
jest rzeczą sensowną.

W pliku /drivers/block/ll_rw_blk.c znajduje się funkcja add_request,
realizująca szeregowanie żądań do urządzeń blokowych. Wykorzystywane jest
w niej makro IN_ORDER, zdefiniowane w pliku /include/linux/blk.h.

Należy:


Wyjaśnić, jaki algorytm funkcja add_request realizuje obecnie.


Zmienić kod funkcji add_request w taki sposób, aby żądania
były szeregowane zgodnie z algorytmem F-C-LOOK.

Wyjaśnić dlaczego nie można zaimplementować algorytmu windy (LOOK).



Algorytm F-C-LOOK jest sprawiedliwą wersją algorytmu C-LOOK,
podobnie jak F-SCAN jest sprawiedliwą wersją algorytmu SCAN.
W C-LOOK żądania są obsługiwane tylko podczas ruchu głowicy w jednym
kierunku. Kierunek ten nazwijmy aktywnym. Podobnie jest w algorytmie F-C-LOOK
z tym, że obsługiwane są tylko te żądania, które nadeszły przed rozpoczęciem
ruchu głowicy w kierunku aktywnym.

Rozpatrzmy następujący przykład. Nadchodzą cztery żądania dotyczące
sektorów o numerach: 5, 6, 10, 7. Zakładamy, że zanim pierwsze
żądanie zostanie obsłużone, nadejdą pozostałe. Wówczas algorytm C-LOOK
ustawi żądania w kolejności 5, 6, 7, 10, natomiast algorytm F-C-LOOK
w kolejności 5, 6, 10, 7. Jeśli zmienimy sytuację: nadchodzą żądania
5, 6, 10, 7, 1, to C-LOOK, przy powyższych założeniach,
ustawi je w kolejności 5, 6, 7, 10, 1, F-C-LOOK w kolejności
5, 6, 10, 1, 7. Kolejność nadchodzenia żądań jest, oczywiście, istotna.


Uwaga. Aby zrozumieć jak działa funkcja add_request
trzeba zapoznać się ze strukturami request oraz blk_dev_struct.


Autor: Maciej Kaczmarek