Solução P1 - Sistemas I - 98.1

(soluções dadas por alunos)

1. Esta solução não leva a starvation de escritores. Esta solução leva em conta a ordem em que processos (escritores ou leitores) chegam à base de dados. Digamos que um processo leitor primeiramente chegou, passando pela linha 2 e 3 do programa. Se o próximo processo a chegar for escritor ele ficará bloqueado na linha 3. Quando o processo leitor passar pela linha 7, o processo escritor (que chegou logo em seguida do primeiro processo) ficará bloqueado na linha 4, não efetuando, ainda, a escrita. Se neste meio tempo chegar um outro leitor, o processo escritor, como chegou antes, terá a preferênciam e este novo leitor fica bloqueado na linha 2.
  Após a passagem do primeiro processo leitor pela linha 11 o processo escritor efetuará sua escrita e liberará a base de dados para o próximo processo (leitor ou escritor - no meu exemplo é leitor!) passar pela linha 2 (caso leitor) ou 3 (caso novo escritor).
2. O semáforo M garante que somente um processo estará alterando e verificando a variável rc ao mesmo tempo. Se não tivéssemos M, imagine só se tivéssemos um processo leitor e ele fosse interrompido depois de executar rc-- e fazer o valor de rc ser 0. Nisso entra um outro leitor e faz rc++. O valor de rc agora seria 1. Ele testa (rc==1( e faz P(W) pois não foi feito V(W) pelo outro processo leitor. Volta então o processo anterior, testa (rc==0) o que não é verdade logo ele não executa V(W). Temos então W=0, R=0, um processo bloqueado em P(W) e qualquer outro processo que entrasse ficaria bloqueado também em P(R).

  receive_any (lista pids) {
    cria um pipe pipe
    para cada pid de lista de pids {
      if ((ret = fork()) != 0) {
        receive (pid, &msg); //processo filho
        write(pipe, &msg);
        exit();
      }
    }
    read(pipe, &msg); // fica bloqueado enquanto
                      // nao tiver mensagem no pipe
    mata todos os processos filho
    return msg;
  }

1. Em primeiro lugar, este modo de execução é necessário em qualquer máquina em que se deseje "backward compatibility". Ou seja, quando é decidido que numa máquina moderna (em que o "modo protegido" é largamente utilizado) deve ser possível executar códigos antigos que pressupõem um modo real de endereçamento. Um claro exemplo desse caso são as máquinas Intel, onde os modelos atuais buscam manter a compatibilidade com os antigos 8088/8086.
  Entretanto, existe um motivo mais fundamental para possibilitar o modo real. Em certas situações, é estrititamente necessário ao sistema operacional acessar um endereço físico da máquina. Uma dessas situações se refere ao momento em que o sistema copia dados para uma determinada page frame (numa troca de páginas). Nesta situação, ele precisa endereçar a memória em modo real.
2. O bit em questão ainda pode ser usado como referência em diversos algoritmos de seleção de páginas para remoção (e.g.: "second chance", NRU). Como nesses algoritmos os bits de referência são resetados a cada dado intervalo de tempo, não faz diferença (para seu uso) se a paginação é feita por demanda ou não.
3. Basta que o sistema, ao invés de limpar o bit de referência (que afinal de contas não existe), limpe os bits de proteção (armazenando seus valores reais em memória). Quando se tentar referenciar uma destas páginas, uma trap será ativada devido ao erro de proteção cometido. Neste momento, o sistema sabe que a página foi referenciada (armazenando este fato em memória) e pode recolocar os bits de permissão da página em questão de volta em seu lugar e repetir o pedido que incorreu em erro.
As quatro condições necessárias para a ocorrência de um deadlock são:
1. exclusão mútua
2. hold & wait
3. espera circular
4. não preempção
obs: A variação de respostas aceitáveis quanto a formas de negar essas condições era bastante grande!
1. A exclusão mútua pode ser evitada somente em alguns casos. Por exemplo, quando o recurso compartilhado é uma impressora, ou equivalente, pode-se evitar a EM ao se utilizar a técnica de spooling, em que é criada uma fila de espera que um único processo administra. Nem sempre o spooling pode ser realizado.
2. Para evitar que um processo retenha um recurso enquanto estiver a espera de outro (que pode gerar deadlock), pode-se realizar uma aquisição de recursos em bloco, no qual o processo tenta conseguir o direito de acesso a todos os recursos de imediato e, caso não consiga, libera os recursos para os quais eventualmente tenha conseguido direito de acesso. Nem sempre é possível pois há casos em que o proceso não pode prever quais recursos serão necessários.
3. A espera circular pode ser evitada de mais de uma forma. Uma delas é a manutenção por parte do SO de um grafo de alocação de recursos em que, a cada recurso solicitado, é avaliado se essa solcicitação pode ou não gerar deadlock e o recurso é ou não negado. Outra solução consiste da ordenação dos recursos e na regra de que os recursos só podem ser concedidos em ordem crescente ou decrescente, previamente determinada. Os recursos seriam então numerados.
4. Não é viável fazer com que o uso de qualquer recurso seja preemptível sem gerar inconsistências ou desfazer o trabalho realizado por algum processo. No caso de uso de arquivos: para que um processo escrevendo em um arquivo pudesse ser preemptado seria necessário manter uma cópia do arquivo original, usá-la no trabalho do processo que levou o primeiro à preempção e depois refazer o trabalho do primeiro processo sobre o resultado do trabalho do segundo.
Last update: Mon Jun 1 20:14:16 EST 1998 by Noemi