📢 본 글은 혼공학습단 미션과 함께 정리해보는 글 입니다.

동기화란

동시다발적으로 실행되는 프로세스들은 공동의 목적을 위해 서로 협력하며 영향을 주고받는다. 이 과정에서 자원의 일관성을 보장해야 한다.

동기화의 의미

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

프로세스 뿐 아니라 스레드도 동기화 대상이긴 하지만 (실행의 흐름을 갖는 모든 것은 동기화의 대상이다.) 이 책에서는 대부분의 전공서 표현에 따라 동기화를 프로세스의 동기화라고 설정한다.

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

실행 순서 제어

프로세스를 올바른 순서대로 실행하기 위한 것을 뜻한다.

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

상호 배제

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

Bank account problem

현재 계좌에 10만원이 있고, 프로세스 A와 프로세스 B가 다음과 같이 실행된다고 가정한다.

프로세스 A

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

프로세스 B

1️⃣ 계좌의 잔액을 읽어들인다.
2️⃣ 읽어들인 잔액에 5만원을 더한다.
3️⃣ 더한 값을 저장한다.
프로세스 A와 프로세스 B를 동시에 실행하면 17만원이 될까? → X

프로세스 A의 더한 값 저장이 일어나기 전 프로세스 B가 실행될 경우, A와 B에서 읽어들인 값이 달라지기 때문에 합산되지 않는다.
이는 동시에 접근해서는 안 되는 자원 (잔액)에 동시에 접근했기 때문이다.

생산자-소비자 문제

생산자-소비자 문제 (producer-consumer problem) 또한 상호 배제를 위한 동기화에 대한 고전적인 문제이다.

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

생산자

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

소비자

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

이때 총합 변수가 10이고, 생산자와 소비자를 각각 10,000번 실행한다면 우리가 예상하기로는 10일 것이다.

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

공유 자원과 임계 구역

공유 자원 (shared resource)이란 여러 프로세스가 공유하는 자원을 뜻한다. 전역 변수, 파일, 입출력, 보조기억장치 등이 해당된다.

임계 구역 (critical section)이란 동시에 실행하면 문제가 발생하는 자원에 접근하는 코드 영역을 뜻한다. 따라서 하나의 프로세스가 이미 임계 구역에 진입했다면, 나머지 프로세스는 그 프로세스가 임계 구역에서 나올 때 까지 대기해야 한다.

race condition

임계 구역에 동시에 접근하면 자원의 일관성이 깨질 수 있는데, 이러한 현상을 레이스 컨디션 (race condition)이라고 한다. 위의 bank-account 예시에서는 값을 최종적으로 저장하기 전에 문맥 교환이 발생했기 때문에 값이 충돌되는 것이다.

임계 구역 해결 방법 (상호 배제를 위한 동기화를 할 때 필요한 원칙)

임계 구역 동시 접근에 따른 문제 (race condition)를 해결하기 위해서는 아래와 같은 원칙들이 보장되어야 한다.

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

---

동기화 기법

동기화 적용 방법으로는 다음과 같은 방법들이 있다.

뮤텍스 락 (Mutex lock)

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

acquire() {
    while (lock == true) /* 만약 임계 구역이 잠겨 있다면 */
        ;                /* 임계 구역이 잠겨 있는지를 반복적으로 확인 */
        lock = true;     /* 만약 임계 구역이 잠겨 있지 않다면 임계 구역 잠금 */
}

release() {
    lock = false;        /* 임계 구역 작업이 끝났으니 잠금 해제 */
}

acquire

• 프로세스가 임계 구역에 진입하기 전 호출
• 임계 구역이 잠겨 있다면 → 임계 구역이 열릴 때 까지 (lock이 false로 될 때 까지) 임계 구역을 반복적으로 확인한다. → busy wait
• 임계 구역이 열려 있다면 → 임계 구역을 잠근다. (lock을 true로 바꾼다.)

release

• 임계 구역에서의 작업이 끝나고 호출된다.
• 현재 잠긴 임계 구역을 연다. (lock을 false로 바꾼다.)

즉, 임계 구역 전후로 구분하면 다음과 같이 된다.

acquire(); // 자물쇠 잠겨 있는지 확인, 잠겨 있지 않다면 잠그고 들어가기
// 임계 구역 // 임계 구역에서의 작업 진행 (생산자-소비자 문제에서는 '총합' 변수에 접근하는 것이 해당된다.)
release(); // 자물쇠 반환

정리

정리하자면

• 락을 획득할 수 없다면 (임계 구역에 진입할 수 없다면) 무작정 기다리고
• 락을 획득할 수 있다면 (임계 구역에 진입할 수 있다면) 임계 구역을 잠근 뒤 임계 구역에서의 작업을 진행하고
• 임계 구역에서 빠져나올 때엔 다시 임계 구역의 잠금을 해제함으로써 임계 구역을 보호할 수 있다.

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

세마포 (Semaphore)

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

세마포의 종류 (이진 세마포, 카운팅 세마포) 중 카운팅 세마포를 다룬다. 이진 세마포는 뮤텍스 락과 비슷하다. 또한, 뮤텍스 락과 동일하게 세마포도 많은 프로그래밍 언어에서 제공한다.

상호 배제를 위한 동기화

세마포는 철도 신호기에서 유래한 단어이다.

• 기차는 신호기가 내려가 있을 때는 '멈춤' 신호로 간주하고 잠시 멈춘다.
• 신호기가 올라와 있을 때는 '가도 좋다'는 신호로 간주하고 다시 움직인다.
• 세마포는 이와 같이 '멈춤' 신호와 '가도 좋다'는 신호로서 임계 구역을 관리한다.

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

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

