Roteiro de Aulas - Sistemas Operacionais

14/3

Apresentação do Curso

• programa do curso
• critério de avaliação
• bibliografia
• introdução: histórico de sistemas operacionais

16/3

Processos

1. o modelo de processos
2. contexto: contador de programa, registradores, pilha, etc
3. multiprogramação e troca de contexto
4. estados e transições

Criação de novos processos

• a primitiva fork do Unix (e minix)
• hierarquias de processos

referência: Tanenbaum, 2.1, 2.1.1, 2.1.2

21/3

Processos

Criação de novos processos (cont)

• primitiva fork do Unix (e minix)
• primitiva exec
• primitiva wait

Sinais

referência: Tanenbaum, 4.7.7

obs: A discussão das primitivas fork, exec e wait não consta no livro texto. A documentaçAo dessas primitivas pode ser obtida através das páginas man de qualquer Unix, Linux ou minix.

23/3

Processos

Threads ou Processos Leves

• motivação:
  1. concorrência com menos custo para o sistema (troca de contexto, etc)
  2. necessidade de compartilhamento de dados globais
• threads como parte do kernel e como bibliotecas de usuário

referência: Tanenbaum, 2.1.3.

28/3

Processos

Escalonamento de Processos

• introdução: objetivos do escalonamento
• (1) escalonamento por rodízio
• (2) escalonamento por prioridades
  • prioridades estáticas
  • prioridades dinâmicas
    • prioridades recalculadas conforme comportamento do processo
    • processos I/O-bound e CPU-bound
• (3) escalonamento em sistemas de tempo real
• (4) escalonamento em dois níveis

referência: Tanenbaum, 2.4, 2.4.1, 2.4.2, 2.4.3, 2.4.4, 2.4.5, 2.4.8.

30/3

Processos

Comunicação entre Processos por Memória Compartilhada

Introdução

• variáveis compartilhadas por vários threads
  • possibilidade de inconsistências
• regiões críticas e exclusão mútua

Soluções para garantir exclusão mútua

• soluções que não funcionam com uso de variáveis compartilhadas...
• soluções por alternância rígida
  • busy waiting
  • um thread pode não conseguir entrar na região crítica mesmo quando nenhum thread está na sua região crítica!
• solução de Peterson
  • busy waiting
• necessidade de bloqueio por condição
  • semáforos

referência: Tanenbaum, 2.2.1, 2.2.2, 2.2.3 (parte), 2.2.5.

4/4

Processos

Semáforos

• definição do mecanismo: operações P e V
• exemplos:
  • produtor-consumidor
  • filósofos
• deadlock e starvation

referência: Tanenbaum, 2.2.4 (só definição do problema produtor-consumidor), 2.2.5, 2.3.1.

6/4

Processos

Semáforos

discussão de exemplos (na verdade, padrões de concorrência)

• leitores e escritores
• barreira

referência: Tanenbaum, 2.3.2.

11/4

exercícios

13/4

• discussão do trabalho
• exercício:
  • Considere o problema dos macacos discutido em sala. Para cada uma das soluções apresentadas aqui, diga (1) se a solução modela corretamente o comportamento dos macacos, e (2) se ela apresenta desvantagens como starvation.

18/4

Processos

Monitores

• introdução
  • histórico
  • definição
• políticas de sinalização
  • vamos assumir signal&continue
• produitor-consumidor
• barreira

  monitor barreira {
  
    int chegaram = 0;
    cond todoschegaram;
  
    void espera () {
      if (++chegaram!=TODOS)
        wait(todoschegaram);
      else {
        chegaram=0;
        signalAll(todoschegaram);
      }
    }
  }
  

referência: Tanenbaum, 2.2.6.

25/4

Processos

Troca de Mensagens

• primitivas de envio e recebimento
• especificação de um destinatário
  • pid
  • servidor de nomes
  • mailboxes
    • mecanismo mais usado na prática!
• primitivas síncronas e assíncronas

Exemplo: pipes no Unix

referência: Tanenbaum, 2.2.7 e Stevens, 3.4.

2/05

PROVA

4/05

Deadlocks

