Sistemi operativi - Teoria

Lezione 4: Processo

Un processo viene definito come un programma in esecuzione. Durante la sua esecuzione, il processo passa attraverso diversi stadi:

• New: stato iniziale (il processo viene creato)
• Ready: il processo è pronto per essere eseguito
• Running: il processo e le sue istruzioni sono in esecuzione
• Waiting: il processo è in attesa di un dato evento
• Terminated: stato finale (il processo ha terminato la sua esecuzione)

Stadi del processo

New: È lo stadio iniziale che avviene appena il processo viene inizializzato. Dal new si può passare solo nello stato di ready tramite un’operazione chiamata ‘admitted’. Nel passaggio da new a ready, il programma è pronto perché gli vengono assegnate le risorse.

Ready: È lo stadio secondario dal quale bisogna necessariamente passare. In questo stato, il processo aspetta che gli venga assegnata la CPU quando non ci sono altri processi in esecuzione per poi passare in fase di running (operazione ‘scheduler dispatch’).

Running: si passa ora alla fase di running, dove ci sono tre possibilità:

• Nella versione più semplice, dopo aver completato il suo codice tramite il comando exit, il processo va in terminated.
• Un'altra possibilità è l’uscita verso waiting quando ha bisogno di un dispositivo di output o che avvenga un evento. Mentre il processo è in waiting, è possibile che in running entri un altro processo.
• Ultima uscita è il ritorno allo stato di ready tramite un interrupt. Dopo aver gestito l’interrupt può intervenire un altro processo.

Gestione degli interrupt

Quando si gestisce un interrupt, gli altri vengono sospesi in attesa della risoluzione dell’interrupt in corso, tranne alcuni interrupt particolari che devono essere risolti immediatamente. Se un processo viene interrotto bruscamente, passa comunque dallo stato di running, non viene interrotta dallo stato di ready.

Process Control Block

Il Process Control Block è una struttura dati memorizzata in memoria centrale e gestita dal sistema operativo. Contiene le informazioni su un processo, tra cui:

• Stato
• Program counter (prossima istruzione da eseguire)
• Registri della CPU
• Scheduling CPU
• Informazioni memory-management
• Informazioni accounting
• Stato dell’I/O
• ID del processo
• ID dell’utente

Commutazione della CPU tra due processi (o Context Switch)

In Linux, il PCB si chiama task_struct. La task_struct è organizzata come una lista bilinkata, nel senso che c’è un link dalla task_struct precedente a quella successiva e viceversa, e c’è un puntatore sulla task_struct corrente. Questa organizzazione è molto efficiente poiché Linux, quando ha esigenza di cambiare PCB, deve solo cambiare il puntatore.

Code di scheduling

Scheduling della CPU significa decidere l’ordine con il quale i processi vengono assegnati alla CPU, ovvero l’ordine di risoluzione dei processi:

• Coda dei processi: coda che contiene i processi presenti nel sistema
• Coda ready queue: insieme dei processi in memoria centrale pronti per essere eseguiti
• Coda del dispositivo: per ogni dispositivo di I/O c’è una coda

I processi passano da una coda all’altra quando cambiano stato.

Tipi di scheduler

In un sistema operativo esistono diversi tipi di scheduler:

• Scheduler a lungo termine: detto anche job scheduler, è un processo del sistema operativo che seleziona i processi che vanno inseriti nello ready queue.
• Sistemi a breve termine: detto anche CPU scheduler, seleziona tra i processi pronti quelli che devono essere eseguiti sulla base di un algoritmo. Se una CPU è un processo per volta.
• Sistemi a medio termine: in alcuni time-sharing esiste uno scheduler a medio termine che gestisce i processi pronti in memoria centrale (swapper). A volte rimuove i processi dalla memoria (swap-out) per riportarli in memoria (swap-in) quando sarà possibile.

Questo migliora l’utilizzo della memoria in caso di una alta richiesta di esecuzione di processi. I processi sottoposti a swap-out sono processi che non sono in esecuzione. Lo scheduler a breve termine deve essere molto veloce poiché è chiamato molto spesso, al contrario del processo a lungo termine che è chiamato meno spesso e può essere quindi più lento.

Classificazione dei processi

I processi possono essere classificati come:

