Strona główna » Algorytmy » Planowanie Pracy Dysku » Metoda Planowania SCAN
 

Metoda Planowania SCAN

https://mattomatti.com/d03

Algorytm

Metoda Planowania SCAN (Elevator) ma za zadanie zoptymalizować prace głowicy dysku. W metodzie tej nie dochodzi do przegłodzeń żądań, ale nie jest ona najidealniejszym rozwiązaniem.

Dysk przechowuje w buforze nadchodzące żądania odczytu / zapisu danych. Głowica, tak jak winda, jedzie raz w górę, raz w dół i tak cały czas. Podczas przejazdu głowica obsługuje napotkane żądania. Jeśli dane żądanie nie znajduje się już po drodze to pozostaje w buforze i zostanie obsłużone jak będzie ona jechać w drugą stronę.

Załóżmy, że dysk składa się z 100 segmentów. Do kolejki przychodzą następujące żądania odczytania: {25, 35, 30, 60, 80, 40}. Początkowo głowica znajduje się nad segmentem 0 i będzie poruszać się "w górę". Schemat pokazujący skuteczność metody jest przedstawiony poniżej:

Algorytm SCAN

Zaniedbując czas przesuwania głowicy i przyjmując, że w i-tym sprawdzeniu bufora przychodzi i-te żądanie z tablicy to pierwsza dwa 25 i 35 zostaną obsłużone od razu. Następny 30 musi poczekać w buforze. Dalej głowica przechodzi na pozycję 60 i 80, które może obsłużyć "po drodze". Potem napotyka 40, które nie znajduje się pomiędzy 80, a 100, więc pozostaje w buforze. W drodze powrotnej głowica odczyta kolejno żądanie o pozycji 40, a potem 30.

W celu optymalizacji głowica wcale nie musi dojść do końca drogi przed zawróceniem. Dzięki temu wykona ona mniej skoków pomiędzy elementami. W tym przypadku głowica wykona dokładnie 130 skoków. Zaletą tego algorytmu jest to, że żadne żądanie nie zostanie zagłodzone, a wręcz jest gwarancja obsługi w określonej ilości skoków głowicy. Jednak algorytm nadal ma problemy, gdy będą napływać żądania z pierwszych pozycji oraz ostatnich pozycji na zmianę.

Analiza Zadania

W celu rozwiązania tego problemu przy pomocy algorytmu należy mieć wskaźnik, który będzie przechodził po kolejnych elementach buforu. W momencie, gdy przychodzi żądanie, jest ono dołączane na koniec buforu. Algorytm przechodząc po kolejnych elementach wybiera te po kolei, które napotyka, a potem je usuwa.

Poz. GłowicyBuforKomentarz
0{→ 25}Obsłuż od razu
25{→ 35}Obsłuż od razu
35{→ 30}Nie po drodze, pozostaw w buforze
35{30, → 60}Obsłuż od razu
60{30, → 80}Obsłuż od razu
80{30, → 40}Nie po drodze, pozostaw w buforze
80{30, 40 ←}Obsłuż bufor
40{30 ←}Obsłuż bufor, koniec algorytmu
40{ - }Bufor pusty, czekaj na kolejne żądania

Strzałka został zaznaczony aktualnie przeglądany element bufora oraz kierunek w którym przechodzi głowica.

Implementacja

Kolejność

Funkcja KolejnoscSCAN() zwraca dla podanej listy lokalizacji kolejność w jakiej żądania zostaną obsłużone. Opcjonalnie można ustawić poz - aktualną pozycję głowicy oraz wGore - kierunek w którym się porusza.

C++C#
Python
  1. def KolejnoscSCAN(dane, poz = 0, wGore = True):
  2.   wynik = []
  3.   bufor = dane[:]
  4.   i = 0
  5.   while (len(bufor) > 0):
  6.     if ((wGore and bufor[i] > poz) or (not wGore and bufor[i] < poz)):
  7.       wynik.append(bufor[i])
  8.       poz = bufor[i]
  9.       bufor.pop(i)
  10.     else:
  11.       i += 1 if wGore else -1
  12.     if (i < 0):
  13.       i = 0
  14.       wGore = True
  15.     elif (i >= len(bufor)):
  16.       i = len(bufor) - 1
  17.       wGore = False
  18.   return wynik

Algorytm działa w pętli dopóki bufor nie zostanie wyczyszczony. Indeks i wskazuje aktualnie przeglądany element bufora. Jeśli żądanie znajduje się po drodze to przesuwana jest głowica na tą pozycję, a żądanie usuwane. Jeśli nie to należy jedynie przejść na kolejne żądanie w buforze. Po wykonanych czynnościach należy się upewnić, że indeks nie wykroczył poza dozwolny zakres. Jeśli tak to należy odpowiednio go zaktualizować i zmienić kierunek ruchu głowicy.

Ilość skoków

W celu obliczenia ile skoków musi łącznie wykonać głowica należy wyznaczyć kolejność obsłużenia, a następnie obliczenia wartości absolutnej każdego kolejnego przesunięcia.

C++C#
Python
  1. def SkokowSCAN(lokalizacje, poz = 0):
  2.   lacznie = 0;
  3.   dane = KolejnoscSCAN(lokalizacje, poz)
  4.   for i in range(len(dane)):
  5.     lacznie += abs(dane[i] - poz)
  6.     poz = dane[i]
  7.   return lacznie

Testowanie funkcji

Algorytmy można przetestować przy pomocy poniższego fragmentu kodu:

C++C#
Python
  1. print("Podaj lokalizacje:")
  2. lokalizacje = [int(x) for x in input().split()]
  3. kolejnosc = KolejnoscSCAN(lokalizacje)
  4. print("Kolejność obsługi:")
  5. for a in kolejnosc:
  6.   print(a, end=' ')
  7. lacznie = SkokowSCAN(lokalizacje)
  8. print("\nPotrzebnych skoków:", lacznie)