Explore "Full-Stack" in depth!

情報系の専門学校で、今は機械学習に的を絞って学習中。プログラミングを趣味でやりつつ、IT系のあらゆる知識と技術を身に付けるべく奮闘中。

UNIX/V6における実行プロセス切り替えのsleep()→swtch()を最低限理解する

目次

概要

この本読んでます。

はじめてのOSコードリーディング ~UNIX V6で学ぶカーネルのしくみ (Software Design plus)

はじめてのOSコードリーディング ~UNIX V6で学ぶカーネルのしくみ (Software Design plus)

  • 比較的ソースコード量も小さい割にOSの基本概念が実装されている
  • 殆どが高級言語であるC(但し現在の規格とはだいぶ違う)で書かれていて読みやすい
  • 殆どのUNIX系(Linux)の大元になっているので、基盤の知識として最適

という理由でUNIX V6を題材にコードリーディングをしていくという内容のものです。

ja.wikipedia.org

今回はこの本の中でも、 TSS(Time Sharing System)におけるコンテキストスイッチの仕組みを紹介していきます。

前提知識もそれなり話していくので、 ゆっくり読んで頂ければ幸いです。


前提

UNIX V6とは

UNIX V6は1975にベル研(Bell Laboratories)がリリースしたUNIX系OSの一つです。 ソースコードが公開されていたために、多くの研究機関等が派生系を開発していきました。

  • プロセス管理
  • メモリ管理
  • ファイルシステム
  • ファイル・周辺デバイスで共通のI/Oシステム
  • 割り込み処理
  • 端末処理のサポート

等、現在のOSに通ずる概念を実装しているため、 上記に示した書籍以外にもOSの基礎を勉強する題材としてよく用いられるようですね。

UNIX V6を構成するハードウェアの一つにPDP-11/40というものがあります。

ja.wikipedia.org

かの有名な DEC社 が開発したプロセッサで、
メモリの最上位8kビットを周辺デバイスレジスタマッピングするMemory Mapped I/Oが有名です。

PSW(Processor Status Word)

PDP-11/40が持つ16ビット長のレジスタです。

プロセッサの状態を示すのに用いられます。

構成を以下に示します。

f:id:orangebladdy:20190310201445p:plain

  • C…命令実行がキャリー(桁上り・桁下がり)を引き起こしたらセット
  • V…命令実行がオーバーフローを引き起こしたらセット
  • Z…命令実行結果が0だったらセット
  • N…命令実行結果が負だったらセット
    • これら4つのフラグは命令を実行した結果によって自動的に更新
  • Trap…トラップビット。
    • CPU内部の出来事により引き起こされるトラップ時に利用
  • Processor priority…プロセッサ優先度。
  • Previous Mode…以前のモード。00ならカーネルモード、11ならユーザモード
    • システムコールユーザモードからカーネルモードに切り替わってから処理
    • カーネルモード・ユーザモードは互いに独立した(プロセスの)仮想アドレス空間を持つ
    • 以前のモードを保持することで、2つのモード間のデータやり取りを可能に

これらビットフィールドを覚えている必要はありません。
但し、命令実行に関する情報を格納している事は知っておくべきでしょう。

汎用レジスタ

PDP-11/40が持つ8つのレジスタです。
次のような用途で用いられます。

  • r0,r1→計算用、関数の戻り値用
  • r2,r3,r4→ローカル処理
  • r5→フレームポインタ・環境ポインタ
    • スタックフレーム内で特定の位置を指しているポインタ。
    • エラー時に関数のスタックトレースが表示されるが、それは各関数のフレームポインタを辿れているから。
  • r6→スタックポインタ…各プロセスの持つスタックの先頭ポインタ
  • r7→プログラムカウンタ…r7で示されたメモリアドレスから命令を読み込み、命令を実行

特に重要なのは太字のレジスタです。

プロセスとは

カーネル実行プログラムの概念を管理するための概念です。

こちらの記事も参考に。
まだ低レイヤーの知識がほぼないときに頑張って理解しようとした記事なので分かりやすいかも。

drumato.hatenablog.com

プログラムが実行される時、
ファイルに記述されたプログラムはメモリにロードされます。

仮想記憶方式を取っているアーキテクチャでは、
このプロセスは仮想アドレス空間を持ちます。

仮想アドレスはMMU(Memory Management Unit)によって物理アドレスに変換されます。

並列処理

V6では、複数ユーザが同時にシステムを利用出来ます。

