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

tom__bo’s Blog

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

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

Book Performance SystemsPerformance Linux

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

前回の続き。
7章3節メモリアーキテクチャを2つに分けた、後半部分。

7.3.2 Software

メモリマネージメントに関するソフトウェアの仕組みは、仮想メモリ、アドレス変換、スワッピング、ページング、アロケーションなどを含む。 メモリの解放、リストの解放、ページのスキャン、スワッピング、プロセスのアドレススペース、メモリアロケータといったこの節のトピックは最もパフォーマンスに関係している。

[Freeing Memory]

システムで利用可能なメモリが少なくなった時、カーネルが"free list"に加えて、メモリを解放する方法はいくつかある。
この方法を図7.6に示す。

図7.6 f:id:tom__bo:20161230232528p:plain

これらには以下の方法が含まれている。 - Free list - "idle memory"とも呼ばれる - 使われていないページのリストで即時のアロケーションが可能なもの - これは大抵複数の"free page lists"として実装され、それぞれのローカルグループに一つある(NUMA) - Reaping - 低いメモリスレッシュホールドを過ぎた時、カーネルモジュールとカーネルスラブアロケータは解放しやすいメモリを即座に解放する命令を出せる - これは"shrinking"としても知られる

Linuxにおける方法には以下がある(Solarisは略)

  • Page Caches
    • ファイルシステムのキャッシュ
    • "swappiness"というチューニング可能なパラメータによってどの程度メモリを解放するか決められる
  • Swapping
    • kswapdというページアウト用のデーモンによるページング
    • スワップファイルやスワップ領域が設定されている場合に、not-recently-usedなページをフリーリストに追加して、ページアウトする
  • OOM killer
    • "out-of-memory"killerはselect_bad_process()によってプロセスを発見し、oom_kill_process()によってプロセスを殺す
    • これは/var/log/messagesに"out of memory: Kill process"というメッセージで記録される

[Free List(s)]

Unixのオリジナルのメモリアロケータでは、メモリーマップとfirst-fitスキャンを使っていた。 BSDでページングされた仮想メモリが紹介されたときに、"first list"と"paged-out daemon"が追加された。 図7.7で示すフリーリストは使用可能なメモリを瞬時に割り当て可能にする。

図7.7 f:id:tom__bo:20161230232651p:plain

解放されたメモリは将来の割当のためにリストの先頭に追加される。 一方、ページアウトデーモンによって解放されたメモリは、(有効なファイルシステムキャッシュを持っている事が多いため)リストの最後に加えられる。 フリーリストの形態は図7.6で示したものが未だにLinuxSolarisベースのシステムで使われている。 フリーリストは特にカーネルのslabアロケータやlibcのmallocでallocator APIを介して使われている。

Linuxではページ管理にバディアロケータを使っている。
これは2のべき乗に従って、異なるサイズのメモリを割り当てるための複数のフリーリストを提供している。 "buddy"とは近隣のフリーメモリを探して一緒に割り当てることを表している。 バディフリーリストはメモリノード毎のpg_data_tに始まる次の階層構造の最下層にあたる。

  • Nodes
    • メモリの層、NUMA-aware
  • Zones
    • 特定の目的のためのメモリ範囲
    • (directmemory access(DMA) normal, highmem)
  • Migration types
    • unmovable, reclaimable, movable
  • Sizes
    • 2のべき乗の数のページ

フリーリストのノードに割り当てることで、メモリのローカリティとパフォーマンスを向上できる。

[Reaping]

リーピングは大抵カーネルのslabアロケータキャッシュからのメモリの解放に含まれている。 これらのキャッシュは再利用のためにslab-size chunkの中に未使用のメモリと共にある。 リーピングはこのメモリをページ割当のためにシステムに返す。

[Page Scanning]

ページングによるメモリの解放はカーネルのページアウトデーモンによって管理される。 フリーリストにおける利用可能なメインメモリの量がしきい値を超えると、ページアウトデーモンは"page scanning"を始める。 ページスキャニングは必要なときのみ行われる。 通常のシステムでは頻繁にスキャンが発生することはなく、起きても一時的なバーストとなる。

Linuxのページアウトデーモンはkswapd(1)と呼ばれ、これはページを解放するためにactive/inactive両方のメモリをLRUリストからスキャンする。 これらは図7.8に示すように履歴現象を提供するためにフリーなメモリと2つの閾値によって起動される。 一度フリーなメモリが最下限のしきい値を下回ると、kswapdは"synchronous"モードで動作し、要求に応じてメモリのページを解放する。 この最下限のしきい値は、vm.min_free_kbytesによって設定できる。 ページキャッシュは"active pages"と"inactive pages"で別々のリストを持っている。 これらの操作はkswapdが高速にフリーページを見つけられるようにLRUの形式で行われる。
この様子を図7.9に示す

