読者です 読者をやめる 読者になる 読者になる

tom__bo’s Blog

情報系学生が筋トレしたり、筋トレしたり筋トレしたことを書くブログ。もはやダイアリー

Systems Performance 読んでいく (3章 その1)

Book Linux Performance SystemsPerformance

Systems Performance: Enterprise and Cloudを読んでいく。

前回に引き続き自分用メモ 3章は長かったので、2分割。前半は2節まで。

3 Operating Systems

OSとその内部のカーネルへの理解はシステムパフォーマンスに必要不可欠である。 この章ではこの本全体にわたって扱われるOSとカーネルの概要について触れる。 自分自身の知識と照らしあわせて読みすすめるとよい。
この章は2つのパートからなっている。

  • Background: 基本的な用語とOSの基礎知識
  • Kernels: LinuxSolarisベースのカーネルについてまとめ

パフォーマンスに関する、CPUスケジューリング、メモリ、ディスク、ファイルシステム、ネットワーキングがこの章の後に続く。

3.1 Terminology

以下がこの本で扱われるOSに関する用語である。

  • Operating system:
    • システムにインストールされているソフトウェアとファイル
    • カーネル・管理ツール・システムライブラリなどを含む
  • Kernel:
    • バイス(ハードウェア)・メモリ・CPUスケジューリングなどを管理するためのプログラムを含むコア部分
    • これは"kernel mode"と呼ばれる特権モードでCPU上で実行される
  • Processe;
    • プログラムを実行するための環境、OSの抽象概念
    • プログラムは通常"user mode"で実行され、カーネルモードではシステムコールかtrapsを使ってアクセスする
  • Threads
    • CPUで実行するための環境
    • カーネルは複数のスレッドを持ち、プロセスは1つ以上のスレッドを持つ
  • Task:
    • プロセスやスレッドによって実行される実態
  • Kernel-space:
  • User-space:
  • User-land:
    • ユーザレベルのプログラム、ライブラリ空間( /usr/bin, /usr/lib,,,)
  • Context switch:
  • System call(syscall):
    • ユーザプログラムが、ハードウェア等へ特権モードで操作を行うためのよく定義されたプロトコル
  • Processor:
    • 1つ以上のCPUを含んだ物理的なチップ
  • Trap:
    • system routine(privileged action)をリクエストするためのカーネルへのシグナル
    • Trap typeはシステムコールやプロセッサの例外、割り込みなどがある
  • Interrupt:
    • 物理的なデバイスからカーネルに送られるシグナル
    • 大抵はI/Oのリクエストを発生させるもの
    • ある割り込みはtrapの一種

3.2 Background

この節ではOSの概念とカーネルの中身を紹介する。
カーネルの種類の違いはこの後のセクションで述べられる

3.2.1 Kernel

CPUスケジューリング、メモリ、ファイルシステム、ネットワーク・プロトコルは全てカーネルによって管理されている。 これらのハードウェアやカーネルへのアクセスはシステムコールによって提供されている。
これを図3.1に示す

図3.1 f:id:tom__bo:20161214155324p:plain

個々にはシステムライブラリが描かれているが、これらはシステムコールを単体で叩くよりも簡単、もしくは高機能なインターフェースを提供するために存在している。 システムライブラリのリングが途切れて描かれているように、アプリケーションから直接システムコールを呼ぶこともできる。

[kernel execution]

カーネルは数専業に渡る膨大なプログラムである。これらはシステムコールや割り込みを受けてそれらを処理する役目があるが、とても軽量に動くように設計されている。

webサーバのような頻繁にI/Oアクセスを行う負荷はカーネルのコンテキストで実行される(?)。 強力な計算が必要なものはできるだけ割り込みが入らないように独立したCPUで実行される。 ならばカーネルの良し悪しはパフォーマンスに影響しないのでは、と思うかもしれない。 しかし、cpu同士で、強豪が発生していたり、どちらのCPUにタスクを割り当てるかによってCPUのローカルキャッシュをどれだけ使えるかに影響があるため、パフォーマンスへの影響はとても大きい。

[Clock]

Unixカーネルが起源のコアなコンポーネントはタイマーの割り込みによって実行される"clock()"ルーチンである。 これは歴史的に1秒間に60, 100, 1000会呼ばれそれぞれの実行は"tick"(ティック)と呼ばれる。

これには、以下のような役割がある。

  • システムの時間を更新する
  • スレッドスケジューリングのタイマーを閉めきったり、時間を区切る
  • CPUの統計情報を取得する
  • "callouts"(スケジュールされたカーネルルーチン)を呼び出す

