并发编程
并行计算
基于分治原则的算法经常表现出高度的并行性,可通过使用并行或并发执行来提高计算速度。
顺序算法和并行算法
顺序算法
begin
step_1
step_2
...
step_n
end
//next step
并行算法
cobegin
task_1
task_2
...
task_n
coand
// next step
cobegin-coend块中,所有任务都是并行执行的。
并行性与并发性
理想情况下,并行算法中的所有任务都应该同时实时执行。但真正的并行执行只能在有多个处理组件的系统中实现,比如多处理器或多核系统。单cpu中,一次只能执行一个任务,并发性是通过多任务处理来实现的
线程原理
操作系统包含许多并发进程
-->
线程是某进程同一地址空间的独立执行单元
-->
创建某个进程就是在一个唯一地址空间创建一个主线程。进程开始时,就会执行该进程的主线程
-->
主线程可能会创建其他线程,每个线程又创建更多的线程
-->
某进程的所有线程都在该进程的相同地址空间中执行,但每个线程都是一个独立的执行单元。如果一个线程被挂起,其他线程可以继续执行。
线程的优点:
- 线程创建和切换速度更快。线程与进程共用一个地址空间,在进程中创建线程不必为新的线程分配内存和创建页表。
- 线程的响应速度更快。某个线程被挂起时,同一线程中的其他线程可以继续执行。
- 线程更适合并行计算。
线程的缺点:
- 由于地址空间共享,线程需要来自用户的明确同步。
- 许多库函数可能对线程不安全。
- 在单CPU系统上,使用线程解决问题实际上要比使用顺序程序慢。
线程操作
- 线程管理函数
创建函数
pthread_creat()
int pthread_creat (pthread_t *pthread_id, pthread_attr_t *attr,
void *(*func)(void *), void *arg);
成功则返回0,失败则返回错误代码。
pthread_id是指向pthread_t类型的指针。
attr是指向另一种不透明数据类型的指针。
线程ID
int pthread_equal (pthread_t t1,pthread_t t2);
线程终止
int pthread_exit (void *status);
显示终止
线程连接
int pthread_join (pthread_t thread, void **status_ptr);
2. 互斥量
3. 连接
4. 条件变量
5. 屏障
线程进行并发编程
-
矩阵计算
-
快速排序
线程同步
最简单的同步工具是锁(互斥量),它允许执行实体仅在有锁的情况下才能继续执行。
初始化互斥量
(1)静态
pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;
(2)动态
pthread_mutex_init(pthread_mutex_t *m,pthread_mutexattr_t,*attr)
使用互斥量
int pthread_mutex_lock (pthread_mutex_t *m);
int pthread_mutex_unlock (pthread_mutex_t *m);
int pthread_mutex_trylock (pthread_mutex_t *m);
int pthread_mutex_destroy (pthread_mutex_t *m);
- 并发线程求解线性方程组
死锁问题
- 防止并发程序中的死锁
互斥量使用封锁协议,如果某线程不能获取互斥量,就会被阻塞,等待互斥量解锁后再继续。
利用条件加锁和退避来预防死锁
while(1){
lock(m1);
if (!trylock(m2))
unlock(m1);
else
break;
}
条件变量
初始化
静态
pthread_cond_t con= PTHREAD_COND_INITIALIZER;
动态
pthread_mutex_t con_mutex;
pthread_cond_t con;
pthread_mutex_init(&con_mutex, NULL);
pthread_cond_init(&con,NULL);
信号量
信号量是进程同步的一般机制。信号量是一种数据结构
信号量相对于条件变量的优点