Nenhuma ConcurrentList <T> no .Net 4.0?

198

Fiquei emocionado ao ver o novo System.Collections.Concurrentespaço para nome no .Net 4.0, muito bom! Eu vi ConcurrentDictionary, ConcurrentQueue, ConcurrentStack, ConcurrentBage BlockingCollection.

Uma coisa que parece estar misteriosamente faltando é a ConcurrentList<T>. Eu tenho que escrever isso sozinho (ou tirá-lo da web :))?

Estou perdendo algo óbvio aqui?

Alan
fonte
7
ConcurrentBag <T> ( msdn.microsoft.com/pt-br/library/… )
Rodrigo Reis
4
@RodrigoReis, ConcurrentBag <T> é uma coleção não ordenada, enquanto Lista <T> é solicitada.
Adam Calvet Bohl
4
Como você poderia ter uma coleção ordenada em um ambiente multithread? Você nunca teria controle da sequência de elementos, por design.
Jeremy Holovacs
Em vez disso, use uma trava #
Erik Bergstedt
existe um arquivo chamado ThreadSafeList.cs no código-fonte dotnet que se parece muito com algum código abaixo. Ele também usa o ReaderWriterLockSlim e estava tentando descobrir por que usá-lo em vez do bloqueio simples (obj)?
colin lamarre 18/02

Respostas:

166

Eu tentei um tempo atrás (também: no GitHub ). Minha implementação teve alguns problemas, dos quais não vou entrar aqui. Deixe-me contar, mais importante, o que aprendi.

Em primeiro lugar, não há como você obter uma implementação completa IList<T>disso sem bloqueio e com segurança para threads. Em particular, inserções e remoções aleatórias não funcionarão, a menos que você também esqueça o acesso aleatório O (1) (ou seja, a menos que você "trapaceie" e use apenas algum tipo de lista vinculada e deixe a indexação ser uma droga).

O que eu pensei que poderia ser interessante era um subconjunto thread-safe, limitado de IList<T>: em particular, aquele que permitiria que um Adde fornecer aleatório somente leitura o acesso por índice (mas não Insert, RemoveAtetc., e também não há aleatório gravação de acesso).

Este foi o objetivo da minha ConcurrentList<T>implementação . Mas quando testei seu desempenho em cenários multithread, descobri que simplesmente a sincronização adiciona a um List<T>era mais rápido . Basicamente, adicionar a um List<T>já é super rápido; a complexidade das etapas computacionais envolvidas é minúscula (incrementa um índice e atribui a um elemento em uma matriz; é isso mesmo ). Você precisaria de uma tonelada de gravações simultâneas para ver qualquer tipo de contenção de bloqueio sobre isso; e mesmo assim, o desempenho médio de cada gravação ainda superaria a implementação mais cara, embora sem bloqueio ConcurrentList<T>.

No caso relativamente raro em que a matriz interna da lista precise se redimensionar, você paga um pequeno custo. Por fim, concluí que esse era o único cenário de nicho em que um ConcurrentList<T>tipo de coleção de adição apenas faria sentido: quando você deseja garantir uma baixa sobrecarga de adicionar um elemento em cada chamada (portanto, em oposição a uma meta de desempenho amortizado).

Simplesmente não é uma aula tão útil quanto você imagina.

