Edited at

並行処理、並列処理のあれこれ

More than 1 year has passed since last update.


この資料の背景

社内向け勉強会で並行処理と並列処理というテーマで発表しようとしたら、

OSの役割や仕組みなどを理解しないといけなくなったので、それらも込でまとめた資料になります。

調べてみて、まだまだ分からないところがたくさんあるので、これからも継続的に勉強していきたいです。


(前提) ProcessとThread

歴史的な経緯を理解すると、腹落ちします。


Processしかなかった時代

OS(カーネル)の主要な仕事の一つに、複数の仕事をどう効率的に実行するかをマネジメントするというものがある。

この仕事(実行)の単位を表す概念がProcessで、Threadという概念自体がLinux 2.4以前ではなかった。

仕事をするには、そのためのリソース(CPUリソースや、メモリリソース)が必要です。

なのでこういうリソースも含めた仕事するために必要な塊Processです。

ただの概念上の存在なので、あまり深く考えず、あぁそういう概念か、とするのがいいと思います。

ここで2つのことを押さえておく必要があります。


  1. 物理メモリはOS(カーネル)によって仮想メモリに分割されており、一つ一つのプロセスからみると、あたかも自分専用のメモリが確保されているかのように見える

  2. プロセスをつくるときには、親プロセスをfork(システムコールの名前、意味としてはcopy)して、子プロセスがつくられる。このとき、子プロセスは独自の仮想メモリを割り当てられる。

process_graffle.png

1__vagrant_10____ssh_.png

また、そもそもLinux カーネル自体もプログラムなので、普段psコマンドで見えてるものの実態は、

linuxの中に定義された構造体のリストです。


Threadはあとで追加された

前述のとおり、Processを作るときには、親プロセスのすべての情報が子プロセスに引き継がれ、さらに子プロセス用に仮想メモリを確保されるので、比較的重い処理になります。

というので、仮想メモリ部分などの共有できるところは親と共有で、もっと軽量な実行単位がほしい!

ということで、Threadという概念が作られました。

とはいえ、linuxの実装上は完全にProcess == Threadというのは正です。

このあたりが紛らわしいのですが、同じ構造体なのですが、buildするときにメモリ空間をコピーするかなどのフラグを渡すことで、threadを実現しています。

参考文献を読むとイメージがつかめると思います


並行と並列の違い

ただの概念(言葉の意味)の確認です。

コンピュータの話で並行と並列というのは、CPUがどんな様子で仕事をするのか、と捉えます。

CPUのcoreが1つだけの場合、並列処理というのはありえません。


並行(concurrent)

ある1つの時点では、1つの仕事しかしていないが、複数の仕事間を切り替えることによって、同時にやっているように見えること。

これは、速くするとかいうより、単純に同時にやることあるいは他を待たせないことが目的。


並列(pararell)

ある1つの時点で、実際に、物理的に、複数の仕事をしていること。

これは、速くすることが目的。

process_graffle.png

上の図で、仕事1,仕事2,仕事3は、それぞれ違うアプリケーションから来た仕事の場合もあるし、

おなじアプリケーションから来た仕事の場合もある。

一般に並行/並列プログラミングとかいう場合は、後者の場合を指している。


一般的な実現方法

ある特定のプログラミング言語とかではなく、一般的にどういう手法があるかという話。

加えてイベント駆動というのもあるらしい、それらのハイブリッド(nginx的な)もあるらしいのだが、

ここでは無視します。

手法
開発
メモリ
通信

マルチプロセス(multi process)で実行する
簡単(安全)
プロセスごとにアドレス空間が必要
違うプロセスなのでIPC

マルチスレッド(multi thread)で実行する
難しい(アドレス空間が共有されてることを意識しないといけない)
スレッドは同一のアドレス空間を共有
メモリを共有しているので直接アクセスできる

一般的にマルチスレッドのほうがマルチプロセスより開発が難しいけど、軽量で速い、といえる。


並列処理で、どういうときにパフォーマンスがあがるのか(理論)

アムダールの法則というものがあるみたいです。

アムダールの法則_-_Wikipedia.png

グラフ

つまり、、、言われてみれば当然のことなのですが


  • 並列化できる割合を大きくしないと、高速化されない

  • 高速化にも限界がある

ということですね!


並列処理で、どういうときにパフォーマンスがあがるのか(実験)

下記のような処理を書いていくつかやってみたいと思います!


  • 1000個のhtmlをダウンロードする

  • MD5で100万個のハッシュ値を計算する

実行環境

1__vagrant_10__vagrant_parallel__ssh_.png


ruby


1000個のhtmlをダウンロードする

require "benchmark"

require "open-uri"
require "securerandom"

Benchmark.bm 10 do |r|
r.report "normal" do
1000.times do |i|
html = open("https://dev.to")
open("tmp/#{SecureRandom.uuid}.html", "w") do |file|
file.write html.read
end
end
end

r.report "threads" do
threads = (1..4).to_a.map {|i|
Thread.fork {
250.times do |i|
html = open("https://dev.to")
open("tmp/#{SecureRandom.uuid}.html", "w") do |file|
file.write html.read
end
end
}
}
threads.map(&:join)
end

r.report "processes" do
processes = (1..4).to_a.map {|i|
Process.fork {
250.times do |i|
html = open("https://dev.to")
open("tmp/#{SecureRandom.uuid}.html", "w") do |file|
file.write html.read
end
end
}
}
Process.waitall
end
end

# bench mark

