请选择 进入手机版 | 继续访问电脑版
[X]关闭

Linux内核进程管理并发同步与原子操作

文档创建者:东吴
浏览次数:508
最后更新:2024-08-07
本帖最后由 东吴 于 2024-8-7 10:39 编辑

一、并发同步
   并发是指在某一时间段内能够处理多个任务的能力,而 并行 是指同一时间能够处理多个任务的能力。并发和并行看起来很像,但实际上是有区别的,如下图(图片来源于网络):
image.jpg
   上图的意思是,有两条在排队买咖啡的队列,并且只有一架咖啡机在处理,而并行就有两架的咖啡机在处理。咖啡机的数量越多,并行能力就越强。可以把上面的两条队列看成两个进程,并发就是指只有单个CPU在处理,而并行就有两个CPU在处理。为了让两个进程在单核CPU中也能得到执行,一般的做法就是让每个进程交替执行一段时间,比如让每个进程固定执行100毫秒 ,执行时间使用完后切换到其他进程执行。而并行就没有这种问题,因为有两个CPU,所以两个进程可以同时执行。如下图:
image.jpg
image.jpg

   上面介绍过,并发有可能会打断当前执行的进程,然后替切换成其他进程执行。如果有两个进程同时对一个共享变量 count 进行加一操作,由于C语言的 count++ 操作会被翻译成如下指令:
1.mov eax, [count]
2.inc eax
3.mov [count], eax
那么在并发的情况下,有可能出现如下问题:
image.jpg
假设count变量初始值为0:
(1)进程1执行完 mov eax, [count] 后,寄存器eax内保存了count的值0。
(2)进程2被调度执行。进程2执行 count++ 的所有指令,将累加后的count值1写回到内存。
(3)进程1再次被调度执行,计算count的累加值仍为1,写回到内存。

   虽然进程1和进程2执行了两次 count++ 操作,但是count最后的值为1,而不是2。要解决这个问题就需要使用 原子操作 ,原子操作是指不能被打断的操作,在单核CPU中,一条指令就是原子操作。比如上面的问题可以把 count++ 语句翻译成指令 inc [count] 即可。Linux也提供了这样的原子操作,如对整数加一操作的 atomic_inc() :


1.static __inline__ void atomic_inc(atomic_t *v)
2.{
3.__asm__ __volatile__(
4.LOCK "incl %0"
5.:"=m" (v->counter)
6.:"m" (v->counter));
7.}


在多核CPU中,一条指令也不一定是原子操作,比如 inc [count] 指令在多核CPU中需要进行如下过程:
(1)从内存将count的数据读取到cpu。
(2)累加读取的值。
(3)将修改的值写回count内存。
Intel x86 CPU 提供了 lock 前缀来锁住总线,可以让指令保证不被其他CPU中断,如下:
1.lock
2.inc [count]


二、锁
1、原子操作、自旋锁、信号量、互斥锁以及RCU的特点和使用规则。
   原子操作:原子操作是指在执行过程中不会被中断的操作。它是在多线程环境下保证数据的一致性和线程安全的一种机制。原子操作通常是不可分割的,要么完全执行,要么完全不执行。在并发编程中,原子操作可以用来保护共享资源,避免多个线程同时访问和修改同一数据导致的竞态条件。
   自旋锁:自旋锁是一种基本的锁机制,它采用忙等待的方式来实现线程的互斥。当一个线程尝试获取自旋锁时,如果锁已经被其他线程占用,那么该线程会一直循环等待,直到获取到锁为止。自旋锁适用于锁的持有时间很短,且线程竞争不激烈的情况下,可以避免线程切换的开销。
   信号量:信号量是一种用于控制对共享资源的访问的同步机制。它可以用来限制同时访问某个资源的线程数量。信号量维护一个计数器,线程在访问资源之前需要申请信号量,如果信号量计数器大于0,则线程可以继续执行;如果计数器为0,则线程需要等待其他线程释放信号量。信号量适用于线程竞争激烈的情况下,可以控制并发访问的数量。
   互斥锁:互斥锁是一种常用的线程同步机制,用于保护共享资源的访问。互斥锁在同一时刻只允许一个线程访问被保护的资源,其他线程需要等待锁的释放。互斥锁可以防止多个线程同时访问共享资源,从而避免数据的不一致性和竞态条件的发生。
   RCU(Read-Copy-Update):RCU是一种用于实现读写并发的机制。它通过在更新数据时创建副本,而不是直接修改原始数据,来实现读操作的无锁化。当有读操作时,RCU可以保证读取到的是一个稳定的数据副本,而不会受到更新操作的影响。RCU适用于读操作频繁、写操作相对较少的场景,可以提高并发性能。
   以上是对原子操作、自旋锁、信号量、互斥锁和RCU的特点和使用规则的简要介绍。具体使用时需要根据具体的编程语言和场景进行选择和配置。
   下面介绍一下自旋锁和信号量的实现。


2、自旋锁
自旋锁只能在多核CPU系统中,其核心原理是 原子操作 ,原理如下图:

image.jpg

