Mudanças entre as edições de "SOP29005-2014-1"

De MediaWiki do Campus São José
Ir para navegação Ir para pesquisar
Linha 2 004: Linha 2 004:
 
== 19/05: Estruturas de memória (cont.) ==
 
== 19/05: Estruturas de memória (cont.) ==
 
* [[https://www.dropbox.com/s/vazv17qcejmm9hk/SOP29005-parte4.pdf slides]]
 
* [[https://www.dropbox.com/s/vazv17qcejmm9hk/SOP29005-parte4.pdf slides]]
 +
 +
== 23/05: Acompanhamento de projetos ==
 +
* [[http://www.lisha.ufsc.br/teaching/os/exercise/hello.html A verdadeira hitória do "Hello World!"]]

Edição das 09h39min de 23 de maio de 2014

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:

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 30/05/2014
t8 Operador join 05/05/2014 30/05/2014
t9 Chamada sleep 05/05/2014 30/05/2014
tA Semáforo 26/05/2014 06/06/2014
tB Uso de semáforos 26/05/2014 13/06/2014
tC Fila de mensagens 26/05/2014 13/06/2014
t7 - tC Apresentação dos trabalhos - 16/06/2014
tD Gerente de disco (trabalho de recuperação) 16/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++

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:

Inheritance.png

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.

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.

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.


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.

DoublyCircularlyLinkedList.png

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.

Booos.png 

/*
 * 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

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

Dispatcher.png

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.

Booos-t3.png

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.

Booos-prio.png

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

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

Booos-preempt.png 

/*
 * 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.


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

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

16/05: Acompanhamento de projetos

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

23/05: Acompanhamento de projetos

Disponível em “https://wiki.sj.ifsc.edu.br/index.php?title=SOP29005-2014-1&oldid=69567”