線程安全在數(shù)據(jù)結(jié)構(gòu)設計中的局限性

摘要：隨著多線程應用程序和系統(tǒng)的普及和繁榮，在程序設計中對于數(shù)據(jù)結(jié)構(gòu)在線程安全性上的要求和考慮不斷提高。有很多程序設計技巧可以用來提高數(shù)據(jù)結(jié)構(gòu)的線程安全性，簡化程序開發(fā)人員的工作。然而在理論上，無論多么精巧的設計，也只能使得數(shù)據(jù)結(jié)構(gòu)提供有限的線程安全性。

關(guān)鍵詞：線程；線程安全；數(shù)據(jù)結(jié)構(gòu)；同步；限制

中圖分類號：TP311文獻標識碼：A文章編號：1009-3044(2008)36-2568-03

Thread-safe Limitation in Data Structure Design

ZHU Yun

(AVIC Xi'an Aero-ENGINE(GROUP) LTD INSTITUTE， Xi'an 710021， China)

Abstract: More and more multi-threading programs and systems appear. They require thread-safe design on data structure. Many programming tricks in data structure design provide thread-safe functionality and reduce programmers' workload. But there are still limitations on such design in theory. Data structures designed for programmers can only provide limited thread-safe guarantee.

Key words: thread; thread safe; data structure; synchronization; limitation

1 引言

數(shù)據(jù)結(jié)構(gòu)是一門計算機學科，專門研究數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)，以及對數(shù)據(jù)的操作算法。數(shù)據(jù)結(jié)構(gòu)算法的設計和實現(xiàn)取決于數(shù)據(jù)的結(jié)構(gòu)設計。線程是進程中的一個指令序列，包含線程局部的變量定義，全局共享數(shù)據(jù)等。進程一般來說可以看作是磁盤上的可執(zhí)行程序在內(nèi)存中的鏡像。該文以C++語言和C++模板技術(shù)為基礎(chǔ)，結(jié)合POSIX線程標準，根據(jù)多年實踐經(jīng)驗，闡述了數(shù)據(jù)結(jié)構(gòu)設計中對于線程安全性的考慮，并且通過實際例子指出線程安全性的考慮和設計在某些方面具有很大的局限性。簡單來說，就是對于增強某些數(shù)據(jù)結(jié)構(gòu)的線程安全性的期望不能太高。本文假設讀者具備基本的數(shù)據(jù)結(jié)構(gòu)知識和程序設計能力，熟悉常用的一些數(shù)據(jù)結(jié)構(gòu)，了解線程設計和共享資源同步思想。

2 現(xiàn)狀分析

標準的數(shù)據(jù)結(jié)構(gòu)世界是相當單純的，設計者的思想只需要集中在如何構(gòu)建一個邏輯上完美的架構(gòu)。在這個世界里，沒有內(nèi)存映射文件和共享內(nèi)存，不存在窗口系統(tǒng)，沒有網(wǎng)絡，沒有數(shù)據(jù)庫，沒有其他進程。在這種情況下，自然也不會有線程這個概念。然而數(shù)據(jù)結(jié)構(gòu)終歸是要給別的開發(fā)人員用的，數(shù)據(jù)結(jié)構(gòu)遭遇線程正是理想遭遇現(xiàn)實的一種反映。軟件系統(tǒng)開發(fā)者在編寫程序的過程中，難免會在線程里使用數(shù)據(jù)結(jié)構(gòu)，例如最常見的數(shù)據(jù)結(jié)構(gòu)鏈表。

2.1 一個鏈表數(shù)據(jù)結(jié)構(gòu)的設計

假設現(xiàn)在有一個CList類，用來實現(xiàn)鏈表數(shù)據(jù)結(jié)構(gòu)。Clist封裝了鏈表的基本數(shù)據(jù)存儲結(jié)構(gòu)和在這個結(jié)構(gòu)上的一系列操作。為了使這個類真正成為一個“容器”，需要使用C++模板技術(shù)來實現(xiàn)。Clist的框架定義看起來如下：

typedef unsigned long POSITION;

// Clist

// all operations is under synchronization control of m_ListRWLock

template

class Clist

