二進制搜索樹（BST）中的多線程插入

Question

我有一個將多個元素插入BST的任務。該任務必須通過使用多個線程進行優化。有多少線程可以啓動沒有限制。

這是我的方法。這是一種理論方法。我還沒有嘗試過實施它，並且不知道它會在多大程度上起作用。請提出你對這個想法的意見。

的BST節點將是這個樣子：

class BSTNode { 
    int val; 
    BSTNode left, right; 
    boolean leftLock, rightLock; 
    Queue<BSTNode> leftQ, rightQ; 
} 

我沒有使用任何Java鎖，而使用兩個布爾變量來表示鎖的狀態。

由於插入任何元素首先要求我們找到相關位置，因此這個任務可以並行執行，因爲這不會修改樹。該任務只能工作，直到路徑上的節點解鎖。如果一個特定的節點被鎖定，那麼該特定的插入線程將被放置到sleep()，並被添加到相應的左側或右側隊列，並在釋放鎖定時再次被喚醒。另一方面，如果路徑上的節點沒有鎖定它們，我們可以繼續進行插入。在插入和修改父對應的指針之前，必須在父對象上獲取鎖。

任何人都可以提出他們對這個實現方法的看法嗎？

Answer 1

這實際上是一個試圖實現自己的鎖的練習。你所做的是創建一個解壓縮的鎖（boolean，waitingQueue）。但是，這種方法可以安全地工作的唯一方法是如果你在外部同步對'鎖定'布爾變量和隊列的訪問。所以要使這個非鎖定代碼成功工作，你必須使用一個鎖。

如果你沒有使用鎖，你將不得不與併發幾個問題：

• 沒有之前發生設置任何值的節點之間的關係。也就是說，其他線程都不會看到任何字段的更新值。這僅僅會導致各種麻煩。但是，還有更多具體的例子。
• 沒有線程知道布爾值鎖定的賦值是因爲它改變了值還是任意數量的其他線程改變了值（競態條件）。本質上，沒有線程會知道它是否擁有該鎖。有一個修復這個使用內置的類，但有足夠的其他問題，這是不值得追求。
• 檢查鎖定並將自己插入隊列之間存在另一種競爭條件。一個線程可能會看到另一個線程'擁有'該鎖（對於第二個點來說這是可疑的），並將其自身添加到隊列中。但是，當它自己加入隊列時，鎖可能被解鎖，並且如果沒有其他線程觸摸那部分樹，它可能會等待無限時間。
• 表現欠佳。每個線程一次只能在節點上查看。即使您將布爾/隊列結構轉換爲鎖，您可能也不會有良好的性能，因爲即使在樹上的search（）類型操作將需要使用鎖來確保正確的內存可見性並且發生在關係之前。

如果你想與子線性搜索時間線程安全的，有序的，可變的容器使用ConcurrentSkipListSet <整數>

Answer 2

一個有趣的問題。還有一些地方你必須重新定義你的方法。

由於任何元件插入第一個要求我們找到相關 位置，這個任務可以並行

• 進行其實這是錯誤的。確實，它不會修改樹，但是由於在後臺有一些線程試圖修改這棵樹（插入一個節點），所以你必須在這裏應用一個鎖/信號量。
• 而且您必須通過單個操作insert執行finding a suitable place + actual insertion。原因是，在一個線程（如t1）已完成finding a suitable place，然後嘗試actual insertion但由於另一個線程（如t2）正在執行actual insertion而必須保持開啓的情況下，第一個線程（t1）必須再次進行地點計算，因爲樹在第二個線程（t2）actual insertion後已更改。 （我覺得你有我說的話）

所以在最後，並行插入一個二叉搜索樹將不利於你，因爲二叉搜索樹插入無法單獨從另一個插入進行。

Answer 3

我想解釋只有1個問題，它顯示了這種方法的基本漏洞。

假設您目前僅支持插入操作而不支持其他任何操作。以下可能是插入操作的實現：

//Using C 
BSTNode* insert(BSTNode* root,int value) 
{ 
1 if(root == NULL){ 
2  return createNewNode(value); 
3 } 
4  
5 if(root->data == value){ 
6  return root; 
7 } 
8 else if(root->data > value){ 
9  while(root->leftLock); 
10  if(!root->left){ 
11   root->leftLock = true; 
12   root->left = insert(root->left,value); 
13   root->leftLock = false; 
14  } 
15  else{ 
16   root->left = insert(root->left,value); 
17  } 
18 } 
19 else{ 
20  while(root->rightLock); 
21  if(!root->right){ 
22   root->rightLock = true; 
23   root->right = insert(root->right,value); 
24   root->rightLock = false; 
25  } 
26  else{ 
27   root->right = insert(root->right,value); 
28  } 
29 } 
30  
31 return root; 
32  
} 

在這種方法中，因爲只有最後一個節點（葉節點）的孩子會在插入值得到更新，所以我們沒有做任何鎖定，同時更新父母（當反覆回來時）。

我正在避免插入請求排隊和使用自旋鎖只是爲了保持它有點簡單。但是我將要加薪都是一樣的那種情況下的點...

考慮這個BST：

​​

假設2個線程T1和T2調用試圖同時分別插入值25和26並且當前處於值爲20的BSTNode。 （最右邊的節點）。

現在讓與螺紋之間的上下文切換執行上面的代碼：

a. t1: 
      1. if(root == NULL) //not true, will go to line 5. 
      //switch 

b. t2: 
      1. if(root == NULL) //not true, will go to line 5. 
      //switch 

c. t1: 
      5. if(root->data == value){ //not true, will go to line 8. 
      8. else if(root->data > value) //not true, will go to line 19. 
      //switch 

d. t2: 
      5. if(root->data == value){ //not true, will go to line 8. 
      //switch 

e. t1: 
      19 else{ 
      20  while(root->rightLock); // lock is not held by anyone, so continue. 
      21  if(!root->right){ 
      //switch 
f. t2: 
      8. else if(root->data > value) //not true, will go to line 19. 
      19 else{ 
      20  while(root->rightLock); // lock is not helpd by anyone, so continue. 
      21  if(!root->right){ 
      22   root->rightLock = true; 
      //switch 

g. t1: 
      22   root->rightLock = true; 
      23   root->right = insert(root->right,value); 
      //switch 

h. t2: 
      23   root->right = insert(root->right,value); 
      24   root->rightLock = false; 
      //switch 

假設線23覆蓋該行的完全執行。

正如你可以在部分˚F，克和ħ兩個T1和T2正在進入臨界區不知道彼此的存在看到。代碼不應該允許這樣做。

那麼問題呢？

的問題是，有一段代碼，這本來是一個去要執行：

20  while(root->rightLock); 
21  if(!root->right){ 
22   root->rightLock = true; 

因此，我們可以通過使我們自己的不間斷指令，執行所有3個任務需要一些硬件控制如上所述。