0x19f (Shinya Kato) の日報

主にプログラミング関連の話をします

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

UNIX V6

勉強会の趣旨

UNIX V6ソースコードを読もうという会です.
この本に沿って読み進めてます.

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

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

月曜5限後にラーニングコモンズでひっそりやってるので興味がある方がいればぜひどうぞ.

これはその勉強会の内容のメモです. (自分が後から見返すよう程度なのであんまり参考にはならないと思います.)

今回の内容

10/30
第3部の割り込みから.
途中からメモを取り始めたので, 第1部, 第2部のメモはないです...
ざっとプロセスについて読んで, execあたりで心が俺て飛ばすことにした(forkあたりまでは読んだ感じ).

割り込み・トラップ

割り込み
  • 周辺デバイスからの非同期的な要求を処理するための仕組み.
トラップ
  • CPU内部で起こる出来事を非同期的に処理するための仕組み.
  • 0除算, バスタイムアウトなどの例外発生をシグナルとして処理する.
  • システムコールはトラップを用いて実現される.

割り込みとトラップの違いは, きっかけとなる要因が外部デバイスかCPUか.

優先度

割り込みには0から7までの優先度が設定される.
割り込み優先度の方がPSWのプロセッサ優先度より小さい時だけ割り込みは処理される.
トラップには優先度がない.
トラップは発生すると即座に処理される.

割り込み・トラップベクタ

カーネルプロセスが割り込み・トラップ処理を開始する際に設定されるPSW, pcの値が格納されているアドレス.
(このアドレスはユーザープロセスの仮想メモリアドレス？カーネルプロセスの仮想メモリアドレス？)
ベクタの値はPDP11によって決められているっぽい.
ベクタデータはカーネルプログラムの下位アドレス部に書かれている.

割り込み・トラップの発生

割り込み・トラップの発生
→PSW, pcをカーネルスタックに退避, ベクタが指すアドレスからPSW, pcを読み込む(ハードウェア処理).
→読み込んだpcから処理を再開(call, trap関数が実行される).

カーネルプログラムの下位アドレス部分を読むと, 0番地にジャンプ命令があって飛んだ先でstart関数を呼び出している.
その部分を除くとだいたいは割り込み・トラップベクタのデータになっている.

ベクタデータの中身は, トラップの場合は, trap関数のアドレスとPSWが格納されている.
割り込みの場合は, それぞれ関数が用意されていてそのアドレスとPSWが格納されている.
その関数の中でcall関数が呼び出される.
ここで使われているjsrが少しわかりづらい.
REF: PDP-11のjsrの動き：いや、まさにログ的な：So-netブログ

ややこしいのが, trap命令とtrap関数がどちらも同じtrapという名前なところ.
一応, このアセンブリではsys命令が擬似trap命令になっているらしく, trapと書いてあったらtrap関数だと思って良さそう(？).

これまたややこしいが, br4〜br7はPSWの値.
トラップの場合はPSWの下位3ビットにトラップの種類を表す値が格納される(br7+4など).
(下位3ビットと書いてあるのに, +9とかしている箇所があって謎.)

次回の内容

call, trap関数の中身を詳細に読む予定.
割り込みが発生した場合, トラップが発生した場合の処理を丁寧追う必要がありそう.
特に, 割り込みの方はjsr命令によってr0とpcの値がいろいろと変わるので気をつける必要がありそう.

会津大学競技プログラミング合宿2017に参加してきました

参加記 競プロ

いろんな人の参加記を見ていたら自分も書きたくなったので書きます.
9/18〜20で会津大学の競技プログラミング合宿に行ってきました.

3日間の日程があってそれぞれ立命館大学, 会津大学, 北海道大学が作問した問題をICPC同様のチーム戦で解くという感じでした.
ちなみに, チームはほぼその場で強さが偏りすぎない程度に適当に決めてました.
実は初めてのオンサイトコンテストだったのでACすると風船が上がる感じとかとても楽しかったです.
コンテスト自体はAOJ上で行われていて, オンラインで参加している方もたくさんいました.

Day 1

東京駅を9:00に出発, 12:00頃に会津若松駅に到着.
郡山まで東北新幹線使うとかなり近いですね.
そして駅からしばらく歩いて会津大学に到着.

