Sistemi Operativi III · Appunti Universitari

01 Jul 2004

Riassunto gerarchico delle nozioni del corso 2003-2004 di Sistemi Operativi del Prof. Francesco Aymerich - Università degli Studi di Cagliari, Facoltà di Scienze Matematiche Fisiche Naturali, Dipartimento di Matematica ed Informatica, Corso di Laurea in Informatica

Il sistema operativo
- lo consideriamo come un insieme di attività
Attività
- fornisce una delle funzioni descritte nel capitolo 2, come, ad esempio, la schedulazione o la gestione dell'I/O.
- Ogni attività consiste nell'esecuzione di uno o più programmi e la si richiama ogni qualvolta si dovrà fornire la funzione corrispondente
Processo (task)
- sequenza di azioni, svolte tramite l'esecuzione di una sequenza di istruzioni (un programma) il cui risultato netto è quello di fornire una delle funzioni di sistema.
- Possiamo allargare il concetto fino ad abbracciare anche le funzioni di utenza oltre a quelle di sistema
  - anche l'esecuzione di un programma applicativo verrà definita processo.
- Un processo può comportare l'esecuzione di più programmi
- Un singolo programma o routine può essere coinvolto in più di un processo
Processore
- agente che consente la prosecuzione di un processo
- il processore può essere realizzato tramite il solo hardware oppure con una combinazione di hardware e software.
  - un'unità centrale d'elaborazione (CPU) è un processore atto all'esecuzione delle istruzioni in linguaggio macchina
  - una CPU assieme ad un interprete BASIC possono formare un processore per l'esecuzione di istruzioni in BASIC
- La trasformazione (trattata nel capitolo 1) di un elaboratore puro e semplice in una macchina virtuale in realtà può essere vista come la combinazione dell'hardware proprio dell'elaboratore con il sistema operativo, al fine di mettere a disposizione dell'utente un processore capace di eseguire i processi applicativi (ovvero, un processore capace di eseguire le istruzioni dategli dall'utente).
- Il programma o i programmi associati ad un processo non necessitano di essere implementati sotto forma di software:
  - L'intervento di un canale nello svolgimento di un trasferimento di dati, può essere considerato come un processo nel quale il programma relativo viene cablato ed inserito nell' hardware del canale stesso.
  - Visto in tal senso, il canale, ma a dire il vero anche una qualsiasi periferica, rappresenta un processore in grado di eseguire soltanto un unico processo.
Concorrenza
- può essere considerata come l'attivazione di svariati processi in contemporanea.
- se vi sono tanti processori quanti sono i processi, non ci sono difficoltà da un punto di vista logico.
- se, però, come accade spesso, vi sono meno processori che processi, si può ottenere una concorrenza virtuale dirottando i processori da un processo all'altro
- Se tale commutazione viene effettuata ad intervalli di tempo adeguatamente brevi, il sistema darà l'illusione della concorrenza, quando lo si prenda in considerazione sulla base di tempi macroscopici.
  - La concorrenza virtuale si raggiunge all'atto pratico tramite la tecnica dell'interfogliazione dei processi su un unico processore
- un processore in un sistema di calcolo deve registrare tutte le informazioni sul processo che sta eseguendo in un dato momento, prima di poter passare ad un qualche altro processo
  - ciò consente di riprendere il processo interrotto successivamente
Spazio di indirizzamento
- è associato ad ogni processo
- è una lista di locazioni di memoria comprese tra un minimo (solitamente 0) e un massimo, che il processo può usare per letture e scritture.
- Lo spazio di indirizzamento contiene il programma eseguibile, i dati del programma e il suo stack
Registri
- sono associati ad ogni processo
- comprendono il program counter, il puntatore allo stack, e altri registri hardware, nonché tutte le altre informazioni necessarie all'esecuzione del programma
Process-Table
- è presente in molti sistemi operativi
- è un array di strutture, una per ogni processo, che memorizza tutte le informazioni di ogni processo ad eccezione del relativo spazio di indirizzamento
Processo Sospeso
- consta del suo spazio di indirizzamento, solitamente chiamato core image (o immagine di nucleo, in onore delle memorie a nucleo magnetico usate un tempo), e della sua voce nella tabella dei processi, contenente, tra le altre cose, i suoi registri
- In molti sistemi operativi tutte le informazioni su ogni processo, a eccezione del contenuto del suo spazio di indirizzamento, vengono immagazzinate in una tabella di sistema chiamata la tabella dei processi (process-table), che è un array (o una lista) di strutture, una per ogni processo esistente.
Chiamate di sistema fondamentali
- creazione e terminazione di processi
- richiedere o rilasciare memoria
- attendere la terminazione di un processo
- sovrascrivere il programma corrente con uno diverso
Interprete dei comandi o shell
- legge comandi da un terminale
- crea un nuovo processo relativo al comando da eseguire
- quando il processo compie tutte le operazioni fa una chiamata di sistema per terminare
Processi figli o child
- se un processo crea altri processi prende il nome di processo padre e questi ultimi sono i processi figlio
- anche un processo figlio può creare altri processi, divenendo padre a sua volta
Albero dei processi correlati
- è dato dal processo padre e da tutti i processi sui figli (anche indiretti)
- l'insieme di tutti i processi dell'albero spesso devono cooperare per portare a termine il compito
- i processi hanno bisogno di comunicare tra loro per sincronizzare le loro attività, dando luogo ad una comunicazione interprocesso
Segnali
- sono l'analogo software degli interrupt hardware
- consentono di interrompere temporaneamente l'esecuzione di un processo e costringerlo a gestire il segnale prima che riprenda con le sue elaborazioni
- possono essere generati per svariati motivi
  - scadenza di un timer
  - un eccezione intercettata dall hardware convertita in segnale verso il processo responsabile
    - ad es. un istruzione illegale o un indirizzo di memoria non valido
