DEIM Forum 2014 D3-5

リアルタイム性を考慮した車載システム向け DSMS のクエリ処理効率化
勝沼

聡†∗

本田

晋也†

高田

広章†

† 名古屋大学大学院情報科学研究科 〒 464–8601 名古屋市千種区不老町∗ 日立製作所 中央研究所
E-mail: †{katsunuma,honda,hiro}@ertl.jp
あらまし 車載システムの複雑化に伴う開発コスト削減を目的とし，車載システムへの DSMS の適用を検討している．
車載システムにおいて，従来の汎用システム向け DSMS のクエリ処理共有方式を適用した場合，優先度が逆転する時
間（優先度逆転時間）が大きくなり，リアルタイム性が保つのが難しい．そこで本稿で提案するクエリコンテキスト共有方式では，優先度逆転時間を削減するために，アプリケーション毎に独立して決められた優先度でクエリを実行する．そして処理が等価なクエリ間で，クエリの処理過程で必要となるデータ（コンテキスト）を共有可能とし，あるクエリの実行がスケジューリングの関係上，中断され，他のクエリが実行された場合，前のクエリのコンテキストを引き継ぐことで処理時間を削減する．クエリコンテキスト共有方式を評価した結果，従来方式であるクエリ処理共有方式と異なり優先度逆転時間が低減され，また処理時間の増加も 2.13% に留まりクエリの処理効率化の効果を示した．
キーワード

データストリーム管理システム，クエリ処理効率化，リアルタイム，車載システム，RTOS

Realtime-Aware Eﬃcient Query Processing for Automotive DSMS
Satoshi KATSUNUMA†∗ , Shinya HONDA† , and Hiroaki TAKADA†† Graduate School of Information Science, Nagoya University Furo-cho, Chikusa-ku, Nagoya, 464–8601 Japan∗ Central Research Lab., Hitachi Ltd.
E-mail: †{katsunuma,honda,hiro}@ertl.jp

1. は じ め に優先度逆転が発生する DSMS のクエリ処理共有方式を適用することは難しい．車載システムでは RTOS が搭載され，アプ

車載システムでは，アプリケーションの生産性向上に向け，

リケーションは RTOS のタスクに割り当てる．そして各タスク

AUTOSAR がデファクトとなり，プラットフォームの導入がをリアルタイム性の要件を満たすために，優先度を設定しプリ進んでいる．AUTOSAR ではソフトウェアコンポーネントのエンティブなマルチタスク環境で動作させる．しかしクエリ処

インタフェースを共通化し，様々な ECU で共通のアプリケー

理共有方式では，そのクエリの処理に対して高い優先度を割りションを動かせるようにする．

当てた場合には優先度逆転が発生し，クエリの処理が他のタス

我々が提案している車載データ統合 PF [1] [2] [3] では，AU-

クの実行を妨げ，またクエリの処理に対して低い優先度を割り

TOSAR 上で，様々な ECU で共通するデータ処理を定義し，当てた場合には他のタスクがクエリの処理を妨げる．そのためそのデータ処理を様々なアプリケーションが利用可能とする．

リアルタイム性を保ちつつ処理を共有するのは難しい．

車載データ統合 PF ではデータ処理をデータストリーム管理

本稿ではリアルタイム性の要件を満たすため，車載システム

システム（以下，DSMS）のクエリとして記述する．そして同のスケジュールの元で，クエリの処理を効率化するクエリコン

一 ECU 上の複数のアプリケーションから呼ばれるクエリの処

テキスト共有方式を提案する．クエリコンテキスト共有方式で理を共有することで，リソース制約が厳しい車載システム上では，クエリの処理を，その処理結果を利用するアプリケーショ

処理量を低減することが期待されている．汎用システム向けのンと同一タスクに割り当て，同一優先度で実行する．そして異DSMS におけるクエリ処理共有方式 [7] [8] では，複数のアプリ

なるタスクに割り当てられたクエリに対し処理が等価なクエリ

ケーション向けのクエリの処理を一度だけ実行し，その処理結間で，キューやウィンドウ，オペレータの計算に必要とする状果を各アプリケーションに渡すことで処理量を低減している．

態などクエリの処理過程で必要となるデータ（以下，コンテキ

しかし車載システムではリアルタイム性が求められるため，

スト）を共有し，タスク切替え時にクエリのコンテキストを用

いて，切替え先のクエリに処理を引き継ぐ．これにより優先度㌴㌴㛫㏻ಙ(࿘ᮇ50ms)

逆転の発生期間を，タスク間で共有するコンテキストへのアクඃඛᗘ

セス時のみに抑制しつつ，クエリの処理をタスク間で引き継ぐ

㧗

ことで処理時間を削減する．

୰

本稿の構成は以下の通りである．まず 2 節で車載システムの

ࢱࢫࢡ
⾪✺㆙࿌
(࿘ᮇ100ms)⥭ᛴ㌴୧㆙࿌
(࢖࣋ࣥࢺ㥑ື)㼑㼢㼑㼚㼠࿘㎶㌴୧⾲♧(࿘ᮇ50ms)ప

要求仕様及び，車載システムへの DSMS 適用について述べ，30ms

節で従来方式であるクエリ処理共有方式の課題を述べる．そし課題を述べる．

ඃඛᗘ

ࢱࢫࢡ

㧗

ඹ᭷ฎ⌮
(࿘ᮇ50ms)

㧗

2. 車載システムの要求仕様と DSMS 適用
本節では車載システムに求められる仕様と，車載システムへ

୰
ప

ඃඛᗘ
㧗

車載システムではリアルタイム性を高めるために，図 1(a) にపり当てられる，マルチタスクの構成になっており，各アプリケー
ションのリアルタイム性の要件に合わせて，アプリケーションを割り当てたタスクに対してあらかじめ優先度を設定する．そして高い優先度のタスクよりも低い優先度のタスクが実行される優先度逆転が発生する時間を小さくする，プリエンティブなスケジューリングを行う．

•

特性 2. 周期実行またはデッドラインを持つイベント駆動