f:id:mizu0x19f:20170926205813j:plain

1日目は立命館大学が作問した問題セットでした. ACPC2017Day1 (解説)

チームは会津大学の方二人と組ませていただきました.
自分はB問題を解いたのですが, バグらせまくって本当に申し訳ないという感じです...
B問題を通した時にはすでにA, C, Dが解かれていました.
残ったE, F, Gは結局解けませんでした, 残念.

合宿終わった後に全部問題ちゃんと見た感想です.

  • A: 丸付け (解答)
    • 2文字ずつ見ていけばO(N)で判定可能.
  • B: 全日本帰りたい協会 (解答)
    • 次の人を迎えに行くまでに1Fに戻っても間に合うならば, 1Fに行くのが常に最適.
    • ...なのですが, 結構チェックしないといけない箇所が多かったりして実装がしんどいです.
    • ちなみに, 僕は最初の人を迎えに行けるかどうかの判定を忘れて2WA出しました.
  • C: ツイート数 (解答)
    • DFSしながら葉からの最短距離を求めていけばOK.
  • D: 次元旅行 (解答)
    • i次元からi - 1次元にだけ辺を張ってダイクストラすればいいというのが面白かったです.
    • 普通に全部に辺を張ったらMLEしたので解説見ました.
  • E: 敵襲から守れ
    • まだACできてないです.
    • あんまり最大フローがよく理解できてないのですが, この期に理解してしまいたいので頑張って通したいと思います.
  • F: Steps
    • ランダムウォークではよくあるタイプの問題らしいのですが, あんまりちゃんと理解できてないです.
  • G: Cryptex
    • めちゃくちゃ頑張ると解けるらしいです(遠い目).

Day 2

二日目は会津大学が作問した問題セットでした. ACPC2017Day2
僕 + 立命館の方 + 社会人の方の3人チームでした.
自分はA, C, F, Lを解きました.
A問題は人生初のFA(オンサイトのみ)で結構嬉しかったです.
FAなので風船にかわいい動物がついてきました.
圧倒的にチームのみなさんが強くてオンサイト1位でした.

以下各問題の感想です(解けたもののみ).

  • A: Clock (解答)
    • 割って余り求めたらいけるやろ〜とか言って提出したら通りました.
    • 人生初オンサイトFAやったね！
  • B: Hating Crowd (解答)
    • ちょっと面倒ですが愚直にやると解けました.
  • C: Palindrome (解答)
    • N^2が間に合う制約なので, 回文にするときのペアを探してから辞書順に貪欲にとっていけばOKです.
    • ちょっと実装がややこしくてバグらせましたが...
  • D: Fissure Puzzle Easy (解答)
    • 白いマスの連結成分の数を数えて1引いて3で割ると答えが出るというちょっと面白い問題でした.
    • 領域を4分割していくのでも解けるみたいです.
  • E: Piano (解答)
    • 連続して増加, 減少している部分の最大を求めれば解けます.
  • F: nCm (解答)
    • 問題を見たらすでに考察がされていたので, その通りに実装したら通りました().
    • 結局2^kのところだけ見ればO(logN)で解けるようです.
  • I: Making Pairs (解答)
    • 木の上でマッチングをする問題.
    • DFSしながら, マッチしていないものと貪欲にマッチさせていけばOK.
  • L: RMQ 2 (解答)
    • クエリはQ個しかないので, 全部コピーする時は以前に変更があった箇所だけコピーすれば間に合います.
    • コンテスト時間中に通せてよかった...

コンテスト後はリクルートコミュニケーションズのアドテク部さんのおかげで無料で懇親会に参加することができました.
(その謎のお金は一体どこから出てきてるんでしょうねぇ......)

Day 3

三日目は北海道大学が作問した問題セットでした. ACPC2017Day3
僕 + 会津大学の方 + 立命館大学の方みたいなチームで臨みました.
B問題が鬼難しくて, Bとは何かについて哲学的な考察をしていました.

以下問題の感想です.

まとめ

初めてのオンサイトコンテストでしたがとっても楽しかったです.
また, 作問している方々を見て素直にすごいなという感想を持ちました.
うちの大学でも強い競プロerの人々がコンテスト開きたいと言っているので, その時は作問側もやってみたいなと思いました.

