Linux Kernel v 2.4.x ＹＬＵＧ 第８回 カーネル読書会 ２０００．７．１４ 渋谷マークシティ １７Ｆ ＹＬＵＧ　第８回　カーネル読書会 Linux Kernel v 2.4.x ２０００．７．１４ 渋谷マークシティ　１７Ｆ サンブリッジベンチャーハビタット会議室

●実行管理 □　プロセス管理 ☆　プロセスのモデル ☆　プロセスの状態遷移 ☆　プロセスの一生 ☆　プロセススケジューリング ☆　プリエンプション処理 ☆　セマフォ ☆　その他のスケジューリング関数の説明 ☆　プロセスの親子関係 ☆　プロセスＩＤ ☆　シグナル ☆　スレッド

プロセスのモデル － プロセスを構成する資源 ■プロセス管理 プロセスのモデル　－　プロセスを構成する資源 Linux の全てのプロセスは task_struct構造体で管理される 主なメンバ struct task_struct { 　　　　struct files_struct* files; //ファイルディスクリプタ struct signal_struct* sig; //シグナルハンドラ struct mm_struct* mm; //メモリ管理モジュール long stat //プロセス状態 struct list_head runlist; //RUNキュー接続用 long priority; //ベースプライオリティ long counter; //変動プライオリティ char comm[]; //コマンド名 struct thread_struct tss; //コンテキストセーブ域 }; プロセスを生成毎にtask_struct構造体を一つ確保 それ以降はtask_struct構造体を通してプロセスの管理をおこなう

forkにより新しいプロセスが生まれると、全ての資源をコピーする Copy-On-Write 書き込み処理がある までコピーしない task_struct mm_struct mm_struct task_struct pid =5 mm sig files pid =6 mm sig files Memory Object signal handler table signal_struct signal handler table signal_struct COPY signal handler table file_struct file signal handler table file_struct ファイルディスクリプタ のみコピーし、ファイル 構造体は共有

CPU プロセスモデル － プロセスの状態遷移 プロセスの状態（state) suspend signal ptrace exit プロセスモデル　－　プロセスの状態遷移 プロセスの状態（state) TASK_RUNNING 実行待ちまたは実行状態 TASK_INTERRUPTIBLE 待ち状態（シグナル受信可能） TASK_UNINTERRUPTIBLE 待ち状態（シグナル受信不可能） TASK_ZOMBIE ゾンビ状態（exit後の状態） TASK_STOPPED サスペンド状態 CPU suspend signal ptrace TASK_RUNNING exit TASK_STOPPED TASK_ZOMBIE resume signal ptrace preempt scheduling sleep_on interruptible_sleep_on wait TASK_RUNNING (READY) Fork close NULL TASK_INTERRUPTIBLE TASK_UNINTERRUPTIBLE wake_up wake_up_interrupt

