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

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	30/05/2014
t8	Operador join	05/05/2014	30/05/2014
t9	Chamada sleep	05/05/2014	30/05/2014
tA	Construção de Semáforos	30/05/2014	13/06/2014
tB	Uso de semáforos	30/05/2014	13/06/2014
tC	Fila de mensagens	30/05/2014	13/06/2014
t7 - tC	Apresentação dos trabalhos	-	16/06/2014
RT	Trabalho de recuperação: reapresentação individual de todos os projetos.	16/06/2014	10/07/2014

Notas

Matrícula	P0	R0	P1	R1	T0	T1	RT	Final
121000556-5	D	B	B	B	C	D	B	B
121003145-0	D	A	A	A	A	A		A
121001036-4	D	C	D	B	A	A		B
121003013-6	B	B	B	B	A	A		A
121003282-1	D	C	A	A	D	B	C	C
121001865-9	C	C	B	B	C	D	B	B
121000526-3	C	A	C	C	A	A		A
121000088-1	C	C	B	B	A	A		B
121001105-0	C	A	B	B	A	A		A
121003758-0	D	B	C	C	A	A		B
121000653-7	D	A	C	B	D	B	B	B
121003004-7	C	C	C	C	A	A		B
121001065-8	F	F	F	F	F	F	F	FI

Relação de Entrega dos Trabalhos Práticos

Grupo	t0	t1	t2	t3	t4	t5	t6	t7	t8	t9	tA	tB	T0	T1	REC
121000556-5, 121001865-9	OK	OK	OK	OK	OK	Zz	Zz	Zz	Zz	Zz	Zz	Zz	C	D	B,B
121003145-0, 121003013-6	OK	OK	OK	OK	OK	OK	OK	OK	OK	OK	OK	OK	A	A	-
121001036-4, 121003004-7	OK	OK	OK	OK	OK	OK	OK	OK	OK	OK	OK	OK	A	A	-
121003282-1, 121000653-7	OK	OK	Zz	Zz	Zz	Zz	Zz	OK	OK	OK	OK	OK	D	B	C,B
121000526-3, 121001105-0	OK	OK	OK	OK	OK	OK	OK	OK	OK	OK	OK	OK	A	A	-
121000088-1, 121003758-0	OK	OK	OK	OK	OK	OK	OK	OK	OK	OK	OK	OK	A	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++:
  • The C++ Programming Language (4th Edition)
  • C++ How to Program, Fifth Edition
• Tutorial C++
  • Moving from Java to 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

• http://www.cplusplus.com/doc/tutorial/inheritance/

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

• http://www.cplusplus.com/doc/tutorial/namespaces/

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

• http://www.delorie.com/djgpp/doc/ug/larger/archives.html

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:

1. Baixe o Eclipse Kepler para C/C++;
2. O eclipse não precisa ser instalado, basta descompactar o arquivo ZIP baixado;
3. Execute o eclipse através do executável "eclipse" na basta descompactada;
4. Baixe o projeto disponibilizado pelo professor;
5. No eclipse, acesse "Arquivo->Importar..." ou "File->Import...";
6. Selecione a opção "Geral->Projetos Existentes para a Área de Trabalho" ou "General->Existing Projects into Workspace" e clique "Next" ou "Próximo";
7. Selecione a opção "Selecionar arquivo compactado" ou "Select archive file", clique em "Buscar..." ou "Browse..." e selecione o arquivo zip do projeto;
8. Verifique se o projeto chamado "booos" está selecionado na lista de "Projetos" ou "Projects";
9. 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:

1. Objetivo e parâmetros de cada uma das funções;
2. Significado dos campos do tipo (struct) ucontext_t que foram utilizados no código acima;
3. 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.

1. 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));
2. 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;
3. 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;
4. 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).

• Veja esta simulação

• 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.

• Veja esta simulação

• 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

07/04: Estruturas de memória

• Revisão da prova.

• [slides]

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

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]

19/05: Estruturas de memória (cont.)

• [slides]

23/05: Acompanhamento de projetos

• A verdadeira hitória do "Hello World!"

30/05: Estruturas de memória (cont.)

• [slides]

tA: Construção de Semáforos

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

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

#ifndef SEMAPHORE_H_
#define SEMAPHORE_H_

namespace BOOOS
{

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

} /* namespace BOOOS */

#endif /* SEMAPHORE_H_ */

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

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

Observações:

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

tB: Uso de Semáforos

Para avaliar o uso do semáfor implementado no tA, você implementará, usando seu BOOOS, a aplicação produtor/consumidor. Já implementamos esta aplicação antes, mas utilizando uma versão de semáforo que o Linux nos oferece. Adapte aquela aplicação para usar o seu semáforo e o Task::sleep() ao invés dos delays por laço.

tC: Fila de Mensagens

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

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

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

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

#ifndef MESSAGEQUEUE_H_
#define MESSAGEQUEUE_H_

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

namespace BOOOS
{

class Message_Queue
{
public:

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

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

        char * get() { return _msg; }

    private:
        char _msg[MSG_SIZE];
    };

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

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

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

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

} /* namespace BOOOS */

#endif /* MESSAGEQUEUE_H_ */

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

• Message_Queue(ing max_size): cria uma fila de mensagens. Cada fila pode ter, no máximo, max_size mensagens.
• ~Message_Queue(): destroi uma fila de mensagens. Mensagens ainda na fila, mas não consumidas, devem ser destruídas. Tarefas bloqueadas aguardando por mensagens devem ser liberadas.
• send(Message & msg): insere uma mensagem no final da fila. A mensagem deve ser criada externamente pela aplicação. Se a fila estiver cheia, este método bloqueia a tarefa até que espaço seja liberado na fila.
• Message receive(): retorna uma cópia de uma mensagem recebida. Se a fila estiver vazia, esta chamada bloqueia a tarefa até que uma mensagem chegue.
• count(): retorna a quantidade de mensagens na fila.

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);
        myself->sleep(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_Configuration::SCHEDULER_TYPE = Scheduler::SCHED_FCFS;
    BOOOS_Configuration::SCHEDULER_PREEMPT = true;
    BOOOS_Configuration::SCHEDULER_AGING = true;
    BOOOS::init();

    Task * myself = Task::self();

    Task prod(&producer);
    Task cons(&consumer);

    myself->join(&prod);
    myself->join(&cons);

    myself->exit(0);

    return 0;
}

06/06: Gerenciamento de arquivos

• [slides]

Estudo de caso: sistema de arquivos no Linux

Neste estudo de caso faremos alguns exercícios práticos que nos permitirão verificar como o sistema de arquivos é organizado no Linux.

Para isto, seguiremos este roteiro do Prof. Maziero da UTFPR.

09/06: Sistemas de arquivos

• [slides]

• Este material do Prof. Krzyzanowski da Rutgers University descreve a implementação de alguns sistemas de arquivos.

16/06: Apresentação de projetos t7 a tC

• Notas atualizadas no início da página.

23/06: Gerenciamento de entrada/saída

• [slides]

04/07: Prova 2

• Na sala 15