Scheduling della CPU - Altervista

Scheduling della CPU

©GiseldaDeVita- 2019 1

Immagine delbaristacreatedbymacrovector - www.freepik.comhttps://www.freepik.com/free-vector/barista-character-collection_1111132.htm

schedulingLo scheduler, in informatica, è un componente di un sistemaoperativo ovvero un programma che implementaun algoritmo di scheduling il quale, dato un insieme di richiestedi accesso ad una risorsa (tipicamente l'accesso al processore da parte di un processo da eseguire), stabilisce un ordinamentotemporale per l'esecuzione di tali richieste, privilegiando quelleche rispettano determinati parametri secondo una certa politicadi scheduling, in modo da ottimizzare l'accesso a tale risorsa e consentire così l'espletamento del servizio/istruzione o processodesiderato.

(Wikipedia)


Al bar…Al bar arrivano 4 persone quasi contemporaneamente e ordinano al bancone cose diverse…

©GiseldaDeVita- 2019

caffè cappuccino

Unbicchiered’acqua

Unaspremutadimelograno

3

Il barista…Il barista sa che ci vuole molto poco tempo per dare un bicchiere d’acqua, poco per il caffè, un po’ di più per il cappuccino e tanto di più per

preparare una spremuta…

Ora il barista dovrà decidere in cheordine comincerà a lavorare per

accontentare i clienti del bar.


Rispettando l’ordine in cui sono arrivati


Il barista decide che, per non fare torto a nessuno, nell’ordine con cui i clienti hanno fatto la loro richiesta verranno serviti.Serve quindi il cappuccino, il caffè, la spremuta, un bicchiere d’acqua, e infine la spremuta.Senza saperlo, il barista ha utilizzato

l’algoritmo FCFS, First Come First Served.

5

Al bar il giorno dopo la stessa situazioneAl bar arrivano 4 persone quasi contemporaneamente e ordinano al bancone cose diverse…


caffècappuccino



6

Prima gli ordini più veloci


Il barista, il giorno prima, aveva fatto aspettare molto la signora che aveva chiesto il bicchiere d’acqua per cui decide, questa volta, di partire dagli ordini più veloci senza preoccuparsi dell’ordine…Serve un bicchiere d’acqua, poi il caffè, il cappuccino e infine la spremuta.Senza saperlo, il barista ha utilizzato

l’algoritmo SJF, Shortest Job First.

7

Al bar il giorno dopo ancora…Al bar arrivano 4 persone quasi contemporaneamente e ordinano al bancone cose diverse …


Caffèdicorsa!Ho

l’autoindoppiafila!

Uncappuccinohomoltafretta!!!

Unbicchiered’acqua,ho

fretta!Unaspremutadimelograno

8

Prima I clienti più esigenti


Il barista, adesso dovrà accontentare i clienti in base alle loro esigenze…Serve prima il caffè, poi il cappuccino, il bicchiere d’acqua ed infine la spremuta.Senza saperlo, il barista ha utilizzato

l’algoritmo con priorità.

9

Al bar il giorno dopo la stessa situazioneAl bar arrivano 4 persone quasi contemporaneamente e ordinano al bancone cose diverse…


caffècappuccino



10

Un pezzetto alla volta


Il barista stavolta decide di portare avanti i lavori dedicando un po’ di tempo a ciascuna attività.Mette il bicchiere nel lavandino per l’acqua,la tazzina in macchina per il caffè, taglia il melograno per il frullato, prepara il latte per il cappuccino, consegna l’acqua e così via…. Senza saperlo, il barista ha

utilizzatol’algoritmo RRRound Robin.

11

Un grafico per il barIl nostro barista-CPU mentalmente ha assegnato un certo “costo” in fattore di tempo e risorse per ognitipo di ordinazione.Possiamo schematizzare in questo modo:


ATTIVITA’ COSTO

Cappucino 3

Caffè 2

Spremuta 4

Acqua 1

12

Ordine di arrivo e prioritàPer non basarsi solo sul tempo che impiega ad accontentare il cliente, abbiamo bisogno anche delleinformazioni di arrivo delle richieste e anche di eventuali “priorità” (cliente con la macchina in doppiafila).


Ordine ATTIVITA’ COSTO Priorità

1 Cappucino 3 3

2 Caffè 2 4

3 Spremuta 4 1

4 Acqua 1 1

13

La priorità…Per comodità, per il bar, indichiamo la priorità maggiore corrispondente ad numero maggiore. A seconda dei sistemi operativi, la priorità dei processi viene settata in maniera esplicita in Windows o con un incremento/decremento nei comandi LINUX/UNIX effettuato tramite il comando nice.


Fonteimmagine:https://www.wikihow.it/Cambiare-la-Priorità-dei-Processi-in-Windows-Task-Manager

Diagramma di Gantt FCFS

Portiamo la tabella in un diagramma di Gantt applicandola prima soluzione pensata dal nostro barista


0 1 2 3 4 5 6 7 8 9 10 11

FCFS

FirstComeFirstServed

Cappuccino Caffè Spremuta Acqua

15

Diagramma di Gantt SJFDi seguito il diagramma di Gantt applicando la seconda soluzione pensata dal nostro barista prima i lavori più veloci!


0 1 2 3 4 5 6 7 8 9 10 11

SJF

ShortJobFirst

Acqua Caffè Cappuccino Spremuta

16

Diagramma a priorità

Di seguito il diagramma di Gantt applicando la soluzione a priorità


0 1 2 3 4 5 6 7 8 9 10 11

Priorità

Priorità

Caffè Cappuccino Acqua Spremuta

17

Diagramma Round Robin

Di seguito il diagramma di Gantt applicando la soluzione con algoritmo Round Robin


0 1 2 3 4 5 6 7 8 9 10 11

RR

RoundRobin

Caffè Cappuccino Acqua Spremuta

18

ComparazioneMettendo i diagrammi insieme vediamo che in totale il barista ha impiegato sempre un tempo pari a 10


ComparazioneTutti i lavori sono finiti al tempo 10, ma i clienti son stati sempre serviti con successo in egual misura?Dobbiamo capire ora la differenza di efficienza, ovvero in quanto tempo il barista ha soddisfatto tutti i clienti? Quanto tempo hanno aspettato i clienti prima che partisse la lavorazione del loro ordine?Ora calcoleremo il tempo medio di completamento(fine elaborazione) ed il tempo medio di attesa (inizio elaborazione).


Tempo di completamento taskPer ogni tipo di algoritmo di scheduling, inseriamo una sbarra per indicare il termine di ogni singolo task.


Tempo di completamento taskRiportiamo ora i tempi di completamento suddivisi per algoritmo


FCFS Caffèà 5 Cappuccinoà3 Acquaà 10 Spremutaà9

SJF Caffèà 3 Cappuccinoà6 Acquaà 1 Spremutaà10

Priorità Caffèà 2 Cappuccinoà5 Acquaà 6 Spremutaà10

RR Caffèà 5 Cappuccinoà8 Acquaà 3 Spremutaà10

22

Tempo medio di completamento taskCalcoliamo ora il tempo medio di completamento per capire quale algoritmo è stato più efficace nel completare prima tutti i task


FCFS Tcm =(5+3+10+9)/4 =27/4=6,75SJF Tcm =(3+6+1+10)/4 =20/4=5Priorità Tcm =(2+5+6+10)/4 =23/4=5,75RR Tcm =(5+8+3+10)/4 =26/4=6,5

23

Tempo di attesa inizio lavorazione taskPer ogni tipo di algoritmo di scheduling, inseriamo una sbarra per indicare l’inizio di lavorazione di ogni singolo task. Il primo lavoro che parte avrà tempo 0.


Tempo di attesaRiportiamo ora i tempi di attesa suddivisi per algoritmo


FCFS Caffèà 3 Cappuccinoà0 Acquaà 9 Spremutaà5

SJF Caffèà 1 Cappuccinoà3 Acquaà 0 Spremutaà6

Priorità Caffèà 0 Cappuccinoà2 Acquaà 5 Spremutaà6

RR Caffèà 0 Cappuccinoà1 Acquaà 2 Spremutaà3

25

Tempo medio di attesaCalcoliamo ora il tempo medio di attesa per capire quale algoritmo è stato più efficace nel diminuire l’attesa


FCFS Tam =(3+0+9+5)/4 =17/4=4,25SJF Tam =(1+3+0+6)/4 =10/4=2,5Priorità Tam =(0+2+5+6)/4 =13/4=3,25RR Tam =(0+1+2+3)/4 =6/4=1,5

26

Conclusioni

Dai valori ottenuti, il nostro barista ha accontentatoprima tutti i clienti utilizzando l’algoritmo SJF, ma ha dato la sensazione di farli attendere di meno iniziandoa lavorare la loro ordinazione con l’algoritmo RR.


Soluzione dello studente Lorenzo C.


Scheduling della CPU - Altervista

Documents

Transcript of Scheduling della CPU - Altervista