Como você implementar Software Transactional memória?

Question

Em termos de instruções atômicas actual nível baixo e cercas de memória (I supor que eles são usados), como você implementar STM?

A parte que é misterioso para mim é que dado algum pedaço arbitrária de código, você precisa encontrar uma maneira de voltar depois e determinar se os valores utilizados em cada passo eram válidos. Como você faz isso, e como você faz isso de forma eficiente? Isso também parecem sugerir que a solução como qualquer outro 'bloqueio' você quer manter suas seções críticas tão pequeno quanto possível (para diminuir a probabilidade de um conflito), estou certo?

Além disso, pode STM simplesmente detectar "outro segmento entrou nesta área, enquanto a computação estava sendo executado, portanto, o cálculo é inválido" ou pode realmente detectar se os valores derrotei foram utilizadas (e, portanto, por sorte, por vezes, dois segmentos podem executar a mesma crítica seção simultaneamente, sem necessidade de reversão)?

Answer 1

A resposta mais simples é "depende". Há toneladas de radicalmente diferentes implementações de trabalho em praticamente qualquer forma imaginável.

A parte que é misterioso para mim é que dado algum pedaço arbitrária de código, você precisa encontrar uma maneira de voltar depois e determinar se os valores utilizados em cada passo eram válidos. Como você faz isso, e como você faz isso de forma eficiente?

Uma solução é usar o controle de versão. Cada vez que um objeto é modificado, seu número de versão é atualizado. Enquanto a transação está em execução, você validar a versão de cada objeto acessado, e quando os commits transação, você verificar que os objetos são ainda válido. Esta validação pode ser uma simples comparação inteiro (se transaction_start_version >= object_version, o objeto é válido), por isso pode ser feito com bastante eficiência.

Isso também parece sugerir que, assim como qualquer outra solução 'bloqueio' você quer manter suas seções críticas tão pequeno quanto possível (para diminuir a probabilidade de um conflito), estou certo?

Muito provável. Eu acho que algumas implementações de ter ido a rota de assumindo / requerendo tudo para ser uma transação, mas pedaços sim, na maioria das implementações, as transações são especialmente marcadas de código, e quanto mais tempo uma transação é executado, o maior a possibilidade de um conflito que pode causar transações para reverter.

Além disso, pode STM simplesmente detectar "outro segmento entrou nesta área, enquanto a computação estava sendo executado, portanto, o cálculo é inválido" ou pode realmente detectar se os valores derrotei foram utilizadas (e, portanto, por sorte, por vezes, dois segmentos podem executar a mesma crítica seção simultaneamente, sem necessidade de reversão)?

Este último. Tenha em mente que a idéia na TM é proteger dados , em vez de código .

caminhos de código diferentes podem acessar a mesma variável em diferentes transações. Isto tem de ser detectado pelo sistema de TM. Não há nenhuma noção real de "nessa área", uma vez que se refere ao código, em vez de dados. O sistema de TM não se importa com o que o código está sendo executado, ele controla os dados que está sendo modificado. Dessa forma, ele difere totalmente de seções críticas (qual o código de proteção, em vez de dados)

Answer 2

Alguns papéis podem ser realmente difícil de ler, mas dois que são muito clara e concisa são:

transacional Locking II, Dave Dice, Ori Shalev, Nir Shavit que descreve o "TL2" algoritmo STM em termos de qualquer idioma.

Deuce: não invasiva Software Transactional Memória em Java, Guy Korland, Nir Shavit, Pascal Felber que explica um transformador classe tempo de carregamento que transforma classes Java regulares em classes na memória que têm bytecode adicional para fazer STM. Isso é relevante para a questão do papel explica como código sem STM pode ser mecanicamente transformada em código que está fazendo STM em qualquer linguagem OO.

O quadro Deuce permite que você plug-in do algoritmo real que você deseja usar; incluindo o algoritmo TL2. Como o quadro Deuce é Java a seguinte terminologia de discussão usa Java, mas apenas está assumindo que você está escrevendo em uma linguagem OO.

