title:GearsOS の Paging と Segmentation
author:並列信頼研 桃原優
profile:

## OSの課題
- OS は時代とともに複雑性を増し、適切な資源管理や信頼性を保証する事は難しい。
- 現代 の OS では, User Space で Page Table Entry によるメモリ管理を行える OS は少ない。  

## 本研究室での取り組み
- メタレベルの処理で記述できる CbC の開発。
- CbC を用いる Gears OS の実装。

## 本研究の目的
- CbC で GearsOS を実装する事でメモリ管理を行えるようになる。
- しかし、今の GearsOS では単に Page Table Entry をコピーしてるだけ(Fork)。
- GearsOS にメモリ管理を行う API を考察する。 


## スライドの流れ
- <font color="red">GearsOS</font>
- Paging
- Segmentation
- GearsOS での Paging
- User Space で Page Table を操作する利点
- Xv6からの書き換え 

## GearsOS
- 以下を目的として GearsOS を開発している
	- 並列実行のサポート
	- 信頼性の保証

- 従来の OS が行うメモリ管理や並列実行などは Meta レベル(kernel space)で処理される。
- CbC という言語で GearsOS を実装する事で、ノーマルレベルから並列実行環境に合わせた記述ができるようにする

## Continuation based C
- Code Gear と Data Gear という単位でプログラムを記述する Continuation based C (以下、CbC)の研究を行っている。
- Code Gear
	- CbC における最も基本的な処理の単位
	- 入力と出力を持つ。goto によって Code Gear から次の Code Gear へ遷移する事で継続的に処理を行い、並列処理をする。
- Data Gear
	- データの基本的な単位。
	- 2種類ある。
		- Input Data Gear
		- Output Data Gear
	- Code Gear の遷移の際に Input Data Gear を受け取り、Output Data Gear を吐き出す。
 

## CbC のメタ計算
- CbCではノーマルレベルの記述とメタ計算を行うメタレベルの記述がある。
- メタ計算を以下のように表現する。
	- Meta Code Gear 
	- Meta Data Gear

## ノーマルレベルとメタレベル
-  ノーマルレベルからメタレベルへの変換は Perl による変換スクリプトで実装している。
-  Meta Code Gear は Code Gear の直前と直後に挿入し、メタ計算を行う。

<div align="center"><img src="./images/meta_cg_dg.svg" style="center"></div>

## Meta Compitation
- Gears OS では通常の処理を Compitation として扱う。
- Compitation のための Compitation を Meta Compitation と呼ぶ。
- GearsOS では Meta Compitation を Meta Code Gear, Meta Data Gear で表現する。

## Meta Compitationの例
- 並列処理の依存関係の解決
- OS が行うネットワーク管理
- メモリ管理


## スライドの流れ
- GearsOS
- <font color="red">Paging</font>
- Segmentation
- GearsOS での Paging
- User Space で Page Table を操作する利点
- Xv6からの書き換え 



## Paging
- 仮想メモリでは Paging と呼ばれるシステムを使っている。
- 様々なコンピュータではプログラム側がメモリアドレスを参照する。
- コンピュータ上では仮想メモリなしでは、仮想アドレスは直接メモリバスを置けない。
	- バス(Bus)はメモリなどの信号を流す共通の信号回路


## MMU
- 仮想メモリが使われる時、仮想アドレスは直接メモリバスへは行かず、MMU(メモリ管理ユニット)に行く。
<div align="center"><img src="./images/fig3_8.svg" style="center"></div>

## MMU の動きの例
- プログラムがアドレス0にアクセスしようとした時
	- MOV REG, 0
- MMU はこの仮想アドレスが Page0で失敗してないか確認し Page Frame2(8192~12287)にマッピングする
- アドレス0を8192に変換し、バスに出力する。
- メモリはMMUについて何も知らず、アドレス8192を読み書きする要求だけを見る。
- 従って、MMU は 0から4095までの仮想アドレスを物理アドレス8192から12287に効果的にマッピングする。
- プログラムがマップされてないアドレスを参照しようとするとOSにCPUをトラップさせる(Page Fault)


## Page と Page Frame
- 仮想アドレス空間では Page と呼ばれる固定サイズ単位を扱う。
- 物理メモリ内での対応する単位は Page Frames と呼ばれる。
- Page と Page Frames は同じサイズを生成する。


## スライドの流れ
- GearsOS
- Paging
- <font color="red">Segmentation</font>
- GearsOS での Paging
- User Space で Page Table を操作する利点
- Xv6からの書き換え

