An Efficient Merging Algorithm for Recovery and Garbage Collection in Incremental Checkpointing

허준영,이상호,홍지만,조유근 朝鮮大學校 電子情報通信硏究所 2003 電子情報通信硏究所論文誌 Vol.6 No.2

Incremental checkpointing saves only the modified pages of the checkpoint using page write-protection. While on the one hand, the checkpointing overhead is decreased when incremental checkpointing is used, old checkpoints cannot be merged and deleted because the process' memory pages become spread out over many incremental checkpoints. In this paper, we present an efficient merging algorithm for the recovery and garbage collection in incremental checkpointing. The proposed algorithm can merge several incremental checkpoints into a full checkpoint for recovery and can delete unnecessary incremental checkpoints.

Optimal Checkpoint Times for a Computer System with Hardware and Software Failures

Kenichiro Naruse,Toshio Nakagawa 대한산업공학회 2015 대한산업공학회 추계학술대회논문집 Vol.2015 No.11

Tasks with random processing times of a computer system are executed successively. Checkpoint methods can be placed at the end of tasks. Two types of checkpoints are called Journal Checkpoint (JC) and Flush Checkpoint (FC) where JC needs a small time compared with FC to store checkpoint data, and FC needs a long time compared with JC to store checkpoint data. The problem is that in what places we set suitable checkpoints. The mean execution times per one task are obtained and optimal numbers which minimize them are derived analytically and numerically.

RM 스케줄링된 실시간 태스크에서의 최적 체크 포인터 구간 선정

郭成祐(Seong-Woo Kwak),鄭容朱(Young-Joo Jung) 대한전기학회 2007 전기학회논문지 Vol.56 No.6

For a system with multiple real-time tasks of different deadlines, it is very difficult to find the optimal checkpoint interval because of the complexity in considering the scheduling of tasks. In this paper, we determine the optimal checkpoint interval for multiple real-time tasks that are scheduled by RM(Rate Monotonic) algorithm. Faults are assumed to occur with Poisson distribution. Checkpoints are inserted in the execution of task with equal distance in the same task, but different distances in other tasks. When faults occur, rollback to the latest checkpoint and re-execute task after the checkpoint. We derive the equation of maximum slack time for each task, and determine the number of re-executable checkpoint intervals for fault recovery. The equation to check the schedulibility of tasks is also derived. Based on these equations, we find the probability of all tasks executed within their deadlines successfully. Checkpoint intervals which make the probability maximum is the optimal.

안정 저장장치의 효율적 사용을 위한 페이지 기반 점진적 검사점 기법

허준영(Junyoung Heo),이상호(Sangho Yi),구본철(Boncheol Gu),조유근(Yookun Cho),홍지만(Jiman Hong) 한국정보과학회 2007 정보과학회논문지 : 시스템 및 이론 Vol.34 No.11·12

페이지 기반 점진적 검사점은 검사점 오버헤드를 줄이기 위해 프로세스의 메모리 상태 중 변경된 페이지만 저장하는 기법이다. 그러나 점진적 검사점의 누적 크기는 검사점 횟수가 증가함에 따라 서서히 증가하게 된다. 이는 한 페이지가 검사점 작성 이후에 변경되어 검사점 작성시에 검사점에 저장되는 과정이 되풀이 되고, 이후에 삭제되지 않기 때문이다. 복구 시에 프로세스의 저장된 상태를 만들기 위해 검사점들이 모두 필요할 수 있으므로 함부로 검사점을 삭제를 할 수 없다. 본 논문에서는 페이지 기반 검사점 도구인 Pickpt를 소개하고, Pickpt가 검사점의 누적 크기 증가 문제를 해결하는 방법을 설명한다. 실험을 통해 기존 점진적 검사점에 비해 Pickpt가 점진적 검사점의 누적 크기를 현저히 줄임을 보였다. Incremental checkpointing, which is intended to minimize checkpointing overhead, saves only the modified pages of a process. However, the cumulative size of incremental checkpoints increases at a steady rate over time because a number of updated values may be saved for the same page. In this paper, we present a comprehensive overview of Pickpt, a page-level incremental checkpointing facility. Pickpt provides space-efficient techniques aiming to minimizing the use of disk space. For our experiments, the results showed that the use of disk space using Pickpt was significantly reduced, compared with existing incremental checkpointing.

Functional Analysis of the Putative BUB2 Homologues of C. elegans in the Spindle Position Checkpoint

Lee, Kyung-Hee,Song, Ki-Won The Korean Society for Integrative Biology 2005 Integrative biosciences Vol.9 No.2

