[06~08주차] Non-Blocking 알고리즘 - LIST

 

- SET

 : 아이템의 중복을 허용하지 않음

 : 정렬되어 저장됨 (unordered_set이 아님) - 검색 효율 증가

 : 삽입 삭제의 효율성을 위해 링크드리스트 구현

 : 구현 ) add, remove, contains

 : 필드 ) 리스트에 저장되는 값 

 : 메서드

 - add(x) : 집합에 x추가, 성공 시 true

 - remove(x) : 집합에서 x 제거, 성공 시 true

 - contains(x) : 집합에 x가 있다면 true

 

 : 추가 구현 ) 보초 노드 - 검색 효율을 위해 항상 존재하는 Head(MAXINT)와 Tail노드(-MAXINT)를 갖도록 함

 

 

 

- 성긴 동기화

 : 리스트는 하나의 잠금을 가짐

 : 모든 매서드 호출은 이 잠금을 통해 Critical Section으로 진행됨 ( = 모든 매서드는 잠금을 갖는 동안에만 리스트에 접근)

 : 문제 ) 경쟁이 낮은 경우 선택하면 좋음. 경쟁이 높을 경우 성능 저하 / Blocking

 

constexpr int MAX_THREADS = 16; // 최대 쓰레드 수를 상수로 정의

class NODE {
	std::mutex  nl; // 각 노드에 대한 뮤텍스
public:
	int v; // 노드의 값
	NODE* next; // 다음 노드의 포인터
	bool removed; // 삭제 여부를 나타내는 플래그
	NODE() : v(-1), next(nullptr), removed(false) {} 
	NODE(int x) : v(x), next(nullptr), removed(false) {} 
	void Lock() // 노드 락 함수
	{
		nl.lock();
	}
	void Unlock() // 노드 언락 함수
	{
		nl.unlock();
	}
};

class SET {
	NODE head, tail; // 헤드와 테일 노드
	mutex ll; // 전역 뮤텍스
public:
	SET() 
	{
		head.v = 0x80000000; // 헤드의 값 초기화
		tail.v = 0x7FFFFFFF; // 테일의 값 초기화
		head.next = &tail; // 헤드의 다음 노드를 테일로 설정
	}

	bool ADD(int x) // 삽입 연산
	{
		NODE* prev = &head;
		ll.lock(); // 전역 락 획득
		NODE* curr = prev->next;
		while (curr->v < x) { // 정렬된 위치 찾기
			prev = curr;
			curr = curr->next;
		}
		if (curr->v != x) { // 중복된 값이 없을 때
			NODE* node = new NODE{ x }; // 새로운 노드 생성
			node->next = curr; // 새로운 노드를 연결
			prev->next = node; // 이전 노드와 새로운 노드 연결
			ll.unlock(); // 전역 락 해제
			return true;
		}
		else // 이미 존재하는 값일 때
		{
			ll.unlock(); // 전역 락 해제
			return false;
		}
	}

	bool REMOVE(int x) // 삭제 연산
	{
		NODE* prev = &head;
		ll.lock(); // 전역 락 획득
		NODE* curr = prev->next;
		while (curr->v < x) { // 삭제할 값 위치 찾기
			prev = curr;
			curr = curr->next;
		}
		if (curr->v != x) { // 삭제할 값이 존재하지 않을 때
			ll.unlock(); // 전역 락 해제
			return false;
		}
		else { // 삭제할 값이 존재할 때
			prev->next = curr->next; // 이전 노드와 다음 노드를 연결
			delete curr; // 노드 삭제
			ll.unlock(); // 전역 락 해제
			return true;
		}
	}

	bool CONTAINS(int x) // 검색 연산
	{
		NODE* prev = &head;
		ll.lock(); // 전역 락 획득
		NODE* curr = prev->next;
		while (curr->v < x) { // 검색할 값 위치 찾기
			prev = curr;
			curr = curr->next;
		}
		bool res = (curr->v == x); // 값 존재 여부 확인
		ll.unlock(); // 전역 락 해제
		return res;
	}

