Algoritmos de Escalonamento

Processos: P1(burst=6), P2(burst=3), P3(burst=8), P4(burst=2)
Chegada:   todos em t=0, ordem P1, P2, P3, P4

Gantt Chart:
|====P1====|==P2==|=====P3=====|=P4=|
0          6      9            17   19

Processo  Chegada  Burst  Inicio  Fim  Turnaround  Waiting
P1        0        6      0       6    6           0
P2        0        3      6       9    9           6
P3        0        8      9       17   17          9
P4        0        2      17      19   19          17

Media Turnaround: (6 + 9 + 17 + 19) / 4 = 12.75
Media Waiting:    (0 + 6 + 9 + 17) / 4  = 8.0

Mesmos processos: P1(6), P2(3), P3(8), P4(2), todos em t=0

SJF ordena por burst: P4(2), P2(3), P1(6), P3(8)

Gantt Chart:
|P4|==P2==|====P1====|=====P3=====|
0  2      5          11           19

Processo  Burst  Inicio  Fim  Turnaround  Waiting
P4        2      0       2    2           0
P2        3      2       5    5           2
P1        6      5       11   11          5
P3        8      11      19   19          11

Media Turnaround: (2 + 5 + 11 + 19) / 4 = 9.25
Media Waiting:    (0 + 2 + 5 + 11) / 4  = 4.5

Comparacao: FCFS waiting = 8.0, SJF waiting = 4.5
SJF e OTIMO para minimizar waiting time medio.

Processos com chegadas diferentes:
P1(burst=8, chegada=0), P2(burst=4, chegada=1),
P3(burst=2, chegada=2), P4(burst=1, chegada=3)

t=0: P1 comeca (unico na fila)
t=1: P2 chega. P1 restante=7, P2=4. P2 < P1 restante: preempcao!
t=2: P3 chega. P2 restante=3, P3=2. P3 < P2: preempcao!
t=3: P4 chega. P3 restante=1, P4=1. Empate, P3 continua.
t=4: P3 termina. P4=1 < P2=3 < P1=7. P4 roda.
t=5: P4 termina. P2=3 < P1=7. P2 roda.
t=8: P2 termina. P1 roda.
t=15: P1 termina.

|=P1=|=P2=|P3|P4|==P2==|=======P1=======|
0    1    2  4 5       8               15

Media Waiting: (7 + 1 + 0 + 0) / 4 = 2.0
(P1 esperou de t=1 a t=8 = 7; P2: t=2 a t=4 + nada = 2-1=1; P3,P4: 0)

Processos: P1(burst=6), P2(burst=3), P3(burst=8), P4(burst=2), todos em t=0
Quantum = 3

t=0:  Ready=[P1,P2,P3,P4]. P1 roda por 3 (restante=3)
t=3:  Ready=[P2,P3,P4,P1]. P2 roda por 3 (termina)
t=6:  Ready=[P3,P4,P1].    P3 roda por 3 (restante=5)
t=9:  Ready=[P4,P1,P3].    P4 roda por 2 (termina, < quantum)
t=11: Ready=[P1,P3].       P1 roda por 3 (termina)
t=14: Ready=[P3].           P3 roda por 3 (restante=2)
t=17: Ready=[P3].           P3 roda por 2 (termina)

|==P1==|==P2==|==P3==|P4|==P1==|==P3==|P3|
0      3      6      9  11     14     17 19

Processo  Turnaround  Waiting
P1        14          8
P2        6           3
P3        19          11
P4        11          9

Media Waiting: (8 + 3 + 11 + 9) / 4 = 7.75

Importante: quantum grande = FCFS. Quantum pequeno = muito overhead.
Regra pratica: quantum entre 10-100ms.

Fila 0 (maior prioridade, quantum = 4ms):
+----+  +----+  +----+
| P1 |  | P5 |  | P9 |     Processos novos e I/O-bound
+----+  +----+  +----+     entram aqui

Fila 1 (prioridade media, quantum = 8ms):
+----+  +----+
| P3 |  | P7 |             Se usa todo quantum da Fila 0,
+----+  +----+             desce para Fila 1

Fila 2 (menor prioridade, quantum = 16ms):
+----+  +----+  +----+  +----+
| P2 |  | P4 |  | P6 |  | P8 |   CPU-bound eventualmente
+----+  +----+  +----+  +----+   caem aqui (FCFS dentro da fila)

Regras do MLFQ:
1. Se A esta em fila acima de B: A roda primeiro
2. Se A e B estao na mesma fila: Round Robin
3. Novo processo entra na Fila 0 (maior prioridade)
4. Se o processo usa todo seu quantum: desce uma fila
5. Se o processo faz I/O antes do quantum: fica na mesma fila
6. Periodicamente: todos sobem para Fila 0 (priority boost)

A regra 6 previne starvation de processos CPU-bound!

Processo  Bilhetes  Probabilidade
P1        75        75/100 = 75%
P2        15        15/100 = 15%
P3        10        10/100 = 10%
          ---
Total:    100

Sorteio: numero aleatorio entre 0-99
  0-74  = P1 roda
  75-89 = P2 roda
  90-99 = P3 roda

Vantagens:
  - Proporcionalidade: tempo de CPU ~ numero de bilhetes
  - Sem starvation: todo processo com >0 bilhetes roda eventualmente
  - Simples de implementar
  - Ticket transfer: processos podem doar bilhetes (ex: cliente-servidor)

| Algoritmo | Preemptivo | Starvation | Caso de uso      | Complexidade |
|-----------|------------|------------|------------------|--------------|
| FCFS      | Nao        | Nao        | Batch simples    | O(1)         |
| SJF       | Nao        | Sim        | Batch otimizado  | O(n)         |
| SRTF      | Sim        | Sim        | Batch otimizado  | O(n)         |
| RR        | Sim        | Nao        | Interativo       | O(1)         |
| MLFQ      | Sim        | Nao*       | Uso geral        | O(1)         |
| Lottery   | Sim        | Nao        | Proporcional     | O(n)         |

* MLFQ: sem starvation se tiver priority boost periodico

class RequestMLFQ:
    """Multi-Level Feedback Queue para requests do harness."""

    def __init__(self):
        self.queues = {
            0: [],  # Alta: bugs, hotfixes (quantum: 1 sessao curta)
            1: [],  # Media: features (quantum: 1 sessao normal)
            2: [],  # Baixa: refactoring, docs (quantum: 1 sessao longa)
        }

    def add_request(self, request):
        # Novos requests entram na fila 0 (como MLFQ)
        self.queues[0].append(request)

    def schedule_next(self):
        # Processa filas de maior prioridade primeiro
        for priority in [0, 1, 2]:
            if self.queues[priority]:
                return self.queues[priority].pop(0)
        return None

    def demote(self, request):
        """Request nao completou na sessao: desce de fila."""
        new_priority = min(request.priority + 1, 2)
        self.queues[new_priority].append(request)

    def priority_boost(self):
        """Periodicamente, sobe tudo pra fila 0 (anti-starvation)."""
        for q in [1, 2]:
            self.queues[0].extend(self.queues[q])
            self.queues[q] = []