Стратегия (policy) планирования— это характеристики поведения планировщика, которые определяют, что и когда должно выполняться. Стратегия планирования определяет глобальный характер поведения системы и отвечает за оптимальное использование процессорного времени. Таким образом, это понятие очень важное.

 

Процессы, ограниченные скоростью ввода-вывода и скоростью процессора

Процессы можно классифицировать как те, которые ограничены скоростью ввода-вывода (I/O-bound), и те, которые ограничены скоростью процессора (processor-bound). К первому типу относятся процессы, которые большую часть своего времени выполнения тратят на отправку запросов на ввод-вывод информации и на ожидание ответов на эти запросы. Следовательно, такие процессы часто готовы к выполнению, но могут выполняться только в течение короткого периода времени, так как в конце концов они блокируются в ожидании выполнения ввода-вывода (имеются в виду не только дисковые операции ввода-вывода, но и любой другой тип ввода-вывода информации, как, например, работа с клавиатурой).

Процессы, ограниченные скоростью процессора, наоборот, большую часть времени исполняют программный код. Такие процессы обычно выполняются до того момента, пока они не будут вытеснены, так как эти процессы не блокируются в ожидании на запросы ввода-вывода. Поскольку такие процессы не влияют на скорость ввода-вывода, то для обеспечения нормальной скорости реакции системы не требуется, чтобы они выполнялись часто. Стратегия планирования процессов, ограниченных скоростью процессора, поэтому предполагает, что такие процессы должны выполняться реже, но более продолжительный период времени. Конечно, оба эти класса процессов взаимно не исключают друг друга. Пример процесса, ограниченного скоростью процессора, — это выполнение бесконечного цикла.

Указанные классификации не являются взаимно исключающими. Процессы могут сочетать в себе оба типа поведения: сервер системы X Windows — это процесс, который одновременно интенсивно загружает процессор и интенсивно выполняет операции ввода-вывода. Некоторые процессы могут быть ограничены скоростью ввода-вывода, но время от времени начинают выполнять интенсивную процессорную работу. Хороший пример — текстовый процессор, который обычно ожидает нажатия клавиш, но время от времени может сильно загружать процессор, выполняя проверку орфографии.

Стратегия планирования операционной системы должна стремиться к удовлетворению двух несовместных условий: обеспечение высокой скорости реакции процессов (малого времени задержки, low latency) и высокой производительности (throughput). Для удовлетворения этим требованиям часто в планировщиках применяются сложные алгоритмы определения наиболее подходящего для выполнения процесса, которые дополнительно гарантируют, что все процессы, имеющие более низкий приоритет, также будут выполняться. В Unix-подобных операционных системах стратегия планирования направлена на то, чтобы процессы, ограниченные скоростью ввода-вывода, имели больший приоритет. Использование более высокого приоритета для процессов, ограниченных скоростью ввода-вывода, приводит к увеличению скорости реакции процессов, так как интерактивные программы обычно ограничиваются скоростью ввода-вывода. В операционной системе Linux для обеспечения хорошей скорости реакции интерактивных программ применяется оптимизация по времени оклика (обеспечение малого времени задержки), т.е. процессы, ограниченные скоростью ввода-вывода, имеют более высокий приоритет. Как будет видно далее, это реализуется таким образом, чтобы не пренебрегать и процессами, ограниченными скоростью процессора.

 

Приоритет процесса

Наиболее широко распространенным типом алгоритмов планирования является планирование с управлением по приоритетам (priority-based). Идея состоит в том, чтобы расположить процессы по порядку в соответствии с их важностью и необходимостью использования процессорного времени. Процессы с более высоким приоритетом будут выполняться раньше тех, которые имеют более низкий приоритет, в то время как процессы с одинаковым приоритетом планируются на выполнение циклически (по кругу, round-robin), т.е. периодически один за другим. В некоторых операционных системах, включая Linux, процессы с более высоким приоритетом получают также и более длительный квант времени. Процесс, который готов к выполнению, у которого еще не закончился квант времени и который имеет наибольший приоритет, будет выполняться всегда. Как операционная система, так и пользователь могут устанавливать значение приоритета процесса и таким образом влиять на работу планировщика системы.

В операционной системе Linux используется планировщик с динамическим управлением по приоритетам (dynamic priority-based), который основан на такой же идее. Основной принцип состоит в том, что вначале устанавливается некоторое начальное значение приоритета, а затем планировщик может динамически уменьшать или увеличивать это значение приоритета для выполнения своих задач. Например, ясно, что процесс, который тратит много времени на выполнение операций ввода-вывода, ограничен скоростью ввода-вывода. В операционной системе Linux такие процессы получают более высокое значение динамического приоритета. С другой стороны, процесс, который постоянно полностью использует свое значение кванта времени, — это процесс, ограниченный скоростью процессора. Такие процессы получают меньшее значение динамического приоритета.

В ядре Linux используется два различных диапазона приоритетов. Первый — это параметр nice, который может принимать значения в диапазоне от -20 до 19, по умолчанию значение этого параметра равно 0. Большее значение параметра nice соответствует меньшему значению приоритета — необходимо быть более тактичным к другим процессам системы (nice — англ. тактичный, хороший). Процессы с меньшим значением параметра nice (большим значением приоритета) выполняются раньше процессов с большим значением nice (меньшим приоритетом). Значение параметра nice позволяет также определить, насколько продолжительный квант времени получит процесс. Процесс со значением параметра nice равным -20 получит квант времени самой большой длительности, в то время как процесс со значением параметра nice равным 19 получит наименьшее значение кванта времени. Использование параметра nice — это стандартный способ указания приоритетов процессов для всех Unix-подобных операционных систем.

Второй диапазон значений приоритетов— это приоритеты реального времени (real-time priority), которые будут рассмотрены ниже. По умолчанию диапазон значений этого параметра лежит от 0 до 99. Все процессы реального времени имеют более высокий приоритет по сравнению с обычными процессами. В операционной системе Linux приоритеты реального времени реализованы в соответствии со стандартом POSIX. В большинстве современных Unix-систем они реализованы по аналогичной схеме.

 

Квант времени

