Appunti per l'esame di Sistemi operativi

Sistemi operativi

Il sistema operativo serve come interfaccia tra livello applicativo ed hardware, non compie operazioni apparentemente utili ma fornisce un ambiente per il corretto funzionamento dei programmi.

Funzioni e servizi base

• Controllo flusso ed esecuzione dei programmi
• Allocazione risorse e gestione memoria
• Accesso a dispositivi I/O
• Comunicazione tra processi
• Gestione errori e malfunzionamenti
• Protezione
• Gestione statistiche e raccolta dati

Componenti base SO

• Gestore dei processi
• Gestore della memoria
• Gestore della memoria secondaria
• Gestore dei sistemi di I/O
• Gestore dei file
• Gestore della comunicazione di rete
• Gestore della sicurezza
• Interprete dei comandi

Tipi di sistema

• Sistemi paralleli => massimizzano throughput (multiprocessore / multicore / distribuiti)¹
• Si può simulare con sistemi time-sharing²
• Sistemi real-time => forniscono risultati entro il tempo prestabilito, possono essere HARD real time o SOFT real time (embedded / sistemi di controllo)

Sistemi multiprocessore e sistemi multicore

Nel caso di processori con multithread fisico si ha un unico chip con una sola ALU ma 2 set di registri separati che permettono l'esecuzione quasi simultanea.

throughput = (produttività) capacità elaborativa in un tempo determinato

¹ time-sharing = possiedono scheduler che assegna quanti di tempo limitati ad ogni processo

Sistemi cluster

Tipi di connessione

• Client-server => ruoli dispositivi ben definiti, un server ed n clients che si connettono ad esso
• Peer-to-peer => ogni dispositivo è sia server che client

Architetture di base

• Architettura a strati => ogni strato fornisce funzionalità allo strato superiore nascondendo quelle del livello inferiore
• Architettura microkernel => kernel comprende solo funzioni essenziali (scheduling / gestione interruzioni / gestione memoria / comunicazione tra processi), tutte le altre funzionalità sono trattate come processi

OSS Sia UNIX che Windows NT usano architetture intermedie incentrate su un kernel³ monolitico che implementa gli altri moduli dinamicamente.

Unix ha architettura base a strati.

Windows ha architettura base microkernel, inoltre è multithread nativo.

Standards

• Standard di linguaggio (API) => insieme delle funzioni di libreria che rimangono⁴ invariate al variare del sistema, permettono portabilità su piattaforme differenti (ex. ANSI-C)
• Standard di sistema (ABI) => insieme di servizi per la programmazione su una⁵ determinata famiglia di sistemi (POSIX per UNIX-LIKE, WINAPI per WINDOWS)⁶

Essendo POSIX gestito da Open Group, che vende le licenze, Linux usa uno standard simile chiamato LSB (Linux Standard Base).

Gli standard forniscono anche le funzioni preambolo per le System call.

kernel = nucleo del sistema operativo contenente tutte le funzioni essenziali³

API = application programming interface, librerie tra app e OS⁴

ABI = application binary interface, convenzioni di sistema, interazione tra OS e Hardware⁵

Certificazione POSIX appartiene a Open Group, Linux non è certificato POSIX⁶

Flusso di controllo eccezionale

Il flusso normale di un programma può essere alterato da:

• Interrupt (asincrone) => eventi generati all’esterno della CPU (I/O / segnali)
• Exception (sincrone) => eventi generati dalla CPU (trap / fault / abort)^{7 8 9}

Al verificarsi di uno di questi si utilizza il codice del sistema operativo, quindi cambia anche il modo di esecuzione, si passa da modalità utente (mode bit = 1) a modalità kernel (mode bit = 0) che permette di usare tutte le istruzioni di cui è dotato il sistema.

Per sapere quale programma del kernel bisogna utilizzare il sistema operativo fa riferimento al suo “interrupt vector”, un array contenuto nel kernel con tutti i descriptor (Linux) o handle (Windows) alle routine di sistema.

Implicano un context switch che utilizza una IRET per il ritorno. (vedere più avanti)

System call

Sono chiamate ad una routine di sistema operativo tramite il supporto delle trap.

Possono essere utilizzate direttamente tramite programmazione con Assembly mediante l'istruzione “int $0x80” che permette di accedere al “interrupt vector”, verrà eseguita la routine corrispondente al numero contenuto nel registro %?a? utilizzando come parametri le informazioni contenute nei registri subito dopo.