fork プロセスモデル － プロセスの一生 － fork do_fork (フラグ, プロセスコンテキスト） 空きtask_struct一つ確保 alloc_task_struct() プロセスIDを付ける get_pid() task_structの各メンバの初期化 ファイルディスクリプタテーブルのコピー copy_files() カレントディレクトリ、umask情報などのコピー copy_fs() シグナル情報のコピー copy_sighand() 親プロセスコンテキストのコピー copy_thread() 仮想空間をCopy-On-Writeで複製コピー copy_mm() 生成した子プロセスをRUNキューに繋ぐ wake_up_process() ※スレッドもdo_fork()で生成される（引数が違うだけ）

exec プロセスモデル － プロセスの一生 － exec do_execve (ファイル名, 引数，環境，レジスタ） して新しいコマンドオブジェクトをマップする。 do_execve (ファイル名, 引数，環境，レジスタ） ファイルのオープン open_namei() exec後のユーザID、グループIDの計算、 prepare_binprm() ファイルヘッダの読み込み コマンド名、環境変数、起動引数の読み込み copy_strings() 各バイナリ種別ごとのハンドラ呼び出し search_binary_handler() ※ELFフォーマットの場合 search_binary_handler()からdo_load_elf_binary()を呼び出す ※ダイナミックリンクの場合 ダイナミック・リンカをマップする

load_elf_binary() プロセス空間 テキスト データ域 ELFヘッダの解析 　　　exec前のプロセス資源の解放 flush_old_exec() スタック空間を生成し、引き継ぐ環境変数/ 引数域を置く setup_arg_pages() 実行ファイルをプロセス空間へマップ elf_map()、do_mmap() 　　　ダイナミックリンカ(ld*.so.*)をプロセス 空間へマップ load_elf_interp() 　　　実行時のUID、GIDを決定する compute_creds() bss領域の空間生成 set_brk()、do_brk() bss領域の０クリア padzero() execから復帰したときの実行開始番地(IP), 　　　　　　　スタックポインタ(SP)の設定 start_thread() ダイナミック リンカ ダイナミック リンク ライブラリ スタック域

exit プロセスモデル － プロセスの一生 － exit do_exit (終了コード） 　（シグナルを受けて死ぬときなどにも呼び出される） do_exit関数ではtask_structを除く全ての資源の解放を行い、exit_notify関数で 親プロセスにSIGCHLDを送出する。 SIGCHLDを受け取った親プロセスは、 ZOMBIE状態になった子プロセスを探してtask_structの解放を行う。 do_exit (終了コード） このプロセス用のタイマを止める del_timer_sync() System V IPCのセマフォを開放する sem_exit() 仮想空間の開放 __exit_mm() ファイルのクローズと管理域の解放 __exit_files() カレントディレクトリ、umask情報の解放 __exit_fs() シグナルの破棄と管理域の解放 __exit_sighand() プロセスの状態をゾンビ（TASK_ZOMBIE）に変更 親プロセスへ通知 exit_notify() CPUを放棄する(スケジューラを呼ぶ） schedule() ※親プロセスは、release()を用いてゾンビ状態のtask_struct構造体を解放する

プロセススケジューリング － スケジューラ current スケジューラは、RUNキューにキューイングされている実行可能なプロセスの中で プロセススケジューリング　－　スケジューラ スケジューラは、RUNキューにキューイングされている実行可能なプロセスの中で 最も優先順位の高いプロセスにCPU（実行権）を与える。現在実行されているプロセスは current というポインタによって示されている（プロセスとスレッドは同じように扱われる）。 current task_struct task_struct task_struct task_struct runqueue_head RUNNING RUNNING RUNNING RUNNING ※何も実行するプロセスが無くなるとスケジューラはidleと呼ばれる何もしないプロセスにＣＰＵ（実行権）を渡す schedule() タスクキュー tq_schedulerの実行 run_task_queue() ボトムハーフ・ハンドラ呼び出し do_softirq() プリエンプション要求をクリア if (スケジューラを呼び出したプロセスの状態　!=　TASK_RUNNING) プロセスをＲＵＮキューから外す del_from_runqueue() while (ＲＵＮキューに繋がっている全プロセスに対し） 最も高いプライオリティのプロセスを探す goodness() while(システム上の全プロセスに対し） プライオリティの再計算 プロセスコンテキストの切り替え switch_to()

CPU プロセススケジューリング － プロセスの切り替え tss tss Process Switch save restore save プロセススケジューリング　－　プロセスの切り替え プロセスの切り替えは、現在実行中のプロセスのコンテキスト（ＣＰＵの状態：レジスタ情報） を保存し、次に実行させるプロセスのコンテキストをＣＰＵ上にロードすることによって行う。 再び実行を開始するときは、メモリにセーブしたプロセスのコンテキストをＣＰＵ上にロード しなおせば、中断された地点から処理を再開することができる。 Linuxでは、switch_to()が、コンテキストの切り替えを行っており、コンテキストのセーブ域は プロセスのカーネルスタックとtask_struct内に確保されたtss領域を使用する。 FROM task_struct TO task_struct tss tss Process Switch save restore CPU save restore kernel stack kernel stack

プロセススケジューリング － プロセスの同期 プロセススケジューリング　－　プロセスの同期 実行中のプロセスが待ち状態になる場合、待ち要因ごとに用意されているwaitキューヘッド に自分自身を繋ぎ、CPUを放棄する（RUNキューから外してスケジューラを呼ぶ）。 このようなことをする関数としてsleep_on()、interruptible_sleep_on()が用意されており、待ち状 態からシグナルによって起床するかしないかという違いがある。 wait_queue_head_t wait_queue wait_queue wait_queue wait_queue task_struct task_struct task_struct task_struct INTER RUPTIBLE UNINTER RUPTIBLE INTER RUPTIBLE UNINTER RUPTIBLE sleep_on(WAITキューの先頭）　または　interruptible_sleep_on(WAITキュー） スタックにwait_queueを用意する 現在のプロセスの状態をTASK_UNINTERRUPTIBLEに変更 （ interruptible_sleep_on()の場合はTASK_INTERRUPTIBLEに変更） wait_queueにカレントプロセスを登録する WAITキューヘッドにwait_queueを繋ぐ add_wait_queue() スケジューラを呼び出してCPUを放棄する schedule() WAITキューヘッドからwait_queueを外す remove_wait_queue()

sleep_on()、interruptible_sleep_on()によって待ち状態になったプロセスは、イベントにより 起床される。Wake_up()、wake_up_interruptible()によって起床されたばかりのプロセスは RUNキューに繋がっているが、WAITキューヘッドにも繋がったままとなっている。このプロ セスは、再度実行権が与えられた時に、まず自分自身をWAITキューから外す。 ※この方式のメリットは、割り込みハンドラからの延長でプロセスの起床を行う場合、WAIT 　キューヘッドの操作を行う必要が無く、排他処理を単純化できるところにある。 wait_queue_head_t wait_queue wait_queue wait_queue wait_queue task_struct task_struct task_struct task_struct INTER RUPTIBLE UNINTER RUPTIBLE RUNNING UNINTER RUPTIBLE Wake_up_process task_struct task_struct task_struct RUNNING RUNNING RUNNING runqueue_head current

__wake_up(WAITキューヘッド, モード） while (WAITキューヘッドで待っている全プロセスに対し）　｛ モードで指定されている属性のプロセスなら起床させる __wake_up_process() 一つだけ起床する指定（TASK_EXCLUSIVE)なら　break ｝ __wake_up_process(プロセス） プロセスの状態をTASK_RUNNINGに変更 if (指定されたプロセスが、まだRUNキューに繋がっていない）　｛ RUNキューに繋ぐ add_to_runqueue() 再スケジューリング要求 schedule_idle() ｝ ※v2.2では、wake_up()は対象となるWAITキューヘッドで待ち状態の全プロセスを 　　RUN状態にしていた。 　　V2.4 からは性能改善のため、WAITキューヘッドで待ち状態のプロセスのうち 　　先頭のプロセスだけをRUN状態にすることができるようになった。これを利用する 　　には、プロセスの属性をTASK_EXCLUSIVEにすればよい。

__wake_up()にはラッパが被せてあり、v2.2までの関数と互換性が考慮されている ●wake_up (WAITキューヘッド） TASK_UNINTERRUPTIBLE, TASK_INTERRUPTIBLE両方で待ちになっている プロセスを起床する。ただし、起床するプロセスはキューの先頭に繋がっているプ ロセス（TASK_EXCLUSIVE）だけである。TASK_EXCLUSIVE属性で待っている プロセスを起床したら、それ以外のプロセスは起床しない。 ●wake_up_all (WAITキューヘッド） 全てのプロセスを起床する。TASK_EXCLUSIVE属性は無視する。 ●wake_up_interruptible (WAITキューヘッド） TASK_UNINTERRUPTIBLE, TASK_INTERRUPRIBLE両方で待ちになっている プロセスを起床する。ただし、起床するプロセスはキューの先頭に繋がっている プロセス（TASK_EXCLUSIVE）だけである。TASK_EXCLUSIVE属性で待って いるプロセスを起床したら、それ以外のプロセスは起床しない。 ●wake_up_interruptible_all (WAITキューヘッド） 全てのプロセスを起床する。

task_structのneed_reschedを設定し、reschedule_idle()呼び出し プリエンプション処理 プロセスがwait_up_process()によって実行可能になるとRUNキューにキューイングされる （RUNキューにキューイングされるだけでは、プライオリティが高くても実行権は与えられない） ＜ RUNキューにキューイングされている プロセスのプライオリティ 実行中のプロセスのプライオリティ CPU明け渡し task_structのneed_reschedを設定し、reschedule_idle()呼び出し プリエンプト要求 スケジューラ　schedule() 以下のポイントで再スケジューリング ・システムコールの終了時 ・割り込みハンドラの終了時 ・idle処理時 ※明示的にスケジューラを呼び出さない限り、カーネルコード実行中には 　　プリエンプションは発生しない　→　資源排他の単純化

セマフォ Linuxでは、資源待ち合わせのための汎用関数としてカウントセマフォが用意されている。 資源 down() down() 資源使用 プロセス１ 資源使用 要求 資源 プロセス２ down() down() 資源使用 要求 資源使用 不可能 使用中 semaphore型 メンバ セマフォ獲得 セマフォ待ち プロセス１がup()によって資源を解放 するまでWAIT状態になる ※V2.2までは up() でセマフォ待ちになっている全てのプロセスを起床し、早いもの勝ち 　でセマフォを獲得する処理になっていたが、v2.4からは待ちキューの先頭のプロセス 　のみを起床するように変更された

semaphore count (セマフォ値） wait_queue wait_queue wait_queue wait_queue_head_t task_struct task_struct task_struct count (セマフォ値） UNINTER RUPTIBLE EXCLUSIVE UNINTER RUPTIBLE EXCLUSIVE UNINTER RUPTIBLE EXCLUSIVE

先頭のプロセスだけを起床させる wake_up() Down （セマフォ） if （count が残っている場合） count を一つ減らして　リターン（セマフォ獲得成功） スタック上にwait_queueを作成 プロセスの状態を TASK_INTERRUPTIBLE | TASK_EXCLUSIVEに変更 wait_queueにプロセスを登録 セマフォにwait_queueを繋ぐ add_wait_queue_exclusive() while (1) { if （countが０の場合） { スケジューラを呼び出す schedule() プロセスの状態をTASK_INTERRUPTIBLE | TASK_EXCLUSIVEに変更 } else { count　を一つ減らす プロセスの状態をTASK_RUNNINGに変更 セマフォからwait_queueを外す remove_wait_queue() } up （セマフォ） count を一つ増やす セマフォで待っているプロセスのうち、 先頭のプロセスだけを起床させる wake_up() ※Linuxの機能として、シグナルで起床可能なdown_interruptible（）や、 　要求した時点で獲得可能ならばセマフォを確保するdown_trylock()も用意されている。

その他のスケジューリング関数 ●reschedule_idle() 指定されたプロセスが、現在実行中のプロセスよりプライオリティが高い場合 スケジューラにプリエンプション要求をする ●goodness() プロセスのプライオリティを得る ●add_to_runqueue() プロセスをRUNキューの先頭に繋ぐ ●del_from_runque() プロセスをRUNキューから外す ●move_last_runqueue(), move_first_runqueue() プロセスをRUNキューの最終または先頭に繋ぎかえる ●add_wait_queue(WAITキューヘッド） プロセスをWAITキューヘッドの先頭に繋ぐ ●add_wait_queue_exclusive（WAITキュー） プロセスをWAITキューヘッドの最終に繋ぐ ●remove_wait_queue() プロセスをWAITキューから外す ●wake_up_process_synchronous() wake_up_process()とほぼ同じだが、プリエンプション要求をしない ●wake_up_sync() wake_up(), wake_up_interruptible()とほぼ同じだが、プリエンプション要求を しない。PIPE処理などの処理が完了するまでプリエンプションしない方が性能 面で有利なときに使用する

プロセスの親子関係 各プロセスは親子関係をもっている。これは、子プロセスの終了を親プロセスが待ちあわせる waitシステムコールなどを実現するためである。 forkシステムコールで子プロセスを生成した時、プロセスのtask_struct間には以下のような リンク構造ができる。親プロセスが子プロセスより先に終了した場合は、子プロセスの親として initプロセスを指定する。initプロセスは唯一親を持たないプロセスである。 親（parent) task_struct p_opptr p_pptr p_cptr p_ysptr p_osptr p_opptr オリジナルの親 p_pptr 親 p_cptr 一番年下の子 p_ysptr 弟 p_osptr 兄 三男（child) 次男（child) 長男（child) task_struct p_opptr p_pptr p_cptr p_ysptr p_osptr task_struct p_opptr p_pptr p_cptr p_ysptr p_osptr task_struct p_opptr p_pptr p_cptr p_ysptr p_osptr

ypcat hosts | grep sun > list & プロセスID 各プロセスは識別子としてプロセスIDを持っている。このIDはプロセスの生成（fork)時に システム内で重複しないようにカーネルが割り当てる。プロセスはプロセスIDの他に、 プロセスグループID、セッションIDも持っている。 Session 3 Process group 6 ypcat hosts | grep sun > list & pid:6 pid:7 Process g roup 4 ls | more pid:4 pid5 $ ls | more $ ypcat hosts | \ _ grep sun > list & Process group 3 csh pid:3 session reader プロセスID、プロセスグループID、セッソンIDの操作を行っているのはシェルであり、シェル を親とするセッションセッションを開いてその中で起動するジョブごとにプロセスグループを 作成する。この動作はシェルによって様々である

ypcat hosts | grep sun > list & 各種デーモンは、他のプロセスからの干渉を防ぐために独自のセッションを持っている。 Session 3 Process group 6 ypcat hosts | grep sun > list & pid:6 pid:7 ls | more pid:4 pid5 Process g roup 4 Session X デーモンの独自セッション csh pid:3 session leader Process group 3 $ ls | more $ ypcat hosts | \ _ grep sun > list & プロセスグループID、セッションIDは自由に割り振られるわけではなく、以下のルールに 従って割り振られる。 ・セッションリーダはプロセスグループリーダを兼ねる。 　（セッションリーダーはプロセスグループを変更できない） ・セッション中に複数のプロセスグループを持っている。 　自分が新しいプロセスグループを生成できる。 　（自分のpidをグループIDとする） 　セッション内に存在するどのプロセスグループに移動することも可能。

プロセスID、プロセスグループID、セッションIDに関連する関数は以下のとおり ●sys_setpgid() プロセスのプロセスグループＩＤを変更する。 指定可能なＩＤは、そのプロセスのプロセスＩＤまたはプロセスが属している セッションに存在するプロセスグループＩＤ。 ●sys_getpgid() プロセスのプロセスグループＩＤを取得する。 ●sys_setsid() プロセスが新しいセッションを開く。 セッションＩＤ、プロセスグループＩＤともに発行したプロセスのプロセスＩＤとなる。 ●sys_getsid() プロセスのセッションＩＤを求める。

kill シグナル シグナル（signal)はプロセスに対して非同期なイベントを通知する手段である 例外発生 シグナル システムコール 変換 カーネル 例外発生 シグナル 変換 システムコール kill シグナル 受信 事象 シグナル通知 ・プロセスが例外を発生したとき、カーネルはシグナルに変換してプロセスに通知する。 ・カーネル内である事象が発生したことを通知するため、カーネルがシグナルを生成 　する場合もある（pipe, ttyなど。 ・プロセスがkillシステムコールにより明示的にシグナルを生成することも可能。

send_sig() プロセスに対してシグナルを送ったとき、すぐに対象となるプロセスが削除されたり、 プロセスに登録されているハンドラが起動されるわけではない。 プロセス シグナル送信のみ send_sig() 受信のみ プロセス コンテキスト シグナル受信 チェック 他プロセス シグナルを 受信している do_signal() プロセスハンドラ プロセスはシグナルの受信チェックを以下の契機で行っている ・システムコールの出口 ・例外ハンドラの出口 ・割り込みハンドラ

シグナル － 関数説明 シグナル処理で重要な役割を担っている関数 ●sys_signal(シグナル種別, ハンドラ関数) シグナル　－　関数説明 シグナル処理で重要な役割を担っている関数 ●sys_signal(シグナル種別, ハンドラ関数) シグナル種別のハンドラをプロセスのシグナルハンドラテーブルに登録する。 シグナルハンドラデーブルstruct signal_structはtask_structからリンクされている） ●do_sigaction(シグナル種別, アクション….) シグナルハンドラの実行に関する詳細な設定を行う。 ●send_sig(シグナル種別, プロセス) プロセスにシグナルを送信する。 ●do_signal（） シグナルを受信したプロセスが呼び出すシグナル受信処理。 ●handle_signal() シグナルハンドラ実行用のスタックを準備して初期化を行う。 ●sys_sigreturn() シグナルハンドラからの復帰（ユーザのシグナルハンドラが終了すると自動的に 呼び出される。 シグナル受信の無視が必要な場合は、signalシステムコールで明示的に指定できる。 シグナルマスクはsys_sigprocmaskによって制御され、マスクするシグナルはtask_structの blockedに保持している。Send_sig()でプロセスにシグナルが送信されるとtask_structの signalに保持される。

シグナル － SIGCHLDシグナル SIGCHLDシグナルはプロセスが終了した時に親プロセスに送信される。 子プロセス 生成 fork() 受信処理 SIGCHLD送信 終了 SIGCHLDを受信したプロセスの受信処理（do_signal)では、以下の処理がされる ・デフォルト（SIG_DFL)時 送信側で何も行わずにシグナルを破棄する。 ・無視指定（SIG_IGN)時 ZOMBIE状態となった子プロセスの資源を解放する。 ・ハンドラが登録済み 通常シグナルを同じ扱い ※子プロセスの終了を待つ必要が無い場合、SIGCHLDシグナルを無視指定にして 　　おけば、システム内にZOMBIE状態のプロセスが増えるこがなくなる。

シグナル － サスペンドシグナル サスペンドシグナルはプロセスの実行を一時中断（TASK_SUSPEND)させる シグナル　－　サスペンドシグナル サスペンドシグナルはプロセスの実行を一時中断（TASK_SUSPEND)させる TTYドライバから生成されるもの SIGSTP, SIGTTIN, SIGTTOU killシステムコールから送られるもの SIGSTOP ・シグナル無視（SIG_IGN)指定の場合は何もしない ・シグナルを受信したプロセスは、シグナル受信処理（do_signal)内でTASK_SUSPEND 　状態になり、処理を中断する（schedule()でCPUを明け渡す）。 中断状態(TASK_STOP)のプロセスを再開させるもの SIGCONT ・シグナル送信処理（send_sig)内で、シグナル受信処理(do_signal)の中断点から 　処理を再開する。 ・サスペンドシグナルに対応するシグナルハンドラが登録されていればハンドラを 　実行する（do_signal)。 ※viをサスペンドした後、リジュームした時のリドローなどで利用

シグナル － シグナル関連のデータ構造 シグナル － シグナル関連のその他の関数 シグナル　－　シグナル関連のデータ構造 シグナル管理用のデータ構造体は、各プロセスごとにtask_struct構造体の内部にもっている struct task_struct { : int sigpending //処理が必要な保留中のシグナル sigset_t signal //シグナル受信フラグ signal_t blocked //シグナルマスクフラグ signal_struct *sig //シグナルハンドラテーブルへのポインタ } シグナル　－　シグナル関連のその他の関数 ●sigaddset(), sigdelset() シグナル受信フラグのON/OFF操作を行う ●sigaddsetmask(), sigdelsetmask() シグナルマスクフラグのON/OFF操作を行う ●sigismember() 指定されたシグナルに対応するフラグがONかOFFかをチェックする ●kill_something_info(), kill_proc(), kill_pg() 指定されたプロセス、プロセスグループに属するするプロセスに対してシグナルを 送信する。セッションに属するプロセス群にシグナルを送るkill_sl()もある。 ●sys_sigprocmask() シグナルマスクを変更する

スレッド Linuxでは、実行単位となるプロセスとスレッドはまったく同一のものとして実現している。 スレッドがプロセスと異なっている点は、プロセスが保有する各種資源を 共有している点のみである。 スレッド プロセス プロセス プロセス スレッド スレッド clone 資源 資源 資源コピー 資源 fork

cloneによるスレッドの生成の場合、プロセスの生成の時と違って資源のコピーをまったく 行わず、両方のコンテキストから同じ資源が参照できる task_struct mm_struct task_struct pid =8 mm sig files pid =8 mm sig files Memory Object signal handler table signal_struct signal handler table file_struct file