Occam言語による マルチプリエンプティブシステムの 実装と検証 首都大学東京 理工学研究科 数理情報科学 福永研究室 田中 和人 目次 本研究の背景 開発環境 研究テーマ 並列プロセッサTPCORE 並列プログラミング言語Occam リアルタイムシステムとは TPCOREの問題点 マルチプリエンプティブシステム 検証とまとめ、今後の課題 2008/1/28 首都大学東京 修士論文発表会 2 本研究の背景（1） 当研究室では、並列プロセッサTPCOREを用いて 研究を行っている。 並列処理においては、処理する順番と処理を 切り替えるタイミングが重要であり、 このアルゴリズムをスケジューリングという。 このTPCOREで並列処理を実行する際、その処理に 時間的制限が加わると、スケジューリングの問題 からその制限を満たせない場合がある。 2008/1/28 首都大学東京 修士論文発表会 3 本研究の背景（2） これを解決するためのアルゴリズムがいくつか 提案されている。 本研究は、これらのアルゴリズムをTPCORE上で実行 させると共に、性能の検証を行ったものである。 2008/1/28 首都大学東京 修士論文発表会 4 並列プロセッサTPCORE 当研究室の過去の研究で開発した並列プロセッサ である。 英Inmos社の並列プロセッサTransputerをモデルに して開発されており、互換性を持っている。 2008/1/28 首都大学東京 修士論文発表会 5 並列プログラミング言語Occam（1） Transputerのために 開発された言語であり、 TPCORE上でも動作可能 逐次プロセスと並列プロセス の記述が可能 チャンネルを用いてプロセス 間の同期通信の記述が可能。 2008/1/28 CHAN OF INT ch1; PAR SEQ ‥‥‥‥ 逐 次 a := b+c プ 並 ch1 ! a ロ 列 ‥‥‥‥ セ プ ス SEQ ロ 逐 セ ‥‥‥‥ 次 ス ch1 ? x プ y := x ロ ‥‥‥‥ セ 首都大学東京 修士論文発表会 ス 例1 6 並列プログラミング言語Occam（2） プロセスには優先度を与える ことができ、重要なプロセスは 優先的に処理される。 優先度は二種類であり、 例2のように高優先度プロセス を指定する事ができる。 TPCORE、Transputerでは 複数プロセスの並列処理を 1台で行うことができる。 2008/1/28 PRI PAR p0 p1 p2 首都大学東京 修士論文発表会 高 低 低 例2 7 リアルタイムシステム システム ： 入力に対して、いくつかのプロセス（処理）を経て出力する 主体 リアルタイムシステム： プロセスの完了に制限時間が加えられたシステム 2008/1/28 首都大学東京 修士論文発表会 8 TPCOREのスケジューリング プロセス実行順序 優先度順 （但し、同優先度の場合は起動要求順） 実行するプロセスの切り替え 実行プロセスが待機状態になったとき 低優先度プロセス実行時に高優先度プロセスが起動した 高優先度待ち行列 p1 p2 低優先度待ち行列 p0 p3 2008/1/28 p4 首都大学東京 修士論文発表会 9 TPCORE上でリアルタイムシステム 構築時の問題点 例） 同優先度のプロセス1、プロセス2が並列処理 プロセス2の 制限時刻超過 プロセス1： 起動時刻＝ 0[μs] 実行時間＝ 400[μs] 制限時刻＝1000[μs] プロセス2： 起動時刻＝ 100[μs] 実行時間＝ 200[μs] 制限時刻＝ 500[μs] プロセス1 プロセス1実行中 プロセス2 0 100 200 300 プロセス2起動要求 2008/1/28 首都大学東京 修士論文発表会 400 500 600 時間 [μs] プロセス2制限時刻 10 マルチプリエンプティブシステム 全プロセスに異なる優先度を付加させる → 高優先度プロセスによる多重割り込み （マルチプリエンプト）が可能である Occam環境において提案されている アルゴリズムが３つあり、それらを使用した。 2008/1/28 首都大学東京 修士論文発表会 11 CFS（Central Fixed Scheduling） P0,P1,P2・・・の順に高優先度 制限時間の短い順に高優先度を与える セントラル方式 優先度付加機構 Kernel : 制御プロセス 各Pに優先度を付加 kernel P : システムに与えられた処理（タスク） を実際に行うプロセス P0 P1 2008/1/28 P2 ・・・ Pn-1 首都大学東京 修士論文発表会 12 CFS～P1が起動し実行される様子～ １．「P1が起動」 → 「Kernelにシグナル送信」（起動を知らせる） ２．「下位Pからのシグナル受信を拒否」 ３．「P1は実行を続ける」 ４．「P1の実行が完了」→「Kernelに実行結果送信」（完了を知らせる） ５．「下位Pからのシグナル受信を許可」 下位Pは起動しても 同期通信のため、 シグナルを送信できないので 待機する Kernel P0 P1 P2 ・・・ Pn-1 実行 2008/1/28 首都大学東京 修士論文発表会 13 CFS～P0による割り込み時の様子～ １．「P1が実行中、上位のP0が起動」 ２．「P0より下位Pのシグナル受信を拒否」 ３．「P0は実行を続ける」 ４．「P0の実行が完了」→「Kernelに実行結果送信」（実行完了を知らせる） ５．「P1は実行再開」 P1は シグナル送信ができるようになる 2008/1/28 P1は実行の際の シグナル送信が できないので待機する。 Kernel P0 P1 実行 実行 P2 ・・・ Pn-1 首都大学東京 修士論文発表会 14 PFS （Pararell Fixed Scheduling） CFSを改良したもの 優先度の付加をKernelでなく各Pで行う パラレル方式 Kernel : 制御プロセス kernel P0 P1 P2 ・・・ Pn-1 P : システムに与えられた処理（タスク） を実際に行うプロセス。 優先度付加機構 2008/1/28 首都大学東京 修士論文発表会 15 PFS～ P1が起動し実行される様子～ １．「P1が起動」→「下位Pへシグナル送信」 ２．「P1は実行と上位Pからのシグナル受信待機を繰り返す」 ３．「P1は実行完了」→「下位Pへシグナル送信」 ４．「Kernelへ結果送信」 Kernel P0 P1 P2 ・・・ Pn-1 実行 2008/1/28 首都大学東京 修士論文発表会 16 PFS～上位Pによる割り込み時の様子～ １．「P1が実行中、P0が起動」→「P0から下位Pへシグナル送信」 ２．「P0実行完了」→「Kernelへ結果送信」 ３．「下位Pへシグナル送信し、P1は実行再開」 Kernel P0 P1 P2 ・・・ Pn-1 実行 2008/1/28 首都大学東京 修士論文発表会 17 CDS（Central Deadline Scheduling） プロセスの構成はCFSと同様 Kernelに優先度を変更するための プログラムを追加している あるPが実行を完了した際、制限時間の近い順に 優先度を並べ替える 2008/1/28 首都大学東京 修士論文発表会 18 CDS～P0が起動し実行後、P1が起動～ １．「P0が起動」 → 「Kernelにシグナル送信」（起動を知らせる） ２．「下位Pからのシグナル受信を拒否」 ３．「P0は実行を続ける」→ 「P0の実行が完了」 ４．「P1が起動」→ 「下位Pのシグナル受信を拒否」 ５．「P1は実行を続ける」 P0は完了したため、制限時間 は延びた。次の制限時間まで の時間によって優先度が変わる Kernel 0 2 P0 実行 2008/1/28 1 0 2 1 P1 n-1 P2 Pn-1 実行 首都大学東京 修士論文発表会 19 CFS,CDS,PFSの検証 これらのシステムは3つとも問題点を解決できるが、 この中でより優れたシステムを検証する。 検証方法 プロセスPの個数を増やし、スケジューリング処理による負荷 の変化を観察し、その負荷がより少ないシステムが優れてい るといえる。 負荷 ： その処理がプロセッサを使用する割合 2008/1/28 首都大学東京 修士論文発表会 20 検証結果（1） 40 X軸はプロセスPの個数 Y軸はプロセッサにかける負荷 35 30 25 CFS CDS PFS 20 15 10 5 0 1 2 3 4 5 6 このグラフはそれぞれのシステムにおいて 並列処理プロセスPを変えたとき(１～6個)の スケジューリングによる負荷の変化を計測したものである。 2008/1/28 首都大学東京 修士論文発表会 21 検証結果（2） PFSが最もスケジューリング処理による 負荷が少なく、優れたシステムであった。 → PFSではKernelを介さず、P同士のやりとりだけで どのPが起動しているかを知ることができる。 これにより、Kernel部分の負担が減ったと考えられる。 2008/1/28 首都大学東京 修士論文発表会 22 まとめ TPCOREへのリアルタイムシステム実装において、 優先度が足りなくなり、制限時間内に完了できな いプロセスが出てくるという問題を解決できる システムをいくつか実装した それらのシステムの中でプロセッサ負荷の観点 から最適なシステムがPFSであるという検証を 行い、ハードウェア実装の指針を提案した。 2008/1/28 首都大学東京 修士論文発表会 23 今後の課題 １． PFSよりもさらに最適なシステムの設計 ２． 最適なシステム（のアルゴリズム）を ハードウェア的に実現 2008/1/28 首都大学東京 修士論文発表会 24
© Copyright 2024 ExpyDoc