Altrimenti possono essere implementate in C (o altro linguaggi di alto livello) tramite uno o più wrapper (involucri), ovvero funzioni che avvolgono a loro volta altre funzioni fino ad arrivare al codice Assembly per la syscall. (ex. printf())

I wrapper fanno sembrare le System call normali funzioni di libreria e combinati con l'utilizzo dell'ambiente di esecuzione permettono la portabilità del codice, la syscall in sé è però machine dependent.

Ambiente di esecuzione

Insieme dei moduli aggiuntivi (import librerie e simili) inseriti nel codice dal linker in fase di compilazione del programma, cambia da un sistema operativo all’altro.

Serve come raccordo tra il kernel ed il main del programma, permette la portabilità del codice ricompilando sul nuovo sistema compatibile.

Ex: nei sistemi Linux il main richiama la funzione “_start()” che effettua il setup e ne permette l’esecuzione.

trap = istruzione macchina per il passaggio del controllo al kernel (usato per system call)⁷

fault = evento generato in condizione di errore, recuperabile (ex. Page fault)⁸

abort = evento raro non recuperabile, provoca terminazione del processo (ex. Prob hardware)⁹

I processi

Entità attiva che rappresenta il programma in esecuzione, 2 o più processi possono condividere lo steso programma.

I processi vengono creati da altri processi come loro copie, il processo che crea il nuovo processo viene detto padre, il processo creato figlio.

Si crea quindi una struttura ad albero dei processi (in Linux il primo processo è init).

Stati di un processo

1. New => fase di creazione del processo
2. Ready => il processo è pronto ed aspetta di essere assegnato alla CPU dallo scheduler per entrare in esecuzione
3. Running (USER / KERNEL) => il processo è in esecuzione nella CPU

OSS il numero massimo dei processi in stato running è dato dal numero delle CPU.

4. Waiting => il processo rimane in attesa di un evento di I/O
5. Terminated => il processo termina e rilascia le risorse utilizzate (funzione exit())

OSS Quando un processo termina, se lo stato di terminazione (dato dalla funzione exit()) non può essere raccolto dal padre, entra nello stato di Zombie, il suo stato di terminazione verrà quindi salvato in un record del kernel finché un altro programma lo raccoglierà e chiuderà.

Immagine in memoria

<- sp (stack pointer)

Ad ogni nuovo processo che entra in esecuzione viene associata una immagine di memoria virtuale corrispondente al suo spazio di indirizzamento.

<- brk

Lo spazio di memoria si divide in:

• Text => codice del programma (execute and read only)
• Data => variabili globali, static e stringhe (stringhe read only)
• Heap => memoria allocata dinamicamente
• Stack => dati delle funzioni, …

PCB (process control block)

Contiene tutte le informazioni per la gestione del processo contenuta nel kernel, differente dall'immagine di memoria ma contiene riferimenti ad essa.

È composto da:

• PID (process ID) e PPID (parent process ID)
• Puntatori ad immagine di memoria
• Privilegi del processo
• Stato del programma
• PC (program counter)
• Priorità ed informazioni sullo scheduling
• Tabella file processo ed I/O
• Area salvataggio registri

Creazione ed esecuzione processo in Unix (versione base)

#include <unistd.h>¹⁰
#include <stdio.h>
int main() {
pid_t pid = fork();¹¹
if (pid < 0) { /* -1 => error occurred */
printf("Fork Failed");
exit(1);
} else if (pid == 0) { /* child process */
execlp("/bin/ls", "ls", NULL); /* execute program “ls” */¹²
_exit(0);¹³
} else { /* parent process */
wait(NULL);¹⁴
printf("Child Complete");
}
return 0; /* in main equivalente a exit()*/
}

pid_t getpid() => restituisce pid processo

vfork() => figlio usa stesso Address space del padre

WARNING se si inserisce fork() in ciclo per generare più processi è essenziale terminare il codice figlio con “break;” o “_exit(status);” per evitare generazione infinita di processi (data dal “goto” alla fine del ciclo).

<unistd.h> => libreria contenente funzioni fork(), wait(), exec()…¹⁰

