(cache) マルチプロセッサ用リアルタイムOSの解説

マルチプロセッサ用リアルタイムOSの解説

名古屋大学　石田です．これから，連載ブログ「マルチプロセッサ用リアルタイムOSの解説」を担当します．

本連載は，シングルプロセッサ用のリアルタイムOSの内部構造はある程度ご存知の方を対象に，マルチプロセッサ用リアルタイムOSの内部構造を解説していきます．

マルチプロセッサは適用分野によって，求められる機能や性能が異なります．そして，様々なハードウェアアーキテクチャが存在します．そんなマルチプロセッサ用のリアルタイムOSの設計方針は，その上で動くアプリケーションの性能に大きく関係してきます．したがって，最適なマルチプロセッサ用のリアルタイムOSを選択するには，ある程度OSの内部構造を理解する必要があります．
これから，マルチプロセッサ用リアルタイムOSの導入をご検討される方，また，マルチプロセッサ用リアルタイムOSについて勉強されたい方などの参考になれば幸いです．

ここでは，2009年に公開予定のTOPPERS/FMPカーネルのソースコードを詳しく見ていきたいと思っています．

どうぞ，おつきあいください．

本連載を始めるにあたって，名古屋大学　高田広章教授，本田晋也助教に，ご指導と，多大なるご協力をいただきました．また，両名が作成されました発表資料等を参考に書かせていただきました．ここに感謝させていただきます．
TOPPERSプロジェクトの成果物である，TOPPERS/FMPカーネルを使用させていただきました．感謝いたします，ありがとうございました．

連載初回である今回は，マルチプロセッサのハードウェアアーキテクチャにはどんなタイプのものがあるのか，そして，マルチプロセッサ用リアルタイムOSにはどんなものがあるのか，といったお話をします．

ハードウェアアーキテクチャから見たマルチプロセッサの分類

まず，マルチプロセッサをハードウェアアーキテクチャで分類します．マルチプロセッサを構成するプロセッサの種類による分類と，メモリ構成による分類をします．

(1)プロセッサの種類による分類

・均質（Homo）

・非均質（Hetero）

命令セットや性能が同じプロセッサで構成されているものを，均質（Homo），そうでないものを，非均質（Hetero）と呼びます．（図１）

(a)Homo

(b)Hetero

【図１　プロセッサの種類による分類】

Homoの場合は，すべて同じプロセッサであるメリットをいかして，動的負荷分散のために使用されることが多く，複数のデータやタスクを並列処理することで，処理能力を上げています．
一方Heteroの場合は，図1(b)のように，携帯電話に搭載されるコンボチップに見られるように，CPUとDSPのように全く異なるアーキテクチャで構成されているものもありますし，またCPUでも命令セットや性能が異なるCPUで構成されているものもあります．Heteroなマルチプロセッサは，解決しようとする問題に最適なアーキテクチャの構成にすることが可能です．しかし，プロセッサ間のインターフェースや開発ツールの問題など，使用するにはHomoの場合より複雑になる傾向があります．

(2)メモリの構成による分類
まず，マルチプロセッサを構成する各プロセッサがメモリを共有するか，しないかで分類できます．すべてのプロセッサでメモリを共有するものを“共有メモリ型（Shared Memory）”,共有しないものを“メッセージ交換型（Message Passing）”といいます．
次に，共有メモリ型の中でも，各プロセッサからメモリが対等に見えるかどうかで分類できます．対等に見えるものを”対称共有メモリ型（Symmetric Shared-Memory）”,対等に見えないものを“分散共有メモリ型（Distributed Shared-Memory）”といいます．

●共有メモリ型（Shared Memory）

 ・対称共有メモリ型（Symmetric Shared-Memory）

   →(1)UMA（Uniform Memory Access）と同義

 ・分散共有メモリ型（Distributed Shared-Memory

   →(2)NUMA（Non-Uniform Memory Access）と同義

●メッセージ交換型（Message Passing）

