Concorrenza configurabile in Java o in qualsiasi altro linguaggio di programmazione

9

Mentre stavo leggendo un documento di ricerca sulla concorrenza denominato Software e la Rivoluzione della concorrenza ( versione html ). Mi sono imbattuto in seguenti righe:

Unfortunately, although locks work, they pose serious problems for modern software development. A fundamental problem with locks is that they are not composable. You can’t take two correct lock-based pieces of code, combine them, and know that the result is still correct. Modern software development relies on the ability to compose libraries into larger programs, and so it is a serious difficulty that we cannot build on lock-based components without examining their implementations.

  1. Stavo pensando, come Java garantisce la concorrenza componibile o persino c'è un modo per produrre questi scenari.

  2. E come possiamo sincronizzare i dati in una o più librerie? Un programmatore può farlo dal suo programma o è in grado di sincronizzare la libreria.

  3. Se non è Java, esiste un'altra lingua che usa la concorrenza basata sul blocco e garantisce la concorrenza componibile?

Anche qui viene preso dallo stesso tipo di carta:

There are at least three major problems with synchronized methods. First, they are not appropriate for types whose methods call virtual functions on other objects (e.g., Java’s Vector and .NET’s SyncHashTable), because calling into third-party code while holding a lock opens the possibility of deadlock. Second, synchronized methods can perform too much locking, by acquiring and releasing locks on all object instances, even those never shared across threads (typically the majority). Third, synchronized methods can also perform too little locking, by not preserving atomicity when a program calls multiple methods on an object or on different objects. As a simple example of the latter, consider a banking transfer: account1.Credit(amount); account2.Debit(amount)...

Nota: il documento è stato pubblicato nel settembre 2005

    
posta gnat 26.03.2016 - 11:50
fonte

5 risposte

1

Prima di tutto ringrazio tutti i membri che hanno risposto a questa domanda, in particolare Robert Harvey, la cui risposta sembra molto vicina alla mia.

Ho fatto ricerche sui concetti di concorrenza per due anni e, secondo le mie scoperte, nessun linguaggio garantisce che i suoi costrutti di concorrenza siano componibili. Un codice in esecuzione perfettamente funzionante che utilizza strutture dati immutabili e STM può anche produrre risultati inaspettati perché sotto la cappa, STM utilizza i blocchi. STM è molto utile per le operazioni atomiche, ma se parliamo di componibilità dei contrasti di concorrenza tra i moduli, c'è una (molto piccola) possibilità che STM non funzioni come previsto.

Tuttavia, possiamo ridurre al minimo l'incertezza utilizzando il seguente metodo (tecniche / metodi / costrutti):

  1. Evitare i blocchi e la sincronizzazione
  2. Utilizzo di STM
  3. Uso di strutture dati persistenti (immutabili)
  4. Come evitare lo stato di condivisione
  5. Funzioni pure
  6. Stile di programmazione asincrono
  7. Evita il cambio di contesto frequente
  8. Il paradigma multi-threading e la natura del suo ambiente giocano un ruolo importante

Perhaps the most fundamental objection [...] is that lock-based programs do not compose: correct fragments may fail when combined. —Tim Harris et al., "Composable Memory Transactions", Section 2: Background, pg.2

Aggiorna

Grazie a Jules, sono corretto. STM utilizza varie implementazioni e la maggior parte di esse è priva di blocchi. Ma io continuo a credere che STM sia una buona soluzione qui, ma non quella perfetta, e ha degli svantaggi:

Each read (or write) of a memory location from inside a transaction is performed by a call to an STM routine for reading (or writing) data. With sequential code, these accesses are performed by a single CPU instruction. STM read and write routines are significantly more expensive than corresponding CPU instructions as they, typically, have to maintain bookkeeping data about every access. Most STMs check for conflicts with other concurrent transactions, log the access, and in case of a write, log the current (or old) value of the data, in addition to reading or writing the accessed memory location. Some of these operations use expensive synchronization instructions and access shared metadata, which further increases their costs. All of this reduces single-threaded performance when compared to sequential code. - Why STM can be more than a research toy - page 1

Vedi anche questi documenti:

Questi documenti hanno pochi anni. Le cose potrebbero essere cambiate / migliorate ma non tutte.

    
risposta data 30.05.2016 - 10:22
fonte
7

Non è la lingua Java. È la natura dei blocchi (mutex).

Esistono modi migliori per migliorare la concorrenza garantendo al tempo stesso la correttezza, modalità che sono indipendenti dalla lingua:

  1. Uso di oggetti immutabili, in modo da non aver bisogno di blocchi.
  2. Uso di promesse e stile di passaggio continuo
  3. Utilizzo di strutture dati senza blocco.
  4. Utilizzo della memoria transazionale del software per condividere lo stato in sicurezza.

Tutte queste tecniche consentono una maggiore concorrenza senza utilizzare i blocchi. Nessuno di loro dipende specificamente dal linguaggio Java.

    
risposta data 25.05.2016 - 17:25
fonte
3

I was thinking, how Java guarantee composable concurrency or even there is a way to produce this scenarios.

