臨界區的互斥控制

本文配套源碼

一、前言

我正在研究線程的通訊，無奈有關這方面的資料實在太少,沒辦法我只好去啃MSDN,但是MSDN好像說得也不太清楚。所以那我就寫了這麼一個例子，以望對學習多線程編程起到引玉拋磚的作用。有個易懂的例子學起來總是容易很多。近來我正在復習那幾個排序算法，於是就把這些算法寫到了這裡來作為線程的例子。同時也對幾個通用的排序算法思想作了一些說明。

這個例子利用多線程使用不同的排序算法對數據進行排序，每一個線程使用不同的算法。主線程裡使用快速排序QuickSort，其他四個算法分別建立四個子線程，在子線程中進行排序。因為每一個線程都要調用函數PrintResult把結果輸出到顯示器上，所以不同的線程就會爭奪著向顯示器輸出，這樣，不同線程的輸出就會混合在一起，所以呢必須讓線程一個接著一個輸出。也就是必須對PrintResult進行互斥控

制。要進行互斥控制，則必須用到Event、Mutex、CrititicalSection、Semaphore等互斥控制量。這個例子可以使用Event、Mutex、CrititicalSection，你可以根據提示修改代碼使用其中的一種互斥量進行測試。 我所寫的例子沒有使用MFC，用的都是SDK的WINAPI，如果使用MFC時有些許差別，但原理是一樣的。而且MFC還把線程分成用戶界面線程和工作者線程，實質上用戶界面線程跟工作者線程的差別是，用戶界面線程要繼承的基類已經實現了消息循環，MFC幫你做了很多的消息處理和界面控制的工作。

一、WINAPI線程控制函數簡介:有關詳細說明請查看MSDN

1.1 線程建立函數 HANDLE CreateThread(
　　LPSECURITY_ATTRIBUTES lpThreadAttributes,
　　// 安全屬性結構指針，可為NULL
　　DWORD dwStackSize,
　　// 線程棧大小，若為0表示使用默認值
　　LPTHREAD_START_ROUTINE lpStartAddress,
　　// 指向線程函數的指針
　　LPVOID lpParameter,
　　// 傳遞給線程函數的參數，可以保存一個指針值
　　//所以，線程函數的參數只能是一個32位值
　　//而且線程函數返回值也有規定，必須是unsigned long
　　DWORD dwCreationFlags,
　　// 線程建立是的初始標記，運行或掛起
　　LPDWORD lpThreadId
　　// 指向接收線程號的DWORD變量
);

1.2 臨界資源控制函數：

1)事件對象的創建

事件對象的作用是為線程傳送一個公共的事件信號，使用CreateEvent函數創建:

HANDLE CreateEvent(
　　LPSECURITY_ATTRIBUTES lpEventAttributes,
　　// 安全屬性結構指針，可為NULL
　　BOOL bManualReset,
　　// 手動清除信號標記，TRUE在WaitForSingleObject後必須手動調
　　//用RetEvent清除信號。
　　//若為FALSE則在WaitForSingleObject後，系統自動清除事件信號
　　BOOL bInitialState, // 初始狀態，TRUE有信號，FALSE無信號
　　LPCTSTR lpName // 信號量的名稱，字符數不可多於MAX_PATH
　　//如果遇到同名的其他信號量函數就會失敗，如果遇到同類信號同名
　　//也要注意變化
);2)互斥量的創建

互斥量的作用是保證每次只能有一個線程獲得互斥量而得以繼續執行，使用CreateMutex函數創建: HANDLE CreateMutex(
　　LPSECURITY_ATTRIBUTES lpMutexAttributes,
　　// 安全屬性結構指針，可為NULL
　　BOOL bInitialOwner, // 當前建立互斥量是否占有該互斥量
　　//TRUE表示占有，這樣其他線程就不能獲得此互斥量也就無法進入由
　　//該互斥量控制的臨界區。FALSE表示不占有該互斥量
　　LPCTSTR lpName // 信號量的名稱，字符數不可多於MAX_PATH
　　//如果遇到同名的其他信號量函數就會失敗，如果遇到同類信號同名
　　//也要注意變化
);3)臨界區信號的初始化