→(3)NORAまたは，NORMA　(No Remote Memory Access)と同義

※本ブログでは，UMA，NUMA，NORAを使用します．

【図2　マルチプロセッサのメモリ構成による分類】

次に各ハードウェアアーキテクチャを解説します．

(1)対称共有メモリ型（UMA）

UMAとは，全プロセッサが共有メモリに対して対等にアクセスするように設計されたメモリアーキテクチャです．つまり，各プロセッサと共有メモリの距離が等しいので、アクセス速度が等しいことを意味します．また、すべてのプロセッサが共通のメモリアドレス空間を持ちます．よって，このタイプのマルチプロセッサでは，どのタスクでプログラムを実行しても性能は変わりません．また，単一のメモリにアクセスが集中するため，多くの場合コヒーレントキャッシュを持ちます．

【図3　UMA型マルチプロセッサの構造】

すべてのプロセッサから同一のメモリにアクセスをするため，他のプロセッサの処理によっては，メモリアクセスの競合が発生し実行時間が変わってしまい，その結果リアルタイム性が確保しにくいアーキテクチャと言えます．

(2)分散共有メモリ型（NUMA）

NUMAとは，全プロセッサが共有メモリに対して対等には見えず，アクセス速度などがプロセッサによって異なるメモリアーキテクチャのことをいいます．NUMA では，UMA と同様にすべてのプロセッサで共通のメモリアドレス空間を持ちます．全プロセッサから等価にアクセスできるグローバルなメモリの他に，プロセッサ専用のバスと接続されたメモリをもちます．（図4）．

【図4　NUMA型マルチプロセッサの構造】

メモリ種別をもう少し詳しく分類します（図5）．

●全プロセッサからアクセス可能
・グローバルメモリ
・ローカルメモリ/リモートメモリ
●特定プロセッサからのみアクセス可能
・プライベートメモリ

全プロセッサからアクセス可能な共有メモリのうち，すべてのプロセッサから同等にアクセスできるものを，グローバルメモリといい，各プロセッサに専用のバスとともに割り当てられるメモリを，ローカルメモリまたはリモートメモリといいます．また，NUMAの中には，特定のプロセッサのみアクセス可能なメモリを持っているものもあります，これを，プライベートメモリといいます．
他のプロセッサのローカルメモリへのアクセスは，自分のローカルメモリへのアクセスより負荷がかかります．

【図5　NUMAにおけるメモリ種別の分類】

NUMAでは，ソフトウェアの設計によって，各プロセッサからのメモリへのアクセスを分散させることができるので，UMA に比べるとプロセッサ間のメモリアクセスの競合が比較的生じにくく，プロセッサ数の多い大規模なマルチプロセッサシステムに適している，といったメリットがあります。
ここで，共有メモリ型ハードウェアアーキテクチャを図6にまとめます．

	Homo	Hetero
UMA	Homo-UMA型	Hetero-UMA型
NUMA	Homo-NUMA型	Hetero-NUMA型

【図6アーキテクチャから見た共有メモリ型マルチプロセッサの分類】

(3)メッセージ交換型（NORA）

NORAとは，共有メモリを持たず，各プロセッサはプライベートなメモリを持つものをいいます．各プロセッサは自分以外のメモリにはアクセスすることができません．メモリ空間を共有していませんので，プロセッサ間で通信が必要な場合は，メッセージを送受信することにより行います．よって，シリアル線などなんらかの通信手段を持ちます．

【図7　NORA型マルチプロセッサの構造】

マルチプロセッサ向けOSの必要性

マルチプロセッサ用OSを使用しないソフトウェア開発では，各プロセッサに独立にシングルプロセッサ用のリアルタイムOSを搭載していました．たとえば，図8のような例です．

null

【図8　マルチプロセッサ向けOSを使用しない場合の例】

このような例の場合，シングルプロセッサ用のOSを搭載しているため，プロセッサ間で処理を行う機能はサポートしていません．よって，例えばプロセッサ間でメッセージを送受信したいような場合は，アプリケーションで実現する必要があります．

