mylab

SO1 – gestão de memória, endereçamento virtual, memória virtual

#gestão de memória, endereçamento virtual, memória virtual

bibliografia especifica:
fundamentos de sistemas operativos, 4º edição, capítulos 4 e 5
operating systems concepts, capítulos 8 e 9
operating systems – internals and design principles, capitulo 7 e 8

#gestão de memória
os mecanismos de gestão de memória:
determinam a organização da memória do computador
identificam o modo de endereçamento: real ou virtual
qual o tamanho dos blocos (de páginas ou segmentos)
e quais os mecanismos de protecção e validação de endereços
e é da responsabilidade do sistema operativo configurar de forma eficiente esses mecanismos proporcionados pelo hardware

os algoritmos de gestão de memória:
são técnicas para fazer a gestão da memória principal e secundária
e é da responsabilidade do sistema operativo usar de forma eficiente esses mecanismos proporcionados pelo hardware

o sistema de endereçamento real:
os endereços correspondem a posições na memória física
um programa é preparador para correr numa determinada gama de endereços
e todos os programas vão querer usar essa gama (sistemas multi-programados)
para o sistema operativo surge uma fragmentação da memória
para o sistema operativo surge limites ao tamanho dos programas
para o sistema operativo surge dificuldades no isolamento e segurança

o sistema de endereçamento virtual:
surgem os endereços virtuais: que podem não corresponder a um espaço de memória física
o processador traduz esses endereços virtuais como se fosse endereços físicos para os programas (tradução transparente)
os endereços de cada processo são subdivididos em conjuntos de blocos
os endereços virtuais do mesmo bloco têm as mesmas regras de tradução para os endereços reais
os blocos mapeados na memória física podem estar em zonas diferentes, sem a necessidade de manter a mesma ordem
é o sistema operativo que gere as transferências e de forma transparente, entre a zona virtual e física
é o sistema operativo que liberta a memoria física
é o sistema operativo que indica ao processador de que forma é feita a tradução de endereços virtuais para reais

surgem as tabelas de segmentos:
são criadas pelos sistema operativo
servem para traduzir os endereços virtuais para reais, e é feito pelo processador através das tabelas de segmentos

surgem os descritores de segmentos:
são as entradas numa tabela
indicam o tamanho e localização da memória física
indicam o tipo de acesso que é permitido (leitura, escrita, execução)
indicam o estado de presença em memória física (bit “P”)

assim o descritor de segmento (figSO1_07):

P, Prot, Base, Lim
em que:
p, indica se o segmento se encontra na memória principal
Prot, indica o tipo de protecção e privilégios (RWX)
Base, indica o endereço real do segmento de memoria
BTS, endereço base da tabela de segmentos
LTS, tamanho da tabela

vantagens da memoria segmentada:
adequa-se à lógica da divisão dos programas
permite trabalhar de forma eficiente sobre uma zona de memória inteira

desvantagens da memoria segmentada:
pode não ser criado um espaço de endereçamento linear e continuo de forma transparente para o processo
são usados algoritmos de gestão complexos
o mapeamento de segmentos pode gerar fragmentação
falta de eficiência se os blocos transferidos entre a memória principal e secundárias forem grandes.

os endereços de memória virtual:
têm um conjunto de bits que indicam qual o descritor de segmento dentro da tabela
e um conjunto de bits que indica qual o deslocamento dentro desse segmento

vantagens da memoria virtual:
facilidade de implementação de sistemas multi-programados
implementação automática de segurança e isolamento
a partilha de zonas de memória entre processos distintos é simples

a memória paginada:
os blocos têm todos o mesmo tamanho
funciona como a tabela segmentada
ao invés de se usarem tabelas de segmentos surgem as tabelas de páginas
cada entrada na tabela de páginas é um PTE (page table entry)
se o endereçamento for muito grande é ineficaz o uso de memoria paginada, surge como solução o uso de tabelas de páginas (em cascata)

