삼중구조 실시간 시스템에서 태스크의 최적 체크 포인트 구간 결정

곽성우(Seong Woo Kwak),양정민(Jung-Min Yang) 한국지능시스템학회 2021 한국지능시스템학회논문지 Vol.31 No.2

여분의 프로세서를 두 개 더 가지는 삼중구조 시스템은 하나의 프로세서에서 고장이 발생하더라도 주어진 임무를 수행할 수 있다. 본 연구에서는 삼중구조 시스템에 체크포인트 기법을 도입하여 고장을 탐지하고 복구하는 새로운 고장 극복 방법을 제안한다. 제안된 방법에서는 한 프로세서에 고장이 발생하면 고장 탐지와 동시에 세 프로세서의 상태를 동기화하여 고장을 복구하도록 한다. 두 개 이상 프로세서에서 고장이 발생하면 시스템이 직전 체크포인트로 회귀하여 태스크를 재실행함으로써 고장을 복구한다. 본 논문에서는 태스크가 데드라인(deadline) 이내에서 성공적으로 수행될 확률을 최대화하는 체크포인트 구간의 선정 방법을 제안한다. 제안된 방식을 탑재한 삼중구조 시스템에 대한 마코프 체인 모델을 개발하고 실시간 태스크가 데드라인이내에 수행을 끝내는 확률을 도출한다. 모의실험을 통하여 최적의 체크포인트 구간을 결정하는 과정을 제시한다. By virtue of surplus components, the triple modular redundancy (TMR) system can continue its mission even when one processor is attacked by faults. In this paper, we propose a new fault tolerance strategy by introducing checkpoint placement into the TMR system. In the proposed scheme, faults in one processor are tolerated by synchronizing the state of three processors. More than one processors faults are tolerated by rollback and re-executing a task from the latest checkpoint. We propose a checkpoint management method maximizing the probability of task completion within the deadline. We develop the Markov model for the TMR system with the proposed checkpoint scheme, and derive the optimal checkpoint interval.

확률 최적화를 이용한 비선점형 Rate Monotonic 스케줄링의 체크포인트 구간 결정

곽성우(Seong Woo Kwak),양정민(Jung-Min Yang) 한국지능시스템학회 2011 한국지능시스템학회논문지 Vol.21 No.1

체크포인트 기법은 실시간 시스템의 내고장성을 구현하는 대표적인 방법이다. 본 논문에서는 확률 최적화를 이용하여 체크 포인트 구간을 결정하는 기법을 제시한다. 본 논문에서 다루는 실시간 시스템은 멀티 태스크(multi-task)들로 구성되며 Poisson 분포를 가지는 과도 고장이 발생한다. 또 멀티 태스크들은 비선점형 Rate Monotonic 알고리듬으로 스케줄링된다. 이번 연구에서는 멀티 태스크들의 수행 성공 확률을 체크포인트 삽입 개수로 표현하는 최적화 문제를 설정하고 이 확률값을 최대로 만드는 체크포인트 개수와 구간 길이를 구한다. 제안된 확률 계산 과정은 체크포인트 재수행 횟수에 대한 비선점형 RM 알고리듬의 스케줄링 가능성을 판별하는 방법도 포함한다. 사례 연구를 통해서 제안된 기법의 적용가능성을 입증한다. Checkpointing is one of common methods of realizing fault-tolerance for real-time systems. This paper presents a scheme to determine checkpoint intervals using probabilistic optimization. The considered real-time systems comprises multiple tasks in which transient faults can happen with a Poisson distribution. Also, multi-tasks are scheduled by the non-preemptive Rate Monotonic (RM) algorithm. In this paper, we present an optimization problem where the probability of task completion is described by checkpoint numbers. The solution to this problem is the optimal set of checkpoint numbers and intervals that maximize the probability. The probability computation includes schedulability test for the non-preemptive RM algorithm with respect to given numbers of checkpoint re-execution. A case study is given to show the applicability of the proposed scheme.

이동 기기에 적합한 소프트웨어 에이전트 기반의 효율적 체크포인팅 기법

임성채,Lim, Sung-Chae 한국정보처리학회 2008 정보처리학회논문지 A Vol.15 No.2

