Elyze: enabling safe parallelism in event-driven servers
Pages 15 - 21
Abstract
It is increasingly necessary for applications to take advantage of concurrency in order to increase performance. Unfortunately, it is notoriously difficult to write correct concurrent applications as they are subject to a variety of subtle bugs that can be difficult to reproduce. We advocate an approach to developing these applications, particularly servers, in which a conservative static analysis determines when code segments may safely run in parallel, and a runtime scheduler respects these constraints, an approach that is safe by default.
We have built an analyzer for event-driven servers written in C that detects unsafe data sharing between event handlers. When the analysis determines that two event handlers might access the same data, whether through a global variable or through the request-specific data structure passed to the handlers, it produces a constraint on the concurrent execution of those handlers. We are building a complementary runtime system that will use these constraints to safely run event handlers concurrently.
We have analyzed thttpd, an event-driven web server, and show that our analyzer finds safe parallelism in this server, enabling increased performance without the hazards of threads and locks.
References
[1]
L. O. Andersen. Program Analysis and Specialization for the C Programming Language. PhD thesis, DIKU, University of Copenhagen (DIKU report 94/19), May 1994.
[2]
N. S. Arora, R. D. Blumofe, and C. G. Plaxton. Thread scheduling for multiprogrammed multiprocessors. In SPAA '98: Proceedings of the 10th annual ACM symposium on Parallel algorithms and architectures, 1998.
[3]
K. Bousias, N. Hasasneh, and C. Jesshope. Instruction level parallelism through microthreading--a scalable approach to chip multiprocessors. The Computer Journal, 49(2), 2006.
[4]
E. Bugnion, J. M. Anderson, T. C. Mowry, M. Rosenblum, and M. S. Lam. Compiler-directed page coloring for multiprocessors. In ASPLOS-VII: Proceedings of the seventh international conference on Architectural support for programming languages and operating systems, 1996.
[5]
B. Chan and T. Abdelrahman. Run-time support for the automatic parallelization of Java programs. In The Journal of Supercomputing, volume 28, Apr. 2004.
[6]
S. Cherem, T. Chilimbi, and S. Gulwani. Inferring locks for atomic sections. In PLDI '08: Proceedings of the 2008 ACM SIGPLAN conference on Programming language design and implementation, 2008.
[7]
M. Das. Unification-based pointer analysis with directional assignments. SIGPLAN Not., 35(5), 2000.
[8]
A. Deutsch. Interprocedural may-alias analysis for pointers: beyond k-limiting. In PLDI '94: Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, 1994.
[9]
H. K. E. M. Nystrom and W. Hwu. Bottom-up and top-down context-sensitive summary-based pointer analysis. In Proc. 11th Static Analysis Symposium, Aug. 2004.
[10]
M. Emami, R. Ghiya, and L. J. Hendren. Context-sensitive interprocedural points-to analysis in the presence of function pointers. In PLDI '94: Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, 1994.
[11]
M. Emmi, J. S. Fischer, R. Jhala, and R. Majumdar. Lock allocation. In POPL '07: Proceedings of the 34th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages, 2007.
[12]
D. Engler and K. Ashcraft. Racerx: effective, static detection of race conditions and deadlocks. In Proc. of the 19th ACM Symposium on Operating Systems Principles, Oct. 2003.
[13]
C. Flanagan and S. N. Freund. Type-based race detection for Java. In Proc. SIGPLAN 2000 Conference (PLDI), 2000.
[14]
C. Flanagan and S. Qadeer. A type and effect system for atomicity. In Proc. SIGPLAN 2003 Conference (PLDI), 2003.
[15]
C. Jesshope. Scalable instruction-level parallelism. Lecture Notes in Computer Science, 3133, 2004.
[16]
W. Landi and B. G. Ryder. A safe approximate algorithm for interprocedural aliasing. SIGPLAN Not., 27(7), 1992.
[17]
B. McCloskey, F. Zhou, D. Gay, and E. Brewer. Autolocker: synchronization inference for atomic sections. In POPL '06: Conference record of the 33rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, 2006.
[18]
A. Navabi, X. Zhang, and S. Jagannathan. Quasi-static scheduling for safe futures. In PPoPP '08: Proceedings of the 13th ACM SIGPLAN Symposium on Principles and practice of parallel programming, 2008.
[19]
G. C. Necula, S. McPeak, S. P. Rahul, and W. Weimer. CIL: Intermediate language and tools for analysis and transformation of C programs. In CC '02: Proceedings of the 11th International Conference on Compiler Construction, 2002.
[20]
D. J. Pearce, P. H. Kelly, and C. Hankin. Efficient field-sensitive pointer analysis of c. ACM Trans. Program. Lang. Syst., 30(1), 2007.
[21]
C. D. Polychronopoulos, M. B. Girkar, M. R. Haghighat, C. L. Lee, B. Leung, and D. Schouten. Parafrase-2: an environment for parallelizing, partitioning, synchronizing, and scheduling programs on multiprocessors. Int. J. High Speed Comput., 1(1), 1989.
[22]
N. Provos. Libevent -- an asynchronous event notification library, 2000. http://www.monkey.org/~provos/libevent/.
[23]
S. Savage, M. Burrows, G. Nelson, P. Sobalvarro, and T. Anderson. Eraser: a dynamic data race detector for multithreaded programs. ACM Trans. Computer Systems, 15(4), 1997.
[24]
B. Steensgaard. Points-to analysis in almost linear time. In POPL '96: Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, 1996.
[25]
thttpd -- tiny/turbo/throttling http server. http://www.acme.com/software/thttpd.
[26]
Tor: anonymity online. http://www.torproject.org/.
[27]
D. W. Wall. Limits of instruction-level parallelism. In ASPLOS-IV: Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, 1991.
[28]
Y. Yu, T. Rodeheffer, and W. Chen. Racetrack: efficient detection of data race conditions via adaptive tracking. ACM SIGOPS Oper. Syst. Rev., 39(5), 2005.
[29]
J. Zahorjan and C. McCann. Processor scheduling in shared memory multiprocessors. In Proc. ACM SIGMETRICS Conference, May 1990.
[30]
N. Zeldovich, A. Yip, F. Dabek, R. Morris, D. Mazières, and F. Kaashoek. Multiprocessor support for event-driven programs. In Proc. USENIX 2003 Annual Technical Conference, June 2003.
Index Terms
- Elyze: enabling safe parallelism in event-driven servers
Recommendations
The Clara framework for hybrid typestate analysis
A typestate property describes which operations are available on an object or a group of inter-related objects, depending on this object's or group's internal state, the typestate. Researchers in the field of static analysis have devised static program ...
Static analysis of atomicity for programs with non-blocking synchronization
PPoPP '05: Proceedings of the tenth ACM SIGPLAN symposium on Principles and practice of parallel programmingIn concurrent programming, non-blocking synchronization is very efficient but difficult to design correctly. This paper presents a static analysis to show that code blocks are atomic, i.e., that every execution of the program is equivalent to one in ...
Practical lock/unlock pairing for concurrent programs
CGO '13: Proceedings of the 2013 IEEE/ACM International Symposium on Code Generation and Optimization (CGO)In the multicore era, developers face increasing pressure to parallelize their programs. However, building correct and efficient concurrent programs is substantially more difficult than building sequential ones. To address the multicore challenge, ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
November 2008
92 pages
Copyright © 2008 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 09 November 2008
Check for updates
Author Tags
Qualifiers
- Research-article
Conference
PASTE08: PASTE '08 - ACM SIGPLAN-SIGSOFT Workshop on Program Analysis for Software Tools and Engineering
November 9 - 10, 2008
Georgia, Atlanta
Acceptance Rates
Overall Acceptance Rate 57 of 159 submissions, 36%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 122Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 12 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in