連載 / Linux のプートプロセスをみる一 0 rest-init() は、プロセス番号 1 (init プロセス ) と呼 はれるカーネルスレッドを生成し、その後に CPU を休 止状態にするルーチンを呼び出します。そのソースコード は、 start-kernel() と同じく init/main. c で定義されて います。 0530 : 0531 0532 : 0533 : 0534 : 0535 : 0536. static void rest—init(void) kernel-thread(init , NULL, CLONE_FS ICLONE_FILESI CLONE_SIGNAL) ; unlock—kernel ( ) ; current—>need„resched = 1 ; cpu—idle() ; 図 2 current はこ current →・ こを指す カーネル スタック領域 8KB プロセス デスクリプタ 532 行目の kernel-thread() は、カーネルスレッドを 生成するサプルーチンです ( 詳しくはします ) 。 532 行目で生成された init プロセスは実行可能プロセ スのリストに登録されますが、この時点では、、まだ " 動き 始めていません。 init プロセスか動き始めるタイミングは プロセス・スケジューラしだいです。 ⅲ it プロセスは、 CPU か割り当てられると init() を実 行します (init() については次回に説明します ) 。 533 行目の unlock-kernel() は、グローノヾルカーネル・ ロックを解放します。 swapper プロセスは、以下のよう に start-kernel() のう頁でカーネルにロックをかけてい ました。 533 行目の unlock-kernel() は、 551 行目の lock-kernel() に対応するものです。 0542 : void start_kernel(void) 0543 : { 0551 : lock—kernel() ; 0623 : } 534 行目の current は、現在 CPU か夫行している プロセス ( つまり swapper) のプロセス・デスクリプタを 孑嗣ーポインタ 1 です。プロセス・デスクリプタとは、 PID や UID 、リソース情報、実行ステータスなど、プロセス のすべての 1 帯にを管理するデータ構造体で、カーネルモー ド・スタックと同しプロックのなかにあります ( 図 2 ) 。 swapper プロセスの current は、 init-task-union と 同しアドレスを指します。 init-task-union は、カーネル 1 正確にはマクロてす。詳しくは include/asm-i386/current. h を参 照してください。 UNIX MAGAZINE 2003.3 内に静的に確保された 8KB の大きさのデータ領域です ( 詳しくは ( 忘れてしまった人は ) 2002 年 11 月号を参照 してください ) 。 この current は以降の説明で何回も登場するので、憶 えておきましよう。 534 行目の need-resched は、スケジューラの呼出し を指示するフラグです。つまり、プロセスに対して、 「そろそろ CPU を明け渡してくれへんかいな」 と、、強制退去 " を指示します。ただし、 need-resched を セットした瞬間に CPU が解放されるわけではありませ ん。プロセスの切替えか発生するのは、あくまでもスケジ ューラか呼び出されるときであり、そのスケジューラの呼 出しを指示するフラグが need-resched です。具体的に は、 1 つのプロセスが CPU を長時間使用したとき、タイ マー割込みのハンドラが need-resched をセットします。 534 行目では、自分自身の need-resched をセットして みずから CPU を解放し、はかのプロセス ( ここでは init プロセス ) に割り当てようとしています。 swapper プロセスは、最彳麦の 535 行目で cpu-idle() を呼び出して眠りに入ります。そして、プロセス・スケ ジューラによりⅲ it プロセスか動き出します。 cpu-idle() cpu-idle() は CPU を体止させ、いわゆる、、アイドル " 状態にする無限ループです。 実行可能状態のプロセスか現れると、プロセス・スケ ジューラを呼び出して CPU を譲ります。そして、プロ 147

