디스크 배열을 이용한 실시간 멀티미디어 저장 서버에서의 스케쥴링 기법

신현식(Heonshik Shin),조진성(Jinsung Cho) 한국정보과학회 1994 정보과학회논문지 Vol.21 No.11

본 논문에서는 멀티미디어 재생 응용을 위한 실시간 저장 서버를 설계하고 성능 향상을 위한 효율적인 스케쥴링 기법을 제시한다. 실시간 저장 서버는 고속망에 연결된 사용자에 멀티미디어 화일의 실시간 검색을 위한 서비스를 제공하며 멀티미디어 화일의 삽입, 삭제 및 변경등의 비실시간 작업을 수행한다. 실시간 저장 서버의 설계 목표는 동시에 서비스 가능한 사용자의 수를 최대화 시키는 것이며 사용자 서비스의 실시간성 및 연속성이라는 제약조건을 만족시키야 한다. 위의 설계 목표와 제약조건을 만족시키기 위해 효율적인 멀티미디어 블럭의 검색을 지원하는 라운드 스케쥴링을 제안한다. 이는 디스크 유휴시간을 최소화한다. 또한 탐색시간을 최적화하는 RR-SCAN 디스크 암 스케쥴링을 제안한다. 디스크 구조는 성능 분석을 통해 디스크 배열을 대상으로 하였으며, 데이타를 블럭 단위로 디스크에 스트라이핑시킨다. In this paper we design a real-time storage server(RTSS) for remote multimedia playback applications and present an effective scheduling method for its high performance. RTSS performs the real-time retrieval of multimedia files for the remote clients over high speed network as well as non real-time insert, delete, update operations. The design goal is to maximize the number of clients which can be serviced simultaneously. RTSS must, however, maintain the continuity of each medium. To satisfy both the design goal and the constraint, we propose a new scheduling scheme, called round scheduling, to effectively retrieve multimedia disk blocks. The round scheduling is shown to minimize disk idle time. We also present SCAN-like disk arm scheduling that optimizes seek time to access multimedia blocks. Disk architecture for our server adopts a disk array, where data blocks are striped across all the disks.

다중버스상에서 실시간 통신을 위한 가상시간 CSMA 프로토콜의 설계 및 분석

정만상(Man Sang Chung),신현식(Heonshik Shin),허신(Shin Heu),전창호(Chang Ho Jeon) 한국정보과학회 1993 정보과학회논문지 Vol.20 No.6

본 논문은 분산 실시간 환경에서 동적으로 발생하는 실시간 메시지를 효율적으로 전송하기 위한 다중버스 가상시간 CSMA(carrier sense multiple access) 프로토콜을 제안한다. 이를 위해, 단일버스상에서 시간제한을 고려한 가상시간 CSMA 프로토콜을 사건-동작 도표 형태를 기술한다. 그리고 이를 다중버스 구조에 적용하기 위해 다중버스 프로토콜로 확장한다. 제안한 프로토콜의 주요 특성으로, 버스 수가 증가하여도 단일 가상시계만을 사용하여 지원할 수 있으므로 확장가능성이 있고, 버스 수의 증가에 따른 성능 향상 및 일부 버스의 결함이 발생하여도 동작이 가능한 결함허용성이 있다. This paper presents a multiple-bus virtual-time carrier sense multiple access(CSMA) protocol to transmit the dynamically generated real-time messages in distributed real-time environment. For this purpose, a single-bus virtual-time CSMA protocol for time-constrained message communication is described using event-action diagram. Then it is extended to the multiple-bus virtual-time CSMA protocol considering application for multiple-bus configuration. The characteristics of the protocol are : ⅰ) scalability using a single virtual clock to support the increased number of buses, ⅱ) performance enhancement with more buses, ⅲ) fault tolerance for continuous operation in the case of fault occurrence in partial buses.

준경성 실시간 트랜잭션 처리 시스템을 위한 우선 순위 구동형 동시실행 제어 프로토콜

김진환(Jinhwan Kim),신현식(Heonshik Shin) 한국정보과학회 1993 정보과학회논문지 Vol.20 No.12

