분산 시스템의 화일 배치 기법에 대한 성능 평가 방법

고건(Kern Koh),엄영익(Young Ik Eom) 한국정보과학회 1993 정보과학회논문지 Vol.20 No.4

분산 처리 시스템에 존재하는 많은 화일들을 각 노드에 최적으로 중복, 배치하는 문제에 대하여 지금까지 많은 연구가 있어 왔다. 이 문제에 대해서는 분산 처리 시스템의 사용 목적, 시스템의 특성 등에 따라 여러가지 모델이 형성되어 왔으며 실제로 이를 해결하는 기법도 여러가지가 개발되고 구현되어 왔다. 이러한 많은 연구에도 불구하고 각 기법들에 대한 성능을 평가할 수 있는 일관된 성능 평가 방법의 개발이 아직 미진한 실정이다. 본 논문에서는 화일들의 배치에 따르는 운영 비용에 대해 화일들의 저장 비용과 화일들의 전송에 의한 통신 비용을 대상으로 하여 임의의 노드에서 불필요한 시간에 화일이 배치되는 일이 없도록 문제에 대한 모델을 설정하고 이에 대한 최적의 배치 상태를 알아내는 해결책을 고안하여 이의 결과가 분산 처리 시스템의 여러 화일 배치 기법들에 대한 비교나 성능 측정의 목적으로 사용될 수 있도록 했으며 그 실험 결과와 이 기법이 O(n³)의 시간 복잡도를 가짐을 보였다. Much research has been conducted for the optimal distribution of files among the nodes in distributed systems. Although many algorithms for file placement have been proposed, their performance evaluation has not received sufficient attention In this paper, a tool for measuring the performance of file palcement algorithms is proposed. First a model is developed for allocating files among the nodes, and then an algorithm for determining optimal dynamic file placement is proposed. Although our optimal solution is realizable only in theory, it provides a useful benchmark to which the performance of any practical file placement algorithms can be compared. The time complexity of our algorithm is shown to be O(n³) where n is the number of nonreference intervals. The results of evaluating representitive file palcement algorithms are also presented.

국내외 Open Source Software 현황

고건(Kern Koh) 한국정보과학회 2008 정보과학회지 Vol.26 No.7

컴퓨터공학의 위기 극복 방안

고건(Kern Koh) 한국정보과학회 2007 정보과학회지 Vol.25 No.8

소프트웨어 시스템의 원가 및 개발기간 평가에 관한 연구

고건(Kern Koh),우치수(Chi Su Wu) 한국정보과학회 1984 정보과학회논문지 Vol.11 No.3

소프트웨어 개발은 인력, 개발기간을 입력으로 하여 출력인 명령어를 생성하는 변환이며, 이 변환은 입력, 출력, 개발환경 사이에 일정한 현상을 가진다. 본 연구는 현상에서 유도된 수식과 Boehm의 COCOMO 모델을 이용하여 랜덤하게 추출된 프로젝트들을 자료로 하여 문제점과 개선점을 지적하였다. Software developments are regarded as a transformation from input, manpower and development time, to output and source instructions. This transformation is a process with some phenomena. In this paper. some problems and improvements are studied based on the model of COCOMO derived some formulas from the phenemena using random sampling software projects data.

확률적 모델을 이용한 교착상태의 특성 분석

고건(Kern Koh),성순용(Soonyong Seong) 한국정보과학회 1991 정보과학회논문지 Vol.18 No.4

교착상태의 발견 기법에는 연속 방식과 주기 방식이 있다. 연속 방식은 교착상태를 바로 발견할 수 있으나 그 부하가 과중할 수 있고, 주기 방식은 최적의 주기를 결정하는 문제가 남는다. 이와 같이 교착상태 발생 빈도는 교착 상태 발견 기법의 성능에 많은 영향을 미친다. 그러나 교착상태 발생 자체에 대한 성질에 관해서는 별로 연구되지 않았다. 본 논문에서는 교착상태의 특성을 분석할 수 있는 확률적 모델을 제시하고, 이 모델을 사용하여 교착상태에 도달할 때까지의 시간 및 그 기간의 자원 이용률과 보류 프로세스 비율 등을 계산하였다. There are two approaches in deadlock detection : continuous detection and periodic detection. The advantage of continuous detection is the early detection of deadlocks, but the problem is the cost for its frequent execution. In periodic detection, the determination of a reasonable or optimal time period becomes an issue. Hence the frequency of deadlock may affect the performance of various deadlock detection schemes. However, study on the deadlock occurrence itself has received relatively little attention. This paper proposes a probabilistic model for the analysis of deadlock properties. We calculate the time to deadlock, resource utilization, and the rate of blocked processes using our model.

