SchedulingSchedulingA. FerrariA. Ferrari

Nuovo

Prontoin

esecuzione

Terminato

bloccato

interruzioneuscitaammissione

attesa evento (es. I/O)evento verificato

assegnazione

Coda Pronti

Code di Attesa

Tipi di processiTipi di processiCPU BoundCPU Bound

Processi che sfruttano pesantemente le risorse Processi che sfruttano pesantemente le risorse computazionali del processore, ma non richiedono computazionali del processore, ma non richiedono servizi di ingresso/uscita dati al sistema operativo servizi di ingresso/uscita dati al sistema operativo in quantità rilevanti.in quantità rilevanti.Es. i programmi di calcolo matematico, i quali Es. i programmi di calcolo matematico, i quali necessitano spesso di un'enorme potenza di necessitano spesso di un'enorme potenza di calcolo, ma sfruttano l'I/O solo all'inizio della loro calcolo, ma sfruttano l'I/O solo all'inizio della loro vita (per caricare gli input) ed alla fine di essa vita (per caricare gli input) ed alla fine di essa (per produrre gli output).(per produrre gli output).

I/O Bound I/O Bound molti accessi alle periferiche, il processo è spesso molti accessi alle periferiche, il processo è spesso interrotto per attendere il completamento delle interrotto per attendere il completamento delle richieste di I/O.richieste di I/O.

P1 (CPU bound) P1 (CPU bound) P2 /I/O bound)P2 /I/O bound)

Lungo burst di CPU Attesa completamento I/OCorto burst di CPU

tempo

P1

P2

In esecuzione In attesa

Classi di Classi di schedulingscheduling

Nella gestione delle risorse di un Nella gestione delle risorse di un elaboratore, il fattore tempo porta a elaboratore, il fattore tempo porta a identificare tre tipi di scheduling:identificare tre tipi di scheduling:

Scheduling a breve termineScheduling a breve termine

Scheduling a medio termineScheduling a medio termine

Scheduling a lungo termineScheduling a lungo termine

Scheduling Scheduling a lungo terminea lungo termine

E’ impiegato nella scelta dei programmi, E’ impiegato nella scelta dei programmi, presenti in memoria secondaria, da presenti in memoria secondaria, da caricare in memoria centrale per la caricare in memoria centrale per la creazione dei corrispondenti processicreazione dei corrispondenti processi

individua i programmi da ammettere individua i programmi da ammettere all’esecuzioneall’esecuzione

regola la presenza in memoria centrale di regola la presenza in memoria centrale di processi I/O bound e CPU boundprocessi I/O bound e CPU bound

controlla il livello di multiprogrammazionecontrolla il livello di multiprogrammazione

Scheduling Scheduling a medio terminea medio termineGestisce la permanenza in memoria dei Gestisce la permanenza in memoria dei processi non in esecuzioneprocessi non in esecuzione

coordina le operazioni di trasferimento coordina le operazioni di trasferimento temporaneo dei processi in memoria temporaneo dei processi in memoria secondaria (swap out):secondaria (swap out):

interviene nella gestione dei processi in interviene nella gestione dei processi in attesa di eventi da lungo tempoattesa di eventi da lungo tempo

Scheduling Scheduling a breve terminea breve termine

Si occupa della selezione del nuovo processo da Si occupa della selezione del nuovo processo da eseguire, quandoeseguire, quando

il processo in esecuzione passa allo stato di attesa o il processo in esecuzione passa allo stato di attesa o ritorna allo stato di pronto oppure terminaritorna allo stato di pronto oppure terminaun processo passa dallo stato di attesa allo stato di un processo passa dallo stato di attesa allo stato di prontoprontosi verificano eventi particolari (interruput, chiamate si verificano eventi particolari (interruput, chiamate al S. O.)al S. O.)

Quando la CPU rimane inattiva, il process Quando la CPU rimane inattiva, il process scheduler (modulo del kernel) seleziona dalla scheduler (modulo del kernel) seleziona dalla ready queue (coda dei processi pronti) il prossimo ready queue (coda dei processi pronti) il prossimo processo a cui assegnare la CPU e decide da quale processo a cui assegnare la CPU e decide da quale momento e per quanto tempo farlo eseguire.momento e per quanto tempo farlo eseguire.

