GESTIONE DEL PROCESSORE E DEI PROCESSI

Il processore è di gran lunga la componente principale di un sistema di elaborazione e pertanto la s corretta ed efficiente gestione è uno dei compiti principali di un sistema operativo. Il ruolo del processore è quello di eseguire programmi; pertanto la gestione del processore si dovrà occupare della corretta ed efficiente gestione ed esecuzione dei programmi. Più precisamente, introdotta la seguente definizione

• Un processo è un programma in esecuzione

diremo che il compito del sistema operativo è la gestione dei processi (a volte, per ragioni storiche, si usa anche il termine "job" per denotare un processo). Parleremo inoltre di "immagine di un processo" per riferirci al programma corrispondente al processo e ai dati su cui opera, per cui l'immagine rappresenta ciò che deve essere mantenuto in memoria principale per poter avere il processo stesso.

Per discutere in modo preciso i problemi che nascono dalla gestione del processore è importante riprendere la distinzione tra sistemi mono-programmati ("mono-tasking") e sistemi multi-programmati ("multi-tasking"). Storicamente i primi sistemi operativi (e ancora oggi alcuni sistemi per macchine meno potenti) adottavano la tecnica del mono tasking; secondo tale tecnica, un solo processo può essere attivo all'interno del sistema. Ciò significa che in tali sistemi è possibile eseguire un solo programma alla volta. I programmi possono quindi essere eseguiti solo in modo sequenziale: si potrà mandare in esecuzione un programma solo quando quello precedente avrà completamente terminato l'esecuzione. Un esempio di sistema con tali caratteristiche era il sistema MS/DOS, sistema operativo di Microsoft prima di Windows.

Il mono-tasking è una tecnica molto rigida, sia per quanto riguarda la visione dell'utente sia per quanto riguarda quella del sistema. Infatti:

• L'utente è forzato a sequenzializzare i suoi programmi. Ciò è riduttivo in quanto in molti casi gli utenti vorrebbero poter eseguire più programmi contemporaneamente. Ad esempio, un utente potrebbe essere interessato ad avere in esecuzione un programma per fare dei calcolo mentre sta usando un altro programma (ad esempio un elaboratore di testi per scrivere una lettera); in altri casi (come durante la scrittura di un testo), può essere interessante avere in esecuzione sia un programma di elaborazione di testi sia un programma di grafica per fare i disegni e quindi inserire disegni nel testo (o viceversa). La necessità di eseguire più programmi contemporaneamente è ancora più evidente in un sistema multi-utente; in tal caso non è pensabile che i diversi utenti siano costretti a sequenzializzare i loro programmi. Un semplice esempio può essere quello del sistema di elaborazione dati di una banca in cui vi sono molti utenti (i cassieri) che mediante terminali interagiscono con il calcolatore centrale. In tal caso, ovviamente, si vuole che i programmi dei diversi utenti siano eseguiti "contemporaneamente" (per cui tutti i cassieri possono fare operazioni "contemporaneamente").

• Nel caso di mono-tasking non è possibile effettuare una gestione efficiente del processore.

Analizziamo in dettaglio il secondo aspetto. Consideriamo due programmi P1 e P2 che devono essere mandati in esecuzione e supponiamo che P1 venga mandato in esecuzione per primo. Il processo corrispondente a tale esecuzione alternerà due diversi stati:

• in qualche momento il processo sarà attivo, ossia in esecuzione da parte del processore; ad esempio se P1 è un programma di elaborazione testi, subito dopo che l'utente ha dato un comando (ha introdotto del nuovo testo o ha dato il comando per la impaginazione del testo o per cambiare lo stile dei caratteri), il programma di elaborazione di testi sarà in esecuzione per soddisfare tale richiesta;

• vi saranno tuttavia lunghe fasi in cui il processo sarà fermo in attesa che l'utente dia un comando o introduca del nuovo testo.

