キューとは？

キューの意味

最初に入れたデータを最初に取り出す（先入れ先出し）データ構造。enqueueで末尾に追加、dequeueで先頭から取り出す。到着順に処理したい場面で使う。

キューの具体例

プリンタの印刷ジョブ、メッセージキューによる非同期処理、ラウンドロビン方式のタスクスケジューリング。

キューは試験でどう引っ掛けられる？

スタックと逆に覚えないこと。キューはFIFO（先入れ先出し）、スタックはLIFO（後入れ先出し）。再帰呼出しの戻り先や式の評価に使うのはスタック。また「優先度付きキュー」は名前にキューが付くが取り出し順は到着順ではなく優先度順で、FIFOではない。

キューと関連する用語

• スタック

キューが出た過去問

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

  正解：14

  要点：ラウンドロビンは待ち行列の順序と経過時刻を丁寧に追う

  タイムクウォンタム2秒で順に割り当てると、プロセス1が0〜4秒を使い残り1秒、続いてプロセス2が4〜6秒を実行します。6秒でプロセス3が生成され、新しいプロセスを優先する規則により待ち行列はプロセス1、プロセス3、プロセス2の順になります。以降は各プロセスが2秒ずつ交代し、プロセス1は7秒、プロセス3は16秒、プロセス2は17秒で終了します。プロセス2の生成時刻は3秒後なので、17−3で14秒後が答えです。

  出典：平成28年度 秋期 応用情報技術者試験 午前 問19（IPA）

• 多数のクライアントが，LANに接続された1台のプリンタを共同利用するときの印刷要求から印刷完了までの所要時間を，待ち行列理論を適用して見積もる場合について考える…

  正解：印刷の緊急性や印刷量の多少にかかわらず，先着順に印刷する。

  要点：M/M/1はポアソン到着・指数サービス・無限長FIFOが前提

  M/M/1モデルは、到着がポアソン分布、サービス時間が指数分布、窓口が1つ、待ち行列は無限長で先着順（FIFO）に処理される、という条件を前提とする。先着順に印刷するという運用はこのFIFOの前提に合致する。

  出典：平成28年度 春期 応用情報技術者試験 午前 問3（IPA）

• サイバーレスキュー隊（J-CRAT）の役割はどれか。

  正解：標的型サイバー攻撃を受けた組織や個人から提供された情報を分析し、社会や産業に重大な被害を及ぼしかねない標的型サイバー攻撃の把握、被害の分析、対策の早期着手の支援を行う。

  要点：J-CRATは標的型攻撃の被害分析と対策着手を支援する

  J-CRAT（サイバーレスキュー隊）はIPAが運営する組織で、標的型サイバー攻撃を受けた組織や個人からの相談・情報提供を受けて分析し、被害の拡大や連鎖を防ぐための助言や支援を行う。攻撃の把握、被害分析、早期の対策着手の支援が役割である。

  出典：平成29年度 秋期 応用情報技術者試験 午前 問42（IPA）

• コンピュータによる伝票処理システムがある。このシステムは，伝票データをためる待ち行列をもち，M/M/1の待ち行列モデルが適用できるものとする。平均待ち時間がT秒…

  正解：50

  要点：M/M/1の平均待ち時間はρ/(1−ρ)×平均サービス時間。

  M/M/1モデルでは、平均待ち時間（行列に並ぶ時間）は「利用率ρ÷(1−ρ)×平均サービス時間」で求まる。平均サービス時間がT秒なので、待ち時間がT秒以上になる条件はρ/(1−ρ)≧1、すなわちρ≧0.5である。よって利用率50％以上のときに平均待ち時間がT秒以上となる。

  出典：平成30年度 秋期 応用情報技術者試験 午前 問2（IPA）

• 処理は全てCPU処理である三つのジョブA，B，Cがある。それらを単独で実行したときの処理時間は，ジョブAは5分，ジョブBは10分，ジョブCは15分である。この三…

  正解：25

  要点：ラウンドロビンでは並行するジョブ数に反比例して進捗が遅くなる。

  タイムクウォンタムが十分小さいラウンドロビンでは、実行中のジョブがCPUを均等に分け合うとみなせる。3本が同時に動く間は各ジョブの進みが実時間の1/3なので、最短のAが5分ぶん処理を終える時点で経過時間は15分となる。以降はBとCの2本でCPUを二分し、残り5分のBはさらに10分かかるので、合計およそ25分でBが終了する。

  出典：平成30年度 秋期 応用情報技術者試験 午前 問16（IPA）