가장 간단한 자료구조중 하나
자료구조 호출할 때 락을 추가, 리턴할 때 락을 해제
확장성이 떨어짐( 여러 쓰레드 동시실행하면 시간이 오래 걸린다)
근사 카운터
CPU마다 존재하는 지역카운터
하나의 전역 카운터 존재
기본 개념
쓰레드는 지역 카운터 증가시킴
지역 카운터는 지역 락에 의해 보호
-> CPU에 의해 분산되어있는 쓰레드들은 지역 카운터 경쟁없이 갱신 가능
쓰레드는 전역 카운터를 읽어서 카운터 값을 판단
전역 카운터는 지역 카운터 값을 반영하여 주기적으로 갱신
지역 카운터가 한계치 S에 도달하면 지역 값은 전역 카운터에 반영되고 지역값은 초기화
병행 삽입
삽입 연산 시작 전에 락 획득, 리턴 직전에 해제
전체 리스트에 lock이 있는게 아니라 개별 node에 lock을 둔다.
리스트 순회 시 각 노드의 lock을 얻는데 시간이 걸림
큐의 헤드와 테일 두개의 락 존재
삽입시 테일 잠금, 추출시 헤드 잠금