Differenza tra il numero di consenso N e il numero di consenso infinito

Question

In Book Programmazione concorrente: Algoritmi, Principi e Fondazioni di Michel Raynal, nella Sezione 16.5.1, Teorema 75 dice

.

Confronta e gli oggetti Swap hanno un numero di consenso infinito.

E nella sezione 16.5.2, Lemma 40 dice

.

Il tipo di oggetto Mem-to-Mem-swap ha il numero di consenso n in un sistema di n processi.

Allora, nella Sezione 16.1, l'autore mette in tabella Confronta e swap e uomini-a-mem-swap come oggetti con numero di consenso infinito.

Allora, qual è la differenza tra oggetti con il numero di consenso n e oggetti con il numero di consenso infinito?

Answer 1

Il numero di consenso di un oggetto è il numero massimo di processi simultanei che è possibile sincronizzare con uno di questi oggetti in modo da attenuazione (non andrò in ciò che significa Aspettenti qui). Ad esempio, un registro con le operazioni di lettura e di scrittura solo non aiuta affatto con la sincronizzazione di attesa, quindi ha il numero di consenso 1. Un registro con un'operazione di test-e-set può essere utilizzata per sincronizzare due processi in attesa -In modo, ma non tre o più, quindi il numero di consenso di test-e-set è 2.

$ N $ -Registrazione Assegnazione, in cui un processo può scrivere atomicamente su più registri, consente fino a $ 2N- 2 $ Processi per sincronizzare Aggiorna se ci sono $ N $ registri. Più processi richiedono più registri. Pertanto il numero di consenso di un objet composto da $ N $ registri che possono essere assegnati atomicamente è $ 2N-2 $ .

Un singolo registro con un'operazione di confronto e swap è sufficiente per sincronizzare qualsiasi numero di processi in attesa. Pertanto il numero di consenso di confronto-e-swap è infinito.

Lemma 40 afferma che un oggetto Mem-and-Swap consente la sincronizzazione senza attesa di tutti i processi in un sistema di $ N $ processi concorrenti, per qualsiasi Numero $ N $ . Ciò significa che per qualsiasi numero $ N $ , il numero di consenso di mem-e-swap è almeno $ N $ < / span>. (Affermando che il numero di consenso è $ N $ in un sistema di $ N $ I processi è un po 'di disattivazione del termine poiché la definizione del numero di consenso non dipende in realtà dal numero totale di processi.) Dal momento che il numero di consenso di Mem-and-swap è almeno $ N $ per qualsiasi classe $ N $ , è infinito.

Se preferisci un'altra fonte del libro di Raynal, puoi leggere l'originale Carta di Maurice Herlihy .