組込みシステムの世界では、マルチコアプロセッサが一般的に使用されています。
中でも、負荷分散型のSMP（Symmetric Multiprocessing；対称型マルチプロセッシング）に対応したCPUやOSも広く使用されています。
しかし、単純にシングルコア環境で開発されたソフトウェアをSMP環境で動作させても、性能が向上するわけではありません。それどころか、正常に動作しない可能性すらあります。
マルチコアプロセッサ環境では、複数の処理が完全に並列で実行されます。そのため、ソフトウェアを正常に動作させるには、適切な排他・同期制御が必要です。
ただし、マルチコア対応のために、新しい特別な技術が必要なわけではありません。基本となるのは「マルチタスク・プログラミング」です。
そこで、本ブログ記事ではマルチタスク・プログラミングの基礎のうちスケジューリングについて説明します。
※本ブログ記事はCQ出版社刊「Interface 2007年11月号」の特集「マルチタスク／マルチコア時代の並列処理技術」の第一章に掲載された記事を再編したものです。
目次
マルチタスク・プログラミングとは
これに対して、マルチタスクとは、一台のコンピュータシステム（処理装置）で同時に複数の処理（タスク）を並行して実行する機能のことです。
例えば、1台のパソコンでCDの音楽を聴きながら、Webサイトを閲覧し、ワープロソフトでレポートを書くことができます。
この例では、音楽再生ソフトとWebブラウザ、ワープロソフトを同時に実行しているため、マルチタスク環境を利用していることになります。
近年のOSでは、パソコン用だけでなく、組込み用のOSでもマルチタスクが標準となっています。複数の処理を同時に行いたいという要求が高まっているためです。
次に、マルチタスク・プログラミングがどのような原理で複数の処理を同時に実行しているかについて説明します。
最も簡単にマルチタスクを実現する方法は、「タスクの数だけプロセッサを用意する」ことです。
マルチタスクを実現したいコンピュータシステムに、同時に実行するタスクの最大数以上のプロセッサ（コア）が搭載されていれば、空いているプロセッサに実行するタスクを割り振るだけで、マルチタスク・プログラミングを実現することが可能です（図1）。
図1 プロセッサがたくさんあれば、マルチタスクは容易に実現できる
とはいえ、一般的なパソコンや組込みシステムでは、経済性、消費電力、物理サイズの制約から、プロセッサを多数搭載するケースはほとんどありません。
そのため、マルチタスク・プログラミングでは、複数のタスクを高速に切り替えながら実行することで、見かけ上、同時に動いているように見せています。
具体的には、一つのプロセッサの処理時間を分割して、複数のタスクに割り当てることで、複数のタスクの同時実行を実現しています。
この分割したプロセッサの処理時間をどのタスクに割り当てるかを管理することを「スケジューリング」と呼び、マルチタスク・プログラミングにおいて重要な概念となります。
つまり、「プロセッサに、複数ある処理のうちどの処理を行わせるのかを指示する」ことがスケジューリングです。日常生活における「スケジュールを決める」というのと同じ意味ですね。
スケジューリングの基準と分類
マルチタスク・プログラミングのスケジューリングにはさまざまな方式（スケジューリング・アルゴリズム）が提案されていますが、すべてのスケジューリング・アルゴリズムを理解することは困難です。
そこで、ここでは主要なスケジューリング・アルゴリズムと、それらを選択する際のポイントを説明します。
まず、スケジューリング・アルゴリズムを比較する際の基準を表1に示します。
表1 スケジューリングの基準
| CPU利用率 | CPU稼働時間÷システム稼働時間 （システム稼働時間＝CPU稼働時間＋アイドル時間） |
| スループット | 単位時間あたりの完了タスク数 |
| ターンアラウンド時間 | タスクの実行要求から完了までの時間 （CPU時間＋各種待ち時間） |
|
待ち時間 |
タスク完了までに実行可能状態で待つ時間 |
|
応答時間 |
タスクの実行要求から最初の応答までの時間 （応答出力の時間ではない） |
スケジューリング・アルゴリズムにさまざまな手法が存在するのは、構築するシステムによってマルチタスク・プログラミングに求められる要求仕様が異なるからです。
システムの要求を満たすため、さまざまなアルゴリズムが考案されてきました。
エンジニアは、スケジューリング・アルゴリズムを選択する際に、この基準に基づいてシステムの要求仕様を満たすアルゴリズムを探すことになります。
表1の例では、「とにかくCPUを有効に使いたい」場合、CPU利用率を重視したスケジューリング・アルゴリズムを採用します。組込み系なら応答時間を重視したものを採用することが多いでしょう。
次に、スケジューリング・アルゴリズムの分類について説明します。
スケジューリング・アルゴリズムは、表2のように横取り可能なもの（プリエンプティブ）と不可能なもの（ノンプリエンプティブ）の二つに分けることができます。
表2 スケジューリングの分類
| 横取り不可能な （ノンプリエンプティブ） スケジューリング・アルゴリズム |
プロセッサがあるタスクに割り付けられると、タスクがプロセッサを解放するまで、ほかのタスクには割り付けられない |
| 横取り可能な （プリエンプティブ） スケジューリング・アルゴリズム |
プロセッサが割り付けられたタスクが実行途中でも、プロセッサを他のタスクから横取り（プリエンプション）して、ほかのタスクに割り付けられる |
ここで出てくる「プリエンプティブ」とは何でしょうか。
まずは簡単なノンプリエンプティブから説明します。
ノンプリエンプティブなスケジューリングでは、タスクの実行する順番はOSが管理しますが、タスクの切り替えのタイミングは実行中のタスクが管理します。
タスク自身がプロセッサを解放しない限り、他のタスクに処理を横取り（プリエンプション）されることはありません。
つまり、「途中で他のタスクに処理を止められることはない」ということです。
逆に、プリエンプティブなスケジューリングでは、タスクを切り替えるタイミングもOSが管理するため、タスクの実行中にOSが他のタスクにプリエンプションすることが可能です。
プリエンプティブなスケジューリングは、「途中で他のタスクに処理を止められ、待たされる」といった状況です。
主なスケジューリング・アルゴリズム
それでは、スケジューリングの基準と分類を理解したところで、主なスケジューリング・アルゴリズムを表3に紹介します。
ここで紹介するスケジューリング・アルゴリズムは、基本的なものだけです。
マルチタスクOSは、単純にこの中の一つに対応しているわけではありません。
この中のスケジューリングをベースに改良を加えたり、複数のスケジューリング・アルゴリズムを組み合わせたりして、さまざまなアルゴリズムを作り出しています。
表3 主なスケジューリング・アルゴリズム
| ノンプリエンプティブ |
到着順（FCFS：First Come First Served）スケジューリング |
|
| 最短時間順（SJF：Shortest Job First）スケジューリング |
|
|
プリエンプティブ |
優先度（Priority）スケジューリング |
|
| ラウンドロビンスケジューリング |
|
大ざっぱに言うと、パソコンで使われるWindowsやUNIXはプリエンプティブなラウンドロビンスケジューリングを採用しており、組込みOSはプリエンプティブな優先度スケジューリングを採用しています。
スケジューリングを実際に行うソフトウェア（モジュール）をスケジューラと呼び、マルチタスクOSではこのスケジューラがOSの核となる機能です。
組込みシステムの「マルチタスク・プログラミング」とは
ここまでは、マルチタスク・プログラミングの基本的な概念として、スケジューリングについて説明しました。
基本的な概念を理解していただいた上で、次は組込みシステムのマルチタスク・プログラミングについて説明します。
組込みシステムでは、リアルタイム性の実現が非常に重要です。
そのため、マルチタスク・プログラミングにおいてもリアルタイム性が重視され、単なるマルチタスクOSではなく、リアルタイム・マルチタスクOSが採用されます。
ここからは、組込みシステムで多く採用されているμITRONを実例に挙げ、リアルタイム性を考慮した組込みシステムのマルチタスク・プログラミングについて説明します。
リアルタイム・マルチタスクOSでは、ほとんどのOSがイベントドリブン・プリエンプション方式のスケジューリングを採用しています。
ここで新たに登場する「イベントドリブン」という言葉は、「イベントの発生をトリガ（きっかけ）とする」という意味です。
コンピュータにおけるイベントとは、「キーが押された」、「マウスがクリックされた」、「ある端子が”H”から”L”になった」などのきっかけのことです。
つまりイベントドリブンとは、こうしたイベントの発生をきっかけにアクションを起こすことです。
イベントドリブン・プリエンプション方式とは、イベントの発生をトリガとして、優先度の高いタスクが優先度の低いタスクをプリエンプションさせるスケジューリング方式です（図2）。
この方式では、イベントを基準とした時間の制約がリアルタイム性を実現する重要な要素となります。
図2 イベントドリブン・プリエンプション方式
一方、プロセッサの処理時間を均等に割り当てるタイムシェアリング方式では、イベントが発生しても、イベントに対応したタスクの処理の順番が来るまで処理は実行されません。
さらに、割り当てられたプロセッサの処理時間内にタスクが完了しなければ、次の処理が割り当てられるまで、待ち時間が発生します（図3）。
これでは、リアルタイム性を実現できません。
図3 タイムシェアリング方式ではリアルタイム性の実現は不可能
イベントドリブン・プリエンプション方式では、まずイベントがトリガとなりタスクの切り替えを行います。この時、緊急度の高いタスクは、優先度を高く設定しておくことで、すぐにタスクを実行することが可能です。
しかも、より優先度の高いタスクが実行されない限り、処理が完了するまでタスクは実行し続けることが可能です（図4）。
このように、イベントドリブン・プリエンプション方式のスケジューリングは、リアルタイム・マルチタスクOSでは欠かせない存在です。
図4 割り込みが入っても優先度が高ければ、プリエンプションされない
イベントドリブン・プリエンプション方式は、リアルタイム性を実現するためのスケジューリング方式ではありますが、実際には適切なタスク分割と優先度の設定を行わなければ、リアルタイム性を実現することはできません。
つまり、「どの処理を優先的に処理するべきか？」、「そのためには処理をどのようにタスク単位に分割するか？」を考えなければなりません。
例えば、図5の処理Aと処理Cのように「連続して実行する必要があり、かつ優先度が異なる二つの処理を一つのタスクAにまとめ、優先度は高い方に合わせて設定」したとします。
この場合、タスク内で優先度の低い処理を実行している間は、実行中の処理より高い優先度であっても、タスク自体としてはより低い優先度で設定されている別のタスクは実行できません。
このような状況を回避するためには、処理Ａと処理Ｃを別々のタスクに分割し、それぞれのタスクに適切な優先度割り付けを行うことが必要となります。
図5 タスク分割と優先度の割り付けは重要
この例では、処理Aと処理CをそれぞれタスクAとタスクCに分割しています。
この作業により、A→C→Bの順に実行されていた処理が、A→B→Cの順に実行されるようになります。
しかし、処理を単純に細かく分割すればよいかというと、そうではありません。タスクの数が増えすぎると、タスク切り替えによるオーバヘッドが発生します。
そのため、処理の要求仕様を正確に把握した上で、適切なタスク分割を行うことが重要です。
最後に
本ブログ記事では、マルチタスク・プログラミングの基礎として、スケジューリングの基本概念についてご紹介しました。
eSOLでは、長年にわたるリアルタイムOSの開発実績を活かし、シングルコア環境で開発されたソフトウェア資産を、マルチコア環境へスムーズに移行するための支援サービスも提供しています。
リアルタイム性を求められる組込み開発において、最適なマルチタスク設計・実装をご検討の際は、ぜひお気軽にご相談ください。
ビジネスマネジメント本部 技術営業部 T.M
