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

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

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

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

Следующая глава >

Похожие главы из других книг

ТЕМА НОМЕРА: Кванты ради квантов

Из книги Журнал «Компьютерра» № 23 от 20 июня 2006 года автора Журнал «Компьютерра»

ТЕМА НОМЕРА: Кванты ради квантов Автор: Леонид Левкович-МаслюкОдин из самых захватывающих сюжетов современной физики — попытки нащупать пути построения квантового компьютера (КК). Погоня за довольно призрачной целью сводит воедино трудносовместимые вещи. С одной


Машина времени

Из книги Журнал `Компьютерра` N740 автора Журнал «Компьютерра»

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


Линейка времени

Из книги Запись CD и DVD: профессиональный подход автора Бахур Виктор

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


Знаки времени

Из книги Журнал "Компьютерра" №711 автора Журнал «Компьютерра»

Знаки времени Автор: Киви БердНа закате правления госадминистрации Клинтона один из видных деятелей ИТ-индустрии, глава Sun Microsystems Скотт Макнили сделал, помнится, весьма сильное публичное заявление, которым многие были просто шокированы. Речь шла о роли технологий в


1.6.13. Правило экономии: время программиста стоит дорого; поэтому экономия его времени более приоритетна по сравнению с экономией машинного времени

Из книги Искусство программирования для Unix автора Реймонд Эрик Стивен

1.6.13. Правило экономии: время программиста стоит дорого; поэтому экономия его времени более приоритетна по сравнению с экономией машинного времени "В ранние мини-компьютерные времена Unix" вынесенная в заголовок идея была довольно радикальной (машины тогда работали


1.6.13. Правило экономии: время программиста стоит дорого; поэтому экономия его времени более приоритетна по сравнению с экономией машинного времени

Из книги Искусство программирования для Unix автора Реймонд Эрик Стивен

1.6.13. Правило экономии: время программиста стоит дорого; поэтому экономия его времени более приоритетна по сравнению с экономией машинного времени "В ранние мини-компьютерные времена Unix" вынесенная в заголовок идея была довольно радикальной (машины тогда работали


18.1.1. Представление времени

Из книги Разработка приложений в среде Linux. Второе издание автора Джонсон Майкл К.

18.1.1. Представление времени В системах Unix и Linux время отслеживается в секундах до или после начала эпохи, которое определяется как полночь 1 января 1970 года по UTC[148]. Положительные значения времени относятся к периоду после начала эпохи; отрицательные — до начала эпохи. Для


Интервал времени

Из книги Firebird РУКОВОДСТВО РАЗРАБОТЧИКА БАЗ ДАННЫХ автора Борри Хелен

Интервал времени Ошибочно предполагать, что тип TIME может хранить интервал времени. Он не может. Для вычисления интервала времени вычтите более позднюю дату или время из более раннего. Результатом будет число NUMERIC(18,9), выражающее интервал в днях. Поскольку точность


Течение времени

Из книги Новый ум короля [О компьютерах, мышлении и законах физики] автора Пенроуз Роджер


Настройка времени

Из книги Офисный компьютер для женщин автора Пастернак Евгения

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


12.1. Ограничения по времени

Из книги Установка, настройка и восстановление Windows 7 на 100% автора Ватаманюк Александр Иванович

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


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

Из книги Разработка ядра Linux автора Лав Роберт

Квант времени Квант времени (timeslice[20]) — это численное значение, которое характеризует, как долго может выполняться задание до того момента, пока оно не будет вытеснено. Стратегия планирования должна устанавливать значение кванта времени, используемое по умолчанию, что


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

Из книги Как приручить компьютер за несколько часов автора Ремнева Ирина

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


Немного времени

Из книги автора

Немного времени Игра «О счастливчик»Игрок: Прошу убрать два неверных варианта.Ведущий: Итак, дорогой компьютер, уберите, пожалуйста, два неверных варианта.Надпись на мониторах: «Программа выполнила недопустимую ошибку и будет закрыта».Ведущий: Что ж, по просьбе компании