Come dice l'articolo, non è possibile garantire la componibilità quando si utilizzano i blocchi con metodi virtuali (o altri meccanismi simili, come il passaggio di funzioni come parametri). Se un pezzo di codice ha accesso a metodi virtuali che provengono da un altro pezzo di codice ed entrambi potenzialmente utilizzano blocchi, quindi per tranquillamente (cioè senza il rischio di un deadlock) comporre i due pezzi di codice, è necessario ispezionare il codice sorgente di entrambe le cose.

And how we can synchronize data in one or more libraries? Can a programmer do it from his program or it is up to library to synchronize things.

Generalmente, spetta al programmatore usare le librerie per fare la sincronizzazione. In questo modo, il programmatore sa dove sono tutte le serrature e può assicurarsi che non si bloccano.

If not Java then is there any other language which use lock based concurrency and guarantee composable concurrency?

Ancora una volta, il punto dell'articolo è che questo non è possibile.

    
risposta data 26.03.2016 - 13:26
fonte
1

I meccanismi di blocco di basso livello non sono intrinsecamente componibili. Questo è principalmente dovuto al fatto che le serrature raggiungono il mondo per influenzare la macchina che esegue le istruzioni.

Le librerie Java successive hanno aggiunto meccanismi di livello superiore e superiore per garantire il corretto funzionamento multithread. Lo fanno limitando l'uso di lock() e volatile a determinate circostanze ben note e controllabili. Ad esempio, un'implementazione simultanea della coda ha un comportamento molto localizzato e consente di ragionare sugli stati prima e dopo. L'utilizzo di meccanismi di livello superiore significa che è necessario leggere meno delle specifiche o del codice per farlo correttamente. Ma, e questo è un grande, ma devi ancora capire il modello di blocco di ogni sottosistema e come interagiscono tra loro. Inoltre, le modifiche in Java per la concorrenza dopo Java 5 sono quasi esclusivamente correlate alle librerie e non alla lingua.

Il problema principale con qualsiasi meccanismo di blocco è che influenza lo stato e opera nel dominio del tempo. Né l'uomo né i computer ragionano bene su uno stato o un tempo. È la capacità di ragionare su valore e struttura che ha permesso agli scienziati informatici di inventare monadi, la prima cosa che mi viene in mente per quanto riguarda la componibilità in una lingua.

Il più vicino che abbiamo è Comunicazione dei processi sequenziali . Ciò richiede comunque un meccanismo di alto livello, come le cassette postali e il passaggio dei messaggi. A mio modesto parere, CSP continua a non trattare adeguatamente con entrambi i sistemi di grandi dimensioni (l'obiettivo finale del software componibile) o il ragionamento basato sul tempo.

    
risposta data 26.03.2016 - 15:47
fonte
1

Ho sentito dire dai ricercatori di tutto rispetto che qualsiasi meccanismo di sincronizzazione utile può essere utilizzato per costruire un deadlock. La memoria transazionale (sia hardware che software) non è diversa. Ad esempio, considera questo approccio alla scrittura di una barriera di thread:

transaction {
    counter++;
}

while (true) {
    transaction {
        if (counter == num_threads)
            break;
    }
}

(Nota: l'esempio è tratto da un articolo di Yannis Smaragdakis a PACT 2009)

Se ignoriamo il fatto che questo non è un buon modo per sincronizzare un numero elevato di thread, sembra che sia corretto. Ma non è componibile. La decisione di inserire la logica in due transazioni è essenziale. Se dovessimo chiamarlo da un'altra transazione, in modo che tutto si appiattisse in un'unica transazione, probabilmente non avremmo mai completato.

Lo stesso vale per i canali che trasmettono messaggi: i cicli di comunicazione possono causare deadlock. La sincronizzazione ad-hoc con gli atomici C ++ può portare a deadlock. È possibile utilizzare RCU, blocchi di sequenza, blocchi di lettori / scrittori, variabili di condizione e semafori per creare deadlock.

Questo non vuol dire che transazioni o canali (o blocchi o RCU) siano cattivi. Piuttosto, è come dire che alcune cose non sembrano possibili. Probabilmente non sono possibili meccanismi di controllo della concorrenza scalabili, componibili e patologici.

Il modo migliore per evitare guai non è cercare un meccanismo con proiettili d'argento, ma utilizzare rigorosamente schemi validi. Nel mondo del calcolo parallelo, un buon punto di partenza è Programmazione parallela strutturata: Pattern per calcolo efficiente , di Arch Robison, James Reinders e Michael McCool. Per la programmazione simultanea, ci sono alcuni buoni schemi (vedi il commento di @ gardenhead), ma i programmatori C ++ e Java non sono propensi a usarli. Uno schema che più persone potrebbero iniziare ad usare i giusti modi è quello di sostituire le sincronizzazioni ad-hoc nei programmi con una coda multi-consumatore multi-produttore. E TM è decisamente meglio dei lock, in quanto innalza il livello di astrazione, in modo che i programmatori si concentrino su ciò che deve essere atomico , non come implementare un protocollo di blocco intelligente per garantire l'atomicità . Si spera che con l'hardware TM migliorato e che le lingue aggiungano più supporto TM, raggiungeremo un punto in cui TM sostituisce i blocchi nel caso comune.

    
risposta data 02.03.2017 - 03:42
fonte

Leggi altre domande sui tag