00:43:48)追加された行はこの色です。削除された行はこの色です。マルチプログラミング環境では、複数のプログラムがCPUの実行権を相互に切り換えながら、全体として同時並行的に処理を進行させる。このとき、CPUの実行権を切り替える単位を''タスク''または''プロセス''と呼ぶ。汎用コンピュータのOSではジョブステップ、UNIXなどのタイムシェリングOSではコマンドで実行させたプログラムがタスク(UNIXの習慣ではプロセスと呼ぶ)である。タスクの中から、他のタスクを起動することもできる。ユーザープログラムと直接結びついたタスクの他に実際のシステムでは、システム運用・管理や間接的なサービスを提供するようなタスクも存在する。UNIXではこのような役割を持つタスクを''デーモンプロセス''と呼ぶ。OSでは、プロセスを構成するルーチン(プログラムの断片)が別々のCPUで動くこともがある。そのOSの管理対象の単位を''スレッド(thread)''と呼ぶ。UNIX系でよく使われる。プロセスよりもさらに小さい処理単位である。プロセスは資源を共有せず、個別に資源が割り当てられる。同じメモリ領域を複数のプロセスが使用する場合、HDDなど別の領域に一旦退避させ、その後別プロセスのメモリ領域として使用する。そのため、プロセスの切り換えには若干の時間がかかり、これが性能低下の一因になっている。これに対して、スレッドはCPU以外の資源を割り当てられず、必要な資源は親のプロセスから継承し、プロセス内の他のスレッドと共有する。そのため、スレッドの切り換え時にメモリ退避などの処理は不要となり、その分高速に切り換えが実現できる。--プロセスA,Bのように、処理時間の中で入出力時間の占める割合が大きいプロセスを入出力バウンドのプロセスという。--大半の事務計算プログラムやオンライントランザクション処理は典型的な入出力バウンドのプロセスといえる。bound)プロセス--プロセスCのように、処理時間の中でCPU時間の占める割合が大きいプロセスをCPUバウンドのプロセスという。--科学技術計算のプログラムやプラントの実時間制御システムなどが該当する。人の側から見た仕事の単位を[[ジョブ]]というのに対して、OSの管理下で実行される仕事の単位を''タスク''と呼ぶ。ジョブが投入されたら、それを''ジョブステップ''ごとに、あるいはジョブステップをさらに分割してタスクを作り、タスクごとに実行されることになる。このタスクの実行を監視し、[[CPU]]や[[主記憶装置]]の管理や制御を行うことを、''タスク管理''という。「マークシートを読み込んで、試験の採点をして、結果をファイルに出力せよ」というジョブが投入されたとする。このとき、「マークシートを読み込む」というジョブステップ1、「試験の採点をする」というジョブステップ2、「結果をファイルに出力する」というジョブステップ3に分解される。その後、さらにそれぞれのジョブステップから単一あるいは複数のタスクが生成される。ジョブ管理によって、ジョブにはハードウェア資源が割り当てられる。仮想記憶装置なら、主記憶装置の割り当てられる。マルチプログラミングなら、CPUの割り当て、割り込み処理が使われる。タスクは、他のタスクにより生成(起動)される。タスク起動に際してはタスクを識別するためのタスク番号、タスク実行権の割り当てを管理するためのタスク優先順位が与えられる。タスクは自分自身を消滅させる場合と、他から消滅させられる場合とがある。タスクの生成・消滅を行うシステムコールが用意されている。ハードウェア資源の状態は、タスクを実行中に変化する。他のタスクが磁気ディスク装置を使っているので、処理が終わるまで待つ必要が出てきたりする。タスク管理によって生み出されたタスクは、すぐに実行できるとは限らない。タスクは次の3つの状態を取る。+実行可能状態--処理装置(CPU)の使用権が与えられれば、実行できる状態。+実行状態+実行可能状態(ready)--処理装置([[CPU]])の使用権が与えられれば、実行できる状態。---実行状態にあるタスクが他の状態に遷移すると、待ち行列中からひとつのタスクを選び、実行状態に遷移させる。---同一優先順位内での順番を決めるにはいくつかの方法がある。+実行状態(running)--処理装置で実行している状態。+待機状態---入出力が完了すれば、それを待っていたタスクは実行可能状態の待ち行列へ加えられる。---初期の[[OS]]では、タスクが到着した順に実行を行い、そのタスクの処理がすべて終了するまで、他のタスクにCPUの使用権を与えることはなかった。これを''到着順方式''という。+待機状態(wait)--入出力装置の処理が終わるのを待っている状態。---実行状態にあったタスクが他の状態へ遷移すると、OSのスケジューリング機能により、実行可能状態の中のタスクがひとつ選ばれて実行状態へ移される。---実行状態にあったタスクは、自ら明示的にWAITシステムコールを発行したり、入出力システムコールを発行することで待ち行列に遷移する。タイムシェリングシステムでタイムスライスが終わったときには、実行可能状態へ遷移させられる。---待ち状態にあるタスクに対するイベントが発生すれば、そのタスクは実行可能状態へ移され、待ち行列に加わる。[補講]現実のOSでは、この3つの他にいくつかの状態が設定されており、それらの状態間を遷移する。状態により遷移が変わってくる。その状態遷移図は次の通りである。処理装置(CPU)が与えらたら実行することができるが、実行状態2から実行状態1に戻っている矢印に注目して欲しい。実行していたタスクの処理を中断して、より優先順位の高いタスクが割り込むことがある。このとき、実行中のタスクはいったん中断して実行可能状態に戻り、優先順位の高いタスクが終了するのを待つ。-�→�--CPUの割り当て(ディスパッチング)---実行可能状態にあるタスクの中で、もっとも優先順位の高いタスクにCPUの使用権を割り当てる。-�→�--タイマ割り込み---タイマ割り込みが発生すると、実行状態にあるタスクが実行可能状態に移る。-�→�--スーパバイザコール割り込み---タイマ割り込みが発生すると、実行状態にあるタスクが待機状態に移る。-�→�--入出力処理の完了---入出力処理が完了すると、待機状態にあるタスクが実行可能状態に移る。複数のタスクがある同じ条件で待ち状態になった場合、条件の成立したタスクすべての待ち状態を同時に解除できるタスク間の同期制御方法を''イベントフラグ''という。タスクに時分割で処理装置を割り当てる方式を''タイムスライシング''と呼ぶ。1ms割り当てたとすると、実行可能状態のタスクにCPUを割り当てて実行状態にするが、処理が終わっていなくても1ms通過したらそのタスクを中断して実行可能状態に戻し、他のタスクに1ms割り当てる。タスクの応答性やシステム全体の効率を高めるために、タスクの処理順序を決めることを、''タスクのスケジューリング(scheduling)''という。Out:先入れ先出し)方式--FIFO方式は、タスクを先着順に処理する方式である。--実行中のタスクが終了するまで、後続のタスク処理が待たされるという問題がある。quantum:タイムクォンタム)を決めて、制限時間に達成したら実行中のタスクを実行可能状態に遷移させる時分割方式が考案された。--ラウンドロビン方式は、時分割方式におけるタスクのスケジューリング方式で、先に到着したタスクから順に処理され、一定時間処理されたタスクは、実行を待つタスクの待ち行列の最後に繋がれる。-イベントドリブン方式--入出力終了やコマンド入力などをの割込みをトリガーに実行する方式。--マルチタスクにイベントドリブン方式を取り入れるとリソースの利用効率が向上する。遷移する矢印が追加されたことになる。ディスパッチャーによってCPUが割り当てられると、タスクは「実行状態」�になる。その後、処理が終了すればタスクは消滅するが、処理の中で入出力が発生すればそのタスクは「待ち状態」�に遷移する。タスク管理としてもうひとつ考慮することは、実行可能状態にあるタスクの待ち行列の並び方である。First)方式--実行時間が短いタスクを優先的に待ち行列の先頭に配置する方式。---実行時間の長いタスクが先に待ち行列に並んでいる場合、実行時間が短いタスクはそれだけ長い時間待たされる。---実行時間が短いタスクはオンラインリアルタイム処理などの即時性を求められるタスクであることが多く、そのようなタスクは実行時間が長いタスクよりも優先的に実行させるべきである。scheduling)方式--タスクの優先度は一律ではなく、一般にリアルタイムのタスク、OSのタスク、対話型のジョブ、バッチジョブの順に優先度が割り当てられている。--優先度順方式はタスクの優先度を考慮したスケジューリング方式で、優先度が高いタスクは優先度の低いタスクよりも優先的にCPUを使用することができる。--これは優先度に応じた待ち行列を用意し、優先度の高い待ち行列から順にCPUを割り当てるイメージである。この方式は優先度が低いタスクになかなかCPUが割り当てられないという問題がある。この状態を''スタベーション(starvation:無期延長)''といい、スタベーション対策として待ち行列に比例して優先度を上げることを''エージング(aging)''という。-多段待ち行列方式(フィードバック待ち行列方式、多重待ち行列方式)--優先度順方式とラウンドロビン方式を合わせた方式。--フィードバックとは、以前の結果を何らかの形で現状に反映することである。--多段待ち行列方式においては、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の使用権を獲得したら、処理が終了するまで他のタスクにCPUの使用権を譲ることはない。マルチタスクだとこれが普通である。複数のタスクにCPUが割り当てる時間をOSをあらかじめ決めておくのがポイントである。実行中の処理よりも優先度の高い別の処理要求が発生した場合には先に実行できる。multitasking:非協調型マルチタスク)''と呼ぶ。95以降のWindowsでは、マウスカーソルが砂時計に変わっても矢印が残り、他の処理を実行することが可能なプリエンプティブなOSである。95,OS/2,UNIXなどはプリエンプティブなOSである。System)も、プリエンプティブマルチタスクの一種であり、短い時間間隔で複数のジョブを強制的に切り換えながら処理する。タスクの切り換えをOSが行わずに、複数のタスクを同時に処理しているように見せる方式で、タスクの切れ目で切り替えていく。アプリケーションの自主的な処理の解放を前提として、複数アプリケーション間で制御を切り替える。multitasking:協調型マルチタスク)''と呼ぶ。''擬似マルチタスク''と呼ぶこともある。特定のタスクがCPUを独占すると、他のタスクの処理が停止することがある。3.1では、アイコンをクリックするなどの動作を行うと、マウスカーソルが砂時計に変わり、他の処理を実行することはできない。ノンプリエンプティブなOSである。CPUから比べると圧倒的にプリンタは低速である。そのためプリンタの動作が完了するのを待っていると時間がかかってしまう。そこで印刷データを一旦補助記憶装置に出力し、CPUは次の処理を実行する。その後、補助記憶装置からプリンタへ適時印刷データが送られる。このような方式を''スプーリング(スプール)''と呼ぶ。あるタスクで使用したプログラムを、再ロードせずに繰り返し実行できるプログラムを''再使用可能プログラム''という。再使用可能プログラムは次のように分類される。-逐次再使用可能(リユーザブル)--単に再使用可能といったらこちらを指す。--ひとつのタスクだけが使用できる。同時には利用できない。-再入可能(リエントラント)--同時に複数のタスクが使用できる。逐次再使用可能プログラムは、実効によって変更された値を初期状態に戻すように作られている。一度実行した後、ロードし直さずに再び実行を繰り返しても、正しい結果が得られる。再入可能プログラムは、実行で変化しない部分をひとつ、変化する部分をタスクの数だけ持っている。複数のタスクで並行して実行しても、正しい結果が得られる。逐次再使用可能プログラムは、実行によって変更された値を初期状態に戻すように作られている。再使用可能といったらこちらを指す。一度実行した後、ロードし直さずに再び実行を繰り返しても、正しい結果が得られる。[補講]自分自身を呼び出せるプログラムを''再帰的プログラム''と呼ぶ。再入可能プログラムは、実行中であっても、他のタスクから呼び出すことのできるプログラムである。よって、複数のタスクで並行して実行しても、正しい結果が得られる。同時実行を可能にするためには、呼び出し元のプログラム毎に専用の変数を確保しなければならない。実行で変化しない部分をひとつ、変化する部分をタスクの数だけ持っている。複数のタスクで並行して実行しても、正しい結果が得られる。再入可能プログラムを実現するためには、プログラムを手続き部分とデータ部分に分割して、データ部分をプロセスごとに持つ必要がある。リユーザブルとリエントラントを比較すると、次の点で異なる。-リユーザブル--同時に複数のプログラムからの呼び出し・実行が不可能。-リエントラント--同時に複数のプログラムからの呼び出し・実行が可能。自分の中から自分を呼び出すことができる。再帰的に呼び出すには、呼び出す際にプログラムの実行状態やデータを[[スタック]]へ保存(push)し、呼び出し元へ処理が戻ったときにスタックからデータを読み出す(pop)仕組みが必要である。実記憶上のどこのアドレスに配置しても実行することが可能である。プログラムと対応するライブラリが、リンク時にリンカによって関連付けられるものが''静的リンク''、関連付けられないものが''動的リンク''である。動的リンクはプログラムが必要に応じてライブラリを呼び出す。Library)は動的リンクから呼び出される。''同期制御''とは、複数のタスクの間で協調する機能である。''排他制御''は、相互干渉を避ける機能である。例:加算を行うプログラムA、減算を行うプログラムBが存在するとき、排他制御を用いない場合のデータベースにアクセスすると次のように変化する。#img(http://security2600.sakura.ne.jp/main2/image3/haiat.jpg)#img(,clear)1:プログラムAがデータXを読む。2:プログラムBがデータXを読む。3:プログラムAにおいてXに50を加えて、その結果をデーベースに書き込む。4:プログラムAにおいてXに50を引いて、その結果をデーベースに書き込む。5:結局データベースの値が100になってしまう。2つのタスクが共有するデータを、両方のタスクが更新する場合に、更新処理の途中で他方のタスクへ実行権が移ると、データの整合性が保証されなくなる。このように中断が許されない処理ステップを''クリティカルセクション''と呼ぶ。相互干渉があってはならない資源をアクセスする間は、それが完了するまで、他のタスクがその資源にアクセスできないようにする必要がある。これを保証することを''相互排他制御''という。相互排他制御の方法として、次が挙げられる。複数のタスクが協調してある結果を得たいとき、ひとつのタスクがあることをしたら別のタスクがこれをする、といった具合に進行させるのは、実は相互排他制御の裏返しである。これを実現させる仕組みを''同期制御''という。''ロック(lock)''とは、二重更新を回避するためにデータ更新中はデータをロックし、他のプログラムにアクセスさせないようにすることである。変更時に用いる''専有ロック(排他ロック)''と、読み取り時に用いる''共有ロック''がある。共有ロックはデータの参照時、専有ロックはデータの更新時に用いられる。ここで、「○:許可」「×:不許可」を意味する。データを参照中に、他のトランザクションが同じデータを参照することは許してもよいが、更新を許すと参照中のデータの整合性が崩れる可能性がある。''デッドロック(deadlock)''とは、両プロセスが相手の解放命令を待っているので、待ち状態は永久に解けない状態のことである。デッドロックが起こると両プロセスが身動きとれない状態に陥ってしまう。例:プロセスP1は資源R1,R2の順に要求を出し、プロセスP2が資源R2,R1の順番に要求を出すとき、P1にR1が割り当てられた時点でP2にR2が割り当てられると、相互に相手の選挙している資源が解放されるのを待ち、永久に停止状態になる。矢印は次のように定義しておいた。並行プロセス環境において、すべてのプロセスに決められた順序にしたがって資源が割り当てられたら、デッドロックは発生しない。逆に、デッドロックが発生する原因として次が挙げられる。-一度割り当てられた資源は、プロセスがその使用を終了するまで強制的には取り上げられない。-プロセスが他のプロセスを待ち合うという関係が、環状になっている。-プロセスは、ひとつの資源を専有しながら他の資源へ要求を出す。デッドロックを避ける方法は色々存在する。-デッドロックは、生じてから除去すると資源の利用効率は上がるが、プロセスから資源を取り上げる割り込み処理のオーバーヘッドが大きくなる。-資源間の線形順序にしたがって資源を順に割り当てる(静的防止)と、プロセス間の環状待ちの状態を待避できるが、オーバーヘッドが大きくなる。-資源割り当ての状況に応じて、デッドロックが生じないように割り当てる(動的防止)と、資源の使用効率はよくなるが、検知のオーバーヘッドが大きくなる。[問題]3つの資源X〜Zを占有して処理を行う4つのプロセスA〜Dがある。各プロセスは処理の進行に伴ない、表中の数値の順に資源を占有し、実行終了時に3つの資源を一括して解放する。このとき、プロセスAとデッドロックを起こす可能性のあるプロセスはどれか。|BGCOLOR(#FFFF00):CENTER:''プロセス''|>|>|BGCOLOR(#00FFFF):CENTER:''資源の占有順序''||~|BGCOLOR(#00FFFF):LEFT:''資源X''|BGCOLOR(#00FFFF):LEFT:''資源Y''|BGCOLOR(#00FFFF):LEFT:''資源Z''||BGCOLOR(#FFFF00):LEFT:''A''|RIGHT:1|RIGHT:2|RIGHT:3||BGCOLOR(#FFFF00):LEFT:''B''|RIGHT:3|RIGHT:2|RIGHT:1||BGCOLOR(#FFFF00):LEFT:''C''|RIGHT:2|RIGHT:3|RIGHT:1||BGCOLOR(#FFFF00):LEFT:''D''|RIGHT:1|RIGHT:2|RIGHT:3|-ア:B,C-イ:B,C,D-ウ:Bだけ-エ:Cだけ[ヒント]プロセスの優先順位を先に決めてから考察する。[解答][1]優先順位をA→B→C→Dと仮定する。このとき、AとBは互いにデッドロックになる。よって、解答にBは必ず含まれる。[2]優先順位をA→C→B→Dと仮定する。このとき、AとCは互いにデッドロックになる。よって、解答にCは必ず含まれる。[3]優先順位をA→D→B→Cと仮定する。プロセスAが資源X→資源Y→資源Zをロックしているときは、プロセスDはプロセスA待ちになる。プロセスAが資源を解放してから、プロセスDによる資源のロックが開始される。下の図はプロセスDがプロセスAをずっと待っている状態である。AとDはまったく同じ資源の優先順位を持つので、プロセスの優先順位を変えても変化しない。よって、解答にDは含まれない。したがって、答えはアである。タスク相互で情報を交換する方法として、次が挙げられる。-共有ライブラリ--タスクを構成するルーチンの一部を、タスク間で共有する。-メールボックス--郵便のやり取りを模擬する。-パイプファイル--ファイルの読み書きを模擬する。メールボックスやパイプライフは、それらを実現するシステムコールが実装さsれる。データの受け取りのシステムコールを発行すれば、データが準備されるまで待ち状態に遷移する。