Discrete event simulation is widely used not only to predict performance but also to analyze behavior of complex systems. Real time, discrete event simulation is a means to verify a real time system in which simulation models may interact with an external environment, such as software components, hardware components or human operators. In such simulation, a simulator must handle external events from its environment in a timely manner. Simulation methodologies developed in non-interactive simulation, such as performance simulation, do not have such capabilities in event processing. This is because such methodologies employ virtual (logical) time, not real (physical) time, in event scheduling and processing.
In real time simulation, it is vital to ensure that the timing requirements of the simulation models are satisfied because the models operate based on real time and compete with one another for processor time. Scheduling feasibility analysis verifies that the component models of a target system are able to timely perform their behavior. This analysis inherently depends on an underlying computational model and a scheduling policy. Early analysis is essential because a later runtime checking is risky and costly, and besides, manual reasoning is error prone.
This thesis proposes a scheduling policy and its feasibility analysis method for the real time DEVS(RT-DEVS) models. The RT-DEVS model provides features such as object-orientation, state description of behavior, and formal semantics for executability. The event driven scheduling policy has been devised for the RT-DEVS models. The RT-DEVS models with the scheduling policy produce a set of tasks with a unique relation, for which we devised a scheduling feasibility analysis method. In order to improve the tractability of formal analysis, we decided to sacrifice the generality by assuming a periodic state sequence of a target system. The proposed analysis method consists of two phases. The first phase is state sequence analysis that verifies the periodic state sequences of the component models of a target system. The state sequence of an RT-DEVS model is affected by interactions with other RT-DEVS models. Therefore, because of the events among the RT-DEVS models, their state sequences are tightly coupled with one another. It must be confirmed that the system has a periodic state sequence by verifying the periodic state sequences of its component models. Then, the following scheduling feasibility analysis is based on their periodic timed state sequences. In the state sequence analysis, the timed state sequences of the RT-DEVS models are completed by exploiting the state and period synchronous relation among the models. The second phase is the scheduling feasibility analysis. In the scheduling feasibility analysis, the global state sequence of the target system is first obtained by the incremental composition of the timed state sets of its component models. Then, an algorithm to check on the scheduling feasibility is applied to verify that the component models of the target system are suitable for real time simulation under the developed simulation environment with the proposed event driven scheduling policy.
실시간 시뮬레이션은 시뮬레이션 도중 외부 소프트웨어, 하드웨어 또는 사용자와 상호 작용을 갖는 모델을 실시간에 기반하여 시뮬레이션하는 것이다. 운전 모의 실험, 실시간 이산 제어기 설계 검증 또는 게임 등에 적용 될 수 있으며 이를 위해서는 실시간 이산 사건 모델을 기술할 수 있는 형식론과 이렇게 기술된 모델을 실제 수행시킬 수 있는 환경이 필요하다. 이러한 실시간 시뮬레이션에서는 시뮬레이터가 모델이 행하는 입출력 사건(event)을 실시간에 맞추어 처리해 주어야한다. 기존의 성능 분석을 위해 개발된 시뮬레이션 방법은 입출력 사건 처리에 있어서 이러한 능력을 갖고 있지 않다. 왜냐하면 이러한 시뮬레이터들은 입출력 사건 처리에 있어서 실시간이 아닌 가상시간을 사용하기 때문이다. 본 논문은 실시간 시뮬레이션을 위하여 DEVS 형식론 [41] 에서 확장된 RT-DEVS 형식론 [22] 을 통해 기술된 모델을 다룬다. RT-DEVS 모델은 기존의 DEVS 모델과 유사하지만 기존의 DEVS 모델은 시간진행을 시간상의 한 점으로 표시하는 반면 RT-DEVS 모델은 이를 구간으로 표시하며 또한 이는 실제 시간을 의미한다.
본 논문에서는 실시간 시뮬레이션을 위하여 DEVS 형식론 [41] 에서 확장된 RT-DEVS 형식론 [22] 을 통해 기술된 모델의 수행 방법론을 제안하며 이를 수행시키기 위한 시뮬레이션 커널의 구조와 구현에 대하여 다룬다. 또한 실시간 시뮬레이션 도중 여러 개의 모델이 동시에 수행해야 하므로 적절한 스케줄링 방식과 이를 위한 스케쥴링 분석 기법도 다룬다. 여러 개의 모델이 실행되는 경우 모든 모델의 실시간 제약 조건을 만족시키면서 시뮬레이션을 진행시키는 것은 항상 가능한 것은 아니다. 따라서 주어진 모델이 실시간 시뮬레이션이 가능한지를 알아보는 스케줄링 가능성 분석 기법이 필요하다. 우선 시스템을 구성하는 RT-DEVS 모델의 상태 전이 그래프를 얻고 이렇게 얻어진 상태 전이 그래프를 합성하여 전체 시스템의 상태 전이 그래프를 얻는다. 이것은 전체 시스템이 실시간 시뮬레이션이 가능한지 분석하기 위한 스케쥴 테스트 그래프로 사용될수 있다. 스케줄 가능성 분석을 마친 시뮬레이션 모델들은 실시간 시뮬레이션 환경 하에서 시뮬레이션이 가능하다.
