Fundamentos de Sistemas Operacionais - 2021-2
UnB-\(\gamma\)

1.1.1. Tópicos

1.1.2. Material de apoio

1.2.1. Vídeo Complementar

1.2.2. Exercícios

1. Questões para pesquisar no livro texto
   
   1. Enumere e explique resumidamente as principais responsabilidades de um sistema operacional.
   2. Qual é a diferença entre modo usuário e modo kernel? Por que esta distinção é feita?
   3. Descreva como são implementados os seguintes eventos:
      • chamada de sistema,
      • tratamento de interrupção, e
      • tratamento de sinais.
      • Quais são as semelhanças e diferenças entre estes eventos?
   4. Qual é a diferença entre um sistema monolítico e um baseado em camadas?
2. Sobre Processos
   
   1. Abra um terminal e execute o comando: pstree -c -p. Descreva o que está vendo (dica: veja o vídeo complementar)

1.3.1. Parte Assíncrona

1.3.2. Vídeo complementar e seus cortes

1.3.3. Tópicos e materiais

1.3.4. Exercícios

1. Sobre Processos
   
   1. Familiarize-se com a chamada: fork(2), wait(2), execl(3);
   2. Descreva o funcionamento das funções listadas acima.
2. Na figura 1 são mostrados três estados de processos. Na teoria, com três estados poderia haver seis transições, duas para cada estado. Contudo, somente quatro transições são mostradas. Há alguma circunstância na qual uma delas ou ambas as transições não ilustradam possam ocorrer?
   
3. O que é um processo Zumbi? Explique como que um processo passe para o estado de Zumbi.
   
4. Escreva um programa que gere um processo Zumbi.
   
5. Considere a seguinte parte de um programa:   prof_Orlando
   

   ...
     p=fork();
     a=fork();
   
   printf("Sistemas Operacionais\n");
   ...
   

   • Quantas vezes é apresentada "Sistemas Operacionais"? Justifique.
   • Quantos processos são criados pelo programa?
6. Faça um programa que crie 2 processos e:   prof_Orlando
   
   • Escreve Eu sou o pai no processo pai;
   • Escreve Eu sou o 1o filho no primeiro filho;
   • Escreve Eu sou o 2o filho no segundo filho.
7. Considere o seguinte pedaço de código em C:   prof_Orlando
   

   1: for(i=0;i<4;i++)
   2:   pid=fork();
   3: printf("FSO\n");
   

   1. Quantos processos são criados por este programa? Justifique.
   2. Quantas vezes é apresentado "FSO"? Justifique.

1.4.1. Material Adicional

1.4.2. Exercícios

1. O que é um processo Zumbi? Escreva um programa que crie processos zumbis.
   
2. Resolva http://www.brunoribas.com.br/so/2019-1/pratica/multiplicacao-matriz.html
   
3. Resolva http://wiki.inf.ufpr.br/maziero/doku.php?id=so:criacao_de_processos
   
4. Resolva http://www.dei.isep.ipp.pt/~orlando/so2/processos.htm
   
5. Familiarize-se com as chamadas: execve(2), clone(2)
   
6. Considere a seguinte parte de um programa   prof_Orlando
   

   int main()
   {
     ...
     pid2=0;
     for(i=0;i<2;i++)
     {
       pid=fork();
       if(pid==0)
         pid2=fork();
       if(pid2==0)
         printf("Exame de SO\n");
     }
     ...
   }
   

   • Quantas vezes é apresentada a frase Exame de SO? Justifique

   • Veja a discussão deste problema no vídeo abaixo:

7. Tendo um vetor de inteiros com mil posições, crie um processo e faça o seguinte:   prof_Orlando HOT
   
   • Os dois processos (pai e filho) fazem o seguinte cálculo: resultado[i]=dados[i]*4+20
   • Cada processo é responsável pelo cálculo de \(500\) posições do vetor dados, colocando o resultado no vetor resultado
   • Os resultados devem ser apresentados seguindo a ordem do vetor (de \([0,499]\) e depois \([500,999]\))
