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

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

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

このページは、次の URL にあります。
http://www.coins.tsukuba.ac.jp/~yas/coins/os2-2020/2021-01-27
あるいは、次のページから手繰っていくこともできます。
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

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
$ ./gettimeofday-print 
Wed Jan 20 18:38:05 2021
$ date 
Wed Jan 20 18:38:06 JST 2021
$ 

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

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

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

1. 外部の時刻サーバから時刻を得る。
2. 自分自身の時刻が遅れていた時: adjtime() で進み方のペースを上げる。
3. 自分自身の時刻が進みすぎていた時: 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 毎にシグナルが通知される。

1. 内部に変数がある。
2. 変数の初期値として、it_value を設定する。
3. 変数の値が 0 になるまでカウントダウンする。
4. 変数が 0 になると、次のことを行う。
   • シグナルを発生させる。
   • 変数の値を、it_interval に設定する。
5. 解除されるまで 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);

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

◆基本的なモデル

図? タイマ関連のハードウェアの基本モデル

• 発振器は、一定の周波数でカウンタに信号を送る。
• 発振器の周波数は、ソフトウェアで設定可能な場合がある。
• カウンタは、ソフトウェアで読み書きできる。
• カウンタは、０になったら、信号を生成する。それにより、 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)

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

• カウンタと初期値は 32 ビット。
• 入力周波数は、CPU のメモリ・バスの周波数と同じ。
• 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)

• 発振器は、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)

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

■jiffiesとHZ

• 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-5.10.3/include/asm-generic/param.h
   8:	# define HZ             CONFIG_HZ       /* Internal kernel timer frequency */

linux-5.10.3/include/generated/autoconf.h
1100:	#define CONFIG_HZ 1000

linux-5.10.3/include/linux/jiffies.h
  79:	extern u64 __cacheline_aligned_in_smp jiffies_64;
  80:	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()

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

linux-5.10.3/kernel/time/tick-common.c
  84:	static void tick_periodic(int cpu)
  85:	{
  86:	        if (tick_do_timer_cpu == cpu) {
...
  93:	                do_timer(1);
...
  96:	                update_wall_time();
  97:	        }
...
  99:	        update_process_times(user_mode(get_irq_regs()));
...
 101:	}

• 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-5.10.3/kernel/time/timer.c
  59:	__visible u64 jiffies_64 __cacheline_aligned_in_smp = INITIAL_JIFFIES;

linux-5.10.3/kernel/time/timekeeping.c
2267:	void do_timer(unsigned long ticks)
2268:	{
2269:	        jiffies_64 += ticks;
2270:	        calc_global_load();
2271:	}

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

■カレンダー時刻の実装

◆struct timekeeper/xtime

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

linux-5.10.3/include/linux/timekeeper_internal.h
  92:	struct timekeeper {
  93:	        struct tk_read_base     tkr_mono;
...
  95:	        u64                     xtime_sec;
...
 139:	};

  34:	struct tk_read_base {
  35:	        struct clocksource      *clock;
...
  39:	        u32                     shift;
  40:	        u64                     xtime_nsec;
...
  43:	};

linux-5.10.3/kernel/time/timekeeping.c
 127:	static inline struct timespec64 tk_xtime(const struct timekeeper *tk)
 128:	{
 129:	        struct timespec64 ts;
 130:	
 131:	        ts.tv_sec = tk->xtime_sec;
 132:	        ts.tv_nsec = (long)(tk->tkr_mono.xtime_nsec >> tk->tkr_mono.shift);
 133:	        return ts;
 134:	}

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

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

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

linux-5.10.3/kernel/time/timekeeping.c
 800:	void ktime_get_real_ts64(struct timespec64 *ts)
 801:	{
 802:	        struct timekeeper *tk = &tk_core.timekeeper;
 803:	        unsigned int seq;
 804:	        u64 nsecs;
...
 811:	                ts->tv_sec = tk->xtime_sec;
 812:	                nsecs = timekeeping_get_ns(&tk->tkr_mono);
...
 816:	        ts->tv_nsec = 0;
 817:	        timespec64_add_ns(ts, nsecs);
 818:	}

