キューとは

きゅー

最初に入れた要素を最初に取り出す、先入れ先出し(FIFO)のデータ構造。末尾に入れる操作をエンキュー、先頭から取り出す操作をデキューという。処理待ちの行列、タスク間のデータの受け渡し、幅優先探索などに使われる。

「キュー」は、6分野の10問の練習問題に出てきます(データ構造とアルゴリズム, 組込み・ファームウェア, マルチコアと同期など)。

この用語の分野: データ構造とアルゴリズム

キューの練習問題に挑戦

条件変数で「キューが空でなくなるまで待つ」とき、待ちから起きた後に条件をif文ではなくwhile文で確かめ直す理由として正しいものはどれか。

  1. Awhile文の方がif文より実行が速いから
  2. Bif文では条件変数を使えない決まりだから
  3. C起こされても、ほかのスレッドが先に取ってしまったり、理由なく起きたりして、条件が満たされていない可能性があるから
答えと解説を見る

正解:C. 起こされても、ほかのスレッドが先に取ってしまったり、理由なく起きたりして、条件が満たされていない可能性があるから

条件変数の待ちは、ロックを手放して眠り、知らせを受けて起きるとロックを取り直して戻ります。しかし起きるまでの間に、ほかのスレッドが先にロックを取ってキューの要素を持っていくことがあります。また、実装の都合で知らせがなくても起きること(見かけ上の起床)が認められています。そのため、起きた後に条件を確かめ、満たされていなければもう一度待つwhile文で書きます。

RTOSで、センサを読むタスクから表示するタスクへデータを渡すのに、キュー(メッセージキュー)を使う利点として正しいものはどれか。

  1. Aデータがキューを通ると、自動で暗号化される
  2. B受け取る側はデータが来るまで眠って待て、送る側と受け取る側の速さの違いもキューにためて吸収できる
  3. Cキューを使うと、タスクの優先度が不要になる
答えと解説を見る

正解:B. 受け取る側はデータが来るまで眠って待て、送る側と受け取る側の速さの違いもキューにためて吸収できる

共有の変数とフラグでデータを渡すと、データ競合を防ぐ工夫や、受け取る側が何度も調べに行く手間が必要です。RTOSのキューを使えば、送る側はデータを入れるだけ、受け取る側はデータが来るまで待ち状態でCPUを使わずに待てます。キューの中に複数のデータをためられるので、一時的に送る側が速くてもデータを失いません。

解説の中の「キュー」

「キュー」が出てくる問題(10問)

  1. 条件変数で「キューが空でなくなるまで待つ」とき、待ちから起きた後に条件をif文ではなくwhile文で確かめ直す理由として正しいものはどれか。
  2. RTOSで、センサを読むタスクから表示するタスクへデータを渡すのに、キュー(メッセージキュー)を使う利点として正しいものはどれか。
  3. 空のキューに A、B、C の順に要素を入れ、1つ取り出し、D を入れて1つ取り出し、E を入れて1つ取り出した。取り出された要素を順に並べたものはどれか。
  4. 要素数4の文字列型の配列 q を環状に使うキューがある。head と tail の初期値は1で、enq(v) は q[tail] ← v の後に tail ← tail mod 4 + 1 を行い、deq() は q[head] の値を返した後に head ← head mod 4 + 1 を行う。次のプログラムを実行したとき、「E」が格納される q の要素はどれか。
  5. 高速なSSDとホストの接続に広く使われている、PCI Expressを利用したインターフェース規格はどれか。
  6. 準仮想化(パラバーチャライゼーション)の説明として正しいものはどれか。
  7. 組込み機器でRTOS(リアルタイムOS)を使う主な目的はどれか。
  8. 空のスタックに対して、push 1、push 2、pop、push 3、push 4、pop、pop の順に操作した。pop で取り出された値を順に並べたものはどれか。
  9. 親の値が子の値以上になる最大ヒープを、根を a[0] とする配列で表している。ヒープ 50, 30, 40, 10, 20, 35 に45を追加する。末尾に置いてから、親より大きい間は親と交換する操作を行った後の配列はどれか。
  10. 辺に重みのないグラフで、出発点から各頂点までの最短の辺の数を求めたい。適した探索の方法と、そのとき使うデータ構造の組はどれか。

データ構造とアルゴリズムの参考書を探す PR

Amazonの検索結果へのリンクです。Amazonのアソシエイトとして、半導体教室は適格販売により収入を得ています。

関連する用語

スタック RTOS(リアルタイムOS) 幅優先探索 配列 条件変数 変数 データ競合 剰余演算 SSD PCI Express

用語集の一覧へ