Sistemi di Calcolo 2

Processi AP 1 (thread)

Un processo è un programma in esecuzione composto da un insieme di dati, possibilmente condiviso, e da degli attributi che descrivono lo stato del processo. Gli elementi di stato in esecuzione di un processo sono: identificatore, stato, priorità, program counter, puntatori, informazioni di accounting, informazioni di I/O, contesto, memoria e dati.

Il Process Control Block (PCB) contiene gli elementi del processo ed è creato, gestito e supportato dall'OS. Inoltre un processo può creare anche più processi figlio. La system call fork() crea un nuovo processo C: l'intera memoria viene copiata e duplicata. Ogni processo eseguito concorrentemente diviene figlio del padre, il quale può creare altri processi, creando così un albero delle fork, la cui radice è un processo chiamato init o bootstrap.

Quando il computer viene acceso, un programma inizializza i registri, fa partire il controller del device, carica la CPU e la memoria 05, e inizia lui il processo. La fork restituisce -1 in caso di errore, 0 nel caso del figlio, e l'identificatore del figlio nel caso del padre. Tra padre e figlio cambia solo l'ID del processo, perché memoria e registri CPU sono copiati, mentre i file aperti vengono ereditati dal padre; anche il PCB è una copia del padre.

System call exit

Esempio di uso della fork(): system call exit(), chiamata eseguendo la funzione exit(status): salviamo lo status, eseguiamo le funzioni atexit(), eseguiamo fflush, chiudiamo gli stream, scarichiamo con exit() le connessioni e i file aperti, chiamiamo status e si può usare qui.

Per creare nuovi processi si eseguono system call. Exit() salva lo status dei figli e lo chiama dallo status; la memoria viene assegnata al processo padre attivo, che richiede il risultato e lo conserva finché il figlio non termina. In questo caso, se il padre non fa wait, il figlio entra nello stato di zombie: il figlio è morto ma il padre non ha ancora letto tutto. Se invece il padre termina, qualsiasi figlio viene terminato.

System call wait e waitpid

La system call wait() blocca il padre finché non termina un figlio; ritorna l'identificatore del figlio terminato, altrimenti -1 se non esiste un figlio. Se vogliamo aspettare uno specifico figlio, dobbiamo usare la chiamata waitpid(), che blocca il padre finché un particolare figlio termina.

Caratteristiche dei processi e scheduling

I processi hanno due caratteristiche: possedimento di risorse e scheduling. Un OS può supportare quattro casi:

• Singolo processo con singolo thread: supportato da MS-DOS.
• Processi multipli con singolo thread: alcuni sistemi Unix presentano ognuno un processo con un thread.
• Singolo processo con molteplici thread: environment Java supporta un time processor con molteplici thread.
• Processi molteplici con molteplici thread: Windows e i moderni sistemi Unix supportano più processi, ognuno con thread.

Ogni thread ha contenuti salvati e stato di esecuzione: running, ready e blocked. Mentre uno è in esecuzione, altri possono accedere alle variabili locali contenute nello stack; uno per esecuzione, dentro il loro program counter e indipendente alla memoria e alle risorse del processo.

Vantaggi dei thread: tempo di creazione e terminazione minore rispetto ai processi; passare da un thread all'altro è più veloce; i thread possono comunicare tra loro senza chiamare il kernel. Sospendendo un processo si sospendono tutti i thread; terminando un processo terminano tutti i thread nel processo.

I thread possono trovarsi nei seguenti stati: blocked, ready, running. Per cambiare lo stato di un thread possiamo creare un altro thread, bloccarlo, sbloccarlo, terminarlo, salvare il contenuto dei registri e lo stack. Esempio: Remote Procedure Call, cavolo nei e duello.

Thread user level e kernel level

Per implementare la gestione dei thread in user level thread (ULT), l'esistenza dei thread è fatta dalle applicazioni e l'OS non ha conoscenza dello user space. Le applicazioni gestiscono lo scheduling dei thread.