使用自旋锁时,必须先对自旋锁进行初始化(设置为1),上锁过程如下:
(1)对自旋锁 lock 进行减一操作,判断结果是否等于0,如果是表示上锁成功并返回。
(2)如果不等于0,表示其他进程已经上锁,此时必须不断比较自旋锁 lock 的值是否等于1(表示已经解锁)。
(3)如果自旋锁 lock 等于1,跳转到第一步继续进行上锁操作。
由于Linux的自旋锁使用汇编实现,所以比较苦涩难懂,这里使用C语言来模拟一下:


1.void spin_lock(amtoic_t *lock)
2.{
3.again:
4.result = --(*lock);
5.if (result == 0) {
6.return;
7.}
8.while (true) {
9.if (*lock == 1) {
10.goto again;
11.}
12.}
13.}


   上面代码将 result = --(*lock); 当成原子操作,解锁过程只需要把 lock 设置为1即可。由于自旋锁会不断尝试上锁操作,并不会对进程进行调度,所以在单核CPU中可能会导致 100% 的CPU占用率。另外,自选锁只适合粒度比较小的操作,如果操作粒度比较大,就需要使用信号量这种可调度进程的锁。


3、信号量
   与自旋锁不一样,当前进程对 信号量 进行上锁时,如果其他进程已经对其进行上锁,那么当前进程会进入睡眠状态,等待其他人对信号量进行解锁。过程如下图:
image.jpg

在Linux内核中,信号量使用 struct semaphore 表示,定义如下:
1.struct semaphore {
2.raw_spinlock_t lock;
3.unsigned int count;
4.struct list_head wait_list;
5.};
各个字段的作用如下:
(1)lock :自旋锁,用于对多核CPU平台进行同步。
(2)count :信号量的计数器,上锁时对其进行减一操作(count--),如果得到的结果为大于等于0,表示成功上锁,如果小于0表示已经被其他进程上锁。
(3)wait_list :正在等待信号量解锁的进程队列。


信号量上锁通过 down() 函数实现,代码如下:
1.void down(struct semaphore *sem)
2.{
3.unsigned long flags;
4.spin_lock_irqsave(&sem->lock, flags);
5.if (likely(sem->count > 0))
6.sem->count--;
7.else
8.__down(sem);
9.spin_unlock_irqrestore(&sem->lock, flags);
10.}
   上面代码可以看出,down() 函数首先对信号量进行自旋锁操作(为了避免多核CPU竞争),然后比较计数器是否大于0,如果是对计数器进行减一操作,并且返回,否则调用 __down() 函数进行下一步操作。
__down() 函数实现如下:
1.static noinline void __sched __down(struct semaphore *sem)
2.{
3.__down_common(sem, TASK_UNINTERRUPTIBLE, MAX_SCHEDULE_TIMEOUT);
4.}
5.static inline int __down_common(struct semaphore *sem,
6.long state, long timeout)
7.{
8.struct task_struct *task = current;
9.struct semaphore_waiter waiter;
10.// 把当前进程添加到等待队列中
11.list_add_tail(&waiter.list, &sem->wait_list);
12.waiter.task = task;
13.waiter.up = 0;
14.for (;;) {
...
15.__set_task_state(task, state);
16.spin_unlock_irq(&sem->lock);
17.timeout = schedule_timeout(timeout);
18.spin_lock_irq(&sem->lock);
19.if (waiter.up) // 当前进程是否获得信号量锁?
20.return 0;
21.}
...
22.}
__down() 函数最终调用 __down_common() 函数,而 __down_common() 函数的操作过程如下:
(1)把当前进程添加到信号量的等待队列中。
(2)切换到其他进程运行,直到被其他进程唤醒。
(3)如果当前进程获得信号量锁(由解锁进程传递),那么函数返回。


接下来看看解锁过程,解锁过程主要通过 up() 函数实现,代码如下:
1.void up(struct semaphore *sem)
2.{
3.unsigned long flags;
4.raw_spin_lock_irqsave(&sem->lock, flags);
5.if (likely(list_empty(&sem->wait_list))) // 如果没有等待的进程, 直接对计数器加一操作
6.sem->count++;
7.else
8.__up(sem); // 如果有等待进程, 那么调用 __up() 函数进行唤醒
9.raw_spin_unlock_irqrestore(&sem->lock, flags);
10.}
11.static noinline void __sched __up(struct semaphore *sem)
12.{
13.// 获取到等待队列的第一个进程
14.struct semaphore_waiter *waiter = list_first_entry(
15.&sem->wait_list, struct semaphore_waiter, list);
16.list_del(&waiter->list); // 把进程从等待队列中删除
17.waiter->up = 1; // 告诉进程已经获得信号量锁
18.wake_up_process(waiter->task); // 唤醒进程
19.}


解锁过程如下:
(1)判断当前信号量是否有等待的进程,如果没有等待的进程, 直接对计数器加以操作
(2)如果有等待的进程,那么获取到等待队列的第一个进程。
(3)把进程从等待队列中删除。
(4)告诉进程已经获得信号量锁
(5)唤醒进程

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则