Metoda Planowania C-LOOK

Wstęp

Algorytm C-LOOK to najoptymalniejszy algorytm do planowania pracy dysku. Wykorzystuje on najlepsze cechy algorytmów SCAN oraz SSTF. Wykorzystuje on szybkie przechodzenie pomiędzy miejscami na dysku. W tym artykule zostanie przedstawione jak zasymulować taki algorytm na podanym zestawie żądań odczytu danych z dysku.

Opis

W celu zrozumienia idei algorytmu C-LOOK należy wrócić do algorytmu SCAN, gdzie głowica przeszukiwała dysk idąc w jednym kierunku, następnie przeciwnym itd. obsługując po drodze napotkane żądania. Podobnie działa algorytm C-SCAN, ale tym razem po pełnym przejściu mógł wrócić na początek, albo zacząć przeszukiwać w przeciwną stronę. Zależało to od najbliższego żądania w buforze. Jednak za każdym razem głowica musiała zrobić pełne przejście. Dopiero algorytm C-LOOK daje możliwość głowicy zakończyć drogą w jedną stronę szybciej niż po dojściu na koniec.

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 C-SCAN

Algorytm wpierw przechodzi kolejno obsługuje żądania 25, 35, 60 oraz 80 następnie przechodząc do końca prawej strony, ale nie dochodzi do końca, a przechodzi do następnych żądań od razu. W tym przypadku algorytm potrzebuje 140 przeskoków, aby obsłużyć wszystkie żądania.

Implementacja

Kolejność

Funkcja KolejnoscCLOOK() zwraca dla podanej listy lokalizacji kolejność w jakiej żądania zostaną obsłużone. Argument poz - określa początkową pozycję głowicy.

1. vector<int> KolejnoscCLOOK(vector<int> dane, int poz = 0) {
2.   vector<int> wynik;
3.   vector<int> bufor(dane);
4.   int i = 0;
5.   while (bufor.size() > 0) {
6.     if (bufor[i] > poz) {
7.       wynik.push_back(bufor[i]);
8.       poz = bufor[i];
9.       bufor.erase(bufor.begin() + i, bufor.begin() + i + 1);
10.     }
11.     else {
12.       i++;
13.     }
15.     if (i >= bufor.size()) {
16.       i = 0;
17.       poz = 0;
18.     }
19.   }
20.   return wynik;
21. }

Algorytm działa w pętli, aż do usunięcia wszystkich żądań z bufora. Żądanie jest obsługiwane, a następnie usuwane tylko pod warunkiem, że aktualnie przeglądane żądanie ma pozycję zaraz po aktualnej pozycji głowicy. Należy pamiętać, aby indeks przeglądanego żądania zwiększyć tylko, gdy aktualne żądanie nie zostaje obsłużone.

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. W tym przypadku należy pamiętać, że jeśli kolejna pozycja jest mniejsza niż poprzednia to głowica musiała przejść do końca i dopiero od pozycji 0 do lokalizacji żądania.

1. int SkokowCLOOK(vector<int> lokalizacje, int max, int poz = 0) {
2.   int lacznie = 0;
3.   vector<int> dane = KolejnoscCLOOK(lokalizacje, poz);
4.   for (int i = 0; i < dane.size(); i++) {
5.     int roznica = abs(dane[i] - poz);
6.     lacznie += min(roznica, max - roznica);
7.     poz = dane[i];
8.   }
9.   return lacznie;
10. }

Testowanie funkcji

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

1. int main() {
2.   vector<int> lokalizacje;
3.   int n, tmp, max;
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.   cout << "Podaj zakres lokalizacji:\n max = ";
12.   cin >> max;
13.   vector<int> kolejnosc = KolejnoscCLOOK(lokalizacje);
14.   cout << "Kolejnosc obslugi:\n";
15.   for each (int a in kolejnosc)
16.     cout << a << " ";
17.   int lacznie = SkokowCLOOK(lokalizacje, max);
18.   cout << "\nPotrzebnych skokow: " << lacznie;
19.   system("pause");
20.   return 0;
21. }

• Kod źródłowy Implementacja