In che modo l'immutabilità elimina la necessità di blocchi quando due thread tentano di aggiornare lo stato condiviso?

Quindi penso che abbiamo bisogno di eliminare il termine "stato condiviso" dalla tua domanda, perché lo stato condiviso è quasi diametralmente opposto alla nozione di usare l'immutabilità per evitare il blocco.

Nel tuo esempio, hai praticamente detto che entrambi leggono il valore "N" ed entrambi creano un nuovo oggetto con un valore "N + 1".

La chiave è che non devi necessariamente salvare il valore "N + 1". Piuttosto, si salverebbero i valori "N" e "+1" all'interno di entrambi i thread 1 e 2. In altre parole, si salverebbe un riferimento al valore originale letto e alla modifica apportata ad esso.

Ora, lo "stato condiviso" dovrebbe invece essere un terzo thread che riconcilia i due (molto spesso questo terzo thread è il thread che ha originariamente creato i primi 2). Quando si riconciliano i due valori "N + 1", dovrebbe vedere che entrambi hanno iniziato con "N" ed entrambi hanno apportato una modifica a "+1". Il risultato finale è "N + 2".

È importante riconoscere che "N + 2", quando salvato, sarà anche un nuovo oggetto immutabile che non può essere modificato. È questa mancanza di questo "stato condiviso" che ti consente di evitare la necessità di blocchi.

What happens when two threads are trying to generate a new shared state?

Siamo chiari su quello che capisco che la tua domanda sia:

Hai una variabile mutabile di stato immutabile. Usiamo un int per semplicità:

int x = 42;

Quindi vuoi che due thread cerchino entrambi di incrementare x di 1.

Quindi puoi sincronizzarli. L'immutabilità fornisce poco valore qui.

Tutte le garanzie di immutabilità è che la variabile da cui stai leggendo non è in uno stato a metà strada quando viene letta. Poiché x è atomico, questo non ha molto senso. Qualsiasi lettura che fai otterrà l'intero valore.

Ma dal momento che hai mutato la variabile x , hai bisogno di sincronizzazione anche se il valore è immutabile. Ogni thread sta effettuando 2 operazioni atomiche:

y = read x;
write x with y+1;

Se entrambi i thread leggono prima di scrivere, allora entrambi i thread vedranno x , non x+1 . Quindi è necessario sincronizzare le cose

Ma cosa succede se x era una coppia?

Pair x = {2,4};

Quindi avere coppie immutabili garantirà che entrambi i valori vengano modificati allo stesso tempo.

Ma i thread hanno 4 operazioni atomiche con coppie mutabili

y = read x.x;
write x.x with y+1;
y = read x.y;
write x.y with y+1;

Ciascuno di essi può essere interrotto a seconda della concorrenza dei thread. Con le coppie immutabili , ti costringe a fare qualcosa del genere:

tmp = x;
y = new Pair(tmp.x+1, tmp.y+1);
x = y;

Hai ancora bisogno di sincronizzazione, perché hai la variabile mutevole x , ma la copia di riferimento su tmp è atomica. Poiché tmp è locale e sai che non viene modificato, it non ha bisogno di essere sincronizzato anche se stai facendo due operazioni diverse (per leggere tmp.x e tmp.y ).

Se pensi a come gli oggetti sono usati, la maggior parte del tempo, vuoi solo fare uno snapshot e fare alcune operazioni su di esso. Se non stavi aggiornando x sopra, non avresti bisogno di sincronizzazione. La copia in tmp avverrà automaticamente quando passi x in una funzione.

Ma dal momento che stavi chiedendo specificamente sull'aggiornamento di un riferimento mutabile, non ottieni i benefici dell'immutabilità. Se il riferimento era anche di sola lettura, non sarebbe necessario sincronizzare nulla poiché nulla può cambiare.

Aren't locks only needed if you're changing state?

C'è una sottigliezza qui. I blocchi sono necessari non solo se il thread corrente vuole modificare lo stato, ma se qualche altro thread potrebbe modificare lo stato. Ciò significa che puoi tranquillamente elidere l'oggetto solo se sai che nessun'altra parte del sistema lo modificherà. In altre parole, puoi solo rimuovere il blocco se l'oggetto è immutabile.

Dire che i blocchi non sono necessari per oggetti immutabili equivale a dire che i blocchi non sono necessari se si legge solo l'oggetto.

Ma in aggiunta, significa anche che ristrutturando il tuo codice per usare oggetti immutabili, possiamo sbarazzarci delle serrature. Consideriamo un caso semplice, implementato usando oggetti mutabili:

List list = new List();
void worker() {
   for(...) {
      synchronized(list) {
         list.add(...)
      }
   }
}

for (...) {
    start(worker)
}

for (...) {
   waitForWorkerToFinish();
}

Funzionerà, ma non molto bene, perché tutti i fili si batteranno sulla serratura. Ecco la soluzione immutabile:

List worker() {
   List list;
   for(...) {
      list.add(...)
   }
   return list;
}

for (...) {
    start(worker)
}

List list;
for (...) {
   list.addAll(waitForWorkerToFinish());
}

Si noti come non ci siano blocchi nel secondo esempio. (Beh, ci sono probabilmente blocchi che implementano start e waitForWorkerToFinish, ma il lavoratore non deve acquisire i blocchi). Perché si è liberato della serratura, sarà più veloce.

Il problema che hai è che stai guardando un esempio semplificato, che è così semplificato che hai completamente rimosso lo stato immutabile da esso e lasciato solo un singolo (sebbene atomico) valore mutabile. Questo non è un esempio realistico di un sistema immutabile.

Per ripristinare l'immutabilità, prendi in considerazione un esempio diverso. Due thread generano oggetti in qualche modo e li inseriscono in una struttura di mappa condivisa. La mappa è implementata come una mappa immutabile, per esempio. ha un'operazione di inserimento che restituisce una copia modificata della mappa, lasciando intatto l'originale. In questo caso, ciò che accade è che ogni thread, quando vuole aggiungere qualcosa, ha alcune opzioni diverse:

1. Potrebbe utilizzare un blocco, creare una copia aggiornata e sostituirla, quindi sbloccarla per altri thread. Questo è un approccio semplice ed è simile al modo in cui si eseguirà l'operazione con una mappa non immutabile, a parte che i thread del lettore non hanno bisogno di acquisire il blocco. Ma possiamo fare meglio:

2. Può afferrare il riferimento alla mappa corrente nell'archiviazione privata, creare una nuova mappa inserendovi, quindi eseguire un test atomico e impostare l'operazione per modificare il riferimento. Se il valore è cambiato mentre ha funzionato, è necessario ripetere l'operazione, ma poiché l'operazione è una funzione pura di stato immutabile, sappiamo che non ha avuto effetti collaterali, quindi può essere ripetuta tutte le volte necessarie per rendere aggiornare il lavoro. Se troppi thread stanno cercando di aggiornare lo stesso stato, può diventare un collo di bottiglia, quindi ricorrere al blocco se viene rilevato un eccesso di contesa è una buona idea. In molti scenari questo può funzionare meglio del blocco

3. Passare le operazioni da eseguire sullo stato mutabile a un terzo thread che può serializzarle in modo che i thread del generatore non debbano preoccuparsi della concorrenza. Questo offre il massimo throughput di tutte le opzioni, ma a spese delle risorse di sistema per mantenere il thread di serializzazione.

In un ambiente in cui possiamo impacchettare operazioni di mutazione pure come questa, puoi scrivere una libreria che gestisce tutto questo automaticamente, quindi devi solo passargli una funzione per l'aggiornamento del valore e decidere quale strategia adottare. Molte lingue hanno librerie che implementano "memoria transazionale del software" (che è il nome della tecnica numero 2 sopra) - alcune di esse eseguiranno anche il blocco e / o la serializzazione come e quando lo ritengono appropriato. Ma tutto ciò è reso possibile dal fatto che gli oggetti in uso sono immutabili e ci sono solo un piccolo numero di riferimenti mutabili.

La risposta è abbastanza semplice, con immutabilità, non si modifica stato, ma si creano nuovi stati.

Quindi hai 2 processi che ricevono input dallo stesso stato. Ciò che ottieni è 3 cose: prima lo stato originale e 2 nuovi stati che sono l'output dei 2 processi.

Ciò di cui hai bisogno ora è un terzo processo dedicato a mettere insieme questi stati dagli altri due processi e ottenere una risposta definitiva.

Non è così che funziona.

Se hai due thread che leggono e incrementano una variabile condivisa, non è immutabile. Quando contrassegni qualcosa di immutabile, stai dicendo a tutti (ea te stesso) che il valore non cambierà.

Se mi perdonerai per aver usato un esempio più complesso con un'opera pesante che vale parallelizzare e non solo operazioni atomiche a una variabile numerica, considera un loop di video game che deve applicare intelligenza artificiale, quindi fisica, quindi rendering in quell'ordine :

