Advertisements
Home > Information Technology, Operating System, programming > Avoiding Busy Wait in timer_sleep() on PintOS

Avoiding Busy Wait in timer_sleep() on PintOS

In device.c:

 /* Sleeps for approximately TICKS timer ticks.  Interrupts must
 be turned on. */
 void
 timer_sleep (int64_t ticks)
 {
  int64_t start = timer_ticks ();
  ASSERT (intr_get_level () == INTR_ON);
  while (timer_elapsed (start) < ticks)
    thread_yield ();
 }

As we can see on the code above, when the timer_sleep() is called,  it goes to a “while” loop until the timer elapsed time is bigger than the ticks. This is a wasted CPU resource as it will remain idle until the timer has expired. To counter this problem, let’s go to thread.h file and introduce a modified thread structure in the file:

thread.h

struct thread
{
 /* Owned by thread.c. */
 tid_t tid;                          /* Thread identifier. */
 enum thread_status status;          /* Thread state. */
 char name[16];                      /* Name (for debugging purposes). */
 uint8_t *stack;                     /* Saved stack pointer. */
 int priority;                       /* Priority. */
 struct list_elem allelem;           /* List element for all threads list. */
 /* Shared between thread.c and synch.c. */
 struct list_elem elem;              /* List element. */
 int64_t sleep_ticks;                /* time to sleep in ticks */
 #ifdef USERPROG
 /* Owned by userprog/process.c. */
 uint32_t *pagedir;                  /* Page directory. */
 #endif
 /* Owned by thread.c. */
 unsigned magic;                     /* Detects stack overflow. */
};

Now if you look closely, we have added sleep_ticks variable in the thread structure to detect how many ticks the thread has to sleep. So, let’s modify the timer_sleep():

timer.c

/* Sleeps for approximately TICKS timer ticks.  Interrupts must
be turned on. */
void
timer_sleep (int64_t ticks)
{
 ASSERT (intr_get_level () == INTR_ON);
 // assign requested sleep time to current thread
 thread_current()->sleep_ticks = ticks;
 // disable interrupts to allow thread blocking
 enum intr_level old_level = intr_disable();
 // block current thread
 thread_block();
 /* set old interrupt level which was used before the current thread was blocked
 to ensure that no other logic crashes */
 intr_set_level(old_level);
}

What the code does is that we assign the sleep_ticks variable of the thread with the defined ticks. We disable our interrupt handle to ensure serialization and block the thread in the thread_block(). Now, the timer_interrupt() will always be called for each elapsed tick:

timer.c

/* Timer interrupt handler. */
static void
timer_interrupt (struct intr_frame *args UNUSED)
{
 ticks++;
 thread_tick ();
 // Check each thread with wake_threads() after each tick. It is assumed that
 // interrupts are disabled  because timer_interrupt() is an interrupt handler.
 thread_foreach(wake_threads, 0);
}

The thread_foreach() will check every thread and execute wake_threads(). And for your information, we have to define that wake_threads() in our timer.c. It basically a function to check whether a thread has to wake up or not.

timer.c

/**
* Function for waking up a sleeping thread. It checks
* whether a thread is being blocked. If TRUE, then
* check whether the thread's sleep_ticks has reached 0 or not
* by decrementing it on each conditional statement.
* If the thread's sleep_ticks has reached 0, then unblock the
* sleeping thread.
*/
static void
wake_threads(struct thread *t, void *aux)
{
 if(t->status == THREAD_BLOCKED)
 {
  if(t->sleep_ticks > 0)
  {
   t->sleep_ticks--;
   if(t->sleep_ticks == 0)
   {
    thread_unblock(t);
   }
  }
 }
}

Essentially, when the wake_threads() is called, it checks if the current thread is being blocked. If it is blocked, then we know that the thread is currently asleep. If the ticks of that thread has not expired (not equal to 0), then we need to decrement the ticks of that thread to indicate that one tick has passed. If the ticks of that thread has expired (equal to 0), now we know that it is okay for the thread to wake up (We perform an unblock() operation to that particular thread).

Advertisements
  1. decars@usi.ch
    April 6, 2016 at 6:15 pm

    I know I’m 5 years late, but this is one of the first hits one google for “pintos avoid busy waiting”, so I’ll do this anyways.

    This solution is wrong, there are many things wrong with it.
    1) It is inefficient, since it iterates over all threads, not only the sleeping ones.
    2) wake_threads will unblock any blocked threads whose sleep_ticks has just decreased to 0, regardless of the reason why they were blocked. They could be blocked because of a different reason than timer_sleep, ie. I/O operations, synchronization, etc.
    3) sleep_ticks is not initialized if a thread has not been put to sleep, therefore accessing it from wake_threads could lead to undefined behavior. For example: accessing it in a thread that is blocked for a different reason, in which case the value of slee_ticks is garbage.
    4) It does not work when the argument of timer_sleep is <= 0.

    • decars@usi.ch
      April 6, 2016 at 7:02 pm

      Scratch points 2) and 3), since threads in pintos get memory that was already initialised in 0. Clever.
      4) is still a problem, I think, though easy to fix.

    • Yellow Flash
      September 8, 2017 at 4:51 am

      can you tell what would be an appropriate solution please , decars@usi

  2. October 22, 2016 at 6:25 pm

    Hey i followed that tutorial. But still i am getting fail for alarm-priority. What’s reason for that?

  3. vijay
    February 22, 2017 at 7:26 pm

    how to reduce stravation in priority scheduling

  4. February 22, 2017 at 7:28 pm

    how to reduce starvation in priority scheduling

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s

%d bloggers like this: