Zé Moleza | TCC, monografias e trabalhos feitos. Pesquise já!

Você está em Trabalhos Acadêmicos > Exatas > Informática

Favoritos Seus trabalhos favoritos: 0

Trabalho em Destaque

Título: A Proteção Social

1 INTRODUÇÃO O nascedouro foi em 1883, na Alemanha com o Chanceler Bismarck. Foi um marco tanto da Seguridade Social como da Previdência Social (primeiro sistema escrito de previdência social – seguro social). A forma de contribuição ou custeio para…


Publicidade


Publicidade

Paginação, Deadlocks e Starvation

Trabalho enviado por: Flávio Vieira de Castro

Data: 30/07/2005

Algoritmos de Substituição de Páginas


Introdução

Neste trabalho apresentarei características dos sitemas operacionias modernos como:

Paginação – Um excelente recurso que faz com que projetos de hardware de pouco desempenho em relação a memórias, possam apresentar bom desempenho frente a programas que exijam maior quantidade de memória do que o existente no projeto.

Deadlock – Um problema que está presente em todos os sistemas operacionais atuais, que leva ao travamento de processos, serão apresentadas algumas formas de evitar este problema.

Starvation – A situação de starvation está presente quando o sistema operacional provê prioridades a processos, que não atualizados fazem com que os processos de menor prioridade nunca sejam executados causando assim, deficiência em servidores de impressão e etc.


1 - Paginação

A maioria dos sistemas de memória virtual usa a técnica denominada paginação, que será descrita a seguir. Em muitos computadores existe um conjunto de endereços de memória que os programas podem gerar no decorrer de suas execuções. Quando um programa executa uma instrução como

MOVE REG,1000

ele está copiando o conteúdo do endereço de memória 1000 para o REG, ou vice-versa, dependendo do computador. Os endereços podem ser gerados por indexação, registradores-base, registradores de segmento, além de várias outras técnicas.

Tais endereços, gerados pelo programa, são chamados de endereços virtuais e forma o espaço de endereçamento virtual. Em computadores sem memória virtual, o endereço virtual é colocado diretamente no barramento da memória, fazendo com que o endereço físico da memória, equivalente a ele, seja lido ou escrito. Quando a memória virtual é usada, os endereços virtuais não vão direto para o barramento da memória. Em vez disso, eles são encaminhados à unidade de gerência de memória (MMU), um chip ou um conjunto de chips que mapeiam os endereços virtuais em endereços físicos da memória, conforme ilustrado na Fig. 3.10.

Um exemplo de como este mapeamento trabalha é mostrado na Fig. 3.11. Neste exemplo, temos um computador que pode gerar endereços de 16 bits, de 0 até 64k, correspondentes ao espaço de endereçamento virtual da máquina. No entanto, este computador tem apenas 32K de memória física, de forma que apesar de podermos escrever programas com até 64K, estes não podem ser totalmente carregados na memória e executados. Uma cópia completa do programa deve sempre ser mantida no disco, de forma que pedaços dele possam ser colocados na memória, quando necessários.

O espaço de endereçamento virtual é dividido em unidades denominadas páginas. As unidades correspondentes na memória física são as molduras de página (page frames). As páginas e as molduras de página são sempre do mesmo tamanho. Neste exemplo, elas têm 4K endereços, porém páginas de 512 até 8K são usadas rotineiramente. Com 64K de espaço de endereçamento virtual, e 32K de memória real, teremos 16 páginas virtuais e oito molduras de página. As transferências da memória para o disco e vice-versa são sempre feitas em páginas.

Quando o programa tenta acessar o endereço 0, por exemplo, usando a instrução

MOVE REG,0

o endereço virtual 0 é enviado à MMU. Esta conclui que este endereço virtual cai na página 0 (endereços virtuais de 0 a 4095), que de acordo com seu processo de mapeamento está na moldura de página 2(endereços reais de 8.192 a 12.287). Ela então transforma o endereço que lhe foi entregue para 8.192, e coloca este valor no barramento da memória. A placa de memória desconhece a existência da MMU, e simplesmente enxerga uma requisição para ler ou escrever no endereço 8.192, realizando tal acesso. Então, a MMU efetivamente mapeia todos os endereços virtuais de 0 a 4.095 nos endereços reais de 8.192 a 12.287.

Da mesma forma, a instrução

MOVE REG,8192

é executada como

MOVE REG,24576

em virtude do endereço virtual 8.192 encontrar-se na página 2, e esta página ser mapeada na moldura 6 (endereços físicos de 24.576 a 28.671) e é mapeado no endereço real 12.288 + 20 = 12.308.