	void print20() // 처음 20개의 노드 값 출력
	{
		NODE* p = head.next;
		for (int i = 0; i < 20; ++i) {
			if (p == &tail) break;
			cout << p->v << ", ";
			p = p->next;
		}
		cout << endl;
	}

	void clear() // 전체 노드 삭제
	{
		NODE* p = head.next;
		while (p != &tail) {
			NODE* t = p;
			p = p->next;
			delete t;
		}
		head.next = &tail;
	}
};

 

성긴 동기화

 

 : 구현

 - pred와 curr를 사용한 add&remove

 

 

 

- 세밀한 동기화 

 : 전체 리스트를 한 번에 잠그는 것보다 개별 노드를 잠그는 것이 병행성 향상

 : 각각의 노드에 잠금을 둠

 : Node의 next field를 변경 시 반드시 Lock()을 얻은 후 변경

 : 주의점

  - Add, Remove 시점의 Pred, Curr가 가리키는 노드는 Locking 되어야 함

  - Head부터 Node 이동 시 Lock을 잠그면서 이동 필요

class F_SET {
	NODE head, tail;
public:
	F_SET()
	{
		head.v = 0x80000000;
		tail.v = 0x7FFFFFFF;
		head.next = &tail;
	}
    
	bool ADD(int x)
	{
		NODE* prev = &head;
		prev->Lock();   // 1. 헤드 락 잠금
		NODE* curr = prev->next;
		curr->Lock();   // 2. 헤드의 다음 노드의 락 잠금
		while (curr->v < x) {
			prev->Unlock();  // 3. 이전 노드 락 해제
			prev = curr;
			curr = curr->next;  // 4. 새로운 현재 노드 락 잠금
			curr->Lock();
		}
		if (curr->v != x) {
			NODE* node = new NODE{ x };
			node->next = curr;
			prev->next = node;
			prev->Unlock(); curr->Unlock();  // 5. 이전과 현재 노드 락 해제
			return true;
		}
		else
		{
			prev->Unlock(); curr->Unlock();  
			return false;
		}
	}

	bool REMOVE(int x)
	{
		NODE* prev = &head;
		prev->Lock();
		NODE* curr = prev->next;
		curr->Lock();
		while (curr->v < x) {
			prev->Unlock();
			prev = curr;
			curr = curr->next;
			curr->Lock();
		}
		if (curr->v != x) {
			prev->Unlock(); curr->Unlock();
			return false;
		}
		else {
			prev->next = curr->next;
			prev->Unlock(); curr->Unlock();
			delete curr;
			return true;
		}
	}

	bool CONTAINS(int x)
	{
		NODE* prev = &head;
		prev->Lock();
		NODE* curr = prev->next;
		curr->Lock();
		while (curr->v < x) {
			prev->Unlock();
			prev = curr;
			curr = curr->next;
			curr->Lock();
		}
		bool res = (curr->v == x);
		prev->Unlock(); curr->Unlock();
		return res;
	}
    
	void print20()
	{
		NODE* p = head.next;
		for (int i = 0; i < 20; ++i) {
			if (p == &tail) break;
			cout << p->v << ", ";
			p = p->next;
		}
		cout << endl;
	}

	void clear()
	{
		NODE* p = head.next;
		while (p != &tail) {
			NODE* t = p;
			p = p->next;
			delete t;
		}
		head.next = &tail;
	}
};

 

세밀한 동기화

 

 : 성능 저하 원인

  - 잠금의 획득과 해제가 빈번, 리스트가 길어지는 경우 성능이 매우 떨어짐

  → 이동 시 잠금을 하지 않는다?  : DataRace

 

 - Crash ( or 무한루프 ) : 제거된 Node라도 next를 따라가면 tail이 나오게 함 (vaildation)

 - 오동작 : pred와 curr를 잠근 후 제대로 잠갔는지 검사하고 잘못 잠궜으면 처음부터 다시 실행

 

 

 

