【読書メモ】Googleのソフトウェアエンジニアリング11, 12章

ちょっとずつ GoogleSWE 本を読んでいるので要約しながら所感をメモる。何においても本を読んだだけで実践できる人って最強だと思うのよね。本を読んだだけでいい気になっている人とは天と地の差がある。天側の人を目指そう。

今回読むのは以下の書籍である。

www.oreilly.co.jp

ちなみに英語版だと以下からオンラインで無料で読める。

abseil.io

今回の範囲は以下の2つ。やっぱ Google を支えるテストの話って気になる。

11章 テスト概観

11.1 何故テストを書くのか

内容: テストコードを書いてテストを自動化しよう。テストは定期的に頻繁に実行しよう。テストの誤りは迅速に修正しよう。テスト文化の醸成は生産性を向上させる。

所感: 自分も普段からテストを書くが、テストの利点として挙げられている「ドキュメンテーションの改善」は特に自分も感じるところである。テストは仕様の一部という意識を持つとよさそう。

11.2 テストスイートを設計する

内容: テストには規模(size)と範囲(scope)という2軸がある。

内容: テストスイートの重要な性質は速度と決定性(determinism)である。テスト規模(size)はこの2つの観点による分類であり、小・中・大の3つのテストからなる。

  • 小テストは、単一のプロセス内で完結し I/O 操作等を実行しないようなもの。テストの実行が早く非決定的な結果を生まないのが特徴。
  • 中テストは、複数のプロセスを使うもの。ただし localhost 以外のネットワーク呼び出しを許さない。非決定的な結果を生む可能性があるがリモートマシンへのアクセスがないので実行時間は膨大にはならない。
  • 大テストは、リモートマシンへの呼び出しができるもの。非決定的だし実行に時間もかかる。

たまに失敗するテスト(flake, flaky test)が増加するとテストへの信頼が喪失するので1%以下にすべき。テストは挙動を実行するために必要な情報のみを含むべき。テスト自体はシンプルに明確に保つべき。
所感: ここはテストの規模(size)についての話。テストの速度と決定性に着目するってのは自分では考えたこともなかった。

内容: テスト範囲(scope)は、テストによってどれだけの量のコードが検証されるかという観点である。小範囲のテストはユニットテスト、中範囲はインテグレーションテスト、大範囲はシステムテスト。前から順番に 80%, 15%, 5% の比を目指そう。

f:id:t-keita:20220112023237p:plain:w300

所感: この分類はわりと馴染みがある内容だが、理想的なバランスが数値として示されているのが Google の経験が詰まっている感じがする。

内容: コードカバレッジはあくまで動かしたコードの範囲であり、テストによって検証されたコードの範囲ではないので注意すべき。また、これらのテストメトリクスを高めることがゴールになってしまうのはダメ。 結局は、ユーザが期待する動作を総合的に考慮しテストスイートを評価することが重要。
所感: カバレッジを高めることがゴールになるのはソフトウェア開発あるある。真の品質を高めることが重要ってのはその通りだな。

12章 ユニットテスト

12.1 保守性の重要さ

内容: 保守性のあるテストとは "just work" する、つまり "普通に動く" ようなものである。具体的には、テストが失敗するまではケアする必要はないし、一方でテストが失敗したときは本当にバグを示すようなものである。脆いテスト(brittle tests)は、本当はバグを生んでいない修正に対して失敗するようになるテストである。テストの失敗が何を意味するのか不明なテストは望ましくない。
所感: テストっぽいものを作るのではく、テストとしてちゃんと役割を果たすものを作ろうという内容。当たり前の話だがチームで共有できていると強い。ちなみに日本語版で "just work" は「とにかく動作する」と訳されていたが、「動けばなんでもいい」という意味に取れるので訳が微妙だと思った。

12.2 脆いテストを防ぐ

内容: 脆いテストにはメンテナンスのコストがかかる。理想的なテストとは、システムの要件が変わらない限り変化しないようなテストである。リファクタリングなのにテストを変更するとか、新機能を追加するだけなのに既存のテストを変更するみたいな場合は怪しい。
所感: 脆いテストを避けるにはどうすればよいのか?そのプラクティスは次に続く。

内容: 脆いテストを避けるため、内部の構造に依存せず public APIs に対してテストを書くべき。テストでは、結果へ至る道筋(how)より、結果そのもの(what)を検証することが重要である。これによってリファクタリング等によってテストが失敗することを避けられる。この原則は Use the front door first principle と呼ばれる。
所感: private なメソッドをどうテストすべきか?というのはしばしば話題になる気がする。Google による見解としては、private なメソッドの粒度ではテストすべきではない、ということなのだろう。リファクタリングされることを前提にテストケースを作ることを意識したい。

12.3 明確なテストを書く

内容: 明確なテストとは存在目的と失敗理由が明確なものである。明確なテストには完全性(completeness)と簡潔性(conciseness)が重要である。

  • 完全性とは、結果に到達する過程を理解するのに十分に情報をテストが提供することである。たとえば、テストの結果の理解に必要な入力値は明記すべき。
  • 簡潔性とは、テストが無関係な情報を含まないことである。たとえば、テストの結果の理解に不要な入力値はヘルパーメソッドで隠蔽すべき。

所感: 意図が分かりやすいテストを書くためのポイントについて。テスト以外のコードを書くときにも有用なプラクティスだと感じた。

内容: テストはメソッドごとではなく挙動(behavior)ごとに書くべき。behavior-driven tests と呼ばれる。挙動は given, when, then の3つから構成できるので、テスト中にこの3つを明記するとよい。テスト名は冗長でもよいのでテストのアクションと結果を明記すべき。
所感: behavior-driven tests は Behavior-driven development とかの概念から派生したものだと思われる。個人的にはメソッドごとにテストしてしまいがちなので、もっと behavior を整理してテストケースを考えてみよう。

12.4 テストとコード共有:DRYではなくDAMP

内容: テストは説明的かつ意味が分かりやすいものであるべき。DAMP(Descriptive And Meaningful Phrases)が目指すべき姿。そのため、コードの繰り返しを減らす目的でコードを共通化すべきではない。ただし、テストしたい挙動と関係のない情報をヘルパーメソッドで隠蔽する形で共通する場合などはアリ。
所感: ヘルパーメソッドの使い方は上手いと思った。複数のテストで同じインスタンスを使い回すのではなく、関心のある部分だけ上書きするような構造にすることで意図が明確になる。