車載システムでは各アプリケーションを周期実行または，デッドラインを持つイベント駆動で動作する．アプリケーションが扱う，車車間通信や自車のセンサのデータは一定の間隔で更新
され，周期実行を行うアプリケーションではその周期で取得できるデータを入力とした処理を行い，処理が完了した場合には，次の周期まで待機する．また各周期の終わりをデッドラインとし，周期の間に処理が完了しなかった場合には，その周期でのアプリケーションの処理を中止する．イベント駆動のアプリ
ケーションでは，デッドラインを設定し，イベントが発生してからデッドラインの時刻までに取得できるデータを入力とし処理する．そしてデッドラインの時刻を超えたらアプリケーショ
ンの処理を中止する．

2. 1. 2 RTOS の活用
車載システムでは，特性 1，2 を持つスケジューリングを行うために RTOS を活用し，一つの ECU に搭載される全てのア
プリケーションに対して統一的なスケジューリングを行う．すなわち各アプリケーションを RTOS のタスクに割り当て，タスクに対し優先度や実行タイミング，デッドライン等を設定することにより，アプリケーションの処理の開始や，他のアプリ
ケーションへの処理の切り替え，処理の中止を RTOS で制御する．なお車載システム向けの RTOS ではメモリ保護を用いる

ඃඛᗘ
㏫㌿

㼑㼢㼑㼚㼠

50ms

ࢱࢫࢡ

100ms

F

⾪✺㆙࿌
(࿘ᮇ100ms)⥭ᛴ㌴୧㆙࿌
(࢖࣋ࣥࢺ㥑ື)࿘㎶㌴୧⾲♧(࿘ᮇ50ms)示す，下記特性 1，2 を持つスケジューリングを行う．
車載システムは一般的に，一つの ECU に複数のタスクが割

250ms

150ms

200ms

250ms

㌴㌴㛫㏻ಙ
(࿘ᮇ50ms)

୰

特性 1. 優先度ベースのプリエンティブスケジューリング

200ms(b) ࢡ࢚ࣜฎ⌮ඹ᭷᪉ᘧ

2. 1. 1 スケジューリングの方法

•

150ms

ฟຊ
ࢹ࣮ࢱ
฼⏝

0ms

2. 1 車載システム
ジューリングを実現するための RTOS の活用方法を述べる．

E

⾪✺㆙࿌
(࿘ᮇ100ms)⥭ᛴ㌴୧㆙࿌
(࢖࣋ࣥࢺ㥑ື)࿘㎶㌴୧⾲♧(࿘ᮇ50ms)の DSMS 適用時の狙いについて述べる．
車載システムにおけるスケジューリングの方法と，そのスケ

100ms

㌴㌴㛫㏻ಙ
(࿘ᮇ50ms)て 4 節で提案方式であるクエリコンテキスト共有方式を説明し，5 節でその評価について述べる．最後に 6 節でまとめと今後の50ms(a) ᪤Ꮡࡢ㌴㍕ࢩࢫࢸ࣒

:ࢡ࢚ࣜ

:࢔ࣉࣜ

F

ฟຊࢹ࣮
ࢱ฼⏝/ࢡ
࢚ࣜࡢฎ
⌮ᘬ⥅ࡂ

0ms

50ms

100ms

150ms

㼑㼢㼑㼚㼠

200ms

250ms

(c) ࢡ࢚ࣜࢥࣥࢸ࢟ࢫࢺඹ᭷᪉ᘧ

図 1 車載システムにおけるスケジューリングの例

ことがほとんどなく，タスク間でデータを共有することが可能
である．

2. 2 車載システムへの DSMS 適用の狙い
車載データ管理 PF では，車載データ処理を DSMS のクエリとして記述し，車載システム向け DSMS（eDSMS）[2] [4] 上で実行する．そしてリソース要件が厳しい車載システムにおけるクエリの処理量を低減するために，DSMS を適用することで複数のアプリケーションが使用するクエリの処理効率化を目指している．図 2 に示す例では，車車間通信データから，走行している他車の平均速度等を算出する他車走行情報配信クエリを，
衝突警告及び緊急車両警告，周辺車両表示の三つのアプリケー
ションが使用している．このような場合に複数アプリケーショ
ン向けの共通するクエリの処理を一度で行うなどの，クエリの処理効率化が求められる．

3. 従来手法の課題
クエリ処理効率化を実現するための，クエリ処理共有方式の概要と，車載システム適用時の課題を述べる．

3. 1 クエリ処理共有方式
クエリ処理共有方式 [7] [8] では，複数のアプリケーションが共通に使用するクエリの処理を纏めて一度だけ実行することで，処理量の低減を行う．例えば渡辺らの方式 [8] では，クエリの処理を一つにするために，実行タイミングが異なるが実行時間に重なりを持つ複数のクエリに対して，各クエリの実行時間を合わせた時間を実行時間とする，クエリの処理を行う．

にクエリ処理効率化を行う，クエリコンテキスト共有方式を提௚㌴㉮⾜᝟ሗ㓄ಙࢡ࢚ࣜࡢฎ⌮ෆᐜ

案する．

㏿ᗘ䚸఩⨨䛛䜙 ᖹᆒ㏿ᗘ
䜰䝥䝸䛻
㉮⾜㌴୧
㓄ಙ䛩䜛
⟬ฟ
ᢳฟ
ᙧᘧ䛻ኚ᥮
Aggre
㌴㌴㛫
௚㌴
Filter
Map
㏻ಙ䝕䞊䝍
㉮⾜᝟ሗ
gate

•

車載システム向けスケジューリング

提案方式では RTOS を用いて車載システム向けのスケジュー࢔ࣉࣜ௚㌴㉮⾜᝟ሗ㓄ಙࢡ࢚ࣜ⾪✺㆙࿌

௚㌴㉮⾜᝟ሗ㓄ಙࢡ࢚ࣜ

⥭ᛴ㌴୧
㆙࿌

௚㌴㉮⾜᝟ሗ㓄ಙࢡ࢚ࣜ

࿘㎶㌴୧
⾲♧

