MAC 324 Estruturas de Dados para Engenharia

1  Descrição do modelo simplificado a ser simulado nesta fase

O modelo a ser simulado segue o esquema de fila única para as impressoras (são 5 impressoras), cada impressora com velocidade de 3000 linhas por minuto. Quando uma impressora fica disponível, o primeiro processo da fila passará à impressão, a menos que algum processo já esteja no sistema há mais de 10 minutos (Veja Figura 1).

Os processos devem ser gerados como nas fases anteriores. Imprima, para cada processo que termina sua impressão também as informações relativas à fila das impressoras. Além disso, mostre o tempo médio gasto nessa fila. Valem as mesmas observações quanto a qualidade da saída e documentação de seu programa. A seguir, mostramos as especificações da implementação do modelo

2  Especificações da implementação do modelo

1. Ciclo de intervenção do sistema de timesharing: 100 milisegundos. Isto significa que a cada 100 milisegundos o scheduler decide qual é o próximo processo que deverá ser executado.
2. Considere que um processo pode ter um tempo mínimo de 10 milisegundos.
3. O scheduler também deve decidir qual é o próximo processo que deverá ser executado imediatamente após o término da execução de qualquer processo, mesmo que o término tenha ocorrido antes de se completar um ciclo de intervenção (ou seja, 100 milisegundos).
4. A fila da CPU deve ser implementada numa lista circularmente ligada (com ou sem cabeça-de-lista).
5. Para simplificar o modelo, um processo entra na fila das impressoras imediatamente após o término da execução do mesmo pela CPU.
6. Velocidade das impressoras: 3000 linhas por minuto.
7. Número máximo de processos na fila da CPU a cada instante: 20.
8. Os processos na fila das impressoras estarão em duas filas ao mesmo tempo: uma por ordem de ingresso na fila e outra pelo tempo de permanência no sistema. Processos que estão no sistema a mais do que 10 minutos têm prioridade para serem impressos. Se não houver processos com mais de 10 minutos no sistema, então a impressão será por ordem de ingresso. Estas filas devem ser implementadas de modo a permitir que inserções em ambas as filas e remoção do primeiro elemento de cada fila possam ser feitas em tempo no máximo O(log n). Para isto, implemente a primeira fila utilizando uma lista circular duplamente ligada com ou sem cabeça-de-lista, e para representar a outra fila, utilize uma fila de prioridade implementada num heap.

3  Especificações da saída do programa

1. Sempre que terminar a execução de um processo, imprima as seguintes informações:
 
a) características do processo (número de identificação, classe, tempo de CPU e número de linhas impressas);

b) tempo total de permanência no sistema;

c) tempo gasto em cada uma das filas;

d) razão entre o tempo útil (tempo de execução na CPU, ou seja, running time) e tempo total de permanência no sistema (ou seja, elapsed time).
 

2. Ao término da simulação, imprima o número total de processos executados, assim como a média dos itens b), c) e d) para cada classe.
3. Além disso, imprima periodicamente (digamos, a cada 100 segundos-a escolha deste número fica a seu critério) o estado de cada uma das filas, inclusive as duas filas para as impressoras:
 
a) Fila das classes. Imprima para cada processo o seu número e o tempo que está na fila.

b) Fila da CPU. Imprima para cada processo o seu número, tempo de CPU, e tempo restante de execução.

c) Fila das impressoras por ordem de chegada. Imprima para cada processo o seu número, número de linhas que irá imprimir, e o tempo que esta na fila.

d) Fila das impressoras por tempo de permanência no sistema. Imprima para cada processo o seu número, número de linhas que irá imprimir, e o tempo de permanência no sistema.
 

4. Se você achar conveniente imprimir mais informações está ótimo. A saída do programa deve, principalmente, ajuda-lo a verificar se a simulação (ou seja, o seu programa) está correta.