EA960
Organização de Computadores

Capítulo 3

Tecnologia de Memória Hierárquica.

Sistemas de Memórias

Memória tem papel crítico no desempenho de um sistema computacional:

• recebe dados do mundo externo / para processador
• recebe dados do processador / para mundo externo
• módulo de memória (convencional) não pode acessar mais que uma palavra durante um ciclo de acesso
• ``gargalo'' de von Neumann

Características Tecnológicas de Dispositivos de Memória:

• custo
• SRAM: $400/Mbyte
• DRAM: $50/Mbyte
• Discos magnéticos: $0.50/Mbyte
• Fitas magnéticas: $0.005/Mbyte
• tempo de acesso
• Tempo para ler (escrever) um item de informação da (para a) memória
• definição precisa deste tempo é difícil
• SRAM: 12-25 ns
• DRAM: 70 ns
• Discos magnéticos: 9 ms
• modo de acesso
• acesso aleatório
• acesso a posições arbitrárias ocorre em tempo independente da posição acessada
• exemplo: dispositivos semicondutores de memória
• acesso serial
• acesso ocorre apenas em sequências pré-estabelecidas
• exemplo: fitas magnéticas
• acesso direto (ou semi-aleatório)
• combina características de acesso aleatório e sequencial
• exemplo: discos magnéticos
• alterabilidade
• caracteriza se o processo de escrita de um item de informação é reversível ou não
• reversível: memórias de escrita e leitura
• irreversível: memórias apenas de leitura (ROM)
• exemplos: ROM, PROM, EPROM, cartões perfurados, WORMs
• permanência de armazenamento
• caracteriza se dispositivo de memória é capaz de manter informação sem refreshing
• caracteriza se dispositivo de memória é capaz de manter informação armazenada na ocorrência de falta de energia para o sistema
• tempo de ciclo e taxa de transferência
• tempo mínimo entre dois acessos consecutivos à memória
• pode ser maior que o tempo de acesso
• define a máxima taxa de transferência (banda de passagem da memória)
• características físicas
• tecnologia de integração
• densidade de armazenamento (bits/area ou bits/volume)
• consumo de energia
• confiabilidade

Hierarquia de Memória

Um dos problemas associados ao projeto de sistemas de memória é a latência de memória

• tempo decorrido entre a requisição de um item de dado pelo processador e o efetivo recebimento deste item
• dois fatores afetam latência:

fator tecnológico:

disparidade entre a velocidade de processamento e a velocidade de acesso à memória

fator estrutural:

em sistemas com mais de uma CPU, concorrência de acesso à memória pode atrasar recebimento do item por contenção na memória ou na rede de interconexão

Para atingir boa banda de passagem de memória a custo razoável: memória hierárquica

• objetivo: estabelecer um sistema de memória que aparenta ao usuário ter grande capacidade de armazenamento e alta velocidade de acesso a um custo razoável
• dificuldade para atingir este objetivo: quanto mais rápida for um dispositivo de memória, mais alto será seu custo
• alternativa: estruturação em níveis de memória M₁, M₂, ..., M_ntal que M_i é mais rápida porém menor que M_i+1 .

Propriedades de uma Hierarquia de Memória

Inclusão

• 
• M_n contém todos os itens de dados
• subconjuntos de M_n são copiados para os outros níveis ao longo do processamento
• item em M_i seguramente terá cópias em M_i+1, M_i+2, ..., M_n
• item em M_i+1 não está necessariamente em M_i quando requisitado àquele nível

    item miss: falha de acesso ao item no nível

Coerência

• cópias de um mesmo item devem ser consistentes ao longo de níveis sucessivos da hierarquia de memória
• dois métodos básicos

write-through:

atualização imediata em M_i+1 quando item é modificado em M_i

write-back:

atualização só é realizada em M_i+1quando o item estiver sendo retirado de M_i

Localidade de Referência

• conceito fundamental para o funcionamento adequado da hierarquia de memória
• comportamento de programas no qual referências à memória geradas pela CPU para acesso a instruções ou a dados faz com que estes acessos estejam agrupados em certas regiões ou sequências no tempo ou no espaço
• Formas de localidade:
• localidade temporal
• itens referenciados no passado recente têm maior chance de serem novamente referenciados em um futuro próximo
• exemplo: subrotinas, iterações, variáveis temporárias
• localidade espacial
• tendência em processos de acessar itens cujos endereços estão próximos
• exemplo: operações em arranjos, segmentos de programas
• relacionada: localidade sequencial
• elementos em posições consecutivas da memória têm chance de serem acessados em sequência
• exemplo: instruções de um programa, elementos de um arranjo

• Pelo princípio da localidade, é possível construir sistemas de memória hierárquica de forma eficiente
• processador-memória principal: cache
• memória principal-memória secundária: memória virtual

Memória Virtual

Objetivo:

otimizar o uso da memória principal usando a memória secundária como backup

