并发编程

Nov 22 2016 Linux

前言

今天来简单地学习Linux中的编发编程,介绍一下互斥和线程同步。

stash.c的问题

竞争条件

临界区

互斥

在某些提供test-and-set指令的机器可以用于解决临界区互斥的问题,这个指令能检查并设置内存的值,而不会被打断。工作原理大致是这样的:

1
2
3
4
5
boolean TestAndSet(boolean *lock){
boolean rv = *lock;
*lock = TRUE;
return rv;
}

注意:这个函数中三条指令是原子执行的,也就是说不会被打断。

使用方法:

1
2
3
4
5
6
7
8
9
10
11
boolean lock = false;

while(TestAndSet(&lock)){
;// 啥也不干
}

临界区;

lock = false;

其他代码;

信号量

信号量数据结构

如上图所示,对于一个互斥的信号量(比如互斥锁),count属性会被初始化为1,代表最多一个任务可以获得这个信号量。

当一个任务调用down(&sem)方法——这个方法会对减少count值,如果新的count值大于0(获得信号量)则会立即返回执行接下来的代码,否则,这个任务会被进入睡眠,即放到信号量的task_list等待队列。之后,当一个已经获得信号量的任务完成之后,调用up(&sem)方法,count值就会增加,等待队列中的所有任务都会被唤醒。

从上面的描述可知,使用信号量不仅可以解决互斥的问题,还可以解决生产者-消费者同步的问题。

使用信号量解决互斥的伪代码:

1
2
3
4
5
6
7
sem->count=1;

down(&sem);

临界区

up(&sem);

使用信号量解决生产者-消费者同步问题伪代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
sem_lock->count = 1; // 用于访问队列时互斥
sem_empty->count = 5; // 生产者信号量,大于0可生产
sem_full->count = 0; // 消费者信号量,大于0可消费

生产者:
while(true){
down(&sem_empty); // 如果队列中没有空余的位置,生产者只能等待

down(&sem_lock); // 加锁,准备操作队列

把新产生的内容加入队列;

up(&sem_lock); // 释放锁

up(&sem_full); // 通知消费者有内容可以消费了
}

消费者:
while(true){
down(&sem_full); // 如果队列中没有内容,消费者只能等待

down(&sem_lock); // 加锁,准备操作队列

将队列中的内容取出进行处理;

up(&sem_lock); // 释放锁

up(&sem_empty); // 通知生产者进行生产
}

newstash.c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include <linux/module.h>	// for init_module() 
#include <linux/fs.h> // for register_chrdev()
#include <linux/sched.h> // for wait_event_interruptible()
#include <asm/uaccess.h> // for get_user(), put_user()

#define RINGSIZE 512

char modname[] = "stash"; // keeps former pseudo-file name
int my_major = 40; // and same device-file major ID
unsigned char ring[ RINGSIZE ];
volatile int head = 0, tail = 0;
wait_queue_head_t wq_rd, wq_wr;

// here two semaphores are added
struct semaphore sem_wr, sem_rd;


int my_open( struct inode *inode, struct file *file )
{
// if task wants to write, obtain 'write' semaphore (or sleep)
if ( file->f_mode & FMODE_WRITE ) down_interruptible( &sem_wr );

// if task wants to read, obtain 'read' semaphore (or sleep)
if ( file->f_mode & FMODE_READ ) down_interruptible( &sem_rd );

return 0; // SUCCESS
}


int my_release( struct inode *inode, struct file *file )
{
// if task was a writer, then release the 'write' semaphore
if ( file->f_mode & FMODE_WRITE ) up( &sem_wr );

// if task was a reader, then release the 'read' semaphore
if ( file->f_mode & FMODE_READ ) up( &sem_rd );

return 0; // SUCCESS
}


ssize_t
my_read( struct file *file, char *buf, size_t count, loff_t *pos )
{
// sleep if necessary until the ringbuffer has some data
if ( wait_event_interruptible( wq_rd, head != tail ) )
return -ERESTARTSYS;

// remove a byte of data from our ringbuffer
if ( put_user( ring[ head ], buf ) ) return -EFAULT;
head = ( 1 + head ) % RINGSIZE;

// now awaken any sleeping writers
wake_up_interruptible( &wq_wr );
return 1;
}

ssize_t
my_write( struct file *file, const char *buf, size_t count, loff_t *pos )
{
// sleep if necessary until the ringbuffer has room for more data
int next = (1 + tail) % RINGSIZE;
if ( wait_event_interruptible( wq_wr, next != head ) )
return -ERESTARTSYS;

// insert a new byte of data into our ringbuffer
if ( get_user( ring[ tail ], buf ) ) return -EFAULT;
tail = (1 + tail) % RINGSIZE;

// now awaken any sleeping readers
wake_up_interruptible( &wq_rd );
return 1;
}

static struct file_operations
my_fops = {
owner: THIS_MODULE,
write: my_write,
read: my_read,
open: my_open,
release: my_release,
};

int __init my_init( void )
{
printk( "<1>\nInstalling \'%s\' module ", modname );
printk( "(major=%d) \n", my_major );

// initialize our semaphores and wait-queue structures
init_MUTEX( &sem_wr );
init_MUTEX( &sem_rd );
init_waitqueue_head( &wq_rd );
init_waitqueue_head( &wq_wr );

// register this device-driver with the kernel
return register_chrdev( my_major, modname, &my_fops );
}

void __exit my_exit( void )
{
printk( "<1>Removing \'%s\' module\n", modname );

// unregister this device-driver
unregister_chrdev( my_major, modname );
}

module_init(my_init);
module_exit(my_exit);
MODULE_LICENSE("GPL");

总结

本文不但学习了test-and-set指令实现互斥,还学习了更加强大的信号量来解决生产者-消费者同步问题。

并发编程