日本ソフトウェア科学会第 37 回大会 (2020 年度) 講演論文集

不揮発性メモリの併用に特化した IOT 向けプログラム
言語ランタイム井上 曜

千葉 滋

回路サイズ，価格コスト，消費電力などの制約で使えるリソースが少ない IOT 向けデバイスでは，メモリ使用量のオーバーヘッドの少ない言語が使われがちである．補助記憶装置である Flash メモリを併用すれば，高級な言語をこのようなデバイスで動かせるが，Flash メモリの書き込み回数には制限がある．そこで，Flash メモリを拡張用のメモリとして利用しても，書き込み限界に達しにくくするプログラミング言語用バーチャルマシンを提案する．書き込み制限の問題に対して，ページングで管理された Flash メモリ領域への物理書き込みを低減するために，ページアウトの対象を書き込み回数に応じて最適化したことと，メモリ確保とメモリ解放機構を改良することで，書き込みの多いオブジェクトをまとめることを行った．

Programmer uses programming language with low memory overhead for Small size, low cost or low power
consumption IOT devices that don’t have have many resources. By using Flash memory, which is theauxiliary storage device of the IOT device, together with RAM, it is possible to use high-level languages
for IOT devices，but it is not possible simply because the number of writes to Flash memory is limited.
Therefore，we propose a virtual machine for programming language that uses Flash as memory to delays
reaching the writing limit as much as possible. We optimize the pageout selection algorithm to reduce thenumber of writes to the Flash memory area managed by pagins and improves the memory allocation andgarbage collection algorithm to separate objects that write a lot and those that don’t.

良い．ただし，IOT デバイスではメモリ管理ユニッ1 はじめにトが搭載されていないという点や Flash には一定回回路サイズ，価格コスト，消費電力などの制約で使数書き込むとその領域が使えなくなるという性質にえるリソースが少ない IOT 向けデバイスでは，メモよって単純な方法では Flash 領域は仮想記憶としてリ使用量のオーバーヘッドの少ない言語が使われが使うことができない．例えば，ATmega328P では書ちである．メモリを仮想的にでも多く使うことができ込み回数は 10,000 回で頻繁に Flash 領域にあるオ

きれば，メモリを多く消費するが，生産性の高い機能ブジェクトを変更させるようなプログラムだとすぐにを使うことができる．そして，IOT 向けアプリケー使えなくなるだろう．このような環境でも Flash を併

ションの開発者は容易にプログラミングを行うことが用してメモリを仮想的に使うことのできるようなメできるようになる．

モリ管理システムが必要である．そこで本論文では，仮想的にメモリを増やすことは，IOT デバイスにFlash を併用してもメモリの書き込みをできるだけ抑搭載されている Flash 領域を仮想記憶として使えばえることができるメモリ管理機構を提案し，容易にIOT デバイスで開発できるようなプログラミング言
Programming language runtime for IOT devices with
non-volatile ﬂash memory．
This is an unrefereed paper. Copyrights belong to
the Author(s)Akira Inoue Shigeru Chiba, 東京大学大学院情報理工学系研究科, Graduate School Information and Science
Technology， The University of Tokyo． .

語ランタイムを実現した．

2 背景
通常のメモリ領域以外の記憶領域である Flash をメ
モリと同じ用に使うには仮想記憶のような機構を作れ

ば良い．Flash 上のアドレスはメモリアドレスと区別

想マシンの read/write barrier によって必要に応じてされているため，仮想的なアドレスに置き換えて通常ページ単位でメモリにページをコピーする (ページイのメモリアドレスのように使える必要がある．一般的ン)．そして，ページをコピーする領域が RAM になな環境で仮想アドレスを実アドレスに変換する場合，くなった場合は優先度の低いページをメモリから取りメモリ管理ユニットを使うが，IOT デバイスではメ出し変更が必要であれば Flash へ反映させせる (ペーモリ管理ユニットを搭載していないものが存在するた

ジアウト)．

め，仮想マシン上で read/write barrier を用いて実際提案手法としてページアウト時に書き込み頻度を下のオブジェクトが置かれているアドレスへと変換するげるためにメモリ管理を工夫した．まず，書き込みのといった手法が必要である．このように read/writeあるページをできるだけメモリ上に保つためのペー

barrier が使えるプログラミング言語処理系であればジアウト対象の選択アルゴリズムを改良した．さら

