【状態遷移】基本情報技術者試験

状態遷移とは

情報処理で用いられる状態遷移とはマルチプログラミングにおいて処理の最小単位であるタスクと呼ばれる処理を切り替えながら実行していきますが、そのタスクの状態の移り変わりのことです。 この移り変わりを図示したものを状態遷移図と呼び、時間や何らかのアクションにより状態が移り変わる様子を表した図です。 起こりうる状態を選んで表し、起こったアクションを矢印として線で結びます。

過去出題問題（平成20年秋午前問29）

頭はマルチタスクで動作するコンピューターにおけるタスクの状態遷移を表したものである実行状態のタスクが実行可能状態に遷移するのはどれか。

ア：自分より優先順位の高いタスクが実行可能状態になった

イ：タスクが生成された

ウ： 入出力要求による処理を完了した

エ：入出力要求を行った

解放

これが状態遷移と呼ばれるものです。三つの待ち状態、実行可能状態、実行状態の移り変わりを表しています。実行状態のタスクが実行可能状態に遷移する箇所は牡蠣の太い矢印です。

どういう場合にこれが起こるのでしょう。

実行状態は文字通り、実行している状態で、実行可能状態とはタスクを実行する条件が整い、実行状態の他のタスクの処理が終了するのを待っている状態、または実行状態にあったが自分より優先度の高いタスクが実行可能状態になったため、自分の処理が中断されて実行可能状態にさせられているという二つのケースがあります。そして実行状態から直接実行可能状態になるのは自分より優先順位の高いタスクが実行可能状態になったため CPU 所有権が他のタスクに移ってしまったケースです。通常は「 待ち状態→ 実行可能状態→実行状態→待ち状態」、例外的に「 実行→実行可能状態」に移り、これは優先度の高い他のタスクにやられたと覚えましょう。

答え　ア

過去出題問題（平成18年秋午前問題29）

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

解法

キーワードの実行可能・実行・ 待ち状態について状態遷移の要因を見て ABC にどの状態が当てはまるか考えてみましょう。まず①から a から b に状態が遷移したので b は 実行可能状態、ただし映画実行状態とはまだ確定していません。 実行可能状態から待ち状態に遷移する可能性もあります。次に②で CPU 使用権が与えられて絵に遷移しましたので A は実行状態ということになります。

ここで状態遷移図についてポイントがひとつあります。それは待ち状態からいきなり実行状態には行かないということです。実行状態になるにはコンピューターのメモリやディスクが割り当てられる実行可能状態になって初めて実行状態になります。すなわち実行状態である a に矢印が出ているだけなのは b だけです。 B は実行可能状態で C は待ちの状態でした。

過去出題問題（平成18年春午前問9）

次の表は文字列を検索するための状態遷移表である。 検査では、初期状態を A とし、文字列の検査中に状態がeとなれば不合格とする。回答表で示される文字列のうち、不合格となるのはどれか。ここで、 文字列は左端から検査し、解答群中の三角は空白を表す。

ア +0010

イ -1

ウ 12.2

エ 9.△

解法

ア、イ、ウ、エの初期状態は全て aです。

ア 「+0010」場合、最初は符号ですので a → c になります。次に数字の0があるので c → b になりますね。その後数字が三つ続くので b → b になり最後は b になります。
イ -1は、最初は符号なので a → c になります。次に数字の1があるので、 c → b になります。
ウ 12.2は最初は数字の1なので a → b になります次に数字の2があるので、 b → b になります。次は小数点なので、 b → dになり次が数字の2なので、d → e になります。
エ 9.△は最初は数字の9なので a → b になります。次は小数点なので、 b →d になります。次が空白なので d → aになります。

答え：ウ

まとめ

状態遷移図はほぼ毎回出題されています。

状態遷移を理解するにはまずマルチプログラミングを理解しなくてはなりません。例えば、ある端末から何かの照会を行っている場合、そのシステムで使っている端末が複数あったとしましょう。

 CPU が一つの場合、 基本的には一つのプログラムしか実行できません。この場合どうなるかと言うと、他の人が先に照会処理を行っていた場合、 あなたはその処理が終わるまでずっと待たされ続けることになります。チケット受付電話がいつも話中で「ただいま、。後ほどおかけ直しください」と何度も聞かされ不愉快な思いをしたことありませんか？マルチプログラミングとはプログラムをタスクという小さな処理の単位に分割して、そのタスクの状態を切り替えながら実行するやり方でマルチタスクとかマルチプロセスと言います。 逆に同時に一つの処理しかできないやり方をシングルタスクと言います。状態遷移とタスクは対になるものと覚えてください。マルチタスクではタスクを待ち状態、実行可能状態、 実行状態の三つに状態を切り替えます。たくさんあるタスクに対してこの状態を非常に短い時間で頻繁に切り替えながら処理を行います。端末側のユーザーから見ると、短い時間で状態が切り替わっているので複数の紹介が同時に行われているように見えます。少しずつ処理が行われていますので待たされぱなしでもありません。そして三つの状態の移動を「 状態遷移」というのです。マルチプログラムの元になっている「タスク」が三つの状態を取りながら処理されていることを理解し、そしてその状態とは「 実行可能状態」「実行状態」「待ち状態」です。この三つの状態は覚えてしまいましょう。