Edição das 14h47min de 24 de março de 2015

Neste página encontram-se os enunciados de atividades do projeto de ensino BOOOS - Basic Object Oriented Operating System. O projeto é constituído de N atividades, descritas abaixo.

Cronograma de Trabalhos Práticos

Apresentação parcial: 24/04/2015: t0 a t5

Apresentação final: 19/06/2015: todos os trabalhos.

Sobre novo mecanismo de testes

Os testes que passei a vocês são um programa de testes automatizados. Vocês não precisam modificá-los. Ao executar o teste, vocẽs verão uma saída como esta:

arliones.hoeller@sj-labdes-29463:~/my_booos/test$ ./Scheduler_Test 
Welcome to BOOOS - Basic Object Oriented Operating System!
This program will test the class: Scheduler
Starting tests for unit: Scheduler
	Init: OK!
	Creation and Destruction: OK!
	FCFS: OK!
	Priority with Aging: OK!
	Priority without Aging: OK!

Para não realizar o teste automático, basta editar a função main do teste e chamar diretamente a função de teste que deseja executar (exemplo: Priority_Scheduler_Test_Functions::test_scheduling_without_aging()).

t0: Biblioteca de Filas

Uma maneira de descrever um Sistema Operacional, sob o ponto de vista da programação, é definir-lo como um grande gerenciador de filas. São exemplos de filas importantes de um SO as filas de processos prontos a serem executados, processos suspensos, processos dormindo e processos bloqueados em semáforos. Para o trabalho da disciplina implementaremos nossas filas através de uma lista circular duplamente encadeada, cuja estrutura pode ser vista na figura abaixo.

Para recapitular a execução de operações sobre uma lista encadeada, consulte o material de Programação II. Lembre-se, nossa estrutura de dados é uma Fila, ou seja, elementos são inseridos no final e removidos do início.

Neste projeto você deve construir uma pequena biblioteca que ofereça uma classe Queue com métodos de inserção e remoção de elementos genéricos. O código-base da classe, que está nos arquivos Queue.h e Queue.cc. A declaração da classe é apresentada abaixo:

/*
 *
 *  Created on: Aug 14, 2014
 *      Author: arliones
 */
 
#ifndef QUEUE_H_
#define QUEUE_H_
 
namespace BOOOS {
 
        class Queue {
        public:
                Queue();
                virtual ~Queue();
 
                class Element {
                public:
                        Element() { _prev = 0; _next = 0; _rank = 0; }
                        virtual ~Element() {}
 
                        Element * prev() { return _prev; }
                        Element * next() { return _next; }
                        int rank() { return _rank; }
                        void prev(Element * p) { _prev = p; }
                        void next(Element * p) { _next = p; }
                        void rank(int r) { _rank = r; }
 
                private:
                        Element * _prev;
                        Element * _next;
                        int _rank;
                };
 
                Element * head() { return &_head; }
 
                int length() { return _length; }
 
                void insert(Element * elem);
                void insert_ordered(Element * elem);
 
                Element * remove();
                void remove(Element * e);
 
        private:
                Element * search(Element * elem);
 
                Element _head; // _head.next will point to head, _head.prev will point to tail
                int _length;
        };
 
}
 
#endif /* QUEUE_H_ */

Esta fila organiza objetos do tipo Element*. A classe Element deve ser estendida para implementar os detalhes da aplicação, como no exemplo do arquivo Queue_Test.cc.

É responsabilidade do aluno implementar mais testes além dos que estão no exemplo para garantir o funcionamento da fila. Apenas o arquivo Queue.cc deve ser entregue ao professor, devidamente preenchido (os métodos estão vazios no original).

Um projeto pré-configurado para o Elicpse Luna também foi disponibilizado aqui. Para utilizar este projeto:

