Calcolatori Elettronici - Sistemi Operativi

Cuncurrency

Molti thread e processi devono essere sincronizzati adeguatamente, dato che utilizzano risorse condivise.

Perciò è molto importante che l'accesso alle aree dati di questi processi avvenga in modo mutuamente

esclusivo. Il SO operativo deve garantire e implementare questi meccanismi.

Gestione di processi multipli o thread multipli:

multiprogramming, più processi con singola CPU

multiprocessing, più processi su più CPU

distributed processing, ovvero quando si hanno più hardware dislocati.

Termini che ricorrono nella trattazione della concorrenza:

atomic operation: operazioni indivisibili che non possono fallire a metà.

critical section: accesso a risorse condivise, che deve essere mutuamente esclusivo nel caso di più processi

che devono accedere alla stessa risorsa o area di memoria.

deadlock: attesa di un processo ad altri processi in modo indefinito

livelock: processi che cambiano stato continuamente a seconda dello stato di altri processi, senza che

compiano nulla di utile.

mutual exclusion: relazione con la critical section; il requisito che un processo in una sezione critica sia

l'unico ad accedervi

race condition: più thread o processi leggono e scrivono stessi dati, il cui risultato finale dipende

strettamente dall'ordine degli accessi.

starvation: processo che non viene mai eseguito dal SO nonostante sia ready

Interleaving e overlapping: processi che vengono eseguiti in tempi diversi dallo stesso processore, o processi

in parallelo su processori diversi.

La velocità d'esecuzione non è prevedibile a priori, perché dipende dall'attività degli altri processi, dagli

interrupt e dallo scheduling, tutti fattori variabili.

Difficoltà della concorrenza:

condivisione delle risorse globali

difficoltà nell'allocazione di risorse

difficoltà nel debugging, dato che certi malfunzionamenti possono avvenire o no in base alla sequenza dei

processi, che ogni volta è differente.

3 tipologie di interazione tra processi:

processi non consapevoli dell'interazione: competizione per le risorse.

processi parzialmente consapevoli: qui i due processi cooperano utilizzando una stessa risorsa o dato

processi consapevoli: comunicazione tra di loro, con primitive di comunicazione esplicite.

Nel garantire la mutua esclusione è fondamentale il SO perché è lui che alloca le risorse e deve fornire ai

processi un metodo per esprimere il requisito di mutua esclusione nell'utilizzo di una risorsa, bloccando i

processi che vogliono accedervi concorrentemente. Non ci può essere interleaving tra critical section.

Cuncurrency 1

Requisiti per la mutua esculsione:

processi che si fermano non devono interferire con altri

no deadlock o starvation

un processo deve poter accedere a una cirtical section quando è possibile utilizzarla

il processo deve rimanere in una critical section un tempo finito

non si devono assumere velocità di esecuzione definite nei meccanismi di mutua esclusione.

Meccanismi di mutua esclusione

Interrupting disabling (solo con mono core): garantisce la mutua esclusione, poiché evita che un processo

possa venire bloccato e che un altro processo utilizzi la critical section. Se disabilito gli interrupt essi

vengono ignorati e così altri processi non vengono fatti partire e non si hanno rischi di contaminazione della

critical section (si intendono time interrupt).

Svantaggi: l'efficienza cala a picco, e l'approccio non può essere applicato su architetture multicore perché più

processi sono in esecuzione e anche disattivando gli interrupt vengono eseguiti comunque in parallelo.

Meccanismi hw

può aiutare con istruzioni specifiche dell'ISA.

Compare&Swap:

Comparazione tra valore in memoria e un valore di test. Se uguali avviene lo swap tra newval e il valore

dell'indirizzo puntato dal puntatore. La funzione torna il valore della della cella puntata (oldval). L'intera

operazione viene effettuata atomicamente senza interruzioni.

int compare_and_swap (int *word, int testval, int newval){

int oldval;

oldval = *word;

if (oldval==testval) *word = newval;

return oldval;

}

Programma slide 15 serie di processi uguali che hanno un loop infinito al loro interno, con l'ingresso in una

sezione critica; noi vogliamo che gli altri processi non entrino nella stessa area critica, quindi usiamo la

compare&swap.

Nel main bolt = 0; tutti i processi vengono avviati concorrentemente. Nella compare&swap viene tornato il

