프로세스 동기화, CAS 알고리즘, Volatile

eunsiver·2023년 5월 2일

운영체제

목록 보기

3/5

임계 구역

공유 자원 접근 순서에 따라 실행 결과가 달라지는 프로그램의 영역
임계구역에서는 프로세스들이 동시에 작업하면 안 됨
어떤 프로세스가 임계구역에 들어가면 다른 프로세스는 임계구역 밖에서 기다려야 하며 임계구역의 프로세스가 나와야 들어갈 수 있음

임계구역 해결 조걸

상호 배제(mutual exclustion)
: 한 프로세스가 임계구역에 들어가면 다른 프로세스는 임계구역에 들어 갈 수 없는 것
한정 대기(bounded waiting)
: 어떤 프로세스도 무한 대기하지 않아야 함
진행의 융통성(progress flexibility)
: 한 프로세스가 다른 프로세스의 진행을 방해해서는 안 된다.
아무도 임계 구역에 있지 않은 상태에서 임계 구역에 들어가고자 하는 프로세스가 있다면 들어가게 해주어야 한다.

임계구역은 일반적으로 아래와 같은 구조로 이루어져있다.

do{
    /*
     entry section (진입 구역)
    */
    
    /*
     critical section (임계 구역)
    */
    
    /*
     exit section (퇴출 구역)
    */
    
    /*
     remainder section (나머지 구역)
    */
    
} while(TRUE)

일반적인 임계구역의 형태는 다음과 같다.

do{
    wants[i] = true; // i 프로세스가 공유 자원을 사용하겠다고 선언
    while(wants[j]) {;} // j 프로세스가 공유 자원을 사용중이면 진입 불가(진입구역)
    	CRITICAL SECTION
    wants[i] = false; // i 프로세스가 공유 자원 사용 완료 후 반납(퇴출구역)
    	REMAINDER SECTION
} while(TRUE)

임계구역의 세가지 요구사항을 만족하는지 확인해보자.

기본적으로 상호배타적 접근은 전제로 깔고 가기 때문에 Process와 Busy waiting만 확인하면 된다.

Peterson's Solution

피터슨(Peterson's algorithm) 알고리즘은 flag와 turn이라는 변수로 임계영역에 들어갈 프로세스(혹은 스레드)를 결정하는 방식이다.

int turn;
boolean flag[2];

Turn 은 critical section에 들어갈 수 있는 프로세스를 나타내는 변수

Flag 는 critical section에 들어갈 준비 상태를 나타내는 변수(공유 자원을 쓰고 싶다라는 것을 표현하기 위한 변수)

Example : P0 와 P1 두개의 프로세스가 Critical section에 접근 하려 할 때

상황 1 : P0 접근 O , P1 접근 X

P0 출발
-> flag[0] = true , turn = 1
-> while 조건 false 이므로 임계 구역 진입

상황 2 : P0 임계 구역 , P1 접근 O

P0 임계 구역 , P1 출발
-> flag[1] = true , turn = 0
-> flag [0] 는 true 이고 turn 는 0 이므로 while 조건 true
-> P1 while 속에 갇힘
-> P0 임계 구역 끝
-> flag[0] = false
-> P1 while 조건 false 이므로 임계 구역 진입

상황 3 : P0 다시 접근 O , P1 임계 구역

P0 remainder section , P1은 임계 구역
-> P0 remainder section 마치고 다시 while통해 접근
-> flag[0] = true , turn = 1
-> flag[1] 는 true , turn 는 1이므로 while 조건 true
-> P0 while 속에 갇힘
-> P1 임계 구역 끝
-> flag[1] = false
-> P0 while 조건 false

이 알고리즘에서는 flag 와 turn 이라는 전역변수를 사용해서, 3가지 조건(상호 배제, 진행, 한정 대기) 를 만족시킨다.

🙆🏻‍♀️ Mutual exclusion

flag , turn 두 변수를 통해 충족

🙆🏻‍♀️ progress

프로세스가 critical section을 나오자마자 flag 변수를 false로 설정함으로써
critical section 입장을 기다리던 프로세스가 바로 진입할 수 있도록 도와 주기 때문에 progress 또한 충족

🙆🏻‍♀️ Bounded waiting

두 개의 프로세스이기 때문에 충족

피터슨 알고리즘 문제점!

현대 컴퓨터에서는 정상 작동하지 않는 문제가 있다.

컴파일러는 메모리 접근을 위해 컴파일 도중에 필요에 따라 코드의 위치를 조금씩 조정한다. 만약 flag[i] = true와 while문의 위치가 바뀌게 되면 제대로 동작하지 않게 된다.

프로세스가 2개인 경우에만 적용된다.

하드웨어적 동기화

원자적 실행 단위를 보장하므로 코드의 순서가 바뀌는 일이 없다.

1) 싱글 코어 프로세스

