Способ распределения задач сервером вычислительной системы, машиночитаемый носитель информации и система для реализации способа

Способ распределения задач сервером вычислительной системы, машиночитаемый носитель информации и система для реализации способа

Иллюстрации

Показать все

Реферат

ОБЛАСТЬ ИЗОБРЕТЕНИЯ

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

УРОВЕНЬ ТЕХНИКИ

В настоящее время известно несколько моделей распределения задач операционной системой, отличающихся различными уровнями сложности распределяемых задач. Один из относительно простых способов распределения называется FIFO (First In, First Out - «первым пришел - первым ушел») и предполагает распределение времени CPU в порядке прихода задачи в очередь. Ссылка: http://ru.wikipedia.org/wiki/FIFO. В этом случае каждая задача использует время CPU до тех пор, пока она не будет завершена.

Другой известный способ распределения называется Round robin (обслуживание по кругу - http://ru.wikipedia.org/wiki/Round-robin_(%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC)).

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

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

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

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

РАСКРЫТИЕ ИЗОБРЕТЕНИЯ

Заявленные способ, носитель информации и система служат для распределения задач сервером вычислительной системы.

Так, заявленный способ распределения задач сервером вычислительной системы заключается в том, что:

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

- однократно выбирают значение коэффициента доступности;

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

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

Предпочтительные, но не обязательные варианты реализации способа предполагают, в частности, дополнительное определение общего числа задач, которым не назначен ни один из обработчиков, при этом такие задачи определяют из условия их приоритетности с последующим назначением свободных обработчиков, которые могут быть предоставлены для выполнения обычных задач, согласно приоритету; множество обработчиков, составляющих неприкосновенный запас, может быть зафиксировано, например, в процентах от общего числа обработчиков; из множества обработчиков, которые могут быть предоставлены для выполнения обычных задач, дополнительно выделяют число обработчиков для распараллеливания (PAT), общее число которых определяют по формуле PAT=Р-Т-ER, где Р - общее число обработчиков, которые могут быть предоставлены для выполнения обычных задач, Т - общее число распределенных задач, ER - число обработчиков, выделенных в неприкосновенный запас, при этом возможность дополнительного назначения каждой последующей в очереди задаче по меньшей мере одного обработчика для распараллеливания определяют из условия сложности такой задачи; при этом число обработчиков (PUT), доступных для выполнения сложной задачи, определяют по формуле max (2, (РТТ+1)*РТР), где РТТ текущее число обработчиков, доступных для распараллеливания, а РТР процент обработчиков, разрешенных использовать для распараллеливания данной задачи; кроме того, итеративное назначение обработчиков задачам в данный момент времени выполняют на основе вычисления нового значения числа обработчиков для задачи, где новое значение числа обработчиков для данной задачи (NPUT) равно max (CPUT, min (PUT, CPUT+FAT, ST)), где CPUT - число обработчиков, используемых данной задачей в данный момент; PUT - число обработчиков, доступных для выделения данной задаче; FAT - максимальное число свободных обработчиков, которое может быть использовано для распараллеливания, где FAT=F-ER; F - общее число свободных обработчиков в данный момент времени; ER - число обработчиков, выделенных в неприкосновенный запас; ST - максимальное число обработчиков, требуемых для обработки данной задачи.

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

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

- однократный выбор значения коэффициента доступности

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

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

Предпочтительные, но не обязательные варианты реализации носителя предполагают, в частности, наличие дополнительной инструкции для определения общего числа задач, которым не назначен ни один из обработчиков, при этом такие задачи определяют из условия их приоритетности с последующим назначением свободных обработчиков, которые могут быть предоставлены для выполнения обычных задач, согласно приоритету; множество обработчиков, составляющих неприкосновенный запас, может быть зафиксировано, например, в процентах от общего числа обработчиков; носитель может содержать дополнительную инструкцию. в которой из множества обработчиков, которые могут быть предоставлены для выполнения обычных задач, дополнительно выделяют число обработчиков для распараллеливания (PAT), общее число которых определяют по формуле PAT=Р-Т-ER, где Р - общее число обработчиков, которые могут быть предоставлены для выполнения обычных задач, Т - общее число распределенных задач, ER - число обработчиков, выделенных в неприкосновенный запас; при этом число обработчиков (PUT), доступных для выполнения сложных задач, определено как max (2, (РТТ+1)*РТР), где РТТ текущее число обработчиков, доступных для распараллеливания, а РТР процент обработчиков, разрешенных использовать для распараллеливания данной задачи; возможно итеративное назначение обработчиков задачам в данный момент времени на основе вычисления нового значения числа обработчиков для задачи, где новое значение числа обработчиков для данной задачи (NPUT) равно max (CPUT, min (PUT, CPUT+FAT, ST)), где CPUT - число обработчиков, используемых данной задачей в данный момент; PUT - число обработчиков, доступных для выделения данной задаче; FAT - максимальное число свободных обработчиков, которое может быть использовано для распараллеливания, где FAT=F-ER; F - общее число свободных обработчиков в данный момент времени; ER - число обработчиков, выделенных в неприкосновенный запас; ST - максимальное число обработчиков, требуемых для обработки данной задачи.

Заявленная система для распределения заданий между множеством вычислительных устройств включает:

один или более процессоров;

одно или более устройств памяти;

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

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

- однократного выбора значения коэффициента доступности

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

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

Предпочтительные, но не обязательные варианты реализации системы предполагают, в частности, дополнительное определение общего числа задач, которым не назначен ни один из обработчиков, при этом такие задачи определяют из условия их приоритетности с последующим назначением свободных обработчиков, которые могут быть предоставлены для выполнения обычных задач, согласно приоритету; множество обработчиков, составляющих неприкосновенный запас системы может быть зафиксировано, например, в процентах от общего числа обработчиков; возможно из множества обработчиков, которые могут быть предоставлены для выполнения обычных задач, дополнительное выделение некоторого числа обработчиков для распараллеливания (PAT), определяемого по формуле PAT=Р-Т-ER, где Р - общее число обработчиков, которые могут быть предоставлены для выполнения обычных задач, Т - общее число распределенных задач, ER - число обработчиков, выделенных в неприкосновенный запас; при этом число обработчиков (PUT), доступных для выполнения сложных задач, равно max (2, (РТТ+1)*РТР), где РТТ текущее число обработчиков, доступных для распараллеливания, а РТР процент обработчиков, разрешенных использовать для распараллеливания данной задачи; кроме того, итеративное назначение обработчиков задачам в данный момент времени выполняют на основе вычисления нового значения числа обработчиков для задачи, где новое значение числа обработчиков для данной задачи (NPUT) равно max (CPUT, min (PUT, CPUT+FAT, ST)), где CPUT - число обработчиков, используемых данной задачей в данный момент; PUT - число обработчиков, доступных для выделения данной задаче; FAT - максимальное число свободных обработчиков, которое может быть использовано для распараллеливания, где FAT=F-ER; F - общее число свободных обработчиков в данный момент времени; ER - число обработчиков, выделенных в неприкосновенный запас; ST - максимальное число обработчиков, требуемых для обработки данной задачи.

КРАТКОЕ ОПИСАНИЕ ЧЕРТЕЖЕЙ

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

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

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

Фиг.3 является блок-схемой алгоритма описываемого метода распределения задач сервером вычислительной системы в соответствии с одним из возможных воплощений изобретения.

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

Фиг.5 иллюстрирует пример очереди заданий в системе распределения заданий в соответствии с одним из воплощений метода данного изобретения.

Фиг.6 иллюстрирует картину распределения обработчиков в случае РТР=0.50 в соответствии с некоторым воплощением изобретения.

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

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

ОПИСАНИЕ ПРЕДПОЧТИТЕЛЬНЫХ ВАРИАНТОВ ОСУЩЕСТВЛЕНИЯ

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

Настоящее изобретение предназначено для использования в любом вычислительном средстве, способном воспринимать и обрабатывать как текстовые данные, так и данные изображений. Это могут быть серверы, персональные компьютеры (ПК), переносные компьютеры (ноутбуки), компактные компьютеры (лаптопы) и любые иные существующие или разрабатываемые, а также будущие вычислительные устройства, подключаемые к компьютерной сети. Предпочтительным вариантом для реализации являются средства, обладающие многопроцессорностью, позволяющие иметь более одного процесса - обработчика на станции обработки, непосредственно выполняющей задание. Только одно задание или одна его подзадача может обрабатываться на каждом обработчике в каждый момент времени.

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

Фиг.1 является блок-схемой алгоритма, иллюстрирующего реализацию способа распределения заданий в вычислительной системе в соответствии с настоящим изобретением. Как показано на Фиг.1, описываемый метод включает шаги: определение 110 (также этот шаг описан на Фиг.3) совокупного числа (свободных) обработчиков вычислительного устройства, доступных для предоставления имеющимся заданиям, где совокупное число доступных обработчиков включает множество обработчиков, которые могут быть предоставлены для выполнения обычных задач и множество обработчиков, составляющих неприкосновенный запас. Задачи назначаются обработчикам в соответствии со следующим способом: способ отличается тем, что предполагает назначение (шаг 130) следующей в очереди задаче числа обработчиков не больше, чем число доступных в данный момент обработчиков, умноженного на некоторый, эмпирически выбираемый коэффициент доступности, и итеративное назначение обработчиков задачам в соответствии с описываемым методом пока имеются свободные обработчики, которые могут быть предоставлены для выполнения задач (шаг 120), и в случае отсутствия таковых, следующей задаче назначаются обработчики из неприкосновенного запаса (шаг 140).

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

Указанный коэффициент доступности может, например, динамически настраиваться с течением времени, настройка может быть осуществлена вручную или программно. Значение коэффициента доступности может назначаться произвольно или выбираться эмпирически для любой заданной системы. Например, если коэффициент доступности равен 0.5, то 50% от общего числа доступных обработчиков приписывается первой задаче. В случае если выбирается значение коэффициента доступности больше 0.5, ранее пришедшие задачи получают больше обработчиков, и соответственно, степень распараллеливания их будет выше, в то время как пришедшие позже могут дольше дожидаться в очереди. Если же выбирается значение коэффициента доступности меньше 0.5, большее количество задач запускается одновременно, но степень распараллеливания их будет меньше.

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

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

Пример реализации компьютерной системы, реализующей распределение задач в соответствии со способом изобретения, показано на Фиг.2. Система, показанная на Фиг.2, представляет клиент-серверную архитектуру. Сервер 202 соединен с множеством вычислительных устройств 204 (станций обработки). Каждое из вычислительных устройств 204 имеет, по меньшей мере, один обработчик 206. Блоки 208, 210, 212 являются примерами клиентов сервера 202. Клиенты 208, 210, 212 посылают задачи на сервер для обработки, где они могут быть распределены по обработчикам. Например, клиент 208 представляет собой папку заданий, ожидающих обработки (горячую папку), и программное приложение - распределитель файлов, управляющий пересылкой задач из горячей папки на сервер. Метод, связанный с горячей папкой, включает обработку или пересылку каждой новой задачи, поступающей в горячую папку, серверу 202. В другом примере клиент 212 может быть приложением-редактором, работающим на удаленном терминале с пользовательским интерфейсом для перевода текста.

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

Число доступных обработчиков для каждой задачи зависит от, например: (1) общего числа задач того же приоритета или выше; (2) числа обработчиков, используемых для выполнения задач с более высоким приоритетом; (3) числа обработчиков, используемых для выполнения задач с тем же приоритетом или выше, которые поступили в очередь раньше. Если число сложных задач выше, чем число обработчиков, каждой сложной задаче может быть назначено не более одного обработчика.

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

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

Описываемый способ распределения задач определяет множество свободных обработчиков из числа предназначенных для назначения задач на выполнение и связывает свободные обработчики с подзадачами. В одном случае число подзадач, образуемых сложной задачей, определяется в самом начале обработки. Например, максимальное число обработчиков, которые могут быть использованы для обработки сложной задачи, есть число ее подзадач - один обработчик на подзадачу, и наоборот - одна подзадача на обработчик. Такой способ распределения является “жадным” в том смысле, что он не отдает все свободные обработчики для выполнения одной сложной задачи.

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

Цель описываемого способа - так распределить задачи и их подзадачи в вычислительной системе, чтобы любая задача - большая или малая, могла вернуть результат выполнения задачи за ожидаемое время - время, определяемое в зависимости от ситуации. Могут существовать различные типы пользователей, например, работающие в реальном времени, пользователи, отправляющие задания через сайт (портал) и т.п. Могут существовать уровни приоритета, назначаемые каждой задаче, каждой подзадаче или одновременно родительской задаче и одной или более подзадач. Для некоторых пользователей время выполнения несущественно, они могут посылать свои задания в пакете, и время выполнения задач для них не важно.

На Фиг.3 показана блок-схема алгоритма описываемого метода распределения задач сервером вычислительной системы в соответствии с одним из возможных воплощений изобретения. На Фиг.4 показана блок-схема метода организации параллельной обработки заданий с одинаковым приоритетом в соответствии с одним из возможных воплощений изобретения. Способ, составляющий настоящее изобретение, и описываемый здесь, включает шаги, показанные на Фиг.3 и Фиг.4.

На Фиг.3 показаны следующие этапы метода: вычисление количества свободных обработчиков (310); определение числа всех нераспределенных сложных задач во всех очередях (320); определение актуального числа обработчиков, которые можно использовать для назначения невыполненным задачам, неприкосновенный запас (НЗ) и число обработчиков, которые могут быть использованы для распараллеливания (330); выбор очереди с наивысшим приоритетом (340); проверка, не пуста ли очередь с наивысшим уровнем приоритета (344); в зависимости от этого, назначение, по меньшей мере, по одному обработчику каждой сложной задаче в текущей очереди (350); перевычисление числа свободных обработчиков, которые могут быть использованы для распараллеливания (360), и распараллеливание сложных задач из текущей очереди заданий (370).

Возвращаясь к Фиг.3, число свободных обработчиков (310) в некоторый момент времени может быть обозначено символом F. Если после выполнения шага 310 число свободных обработчиков (F) больше нуля (314), то вычисляется общее число всех задач всех приоритетов (Т) (шаг 320). В противном случае сервер ждет, когда появятся свободные обработчики (F будет больше нуля).

Один из важных шагов - определение числа сложных задач (Т) во всех очередях с различными уровнями приоритетов (шаг 320). После этого вычисляется число обработчиков (Р), доступных для выполнения заданий (шаг 330).

Число обработчиков, которые необходимы системе распределения заданий, чтобы всегда обеспечить возможность начать обработку новой задачи, называется неприкосновенным запасом. В частном случае реализации обработчики, принадлежащие неприкосновенному запасу, не используются для распараллеливания сложных задач. Например, можно иметь один или более обработчиков для создания неприкосновенного запаса. Неприкосновенный запас составляет некоторую фиксированную долю общего числа обработчиков. Для примера, описываемая система распределения задач может требовать, чтобы 10% (ERP=10%) были доступны для начала обработки новой сложной задачи.

Неприкосновенный запас может быть описан как ER=Р*ERP, где ER число обработчиков неприкосновенного запаса, Р - общее число обработчиков в системе, доступных для выполнения обычных задач, ERP - некоторая постоянная фиксированная доля в процентах, необходимая для того, чтобы поддерживать возможность открыть обработку новой задачи. Значение EPR не должно быть слишком большим, в противном случае система не будет в состоянии распараллеливать сложные задачи и выполнять обработку достаточно быстро.

После того как неприкосновенный запас определен, вычисляется число обработчиков, которое разрешено использовать для распараллеливания сложных задач PAT (Processing units Available for Threading). PAT может быть представлено формулой PAT=P-Т-ER, где Р - общее число обработчиков, Т - общее число задач, и ER - число обработчиков, составляющих неприкосновенный запас. Таким образом, каждой задаче передается, по крайней мере, один обработчик плюс некоторое количество обработчиков для распараллеливания.

Обратимся снова к Фиг.3, где выбирается очередь с наивысшим приоритетом (шаг 340). Для примера, очередь может представлять собой упорядоченный по времени поступления список задач с одинаковым приоритетом. Для каждого уровня приоритета создается отдельная очередь. Распределение сложных задач и подзадач между обработчиками в режиме реального времени может быть оптимизировано в соответствии со следующими критериями: (1) настоящий метод распределения сложных задач позволяет запускать новые задачи на выполнение в вычислительной системе по возможности раньше; (2) сложные задачи, имеющие более высокий приоритет, обрабатываются в первую очередь, после чего обрабатываются задачи с меньшим приоритетом; (3) метод может предоставить несколько обработчиков сложным задачам, состоящим из нескольких подзадач, с целью более быстрого выполнения, чем на одном обработчике. Каждая из сложных задач и ее подзадач может иметь некоторый уровень приоритета. Сложные задачи в каждой из очередей обрабатываются по принципу “первый пришел - первым обслужен” для каждого из уровней приоритета по отдельности. Например, могут быть введены три уровня приоритета - низкий, средний и высокий. Для каждого уровня приоритета, сложные задачи обрабатываются одинаковым образом. Приоритет может приписываться задачам, например, априорно, до начала выполнения. Разным сложным задачам может быть присвоен разный приоритет. Например, срочным задачам или задачам, полученным от VIP-клиентов, может быть присвоен высокий приоритет. Все задачи в одной очереди имеют одинаковый приоритет.

Задачи из очереди с наивысшим приоритетом обрабатываются в первую очередь (шаги 350, 370), таким образом, сначала в качестве текущей очереди рассматривается очередь задач с наивысшим приоритетом. Если текущая очередь не пуста, каждой сложной задаче в очереди должен быть назначен, по меньшей мере, один обработчик (шаг 350). После того как задачи из текущей очереди размещаются на предназначенные им обработчики (350), определяется число обработчиков, которые могут быть использованы для распараллеливания (360).

На шаге 310 определяется число свободных обработчиков (F). F - максимальное число обработчиков, которое может быть использовано для назначения задачам и их распараллеливания в данный момент. Исключая неприкосновенный запас ER, число свободных обработчиков, которые могут быть использованы для распараллеливания (FAT=Free processing units Available for Threading), может быть представлено формулой FAT=F-ER. Обработчики из неприкосновенного запаса могут использоваться только для назначения новым задачам, но не для распараллеливания.

Если число свободных обработчиков, которое может быть использовано для распараллеливания, больше нуля (FAT>0) и общее число обработчиков, которых разрешено использовать для распараллеливания, больше нуля (PAT>0), то выполняются шаги 430, 440, 450, 460, представленные на Фиг.4 для каждой задачи, требующей распараллеливания. РТТ - текущее число обработчиков, доступных для распараллеливания текущей задачи (РТТ=Processing units for Threading Task). Для первой задачи, число обработчиков, которое может быть использовано для ее распараллеливания (РТТ), получает значение PAT - число обработчиков, которое разрешено использовать для распараллеливания сложных задач.

На Фиг.4 показана блок-схема алгоритма метода распараллеливания задач, находящихся в текущей очереди (шаг 370). Например, пусть очередь задач наивысшего приоритета не пуста. На шаге 430 вычисляется число обработчиков, доступных для обработки сложной задачи PUT (Processing units for Use in Task processing). Число обработчиков, доступных для обработки сложной задачи PUT может быть вычислено по формуле PUT=max (2, (РТТ+1)*РТР), где РТТ - текущее число обработчиков, которые могут быть использованы для распараллеливания, а РТР - процент обработчиков, разрешенных для распараллеливания данной задачи. В соответствии с вышеприведенной формулой PUT равно максимальному из значений - (1) целое 2 or (2) округленное значение (РТТ+1), умноженного на РТР, где where РТР - процент обработчиков, разрешенных использовать для распараллеливания. Если (РТТ+1)*РТР меньше 2, то выбирается PUT=2. Поскольку параллельная обработка на одном обработчике невозможно, то значение 2 используется как минимально необходимое число обработчиков для распараллеливания текущей задачи. РТР является константой, обозначающей процент обработчиков, разрешенных к использованию для (распараллеливания) данной задачи. Например, РТР может быть выбрано равным вышеупомянутому коэффициенту доступности. Тогда, предоставление обработчиков задачам осуществляется на основе константы РТР.

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

Например, в системе устанавливается значение константы РТР=50%. Когда новая задача поступает в очередь на распределение, около половины (50%) доступных обработчиков, которые могут быть использованы для распараллеливания, могли бы быть предоставлены этой новой задаче. Когда новая задача появляется в очереди (допустим, ни один обработчик не освободился), то вновь используется константа РТР, и 50% от числа доступных на тот момент обработчиков (50% от оставшихся 50%) будет предоставлено этой следующей новой задаче (около 25% от начального числа доступных обработчиков на момент прихода первой задачи, при условии, что ни один не освободился).

Рассмотрим вычислительную систему с 100 обработчиками и одной очередью задач. Для примера, положим ERP=0 и РТР=50%. Предположим, что первая задача в очереди оказалась очень сложной, и для нее потребовалось 50 обработчиков. Это означает, что после этого 50 обработчиков остались свободными. Далее, вторая пришедшая в очередь задача требует для обработки 25 обработчиков, тогда только 25 обработчиков остаются доступными для распределения следующих задач. Если третья пришедшая в очередь задача потребует 12 обработчиков, останутся свободными 13.

Установленное по умолчанию (default) значение РТР может варьироваться в зависимости от потребностей распределения задач. Например, значение РТР может быть установлено 50%. В другом случае значение РТР может быть, например, 35%. Другое преимущество описываемого метода распределения состоит в том, что в случае, если в некоторый момент есть несколько задач с одинаковым приоритетом, число возможных дополнительных обработчиков для второй задачи всегда меньше, чем число возможных дополнительных обработчиков для первой задачи (около (1-РТР), умноженное на число оставшихся свободных обработчиков после выделения обработчиков предыдущей задаче).

Фиг.5 иллюстрирует пример очереди заданий в системе распределения заданий в соответствии с одним из воплощений метода данного изобретения. На Фиг.5 показан пример очереди 500 задач с одним приоритетом. Задачи были помещены в очередь в следующем порядке: задача 510, задача 520, задача 530, задача 540, задача 550 и задача 560. На Фиг.5 показано, что, например, задача 1, обозначенная 510, разделяется на 150 подзадач, задача 520 делится на 10 подзадач, задача 530 делится на 250 подзадач, задачи 540 и 550 являются простыми неделимыми задачами и задача 560 делится на 95 подзадач.

Предположим, для примера, что клиент - серверная система, поддерживающая очередь заданий, изображенную на Фиг.5, содержит 100 обработчиков и