Ciò capita in generale: qualunque processo P alterna fasi di esecuzione a fasi in cui è bloccato in attesa di qualche evento esterno (in attesa che sia terminata una operazione di input di dati necessari all'elaborazione oppure in attesa di poter usare una qualche risorsa, ad esempio in attesa che una stampante si liberi per poter fornire dati in output). Se si confrontano la velocità di elaborazione di un calcolatore (quindi i tempi in cui un processo è in esecuzione) e i tempi di lavoro delle periferiche di input/output (o addirittura di reazione umani), risulta che i secondi sono di multi ordini di grandezza maggiori dei primi. Ad esempio, si è notato che un elaboratore medio esegue una istruzione di un programma nell'ordine di grandezza di un milionesimo di secondo, mentre le periferiche di input/output operano in modo molto più lento e si può pensare che i tempi di reazione umani per fornire dei dati di input siano dell'ordine dei secondi. Il risultato è che se noi forziamo l'esecuzione sequenziale si avrà che mentre il processo attivo è bloccato in attesa di eventi esterni, il processore rimane del tutto inattivo (in "idle") e pertanto verrà sotto-utilizzato (si veda figura 2).

Figura 2 - Inefficienza dell'esecuzione sequenziale (lunghezza dei tratti di esecuzione e attesa non in scala)

Consideriamo ancora l'esempio di P1 e P2 riportato in precedenza; se assumiamo che P1 operi alternando veloci fasi di elaborazione (es da 1 msec) a fasi di attesa di dati di input (es attese di 1 sec); si avrà che mentre P1 è attivo il processore alterna fasi di attività da 1 msec a fasi di inattività di 1 sec. Si ha quindi un grado di utilizzazione del processore dello 0,1% (ossia per il 99,9% del tempo il processore rimane inattivo). P2 potrà andare in esecuzione solo quando P1 sarà completamente terminato (magari dopo minuti). Potrebbe essere invece ragionevole eseguire i due programmi "contemporaneamente": ogni volta che P1 è bloccato, invece di tenere i processore inattivo, si potrebbe mandare in esecuzione P2.

Più in generale si può pensare di estendere tale idea ad un numero qualunque di programmi da eseguire "contemporaneamente": si possono mantenere più processi attivi all'interno del sistema e fare in modo che il processore sia il più attivo possibile alternando opportunamente l'esecuzione dei vari processi. Questa è l'idea base dal multi-tasking: più programmi vengono eseguiti "contemporaneamente" sullo stesso processore. Si noti che il termine "contemporaneamente" è sempre usato tra virgolette. Infatti, essendoci un solo processore, non è possibile una esecuzione contemporanea reale (l'esecuzione in parallelo di due programmi è possibile solo se si hanno due processori che operano simultaneamente).

L'esecuzione di due programmi avviene alternando frequentemente l'esecuzione da uno all'altro (figura 3(a)).

