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"; <--- }obtemos o seguinte resultado:
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 <--- ...Ao imlementar a nossa proposta, adicionando, também, o log de debug:
OStream cout; <--- while(_state != FINISHING){ wait(); <--- idle waiting cout << "busy\n"; <--- }obtemos a seguinte resposta:
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.
Atualizando os diagramas:<--- 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(); <--- } ...Assim, foi acrescentado ao código os métodos estáticos: sleep, wakeup, wakeup_all; o estado BLOCKED; e a fila estática _blocked; A seguir é mostrado o código referente às mudanças.
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(); } ...Nenhuma das modificações acima pode produzir algum efeito sobre a percepção do resultado da aplicação. Mesmo mudando wakeup por wakeup_all.
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.
}
}