全体的な所感

Google のテスト思想やユニットテストのプラクティスがよく分かった。それほど難しいことはしていないように感じるが、メンバー全員が説明的なテストを作るってのは簡単ではないと思う。あと、カバレッジの話は少しあったが、ユニットテストを設計するときの観点とかは本書に書かれてないだけでノウハウがあるのかな。品質保証においてテスト観点は重要だし、上手く網羅的に設計できる人とそうでない人がいる印象がある。

正規分布の覚え方

正規分布ガウス分布)の確率密度関数の式って覚えづらいですよね。今回は自分的に頭に入りやすい覚え方をまとめる。

覚えたい式を以下に書いておく。これを一度見ただけで覚えられる人は天才。

 f(x) = \frac{1}{\sqrt{2 \pi} \sigma}\mathrm{exp}(- \frac{(x-\mu)^2}{2 \sigma^2})

正規分布の式の覚え方

気合いで覚えること

まずは ガウス積分 の結果を覚える。

\int_{-\infty}^{\infty} \mathrm{exp}(- x^2) dx = \sqrt{\pi}

ここで被積分関数 \mathrm{exp}(- x^2)確率密度関数っぽくしたい。全区間積分が1になるように正規化した関数を考える。ガウス積分の結果を考慮しつつ以下の確率密度関数  f(x) を作る。

 f(x) = \frac{1}{\sqrt{\pi}} \mathrm{exp}(- x^2)

この関数の形はこんな感じである。

f:id:t-keita:20220108013850p:plain:w300

そして、これが 平均 0, 分散  \frac{1}{2}正規分布 になっていることを覚える。

覚えることは以上である。なんならこの平均と分散は計算して導いてもよい。

平均と分散を調整する

ここから平均  \mu、分散  \sigma^2正規分布の式を導きたい。

まずは分散を調整する。具体的には関数  f(x) の分散を  \frac{1}{2} から  \sigma^2 にしたい。

標準偏差でいうと  \frac{1}{\sqrt{2}} から  \sigma にしたいので、関数を  x 軸方向に  \sqrt{2} \sigma 倍に拡大すればよい。これは  x \frac{x}{\sqrt{2} \sigma} で置換すればよい。

 f(x) = \frac{1}{\sqrt{\pi}} \mathrm{exp}(- (\frac{x}{\sqrt{2} \sigma})^2)

おっと、面積も \sqrt{2} \sigma 倍になってしまったので定数も修正しよう。

 f(x) = \frac{1}{\sqrt{2\pi} \sigma} \mathrm{exp}(- (\frac{x}{\sqrt{2} \sigma})^2)

最後に、平均が  0 から  \mu になるように調整する。

この関数は平均が  0 なので、平均を  \mu にするには  x 軸方向に  \mu だけ平行移動すればよい。これは  x x - \mu で置換すればよい。

 f(x) = \frac{1}{\sqrt{2 \pi} \sigma} \mathrm{exp}(- (\frac{x - \mu}{\sqrt{2} \sigma})^2)

これが  \mathcal{N}(\mu, \sigma^2)正規分布だ。

おしまい。

Docker コンテナで snap コマンドを使う方法

困ったこと

Linux の新しめのパッケージマネージャとして Snap がある。 apt などのパッケージマネージャと違って、Snap によってインストールされるパッケージには必要な依存関係ごと含まているのが特徴である。いわば self-contained なパッケージマネージャである。

Snap のパッケージをインストールするとき snap install コマンドを叩くのだが、これを Docker コンテナ内で実行するとエラーが出ることが知られている。たとえば以下のページにその報告がある。

stackoverflow.com

この質問の回答にあるとおり、基本的には Docker コンテナ内で snap コマンドを叩くことはできない(厳密には snapd デーモンを起動できない)ようだ。困った。

解決方法

色々調べてみた結果、以下の GitHub リポジトリの資材を使うと snap install コマンドを叩ける Docker コンテナ(Ubuntu 18.04)を起動できた。そのやり方をここにメモる。ホストマシンは Ubuntu 20.04.3 LTS。

github.com

まずはこの Git リポジトリをクローンする。

$ git clone https://github.com/ogra1/snapd-docker.git
$ cd snapd-docker/

そしてスクリプトを実行する。

$ ./build.sh 

すると Docker コンテナが起動する。以下のコマンドで確認できる。

$ docker container ls
### ->
CONTAINER ID   IMAGE     COMMAND        CREATED          STATUS          PORTS     NAMES
1675068cffef   snapd     "/sbin/init"   57 seconds ago   Up 54 seconds             snappy

snappy という名前のコンテナが起動している。このコンテナは Ubuntu をベースイメージとしているので bash コマンドでコンテナに入ってみる。

$ docker exec -it snappy bash

コンテナ内のプロセスを確認してみる。

root@1675068cffef:/# ps aux
### ->
USER         PID %CPU %MEM    VSZ   RSS TTY      STAT START   TIME COMMAND
root           1  0.2  0.0 224772  8668 ?        Ss   15:01   0:00 /sbin/init
...
root         410  0.7  0.2 1550336 34212 ?       Ssl  15:02   0:00 /usr/lib/snapd/snapd
...

色々なプロセスが動いているが、snapd が起動していることが確認できる。

試しに snap install で pdftk という PDF の編集ツールのパッケージをインストールしてみる。

root@1675068cffef:/# snap install pdftk
pdftk 2.02-4 from Scott Moser (smoser) installed
root@1675068cffef:/# which pdftk
/snap/bin/pdftk

無事 pdftk を Docker コンテナ内にインストールできた。めでたし。

メモ

  • Docker コンテナのベースイメージを Ubuntu 以外にしたかったら build.sh 内で書き出している Dockerfile の内容を書き換えればよさそうだが、そんなに簡単にできるか分からない。
  • GitHub の README.md にあるとおり snapd-docker はセキュリティ面の制約を弱めている。セキュアな処理を実装するためには使わない方がよさそう。

トランザクション分離レベルとは何か