이동 통신 시스템의 발전과 함께 여러 대의 이동 기기에서 동작하는 분산 응용의 필요성이 점차 커지고 있다. 모바일 기기의 고장이나 통신망 단절이 기존 고정 통신망에 비해 자주 발생하는 환경을 고려할 때 모바일 응용을 위한 복구 기법이 매우 중요하며, 중단된 응용의 재시작을위해 체크포인팅이 널리 사용되고 있다. 본 논문에서도 이런 분산 응용의 복구를 위한 효율적 체크포인팅 기법을 제안한다. 제안된 기법에서는 MSS(Mobile Support Station)에서 동작하는 체크포인팅 에이전트라는 소프트웨어 에이전트를 사용한다. 이 에이전트는 R-distance(rollback-distance) 개념을 지원하며, 이를 통해 복귀되는 지역 체크포인트의 최대 개수를 한정할 수 있다. 제안된 방식은 기존의 문제점이었던 도미노 현상이나 체크포인트 유지에 필요한 추가 비용을 크게 줄이면서도 매우 유연한 방식의 체크포인트 생성을 지원할 수 있다. With the advance in mobile communication systems, the need for distributed applications running on multiple mobile devices also grows gradually. As such applications are subject to H/W failures of the mobile device or communication disruptions, compared to the traditional applications in fixed networks, it is crucial to develop any recovery mechanism suitable for them. For this, checkpointing is widely used to restart interrupted applications. In this paper, we devise an efficient checkpointing method that adopts the software agent executed at the mobile support station. The agent, called the checkpointing agent, is aimed at supporting the concept of rollback-distance (R-distance) that bounds the maximum number of roll-backed local checkpoints. By means of the R-distance, our method can prevent undesirable domino effects and heavy checkpoint overhead, while providing high flexibility in checkpoint creation.

멀티 태스크를 가진 실시간 시스템에서 체크포인트를 이용한 과도고장 극복

곽성우(Seong Woo Kwak),양정민(Jung-Min Yang) 한국지능시스템학회 2010 한국지능시스템학회 학술발표 논문집 Vol.20 No.2

본 논문에서는 주기적 멀티 태스크를 가진 실시간 시스템에 대한 최적의 체크포인트 삽입 방법을 제안한다. 실시간 태스크들은 Rate Monotonic 알고리듬으로 스케줄링되며 과도 고장에 의해 영향을 받는다. 제안하는 기법은 고장 환경 하에서 태스크들이 성공적으로 수행 완료될 확률을 최대화하는 체크포인트 구간 길이를 결정하는 것이다. 본 논문에서는 특히 각 태스크의 데드라인이 주기보다 큰 일반적인 경우를 다룬다. 데드라인이 주기보다 작거나 같은 특수한 상황에 비해서 RM 알고리듬의 스케줄링 가능성을 테스트하는 방법과 태스크들의 수행 성공 확률식은 더 복잡하게 유도된다. 사례 연구를 통해서 제안된 기법의 적용가능성을 입증한다.

공간 메인 메모리 DBMS를 위한 효율적인 회복 시스템

김정준,주성완,강홍구,홍동숙,한기준,Kim, Joung-Joon,Ju, Sung-Wan,Kang, Hong-Koo,Hong, Dong-Sook,Han, Ki-Joon 한국공간정보시스템학회 2006 한국공간정보시스템학회 논문지 Vol.8 No.3