Baixe o Eclipse Luna para C/C++;
O eclipse não precisa ser instalado, basta descompactar o arquivo baixado;
Execute o eclipse através do executável "eclipse" na basta descompactada;
Baixe o projeto disponibilizado pelo professor;
No eclipse, acesse "Arquivo->Importar..." ou "File->Import...";
Selecione a opção "Geral->Projetos Existentes para a Área de Trabalho" ou "General->Existing Projects into Workspace" e clique "Next" ou "Próximo";
Selecione a opção "Selecionar arquivo compactado" ou "Select archive file", clique em "Buscar..." ou "Browse..." e selecione o arquivo compactado do projeto;
Verifique se o projeto chamado "booos-t0" está selecionado na lista de "Projetos" ou "Projects";
Clique em "Encerrar" ou "Finish", e o projeto deve aparecer no espaço de trabalho.

Observe que a pasta do projeto possui Makefiles. Se preferir, não é necessário utilizar o Eclipse para compilar e testar o projeto, basta usar os seguintes comandos, a partir do diretório do projeto (booos-t0):

$ make all     #Compila sistema e gera aplicação padrão
$ ./booos      #Executa aplicação padrão
$ make TEST=Queue_Test test     #Compila teste implementado em "Queue_Teste.cc"
$ ./test/Queue_Test     #Executa aplicação teste

t1: troca de contexto e tarefas cooperativas

Neste trabalho deve-se estender o projeto sendo desenvolvido no curso com a construção de uma classe para abstrair processos em nível de usuários - na prática, threads. A classe implementada será chamada de Task (tarefa). Lembre-se que uma classe é uma estrutura de dados, logo, nossa classe Task será o PCB (Proccess Control Block) do sistema. A partir deste trabalho, será disponibilizado um gabarito em C++ como no código abaixo, geralmente incompleto, e um diagrama UML de uma versão completa da solução implementada pelo professor, como na imagem abaixo.

/*
 * Task.h
 *
 *  Created on: Aug 15, 2014
 *      Author: arliones
 */

#ifndef TASK_H_
#define TASK_H_

#include <Queue.h>
#include <ucontext.h>

namespace BOOOS {

class Task : public Queue::Element {
public:
	enum State {
		READY,
		WAITING,
		RUNNING,
		FINISHING
	};

	Task(void (*entry_point)(void *), int nargs, void * arg);
	virtual ~Task();

	int tid() { return _tid; }
	State state() { return _state; }

	void pass_to(Task * t, State s = READY);

	void exit(int code);

	static Task * self() { return (Task*)__running; }
	static void init();

private:
	static volatile Task * __running;

	State _state;
	int _tid; // task ID
	// ...
};

} /* namespace BOOOS */

#endif /* TASK_H_ */

Os métodos de interface (i.e., os públicos) que precisam ser implementados na classe estão na declaração acima. Não altere a assinatura destes métodos! Observe que você certamente precisará de novos atributos para o correto funcionamento da classe, e seria bom utilizar alguns métodos privados para auxiliar na implementação. Você pode criar métodos e atributos privados à vontade. Onde será que será declarado o ucontext_t de cada Task?

O teste no arquivo test/Task_Test.cc implementa uma aplicação para testar sua classe Task. Use este exemplo como teste inicial. Abaixo há uma descrição detalhada dos métodos de interface da classe.

Task(void (*entry_point)(void *), int nargs, void * arg): construtor - deve inicializar todos os atributos dos objetos.

virtual ~Task(): destrutor - deve liberar recursos alocados pelo construtor (new/malloc).

int tid(): getter do Task ID (_tid).

State state(): getter do estado do processo (_state).

void pass_to(Task * t, State s = READY): este método salva o contexto do objeto (this) e carrega o contexto da Task recebida por parâmetro. O estado passado em s é o novo estado do objeto que está deixando a CPU. Há algum atributo de classe (static) que precisa ser atualizado aqui?

void exit(int code): finaliza a Task (this) e configura o valor de resultado da task com o valor de code. Por enquanto, se preocupem em fazer a Task retornar a execução para a main. Ignorem o parâmetro code agora - utilizaremos ele mais adiante.

static Task * self(): método de classe (static) que retorna a Task executando no momento.

static void init(): método de classe que precisa ser chamando na inicialização do sistema e deve inicializar os atributos de classe (static). Atenção, o atributo __main, que é static, deve ser inicializado aqui!

Aqui há um projeto do Eclipse Luna pré-configurado com os gabaritos para o t1.

t2: Escalonador FCFS e por prioridades

