首页 | 邮件资讯 | 技术教程 | 解决方案 | 产品评测 | 邮件人才 | 邮件博客 | 邮件系统论坛 | 软件下载 | 邮件周刊 | 热点专题 | 工具
网络技术 | 操作系统 | 邮件系统 | 客户端 | 电子邮箱 | 反垃圾邮件 | 邮件安全 | 邮件营销 | 移动电邮 | 邮件软件下载 | 电子书下载

操作系统

Windows 9X | Linux&Uinx | Windows Server | 其它操作系统 | Vista | FreeBSD | Windows 7 |
首页 > 操作系统 > Linux&Uinx > Linux内核中的同步和互斥分析报告 > 正文

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

出处:5DMail.Net收集整理 作者:请作者联系 时间:2006-11-21 11:25:00

先看进程间的互斥。在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 ,这时变成没锁状态 )

当然,还有另一种情况,就是up()操作和down()操作是交*出现的,一般的规律就是,如果进程在临界区期间又有进程(无论是哪个进程,新来的还是刚被唤醒的那个)进入睡眠,就会令count的值从0变为-1,从而进程在从临界区出来执行up()里就必须执行一次wake_up(),以确保所有的进程都能被唤醒,因为多唤醒几个是没关系的。如果进程在临界区期间没有别的进程进入睡眠,则从临界区出来执行up()时就用不着去执行wake_up()了(当然,执行了也没什么影响,不过多余罢了)。而为什么要把wake_up()和count++分开呢,可以从上面的up1看出来,例如,进程2第一次得到机会运行时,本来这时唤醒它的进程还没执行up()的,但有可能其它进程执行了up()了,所以真有可能会发现count==1的情况,这时它就真的不用睡觉了,令count=sleepers=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 和SMP的情形了。

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的一个小小的变型而己了。

相关文章 热门文章
  • Linux启动 Sendmail速度慢的解决办法
  • Linux系统下防垃圾邮件基本功能
  • Linux启动sendmail速度慢的解决办法
  • Domino V8 在 UNIX/Linux 平台上的安装及其常见问题
  • IBM Lotus Domino,Linux,虚拟化,可伸缩性:不再是相互排斥的术语
  • 19.11 参 考 资 料
  • 19.10 课 后 练 习
  • 19.9 重 点 回 顾
  • 19.8.3 quota与目录转移
  • 19.8.2 关于备份
  • 19.8.1 问题检查
  • 19.7.8 其他设置技巧
  • linux的基本操作(上)
  • Linux系统下应用知识大荟萃
  • GNU GRUB启动管理器
  • 制作基于软盘的Linux系统
  • 网络配置文件快速解读
  • linux的基本操作(下)
  • 剖析Linux系统启动过程
  • DameWare让局域网管理不再繁琐
  • 在Redhat 9下实现双机热备和集群功能
  • LINUX守护进程介绍
  • Redhat advance server 2.1集群的安装与管理
  • Linux必须学会的60个命令-文件处理
  • 自由广告区
     
    最新软件下载
  • SharePoint Server 2010 部署文档
  • Exchange 2010 RTM升级至SP1 教程
  • Exchange 2010 OWA下RBAC实现的组功能...
  • Lync Server 2010 Standard Edition 标..
  • Lync Server 2010 Enterprise Edition...
  • Forefront Endpoint Protection 2010 ...
  • Lync Server 2010 Edge 服务器部署文档
  • 《Exchange 2003专家指南》
  • Mastering Hyper-V Deployment
  • Windows Server 2008 R2 Hyper-V
  • Microsoft Lync Server 2010 Unleashed
  • Windows Server 2008 R2 Unleashed
  • 今日邮件技术文章
  • 腾讯,在创新中演绎互联网“进化论”
  • 华科人 张小龙 (中国第二代程序员 QQ...
  • 微软推出新功能 提高Hotmail密码安全性
  • 快压技巧分享:秒传邮件超大附件
  • 不容忽视的邮件营销数据分析过程中的算..
  • 国内手机邮箱的现状与未来发展——访尚..
  • 易观数据:2011Q2中国手机邮箱市场收入..
  • 穿越时空的爱恋 QQ邮箱音视频及贺卡邮件
  • Hotmail新功能:“我的朋友可能被黑了”
  • 入侵邻居网络发骚扰邮件 美国男子被重..
  • 网易邮箱莫子睿:《非你莫属》招聘多过..
  • 中国电信推广189邮箱绿色账单
  • 最新专题
  • 鸟哥的Linux私房菜之Mail服务器
  • Exchange Server 2010技术专题
  • Windows 7 技术专题
  • Sendmail 邮件系统配置
  • 组建Exchange 2003邮件系统
  • Windows Server 2008 专题
  • ORF 反垃圾邮件系统
  • Exchange Server 2007 专题
  • ISA Server 2006 教程专题
  • Windows Vista 技术专题
  • “黑莓”(BlackBerry)专题
  • Apache James 专题
  • 分类导航
    邮件新闻资讯:
    IT业界 | 邮件服务器 | 邮件趣闻 | 移动电邮
    电子邮箱 | 反垃圾邮件|邮件客户端|网络安全
    行业数据 | 邮件人物 | 网站公告 | 行业法规
    网络技术:
    邮件原理 | 网络协议 | 网络管理 | 传输介质
    线路接入 | 路由接口 | 邮件存储 | 华为3Com
    CISCO技术 | 网络与服务器硬件
    操作系统:
    Windows 9X | Linux&Uinx | Windows NT
    Windows Vista | FreeBSD | 其它操作系统
    邮件服务器:
    程序与开发 | Exchange | Qmail | Postfix
    Sendmail | MDaemon | Domino | Foxmail
    KerioMail | JavaMail | Winwebmail |James
    Merak&VisNetic | CMailServer | WinMail
    金笛邮件系统 | 其它 |
    反垃圾邮件:
    综述| 客户端反垃圾邮件|服务器端反垃圾邮件
    邮件客户端软件:
    Outlook | Foxmail | DreamMail| KooMail
    The bat | 雷鸟 | Eudora |Becky! |Pegasus
    IncrediMail |其它
    电子邮箱: 个人邮箱 | 企业邮箱 |Gmail
    移动电子邮件:服务器 | 客户端 | 技术前沿
    邮件网络安全:
    软件漏洞 | 安全知识 | 病毒公告 |防火墙
    攻防技术 | 病毒查杀| ISA | 数字签名
    邮件营销:
    Email营销 | 网络营销 | 营销技巧 |营销案例
    邮件人才:招聘 | 职场 | 培训 | 指南 | 职场
    解决方案:
    邮件系统|反垃圾邮件 |安全 |移动电邮 |招标
    产品评测:
    邮件系统 |反垃圾邮件 |邮箱 |安全 |客户端
    广告联系 | 合作联系 | 关于我们 | 联系我们 | 繁體中文
    版权所有:邮件技术资讯网©2003-2010 www.5dmail.net, All Rights Reserved
    www.5Dmail.net Web Team   粤ICP备05009143号