時刻と時間の管理、プロセスのスケジューリング

					2019年01月31日
情報科学類 オペレーティングシステム II

                                       筑波大学 システム情報系 
                                       新城 靖
                                       <yas@cs.tsukuba.ac.jp>

このページは、次の URL にあります。
http://www.coins.tsukuba.ac.jp/~yas/coins/os2-2018/2019-01-31
あるいは、次のページから手繰っていくこともできます。
http://www.coins.tsukuba.ac.jp/~yas/
http://www.cs.tsukuba.ac.jp/~yas/

■今日の大事な話

時刻と時間の管理

モノトニック時刻の考え方
jiffies と HZ
PITの設定
時間切れ処理の方法
遅延処理の方法

プロセスのスケジューリングの関連

優先順位式スケジューリング
nice値の意味
スケジューラ
木構造によるレディ・キューの実装

■時刻と時間

◆求められる機能

システム・コール
- カレンダ時刻の提供: gettimeofday(), settimeofday(), time(), adjtime()。設定可能。
- モノトニック時刻(monotonic time)の提供: 決して後戻りすることがない時計。clock_gettime() システム・コールで使える。
- インターバルタイマ: setitimer(), sigaction().
- 時間切れ: select(), poll(), sleep(), usleep()
カーネル内の仕事
- システム・コールの実装
- プロセスのアカウンティング。スケジューリング。
- 時間切れ処理。モノトニック時刻(monotonic time)で指定することが普通。カレンダ時刻が使えることもある。単位は、秒（ナノ秒）のこともあるが、周期的なタイマ割り込みの間隔(tick)のこともある。

◆カレンダ時刻のAPI

gettimeofday() は、μ(マイクロ)秒単位の時刻を扱う。

struct timeval {
    time_t      tv_sec;     /* seconds. long int */
    suseconds_t tv_usec;    /* microseconds. long int */
};

int gettimeofday(struct timeval *tp, struct timezone *tzp);
int settimeofday(const struct timeval *tp, const struct timezone *tzp);

使い方

   1:	/*
   2:	        gettimeofday-print.c -- get colander time and print
   3:	        Created on: 2014/01/22 20:40:34
   4:	*/
   5:	
   6:	#include <sys/time.h>   /* gettimeofday() */
   7:	#include <time.h>       /* ctime() */
   8:	#include <stdio.h>
   9:	
  10:	main()
  11:	{
  12:	    struct timeval tv;
  13:	    time_t sec;
  14:	        gettimeofday( &tv, NULL );
  15:	        sec = tv.tv_sec;
  16:	        printf("%s", ctime(&sec) );
  17:	}

$ make gettimeofday-print 
cc     gettimeofday-print.c   -o gettimeofday-print
$ date 
Wed Jan 31 17:45:50 JST 2018
$ date 
Thu Jan 24 17:43:42 JST 2019
$ ./gettimeofday-print 
Thu Jan 24 17:43:43 2019
$

POSIX 1003.1, 2003 の struct timespec では、ナノ秒単位。

struct timespec  {
    time_t tv_sec;            /* Seconds.  */
    long int tv_nsec;         /* Nanoseconds.  */
};

int clock_settime(clockid_t clock_id, const struct timespec *tp);
int clock_gettime(clockid_t clock_id, struct timespec *tp);
int clock_getres(clockid_t clock_id, struct timespec *res);

clock_id としては、CLOCK_REALTIME (カレンダ時刻)やCLOCK_MONOTONIC がある。カレンダ時刻は、変更できる。逆走させることも可能。

順方向のジャンプや逆走を避けて、カレンダ時刻を合わせるには、adjtime() を使う。

int adjtime(const struct timeval *delta, struct timeval *olddelta);

adjtime() を使った時刻同期の方法。

外部の時刻サーバから時刻を得る。
自分自身の時刻が遅れていた時: adjtime() で進み方のペースを上げる。
自分自身の時刻が進みすぎていた時: adjtime() で進み方のペースを下げる。

◆インターバルタイマのAPI

定期的な仕事をしたい時に使う

struct itimerval {
    struct timeval it_interval; /* next value */
    struct timeval it_value;    /* current value */
};

int setitimer(int which, const struct itimerval *value, 
    struct itimerval *ovalue);

まず、it_value で指定された時間が経つと、シグナルが通知される。
以後、it_interval 毎にシグナルが通知される。

次のように考えてもよい。

内部に変数がある。
変数の初期値として、it_value を設定する。
変数の値が 0 になるまでカウントダウンする。
変数が 0 になると、次のことを行う。
- シグナルを発生させる。
- 変数の値を、it_interval に設定する。
解除されるまで 3. にもどって繰り返す。

◆時間切れ処理のAPI

int  select(int nfds, fd_set *readfds, fd_set *writefds, fd_set *exceptfds,
     		struct timeval *timeout);
int  poll(struct pollfd *fds, nfds_t nfds, int timeout);
int  epoll_wait(int epfd, struct epoll_event *events, int maxevents, int timeout);
int  kevent(int kq, const struct kevent *changelist, int nchanges,
       struct kevent *eventlist, int nevents, const struct timespec *timeout);

ネットワーク・プログラムでよく使う。複数の入力を監視する。指定された時間、入力がなければ、システム・コールから復帰する。

なにもしない時間切れ。

unsigned int sleep(unsigned int seconds);
int usleep(useconds_t usec);
int nanosleep(const struct timespec *rqtp, struct timespec *rmtp);

■時刻・時間関連のハードウェア

コンピュータによって違う。ここでは、PC/AT の話。

◆基本的なモデル

ハードウェアは、簡単。発振器とカウントダウンするカウンタを使う。

図?　発振器、カウンタ、比較、CPU、割込み、再設定
図? タイマ関連のハードウェアの基本モデル

発振器は、一定の周波数でカウンタに信号を送る。
発振器の周波数は、ソフトウェアで設定可能な場合がある。
カウンタは、ソフトウェアで読み書きできる。
カウンタは、０になったら、信号を生成する。それにより、 CPU に割込みがかかる。
カウンタのモードが一回切り(one shot mode)なら、これで終わり。
カウンタのモードが定期的(periodic mode)なら、別のレジスタから値を再設定する。

カウントダウンではなくカウントアップするものもある。

◆PIT (Programmable Interval Timer)

古いタイマ・デバイス。

発振器の周波数は、 1193182Hz。 NTSC 信号の 1/3。当時、実装が容易。ソフトウェアからは使いにくい。
カウンタ、再設定用のレジスタは、16ビット。
PIT デバイスは、3 つのタイマを持つ。
- 0: 割込み生成可能。OSの時間管理に適する。
- 1: Dynamic RAM のリフレッシュ。
- 2: スピーカーのトーン生成

◆CMOS RTC (Real Time Clock)

電源オフ時にも、バッテリで動作している。BIOS 用の設定を保持するメモリの一部。当時、CMOS は、「低消費電力」用としてだけ使われていた。今は、普通。　

2つの機能がある。

TOD (Time of Day) clock: 時刻を、year/month/day hour:minute:second という形式で持つ。秒以下は読めない。
定期的な割込み用: 2Hz から 8192Hz の範囲で、2 の冪乗の周期で割込みを起こせる。

