explorer

万丈高楼平地起,勿在浮沙筑高台

0%

[What]Semaphores

信号量是我平时使用最为频繁的同步和计数工具,看看大师怎么说……

信号量的基本使用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//先初始化再使用
#include <semaphore.h>
sem_t s;
sem_init(&s, 0, 1);

//当信号量的值为负时,对应多少个线程在等待该信号量
int sem_wait(sem_t *s) {
//decrement the value of semaphore s by one
//wait if value of semaphore s is negative
}

int sem_post(sem_t *s) {
//increment the value of semaphore s by one
//if there are one or more threads waiting, wake one
}

二值信号量作为锁

使用二值信号量可以作为锁来完成临界区的互斥:

  • 进入临界区前获取该锁
  • 退出临界区后释放该锁

根据以上逻辑可以知道锁的初始值为 1:

1
2
3
4
5
6
sem_t m;
sem_init(&m, 0, 1); // initialize to 1;

sem_wait(&m);
// critical section here
sem_post(&m);

信号量用于排序(同步)

一个线程要等待另一个线程到达某个条件后,才继续往后执行,所以这种情况下信号量的初始值为 0.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
sem_t s;

void *child(void *arg) {
printf("child\n");
sem_post(&s); // signal here: child is done
return NULL;
}

int main(int argc, char *argv[]) {
sem_init(&s, 0, 0);
printf("parent: begin\n");
pthread_t c;
Pthread_create(&c, NULL, child, NULL);
sem_wait(&s); // wait here for child
printf("parent: end\n");
return 0;
}

使用信号量解决生产者和消费者问题

根据前面使用条件变量的实现来看,也是需要满位和空位,只是这里的满位和空位是由信号量来表示。

除此之外,对于缓存区的写入也是需要做互斥的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
 int buffer[MAX];
int fill = 0;
int use = 0;

void put(int value) {
buffer[fill] = value; // Line F1
fill = (fill + 1) % MAX; // Line F2
}

int get() {
int tmp = buffer[use]; // Line G1
use = (use + 1) % MAX; // Line G2
return tmp;
}
void *producer(void *arg) {
int i;
for (i = 0; i < loops; i++) {
sem_wait(&empty); // Line P1
sem_wait(&mutex); // Line P1.5 (MUTEX HERE)
put(i); // Line P2
sem_post(&mutex); // Line P2.5 (AND HERE)
sem_post(&full); // Line P3
}
}

void *consumer(void *arg) {
int i;
for (i = 0; i < loops; i++) {
sem_wait(&full); // Line C1
sem_wait(&mutex); // Line C1.5 (MUTEX HERE)
int tmp = get(); // Line C2
sem_post(&mutex); // Line C2.5 (AND HERE)
sem_post(&empty); // Line C3
printf("%d\n", tmp);
}
}

需要注意的是: 互斥量放置位置需要在满位和空位之间,如果互斥量在满位和空位外面,则很大概率会照成死锁。

读写锁

读写锁的实现逻辑如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
typedef struct _rwlock_t {
sem_t lock; // binary semaphore (basic lock)
sem_t writelock; // allow ONE writer/MANY readers
int readers; // #readers in critical section
} rwlock_t;

void rwlock_init(rwlock_t *rw) {
rw->readers = 0;
sem_init(&rw->lock, 0, 1);
sem_init(&rw->writelock, 0, 1);
}

void rwlock_acquire_readlock(rwlock_t *rw) {
sem_wait(&rw->lock);
rw->readers++;
if (rw->readers == 1) // first reader gets writelock
sem_wait(&rw->writelock);
sem_post(&rw->lock);
}

void rwlock_release_readlock(rwlock_t *rw) {
sem_wait(&rw->lock);
rw->readers--;
if (rw->readers == 0) // last reader lets it go
sem_post(&rw->writelock);
sem_post(&rw->lock);
}

void rwlock_acquire_writelock(rwlock_t *rw) {
sem_wait(&rw->writelock);
}

void rwlock_release_writelock(rwlock_t *rw) {
sem_post(&rw->writelock);
}

需要注意的是:假设有多个频繁的读操作,有可能会导致写操作无法进行(被饿死),这种情况下使用普通的互斥锁更为高效。

哲学家就餐问题

哲学家获得餐具就是一段临界区,这段临界区需要做互斥,每个哲学家的逻辑如下:

1
2
3
4
5
6
while (1) {
think();
get_forks(p);
eat();
put_forks(p);
}

这里的关键就在于 get_forks(),put_forks() 的处理。

假设有 5 个哲学家,那么就会有 5 个餐具,为了实现 5 个餐具的互斥,假设以下面的方法实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 5 个餐具的互斥,初始情况下的值为 1
sem_t forks[5];

//获得左边的餐具
int left(int p) { return p; }
//获得右边的餐具
int right(int p) { return (p + 1) % 5; }

void get_forks(int p) {
sem_wait(&forks[left(p)]);
sem_wait(&forks[right(p)]);
}

void put_forks(int p) {
sem_post(&forks[left(p)]);
sem_post(&forks[right(p)]);
}

上面的实现会造成死锁,因为假设有多个线程的话,当一个线程获取了左边的餐具后,右边 的餐具很可能被它旁边的哲学家获取到了。如此环环相扣,便造成了死锁。

要解开这个环,只需要解开其中几个扣即可:

1
2
3
4
5
6
7
8
9
void get_forks(int p) {
if (p == 4) {
sem_wait(&forks[right(p)]);
sem_wait(&forks[left(p)]);
} else {
sem_wait(&forks[left(p)]);
sem_wait(&forks[right(p)]);
}
}

当第 5 个哲学家获取餐具时,他获取的顺序不同于前 4 种,这种情况下就不会锁住第 4 个哲学家了。

Last Updated 2020-06-28 Sun 11:59.
Render by hexo-renderer-org with Emacs 26.3 (Org mode 9.3.7)