Квант времени (timeslice) — это численное значение, которое характеризует, как долго может выполняться задание до того момента, пока оно не будет вытеснено. Стратегия планирования должна устанавливать значение кванта времени, используемое по умолчанию, что является непростой задачей. Слишком большое значение кванта времени приведет к ухудшению интерактивной производительности системы— больше не будет впечатления, что процессы выполняются параллельно. Слишком малое значение кванта времени приведет к возрастанию накладных расходов на переключение между процессами, так как больший процент системного времени будет уходить на переключение с одного процесса с малым квантом времени на другой процесс с малым квантом времени. Более того, снова возникают противоречивые требования к процессам, ограниченным скоростью ввода-вывода и скоростью процессора. Процессам, ограниченным скоростью ввода-вывода, не требуется продолжительный квант времени, в то время как для процессов, ограниченных скоростью процессора, настоятельно требуется продолжительный квант времени, например, чтобы поддерживать кэши процессора в загруженном состоянии.

На основе этих аргументов можно сделать вывод, что любое большое значение кванта времени приведет к ухудшению интерактивной производительности. При реализации большинства операционных систем такой вывод принимается близко к сердцу и значение кванта времени, используемое по умолчанию, достаточно мало, например равно 20 мс. Однако в операционной системе Linux используется то преимущество, что процесс с самым высоким приоритетом всегда выполняется. Планировщик ядра Linux поднимает значение приоритета для интерактивных задач, что позволяет им выполняться более часто. Поэтому в ОС Linux планировщик использует достаточно большое значение кванта времени (рис 4.1). Более того, планировщик ядра Linux динамически определяет значение кванта времени процессов в зависимости от их приоритетов. Это позволяет процессам с более высоким приоритетом, которые считаются более важными, выполняться более часто и в течение большего периода времени. Использование динамического определения величины кванта времени и приоритетов позволяет обеспечить большую устойчивость и производительность планировщика.

Рис. 4.1. Вычисление кванта времени процесса

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

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

Когда истекает квант времени процесса, считается, что процесс потерял право выполняться. Процесс, у которого нет кванта времени, не имеет права выполняться до того момента, пока все другие процессы не используют свой квант времени. Когда это случится, то у всех процессов будет значение оставшегося кванта времени, равное нулю. В этот момент значения квантов времени для всех процессов пересчитываются. В планировщике ОС Linux используется интересный алгоритм для обработки ситуации, когда все процессы использовали свой квант времени. Этот алгоритм будет рассмотрен далее.

 

Вытеснение процесса

Как уже упоминалось, операционная система Linux использует вытесняющую многозадачность. Когда процесс переходит в состояние TASK_RUNNING, ядро проверяет значение приоритета этого процесса. Если это значение больше, чем приоритет процесса, который выполняется в данный момент, то активизируется планировщик, чтобы запустить новый процесс на выполнение (имеется в виду тот процесс, который только что стал готовым к выполнению). Дополнительно, когда квант времени процесса становится равным нулю, он вытесняется и планировщик готов к выбору нового процесса.

 

Стратегия планирования в действии

Рассмотрим систему с двумя готовыми к выполнению заданиями: программой для редактирования текстов и видеокодером. Программа для редактирования текстов ограничена скоростью ввода-вывода, потому что она тратит почти все свое время на ожидание ввода символов с клавиатуры пользователем (не имеет значение, с какой скоростью пользователь печатает, это не те скорости). Несмотря ни на что, при нажатии клавиши пользователь хочет, чтобы текстовый редактор отреагировал сразу же. В противоположность этому видеокодер ограничен скоростью процессора. Если не считать, что он время от времени считывает необработанные данные с диска и записывает результирующий видеоформат на диск, то кодер большую часть времени выполняет программу видеокодека для обработки данных, что легко загружает процессор на все 100%. Для этой программы нет строгих ограничений на время выполнения: пользователю не важно, запустится она на полсекунды раньше или на полсекунды позже. Конечно, чем раньше она завершит работу, тем лучше.

В такой системе планировщик установит для текстового редактора больший приоритет и выделит более продолжительный квант времени, чем для видеокодера, так как текстовый редактор — интерактивная программа. Для текстового редактора продолжительности кванта времени хватит с избытком. Более того, поскольку текстовый редактор имеет больший приоритет, он может вытеснить процесс видеокодера при необходимости. Это гарантирует, что программа текстового редактора будет немедленно реагировать на нажатия клавиш. Однако это не причинит никакого вреда и видеокодеру, так как программа текстового редактора работает с перерывами, и во время перерывов видеокодер может монопольно использовать систему. Все это позволяет оптимизировать производительность для обоих приложений.

 

В предыдущих разделах была рассмотрена в самых общих чертах теория работы планировщика процессов в операционной системе Linux. Теперь, когда мы разобрались с основами, можно более глубоко погрузиться в то, как именно работает планировщик ОС Linux.

Программный код планировщика операционной системы Linux содержится в файле kernel/sched.c. Алгоритм планирования и соответствующий программный код были существенно переработаны в те времена, когда началась разработка ядер серии 2.5. Следовательно, программный код планировщика является полностью новым и отличается от планировщиков предыдущих версий. Новый планировщик разрабатывался для того, чтобы удовлетворять указанным ниже требованиям.

• Должен быть реализован полноценный O(1)-планировщик. Любой алгоритм, использованный в новом планировщике, должен завершать свою работу за постоянный период времени, независимо от числа выполняющихся процессов и других обстоятельств.

• Должна обеспечиваться хорошая масштабируемость для SMP-систем. Каждый процессор должен иметь свои индивидуальные элементы блокировок и свою индивидуальную очередь выполнения.

• Должна быть реализована улучшенная SMP-привязка (SMP affinity). Задания, для выполнения на каждом процессоре многопроцессорной системы, должны быть распределены правильным образом, и, по возможности, выполнение этих задач должно продолжаться на одном и том же процессоре. Осуществлять миграцию заданий с одного процессора на другой необходимо только для уменьшения дисбаланса между размерами очередей выполнения всех процессоров.

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

• Должна быть обеспечена равнодоступность ресурсов (fairness). Ни один процесс не должен ощущать нехватку квантов времени за допустимый период. Кроме того, ни один процесс не должен получить недопустимо большое значение кванта времени.

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

Новый планировщик позволяет удовлетворить всем этим требованиям.

 

Очереди выполнения

Основная структура данных планировщика — это очередь выполнения (runqueue). Очередь выполнения определена в файле kernel/sched.c в виде структуры struct runqueue. Она представляет собой список готовых к выполнению процессов для данного процессора.

Для каждого процессора определяется своя очередь выполнения. Каждый готовый к выполнению процесс может находиться в одной и только в одной очереди выполнения. Кроме этого, очередь выполнения содержит информацию, необходимую для планирования выполнения на данном процессоре. Следовательно, очередь выполнения — это действительно основная структура данных планировщика для каждого процессора. Рассмотрим нашу структуру, описание которой приведено ниже. Комментарии объясняют назначения каждого поля.

