| US20060190482A1 | 2006-08-24 | |||
| US7032186B1 | 2006-04-18 | |||
| US6966033B1 | 2005-11-15 | |||
| US20050240795A1 | 2005-10-27 |
| Формула изобретения 1. Способ управления ресурсами в вычислительной системе, включающей один или более взаимодействующих исполнительных элементов, в которой используют инструкцию передачи управления, которая позволяет передать управление между исполнительными элементами таким образом, что последовательность одной или более выполняемых инструкций передачи управления образует распределенный стек вызовов, указанный способ, отличающийся тем, что один или более ресурс, связанный с исполнительным элементом, предоставляют, когда этот исполнительный элемент получает управление в указанном распределенном стеке вызовов или перед исполнением начальной инструкции передачи управления в указанном распределенном стеке вызовов, для доступа на одном исполнительном элементе к указанному ресурсу другого исполнительного элемента выполняют обратную инструкцию, и указанный ресурс исполнительного элемента освобождают или модифицируют управляющую информацию, в случае возврата управления из этого исполнительного элемента в указанной инструкции передачи управления, или в случае завершения работы указанного стека вызовов на этом исполнительном элементе, или в случае выполнения инструкции программы, которая явно освобождает этот ресурс. 2. Способ по п. 1, отличающийся тем, что указанные исполнительные элементы являются в произвольной комбинации ядрами в многоядерной системе, или процессорами в многопроцессорной системе, или процессорами компьютеров, соединенными через сеть, или реализованными программно виртуальными системами, или экземплярами процессов реальной или виртуальной системы, выполняющими программу в одной или более исполнительных системах. 3. Способ по п. 1, отличающийся тем, что указанная инструкция передачи управления является инструкцией локального или удаленного вызова процедуры. 4. Способ по п. 1, отличающийся тем, что указанная обратная инструкция является инструкцией передачи управления. 5. Способ по п. 1, отличающийся тем, что указанная обратная инструкция является инструкцией локального или удаленного вызова процедуры. 6. Способ по п. 1, отличающийся тем, что указанная обратная инструкция является инструкцией доступа к памяти. 7. Способ по п. 1, отличающийся тем, что ресурсы, предоставленные указанному распределенному стеку вызовов, рассматривают как единую совокупность, являющуюся объединением этих ресурсов, при выполнении операции доступа к элементам указанной совокупности исполнительный элемент контролирует выход за границы своего подмножества ресурсов, если указанный исполнительный элемент обнаруживает выход за границы своего подмножества ресурсов, он обращается к предыдущему в указанном стеке вызовов исполнительному элементу, предыдущий в стеке вызовов исполнительный элемент выполняет операцию доступа к ресурсу, если этот ресурс связан с этим исполнительным элементом, или обращается к своему предыдущему исполнительному элементу в указанном стеке вызовов. 8. Способ по п. 7, отличающийся тем, что указанный предоставляемый ресурс является элементом памяти, связанным с указанным исполнительным элементом. 9. Способ по п. 8, отличающийся тем, что совокупность памяти, которая предоставлена для указанного распределенного стека вызовов, рассматривают как непрерывную память или как массив с элементами постоянной или переменной длины, общий размер или максимальный индекс массива текущей указанной совокупности памяти передают при выполнении указанной инструкции передачи управления, для адресации в указанной совокупности памяти используют относительный адрес или индекс, которые рассчитывают от начала указанной совокупности памяти. 10. Способ по п. 7, отличающийся тем, что указанная совокупность ресурсов, является памятью с ассоциативной адресацией или совокупностью пар ключ (уникальный или не уникальный) - значение. 11. Способ по п. 7, отличающийся тем, что указанным предоставляемым ресурсом является память, в которой расположена выполняемая программа или фрагмент программы. 12. Способ по п. 1, отличающийся тем, что информацию, необходимую для использования указанных ресурсов, передают в параметрах вызова, или возвращаемом значении указанной инструкции передачи управления, или в возвращаемом значении указанной обратной инструкции, или эту информацию передают как составную часть самой инструкции передачи управления, или эту информацию определяют в протоколе взаимодействия исполнительных элементов. 13. Способ по п. 1, отличающийся тем, что указанный стек вызовов завершают на определенном исполнительном элементе при возврате управления из этого исполнительного элемента в указанной инструкции передачи управления в указанном стеке вызовов, или указанный стек вызовов завершают на определенном исполнительном элементе при получении сообщения о необходимости завершения указанного стека вызовов, или указанный стек вызовов завершают на определенном исполнительном элементе при выполнении инструкции программы. 14. Способ по п. 1, отличающийся тем, что возврат управления из указанной инструкции передачи управления выполняют как вызов процедуры, информацию о которой передают при выполнении инструкции передачи управления, из которой выполняют возврат. 15. Способ по п. 1, отличающийся тем, что при выполнении указанной инструкции передачи управления между указанными исполнительными элементами передают идентификационную информацию пользователя или компьютера, который инициировал исполнение указанного распределенного стека вызовов. 16. Способ по п. 1, отличающийся тем, что каждому выполняемому указанному распределенному стеку вызовов присваивают идентификатор, который является уникальным в указанной вычислительной системе на время выполнения этого стека вызовов, включая отсутствие идентификатора как одно из возможных значений. 17. Способ по п. 16, отличающийся тем, что в качестве указанного идентификатора распределенного стека используют цифровую подпись в полном или усеченном виде. 18. Способ по п. 1, отличающийся тем, что ресурсы не предоставляют на любом подмножестве исполнительных элементов в указанном распределенном стеке вызовов, если ресурсы указанного подмножества не являются необходимыми. 19. Способ по п. 18, отличающийся тем, что если исполнительный элемент не предоставил ресурсы, то этот исполнительный элемент исключают из указанного стека вызовов, передав следующему в стеке вызовов исполнительному элементу информацию о предыдущем в стеке вызовов исполнительном элементе и передав предыдущему в стеке вызовов исполнительному элементу информацию о следующем в стеке вызовов исполнительном элементе, если предыдущий исполнительный элемент есть в указанном стеке вызовов. 20. Способ по п. 1, отличающийся тем, что предоставляемые ресурсы частично или полностью совместно используют в более чем в одном распределенном стеке вызовов. 21. Способ по п. 1, отличающийся тем, что указанный распределенный стек вызов ассоциируют с соединениями между исполнительными элементами в этом стеке вызовов. 22. Способ по п. 1, отличающийся тем, что указанную инструкцию передачи управления выполняют синхронно. 23. Способ по п. 1, отличающийся тем, что указанную инструкцию передачи управления выполняют асинхронно. 24. Способ по п. 1, отличающийся тем, что указанным предоставляемым ресурсом является объект, функцию которого вызывают в указанной обратной инструкции. 25. Способ по п. 1, отличающийся тем, что в качестве информации, необходимой для использования указанного ресурса, используют распределенный указатель на ресурсы. 26. Способ по п. 25, отличающийся тем, что указанный указатель на ресурсы включает смещение или индекс или идентификатор ресурса в совокупности ресурсов, предоставленных в указанном распределенном стеке вызовов. 27. Способ по п. 25, отличающийся тем, что указанный указатель на ресурсы включает комбинацию адреса исполнительного элемента и локального идентификатора ресурса. 28. Способ по п. 1, отличающийся тем, что указанные предоставляемые ресурсы рассматривают как переменные состояния указанного распределенного стека вызовов. |
Область техники, к которой относится изобретение
Изобретение определяет способы управления ресурсами, выделяемыми для исполнения программ в локальных, многопроцессорных и распределенных вычислительных системах. В качестве ресурсов может быть оперативная память, файлы, устройства ввода/вывода, прикладные объекты, объекты пользовательского интерфейса, системные объекты, объекты операционной системы, внешние устройства. Уровень техники
Рассматриваемое в заявляемом изобретении управление ресурсами включает выделение ресурсов, освобождение ресурсов и доступ к ресурсам. Использованный в описании термин «ресурсы» подразумевает любые ресурсы, в том числе оперативную память, файлы, устройства ввода/вывода, прикладные объекты, объекты пользовательского интерфейса, системные объекты, объекты операционной системы, внешние устройства и прочее. В контексте настоящего описания термины ресурс и объект рассматриваются как синонимы.
Способы выделения ресурсов обычно являются очевидными и зависят от типа ресурса, функционального назначения ресурса, типа исполнительной системы, языка программирования, архитектуры конкретной системы или других факторов. Способы автоматического освобождения ресурсов после того, как они становятся не нужными приложению, являются более сложными.
В большинстве случаев выделение и освобождение ресурсов тесно связано с операциями выделения/освобождения памяти или модификацией управляющей информации в памяти. В настоящее время для управления ресурсами программы, которая выполняется локально (не в распределенной среде), широко используется стековая память. Использование стека является простым и чрезвычайно эффективным способом выделения и освобождения ресурсов. Во-первых, память выделяется и освобождается последовательно в заранее выделенном блоке достаточно большого размера. Во-вторых, освобождение памяти происходит автоматически и не требует какого-либо кодирования на уровне исходного текста программы. При этом стековая память автоматически освобождается как при нормальном выполнении программы, так и при возникновении исключительных ситуаций (то есть, всегда).
В типичном случае стековая память используется для выделения объектов, которые доступны локально для одного потока управления программы. Хотя алгоритм управления памятью в стеке накладывает определенное ограничение на ее использование, любая программа может быть реализована с использованием только стековой памяти.
Другим типом ресурсов являются ресурсы, которые выделяются в программе явным образом. Такие ресурсы могут использоваться одновременно в нескольких местах программы, или совместно несколькими потоками управления, или несколькими приложениями. Для автоматического управления динамическими ресурсами не из стека используют счетчики ссылок на ресурс, или связанные списки ссылок на ресурс, или сборщики мусора. Ресурс автоматически освобождается, когда на него нет актуальных ссылок в программе.
Рассматривая управление ресурсами в распределенной среде, ,в настоящее время в основном используются счетчики ссылок. Реализация счетчика ссылок при локальном исполнении приложения достаточно проста и надежна. В то же время, перенос счетчика ссылок в распределенную среду является сложной задачей, не имеющей точного решения. Во-первых, это связано с тем, что не всегда имеется возможность полностью согласовать алгоритмы управления на разных узлах системы. Во-вторых, в распределенной системе любой узел или приложение может в любой момент аварийно отключиться без посылки сообщения. Для решения этой проблемы узлы, которые выделяют ресурсы, должны удерживать прямые соединения с каждым узлом, который использует ресурс. Эти соединения должны постоянно тестироваться. Однако, при сложной конфигурации сети или многопроцессорной системы установление прямых соединений не всегда возможно. Цепочки независимых соединений не всегда позволяют вычислить аварийное отключение пользователя ресурсов. Это приводит к ошибочному зависанию ресурсов. В-третьих, управление ресурсами требуется отдельно для каждого ресурса и для каждой ссылки на ресурс. Такое управление требует передачу сообщений между узлами системы для каждого ресурса. Это создает существенный управляющий трафик в распределенной среде и замедляет выполнение программы.
Возможным вариантом решения проблемы управления ресурсами в распределенной системе является перенос логики управления памятью на основе стека в распределенную среду. В некоторой степени это сделано в распределенной памяти с базовой адресацией, предложенной в заявке на патент WO2012/047134, Система и способ распределенных вычислений, Богданов А. Я., 12.04.2012, п. 1 - 3 формулы, стр. 8, фиг. 4. Данный способ основан на удаленном вызове процедуры и рассматривает адресацию в распределенном стеке вызовов. Каждый узел при получении управления в распределенном стеке вызовов выделяет блоки памяти и последовательно добавляет их к совокупности памяти, выделенной в этом распределенном стеке вызовов. Общий размер выделенной в стеке вызовов памяти передается в очередной инструкции удаленного вызова процедуры. Вся выделенная в стеке вызовов память рассматривается как непрерывная. Адрес памяти рассчитывается как смещение от начала первого выделенного блока. Если при обращении к указанной распределенной памяти узел определяет, что она находится не в его памяти, он обращается к предыдущему узлу по цепочке вызовов в распределенном стеке.
Предложенный в указанной заявке способ адресации имеет недостатки. Во- первых, в нем в качестве ресурса используются только блоки оперативной памяти. Во- вторых, адресация с использованием абсолютного смещения ограничивает использование этого способа в языках программирования, не поддерживающих прямую работу с адресами. В-третьих, указанный способ имеет ограниченные возможности по освобождении ресурсов (ресурсы могут быть освобождены только при возврате управления в распределенном стеке). В-четвертых, он не определяет механизмов взаимодействия между узлами, если в системе одновременно выполняется множество распределенных потоков управления. В-пятых, он не предусматривает одновременное использование ресурсов несколькими распределенными потоками. В-шестых, он не предусматривает использование статических ресурсов (в частности, статический памяти). Раскрытие изобретения
Заявляемое изобретение рассматривает управление ресурсами в локальной и/или распределенной системе. Рассматриваемые системы включают один или более исполнительный элемент, который имеет память для хранения программ и данных. Исполнительный элемент выполняет инструкции программы, которые расположены в его памяти. Каждый исполнительный элемент может иметь свою память, или любое подмножество исполнительных элементов может иметь общую память. Наличие только одного исполнительного элемента рассматривается как частный вариант системы, в которой отдельные элементы включаются не одновременно. При этом программа, созданная на основе изобретения, сохраняет работоспособность при работе одного или множества исполнительных элементов.
Исполнительными элементами могут быть в любой комбинации ядра в многоядерной системе или процессоры в многопроцессорной системе или процессоры компьютеров, соединенные через сеть, или реализованные программно виртуальные системы или экземпляры процессов реальной или виртуальной системы, выполняющими приложение в своем адресном пространстве в одной или разных исполнительных системах. Рассматриваемый в изобретении способ работает одинаково как при локальном взаимодействии программ, которые выполняются на одном компьютере в одной исполнительной системе, так и при взаимодействии в многопроцессорной, сетевой или другой распределенной среде в произвольной комбинации.
Исполнительные элементы могут взаимодействовать между собой. Соединения исполнительных элементов каждый с каждым не является обязательным. Изобретение поддерживает цепочки соединений через промежуточные узлы любой длины.
При использовании в локальной системе изобретение предназначено для локального взаимодействия экземпляров программ, которые выполняются в своих изолированных адресных пространствах, или имеют независимое управление ресурсами. Другим возможным применением изобретения является управление ресурсами программы, которая выполняется на нескольких исполнительных элементах.
При выполнении программы могут выделяться новые ресурсы или могут предоставляться в использование ранее выделенные ресурсы. В обоих случаях ресурсы могут рассматриваться как предоставляемые. Предоставленные любым способом ресурсы могут использоваться только определенным распределенным стеком вызовов, или ресурсы могут использоваться более чем одним распределенным стеком. Ресурсы могут быть динамическими или статическими.
Взаимодействие между исполнительными элементами основано на инструкции передачи управления, которая позволяет передать поток управления от одного исполнительного элемента другому. В типичной реализации это удаленный или локальный вызов процедуры. В зависимости от логики программы, рассматриваемая в изобретении инструкция передачи управления может передавать управление как от одного исполнительного элемента к другому, так и в границах одного исполнительного элемента. Механизм реализации удаленного или локального вызова процедуры не имеет для изобретения существенного значения. Это могут быть средства межпроцессорного взаимодействия с использованием параллельной шины, или это может быть взаимодействие на основе общей памяти, или это может быть обмен сообщениями на базе последовательной или параллельной шины или сетевой среды. Способы поиска и идентификации удаленных или локальных процедур также является не существенным для изобретения.
Заявляемое изобретение основано на управлении ресурсами с использованием стека, которое перенесено в распределенную среду. При классической организации вычислительного процесса в стеке располагают короткоживущие объекты. Объекты создаются в кадре стека процедуры и уничтожаются при возврате управления из процедуры. В настоящем изобретении для управления временем жизни объекта предлагается использовать обратную инструкцию. Основной особенностью обратной инструкции является то, что она не возвращает управление из инструкции передачи управления и не раскручивает распределенный стек. Обратная инструкция позволяет сохранять объекты стека в течение любого времени и автоматически удалять их при возврате управления из исходной инструкции передачи управления. Типичными примерами обратной инструкции могут быть удаленный или локальный вызов процедуры, которая обращается к ресурсу, и операции удаленного доступа к памяти (чтение/запись данных или атрибутов памяти). Если обратная инструкция является инструкцией передачи управления, она может продолжать или не продолжать распределенный стек вызовов. Параметры такой обратной инструкции могут содержать ссылки на ресурсы, выделенные на любом узле для этого распределенного стека вызовов. Для доступа к этим ресурсам может быть использована последующая обратная инструкция. Вызов процедуры является частным случаем инструкции передачи управления.
Предлагаемый способ управления ресурсами является:
• Простым - логика управления ресурсами совмещена с логикой потоков управления программы. При разработке программы не требуется явных инструкций освобождения ресурсов. Выделение и освобождение ресурсов выполняется локально и управление ресурсами совмещено с управлением распределенными потоками. Кроме этого, распределенный стек вызовов позволяет согласовать глобальное состояние системы при взаимодействии независимо разработанных программ.
• Надежным - освобождение неиспользуемых ресурсов является гарантированным.
• Децентрализованным - каждый распределенный стек вызовов имеет свое пространство ресурсов, и каждый узел в распределенном стеке вызовов управляет своими ресурсами. Заявленный способ может быть использован как в пиринговых системах, так и в клиент - серверных системах.
• Эффективным - одна команда возврата управления может освобождать сразу множество неиспользуемых ресурсов. Обмен сообщениями при создании и уничтожении ссылок на ресурс не требуется. Ресурсы предоставляются и освобождаются локально.
• Универсальным - предлагаемый распределенный стек является таким же универсальным, как и локальный стек.
Еще одним техническим результатом рассматриваемого способа управления ресурсами является возможность удаленного доступа к элементам памяти в случае, если исполнительная система или язык программирования не предоставляют прямого использования относительный адресации. В частности, это могут быть интерпретируемые языки программирования, например, JavaScript. Заявляемое изобретение позволяет в качестве удаленной ссылки использовать числовой индекс элемента в памяти или ключевое значение или ассоциативный адрес (например, имя переменной или функции в коде программы).
Еще одним техническим результатом является возможность ассоциировать распределенный стек вызовов с сетевыми соединениям. Это позволяет напрямую использовать сетевые сервисы ненадежной доставки данных без установления соединения. Другим преимуществом является возможность организации цепочек сетевых соединений. В частности, это позволяет гарантированно освободить ресурсы при тихом завершении любого подмножества соединений в цепочке.
Кроме этого, заявляемое изобретение устраняет все приведенные выше недостатки прототипа без потери имеющегося технического эффекта.
На фиг. 1 приведена диаграмма, иллюстрирующая заявляемое изобретение. Здесь взаимодействуют два исполнительных элемента с условными названиями Узел А и Узел Б. Инструкция с условным названием ПРИВЯЗАТЬ определяет момент, когда распределенный стек вызовов начинает выполнение на Узле А. Начиная с этого момента в интервале 10 Узел А может выделять ресурсы, которые будут доступны в этом распределенном стеке. Для примера, в этом интервале создан ОБЪЕКТ1, который является объектом в памяти с удаленно вызываемой функцией. Инструкция 11 (с условным названием SCALL) передает управление на Узел Б. Инструкция SCALL может включать информацию о ресурсах, выделенных в распределенном стеке. Такая информация может быть присоединена к сообщению удаленного вызова и/или параметры вызова процедуры могут включать явные ссылки на предоставленные ресурсы (на фиг. 1 указатель на ОБЪЕКП). На Узле Б распределенный стек начинает выполнение при получении вызова 11. В интервале 12 Узел Б может предоставлять свои ресурсы для распределенного стека. Эти ресурсы будут добавлены к ресурсам, выделенным в интервале 10. Инструкция 13 (OBbEKTl.SCALL) является обратной инструкцией, которая вызывает функцию объекта ОБЪЕКТ1. В интервале 14 доступны ресурсы, выделенные в интервалах 10 и 12. В интервале 14 Узел А получил управление по инструкции обратного вызова, а не как возврат управления из инструкции 11. В таком случае на узле А возможно два способа выделения ресурсов, которые отличаются моментом их освобождения. Блок 14.1 иллюстрирует ресурсы, указатели на которые вычисляются независимо от других ресурсов (реализация возможных типов указателей рассмотрена ниже). Такие ресурсы могут быть присоединены к ресурсам, которые выделены в интервале 10. Блок 14.2 иллюстрирует ресурсы, которые должны быть освобождены при возврате управления из инструкции 13. Инструкции 15 (ВОЗВРАТ) возвращают управление из инструкции 13. Если в интервале 14.2 были выделены ресурсы, они освобождаются. В интервале 16 доступными являются ресурсы, выделенные в интервалах 10, 12 и 14.1. Ссылки на ресурсы 14.1 могут быть переданы как возвращаемое значение в инструкции 15. Инструкция 17 (ВОЗВРАТ) возвращает управление из инструкции 11. Если в интервалах 12 и 16 были выделены ресурсы, они освобождаются.
На фиг. 1 на Узле А показаны две инструкции 11 и 19, которые выполняют начальный вызов в распределенном стеке вызовов. В интервалах 10 и 18 распределенной стек не имеет выполняемой начальной инструкции распределенной передачи управления. В интервале 18 перед начальной инструкцией в распределенном стеке вызов Узел А может выделять новые ресурсы, которые будут добавлены к ресурсам 10 и 14.1. Инструкция 19 (SCALL) выполняет еще один распределенный вызов. В интервале 110 доступны ресурсы, выделенные в интервалах 10, 14.1 и 18. Узел А является инициатором создания распределенного стека. Для завершения выполнения распределенного стека на этом узле использована инструкция с условным названием ОТВЯЗАТЬ. При этом освобождаются ресурсы, выделенные в интервалах 10, 14.1, 18 и 111 (в том числе ОБЪЕКТ1). Другим вариантом завершения работы распределенного стека вызовов на узле является возврат управления из первой инструкции передачи управления, по которой этот узел получил управление. Этот вариант показан на фиг. 1, если инструкцию ПРИВЯЗАТЬ заменить на SCALL, а инструкцию ОТВЯЗАТЬ на ВОЗВРАТ (аналогичным образом освобождаются ресурсы 12 и 16 при выполнении инструкции 17).
На фиг. 1 приведен один распределенный стек вызовов с максимальной глубиной вызовов в стеке 2. Во взаимодействии участвуют только два исполнительных элемента. Данные ограничения представлены исключительно в целях простоты изложения. В общем случае может взаимодействовать любое количество исполнительных элементов, в системе может одновременно выполняться один или более распределенных стеков вызовов, и глубина каждого распределенного стека вызовов может быть любой (глубина распределенного стека вызовов может быть ограничена разумной величиной в целях исключить зацикливание и неограниченно длинные цепочки вызовов). В частности, если фиг. 1 на Узле А вместо инструкций ПРИВЯЗАТЬ/ОТВЯЗАТЬ использовать инструкции SCALL/B03BPAT, то приведенную диаграмму можно рассматривать как фрагмент распределенного стека вызовов, который имеет любую глубину вызовов на момент получения управления Узлом А. При этом, во всех рассмотренных интервалах будут доступны ресурсы, предоставленные этому распределенному стеку вызовов на момент получения управления Узлом А.
На фиг. 1 можно выделить следующие моменты начала предоставления ресурсов на исполнительном элементе:
· Момент перед выполнением начальной инструкции распределенной передачи управления в стеке вызовов (начало интервалов 10 и 18 при использовании инструкций ПРИВЯЗАТЬ/ОТВЯЗАТЬ).
• Момент получения управления по инструкции распределенной передачи управления (начало интервалов 12, 14, 110).
· Момент возврата управления из инструкции передачи управления (начало интервалов 16, 18, 111).
Во всех случаях ресурсы на узле могут быть предоставлены в интервалах, в которых этот узел получает управление в заданном распределенном стеке вызовов. Благодаря этому предоставление ресурсов выполняется локально и не требует специального управляющего трафика между узлами системы.
На фиг. 1 можно выделить следующие моменты освобождения предоставленных ресурсов:
• Момент возврата управления из инструкции распределенной передачи управления (конец интервалов 14.2, 16, 110).
· Момент завершения работы распределенного стека вызовов на узле, к которому эти ресурсы относятся (конец интервала 111 при использовании инструкций ПРИВЯЗАТЬ/ОТВЯЗАТЬ).
• Если узел получил управление не через обратную инструкцию, то момент возврата управления из инструкции распределенной передачи управления одновременно является моментом завершения работы распределенного стека вызовов на узле (конец интервалов 16, 110, а так же конец интервала 111 при использовании инструкций SCALL B03BPAT).
Таким образом, предоставленный ресурс исполнительного элемента освобождают или модифицирует управляющую информацию при возврате управления из этого исполнительного элемента в инструкции распределенной передачи управления, или предоставленный ресурс исполнительного элемента освобождают или модифицирует управляющую информацию при завершении работы распределенного стека вызовов на этом исполнительном элементе. При этом, освобождение ресурса происходит локально и не требует передачи специальной информации между узлами системы. Одновременно освобождаются все ресурсы, которые были предоставлены для распределенного стека вызовов на исполнительном элементе.
Кроме этого, предоставленный ресурс исполнительного элемента освобождают или модифицирует управляющую информацию при выполнении инструкции программы, которая явно освобождает этот ресурс (на фиг. 1 не показано). Например, ресурс может быть явно освобожден, если это ресурс больше не нужен в программе.
Предоставляемый ресурс может принадлежать определенному стеку вызовов или ресурс может совместно использоваться разными стеками вызовов. Если каждый ресурс в системе принадлежит только одному распределенному стеку вызовов, может быть реализовано безблокировочное программирование. Для доступа к общему ресурсу может создаваться копия этого ресурса (или шлюз, или мост). Взаимодействие между копией общего ресурса и самим ресурсом может основываться на локальной асинхронной передаче сообщений.
В общем случае, освобождение ресурсов может рассматриваться как модификация управляющей информации при освобождении любого типа предоставляемых ресурсов. Например, освобождение памяти в локальном стеке выполняется через изменение значения в регистре стека, а освобождение памяти из кучи выполняется через модификацию управляющих таблиц. Для освобождения ресурсов, которые используются несколькими распределенными стеками, модифицируют управляющую информацию в счетчике ссылок или в связанном списке ссылок. Реальное освобождение ресурса происходит после того, как ресурс освобождается всеми распределенными стеками на исполнительном элементе. Если используются локальные сборщики мусора, реальное освобождение ресурса может выполняться с задержкой.
Во всех случаях, ресурсы исполнительного элемента предоставляют программе, если они являются необходимыми. Произвольное подмножество исполнительных элементов в распределенном стеке вызовов может не предоставлять ресурсы, если они не нужны. Если на исполнительном элементе не выделено ресурсов и на нем не требуется обрабатывать возврат управления в распределенном стеке вызовов, исполнительный элемент может исключить себя из распределенного стека. В этом случае он должен передать следующему исполнительному элементу информацию об исполнительном элементе, от которого он получил управление. Кроме этого, он должен передать предыдущему исполнительному элементу информацию о следующем исполнительном элементе. Если предыдущего исполнительного элемента нет (текущий исполнительный элемент является начальным), то может быть передано сообщения, означающее что возврат управления не требуется.
Особенностью рассматриваемого способа управления ресурсами является гарантированное освобождение ресурсов при завершении работы распределенного стека вызовов. Распределенный стек может быть завершен следующими способами: · Завершение назад. Данный способ выполняется при нормальном возвращении управления из инструкции передачи управления или при возврате управления через исключение. При завершении всего стека вызовов распределенный стек последовательно раскручивается назад с освобождением ресурсов исполнительных элементов в цепочке вызовов.
· Завершение вперед. Этот способ используется, если инициатором завершения является исполнительный элемент, который в данный момент не находится на вершине распределенного стека вызовов. В этом случае раскрутка стека не происходит, а посылается специальное сообщение завершения стека. Это сообщение последовательно передается по цепочке вызовов от инициатора завершения до исполнительного элемента в вершине распределенного стека вызовов (если это возможно). Каждый исполнительный элемент при получении сообщения о завершении распределенного стека должен освободить ресурсы, которые предоставлены этому стеку.
Выполнение распределенного стека может быть завершено любым узлом в цепочке вызовов. Если инициатор завершения находится не на концах цепочки распределенного стека вызовов, одновременно выполняется завершение вперед и назад. Завершение назад может выполняться через возбуждение исключения. Рассматриваемые способы завершения позволяют гарантированно освободить ресурсы распределенного стека при одновременном отключении произвольного подмножества узлов в цепочке вызовов.
Еще одним техническим результатом использования заявляемого изобретения является согласованное глобальное состояние стека при взаимодействии независимо разработанных программ. При взаимодействии обычных программ с использованием локального или удаленного вызова процедуры (RPC / LPC) каждая программа фактически является самостоятельным конечным автоматом со своим набор переменных состояния и своей логикой переходов. Вызовы RPC / LPC реализуются как слабо - связанное взаимодействие, основанное на обмене сообщениями. В результате глобальное состояние системы и глобальная логика работы являются трудно предсказуемыми. Это повышает сложность разработки и уменьшает надежность. В заявляемом изобретении ресурсы, предоставленные в стеке, можно рассматривать как переменные состояния. В типичном случае, ссылки на эти ресурсы передаются между исполнительными элементами как параметры вызовов и возвращаемые значения процедур RPC / LPC. Таким образом, ресурсы, которые определяют состояние распределенного стека вызовов, известны и являются частью протокола взаимодействия. Ресурсы распределенного стека могут быть логически изолированы от переменных состояния отдельных программ. Переменные состояния распределенного стека могут определять как глобальное состояние всего стека, так и состояние отдельных соединений или отдельного подмножества цепочек соединений. Изменение состояния выполняется через обратную инструкцию и является составной частью протокола взаимодействия. В частности, это позволяет легко разрабатывать распределенные приложения, логика которых основана на состоянии связей между множеством узлов. Еще одним вариантом является использование изобретения при взаимодействии программ с плохо управляемым состоянием, например, Web - страниц.
Краткое описание чертежей
Фиг. 1. Диаграмма, которая иллюстрирует изобретение. Фиг. 2. Схема реализации системы в соответствии с изобретением.
Осуществление изобретения
На фиг. 2 приведена схема возможной реализации заявляемого изобретения.
Рассматриваемая реализация описана на примере программы, разработанной на стандартном языке С++. Этот язык позволяет реализовать любое управление ресурсами и любую организацию вычислительным процессом. Однако заявляемое изобретения является независимым от платформы и используемого языка программирования. Оно может быть реализовано на множестве платформ и интегрировано с различными компилируемыми и интерпретируемыми языками программирования в произвольном сочетании. Например, в качестве возможной реализации на интерпретируемом языке программирования может быть предложен JavaScript.
На фиг. 2 метки 21, 22 указывают на прикладные программы, разработанные на
С++. Это могут быть разные программы или копия одной программы. Программы разработаны с использованием библиотеки шаблонов С++ um.h - 23, 24. Эта библиотека создана на основе заявляемого изобретения. Она включает набор шаблонов, которые являются расширением языка и позволяют скрыть на уровне исходного текста программы детали распределенного взаимодействия. Шаблоны из библиотеки um.h взаимодействует с системной службой 25, 26. Системная служба реализует логику настоящего изобретения. Программы выполняются на исполнительных элементах - компьютерах с условными названиями УЗЕЛ А, УЗЕЛ Б и УЗЛЫ N-N. Компьютеры связаны через сеть 27. Рассматриваемая реализация позволяет взаимодействовать программам, выполняемым на одном или разных компьютерах в произвольной комбинации.
Системная служба 25, 26 является расширением операционной системы. Она реализует собственный протокол удаленного и локального вызова процедуры (RPC и LPC) в соответствии с настоящим изобретением. Конкретная реализация RPC и LPC является не существенной для изобретения. RPC и LPC являются хорошо известными технологиями взаимодействия программ, которые имеют множество частных и стандартизованных реализаций.
Организация вычислительного процесса в рассматриваемой системе включает два типа потоков управления программы. Это локальные потоки управления и распределенные потоки управления. Распределенный поток управления определяется цепочкой вызовов RPC / LPC и выполняется в контексте распределенного стека вызовов. Когда распределенный поток управления выполняется на определенном исполнительном элементе, его выполняет некоторый локальный поток управления. Возможны следующие варианты реализации связи локальных и распределенных потоков управления:
• Распределенный поток ассоциируют с определенным локальным потоком. При такой связи распределенный поток является цепочкой определенных локальных потоков. Вызовы RPC / LPC выполняются синхронно. Локальный поток освобождается, когда он возвращает управление из распределенного вызова. Данный способ является простым и хорошо подходит для пиринговых и клиентских систем. Недостатком этого способа является плохое масштабирование в серверных системах, которые одновременно обрабатывают большое количество запросов. • Распределенный поток выполняется на определенном узле в контексте некоторого локального потока управления. Если распределенный поток управления приостанавливает свое выполнение или выполняет вызов RPC / LPC, освобожденный локальный поток управления может выполнять другой распределенный поток управления. Такой способ поддерживает асинхронные вызовы и хорошо масштабируется в серверных системах.
Реализация указанных способов обработки запросов является хорошо известной для большинства исполнительных систем.
В рассматриваемой реализации для управления распределенным стеком вызовов на локальном компьютере в памяти компьютера создается специальная управляющая структура. Эта структура включает уникальный идентификатор распределенного стека вызовов, адрес предыдущего и следующего узла в распределенном стеке вызовов, ссылки на ресурсы, которые выделены на узле для этого стека, информацию об используемых сетевых соединениях и другую информацию. Данная управляющая структура в явном или неявном виде участвует в операциях с распределенным стеком вызовов.
Следующий пример минимальной программы иллюстрирует использование заявляемого изобретения. Данный пример никак не ограничивает изобретение и приведен исключительно для иллюстрации рассматриваемой реализации. Возможно множество других реализаций кода в соответствии с заявляемым изобретением. В рассматриваемом примере взаимодействуют два узла с условными названиями Узел А и Узел Б. Сетевой адрес Узла А является несущественным для данного примера. Узел Б имеет условный сетевой адрес 10.0.1.28. На Узле А выполняется программа со следующим исходным текстом:
1 #include "um.h"
2 class Objectl {
3 void functHello (const char* s_out) { 4 printf (s_out) ;
5 }
6 };
7 void runHello (uptr<Objectl>) {}
8 void main ( ) {
9 UM_ADD_FUN (Objectl : : functHello) ;
10 UM_ADD_FUN ( runHe1lo) ;
11 UMDS* ds = InitDStack () ;
12 BindDStack(ds) ;
13 uptr<Objectl> ptr = amake<Objectl> ( ) ;
14 scall ("10.0.1.28", runHello, ptr);
15 UnbindDStack(ds) ;
16 }
На Узле Б выполняется программа со следующим исходным текстом:
17 #include "um.h"
18 class Objectl {
19 void functHello (const char*) {}
20 };
21 void runHello (uptr<Objectl> ptr) {
22 ptr. scall (functHello, "Hello, World!");
23 }
24 void main() {
25 UM_ADD_FUN (Objectl : : functHello) ;
26 UM_ADD_FUN (runHe11о) ;
27 RunDStackO;
28 }
Строки 1, 17 включают описанную выше библиотеку шаблонов um.h. Строки 2 - 6 определяют объект, который будет создан как ресурс для обратного вызова. Строка 7 определяет функцию - заглушку для удаленного вызова, которая используется как прототип при формировании удаленного вызова. В строках 9, 10 и 25, 26 регистрируются процедуры для удаленных вызовов. В строке 11 функция InitDStack ( ) инициализирует распределенный стек. При этом создается структура UMDS, которая будет управлять выполнением распределенного стека на Узле А. В строке 12 функция BindDStack () связывает инициализированный распределенный стек с текущим локальным потоком управления программы. Для связи локального и распределенного потока функция BindDStack () записывает указатель на структуру UMDS в специальную переменную, которая расположена в определенном месте в локальной памяти потока. В зависимости от используемой архитектуры системы и среды выполнения могут быть использованы другие способы связи локального и распределенного потока управления. В строке 13 в динамической памяти создается объект типа Object1, который является предоставленным ресурсом. Индекс этого объекта в памяти, выделенной для текущего распределенного стека, записывается в специальный распределенный указатель uptro. Данный тип указателей реализован как шаблон в библиотеке um.h. Типы указателей, используемые для адресации памяти распределенного стека вызовов, описаны ниже. Ссылка на предоставленный объект связывается с управляющей структурой UMDS для последующего автоматического освобождения ресурсов. Строка 14 содержит удаленный вызов функции runHello ( ) на Узле Б. Этот вызов является начальным в стеке ds. В этом вызове передается распределенный указатель на объект Objectl.
На Узле Б в строке 27 функция RunDStack () передает локальный поток управления функции main() для обработки входящих вызовов RPC / LPC. При получении входящего вызова RPC создается структура управления распределенным стеком на Узле Б. Эта структура инициализируется значениями из входящего запроса RPC / LPC. В данном примере в контексте принятого распределенного стека выполняется функция runHello ( ) . Строка 22 содержит обратную инструкцию, которая удаленно вызывает метод functHello ( ) объекта Objectl на Узле А.
Поток функции main ( ) на Узле А находится в состоянии ожидания и выполняет входящий вызов RPC метода functHello (). После этого управление возвращается на Узел Б. Затем функция runHello () завершает выполнение и управление возвращается на Узел А. На Узле А в строке 15 функция UnbindDStack ( ) завершает выполнение распределенного стека вызовов. При этом созданный объект Objectl автоматически удаляется.
Рассматриваемый пример программы содержит синхронные удаленные вызовы процедур, которые являются более простыми для иллюстрации. В общем случае удаленные вызовы процедур могут быть синхронными или асинхронными. Возможный вариант реализации асинхронного вызова может включать специальную функцию, ссылка на которую передается в исходном удаленном вызове процедуры. Обратный вызов этой функции означает возврат управления в соответствующей инструкции удаленного вызова. Эта функция может иметь параметр, совпадающий с возвращаемым значением вызываемой процедуры. В качестве другого параметра может выступать объект, сигнализирующий об исключительной ситуации. Кроме этого, существуют другие известные варианты реализации асинхронных вызов процедур. Асинхронный вызов может продолжать или не продолжать распределенный стек вызовов.
Для того чтобы один исполнительный элемент мог обратиться к ресурсам другого исполнительного элемента, информация о ресурсах может передаваться:
• в параметрах вызова локальной или удаленной процедуры и/или
• как составная часть самой инструкции передачи управления и/или
• в возвращаемых значениях обратной инструкции (например, инструкции чтения памяти) и/или
• в возвращаемом значении инструкции вызова процедуры и/или
• такая информация может быть определена в протоколе взаимодействия исполнительных элементов на этапе разработки и/или настройки исполняемой программы.
Для адресации ресурсов могут быть использованы распределенные указатели
(ссылки). Возможным вариантом адресации ресурсов является способ, при котором ресурсы, которые предоставляются в распределенном стеке, последовательно добавляется к совокупности предоставленных ресурсов в этом распределенном стеке. Вся совокупность предоставленных стеку ресурсов рассматривается как единое пространство.
Если в качестве ресурса используется память, то в качестве распределенного адреса ресурса может быть использовано смещение от начала выделенной в распределенном стеке вызовов памяти (так, как это предложено в прототипе). Более универсальным способом, который предложен в заявляемом изобретении, является использование числового индекса ресурса. Каждому выделенному в распределенном стеке ресурсу присваивается последовательный числовой индекс. Текущий максимальный индекс ресурсов, выделенных в распределенном стеке, передается в инструкции передачи управления. Использование индекса в качестве распределенного указателя позволяет, во-первых, адресовать ресурсы, которые занимают в памяти различную длину, во-вторых, в качестве ресурсов может использоваться не только память (например, дескрипторы системных объектов или других программных или аппаратных объектов).
Возможный вариант технической реализации является следующим: индекс или распределенный адрес связывается с локальным идентификатором ресурса на основании управляющей таблицы (или управляющего связанного списка). Каждый исполнительный элемент имеет свою часть таблицы для своих ресурсов определенного распределенного стека вызовов. Строка таблица связывает распределенный адрес или индекс с локальным адресом памяти этого ресурса (или другим локальным идентификатором ресурса). Если код приложения обращается к ресурсу, исполнительный элемент ищет этот ресурс в управляющей таблице по его распределенному адресу или индексу. Если он не находит ресурс в своей управляющей таблице, он обращается к предыдущему в распределенном стеке вызовов исполнительному элементу. Если ресурс принадлежит предыдущему исполнительному элементу, этот исполнительный элемент обращается к ресурсу. Иначе предыдущий исполнительный элемент обращается к своему предыдущему в стеке вызовов исполнительному элементу.
В заявляемом изобретении, кроме числового индекса массива, можно использовать индексы другого типа, например, строковые. Такой индекс не обязательно является уникальным. В качестве индекса можно использовать имя переменной, имя функции или имя объекта. Алгоритм поиска ресурсов на определенном исполнительном элементе является несущественным для изобретения. Например, алгоритм может определяться логикой областей видимости переменных. Если исполнительный элемент не находит ресурс в своей памяти, он обращается к предыдущему в стеке вызовов исполнительному элементу.
Еще одним вариантом реализации распределенных указателей в заявляемом изобретении является ассоциативная адресация. В этом варианте поиск ресурса ведется в совокупности выделенной распределенному стеку памяти, на основании ассоциативного адреса. Ресурсом может быть память, в которой расположен код или фрагмент кода программы, или динамические данные, или другие ресурсы. Указанные выше управляющие таблицы в этом случае не требуются. Последовательность поиска на отдельном исполнительном элементе определяется типом ассоциативной адресации. Например, если ресурсом является процедура или переменная в памяти, поиск может вестись по имени в соответствии с правилами видимости имен языка программирования. Процедура программы может рассматриваться как статический ресурс. Если исполнительный элемент не находит ресурс в своей памяти, он обращается к предыдущему в сетке вызовов исполнительному элементу.
Строковый индекс или ассоциативный адрес позволяет связать ресурс с его идентификатором на этапе разработки или настройки программы. В этом случае идентификатор ресурса может быть определен в протоколе взаимодействия исполнительных элементов. Обмен информацией между исполнительными элементами для использования такого ресурса не требуется.
Если предоставляемым ресурсом является память, то для описанных выше управляющих таблиц тип памяти не имеет значения. Обычно память любого типа расположена в одном локальном адресном пространстве. Это может быть память из локального стека локального потока управления (с которым ассоциирован распределенный стек вызовов), динамическая память из кучи, или статическая память. От типа предоставляемой памяти зависит то, как она должна освобождаться.
Память из локального стека удаляется автоматически при раскрутке распределенного стека вызовов.
Динамическая память может одновременно использоваться несколькими распределенными стеками вызовов. Для освобождения динамической памяти могут быть использованы локальные счетчики ссылок, локальные связанные списки ссылок, или локальные сборщики мусора. При этом сами ссылки на ресурсы должны принадлежать определенным распределенным стекам вызовов. В общем случае, распределенная ссылка на один и тот же ресурс в разных распределенных стеках может иметь разное значение распределенного адреса. Для того, чтобы ссылка на ресурс одного распределенного стека не была использована в другом распределенном стеке, ссылка может включать указатель на управляющую структуру своего распределенного стека, или ссылка может включать идентификатор распределенного стека. Ссылки удаляются при завершении работы распределенного стека на данном исполнительном элементе. При этом модифицируется управляющая информация, которой могут являться счетчики ссылок или связанные списки. Если все распределенные стеки вызовов, которые используют ресурс, завершают работу на исполнительном элементе, то используемая динамическая память автоматически освобождается. При этом управление ссылками является полностью локальным и не требует передачи сообщений между узлами системы.
Для статической памяти может вестись учет распределенных стеков, которые используют эту память в данный момент. Освобождение памяти в этом случае означает модификацию управляющей информации. Статические ресурсы могут предоставляться для использования в распределенных стеках и никогда фактически не освобождаться.
Еще одним известным вариантом технической реализации распределенных указателей на ресурсы является специальный указатель (ссылка), который включает адрес исполнительного элемента и локальный идентификатор ресурса (например, локальный адрес памяти). В качестве адреса исполнительного элемента может быть использован сетевой адрес узла, или номер процессора, или совокупность идентификатора процесса и адреса исполнительного элемента, или виртуальный адрес, или что-то другое. Каждый такой указатель содержит полную информацию о ресурсе и не зависит от других предоставленных ресурсов (то есть, предоставленные ресурсы не нужно рассматривать как единую совокупность). Для использования таких распределенных указателей не требуются описанные выше управляющие таблицы. Кроме этого, в инструкции передачи управления не требуется передавать специальную управляющую информацию. Один исполнительный элемент может обратиться к ресурсу другого исполнительного элемента через сетевой адрес исполнительного элемента, который содержится в распределенном указателе. Такие указатели могут просто передаваться в параметрах или в возвращаемых значениях распределенных вызовов процедур.
В большинстве реальных систем одновременно существует более одного распределенного стека вызовов. Заявляемое изобретение предлагает для идентификации каждого выполняемого распределенного стека использовать уникальный идентификатор. Этот идентификатор является уникальным в вычислительной системе на время выполнения распределенного стека вызовов. Он должен передаваться в инструкции распределенной передачи управления (например, как часть управляющей информации). Отсутствие идентификатора может рассматриваться как NULL - значение, которое может быть присвоено одному распределенному стеку вызовов. В частности, NULL - значение может быть использовано в системе, в которой выполняется только один распределенный стек вызовов.
Существуют известные способы создания уникальных идентификаторов. Если все узлы системы имеют уникальные адреса, то для идентификатора распределенного стека может быть использована простая комбинация адреса узла и короткого идентификатора, который является уникальным на этом узле в данный момент времени. Если система включает множество независимых сетей, то может быть использован стандартный 16 - байтный глобально - уникальный идентификатор (GUID).
Другим вариантом идентификатора является цифровая подпись известной информации и/или информации, передаваемой одновременно с уникальным идентификатором. Цифровая подпись как идентификатор может передаваться полностью или в усеченном виде (для уменьшения объема трафика). Техническим результатом использования цифровой подписи является возможность идентифицировать компьютер или пользователя, который инициировал выполнение распределенного стека вызовов. Также возможно вложение цифровых подписей в цепочке вызовов распределенного стека.
Уникальный идентификатор распределенного стека позволяет рассматривать стек как полудуплексное соединение, которое соединяет любое количество узлов системы. Узел, который в данный момент получил управление, является активным. Он может вызвать процедуру другого узла или вернуть управление из инструкции распределенной передачи управления. Остальные узлы стека вызовов являются пассивными. Пассивный узел может стать активным при возврате управления из выполняемой инструкции передачи управления или при получении входящего распределенного вызова процедуры. Для реализации полностью дуплексного взаимодействия между двумя узлами могут быть установлены два встречных распределенных стека вызовов с совместно используемыми ресурсами.
Во всех случаях, заявляемый способ работоспособен без уникального идентификатора распределенного стека вызовов. Исполнительный элемент хранит информацию о предыдущем в стеке вызовов исполнительном элементе. Обратная инструкция может предаваться назад по цепочке вызовов до исполнительного элемента владельца ресурса. Идентификация стека между каждой парой узлов в цепочке вызовов является достаточной. Если система поддерживает сквозную идентификацию цепочек соединений между исполнительными элементами, распределенный стек может быть ассоциирован с определенным соединением. В этом случае отдельный идентификатор распределенного стека так же не требуется.
Типичное взаимодействие в клиент - серверной системе в соответствии с заявляемым изобретением включает следующие шаги:
1) Клиент выделяет ресурс (объект или функцию) для обратного вызова и удаленно вызывает процедуру сервера.
2) Сервер предоставляет необходимый клиенту ресурс и передает ссылку на него в обратном вызове.
3) Клиент удаленно вызывает предоставленный на сервере ресурс в инструкции обратного вызова.
Такая последовательность полностью соответствует классическому трех - шаговому установлению сетевого соединения. Это позволяет напрямую использовать ненадежный сервис без установления соединений для передачи сообщений между исполнительными элементами (например, UDP или Ethernet). Техническим результатом является возможность передавать данные, начиная с первой команды установления соединения. Для реализации этой идеи рассматриваемая выше управляющая структура распределенного стека может быть дополнена переменными и таймерами повторной передачи, которые определяют состояние соединения. К информации, передаваемой в удаленном вызове, нужно добавить порядковый номер сообщения. Кроме этого, нужно осуществлять повторную передачу при отсутствии подтверждения по тайм-ауту. Еще одним техническим результатом является возможность использования заявляемого способа для реализации сетевых протоколов с установлением соединения. В этом случае распределенный стек вызовов передает данные других приложений, а предоставляемыми ресурсами являются протокольные конечные автоматы.
Как было отмечено выше, заявляемый способ является универсальным и может быть использован для решения множества различных задач. Рассмотренная реализация изобретения является далеко не единственно возможной. Возможно множество других реализаций в различных исполнительных системах и в различных реализациях удаленных и локальных вызовов процедур. Можно с уверенностью утверждать, что любая реализация RPC и LPC может быть расширена в соответствии с заявляемым изобретением.