Please enable JavaScript.
Coggle requires JavaScript to display documents.
EC009 - Sistemas Operacionais (Cap. 7 - Memória principal (Introdução…
EC009 - Sistemas Operacionais
Cap. 6 - Sincronização de processos
Introdução
Processos podem ser independentes ou cooperantes
Processo cooperante é aquele que pode afetar ou ser afetado por outro processo
Quando vários processos acessam um dado concorrentemente
Dependendo da ordem de acesso uma variável pode assumir diversos valores, podendo causar uma inconsistência
Esta situação é chamada de
RACE CONDITION
O problema da seção crítica
Consiste em desenvolver um protocolo que os processos possam usar para cooperar entre si, criando regras para permitir ou não a entrada de um processo em sua
CRITICAL SECTION
Deve satisfazer 3 requerimentos
Exclusão mútua
Se um processo está executando em sua critical section, então nenhum outro pode estar
Progresso
Se nenhum processo está executando na critical section e há processos que desejam entrar em suas critical sections, somente aqueles que não estão em suas remainder sections podem participar da decisão de qual será o próximo a entrar em critical section
Espera limitada
Há um limite para o número de vezes de entrada de outros processos em suas critical sections depois que um processo faça um pedido para entrar em sua critical section
Suas soluções podem ser implementadas tanto em software quanto em hardware
O Peterson's Solution é uma solução em software para o problema da critical section no caso de haver dois processos cooperantes, mas não funciona corretamente em arquiteturas de computadores modernas, como por exemplo arquiteturas que fazem uso de pipelines
Hardware para sincronização
Muitas máquinas provêm instruções atômicas especiais de hardware que permitem testar e modificar o conteúdo de uma palavra ou trocar os conteúdos de duas palavras atomicamente
Instrução atômica é aquela que não pode ter sua execução interrompida
Test-and-set
Essa instrução permite testar e modificar o conteúdo de uma palavra de forma atômica
Condições de corrida podem ser evitadas se exigirmos que regiões críticas sejam protegidas por locks
Semáforos
O uso de mecanismos de hardware, com instruções atômicas do tipo test-and-set é complicado para programadores
Semáforo é uma ferramenta de sincronização, em software, composta por uma variável inteira, acessada somente (fora a inicialização) por duas operações atômicas:
WAIT
e
SIGNAL
SOs costumam fazer a distinção entre semáforos binários e de contagem
Semáforo binário
Seu valor só pode variar entre 0 e 1
Conhecidos como locks mutex, já que são locks que fornecem exclusão mútua
N processos compartilham um semáforo, inicializando com 1
Semáforo de contagem
Pode variar dentro de um domínio irrestrito
Usados para controlar o acesso a um determinado recurso composto por uma quantidade finita de instâncias
É iniciado com a quantidade de recursos disponíveis
Cada processo que deseja usar um recurso executa uma operação wait() no semáforo (decrementando a contagem)
Quando um processo libera um recurso, ele executa uma operação signal()
A principal desvantagem é que requer
espera em ação
Enquanto um processo estiver em sua seção crítica, qualquer outro processo que tentar fazer o mesmo deve percorrer um loop infinito no código de entrada
Isso desperdiça ciclos de CPU que algum outro processo poderia usar produtivamente
Semáforos que usam espera em ação são chamados de
SPINLOCK
porque o processo gira enquanto espera o lock
Problemas clássicos resolvidos com semáforos
Problema do buffer limitado
Processo produtor e processo consumidor
Problemas dos leitores/gravadores
Ler e/ou atualizar um objeto compartilhado
Não há necessidade de sincronização entre processos que só leem um objeto
Problema do jantar dos filósofos
Problema genérico e abstrato que é utilizado para explicar diversas situações indesejáveis que podem ocorrer em problemas que tem como principal ideia a exclusão mútua
5 filósofos, 5 palitos e uma tigela de arroz
Filósofos podem comer ou pensar
Só come quando tem dois palitos
Monitores
Programadores frequentemente cometem erros ao implementarem semáforos
Para evitá-los, pesquisadores desenvolveram uma construção em linguagem de alto-nível para sincronização de processos chamada monitor
Um TAD (tipo abstrato de dados) é uma estrutura que encapsula dados privados com métodos públicos para operar sobre esses dados
Um monitor é um TAD que representa um conjunto de operações definidas pelo programador que fornecem exclusão mútua
As variáveis de um monitor só podem ser acessadas pelos métodos (ou procedures) do monitor
O monitor garante que somente um processo por vez estará ativo dentro de um monitor
Assim, quando um processo executa um dos métodos do monitor, os outros métodos não poderão ser executados pelos demais processos
Monitores em Java
A linguagem de programação Java fornece um mecanismo de concorrência semelhante ao monitor para a sincronização de threads
Um monitor Java é um objeto que possua, ao menos, um método do tipo synchronized
O monitor permite a apenas uma thread por vez executar o método synchronized sobre o objeto
Todo objeto em Java tem um lock associado a ele
Quando um método synchronized é chamado o objeto é travado pois o método recebe o lock do objeto
Transações atômicas
A consistência de dados, junto com o armazenamento e a recuperação de dados, é uma preocupação frequente dos sistemas de banco de dados
Memória transacional é uma estratégia que permite transações em memória, que são sequências de operações atômicas de read-write em memória
Se todas as operações são completadas, a transação é encerrada (committed), caso contrário, as operações devem ser desfeitas (rolled back)
A grande vantagem desse mecanismo é que o sistema de memória transacional, e não o desenvolvedor, é responsável por garantir a atomicidade
Objetivos
Introduzir o problema da seção crítica, cujas soluções podem ser usadas para garantir a consistência de dados compartilhados
Apresentar soluções tanto de hardware como de software para o problema da seção crítica
Introduzir o conceito de transações e descrever mecanismos que assegurem a atomicidade
Cap. 7 - Memória principal
Introdução
A memória consiste de um grande array de palavras ou bytes, cada um com seu próprio endereço
A CPU obtém instruções a partir da memória de acordo com o valor do PC (program counter)
A CPU pode acessar diretamente somente seus registradores, a memória cache e a memória principal
Por isso a memória principal deve ser protegida de acessos indevidos por parte dos processos dos usuários
Essa proteção deve ser fornecida pelo hardware usando dois registradores, normalmente um registrador base e um registrador limite
O registrador base contém o menor endereço válido da memória física
O registrador limite especifica o tamanho do intervalo
Qualquer tentativa de acessar a memória do SO ou a memória de outros usuários feita por um programa em execução na modalidade de usuário resulta em uma interrupção que trata a tentativa como um erro fatal
Apenas o SO, executando na modalidade de kernel, tem acesso irrestrito tanto à sua própria memória quanto à memória dos usuários
Vinculação de endereços
Um programa para ser executado deve ser inserido na memória como um processo
Durante sua execução, o processo acessa instruções e dados na memória
A vinculação de instruções e dados a endereços de memória pode ser realizada de 3 maneiras
Tempo de compilação
Quando se sabe, em tempo de compilação, onde o processo irá residir na memória
Gera um código absoluto
Tempo de carga
Quando não se sabe em tempo de compilação onde o processo vai residir na memória, então o processo gera um código relocável na memória
Tempo de execução
Quando o processo pode ser movimentado de um segmento de memória para outro durante sua execução
Utilizado pela maioria dos SOs
Se a vinculação de endereços for feita em tempo de compilação ou em tempo de carga, o processo não poderá mover-se de lugar na memória durante sua execução
Se a vinculação de endereços for feita em tempo de execução, o processo poderá mover-se de lugar na memória durante sua execução
Espaços de endereçamento
Endereços lógicos (virtuais)
Os programas do usuário jamais enxergam os endereços físicos reais. O programa do usuário lida com endereços lógicos
Endereços físicos
Correspondem a uma posição real da memória
Implementado pelos circuitos integrados da memória
A MMU (memory management unit) é um dispositivo de hardware que mapeia endereços lógicos em endereços físicos
Contém um registrador de relocação, que é o registrador base
Realiza o address binding em tempo de execução, mapeando cada endereço lógico gerado pela CPU em um endereço físico correspondente
Carga dinâmica
Para obter melhor utilização do espaço de memória, podemos usar a carga dinâmica
Só o programa principal é carregado na memória pelo loader
Todas as sub-rotinas do programa são mantidas em disco
Sub-rotinas nunca chamadas não são carregadas desnecessariamente na memória
Carga estática
O programa inteiro e os dados têm que estar em memória
O programa é integralmente carregado pelo loader
O tamanho máximo de um processo é limitado pelo tamanho da memória
Vinculação dinâmica e bibliotecas compartilhadas
Cada programa pode usufruir de várias bibliotecas comuns
O compartilhamento de bibliotecas entre programas maximiza o uso da memória principal através da técnica de vinculação dinâmica
Com este esquema, todos os processos que utilizam uma biblioteca de linguagem executam apenas uma cópia do código da biblioteca
Os programas utilizam de stubs (pequenos fragmentos de código) para referenciar as bibliotecas comuns
Evita o desperdício tanto de espaço em disco quanto em memória principal
Nem todos os SOs aceitam vinculação dinâmica, mas apenas estática, onde cada biblioteca deve ser incorporada em cada programa
Swapping
Um processo precisa estar na memória para ser executado, mas pode ser transferido temporariamente da memória principal para uma memória secundária e retornar quando necessário
Swapping out é a remoção integral de um processo da memória para o disco
Swapping in é a volta integral de um processo do disco para a memória
Se o CPU Scheduler selecionar um processo não residente na memória para executar, então ele deve trazer para a memória este processo
Swapping é uma operação custosa, por isso deve ser evitado
Processos que tipicamente sofrem swapping
Processos em hibernação
Processos suspensos
Processos em espera de I/O
Swapfiles são arquivos em disco com a finalidade de armazenar swapped processes, cujo acesso deve ser otimizado por questões de desempenho
Esquemas de alocação de memória
A memória principal deve acomodar tanto o SO quanto os diversos processos de usuário
Para isso é preciso alocar a memória principal da maneira mais eficiente possível
A memória é normalmente dividida em duas partições
Uma para o SO
Uma para os processos do usuário
Para alocar a memória disponível aos processos que estão na fila de entrada esperando para serem carregados, podem ser usadas 3 técnicas
Alocação contígua
Paginação
Segmentação
Alocação de memória contígua
Neste esquema de alocação, como o espaço de endereçamento do processo é contíguo, o mapeamento de um processo na memória pode ser definido apenas pelos valores dos registradores
RELOCATION
e
LIMIT
Vale lembrar que quando o scheduler da CPU seleciona um processo para execução, o despachante carrega os registradores de relocação e limite com os valores corretos no momento de context switching
São utilizadas duas estratégias para alocar processos na memória
Partições de tamanho fixo
Divide toda a memória em várias partições de tamanho fixo
Nível de multiprogramação fica limitado pela quantidade de partições
Apesar de simples, este método já caiu em desuso por não ser muito viável
Partições de tamanho variável
O SO mantém uma tabela indicando que partes da memória estão disponíveis e quais estão ocupadas
Partições são criadas conforme a necessidade dos programas
Com a entrada de programas, a memória passará a ter um conjunto de intervalos de vários tamanhos
Para alocar um bloco de memória (hole) que satisfaça o tamanho de um programa, podemos usar 3 métodos
First fit
Aloca o programa na primeira partição grande o bastante para alocá-lo
Best fit
Aloca o programa na menor partição grande o bastante para alocá-lo
Worst fit
Aloca o programa na maior partição grande o bastante para alocá-lo
Essas diferentes alocações são possíveis pois o SO guarda uma lista de partições disponíveis
Conforme processos são carregados na memória e dela removidos, o espaço de memória livre fica dividido em pequenos pedaços, gerando
fragmentação externa
Ocorre quando existe espaço total de memória suficiente para atender uma solicitação, mas os espaços disponíveis não são contíguos
A técnica de compactação é uma solução
Que no modo mais simples move todos os processos para uma das extremidades da memória a fim de liberar espaço
Ou permite que o espaço de endereçamento lógico dos processos não seja contíguo (paginação e segmentação)
Apesar de resolver o problema, é uma operação custosa para o SO
A fragmentação também pode ser
interna
, quando o bloco de memória dado a um processo é maior que o necessário
Paginação
A alocação contígua fragmenta a memória
A paginação é um esquema de gerenciamento de memória que permite que o espaço de endereçamento físico de um processo não seja contíguo, consequentemente, evitando a fragmentação externa e a necessidade de compactação
A memória física é dividida em blocos de tamanho fixo chamados quadros
A memória lógica é quebrada em blocos do mesmo tamanho chamados páginas
Cada endereço gerado pela CPU é dividido em duas partes
Número de página
Usado como um índice na
tabela de páginas
que contém o endereço base de cada página na memória física
Deslocamento de página
É combinado com o endereço base para definir o endereço na memória física
Um aspecto importante da paginação é a separação clara entre a visão que o usuário tem da memória e a memória física real
O programa do usuário vê a memória como um espaço único, mas na verdade, o programa é espalhado por toda a memória física, que também contém outros programas
Todo mapeamento fica oculto do usuário e é realizado pelo SO
O SO mantém uma cópia da tabela de páginas para cada processo
Do modo que quadros vão sendo liberados, novas páginas vão sendo alocadas
Suporte de hardware
Antigamente
A page table de cada processo era gravada em registradores
O PCB de cada processo armazenava os valores destes registradores
Atualmente
A page table de cada processo é muito grande, e fica no espaço de endereçamento do SO
Um registrador chamado PTBR (page-table base register) aponta para a page table
O processador utiliza de uma cache de memória chamada TLB (translation look-aside buffer) que guarda as páginas de diferentes processos mais acessadas recentemente
Cada entrada contém um address space identifier (ASID) que especifica o processo a qual a entrada se refere
Proteção
O mecanismo de paginação deve incluir um mecanismo para proteção de memória
Geralmente um bit válido-inválido e um bit de proteção read-write deve ser associado a cada posição na tabela de páginas para prover esta proteção
O bit válido-inválido caso esteja em 'i', indica que uma página ainda não se encontra na memória - page fault
O bit read-write indica se uma página é de leitura-gravação ou somente de leitura
Páginas compartilhadas
Uma grande vantagem de paginação é a facilidade em compartilhar código reentrante, que é aquele que não se modifica por si mesmo, ou seja, nunca muda durante a execução (read-only)
Portanto pode ser executado ao mesmo tempo por vários processos
Segmentação
Método básico
A visão que usuários preferem ter da memória não é como uma sequência de bytes
Usuários preferem ter uma visão da memória como uma coleção de segmentos de tamanho variável
A segmentação é um esquema de gerenciamento de memória que suporta a visão que o usuário tem da memória
Funcionamento
Um espaço de endereçamento lógico passa a ser uma coleção de segmentos
Cada endereço lógico consiste em uma tupla dupla
<número do segmento, deslocamento>
Normalmente, o programa do usuário é compilado e o compilador constrói automaticamente segmentos para este programa
O compilador C pode criar segmentos separados como
Código
Variáveis globais
Heap
Stacks
Bibliotecas
Hardware
O mapeamento de segmentos lógicos em endereços físicos é feito por meio de uma segment table
Cada entrada da segment table possui uma base e um limite
A segment table é um array de pares de registradores base-limite
Objetivos
Fornecer uma descrição detalhada de várias maneiras de organizar o hardware de memória de um computador
Discutir várias técnicas de gerenciamento de memória, inclusive como funciona a paginação e a segmentação
Paginação com segmentação
Se os segmentos são grandes, não dá para mantê-los na memória em sua totalidade
Aplicar a idéia de paginação nos segmentos, só deixando na memória as páginas realmente necessárias para cada segmento, pode resolver o problema
Logo, o endereço lógico das páginas de um segmento com paginação seria formado pela seguinte combinação
<Núm. do segmento, Núm. da página, deslocamento da página>
Cap. 8 - Memória virtual
Introdução
Memória virtual é uma técnica que permite a execução de processos que não estejam completamente na memória principal
Benefícios
Um programa não fica mais restrito ao montante de memória física disponível
Mais programas podem estar em execução ao mesmo tempo
Menos I/O necessária para carregar e remover um programa da memória
A memória virtual torna a tarefa de programar muito mais fácil, porque o programador não precisa mais se preocupar com a quantidade de memória física disponível
A memória virtual envolve a separação entre a memória lógica como percebida pelos usuários e a memória física
Essa separação permite que uma memória virtual extremamente ampla seja fornecida aos programadores quando existe apenas uma memória física disponível
Paginação por demanda
Conceitos básicos
A paginação por demanda é uma técnica utilizada em sistemas de memória virtual que permite carregar páginas de processos somente quando forem necessárias
Um sistema que implemente paginação por demanda deve implementar as mesmas estruturas necessárias que um sistema de paginação (page-table, memória secundária, etc) e mais um pager
Um pager é similar a um swapper, a diferença é que o swapper manipula processos inteiros, e o pager manipula páginas individuais do processo
Page fault
Provocado pelo acesso a uma página marcada como inválida
Procedimento
A tabela de páginas do processo é acessada
Se a página for inválida, uma excessão é causada e o SO é avisado
SO busca página na memória secundária
Aloca um frame para a nova página
Atualiza a tabela de páginas
Reinicia instrução
Observações
Paginação por demanda pura
O processo continuará sua execução causando erros sempre que necessário até que todas as páginas estejam na memória
Quando o SO posicionar o ponteiro de instruções para a primeira instrução do processo, provocará imediatamente um page fault
Jamais carregue uma página em memória até que ela seja solicitada
Page size pequeno
Diminui a fragmentação interna
Aumenta a resolução (% de memória ativa)
Page size grande
Reduz o overhead devido a redução do número de page-faults
Reduz o tamanho das tabelas de páginas
Pelo aumento do tamanho das memórias atualmente, é uma tendência
I/O interlock
Momentos onde é necessário fixar as páginas na memória a fim de que elas não sejam levadas para a memória secundária
Cópia-após-gravação
Técnica que permite que processos pai e filho compartilhem inicialmente as mesmas páginas
As páginas compartilhadas são marcadas como páginas de cópia-após-gravação, significando que, se um processo gravar em uma página compartilhada, será criada uma nova cópia dessa página
Substituição de páginas
Uma super-alocação ou over-allocating da memória acontece quando ocorre um page fault e não há mais frames livres para abrir a nova página
Soluções
Pode-se remover um processo qualquer para o disco (swapping)
Método radical usado quando as taxas de page faults são altas no sistema
Página vítima
Pode-se escolher uma página vítima (victim page) e substituí-la pela nova página (page replacement) em um frame de memória
A seleção do quadro vítima pode ser feita por algoritmos
FIFO
Algoritmo de substituição de páginas mais simples
Associa a cada página a hora em que foi carregada na memória
Sempre a mais antiga é a vítima
Pode-se também ser criada uma fila para manter todas as páginas em memória, substituindo a da cabeça da fila
Anomalia de belady
Para alguns algoritmos, a taxa de page faults pode aumentar com o aumento do número de quadros alocados
OPTIMAL
Não sofre da anomalia de belady
Algoritmo ótimo, com taxa de erros mais baixa entre todos
De difícil implementação, uma vez que requer o conhecimento futuro de quais páginas serão referenciadas
Substitua a página que não será utilizada pelo período de tempo mais longo
LRU
Least-recently-used
Um algoritmo ótimo olhando para o passado
Escolhe como vítima a página que foi referenciada menos recentemente
Não sofre com a anomalia de belady
Exige assistência de hardware, como por exemplo auxílio do TLB
LRU approximation algorithms
Fazem uso dos reference bits
Um reference bit é associado a cada página
Inicialmente, todos os reference bits são setados para 0
Cada vez que uma página for referenciada, seu RB é setado praa 1
Algoritmo da segunda chance
Implementa-se o FIFO usual
Quando uma página é selecionada, inspecionamos seu bit de referência
Se o valor for 0, substituimos essa página
Se for 1, damos à página uma segunda chance e seu bit de referência é zerado
Ao receber a segunda chance, não será substituída até que todas as outras páginas tenham sido substituídas
Como uma fila circular
Counting-based algorithms
Implementa um contador do número de referências feitas a cada página
LFU
A página vítima é a página com menor valor no contador
Problema
Uma página pode ser inicialmente muito usada e depois não mais referenciada
Essa página terá um valor alto no contador e não deixará mais a memória
Solução
Decrementar todos os contadores em intervalos de tempo regulares
MFU
A página vítima é a página com maior valor no contador
Baseia-se no argumento que a página com menor valor no contador foi provavelmente trazida à memória, e portanto, ainda será usada
Seu custo de implementação é alto e não se aproximam do desempenho do optimal
Page-buffering algorithms
Alguns procedimentos podem ser usados conjuntamente com os algoritmos de troca de páginas com fins de otimização, por exemplo, mantendo um pool de frames livres
Toda vez que um frame é necessário, ele é retirado do pool
Reinicia-se assim mais rapidamente o processo que sofreu page fault
Mais tarde uma victim page é incorporada ao pool para suprir o frame retirado
Este procedimento permite que o processo seja reiniciado o mais breve possível
Alocação de quadros
Deve haver um número mínimo de frames alocados a cada processo que deve permitir a execução de qualquer instrução do processador sem que haja page fault
Algoritmos
Equal allocation
A maneira mais fácil de dividir m quadros entre n processos dando a cada processo uma parte igual correspondente a m/n quadros
Proportional allocation
A memória disponível é alocada a cada processo de acordo com seu tamanho
Priority allocation
A memória disponível é alocada a cada processo de acordo com a sua prioridade
Substituição de páginas
Outro fator que influi na maneira como os quadros são alocados aos diversos processos
Com múltiplos processos competindo por quadros, podemos classificar os algoritmos de substituição de páginas em duas grandes categorias
Substituição global
Permite a um processo obter um quadro mesmo quando este se encontra alocado a um outro processo
Este é o método mais utilizado
Substituição local
Permite a um processo obter um quadro às custas de ter que liberar algum outro de seus próprios frames
Atividade improdutiva (thrashing)
Se um processo tem um número muito pequeno de frames, ele entra em page faults sucessivos, num estado chamado de thrashing
Um processo que se encontra em thrashing gasta mais tempo paginando do que executando
Para evitar
Aumentar a quantidade de RAM de um computador
Diminuir o número de programas rodando no computador
Utilizar programas que utilizem menos memória
Setar prioridades aos programas
Arquivos mapeados em memória
Mapear um arquivo em memória permite que um bloco do arquivo em disco seja mapeado em uma ou mais páginas do processo em memória
Quando o processo executa a primeira operação de read no arquivo, blocos do arquivo são trazidos para uma ou mais páginas do processo em memória
A partir daí, as demais operações de read (ou write) são realizadas diretamente nas páginas mapeadas em memória
Isso leva a uma melhora significativa de desempenho na execução de I/O
Vários processos podem usufruir deste arquivo na memória caso tenham permissão
Objetivos
Descrever os benefícios de um sistema de memória virtual
Explicar os conceitos de paginação por demanda, algoritmos de substituição de páginas e alocação de quadros de páginas