[GUIDE] Dongles (heap‐queue e scheduler)

Aqui é onde iremos usar a priority queue que descrevo no [GUIDE] Heap (priority queue). É importante dizer que cada dongle terá uma propriedade wait_queue, que é um t_heap, ou seja, cada dongle terá sua própria fila de espera/priority queue.
O fluxo aqui será:

1. Coder pede dongles em ordem crescente por id (explicação na seção abaixo sobre deadlocks).
2. Se dongle estiver livre, sem nós na fila de espera e sem cooldown:
   1. Coder recebe o dongle imediatamente
3. Se dongle não estiver livre, tiver nós na fila de espera e/ou estiver em cooldown:
   1. É criado um t_heap_node, que consiste do Coder, Prioridade, que é decidida com base no scheduler (FIFO, priority = get_current_time(), ou EDF, priority = last_compile + time_to_burnout), e seq, um contador que serve para desempates em caso de prioridades iguais.
   2. O nó é colocado na fila e sua posição é decidida conforme as regras da fila, definido na Prioridade com base no scheduler.
   3. A thread do Coder desse nó dorme, com pthread_cond_wait caso o cooldown do dongle tenha terminado, mas o dongle já esteja ocupado novamente, ou com pthread_cond_timedwait caso esteja livre, mas em cooldown. No primeiro caso a thread só irá acordar com um pthread_cond_broadcast, no segundo pode ser tanto por isso quanto pelo tempo definido para espera, nesse caso o cooldown restante.
   4. Quando o dongle é liberado, todos as threads de cada nó da fila acordam e disputam. Com disputar quero dizer que cada uma vai disputar pelo mutex do dongle em questão e aquela que conseguir vai passar pela seguinte verificação: a simulação ainda continua? O dongle está de fato livre? O dongle não está em cooldown? Sou a primeira (head) da fila? A Thread que responder sim a todas essas perguntas vence a disputa. Quem perde, volta a dormir.
   5. A thread vencedora se retira da fila (pop) e marca o dongle como ocupado, adquirindo o dongle. Depois disso, os dois logs de (Coder X has taken a dongle) disparam.

Esse fluxo irá se repetir a cada vez que um dongle ocupado for liberado. Agora, resta uma pergunta:

Como evitar deadlock?

Existem múltiplas formas, mas a usada na minha implementação é fazer com que os coders sempre peçam primeiro o dongle com menor id e depoiis o dongle com maior id. Os coders sempre vão pedir os dois, mas é importante que o de menor id seja requisitado primeiro para evitar a seguinte situação:

Coder	Dongles	Pedidos em ordem
1	{0, 1}	0 → 1
2	{1, 2}	1 → 2
3	{2, 3}	2 → 3
4	{3, 0}	3 → 0

Consegue ver o problema aqui? Coder 1 está esperando para receber o dongle 1, que está com Coder 2, que por sua vez está esperando pelo dongle 2, que está com o Coder 3, que espera pelo dongle 3. O problema é que o Coder 4 está com o dongle 3 e esperando pelo dongle 0, que está com o Coder 1, mas o Coder 1 só vai o largar quando adquirir o dongle 1 e compilar.
Coder 1 nunca vai compilar porque nunca vai adquirir o dongle 1, isso introduz um deadlock. Todos estão segurando 1 dongle e esperando por um segundo dongle que nunca vai chegar. Agora, mudando a ordem de requisição:

Coder	Dongles	Pedidos em ordem
1	{0, 1}	0 → 1
2	{1, 2}	1 → 2
3	{2, 3}	2 → 3
4	{3, 0}	0 → 3

Agora, o Coder 4 não segura nenhum dongle, tendo em vista que sua primeira requisição, o dongle 0, ainda não foi finalizada. Então, o Coder 3 consegue pegar o dongle 3 e compilar. O que possibilita o Coder 2, após o Coder 3 terminar de compilar e largar os dongles, de receber o dongle 2. E então, o Coder 1 a receber o dongle 1, compilar e liberar o dongle 0 para o Coder 4, que finalmente compila.
Esse fluxo não causa deadlock, todos compilam e seguem o ciclo até o final da simulação. É importante manter tudo isso em mente.