Aplicação típica:
mapear um grande espaço de endereçamento a uma memória primária fisicamente menor
• exemplo: com 32 bits de endereço, o espaço de endereçamento virtual é de 4 Gbytes -- memórias primárias têm da ordem de dezenas de Mbytes.
Outra aplicação:
multiprogramação
• pode mapear um espaço de endereçamento pequeno a uma memória primária maior
• libera programas do posicionamento físico de suas variáveis

• Espaços de endereçamento:
• espaço físico M: conjunto de endereços da memória principal
• espaço virtual V: conjunto de endereços gerados pelo processador
• Endereços virtuais precisam ser traduzidos em termos de endereços físicos durante a execução de programas

• Mapeamento:

,onde endereço virtual é traduzido por f_t

• Desempenho do sistema de memória virtual depende da eficiência da tradução de endereços
• operação da memória virtual envolve a cooperação do sistema operacional com os recursos do computador
• Mapeamento de endereço virtual para endereço físico requer a manutenção da informação sobre quais dados estão em memória

• Questões básicas envolvidas no projeto de sistemas de memória virtual:
• o tamanho e a natureza dos blocos de informação que são transferidos entre as memórias primária e secundária



uso de blocos devido a características de acesso à memória secundária

• blocos de tamanho fixo: paginação
• blocos de tamanho variável: segmentação
• política de alocação de espaço e de troca de blocos entre memórias primária e secundária
• política de busca de blocos da memória secundária
• por demanda
• antecipada

Paginação

• Informação é mantida para segmentos de tamanho fixo da memória primária e secundária
• páginas da memória secundária são trazidas para os frames de páginas da memória principal

• Mapas de tradução de endereços são mantidos em memória pelo sistema
• Informação em cada entrada: essencialmente um par (página virtual, página física)
• Problema potencial: mapas podem ocupar muito espaço
• Sistema com endereços de 32 bits, páginas de 4 Kbytes: 12 bits para deslocamento na página, 20 bits para identificar página1M entradas na tabela
• ocupa boa parte da memória principal
• outras informações que podem estar contidas na tabela de páginas:
• entrada é válida (página ainda está presente em memória)
• proteção de acesso à página (leitura apenas, leitura e escrita, apenas execução)

• Para contornar o problema do tamanho da tabela de páginas: a tabela em si também pode ser paginada
• Problema: aumenta número de acessos à memória secundária que podem ser necessários para acessar um endereço
• Alternativa: manter um cache privativo da tabela de páginas para as entradas referenciadas mais recentemente
• TLB (Translation Lookaside Buffer)

Mapeamento em dois níveis:

• endereço da página virtual dividido em duas partes
• primeiro nível: índice para a tabela de páginas
• segundo nível: índice para memória primária
• No exemplo de endereço de 32 bits com 12 bits de deslocamento (páginas de 4 Kbytes):
• dividindo o número da página em duas partes de 10 bits cada, a tabela de cada nível tem 1K entradas -- o primeiro nível sempre mantido em memória, o segundo nível pelo menos uma página da tabela em memória

Segmentação

Objetivo:

melhorar aspecto de localidade de referência em sistemas de memória virtual

• em um sistema paginado, os itens que são transferidos dentro de uma unidade de acesso (página) não estão necessariamente relacionados de forma lógica
• itens que não serão utilizados podem estar sendo trazidos
• possível desperdício de espaço em memória e de banda de passagem

Mecanismo:

agrupar itens relacionados logicamente em unidades de acesso (segmentos) de tamanho variável

• unidades de acesso mais próximas da visão usuário (programas, dados)
• segmentos de uso comum podem ser compartilhados
• memória virtual segmentada tem gerenciamento mais complexo
• entrada na tabela de segmentos tem que manter informação sobre comprimento do segmento
• alocação de um segmento à memória deve gerenciar problema de fragmentação externa

• Endereços em memória segmentadas são bidimensionais
• em sistema paginado, quando um valor de deslocamento é incrementado além de seu valor máximo um endereço na página seguinte é gerado   espaço de endereçamento linear
• em sistema segmentado, uma condição de tentativa de acesso fora de limites é detectada

• Compartilhamento de segmentos -- duas possibilidades
• O processo que for usar o segmento compartilhado tem que conhecer o endereço virtual alocado para o segmento -- uma única tabela de segmentos é mantida
• O processo que for usar o segmento compartilhado pode acessá-lo através de seu índice particular -- uma tabela de segmentos para cada processo
• endereço do início da tabela de segmentos mantido em um registrador base da tabela de segmentos

Esquema Combinado (Segmentação Paginada)

• Esquema usualmente adotado combina as características de paginação e segmentação
• Memória é organizada em segmentos
• Cada segmento é particionado em páginas de tamanho fixo
• Endereço virtual é dividido em três partes:
• número de segmento
• número da página
• deslocamento na página

• Tamanho da página -- dois fatores devem ser considerados
• reduzir o problema de fragmentação
• otimizar acesso à memória secundária

Reduzir fragmentação em sistema de segmentos paginados:

Sejam z e s os tamanhos de uma página e de um segmento em palavras, respectivamente. O número de páginas em um segmento é dado por

O espaço desperdiçado por fragmentação interna (não utilizado na última página) é

e o espaço ocupado pela tabela de páginas do segmento é

