关键词:
相关概念
竞争条件
多个执行线程(进程/线程/中断处理程序)并发(并行)访问共享资源,因为执行顺序不一样造成结果不一样的情况,称为竞争条件(race condition)
举例说明
#include<thread>
using namespace std;
int i = 0;
void thread1(){
//for(int x=0;x<100000;x++)
i++;
}
void thread2(){
//for(int x=0;x<100000;x++)
i++;
}
int main(){
std::thread t1(thread1);
std::thread t2(thread1);
t1.join();
t2.join();
printf(" i = %d\n",i);
}
t1,t2两个线程并发执行时有可能发生竞争条件(当然这个程序发生竞争条件概率很低,但如果你把注释去掉,竞争条件就非常容易发生了)
i++;这条语句一般需要3条机器指令
MOV EAX,i
INC EAX
MOV EAX,i
如果按照如下顺序执行,是没有有问题的,打印出的i是2
thread 1 | thread 2 |
---|---|
MOV EAX,i(i=0) | |
INC EAX | |
MOV EAX,i(i=1) | |
MOV EAX,i(i=1) | |
INC EAX | |
MOV EAX,i(i=2) |
但是两个线程很可能按照如下顺序执行,此时就会出现竞争条件,打印出的i是1
thread 1 | thread 2 |
---|---|
MOV EAX,i (i=0) | |
INC EAX | |
MOV EAX,i (i=0) | |
MOV EAX,i (i=1) | |
INC EAX | |
MOV EAX,i (i=1) |
临界区(critical section)是指 访问和操作共享资源的代码段,例子里就是两个线程的i++语句
为避免竞争条件,临界区必须原子地执行,执行结束前不能被打断。一般会对临界区加锁,使用信号量,条件变量等,例子中的简单操作也可以使用原子变量。
原子性的理解
一般书上对原子性的解释为执行结束前不能被打断。这句话如何理解呢,我个人的理解是:
- 原子变量这种,使用锁总线的方式来实现,相关的若干条指令是连续执行的;
- 使用锁(自旋锁/睡眠锁),信号量,条件变量/完成变量这些,并不是说临界区的所有指令连续执行,可能在临界区执行到了一半,因为调度抢占或者中断,CPU不继续在临界区内执行,也就是执行被打断了。
- 但是这种情况依旧能保证避免竞争条件,原因在于,如果被打断的进程之外的进程被调度,该进程要想访问临界区的时候,被锁或者信号量等“拦住”,是进入不了临界区的,直到原被打断的临界区执行完毕,释放锁/信号量等,其他进程才有可能进入临界区。
造成并发的原因
- 中断:中断几乎可以在任何时刻异步发生,也就可能随时打断当前正在执行的代码
- 软中断和tasklet:内核能在任何时候唤醒或调度软中断和tasklet,打断当前正在执行的代码
- 内核抢占:Linux内核具有抢占性,所以内核的任务可能被另一任务抢占
- 睡眠及用户空间的同步:在内核执行的进程可能会睡眠,会唤醒调度程
序,从而调度一个新的用户进程执行 - SMP,两个或多个处理器可以同时执行代码
内核中的同步手段
加锁
为了避免竞争条件,内核提供了几个机制用于同步,基本思路就是加锁,临界区互斥访问,信号量也可以支持多于一个线程并发访问。
锁的争用
指所被占用时,有其他线程试图获得该锁。锁的争用程度越高,系统性能也就会越低(加锁会降低系统性能,比如睡眠锁,自旋锁),但是为保证正确性有必须使用。要降低锁的争用,加锁粒度要尽可能小,也就是临界区要尽量小。
几种同步方法简介
同步方法 | 主要接口 | 备注 |
---|---|---|
原子整数(32bit)操作 | atomic_t v;/*定义 v*/ | |
atomic_t u = ATOMIC_INIT(0);/*定义u,初始化为0*/ | ||
atomic_set(&v, 4);/* v=4 */ | ||
atomic_add(2, &v);/* v=v+2 */ | ||
atomic_inc(&v);/* v=v+1 */ | ||
原子整数(64bit)操作 | atomic64_t v; | |
原子位操作 | unsigned long word = 0; | 对普通的指针进行操作 |
set_bit(0,&word); //第0位被设置 | __set_bit形式为非原子操作 | |
set_bit(1,&word); //第1位被设置 | 如果不需要原子操作,非原子操作更快一些 | |
printk("%ul\n",word);//打印3 | 《linux内核设计与实现》P147 | |
clear_bit(1,&word);//清空第1位 | ||
change_bit(0,&word);//反转第0位 | ||
自旋锁 | DEFINE_SPINLOCK(mr_lock); | 自旋锁在同一时刻只能由一个线程位于临界区 |
spin_lock(&mr_lock); | 可为多处理器提供并发访问所需的保护机制 | |
/*临界区*/ | 单处理机,当作一个内核抢占是否开启的开关,如果禁止内核抢占,编译时自旋锁会被完全剔除内核 | |
spin_unlock(&mr_lock); | 自旋锁不可递归 | |
自旋锁和下半部 | 下半部和进程上下文共享数据/下半部和中断处理程序共享数据,需要加锁 | 下半部可以抢占进程上下文,中断处理程序可以抢占下半部 |
读写自旋锁 | DEFINE_RWLOCK(mr_rwlock); | |
read_lock(&mr_rwlock); | 所有读者共享 | |
/*临界区(只读)*/ | ||
read_unlock(&mr_rwlock); | ||
write_lock(&mr_rwlock); | 写者相互排斥,写者和读者互斥 | |
/*临界区(读写)*/ | ||
write_unlock(&mr_rwlock); | ||
信号量 | struct semophore name; | 争用的线程会睡眠,因此适合锁会被长时间占有的情况 |
sema_init(&name, count); | 在进程上下文中使用 | |
static DECLARE_MUTEX(name); | ||
init_MUTEX(sem) | 动态初始化互斥信号量 | |
static DECLARE_MUTEX(mr_sem); | ||
if(down_interruptible(&mr_sem)){ /*信号被接收,信号量还未获取*/ } | ||
/*临界区*/ | ||
up(&mr_sem);//释放给定的信号量 | ||
读写信号量 | static DECLARE_RWSEM(mr_rwsem); | 静态定义 |
init_rwsem(struct rw_semaphore *sem); | 动态初始化 | |
down_read(&mr_rwsem); | ||
/*临界区(只读)*/ | ||
up_read(&mr_rwsem); | ||
down_write(&mr_rwsem); | ||
/*临界区(读写)*/ | ||
up_write(&mr_rwsem); | ||
互斥体 | DEFINE_MUTEX(name); | 用于处理互斥的睡眠锁 |
mutex_init(&mutex); | 动态初始化 | |
mutex_lock(&mutex) | 不能递归上锁和解锁 | |
/*临界区*/ | 不能再中断或下半部执行 | |
mutex_unlock(&mutex) | ||
完成变量 | DECLARE_COMPLETION(mr_comp) | 等待,知道任务完成,发出信号 |
init_completion(); | 动态创建 | |
等待任务调用 | wait_for_completion(); | |
产生事件的任务调用 | complete();//发送信号唤醒特定事件 |
关于大内核锁BLK,顺序锁的内容见《Linux内核设计与实现》P160
禁止抢占
内核抢占代码使用自旋锁作为非抢占区域的标记
可以禁用抢占
更简洁的解决每个处理器上的数据访问问题,get_cpu()获取处理器编号,返回处理器编号前会先关闭内核抢占
int cpu;
cpu = get_cpu;//禁止内核抢占,将CPU设置为当前cpu
/*对每一个cpu的数据进行操作*
/*在给予内核抢占性,“cpu”可改变,所以不再有效*/
put_up();
顺序和屏障
保证顺序的原因
- 多处理器之间,硬件设备的同步问题时,需要在程序代码中按照指定的顺序读取内存和写入内存。
- 和硬件交互时,常需要保证给定读操作在其他读/写操作之前
- 多处理器上,可能需要按照写数据的顺序读数据。
为了效率,编译器(编译优化)和处理器(乱序执行)可能对读和写重新排序。
- 所有可能重新排序读写的cpu提供机器指令,确保按顺序执行。
- 也可以指示编译器不进行给定点周围的指令序列进行重新排序。
e.g.
//可能重新排序
a=1;
b=2;
//不可能重新排序
a=1;
b=a;
举例解释保证顺序的原因
a=1,b=2
线程1 | 线程2 |
---|---|
a=3; | – |
mb(); | – |
b=4; | c=b; |
– | rmb(); |
– | d=a; |
如果没有内存屏障,某些处理器上,可能c接受了b的新值4,d接受了a原来的值1
几个方法
完整接口列表
截图自《Linux内核设计与实现》第10章
《linux内核设计与实现》读书笔记linux内核简介
Unix的历史①Unix诞生于1969年,至今仍然被认为是现存操作系统中最强大和最优秀的系统。②Unix起源于一个失败的多用户操作系统Multics,Multics终止而Unix萌生。③1973年整个Unix操作系统用C语言进行了重写,为后面各种... 查看详情
《linux内核设计与实现》读书笔记-内核同步方法(代码片段)
...3.读写自旋锁4.信号量5.读写信号量6.互斥体7.完成变量8.大内核锁9.顺序锁10.禁止抢占11.顺序和屏障12.总结内核中提供了多种方法来防止竞争条件,理解了这些方法的使用场景有助于我们在编写内核代码 查看详情
读薄《linux内核设计与实现》-中断与同步
这篇文章是《读薄「Linux内核设计与实现」》系列文章的第IV篇,本文主要讲了以下问题:中断和中断处理程序的概念与实现原理、Linux中的下半部以及内核同步方法。0x00中断和中断处理程序I中断中断是一种特殊的电信号,由硬... 查看详情
linux内核设计与实现的目录
参考技术A译者序序言前言作者简介第1章 Linux内核简介11.1 Unix的历史11.2 追寻Linus足迹:Linux简介21.3 操作系统和内核简介31.4 Linux内核和传统Unix内核的比较51.5 Linux内核版本71.6 Linux内核开发者社区81.7 小结8第2章 从内... 查看详情
《linux内核设计与实现》读书笔记-内核同步方法(代码片段)
...3.读写自旋锁4.信号量5.读写信号量6.互斥体7.完成变量8.大内核锁9.顺序锁10.禁止抢占11.顺序和屏障12.总结内核中提供了多种方法来防止竞争条件,理解了这些方法的使用场景有助于我们在编写内核代码时选用合适的同步方法... 查看详情
《linux内核设计与实现》读书笔记从内核出发(代码片段)
内核源码获取①可以直接登录linux内核官方网站http://www.kernel.org,可以随时获取当前版本的linux源代码②也可以使用git工具从远程仓库下载,地址:LinuxKernel:Linux内核源码镜像如:gitclonegit@gitee.com:mirrors/linux_old1.git这... 查看详情
《linux内核设计与实现》笔记——vfs
关于VFS有一篇很好的博客http://www.ibm.com/developerworks/cn/linux/l-vfs/建议先阅读本文为基础,然后继续阅读该文章。VFS,虚拟文件系统,为用户提供了文件和文件系统相关的接口。这些接口可以跨越各种文件系统和不同介质执行。VFS... 查看详情
《linux内核设计与实现》知识整合与讲解-第一章
Linux内核简介第一章主要对Linux的内核进行一个大致的介绍,让大家对Linux的内核有一个比较全面的印象。众所周知Linux起源于unix系统,它们之间有着千丝万缕的联系,伟大的linux之父linus不满于当时unix对于源码更改的限制,花费... 查看详情
《内核设计与实现》读书笔记-进程管理
...程序以及相关的资源的总称。线程是进程中活动的对象。内核调度的对象是线程,而不是进程。进程和线程的管理操作(比如创建和销毁)都是由内核来实现的。Linux中的进程于Windows相比是很轻量级的,而且不严格区分进程和线... 查看详情
《linux内核设计与实现》学习笔记——中断中断处理程序
...线,每个irq线关联一个数值。中断处理程序响应中断时,内核会执行一个函数,中断处理程序/中断服务例程ISR,一个设备的中断处理程序是他的设备驱动的一部分。IO资源包括:中断,I/O端口,共享RAM,DMA。驱动程序需要管理注... 查看详情
《linux内核设计与实现》读书笔记linux进程管理(代码片段)
...于执行期的程序,通常进程还包含挂起的信号,内核内部数据,处理器状态,一个或多个具有内存映射的内存地址空间及一个或多个执行线程,还包含存放全局变量的数据段等。②线程是进程中活动的对象ÿ... 查看详情
linux内核模块简介
1.宏内核与微内核内核(Kernel)在计算机科学中是操作系统最基本的部分,主要负责管理系统资源。中文版维基百科上将内核分为四大类:单内核(宏内核);微内核;混合内核;外内核。混合内核实质上也是微内核,而外内核... 查看详情
《linux内核设计与实现》学习笔记——i/o调度算法
I/O调度子系统用于调度来自多个进程对块设备的I/O请求。电梯调度首先,如果队列中已存在一个对相邻磁盘扇区操作的请求,那么新请求将和这个已经存在的请求合并为一个请求。2.如果队列中存在一个驻留时间过长的请求,那... 查看详情
《linux内核设计与实现》读书笔记linux进程管理(代码片段)
...于执行期的程序,通常进程还包含挂起的信号,内核内部数据,处理器状态,一个或多个具有内存映射的内存地址空间及一个或多个执行线程,还包含存放全局变量的数据段等。②线程是进程中活动的对象ÿ... 查看详情
《linux设计与实现》笔记——系统调用工作原理添加系统调用的过程
系统调用的意义为了和用户空间上的进程进行交互,内核提供的提供的一组接口。应用程序通过这组接口访问硬件和其他操作系统资源。完成对硬件和资源访问的控制。安全、可靠,多任务、虚拟必须硬件设备的抽象(提供设备... 查看详情
linux用户与内核空间交互—ioctl(代码片段)
...法笔记与总结二、ioctl三、实战1、头文件2、应用程序3、内核程序4、程序输出简介用户空间与内核的交互方式,使用copy_from_user(),copy_to_user().除了这两种交互方式,内核还提供了其他高级的方式,对于写驱动来说很重... 查看详情
linux内核的代码仓库管理与开发流程简介
Linux内核的代码仓库管理与开发流程简介-泰晓科技(tinylab.org) 查看详情
细读《深入理解android内核设计思想》进程间通信与同步机制(代码片段)
对冗余挑拣重点,对重点深入补充,输出结构清晰的精简版1.进程间通信的经典实现共享内存管道UNIXDomainSocketRemoteProcedureCalls2.同步机制的经典实现信号量Mutex管程LinuxFutex3.Android中的进程间同步机制进程间同步Mutex条件判... 查看详情