今日も今日とてパタヘネ読書記録です。今回は雑多な話がメインです。具体的にはハミング誤り訂正符号、VM、ページング機構の話になります。
5.5
障害とは提供するサービスが仕様から外れていることを言う。信頼性とはサービスが連続でどれくらい稼働し続けられるかを意味する。信頼性を定量化するメトリクスとしては平均故障寿命MTTF、年間故障率AFRがある。障害からどれくらいの時間で復帰できるかを定量化する指標として平均修復時間MTTRがある。可用性はサービスが障害を起こしていない時間が何割か、すなわちMTTF/(MTTF+MTTR)で測定される。MTTFを改善するための指針としては、故障回避（フォールトアボイダンス）、故障許容（フォールトトレランス）、故障予測（フォールトフォアキャスティング）がある。
ビット反転が生じてもデータを保護する方法として、Hamming誤り訂正符号がある。Hamming誤り訂正符号はデータに冗長ビットを追加する。冗長ビットは元データからある規則で生成される。ビットが反転した場合、元データが入っているビット番号から再度冗長ビットを計算すると冗長ビットと不整合になるので、ビット反転が起きたことがわかり、再度整合するよう反転したビットを戻すことができる。ただし、誤りを検出したり訂正したりできるためには反転を許容するビット数と、用意する冗長ビットの個数に条件が必要となる（例えば全ビットが反転するなどしたら当然戻せない）。例えば、1ビットのパリティコードでは元データのビット列のうち1になっているものが奇数なら1、偶数なら0の冗長ビットを付加する。この場合2ビット反転したらパリティが元データと一致するので誤り検出不可能である。
1ビットのHamming誤り訂正符号はデータのうち、2のべき乗にある位置を冗長ビットとして用いる。例えば、1,2,4,8番目のビットなどである。それ以外の位置のビットは元データを入れる。2^n番目のビットは、ビット位置を2進表記したときn+1番目が1になっている箇所のビットから算出する。例えば、1=2^0番目のビットは2進表記で0001,0011,0101,0111,1001,1011,…番目のビットのうち、1になっている個数が奇数なら1、偶数なら0となる。
1ビットのHamming誤り訂正符号は、正常なビット列同士のHamming距離が2離れるため、1ビットの誤りまで訂正できる。2ビット使えばHamming距離が4離れるので、2ビットの誤りまで訂正できる。
5.6
VMの話。恐竜本で読んだので省略。
5.7
ページング機構は複数のプロセスの間で同じメモリを使うことと、メモリ容量の限界を超えて記憶域を確保したい時に使う。プロセスは連綿としたメモリ空間を扱っているように感じる。この仮想アドレス空間でメモリにアクセスしようとすると、プロセスごとに存在するページテーブルを用いて、実メモリ上のアドレスに変換され、実メモリにアクセスできる。仮想アドレスが指し示す先が必ずしも実メモリにロードされている必要はなく、ディスク上に存在することもありうる。アクセス時にページが実メモリ上にロードされていない状況はページフォルトと呼ばれ、OSがディスクから実メモリに内容を読み込む（ページイン）。実メモリに空きがなければ特定のページをディスクにページアウトする。
ページテーブルと主記憶はディスクに対するキャッシュとみなすこともできる。ディスクのアクセス速度の遅さからキャッシュの観点での設計は自ずと決まってくる。まず、ミスペナルティが非常に大きいのでミス率をできる限り減らしたい。そのため、セットアソシアティブ、もしくはフルアソシアティブ方式を取ることになる。また、アクセス時間を補えるよう、ページ（キャッシュの用語ならブロックサイズ）は大きく取る。また、ページフォルトにはソフトウェアで対応する。ディスクが遅いのでソフトウェアで対応しても応答速度に与える影響は小さいからである。それならハードウェアで対応するより柔軟につくれるソフトウェアを使うほうが良い。また、ディスクが遅すぎるのでライトスルーはありえず、ライトバック方式を取ることになる。これはダーティビットが立っているページがページアウトするときだけディスクに書き込まれるという挙動に対応している。
ページテーブル自体は主記憶上にあるので、工夫しなければ1回のメモリアクセスのたびにページテーブルを見に行くので計2回メモリアクセスが必要となる。より高速化するため、ページテーブルのキャッシュを行うアドレス変換バッファ（TLB）が用意されている。TLBにヒットした場合メモリアクセスは1回で済む。TLBミスが起きたら主記憶のページテーブルを見に行く。ページテーブル上でページがメモリ上に読み込まれていることがわかったら、そのエントリーでTLBを更新する。アクセスしたいページがメモリ上にない、すなわちページフォルトが起きたならディスクから読み込んだあと、TLBを更新する。TLBの上書き対象エントリの選定はLRUを使用するもの、ランダムに選択したりするものなどがある。TLBミスは非常に頻繁に発生するので、ソフトウェア的に処理することは不可能であり、ハードウェアで実現する必要がある。LRUはハードウェアで実現しにくいので、ランダムに選択するコンピュータが増えている。
5.8
どんなキャッシュでも設計するときは共通する4つの設計問題を解決する必要がある。まず、キャッシュの連想度やブロックの配置の仕方である。連想度が高いとミスが減るがエントリを探すコストが上がったり実装が複雑になったりする。次に、ブロックの探し方である。ダイレクトマップ方式ではキーから場所を特定できるが、セットアソシアティブ方式では連想度の数だけ検索が入る。フルアソシアティブ方式では全探索が必要となる。全探索が問題にならないほどミスペナルティが大きいならフルアソシアティブ、そうでないならダイレクトマップかセットアソシアティブを使うことになる。第三に、キャッシュミス発生時にどのブロックを犠牲にするかの選択方法である。ランダムに選ぶか、LRUで選ぶかの選択がありうる。LRUは実装が難しいので近似的な方法を使うことになる。最後に、書き込みはライトスルーにするか、ライトバックにするかの選択がある。
キャッシュのミス率に寄与する原因は3つあり、3Cモデルと言われる。1つ目は初期参照ミス(compulsory miss)であり、まだキャッシュに読み込まれていないブロックに最初にアクセスする時のミスである。次に、容量性ミスは、キャッシュサイズがプログラムが必要とする全てのブロックを保持できないことにより、一旦読み込んだブロックが次アクセスした時消えていることで起こるミスである。最後に、競合性ミスはダイレクトマップもしくはセットアソシアティブ方式で、同じブロックを巡って複数のブロックが競合している時に起こる。フルアソシアティブ方式ではどのブロックもキャッシュ上で全ての位置を取りうるので、このタイプのミスは起こらない。
コメント