운영 체제 (Operating System) - 9. 동기화 (1)

1. Data Consistency

이번 강의는 Data Consistency(데이터 일관성)를 해치는 동시 접근 문제에 대해서 알아보자. 데이터 일관성을 유지하기 위해서 서로 협력하는 프로세스들이 순차적으로 수행하게 만드는 동기화 기법이 필요하다. 이를 Process synchronization이라고 표현한다. 그렇다면 Data consistency라는게 어떤 상황에서 발생할까? Shared memory를 사용하는 A와 B가 있다고 가정하자. 다음은 그 프로세스의 코드이다.

 얼핏 보기에는 어떤 문장이 먼저 실행되든지 한 문장씩 실행되면 되므로 Data consistency를 해치지 않을 것 처럼 보인다. 하지만 이를 어셈블리로 분해해서 레지스터까지 고려한다면 이야기는 달라진다. CPU는 계산을 위해서 메모리의 데이터를 Register로 가져와서 instruction들을 실행함으로써 문장을 실행하는데, 두 문장의 instruction의 순서가 꼬일 수 있다는 것이다. 즉 다음과 같이 Data consistency를 해칠 수도 있다.

 

 

2. Critical section 해결 알고리즘 (SW)

이제 이러한 Data consistency를 유지하는 규칙을 설정해보자. Data consistency에 영향을 줄 수 있는 영역을 Critical section이라고 한다. 이 영역(Critical section)에 한 번에 오직 하나의 흐름만이 접근, 실행 하도록 규칙을 정함으로써 Data consistency를 유지할 수 있다.

 

- Critical section 문제를 해결하기 위해서는 알고리즘들이 아래와 같은 세 가지 조건을 만족해야 한다.

- Mutual exclusion(상호 배제) : 하나의 흐름이 Critical section에 접근했다면 다른 모든 흐름은 진입할 수 없다.

- Progress(진행) : Critical section을 진행중인 흐름이 없고, 진입하려는 흐름들이 존재한다면 즉시 어떤 흐름이 진입할 지 결정되어야 한다. (즉, 결정이 무안히 연기될 수 없다)

- Bounded Waiting : 어떠한 흐름이 Critical section에 진입할 때 까지 걸리는 시간엔 Limit이 존재한다. (즉, 무한히 기다리면 안된다)

 

이에 대해서 다음 알고리즘들을 살펴보고, 각 알고리즘이 어떠한 조건들을 만족하고 불만족하는지 알아보자 

 

2-1. 하나의 shared variable

turn을 활용하여 Mutual exclusion은 만족하지만, Progress나 Bounded waiting은 만족하지 않는다 (P1이 먼저 실행된다면 Critical section 진입이 불가능하고, 무한히 기다려야할 가능성이 존재하므로)

 

2-2. 두개의 shared variable

Progress를 위해 Shared variable을 2개로 확장하고, critical section 전인 Entry section에서 상대의 Shared variable을 바꿔서 진행을 막는 방식으로 구현하였다. 이 또한 Mutual exclusion은 만족하나, Progress나 Bounded waiting은 불만족 한다. 그 이유는 Deadlock 때문이다. 위에 명시된 순서대로 instruction이 실행된다면 결국 두 프로세스 모두 while문에 갇히게 된다. 그럼 Mutual exclusion은 왜 만족하냐? 라고 생각할 수 있는데, Deadlock이 발생해도 두 Critical section에 하나의 흐름도 들어가지 않기 때문에 이 성질은 만족한다.

 

3.3 Peterson solution (세개의 shared variable)

Turn이라는 공통의 값을 이용하여 Deadlock 문제를 해결하는 방식이다. 이를 통해 두 Process가 동시에 수행되더라도 turn에 의해 수행 여부가 결정되므로(하나는 실행 되는것으로, 하나는 실행이 되지 않는 것으로) 모든 조건을 만족하게 된다. 

하지만 이 알고리즘에도 한계가 존재했다. 이에 대한 확장(더 많은 프로세스의 동시접근)과 증명(NP문제)이 어렵다는 것이다. 그래서 SW로의 Critical section문제 해결은 위축되었고, HW로의 해결이 제안되었다.

 

 

3. Critical section 해결 알고리즘 (HW)

HW를 이용하여 Critical section에 들어갈 때 Interrupt(HW의 Interrupt)를 Disable하면 원자적 실행의 보장 할 수 있으므로 Critical section 문제가 쉽게 해결되는 것 처럼 보인다. 하지만 이 방식에도 문제가 존재한다.

 

