×

Hardware design of a new genetic based disk scheduling method. (English) Zbl 1213.68197

Summary: Disk management is an increasingly important aspect of operating systems research and development because it has great effect on system performance. As the gap between processor and disk performance continues to increase in modern systems, access to mass storage is a common bottleneck that ultimately limits overall system performance. In this paper, we propose hardware architecture of a new genetic based real-time disk scheduling method. Also, to have a precise simulation, a neural network is proposed to simulate seek-time of disks. Simulation results showed the hardware implementation of proposed algorithm outperformed software implementation in term of execution time, and other related works in terms of number of tasks that miss deadlines and average seeks.

MSC:

68N25 Theory of operating systems
68T05 Learning and adaptive systems in artificial intelligence
68W05 Nonnumerical algorithms
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abbott R, Molina HG (1990) Scheduling I/O requests with deadlines: a performance evaluation. In: Proceedings of the IEEE real-time systems symposium, RTSS, pp 113–124
[2] Aboutabl M, Agrawala A, Decotignie JD (1997) Temporally determinate disk access: an experimental approach. In: Proceedings of the ACM SIGMETRICS joint international conference on measurement and modeling of computer systems, pp 280–281
[3] Buddhikot MM, Parulkar GM, Cox JR (1994) Design of a large scale multimedia storage server. J Comput Netw ISDN Syst 27(3):503–517 · Zbl 05479505 · doi:10.1016/0169-7552(94)90124-4
[4] Chang RI, Shih WK, Chang RC (1998) Deadline-modification-scan with maximum scannable-groups for multimedia real-time disk scheduling. In: Proceedings of the IEEE real-time systems symposium, pp 40–49
[5] Chang HP, Chang RI, Shih WK, Chang RC (2001) Reschedulable-group-scan scheme for mixed real-time/non-real-time disk scheduling in a multimedia system. J Syst Softw 59(2):143–152 · Zbl 05432360 · doi:10.1016/S0164-1212(01)00058-9
[6] Chang HP, Chang RI, Shih WK, Chang RC (2007) GSR: a global seek-optimizing real-time disk-scheduling algorithm. J Syst Softw 80(2):198–215 · Zbl 05434318 · doi:10.1016/j.jss.2006.03.045
[7] John SC, Stankovic JA, Kurose JF, Towsley D (1991) Performance evaluation of two new disk scheduling algorithms for real-time systems. J Real-Time Syst 3(3):307–336 · doi:10.1007/BF00364960
[8] Chen TS, Yang WP, Lee RCT (1992) Amortized analysis of some disk scheduling algorithms: SSTF, SCAN, and N-step SCAN. BIT 32(4):546–558 · Zbl 0757.68061 · doi:10.1007/BF01994839
[9] Chen PY, Chen RD, Chang YP, Shieh LS, Malki HA (2008) Hardware implementation for a genetic algorithm. IEEE Trans Instrum Meas 57(4):699–705 · doi:10.1109/TIM.2007.913807
[10] Chiueh TC, Huang L (2002) Track-based disk logging. In: Proceedings of international conference on dependable systems and networks, pp 429–438
[11] Coffman EG, Klimko LA, Ryan B (1972) Analysis of scanning policies for reducing disk seek times. SIAM J Comput 1(3):269–279 · Zbl 0248.68012 · doi:10.1137/0201018
[12] Demuth H, Beale M (1993) Neural network toolbox for use with Matlab. User Guide Version 4, The Mathworks, Inc
[13] Denning PJ (1967) Effects of scheduling on file memory operations. In: AFIPS joint computer conferences. Atlantic City, New Jersey, pp 9–21
[14] Geist R, Daniel S (1987) A continuum of disk scheduling algorithms. ACM Trans Comput Syst 5(1):77–92 · doi:10.1145/7351.8929
[15] Gemmell J, Christoduoulakis S (1992) Principles of delay sensitive multimedia data storage and retrieval. ACM Trans Inf Syst 10(1):51–90 · doi:10.1145/128756.128758
[16] Gim J, Won Y, Chang J, Shim J, Park Y (2008) DIG: rapid characterization of modern hard disk drive and its performance implication. In: 5th IEEE international workshop on in storage network architecture and parallel I/Os
[17] Hagan MT, Demuth HB, Beale M (1996) Neural network design. PWS, Boston
[18] Hofri M (1980) Disk scheduling: FCFS vs. SSTF revisited. Commun ACM 23(11):645–653 · doi:10.1145/359024.359034
[19] Holland JH (1975) Adaption in natural and artificial systems. University of Michigan Press, Ann Arbor
[20] Huang PC, Lu WC, Chou CN, Shih WK (2005) The NP-hardness and the algorithm for real-time disk-scheduling in a multimedia system. In: Proceedings of the 11th IEEE international conference on embedded and real-time computing systems and applications, RTCSA’05, Hong Kong, pp 260–265
[21] Hwang R, Gen M, Katayama H (2008) A comparison of multiprocessor task scheduling algorithm with communication cost. Comput Oper Res 35(3):976–993 · Zbl 1278.90159 · doi:10.1016/j.cor.2006.05.013
[22] Iyer S (2001) The effect of deceptive idleness on disk schedulers. Master’s thesis, Computer Science Department, Rice University
[23] Schindler J, Griffin JL, Lumb CR, Ganger GR (2002) Track-aligned extents: matching access patterns to disk drive characteristics. In: Proceedings of the 1st usenix symposium on file and storage technologies, FAST
[24] Lei T, Zhu MC, Wang JX (2002) The hardware implementation of a genetic algorithm model with FPGA. In: IEEE international conference on field-programmable technology, Hong Kong, pp 374–377
[25] Liu B, Rangaswami R, Dimitrijevic Z (2005) Thwarting virtual bottlenecks in multi-bitrate streaming servers. In: Proceedings of the real-time systems symposium WiP
[26] Lu LF, Yuan JJ (2007) The single machine batching problem with identical family setup times to minimize maximum lateness is strongly NP-hard. Eur J Oper Res 177(2):1302–1309 · Zbl 1109.90043 · doi:10.1016/j.ejor.2005.12.027
[27] Martin P (2002) An analysis of random number generators for a hardware implementation of genetic programming using FPGAs and Handel-C. In: Proceedings of the genetic and evolutionary computation conference, pp 837–844
[28] Selvi RM, Rajaram R (2007) Effect of cross over operation in genetic algorithms on anticipatory scheduling. In: 24th international symposium on automation & robotics in construction, ISARC
[29] Ökdem S, Karaboga D (2006) Optimal disk scheduling based on ant colony optimization algorithm. Erciyes Univ J Inst Sci Technol 22:11–19
[30] Plagemann T, Goebel V, Halvorsen P, Anshus O (2000) Operating system support for multimedia systems. Comput Commun J 23(3):267–289 · Zbl 05397034 · doi:10.1016/S0140-3664(99)00180-2
[31] Reddy ALN, Wyllie JC (1994) I/O issues in a multimedia system. IEEE Comput 27(3):69–74
[32] Reddy ALN, Wyllie J, Wijayaratne KBR (2005) Disk scheduling in a multimedia I/O system. ACM Trans Multimed Comput Commun Appl 1(1):37–59 · Zbl 05458348 · doi:10.1145/1047936.1047941
[33] Ruemmler C, Wilkes J (1994) An introduction to disc drive modeling. IEEE Comput 27(3):17–29
[34] Santos R, Lipari G, Santos J (2008) Improving the schedulability of soft real-time open dynamic systems: the inheritor is actually a debtor. J Syst Software 81(7):1093–1104 · Zbl 05434432 · doi:10.1016/j.jss.2007.07.004
[35] Schlosser SW, Schindler J, Papadomanolakis S, Shao M, Ailamaki A, Faloutsos C, Ganger GR (2005) On multidimensional data and modern disks. In: Proceedings of the 4th USENIX conference on file and storage technology, FAST ’05. San Francisco, pp 225–238
[36] Serra M, Slater T, Muzio JC, Miller DM (1990) The analysis of one-dimensional linear cellular automata and their aliasing properties. IEEE Trans Comput-Aided Des Integr Circuits Syst 9(7):767–778 · Zbl 05449641 · doi:10.1109/43.55213
[37] Sohn JM, Kim GY (1997) Earliest-deadline-first scheduling on nonpreemptive real-time threads for continuous media server. In: Proceedings of the conference on high-performance computing and networking
[38] Tachibana T, Murata Y, Shibata N, Yasumoto K, Ito M (2006) General architecture for hardware implementation of genetic algorithm. In: Proceedings of the 14th annual IEEE symposium on field-programmable custom computing machines, pp 291–292
[39] Tachibana T, Murata Y, Shibata N, Yasumoto K, Ito M (2007) Proposal of flexible implementation of genetic algorithms on FPGAs. Syst Comput Jpn 38(13):28–38 · Zbl 05441975 · doi:10.1002/scj.20779
[40] Tanenbaum AS (2001) Modern operating systems, 2nd edn. Prentice Hall, New York · Zbl 0967.68046
[41] Thomas S, Seshadri S, Haritsa JR (1996) Integrating standard transactions in firm real-time database systems. Inf Syst 21(1):3–28 · Zbl 05476582 · doi:10.1016/S0306-4379(96)00002-6
[42] Turton BCH, Arsalan T (1995) A parallel genetic VLSI architecture for combinatorial real-time applications-disk scheduling. In: IEEE international conference on genetic algorithms in engineering systems: innovations and applications, GALESIA, pp 493–498
[43] Ulusoy O, Belford GG (1993) Real-time transaction scheduling in database systems. Inf Syst 18(9):559–580 · doi:10.1016/0306-4379(93)90024-U
[44] Wong CK (1980) Minimizing expected head movement in one dimension and two dimensions mass storage system. ACM Comput Surv 12(2):167–178 · doi:10.1145/356810.356814
[45] Worthington BL, Ganger GR, Patt YN (1994) Scheduling algorithms for modern disk drives. In: Proceedings of ACM SIGMETRICS conference, pp 241–251
[46] Worthington BL, Ganger GR, Patt YN, Wilkes J (1995) On-line extraction of SCSI disk drive parameters. ACM SIGMETRICS Perform Eval Rev 23(1), 146–156 · doi:10.1145/223586.223604
[47] Wu AS, Yu H, Jin S, Lin KC, Schiavone G (2004) An incremental genetic algorithm approach to multiprocessor scheduling. IEEE Trans Parallel Distrib Syst 15(9):824–834 · Zbl 05107636 · doi:10.1109/TPDS.2004.38
[48] Yu PS, Chen MS, Kandlur DD (1992) Design and analysis of a grouped sweeping scheme for multimedia storage management. In: 3rd international workshop on network and operating system support for digital audio and video, SanDiego, California, pp 44–55
[49] Yu PS, Chen MS, Kandlur DD (1993) Grouped sweeping scheduling for DASD-based multimedia storage management. Multimed Syst 1(3):99–109 · doi:10.1007/BF01213198
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.