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



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

 


Владельцы патента RU 2420792:

Корпорация "САМСУНГ ЭЛЕКТРОНИКС Ко., Лтд." (KR)

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

 

Изобретение относится к области вычислительной техники, а именно к системам и способам планирования активных заданий в операционной системе, и может применяться в цифровых вычислительных машинах, в которых несколько заданий предназначены дня выполнения одним или более процессором, в многозадачных операционных системах (ОС) со статическим назначением приоритетов в политике планирования, таких как ОС 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.

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

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

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



 

Похожие патенты:

Изобретение относится к области создания заданий обработки данных конечным пользователем. .

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

Изобретение относится к системе управления связью между поставщиком и запросчиком в распределенной сети. .

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

Изобретение относится к компьютерам, в частности к системам и способам обнаружения и взаимодействия со службами. .

Изобретение относится к средствам поиска требуемой информации и контента, а именно к устройствам, в которых реализована функция поискового посредника между множеством приложений и множеством поисковых функций.

Изобретение относится к средствам слежения за арендой времени или подписки предоставляемой вычислительной системы. .

Изобретение относится к многопоточным системам и, более конкретно, к способу и устройству формирования очереди потоков

Изобретение относится к вычислительной технике

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

Изобретение относится к средствам управления виртуальными машинами

Изобретение относится к способу управления объектами приложений

Изобретение относится к области обмена данными между генератором и потребителем

Изобретение относится к области распределенных вычислений. Техническим результатом является обеспечение распределенной вычислительной мощности больших масштабов. Стоимость выполнения сложных анализов финансовых трендов с использованием программного обеспечения существенно снижается путем распределения вычислительной мощности, необходимой для выполнения анализа и вычислительной задачи, между большим числом сетевых отдельных или сгруппированных вычислительных узлов. Для этого вычислительная задача разделяется на множество подзадач. Каждая подзадача выполняется одним из устройств обработки информации для получения множества решений. Затем решения объединяются для получения решения вычислительной задачи. Лицам, под контролем которых находятся устройства обработки информации, выдается вознаграждение за использование ассоциированных с ними устройств обработки информации. Может обеспечиваться возможность изменения алгоритмов во времени. После этого осуществляется выбор одного или нескольких измененных алгоритмов в соответствии с заданным условием. 3 н. и 14 з.п. ф-лы, 4 ил.

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

Изобретение относится к области обработки хеш-таблиц. Техническим результатом является параллельное выполнение изменения размеров и выполняемого по требованию для каждого адресуемого сегмента повторного хеширования для одновременно обрабатываемой хеш-таблицы, которая представляет собой совместно используемое запоминающее устройство, доступ к которому осуществляется одним или больше потоками, которые могут выполнять одно или больше ядер многопроцессорной системы, такой как система, имеющая один или больше многоядерных процессоров. Раскрывается способ для выделения второго количества сегментов для хеш-таблицы, совместно одновременно используемой множеством потоков, где второе количество сегментов логически отображают на соответствующий родительский сегмент первого количества сегментов, и публикуют обновленную емкость хеш-таблицы для завершения выделения без выполнения какого-либо повторного хеширования, таким образом, что повторное хеширование может быть выполнено позже по требованию для каждого сегмента. 3 н. и 17 з.п. ф-лы, 6 ил., 4 табл.

Изобретение относится к способу и системе реализации физического устройства для дифференцирования между множеством виртуальных машин (VM) компьютерной системы. Технический результат изобретения заключается в реализации физического устройства для дифференциации между множеством VM системы хост-компьютера. Дифференцирование VM может быть выполнено в отношении управления конфигурацией и/или трафика данных, основываясь на идентификаторах конкретных VM (VM ID). VM ID могут быть идентифицированы в пределах хост-заголовков программных интерфейсов приложений (API) входящего управления конфигурацией и пакетов данных и/или их можно искать на основе адресов MAC, зависящих от VM, связанных с пакетами данных. Идентификаторы VM могут быть вставлены в заголовки API исходящего управления и/или пакетов данных, чтобы позволить системе хост-компьютера направлять управление и/или пакеты соответствующим VM. Идентификаторы VM могут использоваться для поиска параметров конфигурации, зависящих от VM, и информации о соединении, чтобы переконфигурировать физическое устройство на основе каждой VM. 3 н. и 17 з.п. ф-лы, 11 ил.
Наверх