時刻と時間の管理

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

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

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

■連絡事項

試験について

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

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

■今日の大事な話

モノトニック時刻の考え方
jiffies と HZ
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 では、ナノ秒単位。

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: スピーカーのトーン生成

◆CMOS RTC (Real Time Clock)

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

2つの機能がある。

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

制約

カウンタの値を読み書きできない
初期値は、2 の冪乗しか設定できない。

その他の割込み

TOD クロックが更新された。毎秒１回。
目覚まし。TOD クロックが設定された時刻と一致した時。

◆Local APIC (Advanced Programmable Interrupt Controller) Timers

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

カウンタと初期値は 32 ビット。
入力周波数は、CPU のフロントサイド・メモリ・バスの周波数と同じ。 (DDR 用以前)
PIT や CMOS RTC より高精度だが、ソフトウェアから周波数を調べる方法がない。 (PIT や CMOS RTCを使って調べるしかない。)

◆ACPI (Advanced Configuration and Power Interface)

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

発振器は、3579545 Hz (PIT の 3 倍)
カウンタは、24ビット。
初期値を保持するレジスタがない。24 ビットで一周する。
上位ビットが変化すると割込みがかかる。
省電力モードでも、通常通り動き続ける
読み書きするにも、1-2マイクロ秒かかることがある。

◆TSC (Time Stamp Counter)

Pentium 以降で利用可能。

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

◆HPET(High Precision Event Timer)

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

発振器の周波数は10MHz以上。
1個の増加する中央のカウンタがある。32ビット、または、64 ビット幅。ソフトウェアからカウンタ値を読み／書き／増加を停止できる。
比較器（タイマ）が、複数ある。最大32個。普通は3個以上ある。
比較器の値と中央のカウンタの値が一致すれば、そのタイマが発火し、割り込みを生成できる。
比較器が「定期的的(periodic)」として設定されていると、次に発火する比較器の値が自動的に設定（現在の値に既定値を加算）される。
比較器が「一回きり(one shot)」なら、発火して終わり。
読むのが遅い(1-2マイクロ秒かかる)ことがある。
ソフトウェアで比較器を設定しようとしている時に発火すると、危ない。

■jiffiesとHZ

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

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

利用例

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

実装。

kernel/timer.c
  53: u64 jiffies_64 __cacheline_aligned_in_smp = INITIAL_JIFFIES;

include/linux/jiffies.h
  82:	extern unsigned long volatile __jiffy_data jiffies;

実体は、jiffies_64 という64ビットの変数。
jiffies という名前でアクセスすると、下位32ビットが取れる。別の変数に見えるが、実体はリンカのトリックで同じになっている。
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() を呼ぶ。

kernel/time/tick-common.c
  60: static void tick_periodic(int cpu)
  61: {
  62:         if (tick_do_timer_cpu == cpu) {
...
  68:                 do_timer(1);
  70:         }
...
  72:         update_process_times(user_mode(get_irq_regs()));
...
  74: }

1272:	void update_process_times(int user_tick)
1273:	{
1274:	        struct task_struct *p = current;
...
1278:	        account_process_tick(p, user_tick);
1279:	        run_local_timers();
...
1283:	        scheduler_tick();
...
1285:	}

1303:	void run_local_timers(void)
1304:	{
1305:	        hrtimer_run_queues();
1306:	        raise_softirq(TIMER_SOFTIRQ);
1307:	}

tick_periodic() は、tick ごとになされる割り込みハンドラから呼ばれる。引数は、cpu の ID。
複数の CPU のうち、tick_do_timer_cpu ならば、do_timer() を呼び、 jiffies_64 を増やす。
update_process_times() を呼ぶ。
account_process_tick() で現在実行中のプロセスが消費した資源量(CPU 時間、ユーザ時間、カーネル時間)を記録する。
run_local_timers() で、Softirq の一種 TIMER_SOFTIRQ を起こす。
スケジューラにある関数 sheduler_tick() を呼ぶ。

◆do_timer()

kernel/timer.c
  53: u64 jiffies_64 __cacheline_aligned_in_smp = INITIAL_JIFFIES;
...
1315: void do_timer(unsigned long ticks)
1316: {
1317:         jiffies_64 += ticks;
1318:         update_wall_time();
...
1320: }

do_timer() では、64 ビットの変数 jiffies_64 が 1 だけ増やされる。
update_wall_time() で xtime 変数を更新する。

■カレンダー時刻の実装

◆xtime変数

xtime は、1970年1月1日00:00:00(GMT)からの秒数をナノ秒単位で構造体 struct timespec の形式で保持している。

kernel/time/timekeeping.c
 156: static struct timespec xtime __attribute__ ((aligned (16)));

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

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

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

kernel/time/timekeeping.c
 293:	void do_gettimeofday(struct timeval *tv)
 294:	{
 295:	        struct timespec now;
 296:	
 297:	        getnstimeofday(&now);
 298:	        tv->tv_sec = now.tv_sec;
 299:	        tv->tv_usec = now.tv_nsec/1000;
 300:	}

 213: void getnstimeofday(struct timespec *ts)
 214: {
...
 223:                 *ts = xtime;
 224:                 nsecs = timekeeping_get_ns();
 227:                 nsecs += arch_gettimeoffset();
...
 231:         timespec_add_ns(ts, nsecs);
 232: }

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

