CFS:pianificazione dei processi completamente equa in Linux

Linux adotta un approccio modulare alla pianificazione del processore in quanto diversi algoritmi possono essere utilizzati per pianificare diversi tipi di processo. Una classe di pianificazione specifica quale criterio di pianificazione si applica a quale tipo di processo. La pianificazione completamente equa (CFS), che è diventata parte del kernel Linux 2.6.23 nel 2007, è la classe di pianificazione per i processi normali (in contrapposizione a quelli in tempo reale) e pertanto è denominata SCHED_NORMAL .

CFS è progettato per le applicazioni interattive tipiche di un ambiente desktop, ma può essere configurato come SCHED_BATCH per favorire i carichi di lavoro batch comuni, ad esempio, su un server Web ad alto volume. In ogni caso, CFS rompe drammaticamente con quella che potrebbe essere definita la "programmazione preventiva classica". Inoltre, l'affermazione "completamente corretta" deve essere vista con un occhio tecnico; in caso contrario, l'affermazione potrebbe sembrare un vuoto vanto.

Analizziamo i dettagli di ciò che distingue CFS da, anzi, sopra, altri pianificatori di processi. Iniziamo con una rapida rassegna di alcuni termini tecnici di base.

Alcuni concetti fondamentali

Linux eredita la vista Unix di un processo come un programma in esecuzione. In quanto tale, un processo deve fare i conti con altri processi per le risorse di sistema condivise:memoria per detenere istruzioni e dati, almeno un responsabile per eseguire istruzioni e dispositivi I/O per interagire con il mondo esterno. La pianificazione dei processi è il modo in cui il sistema operativo (OS) assegna le attività (ad esempio, sgranocchiare alcuni numeri, copiare un file) ai processori:un processo in esecuzione esegue quindi l'attività. Un processo ha uno o più thread di esecuzione , che sono sequenze di istruzioni a livello di macchina. Pianificare un processo significa pianificare uno dei suoi thread su un processore.

Il terminale Linux

• I 7 migliori emulatori di terminale per Linux
• 10 strumenti da riga di comando per l'analisi dei dati in Linux
• Scarica ora:cheat sheet SSH
• Cheat sheet sui comandi avanzati di Linux
• Esercitazioni sulla riga di comando di Linux

Con una mossa semplificativa, Linux trasforma la pianificazione dei processi in una pianificazione dei thread trattando un processo pianificato come se fosse a thread singolo. Se un processo è multi-thread con N thread, quindi N sarebbero necessarie azioni di pianificazione per coprire i thread. I thread all'interno di un processo multi-thread rimangono correlati in quanto condividono risorse come lo spazio degli indirizzi di memoria. I thread di Linux sono talvolta descritti come processi leggeri, con il leggero sottolineando la condivisione di risorse tra i thread all'interno di un processo.

Sebbene un processo possa trovarsi in vari stati, due sono di particolare interesse nella pianificazione. Un bloccato il processo è in attesa del completamento di un evento come un evento di I/O. Il processo può riprendere l'esecuzione solo al termine dell'evento. Un eseguibile è un processo che non è attualmente bloccato.

Un processo è limitato al processore (noto anche come limitato al calcolo ) se consuma principalmente il processore anziché le risorse I/O e I/O-bound nel caso opposto; quindi, un processo legato al processore è per lo più eseguibile, mentre un processo legato all'I/O è per lo più bloccato. Ad esempio, il crunching dei numeri è legato al processore e l'accesso ai file è legato all'I/O. Sebbene un intero processo possa essere caratterizzato come legato al processore o legato all'I/O, un determinato processo può essere l'uno o l'altro durante le diverse fasi della sua esecuzione. Le applicazioni desktop interattive, come i browser, tendono ad essere legate all'I/O.

Un buon pianificatore di processi deve bilanciare le esigenze delle attività legate al processore e quelle legate all'I/O, specialmente in un sistema operativo come Linux che prospera su così tante piattaforme hardware:macchine desktop, dispositivi embedded, dispositivi mobili, cluster di server, supercomputer e altro ancora.

Programmazione preventiva classica rispetto a CFS

