操作系统笔记-5-进程&线程同步

引言

前一篇介绍了进程和线程调度，知道线程和进程在系统中是并发执行，这将会引发出一些问题。接下来从一个简单的生产者和消费者例子说起，从前有两个进程，一个进程负责往一个buffer里写数据，我们把它叫做生产者；一个进程负责消费数据也就是取走buffer里的数据，我们把它叫做消费者。因为我们要记录写到哪里，所以需要一个变量in来记录，还需要一个变量记录消费到哪里了out，现在我们假设核心的生产者代码段。

while (true) {
    while (count == BUFFER SIZE)
    ; /* 忙等待，等到buffer有空间写入 */
    buffer[in] = next produced;
    in = (in + 1) % BUFFER SIZE; //构建一个环形数组
    count++;
}

消费者核心代码

while (true) {
    while (count == 0)
    ; /* 忙等待,等到buffer有数据消费 */
    next consumed = buffer[out];
    out = (out + 1) % BUFFER SIZE;
    count--;
}

如果并发执行这个代码，肯定会有问题？因为cpu在修改count时，要先将count读入寄存器，然后在写入内存。假设count此时为4，生产者和消费者分别并发写入和消费，count的结果可能会为3、4、5，如果生产者和消费者分别将4读入寄存器，那么count的值将取决于谁后写回内存覆盖之前的值，所以值可能为3、5，这个结果显然是有问题的。将接下来将学习解决之道。

竞态条件&临界区

在学习进程&线程同步之前得先理解竞态条件和临界区的概念。

竞态条件

多个进程或线程并发访问或操作同一数据，其运行结果依赖于其访问发生的特定顺序

临界区

• 定义：对共享内存访问的程序片段被称为临界区，就像引言例子中外层while循环中的代码片段

• 临界区互斥性示意图

  

解决竞态条件方法满足的条件

• 互斥性，任何两个进程不能同时处于临界区
• 不应对CPU的速度和数量做任何假设
• 临界区外的进程不能阻塞其他进程
• 不得使进程无限期的等待进入临界区

简单解决办法

• 屏蔽中断

  • 实现：在进入临界区后立即屏蔽中断，在快要离开时开启中断。
  • 缺点
    1. 把屏蔽中断的权利交给用户进程是不明智的
    2. 如果是多CPU，只会屏蔽当前CPU有效

• Peterson解法

  • 实现

    #define FALSE 0
    #define TRUE 1
    #define N 2 /* 进程数 */
    
    int turn; /* whose turn is it? */
    int interested[N]; /* 哪个进程对条件感兴趣，初始化为0 */
    
    void enter region(int process); /* 因为只有两个进程，所以process为0或者1 */
    {
        int other; /* 另一个进程编号 */
        other = 1 −process; /* 另一个进程编号 */
        interested[process] = TRUE; /* 表示当前进程对该条件感兴趣 */
        turn =process; /* 设值，注意这里哪个进程后设置，该值为它的进程编号 */
        while (turn == process && interested[other] == TRUE) /* 空语句 */ ;
    }
    void leave region(int process) /* 进程离开临界区 */
    {
        interested[process] = FALSE; /* 将进程对条件感兴趣的标志设置为false */
    }

    while判断分析：如果turn的值为当前进程号，并且interested[other]为true，说明此时两个进程都对该条件感兴趣，并且另一个进程先来，所以turn的值才会为当前进程的值，它覆盖了另一个进程写入的值，所以另一个进程已经进入临界区，所以当前进程需要等待另一个进程离开临界区。

  • 缺点：为了提高性能，现代处理器或者编译器有指令重排序，可能是导致该算法无法保证有效。虽然Peterson的解法在指令重排序下有问题，但是它却提供了同步解决的基础。

同步工具的硬件支持

在介绍同步工具之前，先讲一下硬件支持，比如内存屏障、CAS。

内存屏障

• 内存模型
  • Strongly ordered：一个处理器对内存的修改立刻对其他处理器可见
  • Weakly ordered：一个处理器的内存的修改不能保证立刻对其他处理器可见
• 原理：硬件提供的指令，通过强制将对内存的修改传播到其他处理器，从而确保其他处理器对内存的修改可见，在之后讲内存管理的时候细说

TSL指令

