スレッドスケジューリングアルゴリズム解析
7642 ワード
4.1.1スレッドスケジューリングアルゴリズムの全体的な説明時間分割システムでは、カーネルは各スレッドにCPU時間を割り当て、この時間をタイムスライスと呼び、この時間が過ぎた後、カーネルは別のスレッドをスケジューリングして実行状態にする.これがいわゆるタイムスライス回転法です.
UNIXのスレッドスケジューリングとよく似ているのは、OSKitのスケジューラにも、オペレーティングシステムのスケジューラで最も一般的な1つであるマルチレベルフィードバックサイクルスケジューリングと呼ばれるアルゴリズムが採用されていることです.その核心思想は、カーネルがスレッドにタイムスライスを分け、そのスレッドをいくつかの優先順位キューのいずれかにフィードバックすることである.1つのスレッドが終了する前に、複数回のフィードバックループを通過する必要がある場合があります.カーネルがコンテキストの切り替えとリカバリを行う場合、スケジューラはスレッドが元の保留中の場所から実行されることを保証しなければならない.そうしないと、このようなスケジューラアルゴリズムは採用できない.
したがって,スレッドのコンテキスト切り替えとリカバリを再確認する必要があると考えられる.まず、スレッドのコンテキストとは、ユーザアドレス空間のコンテンツ、ハードウェアレジスタのコンテンツ、およびそのスレッドに関連するカーネルデータ構造からなる.より厳密には、スレッドのコンテキストは、そのユーザレベルコンテキスト、レジスタコンテキスト、およびシステムレベルコンテキストから構成される.
4.1.2優先度逆転法OSKitでは、オペレーティングシステム設計において優れた優先度逆転アルゴリズムが採用されている.すなわち、優先度の低いスレッドがmutexを占有すると同時に、別の優先度の高いスレッドがmutexを申請し、優先度の高いスレッドが彼より低いスレッドにブロックされる.
このとき,優先度逆転アルゴリズムを導入し,すなわち,上記のような状況が発生すると,スレッドスケジューラは優先度の低いスレッドの優先度をより高い優先度のスレッドと同様に向上させ,mutexを占有するスレッドを迅速に実行することができる.
現在スケジューリングが必要なスレッドが2つ以上ある場合、このアルゴリズムは再帰を許可する.すなわち、その優先度の低いスレッドの実行には別のmutexが必要であり、このmutexは別の優先度の低いスレッドに占有されるため、スケジューリングプログラムは優先度の低いスレッドの優先度を順次向上させる.これが再帰向上である.
しかし、再帰的な優先度の向上をサポートすると、デッドロックが発生する可能性があります.そのため、デッドロックを検証するプログラムを導入する必要があります.これにより、オペレーティングシステムのコアのサイズとシステムのオーバーヘッドが大幅に増加しますが、オペレーティングシステムがより完備し、リアルタイムスレッドを処理することができます.
pthread/pthread_scheduler.cこのソースファイルには完全なスレッドスケジューリングメカニズムが含まれており、OSKitのすべてのスレッドスケジューリングアルゴリズムはこのファイルに集中しており、以下の関数分析を読むことで、OSKitがどのような関数でスレッドスケジューリングを具体的に実現しているのかを読者に理解させ、前に述べた概念をより深く理解させることができる.
4.2.1待機スケジューリングのスレッドキューの説明を空にする:この関数の役割を概念的に理解させるために、スレッド待機キューとは何かを先に説明する必要があると思う.スケジューラはオペレーティングシステムにおいても1つのスレッドとして現れるため、同じ時間に1つのスレッドしかスケジューリングできないため、多くのスレッドがスケジューリングを待っているがスケジューリングを受け入れられない場合があり、OSKitが提供するこの関数はこの欠陥を補っており、彼はすべてのスケジューリングを待っているスレッドをチェーンテーブルの形式でリンクしている.これがいわゆるスケジューリング待ちスレッドキューです.明らかに、空にすることは実際にチェーンテーブルを解放するポインタです.
4.2.2待ち行列の中で最も優先度の高いスレッドの優先度の説明を得る:スケジューリングスレッドが手元の仕事を完成して、次のスレッドをスケジューリングする時、1つの問題に直面して、いったいどのスケジューリング待ちスレッドをスケジューリングすべきか?OSKitが提供するこの関数は、スレッドスケジューリングをスケジュールするために、待機キューで最も優先度の高いスレッドを返すことができます.
4.2.3次の実行スレッドを指すポインタの説明を得た:あるスレッドが実行状態に移行する時、スケジューラはこのスレッドがどこに保留されているか分からない.OSKitが提供したこの関数を呼び出すことで、実行スレッドを指すポインタを見つけることができる.
4.2.4スレッドの実行キューのキューの最後に、優先度が最も低いスレッド、または他の理由で最後に実行するスレッドをスレッド実行キューの最後に追加するスレッドの説明を追加する.
4.2.5スレッドの実行キューのキューに、最も優先度の高いスレッドまたは何らかの理由で実行するスレッドをスレッド実行キューの一番前に追加するスレッドの説明を追加する.
4.2.6待機キューの中で最も優先度の高いスレッドをキュー実行説明を提出する:オペレーティングシステムがスレッド実行キューの中で待機スレッドを実行する時、当然最初から始めるべきで、私達はこの関数を調整してスレッドの実行に対する機能を実現する.
4.2.7待機キューから独占リソースを削除するスレッドの説明:オペレーティングシステムが全体的に最適化された前提で実行できるように、OSKitはあるスレッドが長い間システムリソースを独占することを許さないことを規定している.もしこのような時間を発見したら、この関数を呼び出して、独占リソースのスレッドを実行キューから削除して、スレッドスケジューリングの公平と合理を維持することができる.
4.2.8この時使用したスケジューリングアルゴリズムの説明:前の章で、スレッドのスケジューリングアルゴリズムはその属性のように初期化の時に与えられたが、それは変更可能であり、OSKitは次の関数を呼び出すことによってスレッド作成後にスケジューリングアルゴリズムを変更することを実現した.
4.2.9一つのスレッドを実行状態に変更する説明:周知のように、スレッドはシステムの中で一般的に三つの状態があり、OSKitはこの関数を呼び出すことによってスレッドの実行状態への移行機能を実現する.
4.2.10スレッドの現在のスケジューリングアルゴリズムを終了する説明:これはまたスレッドの作成後にそのスケジューリングアルゴリズムを変更する関数呼び出しであり、その機能はスレッドの現在のスケジューリングアルゴリズムを中止することである.
4.2.11新しいスレッドのためにスケジューリングパラメータを作成する説明:スケジューリングパラメータとは、スケジューラがスレッドを実行するかどうかを決定する根拠である.例えば,あるユーザ状態スレッドが最近CPUを用いた時間の統計などである.
4.2.12スレッドのスケジューリング状態の変更説明:スケジューリングパラメータがスケジューリング条件に合致する場合、スケジューラはOSKitを呼び出してこの関数を提供することによって、このスレッドのスケジューリング状態を変更し、それを準備スケジューリング状態に変える.スレッドがロックされ、割り込みがオフになります.
4.2.13優先度移行説明:これは私が上述した優先度逆転法の具体的な実現であり、OSKitはそれを呼び出すことによってスレッド優先度の動的変更を完成する.
注意:これは一時的なもので、リアルタイムスレッドにのみ適用されます.
4.2.14何らかの原因に基づいて、スレッドが待機キューに戻される説明:スレッドがオペレーティングシステムで実行された場合、ユーザーの原因でスレッドが実行されたタイムスライス後に実行キューに戻った場合、位置が変わった可能性がある.下は私がOSKitに提供したいくつかの変更原因に対する注釈です.
4.2.15優先度が最も高い待機中のスレッドを返す説明:スケジューラが待機中のスレッドを実行キューに入れる場合、優先度が最も高い待機スレッドを返す関数が必要で、次の関数はちょうどこの任務を完成した.
4.2.16スレッドの優先度を変更する説明:実質的にスレッドをキューから削除し、優先度を再付与し、キューの最後に挿入する.
4.2.17優先順位継承説明:優先順位継承とは、その理論の本質はすべての待機状態からのスレッドであり、待機中、その優先順位は時間の経過とともに徐々に向上する.
4.2.18優先度の説明を継承しない:これは実際には前の優先度の継承とは正反対で、どれだけ長く待ってもスレッドの優先度は変わらない.
4.2.19優先度の減少説明:1つのスレッドが常に実行状態にある場合、OSKitは全体の最適化を考慮して、この関数を呼び出して優先度を徐々に減少させ、それによってより多くのスレッドが実行される可能性がある.
小結本章では,スレッドスケジューリングの一般性から具体的な実現に至るまで,OSKitのスレッドスケジューリングメカニズムを系統的に述べた.
第1節では主に一般的なスレッドスケジューリング概念の記述であり,OSKitにおける最もすばらしい優先度逆転法の理論について詳細に論じた.第2節では、ソースコードのpthreads/pthread_scheduler.cを例として,スケジューリング待ちのスレッドキュー,スレッドの実行キューから優先順位継承,優先度減少など,OSKitのスレッドスケジューリングメカニズムを完全に解明した.
<!-- google_ad_client = "pub-0246923946865164";/* 728x90, created 10/10/09 */google_ad_slot = "1248078023"; google_ad_width = 728; google_ad_height = 90;//-->
UNIXのスレッドスケジューリングとよく似ているのは、OSKitのスケジューラにも、オペレーティングシステムのスケジューラで最も一般的な1つであるマルチレベルフィードバックサイクルスケジューリングと呼ばれるアルゴリズムが採用されていることです.その核心思想は、カーネルがスレッドにタイムスライスを分け、そのスレッドをいくつかの優先順位キューのいずれかにフィードバックすることである.1つのスレッドが終了する前に、複数回のフィードバックループを通過する必要がある場合があります.カーネルがコンテキストの切り替えとリカバリを行う場合、スケジューラはスレッドが元の保留中の場所から実行されることを保証しなければならない.そうしないと、このようなスケジューラアルゴリズムは採用できない.
したがって,スレッドのコンテキスト切り替えとリカバリを再確認する必要があると考えられる.まず、スレッドのコンテキストとは、ユーザアドレス空間のコンテンツ、ハードウェアレジスタのコンテンツ、およびそのスレッドに関連するカーネルデータ構造からなる.より厳密には、スレッドのコンテキストは、そのユーザレベルコンテキスト、レジスタコンテキスト、およびシステムレベルコンテキストから構成される.
4.1.2優先度逆転法OSKitでは、オペレーティングシステム設計において優れた優先度逆転アルゴリズムが採用されている.すなわち、優先度の低いスレッドがmutexを占有すると同時に、別の優先度の高いスレッドがmutexを申請し、優先度の高いスレッドが彼より低いスレッドにブロックされる.
このとき,優先度逆転アルゴリズムを導入し,すなわち,上記のような状況が発生すると,スレッドスケジューラは優先度の低いスレッドの優先度をより高い優先度のスレッドと同様に向上させ,mutexを占有するスレッドを迅速に実行することができる.
現在スケジューリングが必要なスレッドが2つ以上ある場合、このアルゴリズムは再帰を許可する.すなわち、その優先度の低いスレッドの実行には別のmutexが必要であり、このmutexは別の優先度の低いスレッドに占有されるため、スケジューリングプログラムは優先度の低いスレッドの優先度を順次向上させる.これが再帰向上である.
しかし、再帰的な優先度の向上をサポートすると、デッドロックが発生する可能性があります.そのため、デッドロックを検証するプログラムを導入する必要があります.これにより、オペレーティングシステムのコアのサイズとシステムのオーバーヘッドが大幅に増加しますが、オペレーティングシステムがより完備し、リアルタイムスレッドを処理することができます.
pthread/pthread_scheduler.cこのソースファイルには完全なスレッドスケジューリングメカニズムが含まれており、OSKitのすべてのスレッドスケジューリングアルゴリズムはこのファイルに集中しており、以下の関数分析を読むことで、OSKitがどのような関数でスレッドスケジューリングを具体的に実現しているのかを読者に理解させ、前に述べた概念をより深く理解させることができる.
4.2.1待機スケジューリングのスレッドキューの説明を空にする:この関数の役割を概念的に理解させるために、スレッド待機キューとは何かを先に説明する必要があると思う.スケジューラはオペレーティングシステムにおいても1つのスレッドとして現れるため、同じ時間に1つのスレッドしかスケジューリングできないため、多くのスレッドがスケジューリングを待っているがスケジューリングを受け入れられない場合があり、OSKitが提供するこの関数はこの欠陥を補っており、彼はすべてのスケジューリングを待っているスレッドをチェーンテーブルの形式でリンクしている.これがいわゆるスケジューリング待ちスレッドキューです.明らかに、空にすることは実際にチェーンテーブルを解放するポインタです.
static inline int posix_runq_empty ( void ) 4.2.2待ち行列の中で最も優先度の高いスレッドの優先度の説明を得る:スケジューリングスレッドが手元の仕事を完成して、次のスレッドをスケジューリングする時、1つの問題に直面して、いったいどのスケジューリング待ちスレッドをスケジューリングすべきか?OSKitが提供するこの関数は、スレッドスケジューリングをスケジュールするために、待機キューで最も優先度の高いスレッドを返すことができます.
static inline int posix_runq_maxprio ( void )return PRIORITY_MAX - ( prio - 1 ); 4.2.3次の実行スレッドを指すポインタの説明を得た:あるスレッドが実行状態に移行する時、スケジューラはこのスレッドがどこに保留されているか分からない.OSKitが提供したこの関数を呼び出すことで、実行スレッドを指すポインタを見つけることができる.
static inline int posix_runq_onrunq ( pthread_thread_t *pthread ) 4.2.4スレッドの実行キューのキューの最後に、優先度が最も低いスレッド、または他の理由で最後に実行するスレッドをスレッド実行キューの最後に追加するスレッドの説明を追加する.
static inline void posix_runq_insert_tail ( pthread_thread_t *pthread ) 4.2.5スレッドの実行キューのキューに、最も優先度の高いスレッドまたは何らかの理由で実行するスレッドをスレッド実行キューの一番前に追加するスレッドの説明を追加する.
static inline void posix_runq_insert_head ( pthread_thread_t *pthread ) 4.2.6待機キューの中で最も優先度の高いスレッドをキュー実行説明を提出する:オペレーティングシステムがスレッド実行キューの中で待機スレッドを実行する時、当然最初から始めるべきで、私達はこの関数を調整してスレッドの実行に対する機能を実現する.
static inline pthread_thread_t * posix_runq_dequeue ( void ) 注:次の待機スレッドへのポインタを返します.4.2.7待機キューから独占リソースを削除するスレッドの説明:オペレーティングシステムが全体的に最適化された前提で実行できるように、OSKitはあるスレッドが長い間システムリソースを独占することを許さないことを規定している.もしこのような時間を発見したら、この関数を呼び出して、独占リソースのスレッドを実行キューから削除して、スレッドスケジューリングの公平と合理を維持することができる.
static inline void posix_runq_remove ( pthread_thread_t *pthread ) 4.2.8この時使用したスケジューリングアルゴリズムの説明:前の章で、スレッドのスケジューリングアルゴリズムはその属性のように初期化の時に与えられたが、それは変更可能であり、OSKitは次の関数を呼び出すことによってスレッド作成後にスケジューリングアルゴリズムを変更することを実現した.
int posix_sched_schedules ( int policy )
if ( policy == SCHED_RR || policy == SCHED_FIFO )
return 1;
return 0;4.2.9一つのスレッドを実行状態に変更する説明:周知のように、スレッドはシステムの中で一般的に三つの状態があり、OSKitはこの関数を呼び出すことによってスレッドの実行状態への移行機能を実現する.
int posix_sched_setrunnable ( pthread_thread_t *pthread ) 4.2.10スレッドの現在のスケジューリングアルゴリズムを終了する説明:これはまたスレッドの作成後にそのスケジューリングアルゴリズムを変更する関数呼び出しであり、その機能はスレッドの現在のスケジューリングアルゴリズムを中止することである.
void posix_sched_disassociate ( pthread_thread_t *pthread )
{
if (posix_runq_onrunq(pthread)) {
/* * On the scheduler queue, so its not running. */
posix_runq_remove ( pthread );
}
}4.2.11新しいスレッドのためにスケジューリングパラメータを作成する説明:スケジューリングパラメータとは、スケジューラがスレッドを実行するかどうかを決定する根拠である.例えば,あるユーザ状態スレッドが最近CPUを用いた時間の統計などである.
void posix_sched_init_schedstate ( pthread_thread_t *pthread,const struct
sched_param *param )4.2.12スレッドのスケジューリング状態の変更説明:スケジューリングパラメータがスケジューリング条件に合致する場合、スケジューラはOSKitを呼び出してこの関数を提供することによって、このスレッドのスケジューリング状態を変更し、それを準備スケジューリング状態に変える.スレッドがロックされ、割り込みがオフになります.
int posix_sched_change_state ( pthread_thread_t *pthread , const struct
sched_param *param )4.2.13優先度移行説明:これは私が上述した優先度逆転法の具体的な実現であり、OSKitはそれを呼び出すことによってスレッド優先度の動的変更を完成する.
int posix_sched_priority_bump ( pthread_thread_t *pthread, int newprio ) 注意:これは一時的なもので、リアルタイムスレッドにのみ適用されます.
4.2.14何らかの原因に基づいて、スレッドが待機キューに戻される説明:スレッドがオペレーティングシステムで実行された場合、ユーザーの原因でスレッドが実行されたタイムスライス後に実行キューに戻った場合、位置が変わった可能性がある.下は私がOSKitに提供したいくつかの変更原因に対する注釈です.
int posix_sched_dispatch ( resched_flags_t reason, pthread_thread_t
*pthread )
switch (reason) {
case RESCHED_USERYIELD: posix_runq_insert_tail(pthread);
/* ， */
case RESCHED_YIELD: posix_runq_insert_head(pthread);
/* ， */
case RESCHED_PREEMPT:
/* */
if (pthread->policy == SCHED_RR) {
if (--pthread->ticks == 0) {
posix_runq_insert_tail(pthread);
/* ticks， */
pthread->ticks = SCHED_RR_INTERVAL;
}
else
posix_runq_insert_head(pthread);
/* ， ticks ， */
}
else if (pthread->policy == SCHED_FIFO)
posix_runq_insert_head(pthread);
/* ， */
case RESCHED_INTERNAL: /* */
default:
if (pthread == IDLETHREAD)
/* ， */
panic("posix_sched_dispatch: Idlethread!/n");
}4.2.15優先度が最も高い待機中のスレッドを返す説明:スケジューラが待機中のスレッドを実行キューに入れる場合、優先度が最も高い待機スレッドを返す関数が必要で、次の関数はちょうどこの任務を完成した.
pthread_thread_t * posix_sched_thread_next ( void )
{ if ( posix_runq_empty( ) )
return 0;
return posix_runq_dequeue( );
}4.2.16スレッドの優先度を変更する説明:実質的にスレッドをキューから削除し、優先度を再付与し、キューの最後に挿入する.
OSKIT_INLINE void threads_change_priority (pthread_thread_t *pthread, int newprio) 4.2.17優先順位継承説明:優先順位継承とは、その理論の本質はすべての待機状態からのスレッドであり、待機中、その優先順位は時間の経過とともに徐々に向上する.
void pthread_priority_inherit ( pthread_thread_t *pwaiting_for ) 4.2.18優先度の説明を継承しない:これは実際には前の優先度の継承とは正反対で、どれだけ長く待ってもスレッドの優先度は変わらない.
void pthread_priority_uninherit ( pthread_thread_t *punblocked ) 4.2.19優先度の減少説明:1つのスレッドが常に実行状態にある場合、OSKitは全体の最適化を考慮して、この関数を呼び出して優先度を徐々に減少させ、それによってより多くのスレッドが実行される可能性がある.
void pthread_priority_decreasing_recompute ( pthread_thread_t *pthread) 小結本章では,スレッドスケジューリングの一般性から具体的な実現に至るまで,OSKitのスレッドスケジューリングメカニズムを系統的に述べた.
第1節では主に一般的なスレッドスケジューリング概念の記述であり,OSKitにおける最もすばらしい優先度逆転法の理論について詳細に論じた.第2節では、ソースコードのpthreads/pthread_scheduler.cを例として,スケジューリング待ちのスレッドキュー,スレッドの実行キューから優先順位継承,優先度減少など,OSKitのスレッドスケジューリングメカニズムを完全に解明した.
<!-- google_ad_client = "pub-0246923946865164";/* 728x90, created 10/10/09 */google_ad_slot = "1248078023"; google_ad_width = 728; google_ad_height = 90;//-->