山本一成さんの「エレファントな解法」に対抗して動的計画法による「エレガントな解法」を考えてみた

エレファントな解法(？)

先日Ponanza開発者の山本一成さんがブログでこのような記事を書いておられました.

note.mu

この記事の中では以下の問いが投げかけられています.

問. コインを100回投げて表か裏が10回連続で出る確率は？

山本さんのブログでは「エレファントな解法」としてモンテカルロ法を用いた力任せの解法が紹介されています. つまりは, 乱数を使って100回コインを投げるというシミュレーションを何度も繰り返して条件を満たす確率を近似的に求めるというわけです. この方法ならきちんと確率を求めることができなくても, それなりに確率を正しく求められます. 困った時の最終手段としては非常に便利だと思います.

ちなみに, こういった方法が「エレファントな解法」と呼ばれているのは初めて知りました.

エレガントな解法

「エレファントな解法」のことは一旦置いておいて, 山本さんがエレガントな解法について「私は正直解ける気がしません」と言っておられたのが少し気になりました. 競プロerならぱっと見で「動的計画法で解けそう？」と感じた人も多いんじゃないでしょうか, 僕もそう感じました.

というわけで, この問題を動的計画法(DP)で解いてみたいと思います.

DPで解いてみる

先に断っておくと, 解いてみてから気づいたのですがちょっと冗長なDPをしています. あと, 答えはあったものの, 若干怪しいところがあります(おい).

基本的な考え方

DPそのものの説明はいろいろと調べてもらうのが早いと思うのですが, 僕は「コインの投げ方って2^N通りあるけれど, 実はそんなに場合分けしなくても"何回コインを投げて何回連続で同じ面が出てるか"で場合分けすれば十分じゃない？」というものだと思ってます.

例えば, 10回コインを投げて最後に表が3回連続で出るような投げ方って2⁶通りありますが, 今回の問題では最初の6回までに表裏どっちが出たかって知らなくても答えは出せます.

というわけで, これらをまとめて計算して, さらに上手に前の計算結果を利用していくことで計算量を落とすことができます.

解法

まず, コインを投げる回数をN, 求めたい確率の連続回数をMとします. そして, 以下のようなDPを考えます.

dp[i][j][k][l]:
i回コインを投げた時に, 最後にj回連続で(k = 0: 表, 1: 裏)が出て, 条件を(l = 0: 満たしていない, 1: 満たしている)確率

遷移に関しては, (k, l)の4パターンについてそれぞれ表が出た場合と裏が出た場合を考えます. 表が連続している場合に限って説明します.

まだ条件を満たしていいない場合は, 表が出たら連続回数を1増やし裏が出た場合は連続回数を1に戻してあげます. このとき, 表がM回以上連続していたらl = 1, つまり条件をすでに満たした状態に遷移してあげます.

すでに条件を満たしている場合も, 表が出たら連続回数を1増やし裏が出た場合は連続回数を1に戻してあげます.

裏が連続している場合もほぼ同様です.

最終的な答えは, N回コインを投げて最後の連続数とコインの裏表に関係なく条件を満たしている確率です. つまり, dp[N][j][k][1] (0 <= j < N, k = 0, 1)の和が答えです.

というわけで, O(N²)の時間計算量で答えが出せます.

実装

これをC++で書いてみると以下のようになります.

#include <cstdio>