user system total real
normal 14.966190 6.960724 21.926914 ( 51.650528)
threads 15.563185 4.871977 20.435162 ( 20.309586)
processes 0.000000 0.015060 29.170730 ( 15.762888)

# stat(mpstatコマンド)

# single process single thread
12:06:11 PM CPU %usr %nice %sys %iowait %irq %soft %steal %guest %gnice %idle
12:06:21 PM all 6.88 0.00 2.80 0.00 0.00 0.47 0.00 0.00 0.00 89.86
12:06:21 PM 0 14.82 0.00 3.21 0.00 0.00 0.10 0.00 0.00 0.00 81.87
12:06:21 PM 1 0.00 0.00 0.40 0.00 0.00 0.00 0.00 0.00 0.00 99.60
12:06:21 PM 2 0.10 0.00 0.10 0.00 0.00 0.00 0.00 0.00 0.00 99.80
12:06:21 PM 3 13.33 0.00 7.87 0.00 0.00 1.97 0.00 0.00 0.00 76.83

# multi thread
12:03:11 PM CPU %usr %nice %sys %iowait %irq %soft %steal %guest %gnice %idle
12:03:21 PM all 18.20 0.00 5.27 0.00 0.00 0.76 0.00 0.00 0.00 75.76
12:03:21 PM 0 29.25 0.00 6.97 0.00 0.00 0.00 0.00 0.00 0.00 63.78
12:03:21 PM 1 15.31 0.00 4.52 0.00 0.00 0.00 0.00 0.00 0.00 80.16
12:03:21 PM 2 11.82 0.00 3.36 0.00 0.00 0.00 0.00 0.00 0.00 84.81
12:03:21 PM 3 16.74 0.00 6.25 0.00 0.00 3.24 0.00 0.00 0.00 73.77

# multi process
12:04:21 PM CPU %usr %nice %sys %iowait %irq %soft %steal %guest %gnice %idle
12:04:31 PM all 35.86 0.00 5.99 0.00 0.00 2.01 0.00 0.00 0.00 56.15
12:04:31 PM 0 46.06 0.00 6.08 0.00 0.00 0.53 0.00 0.00 0.00 47.33
12:04:31 PM 1 36.13 0.00 6.30 0.00 0.00 0.21 0.00 0.00 0.00 57.35
12:04:31 PM 2 28.94 0.00 4.88 0.00 0.00 0.21 0.00 0.00 0.00 65.98
12:04:31 PM 3 32.35 0.00 6.67 0.00 0.00 7.47 0.00 0.00 0.00 53.51


MD5で1000万個のハッシュ値を計算する

require "benchmark"

require 'digest/md5'
require "securerandom"

Benchmark.bm 10 do |r|
r.report "normal" do
10000000.times do |i|
Digest::MD5.hexdigest("aa")
end
end

r.report "threads" do
threads = (1..4).to_a.map {|i|
Thread.fork {
2500000.times do |i|
Digest::MD5.hexdigest("aa")
end
}
}
threads.map(&:join)
end

r.report "processes" do
processes = (1..4).to_a.map {|i|
Process.fork {
2500000.times do |i|
Digest::MD5.hexdigest("aa")
end
}
}
Process.waitall
end
end

# bench mark

user system total real
normal 11.072673 0.039019 11.111692 ( 11.120313)
threads 11.379838 0.028152 11.407990 ( 11.412710)
processes 0.000000 0.005396 23.436752 ( 6.241337)

# single process single thread
12:43:59 PM CPU %usr %nice %sys %iowait %irq %soft %steal %guest %gnice %idle
12:44:00 PM all 9.06 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 90.94
12:44:00 PM 0 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 100.00
12:44:00 PM 1 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 100.00
12:44:00 PM 2 0.00 0.00 0.99 0.00 0.00 0.00 0.00 0.00 0.00 99.01
12:44:00 PM 3 100.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00

# multi thread
12:44:05 PM CPU %usr %nice %sys %iowait %irq %soft %steal %guest %gnice %idle
12:44:06 PM all 12.72 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 87.28
12:44:06 PM 0 19.51 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 80.49
12:44:06 PM 1 25.33 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 74.67
12:44:06 PM 2 11.24 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 88.76
12:44:06 PM 3 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 100.00

# multi process
12:44:17 PM CPU %usr %nice %sys %iowait %irq %soft %steal %guest %gnice %idle
12:44:18 PM all 95.36 0.00 0.00 0.00 0.00 4.64 0.00 0.00 0.00 0.00
12:44:18 PM 0 95.00 0.00 0.00 0.00 0.00 5.00 0.00 0.00 0.00 0.00
12:44:18 PM 1 94.92 0.00 0.00 0.00 0.00 5.08 0.00 0.00 0.00 0.00
12:44:18 PM 2 96.67 0.00 0.00 0.00 0.00 3.33 0.00 0.00 0.00 0.00
12:44:18 PM 3 91.67 0.00 1.67 0.00 0.00 6.67 0.00 0.00 0.00 0.00


参考文献

https://unix.stackexchange.com/questions/364660/are-threads-implemented-as-processes-on-linux

https://stackoverflow.com/questions/200469/what-is-the-difference-between-a-process-and-a-thread

http://archive.linux.or.jp/JF/JFdocs/The-Linux-Kernel-4.html

http://www.informit.com/articles/article.aspx?p=370047&seqNum=3

https://linuxjm.osdn.jp/html/LDP_man-pages/man2/clone.2.html

https://ja.wikipedia.org/wiki/%E3%82%A2%E3%83%A0%E3%83%80%E3%83%BC%E3%83%AB%E3%81%AE%E6%B3%95%E5%89%87