Gabriel Rocha
Projects

Alarm Clock (PintOS)

Implementation of the PintOS alarm clock: replacing the timer_sleep busy-wait with a queue of blocked threads, ordered by deadline.

2026Repository

I implemented an improvement to the PintOS alarm clock, a didactic kernel for x86 used in Operating Systems classes. The goal was to make timer_sleep() actually sleep: the default version handled the wait by spinning in thread_yield() until the deadline passed, and the work was to replace that busy-wait with thread blocking.

The busy-wait problem

The original timer_sleep() did not get the timing wrong, but it waited while consuming the CPU. On every iteration it gave the processor back with thread_yield() and returned to the ready queue, so the thread spent the entire wait in the ready_list. The side effect was what bothered me: the idle thread was almost never chosen, the scheduler switched context on every iteration of the loop (thousands of times per tick, since each iteration fits in microseconds) just to wake a thread that would check the clock and go back to sleep, and the time spent showed up counted as kernel ticks instead of idle ones.

The sleepy queue

Instead of waiting by spinning, the thread now blocks. I created in devices/timer.c a single sleepy queue, ordered by the absolute tick at which each thread should wake up. When calling timer_sleep(), the thread records its own deadline, enters the queue and calls thread_block(); from then on it leaves the ready queue and ceases to exist for the scheduler until someone unblocks it.

The one that unblocks is the timer tick handler. Since the queue is ordered, it only needs to look at the front: while the first deadline has already expired, it removes the thread and returns it to the ready queue.

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);
    }
}

The code snippets on this page are normalized to the PintOS style, with a space before the call parentheses. In the repository, the snippet I wrote uses the form without a space (thread_current()). I could have changed it in the repo as well, but I was too lazy

The cost per tick now depends on how many threads wake up on that tick, and not on how many are sleeping. The alarm-simultaneous test, for example, has three threads with the same deadline: they are all released in a single pass of the loop.

Two fields in the TCB

To carry its own deadline and to be able to be in a second list, the thread gained two fields in threads/thread.h: wakeup_ticks (the absolute deadline, on the same clock as timer_ticks()) and sleep_elem (the link element in the queue).

sleep_elem had to be a separate field, and not a reuse of the elem the thread already uses. struct list_elem stores the list pointers inside itself, so an element can belong to only one list at a time. Reusing elem would mean that any kernel path that writes to it (ready queue, semaphores, priority donation) could corrupt the sleepy queue. That is 16 extra bytes per thread, and the comment in the file itself reminds us that the TCB shares a 4 kB page with the kernel stack, so the increase is irrelevant.

The critical section

This part of timer_sleep() runs with interrupts disabled, which is the correct thing.

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);
}

The critical section is mandatory for two reasons. The first is a contract: thread_block() requires interrupts to be disabled, and aborts the kernel if they are not. The second is a race that remains even in a build without asserts. There is a window between inserting the thread into the queue and it effectively blocking; if a tick falls in that window and the deadline is exactly that tick, as in timer_sleep (1), the handler sees the deadline as expired and calls thread_unblock() on a thread whose status is still RUNNING. Disabling interrupts makes reading the clock, entering the queue and blocking count as a single operation from the handler’s point of view.

Validation

I ran the five available alarm tests (alarm-priority is left out, as I explain in the limitations), which create threads with fixed durations and check the order in which they wake up. The most direct evidence that the busy-wait is gone are the kernel’s own counters: thread_tick() increments exactly one of idle, kernel and user on every tick, so the Timer: total is always the sum of the three. In alarm-single, 250 of the 272 ticks were idle; in alarm-multiple, 550 of 578. With the busy-wait, one would expect those same ticks to show up as kernel ticks and the idle time to be close to zero, which is precisely the behavior the project asked to eliminate.

Limitations

Improvement points