《信息安全系统设计与实现》第八周学习笔记
第四章 并发编程
并行计算
尝试使用多个执行并行算法的处理器更快速的解决问题
- 顺序算法与并行算法
- 顺序算法：所有步骤通过单个任务依次执行，每次执行一个步骤，当所有步骤执行完成时，算法结束。
- 并行算法：cobegin-coend代码块来指定独立任务，所有任务都是并行执行的，紧接着代码块的下一个步骤将只在所有这些任务完成之后执行。
- 并行性与并发性
- 在理想情况下，并行算法中的所有任务都应该同时实时执行。
- 真正的并行执行只能在有多个处理组件的系统中实现，比如多处理器或多核系统。
- 在单CPU系统中，一次只能执行一个任务。在这种情况下，不同的任务只能并发执行，即在逻辑上并行执行。
线程
- 线程的原理
- 线程是某进程同一地址空间上的独立执行单元。创建某个进程就是在一个唯一地址空间创建一个主线程。当某进程开始时，就会执行该进程的主线程。
- 线程的优点
- 线程创建和切换速度更快
- 线程的响应速度更快
- 线程更适合并行运算
- 线程的缺点
- 由于地址空间共享，线程需要来自用户的明确同步。
- 许多库函数可能对线程不安全。通常，任何使用全局变量或依赖于静态内存内容的函数，线程都不安全。
- 在单CPU系统上，使用线程解决问题实际上要比使用顺序程序慢。
线程操作
- 线程的执行轨迹与进程类似，线程可在内核模式或用户模式下执行。
- 在用户模式下，线程在进程的相同地址空间中执行，但每个线程都有自己的执行堆栈。
线程管理函数
- 创建线程
- 使用pthread_create()
int pthread_create(pthread_t *pthread_id,pthread_attr_t *attr,void *(*func)(void*),void *arg)
- attr 参数的使用步骤。
- (1)定义一个pthread属性变量pthread attr tattr。
- (2)用pthread attrinit (&attr)初始化属性变量。
- (3)设置属性变量并在pthread create0)调用中使用。
- (4)必要时，通过pthread attr destroy (&attr)释放attr 资源。
- 使用pthread_create()
- 线程ID
int pthread_equal(pthread_t t1,pthread_t t2);如果是不同的线程，返回0，否则返回非0
- 线程终止
int pthread_exit(void *status)；进行显式终止，其中状态是线程的退出状态。
- 线程连接
int pthread_join(pthread_t thread,void **status_ptr)终止线程的退出状态以status_ptr返回。
线程同步
- 互斥量
- 最简单的同步工具是锁，它允许执行实体仅在有锁的情况下才能继续执行。在 Pthread中，锁被称为互斥量，意思是相互排斥。
- 静态方法
- 动态方法
- 死锁预防
- 互斥量使用封锁协议。
- 在任何封锁协议中，误用加锁可能会产生一些问题。
- 死锁是一个状态，在这种状态下，许多执行实体相互等待，无法继续进行下去.
- 条件变量
- 静态方法
- 动态方法
- 生产者-消费者问题
- 共享全局变量：
-
int buf[NBUF]; int head,tail; int data;
-
- 共享全局变量：
- 信号量
- 信号量是进程同步的一般机制。
- 在使用信号量之前，必须使用一个初始值和一个空等待队列进行初始化。
- 屏障
- 在 Pthreads中，可以采用的机制是屏障以及一系列屏障函数。
- 用并发线程解线性方程组
- Linux中的线程
- Linux不区分进程和线程。
- 对于Linux内核，线程只是一个与其他进程共享某些资源的进程。
- 在 Linux 中，进程和线程都是由 clone（）系统调用创建的：
int clone(int (*fn)(void*),void *child_stack,int flags,void *arg)
实践
生产者-消费者问题
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#define NBUF 5
#define N 10
// shared global variables
int buf[NBUF]; // circular buffers
int head, tail; // indices
int data; // number of full buffers
pthread_mutex_t mutex;
pthread_cond_t empty, full;
int init()
{
head = tail = data = 0;
pthread_mutex_init(&mutex, NULL);
pthread_cond_init(&full, NULL);
pthread_cond_init(&empty, NULL);
}
void *producer()
{
int i;
pthread_t me = pthread_self();
for (i=0; i<N; i++) // try to put N items into buf[]
{
pthread_mutex_lock(&mutex); // lock mutex
if (data == NBUF)
{
printf ("producer %lu： all bufs FULL： wait\n", me);
pthread_cond_wait(&empty, &mutex); // wait
}
buf[head++] = i+1;
head %= NBUF;
data++;
printf("producer %lu： data=%d value=%d\n", me, data, i+1);
pthread_mutex_unlock (&mutex);
pthread_cond_signal(&full);
}
printf("producer %lu: exit\n", me);
}
void *consumer()
{
int i, c;
pthread_t me = pthread_self();
for (i=0; i<N; i++)
{
pthread_mutex_lock(&mutex); // lock mutex
if (data == 0)
{
printf ("consumer %lu: all bufs EMPTY: wait\n", me);
pthread_cond_wait(&full, &mutex); // wait
}
c = buf[tail++]; // get an item
tail %= NBUF;
data--; // dec data by 1
printf("consumer %lu： value=%d\n", me, c);
pthread_mutex_unlock(&mutex); // unlock mutex
pthread_cond_signal(&empty); // unblock a producer, if any
}
printf("consumer %lu: exit\n", me);
}
int main ()
{
pthread_t pro, con;
init();
printf("main： create producer and consumer threads\n");
pthread_create(&pro, NULL, producer, NULL);
pthread_create(&con, NULL, consumer, NULL);
printf("main: join with threads\n");
pthread_join(pro, NULL);
pthread_join(con, NULL);
printf("main: exit\n");
}
用线程快速排序
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#define N 10
typedef struct{
int upperbound;
int lowerbound;
}PARM;
int A[N]={5,1,6,4,7,2,9,8,0,3};
int print()
{
int i;
printf("[ ");
for (i=0; i<N; i++)
{
printf("%d ", A[i]);
}
printf("]\n");
}
void *qsort_1(void *aptr)
{
PARM *ap, aleft, aright;
int pivot, pivotIndex, left, right, temp;
int upperbound, lowerbound;
pthread_t me, leftThread, rightThread;
me = pthread_self();
ap = (PARM *)aptr;
upperbound = ap->upperbound;
lowerbound = ap->lowerbound;
pivot = A[upperbound];
left = lowerbound - 1;
right = upperbound;
if (lowerbound >= upperbound)
pthread_exit(NULL);
while (left < right)
{
do { left++;} while (A[left] < pivot);
do { right--;}while (A[right] > pivot);
if (left < right )
{
temp = A[left];
A[left] = A[right];
A[right] = temp;
}
}
print();
pivotIndex = left;
temp = A[pivotIndex];
A[pivotIndex] = pivot;
A[upperbound] = temp;
aleft.upperbound = pivotIndex - 1;
aleft.lowerbound = lowerbound;
aright.upperbound = upperbound;
aright.lowerbound = pivotIndex + 1;
printf("%lu： create left and right threads\n", me);
pthread_create(&leftThread, NULL, qsort_1, (void *)&aleft);
pthread_create(&rightThread, NULL, qsort_1, (void *)&aright);// wait for left and right threads
pthread_join(leftThread, NULL);
pthread_join(rightThread, NULL);
printf("%lu: joined with left & right threads\n", me);
}
int main(int argc, char *argv[])
{
PARM arg;
int i, *array;
pthread_t me, thread;
me = pthread_self();
printf("main %lu: unsorted array =" ,me);
print();
arg.upperbound = N-1;
arg.lowerbound = 0;
printf("main %lu create a thread to do QS\n", me);
pthread_create(&thread, NULL, qsort_1, (void *)&arg); // wait for QS thread to finish
pthread_join(thread, NULL);
printf("main %lu sorted array = ", me);
print();
}
苏格拉底挑战
遇到的问题及解决
问题
- 如何在一个线程中暂停执行一段时间
解决
- 暂停执行一段时间可以使用线程的睡眠函数来实现。在C语言中，常用的线程睡眠函数是usleep，它可以使当前线程在指定的微秒数内暂停执行。另外，还有sleep函数，它以秒为单位暂停执行。这些函数可以在需要暂停一段时间的地方使用，以控制线程的执行。