Способ и система для планирования передачи операций ввода/вывода

Изобретение относится к средствам планирования передачи множества операций ввода/вывода (I/O), предназначенных для выполнения устройством хранения данных. Технический результат заключается в уменьшении времени реакции при выполнении задачи, направленной в устройство хранения и сокращение времени зависание задач. Применяют для последовательных операций I/O из запланированной последовательности скользящего ячейкового окна, размещаемого на последовательных операциях I/O, начиная с первой операции I/O. Передают в устройство хранения данные последовательных операций I/O. Принимают подтверждение выполнения операции от устройства хранения данных. Определяют позицию ячейки скользящего ячейкового окна, связанной с операцией I/O. Если позиция этой ячейки соответствует первой позиции в скользящем ячейковом окне, то осуществляют сдвиг скользящего ячейкового окна на множестве операций I/O так, чтобы в результате окно содержало по меньшей мере одну дополнительную операцию I/O. Передают в устройство хранения данные этой по меньшей мере одной дополнительной операции I/O для выполнения. 2 н. и 24 з.п. ф-лы, 6 ил.

 

Область техники

Данная технология относится в целом к обработке данных и, в частности, к способам и системам для планирования и управления передачей операций ввода/вывода для их выполнения неуправляемым устройством.

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

Операции ввода/вывода (I/O, Input/Output) относятся к операциям считывания или записи, выполняемым, например, обрабатывающим элементом в устройстве хранения данных. В общем случае такие операции планируются операционными системами, выполняющими алгоритмы планирования операций I/O, чтобы определить последовательность операций I/O, передаваемых для обработки в устройства хранения данных. Для сокращения до минимума непроизводительных затрат времени в устройстве хранения данных, такие известные процессы стремятся назначить приоритеты запросам определенных процессов на операции I/O, например, чтобы сократить до минимума физическое перемещение головок накопителей на жестких дисках (HDD, Hard Disk Drive), чтобы разделить производительность диска с другими процессами и чтобы гарантировать выдачу определенных запросов до истечения конкретного предельного срока. Этот процесс обычно приводит к формированию очереди операций I/O, которая определяет порядок передачи операций I/O в дисковую подсистему, содержащую устройства хранения данных (такие как HDD, твердотельные накопители (SSD, Solid-State Drive) и т.п.).

В целом, устройства хранения данных для селективного выбора порядка выполнения операций из очереди операций I/O используют собственное внутреннее логическое устройство, способное выбирать наиболее выгодные операции I/O для выполнения на каждой итерации, например, чтобы оптимизировать производительность устройства хранения данных или для других целей. В результате устройство хранения данных может пропускать выполнение менее выгодных с точки зрения внутреннего логического устройства операций I/O из запланированной последовательности операций. Таким образом, менее выгодные операции I/O из запланированной последовательности могут оставаться необработанными в устройстве хранения данных в течение длительного времени. Например, на каждой итерации внутреннее логическое устройство может выбирать наиболее выгодную операцию I/O и вследствие постоянного пополнения последовательности операций менее выгодная операция I/O может «зависнуть» в такой последовательности на некоторое время из-за значительного нарушения порядка. В результате предельный срок выполнения, связанный с «зависшей» операцией I/O, может быть пропущен.

В патенте США № 8117621 В2 «Simulating a multi-queue scheduler using a single queue on a processor», выданном 14 февраля 2012 г. компании International Business Machines Corp., описаны способ и система для планирования задач в процессоре, при этом задачи планируются операционной системой для выполнения в процессоре в предварительно определенном порядке. Способ включает в себя определение и создание групп из всех соответствующих задач; назначение задач из этих групп в единую общую очередь выполнения; выбор задачи в начале очереди выполнения; определение возможности выполнения задачи в начале очереди выполнения на основе заранее заданного выделенного временного интервала и в зависимости от наличия более ранних «зависших» задач в очереди выполнения; выполнение этой задачи в течение заранее заданного временного интервала; назначение состояния «зависшая» всем невыполненным задачам и выполнение всех задач, пока не будет завершено выполнение всех задач из очереди задач и очередь задач не опустеет.

В патентной заявке США № 2017/0031713 A1 «Task scheduling)) компании Arm Ltd., опубликованной 2 февраля 2017 г., описано устройство, содержащее схему планирования, которая выбирает для выполнения задачу из множества задач в очереди, каждая из которых имеет соответствующий приоритет, в зависимости от соотношения приоритетов задач в очереди. Схема увеличения повышает соответствующий приоритет каждой задачи из множества задач в очереди по истечении некоторого периода времени. Множество задач в очереди включает в себя чувствительную к задержке задачу с соответствующим предельным сроком, по достижении которого схема планирования выбирает для выполнения эту чувствительную к задержке задачу.

В патенте США № 9639396 «Starvation control in a data processing system», выданном 2 мая 2017 г. компании NXP USA Inc., описана система обработки данных, содержащая основной список задач, основную схему планирования, список зависших задач и вспомогательную схему планирования. Способ включает в себя определение потенциально зависших задач в основном списке и занесение их в список зависших задач. Подсистема контроля зависаний управляет зависанием задач в системе путем определения момента времени для использования вспомогательной схемы планирования с целью планирования для выполнения в центральном процессоре задачи с наивысшем приоритетом из списка зависших задач перед планированием основной схемой планирования выполнения других задач из основного списка. Подсистема контроля зависаний определяет сколько раз вместо задачи из основного списка, запланированной для выполнения в центральном процессоре, выполнялись другие задачи из основного списка. Счетчик увеличивается при каждом выполнении в центральном процессоре задачи не из списка зависших задач.

Раскрытие изобретения

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

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

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

В частности, согласно данной технологии предлагается применение «скользящего окна» для запланированной последовательности операций I/O, чтобы селективно передавать некоторое количество операций I/O для их выполнения неуправляемым устройством хранения данных. Благодаря такому скользящему окну возможно принудительное выполнение неуправляемым устройством хранения данных только тех операций I/O, которые оказываются в скользящем окне.

В соответствии с первым аспектом данной технологии реализован способ планирования передачи множества операций I/O, предназначенных для выполнения устройством хранения данных. Устройство хранения данных входит в состав компьютерной системы, которая содержит планировщик операций, выполняющий алгоритм планирования с целью планирования множества операций I/O для их передачи в устройство хранения данных и способный формировать запланированную последовательность, содержащую множество операций I/O, упорядоченных, начиная с первой операции I/O, предназначенной для передачи, и заканчивая последней операцией I/O, предназначенной для передачи. Компьютерная система содержит диспетчерский контроллер операций I/O, связанный с планировщиком операций и с устройством хранения данных. Устройство хранения данных способно выполнять алгоритм упорядочивания выполнения с целью определения порядка выполнения операций I/O, передаваемых из планировщика операций для выполнения. Способ выполняется диспетчерским контроллером операций I/O и включает в себя: применение скользящего N-ячейкового окна для выбора N последовательных операций I/O из запланированной последовательности, при этом N скользящих ячеек размещаются на N последовательных операциях I/O, начиная с первой операции I/O, и каждая ячейка скользящего окна содержит одну соответствующую операцию из N последовательных операций I/O. Способ включает в себя передачу в устройство хранения данных N последовательных операций I/O. Способ включает в себя прием от устройства хранения данных подтверждения выполнения, указывающего, что данная операция I/O из N последовательных операций I/O обработана устройством хранения данных. Способ включает в себя определение позиции ячейки скользящего N-ячейкового окна, связанной с данной операцией I/O. Если эта позиция ячейки соответствует первой позиции среди позиций ячеек скользящего N-ячейкового окна, способ включает в себя сдвиг скользящего N-ячейкового окна на множестве операций I/O так, чтобы скользящее N-ячейковое окно содержало по меньшей мере одну дополнительную операцию I/O, которая в запланированной последовательности множества операций I/O следует непосредственно за N последовательными операциями I/O. Способ включает в себя передачу в устройство хранения данных этой по меньшей мере одной дополнительной операции I/O для выполнения.

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

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

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

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

В некоторых вариантах осуществления способа диспетчерский контроллер операций I/O реализован в виде программного модуля.

В некоторых вариантах осуществления способа диспетчерский контроллер операций I/O реализован в виде конечного автомата.

В некоторых вариантах осуществления способа программный модуль находится в устройстве хранения данных.

В некоторых вариантах осуществления способа алгоритм планирования основан на принципе «справедливости».

В некоторых вариантах осуществления способа устройство хранения данных реализовано в виде отказоустойчивого устройства.

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

В некоторых вариантах осуществления способа он дополнительно включает в себя выполнение устройством хранения данных данной операции I/O.

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

В соответствии со вторым аспектом данной технологии реализована система для планирования передачи множества операций I/O, предназначенных для выполнения устройством хранения данных, связанным с этой системой. Система содержит планировщик операций, выполняющий алгоритм планирования с целью планирования множества операций I/O для их передачи в устройство хранения данных, при этом планировщик операций способен формировать запланированную последовательность, содержащую множество операций I/O, упорядоченных, начиная с первой операции I/O, предназначенной для передачи, и заканчивая последней операцией I/O, предназначенной для передачи. Система содержит диспетчерский контроллер операций I/O, связанный с планировщиком операций и с устройством хранения данных. Устройство хранения данных способно выполнять алгоритм упорядочивания выполнения с целью определения порядка выполнения операций I/O, переданных из планировщика операций для выполнения. Система содержит процессор и машиночитаемый физический носитель информации, содержащий команды, при выполнении которых процессор инициирует применение диспетчерским контроллером операций I/O скользящего N-ячейкового окна для выбора N последовательных операций I/O из запланированной последовательности, при этом N скользящих ячеек размещаются на N последовательных операциях I/O, начиная с первой операции I/O, и каждая ячейка скользящего окна содержит одну соответствующую операцию из N последовательных операций I/O. Процессор способен инициировать передачу диспетчерским контроллером операций I/O в устройство хранения данных N последовательных операций I/O. Процессор способен принимать от устройства хранения данных подтверждение выполнения, указывающее, что данная операция I/O из N последовательных операций I/O обработана устройством хранения данных. Процессор способен инициировать определение диспетчерским контроллером операций I/O позиции ячейки скользящего N-ячейкового окна, связанной с данной операцией I/O. Процессор способен инициировать, если позиция данной ячейки соответствует первой позиции среди позиций ячеек скользящего N-ячейкового окна, выполнение диспетчерским контроллером операций I/O сдвига скользящего N-ячейкового окна на множестве операций I/O так, чтобы скользящее N-ячейковое окно содержало по меньшей мере одну дополнительную операцию I/O, непосредственно следующую за N последовательными операциями I/O в запланированной последовательности множества операций I/O. Процессор способен инициировать передачу диспетчерским контроллером операций I/O в устройство хранения данных этой по меньшей мере одной дополнительной операции I/O для выполнения.

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

В некоторых вариантах осуществления системы запланированная последовательность содержит упомянутую по меньшей мере одну дополнительную операцию I/O. Передача этой по меньшей мере одной дополнительной операции I/O в устройство хранения данных выполняется одновременно с приемом подтверждения выполнения.

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

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

В некоторых вариантах осуществления системы диспетчерский контроллер операций I/O реализован в виде программного модуля.

В некоторых вариантах осуществления системы диспетчерский контроллер операций I/O реализован в виде конечного автомата.

В некоторых вариантах осуществления системы программный модуль находится в устройстве хранения данных.

В некоторых вариантах осуществления системы алгоритм планирования основан на принципе «справедливости».

В некоторых вариантах осуществления системы устройство хранения данных реализовано в виде отказоустойчивого устройства.

В некоторых вариантах осуществления системы алгоритм упорядочивания выполнения не управляется планировщиком задач.

В некоторых вариантах осуществления системы процессор дополнительно способен инициировать операции I/O с целью выполнения данной операции I/O устройством хранения данных.

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

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

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

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

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

В контексте настоящего описания выражение «пригодный для использования в компьютере носитель информации» относится к носителям любого типа и вида, включая ОЗУ, ПЗУ, диски (CD-ROM, DVD, гибкие диски, жесткие диски и т.д.), USB-накопители, твердотельные накопители, накопители на магнитных лентах и т.д.

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

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

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

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

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

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

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

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

На фиг. 3 приведена схема приложения обеспечения работы в реальном времени, выполняемого представленной на фиг. 1 системой распределенной компьютерной обработки данных согласно вариантам осуществления данной технологии, не имеющим ограничительного характера.

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

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

На фиг. 6 приведена блок-схема способа планирования передачи множества операций I/O для выполнения устройством хранения данных, выполняемого в представленной на фиг. 1 системе в соответствии с вариантами осуществления данной технологии.

Осуществление изобретения

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

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

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

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

Система 100 распределенной обработки данных содержит источник 102 запросов, сеть 103 связи, подсистему 104 предварительной обработки запросов, подсистему 105 обработки транзакций, подсистему 106 маршрутизации транзакций, подсистему 108 распределенного хранения данных, подсистему 110 базы данных и операционную подсистему 111.

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

Источник запросов

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

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

В некоторых вариантах осуществления данной технологии, когда система 100 распределенной обработки данных используется в среде бизнес-потребитель (В2С, Business-to-Customer), источник 102 запросов может представлять собой клиентское устройство, такое как смартфон, связанное с пользователем системы 100 распределенной обработки данных. Например, система 100 распределенной обработки данных может обеспечивать услуги «облачного» хранения данных для клиентского устройства определенного пользователя.

В некоторых вариантах осуществления данной технологии, когда система 100 распределенной обработки данных используется в среде бизнес-бизнес (В2В, Business-to-Business), источник 102 запросов может представлять собой подсистему, такую как удаленный сервер, обеспечивающую пользовательские запросы к системе 100 распределенной обработки данных. Например, в некоторых вариантах осуществления данной технологии система 100 распределенной обработки данных может обеспечивать услуги отказоустойчивой обработки и/или хранения данных для оператора такой подсистемы.

В целом, независимо от реализации системы 100 распределенной обработки данных в виде системы В2С или В2В (или любого другого варианта системы), источник 102 запросов может представлять собой клиентское устройство или другую подсистему, которые могут быть внутренними или внешними по отношению к системе 100 распределенной обработки данных.

Как указано выше, источник 102 запросов способен выдавать множество запросов 180, каждый из которых далее называется запросом 180. Характер запроса 180 зависит от вида источника 102 запросов. В частности, один из примеров запроса 180 представляет собой запрос, составленный на языке структурированных запросов (SQL, Structured Query Language). Поэтому предполагается, что в некоторых вариантах осуществления данной технологии запрос 180 может быть составлен на языке декларативного программирования, т.е. запрос 180 может представлять собой запрос декларативного вида.

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

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

В качестве не имеющих ограничительного характера примеров можно привести следующие запросы декларативного вида: «Вставить значение 5 в ячейку, связанную с ключом, который равен значению ячейки, связанной с ключом А» и «Для всех ключей, связанных с ячейкой, имеющей значение 5, заменить это значение на значение 10». Тем не менее, должно быть понятно, что представленные выше примеры декларативных языков и примеры запросов декларативного вида приведены исключительно для лучшего понимания, и что другие декларативные языки и другие запросы декларативного вида могут использоваться источником 102 запросов в пределах объема данной технологии.

В некоторых вариантах осуществления данной технологии источник 102 запросов также способен принимать множество ответов 181, каждый из которых далее называется ответом 181. В общем случае в ответ на запрос 180, обработанный или не обработанный системой 100 распределенной обработки данных, система 100 распределенной обработки данных может формировать ответ 181, предназначенный для источника 102 запросов, связанного с соответствующим запросом 180. Характер ответа 181, среди прочего, зависит от вида источника 102 запросов, вида соответствующего запроса 180 и от того, обработала или не обработала система 100 распределенной обработки данных соответствующий запрос 180. В некоторых вариантах осуществления данной технологии система 100 распределенной обработки данных может формировать ответ 181, только если не удалось обработать запрос, или только в случае успешной обработки запроса, или в обоих случаях.

Например, во время обработки запроса 180 система 100 распределенной обработки данных может быть способна запрашивать дополнительные данные от источника 102 запросов для продолжения или завершения обработки запроса 180. В этом случае система 100 распределенной обработки данных может быть способна формировать ответ 181 в виде сообщения с запросом данных, в котором указываются дополнительные данные, запрашиваемые системой 100 распределенной обработки данных для продолжения или завершения обработки запроса 180.

В другом примере, если система 100 распределенной обработки данных успешно обработала соответствующий запрос 180, система 100 распределенной обработки данных может быть способна формировать ответ 181 в виде сообщения об успешном завершении, оповещающего об успешной обработке соответствующего запроса 180.

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

Сеть связи

Источник 102 запросов связан с сетью 103 связи для направления запроса 180 в систему 100 распределенной обработки данных и для приема ответа 181 от системы 100 распределенной обработки данных. В некоторых не имеющих ограничительного характера вариантах осуществления данной технологии в качестве сети 103 связи может использоваться сеть Интернет. В других не имеющих ограничительного характера вариантах осуществления данной технологии сеть 103 связи может быть реализована иначе, например, в виде любой глобальной сети связи, локальной сети связи, частной сети связи и т.п. Реализация линии связи (отдельно не обозначена) между источником 102 запросов и сетью 103 связи зависит, среди прочего, от реализации источника 102 запросов.

Лишь в качестве примера, не имеющего ограничительного характера, в тех вариантах осуществления данной технологии, где источник 102 запросов реализован как беспроводное устройство связи (такое как смартфон), линия связи может быть реализована как беспроводная линия связи (такая как канал сети связи 3G, канал сети связи 4G, Wireless Fidelity или сокращенно WiFi^®, Bluetooth^® и т.п.). В тех примерах, где источник 102 запросов реализован как удаленный сервер, линия связи может быть беспроводной (такой как Wireless Fidelity или сокращенно WiFi^®, Bluetooth^® и т.д.) или проводной (такой как соединение по сети Ethernet).

Следует отметить, что сеть 103 связи, среди прочего, способна передавать пакет данных запроса, содержащий запрос 180, из источника 102 запросов в подсистему 104 предварительной обработки запросов системы 100 распределенной обработки данных. Например, этот пакет данных запроса может содержать выполняемые компьютером команды, составленные на языке программирования декларативного типа, на котором представлен запрос 180. Сеть 103 связи, среди прочего, также способна передавать пакет данных ответа, содержащий ответ 181, из системы 100 распределенной обработки данных в источник 102 запросов. Например, этот пакет данных ответа может содержать выполняемые компьютером команды, представляющие ответ 181.

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

Операционная подсистема (улей)

