실시간 시스템 설계를 위한 주기 할당 알고리즘 (pp.61-67)

유민수(Minsoo Ryu),홍성수(Seongsoo Hong) 한국정보과학회 2000 정보과학회논문지 : 시스템 및 이론 Vol.27 No.1

산업용 실시간 시스템에서 사용되는 디지털 제어기는 상호 작용하는 주기적 태스크들로 이루어져 있다. 이러한 태스크들은 최대 수행 주기(maximum activation periods)를 제약조건으로 가짐으로써, 요구되는 제어특성을 유지한다. 그러므로 실시간 시스템을 개발하는데 있어 필수적인 단계는 각각의 태스크에게 자원 이용률을 최소화하면서 최대 수행 조건을 만족시킬 수 있는 고정된 주기를 할당하는 것이다[1]. 각각의 태스크간의 생산자/소비자(producer/consumer)관계를 나타내주는 태스크 그래프와 자원 요구량, 그리고 주기에 대한 범위제한이 주어진다면 주기 할당 문제는 비선형 최적화 문제가 된다. 이 논문에서는 최적해의 자원이용률의 두 배를 넘지 않는 해를 찾을 수 있는 선형 수행시간의 근사 알고리즘을 제시한다. 실험 결과에서 알 수 있듯이, 제안된 알고리즘은 대부분의 경우 최적해에 매우 근접한 해를 가지게 된다. Digital controllers found in many industrial real-time systems consist of a number of interacting periodic tasks. To sustain the required control quality, these tasks possess the maximum activation periods as performance constraints. An essential step in developing a real-time system is thus to assign each of these tasks a constant period such that the maximum activation requirements are met while the system utilization is minimized [1]. Given a task graph design allowing producer/consumer relationships among tasks [2], resource demands of tasks, and range constraints on periods, the period assignment problem falls into a class of nonlinear optimization problems. This paper proposes a ploynomial time approximation algorithm which produces a solution whose utilization does not exceed twice the optimal utilization. Our experimental analysis shows that the proposed algorithm finds solutions which are very close to the optimal ones in most cases of practical interest.

실시간 시스템 설계를 위한 주기 할당 알고리즘 (pp.223-226)

유민수(Minsoo Ryu),홍성수(Seongsoo Hong) 한국정보과학회 1997 한국정보과학회 학술발표논문집 Vol.24 No.2Ⅳ

일반적으로 실시간 시스템의 시간적 특성은 시스템의 입력과 출력의 양단간에 부과되는 양극단 시간 제약으로 기술된다. 양극단 시간 제약은 각 태스크들이 취할 수 있는 주기값의 범위를 결정하는데, 이로부터 각 태스크들의 주기값을 유도할 수 있다. 이 때 주기값의 유도는 주기 조화성과 자원 이용을 고려한 목적 함수를 포함한 비선형 최적화 문제이다. 주기 유도 문제는 광범위한 해공간을 갖는 NP-hard 문제로서, 본 논문에서는 이 문제를 명확하게 정의하고 그 해법을 제시한다. 본 연구에서는 GCD 할당 정리와 출력 태스크에 적용하는 주기 조화성을 통해 선형 수행 시간을 가지는 근사(approximation) 알고리즘을 제안한다. 제시된 알고리즘은 최적해와 비교하여 자원 이용률의 측면에서 항상 1/2배 이상의 성능을 보장한다.

실시간 제약 조건의 동적 / 정적 변환을 통한 클록 동기화 문제 해결

유민수(Minsoo Ryu),홍성수(Seongsoo Hong) 한국정보과학회 1998 한국정보과학회 학술발표논문집 Vol.25 No.2Ⅲ

본 논문에서는 클록들을 주기적으로 동기화하는 분산 실시간 시스템에서 주어진 태스크의 시간 제약(timing constraint)을 변환시는 두가지 기법을 제안한다. 전형적인 이산 클록 동기화(discrete clock synchronization) 알고리즘은 클록의 값을 순간적으로 보정(correct)하여 클록의 시간이 불연속적으로 진행하게 한다. 이러한 시간상의 불연속성은 태스크의 시작제한시간(release time)이나 종료시한(deadline)과 같은 이벤트를 잃어버리거나 다시 발생시키는 오류를 범하게한다. 클록 시간의 불연속성을 피하기 위해 일반적으로 연속 클록 동기화(continuos clock synchronization) 기법이 제안되었지만 소프트웨어적으로 구현되기에는 많은 오버헤드를 유발시키는 문제점이 있다. 이에 따라 연속 클록 동기화는 PLL (Phase-Locked Loop)을 이용한 별도의 하드웨어를 사용하는 것이 보통이다. 본 논문에서는 연속 클록 동기화 기법을 사용하는 대신, 태스크의 시간 제약을 동적으로 변환시키는 DCT (Dynamic Constraint Transformation) 기법을 제안하였다. DCT는 소프트웨어적으로 구현이 가능하여 새로운 하드웨어를 필요로 하지 않으며, 이를 통해 기존의 이산적으로 동기화된 시스템에서 클록 시간의 불연속성에 의한 문제점들을 해결할 수 있다. 또 다른 문제점으로서, 클록의 물리적인 특성으로 인해 동기화된 클록들이 상한된(bounded from the above) 오차(skew)를 갖는다는 것이다. 이러한 오차는 지역 클록(local clock)에 대해 만족될 수 있는 임의의 실시간 제약 조건이 전역 클록(global clock)에 대해서는 만족되지 않을 수 있음을 의미한다. 본 논문에서는 이를 위해 먼저 두가지의 스케쥴링 가능성, 지역적 스케쥴링 가능성(local schedulability)과 전역적 스케쥴링 가능성(global schedulability)을 정의하고, 실시간 제약을 정적으로 변환시키는 SCT (Static Constraint Transformation) 기법을 제안하였다. SCT를 통해 지역적으로 스케쥴링 가능한 태스크는 전역적으로 스케쥴링이 가능하므로, 단지 지역적 스케쥴링 가능성만을 검사하면 스케쥴링 문제를 해결할 수 있도록 하였다.

통합시스템 Health Monitoring 기술 및 차량 기술 검증

유민수(Minsoo Ryu),이형철(Hyeongcheol Lee) 한국자동차공학회 2015 오토저널 Vol.37 No.9

시계 동기화 문제의 재 고찰 : 실시간 시스템을 위한 정적/동적 제약 변환 기법

유민수(Minsoo Ryu),박정근(Jungkeun Park),홍성수(Seongsoo Hong) 한국정보과학회 1999 정보과학회논문지 : 시스템 및 이론 Vol.26 No.10

본 논문에서는 분산된 클록들을 주기적으로 동기화 시키는 분산 실시간 시스템에서 시간적 제약을 만족시키기 위한 정적/동적 시간 제약(timing constraint) 변환 기법을 제안한다. 전형적인 이산클록동기화(discrete clock synchronization) 알고리즘은 클록의 값을 순간적으로 조정하여 클록의 시간이 불연속적으로 진행한다. 이러한 시간상의 불연속성은 시간적 이벤트를 잃어버리거나 다시 발생시키는 오류를 범하게 한다. 클록 시간의 불연속성을 피하기 위해 일반적으로 연속클록동기화(continuous clock synchronization) 기법이 제안되고 있지만 소프트웨어적으로 구현되면 많은 오버헤드를 유발시키는 문제점이 있다. 본 논문에서는 시간적 제약을 동적으로 변환시키는 DCT (Dynamic Constraint Transformation) 기법을 제안하였으며, 이를 통해 기존의 이산클록동기화 알고리즘을 수정하지 않고서도 클록 시간의 불연속성에 의한 문제점들을 해결할 수 있도록 하였다. 아울러 DCT에 의해 이산클록동기화 하에서 생성된 태스크 스케쥴이 연속 클록동기화에 의해 생성된 스케쥴과 동일함을 증명하여 DCT의 동작이 이론적으로 정확함을 증명하였다. 또한 분산 실시간 시스템에서 지역 클록(local clock)이 기준 클록과 완벽하게 일치하지 않아서 발생하는 스케쥴링상의 문제점을 다루었다. 이를 위해 먼저 두 가지의 스케쥴링 가능성, 지역적 스케쥴링 가능성(local schedulability)과 전역적 스케쥴링 가능성(global schedulability)을 정의하고, 이를 위해 시간적 제약을 정적으로 변환시키는 SCT (Static Constraint Transformation) 기법을 제안하였다. SCT를 통해 지역적으로 스케쥴링 가능한 태스크는 전역적으로 스케쥴링이 가능하므로, 단지 지역적 스케쥴링 가능성만을 검사하면 스케쥴링 문제를 해결할 수 있도록 하였고 이를 수학적으로 증명하였다. In this paper, we present static and dynamic constraint transformation techniques for ensuring timing requirements in a distributed real-time system possessing periodically synchronized distributed local clocks. Traditional discrete clock synchronization algorithms that adjust local clocks instantaneously yield time discontinuities. Such time discontinuities lead to the loss or the gain of events, thus raising serious run-time faults. While continuous clock synchronization is generally suggested to avoid the time discontinuity problem, it incurs too much run-time overhead to be implemented in software We propose a dynamic constraint transformation (DCT) technique which can solve the problem without modifying discrete clock synchronization algorithms. We formally prove the correctness of the DCT by showing that the DCT with discrete clock synchronization generates the same task schedule as the continuous clock synchronization. We also investigate schedulability problems that arise when imperfect local clocks arc used in distributed real-time systems. We first define two notions of schedulability, global schedulability and local schedulability, and then present a static constraint transformation (SCT) technique. The SCT ensures that it is sufficient to check the schedulability of a task locally in a node with a local clock, since the global schedulability of the task is derived from its local schedulability through SCT. We formally prove the correctness of SCT.

