SOP29005-2019-1

• Professor: Eraldo Silveira e Silva
• Encontros: .
• Atendimento paralelo: .

• Plano de Ensino: ver SIGAA
• Cronograma: ver SIGAA

1 Conteúdo

Unidade 01: Introdução

1.1 Unidade 01: Introdução 1.1.1 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 1.1.2 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

1.2 Unidade 02: Processos 1.2.1 Gerência de tarefas; contextos, processos e threads Apresentação sobre Gerenciamento de Processos Capítulo 3 do livro do Silberschatz 1.2.2 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. 1.2.3 Comunicação entre Processos Apresentação sobre Comunicação entre Processos Capítulo 3 do livro do Silberschatz. 1.2.4 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

1.3 Unidade 03: Memória 1.3.1 Introdução ao Gerenciamento de Memória Apresentação sobre Gerenciamento de Memória Capítulo 8 do livro do Silberschatz. 1.3.2 Memória Principal Apresentação sobre Gerenciamento de Memória Capítulo 8 do livro do Silberschatz. 1.3.3 Memória Virtual Apresentação sobre Gerenciamento de Memória Capítulo 9 do livro do Silberschatz. 1.3.4 Exercícios Exercícios: Introdução. Gerenciamento de Memória 1. Gerenciamento de Memória 2.

Unidade 04: Armazenamento

1.4 Unidade 04: Armazenamento 1.4.1 Interface do Sistema de Arquivos Apresentação sobre Gerenciamento de Arquivos Capítulo 10 do livro do Silberschatz. 1.5 Permissões de sistema de arquivos no Linux Neste 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. 1.5.1 Implementação do Sistema de Arquivos Apresentação sobre Gerenciamento de Arquivos Capítulo 11 do livro do Silberschatz. 1.5.1.1 Exercícios 1. Qual tipo de organização de diretórios que o ubuntu utiliza, grafo cíclico, grafo acíclico, flat ou árvore, comprove seu raciocínio por meio de testes. 2. No ubuntu o que acontece quando deletamos um hard link, e em seguida acessamos o link como um arquivo comum e alteramos seu conteúdo? * É possível tomar tal ação? Se sim Qual o efeito? explique. * Faça o mesmo teste, porém desta vez utilize um soft link. 1.5.2 Estrutura de Armazenamento em Massa Apresentação sobre Gerenciamento de Arquivos Capítulo 12 do livro do Silberschatz. 1.5.3 Gerenciamento de Entrada e Saída Apresentação sobre Gerenciamento de Entrada e Saída Capítulo 13 do livro do Silberschatz. 1.5.4 Exercícios Exercícios Arquivos.

2 Laboratórios

Um Exemplo de Uso "API Padrão POSIX"

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

2.2 Processos no Linux 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

2.3 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

2.4 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); } Trocas de mensagens com pipes 2.5 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. //Solução possível #include <unistd.h> #include <fcntl.h> #include <stdio.h> #include <string.h> #include <stdlib.h> char *message = "This is a message to send!!!" ; main() { int size = strlen(message)+1; char buf[size]; char buf1[size]; char buf2[size]; int status; int fd[2]; pipe(fd); if (fork() != 0) { /* I am the parent */ printf("Processo A PID: %d\n", getpid()); write(fd[1], message, size); wait(&status); } else { /*Child code */ int status1; int fd1[2]; pipe(fd1); if (fork() != 0) { /* I am the parent */ printf("Processo B PID: %d\n", getpid()); read(fd[0], buf, size); write(fd1[1], buf, size); wait(&status1); }else { /*Child code */ int status2; int fd2[2]; pipe(fd2); if (fork() != 0) { /* I am the parent */ printf("Processo C PID: %d\n", getpid()); read(fd1[0], buf1, size); write(fd2[1], buf1, size); wait(&status2); }else { /*Child code */ printf("Processo D PID: %d\n", getpid()); read(fd2[0], buf2, size); printf("\n Mensagem -> %s <- \n ", buf2); } } } exit(0); } 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. Memória Compartilhada Experimento Shared Memory: 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; }

Exercício (Algoritmo de Peterson)

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

Exercício (Semáforos)

2.7 Exercício (Semáforos) 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 Semáforos de acordo com a implementação em semaforo.h. 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); sleep(1); } } else { /*Child code */ int i; for(i = 1;i < 10;i=i+2){ printf("Processo filho %d \n", i); } } exit(0); } SEMAFORO.H #include <sys/sem.h> int criar_semaforo(int val, int chave) { int semid ; union semun { int val; struct semid_ds *buf ; ushort array[1]; } arg_ctl ; key_t ft = ftok("/tmp", chave); semid = semget(ft,1,IPC_CREAT|IPC_EXCL|0666); if (semid == -1) { semid = semget(ft,1,0666); if (semid == -1) { perror("Erro semget()"); exit(1) ; } } arg_ctl.val = val; //valor de início if (semctl(semid,0,SETVAL,arg_ctl) == -1) { perror("Erro inicializacao semaforo"); exit(1); } return(semid) ; } void P(int semid){ struct sembuf *sops = malloc(10*sizeof(int)); sops->sem_num = 0; sops->sem_op = -1; sops->sem_flg = 0; semop(semid, sops, 1); free(sops); } void V(int semid){ struct sembuf *sops = malloc(10*sizeof(int)); sops->sem_num = 0; sops->sem_op = 1; sops->sem_flg = 0; semop(semid, sops, 1); free(sops); } void sem_delete(int semid) { if (semctl(semid,0,IPC_RMID,0) == -1) perror("Erro na destruicao do semaforo"); }

