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

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

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

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

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

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

Определение приоритетов

Из книги Время - деньги. Создание команды разработчиков программного обеспечения автора Салливан Эд


Массивы

Из книги Delphi. Учимся на примерах автора Парижский Сергей Михайлович

Массивы Массив — это упорядоченная именованная совокупность однотипных значений, к которым можно обращаться по их порядковому номеру (индексу). Для описания массивов в языке Object Pascal используют следующие формы:• array [1..N1] of type — одномерный массив фиксированного размера


NetFront Browser 4.0: смена приоритетов  Андрей Крупин

Из книги Цифровой журнал «Компьютерра» № 5 [26.1.2010 — 2.2.2010] автора Журнал «Компьютерра»

NetFront Browser 4.0: смена приоритетов  Андрей Крупин Прошедший 2009 год, богатый событиями на рынке программного обеспечения, многим запомнился гонкой производительности браузеров для настольных платформ. В наступившем году состязание за звание лидера, несомненно, продолжится,


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

Из книги Основы AS/400 автора Солтис Фрэнк

Динамическое планирование приоритетов В предыдущих разделах мы рассмотрели более понятную, но упрощенную модель диспетчеризации задач в AS/400. Со времен первой System/38 в структуру задач было внесено множество изменений для удовлетворения требований различных приложений и


Дмитрий Плесконос: Развитие Интернета — один из приоритетов

Из книги Цифровой журнал «Компьютерра» № 12 [17.3.2010 — 24.3.2010] автора Журнал «Компьютерра»

Дмитрий Плесконос: Развитие Интернета — один из приоритетов Исполнительный вице-президент ОАО «Вымпелком» по развитию бизнеса на массовом рынке Дмитрий Плесконос ответил на вопросы читателей «Компьютерры» о доступе в Интернет, предоставляемом под брендом


Дмитрий Плесконос: Развитие Интернета - один из приоритетов

Из книги Компьютерра PDA 20.03.2010-26.03.2010 автора Журнал «Компьютерра»

Дмитрий Плесконос: Развитие Интернета - один из приоритетов Автор: Опубликовано 22 марта 2010 годаИсполнительный вице-президент ОАО «Вымпелком» по развитию бизнеса на массовом рынке Дмитрий Плесконос ответил на вопросы читателей "Компьютерры" о доступе в Интернет,


Предостережение относительно использования приоритетов потоков и процессов

Из книги Системное программирование в среде Windows автора Харт Джонсон М

Предостережение относительно использования приоритетов потоков и процессов Высокими приоритетами потоков и высокими классами приоритета процессов необходимо пользоваться с осторожностью. Следует решительно избегать использования приоритетов реального времени для


8 Расстановка приоритетов

Из книги Тайм-менеджмент для системных администраторов автора Лимончелли Томас

8 Расстановка приоритетов В этой главе описывается процесс расстановки приоритетов «снизу вверх». Вначале я уточню то, чего поверхностно коснулся в главе 5, - расстановка приоритетов в сегодняшнем списке дел. Затем я собираюсь обсудить приоритеты более крупных проектов.


Расстановка приоритетов в списке дел

Из книги Фундаментальные алгоритмы и структуры данных в Delphi автора Бакнелл Джулиан М.

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


Массивы

Из книги QNX/UNIX [Анатомия параллелизма] автора Цилюрик Олег Иванович

Массивы Предположим, что у нас имеется отсортированный массив. Как было показано ранее, алгоритм последовательного поиска даже при использовании выхода из цикла в случае отсутствия в списке искомого элемента принадлежит к классу O(n). Каким образом можно улучшить


Определение протокола защиты от инверсии приоритетов

Из книги Введение в QNX/Neutrino 2. Руководство по программированию приложений реального времени в QNX Realtime Platform автора Кёртен Роб

Определение протокола защиты от инверсии приоритетов int pthread_mutexattr_setprotocol( pthread_mutexattr_t* attr, int protocol);int pthread_mutexattr_getprotocol( pthread_mutexattr_t* attr, int* protocol);Эти функции устанавливают/считывают протокол, который реализуется мьютексом для защиты от инверсии приоритетов. Переменная protocol


Наследование приоритетов

Из книги Linux программирование в примерах автора Роббинс Арнольд

Наследование приоритетов Одним из интересных моментов в операционных системах реального времени является феномен инверсии приоритетов.Инверсия приоритетов наблюдается, например, в случае, когда поток с низким приоритетом потребляет все процессорное время, в то время


3. МАССИВЫ

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

3. МАССИВЫ Массив - это группа переменных одного типа, доступ к которым осуществляется с помощью общего имени. Для объявления типа массива используются квадратные скобки. В приведенной ниже строке объявляется переменная month_days, тип которой — «массив целых чисел типа int».int


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

Из книги Идеальный программист. Как стать профессионалом разработки ПО автора Мартин Роберт С.

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


Инверсия приоритетов

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

Инверсия приоритетов Независимо от причины мы всегда находим способы избежать выполнения работы. Мы убеждаем себя, что у вас есть более срочная задача, и занимаемся ей. Это называется инверсией приоритетов: вы искусственно повышаете приоритет задачи, чтобы отложить