分享
 
 
 

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

王朝other·作者佚名  2008-05-19
窄屏简体版  字體: |||超大  

浪子清风

先看进程间的互斥。在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

的机

器(UP)上微观上只有一个进程在运行。所以在UP中,spin_lock和spin_unlock就都是空

的了。

在SMP中,spin_lock()和spin_unlock()定义如下。

typedef struct {

volatile unsigned int lock;

} spinlock_t;

static inline void spin_lock(spinlock_t *lock)

{

__asm__ __volatile__(

"\n1:\t"

"lock ; decb %0\n\t"

"js 2f\n" //lock->lock< 0 ,jmp 2 forward

".section .text.lock,\"ax\"\n"

"2:\t"

"cmpb $0,%0\n\t" //wait lock->lock==1

"rep;nop\n\t"

"jle 2b\n\t"

"jmp 1b\n"

".previous"

:"=m" (lock->lock) : : "memory");

}

static inline void spin_unlock(spinlock_t *lock)

{

__asm__ __volatile__(

"movb $1,%0"

:"=m" (lock->lock) : : "memory"); //lock->lock=1

}

一般是如此使用:

#define SPIN_LOCK_UNLOCKED (spinlock_t) { 1 }

spinlock_t xxx_lock = SPIN_LOCK_UNLOCKED;

spin_lock_(&xxx_lock)

...

critical section

...

spin_unlock (&xxx_lock)

可以看出,它和semaphore机制解决的都是两个进程的互斥问题,都是让一个进程退出临

界区后另一个进程才进入的方法,不过sempahore机制实行的是让进程暂时让出CPU,进

入等待队列等待的策略,而spin_lock实行的却是却进程在原地空转,等着另一个进程结

束的策略。

下边考虑中断对临界区的影响。要互斥的还有进程和中断服务程序之间。当一个进程在

执行一个临界区的代码时,可能发生中断,而中断函数可能就会调用这个临界区的代码

,不让它进入的话就会产生死锁。这时一个有效的方法就是关中断了。

#define local_irq_save(x) __asm__ __volatile__("pushfl ; popl %0 ;

cli":

"=g" (x): /* no input */ :"memory")

#define local_irq_restore(x) __asm__ __volatile__("pushl %0 ; popfl": /*

no

output */ :"g" (x):"memory")

#define local_irq_disable() __asm__ __volatile__("cli": : :"memory")

#define local_irq_enable() __asm__ __volatile__("sti": : :"memory")

#define cpu_bh_disable(cpu) do { local_bh_count(cpu)++; barrier(); } while (

0)

#define cpu_bh_enable(cpu) do { barrier(); local_bh_count(cpu)--; } while

(0

)

#define local_bh_disable() cpu_bh_disable(smp_processor_id())

#define local_bh_enable() cpu_bh_enable(smp_processor_id())

对于UP来说,上面已经是足够了,不过对于SMP来说,还要防止来自其它cpu的影响,这

时解决的方法就可以把上面的spin_lock机制也综合进来了。

#define spin_lock_irqsave(lock, flags) do {

local_irq_save(flags); sp

in_lock(lock); } while (0)

#define spin_lock_irq(lock) do { local_irq_disable();

spin_lock(lo

ck); } while (0)

#define spin_lock_bh(lock) do { local_bh_disable();

spin_lock(loc

k); } while (0)

#define spin_unlock_irqrestore(lock, flags) do { spin_unlock(lock); local_i

rq_restore(flags); } while (0)

#define spin_unlock_irq(lock) do { spin_unlock(lock);

local_irq_enable();

} while (0)

#define spin_unlock_bh(lock) do { spin_unlock(lock);

local_bh_enable();

} while (0)

前面说过,对于UP来说,spin_lock()是空的,所以以上的定义就一起适用于UP 和SM

P的情形了。

而read_lock_irqsave(lock, flags) , read_lock_irq(lock),

read_lock_bh(lock) 和

write_lock_irqsave(lock, flags) , write_lock_irq(lock),

write_lock_bh(lock

) 就是spin_lock的一个小小的变型而己了。

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
推荐阅读
 
 
 
>>返回首頁<<
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有