• 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()

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

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

◆struct timer_list

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

jiffies が増加して expires に達すれば、(*function)(tl) を呼ぶ。 引数 tl は、truct timer_list *。

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

timer_setup(struct timer_list *timer, void (*callback)(struct timer_list *), unsigned int flags);

timer を初期化する。function は callback で初期化される。

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() は、もし既に実行中だったら、実行完了を待つ。

(*function)() で独自のデータ(以下の例では struct s1 *)を得るには、次の ようにする。

struct s1 {
	...
        struct timer_list s_timer;
	...
        int s_x;
	...
};

void timer_list_handler(struct timer_list *tl) {
	struct s1 *p1 = from_timer(p1, tl, s_timer);
	f( p1->s_x );
}

図? timer_list から外側の構造体を求める

◆schedule_timeout()

linux-5.10.3/kernel/time/timer.c
1789:	struct process_timer {
1790:	        struct timer_list timer;
1791:	        struct task_struct *task;
1792:	};

1832:	signed long __sched schedule_timeout(signed long timeout)
1833:	{
1834:	        struct process_timer timer;
1835:	        unsigned long expire;
...
1866:	        expire = timeout + jiffies;
1867:	
1868:	        timer.task = current;
1869:	        timer_setup_on_stack(&timer.timer, process_timeout, 0);
1870:	        __mod_timer(&timer.timer, expire, MOD_TIMER_NOTPENDING);
1871:	        schedule();
1872:	        del_singleshot_timer_sync(&timer.timer);
1873:	
1874:	        /* Remove the timer from the object tracker */
1875:	        destroy_timer_on_stack(&timer.timer);
1876:	
1877:	        timeout = expire - jiffies;
1878:	
1879:	 out:
1880:	        return timeout < 0 ? 0 : timeout;
1881:	}

1794:	static void process_timeout(struct timer_list *t)
1795:	{
1796:	        struct process_timer *timeout = from_timer(timeout, t, timer);
1797:	
1798:	        wake_up_process(timeout->task);
1799:	}

linux-5.10.3/include/linux/timer.h
 153:	#define from_timer(var, callback_timer, timer_fieldname) \
 154:	        container_of(callback_timer, typeof(*var), timer_fieldname)

linux-5.10.3/include/linux/kernel.h
 851:	#define container_of(ptr, type, member) ({                              \
 852:	        void *__mptr = (void *)(ptr);                                   \
 853:	        BUILD_BUG_ON_MSG(!__same_type(*(ptr), ((type *)0)->member) &&   \
 854:	                         !__same_type(*(ptr), void),                    \
 855:	                         "pointer type mismatch in container_of()");    \
 856:	        ((type *)(__mptr - offsetof(type, member))); }
)

• struct process_timer は、後で task を取り出すための構造体。
• __sched schedule_timeout() の引数 timeout と jiffies を加えると、いつ起きるべきかの 時刻が得られる。
• timer_setup_on_stack() で、struct timer_list 構造体を初期化。 function としては、process_timeout() 。
• __mod_time() で、タイマの登録。
• schedule() は、スケジューラ。 現在実行中のプロセスは、スリープする。
• jiffies が増加し、expire に達すると process_timeout() が呼ばれる。
• process_timeout() は、wake_up_process() でスリープしているプロセスを 起こす。
• del_singleshot_timer_sync(), destroy_timer_on_stack() で struct process_timer を後片づけ。

