Выполнение Выполнение Выполнение процесса С процесса С процесса А

•---- °.---------- < j> •-------- °

_т о Процесс С

scheduler_tick() приостанавливается

schedule()

Рис. 7.1. Планирование процессов

Process В выполняется некоторое время, которое ему выделено для работы с процессором. Обычно это происходит, когда процесс ожидает некоторых ресурсов. В вызывает schedule (), выбирающую в качестве следующего Process С.

Process С выполняется до возникновения scheduler_tick (), которая не помечает С как требующий перепланировки. В результате внутри вызова schedule () у Process С не забирается управление процессором.

Process С приостанавливается вызовом schedule (), определяющей, что Process A требуется передать управление процессором, и запускающей А на выполнение.

Сначала мы рассмотрим schedule (), с помощью которой ядро Linux решает, какой процесс нужно выполнять следующим, а затем мы рассмотрим scheduler_tick(), в которой ядро решает, какому процессу можно занять процессор. Комбинированный эффект этих двух функций демонстрирует поток управления внутри планировщика:

Kernel/sched.с

2184 asmlinkage void schedule(void)

2185 {

2186 long *switch__count;

2187 task_t *prev, *next;

2188 runqueue_t *rq;

2189 prio_array_t *array;

Планировщик Linux

2190 struct list_head *queue;

2191 unsigned long long now;

2192 unsigned long run_time;

2193 int idx; 2194

2195 /*

2196 * Тест на атомарность.Так как do_exit() необходимо вызвать

2197 * schedule() атомарно, мы игнорируем этот путь.

2198 * В противном случае жалуемся, что мы вызываем планировщик,

2199 * хотя это и не нужно. */

2200 if (likely(! (current-> state & (TASK_DEAD | TASK_ZOMBIE) ) ) ) {

2201 if (unlikely(in_atomic())) {

2202 printk(KERN_ERR " bad: scheduling while atomic! \n ^H);

2203 dump_stack();

2204 }

2205 } 2206

2207 need_resched:

2208 preempt_disable ();

2209 prev = current;

2210 rq = this_rq(); 2211

2212 release_Jcernel_lock(prev);

2213 now = sched_clock();

2214 if (likely(now - prev-> timestamp < NS_MAX_SLEEP_AVG))

2215 run_time = now - pr ev-> times tamp;

2216 else

2217 run_time = NS_MAX_SLEEP_AVG; 2218

2219 /*

2220 * Задача с интерактивным поведением получает меньше времени

2221 * благодаря высокому sleep_avg для отсрочки потери ими их

2222 * интерактивного статуса

2223 */

2224 if (HIGH_CREDIT(prev))

2225 run_time /= (CURRENT_BONUS(prev)? : 1);

Строки 2213-2218

Мы подсчитываем длительность времени, в течение которого процесс будет активен в планировщике. Если процесс будет активен дольше чем среднее максимальное время сна (NS_MAX_SLEEP_AVG), мы устанавливаем его время выполнения равным среднему максимальному времени сна.

Глава 7 • Планировщик и синхронизация ядра

Таким образом, код ядра Linux вызывает другой блок кода на время временного среза. Временной срез (timeslice) связан как со временем между прерываниями планировщика, так и с длительностью времени, в течение которого процесс использует процессор. Если процесс израсходовал свой временной срез, процесс становится исчерпанным и неактивным. Временная отметка (timerstamp) - это абсолютное значение, определяющее, как долго процесс использует процессор. Процессор использует временную отметку для определения временного среза процесса, использующего процессор.

Например, представим, что Process А имеет временной срез длительностью 50 циклов таймера. Он использует процессор в течение 5 циклов и затем передает управление процессором другому процессу. Ядро использует временную отметку для определения того, что у Process А осталось 45 циклов временного среза.

Строки 2224-2225

Интерактивные процессы - это процессы, тратящие большинство отведенного им времени на ожидание ввода. Хорошим примером интерактивного процесса является контроллер клавиатуры - большинство времени он ожидает ввода, но, когда он случается, пользователь ожидает, что он получит высокий приоритет.

Интерактивные процессы, для которых кредит интерактивности больше 100 (значение по умолчанию), получают свое эффективное run_time, деленное на [sleep_avg/max_sleep_avg*MAX_BONUS (10) ]*.

kernel/sched.с

2227 spin_lock_irq(& rq-> lock);

2229 /*

223 0 * как только мы входим в приоритетное прерывание обслуживания,

2231 * сразу переходим к выбору новой задачи.

2232 */

2233 switch_count = & prev-> nivcsw;

2234 if (prev-> state & & ! (preempt_count () & PREEMPT_ACTIVE) ) { 223 5 switch_count = & prev-> nvcsw;

2236 if (unlikely((prev-> state & TASK_INTERRUPTIBLE) & &

2237 unlikely(signal_pending(prev))))

2238 prev-> state = TASK_RUNNING;

2239 else

2240 deactivate_task(prev_/ rq);

2241 }

^h Бонусы - это модификаторы планировщика для повышения приоритета.

Планировщик Linux

Строка 2227

Функция выполняет блокировку очереди выполнения, так как мы хотим ее изменить.

Строки 2233-2241

Если мы вошли в schedule () с предыдущим процессом, являющимся приоритетным прерыванием обслуживания, то мы покидаем предыдущий запущенный процесс, если ожидается сигнал. Это значит, что ядро приоритетно прерывает обслуживание обычного процесса быстрым завершением; соответственно код содержится в двух операторах unlikely () \ Если приоритетных прерываний обслуживания больше нет, мы убираем прервавшие процессы из очереди выполнения и продолжаем выбирать следующий процесс для выполнения.

kernel/sched.с

2243 cpu = smp_processor_id();

2244 if (unlikely(! rq-> nr_running)) {

2245 idle_balance(cpu, rq);

2246 if (! rq-> nr_running) {

2247 next = rq-> idle;

2248 rq-> expired_timestamp = 0;

2249 wake_sleeping_dependent(cpu, rq);

2250 goto switch_tasks;

2251 }

2252 } 2253

2254 array = rq-> active;

2255 if (unlikely(! array-> nr_active)) {

2256 /*

2257 * Переключение между активным и истекшим массивами.

2258 */

2259 rq-> active = rq-> expired;

2260 rq-> expired = array; 22 61 array = rq-> active;

2262 rq-> expired_timestamp = 0;

22 63 rq-> best_expired_prio = MAX_PRIO;

2264 }

Строка 2243

Мы получаем идентификатор текущего процессора с помощью smp_processor id О.

¹ Более подробную информацию о функции unlikely см. в гл. 2, «Исследовательский инструментарий».

Глава 7 • Планировщик и синхронизация ядра

Строки 2244-2252

Если очередь выполнения не имеет в себе процессов, мы устанавливаем следующим процессом процесс простоя и сбрасываем временную отметку очереди выполнения в 0. На многопроцессорных системах мы сначала проверяем, выполняются ли на других процессорах процессы, которые можно выполнить на этом процессоре. В результате простаивающие процессы равномерно распределяются по всем процессорам системы. Только если не остается процессов, которые можно переместить на другие процессоры, следующим процессом в очереди выполнения мы устанавливаем процесс простоя и сбрасываем временную отметку истекших процессов.

Строки 2255-2264

Если очередь выполнения активных процессов пуста, мы переключаемся между активным и истекшим массивами указателей перед выбором нового процесса для выполнения.

kernel/sched.с

2266 idx = sched_find_first_bit(array-> bitmap);

2267 queue = array-> queue + idx;

2268 next = list_entry(queue-> next_/ task_t, run_list); 2269

2270 if (dependent__sleeper(cpu, rq, next)) {

2271 next = rq-> idle;

2272 goto switch__tasks;

2273 }
2274

2275 if (! rt_task(next) & & next-> activated > 0) {

2276 unsigned long long delta = now - next-> timestamp;
2277

2278 if (next-> activated == 1)

2279 delta = delta * (ON_RUNQUEUE_WEIGHT * 128 / 100) / 128; 2280

2281 array = next-> array;

2282 dequeue_task(next, array);

2283 recalc_task__prio(next, next-> timestamp + delta);

2284 enqueue_task(next, array);

2285 }

228 6 next-> activated = 0;

Строки 2266-2268

Планировщик ищет процесс с наивысшим приоритетом для запуска с помощью sched_f ind_f irst_bit () и затем устанавливает queue в указатель на список,

Планировщик Linux

хранящийся в массиве приоритетов в специальном месте; next инициализируется первым процессом из queue.

Строки 2270-2273

Если активируемые процессы зависят от спящих сестринских процессов, мы выбираем новый процесс для активации и переходим в switch_task для продолжения функции планировщика.

Предположим, что у нас есть Process А, порожденный Process В для чтения с устройства, и Process А ожидает завершения Process В, чтобы продолжить свое выполнение. Если планировщик выберет для активации Process А, этот блок кода dependent_ sleeper () определит, что Process А ожидает Process В, и выберет более новый процесс для активации.

Строки 2275-2285

Если атрибут активации процесса больше 0 и следующий процесс не является задачей реального времени, мы удаляем его из queue, пересчитываем его приоритет и снова помешаем его в очередь.

Строка 2286

Мы устанавливаем атрибут активации процесса в 0 и затем выполняем его.

kernel/sched.с

2287 switch_tasks:

2288 prefetch(next);

2289 clear_tsk_need_resched(prev);

2290 RCU_qsctr(task_cpu(prev))++; 2291

2292 prev-> sleep_avg -= run_time;

2293 if ((long)prev-> sleep_avg < = 0) {

2294 prev-> sleep_avg = 0;

2295 if (! (HIGH_CREDIT(prev) || LOW_CREDIT(prev) ) )

2296 prev-> interactive_credit--;

2297 }

2298 prev-> timestamp = now; 2299

2300 if (likely(prev! = next)) {

2301 next-> timestamp = now;
23 02 rq-> nr_switches++;

23 03 rq-> curr = next;

23 04 ++*switch_count;

23 06 prepare_arch_switch(rq, next);

2307 prev = context_switch(rq, prev, next);

Глава 7 • Планировщик и синхронизация ядра

23 08 barrier();
2309

2310 finish_task_switch(prev);

2311 } else

2312 spin_unlock_irq(& rq-> lock); 2313

2314 reacquire_kernel_lock(current);

2315 preempt_enable_no_resched();

2316 if (test_thread_flag(TIF_NEED_RESCHED))

2317 goto need_resched;

2318 }

Строка 2288

Мы пытаемся поместить память структуры задачи нового процесса в кеш процессора первого уровня (L1). (См. более подробную информацию в include/linus/ prefetch, h.)

Строка 2290

Так как мы выполняем переключение контекста, нам нужно проинформировать об этом текущий процессор. Это позволяет многопроцессорному устройству получить доступ к разделяемому между несколькими процессорами ресурсу в эксклюзивном режиме. Этот процесс называется обновлением копирующего чтения. (Более подробную информацию см. в http: //lse.sourceforge.net/locking/ rcupdate. html.)

Строки 2292-2298

Мы уменьшаем атрибут sleep_avg предыдущего процесса на количество времени, в течение которого он выполнялся, корректируя отрицательные значения. Если процесс не является ни интерактивным, ни неинтерактивным, а его значение интерактивности находится между наименьшим и наибольшим значениями, мы увеличиваем его значение интерактивности, так как он обладает низким значением среднего сна. Мы обновляем его временную отметку в значение текущего времени. Эта операция помогает планировщику следить за тем, сколько процессорного времени тратит текущий процесс, и оценить, сколько процессорного времени он потребует в будущем.

Строки 2300-2304

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

7.1 Планировщик Linux

Строки 2306-2308

Эти строки описывают context_switch() на языке ассемблера. Задержимся на несколько абзацев до тех пор, пока мы погрузимся в объяснение переключения контекста в следующем разделе.

Строки 2314-2318

Мы перепоручаем блокировку ядра, включаем приоритетное прерывание обслуживания и смотрим, нужно ли нам производить немедленную перепланировку; если да, мы возвращаемся в начало schedule ().

Может случиться, что после выполнения context_switch () нам потребуется выполнить перепланировку. Возможно, что scheduler_tick() пометит новый процесс как нуждающийся в перепланировке или, когда включено приоритетное прерывание обслуживания, он будет помечен. Мы продолжаем процесс перепланировки (и затем переключаем контекст) до тех пор, пока не найдем первый процесс, не требующий перепланировки. Процесс, завершающий schedule (), становится новым процессом, выполняемым на данном процессоре.

Переключение контекста

Функция context_switch (), вызываемая из schedule () в /kernel/sched. с, выполняет специфическую для системы работу по переключению окружения памяти и состояния процесса. На абстрактном уровне context_switch переключает текущую задачу и следующую задачу. Функция context_switch () начинает выполнение следующей задачи и возвращает указатель на структуру задачи, которая выполнялась до вызова:

kernel/sched.c

1048 /*

1049 * context_switch - переключение на новый ММ и новое

1050 * состояние регистра потока.

1051 */

1052 static inline

1053 task_t * context_switch(runqueue_t *rq, task__t *prev, task_t *next)

1054 {

1055 struct mm_struct *mm = next-> mm;

1056 struct mm_struct *oldmm = prev-> active_mm;

1063 switch_irati(oldnim_/ mm, next);

1072 switch_to(prev_/ next, prev); 1073

1074 return prev;

1075 }

Глава 7 • Планировщик и синхронизация ядра

Здесь мы описываем две задачи context_switch: переключение виртуального отображения памяти и переключение структуры задачи/потока. За выполнение первой задачи отвечает switch_mm() с применением множества аппаратно-зависимых управляющих памятью структур и регистров:

/include/asm-i386/mmu_context.h

026 static inline void switch_mm(struct ram_struct *prev,

27 struct mm_struct *next,

28 struct task_struct *tsk)

029 {

030 int cpu = smp_processor_id();
031

32 if (likely(prev! = next)) {

33 /* остановка сброса ipis для предыдущего mm */

34 cpu_clear(cpu, prev-> cpu_vm_mask);

035 #ifdef CONFIG_SMP

36 cpu_tlbstate[cpu].state = TLBSTATE_OK;

37 cpu_tlbstate[cpu].active_mm = next;

038 #endif

039 cpu_set(cpu_/ next-> cpu_vm_jriask);
040

41 /* Перезагрузка таблицы страниц */

42 load_cr3(next-> pgd); 043

44 /*

45 * загрузка LDT, если LDT отличается:

46 */

047 if (unlikely(prev-> context.ldt! = next-> context.ldt))

048 load_LDT_nolock(& next-> context, cpu);

49 }

50 #ifdef CONFIG_SMP

051 else {

Строка 39

Связывает новую задачу с текущим процессором.

Строка 42

Код переключения контекста памяти использует аппаратный х86-регистр сгЗ, хранящий базовый адрес всех виртуальных операций для данного процесса. Новый глобальный описатель страницы загружается сюда из next-> pgd.

Планировщик Linux

Строка 47

Большинство процессов разделяют один и тот же LDT. Если процессу требуется другой LDT, он загружается сюда из новой структуры next-> context.

Другая половина функции context_switch() находится в /kernel/sched. с,

где вызывается макрос switch_to (), который вызывает С-функцию_____ switch_to ().

Архитектурные ограничения независимы от архитектурных зависимостей для х86- и РРС-макросов switch_to ().

Отслеживание х86 switchJo()

Код х86 более компактен, чем код РРС. Далее приведен архитектурно-зависимый код для

__ switch_to (); task_struct (не tread_struct) передается в______________ switch_to ().

Код, обсуждаемый далее, - встроенный ассемблерный код для вызова С-функции

__ switch_to() (строка 23) с соответствующей структуры task_struct в качестве

параметра.

switch_to получает три указателя на задачи: prev, next и las t. Дополнительно существует текущий указатель.

Давайте объясним на самом верхнем уровне, что происходит, когда вызывается switch_to (), и как указатель на задачу изменяется после вызова switch_to ().

Рис. 7.2 демонстрирует три вызова switch_to () с использованием трех процессов А, В иС.

Мы хотим переключиться с А на В. Перед первым вызовом мы имеем:

• Текущий -* А

• Предыдущий -> А, следующий -► В После первого вызова:

• Текущий -► В

• Последний -► А

Теперь мы хотим переключиться с В на С. Перед вторым вызовом мы имеем:

• Текущий -► В

• Предыдущий -♦ В, следующий -* С После второго вызова:

• Текущий -♦ С

• Последний -+ В

После возвращения из второго вызова текущий указывает на задачу (С) и последний указывает на (В).

Далее метод продолжает работать с задачей (А), переключая ее еще раз, и т. д.

Глава 7 • Планировщик и синхронизация ядра


		TASK A	TASK В
	CURRENT


Первый вызов	SWITCH.TO (PREV, NEXT, LAST) 1
			TASK В	TASK С	TASK A
	CURRENT


Второй вызов	SWITCH.TO (PREV, NEXT, LAST) 1
			TASK С	TASK A	TASK В
	CURRENT


Третий вызов	SWITCH.TO (PREV, NEXT, LAST) 1
			TASK A	TASK?	TASK С
	CURRENT


	ИТОМУПОДОБН	OE...

Рис. 7.2. Вызовы switch_to

Ассемблерная вставка функции switch_to() является отличным примером ассемблерной магии в ядре. Кроме этого, она является отличным примером С-расширения дсс. (См. в гл. 2, «Исследовательский инструментарий», обучающий пример по этой функции.) Теперь мы пройдемся по коду этого блока.

/include/asm-i386/system.h

_switch_to(struct task_struct

012 extern struct task_struct * FAST/CALL (_

*prev, struct task_struct *next));

015 tdefine switch_to(prev, next, last) do {

016 017 018 019 020 021 022

unsigned long esi, edi; asm volatile(" pushfl\n\t"

" pushl %%ebp\n\t" " movl %%esp, %0\n\t" " movl %5, %%esp\n\t" " movl $lf, %l\n\t" ^Hpushl %6\n\t"

/* сохранение ESP */ N

/* восстановление ESP */

/* сохранение EIP */ \

/* восстановление EIP */

Планировщик Linux

023 " jmp ____ switch_to\n" \

23 -l: \t" \

24 " popl %%ebp\n\t" \

02 5 " popfl" \

26: " =m" (prev-> thread.esp), " =m" (prev-> thread.eip), \

27 " =a" (last), " =S^H (esi), " =D" (edi) \

28: " m" (next-> thread.esp), " m" (next-> thread.eip), \

29 ⁿ2" (prev), " d" (next)); \

03 0 } while (0)

Строка 12

Макрос FASTCALL обращается к _______ attribute_regparm(3), принудительно

передающему параметры в регистры вместо стека.

Строки 15-16

Конструкция do { } while (0) позволяет (помимо прочего) иметь макросу локальные переменные esi и edi. Помните, что это просто локальные переменные с такими именами.

⇐ Предыдущая 35 36 37 38 394041 42 43 44 Следующая ⇒