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. vector<int> KolejnoscSCAN(vector<int> dane, int poz = 0, bool wGore = true) {
  2.   vector<int> wynik;
  3.   vector<int> bufor(dane);
  4.   int i = 0;
  5.   while (bufor.size() > 0) {
  6.     if ((wGore && bufor[i] > poz) || (!wGore && bufor[i] < poz)) {
  7.       wynik.push_back(bufor[i]);
  8.       poz = bufor[i];
  9.       bufor.erase(bufor.begin() + i, bufor.begin() + i + 1);
  10.     } else {
  11.       i += wGore ? 1 : -1;
  12.     }
  13.     if (i < 0) {
  14.       i = 0;
  15.       wGore = true;
  16.     } else if (i >= bufor.size()) {
  17.       i = bufor.size() - 1;
  18.       wGore = false;
  19.     }
  20.   }
  21.   return wynik;
  22. }

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. int SkokowSCAN(vector<int> lokalizacje, int poz = 0, bool wGore = true) {
  2.   int lacznie = 0;
  3.   vector<int> dane = KolejnoscSCAN(lokalizacje, poz, wGore);
  4.   for (int i = 0; i < dane.size(); i++) {
  5.     lacznie += 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. int main() {
  2.   vector<int> lokalizacje;
  3.   int n, tmp;
  4.   cout << "Podaj ile lokalizacji:\n n = ";
  5.   cin >> n;
  6.   cout << "Podaj lokalizacje:\n";
  7.   for (int i = 0; i < n; i++) {
  8.     cin >> tmp;
  9.     lokalizacje.push_back(tmp);
  10.   }
  11.   vector<int> kolejnosc = KolejnoscSCAN(lokalizacje);
  12.   cout << "Kolejnosc obslugi:\n";
  13.   for each (int a in kolejnosc)
  14.     cout << a << " ";
  15.   int lacznie = SkokowSCAN(lokalizacje);
  16.   cout << "\nPotrzebnych skokow: " << lacznie;
  17.   system("pause");
  18.   return 0;
  19. }