Algoritmo di pianificazione FCFS: cos'è, programma di esempio
Nathaniel Brooks
Cos'è il metodo "primo arrivato, primo servito"?
Primo arrivato, primo servito (FCFS) è un algoritmo di pianificazione del sistema operativo che esegue automaticamente richieste e processi in coda in ordine di arrivo. È l'algoritmo di pianificazione della CPU più semplice e più semplice. In questo tipo di algoritmo, i processi che richiedono prima la CPU ottengono per primi l'allocazione della CPU. Questo è gestito con una coda FIFO. La forma completa del FCFS è First Come First Serve.
Quando il processo entra nella coda pronta, il suo PCB (Process Control Block) è collegato alla coda della coda e, quando la CPU si libera, deve essere assegnato al processo all'inizio della coda.
Caratteristiche del metodo FCFS
- Supporta algoritmi di pianificazione non preventiva e preventiva.
- I lavori vengono sempre eseguiti in base all'ordine di arrivo.
- È facile da implementare e utilizzare.
- Questo metodo ha prestazioni scadenti e il tempo di attesa generale è piuttosto elevato.
Esempio di pianificazione FCFS
Un esempio reale del metodo FCFS è l'acquisto di un biglietto del cinema alla biglietteria. In questo algoritmo di pianificazione, una persona viene servita in base alla modalità della coda. Chi arriva prima in coda acquista prima il biglietto e poi quello successivo. Ciò continuerà fino a quando l'ultima persona in coda non acquisterà il biglietto. Utilizzando questo algoritmo, il processo della CPU funziona in modo simile.
Come funziona FCFS? Calcolo del tempo medio di attesa
Ecco un esempio di cinque processi che arrivano in momenti diversi. Ogni processo ha un tempo di burst diverso.
| Processo | Tempo di scoppio | Orario di arrivo |
|---|---|---|
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Utilizzando l'algoritmo di pianificazione FCFS, questi processi vengono gestiti come segue.
Passo 1) Il processo inizia con P4 che ha tempo di arrivo 0
Passo 2) All'istante=1 arriva P3. P4 è ancora in esecuzione. Quindi, P3 viene mantenuto in coda.
| Processo | Tempo di scoppio | Orario di arrivo |
|---|---|---|
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Passo 3) All'istante=2 arriva P1 che viene mantenuto in coda.
| Processo | Tempo di scoppio | Orario di arrivo |
|---|---|---|
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Passo 4) Al tempo = 3, il processo P4 completa la sua esecuzione.
Passo 5) All'istante=4, P3, che è il primo in coda, inizia l'esecuzione.
| Processo | Tempo di scoppio | Orario di arrivo |
|---|---|---|
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Passo 6) All'istante =5 arriva P2 e viene tenuto in coda.
| Processo | Tempo di scoppio | Orario di arrivo |
|---|---|---|
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Passo 7) Al momento 11 P3 completa la sua esecuzione.
Passo 8) All'istante=11, P1 inizia l'esecuzione. Ha un tempo di burst pari a 6. Completa l'esecuzione nell'intervallo di tempo 17
Passo 9) All'istante=17, P5 inizia l'esecuzione. Ha un tempo di burst pari a 4. Completa l'esecuzione al tempo = 21
Passo 10) All'istante=21, P2 inizia l'esecuzione. Ha un tempo di burst pari a 2. Completa l'esecuzione nell'intervallo di tempo 23
Passo 11) Calcoliamo il tempo medio di attesa per l'esempio sopra.
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
Tempo di attesa medio
= 40/5= 8
Vantaggi dell'FCFS
Ecco i vantaggi/vantaggi derivanti dall'utilizzo dell'algoritmo di pianificazione FCFS:
- La forma più semplice di a Algoritmo di pianificazione della CPU
- Facile da programmare
- Primo arrivato, primo servito
Svantaggi del FCFS
Ecco i contro/svantaggi dell'utilizzo dell'algoritmo di pianificazione FCFS:
- Si tratta di un algoritmo di pianificazione della CPU non preventivo, quindi dopo che il processo è stato assegnato alla CPU, non rilascerà mai la CPU fino al termine dell'esecuzione.
- Il tempo medio di attesa è elevato.
- I processi brevi che si trovano in fondo alla coda devono attendere il completamento del processo lungo in primo piano.
- Non è una tecnica ideale per i sistemi di time-sharing.
- A causa della sua semplicità, FCFS non è molto efficiente.
Sommario
- Definizione: FCFS è un algoritmo di pianificazione del sistema operativo che esegue automaticamente richieste e processi in coda in base all'ordine del loro arrivo
- Supporta la pianificazione non preventiva e preventiva
- algoritmo.
- FCFS sta per First Come First Serve
- Un esempio reale del metodo FCFS è l'acquisto di un biglietto del cinema alla biglietteria.
- È la forma più semplice di un algoritmo di pianificazione della CPU
- Si tratta di un algoritmo di pianificazione della CPU non preventivo, quindi dopo che il processo è stato assegnato alla CPU, non rilascerà mai la CPU fino al termine dell'esecuzione.