制約

カウンタの値を読み書きできない
初期値は、2 の冪乗しか設定できない。

その他の割込み

TOD クロックが更新された時に割り込み。毎秒１回定期的。
TOD クロックが設定された時刻と一致した時に割り込み。目覚まし機能。

◆Local APIC (Advanced Programmable Interrupt Controller) Timers

Local APIC は、割込みのルーティングに使われる。マルチプロセッサでも、CPU 毎に独立。 Pentium 以降では、CPU に内蔵。

カウンタと初期値は 32 ビット。
入力周波数は、CPU のメモリ・バスの周波数と同じ。 (DDR 用以前)
PIT や CMOS RTC より高精度だが、ソフトウェアから周波数を調べる方法がない。 (PIT や CMOS RTCを使って調べるしかない。)
3つのモードがある。
- one-shot mode
- periodic mode
- TSC-deadline mode。TSC の精度で割り込みを発生させられる。

◆ACPI (Advanced Configuration and Power Interface)

チップセット・タイマとも呼ばれる。

発振器は、3579545 Hz (PIT の 3 倍)
カウンタは、24ビット。
初期値を保持するレジスタがない。24 ビットで一周する。
上位ビットが変化すると割込みがかかる。
省電力モードでも、通常通り動き続ける
読み書きするにも、1-2マイクロ秒かかることがある。

◆TSC (Time Stamp Counter)

Pentium 以降で利用可能。

発振器は、CPU クロック。高精度。
カウンタは、64 ビット。一周するのに、数年かかる。
割り込みを起こす機能はない。
初期値を保持するレジスタがない
ソフトウェアから rdtsc (read time stamp counter) 命令で簡単に読み出せる。
ユーザからもアクセス可能にするのが普通。
ソフトウェアから周波数を調べる方法がない。 (PIT や CMOS RTCを使って調べるしかない。)
省電力で CPU の周波数を落すことがある。 Invariant TSC/ART (Always Running Timer) がサポートされている CPU なら、一定。
SMP でも、CPU は同じ発振器の出力を使うので同じように増える。NUMA では動かない。

◆HPET(High Precision Event Timer)

新しい目の PC で搭載されている。

発振器の周波数は10MHz以上。
1個の増加する中央のカウンタがある。32ビット、または、64 ビット幅。ソフトウェアからカウンタ値を読み／書き／増加を停止できる。
比較器（タイマ）が、複数ある。最大32個。普通は3個以上ある。
比較器の値と中央のカウンタの値が一致すれば、そのタイマが発火し、割り込みを生成できる。
比較器が「定期的的(periodic)」として設定されていると、次に発火する比較器の値が自動的に設定（現在の値に既定値を加算）される。
比較器が「一回きり(one shot)」なら、発火して終わり。
読むのが遅い(1-2マイクロ秒かかる)ことがある。
ソフトウェアで比較器を設定しようとしている時に発火すると、危ない。

■jiffiesとHZ

jiffies は、Linux で、モノトニック時刻を提供する変数。単位は、tick。

PIT等のハードウェアのインターバル・タイマを使って、jiffies という変数を増やす。１回の割込みを tick という。
伝統的な Unix では、1秒間に 100 回-120 回のタイマ割込みを起こす。
Linux では、HZ というコンパイル時の定数で設定される。 100, 250, 1000 などに設定するのが普通。

利用例

time_stamp = jiffies; // 現在のモノトニック時刻を取得
next_tick = jiffies + 1; // 1 tick 後
later = jiffies + 5*HZ; // 5秒後。settimeoday() にかかわらず。
later = jiffies + HZ/10; // 0.1 秒後。

実装。

linux-4.20/include/asm-generic/param.h
   8:	# define HZ             CONFIG_HZ       /* Internal kernel timer frequency */

linux-4.20/include/generated/autoconf.h
 516:	#define CONFIG_HZ 1000

linux-4.20/include/linux/jiffies.h
  80:	extern u64 __cacheline_aligned_in_smp jiffies_64;
  81:	extern unsigned long volatile __cacheline_aligned_in_smp __jiffy_arch_data jiffies;

実体は、jiffies_64 という64ビットの変数。
jiffies という名前でアクセスすると、下位32ビットが取れる。別の変数に見えるが、実体はリンカのトリックで同じになっている。
32ビットの jiffies はオーバフローに注意する。たとえば、HZ が 1000 なら、jiffiesとjiffies_64 は共に、1秒間に1000増える。32 ビットの jiffies は、2^32/1000 秒間 == 約50日で一周する。64ビットの jiffies_64 なら 5.8 億年程度もつ。

◆tick_periodic()

tick_periodic() は、ハードウェアから独立したtick ごとの処理を行う関数である。

ハードウェアに依存した部分は、利用可能なタイマ(インターバル・タイマ) を使って、1秒間に HZ 回だけ定期的な割り込みを発生させる。
この割り込みは、伝統的に IRQ0 でなされる。
IRQ0 の割り込みハンドラ(ハードウェア依存)が tick_periodic() を呼ぶ。

linux-4.20/kernel/time/tick-common.c
  79:	static void tick_periodic(int cpu)
  80:	{
  81:	        if (tick_do_timer_cpu == cpu) {
...
  87:	                do_timer(1);
...
  89:	                update_wall_time();
  90:	        }
...
  92:	        update_process_times(user_mode(get_irq_regs()));
...
  94:	}

tick_periodic() は、tick ごとになされる割り込みハンドラから呼ばれる。引数は、cpu の ID。
複数の CPU のうち、tick_do_timer_cpu ならば、do_timer() を呼び、 jiffies_64 を増やす。
また、update_wall_time() で xtimeを更新する。
全ての CPU で update_process_times() を呼ぶ。時間、ユーザ時間、カーネル時間)を記録する。

◆do_timer()

linux-4.20/kernel/time/timer.c
  59:	__visible u64 jiffies_64 __cacheline_aligned_in_smp = INITIAL_JIFFIES;

linux-4.20/kernel/time/timekeeping.c
2195:	void do_timer(unsigned long ticks)
2196:	{
2197:	        jiffies_64 += ticks;
2198:	        calc_global_load(ticks);
2199:	}

do_timer() では、64 ビットの変数 jiffies_64 が 1 だけ増やされる。 (同じメモリを指している 32 ビットの変数 jiffies も同時に増える。)

■カレンダー時刻の実装

◆struct timekeeper/xtime

struct timekeeper は、全体でカレンダー時刻を計算するための構造体。次の３つのフィールドを使って1970年1月1日00:00:00(UTC)からの秒数をナノ秒単位で保持している。

u64 xtime_sec: 秒
u64 xtime_nsec: ナノ秒
u32 shift: ナノ秒部分のシフト。

実際には、xtime_nsec は、そのままでナノ秒を表すのではなく、 xtime_nsec >> shift でナノ秒を表す。

linux-4.20/include/linux/timekeeper_internal.h
  34:	struct tk_read_base {
...
  39:	        u32                     shift;
  40:	        u64                     xtime_nsec;
...
  43:	};

  88:	struct timekeeper {
  89:	        struct tk_read_base     tkr_mono;
...
  91:	        u64                     xtime_sec;
...
 134:	};

