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

Flash メモリを併用するスモールデバイス向けメモリ管理システム
井上 曜

千葉 滋

IOT で使われるようなスモールデバイスでは， メモリ使用量のオーバーヘッドの少ない言語が使われがちである．
Flash メモリを拡張用に併用することで，高級言語をスモールデバイスで利用できるようになる．Flash メモリは書き込み耐性が低く，高レイテンシで消去操作の必要性や書き込みを一定単位でしか行えないという制限がある．そこで，Flash メモリを拡張用のメモリとして利用しても，書き込み限界に達しにくくするプログラミング言語用メモリ管理システムを提案する．Flash メモリの拡張は，仮想機械の read/write barrier を用いて，ページングとソフトウェア的なアドレス変換によって実現できる．そして，Flash メモリへの物理書き込みを減らすために，ページアウトの対象の選択をその対象の書き込み回数に応じて最適化したことと，分散した変更されそうなオブジェクトをガベージコレクション時にまとめることで，書き込み回数を減らすることを行った．
Software developers tend to use languages with low memory overhead when developing on small devices suchas those used in the IOT. By using Flash memory as extended memory,softwared developers can use highlevel languages on small devieces. Flash memory has many limitations such as low write dndurance, highlatency, the need for erasing operations, and the ability to write only on a page-by-page basis. Therefore we
propose memory management system for programming language that prevents the writing limit from being
reached as much as possible even if the Flash memory is used as memory as extended memory. We have
expanded the Flash memory by paging and software-like address translation using the read / write barrierof the virtual machine. Then, in order to reduce the physical writing to the Flash memory, we reduced thenumber of writes by optimizing the selection of page-out targets according to the number of writes of thetarget, and by grouping distributed and likely to be updated objects during garbage collection.

助記憶装置である Flash メモリを仮想記憶を用いて1 はじめに拡張用のメモリとして使えば良い．ただし，スモール

IOT で使われるようなスモールデバイスでは， 搭デバイスには，仮想的なアドレスを物理アドレスに変載されている主記憶領域が小さく，メモリを多く消費換するデバイスである MMU や，Flash が書き込みするような生産性の高いデータ構造が使えないことに対して脆弱であり，消去や書き込みに制約があるたがある．ソフトウェアを容易に開発するためには，メめ，簡単に使うことはできない．さらに，仮想記憶とモリを多く使えるようにすることや， 自動で不要なガベージコレクションのトレース操作は相性が悪いたオブジェクトを解放するガベージコレクションがある

め，この欠点を相殺するような機能が必要である．と良い．そして，IOT 用途でこのようなデバイスを

本論文では，Flash メモリの書き込みを低減するよ

使う場合は，多量にばらまくことがあるため，できるうなページングアルゴリズムと書き込み回数を考慮だけデバイスの価格コストを押さえる必要もある．

したコンパクションアルゴリズムを提案する．まず，安価にメモリを増やすには，スモールデバイスの補Flash メモリのアドレスはソフトウェアでの変換を用

A memory management system using Flash memory
for small devices
Akira Inoue Shigeru Chiba, 東京大学大学院情報理工学系研究科, Graduate School Information and Science
Technology， The University of Tokyo .

いて，仮想記憶を使えるようにした．オブジェクトの書き込み回数や読み込み回数を記録し，ページアウト時への書き込み回数を押さえるような Conditional

bit LRU というアルゴリズムを実現した．そして，

Mark and Compact 時に書き込みのあったオブジェクトをまとめるようなアルゴリズムも実現した．
本提案手法を適用したメモリ管理システムとそれ3 Conditional bit LRU と Mark andclassiﬁed compactを組み込んだ Scheme 処理系を実装し，仮想的な環

Flash メモリは書き込み耐性が低いため，単純に拡境で，Flash への書き込み回数とページフォルト数を張用のメモリとしてつかうことができない．本研究で計測した．結果は，Scheme 処理系と提案手法との相は，それを解決するために Conditional bit LRU と性が悪く，LRU と比較して書き込み回数がわずかにMark and classiﬁed compact という 2 つの方式を搭しか良くならなかった．そこで，スモールデバイス向載したメモリ管理システムを提案する．提案するメモ

け Ruby 処理系である，Mruby にも提案手法を組みリ管理システムは，ユーザに malloc のような動的確込んで実験を行う予定である．

保とアドレス変換の関数を提供し，メモリ不足を検本研究は，昨年の発表の改良である．以前のシス

出すると自動的に不要なオブジェクトの回収を行う．

テムにたいして，オブジェクトが移動，Condtion bit

この動的確保とアドレス変換関数を用いて，プログラ

LRU を新たに提案する．それから，Scheme 処理系

