Наборы планируемых заданий в планировщике

Наборы планируемых заданий в планировщике

Иллюстрации

Показать все

Реферат

Уровень техники

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

Сущность изобретения

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

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

Краткое описание чертежей

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

Фиг.1 - блок-схема, иллюстрирующая вариант осуществления планировщика с наборами планируемых заданий в рабочей среде.

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

Фиг.3А-3В - схема и таблица, иллюстрирующие вариант осуществления преобразования наборов планируемых заданий.

Фиг.4 - схема последовательности операций, иллюстрирующая вариант осуществления способа выбора заданий для выполнения.

Фиг.5А-5В - блок-схемы, иллюстрирующие варианты осуществления наборов планируемых заданий.

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

Подробное описание

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

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

Фиг.1 - блок-схема, иллюстрирующая вариант осуществления планировщика контекста выполнения 22 в процессе 12 рабочей среды 10. Планировщик 22 содержит совокупность наборов планируемых заданий 40(1)-40(L), где L - целое число, которое больше или равно двум и обозначает L-й набор планируемых заданий 40. Каждый набор планируемых заданий 40(1)-40(L) соответствует соответствующему узлу планирования 30(1)-30(L).

Рабочая среда 10 представляет собой режим выполнения программ в вычислительной системе, такой как варианты осуществления 100А и 100В вычислительной системы 100, изображенной на Фиг.6А и 6В и описанной ниже более подробно, в котором вычислительная система выполняет команды. Вычислительная система формирует рабочую среду 10 из платформы выполнения, такой как платформа выполнения 122, изображенная на Фиг.6А и описанная ниже более подробно.

Рабочая среда 10 включает, по меньшей мере, один вызываемый процесс 12, уровень управления ресурсами 14 и совокупность аппаратных потоков 16(1)-16(М), где М - целое число, которое больше или равно двум и обозначает М-й аппаратный поток 16. Рабочая среда 10 позволяет осуществлять выполнение заданий процесса 12 вместе с заданиями других процессов, которые существуют одновременно с процессом 12 (не показан), с помощью уровня управления ресурсами 14 и совокупности аппаратных потоков 16(1)-16(М). Рабочая среда 10 функционирует во взаимодействии с уровнем управления ресурсами 14, чтобы процесс 12 мог получить ресурсы процессора и прочие ресурсы вычислительной системы (например, аппаратные потоки 16(1)-16(М)).

Рабочая среда 10 включает в себя функцию планировщика, которая формирует планировщик 22. В одном варианте осуществления функция планировщика реализована в виде прикладного программного интерфейса (API) планировщика. В другом варианте осуществления функция планировщика может быть реализована с помощью других подходящих программных структур. При вызове функция планировщика создает планировщик 22 в процессе 12, при этом планировщик 22 производит операции по планированию заданий процесса 12 для выполнения одним или более аппаратных потоков 16(1)-16(М). Рабочая среда 10 может использовать мелкомодульный параллелизм, который разработки приложений или библиотек отражают в своих программах (например, процесс 12) с помощью сопутствующих инструментальных средств, которые знают о возможностях, обеспечиваемых функцией планировщика.

Процесс 12 включает распределение ресурсов обработки и прочих ресурсов, которые ведут один или более контекстов выполнения (а именно, потоков). Процесс 12 получает доступ к обработке и прочим ресурсам вычислительной системы (например, к аппаратным потокам 16(1)-16(М)) от уровня управления ресурсами 14. Процесс 12 обеспечивает выполнение заданий с помощью ресурсов обработки и прочих ресурсов.

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

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

Уровень управления ресурсами 14 выделяет ресурсы обработки на процесс 12 путем выделения одного или более аппаратных потоков 16 на процесс 12. Уровень управления ресурсами 14 существует отдельно от операционной системы вычислительной системы (на Фиг.1 не показана) в изображенном на Фиг.1 варианте осуществления. В других вариантах осуществления уровень управления ресурсами 14 либо некоторые или все их функции могут входить в операционную систему.

