OS concept - 同步工具（Synchronization tools）

1.背景

多个进程可以并发或并行执行，并发在于进程可能执行完部分程序的时候，被打断，处理器转而执行另一个进程的程序；并行在于代表两个进程的两个指令流在各自的处理器上同时执行。
多个并发或并发执行的程序访问到共享数据时，可能会导致数据的不一致；
故需要有种机制确保进程的有序执行，以维护数据的一致性。
举例说明-生产者-消费者程序模型
生产者程序

while (true) { 
    /* produce an item in next produced */ 
    while (count == BUFFER SIZE) ; 
    /* do nothing */ 
    buffer[in] = next produced; 
    in = (in + 1) % BUFFER SIZE;
    count++; 
}

消费者程序

while (true) { 
    while (count == 0) ; 
    /* do nothing */ 
    next consumed = buffer[out];
    out = (out + 1) % BUFFER SIZE; 
    count--; 
    /* consume the item in next consumed */ }

其中当生产者程序count++和消费者程序count--并发执行时，两者执行后结果可能是4，5或6.
count++ 等同于

register1 = count
register1 = register1 +1 
count = register1

count--等同于

register2 = count
register2 = register2 - 1 
count = register2

两者执行顺序可能是：
(1) 若生产者程序先执行，则结果是4，反过来则是6==》 不正确的状态

T0: producer execute register1 = count {register1 = 5} 
T1: producer execute register1 = register1 + 1{register1 = 6} 
T2: consumer execute register2 = count {register2 = 5} 
T3: consumer execute register2 = register2 − 1{register2 = 4} 
T4: producer execute count = register1 {count = 6} 
T5: consumer execute count = register2 {count = 4}

(2) 若两者错开执行，则为5 ==》正确的状态
这种状态就是竞态。这个问题主要靠进程同步工具来解决。

2.临界区（critical section）

避免竞态问题，即避免进程访问的共享数据的部分代码出现竞态，可将这部分程序抽象成一个临界区，并保证两个进程不可能同时临界区。
临界区框架

image.png
临界区问题解决方案要求
1）互斥-一个进程处于临界区时，不会有其他进程同时处于临界区；
2）前进-没有进程进入临界区时，下次进临界区的进程，不会无限期等待；
3）有限等待-不能使其他进程无限等待临界区；

3.同步的硬件支持

3.1 内存屏障指令

内存模型两种：
强有序：一个处理器上的内存修改立刻对所有其他处理可见；
弱有序：一个处理器上的内存修改可能不会立刻对所有其他处理可见；
内存屏障指令

• 就是用来强制内存改变对所有其他处理器可见;
• 确保该指令前面的load 和store 比其后的要先完成；
• 确保即使指令重新安排顺序，前面的load 和store 比其后的要先完成；

例子：
线程1 执行

while (!flag)   
memory_barrier();  
print x

线程2 执行

x = 100;  
memory_barrier();  
flag = true

线程1加内存屏障指令保证在加载x 前，加载flag;
线程2加内存屏障指令保证，在赋值给flag 前先赋值给x;

3.2 硬件指令-特殊的硬件指令

Test-and-Set 指令

Compare-and-Swap 指令

Test-and-Set 指令

• 定义

boolean test_and_set (boolean *target)
{
      boolean rv = *target;
      *target = true;
      return rv:
}

• 特点
  1）原子执行；
  2）返回值为：传递参数的最初的值；
  3）设置传递的参数的值为true；
• critical section问题的解决方案
  1） bool 变量lock初始化为false；
  2）使用框架

do {      while (test_and_set(&lock)) 
      ; /* do nothing */ 
      /* critical section */ 
      lock = false; 
      /* remainder section */ 
} while (true);

Compare-and-Swap 指令

• 定义

int compare_and_swap(int *value, int expected, int new_value)
{                  
    int temp = *value; 
    if (*value == expected) 
         *value = new_value; 
    return temp; 
} 

• 特点
• critical section 的解决方案

while (true){
      while (compare_and_swap(&lock, 0, 1) != 0) 
          ; /* do nothing */ 
      /* critical section */ 
      lock = 0; 
      /* remainder section */ 
} 