最後になりましたが, コンテスト運営してくださった方々, 作問をしてくださった方々, 当日チームを組んで下さった方々, 本当にありがとうございました.

(ちなみに, 実は会津合宿の帰りにもう一泊して「全部ACするまで帰れま10」という企画もやったのですが, その時のことはまた別記事で書きたいと思います.)

9/10 PyCon JP 2017に参加してきました

9/8, 9に行われたPyCon JP 2017に参加してきました.
pycon.jp

正直あまりPython書いたことないのですが, 今年は思い切って行ってみることにしました.
というのも, なんと参加枠に早稲田大学生という枠があって, しかも参加費無料だったんですね.
おまけに開催場所は普段まさしく授業を受けている理工のキャンパスの63号館.
これは参加しない手はないということで即connpassから申し込みました.
決して懇親会のタダ飯が目当てではないです.


PyCon JP 1日目

申し込んだものの, 1日目は大学の夏期集中講座と被ってしまったので, 夕方のLTからの参加です.
(昼間は隣の建物で授業受けてました.)

LTの中で印象に残っているのは, 「built-in関数への代入はやめよう」という趣旨の発表です.
Pythonそんなに書いたことのない自分はこの時は初めて知りました.
listってbuilt-in関数なのかよ！
間違いなく今までにlistという名前にリストを代入した覚えがあります.
知らずにbuilt-in関数の人権を侵害してきたんですねぇ, 申し訳ない...

その他では, ギャル語翻訳も結構インパクト強かったですね.
togetter.com

PyCon JP 2日目

2日目は丸一日参加しました.
いくつか印象に残ったセッションの感想を書いておきたいと思います.

Opening Keynote

speakerdeck.com

pandasとDaskのコミッタである堀越さんのセッション.
OSSコミッタがどんな仕事をしているのか, これからOSS活動を始めたい人が何をすべきなのかという内容でした.
最近Pythonで機械学習をした時にちょろっとpandasを使ったので, 聞いていて話の理解はしやすかったです.

セッションを聞きながら, OSSに貢献はしたい一方で, バグっぽいものに遭遇した時に自分のミスなのか本当のバグなのかの切り分けが難しいよなぁと.
巨大なソフトウェアともなると, ドキュメントだけでも読み切れないぐらいあるので.
そういう状況でissueを書くってのもなかなか勇気がいるなぁなんて考えてました.
あぁいうのってどれぐらいのノリで書くものなんですかね.

Pythonで実現する4コマ漫画の分析・評論 2017

slideship.com

4コマ漫画を各コマごとの画像に変換, セリフを抜き出し, 登場人物を特定するという試みでした.
正直に感想を言うと, ゆゆ式の話が気になって肝心の機械学習周りの話があまり理解できませんでした！

今でも当時のアニメ放送時間になるとエア実況が発生
2017年9月5日(火) 24:30放送(?)分で18クール214話

ゆゆ式の何があそこまで人を狂わせるのか気になったので, そのうちアニメ見てみたいと思います.

理論から学ぶPythonによるサーバーレス開発

slideship.com

サーバーレスって聞いたことはあってもどういうものか全く知りませんでした.
「名前から推測するにサーバーがないということなんだろうか？？？」とか思ってたぐらいです.
とりあえず, セッションを聞きながら一般的なWEBサービスとは相性そんなによくないのかな？って思ったぐらいしか理解できませんでした.

PyConJPで彼女つくってみた(LT)

slideship.com

支離滅裂な文章を返してくるところがマルコフ連鎖の面白いところですよね.
素敵な彼女さんができることを祈っています(遠い目).

まとめ

今までPythonそんなに書いてきませんでしたけど, 今回でいろいろと便利そうなものがあるのもわかったのでちょっと勉強していきたいと思います.

こんな素晴らしいイベントの参加権をいただけで本当に幸運でした.
スタッフのみなさん, 登壇者のみなさん, ありがとうございました.

IMG_4875

8/21 サマーウォーズを見てRSA暗号について調べた

