Caricare documenti e articoli online 
INFtub.com è un sito progettato per cercare i documenti in vari tipi di file e il caricamento di articoli online.


 
Non ricordi la password?  ››  Iscriviti gratis
 

LO SCHEDULATORE DELLA CPU

informatica



LO SCHEDULATORE DELLA CPU


Questo schedulatore interviene nel momento in cui un processo passa fra gli stati running e wait, oppure quando un processo termina definitivamente la propria esecuzione, o ancora, nei sistemi a divisione del tempo, in occasione di un prerilascio (cfr. nota 19 a pag. 37). Gli algoritmi di scheduling della CPU hanno lo scopo di migliorare il THROUGHPUT, il TURNAROUND, il TEMPO DI ATTESA ed il TEMPO DI RISPOSTA.

Aumentare il THROUGHPUT significa aumentare il numero di lavori per unità di tempo, e quindi migliorare il rendimento del sistema. Sottolineiamo che l'aumento del throughput ha l'obbiettivo di massimizzare lo sfruttamento del sistema, in quanto cresce il numero di attività portate a termine, ma non necessariamente il grado di soddisfazione dell'utente. Il TURNAROUND è il tempo di attesa relativo ai lavori batch, cioè l'ampiezza dell'intervallo di tempo al termine del quale il sistema restituisce i risultati di tali lavori.



Il TEMPO DI ATTESA è la quantità di tempo che un processo deve aspettare nella coda pendente su di una certa risorsa. Se tale risorsa è proprio la CPU, tale 'coda pendente' sarà ovviamente la coda dei processi ready. Il TEMPO DI RISPOSTA è la quantità di tempo intercorrente tra l'istante in cui viene immesso l'input e quello in cui si riceve il primo carattere di output. Si noti che questo parametro è in genere in contrasto con il throughput. Migliorare il tempo di risposta significa aumentare il grado di soddisfazione dell'utente, ma anche (di solito) abbassare la resa globale del sistema.


Parliamo ora per sommi capi di alcuni algoritmi per la gestione del processore.


FIRST COME - FIRST SERVED. È il più semplice, ed è quello tipicamente usato dalla primitiva SIGNAL (nella sua più semplice interpretazione). Il primo processo arrivato sarà il primo ad essere servito. Potrebbe essere utilizzato per la schedulazione della CPU, come in effetti avviene in sistemi particolarmente semplici, ma in genere tale utilizzo non risulta vantaggioso perché, non contemplando esso la tecnica del prerilascio ('not preemptive'); il tempo medio di att 212e44c esa ne risulterebbe non ottimizzato. Si consideri il seguente esempio (P1, P2, P3 = nomi di processi):


- P1 richiede l'utilizzo continuato della CPU per 24 ms fino alla propria terminazione (il tempo di occupazione della CPU da parte di un processo è detto CPU BURST);

- P2 la richiede per 3 ms;

- P3 la richiede per 3 ms.


La schedulazione dei processi secondo la tecnica first come - first served, secondo l'ordine indicato, comporta un tempo di attesa medio di (0 + 24 + 27) / 3 = 17 ms. Se invece l'ordine è P2, P3, P1, il tempo di attesa medio diventa 3 ms.

Questo algoritmo è incompatibile con il time sharing visto che è in ogni caso impossibile il prerilascio (un processo non perde il controllo della CPU se non per terminazione o per l'attesa di un'operazione di I/O). Inoltre può dare luogo ad un EFFETTO CONVOY (= convoglio): supponiamo che si abbia un solo processo CPU bound (cioè a prevalente utilizzo della CPU) e molti processi I/O bound (cioè a prevalente utilizzo di periferiche). Supponiamo poi che tutti i processi I/O bound terminino le loro operazioni di I/O e si mettano quindi nella coda dei processi ready. Essi devono allora attendere che il processo CPU bound (attualmente in stato running) abbandoni l'utilizzo della CPU per dirottarsi verso una periferica, il che potrebbe richiedere una notevole lasso di tempo. Nel frattempo, i dispositivi di I/O rimangono inutilizzati. Prima o poi i processi I/O bound otterranno l'uso della CPU, ma la situazione si ripeterà identica in breve tempo, visto che essi sono caratterizzati da un tempo di utilizzo della CPU molto rapido. In pratica, il sistema da multiprogrammato diviene monoprogrammato (sistema completamente mal sfruttato).


2) ROUND ROBIN. Alla risorsa è associata un timer che ne fissa il massimo periodo di tempo di utilizzo consecutivo da parte di un processo. I processo in attesa su tale risorsa seguono l'ordine di una coda circolare. In riferimento alla CPU, questa tecnica consiste nel considerare una coda in cui viene sistemato il processo attualmente in esecuzione (running - ready) nel momento in cui scatta il timer.

Nella sua forma più elementare consiste nella sola aggiunta di un timer all'algoritmo first come - first served. Ovviamente, la bontà delle sue prestazioni è legata al timer. Più è ridotta l'ampiezza della slice di tempo, meglio vanno le cose in paragone al tempo medio di att 212e44c esa che può essere offerto dal metodo 1. Va detto anche però che nel caso della CPU le slice di tempo non devono essere tanto piccole da ottenere l'effetto negativo di perdere più tempo a cambiare contesto che non ad effettuare le elaborazioni (aumento dell'overhead del sistema). Quindi la slice deve essere dimensionata opportunamente, mantenendo sempre al di sopra di un certo limite il rapporto tra ampiezza della slice e tempo di cambio di contesto.


3) SHORTEST JOB (PROCESS) FIRST  (SJF). Vediamo cosa succede quando si introduce il concetto di priorità, e in particolare nel caso in cui si adotti un tipo di priorità legato alla quantità di tempo di utilizzo della risorsa da parte del processo. Poniamo che sia data la priorità all'utilizzo della risorsa, fra tutti i processi che la richiedono, a quello che la impegnerà per minor tempo. Uno schedulatore di job che adottasse questo criterio aprirebbe sempre il job 'più corto'. Storicamente, questo è stato una delle tecniche di schedulazione ideate per prime, e difatti prende il nome dal modo in cui venivano chiamati un tempo i processi (job). Naturalmente esso può essere applicato, con ottimi risultati, anche all'uso della CPU (SHORTEST CPU BURST) ed è, fra gli algoritmi di schedulazione, quello che privilegia, ottimizzandolo, il tempo medio di attesa nell'uso della CPU stessa o più in generale di una risorsa.

Questo sistema, tuttavia, presenta anche un ovvio, notevole problema, e cioè quello di dover preconoscere il tempo di utilizzo di una risorsa per ciascun processo in attesa sulla medesima. È naturale che questo tempo non possa essere calcolato in maniera esatta, ma anche farne una semplice stima non è un'impresa da poco.

Ad esempio, in riferimento al caso dei job, il carico complessivo esercitato sul sistema da un job in termini di tempo deve essere misurato considerando il tempo globale di utilizzo della CPU ma anche il tempo globale di I/O, il numero dei caratteri trasferiti e la velocità del canale di trasmissione; viene poi applicato un parametro che 'scala' questo tempo complessivo riportandolo ad un tempo equivalente di CPU. L'utente, nel sottoporre al sistema l'esecuzione di un job, fornisce il 'tempo massimo di utilizzo della CPU' che verrà preso per buono dallo schedulatore; se questo intervallo di tempo scade prima che il job sia effettivamente terminato, il processo viene abortito e l'utente viene così 'multato' mediante la mancata consegna dei risultati. Quindi all'utente conviene in ogni caso stimare quel quantitativo di tempo per eccesso.

