「プロセス管理」の版間の差分

提供：UnixClassWiki
ナビゲーションに移動 検索に移動
← 古い編集
 
(同じ利用者による、間の106版が非表示)
2行目: 2行目:




プログラムが動作する実行実体のことをプロセスと呼びます。
プログラムが動作する実行実体のことをプロセスと呼びます。単純化して説明すると、プログラムの実行のことです。
単純化して説明すると、プログラムの実行のことです。
 
それで説明が終わるのはあんまりなので、もうちょっと概念的にどのような位置づけなのか考えてみます。
 
プロセスはプロセスごとにプロセスIDを付与され、その数字で管理されています。
このプロセスIDの数字は[[プロセスIDを擬似乱数生成関数の初期化パラメータに使う是非 | 一定の数字で循環]]します。
Linuxカーネルが扱えるプロセスIDの最大値は/proc/sys/kernel/pid_maxを参照すればわかります。
カーネルの[https://github.com/torvalds/linux/blob/master/include/linux/threads.h ソースコード]内ではプロセスIDの最大値は次のようにして設定しています。
最少構成でカーネルを作った場合は4096、32ビットCPUだと32768、64ビットもしくはそれ以上のCPUだと4 * 1024 * 1024つまり4194304ということになります。
 
 
<pre class="C">
/*
* This controls the default maximum pid allocated to a process
*/
#define PID_MAX_DEFAULT (CONFIG_BASE_SMALL ? 0x1000 : 0x8000)
 
/*
* A maximum of 4 million PIDs should be enough for a while.
* [NOTE: PID/TIDs are limited to 2^30 ~= 1 billion, see FUTEX_TID_MASK.]
*/
#define PID_MAX_LIMIT (CONFIG_BASE_SMALL ? PAGE_SIZE * 8 : \
        (sizeof(long) > 4 ? 4 * 1024 * 1024 : PID_MAX_DEFAULT))
 
</pre>
 
 
概念的にどのような位置づけなのかを確認してみます。




17行目: 41行目:


==== ユーザ側から見る ====  
==== ユーザ側から見る ====  
 
[[File:Program-cpu.png|thumb|right|300px|プログラムは自分専用CPUを持っているように見える]]


ユーザ側の視点から見てみましょう。
ユーザ側の視点から見てみましょう。
25行目: 49行目:




;補足: 話を単純化するために、ここではマルチコアとかハイパースレティングなどの能力も持っていない単純なCPUとします。
;補足: 話を単純化するために、ここではマルチコアとかハイパースレティングなどの能力も持っていない単純な1つの計算ユニットだけあるCPUとします。




これをプログラム側の視点から見てみましょう。この時、πを求めている各々のプログラムは、他にどんなプログラムが同時に動作しているのか意識することはありません。プロセスは自分専用のCPUを持っているように見えています。
これをプログラム側の視点から見てみましょう。
この時、πを求めている各々のプログラムは、他にどんなプログラムが同時に動作しているのか意識することはありません。
プロセスは自分専用のCPUを持っているように見えています。


プログラムA <===> CPUリソース
プログラムB <===> CPUリソース
プログラムC <===> CPUリソース


もう一度ユーザ側視点に戻って、この状態を見てみると、
もう一度ユーザ側視点に戻って、この状態を見てみると、
41行目: 63行目:


==== カーネル側から見る ====  
==== カーネル側から見る ====  
[[File:Process-resource.png|thumb|right|350px|プロセスは色々なリソースを持っている]]




47行目: 71行目:
ある一瞬においては1つの物理的なCPUを専有できるのは1つのプログラムだけです。
ある一瞬においては1つの物理的なCPUを専有できるのは1つのプログラムだけです。
また、その実行のためにCPUリソース以外にも必要なリソースも割り当てられています。
また、その実行のためにCPUリソース以外にも必要なリソースも割り当てられています。
この時、この割り当てられたリソースを使って実行する主体をプロセスと呼ぶことができます。
プログラムの実行 (=プロセス) = [
  [CPUリソース]
  [必要なリソース]
  [必要なリソース]
  ....
]
実行中プロセスの持つリソースを分類すると次のようになります。
実行中プロセスの持つリソースを分類すると次のようになります。
* CPUリソース (タスク系リソース)
* CPUリソース (タスク系リソース)
* プロセス間通信系リソース
* プロセス間通信系リソース
68行目: 77行目:
* ファイル管理系リソース
* ファイル管理系リソース
* ユーザ管理系リソース
* ユーザ管理系リソース
* ほか




;調べてみよう:個々のプロセスのデータ構造はsched.hに定義されているstruct task_structです。。個々のプロセスが保持する情報(とリソース)にはどのようなものがあるかチェックしてみよう。
これらの割り当てられたリソースを使って実行する主体をプロセスと呼ぶことができます。
 
 
 
