Sistemas Operacionais
Prova 2 de 2010/2

1. a) Faça um escalonamento RR com quantum igual a 3 do seguinte esquema de
      processos.

      Processo   Tempo de Rajada     Tempo de Chegada
      A          8                   0
      B          3                   2
      C          9                   4
      D          2                   7

      0   3   6   9  12 14 16  19  22
      +---+---+---+---+--+--+---+---+
        A   B   A   C   D  A  C   C

      Estados das filas:

      [0]  A(8)
      [2]  B(3)
      [3]  B(3) A(5)
      [4]  A(5) C(9)
      [6]  A(5) C(9)
      [7]  C(9) D(2)
      [9]  D(2) A(2)
      [12] D(2) A(2) C(6)
      [14] A(2) C(6)
      [16] C(6)
      [19] C(3)
      [22] --

   b) Qual o tempo de espera para cada processo?

      A = (6 - 3) + (14 - 9) = 8
      B = (3 - 2) = 1
      C = (9 - 4) + (16 - 12) = 9
      D = (12 - 7) = 5

   c) Qual o tempo de espera médio?

      (T_A + T_B + T_C + T_C) / 4 =
      (8 + 1 + 9 + 5) / 4 = 5.7


2. a) Suponha um sistema operacional interativo, a ser usado tipicamente por
      vários usuários simultaneamente. Qual seria o critério mais importante
      para escalonamento nesse caso?
      
      Tempo de resposta.

   b) Que algoritmo de esclonamento seria mais adequadro para o sistema?

      Round Robin (RR).

   c) Por que este algoritmo é mais adequado?

      Quando possui um quantum baixo para execução dos processos. Em RR temos a
      garantia de que cada processos irá esperar no máximo (n - 1) * quantum
      unidades de tempo.

      Se este valor for muito baixo, chega-se próximo ao efeito de um
      processador com 1/n capacidade do processador original para n processos.

4. Codifique uma pilha e as operações "push" e "pop", assim como uma operação
   de inicialização "init" controlada por monitores.

    #define MAX 4096

    // Estrutura de dados com as posições `p[]`, uma métrica de limite dada por
    // `topo` e as condições `cheia` e `vazia`.

    monitor pilha {
        int p[MAX];
        int topo;
        condition cheia, vazia;
    }

    void push (int x) {

        // Se a pilha estiver cheia, espera esvaziar

        if (topo == MAX)
            cheia.wait();

        // Coloca o elemento na pilha

        topo++;
        p[topo] = x;

        // Se a pilha estava vazia, informa os processos que estão
        // esperando para remover um elemento dela.

        if (topo == 1)
            vazia.signal();
    }

    int pop () {
        int x;

        // Se a pilha estiver vazia, espera alguém adicionar algum elemento
        // nela para então realizar o `pop`.

        if (topo == 0)
            vazia.wait();

        // Retira o conteúdo do topo da pilha

        x = p[topo];
        topo--;

        // Se a pilha deixa de ficar cheia, informa os processos que estão
        // esperando para acessá-la.

        if (topo == (MAX - 1))
            cheia.signal();

        return x;
    }

    // Inicia uma pilha preenchendo todas as suas posições com valores 0
    // e setando o `topo` também para 0.

    void init () {
        topo = 0;
        int i;
        for (i = 0; i < MAX; i++)
            p[i] = 0;
    }