んどの人にとっては無意味であるが、トラブルシューティ ングを行わなければならないような状況の人にとっては、 スレッド 少々頭を悩ませる点だ のアプリケーションを利用したいがために Linux でも同様 ド実装を生かす強力なアプリケーションが出現すれば、そ はこれでも十分機能している。もし So ぬ ris のようなスレッ 単純な実装であるが、現在のアプリケーションの範囲で されたが、単純な pthread ライブラリが採用された ) 。 には、いくつもの Linux 用スレッドライプラリの実装がな スレッドはすべてカーネルスレッドとして動作する ( 実際 pthread ライブラリは非常に単純なっくりとなっており、 せた pthread ライブラリが標準的に利用されている。この システムコールに POSIX スレッドのインターフェイスを被 イプラリを提供している OS もある。 Linux では上記 clone ッドとユーザースレッドを絶妙に組み合わせたスレッドラ を置くように実装しているものが多い。またカーネルスレ 伝統的な UN Ⅸでは、プロセス管理の中にスレッド管理 じ動作をさせることもできる。 ションの指定方法により fork システムコールとまったく同 共有する資源をオプションで指定することができる。オプ clone システムコールにより生成できる。その場合親子で 形態として実装している。 Linux ではカーネルスレッドを Linux カーネルでは、カーネルスレッドをプロセスの一 2. 割り込みスタックが無い 1 . 割り込みレベルが無い Linux の割り込み機構は非常に単純である。大きな特徴は 割り込み処理 の実装がなされると筆者は考えている。 088 BSD magazine 2002 NO. 1 1 ってもタイマ割り込みを許可することにより、割り込み応 度を与えることにより、ディスク I/O 割り込み処理中であ タイマ割り込みにはディスク I/O の割り込みより高い優先 ということである。伝統的な UN Ⅸでは、応答性の必要な ように特定の割り込みを優先して処理することができない 割り込みレベルが無いということは、伝統的な UN Ⅸの の三点である。 ウェア割り込みのニ段階で処理する 3. 割り込み処理はすべて、ハードウェア割り込みとソフト 答性を確保している。 Linux カーネルでは割り込みレベルを設けない代わりに 積極的にソフトウェア割り込み機構を利用することにより 応答性を確保している。ハードウェア割り込みハンドラ自 体を極力短時間で完了させ、割り込み処理の大部分をソ フトウェア割り込み機構に任せてしまう ( ここでは詳細は 述べないが、 softirq 、 tasklet 、 BH ハンドラ、 taskqueue といった仕組みを提供している ) 。 ただし、ハードウェア割り込み処理が短時間で完了して いるとはいえ、ハードウェア割り込みは割り込み要因の数 だけネストする可能性がある。 lntelCPU 用 Linux カーネル では割り込みスタックは用意せす、割り込み処理はすべて カレントプロセスのカーネルスタック上で実行する実装に なっている。多くの種類のデバイスを接続する環境ではカ ーネルスタックサイズに注意する必要が出てきそうだ。 ( システムコール等 ) カーネルスタック スタック ソフトウェア割り込み 割り込み A スタック 割り込み B スタック ( p 「 oc 構造体に相当 ) struct task struct システムコール 実装方式 lntel CPU 用 Linux カーネルでは、 システムコールは int 命 令を利用して実現している。 int 命令はユーザーモードでの プロセス実行を中断し、 CPU をカーネルモードに切り替え Linux カーネルのシステムコールの先頭に飛び込む。実行 するシステムコールの種類や引数は、レジスタやスタック を利用して Linux カーネルに引き渡す。 旧回 CPU のアーキテクチャ的には一見 c 訓 gate を利用し

のソースは、多数のディレクトリに埋没してしまってわか 入っている。 りにくいかと思うのでいっておくと、 kcontrol/ というディ レクトリにある。コントロールセンターモジュールを書き kparts たい人にとってはふんだんなサンプルといえる。構造が比 API リファレンスの「 kparts 」カテゴリに対応するソース 較的単純なフォント設定ツールの f 。 nts / あたりを参考にす が入っている。上述のコンポーネントのところで解説した るのが取っかかりとしてはよいだろう。 KParts の実装、それにフル機能の HTML プラウザの KParts コンポーネントのソースなどが置かれている。 kdesktop 「デスクトップ」そのものを管理するツール。背景画像 の描画、アイコンの描画、コンテキストメニューの表示、 ラバーバンドの描画、ファイルのドラッグ & ドロップの受 け付けなどの処理をする。 kspell API リファレンスの「 kspell 」カテゴリに対応するソ ース が入っている。 kssl SSL を KDE から簡単に使うためのライプラリクラス群。 kstyl es KDE のスタイルは、せんじ詰めればウイジェットの独自 描画機能を持つプラグインといってよい。つまりスタイル を実装するにはこのようなプラグインを実装すればよいこ とになる。このディレクトリには KDE2.2.2 で用意されてい るスタイルの実装が置かれている。 kd m 機能ごとにきれ ディスプレイマネージャ xdm の KDE 版。 ソースを追いか いにディレクトリに分けられているので、 けやすい。 khelpcenter ヘルププラウザ。高機能なアプリケーションなのでさぞ かし巨大なことだろうと思って行数を数えてみると、せい せい 3000 行強程度だった。 KHTMLPart という HTML ウイ ジェットを利用しているためこの行数で書けたのだろう。 KDE の強力なフレームワーク機能を証明するアプリケーシ ョンであるといってよい。 libkmid API リファレンスの「 kmid 」カテゴリに対応するソース が入っている。 aRts は非常に野心的で優れたマルチメディ ア API だが、現時点ではまだ MIDI を扱うことはできない。 そのため、 MIDI を扱うライプラリが別に用意されている。 kicker パネル。外見が地味なわりに高度に複雑なことをやって いるアプリケーションで、ソースコードの行数も 2 万行を libkscreensaver 超える。 コントロールセンターでスクリーンセーバのセクション を選択すると、ウインドウ内でスクリーンセーバのプレビ ューができるようになっているが、スクリーンセーバを内 kioslave 上述した IOSIave の実装が入っている。 HTTP 、 FTP 、 部で実行できるウイジェットのソースコードである。 GZIP 、 BZIP2 プロトコルは kdelibs/kio/ ディレクトリにソー スコードがあるので間違えないように。ここにはこれら主 kdebase 要なプロトコル以外の IOSlave のソースが置かれている。 kdebase パッケージには基本的なツールのソースコードが こでは主要なツールに関してだけ解説を 置かれている。 加える。 konqueror Konqueroro Web プラウザ、ファイルマネージャ、 FTP ク ライアントと機能が非常に豊富だが、このディレクトリで kcontrol KDE コントロールセンターと、多数のコントロールセン 実装されている機能はほとんどがファイルマネージャ系の 機能と設定系の機能である。 HTML プラウザとしての機能 ターモジュールのソース。コントロールセンターそのもの gazin

な UN Ⅸの実装方法とは異なり、 / dev / raw という特殊なテ バイスを目的のプロックテパイス (/dev/sda2 など ) にア タッチすることによりプロックデバイスに対して raw アク セスを行うことができる。 カーネルメモリアロケータ Linux はカーネルメモリアロケータとしては、 buddy シス テムによるべージアロケータ上に、任意長のメモリアロケ ータであるスラプアロケータを実装している。 スラプアロケータは元々 So は ris 用に設計さていれたもの を、 Linux 用に実装し直したものである。メモリ領域をキ ャッシュすることによる初期化処理の簡略化や、メモリ領 域のキャッシュラインをずらすことによる性能向上などを 図っている。 ただし、カーネルメモリアロケータは、ページサイズを 越える大きな物理メモリ領域を扱うことは少々苦手であ る。 時計 Linux カーネルの時計の機能は、伝統的な UN Ⅸのそれ と同等である。近代的な商用 U N Ⅸの時計と同じく、 Linux の時計はニ段階で実行される。一段目の時計はハー ドウェア割り込みハンドラとして動作し、時刻の更新を行 一段目の時計はソフトウェア割り込みハンドラとして ページアロケータ (buddy システム ) 動的仮想空間制御 カーネル内各種機能 スラプアロケータ 動作し、各種時限処理を行う。また、マルチプロセッサ構 成時には、各 CPU 上で動作中のカレントプロセスに対す る処理を行うため、更にそれぞれの CPU 上で第三の時計 を動かす。 Linux の時限処理は、初期の伝統的な UN Ⅸで実装され ていた callout テーブルと目的は同じにするが、 Linux カー ネルらしくないスケーラブルでかっ最小のオーバーヘッド で実行できる凝った構造になっている。 ネットワーク 世の中に存在するほとんどの TCP/IP スタックは、元祖 BSD UN Ⅸの TCP / 旧スタックを基に開発されたものであ る。組み込みシステムや Windows の TCP / 旧スタックなど にも広く採用されている。 RFC ではなく、 BSD UN Ⅸの実 装が TCP/IP の仕様であるといっても、あながち外れてい ないだろう。 しかし、 Linux カーネルは BSD のスタックを流用せず、 独自の実装を行っている。 Linux カーネルの TC 円旧スタッ クは商用 UN Ⅸのような STREAM 機構は採用せず、シンプ ルな構造を採用している。 Linux は skbuff と呼はれるネッ トワーク用パッフアの管理機構を用いネットワーク層にお けるテータのセロコピー化を実現している。 Linux カーネルのネットワーク機能における最大の課題 は旧 v6 であろう。旧 v4 は完成度も高いが、旧 v6 の実装の ほうは遅々として進んでいない。必要性に迫られると一気 グローバル時計 グローバル時計 ( ハードウェア割り込み ) 時刻 、 . CPUO . ・ CPU ローカル時計 ( BH ハンドラ ) 時限処理 タイマリスト CPUI . ・ グロー / 朝レ ローカル タイマ割り込みタイマ割り込み CPU ローカル時計 ローカ丿レ タイマ割り込み 8 ー ハードウェア タ階 9 の 092 BSD magazine 2002 NO. 1 1

BSD ハッカーへの Linux カーネル紹介 ポインタで参照し管理することが可能である。この方針に より、 Linux カーネル内での各種資源管理が単純化されて いる ファイルシステム ext2 Linux も近代的な UNIX と同様 VFS ( 仮想ファイルシス テム ) 構造を採用している。非常に多くの種類のファイル システムをサポートしており、各種 OS のファイルシステ ムをマウントして利用することができる その多くのファイルシステムの中で、 ext2 が標準ファイ ルシステムとして採用されている。 ext2 は FFS UFS) を 参考として設計されており、構造は非常に良く似ている ティスクレイアウト的なところの違いは、フラクメント機構 を取り込む代わりに、フ、ロックのプリアロケート機能を実 装しているくらいであろうか。それ以外はそっくりである。 ただし、実装面においては大きく異なる点がある。 ext2 は非同期 I/O をテフォルト動作としており、非同期 I/O のと きに最も性能か出るような実装をしている。驚くほとの割 り切りの良さである。実際 Linux の vfs か bread 関数は用意 しているが、 bwrite 関数を用意していないところからも、 Linux か非同期 I/O 中心に設計されていることか見て取れる レ 0 をすべて非同期にすることにより、最も効率のよい I/O 順を選択できるのは当然のこととして、 Linux は更に非 同期 I/O を効率的に動かすための仕組みを用意している 伝統的な UNIX では、レ 0 中のバッファベーシに対してアク VFS キャッシュ iS09660 ディレクトリ 工ントリキャッシュ ext2 ペーシキャッシュ nfs RPC / ヾッフアキャッシュ TCP/IP 7 ファ ) システ セスすることは許されていないが、 Linux はティスクへの書 き出し処理を行っているべーシに対してテータを書き込む ことも可能である ( その場合、同じペーシに対して再度書 き出しレ 0 が発行されることになる ) 。プロセスは I/O 処理 にフロックされることなく、処理を継続することが可能で ある。 もちろん現在の Linux では、堅牢性を重視したシャーナ リンクファイルシステムも多数実装か進んでいる キャッシュ Linux は、近代的な商用 IJ N Ⅸと同じく空き物理メモリ をすべてファイルシステムのキャッシュ用途として利用す る。カーネル v2.4 では一部のメタテータを除き、ファイル テータは基本的にすべてペーシキャッシュに蓄えるように なっている もともとファイルシステムのキャッシュは、初期の UNIX と同じくバッフアキャッシュと呼はれるフロックテパ イス ( ティスク ) のキャッシュとして実装されていた。し かし、 N FS のようなローカルティスクを持たないファイル システムの登場により、論理的なファイルのキャッシュと して働くべーシキャッシュを利用するように実装が変更さ れてきた ( v2.2 カーネルでは、ペーシキャッシュ化か不十 分で、ファイルからのテータ読み出しはペーシキャッシュ 経由、ファイルへの書き込みはバッフアキャッシュ経由と なっていたが、 v2.4 では完全にペーシキャッシュに統一さ れた ) 。 ファイルテータがペーシキャッシュに置かれることによ り、フロセスのファイルマッフ空間との間でペーシを共有 することも可能となった また、 BSD から始まったティレクトリエントリ専用のキ ャッシュも実装されている。 Linux カーネルのティレクトリ 工ントリキャッシュでは、メモリ上のティレクトリエント リと i ノードか相互にリンクされており、パス検索処理を 高速化することに役立っている raw I/O もともと Linux には raw レ 0 の仕組みは存在しなかった 速度さえ気にしなけれは、フロックテパイス用のテパイス ファイル経由のアクセスで何も不自由はない。たか、テー タベース用途なとの要求か高まるにつれ、 Linux でもとう 2002 No. 1 1 BSD magazine 091