elaborazione concorrente (o parallela)
- se si scatta un'istantanea del sistema nel suo complesso, si possono trovare svariati processi in diversi stati compresi tra il punto d'inizio e quello d'arrivo.
- Questa definizione chiaramente abbraccia sia la concorrenza vera e propria che quella virtuale
La non determinatezza
- Se consideriamo i processi come sequenze di azioni interrompibili tra un passo e l'altro, la non determinatezza si riflette nell'ordine imprevedibile secondo il quale procedono le sequenze.
- l'interruzione di un processo può essere considerata come la commutazione, causata da qualche imprevisto, di un processore che viene distolto da un processo
Comunicazione tra processi
- I processi all'interno di un sistema di calcolo non agiscono separatamente l'uno dall'altro.
  - da un lato devono collaborare per raggiungere l'obiettivo voluto, e cioè quello di eseguire i job introdotti dall'utente
  - dall'altro si trovano in competizione per l'uso di risorse limitate, quali processori, memoria o file.
- i campi dove la comunicazione è essenziale possono essere classificati come segue:
  - Mutua esclusione
    - Le risorse di un sistema possono essere classificate come
      - condivisi
        
        possono essere usate da svariati processi in situazioni di concorrenza
        
        CPU
        
        file a sola lettura
        
        zone di memoria contenenti procedure pure o dati protetti
      - non condivisi
        
        il loro utilizzo è limitato ad un processo per volta.
        
        periferiche
        
        file modificabili
        
        aree dati soggette a modifica
    - La non condivisibilità di una risorsa deriva da uno dei due seguenti motivi
      - 1) La natura fisica della risorsa non rende praticabile la via della condivisione.
        
        Esempio tipico ne è un lettore di nastro perforato, nel quale è impossibile commutare i nastri tra caratteri consecutivi.
      - 2) Il tipo di risorsa è tale che, se fosse utilizzata da più processi in modo concorrente, le azioni di uno di questi potrebbero interferire con quelle di un altro.
        
        Un esempio molto comune consiste in una locazione di memoria contenente una variabile cui può aver accesso più di un processo:
        
        se un processo esamina la variabile in questione proprio mentre un altro la modifica, il risultato è imprevedibile e solitamente disastroso.
    - La tecnica della mutua esclusione consiste nell'assicurare che possa accedere solamente un processo per volta alle risorse non condivisi.
    - i processi si svolgono in modo asincrono l'uno rispetto all'altro
      - In linea generale, la velocità di un processo relativamente ad un altro è imprevedibile, poiché dipende dalla frequenza con cui si verificano le interruzioni in ciascun processo e anche dalla frequenza e dal tempo di assegnazione del processore.
    - Per raggiungere una buona collaborazione tra essi, vi sono determinati punti in cui i processi devono sincronizzare le proprie attività. Si tratta, cioè, di quei punti oltre i quali un processo non riesce ad andare fino a che un altro non abbia portato a termine una certa attività.
      - può accadere che un processo di calcolo che produce un qualche output non può proseguire fino a che il suo output precedente non sia stato stampato.
    - Fa parte dei compiti del sistema operativo mettere a disposizione meccanismi tali da attivare la sincronizzazione.
  - Situazione di stallo (deadlock o deadly embrace)
    - si ha quando nessun processo riesce a continuare perché le risorse necessarie a ciascuno di essi sono tenute sotto controllo da un altro.
      - è analoga all'intasamento che si verifica allorchè due correnti opposte di traffico, tentando di svoltare tagliandosi la strada reciprocamente, si immobilizzano completamente, poiché ciascuna corrente occupa lo spazio stradale necessario all'altra.
    - la prevenzione delle situazioni di stallo, o per lo meno la limitazione dei relativi effetti, è una delle funzioni del sistema operativo.
I semafori
- concetto introdotto, assieme alle primitive wait() e signal(), da Dijkstra nel 1965
- Un semaforo, s, è un numero intero non negativo sul quale, a parte l'inizializzazione del suo valore, possono agire solo le operazioni di wait e signal.
  - signal(s) : incremento s
    - aumenta di un'unità il valore del semaforo s, dove l'aumento viene considerato un'operazione indivisibile.
    - L'indivisibilità comporta che signal(s) non è equivalente alla fase di assegnamento "s := s + 1".
      - supponiamo che due processi, A e B, vogliano eseguire l'operazione di "signal (s)" con un valore di s uguale a 3.
        
        Il valore di s, quindi, al completamento di entrambe le operazioni, sarà 5.
      - Supponiamo d'altro canto che, in circostanze analoghe, entrambi i processi vogliano eseguire "s := s +1".
        
        A potrebbe quindi valutare l'espressione s + 1 e riscontrare che è uguale a 4, ma prima che A possa assegnare ad s il risultato, anche B valuterebbe s + I con risultato identico.
        
        Ciascun processo, quindi, assegnerebbe il valore 4 ad s ed uno degli incrementi desiderati andrebbe perso.
  - wait(s) : when s>0 do decremento s
    - Il suo effetto consiste nel diminuire di un'unità il valore del semaforo s non appena si prefigura la possibilità di un risultato non negativo.
    - Anche qui si tratta di un'operazione indivisibile.
    - L'operazione di wait comporta un ritardo potenziale, dato che, quando agisce su un semaforo il cui valore è 0, il processo che esegue l'operazione può proseguire solo quando un altro processo abbia aumentato di 1 il valore del semaforo tramite un'operazione di signal.
    - L'indivisibilità dell'operazione sta a significare che, qualora vengano ritardati svariati processi, solo uno di essi può mandare a buon fine l'operazione allorchè il semaforo diventa positivo.
      - Non si premette, però, di quale processo si tratti.
  - il valore di un semaforo si trova in rapporto con il numero di operazioni di wait e signal eseguite su di esso, secondo la relazione (3.1)
    - val(sem) = C(sem) + ns(sem) - nw(sem)
  - dove
    - val(sem) è il valore del semaforo sem, C(sem) è il suo valore iniziale
    - ns(sem) è il numero di operazioni di signal eseguite su di esso
    - nw(sem) è il numero di operazioni di wait andata a buon fine su di esso.
  - Ma per definizione
    - val(sem)>=0
  - quindi, segue la relazione (3.2)
    - nw(sem) <= ns(sem) + C(sem)<ul>
    - l'eguaglianza risulta vera se e solo se val(sem) = 0.
    - è invariante rispetto alle operazioni di wait e di signal, è, cioè, vera qualsiasi sia il numero delle operazioni eseguite.
