处理器如何实现原子操作
[TOC]
背景
临界区：每个进程中访问临界资源的那段程序称为临界区（临界资源是一次仅允许一个进程使用的共享资源）。每次只准许一个进程进入临界区，进入后不允许其他进程进入。
进程进入临界区的调度原则： ①如果有若干进程要求进入空闲的临界区，一次仅允许一个进程进入。 ②任何时候，处于临界区内的进程不可多于一个。如已有进程进入自己的临界区，则其它所有试图进入临界区的进程必须等待。 ③进入临界区的进程要在有限时间内退出，以便其它进程能及时进入自己的临界区。 ④如果进程不能进入自己的临界区，则应让出CPU，避免进程出现“忙等”现象。
锁主要保护的是临界资源，我们可以用一个状态位（bit）的状态来表示临界区是否空闲（,1：空闲；0：繁忙），当进程1读取到状态位的状态为1（空闲时），将此状态位状态设置为0（繁忙），并进入临界区处理临界资源，处理完后，将此状态位状态设置为1（空闲）。若在程序1进入临界区后，进程2也想进入临界区将要先判断状态位的状态，因为进程1在进入临界区前已经将状态位的值设置为0（繁忙），所以进程2就不能进入临界区，而是要等待。 有上可知，实现锁的前提是对状态位状态的读取设置操作是原子的，即进程1没有完成对状态位的读取-判断-设置这一系列操作之前，进程2不能对状态位的状态进行读取。
由处理器如何实现原子操作.这篇文章，可以知道操作系统有保证操作的原子性的机制（总线锁lock机制）。既然这样就可以实现原子性操作，比如对某个位进行读取设置的原子性操作。在c++中，提供了atomic原子库，提供了对一些常用数据类型进行原子操作的接口。
自旋锁
自旋锁是一种busy-waiting的锁，即进程如果申请不到锁，会一直不断地循环检查锁（状态位）是否可用（会消耗cpu时间），直到获取到这个锁为止。 优点：不会使进程状态发生切换，即进程一直处于active状态，不会进入阻塞状态，获得锁后，不用进行上下文切换，执行速度快。 缺点：没有获得锁前，会一直消耗cpu时间。
上下文切换：（也叫进程切换、任务切换）从正在运行的的进程中收回处理器，即把进程存放在处理器中的中间数据找个地方存起来。
C++实现自旋锁
c++标准库没有提供自旋锁，可以利用atomic_flag实现。 std::atomic_flag是一个原子的布尔类型，可支持两种原子操作： 1.test_and_set： 如果atomic_flag对象被设置，则返回true; 如果atomic_flag对象未被设置，则设置之，返回false 2.clear： 清楚atomic_flag对象
使用自旋锁代码
#include <thread>
#include <atomic>
#include <iostream>
#include <cstdio>
using namespace std;
class spin_lock {
private:
atomic_flag flag;
public:
spin_lock() = default;
spin_lock(const spin_lock&) = delete;
spin_lock& operator=(const spin_lock) = delete;
void lock() { //acquire spin lock
while (flag.test_and_set());
}
void unlock() { //release spin lock
flag.clear();
}
};
spin_lock splock;
long total = 0;
static const int numthread = 50;
// 点击函数
void click()
{
splock.lock();
for(int i=0; i<1000000;++i)
{
// 对全局数据进行加锁访问
total += 1;
}
splock.unlock();
}
int main()
{
// 计时开始
clock_t start = clock();
// 创建100个线程模拟点击统计
std::thread mythread[numthread];
for (int i = 0; i < numthread;i++)
{
mythread[i] = std::thread(click);
}
for (int i = 0; i < numthread; i++)
{
mythread[i].join();
}
// 计时结束
clock_t finish = clock();
// 输出结果
cout<<"result:"<<total<<endl;
cout<<"duration:"<<finish -start<<"ms"<<endl;
return 0;
}运行结果如下，没有出错
不使用自旋锁代码
下面是不使用自旋锁的代码
结果如下，运行比加锁后时间少，但出错：
注：如何把锁加在for循环里，运行非常久，原因未知，代码如下
C实现自旋锁
linux内核有定义自旋锁的接口，定义在<linux/include/linux/spinlock.h>，但是没有系统调用自旋锁的入口（ syscall() 执行一个系统调用，include/linux/syscalls.h文件中定义有所用系统调用函数的原型），在include/linux/syscalls.h没有找到有自旋锁的相关接口。所以在用c编写应用程序时，不能直接调用此函数。
linux自旋锁实现
链接: linux kernel源码镜像地址.
自旋锁的基本使用形式有两种：
或
spinlock_t的定义在<linux/include/linux/spinlock_types.h>
spin_lock()的定义在linux/include/linux/spinlock.h
由上述通用代码追溯没有看到具体的实现，目前也不知道如何与不同平台架构的具体实现相关联。下面将分析内核代码中针对 ARM 平台arch_spin_lock的实现代码。
ARM32 平台arch_spin_lock
路径： linux/arch/arm/include/asm/spinlock.h； linux/arch/arm/include/asm/spinlock_types.h；
由上可知其实关键是指令ldrex和strex，他们保证了对某块内存进行读写的原子操作。
x86_64 平台arch_spin_lock
在linux 的main主线源码的/linux/arch/x86_64没看到有相关源码文件，不知x86平台spin lock的实现原理。
互斥锁
互斥锁：用于保护临界区，确保同一时间只有一个线程访问数据。对共享资源的访问，先对互斥量进行加锁，如果互斥量已经上锁，调用线程会阻塞，直到互斥量被解锁。在完成了对共享资源的访问后，要对互斥量进行解锁。 相比自旋锁，互斥锁会在等待期间放弃cpu。
c++中互斥锁的使用
编译命令g++ mutex_lock.cpp -lpthread
结果如下
不使用互斥锁结果如下，出错
可以看出c++使用互斥锁，比使用自旋锁或不使用锁，耗时少。
c中互斥锁的使用
编译命令cc xxx.c -lpthread
结果如下
不使用互斥锁时，结果如下，可以看出使用互斥锁后程序耗时更少。
pthread_mutex_lock的实现原理
在Linux下，信号量和线程互斥锁的实现都是通过futex系统调用实现。 Futex 是一个提升效率的机制。在Unix系统中，传统的进程间同步机制都是通过对内核对象操作来完成的，这个内核对象在需要同步的进程中都是可见的，进程间的同步是通过系统调用在内核中完成。这种同步方式因为涉及用户态和内核态的切换，效率比较低。而且只要使用了传统的同步机制，进入临界区时即使没有其他的进程竞争也必须切换到内核态来检查内核同步对象的状态，这种不必要的切换显然带来了大量的浪费。 Futex就是为了解决这个问题而诞生的。Futex是一种用户态和内核态混合的同步机制，使用Futex同步机制，如果用于进程间同步，需要先创建一块共享内存，Futex变量就位于共享区。同时对Futex变量的操作必须是原子的，当进程试图进入临界区或者退出临界区的时候，首先检查共享内存中的Futex变量，如果没有其他的进程也申请使用临界区，则只修改Futex变量而不再执行系统调用。如果同时有其他进程在申请使用临界区，还是需要通过系统调用去执行等待或唤醒操作。这样通过用户态的Futex变量的控制，减少了进程在用户态和内核态之间切换的次数，从而减少了系统同步的开销。
pthread_mutex_lock的原理如下
在用户空间的共享变量其实在使用mutex时定义的，pthread_mutex_t类型的变量里。 futex源码在/linux/kernel/futex.c中，主要是futex_wait和futex_wake两个函数
futex_wait
在将进程阻塞前会将当期进程插入到一个全局唯一的等待队列中。 着重看futex_wait_setup
函数futex_wait_setup中主要做了两件事，一是获得自旋锁，二是判断*uaddr是否为预期值。
futex_wait流程：
futex_wake
futex_wake流程如下：
Last updated
Was this helpful?