Scheduling in Scheduling in Linux Linux

Sanjay Kumar Sanjay Kumar Sanjay Kumar Ram Sanjay Kumar Ram

Marcello MissiroliMarcello Missiroli

I Processi in LinuxI Processi in Linux Tre classi di processiTre classi di processi

InterattiviInterattivi Batch Batch Real-timeReal-time

I processi in Linux hanno gli stati seguenti:I processi in Linux hanno gli stati seguenti: Running Running WaitingWaiting StoppedStopped ZombieZombie

Politica di schedulingPolitica di scheduling Il kernel Linux è Il kernel Linux è non-preemptivenon-preemptive but i processi, invece, sono but i processi, invece, sono preemptivepreemptive

Le regole utilizzate per determinare quano e come selezionare un nuovo Le regole utilizzate per determinare quano e come selezionare un nuovo processo si dice processo si dice politica di schedulingpolitica di scheduling. .

Lo scheduling Linux è basato sul Lo scheduling Linux è basato sul time-sharing:time-sharing: molti processi possono molti processi possono essere eseguiti in “concorrenza”, anche su una sola CPU.essere eseguiti in “concorrenza”, anche su una sola CPU.

Il tempo della CPU time è diviso in "fette“Il tempo della CPU time è diviso in "fette“

Lo scheduling è anche basato sulla prioritàLo scheduling è anche basato sulla priorità Priorità staticaPriorità statica – – assegnata dagli utenti ai processi real-time, e MAI assegnata dagli utenti ai processi real-time, e MAI

modificatamodificata Priorità dinamicaPriorità dinamica – – assegnata con una priorità base e modificata in assegnata con una priorità base e modificata in

base alle circostanze.base alle circostanze.

Politica di schedulingPolitica di scheduling PrelazionePrelazione

Quando un processo passa da waiting a Running e la Quando un processo passa da waiting a Running e la priorità dinamica del processo in esecuzione è inferiore al priorità dinamica del processo in esecuzione è inferiore al processo che è appena entratoprocesso che è appena entrato

Quando un processo in fase di running esaurisce il quanto a Quando un processo in fase di running esaurisce il quanto a sua disposizionesua disposizione

Quanto è lungo un quantum?Quanto è lungo un quantum? Se troppo corto → aumenta l'overhead per l'eccessivo Se troppo corto → aumenta l'overhead per l'eccessivo

context switchcontext switch Se troppo lungo → degrada la risposta (o la percezione Se troppo lungo → degrada la risposta (o la percezione

della risposta) del sistemadella risposta) del sistema

Valore standard: Q=200msValore standard: Q=200ms

Algoritmo 2.4 nel caso monoprocessoreAlgoritmo 2.4 nel caso monoprocessore

L'algoritimo divide il tempo della CPU in L'algoritimo divide il tempo della CPU in epocheepoche In ogni epoca, ogni processo ha uno specifico quantumIn ogni epoca, ogni processo ha uno specifico quantum L'epoca finisce quando tutti i processi nella coda si esecuzione hanno esaurito L'epoca finisce quando tutti i processi nella coda si esecuzione hanno esaurito

il quantumil quantum

Ogni processo ha un Ogni processo ha un quantum di basequantum di base Il valore del quantum base è 20 meno la priorità (valore base: 0).Il valore del quantum base è 20 meno la priorità (valore base: 0). Gli utenti possono variare la priorità usando varie funzioni, come Gli utenti possono variare la priorità usando varie funzioni, come nice( ).nice( ). Root

può anche fissare valori negativi.

Ogni processo mantiene Ogni processo mantiene metàmetà del tempo di quantum che possiede del tempo di quantum che possiede (es: se in Waiting).(es: se in Waiting). Riassumendo: Riassumendo:

Quantum della nuova epoca=(quantum corrente/2)+(quantum Quantum della nuova epoca=(quantum corrente/2)+(quantum base)-(nice)base)-(nice)

Esempio (semplificato)Esempio (semplificato)

Supponiamo ci siano due processi: A (word Supponiamo ci siano due processi: A (word processor, interattivo) e B(compilatore)processor, interattivo) e B(compilatore)

