{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,9,4]],"date-time":"2023-09-04T21:44:02Z","timestamp":1693863842918},"reference-count":19,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Syst."],"published-print":{"date-parts":[[1998,11]]},"abstract":"Decay-usage scheduling is a priority-aging time-sharing scheduling policy capable of dealing with a workload of both interactive and batch jobs by decreasing the priority of a job when it acquires CPU time, and by increasing its priority when it does not use the (a) CPU. In this article we deal with a decay-usage scheduling policy in multiprocessors modeled after widely used systems. The priority of a job consists of a base priority and a time-dependent component based on processor usage. Because t he priorities in our model are time dependent, a queuing-theoretic analysis\u2014for instance, for the mean job response time\u2014seems impossible. Still, it turns out that as a consequence of the scheduling policy, the shares of the available CPU time obtained by jobs converge, and a deterministic analysis for these shares is feasible: We show how for a fixed set of jobs with large processing demands, the steady-state shares can be obtained given the base priorities, and conversely, how to set the base priorities given the required shares. In addition, we analyze the relation between the values of the scheduler parameters and the level of control it can exercise over the steady-state share ratios, and we deal with the rate of convergence. We validate the model by simulations and by measurements of actual systems.<\/jats:p>","DOI":"10.1145\/292523.292535","type":"journal-article","created":{"date-parts":[[2002,7,27]],"date-time":"2002-07-27T11:28:46Z","timestamp":1027769326000},"page":"367-415","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":15,"title":["Decay-usage scheduling in multiprocessors"],"prefix":"10.1145","volume":"16","author":[{"given":"D. H. J.","family":"Epema","sequence":"first","affiliation":[{"name":"Delft Univ. of Technology, Delft, The Netherlands"}]}],"member":"320","published-online":{"date-parts":[[1998,11]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"The Design of the UNIX Operating System","author":"BACH M. J.","unstructured":"BACH , M. J. 1986. The Design of the UNIX Operating System . Prentice-Hall Software Series. Prentice-Hall , Inc., Upper Saddle River, NJ.]] BACH, M. J. 1986. The Design of the UNIX Operating System. Prentice-Hall Software Series. Prentice-Hall, Inc., Upper Saddle River, NJ.]]"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/2.53353"},{"key":"e_1_2_1_4_1","first-page":"551","article-title":"A comparison of basic CPU scheduling algorithms for multiprocessor UNIX","volume":"3","author":"CURRAN S.","year":"1990","unstructured":"CURRAN , S. AND STUMM , M. 1990 . A comparison of basic CPU scheduling algorithms for multiprocessor UNIX . Comput. Syst. 3 , 551 - 579 .]] CURRAN, S. AND STUMM, M. 1990. A comparison of basic CPU scheduling algorithms for multiprocessor UNIX. Comput. Syst. 3, 551-579.]]","journal-title":"Comput. Syst."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/75247.75248"},{"key":"e_1_2_1_6_1","first-page":"147","volume-title":"Proceedings of the","author":"ESSICK R. B.","year":"1990","unstructured":"ESSICK , R. B. 1990 . An event-based fair share scheduler . In Proceedings of the Winter 1990 USENIX Conference. USENIX Assoc., Berkeley, CA , 147 - 161 .]] ESSICK, R. B. 1990. An event-based fair share scheduler. In Proceedings of the Winter 1990 USENIX Conference. USENIX Assoc., Berkeley, CA, 147-161.]]"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/322203.322212"},{"key":"e_1_2_1_8_1","volume-title":"Tech. Rep. RC 20155","author":"FONG L. L.","year":"1995","unstructured":"FONG , L. L. AND SQUILLANTE , M. S. 1995 . Time-function scheduling: A general approach to controllable resource management . Tech. Rep. RC 20155 . Research Division, IBM, New York, NY.]] FONG, L. L. AND SQUILLANTE, M. S. 1995. Time-function scheduling: A general approach to controllable resource management. Tech. Rep. RC 20155. Research Division, IBM, New York, NY.]]"},{"key":"e_1_2_1_9_1","volume-title":"The Internals of UNIX System V Release 4: An Open Systems Design","author":"GOODHEART B.","unstructured":"GOODHEART , B. AND COX , J. 1994. The Magic Garden Explained , The Internals of UNIX System V Release 4: An Open Systems Design . Prentice-Hall, Inc. , Upper Saddle River, NJ.]] GOODHEART, B. AND COX, J. 1994. The Magic Garden Explained, The Internals of UNIX System V Release 4: An Open Systems Design. Prentice-Hall, Inc., Upper Saddle River, NJ.]]"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/146637.146658"},{"key":"e_1_2_1_11_1","first-page":"359","volume-title":"Proceedings of the","author":"HELLERSTEIN J. L.","year":"1992","unstructured":"HELLERSTEIN , J. L. 1992 . Control considerations for CPU scheduling in UNIX systems . In Proceedings of the Winter 1992 USENIX Conference. USENIX Assoc., Berkeley, CA , 359 - 374 .]] HELLERSTEIN, J. L. 1992. Control considerations for CPU scheduling in UNIX systems. In Proceedings of the Winter 1992 USENIX Conference. USENIX Assoc., Berkeley, CA, 359-374.]]"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/32.238584"},{"key":"e_1_2_1_13_1","first-page":"8","article-title":"The fair share scheduler. AT&T Bell","volume":"63","author":"HENRY G.J.","year":"1984","unstructured":"HENRY , G.J. 1984 . The fair share scheduler. AT&T Bell Lab. Tech. J. 63 , 8 (Oct.), 1845-1857.]] HENRY, G.J. 1984. The fair share scheduler. AT&T Bell Lab. Tech. J. 63, 8 (Oct.), 1845-1857.]]","journal-title":"Lab. Tech. J."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/35043.35047"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/321386.321388"},{"key":"e_1_2_1_16_1","volume-title":"The Design and Implementation of the 4.3BSD UNIX Operating System","author":"LEFFLER S. J.","unstructured":"LEFFLER , S. J. , McKu SICK , M. K. , KARELS , M. J. , AND QUARTERMAN , J. S. 1989. The Design and Implementation of the 4.3BSD UNIX Operating System . Addison-Wesley , Reading, MA .]] LEFFLER, S. J., McKuSICK, M. K., KARELS, M. J., AND QUARTERMAN, J. S. 1989. The Design and Implementation of the 4.3BSD UNIX Operating System. Addison-Wesley, Reading, MA.]]"},{"key":"e_1_2_1_17_1","volume-title":"The Design and Implementation of the 4.4BSD Operating System","author":"BOSTIC K.","unstructured":"McKusIcK, M. K., BOSTIC , K. , KARELS , M. J. , AND QUARTERMAN , J. S. 1996. The Design and Implementation of the 4.4BSD Operating System . Addison-Wesley , Reading, MA .]] McKusIcK, M. K., BOSTIC, K., KARELS, M. J., AND QUARTERMAN, J. S. 1996. The Design and Implementation of the 4.4BSD Operating System. Addison-Wesley, Reading, MA.]]"},{"key":"e_1_2_1_18_1","first-page":"915","volume-title":"Proceedings of the 11th Annual Joint Conference of the IEEE Computer and Communications Societies on One World through Communications (INFOCOM '92","author":"PAREKH A. K.","year":"1992","unstructured":"PAREKH , A. K. AND GALLAGER , R. G. 1992 . A generalized processor sharing approach to flow control in integrated services networks--the single node case . In Proceedings of the 11th Annual Joint Conference of the IEEE Computer and Communications Societies on One World through Communications (INFOCOM '92 , Florence, Italy, May 4-8). IEEE Computer Society Press, Los Alamitos, CA , 915 - 924 .]] PAREKH, A. K. AND GALLAGER, R. G. 1992. A generalized processor sharing approach to flow control in integrated services networks--the single node case. In Proceedings of the 11th Annual Joint Conference of the IEEE Computer and Communications Societies on One World through Communications (INFOCOM '92, Florence, Italy, May 4-8). IEEE Computer Society Press, Los Alamitos, CA, 915-924.]]"},{"key":"e_1_2_1_20_1","volume-title":"UNIX Internals: The New Frontiers","author":"VAHALIA U.","unstructured":"VAHALIA , U. 1996. UNIX Internals: The New Frontiers . Prentice-Hall, Inc. , Upper Saddle River, NJ.]] VAHALIA, U. 1996. UNIX Internals: The New Frontiers. Prentice-Hall, Inc., Upper Saddle River, NJ.]]"},{"key":"e_1_2_1_21_1","first-page":"1","volume-title":"Proceedings of the 1st USENIX Symposium on Operating Systems Design and Implementation. USENIX Assoc.","author":"WALDSPURGER C. A.","year":"1994","unstructured":"WALDSPURGER , C. A. AND WEIHL , W. E. 1994 . Lottery scheduling: Flexible proportional-share resource management . In Proceedings of the 1st USENIX Symposium on Operating Systems Design and Implementation. USENIX Assoc. , Berkeley, CA , 1 - 11 .]] WALDSPURGER, C. A. AND WEIHL, W. E. 1994. Lottery scheduling: Flexible proportional-share resource management. In Proceedings of the 1st USENIX Symposium on Operating Systems Design and Implementation. USENIX Assoc., Berkeley, CA, 1-11.]]"}],"container-title":["ACM Transactions on Computer Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/292523.292535","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,31]],"date-time":"2022-12-31T09:14:40Z","timestamp":1672478080000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/292523.292535"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,11]]},"references-count":19,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1998,11]]}},"alternative-id":["10.1145\/292523.292535"],"URL":"https:\/\/doi.org\/10.1145\/292523.292535","relation":{},"ISSN":["0734-2071","1557-7333"],"issn-type":[{"value":"0734-2071","type":"print"},{"value":"1557-7333","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,11]]},"assertion":[{"value":"1998-11-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}