3.4Concorrência: O Tempo é Essencial

Vimos o poder dos objetos computacionais com estado local como ferramentas para modelagem. No entanto, como 3.1.3 alertou, esse poder tem um preço: a perda da transparência referencial, dando origem a uma série de questões sobre identidade e mudança, e a necessidade de abandonar o modelo de substituição de avaliação em favor do mais intrincado modelo de ambiente.

A questão central por trás da complexidade do estado, identidade e mudança é que, ao introduzir a atribuição, somos forçados a admitir tempo em nossos modelos computacionais. Antes de introduzirmos a atribuição, todos os nossos programas eram atemporais, no sentido de que qualquer expressão que tinha um valor sempre tinha o mesmo valor. Em contraste, lembre-se do exemplo de modelagem de saques de uma conta bancária e retorno do saldo resultante, introduzido no início de 3.1.1:

(withdraw 25)
75

(withdraw 25)
50

Aqui, avaliações sucessivas da mesma expressão produzem valores diferentes. Esse comportamento surge do fato de que a execução de declarações de atribuição (neste caso, atribuições à variável balance) delineia momentos no tempo em que os valores mudam. O resultado da avaliação de uma expressão depende não apenas da expressão em si, mas também de se a avaliação ocorre antes ou depois desses momentos. Construir modelos em termos de objetos computacionais com estado local nos força a confrontar o tempo como um conceito essencial na programação.

Podemos ir além na estruturação de modelos computacionais para corresponder à nossa percepção do mundo físico. Objetos no mundo não mudam um de cada vez em sequência. Em vez disso, nós os percebemos como agindo concorrentemente—todos de uma vez. Portanto, muitas vezes é natural modelar sistemas como coleções de processos computacionais que executam concorrentemente. Assim como podemos tornar nossos programas modulares organizando modelos em termos de objetos com estado local separado, muitas vezes é apropriado dividir modelos computacionais em partes que evoluem separadamente e concorrentemente. Mesmo que os programas sejam executados em um computador sequencial, a prática de escrever programas como se fossem executados concorrentemente força o programador a evitar restrições de tempo desnecessárias e, assim, torna os programas mais modulares.

Além de tornar os programas mais modulares, a computação concorrente pode fornecer uma vantagem de velocidade sobre a computação sequencial. Computadores sequenciais executam apenas uma operação por vez, então o tempo necessário para realizar uma tarefa é proporcional ao número total de operações realizadas.¹⁶² No entanto, se for possível decompor um problema em partes relativamente independentes e que precisam se comunicar apenas raramente, pode ser possível alocar as partes para processadores de computação separados, produzindo uma vantagem de velocidade proporcional ao número de processadores disponíveis.

Infelizmente, as complexidades introduzidas pela atribuição tornam-se ainda mais problemáticas na presença de concorrência. O fato da execução concorrente, seja porque o mundo opera em paralelo ou porque nossos computadores o fazem, implica em complexidade adicional em nossa compreensão do tempo.

3.4.1A Natureza do Tempo em Sistemas Concorrentes

Na superfície, o tempo parece simples. É uma ordem imposta sobre eventos.¹⁶³ Para quaisquer eventos $A$ e $B$, ou $A$ ocorre antes de $B$, $A$ e $B$ são simultâneos, ou $A$ ocorre depois de $B$. Por exemplo, voltando ao exemplo da conta bancária, suponha que Peter retire $10 e Paul retire $25 de uma conta conjunta que inicialmente contém $100, deixando $65 na conta. Dependendo da ordem dos dois saques, a sequência de saldos na conta é $100 $\to$ $90 $\to$ $65 ou $100 $\to$ $75 $\to$ $65. Em uma implementação computacional do sistema bancário, essa sequência de saldos poderia ser modelada por atribuições sucessivas a uma variável balance.

Em situações complexas, no entanto, essa visão pode ser problemática. Suponha que Peter e Paul, e outras pessoas além deles, estejam acessando a mesma conta bancária através de uma rede de caixas eletrônicos distribuídos por todo o mundo. A sequência real de saldos na conta dependerá criticamente do tempo detalhado dos acessos e dos detalhes da comunicação entre as máquinas.

