レガシーガジェット研究所

気になったことのあれこれ。

Linux Kernel ~ プロセス x86編 ~

概要

「詳解Linux Kernel」を参考にVersion 2.6.11のソースコードリーディングをしていく。CPUのアーキテクチャは書籍に沿ってIntelx86とする。

今回はプロセスディスクリプタやカレントプロセスの取得方法、プロセスの実行及びスリープなどを見ていく。

プロセスとは

プロセスはLinuxソースコード上ではタスクやスレッドと呼ばれることもある。「プロセス」とは一般的にプログラムの実行状態のことを指し、これをコンテキストと呼んだりもする。カーネルから見るとプロセスの目的はシステム資源(CPUやメモリ)を割り当て実態として動かすことにある。

プロセスは生成時、親プロセスとほとんど同じで、プロセスを生成した命令の次の行から処理が始まり。プロセスのデータ領域(スタック及びヒープ)は別のものだがプログラムのコード(テキスト)は共有する。Unixではこの古い仕組みを採用していたが最近のUnixでは「マルチスレッドアプリケーションプログラム」はデータ構造を共有した状態で互いに独立した多くの処理の流れを持つことができる。今日ではほとんどのマルチスレッドアプリケーションはpthread(POSIXスレッド)ライブラリの標準機能を利用して書かれている。

Linuxは前述の通り「マルチスレッドアプリケーションプログラム」のための機能として「軽量プロセス」を提供する。軽量プロセスは複数の資源を共有する、アドレス空間やオープンしているファイルなどである。軽量プロセスが共有資源に変更をかけると、他方の軽量プロセスからもその変更に気づくことができるようになっている。

プロセスディスクリプタ

プロセスの属性、CPU上で実行されているか、何かの事象で実行が停止しているか、どのアドレス空間に割り当てられているのか、どのファイルへのアクセスが許可されているかなどを保持する。そのような情報はtask_struct型のプロセスディスクリプタに保存されており、この構造体がプロセスに関係する全ての情報を保持している。

実際のソースコード上では以下のように定義されている。構造体の定義だけで600行を超える非常に大きいものなので下記では一部省略している。

// include/linux/sched.h

struct task_struct {
    volatile long state;  /* -1 unrunnable, 0 runnable, >0 stopped */
    struct thread_info *thread_info;
    atomic_t usage;
    unsigned long flags;  /* per process flags, defined below */
    
    int prio, static_prio;
    struct list_head run_list;
    prio_array_t *array;

    struct list_head tasks;
    struct mm_struct *mm, *active_mm;

    /* 
    * pointers to (original) parent process, youngest child, younger sibling,
    * older sibling, respectively.  (p->father can be replaced with 
    * p->parent->pid)
    */
    struct task_struct *real_parent; /* real parent process (when being debugged) */
    struct task_struct *parent;    /* parent process */
    /* ipc stuff */
    struct thread_struct thread;
    /* filesystem information */
    struct fs_struct *fs;
    /* open file information */
    struct files_struct *files;
    /* namespace */
    struct signal_struct *signal;

    struct sigpending pending;
};

プロセスの状態

task_structstateメンバにはプロセスの状態を保持し、フラグの集まりとして定義されている。

// include/linux/sched.h

#define TASK_RUNNING       0
#define TASK_INTERRUPTIBLE 1
#define TASK_UNINTERRUPTIBLE   2
#define TASK_STOPPED       4
#define TASK_TRACED        8
#define EXIT_ZOMBIE        16
#define EXIT_DEAD      32

TASK_の接頭語から始める定数はタスクの状態(state)を表し、EXIT_から始まる定数はプロセス終了時の状態(exit_state)が記録される。

定数 説明
TASK_RUNNING プロセスがCPU上で実行されている、もしくは実行待ちの状態。
TASK_INTERRUPTIBLE ある条件が成り立つのを休止して待っている状態。ハードウェア割り込み、資源の解放、シグナルによりプロセスは起こされる。
TASK_UNINTERRUPTIBLE TASK_INTERRUPTIBLEだがシグナルの受診などによりプロセスが起こされることはない。デバイスドライバなどの動作を安定させる必要があるソフトウェアで用いられる。
TASK_STOPPED 停止状態
TASK_TRACED デバッガによる停止状態
EXIT_ZOMBIE プロセスは終了しているが親プロセスがwait系システムコールを発行していないために終了プロセスの状態を取得できていない状態。wait系システムコールが発行されないとカーネルはデータを解放できない。
EXIT_DEAD 親プロセスがwait系システムコールを発行したためプロセスが削除されている最終的な状態。

