うさぎでもわかる計算機システム（基本情報対応）　Part18　プロセスの3状態・スケジューリングアルゴリズム

こんにちは、ももやまです。

今回はオペレーティングシステム分野におけるプロセス、およびスケジューリングアルゴリズムについて紹介していきたいと思います。

 

今までは暗記中心でしたが、スケジューリングアルゴリズムでは計算問題が多く出題されるので、計算方法についてもまとめています。

 

主に

• プロセスの3つの状態（実行状態・実行可能状態・待ち状態）
• どんなときにプロセスの状態が変化するか
• ラウンドロビンなどの代表的スケジューリングアルゴリズム
• 基本情報・応用情報などの試験によく出てくるスケジューリング問題の計算

についてまとめているのでぜひご覧ください！

 

 

前回までの計算機システム（Part17）の記事はこちら！

www.momoyama-usagi.com

 

スポンサードリンク

１．プロセス（タスク）とは

プログラムを作成、もしくはインストールしただけではコンピューター上でプログラムは動きません。

スマホでも、欲しいアプリをインストールしただけではアプリは起動しませんよね。

インストールしたアプリアイコンをタップして起動させますよね。

 

このように、実際にプログラムを動かす際には、実行ボタンなどを押すことによって、プログラムを動作させる必要があります。

 

また、プロセスとは動作しているプログラムのことを指します*1。

（プロセスのことをタスクと呼ぶ人もいます）

 

皆さんが持っているパソコン（Windows）のプロセスを確かめてみたい人は、「Ctrl」+「Shift」+「Esc」キーを同時に押してみてください。

下のようにプロセス一覧が出てくると思います。

 

余談ですが最近ではビジネス用語でも「プロセス」という言葉は「過程、手順」などの意味でよく使われますね。

 

スポンサードリンク

２．プロセス（タスク）の3つの状態

(1) 3つの状態とは

CPUの資源には限りがあるので、複数のプロセス（タスク）を同時に実行することができません。

我々人間も複数の仕事を同時にこなすことはできません（できても難しい）ですよね。

 

そこでプロセス（タスク）に実行状態、実行可能状態、待ち状態の3つの状態を割り当てることで、複数のプロセス（タスク）を並行に処理することができます。

 

まずは、実行状態、実行可能状態、待ち状態がどんな状態なのかを説明していきましょう。

実行状態

CPUが割り当てられてプログラムを実行している状態のことを実行状態と呼びます。

つまり、今まさに仕事をしている状態を表します。

 

実行可能状態

CPUが割り当てられさえすればすぐにプログラムを実行できる状態のことを実行可能状態と呼びます。

 

つまり、仕事が割り当てられさえすればいつでも仕事ができる状態を表します。

 

待ち状態

入出力要求などのCPUが割り当てられていてもどうしようもない処理が必要で、何もできないような状態を待ち状態と呼びます。

つまり、上司の指示を待っていて仕事がストップしている状態を待ち状態と呼びます。

(2) 状態の変化

では、どんな状態のときに状態が変化するのかを下にある図とともに説明していきましょう。

 

その1　プロセス（タスク）の生成

プログラムやアプリを実行すると、プロセス（タスク）が生成されます。

生成されたタスクはすぐには実行されず、実行可能状態となります。

 

その2　プロセス（タスク）の終了

実行状態のプロセスの処理が終わると、プロセスは終了し、消滅します。 

仕事の終了です。 

その3　ディスパッチ

実行可能状態のプロセス（タスク）にCPUを割り当てる処理のことをディスパッチと呼びます。

プロセスにディスパッチを行うことで実行可能状態のプロセスが実行状態となります。

 

また、ディスパッチを行うシステムをディスパッチャと呼びます。

 

人間に例えると、仕事に割り当てる操作がディスパッチ、割り当てる上司がディスパッチャに相当します。

 

その4　プリエンプション（割込み）

実行中のプロセスに割り当てられているCPUを奪うことをプリエンプションと呼びます。

タイマ割込みや、0除算などの割込みによりプリエンプションが起こります。

（割込みについてはこちらの記事で詳しく説明しているので、ぜひご覧ください。）

 

プリエンプションが起こると、実行状態のプロセスは実行可能状態に変化します。

 

その5　実行状態→待ち状態