Essa indeterminação na ordem dos eventos pode causar sérios problemas no design de sistemas concorrentes. Por exemplo, suponha que os saques feitos por Peter e Paul sejam implementados como dois processos separados compartilhando uma variável comum balance, cada processo especificado pelo procedimento dado em 3.1.1:

(define (withdraw amount)
  (if (>= balance amount)
      (begin 
        (set! balance 
              (- balance amount))
        balance)
      "Insufficient funds"))

Se os dois processos operarem independentemente, então Peter pode testar o saldo e tentar sacar uma quantia legítima. No entanto, Paul pode sacar alguns fundos entre o momento em que Peter verifica o saldo e o momento em que Peter completa o saque, invalidando assim o teste de Peter.

As coisas podem ficar ainda piores. Considere a expressão

(set! balance (- balance amount))

executada como parte de cada processo de saque. Isso consiste em três etapas: (1) acessar o valor da variável balance; (2) calcular o novo saldo; (3) definir balance para esse novo valor. Se os saques de Peter e Paul executarem essa declaração concorrentemente, então os dois saques podem intercalar a ordem em que acessam balance e o definem para o novo valor.

O diagrama de tempo em Figura 3.29 descreve uma ordem de eventos em que balance começa em 100, Peter saca 10, Paul saca 25, e ainda assim o valor final de balance é 75. Como mostrado no diagrama, a razão para essa anomalia é que a atribuição de 75 a balance por Paul é feita sob a suposição de que o valor de balance a ser decrementado é 100. Essa suposição, no entanto, tornou-se inválida quando Peter mudou balance para 90. Isso é uma falha catastrófica para o sistema bancário, porque a quantidade total de dinheiro no sistema não é conservada. Antes das transações, a quantidade total de dinheiro era $100. Depois, Peter tem $10, Paul tem $25, e o banco tem $75.¹⁶⁴

O fenômeno geral ilustrado aqui é que vários processos podem compartilhar uma variável de estado comum. O que torna isso complicado é que mais de um processo pode estar tentando manipular o estado compartilhado ao mesmo tempo. Para o exemplo da conta bancária, durante cada transação, cada cliente deve ser capaz de agir como se os outros clientes não existissem. Quando um cliente altera o saldo de uma forma que depende do saldo, ele deve ser capaz de assumir que, logo antes do momento da mudança, o saldo ainda é o que ele pensava que era.

Comportamento correto de programas concorrentes

O exemplo acima tipifica os bugs sutis que podem surgir em programas concorrentes. A raiz dessa complexidade está nas atribuições a variáveis que são compartilhadas entre os diferentes processos. Já sabemos que devemos ter cuidado ao escrever programas que usam set!, porque os resultados de uma computação dependem da ordem em que as atribuições ocorrem.¹⁶⁵ Com processos concorrentes, devemos ser especialmente cuidadosos com as atribuições, porque podemos não ser capazes de controlar a ordem das atribuições feitas pelos diferentes processos. Se várias dessas mudanças puderem ser feitas concorrentemente (como com dois depositantes acessando uma conta conjunta), precisamos de alguma maneira de garantir que nosso sistema se comporte corretamente. Por exemplo, no caso de saques de uma conta bancária conjunta, devemos garantir que o dinheiro seja conservado. Para fazer com que programas concorrentes se comportem corretamente, podemos ter que impor algumas restrições à execução concorrente.

Uma possível restrição à concorrência estipularia que nenhuma operação que altere qualquer variável de estado compartilhado pode ocorrer ao mesmo tempo. Esse é um requisito extremamente rigoroso. Para o banco distribuído, exigiria que o designer do sistema garantisse que apenas uma transação pudesse prosseguir por vez. Isso seria ineficiente e excessivamente conservador. Figura 3.30 mostra Peter e Paul compartilhando uma conta bancária, onde Paul também tem uma conta privada. O diagrama ilustra dois saques da conta compartilhada (um por Peter e outro por Paul) e um depósito na conta privada de Paul.¹⁶⁶ Os dois saques da conta compartilhada não devem ser concorrentes (já que ambos acessam e atualizam a mesma conta), e o depósito e o saque de Paul não devem ser concorrentes (já que ambos acessam e atualizam a quantia na carteira de Paul). Mas não deve haver problema em permitir que o depósito de Paul em sua conta privada prossiga concorrentemente com o saque de Peter da conta compartilhada.