{protected:

struct Cnode

{Cnode* pNext;

Cnode* pPrev;

TYPE data;};

public:

//Constructor and Destructor

Clist();

~Clist();

// Copy-Constructor

Clist(const Clist newList);

//Attributes (head and tail)

// count of elements

int GetCount() const;

bool IsEmpty() const;

// peek at head or tail

TYPE GetHead();

TYPE GetHead() const;

TYPE GetTail();

TYPE GetTail() const;

//Operations

// get head or tail (and remove it) — don't call on empty list !

TYPE RemoveHead();

TYPE RemoveTail();

// add before head or after tail

POSITION AddHead(ARG_TYPE newElement);

POSITION AddTail(ARG_TYPE newElement);

// add another list of elements before head or after tail

void AddHead(Clist* pNewList);

void AddTail(Clist* pNewList);

// remove all elements

void RemoveAll();

// iteration

POSITION GetHeadPosition() const;

POSITION GetTailPosition() const;

TYPE GetNext(POSITION rPosition); // return *Position++

TYPE GetNext(POSITION rPosition) const; // return *Position++

TYPE GetPrev(POSITION rPosition); // return *Position—

TYPE GetPrev(POSITION rPosition) const; // return *Position—

// getting/modifying an element at a given position

TYPE GetAt(POSITION position);

TYPE GetAt(POSITION position) const;

void SetAt(POSITION pos， ARG_TYPE newElement);

void RemoveAt(POSITION position);

// inserting before or after a given position

POSITION InsertBefore(POSITION position， ARG_TYPE newElement);

POSITION InsertAfter(POSITION position， ARG_TYPE newElement);

// helper functions (note: O(n) speed)

POSITION Find(ARG_TYPE searchValue， POSITION startAfter = NULL) const;

// defaults to starting at the HEAD， return NULL if not found

POSITION FindIndex(int nIndex) const;

// get the 'nIndex'th element (may return NULL)

protected:

Cnode* m_pNodeHead;

Cnode* m_pNodeTail;

int m_nCount;

Cnode* NewNode();

void FreeNode(Cnode* pNode);

pthread_rwlock_t m_ListRWLock;

// Operators

public:

Clist operator = (const Clist newList);

};

2.2 線程安全性要求

程序員在使用鏈表類的時候，一般會進行增加、刪除鏈表節(jié)點，修改指定節(jié)點數(shù)據(jù)內(nèi)容，根據(jù)條件查找和定位某個節(jié)點。簡單概括可以分為兩大類，即對鏈表進行讀和寫操作。在多線程程序中，經(jīng)常會出現(xiàn)線程共享資源。共享資源可能會被多個線程同時訪問，可以是任何計算機中任何邏輯上或者物理上的資源，例如鏈表就是一種邏輯資源。當多個線程需要同時訪問同一個資源的時候，可能會對資源本身造成破壞或者不能正常和正確使用資源。例如線程T1查找到了整數(shù)鏈表中的某個值為5的節(jié)點，正要修改該節(jié)點的值的時候，線程T2可能也會同時訪問該鏈表。如果沒有同步訪問控制機制存在，T2把該節(jié)點刪除了，T1的修改操作就會失敗。這個后果輕則會導致程序出現(xiàn)非預期的運行結(jié)果，重則可能會導致程序非法操作和崩潰。

所以開發(fā)者通常必須在程序里設計很多用于同步訪問線程共享資源的代碼。讓線程T1訪問鏈表的時候，線程T2處于等待狀態(tài)。同步訪問控制是一種通過加鎖和等待，來協(xié)調(diào)不同訪問者同時訪問共享資源的機制，用于保證同一時刻只能有一個訪問者能夠獲取和操作資源，避免不同訪問者同時操作共享資源而帶來的問題。

多線程程序是很普遍的，所以大部分數(shù)據(jù)結(jié)構(gòu)設計者努力使他們的代碼實現(xiàn)在線程環(huán)境中可以正常工作。但是，即使再好的數(shù)據(jù)結(jié)構(gòu)設計，仍然會使得大部分工作落在使用者肩上。理解為什么會這樣是很重要的。大體上說，使用者能從實現(xiàn)里確定的最多是下列內(nèi)容：

讀共享，讀寫互斥，寫寫互斥。多個讀取者共同讀取數(shù)據(jù)是安全的。多線程可能同時讀取一個容器的內(nèi)容。在讀取操作進行時不能對容器進行任何寫入操作。

多個寫入者對不同容器的寫入操作是安全的。多線程可以同時對不同的容器進行寫入。

能夠做到的其實就這些了。由于多線程的同步代碼編寫起來有一定的難度，所以很多程序員都希望數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)直接就是線程安全的，也就是說使用者可以完全不用考慮和編寫線程同步控制代碼。

3 線程安全性設計的局限

3.1 理論上的局限性

對于鏈表的設計者來說，可能會試圖在幾個方面實現(xiàn)完全線程安全的容器。注意下面很重要的四點：

1）使用讀寫鎖機制進行同步控制。實現(xiàn)高效讀操作和安全寫操作；

2）在每次操作容器的期間都要鎖定容器；

3）容器返回的引用迭代子在生存期之內(nèi)要鎖定容器；

4）在調(diào)用容器的方法期間要鎖定容器。