入出力要求などのCPUが割り当てられていてもどうしようもない事象が発生した場合は、タスクは待ち状態に変化します。

タスクが待ち状態の間に、他のプロセスにCPUを割り当て（ディスパッチ）、効率的にプロセスを処理していきます。

 

上の人の指示がないとできない仕事を一時的に保留し、別の仕事をしていくイメージです。

 

その6　待ち状態→実行状態

入出力要求などのどうしようもない事象が終了すると、すぐに実行状態に戻るのではなく、実行可能状態に戻ります。

再びCPUを割り当て（ディスパッチ）られることにより、実行状態になります。

 

 

 

スポンサードリンク

３．スケジューリングアルゴリズム

複数の実行可能なプロセスがある場合に、どの順番でプロセスを割り当てるか（つまり実行状態にするか）を考える必要があります。

 

これを（プロセス）スケジューリングと呼びます。

また、スケジューリングに用いられるアルゴリズムのことをスケジューリングアルゴリズムと呼びます。

 

では、代表的なスケジューリングアルゴリズムの紹介、および基本情報・応用情報に出てくるスケジューリングの計算問題の解き方を紹介していきたいと思います。

(1) スケジューリングの評価基準

スケジューリングアルゴリズムを組むときに、どのようにスケジューリングを行えば「良いスケジューリング」と言えるかを考える必要があります。

 

しかし「良いスケジューリング」かどうかは重要視する項目によって変わってきます。

重視されるもの（つまり、評価基準に用いられる）項目としては、

• スループット（処理効率）
• 応答時間の短縮
• ターンアラウンド時間*2の短さ
• 応答時間の予測可能性
• 公平な割り当て

などがあります。

 

バッチ処理、対話処理、リアルタイム処理それぞれでの「良いスケジューリング」かどうか判定するには以下のような項目が使われます。

 

 

４．代表的なスケジューリングアルゴリズム

では、代表的なスケジューリングアルゴリズムをいくつか紹介していきましょう。

 

さらに、それぞれのスケジューリングアルゴリズムごとに下の4つのプロセスのそれぞれのターンアラウンド時間、平均ターンアラウンド時間を求めていきましょう。

 

ちなみにこれ、基本情報や応用情報で頻出する項目なので、もし受ける人は必ずマスターしましょう！

 

確認　ターンアラウンド時間の求め方

まずはターンアラウンド時間はどうやって求められるかについて説明しましょう。

 

ターンアラウンド時間とは、処理要求を出してから処理が完了するまでの時間のことでしたね。

 

処理要求を出した時間は、プロセスが到着した時間と同じですよね。

なので、ターンアラウンド時間は、（プロセスの処理が完了した時間）から（プロセスが到着した時間）を引くことで求めることができます。

 

(1) 到着順

到着したプロセスを待ち行列(ready queue)の最後尾に並べ、待ち行列の先頭から処理するアルゴリズムで、今回紹介するアルゴリズムの中では最も単純です。

待ち行列という難しい言葉が出ていますが、要するに先に到着したプロセスから順番に処理していくだけの簡単かつ単純な処理をしているだけです。

 

単純なのが利点ですが、処理に時間がかかるようなプロセスがあると、その後に到着したプロセスのターンアラウンド時間が大きくなってしまい、結果として平均ターンアラウンド時間も長くなってしまいます。

 

 では、1問例題を見てみましょう。

 

例題1

下のような表のように4つのプロセスが到着する。

到着順のスケジューリングアルゴリズムを適用した際のそれぞれのターンアラウンド時間、および平均ターンアラウンド時間を求めなさい。

解説1

★解答★

それぞれのターンアラウンド時間
→ A: 4秒　B: 11秒　C: 15秒　D: 11秒

平均ターンアラウンド時間：10.25秒

 

到着順なので、先に到着したプロセスから順番に処理していきます。

なので、A→B→D→Cの順番に処理します。

 

すると、Aは4秒後、Bは12秒後、Cは20秒後、Dは14秒後に処理が終了するので、それぞれのターンアラウンド時間は到着時間を引くことで求められます。

よってそれぞれのターンアラウンド時間は、

A：4 - 0 = 4秒
B：12 - 1 = 11秒
C：20 - 5 = 15秒
D：14 - 3 = 11秒

