Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
I corsi di Ingegneria
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Domenico Cotroneo » 10.Introduzione alla Programmazione Concorrente


Introduzione alla Sincronizzazione dei Processi

Sommario:

  • Concorrenza e Race condition
  • Tipi di interazione tra i processi
  • Modelli di interazione

Programmazione concorrente

Intesa come l’insieme delle tecniche, delle metodologie e degli strumenti necessari per fornire il supporto all’esecuzione di applicazioni software come un insieme di attività svolte simultaneamente.

Multiprogrammazione

… è la forma più elementare di programmazione concorrente in quanto fornisce il supporto per l’esecuzione intercalata di processi o threads diversi (interleaving).

Come è noto dalle prime lezioni, la multiprogrammazione consente di estendere le potenzialità di una macchina fisica monoprocessore in modo tale da generare una macchina astratta che dispone di più processori virtuali, uno per ogni processo (thread) che il sistema può supportare.


Elaborazioni concorrenti

Elaborazione (concorrente): attività svolta da una macchina, composta da più elaboratori, quando la stessa esegue un programma (concorrente).

Esempio: Supponiamo di dover scrivere le istruzioni che codificano l’algoritmo di valutazione della seguente espressione aritmetica:

(a-b) * (c+d)+(e*f)

Grafo di precedenza del processo


Grafo di precedenza a ordinamento parziale

Mette in evidenza esclusivamente le precedenze tra gli eventi dell’elaborazione che è necessario rispettare.

Ci sono degli eventi che non hanno alcuna relazione temporale (calcolo di r2 r3 e r1)…il risultato è indipendente dall’ordine in cui vengono calcolati (r2 r3 e r1 possono essere eseguiti in concorrenza).


Concorrenza e Parallelismo


Programmazione concorrente

Primitive per definire attività indipendenti (processi, threads).

Primitive per la comunicazione e sincronizzazione tra attività eseguite in modo concorrente (concorrenza non significa parallelismo).

Fork/Join

L’esecuzione di una fork coincide con la creazione e l’attivazione di un processo che inizia la propria esecuzione in parallelo con quella del processo chiamante.


Fork/Join

La join consente di determinare quando un processo, creato tramite la fork, ha terminato il suo compito, sincronizzandosi con tale evento.


Concorrenza

Processi concorrenti
Insieme di processi la cui esecuzione si sovrappone nel tempo.
Più in generale:

  • in un sistema monoprocessore due processi si dicono concorrenti se la prima operazione di uno comincia prima dell’ultima dell’altro.

… le problematiche

  • Comunicazione tra processi
  • Risorse condivise
  • Sincronizzazione tra processi
  • Assegnazione del tempo del processore.

Un semplice Esempio

void echo()
{

chin = getchar();
chout = chin;
putchar(chout);

}

chin e chout sono variabili condivise

Un semplice Esempio: P1 e P2 invocano la medesima funzione echo()


Race Condition

…si dice che per l’esempio precedente occorre una “Race Condition”, ovvero….

una condizione in cui più processi leggono o scrivono dati condivisi e il risultato finale di tali operazioni dipende dall’ordine (e dalla velocità) di esecuzione delle istruzioni dei processi.

Processi Concorrenti

Processi indipendenti

Due processi P1 e P2 sono indipendenti se l’esecuzione di P1 non è influenzata da P2, e viceversa (Proprietà della riproducibilità).

Processi interagenti
Due processi P1 e P2 sono interagenti se l’esecuzione di P1 è influenzata da P2, e viceversa.

  • Effetto dell’interazione dipende dalla velocità relativa dei processi.
  • Comportamento non riproducibile.

Tipi di interazione

Competizione: per l’uso di risorse comuni che non possono essere utilizzate contemporaneamente (mutua esclusione).

Cooperazione: nell’eseguire un’attività comune mediante scambio di informazioni (comunicazione).

Interferenza: dovuta a competizione tra processi per uso non autorizzato di risorse comuni, oppure ad un erronea soluzione di problemi di competizione e di cooperazione.Si manifesta spesso in modo non deterministico in quanto dovuta alla differente velocità di esecuzione dei processi.

Sincronizzazione

In tutti i casi esaminati, per un corretto funzionamento, è necessario imporre dei vincoli nella esecuzione delle operazioni dei processi.

Vincoli per la sincronizzazione

  • Competizione: un solo processo alla volta deve avere accesso alla risorsa comune (sincronizzazione indiretta o implicita).
  • Cooperazione: le operazioni eseguite dai processi concorrenti devono seguire una sequenza prefissata (sincronizzazione diretta o esplicita).

Modelli di Interazione

  • Modello ad ambiente globale
  • Modello ad ambiente locale

Le risorse

Dicesi risorsa un qualunque oggetto, fisico o logico, di cui un processo necessita per portare a termine la sua evoluzione.

Poiché un processo evolve eseguendo istruzioni (o procedure), una risorsa è sempre una entità astratta rappresentata da operandi di istruzioni (o procedure) e il suo uso consiste nell’esecuzione di una delle istruzioni (o procedure) applicabili a detti operandi.

Una risorsa, sia essa fisica o logica, è quindi un oggetto costituito da procedure e da una struttura dati allocati in memoria.

Alcune definizioni

Una risorsa può essere:

  • privata o locale: se è dedicata ad un solo processo che è il solo che può operare sulla risorsa;
  • comune o globale: se condivisa tra più processi;
  • ad uso esclusivo: se deve essere usata da un processo alla volta.

Il gestore delle risorse

Al concetto di risorsa si associa sempre il concetto di gestore, ossia di una entità il cui compito è quello o di consentire agli stessi processi la corretta allocazione delle risorse comuni controllandone il corretto utilizzo, o di utilizzare le risorsa per eseguire le operazioni richieste dai processi.

Il gestore delle risorse fisiche è sempre un componente del S.O. mentre il gestore delle risorse logiche può anche essere un componente di programma utente o lo stesso programmatore.

Modello ad ambiente globale

L’interazione avviene mediante memoria comune.

Il sistema è visto come un insieme di processi e oggetti (risorse).

  • O2, O3 risorse comuni
  • O1, O4 risorse private

Risorsa Gestore

E’ costituita dalla struttura dati di gestione e da procedure che operano su tale struttura (procedure d’uso).

E’ una risorsa condivisa per i processi che intendono utilizzare la risorsa gestita.

E’ ad uso non esclusivo ed è allocata staticamente dal programmatore.

Procedure d’uso che disciplinano l’accesso ad R

Procedure d’uso che disciplinano l’accesso ad R


Modello ad ambiente locale

Il sistema è visto come un insieme di processi ciascuno operante in un ambiente locale che non è accessibile direttamente a nessun altro processo.

Ogni forma di interazione tra processi (comunicazione, sincronizzazione) avviene tramite scambi di messaggi.


Processo gestore

Anche nel modello ad ambiente locale esiste il concetto di risorsa comune, ma…
… in questo caso la risorsa (con le sue strutture dati di gestione) è privata ad un processo, il processo gestore.

Un processo che intende usare la risorsa, deve interagire tramite scambio di messaggi con il processo gestore.


Strumenti di sincronizzazione

Modello ad ambiente globale:

  • semafori e primitive wait e signal.

Modello ad ambiente locale:

  • messaggi e primitive send e receive.

I materiali di supporto della lezione

P. Ancilotti, M. Boari "Programmazione concorrente e distribuita", Mc-Graw-Hill (Capp. 2 e 3)

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion