Read-Copy-Update for HelenOS
| Název práce v češtině: | Read-Copy-Update pro HelenOS |
|---|---|
| Název v anglickém jazyce: | Read-Copy-Update for HelenOS |
| Klíčová slova: | HelenOS, RCU, Read-Copy Update, concurrency |
| Klíčová slova anglicky: | HelenOS, RCU, Read-Copy Update, concurrency |
| Akademický rok vypsání: | 2012/2013 |
| Typ práce: | diplomová práce |
| Jazyk práce: | angličtina |
| Ústav: | Katedra distribuovaných a spolehlivých systémů (32-KDSS) |
| Vedoucí / školitel: | Mgr. Martin Děcký, Ph.D. |
| Řešitel: | skrytý - zadáno a potvrzeno stud. odd. |
| Datum přihlášení: | 29.11.2012 |
| Datum zadání: | 29.11.2012 |
| Datum potvrzení stud. oddělením: | 06.12.2012 |
| Datum a čas obhajoby: | 09.09.2013 00:00 |
| Datum odevzdání elektronické podoby: | 02.08.2013 |
| Datum odevzdání tištěné podoby: | 02.08.2013 |
| Datum proběhlé obhajoby: | 09.09.2013 |
| Oponenti: | RNDr. Andrej Podzimek, Ph.D. |
| Zásady pro vypracování |
| The goal of this thesis is to identify kernel and user space subsystems in the HelenOS microkernel multiserver operating system which might benefit from the utilization of an RCU (Read-Copy-Update) synchronization mechanism and to design, implement and deploy a variant of RCU in HelenOS.
The main purpose of RCU is to increase concurrency in readers-writers synchronization scenarios, especially in SMP (Symmetric Multiprocessing) environments. This improvement can be achieved by keeping multiple versions of the protected data, which enables both readers and writers to run in parallel. Multiple different implementations of RCU exist and some of them are used in the Linux kernel. The thesis includes an analysis of common RCU variants, a prototype implementation of RCU suitable for HelenOS and testing and benchmarking code to evaluate possible benefits of RCU over mutual exclusion. |
| Seznam odborné literatury |
| [1] McKusick, M. K., Neville-Neil, G. V.: The Design and Implementation of the FreeBSD Operating System, 2004
[2] Hart T., McKenney P., Brown A.: Making Lockless Synchronization Fast: Performance Implications of Memory Reclamation, IPDPS, 2006 [3] McKenney P.: Exploiting Deferred Destruction: An Analysis of Read-Copy-Update Techniques in Operating System Kernels, Ph.D. Thesis, Oregon State University, 2004 [4] McKenney P.: Kernel Korner - Using RCU in the Linux 2.5 Kernel, Linux Journal, Art. 6993, 2003 [5] McKenney P.: Memory Ordering in Modern Microprocessors, Part I, Linux Journal, Art. 8211, 2005 [6] McKenney P.: Memory Ordering in Modern Microprocessors, Part II, Linux Journal, Art. 8212, 2005 [7] McDougall R., Mauro J.: Solaris Internals, Prentice Hall, Westford, 2006 [8] McKenney P.: Priority-Boosting RCU Read-Side Critical Sections, Linux Technology Center, IBM Beaverton, http://www.rdrop.com/users/paulmck/RCU/RCUbooststate.2007.04.16a.pdf, 2007 [9] McKenney P.: QRCU with Lockless Fastpath, Linux Weekly News, Art. 223752, 2007 [10] McKenney P.: Using Promela and Spin to verify parallel algorithms, Linux Weekly News, Art. 243851, 2007 [11] McKenney P.: The design of preemptible readcopy-update, Linux Weekly News, Art. 253651, 2007 [12] McKenney P., Walpole J.: What is RCU, Fundamentally?, Linux Weekly News, Art. 262464, 2007 [13] McKenney P.: What Is RCU? Part 2: Usage, Linux Weekly News, Art. 263130, 2007 [14] McKenney P.: What Is RCU, Really?, Linux Weekly News, http://www.rdrop.com/users/paulmck/RCU/whatisRCU.html, 2007 [15] McKenney P.: RCU part 3: the RCU API, Linux Weekly News, Art. 264090, 2008 [16] McKenney P.: Hierarchical RCU, Linux Weekly News, Art. 305782, 2008 [17] Podzimek A.: Read-Copy-Update for OpenSolaris, Diploma Thesis, Charles University in Prague, Faculty of Mathematics and Physics, 2010, http://d3s.mff.cuni.cz/publications/download/Podzimek-master.pdf, http://d3s.mff.cuni.cz/software/rcu/rcu.patch |
| Předběžná náplň práce |
| Cílem této diplomové práce je identifikovat jaderné a uživatelské subsystémy mikrojádrového multiserverového operačního systému HelenOS, ve kterých by bylo možné účelně využít synchronizační mechanismus RCU (Read-Copy-Update), a navrhnout, naimplementovat a použít variantu RCU v systému HelenOS
Hlavním účelem RCU je zvýšení paralelismu při synchronizaci čtenářů a zapisovatelů, zejména v prostředí symetrických multiprocesorových systémů (SMP). Tohoto lepšení lze dosáhnout udržováním několika verzí chráněných dat, což umožňuje čtenářům i zapisovatelům pracovat souběžně. Existuje několik různých implementací RCU a některé z nich se používají v kernelu Linux. Diplomová práce zahrnuje analýzu obvyklých variant RCU, prototypovou implementaci RCU vhodnou pro HelenOS a kód testů a benchmarků pro vyhodnocení možných výhod RCU ve srovnání se vzájemným vyloučením. |
| Předběžná náplň práce v anglickém jazyce |
| The goal of this thesis is to identify kernel and user space subsystems in the HelenOS microkernel multiserver operating system which might benefit from the utilization of an RCU (Read-Copy-Update) synchronization mechanism and to design, implement and deploy a variant of RCU in HelenOS.
The main purpose of RCU is to increase concurrency in readers-writers synchronization scenarios, especially in SMP (Symmetric Multiprocessing) environments. This improvement can be achieved by keeping multiple versions of the protected data, which enables both readers and writers to run in parallel. Multiple different implementations of RCU exist and some of them are used in the Linux kernel. The thesis includes an analysis of common RCU variants, a prototype implementation of RCU suitable for HelenOS and testing and benchmarking code to evaluate possible benefits of RCU over mutual exclusion. |