- 낙천적 동기화

 : 제거된 노드를 'delete' 하지 않음 (next 필드의 오염 방지)

 : Memory Leak 발생

 : vaildation 조건 검사

  - pred, curr가 리스트에 존재한다 / pred와 curr 사이에 다른 노드가 없음

 : 기아 발생 확률 존재 (다른 쓰레드가 pred와 curr를 계속 수정하는 경우 계속 재시도를 하면서 지연)

class O_SET {
	NODE head, tail;
public:
	O_SET()
	{
		head.v = 0x80000000;
		tail.v = 0x7FFFFFFF;
		head.next = &tail;
	}

	bool validate(const NODE* prev, const NODE* curr) // 현재 노드와 이전 노드가 유효한 순서를 가지는지 확인
	{
		NODE* ptr = &head;
		while (ptr->v <= prev->v) {
			if (ptr == prev)
				return ptr->next == curr;
			ptr = ptr->next;
		}
		return false;
	}

	bool ADD(int x)
	{
		while (true) {
			NODE* prev = &head;
			NODE* curr = prev->next;
			while (curr->v < x) {
				prev = curr;
				curr = curr->next;
			}
			prev->Lock(); curr->Lock(); // 이전 노드와 현재 노드의 락을 잠금
            
			if (true == validate(prev, curr)) {  // 노드의 유효성을 검증하고 유효한 경우
				if (curr->v != x) {
					NODE* node = new NODE{ x };
					node->next = curr;
					prev->next = node;
					prev->Unlock(); curr->Unlock();  // 락 해제
					return true;
				}
				else
				{
					prev->Unlock(); curr->Unlock();  // 락 해제
					return false;
				}
			}
			else {
				prev->Unlock(); curr->Unlock();   // 락 해제
			}
		}
	}

	bool REMOVE(int x)
	{
		while (true) {
			NODE* prev = &head;
			NODE* curr = prev->next;
			while (curr->v < x) {
				prev = curr;
				curr = curr->next;
			}
			prev->Lock(); curr->Lock();
            
			if (true == validate(prev, curr)) { // 노드가 유효한 경우 삭제
				if (curr->v != x) {
					prev->Unlock(); curr->Unlock();
					return false;
				}
				else {
					prev->next = curr->next;
					prev->Unlock(); curr->Unlock();
					// delete curr;
					return true;
				}
			}
			else {
				prev->Unlock(); curr->Unlock();
			}
		}
	}

	bool CONTAINS(int x)
	{
		while (true) {
			NODE* prev = &head;
			NODE* curr = prev->next;
			while (curr->v < x) {
				prev = curr;
				curr = curr->next;
			}
			prev->Lock(); curr->Lock();
			if (true == validate(prev, curr)) {
				bool res = (curr->v == x);
				prev->Unlock(); curr->Unlock();
				return res;
			}
			else {
				prev->Unlock(); curr->Unlock();
			}
		}
	}

	void print20()
	{
		NODE* p = head.next;
		for (int i = 0; i < 20; ++i) {
			if (p == &tail) break;
			cout << p->v << ", ";
			p = p->next;
		}
		cout << endl;
	}

	void clear()
	{
		NODE* p = head.next;
		while (p != &tail) {
			NODE* t = p;
			p = p->next;
			delete t;
		}
		head.next = &tail;
	}
};

 

낙천적 동기화

 

 : Lock의 횟수는 비약적으로 감소하나, 리스트를 두 번 순회해야 함(오버헤드)

 → 다시 순회하지 않는 알고리즘 작성 필요

 

 

 

- 게으른 동기화

 : Contains() 메소드는 자주 호출되는 메소드인데..  Wait-Free면 좋겠..

 : 각 노드에 marked 필드를 추가해 그 노드가 집합에서 제거되었는지 표시

  - marked == true : 제거됨

  - marking 실제 제거 보다 반드시 먼저 수행 ( + 잠금을 획득한 후 수행)

  - marking 되어 있지 않은 모든 Node는 실제 리스트에 존재하는(살아있는) Node!!!

