Programação concorrente - Uma abordagem em operações atômicas

Programação concorrente

Uma abordagem em operações atômicas

Lucas Moura Belo

Belo Horizonte, outubro de 2019

1. AMBIENTES CONCORRENTES

Concorrência é a habilidade de se executar diferentes partes ou unidades de um programa fora de ordem ou em ordem parcial, sem afetar o resultado final. A programação concorrente oferece vantagens relacionadas a desempenho, porém podem gerar problemas inesperados e difíceis de serem identificadas.

1.1 Ambientes thread-safe

Um bloco de código é chamado de thread-safe ao garantir segurança na manipulação de estruturas de dados compartilhadas entre threads. Apesar de dizermos que estas operações acontecem ao mesmo tempo, na prática não é bem assim. O time slicing é uma técnica usada por sistemas operacionais que divide o tempo do processador entre um número de threads. O sistema operacional atribui uma fatia de tempo do processador para uma thread após a outra, dependendo das necessidades e a prioridade de cada uma. Quando a fatia de tempo chega ao fim, o sistema operacional suspende a execução da thread e uma próxima começa a funcionar.

Existem diferentes técnicas que garantem as premissas de um código thread-safe, mas muitas vezes elas resultam em queda de performance. Esse problema é bastante observado em técnicas de exclusão mútua, logo que o objetivo dessa técnica é prevenir acesso simultâneo a um recurso compartilhado.

O exemplo a seguir mostra uma abordagem de exclusão mútua (synchronized) para garantir que um bloco de código seja thread-safe:

{ TMyThread }

procedure TMyThread.Increment;

begin

  Inc(FCounter);

  WriteLn(Format('Inc operation (%d) requested by thread %d and performed by thread %d', [FCounter, ThreadID, GetCurrentThreadId()]));

end;

procedure TMyThread.Decrement;

begin

  Dec(FCounter);

  WriteLn(Format('Dec operation (%d) requested by thread %d and performed by thread %d', [FCounter, ThreadID, GetCurrentThreadId()]));

end;

procedure TMyThread.Execute;

begin

  inherited;

  TThread.Synchronize(nil, Increment);

  TThread.Synchronize(nil, Decrement);

end;

procedure Main;

const

  THREAD_COUNT: integer = 2;

var

  LThreads: array of TThread;

  I: Integer;