Uma restrição menos rigorosa à concorrência garantiria que um sistema concorrente produza o mesmo resultado como se os processos tivessem sido executados sequencialmente em alguma ordem. Há dois aspectos importantes nesse requisito. Primeiro, ele não exige que os processos realmente sejam executados sequencialmente, mas apenas que produzam resultados que sejam os mesmos como se tivessem sido executados sequencialmente. Para o exemplo em Figura 3.30, o designer do sistema de conta bancária pode permitir com segurança que o depósito de Paul e o saque de Peter aconteçam concorrentemente, porque o resultado líquido será o mesmo como se as duas operações tivessem acontecido sequencialmente. Segundo, pode haver mais de um resultado "correto" produzido por um programa concorrente, porque exigimos apenas que o resultado seja o mesmo como para alguma ordem sequencial. Por exemplo, suponha que a conta conjunta de Peter e Paul comece com $100, e Peter deposite $40 enquanto Paul concorrentemente saca metade do dinheiro na conta. Então, a execução sequencial poderia resultar no saldo da conta sendo $70 ou $90 (veja Exercício 3.38).¹⁶⁷

Ainda há requisitos mais fracos para a execução correta de programas concorrentes. Um programa para simular difusão (digamos, o fluxo de calor em um objeto) pode consistir em um grande número de processos, cada um representando um pequeno volume de espaço, que atualizam seus valores concorrentemente. Cada processo repetidamente muda seu valor para a média de seu próprio valor e os valores de seus vizinhos. Esse algoritmo converge para a resposta correta independentemente da ordem em que as operações são feitas; não há necessidade de restrições sobre o uso concorrente dos valores compartilhados.

Exercício 3.38: Suponha que Peter, Paul e Mary compartilhem uma conta bancária conjunta que inicialmente contém $100. Concorrentemente, Peter deposita $10, Paul saca $20, e Mary saca metade do dinheiro na conta, executando os seguintes comandos:

Peter: (set! balance (+ balance 10))
Paul:  (set! balance (- balance 20))
Mary:  (set! balance (- balance 
                        (/ balance 2)))

1. Liste todos os diferentes valores possíveis para balance após essas três transações terem sido concluídas, assumindo que o sistema bancário força os três processos a serem executados sequencialmente em alguma ordem.
2. Quais são alguns outros valores que poderiam ser produzidos se o sistema permitir que os processos sejam intercalados? Desenhe diagramas de tempo como o da Figura 3.29 para explicar como esses valores podem ocorrer.

3.4.2Mecanismos para Controlar Concorrência

Vimos que a dificuldade em lidar com processos concorrentes está enraizada na necessidade de considerar a intercalação da ordem de eventos nos diferentes processos. Por exemplo, suponha que tenhamos dois processos, um com três eventos ordenados $(a,b,c)$ e outro com três eventos ordenados $(x,y,z)$. Se os dois processos forem executados concorrentemente, sem restrições sobre como sua execução é intercalada, então há 20 ordens diferentes possíveis para os eventos que são consistentes com as ordens individuais dos dois processos:

(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)

Como programadores projetando esse sistema, teríamos que considerar os efeitos de cada uma dessas 20 ordens e verificar se cada comportamento é aceitável. Essa abordagem rapidamente se torna inviável à medida que o número de processos e eventos aumenta.

Uma abordagem mais prática para o design de sistemas concorrentes é criar mecanismos gerais que nos permitam restringir a intercalação de processos concorrentes para que possamos ter certeza de que o comportamento do programa está correto. Muitos mecanismos foram desenvolvidos para esse propósito. Nesta seção, descreveremos um deles, o serializador.

Serializando o acesso ao estado compartilhado

A serialização implementa a seguinte ideia: Os processos serão executados concorrentemente, mas haverá certas coleções de procedimentos que não podem ser executados concorrentemente. Mais precisamente, a serialização cria conjuntos distintos de procedimentos de forma que apenas uma execução de um procedimento em cada conjunto serializado é permitida por vez. Se algum procedimento no conjunto estiver sendo executado, então um processo que tenta executar qualquer procedimento no conjunto será forçado a esperar até que a primeira execução termine.

