Synchronization Tools[1]

내 블로그의 첫 게시물은 바로 운영체제 강의의 Synchronization Tool 챕터를 복습하는 글이다. 기말고사를 준비하면서 공부한 내용들을 블로그에 기록해 놓으면 복습하기도 수월할 것 같아서 글을 작성하게 되었다. 시간이 없으니 바로 정리해보자.

Background

여러 개의 프로세스들은 동시에 실행될 수 있으며, 따라서 shared data에 여러 개의 프로세스들이 동시에 접근하게 되면 데이터가 일관적이지 않게 된다. 따라서 여러 개의 프로세스들이 공유하는 데이터를 일관적으로 유지하려면 프로세스 간의 실행과 관계 메커니즘이 질서정연하고 협력적으로 이루어져야 한다.

Race Condition

race condition은 shared data에 대한 접근이 컨트롤되지 않은 채로 데이터 접근이 동시에 이루어질 경우 발생한다. 이름 그대로 두 개 이상의 프로세스가 하나의 shared data를 놓고 경쟁하는 상황을 의미하며, race condition이 발생하면 데이터의 값이 일관적이지 않고, 데이터에 액세스 하는 특정 순서에 따라 달라지게 된다.

위 그림을 보면 Thread 1과 Thread 2는 같은 데이터(k)를 공유한다. 만약 두 Thread 간의 수행속도에 차이가 있어서 Thread 1이 데이터에 먼저 접근해서 k를 수정하면, Thread 2는 그 뒤에 접근해서 변경된 k를 다시 수정하게 된다. 따라서 k의 값이 초기에 n으로 설정됐다면, Thread 1이 rx = rx + 1을 실행했을 때 k의 값은 n + 1이 되고, 이후 Thread 2에서 ry에 k를 load하여, ry = ry + 1 연산을 수행하면 ry = n + 1 + 1이 되는 것이다. 따라서 두 Thread의 접근 순서에 따라 k의 값이 변화하는 것이다.

Critical Section