ステータスを更新する際は単にstateに上記の定数を代入するだけだが、指定したプロセスや現在実行しているプロセスのステータスを更新する関数として以下のようなものが用意されていたりもする。

// include/linux/sched.h

#define __set_task_state(tsk, state_value)     \
   do { (tsk)->state = (state_value); } while (0)

#define __set_current_state(state_value)           \
   do { current->state = (state_value); } while (0)

プロセスの識別

各実行コンテキストにはプロセスディスクリプタ(task_struct)を割り当てる。プロセスとプロセスディスクリプタは必ず1対1で対応しており、カーネルは32bitアドレスを使用してプロセスを識別する。当該アドレスはプロセスディスクリプタと呼ばれる。

Unix系のOSではユーザはプロセスID(PID)でプロセスを識別する。PIDはプロセスディスクリプタのpidメンバに格納されおり、最大値は以下のように定義されている。

// include/linux/threads.h

/*
 * This controls the default maximum pid allocated to a process
 */
#define PID_MAX_DEFAULT 0x8000

システム管理者は以下のファイルに任意の値を書き込むことで最大値を変更することができる。

$ sudo cat /proc/sys/kernel/pid_max
32768

PIDはインクリメントされながらプロセスに順次割り当てられていくが、最大値まで行った後は使用されていないPIDを再利用する形をとる。PIDの使用状況はpidmapというビットマップで管理されており、32bitアーキテクチャの場合、1ページが4096バイト(32768bit)のため当該ビットマップは単一のページフレームに収まる。

PIDを取得する関数は以下のように定義されている。

// include/linux/pid.h

struct pid *alloc_pid(struct pid_namespace *ns)

Linuxでは各プロセスが固有のPIDを保持しているので全ての実行コンテキストを一意に認識できる。一方でPOSIXではマルチスレッドアプリケーションの全てのスレッドが同じPIDを保持している必要がある。この規格に準拠するためLinuxではスレッドグループを使用している。最初のスレッドがスレッドグループリーダとなり、当該スレッドのPIDがTGID(スレッドグループID)として、その後当該スレッドから生成されるスレッドで共有される。よってgetpid()はは通常TGIDを返すような仕様となっている。

スレッド情報とカーネルスタック

プロセスは動的な存在であるがために当該プロセスに対するメモリも動的に確保される。カーネルはプロセスに対して、2ページ分(8KB)のデータ領域にthread_infoカーネルスタックを配置する。当該ページの配置位置は213の倍数アドレス(8KB)位置となる。thread_infoは当該領域の先頭に配置され、カーネルスタックは当該領域の末尾から先頭に向かって伸びる。

ソースコード上では以下のように共用体として定義されている。

// include/linux/sched.h

union thread_union {
    struct thread_info thread_info;
    unsigned long stack[THREAD_SIZE/sizeof(long)];
};

thread_infoからはプロセスディスクリプタであるtask_structを指すためのメンバが存在し、双方向で参照している。

thread_info構造体は以下のように定義されている。taskメンバがtask_structのポインタ変数になっているのがわかると思う。

// arch/x86/include/asm/thread_info.h

struct thread_info {
    struct task_struct *task;      /* main task structure */
    struct exec_domain *exec_domain;   /* execution domain */
    unsigned long     flags;      /* low level flags */
    unsigned long     status;     /* thread-synchronous flags */
    __u32           cpu;        /* current CPU */
    __s32           preempt_count; /* 0 => preemptable, <0 => BUG */


    mm_segment_t        addr_limit; /* thread address space:
                          0-0xBFFFFFFF for user-thead
                          0-0xFFFFFFFF for kernel-thread
                       */
    struct restart_block    restart_block;

    unsigned long           previous_esp;   /* ESP of the previous stack in case
                          of nested (IRQ) stacks
                       */
    __u8            supervisor_stack[0];
};

カーネルalloc_thread_info()を用いてthread_info及びカーネルスタック用の領域を確保する。当該関数は以下のように定義されている。

// include/asm-i386/thread_info.h

#define alloc_thread_info(tsk) kmalloc(THREAD_SIZE, GFP_KERNEL)

カレントプロセスの識別

