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

提供：UnixClassWiki
ナビゲーションに移動 検索に移動
← 古い編集新しい編集 →
501行目: 501行目:
=== マルチプロセッサとプロセス ===
=== マルチプロセッサとプロセス ===


 
[[マルチプロセッサとプロセス]]へ移動しました。
[[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つのプロセスしか動いていない時の処理時間よりは速くなることがありません。


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

2018年9月19日 (水) 17:42時点における版

プロセスの基本的概念

プログラムが動作する実行実体のことをプロセスと呼びます。 単純化して説明すると、プログラムの実行のことです。 それで説明が終わるのはあんまりなので、もうちょっと概念的にどのような位置づけなのか考えてみます。


ここではリソース(計算資源)という視点から説明してみます。 プログラムが実行する際のいろいろなリソースの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 Univ.のブラウンスレッド、 サンマイクロシステムズのLWP (Lightweiht Process)、DECのCMA スレッド、 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を使って、すべてのプロセスの親子関係がどうなっているかチェックしてみよう。

fork(2)

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

#include <unistd.h>
#include <stdlib.h>
#include <sys/types.h>
#include <sys/wait.h>
#include <stdio.h>
void main(){
  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);
  }
  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);
}

システムコール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)などを使う場合の方が多いでしょうが、ここでは説明としてexecve(2) を取り上げています。下のコードは/bin/dateを実行している例です。


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


調べてみよう
カーネルの中でforkをするのはkernel/fork.cの中の関数do_fork です。関数do_forkは関数copy_processを呼び出してプロセスをコピーするのがメインの役割です。関数copy_processは、必要なものを親プロセスからコピーし子プロセス独自に必要な情報を初期化しています。

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

プロセスを生成するシステムコールには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)です。

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

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


  • 独自優先順位 ( 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時間を消化したプロセスを待ち状態に戻し、待っていた次のプロセスに切替えて順繰りにプロセスを実行していく方法です。この一定時間のことをタイムスライス(timeslice)といいます。公平にプロセスに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)に変更されました。


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


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

CFS

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


それまでの Linux のスケジューラは、タスクを管理するキューをもち、その中で処理をしていました。CFSでは平衡2分探索木の一種である 赤黒木 [7] というデータ構造を使いタスクを管理します。タスクは仮想実行時間という値を持ち、タスクが実行されるとこの値は増えます。タスク管理のツリーに戻される時、この仮想実行時間の値によってツリー中の適切な位置に置かれます。このツリーの中で最も値の小さいものが次に実行されるべきタスクとなります。こうすることによって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リソースのみだけで処理が出来るようなものを大量に生成するような場合はスレッドが有利に働きます。

  • fork版
#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>
#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情報には良質の説明が載っていました。[8]

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

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

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

スレッド単位で割り当てる場合、実行中プログラムの持つ複数のスレッドが複数のCPUに同時に割り当てられていきます。その場合はプログラムの処理のスピードは CPU 単体の最大処理速度を越えることが可能になります。ただ、それでも上手にスレッドを分割し、その処理タイミングをきちんとプログラミングできる場合という前提が満たされることが必要です。

こんな計算を仮定してみる。

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

まず、a1 * a2 * a3 * ... * anを計算しAに代入するスレッドとa1 + a2 + a3+ ... + anを計算しBに代入するスレッドを作ります。両方のスレッドの計算の終了を待ってA/Bを計算します。この時、各々のスレッドが別々のCPUで並列に動くので1個のCPUで全部を計算させるよりも速く計算 [9] ができるはずです。

しかしこの場合、処理効率が単純に2倍に上がるわけではありません。たとえば1CPUでの計算に20秒かかったとしましょう。2CPU を使い分母、分子の計算が分割でき並列に計算されたとしても、もし、分子の計算が12秒かかり、分母の計算が10秒かかり、分子÷分母の計算が0.5秒かかったならば、分母の計算時間と割り算の時間を足したものがクリティカルパスですから、その処理時間は12.5秒となります。このようにCPU数が増えたからといって単純に性能がCPU数に合わせて倍数的に増えていくわけではありませんし、もちろん処理が並列化されていないプログラムをいくら走らせても当然ながらその結果はCPUを1つ占有出来ること以上の効果はありません。

調べよう
並列処理一般において処理効率には上限があることを示しているのがアムダールの法則です。アムダールの法則について調べてみましょう。[10]

脚注

  1. ↑ GNU/Linux上で円周率の計算をおこなう http://h2np.net/pi/
  2. ↑ 同じ答えを３つも必要ないというツッコミはここではなし。
  3. ↑ LinuxカーネルではTASK_RUNNING、TASK_INTERRUPTIBLE、 TASK_UNINTERRUPTIBLE、 TASK_STOPPEDなどの状態をもちますが、詳しくはヘッダファイルの sched.h を参照してください。
  4. ↑ デフォルトで使えるかどうかはディストリビューションによります。
  5. ↑ Linux カーネル 2.6 Completely Fair Scheduler の内側 http://www.ibm.com/developerworks/jp/linux/library/l-completely-fair-scheduler/
  6. ↑ Completely Fair Scheduler によるマルチプロセッシング http://www.ibm.com/developerworks/jp/linux/library/l-cfs/index.html
  7. ↑ 赤黒木がどう生成され管理されるかビジュアルで示してくれるサイトです。挿入(insert)、削除(delete)、検索(find)の操作をすると、どうRed/Black Treeが作られるか/操作されるかがビジュアルでわかります。 https://www.cs.usfca.edu/~galles/visualization/RedBlack.html
  8. ↑ Linuxのスレッド http://www-6.ibm.com/jp/developerworks/linux/001208/j_posix1.html
  9. ↑ マルチスレッドを使い円周率を計算したプログラム例: https://uc2.h2np.net/src/mt-bbp.c
  10. ↑ ジーン・アムダールが書いた1967年の論文 "http://www-inst.eecs.berkeley.edu/~n252/paper/Amdahl.pdf" が公開されています。ここに書かれている並列計算の遅滞に関する内容が後にアムダールの法則と呼ばれるようになります。

目次へ

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