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

临界区问题解决方案要求
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:
- value : int
- 指向链表的下一个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);
}
}
网友评论