となり、4つのプロセスの平均ターンアラウンド時間は10.25秒となります。

 

図を用いてそれぞれの処理をわかりやすくしたものを下に載せておくのでご覧ください。

（2秒ごともしくは何かしらのプロセス生成時の待ち行列も記しています。）

※待ち行列の赤文字はちょうど生成されたプロセス、0, 2, 4…の数字は時刻を表す。

 

(2) 処理時間順

処理時間が短い順に、待ち行列(ready queue)に並べるアルゴリズムです。

要するにすでに到着しているプロセスの中で、処理時間が短いものから順に処理していくだけです。

 

処理時間順アルゴリズムのメリットは、平均ターンアラウンドを最も小さくできる点です。

しかし、処理時間が非常に長いプロセスはなかなか処理されない点、および実際の処理時間を知ることは難しいので実現が困難というデメリットもあります。

 

 

 

再び例題を解いてみましょう。

 

例題2

下のような表のように4つのプロセスが到着する（例題1と同じ）。

処理時間順のスケジューリングアルゴリズムを適用した際のそれぞれのターンアラウンド時間、および平均ターンアラウンド時間を求めなさい。

 

解説2

★解答★

それぞれのターンアラウンド時間
→ A: 4秒　B: 19秒　C: 7秒　D: 3秒

平均ターンアラウンド時間：8.25秒

最初に到着しているプロセスはAのみです。

なので最初にAが処理され、4秒のときに完了します。

よってAのターンアラウンド時間は4秒（4 - 0）です。

 

4秒のとき、到着済みの未処理のプロセスはBとDの2つです。

2つのうち、より処理時間が短いDを優先して処理し、6秒のときに完了します。

よってDのターンアラウンド時間は3秒（6 - 3）となります。

 

6秒のとき、到着済みの未処理のプロセスはBとCの2つです。

より処理時間が短いCが優先され、6秒後の12秒で完了します。

よってCのターンアラウンド時間は7秒（12 - 5）です。

 

最後に残ったBを処理し、8秒後の20秒に処理が終わります。

よってBのターンアラウンド時間は19秒（20 - 1）です。

 

よって、A, B, C, D のターンアラウンド時間はそれぞれ4秒、19秒、7秒、3秒となり、平均ターンアラウンド時間は8.25秒となります。

 

(3) ラウンドロビン

今まで紹介したアルゴリズムではプリエンプション（CPUの横取り）、つまり割込みは一切起こりませんでしたが、ここから紹介するアルゴリズムはプリエンプションが発生します。

 

ラウンドロビンは、基本的には到着したプロセスを待ち行列(ready queue)の最後尾に並べる到着順と同じアルゴリズムですが、一定時間経過後に処理が完了していない場合はいったん処理を中断（プリエンプション）し、待ち行列の最後尾に移します。

つまり、一定時間ごとに異なるプロセスを処理していくアルゴリズムなのです！

また、この一定時間のことをタイムクォンタムと呼ぶこともあります。

 

ラウンドロビンの長所は、どのプロセスに対しても公平に処理することができることです。

 

公平に処理ができるので、すべてのプロセスに一定の応答時間を保証できます。

そのため、ラウンドロビンは対話処理に向いたアルゴリズムと言うことができます。

 

タイムクォンタムの設定時間は非常に重要です。

 

タイムクォンタムを小さく設定しすぎるとオーバーヘッド（処理以外にかかってしまう時間）が増えてしまい、時間の無駄となります。

一方大きく設定しすぎると、到着時間順のアルゴリズムとほぼ一緒になってしまい、一定の応答時間を保証できなくなってしまいます。

 

そのため、タイムクォンタムは適切な時間（無駄に大きかったり小さかったりしない）に設定する必要があります。

 

なお試験問題では、基本的に新たに到着したプロセスと定時間（タイムクォンタム内）に終了せずに待ち行列の最後尾に回されたプロセスが同時にやってくることがないように問題設定が行われています。

（後ほど紹介する練習問題でもあるのですが、万が一同時に到着する場合は問題文にどちらを優先すべきかが書いてあるので心配しなくてOKです）

 

再び例題を解いてみましょう。

 

例題3

下のような表のように4つのプロセスが到着する（例題1と同じ）。

