Strona główna » Algorytmy » Planowanie Pracy Dysku » Metoda Planowania FCFS
 

Metoda Planowania FCFS

https://mattomatti.com/d01

Algorytm

Metoda Planowania FCFS (ang. first come, first serve) jest to algorytm, który ma za zadanie obsługiwać żądania odczytu danych z dysku. Zasada jego działania jest bardzo podobna do kolejki FIFO. Mianowicie kolejne żądanie są obsługiwane w takiej samej kolejności w jakiej przyszły. Do zalet takiego rozwiązania należy zaliczyć fakt, że każde żądanie ma szansę zostać obsłużone i ma na to jednakową szansę jak pozostałe. Z drugiej strony algorytm ten w żaden sposób nie optymalizuje pobierania danych.

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}. Dysk obsłużony je w takiej kolejności w jakiej nadeszły tak jak to pokazuje poniższy schemat:

Algorytm FCFS

Jak można zauważyć dysk porusza głowicą raz w lewo, a raz w prawo, a cały proces możnaby zoptymalizować obsługując np. te bliższe niż dalsze elementy. W tym przypadku dysk musi wykonać 140 skoków pomiędzy kolejnymi segmantami, aby odpowiedzieć na wszystkie żądania. Czas oczekiwania na odpowiedź wynosi tyle ile elementów było wcześniej w kolejce. Przyjmując, że co pewien okres czasu t dysk przesuwa głowicę o 1 segment można policzyć, że średni czas odczytania segmentu wynosi 21t (suma 140 / 7 = 20 czyli czas przesuwania oraz 1 czyli czas odczytu).

Implementacja

Kolejność

Funkcja kolejnoscFCFS() dla danej listy zwraca kolejność obsługiwanych zdarzeń. W tym przypadku jej działanie polega na skopiowaniu przekazanej listy.

  1. vector<int> kolejnoscFCFS(vector<int> lokalizacje) {
  2.   vector<int> wynik;
  3.   for each(int a in lokalizacje) {
  4.     wynik.push_back(a);
  5.   }
  6.   return wynik;
  7. }

Ścieżka

Funkcja skokowFCFS() oblicza ile skoków musi łącznie wykonać głowica dysku, aby odpowiedzieć na wszystkie zapytania. Dodatkowy parametr poz pozwala określić aktualne położenie głowicy. Domyślnie wartość ta jest ustawiona na 0.

  1. int skokowFCFS(vector<int> lokalizacje, int poz = 0) {
  2.   int lacznie = 0;
  3.   for (int i = 0; i < lokalizacje.size(); i++) {
  4.     lacznie += abs(lokalizacje[i] - poz);
  5.     poz = lokalizacje[i];
  6.   }
  7.   return lacznie;
  8. }

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 = kolejnoscFCFS(lokalizacje);
  12.   cout << "Kolejnosc obslugi:\n";
  13.   for each (int a in lokalizacje)
  14.     cout << a << " ";
  15.   int lacznie = skokowFCFS(lokalizacje);
  16.   cout << "\nPotrzebnych skokow: " << lacznie;
  17.   system("pause");
  18.   return 0;
  19. }