내 이야기 (70) 썸네일형 리스트형 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 문제, 메모리 재사용 문제 등)을 직접 찾아보고, 어떻게 찾았나 공유하며 만들어진 자료구조의 성능을 테스트하는 등 다른 글에서 잘 다루지 않는 내용을 위주로 정리하려 합니다. 학습, 분석한 내용을 바탕으로 정리한 글 이므로 실제 이론과 다르거나 잘못 분석한 내용이 있을.. 자료구조 구현 : 레드 블랙 트리 (Red Black Tree, RB tree) - 삭제 자료구조 개념 : 레드 블랙 트리 (Red Black Tree, RB tree) 레드 블랙 트리는 일반 이진트리에서 자식들이 한쪽으로 치우치는 것을 막기 위한 균형 기능이 추가된 트리이다. 이를 자가 균형 이진트리(Self-balancing binary tree)라 부른다. 자가 균형 이진트리 dev-game-standalone.tistory.com 이전 포스팅에서 RB 트리의 4가지 조건을 알아보았다. 이 4가지 규칙 중 삽입과 삭제에서 핵심이 되는 규칙은 모든 red는 black 자식을 갖는다. (= red가 red의 부모가 될 수 없다.) 임의의 노드에서 출발하는 모든 경로는 모두 같은 수의 black 노드가 존재한다. 두 가지가 있다. 이 두 가지를 유의하며 RB 트리의 삭제를 살펴보자. 우선 R.. 자료구조 구현 : 레드 블랙 트리 (Red Black Tree, RB tree) - 삽입 자료구조 개념 : 레드 블랙 트리 (Red Black Tree, RB tree) 레드 블랙 트리는 일반 이진트리에서 자식들이 한쪽으로 치우치는 것을 막기 위한 균형 기능이 추가된 트리이다. 이를 자가 균형 이진트리(Self-balancing binary tree)라 부른다. 자가 균형 이진트리 dev-game-standalone.tistory.com 이전 포스팅에서 RB 트리의 4가지 조건을 알아보았다. 이 4가지 규칙 중 삽입과 삭제에서 핵심이 되는 규칙은 모든 red는 black 자식을 갖는다. (= red가 red의 부모가 될 수 없다.) 임의의 노드에서 출발하는 모든 경로는 모두 같은 수의 black 노드가 존재한다. 두 가지가 있다. 이 두 가지를 유의하며 RB 트리의 삽입을 살펴보자. RB 트.. 자료구조 개념 : 레드 블랙 트리 (Red Black Tree, RB tree) 레드 블랙 트리는 일반 이진트리에서 자식들이 한쪽으로 치우치는 것을 막기 위한 균형 기능이 추가된 트리이다. 이를 자가 균형 이진트리(Self-balancing binary tree)라 부른다. 자가 균형 이진트리는 대표적으로 자식의 Depth를 이용하는 AVL 트리와, 노드의 색을 이용하는 Red Black Tree 등이 있다. 이중 노드의 색을 이용한 Red Black Tree (이하 RB 트리)에 대한 설명을 하고자 한다. 트리에 대해 알고 있어야 하며, AVL 트리와 비교하기 좋으므로 이 부분은 더보기를 참고하자. 더보기 자료구조 트리 (tree) 트리는 그래프의 일종으로서 순환 관계 (= cycle)가 존재하지 않으며, 노드 간의 부모 자식 관계가 추가된 자료구조이다. 나무를 뒤집어 놓은 것과 .. BOJ 14890번 경사로 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 백준 14890 경사로 문제는 오래간만에 풀어보는 구현 문제였다. 사실 깡구현에 가깝기 때문에 한 경로가 경사로 건설을 통해 이동 가능한지 판별하는 아이디어 부분만 설명하고자 한다. 특별한 알고리즘을 요구한다는 느낌이 없었기 때문에 이러한 느낌으로 직접 구현했다. 만약 더 좋은 아이디어가 있다면 가르침을 바랍니다. code: GitHub - YoungWoo93/algorithmOnlineJudge: 알고리즘 온라인 저지 알고리즘 온라인 저지. Contribute to YoungWoo93.. 이전 1 2 3 4 ··· 9 다음
