Laboratório 1
Starvation no algoritmo de Dijkstra
Entrega
Este laboratório não precisa ser entregue, mas quem quiser poderá
publicar sua solução na ferramenta colaborativa que será
disponibilizada.
Objetivo
Em 1965 Dijkstra publicou uma solução para o problema de exclusão mútua
para N threads.
int vez = -1, interesse[N] = {false, ..., false}
while (true) { /* Código da Thread_i */
interesse[i] = true;
while (existe j!=i tal que (interesse[j]))
if (vez != i)
interesse[i] = false;
while (vez != -1);
vez = i;
interesse[i] = true;
s = i;
print ("Thr ", i, ": ", s);
vez = -1
interesse[i] = false;
No entanto, esta solução está sujeita a starvation. Modifique a
implementação do algoritmo vista em
aula apenas com comandos sleep (podem ser diferentes para cada thread)
para ilustrar o starvation.
Exemplos:
- Trecho de código válido:
if (thr_id == 3)
sleep(1);
- Trecho de código inválido:
if (thr_id == 3)
sleep(1000000); /* dorme para sempre e não come nada... */
- Trecho de código inválido:
if (thr_id != 3)
vez = i; /* Nunca passa a vez para thread 3 */