In un moderno sistema multiprogrammato è ovviamente il SO ad assumersi la responsabilità di effettuare una stima della CPU burst. Come può il SO sapere quale sarà il prossimo tempo di occupazione della CPU di un processo che è appena entrato nella coda dei processi ready? Viene effettuata una stima più o meno approssimata, basata su criteri a volte sofisticati, a volte piuttosto banali (è quanto accade in UNIX).


Dimostriamo ora con un esempio che questo algoritmo è effettivamente in grado di abbassare i tempi medi di attesa. Sono dati i quattro processi P1, P2, P3 e P4.


P1 richiede la CPU per 6 ms. 

P2 richiede la CPU per 8 ms. 

P3 richiede la CPU per 7 ms. 



P4 richiede la CPU per 3 ms. 


La schedulazione SJF (P4, P1, P3, P2) comporta un tempo di attesa medio di 7 ms, mentre la schedulazione fatta secondo l'ordine dato richiede un tempo di attesa medio di 10,25 ms.

Cerchiamo ora di capire come può essere fatta una stima della CPU burst. Un tipo di stima al quale tipicamente ci si affida è quella della media esponenziale:


tn+1 a * tn + (1 - a tn


dove tn è il CPU burst appena trascorso (questa informazione ovviamente può essere calcolata con esattezza), tn la stima di tale CPU burst, così come era stata effettuata precedentemente, e tn+1 la stima dell' (n+1)-esimo CPU burst; a è un parametro che varia tra 0 e 1.


La stima del prossimo CPU burst quindi viene fatta a partire dall'ultima stima tn e dall'ultimo tempo misurato tn. Sviluppando la precedente espressione, si ha:


tn+1 a * tn + (1 - a a * tn-1 + ... a)j * a * tn-j + ... + (1 - a)n+1 * t


Quindi, per la determinazione di questa formula è necessario memorizzare tutti i tempi effettivi di CPU burst, a partire da quello iniziale, più il valore t (sostanzialmente una costante arbitraria). Applicare la formula vuol dire, concettualmente, basare la stima del tempo di utilizzo della CPU su tutta la storia del sistema fino a questo momento; tale stima è 'pesata' mediante il coefficiente a. Mediante lo studio dei casi limite, saremo aiutati a comprendere il significato di questo coefficiente:




- se a = 0, si ha dalle due formule rispettivamente tn+1 tn e tn+1 to


- se a = 1, si ha tn+1 = tn da entrambe. Ciò significa che la stima del prossimo CPU burst è pari alla durata esatta dell'ultimo CPU burst.


Se ne deduce che se a , la stima viene affidata non solo alla durata dell'ultimo CPU burst ma anche ad alcuni dei CPU burst precedenti; quanto più a tanto più viene tenuta in conto l'evoluzione del sistema.

Quando un processo va in esecuzione, esso occupa la CPU per qualche istante, dopodiché si mette in attesa sul semaforo di una risorsa. Se si tratta di un processo I/O BOUND, sarà caratterizzato da CPU burst molto brevi; al limite di questo comportamento si può dire che esso utilizzerà la CPU al solo scopo di lanciare le operazioni di I/O. Viceversa se è un processo rigorosamente CPU BOUND, esso non sarà disposto a 'mollare' la CPU neanche per un istante e potrà essere interrotto solo grazie all'intervento del timer (CPU burst lunghi). Ma, per la verità, non esiste alcun processo che sia per natura e per tutta la sua vita interamente I/O BOUND o CPU BOUND. Ogni processo evolve eseguendo il flusso di controllo di un programma sequenziale e oscilla dinamicamente tra le due 'anime' I/O BOUND e CPU BOUND a seconda della zona in cui si trova (cioè a seconda del fatto che in quella zona si eseguano o meno operazioni di I/O). È altrettanto naturale rendersi conto del fatto che un processo non commuta con istantanea rapidità tra i due stati di I/O BOUND e CPU BOUND, ma ad esempio permane per un po' di tempo nello stato CPU BOUND. Quindi, all'atto pratico non serve tener conto dell'intera storia del processo (a partire cioè dall'origine dei tempi), ma per fare una buona stima è sufficiente conoscere la sola storia recente del processo. Per tale motivo in genere si fissa il parametro a in modo da considerare solo i più recenti CPU burst. Ovviamente, però, la stima sarà meno attendibile se viene fatta proprio in un momento in cui il processo passa dall'essere I/O BOUND all'essere CPU BOUND.


Come si è accennato, l'algoritmo SJF può essere implementato in combinazione con l'uso di un timer e in tal caso si parla preemptive SJF o meglio di SHORTEST REMAINING TIME FIRST. Si potrebbe procedere ad esempio nel modo che viene proposto di seguito. Quando scatta il timer, il CPU burst del processo interrotto viene decurtato del quantitativo di tempo già effettivamente impiegato nell'uso della CPU, dopodiché quest'ultima viene assegnata al processo caratterizzato dal CPU burst più breve.

In realtà questo algoritmo non è usato perché troppo pesante. Infatti, ad ogni scatto del timer la formula dovrebbe essere applicata per tutti i processo presenti nella coda ready; oppure si potrebbe pensare di usare delle code multiple (vedi oltre), stimando il CPU burst per ogni processo che diventa ready e poi inserirlo in una opportuna coda di priorità. In questo caso si dovrebbe discretizzare la priorità, assumendola uguale per tutti i processi la cui CPU burst stimata appartiene ad un determinato intervallo di tempo.

Nei fatti, vengono usati dei trucchi per applicare l'algoritmo considerato ma senza dover fare troppi calcoli. Per esempio, davvero geniale è lo stratagemma utilizzato nel SO UNIX: nel descrittore di ogni processo è presente tra l'altro un contatore, incaricato di contare il tempo durante il quale il processo è running. (Ad esempio, tale contatore viene incrementato ogni 20 ms). Un secondo contatore, situato in un diverso campo del medesimo descrittore, viene incrementato insieme al primo mentre il processo è running, ma periodicamente (sulla base degli istanti di tempo scanditi da un altro timer) esso viene dimezzato, e questo indipendentemente dal fatto che il processo sia o meno running. Allora, quando il processo diviene ready esso assume un livello di priorità dipendente da questo secondo contatore. Se in questo campo del descrittore è registrato un valore basso, vuol dire che quel contatore ha avuto pochi incrementi e molti dimezzamenti; negli ultimi periodi, tra un dimezzamento ed un altro, esso non è stato mai incrementato, oppure che ha avuto un basso incremento, e quindi il processo ha eseguito dei cicli di CPU burst molto brevi. A tale processo si assegna implicitamente una maggiore priorità. Se invece quel valore è alto, questo è il segno che gli ultimi CPU burst sono stati piuttosto lunghi. Quindi al processo si assegna implicitamente una priorità più bassa. [1]




Esistono molti altri algoritmi a priorità, nei quali però il concetto di priorità è fondato non sul tempo di impiego della CPU, ma su altri parametri di giudizio. Ricordando che, almeno in linea di principio, ogni algoritmo a priorità può generare il fenomeno dello STARVATION, occorrono dei metodi per evitare questo pericolo e nella maggioranza dei casi la tecnica usata a questo scopo è quella dell'invecchiamento (AGING): la priorità dei processi che attendono da più tempo viene automaticamente innalzata.


Abbiamo fuggevolmente accennato alla gestione della priorità mediante code multiple; esaminiamo ora più da vicino questo particolare metodo di schedulazione.


4) SCHEDULER A CODE MULTIPLE CON FEEDBACK. In una schedulazione a code multiple, i processi vengono inserite in via permanente in determinate code a seconda di vari criteri di classificazione (ad esempio, in base all'occupazione di memoria, alla provenienza, al tipo di accesso, o, come si è visto, alla priorità). Una variante di questo sistema (feedback) consiste nel prevedere la possibilità che un processo possa spostarsi da una coda all'altra.


Questa tecnica di schedulazione è caratterizzata dalle seguenti voci:


- numero di code. Tornando all'esempio menzionato nella pagina precedente, in cui i processi vengono considerati più o meno prioritari a seconda del tempo stimato di occupazione della CPU, tali priorità vanno discretizzate proprio sulla base del numero di code che si hanno a disposizione.

- algoritmo di scheduling per ogni coda: di solito è il first come - first served.


- criterio di allocazione in una coda di un processo in arrivo (wait - ready).


- metodo per variare nel tempo la priorità di un processo e quindi la sua appartenenza ad una coda.


Riguardo a quest'ultimo punto, un criterio spesso adottato è quello di associare ad ogni coda una slice di tempo. La coda a più bassa priorità ha una slice di durata maggiore, quella di priorità più alta ne ha una di durata minore; quando un processo perde l'usufrutto della CPU per effetto del timer, diventa ready e viene quindi inserito nella coda di livello più basso, invece che in quella da cui era stato preso. Si osservi che l'handicap costituito dall'essere stato assegnato al livello più basso di priorità è controbilanciato dal fatto che la slice di tempo che avrà a disposizione nel momento della sua successiva attivazione sarà la più ampia possibile.

Il corrispondente accorgimento da adottare nell'altro senso consiste nel 'premiare' quei processi che interrompono la propria esecuzione, sull'attesa di un'operazione di I/O, notevolmente prima della fine del loro quanto di tempo, ad esempio prima di metà della durata della relativa slice; la prossima volta che un processo simile diventerà ready, sarà assegnato alla coda corrispondente al tempo di metà di quella slice (e quindi a maggiore priorità).

Riassumendo, in questo sistema un processo 'naviga' tra le code salendo o scendendo lungo i vari livelli di priorità a seconda del fatto che abbia travalicato la slice o che si sia mantenuto al di sotto della metà di essa.


Si noti allora che, usando questa tecnica, in effetti la priorità viene variata sulla base dello stato di I/O BOUND o CPU BOUND del processo. Difatti se il timer è scattato mentre il processo stava usando la CPU, ciò vuol dire che esso era nello stato CPU BOUND, e quindi il fatto di assegnarli una slice di tempo superiore (all'atto di abbassare la sua priorità) potrebbe permettergli di completare la sua elaborazione in occasione della prossima attivazione. Analogamente dicasi del caso in cui il processo si pone in attesa, assumendo quindi un carattere I/O BOUND, prima dello scadere del tempo. Si può affermare in definitiva che al processo viene assegnata una priorità più alta quando esso diviene I/O BOUND, più bassa quando diviene CPU BOUND.



Un caso particolare dell'algoritmo generale di gestione a code multiple è quello di un sistema che presenta due sole code, una prioritaria per i processi time sharing conversazionali (gestita secondo la disciplina round robin) ed un'altra, meno prioritaria, concernente i processi che nascono da job di tipo batch (gestita secondo la disciplina first come - first served). Quando arriva un processo nella prima coda (foreground) in un momento in cui è in esecuzione un processo della coda meno prioritaria, quest'ultimo subisce un prerilascio e la CPU viene automaticamente assegnata al processo appena arrivato, a motivo della sua maggiore priorità. Il tempo globale di CPU viene però ripartito in modo da garantire che i processi della seconda coda possono comunque operare prima o poi, onde evitare che i processi conversazionali monopolizzino lo sfruttamento del sistema.




In questo punto De Carlini ha fatto un'osservazione poco chiara: "Il dimezzamento serve a trascurare i CPU burst che sono lontani nel tempo rispetto al momento in cui ci troviamo".






Privacy




Articolo informazione


Hits: 2363
Apprezzato: scheda appunto

Commentare questo articolo:

Non sei registrato
Devi essere registrato per commentare

ISCRIVITI



Copiare il codice

nella pagina web del tuo sito.


Copyright InfTub.com 2024