다중처리 시스템의 병렬성 증대를 위한 사이클의 비 지연 발견 기법

김주균(Ju Gyun Kim) 한국정보과학회 2005 정보과학회논문지 : 시스템 및 이론 Vol.32 No.1·2

본 논문에서는 즉시 할당 상태와 함께 단일 자원, 단일 요청의 가정 하에서 다중처리 시스템에서 사이클을 발생 즉시 발견함으로써 지연 없는 교착상태의 발견 방법을 소개한다. 기존의 방법과는 달리 제시된 방법은 n과 m으로 프로세스와 자원의 수를 나타낼 때 사이클의 발견에 O(1), 대기나 자원의 반납시에 O(n+m)의 시간을 요한다. 따라서 n과 m의 크기에 상관없이 교착상태를 발생 즉시 알 수 있으며, 이점이 다중처리 시스템의 특성과 잘 조화될 수 있음을 보였다. 교착상태와 연관된 응용환경에서 이러한 발견의 예측성과 비 지연성은 매우 유용할 것이다. This paper presents a non-blocking deadlock detection scheme with immediate cycle detection in multiprocessing systems. We assume an expedient state and a special case where each type of resource has one unit and each request is limited to one resource unit at a time. Unlike the previous deadlock detection schemes, this new method takes O(1) time for detecting a cycle and O(n+m) time for blocking or handling resource release where n and m are the number of processes and that of resources in the system. The deadlock detection latency is thus minimized and is constant regardless of n and m. However, in a multiprocessing system, the operating system can handle the blocking or release on-the-fly running on a separate processor, thus not interfering with user process execution. To some applications where deadlock is concerned, a predictable and zero-latency deadlock detection scheme could be very useful.

대기 유발 자원의 집합을 이용한 교착상태 발견 알고리즘 : 싸이클 발견

김주균(Ju Gyun Kim),고건(Kern Koh) 한국정보과학회 1990 정보과학회논문지 Vol.17 No.5

운영체제에서의 자원의 요청 및 할당이나, 화일시스템, 데이타베이스 등에서 사용되는 Looking은 널리 쓰이는 기법이나 시스템의 교착상태(Deadlock)를 유발시키는 요인이다. 본 논문에서는 즉시 할당상태의 가정하에 단일 자원의 단일요청 시스템에서 프로세스가 자원요청을 낸 후 내기 상태로 전이되는 경우의 대기유발자원(blocking resources)들을 현재까지의 수행과정을 보관할 수 있는 동질의 집합으로 나눔으로써 효과적으로 교착상태-싸이클-를 감지할 수 있는 방법을 제시하였다. 과거의 방법에서 사용되어 왔던 자원의 대기 그래프(Wait-for-graph)가 시스템내의 모든 프로세스와 자원을 시스템내의 프로세스와 자원의 개수로 나타낼 때 O(n+m)이 되며 교착상태의 판단은 O(1)으로, 교착상태가 아닐 경우 집합의 합병이나 분리에 대기유발자원의 개수에 비례하는-O(m)-시간 복잡도를 가짐을 보였다. 또한 이러한 방법이 현재까지 알려진 교착상태 발견을 위한 자료구조와는 다른 구조와 알고리즘을 사용함으로써 이 분야에 새로운 방법론이 될 수 있음과 동시에 다중처리 시스템에서 효과적인 병렬처리기능을 제공할 수 있음을 보였다. 제시된 방법의 정확성을 위해 알고리즘의 수행과정을 각 경우별로 나누어 그림과 함께 보이면서 증명하였다. Locking is widely used in distributed database systems for enforcing database consistency. This method is also favored in other system softwares, such as operating system, for managing various resources. However, locking shoul be used with great care since it could lead the system into a well known deadlock state. In this paper, we propose a new deadlock detection algorithm which is considerably more efficient than existing deadlock detection algorithms. We assume a special case system where each type of resource has one unit and each request is limited to one at a time. Past deadlock detection algorithms are based on so called "Wait-for-Graph(WFG)," which consists of all the processes and resources in the system. This new algorithm maintains much smaller data structure based on blocking resources only. This new approach helps reducing the complexity since redundant information is now excluded and in the progress of maintaining blocking resource graph, all the past observation are preserved in this new structure. It has time complexities of O(1) for detecting deadlock and O(m) for set merging or splitting with space complexity of O(n+m) where n is the number of processed and in is that of resources in a system. It provides not only a new methodology in this area but also gives chances of parallelism in multiprocessing environments. Correctness proofs are shown by tracing the algorithm with various cases.

영어 어휘력 향상을 위한 CALL (Computer-Assisted Language Learning) 도구의 효과 분석

김주균 ( Ju Gyun Kim ) 한국멀티미디어언어교육학회 2011 멀티미디어 언어교육 Vol.14 No.3

Throughout the decades, various computer assisted learning methods have been developed for computer aided educations (CAE). Computer assisted language learning (CALL) is one of those methods which aim to learn foreign languages. This paper presents the effectiveness of CALL as an educational tool to increase vocabulary power for elementary school students in their English classes. For experimental purpose, students are divided into two groups, CALL based group and traditional learning based group. For the CALL based group, students are divided into two subgroups, Web-based learning tool and CD-ROM titles are provided to student in each subgroup respectively, while only traditional lectures are given to students in comparative group. Performance results shows that CALL based learning is more efficient than traditional learning in achieving vocabulary power and especially, CD-ROM title based learning shows better performance than Web-based learning. This comes from the functional simplicity of CD-ROM title and will be discussed in detail at the analysis part of this paper. Some statistically confirmed hypotheses from this experiment could be useful reference for applying CALL based learning in language learning classes for elementary school students.

다중처리 시스템하의 비 지연적 노트 발견 기법

김주균(Ju Gyun Kim),고건(Kern Koh) 한국정보과학회 1991 정보과학회논문지 Vol.18 No.5

본 논문에서는 다중처리 시스템(Multiprocessing system)하에서 발생되는 노트(Knot)를 발생 즉시에 탐지함으로써 교착상태의 발견을 병렬적으로 수행할 수 있는 방법을 제시하였다. 제시된 방법은 모든 프로세스가 한번에 하나의 자원씩만 요청할 수 있도록 하였으며 즉시 할당상태로 가정하였다. 제시된 방법은 현재까지 알려진 노트 발견기법들이 사용한 대기 그래프(Wait-for-graph)대신 다른 자료구조를 사용하여 노트의 발견을 0(1)으로 가능하게 하였으며, 노트 판단후의 작업과 자원의 반납시에는 n과 m을 시스템내의 프로세스와 자원의 개수로 나타낼 때 0(nm)의 수행시간을 요구한다. 따라서, n과 m의 크기에 무관하게 교착상태의 판단을 즉각 할 수 있으며, 0(nm) 작업들은 교착상태가 아닐 경우의 작업들이므로 다중처리 시스템하에서 여분의 프로세서(Processors)를 사용하여 다른 작업에 영향을 주지않고 병렬 수행이 가능하게 된다. 응용 환경에 따라서는 이러한 수행시간의 예측성과 비 지연성이 매우 중요하다. This papaer presents a non-blocking deadlock detection scheme with an immediate knot detection in multiprocessing systems. We assume an expedient state and a special case where each request is limited to one resource unit at a time. Unlike the previous deadlock detection schemes, our new method, using some different data structures, takes 0(1) time for detecting knot and 0(nm) time for blocking or handling resource release where n and m are the number of processes and that of resources in the system respectively. The deadlock detection latency is thus minimized and is constant regardless of m and n. However, in a multiprocessor system environment, operating system can handle the blocking or release on-the-fly running on a separate processor, thus not interfering with user process execution. To some class of applications, a predictable and zero-latency deadlock detection scheme could be very useful.

분산 데이타베이스의 고장복구를 위한 공동검사점 지정기법

김주균(Ju Gyun Kim),고건(Kern Koh) 한국정보과학회 1989 정보과학회논문지 Vol.16 No.1