Quipersinolestrutturedidaticoncorrentimutevoliperlostatodelgiocononcipermettonodivalutareefficacementequestocomeunaverapipelinesenzasolobloccareestrozzatureefarsìchetuttosiaspettiancora,perchél'intelligenzaartificialedeveessereapplicatacompletamenteprimadellafisicaerenderelesuemodifichevisibiliprimachepossaessereapplicato,edentrambidevonoessereapplicaticompletamenteprimadieseguireilrenderingdiunacorniceperevitareartefatti.Potremmoessereingradodiutilizzarepiùthreadperaccelerareunodiquestinellaloroimplementazioneperevitarecheglialtridueattenderannotantoalungo,manonpossiamovalutarloinparallelo.

Macosasuccedeseilnostrostatodigiocodiventaimmutabile?Inquelcasononabbiamopiù"stato condiviso". Abbiamo una pipeline che si concentra sull'introduzione di un precedente stato di gioco e sull'output di un nuovo stato di gioco:

E mentre il primo passaggio richiederebbe che la fisica attenda il primo output di AI, e che il renderer attenda il primo output dalla fisica, in questa fase le parti della pipeline possono ora essere eseguite parallelamente a escogitare nuove si presenta come una vera pipeline parallela piuttosto che un esecutore seriale.

E questo può potenzialmente essere fatto in un modo privo di blocco con un throughput garantito dal sistema. Quindi questo è solo un esempio, ma è uno molto familiare per me, e uno in cui ne ho beneficiato un bel po '(con enormi miglioramenti ai frame rate, non solo in termini di frame rate più veloci ma con frame rate più consistenti e più uniformi) rendendo ogni fase del gasdotto puro (privo di effetti collaterali esterni osservabili), per il quale anche l'immutabilità ha contribuito a far rispettare.

Se non puoi fare a meno di fare in modo che il thread B dipenda dal thread A per finire e vedere il suo output modificato con quel tipo di dipendenza dall'ordine, puoi comunque trasformarlo in una vera pipeline in cui i due possono essere eseguiti parallelo (il thread B può essere focalizzato sull'avvio di un nuovo output per il thread C, forse, mentre il thread A sta lavorando simultaneamente a un nuovo output per il thread B), e tutto senza blocchi, a condizione che non stiamo mutando lo stato condiviso.

Detto questo, se lo stato è mutabile o no non è in realtà così rilevante per raggiungere questo tipo di concorrenza e sicurezza thread-free, e spero di non turbare i puristi funzionali là fuori dicendo che ( Sto arrivando a questo perseguendo la purezza in linguaggi imperativi come C e C ++, dove la praticità mi costringe a prendere una visione rilassata sull'immutabilità). Ci sono molti vantaggi in termini di immutabilità che aiutano a rafforzare la purezza e aiutano a semplificare il mantenimento degli invarianti, ma l'ultima cosa che aiuta qui è rendere lo stato non più condiviso tra i thread. L'immutabilità lo applica molto rigorosamente, ma puoi realizzare questo tipo di pipeline con un design di interfaccia mutabile per il tuo stato di gioco, purché non sia condiviso tra i thread, con ogni thread che immette una copia ed emette una nuova versione modificata.

How do you reconcile this problem so that the shared state becomes N + 2? Or am I missing something and that's not how it works?

Questo normalmente diventa una questione di operazioni atomiche. Ma immagino per un esempio più complesso e per quello che cerchi davvero, se un thread deve rendere l'output visibile all'altra concettualmente, allora non hai ancora bisogno di bloccare lo stato condiviso perché puoi applicare l'approccio della pipeline sopra menzionato . Il secondo thread dovrà inizialmente attendere (non è necessario bloccare necessariamente) sul primo thread per alimentare l'output iniziale, ma poi il primo thread può iniziare a sfornare nuovi output in parallelo subito dopo mentre il secondo thread sta eseguendo la sua cosa In questi casi, è possibile ottenere almeno una vera pipeline parallela evitando lo stato condiviso e favorendo la pura natura di I / O (al contrario di una natura mutante che causa effetti collaterali esterni) al design.

C'è un oggetto immutabile con un valore di N. Due thread ciascuno vogliono creare un oggetto immutabile con un valore di N + 1. Possono farlo senza alcun blocco bene.

Ciò che non hai menzionato è che molto probabilmente c'è un riferimento condiviso mutabile al primo oggetto, e due thread vogliono cambiare quel riferimento mutevole condiviso puntare a un nuovo oggetto immutabile con un valore più alto. Cambiare quel riferimento mutevole è dove avrai bisogno di un lucchetto. Se non si memorizza mai un riferimento ai nuovi oggetti in una posizione condivisa, non è necessario alcun blocco.