커널의 미리읽기를 고려한 압축파일시스템의 읽기성능향상

안성용(Sungyong Ahn),고건(Kern Koh) 한국정보과학회 2009 한국정보과학회 학술발표논문집 Vol.36 No.2A

병렬 응용 프로그램을 위한 운영체제의 지원

장문석(Moonseok Jang),고건(Kern Koh) 한국정보과학회 1991 한국정보과학회 학술발표논문집 Vol.18 No.2

다중 프로세서 시스템에서 병렬 컴파일러를 사용하면 하나의 응용 프로그램을 병렬로 수행하여 수행 속도를 높일 수 있다. 그러나, 컴파일러가 응용 프로그램 내에서 탐지한 병렬성을 충분히 이용하기 위해서는 새로 생성되는 제어 흐름을 효율적으로 제어해야 한다. 특히, 순차적 응용 프로그램과 병렬 응용 프로그램이 혼합되어 시분할 방식으로 수행되는 다중 프로그래밍 환경에서는 운영체제가 이드를 효과적으로 제어하는 기능을 가져야 한다. 본 논문에서는 컴파일러가 탐지할 수 있는 병렬성 중에서, 프로시져 수준과 루프 수준의 병렬성을 가진 응용 프로그램을 다중 프로그래밍 환경에서 효율적으로 수행시키기 위하여 확장되어야 할 운영체제 커널의 기능을 제시하고, 이 기능을 사용하기 위한 인터페이스를 제안하고자 한다.

블록 분류에 기반한 데이타베이스의 효율적 캐쉬 관리 기법

신일훈(Ilhoon Shin),고건(Kern Koh) 한국정보과학회 2002 정보과학회논문지 : 시스템 및 이론 Vol.29 No.7·8

LRU는 비균등 참조 패턴을 보이는 데이타베이스의 캐쉬 교체 정책으로 적합하지 않음에도 불구하고, 적절한 대안 부재로 인해 대부분의 데이타베이스 시스템에서 캐쉬 교체 정책으로 이용되어 왔다. 본 논문은 실제 데이타베이스 트레이스 분석을 통해 데이타베이스의 블록 참조 패턴을 추출하고, 이를 바탕으로 새로운 캐쉬 교체 정책을 제안한다. 데이타베이스의 트레이스 분석 결과, 전체 시간동안 거의 참조되지 않는 블록이 전체의 70% 가량을 차지하였다. 그리고 블록의 재참조 가능성에 미치는 최근도 (recency)의 영향력이 시간적 지역성으로 인해 처음엔 강력하지만, LRU 스택거리가 증가함에 따라 급격히 감소하여, 결국엔 사라지는 현상을 관찰하였다. 이 관찰을 토대로, 본 논문은 전체 블록을 재참조 가능성과 재참조 가능성에 대한 최근도의 영향력을 기준으로 4개의 그룹으로 분류하고, 각 그룹의 참조 특징에 적합한 우선순위 평가 방법을 운용하는 RCB(Reference Characteristic Based) 캐쉬 교체 정책을 제안한다. RCB 정책은 재참조 가능성이 극히 낮은 블록은 다른 블록보다 캐쉬에서 빨리 교체하며, 오랜 시간 참조되지 않은 블록에 대해서는 참조빈도에 의거하여 블록의 우선순위를 결정한다. 실제 데이타베이스 워크로드를 통한 모의실험 수행 결과, RCB 정책은 기존의 다른 교체 정책들(LRU, 2Q, LRU-K, LRFU)보다 우수한 성능을 나타냈으며, 특히 LRU에 비해서는 약 5 ~ 12.7% 정도, 캐쉬적중실패 회수를 줄였다. RCB 정책의 시간복잡도는 O(1)로서 LRU, 2Q 등과 동일하며, 캐쉬 크기를 N이라 할 때 시간복잡도가 O(log₂N)인 LFU와 LRU-K, 그리고 O(1)부터 O(log₂N) 사이의 값을 갖는 LRFU보다 우수하다. Although LRU is not adequate for database that has non-uniform reference pattern, it has been adopted in most database systems due to the absence of the proper alternative. We analyze database block reference pattern with the realistic database trace. Based on this analysis, we propose a new cache replacement policy. Trace analysis shows that extremely non-popular blocks take up about 70 % of the entire blocks. The influence of recency on blocks’ re-reference likelihood is at first strong due to temporal locality, however, it rapidly decreases and eventually becomes negligible as stack distance increases. Based on this observation, RCB(Reference Characteristic Based) cache replacement policy, which we propose in this paper, classifies the entire blocks into four block groups by blocks’ recency and re-reference likelihood, and operates different priority evaluation methods for each block group. RCB policy evicts non-popular blocks more quickly than the others and evaluates the priority of the block by frequency that has not been referenced for a long time. In a trace-driven simulation, RCB delivers a better performance than the existing polices(LRU, 2Q, LRU-K, LRFU). Especially compared to LRU. It reduces miss count by 5~12.7%. Time complexity of RCB is O(1), which is the same with LRU and 2Q and superior to LRU-K(O(log₂N)) and LRFU(O(1) ~ O(log₂N)).

