数式が読み込まれない場合は1回再読み込みしてみてください。情報-オペレーティングシステムこんにちは、ももやまです。今回はオペレーティングシステム分野におけるプロセス、およびスケジューリングアルゴリズムについて紹介していきたいと思います。今までは暗記中心でしたが、スケジューリングアルゴリズムでは計算問題が多く出題されるので、計算方法についてもまとめています。練習1練習2練習3練習4練習5設問1設問27.練習問題の答え解答1解答2解答3解答4解答5設問1設問28.さいごに前回までの計算機システム(Part17)の記事はこちら!www.momoyama-usagi.com1.プロセス(タスク)とはプログラムを作成、もしくはインストールしただけではコンピューター上でプログラムは動きません。スマホでも、欲しいアプリをインストールしただけではアプリは起動しませんよね。インストールしたアプリアイコンをタップして起動させますよね。このように、実際にプログラムを動かす際には、実行ボタンなどを押すことによって、プログラムを動作させる必要があります。プロセスとは動作しているプログラムのことを指します*1。(プロセスのことをタスクと呼ぶ人もいます)皆さんが持っているパソコン(Windows)のプロセスを確かめてみたい人は、「Ctrl」+「Shift」+「Esc」キーを同時に押してみてください。下のようにプロセス一覧が出てくると思います。余談ですが最近ではビジネス用語でも「プロセス」という言葉は「過程、手順」などの意味でよく使われますね。3つの状態とはCPUの資源には限りがあるので、複数のプロセス(タスク)を同時に実行することができません。我々人間も複数の仕事を同時にこなすことはできません(できても難しい)ですよね。ち状態の3つの状態を割り当てることで、複数のプロセス(タスク)を並行に処理することができます。ち状態がどんな状態なのかを説明していきましょう。実行状態CPUが割り当てられてプログラムを実行している状態のことを実行状態と呼びます。今まさに仕事をしている状態を表します。実行可能状態CPUが割り当てられさえすればすぐにプログラムを実行できる状態のことを実行可能状態と呼びます。仕事が割り当てられさえすればいつでも仕事ができる状態を表します。入出力要求などのCPUが割り当てられていてもどうしようもない処理が必要で、何もできないような状態を待ち状態と呼びます。上司の指示を待っていて仕事がストップしている状態を待ち状態と呼びます。状態の変化では、どんな状態のときに状態が変化するのかを下にある図とともに説明していきましょう。プロセス(タスク)の生成プログラムやアプリを実行すると、プロセス(タスク)が生成されます。生成されたタスクはすぐには実行されず、実行可能状態となります。実行状態のプロセスの処理が終わると、プロセスは終了し、消滅します。ディスパッチ実行可能状態のプロセス(タスク)にCPUを割り当てる処理のことをディスパッチと呼びます。プロセスにディスパッチを行うことで実行可能状態のプロセスが実行状態となります。ディスパッチを行うシステムをディスパッチャと呼びます。人間に例えると、仕事に割り当てる操作がディスパッチ、割り当てる上司がディスパッチャに相当します。プリエンプション(割込み)実行中のプロセスに割り当てられているCPUを奪うことをプリエンプションと呼びます。タイマ割込みや、0除算などの割込みによりプリエンプションが起こります。(割込みについてはこちらの記事で詳しく説明しているので、ぜひご覧ください。)プリエンプションが起こると、実行状態のプロセスは実行可能状態に変化します。入出力要求などのCPUが割り当てられていてもどうしようもない事象が発生した場合は、タスクは待ち状態に変化します。タスクが待ち状態の間に、他のプロセスにCPUを割り当て(ディスパッチ)、効率的にプロセスを処理していきます。上の人の指示がないとできない仕事を一時的に保留し、別の仕事をしていくイメージです。しようもない事象が終了すると、すぐに実行状態に戻るのではなく、実行可能状態に戻ります。CPUを割り当て(ディスパッチ)られることにより、実行状態になります。実行可能状態]3.スケジューリングアルゴリズム複数の実行可能なプロセスがある場合に、どの順番でプロセスを割り当てるか(つまり実行状態にするか)を考える必要があります。これを(プロセス)スケジューリングと呼びます。スケジューリングに用いられるアルゴリズムのことをスケジューリングアルゴリズムと呼びます。出てくるスケジューリングの計算問題の解き方を紹介していきたいと思います。スケジューリングの評価基準スケジューリングアルゴリズムを組むときに、どのようにスケジューリングを行えば「良いスケジューリング」と言えるかを考える必要があります。「良いスケジューリング」かどうかは重要視する項目によって変わってきます。公平な割り当てなどがあります。バッチ処理、対話処理、リアルタイム処理それぞれでの「良いスケジューリング」かどうか判定するには以下のような項目が使われます。それぞれの処理で重要視される項目バッチ処理:とにかくターンアラウンド時間を重視。応答時間はどうでもいい。→できる限りターンアラウンド時間を短くできるアルゴリズムがGood対話処理:すべてのプロセスに対し、一定の応答時間を保証する必要がある→応答時間が長すぎず、かつ公平に割り当てられるスケジューリングがGoodリアルタイム処理:とにかく応答時間に厳しい、かつ正確に応答時間を見積もる必要がある→、かつ応答時間がなるべく予測できるようなアルゴリズムがGood4.代表的なスケジューリングアルゴリズムでは、代表的なスケジューリングアルゴリズムをいくつか紹介していきましょう。それぞれのスケジューリングアルゴリズムごとに下の4つのプロセスのそれぞれのターンアラウンド時間、平均ターンアラウンド時間を求めていきましょう。ターンアラウンド時間の求め方まずはターンアラウンド時間はどうやって求められるかについて説明しましょう。ターンアラウンド時間とは、処理要求を出してから処理が完了するまでの時間のことでしたね。処理要求を出した時間は、プロセスが到着した時間と同じですよね。ターンアラウンド時間は、(プロセスの処理が完了した時間)から(プロセスが到着した時間)を引くことで求めることができます。queue)の最後尾に並べ、待ち行列の先頭から処理するアルゴリズムで、今回紹介するアルゴリズムの中では最も単純です。待ち行列という難しい言葉が出ていますが、要するに先に到着したプロセスから順番に処理していくだけの簡単かつ単純な処理をしているだけです。単純なのが利点ですが、処理に時間がかかるようなプロセスがあると、その後に到着したプロセスのターンアラウンド時間が大きくなってしまい、結果として平均ターンアラウンド時間も長くなってしまいます。到着順アルゴリズム到着順のスケジューリングアルゴリズムとは、先に到着したプロセスから順番に処理していくだけのスケジューリングアルゴリズムである。短所:処理に時間がかかるようなプロセスがある場合、その後に到着したプロセスのターンアラウンド時間が大きくなってしまう。1問例題を見てみましょう。例題1下のような表のように4つのプロセスが到着する。到着順のスケジューリングアルゴリズムを適用した際のそれぞれのターンアラウンド時間、および平均ターンアラウンド時間を求めなさい。到着順なので、先に到着したプロセスから順番に処理していきます。A→B→D→Cの順番に処理します。すると、Aは4秒後、Bは12秒後、Cは20秒後、Dは14秒後に処理が終了するので、それぞれのターンアラウンド時間は到着時間を引くことで求められます。11秒となり、4つのプロセスの平均ターンアラウンド時間は10.25秒となります。図を用いてそれぞれの処理をわかりやすくしたものを下に載せておくのでご覧ください。(2秒ごともしくは何かしらのプロセス生成時の待ち行列も記しています。4...の数字は時刻を表す。queue)に並べるアルゴリズムです。要するにすでに到着しているプロセスの中で、処理時間が短いものから順に処理していくだけです。処理時間順アルゴリズムのメリットは、平均ターンアラウンドを最も小さくできる点です。処理時間が非常に長いプロセスはなかなか処理されない点、および実際の処理時間を知ることは難しいので実現が困難というデメリットもあります。処理時間順アルゴリズム処理時間順のスケジューリングアルゴリズムとは、すでに到着している(かつ未処理)プロセスの中から処理時間が最も短いプロセスから順に処理するアルゴリズムである。例題を解いてみましょう。例題2下のような表のように4つのプロセスが到着する(例題1と同じ)。処理時間順のスケジューリングアルゴリズムを適用した際のそれぞれのターンアラウンド時間、および平均ターンアラウンド時間を求めなさい。最初に到着しているプロセスはAのみです。最初にAが処理され、4秒のときに完了します。4秒のとき、到着済みの未処理のプロセスはBとDの2つです。2つのうち、より処理時間が短いDを優先して処理し、6秒のときに完了します。6秒のとき、到着済みの未処理のプロセスはBとCの2つです。処理時間が短いCが優先され、6秒後の12秒で完了します。最後に残ったBを処理し、8秒後の20秒に処理が終わります。ターンアラウンド時間はそれぞれ4秒、19秒、7秒、3秒となり、平均ターンアラウンド時間は8.25秒となります。ラウンドロビン今まで紹介したアルゴリズムではプリエンプション(CPUの横取り)、つまり割込みは一切起こりませんでしたが、ここから紹介するアルゴリズムはプリエンプションが発生します。queue)の最後尾に並べる到着順と同じアルゴリズムですが、一定時間経過後に処理が完了していない場合はいったん処理を中断(プリエンプション)し、待ち行列の最後尾に移します。一定時間ごとに異なるプロセスを処理していくアルゴリズムなのです!また、この一定時間のことをタイムクォンタムと呼ぶこともあります。ラウンドロビンの長所は、どのプロセスに対しても公平に処理することができることです。公平に処理ができるので、すべてのプロセスに一定の応答時間を保証できます。そのため、ラウンドロビンは対話処理に向いたアルゴリズムと言うことができます。タイムクォンタムの設定時間は非常に重要です。タイムクォンタムを小さく設定しすぎるとオーバーヘッド(処理以外にかかってしまう時間)が増えてしまい、時間の無駄となります。大きく設定しすぎると、到着時間順のアルゴリズムとほぼ一緒になってしまい、一定の応答時間を保証できなくなってしまいます。そのため、タイムクォンタムは適切な時間(無駄に大きかったり小さかったりしない)に設定する必要があります。基本的に到着順に処理ただし、一定時間(タイムクォンタム)以内に処理できないプロセスは中断し、待ち行列の最後尾に回すアルゴリズムである。長所:どのプロセスも公平に実行され、全プロセスに一定の応答時間を保証できる。★ラウンドロビンにおける注意★タイムクォンタムの設定は非常に重要。タイムクォンタムが小さすぎるとオーバーヘッドが大きくなってしまう。逆に大きすぎると一定の応答時間を保証できなくなる。試験問題では、基本的に新たに到着したプロセスと定時間(タイムクォンタム内)に終了せずに待ち行列の最後尾に回されたプロセスが同時にやってくることがないように問題設定が行われています。(後ほど紹介する練習問題でもあるのですが、万が一同時に到着する場合は問題文にどちらを優先すべきかが書いてあるので心配しなくてOKです)再び例題を解いてみましょう。例題3下のような表のように4つのプロセスが到着する(例題1と同じ)。タイムクォンタムが2秒のラウンドロビン方式のスケジューリングアルゴリズムを適用した際のそれぞれのターンアラウンド時間、および平均ターンアラウンド時間を求めなさい。初回なので解説を丁寧に書いています。つぎの問題以降では特に重要なポイントがない限り、下のような図だけを解説に記しています。※待ち行列の赤色の文字は到着したプロセス、緑色の文字はタイムクォンタム内に終了せずに最後尾に回されたプロセスを表します。プロセス到着時)で待ち行列を記述していくことを強くおすすめします。[0秒地点]到着しているプロセスはAのみなのでAを2秒処理します。[1秒・2秒地点]1秒のときにプロセスBが到着するので待ち行列にBが追加されます。タイムクォンタムが経過した2秒後に処理が終わらなかったAが待ち行列の最後尾に追加されます(待ち行列は先頭から順にB,A)。待ち行列の先頭はBなのでつぎに、Bを2秒処理します。(待ち行列:A)[3秒・4秒地点]3秒のときにプロセスDが到着するので待ち行列にDが追加されます。(待ち行列:A,D)さらにタイムクォンタムが経過した4秒で処理が終わらなかったBが待ち行列の最後尾に追加されます。(待ち行列は:A,D,B)待ち行列の先頭はAなのでつぎにAを2秒処理します。(待ち行列:D,B)[5秒・6秒地点]5秒のときにプロセスCが到着するので待ち行列にCが追加されます。待ち行列の先頭はDなのでつぎにDを2秒処理します。(待ち行列:B,C)[8秒地点]Dを2秒処理したため、Dの処理が完了します。待ち行列の先頭はBなので、Bを2秒処理します。(待ち行列:C)[10秒]Bをすべて処理できなかったため、Bを待ち行列の最後尾に移します。待ち行列の先頭にあるCを再び2秒実行します。[12秒]Cをすべて処理できなかったため、Cを待ち行列の最後尾に移します。待ち行列の先頭にあるBを再び2秒実行します。[14秒]Bをすべて処理できなかったため、Bを待ち行列の最後尾に移します。待ち行列の先頭にあるCを再び2秒実行します。[16秒]Cをすべて処理できなかったため、Cを待ち行列の最後尾に移します。待ち行列の先頭にあるBを再び2秒実行します。[18秒]Bの処理が完了します。待ち行列の先頭にいるCを処理します。[20秒]Cの処理が完了します。すべてのプロセスの処理が完了しました。ターンアラウンド時間はそれぞれ6秒、17秒、15秒、5秒となり、平均ターンアラウンド時間は10.75秒となります。優先度順(優先順付きラウンドロビン)基本的には到着順ですが、優先度ごとに待ち行列を用意し、優先度が高い待ち行列から順番に処理していくようなアルゴリズムを優先度順式スケジューリングと呼びます。イメージとしては飛行機の優先搭乗を思い浮かべてください*3。優先度順のアルゴリズムはラウンドロビンと併用されることが多いです。一定時間以内に処理が終わらなければ同じ優先度の待ち行列の最後尾へ優先度の高い待ち行列の処理が終わり次第、優先度が低い待ち行列を処理していくようなアルゴリズムが優先度順とラウンドロビンを併用したスケジューリングアルゴリズムとなります。例題を1問解いてみましょう。例題4下の表のように4つのプロセスが到着する。タイムクォンタムが2秒の優先度付きのラウンドロビン方式のスケジューリングアルゴリズムを適用する。このスケジューリングアルゴリズムでは、高優先度のプロセスを優先的に処理し、高優先度のプロセスがなくなり次第低優先度のプロセスを処理していく。このとき、それぞれのターンアラウンド時間、および平均ターンアラウンド時間を求めなさい。例題3と異なる点は、待ち行列が優先度順に用意されていて、優先度の高い待ち行列から順に処理していくところのみです。それ以外は通常のラウンドロビンと同じです。2秒時点では、BのプロセスよりもAのプロセスのほうが優先度が高いため、Aのプロセスを続けて処理しています。多重レベルフィードバックスケジューリング処理時間が短いプロセスから順に処理すると、平均ターンアラウンド時間は短くなりますよね。現実世界では処理時間を完璧に予測することは非常に困難です。そこで、一定時間以内に処理が終わらない場合、同じ優先度の待ち行列ではなく、1段階低い優先度の待ち行列の最後尾にプロセスを移すことで、処理時間がかかるプロセスを後回しにし、処理時間が短いものを優先的に処理することができますね。処理時間を正確に見積もる必要もありません!このようなスケジューリングアルゴリズムを多重レベルフィードバックスケジューリングと呼びます。多重レベルフィードバックスケジューリングはUNIXのスケジューリングアルゴリズムのベースとなっています。こちらは例題は用意していませんが、後ほどの練習問題で練習できるのでぜひ練習問題にチャレンジしてみてください。短い順にプロセスを処理していくとターンアラウンド時間が短くなると説明しましたね。処理時間が短い順に処理すると平均ターンアラウンド時間が短くなるかを例題を用いて説明していきたいと思います。