Infra-Estrutura de Software

Sistemas Operacionais

Revisão

Sistema Computacional em Camadas

Acesso completo a todo o hardware e pode

executar qualquer instrução que a

máquina seja capaz de executar

Não pode executar instruções que afetam o controle da máquina

ou fazem E/S GUI ou shell

Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved.

Sistema Operacional como uma Máquina Estendida

•  Sistemas operacionais tornam o hardware pouco atraente em abstrações mais interessantes

Processador " Memória" Dispositivos E/S"

Processos"

Arquivos"

Memória Virtual"

Sistema Operacional como um Gerenciador de Recursos

• Gerencia e protege memória, dispositivos de E/S e outros recursos (hardware)

•  Permite o compartilhamento (multiplexação) de recursos –  no tempo (time-sharing)

• Ex.: múltiplos programas compartilham o processador (executam) ao mesmo tempo

–  no espaço • Ex.: um sistema de arquivos (parte do SO) permite

que dados de diferentes usuários/arquivos compartilhem o espaço em disco

5

Camadas em Linux

Kernel (núcleo)

Estrutura de Sistemas Operacionais: Máquina Virtual

(Virtualização)

VMM opera na interface de hardware, fornecendo uma interface idêntica para os SOs acima

Processo

• Estados

Pronto Rodando

Bloqueado

Criar Terminar

bloquear (I/O) desbloquear

ID do Processo Estado

Program Counter Ponteiros da Memória

Contexto (outros regs.) I/O Status

Prioridade

Informações gerais •  tempo de CPU •  limites, usuário, etc.

Contexto

executar

suspender (tempo)

Conceito: Multiprogramação

Escalonamento de processos

•  Quando um ou mais processos estão prontos para serem executados, o sistema operacional deve decidir qual deles vai ser executado primeiro

•  A parte do sistema operacional responsável por essa decisão é chamada escalonador, e o algoritmo usado para tal é chamado de algoritmo de escalonamento

•  Para que um processo não execute tempo demais, praticamente todos os computadores possuem um mecanismo de relógio (clock) que causa uma interrupção, periodicamente

Outros Conceitos

•  Interrupção

–  Por hardware

•  Algum dispositivo externo à CPU (ex. teclado)

•  Relógio (para suspender um processo)

–  Por software (trap)

•  Execução de intrução de programa (ex. READ)

•  Situações em que o programa não teria como prosseguir (ex. overflow em operações aritméticas)

•  Chamadas ao sistema formam a interface entre o SO e os programas de usuário

•  Página: parte de um programa capaz de caber na memória

•  Memória virtual: espaço de armazenamento de páginas em disco

Threads: Motivação

•  Problemas: – Programas que precisam de mais poder

computacional

– Dificuldade de implementação de CPUs mais rápidas

•  Solução: – Construção de computadores capazes de

executar várias tarefas simultaneamente

Problemas com Concorrência

•  Não-determinismo –  x = 1 || x = 2

•  Qual o valor de “x” após a sua execução?

•  Dependência de Velocidade –  [[ f(); x = 1 ]] || [[ g(); x = 2 ]]

–  O valor final de x depende de qual das funções, f() e g(), terminar primeiro

•  Starvation –  Processo de baixa prioridade precisa de um

recurso que nunca é fornecido a ele... Hermano P. Moura

Problemas com Concorrência (cont.)

•  Deadlock •  dois processos bloqueiam a sua execução

pois um precisa de um recurso bloqueado pelo outro processo

Hermano P. Moura

Conceitos: starvation e deadlock

Condições de Disputa/Corrida

Dois processos querem ter acesso simultaneamente à memória compartilhada

Regiões Críticas

• Condições para prover exclusão mútua: –  Nunca dois processos simultaneamente em uma

região crítica

–  Não se pode considerar velocidades ou números de CPUs

–  Nenhum processo executando fora de sua região crítica pode bloquear outros processos

–  Nenhum processo deve esperar eternamente para entrar em sua região crítica

Semáforo

