Понимание планировщика Linux

Question

Я новичок в ядре Linux и низкоуровневом программировании. Я хотел знать, как планировщик Linux должен быть O (1) во временной сложности.

Я наткнулся на следующую статью, которая очень информативна, но у меня возникли проблемы с пониманием текста, который я воспроизвел ниже. http://www.ibm.com/developerworks/linux/library/l-scheduler/

Работа планировщика проста: выберите задачу на самом высоком список приоритетов для выполнения. Чтобы сделать этот процесс более эффективным, Растровое изображение используется, чтобы определить, когда задачи находятся в заданном списке приоритетов. Поэтому на большинстве архитектур инструкция find-first-bit-set используется для нахождения бита с самым высоким приоритетом, установленного в одном из пяти 32-битных слов (для 140 приоритетов). Время, которое требуется, чтобы найти задачу для выполнения зависит не от количества активных задач, а от количества приоритеты. Это делает планировщик 2.6 процессом O (1), потому что время составления графика является фиксированным и детерминированным независимо от количество активных заданий.

Почему 5 слов по 32 бита для 140 очередей? Кому помогает команда find-first-bit-set выбрать одну из 140 очередей?

Answer 1

В битовом поле используется одно значение для представления числа логических состояний, например, если бы мы использовали 8-битное целое число, то мы могли бы сказать, что:

17 (decimal) = 00010001 (binary)

Что означает, что 4-е иВосьмые логические значения имеют значение true, а все остальные логические значения - false.Всего можно отследить 8 логических состояний, так как имеется 8 битов.

Поскольку мы хотим отслеживать 140 состояний (1 для каждой очереди, значение true, указывающее, что очередь содержит задачу), требуется 140 битов, и поэтому140/32 = 4,375, нам нужно как минимум 5 32-битных целых чисел для хранения всех логических состояний.

Answer 2

Примерно так:

int bitmap_idx = priority/BITS_PER_WORD;
int bitmap_bit = priority%BITS_PER_WORD;

isSet = ( bitmap[bitmap_idx]&(1<<bitmap_bit) );  //test
bitmap[bitmap_idx] |= 1<<bitmap_bit;             //set

используется для достижения конкретного процесса с массивом приоритетов, и именно так растровые изображения используются в планировщике, который, в свою очередь, зависит от struct prio_array

Статья, которую вы указали, устарела, проверьте эту http://www.informit.com/articles/article.aspx?p=101760&seqNum=2