Capítulo 2 - Processos

De BCC Wiki

Sistemas Operacionais - Tanenbaum (Segunda Edição)

Questões - Capítulo 2 - Processos

1. Suponha que você vá projetar uma arquitetura avançada de computador que faz a comutação de processos em hardware, em vez de ter interrupções. Que informações a CPU precisaria? Descreva como a comutação de processos por hardware pode funcionar.

2. Em todos os computadores atuais, pelo menos parte dos manipuladores de interrupções são escritos em linguagem assembly. Por quê?

  • Os manipuladores de interrupção devem salvar os registradores e definir o ponteiro da pilha e isso deve ser feito em assembly. (Para saber o que acontece na interrupção, veja a figura 2-5 (página 49 do pdf do Tanenbaum em português)

3. No texto, afirmou-se que o modelo da Figura 2-6(a) não se ajustava a um servidor de arquivos utilizando um cache em memória. Por que não? Cada processo poderia ter seu próprio cache?

Fig2.6.jpg

  • O modelo da figura não se ajusta pois é essencial que os diversos threads do sistema de arquivos acessem o mesmo cache, afim de compartilhar a mesma informação. Outro fator é que se houver somente um thread por processo, caso o mesmo tente acessar um arquivo não encontrado no cache deverá buscá-lo no disco, bloqueando o sistema e impedindo de receber novas requisições, por não haver outro thread para executar.
  • Não. Se cada processo tem seu próprio cache, eles não podem compartilhar informação.

4. Em um sistema com threads, há uma pilha por thread ou uma pilha por processo? Explique.

Em um sistema com threads há uma pilha por thread.

5. O que é uma condição de corrida?

  • Uma condição de corrida (ou em inglês race condition) é uma situação indesejável que acontece quando um dispositivo ou sistema tenta fazer duas operações ao mesmo tempo, mas pela natureza do dispositivo ou sistema ela deve ser feita em uma determinada ordem para tudo dar certo. Usemos como exemplo um programa como sendo uma corrida de cavalos, onde cada cavalo é uma thread operando paralelamente. O software exige que o cavalo 42 chegue antes do cavalo 131, caso isto não ocorra teremos um erro. Uma possível solução é adicionar uma sincronização, na qual o cavalo 131 só poderia atravessar a linha de chegada se o cavalo 42 já tiver passado.

6. Escreva um script de shell (...)

7. [modificado] Uma declaração como ln file file.lock é um mecanismo de bloqueio efetivo para um programa de usuário? Por quê (ou por que não)?

8. A solução da espera ativa usando a variável turn (Figura 2-8) funciona quando os dois processos estão executando em um multiprocessador com memória compartilhada, isto é, duas CPU's compartilhando uma memória comum?

Fig2.8.jpg

9. Considere um computador que não tem uma instrução TEST AND SET LOCK mas tem uma instrução para comutar conteúdo de um registrador e de uma palavra da memória em uma única ação indivisível. É possível utilizar isso para escrever uma rotina enter_region como a encontrada na Figura 2-10?

Fig2.10.jpg

10. Faça um esboço de como um sistema operacional que pode desativar interrupções poderia implementar semáforos.

11. Mostre como semáforos de contagem (semáforos que podem armazenar um valor arbitrariamente grande) podem ser implementados utilizando apenas semáforos binários e instruções comuns de máquina.

12. Na Seção 2.2.4, foi descrita uma situação com um processo de alta prioridade , H, e um processo de baixa prioridade, L, que levou a um laço eterno de H. O mesmo problema ocorre se o agendamento por round robin for utilizado em vez de agendamento por prioridade? Discuta.

13. A sincronização dentro de monitores (...)

14. Um restaurante fast food tem quatro tipos de empregados:

  • (1) os atendentes, que anotam os pedidos dos clientes
  • (2) os cozinheiros, que preparam o alimento
  • (3) os embaladores, que colocam o alimento em sacolas
  • (4) os caixas, que entregam as sacolas aos clientes e recebem o dinheiro

Cada empregado pode ser considerado como um processo de comunicação sequencial. Que forma de comunicação interprocesso eles utilizam? Relacione esse modelo com processos no MINIX.

15. Suponha que temos um sistema de passagem de mensagens utilizando caixas de correio. Ao enviar para uma caixa de correio cheia ou ao tentar receber de uma vazia, um processo não é bloqueado. Em vez disso, ele recebe de volta um código de erro. O processo responde ao código de erro apenas tentando novamente, repetidamente, até ter sucesso. Esse esquema leva a condições de corrida?

16. Na solução para o problema dos filósofos jantando (Figura 2-18), por que a variável de estado é configurada como HUNGRY no procedimento take_forks?

Fig2.18.jpg

17. Considere o procedimento put_forks na Figura 2-18. Suponha que a variável state[i] tenha sido configurada como THINKING após as duas chamadas a test, em vez de antes. Como essa alteração afetaria a solução para o caso de três filósofos? E para 100 filósofos?

18. O problema dos leitores e dos escritores pode ser formulado de várias maneiras com referência a qual categoria de processos pode ser iniciada e quando ela pode ser iniciada. Cuidadosamente, descreva três variações diferentes do problema, cada uma favorecendo (ou não) alguma categoria de processos. Para cada variação, especifique o que acontece quando um leitou ou um escritor torna-se pronto para acessar o banco de dados e o que acontece quando o processo termina de utilizar o banco de dados.

19. Os computadores CDC 6600 podiam gerenciar até 10 processos de E/S simultaneamente, utilizando uma forma interessante de agendamento, round robin, chamada compartilhamento do processador. Uma comutação de processos ocorria depois de cada instrução, assim a instrução 1 vinha do processo 1, a instrução 2 do processo 2, e etc. A comutação de processos era feita por hardware especial e o acréscimo (overhead) era zero. Se um processo precisasse de T segundos para completar-se na ausência de concorrência, quanto tempo precisaria se o compartilhamento do processador fosse utilizado com N processos?

20. Os agendadores por round robin normalmente mantêm uma lista de todos os processos executáveis, com cada processo ocorrendo exatamente uma vez na lista. O que aconteceria se um processo ocorresse duas vezes na lista? Você consegue imaginar qualquer razão para permitir isto?

21. Medidas de um certo sistema mostraram que, na média, as execuções dos processos tendiam para um tempo T antes de bloquear em E/S. Uma comutação de processos requer um tempo S, que é efetivamente desperdiçado (overhead). Para agendamento por round robin com quantum Q, dê uma fórmula da eficiência de CPU para cada um dos seguintes.

  • (a) Q = α
  • (b) Q > T
  • (c) S < Q < T
  • (d) Q = S
  • (e) Q perto de 0

22. Cinco jobs estão esperando para ser executados. Seus tempos esperados de execução são 9, 6, 3, 5 e X. Em que ordem eles devem ser executados para minimizar tempo médio de resposta? (Sua resposta dependerá de x.)

23. Cinco jobs de lote, A até E, chegam a um centro de computação quase ao mesmo tempo. Eles têm tempos de execução estimados de 10, 6, 2, 4 e 8 minutos. Suas prioridades (externamente determinadas) são 3, 5, 2, 1 e 4, respectivamente, com 5 sendo a maior prioridade. Para cada um dos seguintes algoritmos de agendamento, determine o tempo de retorno médio dos processos. Ignore o acréscimo (overhead) da comutação de processos.

  • (a) Round robin
  • (b) Agendamento por prioridade
  • (c) Primeiro a chegar, primeiro a ser servido (execução na ordem 10, 6, 2, 4, 8)
  • (d) Job mais curto primeiro.

Para (a), suponha que o sistema é multiprogramado e que cada job receba sua justa parte da CPU. Para (b) a (d) suponha que só um job execute por vez, até terminar. Todos os jobs são completamente associados à CPU.

24. Um processo que executa no CTSS precisa de 30 quanta para completar-se. Quantas vezes ele deve sofrer comutação, incluindo a primeira vez (antes de ele executar completamente)?

25. O algoritmo com a = 1/2 está sendo utilizado para prever tempos de execução. As quatro execuções anteriores, da mais antiga à mais recente, foram 40, 20, 40 e 15 ms. Qual é a previsão do próximo tempo?

26. Um sistema soft real time tem quatro eventos periódicos com períodos de 50, 100, 200 e 250 ms cada. Suponha que os quatro eventos requeiram 35, 20, 100 e x ms de tempo de CPU, respectivamente. Qual é o maior valor de x para o qual o sistema é agendável?

27. Explique por que o agendamento de dois níveis é comumente utilizado.

28. Durante execução, o MINIX mantém uma variável proc_ptr que aponta para entrada da tabela de processos para o processo atual. Por quê?

29. O MINIX não armazena mensagens. Explique como essa decisão de projeto causa problemas com interrupções de relógio e teclado.

30. Quando uma mensagem é enviada a um processo adormecido no MINIX, o procedimento ready é chamado para colocar esse processo na fila adequada de agendamento. Esse procedimento inicia desativando as interrupções. Explique.

31. O procedimento do MINIX mini_rec contém um laço. Explique para que ele serve.

32. Essencialmente o MINIX utiliza o método de agendamento na Figura 2-23, com prioridades diferentes para classes. A classe mais baixa (processos de usuário) tem agendamento por round robin, mas as tarefas e os servidores sempre têm permissão para executar até bloquearem. É possível que processos na classe mais baixa morram de fome? Por quê (ou por que não)?

Fig2.23.jpg

33. O MINIX é adequado para aplicativos de tempo real, como registro de dados? Se não, o que poderia ser feito para torná-lo adequado?

34. Suponha que você tenha (...)

  • passado em SO?

35. Um aluno forte (...)

  • Cadu.

36. Repita o problema (...)

  • Cadu.

37. Resolva o problema dos filósofos jantando utilizando monitores em vez de semáforos.

38. Adicione código (...)

 codigo++;

39. Modifique o agendador (...)

40. Reprojete o MINIX (...)

41. Modifique as macros (...)

 #define YES NO
Ferramentas pessoais