Mês: março 2014

Programação Paralela – Parte 2 – Locks em threads

O que é um lock?

Há situações em threads que precisamos fazer com que uma thread espera a outra, dado que ambas pretendem acessar um recurso que não pode ser acessado simultaneamente. Neste caso, utilizamos locks.

O problema é que sempre que uma thread espera por um lock, ela está consumindo recursos, gerando trabalho para o escalonador do sistema operacional e não está fazendo nada. Esse comportamento pode gerar problemas de desempenho.

Locks

Como explicado no post anterior (Programação paralela – Parte 1), threads compartilham o heap. Dessa maneira, eventualmente queremos evitar que as threads concorram pelos mesmos recursos. Para isso, existem objetos de sincronização, como no exemplo abaixo:

public void DoSomething()
{
    lock(this)
    {
         //Trecho que executará somente com uma thread de cada vez.
    }
}

O trecho protegido por lock, fará com que as threads não entrem simultaneamente no mesmo trecho. Existem diversos outros objetos de sincronização, inclusive que impedem que mais de um processo acesse o mesmo recurso simultaneamente. Eles ficam no namespace System.Threading.

Corrida de saco

corridadesaco

O grande problema de usarmos uma infinidade de threads com diversos pontos de sincronização (locks) é que nossas threads ficarão realizando uma espécie de corrida de sacos. Uma anda um pouquinho, mas precisa esperar a outra liberar um recurso, fazendo com que na média, tudo fique mais lento.

Para exemplificar, alterei o exemplo anterior, a parte que cada uma das threads executa, para o seguinte código:

        private void DequeueAndProcess(Queue<Job> queue)
        {
            while (true)
            {
                Job job = null;
                lock (queue)
                {
                    if (queue.Count > 0)
                        job = queue.Dequeue();

                    if (job == null)
                    {
                        Thread.Sleep(0);
                        continue;
                    }
                    job.JobDelegate();
                    job.JobEndedNotifier.Set();
                }
            }
        }

Neste caso, obtemos os seguintes tempos:

ProcessamentoParalelo-pt2-1

O exemplo é bastante exagerado, pois todo o processamento está sendo serializado dado que somente uma thread consegue processar o trecho protegido pelo lock, mas para fins didáticos, nos ajuda a entender porque muitas vezes o processamento multi-thread concorrendo por vários recursos fica pior do que o processamento single-threaded. A reposta é que além do custo do processamento, temos todo o custo de gerenciar as threads. Como desenvolvedor, não sentimos este custo, mas o sistema operacional sem dúvida sente.

Deadlocks

deadlock

Se deadlocks em bancos de dados incomodam, deadlocks em threads fazem você sentir saudades dos de banco de dados. O processo é o mesmo: duas threads que dependem de mais de um recurso tentam os obter forma inversa. O sintoma é bem diferente: as threads envolvidas no deadlock simplesmente congelam. Diferentemente do banco de dados, não existe um recurso que automaticamente escolhe uma thread como vítima, e automaticamente a mata. Você precisa desenvolver este mecanismo por sua conta.

Por sorte, deadlocks em threads são tão raros quanto um deadlock na vida real, mas como a foto acima ilustra, eles acontecem.

I/O

Como regra geral, handles também são recursos que não suportam concorrência. O mesmo mecanismo de forçar locks deve ser utilizado para evitar que duas threads tentem escrever no mesmo socket ao mesmo tempo, tentem escrever no mesmo arquivo ao mesmo tempo e assim sucessivamente. Em geral, utiliza-se mecanismos como o “lock” exemplificado acima.

Tipos thread-safe

Outra preocupação que devemos ter ao utilizar concorrência por objetos entre threads está relacionada ao tipo de dados utilizado. No MSDN há para cada tipo de dados observações sobre o tipo de dado ser thread-safe ou não (as vezes notas bastante confusas!).

