論文紹介：Multiprogramming a 64kB Computer Safely and Efficiently

元論文：Multiprogramming a 64 kB Computer Safely and Efficiently

以前の記事でも少し紹介したRustで書かれた組み込みハードウェア向けのOSの設計についての論文である。

実際のOSのプロダクトのサイトはこちら： Tock Embedded Operating System

論文概要

  • タイトル：Multiprogramming a 64 kB Computer Safely and Efficiently
  • 著者：Amit Levy (Stanford University) et al.
  • 会議：The 26th ACM Symposium on Operating Systems Principles (SOSP 17)

目的

同年のAPSysで発表した論文がRustという言語でどのようにOSを書くかを論じているのに対して、こちらはタイトルからもわかるようにCPUが貧弱でメモリが非常に少ない環境でのOSデザインについて論じている。
著者らが対象としてるのはCortex-MシリーズのようなRAMが数10kB程度、MMUのような高度なメモリ保護機能がないマイクロコントローラ（MCU）である。
このようなMCUでも、例えばスマートウォッチのように複数の独立したアプリケーションを動かすためOSが必要になってくる。
もちろん、MCU向けのOSというのは多く存在しているが、並列性やメモリの効率、Fault isolationなどの要件を同時に満たすのは容易ではない。

著者らTockというOSをRustで実装し、これらの課題に取り組んだ。

CapsulesとGrants

Tockを構成するキーとなる概念がこのCapsulesとGrantsである。

Capsulesはカーネルに組み入れられるコンポーネントとなるユニットたちで、Rustの構造体として現される。
このCapsuleを用いてデバイスのインターフェースやシステムコールのインターフェースをつくる。それぞれのCapsuleはRustの型システムによって互いのメモリに直接は干渉できないようにできる。
Capsuleのメモリ安全性は型システムによる所有権により検証される、つまりコンパイル時に検証されるので実行時のオーバーヘッドを最小限にできる。
カーネルのスケジューラはイベントドリブンで駆動し、Capsulesと直接やりとりする。Capsules自体はイベントを発行することはないため、スケジューラを介す必要はない。単純な関数であればインライン化されることも期待されるのでこれも実行時のオーバーヘッドを減らすことになる。
ただし、プリエンティブされることはないことになるので、実行時間の長い処理をさせるとシステム全体を止めることとなり得る。

Tockにも通常のOSのようにプロセスの概念が存在する。それぞれ独立のヒープ領域とスタック領域を持ち、カーネルやその構成要素のCapsulesとはシステムコールイベントを発行することでやりとりする。
ただし、MCUはMMUを持たないため、全て絶対アドレスでのメモリアクセスとなる。そこで代わりにMemory Protection Unit(MPU)を用いてメモリ領域を保護する。
プロセス自体はどんな言語でも書け、またスケジューラによってプリエンティブされる。

プロセスがCapsulesに処理を依頼する場合、そのリクエスト毎にメモリが必要となることがある。例えばタイマーであれば、どの時間にどの関数を呼び出すか、のようなメタデータを格納する必要がある。
ただし、システム実行中にそのメタデータを最大いくつまで保持しなければならないかを予想するのは難しい。そのため、単に静的に確保した配列に情報を格納すれば、並列に実行できるリクエストの数を制限することになるし、
動的にメモリを確保しようとすれば、カーネルのヒープ領域が突然足りなくなることが考えられる。
そこでTockではプロセス毎にGrantsと呼ばれる領域を持たせて、このメモリ領域をCapsulesに渡す、というテクニックを用いる。カーネル領域のヒープ領域に対して、Grantsはプロセス内の一種のヒープ領域みたいなものなので（プロセスの通常のヒープは別に存在している）、
動的にメモリを確保することにはなるが、メモリが足りなくなっても、そのプロセス1つのみが困るだけなのでシステム全体が困るという自体は避けられる。
Grants領域はMPUで保護されているため、プロセス自身がこの領域を直接アクセスすることはできない。

評価

Tock自体、全く新しい構成のOSなので従来OSとの単純比較はできない。
そこで、Case StudyとしてTock上で実際にアプリケーションを実装した時のCase Studyと、新たに導入された概念であるCapsulesとGrantsによるパフォーマンスの検証を行っている。
ボードはArmのCortex-M4を用いた評価ボード上で構成している。
CapsulesやGrantsの各種インターフェースは当然ある程度のメモリオーバーヘッドと実行時オーバーヘッドを伴うが、それがモノリシックなシステムや既存のプロセスベースのシステムと比べて少なくてすむことを検証ている。
ただ、Grantsの導入はカーネルのアルゴリズムの変更を強要する。例えば、タイマーの例であれば、ハードウェアからの割り込みが発生した際、どの処理を行うか登録されたイベントから探さなければならないが、
その情報は各プロセスの各Grants内に入っているためそれを全て走査しなければならない。ただし、そもそもMCU上でのシステムで大量にプロセスが発生することはあまりないので大きい問題にはならないと主張している。

まとめ・感想

Rustの型システムを活用することで、新たな概念を利用しつつ組み込みOSに適した並列性、メモリの効率性、Fault isolationをTockは達成した。

まだ実際の実装を追うところまではできていないので、進捗ダメです