RTOS기반 임베디드 S/W를 위한 API 정변환/역변환기의 개발

박병률(Byeong-Ryu Park),맹지찬(Ji Chan Maeng),이종범(Jong-Bum Lee),유민수(Minsoo Ryu),안현식(Hyun-Sik Ahn),정구민(Gu-Min Jeong) 대한전기학회 2007 정보 및 제어 심포지엄 논문집 Vol.2007 No.4

임베디드 소프트웨어 결함 추적을 위한 효율적인 Record and Replay 기법 개발

김우종 ( Woojong Kim ),유민수 ( Minsoo Ryu ) 한국정보처리학회 2008 한국정보처리학회 학술대회논문집 Vol.15 No.1

임베디드 시스템이 소형화되면서도 많은 기능들이 요구됨에 따라 여기에 올라가는 임베디드 소프트웨어 역시 점점 복잡해지고 있다. 특히 멀티 쓰레드 환경에서 수행되는 임베디드 소프트웨어의 경우, 실행도중 오류가 발생했을 때 버그의 원인을 찾기가 어려울 뿐 아니라, 버그를 재현하는 것 또한 쉽지 않다. 효과적인 디버깅을 하기 위해서는 프로그램 실행 중에 버그가 발생했던 상황을 그대로 재현해야 한다. 본 논문에서는 프로그램이 실행하는 도중에 이벤트가 발생하는 시점의 이벤트정보를 record 하고, 나중에 이를 이용하여 버그가 발생한 시점으로 replay 할 수 있는 기법을 개발하였다. VPOS[1] 에 이 기법을 적용함으로써 임베디드 소프트웨어의 결함을 좀더 쉽게 탐지하여 효율적인 디버깅이 가능하도록 하였다.

효율적인 멀티홉 센서 네트워크 리프로그래밍

이승만(Seungman Lee),유민수(Minsoo Ryu) 한국정보과학회 2006 한국정보과학회 학술발표논문집 Vol.33 No.1

센서 네트워크에서의 네트워크 리프로그래밍은 무선 통신을 통해 센서 노드에서 수행되는 소프트웨어를 변경하는 것으로서, 이를 사용하면 센서 네트워크를 구성하는 수백 개 혹은 수천 개의 노드들의 소프트웨어를 효과적으로 변경시킬 수 있다. 현재 네트워크 리프로그래밍을 위해 XNP, MNP, MOAP, Deluge, Mat? 및 Incremental 기법 등이 제안되어 왔지만 아직 만족할만한 방법은 찾아보기 힘든 실정이다. 본 논문에서는 멀티홉을 지원하는 Deluge에 Incremental 기법을 통합하여 효율적인 리프로그래밍 기법을 구현하였다. 제안된 기법은 TinyOS 1.1.14 버전에 구현되었으며, 이를 통해서 네트워크 리프로그래밍을 위해 요구되는 패킷의 수와 소요시간을 크게 단축시킬 수 있다. 또한 센서 노드에서 패킷 전송에 따른 전력소모가 가장 큰 점을 고려할 때 본 연구에서 제안하는 방식을 사용하면 센서 노드의 전력소모량도 크게 감소시킬 수 있는 효과를 기대할 수 있다.