普段テレビはほとんど見ないのだけれど, 先日は金曜ロードショーのサマーウォーズを見てました.
相変わらずいつ見てもいい作品だなぁとか夏希先輩かわいいなぁとか思いつつ, Twitterでわいわいしてました.

サマーウォーズが放送されると必ず話題に上がるのが健二が解いているあの暗号の話.
解いている様子の描写からRSA暗号じゃないかと言われています.
RSA暗号というと素因数分解というイメージが強いのですが, あまり暗号化と複合の部分がどういう原理でできているのかについては理解できてませんでした.
というわけで, サマーウォーズを見ながらいろいろと調べて考えてみたことをまとめてみたいと思います.

公開鍵暗号方式

そもそも, RSA暗号は公開鍵暗号方式の一種で, 2つの鍵を用いて暗号化と復号を行います.
簡単に言うと, 以下の2つの性質を持つような暗号です.

1. 片方の鍵で暗号化したら, もう片方の鍵でしか復号できない.
2. 片方の鍵からはもう片方の鍵は(簡単には)推測できない.

RSA暗号の基本的な仕組み

RSA暗号の基本的な仕組みについてはWikipediaなどを参照してもらうと良いと思うのですが, 簡単に書いておきます.
RSA暗号 - Wikipedia

p, q: 任意の素数, n = pq
e: (p - 1)(q - 1)と互いに素な任意の正の整数(公開鍵)
d: ed = 1 \pmod{(p - 1)(q - 1)}を満たす正の整数(秘密鍵)
m: 平文, C: 暗号文

暗号化: C = m^e \pmod{n}
復号: m = C^d \pmod{n}

というわけで, 実は累乗が計算できれば暗号化と復号は簡単にできます...
ってほんまか？となるわけですね.
これってつまり, m^{ed} = m \pmod{n}が成り立つってことに他ならないわけです.
さすがに自明ではないよなぁ......と.

復号がうまくいくのはフェルマーの小定理で説明できる

『高校数学の美しい物語』の説明がわかりやすかったです.

mathtrain.jp

少し補足をすると, 合同式には以下の性質があります.

a = b \pmod{p}かつ a = b \pmod{q}ならば a = b \pmod{lcm(p, q)}
( lcm(p, q)は pと qの最小公倍数を表す.)

つまり, m^{ed} = m \pmod{n}を示すためには, m^{ed} = m \pmod{p}を示せば十分ということになります.

興味深いのは, フェルマーの小定理を用いているところです.
これを利用してうまく暗号化ができるようになっているわけですね, 賢い.

素因数分解の困難性が安全を保証している

公開鍵暗号方式なので, 公開鍵 (e, n)から秘密鍵 (d, n)が推測されると暗号を突破されてしまいます.
秘密鍵を推測するためには ed = 1 \pmod{(p - 1)(q - 1)}を満たす dを計算する必要があります.
つまり, nを素因数分解して p, qを求め, (p - 1)(q - 1)を計算する必要があるわけです.

素因数分解は p, qが十分に大きな素数であれば現実的な時間で解くことはできません.
逆に言えば, 素因数分解ができてしまえば暗号を解読することができます.

「RSA暗号 = 素因数分解」というイメージ

サマーウォーズを見ながら, 流れてくるRSA暗号についてのツイートを眺めていたのですが, 「素因数分解する暗号」という説明が結構多かった気がします.
まぁ確かに「ふたつの素数 (p, q)から積 nを求めるのは簡単だけれど, nから (p, q)を計算するのは困難」と言われると, なんとなくわかったような気がしてしまうんですよね.
「素因数分解が効率よくできない」って直感的なのでそういう説明が出てくるのはわかるのですが, それって誤解の原因になりやすいんじゃないかなぁと.

人間って直感的な事柄の次に非直感的な事柄が出てくると, なんとなく理解した気になってしまうところがあると思います.
やはりそういう説明で納得してしまうことのないように気をつけたいなぁと.

まぁ, そんなことを考えていたよ, というお話でした.
(余談ですけど, はてなブログってTeXの数式を書くとMathJaxでレンダリングしてくれるんですね.)

8/11 AtCoder Regular Contest 080

