Aula 4 - Sistemas Operacionais - Gerenciamento de Memória

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Gerenciamento de Memória
Prof. Esp. Alan Rafael Ferreira dos Santos 
Universidade Federal do Piauí – ufpi 
Campus senador helvídio nunes de barros 
Bacharelado em Sistemas de Informação
Disciplina: Sistemas Operacionais 
1
Roteiro 
Memória sem Abstração;
Abstração de Memória;
Algoritmos de Substituição de Páginas;
Questões de Projetos para Sistemas de Paginação;
Segmentação;
Segmentação com Paginação.
 
2
1. Memória sem Abstração 
Memória mais simples que era implementada em computadores das décadas de 70 e 80.
Apenas a memória física era considerada, ou seja, quando um computador executava uma instrução do tipo “MOV REGISTER 1, 1000” o computador apenas movia o valor 1000 para o “REGISTER 1”.
Nestas condições, não é possível executar dois programas simultaneamente, pois se um programa A escrevesse um uma posição 1000, apagaria qualquer valor que foi armazenado pelo programa B.
Existem três variações deste modelo: 
3
1. Memória sem Abstração 
4
1. Memória sem Abstração 
O terceiro modo (c) foi implementado nos primeiros computadores pessoais.
Como executar múltiplos programas sem abstração de memória?
A solução seria fazer o S.O. salvar o conteúdo completo da memória em um arquivo de disco e, em seguida, introduzir e executar o próximo programa.(swapping)
Acrescentar outro hardware possibilita a execução de múltiplos programas simultâneos.
Problema: a memória física absoluta é referenciada por ambos os programas. 
O desejado seria um conjunto privado acessar um conjunto privado de endereços.
 Outra solução proposta foi a alocação estática.
5
2. Abstração de Memória
De modo geral, a exposição da memória a processo apresenta várias desvantagens:
Se um programa pode endereçar diretamente a memória poderá acidentalmente ou intencionalmente danificar o sistema e paralisá-lo.
A implementação prática da exposição da memória é complexa e dificultosa para fazer o sistema executar dois processo simultâneos.
A solução é inventar uma abstração da memória, ou seja, não deixar visível diretamente os espaços de memória e sim uma estrutura intermediária chamada de espaço de endereçamento.
Um espaço de endereçamento é um conjunto de endereços que um processo pode usar para endereçar a memória.
6
2. Abstração de Memória
Podemos associar exemplos para entender os espaços de endereçamento:
Números de telefones: 0000.0000 à 9999.9999
Faixas de IP: 1.1.1.1 à 255.255.255.255
O objetivo do espaço de endereçamento é dar a cada programa seus próprio espaço de endereço de modo que a aquele endereço seja diferente do endereço físico, ou seja, se um programa A usa o endereço 28 e o programa B também utiliza o mesmo endereço 28, ambos terão localizações físicas diferentes.
7
2.1 Noção de Espaço de Endereço
Registradores Base e Registradores limite:
Versão simples da “alocação dinâmica” que mapeia cada espaço de endereçamento do processo em partes diferentes da memória física de modo simples.
Dois programas podem ocupar a memória em posições consecutivas, ou seja, quando um programa é executado, o registrador base e carregado com o endereço físico (início do programa) e o registrador limite é carregado com o comprimento do programa. 
Cada vez que o processo é referenciado o hardware da CPU acrescenta automaticamente o valor base ao endereço, este é verificado com o valor do tamanho do programa, caso haja divergência será gerado um erro.
8
2.1 Noção de Espaço de Endereço
9
A utilização do registrador base e registrador limite é um modo fácil que oferece a cada processo um endereço privado, porém tem uma grande desvantagem que é a expansão e realocação de processos.
 
2.2 Troca de Memória 
As memórias principais atuais não possuem espaço suficiente para armazenar todos os processo do sistema. 
Tanto o Windows como o Linux tem entre 40 – 60 programas que são inicializados com o sistema, tais processo não podem ficar na memória principal e precisam ser movidos para memória secundária.
Uma técnica swapping é utilizada para fazer com que uma memória secundária possa ser referenciada. 
Outra técnica é a memória virtual que possibilita um programa a ser executado mesmo que esteja parcialmente carregado na memória principal.
Um problema enfrentado pela troca de memória é os espaços vazios que são deixados na memoria RAM. 
 