Как указано выше, система 100 распределенной обработки данных содержит операционную подсистему 111 или, сокращенно, улей. В общем случае улей 111 представляет собой программное приложение (например, конечный автомат), способное управлять по меньшей мере некоторыми подсистемами системы 100 распределенной обработки данных, такими как подсистема 104 предварительной обработки запросов и подсистема 105 обработки транзакций. Можно сказать, что улей 111 может быть реализован как конечный автомат (SM, State Machine), способный формировать, удалять и/или выравнивать нагрузку других автоматов SM, образующих по меньшей мере некоторые подсистемы системы 100 распределенной обработки данных.

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

Следует отметить, что в контексте данной технологии автоматы SM, образующие по меньшей мере некоторые подсистемы системы 100 распределенной обработки данных, являются детерминированными по свое природе, т.е. каждое изменение состояния каждого автомата SM однозначно определено (а) текущим состоянием соответствующего автомата SM и (б) внешними входными данными соответствующего автомата SM. Иными словами, для текущего состояния автомата SM и для конкретных внешних входных данных существует единственное следующее состояние этого автомата SM. Этот детерминированный характер изменения состояния не зависит от того, у какого именно автомата SM системы 100 распределенной обработки данных происходит изменение состояния.

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

Подсистема распределенного хранения данных

Как упомянуто ранее, система 100 распределенной обработки данных также содержит подсистему 108 распределенного хранения данных. В общем случае подсистема 108 распределенного хранения данных способна, среди прочего, хранить системные данные, указывающие состояния, изменения состояний, внешние входные и/или выходные данные по меньшей мере некоторых автоматов SM системы 100 распределенной обработки данных. Например, системные данные, связанные с автоматом SM системы 100 распределенной обработки данных, могут храниться в форме журнала, содержащего хронологический список состояний, изменений состояний, внешних входных и/или выходных данных этого автомата SM.

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

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

В некоторых вариантах осуществления данной технологии системные и/или клиентские данные, хранящиеся в одном устройстве 112 хранения данных, могут дублироваться и храниться в нескольких других устройствах 112 хранения данных. В некоторых вариантах осуществления такое дублирование и хранение системных и/или клиентских данных может обеспечивать отказоустойчивое хранение системных и/или клиентских данных в системе 100 распределенной обработки данных. Отказоустойчивое хранение системных и/или клиентских данных способно предотвратить утрату данных, когда устройство 112 хранения данных подсистемы 108 распределенного хранения данных становится временно или постоянно недоступным для хранения и извлечения данных. Такое отказоустойчивое хранение системных и/или клиентских данных также может предотвращать утрату данных, когда автомат SM системы 100 распределенной обработки данных становится временно или постоянно недоступным.

Предполагается, что устройство 112 хранения данных может быть реализовано в виде компьютерного сервера. Такой компьютерный сервер содержит по меньшей мере одно физическое запоминающее устройство (т.е. накопитель 126) и одно или несколько программных приложений, способных выполнять машиночитаемые команды. Накопитель 126 может представлять собой твердотельный накопитель (SSD), накопитель на жестких дисках (HDD) и т.п. Поэтому можно сказать, что по меньшей мере одно физическое запоминающее устройство может быть реализовано как устройство с подвижным или неподвижным (статичным) диском.

Например, как показано на фиг. 1, устройство 112 хранения данных способно содержать, помимо прочего, следующие программные приложения: приложение 114 виртуального накопителя (Vdrive), приложение 116 физического накопителя (Pdrive), по меньшей мере одно приложение 118 моделирования накопителя, по меньшей мере одно приложение 120 планирования работы, приложение 122 обеспечения работы в реальном времени и по меньшей мере один прокси-сервер 124 автомата SM. Функции указанных выше программных приложений и накопителя 126, обеспечивающие хранение по меньшей мере некоторых системных и/или клиентских данных, более подробно описаны ниже со ссылками на фиг. 2.

Подсистема предварительной обработки запросов

Как указано выше, подсистема 105 обработки транзакций может содержать несколько детерминированных автоматов SM, которые должны получать входные данные определенного вида и которые соответствуют свойству детерминированности этих автоматов SM. Также следует еще раз отметить, что источник 102 запросов выдает запрос 180 в виде запроса декларативного типа.

Соответственно, подсистема 104 предварительной обработки запросов способна принимать запрос 180 декларативного типа от источника 102 запросов и предварительно обрабатывать или преобразовывать запрос 180 во множество детерминированных транзакций 182, которые соответствуют свойству детерминированности нескольких автоматов SM, образующих подсистему 105 обработки транзакций.

В целом, подсистема 104 предварительной обработки запросов предназначена для предварительной обработки или преобразования запроса 180 во множество детерминированных транзакций 182, которые могут быть обработаны детерминированными автоматами SM из подсистемы 105 обработки транзакций.

Следует отметить, что подсистема 104 предварительной обработки запросов также способна формировать ответ 181 для его передачи в источник 102 запросов. Разумеется, что подсистема 104 предварительной обработки запросов связана с подсистемой 105 обработки транзакций не только для передачи множества детерминированных транзакций 182, но и для приема информации об обработке множества детерминированных транзакций 182. В некоторых не имеющих ограничительного характера вариантах осуществления данной технологии множество детерминированных транзакций 182 может содержать одну или несколько транзакций вида «считывание» или «запись».

В некоторых вариантах осуществления данной технологии подсистема 104 предварительной обработки запросов реализована в виде по меньшей мере одного автомата SM в пределах объема данной технологии.

В некоторых вариантах осуществления данной технологии предполагается, что представленная на фиг. 1 система 100 распределенной обработки данных способна поддерживать транзакции ACID (Atomicity, Consistency, Isolation and Durability). В целом, ACID - это аббревиатура для набора свойств транзакции (атомарность, согласованность, изолированность, долговечность), которые обеспечивают надежность базы данных при выполнении транзакций. Поэтому в некоторых вариантах осуществления данной технологии предполагается, что транзакции, предназначенные для подсистемы 105 обработки транзакций, могут быть атомарными, согласованными, изолированными и долговечными в пределах объема данной технологии.

Подсистема обработки транзакций

В общем случае подсистема 105 обработки транзакций способна принимать и обрабатывать множество детерминированных транзакций 182 и, таким образом, обрабатывать запрос 180, полученный от источника 102 запросов. Подсистема 105 обработки транзакций содержит (а) подсистему 106 маршрутизации транзакций и (б) подсистему 110 базы данных, которые описаны далее.

Подсистема 110 базы данных содержит множество мест назначения транзакции (TDL, Transaction Destination Location) и разделена на множество сегментов 109, каждый из которых далее называется сегментом 109. В не имеющем ограничительного характера примере подсистема 110 базы данных может содержать базу данных, включающую в себя одну или несколько таблиц базы данных. Таблица базы данных может состоять из по меньшей мере двух столбцов, таких как первый столбец, содержащий ключи, и второй столбец, содержащий записи, в которых хранятся данные, связанные с соответствующими ключами. В этом не имеющем ограничительного характера примере место TDL может соответствовать строке таблицы базы данных, т.е. место TDL может соответствовать ключу и соответствующей записи в таблице базы данных.

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

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

Подсистема 106 маршрутизации транзакций способна маршрутизировать транзакции из множества детерминированных транзакций 182 в соответствующие места TDL и, таким образом, направлять их в соответствующие сегменты 109 подсистемы 110 базы данных. С этой целью подсистема 106 маршрутизации транзакций может включать в себя множество портов, которые обычно способны (а) принимать множество детерминированных транзакций 182 из подсистемы 104 предварительной обработки запросов, (б) разделять множество детерминированных транзакций 182 на подмножества детерминированных транзакций, предназначенных для соответствующих сегментов 109, и (в) формировать для каждого сегмента централизованный порядок выполнения детерминированных транзакций соответствующими сегментами 109.

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

Кроме того, как показано на фиг. 1, по меньшей мере некоторые из автоматов SM подсистемы 105 обработки транзакций могут быть связаны с подсистемой 108 распределенного хранения данных с использованием соответствующей линии 160 связи. В целом, линия 160 связи предназначена для передачи системных данных, таких как данные о состояниях, изменениях состояний, внешние входные и/или выходные данные соответствующих автоматов SM и т.д., в подсистему 108 распределенного хранения данных для хранения. Далее со ссылками на фиг. 2 более подробно описана реализация линий 160 связи и конфигурирование подсистемы 108 распределенного хранения данных для хранения системных данных.

На фиг. 2 представлено устройство 112 хранения данных, входящее в состав подсистемы 108 распределенного хранения данных. Как описано выше, устройство 112 хранения данных содержит по меньшей мере один прокси-сервер 124 автомата SM. Прокси-сервер автомата SM предназначен для управления связью между автоматом SM и подсистемой 108 распределенного хранения данных. В некоторых вариантах осуществления данной технологии предполагается, что по меньшей мере один прокси-сервер 124 автомата SM устройства 112 хранения данных может представлять собой прикладной программный интерфейс (API, Application Programing Interface), управляющий связью между автоматом SM и устройством 112 хранения данных. В других вариантах осуществления данной технологии по меньшей мере один прокси-сервер 124 автомата SM сам может быть реализован как автомат SM. В других вариантах осуществления данной технологии по меньшей мере один прокси-сервер 124 автомата SM может быть реализован как программный модуль (не как автомат SM) для выполнения описанных выше функций.

