{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,20]],"date-time":"2026-03-20T16:13:57Z","timestamp":1774023237471,"version":"3.50.1"},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2019,3,31]],"date-time":"2019-03-31T00:00:00Z","timestamp":1553990400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Netherlands Organisation for Scientific Research (NWO) through the Gravitation Programme Networks","award":["024.002.003"],"award-info":[{"award-number":["024.002.003"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Parallel Comput."],"published-print":{"date-parts":[[2019,3,31]]},"abstract":"<jats:p>A model is considered for representing recurrent precedence-constrained tasks that are to execute on multiprocessor platforms. A recurrent task is specified as a directed acyclic graph (DAG), a period, and a relative deadline. Each vertex of the DAG represents a sequential job, while the edges of the DAG represent precedence constraints between these jobs. All the jobs of the DAG are released simultaneously and need to complete execution within the specified relative deadline of their release. Each task may release jobs in this manner an unbounded number of times, with successive releases occurring at least the specified period apart. Conditional control structures are also allowed. The scheduling problem is to determine whether a set of such recurrent tasks can be scheduled to always meet all deadlines upon a specified number of identical processors.<\/jats:p>\n          <jats:p>This problem is shown to be computationally intractable, but amenable to efficient approximate solutions. Earliest Deadline First (EDF) and Deadline Monotonic (DM) are shown to be good approximate global scheduling algorithms. Polynomial and pseudo-polynomial time schedulability tests, of differing effectiveness, are presented for determining whether a given task set can be scheduled by EDF or DM to always meet deadlines on a specified number of processors.<\/jats:p>","DOI":"10.1145\/3322809","type":"journal-article","created":{"date-parts":[[2019,6,10]],"date-time":"2019-06-10T12:10:51Z","timestamp":1560168651000},"page":"1-40","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["A Generalized Parallel Task Model for Recurrent Real-Time Processes"],"prefix":"10.1145","volume":"6","author":[{"given":"Vincenzo","family":"Bonifaci","sequence":"first","affiliation":[{"name":"IASI--Consiglio Nazionale delle Ricerche, Rome, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andreas","family":"Wiese","sequence":"additional","affiliation":[{"name":"Max Planck Institute for Informatics, Saarbr\u00fccken, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sanjoy K.","family":"Baruah","sequence":"additional","affiliation":[{"name":"University of North Carolina, NC, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alberto","family":"Marchetti-Spaccamela","sequence":"additional","affiliation":[{"name":"Sapienza Universit\u00e0 di Roma, Rome, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sebastian","family":"Stiller","sequence":"additional","affiliation":[{"name":"Technische Universit\u00e4t Braunschweig, Braunschweig, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Leen","family":"Stougie","sequence":"additional","affiliation":[{"name":"CWI 8 Vrije Universiteit Amsterdam, Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,6,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-35476-2_2"},{"key":"e_1_2_1_2_1","volume-title":"Handbook of Real-Time and Embedded Systems, Sang H. Son, Insup Lee, and Joseph Y.-T Leung (Eds.)","author":"Baker Theodore","unstructured":"Theodore Baker and Sanjoy Baruah . 2007. Schedulability analysis of multiprocessor sporadic task systems . In Handbook of Real-Time and Embedded Systems, Sang H. Son, Insup Lee, and Joseph Y.-T Leung (Eds.) . Chapman Hall\/CRC Press . Theodore Baker and Sanjoy Baruah. 2007. Schedulability analysis of multiprocessor sporadic task systems. In Handbook of Real-Time and Embedded Systems, Sang H. Son, Insup Lee, and Joseph Y.-T Leung (Eds.). Chapman Hall\/CRC Press."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/827270.829061"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11241-010-9096-3"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-011-9497-2"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the International Federation for Information Processing Congress. North-Holland","author":"Dertouzos Michael L.","year":"1974","unstructured":"Michael L. Dertouzos . 1974 . Control robotics: The procedural control of physical processes . In Proceedings of the International Federation for Information Processing Congress. North-Holland , Amsterdam, 807--813. Michael L. Dertouzos. 1974. Control robotics: The procedural control of physical processes. In Proceedings of the International Federation for Information Processing Congress. North-Holland, Amsterdam, 807--813."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873684"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2695664.2695808"},{"key":"e_1_2_1_9_1","volume-title":"Johnson","author":"Garey Michael R.","year":"1979","unstructured":"Michael R. Garey and David S . Johnson . 1979 . Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman , New York. Michael R. Garey and David S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, New York."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70356-X"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS.2010.42"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.26.1.22"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(80)90123-4"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-5316(82)90024-4"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/ECRTS.2013.12"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/ECRTS.2014.23"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11241-014-9213-9"},{"key":"e_1_2_1_18_1","volume-title":"II","author":"Liu Chung L.","year":"1969","unstructured":"Chung L. Liu . 1969a. Scheduling algorithms for hard real-time programming of a single processor. JPL Space Progr. Sum. 37--60 , II ( 1969 ), 31--37. Chung L. Liu. 1969a. Scheduling algorithms for hard real-time programming of a single processor. JPL Space Progr. Sum. 37--60, II (1969), 31--37."},{"key":"e_1_2_1_19_1","volume-title":"II","author":"Liu Chung L.","year":"1969","unstructured":"Chung L. Liu . 1969b. Scheduling algorithms for multiprocessors in a hard real-time environment. JPL Space Progr. Sum. 37--60 , II ( 1969 ), 28--31. Chung L. Liu. 1969b. Scheduling algorithms for multiprocessors in a hard real-time environment. JPL Space Progr. Sum. 37--60, II (1969), 28--31."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/321738.321743"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/ECRTS.2012.37"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0068-9"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2013.2297919"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11241-012-9166-9"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTAS.2011.15"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(75)80008-0"}],"container-title":["ACM Transactions on Parallel Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3322809","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3322809","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:02:26Z","timestamp":1750208546000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3322809"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,3,31]]},"references-count":26,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,3,31]]}},"alternative-id":["10.1145\/3322809"],"URL":"https:\/\/doi.org\/10.1145\/3322809","relation":{},"ISSN":["2329-4949","2329-4957"],"issn-type":[{"value":"2329-4949","type":"print"},{"value":"2329-4957","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,3,31]]},"assertion":[{"value":"2017-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-06-07","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}