メモリ管理ユニットが存在しないハードウェアでもに変更のあるオブジェクトだけをメモリ上にあるコFlash を追加のメモリ領域でも使うことができる．しピーされたページ内に保つためにガベージコレクショ

かしそれだけでは Flash に一定回数書き込みを行う

ン時の compaction で変更のあったオブジェクトをまとその領域が使えなくなるため，現状では書き込み回とめるような機構も作成した．

数が多くなりすぎ実用的ではないことが課題である．

3. 1 volatile 領域と non-volatile 領域

3 Conditional second chance FIFO とMark and classiﬁed compact

オブジェクトが割り当てられる領域は，RAM 上に連続した区間で切り出された volatile 領域と volatile

本論文ではガベージコレクションつきの仮想マシン

領域に空きがないときに使われる，Flash 上の non-を使ってメモリ参照を抽象化することでページング

volatile 領域の 2 つが存在する．図 1 に各領域の使わ方式の仮想記憶のようなメモリ管理システムを実現れ方を示す．non-volatile 領域は，仮想記憶のページした．さらに，page out するページの選択方式としングと同様に，ページ単位で RAM 上に確保されたて Second chance FIFO を改造したものを用いるこ

ページサイズの定数倍の大きさの領域のページ置きとと，ガベージコレクション時に compaction するこ場にコピーして読み書きを行っている．本システムでとで書き込み回数の低減を図ることを可能にした．

はポインタの末尾ビットに non-volatile 領域か判定す本システムはメモリ上にある容量の小さい volatileるための情報が入っており，参照時に write-barrier

領域と Flash 上にある volatile 領域より大きい non-によってページ置き場に置かれたページへのポイン

volatile 領域がある．volatile 領域は容量が小さいがタを返す．それ以外は non-volatile 領域上のオブジェ

ページングを必要とする non-volatile 領域と違い直クトは volatile 領域上のオブジェクトと表現は変わ

接参照であるため高速であり変更に制限がないためらない．新しく non-volatile 領域にオブジェクトをこの領域に空きがあれば優先的に volatile 領域から確割り当てたい場合は，ページ置き場に Flash 上の配保する戦略をとる．volatile 領域は貴重であることと置予定のページのアドレスを紐づけた空のページを全領域の頻繁なガベージコレクションは計算コスト置き，そこにオブジェクト用の領域を確保しておく．

が大きくと Flash への書き込みが生じるため volatile

object は，volatile 領域に要求されたサイズが確保で領域だけの Mark and sweep のガベージコレクショきるだけの余裕があった場合優先的に volatile 領域かンが必要である．volatile 領域だけのガベージコレクら確保される．volatile 領域のみガベージコレクショ

ションを使うには，non-volatile 領域に volatile 領域ンするために，non-volatile 領域から volatile 領域へのオブジェクトを書き込みを行った時に仮想マシンの参照を作った場合はそのオブジェクトのアドレスの write barrier に remenberd set へ登録する機構のの remenberd set を作っておく．そして，volatile 領追加によって使用可能になる．non-volatile 領域は仮域だけのガベージコレクションしても領域不足で確スを低減するようなページアウトアルゴリズムが必

ページ置き場volatile領域要である．Second Chance を改良した，Conditional

ページ1(コピー)RAM

Second Chance FIFO を提案する．
まずページに対して，読み書きしたときに立つ参照コピーを置く

参照

フラグと書き込みを行った write フラグと新規当て用
ページ1のページ用のフラグの 3 つを用意する．参照フラグ

ページ2

FLASH

は，FIFO の先頭に出た時点でオンならば，オフにしObjectて FIFO の最後尾に置かれ，それ以外ならばページコード・定数領域

図1

non-volatile領域アウトされる．この時点でページアウトされなければ，write フラグと新規割り当てページと割り当てら提案システムの空間の使われ方れていない区間の割合を元にページアウトの対象を選択する．具体的には図 2 のような順序でページア
図2

Conditional second chance FIFO ページアウ
トの順序ウトされる．

3. 3 Mark and classiﬁed compact

最近参照されていない書き込みのないページ →3.2 のページアウトの最適化は変更のあったページ書き込みのない新規割り当てでないページ →と変更のないページが別れていなければどれをページ書き込みのない新規割り当てページ → 書き込

アウトしても Flash への書き込みが生じるため意味