Аппаратные потоки 16 находятся в исполнительных модулях совокупности либо одного, либо более блоков процессора (например, блоков процессоров 102, показанных на Фиг.6 и описанных ниже более подробно) вычислительной системы. Каждый аппаратный поток 16 настроен на выполнение команд независимо или практически независимо от других исполнительных модулей и включает в себя состояние машины. Аппаратные потоки 16 могут входить в один блок процессора или могут быть распределены по множеству блоков процессоров. Каждый исполнительный модуль в блоке процессора может содержать один или более аппаратных потоков 16.

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

Планировщик 22 взаимодействует с уровнем управления ресурсами 14 для согласования ресурсов вычислительной системы способом, прозрачным для процесса 12. Уровень управления ресурсами 14 выделяет аппаратные потоки 16 планировщику 22 исходя из спроса и предложения и любых политик планировщика 22.

В изображенном на Фиг.1 варианте осуществления планировщик 22 осуществляет управление ресурсами обработки путем создания виртуальных процессоров 32, образующих абстракцию нижележащих аппаратных потоков 16. Планировщик 22 мультиплексирует виртуальные процессоры 32 в аппаратные потоки 16 путем преобразования каждого виртуального процессора 32 в аппаратный поток 16. Планировщик 22 может осуществлять преобразование более одного виртуального процессора 32 в отдельный аппаратный поток 16, однако преобразует только один аппаратный поток 16 в каждый виртуальный процессор 32. В других вариантах осуществления планировщик 22 управляет ресурсами обработки другими подходящими способами для обеспечения выполнения команд процесса 12 аппаратными потоками 16.

Рабочая среда 10 создает планировщик 22 с информацией о лежащей в его основе топологии вычислительной системы. Рабочая среда 10 выдает на уровень управления ресурсами 14 и/или планировщик 22 информацию об узле вычислительной системы. Информация об узле выявляет аппаратные узлы вычислительной системы непосредственно либо включает достаточную информацию о топологии вычислительной системы, чтобы уровень управления ресурсами 14 и/или планировщик 22 могли осуществлять разбиение аппаратных ресурсов на узлы планирования 30 на основе одного или более показателей выполнения. Показатели выполнения могут содержать скорость, тип и/или конфигурацию ресурсов обработки (например, аппаратных потоков 16), ресурсы памяти и/или прочие ресурсы вычислительной системы.

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

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

Рабочая среда 10 обеспечивает включение планировщиком 22 совокупности двух или более узлов планирования 30(1)-30(L) на основе информации об узлах. Каждый узел планирования 30 включает выделенные ресурсы обработки в виде виртуальных процессоров 32 и аппаратных потоков 16. Узел планирования 30(1) включает виртуальные процессоры 30(1)-30(N _l), которые преобразуются в аппаратные потоки 16(1)-16(m _l), где N _l - целое число, которое больше или равно единице и означает (N _l)-й виртуальный процессор 30, а m _l - меньше или равно М и означает (m _l)-й аппаратный поток 16. Узел планирования 30(L) включает виртуальные процессоры 30(l)-30(N _L), которые преобразуются в аппаратные потоки 16(m _m)-16(M), где N _L - целое число, которое больше или равно единице и означает (N _L)-й виртуальный процессор 30, а m _m - меньше или равно М и больше m _l и означает (m _m)-й аппаратный поток 16.

Планировщик 22 создает набор планируемых заданий 40 для каждого узла планирования 30. В соответствии с этим наборы планируемых заданий 40(1)-40(L) должны соответствовать соответствующим узлам планирования 30(1)-30(L), как показано стрелками 37(1)-37(L). Планировщик 22 преобразует наборы планируемых заданий 40 в очередность полного или частичного поиска на основе одного или более показателей выполнения и использует указанную очередность поиска для поиска заданий для выполнения при освобождении ресурсов обработки, как будет описано ниже более подробно.

