応用情報技術者 試験情報＆徹底解説

解説の④以降の記述が誤っているように思います。

＞④  開始から3秒後にジョブDが到着する。処理時間はD＜C＜BなのでDを処理する。
とありますが、ジョブDが到着したときジョブCは1秒分の処理を終えているため、
残り処理時間は C（2秒）＝D（2秒）＜B（4秒） となります。
ですので、ジョブDではなく、そのままジョブCを続けるということも考えられます。

同様に、
＞⑤  開始から4秒後にジョブEが到着する。処理時間はE＜D＜C＜BなのでEを処理する。
に関しても、ジョブEが到着したときジョブCは2秒分の処理を終えているため、
残り処理時間は C（1秒）＝E（1秒）＜D（2秒）＜B（4秒）  となり、
そのままジョブCを続けるということも考えられます。

あとは、残り時間順に E→D→Bと処理をして処理開始から12秒で
全てのジョブが終わりますので、結果的に答えも（エ）になるのですが、
④で処理をジョブDに限定してしまうのはマズいのでは？と思います。

Nasuさんの考え方は、残余処理時間順方式です。

この問題は、「残余」がついていない、ただの「処理時間順方式」ですから、ジョブが到着したときの直後の実行ジョブのスケジューリングには、表の「単独実行時の処理時間」の数値を用います。

通りすがりの者さん、お返事ありがとうございます。

あれから、どうもスッキリしなかったので、追加で調べてみたのですが、
この問題に関して、私のように解釈して解説しているサイトを何か所か見つけました。

さらに「処理時間順方式」に関しても掘り下げて調べてみたのですが、
「横取りを許さないアルゴリズム」であるということでした。
つまり、「処理中のジョブCを中断してジョブDの処理を開始する」という
解説④に書かれているようなことは起こらないと考えられます。
以上より、処理順は A→C→E→D→B になると思うのですが、いかがでしょうか…？

この投稿は投稿者により削除されました。(2018.03.22 11:52)

この投稿は投稿者により削除されました。(2018.03.22 11:54)

№1にて
＞残り処理時間は～
＞残り時間順に～
「残り〇〇」という記載をしてしまったのは良くなかったですね、すみません。

まず、処理時間順方式と残余処理時間順方式の違いは、理解できたでしょうか？

また、残余処理時間順方式は、プリエンプティブ(新たなジョブまたはタスクが到着した、つまり実行可能状態となったときに、再スケジュールする)です。

処理時間順方式は、私も気になって調べましたが、プリエンプティブとノンプリエンプティブの二つの説があります。管理人様は、プリエンプティブとして説明されています。
(掲示板のスレッド「応用情報技術者 平成25年春期 午前問17[0665]」のミルキー＠管理人(No.5)を見てください)

なお、アイテックの本試験問題の解説では、ノンプリエンプティブとして説明されています。私は、最初に解いたときはノンプリエンプティブと理解していました。

この問題は、幸いにもどちらの考え方で解いても解答が同じです。

＞まず、処理時間順方式と残余処理時間順方式の違いは、理解できたでしょうか？
はい、残余処理時間順方式も一緒に調べたので理解しました！

＞「応用情報技術者 平成25年春期 午前問17[0665]」のミルキー＠管理人(No.5)
１年以上前に同じような疑問を持たれていた方がいらっしゃったのですね(;^_^A

通りすがりの者さんの情報を加味すると、私の中では下記のような結論に至りました。
  ・二つの説があるにも関わらず、どちらとも明示していない不明確な設問である。
  ・ただ、今回の場合はどちらの説でも解答は同じになるので結果に影響はない。

たぶん、IPAは、というより、この問題の作成者は、プリエンプティブとノンプリエンプティブの二つの説があることの認識はなく、どちらか一方のつもりでしょう。それがどちらかを確かめる術はありませんが。

ネットには、処理時間順方式の説明が、残余処理時間順方式の内容だったりするものもあります。

このように、タスクのスケジューリング方式として、同じ用語でも異なる複数の解釈があるのは困りますね。

管理人様へ
通りすがりの者さんに頂いたアドバイスを元に考えましたところ、
処理時間順方式はプリエンプティブ/ノンプリエンプティブの２つの説が考えられるため
解説も２通り掲載した方が親切かつ理解が深まりやすいのではと思います。
お手数だとは思いますが、ご検討よろしくお願い致します。

この投稿は投稿者により削除されました。(2018.03.23 22:47)

＞今さら聞けないさん
お返事ありがとうございます。
「多重度１」に関して、私は「同時に実行できるジョブが１つ」という意味だと解釈しているのですが、「多重度」という項目は「割り込みの可・不可」にも影響するのでしょうか？

＞通りすがりの者さん
処理時間順方式について、あれからさらに調べてみたのですが、
「処理時間順方式：ノンプリエンプティブ（横取り不可能）」
と紹介しているサイトはいくつか見つけることが出来たのですが、
プリエンプティブとして紹介しているサイトを見つけることが出来ませんでした。
通りすがりの者さんがおっしゃっている「２つの説」というのは、
どこの情報を元にされた説なのでしょうか？
詳しく知りたいので教えて欲しいです。

この設問、調べれば調べるほど迷宮入りしているような気がします…(;´Д｀)

Nasuさんの探求心には敬服します。
処理時間順方式について再度調べると、ノンプリエンプティブの説が圧倒的に多く、プリエンプティブの説は極々少数派でした。

  ☆://wiki.suikawiki.org/n/スケジューリング  ←  ☆はhttps
誰かの独り言のようなサイトですが、「予想処理時間がより短いプロセスが到着すると横取りが起こります。」とあります。信頼性は薄そうです。

管理人様
掲示板のスレッド「応用情報技術者 平成25年春期 午前問17[0665]」のミルキー＠管理人(No.5)にある、調べられた元ネタはどこなのでしょうか？
また、話は少しそれますが、
ソフトウェア開発技術者 平成20年秋期 午前問24
の解説に、
「残り時間順・到着順・処理時間順はすべてノンプリエンプティブな処理に分類されます」
とありますが、とても気になります。
処理時間順方式はノンプリエンプティブ、残余処理時間順方式はプリエンプティブとするのが、スッキリするような気がします。

通りすがりの者さんに教えて頂いたサイト（SuikaWiki）の管理人さん宛に
処理時間順の記述についての情報元を問い合わせるメールを送りました。

これは、ある大学の講義資料の一部なのですが、
☆://www.info.kindai.ac.jp/OS/lecture/OS03note.pdf ←  ☆はhttps
ページの終盤で
  処理時間順：横取り不可能
  残余処理時間順：横取り可能
とハッキリ書かれています。
さすがに大学の講義で誤った情報を教えるとは考え難く、
やはり「処理時間順＝ノンプリエンプティブ」説が正しいのではないか？
と思い始めています。

> 「多重度１」に関して、私は「同時に実行できるジョブが１つ」という意味だと解釈している
> しているのですが、「多重度」という項目は「割り込みの可・不可」にも影響するのでしょうか？

自分調べですが、「ジョブの多重度が1」に関しては割り込みは関係なさそうでした。
安易な投稿をしてしまったようです。一応、その投稿は削除しておきました。

＞今さら聞けないさん
いえいえ！そんなことないですよ！
私も「多重度」については曖昧でしたし、再確認する切っ掛けにもなったので、
別の視点からの意見を投稿してくださって嬉しかったです。
ありがとうございました(^-^)

何か疑問点であれば何日でもどこまでも納得いくまで考える。
皆様はエンジニアの鑑です！システムの為なら猫の手も借りるというもの。
猫の分際で僭越ですが、自分はタスクスケジュールを以下のように考えていました。

●到着順方式（FCFS）ノンプリエンプション
●優先度順方式  プリエンプション
●ラウンドロビン方式  タイマ割り込みあり
●多重待ち行列（ラウンドロビン＋優先度方式）
●処理時間方式（SPT）

ちなみに某教科書のO先生は「到着順方式のみがノンプリエンプティブ方式であることを押さえておきましょう」と書かれています。
よって時間処理方式にはノンプリもプリも発生しないものと考えていました。
実行可能状態となったタスク順に割り当てるとか（到着順）、タスクに優先度を割り当てるとか（優先度）とか以前の問題で、処理時間方式は最初から「短いタスクに高い優先度」を与えると決めちゃってるんですから。だから実装が難しい。
全然すっとんきょうな事書いているかもしれませんが猫なのでご容赦下さい。

＞猫アプリさん
コメントありがとうございます。
確かに、事前にジョブの処理時間が分からないことが多いと考えられるので、
実際には処理時間順方式の実装は難しいみたいですね。

＞通りすがりの者さん
例のサイトの管理人さんからお返事が届きました。
「記事の出典が不明であり、他のサイトと異なる説明がされているのであれば、
誤っている可能性が高いです。ご指摘を踏まえて修正させていただきます」
とのことでした。

＞管理人様
長くなりましたが、本設問で問われている「処理時間順方式」については、
どうやらノンプリエンプティブ方式（横取り不可能）が正しいようです。
従って、ジョブの処理順は A→C→E→D→B となりますので、
解説④以降の説明が誤っていることになります
大変お手数ですが修正をお願い致します。

Nasuさん
ありがとうございます。例のサイトは既に修正されました。今回は、大活躍でしたね。

管理人様
私もNasuさんと同意見です。また、修正されるなら、
ソフトウェア開発技術者 平成20年秋期 午前問24
の解説の見直しもお願いします。

Nasuさん
大変ご苦労様でした。
おかげでこの問題は目をつぶってでもできそうです。（笑）

皆さまから投稿していただいた記事の内容を整理して解説文に反映いたします。修正作業の実施まで少しお時間をいただければと思います。

修正作業が遅れてしまい申し訳ございませんでした。
こちらでもウェブ上を探索してみましたが、処理時間順方式は"横取りなし"という認識で間違いなさそうです。ですので、ノンプリエンプティブとして解説の一部を書き直しました。

[情報元]
  http://www.cse.kyoto-su.ac.jp/~oomoto/lecture/SystemSoftware/process.html
>6-3 スケジューリング
>「処理時間の短いプロセスから順次処理する．横取り無し．」

http://www.am.ics.keio.ac.jp/members/morimura/teu_os/OS_2.ppt (注  パワーポイント)
>SJF (shortest job first)
>・処理時間の短いプロセスから順にCPUに割り当てる
>・横取りなし

http://mikilab.doshisha.ac.jp/dia/seminar/2003/saiteki3_2003.pdf
>処理時間の短いプロセスから順に CPUに割り当てる，横取りのないアルゴリズムである．

https://en.wikipedia.org/wiki/Shortest_job_next
>SJN（Shortest job next） is a "non-preemptive" algorithm.

＞管理人様
ご対応ありがとうございます。

大変申し上げにくいのですが、修正して頂いた解説の④にまだ気になる点があります。

＞この時点で処理時間の大小はD＜C＜Bとなるが
という記述になっていますが、ジョブCは1秒分の処理を終えているため、
この時点での処理時間の大小は、C（2秒）＝ D（2秒）＜B（4秒）が正しいです。

しかし、改めて考えてみると、横取り不可能なアルゴリズムな訳ですから、
ジョブCをそのまま継続することは明確なので、この時点の処理時間を
他のジョブと比較するという記述そのものが不要なのかもしれません。

以上を参考に、お手数ですが、解説文の再検討をお願いしたいと思います。

>Nasuさん

＞この時点で処理時間の大小はD＜C＜Bとなるが
この説明ですが、本問のスケジューリング方式は処理時間順なので、当初の予想処理時間を比較するものと考えて、D（2秒）＜C（3秒）＜B（4秒）としています。残余処理時間順方式であれば、NasuさんのおっしゃるようにC（2秒）＝ D（2秒）＜B（4秒）なると思うのですが...。

いかがでしょうか？もし私の認識不足でしたら申し訳ございません。

＞管理人様

いえいえ！コメントありがとうございます！

＞当初の予想処理時間を比較するものと考えて
管理人様の記述にそのような意図があったのでしたら納得です。

ただ、日本語の解釈が難しいところではありますが、
＞この時点で処理時間の大小は～
という書き方をしてしまうと、「その時点の各ジョブの残余処理時間」を
連想させてしまうのではないか？と思います。（私がそうでした…）

より分かりやすい文章になるように、私ももうちょっと考えてみて、
ご提案させていただこうと思います。

私なりに分かりやすいと思われる解説文を考えてみました。
ジョブの到着、選択、処理開始の記述に関しては、
元の解説文を踏襲しつつ表記を統一し、処理完了時間も明確に記載しました。
ルールに従って記述しているので、ちょっと堅苦しいかもしれませんが、
参考にして頂ければと思います。

---------------------------------------------------------
①開始時点で到着しているのはジョブAだけなので、
  CPUはジョブAの処理を開始する。
②開始から1秒後にジョブBが到着する。CPUはジョブAの処理を続ける。
③開始から2秒後にジョブCが到着する。同時にジョブAの処理が完了する。
  未処理のタスクの処理時間を比較するとC＜Bなので、
  CPUはジョブCの処理を開始する。
④開始から3秒後にジョブDが到着する。CPUはジョブCの処理を続ける。
⑤開始から4秒後にジョブEが到着する。CPUはジョブCの処理を続ける。
⑥開始から5秒後にジョブCの処理が完了する。
  未処理のタスクの処理時間を比較するとE＜D＜Bなので、
  CPUはジョブEの処理を開始する。
⑦開始から6秒後にジョブEの処理が完了する。
  未処理のタスクの処理時間を比較するとD＜Bなので、
  CPUはジョブDの処理を開始する。
⑧開始から8秒後にジョブDの処理が完了する。
  CPUは最後に残ったジョブBの処理を開始する。
⑨開始から12秒後にジョブBの処理が完了し、全てのジョブの処理が完了する。

＞管理人様

解説下部の画像で、Cの処理時間が4秒になっているようです。
正しくは3秒ですので、併せて修正をお願い致します。

ご提案ありがとうございます。
ご投稿いただいた説明をそのまま採用させていただきました。また画像についても訂正版をアップロードいたしました。

平成25年春期  問17
  http://www.ap-siken.com/kakomon/25_haru/q17.html

>管理人様
お返事が遅くなってしまい申し訳ありません。

解説文が修正されているのを確認致しました。
ご対応ありがとうございました！