8. Faça um programa que crie 6 processos e:   prof_Orlando HOT
   
   • Cada processo escreve \(200\) números:
     • 1o processo \([0,200]\);
     • 2o processo \([201,400]\);
     • 3o processo \([401,600]\);
     • 4o processo \([601,800]\);
     • 5o processo \([801,1000]\);
     • 6o processo \([1001,1200]\);
   • O processo pai tem de esperar que TODOS os processos filho terminem
9. Tendo um vetor de \(1000\) posições, faça um programa que crie 5 processos e:   prof_Orlando HOT
   

1.5.1. Cortes de Aula com exercícios resolvidos

1.6.1. Material Adicional

1.6.2. Exercícios

1.8.1. Threads

1.8.2. Abordagem prática de threads

1.8.3. Exercícios

1. Considere que tem definido na função main duas strings em que a primeira tem o seu primeiro nome e a segunda o último. Faça uma função que receba como parâmetros uma string e escreva essa string no monitor. Implemente um programa em que cada string é apresentada por um thread diferente.   prof_Orlando
   
2. Considere que tem um array com cinco posições, sendo cada posição constituída pelo número, nome e morada. Faça uma função que recebe como parâmetros uma estrutura desse tipo e imprima o conteúdo dessa estrutura. Implemente um programa que crie 5 threads, "passando" como argumentos uma estrutura desse array (Ex: 0 primeiro thread fica com a primeira posição do array, etc.)   prof_Orlando
   
3. Tendo um array de inteiros com 1200 posições, pretende-se calcular resultado[i] = dados[i]*4 + 20. Crie duas threads :   prof_Orlando
   
   • o primeiro thread calcula as primeiras 400 posições;
   • o segundo as seguintes 400;
   • o resto é calculado na função main
     • Depois dos cálculos terminarem, devem ser apresentados os valores no monitor (pode ser feito na função main).
4. Dado um array de inteiros com mil posições, crie 5 threads:   prof_Orlando
   
   • Dado um número, procurar esse número no array.
   • Cada thread, procura 200 posições.
   • O thread que encontrar o número, deve imprimir a posição do array onde se encontra. Também deve "retornar" como valor de saída o número do thread (1, 2, 3, 4, 5).
   • Os threads que não encontrarem o número devem "retornar" como valor de saída o valor 0.
   • A função main tem de esperar que todos os threads terminem e imprimir o número do thread onde esse número foi encontrado (1, 2, 3, 4, 5).
     • Nota: O array não tem números repetidos.
5. Faça um programa que crie 5 threads. Cada thread é responsável por calcular 200 posições do array resultado (resultado[i] = dados[i]*2+10). Os threads devem imprimir os resultados segundo a ordem do array.   prof_Orlando
   

1.9.1. Material complementar

1.9.2. Exercícios

1. Leia o panorama geral de semáforos no linux sem_overview(7)
   
   • Execute o comando man 7 sem_overview
2. Familiarize-se com as funções:
   
   • sem_init(3)
   • sem_wait(3)
   • sem_post(3)
   • sem_destroy(3)
   • sem_getvalue(3)
3. Exercício sobre semáforo   prof_WagnerZola
   

   • Faça duas funções em linguagem C, que possam ser usadas por THREADS COOPERANTES. A função get_ticket() retorna um número inteiro positivo ÚNICO a qualquer thread que chamá-la. Protótipo:

     int get_ticket();
     

     A função return_ticket(int) deve receber "de volta" um ticket (número inteiro), supostamente obtido anteriormente via get_ticket(), de modo que esse ticket possa ser "reutilizado" por get_tickets subsequentes.

     void return_ticket(int t);
     

   • Mostre (explique) brevemente porque sua get_ticket() retorna inteiros ÚNICOS, i.e., nunca retorna valores repetidos.

     OBS: Caso seja necessário, sua get_ticket() pode ter um número máximo de tickets (NMAX), nesse caso, ele deve retornar \(-1\) para indicar que não pode mais retornar valores novos.

     Veja o vídeo abaixo, para ver a discussão do exercício. Mas assista somente após de tentar resolver o exercício.

4. Tente implementar o exercício de multiplicação de matrizes com Threads, conforme descrito em AQUI (há um exemplo de solução)
   
   • Experimente com 2,4 e 8 threads.

