2.2.2 Alarm Clock

[kswgit]

https://web.stanford.edu/class/cs140/projects/pintos/pintos_2.html#SEC15

Reimplement timer_sleep(), defined in devices/timer.c. Although a working implementation is provided, it "busy waits," that is, it spins in a loop checking the current time and calling thread_yield() until enough time has gone by. Reimplement it to avoid busy waiting.
Function: void timer_sleep (int64_t ticks)
Suspends execution of the calling thread until time has advanced by at least x timer ticks. Unless the system is otherwise idle, the thread need not wake up after exactly x ticks. Just put it on the ready queue after they have waited for the right amount of time.
timer_sleep() is useful for threads that operate in real-time, e.g. for blinking the cursor once per second.

The argument to timer_sleep() is expressed in timer ticks, not in milliseconds or any another unit. There are TIMER_FREQ timer ticks per second, where TIMER_FREQ is a macro defined in devices/timer.h. The default value is 100. We don't recommend changing this value, because any change is likely to cause many of the tests to fail.

Separate functions timer_msleep(), timer_usleep(), and timer_nsleep() do exist for sleeping a specific number of milliseconds, microseconds, or nanoseconds, respectively, but these will call timer_sleep() automatically when necessary. You do not need to modify them.
If your delays seem too short or too long, reread the explanation of the -r option to pintos (see section 1.1.4 Debugging versus Testing).
The alarm clock implementation is not needed for later projects, although it could be useful for project 4.

[kswgit]

ALARM CLOCK

DATA STRUCTURES

A1: Copy here the declaration of each new or changed struct' or struct' member, global or static variable, `typedef', or enumeration. Identify the purpose of each in 25 words or less.

Sleeping thread go block until current tick is greater then wakeup_tick.

// src/threads/thread.h   
struct thread
  {
    ...   
    int64_t wakeup_tick;
  }

Tick interrupt handler will check sleeping threads that supposed to
be woken up.
That handler compare the next tick to awake before accessing the
list for performance issue.

// src/threads/thread.c  
static struct list sleep_list;
static int64_t next_tick_to_awake;

ALGORITHMS

A2: Briefly describe what happens in a call to timer_sleep(), including the effects of the timer interrupt handler.

Update static global variable next_tick_to_awake and Push back current
thread into sleep_list and it is watched by interrupt function.
Handler call the timer_interrupt function when raised the timer interrupt.

A3: What steps are taken to minimize the amount of time spent in the timer interrupt handler?

Access to the sleeping thread list has higher time cost then accessing only
one global variable. Handler check the new global static variable that stores
next tick to awake before access to thread list.

SYNCHRONIZATION

A4: How are race conditions avoided when multiple threads call timer_sleep() simultaneously?

Interrupt is disabled when update global static variable for atomic
running

enum intr_level old_level;
old_level = intr_disable();
/* critical section */
intr_set_level(old_level);

A5: How are race conditions avoided when a timer interrupt occurs during a call to timer_sleep()?

Same with A4.

RATIONALE

A6: Why did you choose this design? In what ways is it superior to another design you considered?