{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,22]],"date-time":"2024-07-22T09:13:48Z","timestamp":1721639628651},"reference-count":20,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2004,7]]},"abstract":"\n Scheduling a sequence of jobs released over time when the processing time of a job is only known at its completion is a classical problem in CPU scheduling in time sharing operating systems. A widely used measure for the responsiveness of the system is the average flow time of the jobs, that is, the average time spent by jobs in the system between release and completion.The Windows NT and the Unix operating system scheduling policies are based on the Multilevel Feedback algorithm. In this article, we prove that a randomized version of the Multilevel Feedback algorithm is competitive for single and parallel machine systems, in our opinion providing one theoretical validation of the goodness of an idea that has proven effective in practice along the last two decades.The randomized Multilevel Feedback algorithm (RMLF) was first proposed by Kalyanasundaram and Pruhs for a single machine achieving an\n O<\/jats:italic>\n (log\n n<\/jats:italic>\n log log\n n<\/jats:italic>\n ) competitive ratio to minimize the average flow time against the on-line adaptive adversary, where\n n<\/jats:italic>\n is the number of jobs that are released. We present a version of RMLF working for any number\n m<\/jats:italic>\n of parallel machines. We show for RMLF a first\n O<\/jats:italic>\n (log\n n<\/jats:italic>\n log\n n<\/jats:italic>\n \/\n m<\/jats:italic>\n ) competitiveness result against the oblivious adversary on parallel machines. We also show that the same RMLF algorithm surprisingly achieves a tight\n O<\/jats:italic>\n (log\n n<\/jats:italic>\n ) competitive ratio against the oblivious adversary on a single machine, therefore matching the lower bound for this case.\n <\/jats:p>","DOI":"10.1145\/1008731.1008732","type":"journal-article","created":{"date-parts":[[2004,7,20]],"date-time":"2004-07-20T16:39:33Z","timestamp":1090341573000},"page":"517-539","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":44,"title":["Nonclairvoyant scheduling to minimize the total flow time on single and parallel machines"],"prefix":"10.1145","volume":"51","author":[{"given":"Luca","family":"Becchetti","sequence":"first","affiliation":[{"name":"University of Rome \"La Sapienza\", Rome, Italy"}]},{"given":"Stefano","family":"Leonardi","sequence":"additional","affiliation":[{"name":"University of Rome \"La Sapienza\", Rome, Italy"}]}],"member":"320","published-online":{"date-parts":[[2004,7]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Acharya S. Muthukrishnan S. and Sundaram G. 1999. Scheduling data delivery over multiple channels. Tech. rep. Bell Labs Technical Memo. (Available from acharya@research. bell-labs.com.) Acharya S. Muthukrishnan S. and Sundaram G. 1999. Scheduling data delivery over multiple channels. Tech. rep. Bell Labs Technical Memo. (Available from acharya@research. bell-labs.com.)"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753970037446X"},{"key":"e_1_2_1_3_1","volume-title":"Introduction to Sequencing and Scheduling","author":"Baker K. R.","unstructured":"Baker , K. R. 1974. Introduction to Sequencing and Scheduling . Wiley , New York . Baker, K. R. 1974. Introduction to Sequencing and Scheduling. Wiley, New York."},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 20th Symposium on Theoretical Aspects of Computer Science (STACS). 260--270","author":"Bansal N.","unstructured":"Bansal , N. , Dhamdhere , K. , Konemann , J. , and Sinha , A . 2003. Non-clairvoyant scheduling for mean slowdown . In Proceedings of the 20th Symposium on Theoretical Aspects of Computer Science (STACS). 260--270 . Bansal, N., Dhamdhere, K., Konemann, J., and Sinha, A. 2003. Non-clairvoyant scheduling for mean slowdown. In Proceedings of the 20th Symposium on Theoretical Aspects of Computer Science (STACS). 260--270."},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 35th Symposium on Theory of Computing (STOC). ACM","author":"Bansal N.","unstructured":"Bansal , N. , and Pruhs , K . 2003. Server scheduling in the Lp norm: A rising tide lifts all boats . In Proceedings of the 35th Symposium on Theory of Computing (STOC). ACM , New York, 242--250. 10.1145\/780542.780580 Bansal, N., and Pruhs, K. 2003. Server scheduling in the Lp norm: A rising tide lifts all boats. In Proceedings of the 35th Symposium on Theory of Computing (STOC). ACM, New York, 242--250. 10.1145\/780542.780580"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.06.001"},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1007\/BF01294260","article-title":"On the power of randomization in on-line algorithms","volume":"11","author":"Ben-David S.","year":"1994","unstructured":"Ben-David , S. , Borodin , A. , Karp , R. , Tardos , G. , and Wigderson , A. 1994 . On the power of randomization in on-line algorithms . Algorithmica 11 , 2 -- 14 . Ben-David, S., Borodin, A., Karp, R., Tardos, G., and Wigderson, A. 1994. On the power of randomization in on-line algorithms. Algorithmica 11, 2--14.","journal-title":"Algorithmica"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM","author":"Bender M.","unstructured":"Bender , M. , Muthukrishnan , S. , and Rajaraman , R . 2002. Improved algorithms for stretch scheduling . In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM , New York, 762--771. Bender, M., Muthukrishnan, S., and Rajaraman, R. 2002. Improved algorithms for stretch scheduling. In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM, New York, 762--771."},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM","author":"Bender M. A.","unstructured":"Bender , M. A. , Chakrabarti , S. , and Muthukrishnan , S . 1998. Flow and stretch metrics for scheduling continuous job streams . In Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM , New York, 270--279. Bender, M. A., Chakrabarti, S., and Muthukrishnan, S. 1998. Flow and stretch metrics for scheduling continuous job streams. In Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM, New York, 270--279."},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 40th Annual IEEE Symposium Foundations of Computer Science (FOCS). IEEE Computer Society Press, Los Alamitos, Calif., 433--443","author":"Gehrke J. E.","unstructured":"Gehrke , J. E. , Muthukrishnan , S. , Rajaraman , R. , and Shaheen , A . 1999. Online scheduling to minimize avarage strech . In Proceedings of the 40th Annual IEEE Symposium Foundations of Computer Science (FOCS). IEEE Computer Society Press, Los Alamitos, Calif., 433--443 . Gehrke, J. E., Muthukrishnan, S., Rajaraman, R., and Shaheen, A. 1999. Online scheduling to minimize avarage strech. In Proceedings of the 40th Annual IEEE Symposium Foundations of Computer Science (FOCS). IEEE Computer Society Press, Los Alamitos, Calif., 433--443."},{"key":"e_1_2_1_12_1","unstructured":"IEEE. 1994. Institute for Electrical and Electronic Engineers. POSIX P1003.4a Threads Extensions for Portable Operating Systems. IEEE. 1994. Institute for Electrical and Electronic Engineers. POSIX P1003.4a Threads Extensions for Portable Operating Systems."},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95)","author":"Kalyanasundaram B.","unstructured":"Kalyanasundaram , B. , and Pruhs , K . 1995. Speed is as powerful as clairvoyance . In Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95) . IEEE Computer Society Press, Los Alamitos, Calif., 214--223. Kalyanasundaram, B., and Pruhs, K. 1995. Speed is as powerful as clairvoyance. In Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95). IEEE Computer Society Press, Los Alamitos, Calif., 214--223."},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 38th Annual Symposium on Foundations of Computer Science (Miami Beach, Fla., Oct. 20--22)","author":"Kalyanasundaram B.","unstructured":"Kalyanasundaram , B. , and Pruhs , K . 1997. Minimizing flow time nonclairvoyantly . In Proceedings of the 38th Annual Symposium on Foundations of Computer Science (Miami Beach, Fla., Oct. 20--22) . IEEE Computer Society Press, Los Alamitos Calif., 345--352. Kalyanasundaram, B., and Pruhs, K. 1997. Minimizing flow time nonclairvoyantly. In Proceedings of the 38th Annual Symposium on Foundations of Computer Science (Miami Beach, Fla., Oct. 20--22). IEEE Computer Society Press, Los Alamitos Calif., 345--352."},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 29th Annual ACM Symposium on Theory of Computing. ACM","author":"Leonardi S.","unstructured":"Leonardi , S. , and Raz , D . 1997. Approximating total flow time on parallel machines . In Proceedings of the 29th Annual ACM Symposium on Theory of Computing. ACM , New York, 110--119. 10.1145\/258533.258562 Leonardi, S., and Raz, D. 1997. Approximating total flow time on parallel machines. In Proceedings of the 29th Annual ACM Symposium on Theory of Computing. ACM, New York, 110--119. 10.1145\/258533.258562"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)90151-1"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the USENIX","author":"Mueller F.","year":"1993","unstructured":"Mueller , F. 1993 . A library implementation of POSIX threads under UNIX . In Proceedings of the USENIX Winter 1993 Technical Conference. 29--42. Mueller, F. 1993. A library implementation of POSIX threads under UNIX. In Proceedings of the USENIX Winter 1993 Technical Conference. 29--42."},{"key":"e_1_2_1_18_1","volume-title":"Operating System Projects using Windows NT","author":"Nutt G.","unstructured":"Nutt , G. 1999. Operating System Projects using Windows NT . Addison-Wesley , Reading, Mass . Nutt, G. 1999. Operating System Projects using Windows NT. Addison-Wesley, Reading, Mass."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2786.2793"},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","unstructured":"SUN. 1993. Sunos 5.3 system services. SUN. 1993. Sunos 5.3 system services.","DOI":"10.1002\/yd.23319936003"},{"key":"e_1_2_1_21_1","volume-title":"Modern Operating Systems","author":"Tanenbaum A. S.","unstructured":"Tanenbaum , A. S. 1992. Modern Operating Systems . Prentice-Hall , Englewood Cliffs, N.J. Tanenbaum, A. S. 1992. Modern Operating Systems. Prentice-Hall, Englewood Cliffs, N.J."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1008731.1008732","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T15:41:55Z","timestamp":1672242115000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1008731.1008732"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,7]]},"references-count":20,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2004,7]]}},"alternative-id":["10.1145\/1008731.1008732"],"URL":"https:\/\/doi.org\/10.1145\/1008731.1008732","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004,7]]},"assertion":[{"value":"2004-07-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}