A seguir irá delinear a abordagem TL2. Os papéis têm links para abordagens alternativas, mas estudando um algoritmo responde a um monte de perguntas.

Como você implementar STM? A parte que é misterioso para mim é que dado algum pedaço arbitrária de código, você precisa encontrar uma maneira de voltar depois e determinar se os valores utilizados em cada passo eram válidos.

Uma resposta curta para como TL2 não STM é "contabilidade" e depois usando apenas bloqueios de escrita no tempo de confirmação. Leia o documento para o detalhe muito bem, mas um esboço escova de bordo é a seguinte. Cada propriedade que você pode usar no código original teria um getter e setter. No código transformado haveria também um número de versão do imóvel e adicional de código adicionado ao getter e setter. Você precisa registrar a versão de cada atributo que você lê dentro da transação que a transação "read-set". Você pode fazer isso por ter todos os getter adicionar a versão do atributo visto em um LinkedList ThreadLocal. Você também precisa amortecer os escreve como o "write-set" em um ThreadLocal até que você cometeu. Note-se que os métodos getter precisa verificar e retornar um valor write-set ThreadLocal para um determinado campo, se você tiver um. Dessa forma, você ver as suas gravações confirmadas em suas leituras, mas nenhum outro segmento está indo para vê-los até que você cometeu.

Ao dedicar tempo você tomar bloqueios de escrita contra todos os atributos que você está prestes a escrever. Enquanto você tem as fechaduras você verifique que a sua leitura conjunto ainda é válido; que os atributos que você lê em sua transação não foram atualizados para uma versão superior por outra transação. Se sim, então sua lógica de negócios pode não ser válida como você pode ter inconsistente lê então você precisa para reverter toda a transação. Se as verificações finais passar depois de se comprometer por liberando o seu write-set, bata as versões desses atributos, liberar os bloqueios de escrita, e última tanto o write-conjunto claro e leitura definir listas ThreadLocal.

O documento explica que o algoritmo pode abortar cedo se detectar que um ser leitura atributo foi escrito para uma vez que o tx começou. O papel tem alguns truques para acelerar as operações somente leitura. Ele ainda tem um truque para descobrir quais blocos são somente leitura e que são de leitura e escrita. Qualquer pessoa expressando interesse em tais coisas realmente deve aproveitar os dois papéis.

O quadro Deuce no documento acima mostra como alterar todos os seus getters e setters, injetando novo bytecode Java em suas classes no tempo de carregamento. Outros idiomas podem ter um compilador especial ou pré-processador que realizam a mesma transformação mecânica de código normal em STM habilitado código. Especificamente com Deuce seus objetos de código-fonte pode ter pares getter setter simples mas classes transformada em tempo de execução tem setters getter enriquecidos que fazem o bookwork.

Transformar i código regularescódigo STM nto (particularmente em tempo de execução) é interessante, mas se você precisa realmente escrever um STM habilitado estrutura de dados que você não precisa de nenhum molho de magia. Ao invés de apenas criar uma classe Ref com um get() e uma set(x) e fazer todo relacionamento único entre seus objetos de estrutura de dados composta de alças Ref. No get e set de sua classe Ref você pode fazer o bookwork ThreadLocal. Depois, você pode implementar uma versão simples do "TL2" ou qualquer outro algoritmo que funciona bem para as suas estruturas de dados e sua simultaneidade de leitura contra gravação.

Isso também parece sugerir que, assim como qualquer outro 'bloqueio' solução que você deseja manter suas seções críticas tão pequeno quanto possível (Para diminuir a probabilidade de um conflito), estou certo?