データベーストランザクションの ACID 特性とか分離レベルってややこしい。そんなある日、データベースの "状態" という概念があるのを知った。この概念を軸にすると、これまでややこしいと思っていたものが素直に理解できる気がしたので整理してみる。例によって、勉強しながらまとめているので記事の内容に誤りがある可能性が大いにある。

準備:データベースの状態

本記事ではデータベースの状態(database state)という概念を用いる。とはいっても簡単な話で、単にデータベース中に含まれるあらゆるデータをまとめて1つの状態を見なすだけである。たとえば、データの一部に更新があった場合、データベースは現在の状態から別の状態に遷移すると見なせる。広い範囲のデータが更新された場合でも、ごく一部のデータが更新された場合でも、データベースの状態としては今の状態から別の状態に遷移したと解釈するだけである。

"状態" という考え方はコンピュータサイエンスにおいて超重要な概念であり、状態の遷移を示す 状態遷移図コンピュータサイエンスのあらゆる分野で頻出する。ここではデータベースの状態に対して以下の状態遷移図を考えよう。

f:id:t-keita:20211123233531p:plain:w400

図中の s1 が現在の状態である。データベースの内容が具体的にどうなっているのかはどうでもよい。とにかく現在のデータベースの状態を s1 としている。ここで3種類の操作「C/D」「U」「R」によって状態が遷移する。これらはデータに対する操作として一般的な CRUD に対応する。

  • 「C/D」はデータに対する作成または削除を示しており、SQL の場合は INSERT/DELETE 文に対応する。レコードを作成したり削除する。この例では、状態 s1 に対してなんらかの作成または削除の操作が行われたとき状態 s2 に遷移する。
  • 「U」は既存のデータに対する更新であり、SQL の場合は UPDATE 文に対応する。レコードの作成や削除は行わず、既存レコードの内容を更新する。状態 s1 に対してなんらかの更新が行われたとき状態 s3 に遷移する。
  • 「R」はデータの読み取りであり SQL の場合は SELECT 文に対応する。読み取りなので状態の遷移は起こらない。

この状態遷移図のポイントは、具体的なデータの内容や具体的なデータの操作は考えていないという点である。これまでのトランザクションに関する概念の解説は「飛行機のチケットを予約するトランザクション」みたいな具体的なシチュエーションが想定されていて、その例を追うのだけでお腹いっぱいになってしまうという短所があった。今回の解説では具体的なデータや操作は考えないので、トランザクションをありのまま理解できるようにする狙いがある。上手くいくか知らんけど。

トランザクションとは?

トランザクションは、データベースに対するまとまった操作の列である。データベースの状態を遷移させてゆく一連の操作列と見なすこともできる。たとえば、さきほどの状態遷移図を用いると以下はトランザクションの例である。

f:id:t-keita:20211124001833p:plain:w600

この例ではデータベースの状態 s1 に対して [C/D, R, U, R, U, C/D] という操作を行う例である。読み取り操作である「R」では状態は遷移しないが、他の操作では状態が遷移している。

ACID 特性とは?

ACID 特性は、トランザクションが満たすことが望ましいとされている性質である。ACID は Atomicity, Consistency, Isolation, Durability の4つの頭文字を取ったものである。ただし「ACID 特性」という言葉の使われ方には曖昧性があり、ACID 特性を満たしていると謳ってるデータベースであってもその実装は異なる場合がある。以下、それぞれの具体的な意味について以下で述べるが、必ずしもこれが唯一の説明ではないと思ったほうがよい。なお、説明する順番は durability, consistency, atomicity, isolation とする。

durability(永続性)

durability は、トランザクションの結果が永続化されるという性質である。トランザクションの実行に成功したのに結果がどこにも残っていない、みたいな状況は悲しいので durability は満たすべきである。とはいっても、あらゆる障害に対して永続化を保証することはできないので、保証される基準はシステムに依存する。

consistency(一貫性)

consistency は、トランザクションの実行が完了したときにデータベースに課された "制約" が常に満たされているという性質である。この "制約" はデータベースが外部から課されるものである。たとえば「口座残高が負ではない」は制約の例である。この場合は、トランザクションの実行前後で「口座残高が負はない」を満たしていなければならない。この制約自体は、データベースが管理しているというより、データベースを利用するアプリケーション側でトランザクションを組み立てるときに考慮されるものである。

consistency はトランザクションの実行前後における性質であるため、トランザクションの実行途中においては必ずしも満たされている必要はない。この制約を満たしていない状態を「汚れた状態」と呼ぶことにする。状態遷移図としては以下のように点線で図示されるものとする。

f:id:t-keita:20211124004338p:plain:w600

状態 s4 が汚れた状態である。最終的には汚れていない状態 s5 に遷移するので、トランザクションとしては consistency を保証できている。

atomicity(原子性)

atomicity は、トランザクションの実行に成功した場合はすべての操作が実行され、失敗した場合は元の状態にロールバックされるという性質である。トランザクションの実行が中途半端なところ終わってしまうとデータベースの内容が壊れる可能性がある。トランザクションを実行するたびにデータベースが壊れてゆき、やがて無秩序なデータの蓄積になってしまう。このような状況を避けるため、実行に失敗したときは元の状態へロールバックすることは重要である。

さきほどの状態遷移図を再掲する。

f:id:t-keita:20211124001833p:plain:w600

atomicity が保証されている場合、このトランザクションの実行に成功した場合は状態 s5 に遷移し、失敗した場合は状態 s1 に戻る。たとえば、状態 s4 に対する操作に失敗したからといって状態 s4 のまま実行が終了することはない。状態 s1 まで巻き戻される。

isolation(分離性)

isolation は、トランザクションの実行が他のトランザクションの影響を受けないという性質である。一般に、同一のデータベースに対して同時に複数のトランザクションが実行されるため、排他制御のようなことをしないとデータが壊れてしまう可能性がある。isolation が保証されたもとでは、そのような排他制御が自動的に行われるため、ユーザは安心してトランザクションを実行できる。

SQL の分離レベル(isolation levels)とは