Spindle position checkpoint monitors the orientation of mitotic spindle for proper segregation of replicated chromosomes into mother cell and the daughter, and prohibits mitotic exit when mitotic spindle is misaligned. BUB2 forms one of the key upstream element of spindle position checkpoint in budding yeast, but its functional homologues have not been identified in higher eukaryotes. Here, we analyzed the functions of two putative BUB2 homologues of C. elegans in the spindle orientation checkpoint. From the C. elegans genome database, we found that two open reading frames (ORFs), F35H12_2 and C33F10_2, showed high sequence homology with BUB2. We obtained the expressed sequence tag (EST) clones for F35H12_2 (yk221d4) and C33F10_2 (yk14e10) and verified the full cDNA for each ORF by sequencing and 5' RACE with SL1 primer. The functional complementation assays of yk221d4 and yk14e10 in ${\Delta}bub2$ of S. cerevisiae revealed that these putative BUB2 homologues of C. elegans could not replace the function of BUB2 in spindle position checkpoint and mitotic exit. Our attempt to document the component of spindle position checkpoint in metazoans using sequence homology was not successful. This suggests that structural information about its components might be required to identify functional homologues of the spindle position checkpoint in higher eukaryotes.

Impaired Spindle Checkpoint Response of Brca1-deficient Mouse Embryonic Fibroblasts (MEFs) to Nocodazole Treatment

김명애,김현주,윤진호,Kim Myoung-Ae,Kim Hyunju,Yun Jeanho Korean Society of Life Science 2006 생명과학회지 Vol.16 No.1

항암유전자 Brca1의 변이는 유방암 및 난소암에 대한 감수성을 증가시키며, Brca1은 DNA손상신호후 세포주기 조절에 필수적인 역할을 한다. 연구결과, Brca1이 세포주기 S기와 G2/M 조절점에서 중요한 역할을 담당함이 밝혀졌다. 그러나, Brca1의 spindle checkpoint 관여여부는 알려져 있지 않다. 본 연구에서는 spindle checkpoint를 활성화시키는 nocodazole를 처리하여 야생형, $p53^{-/-}$ 그리고 $p53^{-/-}\;Brca1^{-/-}$ 세포주의 세포주기 변화를 조사하였다. 야생형과 $p53^{-/-}$ 세포주는 신속한 mitosis기 정지가 나타난 반면, $p53^{-/-}\;Brca1^{-/-}$ 세포주의 경우 모든 세포가 M기에서 정지하지 않았다. Double-thymidine block 기법에 의한 세포주기 동조화후 nocodazole 처리시에도 $p53^{-/-}\;Brca1^{-/-}$ 세포주에서는 일부세포가 M기 조절점을 통과하여 계속 G1기로 진행하였다. 형태학적 분석에서도 nocodazole 함유배지에서 계속 증식하는 세포형태가 관찰되었다. 이와 같은 결과들은 Brca1이 spindle checkpoint가 정상적으로 작동하는데 중요한 역할을 담당한다는 것을 의미하고 있다. Genetic alternation of Brca1 predispose of breast and ovarian cancer. Brca1 plays critical role in cell cycle regulation following DNA damage. Previous studies revealed that Brca1 plays an important role in S phase and G2/M checkpoint regulation. However, whether Brca1 involves in spindle checkpoint is unclear. In this study, the role of Brca1 in cell cycle response following nocodazole, which is a reagent that depolymerizes microtubules and activates the spindle checkpoint, has been examined using wild type $p53^{-/-}\;and\;p53^{-/-}Brca1^{-/-}$ mouse embryonic fibroblasts (MEFs). While wild type and Brca1-proficient MEFs showed an acute mitotic arrest, Brca1-deficient MEFs failed to arrest at mitotic phase in response to nocodazole treatment. In double-thymidine block and nocodazole treatment experiment, a portion of $p53^{-/-}\;Brca1^{-/-}$ MEFs were clearly by-passed nocodazole induced mitotic arrest. Consistent with this, in morphologic analysis, $p53^{-/-}\;Brca1^{-/-}$ MEFs showed growing cell morphology after nocodazole treatment. Taken together, these results suggest that Brca1 protein is an important component for normal induction of spindlecheckpoint and impairment of Brca1 function could induce dysregulation of mitotic cell cycle that ultimately results in genomic instability.

Vehicular datacenter modeling for cloud computing: Considering capacity and leave rate of vehicles