これは並列処理とかマルチプロセッサシステムとか呼ばれます。

実際にはCPUはシステム内に一つなので、
TSS(Time Sharing System)によって複数プロセスを随時切り替えて実行しています。

これはプロセス・タスク・ジョブ単位で細かくCPUの処理時間を分け
随時切り替えながら処理を行う事で、
ユーザからは並行処理してるように見えるというものです。

当時はユーザ単位でCPU処理時間が分けられていました。

user構造体

各プロセスの状態・情報を保持する構造体です。

プロセスに一つずつ存在していました。

struct user
{
    int u_rsav[2];      /* プロセスの切替時に実行中のr5,r6を退避 */
    int u_fsav[25];     /* save fp registers PDP-11/40環境では利用しない */
                    /* rsav and fsav must be first in structure */
    char    u_segflg;       /* ファイルの読み書き時に使用されるフラグ */
    char    u_error;        /* エラー時にエラーコードが格納される */
    char    u_uid;          /* 実効ユーザID */
    char    u_gid;          /* 実効グループID */
    char    u_ruid;         /* 実ユーザID */
    char    u_rgid;         /* 実グループID */
    int u_procp;        /* このuser構造体に対応したproc[]エントリを指す */
    char    *u_base;        /* ファイルの読み書きをするときにパラメータを渡すために利用 */
    char    *u_count;       /* ファイルの読み書きをするときにパラメータを渡すために利用 */
    char    *u_offset[2];       /* ファイルの読み書きをするときにパラメータを渡すために利用 */
    int *u_cdir;        /* カレントディレクトリのinode[]エントリ */
    char    u_dbuf[DIRSIZ];     /* namei()で使用される作業領域。ファイル・ディレクトリ名が格納 */
    char    *u_dirp;        /* (ユーザ・カーネル)プログラムから与えられたファイルのパス名を読む時に使用 */
    struct  {           /* namei()で使用される作業領域。ディレクトリエントリが格納 */
        int u_ino; //inode番号
        char    u_name[DIRSIZ]; //ファイル、ディレクトリ名
    } u_dent;
    int *u_pdir;        /* namei()で対象ファイル・ディレクトリの親ディレクトリが格納される */
    int u_uisa[16];     /* ユーザPAR(Page Address Register)の値 */
    int u_uisd[16];     /* ユーザPDR(Page Description Register)の値 */
    int u_ofile[NOFILE];    /* プロセスが開いているファイル */
    int u_arg[5];       /* システムコール処理でユーザプログラムから引数を渡す時等に使用 */
    int u_tsize;        /* テキストセグメントのサイズ(64バイト単位) */
    int u_dsize;        /* データ領域のサイズ(64バイト単位) */
    int u_ssize;        /* スタック領域のサイズ(64バイト単位) */
    int u_sep;          /* flag for I and D separation PDP-11/40環境では基本0*/
    int u_qsav[2];      /* システムコール処理中にシグナルが発生した時に使用されるr5,56の退避領域 */
    int u_ssav[2];      /* スワップアウトによりuser.u_rsav[]の値が不正なときに使用されるr5,r6の退避領域 */
    int u_signal[NSIG];     /* シグナルを受信したときの動作の設定に使用 */
    int u_utime;        /* ユーザモードとしてCPUを使用した時間(単位:ティック) */
    int u_stime;        /* カーネルモードとしてCPUを使用した時間(ティック) */
    int u_cutime[2];        /* 子プロセスがユーザモードとしてCPUを使用した時間(ティック) */
    int u_cstime[2];        /* 親プロセスがカーネルモードとしてCPUを使用した時間(ティック) */
    int *u_ar0;         /* システムコール処理時にユーザプロセスのGRやPSWを捜査するときに使用 */
    int u_prof[4];      /* プロファイル用。本書では省略 */
    char    u_intflg;       /* システムコール処理中にシグナル処理が発生したかどうかを判定するフラグ */
                    /* kernel stack per user
                     * extends from u + USIZE*64
                     * backward not to reach here
                     */
} u;

