Os primeiros exercícios são relacionados ao comportamento de Threads, também conhecidas como processos leves. O epos será o sistema operacional utilizado nesta disciplina onde os trabalhos requisitados são propostas de soluções para problema inseridos no S.O. A seguir é mostrado os diagramas de classe e de estado da thread inicial.

Neste problema é perguntado o que aconteceria se o desenvolvedor "deletar" uma thread e depois dar um join() na mesma. E, claro, propor uma solução para o mesmo.

O snipet a seguir ilustra o nosso teste. Com este teste, embora tenhamos executado uma ação destrutiva, todos as outras threads executaram normalmente com exceção da thread que deu o join(). Infelizmente, neste caso, quem fez esta operação foi a thread main. Esta, ficou eternamente esperando a finalização do filósofo 0, que deu o calote, pendurando, assim, a aplicação.

...
delete phil[0];
for(int i = 0; i < 5; i++) {
   int ret = phil[i]->join();
   ...	

Em uma abordagem mais formal, a main inicia a aplicação, cria todas as threads, deleta o phil[z] e pede um join(). O processador executa o método join, sendo que a main ainda detém o processador. Dentro do join é verificado o status da thread, no caso phil[0] que é um lixo pois o objeto foi destruido. Portanto como não é FINISHING, o processador "trigga" o yield() fazendo a main liberar o processador. Neste momento, a main perde o processador e as outras threads vão executar, depois que todas executam, começa o retorno dos joins que, quando chega na vez do processo "deletado" a aplicação pendura.

Este problema é decorrente do fato do método join ser busy waiting, assim uma solução seria fazer o metodo join ser idle waiting, o que solucionaria o problema. O problema do busy waiting é o nosso segundo exercício, o que deixa o nosso primeiro apenas na proposta sem poder demonstrá-lo antes do segundo. Para não deixar sem uma resposta avaliável, a solução será alcançada ao modificar o destrutor da Thread.

A espera ocupada é caracterizada quando uma thread que está esperando uma condição continua a concorrer pelo processador, onde, volta e meia, a thread que está esperando pergunta se a condição foi atingida. Este fato, embora se tratando de threads, implica em diminuição de performance. Uma solução para a busy waiting é o chamado idle waiting, onde a thread que está esperando - ela dorme - aguarda por uma sinalização quando a condição for satisfeita.

Quando falamos de idle waiting, a partir do momento em que a thread está em estado de espera, ela só volta a concorrer pelo processador apenas quando ela é sinalizada. Assim, a nossa proposta de solução é a criação de uma fila de espera, fila esta como um atributo de objeto. E o métodos de espera e sinalização. Para isto, a thread precisa de mais um estado: WAITING. O snipets abaixo mostram as modificação feitas no código.

A solução proposta é adicionar um novo estado: "WAITING" juntamente com uma fila para esta condição: "_waiting". Isto permite a modificação do método join():

...
if(_state != FINISHING)<--- pergunta apena uma vez, e só acorda quando sinalizado
   Thread::wait(&_waiting); <--- método e classe que pede um ponteiro como parâmetro.
 Neste caso, passamos a referência de um atributo de objeto, a nossa fila _waiting
...

Assim, a thread que está esperando passa a não mais requerir o processador, o que exige uma notificação para sair deste estado. Esta notificação é feita por uma thread quando esta termina ou quando ela é deletada( solução do primeiro problema ). Para isto é necessário modificar ~Thread() e exit(int status).

void Thread::exit(int status)
{
   ...

   if(Traits::active_scheduler)
      CPU::int_disable();

   Thread::notifyAll(&(_running->_waiting)); <--- método de classe que recebe como parâmetro 
a referência da fila _waiting da thread que está em estado running.

   if(_ready.empty() && !_suspended.empty())
      idle(); // implicitly re-enables interrupts
   
   ...
}

~Thread() {
   Thread::notifyAll(&_waiting)); <---
   _ready.remove(this);
   _suspended.remove(this);
   free(_stack);
}

A questão é que, quando uma thread acaba o processamento, ela sinaliza todas as threads que estavam esperando por ela. Esta abordagem também é considerada no problema do delete.

A seguir é mostrado a implementação dos métodos wait() e notify() e notifyAll.

