キューとは？

キューの意味

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

キューの具体例

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

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

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

キューと関連する用語

• スタック
• リスト

キューが出た過去問

• 仮想記憶方式に関する記述のうち，適切なものはどれか。

  正解：LRUアルゴリズムは，使用後の経過時間が最長のページを置換対象とするページ置換アルゴリズムである。

  要点：LRUは最長未使用ページを置換する。局所性が前提

  LRU（Least Recently Used）は最後に参照されてから最も時間が経ったページ、すなわち最長未使用のページを追い出すアルゴリズムである。参照の局所性から、直近に使われていないページは今後も使われにくいという前提に立つ。ページ置換方式としてFIFOより一般にヒット率が高い。

  出典：平成28年度 春期 高度共通_午前I試験 am1 問6（IPA）

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

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

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

  J-CRAT（サイバーレスキュー隊）はIPAが運営し、標的型サイバー攻撃を受けた組織からの相談・情報提供を受けて分析し、被害の拡大や連鎖を防ぐための早期対処を支援する。特に攻撃の連鎖の起点になりやすい組織を助けることで、社会全体への波及を抑えることを狙う。政府機関の監視を担うGSOCやJ-CSIP、ISOGとは役割が異なる。

  出典：平成29年度 秋期 高度共通_午前I試験 am1 問14（IPA）

• 4ブロックのキャッシュメモリC0〜C3が表に示す状態である。ここで，新たに別のブロックの内容をキャッシュメモリにロードする必要が生じたとき，C2のブロックを置換…

  正解：LRU

  要点：LRUは最終参照が最古、FIFOはロードが最古を追い出す

  C2は最終参照時刻が0:05で4つの中で最も古く、最後に使われてから最も長く放置されている。最長未使用のブロックを追い出すのはLRUである。FIFOならロード時刻が最も古いC0、LIFOなら最も新しいC3、LFUなら参照回数が最少のC1が対象になる。

  出典：平成29年度 春期 高度共通_午前I試験 am1 問6（IPA）

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

  正解：50

  要点：M/M/1の平均待ち時間はρ/(1−ρ)×平均処理時間

  M/M/1モデルの平均待ち時間Twは、利用率をρ、平均サービス時間をTsとすると Tw = ρ/(1-ρ) × Ts で表される。ここではTs=T秒なので、Tw≧T となる条件は ρ/(1-ρ) ≧ 1、すなわち ρ ≧ 1-ρ より ρ ≧ 0.5 である。したがって利用率が50%以上になったときに平均待ち時間がT秒以上となる。

  出典：平成30年度 秋期 高度共通_午前I試験 am1 問2（IPA）

• 通信回線を使用したデータ伝送システムにM/M/1の待ち行列モデルを適用すると、平均回線待ち時間、平均伝送時間、回線利用率の関係は、次の式で表すことができる。 平…

  正解：0.5

  要点：待ち時間が伝送時間を超えるのは利用率0.5から

  与式より、平均回線待ち時間が平均伝送時間より長くなる条件は 回線利用率/(1-回線利用率) > 1 である。両辺に(1-回線利用率)を掛けると 回線利用率 > 1-回線利用率 となり、回線利用率 > 0.5 が得られる。したがって0.5を超えたときに初めて待ち時間が伝送時間を上回る。

  出典：令和1年度 秋期 高度共通_午前I試験 am1 問2（IPA）