Eu acho que um fato bem conhecido no mundo da programação é que o padrão singleton (double-checked) em java não é thread safe e que não pode ser arrumado. Aqui está um artigo triplo([1], [2] e [3]) que explica o porquê. Esses artigos oferecem implementações particulares do padrão singleton e uma explicação bem detalhada de como estas implementações podem ser quebradas, e conclui com uma sentença geral.
É válido mencionar que no trabalho “The ‘Double-Checked Locking is Broken’ Declaration” [4], escrito entre outros por Jeremy Manson e Bill Pugh (autores do modelo de memória do Java 1.5), os autores sugeriram uma solução para o problema no padrão singleton double-checked no Java 1.5 (a parte “Fixing Double-Checked Locking using Volatile”).
Qualquer discussão sobre sincronização em Java precisamos considerar uma extensa e uma otimização em java não muito bem definida. O livro Java Language Specification Third Edition (JLS3) [5] comenta:
A especificação oferece uma grande liberdade para o implementador de realizar uma miríade de transformações no código, incluindo a reorganização de ações e remoção de sincronização desnecessária.
O propósito deste artigo é testar as “condições limites” da otimização de uma linguagem de programação. Esta tarefa requer uma abordagem fora do padrão, o qual vou tentar desenvolver aqui.
Qualquer oferta de construção de uma linguagem de programação de sincronização se baseia em um campo não muito bem definido uma vez que não é possível aplicar princípios gerais: o que é permitido e o que não é permitido com otimização. Minha idéia é demonstrar que se a otimização pode quebrar o código somente violando os princípios gerais aceitos, então tal otimização é impossível (ou pelo menos, incorreta). E se nós permanecermos nesta posição, nós podemos até fazer uma sentença sobre qualquer linguagem de programação, não necessariamente apenas o java. Realmente java utiliza sincronização primitiva, C# utiliza lock, C utiliza primitivos POSIX com Mutex, C++ também utiliza Mutex (em Win32 e Solaris), Python – lock, Ruby com Mutex novamente. A questão então é, nós podemos tentar generalizar por dedução sem pular para a conclusão a partir de exemplos específicos?
TO livro JLS3 utiliza a seguinte definição de semânticas intra-thread:
As semânticas para programas com uma única thread permitem uma previsão total do seu comportamento, baseado nos valores conhecidos por ações de leitura em uma thread. As ações para cada thread isolada devem se comportar conforme as regras ditadas pelas semânticas daquela thread.
Nós vamos utilizar a definição mais fraca, conforme segue:
A implementação da linguagem de programação fornece o mínimo de semântica intra-thread (ITS mínimo) se qualquer tempo de compilação / otimização de tempo de execução mantém a semântica de um código não-otimizado em uma execução thread-única acima do nível de qualquer método. (Nós não incluímos os métodos internos aqui).
É fácil demonstrar se o ITS mínimo é quebrado no nível do método, que ele também pode ser quebrado no nível do programa.
Definição: A implementação da linguagem de programação fornece uma sincronização mínima se a sincronização primitiva da linguagem satisfazer as duas condições seguintes:
CS1: somente uma thread pode entrar em um bloco sincronizado
CS2: todas as variáveis compartilhadas por qualquer thread são alteradas da memória principal e salvas para a memória principal na saída de um bloco sincronizado
Definição: O método produz o efeito objeto-fantasma ao retornar uma referência para um objeto, se for possível com este método obter uma referência para um objeto que não foi totalmente construído.
Neste artigo eu investiguei a consistência relativa de uma implementação singleton (tirando uma folha de um livro de Lógica Matemática). Mais precisamente, eu vou tentar ilustrar a seguinte sentença:
A: Se a implementação da linguagem de programação fornece o mínimo ITS e o mínimo de sincronização, o uso do padrão gOracle(*), é consistente
Para este propósito vou tentar provar a seguinte sentença:
B: Se a implementação da linguagem de programação fornece o mínimo ITS e o mínimo de sincronização, o uso do padrão gOracle(*) não pode produzir o efeito objeto-fantasma.
A partir de agora vou partir para o contexto da linguagem de programação java, mas acredito que todo o conteúdo a seguir pode ser adaptado para qualquer linguagem listada abaixo.
Então o quê, quer dizer que é o padrão gOracle? Conforme o nome indica, vou apresentar um oracle, algo similar aos antigos oracles Gregos. Meu oracle vai ser um método com a assinatura static boolean oracle(int h) e uma qualidade muito especial – não tem jeito de um compilador java ou java runtime de prever o valor produzido por este método. Mas vou revelar para você um segredo – ele irá sempre produzir true, vou retornar mais tarde para questão de como construir um método como este, mas por enquanto, preciso assegurar para você que é fácil demais.
Então, segue minha implementação do singleton gOracle:
class Singleton {
static private Singleton instance = null;
static private boolean bInited = false;
private Singleton() {…}
public static Singleton getInstance() {
if (!bInited || instance==null) { // FIRST CHECK
synchronized (Singleton.class) {
if (!bInited) { // INNER IF-BLOCK, SECOND CHECK
instance = new Singleton();
int hash = instance.hashCode();
bInited = oracle(hash);
}
}
}
return instance;
}
static boolean oracle(int h) {…}
}
Agora vou iniciar a minha defesa do gOracle.
A idéia chave é demonstrar que se uma otimização em java resulta em um efeito objeto-fantasma para o método getInstance(), então que o ITS mínimo poderia ser quebrado. Seguindo uma linha, se a execução de um dado código otimizado em um single-thread poderia potencialmente produzir resultados diferentes do que a execução de um código não otimizado.
|
1. Vamos imaginar que a thread-i é a primeira a entrar no bloco sincronizado. Esta thread irá eventualmente mudar o valor da variável bInited, mesmo se inicialmente na memória local 2. Embora o compilador tenha a habilidade de transformar o código getInstance(), e o runtime tenha a habilidade de alterar a ordem de execução das operações, nenhuma otimização tem permissão de quebrar o mínimo ITS para a thread-i executada de maneira isolada 3. O resultado da chamada hash = instance.hashCode() é imprevisível antes da construção da instância do objeto. NOTA 1: De acordo com a API java, o padrão hashCode() é geralmente implementada convertendo o endereço interno do objeto para um inteiro. Mas se isto não for suficiente para se ter uma previsão, nós podemos considerar implementar o método hashCode() para o Singleton como
e então permitir o compilador ou em tempo de execução tentar prever durante ou antes do construtor o valor de Date.getTime() posicionado no código original após o construtor! 4. A chamada bInited = oracle(hash) utiliza o resultado da chamada instance.hashCode() e imprevisível, como supomos 5. Portanto, o compilador ou um runtime otimizado não pode atribuir o valor (true) da variável bInited antes da construção completa do objeto Singleton e atribuir as variáveis de instância na memória local da i-thread 6. Após a thread-i sair do bloco sincronizado e antes que qualquer outra thread entre neste bloco, os valores da instância e das variáveis bInited na memória principal serão atribuídos ao valor da thread-i da memória local. Ambas operações de atribuição são atômicas. 7. Agora considere o comportamento de qualquer outra thread, vamos chamá-la de thread-w, com mínimo de semântica ITS. O que significa que podemos assumir a ordem das execuções para a thread-w conforme especificada no código Singleton, mas as variáveis compartilhadas podem ter valores “inesperados”. Isto é o que veremos agora. Vamos utilizar a seguinte notação:
8.a. A thread-w aguarda no bloco sincronizado pela thread-i para sair do bloco – fácil. Primeiro a thread-i deixa o bloco sincronizado, depois o java sincroniza as variáveis locais da thread-i com a memória principal, I(bInited) => M(bInited) I(instance) => M(instance) então, na entrada da thread-w no bloco sincronizado, o java sincroniza as variáveis locais da thread-w a partir da memória principal, M(bInited) => W(bInited) M(instance) => W(instance) e agora a thread-w possui uma visão correta das variáveis compartilhadas, a mesma visão que a thread-i possui. 8.b. A thread-w está dentro ou antes da operação de PRIMEIRA CHECAGEM quando a thread-i sai do bloco sincronizado. Note, que W(bInited) e W(instância não são inicializadas a partir do memória principal nem antes e nem depois de I(bInited)e I(instância) serem sincronizados a M(bInited)e M(instância), o que acontece após a thread-t deixar o bloco sincronizado. Então cada W(bInited) and W(instância) pode somente ter um valor inicial (conforme definido na classe Singleton) ou o valor produzido pela thread-i, e qualquer combinação possível. Então primeiramente a thread-w verifica o valor da variável W(bInited). Por seu valor ser falso a thread-w pula para o bloco sincronizado, similar ao passo 7.a. Se W(bInited)==true, então a thread-i já atribuiu I(bInited)=true e o java já sincronizou toda a cadeia I(bInited) => M(bInited) => W(bInited) TPortanto, a thread-i já inicializou o objeto Singleton e no mínimo I(instância) já referencia o objeto. Agora, a thread-w verifica o valor da variável W(instância). Se W(instance)==null então o java ainda não sincronizou toda a cadeia I(instance) => M(instance) => W(instance) mas não se preocupe, a thread-w somente irá entrar no bloco sincronizado e descobrir o novo valor da variável de instância no local, como no passo 7.a. Mas se W(instance)=!null, então o único valor que W(instância)pode ter é o valor I(instância). Portanto, neste caso a thread-w irá retornar a instância totalmente construída do Singleton. 9. Então, para qualquer thread que obtenha a variável de instância pelo método getInstance() é garantido que o objeto Singleton já esteja criado e totalmente inicializado pela thread-i. |
Em outras palavras, a única maneira do compilador ou um runtime otimizado quebrar o padrão gOracle é também quebrando a única thread em execução no código (assumindo que nós temos um mínimo de sincronização). Isto prova (para java) a sentença B e ilustra a sentença A. Encerro aqui minha defesa.
Corolário: Qualquer implementação com o JDK 1.4 fornece o mínimo de ITS necessário, o padrão gOracle não pode produzir aqui o efeito objeto-fantasma.
Vamos retornar a questão de como encontrar um oracle para o gOracle. Que tal uma sentença matemática não-trivial, como:
- a soma de dois lados de um triângulo deve ser maior ou igual que o terceiro lado
- qualquer inteiro pode ser apresentado como um produto de números primos
nalisando a segunda sentença, vamos implementar nosso oracle como:
static boolean oracle(int hash) {
Random rand = new Random(Date.getTime());
int iNum = rand.nextInt() + hash;
iNum = iNum % 100; // optional line
if( found iNum presentation as product of primes )
return true
else
return false;
}
Se você concorda que os desenvolvedores de compilador não são Deuses ou Oracles ainda e não podem ensinar ao compilador ou a um runtime otimizado o uso do Fundamental theorem of arithmetic [6] ouos Axiomas da Geometria de Euclides em código java. Existe ainda, o Último Teorema de Fermat.
(*) Eu apresentei o nome “gOracle” para a minha implementação do padrão Singleton para expressar sua origem grega, a idéia de “prever o futuro” como ele era utilizado pelos antigos Gregos, não confundir com alguma produto da Oracle Corp.
Referências
1. Double-checked locking and the Singleton pattern, por peter Haggar
2. Double-checked locking: Clever, but broken, por Brian Goetz
3. Java theory and practice: Fixing the Java Memory Model por Brian Goetz
4. The "Double-Checked Locking is Broken" Declaration, por Jeremy Manson, Bill Pugh …
5. Java Language Specification, Third Edition