With fast advances in the computing power and networking technologies, demands for presentations of time-based data increasingly grow in the computing industry. Time-based data such as digitized video and sound are frequently called the continuous media since the playback of such data requires continuous data retrievals during the period of play-back. For the continuous media playbacks, disk-resident data should be read for the online delivery towards a client's device so that the device continuously consumes data at a specific rate in order to reproduce a sequence of frames or sampled sounds. This requirement for the continuous media playback is referred to continuity requirement. Such continuity requirement should be fulfilled by a continuous media server that provides concurrent play-backs of continuous streams in online mode. To this end, the continuous media server is designed to have a deliberated algorithm for real-time disk scheduling meeting the continuity requirements of simultaneous continuous media streams. Besides the data requests from continuous media streams, there may exist data requests asking for time-independent data such as images, textual files, HTML documents stored in the continuous media server. Therefore, the continuous media server also needs to provide a mechanism to read time-independent data without missing deadlines of continuous requests. The mixed service of continuous requests and time-independent requests is a tough problem to be tackled in this dissertation.
In this dissertation, we first develop a new scheduling method combining the EDF algorithm with the SCAN algorithm to service a number of continuous media streams. In the previous works, the combination of these two algorithms has been done such a limited way that the SCAN algorithm is applied for a small number of data requests with the same deadline. Since the SCAN algorithm cannot reverse the direction of disk head movement for a long while and retrieval orders of data requests depend on their disk locations, rather than their deadline urgencies, it is very hard to efficiently adapt the SCAN algorithm for serving data requests with different deadlines. In other words, the SCAN algorithm is inherently lack of real-time features, although it is the best scheduling algorithm in terms of the seek time optimization. Against such problems in the SCAN algorithm, we build a nice bridge between those algorithms by using data request patterns assigned to each stream and I/O capacity estimations based on the lowest upper bound of disk times taken to perform a disk scan. In our method, the served continuous media streams have a variety of sizes of scheduling periods and each of streams issues data requests according to its specific scheduling period. Then a number of data requests with different deadlines can be served in the same disk scan in order to provide a good seek optimization. Because disk schedules conforming to our scheduling algorithm ensure the scheduling capability equal to or greater than that guaranteed by the well-known EDF scheduler, deadlines of data requests are always satisfied while we admit new streams under 100% of I/O utilization. Due to the high scheduling flexibility and seek optimization, the proposed method outperforms the previous methods.
To go beyond the proposed algorithm for serving continuous media streams, we also propose some interesting mechanisms that can utilize free disk times for the fast service of discrete requests, while meeting deadlines of periodic requests. Here, the discrete requests are the data requests issued for reading time-independent data such as images, HTML documents, and Flash data. To this end, we devise a method that can bookkeep the minimum disk time needed to meet the deadlines of continuous data requests and maximize scheduling flexibility in the use of free disk times. For such flexibility, we use the workload look-ahead table (WLT) in which the future's workloads of continuous requests are estimated. The workload estimations are managed with respect to the streams with the same deadline, i.e., we compute the overall workloads of continuous data requests issued by the streams with the same deadline. By managing workloads having the same deadline, we can produce more flexible disk schedules by distributing workloads across longer time intervals containing workloads of data requests with the same deadline. To enlarge the extent of workloads of continuous requests with the same deadline, we adopt the rate-reservation algorithm for the workload estimations. Along with the WLT, we proposed the use of the earlier service record (ESR) for the estimation of accumulated free times. When we serve continuous requests in an earlier time than expected, by using the free disk time, earlier service of them is bookkept in the ESR and the corresponding workload in the WLT is adjusted for the fast service of discrete data requests during the time in which the adjusted workload occurs.
To show the better performance of the proposed method over other prior methods, we implement several simulators for other methods such as Sweep, Fixed-Stretch, GSS, and Optimal. In addition, we make some modifications to these earlier methods so that they can service a mixed workload of periodic and discrete requests. Then we experiment with many methods to evaluate scheduling efficiency in the service of mixed workloads.
Through extensive simulations, we show the performance characteristics of a variety of disk scheduling methods, and analyze weak points and merits of them in a fair and scientific way.
최근에 급속도로 이루어진 네트워크 기술 및 컴퓨팅 속도의 발전으로 말미암아 동영상이나 음악파일과 같은 상연에 시간제약성을 가진 연속매체의 온라인 상연이 가능해졌다. 이런 연속매체 상연에 대한 요구는 World Wide Web의 발전과 함께 빠르게 증가하고 있는 상황이다. 연속매체의 상연을 위해서는 일정한 속도 이상으로 디스크내의 데이터를 읽어야 하는 연속성제약이 만족되어야 하며, 여러 개의 연속매체 스트림을 동시에 상연해야 하는 시스템의 경우 이런 제약성을 만족시킬 수 있는 실시간 스케줄링 기법이 필요하다. 연속매체 스트림과 함께 이미지 파일이나 Html 파일과 같은 정적인 데이터도 함께 읽혀지는 경우가 일반적이므로 효과적인 상연시스템 구축을 위해서는 연속매체를 위한 시간제약성을 지키면서도 정적인 데이터를 보다 빠르게 읽어 들일 수 있는 다소 복합적인 디스크 스케줄링 기법이 역시 요구되고 있다.
본 논문에서는 연속매체 상연시스템을 위한 디스크 스케줄링 기법이 연구된다. 제안하는 알고리즘은 EDF (Earliest Deadline First) 알고리즘과 디스크 SCAN 알고리즘을 혼용한 알고리즘으로서 상연되는 스트림 별로 각기 다른 스케줄링 패턴에 따른 디스크 대역폭할당이 가능하다는 장점이 있다. 또한 제안한 방법에서는 디스크 서비스 시간 중에 자주 발생하는 여유시간들을 모아 정적데이터를 읽는데 사용할 수 있다는 장점이 있다. 가장 최적의 성능을 내기 위해 본 논문에서는 향후 발생할 데이터 읽기의 작업량을 측정하는 기법이 제안되며 이를 통해 정적데이터에 대한 요청이 있는 경우에는 가장 최소량의 디스크 대역폭만이 연속매체에 할당된다. 연속성제약을 만족시키는 최소량의 디스크 대역폭을 제외한 남은 디스크 시간은 정정데이터 서비스에 모두 이용 가능하므로 제안하는 알고리즘은 이 두 가지 형태의 데이터 서비스를 위한 최적의 성능을 제공한다. 제안된 알고리즘 성능의 우수성을 보이기 위해 시뮬레이션 기법이 이용되며, 다양한 방법의 시뮬레이션을 통해 다른 기존의 기법들에 대비되는 성능 및 특성이 분석된다.
