3.2 Main algorithms

3.2.1 Signals

カーネルは避けられない出来事をプロセスに知らせるためにシグナルを用いる.

ユーザがいつも使うシグナルは

send_sig() がシグナルを送る.引数は

  1. シグナル番号
  2. プロセス記述子
  3. 送り手の優先権(the priority of the sender)

ソースコードは linux-1.2.0/kernel/exit.c

int send_sig(unsined long sig, struct task_struct * p, int priv)
{

優先権は2種類サポートされている.

  1. ユーザプログラムから送られるシグナル priv = 0kill(0)とか)
  2. カーネルから送られるシグナル priv = 1

カーネルは一般ユーザのプロセスが一定の条件下になってもよいときのみ,プロセスにシグナルを自由に送ることができる.

SIGCONTシグナル(SIGSTOPシグナルで一時停止したプロセスを再開するためのシグナル)はプロセスから送られる可能性がある.

    if (!p || sig > 32)
        return -EINVAL;
    if (!priv && ((sig != SIGCONT) || (current->session != p->session)) &&
        (current->euid != p->euid) && (current->uid != p->uid) && !suser())
        return -EPERM;
    if (!sig)
        return 0;
    /*
     * プロセスがもうゾンビになってたらなかったことにしてくれ
     */
    if (p->state == TASK_ZOMBIE)
        return 0;

シグナルを受信したプロセスのために,タスク構造体のメンバ signal にシグナル番号がセットされる.

    if ((sig == SIGKILL) || (sig == SIGCONT)) {
        if (p->state == TASK_STOPPPED)
            p->state = TASK_RUNNING;
        p->exit_code = 0;
        p->signal &= ~( (1 << (SIGSTOP - 1)) | (1 << (SIGTSTP - 1)) |
                        (1 << (SIGTTIN - 1)) | (1 << (SIGTTOU - 1)) );
    }
    /* SIGSTOP, SIGTSTP, SIGTTIN, SIGTTOUの要求に依存している */
    if ((sig >= SIGSTOP) && (sig <= SIGTTOU))
        p->signal &= ~(1 << (SIGCONT - 1));
    /* 実際にシグナルを生成する */
    generate(sig, p);
    return 0
}

シグナルを受信したプロセスによって緊急を要するシグナルがない場合:スケジューラはプロセスにTASK_RUNNING状態(実行可能な状態)を返している(Section 3.2.5).