Mutua esclusione con i semafori
- sezioni critiche
  - segmenti di programma che fanno accesso a risorse non condivisi
- si considera la mutua esclusione nell'esecuzione delle sezioni critiche
- Si può ottenere la mutua esclusione attraverso il semplicemente racchiudendo ogni sezione critica tra le operazioni wait e signal su uno stesso semaforo il cui valore iniziale, C(sem), sia 1
  - la relazione (3.2) può essere riscritta come
    - nw(sem) <= ns(sem) + 1</li>
  - in questo modo non si impedisce mai, senza che ve ne sia il bisogno, l'ingresso di un processo nella sua sezione critica;
    - ciò avviene solamente se qualche altro processo si trova già entro la propria sezione critica.
    - Possiamo verificarlo osservando che ad un processo viene negato l'ingresso solo se il valore di sem è uguale a 0.
    - In tal caso la relazione 3.2 indica che
      - nw(sem) = ns(sem) + 1
Sincronizzazione attraverso i semafori
- La forma più semplice di sincronizzazione può essere rappresentata da un processo A che non deve andare oltre un dato punto L1 fino a che un altro processo B non abbia raggiunto il punto L2.
  - Si verificano esempi di questa situazione ogni qual volta A richiede, al livello L1 informazioni che vengono fornite da B solo dopo aver raggiunto L2:
  - Processo A
    - ...
    - L1: wait(sem)
    - ...
    - ...
  - Processo B
    - ...
    - ...
    - L2: signal(sem)
    - ...
  - dove il valore iniziale del semaforo, sem, è imposto a 0
  - A non può proseguire oltre L1 fino a che B non abbia eseguito l'operazione di signal a livello L2.
  - se B esegue quest'ultima operazione prima che A abbia raggiunto L1, non si verifica alcun ritardo per A.
  - Possiamo nuovamente far ricorso alla relazione 3.2 per introdurre una dimostrazione più formale:
    - nw(sem) <= ns(sem)</li>
  - è un esempio asimmetrico, in quanto l'avanzamento di A è regolato da B ma non il viceversa
- problema classico del produttore e del consumatore
  - Un insieme di processi "produttore" ed uno di processi "consumatore" comunicano per mezzo di un dispositivo di transito (buffer) nel quale i produttori depositano articoli che poi vengono prelevati dai consumatori.
  - I produttori ripetono continuamente il ciclo
    - produzione di un articolo
    - deposito dell'articolo nel buffer
  - i consumatori ripetono continuamente il ciclo:
    - prelievo di un articolo dal buffer
    - consumo dell'articolo
  - è il caso di un processo di calcolo, produttore, che mette in un buffer delle linee di output, mentre il corrispondente consumatore è il processo che provvede alla stampa di ciascuna linea.
  - Il buffer possiede una capacità limitata, pur essendo abbastanza grande da contenere N articoli di dimensioni identiche.
  - La sincronizzazione richiesta è duplice:
    - i produttori non possono mettere articoli nel buffer se questo è già pieno
    - i consumatori non possono prelevare articoli se il buffer è vuoto.
    - In altri termini, se il numero di articoli depositati è D ed il numero di quelli prelevati è D, deve accadere la relazione (3.3):
      - 0 <= D - E <= N</li>
  - il buffer deve essere protetto dall'accesso simultaneo di diversi processi, per il timore che le azioni di uno (ad esempio nella modifica dei puntatori) possano disturbare quelle dell'altro.
    - Sia il deposito che il prelievo di articoli, quindi, devono essere codificati sotto forma di sezioni critiche.
  - Programma per i produttori
    - repeat indefinitamente
    - begin
      - make(article); // produce l'articolo
      - wait(space_left_in_buffer);
      - wait(buffer_modify);
      - put(article); // deposita articolo nel buffer
      - signal(buffer_modify);
      - signal(articles_in_buffer)
    - end
  - Programma per i consumatori
    - repeat indefinitamente
    - begin
      - wait(articles_in_buffer);
      - wait(buffer_modify);
      - get(article); // preleva articolo dal buffer
      - signal(buffer_modify);
      - signal(space_left_in_buffer);
      - use(article); // usa l'articolo
    - end
  - Definizione dei semafori
    - space_left : inizializzato a N, definisce il numero di articoli che possono essere inseriti nel buffer
      - consente la sincronizzazione
    - articles_in_buffer : inizializzato a 0, indica il numero di articoli presenti nel buffer
      - consente la sincronizzazione
    - buffer_modify : inizializzato a 1, indica se è consentito o meno effettuare modifiche al buffer
      - consente la mutua esclusione
  - La soluzione proposta soddisfa la relazione (3.3)
    - Applicando la relazione di invarianza 3.2 ai due semafori di sincronizzazione, otteniamo:
      - nw(space_left) <= ns(space_left) + N (3.4)</li>
      - nw(articles_in_buffer) <= ns(articles_in_buffer) (3.5)</li>
    - dall'ordine delle operazioni relative al programma per i produttori, osserviamo che
      - ns(articles_in_buffer) <= D <= nw(space_left) (3.6)</li>
    - dall'ordine delle operazioni relative al programma per i consumatori, che
      - ns(space_left) <= E <= nw(articles_in_buffer) (3.7)</li>
    - Quindi dalla relazione 3.6
      - D <= nw(space_left)</li>
      - D <= ns(space_left)+N; per la 3.4</li>
      - D <= e + N; per la 3.7</li>
    - Analogamente, dalla relazione 3.7
      - E <= nw(articles_in_buffer)</li>
      - E <= ns(articles_in_buffer); per la 3.5</li>
      - E <= D; per la 3.6</li>
    - Combinando questi due risultati, si ottiene la dimostrazione
      - E <= D <= E + N</li>
  - La soluzione del problema dei produttori e dei consumatori può essere usata come traccia per tutte quelle situazioni in cui un processo passa informazioni ad un altro.
    - Più in particolare, i processi che governano le periferiche di input fungono da produttori per quei processi che consumano I'input, così come i processi che governano le periferiche di output fungono da consumatori per quei processi che producono output.
  - Se disposti in ordine scorretto i wait e signal possono generare delle situazioni di stallo pur verificando la 3.3
    - ribaltando l'ordine delle operazioni di wait eseguite dai programmi per i consumatori e produttori:
      - Se il buffer è vuoto, per un consumatore è possibile guadagnare l'accesso al buffer eseguendo "wait(buffer_modify)", per venire poi posto in stato di sospensione sul "wait(articles_in_buffer)".
      - L'unico modo in cui si può sbloccare il consumatore consiste nel far depositare un articolo nel buffer dal produttore, facendogli eseguire "signal(articles_in_buffer)".
      - Tuttavia, nessun produttore può avere accesso al buffer dato che questo viene occupato dal consumatore in stato di blocco.
      - Ne consegue una situazione di stallo analoga a quella risultante dall'antagonismo nella richiesta di utilizzo delle risorse
