Lettura 17: Concorrenza

#### Software in 6.005

#### Obiettivi + Messaggio che passa & memoria condivisa + Processi & thread + Slicing del tempo + Condizioni di gara # # Concurrency * Concurrency * significa che più calcoli stanno accadendo allo stesso tempo. La concorrenza è ovunque in programmazione moderna, che ci piaccia o no:+ Più computer in una rete+ Più applicazioni in esecuzione su un computer+ Più processori in un computer (oggi, spesso più core di processore su un singolo chip), infatti, la concorrenza è essenziale nella programmazione moderna:+ siti Web deve gestire più utenti contemporaneamente.+ Le app mobili devono eseguire alcune delle loro elaborazioni sui server (“nel cloud”).+ Le interfacce utente grafiche richiedono quasi sempre un lavoro in background che non interrompe l’utente. Ad esempio, Eclipse compila il codice Java mentre lo stai ancora modificando.Essere in grado di programmare con la concorrenza sarà ancora importante in futuro. Le velocità di clock del processore non aumentano più. Invece, stiamo ottenendo più core con ogni nuova generazione di chip. Quindi in futuro, per far funzionare un calcolo più velocemente, dovremo dividere un calcolo in pezzi simultanei.## Due modelli per la programmazione simultaneaci sono due modelli comuni per la programmazione concorrente: *memoria condivisa* e *passaggio messaggi*.

**Memoria condivisa.** Nel modello di memoria condivisa della concorrenza, i moduli concorrenti interagiscono leggendo e scrivendo oggetti condivisi in memoria. Altri esempi del modello di memoria condivisa: + A e B potrebbero essere due processori (o core del processore) nello stesso computer, condividendo la stessa memoria fisica.+ A e B potrebbero essere due programmi in esecuzione sullo stesso computer, la condivisione di un file system comune con i file che possono leggere e scrivere.+ A e B potrebbero essere due thread nello stesso programma Java (spiegheremo cosa è un thread sotto), condividendo gli stessi oggetti Java.

**Passaggio messaggio.** Nel modello di passaggio dei messaggi, i moduli simultanei interagiscono inviando messaggi l’uno all’altro attraverso un canale di comunicazione. I moduli inviano messaggi e i messaggi in arrivo a ciascun modulo vengono messi in coda per la gestione. Gli esempi includono:+ A e B potrebbero essere due computer in una rete, che comunicano tramite connessioni di rete.+ A e B potrebbero essere un browser Web e un server Web A A apre una connessione a B, chiede una pagina Web e B invia i dati della pagina Web ad A.+ A e B potrebbero essere un client e un server di messaggistica istantanea.+ A e B potrebbero essere due programmi in esecuzione sullo stesso computer il cui input e output sono stati collegati da una pipe, come `ls | grep` digitato in un prompt dei comandi.## Processes, Threads, Time-slicingThe message-passing and shared-memory models are about how concurrent modules communicate. I moduli concorrenti stessi sono disponibili in due tipi diversi: processi e thread.**Processo**. Un processo è un’istanza di un programma in esecuzione che è *isolato * da altri processi sulla stessa macchina. In particolare, ha una propria sezione privata della memoria della macchina.L’astrazione del processo è un * computer virtuale*. Fa sentire il programma come se avesse l’intera macchina per sé — come se fosse stato creato un nuovo computer, con nuova memoria, solo per eseguire quel programma.Proprio come i computer collegati in rete, i processi normalmente non condividono memoria tra di loro. Un processo non può accedere alla memoria o agli oggetti di un altro processo. La condivisione della memoria tra i processi è * possibile * sulla maggior parte dei sistemi operativi, ma richiede uno sforzo particolare. Al contrario, un nuovo processo è automaticamente pronto per il passaggio dei messaggi, perché viene creato con flussi di output standard input &, che sono il `Sistema.fuori` e `System.in ‘ flussi che hai usato in Java.**Thread**. Un thread è un luogo di controllo all’interno di un programma in esecuzione. Pensalo come un posto nel programma che viene eseguito, oltre alla pila di chiamate al metodo che hanno portato a quel posto in cui sarà necessario tornare.Proprio come un processo rappresenta un computer virtuale, l’astrazione del thread rappresenta un processore virtuale**. Creare un nuovo thread simula la creazione di un nuovo processore all’interno del computer virtuale rappresentato dal processo. Questo nuovo processore virtuale esegue lo stesso programma e condivide la stessa memoria di altri thread in corso.I thread sono automaticamente pronti per la memoria condivisa, poiché i thread condividono tutta la memoria nel processo. Ha bisogno di uno sforzo speciale per ottenere la memoria “thread-local” che è privata di un singolo thread. È inoltre necessario impostare il passaggio dei messaggi in modo esplicito, creando e utilizzando le strutture di dati della coda. Parleremo di come farlo in una lettura futura.