これらにはすでに改良された以下のような問題があった。

  • Tick latency:
    • 100Hzのクロックでは次のtickを待つまで、10msに及びレイテンシがある
    • これはリアルタイム割り込みによって解決されている
  • Tick overhead:
  • 最近のプロセッサではアイドル中にCPUのパワーを落とす機構があるが、clockルーチンがこれを邪魔して、必要以上に消費電力を発生させていた。
  • Linuxでは"dynamic ticks"を実装することで、タイマールーチンが発生しないようになった。

最近のカーネルでは要求に応じた割り込みを発生させる用により高機能化している。 これらは"tickless kernel"によるもので、"sysetem timer interrupt"を呼ぶことで、効果的に"system clock"と"jiffies"カウンターを更新できる。
"jiffies"とはLinuxの単位時間で、"tick"と似たようなものである。

[Kernel Mode]

カーネルはCPU上の特別な"kernel mode"でのみ実行され、全てのハードディスクと特権命令を実行可能になっている。 ユーザプロセスがI/Oをしたりするためにシステムコールを発行するとカーネルモードへ移行して、高い特権レベルで実行するための"mode-switch"が発生する。
これが図3.2に示されている。

図3.2 f:id:tom__bo:20161214155337p:plain

それぞれのモードにはスタックとレジスタを含む、それぞれの実行状態がある。 ユーザモードから特権命令を実行すると、"excptions"が発生し、カーネルによって適切に処理される。 この切り替えにはCPUサイクルを消費するので、オーバヘッドを避けるためにNFSなどのシステムではカーネルモードで動作するように実装されているものもある。 もし実行中にいちいちシステムがブロックする命令を呼んでいたら、プロセスがコンテキストスイッチによって切り替えられてしまうだろう。

3.2.2 Stack

stackは関数やレジスタのための、スレッドの実行系統を含んでいる。 ネイティブのソフトでCPUが効果的に関数を実行するために使われる。 ある関数が呼ばれるとCPUは現在の実行状態を含むレジスタを現在のスタックの先頭に積み、新しい関数を実行する。 CPUの"return"命令によって実行を終了した関数はスタックから削除され、その以前の状態をスタックから読みだして処理を行う。

スタックを観察することはパフォーマンス分析にとても重要である。 スタックを見ることで現在実行している処理までの呼び出し順序がわかり、なぜ今の関数が実行されているのかが理解できる。

(TCP transmissionのスタックの例)?

この例はLinuxの内部のスタックなので、例外的にAPIや公式のドキュメントが存在するが、たいていの場合はスタックの表示結果はソースコード内部の関数を示すので、ドキュメントや説明はソースコードしかない場合が多い。

[User and Kernel Stacks]

システムコールを実行してる時にはプロセスはユーザレベルのスタックとカーネルレベルのスタックを持っている。
図3.3に概要を示す

図3.3 f:id:tom__bo:20161214155348p:plain

システムコールを実行している間はカーネルレベルのスタックを実行しているので、ユーザレベルのスタックを帰ることは出来ない。
これの例外としてシグナルハンドラがある。

3.2.3 Interrupts and Interrupt Threads

システムコールへの応答とは別にカーネルはデバイスからの要求にも答えている。 これは現在の実行に割り込む"interrupts"(割り込み)である。
これを図3.4に示す。

図3.4 f:id:tom__bo:20161214155357p:plain

"interrupt srevice routine"はデバイスの割り込みを処理するように登録されている。 これらはアクティブなスレッドをできるだけ邪魔せず、できるだけ早く実行されるように設計されている。

割り込みに関する実装はOSごとに異なっており、Linuxではデバイスドライバは半分に分類される。 上位の半分は早く割り込みを行い、下位の半分はあとから実行されるようになっており、上位の半分が実行されている際は下位の実行がこれを邪魔しないようになっている。 割り込みが発生してから実行されるまでの時間を"interrupt latency"と呼び、これはOSの実装によるが、リアルタイムシステムや'low-latency'システムの1つの課題となっている。

3.2.4 Interrupt Priority Level

interrupt priority level(IPL: 割り込み優先度)は実行する割り込みの優先度を表す。 これはプロセッサに読まれ、優先度の低い割り込みは優先度の高い割り込みを邪魔しないようになっている。

IPLレンジの例を図3.5に示す。1~15

図3.5 f:id:tom__bo:20161214155406p:plain

3.2.5 Processes

プロセスはユーザレベルのプログラムを実行するための環境で、主に以下を含んでいる。

プロセスは1つのシステムで何千ものプロせエスを実行するためにカーネルによって多重タスク処理されている。

