• data-structure
  • concurrency
  • python
  • java

Thread-Safe 자료구조: Python GIL과 Java ConcurrentHashMap

Python GIL이 thread-safe를 보장하지 못하는 이유와 Java ConcurrentHashMap, volatile을 정리한다.

Manx4분 읽기
시리즈 · 자료구조 · 알고리즘13 / 13
  1. 시간 복잡도와 공간 복잡도
  2. 재귀 함수와 꼬리 재귀 최적화
  3. 연결 리스트(Linked List)
  4. 스택과 큐: 원형 큐 구현과 덱
  5. 해시 테이블: 해시 함수와 충돌 처리
  6. 트리와 이진 탐색 트리
  7. 힙(Heap)과 우선순위 큐
  8. 균형 이진 탐색 트리: AVL, Red-Black, B-Tree
  9. 그래프: 인접 행렬과 인접 리스트
  10. 최단 경로 알고리즘: BFS, 다익스트라, 벨만-포드, 플로이드-워셜, A*
  11. 최소 신장 트리(MST): Kruskal, Prim, Union-Find
  12. 정렬 알고리즘: 퀵·병합·기수 정렬부터 Timsort까지
  13. Thread-Safe 자료구조: Python GIL과 Java ConcurrentHashMap

여러 스레드가 동시에 접근해도 데이터가 깨지지 않는 자료구조를 thread-safe하다고 한다. Python과 Java가 이를 어떻게 다루는지 정리한다.

Python

GIL

GIL(Global Interpreter Lock)은 파이썬 인터프리터가 한 번에 하나의 스레드만 바이트코드를 실행하도록 하는 락이다. 한 스레드가 인터프리터를 점유하는 동안 다른 스레드는 실행할 수 없다.

GIL이 필요한 이유

  • 파이썬은 reference counting과 GC로 메모리를 관리한다.
  • 모든 객체는 자신이 참조된 횟수인 reference count를 저장하고 있다.
  • 멀티 스레드 환경에서 여러 스레드가 하나의 객체를 사용하면, reference count를 안전하게 관리하기 위해 모든 객체마다 락이 필요해진다.
  • 객체마다 락을 거는 대신 인터프리터 전체에 락 하나를 건 것이 GIL이다.

GIL과 성능

  • CPU 연산 위주의 작업은 멀티 스레드로 실행해도 한 번에 한 스레드만 동작하고 스레드 전환 비용까지 들기 때문에, 싱글 스레드보다 오히려 느릴 수 있다.
  • 반면 I/O 작업이 많아 스레드가 대기해야 하는 경우에는, 대기하는 동안 다른 스레드로 컨텍스트 스위칭이 일어나므로 멀티 스레드로 성능이 개선된다.

GIL은 thread-safe를 보장하지 않는다

GIL은 바이트코드 단위로 한 스레드만 실행되게 할 뿐이다. count += 1처럼 읽기, 계산, 쓰기의 여러 바이트코드로 이루어진 연산은 중간에 스레드가 전환될 수 있으므로 여전히 경쟁 상태가 발생한다.

thread-safe하게 만드는 방법은 다음과 같다.

  • threading 모듈의 Lock 클래스로 임계 구역을 직접 보호한다.
  • queue 모듈의 Queue, PriorityQueue처럼 내부에 락이 구현된 자료구조를 사용한다.

Java

Java에서 thread-safe한 대표적인 클래스는 Hashtable, ConcurrentHashMap, AtomicInteger, BlockingQueue, StringBuffer이다.

Hashtable

메서드에 synchronized 키워드가 붙어 있어 thread-safe를 보장한다. 다만 테이블 전체에 락 하나를 사용하므로, 한 스레드가 접근하는 동안 다른 스레드는 모두 기다려야 한다.

ConcurrentHashMap

락의 범위를 버킷 단위로 줄여 동시성을 높였다.

  • 비어 있는 버킷에 노드를 넣을 때는 별도의 락 없이 처리한다.
  • 이미 버킷에 노드가 존재하면 synchronized로 그 버킷에 하나의 스레드만 접근하도록 제어한다.
  • 따라서 서로 다른 스레드가 같은 해시 버킷에 접근할 때만 해당 블록이 잠기고, 다른 버킷에 접근하는 스레드끼리는 서로를 막지 않는다.

volatile

변수를 CPU 캐시가 아닌 메인 메모리에서 읽고 쓰겠다는 것을 명시하는 키워드이다.

  • 멀티 스레드 환경에서는 각 스레드가 변수 값을 자신이 실행 중인 CPU의 캐시에서 읽어 올 수 있다. 캐시에 저장된 값이 서로 다르면 변수 값 불일치 문제가 발생한다.
  • volatile을 붙이면 항상 메인 메모리의 값을 읽으므로 가장 최신의 값을 보장한다.
  • 적합한 경우: 하나의 스레드만 읽고 쓰고, 나머지 스레드는 읽기만 하는 상황이다. 여러 스레드가 동시에 쓰는 경우에는 volatile만으로 부족하고 synchronized나 Atomic 클래스가 필요하다.

정리

언어 thread-safe 자료구조
Python queue.Queue, queue.PriorityQueue
Java Hashtable, ConcurrentHashMap, AtomicInteger, BlockingQueue