Realizzazione di un driver

REALIZZAZIONE DI UN DRIVER

Oggi vedremo più da vicino le routine che rappresentano i 'mattoni di costruzione' mediante i quali  vengono realizzati i driver. Ricordiamo che i driver che possono essere eseguiti nel contesto del processo che li richiede (il processo utente effettua una chiamata al kernel per poter eseguire il driver, e quindi accedere alla periferica) o nel contesto di un processo driver appositamente incaricato, con il quale i processi utente si sincronizzano, stabilendo un rapporto cliente-servitore. In entrambi i casi il kernel deve disporre di determinate procedure necessarie per scrivere questi driver. Per schematizzare la cosa, supporremo di fare riferimento ad un necessaire di tali procedure costituito da una procedura per l'avvio dell'operazione di scrittura sulla periferica, una per l'arresto della scrittura, una per effettuare un'operazione di input, una per effettuare un'operazione di output, una per acquisire uno stato.

Il codice in pascal-like di tali procedure è il seguente:

Procedure Start_IO (p: dispositivo_periferico) ;

begin

< esecuzione delle istruzioni macchina per trasferire nel registro

di controllo dell'interfaccia i bit di attivazione del dispositivo

e di abilitazione dell'interfaccia ad operare ad interruzione > ;

end ;

Procedure Halt_IO (p: dispositivo_periferico) ;

begin

< esecuzione delle istruzioni macchina per trasferire nel registro

di controllo dell'interfaccia i bit di disattivazione del dispositivo > ;

end ;

Procedure Get (p: dispositivo_periferico; var d: dato) ;

begin

d : = < registro buffer dell'interfaccia > ;

end ;

Procedure Put (p: dispositivo_periferico; d: dato) ;

begin

< registro buffer dell'interfaccia > : = d ;

end ;

Procedure Get_status (p: dispositivo_periferico; var s: dato) ;

begin

s : = < registro di stato dell'interfaccia > ;

end ;

Tali procedure sono scritte nel modo più generale possibile. Non è possibile dire di più, in quanto la loro reale implementazione dipende ovviamente dalla struttura della periferica ed in particolare da quella della sua interfaccia. Per scrivere queste routine in ASSEMBLER, bisogna conoscere esattamente gli indirizzi associati ai registri di interfaccia e la funzione svolta da ciascuno di essi, onde potervi inviare quelle determinate sequenze di byte che permetteranno alla periferica di partire, fermarsi eccetera.

Se il processo utente si rivolge direttamente al Kernel, le procedure del Kernel verificano se l'utente può accedere alla periferica (e cioè se questa è libera o occupata), e in caso affermativo vengono attivate le routine necessarie ad avviare l'operazione.

Se invece si usa la tecnica del processo driver, le procedure di dialogo con la periferica fanno parte di quest'ultimo, e dunque il processo utente deve rivolgersi al processo driver chiedendo l'esecuzione di una di tali procedure. Ad esempio un modo di procedere per realizzare la comunicazione tra processo utente e processo driver è quello di usare una struttura monitor: in questo caso potremmo sfruttare i metodi già visti per la cooperazione tra processi nel modello a memoria comune. Si userebbe un buffer circolare per lo scambio delle informazioni tra i due processi, una procedura SEND che permette al processo utente di caricare un elemento del buffer centrale con i dati da dare in output, una RECEIVE per prelevare dal buffer i dati da dare in input o in output ed una procedura interna al monitor che permette al driver di prendere i dati dal buffer circolare e mandarli in output.

In questo caso il processo driver si farebbe carico di realizzare la maggioranza delle operazioni. In particolare, dovrebbe fare lui le operazioni di START I/O, HALT I/O, PUT e GET e utilizzerebbe il monitor solo per scambiare informazioni con il processo utente che richiede il servizio di I/O, e in particolare per fra da ponte tra il buffer circolare ed il buffer dell'interfaccia [1]. Si noti dunque che in questo caso si ha lo svantaggio di dovere effettuare più copie del messaggio di input o output, ma anche il vantaggio di 'esplodere il parallelismo'. Mentre ad esempio il processo driver esegue uno spostamento di caratteri dal buffer privato verso il buffer della periferica, in parallelo un altro processo utente può caricare il buffer circolare del monitor. Se invece anche tutte le routine summenzionate (START I/O etc.) vengono poste all'interno del monitor, si risparmia un'operazione di copia (tali routine accederebbero infatti direttamente al buffer del monitor), ma si riduce di molto il parallelismo, visto che all'interno di un monitor può esserci al massimo un processo attivo per volta.