valore di bolt, 1 o 0. Se torna 0 il processo entra nella sezione critica perché il while è falso, se torna uno la

verifica viene fatta ad oltranza finché il processo che è riuscito ad entrare esce dalla sezione critica e rimette

bolt a 0.

*alla slide 15 ci vuole &bolt alla compare_and_swap*

La funzione compara l'elemento del puntatore al primo argomento e il secondo argomento. Se la condizione si

verifica viene scambiato l'elemento puntato e i terzo argomento.

Exchange

Si scambia il valore di un registro con quello di una cella di memoria

void exchange (int *register, int *memory){

int temp;

Cuncurrency 2

temp = *memory;

*memory = *register;

*register = temp;

}

Lo stesso programma della 15 con la exchange cambia logica: c'è un do while per l'ingresso nella sezione

critica. Bolt si scambia con il valore di keyi, ovvero diventa 1; se keyi diventa 0 allora entro nella critical section,

se no il loop continua a scambiare keyi=1 e bolt 1; quando il processo che è entrato esce, rimette bolt a 0, così

nello scambio keyi diventa 0 e un nuovo processo può entrare.

Vantaggi dell'utilizzo di istruzioni:

utilizzabile su qualsiasi numero di processi e processori.

semplice da verificare

può essere usato per multiple critcal sections ciascuna identificata dalla propria variabile

Svantaggi:

possibile starvation: in una coda di processi che attendono di entrare in una critical section, alcuni processi

possono rimanere in attesa indefinitamente a causa dell'arbitrarietà della scelta del processo da sbloccare.

possibile deadlock: in caso di processi con priorità più alta che vengono eseguiti a discapito di processi in

critical section ( esempio su slide).

può succedere che un processo sia in attesa ma che utilizzi comunque tempo di CPU

Meccanismi di concorrenza del SO

semafori: variabile intera a cui non si può accedere normalmente, ma si usano le primitive wait e signal, che

possono essere invocate da processi diversi.

semaforo binario: variabile booleana

mutex: varianti del samaforo binario, ma le primitive di accesso devono essere invocate entrambe dallo

stesso processo

Monitor: più rigorosi dei semafori

Mailboxes/messages: mezzi per la comunicazione tra processi per scambio di informazioni.

(altri non visti)

Semafori

3 operazioni:

inizializzazione a un intero non negativo

semWait: viene decrementato il valore, ma se diventa negativo il processo chiamante viene bloccato.

altrimenti il processo continua a essere in running.

semSignal: incrementa il valore del semaforo; se il valore è ancora negativo un processo bloccato da

semWait viene sbloccato.

Il valore assoluto del semaforo (se negativo) indica il numero di processi bloccati. Il valore non negativo del

semaforo indica il numero di processi che possono chiamare una semWait senza essere bloccati.

Conseguenze

Cuncurrency 3

Non c'è modo di sapere il numero di processi bloccati, si può solo accedere tramite le primitive e

l'inizializzazione del semaforo.

non c'è modo di sapere quale processo continui l'esecuzione sul processore (nel caso si un solo

processore) quando un processo dopo l'incremento del semaforo ne sblocca un altro.

non si può sapere se un altro processo sta attendendo quando si fa una semSignal, quindi un processo

potrebbe venire sbloccato, oppure no se il semaforo diventa positivo.

Struttura semaforo su dispense:

ha un contatore, che è l'intero sopra menzionato; c'è anche una coda di processi bloccati sul quel semaforo.

Le due primitive decrementano o incrementato il contatore e poi bloccano o sbloccano proccessi.

Nel caso del semaforo binario il contatore è un valore che può assumere one o zero (vero o falso).

Semafori forti: FIFO per lo sblocco dei processi

Semafori deboli: non c'è un ordine di rilascio

Esempio

Slide 28

L'implementazione avviene usando la samWait come enter sezione critica e la samSignal come exit sezione

ciritica.

Producer/consumer problem:

molti produttori di dati e un solo consumatore che prende i dati. Solo un produttore o consumatore alla volta

può accedere a un buffer. Non si possono aggiungere elementi a un buffer pieno. Sono condizioni ovvie per

evitare races, ma vanno implementate.

Il problema è assicurarsi che non si possa aggiungere dati a un buffer pieno e rimuoverli da un buffer vuoto.

Si risolve con un array dinamico infinito. Così non si deve fare il controllo per il buffer pieno, ma rimane da fare

