Contention-aware scheduler: unlocking execution parallelism in multithreaded java programs

ABSTRACT

In multithreaded programming, locks are frequently used as a mechanism for synchronization. Because today's operating systems do not consider lock usage as a scheduling criterion, scheduling decisions can be unfavorable to multithreaded applications, leading to performance issues such as convoying and heavy lock contention in systems with multiple processors. Previous efforts to address these issues (e.g., transactional memory, lock-free data structure) often treat scheduling decisions as "a fact of life," and therefore these solutions try to cope with the consequences of undesirable scheduling instead of dealing with the problem directly.

In this paper, we introduce Contention-Aware Scheduler (CA-Scheduler), which is designed to support efficient execution of large multithreaded Java applications in multiprocessor systems. Our proposed scheduler employs a scheduling policy that reduces lock contention. As will be shown in this paper, our prototype implementation of the CA-Scheduler in Linux and Sun HotSpot virtual machine only incurs 3.5% runtime overhead, while the overall performance differences, when compared with a system with no contention awareness, range from a degradation of 3% in a small multithreaded benchmark to an improvement of 15% in a large Java application server benchmark.

REFERENCES

• 1: J. Aas. Understanding the Linux 2.6.8.1 Scheduler. On-line article, 2006. http://josh.trancesoftware.com/linux/linux cpu scheduler.pdf.
• 2: Thomas E. Anderson , Brian N. Bershad , Edward D. Lazowska , Henry M. Levy, Scheduler activations: effective kernel support for the user-level management of parallelism, Proceedings of the thirteenth ACM symposium on Operating systems principles, p.95-109, October 13-16, 1991, Pacific Grove, California, United States
• 3: Matthew Arnold , Adam Welc , V. T. Rajan, Improving virtual machine performance using a cross-run profile repository, Proceedings of the 20th annual ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, October 16-20, 2005, San Diego, CA, USA
• 4: David F. Bacon , Ravi Konuru , Chet Murthy , Mauricio Serrano, Thin locks: featherweight synchronization for Java, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.258-268, June 17-19, 1998, Montreal, Quebec, Canada
• 5: J. C. Bezdek, R. Ehrlich, and W. Full. FCM: The fuzzy C-Means Clustering Algorithm. Computers & Geosciences, 10(2-3):191--203, 1984.
• 6: Christopher M. Bishop, Neural Networks for Pattern Recognition, Oxford University Press, Inc., New York, NY, 1995
• 7: Stephen M. Blackburn , Robin Garner , Chris Hoffmann , Asjad M. Khang , Kathryn S. McKinley , Rotem Bentzur , Amer Diwan , Daniel Feinberg , Daniel Frampton , Samuel Z. Guyer , Martin Hirzel , Antony Hosking , Maria Jump , Han Lee , J. Eliot B. Moss , B. Moss , Aashish Phansalkar , Darko Stefanović , Thomas VanDrunen , Daniel von Dincklage , Ben Wiedermann, The DaCapo benchmarks: java benchmarking development and analysis, Proceedings of the 21st annual ACM SIGPLAN conference on Object-oriented programming systems, languages, and applications, October 22-26, 2006, Portland, Oregon, USA
• 8: B. D. Carlstrom, J. Chung, H. Chafi, A. McDonald, C. Cao Minh, L. Hammond, C. Kozyrakis, and K. and Olukotun. Transactional Execution of Java Programs. In OOPSLA 2005 Workshop on Synchronization and Concurrency in Object-Oriented Languages (SCOOL). Oct 2005.
• 9: Myra Cohen , Shiu Beng Kooi , Witawas Srisa-an, Clustering the heap in multi-threaded applications for improved garbage collection, Proceedings of the 8th annual conference on Genetic and evolutionary computation, July 08-12, 2006, Seattle, Washington, USA [doi>10.1145/1143997.1144314]
• 10: James C. Dehnert , Brian K. Grant , John P. Banning , Richard Johnson , Thomas Kistler , Alexander Klaiber , Jim Mattson, The Transmeta Code Morphing™ Software: using speculation, recovery, and adaptive retranslation to address real-life challenges, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, March 23-26, 2003, San Francisco, California
• 11: R. Dimpsey , R. Arora , K. Kuiper, Java server performance: a case study of building efficient, scalable Jvms, IBM Systems Journal, v.39 n.1, p.151-174, January 2000
• 12: Chris Grzegorczyk , Sunil Soman , Chandra Krintz , Rich Wolski, Isla Vista Heap Sizing: Using Feedback to Avoid Paging, Proceedings of the International Symposium on Code Generation and Optimization, p.325-340, March 11-14, 2007 [doi>10.1109/CGO.2007.20]
• 13: Tim Harris , Adrián Cristal , Osman S. Unsal , Eduard Ayguade , Fabrizio Gagliardi , Burton Smith , Mateo Valero, Transactional Memory: An Overview, IEEE Micro, v.27 n.3, p.8-29, May 2007 [doi>10.1109/MM.2007.63]
• 14: Tim Harris , Mark Plesko , Avraham Shinnar , David Tarditi, Optimizing memory transactions, Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, June 11-14, 2006, Ottawa, Ontario, Canada
• 15: J. A. Hartigan and M. A. Wong. A K-Means Clustering Algorithm. Applied Statistics, 28:100--108, 1979.
• 16: Maurice Herlihy , J. Eliot B. Moss, Transactional memory: architectural support for lock-free data structures, Proceedings of the 20th annual international symposium on Computer architecture, p.289-300, May 16-19, 1993, San Diego, California, United States
• 17: HSQL Database Engine. hsqldb. On-Line Documentation, Last visited: December 2007. http://hsqldb.org/web/hsqlFAQ.html.
• 18: IBM. Jikes RVM. http://jikesrvm.sourceforge.net.
• 19: Brian D. Marsh , Michael L. Scott , Thomas J. LeBlanc , Evangelos P. Markatos, First-class user-level threads, Proceedings of the thirteenth ACM symposium on Operating systems principles, p.110-121, October 13-16, 1991, Pacific Grove, California, United States
• 20: Microsoft Corp. Using Microsoft Virtual PC 2007 for Application Compatibility. White Paper, August 2006. http://www.microsoft.com/windows/products/winfamily/virtualpc/appcompat.mspx.
• 21: K. E. Moore, J. Bobba, M. J. Moravan, M. D. Hill, and D. A. Wood. LogTM: Log-Based Transactional Memory. In Proceedings of the International Symposium on High-Performance Computer Architecture (HPCA), pages 254--265. Feb 2006.
• 22: David A. Patterson , John Hennessy, Computer Organization and Design, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2004
• 23: Ravi Rajwar , James R. Goodman, Speculative lock elision: enabling highly concurrent multithreaded execution, Proceedings of the 34th annual ACM/IEEE international symposium on Microarchitecture, December 01-05, 2001, Austin, Texas
• 24: Ravi Rajwar , James R. Goodman, Transactional lock-free execution of lock-based programs, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California
• 25: Christopher J. Rossbach , Owen S. Hofmann , Donald E. Porter , Hany E. Ramadan , Bhandari Aditya , Emmett Witchel, TxLinux: using and managing hardware transactional memory in an operating system, Proceedings of twenty-first ACM SIGOPS symposium on Operating systems principles, October 14-17, 2007, Stevenson, Washington, USA
• 26: Abraham Silberschatz , Peter Baer Galvin , Greg Gagne, Operating System Concepts, Wiley Publishing, 2008
• 27: Jeremy Singer , Gavin Brown , Ian Watson , John Cavazos, Intelligent selection of application-specific garbage collectors, Proceedings of the 6th international symposium on Memory management, October 21-22, 2007, Montreal, Quebec, Canada [doi>10.1145/1296907.1296920]
• 28: Sunil Soman , Chandra Krintz , David F. Bacon, Dynamic selection of application-specific garbage collectors, Proceedings of the 4th international symposium on Memory management, October 24-25, 2004, Vancouver, BC, Canada [doi>10.1145/1029873.1029880]
• 29: Standard Performance Evaluation Corporation. SPECjAppServer2004 user's guide. http://www.spec.org.
• 30: Standard Performance Evaluation Corporation. SPECjbb2005. On-Line Documentation, Last visited: July 2007. http://www.spec.org/jbb2005.
• 31: Sun Microsystems. ECPERF. http://java.sun.com/developer/earlyAccess/j2ee/ecperf/download.html.
• 32: David Tam , Reza Azimi , Michael Stumm, Thread clustering: sharing-aware scheduling on SMP-CMP-SMT multiprocessors, ACM SIGOPS Operating Systems Review, v.41 n.3, June 2007
• 33: A. Tucker , A. Gupta, Process control and scheduling issues for multiprogrammed shared-memory multiprocessors, Proceedings of the twelfth ACM symposium on Operating systems principles, p.159-166, November 1989
• 34: A. Tucker, B. Smaalders, D. Singleton, and N. Kosche. US patent 5,937,187: Method and Apparatus for Execution and Preemption Control of Computer Process Entities, 1999.
• 35: Volkmar Uhlig, The mechanics of in-kernel synchronization for a scalable microkernel, ACM SIGOPS Operating Systems Review, v.41 n.4, July 2007 [doi>10.1145/1278901.1278909]
• 36: Feng Xian , Witawas Srisa-an , Hong Jiang, Allocation-phase aware thread scheduling policies to improve garbage collection performance, Proceedings of the 6th international symposium on Memory management, October 21-22, 2007, Montreal, Quebec, Canada [doi>10.1145/1296907.1296919]
• 37: Ting Yang , Emery D. Berger , Scott F. Kaplan , J. Eliot B. Moss, CRAMM: virtual memory support for garbage-collected applications, Proceedings of the 7th symposium on Operating systems design and implementation, November 06-08, 2006, Seattle, Washington

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Run-time environments

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Scheduling; Concurrency; Threads; Synchronization

General Terms:
Experimentation, Languages, Performance

Keywords:
java, operating systems, scheduling