連載 / Linux のフートプロセスをみる一 0 図 12 タスクリスト (a) 挿入前 (b) 挿入後 init_task init—task prev_task next task prev_task next_task task prev_ next task → prev—task →・ next task こに挿入 prev_task next task prev_task next task プロセス間の親子系 図 13 、、実行可能 ' に設定し、プロセスをランキューの : 麪頁に挿 入する処理をおこないます。ランキューは、デスクリプタ のメンノヾー run-list ( 614 ~ 615 行目 ) をイ吏用して図 14 の ようなリンク構造を作ります。この図の runqueue-head は、ランキューリストの地頁を指すポインタです。その構 造は、以下のように双方向のポインタをイ尉寺しているだけ です。 struct list—head { struct list_head *next , *prev ; struct list—head runqueue—head ; カーネルは、特定のプロセス ID をもつプロセス・デス クリプタを検索することがあります。この検索を高速にお 最後に、子プロセスのプロセス ID を返して do-fork() こなうため、カーネルはハッシュテープルを利用します。 の処理は終ります。 718 行目の hash-pid() は、プロセスをハッシュテープル do-fork() から sys-clone() へ、、返る " のは、親プロセ に登録する処理をおこないます。 スだけである点に注意してください。 そして、いよいよ大詰め wake-up-process() を呼び出 します。 前述したリストのうち、ランキュー (runqueue) と呼 本文に出てきた用語について、簡単な説明を記しておき はれるリストは、実行可能状態のプロセスを管理します。 ます。 つまり、プロセスが実行可能な状態になったら、プロセ ス・デスクリプタをランキューに登録しておけは、あと CPL (Current PriviIege LeveI : 見行寺オレベル ) ・ はプロセス・スケジューラがここから選んで実行してくれ CPU か実行中のプログラムがもつ罸レベル。 ます。 DPL (Descriptor PriviIege LeveI : デスクリプタ特オ レベル ) : セグメント / ゲート・デスクリプタを参照する 725 行目の wake-up-process() は、プロセスの状態を p_cpt r p—p ptr p—p ptr p—ys pt r 兄 p—OS ptr 集 五ロ 用 161 UNIX MAGAZINE 2003.3

連載 / Linux のプートプロセスをみる一 0 図 10 copy-thread() ~ 里 2 EAX を 0 に更新 子プロセス pt—regs 親プロセス pt_reg s の 内容をコピー 3 ESP を設定 EAX ESP pt—regs init 4 ESP を 設定 thread ESP i387 EIP thread i387 6 ~ i387 の内容をコピー 5 E 旧を設定 ret_from fork ん 3 。したがって、親プロセスのカーネルスタックをすべ 舌を戻しましよう。 664 行目を実行している時点で変 数 stack-start には、 init のアドレスか骼納されていま てコピーする必要はないのです。 す ( 図 8 ) 。屯に考えると、システムコールから彳知帚する 0667 : p->semundo = NULL ; とき (system-call() の 211 行目 ) に init のアドレスが ESP にロードされることになります。 「 init ってテキスト領域にあるんとちゃうん。そこにスタ p->swappable ックってどういうこと ? 」 p—>exit—signal = clone—flags & 0X000000ff ; と疑間に思うかもしれません。ここで、カーネルから発行 0677 : p— >pde ath— s ignal されたシステムコールは CPL が変化しないことを思い p —>counter 出してください。このとき、 IRET 命令はレジスタ SS (current—>counter 十 1 ) > > 1 ; 0686 : current—>counter > > = 1 ; と ESP をスタックから復帰させません。つまり、スタ if ( ! current—>counter) 0687 : ックには図 11 のようにデータか積まれていますが、 sys- 0688 : current—>need_resched = 1 ; tem-call() の 211 行目でレジスタにロードされるのは 667 ~ 688 行目では、親プロセスから受け継ぐことがで EBX から EFLAGS までで、残りの ESP と SS の領域 きな弱辭長を初期化します。 はアクセスされないのです。しかし、 ESP の領域に init いよいよここからが d 。ー f 。 rk ( ) のクライマックスです。 のアドレスをオ褓内する理由は分かりませんでした。 こまでの処理では、新しいプロセスの、、存在 " を知るの 子プロセスは、親フ。ロセスのカーネルスタックの内容を は do-fork() だけで、その外からはみえませんでした。 すべてコピーするわけではありません。親プロセスは ker- こからは、新しいプロセスを、、外からみえる " ようにする nel-thread() へ戻り、さらに rest-init() へ戻ります。し 処理か始まります。 かし、子プロセスは、 kerneLthread() の 499 ~ 503 行 目から分かるように、 rest-init() へ戻ることはありませ 3 そオ IJ ユ前に init() から kernel-thread() に戻ることもありません。 一三ロ 0672 : p—>parent_exec_id p->self—exec—id; 0675 : 0676 : 0685 : 159 UNIX MAGAZINE 2003.3

