[F-Lab 모각코 챌린지 1일차] volatile?

부추·2023년 6월 1일

F-Lab 모각코 챌린지

목록 보기

1/66

TIL

알고리즘 : 정수삼각형

volatile 키워드란?

1. 정수삼각형

아래 그림과 같은 구조의 정수 삼각형이 있다. 가장 위에서부터(예시의 경우 7) 삼각형의 밑변까지 각 층의 요소를 하나씩 더하며 내려간다. 밑변에 도착을 때, 가장 크게 나올 수 있는 합이 무엇인지 구하는 문제였다.

첫 눈에 다이나믹 프로그래밍임을 알아차렸다. triangle에 주어진 list와 같은 형식의 dp list를 선언했다. dp의 각 요소들은 꼭대기 층부터 내려오면서, 해당 요소 index에서 가질 수 있는 가장 큰 값을 저장할 수 있도록 했다.

base case는 요소가 1개인 가장 꼭대기 층, 그리고 왼쪽만 선택해서 내려온 경우이다.triangle의 왼쪽 값들을 계속 더하는 식으로 base를 셋팅했다.

이후의 dp[i][j]는 두 가지 값 중 하나를 갖는다. 왼쪽 위에서 내려온 dp[i-1][j-1] + triangle[i][j], 오른쪽 위에서 내려온 dp[i-1][j] + triangle[i][j]값이다. 둘 중 더 큰 값을 max함수를 이용해 dp에 저장했다. 새로운 층의 가장 오른쪽은 왼쪽 위의 값을 더하는 것 밖에 방법이 없으므로 이 또한 따로 계산했다.

각 층에 대한 dp계산이 끝나고 가장 밑 층의 최댓값을 구하는 것으로 마무리했다.

def solution(triangle):
    dp = [[0 for _ in range(i)] for i in range(1,len(triangle)+1)]

    # base case
    dp[0] = [triangle[0][0]]
    for i in range(1,len(triangle)):
        dp[i][0] = dp[i-1][0] + triangle[i][0]

    for i in range(1,len(triangle)):
        for j in range(1,len(triangle[i])-1):
            dp[i][j] = max(dp[i-1][j-1],dp[i-1][j]) + triangle[i][j]
        dp[i][-1] = dp[i-1][-1] + triangle[i][-1]

    return max(dp[-1])

2. Volatile 키워드란?

1) 가시성(Visible)

visible 문제라는 것이 있다. visible은 '보이는'이라는 의미를 가지는데, 가시성 문제라 함은 이 보이는 것에 문제가 있는 것이다. 컴퓨터가 눈을 가진 것도 아닌데 뜬금없이 가시성?

아래 VisibleProblem은 메인 스레드와 thread 스레드가 동작한다. 두 스레드가 공유하는 "static boolean go"라는 변수가 존재한다.

public class VisibleProblem {
    static boolean go = false;
    public static void main(String[] args) throws InterruptedException {
        Thread thread = new Thread(() -> {
            while (!go); // wait until go == true
            System.out.println("thread terminated");
        });

        thread.start();
        Thread.sleep(1000);
        go = true;
        System.out.println("main thread terminated.");
    }
}

thread는 go 변수가 true가 될 때까지 while문을 반복하며 기다린다. go가 true가 되면 반복문을 빠져나오며, "thread terminated"를 출력하며 종료된다.
main 스레드는 thread를 시작시키고 1초간 sleep한다. 그 뒤 공유하는 go 변수를 true로 만들고 "main thread terminated"를 출력하며 종료된다.

일반적으로 생각하기엔 별 문제 없어 보이는 코드이다. 어떤 스레드가 먼저 종료될지는 몰라도, 어쨌든 terminate를 보장하는 프로그램으로 보인다. 하지만 실행시켜보면, 결과는 이상하다.

일단 "main thread termiated" 결과가 출력된걸로 보아 메인 스레드는 종료된 것 같다. 근데 "thread terminated"는 어디에? 게다가 메인 메소드가 실행된지 14초가 지났음에도 프로그램이 계속 실행중이다.

문제의 원인은 CPU 캐시에 있다.

컴퓨터는 프로그램의 실행 속도를 조금이라도 더 빨리 하기 위해 CPU 캐시를 사용한다. CPU의 속도에 비해 RAM에 접근하는 속도는 상당히 느리기 때문에, 프로그램 내에서 자주 사용하는 메모리 값은 접근 속도가 조금 더 빠른 CPU 캐시로 불러온다. locality 덕에 캐시를 이용하면 프로그램 성능이 훨씬 향상되는데, 그것은 캐시와 관련된 사항이므로 이 포스트에선 넘어가기로 하고. 앞선 가시성 문제의 예시를 생각해보면, 공유변수 "go"가 각 프로세스가 동작하는 CPU의 캐시 메모리에 따로 저장되어 있기 때문으로 생각할 수 있다. 그림을 그려보면 아래와 같다.

thread는 최초에 false값인 go 변수를 참조한다. while문을 돌며 계속 go 값을 확인하고 있기 때문에 thread 스레드가 사용하는 캐시 메모리에 해당 변수값을 두고 사용했을 것이다.
메인 스레드는 같은 go 변수를 가져와 true를 write한다. 그러나 메인 스레드가 사용하는 CPU 캐시 메모리에 해당 값을 write했든, RAM에 직접 데이터를 write했든 thread 스레드엔 업데이트된 go 값이 전달되지 않을 것이다.
thread 스레드가 참조하는 go 변수는 thread 스레드가 사용중인 캐시 메모리이기 때문이다.

