Software Transactional Memory の雰囲気メモ

wikipedia の ( Software Transactional Memoryのページ ) を眺めたまとめのメモと、toy 実装をしてみた話。

github.com

stm の rust 実装 見ながら書いてたんだけど、そのまま rust で書くのもあれなのでなんとなく go で書いてみた。 ちなみに int にしか対応していない完全なトイ実装。

STM

並列プログラミングをする際に、共有メモリへのアクセスを制御するための機構のことで、ロックを使用した排他制御機構の代替として使用できる。 例えば、ロックを使用してスレッドセーフなプログラムを実現するには以下のようになる。

v := 1
m := new(sync.Mutex)

go func() {
    m.Lock()
    v += 1
    m.Unlock()
}()

go func() {
    m.Lock()
    v += 1
    m.Unlock()
}()


...

これを STM で実現すると以下のようになる(自分で実装した STM だけど大体ほかの実装もこんなシンタックスになってるはず)。

tvar := istm.NewTVar(1)

go func() {
    tv, _ := istm.Atomically(func(t *istm.Transaction) (int, error) {
        v := tvar.Read(t)
        tvar.Write(t, v+1)
        return v, nil
    })

    fmt.Printf("t1: %v\n", tv)
}()

go func() {
    tv, _ := istm.Atomically(func(t *istm.Transaction) (int, error) {
        v := tvar.Read(t)
        tvar.Write(t, v+1)
        return v, nil
    })

    fmt.Printf("t2: %v\n", tv)
}()

...

Atomically のブロック内は必ずアトミックであることが保証されているので、STM の方ではロックを(シンタックス上は)使用せずにスレッドセーフなプログラムを書くことができる。 ロックを使用する問題点として、デッドロックやライブロックが発生するコードが書けてしまうこと、ロックし忘れてレースコンディションが発生する恐れがあること、 優先順位の逆転 が発生することなどがある。 STM はロックに比べて高いレベルの抽象化を提供しているので、そのあたり問題をいい感じに回避している。 また、STM の利点としてスケールしやすいという点もある。 ロックを用いた場合、大雑把にロックを取るとそこがボトルネックとなりスケールしないプログラムになってしまう(逆に細粒度にロックを取ろうとするとバグを生み出しやすいという問題もある)。 しかし、STM は変更をコミットする瞬間だけロックを取ることで大きなロックを取る必要がなくなりスケールするプログラムを意識しなくても書くことができる。 問題点もあって、コミットにする際に一貫性が取れていないとすべての処理をアボートして、再度処理を初めからすべて実行し直すためオーバヘッドが大きいというのがある。

実装

github.com

DB で言うところの楽観的ロックみたいな実装をしている。 アトミックなブロック中 (istm.Atomicallyに渡されたクロージャ) での変更はトランザクションでログとして持っておき、ブロックが終了するときにまとめて変更をコミットする(このへん)。 コミット処理の際に一貫性を検査し、他のトランザクションと衝突していたら自分側の変更をすべて破棄する。これを成功するまで何度も再実行する。

参考

バリア同期の実装

Java Concurrency in Practice の 5.5.4 Barrier の話

amzn.to

バリア同期とは

バリア同期とは、各スレッドの実行の進行具合を合わせるために使用する同期機構のこと。 複数スレッドにまたがった依存関係のある計算(処理)の完了を待って、処理を実行する際に使用する。 たとえば、時間のかかる計算 A と B の処理を C で使用する時、C を実行する前に A と B の終了をバリア同期で待ってから実行するというような使用方法がある。

実装

実際に Ruby で表現すると以下のようになる。 イニシャライズ時に渡された数(n)になるまでそのスレッドを待ち状態にしておき、待ち状態数が n になったら @cv.broadcast をして待ち状態のスレッドを起こすということをしている。

class CyclicBarrier
  def initialize(n)
    @n = n
    @wait_count = 0
    @mutex = Mutex.new
    @cv = ConditionVariable.new
  end

  def wait
    @mutex.synchronize do
      @wait_count += 1

      if @wait_count == @n
        @cv.broadcast
      else
        @cv.wait(@mutex)
      end
    end
  end
