Metoda Planowania SSTF

Algorytm

Metoda Planowania SSTF (ang. shortest seek time first) ma za zadanie zoptymalizować prace głowicy dysku. Jest ona zdecydowanie lepsza niż FCFS, ale niesie za sobą pewne ryzyko. W metodzie SSTF w pierwszej kolejności odczytywane są segmenty do których głowica musi się najmniej przesunąć. Zaletą tego algorytmu jest fakt, że dzięki temu głowica wykonuje najkrótszą możliwą drogę, aby odczytać wszystkie segmenty. Niestety oznacza to, że niektóre żądania mogą zostać zagłodzone. Nie jest to algorytm optymalny.

Przykład

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, 30}. Początkowo głowica znajduje się nad segmentem 30. Schemat pokazujący skuteczność metody jest przedstawiony poniżej:

Algorytm SSTF

Jak można zauważyć głowica początkowo znajduje się po lewej stronie segmentów i najpierw wykonywane są wszystkie żądania z tamtej części. Dopiero po obsłużeniu algorytm przechodzi do tych bardziej na prawo. Algorytm jest skuteczny, ponieważ potrzebuje jedynie 70 skoków (prawie 2 razy mniej niż dla algorytmu FCFS!) czyli głowica średnio przeskakuje 70/7 = 10 segmentów. Zauważmy jednak, że dysk cały czas przyjmuje nowe żądania. Może się okazać, że cały czas będą żądania z jednej strony dysku, więc żądania z przeciwnej strony bardzo długo nie zostaną obsłużone.

Implementacja

Kolejność

Funkcja kolejnoscSSTF() musi wiedzieć, które żądanie znajduje się najbliżej głowicy, a więc warto napisać wpierw funkcję najblizszy(), która dla danej listy dane zwróci indeks wartości tej, która najmniej różni się od x.

1. int najblizszy(vector<int> dane, int x) {
2.   int imin = 0;
3.   for (int i = 1; i < dane.size(); i++) {
4.     if (abs(x - dane[i]) < abs(x - dane[imin])) {
5.       imin = i;
6.     }
7.   }
8.   return imin;
9. }

Początkowo przyjmujemy, że pierwszy element jest nabliższy, a następnie wśród pozostałych wartości szukamy tej, której odległość od x jest mniejsza. Jeśli taka się znajdzie to należy zaktualizować indeks. Na koniec wystarczy zwrócić znaleziony indeks.

Natomiast funkcja kolejnoscSSTF() używając funkcji wybierze kolejny segment do odczytania, dołączy do wyniku i usunie z podanej listy. Oczywiście w każdej kolejnej iteracji należy pamiętać o aktualizacji aktualnej pozycji głowicy. Na koniec zostaje zwrócona wyznaczona lista.

1. vector<int> kolejnoscSSTF(vector<int> lokalizacje, int poz = 0) {
2.   vector<int> wynik;
3.   while (lokalizacje.size() > 0) {
4.     int i = najblizszy(lokalizacje, poz);
5.     wynik.push_back(lokalizacje[i]);
6.     lokalizacje.erase(lokalizacje.begin() + i, lokalizacje.begin() + i + 1);
7.     poz = wynik[wynik.size() - 1];
8.   }
9.   return wynik;
10. }

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 skokowSSTF(vector<int> lokalizacje, int poz = 0) {
2.   int lacznie = 0;
3.   vector<int> dane = kolejnoscSSTF(lokalizacje, poz);
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 = kolejnoscSSTF(lokalizacje, 30);
12.   cout << "Kolejnosc obslugi:\n";
13.   for each (int a in kolejnosc)
14.     cout << a << " ";
15.   int lacznie = skokowSSTF(lokalizacje, 30);
16.   cout << "\nPotrzebnych skokow: " << lacznie;
17.   system("pause");
18.   return 0;
19. }

• Kod źródłowy Implementacja