{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:36:35Z","timestamp":1750307795585,"version":"3.41.0"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2008,2,1]],"date-time":"2008-02-01T00:00:00Z","timestamp":1201824000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Storage"],"published-print":{"date-parts":[[2008,2]]},"abstract":"<jats:p>We present a new disk scheduling framework to address the needs of a shared multimedia service that provides differentiated multilevel quality-of-service for mixed-media workloads. In such a shared service, requests from different users have different associated performance objectives and utilities, in accordance with the negotiated service-level agreements (SLAs). Service providers typically provision resources only for average workload intensity, so it becomes important to handle workload surges in a way that maximizes the utility of the served requests.<\/jats:p>\n          <jats:p>We capture the performance objectives and utilities associated with these multiclass diverse workloads in a unified framework and formulate the disk scheduling problem as a reward maximization problem. We map the reward maximization problem to a minimization problem on graphs and, by novel use of graph-theoretic techniques, design a scheduling algorithm that is computationally efficient and optimal in the class of seek-optimizing algorithms. Comprehensive experimental studies demonstrate that the proposed algorithm outperforms other disk schedulers under all loads, with the performance improvement approaching 100% under certain high load conditions. In contrast to existing schedulers, the proposed scheduler is extensible to new performance objectives (workload type) and utilities by simply altering the reward functions associated with the requests.<\/jats:p>","DOI":"10.1145\/1326542.1326546","type":"journal-article","created":{"date-parts":[[2008,2,28]],"date-time":"2008-02-28T14:02:33Z","timestamp":1204207353000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["A utility-based unified disk scheduling framework for shared mixed-media services"],"prefix":"10.1145","volume":"3","author":[{"given":"Akshat","family":"Verma","sequence":"first","affiliation":[{"name":"IBM India Research Lab, New Delhi, India"}]},{"given":"Rohit","family":"Jain","sequence":"additional","affiliation":[{"name":"IBM India Research Lab, New Delhi, India"}]},{"given":"Sugata","family":"Ghosal","sequence":"additional","affiliation":[{"name":"IBM India Research Lab, New Delhi, India"}]}],"member":"320","published-online":{"date-parts":[[2008,2,25]]},"reference":[{"volume-title":"the IEEE International Conference on Multimedia and Expo (ICME).","author":"Aggarwal G.","key":"e_1_2_1_1_1","unstructured":"Aggarwal , G. , Dubey , P. K. , Ghosal , S. , Kulshreshtha , A. , and Sarkar , A . 2000. iPURE: Perceptual and user-friendly retrieval of images . In the IEEE International Conference on Multimedia and Expo (ICME). Aggarwal, G., Dubey, P. K., Ghosal, S., Kulshreshtha, A., and Sarkar, A. 2000. iPURE: Perceptual and user-friendly retrieval of images. In the IEEE International Conference on Multimedia and Expo (ICME)."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0071-1"},{"volume-title":"Proceedings of the International Conference on Multimedia Computing and Systems.","author":"Bruno J.","key":"e_1_2_1_3_1","unstructured":"Bruno , J. , Brustoloni , J. , Gabber , E. , Ozden , B. , and Silberschatz , A . 1999. Disk scheduling with quality of service guarantees . In Proceedings of the International Conference on Multimedia Computing and Systems. Bruno, J., Brustoloni, J., Gabber, E., Ozden, B., and Silberschatz, A. 1999. Disk scheduling with quality of service guarantees. In Proceedings of the International Conference on Multimedia Computing and Systems."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/502034.502045"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00364960"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2005.116"},{"key":"e_1_2_1_7_1","unstructured":"Department of Distributed Systems. 2007. Index of MPEG traces. http:\/\/www3.informatik. uni-wuerzburg.de\/MPEG\/traces.  Department of Distributed Systems. 2007. Index of MPEG traces. http:\/\/www3.informatik. uni-wuerzburg.de\/MPEG\/traces."},{"key":"e_1_2_1_8_1","volume-title":"Tech. Rep. CSE-TR-358-98, Department of Electrical Engineering and Computer Science","author":"Ganger G. R.","year":"1999","unstructured":"Ganger , G. R. , Worthington , B. L. , and Patt , Y. N . 1999 . The DiskSim simulation environment: Version 2.0 reference manual. Tech. Rep. CSE-TR-358-98, Department of Electrical Engineering and Computer Science , University of Michigan. Ganger, G. R., Worthington, B. L., and Patt, Y. N. 1999. The DiskSim simulation environment: Version 2.0 reference manual. Tech. Rep. CSE-TR-358-98, Department of Electrical Engineering and Computer Science, University of Michigan."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TMM.2003.811623"},{"key":"e_1_2_1_10_1","volume-title":"Tech. Rep. HPL-95-71, HP Labs.","author":"Gallo G.","year":"1995","unstructured":"Gallo , G. , Malucelli , F. , and Marre , M . 1995 . Hamiltonian paths algorithms for disk scheduling. Tech. Rep. HPL-95-71, HP Labs. Gallo, G., Malucelli, F., and Marre, M. 1995. Hamiltonian paths algorithms for disk scheduling. Tech. Rep. HPL-95-71, HP Labs."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1147\/sj.422.0347"},{"key":"e_1_2_1_12_1","unstructured":"Huang L. and Chiueh T. 2002. Experiences in building a software-based SATF scheduler. Tech. Rep. State University of New York at StonyBrook July.  Huang L. and Chiueh T. 2002. Experiences in building a software-based SATF scheduler. Tech. Rep. State University of New York at StonyBrook July."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1005686.1005692"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1019244621570"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/1032647.1033302"},{"volume-title":"Proceedings of the ACM Conference on Electronic Commerce (EC), 213--223","author":"Jin W.","key":"e_1_2_1_16_1","unstructured":"Jin , W. , Chase , J. S. , and Kaur , J . 2004. Access method concurrency with recovery . In Proceedings of the ACM Conference on Electronic Commerce (EC), 213--223 . Jin, W., Chase, J. S., and Kaur, J. 2004. Access method concurrency with recovery. In Proceedings of the ACM Conference on Electronic Commerce (EC), 213--223."},{"key":"e_1_2_1_17_1","article-title":"On maximizing service level agreement profits.ACM","author":"Liu Z.","year":"2001","unstructured":"Liu , Z. , Squillante , M. S. , and Wolf , J. L. 2001 . On maximizing service level agreement profits.ACM Trans. Comput. Syst. Liu, Z., Squillante, M. S., and Wolf, J. L. 2001. On maximizing service level agreement profits.ACM Trans. Comput. Syst.","journal-title":"Trans. Comput. Syst."},{"volume-title":"Proceedings of the USENIX Conference on File and Storage Technologies (FAST).","author":"Lumb C.","key":"e_1_2_1_18_1","unstructured":"Lumb , C. , Merchant , A. , and Alvarez , G. A . 2003. Fa\u00e7ade: Virtual storage devices with performance guarantees . In Proceedings of the USENIX Conference on File and Storage Technologies (FAST). Lumb, C., Merchant, A., and Alvarez, G. A. 2003. Fa\u00e7ade: Virtual storage devices with performance guarantees. In Proceedings of the USENIX Conference on File and Storage Technologies (FAST)."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/957013.957024"},{"volume-title":"the International Conference on Data Engineering.","author":"Mokbel M. F.","key":"e_1_2_1_20_1","unstructured":"Mokbel , M. F. , Aref , W. G. , El-Bassyouni , K. , and Kamel , I . 2005. Scalable multimedia disk scheduling . In the International Conference on Data Engineering. Mokbel, M. F., Aref, W. G., El-Bassyouni, K., and Kamel, I. 2005. Scalable multimedia disk scheduling. In the International Conference on Data Engineering."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(77)90012-3"},{"key":"e_1_2_1_22_1","unstructured":"PC Technology Guide. 2004. Storage-Hard disks. http:\/\/www.pctechguide.com\/04disks.htm.  PC Technology Guide. 2004. Storage-Hard disks. http:\/\/www.pctechguide.com\/04disks.htm."},{"key":"e_1_2_1_23_1","unstructured":"PC Technology Guide. 2002. Components-Processors. http:\/\/www.pctechguide.com\/02procs.htm.  PC Technology Guide. 2002. Components-Processors. http:\/\/www.pctechguide.com\/02procs.htm."},{"volume-title":"Proceedings of the USENIX Annual Technical Conference, 297--310","author":"Popovici F. I.","key":"e_1_2_1_24_1","unstructured":"Popovici , F. I. , Arpaci-Dusseau , A. C. , and Arpaci-Dusseau , R. H . 2003. Robust, portable I\/O scheduling with the disk mimic . In Proceedings of the USENIX Annual Technical Conference, 297--310 . Popovici, F. I., Arpaci-Dusseau, A. C., and Arpaci-Dusseau, R. H. 2003. Robust, portable I\/O scheduling with the disk mimic. In Proceedings of the USENIX Annual Technical Conference, 297--310."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/166266.166292"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/290747.290785"},{"key":"e_1_2_1_27_1","volume-title":"Tech. Rep. CMU-CS-99-176","author":"Schindler J.","year":"1999","unstructured":"Schindler , J. and Ganger , G. R . 1999 . Automated disk drive characterization. Tech. Rep. CMU-CS-99-176 , Carnegie Mellon University , December. Schindler, J. and Ganger, G. R. 1999. Automated disk drive characterization. Tech. Rep. CMU-CS-99-176, Carnegie Mellon University, December."},{"volume-title":"the USENIX Conference on File and Storage Technologies (FAST).","author":"Schindler J.","key":"e_1_2_1_28_1","unstructured":"Schindler , J. , Griffin , J. L. , Lumb , C. R. , and Ganger , G. R . 2002. Track-Aligned extents: Matching access patterns to disk drive characteristics . In the USENIX Conference on File and Storage Technologies (FAST). Schindler, J., Griffin, J. L., Lumb, C. R., and Ganger, G. R. 2002. Track-Aligned extents: Matching access patterns to disk drive characteristics. In the USENIX Conference on File and Storage Technologies (FAST)."},{"key":"e_1_2_1_29_1","unstructured":"Seagate Corporation. 2007. Cheetah4LP disk specification datasheet. http:\/\/www.seagate.com.  Seagate Corporation. 2007. Cheetah4LP disk specification datasheet. http:\/\/www.seagate.com."},{"volume-title":"Proceedings of the USENIX Winter Technical Conference, 313--324","author":"Seltzer M.","key":"e_1_2_1_30_1","unstructured":"Seltzer , M. , Chen , P. , and Ousterhout , J . 1990. Disk scheduling revisited . In Proceedings of the USENIX Winter Technical Conference, 313--324 . Seltzer, M., Chen, P., and Ousterhout, J. 1990. Disk scheduling revisited. In Proceedings of the USENIX Winter Technical Conference, 313--324."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s005300050126"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/277851.277871"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/775152.775171"}],"container-title":["ACM Transactions on Storage"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1326542.1326546","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1326542.1326546","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:56:25Z","timestamp":1750254985000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1326542.1326546"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,2]]},"references-count":33,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2008,2]]}},"alternative-id":["10.1145\/1326542.1326546"],"URL":"https:\/\/doi.org\/10.1145\/1326542.1326546","relation":{},"ISSN":["1553-3077","1553-3093"],"issn-type":[{"type":"print","value":"1553-3077"},{"type":"electronic","value":"1553-3093"}],"subject":[],"published":{"date-parts":[[2008,2]]},"assertion":[{"value":"2007-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2007-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-02-25","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}