Em geral, um tipo thread safe é aquele que você não precisa ter medo de acessar ou modificar em diferentes threads (Ex.: ConcurrentQueue). Tipos não thread-safe, você precisa explicitamente utilizar um lock (Ex.: Queue), o que pode gerar gargalos de desempenho, como apresentado anteriormente.

Notas importantes para aplicações Web

Aplicações web são em geral, multi-threaded sem muitas vezes nós percebermos. Geralmente cada novo request é servido numa nova thread, ou seja, se 10 usuários pedem para um servidor servir um request, é possível que tenhamos 10 threads no servidor. Utilizo as palavras geralmente e “é possível” porque o ASP.NET utiliza um mecanismo interno dele para determinar quando ou não utilizar uma nova thread, justamente para evitar contenções e baixo desempenho, conforme apresentado nesses posts. As vezes é melhor fazer um usuário esperar e os 10 que estão sendo atendidos serem bem atendidos, do que deixar 11 com péssima responsividade.

Sendo que aplicações web são essencialmente multi-thread, as mesmas preocupações devemos ter em relação a locks. Se dois requests tentam escrever num arquivo simultaneamente, um dos dois tomará uma exception. Se há alguma estrutura em memória compartilhada entre os requests (exemplos: singletons, instâncias únicas de serviço do Spring.NET, dados estáticos em classes), os mesmos problemas de concorrência estão sujeitos a acontecer.

Conclusão

Como diria um amigo: pensou que ia ser fácil, começou errado!

Processamento paralelo está longe de ser simples. É um conceito um tanto quanto complexo e na prática, debuggar aplicações multi-thread é algo bastante complexo. A própria existência do debugger, de uma linha de log, pode fazer com que as threads concorram em locais diferentes e o bug não se apresente.

Mas o recado mais importante é que não adianta pegar uma aplicação que não foi feita para ter paralelismo, que possui diversos pontos de compartilhamento de informações e sair gerando threads e entupindo de locks onde os problemas são apresentados. Muitas vezes esse processo torna a aplicação ainda menos eficiente do que era quando totalmente single-threaded.

É importante pensar numa arquitetura que suporte concorrência e escala.

Programação paralela – Parte 1 – Quantas threads?

Introdução

Recentemente, comecei a fazer alguns estudos referentes à parte de programação assíncrona do .NET 4.5. Para chegar no conceito de como funciona a parte de I/O assíncrono, achei interessante voltar um pouco e começar pelas raízes da programação paralela, com o objetivo de ilustrar claramente as diferenças e como esses conceitos se combinam. Daí nasceu essa série.

Nesse post abordarei o conceito básico de threads, trocas de contexto e como isso pode resultar em desempenho pior do que aplicações que não utilizam nenhum processamento paralelo.

Afinal, o que é uma thread?

Antes de explicar uma thread, acho melhor explicar primeiro o que é um processo. Um processo nada mais é do que uma instância de um executável, na memória do computador, ou seja, cada aplicação ou serviço executam num processo. Basta ver a lista do seu task manager. Lá você tem uma lista de processos. Se você executa duas vezes a mesma aplicação, tem 2 processos executando, apesar do executável ser o mesmo.

Um processo tem suas próprias áreas de memória, seu stack e seu heap (no caso do .NET, managed heap), ou seja, um processo não invade a área de memória do outro processo. Quem vem de .NET não sabe muito bem o que isso significa na prática, mas quem vem de linguagens não gerenciadas (como C++) sabe bem do que eu estou falando. Se por alguma razão, fizer um deslocamento que dá numa região da memória utilizada por outro processo, seu processo capota (ainda bem).

Então o que é uma thread? Eu costumo explicar uma thread como “uma linha de execução separada” dentro de um mesmo processo. Neste caso, o heap é compartilhado por todas as threads do processo, e cada thread tem sua stack separada. De forma bem simplista, isso significa que se você criar uma instância de uma classe e acessá-la de duas diferentes threads, elas estarão no mesmo espaço de memória o que pode gerar efeitos indesejados em sua aplicação, porém as variáveis locais utilizadas não serão compartilhadas. O post Tipos Escalares e Tipos Complexos ou Tipos por Valor e Referência pode ajudar no entendimento destes conceitos.