◆High-resolution kernel timers

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

  65:	enum hrtimer_restart {
  66:	        HRTIMER_NORESTART,      /* Timer is not restarted */
  67:	        HRTIMER_RESTART,        /* Timer must be restarted */
  68:	};

 118:	struct hrtimer {
...
 121:	        enum hrtimer_restart            (*function)(struct hrtimer *);
...
 127:	};

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 へ変換する。

    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_forward_now() 等でタイマの時刻を再設定する。)
• ハンドラで HRTIMER_NORESTART を return すると、タイマは再設定されない。

■実行の遅延

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

様々な方法がある。

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

◆空ループ(busy loop)

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

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

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

◆time_befefore()

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

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

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

◆cond_resched()

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

◆小さな遅延

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

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

◆schedule_timeout()

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

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

• 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一般)

■プロセス・スケジューリング関連の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 になって いる。

◆ps -lコマンド

$ /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 とかビデオ・エンコーダとか。
• (対話的な処理で入出力で待ちが多いプロセスの優先度を上げる。)

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

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

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

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

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

■Linux task構造体とnice値

◆task_struct構造体

linux-5.10.3/include/linux/sched.h
 640:	struct task_struct {
...
 649:	        volatile long                   state;
...
 686:	        int                             prio;
 687:	        int                             static_prio;
 688:	        int                             normal_prio;
 689:	        unsigned int                    rt_priority;
 690:	
 691:	        const struct sched_class        *sched_class;
 692:	        struct sched_entity             se;
 693:	        struct sched_rt_entity          rt;
...
 697:	        struct sched_dl_entity          dl;
...
 721:	        unsigned int                    policy;
...
1366:	};

 451:	struct sched_entity {
...
 453:	        struct load_weight              load;
 454:	        struct rb_node                  run_node;
...
 456:	        unsigned int                    on_rq;
...
 458:	        u64                             exec_start;
 459:	        u64                             sum_exec_runtime;
 460:	        u64                             vruntime;
...
 487:	};

 325:	struct load_weight {
 326:	        unsigned long                   weight;
 327:	        u32                             inv_weight;
 328:	};

◆policy

linux-5.10.3/include/uapi/linux/sched.h
 114:	#define SCHED_NORMAL            0
 115:	#define SCHED_FIFO              1
 116:	#define SCHED_RR                2
 117:	#define SCHED_BATCH             3
 118:	/* SCHED_ISO: reserved but not implemented yet */
 119:	#define SCHED_IDLE              5
 120:	#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

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

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

linux-5.10.3/kernel/sys.c
 267:	SYSCALL_DEFINE2(getpriority, int, which, int, who)
 268:	{
 269:	        struct task_struct *g, *p;
 270:	        struct user_struct *user;
 271:	        const struct cred *cred = current_cred();
 272:	        long niceval, retval = -ESRCH;
 273:	        struct pid *pgrp;
 274:	        kuid_t uid;
...
 281:	        switch (which) {
 282:	        case PRIO_PROCESS:
 283:	                if (who)
 284:	                        p = find_task_by_vpid(who);
 285:	                else
 286:	                        p = current;
 287:	                if (p) {
 288:	                        niceval = nice_to_rlimit(task_nice(p));
 289:	                        if (niceval > retval)
 290:	                                retval = niceval;
 291:	                }
 292:	                break;
...
 293:	        case PRIO_PGRP:
...
 304:	        case PRIO_USER:
...
 324:	        }
...
 329:	        return retval;
 330:	}

linux-5.10.3/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-5.10.3/include/linux/sched.h
1678:	static inline int task_nice(const struct task_struct *p)
1679:	{
1680:	        return PRIO_TO_NICE((p)->static_prio);
1681:	}

linux-5.10.3/include/linux/sched/prio.h
  48:	static inline long nice_to_rlimit(long nice)
  49:	{
  50:	        return (MAX_NICE - nice + 1);
  51:	}

• 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