thread_infoとカーネルスタックを対にして管理することは効率の面で恩恵がある。espレジスタから現在CPU上で動作しているプロセスを簡単に取得することができる。先ほどコードを示したthread_unionが8KBの場合、espレジスタの下位13bitを0でマスクすることでthread_info構造体のベースアドレスが取得できる。current_thread_info関数が当該処理を担っている。

// include/asm-i386/thread_info.h

/* how to get the thread information struct from C */
static inline struct thread_info *current_thread_info(void)
{
    struct thread_info *ti;
    __asm__("andl %%esp,%0; ":"=r" (ti) : "0" (~(THREAD_SIZE - 1)));
    return ti;
}

/* how to get the current stack pointer from C */
register unsigned long current_stack_pointer asm("esp") __attribute_used__;

// arch/x86/include/asm/page_32_types.h
#define THREAD_SIZE        (8192)

THREAD_SIZEは8KBであることがわかる。これを反転してespレジスタの値と論理積を行うため、下位13bitを削ぐような処理となる。

現在実行しているプロセスのプロセスディスクリプタを取得する際に用いられるcurrentマクロも基本的には以下のような定義になっている。

// include/asm-i386/current.h

static inline struct task_struct * get_current(void)
{
    return current_thread_info()->task;
}
 
#define current get_current()

双方向リスト

プロセスの仕組み及び構造を追跡する前に双方向リストを見ておく必要がある。双方向リストの構造体は以下のように定義されている。

// include/linux/list.h
struct list_head {
    struct list_head *next, *prev;
};

リストの初期化は以下のようなマクロで行われ、指定した変数をリスト型で初期化しているのがわかる。

// include/linux/list.h
#define LIST_HEAD_INIT(name) { &(name), &(name) }
#define LIST_HEAD(name) \
   struct list_head name = LIST_HEAD_INIT(name)

list_head構造体には以下のような関数が用意されている。

  • list_add
  • list_add_tail
  • list_del
  • list_empty

プロセスリスト

プロセスディスクリプタであるtask_structlist_head型のtasksメンバを保持しており、各プロセスのtasksメンバで双方向リストを為している。当該プロセスリストの先頭はプロセスIDが0番のinit_taskである。

TASK_RUNNIG状態のプロセスリスト

カーネルがあるCPU上で実行する新しいプロセスを探す時は、実行可能プロセスのみを調べる。初期のLinuxでは実行キューと呼ばれるリストに実行可能プロセスを保持していた。しかしプロセスの優先度にしたがってリストに順序付けするのは非常にコストがかかるため、次に実行すべきであるプロセスを探すのにリストを走査していた。

Linux 2.6では一定時間で次に実行すべきプロセスを選択できるようになっている。スケジューラの高速化は実行キュー内の実行可能プロセスを優先度毎のリストに分割したことにある。各プロセスディスクリプタlist_head型のrun_listメンバを保持しており、プロセスの実行優先度がk(0 ~ 139)なら、優先度kの実行可能プロセスのリスト内のディスクリプタにリンクしている。加えて実行キューは物理CPU毎に保持しており、実行キューは0 ~ 139までの140種類の異なるリストに分割される。

実行キューのデータは実行キューに属するプロセスディスクリプタのリストであり、当該リストはprio_array_tデータ構造によって管理されている。

// include/linux/sched.h
typedef struct prio_array prio_array_t;

// kernel/sched.c
struct prio_array {
    unsigned int nr_active;
    unsigned long bitmap[BITMAP_SIZE];
    struct list_head queue[MAX_PRIO];
};
#define BITMAP_SIZE ((((MAX_PRIO+1+7)/8)+sizeof(long)-1)/sizeof(long))

// include/linux/sched.h
#define MAX_USER_RT_PRIO   100
#define MAX_RT_PRIO        MAX_USER_RT_PRIO
#define MAX_PRIO       (MAX_RT_PRIO + 40)

各優先度のリストはbitmapメンバで管理しておりlong型の配列をビットマップとして実現している。queuelist_head型で各優先度毎に用意されており、nr_activeはリストにリンクされたディスクリプタの個数を保持している。

上記はリストにプロセスディスクリプタを追加するenqueue_task関数の実装を見ることでわかる。

// kernel/sched.c
static void enqueue_task(struct task_struct *p, prio_array_t *array)
{
    sched_info_queued(p);
    list_add_tail(&p->run_list, array->queue + p->prio);
    __set_bit(p->prio, array->bitmap);
    array->nr_active++;
    p->array = array;
}

プロセスの親子関係