struct runqueue {

 spinlock_t lock; /* спин-блокировка для зашиты этой очереди выполнения */

 unsigned long nr_running; /* количество задач, готовых к выполнению */

 unsigned long nr_switches; /* количество переключений контекста */

 unsigned long expired timestamp; /* время последнего обмена массивами */

 unsigned long nr_uninterruptible; /* количество заданий в состоянии

                                      непрерываемого ожидания */

 unsigned long long timestamp last tick; /* последняя метка времени

                                            планировщика */

 struct task_struct *curr; /* текущее задание, выполняемое на данном

                              процессоре */

 struct task_struct *idle; /* холостая задача данного процессора */

 struct mm_struct *prev_mm; /* поле mm_struct последнего выполняемого

                               задания */

 struct prio_array *active; /* указатель на активный массив приоритетов */

 struct prio_array *expired; /* указатель на истекший

                                массив приоритетов */

 struct prio_array arrays[2]; /* массивы приоритетов */

 struct task_struct *migration_thread; /* миграционный поток для

                                          данного процессора */

 struct list_head migration_queue; /* миграционная очередь для

                                      данного процессора */

 atomic_t nr_iowait; /* количество заданий, ожидающих на ввод-вывод */

};

Поскольку очередь выполнения — это основная структура данных планировщика, существует группа макросов, которые используются для доступа к определенным очередям выполнения. Макрос cpu_rq(processor) возвращает указатель на очередь выполнения, связанную с процессором, имеющим заданный номер. Аналогично макрос this_rq() возвращает указатель на очередь, связанную с текущим процессором. И наконец, макрос task_rq(task) возвращает указатель на очередь, в которой находится соответствующее задание.

Перед тем как производить манипуляции с очередью выполнения, ее необходимо заблокировать (блокировки подробно рассматриваются в главе 8, "Введение в синхронизацию выполнения кода ядра"). Так как очередь выполнения уникальна для каждого процессора, процессору редко необходимо блокировать очередь выполнения другого процессора (однако, как будет показано далее, такое все же иногда случается). Блокировка очереди выполнения позволяет запретить внесение любых изменений в структуру данных очереди, пока процессор, удерживающий блокировку, выполняет операции чтения или записи полей этой структуры. Наиболее часто встречается ситуация, когда необходимо заблокировать очередь выполнения, в которой выполняется текущее задание. В этом случае используются функции task_rq_lock() и task_rq_unlock(), как показано ниже.

struct runqueue *rq;

unsigned long flags;

rq = task_rq_lock(task, &flags);

/* здесь можно производить манипуляции с очередью выполнения */

task_rq_unlock(rq, flags);

Альтернативными функциями выступают функция this_rq_lock(), которая позволяет заблокировать текущую очередь выполнения, и функция rq_unlock(struct runqueue *rq), позволяющая разблокировать указанную в аргументе очередь.

Для предотвращения взаимных блокировок код, который захватывает блокировки нескольких очередей, всегда должен захватывать блокировки в одном и том же порядке, а именно в порядке увеличения значения адреса памяти очереди (в главе 8, "Введение в синхронизацию выполнения кода ядра", приведено полное описание). Пример, как это осуществить, показан ниже.

/* для того, чтобы заблокировать ... */

if (rq1 < rq2) (

 spin_lock(&rq1->lock);

 spin_lock(&rq2->lock);

} else (

 spin_lock(&rq2->lock);

 spin_lock(&rq1->lock);

}

/* здесь можно манипулировать обеими очередями ... */

/* для того, чтобы разблокировать ... */

spin_unlock(&rq1->lock);

spin_unlock(&rq2->lock);

С помощью функций double_rq_lock() и double_rq_unlock() указанные шаги можно выполнить автоматически. При этом получаем следующее.

double_rq_lock(rq1, rq2);

/* здесь можно манипулировать обеими очередями ...*/

double_rq_unlock(rq1, rq2);

Рассмотрим небольшой пример, который показывает, почему важен порядок захвата блокировок. Вопрос взаимных блокировок обсуждается в главах 8, "Введение в синхронизацию выполнения кода ядра" и 9, "Средства синхронизации в ядре". Эта проблема касается не только очередей выполнения: вложенные блокировки должны всегда захватываться в одном и том же порядке. Спин-блокировки используются для предотвращения манипуляций с очередями выполнения несколькими задачами одновременно. Принцип работы этих блокировок аналогичен ключу, с помощью которого открывают дверь. Первое задание, которое подошло к двери, захватывает ключ, входит в дверь и закрывает ее с другой стороны. Если другое задание подходит к двери и определяет, что дверь закрыта (потому что за дверью находится первое задание), то оно должно остановиться и подождать, пока первое задание на выйдет и не возвратит ключ. Ожидание называется спиннингом (вращением, spinning), так как на самом деле задание постоянно выполняет цикл, периодически проверяя, не возвращен ли ключ. Теперь рассмотрим, что будет, если одно задание пытается сначала заблокировать первую очередь выполнения, а затем вторую, в то время как другое задание пытается сначала заблокировать вторую очередь, а затем — первую. Допустим, что первое задание успешно захватило блокировку первой очереди, в то время как второе задание захватило блокировку второй очереди. После этого первое задание пытается заблокировать вторую очередь, а второе задание — первую. Ни одно из заданий никогда не добьется успеха, так как другое задание уже захватило эту блокировку. Оба задания будут ожидать друг друга вечно. Так же как в тупике дороги создается блокировка движения, так и неправильный порядок захвата блокировок приводит к тому, что задания начинают ожидать друг друга вечно, и тоже возникает тупиковая ситуация, которая еще называется взаимоблокировкой. Если оба задания захватывают блокировки в одном и том же порядке, то рассмотренной ситуации произойти не может. В главах 8 и 9 представлено полное описание блокировок.

 

Массивы приоритетов

Каждая очередь выполнения содержит два массива приоритетов (priority arrays): активный и истекший. Массивы приоритетов определены в файле kernel/sched.c в виде описания struct prio_array. Массивы приоритетов — это структуры данных, которые обеспечивают O(1)-планирование. Каждый массив приоритетов содержит для каждого значения приоритета одну очередь процессов, готовых к выполнению. Массив приоритетов также содержит битовую маску приоритетов (priority bitmap), используемую для эффективного поиска готового к выполнению задания, у которого значение приоритета является наибольшим в системе.

 struct prio_array {

 int nr_active;                     /* количество заданий */

 unsigned long bitmap[BITMAP_SIZE]; /* битовая маска приоритетов */

 struct list_head queue[MAX_PRIO];  /* очереди приоритетов */

};

