SOP29005-2014-2
EngTel: Sistemas Operacionais - 2014-2
- Professor: Arliones Hoeller
- Turma: 29005
- Encontros: quartas e quintas das 15:40 às 17:30
- Atendimento paralelo: quintas das 9:40 às 10:35 e das 14:25 às 15:20
- Grupo de discussão
- Web: https://www.facebook.com/groups/sop29005.ifsc.2014.2/
- Email: sop29005.ifsc.2014.2@groups.facebook.com
- Outros cursos de sistemas operacionais nos quais este curso se baseia:
Plano de ensino
Cronograma de Atividades
Diário de Aulas
31/07: Apresentação da Disciplina. Visão geral de funções, responsabilidades 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]
- Capítulo 1 do livro do Silberschatz
06/08: Laboratório: Linux e GCC/G++
- Referência sobre C++: http://www.cplusplus.com/
- Livros sobre C++:
- Tutorial C++
- Exercício-exemplo feito em aula. [código-fonte]
Herança
Classes em C++ podem ser estendidas, criando novas classes que retêm as característica da classe-base. Este processo, conhecido como herança, envolve uma classe-base e uma classe derivada: a classe derivada herda os membros da classe-base, sobre os quais ela pode adicionar seus próprios membros.
Por exemplo, imaginemos uma série de classes para descrever dois tipos de polígonos: retângulos e triângulos. Estes dois polígonos têm certas propriedades em comum, como os valores necessários para calcular suas áreas: ambos podem ser descritos simplificadamente com uma altura e uma largura. (ou base).
Isto pode ser representado no formato de classes como uma classe Polygon (polígono) da qual podemos derivar duas outras classes: Rectangle e Triangle:
A classe Polygon poderia conter membros comuns a ambos os tipos de polígonos. Em nosso caso: largura e altura (width e height). E as classes Rectangle e Triangle poderiam ser as classes derivadas, com características específicas que diferenciam um tipo de polígono de outro.
Classes que são derivadas de outras herdam todos os membros acessíveis da classe-base. Isto significa que se a classe-base inclui um membro A e nós derivamos uma classe dela, e esta nova classe possui um membro B, a classe derivada conterá ambos os membros A e B.
No C++, a relação de herança de duas classes é declarada na classe derivada. A definição de classes derivadas usa a seguinte sintaxe:
class classe_derivada : public classe_base
{ /*...*/ };
O código acima define uma classe com nome classe_derivada, que herda publicamente a classe com nome classe_base. A palavra reservada public pode ser substituído por protected ou private, dependendo do tipo de herança desejado. Este delimitador de acesso limita o nível de acesso aos membros herdados da classe-base: os membros com um nível de acesso mais acessível são herdados com o nível declarado na herança, enquanto os membros com níveis de acesso iguais ou mais restritivos mantém, na classe derivada, os níveis de restrição declarados na classe-base.
#include <iostream>
using namespace std;
class Polygon {
protected:
int width, height;
public:
virtual int area() = 0;
void set_values (int a, int b)
{ width=a; height=b;}
};
class Rectangle: public Polygon {
public:
int area ()
{ return width * height; }
};
class Triangle: public Polygon {
public:
int area ()
{ return width * height / 2; }
};
int main () {
Rectangle rect;
Triangle trgl;
rect.set_values (4,5);
trgl.set_values (4,5);
cout << rect.area() << '\n';
cout << trgl.area() << '\n';
return 0;
}
- Experimento 1: compile e execute o exemplo acima.
- Experimento 2: substitua, no exemplo acima, uma herança pública por herança protegida ou privada e verifique o que acontece.
- Leitura extra - Polimorfismo: http://www.cplusplus.com/doc/tutorial/polymorphism/
Espaços de nomes
Espaços de nome, ou namespaces, permite agrupar entidades como classes, objetos e funções sob um mesmo nome. Deste modo o escopo global pode ser dividido em "sub-escopos", cada um com seu próprio nome.
A sintaxe para uso de um namespace em C++ é dada abaixo, onde identifier é o nome do sob o qual as entidades serão declaradas e, no local do comentário, seria registrado o conjunto de classes, objetos e funções incluídos no namespace:
namespace identifier
{
/* entities... */
}
Por exemplo, o código abaixo as variáveis a e b são inteiros normais declarados dentro do namespace myNamespace.
namespace myNamespace
{
int a, b;
}
Estas variáveis podem ser acessadas normalmente por classes ou funções declaradas dentro do mesmo namespace. Para serem acessadas de fora do namespace, contudo, elas precisam ser adequadamente qualificadas utilizando o operador de escopo (::). Por exemplo, para utilizar as variáveis acima de fora do myNamespace, elas devem ser qualificadas como:
myNamespace::a
myNamespace::b
Espaços de nomes podem ser bastante úteis para evitar colisão de identificadores:
// namespaces
#include <iostream>
using namespace std;
namespace foo
{
int value() { return 5; }
}
namespace bar
{
const double pi = 3.1416;
double value() { return 2*pi; }
}
int main () {
cout << foo::value() << '\n';
cout << bar::value() << '\n';
cout << bar::pi << '\n';
return 0;
}
- Experimento 1: compile, execute, e entenda o código do exemplo acima.
- Experimento 2: crie, dentro do namespace bar, uma função que acesse a função value do namespace foo.
- Leitura extra - Visibilidade de nomes em C++: http://www.cplusplus.com/doc/tutorial/namespaces/
Criando bibliotecas
Uma biblioteca é uma coleção de objetos, assim como uma biblioteca tradicional é uma coleção de livros. Quando construindo seu programa, você pode utilizar, no gcc, uma ou mais bibliotecas, de modo que o gcc utilizará os objetos nestas bibliotecas para completar seu programa. Por exemplo, todas as funções da biblioteca padrão C (como printf e exit) estão em uma biblioteca C, geralmente na pasta lib/libc.a da sua instalação GCC. Quando você faz a ligação do seu programa, o GCC adiciona ao binário os objetos da biblioteca C necessários, baseando-se nas chamadas de funções do seu programa. Importante perceber que apenas as funções/objetos utilizados são ligados ao programa, não gerando desperdício de tempo e espaço.
Para fazer usa própria biblioteca, você precisa, primeiro, compilar cada um dos arquivos-fonte, gerando um conjunto de arquivos-objeto. Aqui utilizaremos, como exemplo, o código do exercício-exemplo da aula anterior.
g++ -c pessoa.cc
g++ -c aluno.cc
A seguir, você utilizará o comando ar para criar uma biblioteca contendo os arquivos-objeto criados.
ar rvs mylib.a pessoa.o aluno.o
Cada uma das letras em rvs especifica um parâmetro para o ar. r significa substituir objetos com mesmo nome na biblioteca pelos novos passados pela linha de comando. Como a biblioteca está inicialmente vazia, isto significa o mesmo que adicionar novos objetos à biblioteca. Há também opções para extrair e remover objetos da biblioteca. A opção v significa verbose, ou seja, pede que o programa ar imprima na tela as ações sendo tomadas durante sua execução. Finalmente, a opção s diz ao ar para criar uma tabela de símbolos, que é um recurso extra que o GCC precisa para utilizar uma biblioteca.
Para utilizar a biblioteca, simplesmente adicione ela ao comando de ligação do gcc como se fosse outro objeto:
g++ main.cc mylib.a -o main
É importante listar as bibliotecas na ordem correta. Durante a ligação, o GCC "puxa" apenas os objetos que sabe necessitar até o momento. Isto que dizer que primeiro é necessário alimentar ao GCC os arquivos-objeto que dependem de uma biblioteca (no exemplo, o main.cc), e por fim as bibliotecas que completam esta dependência.
- Experimento 1: pegue o código-fonte da aula anterior e gere a biblioteca mylib.a utilizando os comandos acima.
- Experimento 2: modifique o arquivo makefile da aula anterior para trabalhar com a biblioteca.
- Experimento 3: modifique a assinatura de algum método das classes Pessoa ou Aluno e verifique o que acontece.
- Leitura extra - uso da C++ Standard Template Library: http://www.yolinux.com/TUTORIALS/LinuxTutorialC++STL.html
07/08: Arquitetura de sistemas operacionais e modelos de programação
- Apresentação sobre histórico visão geral e estruturas básicas de um SO [slides]
- Capítulo 2 do livro do Silberschatz
13/08: Gerência de tarefas; contextos, processos e threads
- Apresentação sobre Gerenciamento de Processos. [slides]
14/08: Atividades em laboratório: API POSIX – fork/wait
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.
t0: Biblioteca de Filas
Uma maneira de descrever um Sistema Operacional, sob o ponto de vista da programação, é definir-lo como um grande gerenciador de filas. São exemplos de filas importantes de um SO as filas de processos prontos a serem executados, processos suspensos, processos dormindo e processos bloqueados em semáforos. Para o trabalho da disciplina implementaremos nossas filas através de uma lista circular duplamente encadeada, cuja estrutura pode ser vista na figura abaixo.
Para recapitular a execução de operações sobre uma lista encadeada, consulte o material de Programação II. Lembre-se, nossa estrutura de dados é uma Fila, ou seja, elementos são inseridos no final e removidos do início.
Neste projeto você deve construir uma pequena biblioteca que ofereça uma classe Queue com métodos de inserção e remoção de elementos genéricos. O código-base da classe, que está nos arquivos [1] e [2]. A declaração da classe é apresentada abaixo:
/*
* BOOOS.h
*
* Created on: Aug 14, 2014
* Author: arliones
*/
#ifndef QUEUE_H_
#define QUEUE_H_
namespace BOOOS {
class Queue {
public:
Queue();
virtual ~Queue();
class Element {
public:
Element() { _prev = 0; _next = 0; _rank = 0; }
virtual ~Element() {}
Element * prev() { return _prev; }
Element * next() { return _next; }
int rank() { return _rank; }
void prev(Element * p) { _prev = p; }
void next(Element * p) { _next = p; }
void rank(int r) { _rank = r; }
private:
Element * _prev;
Element * _next;
int _rank;
};
Element * head() { return &_head; }
int length() { return _length; }
void insert(Element * elem);
void insert_ordered(Element * elem);
Element * remove();
void remove(Element * e);
private:
Element * search(Element * elem);
Element _head; // _head.next will point to head, _head.prev will point to tail
int _length;
};
}
#endif /* QUEUE_H_ */
Esta fila organiza objetos do tipo Element*. A classe Element deve ser estendida para implementar os detalhes da aplicação, como no exemplo do arquivo Queue_Test.cc.
É responsabilidade do aluno implementar mais testes além dos que estão no exemplo para garantir o funcionamento da fila. Apenas o arquivo Queue.cc deve ser entregue ao professor, devidamente preenchido (os métodos estão vazios no original).
Um projeto pré-configurado para o Elicpse Luna também foi disponibilizado aqui. Para utilizar este projeto:
- Baixe o Eclipse Luna para C/C++;
- O eclipse não precisa ser instalado, basta descompactar o arquivo baixado;
- Execute o eclipse através do executável "eclipse" na basta descompactada;
- Baixe o projeto disponibilizado pelo professor;
- No eclipse, acesse "Arquivo->Importar..." ou "File->Import...";
- Selecione a opção "Geral->Projetos Existentes para a Área de Trabalho" ou "General->Existing Projects into Workspace" e clique "Next" ou "Próximo";
- Selecione a opção "Selecionar arquivo compactado" ou "Select archive file", clique em "Buscar..." ou "Browse..." e selecione o arquivo compactado do projeto;
- Verifique se o projeto chamado "booos-t0" está selecionado na lista de "Projetos" ou "Projects";
- Clique em "Encerrar" ou "Finish", e o projeto deve aparecer no espaço de trabalho.
Observe que a pasta do projeto possui Makefiles. Se preferir, não é necessário utilizar o Eclipse para compilar e testar o projeto, basta usar os seguintes comandos, a partir do diretório do projeto (booos-t0):
$ make all #Compila sistema e gera aplicação padrão
$ ./booos #Executa aplicação padrão
$ make TEST=Queue_Test test #Compila teste implementado em "Queue_Teste.cc"
$ ./test/Queue_Test #Executa aplicação teste
Resumo do trabalho
- O que é? Classe implementando uma fila usando uma lista circular duplamente encadeada.
- Duração estimada: 6 horas.
- Dependências: Conhecimento básico de C/C++ e de estruturas de dados.
- Entrega: Até 04/09, por email, apenas o arquivo Queue.cc (não modifiquem o Queue.h!).
- Observação: Este trabalho será base para os demais trabalhos realizados no curso, logo, dediquem-se a esta implementação para evitar problemas futuros.
20/08: Escalonamento de tarefas
- Notas de aula [slides]
- Animação de escalonamento de processos - Virginia Tech
21/08: Atividades em laboratório: Estrutura de processos
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).
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);
}
t1: troca de contexto e tarefas cooperativas
Neste trabalho deve-se estender o projeto sendo desenvolvido no curso com a construção de uma classe para abstrair processos em nível de usuários - na prática, threads. A classe implementada será chamada de Task (tarefa). Lembre-se que uma classe é uma estrutura de dados, logo, nossa classe Task será o PCB (Proccess Control Block) do sistema. A partir deste trabalho, será disponibilizado um gabarito em C++ como no código abaixo, geralmente incompleto, e um diagrama UML de uma versão completa da solução implementada pelo professor, como na imagem abaixo.
/*
* Task.h
*
* Created on: Aug 15, 2014
* Author: arliones
*/
#ifndef TASK_H_
#define TASK_H_
#include <Queue.h>
#include <ucontext.h>
namespace BOOOS {
class Task : public Queue::Element {
public:
enum State {
READY,
WAITING,
RUNNING,
FINISHING
};
Task(void (*entry_point)(void *), int nargs, void * arg);
virtual ~Task();
int tid() { return _tid; }
State state() { return _state; }
void pass_to(Task * t, State s = READY);
void exit(int code);
static Task * self() { return (Task*)__running; }
static void init();
private:
static volatile Task * __running;
State _state;
int _tid; // task ID
// ...
};
} /* namespace BOOOS */
#endif /* TASK_H_ */
Os métodos de interface (i.e., os públicos) que precisam ser implementados na classe estão na declaração acima. Não altere a assinatura destes métodos! Observe que você certamente precisará de novos atributos para o correto funcionamento da classe, e seria bom utilizar alguns métodos privados para auxiliar na implementação. Você pode criar métodos e atributos privados à vontade. Onde será que será declarado o ucontext_t de cada Task?
O teste no arquivo test/Task_Test.cc implementa uma aplicação para testar sua classe Task. Use este exemplo como teste inicial. Abaixo há uma descrição detalhada dos métodos de interface da classe.
- Task(void (*entry_point)(void *), int nargs, void * arg): construtor - deve inicializar todos os atributos dos objetos.
- virtual ~Task(): destrutor - deve liberar recursos alocados pelo construtor (new/malloc).
- int tid(): getter do Task ID (_tid).
- State state(): getter do estado do processo (_state).
- void pass_to(Task * t, State s = READY): este método salva o contexto do objeto (this) e carrega o contexto da Task recebida por parâmetro. O estado passado em s é o novo estado do objeto que está deixando a CPU. Há algum atributo de classe (static) que precisa ser atualizado aqui?
- void exit(int code): finaliza a Task (this) e configura o valor de resultado da task com o valor de code. Por enquanto, se preocupem em fazer a Task retornar a execução para a main. Ignorem o parâmetro code agora - utilizaremos ele mais adiante.
- static Task * self(): método de classe (static) que retorna a Task executando no momento.
- static void init(): método de classe que precisa ser chamando na inicialização do sistema e deve inicializar os atributos de classe (static).
Resumo do trabalho
- O que é? Classe Task para nosso SO.
- Duração estimada: 6 horas.
- Dependências: nenhum.
- Entrega: Até 11/09, por email, apenas arquivos Task.h, Task.cc e Task_Test.cc (se modificado).