プリグラムから生成されたプロセスには親子関係があり、プロセスが複数の子プロセスを生成した生成した場合はプロセス間に兄弟関係がある。プロセスディスクリプタにはそのような関係を表すためのメンバが存在する。

メンバ名 説明
real_parent プロセスを生成した親プロセスのディスクリプタをさす。親が存在しない若しくは存在しなくなった場合にはプロセス1(init)のプロセスディスクリプタをさす。シェルからプロセスをバックグラウンドで実行しシェルを終了するとバックグランドプロセスはinitの子プロセスとなる。
parent real_parentと同じだがptrace()などシステムコールなどを使用してプロセスを監視する際などに監視プロセスがparentを用いて指す。
children プロセスが生成した子プロセスのリストの先頭
sibling プロセスと同じ親を持つ兄弟プロセスのリストの次の要素と前の要素に対するポインタ

pidhashテーブルとリスト

カーネルはkill()システムコールなどを処理する際に、PIDから対応するプロセスディスクリプタを必要とする時がある。プロセスリストをトラバースしてPIDを確認していくことは容易だが効率的ではない。この検索の速度を向上させるためにハッシュテーブルが導入された。

// include/linux/pid.h
enum pid_type
{
    PIDTYPE_PID,
    PIDTYPE_TGID,
    PIDTYPE_PGID,
    PIDTYPE_SID,
    PIDTYPE_MAX
};
ハッシュテーブルの種類 メンバ名 説明
PIDTYPE_PID pid プロセスのPID
PIDTYPE_TGID tgid スレッドグループのリーダプロセスのPID
PIDTYPE_PID pgrp プロセスグループのリーダプロセスのPID
PIDTYPE_PID session セッショングループのリーダプロセスのPID

PIDはpid_hashfnマクロにより、テーブルのインデックス(ハッシュ)に変換される。

// kernel/pid.c
#define pid_hashfn(nr) hash_long((unsigned long)nr, pidhash_shift)
static int pidhash_shift;

// include/linux/hash.h
static inline unsigned long hash_long(unsigned long val, unsigned int bits)
{
    unsigned long hash = val;
    hash *= GOLDEN_RATIO_PRIME;
    /* High bits are more random, so use them. */
    return hash >> (BITS_PER_LONG - bits);
}
/*  2^63 + 2^61 - 2^57 + 2^54 - 2^51 - 2^18 + 1 */
#define GOLDEN_RATIO_PRIME 0x9e37fffffffc0001UL

// include/asm-i386/types.h
#define BITS_PER_LONG 32

ハッシュ関数は常にPIDTOテーブルインデックスを1対1で対応させるものではない。別々のPIDが同一のテーブルインデックスにハッシュされることもある。このことを衝突(コリジョン)と言う。 Linuxは衝突したPIDを扱うためにチェイン法(オープンハッシュ法)を使用する。テーブルの各エントリは衝突したプロセスディスクリプタで構成される双方向リストの先頭である。

次にカーネルがあるスレッドグループに属する全てのプロセス、つまりtgidが同じプロセスを全て検索しなければならない場合を考える。スレッドグループ番号で検索した場合、スレッドグループのリーダプロセスが見つかる。そして当該スレッドグループに属するプロセスを高速検索するためにカーネルはスレッドグループ毎のプロセスリストも保持している。ログインセッションやプロセスグループに対しても同様のことが言える。

pid構造体は前述の全ての要求を満たせるように設計されている。ハッシュテーブル内のPID番号に対してプロセスリストを定義することができるためである。pid構造体は以下のように定義されている。

// include/linux/pid.h
struct pid
{
    /* Try to keep pid_chain in the same cacheline as nr for find_pid */
    int nr;
    struct hlist_node pid_chain;
    /* list of pids with the same nr, only one of them is in the hash */
    struct list_head pid_list;
};

各メンバの説明を以下に示す。

名前 説明
int nr PID番号
struct hlist_node pid_chain ハッシュチェインリストの前後要素へのリンク
struct list_head pid_list 各PIDリストの先頭

以下の図はPIDTYPE_TGIDのハッシュテーブルを表す。

pid_hashの2番目のエントリがTGIDのハッシュテーブルを指す、つまりチェインリストの先頭となるhlist_head構造体の配列を指す。ハッシュテーブルの71番目のエントリを先頭とするチェインリストにはPID番号246と4351に対応する2つのディスクリプタが存在することがわかる。pid_listで繋がれているのはそのTGIDに属するプロセスである。

