riassuntoSOReti.pdf

SISTEMI OPERATIVI 1. INTRODUZIONE La maggior parte dei sistemi complessi sfruttano l’ architettura a livelli. Questo tipo di paradigma garantisce questi vantaggi (teoricamente): modularità → un sistema complesso è diviso in unità funzionali più semplici; semantica ben definita → ogni liv...

SISTEMI OPERATIVI 1. INTRODUZIONE La maggior parte dei sistemi complessi sfruttano l’ architettura a livelli. Questo tipo di paradigma garantisce questi vantaggi (teoricamente): modularità → un sistema complesso è diviso in unità funzionali più semplici; semantica ben definita → ogni livello si occupa di risolvere un problema ben definito; riutilizzo → un livello può essere utilizzato (“così com’è”) più volte in varie architetture; separazione delle responsabilità → ogni livello non si preoccupa di come gli altri livelli eseguano il proprio lavoro; miglioramento continuo → si possono apportare aggiornamenti migliorativi localmente ad un livello, senza intaccare il funzionamento degli altri. L’architettura a livelli deve prevedere delle interfacce che permettano lo scambio di dati tra un livello e un altro. I computer sfruttano questo tipo di architettura e il sistema operativo (SO) è un livello di essa. Precisamente il SO si frappone tra l’hardware e le applicazioni (a livello utente, user land ). Un generico modello per rappresentare l’architettura di un computer è il modello di Von Neumann. Esso prevede la presenza di: 1. CPU (Central Processing Unit) → unità centrale che esegue le istruzioni dei programmi. Essa si suddivide poi in: ALU (Arithmetic Logic Unit) e CU (Control Unit); 2. memoria condivisa (RAM) → locazione delle istruzioni e dei dati su cui esse operano; 3. periferiche di input e output. In questo modello esiste il concetto di flusso d’esecuzione delle istruzioni, il quale caratterizza l’ordine con cui esse vengono eseguite dalla CPU. Questo flusso è implementato tramite il registro PC (program counter) che punta all’indirizzo in memoria della prossima istruzione da eseguire. Il flusso d’esecuzione può essere alterato tramite istruzioni di jump e branch. L’esecuzione dell’istruzione non è atomica, o meglio ogni istruzione ha un suo ciclo di vita caratterizzato da: 1. fetch → l’istruzione presente in memoria all’indirizzo contenuto in PC viene prelevata e caricata nell’IR (Instruction Register) che contiene appunto l’istruzione da eseguire adesso; 2. decode → l’istruzione viene analizzata e vengono caricati gli operandi necessari nei registri di lavoro della CPU (ad esempio EAX, EBX); 3. execute → l’istruzione viene eseguita; 4. write-back → viene memorizzato il risultato dell’istruzione e vengono aggiornati i registri (PC++). La CPU inoltre possiede uno stato caratterizzato dal valore di tutti i suoi registri in un dato istante di tempo. Riportare la CPU in un certo stato significa settare i registri ai valori caratterizzanti lo stato stesso. Le periferiche di input/output previste dalla macchina di Von Neumann comunicano con CPU e memoria tramite collegamenti chiamati bus. Esistono 3 tipi di bus principali (il ruolo è autoesplicativo): bus dati; bus indirizzi; bus controllo; 1.1 Interrupt L’utilizzo di dispositivi esterni per comunicare col computer comporta la necessità di implementare un meccanismo di gestione eventi. Si prenda come esempio la tastiera (dispositivo di input). Il SO per gestire l’evento di digitazione tramite tastiera genera un’interrupt. Definiamo quindi interrupt come un segnale asincrono noto che viene trasmesso dal dispositivo alla CPU tramite un’interrupt request line. Il segnale è asincrono perché può essere generato in qualsiasi momento da un dispositivo esterno al computer (inteso come macchina di Von Neumann, ovvero CPU + memoria). Poichè come affermato le interrupt sono note, ad ognuna di esse viene associato una linea che prende il nome di interrupt request line (IRQ) ; ogni interrupt e di conseguenza la IRQ associata sono numerate. Quando viene sollevata un’interrupt (e il segnale si propaga fino alla CPU tramite la IRQ) la CPU interrompe l’esecuzione del programma corrente per gestire l’evento (in realtà non è sempre detto che la gestione avvenga immediatamente, vedi dopo). Le fasi di gestione di un’interrupt sono: 1. la CPU nota che la IRQ j_esima è attiva → l’interrupt numero j è stata generata; 2. la CPU legge il vettore IVT (Interrupt Vector Table) per prelevare l’indirizzo del codice utile a gestire l’interrupt j_esima. L’indirizzo dove individuare questo codice è contenuto nella cella IVT[j]; 3. la CPU memorizza lo stato corrente del programma in esecuzione. In questo modo una volta terminata la gestione dell’interrupt la sua esecuzione potrà riprendere in modo corretto; 4. la CPU modifica il registro PC ponendolo pari a IVT[j] (vedi fase 2); 5. la CPU esegue adesso il codice per la gestione dell’interrupt j_esima. Questo codice prende il nome di Interrupt Service/Handler Routine (ISR). Ogni interrupt possiede quindi anche una ISR diversa e specifica. Poichè l’insieme degli eventi è eterogeneo, ognuno necessita di una gestione specifica. Inoltre gli eventi si differenziano anche per la loro importanza. Precisamente possiamo categorizzare i vari tipi di interrupt in: interrupt maskable (mascherabili) → rientrano in questa categoria le interrupt che possono essere ignorate. Attenzione, ignorare non significa che esse non verranno mai gestite. Le ISR associate a questo tipo di interrupt possono essere eseguite anche in un momento successivo alla loro sollevazione; non forzano quindi l’interruzione del programma corrente sulla CPU; interrupt unmaskable (non mascherabili) → insieme complementare del precedente. Queste interrupt, appena sollevate, devono essere gestite e non possono essere ignorate. Il meccanismo di mascherare delle interrupt è utile per garantire che l’esecuzione di una certa routine (anche una ISR) non venga interrotta dal verificarsi di eventi “non critici”. 1.2 Trap Abbiamo quindi detto che le interrupt sono segnali asincroni e vengono gestiti mediante l’esecuzione della ISR associata. Un meccanismo simile a quello delle interrupt viene implementato mediante le trap. Queste ultime sono segnali sincroni che vengono generati durante il flusso di esecuzione di un programma (l’esempio classico è quello di una system call o di un page fault, vedi dopo). 1.3 Eccezioni Anche le eccezioni sono simili per natura alle interrupt e le trap. Sono segnali sincroni che vengono generati da errori nel flusso di esecuzione di un programma, che necessitano la gestione da parte del sistema operativo. 1.4 Memoria di un computer Come già visto, la CPU necessita di comunicare con la memoria tramite i bus. La scrittura/lettura dei dati dalla memoria è un’operazione onerosa per la CPU (in termini di cicli di clock impiegati). Pertanto nei computer si installa un dispositivo che prende il nome di DMA (Direct Memory Access) il quale esegue le operazioni di scrittura/lettura con la memoria, al posto della CPU (che può quindi continuare ad eseguire il programma caricato su di essa). La CPU comunica al DMA il puntatore di origine dei dati, quello di destinazione e la dimensione dei dati in oggetto. DMA e CPU comunicano tramite un bus ad accesso esclusivo, ovvero può essere utilizzato solo da un dispositivo alla volta. Le modalità di funzionamento del DMA possibili sono 3: burst transfer → il controllo del bus rimane al DMA durante tutta la durata del trasferimento; transparent → il DMA esegue trasferimenti sul bus solo se la CPU non ne ha bisogno (quando sta eseguendo un’istruzione abbastanza lungo);  cycle stealing → il controllo del bus è della CPU. Il DMA ne prende possesso per un ciclo quando i dati sono pronti al trasferimento (il trasferimento può richiedere più cicli, quindi l’accesso al bus è frammentato). Il DMA è quindi un controller che può scrivere direttamente in RAM. La provenienza dei dati può anche essere una periferica. Inoltre la memoria presente in un computer è organizzata secondo una scala gerarchica piramidale. Alla punta della piramide troviamo la CPU e man mano che si scende la distanza da essa aumenta. Precisamente: più siamo vicini alla CPU, allora la velocità della memoria è maggiore ma la sua dimensione è minore; più siamo lontani dalla CPU, allora la velocità della memoria è minore ma la sua dimensione è maggiore; Si implementa quindi il meccanismo di caching il quale prevede il mantenimento dei dati nella memoria più vicina alla CPU, a seconda della frequenza con cui quel dato viene utilizzato dalla CPU stessa. Si parla di hit ratio come la probabilità di individuare un dato nella memoria cache. 1.5 Multiprocessing e multitasking Questi due concetti sono simili ma totalmente diversi: multiprocessing → il sistema operativo è in grado di eseguire più programmi (dal punto di vista hardware), de-schedulando un determinato processo quando è in attesa di operazioni I/O; multitasking → il sistema operativo esegue più programmi (dal punto di vista software) dando l’illusione che essi vengano eseguiti in contemporanea; il sistema operativo deschedula un processo ogni periodo di tempo definito, scandito da un timer (si genera un’interrupt). 1.6 Modalità di esecuzione Il codice che la CPU deve eseguire non sempre ha la stessa rilevanza. Precisamente, ci sono delle porzioni di codice che possono essere malevoli o causare errori critici. Pertanto è necessario l’implementazione di un meccanismo di sicurezza, basato su permessi. Questo meccanismo è organizzato a livelli. I livelli importanti sono due: kernel mode → il codice che deve essere eseguito in questa modalità deve essere fidato. Pertanto in kernel mode si esegue esclusivamente il codice del sistema operativo; user mode → il codice di un programma utente viene eseguito in questa modalità. Per identificare la modalità con cui la CPU lavora si associa un numero (chiamato anche ring). Il numero dipende dalla specifica architettura del processore. Anche se un programma inizia la sua esecuzione in user mode, è possibile che debba eseguire porzioni di codice in kernel mode. Questo accade, ad esempio, quando il programma effettua una system call. Per far sì che il processo cambi modalità di privilegio nell’esecuzione, viene sollevata una trap (modifica il valore del mode_bit). 2. STRUTTURE DEL SISTEMA OPERATIVO E SYSTEM CALL Come già visto il sistema operativo è il layer che si frappone tra l’hardware e le applicazioni utente. Pertanto deve fornire delle interfacce di comunicazione con questi livelli. Precisamente: per il livello utente fornisce dei programmi utili all’utilizzo del computer (file explorer, …) e inoltre fornisce delle API (Application Program Interface) per l’utilizzo di specifiche procedure (system calls). Le system calls implementano operazioni per la gestione dei dispositivi (scrittura/lettura su un file) , per la comunicazione tra vari processi anche attraverso la rete … Per far questo è necessario che il SO definisca un’interfaccia che funga da wrapper tra le API a livello utente e le system calls reali (un esempio è POSIX);  nella comunicazione con l’hardware il sistema operativo svolge il compito di astrarre i vari componenti fisici del computer. Poiché è necessario comunicare con l’hardware i sistemi operativi implementano le ABI (Application Binary Interface) che vanno a definire le strutture dei file eseguibili e come essi devono essere eseguiti; Inoltre è necessario implementare un insieme di istruzioni che la CPU possa eseguire; questo insieme prende il nome di ISA (Instruction Set Architecture). 2.1 System calls Le system calls sono porzioni di codice che implementano diverse funzionalità. Sono offerte direttamente dal sistema operativo ed è codice fidato. Le system calls (“reali”) devono essere eseguite in kernel mode. Pertanto è necessario un meccanismo che permetta lo switch di modalità di privilegio durante l’esecuzione. Precisamente: un programma lato utente (scritto ad esempio in C) contiene la chiamata ad una funzione che è ‘wrappata’ ad una system call; in fase di compilazione, questa chiamata viene sostituita con il codice macchina (istruzioni contenute nell’ISA) che andrà a lanciare la systemcall, mediante l’istruzione syscall; durante l’esecuzione del programma, tramite file eseguibile la cui struttura è definita nelle ABI del SO (ad esempio formato ELF in Linux), una volta giunti alla syscall vi è lo switch di privilegio da user mode a kernel mode; in kernel mode viene eseguito il codice della system call fornito dal SO; terminata la system call si ritorna alla modalità utente e si riprende l’esecuzione del programma da dove si era interrotto. Un aspetto importante del meccanismo relativo alle system calls è il passaggio dei parametri. Vi sono due modalità di implementazione: porre il valore dei parametri nei registri del processore (se bastano). Linux sfrutta questa modalità quando il numero dei parametri è massimo 5; porre i parametri in una regione di memoria e porre in un registro del processore l’indirizzo dove inizia questa regione. Altro aspetto importante è come avviene il cambio di contesto dal programma utente al codice della system call eseguito in kernel mode. Tutto avviene all’invocazione dell’istruzione syscall: il kernel del SO memorizza il valore del PC (Program Counter, o RIP) nel registro RCX in modo che una volta terminata la syscall si rinizi ad eseguire lato utente dalla prima istruzione successiva alla syscall; per eseguire la system call in PC viene posto l’indirizzo di partenza comune ad ogni syscall. Questo indirizzo è contenuto nel registro IA32_LSTAR MSR; terminato il codice la system call (codice kernel) esegue l’istruzione sysretq e si ritorna alla user mode ripristinando il valore PC con quello contenuto in RCX; L’istruzione syscall non permette di specificare quale system call in realtà vada eseguita. In realtà le varie system call sono numerate e il numero corrispondente a quella da eseguire va posto preliminarmente nel registro RAX del processore. Ogni SO dispone di una propria tabella delle system call, dove vi è specificato il numero associato ad ognuna. 2.2 Boot La fase di boot è la prima fase attraversata dal computer e inizia all’accensione. Questa fase prevede: set del PC all’indirizzo di memoria EEPROM (memoria non volatile) dove è presente l’inizio del BIOS/UEFI; l’UEFI legge la GPT (Grid Partition Table) per individuare sul disco il bootstrap program (analogamente il BIOS legge la MBR (Master Boot Record));  il bootstrap program (grub) carica il SO in RAM. Poiché durante l’avvio del SO non è ancora disponibile un filesystem ne viene creato uno temporaneo (initramfs) ad utilizzo del kernel; terminato l’avvio del SO quest’ultimo lancia il processo systemd (system daemon) da cui partono tutti gli altri processi. 2.3 Kernel design Il kernel (traduzione nucleo) è il core centrale del SO e svolge le funzioni più critiche di esso. Riguardo le funzionalità implementate dal kernel è necessario effettuare una divisione sul design del kernel stesso. Esistono 3 tipi di approcci principali: kernel monolitico → il kernel implementa tutte le funzionalità le quali vengono eseguite in kernel mode. E’ un grande programma binario unico. I vantaggi di questo approccio sono le elevate performance ma d’altra parte rende lo sviluppo e la manutenzione più complessa; microkernel → il kernel implementa poche funzionalità (quelle strettamente necessarie al funzionamento della macchina), mentre tutte le altre vengono eseguite in user mode. Il vantaggio di questo approccio è la facilità di sviluppo ma poiché è necessaria comunicazione del kernel con i processi esterni al kernel, le performance si riducono; approccio ibrido → unione dei due approcci scegliendo in fase di design le funzionalità che devono essere eseguite e inglobate all’interno del kernel. Inoltre questo approccio prevede l’utilizzo di moduli che possono essere caricati (durante il boot o durante il funzionamento del SO) nello spazio d’indirizzamento del kernel. 2.4 Virtualizzazione La virtualizzazione (affrontata successivamente) è una serie di tecnologie e meccanismi che permettono l’esecuzione simultanea di più sistemi operativi sulla stessa macchina, contemporaneamente. La virtualizzazione viene implementata mediante l’utilizzo di speciali software che prendono il nome di hypervisor. La virtualizzazione prevede l’astrazione dell’harwdare del computer (CPU, memoria, periferiche) facendo credere ad ogni SO di girare direttamente sulla macchina. Quando un hypervisor deve cambiare anche l’ISA del processore, ovvero quando il SO crede di sfruttare una CPU diversa da quella reale, prende il nome di emulatore. Esistono due principali tipi di virtualizzazione: Tipo 1 → l’hypervisor si frappone fra hardware e i vari SO che girano in contemporanea; Tipo 2 → l’hypervisor è un programma eseguito sul SO che si interfaccia con l’hardware. I SO virtuali (guest) sono posti nella pila sopra l’hypervisor. Le performance del tipo 2 sono sicuramente peggiori del tipo 1, inoltre il malfunzionamento del SO reale comporta la propagazione del ‘guasto’ su tutti quelli guest. Il vantaggio del tipo 2 è la facilità d’utilizzo. 3. PROCESSI La classica definizione di processo è quella di un programma in esecuzione. In un sistema multiprogramming, che quindi permette l’esecuzione simultanea di più programmi sullo stesso hardware, esistono nello stesso instante di tempo più processi. Poiché sulla CPU può girare un singolo processo alla volta, è necessario introdurre il meccanismo di interleaving di un processo. L’interleaving è quel meccanismo mediante il quale un processo può essere in esecuzione sulla CPU o meno ed è il SO a gestire quale processo va eseguito in un determinato istante di tempo. La scelta avviene in corrispondenza di specifici eventi: scadenza di un timer, richiesta di I/O bloccante … Il meccanismo di interleaving aggiunge all’esecuzione di un processo una proprietà di non determinismo, in quanto non è possibile stabilire a propri quanto tempo il processo occuperà la CPU. Il tempo di esecuzione di un processo è quindi influenzato dalle scelte del SO che si basano anche sul comportamento degli altri processi presenti sulla macchina. Inoltre è importante considerare che un processo, se interrotto, alla sua ripresa deve riprendere come se l’interleaving non esistesse. 3.1 Memoria di un processo Quando un programma viene eseguito e quindi diventa un processo, il SO alloca della memoria RAM utile all’esecuzione del processo stesso. Il SO ha la responsabilità della gestione della RAM, in quanto questo fattore influisce su quanti processi possono essere eseguiti contemporaneamente. Grazie al meccanismo di virtualizzazione della memoria, ogni processo ‘crede’ di avere a disposizione l’intera memoria RAM; questo è utile ad impedire che un processo acceda erroneamente all’area di memoria destinata ad un altro processo (fattore di sicurezza). L’area di memoria per un singolo processo può essere raffigurata come di fianco (in realtà la RAM non viene allocata contiguamente, ma secondo il meccanismo della paginazione). Questa rappresentazione è solamente logica, non reale. Le regioni presenti sono: stack → regione di memoria (che può crescere verso il basso) dove vengono caricate le funzioni attualmente in esecuzione dal programma. All’interno di questa regione vi è anche il riferimento alle memorie condivise utilizzabili dai vari processi (ad esempio libc); heap → (traduzione spazzatura), memoria utilizzabile dal processo dinamica. Ovvero è possibile allocarla/deallocarla su esigenza (in C accade con malloc e free); bss → regione in cui vengono poste le variabili non inizializzate; data → regione dove vengono allocati i dati statici (ad esempio una stringa “ciao”); code → immagine binaria di un processo (codice assembly che rispetta l’ISA della CPU). E’ importante notare che lo stack cresce ‘verso il basso’. Ogni volta che viene chiamata una funzione (si pensi proprio al codice scritto in C/C++) viene allocata porzione dello stack. Il SO per ogni processo deve mantenere i limiti superiori e inferiori dei vari frame dello stack afferenti a funzioni diverse. Precisamente questi limiti prendono il nome di EBP e ESP. Quando una nuova funzione viene allocata succede che: il sistema operativo crea un nuovo frame ponendo all’inizio l’indirizzo di ritorno (per riprendere l’esecuzione della funzione chiamante al punto giusto) e il vecchio EBP; aggiorna il valore di EBP e ESP; eseguita la funzione in testa (pensare ad un uomo al contrario per capire la testa) ripristina EBP e ESP (ricordarsi la pila delle chiamate a funzione vista a TdP). Durante l’interleaving è necessario memorizzare i valori di EBP e ESP, per riprendere l’esecuzione del processo dal giusto punto della giusta funzione. 3.2 PCB (Process Control Block) Il sistema operativo per gestire i vari processi che girano simultaneamente memorizza in RAM (nell’area kernel non scrivibile e leggibile da processi utente) una struttura per ognuno di essi che prende il nome di PCB. In sintesi il PCB contiene le seguente informazioni: pid (process identificator) del processo; informazioni sullo stato del processo (vedi paragrafo successivo); lista dei descrittori di file aperti dal processo; altre info sulla gestione memoria e scheduling (priorità del processo ad esempio …). Fare riferimento al paragrafo sul context switch perché il PCB riserva particolare importanza. 3.3 Ciclo di vita di un processo Il processo prima di terminare la sua esecuzione può attraversare varie fasi. Queste fasi sono rappresentate nel seguente diagramma (disegnato da me :-)): Si noti un aspetto molto importante, ovvero che il processo appena creato non viene caricato sulla CPU ma è pronto ad essere eseguito. Il SO ha l’onere di dover decidere quando deschedulare un processo. Per far si che il meccanismo di interleaving venga implementato correttamente è necessario che il processo riprenda da dove si era fermato. Oltre quindi a memorizzare il valore di EBP e ESP è necessario memorizzare il PCB del processo in oggetto. Queste operazioni preliminari al processo prendono il nome di context switch (cambio di contesto) e sono istruzioni che il sistema operativo esegue (quindi occupa CPU) generando overhead, poiché non afferiscono a nessun processo utente. Pertanto l’overhead introdotto dal context switch (utilizzo ‘inutile’ della CPU) va ridotto al minimo. N.B: il context switch non va confuso con quanto accade per le syscall. Nelle syscall vi è un cambio di modalità di privilegio ma il processo rimane sempre lo stesso. Altro aspetto importante sull’utilizzazione della CPU lo riveste il grado di multiprogrammazione. Introduciamo due concetti caratterizzanti un processo: il processo è CPU bound se la maggior parte del tempo di esecuzione è impiegato nell’esecuzione di istruzioni della CPU; il processo è I/O bound se la maggior parte del tempo di esecuzione è impiegato per risolvere richieste di input/output. L’utilizzazione della CPU dipende fortemente dalla tipologia di processi in esecuzione. Aumentando il grado di multiprogrammazione la CPU risulta essere sfruttata al massimo se la maggior parte dei processi sono CPU bound, altrimenti molto tempo viene impiegato nell’attesa di varie richieste I/O. Nella rappresentazione precedente è dato per scontato che un processo venga creato e quindi caricato in memoria. La RAM non sempre permette ad un nuovo processo di essere caricato. Per questo esiste il meccanismo dello swapping (ormai obsoleto poiché le dimensioni delle RAM sono nell’ordine di decine di GB). Con questo meccanismo un processo in memoria può essere direttamente spostato in un’area del disco fisico, per liberare spazio ad un altro processo; un processo appena creato può essere direttamente ‘swappato’. Tenendo conto di questa possibilità il ciclo di vita diviene: Il motivo per cui un processo entra nello stato di waiting è una richiesta di I/O che non può essere evasa e comporta il blocco del processo. Il processo viene quindi tolto dalla CPU che altrimenti sarebbe inutilizzata (in IDLE). Poiché le richieste di I/O possono essere di molteplici tipi, a seconda del dispositivo periferica coinvolto il SO mantiene nel suo spazio di indirizzamento liste di PCB per tipo di richiesta dei processi in waiting. In questo modo sa in minor tempo quale processo sbloccare, poiché riconosce la periferica attraverso l’interrupt che essa genera (e non perde tempo ad analizzare processi la cui richiesta non è soddisfatta). Mostriamo adesso gli stati previsti dal kernel Linux: 3.4 Creazione e terminazione di un processo Abbiamo visto che un processo ha sempre associato un PCB gestito dal SO. All’interno del PCB è contenuto il process identificator, che prende il nome di pid del processo. Abbiamo inoltre visto che alla fine del processo di boot, il SO si avvia sempre con il processo systemd (o init in alcune distribuzioni di Linux). Il processo systemd ha sempre associato pid = 1. Tutti i processi attivi su una macchina sono figli di systemd. Precisamente: il SO gestisce i processi in una struttura gerarchica (albero) in cui ogni processo ha un padre, tranne systemd; ogni processo che ne genera un altro ottiene un figlio. Il figlio eredita delle proprietà dal padre, ad esempio i descrittori dei file che il padre utilizza. Queste proprietà possono essere specificate dal padre e compongono il grado di ereditarietà. Alla terminazione di un processo il SO deve: rilasciare le risorse in uso dal processo; nel rilascio delle risorse attuare i cambiamenti, ad esempio sui file (operazione di flush);  rilasciare la RAM allocata per il processo. Come si crea un processo? Nel linguaggio C/C++ è possibile in queste due modalità: 1. mediante system call fork() → questa system call copia l’intera aerea di memoria del processo chiamante e la duplica in un processo figlio. Il figlio eredita quindi tutti i descrittori dei file aperti dal padre e inizia la sua esecuzione dall’istruzione immediatamente successiva alla fork(). La funzione restituisce il pid del figlio al padre e al figlio 0. E’ importante notare che la memoria del processo è duplicata, quindi eventuali modifiche effettuate da padre/figlio non modificano l’area del figlio/padre; 2. mediante system call exec..() → questa system call sostituisce l’area di memoria del processo chiamante con quella del processo il cui nome è passato come parametro. Il processo rimane il medesimo, con lo stesso pid. Per i dettagli sui parametri vedere il manuale. Esistono diverse alternative di exec: ◦ il passaggio dei parametri al nuovo processo può avvenire mediante una lista di parametri (l) o un vettore (v); ◦ il nuovo processo può girare in un ambiente diverso (e); ◦ il nuovo processo valuta i percorsi anche nelle directory contenuto nella variabile d’ambiente PATH (p). Dalle due alternative nasce quindi il problema di generare un nuovo processo, diverso dal padre, che non si sostituisca al padre stesso. Per effettuare ciò: si genera un processo figlio mediante la fork(); nel figlio (porzione di codice identificabile mediante il tipo di ritorno della fork()) si esegue la exec() per sostituire il codice. 4. Thread Abbiamo visto che in un sistema multiprogramming è possibile avere più processi in esecuzione sul medesimo hardware. Abbiamo inoltre studiato come creare un nuovo processo, e abbiamo visto che l’operazione è complessa: è necessario duplicare l’area di memoria del processo padre; è necessario sostituire l’area di memoria del processo figlio con l’area del processo richiesto. Queste fasi introducono molto overhead pertanto non è sempre la soluzione migliore. I sistemi moderni supportano il meccanismo dei thread. Ogni processo può possedere più thread, ovvero più flussi di esecuzione sulla CPU. I thread afferiscono quindi allo stesso processo e sono simili per natura ai processi stessi (ma più ‘leggeri’). Un thread possiede degli stati: ready; wait; running. I vantaggi dell’utilizzo dei thread sono: meno overhead in fase di creazione; aumento del grado di parallelismo. Il processo può eseguire più attività contemporaneamente; i thread, poiché afferiscono allo stesso processo, condividono l’area di memoria del processo stesso. Pertanto le modifiche effettuate da un thread sono visibili ad un altro thread dello stesso processo. L’utilizzo della stessa area di memoria è un vantaggio poiché evita la necessità di far comunicare processi diversi (tramite IPC, capitolo successivo). Introduce però il grande svantaggio associato ai problemi della sincronizzazione. Possiamo dividere il concetto di parallelismo in due: task level parallelism → ogni thread di un processo esegue un compito diverso;  data level parallelism → ogni thread di un processo esegue lo stesso compito su partizioni di dati diverse. I thread possono essere implementati secondo diverse tecniche. Precisamente esistono: many_to_one (green threads) → i flussi di esecuzione sono a livello utente. Sulla CPU esiste un unico flusso di esecuzione (a livello kernel). Non vi è quindi del vero parallelismo, ma concorrenza tra i thead; one_to_one → ogni flusso del processo è mappato su un thread lato kernel, e quindi esiste per ogni thread un flusso di esecuzione reale sulla CPU; many_to_many → più flussi di esecuzione vengono mappati su unico flusso lato kernel, e di quest’ultimi ne esistono molteplici. Tramite il linguaggio C/C++, in Linux, è possibile implementare i kernel thread mediante la libreria pthread (POSIX Thread). 5. IPC (InterProcess Communication) E’ utile che i SO introducano la comunicazione tra processi in quanto: può essere sfruttata per scrivere applicazioni articolate in più programmi che cooperano tra loro, comunicando; può essere sfruttata per ottenere informazioni sullo stato di altri processi attivi. La comunicazione tra processi può avvenire secondo tre modalità: by shared memory → i processi condividono una porzione di RAM dove possono scrivere e leggere. Un vantaggio di questo approccio è l’indipendenza dal kernel, il quale non è costretto ad intervenire durante la comunicazione (ma solo a creare e inizializzare l’area di memoria convidisa); by messagge → i processi comunicano scambiando messaggi; è necessario quindi l’intervento del kernel che deve offrire lo scambio di messaggi tra i vari processi; by stream → i processi comunicano inviando un flusso di dati ad altri processi. L’esempio classico sono le socket o le pipe. 5.1 Shared memory Come detto la comunicazione avviene tramite una regione di memoria condivisa. Poiché condivisa nasce un problema di sincronizzazione in quanto non deve accadere che più processi tentino di scrivere la stessa locazione di memoria nello stesso istante di tempo. Un problema noto nell’utilizzo delle shared memory è quello del produttore/consumatore. In questo scenario vi sono due processi: produttore → processo che produce i dati; consumatore → processo che legge i dati prodotti; I dati sono quelli da scrivere nella memoria condivisa e pertanto è necessario che il consumatore non tenti di leggere un dato che non è ancora stato prodotto. Dividiamo due situazioni: l’area di memoria condivisa è infinita (situazione ideale) → solamente il consumatore aspetta che il produttore abbia generato un dato; l’area di memoria condivisa è finita (situazione reale) → il consumatore deve aspettare il produttore per la generazione dei dati, ma anche il produttore deve aspettare che il consumatore legga un dato per evitare di sovrascrivere (e quindi perdere) un dato ancora ‘non consumato’. Nella situazione reale è possibile risolvere il problema mediante queste porzioni di codice:  produttore → consumatore → 5.2 Message passing Questo paradigma di comunicazione prevede lo scambio di messaggi tra più processi (ovviamente almeno 2 :-|). Poiché necessita dell’intervento del kernel per far avvenire lo scambio dei messaggi risulterà sicuramente un metodo meno performante rispetto alla shared memory; nonostante ciò è più facile da utilizzare poiché non introduce problemi di sincronizzazione. Una tecnologia IPC deve sicuramente implementare due primitive: send() → usata per l’invio di un messaggio; receive() → usata per la ricezione di un messaggio. E’ importante precisare che in questo tipo di comunicazione i messaggi hanno una struttura e dimensione ben definita (specificata quindi in un protocollo di comunicazione tra processi). La comunicazione tramite messaggi può essere: diretta → per instaurare la comunicazione è necessario conoscere mittente e destinatario. Esiste un’ulteriore suddivisione per la diretta: ◦ simmetrica → la send ha questa struttura send(msg, P) in cui P è destinatario. La receive ha questa struttura receive(msg, Q) in cui Q è mittente (specificato); ◦ asimmetrica → la send ha questa struttura send(msg, P) in cui P è destinatario. La receive ha questa struttura receive(msg, &mitt) in cui mitt conterrà l’identità del mittente (non specificato, l’importante che il messaggio sia arrivato al giusto destinatario); indiretta → un processo invia un messaggio senza specificare il destinatario. Viene introdotta quindi una mailbox che può contenere uno o più messaggi. Non è quindi noto a priori da chi verrà consumato un certo messaggio. Nel caso di comunicazione by message indiretta nasce un problema di sincronizzazione sull’utilizzo della mailbox. Precisamente, va gestita la situazione in cui più processi tentino di ricevere lo stesso messaggio. Le soluzioni per risolvere il problema sono 3: per ogni mailbox può esservi solo un processo che effettua la receive();  la primitiva di receive() può essere eseguita da un solo processo alla volta(); se più processi eseguono la receive() nello stesso momento è il SO a gestire l’inoltro del messaggio ad un singolo processo tra i suddetti. La comunicazione tramite messaggi può essere: sincrona → se sincrona da parte del mittente allora la send è bloccante, ovvero il mittente attende che qualcuno riceva un certo messaggio. Se sincrona da parte del destinatario allora la receive è bloccante, ovvero il destinatario attende di poter consumare un messaggio; asincrona → se asincrona da parte del mittente allora la send ritorna subito, senza verificare che il messaggio abbia raggiunto il destinatario (o la mailbox). Se asincrona da parte del destinatario allora la receive ritorna subito, ovvero un processo consuma il messaggio solo se disponibile (dovrà quindi rieseguire la receive in caso non sia presente un messaggio). Un ulteriore aspetto importante sulla comunicazione tramite messaggi è la bufferizzazione dei messaggi. Esistono tre possibilità: no buffer → il mittente è costretto ad attendere che un processo riceva il messaggio; buffer con capacità limitata → quando il mittente cerca di inviare un messaggio che eccede dallo spazio disponibile del buffer, deve attendere che un processo crei spazio (deve leggere almeno un messaggio già presente nel buffer); buffer con capacità illimitata → situazione analoga il precedente, in cui non accade mai che il mittente trovi il buffer pieno (situazione puramente ideale). 5.3 By stream La comunicazione tramite stream di dati avviene su un link di comunicazione che di solito è un file condiviso. Non vi è quindi un limite superiore sulla dimensione e quantità di dati condivisi tra i processi. E’ la tecnica utilizzata dalle pipe e socket (queste ultime permettono la comunicazione tra processi che risiedono su macchine diverse, tramite la rete). 5.4 Accoppiamento/Disaccoppiamento spaziale e temporale Introduciamo questi due concetti che caratterizzano una comunicazione, a prescindere dalla tecnologia sfruttata. Parliamo di: accoppiamento spaziale → se per eseguire la comunicazione è necessario conoscere sia l’entità del mittente che del destinatario; disaccoppiamento spaziale → se per eseguire la comunicazione non è definita l’identità del destinatario; Parliamo di: accoppiamento temporale → se per eseguire la comunicazione è necessario che mittente e destinatario del messaggio esistano contemporaneamente; disaccoppiamento temporale → se per eseguire la comunicazione non è necessario che mittente e destinatario del messaggio non esistano contemporaneamente. 5.5 Interfacce POSIX Per creare una shared memory, in Linux esistono due possibilità: mediante le funzioni shm_open(), shm_unlink(), ftruncate(), nmap(). Servono rispettivamente a creare una shared memory (file in /dev/shm), distruggere una shared memory, dimensionare una shared memory e mappare la shared memory nello spazio di indirizzamento del processo chiamante; mediante le funzione della System V API: shmget() e shmdt(). Per creare una message queue in Linux si utilizzano le seguenti funzioni: ftok() → per ottenere un codice identificativo da utilizzare per individuare la coda; msget() → per creare o ottenere l’accesso alla coda;  msgrcv() e msgsnd() → per ricevere/inviare messaggi attraverso la coda; Riguardo la comunicazione by stream, fare riferimento alle socket nella parte di Reti. 5.6 Segnali I segnali sono un’ulteriore modalità di IPC. E’ importante conoscere questa modalità poiché è quella utilizzata dal SO per comunicare con i processi. I segnali sono associati a eventi definiti e noti; ad ogni segnale è associato un nome e un numero, ad esempio SIGKILL ha il numero 9. Un segnale può essere: sincrono → generato dal flusso di esecuzione del programma, ad esempio quando si cerca di accedere a porzioni di RAM non del processo, viene inviato il segnale SIGSEGV; asincrono → generato da un evento esterno al processo, ad esempio quando si cerca di interrompere un processo con CTRL+C viene inviato il segnale SIGINT. Un processo, una volta giunto il segnale può: ignorarlo implicitamente → se previsto il kernel eseguirà delle azioni di default; ignorarlo esplicitamente → non verrà eseguita nessuna azione; gestirlo → è possibile definire una routine per la gestione dei segnali variando il comportamento a seconda del tipo. La gestione viene effettuata mediante la funzione signal(..) inclusa nella libreria C/C++ signal.h. Un processo può inviare un segnale ad un altro processo mediante la funzione kill(). Questa system call è analoga al comando eseguibile da bash: kill -NUM_SEGNALE pid_processo_dest. I segnali possono essere: bloccati → mediante funzione sigprocmask(). Questa opportunità non è valida per tutti i segnali (ad esempio SIGKILL). Quando un segnale viene bloccato viene inserito dal kernel in una coda (di segnali) da consegnare a quel processo. E’ il kernel a decidere l’ordine in cui i segnali della coda andranno consegnati al processo, una volta che essi saranno sbloccati (può non avvenire mai lo sblocco). Se lo stesso segnale si ripete mentre è bloccato, nella coda sarà presente una singola istanza del segnale in oggetto, e verrà quindi gestito una singola volta (se il programma ha definito un handler). Un processo, se generato tramite fork, eredita i vari comportamenti di gestione segnali (ignorati, bloccati, gestiti). Quando invece un processo viene avviato a seguito di una exec eredita solo quelli ignorati e comportamenti di default (gli handler non fanno parte del codice del processo). Un processo può ricevere un segnale quando è in stato di waiting a causa di una system call bloccante (sincrona). Al suo risveglio viene sicuramente eseguito l’handler del/dei segnali, se presente. La system call viene terminata dal kernel, ed esistono due conseguenze (in base all’implementazione del SO): la system call restituisce -1 al chiamante, quindi l’handler deve controllare il suo esito ed eventualmente rieseguirla; la system call dopo essere terminata, viene rieseguita in automatico dal SO (meccanismo supportato da Linux). Un processo può ricevere un segnale mentre è deschedulato. La gestione di quest’ultimo avverrà quando il processo ritorna nello stato running. Durante l’esecuzione dell’handler il processo può essere deschedulato e quindi interrotto; in queste ipotesi, se giunge al processo un nuovo segnale, appena il processo ritornerà in esecuzione eseguirà una nuova istanza dell’handler (per poi terminare quella vecchia, interrotta dalla deschedulazione). Questo meccanismo può causare problemi se l’handler è una routine non rientrante. Parliamo di non rientranza quando, sotto queste ipotesi, la semantica associata a strutture dati globali può essere corrotta; pertanto è necessario che gli handler siano strettamente rientranti. Per garantire la rientranza esistono due soluzioni: all’interno dell’handler devono essere eseguite esclusivamente funzioni rientranti (ovvero che non operano su strutture dati globali). Non rientrano in questa categoria funzioni come la malloc; bloccare tutti i segnali prima di ogni chiamata a funzione non rientrante. A causa della complessità dei programmi, la seconda soluzione risulta essere impraticabile. 6. Scheduling Abbiamo visto che un processo attraversa durante la sua vita più stati. Quando un processo è in ‘running’ non è detto che termini la sua esecuzione perché può essere deschedulato. Quando un processo è deschedulato può finire nello stato: waiting → a causa di una richiesta I/O; ready. Ci si occupa della seconda casistica parlando di short term scheduling. Il dispatcher è un componente del SO che si occupa di eseguire il context switch tra processi, seguendo le istruzioni ricevute dallo scheduler. Lo scheduler è il componente del SO che stabilisce quale processo debba essere eseguito sulla CPU in un dato istante, secondo gli algoritmi di scheduling. Gli algoritmi vengono sviluppati cercando di massimizzare il guadagno nei termini espressi da queste metriche: utilizzo della CPU (metrica di sistema) → si cerca di massimizzare il tempo di utilizzo della CPU nell’esecuzione di istruzioni di user process; throughput (metrica di sistema)→ si cerca di massimizzare il numero di processi utenti eseguiti (e terminati) nell’unità di tempo; turn_around time (metrica di processo)→ si cerca di minimizzare l’intervallo di tempo che intercorre tra l’avvio del processo e la sua terminazione; waiting time (metrica di processo) → si cerca di minimizzare l’intervallo di tempo che un processo attende per essere rischedulato sulla CPU. Si noti che, dalle definizioni, alcune metriche sono in competizione tra loro (cercando di migliorarne una, se ne peggiora un’altra). Per questo motivo si cerca un compromesso nello sviluppo degli algoritmi. Gli algoritmi di scheduling possono essere con: prelazione → il processo può essere deschedulato per scelta del SO e finire nello stato di ready; senza prelazione → il processo può essere deschedulato solo alla terminazione o quando è in attesa di evento (richiesta I/O oppure altro). In quest’ultimo caso va nello stato di waiting; Per valutare i vantaggi/svantaggi degli algoritmi di scheduling è necessario introdurre i concetti di: CPU burst → si verifica quando un processo esegue operazioni sulla CPU; I/O burst → si verifica quando un processo è in attesa per richieste I/O. Dall’analisi dei burst, si evince che i burst più frequenti tra i processi sono quelli di media durata (non durano mai ne troppo poco, ma nemmeno tantissimo). 6.1 FCFS (First Come First Served) Questo algoritmo è il più semplice da pensare e implementare. All’arrivo, un processo viene posto in coda alla ready queue (lista di processi pronti ad essere eseguiti). Quando un processo termina il suo CPU burst e esegue un I/O burst, finendo nello stato di waiting, finisce in coda alla ready queue. Valutando il waiting time, si nota che questo parametro dipende sensibilmente dall’ordine di arrivo dei processi. Questo è causato dal fatto che FCFS è senza prelazione, quindi un processo sulla CPU non può essere deschedulato se non perché va in attesa, o termina. I processi che finiscono in coda ad un processo con CPU burst molto grande, attendono inutilmente molto tempo, prima di aver assegnata la CPU. In realtà questo effetto si verifica anche se i processi con CPU burst di minor durata arrivano prima di quello più grande. L’effetto prende il nome di effetto convoglio, poiché i processi che necessitano minor tempo di CPU, dopo aver eseguito l’I/O burst ritorneranno in coda a quello più lento. 6.2 SJF (Shortest Job First) Questo algoritmo, come da nome autoesplicativo, prevede l’esecuzione del processo il cui CPU burst è minore. Ne esistono due varianti, una senza prelazione e una con prelazione; in quest’ultima variante si valuta il CPU burst rimanente di ogni processo, negli istanti di tempo in cui nuovi processi giungono nello stato di ready. SJF risolve il problema del waiting time che colpisce FCFS, ma prevede la stima del CPU burst di un processo. Questa stima, statistica (non si può prevedere il futuro), viene fatto con una media esponenziale: τ (n+1) =α t n +(1−α ) τ n Questo algoritmo introduce il problema della starvation. I processi con un CPU burst molto grande verranno sempre dopo quelli con CPU burst minori, e quindi non verranno mai eseguiti. 6.3 Round Robin (RR) Questo algoritmo, con prelazione, prevede l’assegnazione della CPU ad un processo diverso, ad intervalli di tempo definiti; questi intervalli prendono il nome di time slice. Gli svantaggi di quest’approccio sono: sottoutilizzo della CPU quando questa viene assegnata a processi in I/O burst. Così facendo la time slice non viene sfruttata per eseguire istruzioni sulla CPU; sottoutilizzo delle periferiche poiché i processi che necessitano di effettuare una richiesta verso un dispositivo attualmente disponibile, devono comunque poter attendere il loro turno. Viene però eliminato il problema della starvation. 6.4 Priority scheduling Alcuni algoritmi di scheduling implementano il meccanismo basato su priorità. I processi a cui viene assegnata una priorità maggiore sono ‘privilegiati’, poiché verranno schedulati prima rispetto agli altri. Possiamo considerare SJF come un algoritmo a priorità, in cui quest’ultima è rappresentata dall’inverso della lunghezza del burst (meno dura il burst, prima andrà il processo sulla CPU). Implementare un meccanismo di priorità non è semplice, poiché si può incorrere nel problema della starvation, in cui un processo a bassa priorità non verrà mai eseguito. Per evitare ciò si implementa l’aging priority, ovvero una priorità dinamica nel tempo, che aumenta al passare del tempo di attesa nella ready queue di un processo. 6.5 Multilevel scheduling In questo tipo di algoritmi la ready queue è organizzata su più livelli. Ad ogni livello è associato una time slice e un livello di priorità. Quando un processo viene eseguito ed era nella coda di livello i, al suo deschedulamento viene posto nella coda di livello i+1, in cui la time slice aumenta ma la priorità diminuisce. 6.6 CFS (Completely Fair Scheduling) Questo algoritmo è quello attualmente implementato dallo scheduler del kernel Linux. Già dal nome si intuisce che ha come obiettivo un utilizzo equo della CPU, dal punto di vista dei processi. Infatti l’algoritmo si basa sulla suddivisione del tempo in slice di uguale lunghezza, ovvero la time slice dipende strettamente dal numero n di processi attivi. E’ inoltre presente il target latency T, ovvero un intervallo di tempo in cui ogni processo deve essere assegnato sulla CPU; pertanto la time slice è pari al rapporto T/n. Il target latency è a tutti gli effetti un parametro dell’algoritmo che si può manovrare. Le considerazioni da effettuare sul suo setting sono: T non può essere troppo basso → lo scheduler (coadiuvato dal dispatcher) sarebbe costretto ad ordinare l’esecuzione di molteplici context switch, i quali causano un utilizzo errato della CPU (si passa più tempo ad eseguire i context switch che le istruzioni dei processi); all’aumentare di n la time slice pari a T/n diminuisce generando le stesse conseguenze del punto suddetto; Il CFS prevede la memorizzazione, per ogni processo, del vruntime (virtual runtime), ovvero il cronometro del tempo di utilizzo della CPU. Quando un processo termina la time slice (T/n), o quando va in attesa per una richiesta I/O viene deschedulato, e il vruntime viene aggiornato. Questa informazione viene memorizzata in una struttura dati chiamata Red-Black Binary Tree (ABR migliorati) in cui è possibile individuare il processo con vruntime minore in O(logn). Ogni volta che lo scheduler deve stabilire a quale processo assegnare la CPU, cercherà quello con vruntime minore. Quando un nuovo processo entra nella ready queue la timeslice T/n viene aggiornata e il parametro di scelta rimane invariato. Il CFS implementa anche un meccanismo di priorità basato sulla niceness (gentilezza). Precisamente, all’aumentare del fattore di niceness (il processo è più gentile) il processo acquisisce meno priorità. Questo fattore è un valore numerico che varia nell’intervallo [-20,19) e se non specificato il valore di default è 0. Linux permette di: eseguire un nuovo processo specificando la niceness mediante il comando nice; cambiare la niceness di un processo a runtime, mediante il comando renice. 6.7 Considerazioni su CPU multi-core Fino ad ora si è considerato nello studio degli algoritmi di scheduling uno scenario in cui si possiede una singola CPU. Nei sistemi moderni questo scenario è limitativo. Ogni core del processore possiede una memoria cache (articolata sui livelli L1, L2, L3; vedi piramide) e alcuni core possiedono anche porzioni di cache condivise. Quando un processo viene eseguito su un certo core, sicuramente caricherà dalla RAM dei dati che verranno posti dal SO in queste memorie cache. Il vantaggio nell’utilizzo del caching è la notevole differenza di velocità tra queste (piccole) memorie e la RAM stessa, con un incremento significativo delle performance. Poiché sono piccole, non sempre si riesce a trovare il dato desiderato (e quindi bisogna ricaricarlo dalla RAM), ma si fa di tutto per aumentare l’hit ratio. Parliamo quindi di affinità di un processo, nei termini dell’hit ratio, ovvero un processo è più affine con un core rispetto ad un altro se la probabilità in oggetto è maggiore. Nei sistemi multi-cpu e multi-core bisogna quindi valutare su quale core far eseguire quale processo. Abbiamo sempre detto che il SO pone i processi in stato di ready all’interno di una coda. Questa coda può essere: comune a tutti i core → il vantaggio risiede nel bilanciamento del carico su tutti i core (nessun core sarà in IDLE). Lo svantaggio è relativo alla concorrenza perché le varie istanze dello scheduler (una per ogni core) non devono poter modificare nello stesso istante la ready queue ; singola per core → il vantaggio è l’eliminazione della concorrenza e la facilità di implementazione dell’affinità per i processi. Lo svantaggio risiede nel fatto che un core potrebbe andare in IDLE (senza far nulla, al termine della sua ready queue); Nella seconda modalità è possibile limitare lo svantaggio effettuando due operazioni:  pull → lo scheduler di un core, che ha terminato la sua coda, preleva processi assegnati ad altri core; push → periodicamente il SO bilancia le code su tutti gli scheduler. Ritornando al concetto di affinità, ne esistono due tipi: soft affinity → un processo può essere assegnato a più core che condividono porzioni di memoria cache; hard affinity → un processo può essere assegnato esclusivamente ad un core. 7. Sincronizzazione La sincronizzazione è uno degli aspetti più delicati nella programmazione (concorrente). Si verificano problemi di sincronizzazione quando si cercano di modificare variabili e/o strutture dati condivise, nello stesso istante di tempo da più processi e/o thread. Parliamo di race condition quando, nell’esecuzione di istruzioni di modifica su aree condivise, il risultato finale è dipendente dall’ordine in cui le istruzioni vengono eseguite. Parliamo di sezione critica di un programma, quella porzione di codice in cui si modificano le aree di memoria condivise tra più processi/thread. La sezione critica, deve quindi essere eseguita esclusivamente da un singolo processo/thread alla volta. 7.1 Proprietà della sincronizzazione Nel garantire che la sezione critica (CS) venga eseguita da un solo processo (da qui in avanti sottointendo che vale lo stesso per i thread) alla volta, bisogna rispettare tre proprietà: mutua esclusione → se un processo ha acceduto alla CS, un altro processo non può accedervi fino all’uscita del precedente; liveness → se nessun processo è dentro la CS, prima o poi, un processo che ne ha fatto richiesta accederà alla CS (altrimenti la sezione critica non viene mai eseguita e si eviterebbero i problemi, soluzione banale); fairness → se più processi tentano di accedere alla CS, ognuno di loro attenderà un intervallo finito di tempo prima di eseguire la CS. Per come sono definite le proprietà la fairness implica la liveness; basti pensare che verificata la fairness ci sarà sicuramente almeno un processo che esegue la CS → liveness verificata. Possiamo categorizzare le 3 proprietà in due categorie: proprietà di safety → sono le proprietà che se rispettate proteggono da comportamenti i causerebbero danni irreparabili al sistema/meccanismo. Rientra in questa categoria la mutua esclusione; se questa proprietà è violata a istante t, è violata anche per ogni istante T>t; proprietà di liveness → sono le proprietà che possono essere non rispettate in un certo istante, ma ciò non implica che non lo saranno in un istante successivo. Rientrano in questa categoria le proprietà di liveness e fairness. Il fatto che una di queste proprietà non sia verificata a istante t, non è un fattore irreparabile perché potranno essere verificate a istante T>t. 7.2 Soluzione di Peterson La soluzione di Peterson (codice raffigurato) è una possibile implementazione per garantire le proprietà richieste dalla sincronizzazione, nell’esecuzione di una sezione critica. Testare il funzionamento con i diagrammi temporali e notare che l’ultimo dei due processi che modifica la variabile turn sblocca l’antagonista. Precisamente: flag[i] = true serve a segnalare l’intenzione del processo i=1,2 ad accedere alla CS; la modifica della variabile turn serve a passare il controllo all’antagonista. Se ricevo il controllo, prima di passarlo, sblocco l’altro (questa è l’idea). Se ho già passato il controllo all’altro, ma lui me lo deve ancora passare, allora sarò il primo ad eseguire la CS. Dimostriamo per assurdo la proprietà di mutua esclusione. Supponiamo che non sia verificata e che quindi esista almeno un istante di tempo t per cui P1 e P2 eseguono la CS. Per essere entrati nella CS, entrambi i processi devono aver superato il while e aver valutato la condizione come falsa. Prendiamo in esame gli istanti di tempo in cui viene valutato il while; le possibilità sono: t1 < t2 (analogo al simmetrico, invertire i ragionamenti successivi) → sicuramente all’istante t1 il processo P1 ha effettuato le istruzioni flag = true e turn = 2. Detto ciò è possibile che al momento della valutazione, anche P2 abbia eseguito già flag = true e turn = 1; se quest’ultima ipotesi è vera P1 entra nella CS, ma P2 no. Se quest’ultima ipotesi non è vera P1 all’istante t1 va in attesa, ma si sbloccherà non appena P2 modificherà la variabile turn (P2 non entrerà quindi lo stesso); t1 = t2 → il valore della variabile turn è unico e quindi andrà a sbloccare solamente uno dei due processi. Abbiamo quindi verificato che l’ipotesi iniziale è ASSURDA !!! → mutua esclusione garantita. Dimostriamo adesso la proprietà di fairness, per assurdo. La fairness è verificata se un processo che tenta di accede alla CS, attende per un intervallo di tempo finito. Pertanto le possibilità che negano la fairness sono che P1 non accede mai alla CS, mentre P2 vi accede sempre o mai. Dalle ipotesi effettuate su P1 emerge che: P1 rimane bloccato nel while, pertanto la condizione è verificata → flag = true e turn = 2; Valutiamo i due comportamenti possibili di P2: P2 non entra mai nella CS, senza effettuare richiesta→ P2 non segnalerà l’intenzione di entrare nella CS, quindi flag = false che è una contraddizione con le ipotesi su P1; P2 entra nella CS → significa che prima o poi P2 effettua l’istruzione turn = 1 e quindi rimarrà bloccato nel while. Effettuando però questa istruzione sbloccherà P1. Abbiamo quindi dimostrato che prima o poi P1 entrerà nella sezione critica CS. Nello sviluppo dell’algoritmo vengono fatte queste assunzioni: le operazioni di assegnazione delle variabili sono atomiche; le operazioni vengono eseguite nell’ordine in cui sono scritte. I processori moderni, per ottimizzare, non sempre eseguono le istruzioni cosi come vengono. Si parla quindi di out of order. Questo meccanismo invalida l’algoritmo di Peterson. Altre situazioni in cui l’algoritmo potrebbe non funzionare sono causate da: utilizzo della cache, sfruttando quindi valori inconsistenti delle variabili; L’algoritmo di Peterson è quindi da implementare con operazioni atomiche : operazioni di cui si ha la certezza che vengano eseguite istantaneamente senza interruzioni. Per risolvere il problema legato all’utilizzo del caching, le diverse architetture dei processori (quindi nelle loro ISA) offrono delle istruzioni chiamate memory_barriers. Queste istruzioni sono utili, poiché quando eseguite obbligano la CPU ad attendere che le istruzioni precedenti siano finalizzate (commit). Un’istruzione è finalizzata se: è stata eseguita; il suo risultato è visibile dall’intero hardware (forza quindi il ricaricamento dalla RAM delle porzioni di memoria interessate). Un esempio di memory_barriers è l’istruzione mfence. 7.3 Istruzioni atomiche Definiamo un’istruzione atomica un’istruzione tale che: non può essere eseguita contemporaneamente su più core diversi; il suo risultato è visibile su tutto l’hardware del sistema. Risultano utili per implementare la mutua esclusione. Ne vediamo due esempi Operazione di test and set → l’operazione riceve come parametro un flag, setta il valore del flag a true e ne restituisce il valore precedente al set. Il codice implementativo è il seguente: Possiamo quindi sfruttarla per implementare la mutua esclusione, in questo modo: La variabile lock (condivisa tra i vari processi) viene sfruttata per verificare se qualcuno ha già acceduto alla CS. Poichè test_and_set è atomica, non è possibile che due processi leggano il valore di lock=false (a causa della deschedulazione) senza che prima uno di loro effettui il set a true. Quando un processo attende, questa attesa viene definita busy waiting, poiché il processo in oggetto tenta sempre di entrare valutando la condizione. Valutare la condizione comporta sempre l’esecuzione di operazioni sulla CPU. Operazione di compare and swap → l’operazione riceve in input un intero, un valore atteso e un nuovo valore da settare. Il set avviene solamente nel caso in cui il valore atteso corrisponde a quello effettivo. Ritorna il valore della variabile prima del set. Il codice implementativo è il seguente: Possiamo quindi implementare la mutua esclusione nel seguente modo: Le due soluzioni proposte non garantiscono fairness. Se uno dei processi tenta continuamente di prendere il lock subito dopo averlo rilasciato (pensare ad un ciclo infinito più esterno) non lascerebbe la possibilità agli altri di entrare nella sezione CS → quest’ultimi aspetterebbero all’infinito. 7.4 Implementazione mutua esclusione con fairness tra più processi L’implementazione è effettuata tramite il seguente codice: 7.5 Variabili atomiche e mutex Le istruzioni atomiche di test_and_set e compare_and_swap possono essere sfruttate per rendere una variabile atomica, ovvero una variabile in cui le operazioni basilari effettuate sono atomiche. Si prenda in esempio una variabile intera, le cui operazioni di incremento e decremento non sono atomiche (possono essere interrotte). Vediamo il codice per rendere l’incremento atomico: Possiamo inoltre gestire l’accesso ad una sezione critica mediante l’utilizzo di variabili mutex. Queste variabili possono essere acquisite (acquire) e rilasciate (release) mediante istruzioni che devono essere esclusivamente atomiche. 7.6 Semafori I semafori sono strutture dati per gestire la sincronizzazione tra processi/thread più flessibili rispetto alle semplici mutex. Possiamo vedere la mutex come un semaforo binario, ovvero che permette l’accesso alla sezione critica ad un solo processo per volta (mutua esclusione). I semafori possono essere usati per sincronizzare le attività, infatti se configurati opportunamente permettono di accedere alla sezione critica a più processi/thread, contemporaneamente. I semafori per svolgere il loro compito devono sempre fornire delle primitive atomiche che prendono il nome di wait() e signal(). Lo pseudocodice implementativo dei semafori è il seguente: I semafori portano con sé l’opportunità di eliminare la busy waiting. E’ opportuno eseguire un meccanismo di busy waiting quando l’attesa (stimata) per ottenere il lock è piccola, in modo da aver maggiore probabilità di essere ancora schedulati sulla CPU (se si esegue la sleep() invece si viene deschedulati). 7.7 Semafori POSIX Il kernel di Linux mette a disposizione delle systemcall utilizzabili per implementare dei semafori all’interno di programmi C/C++. Esistono due tipi di semafori nell’interfaccia POSIX: semafori con nome (named) utili quando devono essere condivisi tra più processi. Ad un semaforo di questo tipo gli si associa un nome univoco nel sistema del tipo ‘/sem_name’; semafori senza nome (unamed) utili quando bisogna gestire la sincronizzazione tra processi padre-figlio. Non serve specificare il nome grazie al meccanismo della fork() che prevede l’intera duplicazione dell’area di memoria del padre, per il processo figlio (in pratica eredita il semaforo). Le primitive POSIX sono: sem_open() → per creare un semaforo named; sem_init() → per creare un semaforo unamed, presente nella memoria del processo; sem_wait() , sem_trywait() → che implementano l’operazione atomica di wait, vista in precedenza. La prima è bloccante (necessita la riesecuzione in caso di interrupt per un segnale) mentre la seconda non lo è; sem_post() → che implementa l’operazione atomica di signal, vista in precedenza. sem_close() → per smettere di utilizzare un semaforo aperto; sem_unlink() → per eliminare un semaforo named dal sistema (non più utilizzabile da nessun processo). 7.8 Deadlock Quando più processi condividono più risorse ed effettuano dei lock su di esse è possibile incorrere in situazioni critiche come i deadlock. I deadlock accadono quando processi attendono di acquisire lock su una risorsa, che è posseduta da un altro processo in attesa a causa di un lock posseduto da uno dei processi in precedenza. Vi è quindi un attesa circolare che non permette a nessun processo di proseguire e rilasciare le risorse. Le cause dei deadlock sono: un processo P acquisisce il lock su una risorsa R1 e dopo ciò tenta di acquisire il lock su un’altra risorsa R2. Nel mentre un altro processo, che vorrebbe il lock su R1, rimane in attesa perché P è fermo. Questa situazione prende il nome di hold and wait. Sotto queste ipotesi vi è un sottoutilizzo delle risorse, ad esempio R1 è acquisita da P che non la sta utilizzando. Vi è inoltre starvation, poiché i processi rimangono in attesa di risorse ad alta richiesta, quando nel frattempo potrebbero prendere il lock su quelle a bassa richiesta. L’hold and wait va quindi evitato; non c’è prelazione sulle risorse. Se un processo possiede il lock su una risorsa R ed è in attesa, il lock su R potrebbe esser rimosso per sbloccare un altro processo; non si gestisce l’attesa circolare. L’attesa circolare si genera quando il processo necessita di più risorse, ma non riesce a prenderne il controllo di tutte. Questa situazione è risolvibile creando un ordine tra le risorse, per far si che per possedere una certa risorsa Rk bisogna possedere anche la Rk-1. La soluzione non è universale se il deadlock coinvolge risorse che vengono generate a runtime. Esistono degli algoritmi che individuano la presenza di un deadlock. Bisogna utilizzarli con attenzione poiché si può incorrere in un livelock: più processi effettuano delle operazioni per sbloccare la situazione, ma si ‘elidono’ rendendole inutili. Esistono degli algoritmi che monitorano lo stato di un sistema. Lo stato può essere: safe → se i processi non potranno incorrere in un deadlock; unsafe → se i processi potrebbero incorrere in un deadlock. Gli algoritmi controllano se ammettendo un nuovo processo vi è un cambio di stato. Il SO giunto nello stato di deadlock potrebbe: mandare il segnale SIGKILL a tutti i processi coinvolti; tentare di sbloccare la situazione inviando il segnale SIGKILL ad uno dei processi, e iterando ciò fino allo sblocco, se non dovesse funzionare. 7.9 Problema dei filosofi pensatori Questo problema prevede N filosofi che vivono la loro vita in due stati: pensare; mangiare; Per passare dallo stato pensare a quello mangiare è necessario che un filosofo possegga entrambi le forchette. Lo scenario prevede che vi siano N forchette, ognuna delle quali è condivisa con quello adiacente. Per prendere una forchetta, quest’ultima non deve essere già posseduta da un altro filosofo. La soluzione banale, ovvero quella di prendere le forchette con due operazioni diverse porta ad una situazione di deadlock → ogni filosofo riesce a prendere la forchetta alla sua destra, ma non quella di sinistra, facendo rimanere i filosofi in attesa permanente della forchetta mancante. Si mostra quindi il codice della soluzione di Dijkstra a questo problema: 7.10 Concorrenza reader, writer Nella condivisione di regioni di memoria tra più processi (problema produttore consumatore) si è notato che l’operazione di scrittura è critica, poiché le scritture eseguite da processi potrebbero portare ad uno stato inconsistente le informazioni. L’operazione di lettura, poiché non modifica l’area di memoria condivisa, non è un’operazione critica. Pertanto possiamo dire che: più processi lettori (reader) sono ammessi nello stesso istante; solamente un processo scrittore (writer) deve poter accede all’area di memoria per la sua modifica. Quando un writer ottiene il lock è importante che anche i reader siano bloccati, altrimenti andrebbero a leggere dei dati inconsistenti. Il vantaggio nell’implementazione di quanto detto sta nell’ammissione delle letture in parallelo, con conseguente aumento di performance nei reader. Si presenta quindi l’algoritmo di Michele Raynal per gestire ciò. L’algoritmo prevede: un lock per indicare la presenza di almeno un lettore attivo. Non per forza chi prende possesso del lock lo deve rilasciare, ma può essere anche un altro lettore; un lock per rendere le operazioni atomiche. Con questa implementazione, in presenza di molti lettori lo/gli scrittore/i andrebbero in starvation, poiché il lock ‘scrittore’ rimarrebbe in possesso dei lettori per molto tempo. Questo accade, anche, se i lettori giungono in momenti diversi (l’importante che il contatore non si azzeri). Per risolvere ciò si introduce una priorità sull’operazione di scrittura, basata sul seguente ragionamento: lo scrittore segnala di voler aggiornare i dati; se il lettore nota che lo scrittore vuole scrivere gli lascia effettuare l’operazione. Il codice viene quindi modificato in questo modo: 8. VIRTUAL MEMORY (Di Luna) Abbiamo già visto che la CPU esegue un’istruzione in 4 fasi: fetch; decode; execute;  write back; Tra la fase di execute e la fase di write back, la CPU (a seconda delle istruzioni) può richiedere una scrittura/lettura sulla RAM. Per questioni di sicurezza l’accesso alla RAM deve essere protetto. Noto lo schema virtuale di un processo in RAM, ogni processo può accedere alla sua area di memoria e non può utilizzare quelle assegnate ad altri. E’ necessario quindi un meccanismo di sicurezza che può essere implementato: tramite hardware → soluzione adottata; tramite software → questa soluzioni, seppur teoricamente possibile, non viene adottata in quanto richiederebbe l’intervento del SO per ogni istruzioni, aumentando i tempi di esecuzione di ogni istruzioni, riducendo quindi le performance di tutto il sistema. 8.1 Traduzione degli indirizzi Al momento di scrittura del programma, non è noto quale sarà la locazione di memoria in cui esisterà il processo; pertanto nella scrittura dei programmi non è possibile utilizzare gli indirizzi fisici della RAM. E’ necessario quindi un meccanismo (come visto hardware) che traduca gli indirizzi logici in indirizzi fisici. La traduzione potrebbe esser effettuata in 3 momenti diversi: compile time → durante la compilazione del programma, quindi contestualmente alla creazione del file eseguibile (in Linux un file ELF) gli indirizzi logici vengono tradotti in quelli fisici. Il vantaggio di questo approccio è che non prevede un supporto hardware durante l’esecuzione del processo; lo svantaggio risiede nel fatto che il processo può essere eseguito solo nelle regioni di memoria a cui afferiscono gli indirizzi fisici prodotti dalla traduzione. Se cambia la regione, il programma necessita la ricompilazione; load time → durante il caricamento del processo in RAM, viene effettuata la traduzione negli indirizzi fisici. Il programma è quindi caricabile in diverse regioni di memoria, ma la regione non può cambiare a runtime (situazione che potrebbe accadere in ipotesi di swap in/out del processo). Lo svantaggio risiede nell’introduzione di un’elevata latenza, dal momento di avvio del processo, all’inizio dell’esecuzione dello stesso; execution time (runtime) → durante l’esecuzione di ogni istruzione viene effettuata la traduzione. E’ la soluzione più flessibile, ma comporta la presenza di un supporto hardware durante l’esecuzione del processo. Ha molta rilevanza come viene allocata l’area di memoria relativa ad un processo. L’ipotesi più semplice, ma meno flessibile, è quella di allocare l’immagine di un processo in una regione di memoria contigua. Sotto queste ipotesi, la verifica che un indirizzo appartenga all’area di un certo processo può esser effettuata, mediante l’utilizzo di due registri: reg. base (limite inferiore) → indica l’indirizzo dove inizia la regione di memoria per il processo in esecuzione; reg. limit → indica la fine della regione di memoria per il processo in esecuzione. Pertanto basta verificare la disequazione base≤addrCorrente≤limit. Quando un processo tenta di accedere in una locazione di memoria non assegnata a lui, viene generata un’eccezione che fa intervenire il kernel del SO. 8.2 Memory Management Unit (MMU) Il supporto hardware che effettua la traduzione degli indirizzi logici a quelli fisici prende il nome di Memory Management Unit (MMU). Lo schema primitivo di una MMU è quello in cui quest’ultima si limiti ad introdurre un offset ad aggiungere all’indirizzo logico prodotto dal processo (l’offset serve a portare l’indirizzo nella regione di memoria assegnata al processo, tramite il reg. base). 8.3 Gestione dinamica dei processi Si introducono qui due concetti importanti: dynamic loading → un processo, quando viene eseguito, non deve essere per forza caricato interamente in memoria. Questo aspetto è molto importante, perché alcune funzionalità del processo potrebbero non essere mai usate e andrebbero ad occupare memoria inutilmente; dynamic linking → un processo, per proseguire necessita di librerie. Queste librerie possono essere condivise tra più processi. Una libreria può essere statically linked, se viene  associata al processo al suo avvio; oppure può essere dinamically linked se viene associata al processo a runtime. Quest’ultimo approccio comporta la presenza di una singola istanza in memoria della libreria. Viene implementato tramite lazy binding, ovvero quando si chiama una funzione di libreria vi è un processo (del SO) che individua l’indirizzo della funzione in oggetto e lo memorizza, per future chiamate, in una tabella; 8.4 Metodi di allocazione della memoria Mantenendo l’ipotesi di allocazione contigua della memoria per l’immagine di un processo, il SO deve quindi cercare un frammento di memoria tale che riesca a contenere il processo stesso. Il frammento può essere individuato secondo tre metriche diverse: first-fit → il primo frammento di RAM individuato viene utilizzato; best-fit → viene scelto il frammento di RAM più piccolo tra quelli in grado di contenere il processo. In questo modo si genera un frammento di memoria non allocata più piccolo; worst-fit → viene scelto il frammento di RAM più grande tra quelli in grado di contenere il processo. In questo modo si genera un frammento di memoria non allocata più grande, seguendo l’idea che quest’ultimo possa essere facilmente utilizzabile in futuro. Da esperimenti ‘pratici’, si nota che le prime due tecniche si equivalgono, mentre l’ultima è peggiore. Il limite introdotto dall’ipotesi iniziale comporta la presenza di frammentazione esterna. L’allocazione/deallocazione di processi in RAM, causa la presenza di frammenti sempre più piccoli che non possono essere allocati per nessun processo. Per risolvere la frammentazione esterna, il SO potrebbe eseguire l’operazione di deframmentazione, ovvero i vari processi vengono compattati in RAM. Questa operazione è molto onerosa e comporta lo stop dell’esecuzione dei processi fino al suo termine. Inoltre in ipotesi di allocazione contigua, il SO assegna ad ogni processo degli slot di memoria definiti. Questo fattore causa la presenza di frammentazione interna, poiché uno slot potrebbe non essere coperto interamente da un processo; la parte non utilizzata dal processo non potrà essere sfruttata per l’allocazione di un nuovo processo. 8.5 Paging La MMU nei sistemi operativi moderni è implementata secondo il meccanismo del paging. Questo meccanismo prevede la suddivisione della memoria in pagine (sezioni) di dimensione definita, ad esempio 4KB e 64KB. Ogni pagina di memoria è indipendente dall’altra e questo rimuove l’ipotesi di allocazione contigua per ogni processo. Ad un processo possono essere assegnate diverse pagine, in diverse locazioni. Questo meccanismo però deve essere trasparente al processo, ovvero quest’ultimo deve vedere la sua immagine allocata in maniera contigua. Abbiamo già visto la necessità dell’utilizzo di due tipi di indirizzi, logici e fisici. Gli indirizzi logici hanno questa struttura: virtual page number (36bit)→ prima parte dell’indirizzo logico, indica il numero della pagina ‘virtuale’; page offset (12bit)→ indica l’offset dall’inizio della pagina virtuale. La MMU quindi deve effettuare la traduzione del virtual page number nel physical page number. Infatti un indirizzo fisico è così composto: physical page number → prima parte dell’indirizzo fisico, indica il numero della pagina fisica presente in RAM; page offset → copia del valore contenuto nell’indirizzo logico. Per effettuare la traduzione, la MMU si avvale di una tabella per ogni processo. Durante l’esecuzione del processo questa tabella inizia all’indirizzo memorizzato nel registro PTR (Page Table Register). La posizione della riga nella PTR è implicitamente il numero logico della pagina, e in ogni riga è memorizzato il physical page number. Quando un processo produce un indirizzo logico, il cui numero di pagina non trova corrispondenza nella PTR, viene lanciata un’eccezione (segmentation fault). Il valore del registro PTR viene cambiato ad ogni context switch, poiché la tabella è diversa per ogni processo. Inoltre la tabella puntata da questo registro deve essere protetta in scrittura, poiché altrimenti un processo potrebbe alterarla per assegnarsi pagine di memoria non di sua competenza. Memorizzare in RAM l’intera tabella potrebbe risultare impossibile. Questa tabella cresce con l’aumentare della memoria richiesta in RAM. E’ quindi opportuno organizzare la tabella su una gerarchia a livelli (una struttura simile ad un albero). Ogni livello è identificato da una partizione del virtual page number. In questo modo è necessario mantenere in RAM solamente la tabella di livello 0, e caricare le altre su richiesta. Ad esempio, RISC V, è un architettura con 4 livelli di indirezione. Il vpn viene partizionato in gruppi da 9 bit, pertanto la tabella di livello 0 contiene 29 riferimenti a tabelle di primo livello. Ogni riga della tabella, oltre a contenere la traduzione del virtual page number nel physical page number, porta con se altri bit; ad esempio: validity bit → se la riga della tabella in oggetto è valida o meno; reference bit → se la riga della tabella è stata già utilizzata per una traduzione; bit di protezione → per dare permessi sulla pagina al processo (solo lettura, lettura e scrittura … ). Il meccanismo del paging permette di implementare il dynamic linking. Più processi che fanno utilizzo della stessa libreria, necessitano di condividerla (lo static linking prevederebbe l’allocazione di più istante della libreria, per ogni processo). Pertanto tramite tabelle dei vari processi che condividono la stessa libreria (ad esempio glibc), la traduzione viene effettuata verso lo stesso physical page number. La traduzione di un indirizzo, scorrendo i vari livelli di indirezione, può essere onerosa. Per tanto, si mantiene nella cache una tabella che prende il nome di TLB (Translation Lookaside Buffer). Quando si cerca di tradurre un indirizzo si consulta prima la TLB, in caso di successo si parla di TLB hit, altrimenti di MISS e si consulta la tabella in RAM (tramite il PTR). La TLB contiene le traduzioni per tutti i processi, nella cache della CPU. Si possono adottare due soluzioni: ad ogni context switch viene caricata in cache la TLB di quel processo. Questo prevede che al descheduling di un processo la TLB venga cambiata. L’operazione prende il nome di flush ; la TLB è unica, e in ogni riga viene aggiunto un campo per indicare il processo che l’ha prodotta (ovvero il processo che ha richiesto quella traduzione che ha causato l’inserimento nella TLB della corrispondenza). In questo modo si evita di eseguire il flush ad ogni contex switch. Sotto questa ipotesi, il flush viene effettuato al termine di un processo (delle sole righe afferenti al processo terminato). 8. VIRTUAL MEMORY (Proietti) Abbiamo introdotto il meccanismo del paging. Si riassumono qui i vantaggi di questo meccanico, che ne giustificano la sua implementazione, rispetto all’allocazione contigua dei processi: permette di implementare il dynamic loading → non è necessario mantenere l’intera immagine del processo in RAM, poiché alcune parti di codice (ad esempio gli handler dei segnali) potrebbero non essere mai eseguite e anche per la riduzione del numero di operazioni di I/O necessarie all’esecuzione del processo; permette il disaccoppiamento della memoria logica da quella fisica. In questo modo gli sviluppatori non dovranno preoccuparsi di come viene gestita la RAM del processo.  Inoltre permette di introdurre un importante meccanismo di sicurezza, in quanto i processi vedendo solo la loro regione di memoria virtuale (visualizzata come un blocco contiguo di memoria) non possono accedere alle regioni di altri processi; permette la condivisione di pagine fisiche (frame da qui in avanti), utile per non replicare l’istanza di librerie condivise tra i processi (ad esempio glibc in Linux). 8.1 Demand Paging Per quanto detto, dovrebbe esser noto, che di un processo si caricano in memoria solamente le pagine necessarie. Questo principio prende il nome di demand paging. Il processo durante la sua esecuzione può necessitare di varie pagine, e non è detto che queste sia caricate in memoria. Sappiamo che si cerca corrispondenza tra una pagina virtuale e un frame in memoria mediante la tabella delle pagine (e la TLB). Nelle righe di questa tabella è presente il cosiddetto valid bit: se 1 → indica che la riga della tabella in oggetto è valida; se 0 → indica che la riga della tabella in oggetto non è valida, e non va usata per la traduzione. Il fatto che una riga non sia valida, nasconde due situazioni: 1. il processo sta cercando di accedere ad una pagina che appartiene al suo spazio di indirizzamento, ma non è fisicamente caricata in RAM; 2. il processo sta cercando di accedere ad una pagina che non appartiene al suo spazio di indirizzamento. In questo caso il kernel del SO deve bloccare l’accesso. In Linux, quando ciò accade il kernel invia al processo il segnale SISSEGV (errore di segmentazione), il quale può essere gestito dal processo. Nel primo caso, ovvero quando la pagina virtuale non è caricata e quindi non esiste un frame fisico in RAM si parla di page fault. Quando si verifica un page fault, si genera una trap al SO in modo che si scaturisca il caricamento del frame. Pertanto l’algoritmo è: 1. si verifica che l’indirizzo di memoria appartenga allo spazio di indirizzamento del processo; 2. il page fault genera una trap al SO; 3. il SO individua un frame libero (pagina in RAM utilizzabile); 4. il SO carica la pagina dalla memoria secondaria a quella primaria (RAM); 5. il SO aggiorna la tabella delle pagine. (Ovviamente, si ricorda per i più sbadati, che la gestione della trap avviene in kernel mode, e che rappresenta un overhead nell’esecuzione del processo, da minimizzare :-)). Un’interpretazione del demand paging è il pure demand paging, il quale è una visione ‘estrema’ del caricamento della pagine se necessario. Quando un processo parte, alla prima istruzione, genererà quindi un page fault. In realtà i sistemi operativi si basano sul principio di località, prevedendo quali saranno le pagine che il processo utilizzerà. Alla verifica di un page fault il processo viene interrotto scatenando una trap. L’esecuzione dell’istruzione corrente, può essere interrotta: nel fetch → la CPU tena di caricare gli operandi. Il page fault accade perché non è disponibile la pagina/le pagine in cui gli operandi stessi sono localizzati; nel write/back → la CPU tenta di scrivere il risultato dell’operazione. Il page fault accade perché non è disponibile la pagina/le pagine in cui memorizzare il risultato. Il punto di interruzione ha rilevanza. Se l’istruzione è interrotta nella fase di WB (ultima), l’istruzione al termine della gestione del page fault, dovrà essere rieseguita interamente! Pertanto ci sarà una ri-esecuzione della fase di fetch, decode, execute … Quando si verifica un page fault, è necessario individuare un frame di memoria libero. Per far ciò il SO, non scorre tutta la RAM (ovviamente ;-)), ma mantiene nel suo spazio di indirizzamento una lista che prende il nome di free-frame list. Quando un nuovo frame viene allocato, viene prima azzerato; il meccanismo prende il nome di zero-fill-on-demand. Come visto, la gestione dei page fault introduce overhead nell’esecuzione di un processo. E’ importante quindi valutare il suo impatto, mediante tre parametri: tmm → tempo medio di accesso alla ram; tpf → tempo di gestione del page fault da parte del SO (lo si può ridurre tramite il design del kernel); p → probabilità che si verifichi un page fault. Pertanto il tempo effettivo di accesso alla RAM è: t ea=(1− p)t mm + p t pf 8.2 Copy-on-write La virtual memory, mediante il meccanismo del paging, permette di condividere più frame fisici tra più processi. Questo accade per le librerie condivise ma anche nella creazione di un nuovo processo figlio tramite la systemcall fork(). Sappiamo che il figlio è la copia identica del padre, quindi non è necessario duplicare i frame fisici in memoria, finché essi non vengano modificati (o nel padre o nel figlio). Alcuni SO implementano una variante della fork(), che prende il nome di vfork() [v di virtual, per memorizzarla]. La vfork() condivide le pagine anche dopo la modifica, ed è utile quando dopo la creazione del figlio si esegue la exec() [che forza il cambiamento dell’immagine del processo in memoria, con quello passato]; la vfork() è più veloce rispetto alla fork(). 8.3 Sostituzione delle pagine Il demand paging, poiché non prevede il caricamento dell’intero processo in RAM, aumenta il grado di multiprogrammazione del sistema. La situazione critica che può accadere è che in RAM non ci siano frame liberi (free frame list vuota). In questo caso il SO potrebbe: terminare il processo che ha causato il page fault, perché quest’ultimo non può essere gestito con successo. Così facendo si elimina il disaccoppiamento tra memoria virtuale e fisica → soluzione da scartare; utilizzare lo swapping (non più in uso perché le memorie RAM sono sovradimensionate); implementare un algoritmo di sostituzione delle pagine. L’algoritmo di sostituzione delle pagine deve individuare un frame vittima da sostituire. Il frame vittima può essere sia del processo in oggetto, ma anche di un altro processo. Quando un frame viene sostituito, non è scartato → il suo contenuto deve essere memorizzato sulla memoria secondaria, per un futuro ricaricamento. L’hardware dei sistemi moderni, fornisce il dirty bit. Se il dirty bit vale: 0 → la pagina in oggetto non ha subito modifiche. Pertanto non è necessario il suo salvataggio in memoria secondaria, perché li è già presente la copia più aggiornata (per le pagine in sola lettura, il dirty bit sarà sempre a 0); 1 → la pagina in oggetto ha subito modifiche. Pertanto è necessario il suo salvataggio in memoria secondaria. Gli algoritmi di sostituzione dei frame, e di allocazione iniziale dei frame, hanno importanza. Questo perché impattano notevolmente sulle performance. Si cerca in ogni caso, di minimizzare il page fault rate. Da qui in avanti vediamo gli algoritmi di sostituzione possibili. 8.3 Sostituzione FIFO L’algoritmo FIFO (First In First Out) prevede la sostituzione del frame in memoria che è stato caricato meno recentemente (il primo arrivato). Il vantaggio di questo algoritmo è la facilità di implementazione, ma d’altra parte non tiene conto della frequenza con cui un frame viene utilizzato dal processo. Se una pagina viene caricata all’avvio del processo e viene utilizzata costantemente durante l’esecuzione, verrà comunque selezionata come vittima per risolvere un page fault. Inoltre, all’aumentare dei frame totali della RAM, l’algoritmo FIFO soffre dell’anomalia di belady → esistono delle situazioni in cui il numero di page fault aumenta, anche se i frame totali aumentano. 8.4 Sostituzione OPT L’algoritmo OPT (Optimal) è il migliore algoritmo per la sostituzione dei frame. Si basa sul seguente principio “va sostituita la pagina che non verrà usata per un periodo di tempo più lungo”. Ovviamente, l’algoritmo non è implementabile poiché bisognerebbe conoscere il futuro. Non soffre dell’anomalia di belady, e può essere utilizzato come metro di valutazione per gli altri algoritmi. 8.5 Sostituzione LRU L’algoritmo LRU (Least Recently Used) è un algoritmo che approssima OPT. Si basa sul seguente principio “va sostituita la pagina che non viene usata dal maggior periodo di tempo”. Questo algoritmo risulta implementabile, in quanto necessita un’analisi del passato e non del futuro. L’implementazione può avvenire in due modalità: mediante un orologio → ad ogni pagina viene associato un orologio, che si aggiorna contestualmente all’ultimo utilizzo della stessa. Per individuare la pagina usata meno recentemente, basterà prendere quella con orologio minore; mediante uno stack (pila) → si mantiene una pila con i numeri di pagina. Ogni volta che una pagina viene usata, viene inserita in testa alla pila. La meno recente sarà l’ultima pagina della pila. Questa lista deve essere doppiamente collegata, per effettuare le operazioni in tempo costante. LRU e OPT sono stack alghoritms, ovvero quegli algoritmi per cui si può dimostrare che l’insieme delle pagine con n frame disponibili, è sempre un sottoinsieme delle pagine con n+1 frame disponibili. Per implementare LRU puro, è necessario un supporto hardware. Se questo non ci fosse e le due implementazioni possibili sono a carico del SO, la latenza nella gestione di un page fault sarebbe troppo elevata. 8.6 Sostituzione LRU approssimata Non tutti i sistemi forniscono il supporto hardware necessario all’implementazione di LRU. La maggior parte degli hardware fornisce il reference bit, che indica se la pagina viene utilizzata (scrittura o lettura indistintamente), senza però fornire indicazione sulla tempistica. I seguenti algoritmi fanno utilizzo del reference bit. L’algoritmo con Reference-bit addizionali prevede la memorizzazione di un byte per ogni pagina. In ogni bit del byte (8 in tutto) viene memorizzato il reference bit più recente nel bit più significativo. Ogni intervallo di tempo, il byte viene shiftato a destra. La pagina usata meno recentemente sarà quella con il byte più piccolo. L’algoritmo dell’orologio prevede l’utilizzo del reference bit come indicatore temporale. L’algoritmo prevede la scansione della lista dei frame, e quando il reference bit vale: 0 → la pagina viene sostituita; 1 → il reference bit viene azzerato. Si procede con la scansione fino a trovare una pagina da sostituire. Viene quindi data alla pagina in oggetto una seconda possibilità. Se durante la prima iterazione non viene individuata il frame da sostituire si rinizia la scansione, come una lista circolare. Il puntatore all’inizio della scansione non inizia sempre dal primo frame, ma dalla successiva a quella precedentemente sostituita. Questo algoritmo può far anche utilizzo del dirty bit, quando supportato. Le possibili combinazioni sono (reference, dirty): (0,0) → la pagina non è stata utilizzata e ne modificata, quindi è quella più indicata ad essere vittima; (0,1) → la pagina non è stata utilizzata recentemente ma modificata. Sostituirla comporta il suo caricamento in memoria secondaria;  (1,0) → la pagina è stata utilizzata recentemente ma non modificata. Sostituirla non comporta il suo caricamento in memoria secondaria, e probabilmente sarà utilizzata di nuovo; (1,1) → la pagina è stata modificata recentemente. E’ il caso peggiore di frame da sostituire, perché comporta sia il caricamento in memoria secondaria, e perché probabilmente sarà riutilizzata. Esistono poi due approcci alternativi, poco utilizzati: LFU (Less Frequently Used) → prevede la sostituzione della pagina utilizzata meno frequentemente. Non è utile, in quanto una pagina che viene utilizzata molto all’inizio rimarrebbe in memoria; MFU (Most Frequently Used) → prevede la sostituzione della pagina utilizzata più frequentemente. I SO mobili (Android e iOS) non prevedono lo swapping delle pagine in memoria secondaria; pertanto quando un frame deve essere sostituito applicano algoritmi di compressione per collassare molteplici frame in uno solo. 8.7 Allocazione dei frame E’ importante studiare come il SO alloca i frame in memoria per un nuovo processo. Nel pure demand paging, l’idea è quella di caricare un processo con 0 pagine in memoria. Questo comporta numerosi page fault iniziali (scaturiti già dalla prima istruzione) con conseguente aumento della latenza di avvio, in maniera non accettabile. Pertanto il SO deve allocare un numero di pagine per ogni processo. Esistono due approcci: allocazione equa → se si hanno a disposizione m frame totali, e vi sono n processi si assegnano ad ognuno m/n frame; allocazione proporzionale → il numero di frame varia in base alla grandezza del processo (in m termini di frame richiesti). Detta la grandezza si e S=∑ s i allora il numero di frame per i=1 si processo è pari a a i=m. S Bisogna tener presente che, in memoria per ogni processo vi devono esser un numero sufficiente di frame per eseguire un’istruzione; il numero minimo necessario dipende dall’architettura del processore e sotto quel numero non si può scendere. Altrimenti il processo continuerebbe a generare page fault senza la possibilità di avanzare nell’esecuzione. Aspetto non considerato durante lo studio degli algoritmi di sostituzione delle pagine è se un frame ‘vittima’ debba esser individuato tra le pagine del processo che ha generato il page fault (sostituzione locale) o tra tutte le pagine di tutti i processi (sostituzione globale). Si sceglie la seconda soluzione che comporta: come vantaggio, un aumento delle performance a livello di sistema; come svantaggio, l’effetto indiretto che un processo ha sugli altri processi, poiché un page fault può causare la sostituzione di un frame di un altro processo. Definito come scelta quella della sostituzione globale, bisogna considerare quando far eseguire gli algoritmi di sostituzione. I SO eseguono gli algoritmi (di solito LRU approssimati) senza aspettare che la RAM sia satura (nessun frame disponibili). Precisamente gli algoritmi cercano di mantenere i frame liberi in un range. Quando la soglia minima viene superata (al di sotto, ovviamente) si attivano delle routine kernel, i reapers, che si occupano del recupero di frame. Il lavoro di queste routine al raggiungimento della soglia massima del range (non ci si ferma a quella minima, altrimenti appena viene allocato un nuovo processo, bisognerebbe procedere di nuovo al recupero di frame). In casi estremi, ovvero quando la memoria è prossima alla saturazione, i SO eseguono delle routine che prendono il nome di OOM Killer (Out Of Memory Killer) che scelgono un processo e lo eliminano dalla memoria. Il processo viene scelto in base al oom_score (punteggio contenuto nel PCB del processo) che sale all’aumentare della memoria del processo stesso, con conseguente aumento di probabilità di essere selezionato (per morire :--)). Durante la trattazione, si è considerato il page fault come l’evento scaturito dalla mancanza di una pagina in memoria, con conseguente caricamento di essa dalla memoria secondaria. In realtà esistono due tipi di page fault: major page fault → accade quando la pagina richiesta non è presente fisicamente in RAM e va caricata dalla memoria secondaria; minor page fault → accade quando la pagina richiesta non è presente nello spazio di indirizzamento fisico, ovvero non vi è una entry nella page table che permetta di accedervi, ma in real