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

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

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

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

■今日の大事な話

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

■時刻と時間

◆求められる機能

◆カレンダ時刻のAPI

gettimeofday() は、μ(マイクロ)秒単位の時刻を扱う。
struct timeval {
    time_t      tv_sec;     /* seconds. long int */
    suseconds_t tv_usec;    /* microseconds. long int */
};

int gettimeofday(struct timeval *tp, struct timezone *tzp);
int settimeofday(const struct timeval *tp, const struct timezone *tzp);
使い方
   1:	/*
   2:	        gettimeofday-print.c -- get colander time and print
   3:	        Created on: 2014/01/22 20:40:34
   4:	*/
   5:	
   6:	#include <sys/time.h>   /* gettimeofday() */
   7:	#include <time.h>       /* ctime() */
   8:	#include <stdio.h>
   9:	
  10:	main()
  11:	{
  12:	    struct timeval tv;
  13:	    time_t sec;
  14:	        gettimeofday( &tv, NULL );
  15:	        sec = tv.tv_sec;
  16:	        printf("%s", ctime(&sec) );
  17:	}
$ make gettimeofday-print [←]
cc     gettimeofday-print.c   -o gettimeofday-print
$ date [←]
Wed Jan 31 17:45:50 JST 2018
$ ./gettimeofday-print  [←]
Wed Jan 31 17:45:51 2018
$ []
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() を使った時刻同期の方法。
  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);
次のように考えてもよい。
  1. 内部に変数がある。
  2. 変数の初期値として、it_value を設定する。
  3. 変数の値が 0 になるまでカウントダウンする。
  4. 変数が 0 になると、次のことを行う。
  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);

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

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

◆基本的なモデル

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

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

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

◆PIT (Programmable Interval Timer)

古いタイマ・デバイス。

◆CMOS RTC (Real Time Clock)

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

2つの機能がある。

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

その他の割込み

◆Local APIC (Advanced Programmable Interrupt Controller) Timers

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

◆ACPI (Advanced Configuration and Power Interface)

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

◆TSC (Time Stamp Counter)

Pentium 以降で利用可能。

◆HPET(High Precision Event Timer)

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

■jiffiesとHZ

jiffies は、Linux で、モノトニック時刻を提供する変数。単位は、tick。 利用例 実装。
linux-4.14.12/include/asm-generic/param.h
   8:	# define HZ             CONFIG_HZ       /* Internal kernel timer frequency */

linux-4.14.12/include/generated/autoconf.h
 991:	#define CONFIG_HZ 1000

  59:	__visible u64 jiffies_64 __cacheline_aligned_in_smp = INITIAL_JIFFIES;

linux-4.14.12/include/linux/jiffies.h
  77:	extern u64 __cacheline_aligned_in_smp jiffies_64;
  78:	extern unsigned long volatile __cacheline_aligned_in_smp __jiffy_arch_data jiffies;

◆tick_periodic()

tick_periodic() は、ハードウェアから独立したtick ごとの処理を行う関数 である。
linux-4.14.12/kernel/time/tick-common.c
  79:	static void tick_periodic(int cpu)
  80:	{
  81:	        if (tick_do_timer_cpu == cpu) {
...
  87:	                do_timer(1);
...
  89:	                update_wall_time();
  90:	        }
...
  92:	        update_process_times(user_mode(get_irq_regs()));
...
  94:	}

◆do_timer()


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

linux-4.14.12/kernel/time/timekeeping.c
2200:	void do_timer(unsigned long ticks)
2201:	{
2202:	        jiffies_64 += ticks;
2203:	        calc_global_load(ticks);
2204:	}

■カレンダー時刻の実装

◆struct timekeeper/xtime

struct timekeeper は、全体でカレンダー時刻を計算するための構造体。次の 3つのフィールドを使って1970年1月1日00:00:00(UTC)からの秒数をナノ秒単位 で保持している。 実際には、xtime_nsec は、そのままでナノ秒を表すのではなく、 xtime_nsec >> shift でナノ秒を表す。
linux-4.14.12/include/linux/timekeeper_internal.h
  31:	struct tk_read_base {
...
  36:	        u32                     shift;
  37:	        u64                     xtime_nsec;
...
  39:	};

  84:	struct timekeeper {
  85:	        struct tk_read_base     tkr_mono;
...
  87:	        u64                     xtime_sec;
...
 128:	};