TL2 tem um período crítico em manter os bloqueios de escrita, em seguida, fazer verificações finais e escreve o que é fácil de compreender e otimizar sem qualquer compreensão da lógica de negócios do aplicativo. Se você atribuir cada número uma propriedade única que você pode trivialmente evitar impasse tomando bloqueios em ordem crescente. É importante notar que toda a lógica o seu negócio é feito especulativamente assumindo que a cometer cheques vai passar. Você não mantém bloqueios enquanto você está fazendo lógica de negócios lento arbitrária. Você pode estar fazendo várias pesquisas de serviços web ou chamadas de banco de dados lentas e você não terá quaisquer bloqueios até que o cometem. Claramente os profissionais estão indo para sintonizar o Parreira fora da seção crítica genérica.

O documento deixa claro que o algoritmo pode ser abortar mais frequentemente que a lógica de negócios específica requer. O algoritmo genérico não sabe se suja específica lê não iria afetar o resultado real de gravação. lógica manuscrita que entende a lógica de negócio real poderia saber casos especiais, quando a reversão não é necessário para uma dada conjuntos de leituras sujas. Se, no entanto você tem um monte de código para escrever e uma aplicação onde a probabilidade de reversão é muito baixa uma abordagem STM mecânica genérica pode levar a menos erros e um bom desempenho.

Além disso, pode STM simplesmente detectar "outro segmento entrou nesta área enquanto o cálculo estava sendo executado, portanto, o cálculo é inválido" ou pode, na verdade, detectar se valores clobbered foram utilizados (e assim por sorte, por vezes, dois segmentos podem executar a mesma seção crítica simultaneamente, sem necessidade de reversão)?

A abordagem TL2 como tudo sobre os dados lidos ou não escrito sobre o código que faz isso. É o que você ganha e conjunto e que as contagens; e se qualquer outro trod fio em seus dedos antes de liberar todas as gravações. Tudo que é necessário do código é que você tem um begin(), commit() e rollback() na lógica de negócios para início, fim e abortar a transação. Mesmo que pode ser gerado código. Com Java você pode marcar seus métodos com a anotação @Transactional em métodos, em seguida, gerar o código que envolva seus invocações de método em um try / catch / finally que faz o begin / commit / rollback como java idiomic. Deuce injeta essa lógica em tempo de carregamento de classe.

Mais uma vez você não precisa de tais molho mágico para começar / commit / rollback em seu próprio STM habilitado estruturas de dados. Pode ser explícito e colocar em tudo o que a direita em seu código da lógica de estrutura de dados para criar o seu próprio explicitamente STM habilitado aulas em qualquer linguagem OO.

Answer 3

GHC 's implementação STM é descrito na secção seis:

Composable memória . Tim Harris, Simon Marlow, Simon Jones Peyton, Maurice Herlihy. PPoPP'05: ACM Symposium SIGPLAN sobre os Princípios e Prática de Programação Paralela, Chicago, Illinois, Junho de 2005

E seção cinco de:

transacional de memória com invariantes de dados . Tim Harris, Simon Peyton-Jones. Março 2006 TRANSACT '06

Answer 4

Eu sugiro que você assistir a esta apresentação: http: // www. infoq.com/presentations/Value-Identity-State-Rich-Hickey

Na segunda metade explica como atualizar valores sem deixá-los em um estado indefinido. Por exemplo - se você tem uma árvore que você deseja atualizar no STM-style você não mudar a versão anterior em tudo. Digamos que tree é um ponteiro para a raiz da árvore. A única coisa que você cria é os nós que mudou (mas eles podem referir-se a nós no instantâneo original da árvore.

Então você faz um-and-swap comparar no ponteiro tree. Se ele conseguiu, então todo mundo vai ver agora a sua nova árvore e o antigo pode ser coletado como lixo. Se não tem, então você repetir o processo e a árvore que você simplesmente construído é lixo coletado.

A grande idéia é que você não precisa para detectar se alguém mudou a tree até que você realmente trocar os valores novos e antigos, para que não haja "conflitos" ou "valores derrotei" da programação típica de vários segmentos.

Answer 5

Se você está indo com .NET framework,

Você pode verificar este experimental

• .NET 4.0 STM.Net
  
• .NET rochas podcast sobre STM.Net: Dana Groff e Yossi Levanoni Discussão STM