В некоторых вариантах осуществления данной технологии прокси-сервер 124 автомата SM может быть способен (а) принимать системные данные обновления журнала этого автомата SM с использованием соответствующей линии 160 связи, (б) обрабатывать системные данные и (в) передавать обработанные системные данные соответствующему приложению 114 Vdrive для дальнейшей обработки.

По меньшей мере один прокси-сервер 124 автомата SM может быть способен обрабатывать системные данные, например, для обеспечения целостности и отказоустойчивости системных данных. В некоторых вариантах осуществления данной технологии предполагается, что по меньшей мере один прокси-сервер 124 автомата SM может быть способен выполнять стойкое к потере кодирование (erasure coding) системных данных. В целом, стойкое к потере кодирование представляет собой способ кодирования, предусматривающий получение данных с избыточностью и разделение их на несколько фрагментов. Такие избыточность и фрагментация способствуют восстановлению данных в случае потери одного или нескольких фрагментов вследствие отказов в системе.

Предполагается, что обработанные таким образом по меньшей мере одним прокси-сервером 124 автомата SM системные данные принимаются по меньшей мере одним соответствующим приложением 114 Vdrive устройства 112 хранения данных. Приложение 114 Vdrive предназначено для обработки системных данных, полученных от по меньшей мере одного прокси-сервера 124 автомата SM, и для ответного формирования соответствующих операций I/O, которые должны выполняться накопителем 126 для сохранения системных данных в накопителе 126 устройства 112 хранения данных. После формирования по меньшей мере одним приложением 114 Vdrive операций I/O, соответствующих принятым системным данным, по меньшей мере одно приложение 114 Vdrive передает операции I/O приложению 116 Pdrive.

Иными словами, предполагается, что устройство 112 хранения данных может содержать несколько прокси-серверов 124 автомата SM для обработки и передачи системных данных нескольким соответствующим приложениям 114 Vdrive, которые обрабатывают системные данные, формируют соответствующие операции I/O и передают соответствующие операции I/O в единое приложение 116 Pdrive устройства 112 хранения данных.

В целом, приложение 116 Pdrive предназначено для управления работой накопителя 126. Например, приложение 116 Pdrive может быть способным выполнять кодирование операций I/O, которые должны выполняться в накопителе 126, и различные другие функции, способствующие надежному хранению данных в накопителе 126.

Приложение 116 Pdrive связано с приложением 120 планирования работы для передачи операции I/O. Приложение 120 планирования работы способно планировать передачу операций I/O в накопитель 126. Предполагается, что приложение 120 планирования работы или сокращенно планировщик может использовать различные схемы планирования для определения порядка передачи операций I/O в накопитель 126 для их дальнейшего выполнения.

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

В одном случае планировщик 120 может обеспечивать схему «справедливого» планирования. Должно быть понятно, что для данного устройства 112 хранения данных может потребоваться хранение операций I/O, соответствующих системным данным, связанным с несколькими автоматами SM. Кроме того, каждый из нескольких автоматов SM связан с заранее заданной долей производительности накопителя, которую накопитель 126 может выделить для выполнения операций I/O, связанных с соответствующим автоматом SM. В целом, схемы «справедливого» планирования способны упорядочивать операции I/O, передаваемые в накопитель 126, так, чтобы производительность накопителя 126, предназначенная для выполнения упорядоченных операций I/O, использовалась согласно заранее заданным долям, связанным с несколькими автоматами SM.

В другом случае планировщик 120 может обеспечивать схему планирования «для реального времени». Следует еще раз отметить, что система 100 распределенной обработки данных может использоваться для предоставления услуг «облачного» хранения данных. Во многих таких вариантах осуществления может быть желательным обрабатывать и сохранять системные данные в реальном времени, т.е. в течение очень короткого интервала времени. Чтобы обеспечить выполнение требований относительно режима реального времени к системе 100 распределенной обработки данных, операции I/O могут быть связаны с соответствующими предельными сроками, указывающими момент времени, по прошествии которого соответствующие операции I/O уже не попадают в пределы допустимого времени, соответствующие требованиям относительно режима реального времени к системе 100 распределенной обработки данных. В целом, схемы планирования реального времени способны упорядочивать операции I/O, передаваемые в накопитель 126, так, чтобы операции I/O выполнялись накопителем 126 с соблюдением соответствующих предельных сроков.

В другом случае планировщик 120 способен обеспечивать гибридную схему планирования. Иными словами, планировщик 120 способен обеспечивать схему планирования, позволяющую упорядочивать операции I/O, передаваемые для выполнения в накопитель 126, так, чтобы учитывались и заранее заданные доли производительности накопителя для каждого соответствующего автомата SM, и соответствующие предельные сроки операций I/O.

Как было упомянуто ранее, накопитель 126 представляет собой носитель информации для выполнения операций I/O и, соответственно, для хранения системных данных, переданных в устройство 112 хранения данных. Например, накопитель 126 может быть реализован в виде накопителя HDD или накопителя SSD. Накопитель 126 включает в себя внутреннее логическое устройство 250 накопителя для выбора операции I/O среди всех переданных в накопитель операций I/O для выполнения в текущий момент времени.

Следует отметить, что операции I/O могут направляться для выполнения в накопитель 126 по одной, но это может приводить к увеличению задержек между накопителем 126 и другими компонентами устройства 112 хранения данных. Поэтому операции I/O могут предаваться в накопитель 126 пакетами или группами. После приема пакета или группы операций I/O накопителем 126 внутреннее логическое устройство 250 накопителя способно выбрать для выполнения наиболее эффективную операцию I/O среди имеющихся в пакете операций I/O.

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

Поэтому в некоторых случаях, несмотря на то, что планировщик 120 упорядочил операции I/O для передачи определенным образом с учетом требований относительно режима реального времени к системе 100 распределенной обработки данных, внутреннее логическое устройство 250 накопителя 126 может выдавать в накопитель 126 команды для формирования порядка выполнения операций I/O, отличного от порядка передачи, выбранного планировщиком 120. Поэтому порядок выполнения иногда может не соответствовать требованиям относительно режима реального времени системы 100 распределенной обработки данных (в частности, когда от планировщика 120 принимаются дополнительные операции I/O, которые могут быть более «эффективными» с точки зрения накопителя 126 и могут выбираться среди еще не выполненных операций I/O). В некоторых вариантах осуществления данной технологии планировщик 120 может выполнять алгоритм, основанный на принципе «справедливости», также известный как «справедливая» организация очередей, чтобы обеспечивать «справедливость», при совместном использовании ограниченного ресурса в системе 100 распределенной обработки данных.

Чтобы обеспечить работу устройства 112 хранения данных в реальном времени и предотвратить описанную выше проблему, также известную как «торможение работы» (operation stagnation), устройство 112 хранения данных может содержать диспетчерский контроллер операций I/O, который далее называется приложением 122 обеспечения работы в реальном времени. В целом, приложение 122 обеспечения работы в реальном времени позволяет управлять тем, какие операции I/O из числа уже упорядоченных планировщиком 120 передаются в текущий момент времени для выполнения в накопитель 126.

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

В некоторых вариантах осуществления изобретения в приложении 122 обеспечения работы в реальном времени может быть реализован входной счетчик 202, способный передавать и подсчитывать операции I/O, отправленные в накопитель 126 с использованием пакетов 330 данных. В приложении 122 обеспечения работы в реальном времени также может быть реализован выходной счетчик 204 для обнаружения и подсчета подтверждений выполнения операций I/O, отправленных накопителем 126 с использованием пакетов 340 данных подтверждения.

Устройство 112 хранения данных также может содержать по меньшей мере одно соответствующее приложение 118 моделирования накопителя для каждого накопителя 126 в устройстве 112 хранения данных. В целом, приложение 118 моделирования накопителя способно эмулировать идеальную работу накопителя 126 для диагностического анализа накопителя 126. Приложение 118 моделирования накопителя также способно принимать информацию от входного счетчика 202 и от выходного счетчика 204 для диагностического анализа. Тем не менее, в других вариантах осуществления изобретения планировщик 120 также может использовать приложение 118 моделирования накопителя, чтобы упорядочивать операции I/O для их передачи в накопитель 126.

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

На фиг. 3 представлена схема приложения 122 обеспечения работы в реальном времени, приложения 118 моделирования накопителя и планировщика 120, которые реализованы согласно не имеющим ограничительного характера вариантам осуществления данной технологии.

Приложение 122 обеспечения работы в реальном времени способно принимать множество 300 последовательных операций I/O из планировщика 120 с использованием пакета 298 данных. Несмотря на то, что показан лишь один пакет 298 данных, во ходе работы в различные моменты времени может приниматься множество пакетов 298 данных.

Количество операций I/O во множестве 300 последовательных операций I/O может быть заранее задано и может зависеть от реализации накопителя 126. Например, в не имеющих ограничительного характера вариантах осуществления изобретения, где накопитель 126 реализован в виде накопителя HDD, множество 300 последовательных операций I/O может содержать не более 32 операций I/O. В других не имеющих ограничительного характера вариантах осуществления изобретения, где накопитель 126 реализован в виде накопителя SSD, множество 300 последовательных операций I/O может содержать не более 128 операций I/O.

