Cos’è il Round-Robin Scheduling?
Il nome di questo algoritmo deriva dal principio del round-robin, dove ogni persona ottiene una parte uguale di qualcosa a turno. È il più antico e semplice algoritmo di scheduling, che è principalmente usato per il multitasking.
Nella programmazione Round-robin, ogni compito pronto viene eseguito a turno solo in una coda ciclica per una fetta di tempo limitata. Questo algoritmo offre anche un’esecuzione senza fame dei processi.
In questo tutorial sul sistema operativo, imparerai:
- Che cos’è il Round-Robin Scheduling?
- Caratteristiche del Round-Robin Scheduling
- Esempio di Round-robin Scheduling
- Vantaggio del Round-robin Scheduling
- Svantaggi del Round-robin Scheduling
- Worst Case Latency
Caratteristiche del Round-Robin Scheduling
Ecco le caratteristiche importanti del Round-Robin Scheduling:
- Round robin è un algoritmo pre-emptive
- La CPU viene spostata al processo successivo dopo un intervallo di tempo fisso, che è chiamato time quantum/time slice.
- Il processo che viene preemptato viene aggiunto alla fine della coda.
- Round robin è un modello ibrido che è guidato dall’orologio
- Il time slice dovrebbe essere minimo, che viene assegnato per un compito specifico che deve essere elaborato. Tuttavia, può differire da sistema operativo a sistema operativo.
- È un algoritmo in tempo reale che risponde all’evento entro un limite di tempo specifico.
- Round robin è uno degli algoritmi più antichi, più giusti e più semplici.
- Metodo di pianificazione ampiamente usato nei sistemi operativi tradizionali.
Esempio di Round-robin Scheduling
Considera i seguenti tre processi
| Coda dei processi | Tempo di burst |
| P1 | 4 |
| P2 | 3 |
| P3 | 5 |
Step 1) L’esecuzione inizia con il processo P1, che ha tempo di burst 4. Qui, ogni processo viene eseguito per 2 secondi. P2 e P3 sono ancora nella coda di attesa.
Step 2) Al tempo =2, P1 viene aggiunto alla fine della coda e P2 inizia l’esecuzione
Step 3) Al tempo =4 , P2 viene preempted e aggiunto alla fine della coda. P3 inizia l’esecuzione.
Step 4) A time=6 , P3 è preempted e aggiunto alla fine della coda. P1 inizia l’esecuzione.
Passo 5) A tempo=8 , P1 ha un tempo di burst di 4. Ha completato l’esecuzione. P2 inizia l’esecuzione
Passo 6) P2 ha un tempo di burst di 3. Ha già eseguito per 2 intervalli. Al tempo=9, P2 completa l’esecuzione. Poi, P3 inizia l’esecuzione fino al suo completamento.
Passo 7) Calcoliamo il tempo medio di attesa per l’esempio precedente.
Wait time P1= 0+ 4= 4P2= 2+4= 6P3= 4+3= 7
Vantaggio del Round-robin Scheduling
Qui, sono i pro/benefici del metodo di programmazione Round-robin:
- Non affronta i problemi di inedia o effetto convoglio.
- Tutti i lavori ottengono un’equa assegnazione di CPU.
- Si occupa di tutti i processi senza alcuna priorità
- Se si conosce il numero totale di processi sulla coda di esecuzione, allora si può anche assumere il tempo di risposta nel caso peggiore per lo stesso processo.
- Questo metodo di pianificazione non dipende dal tempo di scoppio. Ecco perché è facilmente implementabile sul sistema.
- Una volta che un processo viene eseguito per un insieme specifico del periodo, il processo viene preempted, e un altro processo viene eseguito per quel dato periodo di tempo.
- Permette al sistema operativo di utilizzare il metodo di commutazione del contesto per salvare gli stati dei processi preempted.
- Dà le migliori prestazioni in termini di tempo medio di risposta.
Svantaggi del Round-robin Scheduling
Qui, sono gli svantaggi/controindicazioni dell’uso del Round-robin scheduling:
- Se il tempo di affettamento del sistema operativo è basso, il rendimento del processore sarà ridotto.
- Questo metodo spende più tempo nella commutazione di contesto
- Le sue prestazioni dipendono pesantemente dal quantum di tempo.
- Non è possibile impostare le priorità per i processi.
- La programmazione Round-robin non dà priorità speciale ai compiti più importanti.
- Diminuisce la comprensione
- Il quantum di tempo più basso risulta in un maggiore overhead di commutazione di contesto nel sistema.
- Trovare un quantum di tempo corretto è un compito abbastanza difficile in questo sistema.
Worst Case Latency
Questo termine è usato per il tempo massimo impiegato per l’esecuzione di tutti i compiti.
- dt = Denota il tempo di rilevamento quando un compito viene portato nella lista
- st = Denota il tempo di passaggio da un compito all’altro
- et = Denota il tempo di esecuzione del compito
Formula:
Tworst = {(dti+ sti + eti ), + (dti+ sti + eti )2 +...+ (dti+ sti + eti )N., + (dti+ sti + eti + eti) N} + tISRt,SR = sum of all execution times
Sommario:
- Il nome di questo algoritmo deriva dal principio del round-robin, dove ogni persona ottiene una parte uguale di qualcosa a turno.
- Round robin è uno dei più vecchi, più giusti e più semplici algoritmi e metodi di programmazione ampiamente utilizzati nei sistemi operativi tradizionali.
- Round robin è un algoritmo pre-emptive
- Il più grande vantaggio del metodo di programmazione round-robin è che se si conosce il numero totale di processi sulla coda di esecuzione, allora si può anche assumere il tempo di risposta peggiore per lo stesso processo.
- Questo metodo spende più tempo nella commutazione di contesto
- La latenza del caso peggiore è un termine usato per il tempo massimo impiegato per l’esecuzione di tutti i compiti.