begin

  SetLength(LThreads, THREAD_COUNT);

  WriteLn('TMyThread.Count is a shared resource. A thread-safe code must be written to inc and dec operations.');

  WriteLn('After all threaded operations, the Counter variable must be with the same   value as is stared.');

  WriteLn(#13#10);

  WriteLn(Format('Counter is started with value %d', [TMyThread.Counter]));

  for I := 0 to Pred(THREAD_COUNT) do begin

    //All threads are initially created suspended

    LThreads[I] := TMyThread.Create(true);

  end;

  for I := 0 to Pred(THREAD_COUNT) do begin

    //Resume all threads

    LThreads[I].Resume;

  end;

  for I := 0 to Pred(THREAD_COUNT) do begin

    //Wait for all threads

    LThreads[I].WaitFor;

  end;

  WriteLn(Format('Counter variable has ended with value %d', [TMyThread.Counter]));

  ReadLn;

end;

begin

  Main;

end. 

  As operações executadas por cada thread foram sincronizadas com a thread principal (Main Thread), ou seja, a execução das operações foram serializadas a apenas uma thread. Operações desse tipo são chamadas de operações bloqueantes, essas operações resultam em perda de performance. Outros exemplos de operações bloqueantes são mutexes, semaphores e critical sections.

Operações bloqueantes podem oferecer outros problemas, como deadlocks, livelocks e priority inversion (problemas de inanição).

2. OPERAÇÕES ATÔMICAS

Algorítimos non-blocking (não bloqueantes) ou lock-free (livres de trava) são uma alternativa às tradicionais implementações bloqueantes.

Uma estrutura não bloqueante gasta a maior parte do seu tempo em execuções paralelas do que em execuções serializadas, resultando em aumento de performance em processadores multi-core, logo que o acesso na estrutura de dados não precisa ser serializada para continuar coerente.

Com algumas exceções, algorítimos não bloqueantes usam primitivas atômicas read-modify-write que o próprio hardware deve prover. O mais notável exemplo dessa primitiva é o algorítimo compare and swap.

Operações atômicas são aquelas que são executadas de forma independente de qualquer outro processo. Uma operação em uma estrutura de dados compartilhada é atômica se ela completar sua operação em apenas uma instrução de processamento relativo às outras threads. Quando uma escrita atômica é executada em uma estrutura de dados compartilhada, nenhuma outra thread pode observar a modificação antes que ela seja feita por inteiro. Quando uma leitura é feita em uma estrutura de dados compartilhada, sua leitura e feita por inteiro, assim como o valor estava em determinado momento.

Sem essas garantias, a programação lock-free seria impossível, logo que diferentes threads nunca poderiam manipular uma estrutura de dados compartilhada ao mesmo tempo.

A violação dessas regras, e o uso de operações não atômicas por threads, levam a uma situação conhecida como data race, ou em um conceito mais geral race condition. Esse problema pode ser explicado pela condição onde o estado de uma estrutura de dados observada em determinado momento pode ser alterada por outra thread antes que seu estado seja escrito. Esse problema pode ser visto no exemplo a seguir:

const

CYCLES: integer = 100000;

{ TRaceConditionProblemThread }

procedure TRaceConditionProblemThread.Execute;

var

  I: integer;

begin

  inherited;

  for I := 0 to Pred(CYCLES) do begin

    Inc(FCounter);

  end;

end;

procedure Main;

const

  THREAD_COUNT: integer = 2;

var

  LThreads: array of TThread;

  I: Integer;

begin

  ReadLn;

  Writeln('Non-atomic op read and write (load/store) operations.');

  WriteLn(Format('Counter has started with value %d and will perform %d cycles and  counter should end off with value %d', [

  TRaceConditionProblemThread.Counter,

  CYCLES,

  THREAD_COUNT * CYCLES]));

  SetLength(LThreads, THREAD_COUNT);

  for I := 0 to THREAD_COUNT - 1 do begin

    LThreads[I] := TRaceConditionProblemThread.Create(true);

  end;

  for I := 0 to THREAD_COUNT - 1 do begin

    LThreads[I].Resume;

  end;

  for I := 0 to THREAD_COUNT - 1 do begin

    LThreads[I].WaitFor;

  end;

  WriteLn(Format('Counter has finished with value %d',   [TRaceConditionProblemThread.Counter]));

  Readln;

end;

begin

  Main;

end.

A operação inc foi executada por duas threads distintas. Cada uma realizou 100.000 ciclos de incremento na variável “Counter” o que deveria resultar um valor de 200.000 na variável “Counter”.

2.1 Operações de baixo nível

Logo que a atomicidade é garantida pela execução de instrução única sem interrupção, e utilizamos apenas uma instrução Inc(FCounter) devemos ver mais a fundo o porque da operação realizada acima não ser atômica.

Primeiramente, uma operação de alto nível pode ser convertida para várias instruções de baixo nível, o que poderia violar a condição de execução de uma única instrução. Vejamos:

A instrução de alto nível Inc(FCounter) foi convertida em apenas uma instrução de baixo nível, utilizando o mnemônico “inc”, o que não explica o problema de condição de corrida, logo que a operação de incremento foi executada em apenas uma instrução de baixo nível. 

A decomposição em baixo nível (nível de hardware) dessa instrução resulta no carregamento do valor contido no endereço de memória para um registrador. Em seguida ocorre o incremento e, por fim, o valor é salvo no endereço de memória inicial. Algo assim:

load temp, [eax]

inc temp

store [eax], temp

Este processo de decomposição em nível de hardware é conhecido como uOps pela Intel e rOps pela AMD, de forma generalizada é chamada de “mini-op”. Porém, a decomposição em “mini-op” é irrelevante, logo que um único núcleo de cpu não pode ser interrompido no meio de uma instrução, garantindo que operações em um único núcleo de cpu sejam atômicas, não importando como sejam feitas. 
 

2.2 Processadores multi-core

Então, se a operação foi executada em apenas uma instrução onde esta não pode ser interrompida, sendo por natureza atômica, o que ocasionou o problema de condição de corrida no incremento da variável “Counter”? A resposta está nos processadores com mais de um núcleo. As operações de baixo nível (nível de hardware) são executadas pelos núcleos do processador, e esses núcleos compartilham o cache da cpu e a memória ram. Resumindo, a operação é atômica para o núcleo da cpu mas não entre os demais núcleos da cpu.

Para testar se uma operação de instrução única é atômica em processadores de núcleo único, podemos fazer o seguinte teste ao executar o exemplo anterior:

Ao definir a afinidade para um processo, definimos em quais núcleos o processo pode executar operações. A seguir o retorno da execução do exemplo anterior ao ser executado apenas no núcleo 0:

O resultado final das operações de incremento foi de 200.000, assim como era esperado. Este exemplo prova que operações com uma única instrução por natureza são atômicas quando executadas em um único núcleo do processador.

Mas os benefícios dos processadores com mais de um núcleo não são perdidos por esta questão. Assim como já foi dito, uma operação em uma estrutura de dados compartilhada é atômica se ela completar sua operação em apenas uma instrução de processamento relativo às outras threads. O sistema operacional é quem decide em qual núcleo uma thread executará suas operações, e nada garante que o núcleo inicial da execução será o mesmo ao fim das operações. Então o que precisamos é garantir que as instruções executadas em determinada estrutura de dados sejam executadas sem a interferência de outra thread.

3. BUS CONTROLLER

O control bus é usada pela cpu para se comunicar com os periféricos do computador. Essa comunicação é feita pela transmissão de sinais entre a cpu e os demais componentes. O system bus consiste em três tipos de barramentos:

* Data bus: recebe os dados que precisam ser processados;

* Address bus: determina para onde os dados devem ser enviados;

* Control bus: determina o processamento de dados.

É através do control bus que o cpu determina quando o sistema está recebendo ou enviando dados. Este componente é responsável por regular em qual direção as informações de leitura e escrita devem ir.

Assim o control bus se torna importante ao executar operações atômicas. Com a ajuda do control bus conseguimos garantir que uma operação de uma thread ocorra sem a interferência de outra thread.

3.1 O prefixo de instrução “lock”

O exemplo a seguir mostra como escrever um incrementador atômico utilizando o prefixo de instrução “lock”.

program atomicincrement;

{$APPTYPE CONSOLE}

uses

  SysUtils,

  Classes,

  Windows;

type

  TAtomicIncrementLockPrefix = class(TThread)

  strict private

    class var FCounter: integer;

  protected

    procedure Execute; override;

  public

    class property Counter: integer read FCounter;

  end;

  TAtomic = class sealed

  public

    class procedure Increment(var AValue: integer); static;

  end;

const

  CYCLES: integer = 100000;

{ TAtomicCheck }

procedure TAtomicIncrementLockPrefix.Execute;

var

  I: integer;

begin

  inherited;

  for I := 0 to Pred(CYCLES) do begin

    TAtomic.Increment(FCounter);

  end;

end;

procedure Main;

const

  THREAD_COUNT: integer = 2;

var

  LThreads: array of TThread;

  I: Integer;

begin

  Writeln('Atomic op read and write (load/store) operations.');

  WriteLn(Format('Counter has started with value %d and will perform %d cycles and counter should end off with value %d', [

  TAtomicIncrementLockPrefix.Counter,

  CYCLES,

  THREAD_COUNT * CYCLES]));

  SetLength(LThreads, THREAD_COUNT);

  for I := 0 to THREAD_COUNT - 1 do begin

    LThreads[I] := TAtomicIncrementLockPrefix.Create(true);

  end;

  for I := 0 to THREAD_COUNT - 1 do begin

    LThreads[I].Resume;

  end;

  for I := 0 to THREAD_COUNT - 1 do begin

    LThreads[I].WaitFor;

  end;

  WriteLn(Format('Counter has finished with value %d', [TAtomicIncrementLockPrefix.Counter]));

  Readln;

end;

{ TAtomic }

class procedure TAtomic.Increment(var AValue: integer);

asm

  lock inc dword ptr [eax];

end;

begin

  Main;

end.

O prefixo “lock” garante que a CPU tenha propriedade exclusiva da linha de cache na duração da operação, garantindo também que a ordem das operações seja garantida. Isso pode ser alcançado através do bus lock. O bus será bloqueado pelo mesmo tempo que durar a instrução.

4. REORGANIZAÇÃO DE OPERAÇÕES E O PROBLEMA DE VISIBILIDADE

Outros problemas podem resultar em instruções não atômicas. A reorganização das operações e o problema de visibilidade das variáveis são exemplos de otimizações feitas pelo compilador ou pelo próprio processador que podem promover execuções não atômicas.

Basicamente o problema de visibilidade é causado pela não escrita de volta na memória principal, o que deveria acontecer de forma imediata. Esse problema acontece quando uma cópia da estrutura de dados é mantida no cache do núcleo da cpu.

O problema da reorganização das operações pode ser visto a seguir:

procedure Main;

var

  a: integer;

  b: integer;

begin

  a := 1;

  b := 2;

  Inc(a);

  Inc(b);

end;

O bloco de código anterior pode ser alterado para outra sequência sem perder a semântica:

procedure Main;

var

  a: integer;

  b: integer;

begin

  a := 1;

  Inc(a);

  b := 2;

  Inc(b);

end;

Mas o seguinte programa pode perder a semântica em caso de reorganização de instruções.

TInstructionReordering = class

private

  FData: array[0..4] of integer;

  FIsReady: Boolean;

public

  procedure InitData;

  procedure SumData;

end;

{ TInstructionReordering }

procedure TInstructionReordering.InitData;

var

  I: Integer;

begin

  for I := Low(FData) to High(FData) do begin

    FData[I] := I;

  end;

  FIsReady := true;

end;

procedure TInstructionReordering.SumData;

var

  I: Integer;

  LSum: Integer;

begin

  if not (FIsReady) then Exit;

  LSum := 0;

  for I := Low(FData) to High(FData) do begin

    LSum := LSum + FData[I];

  end;

  WriteLn(Format('Sum: %d', [LSum]));

  Readln;

end;

Supondo que duas threads estão sendo executadas, uma lendo e outra escrevendo, a thread de leitura estará sempre chamando o método “SumData”. Em algum momento a thread de escrita vai chamar o método “InitData” para inicializar os dados. A variável “FIsReady” foi iniciada com “false”, e somente será alterada para “true” quando a operação de escrita terminar. Assim, somente no fim da escrita a thread de leitura conseguirá ler os valores para serem somados. Mas, caso as instruções contidas no método “InitData” sejam reorganizados e a instrução na variável “FIsReady” aconteça antes da inicialização dos valores, uma operação não atômica vai acontecer.

4.1 A keyword “volatile”

Estes problemas são bastante conhecidos por desenvolvedores JAVA, mas podem ser facilmente contornados pela keyword “volatile”. O problema de reorganização de instruções não é visto por desenvolvedores Delphi, logo que o compilador Delphi não executa eliminação de subexpressões comuns (CSE) em expressões não locais quando há chamadas para métodos non-inlined, ou seja, métodos que não utilizam a keyword “inline”; e o compilador não realiza otimizações interprocedurais.

5. CONCLUSÃO

Ambientes concorrentes são desafiadores. Apresentam aumento significativo na dificuldade de manutenção da aplicação, exigindo conhecimento profundo dos desenvolvedores para que não caiam em algumas “armadilhas”. Contudo, os ganhos em desempenho justificam sua prática.

Operações atômicas apresentam vantagens quando comparadas com outras premissas que tornam um bloco de código thread-safe. Devem ser preferidas em aplicações que necessitam alta disponibilidade e alto desempenho.