In the long history of database communities, lots of research efforts had been done for reducing seek-times and rotational delays caused by mechanical components used in HDD (Hard Disk Drive). As an example of those efforts, some I/O scheduling algorithms were devised for the purpose of efficient services of online video streams being pumped up from HDD storage. To this end, a rate-reservation EDF is recently adopted to be incorporated into the recent platform built on flash storage. In this research, a fixed length of time is chosen as a period unit and the disk bandwidth assumption of each video stream is decided based on that time. The previous rate-reservation EDF algorithm is very suitable for serving a mixture of real-time requests and common requests without deadline. In this paper, we propose a new way that can dynamically compute the varying amounts of free bandwidth arising from more-than-reservation reading, while scheduling video streams according to the rate-reservation EDF algorithm. For this, we devised two data structures that can keep information about workloads and free bandwidth over a certain length of period units. Using scheduling information managed in those data structures, our proposed scheme can efficiently utilize slack times that occur unexpectedly from time to time. Because of the efficient reclamation of slack times, our scheme can improve the actual I/O performance of flash storage that is prepared for Web-based streaming services.

Flash Memory, Video Streaming, I/O Scheduling, Real-time EDF Algorithm

[1] Hofri Micha, “Disk Scheduling: FCFS vs SSTF Revisited," Communications of the ACM, Vol. 23, No 11, pp. 645-653, 1980.
[2] Houssine Chetto and Maryline Chetto, “Some Results of the Earliest Deadline Scheduling Algorithm," IEEE Transactions on Software Engineering, Vol. 15, No. 10, pp. 1261-1269, 1989.
[3] M. Seltzer, P. Chen, and J. Ousterhout, “Disk Scheduling Revisited," in Proc. of the USENIX Winter 1990, pp. 313-324, 1990.
[4] Pengliu Tan, Hai Jin, Minghu Zhang, “A Hybrid Scheduling Scheme for Hard, Soft and Non-Real-time Tasks,” In Proceedings of ISORC, pp. 20-26, 2006.
[5] Kang G. Shin and Yi-Chieh Chang, “A Reservation-Based Algorithm for Scheduling Both Periodic and Aperiodic Real-Time Tasks," IEEE Transactions on Computers, Vol. 44, No. 12, pp. 1405-1419, 1995.
[6] Xin Li, Zhiping Jia, Li Ma, Ruihua Zhang, and Haiyang Wang, “Earliest Deadline Scheduling for Continuous Queries over Data Streams,” In Proceedings of ICESS, pp. 57-64, 2009.
[7] Ray-I Chang, Wei-Kuan Shih, and Ruei-Chuan Chang, “Real-Time Disk Scheduling for Multimedia Applications with Deadline-Modification-Scan Scheme,” Real-Time Systems, Vol.19 , No. 2, pp. 149-168, 2000.
[8] R. K. Abbott and H. Garcia-Molina, “Scheduling I/O Requests with Deadlines: A Performance Evaluation," In Proceedings of the Real-Time Systems Symposium, pp. 113-125, 1990.
[9] E. Balafoutis, M. Paterkakis, and P. Triantallou, “Clustered Scheduling lgorithms for Mixed-Media Disk Workloads in a Multimedia Server," Cluster Computing Journal, Vol. 6, No. 1, pp. 75-86, 2003.
[10] Sungchae Lim, “The Dynamic Sweep Scheme using Slack Time in the Zoned Disk,” In Proceedings of 11st DASFAA, pp. 404-419, 2006.
[11] Mon-Song Chen, Dilip D. Kandlur, and P. Yu, “Optimization of Grouped Sweeping Scheduling (GSS) with Heterogeneous Multimedia Systems," In Proceedings of the ACM Multimedia, 1993.
[12] Seong-Chae Lim, “FlashEDF: An EDF-style Scheduling Scheme for Serving Real-time I/O Requests in Flash Storage,” Vol. 10, No. 3, pp. 26-34, 2018.
[13] Tzu-Jung Huang, Chien-Chung Ho, Po-Chun Huang, Yuan-Hao Chang, Che-Wei Chang, and Tei-Wei Kuo, “Current-aware Scheduling for Flash Storage Devices,” In Proceedings of IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, 2014.
[14] V. Indhumathi, TRP Maximization Technique based Efficient Scheduling in Grid Environment, Internatilal Journal of Scientific Research in Computer Sciences and Engineering, Vol.6, No. 2 , pp. 20-26, 2018.
[15] Vidhi Tiwari and Pratibha Adkar, Implementation of IoT in Home Automation using Android Application, Internatilal Journal of Scientific Research in Computer Sciences and Engineering, Vol.7, No. 2 , pp. 11-16, 2019.
[16] Cheng Ji, Li-Pin Chang, Chao Wu, Liang Shi, and Chun Jason Xue, “An I/O Scheduling Strategy for Embedded Flash Storage Devices With Mapping Cache,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 37, No. 4, 2018.
[17] Jaechun No and Sung-soon Park, “Exploiting the Effect of NAND Flash-Memory SSD on File System Design,” in Proc. of International Conference on Cyber-Enabled Distributed Computing and Knowledge Discovery. 2012.