20211325 2023-2024-1 《信息安全系统设计与实现（上）》第七周学习笔记

一、任务要求

1.自学教材第4章，提交学习笔记（10分），评分标准如下 1. 知识点归纳以及自己最有收获的内容，选择至少2个知识点利用chatgpt等工具进行苏格拉底挑战，并提交过程截图，提示过程参考下面内容（4分） “我在学***X知识点，请你以苏格拉底的方式对我进行提问，一次一个问题” 核心是要求GPT：“请你以苏格拉底的方式对我进行提问” 然后GPT就会给你提问，如果不知道问题的答案，可以反问AI：“你的理解（回答）是什么？” 如果你觉得差不多了，可以先问问GPT：“针对我XXX知识点，我理解了吗？” GPT会给出它的判断，如果你也觉得自己想清楚了，可以最后问GPT：“我的回答结束了，请对我的回答进行评价总结”，让它帮你总结一下。

2. 问题与解决思路，遇到问题最先使用chatgpt等AI工具解决，并提供过程截图（3分）

3. 实践过程截图，代码链接（2分）

4. 其他（知识的结构化，知识的完整性等，提交markdown文档，使用openeuler系统等）（1分）

二、教材知识总结

第四章并发编程

学习目标

学习了解并发编程的概念，理解并行计算的概念和重要性；掌握线程的原理和其对于进程的优势。通过学习Pthread线程操作，了解如何使用线程进行并发编程；理解死锁问题；通过编程实践更加深入的理解多任务处理、线程同步和并发编程的原理及方法。

并行计算与并行编程

并行计算是一种计算体系结构，其中多个处理器同时执行从一个较大的复杂问题中分解出来的多个、较小的计算任务。近年来并行计算已成为计算机体系结构中的主要范例，主要以多核处理器的形式出现。

并行编程

“在并行机提供的并行编程环境上，具体实现并行算法，编制并行程序，并运行该程序，从而达到并行求解应用问题的目的。”

并行与并发

并行算法只识别可执行的任务，并行算法中的所有任务都应该同时实时执行。
并发性是通过多任务处理实现的。

线程

线程是某进程同一地址空间上的独立执行单元。

创建某个进程就是在一个唯一地址空间创建一个线程。当某进程开始时，就会执行该进程的主线程。如果只有一个主线程，那么进程和线程实际上并没有区别。但是，主线程可能会创建其他线程。每个线程又可以创建更多的线程等。某进程的所有线程都在该进程的相同地址空间中执行，但每个线程都是一个独立的执行单元。

实现线程主要有三种方式：

（1）使用内核线程实现

（2）使用用户线程实现

（3）使用用户线程加轻量级进程混合实现

线程的优点

线程创建和切换速度更快

若要在某个进程中创建线程，操作系统不必为新的线程分配内存和创建页表，因为线程与进程共用同一个地址空间。所以，创建线程比创建进程更快。

线程的响应速度更快

一个进程只有一个执行路径。当某个进程被挂起时，帮个进程都将停止执行。相反，当某个线程被挂起时，同一进程中的其他线程可以继续执行。

线程更适合井行计算

并行计算的目标是使用多个执行路径更快地解决间题。基于分治原则（如二叉树查找和快速排序等）的算法经常表现出高度的并行性，可通过使用并行或并发执行来提高计算速度。

线程的缺点

由于地址空间共享，线程需要来自用户的明确同步
许多库函数可能对线程不安全，例如strtok（）；
在单CPU系统上，使用线程解决间题实际上要比使用顺序程序慢，这是由在运行时创建线程和切换上下文的系统开销造成的。

进程和线程对比

一个程序至少有一个进程,一个进程至少有一个线程。
线程的划分尺度小于进程(资源比进程少)，使得多线程程序的并发性高。
进程在执行过程中拥有独立的内存单元，而多个线程共享内存，从而极大地提高了程序的运行效率线线程不能够独立执行，必须依存在进程中。
可以将进程理解为工厂中的一条流水线，而其中的线程就是这个流水线上的工人。

线程操作


线程的执行轨迹与进程类似。

线程可在内核模式或用户模式下执行。

在用户模式下，线程在进程的相同地址空间中执行，但每个线程都有自己的执行堆栈。

线程是独立的执行单元，可根据操作系统内核的调度策略，对内核进行系统调用，变为桂起激活以继续执行等。

Pthread库提供的线程管理API

Pthread库提供了用于线程管理的以下APT。

