OS - Process Synchronization1

---

🚀 OS - CPU Scheduling 2 에서 이어지는 내용입니다.

🧩 Process Synchronizition 문제

• 공유 데이터의 동시 접근은 데이터의 불일치 문제를 발생시킬 수 있음
• 일관성 유지를 위해서는 협력 프로세스간의 실행 순서를 정해주는 메커니즘 필요

🧩 Race Condition

Race Condition(경쟁 상태) 는 여러 프로세스들이 동시에 데이터에 접근하는 상황에서, 어떤 순서로 데이터에 접근하느냐에 따라 결과 값이 달라지는 상황을 말한다.
공유 데이터의 Concurrent access(동시 접근) 은 데이터의 불일치 문제를 발생시킬 수 있다. 따라서 Race condition을 막고 일관성을 유지하기 위해서는 협력 프로세스 간의 실행 순서를 정해주는 메커니즘인 동기화(Synchronization) 이 필요하다.

위와 같은 경쟁상태는 보통 MultiProcessor system, 즉 CPU가 많고 하나의 메모리(공유 메모리)를 사용할 때 벌어진다.또한 운영체제 커널 내부 데이터를 접근하는 루틴이 겹칠때도 벌어진다.

🧩 OS에서 Race Condition이 발생하는 경우

• Kernel 수행 중 인터럽트 발생 시
• Process가 System call을 하여 Kernel mode로 수행중인데 context switch가 일어나는 경우
• Multiprocessor에서 shared memory 내의 kernel data

커널 모드로 수행 중 인터럽트가 발생하는 경우

양쪽 다 커널 코드이므로 kernel address space를 공유

의도된 동작은 count++와 count--가 모두 반영되어 count가 초기값을 유지하는 것이지만, 만약 load 후 인터럽트가 발생하는 경우 인터럽트 결과는 반영되지 않고 count++만 반영된다.

이는 커널 모드의 수행이 끝나기 전에는 인터럽트를 받지 않도록(disable/enable)으로 문제를 해결할 수 있다.

Process가 System call을 하여 Kernel mode로 수행중인데 context switch가 일어나는 경우

두 프로세스의 주소 공간에서는 데이터를 공유하지 않지만, 시스템 콜을 수행하는 동안에는 둘 다 커널 주소 공간의 데이터에 접근한다. 따라서 커널 주소 공간에서 작업을 수행하는 도중에 CPU를 빼앗으면 race condition이 발생한다.

이는 커널 모드를 수행중일땐 CPU가 preept 되지 않도록 하고, 커널 모드에서 유저 모드로 돌아갈 때에는 preept되도록 함으로써 해결할 수 있다.

Multiprocessor에서 shared memory 내의 kernel data ( CPU가 여러개인 환경 )

어떤 CPU가 마지막으로 Count를 저장했는지에 따라 결괏값이 달라진다. 싱글 프로세서인 경우 1번에서와 같이 인터럽트 disable/enable 방법으로는 해결할 수 있지만 멀티 프로세서의 경우 인터럽트 제어로는 해결이 안된다.

한 번에 한 CPU만 커널에 들어갈 수 있도록 하는 방법이 있으나 이는 비효율적이다. 만약 두 프로세서가 서로 다른 데이터에 접근하여 race condition의 가능성이 없음에도 불구하고 한 번에 한 CPU만 커널에 들어갈 수 있기 때문이다.

따라서, 커널 내부에 있는 각 공유 데이터에 접근할 때마다 그 데이터에 대해서만 lock/unlock을 하는 방식으로 해결할 수 있다.

위에서 이제 문제상황들은 살펴보았고, 그렇다면 문제가 있다는 전제 하에, 즉 서로 다른 주체 둘이 공유 데이터를 접근하는 시도를 한다는 전제 하에 그 문제를 어떻게 풀 것인지 이제부터 볼 것이다.

🧩 Critical Section(임계 구역)

Critical section은 코드 상에서 race condition이 발생할 수 있는 특정 부분을 말한다. 즉 공유 데이터를 접근하는 코드 부분이다.
Critical section으로 인해 발생하는 문제들을 해결하기 위해서는 다음 조건들을 만족해야 한다.

🧩 Critical Section 해결 조건

