Computação simultânea - Concurrent computing

Para uma discussão mais teórica, consulte Concurrency (ciência da computação) .
Paradigmas de programação

A computação simultânea é uma forma de computação na qual vários cálculos são executados simultaneamente - durante períodos de tempo sobrepostos - em vez de sequencialmente - com um sendo concluído antes do início do próximo.

Esta é uma propriedade de um sistema - seja um programa , computador ou rede - onde há um ponto de execução separado ou "thread de controle" para cada processo. Um sistema simultâneo é aquele em que um cálculo pode avançar sem esperar que todos os outros cálculos sejam concluídos.

A computação simultânea é uma forma de programação modular . Em seu paradigma, uma computação geral é fatorada em subcomputações que podem ser executadas simultaneamente. Os pioneiros no campo da computação simultânea incluem Edsger Dijkstra , Per Brinch Hansen e CAR Hoare .

Introdução

Veja também: Computação paralela

O conceito de computação simultânea é frequentemente confundido com o conceito relacionado, mas distinto, de computação paralela , embora ambos possam ser descritos como "vários processos em execução durante o mesmo período de tempo ". Na computação paralela, a execução ocorre no mesmo instante físico: por exemplo, em processadores separados de uma máquina multiprocessada , com o objetivo de acelerar os cálculos - a computação paralela é impossível em um único processador ( um núcleo ), como apenas um a computação pode ocorrer a qualquer instante (durante qualquer ciclo de clock único). Por outro lado, a computação simultânea consiste em tempos de vida do processo sobrepostos, mas a execução não precisa acontecer no mesmo instante. O objetivo aqui é modelar processos no mundo externo que acontecem simultaneamente, como vários clientes acessando um servidor ao mesmo tempo. Estruturar sistemas de software como compostos de várias partes simultâneas e comunicantes pode ser útil para lidar com a complexidade, independentemente de as partes poderem ser executadas em paralelo.

Por exemplo, os processos simultâneos podem ser executados em um núcleo intercalando as etapas de execução de cada processo por meio de fatias de tempo compartilhado : apenas um processo é executado por vez e, se não for concluído durante sua fatia de tempo, é pausado , outro processo começa ou continua e, mais tarde, o processo original é reiniciado. Dessa forma, vários processos estão no meio da execução em um único instante, mas apenas um processo está sendo executado naquele instante.

Cálculos simultâneos podem ser executados em paralelo, por exemplo, atribuindo cada processo a um processador ou núcleo de processador separado, ou distribuindo um cálculo através de uma rede. Em geral, entretanto, as linguagens, ferramentas e técnicas para programação paralela podem não ser adequadas para programação simultânea e vice-versa.

O tempo exato de quando as tarefas em um sistema simultâneo são executadas depende do agendamento , e as tarefas nem sempre precisam ser executadas simultaneamente. Por exemplo, dadas duas tarefas, T1 e T2:

  • T1 pode ser executado e concluído antes de T2 ou vice-versa (serial e sequencial)
  • T1 e T2 podem ser executados alternadamente (serial e simultâneo)
  • T1 e T2 podem ser executados simultaneamente no mesmo instante de tempo (paralelo e simultâneo)

A palavra "sequencial" é usada como antônimo para "simultâneo" e "paralelo"; quando estes são explicitamente distinguidos, simultâneo / sequencial e paralelo / serial são usados ​​como pares opostos. Uma programação na qual as tarefas são executadas uma por vez (em série, sem paralelismo), sem intercalação (sequencialmente, sem simultaneidade: nenhuma tarefa começa até que a tarefa anterior termine) é chamada de programação serial . Um conjunto de tarefas que podem ser agendadas em série é serializável , o que simplifica o controle de simultaneidade .

Coordenar o acesso a recursos compartilhados

O principal desafio no projeto de programas simultâneos é o controle da simultaneidade : garantir o sequenciamento correto das interações ou comunicações entre as diferentes execuções computacionais e coordenar o acesso aos recursos que são compartilhados entre as execuções. Os problemas potenciais incluem condições de corrida , impasses e falta de recursos . Por exemplo, considere o seguinte algoritmo para fazer saques de uma conta corrente representada pelo recurso compartilhado balance: 

bool withdraw(int withdrawal)
{
    if (balance >= withdrawal)
    {
        balance -= withdrawal;
        return true;
    } 
    return false;
}

Suponha que balance = 500e dois threads simultâneos façam as chamadas withdraw(300)e withdraw(350). Se a linha 3 em ambas as operações for executada antes da linha 5, ambas as operações descobrirão que balance >= withdrawalavalia para true, e a execução continuará subtraindo o valor da retirada. Porém, como os dois processos realizam seus saques, o valor total sacado acabará sendo superior ao saldo original. Esses tipos de problemas com recursos compartilhados se beneficiam do uso de controle de simultaneidade ou algoritmos sem bloqueio .

Vantagens

As vantagens da computação simultânea incluem:

  • Maior rendimento do programa - a execução paralela de um programa simultâneo permite que o número de tarefas concluídas em um determinado tempo aumente proporcionalmente ao número de processadores de acordo com a lei de Gustafson
  • Alta capacidade de resposta para entrada / saída - programas intensivos de entrada / saída geralmente esperam que as operações de entrada ou saída sejam concluídas. A programação simultânea permite o tempo que seria gasto esperando para ser usado para outra tarefa.
  • Estrutura de programa mais apropriada - alguns problemas e domínios de problemas são adequados para representação como tarefas ou processos simultâneos.

Modelos

Introduzidas em 1962, as redes de Petri foram uma das primeiras tentativas de codificar as regras de execução simultânea. A teoria do fluxo de dados posteriormente construída sobre eles, e as arquiteturas do fluxo de dados foram criadas para implementar fisicamente as ideias da teoria do fluxo de dados. Começando no final da década de 1970, cálculos de processo como Cálculo de Sistemas de Comunicação (CCS) e Processos Seqüenciais de Comunicação (CSP) foram desenvolvidos para permitir o raciocínio algébrico sobre sistemas compostos de componentes em interação. O cálculo π adicionou a capacidade de raciocínio sobre topologias dinâmicas.

Os autômatos de entrada / saída foram introduzidos em 1987.

Lógicas como o TLA + de Lamport e modelos matemáticos como traços e diagramas de eventos de Ator também foram desenvolvidos para descrever o comportamento de sistemas concorrentes.

A memória transacional do software pega emprestado da teoria do banco de dados o conceito de transações atômicas e os aplica aos acessos à memória.

Modelos de consistência

Artigo principal: Modelo de consistência

Linguagens de programação simultâneas e programas multiprocessados ​​devem ter um modelo de consistência (também conhecido como modelo de memória). O modelo de consistência define regras de como as operações na memória do computador ocorrem e como os resultados são produzidos.

Um dos primeiros modelos de consistência foi Leslie Lamport de consistência sequencial modelo. A consistência sequencial é a propriedade de um programa de que sua execução produz os mesmos resultados de um programa sequencial. Especificamente, um programa é sequencialmente consistente se "os resultados de qualquer execução forem os mesmos como se as operações de todos os processadores fossem executadas em alguma ordem sequencial, e as operações de cada processador individual aparecerem nesta sequência na ordem especificada por seu programa "

Veja também: Sequencial relaxado

Implementação

Vários métodos diferentes podem ser usados ​​para implementar programas simultâneos, como implementar cada execução computacional como um processo do sistema operacional ou implementar os processos computacionais como um conjunto de threads em um único processo do sistema operacional.

Interação e comunicação

Em alguns sistemas de computação simultâneos, a comunicação entre os componentes concorrentes é escondida do programador (por exemplo, usando futuros ), enquanto em outros deve ser tratada explicitamente. A comunicação explícita pode ser dividida em duas classes:

Comunicação de memória compartilhada
Os componentes simultâneos se comunicam alterando o conteúdo das localizações de memória compartilhada (exemplificado por Java e C # ). Esse estilo de programação simultânea geralmente precisa do uso de alguma forma de bloqueio (por exemplo, mutexes , semáforos ou monitores ) para coordenar entre as threads. Um programa que implementa adequadamente qualquer um desses é considerado thread-safe .
Comunicação de passagem de mensagem
Os componentes concorrentes se comunicam por meio da troca de mensagens (exemplificado por MPI , Go , Scala , Erlang e occam ). A troca de mensagens pode ser realizada de forma assíncrona, ou pode usar um estilo de "encontro" síncrono em que o remetente bloqueia até que a mensagem seja recebida. A passagem assíncrona de mensagens pode ser confiável ou não confiável (às vezes chamada de "enviar e orar"). A simultaneidade de passagem de mensagens tende a ser muito mais fácil de raciocinar do que a simultaneidade de memória compartilhada e é normalmente considerada uma forma mais robusta de programação simultânea. Uma ampla variedade de teorias matemáticas para compreender e analisar os sistemas de passagem de mensagens está disponível, incluindo o modelo de ator e vários cálculos de processo . A passagem de mensagens pode ser implementada de forma eficiente por meio de multiprocessamento simétrico , com ou sem coerência de cache de memória compartilhada .

A memória compartilhada e a simultaneidade de passagem de mensagens têm características de desempenho diferentes. Normalmente (embora nem sempre), a sobrecarga de memória por processo e a sobrecarga de comutação de tarefas são menores em um sistema de passagem de mensagens, mas a sobrecarga da passagem de mensagens é maior do que para uma chamada de procedimento. Essas diferenças geralmente são superadas por outros fatores de desempenho.

História

A computação concorrente foi desenvolvida a partir de trabalhos anteriores sobre ferrovias e telegrafia , do século 19 e início do século 20, e alguns termos datam desse período, como semáforos. Isso surgiu para resolver a questão de como lidar com vários trens no mesmo sistema ferroviário (evitando colisões e maximizando a eficiência) e como lidar com várias transmissões em um determinado conjunto de fios (melhorando a eficiência), como por meio de multiplexação por divisão de tempo (1870s )

O estudo acadêmico de algoritmos concorrentes começou na década de 1960, com Dijkstra (1965) considerado o primeiro artigo neste campo, identificando e resolvendo exclusão mútua .

Prevalência

A simultaneidade é generalizada na computação, ocorrendo desde hardware de baixo nível em um único chip até redes mundiais. Seguem exemplos.

No nível da linguagem de programação:

No nível do sistema operacional:

No nível da rede, os sistemas em rede geralmente são simultâneos por natureza, pois consistem em dispositivos separados.

Linguagens que suportam programação simultânea

Linguagens de programação simultâneas são linguagens de programação que usam construções de linguagem para simultaneidade . Essas construções podem envolver multi-threading , suporte para computação distribuída , passagem de mensagens , recursos compartilhados (incluindo memória compartilhada ) ou futuros e promessas . Essas linguagens às vezes são descritas como linguagens orientadas à concorrência ou linguagens de programação orientadas à concorrência (COPL).

Hoje, as linguagens de programação mais comumente usadas que têm construções específicas para simultaneidade são Java e C # . Ambas as linguagens usam fundamentalmente um modelo de simultaneidade de memória compartilhada, com bloqueio fornecido por monitores (embora os modelos de transmissão de mensagens possam e tenham sido implementados em cima do modelo de memória compartilhada subjacente). Das linguagens que usam um modelo de simultaneidade de passagem de mensagens, Erlang é provavelmente a mais usada na indústria atualmente.

Muitas linguagens de programação concorrentes foram desenvolvidas mais como linguagens de pesquisa (por exemplo, Pict ) do que como linguagens para uso em produção. No entanto, línguas como Erlang , Limbo e occam tiveram uso industrial várias vezes nos últimos 20 anos. Uma lista não exaustiva de linguagens que usam ou fornecem recursos de programação simultânea:

  • Ada - finalidade geral, com suporte nativo para passagem de mensagens e simultaneidade baseada em monitor
  • Alef - simultâneo, com threads e passagem de mensagens, para a programação do sistema nas primeiras versões do Plano 9 da Bell Labs
  • Alice - extensão para ML padrão , adiciona suporte para concorrência via futuros
  • Ateji PX - extensão para Java com primitivas paralelas inspiradas no cálculo π
  • Axum - específico de domínio, simultâneo, com base no modelo de ator e .NET Common Language Runtime usando uma sintaxe semelhante a C
  • BMDFM —Binary Modular DataFlow Machine
  • C ++ —std :: thread
  • Cω (C omega) —para pesquisa, estende C #, usa comunicação assíncrona
  • C # - suporta computação simultânea usando lock, yield, também desde a versão 5.0 assíncrona e aguardar palavras-chave introduzidas
  • Clojure - dialeto funcional moderno do Lisp na plataforma Java
  • Concurrent Clean - programação funcional, semelhante a Haskell
  • Coleções simultâneas (CnC) - Alcança paralelismo implícito independente do modelo de memória, definindo explicitamente o fluxo de dados e controle
  • Concurrent Haskell - linguagem funcional pura e preguiçosa que opera processos simultâneos na memória compartilhada
  • ML concorrente - extensão simultânea de ML padrão
  • Pascal simultâneo - por Per Brinch Hansen
  • Curry
  • D - linguagem de programação de sistema multiparadigma com suporte explícito para programação simultânea ( modelo de ator )
  • E - usa promessas para evitar impasses
  • ECMAScript - usa promessas para operações assíncronas
  • Eiffel - por meio de seu mecanismo SCOOP baseado nos conceitos de Design by Contract
  • Elixir - linguagem dinâmica e funcional de metaprogramação em execução no Erlang VM.
  • Erlang - usa a passagem de mensagem assíncrona sem nada compartilhado
  • FAUST - funcional em tempo real, para processamento de sinal, o compilador fornece paralelização automática via OpenMP ou um agendador de roubo de trabalho específico
  • Fortran - coarrays e do concorrente fazem parte do padrão Fortran 2008
  • Go —para programação de sistema, com um modelo de programação simultânea baseado em CSP
  • Haskell - linguagem de programação funcional simultânea e paralela
  • Hume - funcional , simultâneo, para ambientes de espaço e tempo limitados onde os processos de autômatos são descritos por padrões de canais síncronos e passagem de mensagens
  • Io - simultaneidade baseada em fator
  • Janus - apresenta questionadores e caixas distintos para variáveis ​​lógicas, canais de bolsa; é puramente declarativo
  • Java - classe de thread ou interface executável
  • Julia - "primitivos de programação simultânea: Tarefas, espera assíncrona, Canais."
  • JavaScript - por meio de web workers , em um ambiente de navegador, promessas e retornos de chamada .
  • JoCaml - baseado em canais simultâneos e distribuídos, extensão de OCaml , implementa o cálculo de junção de processos
  • Junte-se a Java - simultâneo, com base na linguagem Java
  • Joule - baseado em fluxo de dados, comunica-se por passagem de mensagem
  • Joyce - simultâneo, ensinando, baseado em Concurrent Pascal com recursos de CSP por Per Brinch Hansen
  • LabVIEW - gráfico, fluxo de dados, funções são nós em um gráfico, dados são fios entre os nós; inclui linguagem orientada a objetos
  • Limbo —relativo a Alef , para a programação do sistema no Inferno (sistema operacional)
  • MultiLisp - variante do esquema estendida para oferecer suporte ao paralelismo
  • Modula-2 - para programação de sistema, por N. Wirth como sucessor de Pascal com suporte nativo para corrotinas
  • Modula-3 - membro moderno da família Algol com amplo suporte para threads, mutexes, variáveis ​​de condição
  • Newsqueak - para pesquisa, com canais como valores de primeira classe; predecessor de Alef
  • occam - fortemente influenciado pelos processos sequenciais de comunicação (CSP)
  • Orc - fortemente concorrente, não determinístico, baseado na álgebra de Kleene
  • Oz-Mozart —multiparadigma, suporta estado compartilhado e simultaneidade de passagem de mensagens, e futuros
  • Parasail -object-orientado, paralelamente, livre de ponteiros, condições de corrida
  • Pict - essencialmente uma implementação executável do cálculo π de Milner
  • Raku inclui classes para threads, promessas e canais por padrão
  • Python - usa paralelismo baseado em thread e paralelismo baseado em processo
  • Reia - usa a passagem de mensagem assíncrona entre objetos sem compartilhamento
  • Vermelho / Sistema - para programação do sistema, com base em Rebol
  • Rust - para programação de sistema, usando transmissão de mensagens com semântica de movimento, memória imutável compartilhada e memória mutável compartilhada.
  • Scala — propósito geral, projetado para expressar padrões de programação comuns de uma forma concisa, elegante e segura
  • SequenceL - funcional para fins gerais, os objetivos principais do design são facilidade de programação, clareza e legibilidade do código e paralelização automática para desempenho em hardware de vários núcleos e, comprovadamente, livre de condições de corrida
  • SR - para pesquisa
  • SuperPascal - concomitante, para ensino, baseado em Concurrent Pascal e Joyce por Per Brinch Hansen
  • Unicon - para pesquisa
  • TNSDL - para o desenvolvimento de trocas de telecomunicações, usa passagem de mensagem assíncrona
  • Linguagem de descrição de hardware VHSIC ( VHDL ) —IEEE STD-1076
  • XC - subconjunto simultâneo estendido da linguagem C desenvolvido por XMOS , com base em processos sequenciais de comunicação , construções integradas para E / S programáveis

Muitas outras linguagens fornecem suporte para simultaneidade na forma de bibliotecas, em níveis quase comparáveis ​​com a lista acima.

Veja também

Notas

Referências

Fontes

  • Patterson, David A .; Hennessy, John L. (2013). Organização e projeto do computador: a interface de hardware / software . The Morgan Kaufmann Series in Computer Architecture and Design (5 ed.). Morgan Kaufmann. ISBN 978-0-12407886-4.

Leitura adicional

links externos