최근 실시간 서비스의 요구 사항을 갖는 위치 기반 서비스(Location Based Service : LBS)와 텔레매틱스(Telematics) 서비스를 효율적으로 제공하기 위해서 공간 메인 메모리 DBMS에 대한 관심이 급증하고 있다. 이러한 공간 메인 메모리 DBMS에서는 시스템 장애가 발생하였을 경우 메인 메모리상의 모든 공간 데이타를 잃어버릴 수 있으므로 데이타베이스의 안정성을 위한 회복 시스템은 매우 중요하다. 회복 시스템에서 로그와 체크포인트 수행 과정 중 발생하는 디스크 입출력은 전체 시스템 성능을 저하하는 중요한 요인이 되고 있다. 그러므로, 공간 메인 메모리 DBMS에서 디스크 입출력을 줄일 수 있는 효율적인 회복 시스템에 대한 연구가 절실히 필요하다. 본 논문에서는 공간 메인 메모리 DBMS를 위한 효율적인 회복 시스템에 대해서 연구하였다. 먼저 로그 기법으로는 디스크 입출력을 줄이고 트랜잭션의 동시성 향상을 위해 사전 완료 기법을 사용하였고, 전체 시스템 성능을 향상시키기 위해 기존의 퍼지-핑퐁 체크포인트 기법에서 발생하는 동일 페이지에 대한 중복 디스크 입출력 문제를 해결한 퍼지-쉐도우 체크포인트 기법을 제안하여 회복 시스템 구현 시 사용하였다. 그리고 마지막으로 본 논문에서 개발한 회복 시스템의 성능 평가를 수행하여 효율성을 입증하였다. Recently, to efficiently support the real-time requirements of LBS and Telematics services, interest in the spatial main memory DBMS is rising. In the spatial main memory DBMS, because all spatial data can be lost when the system failure happens, the recovery system is very important for the stability of the database. Especially, disk I/O in executing the log and the checkpoint becomes the bottleneck of letting down the total system performance. Therefore, it is urgently necessary to research about the recovery system to reduce disk I/O in the spatial main memory DBMS. In this paper, we study an efficient recovery system for the spatial main memory DBMS. First, the pre-commit log method is used for the decrement of disk I/O and the improvement of transaction concurrency. In addition, we propose the fuzzy-shadow checkpoint method for the recovery system of the spatial main memory DBMS. This method can solve the problem of duplicated disk I/O on the same page of the existing fuzzy-pingpong checkpoint method for the improvement of the whole system performance. Finally, we also report the experimental results confirming the benefit of the proposed recovery system.

소프트 데드라인을 가지는 실시간 태스크에서의 체크포인터 삽입 방법

곽성우(Seong-Woo Kwak),양정민(Jung-Min Yang) 한국지능시스템학회 2011 한국지능시스템학회 학술발표 논문집 Vol.21 No.1

본 논문에서는 주기보다 긴 데드라인을 가지는 실시간 태스크에 대한 체크포인트 배치 기법을 제안한다. 과도고장의 영향을 받는 실시간 시스템에서 멀티 태스크들은 Rate Monotonic 알고리듬으로 스케줄링된다. 제안하는 기법은 고장 환경 하에서 멀티 태스크가 성공적으로 수행 완료될 확률을 최대화하는 체크포인트 구간 길이를 결정하는 것이다. 데드라인이 주기보다 긴 경우 RM 알고리듬의 스케줄링 가능성을 테스트하는 방법과 멀티 태스크의 수행 성공 확률 식은 데드라인이 주기와 동일한 경우보다 더 복잡하게 유도된다. 사례 연구를 통해서 제안된 기법의 적용가능성을 입증한다.

소프트웨어 공학 : 불확실성 및 가변성 환경의 신뢰성 향상을 위한 체크리스트 설계

이은서 ( Eun Ser Lee ) 한국정보처리학회 2014 정보처리학회논문지. 소프트웨어 및 데이터 공학 Vol.3 No.10

프로젝트 수행은 많은 결함을 내포하고 있다. 특히 유사한 분야의 프로젝트 수행 경험이 없다면 결함은 전체 시스템에 많은 영향을 주게 된다. 따라서 이와 같은 결함은 프로젝트의 성공 여부를 판단할 수 있는 중요한 요소가 된다. 결국 효율적인 위험관리는 문제에 쉽게 대처할 수 있게 해주며, 예상하지 못한 품질, 예산초과 및 일정 지연이 되지 않도록 해준다. 본 연구에서는 소프트웨어 개발 시, 프로세스의 신뢰성 향상을 위하여 체크포인트를 제시하고 이를 활용하여 전체 시스템의 신뢰성을 향상하고자 한다. There are many defects when we`re working on a project. Especially, if we don`t have experience in similar field, defects have a strong influence on the system entirely. Therefore, management of risk such like defects is important the factor for success of project. Finally, efficient management of risk can guarantee handling problems such like fault tolerancy, unexpected quality and delay of schedule. In this paper, we propose checkpoint for improvement of reliability and are willing to improve the reliability of an entire system using it.

모바일 그리드에서 체크포인트 기반 작업 이주 기법

정대용 ( Dae Yong Jung ),서태원 ( Tae Weon Suh ),정광식 ( Kwang Sik Chung ),유헌창 ( Heon Chang Yu ) 한국컴퓨터교육학회 2009 컴퓨터교육학회 논문지 Vol.12 No.4

무선 센서 네트워크에서 신뢰성 향상을 위한 효율적인 체크포인트 프로토콜

