A imutabilidade elimina inteiramente a necessidade de bloqueios na programação multiprocessador?

37

Parte 1

Claramente imutabilidade minimiza a necessidade de bloqueios na programação de multiprocessadores, mas isso elimina essa necessidade, ou existem casos em que a imutabilidade sozinha não é suficiente? Parece-me que você só pode adiar o processamento e encapsular o estado por tanto tempo antes que a maioria dos programas precise realmente fazer alguma coisa (atualizar um armazenamento de dados, produzir um relatório, lançar uma exceção etc.). Essas ações sempre podem ser feitas sem bloqueios? A mera ação de jogar fora cada objeto e criar um novo, em vez de mudar o original (uma visão grosseira da imutabilidade), fornece proteção absoluta contra contenção entre processos, ou há casos que ainda precisam ser bloqueados?

Eu sei que muitos programadores funcionais e matemáticos gostam de falar sobre "sem efeitos colaterais", mas no "mundo real" tudo tem um efeito colateral, mesmo que seja o tempo que leva para executar uma instrução de máquina. Estou interessado tanto na resposta teórica / acadêmica quanto na prática / real.

Se a imutabilidade é segura, dados certos limites ou suposições, quero saber quais são exatamente as bordas da "zona de segurança". Alguns exemplos de possíveis limites:

  • E / S
  • Exceções / erros
  • Interações com programas escritos em outros idiomas
  • Interações com outras máquinas (físicas, virtuais ou teóricas)

Um agradecimento especial a @JimmaHoffa pelo seu comentário que começou esta questão!

Parte 2

A programação com vários processadores é frequentemente usada como uma técnica de otimização - para fazer com que alguns códigos sejam executados mais rapidamente. Quando é mais rápido usar bloqueios contra objetos imutáveis?

Dados os limites estabelecidos na Lei de Amdahl , quando é possível alcançar um melhor desempenho geral (com ou sem o coletor de lixo levado em conta) com objetos imutáveis vs. bloqueando mutáveis?

Resumo

Estou combinando essas duas perguntas em uma para tentar chegar onde a caixa delimitadora é para Imutabilidade como uma solução para problemas de encadeamento.

    
por GlenPeterson 24.10.2012 / 20:29
fonte

5 respostas

33

Esta é uma pergunta estranhamente formulada que é muito, muito ampla se respondida completamente. Vou me concentrar em esclarecer algumas das especificidades sobre as quais você está perguntando.

Imutabilidade é um trade off design. Ele dificulta algumas operações (modificando o estado em objetos grandes rapidamente, construindo objetos fragmentados, mantendo um estado em execução, etc.) em favor de outros (depuração mais fácil, raciocínio mais fácil sobre o comportamento do programa, sem ter que se preocupar com mudanças durante o trabalho concorrentemente, etc.). É com este último que nos preocupamos com esta questão, mas quero enfatizar que é uma ferramenta. Uma boa ferramenta que muitas vezes resolve mais problemas do que provoca (na maioria dos programas modernos ), mas não uma bala de prata ... Não é algo que mude o comportamento intrínseco dos programas.

Agora, o que isso faz para você? A imutabilidade leva você a uma coisa: você pode ler o objeto imutável livremente, sem se preocupar com o estado que está mudando debaixo de você (supondo que seja verdadeiramente imutável ... Ter um objeto imutável com membros mutáveis geralmente é um fator decisivo). É isso aí. Ele libera você de ter que gerenciar a simultaneidade (por meio de bloqueios, snapshots, particionamento de dados ou outros mecanismos; o foco da pergunta original em bloqueios é ... Incorreto, dado o escopo da pergunta).

Acontece que muitas coisas leem objetos. O IO faz, mas o próprio IO tende a não lidar bem com o uso simultâneo. Quase todo o processamento funciona, mas outros objetos podem ser mutáveis ou o próprio processamento pode usar um estado que não seja compatível com a simultaneidade. Copiar um objeto é um grande problema oculto em alguns idiomas, já que uma cópia completa (quase) nunca é uma operação atômica. É aqui que objetos imutáveis ajudam você.

Quanto ao desempenho, isso depende do seu aplicativo. Bloqueios são (geralmente) pesados. Outros mecanismos de gerenciamento de simultaneidade são mais rápidos, mas têm um alto impacto em seu design. Em geral , um design altamente concorrente que faz uso de objetos imutáveis (e evita suas fraquezas) terá um desempenho melhor do que um design altamente simultâneo que bloqueia objetos mutáveis. Se o seu programa é levemente concorrente, então depende e / ou não importa.

Mas o desempenho não deve ser sua maior preocupação. Escrever programas concorrentes é difícil . A depuração de programas concorrentes é difícil . Objetos imutáveis ajudam a melhorar a qualidade do seu programa, eliminando oportunidades de erro ao implementar o gerenciamento de simultaneidade manualmente. Eles facilitam a depuração porque você não está tentando controlar o estado em um programa simultâneo. Eles tornam seu design mais simples e, portanto, removem erros.