10
2.2 Troca de Memória 
É necessário uma técnica denominada compactação de memória para organizar estes espaços, porém esta estratégia geralmente não é utilizada por consumir muito tempo de processamento.
Outro ponto importante é a quantidade de memória que deve ser alocada a um processo de acordo com sua natureza: tamanho fixo ou variável.
11
2.2.1 Partição Fixa
Se partições idênticas:
processos menores que o tamanho da partição podem ser carregados diretamente. 
Processos maiores exigirão overlay (sobreposição de memória).
Se processos menores
Fragmentação interna
Desperdício de MP
12
2.2.1 Partição Fixa
Diminuem a ineficiência ( não elimina por completo)
Associa o processo a menor partição possível
Aumenta a sobrecarga do gerenciamento 
De qualquer forma:
O número de partições determina o número de processos
Processo pequenos utilizam de maneira ineficiente a memória 
13
2.2.2 Partição Dinâmica
Cada processo recebe o tamanho de memória que necessita.
Não existe um tamanho fixo de partições, elas vão sendo criadas e destruídas conforme a necessidade dos processos.
É necessário implementar um gerenciamento de buracos e processos 
14
SO
P1
320k
SO
SO
P1
P3
288k
SO
SO
P1
P2
P2
224k
SO
SO
P1
P2
P3
P4
128k
- sem espaço
- SO faz swapping
2.2.2 Partição Dinâmica
Buracos começam a ser formados
Necessidade de arrumar os espaços 
15
SO
SO
P2
P3
P4
2.2.2 Partição Dinâmica
16
2.2.3 Gerenciamento de Memória Livre
Gerenciamento de memória com mapa de bits 
Gerenciamento de memória com listas encadeadas
17
2.2.3.1 Gerenciamento de Memória com Mapa de Bits
A memória é dividida em partes em partes tão pequenas como palavras ou em partes tão grandes como kilobytes. A cada unidade de alocação corresponde um bit no mapa de bits. (0 é livre e 1 é ocupado)
Quanto menor a unidade de alocação maior será seu mapa de bits e quanto maior a referida unidade menor será seu mapa de bits.
Contudo, se a unidade for definida como grande poderá haver desperdício de memória se o tamanho do processo não for exatamente múltiplo da unidade de alocação.
18
2.2.3.1 Gerenciamento de Memória com Mapa de Bits
19
2.2.3.1 Gerenciamento de Memória com Mapa de Bits
O mapa de bits é um maneira simples de gerenciar palavras na memória em uma quantidade fixa de memória, pois o tamanho deste mapa de bits só depende do tamanho da memória e da unidade de alocação.
Problema: quando é necessário inserir um processo de tamanho k na memória o gerenciador de memória tem que procurar no mapa de bits uma sequência de zeros consecutivos. A busca por esta combinação é muito lenta, constituindo um argumento contra o mapa de bits.
 
