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

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

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

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

■今日の大事な話

時刻と時間の管理

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

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

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

■時刻と時間

◆求められる機能

システム・コール
- カレンダ時刻の提供: gettimeofday(), settimeofday(), time(), adjtime(), ntp_gettime(), ntp_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
$ ./gettimeofday-print 
Mon Jan 27 11:50:00 2026
$ date 
Mon Jan 27 11:50:01 JST 2026
$

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

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

参考: システムプログラム/select()による複数のクライアントに対するサービスの同時提供

なにもしない時間切れ。

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

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

コンピュータによって違う。ここでは、PC/AT CPU がx86の標準的なPC) の話。

◆基本的なモデル

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

図?　発振器、カウンタ、比較、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 毎に独立。

カウンタと初期値は 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)」なら、発火して終わり。

◆Linux clocksource

Linux カーネルが時間管理のために利用可能なハードウェア。

$ cat /sys/devices/system/clocksource/clocksource0/available_clocksource 
tsc acpi_pm
$ cat /sys/devices/system/clocksource/clocksource0/current_clocksource 
tsc
$

■jiffiesとHZ

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

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

$ grep CONFIG_HZ .config 
# CONFIG_HZ_PERIODIC is not set 
# CONFIG_HZ_100 is not set 
# CONFIG_HZ_250 is not set 
# CONFIG_HZ_300 is not set 
CONFIG_HZ_1000=y
CONFIG_HZ=1000
$

利用例

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

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

linux-6.18.2/include/linux/jiffies.h
  85:	extern u64 __cacheline_aligned_in_smp jiffies_64;
  86:	extern unsigned long volatile __cacheline_aligned_in_smp __jiffy_arch_data jiffies;

実体は、jiffies_64 という64ビットの変数。

jiffies という名前でアクセスすると、下位32ビットが取れる。別の変数に見えるが、実体はリンカのトリックで同じになっている。

$ ls -l vmlinux 
-rwxr-xr-x 1 yas prof 52309776 Jan  2 12:54 vmlinux
$ nm vmlinux | grep 'D jiffies' 
ffffffff82c099c0 D jiffies
ffffffff82c099c0 D jiffies_64
ffffffff82c09a80 D jiffies_lock
ffffffff82c09a40 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()

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

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

linux-6.18.2/kernel/time/tick-common.c
  86:	static void tick_periodic(int cpu)
  87:	{
  88:	        if (READ_ONCE(tick_do_timer_cpu) == cpu) {
...
  95:	                do_timer(1);
...
  98:	                update_wall_time();
  99:	        }
 100:	
 101:	        update_process_times(user_mode(get_irq_regs()));
...
 103:	}

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

linux-6.18.2/kernel/time/timekeeping.c
2528:	void do_timer(unsigned long ticks)
2529:	{
2530:	        jiffies_64 += ticks;
...
2532:	}

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-6.18.2/include/linux/timekeeper_internal.h
 140:	struct timekeeper {
...
 142:	        struct tk_read_base     tkr_mono;
...
 145:	        u64                     xtime_sec;
...
 183:	};

  50:	struct tk_read_base {
  51:	        struct clocksource      *clock;
...
  55:	        u32                     shift;
  56:	        u64                     xtime_nsec;
...
  59:	};

linux-6.18.2/include/linux/time64.h
  13:	struct timespec64 {
  14:	        time64_t        tv_sec;                 /* seconds */
  15:	        long            tv_nsec;                /* nanoseconds */
  16:	};

linux-6.18.2/kernel/time/timekeeping.c
 202:	static inline struct timespec64 tk_xtime(const struct timekeeper *tk)
 203:	{
 204:	        struct timespec64 ts;
 205:	
 206:	        ts.tv_sec = tk->xtime_sec;
 207:	        ts.tv_nsec = (long)(tk->tkr_mono.xtime_nsec >> tk->tkr_mono.shift);
 208:	        return ts;
 209:	}

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

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

linux-6.18.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.18.2/kernel/time/timekeeping.c
 793:	void ktime_get_real_ts64(struct timespec64 *ts)
 794:	{
 795:	        struct timekeeper *tk = &tk_core.timekeeper;
 796:	        unsigned int seq;
 797:	        u64 nsecs;
...
 804:	                ts->tv_sec = tk->xtime_sec;
 805:	                nsecs = timekeeping_get_ns(&tk->tkr_mono);
...
 809:	        ts->tv_nsec = 0;
 810:	        timespec64_add_ns(ts, nsecs);
 811:	}

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-6.18.2/include/linux/timer_types.h
   8:	struct timer_list {
...
  14:	        unsigned long           expires;
  15:	        void                    (*function)(struct timer_list *);
...
  21:	};

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 timer_list *が渡される。普通、これだけでは不十分で、独自のデータ(構造体へのへポインタ)が必要になる。

