時刻と時間の管理

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

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

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

■復習

■参考文献

VMware: "Timekeeping in VMware Virtual Machines", White paper (2005).

高橋浩和, 小田逸郎, 山幡為佐久: "Linuxカーネル2.6解読室",フトバンククリエイティブ (2006/11/18). ISBN-13: 978-4797338263.

Marshall Kirk McKusick, George V. Neville‐Neil (著), 歌代 和正, 砂原 秀樹(翻訳): "BSDカーネルの設計と実装―FreeBSD詳解", アスキー (2005/10/18). ISBN-13: 978-4756146793. Marshall Kirk McKusick, George V. Neville-Neil: "The Design And Implementation Of The Freebsd Operating System Addison-Wesley (2004/7/30). ISBN-13: 978-0201702453

■オペレーティング・システム

2つのインタフェースを、うまくつなぐもの。

図? システム・コール、ハードウェア、割込み、入出力

図? オペレーティング・システムの働き

ライブラリとシステム・コールの違いに注意

■時刻と時間

◆必要な機能

◆カレンダ時刻の提供

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

int gettimeofday(struct timeval *tp, 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);

◆インターバルタイマ

定期的な仕事をしたい時に使う
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. 変数の値を、it_interval に設定する。
  5. 3. を、解除されるまで繰り返す。

◆時間切れ

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

◆シグナルとハードウェア割込み

Unix のシグナルは、ハードウェア割込みを元に機能が設計されている。 up-call の方が、ソフトウェアとしては使いやすい。

◆up-call

図? ユーザ・プロセス、システム・コール−>オペレーティング・システム、アップコール−>ユーザ・プロセス

図? システムコールとアップコール

アップコールは、システム・コールの逆に、オペレーティング・システムがユー ザ・レベルの関数を呼び出す。 ウインドウ・システムのプログラムでは、call-back 関数やlistener として利 用されている。

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

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

◆基本的なモデル

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

図? 発振器、カウンタ、比較、CPU、割込み、再設定

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

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

◆PIT (Programmable Interval Timer)

古いタイマ・デバイス。 Linux は、0 番を主タイマとして利用している。

◆CMOS RTC (Real Time Clock)

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

2つの機能がある。

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

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

Linux kernel 2.6 は、PIT を補正するのに使う。

◆TSC (Time Stamp Counter)

Pentium 以降で利用可能。 Linux の gettimeofday() で、PIT 以上の精度を出す時に使う。

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

◆jiffies変数


/* kernel/imer.c */
u64 jiffies_64;
void do_timer(unsigned long ticks)
{
        jiffies_64 += ticks;
        update_times(ticks);
}

/* include/asm-i386/mach-default/do_timer.h */
static inline void do_timer_interrupt_hook(void)
{
        do_timer(1);
...
}

/* arch/i386/kernel/time.c */
irqreturn_t timer_interrupt(int irq, void *dev_id) 
{
        do_timer_interrupt_hook();
}

/* arch/i386/mach-default/setup.c */

static struct irqaction irq0  = { timer_interrupt, IRQF_DISABLED, 
CPU_MASK_NONE, "timer", NULL, NULL};

void __init time_init_hook(void)
{
        setup_irq(0, &irq0);
}

◆xtime変数

xtime は、1970年1月1日00:00:00(GMT)からの秒数。gettimeofday() で返される値を nano 秒単位で保持している。実際の精度は、jiffies 単位だが、それより 細かい単位を TSC 等の clocksource から読み込み補正する。
/* kernel/time.c */
asmlinkage long sys_gettimeofday(struct timeval __user *tv, struct timezone __user *tz)
{
	if (likely(tv != NULL)) {
		struct timeval ktv;
		do_gettimeofday(&ktv);
		if (copy_to_user(tv, &ktv, sizeof(ktv)))
			return -EFAULT;
	}
	if (unlikely(tz != NULL)) {
		if (copy_to_user(tz, &sys_tz, sizeof(sys_tz)))
			return -EFAULT;
	}
	return 0;
}

/* kernlel/timer.c */

struct timespec xtime;

void do_gettimeofday(struct timeval *tv)
{
        struct timespec now;

        __get_realtime_clock_ts(&now);
        tv->tv_sec = now.tv_sec;
        tv->tv_usec = now.tv_nsec/1000;
}

static inline void __get_realtime_clock_ts(struct timespec *ts)
{
        unsigned long seq;
        s64 nsecs;

        do {
                seq = read_seqbegin(&xtime_lock);

                *ts = xtime;
                nsecs = __get_nsec_offset();

        } while (read_seqretry(&xtime_lock, seq));

        timespec_add_ns(ts, nsecs);
}

static inline s64 __get_nsec_offset(void)
{
        cycle_t cycle_now, cycle_delta;
        s64 ns_offset;
        /* read clocksource: */
        cycle_now = clocksource_read(clock);
        /* calculate the delta since the last update_wall_time: */
        cycle_delta = (cycle_now - clock->cycle_last) & clock->mask;
        /* convert to nanoseconds: */
        ns_offset = cyc2ns(clock, cycle_delta);
        return ns_offset;
}