Quale che sia la tecnica scelta, il kernel deve prevedere il fatto che nel momento in cui giunge dalla periferica un segnale di interrupt di fine I/O, e si entra quindi nella ISR, questa deve far ripartire il processo nel cui contesto il driver viene eseguito (rispettivamente, si tratterà del processo driver oppure di quel particolare processo utente che è entrato nel Kernel chiedendo di eseguire il processo driver). Abbiamo già visto che nel caso più semplice si suppone di avere una procedura wait_for_interrupt, che è una WAIT su di un semaforo privato con la quale il processo che esegue il codice di entrata si arresta, e una SIGNAL nel ramo della ISR nel quale si entra in occasione dell'interrupt, in modo tale che il processo arrestato possa riprendere la esecuzione.

Un'ottimizzazione potrebbe consistere nel mettere nella ISR, piuttosto che una semplice SIGNAL, una specializzazione di quest'ultima, e precisamente una procedura di risposta alla interruzione.

Infatti una SIGNAL ordinaria inserita nella ISR avrebbe semplicemente l'effetto di inserire il processo che ha eseguito la wait_for_interrupt (e quindi il processo driver nel modello che più ci interessa) nella coda dei processi ready. È bene invece che la coda del driver abbia la massima priorità, e che quindi sia riattivata immediatamente all'arrivo dell'interruzione di ritorno, rimpiazzando il processo che nel frattempo era stato posto in esecuzione nella CPU. Infatti, l'esecuzione della coda del driver ha anche l'effetto di liberare la periferica, la quale diversamente potrebbe rimanere bloccata per troppo tempo. Con una SIGNAL normale diminuisce il THROUGHPUT, cioè il numero di lavori sviluppati nell'unità di tempo. Con la procedura che andiamo a presentare adesso, invece, si 'esplode meglio' il parallelismo tra le operazioni sulla unità centrale e sulla periferica.

Procedure Risposta_interruzione (sp: indice_semaforo) ;

var k: indice_processi;

Procedure Inserimento_testa ;

var j : indice_processi ;

begin

j : = processo_in_esecuzione ;

descrittore_processo j .successivo : = coda_processi_pronti .primo ;

coda_processi_pronti .primo : = j ;

end ;

begin

Salvataggio_stato ;

Inserimento_testa ;

with semafori sp do

begin

if coda.primo <> 0 then

begin

Prelievo (k, coda) ;

processo_in_esecuzione : = k ;

Ripristino_stato ;

end ;

else

contatore : = contatore + 1 ;

end

end ;

Si noti che sarebbe superfluo, benché formalmente corretto, usare una SIGNAL CON PRERILASCIO (cfr. nota 19 a pag.37); non ci si pone cioè il problema di paragonare la priorità del processo sbloccante e quella del processo sbloccato, in quanto si dà per scontato che lo sbloccante sia meno prioritario rispetto allo sbloccato [2]. Il processo interrotto deve perdere il controllo della CPU, e quindi si effettua il salvataggio dello stato, ma esso viene poi inserito in testa alla coda dei processi ready, anziché nella posizione che sarebbe dettata dalla sua priorità, dimodoché il processo interrotto riparta non appena termina l'esecuzione del driver. Questa operazione viene realizzata dalla routine Inserimento_testa.

A questo punto viene sbloccato il processo che si era arrestato su quel semaforo privato con la Wait_for_interrupt. Da notare che il ramo else non dovrebbe mai essere percorso, dato che se viene eseguita la procedura Risposta_interruzione un qualche processo deve pur essersi messo in attesa sulla coda del semaforo; tuttavia, la procedura ha un carattere più generale e prevede anche il caso di risposta alla interruzione di un timer (attivazione di un processo dopo un certo intervallo di tempo) nel qual caso potrebbe effettivamente accadere che non ci sia nessun processo ad aspettare.

Le cose si semplificano notevolmente ricorrendo ad una procedura di risposta ad interruzione più banale:

Procedure Risposta_interruzione (p: dispositivo_periferico) ;

Procedure Inserimento_testa ;

begin

< idem >

end ;

begin

Salvataggio_stato ;

Inserimento_testa ;

processo_in_esecuzione : = driver p

Ripristino_stato ;

end ;

In questo caso si rinuncia a fare qualunque analisi, e in risposta al segnale di interruzione si attiva direttamente il processo driver p . Driver è un vettore contenente i driver delle varie periferiche. Il suo elemento di posto p viene ripristinato, con un'ulteriore ottimizzazione dei tempi..

In UNIX non esiste il concetto di processo driver, ma le operazioni di ingresso uscita possono essere realizzate solo da parte del processo utente mediante chiamate al kernel. La ISR possiede tanti rami quanti sono i driver, e in ognuno di essi è presente la coda del rispettivo driver, la quale viene eseguita. Dopodiché si torna al processo utente.

Nei fatti, il processo utente è penetrato verso l'interno del SO, strato per strato, mediante una sequenza di chiamate, fino ad entrare nel kernel e a lanciare una operazione periferica; quindi dopo l'esecuzione di tale operazioni la stessa sequenza di chiamate dovrà essere eseguita, ma a ritroso e nel modo più rapido possibile. Il processo utente all'interno del Kernel assume una priorità altissima rispetto a quella che deterrebbe rimanendo al suo esterno.

ALGORITMI DI SCHEDULING

Nel parlare degli algoritmi di scheduling, non faremo riferimento ad un particolare tipo di risorsa. Osserviamo che abbiamo già esaminato un algoritmo di scheduling, relativo all'accesso ad un disco a testine mobili da parte dei processi (algoritmo dell'ascensore, pag.99 sgg.).

I tre tipi fondamentali di schedulatore sono:

- lo schedulatore a breve termine (o di CPU);

- lo schedulatore a medio termine (o di swap);

- lo schedulatore a lungo termine (o di job).

Lo schedulatore di CPU è quello che interviene più frequentemente, anzi possiamo dire che esso viene continuamente attivato. Un altro schedulatore importante, che si trova in tutti i sistemi, è quello a medio termine la cui funzione vedremo essere legata alla schedulazione della memoria; e questo vale qualunque sia la tecnica di gestione della memoria. Infatti ogni processo ha bisogno di memoria per andare in esecuzione, e potrebbe essere conveniente spostare nella memoria di massa, e in particolare nell'AREA DI SWAP, un certo quantitativo di processi, scelti tra quelli che potrebbero potenzialmente eseguire la transizione ready - running. Tale schedulatore gestisce allora l'area di SWAP (che è sempre indipendente dai File System) e le operazioni di swap-in, swap-out con opportune strategie di scelta.

Lo schedulatore a lungo termine si può trovare soprattutto nei vecchi sistemi, gestiti a lotti; in questi sistemi la sua funzione consisteva nell'eseguire determinati lavori in un momento in cui il sistema risultava libero, perché non impegnato a svolgere lavori considerati più importanti (conversazionali). Tali job venivano portati avanti quindi in parallelo con gli altri dallo schedulatore della CPU. Ovviamente, al momento della terminazione dei job conversazionali, lo schedulatore a lungo termine doveva decidere quale nuovo job aprire, e in genere ciò veniva fatto sulla base del banale criterio di assegnare la maggiore priorità ai processi che impegnavano la CPU per meno tempo.

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 attesa 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 attesa 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:

t_n+1 a * t_n + (1 - a t_n

dove t_n è il CPU burst appena trascorso (questa informazione ovviamente può essere calcolata con esattezza), t_n la stima di tale CPU burst, così come era stata effettuata precedentemente, e t_n+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 t_n e dall'ultimo tempo misurato t_n. Sviluppando la precedente espressione, si ha:

t_n+1 a * t_n + (1 - a a * t_n-1 + a)^j * a * t_n-j + + (1 - a)ⁿ⁺¹ * 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 t_n+1 t_n e t_n+1 t_o

- se a = 1, si ha t_n+1 = t_n 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 I , la stima viene affidata non solo alla durata dell'ultimo CPU burst ma anche ad alcuni dei CPU burst precedenti; quanto più a 0, 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. [3]

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.