スケジューリングと排他制御の計算
CPU・I/O・共有資源の動きを表から時刻順に書き出し、「何ミリ秒後に終わるか」「何ミリ秒待ったか」「使用率はいくつか」を計算できるようになる。あわせて、ターンアラウンドタイムの関係式とセマフォの目的を選べるようになる。
科目Aでは、表を読んで「何ミリ秒か」を答える計算問題が出ることがあります（本試験・免除試験の過去問に繰り返し登場）。公式の暗記ではなく、時間を区切って一つずつ動きを追えるかが問われます。
このレッスンで稽古する（用語チェック・過去問）結論：時間の線を引いて、1区間ずつ埋めれば解ける
この単元の計算問題は、ほぼ全部がタイムチャート（横に時間、縦にタスクを並べた表）を書けば解けます。暗算で済ませようとすると、「待ち」を1つ見落として選択肢のひっかけに引っかかります。
作業は次の3つだけです。
- 区切りの時刻（誰かの処理が終わる時刻）ごとに列を作る
- 各区間で、CPU（計算する装置）・I/O（入出力装置。ディスクや通信など）・共有資源を誰が使っているかを書く
- 使いたいのに使えないタスクには「待ち」と書く
たとえるなら、CPU はレジが1台だけのお店です。レジが空いていなければ、客は並んで待つしかありません。
時間の関係式（ターンアラウンドタイム・応答時間）
ターンアラウンドタイム（TAT）は、ジョブ（ひとまとまりの仕事）を依頼してから結果が全部返るまでの時間です。中身は「CPUで計算した時間」「I/Oを使った時間」「順番を待った時間」の合計です。
TAT ＝ CPU時間 ＋ 入出力時間 ＋ 処理待ち時間 → 移項すると 処理待ち時間 ＝ TAT − CPU時間 − 入出力時間
オンライン処理の応答時間も同じ考え方で、内訳を足し合わせたものです。
応答時間 ＝ 端末処理時間 ＋ 回線伝送時間 ＋ サーバ処理時間 → サーバ処理時間 ＝ 応答時間 − 回線伝送時間 − 端末処理時間
| 用語 | 何から何まで | 内訳 |
|---|---|---|
| ターンアラウンドタイム | ジョブの到着（投入）→ 処理がすべて終わる | CPU時間＋入出力時間＋処理待ち時間 |
| 応答時間（レスポンスタイム） | 端末で要求を出す → 応答が返ってくる | 端末処理＋回線伝送＋サーバ処理 |
| 処理待ち時間 | CPUなどの順番を待っている時間 | TATから実際に処理した時間を引いた残り |
TATを計算するときは、終了時刻 − 到着時刻で求めます。到着が0秒でないジョブに注意してください。
優先度方式：偉い人が戻ってきたらCPUを譲る
優先度順方式では、CPUを使えるタスクのうち優先度が最も高いものにCPUを割り当てます。高優先度のタスクがI/Oから戻ってくると、低優先度のタスクは実行の途中でもCPUを取り上げられます。これをプリエンプション（横取り）といいます。救急外来で、重症の患者が来たら診察の順番が入れ替わるのと同じです。
追うときのルールは次のとおりです。
- CPUは1つだけ。各区間で、CPUを使いたいタスクのうち優先度が最も高いものだけが使える
- 「I/Oは競合しない」と書いてあれば、I/Oは何個のタスクが同時に使ってもよい
- 横取りされたタスクは、CPU処理の残り時間を後で続きから実行する（最初からやり直しではない）
タスクの状態は前のレッスンの3つで数えます。
| 状態 | 意味 | 例題での数え方 |
|---|---|---|
| 実行状態 | CPUを使って処理している | 表の「CPU」の区間 |
| 実行可能状態 | CPUさえ空けばすぐ動ける（CPUの割当て待ち） | 表の「待ち」の区間 |
| 待ち状態 | I/Oの完了を待っている | 表の「I/O」の区間 |
「実行可能状態にある時間は？」と聞かれたら、CPUの割当てを待っていた時間だけを足します。I/Oを使っていた時間は含めません。
到着順と処理時間順：誰を次に動かすか
多重度（同時に実行できるジョブの数）が1のときは、1つのジョブが終わった時点で次に動かすジョブを選びます。選び方の違いを表で押さえておきます。
| 方式 | 次に選ぶジョブ | ひっかけポイント |
|---|---|---|
| 到着順方式（FCFS） | 先に到着したもの | 到着時刻を引かずに、終了時刻をTATと答えてしまう |
| 処理時間順方式（SPT） | その時点で到着済みのジョブのうち、処理時間が最短のもの | まだ到着していないジョブまで比べてしまう／到着順に並べてしまう |
| 優先度順方式 | 優先度が最も高いもの（途中で横取りもある） | I/O中のタスクを「待ち」と書いてしまう |
SPTでは、ジョブが終わるたびに「いま到着しているのは誰か」を確認し直すのがコツです。
排他資源・共有I/O：使用中なら終わるまで待つ
排他制御とは、共有資源（複数のタスクが使うプリンタやファイルなど）を一度に1つのタスクしか使えないようにする仕組みです。CPUが2台あって同時に計算できても、共有資源Rが使用中なら、後から来たタスクはRが空くまで待たされます。
問題ごとに条件の書き方が違うので、最初に条件を読み分けます。
| 問題文の条件 | 意味 | タイムチャートでの扱い |
|---|---|---|
| I/Oは競合しない | I/Oは同時に何個でも動く | I/Oの待ちは発生しない |
| I/Oの同時動作はできない／同一のI/Oを使用 | I/Oは1つずつしか動かない | I/O使用中なら「I/O待ち」を書く |
| 資源Rを排他的に使用 | Rは一度に1タスクだけ | R使用中なら「R待ち」を書く |
| CPU処理は中断されない | 横取りなし | 優先度が高いタスクが来ても、今のCPU処理が終わるまで待つ |
CPUとI/Oが両方とも1つずつで、順番待ちが発生するタイプの問題（免除試験で繰り返し出題）は、CPUの行とI/Oの行を作って、それぞれの装置を誰が使っているかを書くと速く解けます。使用率を聞かれたら「装置が動いていた合計時間 ÷ 全体の経過時間」で求めます。
セマフォ：共有資源の「使用中」札
セマフォは、共有資源の排他制御や、プロセス同士のタイミング合わせ（同期）に使う仕組みです。トイレの「使用中」札のように、空いている資源の数をカウンタで管理します。資源を使う前にカウンタを1減らし（P操作）、使い終わったら1増やします（V操作）。0のときに使おうとしたタスクは、空くまで待たされます。
試験で問われるのは「セマフォの目的は何か」です。答えは**共有資源の管理（排他制御）**で、スタック・スラッシング・セグメンテーションのような響きの似た別の用語が誤りの選択肢として並びます。
試験での問われ方
- タイムチャート選択型：3ミリ秒〜10ミリ秒のように途中の区間だけを切り出した図を選ばせる。0ミリ秒から自分で書いておかないと、途中の状態が分からない
- 数値型：「全タスクが終わるまで何ミリ秒か」「タスクCが実行可能状態にあった時間は延べ何ミリ秒か」「CPU使用率はいくつか」。選択肢には待ちを1回見落とした値が必ず混ざっている
- 式選択型：TATや応答時間の内訳の式。＋と−を入れ替えた選択肢が並ぶ。「全体＝部分の合計」から移項すれば迷わない
- 用語型：セマフォの目的。似た響きの別の用語との見分け
優先度方式：タスクCが実行可能状態にある時間
| タスク | 優先度 | 単独実行時の動作順序と処理時間（単位 ミリ秒） |
|---|---|---|
| A | 高 | CPU(2)→ I/O(6)→ CPU(4) |
| B | 中 | CPU(2)→ I/O(4)→ CPU(2) |
| C | 低 | CPU(2)→ I/O(2)→ CPU(3) |
ア 6
イ 8
ウ 10
エ 12
出典：基本情報技術者試験 科目A免除 修了試験 20160124 実施分 問16
解き方と答えを見る
- 条件を確認する：優先度は A（高）＞ B（中）＞ C（低）。I/Oは競合しない（同時に使ってよい）。
- 0〜2ms：3つとも実行可能だが、優先度が最も高いAがCPUを使う（CPU 2ms）。BとCは待ち。
- 2ms：AはI/O（6ms）に移り、2〜8msはI/O中。空いたCPUはBが使う（2〜4ms）。Cは引き続き待ち。
- 4ms：BはI/O（4ms）に移り、4〜8msはI/O中。CPUはようやくCが使う（4〜6ms）。6msからCはI/O（2ms）に移り、6〜8msはI/O中。
- 8ms：A・B・Cが同時にI/Oを終えて、3つとも実行可能状態になる。優先度順にA（CPU 4ms：8〜12ms）→ B（CPU 2ms：12〜14ms）→ C（CPU 3ms：14〜17ms）の順に実行する。
- Cが実行可能状態（CPUの割当て待ち）だった区間を拾う：0〜4ms で 4ms、8〜14ms で 6ms。
- 合計：4 ＋ 6 ＝ 10ms。I/O中（6〜8ms）は待ち状態なので数えない。
答え：10ミリ秒（ウ）
処理時間順（SPT）方式：ジョブBのターンアラウンドタイム
| ジョブ | 到着時刻 | 単独実行時の処理時間 |
|---|---|---|
| A | 0 | 2 |
| B | 1 | 4 |
| C | 2 | 3 |
| D | 3 | 2 |
| E | 4 | 1 |
ア 8
イ 9
ウ 10
エ 11
出典：基本情報技術者試験 科目A免除 修了試験 20210725 実施分 問17
解き方と答えを見る
- 0秒：到着しているのはAだけなので、Aを実行する（0〜2秒）。
- 2秒：到着済みで未実行なのは B（処理時間4秒）と C（3秒）。D（到着3秒）とE（到着4秒）はまだ来ていないので比べない。短いCを実行する（2〜5秒）。
- 5秒：到着済みで未実行なのは B（4秒）・D（2秒）・E（1秒）。最も短いEを実行する（5〜6秒）。
- 6秒：残りは B（4秒）と D（2秒）。Dを実行する（6〜8秒）。
- 8秒：最後にBを実行する（8〜12秒）。
- BのTAT ＝ 終了時刻 − 到着時刻 ＝ 12 − 1 ＝ 11秒。
答え：11秒（エ）
CPU 2台＋排他資源R：2つのタスクが終わるまでの時間
ア 120
イ 140
ウ 150
エ 200
解き方と答えを見る
- CPUは2台なので、AとBは最初から同時にCPUを使える。
- A：CPU 0〜10ms。10msで資源Rを要求し、Rは空いているので 10〜60ms でRを使う。
- B：CPU 0〜40ms。40msでRを要求するが、Aが60msまで使っているので 40〜60ms はR待ち。
- B：60〜110ms でRを使う。110〜140ms でCPU 30ms を使い、140msに完了する。
- A：60msにRを返し、60〜120ms でCPU 60ms を使って、120msに完了する。
- 遅いほうの完了時刻が答え：max(120, 140) ＝ 140ms。待ちを無視して B を 40＋50＋30＝120ms と計算すると、誤りの選択肢アを選んでしまう。
答え：140ミリ秒（イ）
CPU 1個・I/O同時動作不可：全タスクが終わるまでの時間
| 優先度 | 単独実行時の動作順序と処理時間（ミリ秒） |
|---|---|
| 高 | CPU(2) → I/O(7) → CPU(3) → I/O(4) → CPU(3) |
| 低 | CPU(2) → I/O(3) → CPU(2) → I/O(2) → CPU(3) |
ア 19
イ 20
ウ 21
エ 22
出典：基本情報技術者試験 科目A免除 修了試験 20180128 実施分 問16
解き方と答えを見る
- 条件を確認する：CPUは1個、I/Oも1つずつしか動かない。優先度が高いタスクを「高」、低いタスクを「低」と呼ぶ。
- 高：CPU 0〜2ms → I/O 2〜9ms。
- 低：高がI/Oに移った後に CPU 2〜4ms。4msでI/Oを使いたいが、高が9msまで使っているので 4〜9ms はI/O待ち。
- 9ms：高はCPUへ移る（9〜12ms）。I/Oが空いたので、低が I/O を使う（9〜12ms）。
- 12ms：高はI/Oへ移る（12〜16ms）。低はCPUを使う（12〜14ms）。14msで低はI/Oを使いたいが、16msまで待つ。
- 16ms：高はCPUへ移る（16〜19ms）で、19msに完了する。低は I/O を使う（16〜18ms）。
- 18ms：低はCPUを使いたいが、高が19msまで使っているので待つ。低は CPU 19〜22ms で完了する。
- 全体の終了時刻は 22ms。I/Oの待ちを見落とすと、19〜21ms の誤りの選択肢を選んでしまう。
答え：22ミリ秒（エ）
CPUと磁気ディスクの使用率
| ジョブ | CPUの処理時間 | 磁気ディスク装置の処理時間 |
|---|---|---|
| A | 3 | 7 |
| B | 12 | 10 |
| CPUの使用率 | 磁気ディスク装置の使用率 | |
|---|---|---|
| ア | 0.47 | 0.53 |
| イ | 0.60 | 0.68 |
| ウ | 0.79 | 0.89 |
| エ | 0.88 | 1.00 |
ア CPUの使用率 0.47，磁気ディスク装置の使用率 0.53
イ CPUの使用率 0.60，磁気ディスク装置の使用率 0.68
ウ CPUの使用率 0.79，磁気ディスク装置の使用率 0.89
エ CPUの使用率 0.88，磁気ディスク装置の使用率 1.00
出典：基本情報技術者試験 科目A免除 修了試験 20190127 実施分 問13
解き方と答えを見る
- A：CPU 0〜3秒 → ディスク 3〜10秒。
- B：Aの後にCPUを使う（3〜15秒、12秒）。15秒でディスクを使う。ディスクは10秒で空いているので、待たずに 15〜25秒（10秒）使う。
- 全体の経過時間 ＝ 25秒。
- CPUが動いていた時間 ＝ 3 ＋ 12 ＝ 15秒 → CPU使用率 ＝ 15 ÷ 25 ＝ 0.60。
- ディスクが動いていた時間 ＝ 7 ＋ 10 ＝ 17秒 → ディスク使用率 ＝ 17 ÷ 25 ＝ 0.68。
答え：CPU 0.60、磁気ディスク 0.68（イ）
要点（試験直前に読む）
- タイムチャートは0ミリ秒から書く。区切りは「誰かの処理が終わった時刻」。
- TAT ＝ CPU時間＋入出力時間＋処理待ち時間。TAT ＝ 終了時刻 − 到着時刻。
- 応答時間 ＝ 端末処理＋回線伝送＋サーバ処理。求めたい項目は全体から引き算で出す。
- 優先度方式は、高優先度のタスクが戻るとCPUを横取りする。横取りされたタスクは残り時間を後で続きから実行する。
- SPTは、ジョブが終わるたびに「到着済み」のジョブの中から最短のものを選ぶ。
- セマフォの目的 ＝ 共有資源の管理（排他制御・同期）。
ひっかけ
- 「実行可能状態の時間」にI/O中の時間を足してしまう → 数えるのはCPUの割当て待ちの区間だけ。
- 「I/Oは競合しない」と「I/Oの同時動作はできない」を読み違える → 最初に条件を表に書き出し、I/O待ちが発生するかを決める。
- 共有資源Rの待ちを無視して、各タスクの処理時間を足すだけで答える → 短めの誤りの選択肢が必ず用意されている。
- TATを終了時刻のまま答える → 到着時刻を引く。
- SPTで、まだ到着していないジョブまで比べてしまう → 選ぶたびに到着時刻を確認する。
用語（14）
ジョブが到着してから処理が全部終わるまでの時間で、CPU時間・入出力時間・処理待ち時間の合計。
⚠ 応答時間：オンライン処理で、要求を出してから応答が返り始めるまで。TATはジョブ全体が終わるまで。
端末から要求を出してから応答が返ってくるまでの時間で、端末処理・回線伝送・サーバ処理の合計。
⚠ ターンアラウンドタイム：バッチ処理（まとめて処理する方式）のジョブ全体の所要時間を指すことが多い。
CPUなどの順番待ちで、何も処理されずに経過した時間。
⚠ 入出力時間：I/Oを使って実際に処理している時間であり、待ちではない。
CPUさえ割り当てられればすぐ動ける状態で、CPUの割当てを待っている。
⚠ 待ち状態：I/Oの完了を待っている状態。「実行可能状態の時間」にI/O中は含めない。
入出力などの完了を待っていて、CPUを渡されても動けない状態。
⚠ 実行可能状態：CPUの割当てを待っているだけで、すぐ動ける。
実行可能なタスクのうち、優先度が最も高いものにCPUを割り当てる方式。
⚠ 到着順方式：優先度ではなく、先に来た順に動かす。
実行中のタスクからOSがCPUを取り上げ、優先度の高いタスクに切り替えること。
⚠ 「CPU処理は中断されない」という条件の問題では横取りが起きない。条件文を必ず確認する。
先に到着したジョブから順に実行する方式。
⚠ 処理時間順方式：到着済みのジョブのうち、処理時間が短いものから実行する。
ジョブが終わるたびに、その時点で到着済みのジョブのうち処理時間が最短のものを選んで実行する方式。
⚠ 到着順方式。また、まだ到着していないジョブは比較の対象にならない。
同時に実行できるジョブの数で、1なら一度に1つずつ順番に処理する。
共有資源を同時に1つのタスクしか使えないようにして、データの競合を防ぐ仕組み。
複数のタスクやプロセスが共通して使う装置やデータ（プリンタ、ファイルなど）。
空いている資源の数をカウンタで管理し、共有資源の排他制御や同期を行う仕組み。
⚠ スラッシング（ページの入れ替えが多発して性能が落ちる現象）やスタック（後入れ先出しのデータ構造）とは無関係。
全体の経過時間のうち、CPUが実際に動いていた時間の割合。
⚠ 分母は各ジョブの処理時間の合計ではなく、最初から最後までの経過時間。
このレッスンの過去問
- 優先度方式タスクスケジューリングのCPU遊休時間平成30年度 春期 基本情報技術者試験 午前 問16
- 処理時間順(SPT)方式のターンアラウンドタイム計算基本情報技術者試験 科目A免除 修了試験 20210725 実施分 問17
- ターンアラウンドタイムと処理待ち時間の関係平成24年度 春期 基本情報技術者試験 午前 問19
- 排他資源を伴うタスク実行時間の計算平成26年度 秋期 基本情報技術者試験 午前 問17
- CPUとI/O競合下のタスク実行時間計算基本情報技術者試験 科目A免除 修了試験 20190127 実施分 問13
- セマフォの目的(共有資源の排他制御)基本情報技術者試験 科目A免除 修了試験 20140622 実施分 問17