ミング言語のランタイムを実装すれば Flash メモリでの実験を追加した．

を追加のメモリとして扱えるプログラミング処理系を作ることができる．

2 背景
Flash メモリは書き込み耐性が低く，書き込みのレ

3. 1 メモリ管理システムの概要

イテンシが大きく，Flash メモリは書き込む前にブ本システムの領域の使い方の概要を図 1 に示す．

ロック単位の領域削除が必要であるため， 単純に拡ヒープ領域は，RAM 上にある volatile 領域と Flash張用のメモリとして使うことはできない．また，スメモリ上にある non-volatile 領域の 2 つに分けられモールデバイスの多くは，仮想アドレスを実アドレスる．volatile 領域上のオブジェクトは直接読み書きでに変換するデバイスである MMU を備えていないた

きるが，non-volatile 領域上のオブジェクトは，ペーめ，仮想記憶を仮想機械の read barrier などのソフジ単位で RAM 上のページ領域上にコピーして使う

トウェア的なアドレス変換などを用いる必要がある．

(ページイン)．ページ領域上にページがあふれるとソフトウェアを容易に開発するには，ガベージコレク

きにページを項 3. 2 のアルゴリズムによって 1 つ選ションが必要だが，仮想記憶とガベージコレクション択し，non-volatile 領域に書き戻す (ページアウト)．のトレース操作は相性が悪いため，この欠点を相殺す

それから，non-volatile 領域上のオブジェクトのオブるような機能が必要である．

Mruby や Micro Python，Picobit [2] など，スモー

ジェクトヘッダは頻繁に変更されるため，RAM 上のヘッダ領域に配置した．

ルデバイス向けの言語処理系はいくつか存在するが，本システムでは，non-volatile 領域上のアドレスは，Flash メモリを併用して仮想的にメモリを増やし，仮想的なアドレスとして表現している．ポインタの末Flash メモリの欠点を軽減するようなメモリ管理シス

尾ビットをフラグとして用いて各領域の区別や、固定テムを搭載している言語処理系は知る限り存在しな長整数などのその他の値と区別するようなことを行

い．多くの処理系は，実装をリソースの消費しないよう。参照バリアを用いて，non-volatile 領域上のオブうなロジックに置き換えるようにしたり，仕様を一部ジェクトが参照を検出し，対象のページをページイン削ることでスモールデバイス上で動くようにしていし，ページ領域にコピーされたオブジェクトのアドレる．これらの処理系では，リソースを多く消費するよスに変換して返す．

うな機能を使うにはメモリを増やさなくてはならず，システムのコストが高くなってしまう．

システムが動的にメモリ領域の確保が必要になった時，優先的に volatile 領域から確保する．volatile 領域が不足すると，volatile 領域内の不要なオブジェクトをページ領域

volatile領域

ヘッダ領域

図2

Conditional second chance FIFO ページアウRAM
オブジェクトヘッダ
移動

ページインページアウト

トの順序



最近参照されていない書き込みのないページ →書き込みのない新規割り当てでないページ →オブジェクト

書き込みのない新規割り当てページ → 書き込

Flash
ページ1

ページ2

ページN-1

ページN

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

non-volatile領域

図1





システムの概要

Conditional bit LRU は，LRU の近似アルゴリズム
回収する volatile-GC を行う．この部分な GC のため，である reference bit LRU を改良したものである．各

non-volatile 領域から volatile 領域への参照が生じた

ページには，reference bit と write bit と allocate bit

場合は，そのオブジェクトのアドレスの rememberedの 3 種類のビットを用いる．ページ内のオブジェク

set を作成しておく．volatile-GC 時に volatile 領域

トが参照されると，reference bit を立てる．また，一上の書き込みが行われていない，non-volatile 領域か定時間おきに reference bit をオフにするページの書ら参照されていないオブジェクトを non-volatile 領域

き込みは，オブジェクトの要素の更新と，初期化時に移動する．volatile-GC を行ってもオブジェクトをに値をセットするものの 2 種類存在する．オブジェ確保できなければ，non-volatile 領域から確保する．

クトの更新は，write bit を立て，確保時の初期化を

non-volatile 領域からオブジェクトを確保するには，

allocate bit を立てる．

non-volatile 領域からコピーしたページ領域上のペー

conditional bit LRU では，最初に write bit と al-ジに一時的に確保され，そのページを non-volatilelocate bit がオフのもので，reference bit がオフのも領域に書き戻す時に non-volatile 領域に反映する．のを選択し，次に reference bit がオンのものをペー

non-volatile 領域からも確保できなくなった場合は，ジアウトする．その次に，allcoate bit がオンのもの