;調べてみよう:個々のプロセスのデータ構造は[https://github.com/torvalds/linux/blob/master/include/linux/sched.h sched.h]に定義されている[https://github.com/torvalds/linux/blob/master/include/linux/sched.h#L723  struct task_struct]です。個々のプロセスが保持する情報(とリソース)にはどのようなものがあるかチェックしてみよう。




76行目: 90行目:
さて、今度はプロセスを実際にCPUに割り当てていくことを考えてみましょう。
さて、今度はプロセスを実際にCPUに割り当てていくことを考えてみましょう。
プロセスを割り当てるためにスケジュール（予定）を立て処理を進めていく必要があります。
プロセスを割り当てるためにスケジュール（予定）を立て処理を進めていく必要があります。
それがスケジュリングです。
それがスケジューリングです。
スケジュリングを説明するまえに、もう少しプロセスをみてみましょう。
スケジューリングを説明するまえに、もう少しプロセスをみてみましょう。


=== プロセス・タスク・スレッド ===  
=== プロセス・タスク・スレッド ===  
87行目: 101行目:


* スレッド実行に必要なすべてのリソースのすべてを指してタスク
* スレッド実行に必要なすべてのリソースのすべてを指してタスク


* リソース中でCPUリソースとして処理の流れを作るものをスレッド
* リソース中でCPUリソースとして処理の流れを作るものをスレッド


* １つのタスクに１つのスレッドしかないものをプロセス
* １つのタスクに１つのスレッドしかないものをプロセス
96行目: 108行目:


スレッドやタスクの考え方（と、実装）は80年代にUNIXに入って来た、UNIXの歴史から見ると、わりと新しい技術です。
スレッドやタスクの考え方（と、実装）は80年代にUNIXに入って来た、UNIXの歴史から見ると、わりと新しい技術です。
80年代に入ってから色々な組織がスレッドの実装を試みました。
米ブラウン大学の [https://cs.brown.edu/research/pubs/techreports/reports/CS-96-18.html Brown Thread Package (BTP)]、
サンマイクロシステムズのLWP (Light-weight process)、DECのDECthreads、
[https://kilthub.cmu.edu/articles/journal_contribution/C_threads/6603980/1 CMUのCスレッドパッケージ]
がありました。各々互換性はありません。
紆余曲折あり、現在では
[https://hpc-tutorials.llnl.gov/posix/ POSIX仕様のスレッド]である
[http://man7.org/linux/man-pages/man7/pthreads.7.html pthreads(7)]
が主流になっています。
タスクが1つのスレッドしか持たない時、これはUNIX の伝統的な実行実体のプロセスです。
タスクが1つのスレッドしか持たない時、これはUNIX の伝統的な実行実体のプロセスです。
ですから、単純にプロセスと呼んでも構わないですし、
ですから、単純にプロセスと呼んでも構わないですし、
また同時に（ここまでの説明の範囲では）「プロセス＝タスクのこと」と考えてもかまいません。
また同時に（ここまでの説明の範囲では）「プロセス＝タスクのこと」と考えてもかまいません。
タスクは複数のスレッドを持つことができます。このような状態の場合は、プロセスと呼ぶよりタスクと呼ぶ方が適切でしょう。
タスクは複数のスレッドを持つことができます。複数のスレッドが動き出すまでは、プロセスといってもいいわけですが、
スレッドを複数持つ状態の場合は、プロセスと呼ぶよりタスクと呼ぶ方が適切でしょう。
このあたりは新旧の考え方が入り乱れて呼び方が混乱しているのは確かなようです。
UNIXが生まれた当時の処理の粒度と今時のUNIXでの処理の粒度は違うので、
UNIXが生まれた当時の処理の粒度と今時のUNIXでの処理の粒度は違うので、
これから先はプロセスという言葉は廃れてタスクという言い方が主流になるかも知れません。
これから先はプロセスという言葉は廃れてタスクという言い方が主流になるかも知れません。
107行目: 132行目:


=== プロセスの状態 ===
=== プロセスの状態 ===
 
[[File:Process-flow.png|thumb|right|480px|プロセス・ステータスの流れ]]
オペレーティングシステムは実行すべき、たくさんのプロセスを同時に抱え込んでいるわけですが、それよりも少ない数のCPUでどうにかこうにか、やりくりしなければいけません。
オペレーティングシステムは実行すべき、たくさんのプロセスを同時に抱え込んでいるわけですが、それよりも少ない数のCPUでどうにかこうにか、やりくりしなければいけません。






そこでプロセスの状態に着目して、その動きを見てみましょう。
まずプロセスの状態に着目して、その動きを見てみましょう。
その前にLinuxのタスクの状態遷移を細かく追っていくと、初心者にとって処理の流れの全体像がわかりづらくなると思います。
その前にLinuxのタスクの状態遷移を細かく追っていくと、初心者にとって処理の流れの全体像がわかりづらくなると思います。
そこでここでは説明は必ずしもLinuxそのままというわけではない
そこでここでは説明は理解しやすいようにLinuxそのままではなく
<ref>
<ref>
LinuxカーネルではTASK_RUNNING、TASK_INTERRUPTIBLE、 TASK_UNINTERRUPTIBLE、 TASK_STOPPEDなどの状態をもちますが、詳しくはinclude/linux/sched.hを参照してください。
LinuxカーネルではTASK_RUNNING、TASK_INTERRUPTIBLE、 TASK_UNINTERRUPTIBLE、 TASK_STOPPEDなどの状態をもちます。詳しくはヘッダファイルの [https://github.com/torvalds/linux/blob/master/include/linux/sched.h#L82 sched.h] を参照してください。
</ref>
</ref>
ですが、
ある程度単純化したプロセス状態の基本モデルを考えて説明したいと思います。
理解しやすいプロセス状態の基本モデルを考えて説明したいと思います。
さて、次の6つの状態を持つモデルを考えます。
 


ここでのプロセスを説明するために5つの状態を持つモデルを考えます。


* (1) 実行中(RUNNING): プロセスがCPUを使用し実行している状態
* (1) 実行中(RUNNING): プロセスがCPUを使用し実行している状態
132行目: 155行目:
**  UNINTERRUPTIBLE: 解除されない限りSLEEP状態になっている
**  UNINTERRUPTIBLE: 解除されない限りSLEEP状態になっている


* (4) 新しいプロセス生成(FORK): fork(2)で新しいプロセスが生成される状態
* (4) 新しいプロセス生成(NEW): 新しいプロセスを作る状態


* (5) 終了待ち (ZOMBIE) : プロセスの終了処理を待っている状態
* (5) 終了待ち (ZOMBIE) : プロセスの終了処理を待っている状態


* (6) 停止 (STOPPED) :  プログラムを一時的に停止させる
* (6) 停止 (STOPPED) :  プログラムを一時的に停止させている状態




  終了待ち
    ^
    |    ---A-->
  実行中 <--B--- 待機中<-----+<--- 新しいプロセス
    |                    　|
    +---C--->イベント待ち--->+
    |                    　|
    +------>一時停止 ------>+




プログラムの状態遷移を単純化してみましょう。プログラムは生成後、消滅までのあいだ状態A、B、Cを繰り返します。
もっと単純に「待機中」「イベント待ち」「実行中」の３つの間を遷移するモデルにしましょう。動きは次のようになります。




* A : 割り当てられたCPUリソースを使ったので、CPUでの実行状態から待機状態になる。この時、CPUリソースが使える状態になれば、すぐに実行状態に戻れる。
* 実行中→待機中 : 割り当てられたCPUリソースを使ったので、CPUでの実行状態から待機状態になる。この時、CPUリソースが使える状態になれば、すぐに実行状態に戻れる。


* B : すぐにでも実行を行える状態で待っている。
* 待機中→実行中 : すぐにでも実行を行える状態で待っていて、CPUが割り当てられればすぐに実行中になる。


* C : 入力などのイベントのために待ち状態になっている。
* 実行中→イベント待ち : 入力などのイベントのために待ち状態になっている。


* イベント待ち→待機中 : 入力のようなイベントがあったので待機中になっている。




ここでのストップ / 一時停止(STOPPED)はたとえばシェル上でコントロールZを押してSIGSTOPを発生させプログラムを停止させるといった状態です。


さて先程例に出したπの計算をしている同時に3つ動かしているプログラムは、ほとんどの場合、「実行中→待機中」と「待機中→実行中」をいったり来たりしているはずです。
たまにIOのためにイベント待ちの状態になりますが、それよりもはるかにCPUを使いπの計算している時間の方が多いはずです。
待機中(READY状態)のプロセス数を示すロードアベレージは1.0を越えて徐々に増えていき最後には3.0を越えるはずです。
一方で例えばエディタのようなインタラクティブなプログラムを考えてみます。そうなると、ユーザが実際に使っている時間のほとんどは入力を待っている待機中です。ロードアベレージは1.0以下で限りなく0.0に近くなるでしょう。


さて先程例に出したπの計算をしている同時に3つ動かしているプログラムは、ほとんどの場合、遷移AとBをいったり来たりしているはずです。たまにIOのためにイベント待ちの状態になりますが、それよりもはるかにCPUを使いπの計算している時間の方が多いはずです。待機中(READY状態)のプロセス数を示すロードアベレージは1.0を越えて徐々に増えていき最後には3.0を越えるはずです。


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


=== プロセスの状態 ===
=== プロセスの状態 ===
170行目: 189行目:
皆さんが動かしているデスクトップレベルでは、いつもそんなに激しく色々なプロセスが同時にCPUを奪いあっている状態ではありません。動いているプロセスのほとんどは入力を待つSPLEEP状態です。コマンドtopを使ってプロセスの状況を見てみましょう。
皆さんが動かしているデスクトップレベルでは、いつもそんなに激しく色々なプロセスが同時にCPUを奪いあっている状態ではありません。動いているプロセスのほとんどは入力を待つSPLEEP状態です。コマンドtopを使ってプロセスの状況を見てみましょう。


 
<pre class="bash">
  % top
  % top
   18:49:03 up 49 days,  4:38,  8 users,  load average: 2.00, 0.82, 0.31
   18:49:03 up 49 days,  4:38,  8 users,  load average: 2.00, 0.82, 0.31
187行目: 206行目:
     2 root      9  0    0    0    0 SW    0.0  0.0  0:00 keventd
     2 root      9  0    0    0    0 SW    0.0  0.0  0:00 keventd
     3 root      19  19    0    0    0 SWN  0.0  0.0  0:00 ksoftirqd_CPU0
     3 root      19  19    0    0    0 SWN  0.0  0.0  0:00 ksoftirqd_CPU0
</PRE>




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




STATの部分はプロセスの状態を表しています。一文字目がプロセスの状態を示していています。
STATの部分はプロセスの状態を表しています。一文字目がプロセスの状態を示していています。


* R : RUNNING状態 (実行している、あるいは実行待ちの状態）
* R : RUNNING状態 (実行している、あるいは実行待ちの状態）
* S : SLEEP状態 (I/O待ちなどの状態)
* S : SLEEP状態 (I/O待ちなどの状態)
* D : 割込みが利かないSLEEP状態 (sleep関数を呼んでSLEEPしている状態など）
* D : 割込みが利かないSLEEP状態 (sleep関数を呼んでSLEEPしている状態など）
* Z : ゾンビ状態 (終了したがまだ親プロセスが終了処理を終えていない状態）
* Z : ゾンビ状態 (終了したがまだ親プロセスが終了処理を終えていない状態）
* T : ストップ状態 (Control-Z/SIGSTOPによるプロセス停止の状態)
* T : ストップ状態 (Control-Z/SIGSTOPによるプロセス停止の状態)




207行目: 228行目:




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




216行目: 238行目:
なぜならばコンパイラは、ファイル入出力を発生させるので、その入出力が発生している最中はイベント待ち状態になっています。ファイル入出力に10msかかったとして、その間はCPUは遊んでいる状態になります。
なぜならばコンパイラは、ファイル入出力を発生させるので、その入出力が発生している最中はイベント待ち状態になっています。ファイル入出力に10msかかったとして、その間はCPUは遊んでいる状態になります。
10msというは今日のCPUにとっては、長い長い暇な時間で、かなり大量の計算ができます。
10msというは今日のCPUにとっては、長い長い暇な時間で、かなり大量の計算ができます。
ですから前のプロセスがCPU専有時間が過ぎたので次のプロセスに順番を与える以外にも、次のプロセスがCPUを使う状態が多数発生します。
このようにプロセスがCPU専有時間が過ぎたので次のプロセスに順番を与える以外にも、他のプロセスがCPUを使う状態が数多く発生します。


=== プロセスの生成 ===
=== プロセスの生成 ===
222行目: 244行目:
親プロセスが子プロセスを生むという形を取り、子プロセスは親プロセスのコピーとして動き始めます。例外はすべてのプロセスの始まりであるinitだけです。
親プロセスが子プロセスを生むという形を取り、子プロセスは親プロセスのコピーとして動き始めます。例外はすべてのプロセスの始まりであるinitだけです。


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


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


1  #include <sys/types.h>
2  #include <unistd.h>
3  #include <stdio.h>
4  main() {
5    char *p;
6    fprintf(stderr,"we are here\n",p);
7    if ( fork() != 0 ) {
8      p="parent";
9      fprintf(stderr,"%s is here\n",p);
10  }
11  else {
12    p="child";
13    fprintf(stderr,"%s is here\n",p);
14  }
15  wait();
16  fprintf(stderr,"%s finish\n",p);
17 }


システムコールfork(2)はフォーク後、親プロセスでは子プロセスのプロセスIDを返却します。フォークができな時は-1を返却します。子プロセスの時は0を返却します。wait(2)は子プロセスの終了を待つシステムコールです。このプログラムを実行すると次のような出力になります
<pre class="C">
#include <unistd.h>
#include <stdlib.h>
#include <sys/types.h>
#include <sys/wait.h>
#include <stdio.h>
int  main(void){
  pid_t pid, wait_pid;
  int wait_stat;
  if ( (pid = fork()) == 0 ) {
    sleep(3);
    fprintf(stderr,"pid in child: %d\n",pid);
    exit(EXIT_SUCCESS);
  }
  else {
    if ( pid == -1 ) {
      exit(EXIT_FAILURE);
    }
    fprintf(stderr,"pid in parent: %d\n",pid);
    wait_pid=wait(&wait_stat);
    fprintf(stderr,"wait returns : %d(%o)\n",wait_pid,wait_stat);
    exit(EXIT_SUCCESS);
  }
  return(0);
}
</pre >


システムコールfork(2)はフォーク後、親プロセスでは子プロセスのプロセスIDを返却し、子プロセスでは0を返却します。
またフォークができない時は-1を返却します。
wait(2)は子プロセスの終了を待つシステムコールです。
このプログラムを実行すると次のような出力になります。
<pre class="bash">
  $ ./a.out  
  $ ./a.out  
  here we are
  pid in parent: 5008
parent is here
  pid in child: 0
  child is here
  wait returns : 5008(0)
  child finish
</pre>
  parent finish
   




最初は親も子もない1つのプロセスで"here we are"を出力しますが、fork(2)の時点で、2つのプロセスが出来ます。子プロセスは親プロセスのコピーで、そのまま子プロセス側の処理を行います。この時点で"child is here"が出力されます。wait(2)の部分では子プロセスは待つべきプロセスは存在しませんから、そのまま通過し"child finish"が出力されます。
最初は1つのプロセスですが、システムコールfork()を呼び出した時点で、エラーが発生しない限り2つのプロセス、つまり親と子のプロセスになります。
 
子プロセスは親プロセスのコピーで、そのまま子プロセス側の処理を行いますがsleep()があるので一旦スリープします。
 
親プロセスはそのまま続行していますから（そしてsleepしていませんから）、"pid in parent : ~ "を出力します。
親プロセスは、親プロセス側の処理を行い"parent is here"が出力されます。その下のwait(2)では子プロセスがあるので、その終了を待つ状態になります。子プロセスが終了した時点でwait(2)は処理され、次の"parent finish"の行に続きます。
システムコールwait()は子プロセスの終了を待つ機能です。そして、まだ子プロセスは終了していませんから、子プロセスの終了を待ちます。
 
子プロセスはsleepの待ち時間が過ぎれば"pid in child:~"を出力して終了します。
 
親プロセスでは子プロセスが終了したのでwaitが終了した子プロセスのidを返却します。
ポインタpを見てみましょう。親プロセスと子プロセスに別れた後は、各々のプロセス中で別々に存在し違う値をもっていていることに注意してください。
親プロセスは"wait returns : ~"を出力して終了します。
 
 
  here we are
  |
  V 親プロセス  子プロセス
fork(2) ---------+  生成
  V              |     
  parent is here  V
  |      child is here
  |              V
  V      child finish
  wait()<-------- +  消滅
  V
  parent finish




子プロセスが新しい実行ファイルを動かすにはシステムコールexecve(2)使います。これは、子プロセスの資源を新しい実行ファイルの資源として与えるものです。
新しいコマンドを動かすのもforkを使い子プロセスを生成します。具体的には子プロセスが新しい実行ファイルを動かすにはシステムコールexecve(2)使います。これは、子プロセスの資源を新しい実行ファイルの資源として与えるものです。




;補足:  プログラム中ではシステムコールexecve(2)よりもライブラリ関数execl(3)などを使う場合の方が多いでしょうが、ここでは説明としてexecve(2) を取り上げています。下のコードは/bin/dateを実行している例です。
;補足:  プログラム中ではシステムコールexecve(2)よりも下のサンプルコードのようにライブラリ関数execl(3)などを使う場合の方が多いでしょう。下のコードはライブラリ関数execl(3)を使って/bin/dateを実行している例です。




1  #include <unistd.h>
<pre class="C">
2  main() {
#include <unistd.h>
3  if ( fork() == 0 )  
#include <sys/types.h>
4    execl("/bin/date",NULL);
#include <sys/wait.h>
5  wait();
void main(void) {
6 }
  int wstat;
  if ( fork() == 0 ) {
    execl("/bin/date","/bin/date",NULL);
  }
  wait(&wstat);
}
</pre>




;調べてみよう: カーネルの中でforkをするのはkernel/fork.cの中の関数do_fork です。関数do_forkは関数copy_processを呼び出してプロセスをコピーするのがメインの役割です。関数copy_processは、必要なものを親プロセスからコピーし子プロセス独自に必要な情報を初期化しています。
;調べてみよう: カーネルの中でforkをするのは[https://github.com/torvalds/linux/blob/master/kernel/fork.c#L2541  kernel_clone()]です。それまでは_do_fork()でしたが2020年にリリースされたLinux Kernel 5.9以降kernel_clone()になりました。[https://patchwork.kernel.org/project/linux-kselftest/cover/20200818173411.404104-1-christian.brauner@ubuntu.com/#23554325 参考資料]


==== プロセスを生成するシステムコール ====
==== プロセスを生成するシステムコール ====
305行目: 332行目:
その反対にプロセスを殺すシステムコールはkill(2)です。ここでは内部でkill(2)を呼んでいるコマンドkillを紹介しましょう。
その反対にプロセスを殺すシステムコールはkill(2)です。ここでは内部でkill(2)を呼んでいるコマンドkillを紹介しましょう。


<pre class="bash">
  $ kill -9 8321
  $ kill -9 8321
</pre>


killにプロセスIDを与えた場合、そのプロセス番号にSIGKILLを送ります。SIGKILLはプロセスを殺すシグナルです。killに与えるプロセスIDが0の場合、自分自身を殺します。-1は、シグナルを受け取ることができる全てのプロセスに送られます。プロセスinitはプロセスIDが1で、むかしは1を指定するとシステム全体が死んでいたのですが、今はルート権限でkill -9 1としても死なないようになっています。
killにプロセスIDを与えた場合、そのプロセス番号にSIGKILLを送ります。SIGKILLはプロセスを殺すシグナルです。killに与えるプロセスIDが0の場合、自分自身を殺します。-1は、シグナルを受け取ることができる全てのプロセスに送られます。プロセスinitはプロセスIDが1で、むかしは1を指定するとシステム全体が死んでいたのですが、今はルート権限でkill -9 1としても死なないようになっています。
312行目: 342行目:
;調べてみよう: killでマイナスの値を指定することができます。それはどのような役目をするのでしょうか？
;調べてみよう: killでマイナスの値を指定することができます。それはどのような役目をするのでしょうか？


===  スケジュリング ===
===  スケジューリング ===




プロセスにCPU資源をどのように与えるかの順番を決めるスケジュール (schedule)ことを行うことがスケジュリング(scheduling)です。それを司るのがスケジュラ(scheduler)です。
プロセスにCPU資源をどのように与えるかの順番を決めるスケジュール (schedule)ことを行うことがスケジューリング(scheduling)です。それを司るのがスケジューラ(scheduler)
<ref>
Linux Scheduler
https://www.kernel.org/doc/html/latest/scheduler/index.html
</ref>
です。


==== 基本的なスケジューリング方式 ====


スケジュリングの方式にはポリシーと呼ばれる、いくつかの方式があります。
スケジューリングの方式にはポリシーと呼ばれる、いくつかの方式<ref>Linux カーネル version 3.14 以降ではデッドラインスケジューリングポリシー (SCHED_DEADLINE) が追加されています。</ref>があります。




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


* FIFO ( SCHED_FIFO ) : 最初に入ったプロセスが終了するまでそのプロセスが専有する方式。最初に入ったものが最初に出るのでFirst-In-First-Out / FIFOと呼ばれる。


* RR : ラウンドロビン( Round Robin: 一定の間隔で順繰りに回ってくる)でプロセスが割り当てられる方式。
* RR ( SCHED_RR ) : ラウンドロビン( Round Robin: 一定の間隔で順繰りに回ってくる)でプロセスが割り当てられる方式。


* バッチ ( SCHED_BATCH ):  （たとえば大量の処理をしても）プライオリティの変化をつけない。尚、当然ながらタイムシェアリングシステムにおいてのバッチという意味である。


* 独自優先順位:  実行に使用した時間の違いなどにより優先順位をつけるなどし、その優先順位に従って割り当てる方式。(Linuxデフォルト)
* アイドル ( SCHED_IDLE ):  CPUがアイドリング状態になった時に処理が行われる。




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




339行目: 377行目:




ラウンドロビンは一定時間CPU時間を消化したプロセスを待ち状態に戻し、待っていた次のプロセスに切替えて順繰りにプロセスを実行していく方法です。この一定時間のことをタイムスライス(timeslice)といいます。公平にプロセスにCPUを割り当てることになります。タイムスライスを小さくすれば小さくするのど、細かくプロセスをCPUへ割り当てることができますが、しかし割り当て処理の回数が増えるにつれカーネル自体が消費するCPU時間も多くなっていきます。ですから、リーズナブルな値にしなければなりません。
ラウンドロビンは一定時間CPU時間を消化したプロセスを待ち状態に戻し、待っていた次のプロセスに切替えて順繰りにプロセスを実行していく方法です。この一定時間のことをタイムスライス(Time Slice)あるいはタイムクアンタム (Time Quantum)と呼びます。公平にプロセスにCPUを割り当てることになります。タイムスライスを小さくすれば小さくするのど、細かくプロセスをCPUへ割り当てることができますが、しかし割り当て処理の回数が増えるにつれカーネル自体が消費するCPU時間も多くなっていきます。ですから、リーズナブルな値にしなければなりません。




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




優先順位方式は、何らかの評価方式でCPUに割り当てる優先度や割り当てる時間を決めて順番を決める方式です。何らかという通り、色々な方法があって、オペレーティングシステムの違いによって異なりますし、あるいは同じカーネルであってもバージョンの違いによっても微妙に異なります。
Linux (Kernel 4.4.0で確認)でのバッチ ( SCHED_BATCH ) とアイドル ( SCHED_IDLE ) を実行した時の違いは曖昧です。カーネルの中では扱いが違いますが、どちらとも同じく実行優先度の各種パラメータが同様に低く押さえられており、処理時間の結果をみると両者の区別をつけるのはむずかしいといえます。




Linuxの基本はUNIXの流れであるラウンドロビンと優先順位をミックスしたものです。優先順位によってタスク待ちの優先順位の高いキューにセットされます。またそれだけでもなくタイムスライスの値も変化させています。Linux 2.6.22の場合、タイムスライスは平均100msですが内部では最小5msから最大800msまで内部で動的に変化させています。
Linuxの基本はUNIXの流れであるラウンドロビンと優先順位をミックスしたものです。優先順位によってタスク待ちの優先順位の高いキューにセットされます。またそれだけでもなくタイムスライスの値も変化させています。Linux 2.6.22の場合、タイムスライスは平均100msですが内部では最小5msから最大800msまで内部で動的に変化させています。


Linux 2.6系におけるスケジュラーは以前2.4系で使われていたスケジュラーからみると画期的に性能がいいO(1)スケジュラ(Order one scheduler)に変更されました。さらにLinux 2.6.23からO(1)スケジュラからCFS(Completely Fair Scheduler)
<ref>
Completely Fair Scheduler によるマルチプロセッシング
http://www.ibm.com/developerworks/jp/linux/library/l-cfs/index.html
</ref>


に変更されました。
Linux 2.6系におけるスケジューラは以前2.4系で使われていたスケジューラからみると画期的に性能がいいO(1)スケジューラ(Order one scheduler)に変更されました。さらにLinux 2.6.23からO(1)スケジューラからCFS(Completely Fair Scheduler)に変更されました。
O(1)スケジュラがヒューリスティック（発見的）にスケジュリングするのですが、CFS のスケジュリングは（数学的な意味で）数値を計算してスケジュリングを決めます。
 
ヒューリスティックな方法では、ある種の特定の条件に嵌まってしまいスケジュリングが公平に処理できなくなったり、あるいは偶然に有利な条件になったり不利な条件になったりとする可能性があります。
==== 使えるスケジューリングを調べてみる ====
それから比べるとCFSは公平にスケジュリングされます。
 
CFS スケジュラに関しての評価
 
<ref>
カーネルにどのスケジューラを入れるかはディストリビューションによって異なりますし、またカーネルのバージョンによっても違ってきます。どのようなスケジューリングが可能かを簡単に調べるのにはコマンド [[chrt]] が便利です。
Benchmarking CFS　http://kerneltrap.org/Linux/Benchmarking_CFS
 
</ref>
<pre class="bash">
を見ていると安定したスケジュリングを実現しており良い結果を残しているようです。
$ uname -r
4.4.0-134-generic
$ sudo chrt -m
SCHED_OTHER min/max priority : 0/0
SCHED_FIFO min/max priority : 1/99
SCHED_RR min/max priority : 1/99
SCHED_BATCH min/max priority : 0/0
SCHED_IDLE min/max priority : 0/0
</pre>
 
またchrtはプロセスのスケジューリング・ポリシーを変更することが出来ます。詳しくはマニュアル [https://man7.org/linux/man-pages/man1/chrt.1.html chrt] を確認してください。


今後もある意味オペレーティングシステムの心臓部ともいえるスケジュラーが色々な要件を満たすため、
あるいはさらなる効率化のために変更される可能性はあるでしょう。
あちらこちらの腕利きのカーネルハッカーがどんどん新しい提案をしてくるダイナミックさを持つLinuxらしいエピソードです。


=== プライオリティ ===
;追記: その後 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://github.com/torvalds/linux/blob/master/kernel/sched/deadline.c カーネルのコメント] では表現している ）アルゴリズムを採用しています。
   
UNIX系のオペレーティングシステムではプロセスの持つ動的に変化するプライオリティ値によって、CPUの割当てが変化します。プライオリティ値が小さいものが実行優先順位が高く、大きいものが実行優先順位が低くなります。


プロセス待機キューの並べ変え、プロセスのタイムスライスの値を設定する時に、プライオリティが高い程、よりCPUが割り当てられるような計算がされます。


もう一度、コマンドtopの出力例を見てみましょう。


  PID USER    PRI  NI  SIZE  RSS SHARE STAT %CPU %MEM  TIME COMMAND
タイムスライスの値はスケジューリングのポリシーによっても変化しますし、スケジューリング・ポリシーによっては動的にも変化します。
6981 hironobu  20  0  6552 6552  140 R    33.4  1.0  0:17 pi
指定されたプロセスの SCHED_RR 間隔を取得するシステムコール[http://man7.org/linux/man-pages/man2/sched_rr_get_interval.2.html sched_rr_get_interval(2)]を使うと実際の[[プロセスのタイムスライスの値を計測する]]ことが可能です。
6980 hironobu  17  0  6552 6552  140 R    32.8  1.0  0:17 pi
6979 hironobu  14  0  6504 6504  140 R    32.6  1.0  0:18 pi


RRIと書いてあるのがプライオリティ値です。NIと書いてあるのがnice値です。通常で使う範囲では、プロセスがCPUを専有すればするほどプライオリティ値が大きくなっていきます。カーネルの中では0から139の範囲で変化しています。優先順位が0が最低で139が最高です。ユーザ側に表示にされるのは20から-19 で、優先順はプラス側低く、マイナス側が高くなっています。


コマンド実行開始時にコマンドniceを使い底上げ値(優先順位を下げるのでハンディキャップ値といった方がいいかも知れませんが)を与えることができます。一般ユーザは優先順位を下げることしか出来ません。root権限では優先順位を上げることもできます。reniceは既に動いているプロセスのnice値を変更するものです。
これらのスケジューリングもカーネルのパラメータを変えることでチューニングができます。ただし、それに関しての説明は本サイトの主旨を越えてしまいますし、当然ながらカーネル内のパラメータを変更するわけですから、不適切な値の場合、システムに大きな損傷を与える可能性があります。ここでは[https://doc.opensuse.org/documentation/leap/archive/42.1/tuning/html/book.sle.tuning/cha.tuning.taskscheduler.html openSUSEのタスクスケジュラーのチューニング]のページを紹介するに留めます。


% nice -19 ./setiathome
==== CFS ====
Linux 2.6.23からCFS(Completely Fair Scheduler)
<ref>
Inside the Linux 2.6 Completely Fair Scheduler
https://developer.ibm.com/tutorials/l-completely-fair-scheduler/
(リンク切れ)
Linux カーネル 2.6 Completely Fair Scheduler の内側
http://www.ibm.com/developerworks/jp/linux/library/l-completely-fair-scheduler/
</ref>
は、O(1) スケジューラがヒューリスティック（発見的）にスケジューリングしていたのに対し、CFS のスケジューリングは（数学的な意味で）数値を計算してスケジューリングを決めます。
ヒューリスティックな方法では、ある種の特定の条件に嵌まってしまいスケジューリングが公平に処理できなくなったり、あるいは偶然に有利な条件になったり不利な条件になったりとする可能性があります。
それに比べCFSは公平にスケジューリングされます。


:補足| コマンドniceやreniceで与えるナイス値と、表示されるナイス値、カーネル内部で使うプライオリティ値、表示されるプライオリティ値ののプラス／マイナスは間違え安いので注意しましょう。上の例では-19の値を与えているが、topなどのNIの欄の値は19となります。


=== スレッド ===
それまでの Linux のスケジューラは、タスクを管理するキューをもち、その中で処理をしていました。CFSでは平衡2分探索木の一種である
赤黒木
<ref>
赤黒木がどう生成され管理されるかビジュアルで示してくれるサイトです。挿入(insert)、削除(delete)、検索(find)の操作をすると、どうRed/Black Treeが作られるか/操作されるかがビジュアルでわかります。
https://www.cs.usfca.edu/~galles/visualization/RedBlack.html
</ref>
というデータ構造を使いタスクを管理します。タスクは仮想実行時間という値を持ち、タスクが実行されるとこの値は増えます。タスク管理のツリーに戻される時、この仮想実行時間の値によってツリー中の適切な位置に置かれます。このツリーの中で最も値の小さいものが次に実行されるべきタスクとなります。こうすることによってCFSは[[計算量]]はO(log n)で、適切なタスクを選ぶという操作が可能になっています。


スレッドは計算資源を共有しCPU資源だけは別の状態であるような処理の流れをいいます。スレッドにはclone(2)のようなカーネルレベルで実行するスレッドとglibcなどユーザライブラリに含まれているユーザレベルで実行するスレッドの2つがあります。ですからスレッドが必ずしもカーネルモードで動作しているわけではなく、それはプログラムの書かれ方によります。ここの説明ではカーネルスレッドとユーザスレッドとの両方取り上げてみます。


既に説明した通りfork(2)が親と子のプロセスで内容をコピーしているのですが、とはいえ fork(2) 後は各々の実体は独立しています。しかし、スレッドは内容が一緒ですから、つまり処理の流れを別に持つCPU資源だけは複数個持つのですから、新しいプロセスが生まれていないので親も子もありません。CPU資源以外の計算資源のコピーが必要ない場合、あるいは同じ計算資源でCPU 資源を複数持ちたい時、計算資源を共有したい時などにスレッドは便利です。
今後もある意味オペレーティングシステムの心臓部ともいえるスケジューラが色々な要件を満たすため、あるいはさらなる効率化のために変更される可能性は十分にあります。
これからも、あちらこちらの腕利きのカーネルハッカーがどんどん新しい提案をしてくることでしょう。


CPUリソースだけを同時に複数個持つことができることで、たとえば実行しているタスク中でネットワーク入出力からの処理を行いつつ同時に他の計算を繰り返すような場合に非常に有効に働きができます。ウインドウシステムを考えてみましょう。マウスのようなポインティングデバイスから入力を受け、さらにその位置を計算しポインタのアイコンを変化させつつ、さらに画面書き換えを行うようなプログラムでは効率良く動くプログラムができます。
==== スケジューラのチューニング ====


            +--> スレッド 1 : 入力を受ける
スケジューラのチューニングに関しては下記の情報が参考になります。
            |
タスク ===>+--> スレッド 2 : 位置を計算
            |
            +--> スレッド 3 : 画面書き換えを行う


次はfork(2)と違い親プロセスの内容をコピーすることなく新しいプロセスを動かすことができるので速くプロセスが生成できることです。この利点は、資源コピーが発生しないまま処理スレッドだけを高速に立ち上げることができると説明しましたが実際にfork(2)とLinuxのpthreadライブラリ(カーネルスレッドではなくユーザスレッド)を使ってどれぐらい違うか試してみました。1000 回プロセスを生成するのとスレッドを生成するプログラムを書いてみます。結果はAthlon 1GHzマシンでスレッド生成側がトータル0.157秒、プロセス生成側が0.360秒と2倍以上の差をつけました。このように処理だけ大量に生成するような場合はスレッドが有利に働きます。
* SUSE [https://www.belbel.or.jp/opensuse-manuals_ja/cha-tuning-taskscheduler.html タスクスケジューラのチューニング]


fork版
* Red Hat Enterprise Linux 9 [https://access.redhat.com/documentation/ja-jp/red_hat_enterprise_linux/9/pdf/monitoring_and_managing_system_status_and_performance/red_hat_enterprise_linux-9-monitoring_and_managing_system_status_and_performance-ja-jp.pdf 第30章 スケジューリングポリシーの調整]
#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);
}
% cc -O fork.c -o f


thread版
=== プライオリティ ===
#include <pthread.h>
      
#include <stdlib.h>
UNIX系のオペレーティングシステムではプロセスの持つ動的に変化するプライオリティ値によって、CPUの割当てが変化します。プライオリティ値が小さいものが実行優先順位が低く、大きいものが実行優先順位が高くなります。
#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);
}
% cc -O thread.c -lpthread -o t


出力
プロセス待機キューの並べ変え、プロセスのタイムスライスの値を設定する時に、プライオリティが高い程、よりCPUが割り当てられるような計算がされます。
% time ./t
...........(続く)....1000
real 0m0.xxxs
user 0m0.xxxs
sys 0m0.xxxs


もう一度、コマンドtopの出力例を見てみましょう。




;補足: Linux上でThreadを使う方法に関しての良い資料を見つけることは難しいですが、IBMのLinux情報
<pre class="bash">
<ref>
  PID USER    PRI NI  SIZE  RSS SHARE STAT %CPU %MEM  TIME COMMAND
  Linuxのスレッド http://www-6.ibm.com/jp/developerworks/linux/001208/j_posix1.html
6981 hironobu  20  0  6552 6552  140 R    33.4  1.0  0:17 pi
</ref>
6980 hironobu  17  0  6552 6552  140 R    32.8  1.0  0:17 pi
には良質の説明が載っていました。
6979 hironobu  14  0  6504 6504  140 R    32.6  1.0  0:18 pi
</pre>




RRIと書いてあるのがプライオリティ値です。NIと書いてあるのがnice値です。通常で使う範囲では、プロセスがCPUを専有すればするほどプライオリティ値が大きくなっていきます。カーネルの中では0から139の範囲で変化しています。優先順位が0が最低で139が最高です。ユーザ側に表示にされるのは20から-19 で、優先順はプラス側低く、マイナス側が高くなっています。


=== マルチプロセッサとプロセス ===
コマンド実行開始時にコマンドniceを使い底上げ値(優先順位を下げるのでハンディキャップ値といった方がいいかも知れませんが)を与えることができます。一般ユーザは優先順位を下げることしか出来ません。root権限では優先順位を上げることもできます。reniceは既に動いているプロセスのnice値を変更するものです。


複数のプロセッサの話題に移りますが、ここでの複数プロセッサといってもスーパーコンピュータのように超並列とかは、この話題の範囲ではないので除外した上で話を進めます。


<pre class="bash">
% nice -19 ./setiathome
</pre>


さて、我々が現在利用の対象としているタイプのものは、対称マルチプロセッサ(SMP: Symmetric Multi-Processor) と呼ばれるタイプのものです。SMPの特徴で覚えておかなければならない点は各々のプロセッサが各々独自の入出力を持っていないのと、そして、どのプロセッサもシステム内のすべての構成部分に対して同等にアクセスできることの2点です。
;補足: コマンドniceやreniceで与えるナイス値と、表示されるナイス値、カーネル内部で使うプライオリティ値、表示されるプライオリティ値のプラス／マイナスは間違え安いので注意しましょう。上の例では-19の値を与えているが、topなどのNIの欄の値は19となります。


=== スレッド ===


似たようなシステムに共有メモリ型マルチプロセッサ ( Shared Memory Multiprocessor )というものがありますが、SMPはメモリを共有しているので共有メモリ型マルチプロセッサと同じ意味です。ただし、狭い定義を採用すれば共有メモリ型マルチプロセッサは、メモリ資源の共有だけに定義を持っているのに対して、SMPはシステムにある構成要素のすべてに対し同等にアクセスできるという点が違うことを注意しましょう。
スレッドは計算資源を共有しCPU資源だけは別の状態であるような処理の流れをいいます。スレッドにはclone(2)のようなカーネルレベルで実行するスレッドとglibcなどユーザライブラリに含まれているユーザレベルで実行するスレッドの2つがあります。ですからスレッドが必ずしもカーネルモードで動作しているわけではなく、それはプログラムの書かれ方によります。ここの説明ではカーネルスレッドとユーザスレッドとの両方取り上げてみます。




まずはSMPとはプロセッサの数が増えただけで、あとは構成要素を共有していると理解するのが良いでしょう。ですからSMPの良い部分は単一プロセッサと同じプログラムのモデルが使用できる点です。考えた方として単純にプロセッサが複数あると考えて構いません。単純化したスケジュールのモデルで考えてみましょう。たとえばラウンドロビンのスケジュールを用いて、CPU(ここでの説明はプロセッサと同じということで捉えてください)が1つだったのを2つにしたときを考えてみると下のようになります。


既に説明した通りfork(2)が親と子のプロセスで内容をコピーしているのですが、とはいえ fork(2) 後は各々の実体は独立しています。しかし、スレッドは内容が一緒ですから、つまり処理の流れを別に持つCPU資源だけは複数個持つのですから、新しいプロセスが生まれていないので親も子もありません。CPU資源以外の計算資源のコピーが必要ない場合、あるいは同じ計算資源でCPU 資源を複数持ちたい時、計算資源を共有したい時などにスレッドは便利です。


P = プロセス
  \
  \                /-> CPU ->+
    P -> P -> P -- /          |
                  \          |
    ^              \-> CPU ->+
    |                        V
    +-------------------------+




カーネルがSMPの複数CPUに対し処理を割り当てる方法はいくつかあります。それはプロセス単位での割り当てとスレッド単位の割り当てです。
CPUリソースだけを同時に複数個持つことができることで、たとえば実行しているタスク中でネットワーク入出力からの処理を行いつつ同時に他の計算を繰り返すような場合に非常に有効に働きができます。
ウインドウシステムを考えてみましょう。マウスのようなポインティングデバイスから入力を受け、さらにその位置を計算しポインタのアイコンを変化させつつ、さらに画面書き換えを行うようなプログラムでは効率良く動くプログラムができます。




;補足:  ここではプロセス (1タスク/1スレッド) と タスク ( 1タスク / 複数スレッド ) とし、前者が「プロセス単位で」、後者が「スレッド単位」でという意味です。
次はfork(2)と違い親プロセスの内容をコピーすることなく新しいプロセスを動かすことができるので速くプロセスが生成できることです。
この利点は、資源コピーが発生しないまま処理スレッドだけを高速に立ち上げることができると説明しましたが実際にfork(2)とLinuxのpthreadライブラリ(カーネルスレッドではなくユーザスレッド)を使ってどれぐらい違うか試してみました。
1000 回プロセスを生成するのとスレッドを生成するプログラムを書いてみます。結果はAthlon 1GHzマシンでスレッド生成側がトータル0.157秒、プロセス生成側が0.360秒と2倍以上の差をつけました。このようにCPUリソースのみだけで処理が出来るようなものを大量に生成するような場合はスレッドが有利に働きます。




ある一定のデータを処理するプログラムをまず仮定します。プロセス単位で割り当てるならプログラム側はSMPを何にも意識しなくても構いません。たくさんのプロセスがスケジュールされている場合でもCPU が多い分、自分の番が回ってくる回数が増えるため負荷に強いという意味で、処理能力が向上します。CPUが1個の時に同時に2つのプロセスを動かす時の処理時間とCPUが2個の時に同時に2つのプロセスを動かす時の処理時間を比較すると、後者の方が速くなります。しかし1つのプロセスに着目してみればCPUが1個で1つのプロセスしか動いていない時の処理時間よりは速くなることがありません。
生成可能な最大スレッド数は利用しているシステムのメモリ量に依存します。/proc/sys/kernel/threads-max を参照することでわかります。


=== マルチプロセッサとスレッド ===
* fork版


スレッド単位で割り当てる場合、実行中プログラムの持つ複数のスレッドが複数のCPUに同時に割当たります。その場合はプログラムの処理のスピードはCPU 単体の最大処理速度を越えることが可能になります。ただ、それでも上手にスレッドを分割し、その処理タイミングをきちんとプログラミングできる場合という前提が満たされることが必要です。
<pre class="C">
#include <sys/types.h>
#include <unistd.h>
#include <stdio.h>
#include <sys/wait.h>
int main(void) {
  int i,stat;
  for(i=0;i<1000;i++) {
    if ( fork() == 0 ) {
      fprintf(stderr,".");
      _exit(0);
    }
    wait(&stat);
  }
  printf("%d\n",i);
}
</pre>


<pre class="bash">
% cc -O fork.c -o f
</pre>


例えば、配列 A = { a1, a2, a3, ... an }があって、表の値をすべて掛けたものを、表の値をすべて足したもので割るという計算をしたいとしましょう。
* thread版


<pre class="C">


  a1 * a2 * a3 * ... * an
#include <pthread.h>
   ----------------------------  == ???
#include <stdlib.h>
   a1 + a2 + a3 + ... + an
#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);
}
</pre>
<pre class="bash">
% cc -O thread.c -lpthread -o t
</pre>




まず、a1 * a2 * a3 * ... * anを計算しAに代入するスレッドとa1 + a2 + a3+ ... + anを計算しBに代入するスレッドを作ります。両方のスレッドの計算の終了を待ってA/Bを計算します。この時、各々のスレッドが別々のCPUで並列に動くので1個のCPUで全部を計算させるよりも速く計算
* 出力
<ref>マルチスレッドを使い円周率を計算したプログラム例: http://h2np.net/pi/mt-bbp.c </ref>
ができるはずです。


<pre class="bash">
% time ./t
...........(続く)....1000
real 0m0.xxxs
user 0m0.xxxs
sys 0m0.xxxs
</pre>


;補足:  この例でも単純に2倍に速度があがるわけではありません。たとえば1CPUでの計算に20秒かかったとしましょう。2CPUを使いきれいに分母、分子の計算が分割でき並列に計算されたとしても、もし、分子の計算が5秒かかり、分母の計算が14.5秒かかり、分子÷分母の計算が0.5秒かかったならば、その処理時間は15秒となります。




SMPでの処理で「速い」という言葉を使う時は要注意です。このように2つの違う意味が同時に存在しているので、どの意味で「速い」のかをきちんと把握する必要があります。
;補足: Linux上でThreadを使う方法に関しての良い資料を見つけることは難しいですが、IBMのLinux情報には良質の説明が載っていました。<ref>
Linuxのスレッド http://www-6.ibm.com/jp/developerworks/linux/001208/j_posix1.html
</ref>


=== マルチプロセッサとプロセス ===


;調べてみよう:ここでは単純なボトルネックの例ですが、並列処理一般において処理効率には上限があるということを示しているアムダールの法則というのがあります。アムダールの法則について調べてみましょう。
[[マルチプロセッサとプロセス]]へ移動しました。


=== 脚注 ===
=== 脚注 ===

2024年10月24日 (木) 13:20時点における最新版

プロセスの基本的概念

プログラムが動作する実行実体のことをプロセスと呼びます。単純化して説明すると、プログラムの実行のことです。


プロセスはプロセスごとにプロセスIDを付与され、その数字で管理されています。 このプロセスIDの数字は 一定の数字で循環します。 Linuxカーネルが扱えるプロセスIDの最大値は/proc/sys/kernel/pid_maxを参照すればわかります。 カーネルのソースコード内ではプロセスIDの最大値は次のようにして設定しています。 最少構成でカーネルを作った場合は4096、32ビットCPUだと32768、64ビットもしくはそれ以上のCPUだと4 * 1024 * 1024つまり4194304ということになります。 


/*
 * This controls the default maximum pid allocated to a process
 */
#define PID_MAX_DEFAULT (CONFIG_BASE_SMALL ? 0x1000 : 0x8000)

/*
 * A maximum of 4 million PIDs should be enough for a while.
 * [NOTE: PID/TIDs are limited to 2^30 ~= 1 billion, see FUTEX_TID_MASK.]
 */
#define PID_MAX_LIMIT (CONFIG_BASE_SMALL ? PAGE_SIZE * 8 : \
        (sizeof(long) > 4 ? 4 * 1024 * 1024 : PID_MAX_DEFAULT))


概念的にどのような位置づけなのかを確認してみます。


ここではリソース(計算資源)という視点から説明してみます。 プログラムが実行する際のいろいろなリソースの1つとして、CPUリソースがありますが、 まずそのCPUリソースで考えてみましょう。円周率π [1] を小数点以下3300万桁まで求めるプログラムがここにあるとします。 このπを求めるには、数分、数十分、あるいは数時間という具合に長いCPU実行時間が必要です。 これを動かしたとしましょう。


ユーザ側から見る

プログラムは自分専用CPUを持っているように見える

ユーザ側の視点から見てみましょう。 CPUを1つしか搭載していないシステム上でユーザがπを求めるプログラムを3つ同時に動かした [2] とします。もちろん遅いでしょうが計算は3つ同時に動いているように見えます。


補足
話を単純化するために、ここではマルチコアとかハイパースレティングなどの能力も持っていない単純な1つの計算ユニットだけあるCPUとします。


これをプログラム側の視点から見てみましょう。 この時、πを求めている各々のプログラムは、他にどんなプログラムが同時に動作しているのか意識することはありません。 プロセスは自分専用のCPUを持っているように見えています。


もう一度ユーザ側視点に戻って、この状態を見てみると、 仮想的なリソースとしてのCPUリソースはプログラムに割り当てられ、 使っているユーザは同時に3つのプログラムが並行して動いているように見えます。

カーネル側から見る

プロセスは色々なリソースを持っている


今度はカーネル側から見てみましょう。物理的なCPUが1個しかありません。 ですから、まったく同時に複数のプログラムが処理できているわけではありません。 ある一瞬においては1つの物理的なCPUを専有できるのは1つのプログラムだけです。 また、その実行のためにCPUリソース以外にも必要なリソースも割り当てられています。 実行中プロセスの持つリソースを分類すると次のようになります。

  • CPUリソース (タスク系リソース)
  • プロセス間通信系リソース
  • 記憶管理系リソース
  • ファイル管理系リソース
  • ユーザ管理系リソース
  • ほか


これらの割り当てられたリソースを使って実行する主体をプロセスと呼ぶことができます。


調べてみよう
個々のプロセスのデータ構造はsched.hに定義されているstruct task_structです。個々のプロセスが保持する情報(とリソース)にはどのようなものがあるかチェックしてみよう。


実行するために必要なリソースを個々のプログラム実行に割り当てて、実行単位プロセスの説明を試みました。 さて、今度はプロセスを実際にCPUに割り当てていくことを考えてみましょう。 プロセスを割り当てるためにスケジュール（予定）を立て処理を進めていく必要があります。 それがスケジューリングです。 スケジューリングを説明するまえに、もう少しプロセスをみてみましょう。

プロセス・タスク・スレッド

ここまでの説明では実行実体の単位のことをプロセスと呼んでいますが、これは今時のUNIXから見て古典的な実行単位です。 今は、タスクとスレッドという単位で実行単位を考えるようになっています。タスク・スレッド・プロセスを定義をすると次のようになります。


  • スレッド実行に必要なすべてのリソースのすべてを指してタスク
  • リソース中でCPUリソースとして処理の流れを作るものをスレッド
  • １つのタスクに１つのスレッドしかないものをプロセス


スレッドやタスクの考え方（と、実装）は80年代にUNIXに入って来た、UNIXの歴史から見ると、わりと新しい技術です。 80年代に入ってから色々な組織がスレッドの実装を試みました。 米ブラウン大学の Brown Thread Package (BTP)、 サンマイクロシステムズのLWP (Light-weight process)、DECのDECthreads、 CMUのCスレッドパッケージ がありました。各々互換性はありません。 紆余曲折あり、現在では POSIX仕様のスレッドである pthreads(7) が主流になっています。


タスクが1つのスレッドしか持たない時、これはUNIX の伝統的な実行実体のプロセスです。 ですから、単純にプロセスと呼んでも構わないですし、 また同時に（ここまでの説明の範囲では）「プロセス＝タスクのこと」と考えてもかまいません。 タスクは複数のスレッドを持つことができます。複数のスレッドが動き出すまでは、プロセスといってもいいわけですが、 スレッドを複数持つ状態の場合は、プロセスと呼ぶよりタスクと呼ぶ方が適切でしょう。 このあたりは新旧の考え方が入り乱れて呼び方が混乱しているのは確かなようです。 UNIXが生まれた当時の処理の粒度と今時のUNIXでの処理の粒度は違うので、 これから先はプロセスという言葉は廃れてタスクという言い方が主流になるかも知れません。


補足
複数のプロセスが動くことをマルチタスクと呼びます。なんでマルチプロセスではないのかというと60年代に最初にマルチタスクが出来たオペレーティングシステムでは実行実体の単位をタスクと呼んでいたからです。なのでマルチタスクと呼びます。タスクという用語は使われる場面で微妙に意味が違うので注意しましょう。

プロセスの状態

プロセス・ステータスの流れ

オペレーティングシステムは実行すべき、たくさんのプロセスを同時に抱え込んでいるわけですが、それよりも少ない数のCPUでどうにかこうにか、やりくりしなければいけません。


まずプロセスの状態に着目して、その動きを見てみましょう。 その前にLinuxのタスクの状態遷移を細かく追っていくと、初心者にとって処理の流れの全体像がわかりづらくなると思います。 そこでここでは説明は理解しやすいようにLinuxそのままではなく [3] ある程度単純化したプロセス状態の基本モデルを考えて説明したいと思います。 さて、次の6つの状態を持つモデルを考えます。


  • (1) 実行中(RUNNING): プロセスがCPUを使用し実行している状態
  • (2) 待機中(READY): いつでも実行できるが、他のプロセスがCPUを使っているので待機している状態
  • (3) イベント待ち(SLEEP): 入力などのイベントを待ている状態
    • INTERRUPTIBLE: 割込みなどによって待ち状態が解除される
    • UNINTERRUPTIBLE: 解除されない限りSLEEP状態になっている
  • (4) 新しいプロセス生成(NEW): 新しいプロセスを作る状態
  • (5) 終了待ち (ZOMBIE) : プロセスの終了処理を待っている状態
  • (6) 停止 (STOPPED) : プログラムを一時的に停止させている状態



もっと単純に「待機中」「イベント待ち」「実行中」の３つの間を遷移するモデルにしましょう。動きは次のようになります。


  • 実行中→待機中 : 割り当てられたCPUリソースを使ったので、CPUでの実行状態から待機状態になる。この時、CPUリソースが使える状態になれば、すぐに実行状態に戻れる。
  • 待機中→実行中 : すぐにでも実行を行える状態で待っていて、CPUが割り当てられればすぐに実行中になる。
  • 実行中→イベント待ち : 入力などのイベントのために待ち状態になっている。
  • イベント待ち→待機中 : 入力のようなイベントがあったので待機中になっている。


さて先程例に出したπの計算をしている同時に3つ動かしているプログラムは、ほとんどの場合、「実行中→待機中」と「待機中→実行中」をいったり来たりしているはずです。 たまにIOのためにイベント待ちの状態になりますが、それよりもはるかにCPUを使いπの計算している時間の方が多いはずです。 待機中(READY状態)のプロセス数を示すロードアベレージは1.0を越えて徐々に増えていき最後には3.0を越えるはずです。 一方で例えばエディタのようなインタラクティブなプログラムを考えてみます。そうなると、ユーザが実際に使っている時間のほとんどは入力を待っている待機中です。ロードアベレージは1.0以下で限りなく0.0に近くなるでしょう。


調べてみよう
コマンドuptimeのマニュアルを調べてみよう。またロードアベレージの意味も調べてみよう。

プロセスの状態

皆さんが動かしているデスクトップレベルでは、いつもそんなに激しく色々なプロセスが同時にCPUを奪いあっている状態ではありません。動いているプロセスのほとんどは入力を待つSPLEEP状態です。コマンドtopを使ってプロセスの状況を見てみましょう。 

 % top
  18:49:03 up 49 days,  4:38,  8 users,  load average: 2.00, 0.82, 0.31
 80 processes: 75 sleeping, 5 running, 0 zombie, 0 stopped
 CPU states:  98.0% user,   2.0% system,   0.0% nice,   0.0% idle
 Mem:    645016K total,   622120K used,    22896K free,    46656K buffers
 Swap:  2441704K total,    16192K used,  2425512K free,   159200K cached
   PID USER     PRI  NI  SIZE  RSS SHARE STAT %CPU %MEM   TIME COMMAND
  6981 hironobu  20   0  6552 6552   140 R    33.4  1.0   0:17 pi
  6980 hironobu  17   0  6552 6552   140 R    32.8  1.0   0:17 pi
  6979 hironobu  14   0  6504 6504   140 R    32.6  1.0   0:18 pi
 19707 hironobu   9   0  5128 5128  2336 S     0.3  0.7   2:38 sawfish
 13399 hironobu  11   0  1060 1060   820 R     0.3  0.1   0:03 top
 13398 hironobu   9   0  3024 3024  1932 R     0.1  0.4   0:01 xterm
     1 root       8   0   472  432   412 S     0.0  0.0   0:43 init
     2 root       9   0     0    0     0 SW    0.0  0.0   0:00 keventd
     3 root      19  19     0    0     0 SWN   0.0  0.0   0:00 ksoftirqd_CPU0


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


STATの部分はプロセスの状態を表しています。一文字目がプロセスの状態を示していています。

  • R : RUNNING状態 (実行している、あるいは実行待ちの状態）
  • S : SLEEP状態 (I/O待ちなどの状態)
  • D : 割込みが利かないSLEEP状態 (sleep関数を呼んでSLEEPしている状態など）
  • Z : ゾンビ状態 (終了したがまだ親プロセスが終了処理を終えていない状態）
  • T : ストップ状態 (Control-Z/SIGSTOPによるプロセス停止の状態)


イベント待ちSLEEP状態で入力などの割込みで止まっている場合はSのSLEEP状態として表示されますが、bashやcsh のようなジョブコントロールが可能なシェル上でコマンドを実行し、コントロールZで止めたような場合はストップ状態となりTのストップ状態として表示されます。


ほとんどのSLEEP状態は場合は割込みがあればすぐに動き出すINTERRUPTIBLEなタイプです。カーネル中で解除されない限りSLEEP状態を続ける UNITERRUPTIBLE のような状態はデバイスをロックするなど特別な場合に使われるだけで、あまり多くはありません。


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


πの計算のように数値計算を延々と行うプログラムは別として、ディスクトップで利用しているソフトウェアの多くはユーザからのインタラクション(入力)待ちの状態で止まっているようなものです。


たとえばコンパイラがソースコードをコンパイルするプロセスでも実行中、待機中、イベント待ち状態を遷移します。 なぜならばコンパイラは、ファイル入出力を発生させるので、その入出力が発生している最中はイベント待ち状態になっています。ファイル入出力に10msかかったとして、その間はCPUは遊んでいる状態になります。 10msというは今日のCPUにとっては、長い長い暇な時間で、かなり大量の計算ができます。 このようにプロセスがCPU専有時間が過ぎたので次のプロセスに順番を与える以外にも、他のプロセスがCPUを使う状態が数多く発生します。

プロセスの生成

親プロセスが子プロセスを生むという形を取り、子プロセスは親プロセスのコピーとして動き始めます。例外はすべてのプロセスの始まりであるinitだけです。

調べてみよう
コマンド pstreeを使って、すべてのプロセスの親子関係がどうなっているかチェックしてみよう(pstreeの出力例)。

fork(2)

プロセスの生成はfork(2)を使い親プロセスが子プロセスを生み出します。下のコードを見て下さい。 


#include <unistd.h>
#include <stdlib.h>
#include <sys/types.h>
#include <sys/wait.h>
#include <stdio.h>
int  main(void){
  pid_t pid, wait_pid;
  int wait_stat;
  if ( (pid = fork()) == 0 ) {
    sleep(3);
    fprintf(stderr,"pid in child: %d\n",pid);
    exit(EXIT_SUCCESS);
  }
  else {
    if ( pid == -1 ) {
      exit(EXIT_FAILURE);
    }
    fprintf(stderr,"pid in parent: %d\n",pid);
    wait_pid=wait(&wait_stat);
    fprintf(stderr,"wait returns : %d(%o)\n",wait_pid,wait_stat);
    exit(EXIT_SUCCESS);
  }
  return(0);
}

システムコールfork(2)はフォーク後、親プロセスでは子プロセスのプロセスIDを返却し、子プロセスでは0を返却します。 またフォークができない時は-1を返却します。 wait(2)は子プロセスの終了を待つシステムコールです。 このプログラムを実行すると次のような出力になります。 

 $ ./a.out 
 pid in parent: 5008
 pid in child: 0
 wait returns : 5008(0)


最初は1つのプロセスですが、システムコールfork()を呼び出した時点で、エラーが発生しない限り2つのプロセス、つまり親と子のプロセスになります。 子プロセスは親プロセスのコピーで、そのまま子プロセス側の処理を行いますがsleep()があるので一旦スリープします。 親プロセスはそのまま続行していますから（そしてsleepしていませんから）、"pid in parent : ~ "を出力します。 システムコールwait()は子プロセスの終了を待つ機能です。そして、まだ子プロセスは終了していませんから、子プロセスの終了を待ちます。 子プロセスはsleepの待ち時間が過ぎれば"pid in child:~"を出力して終了します。 親プロセスでは子プロセスが終了したのでwaitが終了した子プロセスのidを返却します。 親プロセスは"wait returns : ~"を出力して終了します。


新しいコマンドを動かすのもforkを使い子プロセスを生成します。具体的には子プロセスが新しい実行ファイルを動かすにはシステムコールexecve(2)使います。これは、子プロセスの資源を新しい実行ファイルの資源として与えるものです。


補足
プログラム中ではシステムコールexecve(2)よりも下のサンプルコードのようにライブラリ関数execl(3)などを使う場合の方が多いでしょう。下のコードはライブラリ関数execl(3)を使って/bin/dateを実行している例です。


#include <unistd.h>
#include <sys/types.h>
#include <sys/wait.h>
void main(void) {
  int wstat;
  if ( fork() == 0 ) {
    execl("/bin/date","/bin/date",NULL);
  }
  wait(&wstat);
}


調べてみよう
カーネルの中でforkをするのはkernel_clone()です。それまでは_do_fork()でしたが2020年にリリースされたLinux Kernel 5.9以降kernel_clone()になりました。参考資料

プロセスを生成するシステムコール

プロセスを生成するシステムコールにはfork(2)の他にvfork(2)、さらにLinuxではclone(2)があります。vfork(2)の違いは親プロセスからページテーブルをコピーすることなく子プロセスを生成することです。子プロセスでexecve(2) が実行されれば、親プロセスからコピーされたページテーブルの内容は子プロセスの内容に変わります。つまり、fork(2)後すぐにexecve(2)が呼び出されるような場合、使われない内容をわざわざコピーする時間が短縮する分パフォーマンスが改善できます。

fork(2)とclone(2)ともに新しい子プロセスを生成しますが、fork(2)が内容をコピーするのに対しclone(2)は内容を共有しています。その意味では後に説明するスレッドと同じです。execve(2)で新しい内容を必要とした時に始めてコピーを行います。ですからvfork(2)はclone(2) の変形版といえます。ただしclone(2)はLinux独自のものなので、プログラムに使うと、他のシステムへの移植の際は問題が発生する可能性があります。

プロセスを殺すシステムコール

その反対にプロセスを殺すシステムコールはkill(2)です。ここでは内部でkill(2)を呼んでいるコマンドkillを紹介しましょう。 

 $ kill -9 8321


killにプロセスIDを与えた場合、そのプロセス番号にSIGKILLを送ります。SIGKILLはプロセスを殺すシグナルです。killに与えるプロセスIDが0の場合、自分自身を殺します。-1は、シグナルを受け取ることができる全てのプロセスに送られます。プロセスinitはプロセスIDが1で、むかしは1を指定するとシステム全体が死んでいたのですが、今はルート権限でkill -9 1としても死なないようになっています。


調べてみよう
killでマイナスの値を指定することができます。それはどのような役目をするのでしょうか？

スケジューリング

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

基本的なスケジューリング方式

スケジューリングの方式にはポリシーと呼ばれる、いくつかの方式[5]があります。


  • 独自優先順位 ( SCHED_OTHER ) : 実行に使用した時間の違いなどにより優先順位をつけるなどし、その優先順位に従って割り当てる方式。(Linuxデフォルト)
  • FIFO ( SCHED_FIFO ) : 最初に入ったプロセスが終了するまでそのプロセスが専有する方式。最初に入ったものが最初に出るのでFirst-In-First-Out / FIFOと呼ばれる。
  • RR ( SCHED_RR ) : ラウンドロビン( Round Robin: 一定の間隔で順繰りに回ってくる)でプロセスが割り当てられる方式。
  • バッチ ( SCHED_BATCH ): （たとえば大量の処理をしても）プライオリティの変化をつけない。尚、当然ながらタイムシェアリングシステムにおいてのバッチという意味である。
  • アイドル ( SCHED_IDLE ): CPUがアイドリング状態になった時に処理が行われる。


独自優先順位は、何らかの評価方式でCPUに割り当てる優先度や割り当てる時間を決めて順番を決める方式です。何らかという通り、色々な方法があって、オペレーティングシステムの違いによって異なりますし、あるいは同じカーネルであってもバージョンの違いによっても異なります。


FIFOの場合、そのプロセスがCPUを専有するのでCPUが空かない限り他のプロセスはCPUは割り当てられません。プロセスがSLEEP状態から復帰した場合、次にCPUを割り当てられるのはFIFOプロセスです。


調べてみよう
FIFOでプロセスを動かすとリアルタイム処理性能は満足するのでしょうか?もし足らないものがあるとすると、それは何でしょうか?


ラウンドロビンは一定時間CPU時間を消化したプロセスを待ち状態に戻し、待っていた次のプロセスに切替えて順繰りにプロセスを実行していく方法です。この一定時間のことをタイムスライス(Time Slice)あるいはタイムクアンタム (Time Quantum)と呼びます。公平にプロセスにCPUを割り当てることになります。タイムスライスを小さくすれば小さくするのど、細かくプロセスをCPUへ割り当てることができますが、しかし割り当て処理の回数が増えるにつれカーネル自体が消費するCPU時間も多くなっていきます。ですから、リーズナブルな値にしなければなりません。


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


Linux (Kernel 4.4.0で確認)でのバッチ ( SCHED_BATCH ) とアイドル ( SCHED_IDLE ) を実行した時の違いは曖昧です。カーネルの中では扱いが違いますが、どちらとも同じく実行優先度の各種パラメータが同様に低く押さえられており、処理時間の結果をみると両者の区別をつけるのはむずかしいといえます。


Linuxの基本はUNIXの流れであるラウンドロビンと優先順位をミックスしたものです。優先順位によってタスク待ちの優先順位の高いキューにセットされます。またそれだけでもなくタイムスライスの値も変化させています。Linux 2.6.22の場合、タイムスライスは平均100msですが内部では最小5msから最大800msまで内部で動的に変化させています。


Linux 2.6系におけるスケジューラは以前2.4系で使われていたスケジューラからみると画期的に性能がいいO(1)スケジューラ(Order one scheduler)に変更されました。さらにLinux 2.6.23からO(1)スケジューラからCFS(Completely Fair Scheduler)に変更されました。

使えるスケジューリングを調べてみる

カーネルにどのスケジューラを入れるかはディストリビューションによって異なりますし、またカーネルのバージョンによっても違ってきます。どのようなスケジューリングが可能かを簡単に調べるのにはコマンド chrt が便利です。 

$ uname -r
4.4.0-134-generic
$ sudo chrt -m
SCHED_OTHER min/max priority	: 0/0
SCHED_FIFO min/max priority	: 1/99
SCHED_RR min/max priority	: 1/99
SCHED_BATCH min/max priority	: 0/0
SCHED_IDLE min/max priority	: 0/0

またchrtはプロセスのスケジューリング・ポリシーを変更することが出来ます。詳しくはマニュアル chrt を確認してください。


追記
その後 Linux 3.14 (2014/3/20リリース) からリアルタイム指向の処理に必要なデットラインを処理するための SCHED_DEADLINE がスケジューラ [6] に加わっています。Linux 3.14ではデットライン・スケジューラのアルゴリズムはEarliest Deadline First (EDF)を採用していましたが、Linux 4.13 (2017/9/5リリース)からはEDFを改良しさらに Constant Bandwidth Server ( CBS ) 加えた( と、 カーネルのコメント では表現している ）アルゴリズムを採用しています。


タイムスライスの値はスケジューリングのポリシーによっても変化しますし、スケジューリング・ポリシーによっては動的にも変化します。 指定されたプロセスの SCHED_RR 間隔を取得するシステムコールsched_rr_get_interval(2)を使うと実際のプロセスのタイムスライスの値を計測することが可能です。


これらのスケジューリングもカーネルのパラメータを変えることでチューニングができます。ただし、それに関しての説明は本サイトの主旨を越えてしまいますし、当然ながらカーネル内のパラメータを変更するわけですから、不適切な値の場合、システムに大きな損傷を与える可能性があります。ここではopenSUSEのタスクスケジュラーのチューニングのページを紹介するに留めます。

CFS

Linux 2.6.23からCFS(Completely Fair Scheduler) [7] は、O(1) スケジューラがヒューリスティック（発見的）にスケジューリングしていたのに対し、CFS のスケジューリングは（数学的な意味で）数値を計算してスケジューリングを決めます。 ヒューリスティックな方法では、ある種の特定の条件に嵌まってしまいスケジューリングが公平に処理できなくなったり、あるいは偶然に有利な条件になったり不利な条件になったりとする可能性があります。 それに比べCFSは公平にスケジューリングされます。


それまでの Linux のスケジューラは、タスクを管理するキューをもち、その中で処理をしていました。CFSでは平衡2分探索木の一種である 赤黒木 [8] というデータ構造を使いタスクを管理します。タスクは仮想実行時間という値を持ち、タスクが実行されるとこの値は増えます。タスク管理のツリーに戻される時、この仮想実行時間の値によってツリー中の適切な位置に置かれます。このツリーの中で最も値の小さいものが次に実行されるべきタスクとなります。こうすることによってCFSは計算量はO(log n)で、適切なタスクを選ぶという操作が可能になっています。


今後もある意味オペレーティングシステムの心臓部ともいえるスケジューラが色々な要件を満たすため、あるいはさらなる効率化のために変更される可能性は十分にあります。 これからも、あちらこちらの腕利きのカーネルハッカーがどんどん新しい提案をしてくることでしょう。

スケジューラのチューニング

スケジューラのチューニングに関しては下記の情報が参考になります。

プライオリティ

UNIX系のオペレーティングシステムではプロセスの持つ動的に変化するプライオリティ値によって、CPUの割当てが変化します。プライオリティ値が小さいものが実行優先順位が低く、大きいものが実行優先順位が高くなります。

プロセス待機キューの並べ変え、プロセスのタイムスライスの値を設定する時に、プライオリティが高い程、よりCPUが割り当てられるような計算がされます。

もう一度、コマンドtopの出力例を見てみましょう。 


  PID USER     PRI  NI  SIZE  RSS SHARE STAT %CPU %MEM   TIME COMMAND
 6981 hironobu  20   0  6552 6552   140 R    33.4  1.0   0:17 pi
 6980 hironobu  17   0  6552 6552   140 R    32.8  1.0   0:17 pi
 6979 hironobu  14   0  6504 6504   140 R    32.6  1.0   0:18 pi


RRIと書いてあるのがプライオリティ値です。NIと書いてあるのがnice値です。通常で使う範囲では、プロセスがCPUを専有すればするほどプライオリティ値が大きくなっていきます。カーネルの中では0から139の範囲で変化しています。優先順位が0が最低で139が最高です。ユーザ側に表示にされるのは20から-19 で、優先順はプラス側低く、マイナス側が高くなっています。

コマンド実行開始時にコマンドniceを使い底上げ値(優先順位を下げるのでハンディキャップ値といった方がいいかも知れませんが)を与えることができます。一般ユーザは優先順位を下げることしか出来ません。root権限では優先順位を上げることもできます。reniceは既に動いているプロセスのnice値を変更するものです。 


 % nice -19 ./setiathome
補足
コマンドniceやreniceで与えるナイス値と、表示されるナイス値、カーネル内部で使うプライオリティ値、表示されるプライオリティ値のプラス／マイナスは間違え安いので注意しましょう。上の例では-19の値を与えているが、topなどのNIの欄の値は19となります。

スレッド

スレッドは計算資源を共有しCPU資源だけは別の状態であるような処理の流れをいいます。スレッドにはclone(2)のようなカーネルレベルで実行するスレッドとglibcなどユーザライブラリに含まれているユーザレベルで実行するスレッドの2つがあります。ですからスレッドが必ずしもカーネルモードで動作しているわけではなく、それはプログラムの書かれ方によります。ここの説明ではカーネルスレッドとユーザスレッドとの両方取り上げてみます。


既に説明した通りfork(2)が親と子のプロセスで内容をコピーしているのですが、とはいえ fork(2) 後は各々の実体は独立しています。しかし、スレッドは内容が一緒ですから、つまり処理の流れを別に持つCPU資源だけは複数個持つのですから、新しいプロセスが生まれていないので親も子もありません。CPU資源以外の計算資源のコピーが必要ない場合、あるいは同じ計算資源でCPU 資源を複数持ちたい時、計算資源を共有したい時などにスレッドは便利です。


CPUリソースだけを同時に複数個持つことができることで、たとえば実行しているタスク中でネットワーク入出力からの処理を行いつつ同時に他の計算を繰り返すような場合に非常に有効に働きができます。 ウインドウシステムを考えてみましょう。マウスのようなポインティングデバイスから入力を受け、さらにその位置を計算しポインタのアイコンを変化させつつ、さらに画面書き換えを行うようなプログラムでは効率良く動くプログラムができます。


次はfork(2)と違い親プロセスの内容をコピーすることなく新しいプロセスを動かすことができるので速くプロセスが生成できることです。 この利点は、資源コピーが発生しないまま処理スレッドだけを高速に立ち上げることができると説明しましたが実際にfork(2)とLinuxのpthreadライブラリ(カーネルスレッドではなくユーザスレッド)を使ってどれぐらい違うか試してみました。 1000 回プロセスを生成するのとスレッドを生成するプログラムを書いてみます。結果はAthlon 1GHzマシンでスレッド生成側がトータル0.157秒、プロセス生成側が0.360秒と2倍以上の差をつけました。このようにCPUリソースのみだけで処理が出来るようなものを大量に生成するような場合はスレッドが有利に働きます。


生成可能な最大スレッド数は利用しているシステムのメモリ量に依存します。/proc/sys/kernel/threads-max を参照することでわかります。

  • fork版
#include <sys/types.h>
#include <unistd.h>
#include <stdio.h>
#include <sys/wait.h>
int main(void) {
  int i,stat;
  for(i=0;i<1000;i++) {
    if ( fork() == 0 ) {
      fprintf(stderr,".");
      _exit(0);
    }
    wait(&stat);
  }
  printf("%d\n",i);
}

 % cc -O fork.c -o f
  • thread版

#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);
}

 % cc -O thread.c -lpthread -o t


  • 出力
 % time ./t
 ...........(続く)....1000
 real	0m0.xxxs
 user	0m0.xxxs
 sys	0m0.xxxs


補足
Linux上でThreadを使う方法に関しての良い資料を見つけることは難しいですが、IBMのLinux情報には良質の説明が載っていました。[9]

マルチプロセッサとプロセス

マルチプロセッサとプロセスへ移動しました。

脚注

  1. ↑ GNU/Linux上で円周率の計算をおこなう http://h2np.net/pi/
  2. ↑ 同じ答えを３つも必要ないというツッコミはここではなし。
  3. ↑ LinuxカーネルではTASK_RUNNING、TASK_INTERRUPTIBLE、 TASK_UNINTERRUPTIBLE、 TASK_STOPPEDなどの状態をもちます。詳しくはヘッダファイルの sched.h を参照してください。
  4. ↑ Linux Scheduler https://www.kernel.org/doc/html/latest/scheduler/index.html
  5. ↑ Linux カーネル version 3.14 以降ではデッドラインスケジューリングポリシー (SCHED_DEADLINE) が追加されています。
  6. ↑ デフォルトで使えるかどうかはディストリビューションによります。
  7. ↑ Inside the Linux 2.6 Completely Fair Scheduler https://developer.ibm.com/tutorials/l-completely-fair-scheduler/ (リンク切れ) Linux カーネル 2.6 Completely Fair Scheduler の内側 http://www.ibm.com/developerworks/jp/linux/library/l-completely-fair-scheduler/
  8. ↑ 赤黒木がどう生成され管理されるかビジュアルで示してくれるサイトです。挿入(insert)、削除(delete)、検索(find)の操作をすると、どうRed/Black Treeが作られるか/操作されるかがビジュアルでわかります。 https://www.cs.usfca.edu/~galles/visualization/RedBlack.html
  9. ↑ Linuxのスレッド http://www-6.ibm.com/jp/developerworks/linux/001208/j_posix1.html

目次へ

「https://uc2.h2np.net//index.php?title=プロセス管理&oldid=1761」から取得