Sistemas de Computação 1 - Prova Final
PUC-Rio - 11/07/95

1. Em sistemas com memória virtual, pode ocorrer um fenômeno denominado thrashing, onde um processo sofre page faults com intervalos de poucas instruções. Por que ocorre este fenômeno e o que se pode fazer para evitá-lo?
2. Suponha um disco com blocos de 512 bits. Seja F o número de blocos livres e B o número total de blocos no disco. Se cada endereço de bloco ocupa 16 bits, qual a condição necessária para que a lista de blocos ocupe menos blocos do que o mapa de bits? Expresse sua resposta em termos da relação F/D. (Na lista de blocos livres, os próprios blocos livres são usados para armazenar informação de localização de blocos livres. Cada bloco na lista armazena uma seqüência de endereços de blocos. O último destes endereços indica o próximo bloco ``livre'' contendo endereços de blocos livres. No mapa de bits existe um bit por bloco no disco. O valor de cada bit indica se o bloco correspondente está livre ou ocupado)
3. Explique a diferença entre deadlock e starvation. Utilize um problema específico, como o dos filósofos, para exemplificar cada uma das situações.
4. Suponha os seguintes trechos de código, onde c e s são arrays de semáforos:

   codigo de cada processo i,      codigo de proc. coordenador:
   entre n processos:              ...
     ...                           for (i=0;i < n;i++) s[i]=0; 
     c[i] = 0;                     while (...) { 
     while (...){                    for (i=0;i < n;i++) P(c[i]);
       /* etapa de trabalho */       for (i=0;i < n;i++) V(s[i]);
       V(c[i]);                    }
       P(s[i]);                    ...
     }
     ...

   1. Qual o papel dos semáforos c e s nestes trechos?
   2. Como a estrutura acima poderia ser implementada usando pipes e processos do UNIX (onde não há semáforos)? Descreva os processos, forks, e pipes que teriam que ser usados, utilizando um diagrama se possível.