end

使用部分は以下のようになる。 Runner#reduce_process が別スレッドで走らせた Runner#process の計算結果を使用するという例。 実際は sleep(i) の部分に重たい処理が来ることになる。 実行結果を見るとわかるんだけど、 Runner#reduce_processRunner#process の実行の終了を待ってから実行されていることがわかる。

class Runner
  def initialize(n)
    @n = n
    @cb = CyclicBarrier.new(n)
    @queue = Queue.new
  end

  def run
    (@n - 1).times.map do |i|
      Thread.start(i + 1) { |j| process(j) }
    end

    reduce_process
  end

  private

  def reduce_process
    puts "[Wait] reduce process"
    @cb.wait
    puts "[Start] reduce process"

    result = 0
    until @queue.empty?
      result += @queue.pop
    end

    puts "[Done] result is #{ans}"
  end

  def process(i)
    puts "[Start] process #{i}"

    sleep(i)
    @queue << i

    puts "[Wait] process #{i}"
    @cb.wait
  end
end

Runner.new(4).run

実行結果

$ ruby runner.rb
[Start] process 2
[Start] process 3
[Wait] reduce process
[Start] process 1
[Wait] process 1
[Wait] process 2
[Wait] process 3
[Start] reduce process
[Done] result is 6

コードは全体はこちら↓↓↓

github.com

Lock Striping についてとその実装

Java Concurrency in Practice の 5.2.1. ConcurrentHashMap にて Lock Striping というロックの方法が出てくる。 Lock Striping の説明と実装、および簡単にパフォーマンスを測ったのでそのメモ。

Java Concurrency in Practice

Java Concurrency in Practice

  • 作者: Brian Goetz,Tim Peierls,Joshua Bloch,Joseph Bowbeer,David Holmes,Doug Lea
  • 出版社/メーカー: Addison-Wesley Professional
  • 発売日: 2006/05/09
  • メディア: ペーパーバック
  • 購入: 7人 クリック: 14回
  • この商品を含むブログ (22件) を見る

Lock Striping とは

Lock Striping とは Array や HashMap などのオブジェクトに対して、複数スレッドから書き/読み込む場合に、そのオブジェクト全体のロックを取るのではなく部分的にロックを取ること。 例えば、Array オブジェクトの 0 から 9 は Mutex1、10 から 19 は Mutex2 が管理するようにすること。 このようにすることで、依存関係のない操作を複数スレッドで実行する際 (上の例なら Arrayオブジェクトの index 1 と 11 への書き込みなど) に互いの操作を待たなくて良くなり並列度が上がり、パフォーマンスの向上が見込める。

1 つの Mutex オブジェクトでロックする際の問題

Array や Map などのオブジェクトに対して、複数スレッドから書き込み/読み込みがある時にロックが必要になる。 同じキーに対して複数のスレッドから書き込んでしまった場合にレースコンディションが発生するからである。 1 つのオブジェクトに対して 1 つの Mutex オブジェクトを使用すると、ロックの粒度が適切でない時がある。 たとえば、以下のように Map オブジェクト dict に Thread 1 (go の場合は goroutine) では "foo" というキーに 値 1 をセットし、Thread 2 では "bar" というキーに 2 をセットするとする。 この時 Thread 1 と Thread 2 の操作は互いに独立しており、並列に実行してもレースコンディションが発生しないためそれぞれの Thread を並列に実行できた方がパフォーマンスがよくなる。 しかし、dict に対して 1 つの Mutex オブジェクトを使用すると、互いに独立している操作であっても dict への操作は並列に実行することができなくなる。

dict := new(map[string]map)

// In Thread 1
dict["foo"] = 1


// In Thread 2
dict["bar"] = 2

実装

Lock Striping な辞書の実装。 キーは文字列、値は数字のみにしている。 hash 関数に FNV prime を使っている。 Hash値(とbucket sizeの剰余)ごとに bucket をもって、それごとにロックを管理している。 その為、ちがう bucket であれば並列に実行可能になる。

