Alarm Clock (PintOS)

Implementei uma melhoria ao alarm clock do PintOS, um kernel didático para x86 usado nas aulas de Sistemas Operacionais. O objetivo era fazer o timer_sleep() dormir de verdade: a versão padrão resolvia a espera girando em thread_yield() até o prazo passar, e o trabalho era trocar esse busy-wait por bloqueio de thread.

O problema do busy-wait

O timer_sleep() original não errava o tempo, mas esperava ocupando a CPU. A cada iteração ele devolvia o processador com thread_yield() e voltava para a fila de prontos, então a thread passava toda a espera na ready_list. O efeito colateral era o que incomodava: a thread idle quase nunca era escolhida, o escalonador trocava de contexto a cada iteração do laço (milhares de vezes por tick, já que cada iteração cabe em microssegundos) só para acordar uma thread que ia conferir o relógio e dormir de novo, e o tempo gasto aparecia contado como kernel ticks em vez de ociosos.

A fila de dorminhocos

Em vez de esperar girando, a thread passa a se bloquear. Criei em devices/timer.c uma fila única de dorminhocos, ordenada pelo tick absoluto em que cada thread deve acordar. Ao chamar timer_sleep(), a thread grava o próprio prazo, entra na fila e chama thread_block(); a partir daí ela sai da fila de prontos e deixa de existir para o escalonador até alguém desbloqueá-la.

Quem desbloqueia é o handler do tick do timer. Como a fila está ordenada, ele só precisa olhar a frente: enquanto o primeiro prazo já venceu, retira a thread e a devolve à fila de prontos.

static void
timer_interrupt (struct intr_frame *args UNUSED)
{
  ticks++;
  thread_tick ();

  while (!list_empty (&sleep_list))
    {
      struct thread *t = list_entry (list_front (&sleep_list), struct thread, sleep_elem);

      if (t->wakeup_ticks > ticks)
        break;

      list_pop_front (&sleep_list);
      thread_unblock (t);
    }
}

Os trechos de código desta página estão normalizados no estilo do PintOS, com espaço antes dos parênteses de chamada. No repositório, o trecho que escrevi usa a forma sem espaço (thread_current()). Eu poderia ter mudado no repo também, mas fiquei com preguiça

O custo por tick passa a depender de quantas threads acordam naquele tick, e não de quantas estão dormindo. O teste alarm-simultaneous, por exemplo, tem três threads com o mesmo prazo: todas são liberadas numa única passada do laço.

Dois campos no TCB

Para carregar o próprio prazo e poder estar numa segunda lista, a thread ganhou dois campos em threads/thread.h: wakeup_ticks (o prazo absoluto, no mesmo relógio de timer_ticks()) e sleep_elem (o elemento de ligação na fila).

O sleep_elem precisou ser um campo separado, e não um reaproveitamento do elem que a thread já usa. O struct list_elem guarda os ponteiros da lista dentro dele mesmo, então um elemento só pode pertencer a uma lista por vez. Reutilizar o elem significaria que qualquer caminho do kernel que escreve nele (fila de prontos, semáforos, doação de prioridade) poderia corromper a fila de dorminhocos. São 16 bytes a mais por thread, e o comentário do próprio arquivo lembra que o TCB divide uma página de 4 kB com a pilha do kernel, então o acréscimo é irrelevante.

A seção crítica

Essa parte do timer_sleep() roda com as interrupções desligadas, que é o correto.

void
timer_sleep (int64_t ticks)
{
  struct thread *cur = thread_current ();
  enum intr_level old_level;

  ASSERT (intr_get_level () == INTR_ON);
  if (ticks <= 0)
    return;

  old_level = intr_disable ();
  cur->wakeup_ticks = timer_ticks () + ticks;
  list_insert_ordered (&sleep_list, &cur->sleep_elem, wakeup_less, NULL);
  thread_block ();
  intr_set_level (old_level);
}

A seção crítica é obrigatória por dois motivos. O primeiro é um contrato: thread_block() exige que as interrupções estejam desligadas, e aborta o kernel se não estiverem. O segundo é uma corrida que sobra mesmo num build sem asserts. Existe uma janela entre inserir a thread na fila e ela efetivamente se bloquear; se um tick cai nessa janela e o prazo é justamente aquele tick, como em timer_sleep (1), o handler vê o prazo vencido e chama thread_unblock() numa thread cujo status ainda é RUNNING. Desligar as interrupções faz ler o relógio, entrar na fila e bloquear valerem como uma operação só do ponto de vista do handler.

Validação

Rodei os cinco testes de alarm disponíveis (o alarm-priority fica de fora, como explico nas limitações), que criam threads com durações fixas e conferem a ordem em que elas acordam. A evidência mais direta de que o busy-wait sumiu são os contadores do próprio kernel: thread_tick() incrementa exatamente um entre idle, kernel e user a cada tick, então o total do Timer: é sempre a soma dos três. No alarm-single, 250 dos 272 ticks foram ociosos; no alarm-multiple, 550 de 578. Com o busy-wait, esperaria-se que esses mesmos ticks aparecessem como kernel ticks e que o ocioso ficasse perto de zero, que é justamente o comportamento que o projeto pedia para eliminar.

Limitações

• alarm-priority não passa. O teste espera que as threads acordem em ordem de prioridade e depende de o thread_unblock() inserir na fila de prontos de forma ordenada, o que ele não faz hoje. Isso é escopo do projeto de escalonamento por prioridade, não do alarm clock.
• Não funciona em multiprocessador. Desligar interrupções só afeta o núcleo local; num SMP a fila precisaria de um spinlock, e o contador global de ticks também precisaria de proteção.

Pontos de melhoria

• Trocar a lista ordenada por um heap mínimo deixaria a inserção O(log n) em vez de O(n). Não compensa aqui: a API de listas do PintOS só oferece inserção ordenada e o número de threads dormindo ao mesmo tempo é pequeno.
• Proteger a fila com um spinlock por fila para suportar multiprocessador.