Lista de Exercícios

Sistemas Operacionais - 98.1

1. Suponha que, em um sistema com memória virtual paginada, o número de instruções executadas entre page faults seja diretamente proporcional ao número de molduras alocadas ao programa. Suponha que uma instrução normal demora 1 microsegundo para ser executada, enquanto 1 instrução com page fault demora 2000 microsegundos. Se um programa leva 60 segundos para ser executado, e durante este tempo ocorrem 15000 page faults, quanto tempo demoraria sua execução se o dobro de memória estivesse disponível? (Suponha que uma instrução causa 1 ou 0 page faults.)
2. Qual a diferença entre um processo bloqueado e um processo em espera ocupada?
3. Explique o que é deadlock e o que é starvation.
4. Explique o que é um escalonador preemptivo.
5. Abaixo são apresentadas três soluções para o problema dos macacos.
   1. Nas duas primeiras:
      1. Faça uma análise explicando se a solução permite que os macacos atravessem o precipício sem ocorrência de deadlock.
      2. Caso a resposta no item anterior seja afirmativa, discuta as desvantagens apresentadas pela solução.
   2. A terceira solução pode seguramente levar a situações de deadlock. Descreva uma sequência de acontecimentos que faria isto ocorrer, explicando o comportamento do programa neste caso.
      • primeira solução:

        #define FALSE 0
        #define TRUE 1
        sem mutex = 1;
        int cruzandoOeste = FALSE; int cruzandoLeste = FALSE;
        
        CruzaOeste()                    CruzaLeste()
        {                               /* simetrico a CruzaOeste() */
          int consegui = FALSE;
          repeat
            P(mutex)
            if (!cruzandoLeste){
              cruzandoOeste = TRUE;
              consegui = TRUE;
            }
            V(mutex);
          until (consegui);
          Cruza();
          P(mutex);
          cruzandoOeste = FALSE;
          V(mutex);
        }
        

      • segunda solução:

          sem oeste = 0; sem leste = 1;
        
          CruzaOeste()         CruzaLeste()
          {                    {
            P(oeste);            P(leste)
            Cruza();             Cruza();
            V(leste);            V(oeste);
          }                    }
        

      • terceira solução:

          int cruzandoLeste = 0; int queremLeste = 0;
          int cruzandoOeste = 0; int queremOeste = 0;
          sem oeste = 0; sem leste = 0; sem mutex = 1;
        
          CruzaOeste() {                   CruzaLeste() {
                                             
            P(mutex);                      /* simétrico a CruzaOeste() */
            cruzandoOeste++;
            if (!cruzandoLeste)
              V(oeste);
            else
              queremOeste++;
            V(mutex);
            P(oeste);
        
            Cruza();
         
            P(mutex);
            cruzandoOeste--;
            if (!cruzandoOeste && queremLeste) {
              queremLeste--; 
              V(leste);
            }
            V(mutex);
          }
        

   3. O que é o mecanismo de swapping?
   4. O que é o "escalonamento em dois níveis" que é usado em sistemas com swapping?
   5. Em todo sistema com memória virtual, alguma política de substituição de páginas tem que ser adotada.
      1. Qual a influência que a escolha desta política tem sobre o funcionamento do sistema?
      2. Por que a política LRU exata é difícil de implementar sem suporte de hardware? (pense no que teria que ser feito para implementá-la por software)
   6. 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.
   7. Faça os exercícios 3.13, 3.16, 3.11, 4.3, 4.7, 4.10, 4.15, 4.22.
   Last update: Wed Apr 29 17:17:42 EST 1998 by Noemi