따라서 각각의 프로세스들은 shared data를 위해 코드에 critical section을 가져야만 한다. 자원의 수정이 이루어지는 부분이 critical section으로 정의되어서, 하나의 프로세스가 critical section에 존재한다면 다른 프로세스들은 critical section에 진입할 수 없어야 하는 것이다. 각각의 프로세스들은 critical section에 진입하기 위해서는 permission을 요청 받아야 한다.

	while(true) {
    	/* entry section */
        	/* critical section */
        /* eixt section */
        	/* remainder section */

• entry section: critical section에 진입하기 위해 대기하는 공간. 이 곳에서 permission을 받아야지만, critical section에 진입할 수 있다.

• exit section: critical section에서의 작업을 모두 마치고, criticals section을 나가는 공간이다. exit section에서 프로세스가 critical section을 나가는 것이 확인되면, 다른 프로세스가 critical section에 진입할 수 있다.

Critical Section Problem

critical section이 유효한 동작을 하기 위해서는 다음의 문제들을 해결해야 한다.

1. Mutual Exclusion:

mutual exlusion은 critical section의 기본 개념으로 Process P1이 critical section에 진입해 있다면, 다른 프로세스 들은 critical section에 진입할 수 없어야 한다.

2. Progress

critical sction이 비었을 때, critical section에 진입을 원하는 프로세스 p[1] ~ p[n]이 있다면, 진입 순서에 대한 결정은 이들에 대해서만 이루어져야 하며, 선택의 시간이 무기한 길어지면 안된다. 즉, critical section이 비어있고, 진입을 원하는 프로세스가 있다면 진입할 수 있어야 한다는 것이다.

3. Bounded Waiting

프로세스 p1이 critical section에 진입을 요청했다면, 그 요청이 허락되기 전까지(즉 p1이 critical section에 진입할 때까지), 다른 프로세스들이 critical section에 진입할 수 있는 횟수는 제한되어야 한다.

• progress와의 차이점은 progress는 critical section 진입을 원하는 프로세스 집단에서의 선택에 대한 시간을 제한해야 한다는 것이고, bounded waiting은 하나의 프로세스가 진입을 하기까지의 시간에 대해서 제한되어야 한다는 것이다.

Critical Section Solution

Interrupt-based Soution

: 가장 원초적인 방법으로 접근하는 방식이다. 바로 entry section에서는 interrupt를 발생시키지 못하게 하는 것이다. 즉, critical section이 non-preemption으로 설정되는 것이다. 이로써, 하나의 프로세스가 critical section에 있을 때 다른 프로세스들은 critical section에 진입할 수 없으므로, mutual exclusion이 해결되었다. 그러나, critical section에 있는 프로세스가 critical section을 독점해버린다면, 다른 프로세스들은 critical section에 진입하지 못하는 starvation이 발생한다. 또한 멀티코어에서는 대기하던 다른 프로세스가 core2에 들어가서 critical section에 진입해버릴 수도 있다. 따라서 interrupt-based는 critical section의 솔루션이 되지 못한다.

One Software Solution

: 두 개의 프로세스가 있으며 instruction은 atomic하게 수행됨을 가정한다. 솔루션이다. turn 이라는 변수를 설정하여 entry section에서 대기하다가 turn이 자기에게 있을 경우에만 critical section에 진입할 수 있다.

그러나 이것 역시도 mutual exclusion은 해결하지만 progress를 해결하지는 못한다. p[j]의 수행속도가 더 빠르다면, p[j]가 critical section에서 작업을 마치고 나와서 turn을 i에게 넘겨준 뒤, remainder section을 p[i]보다 더 빠르게 마치고 나온다면, critical section이 비어있음에도 p[j]는 critical section에 진입하지 못하게 된다. 왜냐하면 turn을 넘겨받은 p[i]는 아직 remainder section에서 후속 작업을 처리하고 있기 때문이다.

Peterson's Solution

따라서 이러한 문제점들을 해결하고자 나온 것이 바로 peterson's solution이다. 마찬가지로, 두 개의 프로세스가 있다고 가정하며, instruction은 atomic하게 수행되어야 한다. 이 방법에서는 turn 외에도 flag라는 bool 변수를 하나 더 사용한다.

	while (true){ 
    	flag[i] = true; 
        turn = j;
        
        while (flag[j] && turn == j); // entry section
        
        /* critical section */
        
        flag[i] = false; // exit section
        
        /* remainder section */}

flag는 자신의 준비상태를 나타내는 것이다. 즉, 자신이 entry section에 대기할 때, flag = true가 되는 것이다. 따라서, turn이 p[i]에게 있더라도 p[i]가 준비되어 있지 않다면 (flag[i] = false), p[j]는 critical section에 진입할 수 있는 것이다. peterson's solution은 mutual exclusion, prgress, bounded waiting 세 가지를 모두 만족한다!

• 여기서 flag와 turn을 설정하는 순서가 매우 중요하니 잘 기억하고 있을 것!

Peterson's Solution - Problem

하지만 peterson's solution에도 문제점은 있다. 바로 코드의 실행 순서를 마음대로 바꿀 수 있는 현대의 아키텍처에서는 petorson's solution의 올바른 작동이 보장되지 않기 때문이다.

• Out - of - Older Execution: 프로세서나 컴파일러에서 프로세스의 성능을 올리기 위해 실행 순서를 바꿀 수 있음. (reorder)

• 위에서 언급한 듯이 peterson's solution에서는 flag와 turn 값을 설정하는 순서가 매우 중요하다고 했다. 만약 원래 순서가 기억나지 않는다면 잠깐 다시 위로 가서 코드를 확인하고 오자.

- Two process critical section access at the same time! (Feat. reorder)

: 위의 그림에 대해서 설명하자면, 우선 reorder로 인해 turn과 flag의 설정 순서가 바뀐 상황이다. 먼저 process 0은 turn을 1로 설정한 뒤, flag 값을 미처 바꾸지 못하고 interrupt가 발생한다. (이 상황에서 flag[0] = false이다.) process 1도 얼마 뒤에 turn = 0, flag[1] = true로 설정한다. 이때, turn은 process 0에게 있지만 flag[0] = false이기 때문에, process 1은 critical section에 진입하게 된다. 이후 interrupt가 끝난 process 0은 전에 설정하지 못했던 flag[0]을 ture로 설정하게 된다. 따라서 turn = 0이고 flag[0] = true이므로 process 0 도 critical section에 진입하게 되면서 두 개의 프로세스가 동시에 critical section에 접근한 것이다!

Hardware Support for Synchronization

따라서 Synchronization을 해결하기 위해, 하드웨어 수준에서도 많은 기능이 제공된다.

Three forms hardware support :

Memory barrier, Atomic instructions, Atomic variables

1. Memory Barrier

: Memory barrier는 CPU나 컴파일러에게 memory barrier 전후의 명령문을 순서에 맞게 살행하도록 강제시키는 것이다. 즉, memory barrier 전의 명령문이, memory barrier 후에 있는 명령문보다 늦게 실행되어서는 안되는 것이다.

• Strongly ordered

  instruction의 실행 순서를 무조건 지킴.

• Weakly ordered

  instruction의 실행 순서가 살짝 바뀔 수 있음.

2. Atomic Instructions :

: instruction이 atomic 하게 수행된다는 것은 연산이 중간에 중단되지 않고 고정된 순서로 끝까지 실행됨을 의미한다.

• Test-and-Set Inctruction

  

Test-and-Set은 하드웨어적으로 구현되었기 때문에 하나의 명령어로 취급해도 된다. 따라서 위의 그림은 그저 SW로 풀어낸 코드에 불과하다. 코드를 보면 결과값으로 항상 입력받은 boolean 값을 반환하며, 입력된 boolean은 언제나 true로 설정된다. 따라서 Test-and-Set은 lock을 반환하는 함수로 사용될 수 있다.

do{
	while(TestAndSet(&lock)); // entry section
    
    	// critical section
        
    lock = FALSE; // exit section
    
    	// remainder section
        
} while(TRUE);

lock = false인 경우만 진입이 가능하고, TestAndSet(&lock)은 무조건 lock을 ture로 설정하기 때문에 exit section에서 lock = false로 설정해야 다른 프로세스가 critical section에 진입할 수 있다. 따라서 mutual exclusion을 만족한다.

• Compare-and-Swap Instruction

compare_and_swap에서는 총 3개의 입력 파라메터를 받는다. 입력받은 value가 기대하는 값과 같다면 value에 새로운 값을 쓰고 그렇지 않다면, 입력받은 원래 value를 그대로 리턴하는 작업만 수행한다. 멀티 쓰레드 및 코어 환경에서 CPU는 메인 메모리에서 변수값을 참조하는 것이 아니라, CPU 캐시에서 변수값을 참조하게 된다. 이때, 메모리에 있는 값과 CPU의 캐시 변수값이 다른 경우를 가시성 문제가 발생한다고 하는데, CAS 알고리즘을 사용해 이를 해결할 수 있다. 현재 쓰레드에 있는 값과 메모리에 있는 값을 비교해서 같은 경우에만 새로운 값으로 교체하는 것이다.

3. Atomic Variables

atomic variable 은 말 그대로 원자성을 보장하는 변수이다. atomic variable은 CPU 캐시가 아닌 메모리에서 값을 참조한다. 따라서 멀티 쓰레드 환경에서의 가시성 문제를 해결하기 위해 사용하는 CAP 알고리즘에서는 atomic variable을 사용해야 정확하게 메모리 값과 비교하여 새로운 값을 쓸 수 있다.

next...

사실 chapter 6. Synchronization Tools에 대한 정리를 모두 하려고 했는데 생각보다 내용이 너무 길어져서 글을 두 개로 나눠야 할 것 같다.

위에서 언급한 Memory barrier, Atomic Instrunction, Atomic variables는 하드웨어적으로 구현한 부분들이기 때문에 프로그래머가 직접 확인하고 적용하기에는 다소 어려운 부분들이 있다. 하지만 다음 글에서 다룰 Mutex Locks와 Semaphore는 critical section를 해결하기 위해 SW적으로 구현한 Tool들이기 때문에 함께 보면 더 좋을 것 같다..!