logo
Contato | Sobre...        
rebarba rebarba

Rodrigo Strauss :: Blog

follow us in feedly

Win32: sincronização

Em um post do passado eu falei sobre o maravilhoso mundo das threads e de todos problemas que as threads resolvem. Agora é a hora de começarmos a ver os inúmeros problemas que as threads criam. Pensou que ia ser fácil? Pois é, já começou errado...

Como um trecho de código vale mais que e = m * pow(c, 2);, vamos começar com um exemplo clássico de problema que acontece quando temos várias threads compartilhando um recurso:

 
 
#include "stdafx.h"
 
/*
conteúdo do stdafx:
 
#ifndef _WIN32_WINNT		
#define _WIN32_WINNT 0x0501
#endif						
 
#include <Windows.h>
 
#include <stdio.h>
#include <tchar.h>
 
#include <iostream>
#include <vector>
 
#include <assert.h>
#define ASSERT assert
*/
 
using std::cout;
using std::endl;
using std::vector;
 
//
// classe simples (e incompleta) que implementa uma lista
// duplamente ligada. Se você disse "hã?", leia o artigo
// sobre "Linked list" da wikipedia.
//
template<typename T>
class LinkedList
{
  struct NODE
  {
    NODE* previous;
    NODE* next;
    T data;
  };
 
  NODE rootNode_;
  unsigned int count_;
 
public:
 
  LinkedList()
  {
    count_ = 0;
    rootNode_.previous = rootNode_.next = NULL;
  }
 
  void AddAfter(NODE* node, T data)
  {
    NODE* newNode = new NODE();
 
    //
    // primeiro item?
    //
    if(node->next == NULL)
    {
      ASSERT(node->previous == NULL && node == &rootNode_);
      node->next = node->previous = node;
      node->data = data;
      return;
    }
    else
    {
      //
      // refaz todos os links, para que o nó inserido
      // fique entre o nó passado como parâmetro
      // e o próximo
      //
      newNode->next = node->next;
      node->next = newNode;
      newNode->previous = node;
      newNode->next->previous = newNode;
 
      newNode->data = data;
    }
 
    count_++;
  }
 
  void Dump()
  {
    cout << "== DUMP START ==" << endl;
 
    if(rootNode_.next == NULL)
    {
      ASSERT(rootNode_.previous == NULL);
      cout << "== DUMP END ==" << endl;
      return;
    }
 
    cout << rootNode_.data << endl;

 
    for(NODE* node = rootNode_.next ; node != &rootNode_ ; node = node->next)
      cout << node->data << endl;
 
    cout << "== DUMP END ==" << endl;
  }

 
  void Add(T data)
  {
    AddAfter(&rootNode_, data);
  }
 
  unsigned int Count()
  {
    if(rootNode_.next == NULL)
    {
      ASSERT(rootNode_.previous == NULL);
      return 0;
    }

 
    unsigned int count = 1;
 
    for(NODE* node = rootNode_.next ; node != &rootNode_ ; node = node->next)
      count++;
 
    return count;
  }

 
};
 
//
// estrutura para informar a nossa worker thread o que ela
// deve fazer
//
struct WORKER_THREAD_INFO 
{
  LinkedList<int>* list;
  unsigned int addCount;
};

 
//
// nossa "linha trabalhadora" (aposto que algum livro traduzido
// deve usar esse termo, aposto). Ela adicionará itens na 
// nossa lista ligada
//
DWORD WINAPI WorkerThread(void* lpv)
{
  WORKER_THREAD_INFO* info = (WORKER_THREAD_INFO*)lpv;
 
  for(DWORD a = 0 ; a < info->addCount; a++)
  {
    info->list->Add(a);
 
    //
    // dormir é uma boa forma de gastar um tempo
    // e simular trabalho. Pena que a Win32 API
    // não tem um função SleepInTheBathroom();
    //
    Sleep(10);
  }
 
  return 0;
}
 
