入力キュー

コンピュータ サイエンスでは、入力キューは、プログラムを実行するためにメモリに取り込まれるのを待っているストレージ内のプロセスの集合です。入力キューは主に、プロセス間でリソースを配分する手法であるオペレーティング システム スケジューリングで使用されます。入力キューはオペレーティング システム(OS) に適用されるだけでなく、ネットワーク デバイス内のスケジューリングにも適用できます。スケジューリングの目的は、リソースが公平かつ効率的に配分されるようにすることです。これにより、システムのパフォーマンスが向上します。

基本的に、キューは、データが後部に追加され、前部から削除されるコレクションです。キューにはさまざまな種類があり、動作方法はまったく異なる場合があります。オペレーティング システムでは、先着順キュー、最短残り時間、固定優先度プリエンプティブ スケジューリング、ラウンドロビン スケジューリング、およびマルチレベル キュー スケジューリングが使用されます。ネットワーク デバイスでは、先入先出キュー、重み付け公平キュー、優先度キュー、およびカスタム キューが使用されます。

オペレーティング システムでは、プロセスはメモリにロードされ、中央処理装置(CPU) によって実行される順番を待ちます。CPU スケジューリングはプロセスの状態を管理し、入力キューを使用してプロセスを次にいつ実行するかを決定します。

先入先出法のプロセスは、キューに入れられた順番にキューから取り出されます。この方法では、すべてのプロセスが平等に扱われます。優先度の異なる 2 つのプロセスがあり、優先度の低いプロセスが最初にキューに入った場合、そのプロセスが最初に実行されます。この方法は、異なるプロセスの優先度が異なる場合、特にプロセスが長時間実行される場合には理想的ではない可能性があります。

最短残り時間方式は、開発の処理時間を予測し、最短処理時間から最長処理時間の順にキューに配置します。この方式は、過去の履歴レコードに基づいて推定および予測します。結果的に、パフォーマンスは安定していませんが、先着順方式よりも処理待ち時間が改善されます。

固定優先度プリエンプティブ スケジューリング方式では、処理時間に基づいてプロセスに異なる優先度を割り当て、優先度順にキューに配置します。CPU は優先度の高いプロセスから低いプロセスへと処理し、同じ優先度のプロセスは先着順で処理されます。優先度の高いプロセスがキューに入ると、CPU は優先度の低いプロセスの処理を一時的に停止します。

ラウンドロビン スケジューリング方式では、各プロセスに同じ時間を割り当てて、それらを循環させます。この方法は、各プロセスに多くの時間を費やすことに大きく基づいています。多くの時間が短すぎるとプロセスが断片化され、多くの時間が長すぎると各プロセスの実行待ち時間が長くなります。適切な多くの時間を選択することが、この方法の基礎です。^{[説明が必要]}

マルチレベル キュー スケジューリング方式では、複数のキューが使用され、各キューには独自のスケジューリング アルゴリズムが存在します。マルチレベル キュー スケジューリングは他の方法に比べて複雑ですが、OS が複雑な状況でさまざまな応答時間要件に対応できる柔軟性を提供します。

ネットワークでは、パケットはスケジューリングの重要な基盤です。ネットワーク コアでは毎日さまざまな種類のパケットが行き来しており、それらはまったく異なる方法で処理されます。たとえば、音声パケットとビデオ パケットは通常のパケットよりも優先度が高くなります。パケットを効率的に管理および配布するために、ネットワーク デバイスは入力キューを使用して、どのパケットを最初に送信するかを決定します。

このモードでは、パケットはキューから来た順にキューから取り出されます。すべてのパケットは同じ優先順位で扱われます。大きなパケット A が小さなパケット B より先に来た場合、B は A が完全に処理されるまで待機する必要があります。システムがすべてのパケットを同じように扱うと、ユーザーは音声パケットなどの送信に遅延を感じることがあります。

重み付け公平キューは、パケットを分配するために min-max-fair-share アルゴリズムを使用します。最小公平シェアとは、ネットワーク OS が各パケット タイプに最小限のリソースを均等に分配することを意味します。最大公平シェアとは、ネットワーク OS がその時点で大量のデータを転送する必要があるパケットにより多くのリソースを提供するが、転送後にリソースを取り戻すことを意味します。「重み付け」とは、スケジューラが各パケット タイプに重みを割り当てることを意味します。重みに基づいて、パケットをキューに入れて処理する方法が決定されます。通常、各パケットは、各パケットの IP ヘッダーの IP Precedence フィールドに基づいて重み付けされます。

公平な割り当て = (リソース容量 - すでに割り当てられているリソース) / パケット数

優先キューは、優先順位の異なる 4 つのサブキューに分かれています。各キューのデータは、優先順位の高いキューが空の場合にのみ処理されます。ネットワーク OS が優先順位の低いキューのデータを転送しているときに、空の優先順位の高いキューにデータが入ると、ネットワーク OS は優先順位の低いキューのデータを保持し、優先順位の高いキューのデータを最初に処理します。ネットワーク OS は、優先順位の低いキューが順番を待つ時間を気にしません。常に、優先順位の高いキューから低いキューまでを最初に処理してから次のキューに移動するためです。各キュー内では、パケットは先入先出方式で転送されます。

カスタム キューは 17 個の異なるサブ キューに分かれています。最初のキューであるキュー 0 は、ネットワーク OS がシステム パケットを送信するために予約されており、他の 16 個のキューはユーザー定義のパケット用です。ユーザーはさまざまな重要なパケットを定義し、各キューに割り当てることができます。各キューにはサイズ制限があり、その制限に達するとすべてのパケットがドロップされます。各キューは、各キューで処理されるパケットの量に基づいて処理されます。その制限に達すると、ネットワーク OS は現在のキューのパケットを保持し、そのキューが空になるかパケット制限に達するまで次のキューを処理します。1 つのキューが空の場合、ネットワーク OS はそのキューをスキップして次のキューを処理します。

• メッセージキュー