Algorytmy planowania
dostępu do dysku

Wykonali:
Izabela Błońska
Dawid Michalski
Michał Krause

Budowa dysku twardego

Dysk twardy składa się z zamkniętego w
obudowie, wirującego talerza (dysku) lub
zespołu talerzy, wykonanych najczęściej ze
stopów aluminium, o wypolerowanej
powierzchni, pokrytej nośnikiem magnetycznym
o grubości kilku mikrometrów, oraz z głowic
elektromagnetycznych umożliwiających zapis i
odczyt danych. Na każdą powierzchnię talerza
dysku przypada po jednej głowicy odczytu i
zapisu.

Czasy poszczególnych etapów

T

1

- ustawienie głowicy

T

2

- obrót powierzchni

T

3

- odczyt sektora

T

1

>>T

2

>>T

3

Jak system operacyjny widzi dysk
twardy?

System operacyjny widzi dysk twardy jako ciąg
liniowo uporządkowanych sektorów. Numerowanie
jest takie, że dostęp do 2 adresów położonych blisko
siebie jest jak najkrótszy.

Obiekt zgłoszenie

Proponowane pola obiektu zgłoszenie:

cylinder - numer cylindra na którym jest sektor do odczytu/zapisu

czasZgłoszenia - czas kiedy pojawia się dane zgłoszenie

czyPriorytet - pole określające czy dane zgłoszenie ma deadline

deadline - czas w jakim musi zostać wykonane dane zgłoszenie

Algorytm FCFS(First Come First Served)

algorytm zakładający, że kolejność wykonywania zamówień jest

zgodna z ich dołączeniem. Jest najprostszy, lecz posiada wiele wad.

Algorytm FCFS(First Come First Served)

Zalety:
•

Prosty w implementacji

Wady:
•

Nadmierny, chaotyczny ruch głowic czytająco-piszących

•

Długi czas przesyłania bloków

•

Przyspiesza zużycie mechanizmu dysku

Algorytm FCFS(First Come First Served)

1. Ustaw pozycję głowicy oraz sumę przemieszczeń głowicy na zero.
2.Dopóki są zlecenia do obsłużenia, wykonuj:

2.1. Sprawdź, czy są zlecenia pojawiające się w danej chwili. Jeżeli

są, dodaj je

do kolejki.
2.2. Wybierz z kolejki pierwsze zlecenie.
2.3. Do sumy przemieszczeń dodaj odległość między wybranym

sektorem, a

aktualną pozycją głowicy.
2.4. Zmień pozycję głowicy na wybrany sektor.

2.5. Odczytaj lub zapisz dane do sektora.

3. Zwróć sumę przemieszczeń głowicy czytająco–piszącej.

Algorytm SSTF (Shortest-Seek-Time-
First)

algorytm szeregowania zadań, który zakłada, że w pierwszej
kolejności wykonuje się zamówienia odnoszące się do ścieżki
najbliższej bieżącemu położeniu głowicy. SSTF jest algorytmem
bliskim optymalnego. Suma przemieszczeń głowicy jest bardzo niska,
ponieważ wykonujemy ruchy tylko do najbliższego sektora, który
należy odczytać.

Algorytm SSTF (Shortest-Seek-Time-
First)

Zalety:
•

Mała suma przemieszczeń głowicy czytająco - piszącej, co

wydłuża czas działania dysku
•

Średni czas oczekiwania na odczyt/zapis jest mały

Wady:
•

Istnieje możliwość zagłodzenia zleceń, jeżeli do bufora będzie

dodawane dużo zleceń blisko aktualnej pozycji głowicy

Algorytm SCAN

Algorytm w którym głowica rozpoczyna pracę od jednej krawędzi
dysku i przemieszcza się w kierunku krawędzi przeciwległej
obsługując zamówienia z kolejki. Po dotarciu do krawędzi dysku
zmienia się kierunek ruchu głowicy, która nieustannie przeszukuje
(skanuje) dysk tam i z powrotem

Algorytm SCAN

Zalety: Jeśli w kolejce pojawi się zamówienie odnoszące się do
cylindra znajdującego się tuż przed głowicą, to zostałoby
zrealizowane natychmiast

Wady: Jeśli w kolejce pojawi się zamówienie odnoszące się do cylindra
znajdującego się tuż za głowicą, to zamówienie to musi poczekać, aż
głowica dojdzie do końca, zmieni kierunek i wróci.

Algorytm C-SCAN

odmiana algorytmu SCAN, w której po dojściu do skrajnej ścieżki
głowica wraca szybko do ścieżki przeciwległej, bez realizowania
zamówień, gdyż tam mogło dojść do największego zagęszczenia
zamówień-skanowanie w jednym kierunku.

Algorytm C-SCAN

Zalety:
•

Zmniejszone maksymalne opóźnienie związane z nowymi

żądaniami

Algorytm C-SCAN

1. Ustaw pozycję głowicy oraz sumę przemieszczeń głowicy na zero.
2.Dopóki są zgłoszenia do obsłużenia, wykonuj:

2.1. Sprawdź, czy są zgłoszenie pojawiające się w danej chwili. Jeżeli są, dodaj je do kolejki.

2.2. Jeśli głowica nie znajduje się na skrajnej ścieżce,wybierz z kolejki zlecenie odczytania
cylindra, który znajduje się najbliżej głowicy, lecz po stronie zgodnej z jej ruchem.
2.3. W przeciwnym przypadku(jeśli głowica znajduje się na skrajnej ścieżce, wybierz z kolejki
zgłoszenie znajdujące się najdalej(na samym początku))
2.4. Do sumy przemieszczeń dodaj odległość między wybranym cylindrem, a aktualną pozycją
głowicy.
2.5. Zmień pozycję głowicy na wybrany cylinder.
2.6. Odczytaj lub zapisz dane do cylinder.
3. Zwróć sumę przemieszczeń głowicy czytająco–piszącej.

Algorytm EDF (Earliest Deadline First)

algorytm szeregowania zadań wykorzystywany w twardych
systemach czasu rzeczywistego. Zasada jego działania opiera się o
kolejkę priorytetową, w której pierwszeństwo mają zlecenia najbliższe
do swojego deadline’u. W pierwszej kolejności wykonywane są
zlecenia, które muszą zostać wykonane jak najszybciej. Jeżeli
wszystkie zlecenia z deadlinem zostały wykonane, kolejne są
obsługiwane algorytmem FCFS, czyli zgodnie z czasem zgłoszenia.

Algorytm EDF (Earliest Deadline First)

Zalety:
•

Jest konieczny w twardych systemach czasu rzeczywistego.

•

Gwarantuje jak najszybsze wykonanie zleceń z ograniczeniem

czasowym.
Wady:
•

Pozostałe zlecenia (nie mające ograniczenia czasowego) mogą

zostać zagłodzone, jeżeli do bufora będzie dodawane dużo zleceń
czasu rzeczywistego
•

Suma przemieszczeń głowicy czytająco – piszącej duża, ponieważ

po drodze będziemy mijać zlecenia bliższe położeniu głowicy, które
nie będą obsługiwane

Algorytm FD-SCAN

Algorytm działający na podobnej zasadzie co SCAN jednak zgłoszenia
priorytetowe mają pierwszeństwo. W przypadku ich wystąpienia
głowica zmierza w stronę priorytetu z najkrótszą granicą czasową,
wykonując po drodze kolejne zgłoszenia.