Página Principal | Lista de Componentes | Lista de Arquivos | Componentes Membros | Arquivos Membros

Trabalho de Sistemas Operacionais - Programacao Concorrente - Lista Encadeada

versao 1.0

Desenvolvedores

 Helder Brito Nascimento
 Renato Luiz Cunha
 Guilherme Monteiro Garcia
 Luiz Rodrigo Castro
 Uanderson Sigler Gomes

Introducao

Implementacao em linguagem C de uma solucao para o problema de processos concorrentes compartilhando acesso a uma lista encadeada utilizando a biblioteca pthreads.

Tres tipos de processos compartilham acesso a uma lista encadeada: processos de busca, insercao e de eliminacao. Processos de busca meramente examinam a lista; assim podem executar concorrentemente entre si. Processos de insercao incluem itens no final da lista; insercoes devem ser mutualmente exclusivas. No entanto, uma insercao pode ocorrer em paralelo com qualquer numero de buscas. Finalmente, eliminacoes podem ocorrer em qualquer ponto da lista. No maximo um processo de eliminacao pode ter acesso a lista em qualquer instante, e a eliminacao deve ser mutuamente exclusiva com buscas e insercoes. Este problema e uma extensao do problema dos leitores e escritores. descreva as acoes dos processos de busca, insercao e eliminacao. Analise a sua solucao em relacao a possibilidade de starvation para cada um dos tipos de processos.

Nossa Solucao

Nossa solucao consiste no seguinte:

Inicialmente,os Eliminadores sao criados e marcam suas intencoes de eliminar na lista. Como a lista esta vazia,eles ficam bloqueados esperando inseridor inserir uma quantidade "NUM_INSERE" de Nos na lista para poderem ter acesso exclusivo a lista. Em seguida sao criados os Buscadores, que verificam se existem eliminadores tentando eliminar ou eliminando um No na lista. Se existirem, eles ficam bloqueados ate que nao exista mais processos eliminadores tentando acessar a lista pois eles tem menos prioridades do que os Eliminadores. Apos isto, os Inseridores são criados, inserem "NUM_INSERE" Nos na lista e acordam os Eliminadores bloqueados.

Como os Eliminadores devem ter exclusao mutua entre todos os processos, damos a maior prioridade a eles para que nao fiquem em Starvation.Toda vez que a lista e nula ou nao existe intensao em eliminar mais um No da lista, os Eliminadores acordam os inseridores. Estes, por sua vez, cada vez que inserem 1 No na lista acordam um processo bloqueado do tipo Inseridor ou Buscador e idem para o Buscador. Porem, os Eliminadores so voltam a eliminar a lista apos serem inseridos mais "NUM_INSERE" nos na lista, quando serao acordados pelos Inseridores, evitando tambem starvation de algum processo do tipo Inseridor.Os buscadores dificilmente estarao em Starvation pois poderao rodar em paralelo com os inseridores,alem de nao possuirem exclusao mutua no acesso a lista.Depois de acordar os Eliminadores, Buscadores e Inseridores irao automaticamente se bloquearem a espera de que nao haja mais intencao dos eliminadores acessarem a lista.

Compilacao e Execucao

Descompacte o pacote da Listaencadeada, entre no diretorio criado e execute make.

Para rodar a solucao, execute ./lista dentro do diretorio onde foi descompactada nossa solucao. Instrucoes de execucao aparecerao na tela. Boa sorte!

Gerado em Thu Mar 10 15:54:40 2005 para Trabalho de Sistemas Operacionais por