20
2.2.3.2 Gerenciamento de Memória com Listas Encadeadas
Nesta situação é mantido uma lista encadeada de segmentos de memória. Um segmento pode ser um espaço de memória ocupada ou livre.
Esta técnica mantem os segmentos ordenados pelo seu endereço, permitindo uma atualização rápida e simples.
Cada processo tem dois vizinhos (exceto quando o mesmo estiver no início ou no fim da lista).
Após o término de alguns processo os espaços precisam ser combinados para poder de adequar a outros novos processos.
21
2.2.3.2 Gerenciamento de Memória com Listas Encadeadas
22
2.2.3.2 Gerenciamento de Memória com Listas Encadeadas
Nesta técnica é possível utilizar vários algoritmos para alocar memória a um processo recém-criado: 
Primeiro encaixe (o melhor) - first fit
seleciona o primeiro que encaixa, a partir do início.
mais simples, mais rápido e melhor na maioria das vezes.
Próximo encaixe (um pouco pior) – next fit
seleciona o primeiro que encaixa, a partir
da última partição selecionada.
usualmente seleciona para o final da MP.
Melhor encaixe - best fit
de todas as partições, seleciona aquela imediatamente maior.
mais custoso, maior grau de fragmentação externa.
23
3. Memória Virtual
Os softwares estão aumentando de tamanho mais rápido que as memórias, em virtude deste fato, é necessário executar programas enormes que não se encaixam na memória. 
Uma Técnicas foi desenvolvida para tentar contornar a situação e foi chamada de memória virtual que faz com que cada programa tenha seu próprio espaço de endereçamento divididos em blocos denominados de páginas.
Memória virtual é uma generalização da ideia de registrador-limite e registrador- base.
Funciona perfeitamente em sistemas multiprogramação.
24
3. Memória Virtual por Paginação
A memória virtual por paginação é uma técnica de gerência de memória onde o espaço de endereçamento virtual e o espaço de endereçamento real são divididos em blocos denominados páginas. 
Todo mapeamento de página é realizado através da tabela de páginas.
A MMU (Memory Management Unit) mapeia os endereços virtuais em endereços físicos, ou seja, detecta o endereço como virtual e de acordo com seu mapeamento situa-se na página virtual realizando a conversão para o endereço físico.
25
3. Memória Virtual por Paginação
26
3. Memória Virtual por Paginação
Os processos são divididos em páginas que possuem o mesmo tamanho e de fragmentação pequena (tamanho em geral de 1KB).
Cada processo não precisa estar necessariamente na memória principal para ser executado.
Os processo não precisam necessariamente estar alocados de maneira contígua na memória e os endereços podem ser gerados conforme o tempo de execução.
Um bit de ausência/presença informa se a página está fisicamente presente ou não na memória.
 
27
3. Memória Virtual por Paginação
28
3. Memória Virtual por Paginação
Se o bit de presença/ausência for igual a “0”, isto indica que a página virtual não está na MP, mas se igual a “1”, a página está localizada na MP.
Quando a página não está na MP, dizemos que ocorreu uma falta de página, neste caso o S.O. transfere a página da memória secundária para a MP, realizando uma operação de E/S denominada paginação.
Um número de falta de páginas geradas por um processo é denominado de taxa de paginação do processo. O excesso pode provocar perca de desempenho.
Quando ocorre um paginação o processo entra em estado de espera.
29
3.1 Acelerando a Paginação 
Dois problemas importantes: 
O mapeamento do endereço virtual para o endereço físico deve ser rápido.
Se o espaço de endereço virtual for grande a tabela de página será grande
Cada processo tem sua tabela de páginas e quando é inicializado o S.O. carrega essa tabela nos registradores retirada de uma cópia mantida na MP.
Vantagem: não requer referências a MP durante o mapeamento
Desvantagem: é excessivamente caro manter tabela de páginas grandes (necessidade de registradores maiores ) 
Solução: Equipar as máquinas com um pequeno dispositivo de hardware para mapear endereços virtuais (TBL – Tranlation lookaside Buffers ou memória associativa)
30
3.1 Acelerando a Paginação 
Quando um endereço virtual é apresentado a MMU para a tradução o hardware verifica se este número está presente na TBL, caso esteja presente, o endereço físico é obtido diretamente da mesma, caso contrário, é feita uma busca na tabela de páginas e posteriormente a conversão pela MMU que sobrescreve esses valores na TBL. 
Gerenciamento da TBL por software: as entradas da TBL são carregadas pelo S.O. 
Quando há a ausência de páginas e gerado uma interrupção de hardware que repassa o problema para o S.O. que procura na tabela de páginas e converter o endereço virtual em físico e sobrescrever a TBL.
 
31
3.1 Acelerando a Paginação 
Ausência leve: Ocorre quando uma página referencia da não está na TBL, mas na MP (necessário apenas atualizar a TBL).
Ausência completa: quando uma página não está nem na MP e muito menos na TBL (necessário uma busca na memória secundária).
Tabela de Páginas para memórias grande:
Tabela de Páginas Multiníveis
Tabela de Páginas Invertidas
32
4. Algoritmos de Substituição de Páginas 
O maior problema na gerência de memória virtual por paginação não é decidir que paginas carregar para a MP, mas quais liberar?
Quando um processo necessita de uma nova página e não existe espaço disponível o sistema deverá decidir, entre as diversas páginas alocadas na MP, qual delas será liberada para o mesmo.
Os algoritmos de substituição de páginas tem o objetivo de selecionar os espaços que tenham menores chances de serem referenciados.
 A melhor estratégia de substituição de páginas seria aquela que escolhesse o melhor espaço que não fosse mais utilizado no futuro e levasse mais tempo para ser novamente referenciado.