volatile 領域と non-volatile 領域のすべての領域からで，使用率が一定以上のものをページアウトする．そ不要なオブジェクトを解放する full-gc を行う．の次に，write bit がオンのものをページアウトする．

本システムでは，提案手法のために書き込み，生最後に，それ以外をページアウトする．

存期間，マークビットをオブジェクトが持つヘッダに記録している．オブジェクトヘッダは，2bit を non-

3. 3 Mark and classiﬁed compact

volatile 領域で書き込み回数を 3 回まで記録できる

書き込みのあるオブジェクトが分散してページに置値，1bit を volatile-GC を生存したかのフラグ，残りかれていると，最も都合良く書き込みのあるページををマークビットと型情報である．

選択したとしても，書き込みが発生するようになる．
ガベージコレクション時に書き込みのあるページをま3. 2 Conditional bit LRU

とめることで，ページアウトの選択を都合の良い状態

Flash メモリは，書き込みに対して脆弱であるたで行うことができるようになる．ガベージコレクショ

め，LRU のような通常のページアウトアルゴリズム

ンのトレース操作はページングと相性が悪いが，ペーでは短期間で Flash メモリの寿命に到達してしまう．

ジアウトによる書き込みの低減を行うことでこれをそこで，書き込みのあったページを極力避け，ペー相殺できる．オブジェクトをまとめるには Mark andジミスもできるだけ低減するようなページアウトア

compact や Copy GC などの移動を伴うガベージコ

ルゴリズムである，Conditioal bit LRU を提案する．

レクションを併用する必要がある．メモリの無駄を作

る Copy GC は，小さいメモリ空間しかない本システ
ムに向かないため，Mark and compaction をベースとした．そして，Mark and compact に書き込みのあったオブジェクトをまとめる，Mark and classiﬁed

compact を提案する．

Algorithm 1 non-volatile 領域用の compaction algorithm
1: writtenQueue ← 空の Queue
2: noW rittenQueue ← 空の Queue

Mark and classiﬁed compact は，Mark フェーズと Compact フェーズからなる．Mark フェーズでは，ビットマップマーキングを用いて，RAM 上のヘッダ領域にある生存しているオブジェクトに対応するビットを立てる．Compact フェーズは，アルゴリズム 3. 3

3: for page = ﬂash の各ページ do
4:というコンパクションアルゴリズムを改良したものである．まず，オブジェクトの書き込みフラグをもとに，オブジェクトを 2 つのキューに分ける．そして，ページ単位で書き込みができるタイミングで，FlashP ush(writtenQueue, obj)

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

7:

then
8:

P ush(noW rittenQueue, objectP tr)

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

メモリに書き出す．

if alive?(obj) and changed?(obj) then5:にあるような手順で不要なオブジェクトの解放と再配置を行う．このアルゴリズムは，Lisp2 アルゴリズム

for obj = page の各オブジェクト do

13:

if not empty?(writtenQueue) thenwhile doobj ← pop(writtenQueue) ま た はobj ← pop(noW rittenQueue)

4 実験
Conditional bit LRU と Mark and classiﬁed compact が妥当であることを検証するために，Scheme 処
理系を実装し，Flash 書き込み回数とページフォル

14:

if obj が page にかけない then break15:

write(page, obj)

16:

set(addrT able, obj の旧アドレス , objの新アドレス ))ト数を計測した．これらの計測は，表 1 の設定でコンピュータ上の仮想的な環境で行った．vector とし

17: for obj = すべての object doて表現した 16x16 のサイズの画像を 10 回繰り返す18:

k-means 法で減色するプログラムを用いた．

19:

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

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

表1for member = 0tosizeof (object) do

実験の設定

volatile 領域のサイズ

1024byte

ページのサイズ512byteページ数512

ページ領域のサイズ

4

Conditional bit LRU
3. Clean-ﬁrst LRU: Mark and Classiﬁed compact と Clean-ﬁrst LRU
4. Mark and classiﬁed compact: Mark and clas-

提案手法である Mark and classiﬁed compact とsiﬁed compact と LRU

conditional bit LRU といくつかのコンパクション方法とページングアルゴリズムを変えた次の 4 つのも

4. 1 Scheme 処理系

ので比較した．

本研究のために，提案手法のメモリ管理システムを

1. 提 案 手 法: Mark and classiﬁed compact とConditional bit LR
2. Conditional bit LRU: Mark and compact と組み込んだ Scheme 処理系を実装した．M5Stack というデバイスや通常のコンピュータ上で動作する．この Scheme 処理系は，バイトコードインタプリタ方式

の仮想マシンとそのマシンに対するコンパイラから

mutatorGC

mutatorruntimelarge

metadata