(*function)() で独自のデータ(以下の例では struct s1 *)を得るには、次のように from_timer() マクロか container_of() マクロを用いる。

◆container_of()

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

図?　独自の構造体、struct timer_list timer、from_timer、container_ob
図? timer_list から外側の構造体を求める

linux-6.18.2/include/linux/timer.h
 132:	#define from_timer(var, callback_timer, timer_fieldname) \
 133:	        container_of(callback_timer, typeof(*var), timer_fieldname)

linux-6.18.2/include/linux/container_of.h
  19:	#define container_of(ptr, type, member) ({                              \
  20:	        void *__mptr = (void *)(ptr);                                   \
...
  24:	        ((type *)(__mptr - offsetof(type, member))); })

linux-6.18.2/include/linux/stddef.h
  16:	#define offsetof(TYPE, MEMBER)  __builtin_offsetof(TYPE, MEMBER)

linux-6.18.2/tools/include/linux/kernel.h
  26:	#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

◆schedule_timeout()

引数で指定された時間だけしばらく待つ。時間の単位は、tick。

linux-6.18.2/kernel/time/sleep_timeout.c
  18:	struct process_timer {
  19:	        struct timer_list timer;
  20:	        struct task_struct *task;
  21:	};

  61:	signed long __sched schedule_timeout(signed long timeout)
  62:	{
  63:	        struct process_timer timer;
  64:	        unsigned long expire;
...
  93:	        expire = timeout + jiffies;
  94:	
  95:	        timer.task = current;
  96:	        timer_setup_on_stack(&timer.timer, process_timeout, 0);
  97:	        timer.timer.expires = expire;
  98:	        add_timer(&timer.timer);
  99:	        schedule();
 100:	        timer_delete_sync(&timer.timer);
 101:	
 102:	        /* Remove the timer from the object tracker */
 103:	        timer_destroy_on_stack(&timer.timer);
 104:	
 105:	        timeout = expire - jiffies;
 106:	
 107:	 out:
 108:	        return timeout < 0 ? 0 : timeout;
 109:	}
 110:	EXPORT_SYMBOL(schedule_timeout);

  23:	static void process_timeout(struct timer_list *t)
  24:	{
  25:	        struct process_timer *timeout = timer_container_of(timeout, t, timer);
  26:	
  27:	        wake_up_process(timeout->task);
  28:	}

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

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

linux-6.18.2/include/linux/hrtimer.h
  35:	enum hrtimer_mode {
  36:	        HRTIMER_MODE_ABS        = 0x00,
  37:	        HRTIMER_MODE_REL        = 0x01,
...
  56:	};

linux-6.12.7/include/linux/hrtimer_types.h
  13:	enum hrtimer_restart {
  14:	        HRTIMER_NORESTART,      /* Timer is not restarted */
  15:	        HRTIMER_RESTART,        /* Timer must be restarted */
  16:	};

  39:	struct hrtimer {
...
  42:	        enum hrtimer_restart            (*function)(struct hrtimer *);
...
  48:	};

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

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_forward_now() 等でタイマの時刻を再設定する。)
ハンドラで 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,delay))
    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-6.18.2/include/linux/jiffies.h
 127:	#define time_after(a,b)         \
 128:	        (typecheck(unsigned long, a) && \
 129:	         typecheck(unsigned long, b) && \
 130:	         ((long)((b) - (a)) < 0))
...
 138:	#define time_before(a,b)        time_after(b,a)
...
 147:	#define time_after_eq(a,b)      \
 148:	        (typecheck(unsigned long, a) && \
 149:	         typecheck(unsigned long, b) && \
 150:	         ((long)((a) - (b)) >= 0))