Programação concorrente

2.8 Programação concorrente 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() {} 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 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; 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); cout << "Saldo final é " << saldo << "." << endl; } Compile este programa. Você precisará da classe Thread. Execute este programa várias vezes. Ele funciona? Será que ele gera as saídas esperadas? Identifique as seções críticas do programa. Corrija o programa utilizando mutex. Utilize a classe Mutex implementada na aula passada. 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. Modifique o programa para usar um semáforo binário ao invés de um mutex em sua solução. Utilize a classe Semaphore. 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: Criar N threads, uma para somar os valores de cada linha. Receber o resultado do somatório de cada linha e gerar o somatório total da matriz. 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; }

Lista de exercícios "Revisão para Prova"
2.9 Lista de exercícios/Revisão para Prova A lista de exercícios referente a primeira prova (Parte introdutória + Processos) segue neste LINK | Lista de exercícios.

Primeiro trabalho

2.10 JOGO DA VIDA DE CONWAY e JANTAR DOS FILÓSOFOS Referências MPI Tipos de dados MPI Jogo da Vida A partir da implementação sequencial do Game of Life apresentada a seguir, estude o código e transforme esta implementação em uma implementação paralela utilizando o protocolo de passagem de mensagens MPI. Perceba que a impĺementação mencionada utiliza como parâmetros de entrada um aquivo contendo o estado inicial do jogo, e o número de gerações que o usuário deseja rodar. A evolução do estado inicial é impressa na tela passo a passo. Sendo assim, a partir disso: 1: Elabore uma implementação com 2 processos para o jogo da vida utilizando o protocolo MPI, de maneira que um processo execute uma geração i qualquer e o outro execute a geração seguinte i+1 2: (0,7) Os processos deverão se comunicar utilizando as funções do protocolo MPI. 3: (0,3) Relatório simplificado explicando a sua solução. Utilize diagramas para representar a comunicação entre os processos, explicando como a matriz do jogo é transferida entre os processos. 4: Entregue o Relatório e o código fonte do trabalho em um pacote compactado via e-mail (PRAZO 19/10). Compilar o código com MPI mpicc -o nomeApp arquivo.c </syntaxhighlight> Rodar rodar programa utilizando MPI mpirun -np numeroDeProcessos ./nomeApp entrada.txt gerações </syntaxhighlight> * (int) -np: Quantidade de processos que você deseja executar * entrada.txt: Arquivo de entrada com estado inicial do jogo * (int) gerações: número de gerações que você deseja rodar * Arquivo de entrada para Testes /* Conway's Game of Life Compilar código com MPI mpicc -o nomeApp arquivo.c Rodar rodar programa utilizando MPI mpirun -np numeroDeProcessos ./nomeApp entrada.txt gerações (int) -np: Quantidade de processos que você deseja executar entrada.txt: Arquivo de entrada com estado inicial do jogo (int) gerações: número de gerações que você deseja rodar */ #include <stdio.h> #include <string.h> #include <stdlib.h> #include "mpi.h" //Numero de linhas e colunas #define nLinhas 32 #define nColunas 82 char *matriz[nLinhas]; char *entrada[nLinhas]; void iniciar() { int i; //Alocar espaço em memória para as matrizes for (i = 0; i < nLinhas; i++ ) matriz[i] = (char *) malloc((nColunas) * sizeof( char )); } int adjacente(char **matriz, int i, int j){ int x,y, initX, initY, limitX, limitY; int vizinhos = 0; if(i == 0) initX = 0; else initX = -1; if(i == (nLinhas-1)) limitX = 1; else limitX = 2; if(y == 0) initY = 0; else initY = -1; if(y == (nColunas-3)) limitY = 1; else limitY = 2; for(x = initX ; x < limitX; x++){ for(y = initY; y < limitY; y++){ if(matriz[i+x][j+y] == '#') vizinhos++; } } if(matriz[i][j] == '#') return (vizinhos-1); else return vizinhos; } void calculoGeracao(char **matriz, int ger) { int i, j, a; char novaGeracao[nLinhas][nColunas]; /* Aplicando as regras do jogo da vida */ for (i=0; i < nLinhas; i++){ for (j=0; j < nColunas; j++) { a = adjacente(matriz, i, j); if (a == 2) novaGeracao[i][j] = matriz[i][j]; if (a == 3) novaGeracao[i][j] = '#'; if (a < 2) novaGeracao[i][j] = ' '; if (a > 3) novaGeracao[i][j] = ' '; if (j == 0) novaGeracao[i][j] = '"'; } novaGeracao[i][79] = '"'; novaGeracao[i][80] = '\n'; } /* Passando o resultado da nova geração para a matriz de entrada */ for (i=0; i < nLinhas; i++){ for (j=0; j < nColunas; j++) matriz[i][j] = novaGeracao[i][j]; } } main(int argc, char *argv[2]){ /* Para uso com MPI //Variáveis para uso com MPI int numeroDeProcessos = 0; int rank = 0; MPI_Status status; //Iniciar MPI--- MPI_Init( &argc, &argv ); //Atribui a variável numeroDeProcessos o número de processos passado como parâmetro em -np MPI_Comm_size( MPI_COMM_WORLD, &numeroDeProcessos ); //Pega o valor do rank (processo) MPI_Comm_rank( MPI_COMM_WORLD, &rank ); */ FILE *matrizEntrada; matrizEntrada = fopen(argv[1], "r"); iniciar(); if (matrizEntrada == NULL) printf ("Não posso abrir o arquivo \"%s\"\n", argv[1]); char str[nColunas]; int linha = 0; //Lendo o estado inicial do jogo a partir do arquivo while((fgets(str, nColunas, matrizEntrada) != NULL)&&(linha < nLinhas)){ strcat(matriz[linha], str); linha++; } int i,gens; for(gens = 0; gens < atoi(argv[2]); gens++){ //Gens é o número de gerações especificado no segundo parâmetro calculoGeracao(matriz, gens); printf("%c[2J",27); // Esta linha serve para limpar a tela antes de imprimir o resultado de uma geração //Lendo o estado do jogo e imprime na tela for(i = 0; i < nLinhas; i++) printf("%s", matriz[i]); sleep(1); } for(i = 0; i < nLinhas; i++) free(matriz[i]); /* Finaliza o MPI */ //MPI_Finalize(); exit(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 (0,7) 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. Re-insira as operações no código e analise a solução. Esta modificação é suficiente para garantir que não haverá deadlock? Se sim, mostre o porque. Se não, proponha uma solução completa. (0,3) Relatório simplificado explicando a sua solução. Entregue o Relatório e o código fonte do trabalho em um pacote compactado via e-mail (PRAZO 19/10). #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; }