본 논문에서는 준경성 실시간 시스템의 트랜잭션들을 우선 순위에 따라 스케쥴링하는 동시 실행 제어 프로토콜을 제시한다. 각 데이타에 대한 충돌 상태를 반영하여 트랜잭션들의 불필요한 취소와 중단 현상을 방지함으로써 제시된 프로토콜은 우선 순위가 서로 다른 실시간 트랜잭션들을 보다 효과적으로 제어하고자 하였다. 실제 충돌시 이를 적절히 해결하는 동기화 기법을 내포함으로써 데이타의 일치성이나 트랜잭션의 시간적인 제약을 위반하지 않고 가능한한 많은 트랜잭션들을 동시에 실행시킬 수 있다. 결과적으로 본 프로토콜은 주어진 종료시한내에 성공적으로 종료되는 트랜잭션(특히 우선 순위가 높은)들의 수를 증가시킴으로써 실시간 시스템의 전체적 성능 향상을 도모하였다. 그리고 실시간 환경에서 수행되는 트랜잭션들의 정확한 실행 순서와 완전한 종료를 보장하기 위한 2 단계 종료 과정이 본 프로토콜에 포함되었다. This paper presents a concurrency control protocol to schedule active transactions accessing firm real-time database systems based on priority information. In compliance with the transactions conflict state, this protocol intends to control real-time transactions with different priority more effectively by avoiding unnecessary aborts or blocking of conflicting transactions. Thus, enhanced priority-driven scheduling enables this protocol to interleave and complete as many transactions as possible without sacrificing data consistency or timing constraints because it combines flexible synchronization techniques for desirable real-time conflict resolution. The entire performance is achieved by increasing the number of successful transactions, especially with higher priority. A two-phase commit procedure is integrated into this protocol to ensure correct execution order and atomic commitment of concurrent transactions in the real-time environment.

디스크 배열에서 독립성이 큰 입출력 요구를 위한 화일 단위 인터리빙

황기태(Kitae Hwang),신현식(Heonshik Shin) 한국정보과학회 1992 정보과학회논문지 Vol.19 No.1

다중의 소형 디스크로 구성되는 디스크 배열은 입출력 서브시스템의 병목현상을 제거하기 위한 방법으로 널리 사용되고 있다. 본 논문은 디스크 배열에서 비교적 화일의 크기가 작고 입출력 요구의 독립성이 큰 환경의 입출력 성능을 향상시키기 위하여 디스크 배열상의 파일을 배치하는 새로운 방법인 화일 단위 인터리빙을 제안한다. 입출력 요구의 독립성이란 디스크 입출력 요구들이 서로 상이한 화일에 대해 액세스하고자 하는 특성이다. 화일 단위 인터리빙은 화일을 최소한의 디스크 상에(가능한 한 하나의 디스크에) 연속적인 공간 속에 배치함으로써 서로 다른 화일을 액세스하는 입출력 요구들이 디스크 배열에 의해 병렬적으로 처리될 수 있도록 지원한다. 본 논문에서는 블럭 단위 인터리빙에 의한 화일 배치 방법이 입출력 요구의 독립성이 큰 환경에 부적합함을 예를 들어 보이고, 화일 단위 인터리빙에 의해 성능이 개선될 수 있음을 보인다. 그리고 탐구 횟수 분석과 입출력 응답시간에 대한 시뮬레이션을 통해 성능을 비교한다. 시뮬레이션의 결과는 입출력 요구 빈도수 증가에 따라 화일 단위 인터리빙이 기존의 블럭 단위 인터리빙에 비해 더 높은 입출력 처리율을 제공함을 보여준다. An interleaved disk array which consists of a large number of small inexpensive disks is widely used to remove the bottleneck of I/O subsystem. This paper proposes file-level interleaving, a method of file allocation in disk arrays, for environments with high I/O request independence and relatively small files. I/O request independence is the characteristic that the outstanding I/O requests access different files. File-level interleaving supports high concurrency of accesses to files by spreading blocks of files into contiguous blocks on the smallest possible number of disks(one if possible). This paper shows by examples that the file allocation method by block-level interleaving does not fit in the environments with high I/O request independence and that the I/O performance can be improved by file-level interleaving. The performance in block-level interleaving and that in file-level interleaving are compared by the analysis of the number of seeks and the simulation of I/O response time. The results of simulations show the file-level interleaving supports the higher I/O throughput than the block-level interleaving as the number of I/O requests increases.

분산 실시간 태스크의 스케쥴가능성 개선을 위한 지터 분석

김태웅(Taewoong Kim),신현식(Heonshik Shin),장래혁(Naehyuck Chang) 한국정보과학회 2000 정보과학회논문지 : 시스템 및 이론 Vol.27 No.5