• 原理：设置存储器某个地址，测试并上锁。

  TSL RX,LOCK

  1. 内存字LOCK读入寄存器RX，读字和写字硬件保证原子的

  2. 执行TSL指令锁住内存总线，禁止其他CPU在该指令结束前访问内存

     enter region:						
     	TSL REGISTER,LOCK				| 复制锁到寄存器并将锁设置为1
     	CMP REGISTER,#0					| 锁是0吗
     	JNE enter region				| 如果锁不是0，说明锁已经被抢了，循环
     	RET 							| 返回，进入临界区
     	
     leave region:
     	MOVE LOCK,#0					| 在锁存入0
     	RET 							| 返回调用者

XCHG指令

• 原理：原子交换两个操作数，是TSL的一种替代指令

  enter region:
  	MOVE REGISTER,#1		| 将1放入寄存器
  	XCHG REGISTER,LOCK		| 交换寄存器和锁的内容
  	CMP REGISTER,#0			| 锁是0吗
  	JNE enter region		| 如果锁不是0，说明锁已经被抢了，循环
  	RET 					| 返回调用者，进入临界区
  
  leave region:
  	MOVE LOCK,#0			| 在锁存入0
  	RET 					| 返回调用者

原子操作CAS(比较并交换)

• 原理：原理接受三个参数(old,ptr,new)，底层是依赖CPMXCHG，注意CPMXCHG本身并不是atomic的，它的实现是在单处理器系统上通过禁止中断来达到原子性，如果是多处理器，则需要在CPMXCHG加前缀LOCK。ptr是该值存储地址，指令会将old加载到寄存器EAX，将ptr的值加载到EBX，将new加载到ECX，如果EAX等于EBX，将ECX存入EBX并且标志寄存器FZ位置为1；否则EBX存入EAX，将FZ位清0

同步工具

原子变量(Atomic)

• 原理：利用CAS实现的

信号量(Semaphore)

• 原理：提供了一对操作wait(Dijkstra的P)、signal(Dijkstra的V)原子操作。内部提供一个计数器和一个等待队列，这个队列可以是FIFO或者优先级队列。wait操作申请锁，初始定义资源数（当资源只有一个时，其实作用是一个互斥量），wait申请资源时，假设资源数还有剩余，那么扣减资源数，进程进入临界区，执行完临界区代码后，递增资源数，并且唤醒一个进程；如果没有资源可用，那么进程加入信号量的等待队列。当然具体细节各个操作系统实现可能不一样

• 如何保证wait、signal的原子性

  1. 单核处理器：禁用中断，禁止抢占
  2. 多核处理器：可以在信号量中定义一个互斥量，通过CAS和自旋来互斥进入wait和signal的临界区

• linux实现，linux实现没有叫wait和signal，它们叫down和up分别对应wait、signal，只是名字不同它们的语义是一样的

   struct semaphore {//数据结构
       spinlock_t lock; 
       unsigned int count; 
       struct list_head wait_list; 
   };
  //Dijkstra的P
  void down(struct semaphore *sem)
  {
      unsigned long flags;
  
      raw_spin_lock_irqsave(&sem->lock, flags); // 这里面禁止了抢占
      if (likely(sem->count > 0))
          sem->count--;
      else
          __down(sem);   // 这里睡眠，重新调度
      raw_spin_unlock_irqrestore(&sem->lock, flags);
  }
  //Dijkstra的V
  void up(struct semaphore *sem)
  {
      unsigned long flags;
  
      spin_lock_irqsave(&sem->lock, flags);
      if (likely(list_empty(&sem->wait_list)))
          sem->count++;
      else
          __up(sem);
      spin_unlock_irqrestore(&sem->lock, flags);
  }

互斥量(mutex)

• 原理：定义一个变量作为锁，利用处理器提供CAS原子修改变量的值来加锁和释放锁，如果锁不可用，进程自旋等待
• futex(快速用户区互斥量)
  • 原理：实现了基本的锁，但是避免了陷入内核，除非不得不为之。包含两部分：一个内核服务和一个用户库，内核服务提供一个等待队列，没有竞争时，futex完全在用户空间工作。用户态定义一个共享原子变量来标识当前锁是否被其他进程持有，初始值为1表示锁可用，当进程申请锁时，先原子递减该值，如果结果为0，说明没有其他进程持有锁，进程可以进入临界区，否则，进程不会自旋，而是调用系统调用加入内核的等待队列

