락 프리(lock free) (4) 썸네일형 리스트형 4. 락프리 스택 기본 구현체의 문제 1 (ABA 문제 확인, 수정) ABA 문제 이전 포스팅에서 ABA 문제가 발생 가능한 시나리오와 ABA문제로 인하여 스택의 상태가 실제로 꼬이는 문제를 확인하였다. ABA문제는 잘 알려진 문제 이기 때문에 wiki 뿐만 아니라 다양한 블로그와 홈페이지에서 다루고 있으며 해결책 또한 한두 가지가 아니다. ABA problem - Wikipedia From Wikipedia, the free encyclopedia Multithreading computing anomaly In multithreaded computing, the ABA problem occurs during synchronization, when a location is read twice, has the same value for both reads, and the r.. 3. 락프리 스택의 문제 추론 (문제점 정리와 사고실험, 로깅) 이전 테스트의 문제점 정리 Java 예제코드를 c++로 포팅하여 구현한 락프리 스택을 테스트해 본 결과 다음과 같은 문제점이 발생했다. 1. N회 push한 뒤, N회 pop을 하였으나 pop에 실패했다. (= popNode 가 nullptr이 되었다.) 2. pop 과정에서 node를 반환하는 과정에서 힙이 손상되었다는 런타임 에러가 발생했다. 3. pop한 결과에 중복된 값이 포함되어 있다. 이 문제점을 대상으로 추론 및 사고실험을 진행한다. atomic 보다는 interlocked 쪽이 조금 더 동작을 하나씩 뜯기도 쉽고, 기존 둘중 한가지만 알고 있다면 interlocked만 이해한 채로 atomic을 보는 것 보다 atomic만 이해한채로 interlocked를 보는 것이 더 쉽기 때문에 int.. 2. 락프리 스택의 기본 구현 (참고코드 첨부 및 그 구현, 테스트 코드 작성) 락프리 스택의 참고코드와 그 구현 the art of multiprocessor programming 서적을 참고한 락프리 스택의 Java 코드는 다음과 같다. public class Node { public T value; public Node next; public Node(T value) { value = value; next = null; } } public class LockFreeStack { AtomicReference top = new AtomicReference(null); static final int MIN_DELAY = ...; static final int MAX_DELAY = ...; Backoff backoff = new Backoff(MIN_DELAY, MAX_DELAY); .. 1. 락 프리(lock free) 카테고리 설명 및 목차 본 카테고리에서는 여러 스레드가 공용 자원 (큐, 스택)을 사용함에 있어 이를 안전하게 사용하기 위한 여러 가지 방법 중 스레드를 block 시키지 않은 채 thread safety를 보장할 수 있는 방법인 락프리 알고리즘을 이용해 스택과 큐를 c++로 구현하고자 합니다. 락프리에 대한 설명 자체는 위키나 다른 블로그 등에서 다수 소개되고 있기 때문에 간단한 설명은 가능한 적게 할 것입니다. 대신 실제 구현함에 있어 알려진 문제들 (ABA 문제, 메모리 재사용 문제 등)을 직접 찾아보고, 어떻게 찾았나 공유하며 만들어진 자료구조의 성능을 테스트하는 등 다른 글에서 잘 다루지 않는 내용을 위주로 정리하려 합니다. 학습, 분석한 내용을 바탕으로 정리한 글 이므로 실제 이론과 다르거나 잘못 분석한 내용이 있을.. 이전 1 다음
