线程 同步 锁 阻塞 和 死循环 (spin 自旋) 网络摘抄笔

Linux 环境中，实现线程同步的常用方法有 4 种，分别称为互斥锁、信号量、条件变量和读写锁。

java 的同步相关方法
Thread.sleep();
Thread.yield();
Object.wait();
condition.await();
Thread.stop();

/* caller must lock mutex */
pthread_cond_wait(cond, mutex)
{
    lock(cond->__data.__lock);
    unlock(mutex);
    do {
       unlock(cond->__data.__lock);
       futex_wait(cond->__data.__futex);
       lock(cond->__data.__lock);
    } while(...)
    unlock(cond->__data.__lock);
    lock(mutex);
}

pthread_cond_broadcast(cond)
{
    lock(cond->__data.__lock);
    unlock(cond->__data.__lock);
    futex_requeue(cond->data.__futex, cond->mutex);
}

锁是内核中使用最频繁，最基础的设施之一，在内核的各个模块中被大量使用。锁的本质是在并发过程中保证资源的互斥使用。Linux内核提供了多种锁，应用的场合也各不相同，主要包括：原子操作，信号量，读写锁，自旋锁，以及RCU锁机制等。

RCU是比读写锁更高效，并且同时支持多个读者和多个写者并发的机制，其实现非常复杂，涉及到软中断，completion机制等，将不再本篇分析，另起一篇RCU机制和实现。

原子操作（atomic）： https://zhuanlan.zhihu.com/p/333675803

简单来说，自旋锁和读写锁的核心都是利用原子指令来 CAS 操纵一个 32 位/64 位的值，它们都不允许睡眠，但是读写锁对于读者做了优化，允许多个读者同时读取数据，而自旋锁则对于读写操作没有什么偏向性。seq 基于自旋锁实现，不允许睡眠，但是对写者更为友好。mutex 和 semaphore 也是基于自旋锁实现的，但是它们允许互斥区的操作陷入睡眠。

可以看到，加锁这种方式，最核心的还是利用指令实现原子操作。

总结
总结一下：

16 字节或 8 字节以内的内存数据，使用 cpu 的原子操作指令；
16 字节以上的数据，使用加锁、COW 的方式，或者优化过的使用 seq 的 COW 方式，本质上还是依赖于原子指令；
针对多个对象的原子操作，引入事务或者事务内存的概念，实际上的实现要么是写日志，要么是依赖于 COW 或加锁的方式，最终依赖于原子指令。
所以，万变不离其宗，原子操作指令很关键。

feng:原子操作是实现其他各种锁的基础。考虑如下代码语句：

i++;

编译器在编译的过程中，该语句有可能被编译成如下三条CPU指令：

1. 加载内存变量i的值到寄存器

2. 寄存器值+1

3. 将寄存器值写回内存

我们知道，一条指令在单CPU上对内存的访问是原子的（因为中断只能是在当前指令执行完之后才去检查处理），但多条指令之间并不是原子的，单条指令在多处理器系统上也不是原子的。因此，上面i++语句虽然在代码编写上是一条语句，但在二进制可执行指令上却是三条指令，如果在两个并发的例程中对同一个i变量同时执行i++操作，必然会导致数据错乱。因此，每种CPU架构都应该提供一套指令，用于锁定/解锁内存总线，使得在锁定区内执行的指令是一个原子操作。

以x86架构为例，提供了lock;前缀指令，用于在指令执行前先锁定特定内存，保证对特定内存的互斥访问。以atomic_add()实现为例：

D:\linux-5.6.3内核源码win解压有点小丢失弄到vbox1了\linux-2.6.34-rc2\arch\x86\include\asm\atomic.h
static inline int atomic_sub_and_test(int i, atomic_t *v)
{
    unsigned char c;

    asm volatile(LOCK_PREFIX "subl %2,%0; sete %1"
             : "+m" (v->counter), "=qm" (c)
             : "ir" (i) : "memory");
    return c;
}

static inline void atomic_add(int i, atomic_t *v)
{
    asm volatile(LOCK_PREFIX "addl %1,%0"
             : "+m" (v->counter)
             : "ir" (i));
}

在CPU的LOCK信号被声明之后，在此期随同执行的指令会转换成原子指令。在多处理器环境中，LOCK信号确保，在此信号被声明之后，处理器独占使用任何共享内存。

在不大多数IA-32和Inter64位处理器中，锁可能在没有LOCK#信号的时情况下发生。请参阅下面的“IA32体系结构兼容性”部分的详细内容。