Константа MAX_PRIO — это количество уровней приоритета в системе. По умолчанию значение этой константы равно 140. Таким образом, для каждого значения приоритета выделена одна структура struct list_head. Константа BITMAP_SIZE — это размер массива переменных, каждый элемент которого имеет тип unsigned long. Каждый бит этого массива соответствует одному действительному значению приоритета. В случае 140 уровней приоритетов и при использовании 32-разрядных машинных слов, значение константы BITMAP_SIZE равно 5. Таким образом, поле bitmap — это массив из пяти элементов, который имеет длину 160 бит.

Все массивы приоритетов содержат поле bitmap, каждый бит этого поля соответствует одному значению приоритета в системе. В самом начале значения всех битов равны 0. Когда задача с определенным приоритетом становится готовой к выполнению (то есть значение статуса этой задачи становится равным TASK_RUNNING), соответствующий этому приоритету бит поля bitmap устанавливается в значение 1. Например, если задача с приоритетом, равным 7, готова к выполнению, то устанавливается бит номер 7. Нахождение задания с самым высоким приоритетом в системе сводится только лишь к нахождению самого первого установленного бита в битовой маске. Так как количество приоритетов неизменно, то время, которое необходимо затратить на эту операцию поиска, постоянно и не зависит от количества процессов, выполняющихся в системе. Более того, для каждой поддерживаемой аппаратной платформы в ОС Linux должен быть реализован быстрый алгоритм поиска первого установленного бита (find first set) для проведения быстрого поиска в битовой маске. Эта функция называется sched_find_first_bit(). Для многих аппаратных платформ существует машинная инструкция нахождения первого установленного бита в заданном машинном слове. Для таких систем нахождение первого установленного бита является тривиальной операций и сводится к выполнению этой инструкции несколько раз.

Каждый массив приоритетов также содержит массив очередей, представленных структурами struct list_head. Этот массив называется queue. Каждому значению приоритета соответствует своя очередь. Очереди реализованы в виде связанных списков, и каждому значению приоритета соответствует список всех процессов системы, готовых к выполнению, имеющих это значение приоритета и находящихся в очереди выполнения данного процессора. Нахождение задания, которое будет выполняться следующим, является простой задачей и сводится к выбору следующего элемента из списка. Все задания с одинаковым приоритетом планируются на выполнение циклически.

Массив приоритетов также содержит счетчик nr_active, значение которого соответствует количеству готовых к выполнению заданий в данном массиве приоритетов.

 

Пересчет квантов времени

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

Обычно это реализуется с помощью цикла по всем задачам в системе, например, следующим образом.

for (каждого задания в системе) (

 пересчитать значение приоритета

 пересчитать значение кванта времени

}

Значение приоритета и другие атрибуты задачи используются для определения нового значения кванта времени. Такой подход имеет некоторые проблемы.

• Пересчет потенциально может занять много времени. Хуже того, время такого расчета масштабируется как О(n), где n — количество задач в системе.

• Во время пересчета должен быть использован какой-нибудь тип блокировки для защиты списка задач и отдельных дескрипторов процессов. В результате получается высокий уровень конфликтов при захвате блокировок.

• Отсутствие определенности в случайно возникающих пересчетах значений квантов времени является проблемой для программ реального времени.

• Откровенно говоря, это просто нехорошо (что является вполне оправданной причиной для каких-либо усовершенствований ядра Linux).

Новый планировщик ОС Linux позволяет избежать использования цикла пересчета приоритетов. Вместо этого в нем применяется два массива приоритетов для каждого процессора: активный (active) и истекший (expired). Активный массив приоритетов содержит очередь, в которую включены все задания соответствующей очереди выполнения, для которых еще не иссяк квант времени. Истекший массив приоритетов содержит все задания соответствующей очереди, которые израсходовали свой квант времени. Когда значение кванта времени для какого-либо задания становится равным нулю, то перед тем, как поместить это задание в истекший массив приоритетов, для него вычисляется новое значение кванта времени. Пересчет значений кванта времени для всех процессов проводится с помощью перестановки активного и истекшего массивов местами. Так как на массивы ссылаются с помощью указателей, то переключение между ними будет выполняться так же быстро, как и перестановка двух указателей местами. Показанный ниже код выполняется в функции schedule().

struct prio_array array = rq->active;

if (!array->nr_active) {

 rq->active = rq->expired;

 rq->expired = array;

}

Упомянутая перестановка и есть ключевым, моментом O(1)-планировщика. Вместо того чтобы все время пересчитывать значение приоритета и кванта времени для каждого процесса, O(1)-планировщик выполняет простую двухшаговую перестановку массивов. Такая реализация позволяет решить указанные выше проблемы.

Функция schedule()

Все действия по выбору следующего задания на исполнение и переключение на выполнение этого задания реализованы в виде функции schedule(). Эта функция вызывается явно кодом ядра при переходе в приостановленное состояние (sleep), a также в случае когда какое-либо задание вытесняется. Функция schedule() выполняется независимо каждым процессором. Следовательно, каждый процессор самостоятельно принимает решение о том, какой процесс выполнять следующим.

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

struct task_struct *prev, *next;

struct list_head *queue;

struct prio_array *array;

int idx;

prev = current;

array = rq->active;

idx = sched_find_first_bit(array->bitmap);

queue = array->queue + idx;

next = list_entry(queue->next, struct task struct, run_list);

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

Рис. 4.2. Алгоритм работы О(1)-планировщика операционной системы Linux

Если полученные значения переменных prev и next не равны друг другу, то для выполнения выбирается новое задание (next). При этом для переключения с задания, на которое указывает переменная prev, на задание, соответствующее переменной next, вызывается функция context_switch(), зависящая от аппаратной платформы. Переключение контекста будет рассмотрено в одном из следующих разделов.

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

 

Вычисление приоритетов и квантов времени

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

Процессы имеют начальное значение приоритета, которое называется nice. Это значение может лежать в диапазоне от -20 до 19, по умолчанию используется значение 0. Значение 19 соответствует наиболее низкому приоритету, а значение -20 — наиболее высокому. Значение параметра nice хранится в поле static_prio структуры task_struct процесса. Это значение называется статическим приоритетом, потому что оно не изменяется планировщиком и остается таким, каким его указал пользователь. Планировщик свои решения основывает на динамическом приоритете, которое хранится в поле prio. Динамический приоритет вычисляется как функция статического приоритета и интерактивности задания.