看起來只要滿足以上四點，該容器就能讓外部使用者實現(xiàn)他們所想要的結(jié)果。但是問題是，第4點在實際上是沒有意義的。因為，容器的算法沒有辦法識別出它們正在操作的容器，更沒有辦法得知外部使用者的程序塊和邏輯。下面將檢驗這一點，它的重要性在于說明為什么上述事情是可能的但卻沒有意義。

3.2 理論的驗證

首先說明，CList已經(jīng)在內(nèi)部實現(xiàn)了操作的原子化，亦即在單個方法內(nèi)部保證了操作的互斥性。觀察下面的代碼：

// Find an element's position， start after a given position

template

POSITION CList::Find(ARG_TYPE searchValue，

POSITION startAfter) const

{bool bFound = 1;

CNode* pNode = (CNode*) startAfter;

pthread_rwlock_rdlock((pthread_rwlock_t*) m_ListRWLock);

if (pNode == NULL) {pNode = m_pNodeHead;// start at head}

else {pNode = pNode->pNext;// start after the one specified}

for (; pNode != NULL; pNode = pNode->pNext)

if ((pNode->data) == searchValue) {

bFound = true;

break;}

pthread_rwlock_unlock((pthread_rwlock_t*) m_ListRWLock);

if (bFound)

return (POSITION)pNode;

return NULL;}

Find()和SetAt()方法分別用于查找節(jié)點和設置指定節(jié)點的值。可以看到，這兩個方法都使用POSIX標準中的讀寫鎖對共享資源進行了同步控制，保證自己的操作不會和其它的操作沖突。這意味著實現(xiàn)了操作的“原子化”，也可以說實現(xiàn)了需求中談到的1、2、3點。

現(xiàn)在考慮下列CList使用者的代碼。它利用Find和SetAt方法搜尋一個CList中第一次出現(xiàn)6這個值的地方，而且，如果它找到了，就把這個值改為0。

CList nList;

……

// 給初始化鏈表和賦值

……

POSITION p = nList.Find(6);// 行1

if (p != Null) {// 行2

nList.SetAt(p，0);// 行3}

假設多線程環(huán)境有兩個線程T1和T2。T1執(zhí)行完上述代碼行1后，T2修改了nList中的數(shù)據(jù)。此時T1執(zhí)行行3將是無意義的，因為p的值可能已經(jīng)無效了。如果T1繼續(xù)堅持執(zhí)行行3，可能會訪問到無效的內(nèi)存地址，導致程序行為異常或者直接崩潰。

要讓上面的代碼成為線程安全的，nList必須從行1到行3保持鎖定，很難想象CList的實現(xiàn)能夠自動推斷出這個結(jié)果。而且同步原語（例如，信號燈，互斥量，等等）通常開銷很大，在程序沒有明顯性能損失的情況下也很難實現(xiàn)前面所說的第4點。

為了解決上面例子中的問題，不得不對使用者的3行代碼進行并行控制。

CList nList;

Pthread_rwlock_t rwList;

……

// 給初始化鏈表和賦值

……

pthread_rwlock_wrlock(rwList);

POSITION p = nList.Find(6); // 行1

if (p != Null) { // 行2

nList.SetAt(p， 0); // 行3}

pthread_rwlock_unlock(rwList);

這樣就能夠保證使用者的這3行程序不會因為線程同步而出問題。從這里也能看到，外部已經(jīng)使用了并行控制，正如前面提到的，讀寫鎖的操作會消耗很大的系統(tǒng)資源和犧牲運行速度，如果CList內(nèi)部還繼續(xù)保留讀寫鎖的控制，則會更大程度的影響系統(tǒng)性能，并且屬于毫無意義的行為。

4 結(jié)論

在上述例子中可以看到，性能下降只能帶來極為有限的線程安全性保證。還不如徹底放棄這點幾乎沒有意義的線程安全性設計，轉(zhuǎn)而提高整個數(shù)據(jù)結(jié)構(gòu)的性能。所以根本沒有必要在CList內(nèi)部設計任何線程同步機制。追求完美的設計者往往期待設計出方便使用的數(shù)據(jù)結(jié)構(gòu)，同時提供最佳的線程安全性保護。但是理想和現(xiàn)實總是存在著距離。數(shù)據(jù)結(jié)構(gòu)容器設計者在追求性能和線程安全性的同時，需要認識到并不是所有方面都可以做到完美。

參考文獻：

[1] Meyers S.Effective STL[M].Addison-Wesley，2007.

[2] Weiss M A.數(shù)據(jù)結(jié)構(gòu)與算法分析-C語言描述[M].北京:機械工業(yè)出版社，2007.

[3] IEEE POSIX Standard[EB/OL].http://standards.ieee.org.