Unix ha reso popolare la pianificazione preventiva classica, adottata in seguito da altri sistemi operativi, inclusi VAX/VMS, Windows NT e Linux. Al centro di questo modello di pianificazione c'è un intervallo temporale fisso , la quantità di tempo (ad es. 50 ms) durante la quale un'attività può trattenere un processore fino a quando non viene anticipata a favore di un'altra attività. Se un processo anticipato non ha terminato il suo lavoro, il processo deve essere riprogrammato. Questo modello è potente in quanto supporta il multitasking (concorrenza) attraverso la condivisione del tempo del processore, anche sulle macchine a CPU singola del passato.

Il modello classico in genere include più code di pianificazione, una per priorità di processo:ogni processo in una coda con priorità più alta viene pianificato prima di qualsiasi processo in una coda con priorità inferiore. Ad esempio, VAX/VMS utilizza 32 code di priorità per la pianificazione.

CFS elimina intervalli di tempo fissi e priorità esplicite. La quantità di tempo per una determinata attività su un processore viene calcolata dinamicamente quando il contesto di pianificazione cambia durante la vita del sistema. Ecco uno schizzo delle idee motivanti e dei dettagli tecnici:

• Immagina un processore, P, idealizzato in quanto può eseguire più attività contemporaneamente . Ad esempio, i compiti T1 e T2 possono essere eseguiti su P contemporaneamente, ricevendo ciascuno il 50% della potenza di elaborazione magica di P. Questa idealizzazione descrive il multitasking perfetto , che CFS si sforza di ottenere su processori reali anziché idealizzati. CFS è progettato per approssimare un perfetto multitasking.

• Lo scheduler CFS ha una latenza target , che è la quantità di tempo minima, idealizzata per una durata infinitamente piccola, richiesta per ogni attività eseguibile per ottenere almeno un turno di accensione del processore. Se una tale durata potesse essere infinitamente piccola, allora ogni attività eseguibile avrebbe avuto una svolta sul processore durante un dato intervallo di tempo, per quanto piccolo (ad esempio, 10 ms, 5 ns, ecc.). Naturalmente, una durata infinitamente piccola idealizzata deve essere approssimata nel mondo reale e l'approssimazione predefinita è 20 ms. Ogni attività eseguibile ottiene quindi un 1/N porzione della latenza di destinazione, dove N è il numero di compiti. Ad esempio, se la latenza di destinazione è di 20 ms e ci sono quattro attività concorrenti, ciascuna attività ottiene un intervallo di tempo di 5 ms. A proposito, se c'è solo una singola attività durante un evento di pianificazione, questa attività fortunata ottiene l'intera latenza di destinazione come sua fetta. La fiera in CFS viene alla ribalta nella 1/N slice data a ogni attività che si contende un processore.

• Il 1/N slice è, in effetti, una sequenza temporale, ma non fissa perché tale sezione dipende da N , il numero di attività attualmente in lizza per il processore. Il sistema cambia nel tempo. Alcuni processi terminano e ne vengono generati di nuovi; i processi eseguibili si bloccano e i processi bloccati diventano eseguibili. Il valore di N è dinamico e quindi è 1/N timeslice calcolato per ogni attività eseguibile in lizza per un processore. Il tradizionale bello il valore viene utilizzato per pesare 1/N slice:un bello a bassa priorità valore significa che solo una frazione di 1/N slice viene assegnata a un'attività, mentre una priorità alta bello valore significa che una frazione proporzionalmente maggiore di 1/N slice viene assegnata a un compito. In sintesi, bello i valori non determinano la sezione, ma modificano solo 1/N fetta che rappresenta l'equità tra le attività concorrenti.

• Il sistema operativo subisce un sovraccarico ogni volta che si verifica un cambio di contesto si verifica; cioè, quando un processo è anticipato a favore di un altro. Per evitare che questo sovraccarico diventi eccessivamente elevato, c'è una quantità minima di tempo (con un'impostazione tipica da 1 ms a 4 ms) che qualsiasi processo pianificato deve eseguire prima di essere annullato. Questo minimo è noto come granularità minima . Se molte attività (ad es. 20) si contendono il processore, la granularità minima (supponiamo 4 ms) potrebbe essere più rispetto a 1/N slice (in questo caso, 1 ms). Se la granularità minima risulta essere maggiore di 1/N slice, il sistema è sovraccarico perché ci sono troppe attività che si contendono il processore e l'equità va fuori dalla finestra.