onde c é uma constante expressando o número de palavras usado por entrada na tabela de páginas.

O espaço gasto em memória por segmento é

O valor médio para esta função é dado por

onde    é o tamanho médio de segmento.

Deseja-se minimizar este espaço gasto, portanto

de onde o tamanho ideal de página

Por exemplo, para c = 2

Otimizar acesso à memória secundária

• Memória secundária é acessada em unidades de tamanho fixo (blocos, setores)
• para reduzir número de acessos, tamanho da página deve ser um múltiplo inteiro do tamanho de um bloco
• dimensão de blocos variam tipicamente de 512 a 8K bytes

Exemplo: Paginação e segmentação no 486

• Dois modos de operação:
• real: endereçamento até tamanho máximo de 1 Mbyte
• protegido: memória virtual
• paginação pura
• segmentação pura
• paginação segmentada
• endereçamento físico
• número de segmento: 16 bits
• tamanho do segmento: de 1 byte a 4 Gbytes
• Máximo tamanho da memória física é 4 Gbytes
• espaço total de endereçamento: 64 Tbytes
• o endereço base de um segmento é adicionado ao deslocamento de 32 bits para gerar um endereço linear
• mecanismo de paginação é opcional
• ativado ou desativado por software
• opera sobre o endereço linear
• TLB: 32 entradas
• Tamanho da página: 4 Kbytes
• Diretório de tabela de páginas (primeiro nível): 1024 entradas (4 Kbytes)
• Tabela de páginas (segundo nível): 1024 entradas (4 Kbytes)
• O mecanismo de paginação pode ser desabilitado, trabalhando-se então com um mecanismo de segmentação pura. O mecanismo de segmentação não pode ser desabilitado da mesma maneira, mas a paginação pura pode ser emulada ao se trabalhar com um único segmento de tamanho 4 Gbytes.

Política de Troca de Páginas

Objetivo:

definir estratégia para seleção de página a ser substituída na memória de forma a minimizar o número de page faults

• Na ocorrência de um ausência de página referenciada em um instante de tempo t, uma das seguintes políticas poderia ser adotada para selecionar a página a ser substituída caso a memória já esteja completamente ocupada:
• LRU (Least recently used): substitui a página na memória cuja última referência é a mais antiga
• OPT (Optimal): substitui a página na memória cuja a próxima referência está mais distante no tempo
• algoritmo não realizável, pois requer conhecimento do futuro
• usado apenas como algoritmo de comparação
• FIFO (First-in, first-out): substitui a página mais antiga na memória
• LFU (Least frequently used): substitui a página na memória cujo contador de referências tem o valor mais baixo
• FIFO Circular (ou Algoritmo do relógio): mantém páginas em uma fila circular. Se a página apontada para substituição (estratégia FIFO) foi referenciada recentemente (bit de referência setado), o bit de referência é zerado e o apontador move para a página seguinte. A primeira página encontrada com o bit de referência zerado é selecionada para substituição
• RAND: página selecionada para substituição é escolhida aleatoriamente

• Primeiros sistemas implementando memória virtual analisaram estas diversas possibilidades
• Em geral, LRU predizia o futuro satisfatoriamente
• Sob condições de uso intenso, estes sistemas entravam em períodos de instabilidade
• Thrashing: página substituída da memória tem de ser recuperada logo a seguir
• perde-se mais tempo em gerenciamento da memória virtual que em trabalho útil
• tráfego intenso de páginas entre memória principal e secundária

• Solução: conceito de conjunto de trabalho (working set)
• conjunto de páginas de trabalho de um processo
• se um processo tem este conjunto de páginas em memória, a taxa de ausência de páginas requisitadas será muito baixa
• Combinação de todos os conjuntos de trabalhos de processos ativos não deve exceder a capacidade total da memória
• Cálculo dinâmico do conjunto de trabalho
•    no tempo t para janela   contém apenas as páginas que foram referenciadas nos últimos    segundos anteriores a t
• Possível estratégia de gerenciamento:
1. Quando ocorre uma ausência de página requisitada, acrescente a nova página ao conjunto de trabalho
2. Do conjunto de páginas não referenciadas nos    segundos imediatamente anteriores à requisição, selecione uma página por LRU e a descarte. Caso todas as páginas do conjunto de trabalho tenham sido referenciadas no período, mantenha-as todas -- o conjunto de trabalho cresce
3. Se duas ou mais páginas do conjunto de trabalho não foram referenciadas na janela referente ao conjunto de trabalho, selecione duas páginas por LRU e as descarte
• tamanho da janela    deve ser determinado experimentalmente

Regra de Busca de Páginas

• Quando que uma página deve ser trazida da memória secundária para a memória principal?
• paginação por demanda: quando a página é referenciada por um processo
• pré-paginação: carrega a página antes dela ser referenciada baseado em estimativas de acessos futuros a páginas
• Em programas arbitrários, é difícil prever acessos futuros a páginas, e paginação por demanda é usualmente adotada
• Dependendo das características do processo, pré-paginação pode reduzir sensivelmente a sobrecarga de transferência de páginas