•  Semáforo é uma variável que tem como função o controle de acesso a recursos compartilhados

•  O valor de um semáforo indica quantos processos (ou threads) podem ter acesso a um recurso compartilhado

–  Para se ter exclusão mútua, só um processo executa por vez

•  Principais operações:

–  inicialização: inteiro indicando a quantidade de processos que podem acessar um determinado recurso (exclusão mútua = 1)

–  wait ou down ou P: decrementa o valor do semáforo

•  Se valor for zerado, o processo é posto para dormir

–  signal ou up ou V: se o semáforo estiver zerado e existir algum processo adormecido, um processo será acordado

•  Caso contrário, o valor do semáforo é incrementado

Monitores

Exemplo de um monitor

Gerência de Processos

Escalonamento

18

Criação

Terminação

Manutenção

Comportamentos de Processos

•  Surtos de uso da CPU alternam-se com períodos de espera por E/S

a)  um processo orientado à CPU (CPU-bound) b)  um processo orientado à E/S (I/O-bound)

Filas de Escalonamento

Long- term

queue

Short- term

queue CPU

I/O queue

I/O queue

I/O queue I/O

I/O

I/O

Process request FIM

High-level scheduling

Short-term scheduling

I/O scheduling

Interrupt Handler

Interrupt of process

Interrupt from I/O

Categorias de Algoritmos de Escalonamento

•  Em lote (batch)

•  Interativo

•  Tempo-real

Características de Escalonamento •  Justiça (fairness)

–  Todos os processos têm chances iguais de uso dos processador

•  Eficiência –  Taxa de ocupação do processador ao longo do tempo

•  Tempo de Resposta –  Tempo entre a ocorrência de um evento e o termino da

ação correspondente

•  Turnaround (tempo de retorno) –  “Tempo de resposta” para usuários em batch –  Minimizar o tempo que usuários batch devem esperar pelo

resultado

•  Throughput (vazão) –  No. de “jobs” (processos) executados por unidade de

tempo

Problema das trocas de processos

•  Mudar de um processo para outro requer um certo tempo para a administração — salvar e carregar registradores e mapas de memória, atualizar tabelas e listas do SO, etc

•  Isto se chama troca de contexto

•  Ajustar um quantum muito pequeno causa muitas trocas de contexto e diminui a eficiência da CPU, ...

•  mas ajustá-lo para um valor muito alto causa um tempo de resposta inaceitável para pequenas tarefas interativas

Um algoritmo de escalonamento com quatro classes de prioridade

Escalonamento em Sistemas Interativos

3 categorias: -  “Real-time”

FIFO (não-preemptivo)

-  “Real-time” round-robin

-  Timesharing

Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639

Quantum decrescente

Escalonamento em Linux

Gerência de Memória

26

Registers"

On-chip L1"cache (SRAM)"

Main memory"(DRAM)"

Local secondary storage"(local disks)"

Larger, "slower, "

and "cheaper "

(per byte)"storage"devices"

Remote secondary storage"(distributed file systems, Web servers)"

Local disks hold files retrieved from disks on remote network servers."

Main memory holds disk "blocks retrieved from local "disks."

Off-chip L2"cache (SRAM)"

L1 cache holds cache lines retrieved from the L2 cache."

CPU registers hold words retrieved from cache memory."

L2 cache holds cache lines retrieved from memory."

L0:"

L1:"

L2:"

L3:"

L4:"

L5:"

Smaller,"faster,"and "

costlier"(per byte)"storage "devices"

Hierarquia de Memória O Gerenciador de memória trata essa hierarquia

Ocupação de espaço em memória – processo: programa, dados, pilha

a)  Alocação de espaço para uma área de dados em expansão b)  Alocação de espaço para uma pilha e uma área de dados,

ambos em expansão

Gerenciamento de Memória com Mapas de Bits

Memória Virtual Paginação (1)

Localização e função da MMU (Memory Management Unit): nos dias de hoje é comum se localizar no chip da CPU

Entrada típica de uma tabela de páginas