pid_t fork() => permette di creare nuovo processo come copia del padre ma con pid e immagine di memoria differenti, tutte le operazioni effettuate da adesso in avanti nella sezione del figlio non influenzeranno il padre (e viceversa)¹¹

int exec => famiglia di funzioni che permettono al processo di eseguire un nuovo programma passato come argomento, possibile consultare famiglia exec su Open Group¹²

void _exit(int status) => versione con trattino permette di mantenere canali I/O aperti siccome processo padre e figlio usano gli stessi, status = stato di ritorno¹³

pid_t wait(int *stat_loc) => costringe processo padre ad aspettare terminazione figlio evitando generazione processi zombie. Possibile salvare stato di ritorno del figlio su una variabile passandola come argomento stat_loc.¹⁴

Se processo ha più figli si usa funzione “waitpid()” per selezionare processo desiderato.

Threads

Un thread è definito come un processo leggero (lightweight process).

I thread appartenenti allo stesso processo, pur eseguendo operazioni differenti, utilizzano lo stesso spazio di memoria.

Rendono quindi possibile:

• Condivisione della memoria dentro lo stesso task¹⁵
• Multiprogrammazione e scalabilità¹⁶
• Esecuzione indipendente dei singoli thread, un thread può non essere bloccante per altro thread (Ex. grafica separata da elaborazione dati / richieste multiple su server)

Programmazione single core vs multicore

La programmazione multithread permette quindi di sfruttare la concorrenza nei programmi, si può implementare in due modi a seconda del tipo di architettura:

• Esecuzione concorrente => si utilizza in sistemi singolo core, illusione di parallelismo data dall’esecuzione alternata dei thread in quanti di tempo (interleaved)
• Esecuzione parallela => utilizzabile in sistemi multicore, permette di assegnare ad ogni core uno o più threads ed eseguirli contemporaneamente

2 tipi di parallelismo

• Data parallelism => suddivisione sottoinsiemi dei dati su più core per eseguire più velocemente stesse operazioni
• Task parallelism => suddivisione dei threads su ogni core, ognuno esegue le sue operazioni

task = insieme di threads appartenenti allo stesso processo¹⁵

scalabilità = esecuzione parallela su più processori (o core)¹⁶

Strategie creazione threads

• Threading sincrono => (fork-join) genitore dopo aver creato uno o più figli aspetta la loro terminazione e conseguente join prima di continuare la sua esecuzione. (Ex. somma vettore)
• Threading asincrono => dopo aver creato thread figlio, genitore riprende la sua normale esecuzione e non ha bisogno di conoscere quando termina il figlio. (Ex. server)

Categorie di thread

• Kernel level thread (KLT) => implementazione a livello kernel, scheduling più lento a causa del passaggio per il kernel ma i threads sono completamente indipendenti ed il blocco di uno non implica in blocco degli altri.
• User level thread (ULT) => implementazione a livello di applicazione, il kernel non è a conoscenza della loro esistenza, quindi scheduling più veloce ma nel caso di syscall bloccante su un thread si bloccano tutti.

Modelli di multithreading

1. Da uno a molti => più user threads mappati su un solo kernel thread, gestione efficiente risorse, non è però possibile usare parallelismo ed il blocco di uno provoca provoca il blocco di tutti. Usato su pochi sistemi.
2. Da uno ad uno => ogni user thread è mappato su un kernel thread, permette parallelismo e chiamate non sono bloccanti su altri threads, ha lo svantaggio di dover creare un kernel thread per ogni user thread (threads limitati per evitare overhead).¹⁷ Usato in Linux e Windows.
3. Da molti a molti => più user threads vengono mappati su un numero minore o uguale di kernel threads, permette di creare un numero maggiore di user threads rispetto al modello uno ad uno potendo rimappare gli ULT (necessita di LWP)

overhead = richiesta risorse maggiore di quella realmente necessaria¹⁷

Pthreads POSIX