Come posso avere molti thread simultanei con solo uno o due processori nel mio computer? Quando ci sono più thread rispetto ai processori, la concorrenza viene simulata da **time slicing**, il che significa che il processore passa da un thread all’altro. La figura a destra mostra come tre thread T1, T2 e T3 potrebbero essere tagliati in tempo su una macchina che ha solo due processori effettivi. Nella figura, il tempo procede verso il basso, quindi in un primo momento un processore esegue il thread T1 e l’altro esegue il thread T2, quindi il secondo processore passa a eseguire il thread T3. Thread T2 si ferma semplicemente, fino alla sua prossima volta slice sullo stesso processore o su un altro processore.Sulla maggior parte dei sistemi, il time slicing avviene in modo imprevedibile e non deterministico, il che significa che un thread può essere messo in pausa o ripreso in qualsiasi momento.

mitx:c613ec53e92840a4a506f3062c994673 Elabora & Thread # # Shared Memory exampleleggiamo un esempio di un sistema di memoria condivisa. Il punto di questo esempio è mostrare che la programmazione concorrente è difficile, perché può avere bug sottili.

Immagina che una banca abbia bancomat che utilizzano un modello di memoria condivisa, in modo che tutti i bancomat possano leggere e scrivere gli stessi oggetti account in memoria.Per illustrare che cosa può andare male, cerchiamo di semplificare la banca fino a un singolo account, con un saldo conservato in `equilibrio` variabile, e due operazioni di `deposito` e di `ritirare` che sufficiente aggiungere o rimuovere un dollaro: ` ” java// supponiamo che tutti i bancomat condividere una singola banca accountprivate static int balance = 0;private static void deposit() { saldo = saldo + 1;}private static void withdraw() { saldo = saldo – 1;}`I clienti di utilizzare il bancomat per effettuare operazioni come questa:“javadeposit(); // metto un dollaro inwithdraw(); // take it back out` ‘ In questo semplice esempio, ogni transazione è solo un deposito di un dollaro seguito da un prelievo di un dollaro, quindi dovrebbe lasciare invariato il saldo nel conto. Durante il giorno, ogni bancomat nella nostra rete sta elaborando una sequenza di transazioni di deposito/prelievo.“java// ogni ATM fa una serie di transazioni che// modificano il saldo, ma lo lasciano invariato afterwardprivate static void cashMachine() { for (int i = 0; i < TRANSACTIONS_PER_MACHINE; ++i) { deposit (); / / metti un dollaro in withdraw(); // take it back out }}“Quindi, alla fine della giornata, indipendentemente da quanti bancomat erano in esecuzione, o quante transazioni abbiamo elaborato, dovremmo aspettarci che il saldo del conto sia ancora 0.Ma se eseguiamo questo codice, scopriamo spesso che il saldo alla fine della giornata è *non* 0. Se più di una chiamata “cashMachine ()” è in esecuzione contemporaneamente, ad esempio su processori separati nello stesso computer, il “saldo” potrebbe non essere zero alla fine della giornata. Perché no?## Interleavingqui ‘ s una cosa che può accadere . Supponiamo che due bancomat, A e B, stiano entrambi lavorando su un deposito allo stesso tempo. Ecco come il passaggio deposit() in genere si suddivide in istruzioni del processore di basso livello` “‘ get balance (balance=0) add 1 write back the result (balance=1)“Quando A e B sono in esecuzione contemporaneamente, queste istruzioni di basso livello si interfacciano tra loro (alcune potrebbero anche essere simultanee in un certo senso, ma per ora preoccupiamoci solo dell’interleaving):”‘A get balance (balance=0) A add 1 A write back the result (balance=1) B get balance (balance=1) B add 1 B write back the result (balance=2)“Questo interleaving va bene end finiamo con balance 2, quindi sia A che B inseriscono con successo un dollaro. Ma cosa succede se l’interleaving è simile a questo:“A get balance (balance=0) B get balance (balance=0)A add 1 B add 1 A write back the result (balance=1) B write back the result (balance=1)“Il saldo è ora 1 dollar Il dollaro di A è stato perso! A e B leggono entrambi il saldo allo stesso tempo, calcolano i saldi finali separati e poi corrono per archiviare il nuovo saldo which che non tiene conto del deposito dell’altro.## Race conditionquesto è un esempio di * * race condition**. Una condizione di gara significa che la correttezza del programma (la soddisfazione delle postcondizioni e degli invarianti) dipende dalla tempistica relativa degli eventi nei calcoli simultanei A e B. Quando ciò accade, diciamo ” A è in una gara con B.”Alcuni interleaving di eventi possono essere OK, nel senso che sono coerenti con ciò che un singolo processo non corrente produrrebbe, ma altri interleaving producono risposte sbagliate violating violando postcondizioni o invarianti.## Modificare il codice non aiuteràtutte queste versioni del codice del conto bancario presentano la stessa condizione di gara: “‘java / / versione 1private static void deposit () {balance = balance + 1;} private static void withdraw () { balance = balance-1;} “”” java / / versione 2private static void deposit () { balance + = 1;} private static void withdraw () { balance – = 1;} “””java / / versione 3private static void deposit () {++balance;} private static void withdraw () {balance balance;}“Non si può dire solo guardando il codice Java come il processore sta per eseguirlo. Non puoi dire quali saranno le operazioni indivisibili, le operazioni atomiche. Non è atomico solo perché è una linea di Java. Non tocca l’equilibrio solo una volta solo perché l’identificatore di equilibrio si verifica solo una volta nella riga. Il compilatore Java, e in effetti il processore stesso, non assume impegni su quali operazioni di basso livello genererà dal codice. In effetti, un tipico compilatore Java moderno produce esattamente lo stesso codice per tutte e tre queste versioni!La lezione chiave è che non si può dire guardando un’espressione se sarà al sicuro dalle condizioni di gara.