Совокупность контекстов выполнения в планировщике 22 содержит совокупность контекстов выполнения 34 с соответствующими связанными с ними заданиями 36, которые выполняются соответствующими виртуальными процессорами 32 в каждом узле планирования 30, а в каждом наборе планируемых заданий 40 - совокупность нуля или более готовых к выполнению контекстов выполнения 38 и совокупность нуля или более заблокированных (т.е. зависимых от ожидания) контекстов выполнения 40. Каждый контекст выполнения 34, 38 и 40 содержит информацию о состоянии, которая указывает на то, является ли контекст ожидания 34, 38 и 40 выполняющимся, готовым к выполнению (например, в ответ на разблокирование или добавление в планировщик 22) или заблокированным. Контексты выполнения 34, которые являются выполняющимися, присоединены к виртуальному процессору 32 и в настоящее время выполняются. Контексты выполнения 38, которые являются готовыми к выполнению, содержат сопряженное задание 39 и готовы к выполнению свободным виртуальным процессором 32. Контексты выполнения 40, которые заблокированы, содержат сопряженное задание 41 и ожидают данные, сообщение или событие, которое сформировано или будет сформировано другим контекстом выполнения 34, 38 или 40.

Каждый контекст выполнения 24, выполняющийся на виртуальном процессоре 32, в процессе своего выполнения может формировать дополнительные задания 42, которые организуются любым целесообразным способом (например, добавляются к очередям работ (на Фиг.1 не показаны)). Работа может быть создана путем использования либо прикладного программного интерфейса (API), обеспечиваемого рабочей средой 10, либо функций языка программирования и соответствующих средств в одном варианте осуществления. При освобождении ресурсов обработки для планировщика 22 задания назначаются контекстам выполнения 34 или 38, которые выполняют их до завершения на виртуальных процессорах 32 перед выбором новых заданий. Контекст выполнения 34, выполняющийся на виртуальном процессоре 32, может также разблокировать другие контексты выполнения 40 путем формирования данных, сообщения или события, которое будет использоваться другим контекстом выполнения 40.

Каждое задание в планировщике 22 может быть выполнено (например, выполненные задания 36 и 39), что указывает на то, что контекст выполнения 34 или 38 был или будет присоединен к заданию и задание готово к выполнению. Выполненные задания, как правило, содержат разблокированные контексты выполнения и запланированные агенты. Задание, которое не выполнено, называется невыполненным. Невыполненные задания (например, задания 42) могут формироваться в виде порожденных заданий, генерируемых путем выполнения порождающих заданий и могут генерироваться параллельными структурами (например, parallel, parallel for, begin и finish). Каждый набор планируемых заданий 40 в планировщике 22 может быть организован в один или более синхронизированных наборов (например, стек и/или очередь) для логически независимых заданий с контекстами выполнения (т.е., выполненными заданиями) вместе со списком разбросанных очередей для зависимых заданий (т.е., невыполненных заданий), как показано в изображенном на Фиг.5А варианте осуществления, описанном ниже.

После завершения, блокирования или иного прерывания (например, явного возврата или принудительного прерывания обслуживания) контекста выполнения 34, запущенного на виртуальном процессоре 32, виртуальный процессор 32 освобождается для выполнения другого выполненного задания 39 или невыполненного задания 42. Планировщик 22 ищет готовый к выполнению контекст выполнения 38 или невыполненное задание 42 для присоединения к свободному виртуальному процессору 32 с целью выполнения. Планировщик 22 продолжает присоединение контекстов выполнения 38 к свободным виртуальным процессорам 32 с целью выполнения до тех пор, пока не будут выполнены все контексты выполнения 38 планировщика 22.

При освобождении виртуального процессора 32 в узле планирования 30 виртуальный процессор 32 пытается локализовать задание для выполнения в наборе планируемых заданий 40, соответствующем узлу планирования 30. Если виртуальный процессор 32 не локализует задание для выполнения в наборе планируемых заданий 40, виртуальный процессор 32 пытается локализовать задание для выполнения в других наборах планируемых заданий 40 в очередности, задаваемой очередностью поиска. В одном варианте осуществления планировщик 22 может содержать регулируемый параметр задержки, который обеспечивает задержку свободными виртуальными процессорами 32 поиска других наборов планируемых заданий 40, чтобы попытаться минимизировать конкуренцию с другими свободными виртуальными процессорами 32. Параметр задержки может также использоваться для приоритезации поиска работы для набора планируемых заданий 40, соответствующего узлу планирования 30 свободного виртуального процессора 32.

Фиг.2 - схема последовательности операций, иллюстрирующая вариант осуществления способа создания и заполнения наборов планируемых заданий 40 в планировщике 22. Изображенный на Фиг.2 способ будет описан со ссылкой на вариант осуществления планировщика 22 на Фиг.1.

