👶🏻

Vector와 Stack을 사용하지 않는 이유는 무엇인가요?

Stack 자료구조의 대표적인 기능 push() 와 pop() 을 살펴보자.

Stack의 push() 메서드는 Vector의 addElement() 메서드를 사용하는데, synchronized메서드인 것을 볼 수 있고, pop() 메서드 역시 synchronized메서드이다.

synchronized 메서드는 한 번에 하나의 스레드만 해당 메서드를 실행할 수 있도록 해서 스레드 안정성을 보장할 수 있다.

그러나 이러한 동기화는 성능 저하를 초래할 수 있다.

다수의 스레드가 동시에 접근하는 상황에서 시간적으로 비효율적이며, 성능 저하를 초래할 수 있다.

심지어 synchronized 메서드는 멀티 스레드 환경에서 발생하는 모든 문제를 해결할 수도 없다. (ex. 가시성 문제)

그렇다고 단일 스레드에서 사용하는 것도 비효율 적이다.

왜냐하면, 여러 스레드가 공유 자원에 동시에 접근하지 않으므로, 동기화가 필요하지 않기 때문이다.

그런데, Vector와 Stack은 메소드 호출 시 마다 동기화를 사용하기 때문에, 다른 자료구조에 비해 더 많은 시간과 리소스를 소비할 수 있다.

그렇다면 어떤 자료구조를 사용하는 것이 좋을까?

Deque(Double Ended Queue)는 양쪽 끝에서 요소의 삽입과 삭제가 가능한 자료구조이다.

즉, 스택과 큐의 기능을 모두 갖고 있다.

Deque<String> deque = new ArrayDeque<>();

Deque<String> deque = new LinkedList<>();
Java
복사

위와 같이 ArrayDeque 혹은 LinkedList 구현 클래스를 사용해서 초기화하면 된다.

 ArrayDeque : 배열을 사용해 구현되어 있어, 메모리에 연속 할당되어있다. 따라서 캐시 효율성이 높고 인덱스를 사용하여 원소에 빠르게 접근할 수 있다.

LinkedList : 각 요소에 대한 포인터를 갖고 있기 때문에 요소에 대한 삽입 · 삭제가 빠르지만, 요소에 접근할 때는 포인터를 따라가야 하므로 느리다.

Deque<String> deque = Collections.synchronizedDeque(new ArrayDeque<String>());
Java
복사

Deque의 경우 기본적으로 동기화 처리가 안되어있어,

멀티 스레드 환경에서 동시성 문제를 발생시킬 수 있으므로

위와 같이 Collections.synchronizedDeque 를 이용해서 초기화하면 동기화 처리된 Deque를 생성할 수 있다.

근데 이런식으로 생성한 Deque는 Stack과 Vector처럼 모든 메서드에 synchronized 처리가 되어있으므로, 이 역시 모든 동시성 문제를 해결하지 못한다.

ConcurrentLinkedDeque<String> deque = new ConcurrentLinkedDeque<>();

LinkedBlockingDeque<String> deque = new LinkedBlockingDeque<>();
Java
복사

따라서, 위와 같은 구현체를 사용하면 된다.

ConcurrentLinkedDeque는 lock-free 알고리즘을 사용하여 스레드 안전성을 보장하며,

LinkedBlockingDeque는 내부적으로 잠금(lock)을 사용하여 스레드 안전성을 보장한다.

 lock-free 알고리즘 : 락을 사용하지 않고 스레드 안정성을 보장하는 방법, 대표적으로 CAS(Compare And Sweep)가 있다. (참고로! 이전에 배웠던 Atomic 변수도 이 방식을 사용)

① 인자로 기존값과 변경할 값을 전달한다.

② 변경할 값을 메모리에 전달하기 전, 메모리에 있는 값과 연산하기 전 기존값을 비교해서 일치한지 확인한다.

만약 다른 스레드가 변경을 한 뒤라면, 값이 일치하지 않을 것이다.

③ 만약 일치하면 값을 반영하고 다르다면 후처리를 한다.(후처리는 개발자가 결정)