linux-4.14.12/kernel/time/timekeeping.c
  81:	static inline struct timespec64 tk_xtime(struct timekeeper *tk)
  82:	{
  83:	        struct timespec64 ts;
  84:	
  85:	        ts.tv_sec = tk->xtime_sec;
  86:	        ts.tv_nsec = (long)(tk->tkr_mono.xtime_nsec >> tk->tkr_mono.shift);
  87:	        return ts;
  88:	}

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

linux-4.14.12/kernel/time/time.c
 144:	SYSCALL_DEFINE2(gettimeofday, struct timeval __user *, tv,
 145:	                struct timezone __user *, tz)
 146:	{
 147:	        if (likely(tv != NULL)) {
 148:	                struct timeval ktv;
 149:	                do_gettimeofday(&ktv);
 150:	                if (copy_to_user(tv, &ktv, sizeof(ktv)))
 151:	                        return -EFAULT;
 152:	        }
 153:	        if (unlikely(tz != NULL)) {
 154:	                if (copy_to_user(tz, &sys_tz, sizeof(sys_tz)))
 155:	                        return -EFAULT;
 156:	        }
 157:	        return 0;
 158:	}

linux-4.14.12/kernel/time/timekeeping.c
1205:	void do_gettimeofday(struct timeval *tv)
1206:	{
1207:	        struct timespec64 now;
1208:	
1209:	        getnstimeofday64(&now);
1210:	        tv->tv_sec = now.tv_sec;
1211:	        tv->tv_usec = now.tv_nsec/1000;
1212:	}

 742:	void getnstimeofday64(struct timespec64 *ts)
 743:	{
 744:	        WARN_ON(__getnstimeofday64(ts));
 745:	}

 709:	int __getnstimeofday64(struct timespec64 *ts)
 710:	{
 711:	        struct timekeeper *tk = &tk_core.timekeeper;
...
 713:	        u64 nsecs;
...
 718:	                ts->tv_sec = tk->xtime_sec;
 719:	                nsecs = timekeeping_get_ns(&tk->tkr_mono);
...
 723:	        ts->tv_nsec = 0;
 724:	        timespec64_add_ns(ts, nsecs);
..
 732:	        return 0;
 733:	}

◆update_wall_time()

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

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

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

◆struct timer_list

linux-4.14.12/include/linux/timer.h
  13:	struct timer_list {
...
  19:	        unsigned long           expires;
  20:	        void                    (*function)(unsigned long);
  21:	        unsigned long           data;
...
  27:	};

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

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

add_timer(struct timer_list *timer)
add_timer_on(struct timer_list *timer, int cpu)
タイマの登録。_on() は、CPU ごと。
mod_timer(struct timer_list *timer, unsigned long expires)
タイマの起動時刻の変更
del_timer(struct timer_list *timer),
del_timer_sync(struct timer_list *timer)
try_to_del_timer_sync(struct timer_list *timer)
タイマのキャンセル。 del_timer_sync() は、もし既に実行中だったら、実行完了を待つ。
利用例。
{
    struct timer_list my_timer;           // 構造体の宣言
    init_timer(&my_timer);                // 初期化
    my_timer.expires = jiffies + delay;   // どのくらい待ちたいか
    my_timer.data = (unsigned long)data;  // 渡したいデータ
    my_timer.function = my_timer_func;    // 関数
    add_timer(&my_timer);                 // 登録
}

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

◆High-resolution kernel timers

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

linux-4.14.12/include/linux/hrtimer.h
  32:	enum hrtimer_mode {
  33:	        HRTIMER_MODE_ABS = 0x0,         /* Time value is absolute */
  34:	        HRTIMER_MODE_REL = 0x1,         /* Time value is relative to now */
...
  38:	};

  43:	enum hrtimer_restart {
  44:	        HRTIMER_NORESTART,      /* Timer is not restarted */
  45:	        HRTIMER_RESTART,        /* Timer must be restarted */
  46:	};

  93:	struct hrtimer {
...
  96:	        enum hrtimer_restart            (*function)(struct hrtimer *);
...
 100:	};
