SOP29005-2014-1
EngTel: Sistemas Operacionais - Diário de Aulas 2014-1
Professor: Arliones Hoeller
Turma: 29005
Encontros: terças e sextas às 9:40.
Atendimento paralelo: segundas às 13:30 e quintas às 8:25.
Endereço web do grupo: https://www.facebook.com/groups/sop29005.ifsc.sj/
Endereço de e-mail da disciplina: sop29005.ifsc.sj@groups.facebook.com
Outros cursos de sistemas operacionais nos quais este curso se baseia:
- Sistemas Operacionais - Ciências da Computação UFSC
- Sistemas Operacionais - Engenharia da Computação UTFPR
- Operating Systems Engineering - Computer Science MIT
Plano de ensino
Cronograma de Trabalhos Práticos
Trabalho | Descrição | Lançamento | Entrega |
---|---|---|---|
t0 | Biblioteca de filas | 21/02/2014 | 14/03/2014 |
t1 | Troca de contexto | 28/02/2014 | 21/03/2014 |
t2 | Biblioteca de tarefas | 28/02/2014 | 21/03/2014 |
t3 | Despachante de tarefas | 24/03/2014 | 11/04/2014 |
t4 | Escalonamento por prioridade | 28/03/2014 | 11/04/2014 |
t5 | Preempção e compartilhamento de tempo | 31/03/2014 | 14/04/2014 |
t6 | Contabilização de tarefas | 31/03/2014 | 14/04/2014 |
t0 - t6 | Apresentação dos trabalhos | - | 14/04/2014 |
t7 | Tarefa main | 05/05/2014 | 23/05/2014 |
t8 | Operador join | 05/05/2014 | 23/05/2014 |
t9 | Chamada sleep | 05/05/2014 | 23/05/2014 |
tA | Semáforo | 19/05/2014 | 30/05/2014 |
tB | Uso de semáforos | 19/05/2014 | 30/06/2014 |
tC | Fila de mensagens | 26/05/2014 | 06/06/2014 |
t7 - tC | Apresentação dos trabalhos | - | 10/06/2014 |
tD | Gerente de disco (trabalho de recuperação) | 13/06/2014 | 04/07/2014 |
Relação de Entrega dos Trabalhos Práticos
Grupo | t0 | t1 | t2 | t3 | t4 | t5 | t6 | t7 | t8 | t9 | tA | tB | T0 | T1 | tC - REC |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Danilo, Jean | OK | OK | OK | OK | OK | Zz | Zz | C | |||||||
Elton, Flavia | OK | OK | OK | OK | OK | OK | OK | A | |||||||
Ernani, T. Werner | OK | OK | OK | OK | OK | OK | OK | A | |||||||
Gustavo, T. Bonotto | OK | OK | Zz | Zz | Zz | Zz | Zz | D | |||||||
Leonan, Marcus | OK | OK | OK | OK | OK | OK | OK | A | |||||||
Leticia, Tamara | OK | OK | OK | OK | OK | OK | OK | A |
OK - Trabalho entregue.
Zz - Dormiu no ponto e não entregou.
Diário de Aulas
11/02: Apresentação da disciplina. Histórico, visão geral e estruturas de um SO
- Revolution OS: documentário sobre Linux
- Apresentação sobre histórico visão geral e estruturas básicas de um SO. [slides]
14/02: Finalização do conteúdo anterior e atividades em laboratório: Introdução ao Linux e GCC/G++
- Referência sobre C++: http://www.cplusplus.com/
- Livros sobre C++:
- Tutorial C++
- Exercício-exemplo feito em aula. [código-fonte]
18/02: Mais sobre desenvolvimento em C++ com Linux – Herança, métodos e atributos estáticos, bibliotecas
Herança
Classes em C++ podem ser estendidas, criando novas classes que retêm as característica da classe-base. Este processo, conhecido como herança, envolve uma classe-base e uma classe derivada: a classe derivada herda os membros da classe-base, sobre os quais ela pode adicionar seus próprios membros.
Por exemplo, imaginemos uma série de classes para descrever dois tipos de polígonos: retângulos e triângulos. Estes dois polígonos têm certas propriedades em comum, como os valores necessários para calcular suas áreas: ambos podem ser descritos simplificadamente com uma altura e uma largura. (ou base).
Isto pode ser representado no formato de classes como uma classe Polygon (polígono) da qual podemos derivar duas outras classes: Rectangle e Triangle:
A classe Polygon poderia conter membros comuns a ambos os tipos de polígonos. Em nosso caso: largura e altura (width e height). E as classes Rectangle e Triangle poderiam ser as classes derivadas, com características específicas que diferenciam um tipo de polígono de outro.
Classes que são derivadas de outras herdam todos os membros acessíveis da classe-base. Isto significa que se a classe-base inclui um membro A e nós derivamos uma classe dela, e esta nova classe possui um membro B, a classe derivada conterá ambos os membros A e B.
No C++, a relação de herança de duas classes é declarada na classe derivada. A definição de classes derivadas usa a seguinte sintaxe:
class classe_derivada : public classe_base
{ /*...*/ };
O código acima define uma classe com nome classe_derivada, que herda publicamente a classe com nome classe_base. A palavra reservada public pode ser substituído por protected ou private, dependendo do tipo de herança desejado. Este delimitador de acesso limita o nível de acesso aos membros herdados da classe-base: os membros com um nível de acesso mais acessível são herdados com o nível declarado na herança, enquanto os membros com níveis de acesso iguais ou mais restritivos mantém, na classe derivada, os níveis de restrição declarados na classe-base.
#include <iostream>
using namespace std;
class Polygon {
protected:
int width, height;
public:
void set_values (int a, int b)
{ width=a; height=b;}
};
class Rectangle: public Polygon {
public:
int area ()
{ return width * height; }
};
class Triangle: public Polygon {
public:
int area ()
{ return width * height / 2; }
};
int main () {
Rectangle rect;
Triangle trgl;
rect.set_values (4,5);
trgl.set_values (4,5);
cout << rect.area() << '\n';
cout << trgl.area() << '\n';
return 0;
}
- Experimento 1: compile e execute o exemplo acima.
- Experimento 2: substitua, no exemplo acima, uma herança pública por herança protegida ou privada e verifique o que acontece.
- Leitura extra - Polimorfismo: http://www.cplusplus.com/doc/tutorial/polymorphism/
Espaços de nomes
Espaços de nome, ou namespaces, permite agrupar entidades como classes, objetos e funções sob um mesmo nome. Deste modo o escopo global pode ser dividido em "sub-escopos", cada um com seu próprio nome.
A sintaxe para uso de um namespace em C++ é dada abaixo, onde identifier é o nome do sob o qual as entidades serão declaradas e, no local do comentário, seria registrado o conjunto de classes, objetos e funções incluídos no namespace:
namespace identifier
{
/* entities... */
}
Por exemplo, o código abaixo as variáveis a e b são inteiros normais declarados dentro do namespace myNamespace.
namespace myNamespace
{
int a, b;
}
Estas variáveis podem ser acessadas normalmente por classes ou funções declaradas dentro do mesmo namespace. Para serem acessadas de fora do namespace, contudo, elas precisam ser adequadamente qualificadas utilizando o operador de escopo (::). Por exemplo, para utilizar as variáveis acima de fora do myNamespace, elas devem ser qualificadas como:
myNamespace::a
myNamespace::b
Espaços de nomes podem ser bastante úteis para evitar colisão de identificadores:
// namespaces
#include <iostream>
using namespace std;
namespace foo
{
int value() { return 5; }
}
namespace bar
{
const double pi = 3.1416;
double value() { return 2*pi; }
}
int main () {
cout << foo::value() << '\n';
cout << bar::value() << '\n';
cout << bar::pi << '\n';
return 0;
}
- Experimento 1: compile, execute, e entenda o código do exemplo acima.
- Experimento 2: crie, dentro do namespace bar, uma função que acesse a função value do namespace foo.
- Leitura extra - Visibilidade de nomes em C++: http://www.cplusplus.com/doc/tutorial/namespaces/
Criando bibliotecas
Uma biblioteca é uma coleção de objetos, assim como uma biblioteca tradicional é uma coleção de livros. Quando construindo seu programa, você pode utilizar, no gcc, uma ou mais bibliotecas, de modo que o gcc utilizará os objetos nestas bibliotecas para completar seu programa. Por exemplo, todas as funções da biblioteca padrão C (como printf e exit) estão em uma biblioteca C, geralmente na pasta lib/libc.a da sua instalação GCC. Quando você faz a ligação do seu programa, o GCC adiciona ao binário os objetos da biblioteca C necessários, baseando-se nas chamadas de funções do seu programa. Importante perceber que apenas as funções/objetos utilizados são ligados ao programa, não gerando desperdício de tempo e espaço.
Para fazer usa própria biblioteca, você precisa, primeiro, compilar cada um dos arquivos-fonte, gerando um conjunto de arquivos-objeto. Aqui utilizaremos, como exemplo, o código do exercício-exemplo da aula anterior.
g++ -c pessoa.cc
g++ -c aluno.cc
A seguir, você utilizará o comando ar para criar uma biblioteca contendo os arquivos-objeto criados.
ar rvs mylib.a pessoa.o aluno.o
Cada uma das letras em rvs especifica um parâmetro para o ar. r significa substituir objetos com mesmo nome na biblioteca pelos novos passados pela linha de comando. Como a biblioteca está inicialmente vazia, isto significa o mesmo que adicionar novos objetos à biblioteca. Há também opções para extrair e remover objetos da biblioteca. A opção v significa verbose, ou seja, pede que o programa ar imprima na tela as ações sendo tomadas durante sua execução. Finalmente, a opção s diz ao ar para criar uma tabela de símbolos, que é um recurso extra que o GCC precisa para utilizar uma biblioteca.
Para utilizar a biblioteca, simplesmente adicione ela ao comando de ligação do gcc como se fosse outro objeto:
g++ main.cc mylib.a -o main
É importante listar as bibliotecas na ordem correta. Durante a ligação, o GCC "puxa" apenas os objetos que sabe necessitar até o momento. Isto que dizer que primeiro é necessário alimentar ao GCC os arquivos-objeto que dependem de uma biblioteca (no exemplo, o main.cc), e por fim as bibliotecas que completam esta dependência.
- Experimento 1: pegue o código-fonte da aula anterior e gere a biblioteca mylib.a utilizando os comandos acima.
- Experimento 2: modifique o arquivo makefile da aula anterior para trabalhar com a biblioteca.
- Experimento 3: modifique a assinatura de algum método das classes Pessoa ou Aluno e verifique o que acontece.
- Leitura extra - uso da C++ Standard Template Library: http://www.yolinux.com/TUTORIALS/LinuxTutorialC++STL.html
21/02: Finalização do conteúdo anterior e atividades em laboratório
Uso básico do Shell
=> Roteiro do Prof. Maziero: http://dainf.ct.utfpr.edu.br/~maziero/doku.php/unix:shell_basico
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:
/*
* Queue.h
*
* Created on: Feb 21, 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; }
virtual ~Element() {}
Element * prev() { return _prev; }
Element * next() { return _next; }
void prev(Element * p) { _prev = p; }
void next(Element * n) { _next = n; }
private:
Element * _prev;
Element * _next;
};
Element * head() { return &_head; }
int length() { return _length; }
void insert(Element * elem);
Element * remove();
private:
Element _head;
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, apresentado abaixo:
/*
* Queue_Test.cc
*
* Created on: Feb 21, 2014
* Author: arliones
*/
#include <iostream>
#include <Queue.h>
using namespace std;
using namespace BOOOS;
class MyElement : public Queue::Element {
public:
MyElement(string str) : _name(str) {}
virtual ~MyElement() {}
string & name() { return _name; }
private:
string _name;
};
void print_queue(Queue & q) {
cout << "Queue length: " << q.length() << endl;
if(q.length()) {
MyElement * elem = dynamic_cast<MyElement *>(q.head()->next());
do {
cout << elem->name() << endl;
elem = dynamic_cast<MyElement *>(elem->next());
} while (elem != q.head()->next());
}
cout << "==============================" << endl;
}
int main() {
cout << "Welcome to BOOOS - Basic Object Oriented Operating System!" << endl;
cout << "This program will test the class: Queue" << endl;
Queue queue;
MyElement * person1 = new MyElement("João");
MyElement * person2 = new MyElement("Pedro");
MyElement * person3 = new MyElement("Augusto");
MyElement * person4 = new MyElement("Fábio");
queue.insert(person1);
queue.insert(person2);
queue.insert(person3);
queue.insert(person4);
MyElement * removed_person = queue.remove();
delete removed_person; // Which element was removed?
return 0;
}
É 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 Kepler também foi disponibilizado aqui. Para utilizar este projeto:
- Baixe o Eclipse Kepler para C/C++;
- O eclipse não precisa ser instalado, basta descompactar o arquivo ZIP 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 zip do projeto;
- Verifique se o projeto chamado "booos" está selecionado na lista de "Projetos" ou "Projects";
- Clique em "Encerrar" ou "Finish", e o projeto deve aparecer no espaço de trabalho.
- Se você está utilizando o Ubuntu 13.10 e encontrou problemas com os menus, crie um script chamado "run_eclipse.sh" na mesma pasta do executável do eclipse com o conteúdo abaixo e execute este script ao invés do executável. Você pode precisar ajustar as permissões do arquivo executando "chmod +x run_eclipse.sh".
#!/bin/bash
UBUNTU_MENUPROXY= ./eclipse &
Resumo do trabalho
- O que é? Classe implementando fila como uma lista circular duplamente encadeada.
- Duração estimada: 4 horas.
- Dependências: Conhecimento básico de C/C++ e de estruturas de dados.
- Entrega: Até 14/03, por email, apenas o arquivo Queue.cc.
- Observação: Este trabalho será base para os demais trabalhos realizados no curso, logo, dediquem-se a esta implementação.
25/02: Gerência de tarefas: contextos, processos e threads
- Apresentação sobre Gerenciamento de Processos. [slides]
Roteiro de exercícios: gerenciamento de processos
Syscall FORK
- Em um terminal, execute "man fork"
- A função da API POSIX fork() aciona uma chamada de sistema (system call - syscall) que cria um novo processo duplicando o processo que realiza a chamada. O novo processo, chamado de filho, é uma cópia exata do processo criador, chamado de pai, exceto por alguns detalhes listados na manpage. O principal destes detalhes para nós agora é o fato de terem PIDs diferentes.
- O código dos dois processos (pai e filho) são idênticos;
- Os dados dos dois processos (pai e filho) são idênticos NO MOMENTO DA CRIAÇÃO;
- Execução do processo filho inicia na próxima instrução do programa (no retorno da chamada FORK);
- Não é possível saber qual dos processos (pai ou filho) retormará a execução primeiro - isto fica a cargo do excalonador do SO;
- Valores de retorno da chamada FORK:
- (-1): erro na criação do processo (ex.: memória insuficiente);
- (0): em caso de sucesso, este é o valor de retorno recebido pelo processo filho;
- (>0): em caso de sucesso, este é o valor de retorno recebido pelo processo pai;
Syscall JOIN
- A syscall JOIN é implementada no POSIX pelo função wait(). Execute "man wait".
- Além da função wait(), há também waitpid() e waitid();
- Todas estas syscalls são utilizadas para aguardar por mudanças no estado de um processo filho e obter informações sobre o processo filho cujo estado tenha mudado. São consideradas mudanças de estado: o filho terminou; o filho foi finalizado por um sinal (ex.: kill); o filho foi retomado por um sinal (ex.: alarme);
- A chamada wait também libera os recursos do processo filho que termina;
- '1'wait()'1': esta função suspende a execução do processo chamador até que UM DOS SEUS FILHOS finalize;
- waitpid(): suspende a execução do processo chamador até que UM FILHO ESPECÍFICO finalize;
Exemplos POSIX utilizando fork/wait
- Exemplo 1: fork/wait básico
// ex1: fork/wait básico
#include <sys/types.h>
#include <stdlib.h>
#include <stdio.h>
int main()
{
int pid, status;
pid = fork();
if(pid == -1) // fork falhou
{
perror("fork falhou!");
exit(-1);
}
else if(pid == 0) // Este é o processo filho
{
printf("processo filho\t pid: %d\t pid pai: %d\n", getpid(), getppid());
exit(0);
}
else // Este é o processo pai
{
wait(&status);
printf("processo pai\t pid: %d\t pid pai: %d\n", getpid(), getppid());
exit(0);
}
}
arliones@socrates:~/tmp$ gcc ex1.c -o ex1
arliones@socrates:~/tmp$ ./ex1
processo filho pid: 27858 pid pai: 27857
processo pai pid: 27857 pid pai: 5337
arliones@socrates:~/tmp$
- Exemplo 2: processos pai e filho compartilham código, mas não dados.
// ex2: fork/wait "compartilhando" dados
#include <sys/types.h>
#include <stdlib.h>
#include <stdio.h>
int main()
{
int pid, status, k=0;
printf("processo %d\t antes do fork\n", getpid());
pid = fork();
printf("processo %d\t depois do fork\n", getpid());
if(pid == -1) // fork falhou
{
perror("fork falhou!");
exit(-1);
}
else if(pid == 0) // Este é o processo filho
{
k += 1000;
printf("processo filho\t pid: %d\t K: %d\n", getpid(), k);
exit(0);
}
else // Este é o processo pai
{
wait(&status);
k += 10;
printf("processo pai\t pid: %d\t K: %d\n", getpid(), k);
exit(0);
}
k += 10;
printf("processo %d\t K: %d\n", getpid(), k);
exit(0);
}
arliones@socrates:~/tmp$ gcc ex2.c -o ex2
arliones@socrates:~/tmp$ ./ex2
processo 18425 antes do fork
processo 18425 depois do fork
processo 18426 depois do fork
processo filho pid: 18426 K: 1000
processo pai pid: 18425 K: 10
arliones@socrates:~/tmp$
- Modificação no código: comentar linhas 22 e 29
arliones@socrates:~/tmp$ gcc ex2.c -o ex2
arliones@socrates:~/tmp$ ./ex2
processo 32342 antes do fork
processo 32342 depois do fork
processo 32343 depois do fork
processo filho pid: 32343 K: 1000
processo 32343 K: 1010
processo pai pid: 32342 K: 10
processo 32342 K: 20
arliones@socrates:~/tmp$
- Analise os resultados e busque entender a diferença.
Exercício fork/wait
Excrever um programa C que cria uma árvore de 3 processos, onde o processo A faz um fork() criando um processo B, o processo B, por sua vez, faz um fork() criando um processo C. Cada processo deve exibir uma mensagem "Eu sou o processo XXX, filho de YYY", onde XXX e YYY são PIDs de processos. Utilizar wait() para garantir que o processo C imprima sua resposta antes do B, e que o processo B imprima sua resposta antes do A. Utilizar sleep() (man 3 sleep) para haver um intervalo de 1 segundo entre cada mensagem impressa.
28/02: Finalização do conteúdo anterior e atividades em laboratório
- Aviso: mudança na data de viagem do professor - aulas dos dias 25 e 28 de março ocorrerão normalmente.
- Revisão da solução do exercício fork/wait (aula anterior).
t1: Troca de contexto em nível de usuário
- O Linux, através da API POSIX, oferece um conjunto de funções que permite às aplicações manipular contextos, facilitando a vida do programador que quer implementar tarefas "simultâneas" dentro de um único processo, ou seja, threads. As seguintes funções e tipos estão disponíveis:
- getcontext(&a): salva o contexto na variável a;
- setcontext(&a): restaura um contexto salvo anteriormente na variável a;
- swapcontext(&a,&b): salva o contexto atual na variável a e restaura o contexto salvo anteriormente na variável b;
- makecontext(&a, ...): ajusta parâmetros internos do contexto salvo em a;
- ucontext_t: as variáveis a e b são do tipo ucontext_t. Este tipo armazena um contexto.
- Busque mais informações sobre estas funções utilizando o programa manpage do Linux (ex.: man getcontext).
- O objetivo deste trabalho é familiarizar o aluno com o conjunto de funções de manipulação de contexto de execução em espaço de usuário. Estas mesmas funções serão utilizadas no t2 para implementar uma classe de tarefa para nosso projeto.
- O entregável deste trabalho é um relatório. Estude o código no arquivo pingpong.c abaixo e explique seu funcionamento.
#include <stdio.h>
#include <stdlib.h>
#include <ucontext.h>
#define STACKSIZE 32768 /* tamanho de pilha das threads */
/* VARIÁVEIS GLOBAIS */
ucontext_t cPing, cPong, cMain;
/* Funções-comportamento das Tarefas */
void f_ping(void * arg) {
int i;
printf("%s iniciada\n", (char *) arg);
for (i=0; i<4; i++) {
printf("%s %d\n", (char *) arg, i);
swapcontext(&cPing, &cPong);
}
printf("%s FIM\n", (char *) arg);
swapcontext(&cPing, &cMain);
}
void f_pong(void * arg) {
int i;
printf("%s iniciada\n", (char *) arg);
for (i=0; i<4; i++) {
printf("%s %d\n", (char *) arg, i);
swapcontext(&cPong, &cPing);
}
printf("%s FIM\n", (char *) arg);
swapcontext(&cPong, &cMain);
}
/* MAIN */
int main(int argc, char *argv[]) {
char *stack;
printf ("Main INICIO\n");
getcontext(&cPing);
stack = malloc(STACKSIZE);
if(stack) {
cPing.uc_stack.ss_sp = stack ;
cPing.uc_stack.ss_size = STACKSIZE;
cPing.uc_stack.ss_flags = 0;
cPing.uc_link = 0;
}
else {
perror("Erro na criação da pilha: ");
exit(1);
}
makecontext(&cPing, (void*)(*f_ping), 1, "\tPing");
getcontext(&cPong);
stack = malloc(STACKSIZE);
if(stack) {
cPong.uc_stack.ss_sp = stack ;
cPong.uc_stack.ss_size = STACKSIZE;
cPong.uc_stack.ss_flags = 0;
cPong.uc_link = 0;
}
else {
perror("Erro na criação da pilha: ");
exit(1);
}
makecontext (&cPong, (void*)(*f_pong), 1, "\tPong");
swapcontext(&cMain, &cPing);
swapcontext(&cMain, &cPong);
printf("Main FIM\n");
exit(0);
}
- Elabore o relatório cobrindo/explicando, ao menos, o seguinte:
- Objetivo e parâmetros de cada uma das funções;
- Significado dos campos do tipo (struct) ucontext_t que foram utilizados no código acima;
- Explique o objetivo de cada linha de código de pingpong.c que chama uma destas funções ou que manipule ucontext_t.
Resumo do trabalho
- O que é? Estudo sobre funções de manipulação de contexto em espaço de usuário no Linux.
- Duração estimada: 2 horas.
- Dependências: Conhecimento básico de C e aula inicial de gerenciamento de processos.
- Entrega: Até 21/03, por email, apenas arquivo do relatório EM PDF.
t2: Estruturas de tarefas
- Neste trabalho deve-se extender 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: Feb 27, 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 que precisam ser implementados na classe estão na declaração acima. Contudo, 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. Um dos atributos necessários, não declarados, é uma Task guardando o contexto da Main. Onde será que será declarado o ucontext_t de cada Task? O teste no arquivo test/Task_Test.cc implementa a mesma aplicação do t1 utilizando a Task. Use este exemplo como teste inicial.
- 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).
Os arquivos iniciais do trabalho estão no zip do projetoc.
Resumo do trabalho
- O que é? Classe Task para nosso SO.
- Duração estimada: 4 horas.
- Dependências: t1 (troca de contexto).
- Entrega: Até 21/03, por email, apenas arquivos Task.h, Task.cc e Task_Test.cc.
07/03: Escalonamento de tarefas
- Notas de aula [slides]
- Animação de escalonamento de processos - Virginia Tech
11/03: Finalização do conteúdo anterior e atividades em laboratório: acompanhamento de projetos
- Finalização do conteúdo de escalonamento de tarefas (aula anterior)
- Acompanhamento de projetos
- Lembrete: entrega do t0 (biblioteca de fila) para próxima aula (sexta - 14/03)
t3: Despachante de tarefas
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!
Uma aplicação de testes está disponível junto dos esqueletos do projeto aqui. Algumas outras observações:
- Como nosso sistema está ficando mais complexo, foi criado um arquivo geral de configuração para ele: o lib/BOOOS.h. Por enquanto, ele tem uma função init que chamará os inits dos outros componentes. Ele também tem um parâmetro de configuração do sistema: o tipo de escalonador utilizado.
- 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.
Resumo do trabalho
- O que é? Classe implementando um escalonador FCFS para nosso sistema.
- Duração estimada: 5 horas.
- Dependências: Queue e Task.
- Entrega: Até 07/04, por email.
t4: Escalonamento por prioridades
No t3 foi implementado um escalonador First-Come First-Served (FCFS). Agora, a política de escalonamento 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.
Resumo do trabalho
- O que é? Modificações no sistema para suporta escalonamento por prioridade.
- Duração estimada: 3 horas.
- Dependências: Queue, Task e Scheduler.
- Entrega: Até 11/04, por email.
14/03: Atividades em laboratório: acompanhamento de projetos
- Acompanhamento de projetos
- Lembrete: entrega do t0 (biblioteca de fila) para hoje (sexta - 14/03)
17/03: Comunicação entre processos
- Lembrete: entrega de t1 e t2 (troca de contexto em nível de usuário) para sexta – 21/03.
- Notas de aula [slides]
Comunicação entre processos: Troca de mensagens
Um mecanismo disponibilizado por sistemas UNIX para troca de mensagens entre processos é o PIPE. Pipes são mecanismos de comunicação indireta onde mensagens são trocadas através de mailboxes. Cada mailbox possui um identificador único, permitindo que processos identifiquem o canal de comunicação entre eles. O fluxo de mensagens em um Pipe é:
- unidirecional: sobre um mesmo pipe, apenas um processo envia mensagens e um processo recebe mensagens;
- FIFO: as mensagens são entregues na ordem de envio;
- não-estruturado: não há estrutura pré-definida para o formato da mensagem.
No UNIX, pipes são inicializados através da SystemCall pipe, que possui a seguinte sintaxe:
- int pipe(int pipefd[2]): pipe inicializa um novo pipe no sistema e retorna, no array pipefd, os descritores identificando cada uma das pontas do pipe. A primeira posição do array, i.e. pipefd[0], recebe o descritor que pode ser aberto apenas para leitura, enquanto a segunda posição do array, i.e. pipefd[1], recebe o descritor que pode ser aberto apenas para escrita. A função retorna zero no caso de sucesso, ou -1 se ocorrer erro.
As primitivas send/receive para uso de um pipe no UNIX são implementadas por SystemCalls read/write, conforme segue:
- ssize_t read(int fd, void *buf, size_t count): “puxa” dados do pipe identificado pelo descritor fd. Os dados recebidos são os apontados pelo ponteiro buf, sendo count a quantidade máxima de bytes a serem recebidos. A função retorna o número de bytes recebidos.
- ssize_t write(int fd, const void *buf, size_t count): “empurra” dados no pipe identificado pelo descritor fd. Os dados transmitidos são os apontados pelo ponteiro buf, sendo count a quantidade de bytes a serem transmitidos. A função retorna o número de bytes transmitidos.
Abaixo há um exemplo de programa criando um pipe e compartilhando os descritores entre dois processos (criados via fork()).
#include <unistd.h>
#include <fcntl.h>
#include <stdio.h>
char *message = "This is a message!!!" ;
main()
{
char buf[1024] ;
int fd[2];
pipe(fd); /*create pipe*/
if (fork() != 0) { /* I am the parent */
write(fd[1], message, strlen (message) + 1) ;
}
else { /*Child code */
read(fd[0], buf, 1024) ;
printf("Got this from MaMa!!: %s\n", buf) ;
}
}
- Desafio: construa um “pipeline”. Crie um programa que conecta 4 processos através de 3 pipes, assim como na figura abaixo. Utilize fork() para criar vários processos.
21/03: Comunicação entre processos
- Lembrete: entrega de t1 e t2 (troca de contexto em nível de usuário) para hoje.
Comunicação entre processos: Memória Compartilhada
Outra maneira de compartilhar dados entre processos é utilizando memória compartilhada. Nestes casos, o sistema operacional precisa ser utilizado para "mapear" blocos de memória no espaço de endereçamento de cada processo (veremos mais tarde como isto é feito). Sistemas UNIX diponibilizam uma série de SystemCalls para compartilhar memória entre processos:
- int shmget(key_t key, size_t size, int shmflg): retorna o identificador de um segmento de memória compartilhado associado a uma chave de identificação (key). Caso a chave solicitada não exista e a flag IPC_CREAT está especificada, um novo segmento de memória compartilhada é criado, com o tamanho size.
- void *shmat(int shmid, const void *shmaddr, int shmflg): anexa/mapeia o segmento de memória especificado por shmid (obtido através de um shmget) no endereço shmaddr do espaço de endereçamento do processo.
- int shmdt(const void *shmaddr): desfaz o mapeamento do segmento de memória compartilhada que está mapeado em shmaddr.
- int shmctl(int shmid, int cmd, struct shmid_ds *buf): realiza a ação de controle indicada por cmd sobre o segmento de memória compartilhada identificado pelo shmid. Caso o cmd utilizado necessite de parâmetros, estes são passados em buf.
O programa abaixo cria um novo segmento de memória compartilhada em um sistema UNIX. A função ftok é utilizada para gerar uma chave única de identificação do segmento de memória (veja "man ftok"). O programa ipcs pode ser utilizado para verificar os segmentos de memória compartilhada disponíveis no sistema.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/types.h>
#include <sys/ipc.h>
#include <sys/shm.h>
#define SHM_SIZE 1024 /* make it a 1K shared memory segment */
int main(void)
{
key_t key;
int shmid;
char *data;
int mode;
/* make the key: */
if ((key = ftok("/tmp", 'X')) == -1) {
perror("ftok");
exit(1);
}
/* create the shared memory segment: */
if ((shmid = shmget(key, SHM_SIZE, 0644 | IPC_CREAT )) == -1) {
perror("shmget");
exit(1);
}
return(0);
}
O programa abaixo manipula o segmento criado pelo programa anterior. Perceba que o programa utiliza a função ftok com os mesmos parâmetros passados na criação. O sistema operacional utiliza esta chava única para identificar o segmento de memória a ser utilizado. Se o programa abaixo é executado com um string como parâmetro (ex.: "./shm_test abc123"), ele escreve este parâmetro no segmento de memória. Caso seja executado sem parâmetros (ex.: "./shm_test"), o programa imprime o conteúdo da memória compartilhada.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/types.h>
#include <sys/ipc.h>
#include <sys/shm.h>
#define SHM_SIZE 1024 /* make it a 1K shared memory segment */
int main(int argc, char *argv[])
{
key_t key;
int shmid;
char *data;
int mode;
/* make the key: */
if ((key = ftok("/tmp", 'X')) == -1) {
perror("ftok");
exit(1);
}
/* connect to the segment.
NOTE: There's no IPC_CREATE. What happens if you place IPC_CREATE here? */
if ((shmid = shmget(key, SHM_SIZE, 0644)) == -1) {
perror("shmget");
exit(1);
}
/* attach to the segment to get a pointer to it: */
data = shmat(shmid, (void *)0, 0);
if (data == (char *)(-1)) {
perror("shmat");
exit(1);
}
/* read or modify the segment, based on the command line: */
if (argc == 2) {
printf("writing to segment: \"%s\"\n", argv[1]);
strncpy(data, argv[1], SHM_SIZE);
} else
printf("segment contains: \"%s\"\n", data);
/* detach from the segment: */
if (shmdt(data) == -1) {
perror("shmdt");
exit(1);
}
return(0);
}
- Desafio: destrua um shm. Crie um programa que destrua o shm utilizado nos programas anteriores. Para isso utilize shmctl com o parâmetro apropriado (veja "man shmctl").
24/03: Coordenação entre processos
- Sincronização entre processos [slides]
- Algoritmos de sincronização
- Semáforos
28/03: Impasses e Problemas clássicos de coordenação
- Sincronização entre processos [slides]
- Impasses e tratamento de impasses
POSIX Semaphores
Nos sistemas POSIX, semáforos são implementados pelo tipo sem_t e manipulado através das funções (acesse as man-pages das chamadas para maiores detalhes):
- sem_init: inicializa um semáforo;
- sem_destroy: destroty um semáforo;
- sem_wait: implementa a operação p;
- sem_post: implementa a operação v.
Para utilizar estas funções é necessário linkar o programa à librt ou à libpthread (-lrt ou -lpthread). A classe C++ abaixo abstrai estas operações:
#ifndef __semaphore_h
#define __semaphore_h
#include <semaphore.h>
class Semaphore
{
public:
Semaphore(int i = 1) { sem_init(&sem, 0, i); }
~Semaphore() { sem_destroy(&sem); }
void p() { sem_wait(&sem); }
void v() { sem_post(&sem); }
private:
sem_t sem;
};
#endif
POSIX Threads
A API POSIX disponibiliza uma biblioteca de threads chamada pthread. As threads são implementadas pela estrutura pthread_t, e manipuladas pelas funções (acesse as man-pages das chamadas para maiores detalhes):
- pthread_create: cria uma thread;
- pthread_kill: força a terminação de uma thread;
- pthread_join: sincroniza o final de uma thread (qual a diferença/semelhança com o wait que usamos para processos?);
- pthread_exit: finaliza uma thread.
Para utilizar estas funções é necessário linkar o programa à libpthread (-lpthread). A classe C++ abaixo abstrai estas operações:
#ifndef __thread_h
#define __thread_h
#include <pthread.h>
#include <signal.h>
class Thread
{
public:
Thread(int ( * const entry)(int), int arg) {
if(pthread_create(&thread, 0, (void*(*)(void*))entry, (void *)arg))
thread = 0;
}
~Thread() { pthread_kill(thread, SIGKILL); }
int join(int * status) { return pthread_join(thread, (void **)status); }
friend void exit(int status = 0) { pthread_exit((void *) status); }
private:
pthread_t thread;
};
#endif
Problemas clássicos de sincronização
Produtor/Consumidor
O problema clássico Produtor/Consumidor consiste em dois fluxos de execução (threads/processos), sendo que um dos fluxos (consumidor) só pode executar a partir do momento em que seus dados de entrada foram produzidos pelo outro fluxo (produtor).
- DESAFIO: O programa abaixo implementa um produtor/consumidor utilizando semáforos para sincronização. Contudo, as chamadas para as operações v e p foram removidas, conforme comentários no código. Corrija este programa.
#include <iostream>
#include "thread.h"
#include "semaphore.h"
using namespace std;
const int DELAY = 10000000;
const int REP = 5;
Semaphore empty(1);
Semaphore full(0);
int producer(int n)
{
cout << "Producer was born!\n";
// Faltam, no laço abaixo:
// - uma chamada para empty.p()
// - uma chamada para full.v()
for(int i = 0; i < REP; i++) {
cout << "Producing ...\n";
for(int i = 0; i < DELAY * 10; i++);
cout << "Storing ...\n";
for(int i = 0; i < DELAY; i++);
}
return n;
}
int consumer(int n)
{
cout << "Consumer was born!\n";
// Faltam, no laço abaixo:
// - uma chamada para full.p()
// - uma chamada para empty.v()
for(int i = 0; i < REP; i++) {
cout << "Retrieving ...\n";
for(int i = 0; i < DELAY * 10; i++);
cout << "Consuming ...\n";
for(int i = 0; i < DELAY; i++);
}
return n;
}
int main()
{
cout << "The Producer x Consumer Problem\n";
Thread prod(&producer, REP);
Thread cons(&consumer, REP);
int status;
prod.join(&status);
if(status == REP)
cout << "Producer went to heaven!\n";
else
cout << "Producer went to hell!\n";
cons.join(&status);
if(status == REP)
cout << "Consumer went to heaven!\n";
else
cout << "Consumer went to hell!\n";
return 0;
}
Jantar dos Filósofos
O problema clássico Jantar dos Filósofos consiste em quem n fluxos (n filósofos) disputam n recursos (n talheres). No problema, para conseguir "jantar" (ou executar), cada filósofo precisa pegar dois talheres adjascentes a ele. Cada recurso é compartilhado por dois filósofos.
- DESAFIO: O programa abaixo implementa um Jantar dos Filósofos utilizando semáforos para sincronização. Contudo, as chamadas para as operações v e p foram removidas, conforme comentários no código. Corrija este programa.
#include <iostream>
#include "thread.h"
#include "semaphore.h"
using namespace std;
const int DELAY = 10000000;
const int ITERATIONS = 5;
Semaphore chopstick[5];
int philosopher(int n)
{
cout << "Philosopher " << n << " was born!\n";
int first = (n < 4)? n : 0; // left for phil 0 .. 3, right for phil 4
int second = (n < 4)? n + 1 : 4; // right for phil 0 .. 3, left for phil 4
// Foram removidos do laço abaixo:
// - uma chamada para chopstick[first].p()
// - uma chamada para chopstick[second].p()
// - uma chamada para chopstick[first].v()
// - uma chamada para chopstick[second].v()
for(int i = 0; i < ITERATIONS; i++) {
cout << "Philosopher " << n << " thinking ...\n";
for(int i = 0; i < DELAY * 10; i++);
cout << "Philosopher " << n << " eating ...\n";
for(int i = 0; i < DELAY; i++);
}
return n;
}
int main()
{
cout << "The Dining-Philosophers Problem\n";
Thread * phil[5];
for(int i = 0; i < 5; i++)
phil[i] = new Thread(&philosopher, i);
int status;
for(int i = 0; i < 5; i++) {
phil[i]->join(&status);
if(status == i)
cout << "Philosopher " << i << " went to heaven!\n";
else
cout << "Philosopher " << i << " went to hell!\n";
}
return 0;
}
31/03: Acompanhamento de projetos e revisão para prova
- Nossa prova será na sexta (04/04), na sala 09.
t5: Preempção e compartilhamento de tempo
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) ;
}
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. Baixem o novo gabarito do projeto aqui. Notem os presentes de páscoa em locais do código. :-) 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_ */
Sobre novo mecanismo de testes
Os testes que passei a vocês são, agora, 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:~/Dropbox/ifsc/teaching/SOP29005/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()).
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.
Resumo do trabalho
- O que é? Classe implementando temporizador (Timer) integrado ao escalonador.
- Duração estimada: 4 horas.
- Dependências: Scheduler.
- Entrega: Até 11/04, por email.
t6: 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.
Resumo do trabalho
- O que é? Mecanismo de contabilização de tempo de execução das tarefas.
- Duração estimada: 4 horas.
- Dependências: Scheduler, Task, Timer.
- Entrega: Até 11/04, por email.
04/04: Prova 1: Processos
- Prova será realizada na sala 09.
- Conteúdo da prova. Há listas de exercícios ao final do capítulo de alguns livros, especialmente do Fundamentos de sistemas operacionais.
- Abraham Silberschatz, Peter Baer Galvin, Greg Gagne Fundamentos de sistemas operacionais; 8ª ed. Rio de Janeiro:LTC, 2010. 536p. ISBN 9788521617471
- Parte I - Uma visão geral
- Parte II - Gerenciamento de processos
- Andrew S. Tanenbaum Sistemas operacionais modernos; 3ª ed. São Paulo:Pearson Education do Brasil, 2010. 672p. ISBN 9788576052371
- Capítulo 1: Introdução
- Capítulo 2: Processos e threads
- Rômulo S. Oliveira; Alexandre S. Carissimi; Simão S. Toscani Sistemas Operacionais; 4ª ed. Porto Alegre:Bookman, 2010. 375p. ISBN 9788577805211
- Capítulo 1: Introdução
- Capítulo 2: Multiprogramação
- Capítulo 3: Programação concorrente
- Abraham Silberschatz, Peter Baer Galvin, Greg Gagne Fundamentos de sistemas operacionais; 8ª ed. Rio de Janeiro:LTC, 2010. 536p. ISBN 9788521617471
07/04: Estruturas de memória
- Revisão da prova.
- [slides]
11/04: Acompanhamento de projetos
14/04: Apresentação dos projetos p0 a p6
25/04: Revisão para recuperação da prova 1
- Revisão de escalonamento e sincronização de processos
- Dúvidas dos alunos
28/04: Recuperação da Prova 1
- Prova na sala 09
05/05: Aula cancelada pelo professor
09/05: Estruturas de memória (cont.)
- [slides]
t7: 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, caso ainda não tenha sido feito:
- O ponto de partida deve ser o sistema implementado para o t6;
- 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;
}
Resumo do trabalho
- O que é? Garantia de operação adequada da tarefa main.
- Duração estimada: 2 horas.
- Dependências: t0 a t6.
- Entrega: Até 23/05, por email.
t8: 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(Task * t);
Ao chamar Task::self()->join(b), onde b é um ponteiro para outra Task, a tarefa atual (Task::self()) deve ser suspensa até a conclusão da tarefa b. Quando a tarefa b terminar, isto é, chamar o método exit(), a tarefa suspensa deve ser colocada de volta à fila de tarefas prontas. Caso a tarefa b 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 b, 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();
}
Task * Main = Task::self();
int result = 0;
cout << "Main wait pang... ";
result = Main->join(pang);
cout << "Result: " << result << endl;
cout << "Main wait peng... ";
result = Main->join(peng);
cout << "Result: " << result << endl;
cout << "Main wait ping... ";
result = Main->join(ping);
cout << "Result: " << result << endl;
cout << "Main wait pong... ";
result = Main->join(pong);
cout << "Result: " << result << endl;
cout << "Main wait pung... ";
result = Main->join(pung);
cout << "Result: " << result << endl;
cout << "Main End" << endl;
Main->exit(0);
return 0;
}
Resumo do trabalho
- O que é? Mecanismo de sincronização de tarefas.
- Duração estimada: 4 horas.
- Dependências: t0 a t6.
- Entrega: Até 23/05, por email.
t9: Chamada Sleep
A chamada de sistema sleep(t) é uma chamada de sistema UNIX que suspende o processo por t microsegundos. Como nossas tarefas são implementadas dentro de um processo, em um modelo N:1, todas as threads seriam suspensas juntas.
O objetivo deste projeto é criar um método sleep na classe Task com a assinatura abaixo:
void sleep(int t);
Este método faz com que somente a tarefa corrente seja suspensa durante o período desejado, sem perturbar a execução das demais tarefas.
Para implementar esta funcionalidade é necessário:
- Criar uma fila de "tarefas dormindo", separada da fila de prontas;
- Escrever o método sleep, que coloca a tarefa solicitante na fila de tarefas adormecidas, calcula o instante em que a tarefa deverá ser acordad e devolve o controle ao dispatcher;
- Periodicamente, o dispatcher deve percorrer a fila de tarefas adormecidas e devolver à fila de prontas aquelas que já podem "acordar".
Seu sistema deve funcionar com o código abaixo. Modifique os "couts" para imprimir também o tempo atual (Timer::time()) a fim de verificar se os tempos de "sono" estão corretos.
#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;
Task::self()->sleep(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();
}
Task * Main = Task::self();
int result = 0;
cout << "Main wait pang... ";
result = Main->join(pang);
cout << "Result: " << result << endl;
cout << "Main wait peng... ";
result = Main->join(peng);
cout << "Result: " << result << endl;
cout << "Main wait ping... ";
result = Main->join(ping);
cout << "Result: " << result << endl;
cout << "Main wait pong... ";
result = Main->join(pong);
cout << "Result: " << result << endl;
cout << "Main wait pung... ";
result = Main->join(pung);
cout << "Result: " << result << endl;
cout << "Main End" << endl;
Main->exit(0);
return 0;
}
Resumo do trabalho
- O que é? Mecanismo de delay com suspensão de tarefa.
- Duração estimada: 6 horas.
- Dependências: t0 a t6.
- Entrega: Até 23/05, por email.
12/05: Estruturas de memória (cont.)
- [slides]
16/05: Acompanhamento de projetos
19/05: Estruturas de memória (cont.)
- [slides]