Функция effective_prio() возвращает значение динамического приоритета задачи. Эта функция исходит из значения параметра nice для данной задачи и вычисляет для этого значения надбавку или штраф в диапазоне от -5 до 5, в зависимости от интерактивности задачи. Например, задание с высокой интерактивностью, которое имеет значение параметра nice, равное 10, может иметь динамический приоритет, равный 5. И наоборот, программа со значением параметра nice, равным 10, которая достаточно активно использует процессор, может иметь динамический приоритет, равный 12. Задачи, которые обладают умеренной интерактивностью, не получают ни надбавки, ни штрафа, и их динамический приоритет совпадает со значением параметра nice.

Конечно, планировщик по волшебству не может определить, какой процесс является интерактивным. Для определения необходима некоторая эвристика, которая отражает, является ли процесс ограниченным скоростью ввода-вывода или скоростью процессора. Наиболее выразительный показатель — сколько времени задача находится в приостановленном состоянии (sleep). Если задача проводит большую часть времени в приостановленном состоянии, то она ограничена вводом-выводом. Если задача больше времени находится в состоянии готовности к выполнению, чем в приостановленном состоянии, то эта задача не интерактивна. В экстремальных случаях, если задача большую часть времени находится в приостановленном состоянии, то она полностью ограничена скоростью ввода-вывода; если задача все время готова к выполнению, то она ограничена скоростью процессора.

Для реализации такой эвристики в ядре Linux предусмотрен изменяемый показатель того, как соотносится время, которое процесс проводит в приостановленном состоянии, со временем, которое процесс проводит в состоянии готовности к выполнению. Значение этого показателя хранится в поле sleep_avg структуры task_struct. Диапазон значений этого показателя лежит от нуля до значения MAXSLEEP_AVG, которое по умолчанию равно 10 мс. Когда задача становится готовой к выполнению после приостановленного состояния, значение поля sleep_avg увеличивается на значение времени, которое процесс провел в приостановленном состоянии, пока значение sleep_avg не достигнет MAXSLEEP_AVG. Когда задача выполняется, то в течение каждого импульса таймера (timer tick) значение этой переменной уменьшается, пока оно не достигнет значения 0.

Такой показатель является, на удивление, надежным. Он рассчитывается не только на основании того, как долго задача находится в приостановленном состоянии, но и на основании того, насколько мало задача выполняется. Таким образом, задача, которая проводит много времени в приостановленном состоянии и в то же время постоянно использует свой квант времени, не получит большой прибавки к приоритету: показатель работает не только для поощрения интерактивных задач, но и для наказания задач, ограниченных скоростью процессора. Этот показатель также устойчив по отношению к злоупотреблениям. Задача, которая получает повышенное значение приоритета и большое значение кванта времени, быстро утратит свою надбавку к приоритету, если она постоянно выполняется и сильно загружает процессор. В конце концов, такой показатель обеспечивает малое время реакции. Только что созданный интерактивный процесс быстро достигнет высокого значения поля sleep_avg. Несмотря на все сказанное, надбавка и штраф применяются к значению параметра nice, так что пользователь также может влиять на работу системного планировщика путем изменения значения параметра nice процесса.

Расчет значения кванта времени, наоборот, более прост, так как значение динамического приоритета уже базируется на значении параметра nice и на интерактивности (эти показатели планировщик учитывает как наиболее важные). Поэтому продолжительность кванта времени может быть просто выражена через значение динамического приоритета. Когда создается новый процесс, порожденный и родительский процессы делят пополам оставшуюся часть кванта времени родительского процесса. Такой подход обеспечивает равнодоступность ресурсов и предотвращает возможность получения бесконечного значения кванта времени путем постоянного создания порожденных процессов. Однако после того, как квант времени задачи иссякает, это значение пересчитывается на основании динамического приоритета задачи. Функция task_timeslice() возвращает новое значение кванта времени для данного задания. Расчет просто сводится к масштабированию значения приоритета в диапазон значений квантов времени. Чем больше значение приоритета задачи, тем большей продолжительности квант времени получит задание в текущем цикле выполнения. Максимальное значение кванта времени равно MAX_TIMESLICE, которое по умолчанию равно 200 мс. Даже задания с самым низким приоритетом получают квант времени продолжительностью MIN_TIMESLICE, что соответствует 10 мс. Задачи с приоритетом, используемым по умолчанию (значение параметра nice, равно 0 и отсутствует надбавка и штраф за интерактивность), получают квант времени продолжительностью 100 мс, как показано в табл. 4.1.

Таблица 4.1. Продолжительности квантов времени планировщика

Для интерактивных задач планировщик оказывает дополнительную услугу: если задание достаточно интерактивно, то при исчерпании своего кванта времени оно будет помещено не в истекший массив приоритетов, а обратно в активный массив приоритетов. Следует вспомнить, что пересчет значений квантов времени производится путем перестановки активного и истекшего массивов приоритетов: активный массив становится истекшим, а истекший — активным. Такая процедура обеспечивает пересчет значений квантов времени, который масштабируется по времени как O(1). С другой стороны, это может привести к тому, что интерактивное задание станет готовым к выполнению, но не получит возможности выполняться, так как оно "застряло" в истекшем массиве. Помещение интерактивных заданий снова в активный массив позволяет избежать такой проблемы. Следует заметить, что это задание не будет выполняться сразу же, а будет запланировано на выполнение по кругу вместе с другими заданиями, которые имеют такой же приоритет. Данную логику реализует функция scheduler_tick(), которая вызывается обработчиком прерываний таймера (обсуждается в главе 10, "Таймеры и управление временем"), как показано ниже.

struct task_struct *task = current;

struct runqueue *rq = this_rq();

if (!--task->time_slice) {

 if (!TASK_INTERACTIVE(task) || EXPIRED_STARVING(rq))

  enqueue_task(task, rq->expired);

 else

  enqueue_task(task, rq->active);

}

Показанный код уменьшает значение кванта времени процесса и проверяет, не стало ли это значение равным нулю. Если стало, то задание является истекшим и его необходимо поместить в один из массивов. Для этого код вначале проверяет интерактивность задания с помощью макроса TASK_INTERACTIVE(). Этот макрос на основании значения параметра nice рассчитывает, является ли задание "достаточно интерактивным". Чем меньше значение nice (чем выше приоритет), тем менее интерактивным должно быть задание. Задание со значением параметра nice, равным 19, никогда не может быть достаточно интерактивным для помещения обратно в активный массив. Наоборот, задание со значением nice, равным -20, должно очень сильно использовать процессор, чтобы его не поместили в активный массив. Задача со значением nice, используемым по умолчанию, т.е. равным нулю, должна быть достаточно интерактивной, чтобы быть помещенной обратно в активный массив, но это также отрабатывается достаточно четко. Следующий макрос, EXPIRED_STARVING(), проверяет, нет ли в истекшем массиве процессов, особенно нуждающихся в выполнении (starving), когда массивы не переключались в течение достаточно долгого времени. Если массивы давно не переключались, то обратное помещение задачи в активный массив еще больше задержит переключение, что приведет к тому, что задачи в истекшем массиве еще больше будут нуждаться в выполнении. Если это не так, то задача может быть помещена обратно в активный массив. В других случаях задача помещается в истекший массив, что встречается наиболее часто.

 

