2021-2022-1 20191315《資訊安全系統設計與實作（上）》學習筆記7

第四章 并發程式設計

本章論述了并發程式設計，介紹了并行計算的概念，指出了并行計算的重要性;比較了順序算法與并行算法，以及并行性與并發性;解釋了線程的原理及其相對于程序的優勢;通過示例介紹了 Pthread 中的線程操作，包括線程管理函數，互斥量、連接配接、條件變量和屏障等線程同步工具;通過具體示例示範了如何使用線程進行并發程式設計，包括矩陣計算、快速排序和用并發線程求解線性方程組等方法;解釋了死鎖問題，并說明了如何防止并發程式中的死鎖問題;讨論了信号量，并論證了它們相對于條件變量的優點;還解釋了支援 Linux 中線程的獨特方式。程式設計項目是為了實作使用者級線程。它提供了一個基礎系統來幫助讀者開始工作。這個基礎系統支援并發任務的動态建立、執行和終止，相當于在某個程序的同一位址空間中執行線程。讀者可通過該項目實作線程同步的線程連接配接、互斥量和信号量，并示範它們在并發程式中的用法。該程式設計項目會讓讀者更加深入地了解多任務處理、線程同步和并發程式設計的原理及方法。

并行計算導論

• 在早期，大多數計算機隻有一個處理元件，稱為處理器或中央處理器(CPU)。受這種硬體條件的限制，計算機程式通常是為串行計算編寫的。要求解某個問題，先要設計一種算法，描述如何一步步地解決問題，然後用計算機程式以串行指令流的形式實作該算法。在隻有一個 CPU 的情況下，每次隻能按順序執行某算法的一個指令和步驟。但是，基于分治原則(如二叉樹查找和快速排序等)的算法經常表現出高度的并行性，可通過使用并行或并發執行來提高計算速度。并行計算是一種計算方案，它嘗試使用多個執行并行算法的處理器更快速地解決問題。

順序算法與并行算法

• 順序算法：begin-end代碼塊列出算法。可包含多個步驟，所有步驟通過單個任務依次執行，每次執行一個步驟，全執行完，算法結束。
• 并行算法：cobegin-coend代碼塊來指定獨立任務，所有任務都是并行執行的，緊接着代碼塊的下一個步驟将隻在所有這些任務完成之後執行。

  

并行性和并發性

并行算法隻識别可并行執行的任務，但是它沒有規定如何将任務映射到處理元件。在理想情況下，并行算法中的所有任務都應該同時實時執行。然而，真正的并行執行隻能在有多個處理元件的系統中實作，比如多久理器或多核系統。在單CPU系統中，一次隻能執行一個任務。在這種情況下，不同的任多務隻能并發執行，即在邏輯上并行執行。在單CPU系統中，并發性是通過多任務處理來實作的。

線程

原理

• 線程是作業系統能夠進行運算排程的最小機關。它被包含在程序之中，是程序中的實際運作機關。一條線程指的是程序中一個單一順序的控制流，一個程序中可以并發多個線程，每條線程并行執行不同的任務。在Unix System V及SunOS中也被稱為輕量程序（lightweight processes），但輕量程序更多指核心線程（kernel thread），而把使用者線程（user thread）稱為線程。

  線程是獨立排程和分派的基本機關。線程可以為作業系統核心排程的核心線程，如Win32線程；由使用者程序自行排程的使用者線程，如Linux平台的POSIX Thread；或者由核心與使用者程序，如Windows 7的線程，進行混合排程。

• 同一程序中的多條線程将共享該程序中的全部系統資源，如虛拟位址空間，檔案描述符和信号處理等等。但同一程序中的多個線程有各自的調用棧（call stack），自己的寄存器環境（register context），自己的線程本地存儲（thread-local storage）。

  一個程序可以有很多線程，每條線程并行執行不同的任務。

• 在多核或多CPU，或支援Hyper-threading的CPU上使用多線程程式設計的好處是顯而易見，即提高了程式的執行吞吐率。在單CPU單核的計算機上，使用多線程技術，也可以把程序中負責I/O處理、人機互動而常被阻塞的部分與密集計算的部分分開來執行，編寫專門的workhorse線程執行密集計算，進而提高了程式的執行效率。