int main(void) {
  const int N = 100, M = 10; // コインを投げる回数, 連続する回数
  const double P = 0.5;      // 表が出る確率

  // dp[i][j][k][l]:
  //   i回コインを投げて,
  //   最後のj回連続して(k = 0: 表, 1: 裏)が出て,
  //   (l = 0 : まだ条件を満たしていない, 1: すでに条件を満たしている)確率
  double dp[N + 1][N + 1][2][2];
  for(int i = 0; i < N + 1; i++) {
    for(int j = 0; j < N + 1; j++) {
      dp[i][j][0][0] = 0;
      dp[i][j][0][1] = 0;
      dp[i][j][1][0] = 0;
      dp[i][j][1][1] = 0;
    }
  }
  dp[0][0][0][0] = P;
  dp[0][0][1][0] = (1 - P);

  for(int i = 0; i < N; i++) {
    for(int j = 0; j < i + 1; j++) {

      // (k, l) = (0, 0): 表が連続, 条件を満たしてない
      dp[i + 1][j + 1][0][j + 1 >= M] += dp[i][j][0][0] * P;
      dp[i + 1][1][1][0] += dp[i][j][0][0] * (1 - P);

      // (k, l) = (0, 1): 表が連続, 条件を満たした
      dp[i + 1][j + 1][0][1] += dp[i][j][0][1] * P;
      dp[i + 1][1][1][1] += dp[i][j][0][1] * (1 - P);

      // (k, l) = (1, 0): 裏が連続, 条件を満たしてない
      dp[i + 1][1][0][0] += dp[i][j][1][0] * P;
      dp[i + 1][j + 1][1][j + 1 >= M] += dp[i][j][1][0] * (1 - P);

      // (k, l) = (1, 1): 裏が連続, 条件を満たした
      dp[i + 1][1][0][1] += dp[i][j][1][1] * P;
      dp[i + 1][j + 1][1][1] += dp[i][j][1][1] * (1 - P);
    }
  }

  // 最終的な答えは, dp[N][j][k][1] (0 <= j < N, k = 0, 1)の和
  double ans = 0;
  for(int j = 0; j < N + 1; j++) {
    ans += dp[N][j][0][1];
    ans += dp[N][j][1][1];
  }
  printf("%.15lf\n", ans);
}

実行した結果「コインを100回投げて表か裏が10回連続で出る確率」は0.086659044348362となりました. 山本さんがブログの中で知人の数学者の方に「エレガントな解法」で計算してもらったという値と一致してます, やったね.

まとめ

というわけで, こんな感じでこの問題は答えが出せます. これぐらいならまだなんとか確率求められますが, 難しくなると圧倒的にエレファントな解法に分がありそうですね(無理やりまとめた).

ちなみに, 頑張るとO(NM)で答え出せるはずです. この解法はchokudaiさんが書いておられますね......プログラムみじかw

さっきの山本さんの問題、コード気になる人がいたから実行結果と合わせて貼っておくhttps://t.co/AKIMa7zLha

— chokudai(高橋 直大) (@chokudai) 2018年2月4日

【メモ】UNIX V6コードリーディング(メモリ周りの整理/まとめ)

今回の内容

前回まではトラップハンドラについて読み進めていました.

0x19f.hatenablog.com

前回とは大きく内容が変わってメモリ周りの話を整理していきたいと思います(先にシグナルを読んでもよかったかも). 実は先々週あたりの勉強会を思い出して書いているので内容が確かじゃないかもしれないです. 書籍のページ数が結構飛び飛びになるので, 適宜どのあたりの話をしているか書いていきたいと思います.

アドレス変換(p52〜p55)

仮想アドレスから物理アドレスへの変換はp52に書かれていますが, 1点だけ補足を. APRが8つあるということは, 逆に言うと仮想アドレス空間は8Kバイト(= 2¹³)毎に違うAPRを参照して物理アドレスへの変換を行うことになります. p50に書かれている「データ領域はテキストセグメントの後ろの8Kバイト刻みのアドレスに割り当てられます」の理由はここにあります. テキストセグメントとデータセグメントは物理アドレス上では連続していません. つまり, 同じAPRに割り当てられません. このあたりはアドレス変換の仕方についてよく考えると確かにそうなるなぁという感じになります.

仮想アドレス空間(p48〜p52)

細かいメモリの操作をする箇所を読むにあたって, 仮想アドレス空間と物理アドレス空間がどのようにマッピングされているかを理解しておくと非常に理解が進みます. 意識しておいたほうが良さそうなポイントをいくつか.

1. テキストセグメントとデータセグメントは物理メモリ上では別々の連続した領域.
2. テキストセグメントはプロセス間で共有される.
3. データセグメントはPPDA, データ領域(ヒープ領域を含む), スタック領域からなる.
4. PPDAにはuser構造体とカーネルスタック領域が置かれる.
5. PPDAはユーザープロセスの仮想アドレス空間にマッピングされない(ユーザー空間からはアクセスできない).
6. データ領域とスタック領域は物理アドレス空間では連続している.
7. ヒープ領域はアドレスが大きくなる方向に, スタック領域は小さくなる方向に伸びていく.
8. スタック領域は仮想アドレス空間の一番上位(0xffff)に割り当てられている.
9. 物理アドレス上でヒープとスタックがぶつかった場合は拡張が行われる(expand関数).

