Sistemas Operacionais – Prof. Maur´ıcio Aronne Pillon – Semestre: 2008.2
Lista de Exerc´ıcios 1 — Comunica¸c˜ ao Interprocessos 1. [Silberschatz 1994, 6.5] Uma das formas de garantir exclus˜ ao m´ utua em uma se¸c˜ao cr´ıtica ´e desabilitando interrup¸c˜oes. Entretanto, isso pode afetar o rel´ ogio do sistema. Explique os motivos pelos quais isso ocorre e o que pode ser feito para minimizar o problema. 2. [Stevens 1998, 5.2] Algumas linguagens de programa¸c˜ao oferecem suporte a concorrˆencia por meio de um par de comandos parbegin. . . parend. Seja, por exemplo, o trecho de c´odigo abaixo: parbegin P1; P2; P3; parend
O uso de parbegin e parend indica que P1, P2 e P3 executam em paralelo, e podem ser escalonados em qualquer ordem (ou seja, P3 pode come¸car a executar antes de P1 e/ou de P2). Com base nisso, considere um programa concorrente com dois processos, P e Q, mostrados no c´odigo abaixo. A, B, C, D e E s˜ ao instru¸c˜oes atˆ omicas (indivis´ıveis) quaisquer. procedure P; begin A; B; C; end.
(* Programa principal *) parbegin P; Q; parend
procedure Q; begin D; E; end.
Determine todas as poss´ıveis seq¨ uˆencias de execu¸c˜ao dos dois processos acima (mostre as diferentes seq¨ uˆencias de instru¸c˜oes atˆ omicas que podem ocorrer). 3. [Stevens 1998, 5.3] Considere o programa abaixo: #define N 50 int soma; void total(void) { int cont; for (cont = 1; cont <= N; cont++) soma++; } main() { soma = 0; parbegin total(); total(); parend printf("A soma eh %d\n", soma); }
(a) Determine os limites inferior e superior para o valor final da vari´avel compartilhada soma exibido por esse programa concorrente. Suponha que os processos podem executar em velocidades relativas quaisquer e que uma opera¸c˜ao de incremento X++ ´e implementada por trˆes instru¸c˜oes de m´aquina: MOVE X, ACC INC ACC MOVE ACC, X
; copia X para o acumulador ; incrementa o acumulador ; copia o acumulador para X
(b) Suponha que um n´ umero arbitr´ario desses processos podem executar segundo as premissas da parte (a). Qual o efeito de tal modifica¸c˜ao na faixa de valores finais de soma? 4. [Stevens 1998, 5.4] A espera ocupada ´e sempre menos eficiente (em termos de utiliza¸c˜ao do processador) do que uma espera bloqueante? Explique.
1
5. [Oliveira 2004, 3.3] Descreva o erro na implementa¸c˜ao do produtor-consumidor mostrada abaixo. Crie uma seq¨ uˆencia de eventos que termina em algum comportamento indesejado para o programa. struct tipo_dado buffer[N]; int proxima_insercao = 0; int proxima_remocao = 0; ... semaphore exclusao_mutua = 1; semaphore espera_vaga = N; semaphore espera_dado = 0; ... void produtor(void) { ... down(&exclusao_mutua); down(&espera_vaga); buffer[proxima_insercao] = dado_produzido; proxima_insercao = (proxima_insercao + 1) % N; up(&exclusao_mutua); up(&espera_dado); ... } ... void consumidor(void) { ... down(&exclusao_mutua); down(&espera_dado); dado_a_consumir = buffer[proxima_remocao]; proxima_remocao = (proxima_remocao + 1) % N; up(&exclusao_mutua); up(&espera_vaga); ... }
6. [Oliveira 2004, 3.8] O problema dos leitores/escritores consiste de um texto que pode ser lido ou escrito por v´ arios processos. Considerando o c´odigo abaixo, responda justificando: ´ poss´ıvel v´ (a) E arios leitores lerem ao mesmo tempo? ´ poss´ıvel v´ (b) E arios escritores escreverem ao mesmo tempo? ´ poss´ıvel posterga¸c˜ao indefinida de um leitor? (A posterga¸c˜ao indefinida de um processo ocorre quando (c) E ele pode ser impedido de entrar em uma se¸c˜ao cr´ıtica por um tempo ilimitado, enquanto outros processos continuam entrando e saindo dessa se¸c˜ao cr´ıtica.) ´ poss´ıvel posterga¸c˜ao indefinida de um escritor? (d) E ´ poss´ıvel leitores e escritores acessarem ao mesmo tempo? (e) E int nl = 0; semaphore tipo = 1; semaphore exclusivo = 1; void leitor(void) { ... down(&exclusivo); if (nl > 0) ++nl; else { down(&tipo); nl = 1; } up(&exclusivo); acessa_texto(); down(&exclusivo); --nl; if (nl == 0) up(&tipo); up(&exclusivo); ... }
void escritor(void) { ... down(&tipo); acessa_texto(); up(&tipo); ... }
2
7. Com base no c´odigo mostrado no exerc´ıcio anterior, resolva o problema dos leitores/escritores eliminando posterga¸c˜ao indefinida. 8. Um dos problemas de sincroniza¸c˜ao mais conhecidos ´e o “jantar dos fil´osofos”, proposto por Dijkstra em 1965. Nesse problema, cinco fil´osofos sentam-se ao redor de uma mesa circular. Cada fil´osofo tem diante de si um prato de macarr˜ao, e entre cada par de pratos existe um garfo (veja a figura abaixo). Um fil´osofo pode estar meditando ou comendo. Quando um fil´osofo deseja comer, ele tenta pegar dois garfos (´e imposs´ıvel comer o macarr˜ao com um u ´nico garfo), o que est´ a ` a sua direita e o que est´ a `a sua esquerda, em qualquer ordem, um de cada vez (n˜ao ´e poss´ıvel pegar os dois garfos ao mesmo tempo). Se o fil´osofo consegue pegar os garfos, ele come durante um tempo e depois larga os garfos na mesa. O problema consiste em escrever um programa que represente o comportamento dos fil´osofos, e que n˜ao entre em impasse (deadlock ). (Dica: considere a possibilidade de limitar o n´ umero de fil´osofos que tentam comer ao mesmo tempo.)
9. Considere o problema da aloca¸c˜ao de arm´ arios de a¸co na biblioteca da UDESC. Existe um n´ umero fixo NARM de arm´ arios. Normalmente, um usu´ario que chega `a biblioteca e deseja um arm´ ario solicita ao funcion´ ario respons´ avel a chave de um dos arm´ arios desocupados. Caso n˜ao haja um arm´ ario livre, o usu´ario espera em uma fila at´e que algum arm´ ario seja desocupado. Para eliminar a necessidade de um funcion´ ario para a distribui¸c˜ao de chaves, um aluno de SOP desenvolveu o seguinte algoritmo, baseado em sleep() e wakeup(): int armarios[NARM], ocupados = 0; void usuario(int i) { int a;
/* n´ umero do arm´ ario ocupado pelo usu´ ario */
if (ocupados == N) sleep(ocupados); ocupados++; for (a = 0; (a < NARM) && (armarios[a] != 0); a++) ; /* percorre o vetor at´ e achar um arm´ ario livre */ armarios[a] = i; estuda(); armarios[a] = 0; ocupados--; if (ocupados == N-1) wakeup(ocupados); }
Esse algoritmo resolve o problema corretamente? Quais erros vocˆe consegue apontar nessa solu¸c˜ao, se ´e que eles existem? Demonstre o(s) erro(s) mostrando seq¨ uˆencias de execu¸c˜ao que causem problemas. Obs.: O uso de ocupados como parˆ ametro de sleep() e wakeup() n˜ao constitui um erro. 10. Resolva o problema de aloca¸c˜ao de arm´ arios do exerc´ıcio anterior usando sem´ aforos. 11. Suponha que a biblioteca do seu compilador C possui uma instru¸c˜ao swap(&v1, &v2), que troca atomicamente o conte´ udo de duas vari´aveis v1 e v2. Mostre como implementar fun¸c˜oes enter_region() e leave_region() para garantir exclus˜ ao m´ utua em regi˜ oes cr´ıticas usando a fun¸c˜ao swap() e uma vari´avel compartilhada lock. N˜ ao se preocupe em eliminar espera ocupada da sua solu¸c˜ao.
3
12. O algoritmo abaixo implementa um servidor de rede multithread. O servidor possui uma thread despachante, que recebe requisi¸c˜oes da rede, e v´ arias threads oper´ arias, que processam essas requisi¸c˜oes. Ao receber uma requisi¸c˜ao da rede, a thread despachante localiza a oper´ aria op com a menor fila de requisi¸c˜oes pendentes e entrega a nova requisi¸c˜ao para essa thread, inserindo-a na fila associada `a thread (dada por fila_req[op]). O prop´osito disso ´e obter um melhor balanceamento de carga entre as threads oper´ arias. A vari´avel fila_req ´e um vetor de filas circulares de requisi¸c˜oes, que s˜ ao representadas pela estrutura FilaReq. Os campos dessa estrutura s˜ ao inicio, que armazena o ´ındice do pr´oximo elemento a ser retirado (in´ıcio da fila), fim, que armazena o ´ındice onde ser´a inserido o pr´oximo elemento (final da fila), tam, que armazena o tamanho da fila, e req, que ´e um vetor de requisi¸c˜oes com MAXREQ posi¸c˜oes. Para simplificar a implementa¸c˜ao, pode-se supor que o vetor de requisi¸c˜oes nunca fica cheio (ou seja, n˜ao ´e preciso tratar overflow ). Com base nesse algoritmo, responda: (a) Quais s˜ ao as se¸c˜oes cr´ıticas existentes no algoritmo? (Use os n´ umeros de linhas.) (b) Mostre ao menos uma seq¨ uˆencia de execu¸c˜ao que pode provocar um comportamento indesejado no algoritmo. (c) Usando as fun¸c˜oes enter_region() e leave_region() implementadas no exerc´ıcio 11, elimine as condi¸c˜oes de disputa existentes no algoritmo. 1 2
#define MAXOPER 10 #define MAXREQ 100
/* n´ umero de threads oper´ arias */ /* n´ umero m´ aximo de requisi¸ c~ oes na fila */
3 4 5 6 7
struct FilaReq { int inicio, fim, tam; Req reqs[MAXREQ]; };
8 9
struct FilaReq fila_req[MAXOPER];
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
void despachante() { Req r; int i, op, tam, menor; while (TRUE) { r = espera_nova_req(); /* aguarda uma requisi¸ c~ ao da rede */ op = 0; /* encontra a oper´ aria com a menor fila */ menor = fila_req[0].tam; for (i = 1; i < MAXOPER; i++) { if (fila_req[i].tam < menor) { menor = fila_req[i].tam; op = i; /* op ´ e a oper´ aria com menor fila */ } } fila_req[op].req[fim] = r; /* insere r no final de fila_req[op] */ fila_req[op].fim = (fila_req[op].fim + 1) % MAXREQ; fila_req[op].tam++; } }
30 31 32 33
void operaria(int op) { Req r;
34
while (TRUE) { while (fila_req[op].tam == 0) /* espera que a fila cres¸ ca */ ; /* loop vazio */ r = fila_req[op].req[inicio]; /* retira a primeira requisi¸ c~ ao da fila */ fila_req[op].inicio = (fila_req[op].inicio + 1) % MAXREQ; fila_req[op].tam--; processa_req(r); }
35 36 37 38 39 40 41 42 43
}
13. Modifique o algoritmo anterior de forma a eliminar condi¸c˜oes de disputa e espera ocupada usando sem´aforos.
4