{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:35:58Z","timestamp":1750307758615,"version":"3.41.0"},"reference-count":17,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2007,12,1]],"date-time":"2007-12-01T00:00:00Z","timestamp":1196467200000},"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. Embed. Comput. Syst."],"published-print":{"date-parts":[[2007,12]]},"abstract":"<jats:p>A typical design process for real-time embedded systems involves choosing the values of certain system parameters and performing a schedulability analysis to determine whether all deadline constraints can be satisfied. If such an analysis returns a negative answer, then some of the parameters are modified and the analysis is invoked once again. This iteration is repeated until a schedulable design is obtained. However, the schedulability analysis problem for most task models is intractable (usually co-NP hard) and, hence, such an iterative design process is often very expensive. To get around this problem, we introduce the concept of \u201cinteractive\u201d schedulability analysis. It is based on the observation that if only a small number of system parameters are changed, then it is not necessary to rerun the full schedulability analysis algorithm, thereby making the iterative design process considerably faster. We refer to this analysis as being \u201cinteractive\u201d because it is supposed to be run in an interactive mode. This concept is fairly general and can be applied to a wide variety of task models. In this paper, we have chosen the recurring real-time task model, because it can be used to represent realistic applications from the embedded systems domain (containing conditional branches and fine-grained deadline constraints). Our experimental results show that using our scheme can lead to more than 20\u00d7 speedup for each invocation of the schedulability analysis algorithm, compared to the case where the full algorithm is run.<\/jats:p>","DOI":"10.1145\/1324969.1324976","type":"journal-article","created":{"date-parts":[[2008,1,18]],"date-time":"2008-01-18T18:45:29Z","timestamp":1200681929000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Interactive schedulability analysis"],"prefix":"10.1145","volume":"7","author":[{"given":"Unmesh D.","family":"Bordoloi","sequence":"first","affiliation":[{"name":"National University of Singapore, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Samarjit","family":"Chakraborty","sequence":"additional","affiliation":[{"name":"National University of Singapore, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2007,12,12]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/1009383.1009837"},{"key":"e_1_2_1_2_1","series-title":"Lecture Notes in Computer Science 2791","volume-title":"TIMES: A tool for schedulability analysis and code generation of real-time systems. In International Workshop on Formal Modeling and Analysis of Timed Systems","author":"Amnell T.","year":"2003"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/EMWRTS.1998.685078"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/827270.829061"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1021711220939"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008030427220"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS.2005.32"},{"key":"e_1_2_1_8_1","unstructured":"Buttazzo G. 1997. Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications. Kluwer Academic Publ. Boston MA.   Buttazzo G. 1997. Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications. Kluwer Academic Publ. Boston MA."},{"volume":"2125","volume-title":"Proceedings of the International Workshop on Algorithms and Data Structures. Lecture Notes in Computer Science","author":"Chakraborty S.","key":"e_1_2_1_9_1"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/513918.514075"},{"volume-title":"Proceedings of the IEEE Real-Time Systems Symposium","author":"Chakraborty S.","key":"e_1_2_1_11_1"},{"volume-title":"IEEE International Symposium on Human-Centric Computing Languages and Environments. IEEE Computer Society","author":"Esser R.","key":"e_1_2_1_12_1"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/ECRTS.2005.1"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/REAL.2004.17"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/32.637146"},{"volume-title":"Proceedings of the International Workshop on Real-Time Computing Systems and Applications","author":"Takada H.","key":"e_1_2_1_16_1"},{"volume-title":"Proceedings the IEEE International Computer Software and Applications Conference","author":"Tokuda H.","key":"e_1_2_1_17_1"}],"container-title":["ACM Transactions on Embedded Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1324969.1324976","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1324969.1324976","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:39:27Z","timestamp":1750253967000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1324969.1324976"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,12]]},"references-count":17,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2007,12]]}},"alternative-id":["10.1145\/1324969.1324976"],"URL":"https:\/\/doi.org\/10.1145\/1324969.1324976","relation":{},"ISSN":["1539-9087","1558-3465"],"issn-type":[{"type":"print","value":"1539-9087"},{"type":"electronic","value":"1558-3465"}],"subject":[],"published":{"date-parts":[[2007,12]]},"assertion":[{"value":"2008-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2006-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2007-12-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}