例えば，プロセッサ間で同期・通信が必要な場合は，OSではなくアプリケーションで実現する必要があります．つまり，同期・通信の仕組みをアプリケーションごとに開発する必要があり，ある処理を別のプロセッサに移そうとすると，同期・通信部分のプログラムの作り直しが必要となる場合があります．

null

【図9　(a)プロセッサ間，(b)プロセッサ内同期・通信】

図9で示すように，Task1とTask2で同期・通信が必要な場合に，(a)ではプロセッサ間，(b)ではプロセッサ内の処理となります．プロセッサ内であれば，シングルプロセッサ用OSがサポートしている同期・通信機能を使用すればいいのですが，プロセッサ間の場合は，同期・通信機能をアプリケーションで用意する必要があります．同期・通信が必要な場合に，アプリケーションエンジニアにとっては，そのタスクが同一プロセッサに割り付けられているかそうでないかは，大きな違いとなります．

同じように，動的な負荷分散が必要な場合も，アプリケーションで実現する必要があります．こちらもアプリケーションごとに負荷分散の仕組みを開発する必要があります．

マルチプロセッサ用のOSで，プロセッサ間通信機能をサポートすれば，アプリケーションごとにプロセッサ間の同期・通信を実現する必要がないため，アプリケーションの開発工数が減少します．また，プロセッサ間の同期・通信と，プロセッサ内の同期・通信に互換性を持たせれば，同期・通信が必要な処理を別のプロセッサに移動する場合も，比較的容易に実現できます．アプリケーションエンジニアは，同期・通信を行うタスク同士が，同じプロセッサに割り付けられているかどうかを意識する必要はありません．

また，負荷分散の仕組みをサポートしているOSもあります．このようなOSでは，負荷に応じてスループットが最大になるよう処理（タスク，スレッド）を動的にプロセッサに割り当ててくれます．

OSサポートから見たマルチプロセッサの分類

ここでは，OSサポートの視点から見た場合のマルチプロセッサの分類を行います．先ほどの分類は，ハードウェア設計者の視点での分類でしたが，ここでの分類はリアルタイムOS設計者の視点と考えてください．分類結果はよく似ています．

●共有メモリを持つアーキテクチャに対応

(1)対照型マルチプロセッサ（SMP）

(2)機能分散型マルチプロセッサ（FDMPまたはAMP）

●共有メモリを持たないアーキテクチャに対応

(3)疎結合マルチプロセッサ（LCMP）

対称型マルチプロセッサ（SMP）とは，各プロセッサからどのメモリにもアクセスすることができ，どの処理をどのプロセッサでも実行できるものをいいます．それに対して，機能分散型マルチプロセッサ（FDMPまたはAMP）とは，各プロセッサからアクセスできるメモリに違いがあり，どの処理をどのプロセッサで行うかが決まっているようなものをいいます．
※FDMPをAMPと呼ぶ場合もありますが，本ブログではFDMPと記載します．
他には，疎結合マルチプロセッサ（LCMP）があります．これは，プロセッサ間で共有メモリを持たず，プロセッサ間通信をメッセージの送受信で実現するタイプのものと言えます．

(1)対称型マルチプロセッサ（SMP）

SMPは，アプリケーションプログラムから見ると，どのプロセッサも対等に見えます．この構成は，パソコンやワークステーションなどで一般的に用いられています．どのプロセッサも対等ですので，各タスクがいずれのプロセッサでも実行できます．そのためOSには，各プロセッサに負荷を分散することで高い処理性能を引き出すことが求められます．たとえば，複数のプロセッサを用いて，依存性のない複数の処理を並列に実行することでスループットの向上を図ります．
タスクをどのプロセッサで実行するかは，OSが決定して割り当てます．つまりタスクはプロセッサに動的に割り当てられます．アプリケーションエンジニアはどのタスクがどのプロセッサで実行されているか意識する必要はありません．

null

【図10　SMPの構造】

