资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第七章 内核中的同步,临界区和竞争状态,内核同步措施,生产者-消费者并发实例,内核多任务并发实例,什么是临界区,（,critical regions,）,?,就是访问和操作共享数据的代码段,这段代码必须被,原子地,执行,什么是竞争状态?,多个内核任务同时访问同一临界区,什么是同步?,避免并发和防止竞争状态称为,同步,（,synchronization,）,临界区和竞争状态,考虑一个非常简单的共享资源的例子：一个全局整型变量和一个简单的临界区，其中的操作仅仅是将整型变量的值增加,1,：,i+,该操作可以转化成下面三条机器指令序列：,(1),得到当前变量,i,的值并拷贝到一个寄存器中,(2),将寄存器中的值加,1,(3),把,i,的新值写回到内存中,临界区举例,内核任务,1,内核任务,2,获得,i(1) -,增加,i(1-2) -,写回,i(2) -,获得,i(2),增加,i(2-3),写回,i(3),临界区举例,内核任务,1,内核任务,2,获得,i(1) -,-,获得,i(1),增加,i(1-2) -,-,增加,i(1-2),写回,i(2),-,-,写回,i(2),可能的实际执行结果：,期望的结果,当共享资源是一个复杂的数据结构时，竞争状态往往会使该数据结构遭到破坏。,对于这种情况，锁机制可以避免竞争状态正如门锁和门一样,，,门后的房间可想象成一个临界区。,在一个指定时间内，房间里只能有个一个内核任务存在，当一个任务进入房间后，它会锁住身后的房门；当它结束对共享数据的操作后，就会走出房间，打开门锁。如果另一个任务在房门上锁时来了,那么它就必须等待房间内的任务出来并打开门锁后，才能进入房间。,共享队列和加锁,任何要访问队列的代码首先都需要占住相应的锁，这样该锁就能阻止来自其它内核任务的并发访问,：,任务 1,试图锁定队列,成功：获得锁,访问队列,为队列解除锁,任务,2,试图锁定队列,失败：等待,等待,等待,成功：获得锁,访问队列,为队列解除锁,共享队列和加锁,找出哪些数据需要保护是关键所在,内核任务的局部数据仅仅被它本身访问，显然不需要保护,如果数据只会被特定的进程访问，也不需加锁,大多数内核数据结构都需要加锁,：若有其它内核任务可以访问这些数据，那么就给这些数据加上某种形式的锁；若任何其它东西能看到它，那么就要锁住它,确定保护对象,死锁产生的条件：,有一个或多个并发执行的内核任务和一个或多个资源，每个任务都在等待其中的一个资源，但所有的资源都已经被占用。所有任务都在相互等待，,但它们永远不会释放已经占有的资源，于是任何任务都无法继续,典型的死锁：,四路交通堵塞,自死锁：,一个执行任务试图去获得一个自己已经持有的锁,死 锁,加锁的顺序是关键。使用嵌套的锁时必须保证以相同的顺序获取锁，这样可以阻止致命拥抱类型的死锁,防止发生饥饿,不要重复请求同一个锁。,越复杂的加锁方案越有可能造成死锁，因此设计应力求简单,死锁的避免,中断,中断几乎可以在任何时刻异步发生，也可能随时打断正在执行的代码。,内核抢占,若内核具有抢占性，内核中的任务就可能会被另一任务抢占,睡眠及与用户空间的同步,在内核执行的进程可能会睡眠，这将唤醒调度程序，导致调度一个新的用户进程执行,对称多处理,两个或多个处理器可以同时执行代码,并发执行的原因,为了避免并发，防止竞争。内核提供了一组同步方法来提供对共享数据的保护,原子操作,自旋锁,信号量,内核同步措施,原子操作可以保证指令以,原子的方式,被执行,两个原子操作绝对不可能并发地访问同一个变量,Linux内核提供了一个专门的,atomic_t类型（一个24位原子访问计数器）和,一些专门的函数,，,这些函数作用于,atomic_t类型的变量,。关于atomic_t类型的定义如下：,原子操作,typedef struct ,int counter;,atomic_t;,自旋锁是专为防止多处理器并发而引入的一种锁，它在内核中大量应用于中断处理等部分，而对于单处理器来说，可简单采用关闭中断的方式防止中断处理程序的并发执行,自旋锁最多只能被一个内核任务持有，若一个内核任务试图请求一个已被持有的自旋锁，那么这个任务就会一直进行忙循环，也就是旋转，等待锁重新可用,自旋锁,设计自旋锁的初衷是在短期间内进行轻量级的锁定。一个被持有的自旋锁使得请求它的任务在等待锁重新可用期间进行自旋，所以自旋锁不应该被持有时间过长,自旋锁在内核中主要用来防止多处理器中并发访问临界区，防止内核抢占造成的竞争,自旋锁不允许任务睡眠，持有自旋锁的任务睡眠会造成自死锁，因此自旋锁能够在中断上下文中使用,自旋锁,自旋锁的定义如下：,自旋锁,typedef struct raw_spinlock unsigned int slock; raw_spinlock_t;,typedefstruct,raw_spinlock_t raw_lock;,.,spinlockt;,使用自旋锁的基本形式如下：,DEFINE_SPINLOCK(mr_lock); /* 定义一个自旋锁 */,spin_lock(,/*临界区*/,spin_unlock(,Linux,中的信号量是一种睡眠锁。若有一个任务试图获得一个已被持有的信号量时，信号量会将其推入等待队列，然后让其睡眠。这时处理器获得自由而去执行其它代码。当持有信号量的进程将信号量释放后，在等待队列中的一个任务将被唤醒，从而便可以获得这个信号量,信号量具有睡眠特性，适用于锁会被长时间持有的情况，只能在进程上下文中使用,信号量,信号量的使用,信号量的定义,struct semaphore ,spinlock_t lock;,unsigned int count;,struct list_head wait_list;,static DECLARE_MUTEX(mr_sem);,*,声明并初始化互斥信号量,*/,if(!down_interruptible(&mr_sem),/*,信号被接收,信号量还未获取,*/,/*,临界区,*/,up(,信号量,信号量,的相关操作,down()操作,void down(struct semaphore *sem),unsigned long flags;,spin_lock_irqsave( /*加锁，使信号量的,操作在关闭中断的状态下进行，防止多处,理器并发操作造成错误*/,if (sem-count 0) /*,若,信号量可用，则将引用计数减1 */,sem-count-;,else /*如果无信号量可用，则调用_down()函数进入睡眠,等待状态 */,_down(sem);,spin_unlock_irqrestore( /* 对信号量的,操作解锁 */,信号量,的相关操作,down()操作中_down()函数调用_down_common(),这是,各种,down(),操作的统一函数。,释放信号量的,up(),操作：,void up(struct semaphore *sem),unsigned long flags;,spin_lock_irqsave( /* 对信号量操作,进行加锁 */,if list_empty(&sem-wait_list) /* 如果该信号量的等待,队列为空，则释放信号量 */,sem-count+;,else /* 否则唤醒该信号量的等待队列队头的进程 */,_up(sem);,spin_unlock_irqrestore( /* 对信号量,操作进行解锁 */,信号量,的操作函数列表,函数,描述,down(struct semaphore *);,down_interruptible(struct semaphore *);,down_killable(struct semaphore *);,down_trylock(struct semaphore *);,down_timeout(struct semaphore *, long,jiffies);,up(struct semaphore *);,获取信号量，如果不可获取，则进入不可中断睡眠状态（目前已经不建议使用）。,获取信号量，如果不可获取，则进入可中断睡眠状态。,获取信号量，如果不可获取，则进入可被致命信号中断的睡眠状态。,尝试获取信号量，如果不能获取，则立刻返回。,在给定时间（,jiffies,）内获取信号量，如果不能够获取，则返回。,释放信号量。,信号量与自旋锁的比较,需求,建议的加锁方法,低开销加锁,优先使用自旋锁,短期锁定,优先使用自旋锁,长期加锁,优先使用信号量,中断上下文中加锁,使用自旋锁,持有锁时需要睡眠、调度,使用信号量,生产者-消费者并发实例,问题描述,一个生产厂家、一个经销商、一个,仓库。 厂家生产一批产品并放在仓库里，,再通知经销商来批发。经销商卖完产品再,向厂家下订单，生产厂家才生产下一批产,品。,问题分析,生产厂家相当于“生产者”，经销商相,当于“消费者”，仓库则为“公共缓冲区”。该问,题属于单一生产者，单一消费者，单一缓冲,区。这是典型的进程同步问题。生产者和消费,者是不同的线程，“公共缓冲区”为临界区。同,一时刻，只能有一个线程访问临界区。,生产者-消费者并发实例,实现机制, 数据定义,#include ,#include ,#include ,#include ,#include ,#include ,#define PRODUCT_NUMS 10,static struct semaphore sem_producer;,static struct semaphore sem_consumer;,static char product12;,static atomic_t num;,static int producer(void *product);,static int consumer(void *product);,static int id = 1;,static int consume_num = 1;,生产者-消费者并发实例,实现机制, 生产者线程,static int producer(void *p),char *product=(char *)p;,int i;,atomic_inc(,printk(producer %d start. n, current-pid);,for(i = 0; i pid, product);,up(,printk(producer %d exit.n, current-pid);,return 0;,生产者-消费者并发实例,实现机制, 消费者线程,static int consumer(void *p),char *product=(char *)p;,printk(consumer %d start.n, current-pid);,for (;) ,msleep(100);,down_interruptible(,if(consume_num= PRODUCT_NUMS * atomic_read(&num),break;,printk(consumer %d consume %sn,current-pid, product);,consume_num+;,memset(product,0,12);,up(,printk(consumer %d exit.n, current-pid);,return 0;,生产者-消费者并发实例,实现机制, 模块的插入和删除,static int procon_init(void),printk(KERN_INFOshow producer and consumern);,init_MUTEX(,init_MUTEX_LOCKED(,atomic_set(,kernel_thread(producer,product,CLONE_KERNEL);,kernel_thread(consumer,product,CLONE_KERNEL);,return 0;,static void procon_exit(void),printk(KERN_INFOexit producer and consumern);,module_init(procon_init);,module_exit(procon_exit);,MODULE_LICENSE(GPL);,MODULE_DESCRIPTION(producer and consumer Module);,MODULE_ALIAS(a simplest module);,假设存在这样一个的内核共享资源链表。另外我们构造一个内核多任务访问链表的场景：内核线程向链表加入新节点；内核定时器定时删除,结点,；系统调用销毁链表。,上面三种内核任务并发执行时，有可能会破坏链表数据的完整性，所以我们必须对链表进行同步访问保护，以确保数据一致性。,内核多任务,并发控制实例,系统调用,：,是用户程序通过门机制来进入内核执行的内核例程，它运行在内核态，处于进程上下文中，可以认为是代表用户进程的内核任务,内核线程：,内核线程可以理解成在内核中运行的特殊进程，它有自己的,“,进程上下,文,”,。,定时器任务队列：,任务队列属于下半部，,在每次产生时钟节拍时得到处理。,内核任务及其之间的并发关系,系统调用和内核线程可能和各种内核任务并发执行，除了中断（定时器任务队列属于软中断范畴）抢占它产生并发外，它们还有可能自发性地主动睡眠（比如在一些阻塞性的操作中），于是放弃处理器，从而重新调度其它任务，所以系统调用和内核线程除与定时器任务队列发生竞争，也会与其他（包括自己）系统调用与内核线程发生竞争。,内核任务及其之间的并发关系,主要的共享资源是链表（,mine,）,操作它的内核任务有三个：一是,200,个内核线程（,sharelist,），它们负责从表头将新节点（,struct my_struct,）插入链表。二是定时器任务,(qt_task),，它负责每个时钟节拍时从链表头删除一个节点。三是系统调用,share_exit,，它负责销毁链表并卸载模块。,实现机制,内核线程,sharelist,：,该函数是作为内核线程由,keventd,调度执行的，作用是向链表中加入新节点,start_kthread ：,该函数用来构建内核线程,Sharelist,的封装函数kthread_launcher，并启动它,kthread_launcher ：,该函数作用仅仅是通过,kernel_thread方法,启动内核线程,sharelist,实现机制,qt_task ：,该函数删除链表节点，作为定时器任务运行,share_init ：,该函数是我们的模块注册函数，也是通过它启动定时器任务和内核线程,share_exit ：,这是模块注销函数，负责销毁链表,实现机制,share_exit,sharelist,链表,qt_task,kevent,start_kthread,进程上下文,中断上下文,进程上下文,down,up,上锁,添加节点,删除节点,实现机制,并发控制实例示意图,链表是内核开发中的常见数据组织形式，为了方便开发和统一结构，内核提供了一套接口来操作链表，我们用到的接口其主要功能为：,LIST_HEAD,：声明链表结构,list_add(),：添加节点到链表,list_del(),：删除节点,list_entry(),：遍历链表,任务队列结构为,struct tq_struct,kill_proc,，该函数在模块注销时被调用，其主要作用有两个：第一杀死我们生成的内核线程；第二告诉,keventd,回收相关子线程，以免产生,“,残疾,”,子线程序,关键代码解释,变量声明,实现,代码,#define NTHREADS 200 /* 线程数 */,struct my_struct ,struct list_head list;,int id;,int pid;,;,static struct work_struct queue; /* 定义工作队列 */,static struct timer_list mytimer; /* 定时器队列 */,static LIST_HEAD(mine); /* sharelist头 */,static unsigned int list_len = 0;,static DECLARE_MUTEX(sem); /* 内核线程进行同步的信号量 */,static spinlock_t my_lock = SPIN_LOCK_UNLOCKED; /* 保护对链表的操作 */,static atomic_t my_count = ATOMIC_INIT(0); /* 以原子方式进行追加 */,static long count = 0; /* 行计数器，每行打印4个信息 */,static int timer_over = 0; /* 定时器结束标志 */,static int sharelist(void *data); /*从共享链表增删节点的线程*/,static void kthread_launcher(struct work_struct *q); /*创建内核线程*/,static void start_kthread(void); /*调度内核线程 */,模块注册函数share_init,实现,代码,static int share_init(void),int i;,printk(KERN_INFOshare list entern);,INIT_WORK(/初始化工作队列,setup_timer( /设置定时器,add_timer( /添加定时器,for (i=0;iNTHREADS;i+) /再启动200个内核线程来添加节点,start_kthread();,return 0;,该函数是模块注册函数，也是通过它启动定时器任务和内核,线程。它首先初始化定时器任务队列，注册定时器任务qt_task；,然后依次启动200个内核线程start_kthread()。至此开始对链表,进行操作。,实现,代码,#definestatic int sharelist(void *data),struct my_struct *p;,if (count+ % 4 = 0),printk(n);,spin_lock( /* 添加锁，保护共享资源 */,if (list_len id = atomic_read( /* 原子变量操作 */,atomic_inc(,p-pid = current-pid;,list_add( /* 向队列中添加新节点 */,list_len+;,printk(THREAD ADD:%-5dt, p-id);, else /* 队列超过定长则删除节点 */,struct my_struct *my = NULL;,my = list_entry(mine.prev, struct my_struct, list);,list_del(mine.prev); /* 从队列尾部删除节点 */,list_len-;,printk(THREAD DEL:%-5dt, my-id);,kfree(my);,spin_unlock(,return 0;,对共享链表操,作的内核线程,share_list,实现,代码,通过,kernel_thread,方法启动,内核线程,sharelist,void kthread_launcher(struct work_struct *q),/*创建内核线程*,/,kernel_thread(sharelist, NULL, CLONE_KERNEL | SIGCHLD);,up(,调度内核线程的,start_kthread,static void start_kthread(void),down(,schedule_work(/*调度工作队列*/,实现,代码,删除结点的定时器任务qt_task,void qt_task(unsigned long data),if (!list_empty(&mine) ,struct my_struct *i;,if (count+ % 4 = 0),printk(n);,/* 取下一个节点 */,i = list_entry(mine.next, struct my_struct, list);,list_del(mine.next); /* 删除节点 */,list_len-;,printk(TIMER DEL:%-5dt, i-id);,kfree(i);,mod_timer( /*修改定时器时间*/,实现,代码,模块退出函数share_exit,static void_exit share_exit(void),struct list_head *n, *p = NULL;,struct my_struct *my = NULL;,printk(nshare list exitn);,del_timer(,spin_lock( /* 上锁，以保护临界区 */,list_for_each_safe(p, n, &mine) /* 删除所有节点，销毁链表 */,if (count+ % 4 = 0),printk(n);,my = list_entry(p, struct my_struct, list); /* 取下一个节点 */,list_del(p);,printk(SYSCALL DEL: %dt, my-id);,kfree(my);,spin_unlock( /* 开锁 */,printk(KERN_INFOOver n);,对该模块的实际操作步骤如下：,m,ake,编译模块,i,ns,mod sharelist.o,加载模块,r,m,mod sharelist,卸载模块,d,m,esg,观察结果,一步一步,“内核之旅,”网站,
展开阅读全文