1. 仕組み

1-1. GNU/Linux のスケジューラ概要

  システムに存在するプロセスはそれぞれ、実行状態と呼ばれる属性情報を持っており、各プロセスは各実行状態においてそれぞれ別々な形で管理されている。

  特に、システムで現在実行されている実行状態が TASK_RUNNING となっている各プロセスは、実行待ちキューというキューで管理され、スケジューラが呼び出される度に、そのキューの中から最適なプロセスを選定し、cpu を割り当てる。

1-2. プロセスの休眠処理の概要

  実行状態が TASK_RUNNING となっているプロセスを休眠状態にし、特定のイベントが発生するまで実行されないようにする為のプロセス操作が存在する。

  ただし、システムが休眠状態にあるプロセスを一元的に管理するのではなく、各ソフトウェアコンポーネントが休眠プロセスの管理を行う。

　具体的には、ユーザが定義した待ち行列の先頭オブジェクトに、休眠プロセスを待ち行列エントリとして順次挿入していくデータ構造になっており、__wake_up() 関数によって、引数に指定された待ち行列に含まれる各エントリのプロセスの実行状態を TASK_RUNNING に遷移させる。

2. データ構造

2-1. wait_queue_head_t 型構造体

     1  struct __wait_queue_head {
     2    spinlock_t lock;
     3    struct list_head task_list;
     4  };
     5  typedef struct __wait_queue_head wait_queue_head_t;

  待ち行列の先頭リスト構造。このオブジェクトがリストの本体の先頭エントリを参照する list_head オブジェクトを持つ。ユーザが作成。

2-2. wait_queue_t 型構造体

     1  typedef struct __wait_queue wait_queue_t;
     2  
     3  struct __wait_queue {
     4    unsigned int flags;
     5  #define WQ_FLAG_EXCLUSIVE  0x01
     6    void *private;
     7    wait_queue_func_t func;
     8    struct list_head task_list;
     9  };

  待ち行列の本体を構成するオブジェクト。こいつで、どのタスクが休眠状態にあり、どのように起床させるのかという手続きが記録される。GNU/Linux が勝手に作成してくれる。

3. 動作 及び 実装

3-1. プロセスの休眠処理 ( interruptible_sleep_on() [kernel/sched.c] )

  カレントプロセスを、引数で渡した wait_queue_head_t オブジェクトが管理するリストに挿入し、実行状態を休眠状態にする関数。

     1  static long __sched
     2  sleep_on_common(wait_queue_head_t *q, int state, long timeout)
     3  {
     4    unsigned long flags;
     5    wait_queue_t wait;
     6  
     7    init_waitqueue_entry(&wait, current);
     8  
     9    __set_current_state(state);
    10  
    11    spin_lock_irqsave(&q->lock, flags);
    12    __add_wait_queue(q, &wait);
    13    spin_unlock(&q->lock);
    14    timeout = schedule_timeout(timeout);
    15    spin_lock_irq(&q->lock);
    16    __remove_wait_queue(q, &wait);
    17    spin_unlock_irqrestore(&q->lock, flags);
    18  
    19    return timeout;
    20  }
    21  
    22  void __sched interruptible_sleep_on(wait_queue_head_t *q)
    23  {
    24    sleep_on_common(q, TASK_INTERRUPTIBLE, MAX_SCHEDULE_TIMEOUT);
    25  }

  7 行目で実行している init_waitqueue_entry() [include/linux/wait.h] は、引数で渡した wait_queue_t オブジェクトに属性情報を代入するだけのインライン関数。

     1  static inline void init_waitqueue_entry(wait_queue_t *q, struct task_struct *p)
     2  {
     3    q->flags = 0;
     4    q->private = p;
     5    q->func = default_wake_function;
     6  }

  9 行目の __set_current_state() [include/linux/sched.h] で、カレントプロセスの状態を引数で指定した値に変更する。

  そして 12 行目の __add_wait_queue() [include/linux/wait.h] で、wait オブジェクトのリストオブジェクトを wait_queue_head_t オブジェクトのリストに追加し、16 行目の schedule_timeout() を呼び出す。

  schedule_timeout() [kernel/timer.c] では timeout の値に MAX_SCHEDULE_TIMEOUT が指定された場合には、単純にスケジューラを呼び出すだけで処理を終える。

  ただし、この時点でカレントプロセス (厳密には、スケジューラが呼び出された時点でカレントプロセスでは無いが、便宜上カレントプロセスと呼称) の実行状態は TASK_INTERRUPTIBLE に変更されている為、スケジューラが呼び出された時点で、カレントプロセスは休眠状態となり、以降状態変化が起きない限りスケジューラをいくら呼び出しても、当該プロセスが起床することは無い。

  後に示す処理によってプロセスが起床されると、wait_queue_head_t オブジェクトのリストから wait_queue_t オブジェクトが排除され、処理を終了させる。

3-2. プロセスの起床処理 (__wake_up() [kernel/sched.c])

  引数で渡した wait_queue_head_t オブジェクトが管理するリストに含まれる休眠中のプロセスを起床させる関数。

     1  static void __wake_up_common(wait_queue_head_t *q, unsigned int mode,
     2             int nr_exclusive, int sync, void *key)
     3  {
     4    wait_queue_t *curr, *next;
     5  
     6    list_for_each_entry_safe(curr, next, &q->task_list, task_list) {
     7      unsigned flags = curr->flags;
     8  
     9      if (curr->func(curr, mode, sync, key) &&
    10          (flags & WQ_FLAG_EXCLUSIVE) && !--nr_exclusive)
    11        break;
    12    }
    13  }
    14  
    15  void __wake_up(wait_queue_head_t *q, unsigned int mode,
    16        int nr_exclusive, void *key)
    17  {
    18    unsigned long flags;
    19  
    20    spin_lock_irqsave(&q->lock, flags);
    21    __wake_up_common(q, mode, nr_exclusive, 0, key);
    22    spin_unlock_irqrestore(&q->lock, flags);
    23  }

  そして、wait_queue_head_t オブジェクトが管理するリストから wait_queue_t エントリを取得し、wait_queue_t オブジェクトの func メソッドを実行する。

  func メソッドの実体は wait_queue_t オブジェクトを初期化する際に実行される init_waitqueue_entry() によって default_wake_function() に設定されている。

     1  int default_wake_function(wait_queue_t *curr, unsigned mode, int sync,
     2          void *key)
     3  {
     4    return try_to_wake_up(curr->private, mode, sync);
     5  }

  default_wake_function () は try_to_wake_up() 関数のラッパールーチンであり、これを呼び出す事によって、指定した休眠状態のプロセスを起床させる処理を行う。wait_queue_t オブジェクトの private メンバには、休眠状態のプロセスのプロセスディスクリプタが init_waitqueue_entry() で設定されている。