3.4.2 Mecanismos para Controlar Concorrência

Vimos que a dificuldade em lidar com threads concorrentes está enraizada na necessidade de considerar o intercalamento da ordem dos eventos nas diferentes threads. Por exemplo, suponha que temos duas threads, uma com três eventos ordenados $(a,b,c)$ e uma com três eventos ordenados $(x,y,z)$. Se as duas threads executam concorrentemente, sem restrições sobre como sua execução é intercalada, então há 20 ordenações diferentes possíveis para os eventos que são consistentes com as ordenações individuais para as duas threads:

$$\begin{array}{cccc} (a,b,c,x,y,z) & (a,x,b,y,c,z) & (x,a,b,c,y,z) & (x,a,y,z,b,c)\\ (a,b,x,c,y,z) & (a,x,b,y,z,c) & (x,a,b,y,c,z) & (x,y,a,b,c,z)\\ (a,b,x,y,c,z) & (a,x,y,b,c,z) & (x,a,b,y,z,c) & (x,y,a,b,z,c)\\ (a,b,x,y,z,c) & (a,x,y,b,z,c) & (x,a,y,b,c,z) & (x,y,a,z,b,c)\\ (a,x,b,c,y,z) & (a,x,y,z,b,c) & (x,a,y,b,z,c) & (x,y,z,a,b,c) \end{array}$$

Como programadores projetando este sistema, teríamos que considerar os efeitos de cada uma dessas 20 ordenações e verificar que cada comportamento é aceitável. Tal abordagem rapidamente se torna inviável à medida que os números de threads e eventos aumentam.

Uma abordagem mais prática para o projeto de sistemas concorrentes é desenvolver mecanismos gerais que nos permitem restringir o intercalamento de threads concorrentes de modo que possamos ter certeza de que o comportamento do programa está correto. Muitos mecanismos foram desenvolvidos para esse propósito. Nesta seção, descrevemos um deles, o serializador.

Serializando acesso ao estado compartilhado

A serialização implementa a seguinte ideia: Threads executarão concorrentemente, mas haverá certas coleções de funções que não podem ser executadas concorrentemente. Mais precisamente, a serialização cria conjuntos distinguidos de funções de tal forma que apenas uma execução de uma função em cada conjunto serializado é permitida acontecer por vez. Se alguma função no conjunto está sendo executada, então uma thread que tenta executar qualquer função no conjunto será forçada a esperar até que a primeira execução tenha terminado.

Podemos usar a serialização para controlar o acesso a variáveis compartilhadas. Por exemplo, se queremos atualizar uma variável compartilhada com base no valor anterior dessa variável, colocamos o acesso ao valor anterior da variável e a atribuição do novo valor à variável na mesma função. Então garantimos que nenhuma outra função que atribui à variável pode executar concorrentemente com esta função, serializando todas essas funções com o mesmo serializador. Isso garante que o valor da variável não pode ser mudado entre um acesso e a atribuição correspondente.

Serializadores

Para tornar o mecanismo acima mais concreto, suponha que tenhamos estendido JavaScript para incluir uma função chamada concurrent_execute:

concurrent_execute(f₁, f₂, …, fₖ)

Cada $f$ deve ser uma função sem argumentos. A função concurrent_execute cria uma thread separada para cada $f$, que aplica $f$ (sem argumentos). Essas threads todas executam concorrentemente.¹

Como um exemplo de como isso é usado, considere

let x = 10;

concurrent_execute(() => { x = x * x; },
                   () => { x = x + 1; });

Isso cria duas threads concorrentes—$T_1$, que define x para x vezes x, e $T_2$, que incrementa x. Após a execução estar completa, x será deixado com um dos cinco valores possíveis, dependendo do intercalamento dos eventos de $T_1$ e $T_2$:

101:	$T_1$ define x para 100 e então $T_2$ incrementa x para 101.
121:	$T_2$ incrementa x para 11 e então $T_1$ define x para x vezes x.
110:	$T_2$ muda x de 10 para 11 entre as duas vezes que $T_1$ acessa o valor de x durante a avaliação de x * x.
11:	$T_2$ acessa x, então $T_1$ define x para 100, então $T_2$ define x.
100:	$T_1$ acessa x (duas vezes), então $T_2$ define x para 11, então $T_1$ define x.

Podemos restringir a concorrência usando funções serializadas, que são criadas por serializadores. Serializadores são construídos por make_serializer, cuja implementação é dada abaixo. Um serializador recebe uma função como argumento e retorna uma função serializada que se comporta como a função original. Todas as chamadas a um dado serializador retornam funções serializadas no mesmo conjunto.

Assim, em contraste com o exemplo acima, executar

let x = 10;

const s = make_serializer();

concurrent_execute(s(() => { x = x * x; }),
                   s(() => { x = x + 1; }));

pode produzir apenas dois valores possíveis para x, 101 ou 121. As outras possibilidades são eliminadas, porque a execução de $T_1$ e $T_2$ não pode ser intercalada.