На Фиг.2 рабочая среда 10 и/или уровень управления ресурсами 14 выявляет узлы планирования 30 на основе одного или более показателей выполнения в соответствии с блоком 52. Показатели выполнения могут представлять собой любые подходящие меры выполнения команд в вычислительной системе и могут включать следующие характеристики обработки и других ресурсов вычислительной системы: быстродействие, пропускная способность и время задержки памяти. С помощью показателей выполнения, определенных для различных совокупностей компонентов вычислительной системы, рабочая среда 10 и/или уровень управления ресурсами 14 разбивает обработку и другие ресурсы вычислительной системы и использует разбиения для выявления узлов планирования 30 для планировщика 22. Каждый из узлов планирования 30 содержит группы одинаковых или различных совокупностей ресурсов обработки и других ресурсов вычислительной системы.

В одном примере вычислительная система может содержать процессоры, которые включают в себя множество аппаратных потоков 16. В этом примере рабочая среда 10 и/или уровень управления ресурсами 14 могут разбивать каждый блок процессора на отдельные узлы и создавать узел планирования 30 для каждого узла.

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

В другом примере рабочая среда 10 и/или уровень управления ресурсами 14 могут разбивать произвольные или частично произвольные совокупности ресурсов процессора в вычислительной системе на узлы и создавать узел планирования 30 для каждого узла.

В еще одном примере рабочая среда 10 и/или уровень управления ресурсами 14 могут разбивать ресурсы обработки различных типов или скоростей на узлы, при этом каждый узел содержит некоторое количество ресурсов обработки одного и того же типа или скорости. Рабочая среда 10 и/или уровень управления ресурсами 14 создают узел планирования 30 для каждого узла.

В соответствии с блоком 54 рабочая среда 10, уровень управления ресурсами 14 и/или планировщик 22 создают соответствующий набор планируемых заданий 40 для каждого узла планирования 30. Как показано на Фиг.1, планировщик 22 создает наборы планируемых заданий 40(1)-40(L), которые соответствуют соответствующим узлам планирования 30(1)-30(L). Каждый набор планируемых заданий 40 образует в памяти вычислительной системы структуру данных для хранения заданий, при этом указанная структура данных доступна для поиска виртуальными процессорами 32 из соответствующего узла планирования 30 и виртуальными процессорами 32 из других узлов планирования 30.

В соответствии с блоком 56 рабочая среда 10, уровень управления ресурсами 14 и/или планировщик 22 преобразует наборы планируемых заданий 40(1)-40(L) в очередность полного или частичного поиска на основе одного или более показателей выполнения. Планировщик 22 использует эти показатели выполнения для сравнения расходов на выполнение между различными узлами планирования 30. Расходы на выполнение могут быть описаны с точки зрения межузловых расстояний, при этом различные межузловые расстояния отражают разные характеристики выполнения между данным узлом планирования 30 и другими узлами планирования 30. По межузловым расстояниям узлы планирования 30 с более низкими расходами на выполнение относительно данного узла планирования 30 описываются как расположенные ближе к данному узлу планирования 30, а узлы планирования 30 с более высокими расходами на выполнение относительно данного узла планирования 30 описываются как расположенные дальше от данного узла планирования 30. В одном варианте осуществления планировщик 22 преобразует наборы планируемых заданий 40(1)-40(L) в очередность полного или частичного поиска с помощью межузловых расстояний.

Для создания очередности поиска планировщик 22 группирует совокупности наборов планируемых заданий 40 в подсовокупности одного или более наборов планируемых заданий 40 на основе межузловых расстояний. Каждый набор планируемых заданий 40 имеет нулевое межузловое расстояние от соответствующего узла планирования 30. В соответствии с этим каждый набор планируемых заданий 40 образует подсовокупность планируемых заданий 40 первого уровня (например, подсовокупность 0-го уровня) для соответствующего узла планирования 30. Для подсовокупности наборов планируемых заданий 40 следующего уровня (например, подсовокупности 1-го уровня) планировщик 22 группирует совокупность одного или более наборов планируемых заданий 40 с наименьшим диапазоном межузловых расстояний от данного узла планирования 30. Затем планировщик 22 группирует совокупность одного или более наборов планируемых заданий 40 со следующим наименьшим диапазоном межузловых расстояний от данного узла планирования 30 в подсовокупность наборов планируемых заданий 40 следующего уровня (например, подсовокупность 2-го уровня). Планировщик 22 продолжает группировать совокупности одного или более наборов планируемых заданий 40 с последующими диапазонами межузловых расстояний от данного узла планирования 30 в подсовокупности наборов планируемых заданий 40 последующих уровней до тех пор, пока все необходимые наборы планируемых заданий 40 в совокупности наборов планируемых заданий 40 не будут включены в очередность поиска.

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

