[운영체제] 프로세스 동기화 (1/2)

본 게시글은 KOCW 이화여자대학교 반효경 교수님의 <운영체제> 강의를 듣고,
<혼자 공부하는 컴퓨터구조 + 운영체제> 책을 참고하여 정리한 내용입니다.
게시글에 포함되는 이미지 자료는 <운영체제> 강의에 포함된 강의 자료입니다.

데이터 접근 패턴 

프로세스 동기화에 대해 알아보기에 앞서 컴퓨터 시스템 내에서 데이터가 접근되는 패턴에 대해 먼저 알아봅시다.

 

데이터가 저장되어있는 위치에서 읽어와서 연산을 하고 수정된 결과를 다시 데이터에 반영을 하고, 데이터가 저장되는 Storage Box는 공유되기 때문에 동기화(synchronization) 문제가 발생합니다.

 

공유 데이터(shared data)의 동시 접근은 데이터의 불일치 문제를 발생시킬 수 있습니다.

그렇기 때문에 데이터의 일관성(consistency) 유지를 위해서는 협력 프로세스 간의 실행 순서를 정해주는 메커니즘(= 프로세스 동기화)이 필요합니다.

Race Condition

Race Condition이란 여러 프로세스들이 동시에 공유 데이터를 접근하는 상황을 의미합니다.

레이스 컨디션이 발생하면 데이터의 일관성이 깨지는 문제가 발생합니다.(데이터의 최종 연산 결과는 마지막에 그 데이터를 다룬 프로세스가 어떤 프로세스냐에 따라 달라짐)

 

하나의 저장공간을 공유하는 프로세스가 여럿 있는 경우 Race Condition의 가능성이 있음

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

• 커널 수행 중 인터럽트 발생
• 프로세스가 시스템 콜을 하여 커널 모드로 수행 중인데 context switch가 일어나는 경우
• 멀티프로세서에서 shared memory 내의 커널 데이터

Multiprocessor 환경이 아니라면, 일반적인 경우 프로세스는 자기 주소 공간만 접근하기 때문에 race condition 문제가 발생할 가능성이 거의 없습니다. 하지만, 프로세스가 직접 실행할 수 없는 부분은 시스템 콜을 통해 운영체제에 요청하게 됩니다. 이 때, 커널의 코드가 실행되게 되는데 OS 커널 코드는 여러 프로세스가 실행할 수 있기 때문에 문제가 생기게 됩니다. (커널의 데이터를 변경하는 도중 다른 인터럽트가 들어와 다른 루틴을 수행하게 될 경우 race condition의 가능성)

1. 커널  수행 중 인터럽트 발생

 

위의 그림은 커널모드 running 중 interrupt가 발생하여 인터럽트 처리루틴이 수행되는 경우입니다.

양쪽 다 커널 코드이므로 커널 주소 공간을 공유하게 됩니다.

 

고급 언어로 된 코드 한줄이 보통 CPU 내부에서는 여러개의 instruction을 통해 실행이 됩니다. 

ex) count 라는 메모리 변수값을 1 증가 시킨다.

• 메모리 변수 값을 CPU 레지스터로 불러들인다.
• 레지스터 값 1증가 시킨다.
• 레지스터의 값을 다시 메모리의 변수 위치에 쓴다.

위의 그림의 예시로 count 값의 변화를 살펴봅시다!

만약 레지스터로 불러들인 다음, 레지스터 값을 1 증가 시키는 작업 진행 중에 인터럽트가 발생했다면, 이 작업은 잠시 멈추고 인터럽트 처리 루틴으로 넘어가게 됩니다. 인터럽트 처리(count--)가 다 되면 다시 count++의 context로 돌아오게 되는데, 이때 count값은 1증가, 1감소 작업을 차례로 진행했으니 원래의 값과 동일해야겠죠? 하지만 count--의 작업은 반영이 되지 않습니다. (다시 원래 context로 돌아왔을 때 이전에 저장해두었던 값(1증가시키기 전 값)에서 count++ 의 작업을 마무리하기 때문)

 

이러한 문제를 해결하기 위해서는 인터럽트가 들어와도 인터럽트 처리루틴으로 넘기지 않고 대기 시킨다음 먼저하던 일을 다 한 후에 처리하도록 인터럽트를 막는 방식으로 작업의 순서를 정해주어야 합니다!

2. 프로세스가 시스템 콜을 하여 커널 모드로 수행 중인데 context switch가 일어나는 경우

위의 그림에서 시스템 콜에 의해 유저모드와 커널모드가 번갈아가며 실행되고 있습니다. 만약 사용자 프로세스가 시스템 콜을 하여 커널 모드로 프로세스 실행중에 timer interrupt (CPU 할당시간이 있기 때문)가 걸리게 되면?

위의 그림처럼 CPU 제어권이 다른 프로세스에게 넘어가게 됩니다. 다른 프로세스가 count++ 작업을 수행하지만, CPU제어권이 다시 PA에게로 돌아가게 되면 PA는 CPU 제어권을 넘겨줄때의 context에서 작업을 이어서 하기 때문에 결과적으로 PA가 수행하는 count++ 만 반영되게 됩니다. 

 

