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

Изобретение относится к области определения приоритета задач в очереди, обрабатываемой локальной или облачной серверной системой. Техническим результатом является определение приоритета множества задач от множества пользователей по меньшей мере для одного процессора. Способ определения приоритета множества задач от множества пользователей: по меньшей мере для одного процессора содержит, применительно к необработанной задаче одного пользователя из множества пользователей, назначение числового приоритета пользователю; вычисление монотонной метрики M1 по совокупному процессорному времени, использованному предыдущими задачами пользователя по меньшей мере на одном процессоре за предшествующий период времени Т1; вычисление монотонной метрики М2 по временному интервалу между необработанной задачей и предшествующей задачей пользователя по меньшей мере на одном процессоре за предшествующий период времени Т2; вычисление монотонной метрики M3 по совокупному объему задач пользователя по меньшей мере на одном процессоре за предшествующий период времени Т3; уменьшение числового приоритета пользователя, монотонно зависящего от значений M1, М2 и M3; и назначение числового приоритета пользователя необработанной задаче; причем необработанные задачи с более высокими приоритетами выбираются для обработки по меньшей мере на одном процессоре раньше необработанных задач с более низкими приоритетами; и причем по меньшей мере один процессор последовательно выполняет только одну задачу в один момент времени. 3 н. и 12 з.п. ф-лы, 5 ил.

 

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

[0001] Настоящее изобретение относится к определению приоритета задач в очереди, обрабатываемой локальной или облачной серверной системой.

УРОВЕНЬ ТЕХНИКИ НАСТОЯЩЕГО ИЗОБРЕТЕНИЯ

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

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

[0004] Например, можно предположить, что обработка каждой задачи занимает 10 секунд. Пользователь А появляется первым и быстро ставит в очередь сто задач, и для обработки всех задач требуется 17 минут. Через одну минуту после того как пользователь А поставил свои задачи в очередь, пользователь В ставит в очередь одну задачу. Если система работает по принципу FIFO, то единственная задача от пользователя В не будет обрабатываться до тех пор, пока не будут обработаны все задачи от пользователя А, т.е. приблизительно 16 минут. Пользователю В придется ждать приблизительно 16 минут, чтобы просто обработать одну задачу, требующую 10 секунд процессорного времени.

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

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

[0007] Один пример таких задач представляет собой обработку содержащих текст изображений (в любом графическом формате, таком как pdf, tiff, jpeg и т.д.) с использованием оптического распознавания символов (OCR). В этом случае размер или объем каждой задачи измеряется в страницах. Время обработки задачи не обязательно напрямую связано с числом страниц в задаче, так как количество текста на разных страницах в разных задачах может различаться.

[0008] РАСКРЫТИЕ ИЗОБРЕТЕНИЯ Задачи могут размещаться в облачной серверной системе, на удаленном или локальном сетевом сервере, либо на том же компьютере, который отвечает за обработку задачи (в этом случае данный компьютер выступает в качестве сервера), если у пользователей есть возможность загружать задачи в систему. По завершении задачи каждый компьютер или процессор запрашивает у сервера задачу с наивысшим приоритетом. Затем процессор обрабатывает задачу и в это время не обрабатывает любую другую задачу и не прерывается на выполнение любой другой задачи.

[0009] В соответствии с настоящим изобретением каждой задаче, находящейся в очереди в системе, назначается приоритет, выбранный из диапазона приоритетов, например, от 0 до 255, где 0 - наивысший приоритет, который можно назначить задаче. Разным задачам одного пользователя могут назначаться разные приоритеты в зависимости от характера использования. Как правило, приоритет задачи не меняется в течение всего периода существования задачи.

[0010] При поступлении новой задачи система определяет, насколько интенсивно пользователь отправлял новые элементы в недавнем прошлом, и назначает новой задаче приоритет таким образом, чтобы задачи от пользователей, нечасто размещающих небольшие задачи, получали более высокий приоритет, а задачи от пользователей, интенсивно размещающих большое количество задач, получали более низкий приоритет. Система дополнительно отличается от подхода FIFO тем, что задачи сначала выбираются по приоритету (задачи с наибольшим приоритетом обрабатываются первыми), а задачи с одинаковым приоритетом распределяются в порядке их поступления.

