Edição atual tal como às 14h18min de 18 de julho de 2016

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.

Sobre 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()).

Um projeto pré-configurado para o Elicpse também foi disponibilizado aqui. Para utilizar este projeto, baixe o Eclipse com CDT para C/C++. Se preferir, utilize o ambiente pré-configurado disponibilizado aqui.

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-t1):

$ make all     #Compila sistema e gera aplicação padrão
$ ./booos      #Executa aplicação padrão
$ make TEST=Task_Test test     #Compila programa de teste
$ ./test/Task_Test     #Executa programa de teste

t0: 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:
	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.

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!

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.

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

t1: 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>

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!

A aplicação de teste está disponível 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.

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;
O arquivo BOOOS.h deve incluir na classe BOOOS as seguintes constantes de configuração:
1. 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.
2. SCHED_PREEMPT: parâmetro de configuração do sistema que define se o escalonamento é preemptivo (SCHED_PREEMPT == true) ou não-preemptivo (SCHED_PREEMPT == false). Dica: verifique no material da aula quando um escalonador deve agir para trocar um processo sendo escalonado se for preemptivo ou não-preeptivo. Depois, adapte seu código para satisfazer estas diferenças.
3. SCHED_AGING: parâmetro de configuração do sistema que define se o envelhecimento de prioridades está ligado (SCHED_AGING == true) ou desligado (SCHED_AGING == false). Um problema conhecido do escalonamento por prioridades é a inanição (starvation) de tarefas de baixa prioridade, que ocorre se houverem tarefas de alta prioridade prontas para executar a todo tempo. Para resolver isto, um mecanismo de envelhecimento (aging) de prioridades deve ser implementado. Este mecanismo deve executar sempre que o escalonador for acionado, e deve envelhecer a prioridade daquelas tarefas que continuam em espera. É importante lembrar que depois que uma tarefa executa, ao voltar para a fila de prontos ela deve possuir sua prioridade original (não envelhecida).

Baixe aqui os testes do t1.

t2: 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 busywait_25ms() {
  unsigned int i = 0x7ffff0;
  while(i--) {
    __asm__ volatile ("\tnop\n");
  }
}

void function(void * arg) {
	int i;

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

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

int main() {

	BOOOS::SCHED_POLICY = Scheduler::SCHED_PRIORITY;
	BOOOS::SCHED_PREEMPT = true;
	BOOOS::SCHED_AGING = true;
	BOOOS::BOOOS booos;

	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 busywait_25ms() {
  unsigned int i = 0x7ffff0;
  while(i--) {
    __asm__ volatile ("\tnop\n");
  }
}

void function(void * arg) {
	int i;
 
	Task::self()->nice(2*Task::self()->tid());
 
	for(i=0; i<10; i++) {
		cout << (char*)arg << " " << i << endl;
		busywait_25ms();
	}
	cout << (char*)arg << " End" << endl;
	Task::self()->exit(2*Task::self()->tid());
}
 
int main() {
 
	BOOOS::SCHED_POLICY = Scheduler::SCHED_PRIORITY;
	BOOOS::SCHED_PREEMPT = true;
	BOOOS::SCHED_AGING = true;
	BOOOS::BOOOS booos;
 
	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;
}

Mudanças entre as edições de "BOOOS - Basic Object Oriented Operating System"