《信息安全系统设计与实现》第八周学习笔记-526互联

并行计算导论

顺序算法与并行算法

并行性与并发性

通常，并行算法只识别可并行执行的任务，但是它没有规定如何将任务映射到处理组件。在理想情况下，并行算法中的所有任务都应该同时实时执行
CPU系统中，并发性是通过多任务处理来实现的

线程

线程的原理

线程是操作系统能够进行运算调度的最小单位。它被包含在进程之中，是进程中的实际运作单位。一条线程指的是进程中一个单一顺序的控制流，一个进程中可以并发多个线程，每条线程并行执行不同的任务。

线程的优点

线程创建和切换速度更快
库函数不安全
单CPU系统中，线程解决问题实际上要比使用顺序程序慢

线程的缺点

由于地址空间共享，线程需要来自用户的明确同步
许多库函数可能对线程不安全，例如传统 strtok()函数将一个字符串分成一连串令牌。通常，任何使用全局变量或依赖于静态内存内容的函数，线程都不安全。为了使库函数适应线程环境，还需要做大量的工作
在单CPU系统上，使用线程解决问题实际上要比使用顺序程序慢，这是由在运行时创建线程和切换上下文的系统开销造成的

线程操作

线程的执行轨迹与进程类似。线程可在内核模式或用户模式下执行

线程管理函数

创建线程

int pthread_create(pthread_t *pthread_id,pthread_attr_t *attr,void *(*func)(void*),void *arg)

线程ID

int pthread_equal(pthread_t t1,pthread_t t2);

线程终止

int pthread_exit(void *status)；

线程连接

int pthread_join(pthread_t thread,void **status_ptr)

线程示例程序

用线程快速排序

#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()	// print current a[] contents
{
    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; // start the "recursive threads" 
    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();
}