网络程序设计中的并发复杂性
作者:
基金项目:

国家自然科学基金(60703072); 国家重点基础研究发展计划(973)(2005CB321801); 湖南省自然科学基金(08JJ3125); 全国高等学校优秀博士学位论文作者专向基金(200953)


Concurrency-Related Complexities in Network Programming
Author:
  • 摘要
  • | |
  • 访问统计
  • |
  • 参考文献 [44]
  • |
  • 相似文献 [20]
  • |
  • 引证文献
  • | |
  • 文章评论
    摘要:

    互联网已成为现代社会的重要信息基础设施,然而网络环境的并发性使得传统程序设计方法在开发高质量的网络程序时遇到了许多困难,严重影响了开发效率.并发问题对网络程序开发复杂度的影响可以类比多核处理器带来的“软件并发危机”,然而其中的并发问题却远远没有得到应有的重视.网络并发问题目前并不存在普适的应对方法,甚至在不同方法之间存在明显的争论.简要介绍了各种基本的并发模型及其常见的实现方法,并在此基础上着重分析了现有方法的内在复杂性,对比各种方法的优势与劣势,最后展望可能的研究和发展方向.

    Abstract:

    The Internet has become a vital information infrastructure for modern society. However, the concurrent nature of network introduces a wide-range of difficulties in traditional programming methodology in developing high-quality network programs that significantly reduce productivity. The influence of concurrency on the complexity of software development is comparable to the “concurrency crisis” of software brought by multi-core processors, but it receives much less attention here than what it deserves. There is no universal approach to cope with this issue, and there are even disagreements between different approaches. In this paper, the basic concurrency models and their implementations are introduced, and then the paper surveys the inherent complexities of these approaches, comparing their advantages and disadvantages. Finally, this paper offers an opinion on the possibilities for future research on this topic.

    参考文献
    [1] Lazowska ED, Patterson DA. Distributed computing. Science, 2005,308(6).
    [2] Hoffman D, Novak T, Venkatesh A. Has the Internet become indispensable? Communications of the ACM, 2004,47(7):37-42 . [doi: 10.1145/1005817.1005818]
    [3] CNNIC. The 23rd Report on the Development of Internet in China. 2009 (in Chinese). http://www.cnnic.net.cn
    [4] Li DY. Software engineering in the network era. Communications of CCF, 2009,1:7-12 (in Chinese with English abstract).
    [5] Killian CE, Anderson JW, Braud R, Jhala R, Vahdat AM. Mace: Language support for building distributed systems. In: Proc. of the 2007 ACM SIGPLAN Conf. on Programming Language Design and Implementation (PLDI 2007). New York: ACM, 2007. 179-188 . http://portal.acm.org/citation.cfm?id=1250734.1250755
    [6] Li HB, Peng YX, Lu XC. The composability problem of events and threads in distributed systems. In: Proc. of the 2010 Int’l Conf. on Education Technology and Computer (ICETC 2010). Shanghai, 2010. http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber= 5529673
    [7] Adya A, Howell J, Theimer M, Bolosky WJ, Douceur JR. Cooperative task management without manual stack management. In: Proc. of the General Track of the Annual Conf. on USENIX Annual Technical Conf. (ATEC 2002). Berkeley: USENIX Association, 2002. 289-302 . http://www.usenix.org/events/usenix02/adyahowell.html
    [8] Ousterhout JK. Why threads are a bad idea (for most purposes). In: Proc. of the Presentation Given at the ’96 Usenix Annual Technical Conf. Berkeley: USENIX Association, 1996. http://home.pacbell.net/ouster/threads.pdf
    [9] von Behren R, Condit J, Brewer E. Why events are a bad idea (for high-concurrency servers). In: Proc. of the 9th Conf. on Hot Topics in Operating Systems (HOTOS 2003). Berkeley: USENIX Association, 2003. http://www.usenix.org/events/hotos03/ tech/vonbehren.html
    [10] von Behren R, Condit J, Zhou F, Necula GC, Brewer E. Capriccio: Scalable threads for Internet services. In: Proc. of the 9th ACM Symp. on Operating systems Principles (SOSP 2003). New York: ACM, 2003. 268-281 . http://portal.acm.org/citation.cfm?id= 945471 [doi: 10.1145/1165389.945471]
    [11] Lee EA. The problem with threads. Technical Report, No.UCB/EECS-2006-1, 2006. http://www.eecs.berkeley.edu/Pubs/TechRpts/ 2006/EECS-2006-1.html
    [12] DeCandia G, Hastorun D, Jampani M, Kakulapati G, Lakshman A, Pilchin A, Sivasubramanian S, Vosshall P, Vogels W. Dynamo: Amazon’s highly available key-value store. In: Proc. of the 11th ACM Symp. on Operating Systems Principles (SOSP 2007). Washington: ACM, 2007. 205-220 . http://portal.acm.org/citation.cfm?id=1294261.1294281
    [13] Lee EA. Threaded composite: A mechanism for building concurrent and parallel Ptolemy II models. Technical Report, No.UCB/EECS-2008-151. 2008. http://www.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-151.html
    [14] Jr. Halstead RH. Multilisp: A language for concurrent symbolic computation. ACM Trans. on Program Language System, 1985,7(4):501-538 . [doi: 10.1145/4472.4478]
    [15] Zeldovich N, Yip A, Dabek F, Morris R, Mazieres D, Kaashoek F. Multiprocessor support for event-driven programs. In: Proc. of the 2003 USENIX Annual Technical Conf. (USENIX 2003). San Antonio, 2003. http://www.usenix.org/events/usenix03/tech/ zeldovich.html
    [16] Lauer HC, Needham RM. On the duality of operating system structures. SIGOPS Operating System Review, 1979,13(2):3-19 .
    [17] Krohn M, Kohler E, Kaashoek MF. Events can make sense. In: Proc. of the General Track of the Annual Conf. on USENIX Annual Technical Conf. (ATEC 2007). 2007. http://www.usenix.org/event/usenix07/tech/krohn.html
    [18] Li P, Zdancewic S. Combining events and threads for scalable network services. In: Proc. of the 2007 ACM SIGPLAN Conf. on Programming Language Design and Implementation (PLDI 2007). New York: ACM, 2007. 189-199 . http://portal.acm.org/ citation.cfm?id=1273442.1250756 [doi: 10.1145/1273442.1250756]
    [19] Dunkels A, Schmidt O, Voigt T, Ali M. Protothreads: Simplifying event-driven programming of memory-constrained embedded systems. In: Proc. of the 4th Int’l Conf. on Embedded Networked Sensor Systems (SenSys 2006). 2006. 29-42 . http://portal.acm. org/citation.cfm?id=1182807.1182811 [doi: 10.1145/1182807.1182811]
    [20] Fischer J, Majumdar R, Millstein T. Tasks: Language support for event-driven programming. In: Proc. of the 2007 ACM SIGPLAN Symp. on Partial Evaluation and Semantics-Based Program Manipulation (PEPM 2007). New York: ACM, 2007. 134-143 . http://portal.acm.org/citation.cfm?id=1244403 [doi: 10.1145/1244381.1244403]
    [21] Dabek F, Zeldovich N, Kaashoek F, Maziμeres D, Morris R. Event-Driven programming for robust software. In: Proc. of the 10th Workshop on ACM SIGOPS European Workshop. New York: ACM, 2002. 186-189 . http://portal.acm.org/citation.cfm?id= 1133373.1133410 [doi: 10.1145/1133373.1133410]
    [22] Abelson H, Sussman G. Structure and Interpretation of Computer Programs. Cambridge: Massachusetts Institute of Technology Press, 1984.
    [23] Wadler P. Monads for functional programming. In: Proc. of the 1st Int’l Spring School on Advanced Functional Programming Techniques-Tutorial Text. 1995. 24-52 . http://www.springerlink.com/content/715264614rh13340/
    [24] Cunningham R, Kohler E. Making events less slippery with eel. In: Proc. of the 10th Conf. on Hot Topics in Operating Systems (HOTOS 2005). Berkeley: USENIX Association, 2005. 3. http://www.usenix.org/events/hotos05/final_papers/cunningham.html
    [25] Gay D, Levis P, von Behren R, Welsh M, Brewer E, Culler D. The NesC language: A holistic approach to networked embedded systems. In: Proc. of the Programming Language Design and Implementation (PLDI 2003). ACM, 2003. http://portal.acm.org/ citation.cfm?id=781131.781133 [doi: 10.1145/780822.781133]
    [26] Rajagopalan M, Debray SK, Hiltunen MA, Schlichting RD. Profile-Directed optimization of event-based programs. In: Proc. of the 2002 ACM SIGPLAN Conf. on Programming Language Design and Implementation (PLDI 2002). Berlin: ACM, 2002. 106-116 . http://portal.acm.org/citation.cfm?id=512543 [doi: 10.1145/543552.512543]
    [27] Hayden MG. The ensemble system [Ph.D. Thesis]. New York: Graduate School, Cornell University, 1998.
    [28] Bhatia S, Consel C, Lawall J. Memory-Manager/Scheduler co-design: Optimizing event-driven servers to improve cache behavior. In: Proc. of the 5th Int’l Symp. on Memory Management. 2006. 104-114 . http://portal.acm.org/citation.cfm?id=1133971 [doi: 10.1145/1133956.1133971]
    [29] Gu BC, Kim YT, Heo JY, Cho YK. Shared-Stack cooperative threads. In: Proc. of the 2007 ACM Symp. on Applied Computing (SAC 2007). 2007. http://portal.acm.org/citation.cfm?id=1244002.1244258 [doi: 10.1145/1244002.1244258]
    [30] Shivers O, Might M. Continuations and transducer composition. In: Proc. of the 2006 ACM SIGPLAN Conf. on Programming Language Design and Implementation (PLDI 2006). Ottawa, 2006. 295-307 . http://portal.acm.org/citation.cfm?id=1133981. 1134016 [doi: 10.1145/1133981.1134016]
    [31] Jr. Baker HG, Hewitt C. The incremental garbage collection of processes. In: Proc. of the ’77 Symp. on Artificial Intelligence and Programming Languages. ACM Press, 1977. 55-59 . http://portal.acm.org/citation.cfm?id=800228.806932 [doi: 10.1145/ 800228.806932]
    [32] Wagner DB, Calder BG. Leapfrogging: A portable technique for implementing efficient futures. In: Proc. of the ACM Symp. on Principles and Practice of Parallel Programming. 1993. 208-217 . http://portal.acm.org/citation.cfm?id=155332.155354 [doi: 10.1145/155332.155354]
    [33] Kranz DA, Jr. Halstead RH, Mohr E. Mul-T: A high-performance parallel lisp. In: Proc. of the ACM SIGPLAN’89 Conf. on Programming Language Design and Implementation (PLDI). ACM Press, 1989. 81-90 . http://portal.acm.org/citation.cfm?id=74818. 74825 [doi: 10.1145/74818.74825]
    [34] Mohr E, Kranz DA, Jr. Halstead RH. Lazy task creation: A technique for increasing the granularity of parallel programs. IEEE Trans. on Parallel and Distributed Systems, 1991,2(3):264-280 . [doi: 10.1145/91556.91631]
    [35] Van Devoorde MT, Roberts ES. WorkCrews: An abstraction for controlling parallelism. Int’l Journal of Parallel Programming, 1988,17(4):347-366 . [doi: 10.1007/BF01407910]
    [36] Caromel D, Delbe C, di Costanzo A, Leyton M. ProActive: An integrated platform for programming and running applications on grids and P2P systems. Computational Methods in Science And Technology, 2006,12(1):69-77 .
    [37] Zhang LL, Krintz C, Soman S. Efficient support of fine-grained futures in Java. In: Proc. of the Int’l Conf. on Parallel and Distributed Computing Systems (PDCS 2006). 2006. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.67.966&rep=rep1& type=pdf
    [38] Zhang LL, Krintz C, Nagpurkar P. Language and virtual machine support for efficient fine-grained futures in Java. In: Proc. of the 16th Int’l Conf. on Parallel Architecture and Compilation Techniques (PACT 2007). IEEE, 2007. http://portal.acm.org/citation.cfm? id=1299043 [doi: 10.1109/PACT.2007.45]
    [39] Zhang LL, Krintz C, Nagpurkar P. Supporting exception handling for futures in Java. In: Proc. of the Principles and Practice of Programming in Java (PPPJ 2007). 2007. http://portal.acm.org/citation.cfm?id=1294349
    [40] Zhang LL. Exploiting adaptation in a Java virtual machine to enable both programmer productivity and performance for heterogeneous devices [Ph.D. Thesis]. Santa Barbara: Graduate School, University of California Santa Barbara, 2008.
    [41] Welc A, Jagannathan S, Hosking A. Safe futures for Java. In: Proc. of the 20th Annual ACM SIGPLAN Conf. on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA 2005). 2005. http://portal.acm.org/citation.cfm?id=1094845
    [42] Hill J, Szewczyk R, Woo A, Hollar S, Culler DE, Pister KSJ. System architecture directions for networked sensors. In: Proc. of the 9th Int’l Conf. on Architectural Support for Programming Languages and Operating Systems. Boston, 2000. 93-104 . http://portal.acm.org/citation.cfm?id=356989.356998 [doi: 10.1145/356989.356998]
    [43] Oancea C, Selby JWA, Giesbrecht MW, Watt SM. Distributed models of thread-level speculation. In: Proc. of the 2005 Int’l Conf. on Parallel and Distributed Processing Techniques and Applications (PDPTA 2005). 2005. http://citeseerx.ist.psu.edu/viewdoc/ download?doi=10.1.1.110.7774&rep=rep1&type=pdf
    [44] Li HB, Liu SY, Peng YX, Li DS, Zhou HJ, Lu XC. Superscalar communication: A runtime optimization for distributed applications. Science China (Information Sciences), 2010,53:1931-1946 . [doi: 10.1007/s11432-010-4051-4]
引用本文

李慧霸,田甜,彭宇行,李东升,卢锡城.网络程序设计中的并发复杂性.软件学报,2011,22(1):132-148

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2009-12-10
  • 最后修改日期:2010-06-09
文章二维码
您是第19791829位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号