Unidade 8: Gerenciamento de Memória
•
•
•
•
•
•
•
Introdução
Espaço de endereçamento lógico e físico
Swapping
Alocação contínua
Paginação
Segmentação
Segmentação usando Paginação (gambiarra)
Operating System Concepts
8.1
Silberschatz and Galvin1999
Introdução
•
•
•
O programa precisa ser colocado em memória e asociado a um
processo para que possa ser executado.
File de entrada – coleção de processos em disco qua estão
esperando para ser colocados em memória para execução.
Programas passam por várias etapas antes de serem
executadas.
Operating System Concepts
8.2
Silberschatz and Galvin1999
Link-edição
de instruções e Dados na Memória
Link-edição de endereços de instruções e dados pode ser feito
em três situações diferentes:
•
•
•
Em tempo de compilação: Se a alocação da memória é
conhecida antecipadamente é possível gerar código absoluto; o
código deve ser recompilado se o endereço de início muda.
Em tempo de carregamento: código relocalizável (relocatable)
tem que ser gerado se a localidade no momento da execução
não é conhecida no momento da compilação.
Em tempo de execução: Link-edição é adiada para o momento
de execução. Suporte de hardware é preciso para o
mapeamento (por exemplo GDT do Pentium).
Operating System Concepts
8.3
Silberschatz and Galvin1999
Carregamento dinâmico
•
•
•
•
Uma rotina é carregada somente quando chamada
Melhor aproveitamento do espaço de memória física; uma rotina
inútil nunca é carregada.
Carregamento dinâmico é útil quando grandes quantidades de
código são necessárias para tratar casos que raramente ocorrem.
Suporte do sistema operacional é desejável mas não
indispensável (pode ser implementado até a nível do usuário).
Operating System Concepts
8.4
Silberschatz and Galvin1999
Carregamento dinâmico
•
•
•
•
Link-edição é adiada para o momento da execução.
Pequenos pedaços de código (stub) é usado para localizar a
rotina da biblioteca apropriada.
Quando chamado o stub carrega a rotina e substitui o endereço
na instrução a qual o chamou pelo endereço da rotina carregada
e executa a rotina.
O sistema operacional é necessário para verificar se a rotina já
tinha sido carregada por outro processo.
Operating System Concepts
8.5
Silberschatz and Galvin1999
Overlays
•
•
•
Mantém em memória somente aquelas instruções que são
necessários naquele momento.
Necessário quando o processo é maior que a quantidade de
memória alocada para ele.
Pode ser implementado a nível de usuário. Não precisa de
suporte específico do sistema operacional, mas o projeto da
estrutura de overlay é complicado.
Operating System Concepts
8.6
Silberschatz and Galvin1999
Espaço de endereçamento lógico e físico
•
O conceito de um espaço de endereçamento lógico que é
mapeado para um espaço de endereçamento físico é
fundamental para um gerenciamento de memória decente.
– Endereço lógico – usado nas instruções de máquina;
também chamado endereço virtual ou endereço linear.
– Endereço físico – endereço que aparece no barramento
entre CPU e memória principal.
Operating System Concepts
8.7
Silberschatz and Galvin1999
Unidade de Gerenciamento de memória (MMU)
•
•
Um circuito em hardware que mapeia endereços virtuais para
endereços físicos.
O programa do usuário trabalha com endereços lógicos - ele
nunca enxerga endereços físicos.
Operating System Concepts
8.8
Silberschatz and Galvin1999
Swapping
•
Um processo pode ser tirado temporariamente da memória para
ser colocado num armazenamento auxiliar, para mais tarde ser
recolocado para a memória.
•
Arazenamento auxiliar – disco rápido com capacidade suficiente
para manter cópias de todas as imagens de memória para todos
os usuários e possibilitar acesso direto a essas imagens.
•
Roll out, roll in – variante de swapping usada para algoritmos de
scheduling baseadas em prioridade – processo de baixa
prioridade é tirado para que um processo de alta prioridade possa
ser executado.
•
•
A maior parte do tempo de swap é tempo de transferência,
proporcional a quantidade de memória tirada e colocada.
Versões modificadas de swapping podem ser enontadas em
vários sistemas, por exemplo UNIX e Microsoft Windows.
Operating System Concepts
8.9
Silberschatz and Galvin1999
Schematic View of Swapping
Operating System Concepts
8.10
Silberschatz and Galvin1999
Allocação
•
A memória principal é muitas vezes dividida em dois partes:
– A parte residente (permanente) do sistema operacional,
normalmente nos endereços baixos de memória física, junto
com tabelas de interrupções e segmentos (IDT, GDT, etc.)
– Processos de usuários em endereços de memória física
mais altas.
Operating System Concepts
8.11
Silberschatz and Galvin1999
Allocação (Cont.)
•
Alocação em partes múltiplas
– Buraco – bloco de memória disponível; buracos de
tamanhos variados são espalhadas as memória.
– Quando chega um processo ele recebe memória de um
buraco suficientemente grande para que ele caiba.
– O sistema operacional mantém informações sobre:
a) partições alocadas
b) buracos
OS
OS
OS
OS
process 5
process 5
process 5
process 5
process 9
process 9
process 8
process 2
Operating System Concepts
process 10
process 2
process 2
8.12
process 2
Silberschatz and Galvin1999
O problema da alocação dinâmica
Como satisfazer uma requisição de um tamanho de n bytes a partir de uma
lista de buracos?
•
•
•
First-fit: Aloque o primeiro buraco que é suficientemente
grande.
Best-fit: Aloque o menor buraco que é suficientemente grande.
Toda a lista de buracos precisa ser pesquisada (se ela não é
ordenada). Resulta no menor buraco residual possível.
Worst-fit: Aloque o buraco maior; também precisa pesquisar
toda a lista. Deixa o maior buraco residual.
First-fit e best-fit são melhores em termos de velocidade e
utilização de memória.
Operating System Concepts
8.13
Silberschatz and Galvin1999
Fragmentação
•
Fragmentação externa – existe espaço em memória para
satisfazer uma determinada requisição, mas o espaço é
distribuído em vários buracos.
•
Fragmentação interna – memória alocada pode ser ligeiramente
maior do que a memória requisitada; a memória restante não é
usada. Ocorre quando partições tem tamanho fixo.
•
Reduzir fragmentação externa fazendo compactação
– desloca conteúdos da memória de forma a juntar todos os
buracos pequenos num só buraco grande.
– Compactação é possível somente se a relocação é dinâmica
e é feita em tempo de execução.
– Problema de entrada/saída (DMA)
 não move processo na memória quando ele está