プロセスはユニークな"process ID(PID)"によって区別される。 プロセスは1つ以上のスレッドを含み、これらは同一のアドレス空間とファイルディスクリプタを保持している。 スレッドは、スタック、レジスタ、プログラム・カウンタを持った実行可能なコンテキストである。 複数のスレッドは1つのプロセスにCPUをまたいだ並列な実行を可能にする。

[Process Creation]

プロセスはたいていfork()システムコールを使って作られる。 これにより、独自のPIDを持った重複したプロセスが作られ、exec()システムコールによって異なるプログラムが実行される。
図3.6はlsコマンドを実行するshellプロセスが作られる様子を表している。

図3.6 f:id:tom__bo:20161214155416p:plain

fork()システムコールはパフォーマンス改善のために"copy-on-write(COW)"戦略をとっている。 これはコピー前のアドレス空間に参照を追加しただけのもので、どちらかのプロセスに変更が加わるときに初めて実際のコピーが作られる。

[Process Environment]

プロセスの様子を図3.8に示す。
これはプロセスのアドレス空間カーネルメタデータを含むものである。

カーネルコンテキストはプロセスのプロパティや統計情報, PID, UID, 様々な時間などの情報を含み、これらはpsコマンドで調べることができる。 これはファイルディスクリプタも含み、スレッド間で共有されているどのファイルを参照しているかを示している。
実際にはユーザアドレス空間はメモリセグメントやライブラリ、ヒープを含むが、詳しくは7章メモリで扱う。

3.2.6 System Calls

システムコールは特権的なルーチンを実行するために呼ばれる。 システムコールで可能なことは数百に及ぶが、その数をできるだけ少なくするように努力されている。 より精巧な機能はメンテンナンス開発やメンテナンスを楽にするためにユーザランドでシステムライブラリとして実装されている。
主要なシステムコールは以下である

  • read() : read bytes
  • write() : write bytes
  • open() : open a file - close() : close a file
  • fork() : create a new process
  • exec() : execute a new program
  • connect() : connect to a network connection
  • stat() : fetch file statistics
  • ioctl() : set I/O properties, or other miscellaneous functions
  • mmap() : map a file to the memory address space
  • brk() : extend the heap pointer

システムコールはドキュメントgあ充実していて、だいたいOSとともに公開されるmanページがある。 たいていはシンプルで一貫したインターフェースであり、これらは特別な変数"errno"がある。 これは遭遇したエラーとその種類を特定する。 大抵のシステムコールは明確な目的があり、以下に明確な使い方がない少数のサンプルを示す。

  • ioctl()
    • これは一般にカーネルからの多種多様なリクエストに使われる
    • 特に管理者用ツールで、他に適したシステムコールがないときに使われる
  • mmap()
    • これはライブラリや実行しているものにアドレス空間を割り当てるために使われる
    • プロセスにメモリを割り当てるために、brk()ベースのmalloc()
  • brk()
    • これはヒープポインタを拡張するためにあり、プロセスのワーキングメモリのサイズを定義する
    • brk()は特にmalloc()を使った時に実行される。

もしシステムコールに不慣れなのであれば、manページから始めるのが良い。 曖昧な環境を背景としているため、ioctl()は最も学ぶのが難しいだろう。 Linuxのperf(1)は権限付き実行のパフォーマンスを測定するツールとして利用されている。

3.2.7 Virtual Memory

仮想メモリはメインメモリを抽象化したもので、プロセスやカーネル自身をほとんど無限に知恵供している。 これはマルチタスクをサポートしていて、これのおかげで、プロセスyとカーネルは各々のアドレス空間を競合を気にすることなく操作することができる。 また、OSに対して、透過的にメモリとディスクストレージに仮想メモリを割り当てることで、メモリへの割当を超過することを防いでいる。

図3.9は仮想メモリの様子を示し、primary memoryはRAM, secondary memoryはstorage device(disk)を表している。

図3.9 f:id:tom__bo:20161214155428p:plain

3.2.8 Memory Management

仮想メモリがメインメモリの拡張として(ディスク)ストレージを使えるようにする一方で、カーネルはほとんどのアクティブなデータを実メモリ上に保つ用に努力している。

これにはおおきく2つある - Swapping : プロセス全体をメインメモリとストレージで間で移動する - Paging : ページという小さい単位で移動する(4kb程度)

スワップはもともとUnixの方式で、ひどいパフォーマンスロスを引き起こす。 ページングはより効率的で、BSDにページングされた仮想メモリとして導入された。 どちらの方式もLRU(Least recently used)で動いている。