Então, para resumir: a imutabilidade ajuda, mas não elimina os desafios necessários para lidar adequadamente com a concorrência. Essa ajuda tende a ser difundida, mas os maiores ganhos são de uma perspectiva de qualidade e não de desempenho. E não, a imutabilidade não o isenta magicamente de gerenciar a simultaneidade em seu aplicativo, desculpe.

    
por 25.10.2012 / 00:51
fonte
11

Uma função que aceita algum valor e retorna algum outro valor, e não perturba nada fora da função, não tem efeitos colaterais e, portanto, é isenta de threads. Se você quiser considerar coisas como o modo como a função é executada afeta o consumo de energia, esse é um problema diferente.

Estou assumindo que você está se referindo a uma máquina Turing-completa que está executando algum tipo de linguagem de programação bem definida, onde os detalhes da implementação são irrelevantes. Em outras palavras, não importa o que a pilha esteja fazendo, se a função que estou escrevendo na minha linguagem de programação de escolha puder garantir a imutabilidade dentro dos limites da linguagem. Eu não penso sobre a pilha quando estou programando em uma linguagem de alto nível, nem deveria precisar.

Para ilustrar como isso funciona, vou oferecer alguns exemplos simples em C #. Para que esses exemplos sejam verdade, precisamos fazer algumas suposições. Primeiro, que o compilador segue a especificação C # sem erro, e segundo, que produz programas corretos.

Digamos que eu queira uma função simples que aceite uma coleção de strings e retorne uma string que seja uma concatenação de todas as strings da coleção separadas por vírgulas. Uma implementação simples e ingênua no C # pode ser assim:

public string ConcatenateWithCommas(ImmutableList<string> list)
{
    string result = string.Empty;
    bool isFirst = false;

    foreach (string s in list)
    {
        if (isFirst)
            result += s;
        else
            result += ", " + s;
    }
    return result;
} 

Este exemplo é imutável, prima facie. Como eu sei disso? Porque o objeto string é imutável. No entanto, a implementação não é ideal. Como result é imutável, um novo objeto de cadeia de caracteres deve ser criado toda vez através do loop, substituindo o objeto original para o qual result aponta. Isso pode afetar negativamente a velocidade e pressionar o coletor de lixo, já que ele precisa limpar todas essas cordas extras.

Agora, digamos que eu faça isso:

public string ConcatenateWithCommas(ImmutableList<string> list)
{
    var result = new StringBuilder();
    bool isFirst = false;

    foreach (string s in list)
    {
        if (isFirst)
            result.Append(s);
        else
            result.Append(", " + s);
    }
    return result.ToString();
} 

Observe que substituí string result por um objeto mutável, StringBuilder . Isso é muito mais rápido que o primeiro exemplo, porque uma nova string não é criada toda vez através do loop. Em vez disso, o objeto StringBuilder apenas adiciona os caracteres de cada string a uma coleção de caracteres e gera a saída inteira no final.

Esta função é imutável, mesmo que o StringBuilder seja mutável?

Sim, é. Por quê? Porque cada vez que esta função é chamada, um novo StringBuilder é criado, apenas para aquela chamada. Agora temos uma função pura que é thread-safe, mas contém componentes mutáveis.

Mas e se eu fizesse isso?

public class Concatenate
{
    private StringBuilder result = new StringBuilder();
    bool isFirst = false;

    public string ConcatenateWithCommas(ImmutableList<string> list)
    {
        foreach (string s in list)
        {
            if (isFirst)
                result.Append(s);
            else
                result.Append(", " + s);
        }
        return result.ToString();
    } 
}

Este método é seguro para threads? Não é não. Por quê? Porque a classe agora está mantendo o estado do qual meu método depende. Uma condição de corrida agora está presente no método: um thread pode modificar IsFirst , mas outro thread pode executar o primeiro Append() , em Nesse caso, agora tenho uma vírgula no começo da minha string, que não deveria estar lá.

Por que eu posso querer fazer assim? Bem, eu posso querer que os threads acumulem as strings no meu result sem considerar a ordem, ou na ordem em que os threads entram. Talvez seja um logger, quem sabe?

De qualquer forma, para consertar isso, eu coloquei uma declaração lock em torno das entranhas do método.

public class Concatenate
{
    private StringBuilder result = new StringBuilder();
    bool isFirst = false;
    private static object locker = new object();

    public string AppendWithCommas(ImmutableList<string> list)
    {
        lock (locker)
        {
            foreach (string s in list)
            {
                if (isFirst)
                    result.Append(s);
                else
                    result.Append(", " + s);
            }
            return result.ToString();
        }
    } 
}

Agora é seguro para threads novamente.