Фиг.3А-3В - схема и таблица, соответственно, иллюстрирующие вариант осуществления очередности частичного поиска 60 в вычислительной системе с NUMA 61 с четырьмя блоками процессоров, содержащими соответствующие совокупности четырех аппаратных потоков 16. Соответствующая локальная память подключается к каждому процессору (не показан). Поскольку каждый аппаратный поток 16 в блоке процессора имеет аналогичные показатели выполнения, каждый блок процессора образует узел 0-го уровня в примере, изображенном на Фиг.3А-3В. В соответствии с этим узел планирования 0-го уровня 30(1) содержит аппаратные потоки 16(1)-16(4), узел планирования 0-го уровня 30(2) содержит аппаратные потоки 16(5)-16(8), узел планирования 0-го уровня 30(3) содержит аппаратные потоки 16(9)-16(12), а узел планирования 0-го уровня 30(4) содержит аппаратные потоки 16(9)-16(12). Узлы планирования 0-го уровня 30(1)-30(4) соответствуют соответствующим подсовокупностям наборов планируемых заданий 40(1)-40(4) 0-го уровня.

В соответствии с Фиг.3А узлы планирования 30(1)-30(2) совместно используют соединение 62(1) между узлами 30(1)-30(2), узлы планирования 30(1)-30(3) совместно используют соединение 62(2) между узлами 30(1)-30(3), узлы планирования 30(2)-30(4) совместно используют соединение 62(3) между узлами 30(2)-30(4), а узлы планирования 30(3)-30(4) совместно используют соединение 62(4) между узлами 30(3)-30(4). Предполагается, что в изображенном на Фиг.3А примере соединения 62(1)-62(4) имеют одинаковые характеристики быстродействия и полосы пропускания.

Межузловые расстояния между любыми двумя узлами 30, совместно использующими соединения 62, меньше межузловых расстояний между любыми двумя узлами 30, не использующими совместно соединения 62. Например, узел 30(1) осуществляет доступ к узлу 30(4) с помощью либо обоих соединений 62(1) и 62(3), либо обоих соединений 62(2) и 62(4). Подобным образом, узел 30(2) осуществляет доступ к узлу 30(3) с помощью либо обоих соединений 62(1) и 62(2), либо обоих соединений 62(3) и 62(4).

Со стороны узла 30(1) подсовокупность наборов планируемых заданий 40 1-го уровня содержит наборы планируемых заданий 40(2)-40(3), которые соответствуют узлам планирования 30(2)-30(3), а подсовокупность наборов планируемых заданий 40 2-го уровня содержит набор планируемых заданий 40(4), который соответствует узлу планирования 30(4).

Со стороны узла 30(2) подсовокупность наборов планируемых заданий 40 1-го уровня содержит наборы планируемых заданий 40(1)-40(4), которые соответствуют узлам планирования 30(1)-30(4), а подсовокупность наборов планируемых заданий 40 2-го уровня содержит набор планируемых заданий 40(3), который соответствует узлу планирования 30(3).

Со стороны узла 30(3) подсовокупность наборов планируемых заданий 40 1-го уровня содержит наборы планируемых заданий 40(1)-40(4), которые соответствуют узлам планирования 30(1)-30(4), а подсовокупность наборов планируемых заданий 40 2-го уровня содержит набор планируемых заданий 40(2), который соответствует узлу планирования 30(2).

Со стороны узла 30(4) подсовокупность наборов планируемых заданий 40 1-го уровня содержит наборы планируемых заданий 40(2)-40(3), которые соответствуют узлам планирования 30(2)-30(3), а подсовокупность наборов планируемых заданий 40 2-го уровня содержит набор планируемых заданий 40(1), который соответствует узлу планирования 30(1).

