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

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

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

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

■今日の大事な話

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

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

■時刻と時間

◆求められる機能

• システム・コール
  • カレンダ時刻の提供: 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 
Tue Jan 24 18:12:50 2023
$ date 
Tue Jan 24 18:12:52 JST 2023
$ 

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 ビットで一周する。
• 上位ビットが変化すると割込みがかかる。
• 省電力モードでも、通常通り動き続ける

◆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)」なら、発火して終わり。

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

linux-6.1.2/include/generated/autoconf.h
1209:	#define CONFIG_HZ 1000

linux-6.1.2/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ビットが取れる。別の変数 に見えるが、実体はリンカのトリックで同じになっている。

  $ nm vmlinux|grep 'D jiffies' 
  ffffffff828079c0 D jiffies
  ffffffff828079c0 D jiffies_64
  ffffffff82807a40 D jiffies_lock
  ffffffff82807a00 D jiffies_seq
  $ 
  

• 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-6.1.2/kernel/time/tick-common.c
  85:	static void tick_periodic(int cpu)
  86:	{
  87:	        if (tick_do_timer_cpu == cpu) {
...
  94:	                do_timer(1);
...
  97:	                update_wall_time();
  98:	        }
  99:	
 100:	        update_process_times(user_mode(get_irq_regs()));
...
 102:	}

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

linux-6.1.2/kernel/time/timekeeping.c
2289:	void do_timer(unsigned long ticks)
2290:	{
2291:	        jiffies_64 += ticks;
...
2293:	}

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

■カレンダー時刻の実装

◆struct timekeeper/xtime

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

linux-6.1.2/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-6.1.2/include/linux/time64.h
  13:	struct timespec64 {
  14:	        time64_t        tv_sec;                 /* seconds */
  15:	        long            tv_nsec;                /* nanoseconds */
  16:	};

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

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

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

linux-6.1.2/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-6.1.2/kernel/time/timekeeping.c
 815:	void ktime_get_real_ts64(struct timespec64 *ts)
 816:	{
 817:	        struct timekeeper *tk = &tk_core.timekeeper;
 818:	        unsigned int seq;
 819:	        u64 nsecs;
...
 826:	                ts->tv_sec = tk->xtime_sec;
 827:	                nsecs = timekeeping_get_ns(&tk->tkr_mono);
...
 831:	        ts->tv_nsec = 0;
 832:	        timespec64_add_ns(ts, nsecs);
 833:	}

• 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-6.1.2/include/linux/timer.h
  11:	struct timer_list {
...
  17:	        unsigned long           expires;
  18:	        void                    (*function)(struct timer_list *);
...
  24:	};

jiffies が増加して expires に達すれば、(*function)(tl) を呼ぶ。 引数 tl は、struct 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 *)を得るには、次の ように from_timer() マクロか container_of() マクロを用いる。

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 から外側の構造体を求める

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

linux-6.1.2/include/linux/container_of.h
  17:	#define container_of(ptr, type, member) ({                              \
  18:	        void *__mptr = (void *)(ptr);                                   \
...
  22:	        ((type *)(__mptr - offsetof(type, member))); })

◆schedule_timeout()

linux-6.1.2/kernel/time/timer.c
1853:	struct process_timer {
1854:	        struct timer_list timer;
1855:	        struct task_struct *task;
1856:	};

1896:	signed long __sched schedule_timeout(signed long timeout)
1897:	{
1898:	        struct process_timer timer;
1899:	        unsigned long expire;
...
1930:	        expire = timeout + jiffies;
1931:	
1932:	        timer.task = current;
1933:	        timer_setup_on_stack(&timer.timer, process_timeout, 0);
1934:	        __mod_timer(&timer.timer, expire, MOD_TIMER_NOTPENDING);
1935:	        schedule();
1936:	        del_singleshot_timer_sync(&timer.timer);
1937:	
1938:	        /* Remove the timer from the object tracker */
1939:	        destroy_timer_on_stack(&timer.timer);
1940:	
1941:	        timeout = expire - jiffies;
1942:	
1943:	 out:
1944:	        return timeout < 0 ? 0 : timeout;
1945:	}