使用前必須先初始化

VOID InitializeCriticalSection(
　　LPCRITICAL_SECTION lpCriticalSection // 臨界區變量指針
); 4)阻塞函數

如果等待的信號量不可用，那麼線程就會掛起，直到信號可用線程才會被喚醒，該函數會自動修改信號，如Event，線程被喚醒之後

Event信號會變得無信號，Mutex、Semaphore等也會變。我們使用WaitForSingleObject函數等待信號，如果要等待多個信號可以使用WaitForMutipleObject函數。

DWORD WaitForSingleObject(
　　HANDLE hHandle, // 等待對象的句柄
　　DWORD dwMilliseconds // 等待毫秒數，INFINITE表示無限等待
);二、實例講解

下面我們結合本文的示例代碼進行具體的講解：

2.1 函數、變量的申明

#include "stdafx.h"
#include "stdlib.h"
#include "memory.h"
HANDLE evtTerminate; //事件信號,標記是否所有子線程都執行完下面使用了三種控制方法，你可以注釋其中兩種，使用其中一種。注意修改時要連帶修改臨界區PrintResult裡的相應控制語句

HANDLE evtPrint; //事件信號,標記事件是否已發生
//CRITICAL_SECTION csPrint; //臨界區
//HANDLE mtxPrint; //互斥信號,如有信號表明已經有線程進入臨界區並擁有此信號
static long ThreadCompleted = 0;
/*ThreadCompleted用來標記四個子線程中已完成線程的個數,當一個子線程完成時就對ThreadCompleted進行加一操作,
要使用InterlockedIncrement(long* lpAddend)和InterlockedDecrement(long* lpAddend)進行加減操作*/下面的結構是用於傳送排序的數據給各個排序子線程 struct MySafeArray
{
　　long* data;
　　int iLength;
};打印每一個線程的排序結果

void PrintResult(long* Array, int iLength, const char* HeadStr = "sort");排序函數 int QuickSort(long* Array, int iLow, int iHigh); //快速排序
unsigned long __stdcall BubbleSort(void* theArray); //冒泡排序
unsigned long __stdcall SelectSort(void* theArray); //選擇排序
unsigned long __stdcall HeapSort(void* theArray); //堆排序
unsigned long __stdcall InsertSort(void* theArray); //插入排序以上四個函數的聲明必須乎合作為一個線程函數的必要條件才可以使用CreateThread建立一個線程。

（1）調用方法必須是__stdcall，即函數參數壓棧順序由右到左，而且由函數本身負責棧的恢復, C和C++默認是__cdecl, 所以要顯式聲明是__stdcall

（2）返回值必須是unsigned long

（3）參數必須是一個32位值，如一個指針值或long類型

（4）如果函數是類成員函數，必須聲明為static函數，在CreateThread時函數指針有特殊的寫法。如下(函數是類CThreadTest的成員函數中)：

static unsigned long _stdcall MyThreadFun(void* pParam);
handleRet = CreateThread(NULL, 0, &CThreadTestDlg::MyThreadFun, NULL, 0, &ThreadID);之所以要聲明為static是由於該函數必須要獨立於對象實例來使用，即使沒有聲明實例也可以使用。

2.2 具體實現代碼

