Algoritmo di pianificazione FCFS: cos'è, programma di esempio

By: Nathaniel Brooks Nathaniel Brooks
Hours aggiornato

⚡ Riepilogo intelligente

La pianificazione First Come First Serve esegue i processi esattamente nell'ordine in cui raggiungono la coda dei processi pronti, utilizzando un semplice approccio FIFO non preemptive che lo rende l'algoritmo di pianificazione della CPU più facile da implementare per un sistema operativo.

  • 🔄 Definizione: FCFS assegna la CPU al processo che la richiede per primo, gestendo la coda dei processi pronti secondo una struttura FIFO (first-in, first-out).
  • ⚙️ Natura: FCFS non è preemptive, quindi un processo in esecuzione mantiene la CPU occupata fino al termine dell'intero tempo di esecuzione.
  • ️ Analogia: Come in una coda alla biglietteria, chi arriva per primo viene servito per primo, mentre chi arriva dopo aspetta il proprio turno.
  • 📊 Calcolo: Il tempo di attesa medio è trovato da subtraccalcolando il tempo di arrivo di ciascun processo a partire dal suo tempo di inizio, quindi calcolando la media su tutti i processi.
  • ???? Effetto convoglio: Un processo lungo nella fase iniziale costringe i lavori più brevi ad attendere, aumentando il tempo medio di attesa e compromettendo le prestazioni.
  • 🤖 Angolo dell'IA: L'apprendimento automatico prevede i tempi di esecuzione per migliorare la pianificazione, e Copilot aiuta a scrivere e testare rapidamente il codice FCFS (First-Come, First-Served).
Scopri di più

Algoritmo di pianificazione FCFS in Operasistema di ting

Cos'è il metodo "primo arrivato, primo servito"?

Primo arrivato, primo servito (FCFS) FCFS è un algoritmo di pianificazione del sistema operativo che esegue automaticamente le richieste e i processi in coda nell'ordine in cui arrivano. È l'algoritmo di pianificazione della CPU più semplice e basilare. In questo tipo di algoritmo, il processo che richiede per primo la CPU ottiene per primo l'allocazione della CPU. Questo viene gestito tramite una coda FIFO. L'acronimo FCFS sta per First Come First Serve (Primo arrivato, primo servito).

Quando un processo entra nella coda dei processi pronti, il suo PCB (Process Control Block) viene collegato alla coda. Pertanto, quando la CPU si libera, viene assegnata al processo in cima alla coda.

Caratteristiche del metodo FCFS

Le principali caratteristiche del metodo "Primo arrivato, primo servito" sono elencate di seguito:

  • È una non preventivo algoritmo di pianificazione, in modo che un processo mantenga la CPU occupata fino al completamento del suo tempo di esecuzione.
  • 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 concreto del metodo FCFS (First-Come, First-Served) è l'acquisto di un biglietto del cinema alla biglietteria. In questo algoritmo di pianificazione, le persone vengono servite in base all'ordine di arrivo in coda. La persona che arriva per prima acquista il biglietto, seguita dalla successiva. Questo processo continua fino a quando l'ultima persona in coda non ha acquistato il biglietto. Utilizzando questo algoritmo, il processo della CPU funziona in modo simile.

Come funziona FCFS? Calcolo del tempo medio di attesa

Per comprendere come l'algoritmo pianifica i processi, ecco un esempio di cinque processi che arrivano in momenti diversi. Ogni processo ha un tempo di esecuzione 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.

Esempio di pianificazione FCFS, passaggio 1

Passo 2) All'istante=1 arriva P3. P4 è ancora in esecuzione. Quindi, P3 viene mantenuto in coda.

Esempio di pianificazione FCFS, passaggio 2

Passo 3) Al tempo t=2, P1 arriva e viene mantenuto in coda.

Esempio di pianificazione FCFS, passaggio 3

Passo 4) Al tempo t=3, il processo P4 completa la sua esecuzione.

Esempio di pianificazione FCFS, passaggio 4

ARTICOLI CORRELATI

Passo 5) All'istante=4, P3, che è il primo in coda, inizia l'esecuzione.

Esempio di pianificazione FCFS, passaggio 5

Passo 6) Al tempo t=5, P2 arriva e viene messo in coda.

