SOP-EngTel (página)
Sistemas Operacionais
- Professor: Arliones Hoeller
- Encontros: Quartas às 09:40 e sextas às 7:30 no Laboratório de Redes II.
- Inscreva-se neste grupo de discussão.
Notas
Avaliações
Aluno | P0 | P1 | T0 | T1 | T2 | Final |
---|---|---|---|---|---|---|
141002772-4 | 7 () | 9 () | 6 | 9 | 8 | 8 |
141004490-4 | 8 (0) | 3 (6) | 7 | 4 | 7 | 6 |
132002450-5 | 7 (0) | 4 (7) | 8 | 7 | 6 | 7 |
131000557-5 | 3 (4) | 3 (9) | 7 | 5 | 7 | 6 |
132002452-1 | 7 () | 3 () | 8 | 7 | 8 | 6 |
141004492-0 | 3 (6) | 1 (2) | 7 | 5 | 6 | 5 |
142002023-4 | 9 () | 8 () | 6 | 9 | 8 | 8 |
Material de aula
Slides
- Introdução a Sistemas Operacionais
- Escalonamento de Processos
- Comunicação entre Processos
- Coordenação de Processos (Programação Concorrente)
- Gerenciamento de Memória
- Gerenciamento de Arquivos
- Gerenciamento de Entrada e Saída
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.
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:
- 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.
- 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
- Capítulo 6: 1, 2 (utilizar semáforos POSIX), 6, 8, 11-15, 18, 20, 21, 25, 29, 39.
- Capítulo 8: 1-6, 9-21, 23.
- Capítulo 9: 1-8, 14-16, 19-23, 28.
- Capítulo 10: 1-20
- Capítulo 11: 1-7
- Capítulo 12: 1-7, 13-14 (desafio).
- Capítulo 13: 1, 4, 5, 6.
Conteúdo
Unidade 01: Introdução |
---|
Unidade 01: IntroduçãoApresentação do Curso
Visão geral de funções, responsabilidades e estruturas de um SO
Arquitetura de sistemas operacionais e modelos de programação
|
Unidade 02: Processos |
---|
Unidade 02: ProcessosGerência de tarefas; contextos, processos e threads
Escalonamento de tarefas
Comunicação entre Processos
Coordenação de processos
|
Unidade 03: Memória |
---|
Unidade 03: MemóriaIntrodução ao Gerenciamento de Memória
Memória Principal
Memória Virtual
|
Unidade 04: Armazenamento |
---|
Unidade 04: ArmazenamentoInterface do Sistema de Arquivos
Implementação do Sistema de Arquivos
Estrutura de Armazenamento em Massa
Gerenciamento de Entrada e Saída
|
Laboratórios
GCC/G++ no Linux |
---|
GCC/G++ no Linux
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;
}
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;
}
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.
|
Processos no Linux |
---|
Processos no Linux
// 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());
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$
// 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$
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$
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.
O status passado como parâmetro à função wait(&status) é, na verdade, o mecanismo de retorno de resultado do wait/waitpid. Ao retornar, esta variável contém informações sobre o resultado da execução do processo filho. Por exemplo, se um processo terminou normalmente (i.e., chamou exit), o comando WIFEXITED(status) retorna true. Este comando retorna false se o processo foi abortado (e.g., segmentation fault) ou morto (e.g., kill). Investigue no manual do wait no Linux (man wait) o funcionamento do comando WEXITSTATUS(status), e use-o para modificar o exercício anterior para calcular o 5!, sendo que cada processo pode executar apenas uma multiplicação. |
Threads de aplicação |
---|
Threads de aplicaçãoO 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:
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);
}
|
Trocas de mensagens com pipes |
---|
Trocas de mensagens com pipes
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 é:
No UNIX, pipes são inicializados através da SystemCall pipe, que possui a seguinte sintaxe:
As primitivas send/receive para uso de um pipe no UNIX são implementadas por SystemCalls read/write, conforme segue:
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>
#include <string.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) ;
}
}
|
Memória compartilhada entre processos |
---|
Memória compartilhada entre processosOutra 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:
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);
}
#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);
}
/* connect to memory segment: */
if ((shmid = shmget(key, SHM_SIZE, 0644)) == -1) {
perror("shmget");
exit(1);
}
/* delete he segment */
if( shmctl(shmid, IPC_RMID, NULL) == -1) {
perror("shmctl");
exit(1);
}
return(0);
}
|
POSIX Threads |
---|
POSIX ThreadsA 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>
#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);
}
}
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 libpthread. Para isso, deve ser usando a opção -lpthread com o gcc. gcc ... -lpthread
Thread d571a700 – value 0 Thread d4f19700 – value 10 Thread d571a700 – value 1 Thread d4f19700 – value 11 Thread d571a700 – value 2 Thread d4f19700 – value 12 Thread d571a700 – value 3 Thread d4f19700 – value 13 Thread d571a700 – value 4 Thread d4f19700 – value 14 Thread d571a700 – value 5 Thread d4f19700 – value 15 Thread d571a700 – value 6 Thread d4f19700 – value 16 Thread d571a700 – value 7 Thread d4f19700 – value 17 Thread d571a700 – value 8 Thread d4f19700 – value 18 Thread d571a700 – value 9 Thread d4f19700 – value 19
|
Programação concorrente |
---|
Programação concorrente
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):
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() {}
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
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):
#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
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):
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;
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;
}
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:
#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;
}
|
Problemas clássicos de coordenação de processos |
---|
Problemas clássicos de coordenação de processos
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).
#include <iostream>
#include "thread.h"
#include "semaphore.h"
using namespace std;
const int REP = 5;
char buffer;
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()
char data = -1;
for(int i = 0; i < REP; i++) {
cout << "Producing ...\n";
data = (char) i + 0x61;
buffer = data;
cout << "Stored... " << data << endl;
}
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()
char data = -1;
for(int i = 0; i < REP; i++) {
cout << "Retrieving ...\n";
data = buffer;
cout << "Consumed... " << data << endl;
}
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;
}
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.
#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;
}
|
Tradução de endereços com paginação |
---|
Tradução de endereços com paginaçãoEscreva 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:
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: 0x237 (567)
Logical Address: 0x1637 (5687)
Physical Address: 0x1237 (4663)
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: 0x152 (338)
Logical Address: 0x2952 (10578)
Physical Address: 0xfffffd52 (4294966610)
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: 0x1b8 (440)
Logical Address: 0x21b8 (8632)
Physical Address: 0x141b8 (82360)
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: 0xc73 (3187)
Logical Address: 0x10c73 (68723)
Physical Address: 0xfffffc73 (4294966387)
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: 0x162 (354)
Logical Address: 0x162 (354)
Physical Address: 0x2800162 (41943394)
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: 0x189680 (1611392)
Logical Address: 0x2989680 (43554432)
Physical Address: 0xffd89680 (4292384384)
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). |
Permissões de sistema de arquivos no Linux |
---|
Permissões de sistema de arquivos no LinuxNeste estudo de caso são realizados alguns exercícios práticos que permitem verificar como o sistema de arquivos é organizado no Linux. Acesse o estudo de caso através deste roteiro do Prof. Maziero da UTFPR. |
Projetos
TerminALL - FORK/WAIT/EXEC na prática - Prazo: 14/09/2016 |
---|
TerminALL - FORK/WAIT/EXEC na práticaVocê deve utilizar as chamadas de sistema fork, wait e exec para implementar em C++ um interpretador de comandos. Os requisitos do projeto são apresentados na figura abaixo. Uma estrutura geral do sistema é dado pelo diagrama de classes abaixo. Este diagrama é uma versão inicial e, certamente, incompleto. O sistema final de vocês provavelmente terá novos métodos ou assinaturas diferentes para os métodos que estão ali. Além da execução de programas, o projeto deve implementar os comandos exit, para encerrar o programa, e jobs, para listar os processos filhos em execução. Para embasar seu trabalho, estude as seguintes man pages.
Entrega: Sexta, 22/04/2016, por email, em duplas. Entregar o código-fonte do projeto, acompanhado de relatório curto com o diagrama de classes atualizado (implementado) e uma descrição de como o sistema foi testado. Um versão do projeto com classes VAZIAS E INCOMPLETAS pode ser baixada aqui. |
Programação Concorrente - Prazo: 30/10/2016 |
---|
Programação ConcorrenteCorrija 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:
Entrega: Domingo, 30/10/2016, por email, em duplas. Entregar:
|
Implementação de driver Linux |
---|
Implementação de módulo LinuxFase 1: módulo de compartilhamento de dados via char device - Prazo: 11/12/2016Para esta parte do trabalho, você deve implementar um módulo Linux que permite a troca de informações entre processos por meio de um char device. Para isso, o módulo deve:
Para testar o módulo:
O que entregar?
Fase 2: driver de porta serial - Prazo: 18/12/2016De maneira similar à atividade anterior, você deve implementar um módulo Linux que implemente o driver de uma porta serial que exporta sua interface por um char device. As escritas no dispositivo devem gerar dados sendo enviados pela porta serial. Leituras no dispositivo devem retornar caracteres que chegam pela porta serial. Para isso, o módulo deve:
Para testar o módulo, utilize os mesmos programas de teste da atividade anterior, apenas substituindo o nome do dispositivo usado. Observação: Informações detalhadas de como interagir com o hardware serial para configurar, enviar e receber dados serão encaminhadas para a lista de email da turma. O que entregar?
|