主に次の関数で操作する。
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;
}

■実行の遅延

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

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

様々な方法がある。

◆空ループ(busy loop)

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

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

unsigned long timeout = jiffies + 10; // 10 ticks
while (time_before(jiffies,timeout))
    continue;
例2: 2秒待つ
unsigned long delay = jiffies + 2*HZ; // 2秒
while (time_before(jiffies,timeout))
    continue;

◆time_befefore()

jiffies は、32 ビットなので、オーバフローする可能性がある。 次のコードは危ない。
unsigned long timeout = jiffies + 10; // 10 ticks
while (jiffies<timeout)
    continue;
引き算して 0 と比較すると、オーバフローの問題が解決できる。
unsigned long timeout = jiffies + 10; // 10 ticks
while (jiffies-timeout<0)
    continue;
次のマクロを使う方法もある。
linux-4.14.12/include/linux/jiffies.h
 102:	#define time_after(a,b)         \
 103:	        (typecheck(unsigned long, a) && \
 104:	         typecheck(unsigned long, b) && \
 105:	         ((long)((b) - (a)) < 0))
 106:	#define time_before(a,b)        time_after(b,a)
 107:	
 108:	#define time_after_eq(a,b)      \
 109:	        (typecheck(unsigned long, a) && \
 110:	         typecheck(unsigned long, b) && \
 111:	         ((long)((a) - (b)) >= 0))
 112:	#define time_before_eq(a,b)     time_after_eq(b,a)

◆cond_resched()

空ループは、CPU が無駄になるので良くない。その代わりに次の方法が使える。
unsigned long delay = jiffies + 2*HZ; // 2秒
while (time_before(jiffies,timeout))
    cond_resched();
他に実行すべき重要なプロセスが存在する(条件)時には、スケジューラを呼ん で、実行する。存在しなければ、空ループと同じ。ただし、スケジューラを呼 ぶ(sleepする可能性がある)ので、割り込みコンテキストからは使えない。

◆小さな遅延

tick 単位 (10ミリ秒-1ミリ秒) では大きすぎる場合、小さな遅延を実現するよ うな関数がある。
void ndelay(unsigned long nsecs)
void udelay(unsigned long usecs)
void mdelay(unsigned long msecs)
udelay() は、ある回数のループで実装されている。回数は、CPUの速度等で決 まる。ndelay(), mdelay() は、udelay() を呼んでいる。

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

◆schedule_timeout()

set_current_state( TASK_INTERRUPTIBLE ); // signal で起きる可能性がある
schedule_timeout( s * HZ );
実装には struct timer_list が使われている。

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

復習(オペレーティングシステム Iの範囲) 全部は同時には成り立たない。

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

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

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

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

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

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

注意: 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
$ []

◆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
$ []

◆nice値の利用法

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

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

例1: 次の2つの CPU-bound のプロセスが存在したとする。 AのCPU時間 : BのCPU時間 == 1 : 0.9

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

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

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

■Linux task構造体とnice値

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

◆task_struct構造体

linux-4.14.12/include/linux/sched.h
 519:	struct task_struct {
...
 528:	        volatile long                   state;
...
 557:	        int                             prio;
 558:	        int                             static_prio;
 559:	        int                             normal_prio;
 560:	        unsigned int                    rt_priority;
 561:	
 562:	        const struct sched_class        *sched_class;
 563:	        struct sched_entity             se;
 564:	        struct sched_rt_entity          rt;
...
 568:	        struct sched_dl_entity          dl;
...
 579:	        unsigned int                    policy;
...
1116:	};

 377:	struct sched_entity {
...
 379:	        struct load_weight              load;
 380:	        struct rb_node                  run_node;
...
 382:	        unsigned int                    on_rq;
...
 384:	        u64                             exec_start;
 385:	        u64                             sum_exec_runtime;
 386:	        u64                             vruntime;
...
 411:	};

 275:	struct load_weight {
 276:	        unsigned long                   weight;
 277:	        u32                             inv_weight;
 278:	};
