Synchronization Toole(동기화 도구들)

Background

병렬 수행(Concurrent Execution)은 여러 프로세스가 동시에 실행되는 것이다. 이러한 프로세스는 언제든 인터럽트가 발생할 수 있으며, 이 경우 현재 실행 중인 작업을 부분적으로만 완료하게 된다. 이와 같은 병렬 수행 환경에서는 공유 데이터에 대한 동시 접근이 데이터 불일치를 초래할 수 있다. 이를 해결하기 위해 협력하는 프로세스들 사이에서 순차적 실행을 보장하는 메커니즘이 필요하다. 

예를 들어 '생산자-소비자 문제'는 생산자가 데이터를 생성하여 버퍼에 넣고, 소비자가 그 데이터를 사용한다. 이때 모든 버퍼를 채우는 것이 목표라면, 버퍼의 수를 추적하는 정수 카운터를 사용할 수 있다. 카운터는 초기에 0으로 설정되고 생산자가 새로운 데이터를 생성하여 버퍼에 넣을 때마다 증가한다. 반대로 소비자가 데이터를 사용하면 카운터는 감소한다. 이렇게 하면 버퍼의 상태를 정확하게 추적하고, 생산자와 소비자 사이의 동기화를 유지할 수 있다. 

 

Race Condition(경쟁 상황)

경쟁 상황은 두 개 이상의 프로세스나 스레드가 공유 데이터에 대해 동시에 접근하려고 할 때 발생한다.  이는 프로세스나 스레드의 실행 순서에 따라 결과가 달라질 수도 있다. 

예를 들어, 위의 예에서는 'counter++'와 'counter--' 연산이 서로 경쟁하는 상황을 보여준다. 이 두 연산은 각각 레지스터 register1과 register2를 사용하여 counter 값을 변경하는데 두 연산이 번갈아가며 실행되는 경우, 즉 실행이 섞이는 경우(counter의 초기값이 5라고 가정하면) 다음과 같은 결과를 볼 수 있다:

 

1. 생산자가 'register1 = counter'를 실행합니다. (register1 = 5)

2. 생산자가 'register1 = register1 + 1'를 실행합니다. (register1 = 6)

3. 소비자가 'register2 = counter'를 실행합니다. (register2 = 5)

4. 소비자가 'register2 = register2 - 1'를 실행합니다. (register2 = 4)

5. 생산자가 'counter = register1'를 실행합니다. (counter = 6)

6. 소비자가 'counter = register2'를 실행합니다. (counter = 4)

 

이 경우, 생산자와 소비자의 연산 순서에 따라 counter의 최종 값이 달라지게 된다. 이런 결과는 우리가 원하는 것이 아니므로, 이를 방지하기 위해 동기화 메커니즘이 필요하다. 동기화 메커니즘을 통해 한 시점에 하나의 프로세스만이 공유 데이터에 접근할 수 있도록 제어할 수 있다.

 

The Critical-Section Problem

임계 구역(Critical Section)문제는 여러 프로세스가 공유된 데이터를 동시에 접근하려고 할 때 발생하는 동기화 문제이다. 임계 구역은 서로 다른 프로세스가 공유하는 변수, 테이블, 파일 등을 변경하는 작업을 포함하는 코드 부분이다. 

예를 들어, n개의 프로세스 {p0, p1, ... pn-1}가 있을 때, 각 프로세스는 공유 변수를 변경하거나 테이블을 업데이트하거나 파일을 쓰는 등의 작업을 수행하는 임계 구역의 코드 세그먼트를 가질 수 있다. 하나의 프로세스가 임계 구역에 있을 때는 다른 프로세스가 그 프로세스의 임계 구역에 들어갈 수 없어야 한다. 

 

Critical Section

do { 					// entry section(진입구역) : each process must ask permission(허가) to enter critical section(임계구역진입)
	entry section
		critical section	// critical section(임계구역)
	exit section
		remainder section	// exit section(퇴장구역)
} while(true);				// remainder section(나머지 구역)

 

Solution Critical-Section Problem

임계 구역 문제 해결 방법 3가지

1. 상호 배제(Mutual Exclusion) : 하나의 프로세스가 자신의 임계 구역에서 실행 중일 때, 다른 모든 프로세스들은 자신의 임계 구역에서 실행할 수 없어야 한다.

2. 진행(Progress) : 임계 구역에서 실행 중인 프로세스가 없고, 임계 구역에 들어가길 원하는 프로세스가 있을 경우, 임계 구역에 들어갈 프로세스의 선택이 무한정 지연되어서는 안 된다.

