Algorytm C-SCAN

Wstęp

Algorytm C-SCAN optymalizuje działanie algorytmu planowania SCAN poprzez dodanie możliwości przeskoczenia na drugi koniec danych. Oczywiście ma to również wpływ na czas obsługi wszystkich zdarzeń. W tym artykule zostaną wskazane różnice między wersją C-SCAN, a SCAN oraz jak zaimplementować nowy algorytm.

Opis

Głowica dysku w algorytmie SCAN podróżowała w określonym kierunku obsługując napotkane żądania. Po dotarciu do brzegu kierunek głowicy zmieniał się na przeciwny. Jednak w przypadku algorytmu C-SCAN głowica po dotarciu na brzeg przeskakuje na przeciwny brzeg i nie zmienia kierunku. Takie rozwiązanie nie wpływa znacząco na czas obsługi żądań. Wiadomo, że głowica przechodzi przez wszystkie pozycje, więc w czasie jednego cyklu pewne jest, że żądanie zostanie obsłużone.

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 głowica wraca na drugi brzeg i obsługuje pozostałe żądania.

W powyższym przykładzie głowica musi wykonać dokładnie 140 skoków. Nie jest to nadal najbardziej optymalna ścieżka. Jednak takie rozwiązanie gwarantuje, że każde żądanie zostanie obsłużone w trakcie jednego cyklu przejścia głowicy. Dzięki temu o wiele łatwiej jest przewidzieć np. na jak długo wykonywany program powinien zostać wstrzymany.

Analiza Zadania

Algorytm naśladujący algorytm C-SCAN musi przetrzymywać na bieżąco pozycję głowicy, a następnie wybierać kolejne żądania, które mają pozycję większą niż aktualną pozycję głowicy. Jeśli algorytm przejrzy wszystkie elementy tablicy to powinien zresetować pozycję głowicy na 0 i rozpocząć przeszukiwanie bufora żądań od nowa.

Implementacja

Kolejność

Funkcja KolejnoscCSCAN() zwraca dla podanej listy lokalizacji kolejność w jakiej żądania zostaną obsłużone. Opcjonalnie można ustawić poz - aktualną pozycję głowicy.

1. def KolejnoscCSCAN(dane, poz = 0, wGore = True):
2.   wynik = []
3.   bufor = dane[:]
4.   i = 0
5.   while (len(bufor) > 0):
6.     if bufor[i] > poz:
7.       wynik.append(bufor[i])
8.       poz = bufor[i]
9.       bufor.pop(i)
10.     else:
11.       i += 1
12.    
13.     if i >= len(bufor):
14.       i = 0
15.       poz = 0
16.   return wynik

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. def SkokowCSCAN(lokalizacje, max, poz = 0):
2.   lacznie = 0;
3.   dane = KolejnoscCSCAN(lokalizacje, poz)
4.   for i in range(len(dane)):
5.     if dane[i] > poz:
6.       lacznie += abs(dane[i] - poz)
7.     else:
8.       lacznie += max - abs(dane[i] - poz)
9.     poz = dane[i]
10.   return lacznie

Testowanie funkcji

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

1. print("Podaj lokalizacje:")
2. lokalizacje = [int(x) for x in input().split()]
3. kolejnosc = KolejnoscCSCAN(lokalizacje)
4. max = int(input("Podaj zakres lokalizacji:\n max = "))
5. print("Kolejność obsługi:")
6. for a in kolejnosc:
7.   print(a, end=' ')
8. lacznie = SkokowCSCAN(lokalizacje, max)
9. print("\nPotrzebnych skoków:", lacznie)

• Kod źródłowy Implementacja