Matriz Lock Free Elemento Permuta

Question

bloqueio No ambiente multi-thread, a fim de ter o segmento de seguros de elemento de matriz troca, vamos realizar sincronizado.

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

É possível que nós podemos fazer uso do seguinte API na situação acima, para que possamos ter um bloqueio livre elemento de matriz troca? Se sim, como?

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

Answer 1

Independentemente de API usado você não será capaz de alcançar tanto thread-safe e sem bloqueio do elemento da matriz de troca em Java.

O elemento de troca requer várias operações de leitura e de atualização que precisam ser executadas atomicamente. Para simular a atomicidade você precisa de um bloqueio.

EDIT:

Uma alternativa para o algoritmo livre de bloqueio pode ser micro-bloqueio: em vez de bloquear toda a matriz é possível bloquear apenas os elementos que estão sendo trocados.

O valor desta abordagem totalmente é questionável. Ou seja, se o algoritmo que requer elementos trocando pode garantir que diferentes tópicos estão indo para o trabalho em diferentes partes do array, então nenhuma sincronização necessário.

No caso oposto, quando diferentes segmentos podem realmente tentar trocar elementos sobrepostos enrosque ordem de execução importa. Por exemplo se um segmento tenta elementos de troca 0 e 1 da matriz e as outras tentativas simultaneamente a permuta 1 e 2, em seguida, o resultado dependerá inteiramente da ordem de execução, para a { 'a', 'b', «c inicial '} você pode acabar tanto com {' b', 'c', 'a'} ou { 'c', 'a', 'b'}. Daí você requerem uma sincronização mais sofisticada.

Aqui está uma classe rápida e suja para arrays de caracteres que implementos micro bloqueio:

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);
    }

}

Você precisaria criar o SyncCharArray e, em seguida, passá-lo para os tópicos que exigem trocando:

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);

A esperança que faz algum sentido.

UPDATE:

Alguns testes demonstraram que a menos que você tem um grande número de segmentos acessando a matriz simulteniously (100+ em hardware run-of-the-mill) a sincronizar simples (array) {} funciona muito mais rápido do que a sincronização elaborado.

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

O mais próximo que você vai conseguir é java.util.concurrent.atomic.AtomicReferenceArray , que oferece operações baseadas no CAS como boolean compareAndSet(int i, E expect, E update). Ele não tem uma operação swap(int pos1, int pos2) embora assim que você vai ter que imitá-lo com duas chamadas compareAndSet.

Answer 4

"A principal ameaça à escalabilidade em aplicações simultâneas é o bloqueio de recurso exclusivo." -. Java Concurrency in Practice

Eu acho que você precisa de um bloqueio, mas como os outros mencionar que trava pode ser mais granular do que é actualmente.

Você pode usar o bloqueio de striping como java.util.concurrent.ConcurrentHashMap.

Answer 5

A API que você mencionou, como já foi dito por outros, só pode ser usado para definir valores de um único não objeto, uma matriz. Nem mesmo para dois objetos ao mesmo tempo, para que você não teria uma troca segura de qualquer maneira.

A solução depende de sua situação específica. a matriz pode ser substituída por outra estrutura de dados? Está também mudando de tamanho ao mesmo tempo?

Se você deve usar uma matriz, poderia ser alterado para segurar objetos atualizáveis ??(tipos não primitivos nem um Char), e sincronizar sobre ambos sendo trocados. estrutura de dados S, como isso iria funcionar:

public class CharValue {
    public char c;
}

CharValue[] a = new CharValue[N];

Lembre-se de usar uma ordem de sincronização determinista por não ter uma impasses ( http: // en. wikipedia.org/wiki/Deadlock#Circular_wait_prevention )! Você poderia simplesmente seguir o índice de pedidos para evitá-lo.

Se os itens também devem ser adicionados ou removidos simultaneamente a partir da coleção, você poderia usar um Map vez, swaps Sincronizar no Map.Entry'es e usar uma implementação Mapa sincronizado. A List simples não faria isso porque existem estruturas não isolados para reter os valores (ou você não tem acesso a eles).

Answer 6

Eu não acho que o AtomicReferenceFieldUpdater é para acesso à matriz, e mesmo que fosse, ela só fornece garantias atômicas em uma referência de cada vez. AFAIK, todas as classes java.util.concurrent.atomic só fornecem acesso atômica para uma referência de cada vez. A fim de mudar dois ou mais referências como uma operação atômica, você deve usar algum tipo de bloqueio.