Способ и система контроля процессов в операционной системе на микроядре
Изобретение может быть использовано в роботизированных системах и навигационных системах роботов. Согласно способу контроля процессов в операционной системе на микроядре получают дескриптор очередного процесса из планировщика действующей очереди выполнения процессов; проверяют, пуста ли очередь выполнения процессов; проверяют с помощью планировщика, закончен ли внутренний цикл очередного процесса, и, если он закончен, то перемещают дескриптор очередного процесса в очередь ожидания; если очередь выполнения пуста, обрабатывают путем смешивания все сообщения, находящиеся в системной очереди сообщений, и уменьшают объем всех счетчиков связей в базе данных маршрутизации сообщений (MRD) после завершения цикла смешивания; перемещают с помощью планировщика дескрипторы всех процессов из очереди «ожидания» в очередь выполнения для подготовки системы к следующему циклу смешивания, в ином случае используют дескрипторы следующего по очереди процесса; уменьшают с помощью планировщика объем входных/выходных счетчиков текущего процесса и проверяют значения объемов этих входных/выходных счетчиков, при этом, если значения счетчиков меньше нуля, то увеличивают объем счетчика процесса, в ином случае - перемещают процесс из очереди выполнения в очередь ожидания. 2 н. и 2 з.п. ф-лы, 6 ил.
Изобретение относится к способам и системам программного управления, а именно к способам и системам контроля процессов в микроядерной (microkernel) операционной системе, и может быть использовано в роботизированных системах и навигационных системах роботов.
Вследствие быстрого роста цифровых сетей связи и дальнейшего расширения функциональности подключенных к ним устройств встает проблема размещения ресурсов устройств и предоставления доступа к этим ресурсам.
Другое современное и быстро растущее направление развития информационных технологий - это распределенные компьютерные и мультиагентные вычислительные системы. Существует множество преимуществ использования мультиагентных систем. Одно из них способность к самоорганизации и адаптации, а также гибкость.
Многие современные мультиагентные системы построены на основе программных библиотек, которые работают на уровне приложения или поддерживаются в компиляторах как парадигма программирования (см., например, патенты США 7228187 и 7275048).
Во всех этих областях существует главная проблема создания автономных систем адаптивных к меняющемуся окружению с эффективным управлением выполнением процессов, производимых данными системами.
Наиболее близким к заявляемому изобретению в части системы является операционная система M.O.N.S.T.E.R. (см. M.O.N.S.T.E.R.: А new behavior-based microkernel for mobile robots. Dirk Spenneberg, Martin Albrecht, Till Backhaus, Robotics Lab, Faculty of Mathematics and Computer Science, University of Bremen. Bibliotheksstr. 1, D-28359 Bremen, Germany (http:/www.informatik.uni-bremen.de/robotik), в которой применена концепция разделенных процессов совместно с экспортом ресурсов. Данная система выбрана в качестве прототипа заявленного изобретения. Основной недостаток прототипа заключается в недостаточной гибкости при экспорте ресурсов и реализации интерфейсов на языковом уровне, в результате чего система не может быть действительно распределенной системой. Кроме того, процессы в ней должны быть жестко связаны в силу заранее определенных интерфейсов. Указанные недостатки ухудшают гибкость, адаптивность и способность к самоорганизации системы-прототипа.
Задачей, на решение которой направлено заявляемое изобретение, заключается в разработке способа и системы контроля процессов, которые позволили бы повысить гибкость, адаптивность и способность к самоорганизации микроядерной операционной системы.
Поставленная задача решена путем создания способа контроля процессов в микроядерной операционной системе, отличающегося тем, что
- получают описатель (далее упоминается как «дескриптор») следующего процесса для планирования из действующей очереди выполнения процессов;
- проверяют, пуста ли очередь выполнения;
- проверяют с помощью планировщика, закончен ли внутренний цикл процесса, если закончен, то перемещают дескриптор процесса в очередь ожидания;
- если очередь выполнения пуста, обрабатывают путем смешивания все сообщения, находящиеся в системной очереди сообщений, и уменьшают (декрементируют) объем всех счетчиков связей (link counters) в базе данных маршрутизации сообщений (MRD - Message Routing Database) после завершения цикла смешивания;
- перемещают с помощью планировщика дескрипторы всех процессов из очереди «ожидания» в очередь выполнения для подготовки системы к следующему циклу смешивания, в ином случае используют дескрипторы следующего процесса в очереди;
- уменьшают с помощью планировщика объем I/O (input/output) счетчиков текущего процесса (process counters) и проверяют значения объемов этих I/O счетчиков, при этом, если значения счетчиков меньше нуля, то увеличивают (инкрементируют) объем счетчика процесса, в ином случае - перемещают процесс из очереди выполнения в очередь ожидания.
Для функционирования способа важно, чтобы увеличивали объем счетчиков процесса каждый раз, когда процесс получает или отправляет сообщение, и при этом выполняли следующие операции:
- когда инициируется отправка сообщения, с помощью процедуры отправки пытаются получить дескриптор отсылающего процесса для предотвращения анонимности сообщения, при этом, если не получают этот дескриптор, то уничтожают сообщение, в ином случае - отправляют сообщение, при этом процедура получает список подписчиков из базы данных маршрутизации сообщений по дескриптору;
- проверяют список подписчиков, при этом, если список подписчиков пуст, это означает, что для данного процесса нет подписчиков, и объем выходных счетчиков (output counters) уменьшают на соответствующую величину, как и объем счетчиков ссылок для дескриптора в базе данных маршрутизации сообщений, после чего сообщение уничтожают и обрабатывают следующее сообщение в очереди; если список подписчиков не пуст, сообщение дублируют для каждого подписчика из списка и суммируют число успешных дублей;
- увеличивают объем I/O счетчиков для процесса отправки на соответствующую величину, которую определяют из числа успешных попыток, соответственно также увеличивают объем счетчиков ссылок в MRD.
Для функционирования способа важно, чтобы сообщение дублировали для каждого подписчика, причем генерировали сообщение, которое нужно продублировать, и список подписчиков в качестве параметров, а в ответ сообщали о числе успешных попыток дублирования, и при этом выполняли следующие операции:
- получают список подписчиков и сообщение, которое нужно послать, в качестве параметров и осуществляют копирование сообщения;
- копируют сообщение в очередь сообщений процесса, идентифицированного по дескриптору подписчика, причем, если дескриптор подписчика опознан и копирование было произведено успешно, тогда увеличивают объем счетчика ссылок в списке подписчиков для данного дескриптора и увеличивают объем входных счетчиков данного дескриптора процесса.
Поставленная задача решена также путем создания системы контроля процессов в микроядерной операционной системе, содержащей перемешивающий слой и подсистему сообщений, которая сформирована как отдельная подсистема и включает в себя базу данных маршрутизации сообщений (MRD), которая используется подсистемой для маршрутизации сообщениями, причем MRD организована как объектная база данных и содержит два типа таблиц: таблицу источников сообщений (MRT) и таблицу подписчиков, при этом MRD имеет системную очередь сообщений, в которую поступают сообщения от процессов для дальнейшей пересылки подсистемой сообщений.
Таким образом, технический результат достигается за счет создания дополнительных атрибутов в описателях выполняемых процессов, введения способа обнаружения и составления списка процессов в операционной системе, а, также за счет осуществления распределенной обработки данных. Распределенная обработка данных обеспечена введением, так называемого, "перемешивающего слоя", обеспечивающего синхронизацию всех выполняемых процессов. Полный цикл синхронизации всех процессов далее обозначается как "цикл смешивания".
Для лучшего понимания заявленного изобретения далее приводится его подробное описание с привлечением графических материалов.
Фиг.1. Схема дополнительных атрибутов к описателю процесса, выполненного согласно изобретению.
Фиг.2. Схема пошагового выполнения способа контроля процессов в микроядерной операционной системе, осуществляемого согласно изобретению.
Фиг.3. Схема пошагового выполнения процедуры увеличения объема счетчиков процессов, выполненной согласно изобретению.
Фиг.4. Схема структуры базы данных маршрутизации (MRD) процесса, выполненной согласно изобретению.
Фиг.5. Схема движения сообщения в микроядерной операционной системе согласно изобретению.
Фиг.6 Схема пошагового выполнения процедуры дублирования сообщения, выполненной согласно изобретению.
Существо заявляемого изобретения заключается в следующем. Представляется важным, чтобы каждый процесс в системе был отделен от других процессов для обеспечения следующих характеристик: гибкости, адаптивности, устойчивости к сбоям и сохранности данных, и поэтому они должны быть связаны один с другим лишь ассоциативными связями. Это означает недопустимость прямых взаимодействий между процессами (direct inter-process communication). После запуска каждому процессу присваивают уникальный идентификатор (дескриптор) и регистрируют его описание в базе данных описаний ресурсов.
Каждый процесс имеет точку входа в логический блок процесса, и, в общем случае, логический блок осуществляет бесконечный замкнутый цикл. Планировщик управляет выполнением процесса, т.е. осуществляет контроль, и гарантирует один цикл выполнения логического блока для каждого процесса в общем цикле смешивания. Поэтому характеристический период (время цикла смешивания) в такой операционной системе описывают следующим выражением
,
где N - число выполняемых в данный момент процессов, tn - время выполнения процесса под номером n.
Каждый процесс в системе, помимо стандартного дескриптора процесса, имеет дескриптор его поведения и совместной работы (дескриптор группового или «социального» поведения процесса). Дескриптор группового поведения процесса может быть организован как в виде дополнительных атрибутов в стандартном описателе, так и в виде отдельного блока. Используя дескриптор группового поведения процесса, планировщик может принять решение о прекращении (уничтожении) процесса, если поведение процесса становится «асоциальным», т.е. неблагоприятным, по отношению к системе. Решение основывается на формальных параметрах, которые отражают групповые связи процесса, а для обеспечения работы данного механизма вводятся счетчики сообщений (input counters). Групповые связи формируются в процессе обмена данными между процессами и при отсутствии связей (обмена сообщениями) для конкретного процесса, такой процесс считается несоответствующим системе и должен быть прекращен. Таким образом, в каждом процессе необходимо реализовывать алгоритмы для установления и поддержания групповых («социальных») связей. Иначе такой процесс, в конечном счете, будет прекращен планировщиком.
Как было сказано выше, каждый процесс должен быть хорошо отделен от других. В идеале, он не должен знать ничего о других выполняемых процессах в системе в исходном состоянии процесса, когда он загружен в первый раз. Таким образом, главная идея заключается в том, чтобы сделать его анонимным процессом. Каждый процесс имеет входящую и выходящую информацию, в исходном состоянии процесс пытается найти необходимые для работы ресурсы, посылая входные и выходные запросы в систему. Чтобы быть независимым от архитектуры системы (типа файловой системы и структуры файловой системы), он должен знать только описание необходимого ресурса. Для того чтобы сделать механизм работоспособным, предложен также способ поиска ресурсов.
Для выполнения заявленного способа используют счетчики связей в дескрипторе процесса (Фиг.1). Поля, которые должны быть добавлены в дескриптор процесса для предоставления информации для смешивающих слоев, следующие: объем счетчика 1 посланных (output) сообщений увеличивается каждый раз, когда сообщение было успешно послано данным процессом. Объем счетчика 2 полученных (input) сообщений увеличивается каждый раз, когда сообщение было успешно получено данным процессом; объем счетчика 3 посланных байтов увеличивается на число байтов, посланных в сообщении; объем счетчика 4 полученных байтов увеличивается на число байтов, полученных в сообщении; трасса 5 всего времени выполнения - это связанный список периодов выполнения циклов для недавно выполненных циклов процесса.
Рассмотрим пошаговое выполнение заявленного способа (Фиг.2). Сначала получают дескриптор следующего процесса из очереди ожидания (шаг 1). Проверяют, пуста ли очередь выполнения (шаг 2). Перемещают все процессы из очереди ожидания в очередь выполнения (шаг 3). Перемещают процесс в очередь выполнения (шаг 4). Проверяют, закончен ли цикл выполнения для данного процесса (шаг 5). Уменьшают объем I/O-счетчиков процесса (шаг 6). Прекращают процесс (включают процесс в очередь на прекращение) (шаг 7). Проверяют, обнулены ли I/O счетчики процесса (шаг 8). Перемещают процесс из очереди выполнения в очередь ожидания (отложенный процесс) (шаг 9). Обрабатывают все сообщения из очереди сообщений в подсистеме сообщений и уменьшают объем всех счетчиков ссылок в MRD (шаг 10).
Как видно из описания, в ходе выполнения способа все процессы будут прекращены, так как объемы их I/О-счетчиков будут сведены к нулю. Чтобы избежать прекращения, процесс должен постоянно увеличивать объем своих счетчиков. Для обеспечения совместной работы в данном изобретении предложена косвенная процедура увеличения объема I/О-счетчиков для процесса, которую выполняют следующим образом (см. Фиг.3). Получают дескриптор отправляющего процесса (шаг 11). Проверяют правильность дескриптора отправителя (шаг 12). Уничтожают сообщение и выходят из процедуры (шаг 13). Получают список подписчиков из таблицы источников сообщений (MRT - Message Routing Table) (шаг 14). Уменьшают объем счетчиков отправленных сообщений отправляющего процесса (шаг 15). Вызывают процедуру дублирования сообщения (шаг 16). Увеличивают объем выходных счетчиков отправляющего процесса на соответствующую величину (шаг 17). Увеличивают объем выходных счетчиков MRT для дескриптора на соответствующую величину (шаг 18). Уменьшают объем счетчиков ссылок в MRT для дескриптора (шаг 19).
Подсистема сообщений сформирована как отдельная подсистема микроядерной операционной системы и должна выполнять описанные ниже функции. Основой подсистемы сообщений является база данных маршрутизации сообщений (MRD) (см. Фиг.4), которая используется подсистемой для маршрутизации сообщений. MRD организована как объектная база данных и содержит два типа таблиц: таблицу 6 источников сообщений и таблицу 7 получателей сообщений. MRD имеет системную очередь сообщений, в которую поступают сообщения от процессов для дальнейшей их пересылки подсистемой сообщений.
Поток сообщений в операционной системе на микроядре показан на Фиг.5. Сообщения из очереди 8 системных сообщений обрабатываются в каждом цикле перемешивающего слоя. Когда все процессы 9 завершают очередной цикл выполнения (цикл перемешивающего слоя), подсистема сообщений обрабатывает все сообщения в очереди 8 до следующего цикла перемешивания.
Параметры для процедуры отправки отправляют только в блоке сообщения. Процедура не предусматривает возврата значений.
Процедура дублирования заключается в получении сообщения, которое нужно продублировать, и списка подписчиков в качестве параметров, и в ответ сообщаются данные о числе успешных попыток дублирования. Пошаговое выполнение процедуры дублирования показано на Фиг.6. Получают очередной дескриптор из списка подписчиков (шаг 20). Проверяют дескриптор пользователя (шаг 21). Копируют (дублируют) сообщение в очередь входящих сообщений процесса, идентифицированного по дескриптору (шаг 22). Проверяют, прошло ли копирование успешно (процесс присутствует, но очередь не сформирована) (шаг 24). Далее, либо уменьшают объем счетчика ссылок для дескриптора в MRT (шаг 23), а затем уменьшают объем счетчика ссылок принятых по дескриптору сообщений процесса (шаг 27), либо увеличивают объем счетчика ссылок для дескриптора в таблице MRT (шаг 25), а затем увеличивают объем счетчика принятых по дескриптору процесса сообщений (шаг 26).
Главным применением заявленного изобретения могут быть роботизированные системы во встроенных и навигационных системах роботов.
Хотя указанный выше вариант выполнения изобретения был изложен с целью иллюстрации настоящего изобретения, специалистам ясно, что возможны разные модификации, добавления и замены, не выходящие из объема и смысла настоящего изобретения, раскрытого в прилагаемой формуле изобретения.
1. Способ контроля процессов в операционной системе на микроядре, отличающийся тем, что
получают дескриптор очередного процесса из планировщика действующей очереди выполнения процессов;
проверяют, пуста ли очередь выполнения процессов;
проверяют с помощью планировщика, закончен ли внутренний цикл очередного процесса, и, если он закончен, то перемещают дескриптор очередного процесса в очередь ожидания;
если очередь выполнения пуста, обрабатывают путем смешивания все сообщения, находящиеся в системной очереди сообщений, и уменьшают объем всех счетчиков связей в базе данных маршрутизации сообщений (MRD) после завершения цикла смешивания;
перемещают с помощью планировщика дескрипторы всех процессов из очереди «ожидания» в очередь выполнения для подготовки системы к следующему циклу смешивания, в ином случае используют дескрипторы следующего по очереди процесса;
уменьшают с помощью планировщика объем входных/выходных счетчиков текущего процесса и проверяют значения объемов этих входных/выходных счетчиков, при этом если значения счетчиков меньше нуля, то увеличивают объем счетчика процесса, в ином случае - перемещают процесс из очереди выполнения в очередь ожидания.
2. Способ по п.1, отличающийся тем, что увеличивают объем счетчика процесса каждый раз, когда процесс получает или отправляет сообщение, при этом выполняют следующие операции:
когда инициируется отправка сообщения, с помощью процедуры отправки пытаются получить дескриптор отсылающего процесса для предотвращения анонимности сообщения, при этом, если получают этот дескриптор, то уничтожают сообщение, в ином случае отправляют сообщение, при этом процедура получает список подписчиков из MRD;
проверяют список подписчиков, при этом, если список подписчиков пуст, это означает, что для данного процесса нет подписчиков, и объем выходных счетчиков уменьшают на соответствующую величину, как и объем счетчиков ссылок для дескриптора в MRD, после чего сообщение уничтожают и обрабатывают следующее сообщение в очереди; если список подписчиков не пуст, сообщение дублируют для каждого подписчика из списка и суммируют число успешных дублей;
увеличивают объем входных/выходных счетчиков для процесса на соответствующую величину, которую определяют из числа успешных попыток, соответственно также увеличивают объем счетчиков ссылок в MRD.
3. Способ по п.2, отличающийся тем, что сообщение дублируют для каждого подписчика, причем получают сообщение, которое нужно продублировать, и список подписчиков в качестве параметров, и посылают в ответ данные о числе успешных попыток дублирования, при этом выполняют следующие операции:
получают список подписчиков и сообщение, которое нужно послать в качестве параметров, и осуществляют копирование сообщения;
копируют сообщение в очередь сообщений процесса, идентифицированного по дескриптору подписчика, причем, если дескриптор подписчика подтвержден, и копирование было произведено успешно, то увеличивают объем счетчика ссылок в таблице подписчиков для данного дескриптора и увеличивают объем входных счетчиков данного дескриптора процесса.
4. Система управления выполнением процессов в операционной системе на микроядере, содержащая перемешивающий слой и подсистему сообщений, которая сформирована как отдельная подсистема и включает в себя базу данных маршрутизации сообщений MRD, которая используется подсистемой для маршрутизации сообщений, причем MRD организована как объектная база данных и содержит два типа таблиц: таблицу источников сообщений MRT и таблицу подписчиков, при этом MRD имеет системную очередь сообщений, в которую поступают сообщения от процессов для дальнейшей их пересылки подсистемой сообщений.