A única maneira que meus métodos imutáveis poderiam falhar em ser thread-safe é se o método de alguma forma vazar parte de sua implementação. Isso poderia acontecer? Não se o compilador estiver correto e o programa estiver correto. Eu sempre precisarei de bloqueios em tais métodos? Não.

Para ver um exemplo de como a implementação pode vazar em um cenário de simultaneidade, veja aqui .

    
por 25.10.2012 / 06:25
fonte
3

Não tenho certeza se entendi suas perguntas.

IMHO a resposta é sim. Se todos os seus objetos são imutáveis, você não precisa de nenhum bloqueio. Mas se você precisar preservar um estado (por exemplo, implementar um banco de dados ou precisar agregar os resultados de vários segmentos), precisará usar a mutabilidade e, portanto, também bloquear. A imutabilidade elimina a necessidade de bloqueios, mas geralmente você não pode se dar ao luxo de ter aplicativos completamente imutáveis.

Responda à parte 2 - os bloqueios devem ser sempre mais lentos do que sem bloqueios.

    
por 24.10.2012 / 23:03
fonte
3

Você começa com

Claramente imutabilidade minimiza a necessidade de bloqueios na programação multi-processador

Errado. Você precisa ler atentamente a documentação para cada classe que você usa. Por exemplo, const std :: string em C ++ é não thread safe. Objetos imutáveis podem ter um estado interno que muda ao acessá-los.

Mas você está vendo isso de um ponto de vista totalmente errado. Não importa se um objeto é imutável ou não, o que importa é se você o altera. O que você está dizendo é como dizer "se você nunca fizer um exame de direção, nunca poderá perder sua carta de condução por dirigir embriagado". É verdade, mas falta o ponto.

Agora, no código de exemplo que alguém escreveu com uma função chamada "ConcatenateWithCommas": Se a entrada fosse mutável e você usasse um bloqueio, o que você ganharia? Se alguém tentar modificar a lista enquanto você tenta concatenar as seqüências de caracteres, um bloqueio pode impedi-lo de travar. Mas você ainda não sabe se concatena as strings antes ou depois que as outras threads as alteraram. Então seu resultado é um tanto inútil. Você tem um problema que não está relacionado ao bloqueio e não pode ser corrigido com bloqueio. Mas se você usar objetos imutáveis, e o outro thread substituir o objeto inteiro por um novo, você está usando o objeto antigo e não o novo, então seu resultado é inútil. Você tem que pensar sobre esses problemas em um nível funcional real.

    
por 18.03.2014 / 09:40
fonte
2

Encapsular um grupo de estados relacionados em uma única referência mutável a um objeto imutável pode possibilitar que vários tipos de modificação de estado sejam executados sem bloqueio usando o padrão:

do
{
   oldState = someObject.State;
   newState = oldState.WithSomeChanges();
} while (Interlocked.CompareExchange(ref someObject.State, newState, oldState) != oldState;

Se dois threads tentarem atualizar someObject.state simultaneamente, os dois objetos lerão o estado antigo e determinarão qual seria o novo estado sem as alterações um do outro. O primeiro thread para executar o CompareExchange armazenará o que acha que o próximo estado deve ser. O segundo segmento descobrirá que o estado não corresponde mais ao que foi lido anteriormente e, portanto, recalculará o próximo estado apropriado do sistema com as alterações do primeiro thread em vigor.

Esse padrão tem a vantagem de que um encadeamento que fica bloqueado não pode bloquear o progresso de outros encadeamentos. Tem a vantagem adicional de que, mesmo quando há contenção pesada, algum segmento sempre estará progredindo. Tem a desvantagem, no entanto, que na presença de contenção muitos segmentos podem gastar muito tempo fazendo trabalhos que acabarão descartando. Por exemplo, se 30 encadeamentos em CPUs separadas tentarem alterar um objeto simultaneamente, o primeiro será bem-sucedido em sua primeira tentativa, um em seu segundo, um em seu terceiro, etc., de modo que cada encadeamento fique em média fazendo cerca de 15 tentativas para atualizar seus dados. Usar um bloqueio "consultivo" pode melhorar significativamente as coisas: antes que um thread tente uma atualização, ele deve verificar se um indicador de "contenção" está definido. Se assim for, deve adquirir um bloqueio antes de fazer a atualização. Se um encadeamento fizer algumas tentativas malsucedidas de uma atualização, ele deverá definir o sinalizador de contenção. Se um encadeamento que tentar adquirir o bloqueio descobrir que não havia mais ninguém esperando, ele deverá limpar o sinalizador de contenção. Note que o bloqueio aqui não é necessário para "correção"; código funcionaria corretamente, mesmo sem ele. O objetivo do bloqueio é minimizar a quantidade de tempo gasto em operações que provavelmente não serão bem-sucedidas.

    
por 28.12.2013 / 19:53
fonte