作者: 雪山肥鱼
时间：20210427 06:10
目的：信号量
# 信号量的定义
# 二值信号量
# 信号量用作条件变量
# 生产者消费者问题
# 初次尝试
# 读写锁
# 哲学家就餐问题
信号量的定义
#include <semaphore.h>
sem_t s;
//sem_init(sem_t* sem , int pshared, unsigned int value);
sem_init(&s, 0, 1);
信号量是一个整数，在POSIX标准中，我们可以通过sem_wait() 和 sem_post()来操作这个整数。信号量的初始化值，决定了后续同步进程或者线程的行为。
参数意义.png
第二个参pshared 决定了 是进程还是线程使用的信号量。如果是线程，那么信号量必定是全局变量 或者 来源于 heap，因为线程是可以共享全局变量 or heap的嘛.
第三个参数 是信号量的初始值。
int wait(sem_s *s) {
decrement the value of semaphore **s** by one wait if value of semaphore **s** is negative
}
int sem_post( sem_s *s ) {
increment the value of semaphore **s** by one if there are one or more threads waiting , wake one
}
//we can see that sem_wait() will either return right away, or it will cause the caller to suspend execution waiting for a subsequent post.
sem_wait() 的行为有两种
- 立刻返回，当信号量的值大于等于1（如果信号量为0，wait后 为 -1，阻塞）
- 当信号量 为 负数时，挂起调用线程，放到睡眠队列中，等待被下一个post操作唤醒
sem_post() 不用等，直接+1 就行，如果这时候睡眠队列里有线程，那么将被唤醒
sem_t m;
sem_init( &m, 0 , X); //initialize semaphore to X; what should X be
sem_wait(&m）；
// critial section here
sem_post(&m);
当信号量为负数时，值就是等待线程的个数。信号量的使用者看不见这个值，但记住这句话有助于我们理解信号量的行为
二值信号量(锁)
Binary Semaphores
sem_init(&m, 0, 1);
二值信号量初始化为1. 调度流程如下：
调度.png
- sem_t 初始化值为1
- T0调用 sem_wait 会立刻返回，进入临界区 sem_t 的值为 0
- 如果此时中断，进入T1
- T1调用 sem_wait，都是先做减法，再查看结果 0 - 1 = -1，阻塞，进入睡眠队列，等待被唤醒。 -1 代表着有一个线程在等待
- T0 一直运行，直到出临界区，调用sem_post()。sem_t -1 + 1 = 0
- T1 从睡眠队列唤醒（sleep -> ready 等待被调度而已），执行临界区代码
- T1 结束 ，sem_t + 1 = 0+1 = 1. 信号量恢复到1.
二值信号量的效果相当于锁。
信号量用作条件变量
打个比方，效果就是，线程A 在等待其他线程操作list， 线程B只有当这个list非空时，才会进行减操作。也就是说一个线程的执行条件，时另一个线程的结束。
类似条件变量
void * child(void *arg) {
printf("child\n");
sem_post(&s); //signal here:child is done
return NULL:
}
sem_t s;
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);
printf("parent:end\n");
return 0;
}
调度.png
调度会有两种情况。
- 父线程优先被调度，信号量的限制 0 -> -1 ，睡眠。子线程执行
- 子线程优先被调度，就算在执行post 之前 又切换回父线程，父线程一样会睡眠，不执行，再回到子线程 post 后，父线程才执行。
生产者消费者问题
初次尝试
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;
}
sem_t empty;
sem_t full;
void * producer(void * arg) {
int i;
for(i = 0; i< loops; i++ ) {
sem_wait(&empty);//Line P1
put(i);//Line P2
sem_post(&fill);//Line P3
}
}
void * consumer(void * arg) {
int i, tmp = 0;
while(tmp != -1) {
sem_wait(&mutex);
tmp = get();//Line C2
sem_post(&empty);//Line C3
printf("%d\n", tmp);
}
}
int main(int argc, char ** argv) {
//
sem_init(&empty, 0, MAX);
sem_init(&full, 0, 0);
//
}
代码解析：empty buffer 中有多少空位置， full buffer中生产了几个
- consumer 先运行 生产者 full 初始为 0, buffer内部无数据
- sem_t full 初始值 为 0 上来就阻塞，直接就睡了
- 切换到 producer，sem_t empty -1, full + 1.
- consumer 复活，进入ready状态
- 两者竞争，看谁能被调度。
- consumer被调度，full -1, empty+1 告诉producer 继续生产1个
- producer被调度， empty -1 ,full +1， buffer内部又多了一个。可以让consumer消费。
- producer 先运行
- empty 空位置很多，上了就可以占用CPU 运行起来
- full + 1 后，此时 切换到consumer, consumer 发现 full 信号量为1，则运行
- 两者互相切换。
问题：单CPU ，MAX为1时没有问题。当运行到多CPU，且多个 consumer时
对buffer的操作没上锁，会导致race condition. 此时要注意避免死锁。
//增加二值信号量
sem_t empty;
sem_t full;
sem_t mutex;
void * producer(void * arg) {
int i;
for(i = 0; i< loops; i++ ) {
sem_wait(&empty);//Line P1
sem_wait(&mutex);
put(i);//Line P2
sem_post(&mutex);
sem_post(&fill);//Line P3
}
}
void * consumer(void * arg) {
int i, tmp = 0;
for(i = 0;i <loop; i++) {
sem_wait(&full);//Line C1
sem_wait(&mutex);
tmp = get();//Line C2
sem_wait(&mutex);
sem_post(&empty);//Line C3
printf("%d\n", tmp);
}
}
int main(int argc, char ** argv) {
//
sem_init(&empty, 0, MAX);
sem_init(&full, 0, 0);
sem_init(&mutex, 0, 1);
//
}
读写锁
typedef struct _rwlock_t {
sem_t lock; // binary semaphere(basic lock)
sem_t writelock; //use to allow one writers or many readers
int readers; // count how many readers
}rwlock_t;
void rwlock_init(rwlock *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 release acquire 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)
sem_post(&rw->writelock); //last reader release 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);
}
以上代码需求，可以自由获取读锁，但是只有第一个读者可以获得写锁，同时只有当所有读锁都释放的时候，写锁才会释放。
值得注意的是读写锁经常带来性能开销。
哲学家就餐问题
哲学家就餐.png
五个哲学家坐在圆桌周围，一个哲学家左右手各一个叉子，哲学家有时思考，有时候吃饭，思考的时候，左右手，不拿叉子，吃饭的时候必须左右手双手都拿叉子才能吃饭。引入竞争问题
网友评论