Linux锁机制：读-复制-更新策略详解

需积分: 11 46 浏览量更新于2024-07-18 收藏 236KB PDF 举报

本文档深入探讨了Linux系统中的Read-Copy-Update（RCU）锁机制，这是一种针对传统操作系统锁设计的创新方法，旨在解决并发性问题并充分利用操作系统的事件驱动特性。传统的锁定设计往往复杂且导致性能不佳，特别对于处理大量小规模、快速完成的工作负载，如Web服务器和数据库操作，而非CPU密集型科学计算应用。RCU的设计思路是将更新过程分为两个阶段： 1. **读复制** (Read-Copy): 在这个阶段，线程或进程首先创建一个新版本的数据副本，而原始数据仍保持不变。这样做避免了锁竞争，提高了并发访问的效率，因为多个线程可以同时读取旧版本的数据，而不会相互阻塞。 2. **更新操作** (Update): 当新的操作完成时，系统会进行数据更新，将新版本的数据与旧版本合并。由于更新是在读取旧版本之后进行的，所以不会影响到正在读取旧版本的其他线程，实现了“无锁”并发，提升了系统的吞吐量。 RCU特别适合于那些不需要立即可见性（即数据的一致性模型）的应用场景，例如内核中的某些数据结构，因为它们允许短暂的不一致状态。此外，RCU通过利用事件循环和延退确认（deferred synchronization）技术，进一步减少了锁的竞争和等待时间。本文作者包括Paul E. McKenney、Jonathan Appavoo、Andi Kleen、Orran Krieger、Rusty Russell、Dipankar Sarma和Maneesh Soni，分别来自Linux Technology Center、IBM、University of Toronto、SuSE Labs、IBM T.J. Watson Research Center以及印度的IBM实验室。他们共同展示了RCU在Linux内核中的实现原理和应用场景，以及它如何优化系统的并发性能，使之成为现代操作系统设计中一个重要的并发控制策略。

1 struct el *search(long addr)

2 {

3 struct el *p;

5 p = head->next;

6 while (p != head) {

7 if (p->address == addr) {

8 return (p);

9 }

10 p = p->next;

11 }

12 return (NULL);

13 }

Figure 8: Read-Copy Search

The search() function can return a reference to an

already-deleted element, but the kfree rcu() guar-

antees that the element will not be freed (and thus

possibly re-used for some other purpose) while this

reference exists (see Figure 20 for a deﬁnition of

kfree rcu()). There are a number of techniques

that may be used to ensure that search() returns

references only to elements that have not yet been

deleted; see Section 7.3 for an example. However,

there are quite a few algorithms that tolerate “stale

data”, for example, many algorithms that track

state external to the machine must deal with stale

data in any case due to communications delays.

The delete function is quite similar to that

of a single-threaded application, with the addi-

tion of locking, and with kfree() replaced by

kfree rcu(). The internal implementation of

kfree rcu() waits for a grace period before freeing

the speciﬁed block of memory (see Section 4.2), and

also provides the required read-write barriers that

allow this function to execute correctly on weakly

consistent machines.

The search() function contains absolutely no locks

or atomic instructions, which means that the per-

formance of this function will scale with CPU core

clock rate, rather than the much slower memory

latencies for an implementation based on locks or

atomic operations. In addition, the search() does

not disable interrupts, which means that read-copy

update can improve performance of UP as well as

SMP kernels. However, search() can return stale

data. This can be prevented, if need be, see for

example Section 7.3.

Note that delete() is very similar to its reference-

count counterpart, including the global lock. This

particular implementation will therefore give good

1 void delete(struct el *p)

2 {

3 spin_lock(&list_lock);

4 p->next->prev = p->prev;

5 p->prev->next = p->next;

6 spin_unlock(&list_lock);

7 kfree_rcu(p, NULL);

8 }

Figure 9: Read-Copy Deletion

1 /* Read-only access. */

3 p = search(addr);

4 /* Read-only access to the structure. */

5 /* Next yield of CPU acts as release. */

7 /* Access and deletion. */

9 spin_lock(&list_lock);

10 p = search(addr);

11 /* Access and update p. */

12 spin_unlock(&list_lock);

13 if (to_be_deleted) {

14 delete(p);

15 }

16 /* Next yield of CPU acts as release. */

Figure 10: Read-Copy search/delete Usage

speedups only if there are many more searches than

deletions. In many situations (e.g., routing-table

updates), this will be the case. In other situations,

the deletion function might use a more complex but

more highly parallel design.

Figure 10 shows how the read-copy search() and

delete() functions might be used. Line 3 shows

how a read-only operation might be carried out.

Note that there is absolutely no cacheline bounc-

ing if all operations are read-only. Lines 9-15 show

how an update operation, possibly including a dele-

tion, might be carried out. The list lock serializes

concurrent modiﬁcations.

2.3 Discussion

The reference-count and read-copy search() and

delete() functions each have their strengths. The

read-copy functions avoid all cacheline bouncing for

reading tasks, but can return references to deleted

elements, and cannot hold a reference to elements

across a voluntary context switch. There are hybrid

剩余21页未读，继续阅读

奔跑的小刺猬

粉丝: 3821
资源: 7

Linux锁机制：读-复制-更新策略详解

Sleepable Read-Copy Update

Verification of the Tree-Based Hierarchical Read-Copy Update in the Linux Kernel - 10th October, 2016 (1610.03052)-计算机科学

Linux内核源码深度解析与开发实战视频.zip

wait_rcu_gp

操作系统中RCU是什么？

为什么要引入读 - 复制 - 更新锁？ 它对读者和写者分别有何影响？

call_rcu_bh与call_rcu区别

内核启动流程中RCU的作用

linux 中SMP是什么？在内核中如何实现？

怎么区分rcu stall和死锁？

最新资源

为什么要引入读 - 复制 - 更新锁？它对读者和写者分别有何影响？