情報学類 オペレーティングシステム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/
高橋浩和, 小田逸郎, 山幡為佐久: "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
図? オペレーティング・システムの働き
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);
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);
図? システムコールとアップコール
アップコールは、システム・コールの逆に、オペレーティング・システムがユー ザ・レベルの関数を呼び出す。 ウインドウ・システムのプログラムでは、call-back 関数やlistener として利 用されている。図? タイマ関連のハードウェアの基本モデル
2つの機能がある。
その他の割込み
/* 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); }
/* 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); }
図? callout 待ち行列(1)
f(x) を取り除いて実行した後。図? callout 待ち行列(2)
g(y), h(z) を取り除いて実行した後。図? callout 待ち行列(3)
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 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); } } }
/* 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() */ #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 { ... } ... }