• Quando avviene la prelazione? CFS cerca di ridurre al minimo i cambi di contesto, dato il loro sovraccarico:il tempo speso per un cambio di contesto è tempo non disponibile per altre attività. Di conseguenza, una volta che un'attività ottiene il processore, viene eseguita per il suo intero ponderato 1/N fetta prima di essere anticipata a favore di qualche altro compito. Supponiamo che l'attività T1 sia stata eseguita per il suo peso 1/N slice e l'attività eseguibile T2 ha attualmente il runtime virtuale più basso (vruntime) tra le attività che si contendono il processore. Il vruntime registra, in nanosecondi, per quanto tempo un'attività è stata eseguita sul processore. In questo caso, T1 sarebbe anticipato a favore di T2.

• Lo scheduler tiene traccia del vruntime per tutte le attività, eseguibili e bloccate. Più basso è il tempo di esecuzione di un'attività, più l'attività è meritevole di tempo sul processore. Di conseguenza, CFS sposta le attività a basso vruntime all'inizio della linea di pianificazione. I dettagli sono imminenti perché la linea è implementato come un albero, non un elenco.

• Con quale frequenza deve essere riprogrammato lo scheduler CFS? C'è un modo semplice per determinare il periodo di programmazione . Supponiamo che la latenza target (TL) sia 20 ms e la granularità minima (MG) sia 4 ms:

  TL / MG = (20 / 4) = 5 ## five or fewer tasks are ok

  In questo caso, cinque o meno attività consentirebbero a ciascuna attività di accendere il processore durante la latenza di destinazione. Ad esempio, se il numero dell'attività è cinque, ogni attività eseguibile ha un 1/N fetta di 4 ms, che corrisponde alla granularità minima; se il numero dell'attività è tre, ogni attività riceve un 1/N fetta di quasi 7ms. In entrambi i casi, lo scheduler riprogrammerebbe in 20 ms, la durata della latenza target.

  Si verificano problemi se il numero di attività (ad es. 10) supera TL / MG perché ora ogni attività deve ottenere il tempo minimo di 4 ms anziché 1/N calcolato fetta, che è 2 ms. In questo caso, lo scheduler verrebbe riprogrammato in 40 ms:

  (number of tasks) * MG = (10 * 4) = 40ms ## period = 40ms

Gli scheduler Linux precedenti a CFS utilizzano l'euristica per promuovere il trattamento equo delle attività interattive rispetto alla pianificazione. CFS adotta un approccio completamente diverso, lasciando che i fatti di vruntime parlino principalmente da soli, il che sembra supportare l'equità del sonno . Un'attività interattiva, per sua stessa natura, tende a dormire molto, nel senso che attende gli input dell'utente e quindi diventa I/O-bound; quindi, un'attività del genere tende ad avere un vruntime relativamente basso, che tende a spostare l'attività in primo piano rispetto alla linea di pianificazione.

Caratteristiche speciali

CFS supporta il multiprocessing simmetrico (SMP) in cui qualsiasi processo (kernel o utente) può essere eseguito su qualsiasi processore. Eppure scheduling domini configurabili può essere utilizzato per raggruppare i processori per il bilanciamento del carico o addirittura per la segregazione. Se più processori condividono la stessa politica di pianificazione, il bilanciamento del carico tra di loro è un'opzione; se un particolare processore ha una politica di pianificazione diversa dagli altri, allora questo processore sarebbe separato dagli altri per quanto riguarda la pianificazione.

Gruppi di pianificazione configurabili sono un'altra caratteristica di CFS. Ad esempio, considera il server web Nginx in esecuzione sul mio computer desktop. All'avvio, questo server ha un processo master e quattro processi di lavoro, che fungono da gestori di richieste HTTP. Per qualsiasi richiesta HTTP, il particolare lavoratore che gestisce la richiesta è irrilevante; importa solo che la richiesta sia gestita in modo tempestivo, quindi i quattro lavoratori insieme forniscono un pool da cui attingere un responsabile delle attività man mano che arrivano le richieste. Sembra quindi giusto trattare i quattro lavoratori di Nginx come un gruppo piuttosto che come individui ai fini della pianificazione e un gruppo di pianificazione può essere utilizzato proprio per questo. I quattro worker Nginx possono essere configurati per avere un singolo vruntime tra di loro anziché singoli vruntime. La configurazione viene eseguita nel modo tradizionale di Linux, tramite file. Per la condivisione vruntime, un file denominato cpu .condivisioni , con i dettagli forniti tramite comandi shell familiari, verrebbero creati.