なる．継続の実装のために継続渡しスタイルへ変換する方式を採用している．継続の生成を定数時間で行うことができるが，代わりに実行中にクロージャを大量

nursery

matureDRAMに生成するようになっている．

PCM

図3

KG-N

4. 2 実験結果

ト単位での書き込みが可能である点が Flash メモリ

Flash メモリへの書き込み回数を表 2 に示す．提案と異なっている．KG-N と KG-W も書き込み回数を手法が最も書き込み回数が少ないが，言語処理系の削減することを目的にしている．

性質でクロージャや一時的データの作成が多く，確

KG-N は，世代別 GC をベースにしている．図 3 の保と回収が頻発しているため，大きな差が生まれなように，若いオブジェクトに書き込みが多く発生する

かった．ページフォルトの回数を，表 3 に示す．LRU

ため DRAM に割り当て，古くなったオブジェクトをが最もページフォルトが少なく，その次が提案手法

mature に割り当てる．大きいオブジェクトはコピーであった．Flash メモリへの書き込みは，消去操作をにコストがかかるので，最初から PCM の large 領域伴うことや書き込みの時間が読み込みより大きいたに割り当てる．ランタイムのメタデータは，PCM のめ，LRU より増えたミスペナルティよりも提案手法

metadata 領域に置く．

で削減した書き込みの時間コストの方が大きい結果

KG-W も，世代別 GC をベースにしているが，書き込みの監視を行ない，長く生存したオブジェクトをであった．

書き込み回数に応じて Flash メモリか DRAM に振り
表2

実験結果 (書き込み)

分ける．図 4 のように，一定期間生存したオブジェク1:提案手法

26813

2:Conditional bit LRU

27182

3:Clean ﬁrst LRU:

27372

4:Mark and classiﬁed compact

27553

トは DRAM の observer 領域に移動する．observer領域では，オブジェクトの書き込みを監視し，一定期間生存したものの内，書き込みが多いものは PCM のmature に移動し，それ以外を DRAM の mature に移動する．大きいオブジェクトは，KG-N 同様 PCMの large 領域に割り当てるが，書き込み回数を動的

表3

実験結果 (ページフォルト)

1:提案手法45506

2:Conditional bit LRU

46693

3:Clean ﬁrst LRU:

46402

4:Mark and classiﬁed compact:

39254に監視し，書き込みが多いと DRAM の large 領域に移動し，DRAM の large 領域で多く書き込まれた場合は，PCM の large 領域に移動する．KG-W は，KG-N よりも PCM への書き込み回数の削減はできるが，書き込みの監視の分計算時間のオーバーヘッドは大きい．

KG-N/W のアルゴリズムを本研究の対象である

5 関連研究

ﬂash メモリにそのまま当てはめることはできない．

5. 1 KG-N KG-W

なぜなら，この手法は書き込みと読み込みがバイト単PCM など，Flash メモリのように書き込み耐性が位であることを前提としており，書き込み前に消去が低い不揮発性メモリがいくつか存在する．KG-N と必要な記憶デバイスを考慮していないからである．

KG-W [1] は，は PCM と DRAM を併用するメモリ管理手法である．PCM は，書き込みの耐性は Flashメモリほどではないが低いが，消去操作が不要でバイmutatorを追い出すことを遅延させる Reference bit LRU とGC

Mark and compact を改良した Condtional bit LRU
nurseryobservermaturelargeと compact 時に書き込みのあったオブジェクトをまmetadataとめることで Reference bit LRU の効果を最大化すDRAMることを実現した．

GCGCGC mutator

runtime

実験では，処理系と提案手法の相性が悪く十分な効果を示すことができなかった．現在，組み込み向け

maturelarge

metadata

レーターを実装中で，今後実験で再度評価を行う予定

PCM

図4

Ruby 処理系である，Mruby をベースにしたシミュ

KG-Wである．

参 考 文 献6 まとめと今後の課題
本論文では，スモールデバイスの Flash メモリを拡張用に併用することで，高級な機能を利用できるようにする方法を示した．拡張方法は，ソフトウェア的なページング用いた仮想記憶を用いた．Flash メ
モリは書き込みに対して脆弱である問題があるため，書き込みをできるだけ少なくする方式を採用したメ
モリ管理手法を提案した．書き込みのあったページ[1] Shoaib Akram, Jennifer B. Sartor, K. S. M. andEeckhout., L.: Write-rationing Garbage Collectionfor Hybrid Memories., ACM SIGPLAN Conference
on Programming Language Design andImplementation, (2018).
[2] Vincent St-Amour, M. F.: PICOBIT: A Compact Scheme System for Microcontrollers, IFL’09:
Proceedings of the 21st international conference onImplementation and application of functional languages, (2009).