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:
  • Sistemas Operacionais - Ciências da Computação UFSC
  • Sistemas Operacionais - Engenharia da Computação UTFPR

Cronograma de Atividades - Ajustado

Aula	Data	Horas	Conteúdo	Recursos
1	31/7	2	Apresentação da Disciplina. Visão geral de funções, responsabilidades e estruturas de um SO	Lab. Informática
2	6/8	2	Atividades em laboratório: Introdução ao Linux e GCC	Lab. Informática
3	7/8	2	Arquitetura de sistemas operacionais e modelos de programação	Lab. Informática
4	13/8	2	Gerência de tarefas; contextos, processos e threads	Lab. Informática
5	14/8	2	Atividades em laboratório: API POSIX – fork/wait – t0: biblioteca de filas	Lab. Informática
6	20/8	2	Escalonamento de tarefas	Lab. Informática
7	21/8	2	Atividades em laboratório: Estrutura de processos (a verdadeira história do Hello World) – t1: troca de contexto e tarefas cooperativas	Lab. Informática
8	27/8	2	Atividade em laboratório: acompanhamento de projetos	Lab. Informática
9	28/8	2	Algoritmos de escalonamento	Lab. Informática
10	3/9	2	Algoritmos de escalonamento / Revisão para prova	Lab. Informática
11	4/9	2	Revisão e correção de listas de exercícios	Lab. Informática
12	10/9	2	P0 (introdução e gerência de tarefas)	Lab. Informática
13	11/9	2	Atividades em laboratório: pthreads – t2: escalonamento FIFO e por prioridades	Lab. Informática
14	17/9	2	Comunicação entre processos: Troca de mensagens e Memória Compartilhada	Lab. Informática
15	18/9	2	Atividade em laboratório: programação com pipes e API shm – t3: Preempção e compartilhamento de tempo	Lab. Informática
16	24/9	2	Coordenação entre processos	Lab. Informática
17	25/9	2	Laboratório: Problemas clássicos de coordenação; impasses	Lab. Informática
18	1/10	2	Laboratório: Problemas clássicos de coordenação; impasses	Lab. Informática
19	2/10	2	Laboratório: Problemas clássicos de coordenação; impasses	Lab. Informática
20	8/10	2	Laboratório: Problemas clássicos de coordenação; impasses	Lab. Informática
21	9/10	2	Laboratório: Problemas clássicos de coordenação; impasses	Lab. Informática
22	15/10	2	Encaminhamento para palestra MCC	Lab. Informática
23	16/10	2	Revisão e correção de listas de exercícios	Lab. Informática
24	22/10	2	P1 (comunicação e coordenação de tarefas)	Lab. Informática
25	23/10	2	Gerenciamento de memória: Introdução	Lab. Informática
26	29/10	4	Gerenciamento de memória: paginação e segmentação.	Lab. Informática
27	30/10	2	Atividade em laboratório: alocação de memória.	Lab. Informática
28	5/11	2	Aula adiantada em 29/out	Lab. Informática
29	6/11	0	Aula adiada: viagem do professor	Lab. Informática
30	12/11	2	Gerenciamento de memória: memória virtual	Lab. Informática
31	13/11	2	Gerenciamento de memória: memória virtual	Lab. Informática
32	19/11	2	Revisão e correção de listas de exercícios	Lab. Informática
33	20/11	2	P2 (gerenciamento de memória)	Lab. Informática
34	26/11	2	Sistemas de arquivos: introdução e controle de acesso	Lab. Informática
35	27/11	2	Sistemas de arquivos: estudos de caso e gerenciamento de memória secundária	Lab. Informática
36	3/12	2	Gerenciamento de entrada e saída: introdução / Atividade em laboratório: construção de módulo para Linux	Lab. Informática
37	4/12	2	Revisão e correção de listas de exercícios	Lab. Informática
38	10/12	2	P3 (sistemas de arquivo e gerenciamento de entrada e saída)	Lab. Informática
TOTAL		76

Notas

Matrícula	P0	P1	P2	P3	T0	T1	Final
122001838-4	A	A	B	B	A	B	A
122001432-0	A	B	B	A	A	B	A
122005026-1	A	B	A	B	A	B	A
122006899-3	B	A	C	A	A	C	B
122001913-5	B	A	A	B	A	C	B

Material de aula

Slides