분산 실시간 시스템에서 선행 태스크의 완료에 의해 활성화되는 태스크는 활성화 지터를 갖는 주기적 태스크로 모델링될 수 있다. 태스크의 활성화 지터는 선행 태스크의 최악과 최선 응답시간의 차로 정의된다. 기존의 방법은 최선 응답시간을 실제보다 훨씬 작은 값으로 가정하기 때문에, 활성화 지터와 낮은 우선순위를 갖는 태스크들의 최악 응답시간이 과대평가된다. 본 논문은 최선 응답시간을 보다 정확하게 산정하고 활성화 지터의 한계를 줄이기 위해 새로운 최선 응답시간 분석기법을 제안한다. 제안된 기법은 태스크들간의 상대적 위상을 고려하여 최선 응답시간을 구한다. 활성화 지터의 정확한 분석은 다른 태스크들의 최악 응답시간을 감소시키고 스케쥴가능성을 증가시킨다. 모의실험의 결과는 제안된 분석 기법이 최선 응답시간과 최악 응답시간의 정확도를 각각 최대 40%와 6%로 개선함을 보여 준다. In distributed real-time system, a task activated by the completion of its preceding task can be modeled as a periodic task with activation jitter. An activation jitter of a task is defined as the difference between the worst case and the best case response time of its preceding task. Because the existing approaches assume that the best case response time is much smaller than the actual one, the activation jitter and the worst case response time of lower priority tasks are overestimated. This paper proposes a new analysis technique to calculate the best case response time more precisely and to reduce the activation jitter bounds. The proposed technique obtains the best case response time by considering the relative phase between tasks. The precise analysis of the activation jitters can reduce the worst case response time of other tasks and increase the schedulability. The simulation results show that the proposed analysis technique improves the accuracy of the best case and the worst case response time up to 40% and 6%, respectively.

긴급도와 최단 탐색시간 우선 방법에 기초한 실시간 디스크 스케쥴링

황기태(Kitae Hwang),신현식(Heonshik Shin) 한국정보과학회 1993 정보과학회논문지 Vol.20 No.8

이 논문은 UG-SSTF(Urgent Group and Shortest Seek Time First)라는 새로운 실시간 디스크 스케쥴링 알고리즘을 제안한다. 이 알고리즘은 디스크 큐 속의 긴급한 입출력 요구들의 그룹을 결정하고 그 중 최단 탐색시간을 가진 입출력 요구를 우선적으로 서비스한다. 이러한 방법에 의하여 UG-SSTF는 낮은 종료시한 실기율(miss ratio)을 달성할 수 있으며, 또한 연성 실시간 시스템의 전형적인 성능 요구 사항인 실기율과 종료시한 초과시간 사이의 이해득실을 제어하는 메카니즘을 제공한다. 시뮬레이션을 이용한 성능 평가의 결과 UG-SSTF는 실기율과 종료시한 초과시간 사이의 이해득실을 효과적으로 제어할 수 있으며, 기존의 알고리즘에 비해 24% 이상 실기율을 향상시킬 수 있다. This paper proposes a new real-time disk scheduling algorithm called Urgent Group and Shortest Seek Time First(UG-SSTF). It first selects urgent ones among the requests awaiting the disk service in a queue, and then services the urgent request with shortest seek time. Using this policy the UG-SSTF improves the miss ratio considerably. This algorithm also includes a mechanism to control the trade-off between the miss ratio and the tardy time which are two typical performance requirements of soft real-time systems. The proposed algorithm is shown to be able to control this trade-off effectively and improve the performance greater than 24% compared with current real-time disk scheduling algorithms through the simulation study.

주문형 멀티미디어 서버를 위한 혼합 비트율 스케쥴링

성민영(Min-Young Sung),신현식(HeonShik Shin) 한국정보과학회 1997 정보과학회논문지 : 시스템 및 이론 Vol.24 No.12