assim o descritor o PTE (figSO1_08):

P, indica se a pagina se encontra em memoria principal
Prot, indica o tipo de protecção (RWX)
R, indica se a pagina foi referida
M, indica se a pagina foi modificada
Base, é o endereço real da pagina em memória
BTP, endereço base da tabela de segmentos
LTP, tamanho da tabela

vantagens da memoria paginada:
transparente para o programador
transparente para o processo
como todas as paginas têm o mesmo tamanho os algoritmos de gestão são mais simples e eficientes
as transferências entre a memoria principal e a secundária são feitas por páginas individuais

desvantagens da memoria paginada:
não se adequa à divisão lógica dos programas
as faltas de páginas representam uma perda de eficiência maior do que as faltas de segmento

a memória segmentada-paginada:
junta o melhor de: memoria segmentada e memória paginada

o endereço virtual da memória segmentada-paginada (figSO1_09):

segmento, que indica o descritor dentro da tabela de segmentos que deve ser usado na tradução do endereço
uma página, contém a informação acerca da tabela de página que deve ser usada na tradução do endereço
e o deslocamento

#algortimos de gestão de memória

os algoritmos de atribuição (alocação)
determinam na memoria física, onde fica mapeado um bloco de memoria virtual

os algoritmos de atribuição (alocação) em memória paginada:
as páginas têm todos o mesmo tamanho
é usada a page-frame que está livre
existe uma estrutura que indica quais as páginas que estão ocupadas
a primeira livre é a escolhida

os algoritmos de atribuição (alocação) em memória segmentada:
cada segmento tem um tamanho diferente
surgem algoritmos para que não ocorram problemas de fragmentação, na atribuição de blocos

algoritmo best-fit
pesquisa a lista à procura do bloco cuja dimensão seja a mais próxima
procura o melhor bloco que se adapte as dimensões necessárias
a lista de blocos está ordenada de forma crescente

algoritmo worst-fit
procura o maior bloco disponivel
quer evitar que surjam blocos pequenos (com o que “sobra”)
blocos grandes são todos ocupados
a lista de blocos está ordenada de forma decrescente

algoritmo first-fit
procura o bloco que satisfaz
a lista de blocos está ordenada por endereço de blocos

algoritmo next-fit
procura o bloco que satisfaz
continua a pesquisa no ponto onde esteve antes

algoritmo buddy
todos os blocos são do tamanho 2^n
usa o método de recursão para encontrar o bloco ideal
leva à reconstrução de blocos maiores

os algoritmos de transferência
determinam a politica quanto à transferência entre a memoria principal e a secundária

os algoritmos de substituição:
determinam qual o bloco de memória física que deve ser retirado para dar lugar a outro

#politicas de transferência
as politicas por transferência podem ser feitas por:
pedido, o sistema operativo ou o processo, determina quando se deve carregar um loco em memória
necessidade, é necessário carregar o bloco para a memória física, pois é necessário aceder a ele
antecipação, através do factor probabilidade o bloco é transferido para a memoria física pois vai ser usado brevemente

a transferência de páginas:
são feitas por necessidade
o processo quando é criado, surgem a inicialização das tabelas de páginas, mas não são colocadas em memória
à medida que um processo vai progredindo, o sistema operativo vai disponibilizar páginas em memoria de forma transparente para o processo

a transferência de segmentos (swapping):
quando o sistema coloca o processo em execução, coloca também em memória os seus segmentos
as transferências de segmentos são feitas por pedido

a substituição de páginas:
a decisão de retirar páginas está relacionado com a sua utilização
idealmente retira-se aquelas que serão necessárias em ultimo lugar
para se ter uma precisão maior pode-se fazer uso de um dos seguintes algoritmos:
FIFO (quando uma página é carregada, vai para o fim da lista, quando se remove, remove-se a que está no inicio, o que pode ser um problema pois pode ser uma que está a ser usada várias vezes)

