5- 동시성 처리 (2)

지난 시간에 동시성 처리에 대해 알아봤다

더 이어서 알아보자

 

ConcurrentHashMap

현업에서 제일 많이 사용하고 김영한 강사님도 언급한 ConcurrentHashMap이다.

 

 

hashtable vs hashmap vs  concurrentHashMap

 

hashtable 

public class Hashtable<K,V>
    extends Dictionary<K,V>
    implements Map<K,V>, Cloneable, java.io.Serializable {

    public synchronized int size() { }

    @SuppressWarnings("unchecked")
    public synchronized V get(Object key) { }

    public synchronized V put(K key, V value) { }
}

Hashtable 클래스의 대부분의 API를 보면 위와 같이 메소드 전체에 synchronized 키워드가 존재하는 것을 볼 수 있다.(메소드 전체가 임계구역으로 설정 됩니다.) 그렇기 때문에 Multi-Thread 환경에서는 나쁘지 않을 수도 있다.

하지만 동시에 작업을 하려해도 객체마다 Lock을 하나씩 가지고 있기 때문에 동시에 여러 작업을 해야할 때 병목현상이 발생할 수 밖에 없다.(메소드에 접근하게 되면 다른 쓰레드는 Lock을 얻을 때까지 기다려야 하기 때문에)

 

Hashtable 클래스는 Thread-safe 하다는 특징이 있긴 하지만, 위와 같은 특징 때문에 멀티쓰레드 환경에서 사용하기에도 살짝 느리다는 단점이 있다.

 

hashMap

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {

    public V get(Object key) {}
    public V put(K key, V value) {}
}

 

 

 

HashMap 클래스를 보면 synchronized 키워드가 존재하지 않는다. 그렇기 때문에 Map 인터페이스를 구현한 클래스 중에서 성능이 제일 좋다고 할 수 있다. 하지만 synchronized 키워드가 존재하지 않기 때문에 당연히 Multi-Thread 환경에서 사용할 수 없다는 특징을 가지고 있다.

 

멀티 쓰레드 환경이 아니라면 HashMap을 사용하기에 대체적으로 적합하겠지만, 멀티쓰레드의 환경이라면 HashMap 클래스도 Hashtable 클래스의 대안이 될 수는 없다.

 

그러면 Hashtable 클래스보다는 더 빠르고 Multi-Thread 환경에서 쓸 수 있는 클래스는 없을까?

 

concurrentHashMap

public class ConcurrentHashMap<K,V> extends AbstractMap<K,V>
    implements ConcurrentMap<K,V>, Serializable {

    public V get(Object key) {}

    public boolean containsKey(Object key) { }

    public V put(K key, V value) {
        return putVal(key, value, false);
    }

    final V putVal(K key, V value, boolean onlyIfAbsent) {
        if (key == null || value == null) throw new NullPointerException();
        int hash = spread(key.hashCode());
        int binCount = 0;
        for (Node<K,V>[] tab = table;;) {
            Node<K,V> f; int n, i, fh;
            if (tab == null || (n = tab.length) == 0)
                tab = initTable();
            else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
                if (casTabAt(tab, i, null,
                             new Node<K,V>(hash, key, value, null)))
                    break;                   // no lock when adding to empty bin
            }
            else if ((fh = f.hash) == MOVED)
                tab = helpTransfer(tab, f);
            else {
                V oldVal = null;
                synchronized (f) {
                    if (tabAt(tab, i) == f) {
                        if (fh >= 0) {
                            binCount = 1;
                            for (Node<K,V> e = f;; ++binCount) {
                                K ek;
                                if (e.hash == hash &&
                                    ((ek = e.key) == key ||
                                     (ek != null && key.equals(ek)))) {
                                    oldVal = e.val;
                                    if (!onlyIfAbsent)
                                        e.val = value;
                                    break;
                                }
                                Node<K,V> pred = e;
                                if ((e = e.next) == null) {
                                    pred.next = new Node<K,V>(hash, key,
                                                              value, null);
                                    break;
                                }
                            }
                        }
                        else if (f instanceof TreeBin) {
                            Node<K,V> p;
                            binCount = 2;
                            if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
                                                           value)) != null) {
                                oldVal = p.val;
                                if (!onlyIfAbsent)
                                    p.val = value;
                            }
                        }
                    }
                }
                if (binCount != 0) {
                    if (binCount >= TREEIFY_THRESHOLD)
                        treeifyBin(tab, i);
                    if (oldVal != null)
                        return oldVal;
                    break;
                }
            }
        }
        addCount(1L, binCount);
        return null;
    }
}

 

 

 