[0011] В контексте OCR задачи, как правило, представляют собой файлы изображений или PDF-файлы, содержащие более одной страницы. Для анализа характера использования помимо количества задач система использует количество страниц, поскольку время обработки задачи часто приблизительно пропорционально количеству страниц в задаче, таким образом, на приоритет будущих задач одного пользователя должно влиять не только количество задач, поставленных в очередь пользователем, но и количество страниц.

[0012] Чтобы охарактеризовать использованное процессорное время, количество задач и объем задач (например, количество распознаваемых страниц), можно использовать различные монотонные метрики. Монотонные метрики представляют собой функции (например, с такими аргументами, как время или количество страниц или задач), которые имеют монотонную зависимость от своих аргументов, т.е. являются строго невозрастающими или строго неубывающими по всей соответствующей области знаний. Монотонная зависимость представляет собой зависимость, выражаемую монотонной функцией.

[0013] Варианты реализации настоящего изобретения включают в себя способы определения приоритета множества задач от множества пользователей по меньшей мере для одного процессора, содержащие, применительно к необработанной задаче одного пользователя из множества пользователей, назначение числового приоритета пользователю; вычисление монотонной метрики Ml по совокупному процессорному времени, использованному предыдущими задачами пользователя по меньшей мере на одном процессоре за предшествующий период времени Т1; вычисление монотонной метрики М2 по временному интервалу между необработанной задачей и предшествующей задачей пользователя по меньшей мере на одном процессоре за предшествующий период времени Т2; вычисление монотонной метрики М3 по совокупному объему задач пользователя по меньшей мере на одном процессоре за предшествующий период времени Т3; уменьшение числового приоритета пользователя, монотонно зависящего от значений M1, M2 и М3; и назначение числового приоритета пользователя необработанной задаче; причем необработанные задачи с более высокими приоритетами выбираются для обработки по меньшей мере на одном процессоре раньше необработанных задач с более низкими приоритетами; и причем по меньшей мере один процессор последовательно выполняет только одну задачу в один момент времени.