直前にユーザモードに切り替わったものを除き,プロセスはスケジューラによって再び活性し, ret_from_sys_call() (Section 3.3.1)が動く.もしシグナルがカレントプロセス(current prosess)を待っているなら, 実際のシグナル操作を引き継ぐ do_signal() 関数を呼ぶ.この関数はプロセスのレジスタとスタックを操作する( arch//kernel/signal.c).アセンブラを呼び出すのでアーキテクチャに依存する.

シグナル操作ルーチン動いているあいだ,シグナルはブロックされる. current->blocked

current はtask_struct型の構造体( kernel/sched.c)で,定義は include/linux/sched.h

struct task_struct {
/* ハードコード - 触るな */
    volatile long state;    /* -1 実行不可, 0 実行可能, >0 停止*/
    long counter;
    long priority;
    unsigned long signal;
    unsigned long blocked;    /* マスクされたシグナルのビットマップ */
    unsigned long flags;    /* あとでプロセスフラッグごとに定義する */
    int errno;
    int debugreg[8];  /* ハードウェアをデバッグするレジスタ */
    struct exec_domain *exec_domain;
/* いろんなの */
    struct linux_binfmt *binfmt;
    struct task_struct *next_task, *prev_task;
    struct sigaction sigaction[32];
    unsigned long saved_kernel_stack;
    unsigned long kernel_stack_page;
    int exit_code, exit_signal;
    unsigned long personality;
    int dumpable:1;
    int did_exec:1;
    int pid,pgrp,tty_old_pgrp,session,leader;
    int    groups[NGROUPS];
    /* 
     * (オリジナルの) 親プロセス, 一番若い子ども, 弟,
     * 兄,それぞれへのポインタ  (p->father は
     * p->p_pptr->pid とも書ける)
     */
    struct task_struct *p_opptr, *p_pptr, *p_cptr, *p_ysptr, *p_osptr;
    struct wait_queue *wait_chldexit;    /* wait4() 用 */
    unsigned short uid,euid,suid,fsuid;
    unsigned short gid,egid,sgid,fsgid;
    unsigned long timeout;
    unsigned long it_real_value, it_prof_value, it_virt_value;
    unsigned long it_real_incr, it_prof_incr, it_virt_incr;
    long utime, stime, cutime, cstime, start_time;
    struct rlimit rlim[RLIM_NLIMITS]; 
    unsigned short used_math;
    char comm[16];
/* ファイルのシステム情報*/
    int link_count;
    struct tty_struct *tty; /* NULL if no tty */
/* ipc の材料 */
    struct sem_undo *semundo;
    struct sem_queue *semsleeping;
/* このタスクのためのldt - Wineに使われる.  もしNULLならdefault_ldtが使われる */
    struct desc_struct *ldt;
/* このタスクのためのtss */
    struct thread_struct tss;
/* ファイルシステムの情報 */
    struct fs_struct fs[1];
/* 開くファイルの情報 */
    struct files_struct files[1];
/* メモリ管理の情報 */
    struct mm_struct mm[1];
};

システムコール sigreturn .シグナル操作ルーチンから返り,スタックを掃除する.POSIXには規定されていないのでシステムによって動作が異なる.

sigreturn()が見つからない.asklinkage int型を返すsys_sigreturn()ならアーキテクチャ依存のコードを見つけた.

arch/i386/kernel/signal.c

/*
 * このregs->espたちは実のところまだsigstacksを使っていないのだけど..
 */
asmlinkage int sys_sigreturn(unsigned long __unused)
{
#define COPY(x) regs->x = context.x
#define COPY_SEG(x) \
if ((context.x & 0xfffc) && (context.x & 3) != 3) goto badframe; COPY(x);
#define COPY_SEG_STRICT(x) \
if (!(context.x & 0xfffc) || (context.x & 3) != 3) goto badframe; COPY(x);
        struct sigcontext_struct context;
        struct pt_regs * regs;

        regs = (struct pt_regs *) &__unused;
        if (verify_area(VERIFY_READ, (void *) regs->esp, sizeof(context)))
                goto badframe;
        memcpy_fromfs(&context,(void *) regs->esp, sizeof(context));
        current->blocked = context.oldmask & _BLOCKABLE;
        COPY_SEG(ds);
        COPY_SEG(es);
        COPY_SEG(fs);
        COPY_SEG(gs);
        COPY_SEG_STRICT(ss);
        COPY_SEG_STRICT(cs);
        COPY(eip);
        COPY(ecx); COPY(edx);
        COPY(ebx);
        COPY(esp); COPY(ebp);
        COPY(edi); COPY(esi);
        regs->eflags &= ~0x40DD5;
        regs->eflags |= context.eflags & 0x40DD5;
        regs->orig_eax = -1;            /* syscallの検査を無効にする */
        return context.eax;
badframe:
        do_exit(SIGSEGV);
}

sigstack(2) -- シグナルスタックのcontext(訳せない)を設定または取得するシステムコール .

3.2.2 Interrupts

割り込みはハードウェアがOSとのやりとりを許可するために使われる.

Linuxには高速と低速,1種類の割り込みがある.

Slow Interrupts

低速割り込みは通常の割り込みである.他の割り込みは,処理している間は合法である.低速割り込みが処理されたあと,追加の活動がシステムによって処理される.たとえば,スケジューラは要求される限り呼び出される.典型的な低速割り込みの例は時間割り込み(Section 3.2.4)である.この割り込みの処理は以下の動きを伴う.

PSEUDO_CODE IRQ (intr_num, intr_controller, intr_mask)
{

はじめに,すべてのレジスタは保存され,割り込みの受理が割り込みコントローラに承認される.同時に,同じタイプの割り込みの受理は拒否される.

    SAVE_ALL; /* macro in include/asm/irq.h */
      ACK(intr_controller, intr_mask);

割り込みの入れ子の深さはintr_count変数に記録され,その後追加の割り込みが有効になり割り込みルーチン自身が呼び出される.これは割り込みされたプロセスのためにレジスタのセットのコピーが同様に提供される.このレジスタは,ユーザプロセスかカーネルが割り込んだかどうかを判断するために,複数の割り込み操作によって使われる.

    ++intr_count;
    sti();
    do_IRQ(intr_num, Register)

一度割り込みルーチンが正常に実行されると,割り込みコントローラは再び承認可能な割り込みのタイプを知らせる.加えて,割り込みカウンタは減算される.

    cli();
    UNBLK(intr_controller, intr_mask)
    --intr_count;

ret_from_sys_call()はアセンブラルーチンへ飛ぶ.これは低速割り込みやシステムコールのあとに,より一般的な管理タスクを処理する.この関数は返らない.これはレジスタに保存したSAV_ALLを復元し,割り込みルーチンの終わりに必要なiretを実行する.

    ret_from_sys_call();
} /* PSEUDO_CODE IRQ */

Fast Interrupts

高速割り込みは短く,複雑でないタスクに用いられる.高速割り込みが操作される間,操作ルーチンが許可して取り込まない限り,その他すべての割り込みは拒否される.代表的な例はキーボード入力( drivers/char/keyboard.c )である.

PSEUDO_CODE fast_IRQ (intr_num, intr_controller, intr_mask)
{

はじめに,これまでのようにレジスタは保存されるが,通常のC関数によって変更されるものだけである.これはつまり,もしアセンブラコードが操作ルーチンに使われたのであれば,残りのレジスタは事前に,もしくは復帰した事後に保存されていなければならないことを意味する.

    SAVE_MOST; /* macro in include/asm/irq.h */

割り込みコントローラは低速割り込みと同じ方法で割り込みのタイプを知らせ,intr_count変数を増加させる.このときさらなる割り込みは,割り込み操作自身が呼び出されたあとで承認される.sti()は呼び出されない.

    ACK(intr_controller, intr_mask);
    ++intr_count;
    do_fast_IRQ(intr_num)
    UNBLK(intr_controller, intr_mask)
    --intr_count;

割り込み操作が完了したら,RESTORER_MOSTが保存されたレジスタに帰り,割り込まれたプロセスのためにiretが呼び出される.

    RESTORE_MOST; /* macro in include/asm/irq.h */
} /* PSEUDO_CODE fast_IRQ */

include/asm-i386/irq.h

#define SAVE_ALL \
    "cld\n\t" \
    "push %gs\n\t" \
    "push %fs\n\t" \
    "push %es\n\t" \
    "push %ds\n\t" \
    "pushl %eax\n\t" \
    "pushl %ebp\n\t" \
    "pushl %edi\n\t" \
    "pushl %esi\n\t" \
    "pushl %edx\n\t" \
    "pushl %ecx\n\t" \
    "pushl %ebx\n\t" \
    "movl $" STR(KERNEL_DS) ",%edx\n\t" \
    "mov %dx,%ds\n\t" \
    "mov %dx,%es\n\t" \
    "movl $" STR(USER_DS) ",%edx\n\t" \
    "mov %dx,%fs\n\t"   \
    "movl $0,%edx\n\t"  \
    "movl %edx,%db7\n\t"

/*
 * SAVE_MOST/RESTORE_MOSTは高速版IRQハンドラに使われ,
 * SA_INTERRUPTフラグを使うので導入された. このIRQの一種は
 * リターンするときにシグナル操作などをおこなうルーチンを呼びだず,
 * レジスタへの保存にゆとりがあるかもしれない.これらも同様に極めて小さく,
 * 実際にシグナル操作などが必要ないシリアル回路やハードディスクドライバのような
 * 小さくて高速な割り込みに適している. 
 *
 * Also note that we actually save only those registers that are used in
 * C subroutines (%eax, %edx and %ecx), so if you do something weird,
 * you're on your own. The only segments that are saved (not counting the
 * automatic stack and code segment handling) are %ds and %es, and they
 * point to kernel space. No messing around with %fs here.
 */
#define SAVE_MOST \
    "cld\n\t" \
    "push %es\n\t" \
    "push %ds\n\t" \
    "pushl %eax\n\t" \
    "pushl %edx\n\t" \
    "pushl %ecx\n\t" \
    "movl $" STR(KERNEL_DS) ",%edx\n\t" \
    "mov %dx,%ds\n\t" \
    "mov %dx,%es\n\t"
#define RESTORE_MOST \
    "popl %ecx\n\t" \
    "popl %edx\n\t" \
    "popl %eax\n\t" \
    "pop %ds\n\t" \
    "pop %es\n\t" \
    "iret"

3.2.3 Booting the system

アセンブラ(arch/i386/boot/setup)の

jmp 0x1000 , KERNEL_CS

で32ビットOSのカーネルの開始アドレスへ飛び, arch/i386/kernel/head.Sstartup_32:から続く.ここではハードウェアとカーネルの実行に必要な環境が初期化される.初期化が完了したら,最初のC関数start_kernel()init/main.c から呼び出される.

ここでは最初にアセンブラコードが見つけたハードウェアについてのデータが保存される.

asmlinkage void start_kernel (void)
{
    memory_start = paging_init(memory_start, memory_end);

    trap_init();
    init_IRQ();
    sched_init();
    parse_options(command_line);
    init_modules();

    memory_start = console_init(memory_start, memory_end);
    memory_start = bios32_init(memory_start, memory_end);
    memory_start = kmalloc_init(memory_start, memory_end);
    memory_start = chr_dev_init(memory_start, memory_end);
    memory_start = blk_dev_init(memory_start, memory_end);
    memory_start = inode_init(memory_start, memory_end);
    memory_start = file_table_init(memory_start, memory_end);
    memory_start = name_cache_init(memory_start, memory_end);
    mem_init(memory_start, memory_end);

    buffer_init();
    time_init();
    sock_init();

    sti();

この時点で動いているプロセスはプロセス0である.これは残りのシステムの初期化をするプロセス1を作るためにシステムコールforkを呼び出す.

    if (!fork())
        init();

その後,プロセス0は要求されないコンピュータの時間ばかりを使うことだけを考慮するだろう.

    for(;;)
        idle();

プロセス1はinit()関数を実行する.これはファイルシステムの初期化やルートファイルシステムのマウントをsetupシステムコールによっておこなう.コンソールへの接続はその後確立され,ファイル記述子0,1,2が開かれる.その後 /etc/init/bin/init/sbin/init の実行を試みる.通常,これらはLINUX下のバックグラウンドプロセスの実行をはじめ, すべての接続された端末上で getty の実行を確保する.そしてユーザはシステムと対話できる.

その後,シェルのファイルや /etc/rc を実行する.

3.2.4 Timer interrupt

システム時間はハードウェア的に実装される.これらの割り込みルーチンは時間の計測を引き受ける.Linuxでは,システム時間はticksで測定される.1ticksは10ミリ秒.時間割り込みは100 ticksに1回起こる.

時間はunsigned long型のjiffies変数に格納される.この変数は時間割り込みによってのみ変更される.

実時間(actual time)はstruct timeval型のxtimeに記録され,時間割り込みによってアップデートされる.

割り込みルーチンは時間割り込みの発生ごとに,保存されたレジスタが引数として与えられる.この検査によって割り込まれたプロセスがユーザモードかカーネルモードかを判断できる.以下の時間割り込みの説明は元の時間割り込みを要約した処理である.

static void do_timer (int irq, struct pt_regs * regs)
{

システム時間が更新される.

    jiffies++;

実時間xtimeはシステムコールadjtimeによって操作される.

    time_phase += time_adj;
    ...
    if (timer_adjust)
        ...

もしタスク0が活動しているか(active)か現在のタスクが計算時間を使い切ったのであればスケジューラがすぐに呼び出される.この処理はneed_resched変数の内容次第である.もしセットされていればスケジューラがアセンブラルーチンret_from_sys_call()から呼び出される.

    if (current == task[0] || (--current->counter) <= 0) {
        current->counter = 0;
        need_resched = 1;
    }

割り込みされたプロセスの時間の更新

    if (user_mode(regs))
        current->utime++;
    else
        current->stime++;

仮想時間のインターバル時間は,もし割り込まれたプロセスがユーザモードであれば更新される.時間いっぱいになったらSIGVTALARMシグナルがプロセスへ送られる.

    if (user_mode(regs) && current->it_virt_value && 
        !(--current->it_virt_value))
    {
        current->it_virt_value = current->it_virt_incr;
        send_sig(SIGVTALARM, current, 1);
    }

インターバルタイマITIMER_PROFは現在のタスクのために更新される.タイマが満了したらSIGPROFシグナルがプロセスへ送られる.

    if (current->it_prof_value && !(--current->it_prof_value)) {
        current->it_prof_value = current->it_prof_incr;
        send_sig(SIGPROF, current, 1);
    }

実時間のためのインターバルタイマの更新はより難しい問題だ.すべてのタスクを見てシグナルを送るか決める.

    for_each_task(p)
        if (p->it_real_value && !(--p->it_real_value)) {
            p->it_real_value = p->it_real_incr;
            send_sig(SIGLRM, p, 1); /* SIGLRMはalarm(2)からのタイマシグナル */
        }

すべての時間割り込みは関連性のある情報を無くさないよう保証しなければならない.

    cli();
    itimer_ticks++;
    if (itimer_ticks > itimer_next)
        need_resched = 1;

LinuxではプロセスにCPU消費量の制限をかけることができる.これはsetrlimitシステムコールによっておこなわれる.時間割り込みは実行されている時間を確認して,もし制限に達したらそのプロセスにSIGKILLを送る.

    if ((current->rlim[RLIMIT_CPU].rlim_max != RLIM_INFINITY) &&
        ((current->stime + current->utime) / HZ) >
            current->rlimit[RLIMIT_CPU].rlim_max)
    {
        send_sig(SIGKILL, current, 1);
    }

Linuxのプロセスは時間割り込みによって管理されるいくつかのシステム全域のタイマである. 時間割り込みをしすぎないために,ただたんに満期になったタイマを確認する.

    for (mask = 1, tp = timer_table + 0; mask; tp++, mask += mask) {
        if (mask > timer_active)
            break;
        if (!(mask & timer_active))
            continue;
        if (tp->expries > jiffies)
            continue;
        mark_bh(TIMER_BH);
    }
    if (timer_head.next->expires < jiffies)
        mark_bh(TIMER_BH);
    if (tq_timer != &tq_last)
        mark_bh(TQUEUE_BH)
    sti();
} /* do_timer */

3.2.5 The scheduler

スケジューラは個々のプロセスにプロセッサ資源を割り当てる責任がある.

Linuxのスケジューリングアルゴリズムはschedule()関数で実装されている.schedule()はシステムコールのあとと,低速割り込みのあとにneed_reschedret_from_sys_callルーチンによって検査されneed_reschedに値がセットされていれば呼び出される.

schedule()関数は以下の要素からなる

  1. インターバルタイマが全プロセスの実時間it_real_valueを検査する.
  2. 検査されたプロセスはTASK_RUNNING状態を返す.
  3. counter変数の値が最も大きいプロセスを活性させる.

コードは以下の通り

asmlinkage void schedule(void)
{
    int c;
    struct task_struct * p;
    struct task_struct * next;
    unsigned long ticks;

itimer_ticksitimer_nextは時間割り込みによって非同期的に更新される.

    cli();
    ticks = itimer_ticks();
    itimer_ticks = 0;
    itimer_next = ~0;
    sti();

    need_resched = 0;

最後にインターバルタイマが更新される.

    for_each_task(p)
    {
        if (ticks && p->it_real_value) {
            if (p->it_real_value <= ticks) {
                send_sig(SIGALRM, p, 1);
                if (!p->it_real_incr) {
                    p->it_real_value = 0;
                    goto end_itimer;
                }
                do {
                    p->it_real_value += p->it_real_incr;
                } while (p->it_real-value <= ticks);
            }
            p->it_real_value -= ticks;
            if (p->it_real_value < itimer_next)
                itimer_next = p->it_real_value;
        }
        end_itimer:
    } /* for_each_task(p) */

もしプロセスがTASK_INTERRUPTIBLE状態であり,プロセスによってシグナルが無視されず届いたのであればプロセスの状態はTASK_RUNNING状態になる.

    for_each_task(p)
    {
        if (p->state != TASK_INTERRUPTIBLE)
            continue;

        if (p->signal & ~p->blocked)
            p->state = TASK_RUNNING;

        if (p->timeout && p->timeout <= jiffies)
        {
            p->timeout = 0;
            p->state = TASK_RUNNING;
        }
    } /* for_each_task(p) */

もし待っているプロセス(state == TASK_RUNNING)の優先度が0であれば,全プロセスの動的優先度は静的優先度priorityを参考にリセットされる.その後,各プロセスはふたたび0より大きい動的優先度を取得し,スケジューリングアルゴリズムが再びおこなわれる.

    start_schedule:

    c = -1;
    next = &init_task;
    for_each_task(p) {
        if (p->state == TASK_RUNNING && p->counter > c) {
            c = p->counter;
            next = p;
        }
    }

もし変数cの値が0であれば,全プロセスの優先度は再計算される.

    if (c == 0) {
        for_each_task(p)
            p->counter = (p->counter >> 1) + p->priority;
        goto start_schedule;
    } /* if (c == 0) */

ここで,nextは実行可能なプロセス(c > 0)も実行不能なプロセス(c == -1)も含むだろう.そしてnextinit_taskを指すだろう.どちらの場合もnextが指すタスクはこの次に活性される.

    switch_to(next);
} /* schedule() */