Kim, Taesik,Min, Hong,Jung, Jinman North-Holland 2018 Future generations computer systems Vol.88 No.-

<P><B>Abstract</B></P> <P>In this paper, we propose a vehicular datacenter model in a parking lot, where vehicles can be considered as a resource for cloud computing. One of the crucial issues facing the vehicular datacenter is failures caused by arrival and departure of dynamic resources. These failures result in performance degradation of the execution time because the task must be restarted. In order to reduce execution time and mitigate the effects of uncertainty, we propose a vehicular datacenter model that makes use of a checkpoint mechanism. We first characterize the dynamic vehicles in parking lots considering each vehicle’s capacity and leave rate. We derive the expected execution time to analyze the characteristics of vehicles and propose a resource selection strategy based on that time. We also derive the optimal number of checkpoints for each vehicle that maximizes the efficiency of the checkpoint. We demonstrate the results of our analysis through various evaluations.</P> <P><B>Highlights</B></P> <P> <UL> <LI> We propose a vehicular datacenter model that makes use of a checkpoint mechanism. </LI> <LI> We characterize the vehicles in parking lots considering its capacity and leave rate. </LI> <LI> We propose a resource selection strategy based on the expected execution time. </LI> <LI> We optimize the number of checkpoints that maximizes the efficiency of the checkpoint. </LI> </UL> </P>

삼중구조 시스템의 실시간 태스크 최적 체크포인터 및 분산 고장 탐지 구간 선정

곽성우(Seong Woo Kwak),양정민(Jung-Min Yang) 한국전자통신학회 2023 한국전자통신학회 논문지 Vol.18 No.3

삼중구조 시스템에서는 하나의 프로세서에서 고장이 발생해도 여유도 때문에 주어진 임무를 계속 수행할 수 있다. 본 연구에서는 삼중구조 시스템에 체크포인터 기법을 도입한 후 고장 탐지와 체크포인터를 분리하는 새로운 고장 극복 방법을 제안한다. 먼저 한 개 프로세서에서 고장이 발생하면 고장 탐지와 동시에 모든 프로세서의 상태를 동기화함으로써 고장을 복구한다. 또한 두 개 이상의 프로세서에서 동시에 고장이 발생하면 직전의 체크포인터로 회귀하여 태스크를 재실행함으로써 고장을 복구한다. 본 논문에서는 태스크가 데드라인 이내에서 성공적으로 수행될 확률을 최대화하는 고장 탐지 구간과 체크포인터 구간의 선정 방법을 제안한다. 제안된 방식을 탑재한 삼중구조 시스템을 마코프 체인으로 모델링하고 실시간 태스크의 성공적 수행 확률을 도출하는 모의실험을 수행하여 최적의 해를 구하는 과정을 제시한다. Triple modular redundancy (TMR) systems can continue their mission by virtue of their structural redundancy even if one processor is attacked by faults. In this paper, we propose a new fault tolerance strategy by introducing checkpoints into the TMR system in which data saving and fault detection processes are separated while they corporate together in the conventional checkpoints. Faults in one processor are tolerated by synchronizing the state of three processors upon detecting faults. Simultaneous faults occurring to more than one processor are tolerated by re-executing the task from the latest checkpoint. We propose the checkpoint placement and fault detection strategy to maximize the probability of successful execution of a task within the given deadline. We develop the Markov chain model for the TMR system having the proposed checkpoint strategy, and derive the optimal fault detection and checkpoint interval.

분산 고장 탐지 방식을 이용한 실시간 태스크에서의 최적 체크포인터 구간 선정

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

체크포인터를 삽입한 실시간 시스템에서는 고장이 발생하면 고장 직전의 체크포인터로 회귀하여 태스크를 재실행함으로써 과도 고장을 효과적으로 극복할 수 있다. 이번 논문에서는 체크포인터에서 실행되는 데이터 저장과 고장 탐지 과정을 분리한 새로운 체크포인터 방식을 제안한다. 하나의 체크포인터 구간 내에 여러 개의 고장 탐지 과정을 추가하면 고장 발생에서 탐지까지의 지연 시간을 줄일 수 있다. 본 논문에서는 태스크가 데드라인 이내에서 성공적으로 수행될 확률을 최대화하는 고장 탐지 과정의 삽입 방법을 제안한다. 고장 탐지 과정이 분리된 체크포인터 방식을 마코프 체인으로 모델링하고 실시간 태스크의 성공적 수행 확률을 계산하는 모의실험을 수행하여 최적의 해를 구하는 과정을 제시한다. Checkpoint placement is an effective fault tolerance technique against transient faults in which the task is re-executed from the latest checkpoint when a fault is detected. In this paper, we propose a new checkpoint placement strategy separating data saving and fault detection processes that are performed together in conventional checkpoints. Several fault detection processes are performed in one checkpoint interval in order to decrease the latency between the occurrence and detection of faults. We address the placement method of fault detection processes to maximize the probability of successful execution of a task within the given deadline. We develop the Markov chain model for a real-time task having the proposed checkpoints, and derive the optimal fault detection and checkpoint interval.

