SOP-EngTel 2018 1

Sistemas Operacionais

• Professor: André D'Amato
• Encontros: Segundas às 7:30 e sextas às 09:40 no Laboratório de Redes II.
• Atendimento paralelo: Quarta 9:30 às 10:30 na sala telecomunicações 1.

• Plano de Ensino
• Cronograma

Material de aula

Slides

• Introdução a Sistemas Operacionais

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.

Conteúdo

Unidade 01: Introdução

Unidade 01: Introdução Apresentação do Curso Plano de Ensino Cronograma Visão geral de funções, responsabilidades e estruturas de um SO Revolution OS: documentário sobre Linux e software livre Apresentação sobre histórico visão geral e estruturas básicas de um SO Capítulo 1 do livro do Silberschatz Arquitetura de sistemas operacionais e modelos de programação Apresentação sobre histórico visão geral e estruturas básicas de um SO Capítulo 2 do livro do Silberschatz

Unidade 02: Processos

Unidade 02: Processos Gerência de tarefas; contextos, processos e threads Apresentação sobre Gerenciamento de Processos Capítulo 3 do livro do Silberschatz Escalonamento de tarefas Apresentação sobre Escalonamento de Processos Animação de escalonamento de processos - Virginia Tech Capítulo 5 do livro do Silberschatz. Estudo de caso: escalonador do Linux. Escalonador antigo O(n). Escalonador do kernel 2.6 O(1). Escalonador atual O(log(n)). Slides da University of Columbia sobre o mecanismo de escalonamento do Linux. Comunicação entre Processos Apresentação sobre Comunicação entre Processos Capítulo 3 do livro do Silberschatz. Coordenação de processos Apresentação sobre Coordenação de Processos Capítulos 6 e 7 do livro do Silberschatz. Curiosidade: A inversão de prioridades na Mars Pathfinder

Unidade 03: Memória
Unidade 03: Memória Introdução ao Gerenciamento de Memória Apresentação sobre Gerenciamento de Memória Capítulo 8 do livro do Silberschatz. Memória Principal Apresentação sobre Gerenciamento de Memória Capítulo 8 do livro do Silberschatz. Memória Virtual Apresentação sobre Gerenciamento de Memória Capítulo 9 do livro do Silberschatz.

Unidade 04: Armazenamento

Unidade 04: Armazenamento Interface do Sistema de Arquivos Apresentação sobre Gerenciamento de Arquivos Capítulo 10 do livro do Silberschatz. Implementação do Sistema de Arquivos Apresentação sobre Gerenciamento de Arquivos Capítulo 11 do livro do Silberschatz. Estrutura de Armazenamento em Massa Apresentação sobre Gerenciamento de Arquivos Capítulo 12 do livro do Silberschatz. Gerenciamento de Entrada e Saída Apresentação sobre Gerenciamento de Entrada e Saída Capítulo 13 do livro do Silberschatz.

Laboratórios

Um Exemplo de Uso "API Padrão POSIX"

Um Exemplo de Uso "API Padrão POSIX" Referências Referência http://man7.org/linux/man-pages/man2/mmap.2.html Crie uma função soma que receba 2 ponteiros referenciando posições na memória, criadas utilizando nmap(), de maneira que estas posições armazenem números inteiros. A função soma deverá retornar a soma dos números apontados em regiões da memória sem a utilização de nenhuma rotina da biblioteca do C, que não sejam definidas por APIs posix, para criação destas regiões na memória (malloc, alloc, calloc). Após retornar o resultado da soma os devidos ponteiros deverão ser extintos da memória. Experimento 1: Aumente o tamanho da memória alocada até quando for possível. Qual o tamanho limite da memória que você conseguiu alocar? Experimento 2: Mude o escopo para PROT_NONE, após executar e depurar o código explique o que aconteceu. Em sua opinião NMAP trata-se de uma syscall ou de uma API? Afinal API e syscall são a mesma coisa? Explique. void *mmap(void *addr, size_t length, int prot, int flags, int fd, off_t offset); int munmap(void *addr, size_t length); addr = Valor do início do mapeamento. length = valor do tamanho da região a ser alocada. prot = especificações de proteção da região alocada (consultar http://man7.org/linux/man-pages/man2/mmap.2.html). flags = especificação do escopo e do tipo da região criada (exemplo publica ou privada, se é anônima ou não). void* meu_malloc(size_t tamanho) { void* addr = mmap(0, // addr tamanho, // len PROT_READ | PROT_WRITE, // prot MAP_ANON | MAP_PRIVATE, // flags -1, // filedes 0); // off *(size_t*)addr = tamanho; return addr + sizeof(size_t); } int meu_free(void* addr) { return munmap(addr - sizeof(size_t), (size_t) addr); } int soma(int *N1, int *N2){ return (*N1+*N2); } int main(int argc, char* argv[]) { int* numero1 = meu_malloc(sizeof(int)); int* numero2 = meu_malloc(sizeof(int)); *numero1 = 10; *numero2 = 20; int resultado = soma(numero1, numero2); printf("\n\n O resultado da soma é %d \n\n",resultado); meu_free(numero1); meu_free(numero2); return 0; }