管程(Mointor)

• 信号量存在的问题：信号量能正确运行的前提条件是wait、signal严格的执行顺序，如果这啷个操作执行顺序有问题，那么可能会导致2个进程同时进入临界区

  1. 假设wait、signal顺序反了，可能会有多个进程进入临界区

     signal(mutex);
     ...
     critical section
     ...
     wait(mutex);

  2. 假设signal被错误写成wait，这种情况，进程会永久阻塞

     wait(mutex);
     ...
     critical section
     ...
     wait(mutex);

• Monitor出现的背景只是为了方便开发人员使用，减少直接使用信号量、互斥量容易带来的各种问题（信号量和互斥量本身没有任何问题，是使用过程中开发人员不正确使用带来的），因此对信号量、互斥量做了一层封装

• Monitor语义结构

  monitor monitor name
  {
      /* shared variable declarations */
      function P1 ( . . . ) {
      . . .
      }
      function P2 ( . . . ) {
      . . .
      }
      .
      .
      .
      function Pn ( . . . ) {
      . . .
      }
      initialization code ( . . . ) {
      . . .
      }
  }

• Monitor的结构

  

• Monitor特性

  1. 同一时刻，只能有一个活跃进程。
  2. 只是一种编程语言概念，具体实现依靠特定语言，其内部可能是用互斥量实现
  3. 依靠编译器识别管程，进入管程的互斥依靠编译器

• Monitor中有条件变量时，等待在条件变量的线程Q被线程P唤醒时，P的行为

  1. 唤醒并等待：P将等待Q离开Monitor或者等待在其他条件上
  2. 唤醒并继续：Q将等待P离开Monitor或者等待在其他条件上，这种看起来更合理，但是当P离开Monitor时，可能Q等待的条件已经变得不满足

• 用信号量实现Monitor

  1. 首先需要一个互斥量来控制能否进入Monitor，然后需要一个信号量来控制当线程唤醒等待条件变量的线程时，需要自己挂起，Monitor中的F函数被封装。mutex是进入Monitor的互斥量，next是线程唤醒等待条件变量时，因为采用的是唤醒并等待，所以需要等待被唤醒线程执行，而自己却要挂起，next_count是挂起的线程数

     wait(mutex);
     		...
     	body of F
     		...
     if (next count > 0)
     	signal(next);
     else
     	signal(mutex);

  2. Monitor中条件变量实现,x_sem是信号量，x_count是等待的线程数

     1. wait方法实现

        x count++;
        if (next count > 0)
        	signal(next);
        else
        	signal(mutex);
        wait(x sem);
        x count--;

     2. signal方法实现

        if (x count > 0) {
            next count++;
            signal(x sem);
            wait(next);
            next count--;
        }

屏障(Barrier)

• 原理：屏障像一道大门，当所有人都到了的时候，门就开了。进程运行到一个点时，会阻塞等待所有的进程都到达这个点，当所有进程都达到这个点时，所有的进程都将被唤醒，如下图所示

  

• 解决的问题：主要是解决一些程序，程序是分阶段运行，要求所有的进程到处于ready状态时才能进行下一阶段。打个比方，LOL这种竞技游戏，要等待大家都加载好了才能进游戏。

写时复制(Read-Copy-Update)

• 原理：最快的锁就是不用锁，为了找到一种办法对共享数据读和写可以并发执行，通常情况下是不可能的。但是在某些情况下，一些数据结构可以提供一种对读操作的保证，就是读操作要么读取旧数据，要么读取最新数据，但是不会读取新旧数组的组合。当新增和删除节点时，会先初始化需要操作的节点，这时候是不影响读的，读的还是旧的数据，当更改已经初始化完毕时通过CAS原子操作，修改为新的，这样就可以避免在写数据时加锁影响读

  

• 存在问题：比如上图的d中，删除了B,D节点，但是不知道是否有读在使用B、D节点，因此无法确定何时释放B、D节点。RCU设置了一个读持有引用的最大时间

总结

笔记很多地方没有详细的说明，如果要了解详细的细节东西，推荐看看《MODERN OPERATING SYSTEMS》和《Operating System Concepts》。