B 5 0 でルータを作ろう ! れた。 1999 年 2 月にリリースされた の参照モデルに沿った構成となってい 必要な通信を行うことが可能である。 ただし、キューイングは本来、短期 altq -2.0 では、すべての QoS コンポーネ る。カーネル内のバケットフォワーディ 的なトラフィック集中を制御する技術 ントを一括管理する altqd が実装され、 ングパスには、入力側に後述のトラフ diffserv のサポート、Ⅱ FSC[6 】の追加、 イックコンディショナ、出力側にはイ である。継続的な輻輳にはトランスポ NetBSD のサポートが加えられた。 12 ンターフェイス毎にキュー制御が置かれ ート技術、さらに慢性的な輻輳にはキ ャパシテイプランニングを組み合わせ 月の aItq-2.1 で OpenBSD もサポートさ る。これらは実際にバケットを操作する れた。 1999 年 8 月には ALTQ は KAME メカニズムである。そして、ユーザー空 た対策が必要となる。 の開発ツリーにマージされ、 2000 年 1 間のデーモンプロセスがカーネル内に実 月からは複数の BSD プラットフォーム 装された QoS 機構を制御する仕組みに への対応を効率化するため、 ALTQ 自 なっている。 ALTQ の開発が始まった 1997 年当時 体も KAME のツリーで開発されるよう このモデルでは、ルータは送出キュ ーのみを制御する。入力キューを制御 は、インターネットで高品質通信を実 になった。 2000 年 12 月には、デバイス ドライバへの依存性を減らすべくフレ しない理由は、割り込みコンテキスト 現するための QoS 技術がさかんに研究 で処理される入力キューには通常バケ されていたが、理論的な研究が多く利 ームワークが大幅に見直された altq -3.0 ットは溜らないので、キュー制御の効 用できる実装が存在しなかった。イン がリリースされた。同月には NetBSD 果がないためである。もし、入力キュ 本家の開発ツリーにマージされ、 2001 ターネットの技術開発には、実際に利 年 6 月に OpenBSD 本家の開発ツリーに ーにバケットが溜るとすれば、 CPU が 用できるプラットフォームが不可欠と 割り込みを処理しきれていないことを 考え、 P C で動作する A L T Q を マージされている。 意味するので、ソフトウェアでは改善 FreeBSD をベースに開発した。 1997 年 3 月に FreeBSD -2.2 上で動作 できない。 する aItq-O. 2 がリリースされた。 aItq-O. 2 は CBQ[2] と WFQ を実装し、資源予約 実装モデル システムモデルが機能の分割を示す プロトコル RSVP 問とも連動可能だっ トラフィック制御モデル のに対し、図 3 に示す実装モデルは、 た。 1998 年 4 月の altq -1.0 では IPv6 をサ 図 2 に ALTQ ルータのシステムモデ これらの機能が如何に既存の OS に組 ポートし、 RED 川と ECN 同が追加さ ルを示す。これは、 intserv や diffserv み込まれるかを示す。 ALTQ の実装は、 フレームワーク、 QoS コンポーネント、 マネージメントツールに分けられる。 フレームワーク部は既存の OS に QoS コンポーネントを組み込むための汎用 インターフェイスを提供する。キュー イング方式が抽象化されているので、 OS は異なるキューイングメカニズムを 意識することなく、プラックポックス として扱うことができ、 ENQUEUE 操 作あるいは DEQUEUE 操作によってア クセスする。 ALTQ が disable された状態では、従 来からの FIF O キューが使われる。 ALTQ をサポートするにはデバイスド ライバへの修正が必要になるが、 この A Q 開発の経緯 ALTQ の構成 QOS management mechanisms admission control traffic control database QoS manager user kernel packet scheduler classifier buffer traffic condi tioner forwarding output queueing input driver output driver QOS forwarding mechanisms 図 2 ALTQ システムモデル 039 2002 NO. 1 1 BSD magazine

ロル目を ようにバックワードコンパチビリティ を保つことによって、段階的にサポー トするドライバを増やすことができる。 QoS コンポーネントは、実際にトラ フィック制御を実現する種々のメカニ ズムである。 CBQ や RED などの具体的 なメカニズムがこれに当たる。 ALTQ は単にキューイング方式を組 み込むだけでなく、遅延低減に関する システム全体の実装上の工夫がされて いる。 1 つは、スケジューラの制御粒度 を上げるために、デバイス割り込みを カーネルタイマに併用してトリガに使 用している点である。また、ネットワ ークカードでバッフアされるバケット 数を制限するトークンバケットレギュ レータというメカニズムを備えて、バ ッファリングによる不要な遅延を低減 する。この辺りは、単に帯域制限だけ を行う他の実装では実現されていない。 マネージメントツールは、ユーザー 空間に実装され、 QoS コンポーネント を制御するデーモンと統計情報を表示 するツールがある。 application Q 。 S コンボーネント 現在 ALTQ が実装しているキューイ ング方式には、 CBQ (Class Based Queueing) 、 HFSC (HierarchicaI Fair Service Curve) 、 WFQ (Weighted Fair Queueing) 、 PRIQ (Priority Queueing) 、 FIFOQ (First- ln First-Out Queueing) がある。 CBQ は階層的にクラスを構成して、 帯域を分配するキューイング方式で、 もっとも広く使われている。 HFSC も 階層クラスによるモデルを採用してい るが、 CBQ より理論的で、研究向けと いえる。 PRIQ は単純な優先スケジュ ーリングを、 WFQ は簡単な重み付き ラウンドロビンスケジューリングを実 装している。 バッファ管理方式では、 R E D (Random Early Detection) と、これを diffserv 用に拡張したⅢ O (RED with ⅲ and Out) 、さらに BIue という方式が実 装されている。 トラフィックコンディショナは、 diffserv で導入された概念で、ネット ワークの入口でトラフィックを計測し user kernel socket TC P contro l. ip_forward traffic condi tioning ip—input device d river 図 3 ALTQ 実装モデル altq daemon control: ip—output if_output enqueue output queuelng dequeue ifqueue device driver て、 IP ヘッダ内の diffserv フィールド ( もとの TOS フィールド ) を書き換え る仕組みである。クラシファイア、ト バケットマーカ ラフィックメーター ーなどのコンポーネントを組み合わせ て構成する。 A Q の応用 に設定される。 ALTQ は送出トラフィ ーク側のインターフェイス fxp 1 の両方 ーフェイス fxp0 と、ローカルネットワ ALTQ はインターネット側のインタ 合したほうが構成は簡単になる。 ているが、できれば ALTQ ルータに統 アクセスルータが別にある場合を示し ィック制御するものである。こでは アクセス回線を ALTQ を使ってトラフ 図 4 に示す構成例では、 1.5Mbps の して、帯域を割り当てる。 トラフィックタイプ別にクラス分けを る。組織の部門別あるいは HTTP 等の ーネットとの接続回線の帯域管理であ ALTQ が良く使われるのは、インタ アクセス回線の帯域制御 上げる。 体的な運用ネットワークでの使用例を こでは ALTQ の応用例として、具 できないので、手前で可能な範囲の制 しかし、通常は ISP 側のルータは操作 本来は ISP 側で制御する必要がある。 フアが溢れバケットが捨てられるので、 は回線の入口の ISP 側のルータのバッ 回線がボトルネックなので、輻輳時に できない。ここでは基本的にアクセス ィックに関しては、部分的な制御しか しかし、この構成では内向きトラフ 御されることになる。 で、内向きのトラフィックはⅸ pl で制 へ出ていく外向きトラフィックは fxp0 ックを制御するので、インターネット 040 BSD magazine 2002 NO. 1 1

kqueue のすすめ イメージソース花井浩之 hanai@imgsrc. CO. JP 川衂川 1 刻膩に山 IJ Ⅶ EJ IIII(IIIIIL(II 大先生たちによるシステムコールプ OS であればたとえ動かないにしてもす もないのだ。イベントを拾いアプリケ ログラミングの入門を読み、早速何か ぐに動くようにできるのではないかと ーションに通知する部分が遅いと、ア 作ってやるぞ ! と鼻息を荒らくして 思う。 kqueue が実装されていない場合 プリケーションそのものの反応が遅く いる若者のみなさん。また、普通のフ は・・・・・・えーと、実装を手伝うか祈るか なってしまうのは明らかである。実際 ァイルにも select や p 。Ⅱが使えたりした してもらいたい。また、 BSD 系にしか 後で述べるように UNIX で伝統的な らええなあなどと思っているみなさん。 実装されていない kqueue を使うってい select(2) や P0Ⅱ(2) といったシステムコー せつかくだからこの機会に kqueue を使 うのは移植性を悪くするじゃないか、 ルの利用方法にはいくっかの問題があ ってみてもらいたい。きっと嬉しいこ というご意見もおありかとは思うが、 る。また、これらのシステムコールを とがあるはすだ。この記事を読んで 1 人 そこはひとつ # ifdef でグッと堪えていた 利用する場合には拾うことのできるイ でも 2 人でもいいので、今度書くアプ だいて、それでもパフォーマンスを追 べントにも限りがある。アプリケーシ リケーションでは kqueue を使ってみよ 及していただければ、と思っている。 ョン側としては、非同期 I / O リクエスト うとか、あのアプリケーションは が完了したときや signal が発生したと kqueue 使ったほうがだいぶパフォーマ き、ファイルシステム中のファイルが ンスが良くなりそうやから改造してみ なんらかの変更を受けたとき、そして ようか、などと思う人が現われてくれ 世の中にあるアプリケーションソフ プロセスが終了したとき、といったよ れば幸いである。 トの多くはイベント駆動型と言われる うなイベントを拾うことができればい ただし、都合の悪いことはさきに ものだ。わざわざ説明する必要もない ろいろと便利なのだが、これまでの っておこう。 kqueue は最初 FreeBSD で が、バケットの到達やキーボード / マウ BSD ではそのようなことはできないか、 実装されたもので、筆者がここにサン スなどによるユーザーの入力といった、 できても非常に面倒であったり制限が プルとして挙げるプログラムは 発生する「イベント」に反応して動作 あったり無駄なことをやっていたり、 FreeBSD ( しかも -current) でしか動作 するタイプのソフトウェアということ といった問題があった。 確認をしていない。 OpenBSD にはすで だ。工デイタはユーザーの入力に従っ kqueue は、そういった問題を解決す に入っているようだし、 NetBSD にも入 て文字を表示したりカーソルを動かし るためのイベント通知システムであり りつつあるという話は聞いているのだ たり 1 行消したりといった動作をし、 x Jonathan Lemon 氏が中心となって開発 が、実際にどうなのか実はよく知らな クライアントはユーザーのマウス操作 したものである。 FreeB s D には 4.1 ー い (http://cvsweb.netbsd.org/を見る限 やキーボード操作によってそれぞれプ RELEASE から入っており、上にも書 り、 cvs ツリーに kqueue というタグは ログラムされた動き方をし、 SMTP や いたように OpenBSD にもすでに入って あるようだ ) 。日頃の行いが悪いのでい いるようであるし、 NetBSD にも入りつ HTTP のサーバーデーモンはネットワー ざ NetBSD や OpenBSD でどうなのか試 ク越しにやってきたバケットに反応し つあるようだ。 して ( 調べて ) みようと思っても手元 てリクエストを処理する、といった具 に何も ( っていうのは要するにハード 合だ。 OS にはそういったイベントを知 ウェアと時間だが ) なかったのである。 らせてくれるようなメカニズムが備わ とはいえ、プログラム自体は簡単なも っているのだが、そのメカニズムが最 kqueue の使い方を紹介する前にます のであるし、 kqueue が実装されている 適なものかといえばこれは実はそうで は select ( 2 ) ゆ。 ll ( 2 ) での問題点について 078 BSD magazine 2002 NO. 1 1 イントロ se 厄 ct ( 2 ) / po Ⅲ 2 ) での問題

この変動優先度にタイムスライスを組み合わせた仕組み そうだ。もちろん、大きな CPU 数の SM P システムになる と問題がでてくるのだが、そういうシステムでなければ、 は、飢餓状態のプロセスを作らないことにも一役買ってい る。高負荷状態における低優先度のプロセスでも、優先 この単純な構造でも十分ということを再認識した。 スケシューリングのポリシーも、少々気が利いている。 度に応じた与えられたタイムスライスを使い切ることか保 すべてのプロセスに公平に CPU 実行権を与えながら、応 正されている。この低優先度のプロセスがタイムスライス 答性を確保しつつスルーブットも犠牲にしないというの を使い切るまでは、いくら高い優先度のプロセスであって が、 UN Ⅸ系 OS のスケジューリングの命題である。 も再度タイムスライスが与えられることはない。 Linux のプロセススケジューラは、すべての CPU に公平 Ready 状態のすべてのプロセスがタイムスライスを使い にチャンスを与えつつ、 I/O バウンドなプロセスを優先して 切ると、すべてのプロセス ( 待機状態のプロセスも含む ) 動かすために、伝統的な UN Ⅸと同じく固定優先度に加え に対して nice 値を元にしたタイムスライスを与える。もし、 変動優先度を導入している。固定優先度は nice 値という 待機状態であったことによりタイムスライスを使い切って 名前で知られている。変動優先度は時間と共に変化する いないプロセスに対しては、その残りタイムスライス量も 優先度であり CPU 上で実行されているプロセスの変動優 考慮したタイムスライスを与える。タイムスライスは変動 先度はどんどん下がっていき、それ以外のプロセスの優先 優先度としても扱われるため、 I/O バウンドなプロセスや 度はどんどん高くなっていく。 シェルなどのプロセスには相対的に高い優先度が割り当て ここで Linux カーネルは、変動優先度の変化によって生 られることになり、応答性の向上に一役買う。伝統的な じる優先度逆転に起因して頻繁に発生する再スケジューリ UN Ⅸとは実装が異なるがポリシーは同じである。 ングのオーバーヘッドを抑制するために、変動優先度にタ もちろん、 Linux カーネルは次の 2.5 の課題として、スケ ーラヒリティ向上があげられており、プロセススケジュー イムスライスという概念を組み合わせている。スケジュー ラが動作すると、固定優先度 (nice 値 ) と変動優先度 ラもその対象の 1 つである。商用 UN Ⅸのような凝った実 ( タイムスライス ) をあわせた優先度が最も大きなプロセ 装のスケシューラもいくつか提案されている。 スに C PU 実行権を与えるが、一度実行権を与えた後は、 基本的にそのタイムスライスを使い切るまでは再スケジュ アイドル状態 実行可能なプロセスが存在しないときの扱いはどのよう ーリングを行わない。 唯一、 ( I/O 完了待ちなどで ) 待機中のプロセスが起床 に実装されているだろうか ? 実装方式としてはアイドル した場合にのみ再スケジューリングを行う ( 待ち状態のプ 状態を実行するアイドルプロセスに実行権を移す方式と、 ロセスが起床したとき、カレントプロセスより優先度 ( 固 スケジューラ自体がアイドル状態に落ちる方式の 2 つが考 定優先度と変動優先度を合わせたもの ) が高ければ、即 えられる。後者の実装方式のほうがアイドル状態から抜け プリエンプトする ) 。伝統的な U N Ⅸと同様の方法で応答 出すときのオーバーヘッドが僅かに小さくなるが、 Linux 性を確保している。 カーネルでは実装の対称性が良くなる前者の方式を採用し ている。 アイドルプロセスは、システム起動時に生成され、シス テム終了時まで nop 命令を実行し続ける。 プロセス カレントプロセス Linux カーネルのコードを読み始めたとき、カレントプ ロセスへのポインタ current の妙にトリッキーな実装方法に 唸ってしまった。各 CPU 毎に current ポインタを持つ必要 があるため、単純な変数では扱えない。このため何らかの 特殊な仕組みが必要なのであるが、旧回 CPU 用 Linux カー 一三ロ 固定優先度 : N ℃ E 値 ( タイムスライス ) → 残り時間→ ( 変動優先度 ) 時分割プロセス 図 2 プロセスの選択基準 086 BSD magazine 2002 NO. 1 1

U 構造体 コードの読みやすさという点からみたとき、伝統的な UN Ⅸと Linux とでは他にもいくつか異なる点がある。 初めて UN Ⅸのコードを読んだとき、 U 構造体の存在によ りコードの流れを読むときに気を使わなければならなかっ た記憶がある。 Linux カーネルにはこの U 構造体が存在し ない。伝統的な U N Ⅸでは、プロセス管理用のデータを proc 構造体と U 構造体の 2 つに分けて管理している。 IJ 構 造体にはそのプロセスのみが利用し、他のプロセスコンテ キストや割り込みコンテキストからは参照しないデータを 格納する。しかし、 U 構造体はそのプロセスにとってのグ ローバル変数であり、あるカーネル関数を呼び出すときに は、 U 構造体の値がどうなっているかの仮定があるため、 UN Ⅸを読み始めた当初は戸惑ったものである。 Linux カー ネルは、 U 構造体を採用せず、すべて task_struct 構造体 ( pr 。 c 構造体に相当 ) に情報を格納し、また引数に相当す るテータを U 構造体経由で渡すような見通しの悪いことは せず、泥臭い実装だが、すべて関数引数で引き渡すように なっている。 setjmp と longjmp また、 Linux カーネル内には setjmp/longjmp が無い点も、 伝統的な UN Ⅸの実装とは異なる。 setjmp/longjmp の機構 により、システムコールのカーネル内でのエラー発生時に カーネルの奥底から途中の処理をすべて飛ばして一気にシ プロセス BSD ハッカーへの Linux カーネル紹介 ーフ ーフ ステムコールの出口まで戻ることにより、エラー時の手続 きを簡略化することができる。便利ではあるが、それなり の制約も生まれる機構である。 Li n ux カーネルでは setjmp/longjmp を実装しておらす、カーネルの奥底のほう の関数でエラーが発生すると、ネストした関数群は地道に 工ラーリターンを繰り返してカーネルの出口にたどりつく。 Linux で setjmp/longjmp を実装しなかったのは、必要性を 感じなかったのか、単純さを優先するポリシーに乗っ取っ てのことなのかは、私は知らない。 プロセススケジューリンク スケジューリングボリシー 基本は伝統的な UN Ⅸと同じである。 Linux のプロセスス ケジューラは、走行可能状態プロセス (Ready 状態 ) の うちもっとも優先度の高いプロセスに、実際に CPU の実 行権を与える。 Linux カーネルは走行可能状態のプロセス を単純な一本のキューに並べて管理している。 最新の商用 UN Ⅸでは、スケーラビリティを上げるため、 優先度ごとにキューを用意したり、 CPU 毎のキューを持 たせたりしている。しかし、実際のところ、ある一瞬をみ ると Ready 状態のプロセスは数個程度であり、 Linux の単 純な一本のキューでも十分に問題なく機能する。 CPU 数 を遥かに超えるプロセスが同時に Ready 状態になっている システムは、そのシステムの設計が間違っているともいえ RUN キュー CPUO current プロセススケジュ プロセッサ間通信 1 ロセススケジュー CPUI current プロセススケシュ 2002 No. 1 1 BSD magazine 085

せで十分という理由もある。 まず、 CBQ に関して説明しておくこ とにしよう。 CBQ とは CIass Based Queueing つ まり、クラスに基づいたキュー制御方 式のことである。 CBQ を用いると、階 層的に構築されたクラスを利用してあ る回線の帯域を分割したり共有したり することができる。この階層的に構築 されたクラスそれぞれがキューを持ち、 クラス毎に帯域を割り当てられたよう な構造になっているのである。 なお、あるクラスの子として定義され たクラスは、自身の親クラスの余ってい る帯域から自身の帯域を借り受け、そ れを子自身の帯域として利用すること ができるようになる。 次に RED である。 RED は、 Random Early Detection の略であり、平均的なキュー長に基づ いてバケットを捨てたりバケットに統 計的マークを付ける暗黙の輻輳通知機 構として動作する。 RED は単独のバッ ファ管理機構として見ることもできる し、他のバケットスケジュール機構に 統合されたものとして利用することも 可能である。 最後に、 ALTQ を利用しない場合の 標準のキューイング機構である FIFOQ に関しても説明しておく。 FIFOQ とは、 First-In First-Out Queueing の略である。これは、最初 に入力されたデータから順次出力され るキューである。キューのバッフアが 埋まってしまった場合、最後にキュー に入れられるべきデータが捨てられて しまう。 ALTQ にもこの FIFOQ が実装 されているが、 CBQ drop class 分け drop 入力 C lass 分け drop FIFOQ 入力ー drop class A fq3 fq2 fql ca2 cal class Cc ca2 cal class Cb ca2 cal class Ca class C b2 bl class B a3 a2 al これは ALTQ に実装さ lnterface キュー制御機構 lnterface れているキューイング機構の中では最 も単純なキューイング機構である。 CBQ と FIFOQ のイメージを図 2 に挙 げておく 今回は、 CBQ によってバケットのク ラス分けを行いそれぞれに帯域を割り 当てている。加えて、 ICMP に対して は、割り当て帯域をこえないようにす るためにバケットを捨てる機構の制御 に RED を利用した。 ALTQ を利用するためには、 kernel の設定だけではダメである。これは、 ポリシーを記載する必要があるからで、 ポリシーは人間が決めるものである以 上自動で処理できるものではない。ポ リシーの制御は現在 altqd のみで行うこ とができるが、 diffserv 関連の実装を 行っているグループでは、別の制御用 プログラムを実装しているという話も ある。 さて、今回のポリシーとしては ・ The lnternet と Router1 、およびその内 側への ICMP バケットを 64kbps に絞る ・ The lnternet と server 1 の間の http での 通信を回線帯域の 50 % に絞る ・ The lnternet と Server2 の間の通信は 特に制限しない ・ hostl は常時接続状態にあり、「管理 用」としてのみ運用する ・ The lnternet と hostl の ssh による通信 に 64kbps の帯域を確保する ・自宅の hostl から運用ネットワークへ の通信は 32kbps の帯域を確保する (ssh のみ ) 以上の 6 点を採用する。 今回はキュー制御に altqd を利用す るので、 altqd 用の設定ファイルを記載 する必要がある。 a は q. conf の作成 もう一度ポリシーを確認して表現をし 044 図 2 CBQ と日 FOQ のイメージ BSD magazine 2002 NO. 1 1