Какие существуют способы реализации ядра системы
Евдокимов А.А., Майстренко Н.В., Майстренко А.В.
3.2.3. Реализация потоков в пользовательском пространстве
Первый способ реализации набора потоков — это поместить весь набор потоков в пользовательское пространство. Ядро операционной системы не имеет никакой информации о таком наборе. В таком случае ядро управляет с его точки зрения обычными процессами, которые состоят из одного потока. Самым очевидным преимуществом такой реализации считается то, что набор потоков может быть реализован в не поддерживающей потоки операционной системе.
Все эти реализации имеют одну и ту же общую структуру (рис. 3.8, а). Запуск потоков происходит поверх системы поддержки исполнения программ (run-time system), представляющей собой набор процедур, которые управляют потоками.
При управлении потоками в пользовательском пространстве для отслеживания собственных потоков каждый процесс должен иметь соответствующую таблицу потоков. Такая таблица является аналогом таблицы процессов, которая есть в ядре операционной системы. В таблице потоков содержатся свойства, которые принадлежат каждому потоку, например такие как счетчик команд, указатель на стек, регистры, состояние и т.д. Система поддержки исполнения программ управляет записями таблицы потоков. При переводе потока в состояние готовности или при блокировании информация, которая нужна для возобновления выполнения потока, сохраняется в таблице так же, как ядро операционной системы хранит данные о процессах в соответствующей таблице.
При совершении потоком каких-нибудь действий, вызывающих его локальную блокировку, он вызывает процедуру системы поддержки исполнения программ. Данная процедура осуществляет проверку потока на возможность перевода в состояние блокировки. Она сохраняет по возможности регистры потока в соответствующие записи таблицы потоков, затем находит поток, который готов к выполнению, и перезагружает регистры сохраненными значениями нового потока. После переключения указателя стека и счетчика команд выполнение ново¬го потока автоматически возобновляется. Если машина получает инструкцию сохранения всех регистров, а последующей инструкцией будет загрузка всех регистров, то полное переключение потока осуществляется всего лишь за несколько инструкций. Переключение потоков, которое осуществляется подобным образом, на порядок быстрее, чем перехват управления ядром. Такое преимущество является достаточно веским аргументом в пользу реализации набора потоков на пользовательском уровне.
Но потоки имеют также одно основное отличие от процессов. При временной приостановке выполнения потока, например при вызове thread_yield, код процедуры thread_yield самостоятельно сохраняет данные о потоке в таблицу пото¬ков. Эту процедуру также может затем вызвать планировщик потоков, который выберет другой поток для исполнения. Вызов таких локальных процедур более эффективен, чем вызов ядра. Кроме того, не нужен перехват управления ядром, не требуется переключение контекста, нет необходимости сбрасывать кэш из памяти на диск и т.д. Все эти обстоятельства ускоряют работу планировщика потоков.
Но при лучшей производительности реализация потоков на пользова¬тельском уровне имеет и ряд существенных проблем. Самой первой проблемой является вопрос реализации блокирующих системных вызовов. Если, например, некоторый поток считывает информацию перед нажатием какой-нибудь клавиши клавиатуры, то такому потоку невозможно разрешить осуществление системного вызова, так как это приведет к приостановке выполнения всех потоков. При этом работая с блокирующими системными вызовами, довольно трудно достичь главной цели организации потоков, состоящей в возможности использования потоками блокирующих вызовов без оказания влияния на выполнение других потоков.
Реализация набора потоков на пользовательском уровне связана еще с одной проблемой: если один из потоков начинает свое выполнение, то никакой другой поток, который принадлежит этому же процессу, не сможет выполняться до тех пор, пока первый поток не освободит центральный процессор. Процесс не поддерживает прерываний по таймеру своих потоков, то есть в контексте процесса нет возможности планирования работы потоков по круговому циклу.
Какие существуют способы реализации ядра системы
Главное меню
Соглашение
Регистрация
Английский язык
Астрономия
Белорусский язык
Информатика
Итальянский язык
Краеведение
Литература
Математика
Немецкий язык
Обществознание
Окружающий мир
Русский язык
Технология
Физкультура
Для учителей
Дошкольникам
VIP — доступ
Автор: К.Самусенко | ID: 16941 | Дата: 14.4.2022
Помещать страницу в закладки могут только зарегистрированные пользователи
Зарегистрироваться
Получение сертификата
о прохождении теста
Тест с ответами по дисциплине Операционные системы
Какие особенности характерны для современных универсальных операционных систем?
+ 1. поддержка многозадачности
+ 2. поддержка сетевых функций
+ 3. обеспечение безопасности и защиты данных
4. предоставление большого набора системных функций разработчикам приложений
Какие утверждения относительно понятия «API-функция» являются правильными?
+ 1. API-функции определяют прикладной программный интерфейс
+ 2. API-функции используются при разработке приложений для доступа к ресурсам компьютера
3. API-функции реализуют самый нижний уровень ядра системы
4. API-функции — это набор аппаратно реализованных функций системы
Какие особенности характерны для ОС Unix
+ 1. открытость и доступность исходного кода
2. ориентация на использование оконного графического интерфейса
+ 3. использование языка высокого уровня С
+ 4. возможность достаточно легкого перехода на другие аппаратные платформы
Какие типы операционных систем используются наиболее часто в настоящее время?
+ 1. системы семейства Windows
+ 2. системы семейства Unix/Linux
3. системы семейства MS DOS
4. системы семейства IBM OS 360/370
Какие задачи необходимо решать при создании мультипрограммны х ОС
+ 1. защита кода и данных разных приложений, размещенных вместе в основной памяти
+ 2. централизованное управление ресурсами со стороны ОС
+ 3. переключение процессора с одного приложения на другое
4. необходимость размещения в основной памяти кода и данных сразу многих приложений
Какое соотношение между используемыми на СЕРВЕРАХ операционными системами сложилось в настоящее время?
+ 1. примерно поровну используются системы семейств Windows и Unix/Linux
2. около 10 % — системы семейства Windows, около 90 % — системы смейства Unix/Linux
3. около 90 % — системы семейства Windows, около 10 % — системы семейства Unix/Linux
4. около 30 % — системы семейства Windows, около 30 % — системы семейства Unix/Linux, около 40 % — другие системы
Какие утверждения относительно понятия «Ядро операционной системы» являются правильными?
+ 1. ядро реализует наиболее важные функции ОС
+ 2. подпрограммы ядра выполняются в привилегированно м режиме работы процессора
3. ядро в сложных ОС может строиться по многоуровневому принципу
4. ядро всегда реализуется на аппаратном уровне
Какие сообщения возникают при нажатии на клавиатуре алфавитно-цифров ой клавиши?
Какие шаги в алгоритме взаимодействия приложения с системой выполняются операционной системой
1. формирование сообщения и помещение его в системную очередь
+ 2. распределение сообщений по очередям приложений
+ 3. вызов оконной функции для обработки сообщения
4. извлечение сообщения из очереди приложения
Что представляет собой понятие “сообщение” (message)?
1. небольшую структуру данных, содержащую информацию о некотором событии
2. специальную API-функцию, вызываемую системой при возникновении события
3. однобайтовое поле с кодом происшедшего события
+ 4. небольшое окно, выводящее пользователю информацию о возникшем событии
Какие утверждения относительно иерархии окон являются справедливыми
+ 1. главное окно может содержать любое число подчиненных окон
+ 2. любое подчиненное окно может содержать свои подчиненные окна
3. подчиненные окна могут быть двух типов – дочерние и всплывающие
+ 4. приложение может иметь несколько главных окон
Как можно узнать координаты текущего положения мыши при нажатии левой кнопки
+ 1. с помощью события WM_LbuttonDown и его поля LPARAM
2. с помощью события WM_LbuttonDown и его поля WPARAM
3. с помощью события WM_LbuttonDown и его полей WPARAM и LPARAM
4. с помощью события WM_LbuttonCoordi nates
Какие функции можно использовать для получения контекста устройства?
Какая инструкция (оператор) является основной при написании оконной функции?
+ 1. инструкция множественного выбора типа Case — Of
2. условная инструкция if – then
3. инструкция цикла с известным числом повторений
4. инструкция цикла с неизвестным числом повторений
Какой вызов позволяет добавить строку в элемент-список?
+ 1. SendMessage (MyEdit, lb_AddString, 0, строка)
2. SendMessage (“Edit”, lb_AddString, 0, строка)
3. SendMessage (MyEdit, AddString, 0, строка)
4. SendMessage (MyEdit, строка, lb_AddString, 0)
Какие утверждения относительно оконной функции являются правильными
+ 1. оконная функция принимает 4 входных параметра
+ 2. тело оконной функции – это инструкция выбора с обработчиками событий
+ 3. оконная функция обязательно должна обрабатывать сообщение wm_Destroy
+ 4. оконная функция явно вызывается из основной функции приложения
Какие сообщения возникают при нажатии на клавиатуре функциональной клавиши?
Что может быть причиной появления внутреннего прерывания
+ 1. попытка деления на ноль
2. попытка выполнения запрещенной команды
+ 3. попытка обращения по несуществующему адресу
4. щелчок кнопкой мыши
Какие операции определяют взаимодействие драйвера с контроллером
+ 1. проверка состояния устройства
+ 2. запись данных в регистры контроллера
+ 3. чтение данных из регистров контроллера
4. обработка прерываний от устройства
Какие операции включает в себя вызов обработчика нового прерывания
+ 1. обращение к таблице векторов прерываний для определения адреса первой команды вызываемого обработчика
2. сохранение контекста для прерываемого программного кода
+ 3. занесение в счетчик команд начального адреса вызываемого обработчика
+ 4. внесение необходимых изменений в таблицу векторов прерываний
Что входит в программный уровень подсистемы ввода/вывода
2. диспетчер ввода/вывода
+ 3. системные вызовы
Что определяет понятие “порт ввода/вывода”
+ 1. порядковый номер или адрес регистра контроллера
2. машинную команду ввода/вывода
3. устройство ввода/вывода
4. контроллер устройства ввода/вывода
Какие существуют типы прерываний
+ 1. внешние или аппаратные прерывания
+ 2. внутренние прерывания или исключения
+ 3. программные псевдопрерывания
4. системные прерывания
Какие утверждения относительно понятия прерывания являются правильными
+ 1. прерывания — это механизм реагирования вычислительной системы на происходящие в ней события
2. прерывания используются для синхронизации работы основных устройств вычислительной системы
+ 3. прерывания возникают в непредсказуемые моменты времени
4. прерывания — это основной механизм планирования потоков
Какую информацию могут содержать регистры контроллеров устройства
+ 1. текущее состояние устройства
+ 2. текущую выполняемую устройством команду
3. данные, передаваемые от устройства системе
4. данные, передаваемые системой устройству
Как выстраиваются аппаратные прерывания в зависимости от их приоритета
1. сбой аппаратуры > таймер > дисковые устройства > сетевые устройства > клавиатура и мышь
2. сбой аппаратуры > таймер > дисковые устройства > клавиатура и мышь > сетевые устройства
+ 3. таймер > сбой аппаратуры > дисковые устройства > сетевые устройства > клавиатура и мышь
4. сбой аппаратуры > дисковые устройства > таймер > сетевые устройства > клавиатура и мышь
Что может быть причиной появления внешнего прерывания
+ 1. нажатие клавиши на клавиатуре
+ 2. завершение дисковой операции
3. обращение выполняемой процессором команды по несуществующему адресу
4. попытка выполнения запрещенной команды
Особенности реализации ядра системы имитационного моделирования Simulab Текст научной статьи по специальности «Компьютерные и информационные науки»
Аннотация научной статьи по компьютерным и информационным наукам, автор научной работы — Ершов Евгений Сергеевич
В статье рассмотрены особенности реализации ядра системы имитационного моделирования Simulab в режиме виртуального модельного времени. В частности, предлагаются методы повышения скорости работы с календарем событий, а также способы эффективного использования оперативной памяти.
i Надоели баннеры? Вы всегда можете отключить рекламу.
Похожие темы научных работ по компьютерным и информационным наукам , автор научной работы — Ершов Евгений Сергеевич
Анализ методов оценки производительности информационно-вычислительных систем в сегменте мультисервисной сети Омской области
Мультиагентное моделирование процессов распространения массовых эпидемий с использованием суперкомпьютеров
Агентное имитационное моделирование бизнес-процессов в нотации еepc
Мультиагентное моделирование процессов распространения и взаимодействия инфицирующих сущностей
Получение агентной имитационной модели из дискретно-событийного описания бизнес-процесса
i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.
i Надоели баннеры? Вы всегда можете отключить рекламу.
The peculiarities of implementation of Simulab simulation system core
Aspects of the effective implementation of the Simulab simulation engine for virtual time mode are considered. The methods of increasing the performance of the event queue and ways of effective use of memory are offered.
Текст научной работы на тему «Особенности реализации ядра системы имитационного моделирования Simulab»
изводствами) / А.М. Пуртов ; рук. работы В.А. Шапцев. — Омск: ИИТПМ СО РАН, 1994. — 138 с.
8. Смелянский, Р.Л. Об одной вероятностной модели программ / Р.Л. Смелянский, А.Г. Бахмуров, Д. Гурьев // Программирование. — 1986. — № 6. — 45-64.
ДУБЫНИН Дмитрий Геннадьевич, советник упра-
вления связи и безопасности министерства промышленной политики, транспорта и связи Омской области, аспирант.
Адрес для переписки:е-таП: ddg@omskportal.ru
Статья поступила в редакцию 13.05.2010 г.
УДК 681.3.06 Е. С. ЕРШОВ
Омский государственный технический университет
ОСОБЕННОСТИ РЕАЛИЗАЦИИ ЯДРА СИСТЕМЫ ИМИТАЦИОННОГО МОДЕЛИРОВАНИЯ SIMULAB________________________________________
В статье рассмотрены особенности реализации ядра системы имитационного моделирования Simulab в режиме виртуального модельного времени. В частности, предлагаются методы повышения скорости работы с календарем событий, а также способы эффективного использования оперативной памяти.
Ключевые слова: дискретно-событийное моделирование, агентное моделирование, эффективность.
В настоящее время существует большое количество различных систем имитационного моделирования (СИМ), как узкоспециализированных, так и многоцелевых. В данной статье будет рассматриваться система многоподходного имитационного моделирования Simulab, разработанная группой сотрудников кафедры АСОИУ ОмГТУ. В задачи автора статьи, в частности, входило проектирование и реализация ядра и среды разработки моделей СИМ Simulab. Среди особенностей Simulab можно выделить следующие:
1) Simulab реализует подходы системной динамики, динамических систем, процессного дискретнособытийного и агентного моделирования [1], используя один язык моделирования в единой графической среде разработки;
2) графическая среда разработки моделей значительно ускоряет процесс создания моделей;
3) архитектура системы Simulab позволяет подключать ее библиотеки к любой СИМ, обладающей открытым программным интерфейсом (AnyLogic 6, Repast Symphony и т.п.);
4) использование Simulab по сравнению с аналогами позволяет существенно сократить затраты времени и оперативной памяти на проведение имитационных экспериментов (ИЭ);
5) при проведении реплицированных экспериментов (под репликацией эксперимента подразумевается выполнение нескольких «прогонов» стохастической модели для одного набора значений параметров с дальнейшим усреднением результатов) Simulab полностью использует ресурсы компьютеров, оснащенных многоядерными процессорами, что также позволяет сократить временные затраты в 2 — 3 раза;
6) Simulab позволяет решать задачи оптимизации имитационных моделей (ИМ), построенных на базе сетей массового обслуживания [2];
7) как сама среда моделирования, так и все ее библиотеки реализованы на языке программирования Java, что позволяет пользователю работать с Simulab в любой операционной системе и на различных по архитектуре процессорах, для которых существует виртуальная Java-машина (Java Runtime Environment / JRE). Более того, пользователю, работающему на удаленном компьютере, предоставляется возможность запускать из сети (Intranet/Internet) как саму среду Simulab, так и созданные в ней модели, без необходимости устанавливать у себя какое-либо программное обеспечение (кроме Java Runtime Environment), при этом процесс моделирования может происходить как на компьютере пользователя, так и на удаленном сервере;
8) в качестве внутреннего языка также используется язык программирования Java. Таким образом, пользователю, знакомому с языками Java, C+ + или C # нет необходимости изучать какой-либо специализированный язык моделирования, который зачастую во многом будет ограничивать его возможности. Такой подход позволяет работать с имитационной моделью на уровне языка объектно-ориентированного программирования и пользоваться всеми возможностями языка Java. Кроме того, появляется возможность компилировать модель как в исполняемый файл, так и в апплет, не требующие для запуска среды моделирования;
9) редактор форм, входящий в состав Simulab, поддерживает большой набор интерактивных элементов (меток, кнопок, полей ввода и т.д.) и позволяет создавать интерфейсы любой степени сложности, а также связывать их с ИМ.
ОМСКИЙ НАУЧНЫЙ ВЕСТНИК №3 (93) 2010 ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ
ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ ОМСКИЙ НАУЧНЫЙ ВЕСТНИК №3 (93) 2010
Созданные интерфейсы могут использоваться с целью:
— создания управляющих оболочек с возможностью всестороннего контроля над процессом моделирования;
— формирования сложных отчетов, содержащих данные о результатах работы имитационной модели;
— создания сложных оптимизирующих подсистем;
— создания комплексных систем поддержки принятия решений (СППР) на основе имитационных моделей.
Набор стандартных управляющих элементов может быть расширен пользователем. Также поддерживаются средства анализа данных и большой набор элементов бизнес-графики, спроектированных для эффективной обработки и презентации результатов моделирования: статистики, наборы данных, графики, диаграммы, гистограммы;
10) Simulab обладает расширенным набором структур для моделирования больших сетей (таких как Интернет, сеть телефонных переговоров и т.д.) [3];
11) алгоритмы генерации графов, используемые в Simulab, работают в десятки раз быстрее алгоритмов, реализованных в популярной среде для работы с графами Java Universal Network/Graph Framework (JUNG) [4] и среде моделирования AnyLogic 6 [3];
12) 2D/3D анимация в Simulab создается автоматически уже при составлении структуры модели. В общем случае степень «реальности» виртуальной 3D модели, созданной в Simulab, определяется степенью детализации используемых 3D объектов, наличием соответствующего звукового окружения, специальных эффектов и т.п. Так как процессы имитационного моделирования и 3D визуализации являются достаточно ресурсоемкими, пользователю предоставляется возможность создания 2D/3D анимации не только во время имитационного эксперимента (на одном компьютере или нескольких компьютерах, объединенных в сеть), но и при пост-обработке, что значительно снижает нагрузку на компьютер.
2. Особенности реализации ядра СИМ Simulab
Основная задача, которая ставилась при разработке ядра (программы-планировщика для организации выполнения событий имитационной модели в хронологическом порядке) СИМ Simulab—минимизация времени выполнения имитационной модели на компьютере (процессорного времени).
Процессорное время в первую очередь зависит от частоты изменений в моделируемой системе за моделируемый период времени, а также от объема вычислений, связанных с обработкой событий [5]. Таким образом, моделирование сложных систем может потребовать значительных затрат процессорного времени.
Сокращение процессорного времени может быть достигнуто за счет эффективного и полноценного применения аппаратных ресурсов ЭВМ. В частности, решить проблемы ресурсоемкости и вычислительных затрат при имитационном моделировании позволит разработка новых способов построения алгоритмов ИМ и применение эффективных методов программирования.
Одной из важных составляющих ядра любой СИМ является календарь событий (очередь событий, event queue), состоящий в общем случае из элементов, каждый из которых содержит как минимум два поля:
— ссылку на запланированное событие (е);
— модельное время, на которое запланировано событие (t).
Таким образом, можно сказать, что календарь событий — это список элементов l, где = (e, t).
Ядро СИМ выбирает из календаря событий событие с минимальным временем, которое впоследствии становится текущим модельным временем. Далее ядро присваивает системной переменной с текущим модельным временем минимальное значение времени, на которое запланировано выполнение события и передает ему управление. Если сразу несколько событий запланированы на одно и то же время, то они выполняются последовательно друг за другом, системное время не изменяется до тех пор, пока все эти события не будут обработаны. Далее происходит удаление выполненных событий из календаря событий. Для того чтобы поиск был эффективным, календарь событий упорядочивают по возрастанию времени.
Обработка очередного события et также может порождать новое событие е, выполнение которого запланировано на некоторый момент времени t. Таким образом, в календаре событий появляется новый элемент 1, = (е,, tj). В этом случае ядро системы моделирования помещает новый элемент в календарь событий, сохраняя при этом упорядоченность по возрастанию.
Основная проблема дискретно-событийного и агентного моделирования — эффективное использование календаря событий. Традиционно календарь событий реализуется на основе связных списков (linked lists), основное преимущество которых — вставка и удаление элементов занимает время t = O(1), что делает их незаменимыми в случаях, когда необходима быстрая вставка элементов в начало или конец списка. Однако, в случае с календарем событий, проявляется и основной недостаток связных списков — время поиска места для вставки (для сохранения хронологической упорядоченности) пропорционально количеству элементов в данном списке. Большинство алгоритмов, предложенных в [6] и использующих связные списки, различными способами пытаются обойти этот недостаток, например:
1) предпринимается поиск с начала и конца списка;
2) для различных типов событий используют разные списки;
3) список с дополнительным указателем на его середину (элемент равноудаленный от начала и конца списка): при этом сначала происходит сравнение с нужным элементом, а потом поиск происходит в нужной половине списка (с начала и конца подсписка);
4) список событий делится на подсписки, которые соответствуют интервалам системного времени, при этом длины всех интервалов равны фиксированному значению, которое задается пользователем. При планировании нового события вычисляется его индекс в массиве указателей, после чего новый элемент списка событий может быть размещен в соответствующем его подсписке.
К сожалению, использование вышеперечисленных модификаций связного списка не только не приводит к значительному приросту производительности, но и усложняет алгоритм обработки списка.
Как показывает практика, при реализации календаря событий наиболее эффективными по сравнению со связными списками являются алгоритмы на основе самобалансирующихся бинарных деревьев поиска (self-balancing binary search trees). Вызвано это прежде всего тем, что и вставка (сортировка узлов осуществляется автоматически) и удаление
10000 100000 1000000 Количество элементов в календаре
Рис. 1. Эффективность реализаций календаря событий с использованием пула элементов (а), с использованием ссылок на экземпляры агентов (б) и с модификацией красно-черного дерева (в)
Рис. 2. Сравнение Simulab c современными системами ИМ по быстродействию в batch-режиме процессного моделирования
и поиск узла занимает логарифмическое время t = O(log2N), где N — количество узлов в дереве (далее под узлом дерева будем подразумевать элемент календаря событий). Как правило, используют красночерные деревья (red-black trees) [7], популярность которых связана с тем, что на них часто достигается лучшее соотношение между степенью сбалансированности (дерево сбалансировано, если путь от корня до каждого узла имеет длину, не превышающую
0(1од2М)) и сложностью ее поддержки. Сбалансированность достигается за счет введения дополнительного атрибута узла дерева—«цвет». Этот атрибут может принимать одно из двух возможных значений — «черный» или «красный». Красно-черное дерево обладает следующими свойствами:
— все листья черны;
— все потомки красных узлов черны (т.е. запрещена ситуация с двумя красными узлами подряд);
ОМСКИЙ НАУЧНЫЙ ВЕСТНИК №3 (93) 2010 ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ
ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ ОМСКИЙ НАУЧНЫЙ ВЕСТНИК №3 (93) 2010
Рис. 3. Сравнение 8шш1аЬ c системой ИМ AnyLogic 6 по быстродействию в агентном моделировании (а)
и по использованию оперативной памяти (б)
— на всех ветвях дерева, ведущих от его корня к листьям, число чёрных узлов одинаково (что и обеспечивает сбалансированность дерева).
Далее приведено несколько приемов, использованных при реализации ядра СИМ 81ши1аЪ, и в совокупности позволяющих в несколько раз повысить скорость работы с календарем событий на базе красно-черного дерева:
1) как было отмечено ранее, в общем случае время вставки нового узла в красно-черное дерево составляет t=0(Iog2N) (что имеет место, например, при вставке узла с минимальным или максимальным значением ключа). Однако, используя специальные указатели на узлы дерева с минимальным и максимальным значениями ключа, можно сократить время вставки в начало/конец календаря событий до t = 0(1);
2) для календаря событий на каждом шаге моделирования характерно добавление и удаление одного или нескольких элементов. Необходимо отметить, что в этом случае происходит создание/удаление новых экземпляров объектов (элементов календаря), что сильно сказывается на быстродействии календаря событий (рис. 1а). Для решения этой проблемы предлагается применять специальный пул элементов, который используется следующим образом: при удалении элемента из календаря событий он не уничтожается, а помещается в специально выделенный для этого массив. При добавлении в календарь событий нового элемента, ядро системы моделиро-вания сначала проверяет наличие в пуле удаленных элементов, и если таковые имеются, то использует один из них, в противном случае — создает новый элемент;
3) в частном случае в задачи ядра СИМ также входит хранение массива заявок, находящихся в моделируемой системе, а также управление этим массивом. Однако доступ к заявкам по индексу сопряжен с дополнительными временными расходами (рис. 1б), вызванными постоянной проверкой на выход за границы массива. Для решения этой проблемы предлагается хранить в элементе календаря событий ссылки на экземпляр заявки, связанной с событием;
4) стандартная реализация красно-черного дерева не предусматривает возможности хранения узлов с одинаковым значением ключа, что приводит к необходимости реализовывать в каждом узле, по меньшей мере, связный список, предназначенный для хранения событий, запланированных на одно время. Это приводит к дополнительным затратам памяти
(рис. 1в), поскольку мы вынуждены хранить ссылку на этот связный список, возможно, так никогда и не воспользовавшись им. Для решения этой проблемы предлагается модифицировать алгоритм вставки узлов в дерево таким образом, чтобы новые узлы со значением ключа, равным значению ключа существующего узла, рассматривались как узлы с меньшим значением ключа.
При реализации ядра СИМ также необходимо уделять внимание эффективному использованию оперативной памяти. Это особенно важно в агентном моделировании, поскольку при большом количестве (более миллиона) агентов календарь событий будет содержать миллионы элементов, при этом каждый агент будет обладать своими уникальными свойствами и автономным поведением (принятие решения в соответствии с некоторым набором правил, взаимодействие с окружающей средой и другими агентами, самоизменение и т.п.).
Далее приведено несколько приемов реализации класса агента, которые позволили значительно уменьшить затраты памяти в СИМ Simulab:
1) уменьшение количества полей, необходимых для описания базовых свойств агента. Очевидно, что при сокращении количества полей описывающих базовые свойства агента сократится и объем памяти, занимаемой всеми экземплярами данного агента. Добиться этого сокращения можно несколькими способами, например, следует отказаться от полей, значения которых при необходимости могут быть вычислены через другие поля.
Отказ от полей, которые не используются в текущем режиме моделирования, также позволит освободить память. Например, при моделировании в режиме виртуального модельного времени полностью отпадает необходимость в полях и методах, используемых только при визуализации агентов;
2) отказ от использования в качестве полей простых классов (таких как Point, Dimension и т.п.). Необходимо отметить, что, в этом случае при описании свойств агента в оперативной памяти будут храниться не только поля экземпляра класса, но и ссылка на этот экземпляр. Например, отказ от использования класса Point для описания текущего положения агента в непрерывном двухмерном пространстве и, соответственно, использование двух полей типа double, содержащих координаты, позволяет избежать неоправданных затрат памяти на хранение ссылок.
Как показали многочисленные эксперименты с дискретно-событийными, агентными и многоподходными моделями, ядро СИМ ЯішиІаЬ по сравнению с существующими аналогами позволяет:
— существенно сократить время на проведение ИЭ в режиме виртуального модельного времени: в 4 раза для дискретно-событийного моделирования (рис. 2) и в 1,5 — 2 раза для агентного моделирования (рис. 3а);
— сократить объем памяти, необходимой для проведения ИЭ (преимущественно в агентных моделях), в 2 — 3 раза (рис. 3б).
Нужно отметить, что данные результаты достигнуты при полной функциональной совместимости с аналогами и без использования каких-либо технологий распределенных вычислений.
Использование СИМ ЯішиІаЬ (или отдельных ее библиотек в составе других СИМ) позволит разработчикам:
— сократить время на разработку ИМ для решения задач в области производства, логистики и цепочек поставок, в сфере обслуживания, пешеходных и транспортных потоков, информационно-телекоммуникационных сетей, социальных и экологических процессов и систем и т.п.;
— по сравнению с аналогами существенно сократить затраты времени и оперативной памяти на проведение ИЭ;
— полностью использовать ресурсы многоядерных процессоров при проведении реплицированных ИЭ;
— оптимизировать сложные ИМ на базе сетей массового обслуживания;
— значительно упростить разработку СППР на основе ИМ.
1. Карпов, Ю.Г. Имитационное моделирование систем. Введение в моделирование с AnyLogic 5 / Ю.Г. Карпов. — СПб.: БХВ-Петербург, 2005. — 400 с.
2. Задорожный, В.Н. Градиентный метод и программа оптимизации сетей с очередями / В.Н. Задорожный, Е.С. Ершов // Омский научный вестник. — 2009. — № 2(80). — С. 205 — 210.
3. Ершов, Е.С. Система имитационного моделирования Simulab / Е.С. Ершов, Е.Б. Юдин // Имитационное моделирование. Теория и практика: матер. 4-й Всеросс. конф. ИММОД-2009.- СПб., 21-23 октября 2009 / ЦТСС.- СПб., 2009.-Т. 1.-С. 257-261.
4. Java Universal Network / Graph Framework Overview. -URL: http://jiing.soiirceforge.net/index.ht.ml. [Дата обращения: 04.05.2010].
5. Окольнишников, В.В. Представление времени в имитационном моделировании / В.В. Окольнишников / / Вычислительные технологии. — Сибирское отделение РАН, 2005. — Т. 10. -№ 5. — С. 57-77.
6. Миков, А.И. Распределенные системы и алгоритмы / А.И. Миков, Е.Б. Замятина.-URL: http://www.int.uit.ru / department/algorithms/distrsa. Дата обращения: 04.05.2010.
7. Cormen, T. H. Introduction to Algorithms. Second Edition / T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein. — MIT Press and McGraw-Hill, 2001. — P. 273-301.
ЕРШОВ Евгений Сергеевич, аспирант, ассистент кафедры «Автоматизированные системы обработки информации и управления».
Адрес для переписки: e-mail: eugene.ershov@mail.ru
Статья поступила в редакцию 04.06.2010 г.
Хорев, П. Б. Методы и средства защиты информации в компьютерных системах [Текст]: учеб. пособие для вузов по направлению 230100 (654600) «Информатика и вычислительная техника» / П. Б. Хорев.—4-е изд., стер.-М.: Академия, 2008.-254, [1] с.: рис., табл.-(Высшее профессиональное образование).-Библиогр.: с. 251-252.-ISBN 978-5-7695-5118-5.
Основное внимание в учебном пособии уделено программным и программно-аппаратным методам и средствам защиты информации. Рассмотрены, в частности, модели безопасности, используемые в защищенных версиях операционной системы Windows (в том числе использование функций криптографического интерфейса приложений Сгур1;оАР1) и операционных системах «клона» ишх.
i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.
Могилев, А. В. Информатика [Текст]: учеб. пособие для вузов по пед. специальностям / А. В. Могилев, Н. И. Пак, Е. К. Хеннер; под ред. Е. К. Хеннера.-7-е изд., стер.-М.: Академия, 2009.-840, [1] с.: рис., табл.-(Высшее профессиональное образование).-ISBN 978-5-7695-6342-3.
Содержатся обширные сведения по теоретическим основам информатики, программному обеспечению, языкам и методам программирования, вычислительной технике, информационным системам, компьютерным сетям и телекоммуникациям, компьютерному моделированию и социальной информатике.
Черемушкин, А. В. Криптографические протоколы. Основные свойства и уязвимости [Текст]: учеб. пособие для вузов по специальности «Компьютерная безопасность»/А. В. Черемушкин.-М.: Академия , 2009.-271, [1] с.: рис., табл.-(Высшее профессиональное образование).-Библиогр.: с. 264-270.-ISBN 978-5-7695-5748-4.
Изложены основные принципы построения криптографических протоколов, подробно описаны свойства протоколов. Рассмотрено большое число примеров, демонстрирующих типовые уязвимости и их влияние на свойства протоколов.
ОМСКИЙ НАУЧНЫЙ ВЕСТНИК №3 (93) 2010 ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