Как показано на фиг. 3, каждая операция I/O из множества 300 последовательных операций I/O связана с соответствующей позицией, начиная с крайней правой позиции А, соответствующей первой операции 302, за которой следует позиция В, соответствующая второй операции 304, за которой следует позиция С, соответствующая третьей операции 306, за которой следует позиция D, соответствующая четвертой операции 308, за которой следует позиция Е, соответствующая пятой операции 310, за которой следует позиция F, соответствующая шестой операции 312, за которой следует позиция G, соответствующая седьмой операции 314, за которой следует позиция Н, соответствующая восьмой операции 316, за которой следует позиция I, соответствующая девятой операции 318, за которой следует позиция J, соответствующая десятой операции 320, и так далее до крайней левой позиции FF, соответствующей 32-й операции 324. В общем случае расположенная правее операция I/O имеет более высокий приоритет передачи, чем расположенная левее операция I/O.

Приложение 122 обеспечения работы в реальном времени способно применять скользящее ячейковое окно 350 ко множеству 300 последовательных операций I/O, чтобы выбрать заранее заданное количество последовательных операций I/O из множества 300 последовательных операций I/O с целью их передачи в накопитель 126 для выполнения. В некоторых вариантах осуществления изобретения скользящее ячейковое окно 350 может быть реализовано в виде конечного автомата.

Скользящее ячейковое окно 350 содержит заранее заданное количество N ячеек, соответствующих или связанных с N последовательными операциями I/O из множества 300 последовательных операций I/O. Таким образом, каждая ячейка скользящего ячейкового окна 350 может соответствовать одной операции I/O из множества 300 последовательных операций I/O. Как показано на фиг. 3, скользящее ячейковое окно 350 содержит пять ячеек: первую ячейку 352, вторую ячейку 354, третью ячейку 356, четвертую ячейку 358 и пятую ячейку 360. Предполагается, что в других не имеющих ограничительного характера вариантах осуществления данной технологии скользящее ячейковое окно 350 может содержать меньше пяти ячеек или больше пяти ячеек.

Приложение 122 обеспечения работы в реальном времени способно размещать скользящее ячейковое окно 350 в первой позиции 370 на последовательных операциях из множества 300 последовательных операций I/O, начиная с правой стороны множества 300 последовательных операций I/O, так, чтобы первая ячейка 352 находилась в позиции А на первой операции 302, вторая ячейка 354 находилась в позиции В на второй операции 304, третья ячейка 356 находилась в позиции С на третьей операции 306, четвертая ячейка 358 находилась в позиции D на четвертой операции 308 и пятая ячейка 360 находилась в позиции Е на пятой операции 310. Можно сказать, что операции I/O, на которых расположено скользящее ячейковое окно 350, представляют собой операции I/O, содержащиеся в скользящем ячейковом окне 350 или связанные со скользящим ячейковым окном 350.

Приложение 122 обеспечения работы в реальном времени способно передавать операции I/O, связанные со скользящим ячейковым окном 350, в накопитель 126 с использованием пакета 330 данных. Несмотря на то, что показан один пакет 330 данных, в ходе работы в различные моменты времени может передаваться множество пакетов 330 данных, каждый из которых далее называется пакетом 330 данных.

Накопитель 126 способен принимать пакет 330 данных, содержащий операции I/O, связанные со скользящим ячейковым окном 350, а именно, первую операцию 302, вторую операцию 304, третью операцию 306, четвертую операцию 308 и пятую операцию 310. Внутреннее логическое устройство 250 накопителя 126 способно выбирать наиболее эффективную операцию I/O для текущего выполнения среди первой операции 302, второй операции 304, третьей операции 306, четвертой операции 308 и пятой операции 310. На порядок выбора накопителем 126 наиболее эффективной операции I/O не накладывается каких-либо особых ограничений, этот выбор может быть реализован с использованием любого известного способа.

После выполнения наиболее эффективных с точки зрения внутреннего логического устройства 250 накопителя операций I/O, связанных со скользящим ячейковым окном 350, накопитель 126 может передавать подтверждение их выполнения в приложение 122 обеспечения работы в реальном времени с использованием пакета 340 данных подтверждения. В некоторых вариантах осуществления подтверждение выполнения с использованием пакета 340 данных подтверждения может включать в себя множество подтверждений выполнения, соответствующих выполнению множества операций I/O, связанных со скользящим ячейковым окном 350.

В некоторых вариантах осуществления изобретения выполнение одной или нескольких операций I/O накопителем 126 может завершиться неудачно по различным причинам и накопитель 126 может передать сообщение о неудачном завершении выполнения в приложение 122 обеспечения работы в реальном времени с использованием пакета 340 данных подтверждения. Дополнительно или в качестве альтернативы приложение 118 моделирования накопителя может анализировать работу накопителя 126 и оповещать планировщик 120 и/или приложение 122 обеспечения работы в реальном времени об определенных по результатам диагностического анализа неудачных завершениях выполнения операций I/O.

Приложение 122 обеспечения работы в реальном времени способно принимать пакет 340 данных подтверждения и определять позицию операции I/O, выполненной накопителем 126. В некоторых вариантах осуществления изобретения передача операции I/O приложением 122 обеспечения работы в реальном времени в накопитель 126 с использованием пакета 330 данных может выполняться одновременно с получением подтверждения выполнения с использованием пакета 340 данных подтверждения. Несмотря на то, что показан лишь один пакет 340 данных подтверждения, в ходе работы в различные моменты времени может передаваться множество пакетов 340 данных подтверждения, каждый из которых далее называется пакетом 340 данных подтверждения.

В общем случае, приложение 122 обеспечения работы в реальном времени может сдвигать скользящее ячейковое окно 350 на множестве 300 последовательных операций I/O из текущей позиции, т.е. из первой позиции 370, только если позиция операции I/O, выполненной накопителем 126, связана с первой ячейкой 352 скользящего ячейкового окна 350, т.е. с позицией А или с первой операцией 320, как показано на фиг. 3. Кроме того, приложение 122 обеспечения работы в реальном времени может сдвигать скользящее ячейковое окно 350 на несколько операций I/O, если также выполнена по меньшей мере одна операция, непосредственно следующая за первой операцией 302 из множества 300 последовательных операций I/O. Начиная с первой ячейки 352, если накопителем 126 выполнена одна или несколько непосредственно следующих друг за другом операций I/O, приложение 122 обеспечения работы в реальном времени может сдвинуть скользящее ячейковое окно 350 на некоторое количество ячеек так, чтобы первая ячейка 352 располагалась на следующей еще не выполненной операции I/O.

Если позиция операции I/O, выполненной накопителем 126, не связана с первой ячейкой 352, т.е. если эта позиция связана со второй ячейкой 354, третьей ячейкой 356, четвертой ячейкой 358 или пятой ячейкой 360, приложение 122 обеспечения работы в реальном времени не изменяет текущую позицию скользящего ячейкового окна 350, т.е. блокирует сдвиг скользящего ячейкового окна 350 на множестве 300 последовательных операций I/O.

Для лучшего понимания вариантов осуществления данной технологии далее со ссылками на фиг. 4 и на фиг. 5 описаны различные сценарии выполнения приложения 122 обеспечения работы в реальном времени, управляющего скользящим ячейковым окном 350 с целью передачи операций I/O для их выполнения накопителем 126.

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

В первом не имеющем ограничительного характера примере внутреннее логическое устройство 250 накопителя 126 может выбрать первую операцию 302 в качестве наиболее эффективной операции для выполнения среди первой операции 302, второй операции 304, третьей операции 306, четвертой операции 308 и пятой операции 310. Накопитель 126 может выполнить первую операцию 302 и передать подтверждение ее выполнения в приложение 122 обеспечения работы в реальном времени с использованием пакета 340 данных подтверждения.

Приложение 122 обеспечения работы в реальном времени может на основе пакета 340 данных подтверждения определить, что позиция операции I/O, выполненной накопителем 126, соответствует первой операции 302, связанной с первой ячейкой 352 (на фиг. 4 выполненные операции I/O помечены символом «X»).

Поэтому приложение 122 обеспечения работы в реальном времени может сдвинуть скользящее ячейковое окно 350 на множестве 300 последовательных операций I/O так, чтобы это окно содержало по меньшей мере одну дополнительную следующую операцию I/O из множества 300 последовательных операций I/O.

Приложение 122 обеспечения работы в реальном времени может сдвинуть скользящее ячейковое окно 350 из текущей первой позиции 370 во вторую позицию 372, чтобы это окно содержало следующую, шестую операцию 312 из последовательности операций I/O. Во второй позиции 372 первая ячейка 352 расположена в позиции В на второй операции 304, вторая ячейка 354 расположена в позиции С на третьей операции 306, третья ячейка 356 расположена в позиции D на четвертой операции 308, четвертая ячейка 358 расположена в позиции Е на пятой операции 310 и пятая ячейка 360 расположена в позиции F на шестой операции 312, которая еще не выполнена и непосредственно следует за пятой операцией 310.

После сдвига во вторую позицию 372 приложение 122 обеспечения работы в реальном времени может передать шестую операцию 312 в накопитель 126 с использованием пакета 330 данных.

Накопитель 126 может принять пакет 330 данных и внутреннее логическое устройство 250 накопителя 126 может добавить шестую операцию 312 к оставшимся операциям, т.е. ко второй операции 304, третьей операции 306, четвертой операции 308 и пятой операции 310. Внутреннее логическое устройство 250 накопителя 126 может выбрать наиболее эффективную операцию I/O для выполнения среди второй операции 304, третьей операции 306, четвертой операции 308, пятой операции 310 и шестой операции 312.