この前うっかり寝過ごしてで損ねたARC080を解いた.

  • C: 4-adjacent - AtCoder Regular Contest 080 | AtCoder [解答]

    数列の要素を自由に並び替えて隣り合う要素の積が4の倍数になるようにできるか判定する問題. Aiが奇数, (4の倍数でない)偶数, 4の倍数で隣に置かなければならない数の条件が変わることに注目する. Aiが奇数なら, 隣には必ず4の倍数をおく必要がある. Aiが偶数なら, 隣には偶数をおく必要がある. Aiが4の倍数なら, 隣におく数はなんでも良い. ここから考えると, { 奇数, 4の倍数, 奇数, 4の倍数, ..., 4の倍数, 偶数, 偶数, ... }みたいな並びが作れるかを判定すれば良いことになる.

  • D: Grid Coloring - AtCoder Regular Contest 080 | AtCoder [解答]
    1, 1, 1, 2, 2, 3, 3, 3, 3, ...., N, N, Nと左上から順に要素数H * Wのマス目を埋めていき, 奇数番目の行だけreverseして表示すればOK.

  • E: Young Maids - AtCoder Regular Contest 080 | AtCoder [解答]
    辞書順で最小のものを構成するのは後ろから考えるとやりづらいので, 先頭から小さい数字を順に決めていくことを考える. 最初の状態からqの先頭2つの要素を決めるのには, 偶数番目の要素でもっとも小さい値とその要素以降で奇数番目の要素を取るのが最良. この二つの要素がpのi, j番目だとすると, pは[0, i), [i + 1, j), [j + 1, N)の3つの要素に分断される. qの次の2要素はこの3つの領域の偶数番目の値から最小のものを選ぶことになる. これを繰り返していけばO(N^2)でqを求めることができる.
    ここから計算量を落とすためには, 偶数番目/奇数番目の要素から最小を求めるのにセグメントツリー, 分割された領域からどれを選ぶかはpriority_queueを用いればよい. 具体的な手順としては,
    1. { [0, N), min_odd }をpriority_queueに入れる
    2. priority_queueから最小のものを取り出す
    3. 3つの領域に分割して, それぞれをpriority_queueに入れる
    4. priority_queueが空ならループ終了, そうでないなら2に戻る
    という感じ. 結構実装がしんどかった...

8/8 束の間の夏休み

8/3で無事に春学期の期末試験を全て終えて夏休みに突入した. しばらくは休養がてらアニメ見たりして過ごしてた. 昨日から大学の夏期集中講座でまた学校に来ている. なんだかオープンキャンパスで高校生がいっぱいいたり, 何かのイベントで小学生がいっぱいいたりして普段とはかなり違う雰囲気.

 

AtCoder

  • B: Colorful Creatures - AtCoder Grand Contest 011 | AtCoder [解答]
    スライムがN個あってそれぞれの大きさA[i]が与えられている. スライムは自分の大きさの2倍以下の大きさのスラムを吸収してその分大きくなることができる. こうしてスライムが吸収を繰り返して最後に残るスライムが1個になる時, 最後に残るスライムは何通り考えられるかという問題.
    とりあえず, 大きさの昇順にソートして考えてみる. 昇順に並んでいれば, i番目のスライムは1からi - 1番目までのスライムを吸収することができる. i番目のスライムがそれら全てを吸収すると大きさは, A[1]からA[i]までの和sumとなる. この時A[i + 1] <= sum * 2であればi番目のスライムがi + 1番目のスライムを吸収することができる. A[i + 1] > sum * 2であれば, どう足掻いてもi番目のスライムは全てのスライムを吸収することはできない. よって, A[i + 1] > sum * 2となる最大のiを探せば, 答えはN - iとなる. そのようなiが存在しない場合は答えはNとなる.
    実際の実装では降順にソートして, A[i] > sum(A, A + i - 1)となったところでループを抜けるって感じにしてます.

  • B: Mysterious Light - AtCoder Grand Contest 001 | AtCoder [解答]
    光が2個めの反射点に辿りついた直後, 残っている正三角形の領域は平行四辺形になっていることに注目すると考えやすい. このあと何度か光が反射すると再び平行四辺形ができる. この時, 何回光が反射すると次の平行四辺形になるかは二つの辺の長さから計算できる. また, 次の平行四辺形の辺の長さも同様に計算できる. 具体的には辺の長い方をa, 短い方をbとするとa = b, b = a % bになる. これを見てわかる通り, 辺の長さはlogで減っていく. イメージとしてはユークリッドの互除法みたいな感じ. これをbが0になるまで繰り返す.