• Processi I/O-bound: basso uso CPU e alto dell’I/O (molto in waiting e poco in running)
• Processi CPU-bound: elevato uso CPU e basso dell’I/O (molto running poco waiting)

Esempi:

• Browser (I/O-bound)
• Programma che risolve equazioni differenziali (CPU-bound)

Context Switch

La gestione del passaggio da un processo ad un altro da parte della CPU. Il context switch dipende dall’hardware ma è gestito dal sistema operativo.

Operazioni su processi

Creazione: Un processo, per arrivare nello stato di new, deve prima essere creato. Il sistema operativo crea processi utente come processi figli. Un processo figlio è un processo creato da un altro processo.

Condivisione di risorse

• Processi padri e figli condividono tutte le risorse
• Un processo figlio condivide una parte delle risorse del padre
• Processi padri e figli non condividono risorse

Queste condizioni possono essere scelte durante la creazione del programma.

Approccio di esecuzione

• Processi padri e figli eseguono concorrentemente
• Il padre rimane in attesa della terminazione dei figli

Durante la creazione:

• Il processo figlio viene duplicato dal processo padre
• Il processo figlio ha un proprio codice

Ogni sistema operativo mette a disposizione delle system call per creazione ed esecuzione dei processi, la cui sintassi cambia a seconda del sistema operativo in uso.

Esempi in UNIX

• fork: system call che crea un nuovo processo
• exec (nuovo programma): system call usata dopo una fork per sostituire allo spazio di memoria di un processo un nuovo programma

Terminazione di un processo

Un processo esegue il suo codice e poi chiede al sistema operativo di terminare con una system call chiamata exit(). L’istruzione exit() possiamo scriverla nel codice, altrimenti il compilatore inserisce un exit() ad ogni punto di terminazione.

Un processo padre può interrompere i processi figli con abort() per vari motivi:

• Il processo figlio non è più utile
• Il figlio ha usato risorse in eccesso
• Il processo padre termina

Processi indipendenti e cooperanti

I processi indipendenti non interagiscono con altri processi durante la loro esecuzione. I processi cooperanti influenzano o possono essere influenzati da altri processi; il loro comportamento dipende dall’ambiente esterno.

Vantaggi della cooperazione:

• Condivisione dell’informazione
• Velocità di esecuzione
• Modularità
• Distribuzione
• Convenienza

Meccanismi di interazione tra processi cooperanti

• Scambio esplicito di dati
• Sincronizzazione su un particolare evento
• Condivisione di memoria e quindi di informazione

I sistemi operativi mettono a disposizione meccanismi per realizzare queste cose, come:

• Send and receive
• Semafori
• Monitor
• Chiamata di procedura remota

Anche alcuni linguaggi di programmazione offrono meccanismi di cooperazione, come Java.

Thread

Il thread è un processo leggero, una versione del processo realizzata negli ultimi 20 anni. Può essere considerata come un’ottimizzazione del processo. Un thread è un processo che può condividere con altri thread codice, informazioni e risorse. Un insieme di thread prende il nome di task. Quindi un thread è un’unità di esecuzione che ha il proprio program counter, il proprio stack e i propri registri. Un processo equivale ad un task che è formato da un unico thread.

Thread utente

Praticamente tutti i sistemi operativi sono basati sui thread, ed anche i linguaggi mettono a disposizione i thread. Quando parliamo di thread messi a disposizione dai linguaggi, si chiamano user thread. I kernel thread sono invece implementati dal sistema operativo ed eseguiti da esso. Nel linguaggio di programmazione, quando implementiamo i thread, questi si appoggiano sui kernel thread. Queste associazioni si possono fare tramite vari modi e dipende dal linguaggio di programmazione e il sistema operativo. I kernel thread sono implementati e gestiti dal kernel. La gestione dei thread del kernel è più flessibile.

Alcuni Sistemi Operativi implementano sia thread di sistema che thread utente. Esistono delle system call per eseguire i thread.

Associazioni tra user thread e kernel thread

• Molti a uno: più user thread vengono mappati su un singolo kernel thread, usato nei sistemi che non supportano kernel thread.
• Uno a uno: per ogni user thread viene eseguito un kernel thread.
• Molti a molti: tanti user thread vengono associati a molti kernel thread. Permette al sistema operativo di creare un numero sufficiente di kernel thread e non quanti ne vuole l’utente.

