差分

;調べてみよう:個々のプロセスのデータ構造は[http://ucuc2.h2np.net/srcmisc/codes/sched_h .html sched.h]に定義されている[http://ucuc2.h2np.net/srcmisc/codes/sched_h.html#N1228 struct task_struct]です。個々のプロセスが保持する情報(とリソース)にはどのようなものがあるかチェックしてみよう。

Brown Univ米ブラウン大学の [https://cs.のブラウンスレッド、brown.edu/research/pubs/techreports/reports/CS-96-18.html Brown Thread Package (BTP)]、サンマイクロシステムズのLWP (Lightweiht ProcessLight-weight process)、DECのCMA スレッド、、DECのDECthreads、

LinuxカーネルではTASK_RUNNING、TASK_INTERRUPTIBLE、 TASK_UNINTERRUPTIBLE、 TASK_STOPPEDなどの状態をもちますが、詳しくはヘッダファイルの [httphttps://ucuc2.h2np.net/src/sched_h.html#N187 N197 sched.h] を参照してください。

;調べてみよう: コマンドuptimeのマニュアルを調べてみよう。またロードアベレージの意味も調べてみよう。コマンド[http://man7.org/linux/man-pages/man1/uptime.1.html uptime]のマニュアルを調べてみよう。またロードアベレージの意味も調べてみよう。

<tt><PREpre class="bash">

現在80プロセスが動いていて、待機中75、実行中5、終了待ち0、ストップ0です。 このコンピュータでは現在80プロセスが動いていて、待機中75、実行中5、終了待ち0、ストップ0です。

;調べてみよう:プロセスの状態を表しているSTATの欄をみるとR/S/D/Z/Tの後ろにさらに文字がついていますがこの意味は何でしょうか?

;調べてみよう: コマンドpstreeを使って、すべてのプロセスの親子関係がどうなっているかチェックしてみよう。コマンド [http://man7.org/linux/man-pages/man1/pstree.1.html pstree]を使って、すべてのプロセスの親子関係がどうなっているかチェックしてみよう([[pstreeの出力例]])。

プロセスの生成はforkプロセスの生成は[http://man7.org/linux/man-pages/man2/fork.2.html fork(2)]を使い親プロセスが子プロセスを生み出します。下のコードを見て下さい。

<CODEsyntaxhighlight lang='C' line="1" > #include <unistd.h>　 #include <stdlib.h> #include <sys/types.h> #include <sys/wait.h> #include <stdio.h> void main(){

if ( pid == -1 ){ exit(EXIT_FAILURE); }

} </CODEsyntaxhighlight >

<CODEpre class="bash">

</CODEpre>

 <CODEsyntaxhighlight lang='C' line="1" > 1 #include <unistd.h> 2 main() { 3 if ( fork() == 0 ) { 4 execl("/bin/date","/bin/date",NULL); 5 } wait(); 6 }</CODEsyntaxhighlight> 

<codepre class="bash">

</codepre>

プロセスにCPU資源をどのように与えるかの順番を決めるスケジュール (schedule)ことを行うことがスケジューリング(scheduling)です。それを司るのがスケジュラです。それを司るのがスケジューラ(scheduler)です。

* FIFO 独自優先順位 ( SCHED_OTHER ) : 最初に入ったプロセスが終了するまでそのプロセスが専有する方式。最初に入ったものが最初に出るのでFirst-In-First-Out / FIFOと呼ばれる。 実行に使用した時間の違いなどにより優先順位をつけるなどし、その優先順位に従って割り当てる方式。(Linuxデフォルト)

* RR : ラウンドロビンFIFO ( Round RobinSCHED_FIFO ) : 一定の間隔で順繰りに回ってくる)でプロセスが割り当てられる方式。最初に入ったプロセスが終了するまでそのプロセスが専有する方式。最初に入ったものが最初に出るのでFirst-In-First-Out / FIFOと呼ばれる。

* 独自優先順位RR ( SCHED_RR ) : 実行に使用した時間の違いなどにより優先順位をつけるなどし、その優先順位に従って割り当てる方式。ラウンドロビン(LinuxデフォルトRound Robin: 一定の間隔で順繰りに回ってくる)でプロセスが割り当てられる方式。

* バッチ( SCHED_BATCH ): （たとえば大量の処理をしても）プライオリティの変化をつけない。尚、当然ながらタイムシェアリングシステムにおいてのバッチという意味である。 * アイドル ( SCHED_IDLE ): CPUがアイドリング状態になった時に処理が行われる。  独自優先順位は、何らかの評価方式でCPUに割り当てる優先度や割り当てる時間を決めて順番を決める方式です。何らかという通り、色々な方法があって、オペレーティングシステムの違いによって異なりますし、あるいは同じカーネルであってもバージョンの違いによっても異なります。

;補足: 筆者の知る範囲では大体においてラウンドロビン方式と優先順位づけなどを併用しているので、完全に公正で総当たりするようなラウンドロビン方式というのを見たことがありません。筆者の知る範囲ではラウンドロビン方式と優先順位づけなどを併用しているので、単純に順番を待つだけのラウンドロビン方式というのを見たことがありません。

Linux 2.6系におけるスケジューラーは以前26系におけるスケジューラは以前2.4系で使われていたスケジューラーからみると画期的に性能がいいO4系で使われていたスケジューラからみると画期的に性能がいい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 3.14ではデットライン・スケジューラのアルゴリズムはEarliest Deadline First (EDF)を採用していましたが、Linux 4.13 (2017/9/5リリース)からはEDFを改良しさらに Constant Bandwidth Server ( CBS ) 加えた [https://uc2.h2np.net/src/deadline_c.html#N1 ( と、カーネルのコメントでは表現している ）] アルゴリズムを採用しています。  カーネルにどのスケジューラを入れるかはディストリビューションによって異なりますし、またカーネルのバージョンによっても違ってきます。どのようなスケジューリングが可能かを簡単に調べるのにはコマンド [[chrt]] が便利です。 <pre class="bash">$ uname -r4.4.0-134-generic$ sudo chrt -mSCHED_OTHER min/max priority : 0/0SCHED_FIFO min/max priority : 1/99SCHED_RR min/max priority : 1/99SCHED_BATCH min/max priority : 0/0SCHED_IDLE min/max priority : 0/0</pre>

O(1)スケジュラがヒューリスティック（発見的）にスケジューリングしていたのに対し、CFS スケジューラがヒューリスティック（発見的）にスケジューリングしていたのに対し、CFS のスケジューリングは（数学的な意味で）数値を計算してスケジューリングを決めます。

それまでの Linux のスケジューラーは、タスクを管理するキューをもち、その中で処理をしていました。CFSでは平衡2分探索木の一種であるのスケジューラは、タスクを管理するキューをもち、その中で処理をしていました。CFSでは平衡2分探索木の一種である

CFS スケジュラに関しての評価<ref>Benchmarking CFS　http://kerneltrap.org/Linux/Benchmarking_CFS</ref>を見ていると安定したスケジューリングを実現しており良い結果を残しているようです。  今後もある意味オペレーティングシステムの心臓部ともいえるスケジューラーが色々な要件を満たすため、今後もある意味オペレーティングシステムの心臓部ともいえるスケジューラが色々な要件を満たすため、

生成可能な最大スレッド数は利用しているシステムのメモリ量に依存します。/proc/sys/kernel/threads-max を参照することでわかります。 * fork版 <syntaxhighlight lang='C' line="1" >#include <sys/types.h> #include <unistd.h> #include <stdio.h> main() { int i; for(i=0;i<1000;i++) { if ( fork() == 0 ) { fprintf(stderr,"."); _exit(0); } wait(); } printf("%d\n",i); }</syntaxhighlight><pre class="bash">

* thread版 <syntaxhighlight lang='C' line="1" >#include <pthread.h> #include <stdlib.h> #include <stdio.h> void *func() { fprintf(stderr,"."); } int main(void) { pthread_t t; int i; for(i=0 ; i < 1000 ; i++) { pthread_create(&t,NULL,func,NULL); pthread_join ( t, NULL ); } printf("%d\n",i); }</syntaxhighlight><pre class="bash">

* 出力  <pre class="bash">

 [[File:Process-sched.png|thumb|left|300px|プロセスが複数の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|150px|こんな計算を仮定してみる。]]例えば、配列 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>へ移動しました。