Vantaggi dei ULT: lo switching dei thread non richiede i privilegi dell'OS; ogni thread gira su OS. Svantaggi dei ULT: se un thread si blocca, blocca tutto il processo; non sfrutta a pieno i vantaggi di architetture multiprocessor o multicore.

L'approccio può essere anche mixato, cioè ULT anche con kernel level thread. I thread in C usano pthread.

Thread in C con pthread

pthread_create: int pthread_create(pthread_t *thread, const pthread_attr_t *attr, void *(*start_routine)(void *), void *arg); memorizziamo l'ID del thread creato; attr è sempre Null; start_routine è il puntatore alla funzione da eseguire; arg è l'argomento da passare come alla funzione start routine. Restituisce 0 in caso di successo o la causa in caso di errore.

pthread_exit: void pthread_exit(void *value_ptr); termina il thread corrente rendendo il valore disponibile per una eventuale operazione di join. pthread_cancel termina invece un altro thread.

pthread_join: int pthread_join(pthread_t thread, void **value_ptr); attende la terminazione del thread con identificatore thread. Se value_ptr è diverso da Null, memorizza il valore eventualmente restituito dal thread. Restituisce 0 in caso di successo, altrimenti la causa dell'errore.

pthread_detach: int pthread_detach(pthread_t thread); notifica al sistema che su quel thread non ci saranno operazioni di join. Restituisce 0 in caso di successo, altrimenti la causa dell'errore.

Per misurare le performance bisogna linkare con -lrt e -lm.

Processi vs thread

Performance: lanciare e terminare un thread è più veloce rispetto a lanciare e terminare un processo. Memoria: quando si lancia un processo si copia l'intera memoria del padre, mentre tutti i thread hanno accesso alla stessa memoria globale condivisa. Comunicazione: i thread dello stesso processo possono usare la memoria condivisa; i processi richiedono meccanismi di comunicazione interprocesso per comunicare.

Un codice è detto thread safe se thread multipli possono eseguirlo simultaneamente senza avere interazioni inaspettate. Esempio: due thread incrementano insieme il valore di una variabile, aumentando il valore solo di 1 invece che di n, perché arriva solo l'ultimo che modifica la variabile.

Categorie di system computer

• Single Instruction Single Data (SISD): singolo processore che esegue una singola istruzione per operare su un dato custodito in singola memoria.
• Single Instruction Multiple Data (SIMD): ogni istruzione è eseguita su un insieme diverso di dati da un processore.
• Multiple Instruction Single Data (MISD): una sequenza di dati è trasmessa a un insieme diverso di processori, che eseguono ognuno una sequenza diversa.
• Multiple Instruction Multiple Data (MIMD): un insieme di processori esegue simultaneamente istruzioni diverse su insiemi di dati diversi e sequenze diverse.

Considerazioni di design per architetture multiprocessore

• Processori paralleli, OS su processori concorrenti o thread concorrenti.
• Scheduling.
• Sincronizzazione.
• Gestione della memoria.
• Affidabilità e fault tolerance.

Concorrenza AP 2

Parole chiave correlate alla concorrenza

Atomic operation: un'azione implementata come una funzione o una sequenza di istruzioni indivisibili, che iniziano e arrivano alla fine come se apparissero come un'unica operazione. L'atomicità garantisce isolamento dai processi concorrenti; allo stato finale tornano dallo stato iniziale.

Critical action: codice in sezione critica che richiede accesso a risorse condivise utilizzate da un processo e non deve essere eseguita mentre un altro processo usa le stesse risorse condivise.

Mutua esclusione: se un processo si trova in una sezione critica, nessun altro processo può trovare nella sua sezione critica quelle stesse risorse condivise che sta usando.

Race condition: processi e thread leggono e scrivono dati condivisi; il risultato finale dipende dal tempo delle loro esecuzioni e da chi scrive più lentamente.

Deadlock: due o più processi non possono fare nulla perché ognuno aspetta che altri facciano qualcosa. Esempio: P2 aspetta P5, P5 aspetta P2, e nessuno fa nulla.

Livelock: due o più processi cambiano di continuo il loro stato senza fare nulla di utile ai fini del programma.