## Descriptor
- プログラムがアクセスするファイルなどをOSが識別するための識別子
	- GDT(Global Descriptor Table)
		- セグメントを管理するためのテーブル
		- アドレスの最初の番地とサイズなどが格納されている
	 - LDT(Local Descriptor Table
		- タスクごとにGDTに相当する Descriptor を持たせてセキュリティを高める
- Selector ビットのうちの1つはそのセグメントがローカルかグローバルかを知らせる。
- その他の13ビットはLDTかGDTエントリ番号を指定するため、これらのテーブルはそれぞれ8Kのセグメント記述子を保持するように制限されている。


## Segment Register
- selector が利用可能でないことを示すために Segment レジスタにロードする。
	- この時トラップが発生
- ロードされた時点で、対応する Descriptor がLDTまたはGDTからfetchされ、レジスタに格納されるため、素早くアクセスできる。

## Descriptor の構成
- Descriptor は Segment の Baseアドレス、Size、その他の情報を含む8バイトで構成されている。

<div align="center"><img src="./images/x86code.svg" style="center"></div>

## Segmentが存在しない場合(selector0)
- トラップが発生する
- 次にハードウェアはオフセットがSegmentの終わりを超えているかどうかをチェックするためにlimitフィールドを使用する。

## リニアアドレス
- セグメント内のメモリとオフセットが範囲内にあると仮定すると、x86はDescriptor 内の32ビットのBaseフィールドをオフセットに追加してリニアアドレスと呼ばれるものを形成する。

<div align="center"><img src="./images/Conversion_of_a_selector_offset_pair_to_a_linear_address.svg"  width="30%" height="30%"  style="center"></div>

## Pagingが無効にされてる場合
- リニアアドレスは物理アドレスとして解釈され、読み取りまたは書き込みのためにメモリに送信される。
- 従って、Pagingを無効にすると、各セグメントのBaseアドレスをDescriptorで指定した純粋なSegmentation Scheme ができる。

## スライドの流れ
- GearsOS
- Paging
- Segmentation
- <font color="red">GearsOS での Paging</font>
- User Space で Page Table を操作する利点
- Xv6からの書き換え

## GearsOS での Paging の実装
- GearsOS で Paging を実装するために必要なもの
	- Context に必要な Page Table を提供する Interface
	- User Space からアクセスする API
- Page Table に相当するデータを Input Data Gear で受け取って変更
- その後、Context にあるメモリコントロールを担当する Meta Data Gear に goto してアクセス。

## Meta Compitation による Page Table の操作
- Meta Compitation レベルで Paging を処理する事で User プログラムでも Page Table を操作することができる。
- Meta Compitation に戻る際に、Page Table Entry のバリデーションをチェックして反映することで、他のプロセスから Page Table を書き換えられることを防ぐ。
- さらに、サンドボックスにしておいて、他のプロセスが書き換えられた時にエクセプションを飛ばすようにする。


## Segmentation の切り替え
- Code Gear を切り替えるたびに Segmentation を切り替えると処理が遅くなる。
- Context は スレッドごとにあるので、 Code Gear と Data Gear は自由に切り替えることができる。

## 切り替えの問題点と解決手法
- Code Gear と Data Gear は煩雑に切り替わる
	- Context に沿ってアクセスできる範囲を制限する必要がある。
- Context と Segmentation を組み合わせることで GearsOS の Paging を実装する。

## 現代のOSのメモリ管理
- User Space で Page Table Entry によるメモリ管理を行える OS は少ない。
	- User レベルの操作で Page Tabel が書き換えられたり、別のPage にアクセスするのを防ぐためだと考えられる。

## スライドの流れ
- GearsOS
- Paging
- Segmentation
- GearsOS での Paging
- <font color="red">User Space で Page Table を操作する利点</font>
- Xv6からの書き換え

## User Space で Page Tabel を操作する利点
- User Space でメモリ管理を行えるようにするとこで、Page のバリデーションをチェックしたり、サンドボックスによる信頼性の保証が行える。
- また、適切な記述をすれば最適なメモリ管理を行うことができるようになる

## スライドの流れ
- GearsOS
- Paging
- Segmentation
- GearsOS での Paging
- User Space で Page Table を操作する利点
- <font color="red">Xv6からの書き換え</font>

## Xv6
- Xv6 とは、マサチューセッツ工科大の大学院向け講義の教材として使うために、UNIX V6 という OS を ANSI-C に書き換え、x86 に移植した OS である。
- Arm のバイナリを出力するので、Raspberry Pi や携帯電話など様々なハードウェアで動かすことができる

## Xv6 を元にした GearsOS の実装
- GearsOS はメモリ管理や CPU の管理を User Space から操作できることを目標に実装しているので、メモリに限りのあるハードウェアで動くように実装できる方が好ましい。
- ANSI-C で書かれているXv6を CbC で書き直し、 それを元に GeasOSを実装する。
- Xv6の新しい要素として GeasOS の Context の部分を User Space 側で実行する。









## 図 

<div align="center"><img src="./images/x86code.svg" style="center"></div>