상호 협동적 잠금 규약을 이용한 B link-트리 동시성 제어 기법

임성채,이윤준,김명호(Sung-Chae Lim),Yoon Joon Lee,Myoung Ho Kim 한국정보과학회 1997 정보과학회논문지(B) Vol.24 No.2

B-트리의 동시성을 높이기 위한 연구중에서 B^(link)-트리를 이용한 동시성 제어 기법이 많은 관심을 받아왔다. B^(link)-트리를 이용하는 기법은 다른 알고리즘과 비교하여 제공하는 동시성의 정도가 매우 높은 특성을 보이는 반면 키 삭제자의 트리 재구성 동작이 지원되지 않았던 문제가 있었다. 본 논문에서는 기존 B^(link)-트리를 이용한 알고리즘이 갖는 정도의 동시성을 보장하는 동시에 삭제자의 트리 재구성 동작을 허용하는 새로운 B^(link)-트리 동시성 제어 기법을 소개한다. 논문에서는 효과적인 B^(link)-트리 동시성 제어를 위해 상호 협동적인 잠금규약과 트리 재구성을 위한 노드 갱신 규칙을 이용한다. 제안되는 기법에서는 트리 재구성 작업이 다른 프로세스의 탐색 연산과 함께 진행될 수 있으며 알고리즘 수행중에 교착상태가 발생하지 않는다. For the purpose of improving B-tree concurrency, a number of algorithms have been proposed Among the previous works, the algorithms based on B^(link)-tree draw much attention, While such B^(link)-tree algorithms, in general, guarantee higher concurrency than others that do not use B^(link)-tree, they do not provide an efficient mechanism to reconstruct underflowed nodes. In this paper we present a new concurrency control method based on B^(link)-tree that provides high concurrency and an efficient reconstruction mechanism. A new locking protocol, called cooperative locking protocol, and a node modification rule for tree reconstruction are main contributions. In the proposed method, the tree reconstruction operations can concurrently proceed with search operations and any concurrent operations never result in deadlock.

연속매체 재연에 적합한 스케줄링 주기 확장을 허용하는 동적 Sweep 기법

임성채,Lim, Sung-Chae 한국정보처리학회 2005 정보처리학회논문지 A Vol.12 No.5

컴퓨터 성능 및 네트워크 기술의 발전으로 웹 상에서 연속매체(Continuous Media: CM)의 온라인 스트리밍(streaming) 서비스가 일반화 되었다. 이런 서비스를 위해서는 다양한 종류의 CM 스트림을 효과적으로 처리할 수 있어야 하며 이를 위해 Sweep 기법이 연구되었다. 이 기법은 끊김현상 없이 스트리밍 서비스를 할 수 있고 탐색지연 시간을 최적화 할 수 있다는 장점을 가지고 있다. 하지만 서비스 하고 있는 스트림의 스케줄링 주기를 사이클이라고 하는 단일한 크기로 맞춰야 하기 때문에 스케줄링의 유연성이 떨어지며, 이로 인해 발생하는 디스크 대역폭의 낭비가 매우 커질 수 있다는 문제를 가지고 있다. 논문에서는 이런 문제점을 해결하기 위해 CM 스트림의 스케줄링 주기를 동적으로 확장할 수 있는 기법을 연구하며, 이 기법에 적합한 새로운 승인제어 방식을 이용하여 끊김현상을 막는다. 논문에서는 제안된 기법의 성능상의 우수성을 보이기 위해 모의실험이 수행되었으며, 모의실험 결과를 통해 제안된 동적 Sweep 기법이 디스크 이용효율과 스케줄링 유연성의 측면에서 기존 Sweep 기법에 비해 우수한 특성이 있음을 알 수 있다. With fast advances in computing power and network technologies, online streaming services of continuous media (CM) have been popularly implemented on the Web. To implement such services, a variety of CM streams need to be processed efficiently, so that the Sweep scheme was proposed. This scheme has several advantages such as hiccup-free playbacks and seek-time optimization. In this scheme, however, the entire CM streams are scheduled with a single scheduling period, called a cycle. Since only one scheduling period is allowed in this scheme, a significant amount of disk time is usually wasted because of its inflexible disk schedules. To solve this, we propose a new dynamic Sweep scheme. For this, we devise an algorithm that is able to expand scheduling periods of serviced CM streams and propose a new admission control mechanism guaranteeing hiccup-free playbacks. To show performance gains, we execute various simulation experiments. From the experimental results, we can see that the proposed scheme outperforms the Sweep scheme in terms of disk utilization and scheduling flexibility.

연속매체 상영을 위한 실시간 디스크 프리팻칭 기법

임성채,Lim Sung Chae 한국정보처리학회 2004 정보처리학회논문지 A Vol.11 No.7