Você irá construir um despachante de tarefas baseado em duas entidades: uma tarefa dispatcher, responsável pelo controle geral, e uma função choose_next, responsável por determinar qual a próxima tarefa a executar a cada troca de contexto. A figura abaixo ilustra o funcionamento geral do sistema (fonte Prof. Maziero/UTFPR):

Para isto, uma nova classe será adicionada ao nosso sistema: Scheduler. Como nosso escalonador é também um processo, ele herda de Task. Uma função estática chamada dispatcher implementa o comportamento de escalonamento.

Abaixo, o esqueleto C++ da classe Scheduler:

/*
 * Scheduler.h
 *
 *  Created on: Mar 21, 2014
 *      Author: arliones
 */

#ifndef SCHEDULER_H_
#define SCHEDULER_H_

#include <Task.h>
#include <Queue.h>

namespace BOOOS {

class Scheduler : public Task {
	friend class Task;

protected:
	Scheduler();

public:
	enum SchedulerType {
		SCHED_FCFS,
		SCHED_PRIORITY
	};

	virtual ~Scheduler();

	static void init();

	static void dispatcher(void*);

	static Scheduler * self() { return __dispatcher; }

protected:
	virtual Task * choose_next();

	static Scheduler * __dispatcher;
};

} /* namespace BOOOS */

#endif /* SCHEDULER_H_ */

Neste trabalho, os seguintes métodos precisam ser implementados:

Scheduler(): Um construtor que inicializa um Scheduler utilizando o construtor da Task, passando a função dispatcher como entry point. Importante aqui verificar que um Scheduler é um tipo especial de tarefa: ela está sempre pronta (ready), nunca fica bloqueada. Dica: Para permitir esta identificação, crie um estado extra em Task.h, chamado SCHEDULER, e utilize este estado para diferenciar a Scheduler de uma tarefa normal quando utilizando o pass_to;
init(): ele precisa inicializar a tarefa __dispatcher;
dispatcher(void*): esta função implementa o comportamento do escalonador. O pseudo-código abaixo apresenta o comportamento do __dispatcher de modo simplificado:

 void dispatcher()
 {
    while(userTasks > 0)
    {
       next = choose_next() ;  // escolher a próxima Task* a executar
       if(next)
       {
          ... // ações antes de lancar a tarefa "next", se houverem
          self()->pass_to(next); // transfere controle para a tarefa "next"
          ... // ações apos retornar da tarefa "next", se houverem
       }
    }
    exit(0) ; // encerra a tarefa dispatcher
 }

choose_next(): este método virtual é o responsável por implementar a política de escalonamento empregada. Neste trabalho utilizaremos uma política FCFS (First-Come First-Served). Dica: pense na relação entre esta política e a fila que implementamos - esta função deve ser extremamente simples!

Aplicações de testes estão disponíveis aqui. Algumas outras observações:

Como nosso sistema está ficando mais complexo, o lib/BOOOS.h e lib/BOOOS.cc estão sendo utilizados para configurar o sistema. Ele tem uma função init que chamará os inits dos outros componentes. Ele também tem parâmetros de configuração do escalonamento (política, preempção e envelhecimento de prioridades).
O arquivo Scheduler.h disponibilizado está completo, ou seja, você não precisa modificá-lo, a não ser que queira.
Serão necessárias algumas mudanças na classe Task:
- Novo estado: SCHEDULER
- Novo método yield() que transfere a execução da tarefa corrente para o escalonador. Dica: utilize o pass_to.
- A fila de tarefas prontas (_ready) deve ser um atributo de classe (static) de Task. Tasks devem ser incluídas na fila quando criadas e removidas quando destruídas.
- A classe Scheduler é friend da classe Task. Isto significa que Scheduler pode manipular os atributos protegidos de Task.

Algoritmos de escalonamento

A implementação do dispatcher descrito acima já deve gerar uma política de escalonamento implícita. Que política é esta?

Agora, a política de escalonamento inicial deve ser modificada para escalonar tarefas por prioridades. O diagrama abaixo apresenta as modificações necessárias para que o sistema escalone por prioridades.

