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

고건(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.

국내외 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),엄영익(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.

실시간 시스템에서 여러 부정확한 스케쥴링 기법하에서의 부정확한 확률에 관한 비교 분석

안귀임,고건,Ah, Gwl-Im,Koh, Kern 한국통신학회 1994 韓國通信學會論文誌 Vol.19 No.7

실시간 시스템에는 정확한 계산 기법과 부정확한 계산 기법이 있다. 부정확한 계산 기법은 실시간 시스템에서 스케쥴링의 유연성을 제공하는 수단이다. 지금까지 큐잉이론을 이용한 부정확한 스케쥴링에 관한 연구들은 태스크들의 평균 결과의 질과 평균 대기시간을 정충한 때의 비용과 장점들을 명확하게 수량화하는 것들이었다. 이논문은 두개의 부정확한 스케쥴링 방법을 사용할 때, 어떤 태스크가 부정확한 계산이 될 부정확한 확률들을 구하였으며 또한, 이런 두 방법의 부정확한 확률들의 여러 단조형 부정확한 시스템 매개변수들에 대한 의존성을 비교 분석하였다. There are two computation techniques in real time systems : precise and imprecise computation. The imprecise computation technique is a means to provide scheduling flexibility in real time systems. The studies on imprecise scheduling using queueing theoretical formulation up to data are to explicitly quantify the costs and benifits in trade-off between the average result quality and the average waiting time of tasks. This paper uses two imprecise scheduling schemes and solves the imprecision probability, the probability of any task being imprecise under two imprecise scheduling schemes and analyzes the dependence of the imprecision probability on several parameters os the monotone imprecise system.

연속미디어 파일 시스템의 버퍼 캐시에서 데이터 참조 유형의 고려

조경운,류연승,고건,Cho, Kyung-Woon,Ryu, Yeon-Seung,Koh, Kern 한국정보처리학회 2002 정보처리학회논문지 A Vol.9 No.2

연속미디어 파일을 위한 버퍼 캐시 기법들은 연속 미디어의 순차적 접근만을 고려하고 반복참조는 고려하지 않았다. 그러나, 외국어 영상 학습의 경우 사용자가 어떤 장면을 반복 구간으로 설정하면 자동으로 수회 반복 상영하는 기능이 있을 수 있다. 본 논문에서는 순차 참조와 반복 참조가 혼재하는 연속미디어 파일 시스템을 위한 새로운 버퍼 캐시 기법을 제안한다. 제안한 기법은 파일의 참조 유형을 탐지하고 파일 별로 적절한 교체 정책을 적용하여 버퍼 캐시 적중률을 높인다. Previous buffer cache schemes for continuous media file system only exploited the sequentiality of continuous media accesses and didn't consider looping references. However, in some video applications like foreign language learning, users mark the scene as loop area and then application automatically playbacks the scene several times. In this paper, we propose a novel buffer cache scheme for continuous media file system that sequential and looping references exist together. Proposed scheme increases the cache hit ratio by detecting reference pattern of files and appling an appropriate replacement policy to each file.

실시간 태스크 스케쥴링을 위한 비관적 마감시한 상한 프로토콜

김주용(Joo Yong Kim),고건(Kern Koh) 한국정보과학회 1994 정보과학회논문지 Vol.21 No.8

본 논문은 마감시한 우선 스케쥴링(Earliest Deadline First Scheduling)에서의 우선순위 역전(priority inversion) 방지를 위해 비관적 마감시한 상한 프로토콜(Pessimistic Deadline Ceiling Protocol, 이하 PDCP)을 제안한다. PDCP는 공유 자원들의 상한(ceiling) 값을 정적으로 유지하여, 동적 우선순위 상한 프로토콜(Dynamic Priority Ceiling Protocol)에 대해 수행중 오버헤드를 줄인다. 동시에 수행중인 태스크의 우선순위로 실제 마감시한을 사용하고, 자원 요청시에 접근 가능 여부를 조사하여, 스택 자원 정책(Stack Resource Policy)에 대해 성능을 높인다. 이러한 특징들은 현 주기의 수행을 마친 태스크들의 우선순위에 대해 비관적 마감시한(Pessimistic Deadline)을 사용함으로써 가능하다. 비관적 마감시한은 태스크의 한 주기가 특정 시간 직후에 도착할 때의 마감시한이다. PDCP는 비율 단조 스케쥴링(Rate Monotonic Scheduling)상에서 설계된 확장 프로토콜들을 마감시한 우선 스케쥴링에 적용할 수 있다. 한편 본 논문에서는 비율 단조 스케쥴링 상의 PDCP에 대해서도 제안한다. This paper proposes a new protocol called PDCP (Pessimistic Deadline Ceiling Protocol) to solve the priority inversion problem under Earliest Deadline First Scheduling (EDF). PDCP reduces run-time overhead over DPCP (Dynamic Priority Ceiling Protocol) by using static ceiling values for shared resources. It can gain performance over SRP (Stack Resource Policy) by using real deadline for current executing task's priority and testing the accessibility at the resource request time. These are achieved by using pessimistic deadlines for the priorities of tasks which have completed their executions at current periods. Pessimistic deadline is the deadline of a task assuming pessimistically that the task will arrive right after a certain time point. PDCP can be extended to some advanced protocols under EDF that were designed under Rate Monotonic scheduling(RM), some of which are impossible with existing protocols. We also suggest the PDCP under RM.

마이크로커널 기반 운영체제를 위한 성능 측정 도구의 설계와 구현

장문석(Moon-Seok Chang),고건(Kern Koh),이준원(Joon-Won Lee),김해진(Hae-Jin Kim) 한국정보과학회 1999 정보과학회 컴퓨팅의 실제 논문지 Vol.5 No.2

최근 운영체제 개발 분야에서 마이크로커널 설계 기술이 새로운 경향으로 부각되고 있다. 마이크로커널은 기존의 모노리딕 커널과 상이한 구조를 가지고 있으므로, 성능 분석과 튜닝을 위하여 새로운 도구를 필요로 한다. 본 논문에서는 마이크로커널 기반 운영체제를 위한 성능 측정 도구 MKperf의 개발에 관하여 기술하고자 한다. MKperf는 마이크로커널 구조의 성능에 중요한 영향을 미치는 문맥 교환과 운격 프로시저 호출을 추적할 수 있다. 뿐만 아니라, 캐시와 TLB와 같이 메모리 성능에 결정적인 영향을 미치는 다양한 하드웨어 성능 요소들을 측정할 수 있다. MKperf의 이러한 측정 기능은 마이크로커널 기반 운영체제 성능을 정량적으로 분석하는 데에 유용하게 사용될 수 있다. A recent trend in operating system development is the microkernel design. The microkernel requires a newly designed tool for performance analysis and tuning, since it has different structure compared with monolithic one. In this paper we present MKperf, a performance tool for a microkernel-based operating system. MKperf has a capability to monitor context switches and remote procedure calls which are important activities for the performance of a microkernel. In addition, this tool monitors various hardware events critical to the performance of memory system including cache and TLB. As a result, MKperf provides useful information for the performance analysis of a microkernel-based operating system.

순서적 임계 구역을 사용하는 병렬 프로그램의 오류 수정을 위한 수행중 이상 탐지

전용기(Yong-Kee Jun),고건(Kern Koh) 한국정보과학회 1993 정보과학회논문지 Vol.20 No.1

오류를 가진 병렬 프로그램은, 공유 변수에 병렬로 접근 가능한 타스크들간에 존재하는 이상들 때문에 비결정적 수행을 보이는 것이 일반적이므로, 순차 프로그램에 비해 오류 수정 작업이 어렵다. 이러한 접근 이상들을 효과적으로 탐지해 내기 위한 방법으로서, 프로그램의 수행 중에 변수들에 대한 접근 명령들을 감시할 수 있다. 이러한 기법은, 프로그램의 수행 후에 분석하는 기법들에 비해 기억 장소는 훨씬 적게 드나, 수행 시간의 부담이 크다. 본 연구는, 순서적 임계 구역을 가지는 병렬 루프 프로그램에서, 수행 중에 접근 이상들을 탐지하기 위한 효율적인 기법을 보인다. It is more difficult to debug erroneous parallel programs than sequential programs, since their behaviors show the nondeterminism which is from the anmalies in parallel tasks potentially accessing shared variables. To detect access anomalies effectively, one can utilize the technique that monitors a program executon to detect instructions accessing shared variables in parallel. Compared with post-mortem techiques to detect access anomalies, it is still less expensive in storage space, but not in time. An efficient technique presented here attempts to detect the anomalies at a constant cost during an execution of parallel loop programs which use ordered critical sections.