Algoritmo di pianificazione Round Robin con esempio

⚡ Riepilogo intelligente

La pianificazione Round-Robin è l'algoritmo di prelazione per CPU più antico e semplice, in cui ogni processo pronto viene eseguito per un intervallo di tempo fisso in una coda ciclica, garantendo un'esecuzione equa e senza blocchi per il multitasking.

🔄 Definizione: Ciascuna attività pronta viene eseguita a turno per un intervallo di tempo fisso.
️ Quanto temporale: La CPU commuta i processi dopo un intervallo fisso, il quanto di tempo.
️ Equità: Ogni processo riceve lo stesso tempo di CPU, evitando così il blocco per inattività.
🧮 Preventivo: Un processo interrotto viene spostato in fondo alla coda.
✅ vantaggi: Distribuzione equa, nessun effetto convoglio, tempi di risposta prevedibili.
⚠️ Svantaggi: Le prestazioni dipendono dal quanto di tempo e aggiungono un overhead dovuto al cambio di contesto.

Scopri di più

Che cos'è la pianificazione Round-Robin?

Il nome di questo algoritmo deriva dal principio del round robin, secondo cui ogni persona riceve a turno una quota uguale di qualcosa. È l’algoritmo di pianificazione più vecchio e semplice, utilizzato principalmente per il multitasking.

Nella pianificazione Round-robin, ogni attività pronta viene eseguita a turno in una coda ciclica solo per un intervallo di tempo limitato. Questo algoritmo offre anche un'esecuzione dei processi senza blocco (starvation).

Caratteristiche della pianificazione Round-Robin

Ecco le caratteristiche importanti della pianificazione Round-Robin:

Round robin è un algoritmo preemptive.
La CPU passa al processo successivo dopo un intervallo di tempo fisso, chiamato quanto di tempo/fetta di tempo.
Il processo che viene interrotto viene aggiunto alla fine della coda.
Il round robin è un modello ibrido basato sull'orologio.
L'intervallo di tempo dovrebbe essere minimo, ovvero quello assegnato a una specifica attività da elaborare. Tuttavia, può variare da sistema operativo a sistema operativo.
Si tratta di un algoritmo in tempo reale che reagisce all'evento entro un limite di tempo specifico.
Il round robin è uno degli algoritmi più antichi, equi e semplici.
Si tratta di un metodo di pianificazione ampiamente utilizzato nei sistemi operativi tradizionali.

Esempio di pianificazione round-robin

Consideriamo i seguenti tre processi:

Coda di elaborazione	Tempo di scoppio
P1	4
P2	3
P3	5

Passo 1) L'esecuzione inizia con il processo P1, che ha un tempo di burst 4. Qui ogni processo viene eseguito per 2 secondi. P2 e P3 sono ancora in coda d'attesa.

Passo 2) All'istante t = 2, P1 viene aggiunto alla fine della coda e P2 inizia l'esecuzione.

Passo 3) All'istante t = 4, P2 viene interrotto e aggiunto alla fine della coda. P3 inizia l'esecuzione.

Passo 4) All'istante t = 6, P3 viene interrotto e aggiunto alla fine della coda. P1 inizia l'esecuzione.

Passo 5) All'istante t=8, P1 ha un tempo di esecuzione di 4. L'esecuzione è stata completata. P2 inizia l'esecuzione.

Passo 6) P2 ha un tempo di esecuzione di 3. È già stato eseguito per 2 intervalli. Al tempo = 9, P2 completa l'esecuzione. Quindi, P3 inizia l'esecuzione fino al suo completamento.

Passo 7) Calcoliamo il tempo di attesa medio per l'esempio sopra riportato.

Wait time
P1 = 0 + 4 = 4
P2 = 2 + 4 = 6
P3 = 4 + 3 = 7

Vantaggi della programmazione a rotazione (Round-robin)

Ecco i vantaggi/benefici del metodo di pianificazione Round-robin:

Non deve affrontare i problemi della fame o dell'effetto convoglio.
Tutti i lavori ricevono una giusta allocazione di CPU.
Gestisce tutti i processi senza alcuna priorità.
Se conosci il numero totale di processi nella coda di esecuzione, puoi anche ipotizzare il tempo di risposta nel caso peggiore per lo stesso processo.
Questo metodo di pianificazione non dipende dal tempo di esecuzione. Per questo motivo è facilmente implementabile sul sistema.
Una volta che un processo viene eseguito per un determinato periodo di tempo, il processo viene anticipato e un altro processo viene eseguito per quel determinato periodo di tempo.
Consente al sistema operativo di utilizzare il metodo di commutazione di contesto per salvare lo stato dei processi interrotti.
Offre le migliori prestazioni in termini di tempo medio di risposta.

Svantaggi della pianificazione round-robin

Ecco gli svantaggi/gli inconvenienti dell'utilizzo della pianificazione Round-robin:

Se il tempo di slicing del sistema operativo è basso, la potenza di elaborazione del processore si ridurrà.
Questo metodo impiega più tempo nel cambio di contesto.
Le sue prestazioni dipendono fortemente dal quanto temporale.
Non è possibile stabilire priorità per i processi.
La programmazione round-robin non attribuisce priorità speciale ai compiti più importanti.
Diminuisce la comprensione.
Un quanto di tempo inferiore comporta un maggiore sovraccarico dovuto al cambio di contesto nel sistema.
Trovare il quanto di tempo corretto è un compito piuttosto difficile in questo sistema.

Latenza nel caso peggiore

Questo termine viene utilizzato per il tempo massimo impiegato per l'esecuzione di tutte le attività.

dt = Indica il tempo di rilevamento quando un'attività viene aggiunta all'elenco
st = Indica il tempo di commutazione da un'attività all'altra
et = Indica il tempo di esecuzione del compito

Formula:

^T_worst = {(dt_i+ st_i+ et_i ), + (dt_i+ st_i+ et_i )₂ +...+ (dt_i+ st_i + et_i )_N., + (dt_i+ st_i + et_i  + et_i) N} + t_ISR
t_ISR = sum of all execution times

DOMANDE FREQUENTI

Il quanto di tempo, o fetta di tempo, è il tempo fisso di CPU in cui ogni processo viene eseguito prima di essere interrotto. Un valore troppo grande si comporta come FCFS (First-Come, First-Served); un valore troppo piccolo aggiunge un pesante overhead dovuto al cambio di contesto.

FCFS esegue ogni processo fino al completamento nell'ordine di arrivo ed è non preemptive. Round Robin è preemptive: assegna a ciascun processo un intervallo di tempo fisso e lo fa scorrere ciclicamente attraverso la coda, migliorando il tempo di risposta e impedendo che i processi lunghi blocchino gli altri.

Poiché ogni processo viene inserito in una coda ciclica e riceve a turno un intervallo di tempo fisso, nessun processo viene saltato o ritardato indefinitamente, quindi ognuno alla fine ottiene tempo CPU indipendentemente dalla sua durata o dall'ordine di arrivo.

L'intelligenza artificiale e l'apprendimento automatico possono prevedere il comportamento dei processi e i modelli di carico di lavoro per ottimizzare le decisioni di pianificazione in tempo reale. Invece di una politica fissa, il sistema può adattare dinamicamente le priorità e gli intervalli di tempo, migliorando l'utilizzo della CPU, la produttività e i tempi di risposta.

Sì. I modelli di intelligenza artificiale possono analizzare i tempi di burst passati e il carico del sistema per suggerire un intervallo di tempo ottimale e regolarlo al variare delle condizioni. Questo bilancia meglio il sovraccarico dovuto al cambio di contesto con il tempo di risposta rispetto a un singolo valore fisso.