int main()
{
  LinkedList<int> list;

 
  static const DWORD threadCount = 100;
  DWORD dwThreadID;
  vector<HANDLE> threads;
 
  //
  // todas as threads vão adicionar a mesma quantidade,
  // para fins de teste e demonstração está mais que bom.
  //
  WORKER_THREAD_INFO info;
  info.list = &list;
  info.addCount = 100;
 
  //
  // criando todas as threads
  //
  for(DWORD a = 0 ; a < threadCount ; a++)
    threads.push_back(CreateThread(NULL, NULL, &WorkerThread, &info, NULL, &dwThreadID));
 
  //
  // esperando TODAS as threads retornarem
  //             |___________________________________
  //                                                 |
  //                                                 v
  //
  WaitForMultipleObjects(threadCount, &threads[0], TRUE, INFINITE);
 

  list.Dump();
 
  //
  // isso deve mostrar 10.000.
  //
  cout << "count: " << list.Count();
 

  //
  // vou deixar os handles abertos, como o programa vai 
  // morrer agora o Windows se vira com isso...
  //
 
  return 0;
}

Bom, 100 threads criando 100 registros na nossa lista ligada devem criar 10.000 registros, certo? Faça alguns testes: rode primeiro em Debug. Depois rode em Release. Depois brinque com o número do Sleep. Depois repita os testes em diferentes máquinas, com diferentes clocks e quantidades de cores. Olhe algumas saídas que eu obtive durante os testes, usando um Core 2 Duo (2 cores):

== Versão Debug ==
count: 92
count: 99
count: 98
count: 99
== Versão Release ==
count: 40
count: 99
count: 97

Ué, não deveria ser 10.000? Mudando o tempo do Sleep e a quantidades de threads eu consegui outros números, completamente diferentes. Isso é o chamado race condition, um problema ou bug que depende de timming e coisas fora do seu controle, um problema típico de programação multithread. Como a manifestação do bug depende de diversos fatores fora do seu controle - velocidade do processador, carga de processamento da máquina, etc - esse tipo de problema é sempre muito difícil de reproduzir e debugar.

O principal problema desse código está no trecho de código que adiciona um item na lista:

      newNode->next = node->next;
      node->next = newNode;
      newNode->previous = node;
      newNode->next->previous = newNode;
      newNode->data = data;

Esse trecho de código deve ser executado de forma atômica para que a lista ligada continue válida, com todos os ponteiros apontando para seus próximos e anteriores de forma correta. Depois da execução da segunda linha, o estado da lista permanece inválido até que a última linha desse trecho seja executada. Como uma thread pode ser interropida a qualquer hora (inclusive entre essas linhas), a manipulação dos ponteiros é feitas de forma incorreta e desordenada. É grande a probabilidade (isso depende do scheduler) de que a última thread que estava "mexendo" na lista a tenha deixado em um estado inválido. Isso pode gerar um erro de lógica (nosso caso) ou um GPF difícil de achar, que cada hora acontece em um lugar do código.

No próximo post começaremos a ver os recursos da API do Windows para resolver esse problema e permitir que várias threads manipulem um mesmo recurso ao mesmo tempo.


Em 13/07/2008 06:49, por Rodrigo Strauss


  
 
 
Comentários
Wander | website | em 19/09/2008 | #
No caso em que

if(node->next == NULL)

For verdadeiro, temos um memory leak?
Algo a dizer?
Nome:


Site:


E-mail:


Escreva o número vinte e seis:


 Não mostre meu e-mail no site, não serve pra nada mesmo...

Comentário





Os comentários devem ser sobre assuntos relativos ao post, eu provavelmente apagarei comentários totalmente offtopic. Se quiser me enviar uma mensagem, use o formulário de contato. E não esqueça: isso é um site pessoal e eu me reservo o direito de apagar qualquer comentário ofensivo ou inapropriado.
rebarba rebarba
  ::::