linux2.6.27内核信号量的实现

  最近在当操作系统助教，老师要求完成linux0.11下的信号量的实现，感觉很多师弟师妹们对信号量的实现还不是很清楚,于是详细的看了一下linux2.6.27内核关于信号量的实现

----------------------------------------------------------------------------------------------------------------

首先看看信号量的相关数据结构:

<include/linux/semaphore.h>

struct semaphore {
    spinlock_t lock; #lock应该是这个信号量的自旋锁
    unsigned int count; #count表示的是这个信号量的计数器
    struct list_head wait_list; #wait_list顾名思义应该是等待链表了
};

信号量的数据结构就这么简单.那么信号量的初始化是怎么做的呢?还有大家熟悉的信号量P,V操作是怎么实现的呢?

----------------------------------------------------------------------------------------------------------------

信号量的初始化:

<include/linux/semaphore.h>

#define DECLARE_MUTEX(name) \
    struct semaphore name = __SEMAPHORE_INITIALIZER(name, 1)

#define __SEMAPHORE_INITIALIZER(name, n) \
{ \
    .lock = __SPIN_LOCK_UNLOCKED((name).lock), \ #初始化自旋锁
    .count = n, \ #将信号量计数器赋值为n
    .wait_list = LIST_HEAD_INIT((name).wait_list), \ #初始化等待队列
}

也可以用以下方法来初始化信号量:

<include/linux/semaphore.h>

static inline void sema_init(struct semaphore *sem, int val)
{
    static struct lock_class_key __key;
    *sem = (struct semaphore) __SEMAPHORE_INITIALIZER(*sem, val);
    lockdep_init_map(&sem->lock.dep_map, "semaphore->lock", &__key, 0);
}

#define init_MUTEX(sem) sema_init(sem, 1)
#define init_MUTEX_LOCKED(sem) sema_init(sem, 0)


-------------------------------------------------------------------------------------------------------------------
PV操作:

首先看看P操作

<kernel/semaphore.c>

void up(struct semaphore *sem)
{
    unsigned long flags;

    spin_lock_irqsave(&sem->lock, flags);
    if (likely(list_empty(&sem->wait_list)))#如果等待链表为空,表示没有正在等待此信号量的进程,count++就行
        sem->count++;
    else
        __up(sem);
    spin_unlock_irqrestore(&sem->lock, flags);
}

如果等待链表为空,表示没有正在等待此信号量的进程,count++就行

如果等待链表不为空,也就是还有进程在等待此信号量,那么此时进入到__up()这个函数中:


<kernel/semaphore.c>

static noinline void __sched __up(struct semaphore *sem)
{
    #取出等待链表中的最前面的那个进程
    struct semaphore_waiter *waiter = list_first_entry(&sem->wait_list,
                        struct semaphore_waiter, list);
    list_del(&waiter->list); #将这个进程从等待链表中删除
    waiter->up = 1;
    wake_up_process(waiter->task); #唤醒这个进程
}

此函数从等待列表中移出最前面的那个进程,然后唤醒它

<kernel/semaphore.c>

struct semaphore_waiter {
    struct list_head list; #链表项
    struct task_struct *task; #进程结构,也可以叫做进程PCB
    int up;
};

这个结构主要就是用来辅助把进程放到信号量的等待队列,后面的V操作会再介绍它


----------------------------------------------------------------------------------------------------------------

V操作:

<kernel/semaphore.c>

void down(struct semaphore *sem)
{
    unsigned long flags;

    spin_lock_irqsave(&sem->lock, flags); #要对sem进行操作了,加锁
    if (likely(sem->count > 0)) #如果count>0,直接count--就行了
        sem->count--;
    else
        __down(sem); #调用__down()
    spin_unlock_irqrestore(&sem->lock, flags); #对sem操作完毕,释放锁
}

如果count是<=0的,那么调用__down()来把进程放进等待队列里,现在看看__down()是怎么实现的

<kernel/semaphore.c>

static noinline void __sched __down(struct semaphore *sem)
{
    __down_common(sem, TASK_UNINTERRUPTIBLE, MAX_SCHEDULE_TIMEOUT);
}

static inline int __sched __down_common(struct semaphore *sem, long state, long timeout)
{
    struct task_struct *task = current; #得到当前正在运行的进程
    struct semaphore_waiter waiter;

    list_add_tail(&waiter.list, &sem->wait_list); #将waiter加到链表sem->wait_list后面
    waiter.task = task; #waiter的task设置成正在运行的这个进程
    waiter.up = 0;

    for (;;) {
        if (signal_pending_state(state, task)) #如果进程被一个意外的信号中断,直接放弃等待(从等待链表中删除),返回-EINTR错误号
            goto interrupted;
        if (timeout <= 0) #如果等待时间到,从等待链表中删除之,返回-ETIME错误号
            goto timed_out;
        __set_task_state(task, state); #设置进程状态为TASK_UNINTERRUPTIBLE
        spin_unlock_irq(&sem->lock);
        timeout = schedule_timeout(timeout); #调度
        spin_lock_irq(&sem->lock);
        if (waiter.up)
            return 0;
    }

 timed_out:
    list_del(&waiter.list);
    return -ETIME;

 interrupted:
    list_del(&waiter.list);
    return -EINTR;
}


该函数首先申请一个semaphore_waiter结构,

<kernel/semaphore.c>

struct semaphore_waiter {
    struct list_head list;
    struct task_struct *task;
    int up;
};

然后将这个结构加入到sem信号量的等待链表sem->wait_list中,
接着将当前进程task填入waiter.task中,

然后在一个循环中进行进程调度schedule_timeout,每进行一次调度,timeout会减小
如果当前进程task的状态位就绪,则跳转到interrupt,从信号量列表sem-wait_list中删除这个任务对应的节点
如果遇到意外的信号或者等待时间到,从信号量列表sem-wait_list中删除这个任务对应的节点,返回相应的错误号

-----------------------------------------------------------------------------------------------------------
内核还提供了其他几种V操作:
static noinline int __down_interruptible(struct semaphore *sem);
static noinline int __down_killable(struct semaphore *sem);
static noinline int __down_timeout(struct semaphore *sem, long jiffies);
这里就不一一介绍了

读者也可以参考这篇文章
内核同步机制-信号量