Introducing technology into the Linux kernel

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Introducing technology into the Linux kernel: a case study

Full text

Pdf (1.05 MB)

Source

ACM SIGOPS Operating Systems Review archive
Volume 42 , Issue 5 (July 2008) table of contents
Research and developments in the Linux kernel

Pages 4-17

Year of Publication: 2008

ISSN:0163-5980

Authors

Paul E. McKenney	IBM Beaverton
Jonathan Walpole	Portland State University

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 258, Downloads (12 Months): 2380, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTex EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1400097.1400099 What is a DOI?

ABSTRACT

There can be no doubt that a great many technologies have been added to Linux™ over the past ten years. What is less well-known is that it is often necessary to introduce a large amount of Linux into a given technology in order to successfully introduce that technology into Linux. This paper illustrates such an introduction of Linux into technology with Read-Copy Update (RCU). The RCU API's evolution over time clearly shows that Linux's extremely diverse set of workloads and platforms has changed RCU to a far greater degree than RCU has changed Linux---and it is reasonable to expect that other technologies that might be proposed for inclusion into Linux would face similar challenges. In addition, this paper presents a summary of lessons learned and an attempt to foresee what additional challenges Linux might present to RCU.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Arcangeli, A., Cao, M., McKenney, P. E., and Sarma, D. Using read-copy update techniques for System V IPC in the Linux 2.5 kernel. In Proceedings of the 2003 USENIX Annual Technical Conference (FREENIX Track) (June 2003), USENIX Association, pp. 297--310.
	2	Axboe, J. Re: [patch] cpufreq: mark cpufreq_tsc() as core_initcall_sync. Available: http://lkml.org/lkml/2006/11/17/56 [Viewed May 28, 2007], November 2006.
	3	Ben-Yehuda, M., and Hensbergen, E. V. Open source as a foundation for systems research. SIGOPS Oper. Syst. Rev. 42, 1 (2008), 2--4.
	4	Corbet, J. Approaches to realtime Linux. Available: http://lwn.net/Articles/106010/ [Viewed March 25, 2008], October 2004.
	5	Corbet, J. Realtime preemption, part 2. Available: http://lwn.net/Articles/107269/ [Viewed March 25, 2008], October 2004.
	6	Corbet, J. Realtime preemption and read-copy-update. Available: http://lwn.net/Articles/129511/ [Viewed October 17, 2005], March 2005.
	7	Corbet, J. 2.6.24 - some statistics. Available: http://lwn.net/Articles/264440/ [Viewed March 25, 2008], January 2008.
	8	Desnoyers, M. Re: [patch 1/2] Linux kernel markers - support multiple probes. Available: http://lkml.org/lkml/2007/12/20/244 [Viewed March 27, 2008], December 2007.
	9	Gamsa, B., Krieger, O., Appavoo, J., and Stumm, M. Tornado: Maximizing locality and concurrency in a shared memory multiprocessor operating system. In Proceedings of the 3^rd Symposium on Operating System Design and Implementation (New Orleans, LA, February 1999), pp. 87--100.
	10	Gharachorloo, K. Memory consistency models for shared-memory multiprocessors. Tech. Rep. CSL-TR-95-685, Computer Systems Laboratory, Departments of Electrical Engineering and Computer Science, Stanford University, Stanford, CA, December 1995.
	11	Guniguntala, D., McKenney, P. E., Triplett, J., and Walpole, J. The read-copy-update mechanism for supporting real-time applications on shared-memory multiprocessor systems with Linux. IBM Systems Journal 47, 2 (May 2008), 221--236.
	12	Hart, T. E., McKenney, P. E., Brown, A. D., and Walpole, J. Performance of memory reclamation for lockless synchronization. J. Parallel Distrib. Comput. 67, 12 (2007), 1270--1285.
	13	Hellwig, C. Re: [-mm PATCH 1/4] RCU: split classic rcu. Available: http://lkml.org/lkml/2006/9/28/160 [Viewed March 27, 2008], September 2006.
	14	Hennessy, J. P., Osisek, D. L., and Seigh II, J. W. Passive serialization in a multitasking environment. Tech. Rep. US Patent 4,809,168 (lapsed), US Patent and Trademark Office, Washington, DC, February 1989.
	15	Houston, J. [RFC&PATCH] Alternative RCU implementation. Available: http://marc.theaimsgroup.com/?l=linux-kernel&m=109387402400673&w=2 [Viewed February 17, 2005], August 2004.
	16	Hsieh, W. C., and Weihl, W. E. Scalable reader-writer locks for parallel systems. In Proceedings of the 6^th International Parallel Processing Symposium (Beverly Hills, CA, USA, March 1992), pp. 216--230.
	17	Jacobson, V. Avoid read-side locking via delayed free. Verbal discussion, September 1993.
	18	John, A. Dynamic vnodes -- design and implementation. In USENIX Winter 1995 (New Orleans, LA, January 1995), USENIX Association, pp. 11--23.
	19	Kung, H. T., and Lehman, Q. Concurrent maintenance of binary search trees. ACM Transactions on Database Systems 5, 3 (September 1980), 354--382.
	20	Liskov, B. Distributed programming in Argus. Commun. ACM 31, 3 (1988), 300--312.
	21	Manber, U., and Ladner, R. E. Concurrency control in a dynamic search structure. ACM Transactions on Database Systems 9, 3 (September 1984), 439--455.
	22	McKenney, P. E. Stochastic fairness queuing. In IEEE INFOCOM'90 Proceedings (San Francisco, June 1990), The Institute of Electrical and Electronics Engineers, Inc., pp. 733--740.
	23	McKenney, P. E. Exploiting Deferred Destruction: An Analysis of Read-Copy-Update Techniques in Operating System Kernels. PhD thesis, OGI School of Science and Engineering at Oregon Health and Sciences University, 2004. Available: http://www.rdrop.com/users/paulmck/RCU/RCUdissertation.2004.07.14e1.pdf [Viewed October 15, 2004].
	24	McKenney, P. E. RCU vs. locking performance on different CPUs. In linux. conf. au (Adelaide, Australia, January 2004). Available: http://www.rdrop.com/users/paulmck/RCU/lockperf.2004.01.17a.pdf [Viewed June 23, 2004].
	25	McKenney, P. E. Memory ordering in modern microprocessors, part I. Linux Journal 1, 136 (August 2005), 52--57. Available: http://www.rdrop.com/users/paulmck/scalability/paper/ordering.2007.09.19a.pdf [Viewed November 30, 2007].
	26	McKenney, P. E. RCU Linux usage. Available: http://www.rdrop.com/users/paulmck/RCU/linuxusage.html [Viewed January 14, 2007], October 2006.
	27	McKenney, P. E. Sleepable RCU. Available: http://www.rdrop.com/users/paulmck/RCU/srcu.2007.01.14a.pdf [Viewed August 21, 2006], October 2006.
	28	McKenney, P. E. The design of preemptible read-copy-update. Available: http://lwn.net/Articles/253651/ [Viewed October 25, 2007], October 2007.
	29	McKenney, P. E. [PATCH] QRCU with lockless fastpath. Available: http://lkml.org/lkml/2007/2/25/18 [Viewed March 27, 2008], February 2007.
	30	McKenney, P. E. Priority-boosting RCU read-side critical sections. Available: http://www.rdrop.com/users/paulmck/RCU/RCUbooststate.2007.04.16a.pdf [Viewed September 7, 2007], February 2007.
	31	McKenney, P. E. RCU and unloadable modules. Available: http://lwn.net/Articles/217484/ [Viewed November 22, 2007], January 2007.
	32	McKenney, P. E. Using Promela and Spin to verify parallel algorithms. Available: http://lwn.net/Articles/243851/ [Viewed September 8, 2007], August 2007.
	33	McKenney, P. E. RCU part 3: the RCU API. Available: http://lwn.net/Articles/264090/ [Viewed January 10, 2008], January 2008.
	34	McKenney, P. E. What is RCU? part 2: Usage. Available: http://lwn.net/Articles/263130/ [Viewed January 4, 2008], January 2008.
	35	McKenney, P. E., Appavoo, J., Kleen, A., Krieger, O., Russell, R., Sarma, D., and Soni, M. Read-copy update. In Ottawa Linux Symposium (July 2001). Available: http://www.rdrop.com/users/paulmck/RCU/rclock_OLS.2001.05.01c.pdf [Viewed June 23, 2004].
	36	McKenney, P. E., and Sarma, D. Read-copy update mutual exclusion in Linux. Available: http://lse.sourceforge.net/locking/rcu/rcupdate_doc.html [Viewed October 18, 2004], February 2001.
	37	McKenney, P. E., and Sarma, D. Towards hard realtime response from the Linux kernel on SMP hardware. In linux.conf.au 2005 (Canberra, Australia, April 2005). Available: http://www.rdrop.com/users/paulmck/RCU/realtimeRCU.2005.04.23a.pdf [Viewed May 13, 2005].
	38	McKenney, P. E., Sarma, D., Arcangeli, A., Kleen, A., Krieger, O., and Russell, R. Read-copy update. In Ottawa Linux Symposium (June 2002), pp. 338--367. Available: http://www.linux.org.uk/~ajh/ols2002_proceedings.pdf.gz [Viewed June 23, 2004].
	39	McKenney, P. E., Sarma, D., Molnar, I., and Bhattacharya, S. Extending RCU for realtime and embedded workloads. In Ottawa Linux Symposium (July 2006), pp. v2 123--138. Available: http://www.linuxsymposium.org/2006/view_abstract.php?content_key=184 http://www.rdrop.com/users/paulmck/RCU/OLSrtRCU.2006.08.11a.pdf [Viewed January 1, 2007].
	40	McKenney, P. E., and Slingwine, J. D. Read-copy update: Using execution history to solve concurrency problems. In Parallel and Distributed Computing and Systems (Las Vegas, NV, October 1998), pp. 509--518. Available: http://www.rdrop.com/users/paulmck/RCU/rclockpdcsproof.pdf [Viewed December 3, 2007].
	41	McKenney, P. E., and Walpole, J. What is RCU, fundamentally? Available: http://lwn.net/Articles/262464/ [Viewed December 27, 2007], December 2007.
	42	Meuer, H., Dongarra, J., Strohmaier, E., and Simon, H. Top 500 supercomputer sites: Operating system family share. Available: http://www.top500.org/stats/list/30/osfam [Viewed March 25, 2008], November 2007.
	43	Minyard, C., and McKenney, P. E. [PATCH] add an RCU version of list splicing. Available: http://lkml.org/lkml/2007/1/3/112 [Viewed May 28, 2007], January 2007.
	44	Molnar, I., and Miller, D. S. brlock. Available: http://www.tm.kernel.org/pub/linux/kernel/v2.3/patch-html/patch-2.3.49/linux_include_linux_brlock.h.html [Viewed September 3, 2004], March 2000.
	45	Morris, J. Recent developments in SELinux kernel performance. Available: http://www.livejournal.com/users/james_morris/2153.html [Viewed December 10, 2004], December 2004.
	46	Nesterov, O. Re: [patch] cpufreq: mark cpufreq_tsc() as core_initcall_sync. Available: http://lkml.org/lkml/2006/11/19/69 [Viewed May 28, 2007], November 2006.
	47	Olsson, R., and Nilsson, S. TRASH: A dynamic LC-trie and hash data structure. Available: http://www.nada.kth.se/~snilsson/public/papers/trash/trash.pdf [Viewed February 24, 2007], August 2006.
	48	Piggin, N. [patch 3/3] radix-tree: RCU lockless readside. Available: http://lkml.org/lkml/2006/6/20/238 [Viewed March 25, 2008], June 2006.
	49	Pugh, W. Concurrent maintenance of skip lists. Tech. Rep. CS-TR-2222.1, Institute of Advanced Computer Science Studies, Department of Computer Science, University of Maryland, College Park, Maryland, June 1990.
	50	Rashid, R., Tevanian, A., Young, M., Golub, D., Baron, R., Black, D., Bolosky, W., and Chew, J. Machine-independent virtual memory management for paged uniprocessor and multiprocessor architectures. In 2^nd Symposium on Architectural Support for Programming Languages and Operating Systems (Palo Alto, CA, October 1987), Association for Computing Machinery, pp. 31--39.
	51	Rossbach, C. J., Hofmann, O. S., Porter, D. E., Ramadan, H. E., Bhandari, A., and Witchel, E. TxLinux: Using and managing hardware transactional memory in an operating system. In SOSP'07: Twenty-First ACM Symposium on Operating Systems Principles (October 2007), ACM SIGOPS.
	52	Rostedt, S., and McKenney, P. E. [PATCH] add support for dynamic ticks and preempt rcu. Available: http://lkml.org/lkml/2008/1/29/208 [Viewed March 27, 2008], January 2008.
	53	Russell, R. Re: modular net drivers. Available: http://oss.sgi.com/projects/netdev/archive/2000-06/msg00250.html [Viewed April 10, 2006], June 2000.
	54	Sarma, D., and McKenney, P. E. Making RCU safe for deep sub-millisecond response realtime applications. In Proceedings of the 2004 USENIX Annual Technical Conference (FREENIX Track) (June 2004), USENIX Association, pp. 182--191.
	55	Seigh, J. Lock-free synchronization primitives. Available: http://sourceforge.net/projects/atomic-ptr-plus/ [Viewed August 8, 2005], July 2005.
	56	Spraul, M. Re: RFC: patch to allow lock-free traversal of lists with insertion. Available: http://marc.theaimsgroup.com/?l=linux-kernel&m=100264675012867&w=2 [Viewed June 23, 2004], October 2001.
	57	Spraul, M. [rfc] 0/5 rcu lock update. Available: http://marc.theaimsgroup.com/?l=linux-kernel&m=108546407726602&w=2 [Viewed June 23, 2004], May 2004.
	58	Torvalds, L. Linux 2.5.43. Available: http://lkml.org/lkml/2002/10/15/425 [Viewed March 30, 2008], October 2002.
	59	Torvalds, L. Linux 2.5.69. Available: http://marc.theaimsgroup.com/?l=linux-kernel&m=105209603501299&w=2 [Viewed June 23, 2004], May 2003.
	60	Torvalds, L. Linux 2.5.70. Available: http://marc.theaimsgroup.com/?l=linux-kernel&m=105400162802746&w=2 [Viewed June 23, 2004], May 2003.
	61	Transaction Processing Performance Council. TPC benchmark A. Available: http://www.tpc.org/tpca/default.asp [Viewed July 6, 2007], November 1989.
	62	Zijlstra, P., and Molnar, I. [PATCH 3/7] barrier: a scalable synchonisation barrier. Available: http://lkml.org/lkml/2007/1/28/34 [Viewed March 27, 2008], January 2007.