컴퓨터 시스템의 높은 신뢰도를 유지하기 위하여 사이트의 일시적 고장후에도 상태의 일치성(consistent state)을 구축하기 위한 기법이 필요하다. 분산 데이타베이스 시스템 (DDBMS)에서는 이러한 고장에도 불구하고 정상적 프로세스들의 수행을 위해 거의 대부분이 검사점 지정 및 철회(checkpointing and rollback)복구 전략을 채택하고 있다. 본 논문에서는, 데이타가 완전 중복되었을 경우, 2-Phase Commit 프로토콜에 주기적인 검사점 지정을 삽입시킴으로써 전체 사이트의 공동(global)검사정 지정을 이루는 방법을 제시하여 기존의 공동검사점 지정 방법들이 가지는 여러 단점을 해결하도록 하였으며, 제시된 방법의 정확성 및 최적운용을 위한 분석을 보였다. The demand for highly reliable computer systems has led to techniques for construction of a consistent state after transient failures. In DDBMS "checkpointing and rollbackrecovery" are well known techniques that allow processes to make progress in spite of failures. This paper presents and discusses a periodic checkpointing method coordinated with the 2-phase commit protocol which ensures global consistency and recoverability when data are fully replicated. In contrast to previous methods, this method not only solves Domino-effect problem but also needs no additional hardwares and communication overhead. It can be easily implemented in any systems using the 2-phase commit protocol.

클러스터 P2P 네트워크에서의 최적 슈퍼피어 개수

김성희,김주균,이상규,이준수,Kim Sung-Hee,Kim Ju-Gyun,Lee Sang-Kyu,Lee Jun-Soo 한국정보처리학회 2006 정보처리학회논문지 C : 정보통신,정보보안 Vol.13 No.4

슈퍼피어 기반 P2P 네트워크는 전체 네트워크를 여러 개의 작은 서브 네트워크로 클러스터링하고 각 클러스터를 해당 그룹에 속한 노드들에 대한 정보를 가지고 있는 슈퍼피어라는 특정 노드가 관리하는 네트워크 모델로써 검색의 효율성과 네트워크 부하가 적다는 이점을 가지고 있다. 본 논문은 슈퍼피어기반 P2P네트워크에서 먼저 피어들의 정보검색, 새로운 노드 가입, 정보갱신 동의 동작으로 발생하는 메시지의 양을 기반으로 한 트래픽 비용을 클러스터 내의 비용과 슈퍼피어 간의 비용으로 측정하고, 이 두 비용을 바탕으로 다양한 네트워크 크기에 따라 트래픽 비용을 최소화할 수 있는 슈퍼피어의 개수를 제시한다. In a super-peer based P2P network, The network is clustered and each cluster is managed by a special peer, called a super-peer which has information of all peers in its cluster. This clustered P2P model is known to have efficient information search and less traffic load. In this paper, we first estimate the message traffic cost caused by peer's query, join and update actions within a cluster as well as between the clusters and with these values, we present the optimal number of super-peers that minimizes the traffic cost for the various size of super-peer based P2P networks.rks.

거짓 공유를 제거하는 효율적 워드 단위 캐쉬 일관성 프로토콜

이은희(Eun Hee Lee),김주균(Ju Gyun Kim) 한국정보과학회 1998 정보과학회논문지 : 시스템 및 이론 Vol.25 No.6

