Do tematu Podsystem Wejścia-Wyjścia

zadanie nr 5

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.