スケジューラの読解について

スケジューラを読解する為に以下の流れで進めていきたいと思います。
・プロセスとスレッド
・スケジューリングポリシー
・スケジューラの構成
・スケジューリングアルゴリズム

プロセスとスレッド

スケジューラ編ですが、実際のスケジューラを読む前に、まずはスケジューラの対象となるプロセスとスレッドについて述べたいと思います。※従って、本編ではまだスケジューラ自体の話はでてきません。

一般的にはスレッドは、プロセスと比較して、軽量でコンテキストスイッチも高速と言われていますが、本当にそうでしょうか。本記事は【読解】を謳っていますので実際のコードを見て理解を深めましょう。それぞれcloneシステムコールを使用しますが、本システムコールに設定するフラグが異なりますので、呼び出し側（設定している箇所）から見ていきましょう。呼び出し側はglibcになります。
※個人的にはglibcのコードはマクロだらけで読み辛いなので嫌いです（笑）。

ユーザー空間側の処理

前回紹介した通り、各システムコールはソフトウェア例外を発生させますが、各アーキテクチャが発行する命令は異なります。下記にそれぞれのアーキテクチャのソフトウェア例外発生命令を示します。

アーキテクチャ	命令
x86	int 0x80 or sysenter
Power	sc
Arm	svc
MIPS	syscall

子プロセスの呼び出し箇所

cloneシステムコール実行部はアーキテクチャ依存なので、下記関数で見ることにします。flagは以下の通りです。
・CLONE_CHILD_SETTID
・CLONE_CHILD_CLEARTID
・SIGCHLD
上記を設定してcloneシステムコールを発行しています。これを覚えておきましょう。

glibc/sysdeps/unix/sysv/linux/arch-fork.h

static inline pid_t
arch_fork (void *ctid)
{
  const int flags = CLONE_CHILD_SETTID | CLONE_CHILD_CLEARTID | SIGCHLD;
  long int ret;
#ifdef __ASSUME_CLONE_BACKWARDS
# ifdef INLINE_CLONE_SYSCALL
  ret = INLINE_CLONE_SYSCALL (flags, 0, NULL, 0, ctid);
# else
  ret = INLINE_SYSCALL_CALL (clone, flags, 0, NULL, 0, ctid);
# endif
#elif defined(__ASSUME_CLONE_BACKWARDS2)
  ret = INLINE_SYSCALL_CALL (clone, 0, flags, NULL, ctid, 0);
#elif defined(__ASSUME_CLONE_BACKWARDS3)
  ret = INLINE_SYSCALL_CALL (clone, flags, 0, 0, NULL, ctid, 0);
#elif defined(__ASSUME_CLONE2)
  ret = INLINE_SYSCALL_CALL (clone2, flags, 0, 0, NULL, ctid, 0);
#elif defined(__ASSUME_CLONE_DEFAULT)
  ret = INLINE_SYSCALL_CALL (clone, flags, 0, NULL, ctid, 0);
#else
# error "Undefined clone variant"
#endif
  return ret;
}

子スレッドの呼び出し箇所

スレッドの場合は、★でflagsを設定し、☆でcloneシステムコールを発行します。
従ってflagsは以下の通りです。
・CLONE_VM
・CLONE_FS
・CLONE_FILES
・CLONE_SYSVSEM
・CLONE_SIGHAND
・CLONE_THREAD
・CLONE_SETTLS
・CLONE_PARENT_SETTID
・CLONE_CHILD_CLEARTID
こちらも覚えておきましょう。

glibc/sysdeps/unix/sysv/linux/createthread.c

