Sistemas Operacionais Exercícios

Prévia do material em texto

<p>102 Sistemas operacionais modernos o conceito de um processo é um exemplo de algo mui- situação que levaria ao caos. Um processo pode estar exe- to bem estabelecido. Quase todo sistema tem alguma noção cutando, ser executável ou bloqueado e alterar o estado de um processo como um recipiente para agrupar recursos quando ele ou um outro processo executa uma das unida- relacionados, como um espaço de endereçamento, threads, des básicas de comunicação entre processos. A comunica- arquivos abertos, permissões de proteção etc. Sistemas di- ção interthread é semelhante. ferentes fazem esse agrupamento de maneira um pouco As primitivas de comunicação entre processos podem diferente, mas trata-se apenas de diferenças de engenharia. ser usadas para resolver problemas como o produtor-con- A ideia básica não é tão controversa e há pouca pesquisa sumidor, o jantar dos filósofos e o leitor-escritor. Mesmo nova sobre o tema processos. com essas primitivas, devem-se tomar cuidados para evitar Os threads são uma ideia mais nova que os processos, erros e impasses. mas tem havido bastantes reflexões sobre eles. Além disso, Muitos algoritmos de escalonamento têm sido estuda- ocasionalmente aparecem artigos sobre threads tratando, dos. Alguns deles são usados principalmente em sistemas por exemplo, de aglomerados de multiprocessadores (Tam emlote, como a tarefa mais curta primeiro. Outros são comuns et al., 2007) ou do dimensionamento do número de threads aos sistemas em lote e aos sistemas o es- em um processo para cem mil (Von Behren et al., 2003). calonamento circular, o escalonamento por prioridades, as A sincronização de processos está muito mais definida filas múltiplas, o escalonamento garantido, o escalonamen- agora, mas de vez em quando ainda há artigos, como aque- to por loteria e o escalonamento por fração justa. Alguns les sobre processamento concorrente sem locks (Fraser e sistemas fazem uma separação entre o mecanismo de esca- Harris, 2007) ou sincronização no modo não bloqueante lonamento e a política de escalonamento, o que permite aos em sistemas de tempo real (Hothmuth e Haertig, 2001). usuários um controle sobre o algoritmo de escalonamento. o escalonamento (tanto uniprocessador quanto mul- tiprocessador) ainda é um tópico recente e caro a alguns Problemas pesquisadores. Alguns tópicos sendo pesquisados incluem escalonamento de dispositivos móveis em termos de efi- 1. Na Figura 2.2, são mostrados três estados de processos. Na ciência energética (Yuan e Nahrstedt, 2006), escalonamen- teoria, com três estados poderia haver seis transições, duas to com tecnologia hyperthreading (Bulpin e Pratt, 2005), para cada estado. Contudo, somente quatro transições são modos de reduzir a ociosidade da CPU (Eggert e Touch, mostradas. Há alguma circunstância na qual uma delas 2005) e escalonamento de sistemas de tempo virtual (Nieh ou ambas as transições não ilustradas possam ocorrer? et al., 2001). Contudo, poucos projetistas de sistemas ope- 2. Suponha que você seja o projetista de uma arquitetura de racionais andam desesperados pela falta de um algoritmo computador avançada que fez o chaveamento entre pro- decente para o escalonamento de threads portanto, pa- cessos por hardware em vez de usar interrupções. De que rece que esse tipo de pesquisa é mais um desejo do que informação a CPU precisaria? Descreva como o processo uma necessidade de pesquisadores. De modo geral, pro- de chaveamento por hardware poderia funcionar. cessos, threads e escalonamento não são mais tópicos de 3. Em todos os computadores atuais, pelo menos uma parte pesquisa tão procurados como antes. A pesquisa avançou. dos manipuladores de interrupção (interrupt handlers) é escrita em linguagem assembly. Por quê? 4. Quando uma interrupção ou uma chamada de sistema 2.7 Resumo transfere o controle para o sistema operacional, geral- mente é usada uma área da pilha do núcleo separada da Para ocultar os efeitos das interrupções, os sistemas pilha do processo interrompido. Por quê? operacionais oferecem um modelo conceitual que consis- te em processos sequenciais executando em paralelo. Os 5. Tarefas múltiplas podem ser executadas paralelamente processos podem ser criados e terminados dinamicamente. e terminar mais rápido do que se tivessem sido execu- tados sucessivamente. Suponha que duas tarefas, cada Cada processo tem seu próprio espaço de endereçamento. uma precisando de dez minutos do tempo da CPU, co- Para algumas aplicações, é útil ter múltiplos threads de meçassem simultaneamente. De quanto tempo o último controle dentro de um único processo. Esses threads são es- precisará para terminar se elas forem executados sucessi- calonados independentemente e cada um tem sua própria vamente? Quanto tempo se forem executadas paralela- pilha, mas todos os threads em um processo compartilham mente? Suponha 50 por cento de espera de E/S. um espaço de endereçamento comum. Threads podem ser 6. No texto, foi estabelecido que o modelo da Figura 2.8(a) implementados no espaço do usuário ou no núcleo. não era adequado para um servidor de arquivos que usas- Os processos podem se comunicar uns com os outros se uma cache na memória. Por que não? Cada processo por meio de primitivas de comunicação entre processos, poderia ter sua própria cache? como semáforos, monitores ou mensagens. Essas unidades 7. Se um processo multithread bifurcar, há problemas se o básicas são usadas para assegurar que dois processos nunca filho copia todos os threads do pai. Suponha que um dos estarão em suas regiões críticas ao mesmo tempo uma threads originais estivesse esperando por uma entrada do</p><p>Capítulo 2 Processos e threads 103 teclado. Agora dois threads estão esperando pela entra- 18. Suponha que um sistema operacional não tenha uma da do teclado, um em cada processo. Esse problema pode chamada de sistema como a select para verificar previa- ocorrer em processos de thread único? mente se é seguro ler um arquivo, um pipe ou algum 8. Na Figura 2.6, é mostrado um servidor da Web multithread. dispositivo, mas ele permite que "alarm clocks" sejam Se o único modo de ler a partir de um arquivo for o bloqueio setados, os quais interrompem chamadas de sistema blo- normal da chamada de sistema read, você acha que threads queadas. É possível implementar um pacote de threads, no espaço de usuário, sob essas condições? Comente. de usuário ou de núcleo estão sendo usados para o servidor da Web? Por quê? 19. o problema de inversão de prioridades discutido na Seção 2.3.4 pode acontecer com threads de usuário? Por quê? 9. No texto, descrevemos um servidor da Web multithread, mostrando por que ele é melhor que um servidor de 20. Na Seção 2.3.4, foi descrita uma situação com um proces- thread único e um servidor de máquina de estados finitos. so de alta prioridade, H, e um de baixa prioridade, L, que Há alguma circunstância na qual um servidor de thread levava H a um laço infinito. o mesmo problema ocorreria único poderia ser melhor? Dê um exemplo. se fosse usado o escalonamento circular em vez do esca- lonamento por prioridades? Comente. 10. Na Tabela 2.4, o conjunto de registradores é relacionado como um item por thread, e não por processo. Por quê? 21. Em um sistema com threads, quando são utilizados threads (Afinal, a máquina tem somente um conjunto de regis- de usuário, há uma pilha por thread ou uma pilha por tradores.) processo? E quando se usam threads de núcleo? Explique. 11. o que faria um thread desistir voluntariamente da CPU 22. Quando um computador está sendo desenvolvido, ele é chamando hread_yield? (Afinal, como não há interrupção antes simulado por um programa que executa uma ins- periódica de relógio, ele pode nunca mais obter a CPU de trução por vez. Mesmo os multiprocessadores são simu- volta.) lados de modo estritamente sequencial. É possível que ocorra uma condição de corrida quando não há eventos 12. Um thread pode sofrer preempção por uma interrupção simultâneos como nessas simulações? de relógio? Em caso afirmativo, sob quais circunstâncias? Do contrário, por que não? 23. A solução de espera ociosa usando a variável turn (Figura 2.18) funciona quando os dois processos estão executan- 13. Neste problema, você deve comparar a leitura de um ar- do em um multiprocessador de memória compartilhada, quivo usando um servidor de arquivos monothread e um isto é, duas CPUs compartilhando uma memória comum? servidor multithread. São necessários 15 ms para obter uma requisição de trabalho, despachá-la e fazer o restante 24. A solução de Peterson para o problema da exclusão mú- do processamento necessário, presumindo que os dados tua, mostrado na Figura 2.19, funciona quando o escalo- essenciais estejam na cache de blocos. Se for necessá- namento do processo for preemptivo? E quando o escalo- ria uma operação de disco como ocorre em um terço namento não for preemptivo? das vezes - será preciso um tempo adicional de 75 ms, 25. Faça um esboço de como um sistema operacional capaz de durante o qual o thread dorme. Quantas requisições/se- desabilitar interrupções poderia implementar semáforos. gundo o servidor pode tratar se for monothread? E se for 26. Mostre como os semáforos contadores (isto é, os semá- multithread? foros que podem conter um valor arbitrário) podem ser 14. Qual a maior vantagem de implementar threads no espa- implementados usando somente semáforos binários e do usuário? Qual é a maior desvantagem? simples instruções de máquina. 15. Na Figura 2.10, as criações de threads e as mensagens 27. Se um sistema tem somente dois processos, tem sentido impressas pelos threads são intercaladas aleatoriamente. usar uma barreira para sincronizá-los? Por quê? Há algum modo de impor que a ordem seja estritamente 28. Dois threads podem, no mesmo processo, sincronizar a thread 1 criado, thread imprime mensagem, thread 1 sai, partir do uso de um semáforo de núcleo se os threads thread 2 criado, thread 2 imprime a mensagem, thread 2 forem implementados pelo núcleo? E se os threads fos- sai e assim por diante? Em caso de resposta afirmativa, qual sem implementados no espaço do usuário? (Suponha que é esse modo? Em caso de resposta negativa, por que não? nenhum thread em qualquer outro processo tenha acesso 16. Na discussão sobre variáveis globais em threads, usa- ao semáforo.) Comente suas respostas. mos uma rotina para alocar memória a um 29. Sincronização com monitores usa variáveis de condição ponteiro para a variável, em vez de alocar diretamente a e duas operações especiais, wait e signal. Uma forma mais própria variável. Isso é essencial ou as rotinas poderiam geral de sincronização seria ter uma única primitiva, funcionar muito bem apenas com os próprios valores? waituntil, que possuísse um predicado booleano como pa- 17. Considere um sistema no qual threads são implemen- râmetro. Assim, alguém poderia dizer, por exemplo, tados inteiramente no espaço do usuário, sendo que o waituntil ou sistema de tempo de execução sofre uma interrupção de relógio a cada segundo. Suponha que uma interrupção de A primitiva signal não seria mais necessária. Esse esque- relógio ocorra enquanto algum thread estiver executando ma é claramente mais geral que o proposto por Hoare ou no sistema de tempo de execução. Que problema poderia Brinch Hansen, mas não é utilizado. Por quê? Dica: pense ocorrer? o que você sugere para resolvê-lo? na implementação.</p><p>104 Sistemas operacionais modernos 30. Um restaurante de fast-food tem quatro tipos de empre- de execução estimados em 10, 6, 2, 4 e 8 minutos. Suas gados: (1) anotadores de pedido, que anotam o pedido prioridades (externamente determinadas) são 3, 5, 2, e dos clientes; (2) cozinheiros, que preparam a comida; (3) 4, respectivamente, sendo 5 a prioridade mais alta. Para embaladores, que colocam a comida nas sacolas; e (4) cai- cada um dos seguintes algoritmos de escalonamento, de- xas, que entregam as sacolas para os clientes e recebem termine o tempo médio de ida e volta. Ignore a sobrecarga o dinheiro deles. Cada empregado pode ser observado de chaveamento de processos. como um processo sequencial de comunicação. Qual for- (a) Circular. ma de comunicação entre processos eles usariam? Rela- (b) Escalonamento por prioridades. cione esse modelo aos processos no UNIX. (c) Primeiro a chegar, primeiro a ser servido (execute na or- 31. Imagine um sistema por troca de mensagens que use cai- dem 10, 6, 2, 4, 8). xas postais. Quando se envia para uma caixa postal cheia ou tenta-se receber de uma caixa postal vazia, um pro- (d) Tarefa mais curta primeiro. cesso não bloqueia. Na verdade, ele obtém um código de Para (a), presuma que o sistema é multiprogramado e que erro. o processo responde ao código de erro apenas ten- cada tarefa obtenha sua fração justa da CPU. Para os itens tando novamente, sucessivamente, até que ele consiga. (b) a (d), considere a execução de somente uma tarefa por Esse esquema leva a condições de corrida? vez, até que termine. Todas as tarefas são completamente limitadas pela CPU. 32. Os computadores CDC 6600 podiam lidar simultanea- mente com até dez processos de E/S, usando uma forma 38. Um processo executando no CTSS precisa de 30 quan- interessante de escalonamento circular chamada com- ta para terminar. Quantas vezes ocorrerá uma troca para partilhamento de processador. Um chaveamento de a memória, incluindo a primeira vez (antes de executar processo ocorria depois de cada instrução; assim, a instru- qualquer coisa)? ção 1 vinha do processo a instrução 2 vinha do proces- 39. Você tem ideia de como impedir que o sistema de priori- 2 e assim por diante. o chaveamento do processo era dade do CTSS seja enganado digitando-se a tecla feito por um hardware especial e a sobrecarga era zero. Se aleatoriamente? um processo precisasse de T segundos para terminar sua 40. o algoritmo do envelhecimento (aging) com 1/2 está execução, na ausência de competição, quanto tempo seria sendo usado para prever tempos de execução. As quatro necessário se o compartilhamento do processador fosse execuções anteriores, da primeira à mais recente, são 40, usado com n processos? 20, 40 e 15 ms. Qual é a previsão da próxima execução? 33. Seria possível estabelecer uma medida sobre o quanto um 41. Um sistema de tempo real tem quatro eventos periódicos processo é limitado pela CPU ou limitados por E/S anali- com períodos de 50, 100, 200 e 250 ms cada. Suponha sando o código-fonte? Como isso poderia ser determina- que os quatro eventos requeiram 35, 20, 10 e ms de do em tempo de execução? tempo de CPU, respectivamente. Qual é o maior valor de 34. Na seção escalonar', foi mencionado que, algu- para que o sistema seja escalonável? mas vezes, o escalonamento poderia ser melhorado se um 42. Explique por que o escalonamento em dois níveis é bas- processo importante fosse passível de desempenhar um tante usado. papel, ao ser bloqueado, na seleção do próximo processo 43. Um sistema de tempo real precisa controlar duas a executar. Pense em uma situação na qual isso poderia das de voz, cada uma delas executada a cada 5 ms e con- ser usado e explique como. sumindo 1 ms do tempo da CPU por surto, além de um 35. As medidas de um certo sistema mostram que o processo vídeo de 25 quadros/s, e cada quadro requer 20 ms do médio executa por um tempo T antes de ser bloqueado tempo da CPU. Esse sistema pode ser escalonado? para E/S. Um chaveamento de processos requer um tem- 44. Considere um sistema no qual se deseja separar a política po efetivamente gasto (sobrecarga). Para o escalona- e o mecanismo para o algoritmo de escalonamento dos mento circular com um quantum dê uma fórmula para threads de núcleo. Proponha um meio de chegar a esse a eficiência da CPU em cada um dos seguintes casos: objetivo. (a) 45. Na solução para o problema do jantar dos filósofos (Figura (b) Q>T. 2.38), por que é atribuído HUNGRY à variável de estado na rotina (c) S</p><p>Capítulo 2 Processos e threads 105 cada variação, especifique o que acontece quando um lei- Contudo, como uma concessão à tradição, ela decreta que, tor ou um escritor fica pronto para ter acesso ao banco de quando uma mulher estiver no banheiro, outra mulher dados e o que ocorre quando um processo acaba de usar poderá entrar, mas um homem não e vice-versa. Um sinal o banco de dados. com um marcador deslizante, na porta de cada banheiro, 48. Escreva um script do shell que produza um arquivo de indica em qual dos três estados o banheiro se encontra: números sequenciais lendo-se o último número no ar- Vazio quivo, adicionando-se a ele e, então, anexando-o ao Com mulher arquivo. Execute uma instância do script em background (segundo plano) e outra em foreground (primeiro plano), Com homem cada uma realizando acessos ao mesmo arquivo. Quanto Escreva, em sua linguagem de programação favorita, as tempo transcorre antes de se manifestar uma condição de seguintes rotinas: mulher_quer_entrar, disputa? Qual é a região crítica? Modifique o script para homem_sai Você pode usar os contadores e as impedir a disputa. (Dica: use técnicas de sincronização que quiser. In file file.lock 52. Reescreva o programa da Figura 2.18 para tratar mais de dois processos. para proteger o arquivo de dados.) 53. Escreva um problema produtor-consumidor que use 49. Imagine um sistema operacional que permita semáforos. threads e compartilhe um buffer comum. Contudo, não Implemente um sistema de mensagens. Escreva as rotinas use semáforos ou qualquer outra primitiva de sincroni- para enviar e receber mensagens. zação para proteger a estrutura de dados compartilhada. 50. Resolva o problema do jantar dos filósofos usando moni- Apenas deixe cada thread ter acesso a eles quando quiser. tores em vez de semáforos. Use sleep e wakeup para tratar as condições de buffer cheio 51. Suponha que uma universidade, para mostrar como é po- e buffer vazio. Veja quanto tempo leva até ocorrer uma liticamente correta, aplique a doutrina da Suprema Corte condição de disputa fatal. Por exemplo, você pode ter o dos Estados Unidos, "Separado mas igual é inerentemente produtor imprimindo um número a cada intervalo de desigual", para gênero e raça, pondo fim a sua prática de tempo. Não imprima mais do que um número a cada mi- longa data de banheiros no campus segregados por gênero. nuto, porque a E/S poderia afetar as condições de corrida.</p>