인터럽트를 사용할 수 없게 끔 싱글 코어 프로세서를 사용하는 것이다.
그러면 Synchronization이 발생하지 않는다.
멀티 프로세스 시스템에서는 이 방식이 매우 비효율적이다.
확장되어 있는 OS들 에서는 이 방식을 채택하지 않는다.

2) Hardware Support 세 가지

Memory barriers
Hardware instructions
Atomic variables

① Memory barriers

오퍼레이션들의 순서를 보장해주는 장치
보통 store 오퍼레이션들 전후로 위치 한다

memory_Barrier를 설치함으로써 reorder방지
very low - level operation -> kernel 개발자들에 의해 사용됨 (일반 프로그래머들이 사용하기는 어렵고 복잡하다.)

🕹🎯Peterson's Solution 에서의 활용

While (true) {
	Flag[i] = true; 
    memory_barrier();      // reorder 방지
	turn = j; 
	while(flag[j] && turn == j);

.
.
.

② Hardware Instruction

변수들을 이용하여 Synchronization을 해결하는 두 가지 instructions

② - 1) Test - and - Set

boolean test_and_set(boolean *target) {
    boolean rv = *target;
    *target = true;
    
    return rv;
}

target으로 들어온 값을 내부 변수에 저장한 후 그 값을 true로 바꾸고 내부 값을 반환함

do{
    while(test_and_set(&lock));
    
	/* critical section */
    
    lock = false;
    
    /* remainder section */

}while(true);

lock은 false로 초기화 되어 있다.

▷ Lock == true
test_and_set == true -> while 속에 갇힘 -> 다른 thread가 임계영역 안에 있는것 -> lock = false 될 때 까지 기다림.

▶ Lock == false
test_and_set == false -> while 조건 false -> 임계영역 진입 -> 임계영역 탈출 후 lock = false

이를 통해 Atomic 하게 실행 된다.
※ atomic 은 실행중일 때 누구도 interrupt 할 수 없는 것을 말한다.

Test - and - Set

이 solution은 Bounded waiting 조건을 만족하지 못 한다.
P1,P2가 있을 때 P1이 critical section에 진입했다 나온 후 다시 진입하려면 lock이 false로 바뀌어 있기 때문에 P1은 언제든 다시 critical section에 진입할 수 있다. 결국 P2는 무한정 기다리게 될 수 있다.
따라서 Mutual exclusion은 만족하지만 Bounded waiting은 만족하지 못 한다.

② - 2) Compare - and - Swap

int compare_and_swap(int *value, int expected, int new_value) {
    int temp = *value;
    
    if(*value == expected) *value = new_value;
    
    return temp;
}

while(true){
	while(compare_and_swap(&lock , 0 , 1) != 0);
    
    /* critical section */
    
    lock = 0;
    
    /* remainder section */

}

이 solution 역시 TestAndSet과 같은 이유로 상호 배제 조건은 만족하지만, 한정된 대기(Bounded Waiting)을 만족하지 못한다.
따라서 임계 구역 요구 조건을 모두 만족시키는 또 다른 알고리즘이 있다.

보완된 compare - and - swap

boolean waiting[n];
int lock;
while (true) {
	waiting[i] = true;
    ket = 1;
    while(waiting[i] && key == 1)
    	key = compare_and_Swap(&lock , 0 ,1);
    waiting[i] = false;
    
    /* critical section */
    
    j = (i + 1) % n;
    while ((j != i) && !waiting[j])
    	j = (j + 1) % n;
    if (j == i)
    	lock = 0;
    else
    	waiting[j] = false;
    
    /* remainder section */


}

