Appunti di Fabio Missagia parte 2.pdf

4. Gestione dei processi e threads Un processo è definito come un'istanza di programma in esecuzione. Un processo viene eseguito in modo sequenziale (nel senso una esecuzione alla volta, ma non per forza in ordine), ma in un sistema multiprogrammato i processi evolvono in modo concorrente. Da cosa...

4. Gestione dei processi e threads Un processo è definito come un'istanza di programma in esecuzione. Un processo viene eseguito in modo sequenziale (nel senso una esecuzione alla volta, ma non per forza in ordine), ma in un sistema multiprogrammato i processi evolvono in modo concorrente. Da cosa è formato un processo? Un processo consiste di: Istruzioni (sezione Codice o Testo): è la parte statica del codice Dati (sezione Dati): è la parte di variabili globali Stack: le chiamate a procedura e parametri le variabili locali Heap Memoria allocata dinamicamente Attributi (id, stato, controllo) Attributi (Process Control Block) Vediamo ora in maggiore dettaglio la parte degli attributi. All’interno del S.O. ogni processo è rappresentato dal Process Control Block (PCB), che rappresenta appunto la sezione "Attributi" nell'immagine sopra. Il PCB è una struttura dati con una tabella in memoria principale che conserva le seguenti informazioni: Stato: in esecuzione, in attesa, etc. Program Counter (PC): puntatore alla prossima istruzione da eseguire (in alcuni testi e chiamato Instruction Pointer) Valori dei registri: vengono conservati i valori dei registri CPU utilizzati dal processo Informazioni sulla memoria (es: registri limite, tabella pagine) Informazioni sullo stato dell’I/O (es: richieste pendenti, file) Informazioni sull’utilizzo del sistema (CPU) informazioni di scheduling (es: priorità) Stati di un processo Durante la sua esecuzione, un processo evolve attraverso diversi stati: Nuovo: il processo è appena stato avviato, deve essere ancora caricato in memoria dal long-term scheduler Pronto: il processo è in memoria, sta aspettando che lo short-term scheduler gli lasci l'utilizzo della CPU In Esecuzione: sta usando la CPU (ci può essere un solo processo in running alla volta) In Attesa: il processo è in attesa di un evento, o di soddisfare una richiesta di utilizzo di un dispositivo I/O non disponibile al momento (la separazione di waiting dagli altri stati è un passo fondamentale per migliorare l'utilizzo della CPU, infatti il processo torna in memoria se deve aspettare un evento) Terminated: il processo è terminato Scheduling Lo scheduler si occupa di controllare e selezionare il processo da eseguire nella CPU. Ce ne sono di 2 tipi: Long-term Scheduler: si occupa del caricamento dei processi da disco alla memoria principale (ready queue). Viene invocato con intervalli nell'ordine dei secondi/minuti. Controlla il grado di multiprogrammazione, ovvero il numero totale di processi nello stato ready. Short-term Scheduler: più veloce ed invocato con frequenze molto maggiori del precedente, si occupa del dispatching, ovvero il passaggio da Ready a Running. Short-term scheduler che eseguono cambi di  contesto troppo spesso rischiano di causare un grande overhead al sistema, degradando notevolmente le prestazioni, mentre effettuare cambi di contesto troppo poco spesso porta a tempi di risposta ed attesa eccessivamente lunghi. I processi vengono inseriti in delle code: coda dei processi pronti (ready queue): coda dei processi pronti per l'esecuzione coda di un dispositivo (waiting queue): coda dei processi in attesa che il dispositivo si liberi I processi restano nella coda dei processi pronti fino a quando non ne viene selezionato uno per essere eseguito (dispatched). I processi possono essere descritti come I/O bound: maggior parte del loro tempo eseguono operazioni di I/O, molti burst di CPU corti CPU bound: maggior parte del loro tempo eseguono computazioni, pochi burst di CPU lunghi Come fa un processo a sapere a quale tipo appartiene? Bella domanda. L'operazione più critica è quella fatta dal dispatcher, ovvero assegna la CPU ad un certo processo e fa passare il processo da ready a running. Come avviene nel dettaglio? 1. Cambio di contesto: viene salvato il PCB del processo che esce e viene caricato il PCB (precedentemente registrato) del processo che entra 2. Passaggio alla modalità utente (all’inizio della fase di dispatch il sistema si trova in modalità kernel) 3. Salto all'istruzione da eseguire del processo appena arrivato nella CPU Il tempo necessario al cambio di contesto è puro sovraccarico Il sistema non compie alcun lavoro utile durante la commutazione La durata del cambio di contesto dipende molto dall’architettura Creazione di un processo Per quanto riguarda la creazione dei processi, la maggior parte dei SO permette a processi di crearne di nuovi tramite apposite chiamate di sistema. Si parla in questo caso di processi padre e processi figlio; il figlio può ottenere le risorse dal padre o direttamente dall'SO. A seconda delle politiche del SO si hanno 2 tipi di esecuzione: sincrona: il padre può aspettare che terminino i figli asincrona: continuare la propria esecuzione parallelamente ai figli (esecuzione concorrente) Come si crea un processo in UNIX? System call fork(): Crea un figlio che è un duplicato esatto del padre il figlio deve essere più piccolo del padre per evitare di avere 2 processi completamente uguali il PCB del figlio è diverso System call exec(): Carica sul figlio un programma diverso da quello del padre System call wait(): Per esecuzione sincrona tra padre e figlio Come si termina un processo? Un processo può terminare in diversi modi: Il processo finisce la sua esecuzione  Il processo viene terminato forzatamente dal padre Per eccesso nell’uso delle risorse Il compito richiesto al figlio non è più necessario Il padre termina (se il padre muore, muoiono anche i figli, i figli non possono rimanere senza padre) Il processo viene terminato forzatamente dal S.O. Quando l'utente chiude l'applicazione A causa di errori (aritmetici, di protezione, di memoria, …) Threads Qual è la differenza tra processo e thread? Un thread è definito come l'unità minima di utilizzo della CPU, un processo come l'unità minima di possesso delle risorse. All'interno di un processo, i thread condividono codice, dati e risorse, ma ognuno può avere stati e registri diversi. La suddivisione di un processo in più thread permette che parte di essi siano in esecuzione mentre altri sono bloccati per l'attesa di un evento di I/O (questo è solo uno dei vantaggi). Dato che per definizione condividono codice e dati, la comunicazione e la condivisione di risorse tra thread è più semplice rispetto a quella tra processi; anche la creazione di thread è più veloce della creazione di processi. Per riassumere, ad un processo sono associati: Spazio di indirizzamento Risorse del sistema Invece, ad una singola thread sono associati: Stato di esecuzione Contatore di programma (program counter) Insieme di registri (della CPU) Stack Inoltre le thread condividono: Spazio di indirizzamento Risorse e stato del processo In un S.O. classico abbiamo che 1 processo = 1 thread , ma grazie al concetto di multithreading abbiamo la possibilità di supportare più thread per un singolo processo. Di conseguenza, abbiamo una separazione tra “flusso” di esecuzione (thread) e spazio di indirizzamento Processo con thread singola: Un flusso associato ad uno spazio di indirizzamento Processo con thread multiple: Più flussi associati ad un singolo spazio di indirizzamento Vantaggi dei threads Come accennato in precedenza, l'uso di threads presenta vari vantaggi: Riduzione tempo di risposta, più operazioni allo stesso tempo Mentre una thread è bloccata (I/O o elaborazione lunga), un’altra thread può continuare a interagire con l’utente Condivisione delle risorse Le thread di uno stesso processo condividono la memoria Più veloci dei processi Creazione/terminazione thread e context switch tra thread più veloce rispetto ai processi  Scalabilità Grazie al multithreading aumenta il parallelismo, possiamo avere un thread in esecuzione su ogni processore Stati di un thread Gli stati di un thread sono gli stessi di un normale processo (pronto, in esecuzione, in attesa), ma la loro correlazione dipende dall'implementazione. Ad esempio un thread in wait potrebbe bloccare o meno altri thread dello stesso processo o anche l'intero processo. Implementazione dei threads Esistono essenzialmente due modi per implementare i thread in un SO, poi un terzo che è la combinazione dei primi due, di seguito riportati. User-Level Thread Implementati tramite apposite librerie (tipo pthread.h). Vantaggi Tutti i thread sono gestiti da un unico processo nel kernel, il che rende il sistema molto economico. Non è necessario passare in modalità kernel per utilizzare le thread, quindi più efficienza Portabilità, girano su qualunque S.O. senza bisogno di modificare il kernel Meccanismo di scheduling variabile da applicazione ad applicazione Svantaggi Il blocco di una thread blocca l’intero processo (anche se è superabile con accorgimenti specifici) Niente parallellismo, viene eseguito un solo thread alla volta per processo (praticamente il kernel ignora l’esistenza delle altre thread) Kernel-Level Thread Ad ogni thread a livello utente corrisponde un singolo thread a livello kernel. Vari esempi sono Win32, Linux, Native thread di Java. Vantaggi Parallellismo, più thread dello stesso processo in esecuzione contemporanea su CPU diverse Il blocco di un thread non blocca il processo Svantaggi Scarsa efficienza, per ogni thread a livello kernel c'è un thread a livello utente Approccio misto Ad N thread a livello utente corrispondono M ≤ N thread a kernel level. Si ha un buon parallelismo e risulta meno costoso del full kernel-level. Un esempio è Solaris. Libreria POSIX (pthread.h) Per usare i pthreads in un programma C, è necessario includere la libreria. Per compilare un programma che usa i pthreads occorre linkare la libreria libpthread, usando l’opzione -lpthread: $> gcc prog.c -o prog -lpthread Creazione di un thread Un thread ha vari attributi, che possono essere cambiati, ad esempio: la sua priorità (che influenza la frequenza con cui verrà schedulato) la dimensione del suo stack (che specifica la quantità massima di argomenti che gli si possono passare, la profondità delle chiamate ricorsive, e così via) Gli attributi di un thread sono contenuti in un oggetto di tipo pthread_attr_t. La syscall per inizializzare un thread è la seguente: int pthread_attr_init(pthread_attr_t *attr); Questa funzione inizializza con i valori di default un “contenitore di attributi” *attr, che potrà poi essere passato alla system call che crea un nuovo thread. Un nuovo thread viene creato con la syscall intera pthread_create che accetta quattro argomenti: una varibile di tipo pthread_t, che conterrà l’identificativo del thread che viene creato un oggetto attr, che conterrà gli attributi da dare al thread creato. Se si vuole creare un thread con attributi di default, si può anche semplicemente usare NULL un puntatore alla routine che contiene il codice che dovrà essere eseguito dal thread un puntatore all’eventuale argomento che si vuole passare alla routine stessa Terminazione di un thread Un thread termina quanto finisce il codice della routine specificata all’atto della creazione del thread stesso, oppure quando, nel codice della routine, si chiama la syscall di terminazione: void pthread_exit(void *value_ptr); Quando termina, il thread restituisce il “valore di return” specificato nella routine, oppure, se chiama la pthread_exit, il valore passato a questa syscall come argomento. Sincronizzazione tra threads Un thread può sospendersi, in attesa della terminazione di un altro thread chiamando la syscall: int pthread_join(pthread_t thread, void **value_ptr); pthread_t thread è l'identificativo del thread di cui si attende la terminazione. Naturalmente deve essere un thread appartenente allo stesso processo. void **value_ptr è il valore restituito dal thread che termina. Sono comunque disponibili diversi strumenti per sincronizzare fra loro i thread di un processo, fra questi anche i semafori. In realtà i semafori non fanno parte dell’ultima versione dello standard POSIX, ma della precedente. Tuttavia sono normalmente disponibili in tutte le versioni correnti dei pthread. I pthread mettono anche a disposizione meccanismi di sincronizzazione strutturati, quali le variabili condizionali. Esempio #include #include #include void *tbody(void *arg) {  int j; printf(" ciao sono un thread, mi hanno appena creato\n"); *(int *)arg = 10; sleep(2); pthread_exit((int *)50); } int main(int argc, char **argv) { int i; pthread_t mythread; void *result; printf("sono il primo thread, ora ne creo un altro \n"); pthread_create(&mythread, NULL, tbody, (void *) &i); printf("ora aspetto la terminazione del thread che ho creato \n"); pthread_join(mythread, &result); printf("Il thread creato ha assegnato %d ad i\n",i); printf("Il thread ha restituito %d \n", result); } Il thread main ha generato un secondo thread tbody. Poi main si è messo in attesa della terminazione del thread creato (con pthread_join), ed è terminato lui stesso. È importante notare che i due thread condividono lo stesso spazio di indirizzamento, e quindi vedono le stesse variabili: se uno dei due modifica una variabile, la modifica è vista anche dall’altro thread. Nel codice di t1, il main passa al thread tbody il puntatore alla variabile i dichiarata nel main. il thread tbody modifica la variabile, e questa modifica è vista da main. Nel caso dei processi tradizionali, una cosa simile è ottenibile solo usando esplicitamente un segmento di memoria condivisa. Ovviamente i thread di un processo possono condividere variabili in maniera ancora più semplice, usando variabili globali. Tuttavia un thread può anche avere variabili proprie, viste solo dal thread stesso usando la classe di variabili thread_specific_data. SO come processo Sappiamo che il sistema operativo è un programma a tutti gli effetti, quindi può essere considerato esso stesso un processo? Questo varia a seconda dell'implementazione, in cui le parti del SO possono o meno essere considerate dei processi. Vediamo dunque le alternative disponibili: Kernel Separato Il kernel esegue al di fuori dei processi utente, in uno spazio "riservato" in memoria ed in esecuzione privilegiata. Essendo appunto "separato" le cose vanno implementate due volte e in maniera diversa. Inoltre il S.O. prende il controllo dell'intero sistema. Il concetto di processo è quindi applicabile solo ai processi utente. Questa modalità è tipica dei primi SO. Kernel nei processi utente In questa implementazione i servizi del SO sono procedure chiamabili da programmi utente, accessibili però solo in modalità protetta (kernel mode). Ogni processo ha un kernel stack per gestire le chiamate a funzione e una porzione di codice/dati condiviso tra tutti i processi. Ciò velocizza le chiamate di sistema, visto che in caso di interrupt o trap durante l’esecuzione di un processo utente è sufficiente solo un cambio di modalità (mode switch). Ossia, il sistema passa da user mode a kernel mode e viene eseguita la parte di codice relativa al S.O. senza context switch (da processo utente a processo di SO). Kernel come processo A differenza della precedente implementazione, qui solo una parte del kernel (solitamente lo scheduler) esegue separatamente, al di fuori di tutti i processi. Per il resto, ogni parte del SO è un processo separato, eseguito in modalità protetta (kernel mode). Questo è molto vantaggioso nei sistemi multicore, che di solito riservano dei processori ad esclusivo utilizzo del SO. 5. Relazioni tra processi Nonostante esistano processi indipendenti (ovvero che non comunicano con altri processi, nè condividono dati), la maggior parte dei processi risulta cooperante, ovvero scambia in qualche modo informazioni con altri processi durante l'esecuzione. Ma come avviene lo scambio di informazioni? I processi possono comunicare tra loro con 2 tecniche, garantendo così l'IPC (Inter-Process Communication): Memoria condivisa: viene definita un'area di memoria in cui entrambi i processi posso leggere e scrivere dati. Generamente più veloce, in quanto non richiede l'intervento del kernel, tuttavia è necessario un meccanismo di sincronizzazione per gli accessi per evitare conflitti ed inconsistenze Scambio di messaggi: il kernel crea una coda di messaggi alla quale i processi accedono, che quindi comunicano senza condividere variabili. Sebbene richieda l'intervento del kernel, oggi sta diventando popolare e conveniente grazie alla tecnologia multicore. Può essere facilmente esteso ai sistemi distribuiti. Generalmente i SO implementano entrambe queste tecniche, per poter poi usare l'una o l'altra a seconda delle scelte implementative. Vediamole ora entrambe nel dettaglio. Scambio di messaggi (Message Passing) Come detto in precedenza, è un meccanismo utilizzato dai processi per comunicare e sincronizzare le loro azioni, utilizzando lo scambio di messaggi (i processi comunicano tra loro senza condividere variabili). Sono fornite due operazioni: send(message): la lunghezza del messaggio può essere fissa o variabile receive(message) Quindi se i due processi P e Q desiderano comunicare, devono: Stabilire un canale di comunicazione Scambiarsi messaggi via send/receive In ogni caso si ha la necessità di stabilire un link logico tra i processi che può avvenire mediante comunicazione diretta o indiretta. Comunicazione diretta Se ogni processo invia direttamente il messaggio all'altro. La comunicazione può essere simmetrica se sia il mittente che il destinatario conoscono l'uno il nome dell'altro, o asimmetrica se il mittente conosce in anticipo il nome. In entrambi i casi lo svantaggio principale sta nel fatto che un cambiamento nel nome del processo implica un cambiamento del codice. Esempio: Simmetrica send (P1, message) → invia un messaggio a P1 receive (P2, message) → Riceve in message un messaggio da P2 Asimmetrica send (P1, message) receive (id, message) → Riceve messaggi da tutti e in id si trova il nome del processo che ha eseguito la send Comunicazione indiretta i processi non comunicano direttamente, ma utilizzano una mailbox condivisa su cui leggono e scrivono messaggi. A seconda dell'implementazione possono esistere più mailbox condivise tra due processi, oppure la stessa mailbox può essere usata da più di due processi. In questo caso è necessario, in caso di receive() multiple, decidere a chi vada il messaggio. Inoltre, la mailbox può avere un processo server, nel qual caso solo il server può ricevere e controllare la mailbox, mentre gli altri possono solo scrivere. Un'alternativa è che la mailbox sia gestita direttamente dal SO. Esempio: send(A, message) → spedire un messaggio alla mailbox A receive(A, message) → ricevere un messaggio dalla mailbox A Ovviamente questo introduce un problema: P 1, P 2 e P 3 condividono la mailbox A, P 1 spedisce e P2 e P3 ricevono. Chi ottiene il messaggio? Come sempre, sono disponibili diverse soluzioni: Permettere ad un canale che sia associato con al massimo due processi Permettere a solo un processo alla volta di eseguire l’operazione receive() Permettere al sistema di selezionare in modo arbitrario il ricevente. Il mittente è notificato di chi ha ricevuto il messaggio Sincronizzazione Oltre che per l'utilizzo di mailbox o meno, l'implementazione può differenziarsi nelle politiche di sincronizzazione di ricevitore e mittente. Lo scambio di messaggi può essere bloccante o non-bloccante: Bloccante (sincrono): Send bloccante: dopo la send() aspetta conferma dalla mailbox o dal receiver prima di continuare Receive bloccante: il ricevente, una volta invocata la receive(), è bloccato finchè non riceve conferma dalla mailbox o dal mittente Non-bloccante (asincrono): Send non-bloccante: il mittente spedisce il messaggio e continua, non aspetta alcun ACK Receive non-bloccante: il ricevente continua la sua esecuzione anche dopo la receive() Memoria condivisa Generalmente, in un sistema a memoria condivisa, uno dei processi crea un segmento condiviso, con un nome, al quale può accedere l'altro processo. La sincronizzazione di lettura e scrittura è comunque gestita dai processi e non dal SO. Ovviamente questo metodo è più veloce dello scambio di messaggi ma meno sicuro, ed è necessaria la sincronizzazione per gli accessi per evitare conflitti. Vediamo di seguito un esempio di questo in POSIX. Il processo prima crea il segmento di memoria condivisa segment id = shmget(IPC_PRIVATE, size, S_IRUSR | S_IWUSR); Il processo che vuole accedere alla memoria condivisa deve attaccarsi ad essa shared memory = (char *) shmat(id, NULL, 0); Ora il processo puo scrivere nel segmento condiviso sprintf(shared memory, "Writing to shared memory"); Quando il processo ha finito, stacca il segmento di memoria dal proprio spazio di indirizzi  shmdt(shared memory); Infine, per eliminare il segmento di memoria shmctl(shm_id, IPC_RMID, NULL); Pipe È un metodo di comunicazione in cui un processo scrive ad un'estremità della pipe e l'altro legge all'altra estremità. Le pipe sono bloccanti. Esse si dividono in 2 tipologie. Pipe Ordinarie Permettono la comunicazione in un stile standard produttore-consumatore Il produttore scrive ad un estremitá (la write-end della pipe) Il consumatore legge all’altra estremitá (la read-end della pipe) Le pipe ordinarie sono quindi unidirezionali e funzionano solo tra processi padre-figlio Pipe con nome Le pipe con nome sono piú potenti delle pipe ordinarie. Inoltre le comunicazioni sono bidirezionali e non è richiesta la relazione parent-child tra i processi comunicanti. Infine piú processi possono usare la stessa pipe per comunicare. Sono disponibili sia in sistemi UNIX sia in sistemi MS Windows. 6. Scheduling della CPU Con scheduling, si intende l'assegnazione di un'attività nel tempo. Esso è necessario per regolare l'ammissione dei processi nella memoria l'ammissione dei processi nella CPU È importante ricordare che possono esserci N processi nello stato pronto, 1 processo in esecuzione e M processi in attesa in RAM. Tipi di scheduler Come accennato in 4. Gestione dei processi e threads > Scheduling, ci sono più tipi di scheduler: Scheduler a lungo termine (o job scheduler) Seleziona quali processi devono essere portati nella ready queue. O(s) ⇒ può essere lento, visto che è invocato raramente Controlla il grado di multiprogrammazione (il massimo numero di processi in memoria) e il mix di processi di tipo I/O-bound molto I/O, molti brevi burst di CPU CPU-bound molti calcoli, pochi lunghi burst di CPU Può essere addirittura assente, esso è usato principalmente in sistemi con risorse limitate Scheduler a breve termine (o CPU scheduler) Seleziona quale processo deve essere eseguito dalla CPU O(ms) ⇒ deve essere veloce, visto che è invocato più spesso Esempio: 100 ms per processo, 10 ms per scheduling 10/(110) = 9% del tempo di CPU sprecato per scheduling Scheduler a medio termine La RAM fisica ha uno spazio limitato, quindi si può estendere e creare così una memoria virtuale sul disco, che funge da RAM. Questa parte del disco viene chiamata backing store. La CPU comunque comunica solo con la RAM fisica, e se un processo è nel backing store, devo prima passarlo nella RAM tramite uno swap-in, e successivamente con uno swap-out lo posso rimettere nel backing store. Riassumendo, lo scheduler a medio termine è presente nei S.O. con memoria virtuale (che è una parte del disco che viene usata temporaneamente come RAM) e si occupa della rimozione forzata (swapping) di un processo dalla CPU Un processo, alla fine di un burst di CPU può essere infatti posto nel disco, in una coda diversa da quella di ready, per essere poi recuperato in seguito Serve per ridurre il grado di multiprogrammazione Dispatcher L'operazione più critica è quella fatta dal dispatcher, ovvero assegna la CPU ad un certo processo e fa passare il processo da ready a running. Come avviene nel dettaglio? 1. Cambio di contesto: viene salvato il PCB del processo che esce e viene caricato il PCB (precedentemente registrato) del processo che entra 2. Passaggio alla modalità utente 3. Salto all'istruzione da eseguire del processo appena arrivato nella CPU Ovviamente per fare questo, è presente una latenza di dispatch, ossia il tempo necessario al dispatcher per fermare un processo e farne ripartire un altro. E ovviamente deve essere la più bassa possibile. Prelazione Ottimizzare lo short-term scheduler è fondamentale per massimizzare l'utilizzo della CPU, pertanto sono state studiate molte tecniche e algoritmi per migliorare le prestazioni. Dal punto di vista della CPU, ogni processo può essere visto come una serie di CPU burst e I/O burst (dove per burst si intende un intervallo di utilizzo necessario al completamento della task). A partire da questi, si definisce una prima classificazione delle politiche di scheduling, in base alla prelazione(preemption), ossia al rilascio forzato della CPU. Scheduling con prelazione (preemptive): un processo che detiene la CPU può essere forzato a rilasciarla prima del termine del burst. Un esempio può essere il pronto soccorso. Mentre mi stanno curando il braccio rotto, arriva il vecchio con un arresto cardiaco. I medici paccano me e vanno dal vecchio che sta per morire. Ovviamente la prelazione rende il tutto più complicato. Scheduling senza prelazione (non-preemptive): un processo che detiene la CPU non può essere forzato a rilasciarla prima del termine del burst. Metriche di scheduling Per valutare un algoritmo di scheduling si utilizzano apposite metriche di scheduling: Utilizzo della CPU: percentuale di utilizzo media della CPU, l’obiettivo è tenere la CPU occupata il più possibile Throughput: numero di processi completati nell'unità di tempo Turnaround time (tempo di completamento): tempo totale dall'inizio del processo al termine. Comprende il waiting time. Turnaround = ExitTime - ArrivalTime o anche Turnaround = WaitingTime + Tempo di esecuzione (CPUburst) Waiting time: tempo speso dal processo nella ready queue, è influenzato dall’algoritmo di scheduling. Response time: tempo compreso tra l'arrivo del processo nella ready queue e la sua prima esecuzione (quando ottengo la CPU), il primo dispatch. Quando clicco l'icona di un programma mi aspetto una reazione a breve, di solito sotto i 100 ms, sennò, in media, l'utente non è contento. Nota: Negli algoritmi non-preemptive, tempo di attesa e di risposta sono uguali. Inoltre, l'obiettivo è massimizzare l'utilizzo della CPU e il throughput, e minimizzare il tempo di turnaround, il tempo di attesa e il tempo di risposta. A seconda del sistema si può decidere di bilanciare tali metriche o focalizzarsi sulla minimizzazione/massimizzazione di una o più. Ad esempio, nei sistemi interattivi si preferisce minimizzare la varianza del tempo di risposta piuttosto che la media. Algoritmi di scheduling Di seguito sono riportati i principali algoritmi di scheduling: First Come First Served (FCFS) È un algoritmo di base, semplice da implementare e leggero. La coda dei processi funziona come una FIFO, si eseguono quindi i processi in ordine di arrivo. Svantaggi: Ha bassi tempi di risposta ma un waiting time medio molto lungo. Soggetto all' "effetto convoglio": l'esecuzione di processi corti è ritardata da processi più lunghi. È suscettibile a come i processi arrivano.  Essendo non pre-emptive, è un algoritmo problematico per i sistemi a time sharing e per i sistemi interattivi. Esempio Sono dati i seguenti tre processi, con i relativi tempi di arrivo e CPU burst. Processo Tempo di arrivo CPU burst P1 0 24 P2 2 3 P3 4 3 Per capirci meglio, ecco quello che accade: Tempo 0 − 24 24 − 27 27 − 30 P1 X P2 X P3 X Calcoliamo ora il tempo di risposta (response time), di attesa (waiting time), e di completamento (turnaround time) di ogni processo. Processo TR TW TT P1 0 0 24 P2 22 22 25 P3 23 23 26 Analizziamo P1 : È arrivato per primo, non subirà alcun rallentamento. Avrà response time 0, waiting time 0 e tempo di completamento 24. Analizziamo P2 : È arrivato secondo, subirà un rallentamento a causa di P1 Avrà response time (ovvero la differenza tra quando inizia la sua esecuzione per la prima volta e quando è arrivato nella coda) pari a 24 − 2 (deve aspettare che finisca P1. Avrà waiting time (tempo speso dal processo nella ready queue) pari a 22, in questo caso come il response time. Avrà turnaround time (tempo trascorso dall'inizio del processo al termine) pari a WaitingTime + Tempo di esecuzione (CPUburst) = 22 + 3 = 25. Analizziamo P3 : È arrivato terzo, subirà un rallentamento a causa di P1 e P2 Avrà response time (ovvero la differenza tra quando inizia la sua esecuzione per la prima volta e quando è arrivato nella coda) pari a 27 − 4 = 23 (deve aspettare che finisca P e P. 1 2 Avrà waiting time (tempo speso dal processo nella ready queue) pari a 23, in questo caso come il response time. Avrà turnaround time (tempo trascorso dall'inizio del processo al termine) pari a WaitingTime + Tempo di esecuzione (CPUburst) = 23 + 3 = 26. Il tempo di attesa medio è pari a 0+22+23 3 = 15 Esempio 2 Sono dati i seguenti tre processi, con i relativi tempi di arrivo e CPU burst. Processo Tempo di arrivo CPU burst P1 4 24 P2 0 3 P3 2 3 Per capirci meglio, ecco quello che accade: Tempo 0 − 3 3 − 6 6 − 30 P1 X P2 X P3 X Calcoliamo ora il tempo di risposta (response time), di attesa (waiting time), e di completamento (turnaround time) di ogni processo. Processo TR TW TT P1 6 − 4 = 2 2 2 + 24 = 26 P2 0 0 3 P3 1 1 1 + 3 = 4 Il tempo di attesa medio è pari a 2+0+1 3 = 1 Shortest Job First (SJF) Esegue i processi in ready queue partendo da quello con prossimo CPU-burst minore. Può essere sia preemptive, sia non-preemptive. Nel caso di preemptive, se arriva un processo con CPU burst più breve del tempo rimanente a quello di esecuzione, quest'ultimo viene rimosso per fare spazio a quello appena arrivato. In questo caso l’algoritmo si chiama Shortest-Remaining-Time-First (SRTF). L'algoritmo è ottimo per la minimizzazione di waiting time medio e quindi di turnaround (vedi algoritmi greedy) Problema di starvation: un processo con CPU burst molto lungo potrebbe non arrivare mai alla CPU È difficile stimare il burst di un processo. Per ovviare al problema si stima il prossimo burst di CPU tramite media esponenziale. La formula è la seguente: T n+1 = α ⋅ t n + (1 − α) ⋅ T n dove T è il valore stimato per il prossimo burst, T è la media dei burst passati e t la durata n+1 n n dell'ultimo burst registrato, α è un valore compreso tra 0 e 1. In questo modo si ottiene una buona stima del prossimo burst di CPU. Esempio 1 - non-preemptive Sono dati i seguenti quattro processi, con i relativi tempi di arrivo e CPU burst. Processo Tempo di arrivo CPU burst P1 0 7 P2 2 4 P3 4 1 Processo Tempo di arrivo CPU burst P4 5 4 Per capirci meglio, ecco quello che accade: Tempo 0 − 7 7 − 8 8 − 12 12 − 16 P1 X P2 X P3 X P4 X Calcoliamo ora il tempo di risposta (response time), di attesa (waiting time), e di completamento (turnaround time) di ogni processo. Processo TR TW TT P1 0 0 7 P2 8 − 2 = 6 6 6 + 4 = 10 P3 7 − 4 = 3 3 3 + 1 = 4 P4 12 − 5 = 7 7 7 + 4 = 11 Quindi quello che succede è che una volta che un processo termina, viene eseguito quello con CPU burst minore. Essendo però non-preemptive, se entra un processo con CPU burst minore quello in esecuzione non viene killato. Esempio 2 - preemptive I dati sono uguali al precedente esempio. Processo Tempo di arrivo CPU burst P1 0 7 P2 2 4 P3 4 1 P4 5 4 Per capirci meglio, ecco quello che accade: Tempo 0 − 2 2 − 4 4 − 5 5 − 7 7 − 11 11 − 16 P1 X X P2 X X P3 X P4 X Più precisamente: A t = 2 entra P2 che ha CPU burst < P1 (4 < 5). A t = 4 entra P3 che ha CPU burst < P2 (1 < 2). A t = 5 P3 finisce. In questo momento appare anche P4 con CPU burst pari a 4. Ma dato che P2 ha CPU burst < P4 R detta claim edge che indica che P potrebbe richiedere R. Durante l'esecuzione i claim edge si trasformano in allocazioni se la richiesta è soddisfatta. Richieste che causano un ciclo nel grafo non vengono accettate, in quanto causano uno stato unsafe. Visto che è necessario un algoritmo per la rilevazione dei cicli, questo algoritmo ha complessità O(n ), dove n è il numero di processi. 2 Esempio Algoritmo del banchiere Come il RAG, ha bisogno di sapere il numero massimo di istanze che ogni processo potrebbe richiedere per ogni risorsa, ma funziona con qualsiasi numero di istanze, anche se è meno efficiente del RAG. Si basa sul mantenere delle strutture dati (matrici) con le informazioni sulle risorse richieste e allocate da ogni processo e sulle risorse di sistema disponibili. Ad ogni richiesta, si stabilisce se questa è possibile da soddisfare restando in uno stato safe, simulando l'assegnazione delle risorse. È costituito dunque da due algoritmi, l'algoritmo di allocazione e l'algoritmo di verifica dello stato. Vediamo ora quali strutture dati vengono utilizzate: int n; //i processi disponibili int available[m]; // numero di istanze di R_i disponibili int max[n][m]; // matrice delle richieste di risorse, le righe rappresentano i processi // le colonne le risorse int alloc[n][m]; // matrice di allocazione corrente int need[n][m]; // matrice bisogno rimanente, ovvero need[i][j] = max[i][j]-alloc[i][j] Vediamo ora una possibile implementazione dell'algoritmo di allocazione. // request_vector è un vettore contenente le richieste del processo P_i // ossia la colonna di max[i] dove i è il processo P_i void request (int req_vec []) { //se almeno un elemento è maggiore lancia un errore if (req_vec [] > need[i][]) error(); //il processo vuole usare di più del massimo dichiarato if (req_vec[] > available[]) wait(); //se non ci sono abbastanza risorse per soddisfare il processo, aspetto // simuliamo l'allocazione available[] = available[] - req_vec[]; //risorse disponibili -= risorse richieste alloc[i][] = alloc[] + req_vec[]; //risorse allocate += risorse richieste need[i][] = need[i][] - req_vec[]; //risorse di cui necessito -= risorse richieste if(!state_safe()) { //rollback available[] = available[] + req_vec[]; alloc[i][] = alloc[] - req_vec[]; need[i][] = need[i][] + req_vec[]; wait(); } Vediamo ora una possibile implementazione dell'algoritmo di verifica dello stato. //ritorno true se lo stato è safe, false se non è safe //Complessità: O(m*n^2) boolean state_safe() { //vettore locale uguale ad available[] int work[m] = available[]; boolean finish[n] = (FALSE,..., FALSE); int i; while(finish != (TRUE,..., TRUE)) { for(i = 0; (i < n) && (finish[i] || need[i][] > work[]); i++); if(i == n) return FALSE; else { work[] = work[] + alloc[i][]; finish[i] = TRUE; } } return TRUE; } Il problema principale dell'algoritmo del banchiere è la sua inefficienza, il semplice controllo dello stato safe/unsafe ha costo O(n ⋅ m), con n numero di processi e m tipi di risorsa. 2 Esempio Vediamo ora un esempio sul funzionamente dell'algoritmo del banchiere. Abbiamo 5 processi: P0 , P1 , P2 , P3 , P4 e 3 risorse: A (10 istanze) B (5 istanze) C (7 istanze) Inoltre, questa è la situazione al tempo t0 : Questa è la tabella dell'allocazione delle risorse, ossia nell'istante t0 quante risorse sono riusciti a prendere i 5 processi. Allocation A B C P0 0 1 0 P1 2 0 0 P2 3 0 2 P3 2 1 1 P4 0 0 2 Questa è la tabella delle risorse totali che ogni processo necessita di usare. Max A B C Max A B C P0 7 5 3 P1 3 2 2 P2 9 0 2 P3 2 2 2 P4 4 3 3 Calcoliamo ora quante istanze delle risorse A, B, C sono ancora disponibili al tempo t0 : Vediamo A: A P0 0 P1 2 P2 3 P3 2 P4 0 Istanze totali di A usate: 7 Istanze di A ancora usabili : 10 − 7 = 3 Vediamo B: B P0 1 P1 0 P2 0 P3 1 P4 0 Istanze totali di B usate: 2 Istanze di B ancora usabili : 5 − 2 = 3 Vediamo C: C P0 0 P1 0 P2 2 P3 1 P4 2 Istanze totali di C usate: 5 Istanze di C ancora usabili : 7 − 5 = 2 Dunque al tempo t0 le istanze disponibili sono le seguenti: Available A B C 3 3 2 Infine, calcoliamo quante risorse ogni processo necessita ancora, facendo MAX[] - ALLOCATION[], ossia risorse totali di cui necessito - risorse che sono già riuscito ad allocare. Need A B C P0 7 4 3 P1 1 2 2 P2 6 0 0 P3 0 1 1 P4 4 3 1 Detto questo, diamo per vero che al tempo T il sistema sia in stato safe, e è una 0 1 3 4 2 0 sequenza safe. Potremmo tranquillamente calcolarcela con l'algoritmo che vediamo tra poco, ma te lo lascio come esercizio per casa 😳. Ipotizziamo ora che P1 richieda (1, 0, 2) al tempo t1. Verifichiamo prima di tutto se P1 può farlo. richiesta di P 1 ≤ Available? ⟺ (1, 0, 2) ≤ (3, 3, 2) ⇒ OK Dunque P1 può richiedere la risorsa. Aggiorniamo quindi le tabelle nelle righe relative a P1. Allocation A B C P0 0 1 0 P1 2 + 1 = 3 0 0 + 2 = 2 P2 3 0 2 P3 2 1 1 P4 0 0 2 Available A B C 3 − 1 = 2 3 2 − 2 = 0 Need A B C P0 7 4 3 P1 1 − 1 = 0 2 2 − 2 = 0 P2 6 0 0 P3 0 1 1 P4 4 3 1 Non ci resta che eseguire l'algoritmo (la funzione request() sopra) e verificare se si presenterà un deadlock. Abbiamo innanzitutto che work[] = {2,3,0}. Ora parte il for(), che per ogni processo controlla se ci sono abbastanza risorse disponibili per soddisfarlo. i=0 finish=FALSE, need = (7,4,3) > work ❌ Dunque P0 non può allocare le risorse. i=1 finish=FALSE, need = (0,2,0) work ❌ i=3 finish=FALSE, need=(1,0,0) > work ❌ i=4 finish=FALSE, need=(0,0,2) > work ❌ A questo punto il for è finito ma siccome almeno un processo è riuscito ad allocare le risorse, found è stato impostato a true e il for riparte dall'inizio. i=0 finish=TRUE i=1 finish=FALSE, need=(2,0,2) > work ❌ i=2 finish=FALSE, need=(0,0,1) > work ❌ i=3 finish=FALSE, need=(1,0,0) > work ❌ i=4 finish=FALSE, need=(0,0,2) > work ❌ Il for è terminato nuovamente, nessuno ha allocato risorse quindi found è rimasto a false. Dunque si esce dal while e si verifica se f inish[i] = true per ogni i. La risposta è no, P , P , 1 2 P3 , P4 non riescono a prendere le risorse di cui necessitano, dunque P1 , P2 , P3 , P4 formano un deadlock. Dunque, abbiamo detto prima che "ogni tanto" si fa partire l'algoritmo visto sopra. Ma a quanto corrisponde quel "ogni tanto"? La frequenza di invocazione di un algoritmo di rilevamento dipende dalla frequenza con cui si verificano deadlock nel sistema. Generalmente vengono invocati ogni N cicli, o quando l'utilizzo della CPU scende sotto una certa soglia (sintomo di deadlock). Invocarli ad ogni richiesta di risorse è la scelta più sicura, ma anche la più costosa. Detto questo, come ripristiamo il sistema ad uno stato safe? Generalmente si opta per la gestione automatica da parte del sistema, che può intervenire in due modi: uccidendo tutti processi coinvolti o riprendendosi le risorse contese. Nel primo caso, l'uccisione di tutti i processi, si ha un elevato costo per il sistema e, nel caso i processi stessero interagendo con periferiche, si rischiano incosistenze. Inoltre tutti i processi dovrebbero ripartire, perdendo così il lavoro svolto. Spesso quindi si sceglie un'uccisione selettiva, ma in tal caso è necessaria una qualche politica per stabilire un ordine di priorità per la sequenza di uccisione. Inoltre, dopo ogni uccisione, è necessario invocare nuovamente l'algoritmo di rilevamento per stabilire se c'è ancora un deadlock. Se si sceglie la prelazione delle risorse, si deve anche in questo caso definire una politica per stabilire a chi vengono tolte le risorse ed in quale ordine. Nella situazione peggiore si deve effettuare un total rollback (cioè riparto da zero!). Segue che le operazioni di rollback, ovvero di ripristino ad uno stato passato per un processo, sono particolarmente costose ed esiste la possibilità di starvation. Conclusioni Abbiamo capito che ognuno dei 4 approcci visti ha vantaggi e svantaggi. Dunque, come sempre si è soliti fare in queste situazioni, si può cercare una soluzione combinata. Si può quindi suddividere le risorse in classi (tipo risorse interne, memoria, risorse di processo e spazio di swap) e per ognuna di esse scegliere l'algoritmo più appropriato. C'è anche una soluzione molto più semplice, usata per esempio in UNIX, ossia il complesso algoritmo dello struzzo. Semplicemente si nasconde la testa sotto la sabbia e si fa finta che i deadlock non si possano mai verificare.