Dan Tao
fonte
52
E se você precisa de algo semelhante ao List<T>que usos old-skool, sincronização baseado no monitor, não está SynchronizedCollection<T>escondido no BCL: msdn.microsoft.com/en-us/library/ms668265.aspx
LukeH
8
Uma pequena adição: use o parâmetro do construtor Capacity para evitar (o máximo possível) o cenário de redimensionamento.
Henk Holterman
2
O maior cenário em ConcurrentListque uma vitória seria quando não há muita atividade adicionando à lista, mas há muitos leitores simultâneos. Pode-se reduzir a sobrecarga dos leitores a uma única barreira de memória (e eliminar até isso se os leitores não estiverem preocupados com dados levemente obsoletos).
Supercat 19/02
2
@ Kevin: É bastante trivial construir de ConcurrentList<T>tal maneira que os leitores garantam um estado consistente sem a necessidade de qualquer bloqueio, com uma sobrecarga adicional relativamente pequena. Quando a lista se expandir, por exemplo, do tamanho 32 para o 64, mantenha a matriz size-32 e crie uma nova matriz size-64. Ao adicionar cada um dos próximos 32 itens, coloque-o no slot 32-63 da nova matriz e copie um item antigo da matriz tamanho 32 para a nova. Até que o 64º item seja adicionado, os leitores procurarão na matriz tamanho 32 os itens 0 a 31 e na matriz tamanho 64 os itens 32 a 63.
Supercat
2
Depois que o 64º item for adicionado, a matriz tamanho 32 ainda funcionará para buscar os itens de 0 a 31, mas os leitores não precisarão mais usá-lo. Eles podem usar a matriz size-64 para todos os itens de 0 a 63 e uma matriz size-128 para os itens de 64 a 127. A sobrecarga de selecionar qual das duas matrizes usar, além de uma barreira de memória, se desejado, seria menor do que a sobrecarga, mesmo da trava mais eficiente entre leitores e gravadores que se possa imaginar. Escreve provavelmente deve usar fechaduras (livre-lock seria possível, especialmente se não se importa criar uma nova instância do objeto com cada inserção, mas o bloqueio deve ser barato.
supercat
38

Para que você usaria uma ConcurrentList?

O conceito de um contêiner de acesso aleatório em um mundo encadeado não é tão útil quanto pode parecer. A declaração

  if (i < MyConcurrentList.Count)  
      x = MyConcurrentList[i]; 

como um todo ainda não seria seguro para threads.

Em vez de criar uma ConcurrentList, tente criar soluções com o que está lá. As classes mais comuns são o ConcurrentBag e, especialmente, o BlockingCollection.

Henk Holterman
fonte
Bom ponto. Ainda assim, o que estou fazendo é um pouco mais mundano. Estou apenas tentando atribuir o ConcurrentBag <T> em um IList <T>. Eu poderia mudar minha propriedade para um IEnumerable <T>, mas não consigo adicionar.
Alan
1
@ Alan: Não há como implementar isso sem bloquear a lista. Como você já pode Monitorfazer isso de qualquer maneira, não há motivo para uma lista simultânea.
Billy ONeal
6
@ dcp - sim, isso é inerentemente seguro para threads. ConcurrentDictionary tem métodos especiais que fazem isso em uma operação atômica, como AddOrUpdate, GetOrAdd, TryUpdate, etc. Eles ainda têm ContainsKey porque, às vezes, você só quer saber se a chave está lá sem modificar o dicionário (pense em HashSet)
Zarat
3
@dcp - ContainsKey é thread-safe por si só, seu exemplo (não ContainsKey!) apenas tem uma condição de corrida porque você faz uma segunda chamada, dependendo da primeira decisão, que nesse momento já pode estar desatualizada.
Zarat 06/07/11
2
Henk, não estou de acordo. Eu acho que existe um cenário simples em que poderia ser muito útil. A escrita do thread de trabalho nele lerá e atualizará a interface da interface do usuário de acordo. Se você deseja adicionar um item de maneira ordenada, será necessário um acesso aleatório de gravação. Você também pode usar uma pilha e uma visualização dos dados, mas terá que manter duas coleções :-(.
Eric Ouellet
19

Com todo o respeito pelas ótimas respostas já fornecidas, há momentos em que eu simplesmente quero um IList seguro para threads. Nada avançado ou sofisticado. O desempenho é importante em muitos casos, mas às vezes isso simplesmente não é uma preocupação. Sim, sempre haverá desafios sem métodos como "TryGetValue", etc., mas na maioria dos casos eu só quero algo que eu possa enumerar sem precisar se preocupar em bloquear tudo. E sim, alguém provavelmente pode encontrar algum "bug" na minha implementação que possa levar a um impasse ou algo assim (suponho), mas vamos ser honestos: quando se trata de multi-threading, se você não escrever seu código corretamente, ele está entrando em impasse de qualquer maneira. Com isso em mente, decidi fazer uma implementação ConcurrentList simples que forneça essas necessidades básicas.

E pelo que vale: fiz um teste básico de adição de 10.000.000 de itens à List e ConcurrentList regulares e os resultados foram:

Lista finalizada em: 7793 milissegundos. Simultâneo concluído em: 8064 milissegundos.

public class ConcurrentList<T> : IList<T>, IDisposable
{
    #region Fields
    private readonly List<T> _list;
    private readonly ReaderWriterLockSlim _lock;
    #endregion

    #region Constructors
    public ConcurrentList()
    {
        this._lock = new ReaderWriterLockSlim(LockRecursionPolicy.NoRecursion);
        this._list = new List<T>();
    }

    public ConcurrentList(int capacity)
    {
        this._lock = new ReaderWriterLockSlim(LockRecursionPolicy.NoRecursion);
        this._list = new List<T>(capacity);
    }

    public ConcurrentList(IEnumerable<T> items)
    {
        this._lock = new ReaderWriterLockSlim(LockRecursionPolicy.NoRecursion);
        this._list = new List<T>(items);
    }
    #endregion

    #region Methods
    public void Add(T item)
    {
        try
        {
            this._lock.EnterWriteLock();
            this._list.Add(item);
        }
        finally
        {
            this._lock.ExitWriteLock();
        }
    }

    public void Insert(int index, T item)
    {
        try
        {
            this._lock.EnterWriteLock();
            this._list.Insert(index, item);
        }
        finally
        {
            this._lock.ExitWriteLock();
        }
    }

    public bool Remove(T item)
    {
        try
        {
            this._lock.EnterWriteLock();
            return this._list.Remove(item);
        }
        finally
        {
            this._lock.ExitWriteLock();
        }
    }

    public void RemoveAt(int index)
    {
        try
        {
            this._lock.EnterWriteLock();
            this._list.RemoveAt(index);
        }
        finally
        {
            this._lock.ExitWriteLock();
        }
    }

    public int IndexOf(T item)
    {
        try
        {
            this._lock.EnterReadLock();
            return this._list.IndexOf(item);
        }
        finally
        {
            this._lock.ExitReadLock();
        }
    }

    public void Clear()
    {
        try
        {
            this._lock.EnterWriteLock();
            this._list.Clear();
        }
        finally
        {
            this._lock.ExitWriteLock();
        }
    }

    public bool Contains(T item)
    {
        try
        {
            this._lock.EnterReadLock();
            return this._list.Contains(item);
        }
        finally
        {
            this._lock.ExitReadLock();
        }
    }

    public void CopyTo(T[] array, int arrayIndex)
    {
        try
        {
            this._lock.EnterReadLock();
            this._list.CopyTo(array, arrayIndex);
        }
        finally
        {
            this._lock.ExitReadLock();
        }
    }

    public IEnumerator<T> GetEnumerator()
    {
        return new ConcurrentEnumerator<T>(this._list, this._lock);
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return new ConcurrentEnumerator<T>(this._list, this._lock);
    }

    ~ConcurrentList()
    {
        this.Dispose(false);
    }

    public void Dispose()
    {
        this.Dispose(true);
    }

    private void Dispose(bool disposing)
    {
        if (disposing)
            GC.SuppressFinalize(this);

        this._lock.Dispose();
    }
    #endregion

    #region Properties
    public T this[int index]
    {
        get
        {
            try
            {
                this._lock.EnterReadLock();
                return this._list[index];
            }
            finally
            {
                this._lock.ExitReadLock();
            }
        }
        set
        {
            try
            {
                this._lock.EnterWriteLock();
                this._list[index] = value;
            }
            finally
            {
                this._lock.ExitWriteLock();
            }
        }
    }

    public int Count
    {
        get
        {
            try
            {
                this._lock.EnterReadLock();
                return this._list.Count;
            }
            finally
            {
                this._lock.ExitReadLock();
            }
        }
    }

    public bool IsReadOnly
    {
        get { return false; }
    }
    #endregion
}

    public class ConcurrentEnumerator<T> : IEnumerator<T>
{
    #region Fields
    private readonly IEnumerator<T> _inner;
    private readonly ReaderWriterLockSlim _lock;
    #endregion

    #region Constructor
    public ConcurrentEnumerator(IEnumerable<T> inner, ReaderWriterLockSlim @lock)
    {
        this._lock = @lock;
        this._lock.EnterReadLock();
        this._inner = inner.GetEnumerator();
    }
    #endregion

    #region Methods
    public bool MoveNext()
    {
        return _inner.MoveNext();
    }

    public void Reset()
    {
        _inner.Reset();
    }

    public void Dispose()
    {
        this._lock.ExitReadLock();
    }
    #endregion

    #region Properties
    public T Current
    {
        get { return _inner.Current; }
    }

    object IEnumerator.Current
    {
        get { return _inner.Current; }
    }
    #endregion
}
Brian Booth
fonte
5
OK, resposta antiga, mas ainda assim: RemoveAt(int index)nunca Insert(int index, T item)é seguro para threads, é seguro apenas para o índice == 0, o retorno de IndexOf()é imediatamente desatualizado etc. Nem comece sobre o this[int].
Henk Holterman
2
E você não precisa e não quer um ~ Finalizador ().
Henk Holterman
2
Você diz que desistiu de impedir a possibilidade de impasse - e um único ReaderWriterLockSlimpode ser impaciente facilmente usando-o EnterUpgradeableReadLock()simultaneamente. No entanto, você não o usa, não torna o bloqueio acessível para o exterior e, por exemplo, não chama um método que insira um bloqueio de gravação enquanto mantém um bloqueio de leitura, portanto, o uso da sua classe não gera mais impasses. provável.
Eugene Beresovsky
1
A interface não simultânea não é apropriada para acesso simultâneo. Por exemplo, o seguinte não é atômico var l = new ConcurrentList<string>(); /* ... */ l[0] += "asdf";. Em geral, qualquer combinação de leitura e gravação pode causar problemas profundos quando executada simultaneamente. É por isso que as estruturas de dados simultâneos geralmente fornecem métodos para aqueles, como ConcurrentDictionary's AddOrGetetc. NB sua constante (e redundante porque os membros já estão marcadas como tal pelo sublinhado) repetição de this.desordens.
Eugene Beresovsky
1
Obrigado Eugene. Eu sou um usuário pesado do .NET Reflector que coloca "isto". em todos os campos não estáticos. Como tal, passei a preferir o mesmo. Quanto a essa interface não simultânea não ser apropriada: Você está absolutamente certo de que tentar executar várias ações contra minha implementação pode se tornar não confiável. Mas o requisito aqui é simplesmente que ações únicas (adicionar, remover, limpar ou enumerar) possam ser realizadas sem danificar a coleção. Basicamente, remove a necessidade de colocar instruções de bloqueio em torno de tudo.
Brian Booth
11

ConcurrentList(como uma matriz redimensionável, não uma lista vinculada) não é fácil de escrever com operações sem bloqueio. Sua API não se traduz bem em uma versão "simultânea".

Stephen Cleary
fonte
12
Não é apenas difícil escrever, é até difícil descobrir uma interface útil.
CodesInChaos
11

A razão pela qual não existe ConcurrentList é porque fundamentalmente não pode ser gravada. A razão é que várias operações importantes no IList dependem de índices e isso simplesmente não funciona. Por exemplo:

int catIndex = list.IndexOf("cat");
list.Insert(catIndex, "dog");

O efeito que o autor está buscando é inserir "cachorro" antes de "gato", mas em um ambiente multithread, qualquer coisa pode acontecer com a lista entre essas duas linhas de código. Por exemplo, outro encadeamento pode ser feito list.RemoveAt(0), deslocando a lista inteira para a esquerda, mas, crucialmente, o catIndex não será alterado. O impacto aqui é que a Insertoperação realmente colocará o "cachorro" atrás do gato, não antes dele.

As várias implementações que você vê oferecidas como "respostas" a esta pergunta são bem-intencionadas, mas, como mostra acima, elas não oferecem resultados confiáveis. Se você realmente deseja semântica de lista em um ambiente multithread, não pode chegar lá colocando bloqueios dentro os métodos de implementação lista. Você deve garantir que qualquer índice que você use viva inteiramente dentro do contexto do bloqueio. O resultado é que você pode usar uma Lista em um ambiente multithread com o bloqueio correto, mas a lista em si não pode existir nesse mundo.

Se você acha que precisa de uma lista simultânea, existem realmente apenas duas possibilidades:

  1. O que você realmente precisa é de um ConcurrentBag
  2. Você precisa criar sua própria coleção, talvez implementada com uma lista e seu próprio controle de simultaneidade.

Se você tem um ConcurrentBag e está em uma posição em que precisa transmiti-lo como um IList, há um problema, porque o método que você está chamando especificou que eles podem tentar fazer algo como eu fiz acima com o gato & cão. Na maioria dos mundos, o que isso significa é que o método que você está chamando simplesmente não foi criado para funcionar em um ambiente multithread. Isso significa que você o refatora para que seja ou, se não puder, terá que lidar com isso com muito cuidado. Você quase certamente precisará criar sua própria coleção com seus próprios bloqueios e chamar o método incorreto dentro de um bloqueio.

Steve Benz
fonte
5

Nos casos em que as leituras superam em número as gravações ou (por mais freqüentes) que sejam, não são simultâneas , uma cópia na gravação abordagem de pode ser apropriada.

A implementação mostrada abaixo é

  • sem fechadura
  • incrivelmente rápido para leituras simultâneas , mesmo enquanto modificações simultâneas estão em andamento - não importa quanto tempo elas levem
  • porque "snapshots" são imutáveis, a atomicidade sem bloqueio é possível, ou seja var snap = _list; snap[snap.Count - 1];, nunca (bem, exceto por uma lista vazia, é claro) será lançada, e você também terá uma enumeração segura de segmentos com semântica de snapshots de graça .. como EU AMO a imutabilidade!
  • implementado genericamente , aplicável a qualquer estrutura de dados e qualquer tipo de modificação
  • simples morto , fácil de testar, depurar, verificar lendo o código
  • utilizável no .Net 3.5

Para que a cópia na gravação funcione, é necessário manter suas estruturas de dados efetivamente imutáveis , ou seja, ninguém poderá alterá-las depois de disponibilizá-las para outros threads. Quando você deseja modificar, você

  1. clonar a estrutura
  2. faça modificações no clone
  3. trocar atomicamente na referência ao clone modificado

Código

static class CopyOnWriteSwapper
{
    public static void Swap<T>(ref T obj, Func<T, T> cloner, Action<T> op)
        where T : class
    {
        while (true)
        {
            var objBefore = Volatile.Read(ref obj);
            var newObj = cloner(objBefore);
            op(newObj);
            if (Interlocked.CompareExchange(ref obj, newObj, objBefore) == objBefore)
                return;
        }
    }
}

Uso

CopyOnWriteSwapper.Swap(ref _myList,
    orig => new List<string>(orig),
    clone => clone.Add("asdf"));

Se você precisar de mais desempenho, ajudará a não gerar o método, por exemplo, crie um método para cada tipo de modificação (Adicionar, Remover, ...) desejado e codifique os ponteiros de função clonere op.

NB # 1 É de sua responsabilidade garantir que ninguém modifique a estrutura de dados (supostamente) imutável. Não há nada que possamos fazer em uma implementação genérica para impedir isso, mas ao se especializar List<T>, você pode se proteger contra modificações usando List.AsReadOnly ()

Nota # 2 Tenha cuidado com os valores da lista. A abordagem de cópia na gravação acima protege apenas a participação na lista, mas se você não colocar strings, mas alguns outros objetos mutáveis, precisará cuidar da segurança do encadeamento (por exemplo, bloqueio). Mas isso é ortogonal a esta solução e, por exemplo, o bloqueio dos valores mutáveis ​​pode ser facilmente usado sem problemas. Você só precisa estar ciente disso.

Nota # 3 Se sua estrutura de dados é enorme e você a modifica com frequência, a abordagem de copiar tudo na gravação pode ser proibitiva em termos de consumo de memória e no custo de cópia da CPU envolvido. Nesse caso, convém usar as coleções imutáveis da MS .

Eugene Beresovsky
fonte
3

System.Collections.Generic.List<t>já é thread-safe para vários leitores. Tentar torná-lo seguro para vários escritores não faria sentido. (Por razões que Henk e Stephen já mencionaram)

Billy ONeal
fonte
Você não consegue ver um cenário em que eu possa ter 5 tópicos sendo adicionados a uma lista? Dessa forma, você pode ver a lista acumular registros mesmo antes de todos eles terminarem.
Alan
9
@ Alan - seria um ConcurrentQueue, ConcurrentStack ou ConcurrentBag. Para entender um ConcurrentList, você deve fornecer um caso de uso em que as classes disponíveis não sejam suficientes. Não vejo por que desejaria acesso indexado quando os elementos nos índices podem mudar aleatoriamente através de remoções simultâneas. E para uma leitura "bloqueada", você já pode tirar instantâneos das classes simultâneas existentes e colocá-los em uma lista.
Zarat 6/07/11
Você está certo - não quero acesso indexado. Eu geralmente uso IList <T> como um proxy para um IEnumerable ao qual eu posso adicionar (T) novos elementos. É daí que a pergunta vem, realmente.
Alan
@ Alan: Então você quer uma fila, não uma lista.
Billy ONeal
3
Eu acho que você está errado. Dizer: seguro para vários leitores não significa que você não pode escrever ao mesmo tempo. Escrever também significaria excluir e você receberá um erro se excluir ao iterar nela.
precisa
2

Algumas pessoas sugeriram alguns pontos positivos (e alguns dos meus pensamentos):

  • Poderia parecer insano o incapaz de acessar aleatoriamente (indexador), mas para mim parece bom. Você só precisa pensar que existem muitos métodos em coleções multithread que podem falhar, como Indexador e Excluir. Você também pode definir uma ação de falha (fallback) para o acessador de gravação, como "falha" ou simplesmente "adicionar no final".
  • Não é porque é uma coleção multithread que ela sempre será usada em um contexto multithread. Ou também poderia ser usado por apenas um escritor e um leitor.
  • Outra maneira de poder usar o indexador de maneira segura pode ser agrupar ações em um bloqueio da coleção usando sua raiz (se tornada pública).
  • Para muitas pessoas, tornar um rootLock visível se torna uma "boa prática". Não tenho 100% de certeza sobre esse ponto, porque, se estiver oculto, você remove muita flexibilidade do usuário. Sempre devemos lembrar que a programação multithread não é para ninguém. Não podemos impedir todo tipo de uso errado.
  • A Microsoft terá que fazer algum trabalho e definir um novo padrão para introduzir o uso adequado da coleção Multithread. Primeiro, o IEnumerator não deve ter um moveNext, mas deve ter um GetNext que retorne verdadeiro ou falso e obtenha um parâmetro de saída do tipo T (desta forma, a iteração não estaria mais bloqueando). Além disso, a Microsoft já usa "using" internamente no foreach, mas às vezes usa o IEnumerator diretamente, sem agrupá-lo com "using" (um bug na exibição de coleção e provavelmente em mais locais) - O uso de encapsulamento do IEnumerator é uma prática recomendada pela Microsoft. Esse bug remove um bom potencial para o iterador seguro ... Iterador que bloqueia a coleção no construtor e desbloqueia no seu método Dispose - para um método de bloqueio para cada.

Isso não é resposta. São apenas comentários que realmente não se encaixam em um local específico.

... Minha conclusão, a Microsoft precisa fazer algumas alterações profundas no "foreach" para facilitar o uso da coleção MultiThreaded. Também deve seguir as próprias regras de uso do IEnumerator. Até isso, podemos escrever um MultiThreadList facilmente que usaria um iterador de bloqueio, mas que não seguirá "IList". Em vez disso, você terá que definir a interface "IListPersonnal" própria que poderá falhar ao "inserir", "remover" e acessador aleatório (indexador) sem exceção. Mas quem vai querer usá-lo se não for padrão?

Eric Ouellet
fonte
Pode-se facilmente escrever um ConcurrentOrderedBag<T>que inclua uma implementação somente leitura IList<T>, mas também ofereça um int Add(T value)método totalmente seguro para threads . Não vejo por ForEachque seriam necessárias alterações. Embora a Microsoft não diga explicitamente, a prática deles sugere que é perfeitamente aceitável IEnumerator<T>enumerar o conteúdo da coleção que existia quando ele foi criado; a exceção modificada por coleção é necessária apenas se o enumerador não puder garantir uma operação sem falhas.
Supercat 11/12
Iterando através de uma coleção de MT, a maneira como o design pode levar, como você disse, a uma exceção ... Qual eu não conheço. Você capturaria todas as exceções? No meu próprio livro, exceção é exceção e não deve ocorrer na execução normal do código. Caso contrário, para evitar a exceção, você deve bloquear a coleção ou obter uma cópia (de maneira segura, ou seja, bloquear) ou implementar um mecanismo muito complexo na coleção para impedir que a exceção ocorra devido à simultaneidade. Meu embora foi que seria bom para adicionar um IEnumeratorMT que bloquear a coleção enquanto um para cada ocorrer e adicionar código relacionado ...
Eric Ouellet
A outra coisa que também pode ocorrer é que, quando você obtém um iterador, pode bloquear a coleção e, quando o iterador é coletado por GC, pode desbloquear a coleção. De acordo com a Microsfot, eles já verificam se o IEnumerable também é um IDisposable e chamam o GC nesse caso no final de um ForEach. O principal problema é que eles também usam o IEnumerable em outro lugar sem chamar o GC, então você não pode confiar nisso. Ter uma nova interface MT clara para o bloqueio de ativação IEnumerable resolveria o problema, pelo menos em parte. (Isso não impediria as pessoas de não chamá-lo).
Eric Ouellet
É uma péssima forma para um GetEnumeratormétodo público deixar uma coleção bloqueada após seu retorno; esses projetos podem facilmente levar a um impasse. A IEnumerable<T>não fornece nenhuma indicação de se uma enumeração pode ser esperado para completar mesmo se uma recolha é modificado; o melhor que se pode fazer é escrever seus próprios métodos para que eles o façam e ter métodos que aceitem IEnumerable<T>documentar o fato de que somente será seguro IEnumerable<T>para threads se o suporte à enumeração segura para threads.
Supercat 11/12
O que seria mais útil seria se IEnumerable<T>tivesse incluído um método "Instantâneo" com o tipo de retorno IEnumerable<T>. Coleções imutáveis ​​podem se recuperar; uma coleção limitada poderia se nada mais se copiar para um List<T>ou T[]e invocar GetEnumeratorisso. Algumas coleções ilimitadas poderiam ser implementadas Snapshot, e aquelas que não poderiam seriam capazes de lançar uma exceção sem tentar preencher uma lista com seu conteúdo.
Supercat 11/13
1

Na execução seqüencial de código, as estruturas de dados utilizadas são diferentes do código (bem escrito) de execução simultânea. A razão é que o código seqüencial implica ordem implícita. Código simultâneo, no entanto, não implica nenhum pedido; melhor ainda, implica a falta de qualquer ordem definida!

Devido a isso, estruturas de dados com ordem implícita (como Lista) não são muito úteis para resolver problemas simultâneos. Uma lista implica ordem, mas não define claramente qual é essa ordem. Por esse motivo, a ordem de execução do código que manipula a lista determinará (até certo ponto) a ordem implícita da lista, que está em conflito direto com uma solução simultânea eficiente.

Lembre-se de que a simultaneidade é um problema de dados, não de código! Você não pode implementar o código primeiro (ou reescrever o código sequencial existente) e obter uma solução simultânea bem projetada. Você precisa projetar as estruturas de dados primeiro, mantendo em mente que a ordem implícita não existe em um sistema simultâneo.

Blueprint41
fonte
1

A abordagem de copiar e gravar sem bloqueio funciona muito bem se você não estiver lidando com muitos itens. Aqui está uma aula que escrevi:

public class CopyAndWriteList<T>
{
    public static List<T> Clear(List<T> list)
    {
        var a = new List<T>(list);
        a.Clear();
        return a;
    }

    public static List<T> Add(List<T> list, T item)
    {
        var a = new List<T>(list);
        a.Add(item);
        return a;
    }

    public static List<T> RemoveAt(List<T> list, int index)
    {
        var a = new List<T>(list);
        a.RemoveAt(index);
        return a;
    }

    public static List<T> Remove(List<T> list, T item)
    {
        var a = new List<T>(list);
        a.Remove(item);
        return a;
    }

}

exemplo de uso: orders_BUY = CopyAndWriteList.Clear (orders_BUY);

Rob The Quant
fonte
em vez de bloquear, ele cria uma cópia da lista, modifica a lista e define a referência para a nova lista. Portanto, quaisquer outros threads que estão iterando não causarão problemas.
Rob O Quant
0

Eu implementei um semelhante ao de Brian . O meu é diferente:

  • Eu gerencio a matriz diretamente.
  • Não insiro os bloqueios no bloco try.
  • Eu uso yield returnpara produzir um enumerador.
  • Eu apoio a recursão de bloqueio. Isso permite leituras da lista durante a iteração.
  • Eu uso bloqueios de leitura atualizáveis ​​sempre que possível.
  • DoSynce GetSyncmétodos que permitem interações sequenciais que requerem acesso exclusivo à lista.

O código :

public class ConcurrentList<T> : IList<T>, IDisposable
{
    private ReaderWriterLockSlim _lock = new ReaderWriterLockSlim(LockRecursionPolicy.SupportsRecursion);
    private int _count = 0;

    public int Count
    {
        get
        { 
            _lock.EnterReadLock();
            try
            {           
                return _count;
            }
            finally
            {
                _lock.ExitReadLock();
            }
        }
    }

    public int InternalArrayLength
    { 
        get
        { 
            _lock.EnterReadLock();
            try
            {           
                return _arr.Length;
            }
            finally
            {
                _lock.ExitReadLock();
            }
        }
    }

    private T[] _arr;

    public ConcurrentList(int initialCapacity)
    {
        _arr = new T[initialCapacity];
    }

    public ConcurrentList():this(4)
    { }

    public ConcurrentList(IEnumerable<T> items)
    {
        _arr = items.ToArray();
        _count = _arr.Length;
    }

    public void Add(T item)
    {
        _lock.EnterWriteLock();
        try
        {       
            var newCount = _count + 1;          
            EnsureCapacity(newCount);           
            _arr[_count] = item;
            _count = newCount;                  
        }
        finally
        {
            _lock.ExitWriteLock();
        }       
    }

    public void AddRange(IEnumerable<T> items)
    {
        if (items == null)
            throw new ArgumentNullException("items");

        _lock.EnterWriteLock();

        try
        {           
            var arr = items as T[] ?? items.ToArray();          
            var newCount = _count + arr.Length;
            EnsureCapacity(newCount);           
            Array.Copy(arr, 0, _arr, _count, arr.Length);       
            _count = newCount;
        }
        finally
        {
            _lock.ExitWriteLock();          
        }
    }

    private void EnsureCapacity(int capacity)
    {   
        if (_arr.Length >= capacity)
            return;

        int doubled;
        checked
        {
            try
            {           
                doubled = _arr.Length * 2;
            }
            catch (OverflowException)
            {
                doubled = int.MaxValue;
            }
        }

        var newLength = Math.Max(doubled, capacity);            
        Array.Resize(ref _arr, newLength);
    }

    public bool Remove(T item)
    {
        _lock.EnterUpgradeableReadLock();

        try
        {           
            var i = IndexOfInternal(item);

            if (i == -1)
                return false;

            _lock.EnterWriteLock();
            try
            {   
                RemoveAtInternal(i);
                return true;
            }
            finally
            {               
                _lock.ExitWriteLock();
            }
        }
        finally
        {           
            _lock.ExitUpgradeableReadLock();
        }
    }

    public IEnumerator<T> GetEnumerator()
    {
        _lock.EnterReadLock();

        try
        {    
            for (int i = 0; i < _count; i++)
                // deadlocking potential mitigated by lock recursion enforcement
                yield return _arr[i]; 
        }
        finally
        {           
            _lock.ExitReadLock();
        }
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return this.GetEnumerator();
    }

    public int IndexOf(T item)
    {
        _lock.EnterReadLock();
        try
        {   
            return IndexOfInternal(item);
        }
        finally
        {
            _lock.ExitReadLock();
        }
    }

    private int IndexOfInternal(T item)
    {
        return Array.FindIndex(_arr, 0, _count, x => x.Equals(item));
    }

    public void Insert(int index, T item)
    {
        _lock.EnterUpgradeableReadLock();

        try
        {                       
            if (index > _count)
                throw new ArgumentOutOfRangeException("index"); 

            _lock.EnterWriteLock();
            try
            {       
                var newCount = _count + 1;
                EnsureCapacity(newCount);

                // shift everything right by one, starting at index
                Array.Copy(_arr, index, _arr, index + 1, _count - index);

                // insert
                _arr[index] = item;     
                _count = newCount;
            }
            finally
            {           
                _lock.ExitWriteLock();
            }
        }
        finally
        {
            _lock.ExitUpgradeableReadLock();            
        }


    }

    public void RemoveAt(int index)
    {   
        _lock.EnterUpgradeableReadLock();
        try
        {   
            if (index >= _count)
                throw new ArgumentOutOfRangeException("index");

            _lock.EnterWriteLock();
            try
            {           
                RemoveAtInternal(index);
            }
            finally
            {
                _lock.ExitWriteLock();
            }
        }
        finally
        {
            _lock.ExitUpgradeableReadLock();            
        }
    }

    private void RemoveAtInternal(int index)
    {           
        Array.Copy(_arr, index + 1, _arr, index, _count - index-1);
        _count--;

        // release last element
        Array.Clear(_arr, _count, 1);
    }

    public void Clear()
    {
        _lock.EnterWriteLock();
        try
        {        
            Array.Clear(_arr, 0, _count);
            _count = 0;
        }
        finally
        {           
            _lock.ExitWriteLock();
        }   
    }

    public bool Contains(T item)
    {
        _lock.EnterReadLock();
        try
        {   
            return IndexOfInternal(item) != -1;
        }
        finally
        {           
            _lock.ExitReadLock();
        }
    }

    public void CopyTo(T[] array, int arrayIndex)
    {       
        _lock.EnterReadLock();
        try
        {           
            if(_count > array.Length - arrayIndex)
                throw new ArgumentException("Destination array was not long enough.");

            Array.Copy(_arr, 0, array, arrayIndex, _count);
        }
        finally
        {
            _lock.ExitReadLock();           
        }
    }

    public bool IsReadOnly
    {   
        get { return false; }
    }

    public T this[int index]
    {
        get
        {
            _lock.EnterReadLock();
            try
            {           
                if (index >= _count)
                    throw new ArgumentOutOfRangeException("index");

                return _arr[index]; 
            }
            finally
            {
                _lock.ExitReadLock();               
            }           
        }
        set
        {
            _lock.EnterUpgradeableReadLock();
            try
            {

                if (index >= _count)
                    throw new ArgumentOutOfRangeException("index");

                _lock.EnterWriteLock();
                try
                {                       
                    _arr[index] = value;
                }
                finally
                {
                    _lock.ExitWriteLock();              
                }
            }
            finally
            {
                _lock.ExitUpgradeableReadLock();
            }

        }
    }

    public void DoSync(Action<ConcurrentList<T>> action)
    {
        GetSync(l =>
        {
            action(l);
            return 0;
        });
    }

    public TResult GetSync<TResult>(Func<ConcurrentList<T>,TResult> func)
    {
        _lock.EnterWriteLock();
        try
        {           
            return func(this);
        }
        finally
        {
            _lock.ExitWriteLock();
        }
    }

    public void Dispose()
    {   
        _lock.Dispose();
    }
}
Ronnie Overby
fonte
O que acontece se dois threads entrarem no início do trybloco Removeou no indexador ao mesmo tempo?
James
@ James que não parece possível. Leia as observações em msdn.microsoft.com/en-us/library/… . Executar esse código, você nunca vai entrar nesse bloqueio uma segunda vez: gist.github.com/ronnieoverby/59b715c3676127a113c3
Ronnie Overby
@ Ronny Overby: Interessante. Dado isso, suspeito que isso teria um desempenho muito melhor se você removesse o UpgradableReadLock de todas as funções em que a única operação executada no período entre o bloqueio de leitura atualizável e o bloqueio de gravação - a sobrecarga de realizar qualquer tipo de bloqueio é muito mais do que a verificação para ver se o parâmetro está fora do intervalo, que apenas fazer essa verificação dentro do bloqueio de gravação provavelmente teria um desempenho melhor.
James
Essa classe também não parece muito útil, pois as funções baseadas em deslocamento (a maioria delas) nunca podem realmente ser usadas com segurança, a menos que exista algum esquema de bloqueio externo, porque a coleção pode mudar entre quando você decide onde colocar ou obter algo de e quando você realmente obtê-lo.
James
1
Eu queria registrar dizendo que reconheço que a utilidade da IListsemântica em cenários simultâneos é limitada na melhor das hipóteses. Eu escrevi esse código provavelmente antes de chegar a essa conclusão. Minha experiência é a mesma do autor da resposta aceita: tentei com o que sabia sobre sincronização e IList <T> e aprendi algo ao fazer isso.
Ronnie Overby