◆update_wall_time()

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

 734: void update_wall_time(void)
...
 802:         xtime.tv_nsec = ((s64) timekeeper.xtime_nsec >> timekeeper.shift) + 1;
...
 811:         if (unlikely(xtime.tv_nsec >= NSEC_PER_SEC)) {
 812:                 xtime.tv_nsec -= NSEC_PER_SEC;
 813:                 xtime.tv_sec++;
...
 820: }

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

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

struct timer_list: tick 単位
struct hrtimer: ナノ秒単位

◆struct timer_list

include/linux/timer.h

  12: struct timer_list {
...
  17:         struct list_head entry;
  18:         unsigned long expires;
  19:         struct tvec_base *base;
  20: 
  21:         void (*function)(unsigned long);
  22:         unsigned long data;
...
  34: };

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

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

add_timer(), add_timer_on(): タイマの登録。_on() は、CPU ごと。
mod_timer(): タイマの起動時刻の変更
del_timer(), del_timer_sync(), try_to_del_timer_sync(): タイマのキャンセル。 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) {
    ...
}

add_timer() により、delay tick 後に my_timer_func() が呼ばれる。
data

◆High-resolution kernel timers

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

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

hrtimer_init(): struct hrtimer 構造体の初期化。
hrtimer_start(): タイマの開始。モノトニック時刻(CLOCK_MONOTONIC)か、カレンダ時刻(CLOCK_REALTIME)か選べる。引数は、絶対指定(HRTIMER_MODE_ABS)か現在からの相対(HRTIMER_MODE_REL)か指定できる。
hrtimer_cancel(): タイマのキャンセル。
schedule_hrtimeout(): 指定した時間だけ現在実行中のプロセスを sleep させる。
ktime_get(): モノトニック時刻の取得。ktime は、ナノ秒単位。64ビット。
ktime_get_real(): カレンダ時刻の取得。

利用例。

    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, nano), HRTIMER_MODE_REL);
    ...

enum hrtimer_restart my_timer_handler(struct hrtimer *timer)
{
        ...
        return HRTIMER_NORESTART;
}

ハンドラで HRTIMER_RESTART を return すると、タイマが再設定される。

    hrtimer_init(&my_timer, CLOCK_MONOTONIC, HRTIMER_MODE_ABS);
    my_timer.function = func;
    ...
    hrtimer_start(&my_timer, ktime_add_ns(ktime_get(), period),
                      HRTIMER_MODE_ABS);

hrtimer の管理には、red-black tree が使われている。

■実行の遅延

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

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

様々な方法がある。

Busy loop

◆空ループ(busy loop)

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

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

unsigned long timeout = jiffies + 10; // 10 ticks
while (time_before(jiffies,timeout))
    continue;

例1: 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 と比較すると、オーバフローの問題が解決できる。

include/linux/jiffies.h
 106:	#define time_after(a,b)         \
 107:	        (typecheck(unsigned long, a) && \
 108:	         typecheck(unsigned long, b) && \
 109:	         ((long)(b) - (long)(a) < 0))
 110:	#define time_before(a,b)        time_after(b,a)
 111:	
 112:	#define time_after_eq(a,b)      \
 113:	        (typecheck(unsigned long, a) && \
 114:	         typecheck(unsigned long, b) && \
 115:	         ((long)(a) - (long)(b) >= 0))
 116:	#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 が使われている。

■プロセスにおけるtickの処理

◆account_process_tick()

kernel/sched.c
3446:	void account_process_tick(struct task_struct *p, int user_tick)
3447:	{
3448:	        cputime_t one_jiffy_scaled = cputime_to_scaled(cputime_one_jiffy);
3449:	        struct rq *rq = this_rq();
3450:	
3451:	        if (user_tick)
3452:	                account_user_time(p, cputime_one_jiffy, one_jiffy_scaled);
3453:	        else if ((p != rq->idle) || (irq_count() != HARDIRQ_OFFSET))
3454:	                account_system_time(p, HARDIRQ_OFFSET, cputime_one_jiffy,
3455:	                                    one_jiffy_scaled);
3456:	        else
3457:	                account_idle_time(cputime_one_jiffy);
3458:	}

3320:	void account_user_time(struct task_struct *p, cputime_t cputime,
3321:	                       cputime_t cputime_scaled)
3322:	{
...
3324:	        cputime64_t tmp;
3327:	        p->utime = cputime_add(p->utime, cputime);
3328:	        p->utimescaled = cputime_add(p->utimescaled, cputime_scaled);
3329:	        account_group_user_time(p, cputime);
...
3341:	}

account_process_tick() は、tick ごとに tick_periodic() から呼ばれる。
インターバル・タイマによる割り込みが行われた時 CPU が何を実行していたかによって 3 つに分類している。
- ユーザ・モードのユーザ・プロセス
- カーネル・モードのユーザ・プロセス
- アイドル
ユーザ・モードのユーザ・プロセスの場合は、task_struct の utime フィールドに 1 tick 分の時間を足し込む。

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

これを実現するために、どのようなコードを書けばよいか。以下の空欄を埋めなさい。

struct timer_list my_timer_list;

int my_arg_a,my_arg_b,my_arg_c;

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

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

バグ: 2011/02/22 my_timer とmy_timer_list が混在していました。どちらでも可とします。

Last updated: 2011/02/22 16:54:27

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