초기에 waiting 배열의 원소는 false로, lock은 0으로 모두 초기화된다.
위 코드는 위에서 설명한 상호 배제뿐만 아니라 나머지 두 조건을 모두 만족한다.
Progress : 임계 구역을 떠나는 프로세스는 lock을 false로 하거나, waiting[j]를 false로 만들어 줌으로써 어느 쪽이든 임계 구역으로 들어가고자 하는 프로세스를 진입하게 만들어준다.
Bounded waiting : 프로세스가 임계 구역을 떠날 때, waiting 배열을 순환하며 검사한다. 자신의 순서 이후부터 차례대로 보기 때문에, 임계 구역에 들어가고자 하는 프로세스는 최대 (n-1)번만 기다리면 된다.

③ Atomic variable(아래에서 자세히)

Data types(Int , Boolean) 에게 Atomic 한 update를 준다.

위에서 봤듯이 hardware support로도 synchronization을 해결할 수 있다.

그러나 low-level인 기계어로 작성되어 있기 때문에 프로그래머들이 사용하기에는 어렵다고 알려져 있다.

이를 대체하여 software 기반의 synchronization tool들 ( mutex , semaphor , monitor 등 )을 사용하기도 한다.

보통 Mutex Lock은 HW 가 서포트해주는 atomic instructions를 사용한다.(test_and_set)

Volatile을 통한 long과 double의 원자화

JVM은 데이터를 4바이트(32비트) 단위로 처리하기 때문에, int와 int보다 작은 타입들은 한번에 읽거나 쓰는 것이 가능하다. 즉, 단 하나의 명령어로 읽기와 쓰기 작업이 가능하다는 것이다.
하나의 명령어는 더 이상 나눌 수 없는 작업의 최소단위이므로, 작업의 중간에 다른 쓰레드가 끼어들 틈이 없없다.

그러나 크기가 8바이트인 long과 double 타입은 하나의 명령어로 값을 읽거나 쓸 수 없기 때문에 변수의 값을 읽는 과정에서 다른 쓰레드가 끼어들 여지가 있다.
다른 쓰레드가 끼어들지 못하게 하기 위하여 변수를 읽고 쓰는 모든 문장을 synchronized 블럭으로 감쌀 수도 있지만 volatile을 통해 더 간단히 해결할 수 있다.
변수 선언 시 volatile을 사용하므로써 해당 변수에 대한 읽거나 쓰기 작업이 원자화된다.
예시로 AtomicLong 역시 long 값을 volatile을 통해 원자화하였다.

synchronized의 문제점

synchronized는 blocking을사용하여 멀티 스레드 환경에서 공유 객체를 동기화하는 키워드
성능 이슈: 특정 스레드가 해당 블럭 전체에 lock을 걸면, 해당 lock에 접근하는 스레드들은 블로킹 상태에 들어가기 때문에 아무 작업도 하지 못한 채 자원을 낭비한다.
또한 blocking 상태의 스레드를 준비 혹은 실행 상태로 변경하기 위해 시스템의 자원을 사용해야 한다. 결국 이 문제는 성능 저하로 이어진다.
이러한 문제점 때문에 non-blocking을 하며 원자성을 보장하기 위한 방법이 atomic 변수이다.

원자성과 Atomic Type

atomic 변수는 멀티 스레드 환경에서 원자성을 보장하기 위해 나온 개념
synchronized와는 다르게 blocking이 아닌 non-blocking하면서 원자성을 보장하여 동기화 문제를 해결
atomic의 핵심 동작 원리는 CAS(Compare And Swap) 알고리즘

CAS 알고리즘의 동작 원리는 다음과 같다.

인자로 기존 값(Compared Value)과 변경할 값(Exchanged Value)을 전달한다.
기존 값(Compared Value)이 현재 메모리가 가지고 있는 값(Destination)과 같다면 변경할 값(Exchanged Value)을 반영하며 true를 반환한다.
반대로 기존 값(Compared Value)이 현재 메모리가 가지고 있는 값(Destination)과 다르다면 값을 반영하지 않고 false를 반환한다.