linux-5.10.3/kernel/sched/core.c
8445:	/*
8446:	 * Nice levels are multiplicative, with a gentle 10% change for every
8447:	 * nice level changed. I.e. when a CPU-bound task goes from nice 0 to
8448:	 * nice 1, it will get ~10% less CPU time than another CPU-bound task
8449:	 * that remained on nice 0.
8450:	 *
8451:	 * The "10% effect" is relative and cumulative: from _any_ nice level,
8452:	 * if you go up 1 level, it's -10% CPU usage, if you go down 1 level
8453:	 * it's +10% CPU usage. (to achieve that we use a multiplier of 1.25.
8454:	 * If a task goes up by ~10% and another task goes down by ~10% then
8455:	 * the relative distance between them is ~25%.)
8456:	 */
8457:	const int sched_prio_to_weight[40] = {
8458:	 /* -20 */     88761,     71755,     56483,     46273,     36291,
8459:	 /* -15 */     29154,     23254,     18705,     14949,     11916,
8460:	 /* -10 */      9548,      7620,      6100,      4904,      3906,
8461:	 /*  -5 */      3121,      2501,      1991,      1586,      1277,
8462:	 /*   0 */      1024,       820,       655,       526,       423,
8463:	 /*   5 */       335,       272,       215,       172,       137,
8464:	 /*  10 */       110,        87,        70,        56,        45,
8465:	 /*  15 */        36,        29,        23,        18,        15,
8466:	};

 848:	static void set_load_weight(struct task_struct *p, bool update_load)
 849:	{
 850:	        int prio = p->static_prio - MAX_RT_PRIO;
 851:	        struct load_weight *load = &p->se.load;
...
 869:	                load->weight = scale_load(sched_prio_to_weight[prio]);
 870:	                load->inv_weight = sched_prio_to_wmult[prio];
...
 872:	}

linux-5.10.3/kernel/sched/sched.h
 134:	# 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使い方

linux-5.10.3/kernel/sched/core.c
1561:	static inline void enqueue_task(struct rq *rq, struct task_struct *p, int flags)
1562:	{
...
1572:	        p->sched_class->enqueue_task(rq, p, flags);
1573:	}

1575:	static inline void dequeue_task(struct rq *rq, struct task_struct *p, int flags)
1576:	{
...
1586:	        p->sched_class->dequeue_task(rq, p, flags);
1587:	}

• プロセスのクラスに応じて 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 の時に使われる。

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

5169:	static void __setscheduler(struct rq *rq, struct task_struct *p,
5170:	                           const struct sched_attr *attr, bool keep_boost)
5171:	{
...
5179:	        __setscheduler_params(p, attr);
...
5185:	        p->prio = normal_prio(p);
...
5189:	        if (dl_prio(p->prio))
5190:	                p->sched_class = &dl_sched_class;
5191:	        else if (rt_prio(p->prio))
5192:	                p->sched_class = &rt_sched_class;
5193:	        else
5194:	                p->sched_class = &fair_sched_class;
5195:	}

5143:	static void __setscheduler_params(struct task_struct *p,
5144:	                const struct sched_attr *attr)
5145:	{
5146:	        int policy = attr->sched_policy;
5147:	
5148:	        if (policy == SETPARAM_POLICY)
5149:	                policy = p->policy;
5150:	
5151:	        p->policy = policy;
5152:	
5153:	        if (dl_policy(policy))
5154:	                __setparam_dl(p, attr);
5155:	        else if (fair_policy(policy))
5156:	                p->static_prio = NICE_TO_PRIO(attr->sched_nice);
...
5163:	        p->rt_priority = attr->sched_priority;
5164:	        p->normal_prio = normal_prio(p);
5165:	        set_load_weight(p, true);
5166:	}

• __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)

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(リスト的な見方)

図? runqueueの構造

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

linux-5.10.3/kernel/sched/sched.h
 895:	struct rq {
...
 931:	        struct cfs_rq           cfs;
 932:	        struct rt_rq            rt;
 933:	        struct dl_rq            dl;
...
1051:	};

 519:	struct cfs_rq {
...
 531:	        struct rb_root_cached   tasks_timeline;
...
 537:	        struct sched_entity     *curr;
...
 606:	};

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

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

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

