Appunti teoria Sistemi di calcolo 2

Process and Threads

Processi

Sono entità dinamiche caricate in memoria e generate da un programma. Costituite da una serie di attività (task) controllate da uno scheduler che si trova su un processore sotto la supervisione del sistema operativo. Il S.O. controlla la comunicazione tra processi, l’allocazione delle risorse e l’interleaved execution. Un processo è formato da: codice, un insieme di informazioni, una serie di attributi che descrivono lo stato del processo durante l’esecuzione. Le caratteristiche di un processo sono: identificatore, stato, priorità, program counter, puntatori a memoria, stato dei registri e delle informazioni I/O e informazioni a fino statistici. Sono tutte informazioni che vanno nel Program Control Block (PCB) che consente al S.O. di gestire più processi.

Operazioni per processi

• Fork – Sdoppia il processo generando un figlio e entrambi vanno avanti in concorrenza. Cambia il PID del processo e vengono rilasciate delle informazioni per capire se l’utente si trova nel processo padre o figlio. Si genera un albero dei processi con ognuno un solo padre, quest’ultimo può aspettare il figlio prima di terminare ma non viceversa. Padre e figlio hanno la stessa configurazione; se la fork fallisce ritorna -1 e se il figlio ha successo ottiene 0. Figlio eredita dal padre una copia della memoria, copia registri e tutti i file aperti dal padre.
• Exit(status)/_exit(status) – Viene chiamata dal figlio per terminare l’esecuzione e ritorna l’argomento status che generalmente è il risultato del processo. La prima fa una pulizia (dealloca memoria e chiude descrittori) mentre la seconda torna bruscamente al sistema e, se il padre è ancora in esecuzione, mantiene il risultato fino a quando non gli viene richiesto tramite una wait e poi entra in stato zombie perché non muore realmente. Al contrario, se il padre ha terminato l’esecuzione prima del figlio, il figlio muore.
• Wait – Bloccante fino a quando il figlio non termina.

Thread

Filamento o flusso di esecuzione che viene identificato dal program counter. Ogni thread ha uno stato di esecuzione, uno stack di esecuzione, spazio per variabili locali, accesso in memoria e alle risorse appartenenti al proprio processo.

Thread vs Processi

I thread impiegano meno tempo a terminare, anche switchare fra due thread è più veloce. Possono comunicare fra loro perché hanno una zona di memoria condivisa mentre i processi no. È possibile sincronizzare gli stati di esecuzione dei thread in maniera simile ai processi. Il S.O. gestisce i processi, non i thread, quindi terminare un processo implica la terminazione di tutti i thread appartenenti a quest’ultimo.

Stati thread

Running, ready, blocked. Si passa da uno all’altro tramite system call (spawn, block, unblock, finish).

Implementazione thread

ULT – Si lascia gestire il thread al programmatore. Il S.O. riconosce solo che esiste un processo con dentro una libreria per i thread ma non è in grado di sapere quanti siano all’interno del processo. Una chiamata a sys call bloccherebbe l’intero processo ma preservando gli stati dei thread. Vantaggi: si possono definire politiche di scheduling diverse da quelle predefinite, lo switch fra thread non richiede l’intervento del S.O., può essere eseguito su qualsiasi S.O. ricompilando solo il codice. Svantaggi: una chiamata bloccante bloccherebbe tutto, viene assegnato solo un core anche con più thread.

KLT – Il kernel sa quanti thread ci sono nel processo e ne tiene conto nello scheduling. Vantaggi: posso mettere più thread su più core, se un thread si blocca, il kernel può schedulare uno diverso dello stesso processo. Svantaggi: il trasferimento del controllo da un thread all’altro nello stesso processo richiede un cambiamento di modalità del kernel.

Modelli per gestire thread

• Manager/Worker – Un thread manager assegna diversi lavori ad altri thread workers. Il manager gestisce gli input e distribuisce il lavoro nei vari task.
• Pipeline – Ogni task è diviso in tante sottoperazioni ognuna svolta in serie da diversi thread concorrentemente.

Memoria

Ogni thread ha una propria memoria privata ma può comunicare con gli altri tramite un’altra condivisa.

Concurrency: mutual exclusion and synchronization

Sincronizzazione e mutua esclusione

Si hanno problemi di sincronizzazione e mutua esclusione quando si vuole lavorare con più processi, ad esempio multiprogramming (più processi in un solo processore), multiprocessing (più processi e più processori), distributed processing (più macchine e più memorie oltre a più processi). La concorrenza avviene in tre differenti contesti: quando abbiamo più applicazioni, processi o thread; quando vogliamo generare applicazioni strutturate che sfruttano i thread; oppure nel S.O. che è strutturato in thread o più processi perché si deve occupare di allocare le risorse e decidere chi mandare in esecuzione.

