Chinaunix首页 | 论坛 | 博客
  • 博客访问: 659445
  • 博文数量: 372
  • 博客积分: 10063
  • 博客等级: 中将
  • 技术积分: 4220
  • 用 户 组: 普通用户
  • 注册时间: 2012-02-24 11:36
文章分类

全部博文(372)

文章存档

2012年(372)

分类: 虚拟化

2012-03-23 20:38:43

 Linux内核同步控制方法有很多,信号量、锁、原子量、RCU等等,不同的实现方法应用于不同的环境来提高操作系统效率。首先,看看我们最熟悉的两种机制——信号量、锁。

一、信号量

首先还是看看内核中是怎么实现的,内核中用struct semaphore数据结构表示信号量(中):

View Code
1 struct semaphore {
2 spinlock_t lock;
3 unsigned int count;
4 struct list_head wait_list;
5 };

其中lock为自旋锁,放到这里是为了保护count的原子增减,无符号数count为我们竞争的信号量(PV操作的核心),wait_list为等待此信号量的进程链表。

初始化:

对于这一类工具类使用较多的机制,包括用于同步互斥的信号量、锁、completion,用于进程等待的等待队列、用于Per-CPU的变量等等,内核都提供了两种初始化方法,静态与动态方式。

1) 静态初始化,实现代码如下:

View Code
1 #define __SEMAPHORE_INITIALIZER(name, n) \
2 { \
3 .lock = __SPIN_LOCK_UNLOCKED((name).lock), \
4 .count = n, \
5 .wait_list = LIST_HEAD_INIT((name).wait_list), \
6 }
7
8 #define DECLARE_MUTEX(name) \
9 struct semaphore name = __SEMAPHORE_INITIALIZER(name, 1)

可以看到,这种初始化使我们在编程的时候直接用一条语句DECLARE_MUTEX(name);就可以完成申明与初始化,另一种下面要说的动态初始化方式申请与初始化分离。

2) 我们看到,静态初始化时信号量的count值初始化为1,当我们需要初始化为0时需要用动态初始化方法。

View Code
1 #define init_MUTEX(sem) sema_init(sem, 1)
2 #define init_MUTEX_LOCKED(sem) sema_init(sem, 0)
3
4 static inline void sema_init(struct semaphore *sem, int val)
5 {
6 static struct lock_class_key __key;
7 *sem = (struct semaphore) __SEMAPHORE_INITIALIZER(*sem, val);
8 lockdep_init_map(&sem->lock.dep_map, "semaphore->lock", &__key, 0);
9 }

操作:

获取信号量

View Code
1 /*获取信号量*/
2 void down(struct semaphore *sem)
3 {
4 unsigned long flags;
5
6 spin_lock_irqsave(&sem->lock, flags);
7 if (likely(sem->count > 0))
8 sem->count--;
9 else
10 __down(sem);
11 spin_unlock_irqrestore(&sem->lock, flags);
12 }

__down(sem)最终由下面函数实现

View Code
1 static inline int __sched __down_common(struct semaphore *sem, long state,
2 long timeout)
3 {
4 struct task_struct *task = current;
5 struct semaphore_waiter waiter;
6
7 list_add_tail(&waiter.list, &sem->wait_list);
8 waiter.task = task;
9 waiter.up = 0;
10
11 for (;;) {
12 if (signal_pending_state(state, task))
13 goto interrupted;
14 if (timeout <= 0)
15 goto timed_out;
16 __set_task_state(task, state);
17 spin_unlock_irq(&sem->lock);
18 timeout = schedule_timeout(timeout);
19 spin_lock_irq(&sem->lock);
20 if (waiter.up)
21 return 0;
22 }
23
24 timed_out:
25 list_del(&waiter.list);
26 return -ETIME;
27
28 interrupted:
29 list_del(&waiter.list);
30 return -EINTR;
31 }

释放信号量

View Code
1 void up(struct semaphore *sem)
2 {
3 unsigned long flags;
4
5 spin_lock_irqsave(&sem->lock, flags);
6 if (likely(list_empty(&sem->wait_list)))
7 sem->count++;
8 else
9 __up(sem);
10 spin_unlock_irqrestore(&sem->lock, flags);
11 }
View Code
1 static noinline void __sched __up(struct semaphore *sem)
2 {
3 struct semaphore_waiter *waiter = list_first_entry(&sem->wait_list,
4 struct semaphore_waiter, list);
5 list_del(&waiter->list);
6 waiter->up = 1;
7 wake_up_process(waiter->task);
8 }

