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.

  1. static List<int> KolejnoscSCAN(List<int> dane, int poz = 0, bool wGore = true) {
  2.   List<int> wynik = new List<int>();
  3.   List<int> bufor = new List<int>(dane);
  4.   int i = 0;
  5.   while (bufor.Count() > 0) {
  6.     if ((wGore && bufor[i] > poz) || (!wGore && bufor[i] < poz)) {
  7.       wynik.Add(bufor[i]);
  8.       poz = bufor[i];
  9.       bufor.RemoveAt(i);
  10.     }
  11.     else {
  12.       i += wGore ? 1 : -1;
  13.     }
  14.     if (i < 0) {
  15.       i = 0;
  16.       wGore = true;
  17.     } else if (i >= bufor.Count) {
  18.       i = bufor.Count - 1;
  19.       wGore = false;
  20.     }
  21.   }
  22.   return wynik;
  23. }

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.

  1. static int SkokowSCAN(List<int> lokalizacje, int poz = 0) {
  2.   int lacznie = 0;
  3.   List<int> dane = KolejnoscSCAN(lokalizacje, poz);
  4.   for (int i = 0; i < dane.Count; i++) {
  5.     lacznie += Math.Abs(dane[i] - poz);
  6.     poz = dane[i];
  7.   }
  8.   return lacznie;
  9. }

Testowanie funkcji

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

  1. static void Main(string[] args) {
  2.   List<int> lokalizacje = new List<int>();
  3.   Console.WriteLine("Podaj lokalizacje:");
  4.   string[] dane = Console.ReadLine().Split(' ');
  5.   foreach (string s in dane) {
  6.     lokalizacje.Add(Convert.ToInt32(s));
  7.   }
  8.   List<int> kolejnosc = KolejnoscSCAN(lokalizacje);
  9.   Console.WriteLine("Kolejność obsługi:");
  10.   foreach (int a in kolejnosc)
  11.     Console.Write("{0} ", a);
  12.   int lacznie = SkokowSCAN(lokalizacje);
  13.   Console.WriteLine("\nPotrzebnych skoków: {0}", lacznie);
  14.   Console.ReadKey();
  15. }