class Z_SET {
	NODE head, tail;
public:
	Z_SET()
	{
		head.v = 0x80000000;
		tail.v = 0x7FFFFFFF;
		head.next = &tail;
	}

	bool validate(const NODE* prev, const NODE* curr)
	{
		return (false == prev->removed)  // 이전 노드가 제거되지 않았는지 확인
			&& (false == curr->removed)  // 현재 노드가 제거되지 않았는지 확인
			&& (prev->next == curr);  // 이전 노드의 다음 노드가 현재 노드인지 확인
	}

	bool ADD(int x)
	{
		while (true) {
			NODE* prev = &head;
			NODE* curr = prev->next;
			while (curr->v < x) {
				prev = curr;
				curr = curr->next;
			}
			prev->Lock(); curr->Lock();
			if (true == validate(prev, curr)) {
				if (curr->v != x) {
					NODE* node = new NODE{ x };
					node->next = curr;
					prev->next = node;
					prev->Unlock(); curr->Unlock();
					return true;
				}
				else
				{
					prev->Unlock(); curr->Unlock();
					return false;
				}
			}
			else {
				prev->Unlock(); curr->Unlock();
			}
		}
	}

	bool REMOVE(int x)
	{
		while (true) {
			NODE* prev = &head;
			NODE* curr = prev->next;
			while (curr->v < x) {
				prev = curr;
				curr = curr->next;
			}
			prev->Lock(); curr->Lock();
			if (true == validate(prev, curr)) {
				if (curr->v != x) {
					prev->Unlock(); curr->Unlock();
					return false;
				}
				else {
					curr->removed = true;
					prev->next = curr->next;
					prev->Unlock(); curr->Unlock();
					// delete curr;
					return true;
				}
			}
			else {
				prev->Unlock(); curr->Unlock();
			}
		}
	}

	bool CONTAINS(int x)
	{
		NODE* curr = head.next;
		while (curr->v < x) {
			curr = curr->next;
		}
		return (curr->v == x) && (false == curr->removed);
	}

	void print20()
	{
		NODE* p = head.next;
		for (int i = 0; i < 20; ++i) {
			if (p == &tail) break;
			cout << p->v << ", ";
			p = p->next;
		}
		cout << endl;
	}

	void clear()
	{
		NODE* p = head.next;
		while (p != &tail) {
			NODE* t = p;
			p = p->next;
			delete t;
		}
		head.next = &tail;
	}
};

 

게으른 동기화

 

 

  : 일단 Blocking이다

  : Convoying  - 한 쓰레드가 Lock을 얻은 채로 지연되면, 다른 쓰레드 역시 지연되게 됨

 

 

 

- 메모리 릭(메모리 누수) 해결

 : Free List

  - Delete 하지 않고 모아 놓음 → marking이 해제 되는 순간 오작동 가능

  - 언젠가는 재사용 → 아무도 remove된 node를 가리키지 않을 때

 

 : shared_ptr 

  - 아무도 가리키지 않는 노드 제거에 적합

  - 객체에 reference counter를 두고 이를 통해 앞으로 쓰이지 않을 객체를 판별해서 자동 삭제하는 원리

  - Node의 next를 이것으로 구현

class SP_NODE {
	std::mutex  nl;
public:
	int v;
	shared_ptr<SP_NODE> next;
	bool removed;
	SP_NODE() : v(-1), next(nullptr), removed(false) {}
	SP_NODE(int x) : v(x), next(nullptr), removed(false) {}
	void Lock()
	{
		nl.lock();
	}
	void Unlock()
	{
		nl.unlock();
	}
};

class ZSP_SET {
	std::shared_ptr <SP_NODE> head, tail;
public:
	ZSP_SET()
	{
		head = make_shared<SP_NODE>(0x80000000);
		tail = make_shared<SP_NODE>(0x7FFFFFFF);
		head->next = tail;
	}

