[JSCODE 운영체제 4주차] 프로세스 동기화

안녕하세요 dev_writer입니다.
 
이번에는 프로세스 동기화에 대해 작성하고자 합니다.
 

동기화란

동시다발적으로 실행되는 프로세스들은 공동의 목적을 위해 서로 협력하며 영향을 주고받습니다.
 
프로세스들은 컴퓨터 자원을 각자 이용하는데, 협력을 위해서는 이 자원에 대한 일관성도 보장받아야 할 것입니다.
 

동기화의 의미

프로세스에서의 동기화는 프로세스들 사이의 수행 시기를 맞추는 것을 뜻합니다. 프로세스들은 동시에 수행될 때 올바른 수행을 위해 동기화되어야 합니다.

컴퓨터 과학에서 동기화(synchronization)는 합의에 도달하거나 특정 작업 순서를 커밋하기 위해 특정 지점에 합류하거나 핸드셰이킹하도록 여러 프로세스를 조정하는 작업이다. - 위키백과, 동기화 (컴퓨터 과학)

<혼자 공부하는 컴퓨터구조+운영체제>에서는 프로세스뿐 아니라 스레드도 동기화 대상 (실행의 흐름을 갖는 모든 것은 동기화의 대상으로 간주)이지만, 대부분의 전공서 표현에 맞추어 프로세스의 동기화라고 설정합니다.

 
프로세스 동기화는 실행 순서 제어를 위한 동기화와, 상호 배제를 위한 동기화로 구분됩니다.
 

실행 순서 제어

간단한 Reader-Writer 예시를 보겠습니다.
 

• 하나의 책 내용을 담은 book.txt 파일이 있습니다.
• Reader는 book.txt 파일에 저장된 값을 읽어 들이는 프로세스입니다.
• Writer는 book.txt 파일에 값을 저장하는 프로세스입니다.
• 이때, Reader 프로세스는 Writer 프로세스의 실행이 끝나야 실행될 수 있어야 합니다. book.txt에 값이 저장되어야 그것을 읽을 수 있기 때문입니다.
• 따라서 Reader 프로세스와 Writer 프로세스의 실행 순서를 제어해야 합니다.

 

상호 배제

상호 배제는 공유가 불가능한 자원의 동시 사용을 피하기 위해 사용하는 것입니다. 동시 사용을 피하는 것이므로, 한 번에 하나의 프로세스만 접근하도록 합니다.
 

Bank-account problem

Bank-account problem을 예로 들어보겠습니다.

현재 계좌에 10만원이 있고, 프로세스 A와 B가 위와 같이 진행된다고 가정합니다.

프로세스 A

1. 계좌의 잔액을 읽어 들입니다.
2. 읽어 들인 잔액에 2만 원을 더합니다.
3. 더한 값을 저장합니다.

프로세스 B

1. 계좌의 잔액을 읽어 들입니다.
2. 읽어 들인 잔액에 5만 원을 더합니다.
3. 더한 값을 저장합니다.

이때, 프로세스 A와 B를 동시에 실행하면 17만 원이 되지 않습니다.
 
프로세스 A의 더한 값을 저장하기 전 프로세스 B가 실행될 경우, A와 B에서 읽어 들인 값이 달라지기 때문에 합산되지 않습니다.
이런 문제를 예방하기 위해서는 동시에 접근해서는 안 되는 자원 (잔액)에는 동시 접근이 되지 않도록 해야 합니다.
 

생산자-소비자 문제

두 번째 예시로 생산자-소비자 문제도 보겠습니다.

• 생산자는 물건을 계속해서 생산하는 프로세스입니다.
• 소비자는 물건을 계속해서 소비하는 프로세스입니다.
• 이 두 프로세스는 총합 변수를 공유합니다.

생산자

생산자() {
    버퍼에 데이터 삽입
    '총합' 변수 1 증가
}

 
소비자

소비자() {
    버퍼에서 데이터 빼내기
    '총합' 변수 1 감소
}

 
이때 총합 변수가 10이고, 생산자와 소비자를 각각 10,000번 실행하면 예상하기로는 10이 나올 것입니다.
 