Queue::Element::_rank: nosso elemento terá um rank genérico pelo qual a fila pode ser mantida em ordem. O valor padrão deste atributo é zero. O atributo é privado e deve ter métodos getter e setter (rank() e rank(int r));
Queue::insert_ordered(Element* elem): nossa fila agora deve ter um método que a mantém ordenada pelo valor do _rank de cada elemento;
Task::nice(int p): nossa Task terá um método chamado nice que configura a prioridade da tarefa ajustando o valor de seu _rank. O escalonador DEVE utilizar prioridades no estilo UNIX, ou seja, com valores entre -20 e 20. Curiosidade: abra um terminal e digite man nice;
SCHEDULER_TYPE: parâmetro de configuração do sistema que define o tipo escalonador utilizado. Dica: utilize este parâmetro para decidir se o sistema de utilizar Queue::insert ou Queue::insert_ordered.

t3: Main, join, exit

Tarefa main

Desde o início temos forjado uma tarefa main na inicialização de Task. Contudo, não demos ainda toda a atenção necessária a esta tarefa. Neste trabalho, caso ainda não tenha sido feito, vocês devem extender o sistema de vocês para atender aos seguintes requisitos:

O ponto de partida deve ser o sistema implementado para o t2;
O programa principal (main) deverá ser tratado como uma tarefa, sendo escalonável da mesma forma que as demais tarefas instanciadas;
Todas as tarefas poderão ser escalonadas a partir de sua criação, inclusive o main;

Seu sistema deverá funcionar corretamente com o código abaixo (atenção ao exit ao final da main):

#include <iostream>
#include <queue>
#include <sstream>
#include <BOOOS.h>
#include <Scheduler.h>

#define ASSERT(x,y) if(!(x)) return y;

using namespace std;
using namespace BOOOS;

Task *pang, *peng, *ping, *pong, *pung;

void function(void * arg) {
	int i;

	Task::self()->nice(2*Task::self()->tid());

	for(i=0; i<10; i++) {
		cout << (char*)arg << " " << i << endl;
		Timer::delay_ticks(25);
	}
	cout << (char*)arg << " End" << endl;
	Task::self()->exit(0);
}

int main() {

	BOOOS_Configuration::SCHEDULER_TYPE = Scheduler::SCHED_PRIORITY;
	BOOOS_Configuration::SCHEDULER_PREEMPT = true;
	BOOOS_Configuration::SCHEDULER_AGING = true;
	BOOOS::init();

	cout << "Main Start" << endl;

	pang = new Task(function, 1, (char*)"\tPang");
	peng = new Task(function, 1, (char*)"\t\tPeng");
	ping = new Task(function, 1, (char*)"\t\t\tPing");
	pong = new Task(function, 1, (char*)"\t\t\t\tPong");
	pung = new Task(function, 1, (char*)"\t\t\t\t\tPung");

	while(Task::count() > 2) {
		Task::self()->nice(20);
		Task::self()->yield();
	}

	cout << "Main End" << endl;

	Task::self()->exit(0);

	return 0;
}

Operador Join

O objetivo deste projeto é construir um método de sincronização denominado join que permite que uma tarefa espere a conclusão de outra tarefa, de forma similar à chamada POSIX wait para processos. Para isso, um método com a seguinte assinatura deve ser adicionado à classe Task:

int join();

Ao chamar task->join(), a tarefa atual (Task::self()) deve ser suspensa até a conclusão da tarefa task. Quando a tarefa task terminar, isto é, chamar o método exit(), a tarefa suspensa deve ser colocada de volta à fila de tarefas prontas. Caso a tarefa task não exista, ou já tenha encerrado, esta chamada deve retornar imediatamente, sem suspender a tarefa atual. Lembre-se que mais de uma tarefa pode aguardar pela mesma tarefa concluir, e que todas devem ser "acordadas" quando isto acontecer.

O valor de retorno do método join é o código de encerramento da tarefa task, ou seja, o valor passado como parâmetro à chamada do método exit(), ou, -1 caso a tarefa indicada não exista.

Seu sistema deve funcionar com o programa exemplo a seguir.