• Arquivo:SOP29005-parte1.pdf
• Arquivo:SOP29005-parte2.pdf
• Arquivo:SOP29005-parte3.pdf
• Arquivo:SOP29005-parte4.pdf
• Arquivo:SOP29005-parte5.pdf
• Arquivo:SOP29005-parte6.pdf
• Arquivo:SOP29005-parte7.pdf

Listas de exercícios

As listas de exercícios são compostas por exercícios selecionados do livro do Silberschatz, 8a edição. Há 10 volumes deste livro na biblioteca do campus, sendo suficiente para toda a turma deste semestre.

SILBERSCHATZ, Abraham; GALVIN, Peter; GAGNE, Greg. Fundamentos de sistemas operacionais. 8. ed. Rio de Janeiro: LTC, 2011. 515 p., il. ISBN 9788521617471.

Exercícios selecionados:

• Parte 1
  • Capítulo 1: 1-3, 6-8, 10, 13, 14, 17, 22, 23, 25.
  • Capítulo 2: 1-8, 12, 13, 15, 17, 22, 25.
• Parte 2
  • Capítulo 3: 1, 3, 6-10, 13, 15
  • Capítulo 4: 1, 4, 7, 8, 10-13
  • Capítulo 5: 1-3, 5, 6, 9, 10, 13-15, 21
• Parte 3
  • Capítulo 6: 1, 2 (utilizar semáforos POSIX), 6, 8, 11-15, 18, 20, 21, 25, 29, 39.
• Parte 4
  • Capítulo 8: 1-6, 9-21, 23.
  • Capítulo 9: 1-8, 14-16, 19-23, 28.
• Parte 5
  • Capítulo 10: 1-20
  • Capítulo 11: 1-7
  • Capítulo 12: 1-7, 13-14 (desafio).

Projeto

Esta disciplina utiliza um projeto contínuo, no qual os alunos desenvolvem um aplicativo que emula um sistema operacional no espaço de usuário no Linux. Este projeto é chamado de BOOOS - Basic Object Oriented Operating System.

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 (Arquivo:SOP29005-parte1.pdf)
• 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++:
  • 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]

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:

    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

• 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

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 (Arquivo:SOP29005-parte1.pdf)
• Capítulo 2 do livro do Silberschatz

13/08: Gerência de tarefas; contextos, processos e threads

• Apresentação sobre Gerenciamento de Processos (Arquivo:SOP29005-parte2.pdf)
• Capítulo 3 do livro do Silberschatz

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;
  • wait(): 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;

Syscall EXEC

• A syscall EXEC é implementada no POSIX pela família de funções exec(). Execute "man exec".
  • As principais funções da família são execl(), execlp() e execvp();
  • Todas estas funções são, na realidade, front-ends (abstrações) para a syscall execve. Esta syscall substitui a imagem do processo corrente (aquele que chama a syscall) pela a imagem de um novo processo;
  • Os parâmetros passados a estas funções são, basicamente, o nome de um arquivo com a imagem do programa a ser executado (um binário de um programa), e uma lista de parâmetros a serem passados a este novo programa;

Exemplos POSIX utilizando fork/wait/exec

• Exemplo 1: fork/wait básico

// ex1: fork/wait básico
#include <sys/types.h>
#include <stdlib.h>
#include <stdio.h>
#include <unistd.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());
        execl("/bin/ls","ls", (char*) NULL);
        perror("execl falhou!");
        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.

20/08: Escalonamento de tarefas

• Notas de aula (Arquivo:SOP29005-parte2.pdf)
• Animação de escalonamento de processos - Virginia Tech
• Capítulo 5 do livro do Silberschatz.

21/08: Atividades em laboratório: Estrutura de processos

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

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);
}

28/08: Algoritmos de escalonamento

• Notas de aula (Arquivo:SOP29005-parte2.pdf)
• Capítulo 5 do livro do Silberschatz.

11/09: Atividades em laboratório: pthreads – t2: escalonamento FIFO e por prioridades

• Conclusão do conteúdo da aula anterior

Introdução a POSIX Threads

A biblioteca POSIX Threads, ou simplesmente pthreads, é parte do padrão POSIX para programar utilizando threads. O padrão POSIX.1c define a API para criação e manipulação de threads. Esta API é encontrada na maioria dos sistemas baseados no Unix, como Linux, Mac OS X, Solaris, entre outros. Também existem alternativas adaptando a API para sistemas Windows, como a pthreads-w32.

