Главная » Ядро Linux » Алгоритм планирования – ЧАСТЬ 2

0

struct prio_array (

int nr_active;                  /* количество заданий */ unsigned long bitmap[BITMAP_SIZE]; /* битовая маска приоритетов */ struct list head queue[MAX_PRIO];/* очереди приоритетов */

};

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

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

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

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

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

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

4 Для аппаратной  платформы х86 используется  инструкция  bsfl,  а для  платформ ы  РРС — инструкци я     cntlzw.

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

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)-планировщика. Вместо того  чтобы  все  время  пересчитывать значение приоритета и кванта  времени для каждого   процесса, О(1)-планировщик выполняет простую  двухшаговую  перестановку массивов. Такая  реализация позволяет решить указанные выше проблемы.

Функция schedule ()

Все действия по выбору  следующего задания на исполнение и переключение на выполнение этого задания реализованы в виде функции schedul e () . Эта функция вызывается явно кодом  ядра при  переходе  в приостановленное состояние (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_ist);

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

schedule()

Бит 0 приоритет 0

sched_find_first_set()

Бит 7 приоритет 7

Список всех готовых к выполнению задач а соответствии

с их приоритетами

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

длиной 140 бит             Бит 139 приоритет 139

Запуск первого процесса в списке

Список готовых

к выполнению заданий, имеющих приоритет 7

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

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

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

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

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

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

Источник: Лав,  Роберт. Разработка ядра  Linux, 2-е  издание. : Пер.  с англ.  — М.  : ООО  «И.Д.  Вильяме» 2006. — 448 с. : ил. — Парал. тит. англ.

По теме:

  • Комментарии