/* u_error codes */
#define EFAULT  106 //ユーザ・カーネル空間間でデータ転送を失敗
#define EPERM   1 //スーパーユーザでない
#define ENOENT  2 //指定したファイルが存在しない
#define ESRCH   3 //シグナルを送る先のプロセスが存在しないか既に消滅している
#define EINTR   4 //システムコール処理中にシグナル処理
#define EIO 5 //I/Oエラー
#define ENXIO   6 //デバイス番号で示されたデバイスが存在しない
#define E2BIG   7 //execシステムコールで実効プログラムへ512バイト以上の引数リストが与えられた
#define ENOEXEC 8  //実行プログラムのフォーマット(マジックナンバー)が不正
#define EBADF   9  //開かれていないファイルに対する操作、RDONLYに対するwrite,WRONLYに対するread
#define ECHILD  10 //waitシステムコールで子プロセスが見つからない
#define EAGAIN  11 //forkシステムコールでproc[]に空きエントリが見つからない
#define ENOMEM  12 //プロセスに対して使用可能なメモリ容量以上の領域を割り当てようとした
#define EACCES  13 //ファイル、ディレクトリのアクセス権限がない
#define ENOTBLK 15 //ブロックデバイスのスペシャルファイルではない
#define EBUSY   16 //mount,umountシステムコールで対象マウントポイントが使用中
#define EEXIST  17 //linkシステムコールなどで、既にそのファイルが存在する
#define EXDEV   18 //別のデバイスのファイルに対してリンクを貼ろうとした
#define ENODEV  19 //デバイス番号で示されたデバイスは存在しない
#define ENOTDIR 20 //ディレクトリではない
#define EISDIR  21 //ディレクトリに対する書き込み
#define EINVAL  22 //パラメータ不正
#define ENFILE  23 //file[]が溢れた
#define EMFILE  24 //user.u_ofile[]が溢れた
#define ENOTTY  25 //端末のスペシャルファイルではない
#define ETXTBSY 26 
/*テキストセグメントとして割り当てようとしたプログラムファイルが他のプロセスによりデータファイルとして使用されていた。
もしくはテキストセグメントとして割り当てられたファイルに対して書き込もうとした*/
#define EFBIG   27 //ファイルサイズが大きすぎる
#define ENOSPC  28 //ブロックデバイスの容量が足りない
#define ESPIPE  29 //パイプファイルに対してseekシステムコールを実効
#define EROFS   30 //読み取り専用でマウントされたブロックデバイスのファイルやディレクトリを更新しようとした
#define EMLINK  31 //リンク数が多すぎる
#define EPIPE   32 //壊れたパイプファイル

こんな感じで カーネルからグローバル変数uからアクセス出来るようになっていました。

proc[]とproc構造体

実行優先度等、カーネルから必要とされる情報を扱っています。
メモリに常駐するため、カーネルに対するプロセスの情報提供等が高速に働きます。

struct proc{ //各プロセス
  char p_stat; //NULLならproc[]は空とみなされる
  char p_flag; //フラグ。後述
  char p_pri; //実行優先度。値が小さいほど優先度が高い
  char p_sig; //受信したシグナル
  char p_uid; //ユーザID
  char p_time; //メモリまたはスワップ領域に存在している時間(単位:秒)
  char p_cpu; //CPUを利用した累積時間(単位:https://ja.wikipedia.org/wiki/%E3%82%B7%E3%82%B9%E3%83%86%E3%83%A0%E6%99%82%E5%88%BB)
  char p_nice; //実行優先度を下げる補正値。デフォルトは0で、システムコール`nice`によりユーザが任意の値を設定
  int p_ttyp; //プロセスを操作する端末
  int p_pid; //プロセスのID
  int p_ppid; //親プロセスのID
  int p_addr; //割り当てられたメモリの"物理"アドレス(64バイト単位)
  int p_size; //割り当てられたメモリのサイズ(64バイト単位)
  int p_wchan; //スリープ(休止状態)の理由
  int *p_textp; //使用しているテキストセグメント
} proc[NPROC];

/* stat codes */
#define SSLEEP 1 //休眠状態(実行優先度=負)
#define SWAIT 2 //休眠状態(実行優先度=非負)
#define SRUN 3 //実行可能状態
#define SIDL 4 //プロセス生成処理中
#define SZOMB 5 //ゾンビプロセス(親プロセスが終了ステータスを待ち受けていない)
#define SSTOP 6 //トレースによる介入待ち

/* flag codes */
#define SLOAD 01 //メモリ上に存在
#define SSYS 02 //システムプロセス。スワップ対象にならない。(V6ではproc[0]のみ)
#define SLOCK 04 //スワップアウト禁止フラグ
#define SSWAP 010 //スワップアウトにより、user.u_rsav[]の値(後述)が不正。user.u_ssav[]からr5,r6を復帰しなければならない
#define STRC 020 //トレースされている
#define SWTED 040 //トレース処理に使用
}