static void update_wall_time(void)
{
... 
                        xtime.tv_sec++;
...	
       xtime.tv_nsec = (s64)clock->xtime_nsec >> clock->shift;
...
}
static inline void update_times(unsigned long ticks)
{
        update_wall_time();
        calc_load(ticks);
}

◆Unix callout待ち行列

n tick 後に、関数を実行する仕組み。伝統的な Unix での実装では、callout 待ち行列と呼ばれる仕組みを使う。Linux は、少し違う。

◆例: 0 tick 後

図? callout 待ち行列、f(x),g(y),h(z)

図? callout 待ち行列(1)

◆例: 10 tick 後

f(x) を取り除いて実行した後。

図? callout 待ち行列、g(y),h(z)

図? callout 待ち行列(2)

◆例: 200 tick 後

g(y), h(z) を取り除いて実行した後。

図? callout 待ち行列、空

図? callout 待ち行列(3)

◆Linux タイマリスト

include/linux/timer.h:
struct timer_list {
        struct list_head entry;
        unsigned long expires;

        void (*function)(unsigned long);
        unsigned long data;

        struct tvec_t_base_s *base;
};

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

主に次の関数で操作する。 include/linux/timer.h:

static inline void add_timer(struct timer_list *timer)
{
        BUG_ON(timer_pending(timer));
        __mod_timer(timer, timer->expires);
}
利用例。
    timer->expires = jiffies + delay;
    timer->data = (unsigned long)data;
    timer->function = func;
    add_timer(timer);

◆Linux tv1..tv5

内部的には、timer_list は、tv1からtv5の5つの表に分解されて保存されている。

図? Linux tv1,tv2,tv3,tv4,tv5

図? Linux tv

/* timer.c: */
static void run_timer_softirq(struct softirq_action *h)
{
        tvec_base_t *base = __get_cpu_var(tvec_bases);

        hrtimer_run_queues();
        if (time_after_eq(jiffies, base->timer_jiffies))
                __run_timers(base);
}

static inline void __run_timers(tvec_base_t *base)
{
        struct timer_list *timer;
...
        while (time_after_eq(jiffies, base->timer_jiffies)) {
                struct list_head work_list;
                struct list_head *head = &work_list;
                int index = base->timer_jiffies & TVR_MASK;
...
                ++base->timer_jiffies;
                list_replace_init(base->tv1.vec + index, &work_list);
                while (!list_empty(head)) {
                        void (*fn)(unsigned long);
                        unsigned long data;
..
                        timer = list_entry(head->next,struct timer_list,entry);
                        fn = timer->function;
                        data = timer->data;
...
                                fn(data);
		}
	}
}

◆do_setitimer()

/* itimer.c */
int do_setitimer(int which, struct itimerval *value, struct itimerval *ovalue)
{
        struct task_struct *tsk = current;
        struct hrtimer *timer;
...
        switch (which) {
        case ITIMER_REAL:
...
                timer = &tsk->signal->real_timer;
...
                tsk->signal->it_real_incr =
                        timeval_to_ktime(value->it_interval);
                expires = timeval_to_ktime(value->it_value);
                if (expires.tv64 != 0)
                        hrtimer_start(timer, expires, HRTIMER_REL);
...
        }
}

int
hrtimer_start(struct hrtimer *timer, ktime_t tim, const enum hrtimer_mode mode)
{
...
	base = lock_hrtimer_base(timer, &flags);
	new_base = switch_hrtimer_base(timer, base);
        timer->expires = tim;
        enqueue_hrtimer(timer, new_base);
}
hrtimer の管理には、木構造が使われている。O(log n)。

◆scheduler_tick()

/* scheduler_tick() */
#define MIN_TIMESLICE           max(5 * HZ / 1000, 1)
#define DEF_TIMESLICE           (100 * HZ / 1000)
...
void scheduler_tick(void)
{
        unsigned long long now = sched_clock();
        struct task_struct *p = current;
        int cpu = smp_processor_id();
        struct rq *rq = cpu_rq(cpu);

        update_cpu_clock(p, rq, now);

        rq->timestamp_last_tick = now;
...
        if (!--p->time_slice) {
                dequeue_task(p, rq->active);
                set_tsk_need_resched(p);
                p->prio = effective_prio(p);
                p->time_slice = task_timeslice(p);
                p->first_time_slice = 0;

                if (!rq->expired_timestamp)
                        rq->expired_timestamp = jiffies;
                if (!TASK_INTERACTIVE(p) || expired_starving(rq)) {
                        enqueue_task(p, rq->expired);
                        if (p->static_prio < rq->best_expired_prio)
                                rq->best_expired_prio = p->static_prio;
                } else
                        enqueue_task(p, rq->active);
        } else {
...
        }
...
}

Last updated: 2007/01/22 09:50:20
Yasushi Shinjo / <yas@is.tsukuba.ac.jp>