Linux内核中的同步和互斥分析报告

来源： 作者： 时间：2008-02-15 Tag： 点击：

先看进程间的互斥。在linux内核中主要通过semaphore机制和spin_lock机制实现。主要的区别是在semaphore机制中，进不了临界区时会进行进程的切换，而spin_lock刚执行忙等（在smp中）。先看内核中的semaphore机制。前提是对引用计数count增减的原子性操作。内核用atomic_t的数据结构和在它上面的一系列操作如atomic_add()、 atomic_sub()等等实现。（定义在atomic.h中）semaphone机制主要通过up()和down()两个操作实现。 semaphone的结构为:

struct semaphore
{
atomic_t count;
int sleepers;
wait_queue_head_t wait;
};

　　相应的down()函数为:

static inline void down(struct semaphore*sem)
{
/* 1 */sem->count--; //为原子操作
if(sem->count<0)
{
struct task_struct *tsk = current;
declare_waitqueue(wait, tsk);
tsk->state = task_uninterruptible;
add_wait_queue_exclusive(&sem->wait, &wait);
spin_lock_irq(&semaphore_lock);
/* 2 */ sem->sleepers++;
for (;;) {
int sleepers = sem->sleepers;
/*
* add "everybody else" into it. they aren't
* playing, because we own the spinlock.
*/
/* 3 */ if (!atomic_add_negative(sleepers - 1, &sem->count)) {
/* 4 */ sem->sleepers = 0; //这时sem->count=0
break;
}
/* 4 */ sem->sleepers = 1; /* us - see -1 above */ // 这时sem
->count
=-1
spin_unlock_irq(&semaphore_lock);
schedule();
tsk->state = task_uninterruptible;
spin_lock_irq(&semaphore_lock);
}
spin_unlock_irq(&semaphore_lock);
remove_wait_queue(&sem->wait, &wait);
tsk->state = task_running;
wake_up(&sem->wait);
}
}

　　相应的up()函数为:

void up(struct semaphore*sem)
{
sem->count++; //为原子操作
if(sem->count<=0)
{
//唤醒等待队列中的一个符合条件的进程（因为每个进程都加了task_exclusive标志）
。
};

　　假设开始时，count=1;sleepers=0。当进程a执行down()时，引用计数count--，如果这时它的值大于等于0，则从down()中直接返回。如果count少于0，则a的state改为 task_interruptible后进入这个信号量的等待队列中，同时使sleepers++;然后重新计算count=sleepers - 1 + count,若这时引用计数仍小于0（一般情况下应为-1，因为count = - sleepers,不过在smp结构中，期间别的进程可能执行了up()和down()从而使得引用计数的值可能变化），则执行进程切换。

　　当进程a又获得机会运行时，它先执行 wake_up(&sem->wait)操作，唤醒等待队列里的一个进程，接着它进入临界区，从临界区出来时执行up()操作，使 sem->count++,（如果进程a是从down()中直接返回，因为这时等待队列一定为空，所以它不用执行wake_up()操作，

直接进入临界区，在从临界区出来时一样执行up()操作，使 sem->count++）。这时如果count的值小于等于0，这表明在它在临界区期间又有一个进程（可能就是它进入临界区时唤醒的那个进程）进入睡眠了，则执行wake_up()操作，反之，如果count的值已经大于0，这表明在它在临界区期间没有别的进程（包括在它进入临界区时被它唤醒过的那个进程）进入睡眠，那么它就可以直接返回了。

　　从被唤醒的那个进程看看，如果在唤醒它的进程没执行up()之前它就得到了运行机会，这时它又重新计算count=sleepers - 1 + count=-1；从而sleepers被赋值1；这时它又必须进行调度让出运行的机会给别的进程，自己去睡眠。这正是发生在唤醒它的进程在临界区时运行的时候。如果是在唤醒它的进程执行了up()操作后它才得到了运行机会，而且在唤醒它的进程在临界区期间时没别的进程执行down()，则count的值在进程执行up()之前依然为0，这时在up()里面就不必要再执行wake_up()函数了。可以通过一个例子来说明具体的实现。设开始 sem->count=sem->sleepers=0。也就是有锁但无等待队列（一个进程已经在运行中）。先后分别进行3个down()操作，和3个up()操作，如下：为了阐述方便，只保留了一些会改变sleepers和 count值的步骤，并且遵循从左到右依次进行的原则。

down1:
count(0->-1),sleepers(0->1),sleepers-1+count(-1),count(-1),sleepers(1),调度
down2:
count(-1->-2),sleepers(1->2),sleepers-1+count(-1),count(-1),sleepers(1),调度
down3:
count(-1->-2),sleepers(1->2),sleepers-1+count(-1),count(-1),sleepers(1),调度

up1:
count(-1->0),唤醒一个睡眠进程（设为1）,（进程1得到机会运行）
sleepers-1+count(0),count(0),sleepers(0),break,
唤醒另一个睡眠进程（设为2），（进程2得到机会运行）
sleepers-1+count(-1),count(-1),sleepers(1),
调度（没达到条件，又得睡觉）也可能是这样的：
up1`:
count(-1->0),唤醒一个睡眠进程（设为1）,（进程1得到机会运行）
sleepers-1+count(0),count(0),sleepers(0),break,
唤醒另一个睡眠进程（设为2），进程2在以后才得到机会运行）
up2:
count(-1->0),（因为count<=0）唤醒一个睡眠进程（设为2）,进程2得到机会运行）
sleepers-+count(0) , count(0) , sleepers(0) ,break,
唤醒另一个睡眠进程（设为3），进程3得到机会运行）
sleepers-1+count(-1),count(-1),sleepers(1),
调度（没达到条件，又得睡觉）对应上面的1`：
up2`:
count(0->1),（因为count>0,所以直接返回）进程2得到机会运行）
sleepers-1+count(0),count(0),sleepers(0),break,
唤醒另一个睡眠进程，（设为3）
up3:
count(-1->0),（因为count<=0）唤醒一个睡眠进程（设为3）,进程3得到机会运行）
sleepers-1+count(0),count(0),sleepers(0),break,
唤醒另一个睡眠进程（这时队列里没进程了）
进程3运行结束，执行up(), 使count =1 ,这时变成没锁状态 ）
对应上边的2`：
up3`:
count(0->1),（因为count>0,所以直接返回）进程3得到机会运行）
sleepers-1+count(0),count(0),sleepers(0),break,
唤醒另一个睡眠进程（这时队列里没进程了）
进程3运行结束，执行up(), 使count =1 ,这时变成没锁状态 ）

[收藏] [推荐] [评论] [打印] [关闭]

顶一下

上一篇：Linux系统内核的同步机制－自旋锁
下一篇：what does exit() do when be called

最新评论共有 4 位网友发表了评论

查看所有评论

发表评论

栏目列表

91Linux!