static int
create_thread (struct pthread *pd, const struct pthread_attr *attr,
               bool *stopped_start, STACK_VARIABLES_PARMS, bool *thread_ran)
{
：
  /* We rely heavily on various flags the CLONE function understands:
     CLONE_VM, CLONE_FS, CLONE_FILES
        These flags select semantics with shared address space and
        file descriptors according to what POSIX requires.
     CLONE_SIGHAND, CLONE_THREAD
        This flag selects the POSIX signal semantics and various
        other kinds of sharing (itimers, POSIX timers, etc.).
     CLONE_SETTLS
        The sixth parameter to CLONE determines the TLS area for the
        new thread.
     CLONE_PARENT_SETTID
        The kernels writes the thread ID of the newly created thread
        into the location pointed to by the fifth parameters to CLONE.
        Note that it would be semantically equivalent to use
        CLONE_CHILD_SETTID but it is be more expensive in the kernel.
     CLONE_CHILD_CLEARTID
        The kernels clears the thread ID of a thread that has called
        sys_exit() in the location pointed to by the seventh parameter
        to CLONE.
     The termination signal is chosen to be zero which means no signal
     is sent.  */
★  const int clone_flags = (CLONE_VM | CLONE_FS | CLONE_FILES | CLONE_SYSVSEM
                           | CLONE_SIGHAND | CLONE_THREAD
                           | CLONE_SETTLS | CLONE_PARENT_SETTID
                           | CLONE_CHILD_CLEARTID
                           | 0);
  TLS_DEFINE_INIT_TP (tp, pd);
☆ if (__glibc_unlikely (ARCH_CLONE (&start_thread, STACK_VARIABLES_ARGS,
                                    clone_flags, pd, &pd->tid, tp, &pd->tid)
                        == -1))
    return errno;
：
}

カーネル側の処理

次にいよいよカーネル側の処理になります。
今回はプロセス生成時に指定したフラグとスレッド生成時に指定したフラグの差異を中心に見ていきます。

子プロセス生成時のcloneシステムコールに設定したフラグ
・CLONE_CHILD_SETTID
・CLONE_CHILD_CLEARTID
・SIGCHLD

子スレッド生成時のcloneシステムコールに設定したフラグ
・CLONE_VM
・CLONE_FS
・CLONE_FILES
・CLONE_SYSVSEM
・CLONE_SIGHAND
・CLONE_THREAD
・CLONE_SETTLS
・CLONE_PARENT_SETTID
・CLONE_CHILD_CLEARTID

kernel/fork.c

SYSCALL_DEFINE5(clone, unsigned long, clone_flags, unsigned long, newsp,
                 int __user *, parent_tidptr,
                 unsigned long, tls,
                 int __user *, child_tidptr)
{
        return _do_fork(clone_flags, newsp, 0, parent_tidptr, child_tidptr, tls);
}

cloneシステムコールの入り口です。SYSCALL_DEFINE5というマクロでclone関数を定義しています。このSYSCALL_DEFINE5の5は引数の数を示します。
cloneシステムコールの場合、引数は下記のようになります。

引数	型	引数名
1	unsigned long	clone_flags
2	unsigned long	newsp
3	int __user *	parent_tidptr
4	unsigned long	tls
5	int __user *	child_tidptr

long _do_fork(unsigned long clone_flags,
              unsigned long stack_start,
              unsigned long stack_size,
              int __user *parent_tidptr,
              int __user *child_tidptr,
              unsigned long tls)
{
：
        p = copy_process(clone_flags, stack_start, stack_size,
                         child_tidptr, NULL, trace, tls, NUMA_NO_NODE);
：
}