	bool validate(const shared_ptr<SP_NODE>& prev,
		const shared_ptr<SP_NODE>& curr)
	{
		return (false == prev->removed)
			&& (false == curr->removed)
			&& (prev->next == curr);
	}

	bool ADD(int x)
	{
		while (true) {
			shared_ptr<SP_NODE> prev = head;
			shared_ptr<SP_NODE> curr = prev->next;
			while (curr->v < x) {
				prev = curr;
				curr = curr->next;
			}
			prev->Lock(); curr->Lock();
			if (true == validate(prev, curr)) {
				if (curr->v != x) {
					shared_ptr<SP_NODE> node = make_shared<SP_NODE>(x);
					node->next = curr;
					prev->next = node;
					prev->Unlock(); curr->Unlock();
					return true;
				}
				else
				{
					prev->Unlock(); curr->Unlock();
					return false;
				}
			}
			else {
				prev->Unlock(); curr->Unlock();
			}
		}
	}

	bool REMOVE(int x)
	{
		while (true) {
			shared_ptr<SP_NODE> prev = head;
			shared_ptr<SP_NODE> curr = prev->next;
			while (curr->v < x) {
				prev = curr;
				curr = curr->next;
			}
			prev->Lock(); curr->Lock();
			if (true == validate(prev, curr)) {
				if (curr->v != x) {
					prev->Unlock(); curr->Unlock();
					return false;
				}
				else {
					curr->removed = true;
					prev->next = curr->next;
					prev->Unlock(); curr->Unlock();
					return true;
				}
			}
			else {
				prev->Unlock(); curr->Unlock();
			}
		}
	}

	bool CONTAINS(int x)
	{
		shared_ptr<SP_NODE> curr = head->next;
		while (curr->v < x) {
			curr = curr->next;
		}
		return (curr->v == x) && (false == curr->removed);
	}

	void print20()
	{
		shared_ptr<SP_NODE> p = head->next;
		for (int i = 0; i < 20; ++i) {
			if (p == tail) break;
			cout << p->v << ", ";
			p = p->next;
		}
		cout << endl;
	}

	void clear()
	{
		head->next = tail;
	}
};

 

게으른 동기화 + shared_ptr

 

 

 : 돌아가는가? No!

  - shared_ptr 객체를 load, store 하는 것은 atomic이 아님  (auto curr = prev->next 이거 DATA RACE)

  → 공유하는 shared_ptr 객체를 atomic하게 수행한다 (atomic_load, atomic_exchange)

 

class ZSP_SET2 {
	std::shared_ptr <SP_NODE> head, tail;
public:
	ZSP_SET2()
	{
		head = make_shared<SP_NODE>(0x80000000);
		tail = make_shared<SP_NODE>(0x7FFFFFFF);
		head->next = tail;
	}

	bool validate(const shared_ptr<SP_NODE>& prev,
		const shared_ptr<SP_NODE>& curr)
	{
		return (false == prev->removed)
			&& (false == curr->removed)
			&& (prev->next == curr);
	}

	bool ADD(int x)
	{
		while (true) {
			shared_ptr<SP_NODE> prev = head;
			shared_ptr<SP_NODE> curr = atomic_load(&prev->next);
			while (curr->v < x) {
				prev = curr;
				curr = atomic_load(&curr->next);
			}
			prev->Lock(); curr->Lock();
			if (true == validate(prev, curr)) {
				if (curr->v != x) {
					shared_ptr<SP_NODE> node = make_shared<SP_NODE>(x);
					node->next = curr;
					atomic_exchange(&prev->next, node);
					prev->Unlock(); curr->Unlock();
					return true;
				}
				else
				{
					prev->Unlock(); curr->Unlock();
					return false;
				}
			}
			else {
				prev->Unlock(); curr->Unlock();
			}
		}
	}

