マルチプログラミング環境では、複数のプログラムがCPUの実行権を相互に切り換えながら、全体として同時並行的に処理を進行させる。このとき、CPUの実行権を切り替える単位を''タスク''または''プロセス''と呼ぶ。汎用コンピュータのOSではジョブステップ、UNIXなどのタイムシェリングOSではコマンドで実行させたプログラムがタスク(UNIXの習慣ではプロセスと呼ぶ)である。タスクの中から、他のタスクを起動することもできる。ユーザープログラムと直接結びついたタスクの他に実際のシステムでは、システム運用・管理や間接的なサービスを提供するようなタスクも存在する。UNIXではこのような役割を持つタスクを''デーモンプロセス''と呼ぶ。OSでは、プロセスを構成するルーチン(プログラムの断片)が別々のCPUで動くこともがある。そのOSの管理対象の単位を''スレッド''と呼ぶ。--プロセスA,Bのように、処理時間の中で入出力時間の占める割合が大きいプロセスを入出力バウンドのプロセスという。--大半の事務計算プログラムやオンライントランザクション処理は典型的な入出力バウンドのプロセスといえる。bound)プロセス--プロセスCのように、処理時間の中でCPU時間の占める割合が大きいプロセスをCPUバウンドのプロセスという。--科学技術計算のプログラムやプラントの実時間制御システムなどが該当する。人の側から見た仕事の単位を[[ジョブ]]というのに対して、OSの管理下で実行される仕事の単位を''タスク''と呼ぶ。ジョブが投入されたら、それを''ジョブステップ''ごとに、あるいはジョブステップをさらに分割してタスクを作り、タスクごとに実行されることになる。このタスクの実行を監視し、[[CPU]]や[[主記憶装置]]の管理や制御を行うことを、''タスク管理''という。「マークシートを読み込んで、試験の採点をして、結果をファイルに出力せよ」というジョブが投入されたとする。このとき、「マークシートを読み込む」というジョブステップ1、「試験の採点をする」というジョブステップ2、「結果をファイルに出力する」というジョブステップ3に分解される。その後、さらにそれぞれのジョブステップから単一あるいは複数のタスクが生成される。ジョブ管理によって、ジョブにはハードウェア資源が割り当てられる。仮想記憶装置なら、主記憶装置の割り当てられる。マルチプログラミングなら、CPUの割り当て、割り込み処理が使われる。タスクは、他のタスクにより生成(起動)される。タスク起動に際してはタスクを識別するためのタスク番号、タスク実行権の割り当てを管理するためのタスク優先順位が与えられる。タスクは自分自身を消滅させる場合と、他から消滅させられる場合とがある。タスクの生成・消滅を行うシステムコールが用意されている。ハードウェア資源の状態は、タスクを実行中に変化する。他のタスクが磁気ディスク装置を使っているので、処理が終わるまで待つ必要が出てきたりする。タスク管理によって生み出されたタスクは、すぐに実行できるとは限らない。タスクは次の3つの状態を取る。+実行可能状態--処理装置(CPU)の使用権が与えられれば、実行できる状態。---実行状態にあるタスクが他の状態に遷移すると、待ち行列中からひとつのタスクを選び、実行状態に遷移させる。---同一優先順位内での順番を決めるにはいくつかの方法がある。+実行状態--処理装置で実行している状態。---入出力が完了すれば、それを待っていたタスクは実行可能状態の待ち行列へ加えられる。+待機状態--入出力装置の処理が終わるのを待っている状態。---実行状態にあったタスクが他の状態へ遷移すると、OSのスケジューリング機能により、実行可能状態の中のタスクがひとつ選ばれて実行状態へ移される。---実行状態にあったタスクは、自ら明示的にWAITシステムコールを発行したり、入出力システムコールを発行することで待ち行列に遷移する。タイムシェリングシステムでタイムスライスが終わったときには、実行可能状態へ遷移させられる。---待ち状態にあるタスクに対するイベントが発生すれば、そのタスクは実行可能状態へ移され、待ち行列に加わる。[補講]現実のOSでは、この3つの他にいくつかの状態が設定されており、それらの状態間を遷移する。状態により遷移が変わってくる。その状態遷移図は次の通りである。処理装置(CPU)が与えらたら実行することができるが、実行状態2から実行状態1に戻っている矢印に注目して欲しい。実行していたタスクの処理を中断して、より優先順位の高いタスクが割り込むことがある。このとき、実行中のタスクはいったん中断して実行可能状態に戻り、優先順位の高いタスクが終了するのを待つ。-�→�--CPUの割り当て(ディスパッチング)---実行可能状態にあるタスクの中で、もっとも優先順位の高いタスクにCPUの使用権を割り当てる。-�→�--タイマ割り込み---タイマ割り込みが発生すると、実行状態にあるタスクが実行可能状態に移る。-�→�--スーパバイザコール割り込み---タイマ割り込みが発生すると、実行状態にあるタスクが待機状態に移る。-�→�--入出力処理の完了---入出力処理が完了すると、待機状態にあるタスクが実行可能状態に移る。複数のタスクがある同じ条件で待ち状態になった場合、条件の成立したタスクすべての待ち状態を同時に解除できるタスク間の同期制御方法を''イベントフラグ''という。''マルチプログラミング(多重プログラミング)''とは、主記憶上に複数のプログラムを置き、見かけ上複数のプログラムを同時に実行する方式のことである。最近はタスクレベルで考えて、''マルチタスキング''と呼ぶことが多い。マルチプログラミングにより、それぞれの入出力動作時のCPUの空き時間を利用して、他のプログラムを実行し、CPUの利用効率を向上させることができる。次のようなプログラム(タスク)A,Bをマルチタスキングで処理した場合の実行時間の短縮を考える。処理の優先度はAのほうが高く、入出力(I/O)動作は並列処理が可能であるとする。OSのオーバーヘッド((システム全体に関わる制御や管理などを行うのにかかる時間のこと。タスクスケジュールの管理の時間が該当する。))は考慮しなくてよいとする。||CPU|I/O|CPU|I/O|CPU||プログラムA|3ms|5ms|4ms|6ms|3ms||プログラムB|2ms|7ms|3ms|4ms|2ms|[1]マルチプログラミングで処理しない場合のタイムチャートは次のようになる。I/O処理実行時間である。この場合は、両方のプログラムが終了するまでの処理時間を合計すればよいことになる。プログラムAが21ms、プログラムBが18msの処理時間がかかるので、2つのプログラムが終了するには39msが必要である。[1]マルチプログラミングで処理する場合のタイムチャートは次のようになる。この場合は、I/O処理としてプログラムAを実行している間に、CPU処理としてプログラムBを実行できるからである。結果として、2つのプログラムが終了するには23ms必要であることがわかる。よって、[1]のときと比べて、16ms(=39ms−23ms)を短縮できたことになる。タイムチャートの�と�の部分は、''アイドル時間(遊休時間)''といい、ハードウェアが処理を何も行わずユーザーからの処理要求を待っているCPUの空き時間である。''PCB''とは、プロセスの生成の同時に作成されて、プロセスの活動中はプロセスの状態が記録される。プロセスに割り当てられている入出力装置もPCBによって管理されている。プロセス活動が終わればPCBも消滅する。タスクが何らかの理由で中断され、他のタスクが動いた後で、中断したところから再開するのに必要な情報を、そのタスクの''コンテキスト''((「文脈」の意。タスクの状態遷移があると、あるタスクのコンテキストから別のタスクのコンテキストへ切り換える必要がある。これを''コンテキストスイッチ''という。コンテキストとしては次が挙げられる。Block)''と呼ばれるテーブルに格納して、タスク制御プログラムが管理する。タスクを実行中でも、入出力割込みなどにより中断できる方式。マルチタスクだとこれが普通。複数のタスクにCPUが割り当てる時間をOSをあらかじめ決めておくのがポイントである。実行中の処理よりも優先度の高い別の処理要求が発生した場合には先に実行できる。multitasking:非協調型マルチタスク)''と呼ぶ。System)も、プリエンプティブマルチタスクの一種であり、短い時間間隔で複数のジョブを強制的に切り換えながら処理する。タスクの切り換えをOSが行わずに、複数のタスクを同時に処理しているように見せる方式で、タスクの切れ目で切り替えていく。アプリケーションの自主的な処理の解放を前提として、複数アプリケーション間で制御を切り替える。multitasking:協調型マルチタスク)''と呼ぶ。''擬似マルチタスク''と呼ぶこともある。特定のタスクがCPUを独占すると、他のタスクの処理が停止することがある。実行可能状態のタスクから実行状態に移すべきタスクを選び出す処理を、''スケジューリング''と呼ぶ。選び出すルールは、まずタスクの優先順位に従う。優先順位は、起動時に決められたものがずっと使用される静的なものと、動的に変化させるものとがある。入出力終了やコマンド入力などをの割込みをトリガーに実行する方式。マルチタスクにイベントドリブン方式を取り入れるとリソースの利用効率が向上する。タスクに時分割で処理装置を割り当てる方式を''タイムスライシング''と呼ぶ。1ms割り当てたとすると、実行可能状態のタスクにCPUを割り当てて実行状態にするが、処理が終わっていなくても1ms通過したらそのタスクを中断して実行可能状態に戻し、他のタスクに1ms割り当てる。マルチタスクにタイムスライス方式を取り入れるとシステム性能が向上する。プロセスを投入した順、即ちFIFOにより実行する。実行中のプロセスがタイムスライス(一定時間)内に終了できなかった場合にCPUを解放し、'''最後尾に'''再度連結し直す方式である。優先度の高いタスクからCPU時間を割り当てていき、優先度の高いタスクには、徐々に長いCPU時間を割り当てる方式。プロセスの優先度によって実行する。CPUから比べると圧倒的にプリンタは低速である。そのためプリンタの動作が完了するのを待っていると時間がかかってしまう。そこで印刷データを一旦補助記憶装置に出力し、CPUは次の処理を実行する。その後、補助記憶装置からプリンタへ適時印刷データが送られる。このような方式を''スプーリング(スプール)''と呼ぶ。あるタスクで使用したプログラムを、再ロードせずに繰り返し実行できるプログラムを''再使用可能プログラム''という。再使用可能プログラムは次のように分類される。-逐次再使用可能(リユーザブル)--単に再使用可能といったらこちらを指す。--ひとつのタスクだけが使用できる。同時には利用できない。-再入可能(リエントラント)--同時に複数のタスクが使用できる。逐次再使用可能プログラムは、実効によって変更された値を初期状態に戻すように作られている。一度実行した後、ロードし直さずに再び実行を繰り返しても、正しい結果が得られる。再入可能プログラムは、実行で変化しない部分をひとつ、変化する部分をタスクの数だけ持っている。複数のタスクで並行して実行しても、正しい結果が得られる。[補講]自分自身を呼び出せるプログラムを''再帰的プログラム''と呼ぶ。同期制御とは、複数のタスクの間で協調する機能である。排他制御は、相互干渉を避ける機能である。2つのタスクが共有するデータを、両方のタスクが更新する場合に、更新処理の途中で他方のタスクへ実行権が移ると、データの整合性が保証されなくなる。このように中断が許されない処理ステップを''クリティカルセクション''と呼ぶ。相互干渉があってはならない資源をアクセスする間は、それが完了するまで、他のタスクがその資源にアクセスできないようにする必要がある。これを保証することを''相互排他制御''という。複数のタスクが協調してある結果を得たいとき、ひとつのタスクがあることをしたら別のタスクがこれをする、といった具合に進行させるのは、実は相互排他制御の裏返しである。これを実現させる仕組みを''同期制御''という。''セマフォ(Semaphore)''とは、並列処理の実行環境において、排他区間を確保し、資源に同時アクセスできる上限を規定することにより、排他制御を実現化する仕組みのことである。同期制御や相互排他制御をカーネルの機能として提供する仕組みとしてよく知られている。ちなみに、セマフォとは、地方のローカル線で見られる腕木信号機のことで、列車を安全に運行するには、信号機と信号機の間にはただひとつの列車しか進入させないという考え方がこのアルゴリズムの根底にも流れている。セマフォは、カーネルの管理のもとに交通信号を青にしたり、赤にしたりするものと考えてよい。このセマフォの提唱者は、オランダの数学者Dijkstra(ダイクストラ)という人で、Unix系のOSで幅広く採用されている。セマフォでは、資源に対して割り当てられる(データ型の)変数のことである''セマフォ変数''が使われる。このセマフォ変数の値により占有状態がわかる。セマフォ変数にはP操作とV操作がある。-P操作=通行許可--セマフォ変数の値が0以外なら1を減じて実行を継続する。セマフォ変数の値が0ならば、0以外になるまで実行を停止する。--P(S)と記述する。---S≧1の場合、S←S-1とし、Pを実行したプロセスがそのまま実行を継続する。---S<1の場合、Pを実行したプロセスはSの待ち行列に入れられ、そのプロセスは待機状態に移る。-V操作=通行禁止--セマフォ変数の値を1加算する。このときP操作により実行を停止しているタスクがあれば、そのタスクは資源を獲得し実行を再開する。--V(S)と記述する。---(Sの待ち行列に入っているプロセス数)≧1の場合、Sの待ち行列からプロセスがひとつ取り出される。取り出されたプロセスは実行可能状態に移る。---(Sの待ち行列に入っているプロセス数)=0の場合、S←S+1とし、Vを実行したプロセスがそのまま実行を継続する。セマフォ変数の初期値が1であれば、最初のP操作を行ったタスクがV操作を行うまでは他のタスクはP操作で待ち状態になるので、排他制御が実現できる。複数のプロセスで共有するリソースRがあったとする。このリソースRは、それぞれのプロセスが排他的に使用する。Rを使用する2つのプロセスX,Yが並列して動作している場合、セマフォ変数S、P(S)操作、V(S)操作を使って、排他制御を行うことができる。セマフォ変数Sを利用すると、並行して動作するプロセスを強調して動作させることができる。プロセスXとYがひとつのリソースRを共有して、排他的に使用する場合の処理の流れは次の通りである。プロセスX,Yは、それぞれリソースRを利用する処理と、Rを利用する以外の処理の繰り返して行うプロセスである。''デッドロック(deadlock)''とは、両プロセスが相手の解放命令を待っているので、待ち状態は永久に解けない状態のことである。デッドロックが起こると両プロセスが身動きとれない状態に陥ってしまう。デッドロックを避ける方法は色々存在する。タスク相互で情報を交換する方法として、次が挙げられる。-共有ライブラリ--タスクを構成するルーチンの一部を、タスク間で共有する。-メールボックス--郵便のやり取りを模擬する。-パイプファイル--ファイルの読み書きを模擬する。メールボックスやパイプライフは、それらを実現するシステムコールが実装さsれる。データの受け取りのシステムコールを発行すれば、データが準備されるまで待ち状態に遷移する。