Aqui está uma versão da função make_account da seção 3.1.1, onde os depósitos e saques foram serializados:

function make_account(balance) {
    function withdraw(amount) {
        if (balance > amount) {
            balance = balance - amount;
            return balance;
        } else {
            return "Insufficient funds";
        }
    }
    function deposit(amount) {
        balance = balance + amount;
        return balance;
    }
    const protect = make_serializer();
    function dispatch(m) {
        return m === "withdraw"
               ? protect(withdraw)
               : m === "deposit"
               ? protect(deposit)
               : m === "balance"
               ? balance
               : error(m, "unknown request -- make_account");
    }
    return dispatch;
}

Com esta implementação, duas threads não podem estar sacando ou depositando em uma única conta concorrentemente. Isso elimina a fonte do erro ilustrado na Figura 3.29, onde Peter muda o saldo da conta entre os momentos em que Paul acessa o saldo para calcular o novo valor e quando Paul realmente executa a atribuição. Por outro lado, cada conta tem seu próprio serializador, então que depósitos e saques para diferentes contas podem prosseguir concorrentemente.

Exercício 3.39

Quais das cinco possibilidades na execução concorrente mostrada acima permanecem se em vez disso serializamos a execução da seguinte forma:

let x = 10;

const s = make_serializer();

concurrent_execute(  () => { x = s(() => x * x)(); },
                   s(() => { x = x + 1;             }));

💡 Mostrar solução — tente primeiro!💡 Esconder solução

Serializar x * x e serializar x = x + 1 não os coloca no mesmo pacote de exclusão: repare que só a leitura dupla de x * x está protegida (e a atribuição de x ficou fora do s(...) na primeira thread). Das cinco possibilidades do texto restam três:

• 101: o quadrado (100) é escrito, depois o incremento → 101.
• 121: o incremento acontece antes → 11² = 121.
• 100: a primeira thread lê x * x = 100, o incremento inteiro se intercala antes da escrita de x (que ficou fora do serializador), e o 100 sobrescreve o 11.

Eliminadas ficam as intercalações que dependiam de ler x entre os dois acessos de x * x (que davam 110 e 11) — é exatamente isso que s(() => x * x) agora impede.

Resolvi o exercício 3.39

Exercício 3.40

Dê todos os valores possíveis de x que podem resultar da execução de

let x = 10;

concurrent_execute(() => { x = x * x; },
                   () => { x = x * x * x; });

Quais dessas possibilidades permanecem se em vez disso usamos funções serializadas:

let x = 10;

const s = make_serializer();

concurrent_execute(s(() => { x = x * x;     }),
                   s(() => { x = x * x * x; }));

💡 Mostrar solução — tente primeiro!💡 Esconder solução

Sem serialização, cada execução é ler → ler → … → escrever e as intercalações produzem: 1.000.000 (qualquer ordem sequencial), 100 ($10^2$, com a escrita do cubo perdida), 1.000 ($10^3$, com a do quadrado perdida), 10.000 ($100^2$: o cubo leu um 10 e um 100…), 100.000 ($10\cdot100^2$ etc. — leituras mistas do cubo com valores antigo e novo).

Ao todo: 100, 1.000, 10.000, 100.000 e 1.000.000.

Com as duas funções serializadas pelo mesmo serializador, as execuções não se intercalam: as duas ordens sequenciais dão o mesmo resultado, e sobra apenas 1.000.000.

Resolvi o exercício 3.40

Exercício 3.41

Ben Bitdiddle se preocupa que seria melhor implementar a conta bancária da seguinte forma (onde a linha comentada foi mudada):

function make_account(balance) {
    function withdraw(amount) {
        if (balance > amount) {
            balance = balance - amount;
            return balance;
        } else {
            return "Insufficient funds";
        }
    }
    function deposit(amount) {
        balance = balance + amount;
        return balance;
    }
    const protect = make_serializer();
    function dispatch(m) {
        return m === "withdraw"
               ? protect(withdraw)
               : m === "deposit"
               ? protect(deposit)
               : m === "balance"
               ? protect(() => balance)(undefined) // serialized
               : error(m, "unknown request -- make_account");
    }
    return dispatch;
}

porque permitir acesso não serializado ao saldo bancário pode resultar em comportamento anômalo. Você concorda? Há algum cenário que demonstra a preocupação de Ben?

💡 Mostrar solução — tente primeiro!💡 Esconder solução

A preocupação de Ben é desnecessária — a versão sem proteção se comporta igual.

Consultar o saldo é uma única leitura da variável balance, e leituras individuais são atômicas no nosso modelo: não existe "meio de uma leitura" para outra thread se intercalar. Qualquer execução concorrente com a consulta desprotegida corresponde a lê-la ou antes ou depois de cada operação serializada — e esses dois resultados já eram possíveis com a versão de Ben (a serialização apenas escolheria um deles). Não há estado intermediário observável, porque withdraw e deposit fazem sua única escrita em balance de uma vez.