Operazione atomica

Funzione o azione composta da più operazioni di base che risultano indivisibili. L'atomicità garantisce l'isolamento di una porzione di codice da un altro. Non si può essere interrotti durante la sua esecuzione.

Sezione critica

Porzione di codice in cui un processo va a modificare una variabile condivisa o ad una risorsa condivisa (non per forza scrivere, anche leggere). Deve essere minima e finita.

Mutua esclusione

Devo garantire su ogni sezione critica che mentre viene utilizzata una risorsa, nessun altro processo può accedervi.

Race condition

Conseguenza di una mutua esclusione non garantita. Situazione in cui più processi entrano nella sezione critica.

Deadlock

Situazione in cui due processi si bloccano a vicenda e nessuno dei due riesce a progredire.

Livelock

I processi provano a fare qualcosa per uscire dalla situazione di stallo ma non porta a nessun vantaggio. Qui c’è un cambiamento di stato. Se sono in busy waiting è ancora in deadlock non in livelock.

Starvation

Un processo non ha niente che lo blocca ma non riesce a progredire magari per motivi di priorità.

L’output di un processo deve essere indipendente dai tempi di esecuzione degli altri processi, non posso fare assunzioni a priori perché dipende dalle attività degli altri processi, il modo in cui il S.O. gestisce gli interrupt o dalle politiche di scheduling. Difficoltà: sharing di risorse globali, difficoltà per il S.O. su come allocare ottimamente le risorse, difficoltà ad individuare errori di programma perché i risultati non sono deterministici.

Sistema operativo

Deve essere capace di tenere traccia dei vari processi, allocare e de-allocare le risorse per ogni processo attivo, applicare delle politiche eventualmente per evitare il deadlock, proteggere i dati dalle interferenze degli altri processi, assicurare che i processi e gli output siano indipendenti dalla velocità del processo.

Concurrency: mutual exclusion and synchronization (parte seconda)

Gestione della sezione critica

Come si struttura un programma quando devo gestire una sezione critica? Suppongo sempre che sia in un ciclo infinito perché posso immaginare che anche se lo chiudo poi lo riavvio. C’è del codice prima della sezione critica, la sezione critica e poi un’altra porzione da eseguire. Bisogna fornire delle primitive per entrare nella sezione dove tutti i processi accedono alla stessa risorsa e poi bisogna segnalare in qualche modo anche l’uscita dalla sezione. L’entrata e l’uscita devono essere delle operazioni atomiche.

Requisiti per la mutua esclusione

Un processo nella sua critical section non deve interferire con altri processi, non ci deve essere deadlock o starvation, non si devono fare assunzioni in base ai tempi di esecuzione degli altri processi e, infine, un processo deve rimanere nella sezione critica per un tempo finito.

Implementazione entrata/uscita in cs

A livello hardware posso aiutarmi con degli interrupt, tuttavia posso diminuire l’efficienza e poi è un approccio che non si può applicare ad architetture multiprocessore. Si possono utilizzare soluzioni particolari implementate in varie architetture:

• Compare&Swap: Atomica. Scambia il valore di un registro con quello che gli viene assegnato e restituisce quello originario. Provoca busy waiting ed è utilizzabile solo sulle architetture che la implementano.
• Exchange: Scambio registro con un’area di memoria. Atomica.

Vantaggi: sono semplici e facili da utilizzare e possono essere utilizzate per garantire più critical sections. Svantaggi: busy waiting (un processo che aspetta per accedere in CS consuma risorse), starvation e deadlock.

Meccanismi classici software

Semaforo: È una struttura che impedisce l’accesso ad altri processori in CS e nel momento in cui uno non riesce ad entrare, si blocca. Quando il semaforo viene sbloccato, il S.O. prende un processo e lo mette in esecuzione. Due tipi di semaforo: intero e binario.

Mutex: È un semaforo in cui chi blocca deve sbloccare mentre nei semafori binari anche altri processi possono sbloccarlo.

Variabile di condizione: Tipo di dato che blocca il processo fino a quando non si verifica una certa condizione.

Monitor: Semaforo a oggetti. È un linguaggio che contiene metodi per la sincronizzazione.

Messaggi: Procedo se trovo un messaggio che dice ‘posso precedere’ e lo prelevo. Quando ho terminato invio un messaggio dove affermo che qualcun altro può procedere.

Spinlocks: Meccanismi di mutua esclusione che fanno busy waiting.

Semafori