Context switchContext switchIl context switch (commutazione di contesto) Il context switch (commutazione di contesto) è la fase in cui l’uso della CPU passa da un è la fase in cui l’uso della CPU passa da un processo pprocesso pii al suo successivo p al suo successivo pi+1 i+1

Nella fase di passaggio il SO realizza, in Nella fase di passaggio il SO realizza, in sequenza, le seguenti operazioni:sequenza, le seguenti operazioni:

Salvataggio dello stato del processo pSalvataggio dello stato del processo pii uscente uscente

Selezione del nuovo processo pSelezione del nuovo processo pi+1 i+1

Ripristino dello stato del processo pRipristino dello stato del processo pi+1 i+1 entranteentrante

Si modifica, in questo modo, il contesto in cui Si modifica, in questo modo, il contesto in cui lavora il processore.lavora il processore.

Durata del Durata del context switchcontext switch

Il tempo utilizzato dal SO per le Il tempo utilizzato dal SO per le operazioni di context switch, in operazioni di context switch, in rapporto al time-slice (quanto di tempo rapporto al time-slice (quanto di tempo di CPU), non deve essere causa didi CPU), non deve essere causa di

riduzione dell’efficienza della CPUriduzione dell’efficienza della CPU

lunghi tempi di rispostalunghi tempi di risposta

A tal fine, il tempo di context switch A tal fine, il tempo di context switch non deve superare il 25% del time-slice non deve superare il 25% del time-slice (solitamente di circa 100 ms)(solitamente di circa 100 ms)

DispatcherDispatcherL’effettiva assegnazione della CPU al L’effettiva assegnazione della CPU al processo prescelto per l’esecuzione è processo prescelto per l’esecuzione è affidata al dispatcher, modulo del affidata al dispatcher, modulo del kernel che gestiscekernel che gestisce

il context switchil context switch

il passaggio al modo utenteil passaggio al modo utente

il salto alla giusta posizione del il salto alla giusta posizione del programma utente (impostazione del programma utente (impostazione del program counter)program counter)

Politiche di Politiche di scheduling: scheduling:

obiettiviobiettivimassimizzare massimizzare

il throughput (numero di processi utente completati nell’unità di tempo)il throughput (numero di processi utente completati nell’unità di tempo)

l’utilizzo della CPU (percentuale media di utilizzo della CPU nell’unità di l’utilizzo della CPU (percentuale media di utilizzo della CPU nell’unità di tempo)tempo)

minimizzareminimizzare

l’overhead (numero di processi di sistema completati nell’unità di tempo)l’overhead (numero di processi di sistema completati nell’unità di tempo)

il tempo di turnaround (tempo di permanenza di un processo nel sistema)il tempo di turnaround (tempo di permanenza di un processo nel sistema)

il tempo di risposta (tempo trascorso tra l’immissione di un comando e il tempo di risposta (tempo trascorso tra l’immissione di un comando e l’emissione della prima risposta)l’emissione della prima risposta)

il tempo di attesa (tempo totale trascorso da un processo nello stato di il tempo di attesa (tempo totale trascorso da un processo nello stato di pronto)pronto)

garantire garantire

fairness (equità) (imparzialità nell’attribuzione dei time-slice ai processi)fairness (equità) (imparzialità nell’attribuzione dei time-slice ai processi)

Tipi di sistemiTipi di sistemiOgni algoritmo di scheduling della CPU è Ogni algoritmo di scheduling della CPU è finalizzato al raggiungimento di alcuni finalizzato al raggiungimento di alcuni obiettivi. obiettivi.

Nei sistemi batch (elaborazione a lotti) si Nei sistemi batch (elaborazione a lotti) si cerca di massimizzare il throughput e di cerca di massimizzare il throughput e di minimizzare l’overhead.minimizzare l’overhead.

Nei sistemi interattivi (tempi di risposta Nei sistemi interattivi (tempi di risposta immediati) è essenziale minimizzare i immediati) è essenziale minimizzare i tempi di risposta e di attesa dei processi.tempi di risposta e di attesa dei processi.

Parentesi storicaParentesi storicaIBM 7094IBM 7094

IBM 7094IBM 7094The 7094 was IBM's most powerful scientific The 7094 was IBM's most powerful scientific computer in 1963. It could perform 500,000 computer in 1963. It could perform 500,000 logical decisions, 250,000 additions or logical decisions, 250,000 additions or subtractions, 100,000 multiplications, or 62,500 subtractions, 100,000 multiplications, or 62,500 divisions in one second. It had hardware to do divisions in one second. It had hardware to do double-precision floating-point arithmetic.double-precision floating-point arithmetic.