• Mutual Exclusion (상호 배제)
  : 이미 한 프로세스가 Critical Section에서 작업 중이면 다른 모든 프로세스는 Critical section에 진입하면 안된다.
• Progress (진행)
  : Critical section에서 작업 중인 프로세스가 없다면, Critical Section에 진입하고자 하는 프로세스가 존재하는 경우 진입할 수 있어야 한다.
• Bounded Waiting (한정 대기)
  : 프로세스가 Critical Section에 들어가기 위해 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 Critical Section에 들어가는 횟수에 한계가 있어야 한다. 쉽게 말해 Critical Section에 진입하려는 프로세스가 무한정 기다려서는 안된다. (Starvation문제 방지)

🧩 Critical section 해결 방법

critical section 문제를 해결하는 단순한 방법은 Lock을 사용하는 방법이다. 즉, 한 프로세스가 critical section에 들어간다면 lock을 걸어놓아 다른 프로세스가 들어오지 못하게 하는 것이다.

그리고 프로세스가 critical section에서 빠져나오게 되면 lock을 해제하고 동시에 동기화 신호를 보내는 것이다. 동기화 신호는 다음 프로세스에게 critical section을 사용해도 좋다는 신호를 주는 것이다. 임계구역 문제를 해결하기 위한 3가지 조건인 상호 배제, 한정 대기, 진행의 융통성(progress)을 모두 만족하는 lock, unlock, 동기화 구현 방법을 알아보도록 하자.

예제 코드

#include <stdio.h>
typedef enum { false , true} boolean;
extern boolean lock = false;
extern int balance;

int main(){
    while(lock == true);
    lock = true;
    balance = balance + 10;
    lock = false;
}

c 언어는 불린함수가 없기 때문에 다음과 같이 typedef로 정의했다.

critical section에 문제가 되는 들어갈 변수는 balance이고, 잠금은 lock으로 걸어놓는다. false이면 프로세스가 들어가 balance를 쓸 수 있고, true이면 기다리도록 한다.

이제 아래 알고리즘들을 살펴보며 제시한 해결법과 문제점을 파악해보자.

Erroneous Algorithm 1

먼저 turn 변수 하나만 사용하여 알고리즘을 구현하였을 때의 모습이다. turn이 0일때 p0, turn이 1일때 p1이 critical section에 진입할 수 있도록 하였다. 또한 각자 프로세스가 critical section을 나올때 turn값을 바꿔 상대방 프로세스의 진입을 허락한다.
하지만, 위의 알고리즘 같은 경우 turn 변수를 사용하여 mutual exclusion을 보장하지만, progress는 보장하지 못한다.
그 경우는 다음과 같다.

위에 코드를 보면 반드시 교대로 critical section에 진입하게 되어있다. 무조건 상대편이 critical section에 들어갔다가 나와야지만 내 차례가 오기 때문이다.
하지만 프로세스마다 임계구역에 들어가려는 빈도가 다를 수 있다. 먄악 p0 이 더욱 빈번하게 임계구역에 들어가고 싶지만, 그렇다 하더라고 p1이 한번 임계구역에 무조건 들어갔다가 나와야지만 들어갈 수 있는 것이다. 따라서 progress 조건을 만족하지 못했다고 볼 수 있다.

Erroneous Algorithm 2

두번째로 flag 변수만을 사용하여 알고리즘을 구현한 경우이다. 이 알고리즘은 다음과 같이 실행된다. 먼저 loop 에 진입하면서 flag를 true로 설정하여 critical section에 들어가겠다고 알린다.
while(flag[j]);를 통해 상대 프로세스에게 flag가 true값을 가지는지 확인하고, true일 경우 대기한다.
상대 프로세스의 flag가 false가 되었을 때, critical section에 진입하게 된다.
critical section을 실행하고 나오면, 자신의 flag를 false로 만들어 critical section에 들어갈 생각이 없음을 알린다.

위 알고리즘도 문제가 없어보이지만 아래와 같은 문제가 발생한다.