#include <iostream>
#include <queue>
#include <sstream>
#include <BOOOS.h>
#include <Scheduler.h>
 
#define ASSERT(x,y) if(!(x)) return y;
 
using namespace std;
using namespace BOOOS;
 
Task *pang, *peng, *ping, *pong, *pung;
 
void function(void * arg) {
	int i;
 
	Task::self()->nice(2*Task::self()->tid());
 
	for(i=0; i<10; i++) {
		cout << (char*)arg << " " << i << endl;
		Timer::delay_ticks(25);
	}
	cout << (char*)arg << " End" << endl;
	Task::self()->exit(2*Task::self()->tid());
}
 
int main() {
 
	BOOOS_Configuration::SCHEDULER_TYPE = Scheduler::SCHED_PRIORITY;
	BOOOS_Configuration::SCHEDULER_PREEMPT = true;
	BOOOS_Configuration::SCHEDULER_AGING = true;
	BOOOS::init();
 
	cout << "Main Start" << endl;
 
	pang = new Task(function, 1, (char*)"\tPang");
	peng = new Task(function, 1, (char*)"\t\tPeng");
	ping = new Task(function, 1, (char*)"\t\t\tPing");
	pong = new Task(function, 1, (char*)"\t\t\t\tPong");
	pung = new Task(function, 1, (char*)"\t\t\t\t\tPung");
 
	while(Task::count() > 2) {
		Task::self()->nice(20);
		Task::self()->yield();
	}
 
	int result = 0;

	cout << "Main wait pang... ";
	result += pang->join();
	cout << "Result: " << result << endl;

	cout << "Main wait peng... ";
	result += peng->join();
	cout << "Result: " << result << endl;

	cout << "Main wait ping... ";
	result += ping->join();
	cout << "Result: " << result << endl;

	cout << "Main wait pong... ";
	result += pong->join();
	cout << "Result: " << result << endl;

	cout << "Main wait pung... ";
	result += pung->join();
	cout << "Result: " << result << endl;


	cout << "Main End" << endl;
	Task::self()->exit(0);

	return 0;
}

t4: Preempção, compartilhamento de tempo e contabilização de tarefas

Até este ponto nosso sistema apenas escalona tarefas de modo cooperativo, ou seja, para que a CPU passe de uma tarefa para outra é necessário que a tarefa em execução chame explicitamente pass_to ou yield. Neste trabalho, adicionaremos suporte a preempção ao BOOOS.

Preempção

Baseado em texto do Prof. Maziero (UTFPR).

Em sistemas de compartilhamento de tempo (time-sharing) as tarefas recebem "fatias de tempo" de CPU para utilizar. Estas fatias, chamadas de quantum, variam tipicamente entre 1 ms e 100 ms. Ao final de um quantum, a tarefa em execução retorna à fila de prontas e a CPU é passada à próxima tarefa.

Em sistemas reais o controle do quantum pelo sistema operacional é realizada por um dispositivo de hardware chamado temporizador (Timer). O dispositivo é programado para gerar interrupções a cada 1 ms, que são tratadas por um tratador de interrupção (interrupt handler). Essas ativações periódicas do tratador de interrupção são chamadas de ticks do relógio.

Quando uma tarefa recebe o processador, o dispatcher ajusta um contador de ticks que essa tarefa pode usar, ou seja, seu quantum é definido em número de ticks. A cada tick, esse contador deve ser verificado e quando o quantum for atingido o processador deve ser devolvido ao dispatcher para que ele realize um escalonamento.

Como um processo UNIX não tem acesso direto aos temporizadores e interrupções do hardware, vamos simular o temporizador de hardware por um temporizador UNIX, e o mecanismo de interrupção através de sinais UNIX, que serão explicados a seguir.

Sinais UNIX

Baseado em texto do Prof. Maziero (UTFPR).

O mecanismo de sinais do UNIX é similar às interrupções (IRQs) geradas pelo hardware: ao receber um sinal, um processo desvia sua execução para uma função que ele previamente registrou no sistema operacional.

A página de manual signal (seção 7 - man 7 signal) relaciona os principais sinais disponíveis em um sistema UNIX e as ações que cada sinal pode desencadear no processo que o recebe. Através da chamada de sistema sigaction (man sigaction) é possível registrar uma função de tratamento para um determinado sinal (signal handler function).

