Data processing: software development – installation – and managem – Software program development tool – Testing or debugging
Reexamination Certificate
2011-04-12
2011-04-12
Khatri, Anil (Department: 2191)
Data processing: software development, installation, and managem
Software program development tool
Testing or debugging
C717S125000, C717S149000
Reexamination Certificate
active
07926035
ABSTRACT:
Testing multithreaded application programs for errors can be carried out in an efficient and productive manner at least in part by prioritizing thread schedules based on numbers of context switches between threads therein. In particular, each thread schedule in a multithreaded application program can be prioritized based on whether a given thread schedule has the same as or less than some maximum value. A model checker module can then iteratively execute thread schedules that fit within a given context switch maximum value, or a progressively higher value up to some limit. In one implementation, for example, the model checker module executes all thread schedules that have zero preempting context switches, then all thread schedules that have only one preempting context switch, etc. Most errors in an application program can be identified by executing only those thread schedule with relatively few preempting context switches.
REFERENCES:
patent: 5179702 (1993-01-01), Spix et al.
patent: 5442797 (1995-08-01), Casavant et al.
patent: 5692193 (1997-11-01), Jagannathan et al.
patent: 5729710 (1998-03-01), Magee et al.
patent: 6158045 (2000-12-01), You
patent: 6212544 (2001-04-01), Borkenhagen et al.
patent: 6282701 (2001-08-01), Wygodny et al.
patent: 6374286 (2002-04-01), Gee et al.
patent: 6567974 (2003-05-01), Czajkowski
patent: 6697935 (2004-02-01), Borkenhagen et al.
patent: 6748556 (2004-06-01), Storino et al.
patent: 6779135 (2004-08-01), Ur et al.
patent: 6851075 (2005-02-01), Ur et al.
patent: 6854108 (2005-02-01), Choi
patent: 6883162 (2005-04-01), Jackson et al.
patent: 6938247 (2005-08-01), Czajkowski
patent: 6952825 (2005-10-01), Cockx et al.
patent: 6971084 (2005-11-01), Grey et al.
patent: 6978399 (2005-12-01), Bates et al.
patent: 7222264 (2007-05-01), Muratori et al.
patent: 7293251 (2007-11-01), Zeman et al.
patent: 7373640 (2008-05-01), English et al.
patent: 7386864 (2008-06-01), Richardson
patent: 7415704 (2008-08-01), Schmidt et al.
patent: 7426731 (2008-09-01), Findeisen
patent: 7559060 (2009-07-01), Schmidt et al.
patent: 7617488 (2009-11-01), Srinivasan et al.
patent: 7657880 (2010-02-01), Wang et al.
patent: 7685599 (2010-03-01), Kanai et al.
patent: 7712080 (2010-05-01), Pan et al.
patent: 7730291 (2010-06-01), Kissell
patent: 7831961 (2010-11-01), Bush et al.
patent: 2004/0230961 (2004-11-01), Biberstein et al.
patent: 2006/0130010 (2006-06-01), Rehof et al.
patent: 2006/0218534 (2006-09-01), Kahlon et al.
Cui et al, “Extending data prefetching to cope with context switch misses”, IEEE, pp. 260-267, 2009.
Kumar et al, “Asynchronous software thread integartion for efficient software implementations of embedded communication protocol controllers”, ACM LCTES, pp. 37-46, 2004.
Xian et al, “Allocation phase aware therad scheduling policies to improv garbage collection performance”, ACM ISMM, 79-90, 2007.
Feng et al, “Certifying low level programs with hardware interrupts and preemptive threads”, ACM PLDI, pp. 170-182, 2008.
“CHESS: Systematic Stress Testing of Concurrent Software,” by Madan Musuvathi and Shaz Qadeer, date unknown, Microsoft Research, [online] [retrieved on Feb. 13, 2007], 2 pgs. Retrieved from the Internet: http://research.microsoft.com/projects/CHESS/chess.pdf.
“Context-Bounded Model Checking of Concurrent Software,” by Shaz Qadeer and Jakob Rehof, date unknown, Microsoft Research, [online] [retrieved on Feb. 13, 2007], 15 pgs. Retrieved from the Internet: http://Is14-www.cs.uni-dortmund.de/Is14Medien/Dokumente/Pubs/Context-Bounded.pdf.
“Model Checking Multithreaded Programs with Asynchronous Atomic Methods,” by Koushik Sen and Mahesh Viswanathan, date unknown, Department of Computer Science, University of Illinois at Urbana-Champaign, [online] [retrieved on Feb. 13, 2007], 14 pgs. Retrieved from the Internet: http://osl.cs.uiuc.edu/˜ksen/paper/multiset.ps.
“Integrated State Space Reduction for Model Checking Executable Object-oriented Software System Designs,” by FEI Xie and James C. Browne, date unknown, Department of Computer Sciences, University of Texas at Austin, [online] [retrieved on Feb. 13, 2007], 15 pgs. Retrieved from the Internet: http://citeseer.ist.psu.edu/cache/papers/cs/30215/http:zSzzSzwww.cs.utexas.eduzSzuserszSzbrownezSzNewPaperszSzissr-fase2002.pdf/intergrated-state-space-reduction.pdf.
Musuvathi Madanlal S.
Qadeer Shaz
Khatri Anil
Microsoft Corporation
Workman Nydegger
LandOfFree
Testing multi-thread software using prioritized context... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Testing multi-thread software using prioritized context..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Testing multi-thread software using prioritized context... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2734526