3. 한정된 대기(Bounded Waiting) : 프로세스가 임계 구역 진입을 요청한 후 그 요청이 승인될 때까지 다른 프로세스들이 임계 구역에 진입하는 횟수에는 제한이 있어야 한다.

각 프로세스가 0이상의 속도로 실행된다는 가정하에 이루어지며 n개의 프로세스 간, 상대적인 속도에 대한 가정은 없다. 

 

운영체제에서 임계 구역을 다루는 방법은 선점형(preemptive)인지 비선점형(non-preemptive)인지에 따라 다르다. 선점형 커널 모드에 프로세스의 선점을 허용하며, 비선점형 커널은 커널 모드를 종료하거나, 블록되거나 자발적으로 CPU를 양보할 때까지 실행한다. 이는 기본적으로 커널 모드에서 경쟁 조건이 발생하지 않도록 한다.

현대의 멀티 코어 멀티 프로그래밍 시스템에서는 선점형이 필수적이므로 임계 구역을 제어하는 것이 중요하며, 복잡하기에 어렵다. 

 

Peterson's Solution

Peterson Solution은 두 프로세스가 임계 구역 문제를 해결하는 알고리즘이다. 두 프로세스가 두 개의 공유 변수를 사용함으로써 임계 구역에 대한 상호 배제를 보장한다. 

init turn : 어떤 프로세스의 차례인지 나타낸다. tunr 값은 0 또는 1이며, 값에 따라 P0 또는 P1 프로세스가 임계 구역에 들어갈 차례인지 결정한다. 

Boolean flag[2] : 프로세스가 임계 구역에 들어갈 준비가 되었는지를 나타낸다. flag[i]=true는 Pi프로세스가 임계 구역에 들어갈 준비가 되었음을 의미한다. 

 

로드(load) 및 스토어(store) 명령어가 atomic 이라는 가정은 명령어들이 중단될 수 없으며, 한 번에 완전히 실행되거나 실행되지 않는다는 것을 의미한다. atomic연산은 여러 단계로 구성될 수 있지만, 한 번 시작하면 중간에 중단되지 않고 완료된다. 따라서 load와 store 명령어가 atomic하다는 가정 하에 한 프로세스가 데이터를 읽거나 쓰는 동안 다른 프로세스가 동일한 데이터를 변경할 수 없고, 이를 통해 데이터의 동시 접근에 따른 충돌을 방지할 수 있다. 

 

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

1. 상호 배제(Mutaul Excluson) : 프로세스 Pi가 임계 구역에 들어갈 수 있는 경우는 flag[j] = false 또는 turn = i 일 때이다. 즉, 다른 프로세스가 임계 구역에 들어가지 않았을 때만 가능하다. 

2. 진행(Progress) : 만약 다른 프로세스가 임계 구역에 들어가지 않는다면, 프로세스 Pi는 언제든지 임계 구역에 들어갈 수 있다.

3. 한정된 대기(Bounded Waiting) : 두 프로세스가 모두 임계 구역에 들어가려고 준비가 되어 있더라도, 하나의 프로세스가 임계 구역에서 나온 후에 다른 프로세스가 임계 구역에 들어갈 수 있다. 

 

Synchronization Hardware

소프트웽만으로는 한계가 있기에 임계 구역 코드를 구현하기 위해 많은 시스템에서 하드웨워 지원을 제공하고 있다. 

즉, 임계 구역을 보호하기 위해 하드웨어 동기화 방법은 대부분 locking 개념에 기반을 두고 있다. 

Uniprocessors는 인터럽트를 비활성화하여 임계 구역이 실행되는 동안 선점을 방지할 수 있다. 이렇게 하면 실행 중인 코드가 선점 없이 실행된다. 그러나 멀티 프로세서 시스템에서는 인터럽트를 비활성화하면 모든 프로세서에 인터럽트 비활성화 메시지를 전달해야 하므로 확장성이 제한된다. (비효율적)

현재의 기계들은 특별한 Atomic 하드웨어 명령어를 제공한다. Atomic이란 인터럽트가 걸리지 않고 메모리 단어를 테스트하고 값을 설정하거나 두 메모리 단어의 내용을 교환하는 등의 작업을 수행할 수 있다.

do {
    acquire lock // 잠금 획득
    // critical section (임계 구역)
    release lock // 잠금 해제
    // remainder section (나머지 구역)
} while (TRUE);

이를 통해 동시에 여러 프로세스가 임계 구역에 진입하는 것을 방지할 수 있다. 

 

test_and_set Instruction

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