Linuxでは"swapping"という用語は"paging"と言われるようになっている。 Linuxカーネルは古いユニックススタイルの全てのスレッドとプロセスをスワップする方式をサポートしていない。 ページングとスワップに関する詳しい説明は7章メモリを参照のこと。

3.2.9 Schedulers

Unixとその派生系はtime-sharingシステムで、実行を細かい単位に分割することで、同時に複数のプロセスを実行できるようにしている。 プロセッサにおけるプロセスのスケジューリングやそれぞれのCPUではOSカーネルの主要素である"scheduler(スケジューラ)"が動作している。

図3.10にスケジューラがスレッドをCPUに割り当てる様子を示している。

図3.10 f:id:tom__bo:20161214155438p:plain

基本的な役割はCPU時間をプロセスやスレッドに割当、"priority"を管理することにある。 スケジューラは全てのスレッドを"ready-to-run"状態に保ち、伝統的にこれらは"run queues"と呼ばれる。 最近のカーネルではCPUごとにキューが実装されていたり、はたまた、スレッドを追いやすいようにキューでないデータ構造をしていることもある。 もし、利用可能なCPU数よりも多くのスレッドを実行しようとしたら、優先度の低いものは実行を待たされ、優先度の高いものを優先する。   プロセスの優先度は負荷に対するパフォーマンスを上げるためにスケジューラによって動的に変更することができる。

負荷は以下のどちらかに分類することができる。 - CPU-bound - 演算が重いもの - 例えば科学計算や数学的な分析など - 実行に時間がかかり、CPUリソースによって性能が制限されているもの

  • I/O-bound
    • 演算が少なくI/Oを発生させるもの
    • ウェブサーバやファイルサーバなど、よくレイテンシの低さが要求されるもの
    • 負荷が増えた時にストレージのI/Oやネットワークリソースによって制限されているもの

スケジューラは、レイテンシの低さが求められる環境であれば、CPU-boundな処理を特定し、そのプライオリティを下げることができる。
最近のカーネルでは"scheduling classes"という優先度と実行可能なスレッドを管理する異なるアルゴリズムを適用できる仕組みをサポートしている。 これらはクリティカルでない処理を含む全ての処理の優先度を高く保つ"real-time scheduling class"を含んでいる。 このあとで説明するpreemptionのサポートとともにリいようすることで、"real-time scheduling class"はリアルタイムシステムにおいて低いレイテンシを達成できる。

より詳しいカーネルスケジューリングに関しては6章を見ること。

3.2.10 File Systems

ファイルシステムはデータとファイル、ディレクトリによって構成されている。これらはPOSIX標準に乗っ取りファイルベースのインターフェースを提供している。 また、カーネルは複数のファイルシステムをサポートすることができる。

OSは("/")を根とするトップダウン木構造の構造で構成されるグローバルな名前空間を提供する。 ファイルシステムはこの木構造に"mount"することで自身の木構造を"mount point"に接続する。 これによりユーザはファイルの名前空間をそれ以下のファイルシステムの種類を意識せずに透過的に扱えるようにしてくれる。

例えば図3.11のようなシステムがある。

図3.11 f:id:tom__bo:20161214155448p:plain

トップレベルのディレクトリは設定ファイルとしてetc, ユーザれエルのプログラムとライブラリのためにusr, デバイスファイルにdev, システムログなどを含む様々な用途にvar, ホームディレクトリとしてhomeが存在している。
この例ではvarとhomeディレクトリは他のステレージデバイスでおそらく異なるファイルシステムを利用しているが、ほかの要素と同じようにアクセスできる。

いくつかのファイルシステムカーネルによって動的に作られる。
たとえば/procや/devなどがある。

[VFS]

バーチャルファイルシステム(VFS)はカーネルの抽象ファイルシステムであり、UnixファイルシステムNFSと共存しやすいようにSun Microsystemsによって開発された。
その役割を図3.12に示す。

図3.12 f:id:tom__bo:20161214155458p:plain

VFSのインターフェースは新しいファイルシステムカーネルに追加することを容易にしてくれる。 また、先に示したようなグローバル名前空間も提供するので、ユーザプログラムやアプリケーションはファイルシステムによらずこれらに透過的にアクセスすることができる。

[I/O Stack]

ストレージデバイスを元にしたファイルシステムでは、ユーザレベルのソフトウェアからストレージデバイスまでのパスを"I/O stack"と呼ぶ。
一般的なI/O stackを図3.13に示す。

図3.13 f:id:tom__bo:20161214155549p:plain

詳細なファイルシステムに簡易手は8章に、ストレージデバイスに関しては9章に示す。