Um exemplo de uso de sinais está no código abaixo. Nele, uma função é registrada para tratar o sinal SIGINT, que corresponde ao Control-C do teclado. Analise atentamente seu código, execute-o e observe seu comportamento.

#include <stdio.h>
#include <stdlib.h>
#include <signal.h>

/* função que tratará os sinais recebidos */
void tratador (int signum)
{
   printf ("Recebi o sinal %d\n", signum) ;
}

int main (void)
{
   struct sigaction action;

   /* Configura a estrutura que especifica a nova ação */
   action.sa_handler = tratador;
   sigemptyset (&action.sa_mask);
   action.sa_flags = 0;

   /* registra ação para o sinal SIGINT (^C do teclado) */
   if (sigaction (SIGINT, &action, 0) < 0)
   {
      perror ("Erro em sigaction: ") ;
      exit (1) ;
   }

   /* laço vazio */
   while (1) ;
}

Temporizadores UNIX

Para simular as interrupções de relógio do hardware, faremos uso do mecanismo de sinais (para implementar a preempção) e de temporizadores UNIX (para gerar os ticks de relógio). O UNIX permite definir temporizadores através das chamadas de sistemas getitimer e setitimer. Ao disparar, um temporizador gera um sinal para o processo, que pode ser capturado por uma função tratadora previamente registrada por ele. O código abaixo mostra um exemplo:

#include <stdio.h>
#include <stdlib.h>
#include <signal.h>
#include <sys/time.h>

// tratador do sinal
void tratador (int signum)
{
   printf ("Recebi o sinal %d\n", signum) ;
}

int main ()
{
   struct itimerval timer;
   struct sigaction action ;

   // define a ação para o sinal de timer
   action.sa_handler = tratador;
   sigemptyset (&action.sa_mask);
   action.sa_flags = 0;
   if (sigaction (SIGALRM, &action, 0) < 0)
   {
      perror ("Erro em sigaction: ") ;
      exit (1) ;
   }

   // ajusta valores do temporizador
   timer.it_value.tv_usec = 0 ;      // primeiro disparo, em micro-segundos
   timer.it_value.tv_sec  = 3 ;      // primeiro disparo, em segundos
   timer.it_interval.tv_usec = 0 ;   // disparos subsequentes, em micro-segundos
   timer.it_interval.tv_sec  = 1 ;   // disparos subsequentes, em segundos

   // arma o temporizador ITIMER_REAL (vide man setitimer)
   if (setitimer (ITIMER_REAL, &timer, 0) < 0)
   {
      perror ("Erro em setitimer: ") ;
      exit (1) ;
   }

   // laco vazio
   while (1) ;
}

Contabilização de Tarefas

Você irá adicionar mecanismos para contabilizar o uso do processador pelas tarefas em execução. Seu sistema deve produzir uma mensagem de saída com o seguinte formato, para cada tarefa que finaliza (incluindo o próprio dispatcher):

Task 17 exit: response time 4955 ms, CPU time 925 ms, 171 activations

O tempo de resposta é o tempo decorrido desde que a tarefa foi criada (pelo seu construtor), até o momento em que encerra (na chamada a exit()). A Task pode utilizar a função Timer::time() para saber o instante de tempo em que o sistema se encontra em cada tempo. O tempo de CPU é o tempo em que a tarefa permanece utilizando a CPU. O número de ativações é o número de vezes que o escalonador colocou a tarefa para executar.

Implementação do trabalho

O mecanismo a ser implementado no BOOOS deve seguir as seguintes regras:

Criaremos uma classe Timer, que configurará um interval timer de modo semelhante ao exemplo acima, e contabilizará o tempo do sistema através de um tratador de sinal do UNIX. O tempo deverá ser contabilizado em ticks. Este temporizador deverá ser configurado para operar com uma resolução de 1 ms. Dica: defina um parâmetro de configuração TIMER_RESOLUTION em BOOOS.h para tornar a resolução do timer configurável;
Ao ganhar o processador, cada tarefa recebe um quantum de 20 ticks de relógio;
Ao ser acionada, a rotina de tratamento de ticks deve verificar o período de notificação do escalonador e notificá-lo quando for a hora;
Quando um quantum é completado, o controle da tarefa deve retornar ao dispatcher.