このSMP型OSが対象とするハードウェアアーキテクチャを，表1に示します．

【表1　SMP型OSが対象とするマルチプロセッサアーキテクチャ】

	Homo	Hetero
UMA	Homo-UMA型 ◎最も適している	ＢＢＢＢＢＢＢＢＢＢＢＢＢ
NUMA	Homo-NUMA型〇タスクの割り当て方法によっては性能にばらつきがでる．

次に，SMP型OSのメリットとデメリットについて見ていきましょう．

＜メリット＞
・動的な負荷分散が可能で，システムのスループットを向上させることが可能である．
・OSがタスクをプロセッサに動的に割り付けるため，アプリケーションの作りこみなしで，性能を上げられる可能性がある．
＜デメリット＞
・すべてのリソースを各プロセッサからアクセス可能とするために，高速で複雑なバスやコヒーレントキャッシュが必要不可欠．よって，ハードウェアのコストや消費電力は大きくなる傾向にある．
・動的な負荷分散を行うため，各タスクのリアルタイム性の保証が困難になる．

(2)機能分散マルチプロセッサ（FDMP）

FDMPでは，どのタスクをどのプロセッサで実行するかは，システム設計時にアプリケーションエンジニアが決定します．そのためOSは，プロセッサごとに独立にタスクスケジューリングを行えばよいことになります．組込みシステムの場合，パソコンなどと異なり，実行する処理が事前にわかっているケースが一般的であるため，FDMP型のマルチプロセッサシステムを用いることが多いといえます．分割した機能をそれぞれ，１つのプロセッサに専用に割り当て，全体としてシステムの機能を実現する方法です．
この方式は，アプリケーションエンジニアがタスクをプロセッサへ割り付ける必要があり，アプリケーション開発時の手間は増えます．つまり，タスクは静的にプロセッサに割り付けます．一方，特定のプロセッサのみからアクセスされるハードウェア資源を，そのプロセッサにローカルに接続することができるため，プロセッサ間の結合網にかかる負荷を下げることができ，ハードウェアのコストや消費電力を抑えることもできます．また，スケーラビリティやリアルタイム性の確保も，SMP型に比べると容易です．

【図11　FDMPの構成】

このFDMP型OSが対象とするハードウェアアーキテクチャを，表2に示します．

【表2　FDMP型OSが対象とするマルチプロセッサアーキテクチャ】

	Homo	Hetero
UMA	Homo-UMA型〇	Hetero-UMA型 △
NUMA	Homo-NUMA型 ◎最も適している	Hetero-NUMA型　 △

次に，FDMP型OSのメリットとデメリットについて見ていきましょう．

＜メリット＞
・機能を固定することで，ソフトウェア（OS）やハードウェア構成を用途に応じて最適化することが可能．
・プロセッサ間でコードを共有しないため，コヒーレントキャッシュ等の複雑な回路を必要としない．バス構成やメモリ階層を多段にして性能向上を図ることが可能．
・個別のプロセッサの性質はシングルプロセッサに近く，SMP型と比較してリアルタイム性の保証が容易．
＜デメリット＞
・OSでは動的な負荷分散をサポートしていないため，アプリケーションレベルで実現する必要がある．

(3)疎結合マルチプロセッサ（LCMP）

プロセッサ間で共有メモリを持たないLCMP型では，OSの内部情報を管理するデータ構造はプロセッサごとに持ちます．また，プロセッサ間通信はメッセージの送受信によって行います．LCMP型では，一般にプロセッサ間の通信にかかる遅延が大きくなります．そのため，他のプロセッサに処理を依頼する場合に，小さい粒度の処理を何度も依頼するのは効率が悪く，なるべく大きい粒度で処理を依頼するべきです．つまり，他のプロセッサに依頼するのは，OSのシステムコールのような粒度の小さい処理ではなく，アプリケーションレベルの大きい粒度の処理とします．

【図12　LCMPの構成】

このLCMP型OSが対象とするハードウェアアーキテクチャは，NORA型です．

