DSMSのオペレータ単位コミットによる優先度逆転時間削減 Priority

DEIM Forum 2015 E4-5
DSMS のオペレータ単位コミットによる優先度逆転時間削減
勝沼
聡†∗
渡辺 陽介††
本田
晋也†
高田
広章††
† 名古屋大学大学院情報科学研究科 〒 464–8601 名古屋市千種区不老町
†† 名古屋大学未来社会創造機構
∗ 日立製作所中央研究所
E-mail: †{katsunuma,honda,hiro}@ertl.jp, ††[email protected]
あらまし 車載システムの複雑化に伴う開発コスト削減を目的とし，車載システムへの DSMS の適用を検討している．
車載システムへの DSMS 適用時にクエリ間で処理を共有した場合，優先度が逆転する時間（優先度逆転時間）が大き
くなる．そこで我々が提案したクエリコンテキスト共有方式ではクエリの処理過程で必要となるデータ（コンテキス
ト）をクエリ間で共有し，処理を引き継ぐことで，優先度逆転時間を削減しつつクエリ処理最適化を実現する．しか
しクエリコンテキスト共有方式では，クエリ間でコンテキストを共有する際にロックを取得するためオーバヘッドが
発生する．そこで本稿では，ロックの取得頻度を最適化することにより，処理時間及びメモリ使用量，優先度逆転時
間の削減を両立する，クエリコンテキスト共有方式の実現手法を提案する．提案方式を評価した結果，クエリ間で処
理を共有する場合と比較し優先度逆転時間を大幅に削減しつつ，共有しない場合と比較し処理時間，メモリ使用量を
それぞれ 32% ，46% 削減できることを確認した．
キーワード
データストリーム管理システム，クエリ処理最適化，リアルタイム，車載システム，RTOS
Priority Inversion Time Reduction by Operator-Level Commit of DSMS
Satoshi KATSUNUMA†∗ , Yousuke WATANABE†† , Shinya HONDA† , and Hiroaki TAKADA††
† Graduate School of Information Science, Nagoya University Furo-cho, Chikusa-ku, Nagoya, 464–8601 Japan
†† Institute of Innovation for Future Society, Nagoya University
∗ Central Research Lab., Hitachi Ltd.
E-mail: †{katsunuma,honda,hiro}@ertl.jp, ††[email protected]
1. は じ め に
車載システムでは，アプリケーションの生産性向上に向け，
より，複数のアプリケーション向けのクエリの処理を一度だけ
実行し，その処理結果を各アプリケーションに渡すクエリ処理
共有方式により処理やメモリ使用量を低減する．しかしクエリ
AUTOSAR がデファクトとなり，プラットフォームの導入が
処理共有方式により高優先度の処理よりも低優先度の処理が
進んでいる．AUTOSAR ではソフトウェアコンポーネントの
実行される優先度逆転が発生しうる．一般的に車載システムで
インタフェースを共通化し，様々な ECU で共通のアプリケー
は RTOS(Real-Time Operating System) が搭載され，アプリ
ションを動かせるようにする．我々が提案している車載データ
ケーションは RTOS のタスクに割り当てられる．そして各タス
統合 PF [1] [2] [3] では，AUTOSAR 上で，様々な ECU で共通
クは優先度が設定され，優先度の高いタスクから順に実行され
するデータ処理を定義し，そのデータ処理を様々なアプリケー
る．そのためクエリ処理共有方式を適用した場合，優先度が異
ションが利用可能とする．車載データ統合 PF ではデータ処理
なる複数アプリケーション向けクエリに対して高優先度のアプ
をデータストリーム管理システム（以下，DSMS）[5] [6] [7] のク
リケーションと同じ優先度を割り当てる必要がある．しかしそ
エリとして記述する．そして同一 ECU 上の複数のアプリケー
の場合，クエリの処理が他のタスクの実行を妨げるため優先度
ションから呼ばれるクエリの処理を共有することで，リソース
逆転が発生しうる．
制約が厳しい車載システム上で処理量を低減することが期待さ
れている．
汎用システム向けの DSMS ではクエリ処理最適化 [7] [8] に
そこで優先度逆転時間を減らしつつ，処理やメモリの最適化
を実現する，クエリコンテキスト共有方式 [9] を先行研究で提案
した．クエリコンテキスト共有方式では，複数アプリケーショ
ン向けのクエリを重複させ，各アプリケーションとクエリを同
の場合に，同一のクエリを各々のアプリケーションと同一のタ
一タスクに割り当て，同一優先度で実行することで優先度逆転
スクに重複して割り当てる方式が挙げられる．図 1(a1) では，
時間を減らす．そして異なるタスクに割り当てられたクエリに
高優先度，低優先度の二つのアプリケーションがクエリを利用
対して，クエリの処理過程で必要となるデータ（以下，コンテ
するため，クエリを重複させ，各々のアプリケーションと同一
キスト）を共有し，クエリ間で処理を引き継ぐことで，処理時
のタスクにクエリを割り当てる．この場合，図 1(a2) に示すよ
間及びメモリ使用量の削減を実現する．
うに，0∼50ms など，高優先度，低優先度の二つのアプリケー
先行研究ではクエリコンテキスト共有方式のコンセプトを示
したが，具体的な実現方法については検討できていない．クエ
リコンテキスト共有方式ではクエリのコンテキストを共有す
ションを実行される場合，クエリが複数回，実行される．その
ため処理時間及びメモリ使用量が大きくなる．
2. 3 クエリ処理共有
るために，共有メモリ上のコンテキストを更新するコミットが
2. 3. 1 処 理 概 要
必要になる．しかしコミット処理では，排他制御を行うために
クエリ処理共有方式では，同じクエリを重複して実行するこ
ロックの取得が必要となる．そのためコンテキストを頻繁に更
とを防ぐため，DSMS のクエリを一度だけ実行し，そのクエ
新するとロックの取得回数が増大し処理オーバヘッドが大きく
リの処理結果を複数のアプリケーションに配信する．処理タイ
なる．またコンテキストを纏めて更新すると，ロック取得時間
ミングが異なるクエリの処理共有化のため，渡辺らの方式 [8]
が長くなるため他のタスクの実行が妨げられ優先度逆転が発生
では全てのアプリケーションに対しクエリの処理結果を配信で
する．
きるタイミングを設定する．またクエリの優先度についても，
そこで本稿では処理時間，メモリ使用量と，優先度逆転時間
全てアプリケーションに対して配信できるように，アプリケー
の削減を両立することを目的とし，クエリコンテキスト共有方
ションの中で最も高い優先度を設定する必要がある．例えば，
式の実現手法を提案する．提案方式では，ロックの取得頻度の
図 1(b1) は，高優先度，低優先度の二つのアプリケーションが
過度な増加を抑えるため，コミット時のみロックを取得し，コ
クエリを利用する場合を示す．この場合，クエリの優先度を高
ンテキストを纏めて更新する．またデータを処理する度にコ
とし，また 100ms，50ms 周期のアプリケーションに配信でき
ミットを実行するデータ単位コミットと，複数データの処理に
るよう，動作周期を 50ms とする．
対して纏めてコミットを実行するオペレータ単位コミットの二
2. 3. 2 優先度逆転問題
つの方式を提案し，利用ケースに応じて使い分け可能とする．
クエリ処理共有方式により，クエリと，その処理結果を配信
本稿の構成は以下の通りである．まず 2 節で共通するクエリ
するアプリケーションに対して異なる優先度が割り当てられる
の共有化について従来技術や，車載システムにおける要件を述
ため，優先度逆転が発生する可能性がある．図 1(b2) に示す
べ，3 節で我々の先行研究であるクエリコンテキスト共有方式
ように，スケジューリング方法としては，まず高優先度のクエ
の課題を述べる．そして 4 節でクエリコンテキスト共有方式の
リが実行され，その後にクエリの処理結果を利用するアプリ
実現手法を説明し，5 節でその評価について述べる．最後に 6
ケーションが実行される．しかし 50ms から 100ms の間には，
節でまとめと今後の課題を述べる．
100ms 周期の高優先度アプリが実行されないため，クエリの処
2. 共通クエリの共有化
本節では，本稿で対象とする共通クエリの共有化に関する従
来手法と，車載システム適用要件を述べる．
理結果を低優先度アプリのみが利用するにも関わらず，クエリ
は高い優先度で実行される．そのためクエリの処理 (図 1(b2)A)
により，中優先度アプリの実行 (図 1(b2)B) が妨げられ，優先
度逆転が発生する．
2. 1 クエリのタスクへの割り当て
2. 4 車載システム適用に向けた性能要件
車載システムでは一般的に RTOS を搭載し，RTOS を用い
前述のように，共通するクエリに対して処理を共有しない場
てスケジューリングを行う．すなわち各アプリケーションを
合には，処理時間，メモリ使用量が大きくなり，またクエリの
RTOS のタスクに割り当て，異なる優先度や周期でアプリケー
処理を共有する場合には優先度逆転時間が大きくなる．優先度
ションを実行する．車載システムに DSMS を適用する場合に
逆転時間が大きくなるとデッドラインミスが増えるため，リア
も，DSMS も車載アプリケーションと同様に RTOS 上で実行
ルタイム性が求められる車載システムに適用する場合には，優
し，DSMS の各クエリに対し，優先度，周期を設定し，RTOS
先度逆転時間をデッドラインに影響がない範囲に抑える必要が
のタスクとして実行する．そしてクエリが単一のアプリケー
ある (要件 1)．また車載システムはハードウェアのサイズなど
ションが利用する場合には，リアルタイム性を保持するために，
の物理的な制約や，価格の制約から小容量のメモリや低クロッ
クエリとアプリケーションと同一の RTOS のタスクに割り当
クの CPU が搭載される．そのため低クロックの CPU でクエ
てることで，同一優先度，周期で実行する [15]．以下では，複
リの処理を実行できるよう処理時間を抑え (要件 2)，また小容
数アプリケーションで共通するクエリを利用する場合の，クエ
量メモリ上に搭載できるようメモリ使用量を抑える必要がある
リの共有化方法について述べる．
(要件 3)．
2. 2 共 有 な し
車載システムへの DSMS 適用時に，各アプリケーションの
優先度を変えないために，複数アプリケーション向けのクエリ
3. クエリコンテキスト共有方式の課題
本節では，我々が先行研究で提案したクエリコンテキスト共
ࢱࢫࢡ
100ms࿘ᮇ
ࢱࢫࢡ
䜽䜶䝸
㧗ඃඛᗘ䜰䝥䝸
䠇䜽䜶䝸
䜻䝳䞊 䜸䝨䝺䞊䝍
Filter
Map
Aggre
gate
ɲ
㧗ඃඛᗘ
࢔ࣉࣜ
୰ඃඛᗘ䜰䝥䝸
50ms࿘ᮇ
䠖䜽䜶䝸
పඃඛᗘ䜰䝥䝸
䠇䜽䜶䝸
୰ඃඛᗘ
䜰䝥䝸
䠖䜰䝥䝸
A
ϬŵƐ
ϱϬŵƐ
ϭϬϬŵƐ
50ms࿘ᮇ
Filter
Map
Aggre
gate
ɴ
పඃඛᗘ
䜰䝥䝸
(a1) ඹ᭷࡞ࡋ㸸ࢱࢫࢡ๭ࡾᙜ࡚
(a2) ඹ᭷࡞ࡋ㸸ࢫࢣࢪ࣮ࣗࣜࣥࢢ
100ms࿘ᮇ
ɲнɴ
㧗ඃඛᗘࠊ50ms࿘ᮇ
㧗ඃඛᗘ
࢔ࣉࣜ
ඃඛᗘ㏫㌿᫬㛫
䜽䜶䝸;㧗ඃඛᗘͿ
A
ฎ⌮⤖ᯝ฼⏝
50ms࿘ᮇ
Filter
Map
Aggre
gate
୰ඃඛᗘ
䜰䝥䝸
㧗ඃඛᗘ䜰䝥䝸
50ms࿘ᮇ
୰ඃඛᗘ䜰䝥䝸
పඃඛᗘ
䜰䝥䝸
పඃඛᗘ䜰䝥䝸
ϬŵƐ
(b1) ฎ⌮ඹ᭷㸸ࢱࢫࢡ๭ࡾᙜ࡚
ϱϬŵƐ
ϭϬϬŵƐ
(b2) ฎ⌮ඹ᭷㸸ࢫࢣࢪ࣮ࣗࣜࣥࢢ
100ms࿘ᮇ
Filter
Map
Aggre
gate
㧗ඃඛᗘ
࢔ࣉࣜ
50ms࿘ᮇ
୰ඃඛᗘ
䜰䝥䝸
50ms࿘ᮇ
Filter
Map
Aggre
gate
పඃඛᗘ
䜰䝥䝸
ฎ⌮ᘬ⥅䛞
ࢡ࢚ࣜ ࢔ࣉࣜ
㧗ඃඛᗘ࢔ࣉࣜ
㸩ࢡ࢚ࣜ
ඃඛᗘ㏫㌿ᅇ㑊
ฎ⌮⤖ᯝ฼⏝
୰ඃඛᗘ࢔ࣉࣜ
B
పඃඛᗘ࢔ࣉࣜ
㸩ࢡ࢚ࣜ
A
0ms
䝁䞁䝔䜻䝇䝖
(c1) ࢥࣥࢸ࢟ࢫࢺඹ᭷㸸ࢱࢫࢡ๭ࡾᙜ࡚
50ms
100ms
150ms
(c2) ࢥࣥࢸ࢟ࢫࢺඹ᭷㸸ࢫࢣࢪ࣮ࣗࣜࣥࢢ
図 1 共通クエリの共有化
有方式とその課題について述べる．
3. 1 方
針
クエリコンテキスト共有方式では，クエリの処理を共有せず，
コンテキストを共有することで，優先度逆転時間を削減しつつ，
処理やメモリの最適化を実現する．クエリコンテキスト共有方
式では優先度逆転を回避するために，アプリケーションとクエ
とはなく処理効率化を実現できる．
3. 2 動 作 概 要
クエリコンテキスト共有方式の動作概要について，下記で述
べる．
•
コンテキスト更新
コンテキストとは，オペレータの入出力キューや，特定期
リを同じタスクに割り当て，同一優先度，動作周期で実行する．
間データを格納するウィンドウ，Aggregate 計算に用いるオペ
図 1(c1) では高優先度，低優先度のアプリケーションが同じク
レータステート等，クエリの処理に必要となるデータである．
エリの処理結果を利用する場合であり，それぞれのアプリケー
コンテキストをタスク間で共有するために，オペレータ実行後
ションとクエリを同一のタスクに割り当てる．そして, 図 1(c1)
のコミットによりコンテキストを更新する．図 2(a) では低優先
に示すオペレータ間の入出力キューなど，異なるタスクに割り
度タスクにおいて，Filer 及び Map オペレータ後のコミットに
当てられたクエリのコンテキストを共有し，タスク切り替え時
より，それぞれその処理結果であるデータ a0，b0 及び a1，b1
に，他のタスクに割り当てられたクエリに処理を引き継ぐこと
を出力キューに格納することで，コンテキストを更新する．
で，処理時間やメモリ使用量を削減する．
•
処理結果利用
図 1(c2) は高優先度，低優先度アプリがクエリの処理結果を
クエリコンテキスト共有方式では，タスク切り替え後，コン
利用する場合のスケジューリングを示す．クエリの処理を共有
テキストを共有している他タスクのアプリケーションが，クエ
する場合とは異なり，時刻 50∼100ms において，クエリ (図
リの処理結果を利用する．図 2(b) では低優先度タスクにおい
1(c2)A) は低優先度アプリと同じタスクで低い優先度で実行さ
て，Aggregate オペレータの処理完了後，コミットにより処理
れるため，中優先度アプリ (図 1(c2)B) の実行を妨げられるこ
1 ．
結果であるデータ a2，b2 を出力キューに格納する (図 2(b)⃝)
となく，優先度逆転を回避することができる．また時刻 100∼
2 ，同
その後，高先度のタスクへ切り替わった際に (図 2(b)⃝)
150ms のように，低優先度のタスクが先に実行される場合に
タスクでクエリを処理することなく，出力キューに格納された
も，そのクエリの処理を，低優先度から高優先度のタスクに引
3 ．
データ a2，b2 を，アプリケーションが利用する (図 2(b)⃝)
き継ぐことができるため，同じクエリの処理を複数実行するこ
•
処理引継ぎ
㧗ඃඛᗘ
ࢱࢫࢡ
Filter
పඃඛᗘ
ࢱࢫࢡ
Filter
Filter
ࢥ࣑ࢵࢺ
ࢥࣥࢸ࢟ࢫࢺ
RQ࣓ࣔࣜ
D
E
Map
Aggre
gate
㧗ඃඛᗘ
䜰䝥䝸
Map
Aggre
gate
పඃඛᗘ
࢔ࣉࣜ
ࢥ࣑ࢵࢺ
4. 2 方
Aggre
gate
Map
ղࢱࢫࢡ
ษࡾ᭰࠼
ճ
Filter
E
D
リコンテキスト共有方式の実現手法を提案する．
データ/オペレータ単位のコミット
クエリにおける処理の最小単位は，単一データに対する単一
オペレータの処理である．そこで最小単位でのコミット，すな
䝁䝭䝑䝖
わちデータをオペレータで処理する度にコミットを実行する
E D
E D
E D
針
前述の課題をふまえ，本稿では下記に示す方針に従ったクエ
•
పඃඛᗘ
䜰䝥䝸
Aggre
gate
Map
ձ
ࢥࣥࢸ࢟ࢫࢺ
RQ࣓ࣔࣜ
㧗ඃඛᗘ
䜰䝥䝸
ࢥ࣑ࢵࢺ᏶
పඃඛᗘ
ࢱࢫࢡ
のためロック取得時間が大きくなると優先度逆転時間 (要件 1)
きくなることでメモリ使用量 (要件 3) が大きくなる．
(a) ࢥࣥࢸ࢟ࢫࢺ᭦᪂
Filter
度のタスクへの切り替えが妨げられ優先度逆転が発生する．そ
モリに一時的に格納する必要があるため，ロック取得時間が大
䝇䝖䝸䞊䝮䜻䝳䞊
㧗ඃඛᗘ
ࢱࢫࢡ
のタスクはロックを取得中，高優先度で実行するため，中優先
が大きくなる．また共有メモリの更新前にコンテキストを別メ
E D
E D
で最も高い優先度で実行する．例えば図 1(c1) では，低優先度
データ単位コミット及び，複数データに対するオペレータ処理
䝇䝖䝸䞊䝮䜻䝳䞊
に対して纏めてコミットを実行するオペレータ単位コミットを
(b) ฎ⌮⤖ᯝ฼⏝
㧗ඃඛᗘ
ࢱࢫࢡ
Filter
ղࢱࢫࢡ
ษࡾ᭰࠼
ᮍࢥ࣑ࢵࢺࡢ
࣮࢜࣌ࣞࢱ
పඃඛᗘ
ࢱࢫࢡ
Filter
提案する．データ単位コミットではロックの取得時間が小さく，
Aggre
gate
Map
ճ
పඃඛᗘ
䜰䝥䝸
レータ単位コミットではロックの取得頻度が少なくなるため，
優先度逆転時間やメモリ使用量が大きくなる反面，処理時間が
䝁䝭䝑䝖
ࢥࣥࢸ࢟ࢫࢺ
RQ࣓ࣔࣜ
従って優先度逆転時間やメモリ使用量が小さくなるが，ロック
の取得頻度が多くなり処理時間が大きくなる．一方で，オペ
ձ
Aggre
gate
Map
㧗ඃඛᗘ
䜰䝥䝸
小さくなる．
E
D
E D
E D
E D
䝇䝖䝸䞊䝮䜻䝳䞊
(c) ฎ⌮ᘬ⥅ࡂ
図2
クエリコンテキスト共有方式の動作概要
•
コミット時に纏めてコンテキスト更新
コミットから次のコミットまでに共有メモリ上の複数のデー
タの更新が必要になる．例えば Aggregate オペレータでは，出
力キュー，ウィンドウ，オペレータステートの更新が必要にな
る．そのためコンテキストを逐一，更新した場合，ロックの取
クエリの処理中に，他のタスクに処理を引き継ぐ際には，最
後のコミットで更新したコンテキストを読み込み，コミットが
完了した次のオペレータを最初から実行する．図 2(c) では，低
1 ，
優先度のタスクで Aggregate オペレータを実行中 (図 2(c)⃝)
2 ．この場
高優先度のタスクに切り替わる場合である (図 2(c)⃝)
合，完了した Map オペレータの出力結果のデータ a1，b1 を
用いて，Aggregate オペレータの最初から処理を開始する (図
3 ．
2(c)⃝)
4. クエリコンテキスト共有方式の実現手法
我々の先行研究ではクエリコンテキスト共有方式のコンセプ
トを提案した．本節では，性能要件を考慮したクエリコンテキ
スト共有方式の実現手法を述べる．
4. 1 実現に向けた課題
クエリコンテキスト共有方式の実現に向けた課題を述べる．
クエリコンテキスト共有方式では，共有メモリ上のコンテキス
トを更新するためにロックを取得する必要がある．そのため頻
繁にコンテキストを更新すると，ロックの取得回数が増え，処
理時間 (要件 2) が大きくなる．また纏めてコンテキストを更新
すると，ロックの取得時間が大きくなる．ロック取得中，コン
テキストを共有する他のタスクに切り替わらないようにするた
め，RTOS の制御により，コンテキストを共有するタスクの中
得頻度が過度に増加する．またタスク切り替えが発生した場合
には，ロールバックにより一つ前のコミット時点のコンテキス
トに戻す必要があるが，ロールバック時にはコンテキストを変
更するためロックの取得が必要になり，優先度逆転が発生する．
そのため提案方式ではコミット前はタスク専用のメモリにコン
テキストを格納し，コミット時にロックを取得し纏めて共有メ
モリ上のコンテキストを更新する．
4. 3 動
作
クエリコンテキスト共有方式の動作について説明する．図 3
に示すように，まずオペレータ単位コミットについて説明し，
続いてデータ単位コミットついて説明する．
4. 3. 1 タスク切り替えなし
まずクエリの実行中にタスク切り替えが発生しない場合の動
作 (図 3(a1)(a2)) について説明する．
•
タスク専用メモリの確保
まずオペレータの実行前に，次のコミットまでに必要となる
1 では Filter，Map，Agタスク専用メモリを確保する．図 3⃝
gregate オペレータ開始前のコミットにおいて低優先度タスク
用のメモリを確保する．
•
オペレータ実行中のタスク専用メモリへの書き込み
オペレータ実行中，ウィンドウや出力キュー等に格納する
データは，共有メモリではなくタスク専用メモリに書き込む
2 ．タスク専用メモリは，他のタスクと共有しない
(図 3(a1)⃝)
ZdK^
ฎ⌮
䐡
䝻䝑䜽
ྲྀᚓ
㧗ඃඛᗘ
䝍䝇䜽ฎ⌮
పඃඛᗘ
䝍䝇䜽ฎ⌮
䝻䝑䜽
㛤ᨺ
䝻䝑䜽
㛤ᨺ
䝻䝑䜽
ྲྀᚓ
䝻䝑䜽
㛤ᨺ
䝻䝑䜽
ྲྀᚓ
㧗ඃඛᗘ
ࢱࢫࢡ
Filter
Map
Aggre
gate
㧗ඃඛᗘ
䜰䝥䝸
పඃඛᗘ
ࢱࢫࢡ
Filter
Map
Aggre
gate
పඃඛᗘ
䜰䝥䝸
䐠
&ŝůƚĞƌ
䝁䝭䝑䝖
䐟
䐠
䝯䝰䝸
᭩㎸䜏
☜ಖ
䝍䝇䜽ᑓ⏝
䝯䝰䝸
DĂƉ
䝁䝭䝑䝖 ŐŐƌĞŐĂƚĞ 䝁䝭䝑䝖 䜰䝥䝸
䝯䝰䝸
㛤ᨺ ᭩㎸䜏
☜ಖ
&ŝůƚĞƌ⏝
䝯䝰䝸
㛤ᨺ ᭩㎸䜏
☜ಖ
DĂƉ⏝
䐢
᭦᪂
䝯䝰䝸
㛤ᨺ
ࢥࣥࢸ࢟ࢫࢺ
RQඹ᭷
࣓ࣔࣜ
䐣
᭦᪂ ฎ⌮⤖ᯝ
ㄞ㎸䜏
(a1) ࢱࢫࢡษࡾ᭰࠼࡞ࡋ㸸ࢩ࣮ࢣࣥࢫ
ZdK^
ฎ⌮
㧗ඃඛᗘ
䝍䝇䜽ฎ⌮
୰ඃඛᗘ
䝍䝇䜽ฎ⌮
పඃඛᗘ
䝍䝇䜽ฎ⌮
䝻䝑䜽
㛤ᨺ
䝻䝑䜽
ྲྀᚓ
䐣䝍䝇䜽
ษ᥮䛘
䐟
ᐇ⾜ྍ⬟
䝻䝑䜽
ྲྀᚓ
䐧
䝻䝑䜽 䝍䝇䜽
㛤ᨺ ษ᥮䛘
䝻䝑䜽
ྲྀᚓ䠃
㛤ᨺ
䐦
䐡䜰䝥䝸
䐠㧗
ඃඛᗘ
DĂƉ
$JJUH
JDWH
䝁䝭䝑䝖
䐤
䐢
䐥
᭩㎸䜏䝯䝰䝸 ᭩㎸䜏
☜ಖ
᭦᪂
ࢥ࣑ࢵࢺ
E D
䜻䝳䞊
䝯䝰䝸
㛤ᨺ
㧗ඃඛᗘ
ࢱࢫࢡ
Map
Filter
յࢱࢫࢡ
ษࡾ᭰࠼
పඃඛᗘ
ࢱࢫࢡ
Filter
ฟຊ࣮࢟ࣗ
࢘࢕ࣥࢻ࢘
Map
Aggre
gate
㧗ඃඛᗘ
䜰䝥䝸
䐥
୰ඃඛᗘ
䜰䝥䝸
Aggre
gate
పඃඛᗘ
䜰䝥䝸
ࢱࢫࢡᑓ⏝࣓ࣔࣜ
䐢
䐨
᭩㎸䜏
᭦᪂
䝯䝰䝸
㛤ᨺ
D
a
䐪
ฎ⌮
䐩᭦᪂ ⤖ᯝ
䛧䛺䛔 ㄞ㎸䜏
(b1) ࢱࢫࢡษࡾ᭰࠼࠶ࡾ㸸ࢩ࣮ࢣࣥࢫ
40
a
b
㧗ࢱࢫࢡ$JJU⏝
40
E D
50
E D
䐦 ࢥ࣑ࢵࢺ
ࢥࣥࢸ࢟ࢫࢺ
RQඹ᭷࣓ࣔࣜ
䝁䞁䝔䜻䝇䝖
ඹ᭷䝯䝰䝸
䐣
E D
పࢱࢫࢡ$JJU⏝
ప䝍䝇䜽͕ ŐŐƌ⏝
㧗䝍䝇䜽͕ŐŐƌ⏝
DĂƉ⏝
䝁䝭䝑䝖
䜰䝥䝸
ŐŐƌĞŐĂƚĞ
䝯䝰䝸
㛤ᨺ
☜ಖ
E D
(a2) ࢱࢫࢡษࡾ᭰࠼࡞ࡋ㸸ࢹ࣮ࢱࣇ࣮ࣟ
ŐŐƌĞŐĂƚĞ 䝁䝭䝑䝖 䜰䝥䝸
ඃඛᗘ
㏫㌿
䝯䝰䝸
㛤ᨺ ᭩㎸䜏
☜ಖ
䝍䝇䜽ᑓ⏝
䝯䝰䝸
䝍䝇䜽
ษ᥮䛘
40
50
ධຊ࣮࢟ࣗ
䜻䞊 ᖹᆒ
࣮࢜࣌ࣞࢱ a
30
ࢫࢸ࣮ࢺ b
60
䝁䞁䝔䜻䝇䝖
ඹ᭷䝯䝰䝸
a
b
䐢
ŐŐƌ⏝
᭦᪂
ࢱࢫࢡᑓ⏝
࣓ࣔࣜ
పࢱࢫࢡ$JJU⏝
(b2) ࢱࢫࢡษࡾ᭰࠼࠶ࡾ㸸ࢹ࣮ࢱࣇ࣮ࣟ
図 3 クエリコンテキスト共有方式 (オペレータ単位コミット) の動作
メモリであるため，更新時にもロックの取得は不要である．
2 では Aggregate オペレータにおいて，データ a1，
図 3(a2)⃝
オペレータのステートに格納する．また同じくタスク専用メモ
リ上にある Aggregate オペレータの処理結果であるデータ a2，
b1 を，共有メモリにある入力キューから読み出して，そのデー
b2 についてもそのアドレスを出力キューに格納する．このよう
タ a1，b1 をタスク専用メモリ上のウィンドウに格納し，また
にしてクエリの全てのオペレータの処理が完了すると，アプリ
平均速度を算出しその算出結果を同じくタスク専用メモリに
ケーションに制御を移し，アプリケーションがクエリの処理結
格納する．そして出力キューに格納する処理結果であるデータ
5 ．
果を読込む (図 3(a2)⃝)
a2，b2 もオペレータ実行中はタスク専用メモリに格納する．
•
コミット時のコンテキスト更新
4. 3. 2 コンテキストを共有しないタスクへの切り替え
コンテキストを共有しないタスクへの切り替えが発生した
オペレータ実行後にコミットを実行する．そしてコミットに
1 ∼⃝)
3 について説明する．クエリの実
場合の動作 (図 3(b1)⃝
3 ，タスク専用メモリに書き
おいてロックを取得し (図 3(a1)⃝)
行中，コンテキストを共有していない他のタスクが実行可能
込まれた処理結果を，共有メモリ上のコンテキストに反映す
1 となった場合，実行中のタスクよりも優先度が高
(図 3(b1)⃝)
4 ．その際に，タスク専用メモリから共有メモリ
る (図 3(a1)⃝)
ければ RTOS の制御により，タスク切り替えが発生する (図
にデータをコピーするのではなく，タスク専用メモリにおける
3 ．ただしコミット中はロックを取得しているため (図
3(b1)⃝)
データの書き込み先のアドレスを，共有メモリ上のウィンド
2 ，コンテキストを共有するタスクの中で最高優先度の
3(b1)⃝)
ウや出力キューにコピーする．これによりコミットにおいて，
タスクと同じ優先度でタスクを実行するため，優先度逆転が起
データをコピーが不要となり優先度逆転時間及び処理時間を削
き，タスク切り替えが発生しない場合がある．
減する．
4 では Aggregate オペレータのコミットにおいて，
図 3(a2)⃝
例えば図 3(b1) に示す中優先度タスクは，低優先度タスクよ
りも優先度は高いが，高優先度タスクよりも優先度が低い．そ
タスク専用メモリに格納したデータ a1，b1 のアドレスをウィン
のため低優先度タスクでコミット中はロックを取得することで，
ドウに格納し，また平均速度の算出結果のアドレスを Aggregate
中優先度タスクよりも高い優先度で実行される．そのため中優
ZdK^
ฎ⌮
50ms࿘ᮇ
䝻䝑䜽
ྲྀᚓ
㧗ඃඛᗘ
䝍䝇䜽ฎ⌮
పඃඛᗘ
䝍䝇䜽ฎ⌮
䝻䝑䜽
㛤ᨺ
䝻䝑䜽
ྲྀᚓ
䝻䝑䜽
㛤ᨺ
㧗ඃඛᗘ
࢔ࣉࣜ
㌴㌴㛫
㏻ಙࢹ࣮ࢱ
ŐŐƌ͕Ăϭ 䝁䝭䝑䝖 ŐŐƌ͕ďϭ 䝁䝭䝑䝖
䐟䝯䝰䝸
㛤ᨺ ᭩㎸䜏
☜ಖ
䝍䝇䜽
ᑓ⏝䝯䝰䝸
䐠
䝯䝰䝸 ᭩㎸䜏
㛤ᨺ
☜ಖ
ప䝍䝇䜽͕
ŐŐƌ͕Ăϭ⏝
䐢᭦᪂
データ単位コミット
௚㌴㉮⾜
᝟ሗ
Filter
50ms࿘ᮇ
୰ඃඛᗘ
䜰䝥䝸
Union
100ms࿘ᮇ
Join
䝯䝰䝸
㛤ᨺ
䝁䞁䝔䜻䝇䝖
図4
Map
పඃඛᗘ
䜰䝥䝸
図5
ప䝍䝇䜽͕
ŐŐƌ͕ďϭ⏝
䐠᭦᪂
ඹ᭷䝯䝰䝸
ࢡ࢚ࣜ
Aggre
gate
評価に用いるクエリ
Aggregate オペレータでデータ b1 を処理し，コンテキストの
4 ．
更新を実施する (図 4⃝)
5. 評
価
先度タスクへの切り替えは起きずに，ロック開放後に実行が開
5. 1 評価方法，環境
始されるため優先度逆転が発生する．
クエリコンテキスト共有方式について，優先度逆転時間，処
4. 3. 3 コンテキストを共有するタスクへの切り替え
理時間，メモリ使用量を評価した．比較対象は，従来手法であ
コンテキストを共有しているタスクへの切り替えが発生した
るクエリ処理共有方式及び，共有なしの場合である．またクエ
4 ∼12
場合の動作 (図 3(b1)⃝
⃝，(b2)) について説明する．
4. 3. 4 高優先度タスクへの切り替え
コミット前のコンテキストはタスク専用メモリに格納され，
リコンテキスト共有方式についてはオペレータ及びデータ単位
コミットを比較した．
評価環境としては，ハードウェアは Altera 社の NIOS II プ
共有メモリは更新されない．そのためオペレータ実行中 (図
ロセッサ・ボード 3C25 を利用した．OS は車載システム向け
4 に低優先度から高優先度にタスクが切り替わった場合
3(b1)⃝)
RTOS TOPPERS/ATK2 を搭載し，RTOS 上に車載システム
5 ，切り替わり先のタスクで，そのタスク専用のメ
(図 3(b1)⃝)
向け DSMS を動作させた．評価に用いるクエリは，図 5 に示
6 ，コミットが完了したオペレータの
モリを確保し (図 3(b1)⃝)
す車々間通信データから他車走行情報を算出するクエリであ
次のオペレータを最初から実行する．
り，クエリの処理結果を高優先度，低優先度の二種類のアプリ
図 3(b2) は低優先度から高優先度タスクが切り替わる際の動
ケーションに配信する．高優先度，低優先度アプリケーション
作を示す．切り替え前の低優先度タスクでは，Map オペレータ
は各々100ms，50ms 周期で動作し，その他に中優先度アプリ
のコミットが完了したが，Aggregate オペレータを処理中であ
ケーションが 50ms 周期で動作する．
4 ．この場合には，高優先度タスクはコミット時
る (図 3(b2)⃝)
5. 2 評 価 項 目
点のコンテキストを用いて，Aggregate オペレータを最初から
評価項目は優先度逆転時間，処理時間，メモリ使用量である．
7 ．その際に高優先度タスク用の専用メモ
処理する (図 3(b2)⃝)
優先度逆転時間は，中優先度のアプリケーションが低優先度の
リを確保し，そのメモリ領域に書き込む．そしてコミット時に
アプリケーションにより実行が妨げられる時間の最悪値を評価
8 ．
共有メモリ上のコンテキストを更新する (図 3(b2)⃝)
した．処理時間は，50ms 周期における，クエリの処理時間の
4. 3. 5 低優先度タスクへの切り替え
最悪値を評価した．また車載システムを想定した評価環境では
高優先度から低優先度タスクへの再切り替え時には，切り替
ヒープ領域などの動的に割り当てられるメモリ領域は存在しな
え前に実行中のオペレータの処理を継続する．例えば図 3(b1)
いため，メモリ使用量は，静的に割り当てられるメモリ領域の
9 ，低優先
では，低優先度タスクへの再切り替え後 (図 3(b1)⃝)
み評価した．
度タスクでは Aggregate オペレータを継続して処理する．そし
表1
評価結果
てオペレータ実行終了後，他タスクが共有メモリを更新したこ
項目
Op 単位
Data 単位
処理共有
共有なし
とをコミット時に検出し，共有メモリにコンテキストを書き込
優先度逆転時間
48us
34us
20ms
17us
29ms
35 ms
22ms
43ms
むことなくクエリの処理を終了する (図 3(b1)11
⃝)．そして低優
処理時間
先度タスクのアプリケーションは，高優先度タスクで更新した
メモリ使用量
139KByte 137KByte 131KByte 245KByte
コンテキストに含まれる処理結果を読み込む (図 3(b1)12
⃝)．
4. 3. 6 データ単位コミット
5. 3 評 価 結 果
データ単位コミットでは，オペレータ単位コミットとは異な
表 1 に示す，優先度逆転時間，処理時間，メモリ使用量の評
り，オペレータでデータを処理する度に，ロックを取得し共有
価結果を述べる．
メモリ上のコンテキストを更新する．図 4 では，Aggregate オ
5. 3. 1 優先度逆転時間
ペレータでデータ a1 の処理開始前にタスク専用メモリを確保し
クエリコンテキスト共有方式 (オペレータ単位コミット) にお
1 ，処理完了後，コミット処理でコンテキストを更新す
(図 4⃝)
ける優先度逆転時間は 48us となった．クエリコンテキスト共
2 ．そして新たにタスク専用メモリを確保し (図 4⃝)
3 ，
る (図 4⃝)
有方式では，コミット時にロックを取得し，タスク専用メモリ
から共有メモリへアドレスをコピーするため，そのロック取得
周期は一般的には 10ms 以上であり，許容できる優先度逆転時
時間が優先度逆転時間となる．共有しない場合の優先度逆転時
間に収まっている言える．従ってクエリコンテキスト共有方式
間は，RTOS のタスク切り替えに要する時間のみで 17us とな
の有用性を確認できた．
り，上記理由により共有しない場合と比べてクエリコンテキス
一方，コミットの単位については，今回の評価では，オペ
ト共有方式は優先度逆転時間が大きくなることを確認した．ま
レータ単位コミットはデータ単位コミットよりも処理時間が大
たデータ単位コミットの優先度逆転時間は 34us であり，オペ
幅に削減され，また優先度逆転時間も許容できる範囲に収まり，
レータ単位コミットでコンテキストの更新をオペレータ単位で
メモリ使用量もわずかな増加に留まった．しかしクエリや処理
纏めて実施することにより，優先度逆転時間が 17% 増加する
データによっては，オペレータ単位コミットにより優先度逆転
ことを確認した．
時間が大幅に増加するケースもあり，適用ケース毎に使い分け
またクエリ処理共有方式では，高優先度アプリケーションを
実行しない周期で，低優先度アプリケーション向けのクエリが
実行中，中優先度アプリケーションの実行が妨げられる．その
ため優先度逆転時間はクエリの処理時間に近い 20ms となり，
る必要があると考えられる．
6. 関 連 研 究
RTOS におけるタスクの優先度の動的変更機能として，優先
クエリコンテキスト共有方式により優先度逆転時間が大幅に削
度上限プロトコル，優先度継承が挙げられる．優先度上限プロ
減できることを確認した．
トコルでは，リソースを取得することで，そのリソースを共有
5. 3. 2 処 理 時 間
するタスクの中で最高優先度のタスクと同一優先度でタスクを
クエリコンテキスト共有方式 (オペレータ単位コミット) にお
実行することができる．優先度上限プロトコルを用いることで，
ける処理時間は 29ms となった．共有化しない場合の処理時間
クエリ処理共有方式においてクエリを割り当てたタスクの優先
は 43ms であり，クエリの処理引継ぎの効果として処理時間の
度を動的に変更可能となる．しかし優先度上限プロトコルを用
32% 削減を確認した．またクエリ処理共有方式の処理時間は
いた場合，タスクの起動の有無に関係なく，最高優先度のタス
22ms であるため，クエリコンテキスト共有方式では，コミッ
クと同一優先度で実行されるため，例えば稀に起動する最高優
ト時のロックの取得等により処理時間が 32% 増加することを
先度タスクがリソースを共有している場合では，クエリが最高
確認した．またデータ単位コミットでは処理時間は 35ms とな
優先度となるため，優先度逆転が及ぼす影響が大きくなる．
り，オペレータ単位コミットはロック取得回数を削減すること
優先度継承では，リソースを取得中，リソースの取得待機中
により，データ単位コミットと比べて 17% と処理時間を削減
のタスクの中で最高優先度のタスクと同じ優先度でタスクを実
することを確認した．
行することができる．優先度継承を用いることで，優先度上限
5. 3. 3 メモリ使用量
プロトコルとは異なり，クエリ処理共有方式に適用した場合，
クエリコンテキスト共有方式 (オペレータ単位コミット) のメ
実行中のアプリケーション中の最高優先度でクエリを実行でき
モリ使用量は 139KByte となった．共有しない場合のメモリ使
る．しかしクエリがアプリケーションと別タスクで実行される
用量は 245KByte であり，クエリのコンテキスト共有の効果と
ため，クエリの実行タイミングをアプリケーションで制御でき
してメモリ使用量の 43% 削減を確認した．またクエリ処理共
ず，アプリケーション内のより優先度の高い処理を，クエリに
有方式のメモリ使用量は 131KByte であり，クエリコンテキス
より妨げられる可能性がある．一方，クエリコンテキスト共有
ト共有方式ではタスク専用メモリが必要となることから 6.1%
方式では，各アプリケーションが，同一タスクに割り当てられ
メモリ使用量が増加することを確認した．またデータ単位コ
たクエリの実行タイミングを制御することが可能である．
ミットのメモリ使用量は 137KByte となった．オペレータ単位
DSMS におけるリアルタイムシステム向けスケジューリング
コミットでは，複数データの処理結果を纏めて共有メモリに格
方式が提案されている．RTSTREAM [10] では DSMS におけ
納するため，その処理結果を一時的に格納する，より大きなタ
る周期実行クエリモデルを導入し，そのモデル上で，動的に変
スク専用メモリが必要になるため，データ単位コミットよりも
動するストリームデータの入力レートに対応するための，入力
1.5% 増加することを確認した．
の制御メカニズムを提案した．また Li らの方式 [11] では，ク
5. 4 考
察
エリの一部のオペレータパスをタスクとしてモデル化し，その
クエリ処理共有方式では，処理時間，メモリ使用量共にク
タスクのスケジューリングと，タスク内の各オペレータに対し
エリコンテキスト共有方式よりも削減できるものの，優先度
てスケジューリングを行う．スケジューリング方法は，Earliest
逆転時間が 20ms と大きく，適用できるケースは限定的である
deadline に従って，ストリームキュー内の実行待ちのデータに
と言える．一方，クエリコンテキスト共有方式は，共有しな
対して実行順序を決定し，該当するデータを処理する，タスク
い場合と比較し処理時間，メモリ使用量共に大幅に削減でき
を実行する．これらの方式は，クエリコンテキスト共有方式と
た．また優先度逆転時間は共有しない場合よりも増加している
は異なり，DSMS のクエリのみのスケジューリングであり，ク
が，その時間は 0.1ms 未満に収まっており，今回評価に用いた
エリとその他のアプリケーションも合わせたスケジューリング
50ms∼100ms 周期のアプリケーションでは許容できる時間と
については検討されていない．
言える．また車載システム向け DSMS で主にターゲットとし
DSMS においてトランザクションを考慮した方式が検討さ
ている，ADAS(Advanced Driver Assistance Systems) の動作
れている [12] [13] [14]．これらの研究は，クエリが入力とする
DSMS 外部の情報源が更新される場合に，クエリの処理結果の
整合性を確保する方式である．一方，クエリコンテキスト共有
方式では，複数のタスクに割り当てたクエリに対して，共有コ
ンテキストが更新される場合に，クエリの処理結果を保証する
方式である．
7. お わ り に
クエリコンテキスト共有方式では，異なるタスクに割り当て
たクエリに対してコンテキストを共有し，そのコンテキストを
用いて処理を引き継ぐことで，優先度逆転時間を削減しつつ，
クエリ処理最適化を実現する．本稿ではコンテキストの更新に
必要となるロックの取得頻度を最適化することにより，優先度
逆転時間と，処理時間，メモリ使用量を両立することを目的と
して，クエリコンテキスト共有方式の実現手法を提案した．提
案方式では，コンテキストをコミット時に纏めて更新し，また
コミットをデータ単位または，複数のデータを纏めたオペレー
タ単位で実行する．評価の結果，従来手法であるクエリ処理共
有方式と比較し，優先度逆転時間を大幅に削減しつつ，共有し
ない場合と比較し処理時間，メモリ使用量をそれぞれ 32% ，
46% 削減できることを確認した．
今後の課題としては，コミット単位の最適化による処理時間
の改善や，処理タイミングが異なるクエリのコンテキスト共有
化により，クエリコンテキスト共有方式の適用範囲を広げるこ
とが挙げられる．
文
献
[1] 山田真大，鎌田浩典，佐藤健哉，手嶋茂晴，高田広章: データス
トリーム管理機構を利用した車載データ統合モデルの提案と評
価，自動車技術会論文集，Vol.42, No.2, 2010.
[2] 勝沼 聡，山口 晃広，熊谷 康太，本田 晋也，佐藤 健哉，高田 広
章: 車載組込みシステム向けデータストリーム管理システムの開
発，電子情報通信学会論文誌 Vol. J95-D, No.12, 2012．
[3] 山口 晃広, 本田 晋也, 佐藤 健哉, 高田 広章: 車載システム向け
データストリーム管理システムにおけるクエリ自動構築手法, 第
11 回情報科学技術フォーラム講演論文集, Vol.2, 2012.
[4] 勝沼聡，本田晋也，佐藤健哉，佐藤健哉，高田広章: 車載組込み
システム向けデータストリーム管理の静的スケジューリング方
式，情報処理学会論文誌データベース（TOD），vol.55, 2012.
[5] R. Motwani, J. Widom，A. Arasu, B. Babcock, S. Babu, M.
Datar, G. Manku, C. Olston, J. Rosenstein, and R. Varma:
Query Processing, Resource Management, and Approximation in a Data Stream Management System, Conference on
Innovative Data Systems Research (CIDR), 2003.
[6] D. J. Abadi, D. Carney, U. Cetintemel, M. Cherniack, C.
Convey, S. Lee, M. Stonebraker, N. Tatbul, and S. Zdonik:
Aurora: a new model and architecture for data stream management, The VLDB Journal, 2003.
[7] J. Chen, D. J. DeWitt, and J. F. Naughton: Design and
Evaluation of Alternative Selection Placement Strategies in
Optimizing Continuous Queries, ICDE 2002.
[8] 渡辺陽介, 北川博之: 連続的問合せに対する複数問合せ最適化手
法, 電子情報通信学会論文誌，Vol. J87-D-I, No. 10, 2004.
[9] 勝沼聡，本田晋也，高田広章: リアルタイム性を考慮した車載シ
ステム向け DSMS のクエリ処理効率化，日本データベース学会
和文論文誌 Vol.13-J, No.1, 2014.
[10] Y. Wei, S. H. Son, J. A. Stankovic, RTSTREAM: Real-Time
Query Processing for Data Streams: ISORC, 2006
[11] X. Li, Z. Jia, L, Ma, R. Zhang, H. Wang: Earliest Deadline Scheduling for Continuous Queries over Data Streams,
ICESS 2009.
[12] L. Grgen, C. Roncancio, C. Labb, V. Olive: Transactional
Issues In Sensor Data Management, DMSN, 2006.
[13] 小山田昌史，川島英之，北川博之: ストリームデータ処理におけ
る状態一貫性の保証, DEIM, 2012.
[14] U. Cetintemel, J. Du, T. Kraska, S. Madden, D. Maier, J.
Meehan, A. Pavlo, M. Stonebraker, E. Sutherland, N. Tatbul, K. Tufte, H. Wang, and S. Zdonik: S-Store: A Streaming NewSQL System for Big Velocity Applications, VLDB
Endow., vol.7, iss.13, 2014.
[15] S. Katsunuma, S. Honda, K. Sato, Y. Watanabe,
Y. Nakamoto, H. Takada: Real-time-aware Embedded
DSMS Applicable to Advanced Driver Assistance Systems,
SRDSW, 2014.