I monitor
- risolvono alcuni dei problemi legati all'uso scorretto dei semafori
  - è facile per un programmatore mettere nel posto sbagliato operazioni di wait e signal oppure, addirittura, non metterne affatto
- sono uno degli accorgimenti più largamente adottati per gestire l'accesso a risorse non condivisi (Hoare, 1974)
- Un monitor consiste di:
  - 1) i dati comprendenti un oggetto in condivisione;
  - 2) un insieme di procedure che possono essere richiamate per accedere all'oggetto;
  - 3) un (segmento di) programma che inizializzi l'oggetto
    - questo programma viene eseguito una sola volta, quando l'oggetto viene creato
- Il compilatore deve
  - assicurare che l'accesso ad un oggetto condiviso sia possibile solamente richiamando una procedura del monitor corrispondente;
    - si può raggiungere piuttosto agevolmente questo obiettivo tramite il meccanismo di "scope" della maggior parte dei linguaggi con struttura a blocchi.
  - garantire che le procedure di ciascun monitor siano implementate sotto forma di sezioni critiche che si escludono reciprocamente
    - può riuscirvi facilmente generando operazioni di wait e signal sugli idonei semafori esistenti nel programma compilato.
- i monitor eliminano una fonte potenzialmente ricca di situazioni d'errore, trasferendo dal programmatore al compilatore la responsabilità della mutua esclusione.
- il programmatore si assume la responsabilità per altre forme di sincronizzazione, servendosi dei semafori (o di altri metodi equivalenti) per realizzarle
- L'accorgimento del monitor è stato implementato in svariati linguaggi di programmazione, quali il Concurrent Pascal (Hansen, 1975), il Pascal-plus (Welsh e Bustard, 1979) e il Mesa (Lampson e RedelI, 1980).
  - il C non implementa questo meccanismo
- La struttura generica di un monitor (Hoare, 1974) espressa in una sintassi derivata dal Pascal, è la seguente:
  - var m:monitor;
  - begin
    - dichiarazione delle variabili locali che rappresentano l'oggetto;
    - dichiarazione delle procedure che accedono alle variabili locali;
    - inizializzazione delle variabili locali
  - end
- Alle variabili locali non si può avere accesso fuori dall'ambito del monitor; in seguito all'inizializzazione, su di esse possono agire solo le stesse procedure del monitor. Per impedirne la manipolazione contemporanea da parte di più processi, le procedure del monitor sono implementate sotto forma di sezioni critiche dotate di mutua esclusione. Quest'ultima è assicurata dal compilatore, il quale genera le opportune operazioni di sincronizzazione (quali le operazioni di wait e signal sui semafori) nel programma compilato
- un monitor può essere considerato come un oggetto di dati astratto condivisibile tranquillamente tra svariati processi
- Le operazioni di sincronizzazione proposte da Hoare, ed adottate nella maggior parte dei monitor implementati, non consistono in operazioni di wait e signal sui semafori, ma in operazioni simili sugli oggetti denominate condizioni
- condizione
  - Analogamente ad un semaforo ha due operazioni che possono essere applicate ad essa:
    - cwait (condizione): sospendi l'esecuzione del processo chiamante
    - csignal (condizione): riprendi l'esecuzione di qualche processo sospeso in seguito ad un cwait sulla stessa condizione. Se ve ne sono svariati, selezionane uno; se non ve ne sono, non intervenire.
  - L'operazione di cwait annulla l'esclusione del monitor, altrimenti nessun altro processo sarebbe in grado di entrare nel monitor per eseguire un csignal. Analogamente, csignal annulla l'esclusione, affidandola al processo ripreso. A quest'ultimo, pertanto, deve essere concesso di venire eseguito prima che sia possibile entrare nel monitor per qualsiasi altro processo.
- Differenze tra semafori e condizioni
  - a) Una condizione, contrariamente ad un semaforo, non possiede alcun valore. Si può pensare ad essa come ad una coda cui viene aggiunto un processo in seguito all'esecuzione di un cwait e dalla quale viene rimosso quando qualche altro processo effettua un csignal.
  - b) Un'operazione di cwait fa sempre sì che il processo in esecuzione venga ritardato, a differenza di quanto avviene con l'operazione di wait, che provoca un ritardo solo se il valore del semaforo è zero.
  - c) Un'operazione di csignal produce effetti solo se un processo è sospeso sulla stessa condizione. Un'operazione di signal, invece, produce sempre un effetto: l'incremento del valore del semaforo. Le operazioni di signal vengono "ricordate" (nel valore del semaforo), mentre ciò non succede per le operazioni di csignal.
- I monitor hanno una proprietà importante che li rende utili per ottenere la mutua esclusione: un solo processo alla volta può essere attivo al loro interno.
- I monitor sono un costrutto di un linguaggio di programmazione; come tali, il compilatore è a conoscenza delle loro peculiarità e può gestire le chiamate alle procedure di monitor in modo differente dalle altre.
  - In genere, quando un processo chiama una procedura di monitor, le prime istruzioni controllano se un altro processo sta in quel momento utilizzando il monitor.
  - Se è così, il processo viene sospeso finché l'altro processo non abbandona il monitor.
  - Se nessun altro processo sta usando il monitor, il processo chiamante può entrare.
- Il compilatore ha il compito di implementare la mutua esclusione negli accessi al monitor, solitamente usando un semaforo binario.
  - Dato che è il compilatore, e non il programmatore, a gestire la mutua esclusione, è molto meno probabile che qualcosa vada storto.
