사실 EBR에 대해서 이해가 완벽하지 않아서, 수업중 진행했던 EBR Set (그냥 list) 를 다시 보면서 이해를 도우려고 했다.

하지만 아직도 왜 EBR이 작동하는지 이해하지 못한 것 같다. Epoch 시간을 측정해서 현재 노드가 재사용 가능한지 알 수 있는가? 해당 노드가 물리적인 리스트에 남아 있다면 어떤 스레드든 Access 할 가능성이 있지 않은가?

Epoch Based Reuse(Reclamation)로 재사용 가능한지를 판단함에 있어서 Remove된 노드를 가리키는 (Access 하는) 스레드가 존재하지 않는다는 아이디어로, 해당 메소드가 실행되는 동안 실행 시간이 겹치는 메서드들이 모두 종료된 뒤 시간에서 재활용 가능하다고 판단을 하는 것이다.

Skip List Lock Free 버전에도 일단 EBR을 적용시키기 위해 러프하게 Set에서 사용했던 방식을 적용해 보려고 한다 (24-12-29 EBR을 적용하기 위한 시도 commit)

그렇게 시도를 해보았지만 무한루프에 걸리거나 프로그램이 종료되는 오류를 확인할 수 있었다

이에 대한 고찰로, 일반 Set에서 연결리스트는 Skip List의 구조가 아니라 지름길 같은 경로가 추가로 있지 않아서 한번에 CAS(find)로 연결리스트에 존재하는 제거(marking)된 노드를 제거할 수 있었지만, Skip List에서는 그렇지 못한 것으로 판단된다. (여러 층의 경로가 존재하기에)

그렇기에 연결리스트에 marking 뿐만 아니라 실제로 연결리스트에서 제거되어 있는지를 추가로 판단해야 하지 않을까 하는 생각이 든다.

우선 코드에서 아래와 같은 코드를 통해서 다음 노드에 접근하려고 했는데

SK_SPTR* volatile next[MAX_TOP + 1] = {};

이는 성긴 동기화 Skip List와 게으른 동기화 Skip List에서의 next 접근 방식이였던,

SK_NODE* volatile next[MAX_TOP + 1] = {};

에서의 접근 방식이였던 해당 구조체의 포인터를 저장하는 방식이 이제 합성 포인터인 SPTR 방식으로 바뀌어 아래와 같이 바뀌었어야 했지만 필자의 이해도 부족으로 잘못된 사용법으로 코드를 작성했던 것 같다.

SK_SPTR next[MAX_TOP + 1] = {};

따라서 위와 같이 코드를 수정하는 작업을 진행하였다.

다시 EBR로 돌아와서 Node가 삭제되었음을 의미하는 Marking 말고도 연결리스트에서 실제로 제거되었는지(물리적으로 배제 : 연결이 끊긴 노드)를 판단하기위해서 생각을 해보고 아이디어를 기준으로 생각을 해보았다.