그러나 실제 코드를 실행해 보면 오류가 발생합니다. 이는 생산자 프로세스와 소비자 프로세스가 제대로 동기화되지 않았기 때문에 발생한 문제입니다. 소비자가 생산자의 작업이 끝나기 전에 총합을 수정했고, 생산자가 소비자의 작업이 끝나기 전에 총합을 수정하는 등의 문제가 발생했습니다.
 

공유 자원과 임계 구역

프로세스 동기화를 공부하다 보면, 공유 자원 (shared resource)과 임계 구역 (critical section)에 대해 들으실 수 있습니다.
 
공유 자원이란, 여러 프로세스가 공유하는 자원을 의미합니다. 위에서의 '잔액', '총합' 등이 해당됩니다.
 
임계 구역이란, 동시에 실행하면 문제가 발생하는 자원 (= 공유 자원)에 접근하는 코드 영역을 뜻합니다.
 
그러므로 하나의 프로세스가 이미 임계 구역에 진입했다면, 나머지 프로세스는 동기화를 위해 먼저 들어간 프로세스가 임계 구역에서 나올 때까지 대기해야 합니다.

한 번에 한 명만 들어갈 수 있는 화장실을 생각하면 이해하기 쉽습니다.

 

Race condition

임계 구역에 여러 프로세스가 동시에 접근하면 자원의 일관성이 깨질 수 있고, 이런 현상을 Race condition이라 합니다. bank-account problem에서는 값을 최종적으로 저장하기 전에 문맥 교환이 발생했기 때문에 값이 충돌하게 됩니다.
 

Race condition 해결 방법 (상호 배제를 위한 동기화를 할 때 필요한 원칙)

Race condition을 해결하기 위해서는 아래 세 가지 원칙이 반드시 보장되어야 합니다.

• 상호 배제 (mutual exclusion): 한 프로세스가 임계 구역에 진입했다면 다른 프로세스는 임계 구역에 들어올 수 없습니다.
• 진행 (progress): 임계 구역에 어떤 프로세스도 진입하지 않았다면, 임계 구역에 진입하고자 하는 프로세스는 들어갈 수 있어야 합니다.
• 유한 대기 (bounded waiting): 한 프로세스가 임계 구역에 진입하고 싶다면, 그 프로세스는 언젠가는 임계 구역에 들어올 수 있어야 합니다. 임계 구역에 들어오기 위해 무한정 대기해서는 안 됩니다.

 

동기화 기법

이제부터는 실행 순서 제어와 상호 배제를 위한 동기화의 실제 적용 방법들을 살펴보겠습니다.

뮤텍스 락 (Mutex lock)

• 상호 배제를 위한 동기화입니다.
• 탈의실에 있는 자물쇠와 같은 역할을 합니다. 밖에서 탈의실에 사람이 있는지 없는지는 자물쇠가 걸려있는지를 통해 확인할 수 있습니다.
• 자물쇠 역할은 프로세스들이 공유하는 전역 변수 lock을 활용합니다.
• 임계 구역을 잠그는 역할은 acquire 함수를 활용합니다.
• 임계 구역의 잠금을 해제하는 역할은 release 함수를 활용합니다.

acquire() {
    while (lock)
        ; / * busy wait */
    lock = true;
}

release() {
    lock = false;
}

 
acquire

• 프로세스가 임계 구역에 진입하기 전 호출합니다.
• 임계 구역이 잠겨 있다면 임계 구역이 열릴 때까지 임계 구역을 반복적으로 확인합니다. (busy wait)
• 임계 구역이 열려 있다면 임계 구역을 잠급니다.

release

• 임계 구역에서의 작업이 끝나고 호출됩니다.
• 현재 잠긴 임계 구역을 엽니다.

즉 임계 구역을 전후로 구분하면 다음과 같이 진행됩니다.

acquire(); // 자물쇠 잠겨 있는지 확인, 잠겨 있지 않다면 잠그고 들어감
/* 임계 구역 작업 진행 */
release(); // 자물쇠 반환

 
정리하자면