Внутреннее логическое устройство 250 накопителя может выбрать третью операцию 306 для выполнения накопителем 126. Накопитель 126 может выполнить третью операцию 306 и передать подтверждение ее выполнения в приложение 122 обеспечения работы в реальном времени с использованием пакета 340 данных подтверждения.

Приложение 122 обеспечения работы в реальном времени может на основе пакета 340 данных подтверждения определить, что позиция операции I/O, выполненной накопителем 126, соответствует третьей операции 306, связанной со второй ячейкой 354. Поскольку позиция операции I/O, выполненной накопителем 126, не соответствует первой ячейке 352, приложение 122 обеспечения работы в реальном времени может оставить скользящее ячейковое окно 350 во второй позиции 372. Поскольку скользящее ячейковое окно 350 остается во второй позиции 372, приложение 122 обеспечения работы в реальном времени не может отправить какую-либо дополнительную операцию I/O в накопитель 126.

Внутреннее логическое устройство 250 накопителя 126 может выбрать другую наиболее эффективную операцию I/O для выполнения среди второй операции 304, четвертой операции 308, пятой операции 310 и шестой операции 312.

Внутреннее логическое устройство 250 накопителя может выбрать пятую операцию 310 для выполнения накопителем 126. Накопитель 126 может выполнить пятую операцию 310 и передать подтверждение ее выполнения в приложение 122 обеспечения работы в реальном времени с использованием пакета 340 данных подтверждения.

Приложение 122 обеспечения работы в реальном времени может на основе пакета 340 данных подтверждения определить, что позиция операции I/O, выполненной накопителем 126, соответствует пятой операции 310, связанной с четвертой ячейкой 358. Поскольку позиция операции I/O, выполненной накопителем 126, не соответствует первой ячейке 352, приложение 122 обеспечения работы в реальном времени может оставить скользящее ячейковое окно 350 во второй позиции 372. Поскольку скользящее ячейковое окно 350 остается во второй позиции 372, приложение 122 обеспечения работы в реальном времени не может отправить какую-либо дополнительную операцию I/O в накопитель 126.

Внутреннее логическое устройство 250 накопителя 126 может выбрать другую наиболее эффективную операцию I/O для выполнения среди второй операции 304, четвертой операции 308 и шестой операции 312.

Внутреннее логическое устройство 250 накопителя может выбрать вторую операцию 304 для выполнения накопителем 126. Накопитель 126 может выполнить вторую операцию 304 и передать подтверждение ее выполнения в приложение 122 обеспечения работы в реальном времени с использованием пакета 340 данных подтверждения.

Приложение 122 обеспечения работы в реальном времени может принять пакет 340 данных подтверждения и на основе пакета 340 данных подтверждения определить, что выполненная накопителем 126 операция I/O соответствует второй операции 304, связанной с первой ячейкой 352.

Определив, что операция I/O, соответствующая первой ячейке 352, выполнена накопителем 126, приложение 122 обеспечения работы в реальном времени сдвигает скользящее ячейковое окно 350 на множестве 300 последовательных операций I/O так, чтобы это окно содержало по меньшей мере одну дополнительную непосредственно следующую операцию I/O из множества 300 последовательных операций I/O.

Следовательно, приложение 122 обеспечения работы в реальном времени может сдвинуть скользящее ячейковое окно 350 из текущей второй позиции 372 в третью позицию 374. Поскольку третья операция 306, непосредственно следующая за второй операцией 304, уже выполнена накопителем 126, приложение 122 обеспечения работы в реальном времени может сдвинуть скользящее ячейковое окно 350 так, чтобы первая ячейка 352 была связана с еще не выполненной операцией I/O, т.е. с четвертой операцией 308.

В третьей позиции 374 первая ячейка 352 расположена в позиции D на четвертой операции 308, вторая ячейка 354 расположена в позиции Е на пятой операции 310, третья ячейка 356 расположена в позиции F на шестой операции 312, четвертая ячейка 358 расположена в позиции G на седьмой операции 314 и пятая ячейка 360 расположена в позиции Н на восьмой операции 316, причем седьмая операция 314 и восьмая операция 316 являются дополнительными непосредственно следующими операциями I/O, еще не выполненными накопителем 126.

После сдвига в третью позицию 374 приложение 122 обеспечения работы в реальном времени может передать седьмую операцию 314 и восьмую операцию 316 в накопитель 126 с использованием пакета 330 данных, поскольку седьмая операция 314 и восьмая операция 316 представляют собой добавленные в скользящее ячейковое окно 350 операции I/O, ранее не передававшиеся в накопитель 126.

Внутреннее логическое устройство 250 накопителя 126 может выбрать другую наиболее эффективную операцию I/O для выполнения среди четвертой операции 308, шестой операции 312, седьмой операции 314 и восьмой операции 316.

Внутреннее логическое устройство 250 накопителя может выбрать шестую операцию 312 для выполнения накопителем 126. Накопитель 126 может выполнить шестую операцию 312 и передать подтверждение ее выполнения в приложение 122 обеспечения работы в реальном времени с использованием пакета 340 данных подтверждения.

Приложение 122 обеспечения работы в реальном времени может принять пакет 340 данных подтверждения и определить, что выполненная накопителем 126 операция I/O соответствует шестой операции 312, связанной с третьей ячейкой 356. Поскольку позиция шестой операции 312, выполненной накопителем 126, не соответствует первой ячейке 352, приложение 122 обеспечения работы в реальном времени может оставить скользящее ячейковое окно 350 в третьей позиции 374. Поскольку скользящее ячейковое окно 350 остается в третьей позиции 374, приложение 122 обеспечения работы в реальном времени не может отправить какую-либо дополнительную операцию I/O в накопитель 126.

Внутреннее логическое устройство 250 накопителя 126 может выбрать другую наиболее эффективную операцию I/O для выполнения среди четвертой операции 308, седьмой операции 314 и восьмой операции 316.

Внутреннее логическое устройство 250 накопителя может выбрать четвертую операцию 308 для выполнения накопителем 126. Накопитель 126 может выполнить четвертую операцию 308 и передать подтверждение ее выполнения в приложение 122 обеспечения работы в реальном времени с использованием пакета 340 данных подтверждения.

Приложение 122 обеспечения работы в реальном времени может принять пакет 340 данных подтверждения и на основе пакета 340 данных подтверждения определить, что позиция операции I/O, выполненной накопителем 126, соответствует четвертой операции 308, связанной с первой ячейкой 352.

Определив, что операция I/O, соответствующая первой ячейке 352, выполнена накопителем 126, приложение 122 обеспечения работы в реальном времени может сдвинуть скользящее ячейковое окно 350 на множестве 300 последовательных операций I/O так, чтобы это окно содержало по меньшей мере одну дополнительную непосредственно следующую операцию I/O из множества 300 последовательных операций I/O.

Следовательно, приложение 122 обеспечения работы в реальном времени может сдвинуть скользящее ячейковое окно 350 из текущей третьей позиции 374 в четвертую позицию 376. Поскольку пятая операция 310, непосредственно следующая за четвертой операцией 308, и шестая операция 312, непосредственно следующая за пятой операцией 310, уже выполнены накопителем 310, приложение 122 обеспечения работы в реальном времени может сдвинуть скользящее ячейковое окно 350 так, чтобы первая ячейка 352 была связана со следующей еще не выполненной операцией, т.е. с седьмой операцией 314.

В четвертой позиции 376 первая ячейка 352 расположена в позиции G на седьмой операции 314, вторая ячейка 354 расположена в позиции Н на восьмой операции 316, третья ячейка 356 расположена в позиции I на девятой операции 318, четвертая ячейка 358 расположена в позиции J на десятой операции 320 и пятая ячейка 360 расположена в позиции К (не показана) на одиннадцатой операции (не показана), причем девятая операция 318, десятая операция 320 и одиннадцатая операция (не показана) являются дополнительными непосредственно следующими операциями I/O, еще не выполненными накопителем 126.

После сдвига в четвертую позицию 376 приложение 122 обеспечения работы в реальном времени может передать девятую операцию 318, десятую операцию 320 и одиннадцатую операцию (не показана) в накопитель 126 с использованием пакета 330 данных, поскольку девятая операция 318, десятая операция 320 и одиннадцатая операция (не показана) представляют собой добавленные в скользящее ячейковое окно 350 непосредственно следующие операции I/O, ранее не передававшиеся в накопитель 126.

Приложение 122 обеспечения работы в реальном времени может продолжать работу аналогичным образом, пока накопителем 126 не будет выполнено все множество 300 последовательных операций I/O.

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

Во втором не имеющем ограничительного характера примере внутреннее логическое устройство 250 накопителя 126 может выбрать вторую операцию 304 в качестве наиболее эффективной операции для выполнения среди первой операции 302, второй операции 304, третьей операции 306, четвертой операции 308 и пятой операции 310. Накопитель 126 может выполнить вторую операцию 304 и передать подтверждение ее выполнения в приложение 122 обеспечения работы в реальном времени с использованием пакета 340 данных подтверждения.