リングを実現する．車載システムでは，特性 1 に示すようにア
プリケーションごとに優先度が異なるため，提案方式では処理が等価なクエリであっても図 1(c) に示すようにクエリを，クエリを利用するアプリケーションと同一のタスクに割り当て，同

図 2 車載システムへの DSMS 適用

3. 2 車載システム適用に向けた課題
車載システムでは特性 1 に示すように，処理内容が同じクエリであっても，その処理結果を利用するアプリケーションの優
先度が異なる可能性があるため，クエリの処理を共有するためにいずれかのアプリケーションの優先度で実行する必要がある．
しかし共有処理を割り当てるタスクに，いずれかのアプリケー
ションの優先度を設定したとしても優先度逆転が起こる可能性がある．
図 1(b) は衝突検知と周辺車両表示アプリケーションがクエリの処理を共有するため，クエリの処理をアプリケーションとは別のタスクに割り当てる場合である．この場合，各アプリ
ケーションがクエリの処理結果を利用するため，クエリの処理を割り当てるタスクには，優先度が高い衝突検知アプリケー
ションの優先度を割り当て，また動作周期を，周期が短い周辺
車両表示アプリケーションの周期 50ms で実行する必要がある．
しかしその場合には，図 1(b1) に示すように優先度「低」の周
辺車両表示アプリケーションのみがクエリの処理結果を利用するケースでもクエリの処理が優先度「高」で実行されるため，
そのクエリの処理により優先度が「中」の緊急車両警告アプリ
ケーションの実行が妨げられ，優先度逆転が起こりうる．
またクエリの処理を優先度が高い別のタスクとして実行する
場合，クエリの処理終了後に，アプリケーションの処理を開始する．そのためアプリケーションで，クエリの処理結果を利用する前に事前に処理が必要である場合，その処理の開始が遅れる．またクエリで処理しつつ，その結果結果を順次，アプリ
ケーションが受け取り，クエリの処理と並行して処理を実行することもできない．さらにクエリの処理を，アプリケーションと異なる新たなタスクに割り当てるため，その新たなタスクのスタック領域などが必要となりメモリ使用量が大きくなる．
従ってクエリ処理共有方式を，車載システムに適用することは困難である．

一優先度で処理を実行する．また特性 2 に示すようにデッドラ
インの時刻を過ぎた場合には，クエリの処理中であってもタスクを終了する必要があるため，次の周期でクエリの処理を継続できるよう，クエリのコンテキストを引き継ぐ．

•

クエリの処理効率化

前述のように処理が等価なクエリであっても異なるタスクに割り当てられる．そこで処理が等価なクエリのコンテキストを共有し，スケジューリングの都合上，中断され，他のタスクが実行された際に，前のクエリの出力データを切り替わり先のア
プリケーションが利用する．また前のクエリのコンテキストを利用して，前のクエリの処理を切り替わり先のタスクのクエリが引き継ぐ．例えば図 1(c1) では，周辺車両表示用のタスクにおけるクエリの出力データを，衝突警告アプリケーションが利用し，また，周辺車両表示用のタスクにおけるクエリの処理を，
衝突警告用のタスクのクエリが引き継ぐ．
クエリコンテキスト共有方式では，優先度逆転の発生期間を，タスク間で共有するコンテキストへのアクセス時のみに抑制することで優先度逆転時間を削減する．またタスク切り替え時に，クエリの出力データを切り替え先のタスクのアプリケーションが利用し，またクエリの処理を切り替え先のタスクのクエリが引き継ぐことで処理時間を削減する．ただし提案方式ではクエリ処理共有方式と比較し，異なるタスクに割り当てられたクエ
リのコンテキストの共有が必要となるため，コンテキストを管理するための処理オーバヘッドが発生する．

4. 2 構成

提案方式の構成を図 3 に示す．提案方式は RTOS（図 3（a）），

eDSMS（図 3（b）），アプリケーション（図 3（c））から構成
される．提案方式では，従来の eDSMS [4] と同様に，Filter，Aggregate，Map など Borealis [10] をベースとしたオペレータ
によりクエリの処理が行われるため，クエリのセマンティック
スは従来の eDSMS に準じており，またクエリ内のオペレータのスケジューリングについても従来の eDSMS と同様である．
しかしクエリ間及び，クエリとデータ入力部のスケジューリングの方法や，アプリケーションからのクエリの呼び出し方法は，
下記に示すように従来の eDSMS とは異なる．
提案方式では RTOS にはあらかじめタスクが登録され，タス
ク管理テーブル（図 3（a1））を参照しタスクを呼び出す．各タ

4. クエリコンテキスト共有方式
4. 1 コンセプト
本稿では車載システムにおけるリアルタイム性を考慮し，車載システムのスケジューリングの元で，処理量を低減するため

スクではアプリケーションが DSMS スケジューラ（図 3（b1））
を呼び出し，DSMS スケジューラがデータ入力部（図 3（b2））
またはクエリ（図 3（b3））を呼び出す．データ入力部は入力
データを入力キュー（図 3（b5））に格納し，クエリの処理により入力キューから入力データを取り出し，各オペレータで実行E H'606

F ࢔ࣉࣜ

 5726࠿ࡽࢱࢫࢡࢆ࿧ࡧฟࡋࠊ࢔ࣉࣜࢣ࣮ࢩࣙࣥᐇ⾜
ࢱࢫࢡˠ

ࢱࢫࢡ˞
(b1)DSMSࢫࢣࢪ࣮ࣗࣛ

⾪✺㆙࿌E ࢡ࢚ࣜ

(b2)ࢹ࣮ࢱ
ධຊ㒊

Filter

Aggre
gate

࿘㎶㌴୧
⾲♧
DSMSࢫࢣࢪ࣮ࣗࣛ

Map

5726

ࢱࢫࢡ˟
(b1) DSMSࢫࢣࢪ࣮ࣗࣛ

⥭ᛴ㌴୧
㆙࿌

E ࢡ࢚ࣜ

(b2)ࢹ࣮ࢱ
ධຊ㒊

