class: title, smokescreen, shelf, no-footer # 仮想記憶<br>(Virtual Memory)  <div class=footnote> <small> </small> </div> --- class: col-2,compact # はじめに <div class=footnote> <small> (脚注1) 基本情報の出題範囲には、ページング以外にセグメンテーションやオーバレイなどの手法も含まれます <br> (脚注2) 仮想記憶は 「開発者の時間はコンピュータより貴重」という思想を実現するものの一つと考えられます <br> (脚注3) <B>ビジネス</B>では次のように考えます 「<b>(納期によるけど)開発しなくてすむなら、それは大勝利</B>」 プログラマが頑張って10%速くチューニングしても、 一年以内に出荷される次期Intel CPUが10%くらい速くなるので、 ハードウエアアップグレードのほうが確実です(ソフトのバグも増えない)。 なにしろ人件費は高いですからね！ </small> </div> - メモリ(main memory)つまり主記憶装置(ハードウエア)と、 仮想記憶(virtual memory)システムについて取り上げます - タイムシェアリングシステムのような複雑なOSでは**仮想記憶**は必須です (逆に組み込みなら不要なこともあります) <wbr> - 1980年代以降のOSで主流の**ページング型仮想記憶システム**だけを解説します - 仮想記憶システムのおかげで、 システムの**物理的な詳細を気にせず**、 **一続きの大きなメモリを扱っているかのようなプログラミングが可能**になります --- class: img-right,compact # 今回のハイライト: アドレス変換の様子 <div class=footnote> <small> (脚注) 今回の白眉がコレ。あとで、また同じ図が出てきます。今回は、これ(ページング型仮想記憶)の解説です </small> </div>  <small> - 右図の**箱(1〜9の数字)はメモリの概念図**です。 バイト単位ではなく**ページという4K/8Kバイトの単位**で考えています。 ページについては後述 - プロセスAもBも仮想ページ1〜5(上側)を使っていますが、物理ページ(下側)は異なります。 各プロセスは同じ(仮想)メモリ空間(1〜5)を使っていると**錯覚**していますが、 実際に読み書きする物理メモリの場所は異なります - **物理的な詳細を気にせずプログラミングできるのは、この仕組みをOSが提供しているから**です - Unixでは「メモリをください」(mallocほげほげ...)と言うだけでok - これがないOS(たとえばMS-DOS)では、 ハードを意識しないとプログラムが書けません </small> --- class: title, smokescreen, shelf, no-footer # <small>記憶装置(ハードウエア)の多段構造とキャッシュ</small> <div class=footnote> <small> </small> </div> --- class: img-right,compact # 記憶装置(ハードウエア)の多段構造  - プログラムやデータは、**安価で大容量ですが低速な補助記憶装置(HDD,SSD)**に格納しています。 補助記憶装置は通電していなくてもデータが消えない媒体です - 使うときに始めて補助記憶装置から**主記憶装置**(メインメモリ)に読み込みます - CPUはメインメモリにあるデータを読みながら処理を進めますが、 メモリもCPUよりほぼ1桁低速なため、 一度読んだデータはCPU内の**キャッシュに格納し(遅い)メモリアクセスを減らそう**とします - キャッシュは**SRAM**、メインメモリは**DRAM**というLSIです。 <small> SRAMは高速・高価・低容量、 DRAMはSRAMにくらべ低速・安価・大容量。 使い分けが重要 </small> --- class: img-right,compact # キャッシュの重要性 <div class=footnote> <small> (脚注) コンピュータネットワークでもキャッシュは重要です。 OSの速度にくらべてネットワークが遅すぎるため、 CDNなどのキャッシュサービスは通信の高速化に役立ちます </small> </div>  <small> - (初回にHDD,SSDから読み出す時は異なりますが)2回め以降、 読み書きは次のような多段構造 ``` CPU <- レジスタ <- CPU cache <- memory <- HDD,SSD CPU -> レジスタ -> CPU cache -> memory -> HDD,SSD ``` - 左側へいくほど高速・低容量 - CPU cacheも1次、2次、3次などと多段 </small> - **より高速なキャッシュから必要なデータを読みこめれば、 それだけ処理速度が上がります**(**キャッシュヒット**) - **デバイスごとの速度差が大きいため、キャッシュはコンピュータにとって重要** --- class: img-right,compact # スワッピング、スラッシング <div class=footnote> <small> (脚注1) 本稿では4KBなどの固定長でswapする話をしますが、 16bit Unixではプロセス単位でswapするメモリ管理でした(swap-based system)。 どちらもswapという用語で紛らわしい (脚注2) HDDの処理単位(512B)がメモリの処理単位(4KB)と異なる場合もありえますが、 そういう差異はデバイス担当ソフトウエアなどで隠蔽します </small> </div>  - メモリとHDD,SSD間の読み書きの単位は4KBなどの**固定長**、 この単位が**ページ** - データをストレージからメモリへ読みこみ、 (CPUで処理、メモリ上のデータを更新後)、 最終的に更新したデータをストレージへ書き戻すことも多いです。 このデータ交換が**スワッピング**です - あまりにも**スワッピング**が多いと、 ストレージへの(遅い)入出力に引きずられてOS全体のパフォーマンスが低下します。 この状態が**スラッシング**で、 これを避ける設計や運用が重要です --- class: title, smokescreen, shelf, no-footer # 仮想記憶(Virtual Memory) <div class=footnote> <small> </small> </div> --- class: img-right,compact # 今回のハイライト: アドレス変換の様子(再掲) <div class=footnote> <small> (脚注) 今回の白眉がコレ。あとで、また同じ図が出てきます。今回は、これ(ページング型仮想記憶)の解説です </small> </div>  <small> - 右図の**箱(1〜9の数字)はメモリの概念図**です。 バイト単位ではなく**ページという4K/8Kバイトの単位**で考えています。 ページについては後述 - プロセスAもBも仮想ページ1〜5(上側)を使っていますが、物理ページ(下側)は異なります。 各プロセスは同じ(仮想)メモリ空間(1〜5)を使っていると**錯覚**していますが、 実際に読み書きする物理メモリの場所は異なります - **物理的な詳細を気にせずプログラミングできるのは、この仕組みをOSが提供しているから**です - Unixでは「メモリをください」(mallocほげほげ...)と言うだけでok - これがないOS(たとえばMS-DOS)では、 ハードを意識しないとプログラムが書けません </small> --- class: img-right,compact # 仮想記憶(Virtual Memory)とは? <div class=footnote> <small> (脚注1) 仮想アドレス = virtual address (脚注2) MMU = Memory Management Unit </small> </div>  <small> - プロセスに見せているのは**仮想アドレス** - 仮想記憶システムを使うことで (a)**物理メモリの詳細を気にせず** (b)**実際の物理メモリより大きなメモリ空間**を扱えます - (a)によるメリット: **プロセスには仮想アドレス空間がリニア(直線的,一続き)**に見えます - 実装: CPUがメモリへアクセスする際、 (こっそり)**MMU**という回路が**仮想アドレスを物理アドレスへ自動変換**します。 通常MMUは**CPUに搭載**され、 **ページテーブル**(仮想->物理アドレス変換ルール表)の管理をカーネルが行います </small> --- class: img-right,compact # 仮想記憶のメリット、デメリット <div class=footnote> <small> (脚注1) 物理メモリを直接あつかうMS-DOS上のプログラミングは大変です(googleしてみて:-) (脚注2) 大昔(70年代末〜20世紀の間?)はメモリ容量も小さかったため、 巨大な仮想メモリが使えることに意義がありましたが、 <B>物理メモリから溢れた分はHDD,SSDに置いてアクセスするため、ものすごく遅く</b>なります。 いまどき物理を越える仮想メモリが必要なプログラムを走らせたら負けで、 必要なメモリをお金で調達=解決するべきです </small> </div>  - メリットは開発効率の向上です。特に (a)**メモリの詳細を気にせずにプログラムを書ける**ことが重要です。 (b)物理メモリより大きな仮想アドレス空間が利用可能にもなりますが、 遅くなるので現在では重要視しません(脚注も参照) - デメリットとしては (a)実装が複雑になること (b)ほぼMMUが必須であること (c)アドレス変換オーバヘッドなど --- class: img-right,compact # ページング型仮想記憶システム <div class=footnote> <small> (脚注) アドレス=ページ番号x単位(4KBなど)+ページ内オフセット;ページ番号だけを変換 </small> </div>  - アドレス変換はバイトではなくKB単位の固定長で行います。 この処理単位を**ページ**と呼び、大きさは4KBか8KBあたり - メモリをページで分割するタイプの仮想記憶が**ページング(paging)**型で、主流 - **ページテーブル**(アドレス変換ルール表)とは、仮想->物理ページ番号の変換表です。 表の要素(変換ルール)を**PTE**(Page Table Entry)と呼んでいます - HDD,SSDとメモリ間はスワップしています。 ストレージからメモリに読み込むことを**ページイン**、 ストレージに書き戻すことを**ページアウト**と言います --- class: img-right,compact # アドレス変換の様子  - 各プロセスは同じ(仮想)メモリ空間を使っていると**錯覚**していますが、 実際に読み書きする物理メモリの場所を変えています。 物理メモリは同時に複数のプロセスが共用しているわけです (= 物理メモリ上には複数のプロセスが共存) - 右図は、プロセスAもBも仮想ページ１〜５を使っていますが、物理ページは異なります。 プロセスAの仮想ページ1を物理ページの9へ変換し、 プロセスBの仮想ページ1を物理ページの5へ変換しています。 以下同様なので省略 --- class: img-right,compact # ページング型仮想記憶システムのメリット、デメリット <div class=footnote> <small> (脚注) 役割を考える方法も有り、 セキュリティ上よい実装が出来る可能性あり(詳細省略) </small> </div>  - メリットは実装がシンプルなこと - 処理単位が固定長なため - メモリ空間を単純に固定長で分割し領域ごとの役割などは考えない - デメリット - MMUが必要(ソフト処理は非現実的) - 小さなメモリ領域が必要な場合でも、 ページ単位より小さな処理はないため非効率なことがある --- class: col-2,compact # 参照の局所性とTLB(PTEのキャッシュ) <div class=footnote> <small> (脚注) TLB = PTEキャッシュ相当ですがTLBという特別な名称があるので覚えてください </small> </div> - ページテーブルはカーネルがメモリ上に準備します。 このサイズは大きいのでメインメモリでないと置けません - MMUはMMU自身が知らない(MMUのキャッシュにない)アドレス変換を要求された場合、 ページテーブルを検索し該当するPTEを読み込みます - 読み込んだPTEはMMUでキャッシュします。 **同じPTEをしばらく使うことが多いのでキャッシュは有益** - このキャッシュを**TLB**(Translation Lookaside Buffer)と呼びます <wbr> - TLBのキャッシュヒットは仮想記憶の性能向上にとって重要ですが、 このキャッシュヒットの高さを期待できる理由が**参照の局所性(locality of reference)**です - 経験則としてプログラムには**参照の局所性**があります。 もっともわかりやすい例がループ(一部のメモリ領域だけを重点的に使う例)ですが、 プログラムには多かれ少なかれ参照の局所性があります <br> `for(i=0;i<N;i++){ sum+=i;}` --- class: col-2,compact # ページ置換アルゴリズム <div class=footnote> <small> (脚注) 余談ですが、ページ置換アルゴリズムを正しく実装するのは意外と大変で... なにしろPTEを参照する様子をだれかが見張っているの?(いえ見張って無いです:-) </small> </div> - スワッピング(メモリとストレージ間で移動)しながらデータを利用しますが、 メモリも大きくは無いため、 読みこもうとしても、すでにメモリに空きがないことがあります - 空きを作る際は、 **ページ置換アルゴリズム**に従い、ページを削除(or ストレージへ書き戻し)後、 空いたページに必要なデータを読み込み(ページイン)します <wbr> - ページ置換アルゴリズムの代表例 - **LRU (Least Recently Used)** ... もっとも長期間使われていないページを削除 - **LFU (Least Frequently Used)** ... もっとも参照回数が少ないページを削除 - **FIFO (First In First Out)** ... もっとも古いページを削除