Modellare un sistema: rappresentarlo in termini di oggetti matematici che ne riflettono le propriet`a

(1)

Modellazione di sistemi software (Peled, cap. 4)

Modellare un sistema: rappresentarlo in termini di oggetti matematici che ne riflettono le propriet`a

Modellare implica astrarre: semplificare la descrizione del sistema, conservando solo alcuni dei dettagli originari, focalizzandosi sulle propriet`a principali e riuscendone a gestire la complessit`a

Ad esempio, spesso si ignora la durata temporale dei processi

Nelle metodologie di sviluppo del SW per raffinamenti: si definisce il modello, se ne verificano le propriet`a, poi si concretizza in codice

Sistemi sequenziali sono pi`u semplici da modellare rispetto a quelli concorrenti Formalismi di modellazione

Molti formalismi sono linguaggi di programmazione: si deve programmare la descrizione astratta del sistema.

In alcuni casi ci sono traduttori automatici dalla descrizione originaria del sistema al formalismo di modellazione.

Normalmente per`o l’astrazione viene eseguita manualmente

(2)

Sistemi di Transizioni (TS)

Costituiscono un formalismo astratto e generale per la descrizione di sistemi SW.

Il comportamento di un sistema (sequenziale o concorrente) `e descritto come se eseguisse una ed un’unica azione elementare (transizione) alla volta, che trasformano uno stato del sistema in un altro.

Il sistema si trova cio`e in ogni istante in uno stato, dal quale pu`o eseguire una transizione tra quelle abilitate in quello stato.

Ogni transizione t abilitata in uno stato s trasforma s in uno stato s

^′

= t(s) Il processo continua finch´e si pu`o eseguire almeno una transizione.

Linguaggio: per descrivere il comportamento di un sistema, si definisce innanzitutto un linguaggio per rappresentare le variabili, i valori, le operazioni e le relazioni di cui occorre parlare, cio`e una segnatura

G = hV, F, Ri Inoltre, si stabilisce:

• quali sono i valori che possono assumere le variabili e le costanti del linguaggio: un dominio D

• come si vogliono interpretare le costanti, i simboli di funzione e di predicato: una fun- zione di interpretazione f e l’insieme F ∪ R su cui interpreta i simboli di funzione in F e quelli di relazione in R.

In sostanza, si definisce una struttura del primo ordine, costituita da una segnatura

G e un’interpretazione M di G, sulla base della quale si descriver`a il sistema.

(3)

Stati

Uno stato “contiene” tutti i valori delle variabili del programma.

Se le variabili del programma corrispondono a elementi di V :

variabili di programma ⇒ variabili logiche program counter(s) ⇒ variabili logiche allora uno stato `e un’assegnazione a : V → D:

stati ⇒ assegnazioni Esempio: siano V = {x, y} e D = IN. Lo stato

x = 2 y = 1

`e l’assegnazione a tale che a(x) = 2 e a(y) = 1.

Una formula senza quantificatori rappresenta un insieme di stati: tutti gli stati in cui

`e vera

formula F ⇒ {a | (M, a) |= F }

(x > 2 ∧ y ≤ 3) ∨ x = 0 x = 0

y = 1

x = 2 y = 1

x = 3 y = 1

x = 4 y = 2

x = 4

y = 4

(4)

Sistemi descritti in un linguaggio proposizionale

Se non interessano i valori specifici delle variabili, ma solo la verità o falsità di relazioni tra di esse (x > y), si può usare un linguaggio proposizionale:

• La segnatura G `e costituita semplicemente da un insieme P di lettere proposizionali (o variabili proposizionali) – le costanti true e f alse e i connettivi proposizionali sono simboli logici;

• il dominio dell’interpretazione M `e Bool = {T RU E, F ALSE}

• un’assegnazione a `e un’interpretazione proposizionale Uno stato `e dunque un’interpretazione proposizionale.

stato ⇒ a : P → Bool

Un’interpretazione proposizionale a si pu`o rappresentare mediante un insieme di variabili proposizionali: tutte e solo quelle vere in a

{p ∈ P | a(p) = T RU E}

Ad esempio, se P = {rich, work}

lo stato {work} `e l’interpretazione a tale che a(work) = T RU E e a(rich) = F ALSE formula F ⇒ {a | a |= F }

work ⇒











{work} , {work, rich}











(5)

Transizioni

Il sistema si trova in ogni istante in uno stato, dal quale pu`o eseguire una transizione tra quelle abilitate in quello stato.

Ogni transizione t abilitata in uno stato s trasforma s in uno stato s

^′

= t(s) Quindi una transizione t `e caratterizzata da:

• una condizione di abilitazione, che specifica a quali stati `e applicabile

⇒ una formula senza quantificatori, che identifica l’insieme degli stati a cui t `e applica- bile;

• una descrizione dello stato t(s) che si ottiene applicando t al generico stato s:

⇒ una descrizione di come vengono modificati i valori delle variabili passando da s a t(s).

Stati iniziali

Infine, si deve identificare l’insieme degli stati iniziali del sistema

⇒ una formula senza quantificatori

(6)

Sistemi di transizione: definizione Un sistema di transizioni (TS) `e una tripla:

(S, T, Θ)

• S `e una struttura del primo ordine (G, D, F, R, f ), con G = (V, F, R) – oppure, nella nostra notazione: S = hG, Mi.

L’insieme delle variabili V di G include le variabili di programma e i program counters

• T : insieme finito di transizioni Ogni t ∈ T ha la forma

p → (v

1

, v

2

, ..., v

_n

) := (e

1

, e

2

, ..., e

_n

) dove:

la condizione p `e una formula senza quantificatori, v

1

, v

2

, ..., v

_n

∈ V

e

1

, e

2

, ..., e

_n

∈ terms(G)

• Θ: condizione iniziale (formula senza quantificatori, che identifica gli stati iniziali).

(7)

Transizioni

Una transizione t : p → (v

1

, v

2

, ..., v

_n

) := (e

1

, e

2

, ..., e

_n

) `e abilitata (si pu`o eseguire) in ogni stato s che soddisfa p (enabledness condition di t):

t `e abilitata in s sse (M, s) |= p (nella notazione di Peled: s |=

^S

p)

Come cambiano i valori delle variabili: se s

^′

= t(s) `e lo stato che si ottiene eseguendo t in s, allora

s

^′

(v

_i

) =







T

_s

(e

_i

) se 1 ≤ i ≤ n s(v

i

) altrimenti

• per i = 1, ..., n, il valore di v

_i

in s

^′

`e il valore di e

_i

in s:

s

^′

(v

_i

) = T

_s

(e

_i

)

• per ogni altra variabile v 6∈ {v

1

, v

2

, ..., v

_n

}, il valore di v in t(s) resta uguale al valore di v in s:

s

^′

(v) = s(v)

In altri termini, t(s) `e la variante di s che assegna T

_s

(e

1

) a v

1

,...,T

_s

(e

_n

) a v

_n

: t(s) = s[T

_s

(e

1

)/v

1

, ..., T

_s

(e

_n

)/v

_n

]

Si specificano solo i valori che cambiano nel passaggio da s a t(s).

(8)

Esempio

t : x < y → (x, y) := (y, x) L’assegnazione (x, y) := (y, x) scambia i valori di x e y.

s =

x = 0 y = 1 z = 3

s

^′

=

x = 1 y = 0 z = 3

t `e abilitata in s e t(s) = s

^′

t non `e abilitata in s

^′

(9)

Sistemi di transizioni su un linguaggio proposizionale

• G = P `e l’insieme delle variabili proposizionali del linguaggio

• Θ `e una formula proposizionale

• In una transizione

t : p → (v

1

, v

2

, ..., v

_n

) := (e

1

, e

2

, ..., e

_n

) – p `e una formula del linguaggio;

– v

_i

`e una variabile proposizionale, per i = 1, ..., n;

– e

i

`e una formula, per i = 1, ..., n.

Esempio: con P = {rich, work}, sia

t : work → (work, rich) := (f alse, ¬rich)

s

0

= {work} −→

^t

{rich} = t(s

0

)

s

1

= {work, rich}

−→

t

Ø = t(s

1

)

t non `e abilitata n´e in t(s

0

) n´e in t(s

1

).

(10)

Esecuzioni (run)

Una esecuzione (run) di un sistema `e una sequenza massimale di stati, che inizia in uno stato che soddisfa la condizione iniziale e dove ogni stato si ottiene dal precedente mediante una transizione.

Un’esecuzione termina solo se nell’ultimo stato non `e abilitata alcuna transizione.

Per semplificare, ed evitare di avere sia esecuzioni finite che infinite, si considerano soltanto esecuzioni infinite: esecuzioni finite sono rappresentate da sequenze infinite in cui l’ultimo stato si ripete all’infinito.

Un’esecuzione di un sistema `e dunque una sequenza infinita di stati s

0

, s

1

, ... tali che:

• (M, s

0

) |= Θ (s

0

|=

^S

Θ )

• per ogni i, vale uno di questi due casi:

– esiste una transizione t : p → (v

1

, v

2

, ..., v

_n

) := (e

1

, e

2

, ..., e

_n

) abilitata in s

_i

, cio`e tale che

(M, s

_i

) |= p e s

i+1

= t(s

i

), cio`e

s

_i+1

= s

_i

[T

_si

(e

1

)/v

1

, ..., T

_si

(e

_n

)/v

_n

] – nessuna transizione `e abilitata in s

_i

e s

_i+1

= s

_i

Stati raggiungibili: quelli che compaiono in qualche esecuzione del sistema

(11)

Esempio

Sistema di transizioni sul linguaggio proposizionale P = {work, rich}

Θ = ¬rich ∧ work

t

1

: work → work := f alse t

2

: ¬rich → work := true

t

3

: work → (rich, work) := (true, f alse) t

4

: rich → rich := rich

Un sistema di transizioni genera uno spazio di stati: l’insieme degli stati che possono essere generati dal sistema e delle transizioni tra di essi.

s1 {work}

t2 s2

t1 {}

s3 {rich}

t3 t2

t4

Un sistema di transizioni `e un modo per descrivere implicitamente uno spazio di stati.

(12)

Esempio di modellazione di un programma Divisione intera

Divisione del valore in x1 per il valore in x2. Quoziente in y1, resto in y2.

Versione etichettata del programma m1: y1:=0;

m2: y2:=x1;

m3: while y2 >= x2 do

m4: y1:=y1+1;

m5: y2:=y2-x2

m6: end

Segnatura: V = {x

1

, x

2

, y

1

, y

2

, pc} F = {0, 1, m

1

, ..., m

6

, +, −} R = {≥}

Interpretazione: Dominio: IN; Interpretazione standard su IN dei simboli in R e F , arbitraria quella delle etichette (purch´e distinte).

Stato iniziale: Θ = x

2

> 0 ∧ pc = m

1

Transizioni:

t

1

: pc = m

1

→ (pc, y

1

) := (m

2

, 0) t

2

: pc = m

2

→ (pc, y

2

) := (m

3

, x

1

)

t

3

: pc = m

3

→ pc := if (y

2

≥ x

2

, m

4

, m

6

) oppure:







t

3

: pc = m

3

∧ y

2

≥ x

2

→ pc := m

4

t

^′₃

: pc = m

3

∧ y

2

< x

2

→ pc := m

6

t

4

: pc = m

4

→ (pc, y

1

) := (m

5

, y

1

+ 1)

t

5

: pc = m

5

→ (pc, y

2

) := (m

3

, y

2

− x

2

)

(13)

Sistemi concorrenti

La modellazione di un sistema concorrente mediante un TS si basa sul modello interleaving del calcolo

E un modello pi`u semplice di altri, secondo il quale un sistema concorrente viene modellato ` assumendo che tutti gli eventi di una singola esecuzione siano ordinati in un ordine lineare, chiamato interleaving sequence.

Transizioni eseguite contemporaneamente appaiono ordinate linearmente.

L’esecuzione delle componenti del sistema concorrente `e asincrona o alternata (inter- leaved).

Qui assumiamo inoltre che la comunicazione tra componenti del sistema concorrente avvenga

mediante variabili condivise (e non message passing).

(14)

Interleaving model

Secondo l’interleaving model viene eseguita una transizione alla volta: se ci sono pi`u processi la loro esecuzione `e alternata (modello della multiprogrammazione).

In realt`a non `e sempre cos`ı, nei sistemi distribuiti le transizioni possono essere contempo- ranee. Ma spesso sono commutative:

x = 1 y = 1

x = 2 y = 2 α : x := x + 1

β : y := y + 1

rappresentato da

x = 1 y = 1

x = 2 y = 1 α : x := x + 1

x = 1 y = 2 β : y := y + 1

x = 2 y = 2 β : y := y + 1

α : x := x + 1

Se le transizioni non sono commutative (esempio α : x := x + 1 e β : x := x × 2) non

possono essere eseguite contemporaneamente

(15)

Esempio Due processi: P

1

e P

2

P

1

: x := x + y; P

2

: y := y + x Stato iniziale: x = 2, y = 3

Versione etichettata dei due programmi

l1: x:=x+y r1: y:=y+x

l2: end r2: end

Sistema di transizioni:

• S = (G, D, F, R, f ) con

– G = (V, F, R), V = {x, y, pc

_l

, pc

_r

), F = {l

1

, l

2

, r

1

, r

2

, +}, R = {=}

– D = IN, interpretazione standard di = e +, interpretazione arbitraria di l

1

, l

2

, r

1

, r

2

.

• Transizioni:

t

1

: pc

_l

= l

1

→ (pc

_l

, x) := (l

2

, x + y) t

2

: pc

r

= r

1

→ (pc

r

, y) := (r

2

, y + x)

• Θ = x = 2 ∧ y = 3 ∧ pc

_l

= l

1

∧ pc

_r

= r

1

Esercizio: disegnare lo spazio degli stati raggiungibili corrispondente al TS dato. Identi-

ficare le esecuzioni del sistema.

(16)

Granularit` a delle transizioni

Nella maggior parte dei casi la modellazione di un sistema `e fatta manualmente: non esiste ricetta generale

Uno dei problemi pi`u delicati `e quello della scelta del livello di dettaglio appropriato

• Granularit`a troppo piccola (troppi dettagli): il modello contiene pi`u informazioni di quelle che servono.

Esplosione dello spazio degli stati

• Granularit`a troppo grande (pochi dettagli): si possono perdere informazioni sull’intera-

zione tra processi e non si coprono tutti i comportamenti possibili

(17)

Esempio Due processi: P

1

e P

2

P

1

: x := x + y; P

2

: y := y + x Stato iniziale: x = 2, y = 3

Modello A. A ogni istruzione del linguaggio corrisponde una transizione Ci sono due esecuzioni possibli:

• prima P

1

poi P

2

: stato finale x = 5, y = 8

• prima P

2

poi P

1

: stato finale x = 7, y = 5

Modello B. Le variabili sono conservate nelle locazioni m100 e m111, rispettivamente.

Vengono caricate nei registri r

1

e r

2

, sono eseguite le addizioni, e i valori rimemorizzati nelle locazioni rispettive.

P

1

: load r1, m100 P

2

: load r2, m1111

add r1, m111 add r2, m100

store r1, m100 store r2, m111

Assumiamo che i valori iniziali dei registri sia 0.

Se ogni istruzione corrisponde a una transizione, ci sono 20 esecuzioni alternate (inter-

leaved) possibili.

(18)

La sequenza seguente load r1, m100 load r2, m111 add r1, m111 add r2, m100 store r1, m100 store r2, m111

risulta nello stato in cui

x = m100 = 5 y = m111 = 5

Con il primo modello: non si coglie una possibile interazione tra istruzioni macchina. La verifica potrebbe non identificare possibili errori.

Con il secondo modello: se l’implementazione reale corrisponde alla granularità più alta, il modello include comportamenti che in realtà non sono possibili (falsi negativi)

Esercizio: definire un TS corrispondente al modello B e disegnare lo spazio degli stati

raggiungibili

(19)

Combinazioni







n k







= n × (n − 1) × ... × (n − k + 1) 1 × 2 × ... × k

= 1 × n × (n − 1) × ... × (n − (k − 1)) 1 × 2 × ... × k

=

1 × n

1 × (n − 1)

2 × (n − 2)

· · ·

k − 1 × (n − (k − 1)) k

Dopo p moltiplicazioni, si possono fare le prime p divisioni, ma non ancora la (p + 1)-esima Valori iniziali: y1=n, y2=0, y3=1

y1 va da n a n-k+1: n-y1 conta le moltiplicazioni y2 va da 0 a k-1: conta le divisioni

y3: risultato finale

l1: if y1 = n-k then halt r1: if y2=k then halt

l2: y3:=y3*y1 r2: y2:=y2+1

l3: y1:=y1-1 r3: await y2 <= n-y1

l4: goto l1 r4: y3:=y3/y2

r5: goto r1

(20)

Combinazioni (II) Segnatura: ...

Interpretazione: ...

t

1

: pc

_l

= l

1

→ pc

_l

:= if (y

1

= n − k, halt

_l

, l

2

) t

2

: pc

l

= l

2

→ (pc

l

, y

3

) := (l

3

, y

3

× y

1

)

t

3

: pc

_l

= l

3

→ (pc

_l

, y

1

) := (l

4

, y

1

− 1) t

4

: pc

_l

= l

4

→ pc

_l

:= l

1

t

5

: pc

_r

= r

1

→ pc

_r

:= if (y

2

= k, halt

_r

, r

2

) t

6

: pc

_r

= r

2

→ (pc

_r

, y

2

) := (r

3

, y

2

+ 1) t

7

: pc

_r

= r

3

∧ y

2

≤ n − y

1

→ pc

_r

:= r

4

t

8

: pc

_r

= r

4

→ (pc

_r

, y

3

) := (r

5

, y

3

/y

2

) t

9

: pc

_r

= r

5

→ pc

_r

:= r

1

Θ = y

1

= n ∧ y

2

= 0 ∧ y

3

= 1 ∧ pc

_l

= l

1

∧ pc

_r

= r

1

∧ n > 0 ∧ k > 0

(21)

Alcuni stati raggiungibili per n = 3, k = 2 stato pc

l

pc

r

y

1

y

2

y

3

s1 l

1

r

1

3 0 1 s2 l

2

r

1

3 0 1 s3 l

2

r

2

3 0 1 s4 l

3

r

1

3 0 3 s5 l

3

r

2

3 0 1 s6 l

4

r

2

2 0 1 s7 l

2

r

3

3 1 1

s1

t1 s2

s3 t5

t2 s4

t5 s5

t6 s7

t3 s6

(22)

Il setaccio di Eratostene Per generare tutti i numeri primi minori o uguali a P :

1. Mettere nel setaccio tutti i numeri interi compresi tra 2 e P 2. Ripetere finch´e il setaccio non `e vuoto:

(a) Togliere dal setaccio il numero pi`u piccolo M e includerlo tra i numeri primi (b) Rimuovere dal setaccio tutti i multipli di M

• Processo di sinistra: genera gli interi da 2 a P

• N processi di mezzo: l’i-esimo processo di mezzo conserva l’i-esimo numero primo P

_i

e filtra i successivi, passando al processo seguente solo quelli che non sono multipli di P

_i

• Processo di destra: conserva l’N + 1-esimo numero primo.

(23)

Mutua esclusione

Due processi in competizione per entrare in una sezione critica in cui utilizzano una risorsa condivisa. Quando un processo non `e nella sua sezione critica, `e nella sezione non critica.

Propriet`a del protocollo che gestisce la concorrenza:

Esclusione: i processi non entrano contemporaneamente nelle rispettive sezioni critiche Liveness: se un processo richiede di accedere alla sezione critica, gli sar`a consentito in un

tempo finito.

Un tentativo di risolvere il problema della mutua esclusione boolean c1, c2 initially 1

P1::

m1: while true do

m2: (* noncritical section 1 *) m3: c1:=0;

m4: wait until c2=1

m5: (* critical section 1 *) m6: c1:=1

end

P2::

n1: while true do

n2: (* noncritical section 2 *) n3: c2:=0;

n4: wait until c1=1

n5: (* critical section 1 *) n6: c2:=1

end

Si assume che le sezioni non critiche non cambino i valori di c1 e c2.

Una sezione non critica potrebbe non terminare, ma le sezioni critiche terminano sempre

(24)

Sistema di transizioni t1 : pc

1

= m1 → pc

1

:= m2 t2 : pc

1

= m2 → pc

1

:= m3

t2

^′

: pc

1

= m2 → pc

1

:= m2 (* loop *) t3 : pc

1

= m3 → (pc

1

, c1) := (m4, 0) t4 : pc

1

= m4 ∧ c2 = 1 → pc

1

:= m5

t5 : pc

1

= m5 → pc

1

:= m6

t6 : pc

1

= m6 → (pc

1

, c1) := (m1, 1) t7 : pc

2

= n1 → pc

2

:= n2

t8 : pc

2

= n2 → pc

2

:= n3

t8

^′

: pc

2

= n2 → pc

2

:= n2 (* loop *) t9 : pc

2

= n3 → (pc

2

, c2) := (n4, 0) t10 : pc

2

= n4 ∧ c1 = 1 → pc

2

:= n5

t11 : pc

2

= n5 → pc

2

:= n6

t12 : pc

2

= n6 → (pc

2

, c2) := (n1, 1) Θ = pc

1

= m1 ∧ pc

2

= n1 ∧ c1 = 1 ∧ c2 = 1

Esercizio: rappresentare (una parte di) lo spazio degli stati generato, in particolare quel-

lo contenente gli stati generati dalla sequenza di transizioni t1, t2, t3, t7, t8, t9. Ci sono

transizioni abilitate nello stato che si ottiene?

(25)

Automi

Un TS descrive implicitamente lo spazio degli stati del sistema (l’insieme degli stati e delle transizioni): un automa (un grafo)

A = (S, ∆, I) dove:

• S: insieme di stati

• ∆ ⊆ S × S: relazione di transizione

(s, s

^′

) ∈ ∆ se esiste una transizione atomica da s a s

^′

• I ⊆ S: insieme degli stati iniziali

Si possono aggiungere altre componenti: etichette sugli archi, etichette sugli stati, ...

Esecuzioni (run)

Una run dell’automa (S, ∆, I) `e una sequnza massimale s

0

, s

1

, ... tale che:

• s

0

∈ I

• per ogni i: (s

_i

, s

_i+1

) ∈ ∆

Massimale: o `e infinita, oppure l’ultimo stato non ha successori (nessuna transizione `e

abilitata)

(26)

Automi con etichettatura degli stati A = (S, ∆, I, L, Σ) dove S, ∆, I sono come sopra e:

• Σ `e l’alfabeto: un insieme (di etichette);

• L : S → Σ `e una funzione che associa un’etichetta a ciascuno stato.

(27)

Strutture di Kripke

Automi in cui ogni stato ` e etichettato da un insieme di variabili proposizionali

(S, ∆, I, L

P

, 2

^P

)

dove P `e un insieme di variabili proposizionali

Per rappresentare propriet`a di sistemi a stati finiti spesso si usano formalismi proposizionali.

Ogni stato del sistema `e allora etichettato da un insieme di lettere proposizionali L

_P

: S → 2

^P

dove P `e l’insieme di variabili proposizionali che rappresentano propriet`a del sistema L

P

(s) `e l’insieme delle variabili proposizionali vere in s

Questo equivale a considerare ogni stato come un’assegnazione a variabili booleane, o un’interpretazione proposizionale, dove

s |= p sse p ∈ L

_P

(s)

(28)

ASSUNZIONI DI FAIRNESS

A volte non si vogliono considerare tutte le esecuzioni del modello del sistema, perch´e alcune di esse, sebbene presenti nel modello, non lo sono nel sistema

Assunzioni di fairness: vincoli semantici imposti sulle esecuzioni, per escludere quelle irragionevoli

Esempio: P

1

e P

2

eseguiti per sempre, senza interazioni

Una esecuzione alternata `e s

0

, s

1

, ... con s

_i+1

ottenuto da s

_i

eseguendo una transizione di P

1

o una di P

2

. In ogni stato `e sempre abilitata sia una transizione di P

1

che una di P

2

.

Nel modello ci sono anche esecuzioni dove, da un certo punto in poi, si eseguono solo transizioni di P

1

(o di P

2

).

Una rappresentazione fedele dovrebbe soddisfare il vincolo di fairness: ogni esecu- zione contiene un numero infinito di transizioni di ciascun processo.

Una modellazione esatta dovrebbe tener conto dello scheduler reale, ma il modello sarebbe troppo specifico e poco pratico.

Si usa un modello pi`u semplice con fairness constraints che escludono le esecuzioni

irragionevoli.

(29)

Vincoli di fairness semplici

In alcuni formalismi, un vincolo di fairness `e espresso mediante un insieme di stati f ⊆ S

un path `e fair se contiene un elemento di f infinitamente spesso.

Un insieme di vincoli di fairness `e un insieme F ⊆ 2

^S

: F = {f

1

, ..., f

_k

} con f

_i

⊆ S

Un’esecuzione ` e fair se, per ciascun i = 1, ..., k, contiene infinite occorrenze di un elemento di f

_i

.

In un sistema di transizioni, in cui sono definite una segnatura e la sua interpretazione, un vincolo di fairness (insieme di stati) si pu`o rappresentare mediante una formula senza quantificatori F :

s ∈ f se e solo se (M, s) |= F

(30)

Esempio 1 P

1

:: x:=1 P

2

:: while y=0 do

[ no op # if x=1 then y:=1 ] /* #: scelta non deterministica La variabile x `e condivisa, y `e locale a P

2

. Entrambe inizializzate a 0.

Variabili per i program counter: pc

l

e pc

r

, con valori l

0

e l

1

, e r

0

e r

1

, rispettivamente.

Versione etichettata:

P1 P2

l0: x:=1 r0: while y=0 do

l1: end r1: no_op # if x=1 then y:=1

Transizioni:

t

0

: pc

_l

= l

0

→ (pc

_l

, x) := (l

1

, 1)

t

1

: pc

_r

= r

0

∧ y = 0 → pc

_r

:= r

1

(inizio del ciclo)

t

2

: pc

_r

= r

1

→ pc

_r

:= r

0

(esecuzione di no op e ritorno a inizio ciclo) t

3

: pc

_r

= r

1

∧ x = 1 → (pc

_r

, y) := (r

0

, 1) (assegnazione e ritorno a inizio ciclo)

Condizione iniziale:

Θ : x = 0 ∧ y = 0 ∧ pc

_l

= l

0

∧ pc

_r

= r

0

(31)

Esempio 1 (continua)

0 0 l

0

r

0

1 0 l

1

r

0

0 0 l

0

r

1

1 0 l

1

r

1

1 1 l

1

r

0

t

0

t

1

t

2

t

1

t

2

t

0

t

3

Il modello non esclude esecuzioni in cui non viene mai eseguita la transizione t

0

oppure la t

3

.

Se si sa che lo scheduler reale in realt`a esclude tali esecuzioni si pu`o aggiungere al modello del sistema il vincolo di fairness

f =







1 1 l

1

r

0







Equivalentemente, il vincolo si pu`o esprimere mediante una formula F : y = 1