仮想アドレス空間の操作

仮想アドレス空間に対する操作を行っている(と思われる箇所)をピックアップしてみました.

仮想アドレス空間のマッピングの変更はestabur, suregあたりで行われるようです(p103〜). 細かいところは読めてないですが, estaburでuser構造体にAPRにセットする情報を格納, suregでuser構造体の情報に従ってAPRの値を操作するようです.

データ領域の拡張はbreakシステムコールで実現されます(p118). Cライブラリのmallocなどの内部で使用されるようです. 長年疑問だったmallocした時のメモリはどこから出てくるのかに対する答え(？)が少し得られたようで, 個人的には結構面白いと感じました. 実際にはOS側はデータ領域を拡張/縮小しているだけで, その他の諸々はCライブラリのmallocがやってくれているという感じなんでしょうか？

スタック領域の拡張はトラップハンドラの中で行われます(p176, grow).

ちなみに, 実行プロセスのPPDAはカーネル用のAPR6から参照できるようになっており, プログラム中ではuという変数で参照できます(p54一番下). この切り替えはコンテキストスイッチの際にしれっと行われています(p78). 当然ですが, このときにユーザー空間のマッピングが変更されます. おそらく, estaburとsuregが分かれている理由はこの辺にあって, コンテキストスイッチの際はuser構造体に格納された情報からマッピングし直すだけなのでsuregだけが呼び出されてます. (細かく中を読めていないので間違ってるかもしれないですが...)

まとめ

メモリ周りをいろいろと整理してみましたが, これを一発で理解するのは無理ですね(). ただ, いろいろと考えながら読んでみると本当によくできているなぁと思わされることばかりです.

次回の予定

スワッピングあたり？

【メモ】UNIX V6コードリーディング(トラップハンドラ/システムコール, p171〜184)

今回の内容

前回は, 主にタイマー割り込みに関連する箇所を読んでいました.

0x19f.hatenablog.com

今回は, トラップハンドラでの処理を見ていきます. システムコールについてもこの辺りに書かれています.

トラップハンドラtrap

トラップハンドラも割り込みハンドラ同様に呼び出しが行われcsvが実行された後のスタックの状態は以下のようになります.

	値	引数	備考
sp	pc		csvから戻るのに使用されるだけ(あまり関係ない)
	退避されたr2
	退避されたr3
	退避されたr4
r5	退避されたr5
	pc(割り込みハンドラから返る先)
	マスクされたPSW	dev
	割り込まれたプロセスのsp	sp
	古いr1	r1
	PSW	nps
	古いr0	r0
	割り込まれたプロセスのpc	pc
	割り込まれたプロセスのPSW	ps

trap関数の9行目でu.u_ar0に引数r0のアドレスを格納していますが, これはスタック上のアドレスになります. 実際にスタック上の値を操作する際はu.u_ar0[R0]のようにして操作するのですが, R0はただの定数でスタック上のr0が格納されている位置からのオフセットです. 同様にしてR0〜R7とRPS(PSWの操作に用いる)を使ってスタック上の値を書き換えています. トラップハンドラ内ではあまりこの操作は行われませんが, システムコールハンドラ内で行われるのでしょうか？

その後のswitch分でdev(トラップ種別)の値によって処理が分岐していきますが, 基本的にはシグナルを送って処理は終わりです. 例外はillegal instruction, floating exception(カーネルプロセス), segmentation exception, システムコールの時です.

illegal instructionの時はSETDなる謎の命令か否かをチェックしているようですが, 正直なんのためのものなのかあまりわかってないです.

カーネルプロセスでは浮動小数点演算を行わないらしいのですが, PDP11の特性上ユーザープロセスが行った浮動小数点演算によるfloating exceptionがトラップ発生後に引き起こされることがあるらしく, その場合はそのユーザープロセスにシグナルを送って関数から抜けます.