github.com

パフォーマンス

スペック

計測したコード

github.com

結果

synchronizedDict~ が dict に対して 1 つのロックを取っている方で、 stripedDict~ が Striping Lock をしている方。 最後の数 (たとえば、synchronizedDictWriting11) は Write する Worker の数を表している (1,3,5 でためした)。 だいたい予想通りの結果になっているようにみえる。 write する worker が 1 つのとき (並列に実行していない時) は hash 値の計算などのオーバヘッドがあるから若干 stripedDict のほうが遅くなっている。 それ以外はロックが分散されて、並列度が上がったためパフォーマンスがよくなっている。

Elapsed Time in synchronizedDictWriting1: 43.632465ms
Elapsed Time in stripedDictWriting1: 35.341727ms

Elapsed Time in synchronizedDictWriting2: 62.054392ms
Elapsed Time in stripedDictWriting2: 48.307852ms

Elapsed Time in synchronizedDictWriting5: 172.436661ms
Elapsed Time in stripedDictWriting5: 89.864355ms

リポジトリごとに user.name と user.email を変更する

会社で Github Enterprise を使っているので、github.com の方の user.nameuser.email でコミットしてしまわないようにリポジトリごとに設定を変更できるようにした。

gitconfig にあった user.nameuser.email をけして、useConfigOnlytrue にした。 こうすることで、リポジトリごとに user.nameuser.email を設定しないと *** Please tell me who you are. などといわれてコミットに失敗するようになり、誤ったユーザでのコミットを防げる。 変更前

[user]
    name = ganmacs
    email = ganmacs@gmail.com

変更後

[user]
    useConfigOnly = true

あとは、シェルに以下のような関数を定義しておけば良さそう。

function company() {
    git config user.name "namae"
    echo "Set user.name as $(git config --get user.name)"
    git config user.email "foo@bar.com"
    echo "Set user.email as $(git config --get user.email)"
}

function private() {
    git config user.name "ganmacs"
    echo "Set user.name as $(git config --get user.name)"
    git config user.email "ganmacs@gmail.com"
    echo "Set user.email as $(git config --get user.email)"
}

その他

pre-commit hook などでディレクトリごとに自動で設定する方法も考えたが、大げさだなと思ってこの方法に落ち着けた。 もっといい方法があれば教えて欲しい。

Ruby の Monitor

Ruby には Monitor というクラスがあるんだけど、よく見るわりに Mutex との違いをよくわかっていなかった。 たまたま Java Concurrency in Practice を読んでいたら 2.3.2 Reentrancy で同じような概念の話が出てきて、少しわかった気がするのでそのメモ。

Java Concurrency in Practice

Java Concurrency in Practice

  • 作者: Brian Goetz,Tim Peierls,Joshua Bloch,Joseph Bowbeer,David Holmes,Doug Lea
  • 出版社/メーカー: Addison-Wesley Professional
  • 発売日: 2006/05/09
  • メディア: ペーパーバック
  • 購入: 7人 クリック: 14回
  • この商品を含むブログ (22件) を見る

Monitor とは

Ruby の Monitor は何度も lock 出来る Mutex とドキュメントに書いてある。 特になんの意味もない例だけど以下のようにロック中にさらにロックできる(もちろん同じスレッド内で)。 もしこのコードを Mutex を使用して m = Mutex.new とした場合、2回めの m のロックする部分(m.synchronize)でデッドロックが発生するが Monitor を使用すると発生しない。

m = Monitor.new
m.synchronize do
  m.synchronize do
    # your code
  end
end

使い所

たぶん使い所は、すでにあるコードを組みわせてアトミックな処理をするところ。 下のようなコードのような感じ。もともと Nanika クラスに sugoi というスレッドセーフなメソッドがあったとする。 この時、メソッド内でアトミックに sugoi を2回呼び出す ultra_sugoi というメソッドを新たに追加しようとしたときに Monitor が使えそう。 Monitor ではなく Mutex を使用すると、ultra_sugoi 内でロックを取ってから sugoi のメッソド呼び出しが発生して、 sugoi 内で またロックを取りに行きデッドロックが発生する。 しかし、Montior を使用すると何度でもロックが成功するので、 sugoi をアトミックに2回呼び出せる。

