SYSTEMY OPERACYJNE (LAB)
Lista 2 - Algorytmy planowania dostępu do dysku
termin oddawania to 31 marca 2015
Uwaga: Zadania 1-3 nie wymagają implementacji, będą oddawane przy tablicy. Podczas prezentacji
mogą pojawić się pytania związane z wydajnością poszczególnych algorytmów (przepustowością, czasem
obsługi, optymalnością, dyskryminowaniem ścieżek, możliwością ich zagłodzenia...).
Zadanie 1 (0,5pkt)
Wyobraz
my sobie ruchomą głowicę dysku o 100 cylindrach (ponumerowanych od 0 do 99).
Załóżmy, że żądania do dysku są obsługiwane zgodnie z algorytmem C-SCAN (Circular SCAN,
omiatanie cykliczne). W algorytmie tym dysk jest jest traktowany jako powierzchnia cykliczna
(cylindry utożsamiane są z listą cykliczną, na której ostatni cylinder spotyka się
z pierwszym), a głowica porusza się tylko w jednym kierunku obsługując żądania do mijanych
ścieżek. Wiedząc, że łączny dystans (wyrażony liczbą cylindrów) wynosi 60, określ, w którym
cylindrze znajduje się początkowo głowica dysku. Kolejność obsługi cylindrów przedstawia się
następująco:
38 12 84 36 95
Zadanie 2 (0,5pkt)
Głowica dysku z poprzedniego zadania znajduje się początkowo w cylindrze 250.
Obsługując żądania przemieszcza się ona zawsze w kierunku cylindra o wyższym numerze. Do
obsługi wybierane jest żądanie z najmniejszym czasem przeszukiwania względem bieżącego
położenia głowicy SSTF (Shortest Seek Time First). Wiemy, że czas przeszukiwania (Seek Time),
czyli czas przesunięcia głowicy pomiędzy ścieżkami wynosi 2 * 10-6 s (2 mikrosekundy). Oblicz
całkowity czas przeszukiwania znając kolejność obsługi cylindrów:
231 256 245 133 283
Zadanie 3 (1pkt) //zadanie z rozdz. 14. podręcznika1
Przypuśćmy, że dysk ma 5000 cylindrów (0..4999). W danej chwili obsługiwane jest żądanie
w cylindrze 143, a poprzednie żądanie dotyczyło cylindra 125. Kolejka oczekujących żądań
w porządku FIFO przedstawia się następująco:
86 1470 913 1774 948 1509 1022 1750 130
Rozpoczynając od bieżącego położenia głowicy, określ łączny dystans (wyrażony liczbą
cylindrów), który przebywa ramię dysku w celu spełnienia wszystkich żądań dla każdego
z następujących algorytmów planowania dostępu do dysku:
a) FCFS; b) SSTF; c) SCAN; d) C-SCAN.
1 A. Silberschatz, J.L. Peterson, G. Gagne, Podstawy systemów operacyjnych. wydanie siódme, WNT, 2005.
minima punktowe na poszczególne oceny: dst - 5pkt, db - 7pkt, bdb - 9pkt
Zadanie 4 (3pkt)
Dysk jest dzielony przez procesy generujące żądania wejścia-wyjścia. Żądania
scharakteryzowane są parametrami: cylinder i sektor. Wykonanie żądania związane jest
z przesunięciem głowicy nad żądany cylinder, opóz
nienie rotacyjne aż żądany sektor znajdzie się
pod głowicą, oraz transmisję danych między dyskiem a pamięcią operacyjną. Żądania są
wykonywane synchronicznie. Proces żąda dostępu do dysku za pomocą procedury PRZYDZIEL,
wykonuje żądanie, a potem zwalnia dysk wywołując procedurę ZWOLNIJ.
W celu zmniejszenia średniego czasu przesunięcia głowic stosuje się różne algorytmy
szeregowania żądań. Jednym z nich jest SCAN  do obsługi wybierane jest żądanie spełniające dwa
warunki:
1) dotyczy cylindra najbliższego w stosunku do cylindra bieżącego,
2) przesunięcie głowic odbywa się w tym samym kierunku, co poprzednie przesunięcie (jeśli
nie ma żądania spełniającego ten warunek, jest on pomijany).
Napisz program obejmujący procedury PRZYDZIEL i ZWOLNIJ w dwóch wersjach:
(a) Żądania są szeregowane zgodnie z algorytmem FCFS (First Come First Served),
(b) Żądania są szeregowane zgodnie z algorytmem SCAN (algorytm windy, ang. elevator
algorithm).
Podpowiedzi:
 Możliwa reprezentacja żądania: rekord (cylinder: 1..C, gdzie C oznacza liczbę cylindrów dysku,
sektor: integer ...).
 Żądania obsługiwane są w kolejności ich zgłaszania, więc jeżeli dysk jest zajęty, to mogą być
wstrzymywane w jednej kolejce.
 W implementacji algorytmu SCAN można wstrzymywać żądania do różnych cylindrów
w odrębnych kolejkach, gdyż przy wznawianiu należy brać pod uwagę odległość żądanego cylindra
od cylindra, nad którym aktualnie znajdują się głowice. Często jednak liczba żądań oczekujących
jest niewielka a liczba cylindrów duża, zatem takie rozwiązanie jest kosztowne.
 Mając informację, do których cylindrów żądania są skierowane, musimy wiedzieć, które żądanie
znajduje się najbliżej głowic. Potrzebne są dwie kolejki żądań, przed i za głowicami, uporządkowane
według odległości od głowic. Głowice jednak zmieniają położenie, zatem zmieniają się też
odległości. Warto więc ustalić odległość żądań od stałych punktów odniesienia (np. skrajnych
cylindrów). Uporządkowanie według malejącej kolejności od skrajnego cylindra jest takie samo, jak
uporządkowanie według rosnącej odległości od głowic.
Zadanie 5 (5pkt) // https://www.ii.pwr.edu.pl/~juszczyszyn/so.htm
'Dysk' to w naszym przypadku liniowo uporządkowany ciąg bloków o nr od 1 do MAX. Kryterium
oceny algorytmów będzie suma przemieszczeń głowicy dysku, jak wiadomo proporcjonalna do
czasu realizacji zleceń.
" Sprawdzić algorytmy FCFS, SSTF, SCAN i C-SCAN.
" Następnie założyć, że w systemie istnieją także aplikacje real-time, które muszą być
obsłużone za pomocą EDF i/lub FD-SCAN. Jak wpływa to na wyniki?
Uwagi:
Należy samodzielnie określić warunki symulacji dotyczące:
ć% wielkości 'dysku' (ilość bloków)
ć% liczba i sposób generowania zgłoszeń (pełna kolejka od początku? zgłoszenia w trakcie?
rozkład zgłoszeń- równomierny, inny?)
ć% sposób uwzględnienia obsługi zgłoszeń real-time
minima punktowe na poszczególne oceny: dst - 5pkt, db - 7pkt, bdb - 9pkt