В соответствии Фиг.2 планировщик 22 заполняет наборы планируемых заданий 40(1)-40(М) соответствующими совокупностями заданий, как показано в блоке 58. Каждая совокупность одного или более заданий, представленных в планировщике 22, может быть создана явно процессом 12 или неявно рабочей средой 10 (например, путем создания агента без порождающего элемента или введения контекста выполнения операционной системы в контекст выполнения планировщика 22). Планировщик 22 вносит совокупности заданий в наборы планируемых заданий 40 в соответствии с каким-либо подходящим алгоритмом или в соответствии с топологией узлов планирования 30. Например, планировщик 22 может вносить совокупности заданий в наборы планируемых заданий 40 в круговом порядке. В другом примере планировщик 22 может вносить совокупности заданий в наборы планируемых заданий в соответствии с топологией узлов планирования 30.

Фиг.4 - схема последовательности операций, иллюстрирующая вариант осуществления способа выбора заданий для выполнения. Изображенный на Фиг.4 способ будет описан со ссылкой на вариант осуществления планировщика 22 на Фиг.1.

В соответствии с блоком 72 планировщик 22 определяет, освобождается ли виртуальный процессор 32. Планировщик 22 может выполнять эту функцию постоянно при обеспечении выполнения процесса 12. После завершения, блокирования или иного прерывания (например, явного возврата или принудительного прерывания обслуживания) контекста выполнения 34, запущенного на виртуальном процессоре 32, виртуальный процессор 32 освобождается для выполнения нового задания.

Когда планировщик 22 определяет, что виртуальный процессор 32 освобождается, планировщик 22 начинает поиск задания для выполнения свободным виртуальным процессором 32. В соответствии с блоком 74 планировщик 22 сначала пытается локализовать задание для выполнения в первой подсовокупности наборов планируемых заданий 40. Первой подсовокупностью наборов планируемых заданий 40 является набор планируемых заданий 40, соответствующий узлу планирования 30, который включает в себя свободный виртуальный процессор 32. Планировщик 22 может осуществлять поиск первой подсовокупности любым подходящим способом.

Если в первой подсовокупности найдено выполнимое задание, то планировщик 22 обеспечивает выполнение этого задания виртуальным процессором 32, как указано в блоке 76. Виртуальный процессор 32 пытается выполнить задание в продолжение предыдущего контекста выполнения 34. Если виртуальный процессор 32 неспособен продолжить выполнение задания, виртуальный процессор 32 осуществляет полное переключение контекста операционной системы на контекст выполнения, представленный данным заданием.

Если выполнимое задание в первой подсовокупности не найдено, то планировщик 22 определяет, задана ли очередностью поиска другая подсовокупность наборов планируемых заданий 40, как указано в блоке 78. Если подсовокупность первого уровня является единственной подсовокупностью, заданной очередностью поиска, то планировщик 22 продолжает осуществлять поиск первой подсовокупности до тех пор, пока выполнимое задание не будет локализовано.

Если очередностью поиска задана другая подсовокупность, то планировщик 22 пытается локализовать задание для выполнения в одном или более наборов планируемых заданий 40 в следующей подсовокупности, как указано в блоке 80. Если в наборе планируемых заданий 40 в следующей подсовокупности найдено выполнимое задание, то планировщик 22 обеспечивает выполнение задания виртуальным процессором 32, как указано в блоке 82. Если в следующей подсовокупности набора планируемых заданий 40 выполнимое задание не найдено, то планировщик 22 повторяет функцию блока 78. Планировщик 22 продолжает осуществлять поиск подсовокупностей набора планируемых заданий 40 в заданной очередности поиска до тех пор, пока либо не будет найдено выполнимое задание, либо не будет осуществлен поиск по всем подсовокупностям, заданным очередностью поиска.

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

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

Фиг.5А-5В - блок-схемы, иллюстрирующие соответствующие варианты осуществления 40А и 40В наборов планируемых заданий 40.

Фиг.5А - блок-схема, иллюстрирующая вариант осуществления 40А набора планируемых заданий 40, который содержит сово