Roteiro de Aulas - Sistemas Operacionais

2/3

Apresentação do Curso

4/3

Processos

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

Criação de novos processos

referência: Tanenbaum, 2.1, 2.1.1, 2.1.2

9/3

Processos

Criação de novos processos (cont)

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.

11/3

Processos

Threads ou Processos Leves

Escalonamento de Processos

referência: Tanenbaum, 2.1.3, 2.4, 2.4.1, 2.4.2.

16/3

Processos

Escalonamento de Processos (cont)

Comunicação e Sincronização entre Processos

Comunicação por memória compartilhada

referência: Tanenbaum, 2.4.7, 2.4.8, 2.2, 2.2.1, 2.2.3.

18/3

Processos - Comunicação e Sincronização entre Processos

Comunicação por memória compartilhada (cont)

Semáforos

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

23/3

Processos - Comunicação e Sincronização entre Processos

Comunicação por memória compartilhada (cont)

Semáforos (cont)

25/3

Processos - Comunicação e Sincronização entre Processos

Comunicação por Troca de Mensagens

Comunicação no Unix/Minix: pipes

referência: Tanenbaum, 2.2.7; Stevens, 3.3, 3.5.

30/3

Processos - Comunicação e Sincronização entre Processos

Comunicação no Unix/Minix: pipes (cont.)
Apresentação do Trabalho 1
Problema dos Leitores e Escritores

Suponha que diversos processos tentam continuamente realizar acessos a uma base de dados, algumas vezes para realizar operações de leitura e outras para realizar operações de escrita. A escrita requer acesso exclusivo à base de dados. Diversas leituras podem ocorrer simultaneamente. Como modelar este comportamento com memória compartilhada?

referência: Tanenbaum, 2.3.2.

6/04

exercícios sobre sincronização

8/04

Semáforos

Revisitando alguns problemas
  1. Problema dos Filósofos 
    void filosofo(i) {
while(TRUE) {
pensa();
requisita_garfos(i);
come();
libera_garfos(i);
}
}

void requisita_garfos(int i) {         void libera_garfos(int i) {
P(menor_garfo(i));                      V(maior_garfo(i));
P(maior_garfo(i));                      V(menor_garfo(i));
}                                      }

    Outra forma de entender a solução é ordenar os recursos utilizados e exigir que cada processo demande os recursos em ordem crescente!

  2. Problema do Buffer Limitado

    O mesmo problema do produtor-consumidor visto antes, mas agora o buffer tem um número máximo P de posições. Caso o buffer esteja cheio o produtor não pode depositar um item. Como fazer para o produtor não ficar em espera ocupada neste caso?

Construção de uma barreira de sincronização

Em muitas aplicações que envolvem diversos processos executando o mesmo código (chamadas single program multiple data), há alguns pontos onde cada processo só deve prosseguir quando todos os demais tiverem atingido o o mesmo ponto de execução. Como programar uma primitiva barreira() que bloqueie um processo até que todos os demais chamem a mesma primitiva?

  1. com dois processos, processo 0 e processo 1: 
      sem barr[2]; barr[0].valor=0; barr[1].valor=0;
  void barreira(int i) {
  /* i é o número do processo! */
  V(barr[1-i]); /* avisa que chegou */
  P(barr[i]); /* espera o outro chegar */
  }
  2. com n processos: 
      sem barr[n]; barr[0].valor=0; ... barr[n-1].valor=0;
  sem mestre; mestre.valor=0;

  no mestre:

  while(1) {
    for (i=0;i<n;i++) P(mestre);
    for (i=0;i<n;i++) V(barr[i]);
  }
  
  em cada trabalhador:

  void barreira(int i) {
  /* i é o número do processo! */
    V(mestre);
    P(barr[i]);
  }

referência: Tanenbaum, 2.2.5 (buffer limitado), 2.3.1 (outra solução para o problema dos fliósofos: ESTUDAR!).

13/04

Monitores

Disciplinas de Sinalização

A execução de um signal é uma indicação para outro processo de que uma condição que ele estava esperando se tornou verdadeira. No entanto, pode ser que até que ele entre em execução realmente a condição tenha sido novamente alterada...

Diferentes disciplinas de sinalização lidam de formas distintas com esse problema:

  1. Signal and Exit (SX): O processo que sinaliza é obrigado a sair do monitor imediatamente, ie, o signal tem que ser sempre a última coisa a ser executada.
  2. Signal and Urgent Wait (SU): O processo que sinaliza fica bloqueado até que o processo sinalizado saia do monitor ou execute outro wait.
  3. Signal and Continue (SC ou "signal como dica"): O processo que sinaliza continua executando sem restrições dentro do monitor. O processo sinalizado meramente passa para a fila de prontos; ao voltar a execução, tipicamente ele deve novamente testar se a condição sinalizada ainda é verdade.

Só faz sentido discutir se determinada solução por monitor funciona ou não se soubermos qual a disciplina de sinalização utilizada!