struct task_struct の中に、prio 等のフィールドやstruct sched_entity が ある。

◆policy

Linux では、スケジューリングのポリシーが大きく2種類。通常の時分割と実時間。
linux-4.14.12/include/uapi/linux/sched.h
  36:	#define SCHED_NORMAL            0
  37:	#define SCHED_FIFO              1
  38:	#define SCHED_RR                2
  39:	#define SCHED_BATCH             3
  40:	/* SCHED_ISO: reserved but not implemented yet */
  41:	#define SCHED_IDLE              5
  42:	#define SCHED_DEADLINE          6
SCHED_NORMAL
伝統的なプロセス。時分割(time sharing)
SCHED_BATCH
パッチ向け。一度CPUを割り当てたら横取りしない。
SCHED_IDLE
nice 19 よりも低い優先度。
SCHED_FIFO (first in first out)
実時間で FIFO
SCHED_RR (round robin)
実時間でラウンドロビン
SCHED_DEADLINE
実時間で、デッドラインが一番近いもの (Earliest Deadline First (EDF) )

◆prioとstatic_prio

static_prio
nice値を保持する。ただし、次のようなゲタを履かせている (NICE_TO_PRIO()参照)。
prio
スケジューリングに用いる優先度を保持する。
prio を見ると、通常のプロセスか実時間のプロセスかがわかる。 100 以上なら、通常のプロセス。通常のプロセスの prio は、100から140。

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

linux-4.14.12/kernel/sys.c
 253:	SYSCALL_DEFINE2(getpriority, int, which, int, who)
 254:	{
 255:	        struct task_struct *g, *p;
 256:	        struct user_struct *user;
 257:	        const struct cred *cred = current_cred();
 258:	        long niceval, retval = -ESRCH;
 259:	        struct pid *pgrp;
 260:	        kuid_t uid;
 261:	
 262:	        if (which > PRIO_USER || which < PRIO_PROCESS)
 263:	                return -EINVAL;
...
 267:	        switch (which) {
 268:	        case PRIO_PROCESS:
 269:	                if (who)
 270:	                        p = find_task_by_vpid(who);
 271:	                else
 272:	                        p = current;
 273:	                if (p) {
 274:	                        niceval = nice_to_rlimit(task_nice(p));
 275:	                        if (niceval > retval)
 276:	                                retval = niceval;
 277:	                }
 278:	                break;
 279:	        case PRIO_PGRP:
...
 290:	        case PRIO_USER:
...
 310:	        }
...
 315:	        return retval;
 316:	}

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

linux-4.14.12/include/linux/sched.h
1429:	static inline int task_nice(const struct task_struct *p)
1430:	{
1431:	        return PRIO_TO_NICE((p)->static_prio);
1432:	}

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

◆se.load.weight

struct task_struct の static_prio は、struct task_struct の se.load.weight の値を決めるために使われる。
linux-4.14.12/kernel/sched/core.c
6722:	/*
6723:	 * Nice levels are multiplicative, with a gentle 10% change for every
6724:	 * nice level changed. I.e. when a CPU-bound task goes from nice 0 to
6725:	 * nice 1, it will get ~10% less CPU time than another CPU-bound task
6726:	 * that remained on nice 0.
6727:	 *
6728:	 * The "10% effect" is relative and cumulative: from _any_ nice level,
6729:	 * if you go up 1 level, it's -10% CPU usage, if you go down 1 level
6730:	 * it's +10% CPU usage. (to achieve that we use a multiplier of 1.25.
6731:	 * If a task goes up by ~10% and another task goes down by ~10% then
6732:	 * the relative distance between them is ~25%.)
6733:	 */
6734:	const int sched_prio_to_weight[40] = {
6735:	 /* -20 */     88761,     71755,     56483,     46273,     36291,
6736:	 /* -15 */     29154,     23254,     18705,     14949,     11916,
6737:	 /* -10 */      9548,      7620,      6100,      4904,      3906,
6738:	 /*  -5 */      3121,      2501,      1991,      1586,      1277,
6739:	 /*   0 */      1024,       820,       655,       526,       423,
6740:	 /*   5 */       335,       272,       215,       172,       137,
6741:	 /*  10 */       110,        87,        70,        56,        45,
6742:	 /*  15 */        36,        29,        23,        18,        15,
6743:	};

 735:	static void set_load_weight(struct task_struct *p)
 736:	{
 737:	        int prio = p->static_prio - MAX_RT_PRIO;
 738:	        struct load_weight *load = &p->se.load;
...
 749:	        load->weight = scale_load(sched_prio_to_weight[prio]);
 750:	        load->inv_weight = sched_prio_to_wmult[prio];
 751:	}

