時刻と時間の管理

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

                                       筑波大学 システム情報工学研究科 
                                       コンピュータサイエンス専攻, 電子・情報工学系
                                       新城 靖
                                       <yas@is.tsukuba.ac.jp>

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

■連絡事項

試験について

試験は、3月2日。講義と同じ時間・教室で行う。
授業で配布した資料(Webページを印刷したもの)、その他の資料を持ち込んでもよい。
コンピュータ、携帯電話等の通信機器は利用してはいけない。
試験に解答する時には、問題文をよく読み、それに従って答えること。資料の文書をコピー＆ペーストしたとしても、一般的にはよい回答にはなっていない。

欠席した時のクイズの回答を、レポートして受け取ります。試験の日までに提出して下さい。紙はＡ４にしてください。

■今日の大事な話

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

■時刻と時間

◆求められる機能

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

◆カレンダ時刻のAPI

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

struct timeval {
	long    tv_sec;         /* seconds since Jan. 1, 1970 */
	long    tv_usec;        /* and microseconds */
};

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

使い方

    struct timeval  tv;
    gettimeofday(&tv, NULL);

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

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

外部の時刻サーバから時刻を得る。
自分自身の時刻が遅れていた時: 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 になると、シグナルが通知される。
変数の値を、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);

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

なにもしない時間切れ。

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

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

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

◆基本的なモデル

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

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

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

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

◆PIT (Programmable Interval Timer)

古いタイマ・デバイス。

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

Linux は、0 番を主タイマとして利用している。

◆TSC (Time Stamp Counter)

Pentium 以降で利用可能。

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

Linux の gettimeofday() で、PIT 以上の精度を出す時に使う。

■Liux における時刻・時間管理

◆jiffies変数

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

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

kernel/timer.c
  49: u64 jiffies_64 __cacheline_aligned_in_smp = INITIAL_JIFFIES;
...
1197: void do_timer(unsigned long ticks)
1198: {
1199:         jiffies_64 += ticks;
1200:         update_wall_time();
1201:         calc_global_load();
1202: }

kernel/time/tick-common.c
  60: static void tick_periodic(int cpu)
  61: {
...
  68:                 do_timer(1);
...
  72:         update_process_times(user_mode(get_irq_regs()));
...
  74: }
..
  79: void tick_handle_periodic(struct clock_event_device *dev)
  80: {
  81:         int cpu = smp_processor_id();
...
  84:         tick_periodic(cpu);
...
 109: }

kernel/time/tick-internal.h:125:        dev->event_handler = tick_handle_periodic;
kernel/time/tick-broadcast.c:108:               dev->event_handler = tick_handle_periodic;
kernel/time/tick-broadcast.c:288:               dev->event_handler = tick_handle_periodic;

arch/x86/include/asm/i8253.h
  11: extern struct clock_event_device *global_clock_event;

arch/x86/include/asm/do_timer.h:
  13: static inline void do_timer_interrupt_hook(void)
  14: {
  15:         global_clock_event->event_handler(global_clock_event);
  16: }

arch/x86/kernel/time_32.c
  75: irqreturn_t timer_interrupt(int irq, void *dev_id)
  76: {
...
  95:         do_timer_interrupt_hook();
...
 113:         return IRQ_HANDLED;
 114: }

arch/x86/kernel/setup.c
1069: static struct irqaction irq0  = {
1070:         .handler = timer_interrupt,
1071:         .flags = IRQF_DISABLED | IRQF_NOBALANCING | IRQF_IRQPOLL | IRQF_TIMER,
1072:         .name = "timer"
1073: };

1092: void __init x86_quirk_time_init(void)
1093: {
...
1104:         irq0.mask = cpumask_of_cpu(0);
1105:         setup_irq(0, &irq0);
1106: }

起動時に IRQ0 で定期的な割り込みがなされるように設定する。
割り込みハンドラ timer_interrupt() は、様々な層を上り、do_timer() を呼ぶ。
do_timer() では、64 ビットの変数 jiffies_64 が 1 だけ増やされる。
割り込みハンドラでは、update_process_times() も呼ばれる。それでは、現在実行中のプロセスに対してCPU時間の課金したり、スケジューラごとの tick の処理current->sched_class->task_tick() を行う。

◆xtime変数

xtime は、1970年1月1日00:00:00(GMT)からの秒数。gettimeofday() で返される値をnano 秒単位で保持している。tick 単位で更新されるが、それより細かい単位を TSC 等の高精度の clocksource から読み込み補正する。

kernel/time.c

 102: SYSCALL_DEFINE2(gettimeofday, struct timeval __user *, tv,
 103:                 struct timezone __user *, tz)
 104: {
 105:         if (likely(tv != NULL)) {
 106:                 struct timeval ktv;
 107:                 do_gettimeofday(&ktv);
 108:                 if (copy_to_user(tv, &ktv, sizeof(ktv)))
 109:                         return -EFAULT;
 110:         }
 111:         if (unlikely(tz != NULL)) {
 112:                 if (copy_to_user(tz, &sys_tz, sizeof(sys_tz)))
 113:                         return -EFAULT;
 114:         }
 115:         return 0;
 116: }

kernel/time/timekeeping.c

 134: void do_gettimeofday(struct timeval *tv)
 135: {
 136:         struct timespec now;
 137: 
 138:         getnstimeofday(&now);
 139:         tv->tv_sec = now.tv_sec;
 140:         tv->tv_usec = now.tv_nsec/1000;
 141: }

  45: struct timespec xtime __attribute__ ((aligned (16)));
...
  96: void getnstimeofday(struct timespec *ts)
  97: {
...
 107:                 *ts = xtime;
 110:                 cycle_now = clocksource_read(clock);
 113:                 cycle_delta = (cycle_now - clock->cycle_last) & clock->mask;
 116:                 nsecs = cyc2ns(clock, cycle_delta);
 119:                 nsecs += arch_gettimeoffset();
...
 123:         timespec_add_ns(ts, nsecs);
 124: }

 493: void update_wall_time(void)
 494: {
...
 519:                         xtime.tv_sec++;
...
 562:         xtime.tv_nsec = ((s64)clock->xtime_nsec >> clock->) + 1;
...
 571: }

gettimeofday() システム・コールの API は、struct timeval でマイクロ秒単位だが、内部的には、struct timespec で、ナノ秒単位の変数 xtime が使われる。
単に xtime 変数の値をコピーするのではなく、利用可能ならさらに高精度の時計(TSC等)で補正する。
xtime 変数は、update_wall_time() で更新する。update_wall_time() は、タイマ割り込みの割り込みハンドラから呼ばれる。

◆struct timer_list

ある時間が経過したら、関数を実行する。

include/linux/timer.h
  12: struct timer_list {
  13:         struct list_head entry;
  14:         unsigned long expires;
  15: 
  16:         void (*function)(unsigned long);
  17:         unsigned long data;
  18: 
  19:         struct tvec_base *base;
...
  28: };
  29:

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

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

add_timer(), add_timer_on(): タイマの登録。_on() は、CPU ごと。
mod_timer(): タイマの起動時刻の変更
del_timer(), del_timer_sync(), try_to_del_timer_sync(): タイマのキャンセル

利用例。

    init_timer(&timer);
    timer.expires = jiffies + delay;
    timer.data = (unsigned long)data;
    timer.function = func;
    add_timer(&timer);

◆High-resolution kernel timers

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