差分
/* プロセスの基本的概念 */
プログラムが動作する実行実体のことをプロセスと呼びます。
単純化して説明すると、プログラムの実行のことです。
プロセスはプロセスごとにプロセスIDを付与され、その数字で管理されています。
このプロセスIDの数字は[[プロセスIDを擬似乱数生成関数の初期化パラメータに使う是非 | 一定の数字で循環]]します。
Linuxカーネルが扱えるプロセスIDの最大値は/proc/sys/kernel/pid_maxを参照すればわかりますが、
一般向けのLinuxディストリビューションであれば現状ではプロセスIDの最大値は 2^15 (32768) となっています。
それで説明が終わるのはあんまりなので、もうちょっと概念的にどのような位置づけなのか考えてみます。
スレッドやタスクの考え方（と、実装）は80年代にUNIXに入って来た、UNIXの歴史から見ると、わりと新しい技術です。
80年代に入ってから色々な組織がスレッドの実装を試みました。
CMUのCスレッドパッケージがありました。各々互換性はありません。
紆余曲折あり、現在ではPOSIX仕様のスレッドである[http://man7.org/linux/man-pages/man7/pthreads.7.html pthreads(7)]が主流になっています。
ですから、単純にプロセスと呼んでも構わないですし、
また同時に（ここまでの説明の範囲では）「プロセス＝タスクのこと」と考えてもかまいません。
このあたりは新旧の考え方が入り乱れて呼び方が混乱しているのは確かなようです。
UNIXが生まれた当時の処理の粒度と今時のUNIXでの処理の粒度は違うので、
;調べてみよう: コマンドuptimeのマニュアルを調べてみよう。またロードアベレージの意味も調べてみよう。コマンド[http://man7.org/linux/man-pages/man1/uptime.1.html uptime]のマニュアルを調べてみよう。またロードアベレージの意味も調べてみよう。
=== プロセスの状態 ===
親プロセスが子プロセスを生むという形を取り、子プロセスは親プロセスのコピーとして動き始めます。例外はすべてのプロセスの始まりであるinitだけです。
;調べてみよう: コマンドpstreeを使って、すべてのプロセスの親子関係がどうなっているかチェックしてみよう。コマンド [http://man7.org/linux/man-pages/man1/pstree.1.html pstree]を使って、すべてのプロセスの親子関係がどうなっているかチェックしてみよう([[pstreeの出力例]])。
==== fork(2) ====
プロセスにCPU資源をどのように与えるかの順番を決めるスケジュール (schedule)ことを行うことがスケジューリング(scheduling)です。それを司るのがスケジュラです。それを司るのがスケジューラ(scheduler)です。
==== 基本的なスケジュリング方式 基本的なスケジューリング方式 ====
スケジューリングの方式にはポリシーと呼ばれる、いくつかの方式があります。
Linux 2.6系におけるスケジューラーは以前26系におけるスケジューラは以前2.4系で使われていたスケジューラからみると画期的に性能がいいO(1)スケジュラスケジューラ(Order one scheduler)に変更されました。さらにLinux 2.6.23からO(1)スケジュラからCFSスケジューラからCFS(Completely Fair Scheduler)に変更されました。
その後 Linux 3.14 (2014/3/20リリース) から からリアルタイム指向の処理に必要なデットラインを処理するための [https://core.ac.uk/download/pdf/14699805.pdf SCHED_DEADLINE がスケジュラ ] がスケジューラ <ref> デフォルトで使えるかどうかはディストリビューションによります。</ref> に加わっています。これはリアルタイム処理に対して効果的に働くスケジューラです。Linux に加わっています。Linux 3.14ではデットライン・スケジュラーのアルゴリズムはEarliest 14ではデットライン・スケジューラのアルゴリズムはEarliest Deadline First (EDF)を採用していましたが、Linux 4.13 (2017/9/5リリース)からはアルゴリズムがEDFを改良しさらに からはEDFを改良しさらに Constant Bandwidth Server ( CBS ) 加えてたものを採用しています<ref>カーネルのソースコードdeadline加えた [https://uc2.cでは 採用しているアルゴリズムを EDF + CBS という表現をしています<h2np.net/ref>。src/deadline_c.html#N1 ( と、カーネルのコメントでは表現している ）] アルゴリズムを採用しています。
</ref>
は、
O(1)スケジュラがヒューリスティック（発見的）にスケジューリングしていたのに対し、CFS スケジューラがヒューリスティック（発見的）にスケジューリングしていたのに対し、CFS のスケジューリングは（数学的な意味で）数値を計算してスケジューリングを決めます。
ヒューリスティックな方法では、ある種の特定の条件に嵌まってしまいスケジューリングが公平に処理できなくなったり、あるいは偶然に有利な条件になったり不利な条件になったりとする可能性があります。
それに比べCFSは公平にスケジューリングされます。
それまでの Linux のスケジューラーは、タスクを管理するキューをもち、その中で処理をしていました。CFSでは平衡2分探索木の一種であるのスケジューラは、タスクを管理するキューをもち、その中で処理をしていました。CFSでは平衡2分探索木の一種である
赤黒木
<ref>
あるいはさらなる効率化のために変更される可能性は十分にあります。
これからも、あちらこちらの腕利きのカーネルハッカーがどんどん新しい提案をしてくることでしょう。
スレッドは計算資源を共有しCPU資源だけは別の状態であるような処理の流れをいいます。スレッドにはclone(2)のようなカーネルレベルで実行するスレッドとglibcなどユーザライブラリに含まれているユーザレベルで実行するスレッドの2つがあります。ですからスレッドが必ずしもカーネルモードで動作しているわけではなく、それはプログラムの書かれ方によります。ここの説明ではカーネルスレッドとユーザスレッドとの両方取り上げてみます。
既に説明した通りfork(2)が親と子のプロセスで内容をコピーしているのですが、とはいえ fork(2) 後は各々の実体は独立しています。しかし、スレッドは内容が一緒ですから、つまり処理の流れを別に持つCPU資源だけは複数個持つのですから、新しいプロセスが生まれていないので親も子もありません。CPU資源以外の計算資源のコピーが必要ない場合、あるいは同じ計算資源でCPU 資源を複数持ちたい時、計算資源を共有したい時などにスレッドは便利です。
CPUリソースだけを同時に複数個持つことができることで、たとえば実行しているタスク中でネットワーク入出力からの処理を行いつつ同時に他の計算を繰り返すような場合に非常に有効に働きができます。
この利点は、資源コピーが発生しないまま処理スレッドだけを高速に立ち上げることができると説明しましたが実際にfork(2)とLinuxのpthreadライブラリ(カーネルスレッドではなくユーザスレッド)を使ってどれぐらい違うか試してみました。
1000 回プロセスを生成するのとスレッドを生成するプログラムを書いてみます。結果はAthlon 1GHzマシンでスレッド生成側がトータル0.157秒、プロセス生成側が0.360秒と2倍以上の差をつけました。このようにCPUリソースのみだけで処理が出来るようなものを大量に生成するような場合はスレッドが有利に働きます。
生成可能な最大スレッド数は利用しているシステムのメモリ量に依存します。/proc/sys/kernel/threads-max を参照することでわかります。
* fork版
=== マルチプロセッサとプロセス ===
[[File:Process-sched.png|thumb|left|450px|プロセスが複数のCPUに割り当てられるマルチプロセッサとプロセス]]複数のプロセッサの話題に移りますが、ここでの複数プロセッサといってもスーパーコンピュータのように超並列とかは、この話題の範囲ではないので除外した上で話を進めます。 さて、我々が現在利用の対象としているタイプのものは、対称マルチプロセッサ(SMP: Symmetric Multi-Processor) と呼ばれるタイプのものです。SMPの特徴で覚えておかなければならない点は各々のプロセッサが各々独自の入出力を持っていないのと、そして、どのプロセッサもシステム内のすべての構成部分に対して同等にアクセスできることの2点です。 似たようなシステムに共有メモリ型マルチプロセッサ ( Shared Memory Multiprocessor )というものがありますが、SMPはメモリを共有しているので共有メモリ型マルチプロセッサと同じ意味です。ただし、狭い定義を採用すれば共有メモリ型マルチプロセッサは、メモリ資源の共有だけに定義を持っているのに対して、SMPはシステムにある構成要素のすべてに対し同等にアクセスできるという点が違うことを注意しましょう。 まずはSMPとはプロセッサの数が増えただけで、あとは構成要素を共有していると理解するのが良いでしょう。ですからSMPの良い部分は単一プロセッサと同じプログラムのモデルが使用できる点です。考えた方として単純にプロセッサが複数あると考えて構いません。単純化したスケジュールのモデルで考えてみましょう。たとえばラウンドロビンのスケジュールを用いて、CPU(ここでの説明はプロセッサと同じということで捉えてください)が1つだったのを2つにしたときを考えてみると下のようになります。 カーネルがSMPの複数CPUに対し処理を割り当てる方法はいくつかあります。それはプロセス単位での割り当てとスレッド単位の割り当てです。 ;補足: ここではプロセス (1タスク/1スレッド) と タスク ( 1タスク / 複数スレッド ) とし、前者が「プロセス単位で」、後者が「スレッド単位」でという意味です。 ある一定のデータを処理するプログラムをまず仮定します。プロセス単位で割り当てるならプログラム側はSMPを何にも意識しなくても構いません。たくさんのプロセスがスケジュールされている場合でもCPU が多い分、自分の番が回ってくる回数が増えるため負荷に強いという意味で、処理能力が向上します。CPUが1個の時に同時に2つのプロセスを動かす時の処理時間とCPUが2個の時に同時に2つのプロセスを動かす時の処理時間を比較すると、後者の方が速くなります。しかし1つのプロセスに着目してみればCPUが1個で1つのプロセスしか動いていない時の処理時間よりは速くなることがありません。 === マルチプロセッサとスレッド === スレッド単位で割り当てる場合、実行中プログラムの持つ複数のスレッドが複数のCPUに同時に割り当てられていきます。その場合はプログラムの処理のスピードは CPU 単体の最大処理速度を越えることが可能になります。ただ、それでも上手にスレッドを分割し、その処理タイミングをきちんとプログラミングできる場合という前提が満たされることが必要です。 [[File:CodeCogsEqn-2.png|thumb|left|250px|こんな計算を仮定してみる。]]例えば、配列 A = { a1, a2, a3, ... an }があって、表の値をすべて掛けたものを、表の値をすべて足したもので割るという計算をしたいとしましょう。 まず、a1 * a2 * a3 * ... * anを計算しAに代入するスレッドとa1 + a2 + a3+ ... + anを計算しBに代入するスレッドを作ります。両方のスレッドの計算の終了を待ってA/Bを計算します。この時、各々のスレッドが別々のCPUで並列に動くので1個のCPUで全部を計算させるよりも速く計算<ref>マルチスレッドを使い円周率を計算したプログラム例: http://h2np.net/pi/mt-bbp.c </ref>ができるはずです。 しかしこの場合、処理効率が単純に2倍に上がるわけではありません。たとえば1CPUでの計算に20秒かかったとしましょう。2CPU を使い分母、分子の計算が分割でき並列に計算されたとしても、もし、分子の計算が12秒かかり、分母の計算が10秒かかり、分子÷分母の計算が0.5秒かかったならば、分母の計算時間と割り算の時間を足したものがクリティカルパスですから、その処理時間は12.5秒となります。このようにCPU数が増えたからといって単純に性能がCPU数に合わせて倍数的に増えていくわけではありませんし、もちろん処理が並列化されていないプログラムをいくら走らせても当然ながらその結果はCPUを1つ占有出来ること以上の効果はありません。 ;調べよう: 並列処理一般において処理効率には上限があることを示しているのがアムダールの法則です。アムダールの法則について調べてみましょう。<ref>ジーン・アムダールが書いた1967年の論文 "[http://www-inst.eecs.berkeley.edu/~n252/paper/Amdahl.pdf http://www-inst.eecs.berkeley.edu/~n252/paper/Amdahl.pdf]" が公開されています。ここに書かれている並列計算の遅滞に関する内容が後にアムダールの法則と呼ばれるようになります。</ref>へ移動しました。
=== 脚注 ===
