АППАРАТНО-РЕАЛИЗУЕМЫЙ СПОСОБ ПЛАНИРОВАНИЯ ЗАДАНИЙ (ВАРИАНТЫ), СИСТЕМА ПЛАНИРОВАНИЯ ЗАДАНИЙ И МАШИНОЧИТАЕМЫЙ НОСИТЕЛЬ
HARD-WIRED METHOD TO PLAN TASKS (VERSIONS), SYSTEM TO PLAN TASKS AND MACHINE-READABLE MEDIUM

ОБЛАСТЬ ТЕХНИКИ
Настоящее изобретение относится к планированию заданий для выполнения на компьютере. В частности варианты настоящего изобретения относятся к планированию вычислительных заданий, которое осуществляется в соответствии с критериями загрузки ресурсов, необходимых для определенных заданий, и с загрузкой ресурсов компьютера, которые должны использоваться заданиями.
ПРЕДПОСЫЛКИ СОЗДАНИЯ ИЗОБРЕТЕНИЯ
Операционные системы современных компьютеров используют многозадачные планировщики, которые обеспечивают одновременное выполнение на компьютере нескольких заданий (процессов). Существует много различных алгоритмов планирования, однако основная идея таких алгоритмов заключается в том, что одному потоку процесса отводится малый временной интервал (квант), и затем другому потоку этого процесса или другого процесса отводится другой временной интервал и т.д. Длительность такого временного интервала очень мала, обычно она выбирается в пределах 20-120 миллисекунд. Использование таких малых интервалов приводит к тому, что выполнение нескольких заданий воспринимается человеком как одновременное.
Как правило, центральный процессор (ЦП) компьютера является самым быстрым компонентом вычислительных систем, а такие ресурсы компьютера, как дисковая система ввода/вывода и даже устройства памяти работают медленнее. Например, дисковая система ввода/вывода может работать в миллионы раз медленнее, чем ЦП, если сравнивать передачу данных с диска с передачей данных внутри ЦП. В результате из-за таких медленных ресурсов ЦП зачастую простаивает. Например, ЦП с частотой три гигагерца часто простаивает в ожидании выборки данных с диска, поскольку среднее время доступа к данным измеряется миллисекундами.
Поскольку несколько разных заданий могут зачастую обращаться к одним и тем же ресурсам, задания могут конфликтовать друг с другом, результатом чего является замедление выполнения одного или нескольких заданий. Для пользователя конфликты заданий проявляются в отсутствии ответов от приложений, в прерывистых движениях курсора и замедлении прорисовки графики.
Такие негативные последствия могут быть сведены к минимуму с помощью технологии синхронизации. Синхронизация предотвращает использование приложением или вычислительным заданием количества ресурсов, превышающего заданную величину. Могут использоваться различные типы синхронизации: синхронизация дисковой системы ввода/вывода, синхронизация ЦП и синхронизация сети. Например, синхронизация ЦП может предусматривать установку для приложения предельной величины используемого времени ЦП и принудительное прекращение работы приложения, когда оно превысит заданный предел. Синхронизация иногда применяется к ресурсам компьютера для поддержки приложений технического обслуживания или менее важных вычислительных заданий. Хотя синхронизация имеет определенные достоинства, однако использование ресурсов вычислительным заданием не является полностью прозрачным для других заданий и приложений.
Вышеуказанные проблемы еще более усугубляются тем обстоятельством, что компьютеры могут работать круглосуточно, и в этом случае использование их ресурсов становится еще менее эффективным. Например, в большей части настольных компьютеров используется менее пяти процентов имеющихся ресурсов, а высокопроизводительные серверы используются меньше чем на 20 процентов. Даже в компьютерах, в которых используется 80-90% ресурсов, имеется запас 10-20%.
Для возвращения в работу и использования таких ресурсов, которые в противном случае будут потеряны, необходим способ, который позволит выполнять в компьютерной системе одно или несколько заданий без существенного влияния на другие задания или приложения. Такой способ не должен отнимать время у пользователя на планирование задания, и, кроме того, его применение не должно сказываться негативно на взаимодействии пользователя с компьютерной системой в процессе выполнения задания.
Способы, описанные в настоящем разделе, - это способы, которые могли бы быть осуществлены, но необязательно были предложены или осуществлены ранее. Поэтому, если не указано иное, нельзя считать, что любой из способов, описанных в настоящем разделе, определяется как известный способ только лишь по причине его включения в настоящий раздел.
КРАТКОЕ ОПИСАНИЕ ЧЕРТЕЖЕЙ
Настоящее изобретение иллюстрируется на примерах, которые не являются ограничивающими, со ссылками на прилагаемые чертежи, на которых одинаковые ссылочные номера относятся к одинаковым элементам и на которых показано:
фигура 1А - схема планировщика, ориентированного на ресурсы, в котором используются рабочие списки планирования, обеспечивающие учет загрузки ресурсов, в соответствии с одним из вариантов осуществления настоящего изобретения;
фигура 1В - схема планировщика, ориентированного на ресурсы, в соответствии с другим вариантом осуществления настоящего изобретения;
фигура 2 - блок-схема алгоритма планирования, ориентированного на ресурсы, в соответствии с одним из вариантов осуществления настоящего изобретения;
фигура 3 - блок-схема, иллюстрирующая структуру вычислительной системы, на которой может быть реализован один из вариантов изобретения.
ПОДРОБНОЕ ОПИСАНИЕ
В нижеприведенном описании различные конкретные детали указаны в таком порядке, который должен обеспечивать полное понимание настоящего изобретения. Однако будет ясно, что настоящее изобретение может быть осуществлено и без таких конкретных деталей. В других случаях хорошо известные структуры и устройства показаны в общем виде, в форме блоков, чтобы не загромождать описание настоящего изобретения излишними деталями.
ОБЗОР
Бóльшая часть компьютеров не использует все возможности своих ресурсов в течение всего времени работы. Это справедливо для компьютеров, которые работают только часть дня, и даже для компьютеров, загрузка которых довольно высока при круглосуточной работе семь дней в неделю. Поэтому компьютерное время и ресурсы расходуются непроизводительно. Например, на временном интервале, равном двадцати четырем часам, компьютерная система, работающая с высокой загрузкой, и система, у которой могут быть лишь непродолжительные пики активности, могут в среднем использовать от пяти до двадцати процентов своих ресурсов.
В соответствии с одним из вариантов осуществления изобретения вычислительное задание планируется в соответствии с загрузкой ресурса и с критерием загрузки для ресурса, который используется вычислительным заданием. Например, вычислительное задание может использовать критерий загрузки ресурса, заключающийся в том, что дисковая система ввода/вывода должна иметь 60% свободной производительности для того, чтобы можно запланировать это задание для выполнения. Если свободная производительность дисковой системы ввода/вывода ниже 60 процентов, то в этом варианте вычислительное задание для выполнения не планируется.
В одном из вариантов осуществления изобретения планировщик, ориентированный на ресурсы (ПОР), записывает каждое вычислительное задание по меньшей мере в один из нескольких различных рабочих списков планирования, обеспечивающих учет загрузки ресурсов. Такими рабочими списками планирования могут быть: рабочий список дисковой системы ввода/вывода, рабочий список ЦП и рабочий список системы ввода/вывода сети (перечень не является исчерпывающим). Таким образом, в определенный рабочий список планирования записываются вычислительные задания, ожидающие использования определенного ресурса. В этом варианте для каждого вычислительного задания назначается критерий загрузки, относящийся к определенному ресурсу. ПОР выбирает один из ресурсов, который должен быть следующим для планирования вычислительного задания. В одном из вариантов осуществления изобретения выбор осуществляется в соответствии с приоритетом ресурса. Например, дисковая система ввода/вывода имеет более высокий приоритет по сравнению с ЦП. В одном из вариантов осуществления изобретения ресурсам, указанным как менее быстрые ресурсы, назначаются более высокие приоритеты по сравнению с более быстрыми ресурсами.
После выбора ресурса, который должен быть запланирован, ПОР задает выполнение одного из вычислительных заданий из рабочего списка, соответствующего выбранному ресурсу. В одном из вариантов осуществления изобретения ПОР выбирает вычислительное задание в соответствии с критерием загрузки, который выполняется для свободной производительности ресурса. Однако ПОР может также использовать и другие факторы, такие как, например, приоритет вычислительного задания, необходимый порядок выполнения заданий, порядок, в котором задания были записаны в рабочий список и т.п.
Необходимо отметить, что в одном из вариантов осуществления изобретения ПОР обеспечивает эффективное использование ресурсов компьютера путем планирования каждого вычислительного задания, когда ресурсы, которые должны использоваться заданием, доступны (полностью или частично), даже если другие ресурсы, не требующиеся для этого задания, используются (полностью или частично) другими заданиями, и, таким образом, снижает влияние на выполнение других заданий.
ПЛАНИРОВЩИК, ОРИЕНТИРОВАННЫЙ НА РЕСУРСЫ
На фигуре 1А представлена схема планировщика, ориентированного на ресурсы, в котором используются рабочие списки, обеспечивающие учет загрузки ресурсов, в соответствии с одним из вариантов осуществления настоящего изобретения. ПОР 100 осуществляет предварительное планирование выполнения вычислительных заданий с учетом свободной производительности различных ресурсов компьютера. В качестве примеров различных ресурсов можно указать ЦП, дисковую систему ввода/вывода, систему ввода/вывода сети, видеосистему, память, клавиатуру, сетевой ресурс и т.п. Термин “вычислительное задание” или “задание”, используемый в настоящем описании, понимается как процесс, поток, микрозадание (описано ниже) или любая часть исполняемой программы (перечень не является исчерпывающим). ПОР 100 может обеспечить, чтобы потребности каждого вычислительного задания в отношении ресурсов удовлетворялось без конфликта с потребностями других заданий в отношении этих же ресурсов. В одном из вариантов осуществления изобретения ПОР 100 может определить, когда определенный ресурс занят лишь частично, и назначает его неиспользуемую часть выбранному заданию с минимальным ущербом для других заданий, уже использующих этот ресурс.
В одном из вариантов осуществления изобретения ПОР 100 планирует выполнение вычислительных заданий для нескольких различных ресурсов. Различные ресурсы необязательно должны быть в той же вычислительной системе, что и ПОР 100. Например, в одном из вариантов осуществления изобретения ПОР 100 планирует вычислительные задания, использующие ресурс, который оценивается по сети. Более конкретно, ресурс может оцениваться через сеть Интернет.
Таким образом, в одном из вариантов осуществления изобретения ПОР 100 получает запросы вычислительных заданий, для выполнения которых необходимы различные ресурсы, и осуществляет планирование с распределением заданий по ресурсам и определением времени, когда эти задания должны запускаться на выполнение.
Загрузка ресурсов компьютера
В ПОР 100 вводится информация 105 о загрузке ресурсов, описывающая использование различных ресурсов компьютера. Загрузка может относиться к некоторому временному интервалу или к заданному моменту времени. Загрузка может определяться как величина, усредненная на заданном временном интервале. Например, загрузка ресурса может определяться как средняя величина использования ресурса на заданном временном интервале. В качестве конкретного примера, загрузка ЦП, равная 30%, может относиться к среднему использованию ЦП в течение только что прошедшего интервала времени. В одном из вариантов осуществления изобретения интервал измеряется в квантах времени.
В одном из вариантов загрузка может выражаться численной величиной. Например, загрузка может определяться в соответствии с числом операций, которые ожидают выполнения в заданный момент времени. Например, если имеется “х” операций, ожидающих выполнения, то загрузка может быть охарактеризована числом “х”. В качестве другой численной величины загрузки ресурса можно использовать, например, число запросов на использование определенного ресурса. Например, в одном из вариантов осуществления изобретения загрузка определяется на основе суммарного количества запросов, которые используются каждым процессом при обращении к определенному ресурсу. Численная характеристика загрузки может относиться к некоторому моменту времени или к интервалу. Например, в одном из вариантов осуществления изобретения численная характеристика загрузки может определяться по среднему числу операций, ожидающих выполнения в течение определенного интервала времени. В другом варианте численная характеристика загрузки ресурса определяется по числу операций, ожидающих выполнения в определенный момент времени.
В одном из вариантов осуществления изобретения ПОР 100 оценивает предстоящую загрузку ресурсов по информации 105 загрузки. Например, на основе числа запросов на использование определенного ресурса (и, возможно, с учетом других факторов) делается оценка предстоящей загрузки ресурса. В другом примере оценка предстоящей загрузки ресурса делается на основе использования (в процентах) определенного ресурса (и, возможно, с учетом других факторов).
Критерии загрузки для вычислительного задания
В ПОР 100 также вводятся критерии 118 загрузки для заданий, выполнение которых должно планироваться. Критерии 118 загрузки относятся к ресурсам. Например, могут использоваться пороговые величины для ресурсов, при этом ПОР 100 планирует включение вычислительного задания на выполнение только в том случае, когда загрузка ресурса другими заданиями не превышает заданной пороговой величины. Например, ПОР 100 может планировать включение некоторого вычислительного задания, использующего дисковую систему ввода/вывода только в том случае, когда ее свободная производительность превышает 60 процентов. В одном из вариантов осуществления изобретения ПОР 100 имеется интерфейс для прикладных программ (API), обеспечивающий критерии 118 загрузки ресурсов для приложения, которое является источником вычислительного задания. Ниже будет представлен пример API.
В одном из вариантов осуществления изобретения критерии 118 загрузки определяются по времени. Примером критериев 118 загрузки, определяемых по времени, является критерии, определяемые процентным отношением. В одном из вариантов осуществления изобретения критерии 118 загрузки являются численными величинами. Примером критерия 118, представляющего собой численную характеристику, является число операций, ожидающих выполнения с использованием определенного ресурса. Другим примером критерия 118, представляющего собой численную характеристику, является число полученных запросов на использование ресурса. Например, критерий загрузки для определенного процесса может определяться по числу запросов на использование определенного ресурса.
В одном из вариантов осуществления изобретения в ПОР 100 сохраняется журнал 116 информации загрузки. Информация загрузки, сохраняемая в журнале 116, описывает предшествующую загрузку ресурса одним или несколькими заданиями. Например, тот факт, что вычислительное задание использовало 30 процентов ресурса системы ввода/вывода сети, сохраняется для последующего анализа. В одном из вариантов осуществления изобретения ПОР 100 использует информацию загрузки, сохраняемую в журнале 116, для определения критерия загрузки для вычислительного задания, которое должно быть запланировано для выполнения. Например, на основании одного или нескольких случаев, в которых вычислительное задание использовало определенный ресурс, ПОР 100 определяет, что для вычислительного задания критерий загрузки равен “х” процентов для определенного ресурса. Затем ПОР 100 использует этот критерий загрузки при планировании вычислительного задания.
В ПОР 100 также вводится исполняемый код 108 заданий, которые должны быть запланированы для выполнения, для которых ПОР 100 осуществляет анализ для определения критериев загрузки.
ЗАДЕРЖКА ПЛАНИРОВАНИЯ ВЫПОЛНЕНИЯ ЗАДАНИЙ
В одном из вариантов осуществления изобретения определение возможности разрешения использования вычислительным заданием определенного ресурса может быть задержано. Например, для определенного вычислительного задания может использоваться критерий загрузки, который позволяет обслужить заданное число запросов, поступивших от других вычислительных заданий, прежде чем планировщик, ориентирующийся на ресурсы, приступит к планированию определенного вычислительного задания. В одном из вариантов осуществления изобретения ПОР задерживает выполнение определенного вычислительного задания, если загрузка ресурса превышает пороговую величину. Для определенного вычислительного задания задается число запросов от других вычислительных заданий, которые могут быть обслужены, до того как начнется планирование определенного вычислительного задания. В одном из вариантов осуществления изобретения определенное вычислительное задание планируется для выполнения, после того как будет обслужено заданное число запросов. В другом варианте осуществления изобретения после того, как будут обслужены запросы, ПОР определяет возможность разрешения определенному ресурсу использовать ресурс.
В одном из вариантов осуществления изобретения планировщик, ориентированный на ресурсы, использует стандартный рабочий список для запросов ресурса, которые должны быть выполнены без задержки, и рабочий список для задержанных запросов, в который помещаются запросы ресурса, которые могут быть задержаны. Для каждой записи в списке задержанных запросов может указываться текущий номер запроса, когда запрос помещается в список задержанных запросов. Эти задержанные запросы могут быть записаны в том порядке, в котором они должны обслуживаться. В одном из вариантов осуществления изобретения используется несколько рабочих списков задержанных запросов. Когда ПОР определяет, что можно начинать новый запрос, он сначала обращается к списку задержанных запросов для выявления запросов, сроки которых истекают, и выбирает их для планирования выполнения, в обход стандартного списка запросов.
РАБОЧИЕ СПИСКИ ПЛАНИРОВАНИЯ, ОРИЕНТИРОВАННОГО НА РЕСУРСЫ
В одном из вариантов осуществления изобретения в ПОР 100 используется рабочий список 120 планирования, ориентированного на ресурсы, для каждого ресурса, для которого может быть запланировано вычислительное задание. Например, в ПОР 100 используется рабочий список 120(1) ресурса ЦП, рабочий список 120(2) дисковой системы ввода/вывода, рабочий список 120(3) системы ввода/вывода сети и рабочие списки 120(n) других ресурсов. В качестве других примеров можно указать рабочий список сетевого ресурса, рабочий список ресурса видеосистемы и рабочий список ресурса клавиатуры. Каждый рабочий список 120 содержит задания, которые стоят в ожидании использования соответствующего ресурса. Для того чтобы не загромождать схему, не все возможные рабочие списки планирования, ориентированного на ресурсы, представлены на фигуре 1А. В одном из вариантов осуществления изобретения используется отдельный рабочий список для вычислительных заданий, которые используют несколько ресурсов. В одном из вариантов осуществления изобретения используются два или более рабочих списков для определенного ресурса, причем списки соответствуют разным приоритетам. Например, вычислительные задания с высоким приоритетом помещаются в один рабочий список, со средним приоритетом - в другой рабочий список и т.д. Рабочие списки могут быть упорядоченными или неупорядоченными.
В одном из вариантов осуществления изобретения ПОР 100 определяет, в какой из рабочих списков поместить вычислительное задание, на основе анализа исполняемого кода 108. Например, в одном из вариантов осуществления изобретения ПОР 100 проверяет команды исполняемого кода 108 вычислительного задания для определения ресурсов, которые необходимы для этого задания.
В одном из вариантов осуществления изобретения, когда имеется в наличии достаточное количество свободного ресурса компьютера, ПОР 100 назначает этот ресурс одному из вычислительных заданий в рабочем списке, соответствующем этому ресурсу. Например, алгоритм 112 планирования выбирает одно из вычислительных заданий в рабочем списке в соответствии со свободной частью ресурса и критерием загрузки для вычислительных заданий. Могут использоваться и другие критерии выбора. Критерии выбора могут быть следующими (перечень не является исчерпывающим): порядок, в котором задания добавлялись в список, приоритет вычислительного задания (например, приоритет процесса, приоритет потока) и соответствие свободной части ресурса требованиям заданий в части ресурса. Выбор может также осуществляться в соответствии с любой комбинацией таких критериев, а также в соответствии с другими возможными критериями.
ПЛАНИРОВЩИК, ОРИЕНТИРОВАННЫЙ НА РЕСУРСЫ, БЕЗ РАБОЧИХ СПИСКОВ ПЛАНИРОВАНИЯ
В одном из вариантов осуществления изобретения в ПОР 100 отсутствуют рабочие списки планирования, которые соответствуют различным ресурсам компьютера. Как показано на фигуре 1В, ПОР 100 непрерывно принимает текущие запросы на планирование вычислительных заданий, то есть такие запросы поступают неупорядоченно. Например, когда для приложения необходимо выполнение вычислительного задания или заданий, оно направляет запрос в ПОР 100 на планирование одного или нескольких вычислительных заданий. ПОР 100 определяет или получает информацию о том, какой ресурс или ресурсы должны использоваться определенным вычислительным заданием. В качестве примеров ресурсов можно указать процессор 304, накопитель 310, дисплей 312, устройство 314 ввода информации, связной интерфейс 318 и сетевой ресурс 182, к которому может быть обеспечен доступ через сеть 184.
ПОР 100 определяет или получает информацию о загрузке определенного ресурса. ПОР 100 также определяет или получает информацию о критериях загрузки для вычислительного задания в отношении определенного ресурса. На основании загрузки определенного ресурса и критериев загрузки ПОР 100 определяет, можно ли планировать использование определенного ресурса определенным вычислительным заданием. Например, если загрузка связного интерфейса 318 сети удовлетворяет критериям загрузки для вычислительного задания, ПОР 100 планирует выполнение вычислительного задания с использованием связного интерфейса 318 сети. В противном случае ПОР 100 не планирует выполнение вычислительного задания с использованием связного интерфейса 318 сети. В этом случае ПОР 100 находится в режиме ожидания и планирует выполнение вычислительного задания, когда загрузка связного интерфейса 318 сети будет удовлетворять критериям загрузки для вычислительного задания.
НАЗНАЧЕНИЕ ПРИОРИТЕТОВ РЕСУРСОВ
В одном из вариантов осуществления изобретения для целей планирования осуществляется назначение приоритетов ресурсам компьютера. Например, ЦП, дисковая система ввода/вывода, система ввода/вывода сети и другие ресурсы могут ранжироваться в соответствии с относительной скоростью ресурса. Например, дисковая система ввода/вывода работает медленнее, чем ресурс ЦП, и поэтому ей назначается более высокий приоритет. Аналогично, ресурс системы ввода/вывода сети может работать быстрее, чем дисковая система ввода/вывода, но медленнее, чем ресурс ЦП. В этом случае сетевому ресурсу назначается более высокий приоритет, чем ресурсу ЦП, но ниже, чем приоритет дисковой системы ввода/вывода. Если ПОР 100 рассматривает более медленные ресурсы и планирует эти ресурсы с более высокими приоритетами, то может быть минимизирована задержка для более быстрых ресурсов, таких как, например, ЦП.
ПРИМЕР ПЛАНИРОВАНИЯ
Ниже приведен пример планирования, ориентированного на ресурсы, в приложении. Примерами таких приложений может быть программа дефрагментации или антивирусная программа. В этом примере вычислительное задание А находится в самом начале рабочего списка 120(2) планирования для дисковой системы ввода/вывода, и критерий загрузки для этого задания равен 60% свободного ресурса дисковой системы ввода/вывода, а вычислительное задание В стоит следующим в рабочем списке 120(2) планирования для дисковой системы ввода/вывода, и критерий загрузки для этого задания равен 20% свободного ресурса дисковой системы ввода/вывода. Если свободно 30% ресурса дисковой системы ввода/вывода, то ПОР 100 не будет планировать вычислительное задание А, поскольку свободный ресурс для него недостаточен. Однако может быть запланировано для выполнения вычислительное задание В. ПОР 100 в этом случае использует 30% свободного ресурса дисковой системы ввода/вывода путем планирования подходящего вычислительного задания (вычислительного задания В). Если бы ПОР 100 назначил ресурс дисковой системы ввода/вывода вычислительному заданию А, которому необходимо 60% свободной производительности ресурса, то это может вызвать конфликты вычислительных заданий, поскольку было бы распределено более 100% производительности ресурса.
ПЛАНИРОВЩИК, ОРИЕНТИРОВАННЫЙ НА РЕСУРСЫ, НА УРОВНЕ ЯДРА
В одном из вариантов осуществления изобретения ПОР 100 реализуется уровни ядра операционной системы. В таком варианте ПОР 100 располагает полной информацией по всем рабочим спискам вычислительных заданий (например, потоков), которые направляют запросы на выполнение. Таким образом, ПОР 100 может запланировать выполнение заданий в соответствии со свободной производительностью ресурсов без необходимости определять процентное отношение использования каждого ресурса. Это возможно, поскольку ПОР 100 уже имеет полный контроль для планирования различных ресурсов. Нет необходимости в определении, поскольку планировщик располагает всей информацией о назначениях ресурсов.
ОСУЩЕСТВЛЕНИЕ СПОСОБА
На фигуре 2 приведена блок-схема стадий способа 200 планирования, ориентированного на ресурсы, в соответствии с одним из вариантов осуществления настоящего изобретения. Стадии способа 200 рассматриваются ниже в определенном порядке для удобства изложения. Однако стадии могут выполняться и в другом порядке. Кроме того, стадии могут многократно повторяться. На стадии 202 ПОР 100 получает критерии загрузки для одного или нескольких заданий. Например, прикладная программа (приложение) обеспечивает критерии загрузки для ПОР 100. Приложение может задавать различные критерии для разных вычислительных заданий. Приложение необязательно должно задавать критерии загрузки для своих вычислительных заданий.
В соответствии с одним из вариантов осуществления изобретения приложение направляет параметры в ПОР 100 для контроля загрузки ресурса. К таким контролируемым ресурсам относятся, в частности, дисковая система ввода/вывода, ЦП и сеть (перечень не является исчерпывающим). Например, приложение может указать, чтобы вычислительное задание ожидало, пока не будет выполнена какая-либо из комбинаций критериев загрузки, определяемых пороговыми величинами для каждого из вышеуказанных трех ресурсов или для других ресурсов. Кроме того, приложение может задавать различные пороговые величины свободных частей ресурсов для разных вычислительных заданий. Например, в соответствии с одним из вариантов осуществления изобретения приложение указывает различные пороговые величины свободных частей ресурсов для каждого вычислительного задания. Поэтому возможно мелкомодульное управление ресурсами.
На стадии 204 ПОР 100 определяет критерии загрузки для одного или нескольких заданий. В одном из вариантов осуществления изобретения ПОР 100 определяет ожидаемую загрузку определенного ресурса вычислительным заданием, причем критерий загрузки определяется на основании ожидаемой загрузки ресурса. В одном из вариантов осуществления изобретения ПОР 100 определяет ожидаемую загрузку, которая создается определенным вычислительным заданием, путем анализа набора команд этого задания. В одном из вариантов осуществления изобретения ПОР 100 определяет ожидаемую загрузку на основании зарегистрированной величины, которая описывает предыдущее использование ресурса определенным вычислительным заданием.
На стадии 206 вычислительные задания добавляются в рабочие списки планирования, ориентированного на ресурсы. Например, определенный процесс или по меньшей мере потоки определенного процесса записываются по меньшей мере в один рабочий список планирования, ориентированного на ресурсы. По мере того как приходят запросы на планирование заданий, они записываются в рабочие списки планирования, ориентированного на ресурсы. В одном из вариантов осуществления изобретения запросы, поступающие от многих вычислительных заданий, записываются в рабочий список. В одном из вариантов осуществления изобретения запросы могут удовлетворяться путем планирования использования вычислительным заданием определенного ресурса. В одном из вариантов осуществления изобретения место записи вычислительного задания в рабочем списке определяется приоритетом задания. Поскольку порядок выполнения потоков процесса может быть важен, то вычислительные задания (например, потоки) помещаются в рабочий список таким образом, чтобы обеспечить необходимый порядок их выполнения.
На стадии 208 выбирается ресурс компьютера, который должен использоваться. Например, ПОР 100 может определять, что ресурс компьютера, имеющий более низкую производительность, должен иметь более высокий приоритет. Например, ПОР 100 может выбирать ресурс дисковой системы ввода/вывода. Однако выбор может основываться на других факторах, таких как последовательность потоков, приоритет вычислительных заданий (например, приоритет процесса, приоритет потока), число заданий (например, потоков), ожидающих выполнения в каждом рабочем списке, и незанятости других ресурсов, необходимых для задания (например, для потока или процесса).
На стадии 210 ПОР 100 определяет загрузку выбранного ресурса компьютера. Загрузка может определяться на основе активности ресурса в течение только что прошедшего интервала времени. Например, загрузка может определяться по любому подходящему измерению, такому как последний квант “х” времени или последний временной интервал. Однако загрузка не обязательно определяется с использованием временного интервала. Например, загрузка может определяться в соответствии с числом операций, которые ожидают выполнения в определенный момент времени.
В соответствии с одним из вариантов осуществления настоящего изобретения, когда ПОР 100 рассчитывает загрузку ресурса, то это относится к использованию ресурса другими процессами, и не относится к определенному приложению, для которого делается расчет. Для иллюстрации используется следующий пример, в котором пороговая величина загрузки ЦП задается на уровне 20 процентов. Если загрузка ЦП не превышает 20 процентов до разрешения выполнения вычислительных заданий, то эта загрузка может увеличиться и превысить 20 процентов при выполнении этих вычислительных заданий. Такое превышение 20-процентного порога не считается нарушением загрузки ресурса ЦП в данном примере. Аналогичные принципы могут использоваться для сети, дисковой системы ввода/вывода и других ресурсов.
В одном из вариантов осуществления изобретения ПОР 100 оценивает загрузку выбранного ресурса компьютера на следующий интервал времени. ПОР 100 может оценить ожидаемую загрузку по предыдущему использованию ресурса. В качестве конкретного примера измерялась (или определялась иным образом) предыдущая загрузка сетевой системы ввода/вывода. На основании предыдущей загрузки сетевой системы ввода/вывода делается оценка ее ожидаемой загрузки в ближайшее время. Оценка может осуществляться и по другим факторам.
На стадии 212 ПОР 100 выбирает одно из вычислительных заданий в рабочем списке, соответствующем выбранному ресурсу. ПОР 100 планирует выбранное вычислительное задание для выполнения с использованием выбранного вычислительного ресурса. ПОР 100 осуществляет выбор в соответствии с загрузкой определенного ресурса и критерия загрузки по меньшей мере для одного из вычислительных заданий в рабочем списке определенного вычислительного ресурса. Например, если загрузка выбранного ресурса составляет 60%, а критерий загрузки для определенного вычислительного задания - 40%, то есть, ресурс должен быть загружен не более чем на 40%, то определенное вычислительное задание не планируется, поскольку критерий загрузки не выполняется. В этом случае ПОР 100 может выбрать другое вычислительное задание и запланировать его для выполнения, если загрузка в 60% для выбранного ресурса удовлетворяет критерию загрузки для этого другого вычислительного задания.
Повторяя по меньшей мере некоторые стадии способа 200 для планирования одного за другим вычислительных заданий, ПОР определяет порядок их выполнения.
На стадии 214 ПОР 100 сохраняет информацию загрузки ресурса для вычислительного задания, которое только что выполнялось. ПОР 100 может использовать эту информацию загрузки ресурса впоследствии для определения критериев загрузки для вычислительного задания.
МИКРОЗАДАНИЯ
В одном из вариантов осуществления изобретения ПОР 100 осуществляет планирование микрозаданий. В одном из вариантов осуществления изобретения микрозадания имеют такой размер, который позволяет полностью выполнить определенное микрозадание в течение выделенного интервала времени, в котором такое микрозадание использует ресурс, необходимый для его выполнения. В одном из вариантов осуществления изобретения каждое микрозадание имеет такой размер, который позволяет полностью выполнить его в течение выделенного интервал времени. Однако может оказаться, что некоторые из микрозаданий слишком велики и не могут быть полностью выполнены в течение выделенного времени.
В одном из вариантов осуществления изобретения для выделения микрозаданий выделяется квант времени. Квант - это малый временной интервал, выделяемый для части кода программы (например, потока), в течение которого эта часть кода пользуется ресурсом ЦП. Различные операционные системы используют разные кванты времени. Кроме того, квант, выделяемый определенной части кода, может изменяться в зависимости от событий при ее выполнении. Например, операционная система может увеличивать или уменьшать размер кванта, выделенного для потока. В одном из вариантов осуществления изобретения вычислительное задание разбивается на микрозадания, соответствующие размеру кванта, который предполагается выделить для вычислительного задания. В другом варианте осуществления изобретения вычислительное задание разбивается на микрозадания, соответствующие размеру кванта, который выделен для вычислительного задания. Части (микрозадания) вычислительного задания, на которые его необходимо разбить, могут быть определены либо до выполнения вычислительного задания, либо в процессе его выполнения.
Микрозадания представляют собой существенно меньшие по размерам (например, наименьшие) единицы работы, которая может быть выполнена как единое целое, после чего в соответствии с одним из вариантов осуществления изобретения может быть взят перерыв до выполнения следующего микрозадания без каких-либо негативных последствий. Перерыв без каких-либо негативных последствий означает, что выполнение определенного микрозадания может быть задержано без ущерба для результата выполнения всех микрозаданий.
Микрозадание может быть частью потока. Например, поток может быть разбит на несколько микрозаданий. Планирование этих микрозаданий может быть аналогичным планированию потока. Однако, как уже указывалось, микрозадание будет выполнено полностью, если оно будет выполняться в течение кванта времени или другого промежутка времени, в течение которого оно будет использовать ресурс обработки информации.
Микрозаданию каждый раз может требоваться для выполнения лишь небольшое количество ресурсов (например, время ЦП, выделенная память). Такое минимальное использование ресурсов в любой момент времени обеспечивает выполнение микрозаданий с минимальным влиянием на выполнение других приложений или заданий. Малые размеры микрозаданий обеспечивают использование вычислительными заданиями за один раз всего лишь малой части ресурсов компьютера. Поэтому при выполнении микрозадания потребляется достаточно малая часть ресурсов, так что в соответствии с одним вариантом осуществления изобретения не происходит существенного влияния на работу других приложений в компьютерной системе.
ПРИМЕР API
Вариантом осуществления настоящего изобретения является прикладной программный интерфейс (API), который обеспечивает задание приложением различных параметров загрузки ресурсов. В одном из вариантов осуществления изобретения в состав ПОР 100 входит такой API. Приложения могут использовать API для задания критериев загрузки для вычислительных заданий (например, процессов, потоков, микрозаданий или других частей кодов программ). Пример API характеризуется следующими пороговыми параметрами для ЦП, диска и сети:
пороговая величина загрузки ЦП;
пороговая величина времени ожидания при обращении к дисковой системе ввода/вывода;
пороговая величина загрузки сети.
Указанные параметры могут быть заданы для каждого вычислительного задания. Например, для вычислительного задания, использующего сеть, может использоваться пороговая величина загрузки сети. Однако пороговое значение загрузки сети может быть равно нулю для вычислительных заданий, которые не используют сеть. Поэтому в одном из вариантов осуществления настоящего изобретения предусматривается мелкомодульное управление ресурсами.
Например, приложение может запрашивать выполнение определенного вычислительного задания только в том случае, когда загрузка ЦП не превышает 50%, загрузка дисковой системы ввода/вывода не превышает 40% и интенсивность сетевого трафика не выше 60%. Могут использоваться любые комбинации пороговых параметров ресурсов, включая отсутствие каких-либо параметров. В соответствии с одним из вариантов осуществления настоящего изобретения пороговая величина загрузки ЦП устанавливает различие в использовании ЦП планировщиком, ориентированным на ресурсы, и какими-либо другими заданиями. Нижеуказанные два параметра используются для задания интервала, на котором должно осуществляться измерение загрузки ресурса:
интервал для загрузки ЦП;
интервал для загрузки сети.
Интервал для загрузки ЦП определяет временное окно, в котором вычисляется загрузка ЦП. Например, осуществляется усреднение загрузки ЦП за последние n миллисекунд. Интервал для загрузки сети определяет временное окно, в котором вычисляется загрузка сети. Эти параметры могут быть внутренними параметрами ПОР 100. Однако приложение может игнорировать эти параметры. Ожидание дисковой системы ввода/вывода в любой момент времени является абсолютной величиной, и поэтому вычисление этой величины не требуется.
Параметр обязательного времени незанятости может быть передан из приложения в ПОР для контроля распределения вычислительных заданий по времени. Параметр обязательного времени незанятости не является обязательным. Более того, параметр обязательного времени незанятости, если он используется, может быть равен нулю.
Обязательное время незанятости
ПОР отслеживает “время незанятости”, которое определяется как время бездействия системы после выполнения вычислительных заданий. Например, вычислительные задания приложения могут размещаться в рабочих списках ПОР. Когда в списках 120 планирования, ориентированного на ресурсы, нет вычислительных заданий для выполнения, то ПОР ждет в течение заданного обязательного времени незанятости, а затем включается и дает разрешение приложениям на выполнение дополнительной работы. Например, приложение дефрагментации может сначала выполнить несколько вычислительных заданий по дефрагментации диска, а затем будет переведено ПОР в режим ожидания. По прошествии заданного обязательного времени незанятости ПОР вызывает приложение дефрагментации для разрешения выполнения дополнительной работы. Например, приложение дефрагментации может выполнить такое задание, как освобождение памяти. Обязательное время незанятости может быть параметром по умолчанию, который может изменяться приложением.
Нижеуказанные параметры относятся к ожиданию выполнения вычислительного задания, когда загрузка ресурсов превышает заданные пороговые величины:
время ожидания;
максимальное время ожидания.
Если ПОР определяет, что текущая загрузка ресурса слишком высока для выполнения вычислительного задания, то он ожидает в течение заданного времени ожидания и затем снова проверяет загрузку ресурса. Параметр времени ожидания может увеличиваться каждый раз, когда ПОР определяет, что загрузка ресурса слишком высока. Например, ПОР может увеличивать время ожидания, пока не будет достигнуто максимальное значение времени ожидания. Эти параметры могут быть заданы приложением, когда оно запускается в первый раз. Приложение в процессе своей работы может изменять эти параметры.
Хотя в рассмотренном примере API используется время (например, мс) для задания различных параметров, однако могут использоваться и другие единицы измерения, например кванты.
МОДИФИКАЦИИ
В одном из вариантов осуществления изобретения ПОР 100 входит в состав операционной системы. В другом варианте ПОР 100 является автономным приложением, которое облегчает планирование вычислительных заданий для других приложений. Еще в одном варианте осуществления изобретения ПОР 100 встроен в прикладную программу и осуществляет планирование для этой программы. Например, ПОР 100 может быть встроен в программу дефрагментации диска или в антивирусную программу.
В одном из вариантов осуществления изобретения, если ПОР 100 выполняется отдельно от операционной системы, он осуществляет ограничение своего использования как ресурса. Например, ПОР 100 контролирует обращения к себе как к ресурсу, и если использование этого ресурса становится слишком интенсивным, то ПОР 100 делает запрос в операционную систему на прекращение планирования ПОР 100 в течение некоторого времени.
ДОПОЛНИТЕЛЬНЫЕ ПРИМЕРЫ
Следующие примеры иллюстрируют возможные варианты работы ПОР 100. Однако ПОР 100 не обязательно должен работать так, как описано в этих примерах. Например, ПОР 100 может планировать несколько вычислительных заданий одного приложения. Для некоторых из этих вычислительных заданий может потребоваться дисковая система ввода/вывода. ПОР 100 может анализировать загрузку диска в качестве условия для планирования вычислительных заданий. Если загрузка диска слишком высока, то ПОР 100 ожидает, пока она не снизится, и затем планирует определенное вычислительное задание приложения. ПОР 100 продолжает контроль использования дисковой системы ввода/вывода, и разрешает включение другого вычислительного задания, если ни одно другое приложение не требует доступа к дисковой системе ввода/вывода. Однако если другому приложению необходимо использовать дисковую систему ввода/вывода, то ПОР 100 в этом варианте осуществления изобретения не выполняет планирование другого вычислительного задания. Таким образом, другие приложения могут использовать дисковую систему ввода/вывода.
В другом примере ПОР 100 может анализировать активность сети. Если сетевой трафик слишком интенсивен, то ПОР 100 не будет планировать выполнение какого-либо вычислительного задания, пока трафик не снизится. Если сетевой трафик достаточно низкий, то ПОР 100 планирует выполнение вычислительного задания. ПОР 100 продолжает контролировать сетевой трафик, чтобы убедиться, что он остается достаточно низким. Если сетевой трафик остается достаточно низким, то может быть разрешено включение другого вычислительного задания. Однако если сетевой трафик становится высоким, выполнение других вычислительных заданий не планируется. В этих двух примерах вычислительное задание может быть микрозаданием. Однако это не обязательно.
ОПИСАНИЕ АППАРТАНЫХ СРЕДСТВ
На фигуре 3 приведена блок-схема, иллюстрирующая структуру вычислительной системы 300, в которой может быть осуществлено изобретение. Стадии способа 200 запоминаются в форме команд на одном или нескольких машиночитаемых носителях вычислительной системы 300 и выполняются ее процессором. Компьютерная система 300 содержит шину 302 или другое средство передачи информации в системе, и процессор 304 соединен с шиной 302 для обработки информации. Компьютерная система 300 также содержит основное запоминающее устройство 306, такое как, например, оперативное запоминающее устройство (ОЗУ) или другое устройство динамической памяти, соединенное с шиной 302 для хранения информации и команд, которые должны выполняться процессором 304. Основное запоминающее устройство 306 также может использоваться для хранения временных переменных или другой промежуточной информации, получаемой при выполнении команд процессором 304. Компьютерная система 300 также содержит постоянное запоминающее устройство (ПЗУ) 308 или другое статическое запоминающее устройство, подключенное к шине 302, для хранения постоянной информации и команд для процессора 304. Кроме того, имеется запоминающее устройство 310, такое как, например, накопитель на магнитных или оптических дисках, подсоединенный к шине 302, для хранения информации и команд. Компьютерная система 300 может иметь любое число процессоров 304. Например, в одном из вариантов осуществления изобретения компьютерная система 300 может быть многопроцессорной системой. Процессор 304 может иметь любое количество ядер. В одном из вариантов осуществления изобретения в качестве процессора 304 используется многоядерный процессор. Компьютерная система 300 может использоваться в машинах с параллельной обработкой (hyper threaded).
Компьютерная система 300 может быть соединена по шине 302 с дисплеем 312, таким как, например, электронно-лучевая трубка для отображения информации для пользователя компьютера. К шине 302 подсоединено устройство 314 ввода информации, в частности цифробуквенная или иная клавиатура, для передачи информации в процессор 304 и задания команд. Другим видом устройства ввода информации пользователем является устройство 316 управления курсором, такое как, например, мышь, трекбол или клавиши управления перемещениями курсора для ввода управляющей информации в процессор 304 и для управления перемещениями курсора на дисплее 312. Устройство ввода информации обычно имеет две степени свободы по двум осям: первая ось (например, ось х) и вторая ось (например, ось у), что обеспечивает задание с помощью устройства положений в плоскости.
Изобретение относится к использованию компьютерной системы 300 для осуществления описанных в нем способов. В соответствии с одним из вариантов осуществления изобретения эти способы осуществляются вычислительной системой 300 путем выполнения процессором 304 одной или нескольких последовательностей команд, содержащихся в основной оперативной памяти 306. Эти команды могут быть записаны в основную оперативную память 306 из другого машиночитаемого носителя информации, такого как, например, запоминающее устройство 310. Выполнение последовательностей команд, находящихся в основной оперативной памяти 306, обеспечивает выполнение процессором 304 стадий рассмотренных способов. В альтернативных вариантах осуществления изобретения может использоваться аппаратная реализация алгоритмов вместо последовательностей команда, записанных в оперативной памяти. Таким образом, варианты осуществления изобретения не ограничиваются какими-либо конкретными комбинациями аппаратных средств и программного обеспечения.
Под используемым в описании термином “машиночитаемый носитель” понимается любой носитель, который участвует в обеспечении данных, которые позволяют вычислительной системе выполнять заданные действия. В варианте осуществления изобретения с использованием вычислительной системы 300 используются различные машиночитаемые носители информации, например, для обеспечения команд, выполняемых процессором 304. Такие носители могут иметь различные формы, в том числе носители, сохраняющие информацию при отключении питания, носители, теряющие информацию при отключении питания, и средства передачи информации. К носителям, сохраняющим информацию при отключении питания, относятся, например, накопители на оптических или магнитных дисках, такие, как запоминающее устройство 310. К носителям, теряющим информацию при отключении питания, относятся устройства динамической памяти, такие как основная оперативная память 306. К средствам передачи информации относятся коаксиальные кабели, медные и волоконно-оптические проводники, в том числе провода, составляющие шину 302. В качестве средств передачи информации могут использоваться акустические или световые волны, такие как, например, радиоволны или инфракрасные волны. Все такие средства должны быть материальными для обеспечения считывания команд, передаваемых такими носителями, в вычислительную систему.
Типичными видами машиночитаемых носителей являются, например, накопители на гибких дисках, накопители на жестких дисках, накопители на магнитной ленте или на других магнитных носителях, диски CD-ROM, любые другие оптические носители, перфокарты, перфоленты и любые другие физические носители, на которых информация записывается в форме отверстий, ОЗУ, ППЗУ, устройства флеш-памяти и другие чипы или картриджи памяти, колебания, переносящие информацию (см. ниже), или любой другой носитель, с которого компьютер может считывать информацию.
Передача одной или нескольких последовательностей команд для их выполнения процессором 304 может осуществляться с использованием различных форм машиночитаемых носителей. Например, команды могут первоначально находиться на магнитном диске удаленного компьютера. Удаленный компьютер может загрузить команды в свою динамическую память и передать их по телефонной линии с использованием модема. Эти данные могут приниматься из телефонной линии модемом вычислительной системы 300 и затем преобразовываться в инфракрасные сигналы. Эти сигналы могут приниматься инфракрасным датчиком, и полученные данные с помощью соответствующих схем могут передаваться в шину 302. По шине 302 данные поступают в устройство 306 оперативной памяти, из которой они выбираются процессором 304, выполняющим команды. Команды, поступившие в основное устройство 306 оперативной памяти, могут дополнительно запоминаться в запоминающем устройстве 310 перед их выполнением процессором 304 или после выполнения.
Вычислительная система 300 также содержит связной интерфейс 318, соединенный с шиной 302. Связной интерфейс 318 обеспечивает двухсторонний обмен информацией с устройством 320 сопряжения с сетью, соединенным с локальной сетью 322. Например, связной интерфейс 318 может быть платой цифровой сети с интеграцией служб (ISDN) или модемом для обеспечения соединения с соответствующей телефонной линией для обмена информацией. В другом варианте связной интерфейс 318 может быть картой локальной сети (LAN) для обеспечения соединения с совместимой LAN для обмена информацией. Также могут использоваться средства беспроводной связи. В любом таком варианте осуществления изобретения связной интерфейс 318 обеспечивает цередачу и прием электрических, электромагнитных или оптических сигналов, несущих потоки цифровых данных, представляющих различные виды информации.
Устройство 320 сопряжения с сетью обычно обеспечивает обмен данными через одну или несколько сетей с другими информационными устройствами. Например, устройство 320 сопряжения с сетью может обеспечивать соединение через локальную сеть 322 с главным компьютером 324 или с оборудованием данных, эксплуатируемым провайдером 326 услуг сети Интернет Провайдер 328, в свою очередь обеспечивает услуги по обмену данными по глобальной сети передачи пакетов данных, которая сейчас обычно называется сетью Интернет (528). Локальная сеть 322 и сеть Интернет используют электрические, электромагнитные или оптические сигналы, переносящие потоки цифровых данных. Сигналы, передаваемые по различным сетям, сигналы в устройстве 320 сопряжения с сетью и сигналы, передаваемые по связному интерфейсу 318, которые несут цифровые данные, поступающие в вычислительную систему 300 и передаваемые из нее, являются примерами носителей, транспортирующих информацию.
Вычислительная система 300 может передавать сообщения и принимать данные, используя программный код, через сети, устройство 320 сопряжения с сетями и связной интерфейс 318. В случае сети Интернет код, запрошенный прикладной программой, может передаваться сервером 330 через сеть Интернет, провайдера 326, локальную сеть 322 и связной интерфейс 318.
Принятый код может быть сразу выполнен процессором 304 и/или сохранен в запоминающем устройстве 310, или в другом запоминающем устройстве, сохраняющем информацию при выключении питания, для последующего выполнения. Таким образом, вычислительная система 300 может получать код прикладной программы в виде несущей волны.
В вышеприведенном описании варианты осуществления изобретения были раскрыты со ссылками на многочисленные конкретные признаки, которые могут меняться от одного варианта к другому. Таким образом, единственным и исключительным указателем объема изобретения является его формула, которая выведена из настоящей заявки, с любыми последующими корректировками. Любые определения, указанные в явной форме в настоящем описании, для терминов, содержащихся в формуле, устанавливают смысл таких терминов в том виде, как они используются в формуле. Следовательно, никакие ограничения, элементы, свойства, признаки, положительные качества или характеристики, которые не указаны в явной форме в каком-либо пункте формулы изобретения, никоим образом не должны ограничивать объем изобретения. Соответственно, описание и чертежи должны рассматриваться скорее как иллюстративные материалы, а не как ограничивающие объем изобретения.