仮想アドレス空間

プロセスに割り当てられる仮想アドレス空間は、
以下の図を見ると分かりやすいと思います。

f:id:orangebladdy:20190310211518p:plain

真ん中の大きなメモリがプログラムをロードした物理メモリになります。
このプログラムがプロセスA・Bによって同時に実行されると、

プログラムの命令列が格納されたテキストセグメントは共有されます。

ただしデータセグメント(PPDA・データ領域・スタック領域の総称)は必ず独立しています。
ここにはローカル変数やプログラムが用いる静的変数等の情報が入っています。

APR(Active Page Register)と呼ばれるレジスタを用いて、
仮想アドレスから物理アドレスへの変換を行います。

APRPAR(Page Address Register)PDR(Page Description Register)からなります。
詳しくはこちらの記事を参考にしてください。
とても詳しいです。

d.hatena.ne.jp

PDP-11/40はカーネルモードユーザモード用に2セットのAPRを持ちます。

各ユーザプロセスのAPRの値はuser構造体に保存されている。

カーネルグローバル変数uで実行プロセスのuser構造体にアクセスできるのは カーネルモード用のAPRがそのように設定されているからです。


本題

さて、本題に入りましょう。

前提知識は完全に理解していなくても大丈夫です。
前提知識の部分に貼ったuser構造体proc構造体は常に参照できるようにしておくといいと思います。

並列処理におけるプロセスのフロー

  • 実行プロセスは CPUの処理時間(仕様時間)によってsleep()が実行されます。
    • これは 実行しているプロセスを中断 します。
  • 次に、 swtch()によって実行プロセスを切り替え ます。
  • 中断されたプロセスを再実行するときは wakeup()を呼び出します。
    • 今回はwakeup()は省略します。

この全体感を持っておくことが重要です。
それでは各関数を見ていきましょう。

sleep()

sleep()が実行されるのは、

  • ユーザプロセスが waitシステムコールを発行した時
  • 周辺デバイスの処理完了を待つ時
  • 使用中の資源が開放されるのを待つ時

です。

sleep()が実行されると、
proc.p_statSSLEEP又はSWAITに設定します。
proc.p_statはプロセスの状態を保持するメンバです。

めちゃくちゃにコメントアウトしているので、
長いコードも読めると思います。

sleep(chan, pri)
{
    register *rp, s;

    s = PS->integ; //このプロセスの再実行のために現在のPSWの値を退避
    rp = u.u_procp; //rpに実行プロセスのproc[]エントリを格納
    if(pri >= 0) { //もしpriが0以上であれば
        if(issig()) //シグナルを受け取っているかチェックし
            goto psig; //シグナル処理に移行。aletuは6章で
        spl6(); //実行優先度を6に引き上げて割り込みを防ぐ
        rp->p_wchan = chan; //実行プロセスの設定
        rp->p_stat = SWAIT;
        rp->p_pri = pri;
        spl0(); //変更処理後元に戻す
        if(runin != 0) { //スワップ対象がいないか?
            runin = 0; //詳細は省く
            wakeup(&runin); //プロセススケジューラを起動
        }
        swtch(); //実行プロセスの切り替え
        if(issig())
            goto psig;
    } else { //プロセッサ優先度が0未満
        spl6(); //同じく
        rp->p_wchan = chan;
        rp->p_stat = SSLEEP; //SWAITではなくSSLEEPに
        rp->p_pri = pri;
        spl0();
        swtch();
    }
    PS->integ = s; //中断したプロセスの再実行。値の復元
    return;

psig:
    aretu(u.u_qsav); //u.u_qsavはシステムコールの処理中にシグナルを受け取ったときにr5,r6を退避する領域
}

aretu()は引数で渡された領域からr5,r6の値を取り出してPSWに復元します。

コードの意味はわかると思うので、
ここでは流れをもう一度復習しましょう。

sleep()まとめ

  • プロセス再実行のためにPSWの値は退避
  • 引数で渡されたpriが0以上かどうかで挙動を変える。
    • 0未満ならシグナルは無視
    • 0以上ならシグナルを受け取る(シグナルについては解説しない)。
  • 実行優先度を引き上げて割り込みを防いだ後、
    • 実行プロセスのp_wchan=変数等のアドレスを格納
      • つまり アドレスが指す資源の解放待ちを示す
    • 実行プロセスの状態をSWAIT
    • 実行プロセスの優先度をpri
  • 退避していたPSWの値を復元

