この資料の背景

社内向け勉強会で並行処理と並列処理というテーマで発表しようとしたら、
OSの役割や仕組みなどを理解しないといけなくなったので、それらも込でまとめた資料になります。
調べてみて、まだまだ分からないところがたくさんあるので、これからも継続的に勉強していきたいです。

(前提) ProcessとThread

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

Processしかなかった時代

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

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

仕事をするには、そのためのリソース(CPUリソースや、メモリリソース)が必要です。
なのでこういうリソースも含めた仕事するために必要な塊がProcessです。

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

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

物理メモリはOS(カーネル)によって仮想メモリに分割されており、一つ一つのプロセスからみると、あたかも自分専用のメモリが確保されているかのように見える
プロセスをつくるときには、親プロセスをfork(システムコールの名前、意味としてはcopy)して、子プロセスがつくられる。このとき、子プロセスは独自の仮想メモリを割り当てられる。

また、そもそもLinux カーネル自体もプログラムなので、普段psコマンドで見えてるものの実態は、
linuxの中に定義された構造体のリストです。

Threadはあとで追加された

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

というので、仮想メモリ部分などの共有できるところは親と共有で、もっと軽量な実行単位がほしい!
ということで、Threadという概念が作られました。

とはいえ、linuxの実装上は完全にProcess == Threadというのは正です。
このあたりが紛らわしいのですが、同じ構造体なのですが、buildするときにメモリ空間をコピーするかなどのフラグを渡すことで、threadを実現しています。

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

並行と並列の違い

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

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

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

並行(concurrent)

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

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

並列(pararell)

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

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

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

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

一般的な実現方法

ある特定のプログラミング言語とかではなく、一般的にどういう手法があるかという話。
加えてイベント駆動というのもあるらしい、それらのハイブリッド(nginx的な)もあるらしいのだが、
ここでは無視します。

|手法|開発|メモリ|通信|
|---|---|---|---|---|
|マルチプロセス(multi process)で実行する|簡単(安全)|プロセスごとにアドレス空間が必要|違うプロセスなのでIPC|
|マルチスレッド(multi thread)で実行する|難しい(アドレス空間が共有されてることを意識しないといけない)|スレッドは同一のアドレス空間を共有|メモリを共有しているので直接アクセスできる|

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

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

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

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

並列化できる割合を大きくしないと、高速化されない
高速化にも限界がある

ということですね!

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

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

1000個のhtmlをダウンロードする
MD5で100万個のハッシュ値を計算する

実行環境

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