Leitura 17: Simultaneidade

#### Software 6.005

#### Objectives+ Message passing & shared memory+ Processes & threads+ Time slicing+ Race conditions# # Concurreency*Concurreency* means multiple computations are happening at the same time. A concorrência está em toda parte na programação moderna, quer gostemos ou não:+ múltiplos computadores em uma rede+ múltiplas aplicações rodando em um computador+ múltiplos processadores em um computador (hoje, muitas vezes múltiplos núcleos de processador em um único chip) de fato, a concorrência é essencial na programação moderna:+ Web sites devem lidar com múltiplos usuários simultâneos.+ Aplicativos móveis precisam fazer parte de seu processamento em servidores (“na nuvem”).+ As interfaces gráficas do utilizador quase sempre requerem trabalho de fundo que não interrompe o utilizador. Por exemplo, a Eclipse compila seu código Java enquanto você ainda está editando.Ser capaz de programar com concorrência ainda será importante no futuro. As velocidades do relógio do processador não estão mais aumentando. Em vez disso, estamos a receber mais núcleos com cada nova geração de chips. Então, no futuro, a fim de obter uma computação para correr mais rápido, teremos que dividir uma computação em partes simultâneas.## Dois modelos para programação concorrente existem dois modelos comuns para programação concorrente: * memória compartilhada*e * passagem de mensagens*.

* * memória partilhada.** No modelo de memória compartilhada de concorrência, módulos simultâneos interagem pela leitura e escrita de objetos compartilhados na memória. Outros exemplos do modelo de memória compartilhada: + a e B podem ser dois processadores (ou núcleos de processador) no mesmo computador, compartilhando a mesma memória física.+ A e B podem ser dois programas rodando no mesmo computador, compartilhando um sistema de arquivos comum com arquivos que eles podem ler e escrever.+ A e B podem ser dois threads no mesmo programa Java (vamos explicar o que é um thread abaixo), compartilhando os mesmos objetos Java.

* passagem de mensagem.** No modelo de passagem de mensagens, módulos concorrentes interagem enviando mensagens um para o outro através de um canal de comunicação. Os módulos enviam mensagens e as mensagens recebidas para cada módulo estão em fila de espera para serem tratadas. Exemplos incluem:+ a e B podem ser dois computadores em uma rede, comunicando por conexões de rede.+ A e B podem ser um navegador web e um servidor web — a abre uma conexão com B, pede uma página web, e B envia os dados da página web de volta para A.+ A E B podem ser um cliente e servidor de mensagens instantâneas.+ A e B podem ser dois programas rodando no mesmo computador cuja entrada e saída foram conectados por um tubo, como `ls | grep` digitado em uma linha de comandos.## Processes, Threads, Time-slicting the message-passing and shared-memory modules are about how concurrent modules communicate. Os próprios módulos concorrentes vêm em dois tipos diferentes: processos e threads.**Processo**. Um processo é uma instância de um programa em execução que é * isolado* de outros processos na mesma máquina. Em particular, tem sua própria seção privada da memória da máquina.A abstração do processo é um * computador virtual*. Faz o programa sentir que tem a máquina inteira para si mesmo — como um computador novo foi criado, com memória Nova, apenas para executar esse programa.Assim como os computadores conectados através de uma rede, os processos normalmente não compartilham memória entre eles. Um processo não pode acessar a memória ou objetos de outro processo. Compartilhar memória entre processos é *possível* na maioria dos sistemas operacionais, mas precisa de esforço especial. Em contraste, um novo processo está automaticamente pronto para passar mensagens, porque é criado com fluxos de saída padrão &, que são o sistema`.fora` e ” System.in streams que usou em Java.**Segmento**. Um thread é um locus de controle dentro de um programa em execução. Pense nisso como um lugar no programa que está sendo executado, além da pilha de chamadas de método que levou a esse lugar para o qual será necessário retornar.Assim como um processo representa um computador virtual, a abstração de thread representa um *processador virtual*. Fazer um novo thread simula fazer um novo processador dentro do computador virtual representado pelo processo. Este novo processador virtual executa o mesmo programa e compartilha a mesma memória que outros threads em processo.Threads são automaticamente prontos para a memória compartilhada, porque threads compartilham toda a memória no processo. Ele precisa de um esforço especial para obter uma memória “thread-local” que é privada para um único thread. Também é necessário configurar a transmissão de mensagens explicitamente, criando e usando estruturas de dados de fila. Falaremos sobre como fazer isso numa leitura futura.