みのあった新規割り当てでないページ →新規割り当てページで空き領域が多いページ

がなくなる．したがって，今後変更が生じるオブジェ

クトとそうでないものを分けてページに配置する必要がある．これは，過去に変更のあったものは今後も保に失敗した場合，non-volatile 領域から確保する．

変更されやすいという仮定から，Mark and compact

non-volatile 領域上に存在するオブジェクトは，Flashのようなメモリの再配置を行うガベージコレクショ上のアドレスで管理されている．データを参照するンと連動して再配置時に過去の変更記録をもとに今時は，都度 RAM 上にコピーされた領域上のポイン

後変更されやすいオブジェクトをまとめることで解タに変換するコストがかかる．つまり，ページ置き決できると考えられる．そこで mark and compact

場に存在しないページ上にあるオブジェクトの参照の改良として，non-volatile 領域のための Mark andは，ページイン (ページアウト) とアドレスの変換でclassiﬁed compact を提案する．

volatile 領域へのアクセスよりはるかに大きくなる．

mark フェーズでは，Flash への書き込みをしないために Mark ビットを RAM 上に配置することでペー

3. 2 Conditional second chance FIFO

ジは読み込みだけで済む．compaction フェーズは，ページアウトでは，基本的にはページミスを低減

アルゴリズム 1 で示される．non-volatile 領域の各するようにページを選択しなければならないが，書ページの生存しているオブジェクトを過去に書き込

き込みのあ ったページのページアウトは Flash の寿みが発生したかに基づいて 2 種類に分ける．そして，命を縮めるため，それも避ける必要がある．書き込み書き込みが発生していないオブジェクトから ﬂash のが起こるページアウトは，set-car!や set-vector!など各ページに書き出し，その後書き込みが発生したもによって変更されたオブジェクトを含んだページと新のを ﬂash の各ページに書き出す．実装では，すべて

規割り当て用のページアウト時に Flash に反映させのオブジェクトを読むまで書き出しを待つ必要はなる必要のあるページの 2 つで生じる．この 2 種類の

い．1 ページ分の容量分のオブジェクトをどちらかのページの追い出しの優先度を落としつつ，ページミQueue に存在する場合は書き出すようなことをする

案手法のものに置き換えることと，オブジェクトを参Algorithm 1 non-volatile 領域用の compaction algorithm
1: writtenQueue ← 空の Queue

照する時に read/write barrier を挿入するようなコードを出力して non-volatile 領域かを判定すればよい．

4 実装

2: noW rittenQueue ← 空の Queue

本システムは Scheme 用のバーチャルマシン (レジ3: for page = ﬂash の各ページ do4:for obj = page の各オブジェクト do
if alive?(obj) and changed?(obj) then5:

P ush(writtenQueue, obj)

6:else if alive?(obj) and not changed?(obj)7:

P ush(noW rittenQueue, objectP tr)

9: addrT able ← 空の辞書
10: for page = ﬂash の各ページ do
11:
12:
13:

(large) 準拠させるつもりだが，現在は R7RS subset
程度の機能である．処理系の中間コードは CPS 変換したもので，そのまま逆 CPS 変換せずにターゲットのバーチャルマシンに変換した．Scheme からバー

then8:スタマシン) として実装されている．将来的には R7RS

if not empty?(writtenQueue) then

チャルマシンへのコンパイラも実用のために用意した．Aruduino Uno 程度のスペック (表 1) で動作することが目的ではあるが，現状は開発のしやすさから

M5Stack Basic (表 2) で動作するものになっている．

while do表1

obj ← pop(writtenQueue) ま た はobj ← pop(noW rittenQueue)

Arduino UNO のスペック

CPU

16MHZ

RAM

2KB

14:

if obj が page にかけない then break

FLASH

32KB

15:

write(page, obj)

EEPROM

1K

16:

set(addrT able, obj の旧アドレス , objの新アドレス ))表2

17: for obj = すべての object do
18:

for member = 0tosizeof (object) do

19:

if haveKey(addrT able, obj[member]) then20:

obj[member] ← addrT able[obj[member]]

M5Stack Basic のスペック

CPU240MHZ

RAM520KB

FLASH

16MBことで，書き出し待ちの 2 つの Queue によるヒープ

5 関連研究の使用量を低減することができる．

5. 1 CFLRU
フラッシュメモリ用のページ置換アルゴリズムは