Come notato in precedenza, Linux supporta scheduling classi in modo che diverse politiche di pianificazione, insieme ai relativi algoritmi di implementazione, possano coesistere sulla stessa piattaforma. Una classe di pianificazione viene implementata come modulo di codice in C. CFS, la classe di pianificazione descritta finora, è SCHED_NORMAL . Esistono anche classi di pianificazione specifiche per attività in tempo reale, SCHED_FIFO (first in, first out) e SCHED_RR (giro all'italiana). Sotto SCHED_FIFO , le attività vengono eseguite fino al completamento; sotto SCHED_RR , le attività vengono eseguite finché non esauriscono un intervallo di tempo prestabilito e vengono anticipate.

Implementazione CFS

CFS richiede strutture di dati efficienti per tenere traccia delle informazioni sulle attività e codice ad alte prestazioni per generare le pianificazioni. Cominciamo con un termine centrale nella programmazione, la runqueue . Questa è una struttura di dati che rappresenta una sequenza temporale per le attività pianificate. Nonostante il nome, la coda di esecuzione non deve essere implementata in modo tradizionale, come un elenco FIFO. CFS rompe con la tradizione utilizzando un albero rosso-nero ordinato nel tempo come coda. La struttura dei dati è adatta per il lavoro perché è un albero di ricerca binario autobilanciato, con inserimenti efficienti e rimuovere operazioni eseguite in O(log N) ora, dove N è il numero di nodi nell'albero. Inoltre, un albero è un'eccellente struttura dati per organizzare le entità in una gerarchia basata su una particolare proprietà, in questo caso un vruntime.

In CFS, i nodi interni dell'albero rappresentano le attività da pianificare e l'albero nel suo insieme, come qualsiasi coda di esecuzione, rappresenta una sequenza temporale per l'esecuzione delle attività. Gli alberi rosso-neri sono ampiamente utilizzati oltre la programmazione; ad esempio, Java utilizza questa struttura di dati per implementare la sua TreeMap .

In CFS, ogni processore ha una coda di esecuzione specifica di attività e nessuna attività si verifica contemporaneamente in più di una coda di esecuzione. Ogni coda è un albero rosso-nero. I nodi interni dell'albero rappresentano attività o gruppi di attività e questi nodi sono indicizzati dai loro valori vruntime in modo che (nell'albero nel suo insieme o in qualsiasi sottoalbero) i nodi interni a sinistra abbiano valori vruntime inferiori a quelli a destra:

    25     ## 25 is a task vruntime

    /\

  17  29   ## 17 roots the left subtree, 29 the right one

  /\  ...

 5  19     ## and so on

...  \

     nil   ## leaf nodes are nil

In sintesi, le attività con il vruntime più basso e, quindi, la maggiore necessità di un processore risiedono da qualche parte nel sottoalbero di sinistra; le attività con tempi di esecuzione relativamente elevati si riuniscono nel sottoalbero di destra. Un'attività anticipata andrebbe nella sottostruttura di destra, dando così la possibilità ad altre attività di spostarsi verso sinistra nell'albero. Un'attività con il vruntime più piccolo finisce nel nodo (interno) più a sinistra dell'albero, che è quindi la parte anteriore della coda di esecuzione.

Lo scheduler CFS ha un'istanza, C task_struct , per tenere traccia delle informazioni dettagliate su ciascuna attività da pianificare. Questa struttura incorpora una sched_entity struttura, che a sua volta contiene informazioni specifiche sulla pianificazione, in particolare il vruntime per attività o gruppo di attività:

struct task_struct {       /** info on a task **/

  ...

  struct sched_entity se;  /** vruntime, etc. **/

  ...

};

L'albero rosso-nero è implementato nel modo familiare C, con un premio sui puntatori per l'efficienza. Un cfs_rq l'istanza della struttura incorpora una rb_root campo denominato tasks_timeline , che indica la radice di un albero rosso-nero. Ciascuno dei nodi interni dell'albero ha puntatori al genitore e ai due nodi figlio; i nodi foglia hanno nil come il loro valore.

CFS illustra come un'idea semplice (dare a ogni attività una giusta quota di risorse del processore) può essere implementata in modo semplice ma altamente efficiente. Vale la pena ripetere che CFS ottiene una pianificazione equa ed efficiente senza artefatti tradizionali come intervalli di tempo fissi e priorità esplicite delle attività. La ricerca di pianificatori ancora migliori, ovviamente, continua; per il momento, tuttavia, CFS è buono come per la pianificazione di processori generici.