PIDからプロセスディスクリプタを求める関数であるfind_task_by_pid()の定義を示す。

// include/linux/sched.h
#define find_task_by_pid(nr)   find_task_by_pid_type(PIDTYPE_PID, nr)

// kernel/pid.c
task_t *find_task_by_pid_type(int type, int nr)
{
    struct pid *pid;

    pid = find_pid(type, nr);
    if (!pid)
        return NULL;

    return pid_task(&pid->pid_list, type);
}

// kernel/pid.c
struct pid * fastcall find_pid(enum pid_type type, int nr)
{
    struct hlist_node *elem;
    struct pid *pid;

    hlist_for_each_entry(pid, elem,
            &pid_hash[type][pid_hashfn(nr)], pid_chain) {
        if (pid->nr == nr)
            return pid;
    }
    return NULL;
}

// kernel/pid.c
static struct hlist_head *pid_hash[PIDTYPE_MAX];

上記では先ほど言及したpid_hashからハッシュ関数を使ってpid_chainの中からpid構造体のnrを参照し、PIDが同一のものであれば取得するという処理になっている。

プロセスの管理方法

TASK_RUNNIG状態のプロセスは先ほど述べた通り実行キューリストを利用してグループ化しているが、他の状態のプロセスはまた異なる方法でグループ化する。

  • TASK_STOPPEDTASK_ZOMBIEEXIT_DEAD状態のプロセスは専用のリストは作成せず、PIDまたは親プロセス及び子プロセスのリストを通して操作するだけなので、グループ化は行わない。
  • TASK_INTERRUPTIBLETASK_UNINTERRUPTIBLE状態のプロセスはそれぞれの事象毎にさらに詳細に分類される。プロセス状態だけではプロセスを簡単に取得することは困難なので待ちキューというプロセスリストを用いて管理する。