linux-4.20/kernel/time/timekeeping.c
 109:	static inline struct timespec64 tk_xtime(const struct timekeeper *tk)
 110:	{
 111:	        struct timespec64 ts;
 112:	
 113:	        ts.tv_sec = tk->xtime_sec;
 114:	        ts.tv_nsec = (long)(tk->tkr_mono.xtime_nsec >> tk->tkr_mono.shift);
 115:	        return ts;
 116:	}

xtime は、wall clock (掛け時計) とも呼ばれる。
xtime は、tick 単位で更新されるが、それより細かい単位を TSC 等の高精度の clocksource から読み込み補正する。
1970年1月1日00:00:00(UTC) は、epoch と呼ばれる。

◆gettimeofday()システム・コール

linux-4.20/kernel/time/time.c
 143:	SYSCALL_DEFINE2(gettimeofday, struct timeval __user *, tv,
 144:	                struct timezone __user *, tz)
 145:	{
 146:	        if (likely(tv != NULL)) {
 147:	                struct timespec64 ts;
 148:	
 149:	                ktime_get_real_ts64(&ts);
 150:	                if (put_user(ts.tv_sec, &tv->tv_sec) ||
 151:	                    put_user(ts.tv_nsec / 1000, &tv->tv_usec))
 152:	                        return -EFAULT;
 153:	        }
 154:	        if (unlikely(tz != NULL)) {
 155:	                if (copy_to_user(tz, &sys_tz, sizeof(sys_tz)))
 156:	                        return -EFAULT;
 157:	        }
 158:	        return 0;
 159:	}

linux-4.20/kernel/time/timekeeping.c
 723:	void ktime_get_real_ts64(struct timespec64 *ts)
 724:	{
 725:	        struct timekeeper *tk = &tk_core.timekeeper;
 726:	        unsigned long seq;
 727:	        u64 nsecs;
...
 734:	                ts->tv_sec = tk->xtime_sec;
 735:	                nsecs = timekeeping_get_ns(&tk->tkr_mono);
...
 739:	        ts->tv_nsec = 0;
 740:	        timespec64_add_ns(ts, nsecs);
 741:	}

put_user() は、copy_to_user() と同様、カーネル空間からユーザ空間にデータをコピーする。マクロ。
gettimeofday() システム・コールの API は、struct timeval でマイクロ秒単位だが、内部的には、struct timespec で、ナノ秒単位の変数 xtime が使われる。
単に xtime 変数の値をコピーするのではなく、利用可能ならさらに高精度の時計(TSC等)で補正する。
xtime 変数は、update_wall_time() で更新する。update_wall_time() は、タイマ割り込みの割り込みハンドラから呼ばれる。
if 文の中に入っている likely() や unlikely() は無視して良い。 (分岐予測による最適化に使われる。)

◆update_wall_time()

update_wall_time() は、 tick_periodic() から呼ばれ、掛け時計の時刻 xtime を更新する。

■時間切れ処理(タイマ)

Linux カーネルには、ある時間が経過したら、関数を実行する仕組みがある。

struct timer_list: tick 単位
struct hrtimer: ナノ秒単位

◆struct timer_list

linux-4.20/include/linux/timer.h
  11:	struct timer_list {
...
  17:	        unsigned long           expires;
  18:	        void                    (*function)(struct timer_list *);
  19:	        u32                     flags;
...
  24:	};

jiffies が増加して expires に達すれば、(*function)(data) を呼ぶ。

主に次の関数で操作する。

add_timer(struct timer_list *timer)
add_timer_on(struct timer_list *timer, int cpu): タイマの登録。_on() は、CPU ごと。
mod_timer(struct timer_list *timer, unsigned long expires): タイマの起動時刻の変更
del_timer(struct timer_list *timer),
del_timer_sync(struct timer_list *timer)
try_to_del_timer_sync(struct timer_list *timer): タイマのキャンセル。 del_timer_sync() は、もし既に実行中だったら、実行完了を待つ。

利用例。

{
    struct timer_list my_timer;           // 構造体の宣言
    init_timer(&my_timer);                // 初期化
    my_timer.expires = jiffies + delay;   // どのくらい待ちたいか
    my_timer.data = (unsigned long)data;  // 渡したいデータ
    my_timer.function = my_timer_func;    // 関数
    add_timer(&my_timer);                 // 登録
}

void my_timer_func(unsigned long data) {
    ...
}

add_timer() により、delay tick 後に my_timer_func() が呼ばれる。
この時、その関数には data が渡される。

◆High-resolution kernel timers

struct timer_listのAPIでは、tick単位だが、struct hrtimer の API では、ナノ秒単位で指定できる。ただし、実行されるのは、ハードウェアのタイマ割り込みなので、それ以上の精度はない。

linux-4.20/include/linux/hrtimer.h
  39:	enum hrtimer_mode {
  40:	        HRTIMER_MODE_ABS        = 0x00,
  41:	        HRTIMER_MODE_REL        = 0x01,
...
  54:	};

  59:	enum hrtimer_restart {
  60:	        HRTIMER_NORESTART,      /* Timer is not restarted */
  61:	        HRTIMER_RESTART,        /* Timer must be restarted */
  62:	};

 110:	struct hrtimer {
...
 113:	        enum hrtimer_restart            (*function)(struct hrtimer *);
...
 118:	};

主に次の関数で操作する。

hrtimer_init(struct hrtimer *timer, clockid_t clock_id, enum hrtimer_mode mode): struct hrtimer 構造体の初期化。 clock_id としては、モノトニック時刻(CLOCK_MONOTONIC)か、カレンダ時刻 (CLOCK_REALTIME)か選べる。
hrtimer_start(struct hrtimer *timer, ktime_t tim, const enum hrtimer_mode mode): タイマの開始。tim 秒後(ナノ秒単位)に functioon が呼ばれる。mode は、絶対指定(HRTIMER_MODE_ABS, absolute)か現在からの相対(HRTIMER_MODE_REL, relative)か指定できる。
hrtimer_cancel(struct hrtimer *timer): タイマのキャンセル。
schedule_hrtimeout(ktime_t *expires, enum hrtimer_mode mode): 指定した時間だけ現在実行中のプロセスを sleep させる。
ktime_t ktime_get(void): モノトニック時刻の取得。ktime は、ナノ秒単位。64ビット。
ktime_t ktime_get_real(void): カレンダ時刻の取得。
ktime_t ktime_set(s64 sec, unsigned long nsec): sec 秒, nsec ナノ秒の 2 値から ktime へ変換する。

利用例1: 今から(相対的に) t_nano 秒後に関数 my_timer_handler() を1度だけ呼びたい。

    struct hrtimer my_timer;
    hrtimer_init(&my_timer, CLOCK_MONOTONIC, HRTIMER_MODE_REL);
    my_timer.function = my_timer_handler;
    ...
    hrtimer_start(&my_timer,  ktime_set(0, t_nano), HRTIMER_MODE_REL);
    ...

enum hrtimer_restart my_timer_handler(struct hrtimer *timer)
{
        ...
        return HRTIMER_NORESTART;
}

