Algorytm planowania FCFS: co to jest, przykładowy program
Nathaniela Brooksa
Na czym polega metoda „kto pierwszy, ten lepszy”?
Kto pierwszy, ten lepszy (FCFS) jest algorytmem 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 procesy, które najpierw żądają procesora, jako pierwsze otrzymują przydział procesora. Jest to zarządzane za pomocą kolejki FIFO. Pełna forma FCFS to First Come First Serve.
Gdy proces trafia do kolejki gotowości, jego PCB (blok kontroli procesu) jest łączony z końcem kolejki i gdy procesor staje się wolny, powinien zostać przydzielony do procesu na początku kolejki.
Charakterystyka metody FCFS
- Obsługuje algorytm planowania niewywłaszczającego i wywłaszczającego.
- 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 planowania FCFS
Prawdziwym przykładem metody FCFS jest kupowanie biletu do kina w kasie biletowej. W tym algorytmie planowania osoba obsługiwana jest zgodnie z kolejką. Osoba, która stanie w kolejce jako pierwsza, najpierw kupuje bilet, a następnie następną. Dzieje się tak do momentu, aż ostatnia osoba w kolejce kupi bilet. Używając tego algorytmu, proces procesora działa w podobny sposób.
Jak działa FCFS? Obliczanie średniego czasu oczekiwania
Oto przykład pięciu procesów przychodzących w różnym czasie. Każdy proces ma inny czas wybuchu.
| 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.
| Przetwarzanie | Czas wybuchu | Czas przybycia |
|---|---|---|
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Krok 3) O godzinie 2 przybywa P1, który jest trzymany w kolejce.
| Przetwarzanie | Czas wybuchu | Czas przybycia |
|---|---|---|
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Krok 4) W chwili = 3 proces P4 kończy swoje działanie.
Krok 5) O godzinie = 4, P3, który jest pierwszy w kolejce, rozpoczyna wykonanie.
| Przetwarzanie | Czas wybuchu | Czas przybycia |
|---|---|---|
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Krok 6) O godzinie =5 przybywa P2 i jest on trzymany w kolejce.
| Przetwarzanie | Czas wybuchu | Czas przybycia |
|---|---|---|
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Krok 7) W czasie 11 P3 kończy wykonywanie.
Krok 8) W chwili = 11 P1 rozpoczyna wykonanie. Ma czas serii wynoszący 6. Kończy wykonywanie w odstępie czasu 17
Krok 9) W chwili = 17, P5 rozpoczyna wykonywanie. Ma czas serii wynoszący 4. Kończy wykonywanie w czasie = 21
Krok 10) W chwili = 21 P2 rozpoczyna wykonanie. Ma czas serii wynoszący 2. Kończy wykonywanie w odstępie czasu 23
Krok 11) Obliczmy średni czas oczekiwania dla powyższego przykładu.
Waiting time = Start time - Arrival time
P4 = 0-0 = 0
P3 = 3-1 = 2
PI = 11-2 = 9
P5= 17-4 = 13
P2= 21-5= 16
Średni czas oczekiwania
= 40/5 = 8
Zalety FCFS
Oto zalety/korzyści korzystania z algorytmu planowania FCFS:
- Najprostsza forma a Algorytm planowania procesora
- Łatwe do zaprogramowania
- Kto pierwszy ten lepszy
Wady FCFS
Oto wady/wady korzystania z algorytmu planowania FCFS:
- Jest to algorytm planowania procesora z wywłaszczaniem, więc po przydzieleniu procesu do procesora, nigdy nie zwolni on procesora, dopóki nie zakończy wykonywania.
- Średni czas oczekiwania jest wysoki.
- Krótkie procesy znajdujące się na końcu kolejki muszą poczekać 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.
Podsumowanie
- Definicja: FCFS to algorytm planowania systemu operacyjnego, który automatycznie wykonuje kolejkowane żądania i procesy według kolejności ich nadejścia.
- Obsługuje planowanie niewywłaszczające i wywłaszczające
- algorytm.
- FCFS oznacza „kto pierwszy, ten lepszy”.
- Prawdziwym przykładem metody FCFS jest kupowanie biletu do kina w kasie biletowej.
- Jest to najprostsza forma algorytmu planowania procesora
- Jest to algorytm planowania procesora z wywłaszczaniem, więc po przydzieleniu procesu do procesora, nigdy nie zwolni on procesora, dopóki nie zakończy wykonywania.