LRU, last recently used (o tempo a que a página foi acedida, idade da página, significa que está a ser acedida várias vezes)
ainda no LRU:
a página é carregada, o contador fica a zero
quando for acedida, o bit “R” fica a 1
o contador é incrementado, se o bit “R” estiver a zero
o contador passa a zero, se o bit “R” estiver a um
página fica inválida, se o bit “P” atingir o valor máximo, ficando a memória livre

NRU, not recently used (averigua se a pagina foi acedida ou modificada)
ainda no NRU:
quando for acedida, o bit “R” fica a 1
quando for modificada, o bit “M” fica a 1

R e M a 0, sai de memória
R a 0, e M a 1, sai de memória de seguida
R a 1, e M a 0, sai de memória de seguida, se não existir nenhum dos casos anteriores
R a 1, e M a 1, ultima versão a sair nesta ordem

a substituição de segmentos:
normalmente retiram-se segmentos em função do processo a que pertencem, sendo que essa retirada depende:
da importância / prioridade
da sua utilização pelo processador
da sua dimensão (total de segmentos)

O modelo de espaço de trabalho:
é um modelo que está relacionada com a quantidade de páginas que um processo deve ter presente em memória
compensa nunca colocar em memória, mais do que uma determinada percentagem das suas páginas
o espaço criado vai sendo criado à medida que o processo vai decorrendo, sem nunca ultrapassar o valor máximo de trabalho
se atingir o valor máximo, o espaço para outras das suas páginas são retirados a outros processos
se descer a quantidade de páginas para uma valor mínimo, o processo é enviado para memória secundária

Questões:
quais as desvantagens do endereçamento real face ao endereçamento virtual
descreve o mecanismo de tradução de endereço de memória
elabore uma análise comparativa de memoria segmentada e memoria paginada salientando as vantagens e desvantagens de um face ao outro
descreva o conceito de espaço de trabalho e diga como pode ser usado para aumentar o desempenho do seu computador
porque razão o mecanismo de excepções é fundamental para a construção de memória virtual?
como é que se constrói o isolamento entre processos recorrendo à memória segmentada? Em em memória paginada, há alguma diferença significativa?
quais as vantagens de memória segmentada-paginada face à memória segmentada pura e memória paginada pura?
dado este conjunto de páginas e os tempos em que foram acedidos e modificados, diga qual será a primeira a sair de acordo com o algoritmo FIFO/LRU/NRU e porquê?
dada esta tabela de páginas e estas instruções a serem executadas no espaço de endereçamento que lhe corresponde, diga quais irão ser os endereços reais manipulados e se existirá algum comportamento especifico por parte do sistema operativo
dado este processo (código) diga qual acha que será a dimensão (%) do seu espaço de trabalho
dado este cenário de ocupação de memória real em memória segmentada, diga onde irá ser encaixado um novo segmento de tamanho segundo o algoritmo

---

Capítulo: 4 (mecanismos de gestão de memória) – Fundamentos de Sistemas Operativos, José Alves Marques, Paulo Guedes – 3ª edição – Editorial Presença

Os mecanismos de gestão de memória: determinam a organização da memória do computador. são em geral executados pelo hardware de gestão de memória do processador, devidamente programado pelo sistema operativo
Os algoritmos de gestão de memória: são da exclusiva responsabilidade do do sistema operativo. determinam que decisões devem ser tomadas e quando devem ser tomadas, usando os mecanismos de baixo nível para as levar a cabo.

Processo e espaço de endereçamento
o espaço de endereçamento de um processo é o conjunto de posições de memória que um programa executado por esse processo pode referenciar/aceder. a memória divide-se em memória física e memória secundária, os programas só se executam em memória física, sendo a secundária (discos) para guardar a informação persistente