CLOCK_MONOTONIC は、モノトニック時刻の意味。
ktime_set() で、秒、ナノ秒の2値をナノ秒単位の ktime_t へ変換している。単に変換しているだけで値の set はしない。
HRTIMER_MODE_REL は、現在時刻からの相対的な時刻の意味。
ハンドラで HRTIMER_RESTART を return すると、タイマが再設定される。
ハンドラで HRTIMER_NORESTART を return すると、タイマは再設定されない。

■実行の遅延

デバイスドライバでは、遅いデバイスに合わせるためにしばらく待ってから処理をしたいことが多い。得に割り込みの後半部(bottom-half)で。

例: Ethernet のドライバでモードを変更して 2 マイクロ秒だけ待つ。

様々な方法がある。

Busy loop
スケジューラを呼ぶ(スリープする)。

◆空ループ(busy loop)

待つための単純な方法は、空ループを回ること。

例1: 10 tick (インターバル・タイマによる割り込み)を待つ。

unsigned long timeout = jiffies + 10; // 10 ticks
while (time_before(jiffies,timeout))
    continue;

例2: 2秒待つ

unsigned long delay = jiffies + 2*HZ; // 2秒
while (time_before(jiffies,timeout))
    continue;

◆time_befefore()

jiffies は、32 ビットなので、オーバフローする可能性がある。次のコードは危ない。

unsigned long timeout = jiffies + 10; // 10 ticks
while (jiffies<timeout)
    continue;

引き算して 0 と比較すると、オーバフローの問題が解決できる。

unsigned long timeout = jiffies + 10; // 10 ticks
while (jiffies-timeout<0)
    continue;

次のマクロを使う方法もある。

linux-4.20/include/linux/jiffies.h
 105:	#define time_after(a,b)         \
 106:	        (typecheck(unsigned long, a) && \
 107:	         typecheck(unsigned long, b) && \
 108:	         ((long)((b) - (a)) < 0))
 109:	#define time_before(a,b)        time_after(b,a)
 110:	
 111:	#define time_after_eq(a,b)      \
 112:	        (typecheck(unsigned long, a) && \
 113:	         typecheck(unsigned long, b) && \
 114:	         ((long)((a) - (b)) >= 0))
 115:	#define time_before_eq(a,b)     time_after_eq(b,a)

◆cond_resched()

空ループは、CPU が無駄になるので良くない。その代わりに次の方法が使える。

unsigned long delay = jiffies + 2*HZ; // 2秒
while (time_before(jiffies,timeout))
    cond_resched();

他に実行すべき重要なプロセスが存在する(条件)時には、スケジューラを呼んで、実行する。存在しなければ、空ループと同じ。ただし、スケジューラを呼ぶ(sleepする可能性がある)ので、割り込みコンテキストからは使えない。

◆小さな遅延

tick 単位 (10ミリ秒-1ミリ秒) では大きすぎる場合、小さな遅延を実現するような関数がある。

void ndelay(unsigned long nsecs)
void udelay(unsigned long usecs)
void mdelay(unsigned long msecs)

udelay() は、ある回数のループで実装されている。回数は、CPUの速度等で決まる。ndelay(), mdelay() は、udelay() を呼んでいる。

udelay() で1ミリ秒以上待ってはいけない。ループのインデックスがオーバフローする可能性がある。

◆schedule_timeout()

set_current_state( TASK_INTERRUPTIBLE ); // signal で起きる可能性がある
schedule_timeout( s * HZ );

実装には struct timer_list が使われている。

■スケジューリングの目標

復習(オペレーティングシステム Iの範囲)

CPU 使用率を上げる。
スループット(単位時間辺りの仕事量)を上げる。
ターンアラウンド時間(プロセスを生成してから完了するまで)を短くする。
レディ・キューでの待ち時間を短くする。
応答時間を短くする。
プロセスに公平な CPU 時間を割り当てる。
(実時間制約を満たす)

全部は同時には成り立たない。

◆スケジューリング・アルゴリズム

FCFS (Firt-Come, First-Served), FIFO (First-In First-Out)
最短ジョブ優先(Shortest Job First)
優先度スケジューリング。飢餓状態(starvation)を起こす。 aging で優先度を上げる。
Round-Robin。時間刻み(time slice)ごとに切り替える。

◆優先順位式スケジューリング(OS一般)

プロセスごとに優先度を割り当てる。
OS は、実行可能で優先度が最も高くプロセスを(CPUの数だけ)実行する。同じものが複数あれば、ラウンドロビン。
プロセスの優先度は、利用したCPU資源や入出力のパタンで動的に変更する。

◆レディ・キュー(OS一般)

レディ・キューは、レディ状態のプロセスのリスト。優先度の順に並んでいれば、CPU はリストの先頭から要素を取り出して実行する。

■プロセス・スケジューリング関連のAPI

◆Unixにおけるプロセスに関するシステム・コール

nice(), getpriority(), setpriority(): nice値(優先度)の操作。値が小さい方が優先度が高い。一般ユーザは、値を大きくすることだけできる。値の範囲は、-20から19が普通。
sched_getscheduler(), sched_setscheduler(): POSIX 実時間拡張でのスケジューリング・ポリシーと優先度との設定。ポリシーは、SCHED_FIFO (first-in first-out), SCHED_RR (round robin), SCHED_OTHER (その他)。
sched_get_priority_max()、sched_get_priority_min(): 各ポリシーでの優先度の最大と最小を表す整数値。システムによって整数値が異なる。数字が大きい方が、優先度が高い。min < max になっている。

注意: Linux そのものは、実時間OSではない。本当に決められた時間内に完了するが求められる処理（ハードリアルタイム）には使えない。少し遅れても意味がある（ソフトリアルタイム）には、使えることがある。

◆ps -lコマンド

ps -l の結果のうち、次の属性に注目。

表示	説明
NI	Nice。優先度を表す値。

$ /bin/ps l 
F   UID   PID  PPID PRI  NI    VSZ   RSS WCHAN  STAT TTY        TIME COMMAND
0  1013 20638 20636  20   0 123572  2100 wait   Ss   pts/2      0:00 -bash
0  1013 21139 20638  20   0 155660  5900 poll_s S    pts/2      0:02 xterm -class UXTerm -title uxterm -u8
0  1013 21150 21139  20   0 123552  2144 wait   Ss   pts/3      0:00 bash
0  1013 21560 20638  20   0 267808 22928 poll_s S+   pts/2      0:09 emacs -nw
0  1013 21784 21150  20   0 103748   956 signal T    pts/3      0:00 lv kernel/time/timer.c
0  1013 27031 21150  20   0 108132   980 -      R+   pts/3      0:00 /bin/ps l
$ /bin/nice /bin/ps l 
F   UID   PID  PPID PRI  NI    VSZ   RSS WCHAN  STAT TTY        TIME COMMAND
0  1013 20638 20636  20   0 123572  2100 wait   Ss   pts/2      0:00 -bash
0  1013 21139 20638  20   0 155660  5900 poll_s S    pts/2      0:02 xterm -class UXTerm -title uxterm -u8
0  1013 21150 21139  20   0 123552  2144 wait   Ss   pts/3      0:00 bash
0  1013 21560 20638  20   0 267808 22928 poll_s S+   pts/2      0:09 emacs -nw
0  1013 21784 21150  20   0 103748   956 signal T    pts/3      0:00 lv kernel/time/timer.c
0  1013 27034 21150  30  10 108136   984 -      RN+  pts/3      0:00 /bin/ps l
$ /bin/nice -19 /bin/ps l 
F   UID   PID  PPID PRI  NI    VSZ   RSS WCHAN  STAT TTY        TIME COMMAND
0  1013 20638 20636  20   0 123572  2100 wait   Ss   pts/2      0:00 -bash
0  1013 21139 20638  20   0 155660  5900 -      R    pts/2      0:02 xterm -class UXTerm -title uxterm -u8
0  1013 21150 21139  20   0 123552  2144 wait   Ss   pts/3      0:00 bash
0  1013 21560 20638  20   0 267808 22928 poll_s S+   pts/2      0:09 emacs -nw
0  1013 21784 21150  20   0 103748   956 signal T    pts/3      0:00 lv kernel/time/timer.c
0  1013 27035 21150  39  19 108132   984 -      RN+  pts/3      0:00 /bin/ps l
$