class Nanika
  def initialize
    @monitor = Monitor.new
    @sugoi_value = 0
  end

  def sugoi
    @monitor.synchronize do
      @sugoi_value += 1
    end
  end

  def ultra_sugoi
    @monitor.synchronize do
      sugoi
      sugoi
    end
  end
end

nanika = Nanika.new

[*1..2].map {
  Thread.new do
    nanika.ultra_sugoi
  end
}.each(&:join)

その他

javaの本では reentrant という言葉で説明されていた。

reentrancy とは

Reentrancy means that locks are acquired on a per-thread rather than per-invocation basis.

リエントラント性とは、呼び出し単位ではなくスレッド単位でロックが取得される。

Lock with reentrant

同じスレッドであれば、何度でもロックを取得できる ロックしたスレッドとそのスレッド内でのロック保持数を記録しておく。Ruby の Monitor。

Lock without reentrant

呼び出し(処理)単位でロックを取っているので、同じスレッドであっても再度ロックを取れない。 単純にロックされているかどうかだけを見る。Ruby の Mutex。

RubyはGILが

そうね

リーダ選出: ring アルゴリズム

Raft Consensus Algorithm をみつけてリーダ選出とは、となったので調べてちょっと書いてみたメモ。なお、この記事では raft のことは書いてない。

リーダ選出とは

リーダ選出アルゴリズムとは、分散システム内で特別な役割を持ったノード(プロセス)を選出するためのアルゴリズムのこと。 リーダを決め、中央集権的にシステムを動かすことで、権限が分散している場合にくらべシステム内の一貫性を容易に保てる1。 たとえば、分散メモリがあるとすると、あるプロセスが分散メモリに値を書き込む際には、そのプロセスはロックを取ってから書き込みをしないとレースコンディションが発生する可能性がある。この時、一つのプロセスをリーダにし、そのプロセスが他のプロセスにロックを提供し、書き/読み込みをしたいプロセスがロックを取ってクリティカルコンディションに入ることで安全に分散メモリを操作できる。

ring アルゴリズム

ring 型のネットワークを考える。 ring型ネットワークとは、それぞれのプロセスが自分以外の2つのプロセスと結びついてる様なネットワーク。 要は以下の形をしたネットワーク。 f:id:ganmacs:20170325110434g:plain

CS 551: Synchronization, Token Ring Election Algorithm Exampleより

この記事での ring アルゴリズムは以下の話。wikipediaの分散システムのページを見てると、これは ring アルゴリズムの中でも Rings with unique IDs というやつっぽいのだけど、いまいち全体の世界観をつかめていないのでよくわかってない。

このアルゴリズムは election message を送るステップと coordinator message を送るステップの2つのステップに分かれる。 まず、現在のリーダが何かしらの理由 (通信不能になったり、プロセスが死んだり) で fail したところからリーダ選出が始まる。 リーダが fail したのを他のプロセスが検知して election message というメッセージを次のプロセスに送る。もし、次のプロセスが fail したリーダのプロセスだった場合はその次のプロセスに送る。 election message とは自分の id を追加した配列を含んでいるメッセージのこと。例えば、下の図の場合は P3 が自分の id である 3 というメッセージを、それを受け取った P5 は、受け取ったメッセージに自分の id である 5 を追加した 3,5 というメッセージを次のプロセス P0 に送る。 この 3 であったり、3,5 であったりを election message といっている。そして、election message が ring を一周して元のプロセス(図ではP3)に戻ってきたところで election message を送るステップは終了する。

f:id:ganmacs:20170325111007g:plain

CS 551: Synchronization, Token Ring Election Algorithm Exampleより