FilterAggregateࢱࢫࢡ⟶⌮ࢸ࣮ࣈࣝඃඛᗘ ᐇ⾜ྍ⬟䝍䝇䜽α 㧗
㽢䝍䝇䜽β ୰
㽢䝍䝇䜽γ ప䕿Map ࢹ࣮ࢱධຊࢱࢫࢡˠ(b1) DSMSࢫࢣࢪ࣮ࣗࣛ

࿘㎶㌴୧
⾲♧

E ࢡ࢚ࣜ

(b2)ࢹ࣮ࢱ
ධຊ㒊

Filter

Aggre
gate

ࢱࢫࢡˠ

DSMSࢫࢣࢪ࣮ࣗࣛ
ࢹ࣮ࢱධຊ㒊

Map

ࢢ࣮ࣟࣂࣝ㡿ᇦධຊ࣮࢟ࣗE ࢢ࣮ࣟࣂࣝ㡿ᇦ
E ධຊ࣮࢟ࣗ

㌴E ㌴D

㌴E

㌴D

E ኚ᭦ᒚṔE ࢘࢕ࣥࢻ࢘
E ࣮࢜࣌ࣞࢱ
ࢫࢸ࣮ࢺ

E
ฟຊ࣮࢟ࣗ

 ࢡ࢚ࣜࡢฎ⌮ᐇ⾜ࢱࢫࢡˠDSMSࢫࢣࢪ࣮ࣗࣛ
ࢡ࢚ࣜ
Filter

D 5726
ඃඛᗘ ᐇ⾜ྍ⬟D ࢱࢫࢡ⟶⌮䝍䝇䜽α 㧗
㽢ࢸ࣮ࣈࣝ䝍䝇䜽β ୰
㽢䝍䝇䜽γ ప
䕿

図3ࢢ࣮ࣟࣂࣝ㡿ᇦ

Aggre
gate

Map

㌴D
ฟຊ࣮࢟ࣗ

ධຊ࣮࢟ࣗ

㌴D

㌴E
࣮࢜࣌ࣞࢱࢫࢸ࣮ࢺ
࢘࢕ࣥࢻ࢘
㌴
ᖹᆒ㏿ᗘ
㌴D
㌴a

クエリコンテキスト共有方式の構成

40km/h ࢔ࣉࣜࢣ࣮ࢩࣙࣥᐇ⾜後，出力データを出力キュー（図 3（b6））に格納する．そして
アプリケーションに制御が戻ると，出力キューから出力データ

ࢱࢫࢡˠ

࿘㎶㌴୧
⾲♧
DSMSࢫࢣࢪ࣮ࣗࣛ

を取り出し処理を行う．
また提案方式では，入力キュー，出力キューなどのキューや，
ウィンドウ（図 3（b7））及び，Aggregate オペレータなど各オࢢ࣮ࣟࣂࣝ㡿ᇦ
ฟຊ࣮࢟ࣗ
㌴E ㌴D

ペレータの状態を保持するオペレータステート（図 3（b8））な
図 4 基本的な動作

どにある全てのコンテキストを，異なるタスクからアクセスされるグローバル領域（図 3（b4））に格納し，異なるタスクのク
エリ間でコンテキストを共有する．そしてクエリ処理効率化の4. 3. 2 アプリケーションの実行

ために，タスクの切り替わり時に，出力キューに格納される，異RTOS からタスクが呼び出されると，そのタスクに割り当てなるタスクのクエリの出力データをアプリケーションが利用すられたアプリケーションが実行される．例えば図 4（1）では，る．またクエリ実行中にタスクが切り替わった場合に，DSMS

RTOS からタスクγが呼ばれ，タスクγに割り当てられた周辺

スケジューラでロールバックを行い，変更履歴（図 3（b9））に車両表示アプリケーションを実行する．そしてアプリケーショ

基づきコンテキストを入力データの実行前に戻し，切り替わっ

ンから DSMS スケジューラを呼び出すことで，クエリの処理たタスクで，コンテキストを引き継ぎクエリの処理を継続する．

が実行され，DSMS スケジューラの処理終了後に，アプリケー

4. 3 基本的な動作

ションで出力キューに格納された，クエリの出力データを取得

図 1(c1) に示す提案方式においてクエリのコンテキストの引する．例えば図 4（1）では周辺車両表示アプリケーションが継ぎがない場合の動作を，図 4 を用いて説明する．

DSMS スケジューラを呼び出し，その後，クエリの処理実行後

4. 3. 1 アプリケーション構成とタスクへの割当てに図 4(4) に示すように出力キューに格納されたデータ車 a，車まず具体例として挙げるアプリケーションの構成と，そのタb を衝突検知アプリケーションが取り出し処理を行う．

スクへの割当てについて説明する．アプリケーションは衝突検

4. 3. 3 DSMS スケジューラ

知，緊急車両警告，周辺車両表示であり，図 3 に示すように，

アプリケーションから呼ばれる DSMS スケジューラでは，

各アプリケーションは他車走行情報配信クエリと共にそれぞれデータ入力部及び，クエリの処理を呼び出す．データ入力部は，

タスクα，β，γに割り当てる．そして図 1（c）に示すアプリ

図 4(2) に示すように入力データが入力キューに格納されていケーションの優先度に合わせて，タスクα，β，γの優先度をない場合に呼び出す．またクエリの処理は，図 4(3) に示すようそれぞれ「高」，「中」，「低」とし，また実行タイミングは周期に入力データの入力キューへの格納後に呼び出す．

実行（周期 100ms），イベント駆動，周期実行（周期 50ms）と4. 3. 4 データ入力

する．

DSMS スケジューラから呼び出されるデータ入力部では，車により次の周期でコンテキストを引き継ぎ，クエリを処理可能 ࢡ࢚ࣜᐇ⾜#ࢱࢫࢡˠ
ࢱࢫࢡˠ

とする．

DSMSࢫࢣࢪ࣮ࣗࣛ
ࢡ࢚ࣜ
FilterAggregate

4. 4 クエリ処理効率化のためのタスク切替え時の動作

Map