- La persona che programma il monitor non si deve preoccupare di come il compilatore otterrà la mutua esclusione, gli basta sapere che scrivendo tutte le sezioni critiche come procedure di monitor, non accadrà mai che due processi eseguano le loro sezioni critiche nello stesso istante.
Il buffer usato tra i processi dei produttori e quelli dei consumatori mediante i monitor
- potrebbe essere rappresentato da un monitor comprendente:
  - 1) lo spazio ed i puntatori del buffer (per esempio, un array e gli indici relativi);
  - 2) due procedure, deposito e prelievo, che possono essere richiamate dai processi per mettere e togliere, rispettivamente, un articolo dal buffer;
  - 3) un (segmento di) programma che inizializzi i puntatori del buffer sulla sua locazione iniziale.
- il compilatore deve assicurare che l'accesso al buffer sia limitato alle procedure di deposito e prelievo e che queste ultime si escludano reciprocamente.
- A questo punto nessun meccanismo impedisce che i processi continuino a depositare articoli nel buffer quando è pieno, né che tentino di prelevarli quando è vuoto.
  - per risolvere questo problema devono essere introdotte adeguate operazioni di sincronizzazione all'interno delle procedure di deposito e di prelievo.
- Esempio del buffer realizzato con i monitor
  - monitor example
    - integer i;
    - condition c;
    - procedure producer(x);
    - end;
    - procedure consumer(x);
    - end;
  - end monitor;
  - var buffer: monitor;
  - begin
    - var B: array[0... .N-1]of item (spazio per N articoli)
    - nextin, nextout: 0. . . N - 1; puntatori del buffer)
    - nonfull, nonempty, condition; (per la sincronizzazione)
    - count: 0 ... N; (numero di articoli nel buffer)
    - procedure deposit (x: item);
    - begin
      - if count = N then cwait (nonfull); (evita overflow)
      - B [nextin] : = x
      - nextin: = (nextin + 1) mod N;
      - count: = count + 1; (un dato in più nel buffer)
      - csignal (nonempty) (riprendi qualsiasi processo consumatore in attesa)
    - end;
    - procedure extract (var x: item);
    - begin
      - if count = O then cwait (nonempty); (evita overflow)
      - x: = B[nextout];
      - nextout: = (nextout + 1) mod N;
      - count: = count - 1; (un articolo in meno nel buffer)
      - csignal (nonfull) (riprendi qualsiasi processo produttore in attesa)
    - end;
    - nextin: = 0; nextout: = 0; (buffer inizialmente vuoto)
    - count: = 0
  - end
Soluzione alternativa al problema produttore-consumatore
- facciamo uso di due variabili di condizione, insieme a due operazioni, WAIT e SIGNAL, che operano su di esse.
  - Quando una procedura di monitor scopre di non poter continuare (ad esempio quando il produttore trova il buffer pieno), effettua una WAIT sulla variabile di condizione full.
  - Questa chiamata provoca la sospensione del processo chiamante e consente l'ingresso nel monitor a un altro processo a cui era stato in precedenza proibito l'accesso.
  - Quest'altro processo, per esempio il consumatore, può svegliare il suo partner effettuando una SIGNAL sulla variabile di condizione su cui è in attesa.
  - Per evitare due processi attivi all'interno del monitor nello stesso istante, abbiamo bisogno di una regola che stabilisca cosa accade dopo una SIGNAL.
    - Hoare propose di lasciare in esecuzione il processo appena risvegliato, sospendendo l'altro.
    - Brinch Hansen propose di risolvere il problema richiedendo che il processo che esegue la SIGNAL abbandoni immediatamente il monitor.
      - In altre parole, un costrutto SIGNAL può apparire solo come l'ultimo costrutto di una procedura di monitor.
    - In questo testo useremo la proposta di Brinch Hansen, poiché è concettualmente più semplice e anche più facile da realizzare.
- Se si invoca una SIGNAL su una variabile di condizione su cui diversi processi sono in attesa, solo uno di essi, scelto dallo scheduler di sistema, viene risvegliato.
- Le variabili di condizione non sono contatori e non accumulano segnali per un uso successivo come fanno i semafori.
  - Pertanto, se si invia un segnale a una variabile di condizione su cui nessuno è in attesa, il segnale viene perduto.
  - La WAIT deve cioè essere effettuata prima della SIGNAL.
  - Questa regola rende l'implementazione assai più semplice.
- In pratica, questa limitazione non crea problemi, dato che, se necessario, è facile usare delle variabili per tener conto dello stato di ogni processo.
- Un processo che potrebbe altrimenti invocare una SIGNAL è in grado, controllando queste variabili, di accorgersi che l'operazione non è necessaria.
- La mutua esclusione automatica sulle procedure di monitor garantisce che se, ad esempio, il produttore scopre che il buffer è pieno all'interno di una procedura di monitor, esso sarà in grado di completare l'operazione WAIT senza doversi preoccupare della possibilità che lo scheduler esegua il consumatore immediatamente prima del completamento della WAIT.
  - Il consumatore non potrà entrare nel monitor fino a che la WAIT non sarà terminata e il produttore segnalato come non più eseguibile.
- implementazione in pseudo-Pascal
  - monitor ProducerConsumer condition full, empty;
  - integer count;
  - procedure enter;
    - begin
      - if count = N then wait(full);
      - enter_item;
      - count:=count+ 1;
      - if count = 1 then signal(empty)
    - end;
  - procedure remove;
    - begin
      - if count = 0 then wait(empty);
      - remove.item;
      - count := count - 1;
      - if count = N - 1 then signal(full)
    - end;
  - count := 0;
  - end monitor;
  - procedure producer;
    - begin
      - while true do
        
        begin
        
        produce_item;
        
        ProducerConsumer.enter
        
        end
    - end;
  - procedure consumer;
    - begin
      - while true do
        
        begin
        
        ProducerConsumer.remove;
        
        consume.item
        
        end
    - end;