pthread_create(thread, attr, function, arg): create thread
pthread_exit(status）：terminate thread
pthread_cancel(thread) : cancel thread
pthread_attr_init(attr) : initialize thread attributes
pthread_attr_destroy(attr): destroy thread attribute

使用pthread_ create()函数创建线程。

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

如果成功则返回0,如果失败则返回错误代码。

pthread_id是指向pthread_t类型变员的指针。

它会被操作系统内核分配的唯一线程ID填充。
在POSIX中,pthread_t是一种不透明的类型。
线程可通过pthread_self()函数获得自己的ID。在Linux中，pthread_t类型被定义为无符号长整型，因此线程ID可以打印为%lu。

attr是指向另一种不透明数据类型的指针，它指定线程属性。
func是要执行的新线程函数的人口地址。
arg是指向线程函数参数的指针
可写为void *func(void *arg)

attr参数使用：
定义一个pthread展性变址pt:hread_attr_tattr。
用pthread_attr_init(&attr)初始化屈性变掀。
设置属性变垃并在pthread_ create()调用中使用。
必要时，通过pthread_attr_destroy(&attr)释放attr资源。

线程ID

线程ID是一种不透明的数据类型，取决于实现悄况。因此，不应该直接比较线程ID。如果需要，可以使用pthread_ equal()函数对它们进行比较。

int pthread_equal (pthread_t tl, pthread_t t2);

线程终止
线程函数结束后，线程即终止。或者，线程可以调用函数以下函数来进行显示终止。

int pthraad_axit {void *status)

线程连接

一个线程可以等待另一个线程的终止，通过：

int pthread_join (pthread_t thread, void **status__ptr);

终止线程的退出状态以status_ptr返回。

简单编程：利用线程计算矩阵的和

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#define N 4
int A[N][N],sum[N];

void *func(void *arg)
{
        int j,row ;
        pthread_t tid = pthread_self();
        row = (int)arg;
        printf("Thread %d [%lu] computes sum of row %d\n",row,tid,row);
        for(j=0;j<N; j++)
                sum[row] += A[row][j];
        printf("Thread %d [%lu] done:sum [%d] =%d\n",row,tid,row,sum[row]);
        pthread_exit ((void*)0);
}
        int main(int argc, char *argv[])
{
        pthread_t thread[N];
        int i,j,r,total = 0;
        void *status;
        printf("Main: initialize A matrix\n");
        for(i=0; i<N;i++){
                sum[i] = 0;
                for(j=0;j<N;j++){
                        A[i][j]=i*N+j+1;
                        printf("%4d ",A[i][j]);
                }
                printf( "\n" );
        }
        printf ("Main: create %d threads\n",N);
        for(i=0;i<N;i++) {
                pthread_create(&thread[i],NULL,func,(void *)i);
        }
        printf("Main: try to join with thread\n");
        for(i=0; i<N; i++) {
                pthread_join(thread[i],&status);
                printf("Main: joined with %d [%lu]: status=%d\n",i,thread[i],
                                (int)status);
        }
        printf("Main: compute and print total sum:");
        for(i=0;i<N;i++)
                total += sum[i];
        printf ("tatal = %d\n",total );
        pthread_exit(NULL);
}

（运行指令须加-pthread）

简单编程：用线程快速排序

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
typedef struct{
    int upperbound;
    int lowerbound;
}PARM;
#define N 10
int a[N]={5,1,6,4,7,2,9,8,0,3};// unsorted data
int print(){//print current a[] contents
    int i;
    printf("[");
    for(i=0;i<N;i++)
        printf("%d ",a[i]);
    printf("]\n");
}
void *Qsort(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];//pick low pivot value
    left = lowerbound - 1;//scan index from left side
    right = upperbound;//scan index from right side
    if(lowerbound >= upperbound)
        pthread_exit (NULL);
    while(left < right){//partition loop
        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;//put pivot back
    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 threadsln", me) ;
    pthread_create(&leftThread,NULL,Qsort,(void * )&aleft);
    pthread_create(&rightThread,NULL,Qsort,(void *)&aright);
    //wait for left and right threads to finish
    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,(void * ) &arg);//wait for Qs thread to finish
    pthread_join(thread,NULL);
    printf ("main %lu sorted array = ", me);
    print () ;
}

线程同步

当多个线程试图修改同一共享变量或数据结构时，如果修改结果取决于线程的执行顺序，则称之为竞态条件
在并发程序中，绝不能有竞态条件。否则，觉果可能不一致。
并发执行的线程通常需要相互协作，防止出现竞态条件，线程需要同步。

互斥量
在 Pthread中，锁被称为互斥量，意思是相互排斥。互斥变呈是用 ptbread_mutex_t 类型声明的在使，用之前必须对它们进行初始化。有两种方法可以初始化互斥址。