isolation を実現するためにはすべてのトランザクションを順番に1つずつ処理すればよい。しかし、これは実行時の性能が非効率になることが知られている。よく考えれてみれば、読み込み「R」しか持たないトランザクションをいくつ同時に実行してもデータベースが壊れることはない。つまり、トランザクションの性質によっては同時に実行しても問題ない場合がある。

このような背景から isolation のレベルを決めたものが SQL の分離レベルである。isolation のレベルを上げると、同時に実行できるトランザクション数は減るが、別のトランザクションの影響を受けることが少なくなる。逆にレベルを下げると、トランザクション数は増加するが、別のトランザクションの影響をより大きく受けることになる。分離レベルはデータベースの用途に応じて設計され、トランザクションを実行する前に指定される。

具体的には、分離レベルには以下の表の4段階が存在する。

Isolation levels Dirty reads Non-repeatable reads Phantoms
Serializable 起きない 起きない 起きない
Repeatable Read 起きない 起きない 起こりうる
Read Committed 起きない 起こりうる 起こりうる
Read Uncommitted 起こりうる 起こりうる 起こりうる

Dirty reads、Non-repeatable reads、Phantoms がトランザクションの同時実行時に起きうる異常(anomaly)であり、分離レベルを上げるにつれて起こるものが限られてゆく。ただし、データベースごとに分離レベルの実装が異なる可能性があるので、実際に指定するときはその仕様を確認すべきである。

Serializable レベル

Serializable は最も高い分離レベルであり、複数のトランザクションを1つずつ順番に実行したときと同じ挙動をすることを保証するものである。

例として以下の2つのトランザクション T1, T2 を同時に実行することを考える。トランザクション T1 は U1 という更新操作を行うものであり、T2 は [U2, U3] という2つの更新処理を行う。

f:id:t-keita:20211125001135p:plain:w600

現在のデータベースの状態を s1 とすると、Serializable のもとでの状態遷移は以下の2つのいずれかになる。

f:id:t-keita:20211125001307p:plain:w600

トランザクション T1, T2 は1つずつ実行されるので、[U2, U1, U3] のような操作列になることはない。

これに対して、以下の3つの異常のうちどれを許すかによって分離レベルが決まる。

Dirty reads

Dirty reads という異常は、複数のトランザクションを同時に実行したときに "汚れた状態" が読み込まれてしまうものである。

この異常が発生する例として、以下の2つのトランザクション T1, T2 を同時に実行することを考える。トランザクション T1 は現在の状態を読み込む「R」の操作だけを行う.。T2 は [U1, U2] という2つの更新処理を行うが、U1 の操作後は "汚れた状態" になっている。

f:id:t-keita:20211125002655p:plain:w600

Read Uncommitted のような弱い分離レベルでは、これらを同時実行したとき以下のような状態遷移が発生する可能性がある。

f:id:t-keita:20211125003134p:plain:w400

操作列は [U1, R, U2] であるが、R によって汚れた状態が読み込まれてしまう。たとえば、銀行のアプリで「口座残高: -20,000円」みたいな表示が起こりうるのである。実際はこれらの実行が完了するころには汚れていない状態 s3 に遷移するので、あくまでユーザに表示する値がおかしくなるに過ぎないのだが、ユーザからのクレームは止まないだろう。

Non-repeatable reads

Non-repeatable reads という異常は、同じ状態の既存のレコードに対して値を2度読むはずが異なる値を読み込んでしまうものである。

この異常が発生する例として、以下の2つのトランザクション T1, T2 を同時に実行することを考える。トランザクション T1 は [R, R] という操作列であり、同じ状態を2度読むものである。Serializable のもとではまったく同じ状態を2度読むことが保証される。トランザクション T2 は既存のレコードに対して更新操作をするものである。

f:id:t-keita:20211125005049p:plain:w500

Read Committed より弱い分離レベルでは、これらを同時実行したとき以下のような状態遷移が発生する可能性がある。

f:id:t-keita:20211125005120p:plain:w300

操作列は [R, U, R] であるが、トランザクション T1 から見ると2度の R で異なる値を読み込んでしまう可能性がある。dirty reads のように状態遷移の中に汚れた状態は存在しないものの、T1 としては同じ状態を2度読むことを期待していたために異常と言えるわけである。

たとえば、トランザクション T1 が口座Aと口座Bを持つユーザのアプリ画面に総資産額を表示するためのものであるとする。最初の R によって口座Aの残高を取得し、次の R によって口座Bの残高を取得する。そして、トランザクション T2 は口座Aから口座Bに送金するためのものであるとしよう。上記の異常な状態遷移では、送金前の口座Aと送金後の口座Bの残高を取得することになり、結果として総額が実際より多く表示されてしまう可能性がある。

Phantoms

Phantoms という異常は、同じ範囲のレコード集合を2度読むはずが、レコードが追加または削除されたため異なる範囲のレコード集合を読んでしまうものである。

この異常が発生する例として、以下の2つのトランザクション T1, T2 を同時に実行することを考える。

f:id:t-keita:20211125011401p:plain:w500

Repeatable Read より弱い分離レベルでは、これらを同時実行したとき以下のような状態遷移が発生する可能性がある。

f:id:t-keita:20211125011450p:plain:w300

操作列は [R, C/D, R] であり、Non-repeatable reads で異常が発生するケースとの違いは U か C/D の違いのみである。Non-repeatable reads は「既存のレコードに対して同じの値を2度読む」ときに発生する異常であるため、今回のようにレコードごと追加/削除された場合は該当しない。

Phantoms はかなり微妙な異常で、ユーザを想定したアプリみたいな文脈で分かりやすい例を出すのはなかなか難しそう。

おしまい。

参考

CPU使用率とは何か

いきなりまとめ

CPU使用率(CPU Usage, %CPU)は、CPU 時間の合計のうち、特定のタスクが占めた割合である。ただし合計時間には CPU が idle 状態の時間も含む。

背景

たとえば PC の動作が重いとき、Windows のタスクマネージャや Linux の top コマンドから CPU 使用率を見ることがある。あるプロセスの CPU 使用率が高いとき、そのプロセスを停止することで PC の動作が改善されたりする。最近 OS を自作していて、CPU 使用率に対する素朴な疑問を解消したくなったのでメモる。

まずは正しそうな定義を見てみる