Le esecuzioni fair sono quelle che rendono vero y = 1 infinite volte.

(32)

Esempio 2

s1 {work}

t2 s2

t1 {}

s3 {rich}

t3 t2

t4

Se vogliamo escludere (come irrealistiche!) tutte le esecuzioni in cui non si diventa mai ricchi, si pu`o aggiungere alla descrizione del sistema il vincolo di fairness

f = {s3}

O, equivalentemente,

F = rich Infatti F `e vera in tutti e soli gli stati di f

Le esecuzioni fair sono quelle che rendono vere F infinitamente spesso: cio`e quelle che contengono s3:

s1, ..., s1, s3, s3, s3, s3, ....

(33)

Esempio 3: il comportamento di un semaforo

s0 {green}

s1 {yellow}

s2 {red}

Se si vogliono escludere come irrealistiche le esecuzioni in cui da un certo punto in poi il semaforo resta indefinitivamente dello stesso colore, si possono aggiungere i vincoli di fairness

F = {f

1

, f

2

} con f

1

= {s0} e f

2

= {s2}

I due vincoli di fairness possono essere espressi mediante l’insieme di formule

Φ = {green, red}

(34)

Esempio 4: due processi con una risorsa condivisa

s0 {}

s1 {reqB}

s2 {reqA}

s6 {serveB}

s3 {reqA,

reqB}

s7 {serveA}

s4 {serveA,

reqB}

s5 {serveB,

reqA}

Si vogliono escludere le esecuzioni in cui:

• uno dei due processi, pur avendo richie- sto di accedere alla risorsa condivisa, non venga mai servito;

• il servizio di un processo duri all’infinito.

Esecuzioni fair:

per ogni stato t dell’esecuzione, se t contiene reqX (per X = A o X = B), allora esiste uno stato t

^′

successivo a t che non contiene reqX (X `e stato servito e il suo servizio `e terminato).

F = {{s0, s4}, {s0, s5}}

{s0, s4} ⇒ (¬reqA ∧ ¬serveB ∧ ¬reqB ∧ ¬serveA)

∨(¬reqA ∧ ¬serveB ∧ reqB ∧ serveA)

↔ ¬reqA ∧ ¬serveB ∧ (reqB ≡ serveA)

Φ = {¬reqA ∧ ¬serveB ∧ (reqB ≡ serveA), ¬reqB ∧ ¬serveA ∧ (reqA ≡ serveB)}

(35)