C# Programação Paralela — Resolução LeetCode 1195 Fizz Buzz Multithreaded

Atualmente é muito comum nos depararmos com problemas que precisamos recorrer ao processamento paralelo para atingirmos, de maneira mais eficiente, a solução desejada. Entretanto, ao utilizarmos recursos de programação paralela nos deparamos com alguns problemas que não estão presentes quando adotamos soluções “single thread”, tais como:

1. Gerenciamento de acesso a recursos, concorrência;
2. Segmentação das atividades para possibilitar o paralelismo;
3. Orquestração dos processamentos;
4. Gerenciamento de finalizações

Neste artigo não pretendo me aprofundar nos conceitos e desafios da programação paralela, e sim na resolução de um desafio sobre o tema que encontrei no portal LeetCode, Fizz Buzz Multithreaded

Fiquem a vontade para criticar a solução adotada, ou propor novos desafios, pois acredito que este é um ótimo meio de desenvolvimento de skills e, para mim, diversão :)

Problema

Como citado, resolverei o problema encontrado na plataforma LeetCode, 1195 Fizz Buzz Multithreaded, que consiste em escrever um programa que imprima uma string, representando números de 1 até n, onde:

• Se o número for divisível por 3, deve ser impresso “fizz”;
• Se o número for divisível por 5, deve ser impresso “buzz”;
• Se o número for divisível por 3 e 5, ambos, deve ser impresso “fizzbuzz”;

Exemplo: para entrada 15, n=15, deve ser impresso

1, 2, fizz, 4, buzz, fizz, 7, 8, fizz, buzz, 11, fizz, 13, 14, fizzbuzz

A plataforma expõe a estrutura da classe responsável por essa impressão:

class FizzBuzz {
  public FizzBuzz(int n) { ... }               // constructor
  public void fizz(printFizz) { ... }          // only output "fizz"
  public void buzz(printBuzz) { ... }          // only output "buzz"
  public void fizzbuzz(printFizzBuzz) { ... }  // only output "fizzbuzz"
  public void number(printNumber) { ... }      // only output the numbers
}

As regras apresentadas até aqui são relativamente simples, mas são adicionados outros 4 requisitos relacionados a programação paralela.

Implementar uma versão multithreaded da classe FizzBuzz, representada acima, que será consumida por quatro threads, sendo:

• Thread A chamará o método Fizz, para imprimir fizz, conforme regra apresentada anteriormente;
• Thread B chamará o método Buzz, para imprimir buzz;
• Thread C chamará o método FizzBuzz, para imprimir fizzbuzz;
• Thread D chamará o método Number, para imprimir os números;

Solução

Implementação da regra “fizz”, “buzz” e “fizzbuzz”

Primeiramente implementei as regras para saber se devemos imprimir “fizz”, “buzz”, “fizzbuzz” ou o próprio número, portando escrevi três métodos privados para essa finalizada.

private bool IsFizz()
{
   return
      (this.currentNumber % 3 == 0)
      && (this.currentNumber % 5 != 0);
}
private bool IsBuzz()
{
   return
      (this.currentNumber % 5 == 0)
      && (this.currentNumber % 3 != 0);
}
private bool IsFizzBuzz()
{
   return
      (this.currentNumber % 3 == 0)
      && (this.currentNumber % 5 == 0);
}

Para sabermos se devemos imprimir o próprio número basta saber que ele não é Fizz nem Buzz.

Estratégia Multithread

Para orquestração da ordem de impressão, utilizei quadro SemaphoreSlim, que são instanciados no construtor da classe FizzBuzz, e um CancellationTokenSource para sinalizarmos o fim do processamento. O construtor ficou como abaixo:

public FizzBuzz(int n)
{
   this.n = n;
   this.currentNumber = 0;
   this.semaphoreFizz = new SemaphoreSlim(0, 1);
   this.semaphoreBuzz = new SemaphoreSlim(0, 1);
   this.semaphoreFizzBuzz = new SemaphoreSlim(0, 1);
   this.semaphoreNumber = new SemaphoreSlim(0, 1);
   this.ts = new CancellationTokenSource();
   this.MoveToNextNumber();
}

Os SemaphoreSlim são utilizados para orquestrar a execução dos métodos Fizz, Buzz, Fizzbuzz e Number, essa orquestração ocorre no método MoveToNextNumber.

private void MoveToNextNumber()
{
   this.isFinalized = Interlocked.Increment(ref this.currentNumber) > this.n;
if (this.isFinalized)
   ts.Cancel();
else if (IsFizzBuzz())
   semaphoreFizzBuzz.Release();
else if (IsFizz())
   semaphoreFizz.Release();
else if (IsBuzz())
   semaphoreBuzz.Release();
else
   semaphoreNumber.Release();
}

Este método incrementa a variável currentNumber, até o alcançar o valor de n, e determina qual SemaphoreSlim deve ser liberado para próxima execução.

Nos métodos Fizz, Buzz, Fizzbuzz e Number, também é chamado o método MoveToNextNumber para que seja incrementado a variável currentNumber e acionado o próximo SemaphoreSlim, funcionando como um Workflow até atingir o n.

// only output "fizz"
public void Fizz(Action printFizz)
{
   while (!ts.IsCancellationRequested)
   {
      try
      {
         semaphoreFizz.Wait(ts.Token);
      }
      catch (OperationCanceledException) { return; }
      printFizz();
      
      MoveToNextNumber();
   }
}
// only output "buzz"
public void Buzz(Action printBuzz) 
{
   while (!ts.IsCancellationRequested) 
   {
      try
      {
         semaphoreBuzz.Wait(ts.Token);
      }
      catch (OperationCanceledException) { return; }
      printBuzz();
      MoveToNextNumber();
   }
}
// only output "fizzbuzz"
public void Fizzbuzz(Action printFizzBuzz)
{
   while (!ts.IsCancellationRequested)
   {
      try
      {
         semaphoreFizzBuzz.Wait(ts.Token);
      }
      catch (OperationCanceledException) { return; }
      printFizzBuzz();
      MoveToNextNumber();
   }
}
// only output the numbers
public void Number(Action<int> printNumber)
{
   while (!ts.IsCancellationRequested)
   {
      try
      {
         semaphoreNumber.Wait(ts.Token);
      }
      catch (OperationCanceledException) { return; }
      printNumber(this.currentNumber);
      MoveToNextNumber();
   }
}

Essa foi a solução adotada para esse problema e gostaria muito de saber sua opinião. Você faria diferente? Opinem a vontade.

O código fonte esta disponível no meu Github.

Até o próximo desafio!