当前位置:操作系统 > Unix/Linux >>

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

浪子清风

  先看进程间的互斥。在linux内核中主要通过semaphore机制和spin_lock机制实现。主要

  的区别是在semaphore机制中,进不了临界区时会进行进程的切换,而spin_lock刚执行

  忙等(在SMP中)。

  先看内核中的semaphore机制。前提是对引用计数count增减的原子性操作。内核用a

  to

  mic_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 ,这时变成没锁状态 )

  当然,还有另一种情况,就是up()操作和down()操作是交*出现的,

  一般的规律就是,如果进程在临界区期间又有进程(无论是哪个进程,新来的还是刚被

  唤醒的那个)进入睡眠,就会令count的值从0变为-1,从而进程在从临界区出来执行up

  ()里就必须执行一次wake_up(),以确保所有的进程都能被唤醒,因为多唤醒几个是没关

  系的。如果进程在临界区期间没有别的进程进入睡眠,则从临界区出来执行up()时就用

  不着去执行wake_up()了(当然,执行了也没什么影响,不过多余罢了)。

  而为什么要把wake_up()和count++分开呢,可以从上面的up1看出来,例如,进程2第一

  次得到机会运行时,本来这时唤醒它的进程还没执行up()的,但有可能其它进程执行了

  up()了,所以真有可能会发现count==1的情况,这时它就真的不用睡觉了,令count=sl

  eepers=0,就可以接着往下执行了。

  还可看出一点,一般的,( count ,sleepers)的值的取值范围为(n ,0)[n>0] 和(0

  ,0

  )和 (1 ,-1)。

  下边看看spin_lock机制。

  Spin_lock采用的方式是让一个进程运行,另外的进程忙等待,由于在只有一个cpu

  的机
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,