이런 경우는 프로세스가 커널모드에 있다면 CPU 할당시간이 끝나더라도 CPU를 preempt 하지 못하게 하는 방법으로 문제를 해결할 수 있습니다. (커널모드에서 유저모드로 빠져나올때 CPU를 빼앗기)

3. 멀티프로세서에서 shared memory 내의 커널 데이터

CPU가 여러개인 멀티프로세서 환경의 경우 위에서의 해결방법이었던 인터럽트를 막는 방법으로는 문제를 해결할 수 없습니다.

 

문제 해결 방법:

1. 커널을 접근하는 CPU가 매순간 하나만 있도록 커널 전체를 lock으로 막고 빠져나올 때 lock을 풀어주는 방법 (비효율적)

2. 공유 데이터에 접근할 때 그 데이터에 대한 lock / unlock 을 걸어서 프로세서의 접근을 제어하는 방법 (효율적)

Critical Section (임계구역)

Critical Section: 공유데이터를 접근하는 코드

각 프로세스의 code segment에는 공유 데이터를 접근하는 코드인 critical section이 존재합니다.

n개의 프로세스가 공유 데이터를 동시에 사용하기를 원하는 경우, 하나의 프로세스가 critical section에 있을 때 다른 모든 프로세스는 critical section에 들어갈 수 없어야 합니다.

 

Critical-Section Problem - 여러개의 프로세스가 critical section에 있다면 동기화 문제 가능성

해결책 1:  Lock (뮤텍스 락)

가정

• 두 개의 프로세스가 있다고 가정(P0, P1)
• 프로세스들의 일반적인 구조

do {
    entry section // lock
    critical section
    exit section // unlock
    remainder section
} while(1);

• 프로세스들은 수행의 동기화(synchronize)를 위해 몇몇 변수(synchronization variable)를 공유할 수 있다.

프로그램적 해결법의 충족조건

• Mutual Exclusion(상호배제): 여러 프로세스가 동시에 임계 구역에 들어가는 것을 막음(임계구역에는 하나의 프로세스만)
• Progress(진행): 아무도 임계구역에 없는 상태에서 들어가고자 하는 프로세스가 있으면 들어가게 해주어야 함
• Bounded Waiting(유한 대기): 프로세스가 critical section 에 들어가려고 요청한 후부터 요청이 허용되기 전까지 다른 프로세스들이 critical section 에 들어가는 횟수에 한계가 있어야 함(어떤 프로세스가 무한히 대기하는 경우가 없도록)

Algorithm 1

- synchronization variable: turn

int turn = 0; 
// turn 이 i 이면 Pi 가 critical section 에 들어갈 수 있음

- Process P0

do {
    while (turn != 0); // turn 이 0 이 아니면 turn 체크하며 무한루프 대기
    critical section
    turn = 1; // critical section 나올 때 상대방의 차례로 넘겨줌
    remainder section
} while(1);

• mutual exclusion 조건 충족O / but progress 조건 충족X
• 동시 접근은 일어나지 않지만 다른 프로세스가 임계구역에 들어갔다 나와야만 차례가 돌아옴

Algorithm 2

- synchronization variable: flag

boolean flag[2] = { false }; // flag [i] == true 이면 Pi 가 critical section 에 접근할 준비완료된 것

- Process P0

do {
    flag[i] = true; // 임계구역에 들어가고자 하는 의사 표시
    while (flag[j]); // 상대방의 flag 체크 (상대방이 임계구역에 있다면(=true) 대기)
    critical section
    flag[i] = false; // 나올 때 false로 바꿔줌(unlock)
    remainder section
} while(1);

• mutual exclusion 조건 충족O / but progress 조건 충족X
• 만약 임계구역 들어가려고 flag를 true로 바꾼 상태에서 CPU 빼앗긴다면 임계구역에 아무도 없는데 true 상태인 것
• 다른 프로세스는 임계구역에 누가 있다고 판단해서 계속 기다리는 상황이 생김 -> 아무도 들어갈 수 없는 상황이 생길 수 있음

