About Semaphore

Something about Semaphore

Luminol Chen

Oct 11, 2022 2 min read Operating System

信号量应用 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()通过互斥锁保证。

Operating System