segmentation exceptionの場合, スタックを拡張します. それでもexceptionを回避できない場合は, プロセスにシグナルを送ります. このスタックの拡張はgrowという関数の中で行われるのですが, 仮想メモリ空間の話とかをあまりちゃんと理解していないので一旦飛ばします. ちなみに, growの前にbackupという関数が実行されているのですが, この関数はUNIX V6の中で最難関らしいです. exceptionが起きた時の状態を再現する関数らしいのですが, すべてアセンブリで書かれておりおまけに中でPDP11にはないレジスタの挙動をエミュレートしているようです. 実際にソースコードを読むと/ hard partというコメントが見つけられます. 最難関なのでは仕方ないので飛ばします.

システムコールの場合の処理の前にシステムコールの処理の流れをまとめたいと思います.

システムコールの処理の流れ

システムコールハンドラはsysent構造体によって管理されます. この構造体にはシステムコールの引数の数とハンドラのアドレスが格納されます.

sysent構造体の配列sysentに各システムコールの引数の数とハンドラのアドレスが格納されています. この配列は要素数が64で, 添字はsys命令のオペランド(6 bit)と対応しています.

システムコールの0番は間接呼び出しに割り当てられています. 間接呼び出しというものを自分は初めて知ったのですが, どうやら普通の呼び出しと異なるのは引数の渡し方のようです. 通常の呼び出しは, sys命令の後に引数が埋め込まれます. 一方で, 間接呼び出しの場合は, sys命令の後に引数のアドレスが埋め込まれます. これは推測なのですが, 直接命令の場合は引数が埋め込まれる場所がテキストセグメントになるため, 動的にシステムコールの引数が変わる場合に困ってしまうのでこのような仕組みが用意されているのではないかと考えています. sys命令の次にデータ領域のアドレスを埋め込んでおけば, 複数のプロセスでテキストセグメントを共有しつつ個別に引数を扱うことができます. あるいは, 引数の数が動的に変わる場合などでしょうか.

システムコールの引数は上述のようなsys命令の後に埋め込むものと, r0を経由するものがあります.

トラップハンドラ内でのシステムコールの処理

話はトラップハンドラのswitch文に戻ってくるのですが, システムコールの場合の処理を見ていきます. 基本的にはエラーフラグを初期化, 間接呼び出し/直接呼び出しそれぞれの場合で引数とシステムコールの番号を取得, trap1を呼び出してシステムコールハンドラを実行, エラーフラグの処理という流れです.

特筆すべきなのがtrap1を用いてハンドラを呼び出している点です. trap1の中を見てみるとわかるのですが, フラグを立ててからsavuしてシステムコールハンドラを呼び出しています. これが意味するところなのですが, これはシステムコール中にシグナルを受け取った場合にエラーを起こすためのものらしいです. 詳しくはシグナル処理のあたりで書かれています. このsavuに対応するaretuはsleep関数の末尾にあります. このエラーはシステムコールハンドラがsleepを実行して処理を中断している間にシグナルを受け取った場合に起こるものらしいです. シグナルを受け取った場合は, trap1が返る場所から処理が継続されます. この場合は, フラグが立ったまま処理が続行されるため, その後のtrapでの処理でユーザープロセスにはエラーが返ります. このエラーを見てユーザープロセスは再度システムコールを実行することができるようになっています.

まとめ

ということで割り込みとトラップを見てきましたが, なかなか複雑だなぁという感想です. もう一度プロセス管理あたりも読み直してみると納得感が増すのかなぁと思います.

次回の予定

シグナル？メモリ管理？ 未定です

Code Thanks Festival 2017 参加記

Code Thanks Festival 2017に参加してきました

12/2(土)に行われたCode Thanks Festival 2017に参加してきました. 運良く予選で良いパフォーマンスを出すことができて, 参加権を勝ち取ったという感じです.

www.recruit-jinji.jp

会場到着まで

起きると脳が直感的に開始時刻に間に合わないことを理解した. 開始時刻が11:25なのに対して僕が起きた時刻が10:30, 会場のお台場まで1時間はかかるのでどう考えても間に合わない. とにかく家を飛び出した. 久しぶりのゆりかもめに揺られながら会場への到着を待つ.

