Costrutti linguistici per la mutua esclusione



Scaricare 280.5 Kb.
29.12.2017
Dimensione del file280.5 Kb.


COSTRUTTI LINGUISTICI PER LA MUTUA ESCLUSIONE

Enzo Mumolo
DEEI, Universita' di Trieste

I MONITOR
* Costrutto linguistico che incapsula la sincronizzazione di mutua esclusione all’interno della definizione della risorsa (Brinch Hansen, Hoare)
* Associa ad una struttura dati un insieme di procedure
* Il compilatore verifica che:

- nessun’altra operazione sia consentita

- un solo processo alla volta sia attivo entro il monitor
* Esempio di dichiarazione e di chiamata di monitor (Brinch Hansen):
type Esempio=monitor; ...

var ...; (* variabili locali *) var N1:Esempio;

Procedure entry Nome proc1(var ...); (* chiamata di una procedura del begin ... end; monitor *)

procedure entry Nome_proc2(var ...); N1.Nome_proc1(...);

begin ... end; ...

...


procedure Nome_proc(var ...);

begin ... end;


begin

(* inizializzazione variabili locali *)

end;

* Le variabili locali descrivono lo stato della struttura dati


* Nome_proc1 ... Nome_procN sono le uniche operazioni che possono accedere alla struttura dati
* Le strutture dati comuni alle procedure sono permanenti (tra successive esecuzioni delle procedure del monitor)
* Oltre alle procedure entry possono essere definite nel monitor altre procedure utilizzabili dalle procedure entry
* Fasi di controllo dell’uso di una risorsa non condivisibile tra processi concorrenti con monitor:

- controllo che un solo processo alla volta acceda alle strutture dati comuni: solo una procedura del monitor e’ attiva simultaneamente

- controllo della sincronizzazione tra i processi mediante l’uso di una condizione logica

* Variabili ‘condition’ (Hoare):

- controllo della sincronizzazione: il processo puo’ usare una risorsa se una condizione logica e’ vera, altrimenti e’ sospeso

- usa un nuovo tipo di variabili, var x, y: condition;

- operazioni su una variabile condition: wait e signal.
* processo in attesa sulla variabile x: x.wait. Risveglio di un processo sospeso su x: x.signal
* x.wait sospende il processo che la esegue finche’ un altro processo non esegue x.signal
* Regole di simcronizzazione: cosa succede dopo una ‘signal’ su una variabile condizione su cui sono sospesi diversi processi? Quale processo avanza?

- proposta di Hoare: il processo appena svegliato va in esecuzione

- proposta di Brinch Hansen: il processo che chiama la signal deve uscire subito dal monitor (si puo’ fare semplicemente usando signal come ultima istruzione del monitor). L’avanzamento e’ deciso dallo scheduler.
* esempio: produttore/ consumatore in Concurrent Pascal con i monitor

type buffer_circolare=monitor;

var buffer:array[0..N-1] of messaggio;

testa, coda: 0..N-1;

cont:0..N;

non_pieno, non_vuoto: condition;

procedure entry enter(x:messaggio);

begin


if cont=N then non_pieno.wait;

buffer[coda]:=x;

coda:=(coda+1) mod N;

cont:=cont+1;

non_vuoto.signal;

end;


procedure entry remove(var x:messaggio);

begin


if cont=0 then non_vuoto.wait;

c:=buffer[testa];

testa:=(testa+1) mod N;

cont:=cont-1;

non_pieno.signal;

end;


begin cont:=0; testa:=0; coda:=0; end;

end;


var dati: buffer_circolare;

procedure Produttore; procedure Consumatore;

var a:messaggio; var b:messaggio;

begin begin

while true do while true do

begin begin

produce(a); dati.enter(a); dati.remove(b); consuma(b);

end; end;

end; end;

* esempio: produttore/ consumatore in ADA con i monitor


monitor produttore_consumatore is

B:array(0..N-1) of Integer;

In_ptr; Out_ptr: integer:=0;

Count:integer:=0;

Not_full, Not_empty: condition;

Procedure Enter(I: in integer) is

Begin

If Count=N then wait(Not_full); endif;



B(In_ptr):=I;

In_ptr:=(In_ptr+1) mod N;

Signal(Not_empty);

end Enter


procedure Remove(I: out Integer) is

begin


if Count=0 then wait(Not_empty); endif;

I:=B(Out_ptr);

Out_ptr:=(Out_ptr+1) mod N;

Signal(Not_full);

end Remove;

end produttore_consumatore;


task body Produttore is task body Consumatore is

I:Integer; I:Integer;

begin begin

loop loop

Produce(I); Remove(I);