linux-4.14.12/kernel/sched/sched.h
  94:	# define scale_load(w)          (w)

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

◆sched_class

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

◆sched_class使い方

プロセスのクラスに応じて enqueue、 dequeue の操作を切り替える。
linux-4.14.12/kernel/sched/core.c
 753:	static inline void enqueue_task(struct rq *rq, struct task_struct *p, int flags)
 754:	{
...
 761:	        p->sched_class->enqueue_task(rq, p, flags);
 762:	}

 764:	static inline void dequeue_task(struct rq *rq, struct task_struct *p, int flags)
 765:	{
...
 772:	        p->sched_class->dequeue_task(rq, p, flags);
 773:	}

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

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

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

linux-4.14.12/kernel/sched/core.c
3968:	static void __setscheduler(struct rq *rq, struct task_struct *p,
3969:	                           const struct sched_attr *attr, bool keep_boost)
3970:	{
3971:	        __setscheduler_params(p, attr);
...
3977:	        p->prio = normal_prio(p);
...
3981:	        if (dl_prio(p->prio))
3982:	                p->sched_class = &dl_sched_class;
3983:	        else if (rt_prio(p->prio))
3984:	                p->sched_class = &rt_sched_class;
3985:	        else
3986:	                p->sched_class = &fair_sched_class;
3987:	}

3942:	static void __setscheduler_params(struct task_struct *p,
3943:	                const struct sched_attr *attr)
3944:	{
3945:	        int policy = attr->sched_policy;
3946:	
3947:	        if (policy == SETPARAM_POLICY)
3948:	                policy = p->policy;
3949:	
3950:	        p->policy = policy;
3951:	
3952:	        if (dl_policy(policy))
3953:	                __setparam_dl(p, attr);
3954:	        else if (fair_policy(policy))
3955:	                p->static_prio = NICE_TO_PRIO(attr->sched_nice);
...
3962:	        p->rt_priority = attr->sched_priority;
3963:	        p->normal_prio = normal_prio(p);
3964:	        set_load_weight(p);
3965:	}

◆CFS(Completely Fair Scheduler)

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

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

◆runqueues(リスト的な見方)

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

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

linux-4.14.12/kernel/sched/sched.h
 677:	struct rq {
...
 706:	        struct cfs_rq cfs;
 707:	        struct rt_rq rt;
 708:	        struct dl_rq dl;
...
 811:	};

 420:	struct cfs_rq {
...
 430:	        struct rb_root_cached tasks_timeline;
...
 497:	};

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

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

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

二分探索木とは、次のような二分木。 平衡木(balanced tree)、または、高さ平衡木(height-balanced tree)は、任意 の節で左右の高さの差が一定以下の木。

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

◆Linux red-black treeの基本操作

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

◆runqueues(red-black tree)

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

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

◆__enqueue_entity()