Esempio di pianificazione FCFS, passaggio 6

Passo 7) All'istante t=11, P3 completa la sua esecuzione.

Esempio di pianificazione FCFS, passaggio 7

Passo 8) All'istante t=11, P1 inizia l'esecuzione. Ha un tempo di esecuzione di 6, quindi completa l'esecuzione all'intervallo di tempo 17.

Esempio di pianificazione FCFS, passaggio 8

Passo 9) Al tempo t=17, P5 inizia l'esecuzione. Ha un tempo di esecuzione di 4, quindi completa l'esecuzione al tempo t=21.

Esempio di pianificazione FCFS, passaggio 9

Passo 10) All'istante t=21, P2 inizia l'esecuzione. Ha un tempo di esecuzione di 2, quindi completa l'esecuzione all'intervallo di tempo 23.

Esempio di pianificazione FCFS, passaggio 10

Passo 11) Ora calcoliamo il tempo medio di attesa per l'esempio precedente.

tempo medio di attesa nella programmazione FCFS

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

Tempo medio di attesa = (0 + 2 + 9 + 13 + 16) / 5 = 40 / 5 = 8

Calcolo del tempo medio di attesa nella programmazione FCFS

Vantaggi dell'FCFS

Ecco i vantaggi e i benefici derivanti dall'utilizzo dell'algoritmo di pianificazione FCFS:

Svantaggi del FCFS

Ecco gli svantaggi e i punti deboli dell'utilizzo dell'algoritmo di pianificazione FCFS:

  • Si tratta di un algoritmo di pianificazione della CPU non preemptive, quindi una volta che un processo è stato assegnato alla CPU, non la rilascerà finché non avrà terminato l'esecuzione.
  • Il tempo medio di attesa è elevato.
  • I processi brevi in ​​fondo alla coda devono attendere che il processo lungo in testa termini.
  • Non è una tecnica ideale per i sistemi time-sharing.
  • A causa della sua semplicità, FCFS non è molto efficiente.

DOMANDE FREQUENTI

L'algoritmo First Come First Serve (FIFS) non preemptive. Una volta che un processo ottiene la CPU, viene eseguito fino al termine del suo ciclo di elaborazione, quindi lo scheduler non può interromperlo per eseguire un processo appena arrivato o più breve.

L'effetto convoglio si verifica quando diversi processi brevi attendono dietro un singolo processo lungo in testa alla coda. Questo singolo processo di lunga durata aumenta il tempo medio di attesa e riduce la produttività complessiva della CPU.

Il tempo di completamento (turnaround time) è pari al tempo di esecuzione meno il tempo di arrivo di ciascun processo. Misura il tempo totale che un processo trascorre nel sistema, dal suo arrivo fino al termine dell'esecuzione sulla CPU.

Il servizio FCFS viene effettuato in ordine di arrivo, Prima il lavoro più breve serve prima l'impulso più piccolo per ridurre i tempi di attesa e Round Robin assegna a ciascun processo una porzione di tempo fissa per la condivisione del tempo.

L'algoritmo FCFS puro non causa starvation, perché ogni processo raggiunge prima o poi la testa della coda FIFO. Tuttavia, i processi lunghi possono comunque ritardare notevolmente quelli brevi a causa dell'effetto convoglio.

L'algoritmo FCFS ha una complessità temporale di O(n) quando i processi sono già ordinati in base all'arrivo, poiché ciascuno viene pianificato una sola volta. L'ordinamento preliminare degli arrivi non ancora ordinati in base al tempo di arrivo aggiunge un passaggio di complessità O(n log n).

I modelli di apprendimento automatico prevedono i picchi di attività dei processi e selezionano o ottimizzano le politiche di pianificazione per ridurre il tempo medio di attesa e il consumo energetico. I ricercatori applicano questi sistemi di pianificazione basati sull'intelligenza artificiale nei server cloud e nei data center.

Sì. GitHub Copilot può generare codice FCFS in C, Java, o Python con calcoli dei tempi di attesa e dei tempi di completamento. Verificare sempre l'ordinamento in base all'orario di arrivo, i criteri di spareggio e le formule di media prima di considerare attendibile il risultato.

Riassumi questo post con: