[Sistemi Operativi] Semafori

[EveyH]

Buongiorno, faccio molta fatica a capire il funzionamento dei semafori.
Per esempio ho questo esercizio, con 3 processi

P1
while true do
print (A)

P2
while true do
print (B)

P3
while true do
print (C)

L'output desiderato è ABCABC...
come vanno settati i semafori?
La soluzione è:

Occorrono i semafori s, t, v settati rispettivamente a 1, 0, 0

Quindi:

P1
while true do
s.P -->operazione di "decremento" del semaforo s (cioè, pausa?)
print (A)
t.V -->operazione di "incremento" del semaforo t (cioè, via libera?)

P2
while true do
t.P -->operazione di "decremento" del semaforo t
print (B)
v.V -->operazione di "incremento" del semaforo v

P3
while true do
v.P -->operazione di "decremento" del semaforo v
print (C)
s.V -->operazione di "incremento" del semaforo s

Qualcuno può aiutarmi a capire il ragionamento che c'è dietro a questa soluzione?
Perché, ad esempio, si è scelto di partire con il semaforo s settato a 1 e non 0?
grazie!

[apatriarca]

Se pensi ad un semaforo con un valore positivo come ad un "semaforo verde" e ad un semaforo con un valore uguale a zero come ad un "semaforo rosso" è piú facile capire perché hai bisogno che almeno uno dei semafori sia verde all'inizio. Se fossero tutti rossi sarebbero tutti fermi e se ce ne fossero piú di uno verde ci sarebbe un "incidende". Il decremento del tuo semaforo significa che il thread ha sfruttato il fatto che il tuo semaforo è verde per proseguire. Incrementare il valore del semaforo significa invece che ora un'altro thread che fa uso di quel semaforo potrà partire.

Ovviamente è molto difficile che uno decida di fare uso di programmazione concorrente in una situazione in cui l'algoritmo è completamente sequenziale.

[EveyH]

"apatriarca":Se pensi ad un semaforo con un valore positivo come ad un "semaforo verde" e ad un semaforo con un valore uguale a zero come ad un "semaforo rosso" è piú facile capire perché hai bisogno che almeno uno dei semafori sia verde all'inizio. Se fossero tutti rossi sarebbero tutti fermi e se ce ne fossero piú di uno verde ci sarebbe un "incidende". Il decremento del tuo semaforo significa che il thread ha sfruttato il fatto che il tuo semaforo è verde per proseguire. Incrementare il valore del semaforo significa invece che ora un'altro thread che fa uso di quel semaforo potrà partire.

Ovviamente è molto difficile che uno decida di fare uso di programmazione concorrente in una situazione in cui l'algoritmo è completamente sequenziale.

sì, si tratta di un esame di teoria, niente che si applichi in una situazione reale...peraltro leggevo proprio ieri che ormai i semafori sono considerati anche "obsoleti".
Comunque, per tornare all'esempio, ho capito perché almeno in un thread deve esserci una V (o una P se il semaforo viene inzializzato ad 1).

Quest'altro esempio mi è invece meno chiaro:

Riportare il codice di 2 thread che, lanciati in parallelo, permettano di ottenere come tutti e soli output possibili le stringhe CARPI e CAPRI.

Soluzione (forse):

T1
s.P
print R
t.V
print P

T2
print C
print A
s.V
t.P
print I

Con s e t inizializzati a 0.
Per come l'ho capita io:
T1 non può partire se T2 non ha stampato C ed A, dopodiché T2 incrementa S e quindi T1 può partire stampando R e incrementando T, fatto che "sveglia" T2 che... qui mi perdo. Non sono nemmeno sicura che quel "print P" sia nella posizione giusta. Dovendo stampare o CARPI o CAPRI significa che l'ordine in cui stampo la R e la P è indifferente...non riesco a "tradurre" questa clausola.
Grazie.

[apatriarca]

Puoi provare con qualcosa tipo il seguente:

T1
s.P
print R
s.V
t.V

T2
print C
print A
s.V
s.P
print P
s.V
t.P
print I

L'idea è che se T1 esegue s.P prima di T2 allora stampi prima la R, in caso contrario stampi prima la P. La I la puoi invece stampare solo dopo aver eseguito sia il codice in T1 che in T2.

[EveyH]

Vorrei ragionare su un altro esempio. Si tratta sempre di un uso dei semafori per la sincronizzazione dell'esecuzione di più processi.

Abbiamo 3 processi:

P1       P2        P3

<A>     <B>      <C>
<D>

Sia dato un sistema concorrente, stampare prima A e C insieme senza alcun vincolo sull’ordine (quindi intende dire che puoi stampare sia AC che CA; stampare poi B ed infine D (come ultima).

La soluzione dovrebbe essere:

P1		P2		P3
<A>		P(Z)		<C>
V(S)		<B>		V(T)
P(T)		V(Q)		P(S)
V(Z)		V(Z)
P(Q)
<D>

semafori (s, t, z, q) tutti inizializzati a 0.

Mentre io avevo elaborato questa:

s=0
t=0
u=0

P1		P2		P3
<A>		t.P		<C>
t.V		u.P		u.V
s.P.		<B>
<D>		s.V

Non capisco...cioè mi torna che prima di A e C non ci sia nessun blocco dato che non ci interessa l'ordine in cui vengono stampati, poi che ci sia un blocco prima di B perché invece l'ordine in cui viene stampato B è importante, come pure il blocco prima di D. Mi manca quindi capire il senso di quello che c'è dopo A e C.
Grazie mille.

[EveyH]

Mi accorgo ora della formattazione errata del messaggio, ma perché mentre sto scrivendo vedo la spaziatura corretta (copincollata da un file di testo dove è fatta con i TAB) e poi quando lo invio la perde?

[apatriarca]

La formattazione non viene mantenuta quando invii un post. Se desideri inserire del testo che deve mantenere la formattazione devi usare il tag CODE come segue:

[code]
Qui devi 
    inserire 
  il tuo testo
formattato..     

[/code]

[EveyH]

Ho sistemato la formattazione. Per quanto mi sforzi non riesco a capire perfettamente il senso degli acquisisci e rilascia presenti dopo A e dopo C. Sono arrivata a capire che non può funzionare una soluzione che preveda un signal dopo A e un signal dopo C (su due semafori "bloccati" su P2) perché, ad esempio, se P1 e P2 arrivano contemporaneamente e P3 arriva "dopo", avremmo una stampa di AB...
Ma non riesco a capire quale sarebbe il problema della mia soluzione.

[EveyH]

Faccio un'altra domanda.

P1
s1.P()
print O
print D
s2.V()

P2
print L
s1.V()
s2.P()
print E

Con s1, s2 inizializzati a 0.
Dovrei ottenere la stampa "LODE". E' così?

[EveyH]

Ho avuto conferma che la mia soluzione con 3 semafori dell'esercizio sui 3 processi è in realtà corretta. Mi sono scervellata per niente