Второе издание
 Скачать 3.09 Mb.
|
|
Балансировка нагрузки Как уже рассказывалось ранее, планировщик операционной системы Linux ре- ализует отдельные очереди выполнения и блокировки для каждого процессора в симметричной многопроцессорной системе. Это означает, что каждый процессор поддерживает свой список процессов и выполняет алгоритм планирования только для заданий из этого списка. Система планирования, таким образом, является уни- кальной для каждого процессора. Тогда каким же образом планировщик обеспечива- ет какую-либо глобальную стратегию планирования для многопроцессорных систем? Что будет, если нарушится балансировка очередей выполнения, скажем, в очереди выполнения одного процессора будет находиться пять процессов, а в очереди дру- гого — всего один? Решение этой проблемы выполняется системой балансировки на- грузки, которая работает с целью гарантировать, что все очереди выполнения будут сбалансированными. Система балансировки нагрузки сравнивает очередь выполне- ния текущего процессора с другими очередями выполнения в системе. Планирование выполнения процессов 83 Функция add_wait_que-je() помещает задачу в очередь ожидания, устанавливает состояние задачи TASK_INTERRUPTIBLE и вызывает функцию schedule(). Функция scheduled вызывает функцию deactivate_task(), которая удаляет задачу из очереди выполнения. Задача готова к выполнению Задача не готова к выполнению Получен сигнал, задача устанавливается в состояние TASK_RUNNING и выполняет обработчик сигнала Событие, на которое ожидала задача, произошло, и функция try_to_wake_up() устанавливает задачу в состояние TASK_RUNNING, вызывает функцию activate_task() и функцию schedule() . Функция remove_wait_quaue () удаляет задачу из очереди ожидания. Рис. 4,3. Переход в приостановленное состояние (sleeping) и возврат к выполнению (wake up) Если обнаруживается дисбаланс, то процессы из самой загруженной очереди вы- полнения выталкиваются в текущую очередь, В идеальном случае каждая очередь вы- полнения будет иметь одинаковое количество процессов. Такая ситуация, конечно, является высоким идеалом, к которому система балансировки может только прибли- зиться. Система балансировки нагрузки реализована в файле k e r n e l / s c h e d . с в виде функции load_balance (). Эта функция вызывается в двух случаях. Она вызывается функцией s c h e d u l e (), когда текущая очередь выполнения пуста. Она также вызы- вается по таймеру с периодом в 1 мс, когда система не загружена, и каждые 200 мс в другом случае. В однопроцессорной системе функция l o a d _ b a l a n c e () не вызыва- ется никогда, в действительности она даже не компилируется в исполняемый образ ядра, питому что в системе только одна очередь выполнения и никакой балансиров- ки не нужно. Функция балансировки нагрузки вызывается при заблокированной очереди вы- полнения текущего процессора, прерывания при этом также запрещены, чтобы за- щитить очередь выполнения от конкурирующего доступа. В том случае, когда функ- ция load b a l a n c e ( ) вызывается из функции s c h e d u l e ( ) , цель ее вызова вполне ясна, потому что текущая очередь выполнения пуста и нахождение процессов в других очередях с последующим их проталкиванием в текущую очередь позволяет получить преимущества. Когда система балансировки нагрузки активизируется по- средством таймера, то ее задача может быть не так очевидна. В данном случае это необходимо для устранения любого дисбаланса между очередями выполнения, что- бы поддерживать их в почти одинаковом состоянии, как показано на рис. 4.4. 84 Глава 4 load_balancer() Проталкивание процесса из одной очереди в другую для уменьшения дисбаланса Процесс 1 Процесс 2 Процесс 3 Процесс 4 Процесс 5 Процесс 6 Процесс 15 Очередь выполнения процессора 1,всего 20 процессов Очередь выполнения процессора 2, всего 15процессов Рис. 4.4. Система балансировки нагрузки Функция load_balance () и связанные с ней функции сравнительно большие и сложные, хотя шаги, которые они предпринимают, достаточно ясны. • Функция load_balance () вызывает функцию find_busiest_queue () для определения наиболее загруженной очереди выполнения. Другими словами — очередь с наибольшим количеством процессов в ней. Если нет очереди выпол- нения, количество процессов в которой на 25% больше, чем в дайной очереди, то функция f ind_busiest_queue () возвращает значение NULL и происходит возврат из функции load_balance (). В другом случае возвращается указатель на самую загруженную очередь. • Функция load_balance () принимает решение о том, из какого массива прио- ритетов самой загруженной очереди будут проталкиваться процессы. Истекший массив является более предпочтительным, так как содержащиеся в нем задачи не выполнялись достаточно долгое время и, скорее всего, не находятся в кэше процессора (т.е. не активны в кэше, not "cache hot"). Если истекший массив приоритетов пуст, то ничего не остается, как использовать активный массив. • Функция load_balance () находит непустой список заданий, соответствующий самому высокому приоритету (с самым маленьким номером), так как важно бо- лее равномерно распределять задания с высоким приоритетом, чем с низким. • Каждое задание с данным приоритетом анализируется для определения зада- ния, которое не выполняется, не запрещено для миграции из-за процессорной привязки и не активно в кэше.Если найдена задача, которая удовлетворяет этому критерию, то вызывается функция p u l l _ t a s k () для проталкивания этой задачи из наиболее загруженной очереди в данную очередь. • Пока очереди выполнения остаются разбалансированными, предыдущие два шага повторяются и необходимое количество заданий проталкивается из са- мой загруженной очереди выполнения в данную очередь выполнения. В конце концов, когда дисбаланс устранен, очередь выполнения разблокируется и про- исходит возврат из функции load_balance (). Планирование выполнения процессов 85 Процесс З Процесс 4 Процесс 5 Процесс 6 Процесс 20 Процесс 1 Процесс 2 Далее показана функция load_balance (), немного упрощенная, но содержащая все цажные детали. static int load_balance(int this_cpu, runqueue_t *this_rq, struct sched_doraain *sd, enum idle_type idle) { struct sched_group *group; runqueue_t *busiest; unsigned long imbalance; int nr_moved; spin_lock(&this_rq->lock); group = find_busiest_group(sd, this_cpu, &imbalance, idle); if (!group) goto out_balanced; busiest = find_busiest_queue(group) ; if (!busiest) goto out_balanced; nr_moved = 0; if (busiest->nr_running > 1) { double_lock_balance(this_rq, busiest); nr_moved = move_tasks(this_rq, this_cpu, busiest, imbalance, sd, idle); spin_unlock(&busiest->lock); } spin_unlock(&this rq->lock); if (!nr_moved) { sd->nr_balance_failed++; if (unlikely(sd->nr_balance_failed > sd->cache_nice_tries+2)) { int wake = 0; spin_lock(abusiest->lock); if (!busiest->active_balance) { busiest->active_balance = 1; busiest->push_cpu = this_cpu; wake = 1; } spin_unlock(&busiest->lock); if (wake) wake_up_process(busiest->migration_thread); sd->nr_balance_failed = sd->cache_nice_tries; ) } else sd->nr_balance_failed = 0; sd->balance_interval = sd->min_interval; return nr_moved; 86 . Глава 4 out_balanced: spin_unlock (&this_rq->lock) ; if (sd->balance_interval < sd->max_interval) sd->balance_interval *= 2; return 0; } Вытеснение и переключение контекста Переключение контекста — это переключение от одной, готовой к выпол- нению задачи к другой. Это переключение производится с помощью функции context_switch(), определенной в файле kernel/sched.с. Данная функция вы- зывается функцией schedule (), когда новый процесс выбирается для выполнения. При этом выполняются следующие шаги. • Вызывается функция switch_mm (), которая определена в файле include/asm/ mmu_context.h и предназначена для переключения от виртуальной памяти старого процесса к виртуальной памяти нового процесса. • Вызывается функция s w i t c h _ t o () , определенная в файле i n c l u d e /asm/ system.h, для переключения от состояния процессора предыдущего процесса к состоянию процессора нового процесса. Эта процедура включает восстанов- ление информации стека ядра и регистров процессора. Ядро должно иметь информацию о том, когда вызывать функцию schedule (). Если эта функция будет вызываться только тогда, когда программный код вызывает ее явно, то пользовательские программы могут выполняться неопределенное время. Поэтому ядро поддерживает флаг need_resched для того, чтобы сигнализировать, необходимо ли вызывать функцию schedule () (табл. 4.2). Этот флаг устанавлива- ется функцией schediiler_tick (), когда процесс истрачивает свой квант времени, и функцией try_to_wake_up (), когда процесс с приоритетом более высоким, чем у текущего процесса, возвращается к выполнению. Ядро проверяет значение этого флага, и если он установлен, то вызывается функция schedule () для переключения на новый процесс. Этот флаг является сообщением ядру о том, что планировщик должен быть активизирован по возможности раньше, потому что другой процесс должен начать выполнение. Таблица 4.2. Функции для управления флагом n e e d _ r e s c h e d Функция Назначение set_tsk_need_resched (task) Установить флаг need_resched для данного процесса clear_tsk_need_resched (task) Очистить флаг need_resched для данного процесса need_resched() Проверить значение флага need_resched для данного процесса. Возвращается значение true, если этот флаг установлен, и false, если не установлен Планирование выполнения процессов 87 Во время переключения в пространство пользователи или при возврате из пре- рывания, значение флага need_resched проверяется. Если он установлен, то ядро активизирует планировщик перед тем, как продолжить работу. Этот флаг не является глобальной переменной, так как обращение к дескрипто- ру процесса получается более быстрым, чем обращение к глобальным данным (из-за скорости обращения к переменной current и потому, что соответствующие данные могут находиться в кэше). Исторически, этот флаг был глобальным в ядрах до серии 2.2. В ядрах серий 2.2 и 2.4 этот флаг принадлежал структуре task_struct и имел тип int. В серии ядер 2.6 этот флаг перемещен в один определенный бит специаль- ной переменной флагов структуры thread info. Легко видеть, что разработчики ядра никогда не могут быть всем довольны. Вытеснение пространства пользователя Вытеснение пространства пользователя (user preemption) происходит в тот мо- мент, когда ядро собирается возвратить управление режиму пользователя, при этом устанавливается флаг need_resched и, соответственно, активизируется планиров- щик. Когда ядро возвращает управление в пространство пользователя, то оно нахо- дится в безопасном и "спокойном" состоянии. Другими словами, если продолжение выполнения текущего задания является безопасным, то безопасным будет также и выбор нового задания для выполнения. Поэтому когда ядро готовится возвратить управление в режим пользователя или при возврате из прерывания или после си- стемного вызова, происходит проверка флага need_resched. Если этот флаг уста- новлен, то активизируется планировщик И выбирает новый, более подходящий процесс для исполнения. Как процедура возврата из прерывания, так и процедура возврата из системного вызова являются зависимыми от аппаратной платформы и обычно реализуются на языке ассемблера в файле entry.S (этот файл, кроме кода входа в режим ядра, также содержит и код выхода из режима ядра). Если коротко, то вытеснение пространства пользователя может произойти в следующих случаях. • При возврате в пространство пользователя из системного вызова. • При возврате в пространство пользователя из обработчика прерывания. Вытеснение пространства ядра Ядро операционной системы Linux, в отличие от ядер большинства вариантов ОС Unix, является полностью преемптивным (вытесняемым, preemptible). В непре- емптивных ядрах код ядра выполняется до завершения. Иными словами, планиров- щик не может осуществить планирование для выполнения другого задания, пока какое-либо задание выполняется в пространстве ядра — код ядра планируется на вы- полнение кооперативно, а не посредством вытеснения. Код ядра выполняется до тех пор, пока он не завершится (возвратит управление в пространство пользователя) или пока явно не заблокируется. С появлением серии ядер 2.6, ядро Linux стало пре- емптивным: теперь есть возможность вытеснить задание в любой момент, конечно, пока ядро находится в состоянии, когда безопасно производить перепланирование выполнения. В таком случае когда же безопасно производить перепланирование? Ядро способ- но вытеснить задание, работающее в пространстве ядра, когда это задание не удер- 88 Глава 4 живает блокировку. Иными словами, блокировки используются в качестве маркеров тех областей, в которые задание не может быть вытеснено. Ядро рассчитано на мно- гопроцессорность (SMP-safe), поэтому если блокировка не удерживается, то код ядра является реентерабельным и его вытеснять безопасно. Первое изменение, внесенное для поддержки вытеснения пространства ядра, — это введение счетчика преемптивности p r e e m p t _ c o u n t в структуру t h r e a d _ i n f о каждого процесса. Значение этого счетчика вначале равно нулю и увеличивается на единицу при каждом захвате блокировки, а также уменьшается на единицу при каж- дом освобождении блокировки. Когда значение счетчика равно нулю— ядро явля- ется вытесняемым. При возврате из обработчика прерывания, если возврат выпол- няется в пространство ядра, ядро проверяет значения переменных n e e d _ r e s c h e d и p r e e m p t _ c o u n t . Если флаг n e e d _ r e s c h e d установлен и значение счетчика preempt__count равно нулю, значит, более важное задание готово к выполнению и выполнять вытеснение безопасно. Далее активизируется планировщик. Если зна- чение счетчика p r e e m p t _ c o u n t не равно нулю, значит, удерживается захваченная блокировка и выполнять вытеснение не безопасно. В таком случае возврат из об- работчика прерывания происходит в текущее выполняющееся задание. Когда осво- бождаются все блокировки, удерживаемые текущим заданием, значение счетчика preempt_count становится равным нулю. При этом код, осуществляющий освобож- дение блокировки, проверяет, не установлен ли флаг need_resched. Если установ- лен, то активизируется планировщик. Иногда коду ядра необходимо иметь возмож- ность запрещать или разрешать вытеснение в режиме ядра, что будет рассмотрено в главе 9. Вытеснение пространства ядра также может произойти явно, когда задача бло- кируется в режиме ядра или явно вызывается функция s c h e d u l e () . Такая форма преемптивности ядра всегда поддерживалась, так как в этом случае нет необходимо- сти в дополнительной логике, которая бы давала возможность убедиться, что вытес- нение проводить безопасно. Предполагается, что если код явно вызывает функцию schedule (), то точно известно, что перепланирование производить безопасно. Вытеснение пространства ядра может произойти в следующих случаях. • При возврате из обработчика прерывания в пространство ядра. • Когда код ядра снова становится преемптивным. • Если задача, работающая в режиме ядра, явно вызывает функцию schedule (). • Если задача, работающая в режиме ядра, переходит в приостановленное состо- яние, т.е. блокируется (что приводит к вызову функции schedule ()). Режим реального времени Операционная система Linux обеспечивает две стратегии планирования в режи- ме реального времени (real-lime): SCHED_FIFO и SCHED_RR. Стратегия планирования SCHED_OTHER является обычной стратегией планирования, т.е. стратегий планирова- ния не в режиме реального времени. Стратегия SCHED_FIFO обеспечивает простой алгоритм планирования по идеологии "первым вошел — первым обслужен" (first-in first-out, FIFO) без квантов времени. Готовое к выполнению задание со стратегией планирования SCHED_FIFO всегда будет планироваться на выполнение перед всеми заданиями со стратегией планирования SCHED_OTHER. Когда задание со стратегией Планирование выполнения процессов 89 SCHED_FIFO становится готовым к выполнению, то оно будет продолжать выпол- няться до тех пор, пока не заблокируется или пока явно не отдаст управление. Две или более задач с одинаковым приоритетом, имеющие стратегию планирования SCHED_FIFO, будут планироваться на выполнение по круговому алгоритму (round- robin). Если задание, имеющее стратегию планирования SCHED_FIFO, является гото- вым к выполнению, то все задачи с более низким приоритетом не могут выполнять- ся до тех пор, пока это задание не завершится. Стратегия SCHED_RR аналогична стратегии SCHED_FIFO, за исключением того, что процесс может выполняться только до тех пор, пока не израсходует предопре- деленный ему квант времени. Таким образом, стратегия SCHED_RR — это стратегия SCHED_FIFO с квантами времени, т.е. круговой алгоритм планирования (round-robin) реального времени. Когда истекает квант времени процесса со стратегией планиро- вания SCHED_RR, то другие процессы с таким же приоритетом планируются по кру- говому алгоритму. Квант времени используется только для того, чтобы переплани- ровать выполнение заданий с таким же приоритетом. Так же как в случае стратегии SCHED_FIFO, процесс с более высоким приоритетом сразу же вытесняет процессы с более низким приоритетом, а процесс с более низким приоритетом никогда не смо- жет вытеснить процесс со стратегией планирования SCHED_RR, даже если у послед- него истек квант времени. Обе стратегии планирования реального времени используют статические при- оритеты. Ядро не занимается расчетом значений динамических приоритетов для за- дач реального времени. Это означает, что процесс, работающий в режиме реального времени, всегда сможет вытеснить процесс с более низким значением приоритета. Стратегии планирования реального времени в операционной системе Linux обе- спечивают так называемый мягкий режим реального времени (soft real-time). Мягкий режим реального времени обозначает, что ядро пытается планировать выполнение пользовательских программ в границах допустимых временных сроков, но не всегда гарантирует выполнение этой задачи. В противоположность этому операционные системы с жестким режимом реального времени (hard real-time) всегда гарантируют выполнение всех требований по планированию выполнения процессов в заданных пределах. Операционная система Linux не может гарантировать возможности плани- рования задач реального времени. Тем не менее стратегия планирования ОС Linux гарантирует, что задачи реального времени будут выполняться всякий раз, когда они готовы к выполнению. Хотя в ОС Linux и отсутствуют средства, гарантирующие ра- боту в жестком режиме реального времени, тем не менее производительность пла- нировщика ОС Linux в режиме реального времени достаточно хорошая. Ядро серии 2.6 в состоянии удовлетворить очень жестким временным требованиям. Приоритеты реального времени лежат в диапазоне от 1 до MAX_RT_PRIO минус 1, По умолчанию значение константы MAX_RT_PRIO равно 100, поэтому диапазон зна- чений приоритетов реального времени по умолчанию составляет от 1 до 99. Это пространство приоритетов объединяется с пространством значений параметра nice для стратегии планирования SCHED_OTHER, которое соответствует диапазону прио- ритетов от значения MAX_RT_PRIO до значения (MAX_RT_PRIO+40). По умолчанию это означает, что диапазон значений параметра nice от -20 до +19 взаимно однознач- но отображается в диапазон значений приоритетов от 100 до 139. 90 Глава 4 |