という流れです。

大体の流れは掴めたでしょうか。

swtch()

実行プロセスの選択アルゴリズム

swtch()は次に実行するプロセスを選択する関数になります。
プロセスはproc[]に順に格納されている(因みに50個)ので、

proc[]を順に辿っていく事で全てのプロセスを見る事が出来ます。

この時、実行プロセスとして選択する条件は、

  • 実行可能状態(SRUN) である。
  • 実行優先度が最も高い (proc.p_priが最も小さい)

プロセスを選択します。

特定のプロセスを実効プロセスとして明示的に指定することは出来ません。

子プロセスに制御を移すために親プロセスがwaitシステムコールを発行することはよくありますが、
子プロセスよりも優先度の高いプロセスが存在すればそちらが先に実行されます

コンテキストスイッチ

実行プロセスが中断される時にはsevu()によってuser構造体に現在の状態を保存し、
中断していたプロセスが再実行されるときには
retu(),aretu()によってuser構造体から状態を復元します。

このような仕組みをコンテキストスイッチと言います。
これら3つの関数はアセンブリ言語で書かれています。

swtch()
{
    static struct proc *p; //proc[]を走査する時に利用
    register i, n;
    register struct proc *rp;

    if(p == NULL)
        p = &proc[0]; //proc[0]はスケジューラ用のシステムプロセスでシステム起動時に生成される
    savu(u.u_rsav); //中断するプロセスのr5,r6を保持しておく
    retu(proc[0].p_addr); //スケジューラプロセスの起動

loop:
    runrun = 0; //runrunは実行プロセスより実行優先度の高いプロセスが存在する?
    rp = p;
    p = NULL;
    n = 128;
    /*
     * Search for highest-priority runnable process
     */
    i = NPROC;
    do { //実行プロセスとして選択する条件に合致するか一つずつ走査
        rp++;
        if(rp >= &proc[NPROC])
            rp = &proc[0];
        if(rp->p_stat==SRUN && (rp->p_flag&SLOAD)!=0) {
            if(rp->p_pri < n) {
                p = rp;
                n = rp->p_pri;
            }
        }
    } while(--i);
    if(p == NULL) { //選択対象プロセスが存在しなかった場合
        p = rp;
        idle();
        goto loop; //割り込み発生により実行可能なプロセスが現れるのを待つ
    }
    rp = p;
    curpri = n; //実行優先度のグローバル変数
    retu(rp->p_addr); //r5,r6の値を復帰
    sureg(); //選択プロセスのAPRの値をハードウェアのユーザAPRに還元し、ユーザ空間の切り替え
    if(rp->p_flag&SSWAP) { //SSWAPが立っていればクリア
        rp->p_flag =& ~SSWAP;
        aretu(u.u_ssav); //u_ssavはスワップアウト等によりu_rsavの値が不正な時に利用するr5,r6の退避領域
    }
    return(1);
}

proc[]の全探索時には、
上から順にではなく実行プロセスの1個下から順に一周します。

swtch()まとめ

  • 中断するプロセスのr5,r6をu_rsavに保持
  • pには前回swtch()で選択されたプロセスの proc構造体 が入っている。
  • proc[]エントリを順にたどり、条件に合致するプロセスを探す
  • retu()によってカーネルAPRが操作され、実行プロセスのuser構造体にグローバル変数 uアクセスできるように
  • 退避したr5,r6の値は復帰される
  • 最後にsureg()によってユーザ空間の切り替え

総評

かなり難しい内容だったとは思います。
私も完全な理解が出来たかと言われると若干微妙ですが、
低レイヤーやっぱり楽しいUNIX系OSの勉強楽しいってなるような内容でしたね。

記事にすることで多くの知識が身についたと思います。
皆さんもこの本とても良いので是非取り組んでください。
とても難しいですが、絶対に為になると思います。

はじめてのOSコードリーディング ~UNIX V6で学ぶカーネルのしくみ (Software Design plus)

はじめてのOSコードリーディング ~UNIX V6で学ぶカーネルのしくみ (Software Design plus)

おまけ

総合PV10k超えました。ありがとうございます。

PVを増やすために記事を書いているわけではないですが、
有益な記事を書いているわけではない私のブログをいつも見て頂けて本当に嬉しいです。

これからも勉強した事の共有・作ったものの紹介・その他諸々の所感をほそぼそと書いていきます。
よろしくおねがいします。