Blocca scambio di elementi dell'array libero

Question

In ambiente multi-thread, al fine di consentire lo scambio di elementi dell'array thread-safe, eseguiremo il blocco sincronizzato.

// a is char array.
synchronized(a) {
    char tmp = a[1];
    a[1] = a[0];
    a[0] = tmp;
}

È possibile che possiamo utilizzare la seguente API nella situazione precedente, in modo da poter avere uno scambio di elementi dell'array senza blocco? Se sì, come?

http://java.sun.com/j2se/1.5.0/docs/api/java/util/concurrent/atomic/AtomicReferenceFieldUpdater.html#compareAndSet%28T,%20V,%20V % 29

Answer 1

Indipendentemente dall'API utilizzata, non sarà possibile ottenere lo scambio di elementi dell'array sia thread-safe che lock-free in Java.

Lo scambio di elementi richiede più operazioni di lettura e aggiornamento che devono essere eseguite atomicamente. Per simulare l'atomicità è necessario un lucchetto.

EDIT:

Un'alternativa all'algoritmo senza blocco potrebbe essere il micro-blocco: invece di bloccare l'intero array è possibile bloccare solo gli elementi che vengono scambiati.

Il valore di questo approccio è completamente discutibile. Ciò significa che se l'algoritmo che richiede lo scambio di elementi può garantire che thread diversi funzionino su parti diverse dell'array, non è necessaria alcuna sincronizzazione.

Nel caso contrario, quando thread diversi possono effettivamente tentare di scambiare elementi sovrapposti, l'ordine di esecuzione del thread sarà importante. Ad esempio, se un thread tenta di scambiare gli elementi 0 e 1 dell'array e l'altro tenta contemporaneamente di scambiare 1 e 2, il risultato dipenderà interamente dall'ordine di esecuzione, per {{a "," b "," c iniziale '} puoi finire con {' b ',' c ',' a '} o {' c ',' a ',' b '}. Quindi avresti bisogno di una sincronizzazione più sofisticata.

Ecco una classe veloce e sporca per gli array di caratteri che implementa il microblocco:

import java.util.concurrent.atomic.AtomicIntegerArray;

class SyncCharArray {

    final private char array [];
    final private AtomicIntegerArray locktable;

    SyncCharArray (char array[])
    {
      this.array = array;

      // create a lock table the size of the array
      // to track currently locked elements 
      this.locktable = new AtomicIntegerArray(array.length);
      for (int i = 0;i<array.length;i++) unlock(i);

    }

    void swap (int idx1, int idx2)
    {
      // return if the same element
      if (idx1==idx2) return;

      // lock element with the smaller index first to avoid possible deadlock
      lock(Math.min(idx1,idx2));
      lock(Math.max(idx1,idx2));

      char tmp = array[idx1];
      array [idx1] = array[idx2];
      unlock(idx1);
      array[idx2] = tmp;
      unlock(idx2);

    }

    private void lock (int idx)
    {
      // if required element is locked when wait ...
      while (!locktable.compareAndSet(idx,0,1)) Thread.yield();
    }

    private void unlock (int idx)
    {
      locktable.set(idx,0);
    }

}

Dovresti creare SyncCharArray e passarlo a tutti i thread che richiedono lo scambio:

char array [] = {'a','b','c','d','e','f'};
SyncCharArray sca = new SyncCharArray(array);

 // then pass sca to any threads that require swapping
 // then within a thread

sca.swap(15,3);

Spero che abbia un senso.

UPDATE:

Alcuni test hanno dimostrato che, a meno che non si abbia un gran numero di thread che accedono contemporaneamente all'array (oltre 100 su hardware run-of-the-mill), una semplice sincronizzazione (array) {} funziona molto più velocemente rispetto alla sincronizzazione elaborata.

Answer 2

  // lock-free swap array[i] and array[j] (assumes array contains not null elements only)
  static <T> void swap(AtomicReferenceArray<T> array, int i, int j) {
    while (true) {
      T ai = array.getAndSet(i, null);
      if (ai == null) continue;
      T aj = array.getAndSet(j, null);
      if (aj == null) {
        array.set(i, ai);
        continue;
      }
      array.set(i, aj);
      array.set(j, ai);
      break;
    }
  }

Answer 3

Il più vicino che otterrai è java.util.concurrent.atomic.AtomicReferenceArray , che offre operazioni basate su CAS come boolean compareAndSet (int i, E prevedono, E aggiorna) . Non ha un'operazione swap (int pos1, int pos2) , quindi dovrai emularla con due chiamate compareAndSet .

Answer 4

" La principale minaccia alla scalabilità in applicazioni simultanee è il blocco esclusivo delle risorse. " - Concorrenza Java in pratica.

Penso che tu abbia bisogno di un lucchetto, ma come altri dicono che il lucchetto può essere più granulare di quanto non sia attualmente.

Puoi usare lo striping dei blocchi come java.util.concurrent.ConcurrentHashMap.

Answer 5

L'API che hai citato, come già affermato da altri, può essere utilizzata solo per impostare i valori di un singolo oggetto, non di un array. Nemmeno per due oggetti contemporaneamente, quindi non avresti comunque uno scambio sicuro.

La soluzione dipende dalla tua situazione specifica. L'array può essere sostituito da un'altra struttura di dati? Sta cambiando anche le dimensioni contemporaneamente?

Se è necessario utilizzare un array, è possibile modificarlo per contenere oggetti aggiornabili (non tipi primitivi né un Char ) e sincronizzarsi su entrambi gli swap. La struttura dei dati S in questo modo funzionerebbe:

public class CharValue {
    public char c;
}

CharValue[] a = new CharValue[N];

Ricorda di utilizzare un ordine di sincronizzazione deterministica per non avere deadlock ( http: // it. wikipedia.org/wiki/Deadlock#Circular_wait_prevention )! Puoi semplicemente seguire l'ordinamento dell'indice per evitarlo.

Se gli elementi devono essere aggiunti o rimossi contemporaneamente dalla raccolta, è possibile utilizzare una Mappa , sincronizzare gli swap sugli Map.Entry e utilizzare un sincronizzato Implementazione della mappa. Un semplice List non lo farebbe perché non ci sono strutture isolate per conservare i valori (o non hai accesso ad essi).

Answer 6

Non credo che AtomicReferenceFieldUpdater sia pensato per l'accesso all'array e, anche se lo fosse, fornisce solo garanzie atomiche su un riferimento alla volta. AFAIK, tutte le classi in java.util.concurrent.atomic forniscono l'accesso atomico a un riferimento alla volta. Per modificare due o più riferimenti come un'operazione atomica, è necessario utilizzare un tipo di blocco.