연결 리스트 리스트란? 정의 배열과의 비교 연산 삽입 삭제 접근 종류 / 구현 리스트란? 리스트는 순서를 가진 항목들의 모임이다. 이를 나타내는 대표적인 방법은 2가지가 있는데, 하나는 배열을 이용하는 방법이고 나머지 하나는 연결리스트를 이용하는 방법이다. 배열을 이용한 리스트를 선형리스트라고 하는데 구현 자체는 간단하고 임의접근이 가능하지만, 삽입 / 삭제 연산 시 다른 요소들의 이동이 불가피하므로 오버헤드가 크다. 연결리스트는 구현이 복잡하고 순차접근이 필요하지만 삽입, 삭제가 효율적이다. 정의 연결리스트란 아래의 그림과 같이 데이터와 링크로 이루어진 노드로 구성되어있다. 링크는 다음 요소를 가리키는 포인터이다. 연결리스트의 처음에는 헤드 포인터가 헤드 노드를 가리키고 있으며, 마지막 노드의 링크는 ..

목차 문제 정의 lock free 구현 ABA 해결 int형 구현(+ Hazard pointer) Counter 그 외의 방법들 mutex lock(spin lock)과의 비교 문제 정의 문제 Linked List 자료구조에서 push()와 pop() 연산을 구현한다. Linked List는 FreeList와 HeadList 두가지가 있으며 여러 스레드가 두 개의 List를 번갈아가며 push, pop 연산을 수행한다. 스레드들이 각각 연산을 수행하기 위해서는 List들에 대한 상호배제가 필요하다. 해석 상호 배제에는 여러가지 방법이 있지만, 크게 두가지로 나눌 수 있다. lock 변수의 조건을 체크하며 반복문을 돌고 있는 spin lock과, lock 변수 없이 계속 시도하면서 적절한 때에 동작을 수행..