멀티쓰레드환경, 멀티코어 환경에서 각 CPU는 메인 메모리에서 변수값을 참조하는게 아닌, 각 CPU의 캐시 영역에서 메모리를 참조하게 된다.
이떄, 메인메모리에 저장된 값과 CPU캐시에 저장된 값이 다른 경우가 있는데 (가시성문제)

이럴때 사용되는것이 CAS 알고리즘. 현재 쓰레드에 저장된 값과 메인메모리에 저장된 값을 비교하여 일치하는경우 새로운 값으로 교체되고 , 일치하지않는다면 실패하고 재시도를 한다.

이런방법으로 처리하면, CPU캐시에 잘못된 값을 참조하는 가시성문제를 해결할 수 있다.

CAS 알고리즘 사용 예

변수마다 동기화를 해줄 수 있는 특징 덕에 AtomicXXX 클래스에 사용된다. Atomic 자료형은 기본형인 int, long 등의 동기화를 보장해주는 자료형인데, 내부에서 CAS 알고리즘을 사용한다.
또 ConcurrentHashMap 클래스에서도 사용되는데, 빈 버킷에 값을 넣을 때 CAS 알고리즘을 사용함으로써 빠르게 처리해줄 수 있다. (이미 값이 들어있으면 synchronized를 사용한다.)

정리

atomic 변수의 핵심 원리인 CAS 알고리즘은 원자성 뿐만 아니라 가시성 문제도 해결해 주는 것을 볼 수 있다. 그리고 non-blocking이 가능하므로 blocking 방식인 synchronized보다 성능 상 이점이 있다는 것도 알 수 있었다.
참고로 synchronized 키워드의 경우 synchronized 블록에 진입하기 전에 CPU 캐시 메모리와 메인 메모리 값을 동기화하여 가시성을 해결한다.

AtomicInteger 살펴 보기

atomic type인 AtomicInteger 클래스가 동기화 문제를 어떻게 해결하는지 살펴 보자.

public class AtomicIntegerTest {

    private static int count;

    public static void main(String[] args) throws InterruptedException {
        AtomicInteger atomicCount = new AtomicInteger(0);
        Thread thread1 = new Thread(() -> {
            for (int i = 0; i < 100000; i++) {
                count++;
                atomicCount.incrementAndGet();
            }
        });

        Thread thread2 = new Thread(() -> {
            for (int i = 0; i < 100000; i++) {
                count++;
                atomicCount.incrementAndGet();
            }
        });

        thread1.start();
        thread2.start();

        Thread.sleep(5000);
        System.out.println("atomic 결과 : " + atomicCount.get());
        System.out.println("int 결과 : " + count);
    }
}

AtomicInteger와 int 타입인 count 변수를 생성한 다음, 두 개의 스레드에서 count++ 연산을 하는 예제이다. 결과는 다음과 같다.

//결과
atomic 결과 : 200000
int 결과 : 152298

AtomicInteger 타입인 atomicCount는 의도 대로 200000이 출력되는 것을 볼 수 있고, int 타입인 count는 동기화가 지켜지지 않아 잘못된 값을 출력하는 것을 볼 수 있다.

동기화가 어떻게 지켜지는지 AtomicInteger 클래스의 incrementAndGet() 메소드를 살펴 보자.

public class AtomicInteger extends Number implements java.io.Serializable {

        private static final Unsafe U = Unsafe.getUnsafe();
        private static final long VALUE = U.objectFieldOffset(AtomicInteger.class, "value");
    private volatile int value;

        public final int incrementAndGet() {
                return U.getAndAddInt(this, VALUE, 1) + 1;
        }
}

public final class Unsafe {
        @HotSpotIntrinsicCandidate
        public final int getAndAddInt(Object o, long offset, int delta) {
                int v;
                do {
                        v = getIntVolatile(o, offset);
                } while (!weakCompareAndSetInt(o, offset, v, v + delta));
                        return v;
        }
}

incrementAndGet() 메소드 내부에서 CAS 알고리즘의 로직을 구현하고 있다. getAndAddInt() 내부에서는 weakCompareAndSetInt() 메소드를 호출하여 메모리에 저장된 값과 현재 값을 비교하여 동일하다면, 메모리에 변경한 값을 저장하고 true를 반황하여 while문을 빠져 나온다.