ps コマンドの NI には、nice値が表示される。
nice 値を変更してプロセスを生成するには、nice コマンドが使える。デフォルトで 10 に設定される。

◆getpriority-pid.c

   1:	/*
   2:	        getpriority-pid.c -- 優先度の表示
   3:	        ~yas/syspro/proc/getpriority-pid.c
   4:	        Created on: 2009/12/14 12:15:11
   5:	*/
   6:	
   7:	#include <stdio.h>              /* stderr, fprintf() */
   8:	#include <sys/time.h>           /* getpriority() */
   9:	#include <sys/resource.h>       /* getpriority() */
  10:	#include <stdlib.h>             /* strtol() */
  11:	#include <limits.h>             /* strtol() */
  12:	
  13:	main( int argc, char *argv[] )
  14:	{
  15:	    int which, who, prio;
  16:	    pid_t pid;
  17:	        if( argc != 2 )
  18:	        {
  19:	            fprintf(stderr,"Usage: %% %s pid\n",argv[0] );
  20:	            exit( 1 );
  21:	        }
  22:	        pid = strtol( argv[1], NULL, 10 );
  23:	        prio = getpriority( PRIO_PROCESS, pid );
  24:	        printf("pid==%d, priority==%d\n", pid, prio);
  25:	}

$ ./getpriority-pid  
Usage: % ./getpriority-pid pid
$ echo $$ 
21150
$ ./getpriority-pid  
Usage: % ./getpriority-pid pid
$ ./getpriority-pid $$ 
pid==21150, priority==0
$ ./getpriority-pid 0 
pid==0, priority==0
$ /bin/nice -10 ./getpriority-pid 0 
pid==0, priority==10
$ /bin/nice -20 ./getpriority-pid 0 
pid==0, priority==19
$

シェルの PID は、$$ という変数で参照できる。
PID として 0 を指定すると、自分自身(シェルから継承)が表示される。
nice コマンドで値を大きくできる。最大20。 (特権ユーザは、値を小さくできる。)

◆nice値の利用法

優先度の調整方法

主にCPUを使うプロセスの優先度を下げて走らせる。Matlab とかビデオ・エンコーダとか。
(対話的な処理で入出力で待ちが多いプロセスの優先度を上げる。)

nice値の厳密な「意味」は、Unix の実装で異なる。 nice値とCPU時管理割当て方の標準はない。 Linux でも、何度か変更されている。

◆Linux(CFS)での通常のプロセス(非実時間プロセス)でのnice値の意味

nice値が1増えると、相対的に10%だけCPU時間の割当てが少なくなるようにする。

例1: 次の2つの CPU-bound のプロセスが存在したとする。

プロセスA: nice値0
プロセスB: nice値1 (優先度が低い)

AのCPU時間 : BのCPU時間 == 1 : 0.9

◆スケジューリングを行うためのハードウェア

やりたいことの例: 今のプロセスを 50ミリ秒だけ実行して、50ミリ秒後に別のプロセスを実行したい。

目覚まし時計を使う。ある時間がたったら割り込みを発生させるハードウェアを用いる。例: 50ミリ秒後にセットして、プロセスを実行する。割り込みが発生したら、プロセスを切り替える。
定期的な割り込みを使う。例: 10ミリ秒間隔で、割り込みを掛けるようにしかける。プロセスの実行中に、 5 回割り込みが発生したら、プロセスを切り替える。

Unix では、定期的な割り込み(10ミリ秒から1ミリ秒に1回)を使う方法がよく使われる。 1回の割り込みを tick という。

■Linux task構造体とnice値

Linux のプロセスは、task 構造体で表現されている。

◆task_struct構造体

linux-4.20/include/linux/sched.h
 590:	struct task_struct {
...
 599:	        volatile long                   state;
..
 636:	        int                             prio;
 637:	        int                             static_prio;
 638:	        int                             normal_prio;
 639:	        unsigned int                    rt_priority;
 640:	
 641:	        const struct sched_class        *sched_class;
 642:	        struct sched_entity             se;
 643:	        struct sched_rt_entity          rt;
...
 647:	        struct sched_dl_entity          dl;
...
 658:	        unsigned int                    policy;
...
1224:	};

 447:	struct sched_entity {
...
 449:	        struct load_weight              load;
...
 451:	        struct rb_node                  run_node;
...
 453:	        unsigned int                    on_rq;
...
 455:	        u64                             exec_start;
 456:	        u64                             sum_exec_runtime;
 457:	        u64                             vruntime;
...
 482:	};

 314:	struct load_weight {
 315:	        unsigned long                   weight;
 316:	        u32                             inv_weight;
 317:	};

struct task_struct の中に、prio 等のフィールドやstruct sched_entity がある。

◆policy

Linux では、スケジューリングのポリシーが大きく2種類。通常の時分割と実時間。

linux-4.20/include/linux/sched.h
  36:	#define SCHED_NORMAL            0
  37:	#define SCHED_FIFO              1
  38:	#define SCHED_RR                2
  39:	#define SCHED_BATCH             3
  40:	/* SCHED_ISO: reserved but not implemented yet */
  41:	#define SCHED_IDLE              5
  42:	#define SCHED_DEADLINE          6

SCHED_NORMAL: 伝統的なプロセス。時分割(time sharing)
SCHED_BATCH: パッチ向け。一度CPUを割り当てたら横取りしない。
SCHED_IDLE: nice 19 よりも低い優先度。
SCHED_FIFO (first in first out): 実時間で FIFO
SCHED_RR (round robin): 実時間でラウンドロビン
SCHED_DEADLINE: 実時間で、デッドラインが一番近いもの (Earliest Deadline First (EDF) )

◆prioとstatic_prio

static_prio

nice値を保持する。ただし、次のようなゲタを履かせている (NICE_TO_PRIO()参照)。

nice値の範囲 -20..19 を 0..39 にするために 20
実時間(realtime) のプロセスと区別するための 100 (MAX_RT_PRIO)

prio

スケジューリングに用いる優先度を保持する。

prio を見ると、通常のプロセスか実時間のプロセスかがわかる。 100 以上なら、通常のプロセス。通常のプロセスの prio は、100から140。

◆getpriority()システム・コール

