{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:56:23Z","timestamp":1750308983136,"version":"3.41.0"},"reference-count":23,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2017,11,22]],"date-time":"2017-11-22T00:00:00Z","timestamp":1511308800000},"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":["SIGBED Rev."],"published-print":{"date-parts":[[2017,11,22]]},"abstract":"<jats:p>\n            Many solutions for composability and compositionality rely on specifying the interface for a component using bandwidth. Some previous works specify period (P) and budget (Q) as an interface for a component.\n            <jats:italic>Q\/P<\/jats:italic>\n            provides us with a bandwidth (the share of a processor that this component may request);\n            <jats:italic>P<\/jats:italic>\n            specifies the time granularity of the allocation of this processing capacity. Other works add another parameter,\n            <jats:italic>deadline<\/jats:italic>\n            , which can help to provide tighter bounds on how this processing capacity is distributed. Yet other works use the parameters \u03b1 and \u0394 where \u03b1 is the bandwidth and \u0394 specifies how smoothly this bandwidth is distributed. It is known [4] that such bandwidth-like interfaces carry a cost: there are tasksets that could be guaranteed to be schedulable if tasks were scheduled directly on the processor, but with bandwidth-like interfaces, it is impossible to guarantee the taskset to be schedulable. It is known that this penalty can be infinite, i.e., the use of bandwidth-like interfaces may require the use of a processor that has a speed that is\n            <jats:italic>k<\/jats:italic>\n            times faster, and one can show this for any\n            <jats:italic>k.<\/jats:italic>\n            This brings the following question: \"What is the average-case performance penalty of bandwidth-like interfaces?\" A previous paper [5] has partially answered this question by stating an expression on this penalty as a function of taskset parameters and then randomly generated tasksets to obtain a probability distribution of this penalty. In this paper, we answer this question analytically for the case that the taskset has tasks with infinite minimum inter-arrival time, equal task density, uniformly distributed deadlines, and the number of tasks approaches infinity. For this specific case, we derive an expression; if deadlines are uniformly distributed in [0,1], then we find that the penalty is two. We also run experiments to explore systems with these assumptions but for finite number of tasks. From these experiments, we conclude that (i) the larger the number of tasks is, the larger the penalty is, (ii) the larger the number of tasks is, the less skewed the probability distribution is, and (iii) the larger the number of tasks is, the smaller the variance of the penalty is. We are currently working on the case where deadlines follow other distributions.\n          <\/jats:p>","DOI":"10.1145\/3166227.3166229","type":"journal-article","created":{"date-parts":[[2017,11,27]],"date-time":"2017-11-27T13:24:24Z","timestamp":1511789064000},"page":"16-23","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Deriving the average-case performance of bandwidth-like interfaces for tasksets with infinite minimum inter-arrival time, equal task density, uniformly distributed deadlines, and infinite number of tasks"],"prefix":"10.1145","volume":"14","author":[{"given":"Bj\u00f6rn","family":"Andersson","sequence":"first","affiliation":[{"name":"Carnegie Mellon University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hyoseung","family":"Kim","sequence":"additional","affiliation":[{"name":"University of California"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"John","family":"Lehoczky","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dionisio","family":"de Niz","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,11,22]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"RTSS","author":"Abeni L.","year":"1988","unstructured":"L. Abeni and G. Buttazzo . Integrating multimedia applications in hard real-time systems . In RTSS , 1988 . L. Abeni and G. Buttazzo. Integrating multimedia applications in hard real-time systems. In RTSS, 1988."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1017753.1017772"},{"key":"e_1_2_1_3_1","volume-title":"CRTS","author":"Andersson B.","year":"2009","unstructured":"B. Andersson . A pseudo-medium-wide 8-competitive interface for two-level compositional real-time scheduling of constrained-deadline sporadic tasks on a uniprocessor . In CRTS , 2009 . B. Andersson. A pseudo-medium-wide 8-competitive interface for two-level compositional real-time scheduling of constrained-deadline sporadic tasks on a uniprocessor. In CRTS, 2009."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1967021.1967024"},{"key":"e_1_2_1_5_1","volume-title":"CRTS","author":"Andersson B.","year":"2015","unstructured":"B. Andersson . Evaluating the average-case performance penalty of bandwidth-like interfaces . In CRTS , 2015 . B. Andersson. Evaluating the average-case performance penalty of bandwidth-like interfaces. In CRTS, 2015."},{"key":"e_1_2_1_6_1","volume-title":"CRTS","author":"Andersson B.","year":"2016","unstructured":"B. Andersson , H. Kim , J. Lehoczky , and D. de Niz . Deriving the average-case performance of bandwidth-like interfaces for tasksets with infinite minimum inter-arrival time, equal task density, uniformly distributed deadlines, and infinite number of tasks . In CRTS , 2016 . B. Andersson, H. Kim, J. Lehoczky, and D. de Niz. Deriving the average-case performance of bandwidth-like interfaces for tasksets with infinite minimum inter-arrival time, equal task density, uniformly distributed deadlines, and infinite number of tasks. In CRTS, 2016."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01995675"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTCSA.2009.62"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1289927.1289970"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS.2006.42"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/827269.828992"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.26.1.127"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS.2007.17"},{"key":"e_1_2_1_14_1","volume-title":"RTSS","author":"Feng X.","year":"2002","unstructured":"X. Feng and A. K. Mok . A model of hierarchical real-time virtual resources . In RTSS , 2002 . X. Feng and A. K. Mok. A model of hierarchical real-time virtual resources. In RTSS, 2002."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS.2014.11"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTAS.2012.20"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/REAL.1989.63567"},{"key":"e_1_2_1_18_1","volume-title":"RTSS","author":"Lehoczky J. P.","year":"1987","unstructured":"J. P. Lehoczky , L. Sha , and J. K. Strosnider . Enhanced aperiodic responsiveness in hard real-time environments . In RTSS , 1987 . J. P. Lehoczky, L. Sha, and J. K. Strosnider. Enhanced aperiodic responsiveness in hard real-time environments. In RTSS, 1987."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/882481.883791"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/EMRTS.2003.1212738"},{"key":"e_1_2_1_21_1","volume-title":"RTSS","author":"Shin I.","year":"2003","unstructured":"I. Shin and I. Lee . Periodic resource model for compositional real-time guarantees . In RTSS , 2003 . I. Shin and I. Lee. Periodic resource model for compositional real-time guarantees. In RTSS, 2003."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISCAS.2000.858698"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2038642.2038651"}],"container-title":["ACM SIGBED Review"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3166227.3166229","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3166227.3166229","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T21:41:06Z","timestamp":1750282866000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3166227.3166229"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,11,22]]},"references-count":23,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,11,22]]}},"alternative-id":["10.1145\/3166227.3166229"],"URL":"https:\/\/doi.org\/10.1145\/3166227.3166229","relation":{},"ISSN":["1551-3688"],"issn-type":[{"type":"electronic","value":"1551-3688"}],"subject":[],"published":{"date-parts":[[2017,11,22]]},"assertion":[{"value":"2017-11-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}