СПОСОБ И СИСТЕМА ДЛЯ ПЛАНИРОВАНИЯ ОБРАБОТКИ ОПЕРАЦИЙ ВВОДА/ВЫВОДА
METHOD AND SYSTEM FOR SCHEDULING PROCESSING OF I/O OPERATIONS

Область техники
Данная технология относится к распределенной обработке данных и, в частности, к способам и системам для планирования операций ввода/вывода (I/O, Input/Output) с целью их обработки.
Уровень техники
Требования к запоминающим устройствам для хранения цифровых данных постоянно повышаются, поскольку большие объемы цифровых данных создаются ежедневно. Например, хранения могут требовать различные виды пользовательских данных, данных организаций и/или данных приложений. Это повышает требования к емкости хранилищ данных. Растущие потребности пользователей и/или организаций способны удовлетворить «облачные» системы удаленного хранения данных.
В общем случае «облачное» хранилище данных представляет собой вид компьютерного запоминающего устройства, в котором цифровые данные хранятся в логических пулах. Физическая память, в которой фактически хранятся цифровые данные, распределена между несколькими серверами, возможно, расположенными в различных местах (т.е. в различных центрах обработки данных), и обычно управляется компанией, предоставляющей услуги «облачного» хранения данных. Пользователи и/или организации обычно покупают или арендуют некоторый объем памяти у поставщиков услуг «облачного» хранения данных, чтобы хранить свои цифровые данные. Со своей стороны, поставщики услуг «облачного» хранения данных отвечают за доступность цифровых данных и защиту физической памяти с целью предотвращения утраты данных.
Раскрытие изобретения
Разработчики данной технологии обнаружили определенные технические недостатки, связанные с известными решениями для обеспечения доступности данных и предотвращения их утраты.
В соответствии с первым аспектом данной технологии реализован способ планирования множества операций 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, сформированной вторым источником 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, и (б) по меньшей мере одной операции 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, сформированной вторым источником I/O.
В некоторых вариантах осуществления способа скорректированный прогнозный период обработки для другой операции I/O указывает скорректированный прогнозный предельный срок обработки для этой другой операции I/O.
В некоторых вариантах осуществления способа контроль планировщиком операций фактического времени обработки для (а) по меньшей мере одной операции I/O, сформированной первым источником I/O, и (б) по меньшей мере одной операции I/O, сформированной вторым источником I/O, включает в себя прием от накопителя подтверждений обработки, указывающих фактическое время обработки для (а) по меньшей мере одной операции I/O, сформированной первым источником I/O, и (б) по меньшей мере одной операции I/O, сформированной вторым источником I/O.
В некоторых вариантах осуществления способа алгоритм планирования представляет собой алгоритм планирования в реальном времени.
В некоторых вариантах осуществления способа алгоритм планирования в реальном времени представляет собой алгоритм планирования на основе диспетчеризации по ближайшему предельному сроку (EDF, Earliest Deadline First).
В некоторых вариантах осуществления способа определение прогнозного периода обработки для каждой из (а) по меньшей мере одной операции 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, и (б) по меньшей мере одной операции 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, сформированную первым источником 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. Планировщик операций способен контролировать фактическое время обработки при обработке (а) по меньшей мере одной операции 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, сформированной первым источником 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.
В некоторых вариантах осуществления планировщика операций алгоритм планирования представляет собой алгоритм планирования в реальном времени.
В некоторых вариантах осуществления планировщика операций алгоритм планирования в реальном времени представляет собой алгоритм планирования на основе диспетчеризации по ближайшему предельному сроку (EDF).
В некоторых вариантах осуществления планировщика операций его способность определять прогнозный период обработки для каждой из (а) по меньшей мере одной операции 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, и (б) по меньшей мере одной операции I/O, сформированной вторым источником I/O, с использованием прогнозирующей модели, которая эмулирует работу накопителя на основе характеристик накопителя.
В контексте настоящего описания термин «сервер» означает компьютерную программу, выполняемую соответствующими аппаратными средствами и способную принимать запросы (например, от клиентских устройств) через сеть и выполнять эти запросы или инициировать их выполнение. Аппаратные средства могут представлять собой один физический компьютер или одну компьютерную систему и это не существенно для данной технологии. В настоящем контексте выражение «сервер» не означает, что каждая задача (например, принятая команда или запрос) или некоторая определенная задача принимается, выполняется или запускается одним и тем же сервером (т.е. одними и теми же программными и/или аппаратными средствами). Это выражение означает, что любое количество программных средств или аппаратных средств может принимать, отправлять, выполнять или запускать выполнение любой задачи или запроса либо результатов любых задач или запросов. Все эти программные и аппаратные средства могут представлять собой один сервер или несколько серверов, причем оба эти случая подразумеваются в выражении «по меньшей мере один сервер».
В контексте настоящего описания термин «клиентское устройство» означает любое компьютерное аппаратное средство, способное выполнять программы, подходящие для решения некоторой задачи. Таким образом, некоторые (не имеющие ограничительного характера) примеры клиентских устройств включают в себя персональные компьютеры (настольные, ноутбуки, нетбуки и т.п.), смартфоны и планшеты, а также сетевое оборудование, такое как маршрутизаторы, коммутаторы и шлюзы. Следует отметить, что в данном контексте устройство, функционирующее как клиентское устройство, также может функционировать как сервер для других клиентских устройств. Использование выражения «клиентское устройство» не исключает использования нескольких клиентских устройств для приема, отправки, выполнения или инициирования выполнения любой задачи или запроса, либо результатов любых задач или запросов, либо шагов любого описанного здесь способа.
В контексте настоящего описания выражение «информация» включает в себя информацию любого рода или вида, допускающую хранение в базе данных. Таким образом, информация включает в себя аудиовизуальные произведения (изображения, фильмы, звукозаписи, презентации и т.д.), данные (данные о местоположении, числовые данные и т.д.), текст (мнения, комментарии, вопросы, сообщения и т.д.), документы, электронные таблицы, списки слов и т.д., но не ограничивается ими.
В контексте настоящего описания выражение «компонент» включает в себя программное обеспечение (подходящее для определенных аппаратных средств), необходимое и достаточное для выполнения соответствующей определенной функции (или нескольких функций).
В контексте настоящего описания выражение «пригодный для использования в компьютере носитель информации» означает носители любого типа и вида, включая ОЗУ, ПЗУ, диски (CD-ROM, DVD, гибкие диски, жесткие диски и т.д.), USB-накопители, твердотельные накопители, накопители на магнитных лентах и т.д.
В контексте настоящего описания числительные «первый» «второй», «третий» и т.д. используются лишь для указания различия между существительными, к которым они относятся, но не для описания каких-либо определенных взаимосвязей между этими существительными. Например, должно быть понятно, что использование терминов «первый сервер» и «третий сервер» не подразумевает какого-либо определенного порядка, вида, хронологии, иерархии или классификации, в данном случае, серверов, и что их использование (само по себе) не подразумевает обязательного наличия «второго сервера» в любой ситуации. Кроме того, как встречается в настоящем описании в другом контексте, ссылка на «первый» элемент и «второй» элемент не исключает того, что эти два элемента могут быть одним и тем же реальным элементом. Таким образом, например, в некоторых случаях «первый» сервер и «второй» сервер могут представлять собой одно и то же программное и/или аппаратное средство, а в других случаях - различные программные и/или аппаратные средства.
Каждый вариант осуществления данной технологии имеет отношение к по меньшей мере одной из вышеупомянутых целей и/или к одному из вышеупомянутых аспектов, но не обязательно ко всем ним. Должно быть понятно, что некоторые аспекты данной технологии, связанные с попыткой достижения вышеупомянутой цели, могут не соответствовать этой цели и/или могут соответствовать другим целям, явным образом здесь не упомянутым.
Дополнительные и/или альтернативные признаки, аспекты и преимущества вариантов осуществления данной технологии содержатся в дальнейшем описании, в приложенных чертежах и в формуле изобретения.
Краткое описание чертежей
Дальнейшее описание приведено для лучшего понимания данной технологии, а также других аспектов и их признаков, и должно использоваться совместно с приложенными чертежами.
На фиг. 1 представлена схема системы, пригодной для реализации вариантов осуществления данной технологии, не имеющих ограничительного характера.
На фиг. 2 представлено соответствующее некоторым вариантам осуществления данной технологии устройство для хранения данных подсистемы распределенного хранения данных, которая приведена на фиг. 1.
На фиг. 3 представлена известная традиционная система с несколькими источниками для центрального процессора (CPU, Central Processing Unit).
На фиг. 4 представлена соответствующая вариантам осуществления данной технологии система с несколькими источниками для накопителя.
На фиг. 5 показан процесс формирования планировщиком операций, представленным на фиг. 4, прогнозного предельного срока обработки для операции ввода-вывода (I/O).
На фиг. 6 приведен первый не имеющий ограничительного характера пример определения алгоритмом уточнения планирования (SAA, Scheduling Adjustment Algorithm) в составе планировщика операций, представленного на фиг. 4, необходимости корректировки виртуального времени, используемого планировщиком операций.
На фиг. 7 приведен второй не имеющий ограничительного характера пример определения алгоритмом SAA в составе планировщика операций, представленного на фиг. 4, необходимости корректировки виртуального времени, используемого планировщиком операций.
На фиг. 8 показан процесс формирования планировщиком операций, представленным на фиг. 4, скорректированного прогнозного предельного срока обработки для операции I/O при корректировке виртуального времени.
На фиг. 9 приведена блок-схема способа, выполняемого в представленной на фиг. 4 системе с несколькими источниками и реализованного согласно вариантам осуществления данной технологии, не имеющим ограничительного характера.
Осуществление изобретения
На фиг. 1 представлена распределенная система 100 компьютерной обработки информации или сокращенно распределенная система 100 обработки информации. Распределенная система 100 обработки информации позволяет реализовать не имеющие ограничительного характера варианты осуществления данной технологии. Очевидно, что распределенная система 100 обработки информации приведена лишь в качестве иллюстративного варианта осуществления данной технологии. Таким образом, дальнейшее описание системы представляет собой описание примеров, иллюстрирующих данную технологию. Это описание не предназначено для определения объема или границ данной технологии.
В некоторых случаях также приводятся полезные примеры модификаций распределенной системы 100 обработки информации. Они способствуют пониманию, но также не определяют объема или границ данной технологии. Эти модификации не составляют исчерпывающего списка. Специалисту в данной области должно быть понятно, что возможны и другие модификации. Кроме того, если в некоторых случаях примеры модификаций не описаны, это не означает, что модификации невозможны и/или что описание содержит единственный вариант осуществления определенного элемента данной технологии. Специалисту в данной области должно быть понятно, что это не так. Кроме того, следует понимать, что распределенная система 100 обработки информации в некоторых случаях может представлять собой упрощенную реализацию данной технологии, и что такие варианты представлены, чтобы способствовать лучшему ее пониманию. Специалисту в данной области должно быть понятно, что другие варианты осуществления данной технологии могут быть значительно сложнее.
Распределенная система 100 обработки информации содержит источник 102 запросов, сеть 103 связи, подсистему 104 предварительной обработки запросов, подсистему 105 обработки транзакций, подсистему 106 маршрутизации транзакций, подсистему 108 распределенного хранения данных, подсистему 110 базы данных и операционную подсистему 111.
Далее описана реализация указанных выше компонентов распределенной системы 100 обработки информации в соответствии с различивши не имеющими ограничительного характера вариантами осуществления данной технологии.
Источник запросов
Источник 102 запросов может представлять собой электронное устройство, связанное с конечным пользователем (например, клиентское устройство), или любую другую подсистему распределенной системы 100 обработки информации, способную обеспечивать пользовательские запросы к распределенной системе 100 обработки информации. Несмотря на то, что на фиг. 1 показан лишь один источник 102 запросов, распределенная система 100 обработки информации может содержать несколько источников 102 запросов. Как показано в данном документе, источник 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, Solid State Drive), накопитель на жестких дисках (HDD, Hard Disk Drive) и т.п. Поэтому можно сказать, что по меньшей мере одно физическое запоминающее устройство может быть реализовано как устройство с подвижным или неподвижным диском.
Например, как показано на фиг. 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 с соблюдением соответствующих предельных сроков.
Как было упомянуто ранее, накопитель 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).
Чтобы обеспечить работу устройства 112 хранения данных в реальном времени и предотвратить описанную выше проблему, также известную как «торможение работы» (operation stagnation), устройство 112 хранения данных может содержать приложение 122 обеспечения работы в реальном времени. В целом, приложение 122 обеспечения работы в реальном времени позволяет управлять тем, какие операции I/O из числа уже упорядоченных планировщиком 120 передаются в текущий момент времени для обработки в накопитель 126.
Предполагается, что в некоторых вариантах осуществления данной технологии приложение 122 обеспечения работы в реальном времени может быть реализовано как часть приложения 116 Pdrive. Иными словами, вышеупомянутые функции приложения 122 обеспечения работы в реальном времени могут выполняться приложением 116 Pdrive в пределах объема данной технологии.
Устройство 112 хранения данных также может содержать по меньшей мере одно соответствующее приложение 118 моделирования накопителя для каждого накопителя 126 в устройстве 112 хранения данных. В целом, приложение 118 моделирования накопителя способно эмулировать идеальную работу накопителя 126 для анализа накопителя 126 в диагностических целях. Тем не менее, в других вариантах осуществления изобретения планировщик 120 также может использовать приложение 118 моделирования накопителя, чтобы упорядочивать операции I/O с целью их передачи в накопитель 126.
Предполагается, что в некоторых вариантах осуществления данной технологии по меньшей мере одно соответствующее приложение 118 моделирования накопителя может быть реализовано как часть приложения 116 Pdrive. Иными словами, вышеупомянутые функции по меньшей мере одного соответствующего приложения 118 моделирования накопителя могут выполняться приложением 116 Pdrive в пределах объема данной технологии.
Системы с несколькими источниками
В целом, система с несколькими источниками содержит элемент обработки задач и множество источников. Система с несколькими источниками реализована так, чтобы источники обеспечивали задачи для элемента обработки задач, который способен обрабатывать задачи, принятые от этих нескольких источников.
В некоторых системах с несколькими источниками может потребоваться одновременная обработка задач, принятых от нескольких источников. С этой целью система с несколькими источниками также может содержать планировщик, способный обеспечивать запланированный порядок обработки задач, принятых из различных источников системы с несколькими источниками, элементом обработки задач.
На фиг. 3 представлена традиционная система 300 с несколькими источниками, где элемент обработки задач реализован в виде центрального процессора (CPU) 302, а несколько источников реализованы в виде приложений 304 и 306. Традиционная система 300 с несколькими источниками может быть реализована, например, в электронном устройстве (не показано), которое содержит процессор 302 CPU и способно выполнять приложения 304 и 306. Приложения 304 и 306 обеспечивают задачи для обработки процессором 302 CPU.
Для одновременной обработки в процессоре 302 CPU задач из приложений 304 и 306 в традиционной системе 300 с несколькими источниками предусмотрена структура 308 планирования. Структура 308 планирования включает в себя алгоритмы 310 и 312 сервера постоянной производительности (CBS, Constant Bandwidth Server) и планировщик 314 для диспетчеризации на основе приоритета по ближайшему предельному сроку (EDF). Ниже описана конфигурация традиционного алгоритма CBS и планировщика EDF, а также обеспечение структурой 308 планирования запланированного порядка для принятых из приложений 304 и 306 задач, которые должны обрабатываться процессором 302 CPU.
Тем не менее, перед описанием алгоритмов 310 и 312 CBS и планировщика 314 EDF следует отметить, что каждое из приложений 304 и 306 связано с соответствующей заранее заданной долей U производительности процессора 302 CPU, выделенной для обработки задач соответствующего приложения. Например, можно предположить, что приложению 304 выделено 25% производительности (U=1/4) процессора 302 CPU для обработки задач приложения 304. Это означает, что до одной четвертой части всей производительности процессора 302 CPU может быть использовано для обработки задач приложения 304.
Заранее заданная доля U для источника в системе с несколькими источниками обычно выделяется для разделения производительности элемента обработки задач между несколькими источниками так, чтобы эти задачи от нескольких источников могли обрабатываться одновременно.
Также следует отметить, что структура 308 планирования включает в себя соответствующий алгоритм CBS для каждого из приложений 304 и 306. Иными словами, задачи приложения 304 принимаются алгоритмом 310 CBS, а задачи приложения 306 принимаются алгоритмом 312 CBS.
В общем случае, алгоритмы 310 и 312 CBS применяются, чтобы обеспечить «справедливое» использование производительности процессора 302 CPU для обработки задач, принятых от каждого из приложений 304 и 306. Иными словами, алгоритм CBS способен обеспечить, чтобы задачи, принятые из соответствующего приложения, обрабатывались процессором 302 CPU согласно заранее заданной доле U для соответствующего приложения. Например, алгоритм 310 CBS способен обеспечить, чтобы задачи, принятые от приложения 304, обрабатывались процессором 302 CPU с использованием соответствующих выделенных 25% производительности процессора 302 CPU.
С этой целью алгоритм CBS может выполняться на основе двух параметров: выделяемого времени Q (например, в миллисекундах) и периода Р (например, в миллисекундах). Иными словами, алгоритм CBS (например, один из алгоритмов 310 и 312 CBS) способен выделять время Q для обработки задач соответствующего приложения в процессоре 302 CPU в течение каждого периода Р времени. Два параметра Q и Р заранее заданы для каждого алгоритма CBS (например, одного из алгоритмов 310 и 312 CBS) на основе заранее заданной доли U производительности процессора 302 CPU, выделенной для обработки задач соответствующего приложения. Например, два параметра Q и Р алгоритма CBS могут быть заранее заданы согласно следующему уравнению:
Например, в случае алгоритма 310 CBS параметру Q может быть заранее задано значение 10 мс, а параметру Р может быть заранее задано значение 40 мс. Это означает, что для обеспечения выделения 25% (U=1/4) производительности процессора 302 CPU задачам приложения 304 алгоритм 310 CBS способен выделять до 10 мс для обработки задач приложения 304 в процессоре 302 CPU в течение каждого периода времени продолжительностью 40 мс.
В общем случае планировщик 314 EDF представляет собой планировщик реального времени, используемый для выполнения требований режима реального времени к традиционной системе 300 с несколькими источниками. Планировщик реального времени, такой как планировщик 314 EDF, предназначен для упорядочивания задач с целью их передачи в элемент обработки задач, такой как процессор 302 CPU, на основе соответствующих предельных сроков так, чтобы обеспечить обработку этих задач до истечения соответствующих предельных сроков. Например, планировщик 314 EDF упорядочивает принятые задачи так, чтобы задача с ближайшим предельным сроком завершения предавалась в процессор 302 CPU для обработки раньше других задач.
Ниже описаны два различных сценария планирования задачи приложения 304 для обработки в процессоре 302 CPU.
Тем не менее, перед описанием этих двух сценариев следует отметить, что задачи, принятые от приложения и предназначенные для обработки в процессоре 302 CPU, связаны с фактическим интервалом времени (или затратами С времени), необходимым для обработки соответствующей задачи. Например, если некоторая задача связана с затратами С времени длительностью 5 мс, это означает, что для обработки данной задачи в процессоре 302 CPU требуется 5 мс.
В первом сценарии (не показан) предполагается, что алгоритм 310 CBS принимает от приложения 304 задачу, связанную с затратами С времени длительностью 5 мс. Алгоритм 310 CBS может определить, что затраты С времени этой задачи меньше соответствующего выделяемого времени Q длительностью 10 мс для периода Р времени длительностью 40 мс. Таким образом, алгоритм 310 CBS может определить, что эта задача должна быть выполнена (полностью) в течение 40 мс с момента времени приема задачи, поскольку затраты С времени длительностью 5 мс для этой задачи меньше времени обработки длительностью 10 мс, выделенного для обработки задач от приложения 304 в течение следующего периода длительностью 40 мс.
В результате, в этом первом сценарии алгоритм 310 CBS может определить для задачи предельный срок, до истечения которого эта задача должна быть выполнена в процессоре CPU 301. В этом первом сценарии предельный срок составляет 40 мс с момента времени приема этой задачи.
Затем алгоритм 310 CBS способен передать задачу и соответствующий определенный предельный срок в планировщик 314 EDF. Планировщик 314 EDF принимает эту задачу и, возможно, другие задачи с соответствующими предельными сроками от других алгоритмов CBS, таких как алгоритм 312 CBS, и планирует их для передачи с целью обработки, как описано выше.
Во втором сценарии (представлен на фиг. 3) предполагается, что алгоритм 310 CBS принимает от приложения 304 задачу 320, связанную с затратами С времени длительностью 25 мс. Это означает, что в некоторых случаях, например, во втором сценарии, приложение (источник) может передавать задачи с затратами С времени, превышающими выделенное время Q соответствующего алгоритма CBS.
В этом втором сценарии алгоритм 310 CBS может определить, что, поскольку затраты С времени длительностью 25 мс превышают заранее заданное выделенное время Q длительностью 10 мс, задача 320 должна обрабатываться частями в течение нескольких следующих друг за другом периодов по 40 мс с соблюдением заранее заданной для приложения 304 доли U, равной 1/4. Поэтому, как показано на фиг. 3, алгоритм 310 CBS определяет, что:
- первая часть 322 задачи 320, связанная с затратами С времени длительностью 10 мс, должна быть обработана в течение 40 мс (один период Р времени) с момента времени приема задачи 320 (предельный срок для первой части 322 задачи);
- вторая часть 324 задачи 320, связанная с затратами С времени длительностью 10 мс, должна быть обработана в течение 80 мс (два периода Р времени) с момента времени приема задачи 320 (предельный срок для второй части 324 задачи);
- третья часть 326 задачи 320, связанная с затратами С времени длительностью 5 мс, должна быть обработана в течение 120 мс (три периода Р времени) с момента времени приема задачи 320 (предельный срок для третьей части 326 задачи).
Иными словами, в традиционной системе 300 с несколькими источниками, когда некоторая задача связана с затратами С времени, превышающими выделенное время Q алгоритма CBS, алгоритм CBS способен определять соответствующие предельные сроки для различных частей данной задачи с соблюдением заранее заданной доли U для соответствующего приложения.
Поэтому можно сказать, что в случае традиционной системы 300 с несколькими источниками алгоритм 310 CBS способен разделять задачу 320 на три части, поскольку задачи, которые должны обрабатываться в процессоре 302 CPU, являются приостанавливаемыми. Иными словами, не требуется, чтобы в традиционных системах 300 с несколькими источниками задачи обрабатывались как одно целое. Это означает, что первая часть 322 задачи 320 может быть обработана в процессоре 302 CPU до первого момента времени, когда обработка задачи 320 приостанавливается для обработки другой задачи до второго момента времени, когда процессор 302 CPU возобновляет обработку задачи 320 путем обработки второй части 324 задачи, и т.д.
Таким образом, традиционные алгоритмы CBS хорошо подходят для обеспечения справедливого использования производительности элемента обработки задач при обработке задач, принятых от нескольких источников традиционной системы с несколькими источниками, где подлежащие обработке задачи являются приостанавливаемыми так, чтобы задачу можно было разделить на части для обработки с соответствующими предельными сроками, когда затраты С времени для задачи превышают выделенное время Q соответствующего алгоритма CBS.
В некоторых вариантах осуществления данной технологии предполагается, что системы с несколькими источниками содержат элементы обработки задач, реализованные в виде накопителей. В не имеющем ограничительного характера примере предполагается, что система с несколькими источниками в контексте данной технологии может содержать накопитель 126 и несколько приложений 114 Vdrive, как показано на фиг. 1.
В отличие от процессора 302 CPU, способного обрабатывать приостанавливаемые задачи, накопитель 126 способен обрабатывать операции I/O, как описано выше. В большинстве случаев операции I/O не являются приостанавливаемыми задачами, т.е. большинство операций I/O должны обрабатываться как одно целое. Иными словами, в большинстве случаев операция I/O не может быть разделена на части, которые накопитель 126 мог бы обрабатывать по отдельности.
Таким образом, структура 308 планирования, содержащая традиционные алгоритмы CBS, не подходит для определения предельных сроков для операций I/O в системе с несколькими источниками, когда элемент обработки задач реализован в виде накопителя. Разработчики данной технологии разработали не имеющие ограничительного характера варианты осуществления планировщиков операций I/O, пригодных для систем с несколькими источниками, где требуется планирование обработки накопителем операций I/O от нескольких источников I/O.
Технический результат данного решения заключается в повышении точности планирования операций ввода/вывода, которые должны обрабатываться накопителем, входящим в состав распределенной компьютерной системы.
Планировщики I/O для операций I/O
На фиг. 4 представлена система 400 с несколькими источниками, соответствующая не имеющему ограничительного характера примеру осуществления данной технологии. Система 400 с несколькими источниками содержит первый источник 404 I/O и второй источник 406 I/O. Например, первый источник 404 I/O может быть реализован в виде первого приложения 114 Vdrive, формирующего операции I/O, а второй источник 406 I/O может быть реализован в виде второго приложения 114 Vdrive, формирующего операции I/O.
Система 400 с несколькими источниками также содержит накопитель 402 и планировщик 408 операций. Например, накопитель 402 может быть реализован в виде накопителя 126, представленного на фиг. 1. Планировщик 408 операций может быть реализован в виде планировщика 120, представленного на фиг. 1. Как описано выше, планировщик 120 может быть реализован в виде приложения 116 Pdrive. Следовательно, планировщик 408 операций может быть реализован в виде части приложения 116 Pdrive в пределах объема данной технологии.
Планировщик 408 операций содержит модель 470 накопителя, модуль 450 планирования и алгоритм 460 уточнения планирования (SAA). Далее описаны функции различных компонентов планировщика 408 операций.
Модель 470 накопителя связана с накопителем 402. Подобно приложению 118 моделирования накопителя, способному эмулировать идеальную работу накопителя 126, модель 470 накопителя может быть способной эмулировать идеальную работу накопителя 402. На практике в тех вариантах осуществления, где накопитель 402 реализован в виде накопителя 126, модель 470 накопителя может быть реализована в виде приложения 118 моделирования накопителя в пределах объема данной технологии.
Предполагается, что модель 470 накопителя представляет собой прогнозирующую модель, созданную для эмулирования работы накопителя 402 на основе характеристик накопителя 402.
Модель 470 накопителя может использоваться модулем 450 планирования для прогнозирования параметров, на основе которых некоторые компоненты модуля 450 планирования могут быть способны определять прогнозные предельные сроки обработки для соответствующих операций I/O. Это более подробно описано ниже, тем не менее, следует отметить, что модель 470 накопителя может быть способной прогнозировать время обработки, требуемое накопителю 402 для обработки операции I/O, т.е. модель 470 накопителя может быть способной определять прогнозные затраты С* времени для этой операции I/O.
В целом, модуль 450 планирования способен формировать или определять прогнозные предельные сроки обработки для операций I/O, принятых от первого источника 404 I/O и от второго источника 406 I/O (а также от других возможных источников I/O), и на основе сформированных прогнозных предельных сроков обработки формировать запланированный порядок операций I/O для их дальнейшей обработки накопителем 402.
Модуль 450 планирования содержит соответствующий алгоритм формирования предельного срока (DG, Deadline Generation) для каждого источника I/O системы 400 с несколькими источниками: первый алгоритм 454 DG для первого источника 404 I/O и второй алгоритм 456 DG для второго источника 406 I/O.
Подобно описанному выше, каждый источник I/O связан с соответствующей заранее заданной долей U производительности накопителя 402. В целом, первый алгоритм 454 DG и второй алгоритм 456 DG применяются для обеспечения справедливого совместного использования производительности накопителя 402 первым источником 404 I/O и вторым источником 406 I/O (например, согласно соответствующим заранее заданным долям U).
Первый алгоритм 454 DG способен формировать прогнозные предельные сроки обработки для операций I/O от первого источника 404 I/O так, чтобы заранее заданная доля U1, связанная с первым источником 404 I/O, использовалась для обработки операций I/O от первого источника 404 I/O. Подобным образом, второй алгоритм 456 DG способен формировать прогнозные предельные сроки обработки для операций I/O от второго источника 406 I/O так, чтобы заранее заданная доля U2, связанная со вторым источником 406 I/O, использовалась для обработки операций I/O от второго источника 406 I/O. Поэтому предполагается, что первый алгоритм 454 DG и второй алгоритм 456 DG могут быть способны (а) использовать модель 470 накопителя для прогнозирования затрат С времени для принятых операций I/O и (б) на основе этих прогнозных затрат С* времени для операций I/O формировать прогнозные предельные сроки обработки для принятых операций I/O.
Ниже более подробно описан алгоритм DG для формирования прогнозных предельных сроков обработки для операций I/O соответствующего источника I/O.
Следует отметить, что алгоритм DG, реализованный в виде части модуля 450 планирования, работает в соответствии с виртуальным временем, а не в соответствии с фактическим временем. В контексте данной технологии виртуальное время используется для представления интервалов времени обработки (или их суммы), запланированных для накопителя 402.
Далее более подробно описана конфигурация алгоритма DG для работы в соответствии с виртуальным временем.
Модуль 450 планирования также содержит алгоритм 458 планирования в реальном времени. В общем случае алгоритм 458 планирования в реальном времени используется для выполнения требований режима реального времени к системе 400 с несколькими источниками. Алгоритм 458 планирования в реальном времени способен упорядочивать операции I/O для передачи в накопитель 402 так, чтобы операции I/O могли обрабатываться накопителем 402 до истечения соответствующих прогнозных предельных сроков обработки (сформированных соответствующими алгоритмами DG).
На реализуемый вторым модулем 450 планирования алгоритм планирования в реальном времени не накладывается каких-либо особых ограничений. Тем не менее, в одном не имеющем ограничительного характера примере алгоритм 458 планирования в реальном времени может быть реализован как алгоритм планирования типа EDF.
Как более подробно описано ниже, операции I/O, упорядоченные алгоритмом 458 планирования в реальном времени, могут передаваться в накопитель 402 в пакетах. Например, в некоторых вариантах осуществления данной технологии планировщик 408 операций может быть способным группировать упорядоченные операции I/O в пакеты I/O и передавать эти пакеты I/O в накопитель 402 для обработки.
В других вариантах осуществления, где накопитель 402 реализован в виде накопителя 126, объединение операций I/O в пакеты I/O может выполнять промежуточный компонент, например, приложение 122 обеспечения работы в реальном времени. Например, планировщик 408 операций может быть способным передавать упорядоченные операции I/O в приложение 122 обеспечения работы в реальном времени, которое затем группирует их в пакеты I/O и передает эти пакеты I/O в накопитель 402 для обработки.
Как описано выше, планировщик 408 операций также включает в себя алгоритм 460 SAA. В общем случае алгоритм 460 SAA способен корректировать виртуальное время, на основе которого работают алгоритмы DG. С учетом того, что алгоритмы DG формируют прогнозные предельные сроки обработки для операций I/O на основе соответствующих прогнозных затрат С* времени, предоставленных моделью 470 накопителя, эти сформированные прогнозные предельные сроки обработки в виртуальном времени могут не соответствовать фактическому времени, поскольку затраты С* времени, на основе которых они сформированы, могут не соответствовать фактическим затратам С времени для операций I/O.
Предполагается, что алгоритм 460 SAA способен принимать от накопителя 402 данные, указывающие фактическое время обработки (т.е. фактические затраты С времени), необходимое для обработки операций I/O в любом пакете I/O. Алгоритм 460 SAA также может быть способным сравнивать фактические затраты С времени для операций I/O в пакете I/O с прогнозными затратами С* времени для операций I/O в пакете I/O. Затем алгоритм 460 SAA может быть способным корректировать виртуальное время, на основе которого работают алгоритмы DG, в зависимости от результата сравнения фактических затраты С времени для операций I/O в пакете I/O с прогнозными затратами С* времени для операций I/O в пакете I/O. В дальнейшем скорректированное виртуальное время используется для планирования будущих операций I/O.
Например, благодаря корректировке виртуального времени алгоритмы DG могут определять скорректированные прогнозные периоды Р* обработки и скорректированные прогнозные предельные сроки обработки для будущих операций I/O.
Ниже более подробно описано как и когда алгоритм 460 SAA корректирует виртуальное время, на основе которого работают алгоритмы DG.
Планирование операций I/O
Далее со ссылками на фиг. 5 описан не имеющий ограничительного характера пример планирования операции I/O планировщиком 408 операций для ее обработки накопителем 402. Можно предположить, что первый источник 404 I/O передает операцию 520 I/O в планировщик 408 операций. Первый алгоритм 454 DG принимает операцию 520 I/O и способен определить/сформировать прогнозный предельный срок обработки для операции 520 I/O.
Как указано выше, когда операция 520 I/O принята первым алгоритмом 454 DG, фактические затраты С1 времени для операции 520 I/O неизвестны. Первый алгоритм 454 DG способен использовать модель 470 накопителя (например, прогнозирующую модель, созданную на основе характеристик накопителя 402) для прогнозирования затрат С1 времени на операцию 520 I/O. Как описано выше, модель 470 накопителя способна эмулировать идеальную работу накопителя 402 и в результате на основе операции 520 I/O определять прогнозные затраты С1* времени на операцию 520 I/O.
Можно предположить, что модель 470 накопителя определяет, что прогнозные затраты С1* времени для операции 520 I/O составляют величину 25 мс. Иными словами, модель 470 накопителя определяет, что накопителю 402 для обработки операции 520 I/O потребуется 25 мс. Модель 470 накопителя способна передать прогнозные затраты С1* времени длительностью 25 мс в первый алгоритм 454 DG.
Как описано выше, большинство операций I/O не являются приостанавливаемыми, т.е. накопитель 402 должен обработать операцию 520 I/O как одно целое. По этой причине алгоритм 454 DG способен динамически определять прогнозное выделенное время Q1* и прогнозный период Р1* обработки для операции 520 I/O так, (а) чтобы операция I/O 520 не разделялась на части при ее обработке и (б) чтобы обеспечивалась заранее заданная доля U1 производительности накопителя 402, выделенная для первого источника 404 I/O.
Поэтому первый алгоритм 454 DG способен первоначально определять прогнозное выделенное время Q1* так, чтобы операция 520 I/O не разделялась на части при обработке. Первый алгоритм 454 DG может определять, что прогнозное выделенное время Q1* должно быть по меньшей мере равно прогнозным затратам С1* времени длительностью 25 мс на операцию 520 I/O.
Следует отметить, что для того, чтобы не разделять обработку операции I/O (поскольку она не является приостанавливаемой) для определенного периода Р обработки, выделенное время Q должно быть по меньшей мере равно затратам С времени для этой операции I/O. В результате можно предположить, что первый алгоритм DG определяет, что прогнозное выделенное время Q1* равно 25 мс (т.е. равно прогнозным затратам С1* времени длительностью 25 мс для операции 520 I/O).
Далее, когда прогнозное выделенное время Q1* определено первым алгоритмом 454 DG, первый алгоритм 454 DG способен определить прогнозный период Р1* обработки для операции 520 I/O так, чтобы учитывалась заранее заданная доля U1 производительности накопителя 402, выделенная источнику 404 I/O.
Если предполагается, что доля U1 равна 1/4 (или 25% производительности накопителя 402), то первый алгоритм 454 DG может быть способным определять прогнозный период Р1* обработки с использованием представленного выше уравнения (1). Это означает, что первый алгоритм 454 DG может определить, что прогнозный период Р1* обработки равен 100 мс (например, PI*=Q1*/U1=25 мс/0,25=100 мс).
Таким образом, можно сказать, что алгоритм DG может быть способным динамически прогнозировать параметры Q* и Р* для соответствующего источника I/O на основе соответствующих прогнозных затрат С* времени для операции I/O из соответствующего источника I/O и соответствующей заранее заданной доли U.
Следует отметить, что прогнозный период Р1* обработки для операции 520 I/O определен так, чтобы операция 520 I/O могла быть обработана накопителем 402 без приостановки в течение прогнозного периода Р1* обработки с соблюдением заранее заданной доли U1 производительности.
В представленном на фиг. 5 не имеющем ограничительного характера примере первый алгоритм 454 DG может определить, что прогнозный предельный срок обработки для операции 520 I/O равен 100 мс с момента времени приема операции 520 I/O для планирования.
Следует отметить, что обработка операции 520 I/O, выполняемая непосредственно перед истечением прогнозного предельного срока обработки, показана на фиг. 5 только для иллюстрации и не является обязательной для всех не имеющих ограничительного характера вариантов осуществления данной технологии. В действительности цель заключается не в том, чтобы обработать операцию 520 I/O непосредственно перед истечением прогнозного предельного срока обработки, а в том, чтобы к моменту достижения прогнозного предельного срока обработки операция 520 I/O была обработана.
Также следует отметить, что, как показано на фиг. 5, первый алгоритм 454 DG работает в виртуальном времени (см. ось VT(t)). Иными словами, первый алгоритм 454 DG способен выражать прогнозный предельный срок обработки в виртуальном времени, а не в фактическом времени. Как указано выше, в некоторых примерах виртуальное время, в котором выражается прогнозный предельный срок обработки операции 520 I/O, может быть скорректировано алгоритмом 460 SAA. В результате прогнозный предельный срок обработки данной операции I/O может зависеть не только от момента времени приема данной операции I/O для планирования и от прогнозного периода Р* обработки, но и от корректировки виртуального времени алгоритмом 460 SAA.
Тем не менее, исключительно для упрощения можно предположить, что в момент времени, когда прогнозный предельный срок обработки для операции 520 I/O был определен первым алгоритмом 454 DG, алгоритм 460 SAA еще не скорректировал виртуальное время. Ниже более подробно описана корректировка виртуального времени алгоритмом 460 SAA и влияние этой корректировки на прогнозные предельные сроки обработки операций I/O, принятых после корректировки виртуального времени.
Когда прогнозный предельный срок обработки операции 520 I/O определен, как описано выше, операция 520 I/O и соответствующий прогнозный предельный срок обработки передаются первым алгоритмом 454 DG в алгоритм 458 планирования в реальном времени.
Следует отметить, что второй алгоритм 456 DG может быть способным определять прогнозные предельные сроки обработки для операций I/O от второго источника 406 I/O подобно тому, как первый алгоритм 454 DG определяет прогнозный предельный срок обработки для операции 520 I/O от первого источника 404 I/O.
Как описано выше, алгоритм 458 планирования в реальном времени упорядочивает операции I/O, принятые от первого алгоритма 454 DG и от второго алгоритма 456 DG (а также от других возможных алгоритмов DG), на основе соответствующих прогнозных предельных сроков обработки, определенных соответствующими алгоритмами DG. Затем алгоритм 458 планирования в реальном времени может передавать упорядоченные операции I/O для их обработки накопителем 402.
Далее со ссылками на фиг. 6 и фиг. 7 описан алгоритм 460 SAA для селективной корректировки виртуального времени.
Корректировка виртуального времени
Как описано выше, операции I/O могут приниматься накопителем 402 в пакетах I/O. Например, как показано на фиг. 6, накопитель 402 может принимать пакет 602 I/O, содержащий четыре операции 604, 606, 608 и 610 I/O для обработки.
Накопитель 402 способен обработать операции 604, 606, 608 и 610 I/O из пакета 602 I/O. Накопитель 402 может быть способным передавать подтверждения обработки, указывающие, что операции 604, 606, 608 и 610 I/O обработаны (дополнительно или в качестве альтернативы подтверждение обработки может указывать полностью обработанный пакет 602 I/O), в алгоритм 460 SAA.
Предполагается, что подтверждения обработки могут указывать фактическое время обработки, которое потребовалось (т.е. которое фактически затрачено накопителем 402) для обработки операций 604, 606, 608 и 610 I/O. Иными словами, алгоритм 460 SAA может принимать указания на фактические затраты С времени, которые потребовались для обработки операций 604, 606, 608 и 610 I/O.
Алгоритм 460 SAA также может быть способным принимать от модуля 450 планирования и/или от модели 470 накопителя данные, указывающие прогнозное время обработки, определенное для операций 604, 606, 608 и 610 I/O в процессе планирования. Иными словами, алгоритм 460 SAA может принимать данные, указывающие прогнозные затраты С* времени, определенные моделью 470 накопителя для операций 604, 606, 608 и 6101/0.
Алгоритм 460 SAA способен сравнивать фактические затраты С времени для операций 604, 606, 608 и 610 I/O с прогнозными затратами С* времени для операций 604, 606, 608 и 610 I/O. Можно предположить, что показанное на фиг. 6 значение 660 представляет собой сумму прогнозных затрат С* времени для операций 604, 606, 608 и 610 I/O, а значение 650 представляет собой сумму фактических затрат С времени для операций 604, 606, 608 и 610 I/O.
Следует отметить, что расположенная под углом 45 градусов штриховая линия (без числового обозначения) показана на фиг. 6 исключительно для наглядной иллюстрации результата сравнения значения 660 и значения 650. Таким образом, следует отметить, что алгоритм 460 SAA не предназначен для отображения или формирования штриховой линии или иного графического представления (без числового обозначения) результата сравнения значения 660 и значения 650.
В этом случае алгоритм 460 SAA определяет, что значение 660 больше значения 650 на значение 670. Это означает, что накопитель 402 фактически обработал операции 604, 606, 608 и 610 быстрее, чем это предполагалось моделью 470 накопителя, на величину времени, соответствующую значению 670. В этом случае алгоритм 460 SAA может определить, что виртуальное время, на основе которого работают алгоритмы DG, не требует корректировки.
Можно предположить, что показанное на фиг. 7 значение 760 представляет собой сумму прогнозных затрат С* времени для операций 604, 606, 608 и 610 I/O, а значение 750 представляет собой сумму фактических затрат С времени для операций 604, 606, 608 и 610 I/O.
Следует отметить, что расположенная под углом 45 градусов штриховая линия (без числового обозначения) показана на фиг. 7 исключительно для наглядной иллюстрации результата сравнения значения 760 и значения 750. Таким образом, следует отметить, что алгоритм 460 SAA не предназначен для отображения или формирования штриховой линии или иного графического представления (без числового обозначения) результата сравнения значения 760 и значения 750.
В этом случае алгоритм 460 SAA определяет, что значение 760 меньше значения 750 на значение 770. Это означает, что накопитель 402 фактически обработал операции 604, 606, 608 и 610 медленнее, чем это предполагалось моделью 470 накопителя, на величину времени, соответствующую значению 770. В этом случае алгоритм 460 SAA может определить, что виртуальное время, на основе которого работают алгоритмы DG, требует корректировки.
Таким образом, предполагается, что в некоторых вариантах осуществления данной технологии алгоритм 460 SAA может быть способным селективно корректировать виртуальное время, если сумма фактических затрат С времени для операций I/O превышает сумму прогнозных затрат С* времени для операций I/O.
Если сумма фактических затрат С времени для операций I/O превышает сумму прогнозных затрат С* времени для операций I/O, алгоритм 460 SAA может быть способным селективно корректировать виртуальное время алгоритмов DG на количество времени, равное разности между суммой фактических затрат С времени и суммой прогнозных затрат С* времени. В представленном на фиг. 7 примере алгоритм 460 SAA может быть способным селективно скорректировать виртуальное время на интервал времени, соответствующий значению 770.
Далее со ссылками на фиг. 8 описано, как селективная корректировка виртуального времени алгоритмом 460 SAA влияет на прогнозные периоды Р* обработки и на прогнозные предельные сроки обработки, определенные алгоритмами DG после корректировки виртуального времени.
Можно предположить, что значение 770 равно 15 мс. Это означает, что алгоритм 460 SAA способен скорректировать виртуальное время, на основе которого работают алгоритмы DG, на 15 мс.
Также можно предположить, что операция 820 I/O была принята от первого источника 404 I/O подобно тому, как операция 520 I/O была принята от первого источника 404 I/O. Тем не менее, можно предположить, что операция 820 I/O была принята после корректировки виртуального времени алгоритмом 460 SAA. Таким образом, можно сказать, что операция 820 I/O представляет собой будущую операцию I/O, планируемую планировщиком 408 операций после корректировки виртуального времени.
Подобно тому, как прогнозные затраты С1* времени определены моделью 470 накопителя для операции 520 I/O, модель 470 накопителя может определить прогнозные затраты С2* для операции 820 I/O. Можно предположить, что модель 470 накопителя определяет, что прогнозные затраты С2* времени составляют 25 мс (аналогично затратам С1* времени). Подобно тому, как первый алгоритм 454 DG определил прогнозное выделенное время Q1* длительностью 25 мс и прогнозный период Р1* обработки длительностью 100 мс для операции 520 I/O, первый алгоритм 454 DG может быть способным определить прогнозное выделенное время Q2* длительностью 25 мс и прогнозный период Р2* обработки длительностью 100 мс для операции 820 I/O.
Тем не менее, поскольку виртуальное время было скорректировано к моменту времени определения первым алгоритмом 454 DG прогнозного периода Р2* обработки для операции 820 I/O, первый алгоритм 454 DG способен скорректировать прогнозный период Р2* обработки для операции 820 I/O на интервал времени, равный интервалу времени, на который было скорректировано виртуальное время. Иными словами, в этом случае первый алгоритм 454 DG способен добавить интервал времени, на который было скорректировано виртуальное время, к прогнозному периоду Р2* обработки для определения скорректированного прогнозного периода обработки операции 820 I/O.
В этом случае первый алгоритм DG способен добавить 15 мс к прогнозному периоду Р2* обработки длительностью 100 мс, определив скорректированный прогнозный период обработки длительностью 115 мс для операции 820 I/O.
Как показано на фиг. 8, первый алгоритм 454 DG способен сформировать скорректированный прогнозный предельный срок обработки для операции 820 I/O длительностью 115 мс (Р2* (100 мс)+значение 770 (15 мс)) с момента времени приема операции 820 I/O для планирования.
Алгоритм 460 SAA корректирует виртуальное время алгоритмов DG для того, чтобы можно было сформировать скорректированные прогнозные предельные сроки обработки для будущих (последующих) операций I/O с учетом возможной ошибки, связанной с определенными моделью 470 накопителя прогнозными затратами С* времени для предыдущих операций I/O. Путем добавления интервала времени, соответствующего интервалу времени, на который было скорректировано виртуальное время, к прогнозному периоду Р* времени для определения скорректированного прогнозного предельного срока обработки соответствующей операции I/O, можно скорректировать или по меньшей мере уменьшить несоответствие, возникшее вследствие неточного определения моделью 470 накопителя прогнозных затрат С* времени для операций I/O.
Как описано выше, виртуальное время используется для представления интервалов времени обработки (или их суммы), запланированных для накопителя 402. Тем не менее, если используются прогнозные затраты С* времени, меньшие фактических затрат С времени для операций I/O, то запланированные для накопителя 402 интервалы времени обработки «ошибочно» получаются меньшими на величину времени, равную разности между прогнозными затратами С* времени и фактическими затратами С времени для операций I/O. Иными словами, время обработки операций I/O могло быть занижено моделью 470 накопителя. Таким образом, корректировка прогнозного предельного срока обработки на 15 мс в представленном на фиг. 8 примере позволяет полностью или по меньшей мере частично скорректировать такое ошибочное планирование для операций I/O, запланированных после корректировки виртуального времени.
Следует отметить, что алгоритм 460 SAA может быть способным селективно и периодически корректировать виртуальное время. Например, алгоритм 460 SAA может быть способным сравнивать сумму фактических затрат С времени для операций I/O и сумму прогнозных затрат С* времени для операций I/O в каждом пакете I/O, обработанном накопителем 402, и может соответствующим образом селективно корректировать виртуальное время каждый раз, когда сумма прогнозных затрат С* времени для операций I/O меньше суммы фактических затрат С времени для операций I/O. При необходимости эта корректировка виртуального времени может периодически выполняться для каждого обработанного пакета I/O. В качестве альтернативы, эта корректировка виртуального времени при необходимости может периодически выполняться для каждой обработанной операции I/O.
Таким образом, даже если модель 470 накопителя может занижать некоторые затраты С времени для некоторых операций I/O, описанная выше периодическая корректировка виртуального времени позволяет периодически полностью или по меньшей мере частично корректировать ошибочное планирование интервалов времени обработки для накопителя 402 планировщиком 408 операций.
Предполагается, что описанная выше корректировка виртуального времени позволяет обеспечивать скорректированные прогнозные предельные сроки обработки для операций I/O, которые соответствуют более поздним моментам времени по сравнению со случаем использования нескорректированного виртуального времени (например, более поздним срокам по сравнению с соответствующими прогнозными предельными сроками обработки). Это может способствовать обработке будущих операций I/O до истечения соответствующих сформированных скорректированных прогнозных предельных сроков обработки.
В некоторых вариантах осуществления данной технологии планировщик 408 операций способен выполнять представленный на фиг. 9 способ 900 для планирования операций I/O с целью их обработки накопителем 402. Способ 900 описан далее.
Шаг 902: прием (а) по меньшей мере одной операции I/O, сформированной первым источником I/O, и (б) по меньшей мере одной операции I/O, сформированной вторым источником I/O.
Способ 900 начинается с шага 902, на котором планировщик 408 операций способен принимать по меньшей мере одну операцию I/O, сформированную первым источником 404 I/O (см. фиг. 5), например, операцию 520 I/O, и по меньшей мере одну операцию I/O, сформированную вторым источником 406 I/O.
Следует отметить, что первый источник 404 I/O связан с соответствующей заранее заданной долей U1 производительности накопителя 402 для обработки по меньшей мере одной операции I/O, сформированной первым источником 404 I/O (такой как операция 520 I/O). Подобным образом, второй источник 406 I/O связан с соответствующей заранее заданной долей производительности накопителя 402 для обработки по меньшей мере одной операции I/O, сформированной вторым источником 406 I/O, как описано выше.
Шаг 904: определение на основе характеристик накопителя прогнозного времени обработки для (а) по меньшей мере одной операции I/O, сформированной первым источником I/O, и (б) по меньшей мере одной операции I/O, сформированной вторым источником I/O.
Способ 900 продолжается на шаге 904, на котором планировщик 408 операций на основе характеристик накопителя 402 способен определять прогнозное время обработки (прогнозные затраты С* времени) для каждой из по меньшей мере одной операции I/O, сформированной первым источником 404 I/O, и по меньшей мере одной операции I/O, сформированной вторым источником 406 I/O.
Предполагается, что планировщик 408 операций способен выполнять шаг 904 с использованием модели 470 накопителя. Как описано выше, модель 470 накопителя представляет собой прогнозирующую модель, которая эмулирует работу накопителя 402 на основе характеристик накопителя 402.
В случае операции 502 I/O, представленной на фиг. 5, планировщик 408 операций может использовать модель 470 накопителя (созданную на основе характеристик накопителя 402) для определения прогнозного времени обработки (прогнозных затрат С1* времени) на основе операции 520 I/O.
Шаг 906: определение прогнозного периода обработки для каждой из (а) по меньшей мере одной операции I/O, сформированной первым источником I/O, и (б) по меньшей мере одной операции I/O, сформированной вторым источником I/O, с использованием (а) соответствующего прогнозного времени обработки и (б) соответствующей заранее заданной доли производительности накопителя, причем соответствующий прогнозный период обработки указывает прогнозный предельный срок обработки, а прогнозные предельные сроки обработки выражены в виртуальном времени планировщика операций.
Способ 900 продолжается на шаге 906, на котором планировщик 408 операций способен определять прогнозный период (Р*) обработки для каждой из по меньшей мере одной операции I/O, сформированной первым источником 404 I/O, и по меньшей мере одной операции I/O, сформированной вторым источником 406 I/O.
Например, шаг 906 может выполняться планировщиком 408 операций с использованием алгоритмов DG, как описано выше.
Планировщик 408 операций способен определять соответствующий прогнозный период Р* обработки на основе соответствующего прогнозного времени обработки (соответствующих прогнозных затрат С* времени) и соответствующей заранее заданной доли производительности накопителя 402 (соответствующей доли U).
Предполагается, что планировщик 408 операций может быть способным определить соответствующий прогнозный период Р* обработки путем определения соотношения соответствующего прогнозного времени обработки (соответствующих прогнозных затрат С* времени) и соответствующей заранее заданной доли производительности накопителя 402 (соответствующей доли U).
В случае операции 520 I/O, представленной на фиг. 5, планировщик 408 операций может определить прогнозный период Р1* обработки с использованием отношения прогнозных затрат С1* времени и соответствующей заранее заданной доли U1 производительности накопителя 402.
Предполагается, что операция 520 I/O может представлять собой операцию I/O, для которой не предусмотрена приостановка, т.е. операция 520 I/O должна быть обработана накопителем 402 как одно целое, без разделения обработки операции 520 I/O.
Таким образом, как описано выше и показано на фиг. 5, определение прогнозного периода Р1* выполняется так, чтобы операция 520 I/O могла быть обработана накопителем 402 без приостановки в течение прогнозного периода Р1* обработки с соблюдением заранее заданной доли U1 производительности накопителя 402, выделенной для первого источника 404 I/O, сформировавшего операцию 520 I/O.
Шаг 908: выполнение алгоритма планирования для определения запланированного порядка операций I/O на основе соответствующих прогнозных предельных сроков обработки для (а) по меньшей мере одной операции I/O, сформированной первым источником I/O, и (б) по меньшей мере одной операции I/O, сформированной вторым источником I/O.
Способ 900 продолжается на шаге 908, на котором планировщик 408 операций способен выполнять алгоритм планирования для определения запланированного порядка операций I/O на основе соответствующих прогнозных предельных сроков обработки для
(а) по меньшей мере одной операции I/O, сформированной первым источником 404 I/O, и
(б) по меньшей мере одной операции I/O, сформированной вторым источником 406 I/O.
Планировщик 408 операций способен выполнять шаг 908 путем выполнения алгоритма 458 планирования в реальном времени. В некоторых вариантах осуществления изобретения предполагается, что алгоритм 458 планирования в реальном времени может представлять собой алгоритм планирования на основе диспетчеризации по ближайшему предельному сроку (EDF).
Например, (а) по меньшей мере одна операция I/O, сформированная первым источником 404 I/O, и (б) по меньшей мере одна операция I/O, сформированная вторым источником 406 I/O, могут передаваться в алгоритм 458 планирования в реальном времени вместе с соответствующими прогнозными предельными сроками обработки.
В результате алгоритм 458 планирования в реальном времени может определить запланированный порядок операций I/O (запланированный порядок для (а) по меньшей мере одной операции I/O, сформированной первым источником 404 I/O, и (б) по меньшей мере одной операции I/O, сформированной вторым источником 406 I/O) на основе соответствующих прогнозных предельных сроков обработки.
В некоторых вариантах осуществления изобретения операции I/O, упорядоченные алгоритмом 458 планирования в реальном времени, могут передаваться планировщиком 408 операций в накопитель 402 в пакетах. Например, в некоторых вариантах осуществления данной технологии планировщик 408 операций может быть способным группировать упорядоченные операции I/O в пакеты I/O и передавать эти пакеты I/O в накопитель 402 для обработки.
В других вариантах осуществления, где накопитель 402 реализован в виде накопителя 126, объединение операций I/O в пакеты I/O может выполнять промежуточный компонент, например, приложение 122 обеспечения работы в реальном времени. В частности, планировщик 408 операций может быть способным передавать упорядоченные операции I/O в приложение 122 обеспечения работы в реальном времени, которое затем группирует их в пакеты I/O и передает эти пакеты I/O в накопитель 402 для обработки.
Шаг 910: контроль планировщиком операций фактического времени обработки для (а) по меньшей мере одной операции I/O, сформированной первым источником I/O, и (б) по меньшей мере одной операции I/O, сформированной вторым источником I/O, причем фактическое время обработки представляет собой фактическое время, затраченное накопителем на обработку (а) по меньшей мере одной операции I/O, сформированной первым источником I/O, и (б) по меньшей мере одной операции I/O, сформированной вторым источником I/O.
Способ 900 продолжается на шаге 910, на котором планировщик 408 операций способен контролировать фактическое время обработки (фактические затраты С времени) для обработки (а) по меньшей мере одной операции I/O, сформированной первым источником 404 I/O, и (б) по меньшей мере одной операции I/O, сформированной вторым источником 406 I/O.
Например, шаг 910 может выполняться планировщиком 408 операций с использованием алгоритма 460 SAA.
Планировщик 408 операций может контролировать фактическое время, затраченное накопителем на обработку (а) по меньшей мере одной операции I/O, сформированной первым источником 404 I/O, и (б) по меньшей мере одной операции I/O, сформированной вторым источником 406 I/O.
Например, как показано на фиг. 6, планировщик 408 операций может контролировать фактические затраты С времени для операций 604, 606, 608 и 610 I/O. В некоторых вариантах осуществления изобретения планировщик 408 операций может по отдельности контролировать фактические затраты С времени для операций 604, 606, 608 и 610 I/O. В других вариантах осуществления изобретения планировщик 408 операций может контролировать фактические затраты С времени для группы операций 604, 606, 608 и 610 I/O путем контроля фактического времени, затраченного накопителем 402 на обработку пакета 602 I/O.
Следует отметить, что фактическое время обработки (фактические затраты С времени) для некоторой операции I/O может отличаться от прогнозного времени обработки (прогнозных затрат С* времени) для этой операции I/O. Это может произойти, когда модель 470 накопителя завышает или занижает затраты С* времени для данной операции I/O.
В некоторых вариантах осуществления данной технологии предполагается, что для контроля фактического времени обработки (фактических затрат С времени) для обработки для (а) по меньшей мере одной операции I/O, сформированной первым источником 404 I/O, и (б) по меньшей мере одной операции I/O, сформированной вторым источником 406 I/O, планировщик 408 операций может быть способным принимать от накопителя 402 подтверждения обработки, указывающие фактическое время обработки для (а) по меньшей мере одной операции I/O, сформированной первым источником 404 I/O, и (б) по меньшей мере одной операции I/O, сформированной вторым источником 406 I/O.
Шаг 912: корректировка виртуального времени планировщика операций, если фактическое время обработки превысило прогнозное время обработки для любой из (а) по меньшей мере одной операции I/O, сформированной первым источником I/O, и (б) по меньшей мере одной операции I/O, сформированной вторым источником I/O.
Способ 900 продолжается на шаге 912, на котором планировщик 408 операций способен корректировать виртуальное время планировщика 408 операций, если фактическое время обработки (фактические затраты С времени) превышает прогнозное время обработки (прогнозные затраты С* времени) для любой из (а) по меньшей мере одной операции I/O, сформированной первым источником 404 I/O, и (б) по меньшей мере одной операции I/O, сформированной вторым источником 406 I/O.
Например, можно предположить, что для операции I/O (некоторой операции из по меньшей мере одной операции I/O, сформированной первым источником 404 I/O, и по меньшей мере одной операции I/O, сформированной вторым источником 406 I/O) фактическое время обработки превышает соответствующее прогнозное время обработки. Иными словами, Можно предположить, что фактические затраты С времени для этой операции I/O превышают прогнозные затраты С* времени, определенные для этой операции I/O моделью 470 накопителя в процессе планирования этой операции I/O.
Это означает, что накопитель 402 затратил больше времени на обработку этой операции I/O по сравнению с оценкой модели 470 накопителя. Иными словами, модель 470 накопителя выдала заниженную оценку времени обработки по сравнению со временем, фактически затраченным накопителем 402 на обработку этой операции I/O.
Предполагается, что виртуальное время, используемое для представления интервалов времени обработки (или их сумм), запланированных для накопителя 402, корректируется так, чтобы будущие интервалы времени обработки при обработке будущих операций I/O могли планироваться с учетом того, что предыдущий запланированный интервал времени обработки (для обработки определенной операции I/O) превысил спрогнозированный интервал.
Можно предположить, что планировщик 408 операций принимает другую операцию I/O после определения того, что фактическое время С обработки превышает прогнозное время С* обработки для определенной операции I/O.
Предполагается, что в некоторых вариантах осуществления данной технологии корректировка виртуального времени может включать в себя работу планировщика 408 операций, способного при определении прогнозного периода Р* обработки для другой операции I/O добавлять (а) интервал времени, равный разности между фактическим временем С обработки и прогнозным временем С* обработки для определенной операции I/O, к (б) прогнозному периоду Р* обработки для другой операции I/O. Таким образом, планировщик 408 операций может быть способным определять скорректированный прогнозный период обработки для другой операции I/O. Следовательно, скорректированный прогнозный период обработки для другой операции I/O может указывать скорректированный прогнозный предельный срок обработки для другой операции I/O.
В не имеющем ограничительного характера примере операции 820 I/O, представленном на фиг. 8, операция 820 I/O принимается планировщиком 408 операций после определения того, что виртуальное время должно быть скорректировано на значение 770, равное 15 мс.
При определении прогнозного периода Р2* обработки для операции 820 I/O планировщик 408 операций способен добавить значение 770, равное 15 мс, к прогнозному периоду Р2* обработки длительностью 100 мс для определения скорректированного прогнозного периода обработки длительностью 115 мс для операции 820 I/O.
Следует отметить, что в результате использования при планировании скорректированного прогнозного периода обработки вместо прогнозного периода Р2* обработки для операции 820 I/O получаются другие прогнозные предельные сроки обработки.
С одной стороны, в результате использования прогнозного периода Р2* обработки для операции 820 I/O получается прогнозный предельный срок обработки длительностью 100 мс с момента времени приема операции 820 I/O планировщиком 408 операций. С другой стороны, в результате использования скорректированного прогнозного периода обработки для операции 820 I/O получается скорректированный прогнозный предельный срок обработки длительностью 115 мс с момента времени приема операции 820 I/O планировщиком 408 операций.
Таким образом, увеличение прогнозного предельного срока обработки для операции 820 I/O в ответ на корректировку виртуального времени планировщиком 408 операций позволяет учесть занижение прогнозного времени обработки для предыдущей операции I/O, которое привело к занижению соответствующего прогнозного периода обработки для предыдущей операции I/O.
Следует отметить, что прогнозные предельные сроки обработки дополнительных операций I/O, принятые планировщиком 408 операций после определения того, что виртуальное время должно быть скорректировано не значение 770, равное 15 мс, могут быть скорректированы подобно тому, как был скорректирован прогнозный предельный срок обработки для операции 820 I/O. Следовательно, можно сказать, что планировщик 408 операций может быть способным путем корректировки виртуального времени корректировать прогнозные предельные сроки обработки всех операций I/O, принятых после корректировки виртуального времени.
Предполагается, что в других вариантах осуществления данной технологии планировщик 408 операций также может быть способным корректировать виртуальное время, если фактическое время обработки меньше прогнозного времени обработки данной операции I/O (в ответ на завышение времени обработки). В этом случае вместо добавления некоторого количества времени, равного разности между фактическим временем обработки и прогнозным временем обработки данной операции I/O, к прогнозным периодам обработки будущих операций I/O, планировщик 408 операций может быть способным вычитать это количество времени.
Специалисту в данной области могут быть очевидны возможные изменения и усовершенствования описанных выше вариантов осуществления настоящей технологии. Предшествующее описание приведено лишь в качестве примера, но не для ограничения объема изобретения. Объем охраны данной технологии определяется исключительно объемом приложенной формулы изобретения.