quello del buffer vuoto per il consumatore. L'array ha due indici, in e out: indicano rispettivamente dove si

possono inserire elementi e dove si è rimasti a prelevare. Si deve controllare che in sia sempre maggiore di out.

Si può implementare questo con i semafori.

Programma slide 32

un problema è impedire che altri processi non lavorino sullo stesso buffer con le stesse variabili in e out; altro

problema è controllar che il buffer non sia vuoto (ovvero che in sia diverso da out);

Qui append() e take() aggiungono e prendono dati dall'array, incrementando rispettivamente in e out. Il

semaforo s regola gli accessi alla regione critica, delay regola il consumer nel caso si abbia il buffer vuoto.

int n //globale

binary_semaphore s=1, delay =0;

void producer() {

while(true){

produce();

semWaitB(s); //difatto permette l'accesso esclusivo alla regione critica

append(); //perché blocca tutti i processi che cercherebbero di entrare

n++; //numero elementi nel buffer

if (n==1) semSignalB(delay); //se n==1 prima era 0, quindi ora il buffer è non

semSignalB(s); //non vuoto e un processo che aveva provato ad accedere al buffer vuoto viene sbloccato

} //sblocco di un processo (prod. o cons.) che voleva accedere mentre la regione critica era occupata

}

void consumer(){

Cuncurrency 4

//int m;

semWaitB(delay); //verifica che delay possa accedere

while(true){

semWaitB(s); //entrata nella regione crtica

take();

n--;

//m=n;

semSignalB(s); //uscita

consume();

if(n==0) semWaitB(delay); //se abbiamo svuotato il buffer blocchiamo il consumer

}

}

void main () ...