Переход в приостановленное состояние и возврат к выполнению

Приостановленное состояние задачи (состояние ожидания, заблокированное состояние, sleeping, blocked) представляет собой специальное состояние задачи, в котором задание не выполняется. Это является очень важным, так как в противном случае планировщик выбирал бы на выполнение задания, которые не "хотят" выполняться, или, хуже того, состояние ожидания должно было бы быть реализовано в виде цикла, занимающего время процессора. Задачи могут переходить в приостановленное состояние по нескольким причинам, но в любом случае— в ожидании наступления некоторого события. Событием может быть ожидание наступления некоторого момента времени, ожидание следующей порции данных при файловом вводе-выводе или другое событие в аппаратном обеспечении. Задача также может переходить в приостановленное состояние непроизвольным образом, когда она пытается захватить семафор в режиме ядра (эта ситуация рассмотрена в главе 9, "Средства синхронизации в ядре"). Обычная причина перехода в приостановленное состояние — это выполнение операций файлового ввода-вывода, например задание вызывает функцию read() для файла, который необходимо считать с диска. Еще один пример— задача может ожидать на ввод данных с клавиатуры. В любом случае ядро ведет себя одинаково: задача помечает себя как находящуюся в приостановленном состоянии, помещает себя в очередь ожидания (wail queue), удаляет себя из очереди выполнения и вызывает функцию schedule() для выбора нового процесса на выполнение. Возврат к выполнению (wake up) происходит в обратном порядке: задача помечает себя как готовую к выполнению, удаляет себя из очереди ожидания и помещает себя в очередь выполнения.

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

Приостановленное состояние обрабатывается с помощью очередей ожидания (wait queue). Очередь ожидания — это просто список процессов, которые ожидают наступления некоторого события. Очереди ожидания в ядре представляются с помощью типа данных wait_queue_head_t. Они могут быть созданы статически с помощью макроса DECLARE_WAIT_QUEUE_HEAD() или выделены динамически с последующей инициализацией с помощью функции init_waitqueue_head(). Процессы помещают себя в очередь ожидания и устанавливают себя в приостановленное состояние. Когда происходит событие, связанное с очередью ожидания, процессы, находящиеся в этой очереди, возвращаются к выполнению. Важно реализовать переход в приостановленное состояние и возврат к выполнению правильно, так чтобы избежать конкуренции за ресурсы (race).

Существуют простые интерфейсы для перехода в приостановленное состояние, и они широко используются. Однако использование этих интерфейсов может привести к состояниям конкуренции: возможен переход в приостановленное состояние после того, как соответствующее событие уже произошло. В таком случае задача может находиться в приостановленном состоянии неопределенное время. Поэтому рекомендуется следующий метод для перехода в приостановленное состояние в режиме ядра.

/* пусть q — это очередь ожидания (созданная в другом месте) ,

где мы хотим находиться в приостановленном состоянии */

DECLARE_WAITQUEUE(wait, current);

add_wait_queue(q, &wait);

set_current_state(TASK_INTERRUPTIBLE); /* или TASK_UNINTERRUPTIBLE */

/* переменная condition характеризует наступление события,

   которого мы ожидаем */

while (!condition)

 schedule();

set_current_state(TASK_RUNNING);

remove_wait_queue(q, &wait);

Опишем шаги, которые должна проделать задача для того, чтобы поместить себя в очередь ожидания.

• Создать элемент очереди ожидания с помощью макроса DECLARE_WAITQUEUE().

• Добавить себя в очередь ожидания с помощью функции add_wait_queue(). С помощью этой очереди ожидания процесс будет возвращен в состояние готовности к выполнению, когда условие, на выполнение которого ожидает процесс, будет выполнено. Конечно, для этого где-то в другом месте должен быть код, который вызывает функцию wake_up() для данной очереди, когда произойдет соответствующее событие.

• Изменить состояние процесса в значение TASK_INTERRUPTIBLE или TASK_UNINTERRUPTIBLE.

• Проверить, не выполнилось ли ожидаемое условие. Если выполнилось, то больше нет необходимости переходить в приостановленное состояние. Если нет, то вызвать функцию schedule().

• Когда задача становится готовой к выполнению, она снова проверяет выполнение ожидаемого условия. Если условие выполнено, то производится выход из цикла. Если нет, то снова вызывается функция schedule() и повторяется проверка условия.

• Когда условие выполнено, задача может установить свое состояние в значение TASK_RUNNING и удалить себя из очереди ожидания с помощью функции remove_wait_queue().

Если условие выполнится перед тем, как задача переходит в приостановленное состояние, то цикл прервется и задача не перейдет в приостановленное состояние по ошибке. Следует заметить, что во время выполнения тела цикла код ядра часто может выполнять и другие задачи. Например, перед выполнением функции schedule() может возникнуть необходимость освободить некоторые блокировки и захватить их снова после возврата из этой функции; если процессу был доставлен сигнал, то необходимо возвратить значение -ERESTARTSYS; может возникнуть необходимость отреагировать на некоторые другие события.

Возврат к выполнению (wake up) производится с помощью функции wake_up(), которая возвращает все задачи, ожидающие в данной очереди, в состояние готовности к выполнению. Вначале вызывается функция try_to_wake_up(), которая устанавливает поле состояния задачи в значение TASK_RUNNING, далее вызывается функция activate_task() для добавления задачи в очередь выполнения и устанавливается флаг need_resched в ненулевое значение, если приоритет задачи, которая возвращается к выполнению, больше приоритета текущей задачи. Код, который отвечает за наступление некоторого события, обычно вызывает функцию wake_up() после того, как это событие произошло. Например, после того как данные прочитаны с жесткого диска, подсистема VFS вызывает функцию wake_up() для очереди ожидания, которая содержит все процессы, ожидающие поступления данных.

Важным может быть замечание о том, что переход в приостановленное состояние часто сопровождается ложными переходами к выполнению. Это возникает потому, что переход задачи в состояние выполнения не означает, что событие, которого ожидала задача, уже наступило: поэтому переход в приостановленное состояние должен всегда выполняться в цикле, который гарантирует, что условие, на которое ожидает задача, действительно выполнилось (рис. 4.3).

Рис. 4.3. Переход в приостановленное состояние (sleeping) и возврат к выполнению (wake up)

 

Балансировка нагрузки

Как уже рассказывалось ранее, планировщик операционной системы Linux реализует отдельные очереди выполнения и блокировки для каждого процессора в симметричной многопроцессорной системе. Это означает, что каждый процессор поддерживает свой список процессов и выполняет алгоритм планирования только для заданий из этого списка. Система планирования, таким образом, является уникальной для каждого процессора. Тогда каким же образом планировщик обеспечивает какую-либо глобальную стратегию планирования для многопроцессорных систем? Что будет, если нарушится балансировка очередей выполнения, скажем, в очереди выполнения одного процессора будет находиться пять процессов, а в очереди другого — всего один? Решение этой проблемы выполняется системой балансировки нагрузки, которая работает с целью гарантировать, что все очереди выполнения будут сбалансированными. Система балансировки нагрузки сравнивает очередь выполнения текущего процессора с другими очередями выполнения в системе.

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

Система балансировки нагрузки реализована в файле kernel/sched.c в виде функции load_balance(). Эта функция вызывается в двух случаях. Она вызывается функцией schedule(), когда текущая очередь выполнения пуста. Она также вызывается по таймеру с периодом в 1 мс, когда система не загружена, и каждые 200 мс в другом случае. В однопроцессорной системе функция load_balance() не вызывается никогда, в действительности она даже не компилируется в исполняемый образ ядра, питому что в системе только одна очередь выполнения и никакой балансировки не нужно.

Функция балансировки нагрузки вызывается при заблокированной очереди выполнения текущего процессора, прерывания при этом также запрещены, чтобы защитить очередь выполнения от конкурирующего доступа. В том случае, когда функция load_balance() вызывается из функции schedule(), цель ее вызова вполне ясна, потому что текущая очередь выполнения пуста и нахождение процессов в других очередях с последующим их проталкиванием в текущую очередь позволяет получить преимущества. Когда система балансировки нагрузки активизируется посредством таймера, то ее задача может быть не так очевидна. В данном случае это необходимо для устранения любого дисбаланса между очередями выполнения, чтобы поддерживать их в почти одинаковом состоянии, как показано на рис. 4.4.

Рис. 4.4. Система балансировки нагрузки

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

• Функция load_balance() вызывает функцию find_busiest_queue() для определения наиболее загруженной очереди выполнения. Другими словами — очередь с наибольшим количеством процессов в ней. Если нет очереди выполнения, количество процессов в которой на 25% больше, чем в дайной очереди, то функция find_busiest_queue() возвращает значение NULL и происходит возврат из функции load_balance(). В другом случае возвращается указатель на самую загруженную очередь.

• Функция load_balance() принимает решение о том, из какого массива приоритетов самой загруженной очереди будут проталкиваться процессы. Истекший массив является более предпочтительным, так как содержащиеся в нем задачи не выполнялись достаточно долгое время и, скорее всего, не находятся в кэше процессора (т.е. не активны в кэше, not "cache hot"). Если истекший массив приоритетов пуст, то ничего не остается, как использовать активный массив.

• Функция load_balance() находит непустой список заданий, соответствующий самому высокому приоритету (с самым маленьким номером), так как важно более равномерно распределять задания с высоким приоритетом, чем с низким.

• Каждое задание с данным приоритетом анализируется для определения задания, которое не выполняется, не запрещено для миграции из-за процессорной привязки и не активно в кэше. Если найдена задача, которая удовлетворяет этому критерию, то вызывается функция pull_task() для проталкивания этой задачи из наиболее загруженной очереди в данную очередь.

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

Далее показана функция load_balance(), немного упрощенная, но содержащая все важные детали.