O básico da idéia de threads está em:

        public void DoSomething()
        {
            //Algum processamento.
        }

        public void DoSomethingInParallel()
        {
            Thread t = new Thread(DoSomething);
            t.Start();
            DoSomething();
        }

No exemplo acima, ao executar “DoSomethingInParallel”, sua máquina executará duas vezes, simultaneamente, o método “DoSomething”, uma na thread principal (sempre que um novo processo inicia, ele tem uma thread principal) e outra numa thread secundária criada ao executar new Thread, passando como parâmetro um delegate do tipo ThreadStart criado a partir do método DoSomething.

Qual é o limite de threads?

Aqui as coisas começam a ficar complicadas. Não há um limite exato de threads, ou seja, pode-se criar centenas de threads num computador. Talvez a pergunta mais apropriada seja: até onde é eficiente paralelizar um processamento?

Não há uma resposta exata para essa pergunta, mas, existem algumas informações que podem nos ajudar a chegar nesse número mágico.

O limite máximo para execução em paralelo numa máquina está relacionado com o número de cores do processador da máquina, ou seja, numa máquina de 4 cores, 4 threads são executadas em paralelo. As demais, o sistema operacional acaba realizando escalonamento do processamento, ou seja, deixa uma executar um pouquinho, passa para a outra e assim sucessivamente, da mesma forma que ele faz com os processos.

O grande problema é que esse escalonamento é o que chamamos de troca de contexto, ou seja, toda vez que uma thread vai executar, o sistema operacional precisa pegar o stack daquela thread (que pode ter estar fora do cache e até mesmo em disco), recolocar na memória e reexecutar essa thread. Isso obviamente tem um custo.

A resposta para a pergunta acima é: É eficiente deixar o número de threads equivalente ao número de cores processando, sem que haja espera nessas threads. O que chamamos de espera é: espera por carregar itens da memória, operações de I/O, etc. Abordarei esse tema em mais detalhe (espera) em posts futuros.

Um pouco de prática

Para ilustrar o funcionamento das threads, criei um exemplo. A idéia é processar 400 vezes um bubble sort de uma matriz de 1000 itens. A idéia do código é criar worker threads que ficam esperando um determinado dado numa fila em memória, sempre que um dado destes é colocado, ela processa este dado, até que o trabalho todo termine. O código abaixo é o código executado por cada thread.

        private void DequeueAndProcess(ConcurrentQueue<Job> queue)
        {
            while (true)
            {
                Job job = null;
                if (!queue.TryDequeue(out job))
                {
                    Thread.Sleep(0);
                    continue;
                }
                job.JobDelegate();
                job.JobEndedNotifier.Set();
            }
        }        

Cada Job acima é uma estrutura que recebe um JobDelegate (delegate que faz o trabalho quando executado) e um JobEndedNotifier (ManualResetEvent utilizado para avisar o método que cria as threads que o trabalho terminou). Usei uma queue sincronizada justamente para evitar contenção (espera) entre as threads.

Em seguida, um método que cria um número de threads, mede o tempo de execução (Stopwatch) e aguarda o término da execução de todo o trabalho.

        private void CreateJobsAndProcessInParallel(int numberOfThreads)
        {
            ConcurrentBag<int> threadIDs = new ConcurrentBag<int>();
            Stopwatch watch = new Stopwatch();
            watch.Start();
            ConcurrentQueue<Job> queue = new ConcurrentQueue<Job>();
            List<Thread> list = new List<Thread>();
            List<ManualResetEvent> eventList = new List<ManualResetEvent>();
            for (int i = 0; i < numberOfThreads; i++)
            {
                Thread t = new Thread(() => { DequeueAndProcess(queue); });
                list.Add(t);
                t.Start();
            }
            for (int i = 0; i < numberOfJobs; i++)
            {
                ManualResetEvent e = new ManualResetEvent(false);
                eventList.Add(e);
                ThreadStart t = new ThreadStart(() =>
                {
                    BubbleSort.DoBigBubbleSort(bubbleSize, threadIDs);
                });
                queue.Enqueue(new Job(t, e));
            }
            foreach (ManualResetEvent e in eventList)
                e.WaitOne();
            foreach (Thread t in list)
                t.Abort();

            watch.Stop();
            Console.WriteLine("Total elapsed (ms): " + watch.ElapsedMilliseconds);
        }

