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()通过互斥锁保证。

Luminol Chen
Luminol Chen
2024 Undergraduate in Cyberspace Security

My research interests include cryptography and blochchain.