从上面代码可以看出,信号量的获取和释放很简单,不外乎修改count值、加入或移除等待队列元素,其中count值的修改需要自旋锁的支持。还有几个down和up类函数,实现类似,使用时可以看看源码不同之处。

运用:

用信号量我们实现两个线程的同步,我们用kernel_thread创建两个线程,对变量num的值进行同步访问,代码如下,文件为semaphore.c

View Code
1 #include
2 #include
3 #include
4
5 #include
6 #include
7 #define N 15
8
9 MODULE_LICENSE("GPL");
10
11 static unsigned count=0,num=0;
12 struct semaphore sem_2;
13 DECLARE_MUTEX(sem_1);/*init 1*/
14
15
16 int ThreadFunc1(void *context)
17 {
18 char *tmp=(char*)context;
19 while(num20 down(&sem_1);
21 printk("<2>" "%s\tcount:%d\n",tmp,count++);
22 num++;
23 up(&sem_2);
24 }
25 return 0;
26 }
27 int ThreadFunc2(void *context)
28 {
29 char *tmp=(char*)context;
30 while(num31 down(&sem_2);
32 printk("<2>" "%s\tcount:%d\n",tmp,count--);
33 num++;
34 up(&sem_1);
35 }
36 return 0;
37 }
38
39 static __init int semaphore_init(void)
40 {
41 char *ch1="this is first thread!";
42 char *ch2="this is second thread!";
43 init_MUTEX_LOCKED(&sem_2);/*init 0*/
44
45 kernel_thread(ThreadFunc1,ch1,CLONE_KERNEL);
46 kernel_thread(ThreadFunc2,ch2,CLONE_KERNEL);
47
48 return 0;
49 }
50
51 static void semaphore_exit(void)
52 {
53 }
54
55 module_init(semaphore_init);
56 module_exit(semaphore_exit);
57
58 MODULE_AUTHOR("Mike Feng");

实现结果如下。

可以看到线程1和线程2交替运行,实现了同步。

读、写信号量:

类似操作系统中学习的读者、写者问题,内核中,许多任务可以划分为两种不同的工作类型:一些任务只需要读取受保护的数据结构,而其他的则必须做出修改。循序多个并发的读者是可能的,只要他们之中没有哪个要做出修改。Linux内核为这种情形提供了一种特殊的信号量类型——读、写信号量。struct rw_semaphore作为其数据结构,初始化和信号量类似,down_read、up_read等类函数实现信号量控制,这些函数实现比较复杂,用到了读写锁(将在后面分析),有兴趣可以看看,。我们运用读、写信号实现哪个古老的读者、写者同步问题:

文件down_read.c

View Code
1 #include
2 #include
3 #include
4
5 #include
6 #include
7 #include
8
9 MODULE_LICENSE("GPL");
10
11 static int count=0,num=0,readcount=0,writer=0;
12 struct rw_semaphore rw_write;
13 struct rw_semaphore rw_read;
14 struct semaphore sm_1;
15
16
17 int ThreadRead(void *context)
18 {
19 down_read(&rw_write);
20 down(&sm_1);
21 count++;
22 readcount++;
23 up(&sm_1);
24
25 printk("<2>" "Read Thread %d\tcount:%d\n",readcount,count);
26 msleep(10);
27 printk("<2>" "Read Thread Over!\n",readcount);
28
29 up_read(&rw_write);
30
31 return 0;
32 }
33 int ThreadWrite(void *context)
34 {
35 down_write(&rw_write);
36 writer++;
37
38 printk("<2>" "Write Thread %d\tcount:%d\n",writer,--count);
39 msleep(10);
40 printk("<2>" "Write Thread %d Over!\n",writer);
41
42 up_write(&rw_write);
43
44 return count;
45 }
46
47 static __init int rwsem_init(void)
48 {
49 static int i,iread=0,iwrite=0;
50 init_rwsem(&rw_read);
51 init_rwsem(&rw_write);
52 init_MUTEX(&sm_1);
53
54 for(i=0;i<2;i++){
55 kernel_thread(ThreadWrite,&i,CLONE_KERNEL);
56 iwrite++;
57 }
58
59 for(i=0;i<2;i++){
60 kernel_thread(ThreadRead,&i,CLONE_KERNEL);
61 iread++;
62 }
63 for(i=2;i<5;i++){
64 kernel_thread(ThreadRead,&i,CLONE_KERNEL);
65 iread++;
66 }
67 for(i=2;i<5;i++){
68 kernel_thread(ThreadWrite,&i,CLONE_KERNEL);
69 iwrite++;
70 }
71
72 return 0;
73 }
74
75 static void rwsem_exit(void)
76 {
77 }
78
79 module_init(rwsem_init);
80 module_exit(rwsem_exit);
81
82 MODULE_AUTHOR("Mike Feng");

