SISTEMAS OPERACIONAIS PROVA 0.0 AN OUTCAST OF THE ISLANDS

RAUL H.C. LOPES

1. Introdução

Esta primeira parcial da prova 0 avalia conceitos de comunicação de processos e escalonamento de CPU. A prova é individual. Você pode consultar as suas nostas de aula e seu livro. Todas as questões têm o mesmo peso.

2. As questões

Questão 1. Assuma que existe uma estrutura de heap com as seguintes operações:

• addcredit(heap t h, int pid, int c)

Incrementa crédito de pid de c. Se pid for igual a −1 soma c ao crédito de todos os processos.

• popfirst(heap t h)

Retorna o processo com crédito mais elevado.

• getfirst(heap t h, int *pid, int *c)

Retorna pid e crédito do processo com maior crédito em h. Considere que:

• um escalonador dispõe como única estrutura de dados para escalonar o processador um heap t para armazenar processos em estado ready;

• a cada processo (em estado run ou ready) está associado um crédito que pode periodicamente ser incrementado;

• o escalonador é preemptivo.

(1) Assumindo que processos em ready têm periodicamente seu crédito incrementado de a e um processo em run tem seu crédito periodicamento incrementado b:

• Que algoritmo de escalonamento você obtém se a > b > 0? Prove.

Date: 13/03/2003.

• Que algoritmo de escalonamento você obtém se a < b < 0? Prove.

Questão 2. Assuma que você vai implementar uma árvore B concorrente armazenada em disco e que o acesso a disco é feito através de um servidor de nós que não compartilha memória com processo algum e que oferece como únicas operações para recuperação e escrita de nós:

• acquireNode: dada identificação de um nó, lê o nó do disco e retorna-o, bloqueando o acesso a esse nó por i unidades de tempo.

• commitNode: dada identificação do nó, grava-o no disco.

(1) Proponha mecanismo para que processos possam tranferir e receber nós do servidor.

(2) Mostre que é possível ter um algoritmo simples de contagem de tempo e usar as operações acima implementar uma polítca Shortest Job First na aquisição de nós? Discuta qualidades e desvantagens da mesma. Proponha melhorias ainda usando as mesmas operações.

Referências

[1] Donald E. Knuth, Sorting and searching, The Art of Computer Programmin, vol. III, Addison-Wesley, 1998.