Endereços reais e virtuais
o endereçamento real tem um relação directa com os endereços da memória física do computador. este tipo de endereçamento tem desvantagens:
a dimensão dos programas é limitada pela dimensão da memória física do computador
um programa só pode funcionar nos endereços físicos para onde foi escrito
a multiprogramação fica bastante dificultada

o endereçamento virtual são endereços gerados pelo programa que são convertidos pelo processador e em tempo de execução em endereços físicos. é função do hardware de gestão de memória e do sistema operativo fazer a transferência entre o endereço virtual e o endereço físico. a palavra referenciada pelo endereço virtual pode estar em memória física ou em memoria secundária. se estiver em memoria física a unidade de gestão de memoria traduz automaticamente o endereço virtual em endereço físico e a palavra é a acedida; mas se a palavra estiver em memória secundárias a unidade de gestão de memoria avisa o sistema operativo para este carregar a palavra em memoria física.

Endereçamento real – sistemas monoprogramados
os computadores eram monoprogramados, e tinham endereçamento real. o principal inconveniente do endereçamento real é o tamanho dos programas ser limitado pela dimensão da memória física do computador. para ultrapassar este problema usa-se a técnica da sobreposição (overlay), o programa é divido numa parte residente que está sempre em memoria, e em overlays, que são módulos independentes uns dos outros e que são carregados em memória a pedido do programa.

Endereçamento real – sistemas multiprogramados com partições fixas
para permitir a multiprogramação é necessário que vários programas possam coexistir em memória central
a forma mais simples é dividir a memória do computador em partições, carregando cada programa numa delas.

Endereçamento real – sistemas multiprogramados com partições variáveis
neste caso aloca-se uma zona de memória de dimensão suficiente para colocar o programa.
quando um programa se começar a executar, será alocada uma zona de memória para o colocar, ficando a existir duas participações, aquela onde está o programa em execução e a que compreende o restante da memória

endereçamento virtual
o principal objectivo da memória virtual é dissociar os endereços gerados pelo programa dos endereços físicos acedidos na memória da máquina
o mecanismo de tradução de endereços virtuais em endereços virtuais em endereços reais é efectuado pelo hardware, mais precisamente pela unidade de gestão de memoria do processador
as outras componentes do processar só manipulam os endereços virtuais

endereçamento virtual – segmentação
o objectivo da segmentação é a divisão dos programas em segmentos lógicos que reflictam a sua subdivisão funcional. se um endereço for inválido, o hardware interrompe a tradução do endereço e gera uma excepção que será tratada pelo sistema operativo.

endereçamento virtual – paginação
o principal objectivo da arquitectura de memória paginada é oferecer ao programador um espaço de endereçamento (virtual), linear, em geral bastante maior que a dimensão da memória física da máquina. desta forma o programador não precisa de se preocupar com a gestão de memória quando escreve um programa.

endereçamento virtual – paginação – mecanismos de tradução de endereços
a memória é dividida em blocos do mesmo tamanho, chamados páginas, em que cada página contém o número da página e deslocamento, e o deslocamento indica dentro da página.

Capítulo: 5 (algoritmos de gestão de memória) – Fundamentos de Sistemas Operativos, José Alves Marques, Paulo Guedes – 3ª edição – Editorial Presença

os algoritmos de gestão de memória determinam as decisões tomadas pelo SI, e são utilizados para decidir onde se deve colocar um bloco de programa dada a memória livre, quando se transferir uma página ou segmento de memória secundária para a memória principal e vice-versa e quando não existe mais memória livre que bloco retirar para lá colocar outro mais prioritário.

O sistema operativo e em relação à memória tem que ter em conta:
alocação: onde colocar um bloco na memória
transferência: decidir quando transferir um bloco de memória secundária para memória primária e vice-versa
substituição: quando não existe mais memória livre, qual o bloco a retirar de memória para satisfazer o pedido

Alocação de memória
os algoritmos de alocação de memória, decidem, dada a memória livre, onde colocar um bloco de memória de uma determinada dimensão. o sistema operativo faz uso desses algoritmos para:
na criação e terminação de processos
por extensão do espaço de endereçamento