In questa versione abbiamo un problema: consume() e if () fuori dalla regione critica (le regioni critiche devono

essere più piccole possibili per diminuire la concorrenza tra processi e quindi l'efficienza). Il controllo per n==0

avviene dopo una serie di istruzioni che non necessariamente sono svolte di fila, ma sono soggette a interrupt;

perciò il valore decrementato di n non è necessariamente lo stesso nel controllo n==0, perché nel frattempo il

producer potrebbe averlo incrementato. Un altro scenario possibile è che a causa dell'incremento di n nel

momento sbagliato l'if salti e non venga decrementato delay, che rimane a 1; quindi il consumer() può fare un

altro ciclo che porta n a 0 e delay a 0, che non blocca ancora il while del consumer, che rifa un ciclo e porta n a

1, prelevando difatto un elemento che non esiste.

Il problema si risolve usando una variabile locale m che copia n dentro alla regione critica, così da non avere

inconsistenze su n, poi l'if verrà fatto su m.

Lo stesso programma si può implementare utilizzando un semaforo sia per n (numero degli elementi) e s

(accesso nella regione critica). Se n diventa negativo il consumer si blocca.

Un Buffer finito ha un limite destro e si implementa con un array circolare, così in potrà essere prima di out. Si

deve sempre controllare che il buffer non sia vuoto e anche che non sia pieno, vedendo se In==Out. Si usa un

semaforo per individuare le caselle vuote (i puntini nella slide 36.

Nel problema producer/consumer l'implementazione dei semafori è come la precedente, ma con un semaforo e

che rappresenta le caselle vuote e si inizializza con la dimensione del buffer.

Implementazione dei semafori:

le primitive devono essere operazioni atomiche, ovvero non bloccabili da altri processi o time-out di

sistema.

possono essere implementati nell'hardware e nel firmware

si possono usare schemi software particolari

si possono usare le istruzioni hw per la mutua esclusione

Due implementazioni su dispense.

Monitor

E' un costrutto che fornisce una funzione simile ai semafori, ma più semplici da gestire e più strutturati, il che

rende anche più facile il debug. E' presente in molti linguaggi, tramite anche libreria. Fornisce dei dati ai quali si

può accedere tramite i metodi. I metodi tuttavia non garantiscono mutua esclusione in generale.

Le variabili locali sono accessibili solo dal monitor. Un processo alla volta può entrare in un monitor

invocandone i metodi.

Cuncurrency 5

Variabili condizione: dichiarate nel monitor e visibili e accessibili solo all'interno di esso. Servono per la

sincronizzazione.

cwait(c): argomento una condition variable; sospende l'esecuzione del processo chiamante sulla condizione c

se falsa.

csignal(c): riprende l'esecuzione di processi bloccati sulla stessa condizione.

Struttura di un monitor

Il monitor ha solo un'entrata e un'uscita, regolata dalla condizione che solo un processo alla volta può

accedervi. Il monitor crea delle code ognuna corrispondente a una condizione c, comune a più processi con la

stessa condizione. Se un processo che si sta eseguendo all'interno del monitor notifica una modifica della

condizione c, allora utilizza una csignal(c) con la quale notifica alla coda corrispondente alla condizione c, che

essa è cambiata, quindi un processo della coda può venire sbloccato.

Implementazione producer-consumer con i monitor (slide 44 si usano cwait e csignal per regolare take() e

append () nel caso di buffer vuoto o pieno. La riga (nextin+1 % N serve per garantire la circolarità del buffer.

csignal per l'append () che dice a un eventuale take() in attesa di riprendere l'esecuzione. Non servono i

semafori perché non ci sono race condition, grazie all'implementazione dei monitor, che permettono a solo un

processo di essere in esecuzione.

Message passing

Altro meccanismo di interazione tra processi che garantisce la mutua esclusione e anche la comunicazione tra

essi. Funziona anche con sistemi distribuiti, oltre a multiprocessori con memoria condivisa o uniprocessori.

I processi hanno due primitive:

send(destination, message)

receive( source, message)

Serve un meccanismo di indirizzamento per i processi: può essere l'indirizzo IP o meccanismi più sofisticati. I

messaggi sono di tipo char, oppure sono messi in un buffer.

La sincronizzazione è complessa:

la send può essere bloccante (qui il processo si blocca finché il messaggio non è ricevuto ) oppure no e il

processo va avanti.

la receive può essere bloccante, ovvero il processo che deve ricevere il messaggio si blocca in attesa del

messaggio; altrimenti può essere non bloccante, nel senso che anche se non si riceve il messaggio si va

avanti e magari si ricontrolla dopo; oppure si può fare un test per verificare che ci sia un messaggio in

attesa di essere prelevato.

l'addressing può essere diretto o indiretto, a seconda che l'indirizzo di mandante e ricevente siano espliciti

o implementati attraverso bufferizzazione o altri metodi

altro

Caso blocking send e blocking receive: entrambi non continuano finché uno non ha ricevuto il messaggio

dell'altro; qui la sincronizzazione è molto forte.

Caso nonblocking send, blocking receive: la send manda il messaggio ma non aspetta che arrivi, la receive

invece aspetta che il messaggio venga ricevuto; se la send viene eseguito più frequentemente della receive è

necessario un sistema di bufferizzazione dei messaggi inviati e non ancora ricevuti.

Caso nonblocking send e nonblocking receive: nessuno dei due aspetta e non vi è sincronizzazione.

Cuncurrency 6

Inderect process communication: mailbox che si occupa della bufferizzazione dei messaggi in arrivo e del loro

invio ai processi richiedenti; si può attuare in diversi modi, decidendo se avere più sorgenti di sand o receive, o

sorgenti singole.

Esempio slide 56 la main crea una mailbox e manda un messaggio vuoto. Nel processo P ho una receive

bloccante che regola la sincronizzazione e la mutua esclusione nell'ingresso a una regione critica; il primo

processo che arriva vede il messaggio nella mailbox e inizia, gli altri no. Il processo uscente dalla regione critica

manda un messaggio vuoto alla mailbox e un altro processo sarà in grado di prelevarlo ed entrare nella regione

critica. I messaggi sono vuoti perché servono solo per la sincronizzazione

Esempio slide 57 problema producer-consumer.

Problema Readers/Writers

Processi readers e writers, che accedono in lettura o scrittura a un'area dati in comune.

I reader possono accedere insieme alle aree di memoria perché non modificano, mentre un writer solo può

scrivere un'area di memoria o file. Quindi abbiamo da una parte la possibile esecuzione di più processi in

lettura, che non necessitano di meccanismi di mutua esclusione; dall'altra si ha un writer bloccante che deve

accedere da solo.

Esempio

Semaforo wsem per la mutua esclusione tra lettori multipli o altri scrittori e singolo scrittore. La var. readcount

che conta il numero di processi reader;

Il primo scrittore in esecuzione entra trova wsem a 1 e può scrivere, gli altri no.