Group Path Table 에 의한 분산 교착상태 탐지

김경호(Kim Kyongho),고건(koh kern) 한국정보과학회 1990 한국정보과학회 학술발표논문집 Vol.17 No.2

분산시스템의 사용이 증가함에 따라 교착상태를 정확하게 찾아내는 일이 시스템의 효율과 신뢰도 면에서 운영제제의 중요한 일 중 하나가 되고 있다. 특히, 분산방식의 교착상태 탐지 알고리즘은 이 방식이 가지고 있는 특징들로 인해 현재 많은 연구가 이루어져왔다. 그러나, 분산 시스템의 정보전송 지연과 시스템의 동적 환경은 교착상태 탐지에 많은 어려움을 가져왔다. 따라서, 본 논문은 Group Path Table을 이용하여 multi request와 type의 resource 수가 하나인 동적 환경하에서 교착상태 탐지 알고리즘을 제시하고자 한다.

가상 I/O 세그먼트를 이용한 OneNAND 플래시 메모리의 읽기 성능 향상 기법

현승환(Hyun Seunghwan),고건(Koh Kern) 한국정보과학회 2008 정보과학회 컴퓨팅의 실제 논문지 Vol.14 No.7

OneNAND 플래시는 NAND 플래시와 NOR 플래시의 장점을 모두 가진 고성능 하이브리드 플래시 메모리이다. OneNAND 플래시는 NAND 플래시의 장점들을 그대로 가지고 있을 뿐 아니라, 그동안 NAND 플래시의 단점으로 지적되던 느린 읽기 성능을 획기적으로 개선하였다. 그 결과 OneNAND 플래시는 휴대폰 및 디지털 카메라, PMP, 휴대용 게임기와 같은 고성능 휴대용 정보기기를 위한 최적의 스토리지 솔루션으로 각광받고 있다. 하지만 Linux를 비롯하여 현재 사용되고 있는 대부분의 범용 운영체제들은 가상 메모리와 블록 I/O 계층 구조의 제약으로 인해 OneNAND 플래시의 뛰어난 읽기 성능을 제대로 활용하지 못하는 문제를 안고 있다. 이에 본 연구에서는 기존의 소프트웨어 계층 구조 하에서 OneNAND 플래시의 읽기 성능을 최대한 활용하기 위한 기법인 가상 I/O 세그먼트의 활용을 제안한다. 실제 구현을 통한 실험 결과는 제안된 기법이 OneNAND 플래시의 읽기 수행 시간을 기존에 비해 최고 54%까지 단축할 수 있음을 증명하였다. OneNAND flash is a high-performance hybrid flash memory that combines the advantages of both NAND flash and NOR flash. OneNAND flash has not only all virtues of NAND flash but also greatly enhanced read performance which is considered as a downside of NAND flash. As a result, it is widely used in mobile applications such as mobile phones, digital cameras, PMP, and portable game players. However, most of the general purpose operating systems, such as Linux, can not exploit the read performance of OneNAND flash because of the restrictions imposed by their virtual memory system and block I/O architecture. In order to solve that problem, we suggest a new approach called virtual I/O segment. By using virtual I/O segment, the superior read performance of OneNAND flash can be exploited without modifying the existing block I/O architecture and MTD subsystem. Experiments by implementations show that this approach can reduce read latency of OneNAND flash as much as 54%.