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
- CrossCompile
- 今後の課題





## 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 の直前と直後に挿入し、メタ計算を行う。

- 図: ノーマルレベルとメタレベルの継続の見え方

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

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


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

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



## Segmentation with Paging: The intel x86




## 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 にアクセスするのを防ぐためだと考えられる。

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

## 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/Conversion_of_a_selector_offset_pair_to_a_linear_address.svg" style="center"></div>
<div align="center"><img src="./images/x86code.svg" style="center"></div>