4

リアルタイム タスクの最適なスケジューリング戦略について何人かの同僚と興味深い議論をしましたが、誰もが一般的または有用なスケジューリング戦略をよく理解しているわけではありませんでした。

回答については、複数の戦略について少し情報を提供するのではなく、1 つの戦略を選択して詳細に説明してください。他の人の説明に追加するものがあり、それが短い場合は、新しい回答ではなくコメントを追加してください (それが長い、または役立つ、または単にはるかに優れた説明である場合は、回答を使用してください)

  • 戦略とは何か - 一般的なケースを説明します (タスク キューとは何か、セマフォ、ロック、およびスケジューラ自体の外部にあるその他の OS の基礎を人々が知っていると仮定します)
  • この戦略は何のために最適化されていますか (タスクの待ち時間、効率、リアルタイム、ジッター、リソース共有など)
  • リアルタイムですか、それともリアルタイムにできますか

現在の戦略:

-アダム

4

2 に答える 2

8

Real-Time Task Scheduling for Energy-Aware Embedded Systemsというタイトルの論文で説明されているように、Swaminathan と Chakrabarty は、複数のプロセッサ速度と消費電力プロファイルが利用可能な低電力 (組み込み) デバイスでのリアルタイム タスク スケジューリングの課題について説明しています。彼らが概説しているスケジューリング アルゴリズム (テストでは最適なソリューションよりも約 1% 悪いだけであることが示されています) には、LEDF ヒューリスティックと呼ばれるタスクをスケジューリングする興味深い方法があります。

紙から：

低エネルギー最早デッドライン ファースト ヒューリスティック、または単に LEDF は、よく知られている最早デッドライン ファースト (EDF) アルゴリズムの拡張です。LEDF の操作は次のとおりです。LEDF は、「レディ リスト」と呼ばれる、リリースされたすべてのタスクのリストを維持します。タスクがリリースされると、締め切りが最も近いタスクが選択されて実行されます。より低い電圧（速度）でタスクを実行することで、タスクのデッドラインに間に合うかどうかをチェックします。期限に間に合う場合、LEDF はより低い電圧をタスクに割り当て、タスクの実行を開始します。タスクの実行中に、他のタスクがシステムに入る場合があります。これらのタスクは、「実行可能リスト」に自動的に配置されると想定されます。LEDF は、実行する期限が最も近いタスクを再度選択します。実行待ちのタスクがある限り、LEDF はプロセッサをアイドル状態に保ちません。このプロセスは、すべてのタスクがスケジュールされるまで繰り返されます。

そして疑似コードで：

Repeat forever {
    if tasks are waiting to be scheduled {
        Sort deadlines in ascending order
        Schedule task with earliest deadline
        Check if deadline can be met at lower speed (voltage)
        If deadline can be met,
            schedule task to execute at lower voltage (speed)
        If deadline cannot be met,
            check if deadline can be met at higher speed (voltage)
        If deadline can be met,
            schedule task to execute at higher voltage (speed)
        If deadline cannot be met,
            task cannot be scheduled: run the exception handler!
    }
}

リアルタイム スケジューリングは、小型で低電力のデバイスが普及するにつれて、興味深い進化する問題のようです。これは、今後も多くの研究が行われる分野であると思います。

于 2008-09-08T16:09:55.887 に答える
2

一般的なリアルタイム スケジューリング スキームの 1 つは、優先度ベースのプリエンプティブ マルチタスキングを使用することです。
各タスクには、異なる優先度レベルが割り当てられます。
レディ キューで最も優先度の高いタスクが実行されます。CPU を放棄する (つまり、遅延、セマフォの待機など) か、より優先度の高いタスクの実行準備が整うまで実行されます。

このスキームの利点は、システム設計者が、どのタスクをどの優先度で実行するかを完全に制御できることです。スケジューリング アルゴリズムも単純で、決定論的である必要があります。

一方、優先度の低いタスクは、CPU が不足する可能性があります。これは、設計上の問題を示しています。

于 2008-09-16T17:37:45.157 に答える