1. 락을 획득할 수 없다면 계속 대기
2. 락을 획득할 수 있다면 임계 구역을 잠근 뒤 임계 구역에서의 작업을 진행
3. 임계 구역에서 빠져나올 때에는 다시 임계 구역의 잠금을 해제

함으로써 임계 구역을 보호할 수 있습니다.

C/C++, Python 등의 일부 프로그래밍 언어에서는 사용자가 직접 acquire, release 함수를 구현하지 않도록 뮤텍스 락 기능을 제공합니다. 실제 프로그래밍 언어가 제공하는 뮤텍스 락은 앞서 소개한 구현보다 더 정교하게 설계되어 있습니다.

 

세마포어 (Semaphore)

세마포어는 뮤텍스 락 보다 좀 더 일반화된 방식의 동기화 도구이며, 공유 자원이 여러 개 있는 경우에도 적용할 수 있습니다.

<혼자 공부하는 컴퓨터구조+운영체제>에서는 세마포어의 종류 (이진 세마포어, 카운팅 세마포어) 중 카운팅 세마포어를 다룹니다. 이진 세마포어는 뮤텍스 락과 비슷하기 때문입니다. 또한, 뮤텍스 락과 동일하게 세마포어도 많은 프로그래밍 언어에서 제공하고 있습니다.

 
세마포어는 실행 순서 제어를 위한 동기화와 상호 배제를 위한 동기화 두 가지에 모두 적용할 수 있습니다.
 

상호 배제를 위한 동기화

세마포어는 하나의 변수와 두 개의 함수로 단순하게 구현할 수 있습니다.

• 임계 구역에 진입할 수 있는 프로세스의 개수를 나타내는 전역 변수 S
• 임계 구역에 들어가도 좋은지, 기다려야 할지를 알려주는 wait 함수
• 임계 구역 앞에서 기다리는 프로세스에 '이제 가도 좋다'라고 신호를 주는 signal 함수

wait() {
    while (S <= 0)
        /* busy wait */
    S--;
}

signal() {
    S++;
}

wait();
/* 임계 구역 작업 진행 */
signal();

 
예시를 보겠습니다.

세 개의 프로세스 P1, P2, P3이 두 개의 공유 자원 (S = 2)에 P1, P2, P3 순서로 접근한다고 가정합니다.

1. 프로세스 P1이 wait를 호출합니다. S는 현재 2이므로 S를 1 감소시키고 임계 구역에 진입합니다.
2. 프로세스 P2가 wait를 호출합니다. S는 현재 1이므로 S를 1 감소시키고 임계 구역에 진입합니다.
3. 프로세스 P3이 wait를 호출합니다. S는 현재 0이므로 무한히 반복하며 S를 확인합니다.
4. 프로세스 P1이 임계 구역 작업을 종료하고 signal 함수를 호출하여 S를 1 증가시킵니다.
5. 프로세스 P3이 S가 1이 되었음을 확인합니다. S는 현재 1이므로 S를 1 감소시키고 임계 구역에 진입합니다.

현재 위 예시는 심각한 문제가 있는데, 그것은 바로 뮤텍스와 같이 사용할 수 있는 공유 자원이 없는 경우 프로세스는 무작정 무한히 반복하며 S를 사용할 수 있는지 확인한다는 점입니다. 이것을 해결하기 위해 세마포어는 더 효율적인 방법을 사용합니다.
 

wait() {
    S--;
    if (S < 0) {
        add this process to Queue;
        sleep();
    }
}

signal() {
    S++;
    if (S <= 0) {
        remove a process p from Queue;
        wakeup(p);
    }
}

 
wait 함수는 만일 사용할 수 있는 자원이 없을 경우 해당 프로세스 상태를 대기 상태로 만들고, 그 프로세스의 PCB를 세마포어를 위한 대기 큐에 집어넣습니다. 그리고 다른 프로세스의 임계 구역 작업이 끝나고 signal 함수를 호출하면, signal 함수는 대기 중인 프로세스를 대기 큐에서 제거하고, 프로세스 상태를 준비 상태로 변경한 뒤 준비 큐로 옮겨줍니다.
 