...
 158:	#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,delay))
    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 コマンドで値を大きくできる。最大19。 (特権ユーザは、値を小さくできる。最小-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-6.18.2/include/linux/sched.h
 819:	struct task_struct {
...
 827:	        unsigned int                    __state;
...
 865:	        int                             prio;
 866:	        int                             static_prio;
 867:	        int                             normal_prio;
 868:	        unsigned int                    rt_priority;
 869:	
 870:	        struct sched_entity             se;
 871:	        struct sched_rt_entity          rt;
 872:	        struct sched_dl_entity          dl;
...
 877:	        const struct sched_class        *sched_class;
...
 919:	        unsigned int                    policy;
...
1668:	} __attribute__ ((aligned (64)));

 570:	struct sched_entity {
 571:	        /* For load-balancing: */
 572:	        struct load_weight              load;
 573:	        struct rb_node                  run_node;
 574:	        u64                             deadline;
...
 579:	        unsigned char                   on_rq;
...
 585:	        u64                             exec_start;
 586:	        u64                             sum_exec_runtime;
 587:	        u64                             prev_sum_exec_runtime;
 588:	        u64                             vruntime;
...
 595:	                s64                     vlag;
...

 455:	struct load_weight {
 456:	        unsigned long                   weight;
 457:	        u32                             inv_weight;
 458:	};

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

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

run_node: red-black tree の節
vruntime: CFS では各プロセスが消費したCPU時間。ナノ秒単位。 red-black tree の節で使われるキー。
deadline: EEVDF では仮想的な deadline 。 red-black tree の節で使われるキー。

◆policy

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

linux-6.18.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
 121:	#define SCHED_EXT               7

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

◆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-6.18.2/kernel/sys.c
 329:	SYSCALL_DEFINE2(getpriority, int, which, int, who)
 330:	{
 331:	        struct task_struct *g, *p;
 332:	        struct user_struct *user;
 333:	        const struct cred *cred = current_cred();
 334:	        long niceval, retval = -ESRCH;
 335:	        struct pid *pgrp;
 336:	        kuid_t uid;
...
 342:	        switch (which) {
 343:	        case PRIO_PROCESS:
 344:	                if (who)
 345:	                        p = find_task_by_vpid(who);
 346:	                else
 347:	                        p = current;
 348:	                if (p) {
 349:	                        niceval = nice_to_rlimit(task_nice(p));
 350:	                        if (niceval > retval)
 351:	                                retval = niceval;
 352:	                }
 353:	                break;
 354:	        case PRIO_PGRP:
...
 367:	        case PRIO_USER:
...
 383:	                }
...
 391:	        return retval;
 392:	}

linux-6.18.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
...
  19:	#define MAX_PRIO                (MAX_RT_PRIO + NICE_WIDTH)
...
  27:	#define NICE_TO_PRIO(nice)      ((nice) + DEFAULT_PRIO)
  28:	#define PRIO_TO_NICE(prio)      ((prio) - DEFAULT_PRIO)
...
  33:	static inline long nice_to_rlimit(long nice)
  34:	{
  35:	        return (MAX_NICE - nice + 1);
  36:	}

linux-6.18.2/include/linux/sched.h
1891:	static inline int task_nice(const struct task_struct *p)
1892:	{
1893:	        return PRIO_TO_NICE((p)->static_prio);
1894:	}

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.35/sysdeps/unix/sysv/linux/getpriority.c
  27:	#define PZERO 20
...
  34:	int
  35:	__getpriority (enum __priority_which which, id_t who)
  36:	{
  37:	  int res;
  38:	
  39:	  res = INLINE_SYSCALL (getpriority, 2, (int) which, who);
  40:	  if (res >= 0)
  41:	    res = PZERO - res;
  42:	  return res;
  43:	}
  44:	libc_hidden_def (__getpriority)
  45:	weak_alias (__getpriority, getpriority)

◆se.load.weight

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

linux-6.18.2/kernel/sched/core.c
10330:	/*
10331:	 * Nice levels are multiplicative, with a gentle 10% change for every
10332:	 * nice level changed. I.e. when a CPU-bound task goes from nice 0 to
10333:	 * nice 1, it will get ~10% less CPU time than another CPU-bound task
10334:	 * that remained on nice 0.
10335:	 *
10336:	 * The "10% effect" is relative and cumulative: from _any_ nice level,
10337:	 * if you go up 1 level, it's -10% CPU usage, if you go down 1 level
10338:	 * it's +10% CPU usage. (to achieve that we use a multiplier of 1.25.
10339:	 * If a task goes up by ~10% and another task goes down by ~10% then
10340:	 * the relative distance between them is ~25%.)
10341:	 */
10342:	const int sched_prio_to_weight[40] = {
10343:	 /* -20 */     88761,     71755,     56483,     46273,     36291,
10344:	 /* -15 */     29154,     23254,     18705,     14949,     11916,
10345:	 /* -10 */      9548,      7620,      6100,      4904,      3906,
10346:	 /*  -5 */      3121,      2501,      1991,      1586,      1277,
10347:	 /*   0 */      1024,       820,       655,       526,       423,
10348:	 /*   5 */       335,       272,       215,       172,       137,
10349:	 /*  10 */       110,        87,        70,        56,        45,
10350:	 /*  15 */        36,        29,        23,        18,        15,
10351:	};

1432:	void set_load_weight(struct task_struct *p, bool update_load)
1433:	{
1434:	        int prio = p->static_prio - MAX_RT_PRIO;
1435:	        struct load_weight lw;
...
1441:	                lw.weight = scale_load(sched_prio_to_weight[prio]);
1442:	                lw.inv_weight = sched_prio_to_wmult[prio];
...
1452:	                p->se.load = lw;
1453:	}

linux-6.18.2/include/linux/sched.h
 448:	# define SCHED_FIXEDPOINT_SHIFT         10
 449:	# define SCHED_FIXEDPOINT_SCALE         (1L << SCHED_FIXEDPOINT_SHIFT)

linux-6.18.2/kernel/sched/sched.h
 146:	#ifdef CONFIG_64BIT
 147:	# define NICE_0_LOAD_SHIFT      (SCHED_FIXEDPOINT_SHIFT + SCHED_FIXEDPOINT_SHIFT)
 148:	# define scale_load(w)          ((w) << SCHED_FIXEDPOINT_SHIFT)
...
 157:	#else
 158:	# define NICE_0_LOAD_SHIFT      (SCHED_FIXEDPOINT_SHIFT)
 159:	# define scale_load(w)          (w)
 160:	# define scale_load_down(w)     (w)
 161:	#endif

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-6.18.2/kernel/sched/sched.h
2398:	struct sched_class {
...
2404:	        void (*enqueue_task) (struct rq *rq, struct task_struct *p, int flags);
2405:	        bool (*dequeue_task) (struct rq *rq, struct task_struct *p, int flags);
...
2412:	        struct task_struct *(*pick_task)(struct rq *rq);
...
2440:	        void (*task_tick)(struct rq *rq, struct task_struct *p, int queued);
...
2469:	};

linux-6.18.2/kernel/sched/core.c
2080:	void enqueue_task(struct rq *rq, struct task_struct *p, int flags)
2081:	{
...
2092:	        p->sched_class->enqueue_tas(krq, p, flags);
...
2101:	}

2106:	inline bool dequeue_task(struct rq *rq, struct task_struct *p, int flags)
2107:	{
...
2124:	        return p->sched_class->dequeue_task(rq, p, flags);
2125:	}

プロセスのクラスに応じて 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.18.2/kernel/sched/syscalls.c
 513:	int __sched_setscheduler(struct task_struct *p,
 514:	                         const struct sched_attr *attr,
 515:	                         bool user, bool pi)
 516:	{
...
 696:	        next_class = __setscheduler_class(policy, newprio);
...
 709:	                __setscheduler_params(p, attr);
 710:	                p->sched_class = next_class;
 711:	                p->prio = newprio;
...
 753:	}

 290:	static void __setscheduler_params(struct task_struct *p,
 291:	                const struct sched_attr *attr)
 292:	{
 293:	        int policy = attr->sched_policy;
 294:	
 295:	        if (policy == SETPARAM_POLICY)
 296:	                policy = p->policy;
 297:	
 298:	        p->policy = policy;
 299:	
 300:	        if (dl_policy(policy))
...
 302:	        else if (fair_policy(policy))
 303:	                __setparam_fair(p, attr);
...
 319:	        p->normal_prio = normal_prio(p);
 320:	        set_load_weight(p, true);
 321:	}

linux-6.18.2/kernel/sched/core.c
7272:	const struct sched_class *__setscheduler_class(int policy, int prio)
7273:	{
7274:	        if (dl_prio(prio))
7275:	                return &dl_sched_class;
7276:	
7277:	        if (rt_prio(prio))
7278:	                return &rt_sched_class;
7279:	
7280:	#ifdef CONFIG_SCHED_CLASS_EXT
7281:	        if (task_should_scx(policy))
7282:	                return &ext_sched_class;
7283:	#endif
7284:	
7285:	        return &fair_sched_class;
7286:	}

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

■普通のスケジューリング(SCHED_NORMAL,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
$

たとえば、もし優先度が同じプロセスAとプロセスBが存在した時には、15ミリ秒の間にプロセスAに7.5ミリ秒、プロセスBに7.5ミリ秒のCPU資源を割り当てるようにがんばる。

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

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

参考:

https://docs.kernel.org/scheduler/sched-design-CFS.html,The Linux Kernel/CFS Scheduler

◆The Earliest Eligible Virtual Deadline First (EEVDF) Scheduler

Linux 6.6 から CFS に代り EEVDF (Earliest Eligible Virtual Deadline First) (Earliest Virtual Deadline First) というスケジューラが使えるようになった。

EEVDF スケジューラの目標は CFS と同じ。使用可能なCPU時間をシステム内のすべての実行可能なタスク間で均等に分割すること。 EDF (Earliest Deadline First) は、実時間のスケジューリング方式だが、 EEVDF は、名前は似ているが、fair を目指している。

例:

A, B, C という 3 つの実行可能な CPU-bound のプロセスがある。どれも実行されていない。 Lag値の合計は0になる。

プロセス A B C

Lag値 0 0 0

vruntime 0 0 0

deadline 30 30 30
Lag値が0か正なら、スケジュールされる資格がある(eligibleである)。スケジューラが資格があるプロセスとして A を選び、30 ミリ秒実行した。本来なら、各タスクは 10 ミリ秒(30/3)実行すべきであった。 A, B, C の Lag 値に 10 ミリ秒を足す。ただ、A は、30 ミリ秒実行したので、30 ミリ秒を引く。

プロセス A B C

Lag値 -20 10 10

vruntime 30 0 0

deadline 60 30 30
A の lag値は、マイナスになり、実行される資格がなくなる(eligibleではない)。スケジューラは、資格があるものの中から B を選んで、また 30 ミリ秒実行する。 A, B, C の Lag 値に 10 ミリ秒を足す。ただ、B は、30 ミリ秒実行したので、30 ミリ秒を引く。

プロセス A B C

Lag値 -10 -10 20

vruntime 30 60 0

deadline 60 90 30
次にスケジューラは、資格がある C を選んで、30 ミリ秒実行する。 A, B, C の Lag 値に 10 ミリ秒を足す。ただ、C は、30 ミリ秒実行したので、30 ミリ秒を引く。

プロセス A B C

Lag値 0 0 0

vruntime 30 60 90

deadline 60 90 120

vruntime は、そのプロセスがCPUを消費すると(nice値で調整して)増やす。
プロセスが生成した後など、vruntime の初期値は、その時の vruntime の最小値。
deadline は、vruntime + slice で設定する。プロセスは、slice の間は動き続ける。
slice を使い果たすと、vruntime を増やし、さらに、vruntime + slice で新たな deadline を設定する。

参考:

◆runqueues(リスト的な見方)

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

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

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

linux-6.18.2/kernel/sched/sched.h
1119:	struct rq {
...
1147:	        struct cfs_rq           cfs;
1148:	        struct rt_rq            rt;
1149:	        struct dl_rq            dl;
1150:	#ifdef CONFIG_SCHED_CLASS_EXT
1151:	        struct scx_rq           scx;
1152:	#endif
...
1321:	};

 675:	struct cfs_rq {
...
 691:	        struct rb_root_cached   tasks_timeline;
...
 697:	        struct sched_entity     *curr;
...
 771:	};

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

◆EEVDF/CFSのstruct sched_class

EEVDF も従来の CFS と同じく kernel/sched/fair.c に実装されている。

linux-6.18.2/kernel/sched/sched.h
2517:	#define DEFINE_SCHED_CLASS(name) \
2518:	const struct sched_class name##_sched_class \
2519:	        __aligned(__alignof__(struct sched_class)) \
2520:	        __section("__" #name "_sched_class")

linux-6.18.2/kernel/sched/fair.c
13636:	DEFINE_SCHED_CLASS(fair) = {
13637:	
13638:	        .enqueue_task           = enqueue_task_fair,
13639:	        .dequeue_task           = dequeue_task_fair,
...
13645:	        .pick_task              = pick_task_fair,
...
13660:	        .task_tick              = task_tick_fair,
...
13670:	        .update_curr            = update_curr_fair,
...
13683:	};

◆deadlineの設定と更新

enqueue_task_fair(), update_curr() 等で行われる。

linux-6.18.2/kernel/sched/fair.c
6920:	static void
6921:	enqueue_task_fair(struct rq *rq, struct task_struct *p, int flags)
6922:	{
...
6976:	                enqueue_entity(cfs_rq, se, flags);
7039:	}

5241:	static void
5242:	enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
5243:	{
5244:	        bool curr = cfs_rq->curr == se;
...
5250:	        if (curr)
5251:	                place_entity(cfs_rq, se, flags);
...
5253:	        update_curr(cfs_rq);
...
5277:	        if (!curr)
5278:	                place_entity(cfs_rq, se, flags);
...
5288:	        if (!curr)
5289:	                __enqueue_entity(cfs_rq, se);
5290:	        se->on_rq = 1;
...
5305:	}

5127:	static void
5128:	place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
5129:	{
5130:	        u64 vslice, vruntime = avg_vruntime(cfs_rq);
...
5133:	        if (!se->custom_slice)
5134:	                se->slice = sysctl_sched_base_slice;
5135:	        vslice = calc_delta_fair(se->slice, se);
...
5213:	        se->vruntime = vruntime - lag;
...
5232:	        se->deadline = se->vruntime + vslice;
5233:	}

1257:	static void update_curr_fair(struct rq *rq)
1258:	{
1259:	        update_curr(cfs_rq_of(&rq->donor->se));
1260:	}

1207:	static void update_curr(struct cfs_rq *cfs_rq)
1208:	{
...
1223:	        delta_exec = update_se(rq, curr);
...
1227:	        curr->vruntime += calc_delta_fair(delta_exec, curr);
1228:	        resched = update_deadline(cfs_rq, curr);
1229:	        update_min_vruntime(cfs_rq);
...
1248:	        if (cfs_rq->nr_queued == 1)
1249:	                return;
1250:	
1251:	        if (resched || !protect_slice(curr)) {
1252:	                resched_curr_lazy(rq);
1253:	                clear_buddies(cfs_rq, curr);
1254:	        }
1255:	}

1155:	static s64 update_se(struct rq *rq, struct sched_entity *se)
1156:	{
1157:	        u64 now = rq_clock_task(rq);
1158:	        s64 delta_exec;
1159:	
1160:	        delta_exec = now - se->exec_start;
...
1164:	        se->exec_start = now;
...
1166:	                struct task_struct *donor = task_of(se);
1167:	                struct task_struct *running = rq->curr;
...
1172:	                running->se.exec_start = now;
1173:	                running->se.sum_exec_runtime += delta_exec;
...
1193:	        return delta_exec;
1194:	}

1041:	static bool update_deadline(struct cfs_rq *cfs_rq, struct sched_entity *se)
1042:	{
1043:	        if ((s64)(se->vruntime - se->deadline) < 0)
1044:	                return false;
...
1057:	        se->deadline = se->vruntime + calc_delta_fair(se->slice, se);
...
1062:	        return true;
1063:	}

 290:	static inline u64 calc_delta_fair(u64 delta, struct sched_entity *se)
 291:	{
 292:	        if (unlikely(se->load.weight != NICE_0_LOAD))
 293:	                delta = __calc_delta(delta, NICE_0_LOAD, &se->load);
 294:	
 295:	        return delta;
 296:	}

 260:	static u64 __calc_delta(u64 delta_exec, unsigned long weight, struct load_weight *lw)
 261:	{
...
 285:	}

5373:	dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
5374:	{
...
5425:	        if (se != cfs_rq->curr)
5426:	                __dequeue_entity(cfs_rq, se);
5461:	}

enqueue_task_fair() は、fork() 等で新しくプロセスが作られた時に呼ばれる。
enqueue_entity() では、EEVDF では place_entity() で deadline を計算し、その順にキューに入れる。
place_entity() では、今の vruntime に slice を加えたものを deadline とする。
update_se() は、現在の時刻を struct cfs_rq から得ている。前回の実行開始 exec_start と現在時刻の差で　delta_exec　を求めている。
update_curr() は、update_se() で求めた delta_exec をcalc_delta_fair() で調整し、それをそのスケジューラで現在実行中のプロセスの se.vruntime に加え、、update_deadline() を呼ぶ。
update_deadline() は、se.vruntime に、calc_delta_fair() で調整して se.slice を加えた値を deadline として設定する。
calc_delta_fair() は、nice 値に応じて設定された se.load.{weight,inv_weight}を使って調整する。 nice値が0の時(se->load.weight == NICE_0_LOAD)は、そのまま返す。
enqueue_entity() は、__enqueue_entity(), dequeue_entity() は、__dequeue_entity() を呼出してキュー(赤黒木)を操作する。

EEVDF では deadline も更新する。 eligible でなくなった時は、reschedule。

◆赤黒木(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 は、木の根を差す。ノードのキーは、CFS では vruntime、EEVDF では deadline。

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

◆__enqueue_entity()

__enqueue_entity()は、CFS で木構造に要素を1個追加する関数である。関数 __entity_less() でノードを比較して、二分探索木を作る。 __entity_less() は、CFS では vruntime、EEVDF では deadline を比較する。

linux-6.18.2/kernel/sched/fair.c
 848:	static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
 849:	{
...
 851:	        se->min_vruntime = se->vruntime;
...
 853:	        rb_add_augmented_cached(&se->run_node, &cfs_rq->tasks_timeline,
 854:	                                __entity_less, &min_vruntime_cb);
 855:	}

 796:	static inline bool __entity_less(struct rb_node *a, const struct rb_node *b)
 797:	{
 798:	        return entity_before(__node_2_se(a), __node_2_se(b));
 799:	}

 545:	static inline bool entity_before(const struct sched_entity *a,
 546:	                                 const struct sched_entity *b)
 547:	{
 548:	        /*
 549:	         * Tiebreak on vruntime seems unnecessary since it can
 550:	         * hardly happen.
 551:	         */
 552:	        return (s64)(a->deadline - b->deadline) < 0;
 553:	}

 857:	static void __dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
 858:	{
 859:	        rb_erase_augmented_cached(&se->run_node, &cfs_rq->tasks_timeline,
 860:	                                  &min_vruntime_cb);
...
 862:	}

linux-6.18.2/include/linux/rbtree_augmented.h
  63:	static __always_inline struct rb_node *
  64:	rb_add_augmented_cached(struct rb_node *node, struct rb_root_cached *tree,
  65:	                        bool (*less)(struct rb_node *, const struct rb_node *),
  66:	                        const struct rb_augment_callbacks *augment)
  67:	{
  68:	        struct rb_node **link = &tree->rb_root.rb_node;
  69:	        struct rb_node *parent = NULL;
  70:	        bool leftmost = true;
  71:	
  72:	        while (*link) {
  73:	                parent = *link;
  74:	                if (less(node, parent)) {
  75:	                        link = &parent->rb_left;
  76:	                } else {
  77:	                        link = &parent->rb_right;
  78:	                        leftmost = false;
  79:	                }
  80:	        }
  81:	
  82:	        rb_link_node(node, parent, link);
  83:	        augment->propagate(parent, NULL); /* suboptimal */
  84:	        rb_insert_augmented_cached(node, tree, leftmost, augment);
  85:	
  86:	        return leftmost ? node : NULL;
  87:	}

linux-6.18.2/include/linux/rbtree.h
  59:	static inline void rb_link_node(struct rb_node *node, struct rb_node *parent,
  60:	                                struct rb_node **rb_link)
  61:	{
...
  63:	        node->rb_left = node->rb_right = NULL;
  64:	
  65:	        *rb_link = node;
  66:	}

__enqueue_entity() は、rb_add_augmented_cached() を呼び出し、平衡二分探索木の一種、red-black tree に節を追加している。この時、引数として関数 __entity_less() へのポインタを渡している。
__dequeue_entity() は、rb_erase_augmented_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 は、CFS では vruntime、EEVDF では deadline が小さい順に並ぶ。 vruntime/deadline が小さいほど左に来る。
entity_before() で現在着目しているノードと挿入したいデータの vruntime/deadline を比較する。
rb_add_augmented_cached() は、red-black tree に節を追加している。引数の関数 less() を呼び出し、挿入したいデータのvruntime が現在の節より小さければ、左(&parent->rb_left), 大きければ右(&parent->rb_right) に進む。
挿入すべき箇所が見つかる。rb_link_node() で挿入する。
最後に rb_insert_augmented_cached() を呼び出して、バランスを回復する。

◆tickごとの仕事

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

EEVDF では、donation とう仕組みで、他のプロセスから借りた時間で先に実行することがある。

linux-6.18.2/kernel/sched/core.c
5573:	void sched_tick(void)
5574:	{
5575:	        int cpu = smp_processor_id();
5576:	        struct rq *rq = cpu_rq(cpu);
5578:	        struct task_struct *donor;
...
5589:	        donor = rq->donor;
...
5600:	        donor->sched_class->task_tick(rq, donor, 0);
...
5622:	}

CPU ごとの run queue から現在実行中のプロセス rq->curr ではなく donor の tast_strut を取り出す。 EEVDF では、現在実行中のプロセスが donor から CPU 時間を借りて実行していることがある。
その task_struct の sched_class クラスの関数 task_tick() を呼び出す。

◆EEVDFのentity_tick()

linux-6.18.2/kernel/sched/fair.c
13129:	static void task_tick_fair(struct rq *rq, struct task_struct *curr, int queued)
13130:	{
13131:	        struct cfs_rq *cfs_rq;
13132:	        struct sched_entity *se = &curr->se;
...
13135:	                cfs_rq = cfs_rq_of(se);
13136:	                entity_tick(cfs_rq, se, queued);
...
13146:	}

5564:	static void
5565:	entity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr, int queued)
5566:	{
...
5570:	        update_curr(cfs_rq);
...
5588:	}

task_tick_fair() は、tick ごとに定期的に呼び出される。
task_tick_fair() は、entity_tick() を呼ぶ。
entity_tick() は、update_curr() を呼ぶ。その説明は既に行なった。

◆[資料] 以前のCFSのentity_tick()

現在(2026年)広く使われている CFS のentity_tick())

linux-6.6.9/kernel/sched/fair.c
12480:	static void task_tick_fair(struct rq *rq, struct task_struct *curr, int queued)
12481:	{
12482:	        struct cfs_rq *cfs_rq;
12483:	        struct sched_entity *se = &curr->se;
12484:	
12485:	        for_each_sched_entity(se) {
12486:	                cfs_rq = cfs_rq_of(se);
12487:	                entity_tick(cfs_rq, se, queued);
12488:	        }
...
12497:	}

5395:	static void
5396:	entity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr, int queued)
5397:	{
...
5401:	        update_curr(cfs_rq);
...
5425:	}

1150:	static void update_curr(struct cfs_rq *cfs_rq)
1151:	{
1152:	        struct sched_entity *curr = cfs_rq->curr;
1153:	        u64 now = rq_clock_task(rq_of(cfs_rq));
1154:	        u64 delta_exec;
...
1159:	        delta_exec = now - curr->exec_start;
...
1163:	        curr->exec_start = now;
...
1173:	        curr->sum_exec_runtime += delta_exec;
...
1176:	        curr->vruntime += calc_delta_fair(delta_exec, curr);
...
1189:	}

 311:	static inline u64 calc_delta_fair(u64 delta, struct sched_entity *se)
 312:	{
 313:	        if (unlikely(se->load.weight != NICE_0_LOAD))
 314:	                delta = __calc_delta(delta, NICE_0_LOAD, &se->load);
 315:	
 316:	        return delta;
 317:	}

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

$ cat /proc/sched_debug 
Sched Debug Version: v0.11, 4.18.0-477.15.1.el8_8.x86_64 #1
...
jiffies                                 : 8037018588
...
sysctl_sched
  .sysctl_sched_latency                    : 18.000000
  .sysctl_sched_min_granularity            : 10.000000
...

cpu#0, 3092.734 MHz
  .nr_running                    : 0
...
  .curr->pid                     : 0
...
cfs_rq[0]:/system.slice/shibd.service
...
  .se->exec_start                : 3740976147.098853
  .se->vruntime                  : 16904453.116095
  .se->sum_exec_runtime          : 488423.358201

cfs_rq[0]:/system.slice/mariadb.service
...
  .se->exec_start                : 3740976147.098853
  .se->vruntime                  : 16904453.116095
  .se->sum_exec_runtime          : 488423.358201
...

cfs_rq[0]:/system.slice/httpd.service
...
  .se->exec_start                : 3740976409.981736
  .se->vruntime                  : 16904452.748796
  .se->sum_exec_runtime          : 467578.885170
...
runnable tasks:
 S            task   PID         tree-key  switches  prio     wait-time             sum-exec        sum-sleep
-------------------------------------------------------------------------------------------------------------
...
 S           shibd 2029016     36399.620037   1312918   120         0.000000     17147.974128         0.000000 0 0 /system.slice/shibd.service
...
 S          mysqld 3062817    223694.881335      2877   120         0.000000       377.018340         0.000000 0 0 /system.slice/mariadb.service
...
 S           httpd 1887526    304759.136719     29475   120         0.000000      4818.694375         0.000000 0 0 /system.slice/httpd.service
...
>R             cat 3065061  23683938.282852         1   120         0.000000         2.674255         0.000000 0 0 /
...
cpu#1, 3092.734 MHz
..
cpu#2, 3092.734 MHz
...
cpu#3, 3092.734 MHz
...
$ cat /proc/self/sched 
cat (3065430, #threads: 1)
-------------------------------------------------------------------
se.exec_start                                :    3736477629.503557
se.vruntime                                  :      24389027.685650
se.sum_exec_runtime                          :             0.463870
...
se.load.weight                               :              1048576
...
policy                                       :                    0
prio                                         :                  120
...
$

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

★問題(401) PIT

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

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

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

★問題(403) struct timer_listの利用

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

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) {
    timer_setup( /*空欄(a)*/, /*空欄(b)*/, 0);
    my_timer.expires  = /*空欄(c)*/;
    /*空欄(d)*/;
}
void my_timer_func(/*省略*/) {
     h( my_arg_a,my_arg_b,my_arg_c );
}

★問題(404) sched_class

struct task_struct のフィールド sched_class は、プロセスのスケジューリング・ポリシーに応じていくつかの値がセットされる。ポリシーが SCHED_NORMAL の時、どのような値がセットされるか。この Web ページの資料の中から選んで答えなさい。

またポリシーがSCHED_NORMAL の時、EEVDF で sched_class->enqueue_task() として呼ばれる関数を答えなさい。

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

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

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

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

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

Last updated: 2026/01/25 13:35:55

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

プロセス	A	B	C
Lag値	0	0	0
vruntime	0	0	0
deadline	30	30	30