LOCK前缀只能预加在以下指令前面，并且只能加在这些形式的指令前面,其中目标操作数是内存操作数：add、adc、and、btc、btr、bts、cmpxchg、cmpxch8b，cmpxchg16b，dec，inc，neg，not，or，sbb，sub，xor，xadd和xchg。

如果LOCK前缀用上述列表中的指令并且源操作数是内存操作数(也就是指令没有对内存进行写操作)，可能会出现未定义的操作码异常（ud）。

如果锁前缀与任何不在上面列表中的指令一起使用，也将生成未定义的操作码异常。

xchg指令不管有没有声明LOCK前缀，总是会声明LOCK信号。

锁定前缀通常与BTS指令一起使用，在共享内存环境中，以对内存地址执行读-修改-写操作。

锁定前缀的完整性不受内存字段对齐的影响。对于任意未对齐的字段，可以观察到内存锁定。

此指令的操作在非64位模式和64位模式下是相同的。

从P6系列处理器开始，当使用 LOCK 指令访问的内存已经被处理器加载到缓存中时，LOCK# 信号通常不会断言。取而代之的是，只锁定处理器的缓存。在这里处理器的缓存一致性机制确保对内存进行的操作是原子性的。请参见“锁定操作对内部处理器缓存的影响”，在Intel®64和IA-32体系结构软件开发人员手册第3A卷第8章中，有关锁定缓存的详细信息。

https://www.cnblogs.com/yungyu16/p/13200626.html
lock 把其他cpu的执行都锁住了..其他cpu核都停止了. 只有一个cpu核操作该内存. 完了后其他cpu核开始执行. 保证了原子性

image.png

lock 锁总线，其它CPU对内存的读写请求都会被阻塞，直到锁释放，

image.png

2.1、忙等待的互斥(自旋等待)
所谓忙等待，指的是线程自己一直在循环判断是否可以获取到锁了，这种循环也成为自旋。下面我们通过屏蔽中断和锁变量的介绍，依次引出忙等待的相关互斥手段方法。
至于自旋呢，看字面意思也很明白，自己旋转，翻译成人话就是循环，一般是用一个无限循环实现

image.png

我们可以通过Inter处理器提供了很多LOCK前缀的指令来实现。比如位测试和修改指令BTS，BTR，BTC，交换指令XADD，CMPXCHG和其他一些操作数和逻辑指令，比如ADD（加），OR（或）等，被这些指令操作的内存区域就会加锁，导致其他处理器不能同时访问它。

JVM中的CAS操作正是利用了上一节中提到的处理器提供的CMPXCHG指令实现的。自旋CAS实现的基本思路就是循环进行CAS操作直到成功为止，以下代码实现了一个基于CAS线程安全的计数器方法safeCount和一个非线程安全的计数器count。

锁机制保证了只有获得锁的线程能够操作锁定的内存区域。JVM内部实现了很多种锁机制，有偏向锁，轻量级锁和互斥锁，有意思的是除了偏向锁，JVM实现锁的方式都用到的循环CAS，当一个线程想进入同步块的时候使用循环CAS的方式来获取锁，当它退出同步块的时候使用循环CAS释放锁。详细说明可以参见文章Java SE1.6中的Synchronized。

x86/64 cpu支持很多原子指令，我们只需要直接应用这些指令，比如原子加、原子减，原子读写等，用汇编代码写出对应的原子操作函数就行了。现代 C 语言已经支持嵌入汇编代码，可以在 C 函数中按照特定的方式嵌入汇编代码了，实现原子操作就更方便了
https://blog.csdn.net/xystrive/article/details/120909335

https://blog.csdn.net/xystrive/article/details/120909335

//自旋锁结构
typedef struct
{
     volatile u32_t lock;//volatile可以防止编译器优化，保证其它代码始终从内存加载lock变量的值 
} spinlock_t;
//锁初始化函数
static inline void x86_spin_lock_init(spinlock_t * lock)
{
     lock->lock = 0;//锁值初始化为0是未加锁状态
}
//加锁函数
static inline void x86_spin_lock(spinlock_t * lock)
{
    __asm__ __volatile__ (
    "1: \n"
    "lock; xchg  %0, %1 \n"//把值为1的寄存器和lock内存中的值进行交换
    "cmpl   $0, %0 \n" //用0和交换回来的值进行比较
    "jnz    2f \n"  //不等于0则跳转后面2标号处运行
    "jmp 3f \n"     //若等于0则跳转后面3标号处返回
    "2:         \n" 
    "cmpl   $0, %1  \n"//用0和lock内存中的值进行比较
    "jne    2b      \n"//若不等于0则跳转到前面2标号处运行继续比较  
    "jmp    1b      \n"//若等于0则跳转到前面1标号处运行，交换并加锁
    "3:  \n"     :
    : "r"(1), "m"(*lock));
}
//解锁函数
static inline void x86_spin_unlock(spinlock_t * lock)
{
    __asm__ __volatile__(
    "movl   $0, %0\n"//解锁把lock内存中的值设为0就行
    :
    : "m"(*lock));
}