タイムクォンタムが2秒のラウンドロビン方式のスケジューリングアルゴリズムを適用した際のそれぞれのターンアラウンド時間、および平均ターンアラウンド時間を求めなさい。

 

解説3

★解答★

それぞれのターンアラウンド時間
→ A: 6秒　B: 17秒　C: 15秒　D: 5秒

平均ターンアラウンド時間：10.75秒

 

初回なので解説を丁寧に書いています。

なお、つぎの問題以降では特に重要なポイントがない限り、下のような図だけを解説に記しています。

※待ち行列の赤色の文字は到着したプロセス、緑色の文字はタイムクォンタム内に終了せずに最後尾に回されたプロセスを表します。

 

ラウンドロビン方式の問題を解く際には、待ち行列が変化するタイミング（タイムクォンタム経過時 or プロセス到着時）で待ち行列を記述していくことを強くおすすめします。

 

[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,B,C）

Aを2秒処理した6秒後にAの処理が完了するので、Aのターンアラウンド時間は6秒（6 - 0）となります。

待ち行列の先頭は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の処理が完了します。

よってターンアラウンド時間は17秒（18 - 1）となります。

待ち行列の先頭にいるCを処理します。

 

[20秒]

Cの処理が完了します。

よってターンアラウンド時間は15秒（20 - 5）となります。

すべてのプロセスの処理が完了しました。

 

よって、A, B, C, D のターンアラウンド時間はそれぞれ6秒、17秒、15秒、5秒となり、平均ターンアラウンド時間は10.75秒となります。

 

 

(4) 優先度順（優先順付きラウンドロビン）

基本的には到着順ですが、優先度ごとに待ち行列を用意し、優先度が高い待ち行列から順番に処理していくようなアルゴリズムを優先度順式スケジューリングと呼びます。

イメージとしては飛行機の優先搭乗を思い浮かべてください*3。

 

また、優先度順のアルゴリズムはラウンドロビンと併用されることが多いです。

 

つまり、

• 優先度の高い順に待ち行列を処理
• 一定時間以内に処理が終わらなければ同じ優先度の待ち行列の最後尾へ
• 優先度の高い待ち行列の処理が終わり次第、優先度が低い待ち行列を処理

していくようなアルゴリズムが優先度順とラウンドロビンを併用したスケジューリングアルゴリズムとなります。

 

例題を1問解いてみましょう。

例題4

下の表のように4つのプロセスが到着する。

 

タイムクォンタムが2秒の優先度付きのラウンドロビン方式のスケジューリングアルゴリズムを適用する。

このスケジューリングアルゴリズムでは、高優先度のプロセスを優先的に処理し、高優先度のプロセスがなくなり次第低優先度のプロセスを処理していく。

 

このとき、それぞれのターンアラウンド時間、および平均ターンアラウンド時間を求めなさい。

解説4

★解答★

それぞれのターンアラウンド時間
→ Aが4秒　Bが19秒　Cが13秒　Dが3秒

平均ターンアラウンド時間：9.75秒

 

例題3と異なる点は、待ち行列が優先度順に用意されていて、優先度の高い待ち行列から順に処理していくところのみです。

それ以外は通常のラウンドロビンと同じです。

例えば2秒時点では、BのプロセスよりもAのプロセスのほうが優先度が高いため、Aのプロセスを続けて処理しています。

 

 

(5) 多重レベルフィードバックスケジューリング

処理時間が短いプロセスから順に処理すると、平均ターンアラウンド時間は短くなりますよね。

しかし、現実世界では処理時間を完璧に予測することは非常に困難です。

 

そこで、一定時間以内に処理が終わらない場合、同じ優先度の待ち行列ではなく、1段階低い優先度の待ち行列の最後尾にプロセスを移すことで、処理時間がかかるプロセスを後回しにし、処理時間が短いものを優先的に処理することができますね。

 

もちろん処理時間を正確に見積もる必要もありません！

このようなスケジューリングアルゴリズムを多重レベルフィードバックスケジューリングと呼びます。

 

なお、多重レベルフィードバックスケジューリングはUNIXのスケジューリングアルゴリズムのベースとなっています。

 

こちらは例題は用意していませんが、後ほどの練習問題で練習できるのでぜひ練習問題にチャレンジしてみてください。

 

５．処理時間順のターンアラウンド時間が短い理由

先程、処理時間が短い順にプロセスを処理していくとターンアラウンド時間が短くなると説明しましたね。

 

では、なぜ処理時間が短い順に処理すると平均ターンアラウンド時間が短くなるかを例題を用いて説明していきたいと思います。

 

例題5

4つのプロセスA, B, C, Dが同時に到着した。

この4つのプロセスは単独で処理するとそれぞれa, b, c, dの時間がかかる。

(1) A, B, C, Dの順で処理したときのそれぞれのターンアラウンド時間、および平均ターンアラウンド時間を求めなさい。

(2) (1)より、どのようなアルゴリズムでスケジューリングすれば平均ターンアラウンド時間が最短になるかを考えなさい。

解説5

(1)

図を書くと、下のようにそれぞれのプロセスを処理することができますね。

よって、それぞれのターンアラウンド時間は、

A：\( a \)　　B：\( a+b \)
C：\( a+b+c \)　　D：\( a+b+c+d \)

となり、平均ターンアラウンド時間は、\[
\frac{1}{4} ( 4a+ 3b + 2c +d) = a + \frac{3}{4} b + \frac{1}{2} c + \frac{1}{4} d
\]となります。

 

(2)

平均ターンアラウンド時間の係数に注目すると、a, b, c, dの順に大きく、処理した順番と全く同じになりますよね。

つまり、先に処理するプロセスのターンアラウンド時間の係数は大きいので影響も大きく、後に処理するプロセスのターンアラウンド時間の係数は小さいので影響も小さくなっていることがわかりますね。

 

よって、処理時間が短いプロセスから順番に処理すると平均ターンアラウンド時間が短くなりますね。

 

確かに例題の通り、処理時間が短い順に処理すると平均ターンアラウンド時間が短くなることがわかりましたね。

 

６．練習問題

では、5問ほど基本情報や応用情報の過去問で復習してみましょう。

最後の1問は午後の問題なので分量が少し大きめです。

 

練習1

タスクのディスパッチの説明として、適切なものはどれか。

[基本情報技術者平成31年春期 午前問16]

ア：各タスクの実行順序を決定すること
イ：実行可能なタスクに対してプロセッサの使用権を割り当てること
ウ：タスクの実行に必要な情報であるコンテキストのこと
エ：一つのプロセッサで複数のタスクを同時に実行しているかのように見せかけた状態のこと

 

練習2

図はプロセスの状態と遷移を表している。a, b, cの状態の適切な組合せはどれか。

[基本情報技術者平成18年秋期 午前問29]

 

練習3

スケジューリングに関する記述のうち、ラウンドロビン方式の説明として、適切なものはどれか。

[基本情報技術者平成30年秋期 午前問18]

ア：各タスクに、等にCPU時間を割り当てて実行させる方式である。
イ：各タスクに、ターンアラウンドタイムに比例したCPU時間を割り当てて実行させる方式である。
ウ：各タスクの実行イベント発生に応じて、リアルタイムに実行させる方式である。
エ：各タスクを、優先度の高い順に実行させる方式である。

 

練習4

タイムクウォンタムが2秒のラウンドロビン方式で処理されるタイムシェアリングシステムにおいて、プロセス1～3が逐次生成されるとき、プロセス2が終了するのはプロセス2の生成時刻から何秒後か。

ここで、各プロセスはCPU処理だけで構成され、OSのオーバヘッドは考慮しないものとする。また、新しいプロセスの生成と中断されたプロセスの再開が同時に生じた場合には、新しく生成されたプロセスを優先するものとする。

[応用情報技術者平成28年秋期 午前問19]

 

ア：12
イ：14
ウ：16
エ：17

 

練習5

CPUの割当て方式に関する次の記述を読んで，設問1，2に答えよ。

[基本情報技術者過去問題 平成23年特別 午後問2]

（説明中略）

設問1

次の記述中の [            ] に入れる正しい答えを，解答群の中から選べ。

　4つのプロセスA～Dがあり，各プロセスの到着時刻と処理時間を表1に示す。表1において、到着時刻とは、プロセスAが待ち行列に到着した時刻を0としたときの各プロセスが到着する時刻であり、処理時間とは，各プロセスの処理が完了するために必要なCPUの処理時間である。

　このとき、到着順方式におけるターンアラウンドタイムの平均は [     a     ] ミリ秒である。そして，タイムクウォンタムが20ミリ秒のとき，ラウンドロビン方式におけるターンアラウンドタイムの平均は [     b     ] ミリ秒である。ここで、プロセスAが到着したとき、実行可能状態及び実行状態のプロセスはないものとする。

　なお、プロセスの登録と取出し，及び中断の処理でのオーバヘッドは考えない。また，CPUを割り当てられたプロセスは、タイムクウォンタム以外で中断することはない。

 

 

設問2

次の記述中の [            ] に入れる正しい答えを，解答群の中から選べ。

　プロセスの実行順序を決める別の方式に優先度順方式がある。優先度順方式の例を図3に示す。プロセスにはあらかじめ優先度が付けてあり，待ち行列は優先度ごとに用意してある。ここで，、先度は1～10の10種類で、値の大きい方が優先度は高い。

　この方式では、次のとおりにプロセスの実行を制御する。

1. プロセスを優先度に対応した待ち行列の末尾に登録する。
2. プロセスが登録されている優先度の最も高い待ち行列の先頭からプロセスを一つ取り出して実行を開始する。
3. 実行中のプロセスの優先度が2以上のとき、実行時間が20ミリ秒経過するごとに優先度を一つ下げる。優先度を下げた結果、実行中のプロセスの優先度が実行可能状態にある優先度の最も高いプロセスよりも低くなった場合、実行中のプロセスを中断して、(1)に戻る。
4. 実行中のプロセスが終了した場合、(2)に戻る。

　優先度順方式において、あるプロセスが終了した時点で表2に示す三つのプロセスだけが優先度に対応した待ち行列に登録されていたとする。このとき，三つのプロセスが終了する順番は [     c     ] である。そして、プロセスBの実行が終了したときのプロセスBの優先度は [     d     ] である。ここで，三つのプロセスが終了するまで新たに到着するプロセスはないものとする。

 

　なお、プロセスの登録と取出し、及び中断の処理でのオーバヘッドは考えない。また，CPUを割り当てられたプロセスは、タイムクウォンタム以外で中断することはない。

 

おまけ：平均ターンアラウンド時間も求めてみよう！

 

 

７．練習問題の答え

解答1

解答：イ

ディスパッチとは、複数の実行可能状態プロセスの中からCPUを割り当て、実行状態にすることを言います。

よって答えはイとなります。

（ちなみにアはスケジューリングの説明です。）

 

解答2

解答：イ

解答：ウ

矢印③に注目しましょう。

入出力動作の完了を待つ必要があるとき、実行状態から待ち状態に遷移するのでしたね。

なので(c)が待ち状態、(a)が実行状態とわかり、答えはウと確定できます。

 

ちなみに入出力動作が完了すると待ち状態から実行可能状態(b)に移ります。

 

もちろん他の矢印

① CPU使用権が移された：実行状態→実行可能状態

② CPU使用権が与えられた：実行可能状態→実行状態

も重要なので頭に入れておきましょう。

 

解答3

解答：ア

ラウンドロビンは、平等にCPU時間（処理時間）を与えるようなアルゴリズムでしたね。

よって答えはアとなります。

（ちなみにイが処理時間順、エが優先度順アルゴリズムです）

 

解答4

解答：イ（14）

ラウンドロビンの処理時間の問題は、必ず下のような図を書いて時間ごとに待ち行列、および処理されるプロセスがどのように変化するのかを必ず確認しましょう。

注意してほしいのが6秒〜9秒の部分です。

6秒の地点では、新しいプロセス3の生成と、定時間以内に終わらなかったプロセス2が同時に待ち行列に入ってきますね。

 

問題文を読むと、新しいプロセスの生成と中断されたプロセスの再開が同時に生じた場合には、新しく生成されたプロセスを優先するとありますね。

そのため、新しく生成されたプロセス3のほうが中断されたプロセス2よりも先に待ち行列に並びます。

 

なお、すでに待ち行列に並んでいるプロセス1には一切影響しないので注意してください。

（応用技術試験者ドットコムの解説を見ると、待ち行列が前から順に1, 3, 2ではなく、3, 1, 2と並んでしまっているのでサイト側のミスでしょうか……*4。）

 

それ以外の部分については図をご覧ください。

 

解答5

設問1の解答：[   a   ] … オ　[   b   ] … ウ
設問2の解答：[   c   ] … ウ　[   d   ] … オ

午後問題なので少し問題のボリュームが大きめです。

設問1

[   a   ]（解答：オ）

定時間順に処理すると、下の図のようにA, B, C, Dの順に処理されます。

よってターンアラウンドタイムは、

A：180 - 0 = 180（生成が0ms、終了が180ms）
B：260 - 10 = 250（生成が10ms、終了が260ms）
C：300 - 30 = 270（生成が30ms、終了が300ms）
D：320 - 50 = 270（生成が50ms、終了が320ms）

となり、ターンアラウンドタイムの平均は 242.5 msとなり、答えはオとなります。

 

（余談ですが処理時間が大きいものから順番に処理しているため、かなりターンアラウンド時間が大きくなります。）

 

[   b   ]（解答：ウ）

次にタイムクォンタムが20msのラウンドロビンです。

同じように図を書いていきましょう。

よってターンアラウンドタイムは、

A：320 - 0 = 180（生成が0ms、終了が320ms）
B：220 - 10 = 250（生成が10ms、終了が210ms）
C：160 - 30 = 270（生成が30ms、終了が130ms）
D：120 - 50 = 270（生成が50ms、終了が70ms）

となり、ターンアラウンドタイムの平均は 182.5 msとなり、答えはウとなります。

 

設問2

次に優先度を考慮したスケジューリングアルゴリズムについての問題です。

ポイントとしては、

• 実行時間20ms経過ごとに優先度-1
• 実行中のプロセスの優先度が、待ち行列内にあるプロセス内で最も高い優先度よりも小さくなった時点でプリエンプションが発生し、保留。

の2点です。

 

まずは落ち着いて図を書きましょう。

0ms時点

一番優先度が高いBから実行状態に（処理開始）

 

20ms時点

20ms経過したのでBの優先度が8→7に

待ち行列内にあるプロセスの中で優先度が最も高いプロセスは6なので継続してBを処理

 

40ms時点

また20ms経過したのでBの優先度が7→6に

まだ6未満ではないため、引き続き処理

 

60ms時点

また20ms経過したのでBの優先度が6→5に

ここで6未満になったためBを中断、待ち行列へ

 

3つの中で最も優先度が高いプロセスはAなので、Aを処理していく

 

80ms時点

20ms経過したのでAの優先度が6→5に

待ち行列内にあるプロセスの中で優先度が最も高いプロセスはB, Cの5なので継続してBを処理

 

100ms時点

また20ms経過したのでAの優先度が5→4に

ここで6未満になったためAを中断、待ち行列へ

 

3つの中で最も優先度が高いプロセスはB, Cの2つだが、より待ち行列の先頭にあるCから順番に処理。

 

120ms時点

20ms経過したのでCの優先度が5→4に

待ち行列内にあるプロセスの中で優先度が最も高いプロセスはBの5なのでここでCの実行が中断。

 

つぎに処理するプロセスは、3つの中で最も優先度が高いプロセスBとなる。

 

130ms時点

プロセスBの実行が完了。

この時点での優先度は5のため、[   d   ] の答えはオとなる。

 

次に処理するプロセスの候補として、ともに優先度が同じA, Cがあるがより待ち行列の先頭にあるのはAなのでAから順番に処理

 

150ms時点

プロセスAの実行が終了。

ここから230msまでずっとCのみが処理される。

（最終的にCの優先度は1となります）

 

よって B→A→C の順に処理が終了するので答えはウとなる。

 

おまけの解答

それぞれのターンアラウンドタイムは、

A：150ms　B：130ms　C：230ms

となるのでターンアラウンドタイムの平均は 170 msとなります。

 

８．さいごに

今回はプロセス（特に3つの状態）、およびスケジューリングアルゴリズムについての説明でした。

実行状態、実行可能状態、待ち状態などの状態変化、スケジューリングアルゴリズムは基本情報・応用情報ともによく出る分野なのでマスターしましょう！

 

次回は仮想記憶について説明していきたいと思います。

ではまた次回。