1.14.1. Introdução assíncrona ao Gerenciamento de Memória

1.14.2. Vídeos sobre memória

1.17.1. Vídeos

1.17.2. Exercícios

1. Considere um sistema cuja gerência de memória é feita através de partições variáveis.
   
   • Nesse momento, existem as seguintes lacunas (áreas livres): 10K, 4K, 20K,18K, 7K, 9K, 12K e 13K, nessa ordem.
   • Quais espaços serão ocupados pelas solicitações: 4K, 10K e 6K, nessa ordem, se:
     • first-fit for utilizado?
     • best-fit for utilizado?
     • worst-fit for utilizado?
2. Calcule o número de bits para página, quadro e deslocamento.
   
   • Memória lógica = 512K, Memória física = 512K, Tamanho de página = 8K
   • Tamanho de página = 4K, número de páginas = 8, número de quadros = 16
3. O que é paginação?
   
4. Qua é a diferença entre paginação e segmentação?
   
5. Considere que os processos da tabela abaixo devem ser executados em um SO com paginação.
   
   • A memória total é de 64K, o tamanho das páginas é de 4K e o SO ocupa 8K. Mostre como seria a alocação de quadros para cada processo.

   Processo	Mem. (K)	T. Chegada	T. Execução
   P1	8	0	10
   P2	6	1	15
   P3	15	2	10
   P4	5	3	14
   P5	10	15	5

6. Qual a diferença entre fragmentação interna e externa da memória principal?
   
7. Qual a principal diferença entre os sistemas que implementam paginação e segmentação?
   
8. Para que serve o bit de validade nas tabelas de páginas e segmentos?
   
9. Nos sistemas com paginação, a rotina para tratamento de page faults está residente na memória principal
   
   • Esta rotina pode ser removida da memória em algum momento?
   • O que aconteceria se esta rotina não estivesse na memória principal durante a ocorrência de um page fault?
10. Descreva como ocorre a fragmentação interna em um sistema que implementa paginação
    
11. Na figura abaixo está representada um esquema de paginação que utiliza 4 bits para índice da página e 12 bits para deslocamento.   prof_Islene
    

    

    • Considerando esta tabela, indique para cada endereço virtual o endereço físico correspondente ou escreva page fault
      • 0010 0000 0000 0111
      • 0011 0000 1010 0000
      • 0100 0000 0000 0101
      • 1111 1111 1111 1111
      • 0000 0000 0000 0000
12. Seria possível e/ou viável implementar as conversões de endereços realizados pelas MMU em software, ao invés de usar um hardware dedicado? Por quê?
    
13. O que é memória virtual?
    
14. Quais das seguintes técnicas e estruturas de programação são "boas" para um ambiente de paginação por demanda? Quais delas são "más"? Explique suas respostas.
    
    • pilha
    • Busca Sequencial
    • Busca Binária
    • Operações em vetor
    • Simulação
15. Considere os seguintes algoritmos de substituição de páginas. Classifique estes algoritmos em uma escala de cinco pontos do "ruim" ao "perfeito" de acordo com a sua taxa de erros de página. Separe os algoritmos afetados pela anomalia de Belady daqueles que não o são.
    
    • Substituição LRU
    • Substituição FIFO
    • Substituição Ótima
    • Substituição da segunda chance
16. Considere a seguinte sequência de referências de páginas:
    

    1,2,3,4,2,1,5,6,2,1,2,3,7,6,3,2,1,2,3,6

    • Quantos erros de pághinas iriam ocorrer para os seguintes algoritmos de substituição , considerando um, dois, três, quatro, cinco, seis ou sete quadros? Lembre-se de que todos os quadros estão inicialmente vazios, de modo que a primeira página de cada um implicará em um erro de página.
      • Substituição LRU
      • Substituição Ótima
      • Substituição do Relógio
      • Substituição WSClock
17. Você consegue imaginar alguma situação em que dar suporte à memória virtual seria uma má ideia e o que se ganha quando não é necessário o suporte a memória virtual? Explique
    
18. Exercícios do capítulo 3 do Tanembaum
    