top コマンドのマニュアルには CPU 使用率について以下のような記述がある。

  1. %CPU -- CPU Usage The task's share of the elapsed CPU time since the last screen update, expressed as a percentage of total CPU time.

最後のスクリーンの更新からの合計 CPU 時間に対するタスクの占有率である、とのこと。まぁこんなもんだろう。

素朴な疑問を解消してゆく

ここからは、自分がこの世に産まれてから CPU 使用率に対して抱いたことのある疑問と回答を列挙する。この世の何かしらの生命にとって参考になれば幸いである。

1つの CPU が複数のタスクに共有されるのはなぜ?

1つのパソコンに複数の CPU が搭載されているのは知っている。そして CPU というのはプログラムを読み込んで、その命令を実行してゆくものである。4つの CPU があるんだったら4つのタスクがこなせそうである。逆に言うと、あるタスクを実行し続けている限りは、そのタスクが CPU 使用率100%を占めるんだろう。しかし実際は CPU 使用率が100%になることなんてまずない。不思議だ。こんなふうに思ってるんだろう、そこのちびっ子よ。

まず、CPU が同時に1つのタスク(プロセス)しか実行できないのは理解として正しい。しかし、CPU は複数のタスクを瞬時に切り替えながら実行を行うことができる。こういうのは Concurrency と呼ばれている。以下の図には concurrency の例が3つ載っている。1つの CPU がピンク色と青色のタスクを瞬時に切り替えながら実行するため、人間にとっては複数のタスクが同時に実行されているように見える。

f:id:t-keita:20211118005722p:plain:w600

(※画像は このページ から引用した)

以上の話で、1つの CPU が複数のタスクに共有されるため、CPU 使用率が複数のタスクに割り振られることがイメージできただろう。疑問が解消された。めでたし。

ちなみに concurrency は「並行」と訳される。parallelism の「並列」という言葉と混同されがちなので英語のまま concurrency と parallelism で覚えよう。

CPU 使用率の合計が100%未満になるのはなぜ?

CPU 使用率は全体に対してそのタスクが占めた時間の割合であった。そのため、すべてのタスクの CPU 使用率を合計すると100%になると考えるのが妥当だろう。しかし実際は CPU 使用率が100%になることはほぼない。20%とか60%とかそんなもんだろう。

まず、CPU には idle という状態が存在する。これは CPU が与えられたすべてのタスクを終えて停止している状態である。消費電力を抑える狙いがある。たとえば、x86 アセンブリでは HLT 命令が実行されると CPU が idle 状態になる。次なるタスクが与えられると CPU が目を覚まして実行を再開する。

そして、CPU 使用率の計算には idle 状態の時間はどのタスクにも占有されていないと捉えられる。これがすべてのタスクの CPU 使用率を合計しても100%未満にしかならない原因である。

ちなみに、CPU Utilization is Wrong という有名な記事では、CPU 使用率は「idle 状態でない時間」を指すものであり、必ずしも「実際にタスクが実行されている時間」を指すものではないという指摘がある。以下の図がその例である。

f:id:t-keita:20211118011548p:plain

タスクが実行されている "Busy状態" と CPU が停止している "idle状態" に加えて "stalled状態" がある。stalled とはメモリの読み書きなどを待つ状態を指しており、その間は命令の実行が進まないらしい。

(一部修正 2022.01)

参考

【OS自作】littleosbook をやってみる #4

OS 自作シリーズの第四回。前回の記事は以下。

t-keita.hatenadiary.jp

littleosbook は以下。今回は6章から。

littleosbook.github.io

6 Interrupts and Input

この章では、ユーザからのキーボードの入力を受け付けるために interrupts(割り込み)をサポートする。割り込みは、ハードウェアの状態が変わったことを CPU に伝える場合だけでなく CPU 自身が発生させる場合もある。とにかく、CPU にとって想定していなかったことは割り込みとして表現されると思ったらよさそう。

6.1 Interrupts Handlers

割り込みは Interrupt Descriptor Table(IDT)によって管理される。IDT は割り込みの種類ごとにハンドラを管理している。割り込みハンドラの種類は3種類あるが、今回は trap handler を使う。おそらく、IDT に具体的な設定値を埋めて CPU に伝えるのがカーネルの役割。前回のメモリ管理の GDT と同じようなものっぽい。

6.2 Creating an Entry in the IDT

IDT に登録するエントリを定義してゆく。エントリは8バイトで構成され、フォーマットは以下の通りである。

f:id:t-keita:20211103233429p:plain

画像は Intel のマニュアル からの引用。

以下のように、IDT にハンドラの情報を登録する処理を実装した。(interrupt_handler_0 などの割り込みハンドラや load_idt 関数はこの後の手順で作るものである。)愚直に 0-255 番目のハンドラを登録したが、拾いたい割り込みだけ正しく設定出来ていればおそらく問題はなさそう。

struct idt_entry
{
    unsigned short offset_low;
    unsigned short segment;
    unsigned char zeros;
    unsigned char flags; // layout: P_DPL_0_D_110
    unsigned short offset_high;
} __attribute__((packed));

struct idt idt_info;
struct idt_entry idt_table[256];

void load_idt_table()
{
    unsigned int handler_address;

    handler_address = (unsigned int)interrupt_handler_0;
    idt_table[0].offset_low = handler_address & 0xFFFF;
    idt_table[0].offset_high = handler_address >> 16 & 0xFFFF;
    idt_table[0].segment = 0x0008;
    idt_table[0].zeros = 0x00;
    idt_table[0].flags = 0x8E; // = 0b10001110
    (省略)
    idt_info.address = (unsigned int)idt_table;
    idt_info.size = sizeof(struct idt_entry) * 256;
    load_idt(idt_info);   
}

6.3 Handling an Interrupt

IDT に割り込みハンドラを登録しておくと、その割り込みが発生したタイミングで CPU がハンドラを実行する。カーネルとしては、ハンドラが実行された事実によってのみ割り込みが発生したことを知ることができるとのこと。

CPU が割り込みハンドラを実行するとき、以下のような情報がスタックに push されるらしい。(あえてチュートリアルに載っている順序とは逆にしている。x86 ではスタックは番地が小さい方へ伸びる。この表記の方が、アドレスが昇順になるし、push された内容が上に積まれていくとイメージできるので個人的には分かりやすい。)

    [esp]      error code?
    [esp + 4]  eip
    [esp + 8]  cs
    [esp + 12] eflags