linux-4.20/kernel/sys.c
 263:	SYSCALL_DEFINE2(getpriority, int, which, int, who)
 264:	{
 265:	        struct task_struct *g, *p;
 266:	        struct user_struct *user;
 267:	        const struct cred *cred = current_cred();
 268:	        long niceval, retval = -ESRCH;
 269:	        struct pid *pgrp;
 270:	        kuid_t uid;
 271:	
 272:	        if (which > PRIO_USER || which < PRIO_PROCESS)
 273:	                return -EINVAL;
...
 277:	        switch (which) {
 278:	        case PRIO_PROCESS:
 279:	                if (who)
 280:	                        p = find_task_by_vpid(who);
 281:	                else
 282:	                        p = current;
 283:	                if (p) {
 284:	                        niceval = nice_to_rlimit(task_nice(p));
 285:	                        if (niceval > retval)
 286:	                                retval = niceval;
 287:	                }
 288:	                break;
 289:	        case PRIO_PGRP:
...
 300:	        case PRIO_USER:
...
 320:	        }
...
 325:	        return retval;
 326:	}

linux-4.20/include/linux/sched/prio.h
   5:	#define MAX_NICE        19
   6:	#define MIN_NICE        -20
   7:	#define NICE_WIDTH      (MAX_NICE - MIN_NICE + 1)
...
  22:	#define MAX_USER_RT_PRIO        100
  23:	#define MAX_RT_PRIO             MAX_USER_RT_PRIO
  24:	
  25:	#define MAX_PRIO                (MAX_RT_PRIO + NICE_WIDTH)
  26:	#define DEFAULT_PRIO            (MAX_RT_PRIO + NICE_WIDTH / 2)
...
  33:	#define NICE_TO_PRIO(nice)      ((nice) + DEFAULT_PRIO)
  34:	#define PRIO_TO_NICE(prio)      ((prio) - DEFAULT_PRIO)

linux-4.20/include/linux/sched.h
1535:	static inline int task_nice(const struct task_struct *p)
1536:	{
1537:	        return PRIO_TO_NICE((p)->static_prio);
1538:	}

getpriority() は、which と who の 2引数。
which が PRIO_PROCESS なら、who は、pid。
who が 0 なら、自分自身(current)。
who が 0 以外なら find_task_by_vpid()でプロセスを探す。
プロセスが見つかれば、task_nice() で task_struct の static_prio の値を返す。この時、ゲタをはかせた分ゲタをはかせた分を引く。
さらに、システム・コールが負の値を返すとエラーの意味になるので、それを避けるために正の値に置換える。具体的には、-20,-19,-18,...17,18,19 を 40,39,38,...,3,2,1 に変換する。
正の値に置換えられた値は、ユーザ空間のライブラリで元にもどされる。

glibc-2.12/sysdeps/unix/sysv/linux/getpriority.c
  28:	#define PZERO 20
...
  35:	int
  36:	getpriority (enum __priority_which which, id_t who)
  37:	{
  38:	  int res;
  39:	
  40:	  res = INLINE_SYSCALL (getpriority, 2, (int) which, who);
  41:	  if (res >= 0)
  42:	    res = PZERO - res;
  43:	  return res;
  44:	}

◆se.load.weight

struct task_struct の static_prio は、struct task_struct の se.load.weight の値を決めるために使われる。

linux-4.20/kernel/sched/core.c
7019:	/*
7020:	 * Nice levels are multiplicative, with a gentle 10% change for every
7021:	 * nice level changed. I.e. when a CPU-bound task goes from nice 0 to
7022:	 * nice 1, it will get ~10% less CPU time than another CPU-bound task
7023:	 * that remained on nice 0.
7024:	 *
7025:	 * The "10% effect" is relative and cumulative: from _any_ nice level,
7026:	 * if you go up 1 level, it's -10% CPU usage, if you go down 1 level
7027:	 * it's +10% CPU usage. (to achieve that we use a multiplier of 1.25.
7028:	 * If a task goes up by ~10% and another task goes down by ~10% then
7029:	 * the relative distance between them is ~25%.)
7030:	 */
7031:	const int sched_prio_to_weight[40] = {
7032:	 /* -20 */     88761,     71755,     56483,     46273,     36291,
7033:	 /* -15 */     29154,     23254,     18705,     14949,     11916,
7034:	 /* -10 */      9548,      7620,      6100,      4904,      3906,
7035:	 /*  -5 */      3121,      2501,      1991,      1586,      1277,
7036:	 /*   0 */      1024,       820,       655,       526,       423,
7037:	 /*   5 */       335,       272,       215,       172,       137,
7038:	 /*  10 */       110,        87,        70,        56,        45,
7039:	 /*  15 */        36,        29,        23,        18,        15,
7040:	};

 692:	static void set_load_weight(struct task_struct *p, bool update_load)
 693:	{
 694:	        int prio = p->static_prio - MAX_RT_PRIO;
 695:	        struct load_weight *load = &p->se.load;
...
 714:	                load->weight = scale_load(sched_prio_to_weight[prio]);
 715:	                load->inv_weight = sched_prio_to_wmult[prio];
...
 718:	}

linux-4.20/kernel/sched/sched.h
 129:	# define scale_load(w)          (w)

struct task_struct の優先度 static_prio は、struct task_struct の struct sched_entity se の se.load.weight とその逆数se.load.inv_weight　に反映される。
se.load.{weight,inv_weight} の値は、後に、vruntime の計算の重みづけに使われる。

■スケジューラとレディ・キュー

◆sched_class

オブジェクト指向のクラスと同じ意味。スケジューラのための手続きの集合。

sched_classの主要な手続き
名前	説明
enqueue_task	プロセスが実行可能(runnable)になった
dequeue_task	プロセスが実行可能ではなくなった
yield_task	CPUを譲る。dequeueしてenqueue
check_preempt_curr	実行可能になった時にCPUを横取りすべきかをチェック
pick_next_task	次に実行すべきプロセスを選ぶ
set_curr_task	スケジューリング・クラスが変更された
task_tick	タイマ割込み(tick)の時に呼ばれる
task_new	新しいプロセスが生成された

◆sched_class使い方

プロセスのクラスに応じて enqueue、 dequeue の操作を切り替える。

linux-4.20/kernel/sched/core.c
 720:	static inline void enqueue_task(struct rq *rq, struct task_struct *p, int flags)
 721:	{
...
 730:	        p->sched_class->enqueue_task(rq, p, flags);
 731:	}

 733:	static inline void dequeue_task(struct rq *rq, struct task_struct *p, int flags)
 734:	{
...
 743:	        p->sched_class->dequeue_task(rq, p, flags);
 744:	}

プロセスのクラスに応じて struct task_struct の sched_class の値が違う。
プロセスのクラスに応じて、enqueue_task(), dequeue_task() は別の関数が呼ばれる。

◆Linuxの主要なスケジューリング・クラス

fair_sched_class: 公平を目指す。task_struct の policy が SCHED_NORMAL の時に使われる。
rt_sched_class: 実時間を目指す。task_struct の policy が SCHED_FIFO と SCHED_RR の時に使われる。
dl_sched_class: 実時間を目指す。task_struct の policy が SCHED_DEADLINE の時に使われる。