Problemi dei semafori e monitor
- Con i monitor si ha bisogno di un linguaggio che ne preveda l'uso, ma sono rari.
- Un altro problema dei monitor, e anche dei semafori, è che queste astrazioni erano state progettate per risolvere il problema della mutua esclusione su una o più CPU che accedono a una memoria comune.
  - Quando si passa a un sistema distribuito con più CPU, ognuna con la sua memoria privata e connesse da una rete locale, queste primitive diventano inapplicabili.
I messaggi
- risolvono i problemi dei monitor e semafori
- Questo metodo di comunicazione interprocesso usa due primitive, SEND e RECEIVE che, come i semafori e diversamente dai monitor, sono chiamate di sistema piuttosto che costrutti del linguaggio
- Problemi progettuali
  - i messaggi possono essere persi
    - una soluzione può essere quella di mandare un messaggio di ack per ogni messaggio ricevuto
  - i messaggi possono essere duplicati
    - situazione che si verifica se vien perso l'ack e il messaggio viene rispedito
    - occorre aggiungere un numero di sequenza per poter riconoscere e scartare i messaggi già ricevuti
  - i processi che generano e ricevono i messaggi devono avere nomi univoci
  - prestazioni limitate
    - il problema si evidenzia se i processi che scambiano messaggi risiedono sulla stessa macchina
    - Cheriton (1984) ha suggerito di limitare la dimensione dei messaggi a ciò che trova posto nei registri di macchina, e di realizzare quindi lo scambio di messaggi utilizzando i registri
  - autenticazione
    - devo essere sicuro che chi spedisce o riceve i messaggi sia proprio chi dice di essere
- risoluzione del problema del produttore-consumatore con i messaggi
  - Soluzione:
    - # define N 100 /* numero di posizioni nel buffer */
    - void producer(void)
      - {
        
        int item;
        
        message m; /* buffer dei messaggi */
        
        while (TRUE) {
        
        produce_item(&item);
        
        receive(consumer, &m); /* attendi un vuoto */
        
        build_message(&m); /* costruisci il messaggio da inviare */
        
        send(consumer, &m); /* invia il messaggio al consumatore */
        
        }
      - }
    - void consumer(void)
      - {
        
        int item, i;
        
        message m;
        
        for (i = 0; i < N; i++)<ul>
        
        send (producer, &m); / * invia N vuoti */
      - while (TRUE) {
        
        receive(producer, &m); /* estrai il messaggio pieno */
        
        extract_item(&m, &item); /* estrai i dati dal messaggio */
        
        send (producer, &m); /* restituisce un messaggio vuoto */
        
        consume _item(item); /* consuma i dati */
      - }
    - }
- Assumiamo che tutti i messaggi abbiano la stessa dimensione e che i messaggi inviati, ma non ancora ricevuti, siano automaticamente inseriti dal sistema operativo in un buffer.
- In questa soluzione usiamo un totale di N messaggi, in qualche modo analoghi alle N posizioni del buffer in memoria condivisa.
- Il consumatore inizia inviando N messaggi vuoti al produttore.
- Quando il produttore ha un oggetto da inviare al consumatore, prende un messaggio vuoto e ne rimanda indietro uno pieno.
  - In questo modo, il numero totale dei messaggi nel sistema rimane costante nel tempo e i messaggi possono essere salvati in uno spazio di memoria le cui dimensioni sono note in anticipo.
- Se produttore e consumatore lavorano a velocità differenti:
  - Se il produttore lavora più velocemente del consumatore, tutti i messaggi finiranno con l'essere pieni e in attesa del consumatore; il produttore sarà bloccato, attendendo che un messaggio vuoto torni indietro.
  - Se il consumatore lavora più velocemente, accade il contrario: tutti i messaggi resteranno vuoti, in attesa che il produttore li riempia; il consumatore sarà bloccato, in attesa di un messaggio pieno.
- Lo scambio dei messaggi può avvenire in modi differenti:
- si assegna ai processi un indirizzo univoco e i messaggi sono indirizzati ai processi
- si usano mailbox
  - la mailbox è una struttura dati adatta a immagazzinare messaggi
  - all'atto della creazione viene definita la capienza
  - Quando si usano le mailbox i parametri di indirizzamento nelle chiamate SEND e RECEIVE sono mailbox, non processi
  - Quando un processo tenta di inviare a una mailbox piena viene sospeso fino a che un messaggio non viene rimosso dalla mailbox
  - le mailbox sono meccanismi che implementano sostanzialmente dei buffer
  - a mailbox di destinazione trattiene i messaggi che sono stati inviati al processo destinatario, ma non sono stati ancora accettati.
- rendezvous
  - se si chiama la SEND prima della RECEIVE, il processo mittente rimane bloccato fino all'esecuzione della RECEIVE, quando il messaggio può essere copiato direttamente e senza alcun buffer intermedio dal mittente al destinatario.
  - se si esegue prima la RECEIVE, il destinatario resta bloccato fino all'invocazione della SEND.
- Pipe
  - è il meccanismo usato da UNIX per scambiare messaggi
  - sono di fatto delle mailbox.
  - La sola vera differenza tra un sistema a messaggi con mailbox e il meccanismo delle pipe è che queste ultime non preservano i confini tra i messaggi.
    - se un processo scrive su una pipe 10 messaggi di 100 byte e un altro processo legge dalla pipe 1000 byte, il lettore otterrà in un sol colpo tutti e 10 i messaggi.
    - In un vero sistema a messaggi ogni READ dovrebbe restituire un solo messaggio.
  - Ovviamente non ci sono problemi se i processi si accordano per scrivere e leggere sempre dalla pipe messaggi di dimensione fissa, o per terminare ciascun messaggio con un carattere speciale (ad esempio un line-feed).
  - è più facile da implementare di uno schema a messaggi con buffer, ma è meno flessibile in quanto mittente e destinatario devono per forza essere eseguiti in modo sincronizzato.