ハンドラの処理の最後に iret 命令を実行する。これを実行するときにはスタックが上記の状態である必要があるので、余計なものを push していたときは pop すべきらしい。この知識を使った実装は下でまとめて行う。

6.4 Creating a Generic Interrupt Handler

nasm のマクロを使ってハンドラとして登録するためのラベルとその処理を作ってゆく。まずはエラーコードが存在しない場合のために以下のようなマクロを定義する。チュートリアルでは1行目の 1%1 になっていたが、ここでは引数の個数を書くのが構文上正しいので、以下のように書くのが正しい。

    %macro no_error_code_interrupt_handler 1
    global interrupt_handler_%1
    interrupt_handler_%1:
        push    dword 0                     ; push 0 as error code
        push    dword %1                    ; push the interrupt number
        jmp     common_interrupt_handler    ; jump to the common handler
    %endmacro

ここでエラーコードとして 0 と interrupt number をスタックに push している。この挙動の意図を説明すると、6.3 章の通り、ハンドラが実行されるタイミングではスタックにエラー情報が積まれている。今回はエラーコードが存在しないケースなので、初期状態ではスタックが以下のようになっている。

    [esp]      eip
    [esp + 4]  cs
    [esp + 8]  eflags

これに対して、上で述べた2つの値を push するとスタックは以下の状態となる。

    [esp]       interrupt number
    [esp + 4]   0 (error code)
    [esp + 8]   eip
    [esp + 12]  cs
    [esp + 16]  eflags

一方で、エラーコードが存在する場合は以下のようなマクロを定義する。

    %macro error_code_interrupt_handler 1
    global interrupt_handler_%1
    interrupt_handler_%1:
        push    dword %1                    ; push the interrupt number
        jmp     common_interrupt_handler    ; jump to the common handler
    %endmacro

今回はハンドラが呼び出されるタイミングでエラーコードがすでに存在している。具体的には、スタックは以下のようになっている。

    [esp]       error code
    [esp + 4]   eip
    [esp + 8]   cs
    [esp + 12]  eflags

これに対して interrupt number を push するのでスタックは以下のようになる。

    [esp]       interrupt number
    [esp + 4]   error code
    [esp + 8]   eip
    [esp + 12]  cs
    [esp + 16]  eflags

ここで重要なポイントは、エラーコードが存在する場合も存在しない場合も、スタックの初期状態から esp レジスタの値が8バイト分だけ小さくなっているということである。これが、後で esp の値を元に戻すために esp の値を8だけ足す理由である。

次に C 言語で定義される interrupt_handler 関数を呼び出す部分を実装する。以下のように実装した。

   common_interrupt_handler:
        ; save the registers
        push    ebp
        push    edi
        push    esi
        push    edx
        push    ecx
        push    ebx
        push    eax
        ; call the C function
        call    interrupt_handler
        ; restore the registers
        pop   eax
        pop   ebx
        pop   ecx
        pop   edx
        pop   esi
        pop   edi
        pop   ebp
        ; restore the esp
        add   esp, 8
        ; return to the code that got interrupted
        iret

構造体は以下の通り。

struct cpu_state
{
    unsigned int eax;
    unsigned int ebx;
    unsigned int ecx;
    unsigned int edx;
    unsigned int esi;
    unsigned int edi;
    unsigned int ebp;
 } __attribute__((packed));

struct stack_state
{
    unsigned int error_code;
    unsigned int eip;
    unsigned int cs;
    unsigned int eflags;
} __attribute__((packed));

6.5 Loading the IDT

ここはチュートリアルの通りに load_idt を実装した。C 言語からアクセスするためのラッパーも作った。

6.6 Programmable Interrupt Controller (PIC)

PIC は、ハードウェアからのシグナルを割り込みにマッピングする集積回路である。PIC のデフォルトの設定では、キーボードからの入力シグナルを interrupt number が1である割り込みにマッピングする。しかしこの割り込みは CPU が発生させる割り込みと重複しているので他の番地の割り込みにマッピングし直したい。

もう少し PIC について理解を深めるために以下の osdev のページを見てみた。

wiki.osdev.org

PIC はハードウェアからの信号を interrupt requests(IRQ)という形で受信し、それを割り込みとして CPU に送信する。ハンドラによって処理が完了したことは PIC に伝える必要がある。そうしない限りは PIC は次の割り込みリクエストを送ってこないとのこと。

以下、実装したものを抜粋して紹介する。

まず、ハンドラの処理が完了したことを伝える pic_acknowledge 関数はチュートリアルの通りに実装した。interrupt number をリマップするための PIC の設定方法は SigOPS website [35] を参照とのことだったがこのリンクが切れている。ツラい。そこでこのチュートリアルをやったと思われる人の Github リポジトリを覗いてみた。

だいたいこの通りに設定した。以下のような感じ。

void init_idt()
{
    outb(PIC_1_COMMAND, PIC_ICW1_INIT + PIC_ICW1_ICW4); // starts the initialization sequence (in cascade mode)
    outb(PIC_2_COMMAND, PIC_ICW1_INIT + PIC_ICW1_ICW4);
    outb(PIC_1_DATA, PIC1_START_INTERRUPT); // ICW2: Master PIC vector offset
    outb(PIC_2_DATA, PIC2_START_INTERRUPT); // ICW2: Slave PIC vector offset
    outb(PIC_1_DATA, 4);                    // ICW3: tell Master PIC that there is a slave PIC at IRQ2 (0000 0100)
    outb(PIC_2_DATA, 2);                    // ICW3: tell Slave PIC its cascade identity (0000 0010)
    outb(PIC_1_DATA, 0x01);                 // ICW4: 8086/88 (MCS-80/85) mode
    outb(PIC_2_DATA, 0x01);                 // ICW4: 8086/88 (MCS-80/85) mode
    // Setup Interrupt Mask Register (IMR)
    outb(PIC_1_DATA, 0xFD); // 1111 1101 - Enable IRQ 1 only (keyboard).
    outb(PIC_2_DATA, 0xFF);

    asm("sti"); // Enable interrupts.
}