Dal punto di viste del processore si ha che in ogni istante è in esecuzione un solo processo (figura 3(b)). Tuttavia, se lo scambio viene eseguito frequentemente (ad esempio ogni 10 millisecondi), l'utente ha l'impressione che l'esecuzione dei due programmi avvenga "contemporaneamente". A livello macroscopico si ha quindi l'impressione che vi sia contemporaneità, mentre a livello microscopico si ha una semplice alternanza sequenziale. Si noti che per ogni singolo programma il tempo di esecuzione (il tempo tra l'inizio e la fine) risulta aumentato, in quanto si ha l'alternanza di esecuzione con gli altri programmi. L'aspetto importante, tuttavia, è l'aumentato sfruttamento del processore (ma si dovrà fare in modo che il tempo di esecuzione di ogni singolo programma non aumenti troppo).

Figure 3 - Esecuzione "contemporanea" di P1 e P2

L'idea del multi-tasking è quindi quella di avere più processi attivi e di alternare opportunamente l'uso del processore da parte di tali processi.

Un processo durante la sua vita può trovarsi in tre diversi stati:

• in esecuzione: il processo ha attualmente l'uso del processore;

• in attesa (bloccato): il processo è in attesa del verificarsi di un evento esterno (tipicamente la terminazione di una operazione di input/output - come discusso in precedenza - o la possibilità di utilizzare una qualche risorsa attualmente in uso da parte di altri processi);

• pronto: il processo è potenzialmente in condizione di poter utilizzare l'elaboratore che tuttavia è occupato nell'esecuzione di un altro processo.

Non appena un processo viene creato (alla richiesta da parte di un utente di eseguire un programma o ad un comando) esso viene messo nello stato di "pronto" e in tale stato rimane fino a quando non arriverà il suo turno di utilizzare il processore. In generale vi possono essere molti processi nello stato di "pronto", tale numero si dice generalmente il "grado di multiprogrammazione del sistema". Non appena un processo viene selezionato esso passa nello stato "in esecuzione": per quanto osservato in precedenza, vi può essere in ogni istante al più un processo nello stato "in esecuzione". Un processo può abbandonare lo stato "in esecuzione" per tre diverse ragioni (si noti che nei primi due casi l'interruzione è "naturale" da parte del processo, nel terzo è forzata dal sistema):

• Terminazione: il processo termina la sua esecuzione. In tal caso il processo viene sospeso e abbandona il sistema.

• Richiesta di operazione di input/output o di una risorsa occupata. In tal caso il processo passa allo stato "in attesa", il processore viene liberato e può essere concesso ad altri processi "pronti".

• Cambio di esecuzione. Per realizzare in modo equo l'alternanza tra vari processi, in certi casi può essere opportuno fermare un processo, rimetterlo nello stato di "pronto" e concedere il processore ad un altro processo "pronto" (ritorneremo diffusamente più avanti su tale idea).

Un processo nello stato "in attesa" vi rimane fino a quando l'evento atteso non si è verificato (operazione di input/output terminata o risorsa disponibile). Al verificarsi dell'evento atteso il processo ritorna nello stato di "pronto". E' possibile quindi schematizzare gli stati di un processo e le possibili transizioni tra gli stati mediante il seguente diagramma (che verrà perfezionato in seguito):

Da un punto di vista differente, si può vedere il sistema come formato da un certo numero di "code", ognuna delle quali contiene i processi che si trovano nello stesso stato. Così avremo ad esempio una "coda dei processi pronti" ossia quei processi che potrebbero accedere all'uso della CPU e una coda (o più code) di processi in attesa (si può pensare ad una singola coda o a tante code, una per ogni evento esterno di cui si può essere in attesa - ad esempio, una coda dei processi che aspettano di poter usare la stampante, una coda dei processi che aspettano dati in input da un certo terminale e così via). Si ha quindi la seguente visione del sistema come un insieme di code di processi:

La gestione dei processi consiste nella gestione di tali code.

Prima di passare ad analizzare in dettaglio gli aspetti di gestione è importante osservare che, storicamente, non esiste un solo modello di esecuzione in multi-tasking. In particolare, sono stati considerati per lo meno tre modelli, corrispondenti a tre diverse necessità di elaborazione, che possono ancora oggi essere visti come una suddivisione grossolana di tre diverse famiglie di sistemi operativi multi-programmati:

• modello batch (a lotti);

• modello time-sharing (interattivo);

• modello real-time (in tempo reale).

Per comprendere il significato di tali modelli è interessante introdurre una distinzione tra due diversi tipi di processi (la distinzione sarà utile anche in seguito):

• processi compute-bound;

• processi I/O bound.

Alla prima famiglia appartengono quei processi che effettuano lunghe computazioni senza necessità di frequente interazione con l'esterno (con l'utente). Si pensi, ad esempio, ai programmi utilizzati in campo matematico per la risoluzione numerica di problemi. Tali programmi effettuano lunghe elaborazioni di tipo matematico (anche decine di minuti oppure ore) senza alcuna interazione con l'esterno. Alla seconda famiglia appartengono invece quei programmi che effettuano frequente interazione con l'esterno (utente). Si pensi, ad esempio, ad un programma di gestione di basi di dati con frequenti interrogazioni da parte dell'utente o di un programma di elaborazione di testi. E' evidente che tali diversi tipi di processi pongano diversi problemi di gestione ad un sistema operativo.

Il modello batch è nato storicamente per l'esecuzione di programmi compute-bound, la cui tipica interazione è del tipo: l'utente richiede l'esecuzione di un programma, poi se ne disinteressa e ritorna a recuperare i risultati dell'elaborazione dopo del tempo. In questo caso non è necessario una sofisticata alternanza dell'esecuzione dei processi per dare l'impressione della contemporaneità. L'idea della elaborazione batch è allora quella di mantenere un processo nello stato di "esecuzione" fino a quando esso non abbia terminato o si fermi in attesa di eventi esterni.

Il modello time-sharing è nato per la gestione di elaboratori usati prevalentemente per l'esecuzione di programmi I/O bound (interattivi). L'idea è quella di suddividere il tempo di elaborazione tra i vari processi (da cui il nome del modello) alternandone l'esecuzione: si prevede quindi di effettuare frequenti scambi di esecuzione tra processi.

Il modello "real-time" è nato invece per poter soddisfare esigenze di esecuzione in abito in cui il tempo di reazione dei programmi è critico. Si pensi, ad esempio, all'insieme dei programmi che controllano la navigazione di un aereo o all'insieme di programmi che gestiscono il funzionamento di una centrale elettrica. Vi saranno in tale ambito, programmi per la gestione di specifiche situazioni (ad esempio un guasto) e tali programmi devono andare in esecuzione immediatamente, non appena la condizione si sia verificata per intraprendere le azioni opportune. La gestione deve quindi essere effettuata rispettando i vincoli di criticità di tempo di esecuzione e risposta dei diversi programmi.

Data tale descrizione introduttiva, possiamo analizzare in dettaglio quali problemi debbano essere affrontati nella gestione del processore e dei processi, Vi sono, in particolare, almeno tre aspetti che devono essere posti in considerazione:

• aspetti organizzativi e di gestione (bookkeeping) per mantenere traccia di quali siano i processi e quale sia il loro stato;

• aspetti di strategia di gestione (politiche di gestione), per scegliere quale tra i processi pronti mandare in esecuzione;

• coordinamento, sincronizzazione mutua esclusione per fare in modo che i processi non si ostacolino e danneggino a vicenda

Gestione dei processi

Il primo aspetto che deve essere preso in considerazione è quello puramente gestionale. Per gestire più processi attivi contemporaneamente è necessario mantenere traccia di tutti tali processi. In particolare, è necessario ricordarsi, per ognuno dei processi, alcune informazioni quali le sue caratteristiche, il programma che sta eseguendo, lo stato in cui si trova (pronto, in esecuzione, in attesa), a quale punto del programma si è arrivati. Inoltre è necessario poter mantenere in memoria l'immagine di ognuno dei processi, ossia il codice dei programmi in esecuzione e i dati su cui sta lavorando (ritorneremo su tale argomento nel paragrafo sulla gestione della memoria principale). Per disporre di tali informazioni il sistema operativo mantiene, in memoria principale in una zona riservata al sistema stesso, una tabella (la tabella dei processi o PCBT - Process Control Block Table) in cui viene registrata tutta l'informazione concernente i diversi processi attivi. In particolare tale tabella contiene un descrittore (un elemento) per ognuno dei processi, con le seguenti informazioni (oltre ad altre che non considereremo):

• identificatore del processo: ogni processo è identificato da un nome (di solito numerico) unico;

• identificatore dell'utente proprietario; tale informazione è particolarmente importante nel caso di sistemi multi-utente, in quanto permette di realizzare meccanismi di protezione;

• stato del processo; indica lo stato attuale del processo ("pronto", "in esecuzione" o "in attesa");

• valore del registro Program Counter (P.C.); tale informazione permette di ricordare a che punto il processo è arrivato nel corso della sua elaborazione;

• contenuto di tutti i registri dell'unità centrale (torneremo tra breve sull'utilità di tali informazioni);

