PublicouRaul Vida Alterado mais de 7 anos atrás
Gerenciamento de memória Memória Virtual Capítulos 8 Operating Systems: Internals and Design Principles W. Stallings IC - UFF
2 Memória Virtual e Paginação
Requisitos referências em um processo são endereços lógicos mapeamento para endereço real durante a execução devido a swap um processo é dividido em páginas não alocadas em MP continuamente tabelas de páginas e mapeamento de endereços dinamicamente permitem a execução do processo IC - UFF
3 Memória Virtual e Paginação
Somente parte do processo é trazido para MP devido aos requisitos princípio da localidade IC - UFF
4 Como funciona? O conjunto de páginas de um processo presentes na MP é chamado de conjunto residente inicialmente, algumas páginas são carregadas a partir da página 0 Quando é necessário um endereço que não está presente na MP uma interrupção é gerada SO coloca processo em estado bloqueado SO faz pedido de E/S para trazer mais página(s)‏ enquanto isso, SO escolhe outro processo para executar IC - UFF
5 e ... Quando a página é trazida para a memória, o primeiro processo (o que ocasionou falta de páginas) passa para a fila dos prontos controlador envia interrupção (evento realizado)‏ Transparência para usuário Memória virtual – mais vantajoso: MP + MS IC - UFF
6 Vantagens desta divisão
Mais processos (seus pedaços!) podem estar na MP maior eficiência pois maior chance de um deles estar em estado pronto Processos podem ser maiores que a MP (tão grandes quanto a MS)‏ limite: tamanho do MS tarefa do SO e hw trazer partes do processo Reduz o tempo de swapping não é toda a imagem que está em MP somente páginas requisitadas são carregadas IC - UFF
7 Thrashing MP contém páginas de diferentes processos
páginas são carregadas, outras são swapped out Possibilidade de enviar para MS uma página de outro processo logo antes desta ser utilizada O processador pode gastar a maior parte do tempo fazendo swapping em vez de processando instruções do usuário Como evitar: tentando adivinhar qual página será mais necessária IC - UFF
8 Princípio da localidade
Só partes do processo serão utilizadas em um dado intervalo de tempo Localidade espacial e temporal Palpites inteligentes podem ser feitos quanto aos pedaços que serão necessários no futuro próximo memória virtual pode funcionar eficientemente IC - UFF
9 Localidade Localidade de referência (P. Denning, 1968):
localidade espacial: se um item é referenciado, itens com endereço próximo tendem a ser referenciados em seguida localidade temporal: se um item é referenciado, ele tenderá a ser referenciado novamente em breve IC - UFF
10 Exemplo de localidade exemplo ( ... )‏ { ... texto
exemplo ( ... )‏ { ... for (i=1; i<N; i++) { a[i] = b[i] + c[i]; b[i] += 2; } dados e pilha texto memória N-1 reservado código do for i a[ ] b[ ] c[ ] IC - UFF
11 Paginação – Memória Virtual
Cada processo tem sua tabela de páginas (TP)‏ TP: mapeamento página x quadro Bit de presença 0 – página não está em MP 1 – está em MP Bit de modificação 0 – página em MP não foi modificada 1 – foi modificada IC - UFF
12 Paginação: endereçamento
outros bits de ctl. P M número do quadro número da página deslocamento endereço virtual linha da tabela de páginas e.g., referenciada, proteção, compartilhamento, desabilita colocação na cache, etc. IC - UFF
13 Paginação: endereçamento
endereço virtual # página deslocam. # quadro deslocam. registrador pont. tab. de páginas + # quadro memória principal tabela de páginas IC - UFF
14 Paginação: exemplo IC - UFF
15 Estrutura da Tabela de Páginas
número de entradas – depende do tamanho do processo onde armazenar? registradores MP MV em dois níveis uma tabela de X entradas cada uma aponta para uma tabela de Y entradas IC - UFF
16 Estrutura da Tabela de Páginas
1 2 ... Y Y = tamanho de uma página 1 2 3 ... X 1 2 ... Y 1 2 ... Y IC - UFF
17 Tabela de páginas em 2 níveis
Second-level page tables Top-level page table IC - UFF
18 Translation Lookaside Buffer (TLB)‏
para acessar MP com paginação e MV são necessários dois acessos à memória acesso a TP acesso ao endereço real Para diminuir o gargalo: TLB cache especial para tabela de páginas TLB contém as entradas da TP mais utilizadas IC - UFF
19 Translation Lookaside Buffer (TLB)‏
Pedido de acesso a endereço lógico: no da pág. no endereço - entrada naTP a TLB é consultada se está na TLB acessa a info de qual frame senão acessa a TP na MP se P == 1 então acessa a info de qual frame traz esta entrada da TP para TLB senão page fault IC - UFF
20 Paginação: TLB endereço virtual # página deslocam. memória secundária
tabela de páginas memória principal # quadro deslocam. IC - UFF
21 Entrada da TLB Procura na TLB: hardware especial
olha todas as entradas em paralelo cache associativa Pergunta: Como funciona a TLB+MV e cache + MP? no da página P M outros bits de ctl. outros bits de ctl. número do quadro IC - UFF
22 Memória associativa: TLB
23 Tamanho da Página é importante para evitar fragmentação interna
o menor possível, mas... muitas páginas por processo  TP longa MV para tabela de páginas pode gerar duas faltas de páginas: de entradas de tabela de páginas da página do processo caso não esteja em MP IC - UFF
24 Tamanho da Página também está relacionado com o tamanho da MP
deve-se evitar falta de páginas atualmente, os próprios programas dos usuários estão mais modulares IC - UFF
25 Memória virtual: suporte de s/w
Políticas: busca onde colocar pedaços na MP que páginas retirar tamanho do conjunto residente política de limpeza controle de carregamento que processo suspender IC - UFF
26 Tamanho do conjunto residente
quantas páginas de um processo devem ser trazidas para MP quanto menos páginas, mais processos estarão em MP grau de swaping out de processo pode ser menor mas mais falta de páginas de um processo também pode ser limitado pelo princípio da localidade IC - UFF
27 Tamanho do conjunto residente
Alocação fixa cada processo recebe um número fixo de quadros em caso de falta de páginas, uma das residentes é trocada Alocação variável número de páginas varia durante a execução do processo a substituição pode englobar páginas de outros processos Adaptativo se muita falta de páginas então aumenta o no de frames/processo, senão diminui pode ser muito custoso gerenciar essa adaptação IC - UFF
28 Escopo da substituição
Local somente páginas do processo são substituídas alocação fixa fácil implementação Global qualquer frame é candidato desempenho melhor, apesar de overhead maior um processo aumenta com número de páginas em MP, outro diminui (ou até processo sai de MP)‏ IC - UFF
29 Escopo de Substituição - Combinações
Alocação fixa, escopo local problema: prever o melhor número de páginas por processo no momento de carga que tal que o número de falta de páginas seja mínimo Alocação variável, escopo global muito adotado parte de um número inicial de frames alocado a um processo Alocação variável, escopo local de tempos em tempos, o número de frames é realocado, mas a substituição é só local IC - UFF
30 Política de troca/substituição
Trata da seleção da página a ser retirada da MP Algumas páginas podem ficar permanentemente em memória: estruturas do núcleo buffers de E/S SO de tempo real IC - UFF
31 Política de troca/substituição
Questões que devem ser consideradas número de quadros/processo escopo local diminui o grau de multiprogramação das páginas candidatas, qual escolher Políticas de substituição ideal: escolher um quadro que contem uma página que não será mais referenciada geralmente baseada em histórico passado IC - UFF
32 Política de substituição - Ótima
Política ótima seleciona a página cujo tempo para o próximo acesso será o mais longo (comparação)‏ menor # de falta de páginas difícil implementação. Como adivinhar IC - UFF
33 Política de substituição - Ótima
Política ótima pág. referenciadas: 2, 3, 2, 1, 5, 2, 4, 5, 3, 2, 5, 2 2 3 2 1 5 2 4 5 3 2 5 2 2 2 3 2 3 1 2 3 2 3 5 2 3 5 4 3 5 4 3 5 2 3 5 2 3 5 2 3 5 4 3 5 IC - UFF
34 Política de substituição - LRU
LRU (Least Recently Used)‏ pelo princípio da localidade deve ser a de menor probabilidade de ser acessada. Implementação: etiqueta de tempo como guardar o tempo? (mais info)‏ IC - UFF
35 Política de substituição - LRU
LRU (Least Recently Used)‏ pág. referenciadas: 2, 3, 2, 1, 5, 2, 4, 5, 3, 2, 5, 2 2 3 2 1 5 2 4 5 3 2 5 2 2 2 3 2 3 1 2 3 2 5 1 2 5 1 2 5 4 2 5 4 3 5 2 3 5 2 3 5 2 3 5 4 IC - UFF
36 Política de substituição – LRU e MRU
tem desempenho ruim quando aplicações que requerem acesso seqüencial: vetores e matrizes variante: most recently used (MRU) IC - UFF
37 Política de substituição - FIFO
frames de um processo considerados como buffer circular ordem de substituição – round robin ponteiro indica a próxima a ser substituída fácil implementação baixo desempenho IC - UFF
38 Política de substituição - FIFO
pág. referenciadas: 2, 3, 2, 1, 5, 2, 4, 5, 3, 2, 5, 2 2 3 2 1 5 2 4 5 3 2 5 2 2 2 3 2 3 1 2 3 5 3 1 2 5 1 2 5 4 3 2 4 3 5 4 2 5 4 3 2 4 3 5 2 IC - UFF
39 Política de substituição
FIFO X LRU grau de dificuldade de implementar (sobrecarga) versus desempenho Relógio noção de tempo e uso bit adicional de controle Desempenho: LRU, Relógio, FIFO IC - UFF
40 Política de substituição - relógio
um bit é associado a cada quadro: bit utilizado (u) quadro de um processo se escopo local, e de todos os processos se escopo global quando uma página é carregada para um determinado quadro, seu bit u é setado: u:=1 a cada referência, u daquele quadro continua setado IC - UFF
41 Política de substituição - relógio
Algoritmo: especificação de um ponteiro indicando o próximo quadro analisado página a ser escolhida: aquela cujo quadro tem u==0 Na procura por um quadro com bit u ==0, reseta os respectivos u's se o ponteiro voltar para o quadro inicial (na análise corrente), todos os respectivos u's ficarão zerados, então escolher este quadro inicial IC - UFF
42 Política de substituição - relógio
1 2 3 4 5 6 7 8 .... N-1 19 45 191 556 13 67 33 222 9 quadro página u next frame 1 2 3 4 5 6 7 8 .... N-1 19 45 191 556 13 67 33 222 9 1 2 3 4 5 6 7 8 .... N-1 19 45 191 556 13 67 33 222 9 IC - UFF quadro selecionado
43 Política de substituição - relógio
pág. referenciadas: 2, 3, 2, 1, 5, 2, 4, 5, 3, 2, 5, 2 2 3 2 1 5 2 4 5 3 2 5 2 2 3 2 2 3 1 2 3 5 3 1 2 5 4 3 2 4 3 2 5 2 5 1 2 5 4 3 2 4 3 2 5 IC - UFF
44 Política de substituição - relógio
mais bit associados: modificado m Algoritmo a partir de next frame percorrer até encontrar quadro com u=0 e m=0 sem resetar os bits u senão encontrar percorrer até encontrar u=0 e m=1, resetando os bits u que estão setados se falhar, volte para (1)  por cauisa de 2, todos os bits analisados terão valor 1 se (3) falhar, volte para 2 dá prioridade aos quadros com páginas não modificadas, depois aquelas que não foram acessadas recentemente IC - UFF
45 ... ... Política do relógio 1 2 3 4 n-1 1 2 3 4 n-1 pág=120 u=1
1 2 3 4 n-1 pág=120 u=1 pág=237 u=0 pág=12 pág=49 pág=50 ... 1 2 3 4 n-1 pág=53 u=1 IC - UFF
46 Política de Limpeza/Atualização
Sob demanda página modificada é escrita em MS somente quando substituída vantagem: rapidez desvantagem: afeta a execução do processo que sofre falta de páginas (espera pela gravação em MS de outra página)‏ IC - UFF
47 Política de Limpeza Pré Limpeza
grava páginas modificadas em MS antes dos frames serem requisitados na substituição (em bandos)‏ número de páginas gravadas a ser especificado vantagens: gravação em conjunto de frames desvantagens: pode não ser escolhidos para substituição pode ser modificada depois da pré-limpeza e antes da substituição (tem que manter consistente) IC - UFF
48 Política de Limpeza Bufferização de Páginas
limpar páginas substituíveis páginas substituídas são associadas a duas listas: modificadas não modificadas modificadas gravadas periodicamente e colocadas na lista de não modificadas frames das páginas não modificadas são candidatas a substituição IC - UFF
49 Política de busca Determina qual página deve ser trazida para MP
O objetivo é minimizar o número de faltas de página Políticas: demanda quando a página for necessária falta de página pré-paginação (Working Set)‏ conjunto de páginas é trazido vantagens e desvantagens? IC - UFF
50 Tratando a falta de páginas
Interrupção do h/w para o núcleo; salva PC e registradores de status Salvamento dos registradores de uso geral; chama SO SO descobre qual página virtual é necessária SO verifica validade do endereço e proteção e consegue um quadro IC - UFF
51 Tratando a falta de páginas
Se quadro foi alterado, salva-o em disco SO busca página do disco Quando página chega: tabela de páginas é atualizada quadro é marcado Processo que causou falta é re-escalonado Registradores são restaurados e execução continua IC - UFF
52 Controle de carga Determina o número de processos residentes em MP
Poucos processos  possibilidade de processador vazio muitos processos  possibilidade de thrashing cada processo tem poucas páginas residentes Como decidir? Algumas medidas .... tempo médio entre as faltas = tempo médio de processamento de uma falta manter a utilização do processador em paginação em 50% IC - UFF
53 Suspensão de processos (swapped out)
Usada para reduzir o nível de multiprogramação o de menor prioridade: política de escalonamento de médio prazo processo causador de falta de páginas conjunto residente necessário ausente de qualquer maneira coloca o processo em MS de qualquer modo último processo ativado maior processo: libera um maior número de quadros menor processo: menos overhead para tornar suspenso IC - UFF
54 Segmentação: suporte de h/w
pode ser dinâmica compartilhamento e proteção Segmentação pura Segmentação com paginação IC - UFF
55 Vantagens de Segmentação
programas com alocação dinâmica de estrutura de dados um segmento pode ser alocado para as estr. de dados SO manipula o aumento e diminuição do segmento IC - UFF
56 Espaço de uma dimensão IC - UFF
57 Memória segmentada IC - UFF
58 Organização uma tabela de segmentos por processo Campos de entrada
bit P: presença ou não em MP bit M: modificado ou não endereço inicial do segmento tamanho do segmento IC - UFF
59 Segmentação: endereçamento
endereço virtual # seg. deslocam. + base + deslocamento registrador pont. tab. segmentos + comp. base memória principal tabela de segmentos IC - UFF
60 Segmentação: endereçamento
comprimento outros bits de ctl. P M número do segmento deslocamento endereço virtual linha da tabela de segmentos base do segmento IC - UFF
61 Paginação x segmentação
62 Segmentação pura IC - UFF Compactação!
63 Paginação + segmentação
para combinar as vantagens dos dois esquemas paginação: evita a fragmentação externa segmentação: mais fácil manipular alocação dinâmica de dados, por exemplo IC - UFF
64 Segmentação com paginação
# quad. desloc. memória principal # seg. # pág. desloc. pont. tab. seg. + + tabela de páginas tabela de segmentos IC - UFF
65 Segmentação com paginação
número do segmento comprimento outros bits de ctl. deslocamento endereço virtual linha da tabela de segmentos base do segmento número da página P M número do quadro linha da tabela de páginas IC - UFF