## Riordinamentoè anche peggio di così, in effetti. La condizione di gara sul saldo del conto bancario può essere spiegata in termini di diversi interleavings di operazioni sequenziali su diversi processori. Ma in realtà, quando si utilizzano più variabili e più processori, non si può nemmeno contare sulle modifiche a quelle variabili che appaiono nello stesso ordine.Ecco un esempio` “‘ javaprivate boolean ready = false; private int answer = 0; / / computeAnswer viene eseguito in un threadprivate void computeAnswer () {answer = 42; ready = true;}// useAnswer viene eseguito in un threadprivate void diverso useAnswer () {while (!pronto) {Filo.yield ();} if (answer = = 0) lancia la nuova RuntimeException (“la risposta non era pronta!`);} “`Abbiamo due metodi che vengono eseguiti in thread diversi. ‘computeAnswer’ esegue un lungo calcolo, arrivando finalmente alla risposta 42, che inserisce nella variabile di risposta. Quindi imposta la variabile` ready ‘ su true, per segnalare al metodo in esecuzione nell’altro thread, `useAnswer`, che la risposta è pronta per l’uso. Guardando il codice ` ‘answer’ è impostato prima che ready sia impostato, quindi una volta che ‘useAnswer’ vede ‘ready’ come true, allora sembra ragionevole che possa presumere che la` answer ‘ sarà 42, giusto? Non è così.Il problema è che i compilatori e i processori moderni fanno molte cose per rendere il codice veloce. Una di queste cose è fare copie temporanee di variabili come answer e ready in storage più veloce (registri o cache su un processore), e lavorare con loro temporaneamente prima di riporli nella loro posizione ufficiale in memoria. Lo storeback può avvenire in un ordine diverso rispetto alle variabili manipolate nel codice. Ecco cosa potrebbe accadere sotto le coperte (ma espresso in sintassi Java per renderlo chiaro). Il processore sta effettivamente creando due variabili temporanee, ‘tmpr’ e ‘tmpa’, per manipolare i campi pronti e rispondere:”‘javaprivate void computeAnswer () {boolean tmpr = ready; int tmpa = answer; tmpa = 42; tmpr = true; ready = tmpr; / / < what cosa succede se useAnswer() interleaves qui? // ready è impostato, ma la risposta non lo è. answer = tmpa;} “‘ mitx: 2bf4beb7ffd5437bbbb9c782bb99b54e Race Conditions # # Message Passing Example