코드

뮤텍스 락의 경우와 비슷하게 다음과 같이 실행된다.

wait() {
    while (S <= 0) /* 만일 임계 구역에 진입할 수 있는 프로세스 개수가 0 이하라면 */
        ;          /* 사용할 수 있는 자원이 있는지 반복적으로 확인한다. */
    S--;           /* 임계 구역에 진입할 수 있는 프로세스 개수가 하나 이상이면 S를 1 감소시키고 임계 구역에 진입한다. */
}

signal() {
    S++;           /* 임계 구역에서의 작업을 마친 뒤 S를 1 증가시킨다. */
}

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를 확인해야 한다. 이는 CPU 사이클을 낭비하게 되는 문제를 유발한다. 이것을 해결하기 위해 세마포는 더 효율적인 방법을 사용한다.

wait() {
    S--;
    if (S < 0) {
        add this process to Queue; /* 해당 프로세스 PCB를 대기 큐에 삽입한다. */
        sleep();                   /* 대기 상태로 접어든다. */
    }
}

signal() {
    S++;
    if (S <= 0) {
        remove a process p from Queue /* 대기 큐에 있는 프로세스 p를 제거한다. */
        wakeup(p)                     /* 프로세스 p를 대기 상태에서 준비 상태로 만든다. */
    }
}

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

1️⃣ 프로세스 P1이 wait를 호출한다. S는 현재 2이므로 S를 1 감소시키고 임계 구역에 진입한다.
2️⃣ 프로세스 P2가 wait를 호출한다. S를 1 감소시키면 S는 0이므로 임계 구역에 진입한다.
3️⃣ 프로세스 P3이 wait를 호출한다. S를 1 감소시키면 S는 -1이므로 본인의 PCB를 대기 큐에 넣고 대기 상태로 전환한다.
4️⃣ 프로세스 P1이 임계 구역 작업을 종료하고 signal 함수를 호출하여 S를 1 증가시킨다. S가 0이 되었으므로 대기 상태에 있던 P3를 대기 큐에서 꺼내 준비 큐로 옮겨준다.
5️⃣ 깨어난 프로세스 P3이 임계 구역에 진입한다.
6️⃣ 프로세스 P2가 임계 구역 작업을 종료하여 signal 함수를 호출하고, S를 1 증가하여 1로 만든다.
7️⃣ 프로세스 P3이 임계 구역 작업을 종료하여 signal 함수를 호출하고, S를 1 증가하여 2로 만든다.

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

세마포는 실행 순서 제어를 위한 동기화로도 사용할 수 있다.

• 세마포의 변수 S를 0으로 두고
• 먼저 실행할 프로세스 뒤에 signal 함수를 붙이고 (사용한 뒤 S를 증가시키므로)
• 다음에 실행할 프로세스 앞에 wait 함수를 붙이면 된다. (사용할 수 있을 때 까지 대기하므로)
• P1이 먼저 실행되면 P1이 임계 구역에 먼저 진입하고, P2가 먼저 실행되더라도 P2는 wait 함수를 만나야 하므로 P1이 임계 구역에 진입한다. P1이 임계 구역의 실행을 끝내고 signal을 호출하면, 그 때 P2가 임계 구역에 진입한다. 즉, P1이 먼저 실행되든 P2가 먼저 실행되든 반드시 P1 후 P2가 실행된다.

모니터 (Monitor)

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

위의 경우처럼 잘못된 코드로 인해 예기치 못한 결과를 얻을 수 있기도 하다.

상호 배제를 위한 동기화

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

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

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

• 각각의 조건 변수에 대한 큐가 있다.

• 상호 배제를 위한 큐와 조건 변수에 대한 큐는 서로 다른 큐이다.

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

• 특정 조건을 바탕으로 프로세스를 실행하고 일시 중단하기 위해 조건 변수 (condition variable)를 사용한다. 이때 조건 변수는 프로세스나 스레드의 실행 순서를 제어하기 위해 사용하는 특별한 변수이다.

  • 조건변수.wait(): 특정 프로세스, 스레드를 대기 상태로 변경하는 연산이다.
    

  • 조건변수.signal(): wait()으로 대기 상태로 접어든 조건 변수를 실행 상태로 변경하는 연산이다.
    

  • 모니터 안에는 하나의 프로세스만이 있을 수 있다!

  • wait()를 호출했던 프로세스는 signal()을 호출한 프로세스가 모니터를 떠난 뒤에 수행을 재개하는 방식 (signal and continue)과 signal()을 호출한 프로세스의 실행을 일시 중단하고 자신이 실행된 뒤 다시 signal()을 호출한 프로세스의 수행을 재개하는 방식 (signal and wait)이 있다.

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

---

미션

• 임계 구역, 상호 배제 개념 정리하기
  • 임계 구역: 동시에 실행하면 문제가 발생하는 자원에 접근하는 코드 영역이다. 하나의 프로세스 (or 스레드)가 이미 임계 구역에 진입했다면, 나머지 프로세스 (or 스레드)는 그 프로세스 (or 스레드)가 임계 구역에서 나올 때 까지 대기해야 한다.
  • 상호 배제: 공유가 불가능한 자원의 동시 사용을 피하기 위해 사용하는 개념이다.

---

부족하거나 보완할 점이 있다면 댓글 부탁드립니다 😃