I sistemi Unix non fanno distinzione tra processi e threads. Infatti posso anche usare syscall clone() invece di pthread_create().

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
void *print_message_function(void *ptr) {
char *message;
message = (char *) ptr;
printf("%s \n", message);
}
main() {
pthread_t thread1, thread2;
const char *message1 = "Thread 1";
const char *message2 = "Thread 2";
int iret1, iret2; /* permettono di controllare risultato, 0 in caso di successo */
iret1 = pthread_create(&thread1, NULL, print_message_function, (void*) message1);¹⁸
if(iret1) { fprintf(stderr,"Error - pthread_create() return code: %d\n",iret1); exit(EXIT_FAILURE); }
iret2 = pthread_create(&thread2, NULL, print_message_function, (void*) message2);
if(iret2) { fprintf(stderr,"Error - pthread_create() return code: %d\n",iret2); exit(EXIT_FAILURE); }
printf("pthread_create() for thread 1 returns: %d\n",iret1);
printf("pthread_create() for thread 2 returns: %d\n",iret2);
pthread_join(thread1, NULL);¹⁹
pthread_join(thread2, NULL);
exit(EXIT_SUCCESS);
}

int pthread_detach(phtread_t thread) => utilizzabile al posto di join, notifica che non verranno eseguite funzioni di join sul thread.

Le funzioni ritornano valore 0 in caso di successo, altrimenti la causa di errore.

void pthread_exit(void* value_ptr) => termina thread corrente.

OSS se uso funzione famiglia fork in processo multithread in molti sistemi Unix posso scegliere se replicare tutti i thread nel nuovo processore oppure no, se uso exec elimina tutti i thread già presenti. DA EVITARE ENTRAMBE.

int pthread_create(phtread_t* thread, const pthread_attr_t* attr, void* (*start_routine)(void*), void* arg);¹⁸

• thread => puntatore variabile pthread_t dove memorizzare id
• Attr => attributo di creazione (spesso NULL)
• start_routine => funzione da eseguire (deve essere void)
• Arg => puntatore ad argomenti della funzione, spesso vettore allocato dinamicamente

int pthread_join(phtread_t thread, void** value_ptr) => attende terminazione esplicita thread con id passato come argomento¹⁹

Extra threads

Threading implicito

Consiste nel delegare creazione e gestione dei thread a compilatori e librerie di routine.

• thread pools (gruppi) => Si crea un gruppo di threads durante la creazione del processo che attendono di eseguire un determinato servizio.

Finito il lavoro il thread torna in attesa, se non ci sono threads disponibili il servizio aspetta.

Non bisogna attendere creazione threads durante esecuzione processo e si evita overhead dato dalla creazione di troppi threads.

OSS numero threads potrebbe cambiare durante esecuzione.

• OpenMP => insieme di direttive per il compilatore che si inseriscono nel codice e permettono esecuzione parallela tramite librerie runtime OpenMP (Ex. #pragma omp parallel => crea più thread possibili su architettura ed esegue)
• Grand central dispatch => versione proprietaria per sistemi Apple simile a OpenMP e basata su pthread POSIX…

Thread-local storage (TLS)

Permette di allocare variabili visibili solo al thread, uniche per ogni thread.

Differiscono da variabili locali poiché visibili in tutto il thread e non solo nella funzione in cui sono invocate.

Processori virtuali (LWP) e scheduling threads

Necessari per implementazione da molti a molti dinamica, il sistema operativo crea processori virtuali intermedi che dialogano tra kernel threads e user threads.

Ad ogni LWP sono associati vari threads, al blocco di uno si bloccano anche gli altri.

Sono essenziali per lo scheduling in sistemi multithread che può avvenire in 2 modi:

• Process-contention scope (PCS) => ambito della cortesia rispetto al processo, ovvero la mappatura su LWP libero viene fatta in ambito utente tra i threads dello stesso processo.
• System-contention scope (SCS) => ambito della cortesia allargato al sistema, ovvero la mappatura su LWP viene fatta dal kernel e comprende tutti i threads presenti nel sistema.

OSS È possibile personalizzare le priorità di scheduling a livello utente.

OSS Linux e Mac OS X permettono solo SCS.

Lo scheduler

Si occupa della commutazione della CPU da un processo all’altro, funzione alla base dei sistemi operativi multiprogrammati, questi permettono infatti di mantenere in memoria più processi rispetto al numero di core disponibili.

Quando un processo entra in stato di wait (I/O) lo scheduler gli sottrae il controllo della CPU e la assegna ad un altro processo in stato ready.

Fasi cicliche di un processo

• CPU burst => fasi di elaborazione della CPU
• I/O burst => fasi di attesa dell’I/O

I programmi si possono dividere in due tipologie a seconda del tempo impiegato in ogni burst, è importante osservare la durata dei cicli.