今回は，マルチプロセッサをハードウェア設計者の視点で，アーキテクチャによる分類を，そしてリアルタイムOS設計者の視点でOSサポートを考えた場合の分類を行いました．次回は，マルチプロセッサ用リアルタイムOSのスケジュール方法とレディキューの概要を解説します．

第1回では，マルチプロセッサの多様性について解説しました．今回は，マルチプロセッサ用リアルタイムOSの構造について，スケジューリングとレディキューの構造の観点で解説します．FDMP型（機能分散マルチプロセッサ）OSとSMP型（対称型マルチプロセッサ）OSで採用されるスケジューリング方法とレディキューの構造について見ていきます．

シングルプロセッサ用OSでのスケジューリング方法とレディキューの構造

シングルプロセッサ用リアルタイムOSの例で，スケジューリングとレディキューについて簡単に復習をしたいと思います．

シングルプロセッサの場合には，同時に実行できるタスクは実際には一つです．一つしかないプロセッサを，あたかも複数あるかのように見せる機能のことを，マルチタスク機能といいます．リアルタイムOSはマルチタスク機能を使って，あたかもプロセッサが複数あるかのように複数のタスクを並列実行させています．つまりマルチタスク機能の実現には，複数のタスクを時分割で実行しなくてはいけません。このタスクの実行順序を決めることをスケジューリングと呼び，その方式をスケジューリング・アルゴリズムといいます。一般にスケジューリングとは，「いつ」「どのタスク」を実行するかを決定することを指しますが，将来どのタスクを実行するかの計画をあらかじめ立てているわけではなく，次に実行するタスクを決めることをスケジューリングと呼んでいます。
シングルプロセッサ用のリアルタイムOSであるTOPPERS/ASPカーネルのスケジューリング方法は，多くのリアルタイムOSが採用している「プリエンプティブな優先度ベーススケジューリング」です．（「リアルタイムOSの内部構造を見てみよう」第２回を参照）
そして，スケジューリングを実現するために，実行可能状態のタスクを管理しているのがレディキューで，システム全体で１つ存在します（図1）．

null

【図1　シングルプロセッサにおけるレディキュー】

では，マルチプロセッサ用リアルタイムOSでは，どのようになるのでしょうか？

FDMP型OSでのスケジューリング方法とレディキューの構造

FDMP型OSでのリアルタイムOSでは，タスクは静的に割り付けられたプロセッサでのみ処理を行います．タスクは動的に他のプロセッサに移動しませんので，レディキューは各プロセッサごとに持ち，プロセッサごとに個別に管理することが可能です．また，各プロセッサはシングルプロセッサと同様にスケジューリングを行えばいいことになります．プロセッサを2つ持つマルチプロセッサに，FDMP型OSを適用した場合を図2に示します．プロセッサごとにレディキューを持ちますので，全体で2つのレディキューを持ちます．

null

【図2　FDMP型におけるレディキュー】

SMP型OSでのスケジューリング方法とレディキューの構造

SMP型OSでは．タスクはどのプロセッサでも実行できるという特徴がありました．そこで，SMP型OSでは，システム内に存在するタスクをすべて1か所で管理し，システム中の優先度の高いタスクから順に，プロセッサ個数分のタスクを各プロセッサに割り付けます．プロセッサを2つ持つマルチプロセッサに，SMP型OSを適用した場合を図3に示します．タスクはシステム全体で管理しますので，レディキューは全体で1つです．

null

【図3　SMP型におけるレディキュー】

つまり，このようなスケジューリングを行うためには，システム内の全タスクを管理するレディキューを１つ用意し，レディキューの先頭からプロセッサ個数分のタスクを実行させるスケジューリング方法が採用されます．タスクは基本的にどのプロセッサでも実行可能と書きましたが，システムによっては，タスクの実行できるプロセッサを固定する機能を持つものもあります．
このSMP型OSでのスケジューリング方法には，問題点が２つ考えられます．