fazendo uma operação de entrada/saída
 entrada/saída somente com buffers do S.O.
Operating System Concepts
8.14
Silberschatz and Galvin1999
Paginação
•
•
•
•
•
•
•
O espaço de endereçamento físico é particionado. Um processo
recebe partições de memória física na medida que eles se tornam
disponíveis. O mapeamento entre endereços lógicos e físicos
apresenta ao processo um espaço de endereçamento lógico sem
particionamento (contínuo).
Divide a memória física em blocos de tamanho fixo chamado
frames. (tamanho é potencia de 2, entre 512 bytes e 8192 bytes).
Divide memória lógica em blocos do mesmo tamanho chamadas
páginas.
Mantenha registro dos frames livres.
Para rodar um programa de n páginas, procure n frames livres e
carregue o programa.
Tabela de paginação.
Fragmentação interna.
Operating System Concepts
8.15
Silberschatz and Galvin1999
Address Translation Scheme
•
Address generated by CPU is divided into:
– Page number (p) – used as an index into a page table which
contains base address of each page in physical memory.
– Page offset (d) – combined with base address to define the
physical memory address that is sent to the memory unit.
Operating System Concepts
8.16
Silberschatz and Galvin1999
Address Translation Architecture
Operating System Concepts
8.17
Silberschatz and Galvin1999
Paging Example
Operating System Concepts
8.18
Silberschatz and Galvin1999
Implementation of Page Table
•
•
•
•
•
Page table is kept in main memory.
Page-table base register (PTBR) points to the page table.
Page-table length register (PRLR) indicates size of the page
table.
In this scheme every data/instruction access requires two memory
accesses. One for the page table and one for the data/instruction.
The two memory access problem can be solved by the use of a
special fast-lookup hardware cache called associative registers or
translation look-aside buffers (TLBs)
Operating System Concepts
8.19
Silberschatz and Galvin1999
Memória associativa
•
Memórias associativas implementam busca em paralelo em
hardware
Page #
Frame #
– dado o número de página, encontra o número do frame
Operating System Concepts
8.20
Silberschatz and Galvin1999
Tempo de acesso médio efetivo
•
•
•
•
Busca associativa =  unidades de tempo
Suponha ciclo de memória principal de 1 unidade de tempo
taxa de acerto  – porcentagem de vezes que um numero de
pagina é encontrado no registro associativo. Esta razão é
relacionada a capacidade da memória associativa.
Tempo de acesso médio efetivo (EAT)
EAT = (1 + )  + (2 + )(1 – )
=2+–
Operating System Concepts
8.21
Silberschatz and Galvin1999
Proteção de memória com paginação
•
Bit Presente em cada entrada da tabela de página:
– ‘1’ indica que pagina está bom .
– ‘0’ indica que está fora.
Operating System Concepts
8.22
Silberschatz and Galvin1999
Two-Level Page-Table Scheme
Operating System Concepts
8.23
Silberschatz and Galvin1999
Two-Level Paging Example
•
•
•
A logical address (on 32-bit machine with 4K page size) is divided
into:
– a page number consisting of 20 bits.
– a page offset consisting of 12 bits.
Since the page table is paged, the page number is further divided
into:
– a 10-bit page number.
– a 10-bit page offset.
Thus, a logical address is as follows:
page number page offset
pi
p2
d
10
10
12
where pi is an index into the outer page table, and p2 is the
displacement within the page of the outer page table.
Operating System Concepts
8.24
Silberschatz and Galvin1999
Address-Translation Scheme
•
Address-translation scheme for a two-level 32-bit paging
architecture
Operating System Concepts
8.25
Silberschatz and Galvin1999
Multilevel Paging and Performance
•
•
•
Since each level is stored as a separate table in memory,
covering a logical address to a physical one may take four
memory accesses.
Even though time needed for one memory access is quintupled,
caching permits performance to remain reasonable.
Cache hit rate of 98 percent yields:
effective access time = 0.98 x 120 + 0.02 x 520
= 128 nanoseconds.
which is only a 28 percent slowdown in memory access time.
Operating System Concepts
8.26
Silberschatz and Galvin1999
Inverted Page Table
•
•
•
•
One entry for each real page of memory.
Entry consists of the virtual address of the page stored in that real
memory location, with information about the process that owns
that page.
Decreases memory needed to store each page table, but
increases time needed to search the table when a page reference
occurs.
Use hash table to limit the search to one — or at most a few —
page-table entries.
Operating System Concepts
8.27
Silberschatz and Galvin1999
Inverted Page Table Architecture
Operating System Concepts
8.28
Silberschatz and Galvin1999
Shared Pages
•
•
Shared code
– One copy of read-only (reentrant) code shared among
processes (i.e., text editors, compilers, window systems).
– Shared code must appear in same location in the logical
address space of all processes.
Private code and data
– Each process keeps a separate copy of the code and data.
– The pages for the private code and data can appear
anywhere in the logical address space.
Operating System Concepts
8.29
Silberschatz and Galvin1999
Shared Pages Example
Operating System Concepts
8.30
Silberschatz and Galvin1999
Segmentation
•
•
Memory-management scheme that supports user view of
memory.
A program is a collection of segments. A segment is a logical unit
such as:
main program,
procedure,
function,
local variables, global variables,
common block,
stack,
symbol table, arrays
Operating System Concepts
8.31
Silberschatz and Galvin1999
Logical View of Segmentation
1
4
1
2
3
2
4
3
user space
Operating System Concepts
physical memory space
8.32
Silberschatz and Galvin1999
Segmentation Architecture
•
Logical address consists of a two tuple:
<segment-number, offset>,
•
Segment table – maps two-dimensional physical addresses; each
table entry has:
– base – contains the starting physical address where the
segments reside in memory.
– limit – specifies the length of the segment.
•
Segment-table base register (STBR) points to the segment table’s
location in memory.
•
Segment-table length register (STLR) indicates number of
segments used by a program;
segment number s is legal if s < STLR.
Operating System Concepts
8.33
Silberschatz and Galvin1999
Segmentation Architecture (Cont.)
•
•
•
Relocation.
– dynamic
– by segment table
Sharing.
– shared segments
– same segment number
Allocation.
– first fit/best fit
– external fragmentation
Operating System Concepts
8.34
Silberschatz and Galvin1999
Segmentation Architecture (Cont.)
•
•
•
•
Protection. With each entry in segment table associate:
– validation bit = 0  illegal segment
– read/write/execute privileges
Protection bits associated with segments; code sharing occurs at
segment level.
Since segments vary in length, memory allocation is a dynamic
storage-allocation problem.
A segmentation example is shown in the following diagram
Operating System Concepts
8.35
Silberschatz and Galvin1999
Sharing of segments
Operating System Concepts
8.36
Silberschatz and Galvin1999
Segmentation with Paging – MULTICS
•
•
The MULTICS system solved problems of external fragmentation
and lengthy search times by paging the segments.
Solution differs from pure segmentation in that the segment-table
entry contains not the base address of the segment, but rather the
base address of a page table for this segment.
Operating System Concepts
8.37
Silberschatz and Galvin1999
MULTICS Address Translation Scheme
Operating System Concepts
8.38
Silberschatz and Galvin1999
Segmentation with Paging – Intel 386
•
As shown in the following diagram, the Intel 386 uses
segmentation with paging for memory management with a twolevel paging scheme.
Operating System Concepts
8.39
Silberschatz and Galvin1999
Intel 30386 address translation
Operating System Concepts
8.40
Silberschatz and Galvin1999
Comparing Memory-Management Strategies
•
•
•
•
•
•
•
Hardware support
Performance
Fragmentation
Relocation
Swapping
Sharing
Protection
Operating System Concepts
8.41
Silberschatz and Galvin1999