Abaixo o diagrama UML atualizado do sistema e uma versão do arquivo Timer.h COMPLETO. Alguns detalhes sobre esta versão do projeto:

Arquivos de configuração do sistema lib/BOOOS.h e lib/BOOOS.c: Há uma classe com várias constantes declaradas. Estas constantes definem a configuração do sistema e podem ser utilizadas em qualquer local do programa (basta incluir lib/BOOOS.h);
Scheduler::notify_time: o Scheduler tem um método notify_time que é chamado pelo Timer sempre que o período de observação é atingido (ou seja, a cada 20 ticks);
BOOOS::init(): o método init() do sistema em lib/BOOOS.cc está correto como já implementado. Ele verifica a configuração em lib/BOOOS.h e inicializa o sistema de acordo;
BOOOS_Configuration::SCHEDULER_TYPE: esta variável seleciona a política de escalonamento. Dica: use ela para decidir como inserir elementos na fila de prontos..
Timer::init(Scheduler * sched, Timestamp period): nosso Timer notifica apenas um observador: o Scheduler. Na inicialização, o Timer precisa tomar conhecimento do objeto Scheduler e do período de notificação;
delay_ticks(Timestamp ticks): método para gerar um atraso baseado em ticks. Para implementá-lo, salve o __ticks atual e aguarde até que o __ticks do sistema chegue ao valor desejado;
delay(Timestamp microseconds): método para gerar um atraso baseado em tempo (em microsegundos). Implemente-o de modo semelhante ao delay_ticks, porém levando em conta a duração de um tick (SCHEDULER_RESOLUTION).

/*
 * Timer.h
 *
 *  Created on: Mar 30, 2014
 *      Author: arliones
 */

#ifndef TIMER_H_
#define TIMER_H_

#include <signal.h>
#include <unistd.h>
#include <sys/time.h>
#include <Queue.h>

namespace BOOOS {

class Scheduler;

class Timer {

protected:
	Timer() {}

public:

	typedef unsigned long long Timestamp;

	virtual ~Timer() {}

	static void init(Scheduler * sched, Timestamp period);
	static void start();

	static Timestamp ticks();
	static Timestamp time();

	static void delay_ticks(Timestamp ticks);
	static void delay(Timestamp microseconds);

private:
	static void sig_handler(int signum);

	static Timestamp __ticks;

	static itimerval __timer;
	static struct sigaction __action;

	static Scheduler * __scheduler;
	static Timestamp __period;
};

} /* namespace BOOOS */

#endif /* TIMER_H_ */

Observações

É importante evitar preempções dentro do dispatcher ou de funções da biblioteca, pois estas podem ter resultados imprevisíveis, como condições de disputa e instabilidade. Pode-se controlar a ocorrência de preempções de várias formas. Uma forma conveniente de implementar esse controle usa o conceito de tarefa de sistema:

Tarefas críticas como o dispatcher são consideradas tarefas de sistema, pois sua execução correta é fundamental para o bom funcionamento do sistema; sua preempção deve ser evitada.
As demais tarefas (Main, Pang, …Pung) são consideradas tarefas de usuário, pois executam código definido pelo usuário da biblioteca, e podem ser preemptadas quando necessário.
O tratador de temporização no escalonador deve sempre verificar se a tarefa corrente é de usuário ou de sistema antes de preemptá-la devido ao fim de um quantum. Você pode usar o tipo SCHEDULER para testar isto.

t5: Semáforo, Produtor-Consumidor e Fila de Mensagens

Construção de Semáforos

O objetivo deste projeto é implementar uma classe semáforo. A interface da classe a ser implementada está apresentada abaixo. Note que cada semáforo tem um inteiro para guardar seu valor, e uma fila para controlar as tarefas que estão aguardando sua liberação.

/*
 * Semaphore.h
 *
 *  Created on: Mar 16, 2014
 *      Author: arliones
 */