A API da pthreads inclui métodos para criar, manipular e destruir threads, além de outras estruturas de dados para sincronizar as threads, incluindo implementações de mutexes e variáveis de condição.

A API POSIX semaphore, utilizada para sincronização de processos ou threads, também funciona em conjunto com a pthreads, embora sua implementação esteja definida em outro padrão, o POSIX.1b.

Programas em C/C++ que utilizarão a pthreads devem incluir o cabeçalho pthread.h:

#include <pthread.h>

Principais elementos da API

• pthread_t (struct)

Estrutura que armazena dados/atributos de uma pthread.

• pthread_create

Função que cria uma thread, incializando-a e deixando-a pronta para executar. O código abaixo apresenta um exemplo simples de um programa utilizando pthreads.

#include <pthread.h>

pthread_t threads[2];

void *thread_func(void *arg) {
    // ...
}

int main(int argc, char **argv) {
    int i;
    for(i = 0; i < 2; i++) {
        pthread_create(&(threads[i]), NULL, thread_func,NULL);
    }
    for(i = 0; i < 2; i++) {
        pthread_join(threads[i], NULL);
    }
}

• pthread_join

Bloqueia execução de uma thread até que outra thread termine. Similar à chamada de sistema wait usada em processos Unix.

• pthread_exit

Encerra a execução de uma thread. A chamada a esta função por uma thread gera a liberação de outras threads que estejam, eventualmente, bloqueadas nela por uma chamada pthread_join.

O código abaixo apresenta um programa completo utilizando pthreads, onde threads recebem argumentos.

#include <stdlib.h>
#include <stdio.h>
#include <pthread.h>

typedef struct {
    int idx, length;
} thread_arg, *ptr_thread_arg;

pthread_t threads[2];

void *thread_func(void *arg) {
    ptr_thread_arg targ = (ptr_thread_arg) arg;
    int i;

    for(i = targ->idx; i < (targ->idx + targ->length); i++)
        printf(“Thread %d – value %d\n”, pthread_self(), i);
}

int main(int argc, char **argv) {
    thread_arg arguments[2];
    int i;
    for(i = 0; i < 2; i++) {
        arguments[i].idx = i * 10;
        arguments[i].length = 10;
        pthread_create(&(threads[i]), NULL, thread_func, &(arguments[i]));
    }
    for(i = 0; i < 2; i++) {
        pthread_join(threads[i], NULL);
    }
}

Ao compilar um programa com pthreads é necessário "linkar" com a biblioteca. Para isso, deve ser usando a opção -lpthread com o gcc.

gcc ... -lpthread

Exercícios

• Implemente o exemplo do Ping e Pong utilizando pthreads.

17/09 e 18/09: Comunicação entre processos

• Notas de aula (Arquivo:SOP29005-parte3.pdf)

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 1: construa um “pipeline”. Crie um programa que conecta 4 processos através de 3 pipes. Utilize fork() para criar vários processos.

• Desafio 2: cópia de arquivo. Projete um programa de cópia de arquivos chamado FileCopy usando pipes comuns. Esse programa receberá dois parâmetros: o primeiro é o nome do arquivo a ser copiado e o segundo é o nome do arquivo copiado. Em seguida, o programa criará um pipe comum e gravará nele o conteúdo do arquivo a ser copiado. O processo filho lerá esse arquivo do pipe e o gravará no arquivo de destino. Por exemplo, se chamarmos o programa como descrito a seguir:

$ FileCopy entrada.txt copia.txt

o arquivo entrada.txt será gravado no pipe. O processo filho lerá o conteúdo desse arquivo e o gravará no arquivo de destino copia.txt. Escreva o programa usando os pipes da API POSIX no Linux.

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);
}

• Desafio1: 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/09: Coordenação de processos

• Sincronização entre processos (Arquivo:SOP29005-parte4.pdf)
  • Algoritmos de sincronização
  • Exclusão Mútua
  • Semáforos

• Curiosidade: A inversão de prioridades na Mars Pathfinder

25/09: Laboratório: Impasses e Problemas clássicos de coordenação

• Sincronização entre processos (Arquivo:SOP29005-parte4.pdf)

POSIX pthread mutex