이것이 가시성 문제이다. 스레드가 자신의 캐시 메모리만을 보기 때문에 다른 스레드의 캐시 메모리, 혹은 RAM에 있는 값이 "보이지 않는다"라고 해서 visible이라고 표현을 한 것이다.

2) volatile 키워드 : 메인 메모리를 참조하라!

이를 해결하기 위해 volatile 키워드를 사용한다. 위와 100% 똑같은 코드의 go 변수에 "volatile" 키워드를 추가한 뒤 실행시켜보면 우리가 원하는 결과가 잘 나온다.

main thread terminated.
thread terminated

volatile은 변수의 가시성을 보장한다. JVM으로 하여금 해당 키워드가 붙은 변수를 메인 메모리로부터 읽고, 메인 메모리에 쓰도록 한다. 이렇게 되면 캐시 불일치로 인해 생기는 가시성 문제를 해결할 수 있다.스레드가 volatile 변수에 값을 쓰면 메인 메모리로 flush되고, 스레드가 volatile 변수 값을 참조할 땐 메인 메모리에 접근하는 것을 강제한다.

3) 스레드간 협업도 가능!

앞선 예시와 약간 비슷한데, 스레드가 공유하는 Data 객체를 작성하자.

public class Data {
    private static volatile boolean sent = false;
    private static String data;

    public static void send(String data) {
        while (sent) Thread.onSpinWait();
        Data.data = data;
        sent = true;
    }

    public static void receive() {
        while (!sent) Thread.onSpinWait();
        System.out.println("receiver 스레드가 받은 data : " + Data.data);
        sent = false;
    }
}

send()는 sent가 false여야만, receive()는 sent가 true여야만 while문을 빠져나와 동작할 수 있다.
send()는 data 필드에 인자로 들어온 문자열 값을 저장한 후 보냈다는 고지로 sent값을 true로 놓는다.
receive()는 data필드를 받았다는 출력을 한 뒤 다시 sent값을 false로 놓는다.

위 Data 클래스를 사용하는 Example 클래스를 작성했다. sender 스레드는 send()를, receiver 스레드는 receive()를 호출한다.

public class CoOpExample {
    public static void main(String[] args) {
        Thread sender = new Thread(() -> {
            Data.send("스레드가 보낸 데이터");
        });

        Thread receiver = new Thread(Data::receive);

        receiver.start();
        sender.start();
    }
}

위와 같이 코드를 작성하면 sender 스레드가 먼저 send() 메소드를 호출한 뒤 receiver 스레드의 receive() 메소드가 동작하는 것을 보장할 수 있다. 만약 sent가 volatile 변수가 아니라면 sender 스레드와 receiver 스레드가 각자의 캐시 속 sent 변수를 참조하기 때문에 가시성 문제가 발생할 수 있다. receiver가 참조하는 sender 변수가 캐시 상에선 계속 false이므로 루프를 빠져나오지 못할 수도 있다는 말이다.

4) 하자가 명백함

명시적으로 JVM에게 "이렇게 하세요"라고 명령하는 만큼 volatile 키워드는 성능 하자를 동반한다. 이는 컴퓨터가 캐시 메모리를 사용하는 이유와 동일하다.

캐시보다 느리다!

캐시 접근 속도와 메모리 접근 속도는 큰 차이가 난다(대략 N배). 캐시를 사용하면 1초만에 접근 가능했던 변수가 메인 메모리 변수 접근 시마다 cache fault가 발생하는 것과 마찬가지이므로, 캐시를 사용하는 것에 비해 훨씬 느린 동작 시간을 갖는다. 따라서 정말 가시성의 문제를 해결해야 할 때만 최소로 사용해야한다. 실제로 사용되는 예시는 거의 본 적이 없는 것 같다..

Out Of Order X

또한 데이터의 가시성 때문에 volatile 변수는 해당 변수를 참조하는 부분 기준으로 코드의 재정리를 막는다. data dependency 문제가 없는 범위 내에서, JVM은 프로그램의 성능을 향상시키기 위해 OoO Execution을 사용한다. 더 빨리 실행될 수 있는 방향으로 코드의 순서를 바꾸는 과정이다.

앞서 스레드간 협업의 예시에서, 코드의 순서가 아래와 같이 바뀌면 어떻게 될까?

public void send(String data) {
    while (sent);
    // 아래 두 줄 순서 바뀜
    sent = true;
    this.data = data;
}

sender 스레드에 의해 data가 새로 써지기도 전에 receiver 스레드가 data를 읽을 수도 있다. 일반적인 경우에, sent와 data는 서로 다른 변수이고 data dependency가 존재하지 않아 위와 같이 코드의 재정리가 일어날 수도있다.

그렇게 되면 volatile의 의미가 없어진다! 따라서 JVM은 최적화를 위해 코드를 재정리할 때, volatile 변수에 접근하는 부분을 기준으로 코드의 순서를 바꾸지 않는다. sent값을 읽거나 쓰는 코드의 전에 있던 코드가 뒤로 간다거나, 반대의 경우도 불가하다는 소리이다.

이와 같은 특징을 "happens before guarantee"라고 한다.

동작 순서를 빠르게 하기 위한 코드 재정리에 제약이 생긴다.. 역시 성능 저하를 일으킬 것이다.

volatile은 가시성을 보장해주는 대신 synchronized와 마찬가지로 성능상 큰 하자를 불러일으킨다. 웬만해선 안쓰느니만 못하는 결과를 불러일으키므로, 정말로 사용해야 할 때만 신중하게 사용하는게 좋을 것이다.