Enter(I); Consume(I);

end loop; end loop;

end Produttore; end Consumatore;


* Emulazione di semafori con i monitor in ADA
monitor Emulazione_Semafori is

S:Integer:=S0;

Not_zero: condition;
Procedure Sem_Down is

Begin


If S=0 then wait(Not_zero); end if;

S:=S-1;


end Sem_Down;
Procedure Sem_Up is

Begin


S:=S+1;

Signal(Not_zero);

end Sem_Up;

end Emulazione_Semafori


* Emulazione di monitor con i semafori: molto piu’ difficile.

E’ necessario: - un semaforo S per la mutua esclusione delle procedure del monitor

- un semaforo C_Semaphore per ogni variabile condizione
wait(C)  C_count:=C_count+1; signal(C)  if(C_count>0) then

Up(S); Up(C_Semaphore);

Down(C_Semaphore); end if;

Down(S); Up(S);

C_count:=C_count+1;

* Problemi con i monitor:

- hanno bisogno di un linguaggio che li metta a disposizione

- inoltre, i monitor sono stati progettati per sistemi con memoria comune; non funzionano in ambiente distribuito

 Modelli a scambio di messaggi

* Due processi comunicano attraverso un canale (astrazione logica)


* Sono necessari degli strumenti linguistici per specificare la sorgente e la destinazione dei messaggi
* Comunicazione simmetrica: i due processi si specificano a vicenda. Esempio: comunicazione tipo pipeline




* Comunicazione asimmetrica: solo il mittente specifica il destinatario. Esempio: comunicazione tipo cliente-servitore


* Schema Client-Server:

- Processo come gestore di una risorsa

- Il cliente invia una richiesta di servizio al server

- Il server soddisfa le varie richieste una alla volta


* Costrutti linguistici: Send, Receive
* Tipi di Send:
* Send asincrona: il processo continua l'esecuzione dopo la Send (Send non e' un punto di sincronizzazione)

- puo' essere richiesto uno scambio di messaggi di sincronizzazione

- e' necessaria la bufferizzazione dei messaggi

- se il buffer e' pieno:

- il mittente si sospende

- la Send solleva una eccezione al mittente


* Send sincrona: il processo si blocca in attesa che il messaggio sia stato ricevuto (Send e' un punto di sincronizzazione)

- non e' necessaria la bufferizzazione

- scrittura e verifica dei programmi facilitata
* Send tipo chiamata di procedura remota

- il cliente e' strutturato mediante una sequenza Send/Receive

- Send sincrona: la sincronizzazione con il ricevente continua finche' non viene inviata la risposta

- Send: punto di sincronizzazione


* Tipi di Receive:
* Receive di tipo bloccante: il ricevente si sospende finche' non viene inviato un messaggio
* Receive di tipo non bloccante: verifica lo stato del canale e restituisce un messaggio o una eccezione di canale vuoto

-svantaggio: bisogna fare uso di attesa attiva


* Esempi di primitive asincrone:

send(processo_ricevente, messaggio);

/* inserisce 'messaggio' nella coda di ingresso del processo ricevente ed esce */
receive(processo_mittente, messaggio);

/* analizza la coda di ingresso del processo che la esegue: se vuota si blocca, altrimenti estrae el primo messaggio */

* Esempio di utilizzo delle primitive: Produttore/Consumatore con N messaggi
Produttore

{

do{



Produce(&messaggio);

receive(Consumatore, &m); /* aspetta l'arrivo di un messaggio vuoto */

send(Consumatore, messaggio);

}while(true);

}

Consumatore



{

for(i=0; i

do{

receive(Produttore, &messaggio);



send(produttore, m); /* invia un messaggio vuoto */

consuma(messaggio);

}while(true);

}
* Esempio di algoritmo per il problema del produttore/consumatore con un buffer server con comunicazioni asincrone




dati


dati

Buffer


Server



dati

dati

pronto

Process Buffer_Server

{

do{


receive(mittente, messaggio);

if (il messaggio e' un segnale di pronto)

{

if (coda dati vuota)



aggiungi 'mittente' nella coda dei consumatori pronti;

else


preleva un messaggio dalla coda dei dati pronti per essere per essere inviati;

send(mittente,messaggio);

} else /* il messaggio e' un dato */

{

if(coda di consumatori vuota)



inserisci i dati nella coda dei dati pronti per essere inviati;

else


{

preleva un consumatore pronto dalla coda dei consumatori pronti;

send(consumatore, messaggio);

}

}while(true);


Process cosumatore_j

{

do {



send(Buffer_Server, 'pronto');

receive(mittente, &messaggio);

consuma(messaggio);

}while(true);

}
Process produttore_i

{

do{



produci(&dati);

send(Buffer_Server,dati);

}while(true);

}
* Variante dello scambio di messaggi:

- basato su una nuova struttura dati: Mailbox

- coda di messaggi usata da piu' mittenti e piu' destinatari

- una mailbox piena sospende i processi mittenti

- ogni destinatario e' caratterizzato da un numero di porta


* Variante dello scambio di messaggi:

- basato su una comunicazione pipeline

- essenzialmente una mailbox con un mittente e un destinatario
Cenni sui linguaggi per la programmazione concorrente
1) Concurrent Pascal (Brinch Hansen '77)

* Formato da tre tipi di moduli ( o tipi di sistema)

- Processo (struttura dati privata piu' programma sequenziale)

- Classe (tipi di dati astratti cui puo' accedere un solo processo)

- Monitor

* Ogni tipo di sistema e' allocato staticamente in fase di caricamento (non c'e' allocazione dinamica di memoria)

* I tipi di sistema sono globali, ma la visibilita' e' controllata dai 'diritti d'accesso'
2) Modula (Wirth '77)

* Applicazioni in tempo reale

* Meccanismo di base per l'incapsulamento e la protezione delle informazioni: 'Module' (unita' di programma al cui interno possono essere definiti costanti, tipi, variabili, procedure)

* Visibilita': tramite una 'define_list' (oggetti locali -> visibili all'esterno)

tramite una 'use_list' (oggetti esterni -> visibili all'interno)

* I processi non possono essere creati dinamicamente

* Interface module: corrisponde al monitor
3) Modula-2 (Wirth '82)

* Fornisce il meccanismo delle coroutines


4) Mesa (Xeroc '79)

* Programmazione di sistemi

* Moduli di programma e moduli di definizione (interfacce)

* Liste di import/export (visibilita' ed incapsulamento di informazioni)

* Consente di definire procedure come tipi di dati

* Aritmetica dei puntatori

* Gestione di eventi

* Gestione di coroutines ('port')

* Creazione dinamica di procesi ('fork')

* Monitor, con 'broadcast' per svegliare tutti i processi in attesa e risveglio automatico dopo un 'time-out'


5) Pascal-plus (Welsh '79)

* Proces


* Monitor

* Envelope (corrisponde alla classe del Concurrent Pascal o al module di Modula)

* Regole di visibilia': un identificatore puo' essere esportato se preceduto da '*'

* Esempio di envelope:

envelope Nome(..vars..);

... (* variabili locali e procedure *)

begin

I; (* inizializzazione *)



***; (* istruzione di separazione *)

S; (* rilascio della risorsa gestita da envelope *)

Cenni sui linguaggi per la programmazione distribuita
* Programmazione distribuita: Elaborazione congiunta e coordinata eseguita da piu' processi fisicamente distribuiti che si scambiano messaggi
* In un sistema fisicamente distribuito, i messaggi sono scambiati attraverso 'canali di comunicazione'. Il formato dei messaggi e' definito dai 'protocolli'
* Comunicazione nei sistemi ditribuiti

- comunicazione sincrona:

* se il ricevitore non e' pronto, il trasmettitore si blocca e viceversa.

* RENDEZ-VOUS: sincronizzazione tra due processi tramite comunicazione

- comunicazione asincrona:

* il trasmettitore invia messaggi quand'e' pronto


* Buffering: richiesto dalla comunicazione asincrona
* Direzione del flusso dei dati:

- sistemi asincroni: usano un flusso in una sola direzione

- sistemi sincroni: possono avere flusso dei dati in una o due direzioni
* Creazione di processi:

- statica: tutti i processi esistono quando inizia l'esecuzione

* vantaggi: predicibilita' della esecuzione; implementazione piu' efficiente

* svantaggi: incapacita' di adattarsi alle richieste computazionali

- dinamica: alcuni processi sono creati durante l'esecuzione

* vantaggi: flessibilita' sul numero dei processi

* uso dinamico delle risorse

* bilanciamento del carico computazionale tra i processi

Cenni di ADA
* Identificatori, case insensitive, commenti (--...)
* Esempio di programma in ADA
procedure Esempio is

g: integer:=0; -- variabili globali

procedure incr(p: in integer) is -- in, out, in out

l: integer; -- variabile locale

begin

l:=p+1;


g:=l+g;

end incr;


function Square(i: in integer) return integer is

begin


return i*i;

end Square;


begin

g:=g*5;


incr(7);

g=Square(g);

ens Esempio;
* tipi predefiniti: integer, float, character, boolean, string
* statement: if-then-elsif-else-endif, loop-endloop, while C loop-endloop, for in loop - endloop, exit ...
* tipi definiti dall'utente: enumerativi, array, record, puntatori, task
* tasking in ADA: primitive linguistiche per la programmazione concorrente

- comunicazione sincrona: i processi concorrenti si distinguono tra task accettori e task chiamanti.

- i task accettori hanno delle porte di ingresso (entry point) e dei punti di sincronizzazione ('accept')

- un task chiamante chiama un entry point dell'accettore

- modello asimmetrico: due task devono raggiungere insieme un punto di incontro per comunicare --> Rendez-Voous

- il punto di incontro si trova nel task accettore

- il task chiamante deve coniscere l'identita' dell'accettore, e il punto di rendez-vous (entry)

- il task accettore non e' tenuto a conoscere l'identita' del chiamante

* schema di Rendez-Vous
task Esempio_accettore is

entry Aggiungi(I:in integer);

entry Rimuovi(I: out integer);

end Esempio_accettore;

task body Esempio_accettore is

begin


---

---


accept Aggiungi(I: in Integer) do

---


end Aggiungi;

---


---

end Esempio_accettore;


task Chiamante

---


---

Esempio.Aggiungi(I:integer);

---

---
* sincronizzazione tra task comunicanti:



- Se il task chiamante chiama l'entry point prima che l'accettore raggiunga l'accept, si sospende e accetta

- Se viceversa l'accettore arriva all'istruzione accept, si sospende e aspetta che il chiamante chiami l'entry point


* un task accettore puo' avere molti 'accepts',
* molti task chiamanti possono chiamare l'entry: vengono messi in coda FIFO
* ‘Packages’ in ADA

- Package: un insieme di dati e dichiarazioni di procedure complete e messe in libreria

- Esempio: package text_IO:
with text_IO;

procedure Main_program is

begin

text_IO, Put_line(“Buon Giorno”);



end Main_program;
* Sommario di Ada

- istruzioni di controllo derivate dal Pascal

- struttura delle procedure derivata dal Pascal

- uso di package per funzioni di libreria

- supporto di programmazione concorrente con i task

- tipi definiti dall’utente

- gestione delle eccezioni

- Packages di semafori binari e contatori

- Monitor

- creazione dinamica di processi


Cenni di altri linguaggi di programmazione distribuita
1) OCCAM (Inmos ’88)

- modello di programmazione concorrente basato sul meccanismo Rendez-vous

- ogni istruzione e’ un processo: il programmatore indica esplicitamente i processi

sequenziali e quelli paralleli


2) LINDA (gelenter ‘85-’89)

- basato su sequenze tipicizzate di dati: Tuple Space (TS)

- TS e’ assimilabile ad una sequenza di procedure
3) PLITS (Programming Language in the Sky) (Feldmann ’79)

- primitive asincrone: messaggi memorizzati in code FIFO

- tipo message: record di ‘slot’ (nome, valore)

- costrutto di base: modulo. Un programma e’ un insieme di moduli


4) CSP (Communicating Sequential Processes) (Hoare ’78)

- specifica di processo : ::

- specifica di concorrenza nel corpo del processo:

[
//


//...//
];

- primitive di invio e ricezione di messaggi:



!

?

- processi e canali statici

- uso del nome dei processi per denotare un canale
5) DP (Distributed Processes) (Brinch Hansen ’78)

- primo esempio di linguaggio basato su chiamate a procedura remota

- applicazioni in tempo reale (piu’ processori privi di memoria comune)

- programma in tempo reale: insieme di processi distribuiti che iniziano contemporaneamente e continuano fino alla fine del sistema

- schema di processo:

Process None;



;

;


;

begin


---

end;


- interazioni tra processi mediante chiamate a procedure remote
4) CHILL (Ccitt HIgh Level Language) (Helf ’81)

- linguaggio di uso generale orientato ad applicazioni in tempo reale

- modello a memoria comune

- scambio di messaggi

- creazione (‘start P’), attivazione e terminazione (‘stop P’) dinamica di processi

- condivisione di codice tra processi

- interazioni tra processi anche tramite variabili globali
5) SR (Syncronizing Resources) (Andrews ’81)

- procedure remote

- costrutto ‘port’ per denotare i canali

- comunicazione asincrona

- variabili globali
6) Gypsy (Good ’79)

- applicazioni dedicate su architetture mono e multi CPU

- comunicazione tramite messaggi asincroni
7) Starmode (Cook ’80)

- ispirato a DP



- basato sul costrutto ‘module’







Condividi con i tuoi amici:


©astratto.info 2019
invia messaggio

    Pagina principale