A biblioteca pthread implementa um tipo pthread_mutex_t, que garante a exclusão mútua entre threads. Estes mutex são manipulados através das funções (acesse as man-pages das chamadas para maiores detalhes):

• pthread_mutex_lock: acessa um mutex.
• pthread_mutex_trylock: tenta acessar um mutex (retorna valor indicando sucesso ou falha no lock).
• pthread_mutex_unlock: libera um mutex.

#ifndef __mutex_h
#define __mutex_h

#include <pthread.h>

class Mutex
{
public:
    Mutex() {}
    ~Mutex() {}

    void lock() { pthread_mutex_lock(&mut); }
    bool try_lock() { return (pthread_mutex_trylock(&mut) == 0); } // true when succeeds.
    void unlock() { pthread_mutex_unlock(&mut); }

private:
    pthread_mutex_t mut;
};

#endif

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: destroy 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); }

    operator int()
    {
        int ret;
        sem_getvalue(&sem, &ret);
        return ret;
    }

private:
    sem_t sem;
};

#endif

Exemplo de uso do operator:

Semaphore sem;
cout << (int)sem << endl;

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
• Veja esta descrição do problema

• 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 que 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
• Veja esta descrição do problema

• 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;
}

01/10 a 08/10: Laboratório: programação concorrente

Exercício 1

O programa abaixo cria 5 threads, e cada uma destas threads atualiza uma variável global (memória compartilhada).

#include <iostream>
#include "thread.h"

#define NUM_THREADS 5

using namespace std;

int saldo = 1000;

int AtualizaSaldo(int n)
{
	int meu_saldo = saldo;
	int novo_saldo = meu_saldo + n*100;
	cout << "Novo saldo = " << novo_saldo << endl;
	saldo = novo_saldo;
}

int main()
{
	Thread * threads[NUM_THREADS];

	for(int t = 0; t < NUM_THREADS; t++)
		threads[t] = new Thread(&AtualizaSaldo, t+1);

	int status;
	for(int t = 0; t < NUM_THREADS; t++) {
		threads[t]->join(&status);
		cout << "Thread " << t << " terminou com status " << status << "." << endl;
	}

	cout << "Saldo final é " << saldo << "." << endl;
}

1. Compile este programa. Você precisará da classe Thread implementada na aula passada.
2. Execute este programa várias vezes. Ele funciona? Será que ele gera as saídas esperadas?
3. Identifique as seções críticas do programa.
4. Corrija o programa utilizando mutex. Utilize a classe Mutex implementada na aula passada.
5. Analise a função AtualizaSaldo() com a sua solução. Lembre-se que o uso do mutex implica em apenas uma thread acessar a seção crítica por vez, enquanto outras threads ficam bloqueadas, esperando. Disso vem que, quanto menor o trecho de código entre um lock e um unlock, menos tempo uma thread necessita ficar esperando.
6. Modifique a função AtualizaSaldo() para reduzir o tempo de lock do programa.
7. Modifique o programa para usar um semáforo binário ao invés de um mutex em sua solução. Utilize a classe Semaphore da aula passada.

Exercício 2

O programa abaixo manipula uma matriz de tamanho MxN (veja os defines para o tamanho da matriz). A função SumValues soma todos os valores em uma linha da matriz. A linha a ser somada é identificada pela variável i. Modifique o programa principal (main) nos locais indicados para:

1. Criar N threads, uma para somar os valores de cada linha.
2. Receber o resultado do somatório de cada linha e gerar o somatório total da matriz.
3. Analise o programa: há problemas de sincronização que precisam ser resolvidos? Se sim, resolva-os.

#include <iostream>
#include "thread.h"

/* number of matrix columns and rows */
#define M 5
#define N 10

using namespace std;

int matrix[N][M];
Thread *threads[N];


/* thread function; it sums the values of the matrix in the row */
int SumValues(int i)
{
	int n = i; /* number of row */
	int total = 0; /* the total of the values in the row */
	int j;
	for (j = 0; j < M; j++) /* sum values in the "n" row */
		total += matrix[n][j];
	cout << "The total in row" << n << " is " << total << "." << endl;
	/* terminate a thread and return a total in the row */
	exit(total);
}