Starvation: un processo viene trascurato dalla schedula e non riceve mai CPU.

Difficoltà della concorrenza

Alcune difficoltà della concorrenza sono: la condivisione di risorse globali; la difficoltà dell'OS di organizzare in modo ottimale l'allocazione delle risorse; la difficoltà di localizzare errori di programmazione.

Il sistema operativo deve: tenere traccia dei vari processi con PCB; allocare e deallocare risorse per ciascun processo attivo; proteggere le risorse fisiche e i dati di ciascun processo dall'interferenza di altri processi; assicurarsi che gli output siano indipendenti dalla velocità dei processi.

Se i processi competono per risorse comuni bisogna affrontare tre necessità:

• Mutua esclusione.
• No deadlock.
• No starvation.

Mutua esclusione

Un programma deve garantire sempre mutua esclusione, no starvation e no deadlock. Inoltre, se un processo non si trova nella sua sezione critica, non deve interferire con altri processi che vogliono entrare nella loro sezione critica; mentre un processo si trova nella sezione critica, deve restarci per un tempo finito. Non facciamo alcuna assunzione sulla velocità o sul numero dei processi.

Ora vediamo alcuni tentativi, con supporto hardware, al problema della mutua esclusione:

• Disabilitiamo interrupt nei sistemi uniprocessori: efficiente ma poco.
• Compare and swap, circuito hardware: esclusione mutua sì, no deadlock, no starvation potrebbe esserci. Confrontiamo un valore in memoria con un valore atteso; se sono uguali facciamo swap con un nuovo valore. Garantisce no deadlock, non garantisce starvation.
• Istruzioni hardware di exchange: scambia il contenuto di un registro con quello di una memoria. Garantisce deadlock no, non garantisce starvation.

Sono utilizzabili anche con multiprocessori. Busy waiting, semplici, decide possibili, più costoso anche con Stancs, e non sono presenti in tutte le architetture.

Meccanismi software per la concorrenza

Meccanismi software comuni per la concorrenza sono: semafori, mutex, condition, variabile binaria, flags, spinlock, event, mailbox, message.

I semafori sono una variabile intera su cui sono possibili tre operazioni: inizializzazione a un valore non negativo; wait, che decrementa il valore se il valore è maggiore di 0; signal, che incrementa il valore. Se il valore rappresenta il numero di risorse disponibili, rappresenta anche, se negativo, il numero di processi in attesa di risorse.

Quale implementazione di semafori: wait e signal possono essere strong FIFO oppure weak, se ci può essere starvation. Con i semafori si potrebbe implementare mutua esclusione; i semafori con compare and swap o interrupt. Noi usiamo le POSIX.

Semafori POSIX

Creare un semaforo staticamente: sem_t sem. sem_init: int sem_init(sem_t *sem, int pshared, unsigned int value); restituisce 0 in successo e -1 in errore; value è il numero di risorse condivisibili.

sem_wait(sem_t *sem): mette in attesa, facendo while con un count. sem_post(sem_t *sem): incrementa il count. sem_destroy(sem_t *sem): distrugge il semaforo. Possiamo implementare i semafori con compare and swap, con l'interrupt, con exchange o con while e operazioni giuste.

Monitor

I monitor sono implementati in C++ e hanno le stesse funzionalità dei semafori, ma sono più facili da usare. Le variabili locali sono accessibili solo con le procedure del monitor. Mentre un processo entra nel monitor, gli altri processi si troveranno in una coda di attesa.

La sincronizzazione è ottenuta con variabili condizionali contenute e accessibili solo dentro il monitor. Possiamo operare su queste variabili con funzioni: cwait(c), che sospende l'esecuzione sulla base della condizione, e csignal(c), che riprende dopo la stessa condizione.

Message passing

Il message passing permette a due processi di interagire tra loro e deve soddisfare due requisiti: la mutua esclusione e la sincronizzazione per la comunicazione. Fornisce funzioni per scambiare informazioni. Message passing lavora bene in sistemi distribuiti e multiprocessori con memoria.