Ora diamo un’occhiata all’approccio di passaggio dei messaggi al nostro esempio di conto bancario.Ora non solo sono i moduli bancomat, ma i conti sono moduli, troppo. I moduli interagiscono inviando messaggi l’uno all’altro. Le richieste in arrivo vengono inserite in una coda da gestire una alla volta. Il mittente non smette di funzionare in attesa di una risposta alla sua richiesta. Gestisce più richieste dalla propria coda. La risposta alla sua richiesta alla fine ritorna come un altro messaggio.Sfortunatamente, il passaggio dei messaggi non elimina la possibilità di condizioni di gara. Supponiamo che ogni account supporti le operazioni “get-balance” e “withdraw”, con i messaggi corrispondenti. Due utenti, al bancomat A e B, stanno entrambi cercando di prelevare un dollaro dallo stesso conto. Essi controllare il saldo prima per essere sicuri di non ritirare più di un account detiene, perché scoperti di trigger grande banca sanzioni:“get-balanceif equilibrio >= 1 quindi ritirare 1` ” Il problema è di nuovo l’interleaving, ma questa volta l’interleaving del ** messaggi inviati al conto in banca, piuttosto che l’ *istruzioni* eseguito da A e B. Se il conto inizia con un dollaro in esso, quindi cosa sovrapposizione di messaggi di ingannare A e B a pensare che sia possibile ritirare un dollaro, quindi overdrawing l’account?Una lezione qui è che è necessario scegliere con attenzione le operazioni di un modello di passaggio di messaggi. “ritirare-se-fondi sufficienti” sarebbe un’operazione migliore del semplice “ritirare”.## La concorrenza è difficile da testare e DebugSe non ti abbiamo convinto che la concorrenza è difficile, ecco il peggio. È molto difficile scoprire le condizioni di gara usando i test. E anche una volta che un test ha trovato un bug, potrebbe essere molto difficile localizzarlo nella parte del programma che lo causa.I bug di concorrenza mostrano una riproducibilità molto scarsa. È difficile farli accadere allo stesso modo due volte. L’interleaving di istruzioni o messaggi dipende dalla tempistica relativa degli eventi che sono fortemente influenzati dall’ambiente. I ritardi possono essere causati da altri programmi in esecuzione, altro traffico di rete, decisioni di pianificazione del sistema operativo, variazioni della velocità di clock del processore, ecc. Ogni volta che si esegue un programma contenente una condizione di gara, è possibile ottenere un comportamento diverso. Questi tipi di bug sono **heisenbugs**, che sono non deterministici e difficili da riprodurre, al contrario di un “bohrbug”, che si presenta ripetutamente ogni volta che lo si guarda. Quasi tutti i bug nella programmazione sequenziale sono bohrbugs.Un heisenbug può anche scomparire quando si tenta di guardarlo con `println` o `debugger`! Il motivo è che la stampa e il debug sono molto più lenti di altre operazioni, spesso 100-1000x più lenti, che cambiano drasticamente i tempi delle operazioni e l’interleaving. Quindi inserendo una semplice istruzione di stampa in cashMachine ()` “‘ javaprivate static void cashMachine () {for (int i = 0; i < TRANSACTIONS_PER_MACHINE; ++i) {deposit (); / / metti un dollaro in withdraw (); / / riprendilo Sistema.fuori.println (balance); // fa sparire il bug! }}“`…e improvvisamente il saldo è sempre 0, come desiderato, e il bug sembra scomparire. Ma è solo mascherato, non veramente fisso. Un cambiamento nei tempi da qualche altra parte nel programma potrebbe improvvisamente far tornare il bug.La concorrenza è difficile da ottenere. Parte del punto di questa lettura è quello di spaventare un po’. Nel corso delle prossime letture, vedremo modi di principio per progettare programmi concorrenti in modo che siano più sicuri da questi tipi di bug.mitx: 704b9c4db3c6487c9f1549956af8bfc8 Test di concorrenza # # Sintesi + Concorrenza: più calcoli in esecuzione contemporaneamente + Memoria condivisa & paradigmi di passaggio dei messaggi + Processi & thread + Processo è come un computer virtuale; thread è come un processore virtuale + Condizioni di gara + Quando la correttezza del risultato (postcondizioni e invarianti) dipende dalla tempistica relativa degli eventiqueste idee si connettono alle nostre tre proprietà chiave del buon software per lo più in modi cattivi. La concorrenza è necessaria ma causa seri problemi di correttezza. Lavoreremo per risolvere questi problemi nelle prossime letture.+ * * Al sicuro da bug.** I bug di concorrenza sono alcuni dei bug più difficili da trovare e correggere e richiedono un’attenta progettazione da evitare.+ * * Facile da capire.** Prevedere come il codice concorrente potrebbe interleave con altro codice concorrente è molto difficile per i programmatori di fare. È meglio progettare in modo tale che i programmatori non debbano pensarci. + * * Pronto per il cambiamento.** Non particolarmente rilevante qui.