연속매체(Continuous Media : CM)와 같은 데이터를 온라인으로 상영해야 하는 멀티미디어 시스템에서는 연속매체의 시간제약성을 만족시켜 줄 수 있는 실시간 디스크 스케줄링 기법이 요구되며 이를 통해 상영중인 CM 스트림(stream)의 끊김현상(hiccup)을 막을 수 있다. 이런 디스크 스케줄링을 위해 주기성을 가지는 프리팻칭(prefetching) 기법이 널리 쓰이고 있으며, 이는 연속매체가 상당기간 동안 계속 상영된다는 특성에 기반한 것이다. 본 논문에서도 효과적인 디스크 프리팻칭을 위해, 정시도착채널이란 실시간 디스크 채널을 이용한 스케줄링 기법을 제안한다. 이런 디스크 채널의 생성을 위해 bulk-SCAN 기법이 사용되며 유연한 채널 할당을 위해 실시간 알고리즘인 EDF(earliest-deadline-first) 알고리즘이 이용된다. 제안한 기법은 기존 방법에서와 같이 끊김현상 없는 상영을 제공함은 물론이고, I/O 처리율과 서비스 응답시간 면에서 우수성을 가진다. 논문에서는 이런 성능상의 장점을 시뮬레이션을 통해 보인다. To play back CM (Continuous Media) in online mode, the multimedia system Is required to have a real-time disk scheduling scheme that can efficiently fulfill the strict temporal constraints of serviced CM streams to prevent hiccups. In general, such disk scheduling is performed based on the concept of periodic prefetching since a CM stream has a rather long Playback time. In this paper, we also propose a periodic prefetching scheme that runs by using real-time disk channels, called on-time delivery channels. Since the channels are generated from the bulk-SCAN algorithm and they can be allocated in a very flexible manner based on the EDF (earliest-deadline-first) algorithm, the proposed scheme provides a better Performance in terms of I/O throughput and the average response time, as well as hiccup-free playback of concurrent CM streams. To show that the proposed scheme outperforms other methods, we give some simulation results.

6 · 25전쟁 기간 중 미국의 대한 군사정책이 한국해군력에 미친 영향

임성채(Lim, Sung-chae) 국방부 군사편찬연구소 2010 군사 Vol.- No.75

마감시간을 고려한 유연성 있는 디스크 SCAN 알고리즘

임성채(Sung Chae Lim) 한국정보과학회 2009 한국정보과학회 학술발표논문집 Vol.36 No.2B

동영상이나 디지털 음악파일과 같이 일정 속도 이상으로 디스크 대역폭을 사용하는 응용이나, 시간 긴급성을 요하는 전자상거래 시스템에 대한 요구로 인해, 마감시간을 지키는 디스크 스케줄링 기법의 필요성이 커지고 있다. 본 논문에서는 SCAN 알고리즘에 기반한 유연한 실시간 디스크 스케줄링 알고리즘을 제안한다. 성능 비교를 위해 현재 사용되는 디스크 드라이브의 동작 속도를 모형화했으며, 시스템에 입력되는 디스크 요청들을 모의 실험하였다. 디스크 요청 비율이 증가함에 따라 변화하는 마감시간 위반비율을 측정함으로써 성능 평가를 수행했다. 제안된 알고리즘은 탐색지연시간을 최소화 하면서 마감시간을 지킬 수 있어 다른 알고리즘에 비해 매우 우수한 성능을 보였다.

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

임성채,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.

대용량 데이터 색인에 적합한 역파일의 구현

임성채 ( Sung Chae Lim ) 한국정보처리학회 2008 한국정보처리학회 학술대회논문집 Vol.15 No.2

대용량 문서에 대한 키워드 검색을 위해 역파일(inverted-file) 색인 기법이 널리 쓰이고 있다. 역파일 색인 기법을 구현함에 있어 고려되어야 할 점은 키워드 검색 처리 시에 디스크 사용을 최소로 할 수 있는 방법이다. 크기가 작은 역파일이라면 디스크 I/O 사용도 작고 필요시 역파일을 메모리에 적재하여 둠으로써 디스크 사용을 크게 줄일 수 있다. 하지만, 웹 검색이나 규모가 큰 도서관 시스템에서와 같이 색인 데이터 크기가 매우 큰 경우 역파일을 읽는 디스크 비용이 급격히 증가할 수 있다. 본 논문에서는 매우 큰 크기의 역파일을 사용하는 검색 환경에서 디스크 사용을 최소로 할 수 있는 역파일 구조를 제안한다. 제안된 구조는 질의 처리 과정을 고려해 계층 구조로 설계되며 실제 상용 시스템에 적용되어 안정성 및 성능을 입증했다.

다중 키워드 검색에 적합한 동등조인 연산 결과의 동적 관리 기법

임성채,Lim, Sung-Chae 한국정보처리학회 2010 정보처리학회논문지 A Vol.17 No.5