あの、報告なのですが、遅刻が確定しました()

— Shinya Kato (@0x19f) 2017年12月2日

結局なんとかコンテスト開始前には会場にたどり着くことができ, ほっと胸を撫でおろす.

コンテスト

コンテストは100 - 200 - 300 - 300 - 400 - 500 - 600 - 600の計8問. 1800点以上だとパーカーがもらえるとのことなので1800点を目標に頑張ろうという気持ちになる.

コンテスト開始と同時にA, B, Cと順調にACしていく. D問題には少し苦戦した, 制約を見るにgcdなんだろうなぁと思うのだがどうすればいいのかわからない. いろいろと悩むが, 高校数学で教わった1次不定方程式を思い出しAC. あと2問でパーカーだ.

しかし, ものごとはそう順調には進まない. E問題がインタラクティブ形式, 問題を見てすぐに13の累乗をクエリとして出力すればいいと思った. しかし, これが罠だった. よくよく考えると13⁴は10000を超えてしまうのだ. 頭のついていない僕はこのことに気づくのに30分を要した. 問題を読み始めてから1時間ほど経つが一向に糸口がつかめない. 焦りばかりが募っていく. 落ち着け, まだ問題は他にもあるんだ, そう自分自身に言い聞かせた.

心を切り替えてF問題を読んでいく. 制約が小さければ, 単純なDPだ. しかし, 制約が大きい. 代わりに和が一定で抑えられるという謎の条件が付け加えられている. 瞬間的に頭にルートという言葉が浮かんできた. そうだ, 何かがルートで抑えられるに違いない. 大量のWAを出しながら, 一歩ずつ答えに近づいていく. 残り40分というところでついにFを通した.

ここで, 苦戦していたEに戻る. これを通せばパーカーだ, 何としても通したい. なんらかの方法でクエリからコインの重さが復元可能なのであれば, 和と5種類のコインの重さの組は1対1に対応するはずだ. そう思い手当たり次第にいろいろな枚数の組み合わせで, このような条件を満たすものを探し始めた. すると5の累乗であればこの条件を満たすことを発見した. 残り20分, まだ焦る時間じゃない. そう言い聞かせながら, 不恰好なプログラムを書いていく. クエリの応答からコインの重さを逆引きするテーブルを作りそれを参照する作戦だ. 一心不乱にコピペを駆使してプログラムを書き上げ, 提出した. 結果は......AC. 残り時間は10分だった.

結果は参加者100人中の54位. なによりも1800点を達成できたことが嬉しかった.

表彰 and 解説

大学の先輩であらせられるtossyさんが1位だったり, imulanさんが3位だったりして, やはり目指すべきはあそこなんだなぁと思った. ふーらくたるさんが折角の5位なのにマイクが入っておらずコメントが全く聞き取れなくておもしろかった.

ふーらくたる「%$*#(@(*W)$#)($#(@」

— Shinya Kato (@0x19f) 2017年12月2日

あと, chokudaiさんはファッション英語勢なのかと思っていたけれど, 本当に英語苦手みたいだった.

懇親会

TLのみなさんにこんにちは. 名前入りの名札を見て「あの赤いCの人」とわかってもらえるのは非常に便利なので, みなさんも実名Twitterしていきませう. 懇親会の間にtreeoneさんの通知が400件溜まっていたらしく, 本当におもしろい.

解散の後も参加者の方々とボーリングしたりカラオケしたりしてきました. いやー, 非常に楽しかったですねぇ.

【メモ】UNIX V6コードリーディング(クロック割り込み, p160〜170)

今回の内容

前回までは, 割り込みとトラップが発生してからハンドラが実行されるまでの流れを追っていました.

0x19f.hatenablog.com

今回は, クロック割り込みハンドラのお話です. クロック割り込みによって処理される指定時間実行とsleepシステムコールも一緒に見ていきます.

クロック装置

UNIX V6では以下の2種類のクロックが使用可能です.

• 電源周波数に従うクロック: KW11-L
• プログラマブルクロック: KW11-P

前者のクロックは電源周波数が50Hzか60Hzかによってクロック周波数が変わります. 後者のクロックの間隔などを設定することができるようです.