O método DoBigBubbleSort apenas executa o bubble sort e guarda uma lista de quantas diferentes threads foram usadas no processamento.

Em seguida, executei o exemplo acima com 1, 2, 4, 100, 200, 400 threads, na minha máquina que possui 4 cores (2 cores físicos, 4 processadores lógicos). Os resultados estão abaixo:

ProcessamentoParalelo-pt1-2

ProcessamentoParalelo-pt1-1

Este gráfico nos mostra algumas características muito interessantes:

  • O processamento com duas threads é mais do que a metade do processamento com uma thread só. Na prática isso significa que apesar de paralelizar o processamento, a um custo para gerenciar as threads, além dos demais processos que executam no sistema operacional
  • O processamento com 4 threads é um pouquinho melhor do que o processamento com 2 threads, apesar da máquina ter somente 2 cores físicos. Acredito que esse número seja explicável com a existência de 4 processadores lógicos na máquina (ver hyper threading).
  • O mais interessante aqui é a partir de algo entre ~150 threads o processamento paralelo começa a ficar pior do que o processamento numa thread só. Isso é uma demonstração prática do custo de troca de contexto entre threads

Usando Task Parallel Library

Um outro exemplo, usando a TPL (Task Parallel Library):

        public void TaskBasedTest()
        {
            ConcurrentBag<int> threadIDs = new ConcurrentBag<int>();
            Stopwatch watch = new Stopwatch();
            watch.Start();
            List<Task> l = new List<Task>();
            for (int i = 0; i < numberOfJobs; i++)
                l.Add(Task.Factory.StartNew(() => { BubbleSort.DoBigBubbleSort(bubbleSize, threadIDs); }));
            foreach(Task t in l)
                t.Wait();
            watch.Stop();
            Console.WriteLine("Total elapsed (ms): " + watch.ElapsedMilliseconds);
            Console.WriteLine("Number of threads used: " + threadIDs.Distinct().Count());
        }

O exemplo acima, teve o seguinte tempo de execução:

ProcessamentoParalelo-pt1-3

Como vemos no código, não fazemos qualquer controle do número de threads. Apenas disparamos a execução e contamos quantas diferentes threads foram utilizadas no processamento. No exemplo acima, foram 5.

Como a TPL funciona? Qual é a mágica?

Sempre que executamos um Task.Factory.StartNew, estamos criando uma nova Task na TaskFactory “default”. A TaskFactory default utiliza uma implementação interna de um TaskScheduler (é uma classe abstrata). A implementação default é um ThreadPoolTaskScheduler.

Internamente, o ThreadPoolTaskScheduler delega a execução das tasks para um thread pool que procura manter sempre executando o número de threads correspondente ao número de processadores da máquina. Na prática quando recebe uma task, baseada em quantas threads estão executando, ele checa se deve ou não iniciar uma nova thread ou utilizar uma das que estão ociosas. Espertinho, não?

Na prática, quando usamos PLINQ (Parallel LINQ), Parallel.For, e outros, estamos delegando para este TaskScheduler a lógica de como quebrar o processamento em múltiplas threads, como visto no exemplo acima, um processo um tanto quanto complexo, que a API consegue nos abstrair de uma forma bem eficiente.

Código fonte do exemplo

O código ainda está uma bagunça, mesmo assim, subi para o GitHub: https://github.com/ericlemes/ParallelProgramming.