Saccharomyces cerevisiae에서 세포주기의 진행과 조절에 관련된 변이주들의 분리 및 특성화

박정은,임선희,선우양일 한국미생물학회 2001 미생물학회지 Vol.37 No.1

본 연구에서는 세포주기의 Gl/S기에 관련된 유전자의 작용기작을 이해하기 위하여 출아효모인 Saccharomyces cerevisiae를 사용하여 세포주기 진행 및 조절에 관련된 변이주를 분 리하여 특성화하는 연구를 수행하였다. 먼저 새로운 변이주를 분리하기 위해서 HeLa 세포와 출아효모에서 Gl을 유발하는 CPO(ciclopirox olamine) 약제에 대해 감수성을 보이는 변이주를 선별하였다. 그 결과, 총 31개의 CPO에 대한 감수성 변이주들이 분리되었고, ciclopirox olamine sensitivity의 첫 글자를 따서 con mutants라 명명하였다. cos 변이주들의 표현형의 특성을 결정하기 위해 MMS(methylmethane sulfonate)와 HU(hydrsxyurea)에 대한 감수성을 조사하여 그 성질에 따라 4개의 group으로 나누었다. Group I에는 cos27, cos28, cos32, cos33, cos36, cos37, cos40, cos42, cos46, cos50, cos52, cos53 변이주가 포함되고, 이들은 MMS와 HU 두 약제 모두에 대해서 감수성을 보여 S기 checkpoint에 관련된 것으로 보이고, Group II는 cos43, cos48 변이주로 MMS에 대해서 감수성을 지녀 G1기 또는 G2기 checkpoint에 관련된 것으로 추측된다. Group III 변이주에는 cos35, cos47, cos54, cos55, cos56이 포함되고 HU에 대해서 감수성을 보여 S기에 관련된다고 보여지며, Group IV 변이 주는 cos29, cos30, cos31, cos34, cos38, cos39, cos41, cos44, cos45, cos49, cos51, cos57로서 단지 CPO에 대해서만 감수성을 나타냈다. 더욱이 변이주의 최종표현형을 형광현미경을 이용하여 조사하여, S기 checkpoint에 관련된 것으로 보이는 cos37 변이주를 확인하였다. 또한, 변이주와 야생주의 이형접합체인 이배체를 만들어 변이주의 유전학적 분석을 수행하였다. These studies were carried out to understand the mechanisms of genes which are related in cell cycle progression at G1/S phase. Mutants involved in cell cycle progression and regulation in Saccharomyces cerevisiae were isolated and characterized. To isolate new mutants, we screened the sensitivity to ciclopirox olamine (CPO) which inhibits the cell cycle traverse at or very near the G1/S phase boundary in HeLa cell and budding yeast. As results, we isolated 30 mutants and named cos(ciclopirox olamine sensitivity: cos27∼cos57) mutants. To determine the phenotype of mutants, we examined the sensitivity to methyl-methane sulfonate (MMS) and hydroxyurea (HU). Several mutants were sensitive to MMS and HU. According to these Phenotypes, cos mutants were grouped into four. Group I mutants are cos27, cos28, cos32, cos33, cos36, cos37, cos40, cos42, cos46, cos50, cos52 and cos53 which show MMS, HU sensitivities and might act at a checkpoint pathway during S phase. Group II mutants are cos43 and cos48 which show MMS sensitivities and might act at a checkpoint pathway during Gl or G2 phase. Group III mutants are cos35, cos47, cos54, cos55 and cos56 which show HU sensitivities and might act at a progress pathway during S phase. Finally, Group IV mutants are cos29, cos30, cos31, cos34, cos38, cos39, cos41, cos44, cos45, cos49, cos51 and cos57 which show only CPO sensitivities. Moreover, we examined the terminal phenotype of mutants under fluorescent microscope and then found one of S phase checkpoint related mutant(cos37). Furthermore, we constructed the heterozygote strain between mutant and wild type haploid strains to study their genetic analysis of cos mutants.