Приложение 122 обеспечения работы в реальном времени может на основе пакета 340 данных подтверждения определить, что позиция операции I/O, выполненной накопителем 126, соответствует второй операции 304, связанной со второй ячейкой 354 (на фиг. 5 выполненные операции I/O помечены символом «X»). Поскольку позиция операции I/O, выполненной накопителем 126, не соответствует первой ячейке 352, приложение 122 обеспечения работы в реальном времени оставляет скользящее ячейковое окно 350 в первой позиции 370. Поскольку скользящее ячейковое окно 350 остается в первой позиции 370, приложение 122 обеспечения работы в реальном времени не отправляет никаких дополнительных операций I/O в накопитель 126.

Внутреннее логическое устройство 250 накопителя может выбрать третью операцию 306 для выполнения накопителем 126. Накопитель 126 может выполнить третью операцию 306 и передать подтверждение ее выполнения в приложение 122 обеспечения работы в реальном времени с использованием пакета 340 данных подтверждения.

Приложение 122 обеспечения работы в реальном времени на основе пакета 340 данных подтверждения определяет, что позиция операции I/O, выполненной накопителем 126, соответствует третьей операции 306, связанной с третьей ячейкой 356 скользящего ячейкового окна 350. Поскольку позиция операции I/O, выполненной накопителем 126, не соответствует первой ячейке 352, приложение 122 обеспечения работы в реальном времени оставляет скользящее ячейковое окно 350 в первой позиции 370. Поскольку скользящее ячейковое окно 350 остается в первой позиции 370, приложение 122 обеспечения работы в реальном времени не отправляет никаких дополнительных операций I/O в накопитель 126.

Внутреннее логическое устройство 250 накопителя может выбрать пятую операцию 310 и вторую операцию 304 для выполнения накопителем 126. Накопитель 126 может выполнить пятую операцию 310 и вторую операцию 304 и передать подтверждение их выполнения в приложение 122 обеспечения работы в реальном времени с использованием пакета 340 данных подтверждения.

Приложение 122 обеспечения работы в реальном времени на основе пакета 340 данных подтверждения определяет, что позиции операций I/O, выполненных накопителем 126, соответствуют пятой операции 310 и второй операции 304, связанным с пятой ячейкой 360 и второй ячейкой 354 скользящего ячейкового окна 350, соответственно. Поскольку позиции операций I/O, выполненных накопителем 126, не соответствуют первой ячейке 352, приложение 122 обеспечения работы в реальном времени оставляет скользящее ячейковое окно 350 в первой позиции 370. Поскольку скользящее ячейковое окно 350 остается в первой позиции 370, приложение 122 обеспечения работы в реальном времени не отправляет никаких дополнительных операций I/O в накопитель 126.

Внутреннее логическое устройство 250 накопителя может выбрать первую операцию 302 для выполнения накопителем 126. Накопитель 126 может выполнить первую операцию 302 и передать подтверждение ее выполнения в приложение 122 обеспечения работы в реальном времени с использованием пакета 340 данных подтверждения.

Приложение 122 обеспечения работы в реальном времени на основе пакета 340 данных подтверждения определяет, что позиция операции I/O, выполненной накопителем 126, соответствует первой операции 302, связанной с первой ячейкой 352.

Приложение 122 обеспечения работы в реальном времени сдвигает скользящее ячейковое окно 350 на множестве 300 последовательных операций I/O так, чтобы оно содержало по меньшей мере одну дополнительную непосредственно следующую операцию I/O из множества 300 последовательных операций I/O. Иными словами, приложение 122 обеспечения работы в реальном времени сдвигает скользящее ячейковое окно 350 из текущей первой позиции 370 во вторую позицию 472, чтобы это окно содержало по меньшей мере одну дополнительную операцию из последовательности. Поскольку вторая операция 304, третья операция 306, четвертая операция 308 и пятая операция 310 уже выполнены накопителем 126, приложение 122 обеспечения работы в реальном времени может сдвинуть скользящее ячейковое окно 350 на следующую еще не выполненную операцию I/O из множества 300 последовательных операций I/O, т.е. на шестую операцию 312.

Таким образом, во второй позиции 472 первая ячейка 352 расположена в позиции F на шестой операции 312, вторая ячейка 354 расположена в позиции G на седьмой операции 314, третья ячейка 356 расположена в позиции Н на восьмой операции 316, четвертая ячейка 358 расположена в позиции I на девятой операции 318 и пятая ячейка 360 расположена в позиции J на десятой операции 320. Иными словами, количество ячеек, на которое было сдвинуто скользящее ячейковое окно 350, соответствует количеству непосредственно следующих друг за другом «пустых» ячеек (помечены во второй позиции 472 символами «X»), связанных с выполненными операциями I/O.

После сдвига во вторую позицию 472 приложение 122 обеспечения работы в реальном времени передает шестую операцию 312, седьмую операцию 314, восьмую операцию 316, девятую операцию 318 и десятую операцию 320 в накопитель 126 с использованием пакета 330 данных, поскольку шестая операция 312, седьмая операция 314, восьмая операция 316, девятая операция 318 и десятая операция 320 представляют собой добавленные в скользящее ячейковое окно 350 операции I/O, ранее не передававшиеся в накопитель 126.

Внутреннее логическое устройство 250 накопителя 126 может выбрать наиболее эффективную операцию I/O для выполнения среди шестой операции 312, седьмой операции 314, восьмой операции 316, девятой операции 318 и десятой операции 320.

Внутреннее логическое устройство 250 накопителя может выбрать шестую операцию 312 для выполнения накопителем 126. Накопитель 126 может выполнить шестую операцию 312 и передать подтверждение ее выполнения в приложение 122 обеспечения работы в реальном времени с использованием пакета 340 данных подтверждения.

Приложение 122 обеспечения работы в реальном времени может на основе пакета 340 данных подтверждения определить, что выполненная накопителем 126 операция I/O соответствует шестой операции 312, связанной с первой ячейкой 352.

Приложение 122 обеспечения работы в реальном времени сдвигает скользящее ячейковое окно 350 на множестве 300 последовательных операций I/O так, чтобы оно содержало по меньшей мере одну дополнительную непосредственно следующую операцию I/O из множества 300 последовательных операций I/O. Иными словами, приложение 122 обеспечения работы в реальном времени может сдвинуть скользящее ячейковое окно 350 из текущей второй позиции 472 в третью позицию 474, чтобы это окно содержало по меньшей мере одну дополнительную операцию из последовательности. Приложение 122 обеспечения работы в реальном времени может сдвинуть скользящее ячейковое окно 350, чтобы добавить в это окно следующую еще не выполненную операцию I/O из множества 300 последовательных операций I/O, т.е. одиннадцатую операцию (не показана).

В третьей позиции 474 первая ячейка 352 расположена в позиции G на седьмой операции 314, вторая ячейка 354 расположена в позиции Н на восьмой операции 316, третья ячейка 356 расположена в позиции I на девятой операции 318, четвертая ячейка 358 расположена в позиции J на десятой операции 320 и пятая ячейка 360 расположена в позиции К (не показана) на одиннадцатой операции (не показана), причем девятая операция 318, десятая операция 320 и одиннадцатая операция (не показана) являются дополнительными непосредственно следующими операциями I/O, еще не выполненными накопителем 126.

После сдвига в третью позицию 474 приложение 122 обеспечения работы в реальном времени передает одиннадцатую операцию (не показана) в накопитель 126 с использованием пакета 330 данных, поскольку одиннадцатая операция (не показана) представляет собой добавленную в скользящее ячейковое окно 350 операцию I/O, ранее не передавшуюся в накопитель 126.

Приложение 122 обеспечения работы в реальном времени может продолжать работу аналогичным образом, пока накопителем 126 не будет выполнено все множество 300 последовательных операций I/O. Следует отметить, что в некоторых вариантах осуществления данной технологии ячейка скользящего ячейкового окна 350 может располагаться на операции I/O, еще не принятой приложением 122 обеспечения работы в реальном времени из планировщика 120 по различным причинам. В таких случаях приложение 122 обеспечения работы в реальном времени может передавать операцию I/O сразу после ее получения из планировщика 120.

На фиг. 6 представлена блок-схема способа 600 планирования передачи множества 300 последовательных операций, которые должны выполняться накопителем 126, согласно не имеющим ограничительного характера вариантам осуществления данной технологии.

Способ 600 может выполняться приложением 122 обеспечения работы в реальном времени после приема множества 300 последовательных операций I/O от планировщика 120.

Способ 600 может начинаться с шага 602.

Шаг 602: применение скользящего N-ячейкового окна для выбора N последовательных операций I/O из запланированной последовательности, при этом N скользящих ячеек размещаются на N последовательных операциях I/O, начиная с первой операции I/O, и каждая ячейка скользящего окна содержит одну соответствующую операцию из N последовательных операций I/O.

На шаге 602 приложение 122 обеспечения работы в реальном времени может применять скользящее ячейковое окно 350 для выбора N последовательных операций I/O из множества 300 последовательных операций I/O, при этом скользящее ячейковое окно 350 размещается на пяти последовательных операциях I/O, начиная с первой ячейки 352, которая размещается на первой операции 302, при этом вторая ячейка 354 размещается на второй операции 304, третья ячейка 356 размещается на третьей операции 306, четвертая ячейка 358 размещается на четвертой операции 308, пятая ячейка 360 размещается на пятой операции 310.

Способ 600 затем может продолжаться на шаге 604.

Шаг 604: передача в устройство хранения данных N последовательных операций I/O.

На шаге 604 приложение 122 обеспечения работы в реальном времени может с использованием пакета данных 330 передавать в накопитель 126 первую операцию 302, вторую операцию 304, третью операцию 306, четвертую операцию 308 и пятую операцию 310.