	bool REMOVE(int x)
	{
		while (true) {
			shared_ptr<SP_NODE> prev = head;
			shared_ptr<SP_NODE> curr = atomic_load(&prev->next);
			while (curr->v < x) {
				prev = curr;
				curr = atomic_load(&curr->next);
			}
			prev->Lock(); curr->Lock();
			if (true == validate(prev, curr)) {
				if (curr->v != x) {
					prev->Unlock(); curr->Unlock();
					return false;
				}
				else {
					curr->removed = true;
					atomic_exchange(&prev->next, atomic_load(&curr->next));
					prev->Unlock(); curr->Unlock();
					return true;
				}
			}
			else {
				prev->Unlock(); curr->Unlock();
			}
		}
	}

	bool CONTAINS(int x)
	{
		shared_ptr<SP_NODE> curr = atomic_load(&head->next);
		while (curr->v < x) {
			curr = atomic_load(&curr->next);
		}
		return (curr->v == x) && (false == curr->removed);
	}

	void print20()
	{
		shared_ptr<SP_NODE> p = head->next;
		for (int i = 0; i < 20; ++i) {
			if (p == tail) break;
			cout << p->v << ", ";
			p = p->next;
		}
		cout << endl;
	}

	void clear()
	{
		head->next = tail;
	}
};

 

atomic_load & atomic_exchange

 

 

 : 성능 문제 발생

 - atomic_load와 atomic_exchange는 하나의 lock으로 구현되어 있다

  → shared_ptr 각각이 별도의 lock을 갖도록 atomic_shared_ptr를 정의해서 사용

 

class ASP_NODE {
	std::mutex  nl;
public:
	int v;
	atomic<shared_ptr<ASP_NODE>> next;
	bool removed;
	ASP_NODE() : v(-1), next(nullptr), removed(false) {}
	ASP_NODE(int x) : v(x), next(nullptr), removed(false) {}
	void Lock()
	{
		nl.lock();
	}
	void Unlock()
	{
		nl.unlock();
	}
};

class ZSP_SET3 {
	std::atomic<std::shared_ptr <ASP_NODE>> head, tail;
public:
	ZSP_SET3()
	{
		head = make_shared<ASP_NODE>(0x80000000);
		tail = make_shared<ASP_NODE>(0x7FFFFFFF);
		head.load()->next = tail.load();
	}

	bool validate(const shared_ptr<ASP_NODE>& prev,
		const shared_ptr<ASP_NODE>& curr)
	{
		return (false == prev->removed)
			&& (false == curr->removed)
			&& (prev->next.load() == curr);
	}

	bool ADD(int x)
	{
		while (true) {
			shared_ptr<ASP_NODE> prev = head;
			shared_ptr<ASP_NODE> curr = prev->next;
			while (curr->v < x) {
				prev = curr;
				curr = curr->next;
			}
			prev->Lock(); curr->Lock();
			if (true == validate(prev, curr)) {
				if (curr->v != x) {
					shared_ptr<ASP_NODE> node = make_shared<ASP_NODE>(x);
					node->next = curr;
					prev->next = node;
					prev->Unlock(); curr->Unlock();
					return true;
				}
				else
				{
					prev->Unlock(); curr->Unlock();
					return false;
				}
			}
			else {
				prev->Unlock(); curr->Unlock();
			}
		}
	}

	bool REMOVE(int x)
	{
		while (true) {
			shared_ptr<ASP_NODE> prev = head;
			shared_ptr<ASP_NODE> curr = prev->next;
			while (curr->v < x) {
				prev = curr;
				curr = curr->next;
			}
			prev->Lock(); curr->Lock();
			if (true == validate(prev, curr)) {
				if (curr->v != x) {
					prev->Unlock(); curr->Unlock();
					return false;
				}
				else {
					curr->removed = true;
					prev->next.store(curr->next);
					prev->Unlock(); curr->Unlock();
					return true;
				}
			}
			else {
				prev->Unlock(); curr->Unlock();
			}
		}
	}