33
4. Algoritmos de Substituição de Páginas 
Principais algoritmos de substituição de páginas:
Ótimo 
Aleatório 
FIFO 
LFU (página menos referenciada)
LRU (página com mais tempo sem ser referenciada)
NRU (semelhante ao LRU)
FIFO com Buffer de Páginas 
FIFO Circular (clock)
34
4. Algoritmos de Substituição de Páginas 
1. Algoritmo Ótimo : 
Seleciona para substituição uma página que não será mais referenciada no futuro ou aquela que levará maior intervalo de tempo para ser novamente utilizada (menor taxa de paginação).
É apenas um modelo comparativo, impossível implementar (irrealizável), não sendo possível ter valores relacionados a desempenho.
Apenas útil para estudos teóricos que possam embasar algoritmos que realmente sejam implementados em sistemas reais.
35
4. Algoritmos de Substituição de Páginas 
2. Algoritmo Aleatório:
Como o próprio nome já diz não utiliza nenhum critério de seleção de páginas, todas as paginas tem a mesma chance de serem escolhidas.
Apesar de ser uma estratégia que consome pouco recurso do sistema é pouco implementada.
Baixa eficiência 
36
4. Algoritmos de Substituição de Páginas 
3. Algoritmo FIFO (First-in First-out):
A página que foi primeiro utilizada será a primeira a ser escolhida, ou seja, a página selecionada será a que estiver a mais tempo na MP.
Associação de fila as páginas na memória onde as mais antigas estão na frente.
Nem sempre a página mais antiga será a melhor a ser substituída.
Geralmente o FIFO é implementado com algum outro mecanismo.
 
37
4. Algoritmos de Substituição de Páginas 
4. LFU (Least-Frequently-Used):
Este algoritmo seleciona as páginas menos referenciadas, ou seja, espaços menos utilizados. Para isso é mantido um contador com um número de referências para cada página de memória.
A pagina na qual o contador possuir menor valor será escolhida .
Parece ser uma boa estratégia, porém páginas que estão a pouco tempo na memória podem ser escolhidas.
Esquema raramente utilizado, porém pode embasar outros algoritmos de substituição
38
4. Algoritmos de Substituição de Páginas 
5. NRU (Not-Recently- Used):
Bastante semelhante ao LRU, porém com menor sofisticação, para implementar este tipo de estratégia e necessário implementar um Bit de Referência (BR). O bit indica se a página foi usada recentemente e está presente em cada entrada da tabela de páginas.
Quando a página é carregada na MP o Bit de Referência é alterado pelo hardware, se a página foi referenciada (BR=1), periodicamente estes bits são alterados (BR=0), a medida que estas páginas são utilizadas o valor muda para 1.
O NRU se torna mais eficiente se o Bit de Modificação (BM) for utilizado em conjunto com o BR.
39
4. Algoritmos de Substituição de Páginas 
5. NRU (Not-Recently- Used):
40
4. Algoritmos de Substituição de Páginas 
5. FIFO com Buffer de Páginas :
O algoritmo FIFO apresenta limitações quanto a páginas antigas, no entanto se implementar variações no algoritmo ele se torna mais eficiente.
Um algoritmo FIFO com buffer de páginas combina uma Lista de Páginas Alocadas (LPA) com uma Lista de Páginas Livres (LPL). A LPA organiza as páginas alocadas
a mais tempo na MP no início da lista, enquanto as páginas recentes ao final. Da mesma forma a LPL organiza todos os espações livres da MP.
A LPL funciona como buffer, evitando o acesso a memória secundária. 
 
 
41
4. Algoritmos de Substituição de Páginas 
42
5. FIFO com Buffer de Páginas :
4. Algoritmos de Substituição de Páginas 
6. FIFO Circular (clock):
Este algoritmo utiliza como base o FIFO, porém as páginas de memória estão alocadas na memória em uma estrutura de lista circular, semelhante a um relógio.
Neste algoritmo existe um ponteiro que guarda a posição da página mais antiga e cada página possui um Bit de Referência (BR) que identifica se a página foi referenciada recentemente. Quando é necessário substituir uma página o sistema verifica se o ponteiro aponta para o BR = 0. Nesta situação a página selecionada é descartada.
 	