A proteção seria necessária se a consulta fizesse duas leituras relacionadas (como a exchange faz com dois saldos) — aí sim um valor inconsistente "do meio" poderia ser observado.

Resolvi o exercício 3.41

Exercício 3.42

Ben Bitdiddle sugere que é um desperdício de tempo criar uma nova função serializada em resposta a cada mensagem withdraw e deposit. Ele diz que make_account poderia ser mudada para que as chamadas a protect sejam feitas fora da função dispatch. Isto é, uma conta retornaria a mesma função serializada (que foi criada ao mesmo tempo que a conta) cada vez que for solicitada uma função de saque.

function make_account(balance) {
    function withdraw(amount) {
        if (balance > amount) {
            balance = balance - amount;
            return balance;
        } else {
            return "Insufficient funds";
        }
    }
    function deposit(amount) {
        balance = balance + amount;
        return balance;
    }
    const protect = make_serializer();
    const protect_withdraw = protect(withdraw);
    const protect_deposit = protect(deposit);
    function dispatch(m) {
        return m === "withdraw"
               ? protect_withdraw
               : m === "deposit"
               ? protect_deposit
               : m === "balance"
               ? balance
               : error(m, "unknown request -- make_account");
    }
    return dispatch;
}

Esta é uma mudança segura para fazer? Em particular, há alguma diferença na concorrência que é permitida por essas duas versões de make_account?

Complexidade de usar múltiplos recursos compartilhados

Serializadores fornecem uma abstração poderosa que ajuda a isolar as complexidades de programas concorrentes para que possam ser tratadas cuidadosamente e (esperançosamente) corretamente. No entanto, embora usar serializadores seja relativamente direto quando há apenas um único recurso compartilhado (como uma única conta bancária), a programação concorrente pode ser traiçoeiramente difícil quando há múltiplos recursos compartilhados.

Para ilustrar uma das dificuldades que podem surgir, suponha que desejamos trocar os saldos em duas contas bancárias. Acessamos cada conta para encontrar o saldo, calculamos a diferença entre os saldos, sacamos essa diferença de uma conta e a depositamos na outra conta. Poderíamos implementar isso da seguinte forma:²

function exchange(account1, account2) {
    const difference = account1("balance") - account2("balance");
    account1("withdraw")(difference);
    account2("deposit")(difference);
}

Esta função funciona bem quando apenas uma única thread está tentando fazer a troca. Suponha, no entanto, que Peter e Paul ambos tenham acesso às contas $a_1$, $a_2$ e $a_3$, e que Peter troque $a_1$ e $a_2$ enquanto Paul concorrentemente troca $a_1$ e $a_3$. Mesmo com depósitos e saques em contas individuais serializados para correção (como no exemplo de make_account dado acima), exchange pode produzir ainda resultados incorretos. Por exemplo, Peter pode calcular a diferença nos saldos para $a_1$ e $a_2$, mas então Paul pode mudar o saldo em $a_1$ antes que Peter seja capaz de completar a troca.³ Para uma versão correta de exchange, devemos arranjar que as threads de Peter e Paul executem a função exchange mutuamente exclusivamente—por exemplo, usando um serializador:

function serialized_exchange(account1, account2) {
    const serializer1 = account1("serializer");
    const serializer2 = account2("serializer");
    serializer1(serializer2(exchange))(account1, account2);
}

Aqui adicionamos a seguinte cláusula à função dispatch de make_account:⁴

m === "serializer"
? protect
:

💡 Mostrar solução — tente primeiro!💡 Esconder solução

Ben está enganado quanto à necessidade, mas a mudança dele é segura — e a preocupação inversa (de que algo se perca) não se concretiza.

Na versão original, cada mensagem cria protect(withdraw) de novo; na de Ben, as versões protegidas protected_withdraw e protected_deposit são criadas uma única vez. O que garante a exclusão mútua não é qual embrulho serializado se executa, e sim qual serializador ele usa — e nas duas versões todas as operações da conta passam pelo mesmo serializador daquela conta. O conjunto de intercalações permitidas é, portanto, o mesmo: nunca duas operações da mesma conta ao mesmo tempo.

A diferença é só de eficiência (menos criação de objetos-função por mensagem). É uma mudança segura.

Resolvi o exercício 3.42

Exercício 3.43

Suponha que os saldos em três contas comecem em $10,$20 e $30, e que múltiplas trocas de saldos de conta sejam executadas concorrentemente. Argumente que se os processos são executados sequencialmente, após qualquer número de trocas concorrentes, os saldos de conta devem ser$10, $20 e$30 em alguma ordem. Desenhe um diagrama de temporização como o da Figura 3.29 para mostrar como este requisito pode ser violado se a função exchange for usada sem serializar as transações em contas individuais. Por outro lado, argumente que mesmo com essa troca incorreta, a soma dos saldos nas contas será preservada. Desenhe um diagrama de temporização para mostrar como mesmo esta condição seria violada se não serializarmos as transações em contas individuais.