3. 4 本方式の汎用性他にもあり，基本的なものでは LRU の改良である，

本方式はバーチャルマシンや事前にネイティブコン

CleanFirst LRU (CFLRU) [1] がある．Flash の書きパイルする言語において read/write-barrier と動的確込み時間は読み込み時間より大きく，書き込みのある保部分を置き換えることで実現できる．バーチャルマ

ページと読んだだけのページを区別せずにページアウシンでの実装は本研究で実現できた．ポインタを直接トすると時間的な効率が悪くなる．そこで，書き込み操作しないような言語用のコンパイラで提案手法ををしていないページ (Clean page) を優先的に RAM実現するにはまず提案手法のメモリ管理を組み込むから追い出すことをしている (Clean First)．すべて必要がある．そして，メモリを動的確保する関数を提において Clean page を優先的にページアウトし続けページ7

ページ6

ページ5

ページ4

ページ3

ページ2

ページ1

フラグと初期化用のページのフラグを付けて，参照ビット以外にもそのフラグを立っているものも優先度を下げるために再度 FIFO に挿入されるようにしてWorking region

Clean-ﬁrst region(w=4)

ある．メモリにコピーされたすべてのページが pageout 時に Flash への書き込みが発生しないページの場
Dirty page

Clean page

図3

CFLRU のアルゴリズムのサンプル

合 Second chance FIFO と同じになる．

6 まとめ
本論文では，メモリの足りない IOT デバイスでも，不揮発性メモリを仮想的に使えるようなメモリるとキャッシュヒット率が著しく低下するため，LRU管理方法を示した．書き込みの多いページをできるの先頭 w ページ分を Clean First とし，それ以外はだけメモリに保つために．Second chance FIFO を改書き込みをしているかどうか区別せずページアウトす

良して ページアウトの優先順位を変更するアルゴリるようになっている．例えば，CFLRU が図 3 のようズムを提案した．それから，Mark and compact のな状態の時，ページアウトされる優先順位は，(ペーcompaction を改良し，書き込みのあったオブジェク

ジ 1，ページ 4，ページ 2，ページ 3，ページ 5，ペートをまとめることで，クリーンなページだけをページジ 6，ページ 7) となる．

アウトすることも実現した．

CFLRU は書き込みのあったページをできるだけ今回提案した手法の問題がいくつかある．まず，すページアウトしない方針である．今回提案するシステ

ぐに不要になりうるオブジェクトが non-volatile 領域

ムでは，確保されたが Flash に一度も書き込まれてに置かれるようになっている．また，変更の多いオブいないオブジェクトを含むページもページアウト時ジェクトもガベージコレクション時にまとめられるよに Flash への書き込みが発生するページとして扱わうになっているが，non-volatile 領域に置かれたままれる．このような確保用のページは書き込みは 1 度になっているのも問題になっている．この両方で必要は発生するがオブジェクトに変更を加えたわけではなな要素は，volatile 領域と non-volatile 領域でのオブいため，今後も Flash への書き込みが起こりやすいジェクト間の移動をする機構である．使用頻度や書きページとは限らないということを考慮が必要である．

込みの有無，オブジェクトの寿命などの要素から適切

Conditional second chance FIFO は書き込みを抑えな領域に配置するような機構を今後導入を検討してるという点では CFLRU と目的は同じだがプログラいる．それから，今回のアルゴリズムの評価のためのム言語ランタイム用のページングとして確保用のペー実験を行うことも今後の課題である．ページアウトのジの性質もページアウトの優先順位の要素として加アルゴリズムを CFLRU [1] と比較したり，実用的なえた点が異なっている．

アプリケーションでの書き込み頻度と寿命を計測したりすることを検討している．

5. 2 Second chance FIFO
Second chance FIFO は FIFO を改良したアルゴリズムで参照された時に立てられる参照ビットが各ページに存在しており，FIFO の先頭のページが参照ビットが立っていた場合，参照ビットをクリアして最後尾に繋げるアルゴリズムである．提案手法である

Conditional Second chance FIFO はこれに書き込み

参 考 文 献[1] Park, S., Jung, D., Kang, J., Kim, J., Lee, J:Cﬂru:A replacement algorithm for ﬂash memory,
Proceedings ofthe 2006 International Conference onCompilers, Architectureand Synthesis for Embedded Systems, ser. CASES 06, NewYork, NY, USA,2006, pp. 234–241.