/* для того, чтобы заблокировать ... */
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(). Для многих аппаратных платформ существует машинная инструкция нахождения первого установленного бита в заданном машинном слове[22]. Для таких систем нахождение первого установленного бита является тривиальной операций и сводится к выполнению этой инструкции несколько раз.
Каждый массив приоритетов также содержит массив очередей, представленных структурами struct list_head. Этот массив называется queue. Каждому значению приоритета соответствует своя очередь. Очереди реализованы в виде связанных списков, и каждому значению приоритета соответствует список всех процессов системы, готовых к выполнению, имеющих это значение приоритета и находящихся в очереди выполнения данного процессора. Нахождение задания, которое будет выполняться следующим, является простой задачей и сводится к выбору следующего элемента из списка. Все задания с одинаковым приоритетом планируются на выполнение циклически.
Массив приоритетов также содержит счетчик nr_active, значение которого соответствует количеству готовых к выполнению заданий в данном массиве приоритетов.
Пересчет квантов времени
Во многих операционных системах (включая и более старые версии ОС Linux) используется прямой метод для пересчета значения кванта времени каждого задания, когда все эти значения достигают нуля.
Обычно это реализуется с помощью цикла по всем задачам в системе, например, следующим образом.
for (каждого задания в системе) (
пересчитать значение приоритета
пересчитать значение кванта времени
}
Значение приоритета и другие атрибуты задачи используются для определения нового значения кванта времени. Такой подход имеет некоторые проблемы.
• Пересчет потенциально может занять много времени. Хуже того, время такого расчета масштабируется как О(n), где n — количество задач в системе.
22
Для аппаратной платформы x86 используется инструкция bsfl, а для платформы PPC — инструкция cntlzw.