int main(int argc, char* argv[])
{
　　/*
　　//下面的代碼是為了從命令行上接收參數進行排序的
　　//但為了測試方便,所以就省去,改用靜態數據進行排序
　　//排序數據在接著的data數組裡靜態聲明
　　if(argc <= 1)
　　{
　　　　 printf("Please Input Data.");
　　　　 return 0;
　　}
　　int i;
　　long *data;
　　int iDataLen = argc - 1;
　　data = new long[argc-1];
　　for (i=0; i<argc-1; i++)
　　{
　　　　 data[i] = atol(argv[i+1]);
　　}
　　*/
　　long data[] = {123,34,546,754,34,74,3,56};
　　int iDataLen = 8;
　　//為了對各個子線程分別對原始數據進行排序和保存排序結果
　　//分別分配內存對data數組的數據進行復制
　　long *data1, *data2, *data3, *data4, *data5;
　　MySafeArray StructData1, StructData2, StructData3, StructData4;
　　data1 = new long[iDataLen];
　　memcpy(data1, data, iDataLen << 2); //把data中的數據復制到data1中
　　//內存復制 memcpy(目標內存指針, 源內存指針, 復制字節數), 因為long的長度
　　//為4字節,所以復制的字節數為iDataLen << 2, 即等於iDataLen*4
　　StructData1.data = data1;
　　StructData1.iLength = iDataLen;
　　data2 = new long[iDataLen];
　　memcpy(data2, data, iDataLen << 2);
　　StructData2.data = data2;
　　StructData2.iLength = iDataLen;
　　data3 = new long[iDataLen];
　　memcpy(data3, data, iDataLen << 2);
　　StructData3.data = data3;
　　StructData3.iLength = iDataLen;
　　data4 = new long[iDataLen];
　　memcpy(data4, data, iDataLen << 2);
　　StructData4.data = data4;
　　StructData4.iLength = iDataLen;
　　data5 = new long[iDataLen];
　　memcpy(data5, data, iDataLen << 2);
　　　　
　　unsigned long TID1, TID2, TID3, TID4;
　　//對信號量進行初始化
　　evtTerminate = CreateEvent(NULL, FALSE, FALSE, "Terminate");
　　evtPrint = CreateEvent(NULL, FALSE, TRUE, "PrintResult");
　　//mtxPrint = CreateMutex(NULL, FALSE, "PrintMutex");
　　//InitializeCriticalSection(&csPrint);
　　//分別建立各個子線程
　　CreateThread(NULL, 0, &BubbleSort, &StructData1, NULL, &TID1);
　　CreateThread(NULL, 0, &SelectSort, &StructData2, NULL, &TID2);
　　CreateThread(NULL, 0, &HeapSort, &StructData3, NULL, &TID3);
　　CreateThread(NULL, 0, &InsertSort, &StructData4, NULL, &TID4);
　　//在主線程中執行行快速排序，其他排序在子線程中執行
　　QuickSort(data5, 0, iDataLen - 1);
　　PrintResult(data5, iDataLen, "Quick Sort");
　　WaitForSingleObject(evtTerminate, INFINITE); //等待所有的子線程結束
　　//所有的子線程結束後，主線程才可以結束
　　//delete[] data;
　　delete[] data1;
　　delete[] data2;
　　delete[] data3;
　　delete[] data4;
　　CloseHandle(evtPrint);
　　return 0;
}

每一個線程都要使用下面這個函數進行輸出，而且只有一個顯示器，產生多個線程競爭對控制台的使用權。

//*****************************臨界區***************************************

//

void PrintResult(long* Array, int iLength, const char* HeadStr)
{
　　WaitForSingleObject(evtPrint, INFINITE); //等待事件有信號
　　//EnterCriticalSection(&csPrint); //標記有線程進入臨界區
　　//WaitForSingleObject(mtxPrint, INFINITE); //等待互斥量空置（沒有線程擁有它）
　　int i;
　　printf("%s: ", HeadStr);
　　for (i=0; i<iLength-1; i++)
　　{
　　　　printf("%d,", Array[i]);
　　　　Sleep(100); //延時（可以去掉）
　　　　/*只是使得多線程對臨界區訪問的問題比較容易看得到
　　　　如果你把臨界控制的語句注釋掉，輸出就會變得很凌亂，各個排序的結果會
　　　　分插間隔著輸出，如果不延時就不容易看到這種不對臨界區控制的結果
　　　　*/
　　}
　　printf("%d\n", Array[i]);
　　SetEvent(evtPrint); //把事件信號量恢復，變為有信號
　　//LeaveCriticalSection(&csPrint); //標記線程離開臨界區
　　//ReleaseMutex(mtxPrint); //釋放對互斥量的占有
}//***************************************************************************

三、排序思想與具體算法

3.1 冒泡排序思想(升序，降序同理，後面的算法一樣都是升序):

