Abstract
Identifying synchronizations could significantly improve testing and debugging of multithreaded programs because it could substantially cut down the number of possible interleavings in those tests. There are two general techniques to implement synchronizations: modularized and ad-hoc. Identifying synchronizations in multi-threaded programs could be quite challenging. It is because modularized synchronizations are often implemented in an obscure and implicit way, and ad-hoc synchronizations could be quite subtle. In this paper, we try to identify synchronizations from a new perspective. We found that if a thread is waiting for synchronizations, the code it executes during the wait is very different from that after the completion of the synchronization. Based on such an observation, we proposed an effective method to identify synchronizations. It doesn’t depend on the understanding of source codes or the knowledge of semantics of library routines. A system called SyncTester is developed, and experiments show that SyncTester is effective and useful.
Chapter PDF
Similar content being viewed by others
References
Savage, S., Burrows, M., Nelson, G., Sobalvarro, P., Anderson, T.: Eraser: a dynamic data race detector for multithreaded programs. J. ACM TOCS 15(4), 391–411 (1997)
Zhang, W., Sun, C., Lu, S.: ConMem: detecting severe concurrency bugs through an effect-oriented approach. In: Proc. of 15th ASPLOS, pp. 179–192. ACM, NY (2010)
Flanagan, C., Freund, S.N.: FastTrack: efficient and precise dynamic race detection. In: Proceedings of the PLDI, pp. 121–133. ACM, NY (2009)
Park, S., Lu, S., Zhou, Y.: CTrigger: exposing atomicity violation bugs from their hiding places. In: Proceedings of the 14th ASPLOS, pp. 25–36. ACM, NY (2009)
Cui, H., Wu, J., Tsai, C.C., Yang, J.: Stable deterministic multithreading through schedule memorization. In: Proceedings of the 9th OSDI. USENIX Association, Berkeley (2010)
Park, S., Zhou, Y., Xiong, W., Yin, Z., Kaushik, R., Lee, K.H., Lu, S.: PRES: probabilistic replay with execution sketching on multiprocessors. In: Proceedings of the 22nd SOSP, pp. 177–192. ACM, NY (2009)
Tian, C., Nagarajan, V., Gupta, R., Tallam, S.: Dynamic recognition of synchronization operations for improved data race detection. In: Proceedings of the ISSTA, pp. 143–154. ACM, NY (2008)
Jannesari, A., Tichy, W.F.: Identifying ad-hoc synchronization for enhanced race detection. In: Proceedings of the IPDPS, pp. 1–10. IEEE Press, NY (2010)
Sherwood, T., Perelman, E., Calder, B.: Basic Block Distribution Analysis to Find Periodic Behavior and Simulation Points in Applications. In: Proceedings of the PACT, pp. 3–14. IEEE Computer Society, Washington, DC (2001)
Woo, S.C., Ohara, M., Torrie, E., Singh, J.P., Gupta, A.: The SPLASH-2 programs: characterization and methodological considerations. In: Proceedings of the 22nd ISCA, pp. 24–36. ACM, NY (1995)
Minh, C.C., Chung, J.W., Kozyrakis, C., Olukotun, K.: STAMP: Stanford Transactional Applications for Multi-Processing. In: Proceedings of the 2008 IISWC, pp. 35–46. IEEE Press, NY (2008)
Xiong, W., Park, S., Zhang, J., Zhou, Y., Ma, Z.: Ad hoc synchronization considered harmful. In: Proceedings of the 9th OSDI. USENIX Association, Berkeley (2010)
Zhang, J., Xiong, W., Liu, Y., Park, S., Zhou, Y., Ma, Z.: ATDetector: improving the accuracy of a commercial data race detector by identifying address transfer. In: Proceedings of the 44th MICRO, pp. 206–215. ACM, NY (2011)
The GNU C Library manual, http://www.gnu.org/software/libc/manual/
Li, T., Lebeck, A.R., Sorin, D.J.: Spin detection hardware for improved management of multithreaded systems. J. IEEE PDS 17(6), 508–512 (2006)
Luk, C.K., Cohn, R., Muth, R., Patil, H., Klauser, A., Lowney, G., Wallace, S., Reddi, V.J., Hazelwood, K.: Pin: building customized program analysis tools with dynamic instrumentation. In: Proceedings of the PLDI, pp. 190–200. ACM, NY (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Yuan, X. et al. (2013). Synchronization Identification through On-the-Fly Test. In: Wolf, F., Mohr, B., an Mey, D. (eds) Euro-Par 2013 Parallel Processing. Euro-Par 2013. Lecture Notes in Computer Science, vol 8097. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-40047-6_3
Download citation
DOI: https://doi.org/10.1007/978-3-642-40047-6_3
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-40046-9
Online ISBN: 978-3-642-40047-6
eBook Packages: Computer ScienceComputer Science (R0)