Occam言語による マルチプリエンプティブシステムの 実装と検証 首都大学東京 理工学研究科 数理情報科学 福永研究室 田中 和人

目次 本研究の背景 開発環境 研究テーマ 検証とまとめ、今後の課題 並列プロセッサTPCORE 並列プログラミング言語Occam リアルタイムシステムとは TPCOREの問題点 マルチプリエンプティブシステム 検証とまとめ、今後の課題 2008/1/28 首都大学東京　修士論文発表会

本研究の背景（1） 当研究室では、並列プロセッサTPCOREを用いて 研究を行っている。 並列処理においては、処理する順番と処理を 切り替えるタイミングが重要であり、 このアルゴリズムをスケジューリングという。 このTPCOREで並列処理を実行する際、その処理に時間的制限が加わると、スケジューリングの問題 からその制限を満たせない場合がある。 2008/1/28 首都大学東京　修士論文発表会

本研究の背景（2） これを解決するためのアルゴリズムがいくつか 提案されている。 本研究は、これらのアルゴリズムをTPCORE上で実行させると共に、性能の検証を行ったものである。 2008/1/28 首都大学東京　修士論文発表会

並列プロセッサTPCORE 当研究室の過去の研究で開発した並列プロセッサである。 英Inmos社の並列プロセッサTransputerをモデルにして開発されており、互換性を持っている。 2008/1/28 首都大学東京　修士論文発表会

並列プログラミング言語Occam（1） Transputerのために 開発された言語であり、TPCORE上でも動作可能 逐次プロセスと並列プロセスの記述が可能 チャンネルを用いてプロセス間の同期通信の記述が可能。 CHAN OF INT ch1; PAR 　　SEQ ‥‥‥‥ a := b+c ch1 ! a ch1 ? x y := x 並 列 プ ロ セ ス 逐 次 プ ロ セ ス 逐 次 プ ロ セ ス 例1 2008/1/28 首都大学東京　修士論文発表会

並列プログラミング言語Occam（2） プロセスには優先度を与えることができ、重要なプロセスは優先的に処理される。 優先度は二種類であり、 例2のように高優先度プロセスを指定する事ができる。 TPCORE、Transputerでは 複数プロセスの並列処理を 1台で行うことができる。 PRI PAR p0 p1 p2 高 低 低 例2 2008/1/28 首都大学東京　修士論文発表会

リアルタイムシステム システム ： 入力に対して、いくつかのプロセス（処理）を経て出力する主体 リアルタイムシステム： プロセスの完了に制限時間が加えられたシステム 2008/1/28 首都大学東京　修士論文発表会

TPCOREのスケジューリング プロセス実行順序 実行するプロセスの切り替え 優先度順 （但し、同優先度の場合は起動要求順） 優先度順 （但し、同優先度の場合は起動要求順） 実行するプロセスの切り替え 実行プロセスが待機状態になったとき 低優先度プロセス実行時に高優先度プロセスが起動した p1 p2 高優先度待ち行列 p0 p3 p4 低優先度待ち行列 2008/1/28 首都大学東京　修士論文発表会

TPCORE上でリアルタイムシステム 構築時の問題点 例） 同優先度のプロセス1、プロセス2が並列処理 プロセス2の 制限時刻超過 プロセス1： 起動時刻＝ 0[μs] 実行時間＝ 400[μs] 制限時刻＝1000[μs] プロセス2： 起動時刻＝ 100[μs] 実行時間＝ 200[μs] 制限時刻＝ 500[μs] プロセス1実行中 プロセス1 プロセス2 100 200 300 400 500 600 時間 [μs] プロセス2起動要求 プロセス2制限時刻 2008/1/28 首都大学東京　修士論文発表会

マルチプリエンプティブシステム 全プロセスに異なる優先度を付加させる → 高優先度プロセスによる多重割り込み （マルチプリエンプト）が可能である Occam環境において提案されている アルゴリズムが３つあり、それらを使用した。 2008/1/28 首都大学東京　修士論文発表会