43
4. Algoritmos de Substituição de Páginas 
6. FIFO Circular (clock):
44
5. Questões de Projeto de Sistemas de Paginação
A escolha do tamanho da página é primordial em um projeto de sistemas que implementam memória virtual por paginação. O tamanho de página é associado ao hardware e varia de acordo com a arquitetura do processador.
Algumas arquiteturas permitem a configuração de páginas.
O principal argumento a favor do uso de páginas pequenas é a melhor utilização dos espaços de memória.
Outra preocupação em relação ao tamanho de páginas é o tempo gasto para realizar a leitura e gravação na memória secundária.
A tendência nos novos sistemas com aumento na velocidade de acesso a memória principal e secundária é a adoção de páginas maiores, mesmo com os problemas citados.
45
6. Proteção de Memória 
Em qualquer sistema multiprogramável, onde diversas aplicações compartilham a mesma memória é necessário mecanismos para manter a privacidade dos espaços de memória dedicados ao S.O.
Se uma página do S.O. for alterada indevidamente por um processo pode causar uma instabilidade ou uma parada completa.
A proteção de páginas é feita individualmente, ou seja, cada página possui uma restrição específica.
A utilização de bits podem restringir de maneira fácil e eficiente, negando o acesso totalmente ou parcialmente, porém é de complexa implementação em memórias virtuais por paginação. 
46
6. Proteção de Memória 
47
7. Memória Virtual por Segmentação
É a técnica de gerência de memória onde o espaço de endereçamento virtual é dividido em blocos de tamanho diferentes chamados “segmentos”.
Nesta técnica existe uma relação entre a lógica do programa e a sua alocação na memória principal, diferentemente da estrutura de paginação.
A definição dos segmentos é dada pelo compilador do programa, cada segmento pode representar um procedimento, vetor, função ou pilha. Estes podem mudar conforme a execução do programa.
O espaço de endereçamento possui um limite de segmentos que podem existir, onde cada segmento pode variar dentro do limite.
 
48
7. Memória Virtual por Segmentação
49
7. Memória Virtual por Segmentação
O mecanismo de mapeamento de segmentos é bem semelhante a paginação:
Tabela de Mapeamento de Segmentos (TMS)
Número de Segmento Virtual (NSV) e deslocamento
O NSV indica o segmento virtual que é indicado como índice na TMS.
Uma grande vantagem da segmentação em relação a paginação é a facilidade de tratar o dinamismo.
Para alocar os segmentos na memória o S.O. mantém uma tabela com áreas livres e áreas ocupadas da MP. A política de alocação pode ser a mesma que já vimos na paginação (first-fit, best-fit...).
50
7. Memória Virtual por Segmentação
Quando um segmento precisa ser alocado na memória e não há espaço suficiente é necessário realocar os segmentos para que os espaços livres sejam agrupados.
O endereço virtual tem uma relação com o endereço real que é notada no ato da conversão pelo S.O.
Os endereços nas tabelas de segmentos possuem uma serie de informações adicionais que facilitam sua localização.
51
7. Memória Virtual por Segmentação
52
7. Memória Virtual por Segmentação
53
8. Memória Virtual por Segmentação com Páginas
É a técnica de gerência de memória onde o espaço de endereçamento é dividido em “segmentos”, e por sua vez, cada segmento é dividido em página. 
O S.O. interpreta cada segmento como um conjunto de páginas (cada segmento com tamanho diferente) que são mapeadas por tabela de páginas associadas aos seus segmentos.
Resolve definitivamente o problema da fragmentação externa.
54
8. Memória Virtual por Segmentação com Páginas
55