Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
vuoi
o PayPal
tutte le volte che vuoi
Descrizione del meccanismo di scheduling First-come-first-served
Il meccanismo di scheduling First-come-first-served garantisce che i thread vengano serviti nell'ordine in cui arrivano, garantendo l'accesso alla sezione critica.
Se un thread A finisce la sua doorway prima che un thread B inizi la sua doorway, allora A non può essere sorpassato da B. Questo significa che A accede alla sezione critica prima di B.
Il meccanismo First-come-first-served garantisce che non ci sia starvation, poiché una volta che un thread ha finito la sua doorway, ci saranno due gruppi di thread: quelli che iniziano la doorway dopo e quelli che hanno finito la doorway prima o che l'hanno fatta concorrentemente.
I thread che hanno finito la doorway prima o che l'hanno fatta concorrentemente possono essere schedulati prima degli altri, ma sono un numero finito. Quindi, anche se questi thread vengono eseguiti prima, grazie al meccanismo First-come-first-served, i thread successivi riusciranno comunque ad accedere alla sezione critica.
accedere alla CS). Sezione critica per 2 thread Presentiamo due algoritmi LockOne e LockTwo entrambi offrono la mutua esclusione ma ciascuno di loro non è deadlock-free e ciascuno in situazioni diverse e complementari (quando i task sono interfogliati o quando vengono eseguiti uno dopo l'altro). Mentre il lock di Peterson, unisce le tecniche dei due algoritmi, soddisfacendo la mutua esclusione e il deadlock-free. - Indichiamo con w (x = v) l'evento (operazione non interrompibile) in cui A assegna il valore v ad x. - Indichiamo con r (v == x) l'evento in cui A legge dalla variabile x un valore v. Teorema LockOne soddisfa la mutua esclusione, (dimostrazione) per contraddizione ∃ una coppia di interi j, k tali che: ¬(kA jB jB kA CS CS e CS CS) (cioè supponiamo che entrambi i thread sono in CS). L'ultima volta che il thread A ha eseguito lock() prima del conflitto ha scritto che era interessato e ha verificato che B non era interessato (nel while) e poi<p>è entrato in sezione critica: w (flag[A] = true) → r (flag[B] == false) → CSA A AViceversa stessa cosa per B: w (flag[B] = true) → r (flag[A] == false) → CSB B B</p> <p>Poiché quando flag[B] è messo a true da B, nessuno lo cambia (quindi se entrambi per contraddizione nellasezione critica, allora la lettura che ha fatto A, che flag[B] era a false è dovuta avvenire prima che B abbiascritto flag[B] a true) allora: r (flag[B] == false) → w (flag[B] = true)A BMa w (flag[A] = true) → r (flag[B] == false) → w (flag[B] = true) → r (flag[A] == false)A A B Bw (flag[A] = true) → r (flag[A] == false) ma è un assurdo perché nessun altro modifica flag[A] tranne A,A Bquindi Lockone soddisfa la mutua esclusione.Non è deadlock-freeSe la esecuzione dei thread si “interfogliano” cioè w (flag[A] = true) e w (flag[B] = true) capitano prima diA Br (flag[B]) e r (flag[A]), cioè tutti e due</p>
continueranno ad attendere che l'altro sblocchi.
Teorema 9
LockTwo soddisfa la mutua esclusione, (dimostrazione) per contraddizione ∃ una coppia di interi j, k taliche:
→ kA jB jB kACS CS e CS CS (cioè supponiamo che entrambi i thread sono in CS).
L'ultima volta che il thread A ha eseguito lock() prima del conflitto (quindi è entrato) ha dato precedenza e poi ha verificato che B dava precedenza (quindi la vittima non era più A ma B) e poi entra in CS.
w (victim = A) → r (victim == B) → CS (1)
A A A
Stessa cosa per B: w (victim = B) → r (victim == A) → CS (2)
B B B
B deve assegnare B a victim tra gli eventi w (victim = A) e r (victim == B)
A A
Quindi w (victim = A) → w (victim = B) → r (victim == B), ma a questo punto victim non cambia e ogni lettura restituisce B contraddicendo (2).
Non è deadlock-free
Se un thread viene eseguito prima dell'altro c'è deadlock (se il thread B non fa nulla o ha finito,
Allora Arimane lì in attesa senza mai entrare), ma se i due thread si interfogliano, il metodo lock() ha successo.
Teorema
Il Lock di Peterson soddisfa la mutua esclusione, (dimostrazione) per contraddizione ∃ una coppia di interi j,↛ ↛kA jB jB kAk tali che: CS CS e CS CS (cioè supponiamo che entrambi i thread sono in CS).
Consideriamo l'ultima esecuzione del lock() di A e B (entrambe in sezione critica).
A ha scritto il suo flag a true (segnala interesse) ma dà la precedenza a B (setta la variabile di victim ad A), poi rimane a leggere il flag di B e contemporaneamente victim finché le condizioni non diventano vere e poi entra in CS.
Formalmente: w (flag[A] = true) → w (victim = A) → r (flag[B]) → r (victim) → CS (1)
A A A A A
Viceversa stessa cosa per B: w (flag[B] = true) → w (victim = B) → r (flag[A]) → r (victim) → CS (2)
B B B B B
(fissiamo A ma si può fare anche con B) Sia A l'ultimo a scrivere
victim allora: w (victim = B) → w (victim = A)
B A
Se A entra in CS, allora flag[B] = false e quindi la scrittura di A = victim è avvenuta prima, cioè
w (victim = A) → r (flag[B]==false)
A A
Ma: w (flag[B] = true) → w (victim = B) → w (victim = A) → r (flag[B]==false)
Contraddizione!
B B A A
Il Lock di Petereson è starvation-free
Prova: supponiamo per assurdo che A sia sempre nel metodo lock(), e deve eseguire l'istruzione while, in attesa che l'una o l'altra condizione (flag[B] diventi false o che la victim sia impostata su B) lo facciano entrare in CS. Cosa sta facendo B mentre A non riesce a fare progressi? Forse B sta entrando e uscendo ripetutamente dalla sua sezione critica. In tal caso, tuttavia, B imposta la victim su B non appena rientra nella sezione critica. Una volta che la victim è impostata su B, non cambia e A deve infine tornare dal metodo lock(), una contraddizione. Quindi deve essere che anche B sia bloccato nella
Corollario: Il lock di Peterson algorithm è deadlock-free
Sezione critica per N thread
L’algoritmo del “Panettiere” (Bakery)
Algoritmo sviluppato da Leslie Lamport. First-come-first-served: una versione distribuita di una macchinetta che distribuisce i numeri dal “panettiere”, ogni thread prende un numero durante la doorway ed aspetta fino a quando non c’è più nessun thread in attesa con un numero più “basso” del proprio, garantendo la deadlock-free. Due o più thread possono eseguire la doorway contemporaneamente (stessa etichetta), la soluzione: il confronto viene effettuato “lessicograficamente” (prima le etichette più piccole) concatenando la proprio ID (che è univoco). Nel momento che le etichette
dovesserocorrispondere allora la parte rilevante sarà l'ID, il thread con l'ID più basso precederà quello con l'ID più alto. Teorema Bakery è deadlock-free Tra i thread in attesa (flag[A] settato a true) ce ne sarà uno (sia A) con una certa etichetta (label[A], A) che risulta essere sempre la più piccola ed entra. Questo thread non attenderà nessun altro thread, in ogni situazione, ci sarà sempre qualcuno con etichetta più piccola con questa definizione di ordine lessicografico e quindi la risorsa sarà sempre possibile accedervi. Teorema Bakery è FCFS (first-come-first-served e quindi è starvation-free) Se due thread termina la doorway in due tempi diversi, cioè: D -> D. Allora la label di A precede quella di A BB (B avrà un etichetta più grande). Infatti: w (label[A]) -> r (label[A]) -> w (label[B]) -> r (flag[A]) A B B B Quindi B non entra in quantoflag[A] è settato a true. (Dimostrato!)
Nota: è starvation-free perché anche l'ultimo thread che avrà, magari, la stessa etichetta di molti altri thread e un ID più elevato degli altri, dovrà aspettare un tempo finito.
Teorema Bakery ha ME
Supponiamo per assurdo che due thread A e B siano insieme in CS. E labeling sia l'insieme degli eventi per A
calcolare le label di A prima di entrare in CS (label[A], A) << (label[B], B)
Se sono insieme in critical section allora hanno superato la parte di waiting, quando B ha superato questa
parte allora deve aver letto che flag[A] era uguale a false altrimenti non avrebbe potuto superare la
waiting. Quindi A ha la label più piccola e il flag a false. 11
Quindi labeling → r (flag[A]) → w (flag[A]) → labeling
B B A A
Ma in questa maniera (label[B], B) << (label[A], A) (contraddizione).
Bounded TimeStamps
Problema nell'algoritmo del Panettiere: etichette che crescono sempre,
Il testo fornito descrive un grafo con un numero finito di nodi. Gli archi nel grafo sono rappresentati dalla freccia → e indicano che un nodo a ha un timestamp "preso" dopo il nodo b (cioè b è in fila prima di a). L'ordine dei timestamp è irriflessivo (non ci sono loop, un nodo non può puntare a se stesso) e antisimmetrico (se esiste un arco a → b, non esiste l'arco b → a). Non è richiesta la transitività: se a → b e b → c, non è necessariamente vero che c → a.
L'assegnazione di un timestamp a un thread corrisponde a posizionare un token del thread su un nodo del grafo.
Le seguenti operazioni possono essere eseguite sui token dei thread:
- Scan: semplice localizzazione dei token degli altri thread.
- Label: muove il proprio token su un nodo a tale che ci sia un arco da a a tutti gli altri nodi con un token di un thread.
Dati due thread "Red" e "Blue", sia "Red" il primo a posizionare il suo token.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo
