Idle-waiting thread synchronization

Arquivo

• thread_sync.tar.gz

Solução

O exercício proposto foi eliminar o busy-waiting do semáforo.

Operações sleep, wakeup e wakeup_all

Todas as vezes em que uma thread fica presa em um semáforo, o semáforo deve saber quem é a thread que está presa nele para poder liberá-la quando a outra thread que tiver obtido a tranca sair da região crítica (destrancar o semáforo). Para isso foi criada uma lista _waiting que armazena a informação de todas as threads que estão presas em cada semáforo.

As operações sleep, wakeup e wakeup all foram implementadas da seguinte maneira:

sleep

Insere a thread no final da lista _waiting e a suspende.

wakeup

Remove a primeira thread da lista _waiting e retoma a execução da thread removida.

wakeup_all

Repete a mesma operação do wakeup para todas as threads da lista _waiting.

List<Thread> _waiting;

...

// Thread operations
void sleep() {
  db<Semaphore>(TRC) << "Sleep...\n";
  if(!busy_waiting) {
    List<Thread>::Element * e = new List<Thread>::Element(Thread::running());
    _waiting.insert(e);
    Thread::running()->suspend();
  }
}
void wakeup() {
  db<Semaphore>(TRC) << "Wakeup...\n";
  if(!busy_waiting) {
    if (List<Thread>::Element * tmp = _waiting.remove()) {
      tmp->object()->resume();
    }
  }
}
void wakeup_all() {
  db<Semaphore>(TRC) << "Wakeup all...\n";
  if(!busy_waiting) {
    while (List<Thread>::Element * tmp = _waiting.remove()) {
      tmp->object()->resume();
    }
  }
}

Semáforo

Havia um bug na implementação do semáforo que nos foi dada. Anteriormente, a saída do programa semaphore_test.cc era algo próximo de:

thinkingthinkingthinkingthinkingthinking eating  eating  eating  eating  eating thinkingthinkingthinkingthinkingthinking eating  eating  eating  eating  eating thinkingthinkingthinkingthinkingthinking eating  eating  eating  eating  eating thinkingthinkingthinkingthinkingthinking eating  eating  eating  eating  eating thinkingthinkingthinkingthinkingthinking eating  eating  eating  eating  eating thinkingthinkingthinkingthinkingthinking eating  eating  eating  eating  eating ...

Uma vez que cada hashi era compartilhado entre dois filósofos, e cada filósofo necessitava de dois hashis para poder comer, é impossível que os 5 filósofos estejam comendo ao mesmo tempo (como mostra a saída acima).

Percebemos que o que estava causando esse comportamento errôneo eram os métodos p() e v() do semáforo. A implementação correta é mostrada abaixo.

void p() { 
  db<Semaphore>(TRC) << "Semaphore::p(value=" << _value << ")\n";
  if (dec(_value) < 1) // Antes era while(dec(_value) < 0)
    sleep();
}
void v() {
  db<Semaphore>(TRC) << "Semaphore::v(value=" << _value << ")\n";
  if (inc(_value) < 0) // Antes era if(inc(_value) < 1)
    wakeup();
}