반응형 CAS2 [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으로 진행됨 ( = .. 2024. 4. 25. [05주차] 동기화 연산 & CAS - Lock-free 자료구조 : 여러 개의 쓰레드에서 동시에 호출했을 때에도 정해진 단위 시간마다 적어도 한 개의 호출이 완료되는 알고리즘 : Non-blocking이 보장되어야 함 : 알고리즘 내에 Lock이 있으면 당연히 Lock-free X, Lock이 없다고 해도 무조건 Lock-free인 것은 아님 : Lock이 존재하는 경우 다른 쓰레드를 실행할 수 없어 싱글 쓰레드와 다를 바가 없음 → wait-free를 유지하며, 메모리로 Atomic Memory를 만들 수 있는 알고리즘 존재? : 존재, 이 강의에서 생략. → wait-free를 유지하며, 기존 씽글 스레드 자료구조도 Atomic Memory를 사용해 멀티쓰레드 자료구조로 변환 가능? : 불가능하다.. 2024. 4. 24. 이전 1 다음 728x90 반응형