static __latent_entropy struct task_struct *copy_process(
                                        unsigned long clone_flags,
                                        unsigned long stack_start,
                                        unsigned long stack_size,
                                        int __user *child_tidptr,
                                        struct pid *pid,
                                        int trace,
                                        unsigned long tls,
                                        int node)
{
 ：
 1        struct task_struct *p;
 ：
 2        p = dup_task_struct(current, node);
 ：
 3        retval = copy_semundo(clone_flags, p);
 4        retval = copy_files(clone_flags, p);
 5        retval = copy_fs(clone_flags, p);
 6        retval = copy_sighand(clone_flags, p);
 7        retval = copy_signal(clone_flags, p);
 8        retval = copy_mm(clone_flags, p);
 9        retval = copy_namespaces(clone_flags, p);
10        retval = copy_io(clone_flags, p);
11        retval = copy_thread_tls(clone_flags, stack_start, stack_size, p, tls);
：
｝

主要部のみ抜き出しました。
初めに2行目で親プロセスのtask_struct構造体をコピーしています。
このtask_struct構造体はプロセスやスレッドごとに必ず存在して、プロセス/スレッド管理の中枢となる非常に重要な構造体です。「プロセス編」で記載する予定ですので、ここではプロセス/スレッドを管理するための重要な構造体と覚えておいてください。
なお、2のcurrentは、常に現在実行しているプロセス/スレッドのtask_struct構造体へのポインタとなっています。従って、子プロセス/スレッドを生成する処理の場合、必ず親プロセス/スレッドのtask_struct構造体がcurrentに設定されています。

3行目です。copy_semundo( )を呼び出しています。

ipc/sem.c

int copy_semundo(unsigned long clone_flags, struct task_struct *tsk)
{
	struct sem_undo_list *undo_list;
	int error;

1	if (clone_flags & CLONE_SYSVSEM) {
2		error = get_undo_list(&undo_list);
		if (error)
			return error;
3		refcount_inc(&undo_list->refcnt);
4		tsk->sysvsem.undo_list = undo_list;
5	} else
6		tsk->sysvsem.undo_list = NULL;

	return 0;
}

子スレッド生成時のみ以下の処理を行います。
2行目で親スレッドのSystem V セマフォのSEM_UNDOの状態を取得してundo_listに格納します。3行目で親スレッドのundo_listの参照カウントをインクリメントした後に4行目で子スレッドのsysvsem.undo_listに親スレッドのundo_listポインタを設定しています。従って、undo_listは親子で同一のアドレスを指すことになります。
子プロセスのときはNULLを設定します。（6行目）

次に4行目です。

kernel/fork.c

static int copy_files(unsigned long clone_flags, struct task_struct *tsk)
{
	struct files_struct *oldf, *newf;
	int error = 0;

	/*
	 * A background process may not have any files ...
	 */
1	oldf = current->files;
	if (!oldf)
		goto out;

2	if (clone_flags & CLONE_FILES) {
3		atomic_inc(&oldf->count);
4		goto out;
5	}

6	newf = dup_fd(oldf, &error);
	if (!newf)
		goto out;

7	tsk->files = newf;
	error = 0;
out:
	return error;
}

tskは子スレッド or 子プロセスです。
子スレッドの場合は2～5行目の処理によって親プロセス/スレッドのfiles->countを継承する為、3行目でインクリメントしています。
一方、子プロセスの場合は、6行目で親プロセスのfiles_struct構造体をコピーしています。つまり、子プロセスの場合は、プロセス生成時は親プロセスと同じ内容のファイルディスクリプタと同じですが、その後は独立して操作します。
一方で、子スレッドの場合は、files_struct構造体のコピーを生成したりせずに親スレッドと常にファイルディスクリプタのテーブルを共有します。

下記はcopy_process( )の5行目です。

kernel/fork.c

static int copy_fs(unsigned long clone_flags, struct task_struct *tsk)
{
1	struct fs_struct *fs = current->fs;
2	if (clone_flags & CLONE_FS) {
3		/* tsk->fs is already what we want */
4		spin_lock(&fs->lock);
5		if (fs->in_exec) {
6			spin_unlock(&fs->lock);
7			return -EAGAIN;
8		}
9		fs->users++;
10		spin_unlock(&fs->lock);
11		return 0;
12	}
13	tsk->fs = copy_fs_struct(fs);
14	if (!tsk->fs)
15		return -ENOMEM;
16	return 0;
}

子スレッドの場合はCLONE_FSが設定されている為、fs_usersをインクリメントして復帰します。（2～12行目）つまり、親スレッドとfs_struct構造体を共有するため、chrootやchdirの結果を共有します。
一方、子プロセスの場合は親プロセスのfs_struct構造体をコピーして（13行目）、プロセス実行の最初は親プロセスと同じ状態となりますが、その後の挙動は独立します。

下記はcopy_process( )の6行目です。

kernel/fork.c

static int copy_sighand(unsigned long clone_flags, struct task_struct *tsk)
{
	struct sighand_struct *sig;

1	if (clone_flags & CLONE_SIGHAND) {
2		atomic_inc(&current->sighand->count);
3		return 0;
4	}
5	sig = kmem_cache_alloc(sighand_cachep, GFP_KERNEL);
6	rcu_assign_pointer(tsk->sighand, sig);
7	if (!sig)
8		return -ENOMEM;

9	atomic_set(&sig->count, 1);
10	spin_lock_irq(&current->sighand->siglock);
11	memcpy(sig->action, current->sighand->action, sizeof(sig->action));
12	spin_unlock_irq(&current->sighand->siglock);
13	return 0;
}

子スレッドはsignal_struct構造体の内容（シグナルハンドラなど）を共有します。（1～3行目）
子プロセスは親プロセスのsignal_struct構造体をコピーしますが（11行目）、その後は独立して設定します。

次にcopy_process( )の7行目です。

kernel/fork.c

static int copy_mm(unsigned long clone_flags, struct task_struct *tsk)
{
1	struct mm_struct *mm, *oldmm;
2	int retval;

3	tsk->min_flt = tsk->maj_flt = 0;
4	tsk->nvcsw = tsk->nivcsw = 0;
#ifdef CONFIG_DETECT_HUNG_TASK
5	tsk->last_switch_count = tsk->nvcsw + tsk->nivcsw;
6	tsk->last_switch_time = 0;
#endif

7	tsk->mm = NULL;
8	tsk->active_mm = NULL;

	/*
	 * Are we cloning a kernel thread?
	 *
	 * We need to steal a active VM for that..
	 */
9	oldmm = current->mm;
10	if (!oldmm)
11		return 0;

	/* initialize the new vmacache entries */
12	vmacache_flush(tsk);

13	if (clone_flags & CLONE_VM) {
14		mmget(oldmm);
15		mm = oldmm;
16		goto good_mm;
17	}

18	retval = -ENOMEM;
19	mm = dup_mm(tsk);
20	if (!mm)
21		goto fail_nomem;

good_mm:
	tsk->mm = mm;
	tsk->active_mm = mm;
	return 0;

fail_nomem:
	return retval;
}

プロセス空間（0x00000000から0xffffffffの内容）を共有するか否かを決定します。
スレッドの場合は14～15行目で親スレッドのmm_struct構造体を共有、プロセスの場合はdup_mm( )で親プロセスのプロセス空間を全てコピーし、その後は独立してページテーブルの更新などを行います。

ほぼ同じ内容の繰り返しになりますので、copy_process( )の9～11行目は説明を割愛させていただきます。
興味のある方は実際にコードを見てスレッドとプロセスの違いをご理解いただければ、と思います。

纏めると以下の通りです。
基本的にはスレッドは、task_struct構造体以外の上記で出てきた内容を親プロセスと共有します。プロセスの場合は、親プロセスの各データをコピーしますが、その後は独立して使用します。

これらの内容はmanページでも載っていますが、文章だけでなく実際にコードを見ることで「こういうことか」と理解が深まるのではないでしょうか。

ちなみにスレッドが高速と言うのは親スレッドと子スレッドのコンテキストスイッチを行う際にプロセス空間の切り替えが発生しないためです。これについては「スケジューリングアルゴリズム」で述べたいと思います。
また、スレッドは親スレッドのデータ構造を共有するのに対してプロセスはコピーしてその後は独立して使用します。このことからも使用するメモリサイズも軽量といえます。

もう一点、スケジューラからみた場合にプロセスとスレッドの扱いに違いはありません。task_struct構造体を持ったものは全て同列で扱います。

プロセスやスレッドの詳細は「プロセス編」で述べたいと思います。

最後に、子プロセスを生成した時のプロセス空間と子スレッドを生成した時のスレッド空間を比較します。
(※Armでなくx86マシン上で見ます）

・子プロセスの生成
親プロセスのpidが3342、子プロセスのpidが3343です。
親プロセスのプロセス空間（マッピング情報）

$ cat /proc/3342/maps 
00400000-00401000 r-xp 00000000 08:01 1843845                            /tmp/devel/fork_sample
00600000-00601000 r--p 00000000 08:01 1843845                            /tmp/devel/fork_sample
00601000-00602000 rw-p 00001000 08:01 1843845                            /tmp/devel/fork_sample
7f06e80f4000-7f06e82af000 r-xp 00000000 08:01 524387                     /lib/x86_64-linux-gnu/libc-2.19.so
7f06e82af000-7f06e84af000 ---p 001bb000 08:01 524387                     /lib/x86_64-linux-gnu/libc-2.19.so
7f06e84af000-7f06e84b3000 r--p 001bb000 08:01 524387                     /lib/x86_64-linux-gnu/libc-2.19.so
7f06e84b3000-7f06e84b5000 rw-p 001bf000 08:01 524387                     /lib/x86_64-linux-gnu/libc-2.19.so
7f06e84b5000-7f06e84ba000 rw-p 00000000 00:00 0 
7f06e84ba000-7f06e84dd000 r-xp 00000000 08:01 524385                     /lib/x86_64-linux-gnu/ld-2.19.so
7f06e86c0000-7f06e86c3000 rw-p 00000000 00:00 0 
7f06e86da000-7f06e86dc000 rw-p 00000000 00:00 0 
7f06e86dc000-7f06e86dd000 r--p 00022000 08:01 524385                     /lib/x86_64-linux-gnu/ld-2.19.so
7f06e86dd000-7f06e86de000 rw-p 00023000 08:01 524385                     /lib/x86_64-linux-gnu/ld-2.19.so
7f06e86de000-7f06e86df000 rw-p 00000000 00:00 0 
7fff2cb54000-7fff2cb75000 rw-p 00000000 00:00 0                          [stack]
7fff2cbfe000-7fff2cc00000 r-xp 00000000 00:00 0                          [vdso]
ffffffffff600000-ffffffffff601000 r-xp 00000000 00:00 0                  [vsyscall]

次に子プロセスです。

$ cat /proc/3343/maps 
00400000-00401000 r-xp 00000000 08:01 1843845                            /tmp/fork_sample
00600000-00601000 r--p 00000000 08:01 1843845                            /tmp/fork_sample
00601000-00602000 rw-p 00001000 08:01 1843845                            /tmp/devel/fork_sample
7f06e80f4000-7f06e82af000 r-xp 00000000 08:01 524387                     /lib/x86_64-linux-gnu/libc-2.19.so
7f06e82af000-7f06e84af000 ---p 001bb000 08:01 524387                     /lib/x86_64-linux-gnu/libc-2.19.so
7f06e84af000-7f06e84b3000 r--p 001bb000 08:01 524387                     /lib/x86_64-linux-gnu/libc-2.19.so
7f06e84b3000-7f06e84b5000 rw-p 001bf000 08:01 524387                     /lib/x86_64-linux-gnu/libc-2.19.so
7f06e84b5000-7f06e84ba000 rw-p 00000000 00:00 0 
7f06e84ba000-7f06e84dd000 r-xp 00000000 08:01 524385                     /lib/x86_64-linux-gnu/ld-2.19.so
7f06e86c0000-7f06e86c3000 rw-p 00000000 00:00 0 
7f06e86d9000-7f06e86da000 rw-p 00000000 00:00 0 
7f06e86da000-7f06e86dc000 rw-p 00000000 00:00 0 
7f06e86dc000-7f06e86dd000 r--p 00022000 08:01 524385                     /lib/x86_64-linux-gnu/ld-2.19.so
7f06e86dd000-7f06e86de000 rw-p 00023000 08:01 524385                     /lib/x86_64-linux-gnu/ld-2.19.so
7f06e86de000-7f06e86df000 rw-p 00000000 00:00 0 
7fff2cb54000-7fff2cb75000 rw-p 00000000 00:00 0                          [stack]
7fff2cbfe000-7fff2cc00000 r-xp 00000000 00:00 0                          [vdso]
ffffffffff600000-ffffffffff601000 r-xp 00000000 00:00 0                  [vsyscall]

・子スレッドの生成
親スレッドが3380、子スレッドが3381です。

$ cat /proc/3380/maps 
00400000-00401000 r-xp 00000000 08:01 1845511                            /tmp/pthread_sample
00600000-00601000 r--p 00000000 08:01 1845511                            /tmp/pthread_sample
00601000-00602000 rw-p 00001000 08:01 1845511                            /tmp/pthread_sample
01c1d000-01c3e000 rw-p 00000000 00:00 0                                  [heap]
7f9982943000-7f9982944000 ---p 00000000 00:00 0 
7f9982944000-7f9983144000 rw-p 00000000 00:00 0                          [stack:3381]
7f9983144000-7f99832ff000 r-xp 00000000 08:01 524387                     /lib/x86_64-linux-gnu/libc-2.19.so
7f99832ff000-7f99834ff000 ---p 001bb000 08:01 524387                     /lib/x86_64-linux-gnu/libc-2.19.so
7f99834ff000-7f9983503000 r--p 001bb000 08:01 524387                     /lib/x86_64-linux-gnu/libc-2.19.so
7f9983503000-7f9983505000 rw-p 001bf000 08:01 524387                     /lib/x86_64-linux-gnu/libc-2.19.so
7f9983505000-7f998350a000 rw-p 00000000 00:00 0 
7f998350a000-7f9983523000 r-xp 00000000 08:01 528337                     /lib/x86_64-linux-gnu/libpthread-2.19.so
7f9983523000-7f9983722000 ---p 00019000 08:01 528337                     /lib/x86_64-linux-gnu/libpthread-2.19.so
7f9983722000-7f9983723000 r--p 00018000 08:01 528337                     /lib/x86_64-linux-gnu/libpthread-2.19.so
7f9983723000-7f9983724000 rw-p 00019000 08:01 528337                     /lib/x86_64-linux-gnu/libpthread-2.19.so
7f9983724000-7f9983728000 rw-p 00000000 00:00 0 
7f9983728000-7f998374b000 r-xp 00000000 08:01 524385                     /lib/x86_64-linux-gnu/ld-2.19.so
7f998392e000-7f9983931000 rw-p 00000000 00:00 0 
7f9983948000-7f998394a000 rw-p 00000000 00:00 0 
7f998394a000-7f998394b000 r--p 00022000 08:01 524385                     /lib/x86_64-linux-gnu/ld-2.19.so
7f998394b000-7f998394c000 rw-p 00023000 08:01 524385                     /lib/x86_64-linux-gnu/ld-2.19.so
7f998394c000-7f998394d000 rw-p 00000000 00:00 0 
7fff91ea0000-7fff91ec1000 rw-p 00000000 00:00 0                          [stack]
7fff91ffe000-7fff92000000 r-xp 00000000 00:00 0                          [vdso]
ffffffffff600000-ffffffffff601000 r-xp 00000000 00:00 0                  [vsyscall]

上記をみると、子プロセス生成の場合は子プロセスは独自のプロセス空間を持っているのに対して
子スレッドの生成時には親スレッドのプロセス空間を使用していることが分かります。（0x7f9982944000-0x7f9983144000）

次回は、よりスケジューラに近いプロセス/スレッドのスケジューリングポリシーについて述べたいと思います。

前回：【読解入門】Linuxカーネル（概要編）
次回：【読解入門】Linuxカーネル（スケジューラ編その2）