СИСТЕМА И СПОСОБ ПЛАНИРОВАНИЯ АКТИВНЫХ ЗАДАНИЙ В ОПЕРАЦИОННОЙ СИСТЕМЕ Российский патент 2011 года по МПК G06F9/46 

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

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

В многозадачном ядре каждое готовое для выполнения задание представлено потоком (thread). Операционные системы (ОС) классифицируют потоки на «ограниченные возможностями процессора» и «ограниченные устройствами ввода-вывода». «Ограниченные возможностями процессора» потоки долгое время используют процессор для выполнения вычислений, а «ограниченные устройствами ввода-вывода» тратят много времени на ожидание завершения относительно медленных операций ввода-вывода. Для оптимальной производительности планировщики дают потокам, «ограниченным устройствами ввода-вывода», приоритетный доступ к центральному процессору.

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

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

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

Известен способ микропланирования (патент US 6779181) [1], примененный в ядре операционной системы для поддержки мультимедийных приложений, который содержит этапы определения параметра производительности путем измерения производительности задания, «ограниченного устройством ввода-вывода», и задания, «ограниченного возможностями процессора» в данном приложении, и соответствующего изменения параметра производительности в соответствии с политикой, установленной системным администратором, при контроле допуска выполнения задания. В данном способе определяют порядок приоритета дня обработки классов приложения на основе измерения производительности и контроля допуска выполнения задания путем планирования периодического выполнения заданий ввода-вывода данных, которые не должны перемещаться в пространство пользователя, согласно параметрам мультимедийных приложений, и выполнения специальных системных вызовов ввода-вывода в соответствии с порядком приоритета для обработки. Способ микропланирования позволяет поддерживать правильное качество и класс предоставляемых услуг передачи данных для любой операционной системы, которая поддерживает мультимедийные приложения.

В патенте US 5247677 [2] приведен стохастический планировщик заданий на основе приоритета для выбора выполняемых заданий в вычислительной системе. Данный планировщик на основе стохастического приоритета выбирает задания согласно случайному номеру с весом приоритета задания. Поскольку каждое задание имеет ненулевую ограниченную вероятность быть выбранным, вероятность пропорциональна приоритету задания, все задания, даже имеющие низкий приоритет, имеют шанс быть выбранными, таким образом устраняется проблема блокировки.

Наиболее близки к заявленному изобретению система и способ динамической настройки квантовой величины планирования потока, описанные в заявке US 2005/024923 [3], в которых оптимизируют планирование выполнения потоков путем получения объектных данных каждого потока, которые содержат требуемую рабочую характеристику, точки замера образцов рабочих характеристик, причем каждая точка замера меняется согласно функции квантовой величины планирования, и вычисляют новую квантовую величину планирования путем обработки данных в точках замера образцов рабочих характеристик в соответствии с рабочей характеристикой. Диспетчер процессов настраивает квантовую величину планирования для повышения производительности потока за счет использования вычисленной квантовой величины планирования. Данные система и способ выбраны в качестве прототипа заявляемого изобретения.

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

Задачей заявляемого изобретения является создание более динамичной и эффективной системы и способа планирования активных заданий в операционной системе.

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

сбора списка активных заданий в операционной системе для предварительно исследованного периода времени;

вычисления и нормализации фактического времени выполнения текущего активного задания, в том числе за счет уменьшения временных затрат контекстных переключателей;

сортировки списка активных заданий по величине фактического времени выполнения;

назначения статических приоритетов записанных активных заданий в восходящем порядке в соответствии с возрастающей величиной фактического времени выполнения.

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

собирают список активных заданий в операционной системе для предварительно исследованного периода времени;

вычисляют и нормализуют фактическое время выполнения текущего активного задания, в том числе за счет уменьшения временных затрат контекстных переключателей;

сортируют список активных заданий по величине фактического времени выполнения;

назначают статические приоритеты записанных активных заданий в восходящем порядке в соответствии с возрастающей величиной фактического времени выполнения.

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

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

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

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

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

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

Для лучшего понимания заявленного изобретения далее приводится его подробное описание с привлечением графических материалов.

Фиг.1. Блок-схема системы планирования активных заданий в операционной системе согласно изобретению. Элементы:

1 - аппаратная платформа;

2 - пространство пользователя;

3 - группа целевых приложений, запущенных в пространстве пользователя;

4 - пространство ядра;

5 - планировщик;

6 - модуль B для автоматического управления приоритетом;

7 - модуль A для динамической инструментации.

Фиг.2. Схема реорганизации активных заданий по фактическому времени выполнения в планировщике согласно изобретению.

Фиг.3. Блок-схема способа планирования активных заданий в операционной системе согласно изобретению.

Фиг.4. Схема планировщика ОС Linux в структуре очереди готовых к выполнению программ до и после выполнения способа планирования активных заданий в операционной системе согласно изобретению.

Рассмотрим более подробно вариант выполнения заявленного изобретения (Фиг.1-3). Сущность заявленного изобретения заключается в использовании модуля 7 ядра (модуль A), выполненного с возможностью осуществления динамической инструментации, и модуля 6 ядра (модуль B), выполненного с возможностью автоматического назначения статических приоритетов для активных заданий.

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

Модуль 6 ядра выполняет основные операции для автоматического пересчета и назначения приоритета для активных пользовательских заданий, на основании информации, полученной в результате работы модуля 7 ядра.

Модуль 6 ядра определяет период наблюдения для сбора характеристик активных заданий, по истечении которого значения статических приоритетов для активных пользовательских задач будут пересчитаны. Таким образом, модуль 6 ядра проверяет, истек ли период наблюдения со времени последнего пересчета приоритетов или нет. Если да, то модуль 6 ядра получает характеристики для всех активных заданий и вычисляет фактическое время использование процессора этими заданиями за период наблюдения.

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

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

Поэтому заявляемое изобретение позволяет значительно увеличить производительность приложений при их запуске в ОС, например в ОС Linux.

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

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

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

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