• informazioni sui file attualmente in uso; informazioni sulle risorse hardware (periferiche) attualmente in uso;

• informazioni sull'utilizzo della memoria centrale e della memoria secondaria, ossia informazioni sulla posizione del processo in memoria principale e/o secondaria;

• informazioni per lo scheduling; ad esempio priorità del processo.

Come anticipato, l'utilità di alcune di queste informazioni sarà chiara solo più avanti analizzando altri aspetti del sistema operativo. Al momento è interessante concentrarci sulle necessità di mantenere il valore del registro P.C. e di tutti gli altri registri del processore.

Si è osservato ripetutamente che nel multi-tasking i processi si alternano nell'esecuzione. Affinché tale alternanza possa essere effettuata correttamente, è necessario che nel momento in cui si ferma l'esecuzione di un processo per farne eseguire un altro, si memorizzi il punto in cui era arrivato il processo fermato. Si deve cioè ricordare a quale istruzione del programma il processo era arrivato (ossia il valore del registro P.C. al momento dell'interruzione). In tal modo, quando il processo potrà riprendere ad eseguire, si potrà riprendere esattamente dal punto in cui era stato sospeso. Ricordarsi il valore del registro P.C. è necessario ma non sufficiente; in realtà ogni volta che un processo viene fermato e un altro processo va in esecuzione devono essere effettuate una serie di operazioni che prendono il nome di "switch di contesto" (cambio di contesto).

Switch di contesto

Si consideri un processo P1 in esecuzione: il processore conterrà, nei registri, informazioni concernenti l'esecuzione di P1 (ad esempio, il registro P.S. conterrà informazioni sullo stato di esecuzione, i registri generali conterranno risultati parziali dell'elaborazione). Nel momento in cui P1 perde l'uso del processore, tutte tali informazioni devono essere salvata in modo tale che, quando l'esecuzione potrà riprendere, sia possibile ripristinare tutte le informazioni nel processore esattamente come erano al momento della sospensione. Ciò è necessario per fare in modo che l'alternanza di esecuzione non abbia nessun effetto sulla corretta esecuzione dei processi. Lo switch di contesto consiste allora nella seguente sequenza di operazioni:

• salvataggio del valore di tutti i registri del processore nel descrittore del processo P1 che viene sospeso; le informazioni vengono salvata all'interno del descrittore del processo nella tabella dei processi;

• selezione del prossimo processo P2 "pronto" da mandare in esecuzione (scheduling, si veda il prossimo paragrafo);

• copia all'interno dei registri della CPU dei valori dei registri salvati nel descrittore del processo P2, in modo da ripristinare lo stato in cui P2 si trova quando era stato sospeso e poter quindi riprendere l'esecuzione. Se P2 non era mai stato eseguito in precedenza (è un processo "nuovo"), è sufficiente caricare nel registro P.C. l'indirizzo della sua prima istruzione.

In questo modo un processo, quando riparte, si trova esattamente nella situazione in cui si trovava quando era stato sospeso. Le due operazioni di salvataggio e ripristino dei valori vengono di solito effettuate mediante istruzioni macchina speciali, pertanto tutta l'operazione di switch di contesto viene effettuata in modo estremamente veloce. Si noti che il tempo per effettuare tali operazioni è comunque tempo non dedicato ai processi di utente e quindi in un certo senso "sprecato", per cui lo switch di contesto non può essere effettuato troppo frequentemente.

Politiche di gestione (scheduling del processore)

Visti gli aspetti di gestione, si tratta ora di discutere gli aspetti strategici (politici). In riferimento all'operazione di switch di contesto, in particolare, rimane da vedere quali strategie possono essere utilizzate nella selezione del prossimo processo da mandare in esecuzione: tali strategie prendono il nome di "politiche di scheduling del processore".

L'obiettivo di tali politiche è l'ottimizzazione di vari parametri, in particolare:

• massimizzare il grado di utilizzazione del processore (fare in modo che il processore rimanga inattivo il minor tempo possibile);

• massimizzare il numero di programmi che vengono eseguiti nell'unità di tempo ("throughput" del sistema), in modo che il processore svolga il massimo lavoro possibile;