提案方式では図 1(c2) に示すように，処理が等価なクエリの㌴Eࢢ࣮ࣟࣂࣝ㡿ᇦ

ධຊ࣮࢟ࣗ

ኚ᭦ᒚṔ

ฟຊ࣮࢟ࣗ
࣮࢜࣌ࣞࢱࢫࢸ࣮ࢺ

࣭ධຊ࣮࢟ࣗ ㌴b㝖ཤ࣭࢘࢕ࣥࢻ࢘ ㌴bᤄධ࣭࣮࢜࣌ࣞࢱࢫࢸ࣮ࢺ
㌴b 50km/h -> 60km/h

࢘࢕ࣥࢻ࢘
㌴E ㌴D

㌴D

コンテキストを共有することで，タスクが切り替わる際に（A）

㌴

ᖹᆒ㏿ᗘ

クエリの出力データを，切り替わり先のタスクのアプリケー㌴a

40km/hションが利用する．また（B）クエリの処理を，切り替わり先㌴b

60km/hのタスクのクエリが引き継ぐ．以下で (A)(B) の動作について説明する．

 ࢹࢵࢻࣛ࢖ࣥ᫬้⤒㐣ᚋࠊḟࡢ࿘ᮇ࡛࣮ࣟࣝࣂࢵࢡ#ࢱࢫࢡˠ
ࢱࢫࢡˠ

⾪✺㆙࿌

タスクの切り替わり時に，他タスクのクエリの出力データをDSMSࢫࢣࢪ࣮ࣗࣛ

切り替え先のアプリケーションが利用する場合の動作を図 6 の࣮ࣟࣝࣂࢵࢡ

(1)〜(3) に示す．クエリの処理の出力データはグローバル領域ࢢ࣮ࣟࣂࣝ㡿ᇦኚ᭦ᒚṔ࣭ධຊ࣮࢟ࣗ ㌴b㝖ཤ࣭࢘࢕ࣥࢻ࢘ ㌴bᤄධ࣭࣮࢜࣌ࣞࢱࢫࢸ࣮ࢺ
㌴b 50km/h -> 60km/h

4. 4. 1 出力データの利用

㌴E
ධຊ࣮࢟ࣗ

࣮࢜࣌ࣞࢱࢫࢸ࣮ࢺ
㌴
ᖹᆒ㏿ᗘ
࢘࢕ࣥࢻ࢘
㌴D

㌴a

40km/h㌴b

60km/hにある出力キューに格納されているため，タスク切り替え後，
アプリケーションで出力キューにアクセスし，出力データを取得する．例えば図 6(1) ではタスクγでデータ車 a が出力キューに格納されているため，図 6(2) でタスクγからタスクαに切

図 5 デッドライン時刻経過時のクエリ処理の中止

り替わった後に，て図 6(3) に示すようにタスクαに割り当てられた衝突警告アプリケーションが，出力キューからデータ車

車間通信データなどの入力データを入力キューに格納する．例

a を取得する．

えば図 4(2) では，データ車 a，車 b を順に入力キューに格納

4. 4. 2 クエリの処理引継ぎ

する．

タスク切り替わり時に，切り替わり先のタスクでクエリの処

4. 3. 5 クエリの処理の実行

理を継続する場合の動作を図 6 に示す．4.3.6 節で述べたよう

DSMS スケジューラからクエリの処理が呼び出されると，まに，提案方式ではクエリの実行中にコンテキストの変更履歴をずクエリの先頭のオペレータが入力キューから最新のデータを書き込む．そして変更履歴に基づき，切り替わり先のタスクで一つ読み込み，処理を実行する．そして先頭オペレータの処理

キュー，ウィンドウ，オペレータステートに保存されているコ

終了後に，クエリの次のオペレータを処理し，そして続けてク

ンテキストを，データを処理する前の状態に戻すことで，切りエリの最後のオペレータまで処理をする．例えば図 4（3）で替わり先のタスクでクエリの処理を継続する．図 6（1）では，はデータ車 a をクエリで処理する場合を示す．まず先頭のオペ

データ車 b に対してクエリを実行中，変更履歴を書き込み，図レータ Filter が入力キューからデータ車 a を読み出し処理し，6（2）に示すようにタスクγからタスクαへの切り替わり時に，続いて次のオペレータ Aggregate で処理した後に，最後にオペ

図 6（4）に示すようにタスクαでロールバックを行い，データ

レータ Map を処理する．そしてオペレータ Map は処理結果で

車 b をクエリで処理する前のコンテキストに戻す．これによりある出力データを出力キューに格納する．なお eDSMS におけ図 6（5）に示すように，切り替わり先のタスクで再び，データ

るオペレータの処理方法の詳細は文献 [4] に記載する．

車 b をクエリの処理で実行可能とする．

4. 3. 6 デッドライン時刻経過時のクエリ処理の中止

また切り替え先のタスクでアプリケーションの実行終了後に，

デッドラインまでにクエリの処理が完了しなかった場合に，クエリの処理を実行中の切り替え元のタスクを呼び出す．そのそのタスクにおけるクエリの処理を中止する．その場合に，次際にクエリのコンテキストが切り替え先のタスクで変更したにの周期でクエリの処理を継続するために，クエリのコンテキスもかかわらず，切り替え元のタスクではクエリの処理を実行中

トを引き継ぐ必要がある．

であるため，そのままクエリの処理を行うとグローバル領域に

デッドライン時刻経過時においてクエリの処理を中止する処あるコンテキストにアクセスすると処理が不正になる．そこで理を図 5 に示す．提案方式ではクエリの実行中に，クエリの提案方式ではクエリ実行中にグローバル領域へアクセスする際

コンテキストすなわちキュー，ウィンドウ，オペレータステーにはタスクの切り替えを起こらないようにし，かつグローバル

トにあるデータの変更履歴を書き込む．例えば図 5（1）では，領域にアクセスする前にコンテキストが他のタスクのクエリ

データ車 b に対してクエリを実行中，入力キューからデータ車

により更新されているか否かをチェックする．そしてコンテキ

b を除去したことや，ウィンドウにデータ車 b を挿入したこと，