💡 Mostrar solução — tente primeiro!💡 Esconder solução

Sequencial preserva o conjunto 30. Cada exchange troca os saldos de duas contas — uma permutação dos três valores. Composição de permutações é permutação; por indução, após qualquer número de trocas os saldos são 10, 20 e 30 em alguma ordem.

Só serializar contas individuais quebra isso. exchange calcula difference com leituras e depois faz o saque e o depósito como transações separadas. Intercalando duas trocas — digamos, troca A↔B (diferença $-10$) e troca A↔C (diferença $-20$) calculadas ambas sobre os saldos originais — as quatro operações serializadas executam sobre estados que já mudaram, e pode-se terminar, por exemplo, com contas em 20, 20 e 20: valores que não são permutação de 30. (Diagrama: as duas leituras de diferença acontecem antes de qualquer escrita; depois as quatro escritas se aplicam em qualquer ordem.)

Mas a soma se preserva mesmo assim: cada exchange executa exatamente um withdraw(d) e um deposit(d) com o mesmo d, e cada uma dessas operações, sendo serializada na sua conta, soma-se corretamente — o total muda $-d + d = 0$.

Sem serializar nem as contas individuais, até a soma cai: um deposit e um withdraw concorrentes na mesma conta podem ambos ler o mesmo saldo e uma escrita engolir a outra — dinheiro criado ou destruído. (Diagrama: duas leituras do mesmo balance seguidas de duas escritas.)

Resolvi o exercício 3.43

Exercício 3.44

Considere o problema de transferir uma quantia de uma conta para outra. Ben Bitdiddle afirma que isso pode ser realizado com a seguinte função, mesmo que múltiplas pessoas estejam concorrentemente transferindo dinheiro entre múltiplas contas, usando qualquer mecanismo de conta que serialize depósito e saque transações, por exemplo, a versão de make_account na parte do texto acima dos exercícios.

function transfer(from_account, to_account, amount) {
    from_account("withdraw")(amount);
    to_account("deposit")(amount);
}

Louis Reasoner afirma que há um problema aqui, e que precisamos usar uma versão serializada mais elaborada, como a função serialized_exchange. Ben está certo ou Louis está certo? Explique sua resposta.

💡 Mostrar solução — tente primeiro!💡 Esconder solução

Ben está certo desta vez — para transferências, o problema da troca não existe.

A diferença essencial: exchange primeiro observa os dois saldos (para calcular a diferença) e depois age com base na observação — entre observar e agir, o mundo pode mudar. transfer não observa nada: a quantia é um dado de entrada. O withdraw serializado debita amount corretamente não importa o que aconteça em volta, e o deposit serializado credita amount corretamente. Transferências concorrentes se intercalam entre essas duas operações à vontade, mas cada centavo sai de uma conta e entra na outra exatamente uma vez.

O que pode acontecer é um estado transitório em que o dinheiro saiu de uma conta e ainda não entrou na outra — a soma instantânea observável fica temporariamente menor. Para a correção final das contas, isso é inofensivo.

Resolvi o exercício 3.44

Exercício 3.45

Louis Reasoner pensa que nossa abordagem de reescrever a função exchange de modo que ela chame serialized_exchange é excessivamente complicada. Em vez de proteger transações individuais contra execução simultânea usando serializadores individuais, ele sugere que simplesmente fazemos a serialização da exchange em si, usando um serializador que serializa todos os depósitos e saques em contas individuais. Ele propõe redefinir make_account da seguinte forma, onde o corpo da função dispatch é idêntico àquele mostrado acima (incluindo a resposta ao exercício 3.42):

function make_account_and_serializer(balance) {
    function withdraw(amount) {
        if (balance >= amount) {
            balance = balance - amount;
            return balance;
        } else {
            return "Insufficient funds";
        }
    }
    function deposit(amount) {
        balance = balance + amount;
        return balance;
    }
    const balance_serializer = make_serializer();
    return m => m === "withdraw"
                ? balance_serializer(withdraw)
                : m === "deposit"
                ? balance_serializer(deposit)
                : m === "balance"
                ? balance
                : m === "serializer"
                ? balance_serializer
                : error(m, "unknown request -- make_account");
}

Então os depósitos são manipulados como na versão original de make_account:

function deposit(account, amount) {
    const d = account("withdraw");
    return d(amount);
}

e, de acordo com Louis, exchange é escrita da seguinte forma:

function exchange(account1, account2) {
    const difference = account1("balance") - account2("balance");
    account1("withdraw")(difference);
    account2("deposit")(difference);
}

e a própria exchange é serializada assim:

function serialized_exchange(account1, account2) {
    const serializer1 = account1("serializer");
    const serializer2 = account2("serializer");
    serializer1(serializer2(exchange))(account1, account2);
}