Acelerando a Paginação

1.  O mapeamento de endereço virtual para endereço físico deve ser rápido

2.  Se o espaço de endereçamento virtual for grande, a tabela de páginas será grande

Memória Associativa ou TLB (Translation Lookaside Buffers)

•  Tabela das traduções de endereços mais recentes

•  Funciona como uma cache para tabelas de página

Tabelas de Páginas Multi-Níveis

a)  Endereço de 32 bits com 2 campos (Page Table - PT1, PT2) para endereçamento de tabelas de páginas

b)  Tabelas de páginas com 2 níveis

•  Para minimizar o problema de continuamente armazenar tabelas de páginas muito grandes na memória

Substituição de Páginas

•  Falta de página (page-fault) na memória: –  qual página deve ser removida?

–  alocação de espaço para a página a ser trazida para a memória

•  A página modificada deve primeiro ser salva –  se não tiver sido modificada é apenas sobreposta

•  Melhor não escolher uma página que está sendo muito usada –  provavelmente precisará ser trazida de volta logo

WSClock

Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639

Algoritmo de Substituição de Páginas em Linux

Page Frame Reclaiming Algorithm (PFRA)

Anomalia de Belady

•  FIFO com 3 molduras de página •  FIFO com 4 molduras de página •  P mostra quais referências de página causaram faltas de página

Esperado: quanto mais molduras de página a memória possuir, menos faltas de página o programa terá."

Anomalia: neste exemplo, o algoritmo de substituição FIFO tem mais faltas de página (10P) para mais molduras (4)..."

Controle de Carga

•  Mesmo com um bom projeto, o sistema ainda pode sofrer paginação excessiva (thrashing)

•  Quando –  alguns processos precisam de mais memória –  mas nenhum processo precisa de menos (ou seja, nenhum

pode ceder páginas)

•  Solução: Reduzir o número de processos que competem pela memória –  levar alguns deles para disco (swap) e liberar a memória a

eles alocada –  reconsiderar grau de multiprogramação

Tamanho de Página

Tamanho de página pequeno

• Vantagens – menos fragmentação interna

– menos programa não usado na memória

• Desvantagens – programas precisam de mais páginas,

tabelas de página maiores

Segmentação

Permite que cada tabela cresça ou encolha, independentemente

Gerência de memória: conclusões

•  No projeto de sistemas de paginação, a escolha de um algoritmo não é suficiente Outras considerações:

–  Política de alocação

–  Tamanho de página

•  Segmentação ajuda a lidar com estruturas de dados que mudam de tamanho durante a execução –  simplifica o compartilhamento

–  permite proteção diferente para segmentos diferentes

•  Segmentação e paginação podem ser combinados para fornecer uma memória virtual de duas dimensões

Sistemas de Arquivos

Arquivos Diretórios

Implementação do sistema de arquivos Gerenciamento de espaço em disco

Implementação do Sistema de Arquivos

Um possível layout de sistema de arquivo

Master Boot Record: Registro Principal do Boot,

usado para iniciar o computador

Principais parâmetros do sistema de arquivo – ex. tipo

do sistema de arquivos, número de blocos do

sistema

Estrutura de dados com informações sobre um

arquivo, sendo um i-node por arquivo

Implementação de Arquivos (3)

Um exemplo de i-node

Gerenciamento do Espaço em Disco

Considerações relevantes:

• Tamanho do bloco: eficiência

• Monitoramento de blocos livres (ex. mapas de bits)

• Cotas de usuários

Gerência de E/S

1o. EE: sexta-feira, 30/04, 8h

•  Assuntos: –  Conceitos

–  Gerenciamento de processos

–  Gerenciamento de memória

–  Sistema de arquivos

–  Entrada/Saída

•  Material –  Transparências:

http://www.cin.ufpe.br/~if677 Plano de Aulas

–  Assuntos correspondentes no livro “Sistemas Operacionais Modernos” – 2ª Edição. A. Tanenbaum, 2003

Lida com a diversidade de dispositivos, como visto na última aula