블록체인인 환경에서 합의의 확장성 개선을 위한 무효표를 활용한 비잔틴 합의 방법

정성욱(Sungwook Chung),유민수(Minsoo Ryu) 한국통신학회 2021 한국통신학회 학술대회논문집 Vol.2021 No.2

블록체인의 확장성을 향상하기 위해 다양한 방법들이 제시되고 연구되고 있으나 블록체인에서 실행되는 대부분의 동작이 합의 과정에 직간접적으로 관련되어 있어 합의 작업의 비용을 줄이지 않고서는 블록체인 확장성의 근본적 개선이 어렵다. 본 논문은 무효표를 활용한 비잔틴 합의 방법을 적용하여 블록체인 확장성 문제를 해결하는 방안을 제안한다. 비잔틴 오류 발생 노드를 비정상적인 메시지(프로토콜 규칙에 어긋나는 메시지)를 보낸 경우, 두 개 이상의 상충하는 정상적인 메시지를 보낸 경우, 특정 시간 안에 메시지를 보내지 않는 경우로 산출한다. 무효표를 활용하여 자신이 비잔틴 오류가 없다는 걸 증명하는 데 사용한다. 비잔틴 오류를 정의하여 비잔틴 오류 발생 노드를 제외하고 합의를 하여 단위 시간당 트랜잭션 처리량(TPS)과 최종성(finality)을 확보하는데 걸리는 시간이 개선됨을 확인하였다.

CNC 제어기 사례 연구를 통한 실시간 시스템 설계 기법의 평가

김남윤(Namyun Kim),유민수(Minsoo Ryu),홍성수(Seongsoo Hong),신현식(Heonshik Shin) 한국정보과학회 1998 정보과학회 컴퓨팅의 실제 논문지 Vol.4 No.1

디지털 제어기의 응용 분야가 다양해지고 복잡해짐에 따라 정확하고 자동화된 실시간 시스템 설계 기법이 요구되고 있다. 본 논문에서는 스케쥴링 지터, 센서에서 출력까지의 지연 시간, 태스크간 통신 기법, 시스템 이용률과 같은 설계 선택 사항을 바탕으로 실시간 제어 시스템에 관한 실험 결과를 제시한다. 실험의 주요 목적은 Gerber 등이 제시한 주기 할당 기법을 이용하여 생성된 실시간 시스템을 평가하고 이 방법의 문제점을 적시하는 것이다. 대상 실시간 시스템으로서 CNC(Computerized Numerical Control) 기계를 선택하였으며 제어기와 플랜트 시뮬레이터를 사실적으로 구현하였다. 본 연구는 많은 흥미로운 사실을 보여주고 있는데 실험 결과를 요약하면 다음과 같다. 첫째, 센서에서 출력까지의 평균 지연 시간은 제어 시스템의 성능을 결정하는데 가장 중요한 요소중 하나이다. 둘째, 스케쥴링 지터에 의한 영향은 평균 지연시간이 작을 때만 나타난다. 셋째, 태스크의 주기는 성능을 결정하는 중요한 요소이며 초기의 예상과는 달리, 시스템의 이용률은 성능과 직접적인 관련이 없다. 실험 결과에 대한 분석을 토대로 본 논문에서는 새로운 통신 기법과 주기 할당 기법을 제안한다. As the application areas of digital controller diversify and controlled systems become more complex, correct and automatic methodology on real-time system design is required. In this paper we describe our experiments on a real-time control system, focusing on design alternatives such as scheduling jitters, sensor-to-output latency, intertask communication schemes and the system utilization. The primary objectives of these experiments are to evaluate a real-time system design produced using the period calibration method proposed by R. Gerber and his colleagues and thus identify the limitations of the method. We choose a computerized numerical control(CNC) machine as our target real-time system and build a realistic controller and a plant simulator. This study unveils many interesting facts: (1) Average sensor-to-output latency is one of the most dominating factors in determining control quality, (2) the effect of scheduling jitter appears only when the average sensor-to-output latency is sufficiently small, and (3) loop processing periods are another dominating factor of performance. Contrary to our original expectation, the system utilization is not directly related to the performance. Based on our analysis, we propose a new communication scheme and a new obiective function for the period calibration method.