静态方法：
pthreaa—mutex_t m = PTHREAD_MUTEX_INITIALIZER;
定义互斥量 m, 并使用默认属性对其进行初始化。

动态方法，使用 pthread_ mutex _init()函数

线程通过互斥量来保护共享数据对象

线程同步的几种方式：

互斥锁（mutex）
条件变量（condition）
读写锁（reader-writer lock）
信号量（semphore）

简单编程：Pthread互斥量

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#define N 4
int A[N][N], sum[N];


int total = 0;
pthread_mutex_t *m;

void *func(void *arg)
{
        int i,row,sum =0 ;
        pthread_t tid = pthread_self();
        row = (int)arg;
        printf("Thread %d [%lu] computes sum of row %d\n",row,tid,row);
        for(i=0;i<N; i++)
                sum += A[row][i];
        printf("Thread %d [%lu] update total with %d : ",row,tid,sum);
        pthread_mutex_lock(m);
         total += sum;
        pthread_mutex_unlock(m);
        printf("total = %d\n",total);
}
        int main(int argc, char *argv[])
{
        pthread_t thread[N];
        int i,j,r;
        void *status;
        printf("Main: initialize A matrix\n");
        for(i=0; i<N;i++){
                sum[i] = 0;
                for(j=0;j<N;j++){
                        A[i][j]=i*N+j+1;
                        printf("%4d ",A[i][j]);
                }
                printf( "\n" );
                m = (pthread_mutex_t *)malloc(sizeof(pthread_mutex_t));
        pthread_mutex_init(m,NULL);
        printf ("Main: create %d threads\n",N);
        for(i=0;i<N;i++) {
                pthread_create(&thread[i],NULL,func,(void *)i);
        }
        printf("Main: try to join with thread\n");
        for(i=0; i<N; i++) {
                pthread_join(thread[i],&status);
                printf("Main: joined with %d [%lu]: status=%d\n",i,thread[i],
                                (int)status);
        }
        printf ("Main:tatal = %d\n",total );
        pthread_mutex_destroy(m);
        pthread_exit(NULL);
　　}
}

条件变量

条件变量：作为锁，互斥量仅用于确保线程只能互斥地访间临界区中的共享数据对象。在Pthread中，使用类型pthread_cond_t来声明条件变拉，而且必须在使用前进行初始化。与互斥变量一样，条件变量也可以通过两种方法进行初始化。

静态方法:
pthread_cond_t con= PTHREAD_COND_INITIALIZER;
定义一个条件变量con,并使用默认属性对其进行初始化。

动态方法:使用pthread_cond_init()函数，可通过attr参数设置条件变量。

死锁预防

死锁是一种状态，在这种状态下，许多执行实体相互等待，因此都无法继续下去。

防止死锁的发生只需破坏死锁产生的四个必要条件之一即可。

破坏互斥条件
破坏不剥夺条件
破坏请求和保持条件
破坏循环等待条件

生产者-消费者问题

该问题需要注意的几点：

在缓冲区为空时，消费者不能再进行消费
在缓冲区为满时，生产者不能再进行生产
在一个线程进行生产或消费时，其余线程不能再进行生产或消费等操作，即保持线程间的同步
注意条件变量与互斥锁的顺序

由于前两点原因，因此需要保持线程间的同步，即一个线程消费（或生产）完，其他线程才能进行竞争CPU，获得消费（或生产）的机会。对于这一点，可以使用条件变量进行线程间的同步：生产者线程在product之前，需要wait直至获取自己所需的信号量之后，才会进行product的操作；同样，对于消费者线程，在consume之前需要wait直到没有线程在访问共享区（缓冲区），再进行consume的操作，之后再解锁并唤醒其他可用阻塞线程。

在访问共享区资源时，为避免多个线程同时访问资源造成混乱，需要对共享资源加锁，从而保证某一时刻只有一个线程在访问共享资源。

简单编程：生产者-消费者

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#define NBUF 5
#define N 10
int buf [NBUF];
int head, tail;
int data;
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++){ 
        pthread_mutex_lock(&mutex);
        if(data == NBUF) {
            printf("producer %lu: all bufs FULL: wait\n",me);
            pthread_cond_wait(&empty, &mutex);
        }
        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);
        if(data == 0){
            printf ("consumer %lu: all bufs EMPTY : wait\n",me);
            pthread_cond_wait(&full,&mutex);
        }
        c=buf[tail++];
        tail%=NBUF;
        data--;
        printf("consumer %lu: value=%d\n",me,c);
        pthread_mutex_unlock(&mutex);
        pthread_cond_signal(&empty);
    }
    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");
}