Softwares básicos, caso Hello Word! (Trabalho 2) Entrega dia 09/11

2.11 Softwares básicos, caso Hello Word! O objetivo do experimento de hoje é pesquisar e entender os processos de atribuição de endereços de programas realizados em tempo de compilação pelos softwares básicos como: compilador, linker, e assembler. Sendo assim, neste experimento vamos utilizar os seguintes softwares para criação e análise de código: GCC: compilador para gerar código objeto a partir de um código de programa escrito na linguagem c; GNU Linker (LD): Para vincular os códigos (módulos) objetos do programa; Linker GNU Assembler: Para gerar o código executável a partir do código objeto; | assembler OBJDUMP: Para mostrar informações do código; | Objdump A seguir segue descrito o programa a ser utilizado no exercício 1: #include <stdio.h> int main() { printf("Hello, World!"); return 0; } Trata-se do programa hello word, este programa apenas exibe uma mensagem na tela. No entanto, vamos analisar como são as etapas confecção do executável a partir deste código simples. Exercício 1: Compile o programa hello word, e o transforme em código objeto utilizando o programa GCC. Para esta tarefa execute o seguinte comando: gcc -o hello hello.c </syntaxhighlight> Agora abra o código objeto utilizando o programa OBJDUMP. objdump -D hello </syntaxhighlight> Identifique quais são as seções de código obtidas a partir do hello.c. Pesquise e entenda o significado das seções de código: .bss, .txt, .data, .init. Faça uma análise e identifique o endereço de memória que o programa hello world vai ser carregado. Este código objeto é relocável? Justifique sua resposta. Agora gere o código assembly do hello world. gcc -S hello.c </syntaxhighlight> Agora gere o código executável utilizando o programa AS e o programa LD. as -o hello.o hello.s </syntaxhighlight> Como a etapa de linkagem para a construção do código executável está sendo executada sem o auxílio do GCC, necessitamos vincular manualmente as bibliotecas necessárias. Para criar apropriadamente o executável vamos precisar das bibliotecas ld-linux-x86-64.so.2, crt1.o, crti.o, crtn.o. Para descobrir suas respectivas localizações use o comando LOCATE. Por exemplo: locate crti.o </syntaxhighlight> ou find /usr/ -name crti* </syntaxhighlight> Agora que já sabemos a localização das bibliotecas necessárias vamos vincular essas a nossa aplicação. ld --dynamic-linker /caminho/ld-linux-x86-64.so.2 /caminho/crt1.o /caminho/crti.o /caminho/crtn.o hello.o -lc -o hello.exe </syntaxhighlight> Agora abra o código objeto utilizando o programa OBJDUMP. Faça uma análise e identifique o endereço de memória em que o programa hello world inicializa suas estruturas na memória. Dica! objdump -D -s -j .init hello.exe </syntaxhighlight> Houve diferença entre os endereços do programa executável em relação ao código objeto? Explique. Explique as principais diferenças entre o arquivo objeto .o e o executável final. (dica utilize o objdump para fazer essa análise)