이 접근법에서 기본적인 허점을 보여주는 문제 만 설명하려고합니다.
지금은 삽입 조작 만 지원하고 다른 조작은 지원하지 않는다고 가정하십시오. 삽입 작업의 구현 될 수있다 다음은 마지막 노드 (잎 노드)의 아이들이 값을 삽입하고 업데이 트하기 때문에,이 방법에서
//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을 고려 그러나 :
10
/\
5 15
/\/\
2 6 13 20
은 가정하자 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, g 모두 T1 및 T2 서로의 존재를 알지 못하고 임계 영역에 진입하고있다H에서 볼 수 있듯이. 코드가이를 허용하지 않았습니다.
무엇이 문제입니까?
문제는 한 번에 실행되도록했는데 코드 조각 있다는 것입니다 :
20 while(root->rightLock);
21 if(!root->right){
22 root->rightLock = true;
그래서 우리는 3 작업을 실행하는 우리 자신의 무정전 지시를함으로써 일부 하드웨어 제어를 필요로 할 수는 함께 위에서 언급 한.
요소를 삽입 한 후에 트리가 변경되지만 새로운 검색은 루트가 아닌 특정 노드에서 시작할 수 있다는 것을 알고 있습니다. 이것은 엄청난 수의 요소를 삽입 할 때 시간에 영향을줍니다. 위치 찾기 작업은 경로의 첫 번째 노드가 잠길 때까지만 병렬 처리됩니다. 루트의 다른면에 삽입 할 값은 여전히 병렬로 검색 할 수 있습니다. p 스레드의 'p'시간 성능을 기대하지는 않지만 순차적 인 것보다 좋을 것입니다. – LearningToCode
@LearningToCode는 새로운 검색이 특정 노드에서 시작될 수 있다는 것과 일치하며 동시에 상당한 수의 스레드에 적용될 수 없습니다. 그래서 유일한 편리한 솔루션은 처음부터 시작될 것입니다. 그렇지 않으면 계속하기 위해 여러 노드를 전환하는 시간을 낭비하고 있습니다. 두 번째 요점이 맞습니다. 그 영향을 분석 할 시간을주십시오. :)) –