Lezione 5: Scheduling della CPU

Lo scheduling della CPU è uno dei compiti principali del kernel, vuol dire decidere l’ordine di esecuzione dei processi. Il compito di eseguire gli algoritmi di scheduling è dello scheduler a breve termine. L’obiettivo dello scheduling è la massimizzazione della CPU, quindi completare più velocemente le esecuzioni dei programmi tenendo la CPU sempre occupata.

Ciclo CPU Burst – I/O Burst

Uno dei concetti fondamentali è il ciclo CPU Burst – I/O Burst, che scandisce il fatto che ogni processo tende ad utilizzare in maniera alternata la CPU e gli strumenti di input/output.

• CPU burst: Sequenza di operazioni comprese tra due operazioni di I/O.
• I/O burst: Operazioni di I/O eseguite tra due CPU burst.

Lo scheduling della CPU si occupa di interrompere questi due processi quando non servono. La frequenza di CPU burst brevi è molto alta, mentre la frequenza dei CPU burst lunghi è molto bassa.

Dato che l’esistenza di questa evidenza sperimentale, la CPU viene assegnata ai processi per circa 8 millisecondi. La maggior parte dei processi ha durata inferiore e, se ne capita qualcuno con durata maggiore, gli viene comunque dedicata dallo scheduler una durata di 8 millisecondi. Poi viene interrotto e rimesso in ready in attesa di tornare in running. Successivamente, quando il processo torna in prima posizione nella coda di ready, sarà rimesso in running. In questi casi c’è una minima perdita di tempo ma si è constatato che, dato che è abbastanza raro che un processo abbia tempo di esecuzione maggiore di 8 millisecondi, è conveniente adottare questa convenzione.

Interventi dello scheduler

Lo scheduler a breve termine seleziona uno tra i processi in memoria pronti per essere eseguiti (ready queue) e lo assegna alla CPU mettendo il processo in esecuzione. Lo scheduler interviene in determinati casi:

1. Un processo passa dallo stato di running allo stato di waiting: qui interviene perché in questo caso la CPU si libera, quindi lo scheduler va a scegliere un nuovo processo che imposterà in stato di running molto velocemente.
2. Quando un processo termina: è abbastanza chiaro il perché lo scheduler deve intervenire nella scelta del nuovo processo da impostare nello stato di running.
3. Lo scheduler interviene quando un processo passa dallo stato di running allo stato di ready: il processo era in running e per un interrupt torna in ready, lo scheduler della CPU guarda tra i processi di ready.
4. Un processo è passato da waiting a ready (caso particolare): si è verificato l’evento che soddisfa la waiting, questo avviene solo se il processo in argomento è molto importante. Quindi, se c’è un processo in funzione (quindi in running), viene interrotto dallo scheduling.

I punti 3 e 4 sono casi di scheduling preemptive (con prelazione), nei punti 1 e 2 lo scheduling è non preemptive (senza prelazione).

Dispatcher

Il modulo dispatcher svolge il lavoro di passare il controllo ai processi selezionati dallo scheduler della CPU per la loro esecuzione. Questo componente fa da ausilio allo scheduler per la gestione della CPU.

Più in dettaglio, lo scheduler decide il processo da eseguire, però l’operazione di context switch (ovvero lo scambio effettivo tra i due processi) tocca al dispatcher.

Latenza di dispatch: come si evince dall’espressione, la latenza del dispatch è il tempo impiegato dal dispatcher per fermare un processo e far eseguire il successivo. Ovviamente il dispatcher deve essere molto veloce.

Critèri di scheduling

Nella scelta di una strategia di scheduling occorre tenere conto delle diverse caratteristiche dei programmi:

• Utilizzo della CPU: avere la CPU il più attiva possibile
• Throughput: numero di processi completati nell’unità di tempo
• Tempo di turnaround: tempo totale per eseguire un processo, ovviamente un algoritmo di scheduling efficiente ci consente di minimizzare il turnaround
• Tempo di waiting: tempo totale di attesa sulla ready queue, quindi è la misura di tempo ‘perso’ dai vari processi (non riguarda lo stato di waiting, ma riguarda il tempo ‘perso’ nello stato di ready, nella coda dei pronti)
• Tempo di risposta: tempo da quando viene inviata una richiesta fino a quando si produce una prima risposta (non considerando il tempo di output)