重点回顾
原子变量，在只有单个变量全局数据的情况下，这种变量非常实用，如全局计数器、状态标志变量等。我们利用了 CPU 的原子指令实现了一组操作原子变量的函数。
中断的控制。当要操作的数据很多的情况下，用原子变量就不适合了。但是我们发现在单核心的 CPU，同一时刻只有一个代码执行流，除了响应中断导致代码执行流切换，不会有其它条件会干扰全局数据的操作，所以我们只要在操作全局数据时关闭或者开启中断就行了，为此我们开发了控制中断的函数。
自旋锁。由于多核心的 CPU 出现，控制中断已经失效了，因为系统中同时有多个代码执行流，为了解决这个问题，我们开发了自旋锁，自旋锁要么一下子获取锁，要么循环等待最终获取锁。
信号量。如果长时间等待后才能获取数据，在这样的情况下，前面中断控制和自旋锁都不能很好地解决，于是我们开发了信号量。信号量由一套数据结构和函数组成，它能使获取数据的代码执行流进入睡眠，然后在相关条件满足时被唤醒，这样就能让 CPU 能有时间处理其它任务。所以信号量同时解决了三个问题：等待、互斥、唤醒。
————————————————
版权声明：本文为CSDN博主「一顿吃不饱」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/m0_48958478/article/details/121308373

涉及到信号量的改变，为了防止放置进程的切换使得信号量的值被搞乱了，需要设置临界区来保护信号量:
不采用软件保护法(比如：轮换法\标记法\ peterson算法\ Lamport面包店算法)，
采用硬件保护法，
由于是linux0.11运行在单cpu上(Bochs虚拟机提供单cpu环境)，所以可以采用简单的开关中断的方法，
如果是多cpu环境，就使用硬件原子指令保护法(用硬件原子指令操控一个mutex信号量来保护临界区)
————————————————
版权声明：本文为CSDN博主「garbage_man」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_42518941/article/details/119757885

多线程编程之数据访问互斥

在多线程存在的环境中，除了堆栈中的临时数据之外，所有的数据都是共享的。如果我们需要线程之间正确地运行，那么务必需要保证公共数据的执行和计算是正确的。简单一点说，就是保证数据在执行的时候必须是互斥的。否则，如果两个或者多个线程在同一时刻对数据进行了操作，那么后果是不可想象的。

保证多线程之间的数据访问互斥，有以下四类方法：

（1）关中断 (cli sti 汇编cpu指令)

（2）数学互斥方法

（3）操作系统提供的互斥方法

（4）CPU原子操作

进程同步
引言
如何鉴别分时操作系统引起的问题
几种解决上述问题的方案：
概念补充
解决临界区问题应该满足的条件
1.Peterson方法
2.硬件同步
版本1：关中断
版本2.1：test_and_set指令
版本2.2 swap指令
硬件指令小结
3.信号量（由Dijkstra提出）
小结
————————————————
版权声明：本文为CSDN博主「鹏鹏~」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_36321889/article/details/91347869

内联 汇编模板，用双引号包含起来，每条指令都需要使用系统汇编代码中的分隔符进行分隔，如分号" ; "或" \n\t "等, 在大多数地方都可以使用的组合是换行符和制表符(写为" \n\t ")。 有些汇编程序允许分号(;)作为行分隔符。(linux内核中的atomic_sub_and_test 就用到了分号)但是，请注意，一些汇编语言使用分号来表示注释的开始。

阻塞 和 死循环
一般我们在线程里的代码会这样写：

while(!Terminated)
{
if (WaitForSingleObject(m_SomeEvent, INFINITE) == WAIT_OBJECT_0)
{
//Do something
}
}
这里的外层循环只是为了保证线程不会结束，而当m_SomeEvent的状态为假时，代码到WaitFor这里就会挂起，不会向下执行。这就是所谓的“阻塞”。

而如果这么写：
while(!Terminated)
{
if (m_SomeCondition == true)
{
//Do something
}
}