19. Qual é a diferença entre paginação e segmentação? Qual a principal diferença entre os sistemas que implementam paginação e segmentação? Por quê alguns sistemas implementam Segmentação com Paginação?
    
20. Observe o programa abaixo:
    

     4: #define PAGESIZE 4096
     5: #define N 500000
     6: char mat[N][PAGESIZE];
     7: void funcao_A(char c) {
     8:   int i, j;
     9:   for (i = 0; i < N; i++)
    10:     for (j = 0; j < PAGESIZE; j++)
    11:       mat[i][j] = c;
    12: }
    13: void funcao_B(char c) {
    14:   int i,j;
    15:   for (j = 0; j < PAGESIZE; j++)
    16:     for (i = 0; i < N; i++)
    17:       mat[i][j] = c;
    18: }
    19: int main() {
    20:   funcao_A('*');
    21:   funcao_B('-');
    22:   return 0;
    23: }
    

    Considere que o seu sistema utiliza paginação e que o endereço mat[i][j] é calculado da seguinte forma: mat[i][j] = mat + (i*PAGESIZE+j)*sizeof(char)

    • Qual função (funcao_A ou funcao_B) irá, provavelmente, ser executada mais rápido?
    • Descreva duas razões relacionadas ao gerenciamento de memória que justificam a sua resposta acima.

1.21.1. Vídeos Adicionais

1.21.2. Material de apoio

1.21.3. Exercícios

1. A alocação contígua de arquivos leva a uma fragmentação do disco, explique como essa fragmentação ocorre
   
   • Essa fragmentação é interna ou externa?
   • Faça uma analogia com a gerência de memória
2. É possível criar um link simbólico para um arquivo que não existe? E um hard link? Justifique a sua resposta
   
3. Por que razão o sistema UNIX não permite hard links de diretórios?
   
4. A respeito das imagens abaixo
   

   

   Figure 2: Lista Ligada

   

   Figure 3: FAT

   

   Figure 4: INODE

   • A figura 2 apresenta dois arquivos armazenados na forma de uma lista ligada de blocos em disco. A figura 3 apresenta estes mesmos arquivos em uma tabela de alocação em memória (tipo FAT - File Allocation Table). A figura 4 é um exemplo de i-node.
     • Compare e explique as vantagens e desvantagens de se utilizar o armazenamento dos arquivos por lista ligada e por tabela de alocação de memória.
     • Comente vantagens da utilização de i-nodes, como o representado na figura, sobre o uso das tabelas em memória
     • Para arquivos menores que um bloco (ou um i-node) qual é o desperdício no disco? Como o EXT4 minimiza esse impacto?
5. O início de um mapa de bits do espaço livre parece-se com isto depois que a partição de disco é formatada pela primeira vez: 1000 0000 0000 0000 (o primeiro bloco é utilizado pelo diretório raiz). O sistema sempre busca blocos livres a partir do bloco com o menor número; assim, depois de escrever um arquivo A, que usa seis blocos, o mapa de bits se parece com isto: 1111 1110 0000 0000. Mostre o mapa de bits depois de cada uma das seguintes ações adicionais
   
   • O arquivo B é escrito, usando cinco blocos
   • O arquivo A é removido
   • O arquivo C é escrito, usando oito blocos
   • O aquivo B é removido
6. O que aconteceria se o mapa de bits, ou lista de blocos livres contendo a informação sobre blocos de disco livres tivessem sido completamente perdidos em decorrência de um desastre? Há algum modo de recuperar o disco desse desastre ou adeus, disco? Discuta sua resposta, separadamente, para os sistemas de arquivos UNIX e para o FAT-12.
   
7. Um certo sistema de arquivos usa blocos de disco de 2KB. O tamanho mediano do arquivo é de 1KB, qual a fração de espaço em disco que será desperdiçada? Você acha que o desperdício para um sistema de arquivos real será mai alto ou mais baixo que esse? Explique.
   

1.22.1. Manipulando arquivos Binários

2.1.1. Revisão de Ponteiros

2.1.2. Strings em C

2.1.3. SCANF

3.4.1. Presença

3.4.2. Menção Final

3.4.3. Critérios de aprovação