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

提供：UnixClassWiki
ナビゲーションに移動 検索に移動
← 古い編集新しい編集 →
444行目: 444行目:


今後もある意味オペレーティングシステムの心臓部ともいえるスケジューラが色々な要件を満たすため、
今後もある意味オペレーティングシステムの心臓部ともいえるスケジューラが色々な要件を満たすため、
あるいはさらなる効率化のために変更される可能性は十分にあります。
あるいはさらなる効率化のために変更される可能性は十分にあります。
これからも、あちらこちらの腕利きのカーネルハッカーがどんどん新しい提案をしてくることでしょう。
これからも、あちらこちらの腕利きのカーネルハッカーがどんどん新しい提案をしてくることでしょう。
==== スケジューラのチューニング ====
スケジューラのチューニングに関しては下記の情報が参考になります。
- SUSE [タスクスケジューラのチューニング](https://www.belbel.or.jp/opensuse-manuals_ja/cha-tuning-taskscheduler.html)
- Red Hat Enterprise Linux 9 [第30章 スケジューリングポリシーの調整] (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)


=== プライオリティ ===
=== プライオリティ ===

2023年8月18日 (金) 12:11時点における版

プロセスの基本的概念

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


プロセスはプロセスごとにプロセス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)で、適切なタスクを選ぶという操作が可能になっています。


今後もある意味オペレーティングシステムの心臓部ともいえるスケジューラが色々な要件を満たすため、

あるいはさらなる効率化のために変更される可能性は十分にあります。 これからも、あちらこちらの腕利きのカーネルハッカーがどんどん新しい提案をしてくることでしょう。


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

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

- SUSE [タスクスケジューラのチューニング](https://www.belbel.or.jp/opensuse-manuals_ja/cha-tuning-taskscheduler.html) - Red Hat Enterprise Linux 9 [第30章 スケジューリングポリシーの調整] (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)

プライオリティ

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=1732」から取得