連載 / Linux のプートプロセスをみる一 0 セス・スケジューラは、はかに実行可能なプロセスか存在 ーチンを呼び出します。 しなけれは swapper プロセスお尺し、 CPU はふたた 一見したところ、 80 ~ 89 行目のアイドルルーチンでは び無限ループに戻ってアイドル状態になります。 need-resched がセットされることはなく、 134 ~ 135 行 目のループを抜け出すことは永久になさそうです。しか cpu-idle() は、 arch/i386/kernel/process. c で以下 し、心配は無用です。 need-resched は、割込みハンドラ のように定義されています。 によってセッ・・トされるのです。 static void default—idle(void) 0080 : ただし、 rest-init() から呼び出された場合は、すでに 0081 : { need-resched がセットされているため、この部分を素通 if (current—cpu—data. hlt—works—ok & & 0082 : ! hlt—counter) { りしてすぐに 136 行目の schedule() を呼び出します。 —asm—-("cli" "memory" ) ; if ( ! current—>need—resched) —asm——("sti; hlt" "memory") ; else "memory") 0083 : 0084 : 0085 : 0086 : 0087 : 0088 : 0089 kernel-thread() kernel-thread() は新しいカーネルスレッドを生成する サプルーチンで、 arch/i386/kerneI/process. c のなかで 定義されています。そのコードは、次のようにほとんどイ ンライン・アセンプリ命令で書かれています。 int kernel—thread(int (*fn) (void * ) , 0487 : void *arg, unsigned 10 Ⅱ g flags) —asm—— ( "sti " void cpu—idle (void) 0123 : 0124. while ( 1 ) { void (*idle) (void) = pm-idle; if ( ! idle) idle = default_idle; while ( ! current—>need—resched) idle() ; schedule() ; check—pgt—cache ( ) ; 0130 : 0131 : 0132 : 0133 : —volatile——( 0134 : _asm 。 vl %%esp , %%esi\n\t " 0135 : : 00 、 $ 0 、 80 \ 0 \ 、 " 0136 : "cmpl %%esp,%%esi\n\t" 0137 : "je lf\n\t" 0138 : 0139 "movl % 4 , %%eax\n\t ” 0499 : 80 ~ 89 行目は、デフォルトのアイドルルーチンです。 "pushl %%eax\n\t " 0500 : ” ca11 *%5\n\t " 0501 : このルーチンは、 HLT 命令を実行して CPU を休止しま "movl % 3 , %O\n\t " 0502 : す。ただし、そのままだと永遠に止まってしまい、、、アイ "int $ 0X80 \ Ⅱ " 0503 : 0504 : ドル " といえなくなります。そこで、前もって STI 命令 =&a" (retval) , 0505 : によって割込み可能な状態にしておきます。 CPU は、外 ・ " 0 ” ( ー NR_c10ne), 0506 : 部から割込み信号を受け取ると測胙を再開します。 0507 : "b" (flags ー CLONE VM) 0508 : 131 行目の pm-idle には、デフォルト以外のアイド 'memory" ) ; 0509 : ルルーチンへのポインタか格納されています。たとえば、 0510 : return retval ; 0511 : } ACPI のモジュールを組み込むと、その初期化処理で pm-idle に専用アイドルルーチンへのホインタが設定され このコードを見て、 ます。 「なんやこさつばり分からんがな ! 」 134 ~ 135 行目は、 need-resched がセットされるま と怒りを爆発させたり、あるいはクラクラと気か遠くなっ でアイドルルーチンを無限に呼び出すループです。 idle() た人がいるかもしれません。 は、割込みなど、、何かの拍子 " に戻ってくることがありま 上記のコードを C 言語で書き直すと、だいたい次のよ す。しかし、 need-resched がクリアされている、つまり うな感しになります。 はかに実行可能なプロセスがない場合は、再度アイドルル 0488. 0491 : 0492 : 0493 : 0494 : 0495 : 148 UNIX MAGAZINE 2003.3

0 図 2 度ファイルを生成するプログラム (makefreqfiles) # ! /usr/bin/env ruby # ー * ー mode: ruby ー * ー reqtllre 'kconv require 'ftools ' require parsedate ' 土て di て = Fi1e . dirname($O) $ : くく irdir requxre 'fileattr' require ' timerange ) class FreqfiIeGenerator MECAB = "/usr/local/bin/mecab" ゝ NKF = "/usr/local/bin/nkf def initialize(getaroot) @getaroot = getaroot @home = ENV [ ' HOME ' ] @offset = @home. length + end def generate (dir) path = "#{@home}/#{dir}" Find. find(path){ は il 引 @file file 1 def create-freqfile "/tmp/mecabtmp#{$$}" tmpfile = mecab = IO. popen ( "#{NKF} ー #{MECAB} @fileattr. text . each { ー line ー mecab. puts line mecab . close freq = { } Fi1e. open(tmpfile,"r"){ は一 f . each { は i 取引 word = 1ine ・ split . first . downcase freq [word] freqCword] . t0—i + 1 - if word ! = ' EOS , Fi1e. delete(tmpfile) Fi1e. makedirs (Fi1e. dirname (@freqfile)) Fi1e.open(@freqfile."w"){ は一 f . puts "@#{@file}" freq. each { ー word , count ー next if word [ 0 ] = = OxOa f . puts "#{count} #{word}" TimeRange ・ rangefreq(@fileattr.time) ・ each { lfreqlinel f . puts freqline end @fileattr = Fi1eAttr . new(file) relpath = file [@offset.file. length] '#{@getaroot}/freqfiles/=+ @freqfile #{relpath}. freq" if @fileattr. valid? & & freqfile—missing? end Fi1e . stat(@file) . mtime Fi1e.stat(@freqfile) . mtime く - !test(?f.@freqfile) Ⅱ def freqfile—missing? end end create—freqfile puts @freqfile されたときだけ頻度ファイルを更新するようにすれば、頻 ファイルごとに頻度ファイルを用意し、ファイルか変更 それをもとに WAM を生成していました。これに対し、 対して形態素角斤処理を実行して頻度ファイルを生成し、 12 月号て紹介した去では、毎回あらゆるファイルに におこなうことができます。 WAM に変換する処理は、形態素解析に上交すれは高速 するとかなりの時間が必要です。一方、頻度ファイルを 理には時間がかかるため、大量のファイルを処理しようと 178 end root = ARGV [ 0 ] exit unless root fg = FreqfiIeGenerator. new (root) fg ・ generate( ' IR' ) fg ・ generate( 'DOC' ) ( 誌面の都合 E, 斤り返しています。以訃 1 司椥 度ファイル用のディスクがよぶんに必要にはなりますが、 インデックス作成にかかる時間を時鬲に矢宿できます。 検索対象ファイルごとに頻度ファイルを作成するための Ruby スクリプト makefreqfiles を図 2 に示します。 ホーム・ディレクトリが /user/masui のとき、 % makefreqfiles /user/masui/IR のように検索ディレクトリを指定して makefreqfiles を 起動づーると、 /user/masui/Mail/inbox/1000 のような UNIX MAGAZINE 2003.3

- DA ドルサ、バ設計と実第 表 1 vnode 操作 vnode 乍 説明 アクセス許可のチェック VOP-ACCESS プロック数のマップ VOP-BMAP プロックの言ムみ VO P -B READ プロックバッフアの解放 VOP-BRELSE ファイルを閉したことをマーク VOP-CLOSE ファイルの作成 VO P -CREATE VOP-FSYNC ダーテイプロックのフラッシュ ファイル属を返す VOP-GETATTR vnode をインアクテイプとマー VOP-INACTIVE ク 入出力制餌牒作の実行 VOP-IOCTL ファイルにリンク VOP-LINK ファイル名の検索 VOP-LOOKUP ディレクトリの作成 VOP-MKDIR ファイルをオープンしたことをマ VOP-OPEN ファイルの言翹 ( り / 書込み VOP -RDWR ファイルの削除 VOP -REMOVE シンポリック・リンクの言翹えり VOP-READLINK ファイルの名前変更 VOP-RENAME ディレクトリ・エントリの言翹 ( り VOP-READDIR ディレクトリの削除 VOP-RMDIR ファイノレシステム・プロックの言冗 VOP-STRATEGY 取り / 書込み シンポリック・リンクの作成 VOP-SYMLINK VOP-SELECT select ファイル属の設定 VOP-SETATTR イ瓦想メモリ内のページの言翹りと VOP-GETPAGES マップ マップされたページのディスクへ VOP-PUTPAGES の書込み Sandberg らによる [ 20 ] 。 イス ( 後を内部で使用する。これは引数の 1 っとして、 リクエストの状態を参照できる非い期入出力制徊ワ・ロック (kaiocb) をとる。 aread(struct vnode *VP , struct kaiocb *Cb) cb からプロック入出力リクエストを得る ; bp = getblk(vp, プロック・リクエスト ) ; if ( パッフア・キャッシュ内に bp がみつからない ) { EVFILT_KAIO を使って kevent を登録 ; bp をもつ kaio-biodone ハンドラを登録 ; VOP_STRATEGY ()p , (p) ; 表 2 ′くッフア・キャッシュへの vnode インターフェイス vnode 操作 説明 入出力に必要なすべてのバッフアを VOP-BREAD ロック。 vp からの言もムみ 入出力に必要なすべてのバッフアを VO P -A READ ロック。 vp からの言ムみ。プロッ クしない ダーティエントリをマーク。 vp へ VOP-BDWRITE の遅延書込み。リクエストがあれば 状態を史新 vp へのプロック書込み。リクエス VO P -BWRITE トがあれは態を更新 ダーティエントリをマーク。 vp へ VOP-BAWRITE の非同期書込み。リクエストがあれ は状態を更新 バッフアを解放。リクエストがあれ は状態を更新 ための kaio-biodone() か呼び出される。 kaio—biodone (struct buf *bp) bp から kaiocb を取得 ; kaiocb の klist 内の knote にイベントを配信 バッフアを解放し、必要に応してファイルシステムの 状態を更新するために VOP-BRELSE か使われる。ロー カルのファイルシステムは、 DAFS サーバーの効率的な 実行のために表 2 のインターフェイスを実装する。このイ ンターフェイスや他の適当なインターフェイスがない場合 でも、ローカルのファイルシステムは既存のインターフェ イスを使って DAFS サーバーを構成することができる。 しかし、マルチスレッド処理などのためにオーバーヘッド が大きくなってしまう。 ネットワーク・イベント配信は、前述のように kevent 冫欟冓を通してディスク入出力のものと統合することができ る。 RDMA ⅱ当子が発行されるたびに、 kevent が EV- FILT-RDMA フィルタを使って登録さオ t 、コンプリー ション・グループ (CG) 構造体に言当求される。コンプリー ション・グルーフのハンドラは kqueue のイベント配信 を扱う必要がある。 send—event ()G *cq, Transport *vi) CG の klist 内の knote にイベントを配信 ; VOP-BRELSE aread() か発行したリクエストか完了した点では、デ ータはロックされた状態で bp に存し、イベント配信の DAFS サーバーは、 kqueue の定期的なポーリングに 169 UNIX MAGAZINE 2003.3

0 図 9 期間を表すキーワード 1 R48T10 2 R48T9 4 R48T8 2 R48T7 R48T6 R24T18 2 R24T17 2 R2T199 1 R2T198 1 RIT403 2 RIT402 4 RIT401 2 RIT400 1 RIT399 1 1 表 1 時期諚するための引数 引数 —lm ー 2 ー 3m ー 3 ー 4y 1 カ月前 2 ~ 3 カ月前 3 ~ 4 年前 図 10 期間オ諚か可能なプログラム tsearch # ! /usr/bin/env ruby # ー * ー mode : ruby ー * ー irdir = Fi1e . dirname($O) $ : くく irdir requlre ' timerange . rb ) SEARCH = "#{irdir}/search" "#{irdir}/search2htm1" SEARCH2HTML W3M = " 3m —T text/html" p = IO. popen( "#{SEARCH} ー #{SEARCH2HTML} if ARGV [ 0 ] ARGV . shift time—keyword = TimeRange ・ rangearg ( $ 1 ) p. puts time—keyword if time—keyword end if ARGV. length > 0 then ARGV. each { ー argl p ・ put s arg else p. puts STDIN. readlines end p ・ close ら 2 ~ 3 カ月前にもっとも近いものを使用します。この計 2 カ月の期間を表現する期間キーワードのうち現在日リか 182 図 11 tsearch —2m wiki による結果 Eile 印 Cm 引当新鰍出い リ T 引物 Term - tne 新℃ s 医朝 vco. 、、叮 ・ [ , ] メーリングリスんもう , ・ 0 引・ , " y ・ . ル / / な , ui iki / pr 等 0 ・ - / " " ・に叩 , に引 ? ぬ c os トの場合以下のよう感じです。記 / b た引 : ・ h い p : / コマンドラインから呼び出す、ⅸドというコマンドを作ってました。私の To: ⅵ ki 物 iki. ー引 . 0 ・ ron : Toshiyüi ー & カ . i# を : [wiki:61) Tiki を 【 2002 / 12 / 02 13 : 05 】 / し rs / ” sui / i Ⅵ「 x / 2 引 23 [wiki:S1] 2002 までに投がないと消減します。 -- 札 : wikihiki. 8i0嬉に0g リングリストもうじき消減このメーリンゲリストはを 03 00 : 48 : 03 JST To: 響 iki iki ・ q•ic に侊・「 on : wiki&wiki.quicknl. comSubjEt.• [wiki] メー *iki メーリングリス人 / i/ Ⅱ月。 = / 20850 増芍の響 iki のを ~ ) ページが表示されます。 WikiHeIp 「響 iki 」についてユニマガに書さました。 % wiki 印を起する To: 23u ト la 」 ic 匚 c ( 「 om : T«hiyuki 淞純 i & 上 jec を : [ 23i - b : 博 82 ] 【 2002 / 11 / 27 13 : 02 】 / リ門 / ぬ i レ i 「 x / 24590 [ リ i - b : 1382 ] WikiHelp 響 iki の“ e ) ページが表示されます。 WikiHelpJ についてユニマガに書きました。 % wiki “を起助すると増井の To: ト叩 ic に & 」 b. iec { : WikiHelpFræ: Toshiyt.ki 淞 sui 「 【 2002 / い / 27 13 : 02 】 / 騰 e / nas リ i / 淞Ⅱ / 改 up / 2319 Wi い厄 2002 までに投穡がないと減します。 -- : 響 iki 聞 . quic し com リングリストもうじき消減このメーリングリストは n 03 川 : 57 : ⅱ JST To: ⅵ ki iki. qui 改 .0 ( 「 : 響 iki ik に i 改 .08S jec を : [wiki) メー 算は、 rangearg メソッドでおこないます。 2002 / に / 02 13 : 0 / し「 s / ” i/ 淞Ⅱ / 改 / 2368 title:$l" このコマンドに、、 2 カ月前 " を未する一 2m オフション す。 能な検索コマンド tsearch ( 図 10 ) を使うことができま search2htmI と期間キーワードを用いて、期間指定可 期間の指定 か重点的に検索されます。 ば、 2003 年 3 月 1 日から数えて 2 ~ 3 カ月前のファイル ワードにこの期間キーワードを加えて全文検索をおこなえ して、、 R2T194 " か得られます。そこで、通常のオキー 用いて、、 2 ~ 3 カ月前 " を指定すると、期間キーワードと たとえは、 2003 年 3 月 1 日の時点で引数ー 2 ー 3m を おわりに なる結果等られます ( 図 11 ) 。 のようにして図 5 と同し検索を実行すると、図 7 とは異 tsearch —2m wiki を付け、 UNIX MAGAZINE 2003.3 理手法を充実させるはうか容易で効果的だからかもしれま やメールに対しては、検索システムを活用するよりも、整 している人はあまり多くなさそうです。自分のファイル す。しかし、計算機での通常の作業で全文検索を活用 うに使っていますし、その重要性はひろく認められていま Google などの全文検索システムは多くの人が毎日のよ