About Semaphore
Something about Semaphore

信号量应用 3、用信号量描述同步:
例: 某控制测量系统中,数据采集任务反复把 所采集的数据送入一个单缓冲区;计算任务不断从 该单缓冲区取出数据进行计算。
var buf;
int flag = 0;
collection() {
while (ture) {
// 采集数据;
while(flag==1);
// 将采集的数据放入buffer;
flag=1;
}
}
calculate() {
while (ture) {
while(flag==0);
// 从buf中取出数据;
flag=0;
// 计算处理;
}
}
🤔 此处使用signal flag替代信号量,会不会产生问题?
Answer:可以看到此处while(flag==1);
和while(flag==0);
均为循环忙等的操作,
因此该方法和教材中整型信号量是一致的,因此会出现让权等待、有限等待不满足的问题。
😉 问题解答结束,以下为相关的补充内容
1 整型信号量
教材:整型信号量:
typedef int semaphore;
P(semaphore sem) {
while (sem<=0)
; /* 循环忙等 */
sem--;
}
V(semaphore sem) {
sem++;
}
存在循环忙等,和PPT给出方法是一致的,该方法显然不满足:
- 让权等待:P操作循环忙等。
- 有限等待:某一线程V操作后其余线程竞争资源,其结果不确定。
2 整型信号量的小改进
此处我们消除循环忙等的过程,通过yield()
让线程转让CPU使用权。
typedef int semaphore;
P(semaphore sem) {
bool succ = false;
while (!succ) {
if (sem > 0) {
sem--;
succ = true;
}
if (!succ)
yield();
}
}
V(semaphore sem) {
sem++;
}
但是此时发现仅满足让权等待(yield()
对应线程让权),但不满足有限等待(同1部分)。
3 记录型信号量
教材:记录型信号量:利用PCB链式队列实现,仅需保证单条操作的原子性(through model-checker)
model-checker 信号量的状态转移图
typedef struct {
int value;
struct PCB *list;
} semaphore;
P(semaphore *sem) {
S->value--;
if (S->value < 0) {
block(S->list);
}
}
V(semaphore *sem) {
S->value++;
if (S->value <= 0) {
wakeup(S->list);
}
}
4 信号量(API实现)
进一步:信号量实际的实现,思想和教材中的记录型信号量相同,对应semaphore.h
的抽象。由于semaphore.h
的源码不是很好找(笔者的系统上这个被链接了,需要一些
反汇编),此处给出OSTEP的实现:
Ref: https://github.com/remzi-arpacidusseau/ostep-code/blob/master/threads-sema/zemaphore.h
#ifndef __zemaphore_h__
#define __zemaphore_h__
typedef struct __Zem_t {
int value;
pthread_cond_t cond;
pthread_mutex_t lock;
} Zem_t;
void Zem_init(Zem_t *z, int value) {
z->value = value;
Cond_init(&z->cond);
Mutex_init(&z->lock);
}
void Zem_wait(Zem_t *z) {
Mutex_lock(&z->lock);
while (z->value <= 0)
Cond_wait(&z->cond, &z->lock);
z->value--;
Mutex_unlock(&z->lock);
}
void Zem_post(Zem_t *z) {
Mutex_lock(&z->lock);
z->value++;
Cond_signal(&z->cond);
Mutex_unlock(&z->lock);
}
#ifdef __APPLE__
typedef Zem_t sem_t;
#define Sem_wait(s) Zem_wait(s)
#define Sem_post(s) Zem_post(s)
#define Sem_init(s, v) Zem_init(s, v)
#endif
#endif // __zemaphore_h__
可以看到使用了一个互斥锁和条件变量。
事实上条件变量对应上面的的PCB队列,而block()
和wakeup()
的原子性,
对应这里条件变量的wait()
和signal()
通过互斥锁保证。