Processos no Linux (Atividade 1)

Processos no Linux Entregar um relatório impresso sobre a sua solução para o problema descrito. O relatório deve conter as seguintes seções: Resumo; Introdução; Conceitos; Problema; Solução (Diagramas e código fonte); Conclusão. 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 pela 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()); 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. Exercício status/wait 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 (Atividade 2)

Threads de aplicação Entregar um relatório impresso sobre a sua solução para o problema descrito. O relatório deve conter as seguintes seções: Resumo; Introdução; Conceitos; Problema; Solução (Diagramas e código fonte); Conclusão. 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); } Exercício 1: Primeiramente compile e execute o código. Agora estude o código e entenda completamente o seu funcionamento. Explique em DETALHES o código, comentando todas as linhas. Na seção de diagrama do seu relatório, desenhe um diagrama de funcionamento do código para mostrar exatamente como acontece a troca de contexto entre as threads. Exercício 2: Acrescente um procedimento f_new que receba 4 strings como parâmetros e imprima todas na tela. Antes do final da execução do main faça uma mudança de contexto para chamar o procedimento criado.

Exercícios sobre pipe e memória compartilhada

PIPE e SH_MEMORY Referências http://man7.org/linux/man-pages/man2/pipe.2.html http://man7.org/linux/man-pages/man2/shmget.2.html http://man7.org/linux/man-pages/man3/ftok.3.html Experimento 1: Complete o código a seguir para implementar um processo que escreva no pipe fd a mensagem de "hello pipe", e envie esta mensagem para outro processo escrever na tela. #include <stdio.h> #include <unistd.h> #include <sys/types.h> #include <string.h> #include <stdlib.h> int main(void) { int fd[2], pipe_ret, filho; char string[] = "Hello, pipe!\n"; char buffer[20]; pipe(fd); if((filho = fork()) == -1) { perror("fork"); exit(1); } if(filho == 0) { /*Mandar string para a extremidade do pipe*/ exit(0); } else { /*Ler a mensagem no pipe*/ printf("Recebi este texto %s", buffer); } return(0); } Experimento 2: Complete o código a seguir para que os processos pai e filho possam compartilhar um segmento de memória. O filho escreve no segmento e o pai imprime na tela o conteúdo da mensagem. #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 int main(int argc, char *argv[]) { key_t key; int shmid; char *segmento; int modo,filho; /* Criar a chave: */ if (key == -1) { perror("ftok"); exit(1); } /*Criar o segmento */ if (shmid == -1) { perror("shmget"); exit(1); } /*Vincula o segmento de memória á variável segmento*/ segmento = shmat(shmid, (void *)0, 0); if (segmento == (char *)(-1)) { perror("shmat"); exit(1); } if((filho = fork()) == -1) { perror("fork"); exit(1); } if(filho == 0) //Código do filho { exit(0); } else //Código do pai { } /* detach from the segment: */ if (shmdt(segmento) == -1) { perror("shmdt"); exit(1); } return 0; }

Trocas de mensagens com pipes (Atividade 3)

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

Exercício (Algoritmo de Patterson)

Exercício (Algoritmo de Peterson) Exercício 1: Sincronize o código a seguir, de maneira que o processo pai imprima apenas os números impares e o processo filho os números pares. Para isso utilize o algoritmo de Peterson visto em aula. Utilize memória compartilhada para comunicação entre os processos. #include <stdio.h> #include <stdlib.h> #include <string.h> #include <sys/types.h> #include <sys/ipc.h> #include <sys/shm.h> main() { if (fork() != 0) { /* I am the parent */ int i; for(i = 0;i < 10;i=i+2){ printf("Processo pai %d \n", i); } } else { /*Child code */ int i; for(i = 1;i < 10;i=i+2){ printf("Processo filho %d \n", i); } } exit(0); } Exercício 2: Considerando o exercício anterior faça a mesma sincronização, no entanto desta vez utilize a modelagem em software do TSL. Em sua experiência, depois de testar diversas vezes as execuções de suas soluções baseadas no algoritmo de Peterson e Tsl, qual sua opinião sobre as abordagens? Explique seu raciocínio.