	bool CONTAINS(int x)
	{
		shared_ptr<ASP_NODE> curr = head.load()->next;
		while (curr->v < x) {
			curr = curr->next;
		}
		return (curr->v == x) && (false == curr->removed);
	}

	void print20()
	{
		shared_ptr<ASP_NODE> p = head.load()->next;
		for (int i = 0; i < 20; ++i) {
			if (p == tail.load()) break;
			cout << p->v << ", ";
			p = p->next;
		}
		cout << endl;
	}

	void clear()
	{
		head.load()->next = tail.load();
	}
};

 

atomic_shared_ptr

 

 

 : C++20부터는 atomic<shared_ptr<T>> 를 지원함 - 근데 blocking 구현이다 ㅠ

 : atomic한 shared_ptr은 느리다 → mutex, blocking!

 

→ 효율적인(non-blocking) atomic_shared_ptr이 필요하다

 

 

 

- Look-free 알고리즘

 : 여러 개의 쓰레드에서 동시에 호출 시 정해진 단위 시간마다 적어도 한 개의 호출이 완료되는 알고리즘

 : 멀티쓰레드에서 동시에 호출해도 정확한 결과를 만들어 주는 알고리즘 (STL X, Atomic한 동작)

 : 사용하지 않으면 다음 문제 발생

  - 병렬성 감소

  - Priority Inversion (우선 순위 역전)

  - Convoying

  - 성능 저하 & 랙

 

 + wait-free 알고리즘 : 호출이 다른 쓰레드와 충돌해도 모두 딜레이 없이 완료됨

 

 

 : Non-blocking 알고리즘 - 다른 쓰레드가 어떤 상태에 있건 상관없이 호출 완료

 : CAS가 없이는 대부분의 non-blocking  알고리즘들을 구현할 수 없음

 

 : CAS(&A, old, new);

 : A의 값이 old면 new로 바꾸고 true를 리턴

 : A메모리를 다른 쓰레드가 먼저 업데이트 해서 false가 나왔다. 모든 것을 포기하라.

 

 

 : 알고리즘이 무척 복잡 → 증명된 알고리즘만 사용하자

 

 

- Non-blocking 구현 (비멈춤 동기화)

 : 게으른 동기화에서 출발

 : Lock 사용 금지 + 서로 충돌하는 thread는 CAS로 승부

 

 : ADD 구현

 

  - 다른 쓰레드가 *pred를 remove ? →  pred의 marking을 확인하면서 변경

  - 다른 쓰레드가 *curr를 remove? → Pred의 mark가 false인 것을 확인하면서 변경

  - 다른 쓰레드가 *pred, *curr 사이에 새로운 노드를 끼워 넣으면? →  pred의 next가 curr인 것을 확인하면서 변경

 

 

 

  - pred와 curr를 locking하지 않기에 발생하는 오류를 검출하려면 next와 marking을 동시에 감시하며 CAS 수행

  → 동시 CAS 구현 한계 : 한 번에 하나의 변수 밖에 바꾸지 못함

  → 한 장소에 주소와 Marking을 동시에 저장하자. (특수 경우에만 사용 가능)

 

 

 : Remove 구현

  - curr를 delete? → curr를 마킹(CAS 사용) → pred의 next를 curr의 next로 변경 (CAS 사용)

  - 문제 ) pred와 curr를 잠글 수 없다.

  → Remove시 제거를 시도, 실패하면 무시 (모든 메소드를 수정)

  → 메소드 호출 시 마킹된 노드를 제거하고 진행 – 제거하면서 검색 (검색시 노드의 삭제를 동시에 행함)

 

 [ 구현 숙제 ]

 

 

- 메모리 릭의 해결방법

 1) Atomic shared_ptr 

  -  (blocking구현) 느려, 지역변수 atomic이 아닌 shared_ptr 사용(포인터 update 많이 하면 X), 함수엔 const reference
 2) stamped pointer
 3) EPOCH (Epoch Based Reuse)
 4) Hazard Pointer (대학원..)