Como posso ter muitos fios concorrentes com apenas um ou dois processadores no meu computador? Quando há mais threads do que processadores, a concorrência é simulada por **corte de tempo**, o que significa que o processador muda entre threads. A figura à direita mostra como três threads T1, T2 e T3 podem ser fatiados no tempo em uma máquina que tem apenas dois processadores reais. Na figura, o tempo passa para baixo, então no primeiro processador está executando thread T1 e o outro está executando thread T2, e então o segundo processador muda para executar thread T3. Thread T2 simplesmente pára, até sua próxima fatia no mesmo processador ou outro processador.Na maioria dos sistemas, o corte de tempo acontece imprevisivelmente e não deterministicamente, o que significa que um fio pode ser parado ou retomado a qualquer momento.

mitx:c613ec53e92840a4a506f3062c994673 Processes & Threads# # Shared Memory Examplelet’s look at an example of a shared memory system. O ponto deste exemplo é mostrar que programação concorrente é difícil, porque pode ter bugs sutis.

Imagine que um banco tem máquinas de caixa que usam um modelo de memória compartilhada, para que todas as máquinas de caixa possam ler e escrever os mesmos objetos de conta na memória.Para ilustrar o que pode dar errado, vamos simplificar o banco para baixo para uma única conta, com um saldo dólar armazenados em `balance` variável e duas operações de `depósito` e `retirar` que simplesmente adicionar ou remover um dólar: “java// suponha que todas as máquinas de dinheiro compartilhamento de um único banco accountprivate static int saldo = 0;private static void depositar() { saldo = saldo + 1;}private static void sacar() { saldo = saldo – 1;}“Os clientes a utilizar as máquinas de dinheiro para fazer transações, como esta:“javadeposit(); // colocar um dólar inwithdraw(); // take it back out “‘ neste exemplo simples, cada transação é apenas um depósito de um dólar seguido de um levantamento de um dólar, por isso deve deixar o saldo na conta inalterado. Ao longo do dia, cada máquina de dinheiro da nossa rede está a processar uma sequência de operações de depósito/levantamento.”‘java / / each ATM does a bunch of transactions that / / modify balance, but leave it unchanged afterwardprivate static void cashMachine () {for (int i = 0; i < TRANSACTIONS_PER_MACHINE; ++i) {deposit (); / / put a dollar in Levant(); / por isso, no final do dia, independentemente de quantas máquinas de dinheiro estavam a funcionar, ou de quantas transacções processámos, devemos esperar que o saldo da conta ainda seja 0.Mas se executarmos este código, descobrimos frequentemente que o saldo no final do dia é *Não* 0. Se mais de uma chamada de “cashMachine ()” estiver a correr ao mesmo tempo — digamos, em processadores separados no mesmo computador — então o “saldo” pode não ser zero no final do dia. Porque não?## Separar-nos é uma coisa que pode acontecer. Suponha que duas máquinas de dinheiro, A E B, estão ambos trabalhando em um depósito ao mesmo tempo. Veja como o depósito() passo normalmente divide-se em baixo nível de instruções do processador:“get saldo (saldo=0)adicionar 1 escrever de volta o resultado (saldo=1)“Quando A e B estão em execução em simultâneo, estas instruções de baixo nível intercalar uns com os outros (algumas até poderiam ser simultâneas, em algum sentido, mas vamos se preocupar com intercalação por agora):”‘A get balance (balance=0) a add 1 A write back the result (balance=1) B get balance (balance=1) b add 1 B write back the result (balance=2)“This interleaving is fine — we end up with balance 2, so both a and B successful put in a dollar. Mas e se a intersecção fosse assim:` ‘ a get balance (balance=0) B get balance (balance=0)a add 1 B add 1 a write back the result (balance=1) B write back the result (balance=1)“the balance is now 1 — a’S dollar was lost! A E B leram o saldo ao mesmo tempo, computaram saldos finais separados, e depois correram para armazenar de volta o novo saldo — que não levou em conta o depósito do outro.## Race ConditionThis is an example of a * * race condition**. Uma condição de corrida significa que a correção do programa (a satisfação de pós-Condições e invariantes) depende do tempo relativo de eventos em computações simultâneas A E B. Quando isso acontece, dizemos ” A está em uma corrida com B.”Algumas interlivações de eventos podem ser OK, no sentido de que eles são consistentes com o que um único processo não-atual produziria, mas outras interlivações produzem respostas erradas — violando pós-condições ou invariantes.## Ajustando o Código não HelpAll estas versões do banco, código da conta apresentam a mesma condição de corrida:“java// versão 1private static void depositar() { saldo = saldo + 1;}private static void sacar() { saldo = saldo – 1;}“java`// versão 2private static void depositar() { saldo += 1;}private static void sacar() { saldo -= 1;} “”java / / version 3private static void deposit () {++balance;}private static void Draw () {–balance;}“Você não pode dizer apenas ao olhar para o código Java como o processador vai executá-lo. Você não pode dizer quais serão as operações indivisíveis — as operações atômicas — Não é atômica só porque é uma linha de Java. Ele não toca equilíbrio apenas uma vez só porque o identificador de equilíbrio ocorre apenas uma vez na linha. O compilador Java, e de fato o próprio processador, não se compromete com as operações de baixo nível que irá gerar a partir de seu código. Na verdade,um compilador Java moderno típico produz exatamente o mesmo código para todas as três versões!A lição chave é que você não pode dizer olhando para uma expressão se será seguro das condições de corrida.

## reordená-lo ainda é pior do que isso, na verdade. A condição de corrida no saldo da conta bancária pode ser explicada em termos de diferentes interligações de operações sequenciais em diferentes processadores. Mas na verdade, quando você está usando múltiplas variáveis e múltiplos processadores, você nem pode contar com mudanças nessas variáveis aparecendo na mesma ordem.Aqui está um exemplo: “‘ javaprivate Boolean ready = false; private int answer = 0; / / computeAnswer corre em um threadprivate void computeAnswer () {answer = 42; ready = true;}/ / useAnswer corre em um diferente threadprivate void useAnswer () {while (!pronto . yield ();} if (answer = = 0) throw new RuntimeException (“answer wasn’t ready!”);} “‘Nós temos dois métodos que estão sendo executados em threads diferentes. “computeAnswer” faz um cálculo longo, finalmente chegando com a resposta 42, que coloca na variável resposta. Em seguida, ele define a variável ‘pronto `para verdadeiro, a fim de sinalizar para o método que está rodando na outra thread,` useAnswer’, que a resposta está pronta para ela usar. Olhando para o código, “resposta” é definido antes de pronto é definido, assim que “useAnswer” vê “pronto” como verdadeiro, então parece razoável que ele pode assumir que a “resposta” será 42, certo? Menos.O problema é que Compiladores e processadores modernos fazem muitas coisas para tornar o código rápido. Uma dessas coisas é fazer cópias temporárias de variáveis como Resposta e pronto em armazenamento mais rápido (registros ou caches em um processador), e trabalhar com eles temporariamente antes de eventualmente armazená-los de volta para sua localização oficial em memória. O storeback pode ocorrer em uma ordem diferente do que as variáveis foram manipuladas em seu código. Aqui está o que pode estar acontecendo sob as capas (mas expresso em sintaxe Java para torná-lo claro). O processador está efetivamente criando duas variáveis temporárias, ‘tmpr` e ‘tmpa’, para manipular os campos prontos e responder:”‘javaprivate void computeAnswer () {boolean tmpr = ready; int tmpa = answer; tmpa = 42; tmpr = true; ready = tmpr; / / <– what happens if useAnswer() interleaves here? // ready está definido, mas a resposta não é. answer = tmpa;}“mitx:2bf4beb7ffd5437bbbb9c782b99b54e Race Conditions## Message Passing Example

Now let’s look at the message-passing approach to our bank account example.Agora não só são os módulos da máquina de dinheiro, mas as contas também são módulos. Os módulos interagem enviando mensagens uns aos outros. Os pedidos recebidos são colocados em fila para serem tratados um de cada vez. O remetente não pára de trabalhar enquanto espera por uma resposta ao seu pedido. Ele lida com mais pedidos de sua própria fila. A resposta ao seu pedido acaba por voltar como outra mensagem.Infelizmente, a transmissão de mensagens não elimina a possibilidade de condições raciais. Suponha que cada conta suporta as operações “get-balance” e “retirar”, com as mensagens correspondentes. Dois utilizadores, na caixa A e na caixa B, estão ambos a tentar levantar um dólar da mesma conta. Eles verifique o saldo do primeiro para certificar-se de que eles nunca retirar mais do que a conta possui, porque descobertos trigger de banco grande penalidades:“get-balanceif saldo >= 1, em seguida, retirar 1“O problema é novamente interleaving, mas esse time interleaving do que o *as mensagens enviadas para a conta do banco, em vez de a *instruções* executado por A e B. Se a conta começa com um dólar em ti, em seguida, o que intercalação de mensagens vai enganar A e B em pensar que tanto pode retirar um dólar, assim overdrawing a conta?Uma lição aqui é que você precisa escolher cuidadosamente as operações de um modelo de passagem de mensagens. “retirar-se-fundos suficientes” seria uma operação melhor do que apenas “retirar”.## A concorrência é difícil de testar e depurar se não o convencemos de que a concorrência é complicada, eis o pior. É muito difícil descobrir condições de corrida usando testes. E mesmo uma vez que um teste tenha encontrado um bug, pode ser muito difícil localizá-lo para a parte do programa que o causa.Bugs de concorrência exibem muito fraca reprodutibilidade. É difícil fazê-los acontecer da mesma maneira duas vezes. A intercalação de instruções ou mensagens depende do tempo relativo de eventos que são fortemente influenciados pelo ambiente. Atrasos podem ser causados por outros programas em execução, Outros tráfego de rede, decisões de agendamento do sistema operacional, variações na velocidade do relógio do processador, etc. Cada vez que você executa um programa contendo uma condição de corrida, você pode ter um comportamento diferente. Estes tipos de insetos são **heisenbugs**, que são não-determinísticos e difíceis de reproduzir, em oposição a um “bohrbug”, que aparece repetidamente sempre que você olha para ele. Quase todos os bugs na programação sequencial são bohrbugs.Um heisenbug pode até desaparecer quando se tenta olhar para ele com` println `ou`depurador’! A razão é que a impressão e depuração são muito mais lentas do que outras operações, muitas vezes 100-1000x mais lentas, que eles mudam drasticamente o timing das operações, e o interleaving. Assim, inserindo uma simples declaração de impressão na cashMachine (): “‘ javaprivate static void cashMachine () {for (int i = 0; i < TRANSACTIONS_PER_ machine; ++i) {deposit (); / / put a dollar in Levant (); / / take it back out System.as.println (equilíbrio); / / faz o erro desaparecer! }}“`…e de repente o equilíbrio é sempre 0, como desejado, e o bug parece desaparecer. Mas é apenas Mascarado, não é realmente fixo. Uma mudança de timing em algum outro lugar do programa pode de repente fazer o bug voltar.A concorrência é difícil de acertar. Parte do objectivo desta leitura é assustar-te um pouco. Ao longo das próximas leituras, veremos maneiras principiadas de projetar programas simultâneos para que eles estejam mais seguros desses tipos de bugs.mitx: 704b9c4db3c6487c9f1549956af8bfc8 testando simultaneamente# # resumo+ concorrência: vários cálculos em execução em simultâneo+ memória Partilhada & mensagem de passagem de paradigmas+ Processos & threads + Processo é como um computador virtual; thread é como um processador virtual+ condições de Corrida + Quando exatidão do resultado (pós-condições e invariantes) depende da temporização relativa de eventsThese idéias se conectar aos nossos três principais propriedades de um bom software, principalmente na forma ruim. A concorrência é necessária, mas causa sérios problemas para a correção. Vamos tratar desses problemas nas próximas leituras.+ * * A salvo dos insectos.** Bugs concurrencial são alguns dos bugs mais difíceis de encontrar e corrigir, e requerem um design cuidadoso para evitar. Fácil de entender.** Prever como o código concorrente pode se entrelaçar com outro código concorrente é muito difícil para programadores fazer. É melhor projetar de tal forma que os programadores não tenham que pensar nisso. + * * Pronto para a mudança.** Não particularmente relevante aqui.