7/30 ISUCONの練習始めました

今年こそISUCONに出たい

前々からISUCONにチャレンジしてみたいなぁーと思っていたのもあって, 今年こそはちゃんと練習しようと思っています. 夏休みに入って時間も取れるようになってきたので.

とりあえず, Vagrant使って過去問を触ってみる. ISUCON過去問とほぼ同じサーバー環境をVagrantで構築するためのVagrantファイルを公開してくださっている方がいるので, それを使う. 圧倒的感謝.

d.hatena.ne.jp

github.com

環境構築の手順

リポジトリをgit cloneして立ち上げたい問題のディレクトリに移動, vagrant upするとサーバーが起動する. ちなみに, 起動には結構時間がかかるので注意. あと, なぜかISUCON6のqualifyはうまく立ち上げられなかった. というわけで, isucon5-qualifyを立ち上げてとりあえずベンチを取ってみるところまでメモしておきます.

1. Virtualbox, Vagrantのインストール
brew cask install virtualbox
brew cask install vagrant

すでにインストールしている場合は, バージョンが古いとエラーが出ることがあるようなので再インストールしておくといいと思います.

brew cask reinstall virtualbox
brew cask reinstall vagrant
2. Vagrantfileが入っているリポジトリをcloneしてくる.
git clone https://github.com/matsuu/vagrant-isucon.git
3. 立ち上げたい問題のディレクトリに移動してvagrant up
cd vagrant-isucon/isucon5-qualifier/
vagrant up

これが結構時間かかります. 気長に待ちます. 諸々の準備が終わるとimageというサーバーとbenchというサーバーが起動しているはずです. きちんと把握してないですが, imageは問題を解く用, benchは負荷走行用かなと思っています. おそらく, 予選本番ではimageの方だけが参加者には与えられていて, benchサーバーにはベンチマーク取ってくださいってリクエストをするだけなのかと.

もしかしたらstandaloneは両方立ち上げないのかも. そうだとしたらそっちの方が早く起動できる(？).

4. imageサーバーにsshで接続する
vagrant ssh image
5. ユーザーを切り替える

ログインするとvagrantユーザーになっていると思うので, isuconというユーザーに切り替えます.

sudo su - isucon

そこでlsしてもらうといろいろファイルがあるのがわかると思います. 基本的にはアプリケーションなどの中身は/home/isucon以下に置かれてます.

6. とりあえずベンチを取ってみる

/home/isucon以下にbench.shというスクリプトがあるのでそれを実行します.

./bench.sh

しばらく待っているとベンチが終わって, 以下のような結果が標準出力に出てきます. これがスコアになるようです.

...
Isucon5Checker
done
success
114.1
{"success"=>206, "redirect"=>81, "failure"=>1, "error"=>0, "exception"=>0}
アプリケーションが 3000 ミリ秒以内に応答しませんでした

ここからやること

基本的にはNginxとMySQLのログを見ながらボトルネックになっている箇所を探していくことになるかなぁと考えています. MySLQはベンチ取った時のログをざっと見る限りでは結構N+1クエリがありそう. 他にもいくつか時間かかっているクエリもあったのでそのあたりを中心に見ていくことになりそう. あと, 実際にブラウザからアクセスもしてみるとどういうお題なのかわかりやすくていいかなぁと.

チームメンバーに競プロerがいるので, C++でゴリゴリ書き直すみたいな戦略も面白いかなぁって思っている. ちなみに, 昨年はC++で予選を突破したチームが1つだけいた模様. と思って調べてみたらまさかのこのチームで爆笑してしまった.

ISUCON6予選をC++で参加して予選通過した話 - いもす研 (imos laboratory)

さすがに自前でC++のWebサーバーを作るのは険しすぎるのでC++でCGIとか作ってみるのはどうかなぁなんて考えているところ. どれぐらい速度出るか全くわからないけれど.