Exemplo de Utilização de Monitores: Leitores e Escritores

A idéia é programar um monitor ControlaBase com operações Pede_leitura, Pede_escrita, Libera_leitura e Libera_escrita, que devem ser chamadas por processos leitores e escritores antes e depois do acesso a base, respectivamente.

Observe que pareceria mais elegante definir um monitor Base com operaçãoes Leitura e Escrita. Por que isso é complicado???

Uma primeira tentativa de solução é pegar a solução do livro (Figura 2.19) e transpor diretamente os trechos protegidos por P(e) e V(e) (no livro, down(&mutex) e up(&mutex)) para rotinas do monitor: 

monitor ControlaBase {

  cond db;
  int leitores=0, escritores=0;

  void pede_leitura() {
    leitores++;
    if (leitores==1) wait(db);
  }
  ...
}

Essa solução NÃO vai funcionar!!!!!!! Variáveis de condição, ao contrário de semáforos, não têm valor. Assim, se logo de início um leitor executar Pede_leitura, ele vai ficar bloqueado (incondicionalmente!) ao executar wait!!!

referência: Tanenbaum, 2.2.6.

15/04

Monitores (cont.)

Soluções para o problema dos leitores e escritores
  1. Solução com a disciplina SC (signal&continue) 
    monitor ControlaBase {

cond okLeitura, okEscrita;
int leitores=0, escritores=0;

  void pede_leitura() {
    while (escritores) wait(okLeitura);
    leitores++;
  }

  void pede_escrita() {
    while (leitores || escritores) wait(okEscrita);
    escritores++;
  }

  void libera_leitura() {
    leitores--;
    if (!leitores)
      signal(okEscrita);
  }

  void libera_escrita() {
    escritores--;
    signal(okEscrita);
    signalAll(okLeitura);

}
  2. Solução com disciplina SX:

    Só pode haver uma sinalização em cada rotina, pois a sinalização necessariamente é a última ação de um processo dentro do monitor! 

    monitor ControlaBase {

cond okLeitura, okEscrita;
int leitores=0, escritores=0, esp_leit=0, esp_escrita=0;

  void pede_leitura() {
    if (escritores) {   /* teste possibilita starvation de escritores! */
      esp_leit++;
      wait(okLeitura);
      esp_leit--;
    }
    leitores++;
    if (esp_leit) signal(okLeitura); /* acorda eventuais colegas de fila */
  }

  void pede_escrita() {
    if (leitores || escritores) {
      esp_escrita++;
      wait(okEscrita);
      esp_escrita--;
    }
    escritores++;
  }

  void libera_leitura() {
    leitores--;
    if (!leitores)
      signal(okEscrita);
  }

  void libera_escrita() {
    escritores--;
    if (esp_escrita) signal(okEscrita); /* aqui prioridade para escritores */
    else signal(okLeitura); /* vai acordar só 1 leitor! */
  }

}

20/04

Deadlocks

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
  2. negação do hold and wait
  3. negação da espera circular
  4. negação da não preempção

Prevenção Dinâmica

Algoritmo da Avestruz

referência: Tanenbaum, 3.3.

22/04

Transações Atômicas

propriedades:

Atomicidade

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

27/04

aula de dúvidas

29/04

Prova 1

4/05

correção da prova

6/05

Apresentação do Trabalho 2

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)

Swapping

Controle de Espaço Livre

Segmentação

Paginação

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

11/05

Gerência de Memória (cont.)

Paginação

Memória virtual

referência: Tanenbaum, 4.3.2, 4.3.3, 4.3.4.

13/05

nao houve aula

18/05

Gerência de Memória (cont.)

Memória Virtual (cont.)

Algoritmos de Substituição de Páginas

referência: Tanenbaum, 4.4.1, 4.4.2, 4.4.4, 4.4.5, 4.4.6, 4.4.7.

20/05

Memória Virtual (cont.)

Thrashing
discussão sobre tamanho da página
Segmentação com Paginação

referência: Tanenbaum, 4.5.1, 4.5.3, 4.6.

25/05

Memória Virtual (cont.): exemplo - System V

27/05

Sistemas de Arquivos

Visão do Usuário (programador)

arquivos
diretórios

Implementação

implementação de diretórios
descricao de localização de arquivos

referência: Tanenbaum, 5.1, 5.2.1, 5.3.1, 5.3.2.

1/06

nao houve aula - entrega do trabalho

3/06 - feriado

8/06

Implementação de sistemas de arquivos (cont.)

Gerência de espaço livre
Consistência
Desempenho

referência: Tanenbaum, 5.3.3, 5.3.4, 5.3.5.

10/06

Segurança em sistemas de arquivos

15/06

Descritores de arquivos e u-area
Montagem de Sistemas de Arquivos

referência: Tanenbaum, 5.6.6, 5.6.7.

Last update: Tue Jun 15 17:19:29 EST 1999 by Noemi