図7.9 f:id:tom__bo:20161230232902p:plain

kswapdはアクティブでないページを先にスキャンし、必要に応じてアクティブなページをスキャンする。 "scanning"という用語は、ページをロックされていたりダーティな状態でないかをチェックしつつ、リストを走査することに由来している。

7.3.3 Process Address space

ハードウェアとソフトウェアの両方から管理される。 プロセスの仮想アドレススペースは必要なときに物理ページにマッピングされる仮想ページの範囲にある。 このアドレスは、スレッドスタック、実行可能なプロセス、ライブラリ、ヒープを格納するための"segments"と呼ばれる単位に分割される。 例として図7.12に32bitプロセスのx86SPARCプロセッサーを示す。

図7.12 f:id:tom__bo:20161230232918p:plain

実行可能なプログラムとライブラリは、実行可能なテキスト領域と実行可能なデータ領域からなっている。

  • Executable text
    • プロセスのための実行可能なCPU命令からなる
    • これはファイルシステム上のバイナリプログラムのテキストセグメントからマッピングされている
    • execute権限で読み取り専用である
  • Executable data
    • バイナリプログラムのデータセグメントからマッピングされている初期化された変数からなる
    • これは読み書きが可能だが、プライベートフラグを持っているので、へんこうはディスクに反映されない
  • Heap
    • プログラムの動作に必要なメモリと雑多なメモリ
    • malloc()を介して必要に応じて増える
  • Stack
    • 実行中のスレッドのスタック

ライブラリのテキストセグメントは他の同じライブラリを利用するプロセスと共有されていて、それぞれのプロセスでプライベートなコピーを持っている。

[Heap Growth]

一般的なヒープへの混乱はヒープの際限のない増大である。 これはメモリリークなのだろうか?

大抵のアロケータではfree()はOSにメモリを返さず、将来の割当に備えてキープする。 これはプロセスの在中メモリは増える一方であることを意味するが、それで普通である。

このメモリを減らす方法は以下がある。

  • Re-exec
    • 空のアドレススペースにexec()で始める
  • Memory mapping
    • mmap()やmumap()を使うことでメモリを返す。

幾つかのアロケータはmmapを操作モードとしてサポートしており、それは8.3.10節Memory-Mapped Fileを見るように。

7.3.4 Allocators

メモリアロケーションにはユーザとカーネルレベルの様々なアロケータがある。
図7.13に一般的なアロケータの役割を示す。

図7.13 f:id:tom__bo:20161230233043p:plain

ページ管理に関しては7.3.2節でFree Listと共に説明した。
メモリアロケータの特徴は以下がある。

  • Simple API
  • Efficient memory usage
    • メモリのアロケーションを繰り返すとメモリは"fragmented"な状態になる
    • そこで、メモリの使用部分を結合することで効率を高め、大きなアロケーションを可能にする
  • Performance
    • メモリアロケーションは頻繁に起こるが、マルチスレッド環境では同期プリミティブの競合によってパフォーマンスが落ちる
    • そこでアロケータは少しだけロックを使ったり、スレッド、CPU毎のキャッシュを使ったりすることで、メモリの局所性を向上するようにデザインされている
  • Observavbility
    • アロケータはそれがどのように使われ、どのコードパスがアロケーションの責任をもつのかを示すために、統計情報とデバッグモードを提供している

この節以降の部分では、カーネルレベルアロケータであるslabとSLUBそしてユーザレベルのlibmalloc, libumem, mtmallocについて説明する。
(libumem, mtallocはSolarisベースなので、省略)

[Slab]

カーネルのslabアロケータは特定のサイズのオブジェクトのキャッシュを管理し、ページアロケーションのオーバヘッド無しで高速にリサイクルすることを可能にする。 これは特に、固定サイズの構造体を頻繁にアロケートすることに効果的である。
これはSolaris2.4で開発され、Linux2.2に導入された、Linuxでは長い間デフォルトだったが、最近ではSLUBがデフォルトである。

[SLUB]

LinuxカーネルのSLUBアロケータはslabアロケータを基にデザインされ、様々なことを考慮した複雑なslabアロケータと言える。 これにはオブジェクトキューとCPUごとのキャッシュの削除、NUMA最適化をページアロケータに渡したことがある。 SLUBアロケータはLinux2.6.23からのデフォルトである。

[glibc]

GNU libcアロケータの振る舞いは、割り当てのリクエストサイズに依存する。 小さいサイズの割当は小さいユニットサイズをバディアルゴリズムのような方法で結合する。 大きい割当は木構造のルックアップでスペースを見つけ、更に大きいサイズではmmap()を利用するように切り替わる。