從頭到尾對數據進行兩兩比較進行交換,小的放前大的放後。這樣一次下來，最大的元素就會被交換的最後，然後下一次循環就不用對最後一個元素進行比較交換了，所以呢每一次比較交換的次數都比上一次循環的次數少一，這樣N次之後數據就變得升序排列了

unsigned long __stdcall BubbleSort(void* theArray)
{
　　long* Array = ((MySafeArray*)theArray)->data;
　　int iLength = ((MySafeArray*)theArray)->iLength;
　　int i, j=0;
　　long swap;
　　for (i = iLength-1; i > 0; i--)
　　{
　　　for(j = 0; j < i; j++)
　　　{
　　　　if(Array[j] > Array[j+1]) //前比後大，交換
　　　　{
　　　　swap = Array[j];
　　　　Array[j] = Array[j+1];
　　　　Array[j+1] = swap;
　　　　}
　　　}
　　}
　　PrintResult(Array, iLength, "Bubble Sort"); //向控制台打印排序結果
　　InterlockedIncrement(&ThreadCompleted); //返回前使線程完成數標記加1
　　if(ThreadCompleted == 4) SetEvent(evtTerminate);//檢查是否其他線程都已執行完
　　//若都執行完則設置程序結束信號量
　　return 0;
}
　　　3.2 選擇排序思想:

每一次都從無序的數據中找出最小的元素，然後和前面已經有序的元素序列的後一個元素進行交換，這樣整個源序列就會分成兩部分，前面一部分是已經排好序的有序序列，後面一部分是無序的，用於選出最小的元素。 循環N次之後，前面的有序序列加長到跟源序列一樣長，後面的無序部分長度變為0，排序就完成了。

unsigned long __stdcall SelectSort(void* theArray)
{
　　long* Array = ((MySafeArray*)theArray)->data;
　　int iLength = ((MySafeArray*)theArray)->iLength;
　　long lMin, lSwap;
　　int i, j, iMinPos;
　　for(i=0; i < iLength-1; i++)
　　{
　　　lMin = Array[i];
　　　iMinPos = i;
　　　for(j=i + 1; j <= iLength-1; j++) //從無序的元素中找出最小的元素
　　　{
　　　　if(Array[j] < lMin)
　　　　{
　　　　 iMinPos = j;
　　　　 lMin = Array[j];
　　　　}
　　　}
　　　//把選出的元素交換拼接到有序序列的最後
　　　lSwap = Array[i];
　　　Array[i] = Array[iMinPos];
　　　Array[iMinPos] = lSwap;
　　}
　　PrintResult(Array, iLength, "Select Sort"); //向控制台打印排序結果
　　InterlockedIncrement(&ThreadCompleted); //返回前使線程完成數標記加1
　　if(ThreadCompleted == 4) SetEvent(evtTerminate); //檢查是否其他線程都已執行完
　　//若都執行完則設置程序結束信號量
　　return 0;
}3.3 堆排序思想：

堆：數據元素從1到N排列成一棵二叉樹，而且這棵樹的每一個子樹的根都是該樹中的元素的最小或最大的元素這樣如果一個無序數據集合是一個堆那麼，根元素就是最小或最大的元素 ,堆排序就是不斷對剩下的數據建堆，把最小或最大的元素析透出來。

下面的算法，就是從最後一個元素開始，依據一個節點比父節點數值大的原則對所有元素進行調整，這樣調整一次就形成一個堆，第一個元素就是最小的元素。然後再對剩下的無序數據再進行建堆，注意這時後面的無序數據元素的序數都要改變，如第一次建堆後，第二個元素就會變成堆的第一個元素。