◆Linux red-black treeの基本操作

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

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

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

◆runqueues(red-black tree)

図? runqueueの構造(red-black tree)

◆__enqueue_entity()

linux-5.10.3/kernel/sched/fair.c
 575:	static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
 576:	{
 577:	        struct rb_node **link = &cfs_rq->tasks_timeline.rb_root.rb_node;
 578:	        struct rb_node *parent = NULL;
 579:	        struct sched_entity *entry;
 580:	        bool leftmost = true;
 581:	
 582:	        /*
 583:	         * Find the right place in the rbtree:
 584:	         */
 585:	        while (*link) {
 586:	                parent = *link;
 587:	                entry = rb_entry(parent, struct sched_entity, run_node);
 588:	                /*
 589:	                 * We dont care about collisions. Nodes with
 590:	                 * the same key stay together.
 591:	                 */
 592:	                if (entity_before(se, entry)) {
 593:	                        link = &parent->rb_left;
 594:	                } else {
 595:	                        link = &parent->rb_right;
 596:	                        leftmost = false;
 597:	                }
 598:	        }
 599:	
 600:	        rb_link_node(&se->run_node, parent, link);
 601:	        rb_insert_color_cached(&se->run_node,
 602:	                               &cfs_rq->tasks_timeline, leftmost);
 603:	}
 604:	
 605:	static void __dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
 606:	{
 607:	        rb_erase_cached(&se->run_node, &cfs_rq->tasks_timeline);
 608:	}

 534:	static inline int entity_before(struct sched_entity *a,
 535:	                                struct sched_entity *b)
 536:	{
 537:	        return (s64)(a->vruntime - b->vruntime) < 0;
 538:	}

• __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ごとの仕事

3984:	void scheduler_tick(void)
3985:	{
3986:	        int cpu = smp_processor_id();
3987:	        struct rq *rq = cpu_rq(cpu);
3988:	        struct task_struct *curr = rq->curr;
...
4000:	        curr->sched_class->task_tick(rq, curr, 0);
...
4012:	}

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

◆CFSのentity_tick()

linux-5.10.3/kernel/sched/fair.c
10693:	static void task_tick_fair(struct rq *rq, struct task_struct *curr, int queued)
10694:	{
10695:	        struct cfs_rq *cfs_rq;
10696:	        struct sched_entity *se = &curr->se;
10697:	
10698:	        for_each_sched_entity(se) {
10699:	                cfs_rq = cfs_rq_of(se);
10700:	                entity_tick(cfs_rq, se, queued);
10701:	        }
...
10708:	}

4511:	static void
4512:	entity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr, int queued)
4513:	{
...
4517:	        update_curr(cfs_rq);
...
4544:	}

 842:	static void update_curr(struct cfs_rq *cfs_rq)
 843:	{
 844:	        struct sched_entity *curr = cfs_rq->curr;
 845:	        u64 now = rq_clock_task(rq_of(cfs_rq));
 846:	        u64 delta_exec;
...
 851:	        delta_exec = now - curr->exec_start;
...
 855:	        curr->exec_start = now;
...
 860:	        curr->sum_exec_runtime += delta_exec;
...
 863:	        curr->vruntime += calc_delta_fair(delta_exec, curr);
 864:	        update_min_vruntime(cfs_rq);
...
 875:	}

 671:	static inline u64 calc_delta_fair(u64 delta, struct sched_entity *se)
 672:	{
 673:	        if (unlikely(se->load.weight != NICE_0_LOAD))
 674:	                delta = __calc_delta(delta, NICE_0_LOAD, &se->load);
 675:	
 676:	        return delta;
 677:	}

• 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) モノトニック時刻の利用

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

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

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