Sistemi Operativi PDF - Introduzione e Concetti Fondamentali

SISTEMI OPERATIVI INTRODUZIONE Gli scopi del OS (Ovvero il sistema operativo) sono molteplici. In primis un sistema operativo deve permettere ad ogni tipologia di utente un facile utilizzo (convenienza del so), deve essere efficiente (efficienza del so) e deve essere in grado di adattarsi rispetto a...

SISTEMI OPERATIVI INTRODUZIONE Gli scopi del OS (Ovvero il sistema operativo) sono molteplici. In primis un sistema operativo deve permettere ad ogni tipologia di utente un facile utilizzo (convenienza del so), deve essere efficiente (efficienza del so) e deve essere in grado di adattarsi rispetto all’evoluzione dell’hardware e alle esigenze degli utenti (capacità di evolversi). CONVENIENZA DEL SO Il sistema operativo deve essere trasparente, ovvero deve nascondere i dettagli hardware al programmatore e mettere a disposizione una interfaccia all’utente (convenienza del so). Infatti, possiamo immaginare questa struttura come una scala o una piramide gerarchica, dove alla base c’è la parte Hardware del computer, al di sopra il SO che fa da maschera per la componentistica hardware e al di sopra del sistema operativo, tutti i programmi e le applicazioni utenti che comunicano con il sistema operati che a sua volta comunica con l’hardware (Ogni livello si basa sulle fondamenta del livello inferiore). SERVIZI OFFERTI DAL SO Creazione dei programmi: Il compilatore, il debugger sono funzionalità(programmi) offerte al programmatore che può utilizzare ma che non sono parti del SO ma sono accessibili tramite esso. Esecuzione dei programmi: Il sistema operativo facilità l’esecuzione dei programmi, caricandoli in memoria, inizializzando i dispositivi di Input e Output ecc… Accesso ai dispositivi di I/O: L’utente o il programmatore vede con trasparenza e ignora tutte le istruzioni e i segnali che in sistemi di Input e Output producono/richiedono per funzionare. Accesso controllato ai file: Il sistema operativo comprende il formato dei file, i meccanismi di protezione e associa ogni file ad un indirizzo di memoria. Rilevazione e correzione degli errori hardware o dei programmi in esecuzione. Analisi e statistiche di tutte le risorse del computer, dei tempi di risposta per il fine di migliorare le prestazioni. EFFICIENZA DEL SO Il sistema operativo ha il compito di dirigere l’utilizzo delle risorse del sistema (Come per esempio la CPU) e nella temporizzazione dell’esecuzione dei programmi. Quindi lui decide quando e come una risorsa deve essere utilizzata. Le funzioni principali e fondamentali del sistema operativo prendono il nome di KERNEL e vengono caricate, all’avvio del computer nella memoria centrale per permettere un rapido utilizzo di questo set di funzioni principali. Quindi in memoria risiede il Kernel, parti del sistema operativo utili per la funzione in esecuzione e tutti i programmi e dati utilizzati in quel momento. La Mono-Programmazione è la forma più semplice di organizzazione del computer per quanto riguarda l’esecuzione di programmi/funzioni, infatti il SO operativo si concentra al 100% sull’esecuzione di un singolo programma con l’utilizzo di tutte le risorse dedicate a quel singolo programma e quindi in memoria sarà presente solamente il programma in esecuzione e tutte le relative istruzioni e dati adoperati. La Multi-Programmazione è uno scenario nel quale in memoria sono presenti più programmi ed ha come obbiettivo l’impiego intelligente delle risorse, ovvero quando un job(istruzione) non utilizza più la CPU, essa al posto di rimanere in attesa, verrà adoperata per l’esecuzione di altre istruzioni (Esempio quando un job effettua una operazione di I/O, la CPU, può essere adoperata per altri utilizzi, altro esempio quando il computer deve eseguire 3 job, che richiedono tempi e risorse differenti, al posto di eseguire prima interamente il primo job e successivamente passare al 2 e così via, avvia in contemporanea i 3 job ed attraverso delle regole di schedulazione, decidere come organizzare l’utilizzo delle risorse secondo delle Cassano Francesco Saverio priorità scelte). Le difficoltà della multiprogrammazione sono la gestione della memoria e la scelta di quale job mandare in esecuzione (ovvero la schedulazione). Un Job non è altro che il processo di un programma che è formato dal codice eseguibile, dai dati (variabili, spazi di lavoro, buffer) e le informazioni di esecuzione ovvero le info necessarie al so per gestire il processo (Contenuto dei registri della CPU, priorità, stato di esecuzione, stati di attesa di dispositivi di I/O). GESTIONE DELLA MEMORIA Nel quadro generale dell’esecuzione dei programmi in memoria, abbiamo caricati la lista dei processi in esecuzione, tutte le informazioni di quest’ultimi (Dati, info, codice) e parallelamente avremo nei registri della CPU tutte informazioni del processo in esecuzione (Come il numero del processo, il numero del processo successivo (numero è una semplificazione della posizione in memoria del processo). Il Context Switching non è altro che il processo di cambiamento di processo in esecuzione, lo stato e i risultati del primo processo vengono memorizzati e viene caricato il secondo processo). In pratica il SO deve assolvere 5 compiti: 1. Isolamento dei processi. 2. Allocazione e gestione automatica della memoria: la gerarchia delle memorie deve essere trasparente all’utente. 3. Supporto alla programmazione modulare: Variazione di dimensione dei programmi. 4. Protezione e controllo dell’accesso: Gestione di aree di memoria condivise tra i processi. 5. Memorizzazione a lungo termine. Necessità soddisfatte dalla Memoria Virtuale (I programmi indirizzano la memorai con riferimenti logici ignorando gli aspetti fisici, quando un programma è in esecuzione solo una sua parte risiede effettivamente in memoria centrale) e il File System (Implementa la memorizzazione a lungo termine). SCHEDULAZIONE (accenno) La schedulazione è la “tecnica” di gestione dei processi. La politica di allocazione delle risorse deve considerare i seguenti fattori: Equità di tutti i processi (appartenenti ad una stessa categoria, con richieste simili, stesso costo di risorse) e devono avere tutti la stessa possibilità di accesso alla memoria. Efficienza ovvero la massimizzazione dei trasporti e la minimizzazione dei tempi di riposta. Il tempo di risposta differenziale, il so discrimina tra classi che hanno bisogno di risorse diverse e tempi diversi (Esempio i processi che utilizzano molto i dispositivi di I/O vengono eseguiti per primi). Cassano Francesco Saverio  DESCRIZIONE e CONTROLLO dei PROCESSI In ambienti multi-programmati Un processo è una entità che deve essere eseguita su una CPU che è caratterizzata dall’esecuzione in sequenza di istruzioni, uno stato corrente e un set di risorse di sistema. Il processo è un’istanza di programma in esecuzione (che può entrare nella CPU). Il sistema operativo ha necessità di uno strumento per gestire i processi, che tenga traccia di tutte le info disponibili dei processi (Come per esempio il nome, le risorse, i collegamenti, la cronologia delle attività ecc..). Tale strumento prende il nome di PCB, ovvero Process Control Block. PROCESS CONTROL BLOCK Il PCB descrive il processo attraverso il quale il SO può gestirlo. Il PCB è una tabella che è strutturata in questo modo. l’INDETIFICATORE DEL PROCESSO o PID ovvero il valore numerico del processo, il nome (ID del processo) e o Il PID del processo genitore (Infatti un processo può essere generato anche da un altro processo e quindi avremo la situazione del processo genitore e il processo figlio). INFO SULLO STATO DEL PROCESSORE o Registri Dati visibili all’utente o Puntatori allo stack (SP, BP) usati per procedure e funzioni. o Registri di controllo e di stato (PSW)  PC, indirizzo della prossima istruzione da eseguire.  Registri di stato, includono i flag per l’abilitazione degli interrupt.  Registri che contengono codici di condizione (segno, overflow ecc…). INFORMAZIONI DI CONTROLLO DEL PROCESSO o Schedulazione e info di stato  Stati del processo (Running, ready, blocked, ecc…).  Priorità nelle code di scheduling  Info correlate alla schedulazione (Tempo di attesa, tempo di esecuzione, ecc…).  Evento (Del quale è in attesa). o Strutturazione dati, ovvero puntatori ad altri processi (Figli/padre o per l’implementazione di code). o Comunicazione tra Processi, ovvero flag, segnali e messaggi per la comunicazione. o Privilegi, in relazione all’uso di memoria, dispositivi, ecc… o Gestione memoria, limiti di memoria, insieme degli indirizzi accessibili (Base, indice). o Contabilizzazione delle risorse, risorse controllate dal processo (Lista file aperti, lista dispostivi I/O) e la loro cronologia. Questi 3 grandi blocchi, possono anche non essere contigui in memoria ed essere separati nella memoria in base al metodo di gestione della memoria. Cassano Francesco Saverio  EVENTI di CREAZIONE e TERMINAZIONE dei PROCESSI Gli eventi che portano alla creazione di un processo sono 3, ovvero 1. Richiesta (Un utente accede al sistema). 2. Il SO genera un processo sulla base della richiesta di un processo utente. 3. Un processo utente genera un nuovo processo (Padrefiglio) Gli eventi che portano alla terminazione di un processo sono: 1. Terminazione normale (End, il processo ha terminato il suo compito). 2. Uscita dell’utente dalla applicazione. 3. Superamento del tempo massimo. 4. Memoria non disponibile. 5. Violazione dei limiti di memoria. 6. Fallimento di una operazione (aritmetica – I/O). 7. Terminazione del genitore. 8. Richiesta del genitore. MODALITÀ di CREAZIONE dei PROCESSI Quando un processo viene creato, prima di andare in esecuzione vengono creati tutti i campi del PCB. 1. Assegnare un PID unico al processo a. Aggiungere una entry level alla tabella dei processi. 2. Allocare lo spazio per il processo e per tutti gli elementi della sua immagine (PCB, User Stack, Area di memorai dati e istruzioni, aree condivise). 3. Inizializzazione del PCB a. Stato del processore = 0. b. PC = Prossima istruzione. c. Puntatori allo stack. d. Stato = Ready (Ready-suspended). 4. Inserimento nella coda ready. 5. Estende le strutture al fine della fatturazione o delle statistiche. MODALITÀ di TERMINAZIONE dei PROCESSI Il processo può terminare per svariati motivi. Perché ha eseguito l’ultima istruzione e chiede al SO di cancellarlo (exit) ed un processo figlio può riportare dati al padre e le risorse del processore sono deallocate. Un Processo padre può uccidere un processo figlio (abort), ciò può avvenire perché il figlio ha ecceduto nell’uso delle risorse, il compito del figlio non è più richiesto o se il processo genitore è terminato, in alcuni sistemi operativi il processo figlio termina (cascading termination). Cassano Francesco Saverio  MODALITÀ di ESECUZIONE dei PROCESSI Un processo può essere eseguito in due modalità, utente e sistema (Kernel o controllo). Nella modalità utente, un processo è in uno stato caratterizzato da un numero relativamente basso di privilegi verso la memoria, l'hardware e altre risorse. Nella modalità Kernel, i processi hanno come scopo:  Gestione dei Processi o Creazione e terminazione. o Schedulazione. o Cambio di contesto. o Sincronizzazione. o PCB  Gestione della Memoria o Allocazione. o Trasferimento disco/RAM e viceversa. o Gestione paginazione/segmentazione.  Gestione I/O o Gestione buffer. o Allocazione canali I/O.  Supporto o Gestione Interruzioni. o Contabilità. CONTEXT SWITCH Il context switch riguarda il cambio del processo in esecuzione sulla CPU. Le principali cause sono il clock interrupt, ovvero il processo ha terminato il tempo a sua disposizione (torna in ready) per un I/O interrupt, ovvero una operazione di I/O è terminata, il SO sposta il processo in attesa di tale evento da blocked a ready e decide se riprendere l’esecuzione del processo precedente, il Memory Fault, ovvero l’indirizzo di memoria generato è sul disco (memoria virtuale) e deve essere portato in RAM. Il SO carica il blocco, nel frattempo il processo che ha generato la richiesta è in blocked (al termine del trasferimento andrà in ready), per Trap, ovvero per colpa di un errore di esecuzione (il processo potrebbe andare in exit) e per una Spervisor call, ovvero per esempio quando vi è un File open, il processo utente va in blocked. Le operazioni svolte dal SO in modalità supervisor al momento del cambio di processo in stato di running, vengono salvati tutte le informazioni nei registri del processo, vi è un aggiornamento dello stato del PCB (da ready a blocked ecc…), viene spostato il PCB in una nuova coda (ready o blocked) o de alloca le sue risorse (exit), vengono aggiornate delle strutture dati nella gestione della memoria (area dello stack), viene selezionato il nuovo processo per lo stato running (dispatcher), viene aggiornato lo stato del suo PCB e viene ripristinato il contesto. Nel tempo detto Overhead impiegato per il context switch, il sistema non svolge nessun compito (utile all’utente), più l’overhead è basso, maggiore è la quantità di tempo CPU che si può utilizzare per i processi utente ed il tempo dipende dalla complessità del SO e dall’hardware. Cassano Francesco Saverio  ESECUZIONE DEL SISTEMA OPERATIVO Il sistema operativo può essere eseguito in 3 modi distinti, in modalità kernel separato (obsoleto), dentro i processi utenti e in modalità basata su processi. Kernel separato o Risiede in una regione di memoria specifica. o Monolitico. o Eseguito come entità (programma) separata. Dentro i processi utente (Vengono incluse librerie, programmi, dati e stack del kernel del SO) o Il SO mantiene poche funzioni (Process switch) o Quando in un programma vi è una chiamata a funzionalità di SO, si cambia modo di esecuzione dopo il salvataggio del contesto utente (modo utente modo kernel) (non c’è nessun cambio di processo). SO basto su processi o Il SO è formato da più Processi di Sistema. o Pro: interfacce pulite e semplici tra i moduli. o Utile in sistemi multiprocessore. MODELLO A DUE STATI Il compito principale di un SO è il controllo dell’esecuzione dei processi per questo il SO deve sapere lo stato di ogni processo per poter allocare le risorse che richiede il processo. Quando un processo viene creato, il sistema operativo lo imposta in stato di “not running”, il processo esiste e attende il momento in cui può passare in esecuzione e quindi, in quel caso, lo stato del processo cambia in “running”, una volta che il processo ha terminato la sua esecuzione, il suo stato passa nuovamente in “not running” e il processo in coda, verrà allocato e il suo stato passerà in “running”. MODELLO A CINQUE STATI Nel modello a 2 stati lo stato “not-running” sottintende 2 diverse possibilità, ovvero in coda in attesa di andare in run e in coda in attesa di I/O, infatti non sempre tutti i processi sono effettivamente pronti poiché può capitare che un processo è bloccato. Per questo lo stato di running è stato suddiviso in “ready” e “blocked”. Quando un processo è in ready il SO carica tutte le risorse che necessità quel processo (Carica in RAM tutte le istruzioni e i dati di quel processo) e quando è il suo turno passa in running, se il processo è deve attendere per esempio un dispositivo di I/O, il processo passa in stato di “blocked”. In aggiunta a questi 3 stati, vengono aggiunti anche lo stato di “new”, ovvero quando un processo passa è appena creato e il SO, compila la tabella delle sue informazioni (PCB) e infine lo stato di “exit”, ovvero quando un processo ha terminato la sua esecuzione o/e fallito. Riepilogando abbiamo: 1. New: Il processo viene creato e viene generata la sua relativa tabella PCB. 2. Ready: Il processo è pronto per l’esecuzione. 3. Blocked: Il processo è bloccato perché attende un determinato evento. 4. Running: Il processo è in corretta esecuzione. 5. Exit: Il processo ha terminato la sua esecuzione e/o è stato rilasciato dall’insieme dei sistemi eseguiti o è terminato per un errore. Non è detto che un processo segua questo ordine, infatti un processo figlio, può andare in exit senza mai andare in esecuzione, perché il processo figlio termina. I processi possono entrare in code durante lo stato di ready o blocked e in base alle regole di schedulazione entrano in esecuzione. Cassano Francesco Saverio  MODELLO A SETTE STATI (Swapping) Può capitare che molti processi in stato di blocked, non vadano in esecuzione per molto tempo ed occupano inutilmente spazio in memoria centrale. Le possibili soluzioni sono due, in primis aumentare la dimensione della memoria centrale del computer ma questo comporterebbe un enorme dispendio economico, la seconda soluzione è lo swapping, ovvero spostare un processo momentaneamente dalla memoria centrale alla memoria di archiviazione. Per questo motivo i processi passano nello stato di “suspend”. Ovviamente un processo che originariamente era nello stato di blocked, anche se spostato in memoria continua a rimanere in questo stato bloccato, in attesa di un evento e non vi è necessità di ricaricarlo in memoria centrale se ancora bloccato, per questo motivo vengono introdotti due nuovi stadi, ovvero, “blocked-suspend” e “ready-suspend”. Nello stato “blocked-suspend” il processo viene caricato nella memoria di archiviazione ma risulta ancora in stato di blocco, in alcuni casi può capitare che per necessità bisogna liberare memoria e il SO decida di spostare anche un processo in stato di “ready” in memoria per questo il processo passa in stato di “ready-suspend”. Ovviamente quando un processo in stato di “blocked-suspend” ha ricevuto il suo evento, esso può passare allo stato di “ready-suspend” o eventualmente anche in “ready”. Un processo in “blocked-suspend”, può passare allo stato “blocked”, ovvero ricaricato in memoria principale, anche se ancora in attesa del suo evento, questo può capitare perché tale processo ha una priorità maggiore a processi in stato di “ready-suspend”. Ricapitolando abbiamo: 1. New: Il processo viene creato e viene generata la sua relativa tabella PCB. 2. Ready: Il processo è pronto per l’esecuzione. 3. Blocked: Il processo è bloccato perché attende un determinato evento. 4. Running: Il processo è in corretta esecuzione. 5. Exit: Il processo ha terminato la sua esecuzione e/o è stato rilasciato dall’insieme dei sistemi eseguiti o è terminato per un errore. 6. Blocked-suspend: Il processo viene trasferito in memoria di archiviazione per liberare spazio nella memoria centrale (nel mentre il processo è ancora in attesa dell’evento). 7. Ready-suspend: Il processo viene trasferito in memoria di archiviazione per liberare spazio in memoria centrale, anche se il processo è pronto per l’esecuzione (Per esempio un processo con uno stato di priorità maggiore richiede spazio in memoria). SCHEDULAZIONE dei PROCESSI L’obbiettivo dello scheduler è quello di amministrare l’ordine in cui i processi vanno in esecuzione e quindi il suo utilizzo è essenziale per la massimizzazione e ottimizzazione delle prestazioni del sistema. Il sistema operativo può prevedere fino a 3 tipi di scheduler. Uno scheduler di lungo termine (SLT), uno scheduler a medio termine (SMT) e uno scheduler a breve termine (SBT). Tutti queste 3 tipologie di scheduler bisogna immaginarli come 3 cicli annidati, partendo dallo scheduler a lungo termine per poi trovare quello a medio e breve termine. SHEDULER A LUNGO TERMINE L’obbiettivo dello scheduler a lungo termine è quello di determinare quali programmi inserire nel sistema per l’esecuzione, perciò controlla il grado di multiprogrammazione, ovvero più processi vuol dire un minor tempo percentuale di esecuzione di ognuno di essi (attenzione il tempo dato per l’esecuzione, non il tempo effettivo di esecuzione del singolo processo). Stime fatte dal programmatore o dal sistema, forniscono le informazioni essenziali sulle risorse necessarie all’esecuzione (dimensioni memoria, tempo di esecuzione Cassano Francesco Saverio totale ecc..), in pratica lo scheduler a lungo termine si basa quindi sulla stima del comportamento globale dei processi. Le strategie principali sono quella di fornire alla coda dei processi pronti (e quindi allo scheduler di breve termine) gruppi di processi che siano bilanciati tra loro nello sfruttamento della CPU e dell’I/O. Infatti, esistono dei processi che sono detti “processor bound” ovvero processi che lavorano prevalentemente a livello computazionale ed occasionalmente utilizzano i dispositivi di I/O, al contrario i “I/O bound” sono i processi che principalmente lavorano con i dispositivi di I/O piuttosto che il processore. Un altro compito è quello di aumentare il numero di processi proveniente dalla coda batch, quando il carico della CPU diminuisce e un ultimo compito è quello di diminuire (fino anche a bloccare) i job proveniente dalla coda batch, quando il carico aumenta e/o i tempi di risposta del sistema diminuiscono. Lo scheduler a lungo termine lavora con i processi in stato di New, ready e Ready Suspend. SHEDULER A LUNGO TERMINE L’obbiettivo dello scheduler a medio termine è quello di gestire la parte del disco o meglio la funzione di swapping. La presenza di molti processi sospesi in memoria riduce la disponibilità per nuovi processi pronti. In questo caso lo scheduler di breve termine è obbligato a scegliere tra i pochi processi pronti. Lo scheduler a medio termine utilizza le informazioni del PCB per stabilire la richiesta di memoria del processo. tenta di allocare spazio in memoria centrale e riposiziona il processo in memoria nella coda dei pronti. Lo scheduler a medio termine viene attivato quando si rende disponibile lo spazio in memoria e/o quando l’arrivo di processi pronti scende al di sotto di una soglia specificata. Lo scheduler a medio termine lavora con i processi in stato di Blocked, ready, Ready Suspend e Blocked Suspend. SHEDULER A BREVE TERMINE Lo scheduler a breve termine è lo scheduler che prende decisioni più spesso, viene anche chiamato solitamente dispatcher o allocatore ed ha il compito di decidere quale processo eseguire per prossimo. Lo scheduler a breve termine viene chiamato ogni volta che si verifica un evento che può portare alla sospensione di un processo corrente o di pre-rilasciare il processo attualmente in esecuzione in favore di un altro (leggi “EVENTI di CREAZIONE e TERMINAZIONE dei PROCESSI”). Quindi in soldoni la sua principale strategia è orientata alla massimizzazione delle prestazioni del sistema secondo uno specifico insieme di obiettivi. Lo scheduler a breve termine lavora con i processi in stato di Ready e Run. Cassano Francesco Saverio  SHEDULING DELLA CPU Lo scheduling della CPU riguarda la distribuzione delle sequenze di elaborazione della CPU con cicli di elaborazione (CPU) e di attesa di completamento di I/O. Ci sono due tipologie di approcci ovvero User- Oriented e System-Oriented. User-oriented o Turnaround time: Tempo intercorso tra la sottomissione di un processo e la sua terminazione. o Tempo di risposta: Per un processo interattivo è il tempo trascorso tra la sottomissione di richiesta e il ritorno del primo output (Il processo può continuare nel suo ciclo di esecuzione mentre produce output). o Deadlines: Quando la deadline di un processo specificata, lo scheduler deve fare in modo di completare (o avviare) il processo entro la deadline. System-oriented o Throughput: Numero di processi terminati per unità di tempo. o Utilizzo del processore: % del tempo in cui la CPU è impegnata  Per eseguire programmi degli utenti.  Per eseguire moduli del sistema operativo. o Evitare la starvation: Processi a bassa priorità in attesa infinita (La starvation è l’impossibilità di un processo nell’ottenere le risorse che gli servono. o Utilizzare tutte le risorse: (dispositivo di I/O, CPU, ecc.) In soldoni i criteri orientati all’utente sono relativi a come il singolo utente o processo percepisce il comportamento del sistema, come per esempio il tempo di risposta che grazie allo scheduling deve essere il più ottimale possibile, per quanto riguarda i criteri orientati al sistema il punto focale è l’efficienza e l’efficacia dell’utilizzo del processore, come per esempio il throughput, che la frequenza di completamento dei processi. I criteri di ottimizzazione sono il massimo impiego della CPU, il massimo throughput (La massima portata), il minimo tempo di risposta e il minimo turnaraund time (“Il tempo di ricircolo” è una delle metriche utilizzate per valutare gli algoritmi di pianificazione del SO). Il Turnaround time (Tempo di ricircolo) è il tempo trascorso l’avvio (l’immissione nel sistema) e la terminazione di un processo. Tempo di caricamento + Tempo di “Ready” + Tempo CPU + Tempo I/O. Il Tempo di attesa misura il tempo che un processo trascorre in attesa delle risorse a causa di conflitti con altri processi. È la penalità che si paga per condividere risorse ed è espressa come: Tempo di ricircolo – tempo di esecuzione In sostanza il tempo di attesa valuta la sorgente di inefficienza del processo. Il tempo di risposta nei sistemi time-sharing misura il tempo che trascorre dal momento in cui viene introdotto l’unico carattere al terminale all’instante in cui restituita la prima risposta, invece, nei sistemi real-time misura il tempo che trascorre dal momento in cui viene segnalato un evento esterno all’instante in cui viene eseguita la prima istruzione della relativa routine di gestione. Ad ogni processo durante la sua creazione viene assegnato un grado di priorità, lo scheduler sceglie sempre il processo pronto con priorità maggiore. La priorità può essere assegnata dal sistema o dall’utente e può essere di tipo statico o dinamico. La priorità dinamica può variare in funzione del valore iniziale, delle caratteristiche del processo, della richiesta di risorse e del comportamento durante l’esecuzione. Cassano Francesco Saverio  PRIORITÀ – EVENT DRIVER Il modello Event Driver applicato nei sistemi dove il tempo di risposta, soprattutto ad eventi esteri è critico. Caratteristiche: Il sistemista può influire sull’ordine in cui uno scheduler serve gli eventi esterni modificando le priorità assegnate ai processi. Le prestazioni sono dipendenti da un’accurata pianificazione nell’ assegnazione delle priorità Non è in grado di garantire il completamento di un processo in un intervallo di tempo finito dalla sua creazione. Lo scheduler deve sempre dare priorità ai processi nella lista di attesa con alta priorità, infatti ad ogni processo è associato un intero corrispondente al suo grado di priorità, solitamente più questo è basso, più è alta la sua priorità. Questo livello di priorità può essere deciso dal SO (Considerando grandezze come uso di memoria, file aperti, utilizzo di CPU e I/O) o esternamente al SO ovvero in base alla rilevanza del processo e la sua criticità. Il problema di questa soluzione è la Starvation ovvero che i processi a bassa priorità non vengono mai eseguiti. Una soluzione è l’Aging, ovvero al passare del tempo in stato di ready, il numero di priorità del processo aumenta. Per quanto riguarda il modo di decisione dello scheduler esistono due categorie distinte, senza prerilascio e con prerilascio. Senza prerilascio, in questo caso, una volta che il processo è in esecuzione, continua la sua esecuzione fino alla terminazione o finché si blocca in attesa di I/O o se richiede altri servizi del sistema operativo. Con prerilascio, il processo al momento in esecuzione può essere interrotto e spostato in stato Ready dal sistema operativo. La decisione di può essere presa quando arriva un nuovo processo, quando avviene un interrupt che trasferisce un processo dallo stato di blocked allo stato ready, oppure periodicamente in base all’interruzione di clock. I PRO del prerilascio è che nessun processo può monopolizzare il processore ma come contro i processi che condividono dati sono più avvantaggiati rispetto ai processi che gestiscono i meccanismi di sincronizzazione. Ricordiamo che il Dispatcher è il modulo del So che passo il controllo della CPU al processo selezionato dallo scheduler a breve termine attraverso lo switch del contesto, lo switch del modo utente/kernel e il salto alla locazione opportuna del programma utente (contenuta nel PCB) per farlo ripartire. Il Dispatch latency è il tempo che il dispatcher usa per fermare un processo e far partire un altro. First Come First Served – FCFS La più semplice strategia di scheduling è il First Come First Served o First in First Out, non appena un processo diventa Ready, s’inserisce nella coda dei processi Ready. Quando il processo al momento in esecuzione si sospende, il più vecchio processo nella coda dei processi Ready è selezionato per l’esecuzione. Una situazione ideale che i processi più rapidi vengano eseguiti per primi e quelli più lenti per ultimi, ma ciò non sempre accade è può succedere che un processo veloce attenderà molto tempo prima di poter passare in stato di running. Infatti, il problema di questa strategia consiste nel fatto che tende a favorire i processi processor bound (Anche detti CPU Bound) a discapito di quelli I/O. È un sistema senza prerilascio. Cassano Francesco Saverio  Round Robin – Time Slice Un modo per superare i problemi del FIFO è adoperare il prerilascio basato sul clock. La strategia più semplice che usa questa idea è il Round Robin conosciuto anche come Time Slice. Quando avviene un’interruzione il processo in esecuzione ritorna nella coda dei Ready e il successivo processo è selezionato con il FIFO. Quando il tempo sarà molto grande, l’utilizzo del FIFO è ottimale ma con un tempo molto corto, ci sarà un incremento del numero di context switch. Un inconveniente di questa tecnica è la suddivisione non equa per i processi CPU-bound. Infatti, quando un processo I/O bound si blocca, verrà sostituito da un altro processo e ritornerà in coda di Ready solo quando il processo ha ricevuto il suo evento. Invece un processo CPU-Bound una volta terminato andrà direttamente nella coda dei Ready. In più un processo CPU- Bound sarà costretto ad andare più volte in esecuzione prima di terminare il suo compito. Highest Response Ratio Next Viene calcolato per ogni processo il responde ratio, e viene mandato in esecuzione il processo con il valore più alto. Il response ratio viene calcolato ponendo: w - tempo speso in coda di Ready (attesa della disponibilità del processore). s - tempo di servizio previsto. si definisce il Response Ratio come (w+s)/s. Quando il processo in esecuzione termina o si blocca, si passa al processo Ready con il più grande rapporto (quando il processo entra in Ready per la prima volta il suo rapporto è uguale ad 1), vengono avvantaggiati i processi con un denominatore più piccolo, quindi i processi più brevi ma con il passare del tempo, se un processo non viene servito, aumenterà il suo rapporto e quindi prima o poi supererà i processi più corti. Shortest Process Next SPN Un'altra strategia è il Shortest Process Nest (SPN), ovvero il processo che ha un tempo di esecuzione minore, viene eseguito per primo. Il SPN è ottimale perché favorisce il tempo medio di attesa minimo, per un dato set di processi. Questa strategia è solitamente utilizzata nello scheduler a lungo termine. Questa strategia sfavorisce i processi CPU-Bound in quanto il tempo di esecuzione per questi ultimi è maggiore e quindi potrebbe portare alla starvation. Il SPN è una strategia senza prerilascio. Se utilizziamo il prerilascio, se arriva un nuovo processo con una sequenza di CPU minore del tempo necessario per la conclusione del processo attualmente in esecuzione, si ha il prerilascio della CPU a favore del processo appena arrivato. Questo schema è anche noto come Shortest Remaining Time First (SRTF). Shortest Remaining Time First (SRTF) La strategia del SRTF è una versione del SPN con prerilascio, in questo caso lo scheduler sceglie sempre il processo che ha il minor tempo di esecuzione rimanente. Quando un nuovo processo è inserito nella coda dei processi Ready, può avere un tempo rimanente più breve di quello del processo in esecuzione al momento, di conseguenza, lo scheduler può dover prerilasciare ogni volta che un nuovo processo diventa Ready. Come il SPN il sistema deve tener conto di una stima del tempo di elaborazione per eseguire la funzione di selezione e c’è il rischio di starvation per i processi più lunghi. Cassano Francesco Saverio  Schedulazione a code multiple La coda di Ready è suddivisa in sotto-code, foreground (interactive) e background (batch) ed ogni coda ha il suo algoritmo di schedulazione. Le varie code verranno schedulate a loro volta ad esempio mediante un meccanismo di prelazione, condendo priorità più alta alle code foreground, causano però eventuali problemi di Starvation alle code batch, per questo motivo si può concedere un tempo ad ogni coda (time slicing) concedendo per esempio 80% alla coda foreground e 20% alla coda batch. Schedulazione a code multiple con feedback Un processo può essere spostato da una coda all’altra (implementazione dell’Aging). Code Multilevel Feedback definite dai seguenti parametri: Numero di code. Algoritmo di scheduling per ogni coda. Metodi usati per l’up grading e il down grading di ogni processo. Esempio: Tre code: 1. Q0 –RR con time quantum 8 milliseconds. 2. Q1 –RR con time quantum 16 milliseconds. 3. Q2 –FCFS. Scheduling 1. Un nuovo processo entra nella coda Q0 (RR-8). 2. Quando ottiene la CPU, la impegna per 8 ms. Se non termina entro gli 8 ms è spostato in Q1. 3. Il processo in Q1 viene nuovamente servito con politica RR ma riceve la CPU per ulteriori 16 ms. 4. Se ancora non termina viene spostato in Q2. 5. In Q2 pu essendoci un FCSS, sono arrivati i jobs ottimizzati ed ordinate in modo da andare in sequenza in modo ottimo. Schedulazione MULTIPROCESSORE Per par parlare della schedulazione in sistemi multiprocessore dobbiamo prima classificare le tipologie di sistemi multiprocessore. In primis abbiamo sistemi di computer con processori debolmente accoppiati o distribuiti o cluster, in questo caso ogni processore ha la sua memoria e i propri canali di I/O. Poi abbiamo sistemi di computer con processori specializzati per funzioni controllati da un processore master a cui fornisce servizi (Esempio I/O processor. Infine, abbiamo i sistemi di computer multiprocessore con processori fortemente accoppiati, in questo caso i processori condividono la memoria centrale e sono sotto il controllo del SO. Un buon metodo per caratterizzare i multiprocessori e poterli confrontare con le altre architetture è considerare la granulità della sincronizzazione, o grado di sincronizzazione, tra i processi in un sistema. È possibile distinguere 4 categorie ovvero Parallelismo indipendente, Parallelismo a grana grossa e molto grossa, Parallelismo a grana media e Parallelismo a grana fine. Il Parallelismo indipendente è una strategia dove non c’è sincronizzazione esplicita tra i processi e ogni processo è un job separato indipendente. Questo tipo di sistema è usato in un sistema time sharing, ogni utente esegue una particolare applicazione, il multiprocessore fornisce lo stesso servizio di un monoprocessore multiprogrammato, ma essendo disponibili più processori, il tempo di risposta medio agli utenti sarà minore. Cassano Francesco Saverio Il Parallelismo a grana grossa o molto grossa c’è una sincronizzazione ma molto bassa. Questo genere di situazione viene facilmente trattata come un insieme di processi concorrenti eseguiti su un monoprocessore multiprogrammato e può essere supportata su un multiprocessore, con nessuno o pochi cambiamenti al software dell’utente. Il Parallelismo a grana media i thread dei processori sono altamente sincronizzati tra loro ma è necessario gestire al meglio lo scheduling poiché esso può influenzare notevolmente le prestazioni. Il Parallelismo a grana fine è una strategia sperimentale dove ogni applicazione è ad un elevato livello di sincronizzazione. Assegnazione dei processi ai processori Se i processori sono tutti uguali, ovvero nessuno dei processori ha dei vantaggi fisici rispetto agli altri (SMP), possono essere trattati come un pool di risorse e i processi possono essere eseguiti su ogni processore. Assegnazione permanente (Statica) In questo modo un processo viene sempre eseguito su uno specifico processore generando una coda a breve termine dedicata per ogni processore, questa strategia provoca poco overhead nella gestione dello scheduling. Un processore può rimanere inutilizzato a seguito di una coda vuota mentre un altro ha un carico arretrato. Assegnazione Dinamica Una differenza rispetto alla assegnazione statica è la gestione della coda, infatti quest’ultima è globale, ovvero tutti i processi finiscono in una coda comune per entrambi i processori, in più se le tabelle PCB sono in RAM o in CACHE non c’è alcuni svantaggio o perdita di prestazioni. In entrambi i casi bisogna trovare un sistema per assegnare i processi ai processori, per questo motivo si possono utilizzare due approcci: Master/Slave e alla pari (Peer). Nella strategia Master/Slave, le funzioni kernel sono sempre eseguite su un singolo processore, gli altri processori possono solo seguire processi di tipo utente ed il master è responsabile dello scheduling del job, se lo slave ha bisogno di un servizio come per esempio chiamate I/O, dovrà richiederle al master ed attendere una sua risposta. Il problema di questa strategia è che se il master si blocca, l’intero sistema è bloccato e il master può eventualmente diventare un collo di bottiglia. Nella strategia Peer (Tra pari), il sistema operativo è eseguito su ogni processore ed ogni processore fa fronte il proprio scheduling. In questa strategia il processore deve stare sempre attento a non permettere a due processori di scegliere lo stesso processo. Scheduling dei threads Con i thread il concetto di esecuzione è separato dal resto della definizione di processo; un’applicazione può essere implementata come un insieme di thread, che cooperano e sono eseguiti nello stesso spazio di indirizzo con correntemente. Nei sistemi multiprocessori i thread possono essere utilizzati per sfruttare il vero parallelismo in un’applicazione e se i vari thread di un’applicazione sono eseguiti simultaneamente su processori separati, sono possibili guadagni evidenti nelle prestazioni. Per lo scheduling multiprocessore di thread e l’assegnazione dei processori ci sono principalmente quattro approcci generali ovvero il Load sharing (condivisione del carico), il gang scheduling (schedulazione a gruppi), l’assegnazione dedicata e lo Scheduling Dinamico. Con il Load Sharing, i processi non sono assegnati a specifici processori e si mantiene una coda globale di thread pronti, ed ogni processore, quando è in ozio, seleziona un thread dalla coda. Con il Gang scheduling, viene schedulato un insieme di thread correlati, da eseguire su insieme di processori, sulla base di un processo per processore. Cassano Francesco Saverio Con lo Scheduling Statico, un gruppo di processori viene dedicato ad una applicazione fino al suo termine. Quando una applicazione è schedulata ognuno dei suoi threads viene assegnato ad un processore fino al termine dell’esecuzione dell’applicazione. Il problema di questa strategia è che alcuni processori potrebbero rimanere fermi ma i principali vantaggi sono che i cambi di contesto si riducono al minimo per tutta l’esecuzione di un programma. Con lo Scheduling dinamico il numero dei threads di un processo può essere modificato dinamicamente. Il SO può modificare il carico per migliorare l’utilizzazione dei processori e il SO e l’applicazione collaborano nell’attività di scheduling, in questo caso il SO è responsabile della assegnazione dei processori ai processi e l’applicazione decide quali threads eseguire, quali sospendere ecc. Il SO assegna il processore ad un nuovo processo se tale processore è in idle e assegna un processore ad un nuovo processo requisendolo ad uno che ne detiene già più di uno. Se una richiesta non può essere soddisfatta, essa viene sospesa fino a quando un processore non diventa disponibile. Assegna il processore ad un processo che non ha correntemente alcun processore allocato. THREAD SMP MICROKERNEL Un processo è contemporaneamente un elemento che possiede delle risorse, ovvero uno spazio di indirizzamento virtuale che contiene l’immagine del processo e saltuariamente può richiedere ulteriore memoria e il controllo di altre risorse, quali canali di I/O, dispostivi e file, ma anche un elemento che viene allocato, infatti un processo è una traccia di esecuzione entro uno o più programmi. Tale esecuzione può essere alternata con quella di altri processi, quindi un processo ha uno stato di esecuzione (Running, ready ecc.) e una priorità di schedulazione. Il sistema operativo ha il compito di schedulare e allocare i processi. In molti sistemi operativi queste due caratteristiche costituiscono l’essenza di un processo. Queste due caratteristiche possono essere gestite separatamente dal sistema. Per distinguerle, l’elemento che viene allocato viene chiamato Thread (o Lighweight processo ovvero processo leggero) mentre l’elemento che possiede le risorse è chiamato processo o task. In pratica un Thread è una traccia in esecuzione in uno o più programmi. MULTI-THREADING Il Multi-Threading è la capacità del sistema operativo di gestire thread di esecuzioni multiple per ogni processo. L’approccio tradizionale dove il concetto di thread non è evidenziato, viene chiamato Thread Singolo un esempio è MS-DOS. Invece UNIX supporta Processi Multipli a Singolo Thread. Un motore runtime di Java è un esempio di Processo Singolo a Multi Thread, invece i sistemi operativi moderni sono sistemi basati sui Molti Processi a Multi Thread. In un sistema a singolo thread, la rappresentazione di un processo contiene il suo Process Control Block e il suo spazio di indirizzamento utente, nonché lo stack utente e lo stack del kernel, per controllare il comportamento delle chiamate di procedura e i ritorni da chiamata durante l’esecuzione del processo. Mentre il processo è in esecuzione, esso controlla i registri del processore e il contenuto dei registri viene salvato quando il processore non è in esecuzione. In un ambiente Multi Thread, ogni processo ha associato un solo PCB (Process Control Block) e un solo spazio di indirizzamento utente ma ogni thread ha un proprio stack, un blocco di controllo privato contenente l’immagine dei registri, la priorità e altre informazioni relative al thread. Quindi, tutti i thread componenti un processo condividono lo stato e le risorse di quel processo, risiedono nello stesso spazio di indirizzamento e hanno accesso agli stessi dati. Quindi, quando un thread altera un dato in memoria, gli altri thread vedono il risultato quando accedono a quel dato. Se un thread apre un file con privilegi di lettura, gli atri thread dello stesso processo possono leggere quel file. Il vantaggio chiave dei thread è nelle Cassano Francesco Saverio prestazioni, la creazione di un nuovo processo e lo stesso vale per la terminazione di un thread e il cambio tra due thread dello stesso processo. Degli esempi di utilizzo di thread possono essere: L’esecuzione in foreground e background, infatti in un foglio di calcolo ogni thread controlla una funzione particolare del programma, per esempio la gestione degli input degli utenti o la funzione di stampa a video. L’elaborazione asincrona infatti immaginiamo un programma di editor di testo che ogni minuto scrive sul disco il file, per evitare problemi eventuali dovuti alla sospensione di corrente. L’aumento della velocità, infatti in un sistema multithread può calcolare dati e allo stesso tempo può leggere dei nuovi e in un sistema multiprocessore queste operazioni possono avvenire parallelamente. Programmi di organizzazione, che traggono molti benefici poiché composti da molteplici attività di input e output e grazie ad i thread sono facili da progettare. Gli svantaggi dei thread sono principalmente due, ovvero quando un processo viene sospeso, tutti i thread vengono sospesi contemporaneamente perché si deve liverare spazio in memoria e tutti i thread utilizzano lo stesso spazio di memoria condivisa e infine quando un processo viene terminato, richiede che tutti i thread vengano terminati. SPIEGAZIONI ESEMPI SLIDE Esempio 1: Programma di video-scrittura, gestione e pubblicazione di pagine sul desktop. (Aldus Page Maker). Un esempio d’uso dei thread è l’applicazione Aldus PageMaker, esso è un programma per la scrittura, progettazione e produzione per il desktop publishing. I thread sono sempre attivi: un thread di gestione degli eventi, un thread per ridisegnare lo schermo e n thread di servizio. Generalmente, la gestione delle finestre rallenta se l’elaborazione di qualche messaggio di input richiede troppo tempo, infatti nessun messaggio deve richiedere un tempo di elaborazione superiore a 0.1 secondi. Per rispettare questo criterio, le operazioni complesse di PageMaker (Stampa-lettura dei dati e disposizione del testo) sono effettuate dal thread di servizio, che si occupa anche di gran parte dell’indicizzazione del programma: in questo modo utilizza il tempo durante il quale l’utente chiama la finestra di dialogo per creare nuovo documento o aprire un documento esistente. Un altro thread aspetta i nuovi messaggi. Sincronizzare il thread di servizio e il thread che gestisce gli eventi è complicato, perché un utente può continuare a scrivere con la tastiera o muovere il mouse, attivando il thread di gestione degli eventi, mentre il thread di servizio è occupato. Quando avviene questo conflitto il PageMaker filtra questi messaggi e accetta solo alcuni messaggi base come per esempio il ridimensionamento della finestra. Quando il thread di servizio completa un compito, invia un messaggio, fino al quel momento, l’attività dell’utente di PageMaker è limitata. Il programma indica questo stato disabilitando le voci di menu e mostrando un cursore “busy”. L’utente è livero di passare a un’altra applicazione e quando il cursore “busy” si posta sopra ad un’altra finestra, riprende l’aspetto normale per quell’applicazione. Cassano Francesco Saverio  Esempio 2: Server, Remote Procedure Call (RPC) La prima immagine raffigura una situazione in un processo ad un solo thread. La richiesta di accesso ai 2 server viene effettuata separatamente e non nello stesso modello. Nella seconda immagine ogni thread si occupa di una singola chiamata al server, in questo modo possiamo quasi avviare nello stesso momento le due chiamate e guadagnare tempo. STATO DEI THREAD Analogamente ai processi, anche i thread sono contraddistinti da stati, in particolare i thread possono assumere lo stato di Ready, Running e Blocked. A differenza dei processi, non è presente lo stato di Suppsend, perché se un processo viene scaricato dalla memoria centrale lo stesso avviene per TUTTI i suoi thread. Ci sono quattro operazioni base associate ad un cambiamento di thread: Creazione, ovvero quando un processo viene generato, viene generato anche un thread ed un thread può generare un altro thread per lo stesso processo e vengono inserite tutte le info nel Thread Controlo Block (TCB) l’equivalente PCB per i thread. Blocco, quando un thread è in attesa di un evento entra in fase di blocked e vengono salvati il Program Counter e lo stack pointer. Sblocco, all’occorrenza dell’evento su cui il thread era bloccato, io thread passa in stato di Ready. Terminazione, ovvero quando un thread completa il suo compito, il suo contesto per i registri e i suoi stack vengono deallocati. CATEGORIE DI THREAD Ci sono due categorie di implementazione di thread, ovvero Thread a livello utente (ULT) e Thread a livello Kernel (KLT). THREAD A LIVELLO UTENTE Tutto il lavoro della gestione dei thread viene effettuato dall’applicazione e il kernel non sa della esistenza dei thread. Qualunque applicazione può essere programmata con thread multipli utilizzando librerie per i thread che consentono di creare e distruggere thread, scambiare messaggi e dati fra thread per schedulare la gestione dei thread e per salvare e ricaricare i contesti del thread. In ogni momento quando viene creata una applicazione, viene generato un nuovo thread associato a quella applicazione ed essa può generare Cassano Francesco Saverio ulteriori thread utilizzando “spawn” un’utilità della libreria per i thread, crea la relativa tabella e passa il controllo ad uno degli altri thread dello stesso processo che si trova nello stato di Ready, utilizzando qualche algoritmo di programmazione. Quando un processo utente viene passato il controllo alla libreria, il contesto del thread corrente viene salvato e quando il controllo passa dalla libreria ad un thread, il contesto del thread viene ristabilito (Il contesto è formato dal PC e gli stack pointer). È da notare che quando un processo è in stato di running, anche un thread è in stato di running ma quando questo processo viene bloccato, il thread per la libreria continua ad essere in stato di running (anche se non effettivamente in esecuzione sul processore fisico). Ci sono vari vantaggi nell’utilizzare i thread al livello utente. 1. In primis il cambio thread non richiede privilegi in modalità kernel, poiché tutte le attività avvengono nello spazio utente. Ciò comporta al risparmio del sovraccarico dovuto ai cambiamenti tra le due modalità. 2. Ogni applicazione può utilizzare un proprio algoritmo di schedulazione in base alle proprie esigenze e quindi ottimizzare l’efficienza di esecuzione. 3. Lavorando con thread a livello utente, si può implementare questa strategia su qualsiasi sistema operativo perché non bisogna modificare il kernel sottostante, infatti le librerie sono al livello di applicazione. Ovviamente questa strategia comporta anche degli svantaggi: 1. In un tipico sistema operativo, la maggior parte delle chiamate di sistema comporta un blocco. Così quando un thread esegue una chiamata di sistema, non viene bloccato solo quel thread ma tutti quelli appartenenti allo stesso processo. 2. Una applicazione multihread non può sfruttare il multiprocessing, infatti un kernel assegna un solo processo ad un solo processore alla volta, quindi in un dato istante, un solo thread per processo è in esecuzione. Quindi si ha un multiprocessing solo a livello di applicazione. Si possono aggirare questi problemi scrivendo un programma che sfrutta processi multipli e non thread multipli ma questo eliminerebbe l’utilità dei thread, un’altra soluzione è di utilizzare la strategia jacketing, ovvero convertire una chiamata bloccante di sistema in una chiamata bloccante a livello di thread, quindi una chiamata bloccante diventa una chiamata non bloccante, in questo modo si verifica se il dispositivo è bloccato, in caso affermativo l’attuale thread passa in ready e passa in running un altro thread. THREAD A LIVELLO KERNEL In caso di KLT puro, tutto il lavoro di gestione dei thread viene effettuato dal kernel. Nella sezione dell’applicazione, non sarà più presente il codice per la gestione dei thread ma solo le API (Application Programming Interface, ovvero interfaccia per la programmazione delle applicazioni). In questo modo il kernel mantiene info su il contesto del processo, il contesto dei thread, e lo scambio dei messaggi tra i threads. Se un thread di un processo x è bloccato, un altro thread dello stesso processo può essere eseguito o un thread di uno stesso x possono essere schedulati su diversi processori. L’unico svantaggio è l’overhead, ovvero il trasferimento del controllo da un thread ad un altro richiede l’intervento del kernel e quindi una perdita di tempo. Cassano Francesco Saverio  APPROCCI MISTI In un sistema misto, la creazione dei Thread è effettuata completamente nello spazio utente e lo stesso accada per la schedulazione e la sincronizzazione in un’applicazione. Nella zona kernel esistono altri thread che sono in stretta corrispondenza dei thread a livello utente. In questo approccio si necessita una comunicazione fra kernel e libreria dei thread (creati a livello utente). Ambienti distribuiti: i thread possono spostarsi tra più calcolatori (threads in Cloud) MICRO KERNEL Il microkernel è un piccolo nucleo del sistema operativo che racchiude tutte le funzionalità essenziali per la gestione di una macchina e le funzionalità meno essenziali e le applicazioni sono costruite sopra al microkernel e vengono eseguite in modalità utente. Il microkernel differisce dai sistemi stratificati dove ogni parte comunica solo con quelle adiacenti, infatti il microkernel si pone alla base di tutto e ogni funzione deve passare solo dal kernel (Creando una sottospecie di comunicazione Client/Server). Il problema del microkernel è il passaggio continuo tra gli stati (utente/kernel e viceversa), questo problema si può arginare aumentato il numero di funzioni del microkernel o riducendo il numero. I vantaggi del Micro Kernel sono molteplici: L’interfaccia uniforme, ovvero i moduli usano le stesse interfacce per le richieste al microkernel. L’Estensibilità, ovvero l’introduzione di nuovi servizi o modifiche non richiedono modifiche al microkernel. La Flessibilità, infatti a seconda delle applicazioni certe caratteristiche possono essere ridotte o potenziate per soddisfare al meglio le richieste dei clienti. La Portabilità, infatti il cambio dell’hardware comporta solo ed unicamente la modifica del microkernel. L’Affidabilità, infatti lo sviluppo di piccole porzioni di codice ne permette una migliore ottimizzazione e test. Il Supporto ai Sistemi Distribuiti, ogni servizio è identificato da un numero nel microkernel e una richiesta da client non è necessario che sappia dove si trova il server in grado di soddisfarla. Messaggistica gestione del microkernel. Ricapitolando il microkernel deve contenere le funzioni che dipendono direttamente dall’hardware, le funzioni per la gestione dei processi e la gestione primitiva della memoria. Una delle funzionalità minime del microkernel è la gestione primitiva della memoria, ovvero il controllo di indirizzamento per rendere possibile l’implementazione della protezione a livello di processo. Un modello esterno al microkernel mappa pagine virtuali in pagine fisiche. Il mapping è conservato in memoria Cassano Francesco Saverio principale. Una applicazione che accede ad una pagina che non si trova in memoria genera una page fault. L’esecuzione passa al microkernel che invia un messaggio al paginatore comunicando la pagina richiesta e la pagina viene caricata (Il paginatore e il kernel collaborano per il mapping memoria reale-virtuale), poi quando viene caricata la pagina il pager invia un messaggio all’applicazione. Il microkernel riconosce gli interrupt ma non li gestisce direttamente, infatti li trasforma in messaggi a livello utente, che invia al processo che gestisce l’interrupt. La comunicazione tra processi avviene in questo modo, il messaggio è formato dall’intestazione (ovvero il mittente e il ricevente) il corpo del messaggio (ovvero i dati del messaggio) e il puntatore + le info di controllo (informazioni di controllo del processo, blocco dati). Ad ogni processo è associata una porta amministrata dal Kernel e la Capability list indica chi può inviare messaggi. SMP Un sistema multiprocessore simmetrico (Symmetric multiprocessor system - SMP) è un sistema multiprocessore con una memoria centralizzata condivisa chiamata memoria principale, operante sotto un unico sistema operativo con due o più processori omogenei. Un sistema operativo SMP gestisce i processori e le altre risorse in maniera tale che la visione dell’utente sia un sistema monoprocessore con multiprogrammazione, infatti, un utente può realizzare applicazioni che fanno uso di processi o thread multipli senza preoccuparsi del numero di processori disponibili. Cosi un sistema operativo multiprocessore deve fornire tutte le funzionalità di un sistema di multiprogrammazione, più la gestione di processori multipli. Le caratteristiche fondamentali per il progettista sono le seguenti: Concorrenza tra Processi e Thread del Kernel: l’esecuzione contemporanea su diversi processori non deve compromettere le strutture di gestione del SO ed evitare gli stalli. Schedulazione: necessità di evitare conflitti. Sincronizzazione: mutua esclusione e ordinamento degli eventi Gestione della memoria condivisa. Tolleranza ai guasti: in caso di “perdita di un processore” devono essere aggiornate le strutture di controllo del SO. CONCORRENZA: MUTA ESCLUSIONE E SINCRONIZZAZIONE I temi centrali della progettazione di un sistema operativo sono connessi con la gestione di processi e thread. La Multiprogrammazione, ovvero la gestione di processi multipli in un sistema a singolo processore. In partica tutti i sistemi operativi recenti forniscono la multiprogrammazione. Il Multiprocessing, ovvero la gestione di processi multipli in un sistema multiprocessore. I Processi Distribuiti, ovvero la gestione di processi multipli che sono eseguiti su sistemi distribuiti (un esempio sono i cluster). La competizione tra processi (threads) per ottenere e condividere risorse come la CPU, la Memoria, i canali di I/O, i Files ecc… Cassano Francesco Saverio  CONCORRENZA: TERMINOLOGIA Sessione Critica: Porzione di codice all’interno di un processo (thread) che richiede accesso a risorse condivise. Deadlock: Situazione nella quale due o più processi sono impossibilitati dal procedere poiché sono in attesa l’uno dell’altro. Livelock: situazione nella quale due o più processi cambiano continuamente il proprio stato a causa del cambiamento di stato degli altri (senza fare alcun lavoro utile). Mutua esclusione: requisito per il quale, quando un processo è nella propria sezione critica, nessun altro processo può essere nella propria sezione critica se questa fa riferimento a risorse condivise con il primo processo. Race condition: situazione nella quale thread o processi leggono e scrivono un dato condiviso e il risultato dipende dalla loro velocità reciproca. Starvation: situazione nella quale un processo non riceve mai l’utilizzo di una risorsa e viene costantemente scavalcato da altri processi. VANTAGGI E PROBLEMI DERIVANTI DALLA CONCORRENZA Vantaggi I benefici sulla esecuzione nonostante il sovraccarico (context switching). Migliore utilizzazione delle risorse. Problemi I principali problemi si presentano quando trattiamo il singolo processore, infatti un primo problema è la condivisione pericolosa, ovvero l’ordine delle operazioni di letture e scrittura su aree di memoria condivise. Un altro problema è la difficoltà nell’assegnare le risorse ai processi in maniera ottimale e la difficoltà nella rilevazione degli errori nel codice e dei conflitti di interlacciamento. Per quanto riguarda gli SMP, ci sono gli stessi problemi di un calcolatore a singolo processore (Una interruzione può fermare l’esecuzione di un processo in un qualsiasi istante), VI è un interlacciamento di esecuzione tra i processi paralleli. Un modo per risolvere tutti questi problemi è la mutua esclusione. MUTUA ESCLUSIONE I meccanismi che provvedono alla mutua esclusione devono garantire i seguenti requisiti: 1. Un solo processo alla volta deve accedere alla sezione (o risorsa) critica. 2. Un processo fuori della sezione critica non deve interferire con il processo nella sezione critica. 3. Ogni processo deve poter accedere dopo un tempo finito di attesa in coda alla risorsa critica (no stallo o starvation). 4. Se nessun processo è nella sezione critica, un processo deve poter entrare nella sezione critica senza attese. 5. Non ci devono essere supposizioni sulla velocità di esecuzione relativa dei processi. 6. Il tempo di permanenza nella sezione critica è (de)finito. Ci sono vari metodi per rispettare questi meccanismi, ovvero tramite approcci software, ovvero i processi, senza ausilio del Sistema Operativo o del linguaggio di programmazione, devono coordinarsi tra loro (Algoritmo di dekker), ciò comporta un aumento del tempo di esecuzione ed errori frequenti. Un altro approccio è attraverso l’ausilio di particolari istruzioni macchina (test-set, scambio), questi comandi Cassano Francesco Saverio riducono situazioni di sovraccarico ma non sono soddisfacenti. Un ultimo meccanismo è il supporto del sistema operativo o del linguaggio di programmazione attraverso tecniche di scambio di messaggi (Inter Processor Communication), semafori e monitor. ALGORITMO DI DEKKER Una soluzione per risolvere il problema della mutua esclusione è l’algoritmo di dekker. Ogni processo per entrare nella propria sezione critica deve considerare alcuni fattori. Ogni processo ha una propria variabile flag che indica se vuole andare o meno nella sezione critica (TRUE o FALSE). Esiste una variabile condivisa turno che specifica chi ha il diritto di insistere nel tentativo di entrare nella propria sezione critica. Abbiamo 2 processi, P0 e P1. P0 vuole entrare nella sezione critica (Viene posto il suo flag pari a TRUE) P0 controlla il flag di P1 Se (il flag di P1 = FALSE) Allora P0 può entrare nella sezione critica Altrimenti P0 controlla la variabile turno Se (turno = 0) Allora P0 controlla periodicamente il flag di P1 e quando diventa FALSE, P0 entra nella sua sezione critica Altrimenti P1 va nella sua sezione critica e il flag di P0 diventa FALSE FINE FINE Questo algoritmo complesso permette il principio di mutua esclusione. SUPPORTO HARDWARE Una strategia di soluzione e implementazione del principio di mutua esclusione, è quello di lasciare al sistema operativo tale gestione. Infatti, in un sistema monoprocessore, i processi non vengono eseguiti parallelamente e quindi il principio di muta esclusione è garantito, ma un processo può essere interrotto per dar posto ad un altro, anche durante la permanenza nella sua sezione critica, creando non pochi problemi. Per evitare ciò, è possibile disattivare momentaneamente tutti gli interrupt, ovvero tutte le interruzioni che permettono il cambio di processo, in questo modo il processo può entrare liberamente nella sua sezione critica e quando ha terminato, gli interrupt vengono ripristinati. Questo approccio però ha dei problemi, in primis rallenta l’esecuzione generale del sistema, perché l’OS non può più interrompere a piacimento un processo e nei sistemi SMP, questo approccio non può funzionare (Poiché i processi possono essere eseguiti anche parallelamente). Esistono comunque delle soluzioni per l’approccio di questa filosofia con i sistemi SMP, ovvero istruzioni macchina speciali per l’accesso a locazioni di memoria in modo atomico (non interrompibile), ovvero il test and set e lo scambio (swap). Il test and set utilizza questa struttura: Cassano Francesco Saverio boolean TestAndSet (boolean *target) { boolean val = *target; *target = TRUE; return val; } Utilizzo di test and set per garantire la mutua esclusione sia lock una variabile boolean condivisa inizializzata a falso (la risorsa è libera). while (true) { while ( TestAndSet (&lock )) ; /* do nothing lock = FALSE; //rilascio … } Un'altra istruzione può essere lo swap: void swap (boolean *a, boolean *b) { boolean temp = *a; *a = *b; *b = temp: } L’utilizzo di swap per garantire la mutua esclusione, sia lock una variabile booleana condivisa inizializzata a FALSE. while (true) { key = TRUE; while (key == TRUE) swap (&lock, &key ); //in key torna false lock = FALSE; … } Cassano Francesco Saverio I principali vantaggi di utilizzo di questo set di istruzioni sono: Si può applicare a un qualsiasi numero di processi anche su multiprocessori a memoria condivisa. Si può usare per gestire più di una sezione critica, ciascuna con una propria variabile. I principali svantaggi sono: Attesa attiva (I processi consumano tempo di cpu) Starvation (la scelta di quale processo andrà nella sezione critica è arbitraria). Stallo o Es (Singolo processore) o P1 in sezione critica o P2 ha priorità più alta di P1 o P2 tenterà di accedere (tramite test and set o swap) alla risorsa bloccata da P1, nella sua attesa attiva non lascerà mai il posto a P1 che ha priorità più bassa. SEMAFORI Il semaforo è una particolare strategia risolutiva per la mutua esclusione. Esistono varianti del semaforo, una generica e una binaria. Nel caso dei semafori generici, si associa un semaforo ad ogni risorsa condivisa, successivamente, si inizializza la variabile del semaforo. Ogni volta che un processo vuole entrare nella sezione critica, richiama la funzione wait(), questa funzione decrementa la variabile del semaforo, se questa variabile diventa negativa, il processo viene messo bloccato (il valore assoluto di questa variabile è il numero di processi in attesa). Una volta che il processo è entrato nella sezione critica ed ha terminato il lavoro con essa, viene richiamata la funzione signal(), questa funzione incrementa il valore della variabile del semaforo e se il valore della variabile è negativo, uno dei processi bloccati sull’operazione di wait viene sbloccato. Il semaforo binario è identico solo che utilizza una variabile che può assumere unicamente il valore di 0 e 1. MONITOR I semafori sono potenti ma primitivi per la gestione della mutua esclusione, infatti la loro implementazione non è semplice (Infatti i semafori sono un tipo di implementazione a livello assembly). Una soluzione di più alto livello, e quindi più semplice, è il monitor che utilizza la programmazione ad oggetti. Infatti, in un sistema scritto ad oggetti, l’implementazione del monitor è molto più semplice, infatti basta rendere il monitor un oggetto dotato di certi privilegi. Con un monitor bisogna utilizzare anche variabili di condizione per utilizzarlo al meglio. Nel monitor abbiamo due funzioni wait() e singnal(), wait permette di inserire un processo in coda finché un altro processo non esegue la funzione singnal, infatti la funzione signal, quando richiamata, rimuove il processo dalla coda. Cassano Francesco Saverio  CONCORRENZA: STALLO e STARVATION STALLO Per prima cosa, introduciamo la definizione di stallo. Un insieme di processi è in stallo se ogni processo nell’insieme è in attesa di un evento che solo un altro processo nello stesso insieme può generare (Per evento generalmente si intende il rilascio di una risorsa). Quando un processo è in stallo non può passare in esecuzione, rilasciare risorse ed essere riattivato. Esistono delle condizioni che possono portare allo stallo. Condizioni necessarie ma non sufficienti (derivate direttamente dalla progettazione): Mutua esclusione, un solo processo alla volta può usare una risorsa. “Hold e Wait” – possesso e attesa, un processo può mantenere il possesso di una risorsa allocata mentre attende altre. Assenza di prerilascio, i processi non possono essere forzati a rilasciare in anticipo le risorse acquisite. Condizioni necessarie e sufficienti: Attesa circolare (evento che si può verificare e dipende dalla particolare sequenza di richieste e rilasci). o Applicabile almeno con due processi. o Ogni processo aspetta una risorsa occupata da un altro processo in attesa circolare. Vi sono varie strategie per evitare il problema dello stallo tra cui: 1. Ignorare il problema (algoritmo dello struzzo) a. Soluzione adottata dalla maggior parte dei SO (Unix e Windows). b. Soluzione ragionevole se lo stallo capita raramente o evitare lo stallo risulta molto costoso. c. Degrado delle prestazioni: Blocco totale del sistema e riavvio manuale. d. Compromesso tra convenienza e correttezza. 2. Prevenirlo: Progettare un SO in grado di evitare una situazione di stallo, tramite la negazione di una delle 4 condizioni. 3. Esclusione: Le tre condizioni necessarie sono permesse, un algoritmo verifica dinamicamente che una richiesta non produca una situazione di stallo. 4. Consentire il verificarsi di uno stallo, riservarlo e risolverlo. PREVENZIONE DELLO STALLO Un metodo per eliminare i problemi relativi allo stallo è cercare di prevenirlo attraverso diverse strategie. Per fare ciò si impongono vincoli sulla richiesta delle risorse, vi sono metodi indiretti (che prevengono il verificarsi di una delle tre condizioni necessarie) e metodi diretti (che prevengono il verificarsi dell’attesa circolare). Per quanto riguarda la mutua esclusione, un processo non deve mai attendere una risorsa condivisibile e devono essere possibili accessi multipli contemporanei alle risorse condivise (di fatto non applicabile come metodo). Per quanto riguarda il Hold and Wait, ogni processo deve richiedere all’inizio della sua esecuzione tutte le risorse e quando il processo entra in stato di blocked fino a quando tutte le richieste non vengono Cassano Francesco Saverio soddisfatte contemporaneamente, questo approccio ha dei problemi perché comunque il processo può andare in parte in esecuzione anche se non dispone di tutte le risorse disponibili e in più le risorse in suo possesso possono rimanere inutilizzate per molto tempo ed altri processi rimangono in attesa indefinita. Per quanto riguarda il prerilascio, ci sono due possibilità: 1. Un processo che non riesce ad ottenere le risorse di cui necessita, rilascia quelle che detiene per chiederle nuovamente in un istante successivo. 2. Il sistema operativo richiede il pre-rilascio delle risorse al processo che le detiene per assegnarle al richiedente (Approccio applicabile solo se lo stato della risorsa è facilmente salvabile (CPU), in ogni caso questo metodo non è applicabile nel caso di stampanti. Per quanto riguarda l’attesa circolare (metodo diretto), si definisce un ordine lineare (di numerazione) per tutte le risorse e se un processo richiede una risorsa R, successivamente potrà richiedere solo una risorsa che nell’ordine segue R, questo metodo può essere inefficiente. Esempio R i precede Rj se i= C (n+1)i + La sommatoria da n a k-1 delle richieste, per ogni i. Traduzione Il processo può essere avviato se e sole se è possibile (per ogni risorsa) soddisfare la sua richiesta e quelle dei processi correnti. Questa strategia non è ottimale perché si suppone che i processi richiedano le risorse nello stesso istante, in più le richieste devono essere note all’avvio del processo. RIFIUTO DI ALLOCAZIONE DELLE RISORSE In questa situazione, ritroviamo lo schema precedente di matrici. Lo stato del sistema può essere Sicuro, quando esiste almeno una sequenza di esecuzione dei processi che ne consente la terminazione senza incorrere in una situazione di stallo, Non sicuro quando si ha un rischio di stallo. Quando un processo richiede una risorsa disponibile, il sistema: Simula l’assegnazione delle risorse e l’aggiornamento dello stato, verifica che il nuovo stato sia uno stato sicuro, in caso positivo, il sistema Cassano Francesco Saverio assegna le risorse, in caso negativo rifiuta la richiesta e il processo viene bloccato fino a che la risorsa si rende disponibile. Osservazioni: Se le risorse del processo non sono immediatamente disponibili, allora il processo deve attendere la terminazione di un processo che rilascia un numero sufficiente di risorse, quando il processo termina, il processo in attesa può ottenere le risorse necessarie all’esecuzione e terminare a sua volta rilasciando le risorse detenute. In una situazione di stato sicuro non ha alcun problema di deadlocks, in uno stato non sicuro, c’è possibilità di deadlocks, l’avoidance assicura che il sistema non entri in uno stato non sicuro. È bene ricordare che uno stato non sicuro non rappresenta uno stato di stallo ma una situazione di possibilità di crearsi uno stallo. La strategia di esclusione dello stallo si basa sulla possibilità che uno stato non sicuro determini uno stallo. Questa strategia ovviamente comporta vantaggi e svantaggi. VANTAGGI: Non è necessario interrompere processi e riportarli in uno stato precedente (problema presente nelle strategie di rilevamento dello stallo). SVANTAGGI: Il numero massimo di risorse necessitate da ogni processo deve essere noto a priori (Prima dell’esecuzione). I processi devono essere indipendenti: l’ordine di esecuzione non deve essere vincolato a esigenze di sincronizzazione. Deve esserci un numero fissato di risorse da allocare. Quando un processo richiede risorse potrebbe essere posto in attesa. Quando un processo ottiene tutte le risorse di cui necessita, deve rilasciarle in un tempo finito. DEADLOCK DETECTION: RILEVAMENTE DELLO STALLO Le strategie per la prevenzione dello stallo sono molto conservative: risolvono il problema limitando l’accesso alle risorse e imponendo delle restrizioni ai processi. Invece le strategie di rilevamento dello stallo non limitano l’accesso alle risorse e non impongono restrizione alle azioni dei processi. Con il rilevamento dello stallo, quando è possibile le richieste vengono sempre soddisfatte e il sistema operativo esegue periodicamente un algoritmo per rilevare la presenza della condizione di attesa circolare e applica uno schema di recovery per risolvere lo stallo. Un comune algoritmo per il rilevamento dello stallo utilizza una matrice Assegnazione e il vettore Disponibili. Inoltre, si definisce una matrice Q, tale che qij rappresenta il numero di risorse di tipo j richieste dal processo i. L’algoritmo procede marcando i processi che non sono in stallo, all’inizio nessun processo è marcato. In seguito, si effettuano i seguenti passi: 1. Si marca ogni processo che una riga di tutti zero nella matrice Assegnazione. 2. Si inizializza il vettore W con il contenuto del vettore Disponibili. 3. Si cerca un indice i tale che il processo i non è marcato e la i-esima riga di Q è minore o uguale a W, cioè Qij