Sistemi Operativi Modulo I PDF

Sistemi Operativi Modulo I Secondo canale Corso di Laurea in Informatica La Gestione della Concorrenza Fabio De Gaspari Sapienza Università di Roma Dipartimento di Informatica slides by: Igor Melatti Roadmap Concetti basilari di concorrenza Mutua esclusione: supporto hardware Semafori Passaggio di messaggi Problema dei lettori/scrittori Equivalenze Processi Multipli Per i SO moderni, è essenziale supportare più processi in esecuzione multiprogrammazione multiprocessamento (multiprocessing) computazione distribuita (cluster) Grosso problema da affrontare: la concorrenza gestire il modo con cui questi processi interagiscono Multiprogramming Se c’è un solo processore, i processi si alternano nel suo uso (interleaving) Multiprocessing Se c’è più di un processore, i processi si alternano (interleaving) nell’uso di un processore, e possono sovrapporsi nell’uso dei vari processori (overlapping) Concorrenza Si manifesta nelle seguenti occasioni: Applicazioni multiple condivisione di tempo di calcolo Applicazioni strutturate per essere parallele estensione della progettazione modulare Struttura del sistema operativo gli stessi SO operativi sono costituiti da svariati processi o thread in esecuzione parallela Terminologia Operazione atomica una sequenza indivisibile di comandi nessun altro processo può vedere uno stato intermedio della sequenza o interrompere la sequenza Sezione critica parte del codice di un processo in cui c’è un accesso esclusivo ad una risorsa condivisa nessun altro processo che voglia accedere in modo esclusivo alla stessa risorsa può farlo Mutua esclusione requisito che impone che un solo processo sia in una data sezione critica (per risorsa condivisa) Corsa critica (race condition) violazione della mutua esclusione il risultato dipende da come i processi si alternano Terminologia Stallo (deadlock) situazione nella quale due o più processi non possono procedere con la prossima istruzione, perché ciascuno attende l’altro Stallo attivo (livelock) situazione nella quale due o più processi cambiano continuamente il proprio stato, l’uno in risposta all’altro, senza fare alcunché di “utile” Morte per fame (starvation) un processo, pur essendo ready, non viene mai scelto dallo scheduler Concorrenza: Difficoltà LA difficoltà: non si può fare nessuna assunzione sul comportamento dei processi e neanche su come funzionerà lo scheduler Condivisione di risorse es.: una stampante ma anche più semplice: 2 thread che accedono alla stessa variabile globale Gestione dell’allocazione delle risorse condivise diventa impossibile la gestione ottima ad es., un processo potrebbe richiedere un I/O e poi essere rimesso in ready prima di usarlo: quell’I/O va considerato locked oppure no? Difficile tracciare gli errori di programmazione spesso il manifestarsi di un errore dipende dallo scheduler e dagli altri processi presenti rilanciare l’ultimo processo spesso non riproduce lo stesso errore Esempio Facile void echo () { chin = getchar () ; chout = chin ; putchar ( chout ) ; } Esempio su Un Processore Process P1 Process P2.. chin = getchar () ;.. chin = getchar () ; chout = chin ;. chout = chin ; putchar ( chout ) ;.. putchar ( chout ) ;.. Esempio su Più Processori Process P1 Process P2.. chin = getchar () ;.. chin = getchar () ; chout = chin ; chout = chin ; putchar ( chout ) ;.. putchar ( chout ) ;.. Restrizione all’Accesso Singolo Si supponga di far sı̀ che dentro la funzione echo ci possa entrare solo un processo alla volta l’intera funzione echo viene vista come una risorsa condivisa P1 ci entra per primo P2 ci prova ma viene bloccato finché P1 non finisce A quel punto, P2 viene riesumato e può essere completato Niente più comportamenti indesiderati → occorrono meccanismi di protezione Race Condition Si ha una corsa critica quando: più processi o thread leggono e scrivono su una stessa risorsa condivisa lo fanno in modo tale che lo stato finale della risorsa dipende dall’ordine di esecuzione dei detti processi e thread come prima: il contenuto di chin, e quindi di cosa viene poi scritto su monitor, dipende dal processo che esegue l’assegnamento per ultimo In particolare, il risultato può dipendere dal processo o thread che finisce per ultimo Sezione critica è la parte di codice di un processo che può portare ad una corsa critica Per Ciò che Riguarda il SO Quali problemi di progetto e gestione sorgono dalla presenza di concorrenza? Il SO deve tener traccia di vari processi allocare e deallocare risorse (processore, memoria, file, dispositivi di I/O) proteggere dati e risorse dall’interferenza (non autorizzata) di altri processi assicurare che processi ed output siano indipendenti dalla velocità di computazione (ovvero dallo scheduling) “indipendenti” da intendere cum grano salis rispetto alle specifiche di ciascun processo Interazione tra Processi Comunicazione Relazione Influenza Problemi di Con- trollo Nessuna (ogni Competizione Risultato di un processo Mutua esclusione; processo pensa indipendente dagli altri; deadlock; starva- di essere solo) Tempo di esecuzione di un tion processo dipendente dagli altri Memoria condi- Cooperazione Risultato di un pro- Mutua esclusione; visa (i processi cesso dipendente deadlock; starva- sanno che dall’informazione data tion; coerenza dei c’è qualche da altri; Tempo di ese- dati altro processo) cuzione di un processo dipendente dagli altri Primitive di co- Cooperazione Risultato di un pro- Deadlock; starva- municazione (i cesso dipendente tion processi sanno dall’informazione data anche i PID di da altri; Tempo di ese- alcuni altri pro- cuzione di un processo cessi) dipendente dagli altri I Processi e la Competizione per le Risorse Problema principale per i processi del primo tipo ovvero, ogni processo pensa solo a sé ma per l’accesso alle risorse deve fare una richiesta al sistema operativo (tramite syscall) Tre problemi di controllo principali: Necessità di mutua esclusione sezioni critiche Deadlock Starvation Mutua Esclusione per Processi in Competizione Basta che chiamino una syscall che fa tutto lei: entra nella sezione critica, fa l’operazione, esce Tuttavia, non è sempre possibile: se occorre accedere ad una risorsa che potrebbe essere condivisa con altri processi, occorre fare una richiesta esplicita di “bloccaggio” della risorsa E si ricade nel caso dei processi cooperanti Mutua Esclusione per Processi Cooperanti Gli stessi processi devono essere scritti pensando già alla cooperazione usando opportune syscall (ad es.: quelle sui semafori) devono preoccuparsi di scrivere entercritical ed exitcritical le specifiche dei processi potrebbero richiedere comportamenti particolari Deadlock Nasce dalla gestione della mutua esclusione Esempio di deadlock A richiede accesso prima alla stampante e poi al monitor B il contrario capita che lo scheduler faccia andare B in mezzo alle 2 richieste di A quel tanto che basta per fargli richiedere il monitor le successive richieste (del monitor per A e della stampante per B) non possono essere soddisfatte A e B restano bloccati per sempre eppure, è tutto avvenuto legalmente: la mutua esclusione non è violata Starvation Come il deadlock, è un problema che nasce dalla gestione della mutua esclusione Esempio di starvation A richiede accesso prima alla stampante B pure il SO dà la stampante ad A A rilascia la stampante e lo scheduler gli permette di richiederla nuovamente il SO dà nuovamente la stampante ad A e cosı̀ via per sempre B non “mangia” mai, quindi muore di fame (starvation) con 2 soli processi è assai improbabile, ma con tanti processi diventa probabile che uno soffra di starvation Requisiti per la Mutua Esclusione Qualsiasi meccanismo si usi per offrire la mutua esclusione, deve soddisfare i seguenti requisiti: Solo un processo alla volta può essere nella sezione critica per una risorsa Niente deadlock né starvation Nessuna assunzione su scheduling dei processi, né sul numero dei processi Un processo deve entrare subito nella sezione critica, se nessun altro processo usa la risorsa Un processo che si trova nella sua sezione non-critica non deve subire interferenze da altri processi in particolare non può essere bloccato Un processo che si trova nella sezione critica ne deve prima o poi uscire più in generale, ci vuole cooperazione ad es., non bisogna scrivere un processo che entra nella sua sezione critica senza chiamare entercritical Mutua Esclusione for Dummies i n t bolt = 0; void P ( i n t i ) { while ( true ) { bolt = 1; while ( bolt == 1) ; ; bolt = 0; ; } } parbegin ( P (0) , P (1) ,... , P ( n ) ) Basta che lo scheduler faccia eseguire i 2 processi in interleaving perfetto, ed è deadlock Oppure basta anche che ci sia un processo solo Mutua Esclusione for Dummies i n t bolt = 0; void P ( i n t i ) { while ( true ) { while ( bolt == 1) ; bolt = 1; ; bolt = 0; ; } } Basta che lo scheduler faccia eseguire i 2 processi in interleaving perfetto, e si viola la mutua esclusione Scheduler e Livello Macchina Altra corsa critica meno evidente: lo scheduler interrompe a livello di istruzione macchina diciamo assembler per visualizzarlo meglio Supponiamo che P(0) venga eseguito fino a bolt = 1 compreso Si potrebbe pensare che almeno cosı̀ la mutua esclusione sia sia sicuramente ok Invece no! Infatti, P(1) potrebbe essere arrivato in precedenza fino a “metà” del while (bolt == 1); ovvero, fino a caricare il valore della variabile bolt (che, a quel punto, era ancora 0) dentro un registro Quando il controllo ritorna a P(1), per lui bolt vale 0... Roadmap Concetti basilari di concorrenza Mutua esclusione: supporto hardware Semafori Passaggio di messaggi Problema dei lettori/scrittori Equivalenze Disabilitazione delle Interruzioni while ( true ) { ; di s a b i l i t a _ i n t e r r u p t () ; ; ri ab i l it a _ in t e rr u p t () ; ; } Disabilitazione delle Interruzioni Disabilitazione delle Interruzioni I sistemi con un solo processore permettono solo l’interleaving Un processo viene eseguito finché non invoca il sistema operativo o viene interrotto Disabilitare le interruzioni garantisce la mutua esclusione ovvero, se il processo può decidere di non essere interrotto, allora nessun altro lo può interrompere mentre si trova nella sezione critica Non funziona su sistemi con più processori Se i processi abusano della disabilitazione, peggiorano le prestazioni del SO cala la multiprogrammazione e quindi l’uso del processore Istruzioni Macchina Speciali Istruzione compare and swap (confronta e scambia) Istruzione exchange Entrambe atomiche l’hardware garantisce che un solo processo per volta possa eseguire una chiamata a tali istruzioni/funzioni anche se ci sono più processori compare and swap: Pseudocodice i n t compare_and_swap ( i n t word , i n t testval , i n t newval ) { i n t oldval ; oldval = word ; i f ( word == testval ) word = newval ; return oldval ; } Linguaggio C “finto”: l’istruzione word = newval; non funzionerebbe in questo modo (passaggio per valore) Mutua Esclusione con compare and swap exchange: Pseudocodice void exchange ( i n t register, i n t memory ) { i n t temp ; temp = memory ; memory = register; register = temp ; } Mutua Esclusione con exchange Sbagliato Mutua Esclusione con exchange È SBAGLIATO!!! Mutua Esclusione con Istruzioni Speciali In entrambi i casi precedenti l’idea è che il processo che trova bolt a 0 può entrare E per impedire ad altri di entrare mette bolt a 1 se un processo si mette in mezzo nel frattempo, la mutua esclusione può essere violata per questo sono istruzioni atomiche Una volta finito, rimette bolt a 0, cosı̀ gli altri processi possono entrare o anche lui stesso, se è solo oppure se lo scheduler lo favorisce Nel caso della exchange, l’errore sta nel fatto che, se un processo fa 2 iterazioni consecutive e rientra nella sezione critica, bolt non viene messo a 1 quindi altri processi possono entrare, dando luogo ad una race condition Istruzioni Macchina Speciali: Vantaggi Applicabili a qualsiasi numero di processi, sia su un sistema ad un solo processore che ad un sistema a più processori con memoria condivisa Semplici e quindi facili da verificare Possono essere usate per gestire sezioni critiche multiple Istruzioni Macchina Speciali: Svantaggi Basate sul busy-waiting: spreco di tempo di computazione un ciclo di busy wait non è distinguibile da codice “normale” quindi la CPU lo deve eseguire fino al timeout (preemption obbligatoria!) oppure, ci deve essere più di una CPU Possibile la starvation (come mostrato sopra) Possibile anche il deadlock, se a questi meccanismi viene abbinata la priorità (fissa) se un processo A a bassa priorità viene interrotto mentre è già nella sezione critica...... e un processo B a priorità alta entra nel busy waiting... B non può essere interrotto per eseguire A a causa della priorità, e A non può andare avanti perché solo B, finendo la sua sezione critica, lo può far uscire dal busy-waiting Roadmap Concetti basilari di concorrenza Mutua esclusione: supporto hardware Semafori Passaggio di messaggi Problema dei lettori/scrittori Equivalenze Semafori Un valore intero usato dai processi per scambiarsi segnali Solo tre operazioni definite, tutte e 3 atomiche: initialize decrement o semWait può mettere il processo in blocked: niente CPU sprecata come con il busy waiting increment o semSignal può mettere un processo blocked in ready Si tratta di syscall, quindi sono eseguite in kernel mode e possono agire direttamente sui processi Semafori: Pseudocodice Semafori Binari: Pseudocodice Semafori: Pseudocodice “Vero” Semafori: Pseudocodice “Vero” Errore nel codice di sinistra: manca un else prima di s.flag = 0 Semafori: Pseudocodice “Vero” Consideriamo tre processi A, B e C 1 A ha giá completato la semWait e sta eseguendo codice in sezione critica. s.count è 0 2 B entra in semWait, count va a −1 e B diventa blocked. s.flag = 0 3 tocca ad A, che esegue sezione critica e semSignal. s.count = 0 il sistema dunque sposta B che era in wait sul semaforo da blocked a ready A completa semSignal. s.flag = 0 4 C entra in semWait, passa il while compare and swap e viene interrotto immediatamente dallo scheduler. s.flag = 1 5 B riprende l’esecuzione, imposta s.flag = 0 esegue la sua sezione critica e chiama semSignal. Passa il while. s.flag = 1 imposta s.count = 1, termina semSignal ed imposta s.flag = 0 Semafori: Pseudocodice “Vero” Stato corrente: C fermo prima di s.count − −; s.count == 1; s.flag == 0 6 Arriva un nuovo processo D, che entra in semWait. Passa il while, ora s.flag = 1 7 D esegue s.count − −: legge s.count da memoria e lo porta in eax. eax == 1 scheduler interrompe D ed esegue C 8 C continua da dov’era: esegue s.count − −, che diventa ora 0, quindi non va in block 9 C preempted nella sezione critica 10 tocca a D, che continua il calcolo di prima: salva eax − 1 in s.count, che rimane (!) 0 11 D non va in block, e continua nella sezione critica Race condition Semafori Deboli e Forti Il SO usa una coda per memorizzare i processi in attesa su un semaforo Quale politica viene usata per prendere il prossimo processo in attesa nella coda? Se è l’“ovvia” FIFO, allora si parla di strong semaphore (semaforo forte) Se la politica non viene specificata, allora si parla di weak semaphore (semaforo debole) Con i semafori forti, ovviamente usati bene, si può evitare la starvation; con i deboli no Semafori Forti: Esempio Semafori Forti: Esempio Mutua Esclusione con i Semafori Processi e Semafori Problema del Produttore/Consumatore Situazione generale: uno o più (processi) produttori creano dati e li mettono in un buffer un consumatore prende dati dal buffer uno alla volta al buffer può accedere un solo processo, sia esso produttore o consumatore Il problema: assicurare che il produttore o i produttori non inseriscano dati quando il buffer è pieno assicurare che il consumatore non prenda dati quando il buffer è vuoto oltre alla mutua esclusione sull’intero buffer in realtà, sarebbe possibile permettere a consumatori e produttori di agire anche in contemporanea per semplicità, non considereremo questo caso Produttore/Consumatore: Pseudocodici Per ora, facciamo finta che il buffer sia infinito: il produttore non ha mai motivo di fermarsi while ( true ) { while ( true ) { while ( in 2 processi Roadmap Concetti basilari di concorrenza Mutua esclusione: supporto hardware Semafori Mutua esclusione: soluzioni software Passaggio di messaggi Problema dei lettori/scrittori Equivalenze Interazione tra Processi Quando un processo interagisce con un altro, due requisiti fondamentali devono essere soddisfatti: sincronizzazione (mutua esclusione) comunicazione Lo scambio di messaggi (message passing) è una soluzione al secondo requisito funziona sia con memoria condivisa che distribuita può essere usata anche per la sincronizzazione Funzionalità fornita tramite due primitive send(destination, message) receive(source, message) spesso c’è anche il test di ricezione notare che message è un input per la send ed un output per la receive Sincronizzazione La comunicazione richiede anche la sincronizzazione il mittente deve inviare prima che il ricevente riceva Cosa succede dopo che un processo ha effettuato un invio od una ricezione? queste operazioni possono essere bloccanti oppure no il test di ricezione non è mai bloccante Send e Receive Bloccanti Sia mittente che destinatario sono bloccati finché il messaggio non è completamente ricevuto Tipicamente viene chiamato rendezvous Sincronizzazione molto stretta Send Non Bloccante Più naturale per molti programmi concorrenti La indicheremo come nbsend Con ricezione bloccante (caso molto comune): il mittente continua (nel senso: non viene messo in blocked) il destinatario rimane bloccato finché non ha ricevuto il messaggio Con ricezione non bloccante: se il messaggio c’è viene ricevuto, altrimenti si va avanti La indicheremo come nbreceive può settare un bit dentro il messaggio per dire se la ricezione è avvenuta oppure no se la ricezione è non bloccante, allora tipicamente non lo è neanche l’invio Sempre atomiche un solo processo per volta le esegue finché l’operazione non è stata completata, oppure il processo non viene bloccato Indirizzamento Il mittente deve poter dire a quale processo (o quali processi) vuole mandare il messaggio Lo stesso per il destinatario, anche se non sempre Si possono usare: indirizzamento diretto indirizzamento indiretto Indirizzamento Diretto La primitiva di send include uno specifico identificatore per il destinatario o per un gruppo di destinatari Per la receive, ci può essere oppure no receive(sender, msg): ricevi solo se il mittente coincide con sender utile per applicazioni fortemente cooperative receive(null, msg): ricevi da chiunque dentro msg, come vedremo, c’è anche il mittente es.: il processo che gestisce le stampe può accettare messaggi da tutti Ogni processo ha una sua coda; una volta piena, solitamente il messaggio si perde o viene ritrasmesso es.: syscall listen di Linux Indirizzamento Indiretto I messaggi sono inviati ad una casella di posta (mailbox) condivisa va esplicitamente creata da un qualche processo Il mittente manda messaggi alla mailbox, da dove il destinatario se li va a prendere Se la ricezione è bloccante, e ci sono più processi in attesa su una ricezione, un solo processo viene svegliato Evidenti analogie con il produttore/consumatore in particolare, se la mailbox è piena allora anche nbsend si deve bloccare se serve solo per le versioni bloccanti e per comunicazioni x-to-one, la mailbox può avere dimensione 1 Comunicazione Indiretta La prima riga, in realtà, è la comunicazione diretta Tipico Formato dei Messaggi Mutua Esclusione con i Messaggi const message null = ; mailbox box ; void P ( i n t i ) { message msg ; while ( true ) { receive ( box , msg ) ; ; nbsend ( box , msg ) ; ; } } void main () { box = create_mailbox () ; nbsend ( box , null ) ; parbegin ( P (1) , P (2) ,... , P ( n ) ) ; } Problema del Produttore/Consumatore Situazione generale: uno o più (processi) produttori creano dati e li mettono in un buffer un consumatore prende dati dal buffer uno alla volta al buffer può accedere un solo processo, sia esso produttore o consumatore Il problema: assicurare che il produttore o i produttori non inseriscano dati quando il buffer è pieno assicurare che il consumatore non prenda dati quando il buffer è vuoto oltre alla mutua esclusione sull’intero buffer Produttore/Consumatore con i Messaggi const i n t capacity = ; mailbox mayproduce , mayconsume ; const message null = ; void main () { mayproduce = create_mailbox () , mayconsume = create_mailbox () ; f o r ( i n t i = 1; i 0) { i f (! empty ( finished ) ) { receive ( finished , msg ) ; count ++; } e l s e i f (! empty ( writerequest ) ) { receive ( writerequest , msg ) ; writer_id = msg. sender ; count = count - MAX_READERS ; } e l s e i f (! empty ( readrequest ) ) { receive ( readrequest , msg ) ; count - -; nbsend ( msg. sender , " OK " ) ; } } Soluzione Con i Messaggi i f ( count == 0) { nbsend ( writer_id , " OK " ) ; receive ( finished , msg ) ; count = MAX_READERS ; } while ( count < 0) { receive ( finished , msg ) ; count ++; } } } Soluzione Con i Messaggi Ovviamente, occorre un processo di inizializzazione crea le 3 mailbox lancia 1 controller più reader e writer a piacimento Se ci sono più di MAX READERS-1 richieste contemporanee da lettori, la soluzione non funziona Se count > 0, cosa è sempre vero? Se count == 0, cosa è sempre vero? Se count < 0, cosa è sempre vero? Roadmap Concetti basilari di concorrenza Mutua esclusione: supporto hardware Semafori Mutua esclusione: soluzioni software Passaggio di messaggi Problema dei lettori/scrittori Equivalenze Equivalenze La condivisione di risorse può quindi essere implementata con 3 metodi diversi istruzioni hardware sincronizzazione (semafori) message passing Se si può implementare un’applicazione con uno qualsiasi dei 3 metodi, allora lo si può fare anche con gli altri 2 un particolare meccanismo potrà rivelarsi più conveniente degli altri, in termini di facilità di sviluppo, di prestazioni, e di gestione

Sistemi Operativi Modulo I PDF

Document Details

Tags

Related

Summary

Full Transcript