Способ 600 затем может продолжаться на шаге 606.

Шаг 606: прием от устройства хранения данных подтверждения выполнения, указывающего, что определенная операция I/O из N последовательных операций I/O обработана устройством хранения данных.

На шаге 606 приложение 122 обеспечения работы в реальном времени может с использованием пакета 340 данных подтверждения принимать подтверждение выполнения операции I/O, выбранной для выполнения внутренним логическим устройством 250 накопителя 126 среди первой операции 302, второй операции 304, третьей операции 306, четвертой операции 308 и пятой операции 310.

Способ 600 затем может продолжаться на шаге 608.

Шаг 608: определение позиции ячейки скользящего N-ячейкового окна, связанной с этой операцией I/O.

На шаге 608 приложение 122 обеспечения работы в реальном времени способно на основе пакета 340 данных подтверждения определять позицию ячейки, связанной с операцией I/O, выполненной накопителем 126, среди первой ячейки 352, второй ячейки 354, третьей ячейки 356, четвертой ячейки 358 и пятой ячейки 360.

Способ 600 затем может продолжаться на шаге 610 или на шаге 612.

Шаг 610: если позиция такой ячейки соответствует первой позиции среди позиций ячеек скользящего N-ячейкового окна, выполняется сдвиг скользящего N-ячейкового окна на множестве операций I/O так, чтобы скользящее N-ячейковое окно содержало по меньшей мере одну дополнительную операцию I/O, следующую непосредственно за N последовательными операциями I/O в запланированной последовательности множества операций I/O, и передача в устройство хранения данных этой по меньшей мере одной дополнительной операции I/O для выполнения.

На шаге 610, если позиция такой ячейки соответствует первой ячейке 352 скользящего ячейкового окна 350, приложение 122 обеспечения работы в реальном времени может сдвигать скользящее ячейковое окно 350 на множестве 300 последовательных операций I/O так, чтобы это окно содержало по меньшей мере одну дополнительную непосредственно следующую операцию I/O из множества 300 последовательных операций I/O. В не имеющем ограничительного характера примере, если операция I/O является первой операцией 302, соответствующей первой ячейке 352, приложение 122 обеспечения работы в реальном времени может сдвигать скользящее ячейковое окно 350 так, чтобы первая ячейка 352 размещалась на второй операции 304, вторая ячейка 354 размещалась на третьей операции 306, третья ячейка 356 размещалась на четвертой операции 308, четвертая ячейка 358 размещалась на пятой операции 310 и пятая ячейка 360 размещалась на шестой операции 312. Приложение 122 обеспечения работы в реальном времени способно передавать шестую операцию 312 в накопитель 126 с использованием пакета 330 данных. Приложение 122 обеспечения работы в реальном времени способно передавать шестую операцию 312 в накопитель 126 с использованием пакета 330 данных одновременно с приемом подтверждения выполнения операции I/O с использованием пакета 340 данных подтверждения.

Шаг 610 может выполняться каждый раз при приеме подтверждения выполнения для первой ячейки 352.

Шаг 612: если позиция такой ячейки не соответствует первой позиции среди позиций ячеек N-ячейкового окна, выполняется блокировка сдвига скользящего N-ячейкового окна на запланированной последовательности множества операций I/O.

На шаге 612 приложение 122 обеспечения работы в реальном времени может блокировать сдвиг скользящего ячейкового окна 350 на множестве 300 последовательных операций I/O, если позиция данной ячейки не соответствует первой ячейке 352 скользящего ячейкового окна 350.

Шаг 612 может выполняться каждый раз при приеме подтверждения выполнения для ячейки, отличной от первой ячейки 352.

Затем способ 600 может завершаться.

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

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

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

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

1. Способ планирования передачи множества операций ввода/вывода (I/O), предназначенных для выполнения устройством хранения данных, входящим в состав компьютерной системы, содержащей:

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

- диспетчерский контроллер операций I/O, связанный с планировщиком операций и с устройством хранения данных;

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

способ выполняемый диспетчерским контроллером операций I/O и включающий в себя:

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

- передачу в устройство хранения данных N последовательных операций I/O;

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

- определение позиции ячейки скользящего N-ячейкового окна, связанной с данной операцией I/O;

- если эта позиция ячейки соответствует первой позиции среди позиций ячеек скользящего N-ячейкового окна:

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

- передачу в устройство хранения данных этой по меньшей мере одной дополнительной операции I/O для выполнения.

2. Способ по п. 1, отличающийся тем, что он дополнительно включает в себя блокировку сдвига скользящего N-ячейкового окна на запланированной последовательности множества операций I/O, если указанная позиция ячейки не соответствует первой позиции среди позиций ячеек N-ячейкового окна.

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

4. Способ по п. 1, отличающийся тем, что запланированная последовательность не содержит указанной по меньшей мере одной дополнительной операции I/O, при этом передача этой по меньшей мере одной дополнительной операции I/O в устройство хранения данных выполняется после приема подтверждения выполнения, как только эта по меньшей мере одна дополнительная операция I/O принята из планировщика операций и добавлена в запланированную последовательность.

5. Способ по п. 1, отличающийся тем, что прием подтверждения выполнения включает в себя прием множества подтверждений, соответствующих множеству последовательных операций I/O из N последовательных операций I/O, обработанных устройством хранения данных, при этом скользящее окно сдвигается на некоторое количество Х-ячеек, соответствующее количеству выполненных последовательных операций I/O из множества операций I/O, начиная с первой операции I/O.

6. Способ по п. 1, отличающийся тем, что диспетчерский контроллер операций I/O реализован в виде программного модуля.

7. Способ по п. 1, отличающийся тем, что диспетчерский контроллер операций I/O реализован в виде конечного автомата.

8. Способ по п. 6, отличающийся тем, что программный модуль находится в устройстве хранения данных.

9. Способ по п. 1, отличающийся тем, что алгоритм планирования основан на принципе «справедливости».

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

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

12. Способ по п. 1, отличающийся тем, что дополнительно включает в себя выполнение данной операции I/O устройством хранения данных.

13. Способ по п. 1, отличающийся тем, что дополнительно включает в себя передачу устройством хранения данных в диспетчерский контроллер операций I/O информации, указывающей на выполнение данной операции I/O.

14. Система планирования передачи множества операций ввода/вывода (I/O), предназначенных для выполнения устройством хранения данных, связанным с этой системой, содержащая:

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

- диспетчерский контроллер операций I/O, связанный с планировщиком операций и с устройством хранения данных;

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

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

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

- передача в устройство хранения данных N последовательных операций I/O;

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

- определение позиции ячейки скользящего N-ячейкового окна, связанной с данной операцией I/O;

- если эта позиция ячейки соответствует первой позиции среди позиций ячеек скользящего N-ячейкового окна:

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

- передача в устройство хранения данных этой по меньшей мере одной дополнительной операции I/O для выполнения.

15. Система по п. 14, отличающаяся тем, что процессор дополнительно выполнен с возможностью инициирования блокировки диспетчерским контроллером операций I/O сдвига скользящего N-ячейкового окна на запланированной последовательности множества операций I/O, если указанная позиция ячейки не соответствует первой позиции среди позиций ячеек N-ячейкового окна.

16. Система по п. 14, отличающаяся тем, что запланированная последовательность содержит указанную по меньшей мере одну дополнительную операцию I/O, при этом передача этой по меньшей мере одной дополнительной операции I/O в устройство хранения данных выполняется одновременно с приемом подтверждения выполнения.

17. Система по п. 14, отличающаяся тем, что запланированная последовательность не содержит указанной по меньшей мере одной дополнительной операции I/O, при этом передача этой по меньшей мере одной дополнительной операции I/O в устройство хранения данных выполняется после приема подтверждения выполнения, как только эта по меньшей мере одна дополнительная операция I/O принята из планировщика операций и добавлена в запланированную последовательность.

18. Система по п. 14, отличающаяся тем, что прием подтверждения выполнения включает в себя прием множества подтверждений, соответствующих множеству последовательных операций I/O из N последовательных операций I/O, обработанных устройством хранения данных, при этом скользящее окно сдвигается на некоторое количество Х-ячеек, соответствующее количеству выполненных последовательных операций I/O из множества операций I/O, начиная с первой операции I/O.

19. Система по п. 14, отличающаяся тем, что диспетчерский контроллер операций I/O реализован в виде программного модуля, содержащего указанные команды.

20. Система по п. 14, отличающаяся тем, что диспетчерский контроллер операций I/O реализован в виде конечного автомата, содержащего указанные команды.

21. Система по п. 19, отличающаяся тем, что программный модуль находится в устройстве хранения данных.

22. Система по п. 14, отличающаяся тем, что алгоритм планирования основан на принципе «справедливости».

23. Система по п. 14, отличающаяся тем, что устройство хранения данных реализовано в виде отказоустойчивого устройства.

24. Система по п. 14, отличающаяся тем, что алгоритм упорядочивания выполнения не управляется планировщиком задач.

25. Система по п. 14, отличающаяся тем, что процессор дополнительно выполнен с возможностью инициирования операций I/O с целью выполнения данной операции I/O устройством хранения данных.

26. Система по п. 14, отличающаяся тем, что процессор дополнительно выполнен с возможностью инициирования операций I/O с целью передачи устройством хранения данных информации, указывающей на выполнение данной операции I/O.