void Thread::wait(Queue * _waitingQueue) {
   db(TRC) << "Thrad::wait()\n";

   if(Traits::active_scheduler)
      CPU::int_disable();

   if(!_ready.empty()) {
       Thread * old = _running;
       old->_state = WAITING;
       //--
       _waitingQueue->insert(&old->_link);
       
       _running = _ready.remove()->object();
       _running->_state = RUNNING;

       db(INF) << "old={" << old << ","
                       << *old->_context << "}\n";
       db(INF) << "new={" << _running << ","
                       << *_running->_context << "}\n";

       CPU::switch_context(&old->_context, _running->_context);
   }
   
   if(Traits::active_scheduler)
       CPU::int_enable();
}

void Thread::notify(Queue * _waitingQueue){
   db(TRC) << "Thread::notify()\n";

   if(Traits::active_scheduler)
      CPU::int_disable();

   if(!_waitingQueue->empty()){
      Thread * notified = _waitingQueue->remove()->object();
      notified->_state = READY;
      _ready.insert(¬ified->_link);
   }

   if(Traits::active_scheduler)
      CPU::int_enable();
}

void Thread::notifyAll(Queue * _waitingQueue){
   db(TRC) << "Thread::notify()\n";

   if(Traits::active_scheduler)
      CPU::int_disable();

   while(!_waitingQueue->empty()){
      Thread * notified = _waitingQueue->remove()->object();
      notified->_state = READY;
      _ready.insert(¬ified->_link);
   }

   if(Traits::active_scheduler)
      CPU::int_enable();
}

Para a ralização do experimento foi realizado o seguinte teste:
Mantendo o join como busy waiting, e adicionando um log de debug no laço de espera,

OStream cout; <---
while(_state != FINISHING){
   yield(); <--- busy waiting
   cout << "busy\n"; <---
}

The Philosopher's Dinner:
Philosophers are alife and hungry!
The dinner is served!
/\|/\waitiing phil[0]
phil[0] -> thinking
phil[1] -> thinking
phil[2] -> thinking
phil[3] -> thinking
phil[4] -> thinking
busy <---
phil[0] ->  eating 
phil[1] ->  eating 
phil[2] ->  eating 
phil[3] ->  eating 
phil[4] ->  eating 
busy <---
phil[0] -> thinking
phil[1] -> thinking
phil[2] -> thinking
phil[3] -> thinking
phil[4] -> thinking
busy <---
phil[0] ->  eating 
phil[1] ->  eating 
phil[2] ->  eating 
phil[3] ->  eating 
phil[4] ->  eating 
busy <---
...

OStream cout; <---
while(_state != FINISHING){
   wait(); <--- idle waiting
   cout << "busy\n"; <---
}

The Philosopher's Dinner:
Philosophers are alife and hungry!
The dinner is served!
/\|/\waitiing phil[0]
phil[0] -> thinking
phil[1] -> thinking
phil[2] -> thinking
phil[3] -> thinking
phil[4] -> thinking
phil[0] ->  eating 
phil[1] ->  eating 
phil[2] ->  eating 
phil[3] ->  eating 
phil[4] ->  eating 
phil[0] -> thinking
phil[1] -> thinking
phil[2] -> thinking
phil[3] -> thinking
phil[4] -> thinking
phil[0] ->  eating 
phil[1] ->  eating 
phil[2] ->  eating 
phil[3] ->  eating 
phil[4] ->  eating 
...
phil[3] ->  eating 
phil[4] ->  eating 
busy <---
Philosopher 0 ate 10 times 
waitiing phil[1]
Philosopher 1 ate 10 times 
waitiing phil[2]
Philosopher 2 ate 10 times 
waitiing phil[3]
Philosopher 3 ate 10 times 
waitiing phil[4]
Philosopher 4 ate 10 times 
The end!

Este resultado, além de demonstrar que o idle waiting está funcionando, nos permite deduzir que não precisamos do laço para testes. Apenas um condiional é necessário.

<--- modificar!!! Neste problema, primeiro é proposto para retirarmos a função que decrementa do loop.

em semaphore.h:

antes:
void p() { // proberen 
   while(dec(_value) < 0)
      sleep();
}

depois:
void p() { 
   int value = dec(_value); <---
   while(value < 0)
      sleep();
}

No teste realizado não foi possível notar nenhuma diferença no resultado.