Podemos usar a serialização para controlar o acesso a variáveis compartilhadas. Por exemplo, se quisermos 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 no mesmo procedimento. Em seguida, garantimos que nenhum outro procedimento que atribua à variável possa ser executado concorrentemente com esse procedimento, serializando todos esses procedimentos com o mesmo serializador. Isso garante que o valor da variável não possa ser alterado entre um acesso e a atribuição correspondente.

Serializadores em Scheme

Para tornar o mecanismo acima mais concreto, suponha que estendemos Scheme para incluir um procedimento chamado parallel-execute:

(parallel-execute ⟨p₁⟩ 
                  ⟨p₂⟩ 
                  … 
                  ⟨pₖ⟩)

Cada ⟨p⟩ deve ser um procedimento sem argumentos. Parallel-execute cria um processo separado para cada ⟨p⟩, que aplica ⟨p⟩ (sem argumentos). Esses processos são executados concorrentemente.¹⁶⁸

Como exemplo de como isso é usado, considere

(define x 10)
(parallel-execute (lambda () (set! x (* x x)))
                  (lambda () (set! x (+ x 1))))

Isso cria dois processos concorrentes—$P_1$, que define x como x vezes x, e $P_2$, que incrementa x. Após a execução, x terá um dos cinco valores possíveis, dependendo da intercalação dos eventos de $P_1$ e $P_2$:

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

Podemos restringir a concorrência usando procedimentos serializados, que são criados por serializadores. Serializadores são construídos por make-serializer, cuja implementação é dada abaixo. Um serializador recebe um procedimento como argumento e retorna um procedimento serializado que se comporta como o procedimento original. Todas as chamadas para um determinado serializador retornam procedimentos serializados no mesmo conjunto.

Assim, em contraste com o exemplo acima, executando

(define x 10)
(define s (make-serializer))
(parallel-execute 
 (s (lambda () (set! x (* x x))))
 (s (lambda () (set! 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 $P_1$ e $P_2$ não pode ser intercalada.

Aqui está uma versão do procedimento make-account de 3.1.1, onde os depósitos e saques foram serializados:

(define (make-account balance)
  (define (withdraw amount)
    (if (>= balance amount)
        (begin 
          (set! balance 
                (- balance amount))
          balance)
        "Insufficient funds"))
  (define (deposit amount)
    (set! balance (+ balance amount))
    balance)
  (let ((protected (make-serializer)))
    (define (dispatch m)
      (cond ((eq? m 'withdraw) 
             (protected withdraw))
            ((eq? m 'deposit) 
             (protected deposit))
            ((eq? m 'balance) 
             balance)
            (else 
             (error 
              "Unknown request: 
               MAKE-ACCOUNT"
              m))))
    dispatch))

Com essa implementação, dois processos não podem sacar ou depositar em uma única conta concorrentemente. Isso elimina a fonte do erro ilustrado em 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 realiza a atribuição. Por outro lado, cada conta tem seu próprio serializador, de modo que depósitos e saques para diferentes contas podem prosseguir concorrentemente.

Exercício 3.39: Quais das cinco possibilidades na execução paralela mostrada acima permanecem se, em vez disso, serializarmos a execução da seguinte forma:

(define x 10)
(define s (make-serializer))
(parallel-execute 
  (lambda () 
    (set! x ((s (lambda () (* x x))))))
  (s (lambda () (set! x (+ x 1)))))

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

(define x 10)
(parallel-execute 
 (lambda () (set! x (* x x)))
 (lambda () (set! x (* x x x))))

Quais dessas possibilidades permanecem se, em vez disso, usarmos procedimentos serializados:

(define x 10)
(define s (make-serializer))
(parallel-execute 
 (s (lambda () (set! x (* x x))))
 (s (lambda () (set! x (* x x x)))))

Exercício 3.41: Ben Bitdiddle se preocupa que seria melhor implementar a conta bancária da seguinte forma (onde a linha comentada foi alterada):

(define (make-account balance)
  (define (withdraw amount)
    (if (>= balance amount)
        (begin 
          (set! balance 
                (- balance amount))
          balance)
        "Insufficient funds"))
  (define (deposit amount)
    (set! balance (+ balance amount))
    balance)
  (let ((protected (make-serializer)))
    (define (dispatch m)
      (cond ((eq? m 'withdraw) 
             (protected withdraw))
            ((eq? m 'deposit) 
             (protected deposit))
            ((eq? m 'balance) 
             ((protected 
                (lambda () 
                  balance)))) ; serialized
            (else 
             (error 
              "Unknown request: 
               MAKE-ACCOUNT"
              m))))
    dispatch))

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

Exercício 3.42: Ben Bitdiddle sugere que é um desperdício de tempo criar um novo procedimento serializado em resposta a cada mensagem de withdraw e deposit. Ele diz que make-account poderia ser alterado para que as chamadas a protected sejam feitas fora do procedimento dispatch. Ou seja, uma conta retornaria o mesmo procedimento serializado (que foi criado ao mesmo tempo que a conta) cada vez que for solicitado um procedimento de saque.

(define (make-account balance)
  (define (withdraw amount)
    (if (>= balance amount)
        (begin 
          (set! balance 
                (- balance amount))
          balance)
        "Insufficient funds"))
  (define (deposit amount)
    (set! balance (+ balance amount))
    balance)
  (let ((protected (make-serializer)))
    (let ((protected-withdraw 
           (protected withdraw))
          (protected-deposit 
           (protected deposit)))
      (define (dispatch m)
        (cond ((eq? m 'withdraw) 
               protected-withdraw))
              ((eq? m 'deposit) 
               protected-deposit))
              ((eq? m 'balance) 
               balance)
              (else 
               (error 
                "Unknown request: 
                 MAKE-ACCOUNT"
                m))))
      dispatch)))

Essa é uma mudança segura? Em particular, há alguma diferença no que a concorrência é permitida por essas duas versões de make-account?

Complexidade de usar múltiplos recursos compartilhados

Os serializadores fornecem uma abstração poderosa que ajuda a isolar as complexidades dos programas concorrentes para que possam ser tratadas com cuidado e (esperançosamente) corretamente. No entanto, embora o uso de serializadores seja relativamente simples quando há apenas um 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:¹⁶⁹

(define (exchange account1 account2)
  (let ((difference (- (account1 'balance)
                       (account2 'balance))))
    ((account1 'withdraw) difference))
    ((account2 'deposit) difference)))

Esse procedimento funciona bem quando apenas um único processo está tentando fazer a troca. Suponha, no entanto, que Peter e Paul tenham acesso às contas $a1$, $a2$ e $a3$, e que Peter troque $a1$ e $a2$ enquanto Paul concorrentemente troca $a1$ e $a3$. Mesmo com depósitos e saques serializados para contas individuais (como no procedimento make-account mostrado acima nesta seção), exchange ainda pode produzir resultados incorretos. Por exemplo, Peter pode calcular a diferença nos saldos para $a1$ e $a2$, mas então Paul pode mudar o saldo em $a1$ antes que Peter possa completar a troca.¹⁷⁰ Para um comportamento correto, devemos garantir que o procedimento exchange bloqueie qualquer outro acesso concorrente às contas durante todo o tempo da troca.

Uma maneira de conseguir isso é usar os serializadores de ambas as contas para serializar todo o procedimento exchange. Para fazer isso, vamos organizar o acesso ao serializador de uma conta. Observe que estamos deliberadamente quebrando a modularidade do objeto conta bancária ao expor o serializador. A seguinte versão de make-account é idêntica à versão original dada em 3.1.1, exceto que um serializador é fornecido para proteger a variável de saldo, e o serializador é exportado via passagem de mensagens:

(define (make-account-and-serializer balance)
  (define (withdraw amount)
    (if (>= balance amount)
        (begin 
          (set! balance (- balance amount))
          balance)
        "Insufficient funds"))
  (define (deposit amount)
    (set! balance (+ balance amount))
    balance)
  (let ((balance-serializer 
         (make-serializer)))
    (define (dispatch m)
      (cond ((eq? m 'withdraw) 
             withdraw))
            ((eq? m 'deposit) 
             deposit))
            ((eq? m 'balance) 
             balance)
            ((eq? m 'serializer) 
             balance-serializer))
            (else 
             (error 
              "Unknown request: 
               MAKE-ACCOUNT"
              m))))
    dispatch))

Podemos usar isso para fazer depósitos e saques serializados. No entanto, ao contrário de nossa conta serializada anterior, agora é responsabilidade de cada usuário de objetos conta bancária gerenciar explicitamente a serialização, por exemplo da seguinte forma:¹⁷¹

(define (deposit account amount)
  (let ((s (account 'serializer))
        (d (account 'deposit)))
    ((s d) amount)))

Exportar o serializador dessa forma nos dá flexibilidade suficiente para implementar um programa de troca serializado. Simplesmente serializamos o procedimento exchange original com os serializadores de ambas as contas:

(define (serialized-exchange account1 account2)
  (let ((serializer1 (account1 'serializer))
        (serializer2 (account2 'serializer)))
    ((serializer1 (serializer2 exchange))
     account1
     account2)))

Exercício 3.43: Suponha que os saldos em três contas comecem com $10, $20 e $30, e que múltiplos processos sejam executados, trocando os saldos nas contas. Argumente que, se os processos forem executados sequencialmente, após qualquer número de trocas concorrentes, os saldos das contas devem ser $10, $20 e $30 em alguma ordem. Desenhe um diagrama de tempo como o da Figura 3.29 para mostrar como essa condição pode ser violada se as trocas forem implementadas usando a primeira versão do programa de troca de contas nesta seção. Por outro lado, argumente que, mesmo com esse programa exchange, a soma dos saldos nas contas será preservada. Desenhe um diagrama de tempo para mostrar como até essa condição seria violada se não serializássemos as transações em contas individuais.

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 o seguinte procedimento, mesmo que haja várias pessoas transferindo dinheiro concorrentemente entre várias contas, usando qualquer mecanismo de conta que serialize transações de depósito e saque, por exemplo, a versão de make-account no texto acima.

(define 
  (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 um método mais sofisticado, como o necessário para lidar com o problema de troca. Louis está certo? Se não, qual é a diferença essencial entre o problema de transferência e o problema de troca? (Você deve assumir que o saldo em from-account é pelo menos amount.)

Exercício 3.45: Louis Reasoner acha que nosso sistema de conta bancária é desnecessariamente complexo e propenso a erros agora que depósitos e saques não são automaticamente serializados. Ele sugere que make-account-and-serializer deveria ter exportado o serializador (para uso por procedimentos como serialized-exchange) além de (em vez de) usá-lo para serializar contas e depósitos como make-account fez. Ele propõe redefinir contas da seguinte forma:

(define 
  (make-account-and-serializer balance)
  (define (withdraw amount)
    (if (>= balance amount)
        (begin 
          (set! balance 
                (- balance amount))
          balance)
        "Insufficient funds"))
  (define (deposit amount)
    (set! balance (+ balance amount))
    balance)
  (let ((balance-serializer 
         (make-serializer)))
    (define (dispatch m)
      (cond ((eq? m 'withdraw) 
             (balance-serializer withdraw))
            ((eq? m 'deposit) 
             (balance-serializer deposit))
            ((eq? m 'balance) 
             balance)
            ((eq? m 'serializer) 
             balance-serializer))
            (else 
             (error 
              "Unknown request: 
               MAKE-ACCOUNT"
              m))))
    dispatch))

Então, os depósitos são tratados como na versão original de make-account:

(define (deposit account amount)
  ((account 'deposit) amount))

Explique o que está errado com o raciocínio de Louis. Em particular, considere o que acontece quando serialized-exchange é chamado.

Implementando serializadores

Implementamos serializadores em termos de um mecanismo de sincronização mais primitivo chamado 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 outra 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 um procedimento p, o serializador retorna um procedimento que adquire o mutex, executa p e, em seguida, libera o mutex. Isso garante que apenas um dos procedimentos produzidos pelo serializador pode estar em execução por vez, o que é exatamente a propriedade de serialização que precisamos garantir.

(define (make-serializer)
  (let ((mutex (make-mutex)))
    (lambda (p)
      (define (serialized-p . args)
        (mutex 'acquire))
        (let ((val (apply p args)))
          (mutex 'release))
          val))
      serialized-p)))

O mutex é um objeto mutável (aqui usaremos uma lista de um elemento, que chamaremos de célula) que pode conter o valor verdadeiro ou falso. Quando o valor é falso, o mutex está disponível para ser adquirido. Quando o valor é verdadeiro, o mutex está indisponível, e qualquer processo que tente adquirir o mutex deve esperar.

Nosso construtor de mutex make-mutex começa inicializando o conteúdo da célula como falso. Para adquirir o mutex, testamos a célula. Se o mutex estiver disponível, definimos o conteúdo da célula como verdadeiro e prosseguimos. Caso contrário, esperamos em um loop, tentando adquirir repetidamente até encontrarmos o mutex disponível.¹⁷³ Para liberar o mutex, definimos o conteúdo da célula como falso.

(define (make-mutex)
  (let ((cell (list false)))
    (define (the-mutex m)
      (cond ((eq? m 'acquire))
             (if (test-and-set! cell)
                 (the-mutex 'acquire)))) ; retry
            ((eq? m 'release)) (clear! cell))))
    the-mutex))
(define (clear! cell) (set-car! cell false))

Test-and-set! testa a célula e retorna o resultado do teste. Além disso, se o teste for falso, test-and-set! define o conteúdo da célula como verdadeiro antes de retornar falso. Podemos expressar esse comportamento como o seguinte procedimento:

(define (test-and-set! cell)
  (if (car cell)
      true
      (begin (set-car! cell true)
             false)))

No entanto, essa implementação de test-and-set! não é suficiente como está. Há uma sutileza crucial aqui, que é o lugar essencial onde o controle de concorrência entra no sistema: A operação test-and-set! deve ser realizada atomicamente. Ou seja, devemos garantir que, uma vez que um processo tenha testado a célula e encontrado o valor falso, o conteúdo da célula será realmente definido como verdadeiro antes que qualquer outro processo possa testar a célula. Se não fizermos essa garantia, o mutex pode falhar de maneira semelhante à falha da conta bancária na Figura 3.29. (Veja Exercício 3.46.)

A implementação real de test-and-set! depende dos detalhes de como nosso sistema executa processos concorrentes. Por exemplo, podemos estar executando processos concorrentes em um processador sequencial usando um mecanismo de divisão de tempo que alterna entre os processos, permitindo que cada processo execute por um curto período antes de interrompê-lo e passar para o próximo processo. Nesse caso, test-and-set! pode funcionar desabilitando a divisão de tempo durante o teste e a definição.¹⁷⁴ Alternativamente, computadores multiprocessados fornecem instruções que suportam operações atômicas diretamente no hardware.¹⁷⁵

Exercício 3.46: Suponha que implementemos test-and-set! usando um procedimento comum, como mostrado no texto, sem tentar tornar a operação atômica. Desenhe um diagrama de tempo como o da Figura 3.29 para demonstrar como a implementação do mutex pode falhar, permitindo que dois processos adquiram o mutex ao mesmo tempo.

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, pois até $n$ processos podem adquiri-lo concorrentemente. Processos adicionais que tentam adquirir o semáforo devem esperar por operações de liberação. Dê implementações de semáforos

1. em termos de mutexes
2. em termos de operações atômicas test-and-set!.

Deadlock

Agora que vimos como implementar serializadores, podemos ver que a troca de contas ainda tem um problema, mesmo com o procedimento serialized-exchange acima. Imagine que Peter tente trocar $a1$ com $a2$ enquanto Paul concorrentemente tenta trocar $a2$ com $a1$. Suponha que o processo de Peter chegue ao ponto em que ele entrou em um procedimento serializado protegendo $a1$ e, logo após isso, o processo de Paul entre em um procedimento serializado protegendo $a2$. Agora Peter não pode prosseguir (para entrar em um procedimento serializado protegendo $a2$) até que Paul saia do procedimento serializado protegendo $a2$. Da mesma forma, Paul não pode prosseguir até que Peter saia do procedimento serializado protegendo $a1$. Cada processo está parado para sempre, esperando pelo outro. Essa situação é chamada de deadlock. Deadlock é sempre um perigo em sistemas que fornecem acesso concorrente a múltiplos recursos compartilhados.

Uma maneira de evitar o deadlock nessa situação é dar a cada conta um número de identificação único e reescrever serialized-exchange para que um processo sempre tente entrar em um procedimento protegendo a conta de número mais baixo primeiro. Embora esse método funcione bem para o problema de troca, há outras situações que exigem técnicas mais sofisticadas de evitar deadlock, ou onde o deadlock não pode ser evitado. (Veja Exercício 3.48 e Exercício 3.49.)¹⁷⁶

Exercício 3.48: Explique em detalhes por que o método de evitar deadlock descrito acima (ou seja, as contas são numeradas, e cada processo tenta adquirir a conta de número menor primeiro) evita deadlock no problema de troca. Reescreva serialized-exchange para incorporar essa ideia. (Você também precisará modificar make-account para que cada conta seja criada com um número, que pode ser acessado enviando uma mensagem apropriada.)

Exercício 3.49: Dê um cenário onde o mecanismo de evitar deadlock descrito acima não funciona. (Dica: No problema de troca, cada processo sabe de antemão quais contas precisará acessar. Considere uma situação onde um processo deve acessar alguns recursos compartilhados antes de saber quais recursos compartilhados adicionais precisará.)

Concorrência, tempo e comunicação

Vimos como programar sistemas concorrentes exige controlar a ordem dos eventos quando diferentes processos acessam o estado compartilhado, e vimos como alcançar esse controle através do uso criterioso de serializadores. Mas os problemas da concorrência vão mais fundo do que isso, porque, de um ponto de vista fundamental, nem sempre está claro o que se entende por "estado compartilhado".

Mecanismos como test-and-set! exigem que os processos examinem uma flag global compartilhada em momentos arbitrários. Isso é problemático e ineficiente de implementar em processadores modernos de alta velocidade, onde, devido a técnicas de otimização como pipelining e memória cache, o conteúdo da memória pode não estar em um estado consistente a cada instante. Em sistemas multiprocessados contemporâneos, portanto, o paradigma de serialização está sendo substituído por novas abordagens para controle de concorrência.¹⁷⁷

Os aspectos problemáticos do estado compartilhado também surgem em grandes sistemas distribuídos. Por exemplo, imagine um sistema bancário distribuído onde bancos individuais mantêm valores locais para saldos bancários e periodicamente comparam esses valores com os valores mantidos por outros bancos. Em tal sistema, o valor de "o saldo da conta" seria indeterminado, exceto logo após a sincronização. Se Peter depositar dinheiro em uma conta que ele mantém em conjunto com Paul, quando devemos dizer que o saldo da conta mudou—quando o saldo no banco local muda, ou não até depois da sincronização? E se Paul acessar a conta de um banco diferente, quais são as restrições razoáveis a serem impostas ao sistema bancário para que o comportamento seja "correto"? A única coisa que pode importar para a correção é o comportamento observado por Peter e Paul individualmente e o "estado" da conta imediatamente após a sincronização. Questões sobre o "verdadeiro" saldo da conta ou a ordem dos eventos entre sincronizações podem ser irrelevantes ou sem sentido.¹⁷⁸

O fenômeno básico aqui é que sincronizar diferentes processos, estabelecer estado compartilhado ou impor uma ordem sobre eventos exige comunicação entre os processos. Em essência, qualquer noção de tempo no controle de concorrência deve estar intimamente ligada à comunicação.¹⁷⁹ É intrigante que uma conexão semelhante entre tempo e comunicação também surja na Teoria da Relatividade, onde a velocidade da luz (o sinal mais rápido que pode ser usado para sincronizar eventos) é uma constante fundamental relacionando tempo e espaço. As complexidades que encontramos ao lidar com tempo e estado em nossos modelos computacionais podem, de fato, espelhar uma complexidade fundamental do universo físico.

(define (test-and-set! cell)
  (without-interrupts
   (lambda ()
     (if (car cell)
         true
         (begin (set-car! cell true)
                false))))