詳しいところまでは調べていないが、シリアルポートに設定値を送って PIC が発生させる割り込みの interrupt number をずらしている。最後の asm("sti");アセンブリ命令であり、これを呼び出さないと割り込みが有効化されないらしい。

6.7 Reading Input from the Keyboard

キーボードからの信号を読み取るには、チュートリアルにある通りにシリアルポートから char を読み取ればよい。ただし、この信号は scan code であり、これを ascii にマッピングする必要がある。ちゃんと頑張るようなところでもないと思ったので、適当に以下のアンサーにあるコードを移植してみた。

最後に、割り込みハンドラは以下のように実装してみた。

void interrupt_handler(struct cpu_state cpu, unsigned int interrupt, struct stack_state stack)
{
    // unused parameters
    cpu = cpu;
    stack = stack;

    if (interrupt == 0x21)
    {
        // scan code from the keyboard
        char scancode = inb(KBD_DATA_PORT);
        char input_char = kbd_US[(unsigned int)scancode];
        if (input_char != 0)
        {
            write_len(&input_char, 1);
        }
        pic_acknowledge(interrupt);
    }
}

キーボードから送られる信号が PIC によって 0x21 番の割り込みにマッピングされるので、0x21 のときに画面に文字を表示するようにしている。なお、文字に対応しないキーの信号はここでは無視している。たとえば Ctrl キーを押しても画面上は何も変化が起こらない。

以上を実装したものを Bochs で起動して動作確認してみた。このとき仮想キーボードの設定などは必要なかった。

f:id:t-keita:20211111010932p:plain:w600

緑色の文字の hello world はキーボードから入力したものである。同じようにしてコンソールっぽいものは作れそうな気がする。めでたし。

所感

割り込み処理はコールバックとして CPU に登録する仕組みになっている。また PIC がハードウェアと CPU をつなぐ役割を果たしている。今回はこんなイメージが具体的に湧くようになったのが成果。今この瞬間ブログを書いているときも、CPU は PIC を経由して割り込みを認識し、キーボードからの信号を文字に変換する処理を行っていると思うと感慨深い。

今回は PIC の正しい設定方法を探すのに苦労した。結果的には同じチュートリアルをやったっぽい人のリポジトリを覗くという元も子もない感じになったが、調べるのに時間使いすぎるのもアレなのでこんな感じでよしとしよう。

【OS自作】littleosbook をやってみる #3

OS 自作シリーズの第三回。前回の記事は以下。

t-keita.hatenadiary.jp

不備が修正されたバージョンの littleosbook は以下。今回は5章から。

ordoflammae.github.io

5 Segmentation

セグメントはメモリ上の区間である。セグメンテーションとはセグメントを経由してメモリへアクセスする方式である。セグメントを介したアクセスは6バイトの論理アドレスを用いて行われる。上位2バイトがどのセグメントであるかの指定(segment selector)で、下位4バイトはセグメント内のオフセット(offset)であるとのこと。なんとなく IP アドレスのホスト部とネットワーク部みたいなものをイメージした。

6バイトの論理アドレスから、アクセスするアドレス(liner address)への変換は次の流れである。上位 2バイトの segment selector の値から segment descriptor を用いてセグメントを特定し base address を得る。そして、下位4バイトのオフセットと base address を足し合わせると liner address が求まる。仕組みは簡単。

5.1 Accessing Memory

プロセッサは6つのセグメントレジスタ cs, ss, ds, es, gs, fs を持っている。たとえば、cs レジスタは code segment を指す segment selector であり、プログラムの命令をフェッチするときに利用される。また ss レジスタは stack segment、ds レジスタは data segment を指す。要するにプログラムの実行状態のうちセグメンテーションに関わるものはレジスタとして保持されているということだろう。

x86アセンブリから eax レジスタを使う例が書かれている。[eax] は明示的に書くと [ds:eax] と書けるらしい。この場合は、ds がセグメントを表す segment selector になっていて eax はオフセットである理解したらいいのかな。実行するプロセスが異なれば ds に対応するベースアドレスも異なっているため、[ds:eax] でアクセスされるアドレスも異なるようになっているみたいなイメージをした。

5.2 The Global Descriptor Table (GDT)

2バイトの segment selector からベースアドレスを返す descriptor について。特に GDT は以下の画像のフィールドをもつ8バイトのエントリの配列である。ちなみに各要素は segment descriptor と呼ばれている。

f:id:t-keita:20211023232900p:plain:w700

※ 画像は Intel のマニュアル からの引用

フィールドの中にはセグメントのタイプを表すものがある。Descriptor type が 1 であるときはそのセグメントが code segment または data segment である。code/data segment や、もう少し細かな権限の設定は TYPE フィールドで設定される。code segment のときはそのセグメントの内容を実行できるが書き込むことはできない。一方で data segment はそのセグメントに書き込みができる。

他の重要フィールドとして Descriptor Privilege Level(DPL)がある。PL0 が特権モードで、PL3 がもっと弱い権限を与えるモード。この privilege level はおそらく CPU modes に関係する話。メモリにロードされたプログラムが特権モードで実行してよいのかどうかを descriptor table が管理しているのだろう。

en.wikipedia.org

チュートリアルには At least two segment descriptors (plus the null descriptor) are needed みたいに書いている。最初読んだときこの文の意味が分からなかったが、これはカーネルを実行するために2つの descriptors が必要であるという話をしているのだろう。カーネルのための code segment と data segment をそれぞれ descriptor table に追加する必要がある。もちろんカーネルなので PL0 の特権が必要である。ここの実装は下でまとめてやる。

5.3 Loading the GDT

ここからは GDT の管理を自作カーネルの一部として実装する。今回のチュートリアルでは、カーネルがすべてのアドレス範囲を特権モードで扱えるようにすることが目的である。実装のおおまかな流れを先に説明する。GDT にカーネルのための2つのエントリ(code segment とdata segment)を追加したうえで、GDT の場所をプロセッサに伝える。その後、セグメントレジスタの値を設定する。

まずは、lgdt 命令を実行するアセンブリコードと C 言語のプログラムをつなぐためのインターフェースの定義を行う。以下のようなコードを gdb.h というファイルに定義した。チュートリアルでは sizeaddress の位置が逆になっているが以下の方が正しいので注意。

