Mudanças entre as edições de "BOOOS - Basic Object Oriented Operating System"
Linha 100: | Linha 100: | ||
</syntaxhighlight> | </syntaxhighlight> | ||
--> | --> | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
= t1: troca de contexto e tarefas cooperativas = | = t1: troca de contexto e tarefas cooperativas = | ||
Linha 188: | Linha 180: | ||
[https://www.dropbox.com/s/x7sxnpsh2k53lqp/booos-t1.tar.gz Aqui] há um projeto do Eclipse Luna pré-configurado com os gabaritos para o t1. | [https://www.dropbox.com/s/x7sxnpsh2k53lqp/booos-t1.tar.gz Aqui] há um projeto do Eclipse Luna pré-configurado com os gabaritos para o t1. | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
Linha 301: | Linha 286: | ||
# ''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'''; | # ''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''. | # ''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''. | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
Edição das 14h24min de 12 de novembro de 2014
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.
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 [1] e [2]. A declaração da classe é apresentada abaixo:
/*
* BOOOS.h
*
* 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).
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). Baixe estes arquivos aqui.
- 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;
}