Notatka2  planowanie dostępu do dysku
I. Opis algorytmów
II. Podpowiedzi do zadań z listy drugiej (studentów z zeszłego roku, w tym
semestrze nie padły zdalnie żadne pytania)
Uwaga: Nie będę przypominał schematu odwzorowującego strukturę dysku. Powiedzieliśmy
sobie o tym na zajęciach. Powinniście mieć wiedzę dotyczącą podstawowych pojęć (sektor,
ścieżka, cylinder, czas przeszukiwania, adres dyskowy). Kolejny raz zachęcam do studiowania
podstawowego podręcznika. W rozdziale związanym ze strukturą pamięci masowej są
zamieszczone wszystkie niezbędne informacje dotyczące struktury dysku (np. prędkości
liniowej, kątowej, opóz
nienia obrotowego, szerokości pasma itd.).
I.
W systemach operacyjnych czas przeszukiwania dysku (ang. seek time) jest bardzo
ważny. Kiedy żądania dostępu do dysku ustawiane są w kolejce, czas przeszukiwania
rośnie i znacząco spowalnia cały system. Algorytmy planowania dostępu są używane
w celu redukcji czasu przeszukiwania.
Koncentrujemy się głównie nad następującymi algorytmami:
" FCFS (First Come First Serve);
" SSTF (Shortest Seek Time First), odpowiednik SJF (Shortest Job First);
" SCAN (Elevator);
" C-SCAN (Circular SCAN);
" LOOK;
" C-LOOK.
Algorytmy te są naiwnie proste, zarówno w założeniach, realizacji, jak
i w implementacji. Problemem (wynika to z zapytań, jakie od państwa otrzymałem)
jest jednak to, że są do siebie podobne.
Spróbujmy je przeanalizować (raz jeszcze) na przykładzie i zastanowić się, który
z algorytmów (w średnim przypadku) zapewnia minimalną liczbę przesunięć głowicy
i, w konsekwencji, minimalny czas przeszukiwania. Czy tym algorytmem jest C-LOOK?
Przykład:
Załóżmy, że dysk ma 200 cylindrów (ścieżek) numerowanych od 0 do 199.
W kolejce (związanej z żądaniami zapisu/odczytu) ustawiamy numery
cylindrów: 95, 180, 34, 119, 11, 123, 62, 64. Głowica ustawiona jest
początkowo nad cylindrem o numerze 50.
1
1. First Come -First Serve
Żądania dodawane są na końcu kolejki i spełniane według kolejności ich dodawania.
Aby określić liczbę przesunięć głowicy zliczamy liczbę cylindrów (lub ścieżek), które są
mijane w trakcie realizacji poszczególnych żądań (np. przemieszczając się między
cylindrami o numerach 50 i 95 głowica mija 45 cylindrów (ścieżek).
Proszę sprawdzić, jaki jest łączny koszt zastosowania tego algorytmu (640?)
Sekwencja przesunięć głowicy zilustrowana jest na poniższym rysunku.
Czy ten algorytm jest najgorszy ze względu na przyjęte kryterium?
2
2. Shortest Seek Time First (odpowiednik SJF z poprzedniej listy)
W tym przypadku żądania są obsługiwane według kolejności wyznaczonej
najkrótszymi odległościami między cylindrami sąsiadującymi w pojedynczym ruchu
głowicy. Przykładowo, startując z cylindra o numerze 50, w pierwszym ruchu wybrany
zostanie cylinder 62 (odległość 12 cylindrów) zamiast 34 (odległość 16 cylindrów).
A
ączny dystans do przebycia przez ramię głowicy to 236?
Proszę zastanowić się, jakie niekorzystne zjawisko może tu się pojawić (analogia do
zjawiska głodzenia procesów w SJF). Dla ułatwienia dodam, że może się zdarzyć tak,
że żądania spływające na bieżąco dotyczą cylindrów oddalonych niewiele od siebie. Co
w przypadku, gdy istnieje chociaż jedno żądanie związane z międzycylindrową
odległością zawsze większą od odległości dotyczących pozostałych żądań?
3
3. SCAN (elevator  winda)
W ogólnym założeniu głowica przemierza dysk w kierunku skrajnych cylindrów,
realizując po drodze operacje odczytu i zapisu.
Proszę zastanowić się, w którym kierunku powinno podążać ramię głowicy
w początkowej sekwencji przemieszczania się.
Jakie niekorzystne zjawisko można tutaj zaobserwować? Czy żądania obsługiwane są
sprawiedliwie? Jeśli nie, to które są dyskryminowane?
A
ączny dystans to 230? Jest optymalny? Czy ten algorytm można usprawnić? Jak?
4
4. Circular Scan
Ten algorytm jest odpowiedzią na jedno z pytań zadanych przeze mnie w punkcie 3.
i ma zapewnić  sprawiedliwą obsługę żądań.
Algorytm działa podobnie jak winda, przy czym dysk traktowany jest jak powierzchnia
cykliczna (ostatni cylinder jest utożsamiany z pierwszym).
A
ączny dystans to 187? Czy ten algorytm można usprawnić? Jak?
5
5. C-LOOK
To ulepszona wersja algorytmu C-SCAN (analogicznie algorytm LOOK jest modyfikacją
algorytmu SCAN). Modyfikację omawialiśmy na zajęciach. Dotyczy skrajnych cylindrów
dysku, które nie są powiązane z żadnymi żądaniami odczyty/zapisu.
A
ączny dystans to 157? Optymalny?
Proszę zauważyć, że w tej krótkiej analizie poszczególnych algorytmów, wyraz
nie
rysowała się poprawa jakości zwracanych rozwiązań (z wartości funkcji kryterialnej
równej 640 zeszliśmy do 157).
Uwaga: Podobnie, jak w przypadku listy pierwszej, jednym z elementów pracy nad
listą drugą ma być porównanie algorytmów (zadania 1-3, 5). Będę wymagał pełnego
rozumienia poszczególnych algorytmów i ich porównania.
6
II
Odn. zadania 5:
Warunki symulacji określacie indywidualnie. Na tym polega trudność tego zadania.
Celowo nie chcę niczego sugerować (poza wykorzystaniem metod z zadania 4), licząc,
że ktoś mnie zaskoczy oryginalnym podejściem do analizy algorytmów.
Algorytmy EDF i FD-SCAN zostały omówione pokrótce na zajęciach. Gdyby jednak ktoś
nie uważał, lub też chciał poznać inne algorytmy czasu rzeczywistego
z uwzględnieniem okien czasowych, zostały one zilustrowane np. w książce Saud A.
Aldarmi  Real-Time Database Systems: Concepts and Design :
https://www.cs.york.ac.uk/ftpdir/reports/98/YCS/303/YCS-98-303.pdf
Jak będzie oceniane zadanie 5? Przede wszystkim zależy mi na strukturalnym
zaprogramowaniu synchronizacji. Właśnie dlatego pojawiło się na liście zadanie 4.
Wydawało mi się, że w sposób naturalny wszyscy zauważą celowość tej propozycji
spojrzenia na zarządzanie operacjami dyskowymi. Jeżeli ktoś uwzględni
zaproponowane metody w zadaniu 5, nie ma potrzeby oceniania poprzedniego
zadania.
Odn. zadania 4:
Macie sporo wątpliwości z nim związanych. W jego treści nie ma mowy
o przeprowadzeniu symulacji. Jeżeli jednak uważnie przyjrzycie się proponowanemu
rozwiązaniu, powinniście wychwycić pewne szczegóły i problemy z nim związane.
Rozwiązanie dotyczy wykorzystania dwóch kolejek zamiast jednej. Niech  lewa
kolejka dotyczy żądań skierowanych do cylindrów o numerach mniejszych niż numer
cylindra bieżącego, czyli tego, nad którym znajduje się głowica. Natomiast  prawa
kolejka dotyczy żądań skierowanych do cylindrów o numerach większych niż numer
cylindra bieżącego. Sugeruję wprowadzenie zmiennej logicznej KIERUNEK wskazującej
na kierunek ruchu głowicy.
Żądania w  lewej kolejce są uporządkowane malejąco według numerów cylindrów,
natomiast w  prawej kolejce - rosnąco. Wstawiając żądania do kolejek najlepiej
uwzględniać różnicę liczby cylindrów dysku i numeru żądanego cylindra. Podpowiedz

zamieściłem w treści zadania.
Zwróćcie uwagę na subtelne szczegóły tego rozwiązania. Jeżeli dysk jest  zajęty
(należałoby to uwzględnić w swoim rozwiązaniu zadania 5, kiedyś przecież głowica
czyta/zapisuje poza przemieszczaniem się między cylindrami), a głowica porusza się w
kierunku  lewym i przybywa żądanie skierowane do bieżącego cylindra, to jest ono
umieszczane w  lewej kolejce (analogicznie, jeśli głowica porusza się w  prawym
kierunku, to żądanie umieszczane jest w  prawej kolejce ). Po obsłudze bieżącego
żądania nie zmieni się kierunek ruchu głowicy. Jeśli więc intensywnie będą zgłaszane
żądania do tego samego cylindra, to zagłodzą one żądania oczekujące do innych
cylindrów.
Jak tego uniknąć? Należy wstawiać żądania do kolejek w sposób odwrotny do tego,
który podpowiada nam intuicja, tj. do  prawej kolejki gdy kierunek jest  lewy i do
7
 lewej kolejki gdy kierunek jest  prawy . Żądania nie zostaną wtedy zagłodzone
i będą obsłużone przy następnym przejściu głowic nad konkretnymi cylindrami.
Dotyczy to żądań do bieżącego cylindra, które przybyły podczas wykonywania żądania
dotyczącego tego cylindra.
Drugi problem dotyczy zmiany kierunku ruchu głowicy. Zmiana ma miejsce wtedy, gdy
po zakończeniu wykonywania żądania nie ma już dalszych żądań przed głowicą, ale
są żądania za nią. Proszę zadbać, aby kierunek ruchu głowicy był ustalany
każdorazowo przy rozpoczynaniu wykonywania kolejnego żądania (mimo, że
w większości algorytmów, opartych o mechanizm windy, naturalna wydaje się
jednorazowa zmiana kierunku ruchu głowicy dla wszystkich żądań leżących na  prawo
lub na  lewo od niej). Mam nadzieję, że sami przekonacie się, że bez tego podejścia,
w pewnej specyficznej sytuacji nowe żądanie może wymagać przemieszczenia się
głowicy i zastać jednocześnie kierunek przeciwny do pożądanego.
Jeżeli chcecie dowiedzieć się więcej na temat tego rozwiązania, odsyłam do:
Hoare, C.A.R.,  Monitors: An Operating System Structuring Concept, Communications
of ACM, vol. 17, Oct. 1974, p. 549-557
http://web.cs.wpi.edu/~cs4513/b10/Papers/index.htm
oraz do
R. C. Holt ,  Concurrent Euclid, the Unix* System, and Tunis , Addison-Wesley series
in computer science, 1986
http://maximumbook.org/Concurrent-Euclid-the-Unix-System-and-Tunis-Addison-
Wesley-series-in-computer-science-page1958485636.html
Jedno z pytań dotyczyło mechanizmu synchronizacji wykonywania żądań. Na czym
polega? Na porządkowaniu w czasie realizacji poszczególnych żądań. Temu właśnie ma
służyć zaproponowane rozwiązanie i istotne jest wykorzystanie informacji płynącej
z realizacji żądań poprzednich, gdyż wyznacza ona kierunek ruchu głowicy. Można
więc założyć, że żądania komunikują się ze sobą i przekazują pewną informację.
Jeszcze jedno pytanie dotyczyło uwzględnienia w implementacji wszystkich trzech
składowych wpływających na czas przeszukiwania dysku. W założeniu powinniście
uwzględniać prędkość przemieszczania się głowicy między sąsiednimi cylindrami
(ścieżkami) Możecie (ale nie musicie) uwzględniać prędkość obrotową dysku
i szerokość pasma. To dość łatwe do zrobienia w sposób  byle jaki i dość trudne,
jeżeli chcecie zrobić to dobrze. Dlaczego? Mógłbym sporo napisać na ten temat.
Zastanówcie się proszę, na czym polega trudność takiego podejścia. Czy i w jaki
sposób prędkość obrotowa zależy od numeru cylindra, którego dotyczy żądanie, w jaki
sposób poukładane są sektory w ramach ścieżek różnie oddalonych od osi obrotu
dysku. W jaki sposób szerokość pasma wpływa na czas realizacji operacji
odczytu/zapisu?
8