信号量

信号量(semaphore)是一种同步互斥的实现。semaphore一词来源于荷兰语,原来是指火车信号灯。想象一些火车要进站,火车站里有n个站台,那么同一时间只能有n辆火车进站装卸货物。当火车站里已经有了n辆火车,信号灯应该通知后面的火车不能进站了。当有火车出站之后,信号灯应该告诉后面的火车可以进站。

这个问题放在操作系统的语境下就是有一个共享资源只能支持n个线程并行的访问,信号量统计目前有多少进程正在访问,当同时访问的进程数小于n时就可以让新的线程进入,当同时访问的进程数为n时想要访问的进程就需要等待。

在信号量中,一般用两种操作来刻画申请资源和释放资源:P操作申请一份资源,如果申请不到则等待;V操作释放一份资源,如果此时有进程正在等待,则唤醒该进程。在ucore中,我们使用down函数实现P操作,up函数实现V操作。

首先是信号量结构体的定义:

typedef struct {
    int value;
    wait_queue_t wait_queue;
} semaphore_t;

其中的value表示信号量的值,其正值表示当前可用的资源数量,负值表示正在等待资源的进程数量。wait_queue即为这个信号量相对应的等待队列。

down函数实现的是P操作。首先关闭中断,然后判断信号量的值是否为正,如果是正值说明进程可以获得信号量,将信号量的值减一,打开中断然后函数返回即可。否则表示无法获取信号量,将自己的进程保存进等待队列,打开中断,调用schedule函数进行调度。等到V操作唤醒进程的时候,其会回到调用schedule函数后面,将自身从等待队列中删除(此过程需要关闭中断)并返回即可。具体的实现如下:

static __noinline uint32_t __down(semaphore_t *sem, uint32_t wait_state) {
    bool intr_flag;
    local_intr_save(intr_flag);
    if (sem->value > 0) {
        sem->value --;
        local_intr_restore(intr_flag);
        return 0;
    }
    wait_t __wait, *wait = &__wait;
    wait_current_set(&(sem->wait_queue), wait, wait_state);
    local_intr_restore(intr_flag);

    schedule();

    local_intr_save(intr_flag);
    wait_current_del(&(sem->wait_queue), wait);
    local_intr_restore(intr_flag);

    if (wait->wakeup_flags != wait_state) {
        return wait->wakeup_flags;
    }
    return 0;
}

up函数实现了V操作。首先关闭中断,如果释放的信号量没有进程正在等待,那么将信号量的值加一,打开中断直接返回即可。如果有进程正在等待,那么唤醒这个进程,把它放进就绪队列,把信号量的值加一,打开中断并返回。具体的实现如下:

static __noinline void __up(semaphore_t *sem, uint32_t wait_state) {
    bool intr_flag;
    local_intr_save(intr_flag);
    {
        wait_t *wait;
        if ((wait = wait_queue_first(&(sem->wait_queue))) == NULL) {
            sem->value ++;
        }
        else {
            assert(wait->proc->wait_state == wait_state);
            wakeup_wait(&(sem->wait_queue), wait, wait_state, 1);
        }
    }
    local_intr_restore(intr_flag);
}

下一节,我们来看看如何使用信号量实现条件变量以及管程。

最后更新于