優點

• 線程建立和切換速度更快
• 響應速度更快
• 更适合并行計算

缺點

• 由于位址空間共享，線程需要來自使用者的明确同步。
• 許多庫函數可能對線程不安全，例如傳統 strtok()函數将一個字元串分成一連串令牌。通常，任何使用全局變量或依賴于靜态内有内容的函數，線程都不安全。為了使庫函數适應線程環境，還需要做大量的工作。
• 在單CPU系統上，使用線程解決問題實際上要比使用順序程式慢，這是由在運作時建立線程和切換上下文的系統開銷造成的。

線程操作

線程可在核心模式或使用者模式下執行

線程管理函數

Pthread庫提供了用于線程管理的以下API

建立一個新的線程

#include <pthread.h>

int pthread_create(pthread_t *thread, const pthread_attr_t *attr,void *(*start_routine) (void *), void *arg);

線程終止

void pthread_exit(void *retval);

等待線程結束

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

傳回線程ID

pthread_t pthread_self(void);

取消一個線程

int pthread_cancel(pthread_t thread);

将一個線程從程序中分離

int pthread_detach(pthread_t thread);

線程同步

由于線程在程序的同一位址空間中執行 它們共享同一位址空間中的所有全局變量和資料結構。當多個線程試圖修改同一共享變量或資料結構時，如果修改結果取決于線程的執行順序，則稱之為競态條件。在并發程式中，絕不能有競态條件。否則，結果可能不一緻。除了連接配接操作之外，并發執行的線程通常需要互相協作。為了防止出現競态條件并且支援線程協作，線程需要同步。通常，同步是一種機制和規則，用于確定共享資料對象的完整性和并發執行實體的協調性。它可以應用于核心模式下的程序，也可以應用于使用者模式下的線程。

互斥量

同步工具是鎖，它允許執行實體僅在有鎖的情況下才能執行。鎖被稱為互斥量

互斥變量是用pthread_mutex_t類型聲明的，在使用之前必須進行初始化。

• 靜态方法：

  pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;

  定義互斥量m，并使用預設屬性對其進行初始化。
• 動态方法:

  pthread_mutex_init(pthread_mutex_t *m,pthread_mutexattr_t,*attr);

  通常attr參數可以設定位NULL，作為預設屬性。

  初始化完成後，線程可以通過以下函數使用互斥量。

  

線程使用互斥量來保護共享資料對象。

死鎖預防

• 互斥量使用封鎖協定。有多種方法可以解決可能的死鎖問題，其中包括死鎖防禦、死鎖規避、死鎖檢測和回複等。在實際情況中，唯一可行的方法時死鎖預防，試圖在設計并行算法是防止死鎖發生。
• 一種簡單的死鎖預防時對互斥量進行排序，并確定每個線程隻在一個方向請求互斥量，這樣請求序列中就不會有循環。
• 條件加鎖和退避預防死鎖

  

條件變量

作為鎖，互斥量僅用于確定線程隻能互斥地通路臨界區中的共享資料對象。條件變量提供了一種線程協作的方法。在Pthread中，使用othread_cond_t來聲明條件變量，而且必須在使用前進行初始化。

• 靜态方法

  pthread_cond_t con = PTHREAD_COND_INITALLIZER;

• 動态方法

  使用pthread_cond_init()函數，通過attr參數設定條件變量。

信号量

信号量是程序同步的一般機制。（計數）信号量是一種資料結構.

struct sem{
   int value;
   struct process *queue
}s;
           

最有名的信号量操作時P和V

屏障

線程連接配接操作允許某線程（通常是主線程）等待其他線程終止。在某些情況下，保持線程活動會更好，但應要求他們在所有線程都達到指定同步點之前不能繼續活動。在Pthreads中，可以采用屏障以及一系列屏障函數。

首先，主線程建立一個屏障對象

pthread_barrier_init(&barrier NULL,nthreads);

用屏蔽中同步線程數字對他進行初始化。然後，主線程建立工作線程來執行任務。

實踐

用并發線程快速排序

源代碼

點選檢視代碼

#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 () ;
}
           

運作結果

用線程計算矩陣的和

源代碼

點選檢視代碼

#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);
}

           

運作結果