실행 순서 제어를 위한 동기화

이번에는 실행 순서 제어를 위한 동기화에서 적용된 예를 보겠습니다.

실행 순서 제어 예

1. 세마포어의 변수 S를 0으로 두고
2. 먼저 실행할 프로세스 뒤에 signal 함수를 붙이고
3. 다음에 실행할 프로세스 앞에 wait 함수를 붙입니다.

P1 프로세스가 먼저 실행되면 P1이 임계 구역에 먼저 진입하고, P2 프로세스가 먼저 실행되더라도 P2는 wait 함수를 만나야 하므로 P1이 임계 구역에 진입합니다. P1이 임계 구역의 실행을 끝내고 signal을 호출하면, 그때 P2가 임계 구역에 진입합니다.
 
즉, P1이 먼저 실행되든 P2가 먼저 실행되든 반드시 P1 후 P2가 실행됩니다.
 

모니터

세마포어는 좋은 프로세스 동기화 도구이지만, 매번 임계 구역 앞뒤로 wait와 signal 함수를 명시하는 것은 번거로운 과정입니다.

wait와 signal 함수 호출을 잘못한 케이스

 
위의 경우처럼 잘못된 코드로 인해 예기치 못한 결과를 얻을 수도 있습니다.
 
이에 모니터 기법이 최근에 등장하였으며, 세마포어에 비하면 개발자가 사용하기에 훨씬 편리하다고 할 수 있습니다.
 

상호 배제를 위한 동기화

이미지 출처: 혼자 공부하는 컴퓨터구조+운영체제

모니터는 공유 자원과 공유 자원에 접근하기 위한 인터페이스를 묶어 관리하며, 프로세스는 반드시 인터페이스를 통해서만 공유 자원에 접근하도록 합니다.

• 인터페이스를 위한 큐가 있습니다.
• 공유 자원에 접근하고자 하는 프로세스를 (인터페이스를 위한) 큐에 삽입합니다.
• 큐에 삽입된 순서대로 (한 번에 하나의 프로세스만) 공유 자원을 이용합니다.

 

실행 순서 제어를 위한 동기화

이미지 출처: 혼자 공부하는 컴퓨터구조+운영체제

 
실행 순서 제어를 위해서는 조건 변수를 이용합니다. 조건 변수란, 프로세스나 스레드의 실행 순서를 제어하기 위해 사용하는 특별한 변수입니다.
 

• 상호 배제를 위한 큐는 모니터에 한 번에 하나의 프로세스만 진입하도록 하기 위해 만든 큐입니다.
• 조건 변수에 대한 큐는 모니터에 이미 진입한 프로세스의 실행 조건이 만족될 때까지 잠시 실행이 중단되어 기다리기 위해 만들어진 큐입니다.

이미지 출처: 혼자 공부하는 컴퓨터구조+운영체제

• 조건변수. wait()을 통해 특정 프로세스를 대기 상태로 변경합니다.

이미지 출처: 혼자 공부하는 컴퓨터구조+운영체제

• 조건변수.signal()을 통해 대기 상태로 접어든 조건 변수를 실행 상태로 변경합니다.
• 모니터 안에는 하나의 프로세스만이 있을 수 있습니다.
• wait()를 호출했던 프로세스는 signal()을 호출한 프로세스가 모니터를 떠난 뒤에 수행을 재개하는 방식 (signal and continue) signal()을 호출한 프로세스의 실행을 일시 중단하고 자신이 실행된 뒤 다시 signal()을 호출한 프로세스의 수행을 재개하는 방식 (signal and wait)이 있습니다.

정리하자면 특정 프로세스가 아직 실행될 조건이 되지 않았을 때는 wait()을 통해 실행을 중단하고, 특정 프로세스가 실행될 조건이 충족되었을 때는 signal()을 통해 실행을 재개합니다.