这样的话，程序就会不停循环，只是每次因为条件不符而不执行Do something而已，这就是死循环（当然可以设置条件跳出了）。

阻塞 里面循环等待信号量。信号量可以是接收到消息，也可以是某个标志位。

“函数阻塞”是什么意思？

阻塞应该是线程中的概念，就是利用WaitFor函数族（WaitForSingleObject之类），根据Event状态来使线程挂起，或者是用Sleep函数让线程挂起一段时间。

作者：张砸锅
链接：https://www.zhihu.com/question/391359472/answer/1187969709
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

阻塞本质上是资源调度过程中出现的一种现象。为了完成某个任务，需要在某个时间使用某个资源，但是却发现该资源却不可用，我们说，此时该任务被该资源阻塞了。对待阻塞有两种处理模式，分别是同步方式和异步方式。同步方式下，感觉上可能像无限循环，但通常并不是。异步方式下，有没有无限循环，就看你代码写成啥样了。我们用个具体例子来说明，假设我们的任务是从网络上读取一段数据，如果此时数据尚未从对端传输过来，就不可能读到，因此我们说，此时读操作被网络阻塞了。如果用同步方式处理这个阻塞，那么对于这段程序来说，就是死等，直到数据被传输过来，然后程序读到数据，继续执行下去。站在这段程序的角度，感觉上像是进入了一个无限循环，循环里在不停的检查网络上是不是有数据，一旦有就读出数据，然后继续处理。真实情况是不是这样呢？如果是早期的单任务操作系统或者协作式多任务操作系统，比如以前的 DOS、Windows 3.x 等，确实如此；但对于 Unix、Windows 95 及之后的抢占式多任务操作系统，实际上并非如此。（注：协作式多任务也可以不死等，具体要看内部实现，不细说了。）对于抢占式多任务操作系统来说，当一个任务被阻塞时，该任务所在的进程或线程会被暂停运行，将进程或线程状态保存下来，转去执行其他未被阻塞的其他任务。当阻塞条件解除后，该进程或线程会得到重新调度，得以继续执行。也就是说，站在这段程序来说，感觉上好像在死等，但站在操作系统的角度上，并没在死等该程序的执行，该程序已经被暂停挂起了，并没在执行。刚才提到，阻塞还有一种异步处理方式，细分下来也有多种处理方式。程序不是直接去读网络，而是先询问网络是否可读，可读就去读，不可读就先做别的事，做完后再来检查网络是否可读，如此循环。程序注册一个回调例程，然后去做别的事。当网络可读时回调例程被自动调用。程序使用多路复用技术，同时要管理多个网络读写，哪个可读就读哪个。所以，有没有无限循环，就看你代码写成啥样了。以上。希望对题主有所帮助。

https://www.cnblogs.com/crybaby/p/13090707.html

<meta charset="utf-8">

Mutual exclusion（或者锁）的实现有硬件实现和软件实现，软件实现是通过一些特别的算法譬如https://en.wikipedia.org/wiki/Peterson%27s_algorithm，这类软件实现通常比硬件实现需要更多的内存，而且由于现代计算机的乱序执行，需要手动加memory barrier来保证memory ordering，这里暂时不做讨论纯软件实现。CPU如果提供一些用来构建锁的atomic指令，一般会更高效一些。

锁的本质

所谓的锁，在计算机里本质上就是一块内存空间。当这个空间被赋值为1的时候表示加锁了，被赋值为0的时候表示解锁了，仅此而已。多个线程抢一个锁，就是抢着要把这块内存赋值为1。在一个多核环境里，内存空间是共享的。每个核上各跑一个线程，那如何保证一次只有一个线程成功抢到锁呢？你或许已经猜到了，这必须要硬件的某种guarantee。具体的实现如下。

作者：陈清扬
链接：https://www.zhihu.com/question/332113890/answer/1052024052
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

https://blog.csdn.net/zhangxinrun/article/details/5843393 巧妙使用lock 前缀加到
nop的异常....

原来如此，赶紧搜索一个L4的异常处理程序，果然看到了下面代码段：

case 0xf0: /* lock prefix */
     if (space->get_from_user(addr_offset(addr, 1)) == 0x90)
     {
          /* lock; nop */
          frame->eax = (u32_t)space->get_kip_page_area().get_base();
          frame->ecx = get_kip()->api_version;
          frame->edx = get_kip()->api_flags;
          frame->esi = get_kip()->get_kernel_descriptor()->kernel_id.get_raw();
          frame->eip+= 2;
          return;
      }