위의 코드는 ConcurrentHashMap 클래스의 일부 API 입니다. ConcuurentHashMap에는 Hashtable 과는 다르게 synchronized 키워드가 메소드 전체에 붙어 있지 않다. get() 메소드에는 아예 synchronized가 존재하지 않고, put() 메소드에는 중간에 synchronized 키워드가 존재하는 것을 볼 수 있다.

 

이것을 좀 더 정리해보면 ConcurrentHashMap은 읽기 작업에는 여러 쓰레드가 동시에 읽을 수 있지만, 쓰기 작업에는 특정 세그먼트 or 버킷에 대한 Lock을 사용한다는 것이다.

 

public class ConcurrentHashMap<K,V> extends AbstractMap<K,V>
    implements ConcurrentMap<K,V>, Serializable {

    private static final int DEFAULT_CAPACITY = 16;

    // 동시에 업데이트를 수행하는 쓰레드 수
    private static final int DEFAULT_CONCURRENCY_LEVEL = 16;
}

 

ConcurrentHashMap 클래스를 보면 위와 같이 DEFAULT_CAPACITY, DEFAULT_CONCURRENCY_LEVEL가 16으로 설정되어있다.
DEFAULT_CAPACITY는 버킷의 수이다. 그리고 DEFAULT_CONCURRENCY_LEVEL는 동시에 작업 가능한 쓰레드 수다.

 

버킷의 수 == 동시작업 가능한 쓰레드 수인 이유는 위에서 말했던 것처럼 ConcurrentHashMap은 버킷 단위로 lock을 사용하기 때문에 같은 버킷만 아니라면 Lock을 기다릴 필요가 없다는 특징이 있다.(버킷당 하나의 Lock을 가지고 있다라고 생각하면 될 것 같다.)

 

즉, 여러 쓰레드에서 ConcurrentHashMap 객체에 동시에 데이터를 삽입, 참조하더라도 그 데이터가 다른 세그먼트에 위치하면 서로 락을 얻기 위해 경쟁하지 않는다.

 

읽기 작업보다는 쓰기 작업에 성능이 중요한 상황에서 쓰면 적합한 것 같다.

 

데드락이란?

 

저번시간에 동시성을 조사하다가 데드락에 관한 내용이 나와서 데드락이 무엇인지 알아보자

 

데드락은 교착상태라고도 불린다.

사실 별 내용이 없는 거 같다.

멀티쓰레드 환경에서 공유자원이 있을 때 lock기법을 사용한다. 이때 한 쓰레드가 lock을 계속 사용하고 있을 때 발생한다.

예를 들어 화장실이 1개밖에 없는데 한명이 계속 사용하여 나머지 사람들이 기다리고 있는 상태이다.

 

데드락이 발생하려면 4가지 조건이 필요하다.

교착상태의 4가지 필요 조건

아래 4가지 조건이 모두 만족되는 경우 데드락이 발생할 가능성이 있다.
→ 하나라도 만족하지 않으면 발생하지 X

1. 상호 배제 (Mutual exclusion)
   • 한 리소스는 한 번에 한 프로세스만이 사용할 수 있다.
   • 사용 중인 자원을 다른 프로세스가 사용하려면 요청한 자원이 해제될 때까지 기다려야 한다.
2. 점유와 대기(Hold and wait)
   • 자원을 최소한 하나 보유하고, 다른 프로세스에 할당된 자원을 점유하기 위해 대기하는 프로세스가 존재해야 한다.