O segundo exercíco é modificar o código para que a espera seja do tipo idle waiting e implementar a sinalização wakeup. A primeira solução considerada foi chamar os métodos da thread que trata de esperas: wait() e notify(). O problema é que nem wait() nem notify() são métodos de classe, não podendo ser chamados deste jeito. Uma possibilidade seria tornar estes métodos em estático, o que seria complicado, já que existe código dependente destes métodos sendo não-estáticos.
Outra solução, a qual adotamos, foi criar métodos de classe para solucionar este problema, acompanhado por uma fila como atributo de classe.

void v() { // verhoegen
   if(inc(_value) < 1)
      wakeup();
}

em synchronizer.h:
...
protected:
   // Atomic operations
   bool tsl(volatile bool & lock) { return CPU::tsl(lock); }
   int inc(volatile int & number) { return CPU::finc(number); }
   int dec(volatile int & number) { return CPU::fdec(number); }

   // Thread operations
   void sleep() {
      if(!busy_waiting) 
         Thread::sleep(); <---
   }
   
   void wakeup() {
      if(!busy_waiting) 
         Thread::wakeup(); <---
   }
   
   void wakeup_all() {
      if(!busy_waiting) 
       Thread::wakeup_all(); <---
   }
...

thread.h:
...
enum  {
 RUNNING,
 READY,
 WAITING,
 SUSPENDED,
 BLOCKED,
 FINISHING
};
...
static void sleep();
static void wakeup();
static void wakeup_all();
...
static Queue _blocked;
...

thread.cc:
...
void Thread::sleep() {

   if(Traits::active_scheduler)
      CPU::int_disable();

   if(!_ready.empty()) {
       Thread * old = _running;
       old->_state = BLOCKED;
       
       _blocked.insert(&old->_link);
       
       _running = _ready.remove()->object();
       _running->_state = RUNNING;

       CPU::switch_context(&old->_context, _running->_context);
   }
   
   if(Traits::active_scheduler)
       CPU::int_enable();
}

void Thread::wakeup(){
   if(Traits::active_scheduler)
      CPU::int_disable();

   if(!_blocked.empty()){
      Thread * signaled = _blocked.remove()->object();
      signaled->_state = READY;
      _ready.insert(&signaled->_link);
   }

   if(Traits::active_scheduler)
      CPU::int_enable();
}

void Thread::wakeup_all(){
   if(Traits::active_scheduler)
      CPU::int_disable();

   while(!_blocked.empty()){
      Thread * signaled = _blocked.remove()->object();
      signaled->_state = READY;
      _ready.insert(&signaled->_link);
   }

   if(Traits::active_scheduler)
      CPU::int_enable();
}
...    

Este problema trata do alarm. Ou temporizador relativo. Neste problema é solicitado a modificação, que antes era busy waiting, para idle waiting. E utilizar como tratador do alarm o semáforo. A nossa modificação consiste em declarar um semáforo, iniciado em "0". Utilizar a função proberen do semáforo para que este fique em uma fila de espera até que o tratador o sinalize com a função verhoegen, o que caracteriza o idle waiting. O semáforo é inicialzado em "0" para que, na primeira passagem, a thread é barrada.

em alarm.h:

class Alarm
{
private:
   ...
   Semaphore * semaphore(0); <---
   ...
   

em alarm.cc:

antes:
void Alarm::delay(const Microseconds & time)
{
   Tick t = _elapsed + time / period();
   while(_elapsed < t);
}

depois:

void Alarm::delay(const Microseconds & time)
{
   Tick t = _elapsed + time / period();
   if(_elapsed < t) <---
  	   semaphore.p(); <---  Na primeira passagem, a thread é suspensa.
}

void Alarm::timer_handler(void)
{
   static Tick next;
   static Handler handler;

   _elapsed++;
    
   ...

   if(next)
      next--;
   if(!next) {
      if(handler)
         handler();
      if(_requests.empty())
         handler = 0;
      else {
         Alarm * alarm = _requests.remove()->object();
         next = alarm->_ticks;
         handler = alarm->_handler;
         if(alarm->_times != -1)
            alarm->_times--;
         if(alarm->_times) 
            _requests.insert(&alarm->_link, alarm->_ticks);
      }
      semaphore.v(); <---  sinaliza a thread que estava esperando.
   }
}