クロック周波数はparams.hの中でHZとしてdefineされているようです. 書籍ではどちらの装置を用いるにしてもクロック周波数が60Hzであるという前提で解説を進めています.

クロック割り込みハンドラ

クロック割り込みハンドラはC言語で書かれたclock関数になります. この関数に前回まで見てきた箇所で積まれたスタックの中身が引数として渡ります.

C言語で書かれている関数は, コンパイルの際に先頭にcsvというアセンブリで書かれた関数の実行が挿入されます. 簡単に説明だけしておくと, r2, r3, r4を退避する関数です. このcsvについては, 書籍の78ページから詳しく説明されています. (このメモを書き始める前に読んでます.)

csvが実行された直後のスタックの状態とclock関数の引数の対応は以下のようになります. 引数の内容がわからなくなったらここを見ましょう.

	値	引数	備考
sp	pc		csvから戻るのに使用されるだけ(あまり関係ない)
	退避されたr2
	退避されたr3
	退避されたr4
r5	退避されたr5
	pc(割り込みハンドラから返る先)
	マスクされたPSW	dev
	割り込まれたプロセスのsp	sp
	古いr1	r1
	PSW	nps
	古いr0	r0
	割り込まれたプロセスのpc	pc
	割り込まれたプロセスのPSW	ps

クロック割り込みハンドラの中身を読んでいくと以下の処理が上から順にされていることがわかります.

• クロック毎の処理
  • クロック装置のレジスタを再設定
  • 指定時間実行の処理を行う ... (1)
  • CPU時間のインクリメント
• 1秒毎の処理
  • 時刻のインクリメント
  • sleepしているプロセスを起こす ... (2)
  • プロセスの実行優先度を再計算 ... (3)
  • スワップ処理を継続できない場合の再スケジューリング ... (4)
  • シグナル処理 ... (5)
• 4秒毎の処理
  • lightning boltの処理 ... (6)

以下, いくつか数字を振ったものについて補足しておきます.

(1) 指定時間実行

これについては, 書籍の162ページから詳しく書かれています. 指定時間に実行したい関数を登録するtimeout関数などのソースコードが出てきますが, 書いてある通りに読めば難しい箇所はないと思います. クロック割り込みハンドラの中では, 指定時間になった関数の実行をしています.

(2) sleepしているプロセスを起こす

書籍の165ページにsleepシステムコールのハンドラであるsslepが掲載されているのですが, これだけでは少し何が起きているのかわからないのでメモをば.

まず, timeはグローバル変数で現在の時刻を秒単位で管理しています. いわゆるUNIX時間(？). この時刻データは, 2 word分(32 bit)に収められています. dpadd, dpcmpはこの2 wordをまとめて足したり比較したりするための関数です. 書籍の441ページに説明があります.

もう一つ関数の中に出てくるグローバル変数に, toutという時刻データがあります. これは, 次にsleepから起こされる関数が起こされる時刻を表しています.

個人的にここが今回得られた理解の中で一番おもしろかったのですが, sleepしているプロセスはtoutが示す時刻を過ぎたらすべて起こされます. そして, 指定された時刻を過ぎていないプロセスは再びsleep状態に戻ります.

これを実現しているのがsslep関数中のwhile文です. while文の条件が真になるのは, 指定された秒数分sleepした場合のみです. 真になるまでは, if文によって直近に起こさないといけないプロセスを起こす時間をtoutに格納して, sleep関数を呼び出しています. sleep関数については, 73ページにソースコードが掲載されています. sleep関数の第一引数には待っている資源のアドレスを渡すのですが, ここではtoutのアドレスを渡しています. clock関数の中でwakeup関数にtoutを渡して, すべてのsleep中のプロセスを起こしています. 起こされたプロセスはwhile文の最後から処理を再開し, while文の継続条件を判定してsslep関数から抜けるもしくは再度sleep関数を呼び出します.

このようにしてsleepシステムコールは実現されているわけですが, これって何かに似てるなーと思ったらJavaのマルチスレッドプログラミングで出てくるwait/notifyAllと同じようなもんかなという気持ちになりました. あれもnotifyAllですべてのプロセスが起きた時にwhile文でガードするってことをしますよね.