Molto importante nei programmi che hanno molta interazione con l’utente.

Critèri di ottimizzazione

• Massimizzare l’utilizzo della CPU
• Massimizzare il throughput
• Minimizzare il tempo di turnaround
• Minimizzare il tempo di waiting
• Minimizzare il tempo di risposta
• Generalmente si tende ad ottimizzare i valori medi
• Nei sistemi time-sharing è più importante minimizzare la varianza del tempo di risposta

Scheduling First-Come, First-Served (FCFS)

Questo algoritmo di scheduling si basa sul fatto che il primo processo ‘arrivato’ sarà il primo ad essere eseguito. Supponendo che arrivino tre processi p1, p2, p3, con tempi di esecuzione rispettivamente 24, 3, 3. Chiaramente i tempi di attesa saranno rispettivamente: [0 per p1], [24 per p2], [27 per p3]. Questo ci dà come tempo di attesa medio il valore di 17: tempo di waiting medio = (0 + 24 + 27) / 3 = 17.

Ovviamente, se l’ordine di arrivo fosse stato diverso, anche il tempo di attesa medio sarebbe diverso. Per esempio, consideriamo la possibilità che p1 arrivi per ultimo, il tempo di attesa medio è 3, sicuramente meglio di prima. Questo è il problema dell’algoritmo appena trattato, chiamato effetto convoglio, cioè i processi non hanno priorità quindi se un processo lungo ‘arriva prima’ di un altro allora verrà eseguito prima a discapito dell’efficienza. Nonostante questo, in alcuni casi è ancora utilizzato.

Scheduling Shortest-Job-First (SJF)

Associa ad ogni processo la lunghezza del prossimo CPU burst. Usa questi tempi per schedulare il processo con la lunghezza minima. I processi vengono ordinati nella ready queue in base al loro prossimo CPU burst in ordine crescente (il primo processo ha il minimo CPU).

Due schemi:

• Nonpreemptive: il processo assegnato alla CPU (quindi in running) non può essere sospeso prima di completare il suo CPU burst.
• Preemptive: se arriva un nuovo processo nella ready queue con un CPU burst più breve del tempo rimanente al processo in running, viene servito. Questo schema è chiamato Shortest-Remaining-Time-First (SRTF).

SJF è ottimale rispetto al tempo di attesa (waiting time), ovvero offre il minimo tempo medio di attesa per un insieme di processi. L’algoritmo SJF viene usato nei sistemi operativi, a volte con delle migliorie, specialmente nella forma preemptive. Questo algoritmo ha un problema chiamato starvation (ovvero che il processo con CPU burst più lungo a volte non riceverà mai la CPU, e si dice ‘affamato di CPU’). Il problema viene risolto dando una priorità proporzionale al tempo, processo chiamato aging (invecchiamento). Ad un certo punto il processo verrà eseguito indipendentemente dal suo tempo di esecuzione.

Questo algoritmo è basato sul conoscere la lunghezza del prossimo CPU burst, ma il prossimo CPU burst non si conosce, si può solo stimare. La stima si effettua usando la lunghezza dei precedenti CPU burst e usando una media esponenziale:

Θ(n+1) = (alfa) * Tn + [1 – (alfa)] * Θ(n)

• Tn = lunghezza dell’n-esimo CPU burst
• Θ(n+1) = valore predetto del prossimo CPU burst
• (alfa) = {0 <= (alfa) <= 1}

Il processo che viene selezionato per l’esecuzione verrà eseguito per il tempo effettivo del suo CPU burst.

Lezione 6: Scheduling con priorità

Una priorità (numero intero) è assegnata ad ogni processo. La CPU è assegnata al processo con più alta priorità (in alcuni SO: il numero più piccolo ha la più alta priorità). Esistono alcuni sistemi che consentono di cambiare la priorità ai vari processi. Ci è però consentito di diminuire la priorità tranne per l’amministratore di sistema che può gestire la priorità a suo piacimento.

Versioni di scheduling con priorità

• Preemptive: La versione con prelazione in un algoritmo con priorità, nella pratica succede che se arriva nella coda di ready un processo che ha priorità più alta di ogni altro processo in ready e del processo in running, questo nuovo processo prende il posto del processo in esecuzione.