美文网首页
OS concept-同步

OS concept-同步

作者: 1哥 | 来源:发表于2021-11-05 09:07 被阅读0次

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); 
   } 
} 

相关文章

网友评论

      本文标题:OS concept-同步

      本文链接:https://www.haomeiwen.com/subject/wtmfzltx.html