The computer gained considerable I/O The computer gained considerable I/O bandwidth from its separate data channels with bandwidth from its separate data channels with direct memory access, and so it was also used to direct memory access, and so it was also used to run business and general-purpose applications. run business and general-purpose applications. The 7094 had an operating system called IBSYS, The 7094 had an operating system called IBSYS, and FORTRAN and COBOL compilers.and FORTRAN and COBOL compilers.

A typical system cost $3,134,500. IBM stopped A typical system cost $3,134,500. IBM stopped selling them in 1969.selling them in 1969.

Dati tecniciDati tecniciManufacturer:Manufacturer:

IBMIBM

Memory technology:Memory technology:magnetic coremagnetic core

First introduced:First introduced:19631963

Memory size:Memory size:32K 36-bit words32K 36-bit words

CPU technology:CPU technology:transistortransistor

Cycle time:Cycle time:2 microseconds (0.5 MHz)2 microseconds (0.5 MHz)

Sfruttare al Sfruttare al massimo la massimo la

potenza di calcolopotenza di calcolo

Sistemi batchSistemi batchNon interattività dei programmiNon interattività dei programmi

Esecuzione non immediata ma rimandata nel tempo Esecuzione non immediata ma rimandata nel tempo dei programmidei programmi

Il termine batch risale all'epoca della Il termine batch risale all'epoca della programmazione per schede perforate. In quel programmazione per schede perforate. In quel contesto, i programmatori solitamente non avevano contesto, i programmatori solitamente non avevano accesso diretto al computer, bensì preparavano i accesso diretto al computer, bensì preparavano i propri programmi "off-line" e li passavano a un propri programmi "off-line" e li passavano a un amministratore di sistema, il quale aveva il compito amministratore di sistema, il quale aveva il compito di mandarli in esecuzione quando possibile di mandarli in esecuzione quando possibile (accodandoli rispetto ad altri programmi in (accodandoli rispetto ad altri programmi in esecuzione e spesso accorpando più programmi in esecuzione e spesso accorpando più programmi in un'unica unità di esecuzione), restituendo poi in un'unica unità di esecuzione), restituendo poi in seguito i risultati dell'elaborazione agli interessati.seguito i risultati dell'elaborazione agli interessati.

Sistemi interattiviSistemi interattiviNei sistemi interattivi il tempo di Nei sistemi interattivi il tempo di risposta deve essere il minimo possibile risposta deve essere il minimo possibile per dare l'idea di continuità all'utente e per dare l'idea di continuità all'utente e la proporzionalità deve essere la proporzionalità deve essere rispettata, ossia il tempo di risposta rispettata, ossia il tempo di risposta deve essere proporzionale alla deve essere proporzionale alla complessità dell'azione.complessità dell'azione.

Classificazione Classificazione delle politiche di delle politiche di

schedulingschedulingLe politiche di scheduling della Le politiche di scheduling della CPU si differenziano in base a tre CPU si differenziano in base a tre criteri di classificazione:criteri di classificazione:

senza prelazione/con prelazionesenza prelazione/con prelazione

senza priorità/con prioritàsenza priorità/con priorità

statiche/dinamichestatiche/dinamiche

Prelazione (pre-Prelazione (pre-rilascio)rilascio)

Politiche senza prelazione Politiche senza prelazione (non pre-emptive)(non pre-emptive)

una volta che la CPU una volta che la CPU è stata assegnata ad è stata assegnata ad un processo, essa un processo, essa non può più essergli non può più essergli tolta se non quando tolta se non quando il processo ha il processo ha esaurito il suo tempo esaurito il suo tempo di servizio o di servizio o necessita di necessita di un'operazione di I/O.un'operazione di I/O.

Politiche con prelazione Politiche con prelazione (pre-emptive)(pre-emptive)

la CPU può essere la CPU può essere forzatamente tolta al forzatamente tolta al processo in corso di processo in corso di esecuzione per esecuzione per essere assegnata ad essere assegnata ad un altro processo. un altro processo.

PrioritàPrioritàPolitiche senza prioritàPolitiche senza priorità

pongono i pongono i processi sullo processi sullo stesso piano, dal stesso piano, dal punto di vista punto di vista dell’urgenza di dell’urgenza di esecuzione.esecuzione.

Politiche con prioritàPolitiche con priorità

distinguono e distinguono e suddividono in classi suddividono in classi i processi in stato di i processi in stato di pronto, a secondala pronto, a secondala della loro importanza della loro importanza o urgenza di o urgenza di esecuzione. Sono esecuzione. Sono necessarie nei necessarie nei sistemi real-time e sistemi real-time e interattivi.interattivi.

Statiche/Statiche/dinamichedinamiche

Politiche statichePolitiche statiche

un processo un processo conserva nel tempo i conserva nel tempo i suoi diritti di accesso suoi diritti di accesso all’unità centrale all’unità centrale (priorità)(priorità)

Politiche dinamichePolitiche dinamiche

i processi modificano i processi modificano nel tempo i propri nel tempo i propri diritti di accesso diritti di accesso all’unità centrale.all’unità centrale.

Politiche di Politiche di schedulazioneschedulazione

FCFS: First Come First FCFS: First Come First ServedServed

SJF: Shortest Job First -> SJF: Shortest Job First -> (SRTF)(SRTF)

Per priorità Per priorità

Round Robin Round Robin

FCFS: First Come FCFS: First Come First ServedFirst Served

La CPU è assegnata ai singoli processi La CPU è assegnata ai singoli processi in base al loro ordine nella coda dei in base al loro ordine nella coda dei processi pronti (ready queue), stabilito processi pronti (ready queue), stabilito in base al tempo di arrivo oppure dal in base al tempo di arrivo oppure dal numero identificativo (PID)numero identificativo (PID)

La ready queue è gestita in modalità La ready queue è gestita in modalità FIFO (First In First Out)FIFO (First In First Out)

al processo che giunge nella ready queue al processo che giunge nella ready queue viene attribuito l’ultimo posto della codaviene attribuito l’ultimo posto della codala CPU è assegnata al processo situato la CPU è assegnata al processo situato alla testa alla ready queuealla testa alla ready queue

FCFS: FCFS: caratteristichecaratteristiche

E’ senza prelazione: il processo in esecuzione E’ senza prelazione: il processo in esecuzione trattiene la CPU sino al termine del suo tempo trattiene la CPU sino al termine del suo tempo di servizio o fino a quando non necessita di di servizio o fino a quando non necessita di un’operazione di I/Oun’operazione di I/O

Tende a penalizzare i processi I/O bound e Tende a penalizzare i processi I/O bound e quelli di breve durata, poiché costretti a lunghe quelli di breve durata, poiché costretti a lunghe attese dietro processi CPU boundattese dietro processi CPU bound

Tempi di attesa molto variabili e generalmente Tempi di attesa molto variabili e generalmente lunghi. La gestione dei dispositivi è poco lunghi. La gestione dei dispositivi è poco efficiente ed è adeguata per sistemi batch efficiente ed è adeguata per sistemi batch (mancanza di interattività).(mancanza di interattività).

SJF: Shortest Job SJF: Shortest Job FirstFirst

La CPU è assegnata al processo il cui La CPU è assegnata al processo il cui intervallo di tempo previsto per intervallo di tempo previsto per l’utilizzo della CPU è più brevel’utilizzo della CPU è più breve

Nel caso in cui più processi pronti Nel caso in cui più processi pronti presentino gli stessi tempi di servizio, presentino gli stessi tempi di servizio, la scelta viene fatta secondo la politica la scelta viene fatta secondo la politica FCFSFCFS

SJF: due casiSJF: due casiSJF senza prelazioneSJF senza prelazione

il processo in esecuzione trattiene la CPU sino il processo in esecuzione trattiene la CPU sino al termine del suo tempo di servizio o fino a al termine del suo tempo di servizio o fino a quando non necessita di un’operazione di I/O.quando non necessita di un’operazione di I/O.

SJF con prelazioneSJF con prelazionese, ad un certo istante, nella coda dei processi se, ad un certo istante, nella coda dei processi pronti giunge un processo con un tempo di pronti giunge un processo con un tempo di servizio più breve di quello che rimane (da servizio più breve di quello che rimane (da completare) al processo in esecuzione, la CPU completare) al processo in esecuzione, la CPU viene rilasciata e ceduta al processo appena viene rilasciata e ceduta al processo appena arrivato (Shortest Remaining Time First - arrivato (Shortest Remaining Time First - SRTF)SRTF)

Scheduling per Scheduling per prioritàpriorità

A ciascun processo, in fase di A ciascun processo, in fase di generazione, viene attribuito un livello generazione, viene attribuito un livello di priorità, espresso da un numero di priorità, espresso da un numero interointero

La CPU è assegnata al processo che La CPU è assegnata al processo che presenta la massima priorità.presenta la massima priorità.

A parità di priorità, si ricorre alla A parità di priorità, si ricorre alla politica FCFSpolitica FCFS

Per priorità: due Per priorità: due casicasi

Senza prelazioneSenza prelazioneil processo in esecuzione trattiene la CPU il processo in esecuzione trattiene la CPU sino al termine del suo tempo di servizio o sino al termine del suo tempo di servizio o fino a quando non necessita di fino a quando non necessita di un’operazione di I/O.un’operazione di I/O.

Con prelazioneCon prelazionese nella coda dei processi pronti arriva un se nella coda dei processi pronti arriva un processo con priorità maggiore di quella processo con priorità maggiore di quella del processo in esecuzione, questo rilascia del processo in esecuzione, questo rilascia la CPU, cedendola al processo appena la CPU, cedendola al processo appena arrivato.arrivato.

Determinare la Determinare la prioritàpriorità

Priorità definite dal S. O. (p. interna)Priorità definite dal S. O. (p. interna)

Priorità definite dall’utente (p. esterna)Priorità definite dall’utente (p. esterna)

Priorità statica Priorità statica una volta stabilita, non varia nel tempouna volta stabilita, non varia nel tempo

Priorità dinamicaPriorità dinamicavaria nel tempo per evitare che alcuni varia nel tempo per evitare che alcuni processi possano essere bloccati per un processi possano essere bloccati per un tempo indefinito (starvation), a causa tempo indefinito (starvation), a causa della costante presenza nella ready queue della costante presenza nella ready queue di processi a più elevata prioritàdi processi a più elevata priorità

Starvation Starvation (attesa indefinita)(attesa indefinita)• Una possibile soluzione allo starvation è Una possibile soluzione allo starvation è

data dalla procedura di aging data dalla procedura di aging (invecchiamento): la priorità di un (invecchiamento): la priorità di un processo puòprocesso può– aumentare al crescere del suo tempo di aumentare al crescere del suo tempo di

attesaattesa– diminuire al crescere del tempo di CPU diminuire al crescere del tempo di CPU

già utilizzato già utilizzato

Round RobinRound Robin• La CPU viene assegnata, a turno, ad ogni La CPU viene assegnata, a turno, ad ogni

processo per un certo periodo processo per un certo periodo qq di tempo di tempo massimo (time-slice o quanto di tempo)massimo (time-slice o quanto di tempo)

• Se, alla fine di tale periodo, il processo in Se, alla fine di tale periodo, il processo in esecuzione non è terminato, esso viene esecuzione non è terminato, esso viene ricondotto nella coda dei processi pronti, ricondotto nella coda dei processi pronti, all’ultima posizioneall’ultima posizione

• Alla messa in esecuzione, il S. O. avvia un Alla messa in esecuzione, il S. O. avvia un dispositivo timer, trascorso l’intervallo dispositivo timer, trascorso l’intervallo qq, il , il timer genera un’interruzione che provoca il timer genera un’interruzione che provoca il prerilascio della CPUprerilascio della CPU

time-slicetime-slice• Un time-slice troppo grande rischia di far Un time-slice troppo grande rischia di far

tendere la politica Round Robin a quella FCFS.tendere la politica Round Robin a quella FCFS.

• Un time-slice troppo piccolo consente tempi di Un time-slice troppo piccolo consente tempi di risposta brevi ma impegna eccessivamente la risposta brevi ma impegna eccessivamente la CPU per le operazioni di context switch, con CPU per le operazioni di context switch, con conseguente calo della produttività e conseguente calo della produttività e dell’efficienza del sistema.dell’efficienza del sistema.

• Nei sistemi reali il valore del time-slice che Nei sistemi reali il valore del time-slice che garantisce buone prestazioni è compreso tra garantisce buone prestazioni è compreso tra 20 e 50 millisecondi.20 e 50 millisecondi.