基本情報 平成30年度 秋期 問18｜テクノロジ系に関する問題

答えは a「各タスクに、均等にCPU時間を割り当てる」 です。

ラウンドロビン＝「順番に少しずつ」スケジューリング方式。

複数のタスクをぐるぐる順番に、それぞれに決まった時間（タイムスライス）ずつCPUを使わせて切り替える方法です。「お客様が並んでて、1人○分ずつ順番で対応する」イメージ。

👉 覚え方：ラウンドロビン＝順番に均等！

ほかの選択肢：b ターンアラウンドタイム比例＝そんな方式ない／c イベント発生時にリアルタイム＝イベント駆動／d 優先度順＝プライオリティスケジューリング。

なぜこれが正解か

正解は a。ラウンドロビン（Round Robin）方式は、各タスクに固定のタイムスライス（タイムクォンタム）を順番に割り当てるスケジューリング方式。CPU時間を全タスクに均等に分配することで、応答性と公平性を両立する。タイムスライス終了時点でタスクを実行可能列の末尾に戻し、次のタスクを実行する。

各選択肢の解説

• a 均等にCPU時間配分：ラウンドロビン → 正解。
• b ターンアラウンドタイム比例配分：そのような名前のスケジューリング方式は存在しない（ひっかけ）。
• c イベント発生に応じてリアルタイム実行：イベント駆動方式または割込み駆動方式。
• d 優先度順実行：優先度スケジューリング（プライオリティスケジューリング）。

覚え方・ひっかけ注意

主要スケジューリング方式：

• FCFS（First Come First Served）：到着順。
• SJF（Shortest Job First）：短いジョブ優先。
• ラウンドロビン：時分割で均等配分。
• 優先度スケジューリング：優先度順。
• 多重キュー：優先度別キューを組み合わせ。
• 多重フィードバックキュー：UNIX/Linuxの伝統的方式。

ラウンドロビンはタイムスライスが短すぎるとオーバーヘッド増、長すぎると応答性低下のトレードオフがある。

主要スケジューリングアルゴリズムの比較

タイムスライスのトレードオフ

• 短すぎる：コンテキストスイッチ頻発でオーバーヘッド大（数百μs〜数ms）。
• 長すぎる：応答性低下、対話タスクに不利。
• 典型値：Linux CFSは数ms〜数十ms、Windowsは10〜15ms、リアルタイムOSは1ms以下。

現代OSのスケジューラ

• Linux CFS（Completely Fair Scheduler、2007〜）：仮想実行時間（vruntime）で公平性を実現。赤黒木でO(log n)。
• Linux EEVDF（2023〜）：CFSの後継、より細かい優先度制御。
• Windows：32レベルの優先度クラス＋ラウンドロビン。クォンタム単位で実行。
• macOS / iOS：QoS（Quality of Service）クラス（UserInteractive, UserInitiated, Utility, Background）でグルーピング。
• RTOS（FreeRTOS、VxWorks、μITRON）：優先度ベース＋プリエンプティブが主流。

飢餓（starvation）の問題と対策

• エイジング（aging）：待ち時間が長いタスクの優先度を上げる手法。
• 多重フィードバックキュー：使用CPU時間が長いタスクを低優先度キューへ。
• デッドロック検出：循環待ち防止。

試験での位置づけ

FE「OS／スケジューリング」分野で毎期出題の頻出領域。各方式の特徴判別、ガントチャート問題、平均待ち時間・ターンアラウンドタイム計算は確実な得点源。応用情報・エンベデッドではEDF（Earliest Deadline First）、Rate Monotonicスケジューリング、優先度逆転問題（priority inversion）、優先度継承プロトコル等のリアルタイム理論まで踏み込む。

並列・分散の発展

• マルチコアスケジューリング：ロードバランシング、キャッシュアフィニティ、Bigger.LITTLE（heterogeneous）。
• 仮想化スケジューリング：vCPUとpCPUのマッピング、CPUオーバーコミット。
• コンテナ・cgroup：CPUシェア、CFSクォータでリソース制限。
• クラウドスケジューリング：Kubernetes Scheduler、HPA（Horizontal Pod Autoscaler）。

選択肢の発展補足

dの優先度スケジューリングはプリエンプティブ／非プリエンプティブの2種類。リアルタイム系ではRM（Rate Monotonic）、DM（Deadline Monotonic）、EDF（Earliest Deadline First）等の理論的アルゴリズムが存在し、デッドライン保証の限界条件（Liu & Laylandの定理）も古典理論として頻出。