Sistemas de Computação I - Prova 1
PUC-Rio - 30/04/98

1. Considere o problema dos leitores e escritores, onde existem diversos processos que eventualmente fazem acessos de leitura a uma base de dados e diversos processos que eventualmente fazem acessos de escrita à mesma base. Vários acessos de leitura podem ocorrer simultaneamente, mas um acesso de escrita não pode ocorrer simultaneamente com acessos de nenhum tipo. Considere o código abaixo para os processos de leitura e de escrita. Suponha que todos os semáforos são inicializados com valor 1.

   leitor:                         escritor:
   ...                             ...
   1  while(1) {                   1  while(1) {
   2    P(R);                      2    ...produz
   3    P(M);                      3    P(R);
   4    rc++;                      4    P(W);
   5    if (rc==1) P(W);           5    ESCREVE;
   6    V(M);                      6    V(W);
   7    V(R);                      7    V(R);
   8    LE;                        8  }
   9    P(M);
   10   rc--;
   11   if (rc==0) V(W);
   12   V(M);
   13   ... consome

   1. Essa solução pode levar a starvation de escritores? (pode acontecer de um escritor nunca conseguir o acesso à base devido à seguida chegada de novos leitores?) Explique sua resposta, usando os números das linhas de código para se referir aos passos do programa.
   2. Explique o papel do semáforo M. Dê um exemplo de problema que poderia ocorrer caso as operações sobre ele fossem retiradas.
2. Imagine que uma determinada biblioteca oferece uma primitiva receive(origem, &msg) que permite a um processo especificar que deseja receber uma mensagem do processo identificado por origem. Suponha que esta primitiva bloqueie o processo receptor até que chegue a mensagem do processo requisitado. Suponha ainda que se deseje construir um programa que precise ficar bloqueado até que chegue uma mensagem de qualquer um entre n processos. Esboce a implementação de uma função receive_any, que receba como parâmetro uma lista dos identificadores dos processos origem, e cause bloqueio até que um destes processos envie uma mensagem, retornando então com a mensagem recebida. Para este esboço, utilize a primitiva send descrita, em conjunto com as chamadas fork e pipe do Unix (não é necessário escrever detalhes de código, apenas um esqueleto).
3. O mecanismo de memória virtual requer que o hardware ofereça algum suporte de tradução de endereços.
   1. Em geral, máquinas com este suporte possuem dois modos de execução: um real, onde os endereços vistos pelo processo (virtuais) são iguais aos endereços físicos, e um outro, chamado às vezes de protegido, onde todos os endereços são automaticamente traduzidos através do uso de tabelas de páginas. Por que o primeiro modo de execução é necessário?
   2. Algumas plataformas possuem no hardware de tradução de endereços um bit de referência associado a cada página virtual, que é usado para indicar que houve uma referência à página correspondente.
      1. Para que serve este bit num sistema com paginação por demanda, já que, neste tipo de sistema, uma página só é trazida para a memória se é referenciada?
      2. Se a tabela de páginas não tiver este bit, mas tiver outros bits de proteção, como o bit de referência pode ser simulado em software?
4. Quais são as quatro condições necessárias para a ocorrência de um deadlock, segundo o livro? Para cada uma delas, dê um exemplo de como a condição pode ser negada, evitando deadlocks, ou explique por que não é viável negar a condição.