厳しい読者への直接リクエスト。 使用されている用語のいずれかを理解していない場合は、尋ねてください、私は念頭に置いていたものを教えてくれます。 また、この用語の別のスペルまたは翻訳が必要な場合は、コメントでそれを示してください。 好きなものを適用します。
そのため、以前の記事では、スケジューラを除いたマルチタスク実装のメカニズムについて説明しました。彼はスケジューラーで
すでに述べたように、シェドラーは、質問に答える関数です。つまり、どのスレッドで、どのくらいの時間をプロセッサにかけるかです。
ちなみに、SMPシステムでは、シェダーはシングルプロセッサのものと変わりません。 一般に、1つまたは複数のプロセッサ上のエンティティの相互作用の構造を理解しやすくするために、次のモデルを想像するのが最も簡単です。各プロセッサには、「アイドル」スレッドがあります。 »プロセッサ（所有していると思われる）が他のスレッドで、シェダーを使用してスレッドを選択します。
シェドラーについて言えば、優先順位について語るしかありません。
優先度-このスレッドとプロセッサの他のスレッドとの競合に影響するスレッド（またはプロセス）のプロパティ。
優先度は通常、ペア<優先度クラス、クラス内の優先度値>で記述されます。
今日、優先順位の実装のためのかなり明確なスキームが形成されました。 スレッドの優先度は3つのクラスに分けられます。
- リアルタイム：このクラスのスレッドは、常に他のクラスのスレッドを可能な限り迅速にプロセッサから追い出し、 リアルタイム優先度の高いスレッドが存在する場合を除き、プロセッサから削除されることはありません。 つまり、そのようなスレッド自体は、プロセッサが不要になった時点を判断する必要があります。
- タイムシェアリング：このクラスのスレッドは常にプロセッサからアイドルスレッドをプッシュし、タイムシェアリングスレッドは互いにソフト競合します。 異なる優先度値を持つこのクラスの2つのスレッドは、プロセッサ時間の異なる割合を受け取りますが、優先度値が最大限に異なっていても、確実に受け取ります。
- アイドルクラス：このクラスのスレッドは、「変更」のために他のクラスを実行する準備ができているスレッドがない場合にのみプロセッサを受け取ります。 個人的には、アイドルクラス内の優先順位の値にはポイントがありません。 これも起こりますが。
ところで。 彼らは、カーニガンがかつてUnixを書くとしたらどうするかを尋ねられたと言っています。 「クリエイトをクリエイトと書く」とマスターは答えました。 niceから始めて、修正リストに不条理の袋を追加します-何らかの理由で、Unixの優先順位の概念は不安定です。 ナイスが小さいほど、優先度が高くなります。
この記事では、より人道的なスケール、つまり数値が大きいほどプロセッサを増やします。
おそらく誰かがすでにコードを調べたいと思っています。 ここにあります：
ファントモフスキーのシェドラーのソーステキスト 。
ここで、プーシキンを少しプレイします:)
そして今、霜が割れています
そして、フィールドの中で銀...
（読者はすでにバラの韻を待っています。
すぐに彼女を連れて行ってください！）
そして、フィールドの中で銀...
（読者はすでにバラの韻を待っています。
すぐに彼女を連れて行ってください！）
プーシキンといえば。 私は、プランナーを書く分野で神聖な知識を断固として主張しません。 上記の例は、非常に合理的な実装ですが、ホームスパンであり平凡なものです。 それにもかかわらず、優れたシェダーを書くことは非常に深刻な科学的課題であり、これについての論文が書かれています。リアルタイムになると、すべてが非常に深刻になります。 この記事では、基本のみを説明します。 私たちの国では、謙虚な召使いよりも3桁以上このトピックについて知っている専門家がいます。
シムの場合-続行します。
シェダラーのかなり伝統的な実装は、いわゆる実行キューの存在を意味します-実行の準備ができたスレッドのキュー。 実際、これは必ずしもキューではありません。キューの場合、通常は異なるクラスに属するキューが多く、場合によっては優先度レベルがあります。
特にPhantomでは、クラスに応じて3行になります。
/** Idle prio threads */ static queue_head_t runq_idle = {0,0}; /** Normal prio threads */ static queue_head_t runq_norm = {0,0}; /** Realtime prio threads */ static queue_head_t runq_rt = {0,0};
一般に、プロセッサに関連するスレッドは次の3つの状態になります。
- ブロックされました。 プロセッサにないため、プロセッサにインストールできません。 実行キューにありません。
- 実行されました。 実行キューにありません。
- 実行できます。 実行キューに存在します。
つまり、実行キューには、プロセッサに到達したいスレッドがあります。
したがって、スケジューラの作業は次のように要約されます。
- どの優先度クラスのどのスレッドを今すぐ起動するかを決定します。 簡単です-リアルタイムキューが空かどうかを確認する-空でない場合、リアルタイムスレッドを開始し、通常の優先度キューを確認します-空でない場合、通常のスレッドを開始します。 それ以外の場合は、アイドルスレッドを実行します。 存在しない場合、プロセッサがアイドル状態であり、「永遠の」スリープのスレッドに入ることに注意してください。
- 優先度を決定する場合、この優先度で実行する正しいスレッドを選択します。
- スレッドに実行の時間間隔を割り当てます。
一般に、実装は非常に一般的です。 リアルタイムから始めましょう。 単純な実装は、利用可能なスレッドをソートし、数値の最大優先度値でスレッドを開始します。 時間間隔は、リアルタイムの優先順位を持つスレッドがチェックされないため、割り当てられません。
// Have some realtime? if( !queue_empty(&runq_rt) ) { int maxprio = -1; phantom_thread_t *best = 0; phantom_thread_t *it = 0; queue_iterate(&runq_rt, it, phantom_thread_t *, runq_chain) { if( it->thread_flags & THREAD_FLAG_NOSCHEDULE ) continue; if( ((int)it->priority) > maxprio ) { maxprio = it->priority; best = it; } } if( best ) { assert(t_is_runnable(best)); return best; } }
コードの明確な改良点は、シェダー内のすべてのスレッドをソートすることではなく、数値の優先順位の降順でキューにスレッドを挿入することです。 その後、スケジューラはキューから最初のスレッドを削除して開始するだけです。
これで、タイムシェアリングクラスの優先順位を持つスレッド、つまり、プロセッサを優しく競合する通常のスレッド。
ここで、スレッドの状態構造のticks_left変数によって、スレッドがプロセッサ上で保持する10ミリ秒間隔が決定されることに注意してください。
最初に、t_assign_time（）関数が何をするかを考えます。
it->ticks_left = NORM_TICKS + it->priority;
彼女は、すべてのスレッドがticks_leftを使用したことを確認し、使用している場合は、新しいticks_leftを割り当てます-より優先度の高いユーザーには、より多くのプロセッサー時間を与えます。
スケジューラは何をしますか？ 優先度が最も高く、プロセッサ時間の残りがゼロ以外のスレッドを選択して開始します。
// Have normal one? if( !queue_empty(&runq_norm) ) { // If no normal thread has ticks left, reassign // ticks and retry do { unsigned int maxprio = 0; // NB! not a negative number! phantom_thread_t *best = 0; phantom_thread_t *it = 0; queue_iterate(&runq_norm, it, phantom_thread_t *, runq_chain) { if( it->thread_flags & THREAD_FLAG_NOSCHEDULE ) continue; if( (it->priority > maxprio) && (it->ticks_left > 0) ) { maxprio = it->priority; best = it; } } if( best ) { return best; } } while(t_assign_time()); }
すべてのスレッドのすべての残基がなくなったとき-スレッドに新しい残基を割り当てるようt_assign_time（）に要求します。
実際、ここではソートは比較的冗長です。 キューの最後にスレッドを追加し、最初から選択するだけで十分です。 一般に、すべてのスレッドを並べ替えるのは明らかに悪いので、これを行わないでください。 また、この記事をより最適な方法で書き直します。たとえば、既に上で説明したように、リアルタイムで。
ところで、スケジューラーコードを読むとき、スレッドは常にタイムスライスを「食い尽くす」わけではないことを考慮に入れなければなりません-スレッドは同期プリミティブでブロックされ、それ自体の自由意志ではない時間の一部になります。 これがソートの理由です。スレッドの優先度が高い場合、ロック解除後のスレッドは、他のすべてのスレッドが終了する前にプロセッサに戻ります。
では、アイドルプライオリティクラスに移りましょう。 以前のクラスですべてのスレッドがスリープ状態または欠落している場合にのみ、ここに到達します。
// Have idle one? ret = (phantom_thread_t *)queue_first(&runq_idle); if( ret ) { if( ret->thread_flags & THREAD_FLAG_NOSCHEDULE ) goto idle_retry; // Just take first. Switched off thread will become // last on runq, so all idle threads will run in cycle ret->ticks_left = NORM_TICKS; return ret; } else goto idle_no;
ここではすべてが簡単です-最初に取得したものを取得し、標準時に実行します。 プロセッサから削除されると、runq_idleキューの最後に落ちるため、このようなスレッドはすべて円で起動されます。
最後に、何も見つからなかった場合、この場合に特別なアイドルスレッドがあります。
STAT_INC_CNT(STAT_CNT_THREAD_IDLE); percpu_idle_status[GET_CPU_ID()] = 1; // idle return GET_IDLEST_THREAD(); // No real thread is ready to run
1つのスレッドを2回起動できないため、各プロセッサには独自のプロセッサがあります。 mooのようにシンプル：
while(1) { hal_sti(); hal_wait_for_interrupt(); }
ほとんどすべて。
ここで考慮されていないもの。
対話型スレッドprio boost ：通常、スケジューラーは、コンソールまたは別のエンティティからのI / Oで見られるスレッドの実際の優先順位を上げます。これらは潜在的に、対話ユーザーによって隠されています。 これにより、システムの知覚反応性が向上します。人間の観点からは、「OSは愚かではありません」。 また、その逆-スレッドがタイムスライスを最後まで「使い果たし」、安定して実行する場合、純粋に計算的であるとみなして、優先度をわずかに下げます。 同じ目的で-システムの反応性を高めます。
もちろん、これは通常の優先度クラスを持つスレッドにのみ適用されます。リアルタイムの優先度に触れる人はいません。
プロセッサの保証されたシェアによるリアルタイム計画 。 厳密なリアルタイムシステムには、スレッドまたはスレッドのグループが明確に指定された量のプロセッサ時間を受け取ることができる厳格な計画があります。
優先順位の反転。
最大のリアルタイム優先度を持つ非常に重要なスレッドRと、クラスIdleの優先度を持つスレッドIがあり、無関係なナンセンスを処理するとします。 また、ユーザーと連携する通常のUスレッドも、コンソールからコマンドを読み取ります。 たとえば、シェル。
ユーザーはアイドル状態で、入出力とスレッドUを待っています。
スレッドIはプロセッサを受け取り、その処理を行うことを決定し、このために少しのメモリを割り当てたいと考えています。 カーネルメモリ割り当て関数は、グローバルミューテックスをロックし、割り当てを開始します。 明らかに、アイドル状態のプリオで実行しています。
この時点で、スレッドRがスリープから起動します。これは、原子炉コアの吸収体のコアの位置を修正する時間です。 そして彼女はまたいくらかの記憶を望んでいます。
（UとRが同じマシンで何をするかを選んで尋ねないでください。たとえば、UはTCP経由の統計サーバーになります。）
当然、RはIからプロセッサを取得しますが、メモリの割り当て時にグローバルミューテックスに反して停止します。
その後、作業を続行しますが、ユーザーがコマンドを入力すると、Uが動作し、プロセッサをIから取得します。今、突然、優先度の高いリアルタイムスレッドRがスレッドUの動作完了を待機し、リアクターが地獄に爆発します。
これを防ぐために、彼らは私がPhantomでまだ行っていないこと-優先順位の逆転を行います。
次のように定式化されます：優先度の低いスレッドが占有するリソースで優先度の高いスレッドがロックされている場合、2番目のスレッドはそのようなロックの間、最初のスレッドの優先度を受け取ります。
つまり、この例では、メモリ割り当てのミューテックスをブロックするときのスレッドIは、スレッドRからリアルタイムの優先度を取得し、スレッドUを地獄にプッシュし、スレッドRをブロックするものを終了する必要があります。ミューテックスをロック解除した後、その優先度はアイドルに戻り、プロセッサはRに移動します。
さて、おそらく、それですべてです。 :)