Algorithm 3 (Peterson's Algorithm) 

- synchronization variable: turn, flag 둘다 사용

do {
    flag[i] = true; // enter 의사 표현 (flag true로 변경)
    turn = j; // 임계구역 들어가기 전에 turn 변수 변경 (turn 상대방으로 세팅)
    while (flag[j] && turn == j); // 상대방의 flag, turn 체크 (turn이 상대방 && flag도 true이면 기다림) 
    critical section
    flag[i] = false; // 나올 때 unlock
    remainder section
} while(1);

• 변수를 두개 모두 사용하기 때문에 중간 어디에서 CPU를 빼앗긴다 하더라도 모든 조건 충족하는 알고리즘
• 하지만 Busy Waiting(= spin lock) 이라는 문제가 있음 - 계속 CPU 와 메모리를 쓰면서 기다리게 됨(비효율적)
• 다른 프로세스가 critical section 에 들어가있으면 본인의 CPU 할당시간 동안 계속 while 문을 돌면서 critical section 에 들어갈 수 있는지 체크함. but 상대방이 CPU를 잡기 전에는 체크하는 값이 바뀌지 않음 

Synchronization Hardware

프로세스 동기화 문제는 데이터를 읽고 쓰는 것이 하나의 instruction 으로 이루어져있지 않아서 발생하는 문제입니다.

하드웨어적으로 Test & modify를 atomic하게(동시에) 수행할 수 있도록 지원한다면 이러한 문제는 간단히 해결할 수 있습니다.

 

- synchronization variable: lock

boolean lock = false;

do {
    while (Test_and-Set(lock)); // 원래 값 읽어내고(lock 체크) 그 자리에 true로 세팅
    critical section
    lock = false; // 나올 때 unlock
    remainder section
} while(1);

해결책 2: Semaphore(세마포어)

세마포어는 일종의 추상자료형(논리적으로 정의하는 것. 실제 컴퓨터에서 구현되는 것과 별개)입니다.

프로그래머가 critical section 에 들어가는 모든 코드를 신경쓰긴 힘드니 추상자료형(프로퍼티와 메서드로 이루어진 논리자료형)으로 연산을 통해 확인할 수 있게 만드는 것입니다.

세마포어는 공유 자원이 여러 개 있는 상황에서도 적용이 가능한 동기화 도구입니다. (cf. 뮤텍스 락은 하나의 공유자원 대상)

세마포어의 종류

1. counting semaphore

- 자원의 개수가 여러 개 -> 0 이상의 정수값을 사용

 

2. binary semaphore (= mutex lock)

- 0 또는 1의 값만 가짐

- mutual exclusion (lock / unlock) 에 사용한다. (= 뮤텍스 락)

Semaphore S

- integer 변수

- 아래의 두 가지 atomic 연산(P, V)에 의해서만 접근 가능

 

P(S): while (S <= 0) do no-op
      S--;

 

V(S): S++;

 

• P 연산 
  • S값이 0이하(=쓸 수 있는자원이 없음)인 동안 while문 돌면서 wait
  • S값이 양수가 되면(= 누군가가 자원을 내어놓으면) 그 때 S--, 자원 획득, lock
• V 연산
  • 공유 자원 반납, S++, unlock

// Synchronization variable
Semaphore mutex;

// Process Pi
do {
    P(mutex);
    critical section
    V(mutex);
    remainder section
} while(1);

세마포어를 사용하게 되면, 세마포어 변수인 mutex를 1로 놓고 lock을 걸때(= 임계구역에 들어갈 때) P연산, 풀 때(임계구역에서 빠져나올때) V연산을 해주면 임계구역 문제가 자연스럽게 해결됩니다. 하지만 busy-waiting (= spin lock)문제는 여전히 발생하는데, 이는 효율적이지 못하므로 Block & Wakeup (= sleep lock) 방식으로 구현할 수 있습니다.

Block & Wakeup Implementation

세마포어 정의

- S: 세마포어 변수

- L: 프로세스 대기 큐

- block: 커널은 block을 호출한 프로세스를 suspend 시킴. 이 프로세스의 PCB를 세마포어에 대한 wait queue에 넣음

- wakeup(P): block된 프로세스 P를 wakeup 시킴. 이 프로세스의 PCB를 ready queue로 옮김

 

연산

P(S)

S.value--;
if (S.value < 0) { // 공유 자원 접근 불가 
    add this process to S.L;
    block(); // suspend
}

V(S)

S.value++;
if (S.value <= 0) { // 자원을 내놨는데 기다리는 프로세스가 있음
    remove a process P from S.L;
    wakeup(P); // wakeup
}

프로세스 자체를 blocked 시켜서 해당 프로세스가 CPU를 아예 반납하고 잠들어 있다가 공유데이터를 가지고 있던 프로세스가 CPU를 내놓으면 그 때 ready queue에 들어가서 CPU를 얻는 방식(쓸데없이 CPU를 잡고있으면서 기다리지 않음)입니다.

block & wakeup 방식의 경우, 프로세스를 재우고 깨우는데에 대한 오버헤드가 있으므로 critical section 의 길이가 매우 짧은 경우 busy-wait 가 나을 수도 있지만 일반적으로는 block & wakeup 이 더 효율적(CPU 이용률 측면에서)입니다.

세마포어의 문제점: Deadlock & Starvation

만약 프로세스가 S, Q자원 모두 사용해야한다면,

두 개의 프로세스가 서로에 의해 영원히 S, Q 자원 두 개 모두를 한꺼번에 획득할 수 없는 문제가 생기게 됩니다. (Deadlock)

프로세스가 하나의 자원을 선점한 채로 다른 자원을 얻기 위해 기다리게 되는데, 하나씩 선점한 상태라면 획득할 수 없는 자원을 무한히 기다리게 되는 것입니다. (Starvation)

 

• Deadlock: 둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 현상
• Starvation: 프로세스가 suspend된 이유에 해당하는 세마포어 큐에서 빠져나갈 수 없는 현상. 일부 프로세스의 공유 자원을 독점으로 어떤 프로세스는 영원히 자원을 얻지 못해서 실행되지 못함. (indefinite blocking)
• Deadlock도 Starvation의 일종으로 볼 수 있음