escalonamento_e_sincronizacao

Prévia do material em texto

Sistemas Operacionais – Lista de Exerc´ıcios
Escalonamento e Sincronizac¸a˜o de Processos
1. Na figura mostrada abaixo, sa˜o mostrados treˆs estados de processo. Na teoria, com treˆs estados de
processos, poderia haver seis transic¸o˜es, duas para cada estado. Contudo, apenas quatro transic¸o˜es
sa˜o mostradas. Ha´ alguma circunstaˆncia na qual uma delas ou ambas as transic¸o˜es na˜o ilustradas
possam ocorrer?
2. Suponha as seguintes tarefas em lote:
ID Tempo de Chegada Tempo Necessa´rio Prioridade
1 2 10 3
2 3 6 5
3 1 2 2
4 5 4 1
5 4 8 4
Para cada algoritmo abaixo, calcule: tempo de resposta (turnaround) e tempo de espera para cada
processo, tempo de resposta me´dio e tempo de espera me´dio.
(a) Round-Robin com quantum 2;
(b) Escalonamento por prioridades preemptivo;
(c) FCFS;
(d) SJF;
(e) SRTN.
Se a tabela listada representasse um contexto comum de um SO, qual algoritmo de escalonamento
voceˆ escolheria? Justifique.
3. Cinco tarefas em lote, de A ate´ E, chegam em um centro de computac¸a˜o ao mesmo tempo. Elas
tem um tempo estimado de 15, 9, 3, 6 e 12 minutos, respectivamente. Suas prioridades sao 6, 3, 7, 9
e 4 respectivamente. Quanto menor o valor de prioridade, mais prioritario e´ o processo. Para cada
um dos algoritmos de escalonamento abaixo, determine o tempo de resposta para cada processo e
o tempo de resposta me´dio. Ignore o tempo de troca de contexto. Mostre como voceˆ chegou nas
respostas. Assuma que os treˆs u´ltimos escalonadores na˜o sa˜o preemptivos.
(a) Round robin com quantum = 1 minuto;
(b) Escalonamento por prioridades;
(c) FCFS (de acordo com a ordem mostrada no enunciado);
(d) SJF.
4. A maioria dos escalonadores round-robin usam um quantum fixo. Deˆ um argumento em favor de um
quantum pequeno. Agora deˆ um argumento em favor de um quantum grande. Compare e contraste
os tipos de sistemas e tarefas para os quais os argumentos se aplicam. Ha´ argumentos que se aplicam
para qualquer sistema?
1
5. Tarefas mu´ltiplas podem ser executadas paralelamente e terminar mais ra´pido do que se tivessem
sido executadas sucessivamente. Suponha que duas tarefas, cada uma precisando de dez minutos do
tempo da CPU, comec¸assem simultaneamente. De quanto tempo a u´ltima precisara´ para terminar se
elas forem executadas sucessivamente? Quanto tempo se forem executadas paralelamente? Suponha
50% de tempo de espera de E/S.
6. A Figura abaixo mostra um servidor da Web multithread:
Na Figura, uma thread despachante leˆ as requisic¸o˜es de trabalho que chegam da rede. Depois de
examinar a requisic¸a˜o, ele escolhe uma thread opera´rio ocioso (isto e´, bloqueado) e entrega-lhe
a requisic¸a˜o. O despachante enta˜o acorda o opera´rio que esta´ descansando, colocando-o no estado
de pronto. Quando desperta, o opera´rio verifica se a requisic¸a˜o pode ser satisfeita pela cache de
pa´ginas da Web, a` qual todos as threads tem acesso. Se na˜o puder, ele inicializara´ uma operac¸a˜o de
read para obter a pa´gina do disco e permanecera´ bloqueado ate´ a operac¸a˜o de disco terminar.
Voceˆ acha que threads de usua´rio ou de nu´cleo esta˜o sendo usadas para os servidor da Web? Por
queˆ?
7. Durante as aulas vimos que o conjunto de registradores e´ relacionado como um item por thread, e
na˜o por processo. Por queˆ? (Afinal, a ma´quina tem somente um conjunto de registradores).
8. Uma thread pode sofrer preempc¸a˜o por uma interrupc¸a˜o de relo´gio? Em caso afirmativo, sob quais
circunstaˆncia? Do contra´rio, por que na˜o?
9. Qual a maior vantagem de implementar threads no espac¸o do usua´rio? Qual a maior desvantagem?
2
10. Considere o co´digo abaixo:
A criac¸a˜o das threads e as mensagens impressas pelos threads sa˜o intercaladas aleatoriamente. Ha´
algum modo de impor que a ordem seja estritamente thread 1 criado, thread 1 imprime a mensagem,
thread 1 sai, thread 2 criado, thread 2 imprime, thread 2 sai e assim por diante? Em caso de resposta
afirmativa, qual e´ esse modo? Em caso de resposta negativa, por que na˜o?
11. O problema da inversa˜o de prioridades, que acontece com protocolos de sec¸a˜o cr´ıtica que utilizam
espera ocupada, ocorreria se fosse usado o escalonamento circular em vez do escalonamento por
prioridades? Comente.
12. Em um sistema com threads, quando sa˜o utilizados threads de usua´rio, ha´ uma pilha por thread ou
uma pilha por processo? E quando se usam threads de nu´cleo? Explique
13. A soluc¸a˜o de espera ociosa usando a varia´vel turn funciona quando os dois processos esta˜o executando
em um multiprocessador de memo´ria compartilhada, isto e´, duas CPUs compartilhando uma
memo´ria comum?
14. A soluc¸a˜o de Peterson para o problema da exclusa˜o mu´tua funciona quando o escalonamento do
processo for preemptivo? E quando o escalonamento na˜o for preemptivo?
15. Fac¸a um esboc¸o de como um sistema operacional capaz de desabilitar interrupc¸o˜es poderia
implementar sema´foros.
16. Se um sistema tem somente dois processos, tem sentido usar uma barreira para sincroniza´-los? Por
queˆ?
17. E´ aceita´vel utilizar sema´foros quando as threads sa˜o implementadas no espac¸o do kernel? E no
espac¸o do usua´rio? Comente.
18. Ate´ que ponto e´ poss´ıvel estabelecer uma medida sobre quanto um processo e´ limitado pela CPU
ou limitado por E/S analisando o co´digo fonte?
19. Cinco tarefas esta˜o esperando para serem executadas. Seus tempos de execuc¸a˜o previstos sa˜o 9, 6,
3, 5 e X. Em que ordem elas deveriam ser executadas para minimizar o tempo me´dio de resposta?
(Sua resposta dependera´ de X).
3