◆スケジューラ・クラスの設定

linux-4.20/kernel/sched/core.c
4077:	static void __setscheduler(struct rq *rq, struct task_struct *p,
4078:	                           const struct sched_attr *attr, bool keep_boost)
4079:	{
4080:	        __setscheduler_params(p, attr);
...
4086:	        p->prio = normal_prio(p);
...
4090:	        if (dl_prio(p->prio))
4091:	                p->sched_class = &dl_sched_class;
4092:	        else if (rt_prio(p->prio))
4093:	                p->sched_class = &rt_sched_class;
4094:	        else
4095:	                p->sched_class = &fair_sched_class;
4096:	}

4051:	static void __setscheduler_params(struct task_struct *p,
4052:	                const struct sched_attr *attr)
4053:	{
4054:	        int policy = attr->sched_policy;
4055:	
4056:	        if (policy == SETPARAM_POLICY)
4057:	                policy = p->policy;
4058:	
4059:	        p->policy = policy;
4060:	
4061:	        if (dl_policy(policy))
4062:	                __setparam_dl(p, attr);
4063:	        else if (fair_policy(policy))
4064:	                p->static_prio = NICE_TO_PRIO(attr->sched_nice);
...
4071:	        p->rt_priority = attr->sched_priority;
4072:	        p->normal_prio = normal_prio(p);
4073:	        set_load_weight(p, true);
4074:	}

__setscheduler_params() は、 policy に応じて task_struct や struct sched_attr のパラメタを設定する。
__setscheduler() は、task_struct の p->prio をpolicy に応じて設定する。
__setscheduler() は、 task_struct の sched_class を p->prio の値に応じて &dl_sched_class か &rt_sched_class か &fair_sched_class のいずれかを指すようにする。

◆CFS(Completely Fair Scheduler)

CFS は、Linux のスケジューラの固有名詞。 fair を目指してはいるが、complete に fair かと言われると不明。

CPUバウンドのプロセスが複数存在した時、ある期間を定めて、この期間の間に、 (優先度を考慮して)公平になるようにCPU資源を割り当てる。この期間の間に、 1度はCPUを割り当てられるようにする。この期間は、 kernel.sched_latency_ns で設定されている。以下の例では、15ミリ秒。

$ sysctl kernel.sched_latency_ns 
kernel.sched_latency_ns = 15000000
$

Linux CFS は、次の方法でスケジューリングを行なう。

各プロセスの se.vruntime (ナノ秒単位) が消費したCPU時間をもつ。
プロセスは、se.vruntime が小さい順にソートされたリストにつながれる。
スケジューラは、se.vruntime が最も小さいプロセス(リストの一番左) を実行する。
スケジューラは、実行した時間を現在実行しているプロセスの se.vruntime に加える。
ある程度、実行すると、現在実行中のプロセスのse.vruntime よりも、リストのものが小さくなる。そうなると、リストを作り直す。現在実行中のプロセスは、リストの先頭ではなくなる。
作り直したリストから se.vruntime が最も小さいプロセス(リストの一番左) を実行する。
ただし、あまり激しく切り替えると、キャッシュが効かなくなるので、ある granularity は、実行しつづける。

◆runqueues(リスト的な見方)

Linux における ready queue の1実装では、tasks_timeline を出発点とするリストと考えて良い。実際には、struct sched_entity se (struct task_structの途中) をつないでいく。

runqueue、tasks_timeline、se.vruntime
図? runqueueの構造

linux-4.20/kernel/sched/sched.h
 782:	struct rq {
...
 813:	        struct cfs_rq           cfs;
 814:	        struct rt_rq            rt;
 815:	        struct dl_rq            dl;
...
 927:	};

 482:	struct cfs_rq {
...
 494:	        struct rb_root_cached   tasks_timeline;
...
 571:	};

linux-4.20/kernel/sched/core.c
  25:	DEFINE_PER_CPU_SHARED_ALIGNED(struct rq, runqueues);

(CPUごとに) runqueue がある。
runqueue には、CFS(Completely Fair Scheduler))のための構造体 cfs_rq (cfs run queue)がある。
cfs_rq には、tasks_timeline がある。
tasks_timeline は、プロセス(task_struct) の se (struct sched_entity) を通じて、プロセスのリストを持っている。

◆赤黒木(red-black tree (rbtree))

赤黒木(red-black tree) は、平衡二分探索木(self-balancing binary search tree)の一種。節は、赤と黒に分類される。

二分探索木とは、次のような二分木。

各節にキーがある。
左の部分木は、根よりも小さいキーだけをもつ。
右の部分木は、根よりも大きいキーだけをもつ。

平衡木(balanced tree)、または、高さ平衡木(height-balanced tree)は、任意の節で左右の高さの差が一定以下の木。

Linux では、赤黒木をソートされた要素が並ぶリストを実現するために使っている。

◆Linux red-black treeの基本操作

型定義で、各要素に次の要素を含める。

struct rb_node node (rb_right, rb_left, rb_parent_color)
キーになるフィールド

検索

現在のノードとキーを比較
等しいなら見つかった
キーが小さいなら左の枝へ
キーが大きいなら右の枝へ
枝がなければキーは存在しない

挿入

まず検索する。現在のノードと挿入したいデータのキーを比較する。
キーが小さいなら左の枝を「親」にして検索を続ける。
キーが大きいなら右の枝を「親」にして検索を続ける。
キーが等しいならエラー(エラーにせず、重複を許すこともある)
子供がいない「親」が見つかる。
「親」から挿入したいデータへのリンクを作成する(rb_link_node())
平衡になるようにする(rebalancing, recoloring, rb_insert_color())

◆runqueues(red-black tree)

レディ・キューは、実際にはred-black tree による木構造になっている。 tasks_timeline は、木の根を差す。

runqueue、tasks_timeline、se.vruntime、red-black tree
図? runqueueの構造(red-black tree)

◆__enqueue_entity()

__enqueue_entity()は、CFS で木構造に要素を1個追加する関数である。

linux-4.20/kernel/sched/fair.c
 531:	static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
 532:	{
 533:	        struct rb_node **link = &cfs_rq->tasks_timeline.rb_root.rb_node;
 534:	        struct rb_node *parent = NULL;
 535:	        struct sched_entity *entry;
 536:	        bool leftmost = true;
 537:	
 538:	        /*
 539:	         * Find the right place in the rbtree:
 540:	         */
 541:	        while (*link) {
 542:	                parent = *link;
 543:	                entry = rb_entry(parent, struct sched_entity, run_node);
 544:	                /*
 545:	                 * We dont care about collisions. Nodes with
 546:	                 * the same key stay together.
 547:	                 */
 548:	                if (entity_before(se, entry)) {
 549:	                        link = &parent->rb_left;
 550:	                } else {
 551:	                        link = &parent->rb_right;
 552:	                        leftmost = false;
 553:	                }
 554:	        }
 555:	
 556:	        rb_link_node(&se->run_node, parent, link);
 557:	        rb_insert_color_cached(&se->run_node,
 558:	                               &cfs_rq->tasks_timeline, leftmost);
 559:	}
 560:	
 561:	static void __dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
 562:	{
 563:	        rb_erase_cached(&se->run_node, &cfs_rq->tasks_timeline);
 564:	}
 565:	

 490:	static inline int entity_before(struct sched_entity *a,
 491:	                                struct sched_entity *b)
 492:	{
 493:	        return (s64)(a->vruntime - b->vruntime) < 0;
 494:	}