struct gdt
{
    unsigned short size;
    unsigned int address;
} __attribute__((packed));

void gdtb(struct gdt gdt);

nasm の lgdt 命令の引数には上記の構造体 gdt そのもの(厳密には構造体をバイナリ表現にしたもの)が必要であるため、このように構造体を引数としている。最初、チュートリアルにある the address to such a struct という表現を読んだとき、lgdt 命令が構造体へのポインタのアドレスを引数に取るものだと理解してしまった。正しくは構造体そのもののアドレスである。(C 言語の関数の引数に与えると esp + 4 がまさにこのアドレスに相当する)。この勘違いで時間を溶かした。

そして lgdt 命令を実行し、セグメントレジスタチュートリアルの通りに設定する。以下のようなアセンブリを書いて gdt.s という名前のファイルとした。

    global gdtb

    ; gdtb - loading the Global Descriptor Table
    ; stack: [esp + 4] gdt struct
    ;        [esp    ] return address
    gdtb:
        lgdt [esp + 4]
        mov ax, 0x10
        mov ds, ax
        mov ss, ax
        mov es, ax
        mov fs, ax
        mov gs, ax
        ; code here uses the previous cs
        jmp 0x08:flush_cs   ; specify cs when jumping to flush_cs

    flush_cs:s
        ; now we've changed cs to 0x08        
        ret

最後に、C 言語のプログラムから GDT のエントリの設定をする。エントリの設定内容はチュートリアルや上で説明した segment descriptor の仕様に従うようにする。

#include "gdt.h"

struct gdt_entry
{
    unsigned short limit_low;
    unsigned short base_low;
    unsigned char base_middle;
    unsigned char access_byte;
    unsigned char limit_and_flags;
    unsigned char base_high;
} __attribute__((packed));

struct gdt table;
struct gdt_entry entries[3];

void load_gdt_table()
{
    //null descriptor
    entries[0].limit_low = 0x0000;
    entries[0].limit_and_flags = 0x00;
    entries[0].base_low = 0x0000;
    entries[0].base_middle = 0x00;
    entries[0].base_high = 0x00;
    entries[0].access_byte = 0x00;

    // kernel code segment
    // 0x00CF9A00 = 0000 0000 1100 1111 1001 1010 0000 0000
    // 0x0000FFFF = 0000 0000 0000 0000 1111 1111 1111 1111
    entries[1].limit_low = 0xFFFF;
    entries[1].limit_and_flags = 0xCF;
    entries[1].base_low = 0x0000;
    entries[1].base_middle = 0x00;
    entries[1].base_high = 0x00;
    entries[1].access_byte = 0x9A;

    // kernel data segment
    // 0x00CF9200 = 0000 0000 1100 1111 1001 0010 0000 0000
    // 0x0000FFFF = 0000 0000 0000 0000 1111 1111 1111 1111
    entries[2].limit_low = 0xFFFF;
    entries[2].limit_and_flags = 0xCF;
    entries[2].base_low = 0x0000;
    entries[2].base_middle = 0x00;
    entries[2].base_high = 0x00;
    entries[2].access_byte = 0x92;

    // load table
    table.address = (unsigned int)entries;
    table.size = sizeof(struct gdt_entry) * 3;

    gdtb(table);
}

GDT の設定が上手くできていることの動作確認をしてみた。まずはブレークポイントを設定するために lgdt 命令の場所を特定する。

$ objdump -M intel -S kernel.elf  | grep lgdt 
  100640:   0f 01 54 24 04          lgdtd  [esp+0x4]

100640 番地に lgdt 命令があることが分かったので、ここに bochsブレークポイントを置いて実行してみた。

<bochs:1> lb 0x100640
<bochs:2> c
(0) Breakpoint 1, 0x0000000000100640 in ?? ()
Next at t=1311390526
(0) [0x000000100640] 0008:0000000000100640 (unk. ctxt): lgdt ss:[esp+4]           ; 0f01542404

lgdt 命令を実行する直前の GDT の内容を info gdt コマンドで確認する。何かよく分からない値がすでに設定されている。

<bochs:3> info gdt
Global Descriptor Table (base=0x0000000000008f5c, limit=39):
GDT[0x0000]=??? descriptor hi=0x00000000, lo=0x0000fff0
GDT[0x0008]=Code segment, base=0x00000000, limit=0xffffffff, Execute/Read, Non-Conforming, Accessed, 32-bit
GDT[0x0010]=Data segment, base=0x00000000, limit=0xffffffff, Read/Write, Accessed
GDT[0x0018]=Code segment, base=0x00000000, limit=0x0000ffff, Execute/Read, Conforming, Accessed, 16-bit
GDT[0x0020]=Data segment, base=0x00000000, limit=0x0000ffff, Read/Write, Accessed
You can list individual entries with 'info gdt [NUM]' or groups with 'info gdt [NUM] [NUM]'

そして lgdt 命令を実行してみる。1命令だけ実行するには s コマンドを使う。

<bochs:4> s
Next at t=1311390527
(0) [0x000000100645] 0008:0000000000100645 (unk. ctxt): mov ax, 0x0010            ; 66b81000

lgdt 命令の実行後の GDT の中身を見てみる。意図通りに設定できていることが分かった。

<bochs:5> info gdt
Global Descriptor Table (base=0x0000000000103008, limit=24):
GDT[0x0000]=??? descriptor hi=0x00000000, lo=0x00000000
GDT[0x0008]=Code segment, base=0x00000000, limit=0xffffffff, Execute/Read, Non-Conforming, 32-bit
GDT[0x0010]=Data segment, base=0x00000000, limit=0xffffffff, Read/Write

所感

これでセグメンテーションの章は終わり。カーネルの機能なのかプロセッサの機能なのかややこしいが、今回の場合はメモリ空間をセグメントに分割し、セグメントごとに管理する機能をプロセッサが提供していることを意識したい。カーネルは GDT という形で具体的な設定値を与えているにすぎない。今回は lgdt 命令の仕様にハマったが、そのおかげで bochs の実行時にブレークポイントを置いたり、シリアルポートを経由したログ機能を活用したり、デバッグのコツが少し分かった気がする。