ストが更新されている場合には，クエリの処理が不正となるた

Aggregate オペレータのオペレータステートの値を変更したこ

め，グローバル領域にアクセスする前にクエリの処理を中止しとを変更履歴に記述する．そしてデータ車 b に対するクエリのDSMS スケジューラに制御を戻す．例えば図 6（6）では再びタ処理を実行中にデッドラインの時刻が経過し，クエリの処理をスクγからタスクαに切り替わった際に，クエリの処理におい中止する場合，図 5（2）に示すように次の周期でロールバックて Map オペレータがグローバル領域にアクセスする際に，タを行い，データ車 b を処理する前のコンテキストに戻す．これスクγにおけるクエリの処理によるコンテキストの更新を検出 ࢡ࢚ࣜᐇ⾜#ࢱࢫࢡˠࢱࢫࢡˠ ࣮ࣟࣝࣂࢵࢡ#ࢱࢫࢡ˞ࢱࢫࢡ˞DSMSࢫࢣࢪ࣮ࣗࣛ
ࢡ࢚ࣜ
Filter

Aggre
gate

DSMSࢫࢣࢪ࣮ࣗࣛ

Map

࣮ࣟࣝࣂࢵࢡ

㌴Eࢢ࣮ࣟࣂࣝ㡿ᇦࢢ࣮ࣟࣂࣝ㡿ᇦ

ධຊ࣮࢟ࣗ

ኚ᭦ᒚṔ
࣭ධຊ࣮࢟ࣗ ㌴b㝖ཤ࣭࢘࢕ࣥࢻ࢘ ㌴bᤄධ࣭࣮࢜࣌ࣞࢱࢫࢸ࣮ࢺ
㌴b 50km/h -> 60km/h

ฟຊ࣮࢟ࣗ
㌴D

࢘࢕ࣥࢻ࢘
㌴E ㌴D

㌴

ᖹᆒ㏿ᗘ

㌴a

40km/h㌴b 60km/h
࣮࢜࣌ࣞࢱࢫࢸ࣮ࢺ ࢱࢫࢡษࡾ᭰࠼㸸ࢱࢫࢡˠൺࢱࢫࢡ˞
ࢱࢫࢡ˞

⾪✺㆙࿌

ኚ᭦ᒚṔ
࣭ධຊ࣮࢟ࣗ ㌴b㝖ཤ࣭࢘࢕ࣥࢻ࢘ ㌴bᤄධ࣭࣮࢜࣌ࣞࢱࢫࢸ࣮ࢺ
㌴b 50km/h -> 60km/h࣮࢜࣌ࣞࢱࢫࢸ࣮ࢺ
㌴
ᖹᆒ㏿ᗘ

㌴E

࢘࢕ࣥࢻ࢘

ධຊ࣮࢟ࣗ

㌴D

㌴a

40km/h㌴b

60km/h ࢡ࢚ࣜᐇ⾜#ࢱࢫࢡ˞
ࢱࢫࢡ˞

⾪✺㆙࿌

DSMSࢫࢣࢪ࣮ࣗࣛ
ࢡ࢚ࣜ
Aggre
gate

Filter5726㌴Eࢢ࣮ࣟࣂࣝ㡿ᇦࢱࢫࢡ⟶⌮ࢸ࣮ࣈࣝඃඛᗘ ᐇ⾜ྍ⬟䝍䝇䜽α 㧗
䕿䝍䝇䜽β ୰
㽢䝍䝇䜽γ ప
䕿

ධຊ࣮࢟ࣗ

ኚ᭦ᒚṔ
࣭ධຊ࣮࢟ࣗ ㌴b㝖ཤ࣭࢘࢕ࣥࢻ࢘ ㌴bᤄධ࣭࣮࢜࣌ࣞࢱࢫࢸ࣮ࢺ
㌴b 50km/h -> 60km/h࣭ฟຊ࣮࢟ࣗ㌴bᤄධ ࢔ࣉࣜࢣ࣮ࢩࣙࣥ࡟ࡼࡿฟຊࢹ࣮ࢱ฼⏝#ࢱࢫࢡ˞

Map

ฟຊ࣮࢟ࣗ
㌴E ㌴D

࢘࢕ࣥࢻ࢘
㌴E ㌴D

㌴

ᖹᆒ㏿ᗘ

㌴a

40km/h㌴b 60km/h
࣮࢜࣌ࣞࢱࢫࢸ࣮ࢺ ࢱࢫࢡษࡾ᭰࠼㸸ࢱࢫࢡˠൺࢱࢫࢡ˞

ࢱࢫࢡ˞
ࢱࢫࢡ˞

⾪✺㆙࿌

⾪✺᳨▱

㌴D
ࢢ࣮ࣟࣂࣝ㡿ᇦฟຊ࣮࢟ࣗ

DSMSࢫࢣࢪ࣮ࣗࣛ

㌴D

ࢱࢫࢡˠ

࿘㎶㌴୧
⾲♧
DSMSࢫࢣࢪ࣮ࣗࣛ
ࢡ࢚ࣜ
Filter

Aggre
gate

Map

5726

図 6 クエリ処理効率化のためのタスク切替え時の動作するため，クエリの処理を中止し DSMS スケジューラに制御を戻す．

拡張方式では NPS を RTOS の機能である優先度上限プロト
コルにより実現する．優先度上限プロトコルでは，あらかじめ

4. 5 拡張方式：Non-preemptive section の導入

複数のタスクに対してリソースを登録することで，そのリソー提案方式では 4.4.2 節で述べたように，タスク切り替え時にスを獲得したタスクは，リソースを登録したタスクの中の最

コンテキストを引き継ぐ際に，クエリの処理をロールバックし，も高い優先度のタスクと同じ優先度で実行することができる．

切り替え先のタスクでその入力データに対してクエリの処理を拡張方式では同じクエリを割り当てたタスクα，β，γに対し再度，実行する必要がある．そのためタスク切り替え時に処理てリソースを登録し NPS でリソースを獲得することにより，のオーバヘッドが発生する．

NPS で他のタスクに割り込まれることを回避する．