3.2.11 Caching

歴史的にディスクI/Oは高いレイテンシを発生させることから、様々なソフトウェあスタックのレイヤでキャッシュとバッファリングがされてきた。

表3.2にキャッシュの分類を示す。

表3.2 f:id:tom__bo:20161214155620p:plain

3.2.12 Networking

最近のカーネルは組み込みのネットワーク・プロトコルを提供していて、ネットワーク上の他のシステムとコミュニケーションできるようにしている。 これらは"TCP/IP stacks"と言われ、一般によく使われるTCP,IPにちなんでいる。 ユーザレベルのアプリケーションは"sockets"というエンドポイントを介して、ネットワークに接続できる。

ネットワークに接続するための物理的なデバイスは"network interface"と呼ばれ、たいていは"network interface card(NIC)"によって提供される。 一般に管理者がやるべきことはネットワークインターフェースにIPアドレスと紐付けることである。

ネットワーク・プロトコルは頻繁に変わることはないが、強化やオプションはよく変更される。例えば、TCPのオプションやTCPの服装制御アルゴリズムがそうだ。
ネットワーキングに関しては10章を見るように。

3.2.13 Device Drivers

カーネルは様々な物理デバイスと連携できる必要がある。 それらは"device drivers"によって達成される。これらは時として、ハードウェアを開発しているベンダーから提供されることもある。いくつかのカーネルは"pluggable"デバイスドライバをサポートしていて、これらによりデバイスドライバをシステムの再起動無しに読み込んだりできる。

デバイスドライバはそのデバイスに"character"か"block"のインターフェースを提供する。 characterデバイスは"raw devices"とも呼ばれ、全てのI/Oを1つの文字として、バッファリングせず、連続なデータとして提供している。これらはキーボードやマウスなどがある。 ブロックデバイスは歴史的に512バイトのブロック単位でI/Oを行う。これらは"buffer cache"と呼ばれるメインメモリの領域をバッファに使うことで効率化している。

3.2.14 Multiprocessor

マルチプロセッサのサポートは複数のCPUで並列に演算を擦ることを可能にしてくれる。 たいていは全てのCPUが同等に扱われる"symmetric multiprocessing(SMP)"になっている。これでは、並列に走っているスレッドをメモリやCPU間で共有を停止する問題を扱うのが難しい。 共有のスケジューリングやスレッドの動機については7章のメモリを見ること。

[CPU Cross Calls]

マルチプロセッサシステムにおいてはCPUは協調しあう必要があるときおまる。例えば、キャッシュの一貫性を保つためなどだ。 そういった場合CPUは他のCPUに"cross call"を即座に発行する。 クロスコールはプロセッサに対する割り込みで、即座に実行されるように設計されている。 クロスコールは次のpreemptionでも使われる。

3.2.15 Preemption

カーネルのプリエンプションサポートはユーザレベルのスレッドにカーネルへの割り込みを可能にする。 これによって、厳しいレスポンスタイムの要求があるリアルタイム・システムが可能になる。 プリエンプションをサポートしているカーネルを"fully preemptable"といい、多少の割り込み不可なクリティカルセクションがあったとしても、fullyという。

Linuxのアプローチは"voluntary kernel preemption"といい、カーネルが論理的なポイントで確認を行い、プリエンプションを実行される。 これにより、"fully preemptive kernel"となる複雑さを酒、一般的な負荷において、レイテンシを下げることができる。

3.2.16 Resource Management

OSはCPUやメモリ、ディスク、ネットワークに対する様々な設定操作の方法を提供している。これらを"resource controls"といい、クラウドコンピューティング場などの様々なアプリケーションのホストでパフォーマンスの管理をできるようにしている。 予期のUnixやBSではプロセスごとに、nice(1)やulimit(1)などの基本的なリソースコントロール機能があった。

Solarisベースのシステムでは、Solaris 9(2002)からadvancedなリソースコントロールがあり、これはresources_controls(5)のmanページにある。 Linuxでは2.6.4(2008)からコントロールグループ(cgroup)が開発されている。 これらはkernel sourceの"Documentation/cgroups"にドキュメントが存在する。 今後は、それぞれのリソースコントールに関してはそれぞれの章で説明されている。

3.2.17 Observability

OSはカーネル、ライブラリ、プログラムを含んでいる。 これらはシステムのアクティビティを観察したり、パフォーマンスを分析するツールを含み、特に/usr/binと/usr/sbinに含まれている。 サードパーティ製ツールも適宜インストールされることがある。

観測ツールやそれの元になるシステムについての詳解は次の章に続く。