• minimizzare il tempo di esecuzione dei processi (tempo di "turnaround" che intercorre tra l'istante in cui un processo viene creato q quello in cui termina) in modo che gli utenti debbano aspettare il meno possibile dalla richiesta di esecuzione di un programma alla sua terminazione;

• minimizzare il tempo di attesa dei processi; per i processi interattivi minimizzare il tempo di risposta di tali processi agli utenti.

In ogni caso si vogliono ottimizzare i valori "medi" di tali parametri. Spesso si vuole inoltre che le prestazioni siano "predicibili", ossia si è interessati ad avere prestazioni uniformi e che non succeda che uno stesso processo venga eseguito una volta in pochi secondi, e un'altra volta invece richieda ore. Si noti, inoltre, che spesso alcuni degli obiettivi menzionati in precedenza sono in antitesi tra loro. Ad esempio, aumentare il numero di programmi in esecuzione contemporaneamente tende a far aumentare il tempo di "turnaround" in quanto ogni processo va in esecuzione meno frequentemente. Si tratta quindi di mediare tra tali diversi obiettivi per raggiungere una ragionevole situazione di compromesso.

Parlando di politiche di scheduling si distingue di solito tra due aspetti: lo "scheduling a breve termine" e lo "scheduling a lungo termine". Il primo, su cui ci concentreremo nel seguito, riguarda la selezione del processo pronto da mandare in esecuzione. Il secondo riguarda il grado di multiprogrammazione del processore, ossia quanti processi devono essere mantenuti attivi contemporaneamente (su di esso ritorneremo più avanti).

Le politiche di scheduling a breve termine del processore che sono state proposte possono essere distinte in due famiglie:

• politiche non-preentive, pe cui il processo in esecuzione viene sostituito solo se si frema volontariamente (si ferma in attesa di una operazione di I/O); altrimenti la sua esecuzione continua;

• politiche preentive, per cui il sistema operativo può decidere di fermare un processo durante la sua esecuzione per mandare in esecuzione un altro processo.

Consideriamo il caso delle politiche non-preentive e il diagramma di stato dei processi. Un processo può abbandonare lo stato "in esecuzione" solo nel momento in cui va "in attesa" di un evento esterno. Ciò significa, in particolare, che il diagramma di transizione di stato è il seguente:

Tale schema risulta adatto al modello "batch" discusso in precedenza.

Nel caso delle politiche preentive è possibile che un processo "in esecuzione" venga rimesso nello stato di pronto e il processore ceduto ad un altro processo (tale operazione prende il nome di "preemption" ossia di pre-rilascio dell'unità centrale). Lo schema risulta adatto ai modelli "time-sharing" e "real-time" menzionati in precedenza. Il diagramma di transizione di stato dei processi è quello visto in precedenza, ossia:

All'interno di tali famiglie esistono diverse specifiche politiche di scheduling. Tra di esse le principali sono:

• FCFS (First Come, First Served) (o FIFO First In First Out). E' una politica non-preentive. I processi sono eseguiti nell'ordine in cui vengono sottomessi al sistema. La coda dei processi pronti viene quindi gestita selezionando dall'inizio della coda il processo da mandare in esecuzione e inserendo in fondo i processi che diventeranno "pronti". Il processo selezionato (primo della coda) viene mandato in esecuzione e vi rimane fino a quando non termina o va in attesa (in tal caso viene preso come prossimo il primo della coda dei "pronti"). Non appena un processo in attesa ritorna "pronto", esso viene messo al fondo della coda. In altri termini, si ha il seguente diagramma:

• Shortest Job First (SJF). E' una politica non-preentive. Lo schema è molto simile a quello della politica FCFS, a invece di selezionare il primo processo della coda viene selezionato il processo più breve (quello che richiede meno tempo per terminare o per fermarsi sulla prossima operazione di attesa). Questa politica permette di rendere ottimale il tempo medio di esecuzione. Il problema è che non si conosce il tempo necessario ad un processo per terminare; tale parametro può essere solo stimato, ad esempio su vecchie esecuzioni del programma o in base alle dimensioni (numero di istruzioni) del programma (la seconda misura è molto approssimativa data la presenza di istruzioni di salto che possono fare si che programmi con poche istruzioni richiedano molto tempo di esecuzione).

• Shortest Remaining Time First (SRTF). E' una politica preentive e una variante della politica SJF: il processo in esecuzione può essere fermato se diventa pronto un processo che richiede meno tempo per terminare (meno di quanto ne rimanga al processo in esecuzione).

• Selezione con priorità. L'idea è di associare una priorità ai processi e di selezionare, ogni volta, il processo nella coda dei "pronti" che ha la priorità più alta. Esistono due varianti di questa politica:

  • variante preentive: se, mentre il processo P1 è in esecuzione, un altro processo P2 prioritario rispetto a P1 diventa "pronto", allora viene effettuato lo switch di contesto;

  • variante non-preentive: il processo in esecuzione rimane in esecuzione fino a quando non va in attesa, anche se processi con priorità maggiore diventano "pronti".

• Round-Robin. E' una politica preentive basata sul concetto di "time-slice" ("quanto di tempo"). Quando un processo viene messo in esecuzione gli viene assegnato un quanto di tempo prefissato (di solito una decina di millisecondi) entro il quale dovrà abbandonare lo stato di esecuzione. Vi sono due possibilità:

  • Il processo termina o va "in attesa"; nel qual caso viene selezionato il prossimo processo pronto (il primo della coda dei pronti) e ad esso viene assegnato il processore per un quanto di tempo. Quando il processo "in attesa" ritornerà "pronto" verrà inserito al fondo della coda.

  • Scade il quanto di tempo; in tal caso il processo viene fermato e ritorna nella coda dei processi "pronti" (in ultima posizione) e il processore viene assegnato, per un quanto di tempo, al primo processo della coda dei "pronti".

In altri termini si ha il seguente diagramma:

In questo modo si ha una esecuzione alternata: ogni processo viene eseguito per un quanto di tempo fisso, poi lascia il posto ad un altro e torna al fondo della coda. Questo corrisponde al tipo di politica che si vuole nel caso di un sistema interattivo, in cui vi sono molti processi (magari di utenti diversi) e si vuole dare l'impressione che l'esecuzione avvenga in modo contemporaneo. Un aspetto critico della politica Round-Robin è la scelta del quanto di tempo. Se è troppo breve, si ha il vantaggio di uno scambio frequente e quindi di una "contemporaneità" di esecuzione più marcata, ma si ha lo svantaggio che si perde tempo in frequento switch di contesto. Se è troppo lungo, si rischia di cadere nella politica FCFS perché nessun processo viene mai fermato per la scadenza del quanto di tempo.

La politica Round-Robin (o sue varianti più sofisticate) è quella adottata nei sistemi operativi interattivi, in quanto in questi casi le altre politiche (e in particolare quella FCFS) non danno buoni risultati.

Un ultimo aspetto che è importante menzionare riguardo alle politiche di scheduling è la distinzione tra politiche "eque" ("fair") e politiche non eque ("unfair"). Una politica si dice equa se garantisce che ogni processo prima o poi verrà selezionato e andrà in esecuzione (le politiche FCSF e Round-Robin sono esempi di politiche eque). Nel caso di politiche non eque, invece, c'è il rischio che un processo sia costretto ad espettare in eterno e non arrivi mai il suo turno per l'esecuzione. Ad esempio, nella politica a priorità può accedere che il processo non venga mai selezionato, in quando ve ne è sempre uno con priorità maggiore (è ovvio che tali situazioni sono patologiche). Un tale rischio deve quindi essere calcolato nella scelta di una politica di gestione.

La discussione fatta fino ad ora riguarda le politiche di scheduling a breve termine. Per quanto riguarda lo scheduling a lungo termine, il problema è il seguente: nel momento in cui viene creato un nuovo processo, esso deve essere subito ammesso alla coda dei processi pronti? In molti casi (specie se si adotta la politica Round-Robin) non è opportuno avere troppi processi nella coda dei pronti altrimenti si rischia di allungare troppo il tempo medio di turnaround (si vedano i commenti all'inizio del paragrafo). E' opportuno, quindi, mantenere una ulteriore coda di processi in anticamera e man mano ammettere tali processi nella coda dei pronti quando altri processi terminano. Di solito ogni volta che un processo termina viene ammesso alla coda dei pronti quello che si trova in anticamera da più tempo per cui è sufficiente adottare una politica FCFS.

Nel caso in cui vi siano, nel sistema, sia processi compute-bound che processi I/O bound, si deve fare in modo che vi sia un bilanciamento tra i due tipi di processi. Infatti, solo mescolando tali processi si può gestire in modo ottimale l'intero sistema di elaborazione. Se si hanno solo processi compute-bound si potrà utilizzare al massimo il processore ma tutte le risorse di input/output rimarranno inattive mentre nel caso in cui si abbiano solo processi I/O bound si potranno mantenere impegnate risorse periferiche ma si avrà il rischio che il processore rimanga inattivo quando tutti i processi sono in attesa. La giusta mescolanza permette di eseguire i processi compute-bound nel momento in cui i processi I/O bound sono in attesa. In tale caso si può quindi adottare una politica che mescola la tecnica Round-Robin e le politiche con priorità:

• i processi I/O bound hanno priorità più alta rispetto a quelli compute bound, questi vengono selezionati dalla coda dei pronti solo se non vi è alcun processo I/O bound;

• i processi I/O bound vengono eseguiti secondo la politica round/robin;

• si adotta un meccanismo di preemption per cui appena un processo I/O bound diventa pronto e c'è in esecuzione un processo compute-bound viene fatto il cambio di contesto.

In questo modo viene data la precedenza ai processi interattivi per diminuire il tempo di risposta agli utenti e nei tempi non occupati dai processi interattivi vengono eseguiti quelli compute-bound (per i quali il tempo di risposta non è un fattore critico).

Coordinamento, sincronizzazione e mutua esclusione

Nel caso in cui vi siano più processi in esecuzione "contemporaneamente" possono nascere situazioni di conflitto e competizione tra tali processi. In tali casi, invece, può capitare che i processi debbano scambiarsi informazioni (ad esempio, dati). Particolarmente critici sono i problemi di conflitto e competizione che devono essere risolti dal sistema operativo. Analizziamo un tipico caso. Quasi tutte le risorse all'interno di un sistema di calcolo (sia risorse hardware che software) sono di tipo "seriale" ossia possono essere utilizzate da un processo alla volta. Ad esempio, una stampante può essere usata in ogni istante da un solo processo. Molto spesso poi vi sono anche insiemi di dati che possono essere usati da un solo processo alla volta; ad esempio, nel caso di una banca non si può avere che due processi operino nello stesso momento sullo stesso conto corrente, altrimenti si potrebbero creare situazioni di inconsistenza. Tutte tali risorse sono tuttavia condivise tra i vari processi: si ha quindi competizione per il loro uso e si deve quindi realizzare mutua esclusione: quando un processo richiede l'uso della stampante e la stampante è occupata da un altro processo allora si deve fare aspettare il nuovo richiedente fino a che la stampante non sia libera.

Tali problemi vengono risolti facendo in modo che sia il sistema operativo a gestire ogni risorsa (come vedremo più avanti) per cui ogni richiesta deve essere fatta al sistema e questo deve risolvere eventuali situazioni di conflitto. In particolare, per risolvere il problema della mutua esclusione, i sistemi operativi usano una tecnica particolare basata sull'uso di una particolare struttura dati, il "semaforo", il cui modo di funzionamento è molto simile a quello dei semafori ferroviari di uso comune. L'idea è che ogni risorsa seriale (ad esempio una stampante o il conto corrente cui più cassieri possono accedere) viene associato a un semaforo che è un bit che può assumere due valori: "verde" (ad indicare che la risorsa è libera) e "rosso" (ad indicare che la risorsa è occupata (nello stesso modo in cui un semaforo ferroviario indica che un binario è libero o occupato). Ogni richiesta di uso della risorsa viene quindi gestita (a livello molto astratto) nel modo seguente:

• la risorsa è usabile solo con semaforo "verde";

• il processo che vuole usare la risorsa, deve prima verificare il semaforo; se è rosso aspetta che torni "verde" e nel frattempo lascia il processore ad altri (va in stato "in attesa" e viene quindi effettuato uno switch di contesto con un processo selezionato tra quelli "pronti");

• il processo che stava occupando la risorsa ed ha finito di usarla, rimette il semaforo a "verde" e avverte chi sta aspettando della possibilità di ripartire (ossia un processo che era "in attesa" viene rimesso a "pronto").

In questo modo i conflitti possono essere evitati dal sistema operativo. In modo simile è possibile realizzare meccanismi di sincronizzazione tra processi e meccanismi di scambio di dati (comunicazione). Tali aspetti esulano dalla visione astratta della nostra trattazione.

Esecuzione di processi di sistema

Si è osservato nella sezione precedente che parte del sistema operativo viene sempre mantenuta in memoria principale. In particolare tale parte è costituita da un insieme di programmi che sono permanentemente attivi (processi di sistema).

I processi di sistema vengono trattati in modo speciale dal sistema operativo nel senso che non rientrano nelle tecniche discusse in precedenza. In particolare, tali processi vengono mandati in esecuzione non appena il loro intervento viene richiesto e quindi passano davanti a tutti i processi di utente.