unsigned long __stdcall HeapSort(void* theArray)
{
　　long* Array = ((MySafeArray*)theArray)->data;
　　int iLength = ((MySafeArray*)theArray)->iLength;
　　int i, j, p;
　　long swap;
　　for(i=0; ii; j--) //從最後倒數上去比較字節點和父節點
　　　{
　　　　p = (j - i - 1)/2 + i; //計算父節點數組下標
　　　　//注意到樹節點序數跟數組下標不是等同的，因為建堆的元素個數逐個遞減
　　　　if(Array[j] < Array[p]) //如果父節點數值大則交換父節點和字節點
　　　　{
　　　　　swap = Array[j];
　　　　　Array[j] = Array[p];
　　　　　Array[p] = swap;
　　　　}
　　　}
　　}
　　PrintResult(Array, iLength, "Heap Sort"); //向控制台打印排序結果
　　InterlockedIncrement(&ThreadCompleted); //返回前使線程完成數標記加1
　　if(ThreadCompleted == 4) SetEvent(evtTerminate); //檢查是否其他線程都已執行完
　　//若都執行完則設置程序結束信號量
　　return 0;
}

3.4 插入排序思想：

把源數據序列看成兩半，前面一半是有序的，後面一半是無序的，把無序的數據從頭到尾逐個逐個的插入到前面的有序數據中，使得有序的數據的個數不斷增大，同時無序的數據個數就越來越少，最後所有元素都會變得有序。

unsigned long __stdcall InsertSort(void* theArray)
{
　　long* Array = ((MySafeArray*)theArray)->data;
　　int iLength = ((MySafeArray*)theArray)->iLength;
　　int i=1, j=0;
　　long temp;
　　for(i=1; i0; j--) //和前面的有序數據逐個進行比較找出合適的插入位置
　　　{
　　　　if(Array[j - 1] > temp) //如果該元素比插入值大則後移
　　　　　Array[j] = Array[j - 1];
　　　　else //如果該元素比插入值小，那麼該位置的後一位就是插入元素的位置
　　　　　break;
　　　}
　　　Array[j] = temp;
　　}
　　PrintResult(Array, iLength, "Insert Sort"); //向控制台打印排序結果
　　InterlockedIncrement(&ThreadCompleted); //返回前使線程完成數標記加1
　　if(ThreadCompleted == 4) SetEvent(evtTerminate); //檢查是否其他線程都已執行完
　　//若都執行完則設置程序結束信號量
　　return 0;
}

3.5 快速排序思想：

快速排序是分治思想的一種應用，它先選取一個支點，然後把小於支點的元素交換到支點的前邊，把大於支點的元素交換到支點的右邊。然後再對支點左邊部分和右邊部分進行同樣的處理，這樣若干次之後，數據就會變得有序。

下面的實現使用了遞歸

建立兩個游標：iLow，iHigh；iLow指向序列的第一個元素，iHigh指向最後一個先選第一個元素作為支點，並把它的值存貯在一個輔助變量裡。那麼第一個位置就變為空並可以放置其他的元素。 這樣從iHigh指向的元素開始向前移動游標iHigh查找比支點小的元素，如果找到，則把它放置到空置了的位置（現在是第一個位置）然後iHigh游標停止移動，這時iHigh指向的位置被空置，然後移動iLow游標尋找比支點大的元素放置到iHigh指向的空置的位置，如此往復直到iLow與iHigh相等。最後使用遞歸對左右兩部分進行同樣處理.

int QuickSort(long* Array, int iLow, int iHigh)
{
　　if(iLow >= iHigh) return 1; //遞歸結束條件
　　long pivot = Array[iLow];
　　int iLowSaved = iLow, iHighSaved = iHigh; //保未改變的iLow，iHigh值保存起來
　　while (iLow < iHigh)
　　{
　　　　while (Array[iHigh] >= pivot && iHigh > iLow) //尋找比支點大的元素
　　　　iHigh -- ;
　　　　Array[iLow] = Array[iHigh]; //把找到的元素放置到空置的位置
　　　　while (Array[iLow] < pivot && iLow < iHigh) //尋找比支點小的元素
　　　　　iLow ++ ;
　　　　Array[iHigh] = Array[iLow]; //把找到的元素放置到空置的位置
　　}
　　Array[iLow] = pivot; //把支點值放置到支點位置，這時支點位置是空置的
　　//對左右部分分別進行遞歸處理
　　QuickSort(Array, iLowSaved, iHigh-1);
　　QuickSort(Array, iLow+1, iHighSaved);
　　return 0;
}

如有不妥之處敬請讀者來信告知。

來信請寄 [email protected]