만약 프로세스 i가 본인의 flag를 true로 만든 상태에서 CPU를 뻇긴다. 그 상황에서 CPU가 프로세스 j에게 간다. 그러면 프로세스 j도 flag를 true로 만든다.
이 상황에서는 양 프로그램 모두 flag만 true로 만들고 아무도 critical section에 들어가지 않은 상황이다. 이 상황에서 서로 while문의 flag를 들여다보면 상대방의 flag가 모두 true인 것이다. 또한 한 프로세스가 critical section에 들어갔다가 나와야지만 flag값을 바꾸지만, 아무도 critical section에 들어가지 못하니 flag값이 바뀔 일이 없다.
결과적으로 아무도 critical section에 들어가지 못하고 계속 대기하게 된다.

결과적으로 mutual exclusion은 해결하지만 아무도 critical section에 들어가지 못하는 상황이 발생한다.

Erroneous Algorithm 3 (Peterson's Algorithm)

위의 두가지 알고리즘 에러를 막기 위해, turn과 flag 변수를 함께 사용한 피터슨 알고리즘은 다음과 같다.

프로세스 p0과 p1이 있다. 먼저 p0은 flag를 true로 , turn은 1로 설정한다. while(flag[1] && turn = 1); 을 보면 flag[1] = true이고, turn == 1이면 기다려야 함을 알 수 있다. 이는 p1이 flag가 true라면 p1이 먼저 실행되도록 대기하겠다는 것을 의미한다. p1의 flag가 false라면, p0이 critical section을 실행하게 된다.

이 알고리즘이 앞에서 말한 3가지 조건에 부합하는지 살펴보자.

❗️ Mutual exclusion :
p0과 p1이 동시에 임계 영역에 들어간다는 것은 flag[0] = flag[1] = true라는 것인데, turn은 0또는 1의 값을 가질 수 밖에 없으므로 둥리 동시에 임계구역에 진입하지 못한다. 따라서 상호 배제는 보장한다.
❗️ Progress & bounded waiting :
p1가 임계 구역에 들어갈 준비가 되지 않았을 경우, flag[1] == false 이다. 즉 p0이 임계구역에 들어갈 수 있다.
p1가 while문에서 기다리고 있을 때, turn은 0이거나 1이다. 만약 turn이 0이면, p0이 임계구역에 들어갈 수 있으며, turn이 1이면 p1이 임계구역에 들어갈 수 있다.
p1가 임계구역을 나오게 되면 p1은 flag[1]을 false로 설정하고, p1가 turn을 0으로 전환하기 때문에 p0가 임계구역에 들어갈 수 있게 된다.

❗️ 따라서 세가지 조건을 모두 부합한다.

하지만 이렇게 완벽할 것 같은 피터슨알고리즘에도 문제가 존재한다.

Busy Waiting(spin lock)
만약 어떤 프로세스가 critical section에 들어가있는 상태에서 다른 프로세스가 CPU를 잡으면 while문을 돌게된다. 하지만 이 상황에서는 절대 빠져나갈 수가 없다. 본인의 CPU할당시간동안 계속 while문을 체크하지만 절대 빠져나갈 수가 없다.
이 경우 상대방에 CPU를 잡은 다음 while문을 빠져나갈 수 있는 조건을 만들어줘야지만 빠져나올 수 있다.
이러한 상황을 Busy waiting이라고 한다.

---

위에서는 복잡한 소프트웨어적인 접근으로 문제를 해결하려고 했다. 하지만 하드웨어적으로는 하나의 instruction만 주어지면 critical section 문제는 아주 쉽게 해결된다.

🧩 Synchronization Hardware

• 하드웨어적으로 Test & modify를 atomic하게 수행할 수 있도록 지원하는 경우 앞의 문제는 간단히 해결

앞에 문제가 생겼던 이유는 어떠한 데이터를 쓰거나 읽는 것을 하나의 instruction으로 처리하지 못했기 때문이다. 만약 어떠한 데이터를 읽으면서 동시에 쓰는, 즉 하나의 instruction으로 실행이 가능하다면 적어도 instruction 하나가 실행되는 동안에 CPU를 빼앗길 일은 없다.

보통 이런것과 관련된 instruction으로 Test_and_set을 꼽는다. 이 instruction은 a라는 값을 읽어오고 이 값을 1로 바꿔주는 instruction이다.

하드웨어적으로 이게 지원이 된다면 critical section에 들어가기 전에 lock을 걸고, 빠져나올 때 lock을 푸는 코드가 간단하게 구현이 된다.