각 프로세서의 전용으로 캐쉬가 연결된 버스 기반 공유메모리 다중프로세서 시스템에서 시스템의 성능은 캐쉬 일관성 유지를 위해 발생하는 버스 트래픽에 의해 결정된다. 이러한 버스 트래픽 오버헤드중 어떤 것은 이른바 거짓 공유로 인해 발생되는데 거짓 공유는 캐쉬 블럭이 다중워드로 구성된 경우 각 프로세서가 동일 블럭내의 서로 다른 워드들을 독립적으로 참조할 때 발생하는 것으로 이 때 시스템은 캐쉬 블럭만이 공유되고 실제 데이타는 공유되지 않았음에도 불구하고 전체 데이타가 공유된 것처럼 취급한다. 기존의 기법 중 워드단위 캐쉬 일관성 프로토콜(WUCP)는 효율적으로 알려져 있다. 이 기법은 거짓 공유를 제거하며 이에 따라 버스트래픽을 감소시킬 수 있으나 거짓 공유의 감지를 위해 추가적인 버스트래픽과 비트 오버헤드가 필요하다. 본 논문은 WUCP 의 이러한 단점을 극복하여 보다 효과적으로 거짓 공유의 제거에 필요한 버스트래픽과 비트 오버헤드를 감소시키며 캐쉬 일관성을 유지하는 개선된 워드단위 캐쉬 일관성 프로토콜(IWUCP)을 제안한다. IWUCP는 다른 기타의 기록-무효 프로토콜들에 비해 향상된 WUCP의 장점을 그대로 보장하며 거짓공유를 제거하는데 필요한 오버헤드를 최소화 할 수 있다. In a bus-based shared memory multiprocessor system with private caches, the performance is limited by the amount of the bus traffic in order to keep the cache coherence. Some of this traffic overhead is caused by so called false sharing when multiple processors access different words in the same cache blocks and the system treats it as if data is shared even though the cache block containing the data is actually not shared. Among the existing schemes, the Word Unit Cache Protocol(WUCP) is known to be efficient. It eliminates the false sharing, thus can reduce the bus traffic, but It requires additional bits and another kind of bus traffic in order to detect the false sharing. In this paper, we present an improved version of WUCP, called IWUCP, which requires less amount of bits and bus traffic. By IWUCP, the advantages of WUCP compared to the other write invalidation protocols are also guaranteed and the overhead for preventing the false sharing can be kept in minimum.

학업성취도 향상을 위한 웹기반 학습과 동료 교수법의 혼합 모델

이윤경 ( Yun Kyung Lee ),김주균 ( Ju Gyun Kim ) 한국컴퓨터교육학회 2008 컴퓨터교육학회 논문지 Vol.11 No.6

MANET에서 Interrupt message를 이용한 AODV 라우팅 프로토콜의 성능 개선

이윤경(Yun-kyung Lee),김주균(Ju-gyun Kim) 한국통신학회 2013 韓國通信學會論文誌 Vol.25 No.8

MANET 환경에서 AODV는 요구기반 방식으로써의 장점을 갖지만 다른 라우팅 프로토콜들에 비해 제어패킷 오버헤드가 크다는 단점도 가지고 있다. 본 논문은 로컬 연결의 탐지와 이웃 목록을 유지하기 위해 주기적으로 브로드캐스트하는 Hello message로 인한 문제점을 개선한다. 주기적인 Hello message는 패킷 전달률과 제한된 대역폭의 효율성을 감소시키고, 제어 패킷 오버헤드를 증가시켜 잔존 에너지량과 네트워크 수명을 감소시킨다. 또한 AODV에서의 주기적인 Hello message는 “Reactive”하지 않은 방식이기 때문에 많은 논쟁의 근원이었다. 이러한 문제점을 개선하기 위해 본 연구에서는 인터럽트 방식을 이용하여 주기적인 Hello message를 제거함으로써 제어패킷 오버헤드를 줄여 성능을 개선하였다. 기존의 AODV와 제안된 mod_AODV의 성능은 QualNet 5.0을 이용하여 실험 분석하였고, 실험 결과는 시뮬레이션 파라메터들의 변화에 대한 모든 성능 매트릭들에서 mod_AODV가 전반적으로 우수한 성능을 보였다. In MANET, AODV(Ad hoc On-demand Distance Vector) has its advantages as on-demand approach but it also has a disadvantage that the control packet overhead is high compared to other routing protocols. This paper improves the problem caused by Hello messages that are broadcasted periodically to detect the local connectivity and maintain neighbor list. Periodic hello messages reduce the Packet delivery ratio and the efficiency in the limited bandwidth. And its increased Control packet overhead leads to decrease the Residual battery capacity and the Network lifetime. Further, non-reactive nature of periodic hello messages in AODV has also been the source of numerous controversies. In order to solve these problems, this paper improves the performance by using the interrupt driven approach which removes periodic hello messages and decreases the Control packet overhead. Performance comparisons between the traditional AODV and proposed mod_AODV done with network simulator QualNet 5.0 show that the mod_AODV performs better in most performance metrics under scenarios with various values of simulation parameters.

MANET환경에서 Interrupt Message와 Backup path 기법에 기반한 AODV의 성능개선

이윤경(Yun-kyung Lee),김주균(Ju-gyun Kim) 한국통신학회 2015 韓國通信學會論文誌 Vol.40 No.7