リード・コピー・アップデート
(read-copy-update から転送)
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/07/12 04:50 UTC 版)
リード・コピー・アップデート（read-copy-update、RCUと略記）とは、オペレーティングシステムにおいて一種の排他制御[note 1]を実装する同期機構であり、リーダー・ライターロックの代替手段として使われることがある。参照において待ち状態が生じず、極めてオーバーヘッドが低い。しかしRCUにおけるデータ更新は、既存の参照者のために古い版のデータ構造を保持しつつ行うため、時間と空間（メモリ）をより多く必要とする。古い版のデータ構造は、既存の参照者が全てアクセスを完了した後で回収される。
注釈
- ^ RCU は一般的な意味での排他制御の実装ではない。通常の排他制御機構が時間的に排他するのに対して、RCUではデータを更新中もデータの古いバージョンへの参照を同時に行えるようにすることで、空間的な排他を行う。
- ^ 削除フェーズ中に動作中の参照者のみを考慮する必要がある。削除フェーズ後に動作開始した参照者は削除された旧版のデータへの参照が不可能なためであり、再利用フェーズに影響されることがない。
- ^ 可能ならばこのステップでガベージコレクションを行うこともある。
- ^ RCUでもデッドロックは発生しうる。例えばRCU参照側クリティカルセクション内で猶予期間が完了するまでブロックする操作を行った場合などである。
出典
- ^ Guniguntala, Dinakar; McKenney, Paul E.; Triplett, Joshua; Walpole, Jonathan (2008). “The read-copy-update mechanism for supporting real-time applications on shared-memory multiprocessor systems with Linux”. IBM Systems Journal 47 (2): 221–236. doi:10.1147/sj.472.0221.
- ^ McKenney, Paul E. (2007年12月17日). “What is RCU, Fundamentally?”. Linux Weekly News. 2010年9月24日閲覧。
- ^ McKenney, Paul E.; Slingwine, John D. (October 1998). Read-Copy Update: Using Execution History to Solve Concurrency Problems (PDF). Parallel and Distributed Computing and Systems. pp. 509–518.
- ^ Olsson, Robert; Nilsson, Stefan (May 2007). TRASH: A dynamic LC-trie and hash table structure. Workshop on High Performance Switching and Routing (HPSR'07).
- ^ Piggin, Nick (July 2006). A Lockless Pagecache in Linux---Introduction, Progress, Performance (PDF). Ottawa Linux Symposium.
- ^ McKenney, Paul E.; Walpole, Jonathan (July 2008). “Introducing technology into the Linux kernel: a case study”. SIGOPS Oper. Syst. Rev. 42 (5): 4–17. doi:10.1145/1400097.1400099.
- ^ Kannan, Hari (2009). Ordering decoupled metadata accesses in multiprocessors. MICRO 42: Proceedings of the 42nd Annual IEEE/ACM International Symposium on Microarchitecture. New York, NY, USA. pp. 381–390. doi:10.1145/1669112.1669161. ISBN 978-1-60558-798-1。
- ^ Matthews, Chris; Coady, Yvonne; Appavoo, Jonathan (2009). Portability events: a programming model for scalable system infrastructures. PLOS '06: Proceedings of the 3rd workshop on Programming languages and operating systems. San Jose, CA, USA. doi:10.1145/1215995.1216006. ISBN 1-59593-577-0。
- ^ Da Silva, Dilma; Krieger, Orran; Wisniewski, Robert W.; Waterland, Amos; Tam, David; Baumann, Andrew (April 2006). “K42: an infrastructure for operating system research”. SIGOPS Oper. Syst. Rev. 40 (2): 34–42. doi:10.1145/1131322.1131333.
- ^ Appavoo, Jonathan; Da Silva, Dilma; Krieger, Orran; Auslander, Mark; Ostrowski, Michal; Rosenburg, Bryan; Waterland, Amos; Wisniewski, Robert W. et al. (August 2007). “Experience distributing objects in an SMMP OS”. ACM Trans. Comput. Syst. 25 (3): 6/1–6/52. doi:10.1145/1275517.1275518.
- ^ Fraser, Keir; Harris, Tim (2007). “Concurrent programming without locks”. ACM Trans. Comput. Syst. (ACM) 25 (2): 34–42. doi:10.1145/1233307.1233309.
- ^ Porter, Donale E.; Hofmann, Owen S.; Rossbach, Christopher J.; Benn, Alexander; Witchel, Emmett (2009). Operating systems transactions infrastructures. SOSP '09: Proceedings of the ACM SIGOPS 22nd symposium on Operating systems principles. Big Sky, MT, USA: ACM. doi:10.1145/1629575.1629591. ISBN 978-1-60558-752-3。
- ^ Hart, Thomas E.; McKenney, Paul E.; Demke Brown, Angela; Walpole, Jonathan (December 2007). “Performance of memory reclamation for lockless synchronization”. J. Parallel Distrib. Comput. 67: 1270–1285.
- ^ McKenney, Paul E. (2008年1月4日). “RCU part 2: Usage”. Linux Weekly News. 2010年9月24日閲覧。
- ^ Desnoyers, Mathieu (December 2009). “Low-Impact Operating System Tracing”. Ecole Polytechnique de Montreal.
- ^ McKenney, Paul E. (2008年1月17日). “RCU part 3: the RCU API”. Linux Weekly News. 2010年9月24日閲覧。
- ^ McKenney, Paul E.; Appavoo, Jonathan; Kleen, Andi; Krieger, Orran; Russell, Rusty; Sarma, Dipankar; Soni, Maneesh (July 2001). Read-Copy Update (PDF). Ottawa Linux Symposium.
- ^ Wizard, The (2001年8月). “Shared Memory, Threads, Interprocess Communication”. Hewlett-Packard. 2010年12月26日閲覧。
- ^ McKenney, Paul E. (2003年10月). “Using {RCU} in the {Linux} 2.5 Kernel”. Linux Journal. 2010年9月24日閲覧。
- ^ McKenney, Paul E. (July 2004). “Exploiting Deferred Destruction: An Analysis of Read-Copy-Update Techniques”. OGI School of Science and Engineering at Oregon Health and Sciences University.
- ^ Kung, H. T.; Lehman, Q. (September 1980). “Concurrent Maintenance of Binary Search Trees”. ACM Transactions on Database Systems 5 (3): 354. doi:10.1145/320613.320619.
- ^ Manber, Udi; Ladner, Richard E. (September 1984). “Concurrency Control in a Dynamic Search Structure”. ACM Transactions on Database Systems 9 (3).
- ^ Rashid, Richard; Tevanian, Avadis; Young, Michael; Golub, David; Baron, Robert; Bolosky, William; Chew, Jonathan (January 1995). Machine-Independent Virtual Memory Management for Paged Uniprocessor and Multiprocessor Architectures (PDF). Second Symposium on Architectural Support for Programming Languages and Operating Systems. Association for Computing Machinery.
- ^ 4,809,168, "Passive Serialization in a Multitasking Environment"
- ^ Pugh, William (June 1990). Concurrent Maintenance of Skip Lists (Technical report). Institute of Advanced Computer Science Studies, Department of Computer Science, University of Maryland. CS-TR-2222.1。
- ^ John, Aju (January 1995). Dynamic vnodes — design and implementation. USENIX Winter 1995.
- ^ 5,442,758, "Apparatus and Method for Achieving Reduced Overhead Mutual Exclusion and Maintaining Coherency in a Multiprocessor System"
- ^ Gamsa, Ben; Krieger, Orran; Appavoo, Jonathan; Stumm, Michael (February 1999). Tornado: Maximizing Locality and Concurrency in a Shared Memory Multiprocessor Operating System (PDF). Proceedings of the Third Symposium on Operating System Design and Implementation.
- ^ Russell, Rusty (2000年6月). “Re: modular net drivers”. 2012年3月28日閲覧。
- ^ Russell, Rusty (2000年6月). “Re: modular net drivers”. 2012年3月28日閲覧。
- ^ Summary of changes from v2.5.42 to v2.5.43
- ^ Colvin, Robert; Groves, Lindsay; Luchangco, Victor; Moir, Mark (August 2006). Formal Verification of a Lazy Concurrent List-Based Set Algorithm (PDF). Computer Aided Verification (CAV 2006).
[続きの解説]
「リード・コピー・アップデート」の続きの解説一覧
固有名詞の分類
| 排他制御 | 複数粒度ロック コンペア・アンド・スワップ リード・コピー・アップデート コミットメント順序付け 操作変換 |
- リード・コピー・アップデートのページへのリンク
