some image logo

HOME

SEARCH

CURRENT ISSUE

REGULAR ISSUES

   Volume 1 (2005)

   Volume 2 (2006)

   Volume 3 (2007)

   Volume 4 (2008)

   Volume 5 (2009)

   Volume 6 (2010)

   Volume 7 (2011)

      Issue 1

      Issue 2

      Issue 3

      Issue 4

   Volume 8 (2012)

   Volume 9 (2013)

   Volume 10 (2014)

   Volume 11 (2015)

   Volume 12 (2016)

SPECIAL ISSUES

SURVEY ARTICLES

AUTHORS

ABOUT

SERVICE

LOGIN

FAQ

SUPPORT

CONTACT

VOLUME 7, ISSUE 4, PAPER 4


Context-Bounded Analysis For Concurrent Programs With Dynamic Creation of Threads

©Mohamed Faou Atig, LIAFA, CNRS & University of Paris Diderot (Paris 7)
©Ahmed Bouajjani, LIAFA, CNRS & University of Paris Diderot (Paris 7)
©Shaz Qadeer, Microsoft Research, Redmond

Abstract
Context-bounded analysis has been shown to be both efficient and effective at finding bugs in concurrent programs. According to its original definition, context-bounded analysis explores all behaviors of a concurrent program up to some fixed number of context switches between threads. This definition is inadequate for programs that create threads dynamically because bounding the number of context switches in a computation also bounds the number of threads involved in the computation. In this paper, we propose a more general definition of context-bounded analysis useful for programs with dynamic thread creation. The idea is to bound the number of context switches for each thread instead of bounding the number of switches of all threads. We consider several variants based on this new definition, and we establish decidability and complexity results for the analysis induced by them.

Publication date: November 23, 2011

Full Text: PDF | PostScript
DOI: 10.2168/LMCS-7(4:4)2011

Hit Counts: 4766

Creative Commons