多数のいいねにもかかわらず、以前の2つの投稿にコメントがなかったため、大多数は何も理解していないという結論に至りました。 長い間トピックに没頭していた私は、読者に不注意を示しただけです。 私のせい、私は修正されます。 アクセスしやすい言語で計画することについて話します。
それでは、スケジューラとは何ですか？ スケジューラは、マルチタスクを実装するOSの一部です。 プロセッサの数は通常、実行されるタスクの数よりもはるかに少ないです。 したがって、各プロセッサにはいくつかのタスクがあります。 その一貫した性質のため、プロセッサはこれらのタスクを同時に実行することはできません-あるタスクから別のタスクに交互に切り替わります。
タスクを切り替える方法により、プランナーは協力的なものと混雑するものに分けられます。 協調計画では、タスクの切り替えはタスク自体の責任です。 つまり 次のものに道を譲ることが可能な場合、問題自体は解決します。 協力的なプランナーとは異なり、混雑したプランナーは、変化するタスクについて独自の決定を下します。 2番目の計画方法は、その予測可能性と信頼性のために、一般的にOSにとってより好ましいことを理解するのは簡単です。
以降のタスクはフローと呼ばれます。 最初は、タスクはシングルスレッドであり、実行のフローは常にタスクに対応していました。 現在、これは事実ではないため、タスクは論理的に2つの関連する概念に分割されました。リソースコンテナとしてのプロセスと、コード実行の独立したシーケンスとしてのスレッドです。
プリエンプティブスケジューラのスレッドスイッチングは、タイマー割り込みによってトリガーされます。 指定された期間ごとに、コードの実行が一時停止され、制御が割り込みハンドラーに転送されます。 このハンドラーは、次の期間まで現在のスレッドで作業を続けるか、別のスレッドに制御を移すかを決定します。
優先度に応じて、ストリームには一定の量の時間が割り当てられます。 たとえば、タイマーがミリ秒ごとに割り込みを生成するとします。 その後、クォンタム50が割り当てられたフローは、優先度の高いフローに置き換えられない場合、50ミリ秒間機能します。
ハンドラーはどのようにスレッドを切り替えますか？ 最初の投稿では、割り込み中に、プロセッサがスタック上で実行されるタスクのいくつかのレジスタを書き込むことを書きました。 さらに、残りのレジスタはスタックにさらにプッシュされました。 すべてのレジスタは、現在の状態を記述するストリームのいわゆるコンテキストを形成します。 タスクを切り替えるには、まず現在のコンテキストを保存し（将来復元できるように）、代わりに別のスレッドの以前に保存したコンテキストを記録する必要があります。
おもちゃでは、これは次のように行われます。
DEFINE_ISR(timer, 0) { ... thrd->context = *stack_frame; // thread_data update_priority_quantum(thrd); // ... prio = &cpud->priorities[cpud->current_priority = highest]; // struct thread_data *thrd2 = prio->active_tail; // if (thrd2 != thrd) { // - *stack_frame = thrd2->context; // wrmsr(MSR_FS_BASE, (uint64_t)thrd2); } ... }
マルチプロセッサスケジューラ（ SMP ）に進む前に、論理プロセッサの概念を定義する必要があります。 論理プロセッサとは、一連の命令を独立して実行するエンティティを意味します。 つまり 論理プロセッサは、古いシングルコアチップまたはマルチコアプロセッサのコア（またはマルチスレッドが存在するカーネルスレッド）のいずれかです。
SMPスケジューラコードは各論理プロセッサで実行されることを理解することが重要です。 つまり それらのそれぞれで、タイマー割り込みが生成され、フローのコンテキストが切り替えられます。 そのため、スレッドは既存の論理プロセッサ間で分散されます（それらの負荷の分散は別の重要なタスクです）。 最新のx86システムでは、古いプログラマブルタイマーとともに、いわゆるローカルAPICタイマーがサポートされています。 主な利点は、各論理プロセッサに独自の独立したローカルAPICタイマーがあることです。 したがって、計画に使用すると便利なのはこれらのタイマーです。 玩具でAPICタイマーを使用するためのコードは、 こちらにあります 。
各論理プロセッサが独自のスレッドをスケジュールするため、同期の必要がないという誤った印象があるかもしれません。 実際、スレッドは1つのプロセッサに厳密に接続されていませんが、移行できます（負荷を分散するときと、明示的に別のスレッドの主導で）。 たとえば、おもちゃでは、1つのスレッドが2番目のスレッドを一時停止し、別のプロセッサで実行できます。 したがって、共有データを保護する必要があります。
スケジューラーを作成する場合、ミューテックス、セマフォ、条件変数など、アプリケーションプログラマーに馴染みのある同期プリミティブは使用できません。 そのようなプリミティブは、要求されたリソースが利用できない間、フローのブロック（スリープ）を想定しています。 しかし、ブロックする人はいないので、積極的な待機が助けになります。 つまり プロセッサはリソースの状態を連続的にポーリングし、リリース時に排他的にキャプチャします。 アクティブアイドル待機はプロセッサをロードするため、リソースを保持する時間はできるだけ短くする必要があります。
アクティブな待機に基づく主な同期プリミティブはspinlockです。 現代のシステムでは、スピンロックはアトミック命令に基づいています。 x86の場合、これらはxchg、lock cmpxchgなどです。 このような命令の主なタスクは、メモリセルをアトミックに読み取り、変更することです。 おもちゃにスピンロックの基本的なキャプチャとリリースを実装する：
struct spinlock { volatile uint8_t busy; }; static inline void create_spinlock(struct spinlock *lock) { lock->busy = false; } // zero tries means (practically) forever static inline bool acquire_spinlock_int(struct spinlock *lock, uint64_t tries) { uint8_t al; do ASMV("mov $1, %%al\nxchgb %%al, %0" : "+m"(lock->busy), "=&a"(al)); while (al && --tries); return !al; } static inline void release_spinlock_int(struct spinlock *lock) { ASMV("xorb %%al, %%al\nxchgb %%al, %0" : "+m"(lock->busy) : : "al"); }
今日は以上です。