Algorytm planowania FCFS: co to jest, przykładowy program
Nathaniela Brooksa
⚡ Inteligentne podsumowanie
Harmonogramowanie oparte na zasadzie „pierwszy przyszedł, pierwszy obsłużony” uruchamia procesy w dokładnej kolejności, w jakiej docierają do kolejki zadań gotowych do wykonania, wykorzystując proste, niewywłaszczające podejście FIFO. Dzięki temu jest to najłatwiejszy do zaimplementowania algorytm harmonogramowania procesora w systemie operacyjnym.
Na czym polega metoda „kto pierwszy, ten lepszy”?
Kto pierwszy, ten lepszy (FCFS) to algorytm planowania systemu operacyjnego, który automatycznie wykonuje kolejkowane żądania i procesy w kolejności ich nadejścia. Jest to najłatwiejszy i najprostszy algorytm planowania procesora. W tym typie algorytmu proces, który jako pierwszy zażąda procesora, otrzymuje go jako pierwszy. Jest to zarządzane za pomocą kolejki FIFO. Pełna nazwa FCFS to First Come First Serve (pierwszy przyszedł, pierwszy obsłużony).
Gdy proces wchodzi do kolejki gotowych procesów, jego blok PCB (Process Control Block) jest połączony z końcem kolejki. W ten sposób, gdy procesor staje się wolny, jest przypisywany do procesu na początku kolejki.
Charakterystyka metody FCFS
Poniżej przedstawiono główne cechy metody „kto pierwszy, ten lepszy”:
- Jest nieprewencyjny algorytm planowania, dzięki któremu proces utrzymuje procesor do momentu zakończenia przydzielonego mu czasu.
- Zadania są zawsze wykonywane na zasadzie „kto pierwszy, ten lepszy”.
- Jest łatwy do wdrożenia i użytkowania.
- Ta metoda jest mało wydajna, a ogólny czas oczekiwania jest dość długi.
Przykład harmonogramowania FCFS
Przykładem zastosowania metody FCFS w praktyce jest zakup biletu do kina w kasie biletowej. W tym algorytmie harmonogramowania, osoby są obsługiwane zgodnie z kolejnością w kolejce. Osoba, która pojawi się pierwsza w kolejce, kupuje bilet jako pierwsza, a następnie kolejna. Proces ten trwa do momentu, aż ostatnia osoba w kolejce kupi bilet. W przypadku tego algorytmu, proces procesora działa w podobny sposób.
Jak działa FCFS? Obliczanie średniego czasu oczekiwania
Aby zrozumieć, jak algorytm planuje procesy, poniżej przedstawiono przykład pięciu procesów przybywających w różnym czasie. Każdy proces ma inny czas realizacji.
| Przetwarzanie | Czas wybuchu | Czas przybycia |
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Używając algorytmu planowania FCFS, procesy te są obsługiwane w następujący sposób.
Krok 1) Proces rozpoczyna się od P4, którego czas przybycia wynosi 0.
Krok 2) W chwili = 1 przybywa P3. P4 nadal działa. Dlatego P3 jest trzymany w kolejce.
Krok 3) W czasie=2 przybywa P1 i zostaje umieszczony w kolejce.
Krok 4) W czasie 3 proces P4 kończy swoje wykonywanie.
Krok 5) O godzinie = 4, P3, który jest pierwszy w kolejce, rozpoczyna wykonanie.
Krok 6) W czasie 5 przybywa P2 i zostaje umieszczony w kolejce.
Krok 7) W czasie 11 P3 kończy wykonywanie.
Krok 8) W czasie 11 P1 rozpoczyna wykonywanie. Ma on czas burst równy 6, więc kończy wykonywanie w przedziale czasowym 17.
Krok 9) W czasie 17 P5 rozpoczyna wykonywanie. Ma czas burst równy 4, więc kończy wykonywanie w czasie 21.
Krok 10) W czasie 21 P2 rozpoczyna wykonywanie. Ma on czas burst równy 2, więc kończy wykonywanie w przedziale czasowym 23.
Krok 11) Obliczmy teraz średni czas oczekiwania dla powyższego przykładu.
Waiting time = Start time - Arrival time
P4 = 0 – 0 = 0
P3 = 3 – 1 = 2
P1 = 11 – 2 = 9
P5 = 17 – 4 = 13
P2 = 21 – 5 = 16
Średni czas oczekiwania = (0 + 2 + 9 + 13 + 16) / 5 = 40 / 5 = 8
Zalety FCFS
Oto zalety i korzyści wynikające ze stosowania algorytmu planowania FCFS:
- Jest to najprostsza forma Algorytm planowania procesora.
- Łatwo jest programować.
- Obowiązuje prosta zasada „kto pierwszy, ten lepszy”.
Wady FCFS
Oto wady i niedogodności wynikające ze stosowania algorytmu planowania FCFS:
- Jest to algorytm planowania zadań procesora bez wywłaszczania, co oznacza, że po przydzieleniu procesu do procesora, nie jest on zwalniany, dopóki proces nie zakończy wykonywania.
- Średni czas oczekiwania jest długi.
- Krótkie procesy znajdujące się na końcu kolejki muszą czekać na zakończenie długiego procesu z przodu.
- Nie jest to idealna technika dla systemów z podziałem czasu.
- Ze względu na swoją prostotę FCFS nie jest zbyt wydajny.