Qual é o problema com essa abordagem? (Dica: você pode querer considerar o que acontece quando serialized_exchange é chamada.)

Implementando serializadores

Implementamos serializadores em termos de uma primitiva mais primitiva de sincronização chamada mutex. Um mutex é um objeto que suporta duas operações—o mutex pode ser adquirido, e o mutex pode ser liberado. Uma vez que um mutex foi adquirido, nenhuma operação de aquisição nesse mutex pode prosseguir até que o mutex seja liberado.⁵ Em nossa implementação, cada serializador tem um mutex associado. Dado uma função f, o serializador retorna uma função que adquire o mutex, executa f, e então libera o mutex. Isso garante que apenas uma das funções produzidas por um serializador pode estar executando por vez, que é exatamente a propriedade de serialização que precisamos garantir.

function make_serializer() {
    const mutex = make_mutex();
    return f => {
               function serialized_f(...args) {
                   mutex("acquire");
                   const val = f(...args);
                   mutex("release");
                   return val;
               }
               return serialized_f;
           };
}

O mutex é um objeto mutável (aqui usaremos uma função de um argumento) que suporta duas operações: a mensagem "acquire" e a mensagem "release". Adquirir o mutex verifica para ver se o mutex está atualmente em uso. Se não estiver, o mutex é adquirido marcando-o como em uso; caso contrário, "acquire" espera até que o mutex seja liberado, e então tenta adquiri-lo novamente (recursivamente). Liberar o mutex marca-o como não em uso.

function make_mutex() {
    let in_use = false;
    return m => {
               if (m === "acquire") {
                   if (in_use) {
                       make_mutex()("acquire"); // retry
                   } else {
                       in_use = true;
                   }
               } else if (m === "release") {
                   in_use = false;
               }
           };
}

make_mutex usa a instrução if de JavaScript para verificar e definir a variável in_use. Infelizmente, isso não é uma solução adequada, porque há uma sutil corrida envolvida.

A condição de teste no if de "acquire" consiste em verificar o valor da variável in_use e então definindo in_use para true se ela for false. Se houver duas threads tentando adquirir o mesmo mutex simultaneamente, pode acontecer que ambas as threads leiam in_use como false, e ambas então definam in_use para true, permitindo que ambas prossigam. Uma maneira de evitar este problema é usar um mecanismo de hardware chamado test-and-set. A operação test-and-set testa o conteúdo de uma célula de memória, retorna o conteúdo dessa célula de memória, e então, se o teste foi bem-sucedido, modifica o conteúdo da célula de memória. Suporemos que o JavaScript fornece tal operação, na forma de uma função test_and_set que verifica uma célula de memória representada como uma caixa contendo um booleano. test_and_set retorna o valor da caixa. Além disso, se o valor era false, test_and_set define o conteúdo da caixa para true antes de retornar false; caso contrário, deixa a caixa inalterada. A operação test_and_set é realizada atomicamente, o que significa que nenhuma outra operação pode intercalar com ela durante sua execução. Para implementar mutexes com test_and_set, precisamos de caixas, que podemos construir como pares:

function make_box(value) {
    return pair(value, null);
}
function get_content(box) {
    return head(box);
}
function set_content(box, value) {
    set_head(box, value);
}

Com estes novos ingredientes, podemos então implementar mutexes como segue:

function make_mutex() {
    const cell = make_box(false);
    function the_mutex(m) {
        return m === "acquire"
               ? (test_and_set(cell)
                  ? the_mutex("acquire") // retry
                  : true)
               : m === "release"
               ? (set_content(cell, false), false)
               : error(m, "unknown request -- mutex");
    }
    return the_mutex;
}

onde test_and_set é implementado como

function test_and_set(cell) {
    if (get_content(cell)) {
        return true;
    } else {
        set_content(cell, true);
        return false;
    }
}

💡 Mostrar solução — tente primeiro!💡 Esconder solução

O problema de Louis: serializer((a, b) => ...) embrulharia a troca inteira no serializador de qual conta? Na proposta dele, serialized_exchange chama a troca protegida pelos serializadores das duas contas — e cada acesso interno de exchange (os withdraw/deposit via dispatch) tentaria adquirir de novo um serializador que a própria troca já segura.

Com a implementação de serializadores desta seção, uma função serializada que chama outra função do mesmo serializador fica esperando por si mesma: o mutex já está adquirido e nunca será liberado — deadlock imediato, mesmo sem nenhuma concorrência de verdade. É a armadilha clássica de travas não reentrantes: quem projeta a serialização precisa decidir em um único nível onde ela acontece.

Resolvi o exercício 3.45

Exercício 3.46

Suponha que implementamos test_and_set usando uma verificação ordinária de uma variável, seguida de definir a variável, da seguinte forma:

function test_and_set(cell) {
    if (get_content(cell)) {
        return true;
    } else {
        set_content(cell, true);
        return false;
    }
}

