Mudanças entre as edições de "BOOOS - Basic Object Oriented Operating System"
Linha 221: | Linha 221: | ||
## ''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. | ## ''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. | ||
## ''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). | ## ''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 [http://docente.ifsc.edu.br/arliones.hoeller/sop/booos-t1-tests.tar.gz testes do t1].''' | ||
{{collapse bottom}} | {{collapse bottom}} |
Edição das 09h07min de 1 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 |
---|
Sobre mecanismo de testesOs 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 |
---|
t0: troca de contexto e tarefas cooperativasNeste 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.
|
t1: Escalonador FCFS e por prioridades |
---|
t1: Escalonador FCFS e por prioridadesVocê 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:
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
}
A aplicação de teste está disponível aqui. Algumas outras observações:
Algoritmos de escalonamentoA 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.
|
t2: Main, join, exit |
---|
t2: Main, join, exitTarefa mainDesde 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:
#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 JoinO 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;
}
|
t3: Preempção, compartilhamento de tempo e contabilização de tarefas |
---|
t3: Preempção, compartilhamento de tempo e contabilização de tarefasAté 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
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
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 UNIXPara 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 TarefasVocê 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):
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 trabalhoO mecanismo a ser implementado no BOOOS deve seguir as seguintes regras:
Abaixo o diagrama UML atualizado do sistema e uma versão do arquivo Timer.h COMPLETO. Alguns detalhes sobre esta versão do projeto:
/*
* 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:
|
t4: Semáforo, Produtor-Consumidor e Fila de Mensagens |
---|
t4: Semáforo, Produtor-Consumidor e Fila de MensagensConstrução de SemáforosO 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:
Observações:
Uso de SemáforosPara 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 MensagensUma 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::BOOOS::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_ */
Os métodos da classe devem implementar as seguintes funções:
Sua Message_Queue pode ser testada com o programa abaixo. Repare que a aplicação não controla mais a concorrência. Ela delega esta responsabilidade à Message_Queue. /*
* Semaphore_Test.cc
*
* Created on: Jun 01, 2014
* Author: arliones
*/
#include <BOOOS.h>
#include <Task.h>
#include <MessageQueue.h>
#include <iostream>
using namespace std;
using namespace BOOOS;
Message_Queue queue;
static const int repetitions = 10;
void producer(void *)
{
cout << "Producer was born!" << endl;
Task * myself = Task::self();
char msg[26] = "This is message number 0.";
for(int i = 0; i < repetitions; i++) {
msg[23] = 0x30 + i;
Message_Queue::Message qmsg(msg);
queue.send(qmsg);
Timer::delay(25000);
}
myself->exit(repetitions);
}
void consumer(void *)
{
cout << "Consumer was born!" << endl;
Task * myself = Task::self();
for(int i = 0; i < repetitions; i++) {
cout << queue.receive().get() << endl;
}
myself->exit(repetitions);
}
int main()
{
cout << "Welcome to BOOOS - Basic Object Oriented Operating System!" << endl;
cout << "This program will test the class: Semaphore" << endl;
BOOOS::BOOOS::SCHED_POLICY = BOOOS::BOOOS::SCHED_ROUNDROBIN;
BOOOS::BOOOS::SCHED_PREEMPT = true;
BOOOS::BOOOS::SCHED_AGING = true;
BOOOS::BOOOS booos(false);
Task * myself = Task::self();
Task prod(&producer,0,0);
Task cons(&consumer,0,0);
prod.join();
cons.join();
myself->exit(0);
return 0;
}
|