Por si só, está capacidade de mapear as 16 páginas em qualquer uma das molduras de página, realizada pela MMU, não resolve o problema do espaço virtual ser maior do que o espaço real disponível na memória. Como dispomos de apenas oito molduras de página, somente oito das páginas virtuais da Fig. 3.11 são passíveis de ser mapeadas em endereços físicos. As outras, identificadas por um X na figura, não são mapeáveis. No hardware real, um bit de presença/ausência existente em cada uma das entradas informa se a pagina pode eu não ser mapeada.

O que ocorre se um programa tenta usar uma página não mapeada, tentando, por exemplo, executar a instrução

MOVE REG,32780

cujo endereço virtual gerado está 12 bits após a origem da página 8, que tem início em 32.768? A MMU observa que se trata de uma página não-mapeável e força o processador a executar um trap para o sistema operacional. Este trap é denominado falta de página. Como resposta ao trap, o sistema operacional pega a moldura de página menos usada e a copia de volta para o disco. Então ele busca a página referenciada e a copia na moldura que acabou de ser liberada, modifica o mapa e reexecuta a instrução causadora do trap.

Por exemplo, se o sistema operacional resolver substituir a página na moldura 1, ele deve carregar a página virtual 8 no endereço 4K e fazer duas mudanças no mapeamento da MMU. Primeiro, ele deve marcar a entrada correspondente à página virtual 1 como não-mapeável, para que um trap seja gerado quando houver qualquer acesso futuro a um endereço virtual desta página. Depois, ele deve substituir o xis na entrada correspondente à página virtual 8 por um 1, de maneira que quando a instrução que gerou o trap for reexecutada, deve haver o mapeamento do endereço virtual 32.780 no endereço físico 4.108.

Agora vamos dar uma olhada dentro da MMU, para ver como ela funciona, e entender por que escolhemos um tamanho de página que é uma potência inteira de 2. Na Fig. 3.12, vemos um exemplo do endereço virtual 8.196 (0010000000000100 em binário), sendo mapeado usando o mapa da MMU da Fig. 3.11. O endereço virtual de 16 bits que chaga à MMU é dividido em um número de pagina de quatro bits, e em um deslocamento de 12 bits. Com os quatro bits referentes ao número da página, podemos representar 16 páginas, e com os 12 do deslocamento podemos endereçar todos os 4.096 bytes que compõem uma determinada página.

O número da página é usado como índice da tabela de páginas, levando ao número da moldura de página correspondente a esta página virtual. Se o bit e Presença/Ausência for 0, é gerado um trap para o sistema operacional. Se este bit for igual a 1, o número da moldura de página é copiado para os três bits de mais alta ordem do registrador de saída da MMU, junto com os 12 bits do deslocamento, copiados sem nenhuma modificação em relação ao deslocamento do endereço virtual. Juntos eles formam o endereço físico de 15 bits. O conteúdo do registrador de saída é então colocado no barramento da memória, correspondendo ao endereço físico, resultante do endereço virtual que foi apresentado anteriormente à MMU.

1.1 - Algoritmos de substituição de páginas

Quando ocorre falta de página, o sistema operacional deve escolher uma página a ser removida para dar lugar à que deve ser gravada na memória real. Se a página escolhida para ser removida tiver sido modificada durante sua estada de memória, ela deve ser reescrita no disco, de forma a atualizar a cópia lá existente. Se a página não tiver sofrido nenhuma modificação (por exemplo, uma página de código), a cópia do disco continua atualizada, e não é necessário recopiá-la. A nova página é simplesmente escrita em cima da página escolhida para ser retirada.

Apesar de ser poder escolher randomicamente a página a ser retirada a cada ocorrência de uma falta de página, a performance do sistema será muito melhor se conseguirmos substituir uma página que não esteja sendo muito referenciada. Se removermos uma página fortemente referenciada, talvez tenhamos de trazê-la de volta muito em breve, causando um overhead desnecessário. Muito trabalho, tanto teórico quanto experimental, tem sido feito em cima da questão dos algoritmos de substituição de páginas. A bibliografia do paper de Smith (1978) lista nada mais nada menos que 300 outros papers a respeito do assunto.

1.1.1 - O Algoritmo Ótimo

O melhor dos algoritmos de substituição de páginas é fácil de descrever, mas impossível de implementar. Ele funciona da seguinte forma: no momento em que há a ocorrência de falta de página, existe um conjunto delas armazenado na memória. Uma delas será referenciada na próxima instrução, ou seja, trata-se da página que contém a instrução que gerou a falta de página. Outras páginas poderão só ser referenciadas 10, 100 ou até 1.000 instruções depois da atual. Cada página pode ser identificada pelo número de instruções depois da corrente que deverão ser...

Para ver o trabalho na íntegra escolha uma das opções abaixo

Ou faça login



Crie seu cadastro




English Town