待ちキュー(待ち行列

待ちキューは割り込み処理、プロセスの同期、タイミングを取るときに使用され、ディスクの入出力やシステム資源の解放、一定時間の経過など、待つ処理を実装している。特定の事象の発生を待つプロセスは自身を適切な待ちキューに入れて処理を任せる。つまり待ちキューはある条件が真になった際に起床される休止中のプロセスグループを表している。

待ちキューは双方向リストとして実装されている。各要素はプロセスディスクリプタへのポインタを持つ。各待ちキューは待ちキューの先頭で識別し、実際には以下のように定義されている。

// include/linux/wait.h
struct __wait_queue_head {
    spinlock_t lock;
    struct list_head task_list;
};
typedef struct __wait_queue_head wait_queue_head_t;

待ちキューはカーネル関数だけでなく、割り込みハンドラからも更新されるため、双方向リストを同時アクセスから保護する必要がある。同期は上記のlockメンバを用いて待ちキュー内のスピンロックによって行う。task_listは待ち状態プロセスリストの先頭となる。

待ちキューの要素はwait_queue_tとなる。定義は以下。

typedef struct __wait_queue wait_queue_t;
struct __wait_queue {
    unsigned int flags;
#define WQ_FLAG_EXCLUSIVE  0x01
    struct task_struct * task;
    wait_queue_func_t func;
    struct list_head task_list;
};

待ちキュー内の各要素は待ち状態のプロセスであり、特定の事象の発生を待ち合わせている、そしてtaskメンバがそのプロセスディスクリプタを指している。task_listメンバは同じ事象を待ち合わせているプロセスリストの要素を指している。

待ち状態には2種類存在する。

  • 排他的待ちプロセス(flagsメンバが1)
  • 排他的待ちでないプロセス(flagsメンバが0)

一度に1つのプロセスしか利用できない資源を待ち合わせているプロセスは典型的な「排他的待ちプロセス」となる。逆にある1つ事象を待っているのであれば、それは排他的でない待ちの状態となる。例えばディスクブロック転送終了を待ち合わせている場合などが考えられる。待ちキュー要素のfuncメンバを用いて待ちキューで待ち状態のプロセスの起床方法を指定する。

待ちキューの操作

待ちキューはDECLARE_WAIT_QUEUE_HEADで先頭の要素を定義し、init_waitqueue_head()で初期化する。

// include/linux/wait.h
#define DECLARE_WAIT_QUEUE_HEAD(name) \
   wait_queue_head_t name = __WAIT_QUEUE_HEAD_INITIALIZER(name)
    
static inline void init_waitqueue_head(wait_queue_head_t *q)
{
    q->lock = SPIN_LOCK_UNLOCKED;
    INIT_LIST_HEAD(&q->task_list);
}

待ちキューの要素であるwait_queue_tinit_waitqueue_entry()によって初期化される。

// include/linux/wait.h
static inline void init_waitqueue_entry(wait_queue_t *q, struct task_struct *p)
{
    q->flags = 0;
    q->task = p;
    q->func = default_wake_function;
}

上記のように排他的でない待ち合わせ状態のプロセスはdefault_wake_functionによって起こすことができる。

その他にもautoremove_wake_functionという関数ではdefault_wake_functionをコールした後に対象プロセスを持つ要素を待ちキューから外す処理まで行ってくれるものもある。

// kernel/wait.c
int autoremove_wake_function(wait_queue_t *wait, unsigned mode, int sync, void *key)
{
    int ret = default_wake_function(wait, mode, sync, key);

    if (ret)
        list_del_init(&wait->task_list);
    return ret;
}

またinit_waitqueue_func_entry()で待ちキュー要素を初期化することにより独自の起床関数を定義することもできる。

// include/linux/wait.h
static inline void init_waitqueue_func_entry(wait_queue_t *q,
                    wait_queue_func_t func)
{
    q->flags = 0;
    q->task = NULL;
    q->func = func;
}

待ちキューへの要素の追加は以下のような関数を用いて行う。

関数名 説明
add_wait_queue 排他的でない待ちプロセスをキューの先頭に追加
add_wait_queue_exclusive 排他的待ちプロセスをキューの末尾に追加
// kernel/wait.c
void fastcall add_wait_queue(wait_queue_head_t *q, wait_queue_t *wait)
{
    unsigned long flags;

    wait->flags &= ~WQ_FLAG_EXCLUSIVE;
    spin_lock_irqsave(&q->lock, flags);
    __add_wait_queue(q, wait);
    spin_unlock_irqrestore(&q->lock, flags);
}

void fastcall add_wait_queue_exclusive(wait_queue_head_t *q, wait_queue_t *wait)
{
    unsigned long flags;

    wait->flags |= WQ_FLAG_EXCLUSIVE;
    spin_lock_irqsave(&q->lock, flags);
    __add_wait_queue_tail(q, wait);
    spin_unlock_irqrestore(&q->lock, flags);
}

上記を見るとWQ_FLAG_EXCLUSIVEを使用しており、排他的であるか否かを設定しているのがわかる。

待ちキューから要素を削除するのはremove_wait_queueを使用する。

// kernel/wait.c
void fastcall remove_wait_queue(wait_queue_head_t *q, wait_queue_t *wait)
{
    unsigned long flags;

    spin_lock_irqsave(&q->lock, flags);
    __remove_wait_queue(q, wait);
    spin_unlock_irqrestore(&q->lock, flags);
}

待ちキューにエントリが存在するかは以下の関数を用いて確認する。

// include/linux/wait.h
static inline int waitqueue_active(wait_queue_head_t *q)
{
    return !list_empty(&q->task_list);
}

カレントプロセスを待ちキューに追加する際は``

// kernel/sched.c
void fastcall __sched sleep_on(wait_queue_head_t *q)
{
    SLEEP_ON_VAR

    current->state = TASK_UNINTERRUPTIBLE;

    SLEEP_ON_HEAD
    schedule();
    SLEEP_ON_TAIL
}

#define    SLEEP_ON_VAR                    \
   unsigned long flags;              \
   wait_queue_t wait;              \
   init_waitqueue_entry(&wait, current);

#define SLEEP_ON_HEAD                  \
   spin_lock_irqsave(&q->lock,flags);       \
   __add_wait_queue(q, &wait);         \
   spin_unlock(&q->lock);

#define    SLEEP_ON_TAIL                   \
   spin_lock_irq(&q->lock);         \
   __remove_wait_queue(q, &wait);          \
   spin_unlock_irqrestore(&q->lock, flags);

上記ではカレントプロセスを含んだ待ちキューの要素を初期化し、TASK_UNINTERRUPTIBLEに設定した後、当該要素を待ちキューに実際に登録しschedule()で他のプロセスを起床させるという処理を行う。他にもプロセスを待ちキューに登録する関数として以下のようなものがある。

関数名 説明
interruptible_sleep_on_timeout カレントプロセスの状態にTASK_UNINTERRUPTIBLEではなくTASK_INTERRUPTIBLEを設定する
sleep_on_timeout タイムアウトを設定できる。内部でschedule()ではなくschedule_timeout()を呼んでいる

カレントプロセスを待ちキューに登録する方法としてKernel 2.6からは別の方法も提供されている。

  • prepare_to_wait()
  • prepare_to_wait_exclusive()
  • finish_wait()

上記の関数を用いて以下のように待ちキューにプロセスを登録する方法もある。

static long inet_wait_for_connect(struct sock *sk, long timeo)
{
    DEFINE_WAIT(wait);

    prepare_to_wait(sk->sk_sleep, &wait, TASK_INTERRUPTIBLE);

    while ((1 << sk->sk_state) & (TCPF_SYN_SENT | TCPF_SYN_RECV)) {
        release_sock(sk);
        timeo = schedule_timeout(timeo);
        lock_sock(sk);
        if (signal_pending(current) || !timeo)
            break;
        prepare_to_wait(sk->sk_sleep, &wait, TASK_INTERRUPTIBLE);
    }
    finish_wait(sk->sk_sleep, &wait);
    return timeo;
}

prepare_to_wait*()はプロセスの状態を第3引数に取り、待ちキューの要素であるwaitを登録する。finish_wait()はプロセスの状態を再度TASK_RUNNIGに戻し、待ちキューから当該プロセスが包含された要素を削除する。

待ちキューには何らかの事象を待ち合わせるプロセスも登録されると前述したが、そのようなプロセスはwait_event()で待ちキューに登録される。

// include/linux/wait.h
#define __wait_event(wq, condition)                    \
do {                                 \
   DEFINE_WAIT(__wait);                        \
                                   \
   for (;;) {                            \
       prepare_to_wait(&wq, &__wait, TASK_UNINTERRUPTIBLE);    \
       if (condition)                        \
           break;                        \
       schedule();                     \
   }                               \
   finish_wait(&wq, &__wait);                  \
} while (0)

#define wait_event(wq, condition)                  \
do {                                 \
   if (condition)                            \
       break;                            \
   __wait_event(wq, condition);                    \
} while (0)

上記を見ると、conditionが真を返さないと再度待ちキューに登録されるのがわかる。

他にも以下のようにシグナルを送ることができるものやタイムアウトを設定できる派生関数も用意されている。

// include/linux/wait.h
#define __wait_event_timeout(wq, condition, ret)           \
do {                                 \
   DEFINE_WAIT(__wait);                        \
                                   \
   for (;;) {                            \
       prepare_to_wait(&wq, &__wait, TASK_UNINTERRUPTIBLE);    \
       if (condition)                        \
           break;                        \
       ret = schedule_timeout(ret);                \
       if (!ret)                     \
           break;                        \
   }                               \
   finish_wait(&wq, &__wait);                  \
} while (0)

#define wait_event_timeout(wq, condition, timeout)         \
({                                   \
   long __ret = timeout;                      \
   if (!(condition))                         \
       __wait_event_timeout(wq, condition, __ret);     \
   __ret;                              \
})

#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)

#define wait_event_interruptible(wq, condition)                \
({                                   \
   int __ret = 0;                            \
   if (!(condition))                     \
       __wait_event_interruptible(wq, condition, __ret);   \
   __ret;                              \
})

待ちキューに存在するプロセスを起床させる場合は以下のようなマクロを使用し、 対象のプロセスを TASK_RUNNIGに戻す。

// include/linux/wait.h
#define wake_up(x)         __wake_up(x, TASK_UNINTERRUPTIBLE | TASK_INTERRUPTIBLE, 1, NULL)
#define wake_up_nr(x, nr)      __wake_up(x, TASK_UNINTERRUPTIBLE | TASK_INTERRUPTIBLE, nr, NULL)
#define wake_up_all(x)         __wake_up(x, TASK_UNINTERRUPTIBLE | TASK_INTERRUPTIBLE, 0, NULL)
#define wake_up_interruptible(x)   __wake_up(x, TASK_INTERRUPTIBLE, 1, NULL)
#define wake_up_interruptible_nr(x, nr)    __wake_up(x, TASK_INTERRUPTIBLE, nr, NULL)
#define wake_up_interruptible_all(x)   __wake_up(x, TASK_INTERRUPTIBLE, 0, NULL)
#define    wake_up_locked(x)       __wake_up_locked((x), TASK_UNINTERRUPTIBLE | TASK_INTERRUPTIBLE)
#define wake_up_interruptible_sync(x)   __wake_up_sync((x),TASK_INTERRUPTIBLE, 1)
  • 全てのマクロはTASK_INTERRUPTIBLE状態で待っているプロセスを対象とする。「interruptible」の文字がない場合はTASK_UNINTERRUPTIBLEも含む。
  • 全てのマクロは指定した状態(TASK_INTERRUPTIBLEまたはTASK_UNINTERRUPTIBLE)の排他的でない待ち状態のプロセスを起床する。
  • nr付くものはは指定の数、allが付くものは全ての指定した状態のプロセスを起床させる。
  • syncが付くものは起床したプロセスの優先度をカレントプロセスを比較し、必要であればschedule()を呼び出す。結果として優先度の高いプロセスの実行が遅れることになる。
  • wake_up_lockedは既にスピンロックされている場合に使用する。
// include/linux/wait.h
#define wake_up(x)         __wake_up(x, TASK_UNINTERRUPTIBLE | TASK_INTERRUPTIBLE, 1, NULL)

// kernel/sched.c
void fastcall __wake_up(wait_queue_head_t *q, unsigned int mode,
                int nr_exclusive, void *key)
{
    unsigned long flags;

    spin_lock_irqsave(&q->lock, flags);
    __wake_up_common(q, mode, nr_exclusive, 0, key);
    spin_unlock_irqrestore(&q->lock, flags);
}

static void __wake_up_common(wait_queue_head_t *q, unsigned int mode,
                 int nr_exclusive, int sync, void *key)
{
    struct list_head *tmp, *next;

    list_for_each_safe(tmp, next, &q->task_list) {
        wait_queue_t *curr;
        unsigned flags;
        curr = list_entry(tmp, wait_queue_t, task_list);
        flags = curr->flags;
        if (curr->func(curr, mode, sync, key) &&
            (flags & WQ_FLAG_EXCLUSIVE) &&
            !--nr_exclusive)
            break;
    }
}

// include/linux/list.h
#define list_for_each_safe(pos, n, head) \
   for (pos = (head)->next, n = pos->next; pos != (head); \
       pos = n, n = pos->next)

全体の流れとしてはスピンロック→プロセス起床という流れになっている。上記の場合だとwake_up()に指定した待ちキューの先頭からトラバースしていき順に全てのプロセスを起床させる。

プロセスの資源利用制限

プロセスには使用可能な資源(CPUやディスク)の量に対する利用制限が存在する。

// include/asm-generic/resource.h
#define RLIMIT_CPU     0  /* CPU time in ms */
#define RLIMIT_FSIZE       1  /* Maximum filesize */
#define RLIMIT_DATA        2  /* max data size */
#define RLIMIT_STACK       3  /* max stack size */
#define RLIMIT_CORE        4  /* max core file size */
#define RLIMIT_RSS     5  /* max resident set size */
#define RLIMIT_NPROC       6  /* max number of processes */
#define RLIMIT_NOFILE      7  /* max number of open files */
#define RLIMIT_MEMLOCK     8  /* max locked-in-memory address space */
#define RLIMIT_AS      9  /* address space limit */
#define RLIMIT_LOCKS       10 /* maximum file locks held */
#define RLIMIT_SIGPENDING  11 /* max number of pending signals */
#define RLIMIT_MSGQUEUE        12 /* maximum bytes in POSIX mqueues */

上記をインデックスに以下の構造体配列で各制限を定義する。

// include/linux/resource.h
struct rlimit {
    unsigned long rlim_cur;
    unsigned long rlim_max;
};

例えばCPUであればcurrent->signal->rlim[RLIMIT_CPU].rlim_curが現在の利用制限値となり、rlim_maxは設定可能な最大値となる。ユーザはgetrlimit()setrlimit()システムコールを用いて資源の制限値を変更できるが、CAP_SYS_RESOURCE権限があるユーザであれば(基本的にはスーパユーザ)rlim_currlim_maxより大きな値に設定できる。

通常利用制限値はRLIMIT_INFINITY(0xFFFFFFFF)となっており実質の無制限となっている(CPUやディスクなどにはもちろん存在する)。システム管理者が資源の制限を行うこともある。ユーザがシステムにログインするとカーネルはスーパユーザが所有するプロセス(シェル)を生成し、setrlimit()を発行して資源のrlim_max及びrlim_curを設定した後、所有者を当該ユーザに変更する。当該ユーザから生成されるプロセスはその親プロセスのrlim配列の値を引き継ぐのでユーザは管理者により設定された制限を超過することはない。

参考