• Deadlock: Um conjunto de processos onde cada processo está bloqueado esperando por um evento que só pode ser gerado por outro processo do mesmo conjunto.
• A espera pode ser motivada por uma requisição de recurso qualquer; além de bloqueios por semáforos, um processo pode ficar bloqueado a espera de uma mensagem ou a espera de um recurso qualquer, como um lock de arquivo, uma página de memória, etc.

Condições para ocorrência de deadlock

Grafo de Alocação de Recursos

Formas de Tratamento

Detecção

Prevenção Estrutural

A idéia é negar uma das quatro condições necessárias para ocorrência do deadlock!

1. negação da exclusão mútua
   • técnicas tipo spooling
2. negação do hold and wait
   • alocação de recursos em bloco
3. negação da espera circular
   • ordenação de recursos e alocação em ordem crescente
4. negação da não preempção
   • apenas em contextos específicos: checkpoints e estados consistentes

Prevenção Dinâmica

• Com uma unidade de cada recurso, o sistema operacional pode manter o grafo de alocação de recursos e, antes de cada alocação, verificar se ela causaria um ciclo no grafo.
• Essa técnica não funciona com mais de uma unidade de cada recurso...
• Regiões de execução inseguras e o algoritmo do banqueiro

Algoritmo da Avestruz

referência: Tanenbaum, 3.3.

9/05

apresentação do primeiro trabalho

11/05

Transações Atômicas

propriedades:

• atomicidade
• serialização
• permanência

Atomicidade

• por cópias (de arquivos ou páginas)
• por log

Serialização

Nada se pode afirmar sobre a ordem em que duas transações concorrentes serão executadas, mas o efeito das transações deve ser coerente com a término completo de cada transação antes do início da próxima.

Formas de garantir a serialização

• mais comum: uso de locks
  • garantia de execução eventual
  • possibilidade de deadlocks

16/05

Gerência de Memória

endereços físicos e endereços lógicos ou virtuais

amarração de endereços lógicos (do programa executável) com físicos (da memória principal)

• em tempo de compilação
  • usado em arquiteturas antigas, onde o programa era sempre carregado na mesma posição da memória
  • só faz sentido com monoprogramação
• em tempo de carga
  • executável contém mapa de relocação
  • incompatível com técnicas como swapping
• em tempo de execução (necessidade de hardware especial)
  • exemplo: registrador base cujo valor é sempre somado a endereço lógico
  • de forma geral: MMU (memory management unit) realiza mapeamento

Alocação de Espaço para Processos

• blocos de tamanho variável
  • best-fit
  • first-fit
• fragmentação externa

Swapping

Segmentação

• espaço lógico do programa é dividido em unidades que têm sentido para o programa: segmentos
• cada segmento pode ser alocado na memória física de forma independente

Paginação

• páginas físicas (frames) e páginas lógicas (pages)
• mapeamento de endereços: tabela de páginas
• fragmentação interna
• tabela de páginas como conjunto de registradores na MMU
• tabela de páginas na MP e registrador com endereço da tabela na MMU
• necessidade de atualizar as informações na MMU na troca de contexto
• cache da tabela de páginas: TLB
• influência de acessos à tabela de páginas no tempo de acesso à memória

referência: Tanenbaum, 4.1, 4.2, 4.3.

18/05

Gerência de Memória (cont.)

Paginação

Memória virtual

• permite que o programa de usuário utilize um espaço de endereçamento virtual maior que a memória física total.
• parecido com swapping mas...
  • muito mais eficiente
  • Com swapping, o espaço de endereçamento de cada processo tem que ser menor que a MP; o que pode ser maior que a MP é a soma dos espaços de endereçamento de todos os processos.
• Apenas algumas das páginas virtuais têm um correspondente físico em cada instante; as demais páginas são marcadas como inválidas na tabela de páginas.
• Quando um programa faz um acesso a uma página que não está carregada na MP, a MMU gera um trap para o sistema operacional, que entra em ação para carregar a página requisitada.
• paginação sob demanda
• tratamento de um page fault
  • sistema operacional é ativado:
  • procura de página livre
  • carrega página desejada
  • atualiza tabela de páginas do processo
  • coloca processo que causou page fault novamente em estado pronto