AtomicInteger내 Volatile

여기서 눈여겨 볼 접은 volatile int value; 이다.
volatile 변수는 가시성 문제를 해결하기 위하여 사용된다.
volatile키워드가 붙어있는 객체는 CPU캐시가 아닌 메모리에서 값을 참조한다.

그러면 왜 굳이 volatile을 사용하여 메모리에서 직접 값을 참조하는데 CAS알고리즘 적용이 필요할까?

volatile 키워드는 오직 한개의 쓰레드에서 쓰기작업을할때, 그리고 다른 쓰레드는 읽기작업만을 할떄 안정성을 보장한다.

하지만 AtomicInteger는 여러 쓰레드에서 읽기/쓰기작업을 병행한다.

그래서 CAS 알고리즘을 사용하여 2중 안전을 기하는 방법을 사용한다.

예상 면접 질문 및 답변

synchronized의 문제점은?

synchronized는 스레드가 해당 블록에 lock을 걸면 lock에 접근하는 스레드들은 Blocking되기 때문에 성능 저하로 이어진다. 스레드가 Blocking 상태에 들어가면 아무 작업도 하지 못해 자원이 낭비되고, 상태가 변경되는 동안에도 시스템의 자원을 사용하기 때문이다.

atomic type에 대해 설명

atomic type은 멀티 스레드 환경에서 원자성을 보장하기 위한 개념이다. CAS 알고리즘을 통해 non-blocking하면서 가시성과 원자성을 보장해 동기화 문제를 해결한다.

CAS 알고리즘에 대해 설명

CAS 알고리즘은 현재 스레드가 가지고 있는 기존값과 메모리가 가지고 있는 값을 비교해 같은 경우 변경할 값을 메모리에 반영하고 true를 반환한다. 다른 경우에는 변경값이 반영되지 않고 false를 반환한 다음 재시도를 하는 방식으로 동작한다. CAS 알고리즘을 통해 가시성과 원자성 문제를 해결할 수 있다.

추가 Volatile 개념

volatile로 선언된 변수가 있는 코드는 최적화되지 않습니다.
volatile 키워드는 변수를 'Main Memory에 저장하겠다'라고 명시하는 것입니다.
변수의 값을 Read할 때마다 CPU cache에 저장된 값이 아닌, Main Memory에서 읽는 것입니다.
volatile 은 Main Memory에 read & write를 보장하는 키워드입니다.
Multi Thread 환경에서 하나의 Thread만 Read&Write 하고, 다른 Thread들은 Only Read가 보장되는 경우에 사용합니다.
Multi Thread 환경에서 하나의 Thread만 read & write하고 나머지 Thread가 read하는 상황에서 가장 최신의 값을 보장
여러 Thread가 write하는 상황이라면 race condition을 해결 할 수 없다. synchronized를 통해 변수 read & write의 원자성(atomic)을 보장해야 합니다.

멀티 스레드로 인한 동시성 문제를 해결하기 위해 Java는 synchronized와 Atomic타입이 있다.

그런데 왜 Atomic 타입은 Thread-safe하다고 할까?

Atomic & Concurrent & volatile

(ConcurrentHashMap의 메서드에서는 일부 로직에 synchronized 키워드도 있었지만 ConcurrentLinkedQueue에서는 그마저도 없이 volatile만 사용하고 있었다.)

멀티 프로세서 아키텍처(java memory model)

프로세서는 프로그램 명령 실행을 담당한다. 따라서 RAM에서 프로그램 명령과 필요한 데이터를 모두 검색해야 한다. CPU는 초당 정말 많은 수의 명령을 수행할 수 있기 때문에 모든 것을 RAM에서 직접 가져오는 것은 효율이 좋지 않다. 이를 개선하기 위해 프로세서는 캐싱과 같은 기능을 사용한다.

코어마다 각자 캐시를 갖고 있다. 이렇게 되면 캐시 일관성 문제가 발생할 수는 있으나 전체 성능이 향상된다.