Desenhe um diagrama de temporização como o da Figura 3.29 para demonstrar como a implementação de mutex pode falhar permitindo que duas threads adquiram o mutex ao mesmo tempo.

💡 Mostrar solução — tente primeiro!💡 Esconder solução

Com um test_and_set não atômico, duas threads podem intercalar assim:

Thread A: get_content(cell) → false
Thread B: get_content(cell) → false      (antes da escrita de A!)
Thread A: set_content(cell, true) → adquire
Thread B: set_content(cell, true) → adquire TAMBÉM

As duas veem a célula "livre" e as duas entram na região crítica ao mesmo tempo — o mutex deixou de excluir exatamente no cenário para o qual existe. Por isso test_and_set precisa ser atômico: o teste e a escrita têm de acontecer como uma operação indivisível (com suporte do hardware ou desabilitando interrupções), sem janela entre ler e marcar.

Resolvi o exercício 3.46

Exercício 3.47

Um semáforo (de tamanho $n$) é uma generalização de um mutex. Como um mutex, um semáforo suporta operações de aquisição e liberação, mas é mais geral na medida em que até $n$ threads podem adquirir em qualquer tempo. Tentativas adicionais de adquirir o semáforo devem esperar pela liberação até que uma operação de aquisição seja bem-sucedida.

a. Em termos de mutexes, forneça uma implementação de semáforos.

b. Forneça uma implementação de semáforos em termos de operações atômicas test_and_set.

Deadlock

Agora que vimos como implementar serializadores, podemos ver que a serialização de contas em serialized_exchange ainda tem um problema, mesmo com a versão de make_account que serializa depósitos e saques. Imagine que Peter tenta trocar $a_1$ com $a_2$ enquanto Paul concorrentemente tenta trocar $a_2$ com $a_1$. Suponha que a thread de Peter chegue ao ponto onde ela adquiriu o serializador para $a_1$ e está esperando para adquirir o serializador para $a_2$; suponha que a thread de Paul está simetricamente esperando para adquirir o serializador para $a_1$. Cada thread ficará esperando para sempre para que a outra libere o serializador que ela precisa. Essa situação é chamada de deadlock. Deadlock é sempre um perigo em sistemas que fornecem acesso concorrente a múltiplos recursos compartilhados.

Uma forma de evitar o risco de deadlock é dar a cada conta um número de identificação único e reescrever serialized_exchange de modo que uma thread sempre tente entrar primeiro na conta de número mais baixo. Embora este método funcione bem para o problema de troca, há outras situações que requerem mecanismos de coordenação mais sofisticados. (Ver exercícios 3.48 e 3.49.)⁶

💡 Mostrar solução — tente primeiro!💡 Esconder solução

a. Semáforo com mutex — um contador protegido:

function make_semaphore(n) {
    let count = 0;
    const mutex = make_mutex();
    function the_semaphore(m) {
        if (m === "acquire") {
            mutex("acquire");
            if (count < n) {
                count = count + 1;
                mutex("release");
            } else {
                mutex("release");
                the_semaphore("acquire");   // tenta de novo (busy waiting)
            }
        } else if (m === "release") {
            mutex("acquire");
            count = count - 1;
            mutex("release");
        }
    }
    return the_semaphore;
}

O mutex protege só a consulta e atualização do contador; quem encontra o semáforo cheio solta o mutex e tenta de novo — sem isso, seguraria o mutex e ninguém conseguiria liberar.

b. Com test_and_set direto — a célula faz o papel do mutex:

function make_semaphore(n) {
    let count = 0;
    const cell = list(false);
    function the_semaphore(m) {
        if (m === "acquire") {
            if (test_and_set(cell)) {
                the_semaphore("acquire");        // célula ocupada: repete
            } else if (count < n) {
                count = count + 1;
                clear(cell);
            } else {
                clear(cell);
                the_semaphore("acquire");        // cheio: repete
            }
        } else if (m === "release") {
            if (test_and_set(cell)) {
                the_semaphore("release");
            } else {
                count = count - 1;
                clear(cell);
            }
        }
    }
    return the_semaphore;
}

A estrutura é a mesma; test_and_set/clear protegem o contador em vez do mutex.

Resolvi o exercício 3.47

Exercício 3.48

Explique em detalhes por que a estratégia de deadlock-avoidance descrita acima, (ou seja, os serializadores de conta são adquiridos primeiro pela conta de número menor) evita deadlock no problema de troca. Reescreva serialized_exchange para incorporar esta ideia. (Você também precisará modificar make_account de modo que cada conta seja criada com um número, e fornecer uma forma para acessar esse número.)

💡 Mostrar solução — tente primeiro!💡 Esconder solução

Por que a ordenação evita o deadlock. Deadlock exige um ciclo de espera: A segura o recurso que B quer e B segura o que A quer. Se todo mundo adquire serializadores em ordem crescente de número de conta, uma thread só espera por serializadores de número maior ou igual aos que já possui. Num suposto ciclo, siga as setas de espera: os números teriam de crescer estritamente ao longo do ciclo e voltar ao início — impossível. Sem ciclo, sem deadlock.

