Lista Resolvida-2023-2

Ex1: Memória virtual Ex2: Paginação 1 Considere um sistema operacional que trabalha com paginação simples. As páginas são de 1 KB. O endereço lógico é formado por 16 bits. O endereço físico é formado por 20 bits. Qual o tamanho do: 1. Espaço do endereçamento lógico (maior programa possível)? 2. Espaço do endereçamento físico (memória principal)? 3. Entrada da tabela de páginas, sem considerar bits auxiliares? 4. Tabela de páginas (número de entradas necessárias no pior caso)? 2 Considere a seguinte tabela de segmentos: Segmento Base Limite 000 0000111011011 1001011000 001 100011111100 0000001110 010 000001010110 0001100100 011 010100101111 1001000000 100 011110100000 0001100000 Quais os endereços físicos para os seguintes endereços lógicos? 1. 000001101011110 2. 001000000010010 3. 010000111110100 4. 011000110010000 5. 100000011100000 3 Em um sistema usando segmentação paginada, o espaço de endereçamento lógico de cada processo consiste de no máximo 16 segmentos, cada um deles podendo ter até 64 KB de tamanho. As páginas físicas são de 512 bytes. Diga quantos bits são necessários para especificar cada uma das grandezas abaixo, mostrando os cálculos de origem de cada número. 1. Número do segmento 2. Número de uma página lógica dentro do segmento 3. Deslocamento dentro de um página 4. Endereço lógico completo Memória Principal Questão 1 Endereços Lógicos: São gerenciados pelo sistema operacional, que mapeia esses endereços para endereços físicos. Esse processo de mapeamento é muitas vezes realizado através de técnicas como paginação ou segmentação, permitindo que múltiplos processos compartilhem a memória de forma eficiente e segura. Endereços Físicos: São diretamente acessados pelo hardware. O mapeamento de endereços lógicos para físicos é transparente para o programa em execução. Isso significa que um programa não precisa saber onde seus dados estão fisicamente armazenados na memória. Questão 2 Os tamanhos de páginas em sistemas de computação são sempre potências de 2 devido a várias razões técnicas e práticas: Simplificação de Cálculos de Endereçamento: Ao usar tamanhos de página que são potências de 2, o cálculo de endereços lógicos para endereços físicos torna-se mais simples. Isso é especialmente útil em operações de mapeamento de páginas e cálculo de offsets dentro das páginas. Em termos práticos, isto permite o uso de operações de deslocamento binário e mascaramento de bits, que são muito mais eficientes do que operações aritméticas complexas. Alocação Eficiente de Memória: Com tamanhos de página sendo potências de 2, a alocação e o gerenciamento de memória tornam-se mais eficientes. Isso ocorre porque a memória de computadores modernos é organizada de maneira a facilitar o acesso e a divisão em blocos de tamanhos que são potências de 2, mantendo a compatibilidade e eficiência com a arquitetura de hardware. Compatibilidade com a Arquitetura de Hardware: A maioria dos sistemas de computador usa arquitetura binária, onde todas as dimensões de memória (como endereços e dados) são expressas em potências de 2. Manter tamanhos de página que também são potências de 2 garante uma melhor compatibilidade e aproveitamento dessa arquitetura. Redução de Fragmentação: O uso de tamanhos de páginas que são potências de 2 ajuda a minimizar a fragmentação da memória. Como os blocos de memória e as páginas têm tamanhos que se encaixam perfeitamente em potências de 2, a probabilidade de haver espaços não utilizados ou mal aproveitados dentro da memória é reduzida. Questão 3 a) O espaço de endereços lógicos tem 64 páginas, cada uma com 1024 palavras.Primeiro, determinamos quantos bits são necessários para indexar as páginas. Como há 64 páginas, precisamos de log2(64)bits. 64 = 26 então são necessários 6 bits para indexar as páginas.Em seguida, determinamos quantos bits são necessários para indexar as palavras dentro de uma página. Com 1024 palavras por página, precisamos de log2(1024) bits. 1024 = 210 , então são necessários 10 bits para indexar as palavras dentro de uma página.Somando, o endereço lógico precisa de 6 + 10 =16 bits. b) A memória física tem 32 quadros, cada um do tamanho de uma página (1024 palavras) Para indexar os quadros, precisamos de log2(32) bits. 32 = 25 então são necessários 5 bits para indexar os quadros. Como o tamanho de cada quadro é o mesmo das páginas (1024 palavras), ainda precisamos de 10 bits para indexar as palavras dentro de um quadro. Somando, o endereço físico precisa de 5+10=15 bits. Questão 4 Um mecanismo é o compartilhamento de memória. Uma mandeira de implementar isso seria através do mapeamento de mémória compartilhada. O sistema operacional fornece uma funcionalidade chamada mapeamento de memória compartilhada. Neste método, um segmento de memória é criado e pode ser mapeado para o espaço de endereços de dois ou mais processos. Este segmento compartilhado pode ser usado para comunicação interprocessos ou para compartilhar dados. Cada processo tem um ponteiro ou referência para esse segmento compartilhado em seu próprio espaço de endereços, mas a memória física subjacente é a mesma para todos os processos. Questão 5 Fragmentação Interna: Ocorre quando há espaço não utilizado dentro de blocos de memória alocados. Isso acontece geralmente em sistemas que utilizam alocação de memória baseada em blocos ou páginas de tamanho fixo. Exemplo: Se um processo requer 1035 bytes de memória e o sistema aloca memória em blocos de 1024 bytes (ou 1 KB), ele terá que alocar dois blocos (2048 bytes no total) para atender a essa demanda. Isso deixa 1013 bytes não utilizados dentro do segundo bloco. Este espaço não utilizado dentro do bloco alocado representa a fragmentação interna. Fragmentação Externa: Ocorre quando há espaço livre suficiente na memória para atender a uma solicitação de alocação, mas esse espaço está dividido em pequenos blocos dispersos, impedindo a alocação contínua de memória. Exemplo: Suponha que um sistema tenha 5 MB de memória livre, mas essa memória livre esteja espalhada em pequenos blocos de 100 KB cada, dispersos por toda a memória. Se um processo solicitar 1 MB de memória contígua, essa solicitação não poderá ser atendida, mesmo havendo memória livre suficiente no total, porque não existe um único bloco de 1 MB disponível. Isso é fragmentação externa. Questão 6 a) First-fit: Processo de 212 KB: Vai para a partição de 500 KB (pois é a primeira que pode acomodá-lo). Processo de 417 KB: Vai para a partição de 600 KB (a próxima partição que pode acomodá-lo). Processo de 112 KB: Vai para a partição de 300 KB (primeira partição disponível após as alocações anteriores). Processo de 426 KB: Não pode ser alocado, pois não há partições disponíveis suficientemente grandes. Best-fit. Processo de 212 KB: Vai para a partição de 300 KB (é a menor que pode acomodá-lo). Processo de 417 KB: Vai para a partição de 500 KB (a menor disponível para ele). Processo de 112 KB: Vai para a partição de 200 KB (a menor disponível para ele). Processo de 426 KB: Vai para a partição de 600 KB (a única que pode acomodá-lo). Worst-fit: Aloca cada processo na maior partição disponível. Processo de 212 KB: Vai para a partição de 600 KB (a maior partição disponível). Processo de 417 KB: Vai para a partição de 500 KB (a próxima maior partição). Processo de 112 KB: Vai para a partição de 300 KB (a maior restante disponível). Processo de 426 KB: Não pode ser alocado, pois não há partições disponíveis suficientemente grandes. b) A eficiência do uso da memória pode ser avaliada com base na quantidade de memória desperdiçada e na fragmentação externa resultante após a alocação dos processos. O algoritmo best-fit tende a deixar a menor quantidade de espaço não utilizado porque sempre escolhe a menor partição disponível em que um processo cabe, minimizando assim a fragmentação externa. No entanto, ele pode aumentar a fragmentação interna se houver uma grande diferença entre o tamanho da partição e o do processo. Para determinar com precisão qual algoritmo é mais eficiente com esses processos e partições específicas, precisaríamos calcular o espaço não utilizado (fragmentação) após as alocações em cada método. Vamos calcular isso. Após a alocação de memória pelos três algoritmos, temos os seguintes espaços não utilizados: First-fit: Deixa 959 KB de memória não utilizada. Best-fit: Deixa 533 KB de memória não utilizada, o que é o menor desperdício entre os três algoritmos. Worst-fit: Também deixa 959 KB de memória não utilizada. Questao 7 Alocação de Memória Contígua: a. Fragmentação Externa: Este método é suscetível a uma alta fragmentação externa. Como os processos são alocados em blocos contínuos de memória, espaços livres dispersos podem surgir com o tempo, dificultando a alocação de memória para novos processos, mesmo quando há memória livre suficiente. b. Fragmentação Interna: Geralmente, há menos fragmentação interna, pois o espaço de memória alocado é geralmente um bom ajuste para o tamanho do processo. No entanto, pode ocorrer alguma fragmentação interna se o tamanho do processo não for exatamente um múltiplo do tamanho de alocação. c. Capacidade de Compartilhar Código: A compartilhação de código é mais complicada, pois cada processo precisa ter seu próprio espaço contíguo de memória, o que pode limitar a eficiência do compartilhamento de código comum, como bibliotecas. Segmentação Pura: a. Fragmentação Externa: A segmentação pode reduzir a fragmentação externa em comparação com a alocação contígua, pois permite que a memória seja alocada de forma mais flexível. No entanto, ainda pode ocorrer fragmentação externa, especialmente se muitos segmentos de tamanhos variados forem alocados e desalocados frequentemente. b. Fragmentação Interna: A fragmentação interna é minimizada, pois cada segmento é alocado exatamente com o tamanho necessário para o conteúdo que ele armazena. c. Capacidade de Compartilhar Código: A segmentação facilita o compartilhamento de código, pois diferentes processos podem ter segmentos que apontam para o mesmo espaço de memória física. Isso é útil para compartilhar bibliotecas comuns entre vários processos. Paginação Pura: a. Fragmentação Externa: A paginação praticamente elimina a fragmentação externa, pois as páginas são alocadas em espaços de memória que não precisam ser contíguos. Isso permite uma utilização mais eficiente da memória disponível. b. Fragmentação Interna: Existe alguma fragmentação interna, que ocorre quando o tamanho do processo não é um múltiplo exato do tamanho da página, deixando um espaço não utilizado na última página. c. Capacidade de Compartilhar Código: A paginação é extremamente eficiente para compartilhar código, pois páginas específicas podem ser mapeadas para vários processos. Isso é frequentemente usado para compartilhar bibliotecas de código e para implementar memória virtual. Questão 8 Isso é devido a vários mecanismos de proteção e isolamento implementados pelo sistema operacional e pelo hardware. Mecanismos como espaço de endereçamento isolado, mapeamento de páginas e proteção de hardware garantem a segurança e integridade tanto dos processos individuais quanto do sistema como um todo Questão 9 a) Endereço 2375: Número da Página: 2 Deslocamento: 327 b) Endereço 19366: Número da Página: 18 Deslocamento: 934 c) Endereço 30000: Número da Página: 29 Deslocamento: 304 d) Endereço 256: Número da Página: 0 (primeira página) Deslocamento: 256 e) Endereço 16385: Número da Página: 16 Deslocamento: 1 Questão 10 A finalidade principal da paginação das tabelas de página, ou paginação multinível, é gerenciar de forma mais eficiente e econômica o espaço de endereçamento de memória em sistemas de computação. Esta técnica ajuda a reduzir o uso de memória para as tabelas de páginas, especialmente em sistemas com grandes espaços de endereçamento, como os de 64 bits. Ao dividir a tabela de páginas em níveis menores, apenas as partes necessárias da tabela são mantidas na memória principal, economizando espaço e melhorando a eficiência de acesso à memória. Isso permite um gerenciamento mais flexível e escalável do espaço de endereçamento, otimizando o uso dos recursos de memória do sistema. Questão 11 a) Existem aproximadamente 1.048.576 entradas. Isso se deve ao fato de que, com um endereço lógico de 32 bits e um tamanho de página de 4 KB, o sistema pode endereçar 232 bytes no total, resultando neste número de páginas e portanto, entradas na tabela de páginas. b) Existem aproximadamente 131.072 entradas. Neste caso, o número de entradas é determinado pela quantidade de memória física (512 MB) dividida pelo tamanho da página (4 KB), resultando neste número de páginas que podem ser alocadas na memória física. Questão 12 a) Em um sistema de paginação simples sem TLBs, cada referência à memória requer duas buscas na memória: uma para a tabela de páginas para encontrar o quadro de memória e outra para acessar os dados no quadro de memória.Se uma referência de memória leva 200 nanossegundos, então uma referência à memória paginada (que requer duas buscas) levaria 2×200 nanossegundos, ou seja, 400 nanossegundos. b) Se 75% das referências à tabela de páginas são encontradas nas TLBs, isso significa que apenas 25% das referências à memória precisarão de duas buscas na memória. As 75% restantes serão resolvidas imediatamente pelas TLBs (que assumimos ter um tempo de acesso de zero). Para as 25% das referências que requerem duas buscas na memória, o tempo é de 400 nanossegundos (como calculado em a). Para as 75% restantes, o tempo é de 200 nanossegundos (apenas uma busca na memória).O tempo efetivo de referência à memória pode ser calculado como a média ponderada destes dois casos, então 250 nanossegundos. Questão 13 A combinação de segmentação e paginação oferece um equilíbrio entre a facilidade de programação e gerenciamento de memória eficiente, ao mesmo tempo em que melhora a segurança, a proteção e o suporte para técnicas avançadas como a memória virtual. Questão 14 a) Segmento 0, Deslocamento 430: Endereço Físico: 649 b) Segmento 1, Deslocamento 10: Endereço Físico: 2310 c) Segmento 2, Deslocamento 500: O endereço lógico é inválido, pois o deslocamento (500) excede o tamanho do segmento (100). d) Segmento 3, Deslocamento 400: Endereço Físico: 1727 e) Segmento 4, Deslocamento 112: O endereço lógico é inválido, pois o deslocamento (112) excede o tamanho do segmento (96). Questão 15 First fit Best fit Worst fit Next fit 12KB 20KB 12KB 20KB depende da última alocação 10KB 10KB 10KB 20KB depende da última alocação 9KB 10KB 9KB 20KB depende da última alocação Questão 16 Para um tamanho de página de 4 KB: Endereço 20000: Número da página: 4 Deslocamento: 3616 Endereço 32768: Número da página: 8 Deslocamento: 0 Endereço 60000: Número da página: 14 Deslocamento: 2656 Para um tamanho de página de 8 KB: Endereço 20000: Número da página: 2 Deslocamento: 3616 Endereço 32768: Número da página: 4 Deslocamento: 0 Endereço 60000: Número da página: 7 Deslocamento: 2656 Questao 17 - Desafio a) Para determinar os valores de M e N que causariam uma ausência de página na TLB (Translation Lookaside Buffer) para cada execução do laço interno, precisamos considerar o tamanho da página e como os elementos do array X são armazenados na memória. Em C, um array é armazenado de forma contínua na memória. Supondo que int tem 4 bytes, cada elemento do array X ocupa 4 bytes. Com um tamanho de página de 4 KB (4096 bytes), cada página pode conter 1024 elementos do array. Para causar uma ausência de página na TLB em cada iteração, o passo step deve ser tal que cada acesso a X[i] esteja em uma página diferente. Isso significa que step deve ser pelo menos 1024 para garantir que cada acesso a X[i] seja em uma nova página. b) Se o laço for repetido muitas vezes, a resposta pode ser diferente dependendo do comportamento da TLB. A TLB armazena as traduções de endereços virtuais para físicos mais recentes ou mais usadas. Se o laço for repetido muitas vezes, as páginas acessadas frequentemente podem permanecer na TLB, resultando em menos ausências de página na TLB nas iterações subsequentes. Isso ocorre porque, uma vez que uma tradução de endereço é carregada na TLB, ela permanece lá até ser substituída por outra tradução devido à limitação de espaço ou políticas de substituição da TLB. Portanto, acessos repetidos ao mesmo conjunto de páginas têm maior probabilidade de encontrar suas traduções já na TLB, reduzindo as ausências de página. Memória Virtual Questão 1 As falhas de página ocorrem principalmente quando um processo tenta acessar uma página de memória que não está carregada na memória física (RAM), mas está indicada como presente na tabela de páginas. Isso pode acontecer se a página estiver armazenada em um dispositivo de armazenamento secundário, como um disco rígido (em um arquivo de paginação ou swap), ou se a página nunca foi acessada ou alocada antes (em sistemas com alocação de memória sob demanda). Outra causa de falha de página é a tentativa de acesso a uma página com permissões inadequadas, como escrever em uma página marcada como somente leitura. Quando ocorre uma falha de página, o sistema operacional interrompe o processo atual e executa uma rotina de tratamento de falha de página. Inicialmente, verifica-se a validade da falha: se a página realmente existe e se o acesso era permitido. Se for válida, o sistema operacional localiza a página faltante no armazenamento secundário e aloca um quadro de página livre na memória física. A página é então carregada do armazenamento secundário para a memória física, a tabela de páginas é atualizada para refletir a nova localização da página, e o processo é retomado do ponto onde a falha ocorreu. Se a falha for inválida (por exemplo, acessando uma área de memória não alocada ou violando permissões), o sistema operacional pode terminar o processo ou sinalizar um erro. Questão 2 Dentre os algoritmos de substituição de páginas listados, o que sofre da anomalia de Belady é o algoritmo FIFO (First-In, First-Out). A anomalia de Belady refere-se a um fenômeno no qual aumentar o número de quadros de página na memória pode levar a mais falhas de página, ao invés de menos. Isso pode ocorrer no algoritmo FIFO devido à sua abordagem simplista de substituir sempre a página mais antiga, independentemente de sua frequência ou padrão de uso. Os outros algoritmos mencionados, LRU (Least Recently Used), Substituição Ótima e Substituição de Segunda Chance, são projetados de maneira a evitar essa anomalia, levando em conta fatores como o uso recente ou a importância da página. Questão 3 Custos da Memória Virtual: Desempenho: Acessar memória virtual armazenada em discos é mais lento que acessar a memória física (RAM). Complexidade do Sistema Operacional: Implementar e gerenciar a memória virtual requer algoritmos complexos para gerenciamento de páginas e troca. Overhead de Hardware: Requer hardware adicional, como unidades de gerenciamento de memória (MMU), para mapeamento de endereços. Benefícios da Memória Virtual: Uso Eficiente da Memória: Permite que os programas usem mais memória do que a disponível fisicamente, compartilhando a memória física entre múltiplos processos. Proteção de Memória: Separa os espaços de memória dos processos, aumentando a segurança. Facilidade de Programação: Os programadores não precisam gerenciar a memória manualmente, pois o espaço de endereçamento é contínuo e uniforme. Sim, é possível que os custos sejam maiores que os benefícios. Os custos podem superar os benefícios em sistemas com hardware limitado ou com uma carga de trabalho que exige acesso frequente a dados armazenados no disco. Para mitigar isso, pode-se: Aumentar a Memória Física (RAM): Reduz a frequência de acessos ao disco. Otimizar o Sistema Operacional: Melhorar os algoritmos de gerenciamento de memória. Usar Discos Mais Rápidos (SSD): Diminui o tempo de acesso a dados no armazenamento secundário. Questão 4 O número de falhas de página para cada algoritmo é: LRU (Least Recently Used): 8 falhas de página. FIFO (First-In, First-Out): 10 falhas de página. Substituição Ótima: 7 falhas de página. Questão 5 Não, o novo algoritmo de substituição de página não pode ser considerado ótimo se ele sofre da anomalia de Belady. A anomalia de Belady refere-se a um fenômeno no qual aumentar o número de quadros de página disponíveis na memória resulta em mais falhas de página, ao invés de menos. Um algoritmo de substituição de página ótimo, por definição, não deve exibir essa anomalia, pois ele deve minimizar o número de falhas de página para qualquer número de quadros de página. Se um algoritmo mostra a anomalia de Belady em qualquer caso de teste, ele não atende ao critério de otimização nesse aspecto e, portanto, não pode ser considerado ótimo. Questão 6 a) Falta de TLB sem Falha de Página: Isso pode ocorrer se o endereço da página estiver na memória principal, mas não na TLB (Translation Lookaside Buffer). A TLB é uma cache pequena e rápida que armazena traduções recentes de endereços virtuais para físicos. Se um endereço não está na TLB, o sistema verifica na tabela de páginas. Se a página já estiver carregada na memória, o endereço é adicionado à TLB, ocorrendo uma falta de TLB, mas sem falha de página. b) Falta de TLB e Falha de Página: Ocorre quando o endereço referenciado não está na TLB e a página correspondente também não está na memória principal. O sistema primeiro verifica a TLB, não encontra a entrada (falta de TLB), e depois consulta a tabela de páginas, percebendo que a página precisa ser carregada do armazenamento secundário para a memória principal (falha de página). c) Acerto de TLB sem Falha de Página: Isso acontece quando o endereço da página já está na TLB e a página correspondente está na memória principal. O sistema consegue traduzir rapidamente o endereço virtual para um endereço físico usando a TLB, sem precisar acessar a tabela de páginas ou carregar a página do armazenamento secundário. d) Acerto de TLB e Falha de Página: Na prática, essa situação é improvável ou impossível. Um acerto na TLB implica que a tradução do endereço virtual para o físico já está disponível e a página correspondente está na memória. Portanto, não ocorre uma falha de página. Se a página estivesse ausente da memória principal, a tradução correspondente também não estaria na TLB. Questão 7 Para suportar a paginação por demanda, o hardware de um sistema de computação precisa de alguns componentes e funcionalidades essenciais: Unidade de Gerenciamento de Memória (MMU): Essencial para mapear endereços virtuais para endereços físicos. A MMU usa a tabela de páginas para esse mapeamento e é fundamental para identificar quando uma página necessária não está na memória física, resultando em uma falha de página. Registro de Estado da Página: Cada entrada na tabela de páginas deve ter um status que indica se a página está na memória ou no armazenamento secundário. Este registro é vital para a implementação da paginação por demanda. Mecanismos de Proteção: O hardware deve fornecer meios para definir e verificar permissões de página, como leitura, escrita e execução, para garantir que os processos acessem apenas as páginas às quais têm direito. Suporte para Falhas de Página: O hardware deve ser capaz de gerar uma interrupção de falha de página quando uma referência a uma página ausente é detectada. Essa interrupção sinaliza ao sistema operacional para carregar a página necessária do armazenamento secundário. TLB (Translation Lookaside Buffer): Uma cache especializada que armazena as traduções de endereços virtuais para físicos mais recentes ou mais usadas. Isso acelera o processo de tradução de endereços e é crucial para o desempenho da paginação por demanda. Dispositivos de Armazenamento Secundário Rápido: Como a paginação por demanda frequentemente acessa o armazenamento secundário (como discos rígidos ou SSDs) para carregar páginas, ter um dispositivo de armazenamento rápido pode melhorar significativamente o desempenho. Questão 8 Para o endereço virtual 11123456, o sistema extrai o número da página e o deslocamento, consulta a tabela de páginas para encontrar a página física correspondente e, então, combina o número da página física com o deslocamento para obter o endereço físico final. Questão 9 A taxa de falha de página aceitável para manter um tempo de acesso eficaz de não mais de 200 nanossegundos, considerando os parâmetros fornecidos, é aproximadamente 6.10 x 10-6, ou seja, cerca de 0.00061%. Isso significa que para cada milhão de acessos à memória, menos de 7 podem resultar em falha de página para manter o tempo de acesso eficaz desejado. Questão 10 a) a matriz é percorrida coluna por coluna. Cada elemento A[i][j] está no local de memória 200 + i*100 + j. Com páginas de tamanho 200, cada página contém elementos de duas linhas da matriz. Neste caso, acessar uma nova coluna frequentemente levará a uma nova página, gerando uma falha de página. b) a matriz é percorrida linha por linha. Como cada página contém elementos de duas linhas, haverá menos falhas de página comparado ao acesso coluna por coluna, pois a iteração linha por linha mantém os acessos dentro da mesma página ou na página adjacente. Para as malhas de inicialização de arrays no cenário descrito, o número de falhas de página usando o algoritmo de substituição LRU é: Malha a (Coluna-por-Coluna): 5000 falhas de página. Malha b (Linha-por-Linha): 50 falhas de página. A diferença significativa no número de falhas de página entre as duas abordagens é devida ao padrão de acesso à memória.