Linuxカーネルのスケジューラがどのように機能するかを理解しようとしています
このリンクに記載されているように
http://books.google.co.in/books?id=NXVkcCjPblcC&lpg=PP1&pg=PA47#v=onepage&q&f=false および次のリンク http://www.informit.com/articles/article.aspx?p=101760&seqNum= 2
struct runque は、スケジューラが実行される基本的なデータ構造です
それは
struct runqueue {
spinlock_t lock; /* spin lock which protects this
runqueue */
unsigned long nr_running; /* number of runnable tasks */
unsigned long nr_switches; /* number of contextswitches */
unsigned long expired_timestamp; /* time of last array swap */
unsigned long nr_uninterruptible; /* number of tasks in
uinterruptible sleep */
struct task_struct *curr; /* this processor's currently
running task */
struct task_struct *idle; /* this processor's idle task */
struct mm_struct *prev_mm; /* mm_struct of last running task
*/
struct prio_array *active; /* pointer to the active priority
array */
struct prio_array *expired; /* pointer to the expired
priority array */
struct prio_array arrays[2]; /* the actual priority arrays */
int prev_cpu_load[NR_CPUS];/* load on each processor */
struct task_struct *migration_thread; /* the migration thread on this
processor */
struct list_head migration_queue; /* the migration queue for this
processor */
atomic_t nr_iowait; /* number of tasks waiting on I/O
*/
}
上記には2人のメンバーがいます
struct prio_array *active; /* pointer to the active priority
array */
struct prio_array *expired; /* pointer to the expired priority array */
構造体prio_arrayは次のように定義されています
struct prio_array {
int nr_active; /* number of tasks */
unsigned long bitmap[BITMAP_SIZE]; /* priority bitmap */
struct list_head queue[MAX_PRIO]; /* priority queues */
};
私は次の文で明確ではありません
質問1）
Each priority array contains one queue of runnable processors per priority level.
上記の定義の中で、struct prio_array 実行可能なプロセッサのキューはどこにありますか
それからそれは言います
The priority arrays also contain a priority bitmap used toシステム内で最も優先度の高い実行可能なタスクを効率的に発見します。
次に、「140 の優先順位と 32 ビット ワードで、これは 5 です」と表示されます。
これが 5 であるという結論はどのようにして得られるのでしょうか? その背後にある数学的計算は何ですか?
上記は、2 番目のリンクで公開されている本の第 4 章からの抜粋で、どちらも同じテキストを含んでいます。わかりやすくするためにここに掲載しました。
* UPDATE1 * コメントに基づいて、私が求めていることを明確にしたかっただけです
BITMAP_SIZE は、有効な優先度レベルごとに 1 ビットを提供するために unsigned long 型変数の配列が必要とするサイズです。140 の優先順位と 32 ビット ワードを使用すると、これは 5 になります。
質問 2)
各優先度レベルに 1 ビットが与えられ、140 の優先度レベルが存在するため、配列サイズがどのように 5 になるかは不明です。140/32=5 ではない BITMAP_SIZE 計算のロジックが得られません。
それは次の段落と関係があります
When a task of a given priority becomes runnable (that is,
its state becomes TASK_RUNNING), the corresponding bit in the
bitmap is set to one. For example, if a task with priority seven is
runnable, then bit seven is set
配列であるリンク上
unsigned long bitmap[BITMAP_SIZE]; /* priority bitmap */
が設定されているため、基本的にこの配列がどのように設定されているかが明確ではありません。正しく説明できる場合は、質問 1 も参照してください。
UPDATE 2と以下の回答の説明
以下の回答で、基本的にここに来れば、将来的に役立つかもしれない小さな説明を追加しています
スケジューラーはランキューと実行可能なプロセスのリストを維持し、各実行可能なプロセスは正確に 1 つのランキュー上にあります。私が提供したリンク先の記事では、多くの実行キューを持つマルチ プロセッサ システムについて考察しています。さまざまな優先度
140 の優先度レベルがあり、各優先度レベルには TASK_RUNNING 状態の異なるプロセスがあります。たとえば、優先度 8 のプロセスが多数存在する可能性があります (例として 8 を取り上げました) struct runque は、優先度配列を示します。
btimap[BITMAP] /* this is the priority level
struct list_head /* points to the start of list of processes of that run level
したがって、runque は優先度配列を指し、優先度配列から O(1) 時間で実行する必要があるプロセスを簡単に取得できます。