CPU 내에는 성능 향상을 위해서 L1 Cache가 내장되어 있습니다.

CPU 코어는 메모리에서 읽어온 값을 캐시에 저장하고, 캐시에서 값을 읽어서 작업합니다.

값을 읽어올 때 우선 캐시에 해당 값이 있는지 확인하고 없는 경우에만 메인 메모리에서 읽어옵니다.

그러다보니 도중에 메모리에 저장된 변수의 값이 변경되었는데도 캐시에 저장된 값이 갱신되지 않아 메모리에 저장된 값과 달라지는 경우가 발생합니다.

동기화 문제를 방지하는 것이 volatile키워드

변수를 volatile로 선언하면 메인 메모리 영역을 참조하게 되므로 다른 스레드라도 같은 메모리 주소를 참조

Multi Thread 환경에서 여러개의 Thread가 write하는 상황이라면 race condition을 해결할 수 없습니다.

→ 이럴 경우에는 synchronized를 사용하여 원자성(atomic)을 보장해야 합니다.

synchronized 키워드와 volatile 키워드의 차이점을 알기 위해 Mutual Exclusion과 Visibility 개념을 설명한다.

Mutual Exclusion: 한 코드 블록은 하나의 스레드 또는 프로세스만 실행할 수 있음
Visibility: 한 스레드가 공유 데이터를 변경하면 다른 스레드에서도 볼 수 있음

synchronized 키워드는 Mutual Exclusion과 Visibility 모두 지원한다. 공유 변수 값을 수정하는 블록을 synchronized 처리하면 한 번에 한 스레드만 접근이 가능해진다. 공유 변수 값을 변경하면 메인 메모리에도 저장된다. Visibility만 지원해도 충분한 경우에 synchronized를 사용하는 것은 비효율적인 일이다.

volatile 키워드는 Visiblity만을 지원하고 싶을 때 사용한다. volatile로 지정된 변수의 값은 캐싱되지 않으며 모든 읽기쓰기는 메인 메모리에서 수행된다.

volatile은 volatile이 붙은 변수만을 메인 메모리에 기록하는 것이 아닌, 해당 변수와 함께 보여지는 모든 변수가 메인 메모리에 기록된다.

update() 시 Full Visibility를 지원한다는 것은 days 변수에 값이 쓰이면, 해당 쓰레드에서 볼 수 있는 모든 변수들 또한 메인 메모리에 기록된다는 것을 의미한다.

Blocking, Non-Blocking

synchronized 방식이 무한 루프를 돌면서 true를 반환할 때까지 기다리는 atomic 방식보다 성능이 우수하지 않나 생각을 할 수 있다.

왜냐하면 blocking된 스레드는 즉시 자신이 CPU 제어권을 다른 스레드에게 양보하는 반면, non-blocking된 스레드는 무한 루프를 돌면서 의미 없이 true를 반환받을 때까지 CPU를 붙잡고 있기 때문이다.

하지만 싱글 코어 환경에서 공유 변수 count를 사용하는 스레드가 100개가 있다면 어떨까?

synchronized 방식의 경우 blocking이므로 count를 사용하는 하나의 스레드 외에 나머지는 모두 스레드 상태가 blocked로 바뀌고 다른 일을 할 수 없다.

따라서 CPU 자원이 낭비가 되고, 공유 자원의 lock이 풀리더라도 특정 스레드의 상태를 blocked에서 running으로 바꾸어야 하고, 반대로 99개의 스레드를 running에서 blocked 상태로 바꾸어야 하므로 atomic에 비해 성능이 느릴 수 밖에 없다.

반면 atomic 방식의 경우 non-blocking이므로 비록 무의미한 무한 루프를 돌 수도 있지만, true를 반환 받는 순간 스레드의 상태를 변경하는 일 없이 바로 이후 작업을 이어서 할 수 있다.

또한, non-blocking 방식은 무한 루프를 하면서 작업이 끝났는지 물어보지 않고 다른 작업을 해도 되므로 선택이 자유롭다.

참고
https://8156217.tistory.com/40
https://t0pli.tistory.com/220
https://8156217.tistory.com/41
https://steady-coding.tistory.com/568
https://truehong.tistory.com/71