È una struttura che ha una variabile e tre metodi che lavorano sulla variabile. Quest’ultima è un intero che viene inizializzato ad un valore non negativo che indica quante risorse si hanno. Ho due operazioni: semWait (decrementa il valore e toglie una risorsa) e semSignal (aumenta il valore e mette una risorsa disponibile). Non posso sapere il valore interno della variabile, lo so solo quando la inizializzo. Se decrementandolo il semaforo diventa negativo allora non entro e finisco in coda di attesa, aspetterò che il valore tornerà positivo ma non posso sapere se entrerò in coda di attesa ancora prima di averla chiesta. Non posso sapere il numero di processi bloccati. Un semaforo che usa una coda FIFO è strong, altrimenti è weak (non si sa l’ordine con cui verranno rimessi in esecuzione i processi nella coda).

Concurrency: mutual exclusion and synchronization (parte terza)

Producer/Consumer Problem

Asserzioni: uno o più produttori generano informazioni che inseriscono all’interno di un buffer e uno o più consumatori prendono risorse dal buffer uno alla volta. Possono accedere al buffer o un produttore o un consumatore e devono farlo uno alla volta. Problema: assicurarsi che il produttore non possa aggiungere risorse in un buffer pieno e consumatore non possa toglierle in uno vuoto.

Buffer infinito

Non vado a pormi il problema del produttore perché posso aggiungere una risorsa sempre in uno slot a destra del precedente, tuttavia, devo assicurarmi che i consumatori non leggano dati se non ce ne sono disponibili. Utilizzo due semafori per la sincronizzazione: il primo (s) per gestire la sezione critica e il secondo (n) per indicare che è possibile accedere ad una risorsa del buffer. Il produttore produce la risorsa, vede se non c’è nessuno in CS e nel caso entra e inserisce la risorsa nel buffer, poi esce dalla sezione critica e facendo la signal indica che c’è una risorsa disponibile. Il consumatore prima fa una wait per verificare se ci sono risorse disponibili poi ne fa un’altra per vedere se può entrare in sezione critica ed eventualmente entra e fa una signal per uscire.

Buffer finito

Utilizzo una costante sizeofbuffer per dirmi quanto è la capacità. Uso tre semafori: uno per accedere in mutua esclusione al buffer, uno per dirmi quanti sono gli elementi che posso consumare e uno che segnala quante sono le celle in cui posso scrivere.

Il produttore produce la risorsa, vede se ci sono celle disponibili in cui scrivere (wait-e) e nel caso entra in cs (wait-s), poi inserisce la risorsa ed esce dalla cs (signal-s) e segnala che c’è una risorsa in più che può essere consumata (signal-n). Il consumatore vede se ci sono risorse da consumare (wait-n), vede se può entrare in cs (wait-s), consuma la risorsa, lascia la cs (signal-s) e segnala che c’è una cella in più in cui si può scrivere (signal-e). Se scambio una coppia di wait si va in deadlock perché se entro prima nel buffer e poi controllo se ci fossero celle su cui scrivere potrei bloccarmi e non rilasciare mai il buffer non permettendo quindi l’accesso al consumatore. Viceversa, se scambio due wait nel consumatore non permetterò mai l’accesso al produttore. Se scambio due signal, non succede assolutamente nulla.

Message Passing

Con un messaggio posso garantire comunicazione ma anche sincronizzazione. Funziona con due primitive: send e receive. Quest’ultima ha due significati: ricevo un messaggio da quella destinazione e rimango bloccato anche se me ne arrivano altri oppure ricevo un messaggio con scritto chi lo ha mandato nella sorgente. Quando faccio una send posso attendere una ricevuta di consegna oppure andare avanti. Quando si fa una receive possono succedere due cose: se non ci sono messaggi posso bloccarmi in attesa e decidere di fare altro, se ci sono messaggi posso analizzarli e questo implica che chi manda e riceve può bloccarsi o no. Un sender e receiver bloccanti si chiama rendez-vous ed è utilizzato per la sincronizzazione fra processi per mandarli avanti insieme. La combinazione nonblocking send, blocking receive è la più usata e permette di inviare più messaggi a più destinazioni diverse.

Per la consegna di messaggi posso usare indirizzamento diretto o indiretto. Nel caso di indirizzamento diretto viene specificato il destinatario nella send, mentre nella receive è facoltativo il mittente. Nel caso di indirizzamento indiretto il messaggio è mandato ad una mailbox e il destinatario lo prende da lì. La mailbox può essere una semplice coda che mantiene i messaggi fino a che il receiver non li ha presi.

Readers/Writers Problem

Abbiamo un’area di memoria condivisa dove ci sono dei lettori che simultaneamente possono solo leggere e degli scrittori che possono solo scrivere in questa area ma uno alla volta. Mentre uno scrittore scrive non ci devono essere lettori.

Deadlock

Una situazione permanente di processi che competono per qualche risorsa di sistema o per comunicare l’uno con l’altro. Non ci sono soluzioni efficienti per uscirne.