1858:	static void process_timeout(struct timer_list *t)
1859:	{
1860:	        struct process_timer *timeout = from_timer(timeout, t, timer);
1861:	
1862:	        wake_up_process(timeout->task);
1863:	}

• 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-6.1.2/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-6.1.2/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 コマンドで値を大きくできる。最大19。 (特権ユーザは、値を小さくできる。最小-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-6.1.2/include/linux/sched.h
 737:	struct task_struct {
...
 745:	        unsigned int                    __state;
...
 783:	        int                             prio;
 784:	        int                             static_prio;
 785:	        int                             normal_prio;
 786:	        unsigned int                    rt_priority;
 787:	
 788:	        struct sched_entity             se;
 789:	        struct sched_rt_entity          rt;
 790:	        struct sched_dl_entity          dl;
 791:	        const struct sched_class        *sched_class;
...
 827:	        unsigned int                    policy;
...
1546:	};

 547:	struct sched_entity {
...
 549:	        struct load_weight              load;
 550:	        struct rb_node                  run_node;
...
 552:	        unsigned int                    on_rq;
 553:	
 554:	        u64                             exec_start;
 555:	        u64                             sum_exec_runtime;
 556:	        u64                             vruntime;
...
 581:	};

 407:	struct load_weight {
 408:	        unsigned long                   weight;
 409:	        u32                             inv_weight;
 410:	};

struct sched_entity で重要なフィールド。詳しくは後述。

• run_node: red-black tree の節
• vruntime: 各プロセスが消費したCPU時間。ナノ秒単位。 red-black tree の節で使われるキー。

◆policy

linux-6.1.2/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-6.1.2/kernel/sys.c
 281:	SYSCALL_DEFINE2(getpriority, int, which, int, who)
 282:	{
 283:	        struct task_struct *g, *p;
 284:	        struct user_struct *user;
 285:	        const struct cred *cred = current_cred();
 286:	        long niceval, retval = -ESRCH;
 287:	        struct pid *pgrp;
 288:	        kuid_t uid;
...
 294:	        switch (which) {
 295:	        case PRIO_PROCESS:
 296:	                if (who)
 297:	                        p = find_task_by_vpid(who);
 298:	                else
 299:	                        p = current;
 300:	                if (p) {
 301:	                        niceval = nice_to_rlimit(task_nice(p));
 302:	                        if (niceval > retval)
 303:	                                retval = niceval;
 304:	                }
 305:	                break;
 306:	        case PRIO_PGRP:
...
 319:	        case PRIO_USER:
...
 339:	        }
...
 343:	        return retval;
 344:	}

linux-6.1.2/include/linux/sched/prio.h
   5:	#define MAX_NICE        19
   6:	#define MIN_NICE        -20
   7:	#define NICE_WIDTH      (MAX_NICE - MIN_NICE + 1)
...
  16:	#define MAX_RT_PRIO             100
  17:	
  18:	#define MAX_PRIO                (MAX_RT_PRIO + NICE_WIDTH)
  19:	#define DEFAULT_PRIO            (MAX_RT_PRIO + NICE_WIDTH / 2)
...
  26:	#define NICE_TO_PRIO(nice)      ((nice) + DEFAULT_PRIO)
  27:	#define PRIO_TO_NICE(prio)      ((prio) - DEFAULT_PRIO)

1889:	/**
1890:	 * task_nice - return the nice value of a given task.
1891:	 * @p: the task in question.
1892:	 *
1893:	 * Return: The nice value [ -20 ... 0 ... 19 ].
1894:	 */
1895:	static inline int task_nice(const struct task_struct *p)
1896:	{
1897:	        return PRIO_TO_NICE((p)->static_prio);
1898:	}

linux-6.1.2/include/linux/sched/prio.h
  32:	static inline long nice_to_rlimit(long nice)
  33:	{
  34:	        return (MAX_NICE - nice + 1);
  35:	}

• 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-6.1.2/kernel/sched/core.c
11186:	/*
11187:	 * Nice levels are multiplicative, with a gentle 10% change for every
11188:	 * nice level changed. I.e. when a CPU-bound task goes from nice 0 to
11189:	 * nice 1, it will get ~10% less CPU time than another CPU-bound task
11190:	 * that remained on nice 0.
11191:	 *
11192:	 * The "10% effect" is relative and cumulative: from _any_ nice level,
11193:	 * if you go up 1 level, it's -10% CPU usage, if you go down 1 level
11194:	 * it's +10% CPU usage. (to achieve that we use a multiplier of 1.25.
11195:	 * If a task goes up by ~10% and another task goes down by ~10% then
11196:	 * the relative distance between them is ~25%.)
11197:	 */
11198:	const int sched_prio_to_weight[40] = {
11199:	 /* -20 */     88761,     71755,     56483,     46273,     36291,
11200:	 /* -15 */     29154,     23254,     18705,     14949,     11916,
11201:	 /* -10 */      9548,      7620,      6100,      4904,      3906,
11202:	 /*  -5 */      3121,      2501,      1991,      1586,      1277,
11203:	 /*   0 */      1024,       820,       655,       526,       423,
11204:	 /*   5 */       335,       272,       215,       172,       137,
11205:	 /*  10 */       110,        87,        70,        56,        45,
11206:	 /*  15 */        36,        29,        23,        18,        15,
11207:	};

1260:	static void set_load_weight(struct task_struct *p, bool update_load)
1261:	{
1262:	        int prio = p->static_prio - MAX_RT_PRIO;
1263:	        struct load_weight *load = &p->se.load;
1264:	
...
1281:	                load->weight = scale_load(sched_prio_to_weight[prio]);
1282:	                load->inv_weight = sched_prio_to_wmult[prio];
...
1284:	}

linux-6.1.2/kernel/sched/sched.h
 400:	# define SCHED_FIXEDPOINT_SHIFT         10
 401:	# define SCHED_FIXEDPOINT_SCALE         (1L << SCHED_FIXEDPOINT_SHIFT)


linux-6.1.2/kernel/sched/sched.h
 144:	# define scale_load(w)          ((w) << SCHED_FIXEDPOINT_SHIFT)

• 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-6.1.2/kernel/sched/core.c
2049:	static inline void enqueue_task(struct rq *rq, struct task_struct *p, int flags)
2050:	{
...
2060:	        p->sched_class->enqueue_task(rq, p, flags);
...
2064:	}

2066:	static inline void dequeue_task(struct rq *rq, struct task_struct *p, int flags)
2067:	{
...
2080:	        p->sched_class->dequeue_task(rq, p, flags);
2081:	}

• プロセスのクラスに応じて 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-6.1.2/kernel/sched/core.c
7433:	static int __sched_setscheduler(struct task_struct *p,
7434:	                                const struct sched_attr *attr,
7435:	                                bool user, bool pi)
7436:	{
...
7613:	                __setscheduler_params(p, attr);
7614:	                __setscheduler_prio(p, newprio);
...
7654:	}

7329:	static void __setscheduler_params(struct task_struct *p,
7330:	                const struct sched_attr *attr)
7331:	{
7332:	        int policy = attr->sched_policy;
7333:	
7334:	        if (policy == SETPARAM_POLICY)
7335:	                policy = p->policy;
7336:	
7337:	        p->policy = policy;
7338:	
7339:	        if (dl_policy(policy))
7340:	                __setparam_dl(p, attr);
7341:	        else if (fair_policy(policy))
7342:	                p->static_prio = NICE_TO_PRIO(attr->sched_nice);
...
7349:	        p->rt_priority = attr->sched_priority;
7350:	        p->normal_prio = normal_prio(p);
7351:	        set_load_weight(p, true);
7352:	}

6849:	static void __setscheduler_prio(struct task_struct *p, int prio)
6850:	{
6851:	        if (dl_prio(prio))
6852:	                p->sched_class = &dl_sched_class;
6853:	        else if (rt_prio(prio))
6854:	                p->sched_class = &rt_sched_class;
6855:	        else
6856:	                p->sched_class = &fair_sched_class;
6857:	
6858:	        p->prio = prio;
6859:	}

• __setscheduler_prio() は、 task_struct の sched_class を p->prio の値に応じて &dl_sched_class か &rt_sched_class か &fair_sched_class のいずれかを指すようにする。
• __setscheduler_params() は、 policy に応じて task_struct の static_prio, rt_priority, normal_prio, se.load 等を設定する。

■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-6.1.2/kernel/sched/core.c
 114:	DEFINE_PER_CPU_SHARED_ALIGNED(struct rq, runqueues);

linux-6.1.2/kernel/sched/sched.h
 954:	struct rq {
...
 990:	        struct cfs_rq           cfs;
 991:	        struct rt_rq            rt;
 992:	        struct dl_rq            dl;
...
1153:	};

 550:	struct cfs_rq {
...
 568:	        struct rb_root_cached   tasks_timeline;
...
 574:	        struct sched_entity     *curr;
...
 650:	};

• (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-6.1.2/kernel/sched/fair.c
 628:	static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
 629:	{
 630:	        rb_add_cached(&se->run_node, &cfs_rq->tasks_timeline, __entity_less);
 631:	}

 633:	static void __dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
 634:	{
 635:	        rb_erase_cached(&se->run_node, &cfs_rq->tasks_timeline);
 636:	}

 620:	static inline bool __entity_less(struct rb_node *a, const struct rb_node *b)
 621:	{
 622:	        return entity_before(__node_2_se(a), __node_2_se(b));
 623:	}

 583:	static inline bool entity_before(struct sched_entity *a,
 584:	                                struct sched_entity *b)
 585:	{
 586:	        return (s64)(a->vruntime - b->vruntime) < 0;
 587:	}

 589:	#define __node_2_se(node) \
 590:	        rb_entry((node), struct sched_entity, run_node)

linux-6.1.2/include/linux/rbtree.h
  28:	#define rb_entry(ptr, type, member) container_of(ptr, type, member)

 164:	static __always_inline struct rb_node *
 165:	rb_add_cached(struct rb_node *node, struct rb_root_cached *tree,
 166:	              bool (*less)(struct rb_node *, const struct rb_node *))
 167:	{
 168:	        struct rb_node **link = &tree->rb_root.rb_node;
 169:	        struct rb_node *parent = NULL;
 170:	        bool leftmost = true;
 171:	
 172:	        while (*link) {
 173:	                parent = *link;
 174:	                if (less(node, parent)) {
 175:	                        link = &parent->rb_left;
 176:	                } else {
 177:	                        link = &parent->rb_right;
 178:	                        leftmost = false;
 179:	                }
 180:	        }
 181:	
 182:	        rb_link_node(node, parent, link);
 183:	        rb_insert_color_cached(node, tree, leftmost);
 184:	
 185:	        return leftmost ? node : NULL;
 186:	}

• CFS の関数 __enqueue_entity() は、rb_add_cached() を呼び出し、平衡二分探索木の一種、red-black tree に節を 追加している。この時、引数として関数 __entity_less() へのポインタを渡している。
• CFS の関数 __dequeue_entity() は、rb_erase_cached() を呼び出して red-black tree から節を取り出す。
• __entity_less() は、red-black tree の節 a, b を引数に取り、 entity_before() を呼び出して、a と b を比較し、a が b より小さければ真を返す。 __node_2_se() は、red-black tree　の節から、 container_of() を使って struct sched_entity * を取り出す。
• entity_before() は、引数として2 つの struct sched_entity * を取り、 vruntime を比較している。
• 結果として、red-black tree は、vruntime が小さい順に並ぶ。 vruntime が小さいほど左に来る。
• entity_before() で現在着目しているノードと挿入したいデータの vruntime を比較する。
• rb_add_cached() は、red-black tree に節を 追加している。 引数の関数 less() を呼び出し、 挿入したいデータのvruntime が現在の節より小さければ、左(&parent->rb_left), 大きければ右(&parent->rb_right) に進む。
• 挿入すべき箇所が見つかる。rb_link_node() で挿入する。
• 最後に rb_insert_color() を呼び出して、バランスを回復する。 この時、一番左なら、キャッシュとして cfs_rq->tasks_timeline->rb_leftmost にも保存。

◆tickごとの仕事

linux-6.1.2/kernel/sched/core.c
5463:	void scheduler_tick(void)
5464:	{
5465:	        int cpu = smp_processor_id();
5466:	        struct rq *rq = cpu_rq(cpu);
5467:	        struct task_struct *curr = rq->curr;
...
5480:	        curr->sched_class->task_tick(rq, curr, 0);
...
5497:	}

• CPU ごとの run queue から現在実行中のプロセスの tast_strut を取り出す。
• その task_struct の sched_class クラスの関数 task_tick() を呼び出す。

◆CFSのentity_tick()

linux-6.1.2/kernel/sched/fair.c
11740:	static void task_tick_fair(struct rq *rq, struct task_struct *curr, int queued)
11741:	{
11742:	        struct cfs_rq *cfs_rq;
11743:	        struct sched_entity *se = &curr->se;
11744:	
11745:	        for_each_sched_entity(se) {
11746:	                cfs_rq = cfs_rq_of(se);
11747:	                entity_tick(cfs_rq, se, queued);
11748:	        }
...
11757:	}

5036:	static void
5037:	entity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr, int queued)
5038:	{
...
5042:	        update_curr(cfs_rq);
...
5069:	}

...
 882:	static void update_curr(struct cfs_rq *cfs_rq)
 883:	{
 884:	        struct sched_entity *curr = cfs_rq->curr;
 885:	        u64 now = rq_clock_task(rq_of(cfs_rq));
 886:	        u64 delta_exec;
 887:	
...
 891:	        delta_exec = now - curr->exec_start;
...
 895:	        curr->exec_start = now;
...
 905:	        curr->sum_exec_runtime += delta_exec;
...
 908:	        curr->vruntime += calc_delta_fair(delta_exec, curr);
 909:	        update_min_vruntime(cfs_rq);
...
 920:	}

 694:	static inline u64 calc_delta_fair(u64 delta, struct sched_entity *se)
 695:	{
 696:	        if (unlikely(se->load.weight != NICE_0_LOAD))
 697:	                delta = __calc_delta(delta, NICE_0_LOAD, &se->load);
 698:	
 699:	        return delta;
 700:	}

• 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)が使われる。
• nice値が0の時(se->load.weight == NICE_0_LOAD)は、そのまま足す。

◆/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

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

★問題(403) struct timer_listの利用

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

2023/01/27 問題を少し修正します。回答は同じで良いです。空欄の順番が少しずれています。

struct timer_list my_timer;

int my_arg_a,my_arg_b,my_arg_c;

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

void my_timer_func(/*省略*/) {
     h( my_arg_a,my_arg_b,my_arg_c );
}

★問題(404) sched_class

またポリシーがSCHED_NORMAL の時、 struct task_struct のフィールドで ある期間に消費したCPU時間(ナノ秒単位)を保持するフィールドを答えなさい。

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

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

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