인터넷이나 기업체 안에서 생성되는 문서의 수가 빠르게 증가하고 있고 이에 따라 효율적인 문서 검색 서비스의 중요성도 함께 커지고 있다. 이런 검색 환경에서 사용자의 검색 질의를 미리 예측할 수 없기 때문에 문서 내의 키워드를 자동 추출하여 색인어로 사용하는 전문검색(full-text search)이 일반적으로 적용된다. 전문검색을 위해 생성된 색인 파일의 크기는 문서 수 증가로 대용량화 되고, 이런 대용량 색인에 대한 다중 키워드 질의 처리에는 과도한 디스크 비용이 초래될 수 있다. 논문에서는 이런 비용 문제를 해결하기 위해 대용량 문서의 전문검색 시스템에서 다중 키워드 질의를 효율적으로 처리할 수 있게 하는 색인 파일 구조 및 관리 기법을 제안한다. 제안된 방법은 다중 키워드 검색에 적합한 것으로 알려진 역파일을 기본 색인 구조로 하며, 질의 처리의 조인 연산과 랭킹 연산에 적합하도록 색인 파일을 계층화한다. 이를 바탕으로 다중 키워드 질의를 구성할 확률이 높은 키워드 쌍에 대한 조인 연산 결과를 주기억장치 공간에 동적으로 저장함으로써 디스크 사용량을 크게 줄일 수 있다. 논문에서는 제안된 기법의 우수성을 보이기 위해 디스크 비용 모델에 기반한 성능 비교도 수행한다. With an increasing number of documents in the Internet or enterprises, it becomes crucial to efficiently support users' queries on those documents. In that situation, the full-text search technique is accepted in general, because it can answer uncontrolled ad-hoc queries by automatically indexing all the keywords found in the documents. The size of index files made for full-text searches grows with the increasing number of indexed documents, and thus the disk cost may be too large to process multi-keyword queries against those enlarged index files. To solve the problem, we propose both of the index file structure and its management scheme suitable to the processing of multi-keyword queries against a large volume of index files. For this, we adopt the structure of inverted-files, which are widely used in the multi-keyword searches, as a basic index structure and modify it to a hierarchical structure for join operations and ranking operations performed during the query processing. In order to save disk costs based on that index structure, we dynamically store in the main memory the results of join operations between two keywords, if they are highly expected to be entered in users' queries. We also do performance comparisons using a cost model of the disk to show the performance advantage of the proposed scheme.

쿨링다운 노드를 사용한 TPR*-트리 효율화 기법

임성채(Sung Chae Lim) 한국정보과학회 2011 한국정보과학회 학술발표논문집 Vol.38 No.1B

GPS 칩을 내장한 다양한 이동 통신 기기의 사용으로 위치 정보를 이용한 응용이 점차 확산될 전망이다. 위치 정보를 기반으로 한 응용 시스템에서는 다수 이동 객체의 위치 정보를 실시간으로 기록하고, 미래 시점의 객체 위치를 추정할 수 있어야 한다. 이런 요구에 따라 효과적인 이동 객체 색인에 고안된 기법이 TPR*-트리이다. 하지만 TPR*-트리는 고정 위치 색인에 최적화된 R-트리에 기본을 두었기 때문에 갱신 비용이 매우 커질 수 있다는 문제가 있다. R-트리에서는 갱신 연산이 빈번하지 않을 수 있지만 TPR*-트리의 경우는 이동 객체가 속도를 변화시킬 때마다 갱신 연산이 요구되기 때문에 상대적으로 매우 큰 갱신 비용이 발생할 수 있다. 이런 문제점을 부분적으로 해결하기 위해 본 논문에서는 쿨링다운 노드를 사용한 TPR*-트리를 제안한다. 제안된 트리는 트리의 상위 계층에 일부 이동 객체를 버퍼링함으로써 갱신 연산을 최소화 할 수 있다. 또한 지나친 사장 영역(dead space)의 확대를 방지함으로써 검색 성능 저하를 효과적으로 줄일 수 있다.

OSI - CCR 서비스의 구현

임성채(Sung-Chae Lim),유호동(Ho-Dong Yoo),김명호(Myoung-Ho Kim) 한국정보과학회 1993 한국정보과학회 학술발표논문집 Vol.20 No.2

분산 환경에서 수행되는 트랜잭션은 분산 트랜잭션에 관계한 모든 사이트에 대해 각 사이트의 국부 트랜잭션이 갖는 결과들이 일관성(consistency)을 유지할 수 있어야 한다. 분산 트랜잭션의 일관성을 유지하기 위해선 2단계 종료 규약과 통신장애나 응용 프로그램의 고장에 대비한 회복 기능이 요구되며 이런 요구 사항을 표준적으로 제공하고자 하는 것이 OSI-CCR(Commitment,Concurrency and Recovery) 서비스의 목적이다. 본 논문에서는 분산 트랜잭션 처리 시스템 개발에 유용하게 사용되는 OSI-CCR 서비스의 구현에 관해 기술하려 하며, 특히 CCR 구현에 있어 핵심적인 부분인 CCR 로그 관리 시스템 구현을 위한 사항들을 자세히 기술하도록 한다.