ここからが、次の coordinator message を送るプロセスになる。 election message が ring を一周して、最初にリーダの fail を検知したプロセスに戻ってきたとき、election message の中身は ringに所属しているプロセスのidが全て含まれている。この id の中から一番大きな値を選びだし、その id が次のリーダだということを他のプロセスに周知するメッセージが coordinator message になる。coordinator message が ring を一周して元のプロセスに戻ってきたところで coordinator message を送るステップも終了しリーダが決定する。 例えば下の図では、P3が最初にリーダの fail を検知したプロセスだとして、そこに返ってきた election message が 3,5,0,1,4 だとすると、この中から一番大きな数である 5 を次のリーダ(つまりプロセス P5 )とする。そこで P3 は 「次のリーダは P5 だ」というメッセージまた他のプロセスに送信する。このメッセージを coordinator message という。他のプロセスも自分の次のプロセスに「次のリーダは P5 だ」というメッセージをおくる。そして、P3 に戻ってきたところリーダ選出を終えて P5 がこのシステムのリーダとなる。

f:id:ganmacs:20170325122210g:plain

CS 551: Synchronization, Token Ring Election Algorithm Exampleより

作った

ring アルゴリズムを実装してみた。

github.com

ring アルゴリズム自体の実装は https://github.com/ganmacs/eve/blob/master/lib/eve/agent/ring.rb この辺にある。仕様的なものを見つけることができなかったので、上の図を見て気持ちを感じて実装した。


  1. EffatParvar, MohammadReza, et al. “Improved algorithms for leader election in distributed systems.” Computer engineering and technology (ICCET), 2010 2nd International Conference on. Vol. 2. IEEE, 2010.

Linuxシステムプログラミング8章

Linuxシステムプログラミングの8章メモリ管理の雑なメモ。 下に行くほど雑になってそう。この本。

Linuxシステムプログラミング

Linuxシステムプログラミング

プロセスアドレス空間

  • 物理メモリを仮想化しているため、プロセスは物理メモリを参照するのではない。
  • カーネルがプロセスそれぞれに仮想アドレス空間を与える
  • 仮想アドレス空間は0から始まるリニアアドレス

ページとページイン/アウト

  • 仮想アドレス空間はページで構成される
  • サイズはマシンによる 32だと4KB、64ビットマシンだと8KB
  • ページには有効と無効という概念がある
    • 有効なページは実際に対応する物理メモリ、またはディスク上のファイルがが存在する
    • 無向なページはアクセスするとセグフォになる
  • プログラムが物理メモリに存在せず二次記憶装置に存在するページにアクセスしようとすると、ページフォルトMMUが発生させる
    • カーネルページフォルトに対応し、二次記憶装置から物理メモリにページインする
    • 物理メモリ上にあって、直近で最もアクセスされていないデータはページアウトされる

ページ共有とcopy-on-write

  • (異なるプロセスの)異なる仮想アドレスから物理メモリ内のデータを共有できる
    • 読み書き専用、読み取り専用どちらでも良い
  • 書き込む処理は二種類ある
    • 一つは単純に共有しているページにプロセスが書き込み変更された同じデータを参照
    • もう一つはMMUが書き込みを検知し例外をなげる、カーネルがその例外を検知して透過的にそのうろセス専用のページを新たに作り、そこに書き込むようにする(Copy on write)

メモリ領域

  • カーネルはページを複数のブロックに分けアクセスパーミッションなどの属性を管理している
    • このブロックをメモリ領域、セグメント、マッピングという
  • すべてのプロセスには決まったメモリ領域が存在する
    • テキストセグメント - プロセスの実行コード、文字列、定数、その他専用のデータを格納。読み取り専用、オブジェクトファイルにマッピングされる
    • スタック - 実行時に動的に拡張、縮小するデータ。ローカル変数や関数の戻り値などに使う
    • データセグメント(ヒープ領域) - プロセスの動的メモリを格納する。書き込み可能(malloc)
    • bss - 未初期化のグローバル変数を格納。

動的メモリ割り当て

  • 動的メモリは、コンパイル時ではなく実行時に割り当てるもの
    • 実行時になるまで、実際のサイズなどはわからない
  • cだとmalloc で動的メモリ割り当て出来る
    • 成功すると、割り当てたメモリ領域の先頭アドレスを返す