[0014| Варианты реализации настоящего изобретения также включают в себя систему, содержащую компьютерный сервер или облачный сервер, на котором хранятся задачи и программное обеспечение, способное выполнять команды по определению приоритета множества задач от множества пользователей по меньшей мере для одного процессора, содержащие, применительно к необработанной задаче одного пользователя из множества пользователей: назначение числового приоритета пользователю; вычисление монотонной метрики M1 по совокупному процессорному времени, использованному предыдущими задачами пользователя по меньшей мере на одном процессоре за предшествующий период времени Т1; вычисление монотонной метрики M2 по временному интервалу между необработанной задачей и предшествующей задачей пользователя по меньшей мере на одном процессоре за предшествующий период времени Т2; вычисление монотонной метрики М3 по совокупному объему задач пользователя по меньшей мере на одном процессоре за предшествующий период времени Т3; уменьшение числового приоритета пользователя, монотонно зависящего от значений M1, M2 и М3; и назначение числового приоритета пользователя необработанной задаче; причем необработанные задачи с более высокими приоритетами выбираются для обработки по меньшей мере на одном процессоре раньше необработанных задач с более низкими приоритетами; и причем по меньшей мере один процессор последовательно выполняет только одну задачу в один момент времени.

[0015] Варианты реализации настоящего изобретения также включают в себя физический носитель данных, на котором хранится программа, при исполнении которой процессор выполняет команды по определению приоритета множества задач от множества пользователей по меньшей мере для одного процессора, содержащие, применительно к необработанной задаче одного пользователя из множества пользователей: назначение числового приоритета пользователю; вычисление монотонной метрики M1 по совокупному процессорному времени, использованному предыдущими задачами пользователя по меньшей мере на одном процессоре за предшествующий период времени Т1; вычисление монотонной метрики М2 по временному интервалу между необработанной задачей и предшествующей задачей пользователя по меньшей мере на одном процессоре за предшествующий период времени Т2; вычисление монотонной метрики М3 по совокупному объему задач пользователя по меньшей мере на одном процессоре за предшествующий период времени Т3; уменьшение числового приоритета пользователя, монотонно зависящего от значений M1, М2 и М3; и назначение числового приоритета пользователя необработанной задаче; причем необработанные задачи с более высокими приоритетами выбираются для обработки по меньшей мере на одном процессоре раньше необработанных задач с более низкими приоритетами; и причем по меньшей мере один процессор выполняет последовательно только одну задачу в один момент времени.

[0016] Варианты реализации настоящего изобретения также могут включать в себя вычисление монотонной метрики М4 по совокупному объему задач, размещенных пользователем, по меньшей мере для одного процессора за более ранний период времени Т4; а также уменьшение числового приоритета пользователя, монотонно зависящего от значений M1, М2, М3 и М4.

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

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

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

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

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

[0021] На прилагаемых чертежах одинаковые номера позиций относятся к одинаковым частям на разных чертежах. Чертежи не обязательно приведены в масштабе; вместо этого акцент делается на представлении принципов настоящего изобретения. Содержание чертежей представлено ниже.

[0022] На Фиг. 1 представлена блок-схема нескольких первых этапов одного конкретного варианта реализации настоящего изобретения. Элемент А показывает, как блок-схема, представленная на Фиг. 1, связана с блок-схемой, представленной на Фиг. 2.

[0023] На Фиг. 2 представлена блок-схема нескольких этапов одного конкретного варианта реализации настоящего изобретения, следующих за этапами, показанными на Фиг. 1. Элемент В показывает, как блок-схема, представленная на Фиг. 2, связана с блок-схемой, представленной на Фиг. 3.

[0024| На Фиг. 3 представлена блок-схема нескольких заключительных этапов одного конкретного варианта реализации настоящего изобретения, следующих за этапами, показанными на Фиг. 2.

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

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

ПОДРОБНОЕ ОПИСАНИЕ ИЗОБРЕТЕНИЯ

[0027] Для каждого пользователя в системе хранятся пять переменных: «приоритет пользователя» (его не следует путать с приоритетом задачи), «число страниц за последний час», «число страниц за последнюю минуту», «конец последнего часа» и «конец последней минуты». Последние две переменные хранятся таким образом, чтобы системе не приходилось постоянно обновлять все данные при каждом размещении задачи пользователем.

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

[0029] Цель описанного ниже метода состоит в назначении задаче приоритета. В данном варианте реализации приоритет представляет собой целое число в диапазоне от 0 до 255.

[0030] Как показано на Фиг. 1, при размещении задачи на сервере переменной «готовность задачи к обработке» присваивается значение «ложь» (элемент 1 на блок-схеме). Затем читаются переменные, связанные с пользователем (элемент 2 на блок-схеме).

[0031] При загрузке в локальную память приоритету задачи присваивается нулевое значение. Значение переменной пользователя «конец последнего часа» копируется в локальную память в виде локальной переменной «конец последнего часа», и значение переменной пользователя «число страниц за последний час» копируется в локальную память в виде локальной переменной «число страниц за последний час» (элемент 3 на блок-схеме).

[0032] Если (элемент 4 на блок-схеме) локальная переменная «конец последнего часа» не определена (т.е. не имеет значения) или ее значение на 30 минут меньше текущего времени (в противном случае следующие этапы показаны на Фиг. 2), то

[0033] Система просматривает задачи, поставленные в очередь пользователем в течение часа до текущего времени, и присваивает локальной переменной «число страниц за последний час» значение, равное общему количеству страниц во всех данных задачах (суммарное число страниц в задачах, поставленных пользователем в очередь в течение последнего часа). Локальной переменной «конец последнего часа» присваивается значение, равное текущему времени (элемент 5 на блок-схеме).

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

[0035] Локальная переменная «число секунд последнего часа», полученная на предыдущем этапе, используется для вычисления приоритета задачи по нагрузке в соответствии со следующей закономерностью, аппроксимирующей логарифмическую функцию (элемент 7 на блок-схеме):

если локальная переменная «число секунд последнего часа» меньше 100, то «приоритет задачи по нагрузке» равен 0, в противном случае,

если локальная переменная «число секунд последнего часа» меньше 300, то «приоритет задачи по нагрузке» равен 3, в противном случае,

если локальная переменная «число секунд последнего часа» меньше 700, то «приоритет задачи по нагрузке» равен 5, в противном случае,

если локальная переменная «число секунд последнего часа» меньше 1500, то «приоритет задачи по нагрузке» равен 8, в противном случае,

если локальная переменная «число секунд последнего часа» меньше 4000, то «приоритет задачи по нагрузке» равен 11,

в противном случае «приоритет задачи по нагрузке» равен 15.

(0036| Этапы после получения значений переменной «приоритет задач по нагрузке» и локальной переменной «число страниц за последний час» показаны на Фиг. 2.

[0037] Значение «приоритет пользователя» копируется в переменную «старый приоритет задачи». Переменной «новый приоритет задачи» присваивается значение переменной «старый приоритет задачи». Переменная пользователя «конец последней минуты» копируется в локальную переменную «конец последней минуты», а переменная пользователя «число страниц за последнюю минуту» копируется в локальную переменную «число страниц за последнюю минуту» (элемент 8 на блок-схеме).

[0038] Если (элемент 9 на блок-схеме) локальная переменная «конец последней минуты» не определена (т.е. не имеет значения) или ее значение меньше текущего времени менее чем на минуту (в противном случае необходимо пропустить следующие три пункта), то:

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

[0040] Если (элемент 12 на блок-схеме) результат целочисленного деления переменной «сохраненные целые минуты» на 20 меньше результата целочисленного деления переменной «целые минуты» на 20 (т.е. данный этап выполняется не более одного раза за 20 минут), то переменной «новый приоритет задачи» присваивается значение переменной «старый приоритет задачи» минус единица, минус результат вычитания («целые минуты» минус «сохраненные целые минуты»), разделенный на 20 (элемент 13 на блок-схеме).

[0041] Локальной переменной «конец последней минуты» присваивается значение текущего времени. Локальной переменной «число страниц за последнюю минуту» присваивается нулевое значение (элемент 14 на блок-схеме).

[0042| Локальная переменная «число страниц за последнюю минуту» увеличивается на число страниц в новой задаче (элемент 15 на блок-схеме).

[0043] Этапы после получения значения локальной переменной «число страниц за последнюю минуту» показаны на Фиг. 3.

[0044] Если значение переменной «число страниц за последний час» меньше 5, то переменной «часовой приоритет задачи» присваивается значение 0, а переменной «лимит страниц за минуту» присваивается значение 3, в противном случае,

если значение переменной «число страниц за последний час» меньше 10, то переменной «часовой приоритет задачи» присваивается значение 1, а переменной «лимит страниц за минуту» присваивается значение 3, в противном случае,

если значение переменной «число страниц за последний час» меньше 50, то переменной «часовой приоритет задачи» присваивается значение 2, а переменной «лимит страниц за минуту» присваивается значение 5, в противном случае,

если значение переменной «число страниц за последний час» меньше 100, то переменной «часовой приоритет задачи» присваивается значение 3, а переменной «лимит страниц за минуту» присваивается значение 10, в противном случае,

если значение переменной «число страниц за последний час» меньше 250, то переменной «часовой приоритет задачи» присваивается значение 4, а переменной «лимит страниц за минуту» присваивается значение 15, в противном случае,

если значение переменной «число страниц за последний час» меньше 512, то переменной «часовой приоритет задачи» присваивается значение 5, а переменной «лимит страниц за минуту» присваивается значение 22, в противном случае,

если значение переменной «число страниц за последний час» меньше 1024, то переменной «часовой приоритет задачи» присваивается значение 6, а переменной «лимит страниц за минуту» присваивается значение 32,

в противном случае переменной «часовой приоритет задачи» присваивается значение, равное целой части натурального логарифма от значения локальной переменной «число страниц за последний час» минус 2, а переменной «лимит страниц за минуту» присваивается значение, равное целой части квадратного корня от значения локальной переменной «число страниц за последний час» (элемент 16 на блок-схеме).

[0045] Переменной «минутный приоритет задачи» присваивается нулевое значение (элемент 17 на блок-схеме).

[0046] Если (элемент 18 на блок-схеме) локальная переменная «число страниц за последнюю минуту» больше значения переменной «лимит страниц за минуту», то:

если локальная переменная «число страниц за последнюю минуту» меньше 4, то переменной «минутный приоритет задачи» присваивается значение 0, в противном случае,

если локальная переменная «число страниц за последнюю минуту» меньше 16, то переменной «минутный приоритет задачи» присваивается значение 5, в противном случае,

если локальная переменная «число страниц за последнюю минуту» меньше 23, то переменной «минутный приоритет задачи» присваивается значение 7, в противном случае,

если локальная переменная «число страниц за последнюю минуту» меньше 91, то переменной «минутный приоритет задачи» присваивается значение 10, в противном случае,

если локальная переменная «число страниц за последнюю минуту» меньше 180, то переменной «минутный приоритет задачи» присваивается значение 12,

в противном случае переменной «минутный приоритет задачи» присваивается значение, равное целой части натурального логарифма от значения (локальная переменная «число страниц за последнюю минуту», умноженная на 60) минус 2 (элемент 19 на блок-схеме).

[0047] Переменной «новый приоритет задачи по числу страниц» присваивается большее из значений «часовой приоритет задачи» и «минутный приоритет задачи» (элемент 20 на блок-схеме).

[0048] Переменной «новый приоритет задачи» присваивается меньшее из значений «новый приоритет задачи по числу страниц» и «новый приоритет задачи». Если значение переменной «новый приоритет задачи» больше 255, переменной «новый приоритет задачи» присваивается значение 255; если значение переменной «новый приоритет задачи» меньше нуля, переменной «новый приоритет задачи» присваивается нулевое значение (элемент 21 на блок-схеме).

[0049] Переменной «новый приоритет задачи» присваивается меньшее из значений «новый приоритет задачи по нагрузке» и «новый приоритет задачи» (элемент 21 на блок-схеме).

[0050] Переменной пользователя «конец последнего часа» присваивается значение локальной переменной «конец последнего часа». Переменной пользователя «конец последней минуты» присваивается значение локальной переменной «конец последней минуты». Переменной пользователя «число страниц за последний час» присваивается значение локальной переменной «число страниц за последний час». Переменной пользователя «число страниц за последнюю минуту» присваивается значение локальной переменной «число страниц за последнюю минуту». Переменной «приоритет пользователя» присваивается значение переменной «новый приоритет задачи» (элемент 22 на блок-схеме).

[0051] Переменной «приоритет новой задачи» присваивается значение переменной «новый приоритет задачи»; переменной «готовность задачи к обработке» присваивается значение «истина» (элемент 23 на блок-схеме).

[0052] Теперь новая задача на сервере готова к обработке процессором в соответствии с новым приоритетом задачи, рассчитанным по описанной выше методике.

[0053] На Фиг. 4 представлена система, реализующая способ определения приоритета задач для нескольких пользователей и нескольких процессоров с применением облачного сервера, содержащий, применительно к необработанной задаче, размещенной пользователем, назначение числового приоритета пользователю; вычисление монотонной метрики M1 по совокупному процессорному времени, использованному предыдущими задачами пользователя по меньшей мере на одном процессоре за предшествующий период времени Т1; вычисление монотонной метрики М2 по временному интервалу между необработанной задачей и предшествующей задачей пользователя по меньшей мере на одном процессоре за предшествующий период времени Т2; вычисление монотонной метрики М3 по совокупному объему задач пользователя по меньшей мере на одном процессоре за предшествующий период времени Т3; уменьшение числового приоритета пользователя, монотонного зависящего от значений M1, M2 и М3; и назначение числового приоритета пользователя необработанной задаче; причем необработанные задачи с более высокими приоритетами выбираются для обработки по меньшей мере на одном процессоре раньше необработанных задач с более низкими приоритетами; и причем по меньшей мере один процессор последовательно выполняет только одну задачу в один момент времени. Пользователи 1001, 1002 и 1003 размещают задачи (например, задачи по оптическому распознаванию символов) на облачном сервере 1011, где каждой задаче назначается приоритет в соответствии со способом, воплощающим настоящее изобретение. Задачи читаются облачным сервером и обрабатываются (например, путем оптического распознавания символов) процессорами 1021, 1022 и 1023. Пользователи и процессоры соединяются с облачным сервером через Интернет, другую сеть, через беспроводное соединение или напрямую.

[0054] На Фиг. 5 представлена система, реализующая способ определения приоритета задач для нескольких пользователей и нескольких процессоров с применением компьютерного сервера, содержащий, применительно к необработанной задаче, размещенной пользователем, назначение числового приоритета пользователю; вычисление монотонной метрики M1 по совокупному процессорному времени, использованному предыдущими задачами пользователя по меньшей мере на одном процессоре за предшествующий период времени Т1; вычисление монотонной метрики M2 по временному интервалу между необработанной задачей и предшествующей задачей пользователя по меньшей мере на одном процессоре за предшествующий период времени Т2; вычисление монотонной метрики М3 по совокупному объему задач пользователя по меньшей мере на одном процессоре за предшествующий период времени Т3; уменьшение числового приоритета пользователя, монотонно зависящего от значений M1, M2 и М3; и назначение числового приоритета пользователя необработанной задаче; причем необработанные задачи с более высокими приоритетами выбираются для обработки по меньшей мере на одном процессоре раньше необработанных задач с более низкими приоритетами; и причем по меньшей мере один процессор последовательно выполняет только одну задачу в один момент времени. Пользователи 2001 и 2002 размещают задачи (например, задачи по оптическому распознаванию символов) на компьютерном сервере 2011, где каждой задаче назначается приоритет в соответствии со способом, воплощающим настоящее изобретение. Задачи читаются компьютерным сервером и обрабатываются (например, путем оптического распознавания символов) процессорами 2021 и 2022. Пользователи и процессоры соединяются с компьютерным сервером через Интернет, другую сеть, через беспроводное соединение или напрямую.

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

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

назначение числового приоритета пользователю;

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

вычисление монотонной метрики М2 по временному интервалу между необработанной задачей и предшествующей задачей пользователя по меньшей мере на одном процессоре за предшествующий период времени Т2;

вычисление монотонной метрики M3 по совокупному объему задач пользователя по меньшей мере на одном процессоре за предшествующий период времени Т3;

уменьшение числового приоритета пользователя, монотонно зависящего от значений M1, М2 и M3; и

назначение числового приоритета пользователя необработанной задаче;

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

причем по меньшей мере один процессор последовательно выполняет только одну задачу в один момент времени.

2. Способ по п. 1, дополнительно содержащий:

вычисление монотонной метрики М4 по совокупному объему задач пользователя по меньшей мере на одном процессоре за более ранний период времени Т4; и

уменьшение числового приоритета пользователя монотонно зависящего от значений M1, М2, M3 и М4.

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

4. Способ по п. 1, в котором числовой приоритет пользователя представляет собой целое число, выбранное из некоторого интервала.

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

6. Система для определения приоритета множества задач от множества пользователей по меньшей мере для одного процессора, содержащая:

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

назначение числового приоритета пользователю;

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

вычисление монотонной метрики М2 по временному интервалу между необработанной задачей и предшествующей задачей пользователя по меньшей мере на одном процессоре за предшествующий период времени Т2;

вычисление монотонной метрики M3 по совокупному объему задач пользователя по меньшей мере на одном процессоре за предшествующий период времени Т3;

уменьшение числового приоритета пользователя, монотонно зависящего от значений M1, M2 и M3; и

назначение числового приоритета пользователя необработанной задаче;

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

причем по меньшей мере один процессор последовательно выполняет только одну задачу в один момент времени.

7. Система по п. 6, в которой команды дополнительно содержат:

вычисление монотонной метрики М4 по совокупному объему задач пользователя по меньшей мере на одном процессоре за более ранний период времени Т4; и

уменьшение числового приоритета пользователя монотонно зависящего от значений M1, M2, M3 и М4.

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

9. Система по п. 6, в которой числовой приоритет пользователя представляет собой целое число, выбранное из некоторого интервала.

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

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

назначение числового приоритета пользователю;

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

вычисление монотонной метрики М2 по временному интервалу между необработанной задачей и предшествующей задачей пользователя по меньшей мере на одном процессоре за предшествующий период времени Т2;

вычисление монотонной метрики M3 по совокупному объему задач пользователя по меньшей мере на одном процессоре за предшествующий период времени Т3;

уменьшение числового приоритета пользователя, монотонно зависящего от значений M1, М2 и M3; и

назначение числового приоритета пользователя необработанной задаче;

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

причем по меньшей мере один процессор последовательно выполняет только одну задачу в один момент времени.

12. Носитель по п. 11, в котором команды дополнительно содержат:

вычисление монотонной метрики М4 по совокупному объему задач пользователя по меньшей мере на одном процессоре за более ранний период времени Т4; и

уменьшение числового приоритета пользователя, монотонно зависящего от значений M1, М2, M3 и М4.

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

14. Носитель по п. 11, в котором числовой приоритет пользователя представляет собой целое число, выбранное из некоторого интервала.

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



 

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

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

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

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

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

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

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

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

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

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

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

Изобретение относится к способу функционирования защищенной операционной системы (SecureOS) на многопроцессорных системах в мобильных устройствах. Технический результат заключается в повышении производительности SecureOS. Способ содержит этапы, на которых: после активации потока в SecureOS назначают в SecureOS этот поток ядру процессора (CPU), каковое назначение включает в себя этап, на котором изменяют маску CPU, при этом маска CPU является структурой данных, поддерживаемой в SecureOS для информирования незащищенной операционной системы (RichOS) о текущих потребностях SecureOS в ядрах CPU; передают посредством SecureOS маску CPU в RichOS для запрашивания RichOS предоставить SecureOS управление на ядре CPU; на основе маски CPU включают посредством RichOS ядро CPU, если ядро CPU отключено; и переключают посредством RichOS ядро CPU в защищенный режим, предоставляя SecureOS управление на ядре CPU, причем мобильное устройство содержит CPU, имеющий множество ядер CPU, каждое из которых функционирует либо в защищенном, либо в незащищенном режиме, и установленные в мобильном устройстве RichOS и SecureOS поддерживают многопоточность и сообщаются друг с другом через предварительно заданный интерфейс. 2 н. и 28 з.п. ф-лы, 5 ил.

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

Изобретение относится к области определения приоритета задач в очереди, обрабатываемой локальной или облачной серверной системой. Техническим результатом является определение приоритета множества задач от множества пользователей по меньшей мере для одного процессора. Способ определения приоритета множества задач от множества пользователей: по меньшей мере для одного процессора содержит, применительно к необработанной задаче одного пользователя из множества пользователей, назначение числового приоритета пользователю; вычисление монотонной метрики M1 по совокупному процессорному времени, использованному предыдущими задачами пользователя по меньшей мере на одном процессоре за предшествующий период времени Т1; вычисление монотонной метрики М2 по временному интервалу между необработанной задачей и предшествующей задачей пользователя по меньшей мере на одном процессоре за предшествующий период времени Т2; вычисление монотонной метрики M3 по совокупному объему задач пользователя по меньшей мере на одном процессоре за предшествующий период времени Т3; уменьшение числового приоритета пользователя, монотонно зависящего от значений M1, М2 и M3; и назначение числового приоритета пользователя необработанной задаче; причем необработанные задачи с более высокими приоритетами выбираются для обработки по меньшей мере на одном процессоре раньше необработанных задач с более низкими приоритетами; и причем по меньшей мере один процессор последовательно выполняет только одну задачу в один момент времени. 3 н. и 12 з.п. ф-лы, 5 ил.

Наверх