(3) プロセスの実行優先度を再計算

プロセスのあたりは一応読んだはずなのですが, 細かいところはかなり忘れているので再度読み直します...

(4) スワップを継続できない場合の再スケジューリング

スワップ辺りを飛ばしているので, あまりよくわかってないです...

(5) シグナル処理

シグナルの話は次の章に出てくるので一旦飛ばす.

(6) lightning bolt

lightning boltというのは, カーネルが特に待ち時間は決まっていないけれど適当に待たせておきたい時に使用するものらしいです. lbolt変数を待ち資源にしてsleepさせておくんでしょうか？ 4秒に1度clock関数の中で起こされます.

次回の予定

トラップハンドラの中身を読み進めていきたいと思います.

【メモ】UNIX V6コードリーディング(割り込み, p154〜159, その2)

今回の内容

前回の続きから.
アセンブリで書かれたtrapとcallを詳しく見ていきます.

0x19f.hatenablog.com

前回解決できなかった疑問点

nofaultが設定されている場合の割り込み箇所への復帰方法について, 前回の記事には,

もう一つわからないことがあって, この後のトラップハンドラからどうやってユーザープログラムに復帰するのかということ.

なんてことを書いたのですが, そもそも前提が間違ってました.
nofaultを設定した上で命令を実行するのはカーネルプロセスでした.
このnofaultというのは, カーネルプロセスが例外が起きるとまずい命令を実行する前に設定するというものみたいです.
ここからは推測ですが, こういった命令を実行する直前にカーネルはnofaultにエラーハンドラを設定しカーネルスタックに戻り先のアドレスを積んだ状態で命令を実行するのではないかと.
すると, 例外が起きた場合には, スタックに戻り先のアドレスのみが積まれた状態でnofaultが指すアドレスにジャンプし, その処理の最後にrtsで戻り先に復帰するという風になるんじゃないでしょうか.

こっちの方はわかってないのですが, 読み進めていく上ではあまり問題なさそうなので一旦スルーします.

ここが若干謎で, SR0の1ビット目が1になるとMMUが有効になるらしい.
しかし, なぜこのタイミングでSR0に1を格納しているのかがわからない.

trapでnofaultが設定されていない場合

nofaultに値が入っていない場合は, 前回軽く書いた通りSR0, SR2を退避, SR0を初期化してjsr命令でcall1へとジャンプします.
この時, 古いr0の値がスタックに積まれ, r0には_trap(C言語で書かれたtrap関数のアドレス)が格納されることに注意してください.

call1にジャンプすると, spをひとつ上にずらし, プロセッサ優先度を0にし, callの途中へとジャンプします.
ここからの処理は後述するcallでの処理とほぼ同じです.
callの1行目を実行した直後とスタック, r0の状態は同じ形になっている点に注意.

最終的なスタックの状態は以下のようになっており, r0にはtrap関数のアドレスが入っています.

	値
sp	トラップ種別を含んだPSW
	古いr0
	割り込まれたプロセスのpc
	割り込まれたプロセスのPSW

callの処理

前々回ぐらいのおさらいになるのですが, callに処理が移った時のスタックの状態は以下のようになっています.

	値
sp	古いr0
	割り込まれたプロセスのpc
	割り込まれたプロセスのPSW

ここにPSWの値が積まれて以下のような状態になります.

	値
sp	PSW
	古いr0
	割り込まれたプロセスのpc
	割り込まれたプロセスのPSW

ここからはtrapのnofaultが設定されていない場合と同じ処理になります.
スタックが同じような形をしているところに気をつけてください.

まず, 古いr1がスタックに積まれます.
次にmfpi命令を用いて割り込まれたプロセスのspをスタックに積みます.
mfpi命令はPSWの前のモードの仮想アドレス空間から値を取得して現在のモードのスタックに積む命令です.
ここで得たspを用いて割込みハンドラの中でスタックを操作するのかな？と予想しています.
さらに, SPWをスタックに積み, 下位5ビット以外を0でクリアします.

ここで, 割り込まれたプロセスがユーザーモードだったかカーネルモードだったかで処理が分岐するのですが, やっていることは大きくは変わらないです.