有限等待的compare-and-swap

while (true) {   waiting[i] = true;   key = 1;   while (waiting[i] && key == 1) 
      key = compare_and_swap(&lock,0,1); 
   waiting[i] = false; 
   /* critical section */ 
   j = (i + 1) % n; 
   while ((j != i) && !waiting[j]) 
      j = (j + 1) % n; 
   if (j == i) 
      lock = 0; 
   else 
      waiting[j] = false; 
   /* remainder section */ 
}

3.3 原子变量

• 硬件指令通常用来构建其他的同步工具，原子变量就是这样实现的工具。
• 原子变量提供对基本数据类型原子（不可打断）更新
• 例子
  1）sequence 是原子变量；
  2）increment（）对原子变量+1；
  3）命令：increment（&sequence);
  确保sequence + 1 不会被打断；
  4）increment 实现

void increment(atomic_int *v){  int temp;   do {        temp = *v;  }   while (temp != (compare_and_swap(v,temp,temp+1));} 

4.同步工具

4.1 互斥量

• 前面的方案对应用开发来说不可用
• OS 需要构建软件工具；
• 互斥量保护critical section方法：
  首先，acquire（）一个锁；
  然后，release（）这个锁；
• acquire（）和release（）必须是原子；
  • 通常通过硬件原子指令（像compare-and-swap）
• 需要忙等：spinlock
• 使用互斥量，Critical section问题的解决方案

while (true) { 
    acquire lock 
            
       critical section 

    release lock 
    
        remainder section 
} 

4.2 信号量（semaphore）

4.2.1 基本

• 提供进程同步活动
• 信号量Semaphore S 是一个整型变量；
• 只通过两个原子操作访问
  • wait() 和signal() 以前叫P(),V()
• wait()定义

wait(S) { 
    while (S <= 0)
       ; // busy wait
    S--;
}

• signa()定义

signal(S) { 
    S++;
}

• 信号量分类-基于S 取值范围
  1）计数信号量（无限）
  2）二进制信号量（0-1）--等同于一个互斥量
• 可以作为一个二进制信号量来实现计数信号量；

4.2.2 信号量用途

• 解决critical section问题
  创建一个semaphore “mutex" ,初始化为1

wait(mutex);
   CS
signal(mutex);

• 解决两个进程同步问题
  如进程P1、P2，保证在s2 语句执行之前s1 发生；

P1:
   S1;
   signal(synch);
P2:
   wait(synch);
   S2;

4.2.3 信号量的实现

前面定义的wait()和signal() 信号量操作都需要忙等的弱点，类似于互斥量的实现。
若临界区占用很少CPU时间，则只有很少的忙等。
若应用在临界区占用很多时间，则不是好的解决方案。
这就需要不忙等的信号量：

• 当进程进程执行wait()发现信号量值不是大于0，则必须等，但不是忙等，而是进程suspend 自身。
• suspend 操作把进程放到一个与信号量相关的等待队列中，并把进程的状态切换成waiting状态，然后加控制权交给CPU 调度器，选择下一个运行的进程。
• 其他进程执行与这个信号量的signal() 操作则通过wakeup()让suspended 进程重新运行,将进程状态从waiting 状态转变成ready 状态。
  不忙等的信号量的实现
• 每个信号量，有一个相关连的等待队列
• 等待队列的每个entry 有两个items:

1. value : int
2. 指向链表的下一个entry

typedef struct { 
    int value; 
    struct process *list; 
} semaphore; 

• 两个操作
  1）阻塞(block) -把进程放到一个与信号量相关的等待队列中
  2）唤醒(wakeup)-让suspended 进程从等待队列中移除，放到ready 队列重新运行,将进程状态从waiting 状态转变成ready 状态
  wait 实现

wait(semaphore *S) { 
   S->value--; 
   if (S->value < 0) {
      add this process to S->list; 
      block(); 
   } 
}

signal实现

signal(semaphore *S) { 
   S->value++; 
   if (S->value <= 0) {
      remove a process P from S->list; 
      wakeup(P); 
   } 
}