A ha maggiore priorità, ma ha lunghe pause (per A ha maggiore priorità, ma ha lunghe pause (per esempio tra un tasto e l'altro). esempio tra un tasto e l'altro).

Quando si preme un tasto, l'interrupt “risveglia” il Quando si preme un tasto, l'interrupt “risveglia” il processo e lo porta allo stato di running. processo e lo porta allo stato di running.

Dato che A ha priorità maggiore di B, lo scheduler Dato che A ha priorità maggiore di B, lo scheduler preempta il compilatore (context switch). preempta il compilatore (context switch).

Il tasto è visualizzato sullo schermo, poi A si Il tasto è visualizzato sullo schermo, poi A si autosospende .autosospende .

AlgoritmoAlgoritmo Ad intervalli regolari un timer ('tick') decrementa il quantum di tempo del Ad intervalli regolari un timer ('tick') decrementa il quantum di tempo del

processo in esecuzioneprocesso in esecuzione Quando raggiunge 0, si sceglie un nuovo processo, scegliendo quello più Quando raggiunge 0, si sceglie un nuovo processo, scegliendo quello più

adatto (funzione adatto (funzione goodness()goodness())) Se ci sono più processi con la stessa priorità si sceglie quello più in altro Se ci sono più processi con la stessa priorità si sceglie quello più in altro

(stile FIFO),(stile FIFO), Se non ci sono più processi, finisce l'epoca.Se non ci sono più processi, finisce l'epoca. Se un processo si forka, il numero di 'tick' è diviso tra padre e figlioSe un processo si forka, il numero di 'tick' è diviso tra padre e figlio

Tutto questo si trova nel fileTutto questo si trova nel file sched.c sched.c

Problemi dell'algoritmoProblemi dell'algoritmo

Ha una performance che si deteriora in Ha una performance che si deteriora in funzione del numero dei processi (complessità funzione del numero dei processi (complessità O(n)).O(n)).

Non tiene conto delle caratteristiche dei Non tiene conto delle caratteristiche dei multiprocessori, tenendo una coda unica di multiprocessori, tenendo una coda unica di processi pronti per l'intero sistemaprocessi pronti per l'intero sistema

Nuovo algorimo (2.6)Nuovo algorimo (2.6)

Obiettivi che si pone: Obiettivi che si pone: Implementare uno scheduling O(1) scheduling.Implementare uno scheduling O(1) scheduling. Le Le

operazioni dell'algoritmo si svolgono in tempo costante. operazioni dell'algoritmo si svolgono in tempo costante.

Implementare scalabilità SMPImplementare scalabilità SMP. . Ogni processore ha la Ogni processore ha la propria coda di esecuzionepropria coda di esecuzione. .

Implementare affinità SMP. Implementare affinità SMP. Acerca di raggruppare i Acerca di raggruppare i processi per ogni CPU e tenta di eseguirli sempre sullo processi per ogni CPU e tenta di eseguirli sempre sullo stesso processore. I processi sono migrati solo per stesso processore. I processi sono migrati solo per bilanciamentobilanciamento

Nuovo algoritmo (2.6, cont.)Nuovo algoritmo (2.6, cont.)

Buona performance interattivaBuona performance interattiva,, Il sistema dovrebbe Il sistema dovrebbe reagire immediatamente anche sotto elevato carico. reagire immediatamente anche sotto elevato carico.

EquitàEquità, , (evitare starvation). (evitare starvation).

Nuovo algoritmo (2.6, cont.)Nuovo algoritmo (2.6, cont.)

Gli array di prioritàGli array di priorità Ogni coda di esecuzione (runqueue, una per Ogni coda di esecuzione (runqueue, una per

processore) contienea due processore) contienea due array di prioritàarray di priorità: l'array dei: l'array dei processi attiviprocessi attivi e quella dei e quella dei processi esauritiprocessi esauriti

Ogni array contiene una coda per ogni livello di Ogni array contiene una coda per ogni livello di priorità.priorità.

L'algoritmo O(1)L'algoritmo O(1)

Il sistema mantiene una mappa di 140 bit che indicano se c'è un Il sistema mantiene una mappa di 140 bit che indicano se c'è un processo in esecuzione con tale prioritàprocesso in esecuzione con tale priorità

E' quindi facile trovare la coda che contiene il processo a priorità più E' quindi facile trovare la coda che contiene il processo a priorità più alta. Basta infatti trovare il primo bit settato a partire dall'alto. alta. Basta infatti trovare il primo bit settato a partire dall'alto.

Si seleziona quindi il primo processo della coda.Si seleziona quindi il primo processo della coda.

..

Ricalcolo del quantumRicalcolo del quantum

Quando un processo termina il proprio quantum, Quando un processo termina il proprio quantum, viene spostato dall'array dei processi attivi a quelli viene spostato dall'array dei processi attivi a quelli dei processi esauriti.dei processi esauriti.

Durante questa operazione viene anche ricalcolato il Durante questa operazione viene anche ricalcolato il quantum. quantum.

Quando non ci sono più processi nell'array dei Quando non ci sono più processi nell'array dei processi attivi, le due array cambiano di ruolo. processi attivi, le due array cambiano di ruolo. Essendo puntatori, lo scambio è rapidissimo. Essendo puntatori, lo scambio è rapidissimo.

Scheduling algorithm for multiprocessor Scheduling algorithm for multiprocessor (contd.)(contd.)

Bilanciatore di caricoBilanciatore di carico

Esercizio 1Esercizio 1

In un sistema sono attivi i processi A, B, C. A In un sistema sono attivi i processi A, B, C. A ha priorità 0, B ha nice 5, mentre C ha nice ha priorità 0, B ha nice 5, mentre C ha nice

11. 11.

A è attualmente in esecuzione, ma dopo 7 A è attualmente in esecuzione, ma dopo 7 'tick' passerà in Waiting per 12 'tick'.'tick' passerà in Waiting per 12 'tick'.

Mostrare l'evoluzione del sistema per i primi Mostrare l'evoluzione del sistema per i primi 32 tick, evidenziando cambi di contesto ed 32 tick, evidenziando cambi di contesto ed

epoche (se vi sono) epoche (se vi sono)

0 1 2 3 4 5 6 7 8 9 10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

AA19

A18

A17

A16

A15

A14

A13

- - - - - - - - - - -A12

A11

A10

A9

A8

A7

A6

A5

A4

A3

A2

A1

A0

a0

Bb15

b15

b15

b20

b20

b20

b20

B19

B18

B17

B16

B15

B14

B13

B12

B10

B9

B8

e8

e8

e8

e8

e8

e8

e8

e8

e8

e8

e8

e8

e8

e8

C c9

c9

c9

c9

c9

c9

c9

c9

c9

c9

c9

c9

c9

c9

c9

c9

c9

c9

c9

c9

c9

c9

c9

c9

c9

c9

c9

c9

c9

c9

c9

C9

Esercizio 2Esercizio 2

In un sistema si hanno i seguenti processi:In un sistema si hanno i seguenti processi:

A (priorità 0, attualmente 12 tick, dopo 8 tick A (priorità 0, attualmente 12 tick, dopo 8 tick va in Waiting per 6 tick)va in Waiting per 6 tick)

B (priorità 1, attualmente 0 tick).B (priorità 1, attualmente 0 tick).

Dopo 2 tick il processo C, che ha priorità real Dopo 2 tick il processo C, che ha priorità real time, si attiva, resta per 4 tick. .time, si attiva, resta per 4 tick. .

Mostrare l'evoluzione del sistema per i primi Mostrare l'evoluzione del sistema per i primi 30 tick, evidenziando cambi di contesto ed 30 tick, evidenziando cambi di contesto ed

epoche (se vi sono) epoche (se vi sono)

RiferimentiRiferimenti

http://iamexwiwww.unibe.ch/studenten/schlpbch/linuxSchhttp://iamexwiwww.unibe.ch/studenten/schlpbch/linuxScheduling/LinuxScheduling.htmleduling/LinuxScheduling.html

http://oopweb.com/OS/Documents/tlk/VolumeFrames.hthttp://oopweb.com/OS/Documents/tlk/VolumeFrames.htmlml

http://www.samspublishing.com/articles/article.asp?p=10http://www.samspublishing.com/articles/article.asp?p=101760&rl=11760&rl=1

http://www.oreilly.com/catalog/linuxkernel/chapter/ch10.hhttp://www.oreilly.com/catalog/linuxkernel/chapter/ch10.htmltml

G. M. Candea and M. B. Jones, “ G. M. Candea and M. B. Jones, “ Vassal: Loadable Scheduler Support for Multi-Policy Scheduling,” Proceedings of the 2nd USENIX Windows NT Symposium Seattle, Washington, August 3–4, 1998

LicenzaLicenza

• La versione originale di questa La versione originale di questa presentazione è in ingliese, sul sito presentazione è in ingliese, sul sito http://www.cse.iitb.ac.in/~cs431/student_slidhttp://www.cse.iitb.ac.in/~cs431/student_slides/Scheduling%20in%20Linux%20and%20es/Scheduling%20in%20Linux%20and%20Windows%202000.pptWindows%202000.ppt

• Non mi è stato possibile trovare riferimenti Non mi è stato possibile trovare riferimenti circa l'autore o le sue licenze, per cui, per circa l'autore o le sue licenze, per cui, per quanto concerne le mie modifiche, questo quanto concerne le mie modifiche, questo lavoro è soggetto alla licenza Creative lavoro è soggetto alla licenza Creative Commons, Commons, http://creativecommons.org/licenses/by-sa/2.http://creativecommons.org/licenses/by-sa/2.5/5/ salvo diverse indicazioni salvo diverse indicazioni