ユーザーモードだった場合は, jsr命令で現在のpcをスタックに積みながらr0に設定された割り込みハンドラにジャンプします.
ここで積んだpcが割り込みハンドラからの戻り先になります.
割り込みハンドラから処理が戻ると, コンテキストスイッチを行います.
割り込みによってプロセスの実行可能状態や優先度が変化した分を考慮するためのものかなと考えています.
最後に, mtpi命令で前モードのspの値を戻します.

カーネルモードだった場合は, PSWの前モードをユーザーモードに書き換えてから, 割み込みハンドラへジャンプします.
ここは上記と同様にjsrを用いています.

割り込みハンドラが呼び出される時のスタックは以下のような状態になります.
実際にはこれがハンドラ関数の引数として扱われます.
具体的にどのように使われるのかはclock, trapなどの関数を見ていくことになるかと思います.

	値
sp	pc(割り込みハンドラから返る先)
	マスクされたPSW
	割り込まれたプロセスのsp
	古いr1
	PSW
	古いr0
	割り込まれたプロセスのpc
	割り込まれたプロセスのPSW

ここからは両モード共通です.
スタックに積んでいたr1, r0を復帰してrtt命令で割り込まれた箇所に復帰します.

まとめ

ソースコードを読むだけだと理解しづらいので, 簡単にまとめておきます.

• カーネルは例外が起こりうる命令を実行する前にnofaultを設定することがある.
• nofaultが設定されているトラップは設定されたハンドラによって処理される.
• そうでないトラップはtrap関数によって処理される.
• 割り込みはそれぞれの割り込みハンドラによって処理される.

次回の予定

割り込みハンドラ(clock)とトラップハンドラ(trap)を読んでいく予定.

【メモ】UNIX V6コードリーディング(割り込み, p154〜159)

今回の内容

前回の続きから.
アセンブリで書かれたcallとtrapの実行を詳しく見ていきます.

0x19f.hatenablog.com

call, trapの実行

書籍ではあまり言及されていない箇所が多くあまり進みませんでした.
以下, ざっくりとした理解です.
(間違っている箇所がありそう.)

割り込みの場合は, callの内部でr0に格納された割り込みハンドラが呼び出されます.
このr0に割り込みハンドラが格納される箇所は前回見たとおりです.

トラップの場合は, nofaultにトラップハンドラが指定されている場合とそうでない場合で分岐が発生します.
nofaultにトラップハンドラが指定されている場合は, そのトラップハンドラが呼び出されます.
そうでない場合は, callの中へとジャンプしC言語で書かれたtrap関数が呼び出されます.
(アセンブリ中では_trapで参照されています.)

基本的には, スタックになにが積まれていくのかが大事なようです.
ちらっと先読みした感じだと, この後割り込みハンドラ/トラップハンドラに処理が移った際にこのスタックがC言語で書かれた関数の引数になるようです.

trap

トラップ種別が含まれたPSWの値をカーネルスタックに格納します.
trap関数内でこの種別によって処理が分岐するんでしょうか.
nofaultが0かで分岐するのをtst, bne命令で実現しています.

nofaultにトラップハンドラが指定されている場合:
SR0レジスタを1で初期化.
ここが若干謎で, SR0の1ビット目が1になるとMMUが有効になるらしい.
しかし, なぜこのタイミングでSR0に1を格納しているのかがわからない.
実は割り込みが発生したタイミングでMMUが無効になってたりするんでしょうか.
nofaultをカーネルスタック上の割り込みされたプロセスのpcが格納されている場所に格納.
rtt命令でnofaultが指すトラップハンドラに飛びます.
もう一つよくわかっていないのが, この後のトラップハンドラからどうやってユーザープログラムに復帰するのかということ.
rttによって割り込まれたプロセスのPSWとpcが元に戻されているところまではわかるのですが...

nofaultにトラップハンドラが指定されていない場合: あまり細かく読んでいないのでざっくりと. jsr命令でr0を退避, _trapのアドレスを代わりに格納してcall1にジャンプ. callの中へジャンプ.

call

全然読めてないです.
最終的には割り込みハンドラへと飛んでいく感じ？

次回の予定

もう少しcallとtrapを詳しく.