- - - - CENAPAD-MGCO

A seguir: Respostas Acima: Introdução à Programação Paralela Anterior: Conclusões

Exercícios

Exercício 17082 (Quicksort paralelo)

 Proponha uma versão paralela para o Quicksort. Mostre o grafo de precedências associado ao procedimento. Supondo que a mediana de cada partição é sempre escolhida como pivô, calcule o tempo necessário para a ordenação de n elementos por um computador com muitos processadores. Considere nulo o tempo necessário para a criação e término de processos. Observação: Classificação em paralelo constitui um campo ativo de pesquisa; um panorama da área pode ser encontrado em [Bitton et al., 1984]

Exercício 17084 (Comparação e Troca em paralelo)

 (Solução ) Proponha um ``sort'' paralelo baseado no algoritmo de comparação e troca, onde fases pares e ímpares se alternam. Nas fases pares os elementos de índice par são comparados com os seus sucessores imediatos, sendo feitas trocas nas posições desordenadas. As fases ímpares são análogas. Calcule o tempo necessário para a ordenação de um vetor com n elementos.

Exercício 17086 (Transações)

 (Solução ) Considere o seguinte programa:

a = 1;  b = 1;
cobegin
  T1:: a := a + 100;  b := b + 100;
||
  T2:: a := a * 2;  b := b * 2;
coend

Na terminologia introduzida por [Eswaran et al., 1976], uma transação é uma unidade de consistência , isto é, um procedimento que, se executado isoladamente, preserva a consistência de um banco de dados. Supondo que a = b é a condição de consistência no programa acima, T1 e T2 seriam transações. O controle de concorrência de um banco de dados deve cuidar para que o efeito de transações executadas em paralelo seja equivalente à sua execução numa sequência qualquer. Acrescente ao programa acima comandos de sincronização que garantam a serializabilidade de sua execução. Procure maximizar o paralelismo, não utilizando uma única região crítica.

Exercício 17087 (Escalonamento SJF)

  Uma impressora é compartilhada por diversos processos. Cada processo cliente submete seu arquivo chamando printerScheduler.submit(int fileSize) ; Seu servidor deve:

1.

garantir a exclusão mútua no uso da impressora, e

2.

dar prioridade aos arquivos menores, impondo uma política SJF (Shortest Job First ) no escalonamento.

Exercício 17088 (Aging)

  Arquivos muito grandes podem ser preteridos indefinidamente numa política SJF. Mude a solução do problema anterior, usando a técnica de aging (envelhecimento), onde:

• a prioridade inicial de cada submissão é o tamanho do arquivo a ser impresso;
• cada vez que um processo ganha a impressora, ele aumenta a prioridade de todos os processos que estão esperando.

Compare a política de aging com as políticas SJF e FIFO.

Exercício 17089 (Controlando o nível de paralelismo)

 Modifique a solução para o problema dos leitores e escritores de forma a permitir que no máximo 4 leitores consigam ler simultaneamente.

Exercício 17090 (Árvore-B)

 (Solução ) Um sistema de controle de concorrência de uma árvore-B pode adotar a seguinte sistemática:

• pode-se ter um número arbitrário de leituras simultâneas;
• um processo escritor (que modifica a árvore) comporta-se da seguinte maneira:
  • requisita acesso exclusivo com relação aos outros escritores; leitores podem continuar lendo, e novos leitores podem entrar;
  • obtida a autorização, caminha na árvore-B até atingir o ponto onde faz efetivamente a modificação;
  • requisita então a extensão aos leitores da exclusividade do acesso;
  • faz a modificação, e libera a árvore.

Programe um módulo que faça este controle de concorrência.
Observação : este controle de concorrência é ingênuo, restringindo desnecessariamente o paralelismo. Algoritmos muito mais eficientes podem ser encontrados por exemplo em [Johnson and Shasha, 1993].

Exercício 17098 (Pool de Recursos Idênticos)

 R recursos idênticos são compartilhados por C processos clientes. Um recurso não pode ser utilizado por mais de um processo simultaneamente. A vida de um processo cliente segue o ciclo:

• pensa;
• requisita n recursos, onde n é um valor arbitrário entre 1 e R;
• utiliza os n recursos;
• devolve os n recursos.

1.

Proponha uma solução que utilize a técnica de aging para aumentar a taxa de utilização dos recursos mantendo a garantia de equanimidade.

2.

Argumente a favor da correção da solução proposta.

Exercício 17099 (Buffer com mútiplos clientes)

 Encontre uma solução equânime (livre de starvation ) para o problema do compartilhamento de um buffer limitado por um número qualquer de processos produtores e consumidores.