Problemi classici dell IPC - InterProcess Comunication
- Problema dei filosofi affamati (1965 Dijkstra)
- viene usato da chiunque inventa una primitiva di sincronizzazione per dimostrarne l'efficacia
- è utile per modellare il caso di processi che competono per l'accesso esclusivo a un numero limitato di risorse, come i dispositivi di I/O
- formulazione del problema
  - Cinque filosofi sono seduti intorno a un tavolo circolare. Ognuno di loro ha un piatto di spaghetti, tanto scivolosi che ogni filosofo ha bisogno di due forchette per mangiarli. Tra ogni coppia di piatti c'è una forchetta.
  - La vita di un filosofo consiste di periodi in cui pensa, alternati a periodi in cui mangia.
  - Quando un filosofo ha fame cerca di ottenere la forchetta alla sua sinistra e quella alla sua destra, una alla volta e in qualsiasi ordine.
  - Se riesce a ottenere le due forchette, mangia per un po', quindi posa le forchette e riprende a pensare.
  - La domanda chiave è: si può scrivere un programma per ciascun filosofo che faccia ciò che si suppone debba fare e non si blocchi mai?
- soluzione 1 : ovvia e sbagliata
  - #define N 5 /* numero di filosofi */
  - void filosofo(int i){ /* i: indice del filosofo, da O a 4 */
    - while (TRUE) {
      - pensa(); /* il filosofo sta pensando */
      - prendi_la_forchetta(i); /* prendi la forchetta sinistra */
      - prendi_la_forchetta((i+1) % N); /* prendi la forchetta destra; % è l'operatore modulo */
      - mangia (); /* yum-yum, spaghetti */
      - posa_la_forchetta(i); /* rimetti la forchetta sinistra sul tavolo */
      - posa_la_forchetta((i+1) % N); /* rimetti la forchetta destra sul tavolo */
    - }
  - }
  - Supponiamo che tutti e cinque i filosofi prendano simultaneamente la loro forchetta sinistra.
    - Nessuno sarà in grado di prendere la forchetta destra e avremo un deadlock.
- soluzione 2 : ancora sbagliata
  - Potremmo modificare la soluzione 1 in modo che il filosofo, dopo aver preso la forchetta sinistra, controlli che la forchetta destra sia disponibile.
    - Se non lo è, il filosofo posa la forchetta sinistra, aspetta un po', e quindi ripete l'intera procedura.
  - Con un po' di sfortuna, tutti i filosofi potrebbero iniziare l'algoritmo simultaneamente, prendendo la loro forchetta sinistra, per poi rendersi conto che la forchetta destra non è disponibile, mettendo quindi a posto la forchetta sinistra e aspettando per prendere nuovamente la forchetta sinistra in modo simultaneo, e così via, per sempre.
  - Una situazione come questa, nella quale tutti i programmi procedono senza termine e senza ottenere alcun progresso, viene chiamata starvation
  - Se quando non riescono a ottenere la forchetta destra i filosofi attendessero semplicemente un tempo casuale, anzichè lo stesso tempo, la probabilità che tutti continuino a procedere raggruppati per un tempo di circa un'ora è molto piccola, ma vorremmo una soluzione che funzioni sempre e non possa fallire a causa di una sequenza improbabile di numeri casuali (si pensi ai controlli di sicurezza di una centrale nucleare)
- soluzione 3 : con l'uso dei semafori
  - #define N 5 // numero dei filosofi
  - #define SINISTRA (i-1)%N // indice del vicino di sinistra di
  - #define DESTRA (i+1)%N // indice del vicino di destra di
  - #define PENSANDO 0 // il filosofo sta pensando
  - #define AFFAMATO 1 // il filosofo sta cercando di prendere le forchette
  - #define MANGIANDO 2 // il filosofo sta mangiando
  - typedef int semaphore; // i semafori sono degli interi particolari
  - int state[N]; // l'array che memorizza gli stati di tutti
  - semaphore mutex = 1; // mutua esclusione per le sezioni cntiche
  - semaphore s[N]; // un semaforo per ogni filosofo
  - void filosofi (int i){ // i: indice del filosofo, da O a N-1
    - while (TRUE) { // ripeti all'infinito
      - pensa ( ); // il filosofo sta pensando
      - prendi_la_forchettas(i); // prendi le due forchette o bloccati
      - mangia( ); // yum-yum, spaghetti
      - posa_la_forchettas(i); // rimetti entrambe le forchette sul tavolo
    - }
  - }
  - void prendi_la_forchetta(int i){ // i: indice del filosofo, da O a N-1
    - wait(&mutex); // entra in sezione critica
    - state[i] = AFFAMATO; // registra che il filosofo i è affamato
    - test(i); // cerca di ottenere le 2 forchette
    - SIGNAL(&mutex); // esce dalla sezione critica
    - wait(&s[i]); // si blocca se non ha ottenuto le forchette
  - }
  - void posa_la_forchetta(i){ // i: indice del filosofo, da O a N-1
    - wait(&mutex); // entra in sezione critica
    - state(i) = PENSANDO; // il filosofo ha finito di mangiare
    - test(SINISTRA); // controlla se il vicino di sinistra può mangiare
    - test(DESTRA); // controlla se il vicino di destra può mangiare
    - SIGNAL(&mutex); // esce dalla sezione critica
  - }
  - void test(i){ // i: indice del filosofo, da O a N-1
    - if (state[i] == AFFAMATO && state[SINISTRA] != MANGIANDO && state[DESTRA] != MANGIANDO)
      - state[i] = MANGIANDO;
    - SIGNAL(&s[i]);
  - }
- Problema dei lettori e degli scrittori (Courtois et al., 1971)
- modella l'accesso a una base di dati
- È accettabile che più processi leggano nello stesso istante la base di dati, ma se un processo sta aggiornando (scrivendo) la base di dati, nessun altro processo può accedere alla base di dati, neanche i lettori
  - Il problema è: come si programmano i lettori e gli scrittori?
