{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,1]],"date-time":"2025-07-01T23:14:02Z","timestamp":1751411642607},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2017,5,8]],"date-time":"2017-05-08T00:00:00Z","timestamp":1494201600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2017,5,8]],"date-time":"2017-05-08T00:00:00Z","timestamp":1494201600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Computing"],"published-print":{"date-parts":[[2021,5]]},"DOI":"10.1007\/s00607-017-0555-8","type":"journal-article","created":{"date-parts":[[2017,5,8]],"date-time":"2017-05-08T07:52:19Z","timestamp":1494229939000},"page":"749-770","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Deadlock and WCET analysis of barrier-synchronized concurrent programs"],"prefix":"10.1007","volume":"103","author":[{"given":"Robert","family":"Mittermayr","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Johann","family":"Blieberger","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,5,8]]},"reference":[{"key":"555_CR1","doi-asserted-by":"crossref","unstructured":"Aiken A, Gay D (1998) Barrier inference. In: Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on principles of programming languages, POPL \u201998, 19\u201321 January 1998, San Diego, California, USA, pp 342\u2013354","DOI":"10.1145\/268946.268974"},{"issue":"3","key":"555_CR2","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1023\/A:1014535317056","volume":"22","author":"J Blieberger","year":"2002","unstructured":"Blieberger J (2002) Data-flow frameworks for worst-case execution time analysis. Real Time Syst 22(3):183\u2013227","journal-title":"Real Time Syst"},{"key":"555_CR3","doi-asserted-by":"crossref","unstructured":"Blieberger J, Burgstaller B, Mittermayr R (2007) Static detection of livelocks in ada multitasking programs. In: Proceedings of the 12th international conference on reliable software technologies, vol 4498. Springer LNCS, pp 69\u201383","DOI":"10.1007\/978-3-540-73230-3_6"},{"key":"555_CR4","unstructured":"Brukardt RL (ed) (2016) Annotated ada reference manual, ISO\/IEC 8652:2012\/Cor 1:2016"},{"issue":"3","key":"555_CR5","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1023\/A:1015669415634","volume":"12","author":"P Buchholz","year":"2002","unstructured":"Buchholz P, Kemper P (2002) Efficient computation and representation of large reachability sets for composed automata. Discret Event Dyn. Syst. 12(3):265\u2013286","journal-title":"Discret Event Dyn. Syst."},{"key":"555_CR6","doi-asserted-by":"crossref","unstructured":"Burgstaller B, Blieberger J (2014) Kronecker algebra for static analysis of Ada programs with protected objects. In: Ada-Europe\u2019 2014 international conference on reliable software technologies, LNCS 8454, Paris, pp 27\u201342","DOI":"10.1007\/978-3-319-08311-7_4"},{"issue":"6","key":"555_CR7","doi-asserted-by":"publisher","first-page":"1418","DOI":"10.1016\/j.jss.2011.11.1039","volume":"85","author":"B Burgstaller","year":"2012","unstructured":"Burgstaller B, Scholz B, Blieberger J (2012) A symbolic analysis framework for static analysis of imperative programming languages. J Syst Softw 85(6):1418\u20131439","journal-title":"J Syst Softw"},{"key":"555_CR8","doi-asserted-by":"crossref","unstructured":"Buse RPL, Weimer WR (2009) The road not taken: estimating path execution frequency statically. In: Proceedings of the 31st international conference on software engineering\u2014ICSE 2009, Vancouver, Canada, May 16\u201324, 2009, pp 144\u2013154","DOI":"10.1109\/ICSE.2009.5070516"},{"key":"555_CR9","doi-asserted-by":"crossref","unstructured":"Chattopadhyay S, Chong LK, Roychoudhury A, Kelter T, Marwedel P, Falk H (2012) A unified WCET analysis framework for multi-core platforms. In: IEEE real-time and embedded technology and applications symposium, pp 99\u2013108","DOI":"10.1109\/RTAS.2012.26"},{"key":"555_CR10","unstructured":"Downey AB (2016) The little book of semaphores. Green Tea Press, 2nd edn, version 2.2.1"},{"key":"555_CR11","doi-asserted-by":"crossref","unstructured":"Fechete R, Kienesberger G, Blieberger J (2008) A framework for CFG-based static program analysis of ada programs. In: Proceedings of Ada-Europe, Springer LNCS, pp 130\u2013143","DOI":"10.1007\/978-3-540-68624-8_10"},{"key":"555_CR12","doi-asserted-by":"crossref","unstructured":"Gerdes M, Kluge F, Ungerer T, Rochange C (2012) The split-phase synchronisation technique: reducing the pessimism in the WCET analysis of parallelised hard real-time programs. In: Proceedings of the 18th international conference RTCSA, pp 88\u201397","DOI":"10.1109\/RTCSA.2012.11"},{"key":"555_CR13","volume-title":"Java 7 concurrency cookbook","author":"JF Gonz\u00e1lez","year":"2012","unstructured":"Gonz\u00e1lez JF (2012) Java 7 concurrency cookbook. Packt Publishing Ltd., Mumbai\/Birmingham"},{"key":"555_CR14","volume-title":"Concrete mathematics: a foundation for computer science","author":"RL Graham","year":"1994","unstructured":"Graham RL, Knuth DE, Patashnik O (1994) Concrete mathematics: a foundation for computer science, 2nd edn. Addison-Wesley Longman Publishing Co., Inc., Boston","edition":"2"},{"key":"555_CR15","unstructured":"Hill JMD, Skillicorn DB (1998) Practical barrier synchronisation. In: 6th EuroMicro workshop on parallel and distributed processing (PDP \u201998), IEEE Computer Society Press, pp 438\u2013444"},{"key":"555_CR16","doi-asserted-by":"crossref","unstructured":"Kamil A, Yelick K (2006) Concurrency analysis for parallel programs with textually aligned barriers. In: Ayguad\u00e9 E, Baumgartner G, Ramanujam J, Sadayappan P (eds) Languages and compilers for parallel computing, LCPC 2005, Lecture Notes in Computer Science, vol 4339. Springer, Berlin, pp 185\u2013199","DOI":"10.1007\/978-3-540-69330-7_13"},{"key":"555_CR17","doi-asserted-by":"crossref","unstructured":"Le D-K, Chin W-N, Teo Y-M (2013) Verification of static and dynamic barrier synchronization using bounded permissions. ICFEM 2013, pp 231\u2013248","DOI":"10.1007\/978-3-642-41202-8_16"},{"issue":"6","key":"555_CR18","doi-asserted-by":"publisher","first-page":"638","DOI":"10.1007\/s11241-012-9160-2","volume":"48","author":"Y Liang","year":"2012","unstructured":"Liang Y, Ding H, Mitra T, Roychoudhury A, Li Y, Suhendra V (2012) Timing analysis of concurrent programs running on shared cache multi-cores. Real-Time Syst. 48(6):638\u2013680","journal-title":"Real-Time Syst."},{"key":"555_CR19","doi-asserted-by":"crossref","unstructured":"Malkis A, Banerjee A (2012) Verification of software barriers. In: Proceedings of the 17th ACM SIGPLAN symposium on principles and practice of parallel programming, PPoPP \u201912, New Orleans, Louisiana, USA, 25\u201329 February 2012, pp 313\u2013314","DOI":"10.1145\/2145816.2145871"},{"key":"555_CR20","unstructured":"Mittermayr R (Aug. 2016) Kronecker algebra based analysis of shared memory concurrent systems. Dissertation, 163 pp. TU Vienna, Treitlstr 1\u20133, 1040 Vienna"},{"issue":"5","key":"555_CR21","first-page":"182","volume":"9","author":"R Mittermayr","year":"2016","unstructured":"Mittermayr R, Blieberger J (2016) A generic graph model for WCET analysis of multi-core concurrent applications. J. of Softw. Eng. Appl. (JSEA), Spec Issue Parallel Concurr Comput 9(5):182\u2013198","journal-title":"J. of Softw. Eng. Appl. (JSEA), Spec Issue Parallel Concurr Comput"},{"key":"555_CR22","doi-asserted-by":"crossref","unstructured":"Mittermayr R, Blieberger J (2016) Kronecker algebra for static analysis of barriers in ada. In: Bertogna M, Pinho LM, Quinones E (eds), Proceedings of the 21th international conference on reliable software technologies, vol 9695, LNCS, pp 145\u2013159","DOI":"10.1007\/978-3-319-39083-3_10"},{"issue":"5","key":"555_CR23","doi-asserted-by":"publisher","first-page":"359","DOI":"10.7307\/ptt.v24i5.1171","volume":"24","author":"R Mittermayr","year":"2012","unstructured":"Mittermayr R, Blieberger J, Sch\u00f6bel A (2012) Kronecker algebra based deadlock analysis for railway systems. J PROMET 24(5):359\u2013369","journal-title":"J PROMET"},{"key":"555_CR24","doi-asserted-by":"crossref","unstructured":"N\u00e9lis V, Yomsi PM, Pinho LM (2015) Methodologies for the WCET analysis of parallel applications on many-core architectures. In: Proceedings of the 18th Euromicro conference on DSD, pp 748\u2013755,","DOI":"10.1109\/DSD.2015.105"},{"key":"555_CR25","unstructured":"Ozaktas H, Rochange C, Sainrat P (2013) Automatic WCET analysis of real-time parallel applications. In: Maiza C (ed), Proceedings of the 13th international WCET, volume\u00a030 of OASIcs, pp 11\u201320"},{"issue":"2","key":"555_CR26","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1145\/317786.317819","volume":"13","author":"B Plateau","year":"1985","unstructured":"Plateau B (1985) On the stochastic structure of parallelism and synchronization models for distributed algorithms. Perform Evaluation Rev 13(2):142\u2013154","journal-title":"Perform Evaluation Rev"},{"key":"555_CR27","doi-asserted-by":"crossref","unstructured":"Ramalingam G (1996) Data flow frequency analysis. In Fischer CN (ed), Proceedings of the ACM SIGPLAN conference on PLDI, ACM, pp 267\u2013277","DOI":"10.1145\/249069.231433"},{"issue":"2","key":"555_CR28","doi-asserted-by":"publisher","first-page":"416","DOI":"10.1145\/349214.349241","volume":"22","author":"G Ramalingam","year":"2000","unstructured":"Ramalingam G (2000) Context-sensitive synchronization-sensitive analysis is undecidable. ACM Trans. Program. Lang. Syst. 22(2):416\u2013430","journal-title":"ACM Trans. Program. Lang. Syst."},{"issue":"2","key":"555_CR29","doi-asserted-by":"publisher","first-page":"388","DOI":"10.1145\/276393.278523","volume":"20","author":"VC Sreedhar","year":"1998","unstructured":"Sreedhar VC, Gao GR, Lee Y-F (1998) A new framework for elimination-based data flow analysis using DJ graphs. ACM Trans. Prog. Lang. Syst. (TOPLAS) 20(2):388\u2013435","journal-title":"ACM Trans. Prog. Lang. Syst. (TOPLAS)"},{"key":"555_CR30","volume-title":"Operating systems\u2013internals and design principles","author":"W Stallings","year":"2011","unstructured":"Stallings W (2011) Operating systems\u2013internals and design principles, 7th edn. Prentice Hall, Upper Saddle River, New Jersey","edition":"7"},{"key":"555_CR31","doi-asserted-by":"crossref","unstructured":"Stefan M, Blieberger J, Sch\u00f6bel A (2017) Application of Kronecker algebra in railway operation. Tehni\u010dki vjesnik\u2014Technical Gazette (TV-TG) 24(1):21\u201330","DOI":"10.17559\/TV-20131107130926"},{"issue":"2","key":"555_CR32","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1137\/0201010","volume":"1","author":"RE Tarjan","year":"1972","unstructured":"Tarjan RE (1972) Depth-first search and linear graph algorithms. SIAM J Comput (SICOMP) 1(2):146\u2013160","journal-title":"SIAM J Comput (SICOMP)"},{"issue":"3","key":"555_CR33","first-page":"36:1","volume":"7","author":"R Wilhelm","year":"2008","unstructured":"Wilhelm R, Engblom J, Ermedahl A, Holsti N, Thesing S, Whalley D, Bernat G, Ferdinand C, Heckmann R, Mitra T, Mueller F, Puaut I, Puschner P, Staschulat J, Stenstr\u00f6m P (2008) The worst-case execution-time problem\u2014overview of methods and survey of tools. ACM TECS 7(3):36:1\u201336:53","journal-title":"ACM TECS"},{"key":"555_CR34","doi-asserted-by":"crossref","unstructured":"Yan J, Zhang W (2008) WCET analysis for multi-core processors with shared L2 instruction caches. In: IEEE real-time and embedded technology and applications symposium, pp 80\u201389","DOI":"10.1109\/RTAS.2008.6"},{"key":"555_CR35","doi-asserted-by":"crossref","unstructured":"Zhang Y, Duesterwald E (2007) Barriers matching for programs with textually unaligned barriers. In: Proceedings of the 12th ACM SIGPLAN symposium on principles and practice of parallel programming, PPoPP \u201907, 14\u201317 March 2007, San Jose, California, USA, pp 194\u2013204","DOI":"10.1145\/1229428.1229472"},{"key":"555_CR36","doi-asserted-by":"crossref","unstructured":"Zhang Y, Duesterwald E, Gao GR (2007) Concurrency analysis for shared memory programs with textually unaligned barriers. LCPC","DOI":"10.1145\/1229428.1229472"}],"container-title":["Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00607-017-0555-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00607-017-0555-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00607-017-0555-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T20:16:00Z","timestamp":1620159360000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00607-017-0555-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,5,8]]},"references-count":36,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2021,5]]}},"alternative-id":["555"],"URL":"https:\/\/doi.org\/10.1007\/s00607-017-0555-8","relation":{},"ISSN":["0010-485X","1436-5057"],"issn-type":[{"value":"0010-485X","type":"print"},{"value":"1436-5057","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,5,8]]},"assertion":[{"value":"31 October 2016","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 April 2017","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 May 2017","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}