A reescrita:

function serialized_exchange(account1, account2) {
    const serializer1 = account1("serializer");
    const serializer2 = account2("serializer");
    return account1("number") < account2("number")
           ? serializer1(serializer2(exchange))(account1, account2)
           : serializer2(serializer1(exchange))(account1, account2);
}

com make_account_and_serializer recebendo/gerando um número de conta (um contador global let next_account_number = 1; incrementado a cada criação) e respondendo à mensagem "number".

Resolvi o exercício 3.48

Exercício 3.49

Dê um cenário onde a estratégia de deadlock-avoidance descrita acima não funciona. (Dica: No problema de troca, cada thread conhece antecipadamente quais contas ela precisará acessar. Considere uma situação onde uma thread deve adquirir alguns recursos compartilhados antes que possa saber quais recursos adicionais compartilhados ela exigirá.)

💡 Mostrar solução — tente primeiro!💡 Esconder solução

A estratégia pressupõe que a thread sabe de antemão todos os recursos de que vai precisar — só assim pode ordená-los antes de adquirir o primeiro.

Cenário em que isso falha: um banco de dados de contas em que a operação é "saque da conta A e deposite na conta indicada DENTRO de A" (uma conta que aponta para outra — pense em débito automático). A thread precisa adquirir A e ler seu conteúdo para descobrir que a segunda conta é B. Se B tem número menor que A, a regra mandaria adquirir B primeiro — tarde demais: A já está adquirida. Duas threads em situação espelhada (uma partindo de A→B, outra de B→A) adquirem A e B respectivamente e entram em deadlock esperando uma pela outra.

Em geral: qualquer protocolo em que a posse de um recurso é necessária para descobrir o próximo recurso quebra a hipótese da ordenação global prévia.

Resolvi o exercício 3.49

Concorrência, tempo e comunicação

Vimos como a programação concorrente é complicada pela necessidade de considerar a intercalação de eventos concorrentes. Além disso, vimos que os objetos compartilhados entre threads (como células de memória) podem requerer proteção de acesso simultâneo. Vimos como implementar a serialização com serializadores, e como serializers são implementados usando mutexes e operações primitivas atômicas test-and-set.

O problema central que encontramos ao lidar com concorrência é a necessidade de reconciliar diferentes eventos no mundo. Reconciliar eventos concorrentes em um sistema computacional requer algum tipo de coordenação entre threads. Como vimos na seção anterior, a serialização é um meio de coordenação, mas é apenas um mecanismo possível.

O problema de sincronização de eventos concorrentes surge não apenas na programação de computadores, mas em outras áreas também. Por exemplo, o sistema de controle de um carro pode ter componentes concorrentes controlando o motor, os freios, e a direção. Esses componentes devem ser coordenados de modo que, por exemplo, o carro não tente acelerar e frear ao mesmo tempo. Além disso, o sistema de controle pode ter que interagir com sensores que detectam obstáculos à frente, de modo que o carro possa parar ou reduzir a velocidade quando necessário.

Como outro exemplo, considere os desafios que sistemas distribuídos de grande escala apresentam para coordenar atividades concorrentes. A Internet, por exemplo, é um sistema distribuído que compreende milhões de computadores interconectados. Coordenar atividades através deste sistema é um desafio formidável. Um aspecto deste desafio é a questão de como diferentes computadores podem ter visões consistentes do tempo, de modo que possam coordenar atividades que dependem da temporização.

Um problema relacionado envolve a questão de o que é tempo. Do ponto de vista físico, pode parecer que tempo é absoluto—que eventos podem sempre ser ordenados temporalmente. No entanto, na prática, coordenar eventos concorrentes requer comunicação entre as entidades envolvidas. Como a velocidade de comunicação é limitada (no máximo pela velocidade da luz), pode haver situações onde não é possível determinar a ordem temporal de dois eventos.

Na verdade, vimos que o problema fundamental de sincronizar threads concorrentes está relacionado ao problema de comunicação entre threads. Se não houvesse comunicação entre threads, não haveria problema de sincronização. Por outro lado, se as threads se comunicam instantaneamente, a sincronização seria trivial. O problema real surge quando a comunicação não é instantânea.

O fenômeno da comunicação não instantânea está intimamente relacionado à questão de tempo em física. A teoria da relatividade de Einstein nos diz que dois eventos separados no espaço podem ocorrer simultaneamente de acordo com um observador, mas não simultaneamente de acordo com outro observador (movendo-se em relação ao primeiro). Não há "tempo absoluto" que todos os observadores concordem. A melhor que podemos fazer é sincronizar os relógios dos observadores trocando sinais entre eles. Mas, novamente, como os sinais levam tempo para viajar, essa sincronização nunca pode ser perfeita.

