Che cos'è la pianificazione round-robin?

Question

In un contesto di sistema operativo multitasking, a volte si sente il termine pianificazione round-robin.A cosa si riferisce?
Che altro tipo di programmazione esiste?

Answer 1

Pianificazione Round Robin

Se sei l'host di un gruppo di 100 ospiti, la programmazione round-robin significherebbe che spenderai 1 minuto (un importo fisso) per ospite.Esamini ogni ospite uno per uno e dopo 100 minuti avresti trascorso 1 minuto con ogni ospite.Più su Wikipedia.

Esistono molti altri tipi di pianificazione, come quella basata sulle priorità (ad es.prima le persone più importanti), primo arrivato, primo servito, prima scadenza (ad es.persona che parte prima per prima), ecc.Puoi iniziare cercando su Google gli algoritmi di pianificazione o effettuando il check-out programmazione su Wikipedia

Answer 2

Nella pratica, il time-licing è inerente a qualsiasi sistema di pianificazione round-robin, per quanto ne so.

Non sono d'accordo con l'implicazione di InSciTek Jeff secondo cui quanto segue È programmazione del girone all'italiana:

Cioè, a ciascuna attività con la stessa priorità nella rotazione round-robin può essere consentita l'esecuzione finché non raggiunge una condizione di blocco delle risorse prima di cedere all'attività successiva nella rotazione.

Non vedo come questo possa essere considerato un round robin.Questa è in realtà una pianificazione preventiva.Tuttavia, è possibile avere un algoritmo di pianificazione che abbia elementi sia di pianificazione round-robin che di pianificazione preventiva, cosa che VxWorks fa se la pianificazione round-robin e la prelazione sono entrambe abilitate (il round-robin è disabilitato per impostazione predefinita).Il modo per abilitare la pianificazione round-robin è fornire un valore diverso da zero in kernelTimeSlice.

Sono d'accordo con questa affermazione:

Pertanto, mentre la pianificazione basata sul time-licing implica la pianificazione round-robin, la pianificazione round-robin non richiede un time-licing basato sullo stesso tempo.

Hai ragione nel dire che non richiede lo stesso tempo.La prevenzione può rovinare tutto ciò.E in realtà in VxWorks, se un'attività viene anticipata durante la pianificazione round-robin, quando l'attività riprende il controllo verrà eseguita per il resto del tempo assegnato.

Modifica diretta su Inscitek Jeff (non ho privilegi di commento) Sì, mi riferivo al blocco/interruzione delle attività, anche se ovviamente non l'ho espresso molto bene.Mi hai anticipato (ah!) con il tuo secondo commento.Spero di discutere il punto più saliente, ovvero che ritieni che la pianificazione round-robin possa esistere senza suddivisione del tempo.O intendevi semplicemente affettare il tempo in base al tempo uguale?Non sono d'accordo con il primo, ma sono d'accordo con il secondo.Sono ansioso di imparare.Grazie.

Edit2 diretto a Jeff:

Il round robin può esistere senza time-licing.Questo è esattamente ciò che accade in VxWorks quando kernelTimeSlice è disabilitato (zero).

Non sono d'accordo con questa affermazione.Vedere questo documento sezione 2.2.3 con il titolo Programmazione Round-Robin.

La pianificazione round-robin utilizza un taglio temporale per ottenere un'allocazione equa della CPU a tutte le attività con la stessa priorità.Ogni attività, in un gruppo di attività con la stessa priorità, esegue per un intervallo definito o una fetta di tempo.La pianificazione round-robin è abilitata chiamando Kerneltimeslice (), che prende un parametro per una fetta di tempo o intervallo....] Se la pianificazione round-robin è abilitata e la preemption è abilitata per l'attività di esecuzione, il gestore del sistema di spunta aumenta il conteggio delle aree temporali dell'attività.

Il time-licing è inerente alla pianificazione round-robin.Altrimenti ti affidi a un'attività per rinunciare al controllo della CPU, che la pianificazione round-robin è destinata a risolvere.

Answer 3

Le risposte qui e persino l'articolo di Wikipedia descrivono la pianificazione round-robin per includere intrinsecamente il timelicing periodico.Anche se questo è molto comune, credo che la pianificazione Round-Robin e il time-licing lo siano non esattamente la stessa cosa.Certamente, affinché il time-licing abbia senso, la pianificazione round-robin è implicita quando si ruota su ciascuna attività, tuttavia è possibile eseguire la pianificazione round-robin senza avere il time-licing.Cioè, è possibile consentire l'esecuzione di ciascuna attività con la stessa priorità nella rotazione round-robin finché non raggiunge una condizione di blocco delle risorse e solo allora viene eseguita l'attività successiva nella rotazione.In altre parole, quando esistono compiti con pari priorità, i punti di riprogrammazione lo sono non tempo preventivo.

L'idea di cui sopra è in realtà realizzata specificamente nel caso del kernel VxWorks di Wind River.All'interno del loro schema di priorità, le attività di ciascuna priorità vengono eseguite in round robin ma non in suddivisioni temporali senza abilitare specificamente tale funzionalità nel kernel.Il motivo di questa flessibilità è quello di evitare il sovraccarico delle attività di suddivisione temporale che è già noto che si verificano in un blocco entro un tempo ben delimitato.

Pertanto, mentre la pianificazione basata sul time-licing implica la pianificazione round-robin, la pianificazione round-robin non richiede un time-licing basato sullo stesso tempo.

Answer 4

Un'opinione.Sembra che stiamo intrecciando due meccanismi in uno solo.Supponendo quindi solo l'affermazione originale dell'OP "In un contesto di sistema operativo multitasking".

1 - Uno scheduler round robin pianifica sempre l'elemento successivo in una coda circolare.

2 - Il modo in cui lo scheduler riprende il controllo per eseguire la pianificazione è separato e non correlato.

Non sono d'accordo sul fatto che il metodo più diffuso per 2 sia il time-slicing/rendimento in attesa della risorsa, ma come è stato notato ce ne sono altri.Se non sbaglio, i primi Mac non utilizzavano il time-slicing, ma utilizzavano il rendimento volontario/rendimento in attesa di risorse (le cellule cerebrali di oltre 20 anni possono sbagliarsi a volte;).

Answer 5

Il Round Robin è un semplice algoritmo di pianificazione in cui il tempo viene suddiviso equamente tra i lavori senza priorità.

Ad esempio, se sono in esecuzione 5 processi, a ogni processo sarà consentita l'esecuzione per 1/5 di un'unità di tempo prima che sia consentita l'esecuzione di un altro processo.Il round robin è in genere facile da implementare in un sistema operativo.

Answer 6

In realtà, ti stai confondendo con la pianificazione preventiva e il Round robin.Infatti RR fa parte della pianificazione preventiva.

Answer 7

La pianificazione Round Robin si basa sulla condivisione del tempo nota anche come quantistica (tempo massimo concesso dalla CPU a qualsiasi processo in una volta sola).Esistono più processi (che richiedono tempi diversi per essere completati, ovvero tempo di burst) in una coda e la CPU deve elaborarli tutti in modo da continuare a passare da un processo all'altro per dare a ogni processo lo stesso tempo in base al valore quantico.Questo tipo di pianificazione è nota come pianificazione Round Robin.Guarda questo semplice video per comprendere facilmente la pianificazione del round robin: https://www.youtube.com/watch?v=9hw-_qJ55K4