CFS（Central Fixed Scheduling） P0,P1,P2・・・の順に高優先度 制限時間の短い順に高優先度を与える セントラル方式 Kernel : 制御プロセス 各Pに優先度を付加 優先度付加機構 kernel P : システムに与えられた処理（タスク） を実際に行うプロセス P0 P1 P2 ・・・ Pn-1 2008/1/28 首都大学東京　修士論文発表会

CFS～P1が起動し実行される様子～ Kernel １．「P1が起動」 → 「Kernelにシグナル送信」（起動を知らせる） 同期通信のため、 シグナルを送信できないので 待機する Kernel P0 P1 P2 ・・・ Pn-1 実行 実行 実行 実行 実行 2008/1/28 首都大学東京　修士論文発表会

CFS～P0による割り込み時の様子～ Kernel １．「P1が実行中、上位のP0が起動」 ２．「P0より下位Pのシグナル受信を拒否」 シグナル送信ができるようになる P1は実行の際の シグナル送信が できないので待機する。 Kernel P0 P1 P2 ・・・ Pn-1 実行 実行 実行 実行 実行 実行 実行 実行 2008/1/28 首都大学東京　修士論文発表会

PFS （Pararell Fixed Scheduling） CFSを改良したもの 優先度の付加をKernelでなく各Pで行う パラレル方式 kernel Kernel : 制御プロセス P : システムに与えられた処理（タスク） を実際に行うプロセス。 P0 P1 P2 ・・・ Pn-1 優先度付加機構 2008/1/28 首都大学東京　修士論文発表会

PFS～ P1が起動し実行される様子～ Kernel １．「P1が起動」→「下位Pへシグナル送信」 ・・・ Pn-1 Pn-1 Pn-1 実行 実行 実行 実行 実行 2008/1/28 首都大学東京　修士論文発表会

PFS～上位Pによる割り込み時の様子～ Kernel １．「P1が実行中、P0が起動」→「P0から下位Pへシグナル送信」 ・・・ Pn-1 Pn-1 Pn-1 実行 2008/1/28 首都大学東京　修士論文発表会

CDS（Central Deadline Scheduling） プロセスの構成はCFSと同様 Kernelに優先度を変更するための プログラムを追加している あるPが実行を完了した際、制限時間の近い順に 優先度を並べ替える 2008/1/28 首都大学東京　修士論文発表会

CDS～P0が起動し実行後、P1が起動～ Kernel １．「P0が起動」 → 「Kernelにシグナル送信」（起動を知らせる） 2 1 1 2 n-1 P0 P1 P2 Pn-1 実行 実行 実行 実行 実行 実行 実行 2008/1/28 首都大学東京　修士論文発表会

CFS,CDS,PFSの検証 これらのシステムは3つとも問題点を解決できるが、 この中でより優れたシステムを検証する。 検証方法 負荷 ： その処理がプロセッサを使用する割合 2008/1/28 首都大学東京　修士論文発表会

検証結果（1） X軸はプロセスPの個数 Y軸はプロセッサにかける負荷 このグラフはそれぞれのシステムにおいて 並列処理プロセスPを変えたとき(１～6個)の スケジューリングによる負荷の変化を計測したものである。 2008/1/28 首都大学東京　修士論文発表会

検証結果（2） PFSが最もスケジューリング処理による 負荷が少なく、優れたシステムであった。 → PFSではKernelを介さず、P同士のやりとりだけで どのPが起動しているかを知ることができる。 これにより、Kernel部分の負担が減ったと考えられる。 2008/1/28 首都大学東京　修士論文発表会

まとめ TPCOREへのリアルタイムシステム実装において、優先度が足りなくなり、制限時間内に完了できないプロセスが出てくるという問題を解決できる システムをいくつか実装した それらのシステムの中でプロセッサ負荷の観点から最適なシステムがPFSであるという検証を 行い、ハードウェア実装の指針を提案した。 2008/1/28 首都大学東京　修士論文発表会

今後の課題 １． PFSよりもさらに最適なシステムの設計 ２． 最適なシステム（のアルゴリズム）を ハードウェア的に実現 2008/1/28 ２． 最適なシステム（のアルゴリズム）を ハードウェア的に実現 2008/1/28 首都大学東京　修士論文発表会