3. 비선점 (No preemption)
   • 이미 할당된 자원을 강제로 빼앗을 수 없다.
   • 프로세스가 task를 마친 후 리소스를 자발적으로 반환할 때까지 기다려야 한다.
4. 환형 대기 (Circular wait)
   - 대기 프로세스의 집합이 순환 형태로 자원을 대기하고 있어야 한다.
   - Hold and wait 관계의 프로세스들이 서로를 기다림

교착상태 해결방법

 

크게 3가지의 해결법이 존재한다.

• 데드락이 발생하지 않도록 예방(prevention) 하기
• 데드락 발생 가능성을 인정하면서도 적절하게 회피(avoidance) 하기
• 데드락 발생을 허용하지만 데드락을 탐지(detection)하여, 데드락에서 회복(Recovery)하기

1️⃣ 예방 (Prevention)

• 교착상태가 발생할 수 있는 요구조건을 만족시키지 않게 함으로써 교착상태를 방지한다.
• 위에 있는 교착상태 발생의 네가지 조건 중에서 어느 하나를 제거함으로써 수행된다.
• 자원 낭비가 가장 심한 기법이다.

2️⃣ 회피 (Avoidance)

• 교착상태가 발생할 가능성을 배제하지 않고 교착상태가 발생하면 적절히 피해나가는 방법이다.
• 리소스 할당의 측면에서, 교착상태가 발생할 가능성이 있는 자원 할당(unsafe allocation)을 하지 않는다.
• 주로 은행원 알고리즘(Banker's Algorithm)이 사용된다.

은행원 알고리즘

• 은행원 알고리즘은 다익스트라가 제안한 기법으로, 은행에서 모든 고객의 요구가 충족되도록 현금을 할당하는데서 유래한 기법
• 각 프로세스에게 자원을 할당하여 교착상태가 발생하지 않으며 모든 프로세스가 완료될 수 있는 상태는 안전상태, 교착상태가 발생할 수 있는 상태는 불안전 상태 라고 한다.
• 은행원 알고리즘을 적용하기 위해서는 자원의 양과 사용자(프로세스) 수가 일정해야 한다.
• 은행원 알고리즘은 프로세스의 모든 요구를 유한한 시간안에 할당하는 것을 보장한다.

3️⃣ 탐지 및 회복 (Detection and Recovery)

• 교착상태가 발생 할 수 있도록 놔 두고 교착상태가 발생 할 경우 찾아내어 고친다.

탐지

• 시스템에 교착상태가 발생했는지 점검하여 교착상태에 있는 프로세스와 자원을 발견한다.
• 교착상태 발견 알고리즘과 자원 할당 그래프 등을 사용한다.자원 할당 그래프의 단점 : 자원을 요청할 때마다 탐지 알고리즘을 실행하면, 오버헤드가 발생한다.

회복

• 교착상태를 발견했다면 회복기법을 진행한다.
• 교착상태를 일으킨 프로세스를 종료하거나 교착상태의 프로세스에 할당된 자원을 선점하여 프로세스나 자원을 회복한다.
• 1. 프로세스 종료 방법
  • 교착 상태의 프로세스 모두 중지
  • 교착 상태가 제거될 때까지 한 프로세스씩 중지
  2. 자원 선점 방법
  • 자원을 빼앗긴 프로세스는 강제 종류 이후 재시작
  • 교착 상태에 빠진 프로세스가 필요로 하는 자원을 강제로 가져옴

출처

https://devlog-wjdrbs96.tistory.com/269

[Java] ConcurrentHashMap 이란 무엇일까?

https://velog.io/@ejung803/%EA%B5%90%EC%B0%A9%EC%83%81%ED%83%9C%EC%99%80-%EA%B5%90%EC%B0%A9%EC%83%81%ED%83%9C-%ED%95%B4%EA%B2%B0%EB%B0%A9%EB%B2%95

교착상태와 교착상태 해결방법