配列割当

  • 配列の割当にはcallocをつかう
    • mallocと違って0で初期化する

メモリ領域のサイズ変更

  • realloc でメモリ領域のサイズを変更できる

動的メモリの解放

  • 動的に割り当てたメモリは明示的に解放するまでプロセスアドレスの一部として存在し続ける
    • free を使う
    • 開放しないとメモリリークする
    • 解放後のメモリにアクセスしてはいけない(ダングリングポインタ)

アラインメント

  • ハードウェアからみたメモリ領域とアドレスの関係
  • データサイズの定数倍のメモリアドレスへ配置された変数を自然なアライメントという
    • 32ビットの変数がメモリ上で4の倍数のアドレスに配置されているとき

アラインメントされたメモリの割当

  • コンパイラとCライブラリがよしなに解決してくれる
  • 32ビットシステムでは8バイト,64ビットだと16バイト境界にアライメントされる
  • posix_memalign を使用すると、任意の倍数でアライメントされたsizeバイトの動的メモリを割り当てられる

他のアライメント問題

  • 非標準の型
    • 構造体のアライメントはメンバの最大サイズに合わせる
      • 最大サイズを持つメンバが4バイト境界でアライメントされる32ビット整数なら、その構造体は4バイト以上のアライメント
    • パディング(padding)が必要。
      • char(1バイト)のあとにintのメンバ(4バイトでアライメントされる)がある場合、charの後ろに3倍とのパディングが必要
    • 共用体のアライメントはメンバの最大サイズに合わす
    • 配列アラインメントは要素に合わせる
  • ポインタ
    • 以下の例では、unsigned longは4 or 8バイト境界に割り当てられるのに、charはほぼ確実に1バイト
    • そこで c をロードするとアラインメント違反
    • 違反の結果はアーキテクチャ依存でクラッシュすることもある
char greeting[] = "Ahoy Matey";
char *c = greeting[1];
unsigned long badnews = *(unsigned long *) c;

データセグメントの管理(ヒープ領域)

  • でたーセグメントを直接操作する関数はあるが、malloc などが使いやすく機能も豊富であるためほぼ使われていない
  • brk はデータセグメントの末尾(break point)を渡された場所を変更する

無名メモリマッピング

  • 典型的な malloc はデータセグメントを2の累乗のサイズの領域が並んだ状態に分割し,要求されたサイズに最も近い領域を貸す
    • 直前の領域がフリーの場合はつなげて,一つの大きなフリー領域にする
    • 戦闘だった場合は領域を縮めてカーネルに返す
    • バディメモリ割り当てシステムという
  • 内部フラグメンテーション - 要求されたメモリより大きなメモリ領域を返す問題
  • 外部フラグメンテーション - サイズ分のメモリ領域があるにも関わらず,複数のメモリ領域に分断されている
  • 領域Bと領域Aが隣接しており,領域Aがbreakpointに隣接している場合,Bを開放してもAが終わらない限り開放されない

  • 巨大なメモリ割り当てをするとglibcはヒープを使用せす無名メモリマッピングをする

    • ファイルを使わない
    • 巨大で,0に初期化された領域を使用できる
    • 本来のヒープの外にあるのでフラグメンテーションが発生しない
    • メモリ領域はサイズ,アクセスパー密書の変更が可能
    • 短所
      • メモリのサイズがページングサイズの整数倍になる,要求サイズがページサイズより小さいと無駄な領域が発生する
      • カーネルからのヒープ割当に比べてオーバヘッドが大きい

無名メモリマッピングの作成

/dev/zero のマッピング

高度なメモリ割り当て

  • mallopt を使用してカーネルパラメータを変更できる。

メモリ割り当てのデバッグ

メモリ割り当て統計情報

  • mallinfo でメモリ割り当ての統計情報を得る