__enqueue_entity()は、CFS で木構造に要素を1個追加する関数である。
linux-4.14.12/kernel/sched/fair.c
 549:	static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
 550:	{
 551:	        struct rb_node **link = &cfs_rq->tasks_timeline.rb_root.rb_node;
 552:	        struct rb_node *parent = NULL;
 553:	        struct sched_entity *entry;
 554:	        bool leftmost = true;
 555:	
 556:	        /*
 557:	         * Find the right place in the rbtree:
 558:	         */
 559:	        while (*link) {
 560:	                parent = *link;
 561:	                entry = rb_entry(parent, struct sched_entity, run_node);
 562:	                /*
 563:	                 * We dont care about collisions. Nodes with
 564:	                 * the same key stay together.
 565:	                 */
 566:	                if (entity_before(se, entry)) {
 567:	                        link = &parent->rb_left;
 568:	                } else {
 569:	                        link = &parent->rb_right;
 570:	                        leftmost = false;
 571:	                }
 572:	        }
 573:	
 574:	        rb_link_node(&se->run_node, parent, link);
 575:	        rb_insert_color_cached(&se->run_node,
 576:	                               &cfs_rq->tasks_timeline, leftmost);
 577:	}
 578:	
 579:	static void __dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
 580:	{
 581:	        rb_erase_cached(&se->run_node, &cfs_rq->tasks_timeline);
 582:	}

 508:	static inline int entity_before(struct sched_entity *a,
 509:	                                struct sched_entity *b)
 510:	{
 511:	        return (s64)(a->vruntime - b->vruntime) < 0;
 512:	}

◆tickごとの仕事

scheduler_tick() は、tick ごとに定期的に呼び出される。 1 tick は、10 ミリ秒(HZ == 100)、4ミリ秒(HZ == 250)、1 ミリ秒(HZ == 1000)が一般的。
linux-4.14.12/kernel/sched/core.c
3002:	void scheduler_tick(void)
3003:	{
3004:	        int cpu = smp_processor_id();
3005:	        struct rq *rq = cpu_rq(cpu);
3006:	        struct task_struct *curr = rq->curr;
...
3014:	        curr->sched_class->task_tick(rq, curr, 0);
...
3027:	}

◆CFSのentity_tick()

linux-4.14.12/kernel/sched/fair.c

9044:	static void task_tick_fair(struct rq *rq, struct task_struct *curr, int queued)
9045:	{
9046:	        struct cfs_rq *cfs_rq;
9047:	        struct sched_entity *se = &curr->se;
9048:	
9049:	        for_each_sched_entity(se) {
9050:	                cfs_rq = cfs_rq_of(se);
9051:	                entity_tick(cfs_rq, se, queued);
9052:	        }
...
9056:	}

3989:	static void
3990:	entity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr, int queued)
3991:	{
...
3995:	        update_curr(cfs_rq);
...
4022:	}

 827:	static void update_curr(struct cfs_rq *cfs_rq)
 828:	{
 829:	        struct sched_entity *curr = cfs_rq->curr;
 830:	        u64 now = rq_clock_task(rq_of(cfs_rq));
 831:	        u64 delta_exec;
...
 836:	        delta_exec = now - curr->exec_start;
...
 840:	        curr->exec_start = now;
...
 845:	        curr->sum_exec_runtime += delta_exec;
 849:	        update_min_vruntime(cfs_rq);
...
 848:	        curr->vruntime += calc_delta_fair(delta_exec, curr);
...
 860:	}

 646:	static inline u64 calc_delta_fair(u64 delta, struct sched_entity *se)
 647:	{
 648:	        if (unlikely(se->load.weight != NICE_0_LOAD))
 649:	                delta = __calc_delta(delta, NICE_0_LOAD, &se->load);
 650:	
 651:	        return delta;
 652:	}

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

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

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

★問題(401) PIT

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

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

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

★問題(403) struct timer_listの利用

関数f()を実行している時に、次の関数h()を、50 ミリ秒後に実行したいとする。
void h(int a,int b, int c) {
   ....
}
これを実現するために、どのようなコードを書けばよいか。以下の空欄を埋め なさい。
struct timer_list my_timer;

int my_arg_a,my_arg_b,my_arg_c;

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

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

★問題(404) nice値

例1: 次の2つの CPU-bound のプロセスが存在したとする。 19秒間実行した場合、プロセスAとプロセスBは、それぞれ何秒ずつ CPU時間が割り当てられると期待されるか。

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

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

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

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

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


Last updated: 2018/02/15 16:39:01
Yasushi Shinjo / <yas@cs.tsukuba.ac.jp>