1. User program이 Interrupt를 Control하는 것은 바람직 하지 않다

2. Scalable(프로세스 갯수의 확장이 가능)하지 않다

 

이에 따라 동기화를 위한 Instruction(Synchronization instruction)이 도입되었다. Synchronization instrucation이란 CPU의 지원으로 원자적(수행 중 방해 받지 않음)으로 수행되는 명령어를 일컫는다. 여기서 방해란 HW의 Instruction이나 SW 모든 것을 의미한다. 다음은 그 Instruction와 활용 예시이다.

 

3-1. Test and set

 

 

3-2. Swap

여기서 Bounded wait를 100%를 제공하지 못한다는 것은 synchronization instruction이 Bounded waiting을 제공하지 못하기 때문이다. Synchronization instruction을 실행할 때 Bounded wait는 User program에서 지원해줘야 한다. (왜냐하면 instruction은 단순한 명령셋이기 때문에, 우선순위라던가 상황 체크를 하지 않으므로) 따라서 좀더 Comprehensive한 동기화 primitive가 필요해지게 되었다. 

 

 

4. Semaphore

세마포어는 두개의 원자적 연산(Atomic operation)을 가지는 정적 변수로, 그 변수는 해당 연산을 통해서만 접근 가능하다. P는 -와 wait을, V는 +와 signal을 의미한다.

이를 구현 할 수 있는 방법은 크게 두가지로 나뉜다. while을 사용해서 CPU로 값의 변화를 계속 체크하는 Busy Waiting과 Queue를 활용하여 대기 중인 Process를 관리하는 Sleep queue 방식으로 나뉜다.

Busy waiting의 경우 CPU Cycle이 낭비되고, 누가 다음에 Critical section으로 들어가는 지 결정하지 못하므로 사용하지 않고, Sleep queue를 사용한다고 한다.

 

세마포어는 세마포어가 가질 수 있는 값에 따라서 Counting semaphore와 Binary semaphore로 나뉜다. Counting semaphore의 경우 범위가 정해져있지 않고, 초기 값이 가능한 자원의 수로 정해진다. 이는 0과 1만 가질 수 있는 Binary semaphore를 통해 구현할 수 있다. 이 모두 Atomic operation을 위해서 HW의 도움을 받아야 한다. 다음은 Binary semaphore와 Counting semaphore의 구현이다.

여기서 눈 여겨 볼 만한 것은 Counting semaphore가 두개의 Binary semaphore를 이용해서 구현된다는 점이다. 이렇게 2개를 사용해야 하는 이유는 C를 포함한 전체적인 Critical section에 대한 세마포어 S1과 C의 값에 따라 Block과 Signal을 담당하는 세마포어 S2가 필요하기 때문이다.

 

5. Semaphore의 문제

P/V를 System call로 구현하고, Kernel 내에서 처리하여 Semaphore 동작을 구현한다.

Kernel이 Single thread인 경우, Kernel 내의 수행이 Non-Preemptive이므로 Kernel에 들어간 것이 Critical section에 들어간 것과 동일하여 따로 동기화 해줄 필요가 없다.

하지만 Kernel이 Multithread인 경우에는 Kernel내에서 별도로 동기화를 해주어야 한다. (당연히)

하지만 문제는 Deadlock이 발생할 가능성이 존재한다는 점이다. P와 V가 분리되어 프로그래머의 실수로 할 수 Deadlock이 발생할 수 있다.

이에 대해 High-level에서 이러한 Deadlock로 부터 자유로움을 보장해줄 필요성이 생겼다. 그래서 등장한 개념이 Monitor이다. 

 

6. Monitor

Monitor란 한 순간에 하나의 Process만 Monitor에서 활동하도록 보장하는 기술로, Application이 Semaphore의 P와 V와 같은 연산에 대한 고려 없이도 Procedure호출만으로 동기화 문제를 해결할 수 있게 한다.

위 코드에 대한 메카니즘은 다음과 같다.

위와 같이 Monitor waiting area내의 queue를 이용하여 각 조건에 대해서 올바른 시기에 올바른 Procedure의 실행을 보장한다. 이에 대한 예시는 DB의 Transaction을 생각하면 쉽다.

조건에 맞을 때 동기화하여 실행의 단위 연산을 진행한다