#ifndef SEMAPHORE_H_
#define SEMAPHORE_H_

namespace BOOOS
{

class Semaphore
{
public:
    Semaphore(int i = 1);
    virtual ~Semaphore();
 
    void p();
    void v();
 
private:
    volatile int sem;
    Queue _waiting;
};

} /* namespace BOOOS */

#endif /* SEMAPHORE_H_ */

Os métodos da classe devem implementar as seguintes funções:

Semaphore(int i = 1): o construtor deve inicializar o semáforo. Perceba que se o construtor for chamado sem parâmetros, o semáforo será binário, ou seja, pode ser utilizado para implementar acesso ordenado a uma sessão crítica. O valor do semáforo deve ser inicializado com o parâmetro passado.
~Semaphore(): deve finalizar o semáforo, acordando todas as tarefas que aguardavam por ele.
p(): esta chamada deve decrementar o valor do semáforo. Caso o resultado do decremento seja negativo, a tarefa deve bloquear e retornar à execução apenas quando um v() for chamado. No caso de bloquear a tarefa, a execução deve retornar ao dispatcher.
v(): esta chamada de incrementar o valor do semáforo. Esta tarefa nunca é bloqueante e a tarefa que executa nunca perde o processador. Se houver alguma tarefa aguardando no semáforo, a primeira tarefa da fila deve ser acordada e retornar à fila de prontas.

Observações:

Pode (deve!) ser necessário modificar ou criar funções extra na classe Task para resolver este problema.
Os semáforos devem ser implementados totalmente por você, ou seja, você NÃO deve usar outras bibliotecas ou funções do SO para implementar seu semáforo.
Para que um semáforo funcione, as operações de p() e v() devem ser executadas de forma atômica, isto é, as trocas de contexto e interrupções de timer não podem acontecer durante a execução das funções do semáforo. Para isto, modifique sua implementação de timer de modo que a classe semáforo possa impedir, temporariamente, que o timer interrompa a execução de um método de semáforo.

Uso de Semáforos

Para avaliar o uso do semáforo implementado, você implementará, usando seu BOOOS, a aplicação produtor/consumidor. Já implementamos esta aplicação em uma aula anterior, mas utilizando uma versão de semáforo que o Linux nos oferece.

Fila de Mensagens

Uma fila de mensagens é uma estrutura usada por tarefas para comunicação de mensagens de tamanho fixo. O acesso à fila é bloqueante, ou seja, uma tarefa que tenta colocar uma mensagem em uma fila cheia terá de esperar até que surjam vagas; uma tarefa que deseja receber mensagens de uma fila vazia terá de esperar até que uma mensagem seja enviada para a fila. Isto lembra algo do trabalho anterior?

Filas de mensagens são na verdade buffers limitados acessados por tarefas que se comportam como produtoras e consumidoras de mensagens. A fila de mensagens em si é uma região crítica que deve ser protegida de eventuais condições de disputa. Para isso, você deve utilizar os semáforos desenvolvidos no módulo anterior em sua implementação.

Implementaremos um componente para nosso sistema que será chamado de Message_Queue, e tem a seguinte interface:

/*
 * MessageQueue.h
 *
 *  Created on: Mar 17, 2014
 *      Author: arliones
 */

#ifndef MESSAGEQUEUE_H_
#define MESSAGEQUEUE_H_

#include <BOOOS.h>
#include <Queue.h>
#include <string.h>

namespace BOOOS
{

class Message_Queue
{
public:

    class Message: public Queue::Element
    {
    public:
        static const int MSG_SIZE = BOOOS_Configuration::MESSAGE_SIZE;

        Message(char msg[MSG_SIZE]) { memcpy(_msg, msg, MSG_SIZE); }
        virtual ~Message() {}

        char * get() { return _msg; }

    private:
        char _msg[MSG_SIZE];
    };

    Message_Queue(int max_size = 5);
    virtual ~Message_Queue();

    void send(Message & msg);
    Message receive();

    int count() { return _queue.length(); }

private:
    Queue _queue;
    int _max_size;
    // ... mais coisas?
};

} /* namespace BOOOS */

#endif /* MESSAGEQUEUE_H_ */