정동원,최창열,김성수,Jung, Dong-Won,Choi, Chang-Yeol,Kim, Sung-Soo 한국정보처리학회 2006 정보처리학회논문지 C : 정보통신,정보보안 Vol.13 No.5

유비쿼터스 환경에서 정확한 데이터를 얻기 위해, 무선 센서 네트워크의 신뢰성은 필수적이다. 이것을 위해, 롤백 기술을 통한 자가 치유는 신뢰성 향상에 도움을 준다. 하지만, 로컬 시스템만을 고려한 기존 롤백 기술은 무선 센서 네트워크에서 자칫 전체 시스템 차원의 결함을 발생시킨다. 따라서, 롤백 기술을 무선 네트워크 차원으로 지원하기 위해 체크포인트 프로토콜이 제시되었다. 하지만, 무선 센서 네트워크가 가지고 있는 특유의 제한 조건 때문에 각각의 프로토콜들은 메모리, 성능, 그리고 전력 소모 효율에 있어서 상충관계가 존재한다. 따라서, 본 논문에서는 주소 기록 기반 프로토콜(address log based protocol, ALBP)이라 불리는 새로운 프로토콜을 제시한다. 이 기법은 비동기 방식을 지원하는 플랫폼 기반의 프로토콜로, 무선 센서 네트워크에서 중요한 고려사항인 전력 소모량, 메모리 사용량, 그리고 마감시간을 맞추기 위한 빠른 응답시간을 만족시킬 수 있다. The reliability concept of wireless sensor network is essential to get exactly actual data from the ubiquitous environment. A rollback technique for the self-healing helps to increase it. However, a fault can occur in wireless sensor network when to use a previous rollback technique because it is designed just for the local system. So, checkpoint protocols are suggested in order to use a rollback technique in the network without the fault. However, there is trade-off among performance overhead, power consumption, and memory overhead for each of protocols. Hence, we suggest a novel global checkpoint protocol, so called address log based protocol(ALBP), based on an asynchronous protocol. It is a platform based protocol to reduce power consumption, performance overhead, and memory overhead which are the most of consideration in wireless sensor network.

모바일 메인메모리 데이터베이스 회복 시스템 개선

이광근 사단법인 인문사회과학기술융합학회 2016 예술인문사회융합멀티미디어논문지 Vol.6 No.4

Recently, due to supply of smart phone and mobile devices, the research for a transaction model has been actively progress to deal with real-time transaction processing. The mobile recovery methods for database stability is very important because on the mobile main memory database system, the data loss will occur when passed the boundary between cells. In the mobile main memory recovery method, system performance could reduced by input and output for record the execution of the programs. So, the research for efficient recovery methods are truly required Logging and check-point effective recovery method to reduce input and output of mobile main memory database systems. In this paper, by using T- tree index methods and log directories to carried out the recovery by the mobile site and received the hand-over remove the overhead of the recovery time. This new method is called T-tree Index Log Directory: TILD, and the recovery is applied by it. And the efficiency was proved by test of the proposed recovery systems. 최근 스마트폰 및 모바일 기기의 대중화로 인하여 실시간 트랜잭션 모델에 관한 연구가 활발히 진행되고 있다. 이러한 모바일 메인메모리 데이터베이스시스템에서는 셀과 셀 사이 서비스 공간 이동시 통화가 단절되는 현상이 나타날 경우 데이터의 손실이 발생할 수 있으므로 데이터베이스의 안정성을 위하여 회복기법은 매우 중요하다. 모바일 메인메모리 회복기법에서는 프로그램의 실행 상태를 기록하기 위하여 발생하는 입출력으로 인하여 시스템의 성능이 저하될 수 있다. 그로 인하여 모바일 메인메모리 데이터베이스시스템에서는 로깅과 체크포인트로 인하여 발생되는 입출력을 줄일 수 있는 효율적인 회복기법에 대한 연구가 요구된다. 본 연구에서는 T-트리 인덱스 기법과 로그 디렉터리를 이용하여 통화가 단절되는 현상이 발생한 모바일 사이트별로 회복을 수행함으로써 회복시간의 오버헤드를 제거하였다. 이 제안된 기법을 T-트리 인덱스 로그 디렉터리(T-tree Index Log Directory: TILD) 기법이라 하며, 이 기법을 이용하여 성능 평가를 수행하여 효율성을 입증하였다.