- soluzione
  - typedef int semaphore;
  - semaphore mutex = 1; // controlla l'accesso a 'rc'
  - semaphore db = 1; // controlla l'accesso al data base
  - int rc = 0 // n di processi in lettura o che vogliono leggere
  - void lettore(void){
    - while (TRUE){ // ripeti all'infinito
      - wait(&mutex); // ottieni l'accesso esclusivo a 'rc'
      - rc = rc + 1; // c'è un lettore in più
      - if (rc == 1) wait(&db); // se è il primo lettore ...
      - SIGNAL(&mutex); // rilascia l'accesso esclusivo a 'rc
      - leggi_data_base ( ); // accedi ai dati
      - wait(&mutex); // ottieni l'accesso esclusivo a 'rc'
      - rc = rc - 1; // c'è un lettore in meno
      - if (rc == 0) // se è l'ultimo lettore ...
        
        SIGNAL(&db);
      - SIGNAL(&mutex); // rilascia l'accesso esclusivo a 'rc'
      - usa_dat_letti ( ); // sezione non critica
    - }
  - }
  - void scrittore(void){
    - while (TRUE){ // ripeti all'infinito
      - rifletti_sui_dati ( ); // sezione non critica
      - wait(&db); // ottieni l'accesso esclusivo
      - scrivi_data_base ( ); // aggiorna i dati
      - SIGNAL(&db); // rilascia l'accesso esclusivo
    - }
  - }
- In questa soluzione, il primo lettore che accede alla base di dati esegue una WAIT sul semaforo db. I lettori seguenti si limitano a incrementare un contatore, rc. I lettori, uscendo, decrementano il contatore e l'ultimo ad uscire esegue una SIGNAL sul semaforo, consentendo l'ingresso di un eventuale scrittore bloccato.
- Supponiamo che, mentre un lettore sta usando la base di dati, un altro lettore arrivi. Poiché non c'è nessun problema se due o più lettori usano la risorsa nel medesimo istante, al secondo lettore viene consentito l'accesso.
- Supponiamo ora che arrivi uno scrittore. Lo scrittore non può accedere alla base di dati, poiché gli scrittori devono ottenere un accesso esclusivo, di conseguenza lo scrittore viene sospeso.
- In seguito arrivano altri lettori. Finché almeno un lettore è attivo, i lettori che seguono vengono fatti accedere alla risorsa.
  - Come conseguenza di questa strategia, tutti i lettori vengono immediatamente ammessi fintanto che si ha un flusso costante di lettori.
  - Lo scrittore resterà sospeso fino a che non rimane nessun lettore.
- Per prevenire la situazione in cui gli scrittori non riescono mai ad accedere alla base di dati, il programma potrebbe essere modificato in modo che quando un lettore arriva e uno scrittore è in attesa, il lettore viene sospeso in coda allo scrittore invece di essere immediatamente ammesso.
  - In questo modo, lo scrittore deve aspettare che terminino i lettori che erano attivi al momento del suo arrivo, ma non i lettori arrivati in seguito.
  - Lo svantaggio di questa soluzione è che consente una minore concorrenza e quindi prestazioni inferiori.
- Problema del barbiere addormentato
- formulazione del problema
  - Nel salone ci sono un barbiere, una sedia da barbiere e n sedie per far sedere i clienti in attesa, se ve ne sono. Se non ci sono clienti, il barbiere si siede nella sedia e si addormenta
  - Quando un cliente arriva sveglia il barbiere addormentato.
  - Se altri clienti arrivano mentre il barbiere sta tagliando i capelli a un cliente, si siedono (se ci sono sedie vuote) o altrimenti abbandonano il negozio (se le sedie sono occupate).
  - Il problema consiste nel programmare il barbiere e i clienti in modo da evitare corse critiche.
- soluzione
  - #define CHAIRS 5 // n di sedie per i clienti in attesa
  - typedef int semaphore;
  - semaphore clienti = 0; // n di clienti in attesa
  - semaphore barbieri = 0; // n di barbieri in attesa di clienti
  - semaphore mutex = 1; // per la mutua esclusione
  - int waiting = 0; // ci sono clienti in attesa, mi occorre perche' non posso leggere il valore di un semaforo
  - void barbiere(void){
    - while (TRUE) {
      - wait(clienti); // si sospende se il n di clienti è 0
      - wait(mutex); // accede a 'waiting'
      - waiting = waiting - 1; // decrementa il numero di clienti in attesa
      - SIGNAL(barbieri); // un barbiere è pronto a tagliare
      - SIGNAL(mutex); 1 // rilascia 'waiting'
      - taglia_capelli( ); // taglia i capelli (fuori dalla sezione critica)
    - }
  - }
  - void cliente(void){
    - wait(mutex); // entra in sezione critica
    - if (waiting < CHAIRS){ // se non ci sono sedie libere esci<ul>
    - waiting = waiting + 1; // incrementa il numero di clienti in attesa
    - SIGNAL(clienti); // sveglia il barbiere se necessario
    - SIGNAL(mutex); // rilascia l'accesso a 'waiting'
    - wait(barbieri); // si sospende se non ci sono barbieri liberi
    - viene_servito ( ); // si siede e viene servito
  - } else
    - SIGNAL(mutex); // il salone è pieno, esci
- }
- Spiegazione della soluzione
- Quando il barbiere arriva al lavoro, esegue la procedura barbiere, che lo sospende sul semaforo clienti fino a che non arriva qualcuno. Il barbiere quindi si addormenta
- Quando un cliente arriva esegue cliente, che inizia cercando di acquisire mutex per entrare in sezione critica.
  - Un altro cliente che entri di li a poco non potrà far nulla fino a che il primo non abbia rilasciato mutex.
  - Il cliente controlla quindi che il numero dei clienti in attesa sia inferiore al numero di sedie.
    - Se non è così, rilascia mutex ed esce senza taglio
    - Se c'è una sedia disponibile, il cliente incrementa la variabile intera waiting ed esegue quindi una SIGNAL sul semaforo clienti, risvegliando il barbiere.
- A questo punto, il cliente e il barbiere sono entrambi svegli.
- Quando il cliente rilascia mutex, il barbiere acquisisce il semaforo, sbriga le sue faccende, e inizia quindi il taglio.
- Quando il taglio è terminato il cliente abbandona la procedura ed esce dal negozio.
- In questo problema, il cliente non esegue alcun ciclo, poiché ogni cliente riceve un solo taglio.
- Il barbiere invece esegue un ciclo, cercando ogni volta di servire il cliente successivo. Se ne trova uno, somministra un altro taglio, altrimenti si addormenta.
- vale la pena notare come i problemi dei lettori-scrittori e del barbiere addormentato, benché non comprendano alcun trasferimento di dati, appartengono all'area dell'IPC, in quanto comportano una sincronizzazione tra più processi.