そこで本節では拡張方式として，その期間中はタスクの切そのため拡張方式では NPS の期間中において優先度が高くり替えが起こらない Non-preemptive section(NPS) を導入し，なるため，その期間に優先度逆転が生じる可能性がある．例え

クエリの処理を実行中，NPS とすることで，タスク切り替え後

ばタスクγは NPS の期間中ではタスクαと同じ優先度で実行のロールバック及びクエリの処理の再実行を不要にする．拡張されるため，NPS の期間である単一のデータをクエリの最初

方式の動作を図 7 に示す．拡張方式では図 7（1）に示すようから最後まで処理する間，タスクγよりも優先度が高いが，タに，タスクγ実行中に，より優先度が高いタスクαが実行可能

スクα以下の優先度のタスクの実行が妨げられる．

となった場合にも，クエリの処理を実行中，NPS となっている
ためタスクαへの切り替えが発生せず，データ車 a をクエリで最後まで処理することができる．NPS は一つのデータをクエ
リの最後のオペレータまで処理すると終了し，タスクを切り替える．図 7（2）に示すようにデータ車 a の処理後にタスクγ

5. 評

価

5. 1 評価方法，環境
クエリコンテキスト共有方式をクエリ処理共有方式と比較し，優先度逆転時間，クエリの処理時間について評価を行った．

からタスクαに切り替わり，タスクαではロールバックやデー

評価環境は，ZMP 社の RoboCar [9] を利用した．評価に用

タ車 a の再実行を行うことなく，図 7（3）に示すように続けていたクエリは，図 8 に示す周辺車両情報を配信するクエリ（周データ車 b に対してクエリの処理を実行する．

辺車両情報配信クエリ）である．周辺車両情報配信クエリでは，

ける実行方法について述べる．

 ࢡ࢚ࣜ ᐇ⾜#ࢱࢫࢡˠࢱࢫࢡˠ•DSMSࢫࢣࢪ࣮ࣗࣛ
ࢡ࢚ࣜ
Aggre
gate

FilterMap

方法と同様に，衝突警告，周辺車両表示アプリケーションが利Non-preemptive section

用するクエリの処理を，各アプリケーションとは別のタスクにࢢ࣮ࣟࣂࣝ㡿ᇦ ㌴D
ධຊ࣮࢟ࣗ

ฟຊ࣮࢟ࣗ

割り当てる．そしてクエリを割り当てるタスクを，より優先度㌴D㌴Eが高い衝突検知アプリケーションの優先度及び，動作周期が短࣮࢜࣌ࣞࢱࢫࢸ࣮ࢺ
㌴D
࢘࢕ࣥࢻ࢘

㌴

ᖹᆒ㏿ᗘ

㌴a

40km/hい周辺車両表示アプリケーションの動作周期に合わせて，優先度「高」，動作周期 50ms で実行する．

•
 5726࡟ࡼࡿࢱࢫࢡษࡾ᭰࠼

辺車両表示アプリケーションと同一タスクに割り当てる．そし⾪✺᳨▱DSMSࢫࢣࢪ࣮ࣗࣛ

てクエリ処理効率化のために，クエリの出力データを他のタス

5726

クのアプリケーションが利用する．またクエリのコンテキストを共有し，タスク切り替え時にクエリの処理を別のタスクのクࢱࢫࢡ⟶⌮ࢸ࣮ࣈࣝඃඛᗘ ᐇ⾜ྍ⬟䝍䝇䜽α 㧗
䕿䝍䝇䜽β ୰
㽢䝍䝇䜽γ ప
䕿

エリが引き継ぐ．NPS を導入する拡張方式では，クエリ全体を一つの NPS の期間とし，一つのデータをクエリの処理で最初のオペレータから最後のオペレータまで実行する間，タスクの ࢡ࢚ࣜᐇ⾜#ࢱࢫࢡ˞

切り替えをしない．

DSMSࢫࢣࢪ࣮ࣗࣛ
ࢡ࢚ࣜ
Filter

Aggre
gate

Map

表1

ࢢ࣮ࣟࣂࣝ㡿ᇦධຊ࣮࢟ࣗ ㌴E

ฟຊ࣮࢟ࣗ
㌴E ㌴D

࣮࢜࣌ࣞࢱࢫࢸ࣮ࢺ
㌴
ᖹᆒ㏿ᗘ

図7

クエリコンテキスト共有方式

クエリコンテキスト共有方式ではクエリを，衝突警告及び周

ࢱࢫࢡ˞

ࢱࢫࢡ˞

クエリ処理共有方式

クエリ処理共有方式では，図 1(b) に示すスケジューリング

㌴E ㌴D

㌴a

40km/h࢘࢕ࣥࢻ࢘㌴b

60km/h

評価結果

項目

コンテキスト

NPS

処理共有

共有なし

優先度逆転時間

0 us

280 us13,100 us

0 us

クエリ処理時間

13,380 us

13,100 us 13,100 us 26,200 us

5. 3 優先度逆転時間
各方式の優先度逆転時間の評価結果を述べる．表 1 に，クエ

拡張方式：Non-preemptive section の導入

リコンテキスト共有方式（コンテキスト），クエリコンテキス
࿘㎶㌴୧᝟ሗ㓄ಙࢡ࢚ࣜ⮬㌴㉮⾜≧ἣ

⮬㌴
䝉䞁䝃

๓᪉㌴୧
᝟ሗ

Join
Filter௚㌴㉮⾜≧ἣ

㐨㊰ᆅᅗ࢔ࣉࣜ

Filter

Join

Map

஺ᕪ㌴୧
᝟ሗ

Map
Map

Join

Map

リ処理共有方式（処理共有），クエリに対して処理効率化のた

Map

Join

㌴㌴㛫
㏻ಙ䝕䞊䝍

ト共有方式における NPS を導入した拡張方式（NPS），クエ

Aggregate⾪✺㆙࿌

クエリ処理共有方式でクエリの処理を実行する場合には，優先度が高い衝突警告アプリケーションと同一の優先度で実行すMapྑᢡ᫬ᑐྥ㌴୧᝟ሗ