Alocação de memória – Alocação de páginas
como as páginas são todas do mesmo tamanho, no caso da paginação este algoritmo é trivial: aloca-se qualquer página que esteja livre
as páginas livres são mantidas numa lista, geralmente gerida em FIFO, na alocação retira-se a primeira página da lista, na libertação coloca-se a página no fim da lista

Alocação de memória – Alocação de segmentos
a alocação de segmentos é mais complicada pois é necessário analisar a memória livre para encontrar um bloco desocupado com dimensão suficiente para satisfazer o pedido.  mas tem algumas vantagens:
evita que se gerem fragmentos muito pequenos
os blocos devolvidos ficam naturalmente alinhados
os registos da lista livres precisam de menos bits para guardar o endereço e o comprimento dos blocos

Algoritmos de transferência
os algoritmos de transferência determinam quando um bloco de memória deve ser transferido entre memória secundária e memória central, e essa transferência pode ocorrer quando:
a pedido (request): o programa ou o sistema operativo determinam explicitamente quando se deve carregar o bloco em memória
por necessidade (on demand): o bloco é acedido e gera-se uma falta de página ou segmento, sendo necessário carregá-lo em memória
por antecipação: o bloco é carregado em memória pelo sistema operativo pois este considera fortemente provavelmente que ele venha a ser acedido nos próximo instantes

Algoritmos de transferência – transferência de segmentos (swapping)
em sistemas de memória segmentada, um processo é composto por vários segmentos lógicos: código, dados, pilha e dados do sistema operativo respeitantes ao processo.
um segmento é sempre transferido como um todo entre memória e disco, nunca é transferida apenas parte do segmento
a transferência de segmentos (swapping) permite que de uma forma simples e sem hardware sofisticado, se ofereça um ambiente de multiprogramação.

Algoritmos de transferência – transferência de página
o mecanismo normal de transferência de páginas é por necessidade (on demand): uma página é transferida para memória primária quando se dá uma falta nessa página

Algoritmos de substituição
quando a memória física fica cheia, o sistema operativo tem que retirar um bloco de memória primária (enviar para o disco) para arranjar espaço livre

Algoritmos de substituição – de páginas
quando um processo tenta aceder a uma página que não esteja carregada em memória primária, e não haja páginas livres mas modificadas. as páginas livres podem ser reutilizadas em qualquer momento. as páginas livres mas modificadas têm de ser escritas em disco antes de serem reutilizadas.
dado um conjunto de páginas em memória, a escolha óptima é retirar a que for acedida mais tarde no tempo

Algoritmos de substituição – de páginas, menos usada recentemente (LRU)

Algoritmos de substituição – de páginas, FIFO

Análise comparativa da segmentação e paginação
vantagens segmentação:
adapta-se à estrutura lógica do programa
permite a realização de sistemas simples sobre hardware simples
permite realizar eficientemente as operações que agem sobre um segmento inteiro

desvantagens segmentação:
o programador tem de ter sempre algum conhecimento dos segmentos subjacentes
os algoritmos tornam-se bastante complicados em sistemas mais sofisticados
o tempo de transferência de segmentos entre memória central e disco torna-se incomportável para segmentos muito grandes
a dimensão máxima dos segmentos é limitada

vantagens paginação:
o programador não tem que se preocupar com a gestão de memória
os algoritmos de alocação, substituição e transferência são mais simples e eficientes
o tempo de leitura de uma página de disco é razoavelmente pequeno
a dimensão dos programas é virtualmente ilimitada

desvantagens paginação:
o hardware é mais complexo que o de memória segmentada, não permitindo a realização de máquinas de muito baixo custo
operações sobre segmentos lógicos são mais complexas e menos elegantes, pois têm de ser realizadas sobre um conjunto de páginas
o tratamento das faltas de páginas representa uma sobrecarga adicional de processamento