スタック上のメモリ割り当て

  • スタックはプログラムのオート変数(automatic variable)を格納する場所
  • allocaを使ってスタック上で動的にメモリ割り当てをする
    • メモリ領域はスタック上に取られる
    • つまり、alloca を実行した関数がリターンしたら解放/破棄される -> freeしなくていいのでコードが簡潔に
    • alloca を関数コールのパラメータ内で使用すると、関数パラメータの用のスタック領域にメモリを割り当ててしまうため使用を避ける

スタック上へ文字列をコピー

  • 文字列の一時的なコピー等に使える

メモリ割り当て方法の選択

  • malloc
    • 単純だが割り当てられたメモリがゼロクリアされていない
  • calloc
    • 配列の割当が容易でゼロクリアされてる、配列以外には使いづらい
  • realloc
    • メモリサイズを変更できる、ソレ以外使えない
  • brk and sbrk
  • 無名メモリマッピング
    • 共有可能、アクセスパーミッションもできる。サイズが大きいときにも使える。メモリが小さいと効率が落ちる
  • posix_memalign
    • 任意サイズの境界に従うメモリを割り当てる。移植性に難がある
  • memalign and valloc
    • unixシステムで使えるかも、posix標準ではない
  • alloca
    • 高速なメモリ割り当て、解放不要、サイズの大きな割当には不向き。
  • 可変サイズ配列
    • allocaとほぼ同じ、スコープを抜けたときに解放される。配列に限り有効

メモリ操作

バイト設定

  • memset(void *s,int c,size_t n) sのメモリ領域へcをnバイト分設定

バイト比較

  • memcmp(s1,s2,n) s1の先頭からnバイトs2と比較
    • 構造体は持つ内部にパディングを含むため正しく比較できない(パディングは不定値だから)

バイト移動

  • memmove(dst,src,n) srcの先頭nバイトをdstへこぴー
    • メモリ領域が重なっていない場合も正しく動く
    • もともと重ならないとわかっている場合にはmemcpyを使用する

バイト検索

  • memchrはメモリ領域内の指定されたバイトを検索する

メモリのロック

  • linuxカーネルは不要なページはスワップアウトして、必要に応じてスワップインするデマンドページングを使用している
    • この操作は透過的に行われるのでアプリケーションは気にしなくて良い
    • しかし意識したい場合もある
      • 決定論
        • 時間的な制約を持つアプリケーションではページフォルトしてディスクIOが発生して時間的制約を超過してしまう
      • セキュリティ
        • 機密情報がページアウトされてしまうと、暗号化されずディスクへ保存されてしまう
    • 当然全体のパフォーマンスが落ちる可能性があるので気をつける

アドレス空間の一部をロック

  • mlock(addr, len)でアドレスの範囲を指定して物理メモリ上にロックする

アドレス空間全体をロック

  • mlockallで(カレントプロセスの)メモリ全体を物理メモリ上にロックする

メモリのアンロック

  • munlock, munlockall

メモリの遅延割当

  • カーネルへメモリの追加を要求すると,カーネルは実際には物理メモリを割り当てずに成功を返す(commit)
  • 書き込んだ時点で初めて割り当てる(CoW)
    • 遅延できる
    • 実際に使用する分(割当要求分ではない)のみ物理メモリを使用する(ページ単位にする)
    • コミットしたメモリサイズをシステムの持っているメモリよりも大きくすることが出来る。(overcommit)

オーバコミットとOOM

  • 2GBのファイルのCoWをマッピングするのは2GBのメモリが必要
    • オーバコミットを使用すると、実際に書き込んだ部分だけで良い
  • 実装メモリサイズおよび、スワップ領域より大きなメモリ領域を要求したとき
    • カーネルは要求したしシステムコールに対して成功を返す
    • コミットしてるからどこからからメモリを取ってこないといけない
    • そこでkillするプロセスを見つけ出しOOM killerで殺す
  • OOM killer は sysctlパラメータの vm.overcommit_memoryに値を設定してOOMを逃れる
    • 0がデフォルトで、ヒューリスティックオーバーコミットする
    • 1はメモリを非常に多く使用するアプリだとこれがいいか
    • 2はオーバコミットを禁止する。