int main(int argc, char *argv[])
{
	int i, j;
	int total = 0; /* the total of the values in the matrix */

	 /* initialize the matrix */
	for (i = 0; i < N; i++)
		for (j = 0; j < M; j++)
			matrix[i][j] = i * M + j;

	/* create threads */
	/* COLOQUE SEU CÓDIGO PARA CRIAR AS THREADS AQUI! */

	/* wait for terminate a threads */
	/* COLOQUE SEU CÓDIGO PARA PEGAR O SOMATÓRIO DE LINHAS E TOTALIZAR A SOMA DA MATRIZ AQUI! */

	cout << "The total values in the matrix is " << total << endl;

	return 0;
}

Exercício 3

Corrija os problemas de sincronização do programa abaixo.

#include <iostream>
#include <fstream>
#include <uuid/uuid.h>
#include <unistd.h>
#include <errno.h>

#include "thread.h"

using namespace std;

const int PRODS = 100;
const int REP = 10;

const int CONS = 20;

const int BUF_SIZE = 35;

Thread * prods[PRODS];
Thread * cons[CONS];

uuid_t buffer[BUF_SIZE];
static int prod_pos = 0;
static int cons_pos = 0;

bool finished = false;

int producer(int n)
{
	cout << "Producer was born!" << endl;

	int rep = REP;

	char fname[36+1];

	while(rep--)
	{
		if(++prod_pos == BUF_SIZE) prod_pos = 0;
		uuid_generate(buffer[prod_pos]);
		uuid_unparse(buffer[prod_pos], fname);

		string name(fname,sizeof(uuid_t)*2 + 4);
		ofstream file(name.c_str());
		file << name;
		file.close();
	}

	exit(REP);
}

int consumer(int n)
{
	cout << "Consumer was born!" << endl;

	char fname[36+1];
	int consumed = 0;


	while(true)
	{
		if(finished) exit(consumed);

		consumed++;

		if(++cons_pos == BUF_SIZE) cons_pos = 0;
		uuid_unparse(buffer[cons_pos], fname);

		{
			ifstream file(fname);
			if(!file.good()) continue;
			string str;
			file >> str;
			cout << "Consumed: " << str << endl;
		}

		if(remove(fname)) cerr << "Error: " << errno << endl;
	}

	exit(consumed);
}

int main()
{
    cout << "Massive Producer x Consumer Problem\n";

    // Create
    for(int i = 0; i < PRODS; i++)
    	prods[i] = new Thread(&producer, i);
    for(int i = 0; i < CONS; i++)
    	cons[i] = new Thread(&consumer, i);

    // Join
    int status = 0;
    int produced = 0;
    int consumed = 0;
    for(int i = 0; i < PRODS; i++)
    {
    	prods[i]->join(&status);
    	produced += status;
    }

    finished = true;

    for(int i = 0; i < CONS; i++)
    {
    	cons[i]->join(&status);
    	consumed += status;
    }

    cout << "Total produced: " << produced << endl;
    cout << "Total consumed: " << consumed << endl;

    return 0;
}

Utilize o script abaixo para executar o programa. O script cria um diretório em /tmp/test onde são salvos os arquivos criados pelos produtores. Para ter certeza de que todos os arquivos foram adequadamente consumidos (i.e., deletados), o diretório /tmp/test deve estar vazio após a execução do programa.

#!/bin/bash

export myrun_DIR=`pwd`
export myrun_TEST=/tmp/test

rm -rf $myrun_TEST
mkdir $myrun_TEST
cd $myrun_TEST
$myrun_DIR/multi_prod_cons
cd $myrun_DIR

Problemas de sincronização a serem considerados:

1. Limite de tamanho do buffer: os produtores só podem produzir se houver espaço no buffer - nunca pode haver mais que BUF_SIZE arquivos na pasta de troca de arquivos.
2. Uso da posição do buffer: verificar se a posição consumida já foi de fato produzida.
3. Consumo: verificar se todos os arquivos produzidos foram consumidos.
4. Sistema de arquivos: verificar se os arquivos estão sendo sincronizados adequadamente no sistema de arquivos (ver man 2 sync).

23/10: Gerenciamento de memória: Introdução

• Arquivo:SOP29005-parte5.pdf

29/10 e 30/10: Gerenciamento de memória

• Arquivo:SOP29005-parte5.pdf

Atividade prática

Escreva um programa de computador que, dada a configuração de um sistema de paginação e um endereço de entrada, forneça informações sobre o endereço dado no referido sistema. Mais detalhes abaixo:

• Entradas do programa:
  • Largura do endereço em bits
  • Tamanho das páginas em bytes
  • Arquivo com tabela de páginas
  • Endereço a ser traduzido

• Saídas do programa:
  • Número de frames no sistema
  • Número da página (endereço lógico)
  • Número do frame (endereço físico) (Hit ou Page Fault?)
  • Deslocamento

A tabela de páginas estará em um arquivo em modo texto contendo um mapeamento por linha, como o abaixo. Observe que o arquivo contém os números de página ou frame, e não endereços.

0-10
1-9
2-20
3-37
4-1
5-4
6-7
7-6

A classe abaixo pode ser utilizada para processar o arquivo de entrada. Ela utiliza um map da STL para fazer o mapeamento. Você precisará implementar o método get_frame desta classe.

/*
 * MapFile.h
 *
 *  Created on: Oct 29, 2014
 *      Author: arliones
 */

#ifndef MAPFILE_H_
#define MAPFILE_H_

#include <string>
#include <map>
#include <fstream>
#include <stdlib.h>
#include <iostream>

using namespace std;

class MapFile {
	MapFile() {}
public:
	MapFile(string filename)
	{
		ifstream file(filename.c_str());
		string line;
		char line_c[256];
		unsigned int page, frame, delimiter;
		while(!file.eof()) {
			file.getline(line_c,256); line = string(line_c);
			delimiter = line.find('-');
			page = atoi(line.substr(0,delimiter+1).c_str());
			frame = atoi(line.substr(delimiter+1).c_str());
			_pt.insert(make_pair(page,frame));
		}

	}

	virtual ~MapFile() {}

	// Returns the number of the frame or -1 if not found
	unsigned int get_frame(unsigned int page)
	{
		//TODO
	}

	void print_page_table()
	{
		cout << "Page Table:" << endl;
		map<unsigned int, unsigned int>::iterator mit = _pt.begin();
		for(; mit != _pt.end(); ++mit)
			cout << mit->first << " - " << mit->second << endl;
	}

private:
	map<unsigned int, unsigned int> _pt;
};

#endif /* MAPFILE_H_ */

Abaixo, exemplos de execução do programa desejado:

arliones@socrates:~/workspace/paging_sim$ ./paging_sim
Usage: ./paging_sim ADDR_LEN PAGE_SIZE MAP_FILE ADDRESS

arliones@socrates:~/workspace/paging_sim$ ./paging_sim 16 1024 page_table.txt 5687
Frames in the system: 64
Requested page: 5
Requested frame: 4
Offset: 567

arliones@socrates:~/workspace/paging_sim$ ./paging_sim 16 1024 page_table.txt 10578
Frames in the system: 64
Requested page: 10
Requested frame: Page Fault
Offset: 338

arliones@socrates:~/workspace/paging_sim$ ./paging_sim 32 4096 page_table.txt 8632
Frames in the system: 1048576
Requested page: 2
Requested frame: 20
Offset: 440

arliones@socrates:~/workspace/paging_sim$ ./paging_sim 32 4096 page_table.txt 68723
Frames in the system: 1048576
Requested page: 16
Requested frame: Page Fault
Offset: 3187

arliones@socrates:~/workspace/paging_sim$ ./paging_sim 32 4194304 page_table.txt 354
Frames in the system: 1024
Requested page: 0
Requested frame: 10
Offset: 354

arliones@socrates:~/workspace/paging_sim$ ./paging_sim 32 4194304 page_table.txt 43554432
Frames in the system: 1024
Requested page: 10
Requested frame: Page Fault
Offset: 1611392

Dicas: utilize variáveis unsigned do tipo adequado em seus cálculos. Você provavelmente precisará das funções log2 e exp2 da libmath (include math.h).

12/11 e 13/11: Memória Virtual

• Arquivo:SOP29005-parte5.pdf

19/11 e 20/11: Sistemas de arquivos

• Arquivo:SOP29005-parte6.pdf

26/11: Revisão para prova

• Dúvidas / Lista de exercícios.
• Aula será no

03/12: Sistemas de arquivos: estudos de caso

• Arquivo:SOP29005-parte6.pdf

04/12: Gerenciamento de entrada e saída: introdução / Atividade em laboratório: construção de módulo para Linux

• Arquivo:SOP29005-parte7.pdf