멀티미디어 데이타는 기존의 문자 위주의 데이타와는 달리 미디어 재생의 연속성을 보장하기 위해서는 시간 제약 조건을 만족시킬 수 있는 실시간 기법을 필요로 한다. 특히 가변 비트율로 압축된 비디오는 매우 심한 비트 변화율을 보이므로 이러한 미디어가 네트워크를 통해 온라인으로 전달될 경우 실시간적 특성은 필연적인 제약 조건이 된다. 그러나 이 분야에 있어서 대부분의 이전 연구들은 각 스트림이 고정 비트율을 가진다고 가정해 왔다. 물론 이러한 가정을 이용하는 것이 가능하지만 이 경우 과도한 자원 요구가 발생하거나 연속성이 지켜지지 않을 수 있다. 본 논문에서는 혼합 비트율 스케쥴링이라는 새로운 가변 비트율 기법을 제안하고 시스템 메모리를 이용한 적절한 미리 읽기를 통해 디스크 이용률을 개선할 수 있음을 밝힌다. 실험 결과, 본 논문에서 제안된 기법이 고정 비트율 기법에 비해 최고 161 %, 그리고 단순 가변 비트율 기법에 대해서는 18~26%의 성능 (동시에 서비스할 수 있는 요청의 최대수로 측정됨) 향상을 보였다. 혼합 비트율 기법의 주특징은 모든 요청에 대해 각 서비스 주기에 대한 디스크 대역 요구량 특정 임계값 이하로 한정하는 데에 있다. 이것은 이후에 도착할 요청의 수용 가능성을 높이는 요소가 된다. 또한 이 기법은 FIFO나 SCAN과 같은 디스크 스케쥴링과는 무관하게 적용될 수 있다는 점에서 매우 유연하다는 장점을 지닌다. Unlike traditional text-oriented data, multimedia data requires real-time techniques that satisfy the timing constraints to guarantee the continuity of media playback. Its real-time property is deemed indispensible when they are presented on-line over the network because variable-bit-rate(VBR) compressed video exhibits significant rate variability. Most of the prior research in this area assumed, however, that each individual stream has a constant-bit-rate(CBR). It is, of course, possible to use these schemes but then either too many resources are required or the quality of the stream is impaired. In this paper, a new VBR method, Hybrid-Bit-Rate(HBR) scheduling is proposed to improve the disk utilization through proper read-ahead using the system memory. The simulation results show that the system performance (measured by the maximum number of concurrent streams supported) can be improved by 18~26% as compared to simple VBR and by up to 161% as compared to CBR. The major characteristic of the HBR scheduling is that for each service round the requirement for the disk bandwidth is restricted to a predefined value and thus enhances the admissibility of later requests. It has also been found to be flexible because it can be applied irrespective of disk head scheduling policies like FIFO and SCAN.

대규모 주문형 비디오 서버의 큐잉 모델

조진성(Jinsung Cho),신현식(Heonshik Shin) 한국정보과학회 1997 한국정보과학회 학술발표논문집 Vol.24 No.1A

본 논문에서는 대규모 주문형 비디오 서비스를 위한 서버의 큐잉 모델을 설정하고 이를 통하여 성능을 분석한다. 주문형 비디오 서비스는 향후 초고속정보통신망에서 가장 큰 시장을 형성할 것으로 예측되고 있으며 이는 수천편의 영화를 저장하고 수만명의 사용자를 동시에 서비스할 수 있는 대규모 서버를 필요도 한다. 본 논문에서는 중소형 컴퓨터로 구성된 분산 시스템을 대상으로 하며 분산 시스템 내의 각 서버 노드들이 독립적으로 서비스를 수행한다. 제시된 큐잉 모델은 시뮬레이션에 의해 그 정확정이 검증되므로 대규모 서버의 설계시 도구로 유용하게 사용될 수 있다. 또한 큐잉 모델과 같은 수학적 모델에 의한 성능 분석을 그 정확성이 명백하며 실제 시스템은 물론 시뮬레이션에 의한 방법보다 훨씬 빠르게 이루어진다는 장점을 가진다.

ATM 스위치에서 QoS 보장을 위한 큐 서비스 방식의 설계

송민석(Minseok Song),신현식(Heonshik Shin) 한국정보과학회 1997 한국정보과학회 학술발표논문집 Vol.24 No.2Ⅲ

본 논문에서는 대역폭 할당이 용이한 기존의 WRR (Weighted Round Robin) 큐 서비스 방식을 이용하여 지터 한계 보장이 가능한 Rate-Controlled WRR 큐 서비스 방식을 제안한다. 기존의 WRR은 보장된 할당 대역폭, 남은 대역폭의 용이한 공유, 공평성으로 인하여 대역폭 할당 중심 정책을 사용하는 ATM에 적합한 것으로 알려져 있으나, 지터 한계의 보장이 안되어 버퍼 크기가 일정하지 않는 단점이 있다. 그러나, Rate-Controlled WRR 방식은 WRR 방식에 다중프레임 방식을 적용하여서, 다양한 지터 한계를 적용할 수 있을 뿐만 아니라, 다중 프레임 방식의 지터 한계의 상호 정수배 조건도 극복하게 되었다. 또한 비록 조절기(regulator)를 두었다고 하나, 패킷 보유의 기능만 하므로, 간단하게 구현이 가능해서 고속의 통신망에 적합하다. 아울러 본 논문에서는 ATM의 다양한 서비스 클래스의 QoS 보장을 위해서, CBR 트래픽은 Rate-Controlled WRR를 적용시키고, VBR 트래픽과 비실시간 트래픽도 이에 적합한 큐잉 정책을 적용하여 ATM망에서의 새로운 큐 서비스 방식을 제안한다.

분산 실시간 데이타베이스에서 2단계 종료 과정이 포함된 우선순위 방식의 동시실행 제어 프로토콜

김진환(Jinhwan Kim),신현식(Heonshik Shin) 한국정보과학회 데이터베이스 소사이어티 1994 데이타베이스 연구 Vol.10 No.3