Run queues and Wait queues

Spin Locks

• Recall bank example where we protected a critical section with a lock:

  pthread_mutex_lock(&lock);
  balance++;
  pthread_mutex_unlock(&lock);
  

• Two types of locks:

  1. Sleeping locks
  2. Spin locks

• Implementing spin locks

  1. Wrong implementation:

     int flag = 0;
     
     lock() {
         while (flag == 1)
             ;
     
         // This gap between testing and setting the variable
         // creates a race condition!
     
         flag = 1;
     }
     
     unlock() {
         flag = 0;
     }
     

  2. Correct implementation using atomic test_and_set hardware instruction:

     int flag = 0;
     
     lock() {
         while(test_and_set(&flag))
             ;
     }
     
     unlock() {
         flag = 0;
     }
     

     The atomic test_and_set hardware instruction essentially does the following:

     int test_and_set(int *lock) {
         int old = *lock;
         *lock = 1;
         return old;
     }
     

Process Memory Layout

Kernel data include things like:

• One kernel stack for each process (8k for 32-bit and 16k for 64-bit)
• Linked list of task_struct (tasks)

Run Queues

Process State Transitions

When a user process makes read() system call, for example:

1. Trap into kernel

   • save registers into per-proc kernel stack

2. Device driver issues an I/O request to the device

3. Put the calling process to sleep

   • wait_event() -> schedule() -> pick_next_task() -> context_switch()

4. Another process starts running

5. The device completes the I/O request and raises a hardware interrupt

6. Trap into kernel and jump to the interrupt handler

   • wake_up() -> schedule() -> pick_next_task() -> context_switch()

7. Another process starts running

   • this process may or may not be the one that called read()

Wait Queues

• Wait queue structures (pseudo-code):

  struct waitqueue_head {
          spin_lock_t lock;
          list_head task_list;
  }
  
  struct waitqueue {
          task_struct *task;
          wq_func func; // callback function
          list_head task_list;
  }
  

• Wait queue and task_struct:

  

• wait_event_interruptible() macro, defined in wait.h (kernel 3.12.74):

  #define __wait_event_interruptible(wq, condition, ret)			\
  do {									\
          DEFINE_WAIT(__wait);						\
                                                                          \
          for (;;) {							\
                  prepare_to_wait(&wq, &__wait, TASK_INTERRUPTIBLE);	\
                  if (condition)						\
                          break;						\
                  if (!signal_pending(current)) {				\
                          schedule();					\
                          continue;					\
                  }							\
                  ret = -ERESTARTSYS;					\
                  break;							\
          }								\
          finish_wait(&wq, &__wait);					\
  } while (0)
  
  /**
   * wait_event_interruptible - sleep until a condition gets true
   * @wq: the waitqueue to wait on
   * @condition: a C expression for the event to wait for
   *
   * The process is put to sleep (TASK_INTERRUPTIBLE) until the
   * @condition evaluates to true or a signal is received.
   * The @condition is checked each time the waitqueue @wq is woken up.
   *
   * wake_up() has to be called after changing any variable that could
   * change the result of the wait condition.
   *
   * The function will return -ERESTARTSYS if it was interrupted by a
   * signal and 0 if @condition evaluated to true.
   */
  #define wait_event_interruptible(wq, condition)				\
  ({									\
          int __ret = 0;							\
          if (!(condition))						\
                  __wait_event_interruptible(wq, condition, __ret);	\
          __ret;								\
  })
  

Last updated: 2019–03–07