test_and_set 명령어는 원자적으로 실행되는 명령어로, 인자로 받은 target의 원래 값을 반환하고, target의 값을 TRUE로 설정한다. 이 명령어가 원자적으로 실행되기 때문에 인터럽트가 발생하지 않는다. 

 

Mutex Locks

뮤텍스(Mutex, Mutual Exclusion) 락은 여러 스레드가 동시에 공유 자원에 접근하는 것을 방지하기 위해 사용되는 동기화 기법 중 하나이다. 이전에 제시한 `test_and_set` 함수와 같은 솔루션은 복잡하고 일반적으로 애플리케이션 프로그래머들이 접근하기 어려워, 운영 체제 디자이너들은 뮤텍스 락과 같은 소프트웨어 도구를 만들어 임계 구역 문제를 해결하고자 했다.

뮤텍스 락을 사용하면, 임계 구역에 접근하기 전에 락을 획득(`acquire()`)하고, 접근이 끝난 후에는 락을 해제(`release()`)합니다. 이렇게 하면 한 번에 하나의 스레드만이 임계 구역에 접근할 수 있게 되어, 데이터의 일관성을 유지할 수 있다.

 

뮤텍스 락의 상태는 Boolean 변수로 표현되며, 이 변수는 락이 사용 가능한지 여부를 나타냅니다. 락을 획득하거나 해제하는 `acquire()`와 `release()` 함수는 원자적으로 실행되어야 한다. 즉, 이들은 한 번에 완전히 실행되거나 실행되지 않아야 하며, 이를 위해 하드웨어 원자적 명령어를 통해 구현되는 경우가 많다.

 

그러나 이러한 뮤텍스 락 솔루션은 바쁜 대기(Busy Waiting)를 필요로 한다. 즉, 스레드가 락을 획득할 수 있을 때까지 계속해서 락의 상태를 확인해야 한다. 이러한 락은 스핀락(Spinlock)이라고도 부른다. 이는 CPU 시간을 낭비할 수 있으므로, 스레드가 락을 획득할 수 있을 때까지 대기 상태로 전환하는 방식의 락이 개발되었다.

 

Semaphores

세마포어(Semaphore)는 프로세스가 활동을 동기화하는 데 뮤텍스 락보다 더 정교한 방법을 제공하는 동기화 도구이다. 세마포어는 바쁜 대기가 필요하지 않은 동기화 기법으로, 락을 획득할 수 없는 스레드가 CPU를 계속 점유하지 않고 대기 상태로 전환할 수 있다.

 

wait(S) { // CS 진입 시도
	while (S <= 0)
	; // busy wait
	S--;
}

Signal(S) { // CS 퇴장
	S++;
}

세마포어는 정수 변수 S와 두 개의 원자적 연산, 즉 `wait()`과 `signal()`으로 구성된다. `wait()` 연산은 임계 구역에 진입하려는 시도를 나타내며, `signal()` 연산은 임계 구역에서 퇴장을 나타낸다. 이들 연산은 원자적으로 실행되어야 하므로, 두 프로세스가 동시에 같은 세마포어에 `wait()`과 `signal()`을 실행할 수 없다.

 

세마포어는 카운팅 세마포어와 이진 세마포어 두 가지 유형이 있다. 카운팅 세마포어의 값은 제한 없이 변경될 수 있으며, 이진 세마포어의 값은 0과 1 사이에서만 변경될 수 있다. 이진 세마포어는 뮤텍스 락과 동일하게 작동한다.

 

세마포어는 다양한 동기화 문제를 해결할 수 있다. 예를 들어, P1과 P2라는 두 프로세스가 있고, S1이 S2보다 먼저 일어나야 한다고 가정한다. 이 경우 0으로 초기화된 "synch"라는 세마포어를 생성하여 S1이 실행된 후 `signal(synch)`를 호출하고, P2에서는 `wait(synch)`를 호출한 후 S2를 실행하게 할 수 있다.

 

그러나 세마포어를 사용하면서 주의해야 할 점은, 바쁜 대기가 필요하지 않게 `wait()`, `signal()` 연산을 재정의하면서 프로세스가 `wait()` 연산을 실행하고 세마포어 값이 양수가 아닌 경우 프로세스를 중지시킬 수 있다는 점이다. 그리고 이후 자원이 해제되면 중지된 프로세스를 다시 실행하게 된다. 이렇게 함으로써 바쁜 대기 문제를 해결할 수 있다.

 

https://os.ecci.ucr.ac.cr/slides/Abraham-Silberschatz-Operating-System-Concepts-10th-2018.pdf