Assim, a complexidade de lidar com tempo e estado em nossos modelos computacionais reflete diretamente a complexidade de tempo e estado no mundo físico. Essa complexidade surge sempre que temos sistemas computacionais que modelam sistemas físicos que estão compostos de partes separadamente evoluindo que devem se comunicar para coordenar suas ações. O fato central aqui é que, por razões fundamentais físicas, não pode haver "agora" instantaneamente compartilhado. A noção de tempo em sistemas concorrentes deve ser intimamente ligada à comunicação.⁷

Felizmente, nossa compreensão dos problemas envolvidos na programação concorrente está evoluindo. Há desenvolvimentos em andamento de novos modelos de programação concorrente, e desenvolvimentos correspondentes em linguagens de programação e sistemas de execução, que podem oferecer abordagens mais claras e mais eficientes para programação concorrente.

📝 Encontrou algo errado nesta página?

Sua ajuda é muito importante para melhorar a qualidade da tradução!

🐛 Encontrou um erro?

Se você encontrou:

• Erro de tradução (palavra incorreta, termo técnico errado)
• Erro de ortografia ou gramática
• Link quebrado
• Código de exemplo que não funciona
• Problema de formatação

Reporte um bug →

❓ Tem uma dúvida?

Se você tem:

• Dúvida sobre o conteúdo desta seção
• Pergunta sobre um conceito do SICP
• Dificuldade em entender algum exemplo
• Questão sobre a tradução de algum termo

Inicie uma discussão →

💡 Tem uma sugestão de melhoria?

Se você quer sugerir:

• Melhoria na explicação
• Exemplo adicional
• Recurso visual (diagrama, ilustração)
• Qualquer outra ideia

Sugira uma melhoria →

🌍 Quer discutir a tradução?

Se você quer debater:

• Escolha de tradução de algum termo
• Consistência de terminologia
• Nuances do português

Discussão de tradução →

Obrigado por ajudar a melhorar o SICP.js PT-BR! ✨

Footnotes

1. A função concurrent_execute não é parte do padrão JavaScript, mas os exemplos nesta seção podem ser implementados em ECMAScript 2020. ↩

2. Simplificamos exchange explorando o fato de que nossa mensagem deposit aceita quantias negativas. (Este é um bug sério em nosso sistema bancário!) ↩

3. Se o saldo de $a_1$ é menor que o saldo de $a_2$, exchange tentará sacar uma quantia negativa de $a_1$. Esta é uma correção fortuita, porque nossa implementação de make_account permite que depósitos e saques continuem (via deposit de quantias negativas) mesmo se a conta não tem saldo suficiente. Um bug pior pode ocorrer se tentamos exchange em três contas simultaneamente. ↩

4. Usar mutexes dessa forma é análogo ao uso de travas no gerenciamento de banco de dados. Por exemplo, considere um banco de dados que consiste de uma coleção de registros, cada um dos quais pode ser modificado por múltiplas transações concorrentes. Para garantir que as transações não interfiram umas com as outras, podemos usar travas para controlar acesso aos registros. Antes de ler ou escrever um registro, uma transação deve adquirir a trava associada com esse registro. Após a transação ter terminado de acessar o registro, ela deve liberar a trava. Essa estratégia é chamada de two-phase locking. ↩

5. A instrução de aquisição de um mutex é semelhante à operação test_and_set que descrevemos, exceto que em vez de retornar um valor booleano, ela espera até que o mutex esteja disponível e então o adquire. ↩

6. O problema geral de como coordenar threads é extremamente difícil e é um tema de pesquisa contínua. Ver Lamport 1978, Schneider 1997, e Herlihy e Shavit 2008 para discussões mais aprofundadas de deadlock. Chandy e Misra 1988 e Dijkstra 1968 descrevem o problema de deadlock no contexto do problema clássico dos "filósofos jantando", onde há cinco filósofos sentados em uma mesa redonda com um garfo entre cada par de filósofos. Cada filósofo precisa de dois garfos para comer. Se cada filósofo pega o garfo à sua direita simultaneamente, todos ficarão esperando para pegar o garfo à sua esquerda, resultando em deadlock. ↩

7. Para discussões mais aprofundadas dos conceitos de tempo e identidade em sistemas concorrentes, ver Lamport 1978 e Schneider 1997. Chandy e Misra 1988 discutem tempo e comunicação no contexto de sistemas distribuídos. Lamport, Shostak e Pease 1982 examinam o problema de sincronização de relógios em sistemas distribuídos. Há também uma literatura substancial sobre modelos alternativos de concorrência. Ver, por exemplo, Hoare 1978, Milner 1980, e Hewitt e Baker 1977. A linguagem Erlang (Armstrong 2007) é baseada em um modelo de passagem de mensagens de concorrência. A biblioteca de concorrência de Java oferece suporte para monitores (Hoare 1974). Trabalho recente em memória transacional de software (Shavit e Touitou 1997, Harris e Fraser 2003) oferece uma alternativa para travas e mutexes para controlar acesso a recursos compartilhados. ↩