实验结果:

从代码上看,实现起来很简单。

二、自旋锁

读写信号量基于自旋锁实现。内核中为如下结构:

View Code
1 typedef struct {
2 raw_spinlock_t raw_lock;
3 #ifdef CONFIG_GENERIC_LOCKBREAK
4 unsigned int break_lock;
5 #endif
6 #ifdef CONFIG_DEBUG_SPINLOCK
7 unsigned int magic, owner_cpu;
8 void *owner;
9 #endif
10 #ifdef CONFIG_DEBUG_LOCK_ALLOC
11 struct lockdep_map dep_map;
12 #endif
13 } spinlock_t;

其中raw_lock为实现的原子量控制。下面我们就信号量和自旋锁实现我们上面用读写信号量实现的读者、写者问题:spinlock.c文件

View Code
1 #include
2 #include
3 #include
4
5 #include
6 #include
7 #include
8
9 MODULE_LICENSE("GPL");
10
11 static int count=0,num=0,readcount=0,writer=0,writecount=0;
12 struct semaphore sem_w,sem_r;
13
14 spinlock_t lock1=SPIN_LOCK_UNLOCKED;
15
16 int ThreadRead(void *context)
17 {
18 down(&sem_r);
19 spin_lock(&lock1);
20 readcount++;
21 if(readcount==1)
22 down(&sem_w);
23 spin_unlock(&lock1);
24 up(&sem_r);
25
26 printk("<2>" "Reader %d is reading!\n",readcount);
27 msleep(10);
28 printk("<2>" "Reader is over!\n");
29
30 spin_lock(&lock1);
31 readcount--;
32 if(readcount==0)
33 up(&sem_w);
34 spin_unlock(&lock1);
35
36 return count;
37 }
38
39 int ThreadWrite(void *context)
40 {
41 spin_lock(&lock1);
42 writecount++;
43 if(writecount==1)
44 down(&sem_r);
45 spin_unlock(&lock1);
46
47 down(&sem_w);
48 writer++;
49 printk("<2>" "Writer %d is writting!\n",writer);
50 msleep(10);
51 printk("<2>" "Writer %d is over!\n",writer);
52 up(&sem_w);
53
54 spin_lock(&lock1);
55 writecount--;
56 if(writecount==0)
57 up(&sem_r);
58 spin_unlock(&lock1);
59
60 return count;
61 }
62
63 static __init int rwsem_init(void)
64 {
65 static int i;
66 init_MUTEX(&sem_r);
67 init_MUTEX(&sem_w);
68 for(i=0;i<2;i++){
69 kernel_thread(ThreadWrite,&i,CLONE_VM);
70 }
71
72 for(i=0;i<2;i++){
73 kernel_thread(ThreadRead,&i,CLONE_KERNEL);
74 }
75 for(i=2;i<5;i++){
76 kernel_thread(ThreadRead,&i,CLONE_KERNEL);
77 }
78 for(i=2;i<5;i++){
79 kernel_thread(ThreadWrite,&i,CLONE_KERNEL);
80 }
81
82 return 0;
83 }
84
85 static void rwsem_exit(void)
86 {
87
88 }
89
90 module_init(rwsem_init);
91 module_exit(rwsem_exit);
92
93 MODULE_AUTHOR("Mike Feng");

运行结果:

从结果上看,和我们上面的结果略有差别,因为我们这里实现的是写者优先算法。

读写锁:

读写信号量的实现是基于读写锁的。可以想到他们的应用都差不多。自旋锁、读写锁中不能有睡眠,我们就不做实验验证了,当你在锁之间添加msleep函数时,会造成系统崩溃。

顺序锁:

顺序锁和读写锁非常相似,只是他为写者赋予了较高的优先级:事实上,即使在读者正在读的时候也允许写者继续运行。这种策略的好处是写者永远不会等待(除非另外一个写者正在写),缺点是有些时候读者不得不反复读相同数据直到他获得有效的副本。

最后,为完整起见,附上代码的Makefile文件:

View Code
1 obj-m+=semaphore.o down_read.o spinlock.o
2 CURRENT:=$(shell pwd)
3 KERNEL_PATH:=/usr/src/kernels/$(shell uname -r)
4
5 all:
6 make -C $(KERNEL_PATH) M=$(CURRENT) modules
7 clean:
8 make -C $(KERNEL_PATH) M=$(CURRENT) clean
阅读(581) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~