__enqueue_entity() は、平衡二分探索木の一種、red-black tree に節を追加している。
キーは、vruntime。vruntime が小さいほど左に来る。
entity_before() で現在着目しているノードと挿入したいデータの vruntime を比較する。
挿入したいデータのvruntime が現在のノードより小さければ、左(&parent->rb_left), 大きければ右(&parent->rb_right) に進む。
挿入すべき箇所が見つかる。rb_link_node() で挿入する。
最後に rb_insert_color() を呼び出して、バランスを回復する。この時、一番左なら、キャッシュとして cfs_rq->tasks_timeline->rb_leftmost にも保存。

◆tickごとの仕事

scheduler_tick() は、tick ごとに定期的に呼び出される。 1 tick は、10 ミリ秒(HZ == 100)、4ミリ秒(HZ == 250)、1 ミリ秒(HZ == 1000)が一般的。

linux-4.20/kernel/sched/core.c
3036:	void scheduler_tick(void)
3037:	{
3038:	        int cpu = smp_processor_id();
3039:	        struct rq *rq = cpu_rq(cpu);
3040:	        struct task_struct *curr = rq->curr;
...
3048:	        curr->sched_class->task_tick(rq, curr, 0);
...
3061:	}

sched_class クラスの task_tick() を呼び出す。

◆CFSのentity_tick()

linux-4.20/kernel/sched/fair.c
9774:	static void task_tick_fair(struct rq *rq, struct task_struct *curr, int queued)
9775:	{
9776:	        struct cfs_rq *cfs_rq;
9777:	        struct sched_entity *se = &curr->se;
9778:	
9779:	        for_each_sched_entity(se) {
9780:	                cfs_rq = cfs_rq_of(se);
9781:	                entity_tick(cfs_rq, se, queued);
9782:	        }
...
9788:	}

4169:	static void
4170:	entity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr, int queued)
4171:	{
...
4175:	        update_curr(cfs_rq);
...
4202:	}

 803:	static void update_curr(struct cfs_rq *cfs_rq)
 804:	{
 805:	        struct sched_entity *curr = cfs_rq->curr;
 806:	        u64 now = rq_clock_task(rq_of(cfs_rq));
 807:	        u64 delta_exec;
...
 812:	        delta_exec = now - curr->exec_start;
...
 816:	        curr->exec_start = now;
...
 821:	        curr->sum_exec_runtime += delta_exec;
...
 824:	        curr->vruntime += calc_delta_fair(delta_exec, curr);
 825:	        update_min_vruntime(cfs_rq);
...
 836:	}

 628:	static inline u64 calc_delta_fair(u64 delta, struct sched_entity *se)
 629:	{
 630:	        if (unlikely(se->load.weight != NICE_0_LOAD))
 631:	                delta = __calc_delta(delta, NICE_0_LOAD, &se->load);
 632:	
 633:	        return delta;
 634:	}

task_tick_fair() は、tick ごとに定期的に呼び出される。
task_tick_fair() は、entity_tick() を呼ぶ。
entity_tick() は、update_curr() を呼ぶ。
update_curr() は、まず、現在の時刻を struct cfs_rq から得ている。
次に、前回の実行開始 exec_start と現在時刻の差　delta_exec　を求めている。
これを、引数に __update_curr() を呼び出している。
__update_curr() は、delta_exec　をさまざまな要素に加えている。
curr (現在実行中の)の vruntime については、重み付けをして加えている。重みの計算には、nice値(prio,se.load.weight)が使われる。

◆/proc を使ったスケジューラのパラメタの表示

$ cat /proc/sched_debug 
Sched Debug Version: v0.09, 2.6.32-431.3.1.el6.x86_64 #1
now at 7955627655.961573 msecs
  .jiffies                                 : 12250294951
...
cpu#0, 2100.000 MHz
  .nr_running                    : 1
...
  .curr->pid                     : 30990
...
cfs_rq[0]:/
  .exec_clock                    : 40812852.059736
...
rt_rq[0]:/
  .rt_nr_running                 : 0
...
  .nr_running                    : 1
...
runnable tasks:
            task   PID         tree-key  switches  prio     exec-runtime         sum-exec        sum-sleep
----------------------------------------------------------------------------------------------------------
R            cat 30990  32644150.029656         2   120  32644150.029656         1.072543         0.366310 /
...
cpu#1, 2100.000 MHz
...
cpu#2, 2100.000 MHz
...
cpu#3, 2100.000 MHz
...
$ cat /proc/self/sched 
cat (31354, #threads: 1)
---------------------------------------------------------
se.exec_start                      :    7962193228.073935
se.vruntime                        :      51856286.476132
se.sum_exec_runtime                :             1.211193
...
se.load.weight                     :                 1024
policy                             :                    0
prio                               :                  120
clock-delta                        :                  127
$

■課題4 時刻と時間の管理、プロセスのスケジューリング

★問題(401) PIT

PIT (Programmable Interval Timer)では、発振器の周波数は、1193182Hz である。再設定用のレジスタを 1193 に設定したら、何秒に1回、割り込みが発生するか。

★問題(402) モノトニック時刻の利用

カーネルの中で、カレンダ時刻ではなくてモノトニック時刻が使われている場所がある。その理由を簡単に説明しなさい。その場所をカレンダ時刻を使うようにすると、「ある操作をした場合」に「ある不都合」が生じる。このことを、例を使って説明しなさい。

★問題(403) struct timer_listの利用

関数f()を実行している時に、次の関数h()を、50 ミリ秒後に実行したいとする。

void h(int a,int b, int c) {
   ....
}

これを実現するために、どのようなコードを書けばよいか。以下の空欄を埋めなさい。

struct timer_list my_timer;

int my_arg_a,my_arg_b,my_arg_c;

void f(unsigned long data) {
    init_timer( /*空欄(a)*/ );
    my_timer.expires  = /*空欄(b)*/;
    my_timer.data     = 0;
    my_timer.function = /*空欄(c)*/;
    /*空欄(d)*/;
}

void my_timer_func(unsigned long data) {
     h( my_arg_a,my_arg_b,my_arg_c );
}

★問題(404) nice値

例1: 次の2つの CPU-bound のプロセスが存在したとする。

プロセスA: nice値0 (標準)
プロセスB: nice値1 (優先度が低い)

19秒間実行した場合、プロセスAとプロセスBは、それぞれ何秒ずつ CPU時間が割り当てられると期待されるか。

★問題(405) 二分探索木によるレディ・キューの実装

以下の図は、4つの要素を持つリストを表している。各要素には、キーがあり、優先度を表しているものとする。

head、next、next、next
図? 4つの要素を持つリスト構造

このリストを表現した二分探索木を１つ作り、節と枝（矢印）を用いて図示しなさい。ただし、木はバランスをしていなくても良いものとする。

注意: 正しい二分探索木は、複数存在する。

Last updated: 2019/01/27 23:14:54

Yasushi Shinjo / <yas@cs.tsukuba.ac.jp>