static int load_balance(int this_cpu, runqueue_t *this_rq,

 struct sched_domain *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(&busiest->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;

out_balanced:

 spin_unlock(&this_rq->lock);

 if (sd->balance_interval < sd->max_interval)

  sd->balance_interval *= 2;

 return 0;

}

 

Переключение контекста — это переключение от одной, готовой к выполнению задачи к другой. Это переключение производится с помощью функции context_switch(), определенной в файле kernel/sched.c. Данная функция вызывается функцией schedule(), когда новый процесс выбирается для выполнения. При этом выполняются следующие шаги.

• Вызывается функция switch_mm(), которая определена в файле include/asm/mmu_context.h и предназначена для переключения от виртуальной памяти старого процесса к виртуальной памяти нового процесса.

• Вызывается функция switch_to(), определенная в файле include/asm/system.h, для переключения от состояния процессора предыдущего процесса к состоянию процессора нового процесса. Эта процедура включает восстановление информации стека ядра и регистров процессора.

Ядро должно иметь информацию о том, когда вызывать функцию schedule(). Если эта функция будет вызываться только тогда, когда программный код вызывает ее явно, то пользовательские программы могут выполняться неопределенное время. Поэтому ядро поддерживает флаг need_resched для того, чтобы сигнализировать, необходимо ли вызывать функцию schedule() (табл. 4.2). Этот флаг устанавливается функцией scheduler_tick(), когда процесс истрачивает свой квант времени, и функцией try_to_wake_up(), когда процесс с приоритетом более высоким, чем у текущего процесса, возвращается к выполнению. Ядро проверяет значение этого флага, и если он установлен, то вызывается функция schedule() для переключения на новый процесс. Этот флаг является сообщением ядру о том, что планировщик должен быть активизирован по возможности раньше, потому что другой процесс должен начать выполнение.

Таблица 4.2. Функции для управления флагом need_resched

Во время переключения в пространство пользователи или при возврате из прерывания, значение флага 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 стало преемптивным: теперь есть возможность вытеснить задание в любой момент, конечно, пока ядро находится в состоянии, когда безопасно производить перепланирование выполнения.

В таком случае когда же безопасно производить перепланирование? Ядро способно вытеснить задание, работающее в пространстве ядра, когда это задание не удерживает блокировку. Иными словами, блокировки используются в качестве маркеров тех областей, в которые задание не может быть вытеснено. Ядро рассчитано на многопроцессорность (SMP-safe), поэтому если блокировка не удерживается, то код ядра является реентерабельным и его вытеснять безопасно.

Первое изменение, внесенное для поддержки вытеснения пространства ядра, — это введение счетчика преемптивности preempt_count в структуру thread_info каждого процесса. Значение этого счетчика вначале равно нулю и увеличивается на единицу при каждом захвате блокировки, а также уменьшается на единицу при каждом освобождении блокировки. Когда значение счетчика равно нулю— ядро является вытесняемым. При возврате из обработчика прерывания, если возврат выполняется в пространство ядра, ядро проверяет значения переменных need_resched и preempt_count. Если флаг need_resched установлен и значение счетчика preempt_count равно нулю, значит, более важное задание готово к выполнению и выполнять вытеснение безопасно. Далее активизируется планировщик. Если значение счетчика preempt_count не равно нулю, значит, удерживается захваченная блокировка и выполнять вытеснение не безопасно. В таком случае возврат из обработчика прерывания происходит в текущее выполняющееся задание. Когда освобождаются все блокировки, удерживаемые текущим заданием, значение счетчика preempt_count становится равным нулю. При этом код, осуществляющий освобождение блокировки, проверяет, не установлен ли флаг need_resched. Если установлен, то активизируется планировщик. Иногда коду ядра необходимо иметь возможность запрещать или разрешать вытеснение в режиме ядра, что будет рассмотрено в главе 9.

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

Вытеснение пространства ядра может произойти в следующих случаях.

• При возврате из обработчика прерывания в пространство ядра.

• Когда код ядра снова становится преемптивным.

• Если задача, работающая в режиме ядра, явно вызывает функцию schedule().

• Если задача, работающая в режиме ядра, переходит в приостановленное состояние, т.е. блокируется (что приводит к вызову функции schedule()).

 

Операционная система Linux предоставляет семейство системных вызовов для управления параметрами планировщика. Эти системные вызовы позволяют манипулировать приоритетом процесса, стратегией планирования и процессорной привязкой, а также предоставляют механизм, с помощью которого можно явно передать процессор (yield) в использование другим заданиям.

Существуют различные книги, а также дружественные страницы системного руководства (man pages), которые предоставляют информацию об этих системных вызовах (реализованных в библиотеке С без особых интерфейсных оболочек, а прямым вызовом системной функции). В табл. 4.3 приведен список этих функций с кратким описанием. О том, как системные вызовы реализованы в ядре, рассказывается в главе 5, "Системные вызовы".

Таблица 4.3. Системные вызовы для управления планировщиком

 

Системные вызовы, связанные с управлением стратегией и приоритетом

Системные вызовы sched_setscheduler() и sched_getcheduler() позволяют соответственно установить и получить значение стратегии планирования и приоритета реального времени для указанного процесса. Реализация этих функций, так же как и для большинства остальных системных вызовов, включает большое количество разнообразных проверок, инициализаций и очистку значений аргументов. Полезная работа включает в себя только чтение или запись полей policy и rt_priority структуры task_struct указанного процесса.

Системные вызовы sched_setparam() и sched_getparam() позволяют установить и получить значение приоритета реального времени для указанного процесса. Последняя функция просто возвращает значение поля rt_priority, инкапсулированное в специальную структуру sched_param. Вызовы sched_get_priority_max() и sched_get_priority_min() возвращают соответственно максимальное и минимальное значение приоритета реального времени для указанной стратегии планирования. Максимальное значение приоритета для стратегий планирования реального времени равно (MAX_USER_RT_PRIO-1), а минимальное значение — 1.

Для обычных задач функция nice() увеличивает значение статического приоритета вызывающего процесса на указанную в аргументе величину. Только пользователь root может указывать отрицательные значения, т.е. уменьшать значение параметра nice и соответственно увеличивать приоритет. Функция nice() вызывает функцию ядра set_user_nice(), которая устанавливает значение полей static_prio и prio структуры task_struct.

 

Системные вызовы управления процессорной привязкой

Планировщик ОС Linux может обеспечивать жесткую процессорную привязку (processor affinity). Хотя планировщик пытается обеспечивать мягкую или естественную привязку путем удержания процессов на одном и том же процессоре, он также позволяет пользователям сказать: "Эти задания должны выполняться только на указанных процессорах независимо ни от чего". Значение жесткой привязки хранится в виде битовой маски в поле cpus_allowed структуры task_struct. Эта битовая маска содержит один бит для каждого возможного процессора в системе. По умолчанию все биты установлены в значение 1, и поэтому процесс потенциально может выполняться на всех процессорах в системе. Пользователь с помощью функции sched_setaffinity() может указать другую битовую маску с любой комбинацией установленных битов. Аналогично функция sched_getaffinity() возвращает текущее значение битовой маски cpus_allowed.

Ядро обеспечивает жесткую привязку очень простым способом. Во-первых, только что созданный процесс наследует маску привязки от родительского процесса. Поскольку родительский процесс выполняется на дозволенном процессоре, то и порожденный процесс также будет выполняться на дозволенном процессоре. Во-вторых, когда привязка процесса изменяется, ядро использует миграционные потоки (migration threads) для проталкивания задания на дозволенный процессор. Следовательно, процесс всегда выполняется только на том процессоре, которому соответствует установленный бит в поле cpus_allowed дескриптора процесса.

 

Передача процессорного времени

Операционная система Linux предоставляет системный вызов sched_yield() как механизм, благодаря которому процесс может явно передать процессор под управление другим ожидающим процессам. Этот вызов работает путем удаления процесса из активного массива приоритетов (где он в данный момент находится, потому что процесс выполняется) с последующим помещением этого процесса в истекший массив. Получаемый аффект состоит не только в том, что процесс вытесняется и становится последним в списке заданий с соответствующим приоритетом, а также в том, что помещение процесса в истекший массив гарантирует, что этот процесс не будет выполняться некоторое время. Так как задачи реального времени никогда не могут быть помещены в истекший массив, они составляют специальный случай. Поэтому они только перемещаются в конец списка заданий с таким же значением приоритета (и не помещаются в истекший массив). В более ранних версиях ОС. Linux семантика вызова sched_yield() была несколько иной. В лучшем случае задание только лишь перемещалось в конец списка заданий с данным приоритетом. Сегодня для пользовательских программ и даже для потоков пространства ядра должна быть полная уверенность в том, что действительно необходимо отказаться от использования процессора, перед тем как ввязывать функцию sched_yield().

В коде ядра, для удобства, можно вызывать функцию yield(), которая проверяет, что состояние задачи равно TASK_RUNNING, а после этого вызывает функцию sched_yield(). Пользовательские программы должны использовать системный вызов sched_yield().