January
30th,
2019
同步原语：
- 互斥：锁、原子操作、transaction
- 时间信号：barrier，flag
两种同步机制：
- 忙等待：不停地请求资源指导获取，如pthread_spin_lock
- 阻塞同步：当进程无法获取资源时，会有上下文切换，如pthread_mutux
锁实现
test-and-set lock
lock: ts R0, men[addr] // atomic: load mem[addr] into R0
// if mem[addr] is 0, set to 1
bnz R0, lock
unlock: st mem[addr], #0
void Lock(int* lock){
while(1){
if(test_and_set(*lock) == 0)
return;
}
}
- 处理器1获得锁，其他处理器会一直尝试获得锁，造成缓存一致性开销
- 处理器数量增加，获得/释放锁的开销增加，因为每个处理器的缓存需要同步锁的信息
test-and-test-and-set lock
void Lock(int* lock){
while(1){
while(*lock != 0);
if(test_and_set(*lock) == 0)
return;
}
}
- 缺点：非竞争时，延迟更高
- 优点：处理器1获得锁，其他处理器不会一直尝试获得锁，减少缓存一致性开销
test-and-set lock with back off
void Lock(int* lock){
int amount = 1;
while(1){
if(test_and_set(*lock) == 0)
return;
delay(amount); // 获得锁失败，延时
amount *= 2;
}
}
- 获取锁失败时，增加延迟时间
- 非竞争时，延时与test-and-set一样
- 产生竞争时，延时更高
ticket lock
struct lock{
volatile int next_ticket;
volatile int now_serving;
};
void Lock(lock* l){
int my_ticket = atimic_increment(&l->next_ticket);
while(my_ticket != l->now_serving);
}
void Unlock(lock* l){
l->now_serving++;
}
- 针对test-and-set lock中，处理器释放锁导致其他处理器竞争，处理器获得锁不公平的现象
- 释放锁时，更新一次缓存
array-based lock
struct lock{
volatile padded_int status[P];
volatile int head;
};
void Lock(lock* l){
int my_element = atimic_circ_increment(&l->head);
while(l->status[my_element] == 1);
}
void Unlock(lock* l){
l->status[my_element] = 1;
l->status[circ_next(my_element)] = 0;
}
- 释放锁时，更新一次缓存
atimic_circ_increment是复杂操作
barrier实现
- 定义：强制同步，等待所有线程到达该语句。
- 实现：当所有线程离开第一个barrier，开始计数，直到所有线程完成。
- 缓存同步$O(P)$，每个处理器获取锁、更新计数。
- 当所有处理器共享一个barrier时，有高竞争性，可以使用树状结构
struct Barrier_t{
LOCK lock;
int counter;
int flag;
}
int local_sense = 0; // 每个处理器私有
void Barrier(Barrier_t* b, int p){
local_sense = (local_sense == 0) ? 1 : 0;
lock(b->lock);
int num_arrived = ++(b->counter);
if(b->counter == p){ // 最后一个完成
unlock(b->lock);
b->counter = 0;
b->flag = local_sense;
}else{
unlock(b->lock);
while(b.flag != local_sense); // 等待flag
}
}