めの共有を行わない方式（共有なし）の評価結果を示す．

࿘㎶㌴୧
⾲♧

る．従って図 1(b1) に示すように，衝突警告アプリケーション

FilterJoin

Map

Filterが実行されない周期では，優先度が低い周辺車両表示アプリ
ケーション向けのクエリが高い優先度で実行されるため優先度

図8評価に用いたクエリ

逆転が生じる．同一周期で最大で他車 90 台分のデータがクエ
リにより処理され，その処理時間は最大で 13,100us となるた

自車センサ情報，車々間通信により受け取る他車センサ情報を入力源とし，道路地図情報も用いて前方車両及び，交差点における交差車両，右折時の対向車両の情報を算出する．そして算出した各種情報を衝突警告及び周辺車両表示アプリケーショ
ンに配信する．車々間通信データ，自車センサ情報はそれぞれ

め，優先度逆転時間の最大値は 13,100us となる．
一方，クエリコンテキスト共有方式ではクエリの処理はアプ
リケーションと同一の優先度で実行されるため，クエリの処理を実行中，優先度が逆転することはない．ただし 4.4.2 節で述べたように，グローバル領域の更新中はタスクの切り替えを禁

50ms，20ms 周期で更新し，車々間通信データは最大で他車 90止するため，優先度逆転が発生する可能性がある．上記に関す台から受信する．また図 1 の例と同様に，衝突警告，周辺車両

る優先度逆転時間の評価については今後の課題とする．

表示アプリケーションはいずれも周期実行を行い，動作周期はそれぞれ 100ms，50ms とする．優先度については，衝突警告
アプリケーションの優先度は「高」，周辺車両表示アプリケー
ションの優先度は「低」とする．

5. 2 クエリ実行方法
クエリ処理共有方式及び，クエリコンテキスト共有方式におまた NPS を導入する方式では，周辺車両表示アプリケーショ
ン向けのクエリの処理を NPS で実行中，衝突警告アプリケー
ションと同様に優先度「高」で実行されるため，優先度逆転が生じる．NPS の期間は，一つの入力データを最初のオペレータ
から最後のオペレータまでクエリで処理する時間となるため，

優先度逆転時間は最大でも 280us に留まる．従ってクエリコン
テキスト共有方式による優先度逆転時間の削減効果が示された．

5. 4 処 理 時 間[6]各方式のクエリの処理時間の評価結果を述べる．図 1 に示す
ように，クエリ処理共有方式では，二つのアプリケーション向
けのクエリの処理を共有することにより，共有化しない場合と[7]比較しクエリの処理時間を半分に削減することができる．またNPS を導入するクエリコンテキスト共有方式でも同様にクエ[8]

リの処理時間を半分に削減することができる．一方，NPS を導入しないクエリコンテキスト共有方式では，タスク切り替え
時にクエリを処理中の場合に，ロールバックを行い切り替え先のタスクで，クエリ処理を再実行する．一つの入力データを最初のオペレータから最後のオペレータまでクエリで処理する時
間は 280us であるため，クエリ処理共有方式と比較し，最大で280us 処理時間が増加する．したがってクエリコンテキスト共有方式のクエリ処理共有方式と比較した場合のクエリの処理時間の増加は最大でも 2.13% に留まり，十分，小さいことが示された．
なお本評価におけるクエリの処理時間は，クエリ内のオペ
レータの処理時間であり，ロールバックや，変更履歴の書き込
み，RTOS 内の処理で発生する処理オーバヘッドは考慮していない．上記の処理オーバヘッドを含めた処理時間の評価は今後の課題とする．

6. お わ り に
本稿では，車載システムのスケジューリングの元で，クエリの処理を効率化する，クエリコンテキスト共有方式を提案する．
クエリコンテキスト共有方式では，アプリケーションに合わせて異なる優先度でクエリを実行しつつ，優先度の異なるタスク
において処理が等価なクエリのコンテキストを共有する．そしてクエリの実行を中断しタスクを切り替える際に，前のクエリの出力データをアプリケーションを利用し，また前のクエリの処理を引き継ぐ．クエリコンテキスト共有方式を評価した結果，クエリ処理共有方式と比較し優先度逆転時間を低減し，また処理時間の増加も 2.13% に留まり，クエリの処理効率化の効果を示した．今後の課題としては，処理時間等に関するより詳細な評価や，部分的に同一の処理内容を持つクエリのコンテキスト
共有化などが挙げられる．
文

献[1] 山田真大，鎌田浩典，佐藤健哉，手嶋茂晴，高田広章: データス
トリーム管理機構を利用した車載データ統合モデルの提案と評
価，自動車技術会論文集，Vol.42, No.2, 2010.
[2] 勝沼 聡，山口 晃広，熊谷 康太，本田 晋也，佐藤 健哉，高田 広
章: 車載組込みシステム向けデータストリーム管理システムの開発，電子情報通信学会論文誌 Vol. J95-D, No.12, pp.2031-2047,
Dec, 2012．
[3] 山口 晃広, 本田 晋也, 佐藤 健哉, 高田 広章: 車載システム向け
データストリーム管理システムにおけるクエリ自動構築手法, 第11 回情報科学技術フォーラム講演論文集, Vol.2, pp.7-14, 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:

[9]
[10]

Query Processing, Resource Management, and Approximation in a Data Stream Management System, Conference on
Innovative Data Systems Research (CIDR), 2003.
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.
J. Chen, D. J. DeWitt, and J. F. Naughton: Design and
Evaluation of Alternative Selection Placement Strategies in
Optimizing Continuous Queries, ICDE 2002.
渡辺陽介, 北川博之: 連続的問合せに対する複数問合せ最適化手法, 電子情報通信学会論文誌，Vol. J87-D-I, No. 10, pp.
873-886, 2004.
ZMP: RoboCarR 1/10 / ZMP RC-Z, http://www.zmp.co.jp/enuvo/jp/robocar-110.html.
Borealis Distributed Stream Processing Engine,
http://www.cs.brown.edu/research/borealis/public/.