본 글은 책 "혼자 공부하는 컴퓨터 구조+운영체제" 의 Chapter 12. 프로세스 동기화 부분을 읽고 정리한 내용입니다.

동기화의 의미

• 동시다발적으로 실행되는 많은 프로세스는 서로 데이터를 주고 받으며 협력하며 실행될 수 있고 이 때 데이터의 일관성을 유지해야 함
• 프로세스 동기화란 프로세스 사이의 수행 시기를 맞추는 것을 의미하고 아래 2가지를 위헌 동기화가 있음
  • 실행 순서 제어: 프로세스를 올바른 순서대로 실행하기
  • 상호 배제: 동시에 접근해서는 안되는 자원에 하나의 프로세스만 접근하게 하기

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

• book.txt 파일에 2가지 프로세스가 동시에 실행중이라고 가정해보자
  • Writer process
  • Reader process
• 둘은 무작정 아무 순서대로 실행되어서는 안되고 Writer 실행이 끝난 후 Reader가 실행되어야 함

상호 배제를 위한 동기화

• 공유가 불가능한 자원의 동시 사용을 피하기 위해 사용하는 알고리즘

예시 (Bank account problem)

• 계좌에 10만원이 저축되어 있다고 가정
• 프로세스 A는 2만원 입금
• 프로세스 B는 5만원 입금

프로세스 A 실행되는 과정

1. 계좌의 잔액 읽음
2. 읽어들인 잔액에 2만원 더함
3. 더한 값 저장

프로세스 B 실행되는 과정

1. 계좌의 잔액 읽음
2. 읽어들인 잔액에 5만원 더함
3. 더한 값 저장

이때 두 프로세스가 동시에 실행되었다고 가정했을 때 동기화가 제대로 이루어지지 않은 경우 아래와 같이 전혀 엉뚱한 결과가 나올 수 있음

정상적으로 작동하길 기대되는 예시

생산자와 소비자 문제

• 생산자와 소비자는 ‘총합’이라는 데이터를 공유
• 생산자는 총합에 1을 더하고, 소비자는 총합에 1을 뺌

• 생산자와 소비자를 동시에 실행했을 때 예상되는건 총합의 값은 초기 상태를 유지하는 것
• 하지만 직접 코드를 돌려보면 예상치 못한 결과 발생

#include <iostream>
#include <queue>
#include <thread>

void produce();
void consume();

int sum = 0;

int main() {

    std::cout << "초기 합계: " <<  sum << std::endl;
    std::thread producer(produce);
    std::thread consumer(consume);

    producer.join();
    consumer.join();
    
    std::cout << "producer, consumer 스레드 실행 이후 합계: " <<  sum << std::endl;
    
    return 0;
}

void produce() {
    for(int i = 0; i < 100000; i++) {
        sum++;
    }
}

void consume() {
    for(int i = 0; i < 100000; i++) {
        sum--;
    }
}

초기 합계 : 10
producer, consumer 스레드 실행 이후 합계: -13750

• 이는 생산자 프로세스와 소비자 프로세스가 제대로 동기화되지 않았기 때문
  • ‘총합’ 데이터를 동시에 사용하는데 소비자가 생산자의 작업이 끝나기 전에 총합을 수정했고, 생산자가 소비자의 작업이 끝나기 전에 총합을 수정했기 때문

공유 자원과 임계 구역

• shared resource: 여러 프로세스 혹은 쓰레드가 공유하는 자원
  • 전역 변수, 파일, 입출력 장치, 보조기억장치
• 임계구역: 동시에 실행하면 문제가 발생하는 자원에 접근하는 코드 영역
• 두 개 이상의 프로세스가 임계 구역에 진입하고자 하면 둘 중 하나는 대기해야 함

Race condition

• 임계 구역은 두 개 이상의 프로세스가 동시에 실행되면 안되는 영역이지만 여러 프로세스가 동시에 다발적으로 실행하여 자원의 일관성이 깨지는 경우

Race condition의 근본적인 이유

• 고급언어(C/C++, Python) → 저급언어로 변환되며 코드가 늘어날 수 있음
• 이 때 context switching이 발생하면 예상치 못한 결과를 얻을 수 있음

상호 배제를 위한 동기화는 이런 일이 발생하지 않도록 두 개 이상의 프로세스가 임계 구역에 동시에 접근하지 못하도록 관리하는 것을 의미하며 운영체제는 3가지 원칙하에 해결

1. progress: 임계 구역에 어떤 프로세스도 진입하지 않았다면 임계 구역에 진입하고자 하는 프로세스는 들어갈 수 있어야 함
2. Mutual exclusion : 한 프로세스가 임계 구역에 진입했다면 다른 프로세스는 임게 구역에 들어올 수 없음
3. bounded waiting: 한 프로세스가 임계 구역에 진입하고 싶다면 그 프로세스는 언젠가는 임게 구역에 들어올 수 있어야 함 (무한정 대기 X)

동기화 기법

동기화를 위한 대표적인 도구 3가지

1. 뮤텍스 락
2. 세마포
3. 모니터

뮤텍스 락(Mutex lock)

• Mutual EXclusion lock, 상호 배제를 위한 동기화 도구로 기능을 코드로 구현한 것
• 매우 단순한 형태는 하나의 전역 변수와 두개의 함수
  • 자물쇠 역할: 프로세스들이 공유하는 전역 변수 lock
  • 임계구역을 잠그는 역할: acquire 함수
  • 임계 구역의 잠금을 해제하는 역할: release 함수

acquire 함수

• 프로세스가 임계 구역에 진입하기 전에 호출하는 함수
• 임계 구역이 잠겨있으면 열릴 때까지(lock이 false가 될 때까지) 임계 구역을 반복적으로 확인
• 임계 구역이 열려있으면 임계 구역을 잠그는 함수

release 함수

• 임계 구역에서의 작업이 끝나고 호출하는 함수

acquire(){
    while (lock ==true) # 반복해서 확인하는 대기 방식을 busy wait이라고 함
        ;               # 임계 구역이 잠겨 있는지 반복적으로 확인
    lock = true;        # 만약 임계 구역이 잠겨 있지 않다면 임계 구역 잠금
}

release() {
    lock = false; # 임계 구역 작업이 끝나서 잠금 해제
}

acquire();
// 임계구역 (ex) '총합' 변수 접근)
release();

세마포(Semaphore)

• 사전적 의미: 수기 신호

• 뮤텍스 락과 비슷하지만 좀 더 일반화된 방식의 동기화 도구
• 공유 자원이 여러개 있는 상황에서도 적용이 가능한 동기화 도구

• 단순한 형태로 하나의 변수와 두개의 함수로 구현가능
  • 임계 구역에 진입할 수 있는 프로세스의 개수를 나타내는 전역 변수 S
  • 임계 구역에 들어가도 좋은지 기다려야 할지를 아려주는 wait 함수
  • 이제 가도 좋다는 신호를 주는 signal 함수

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

signal()
{
    S++;           # 임계 구역에서의 작업을 마친 뒤 S를 1 증가 시킴
}

wait()
// 임계 구역
signal()

예시

세 개의 프로세스 P1, P2, P3가 2개의 공유 자원(S=2)에 순서대로 접근한다고 가정하면,

1. 프로세스 P1 wait 호출, S는 2→1로 감소
2. 프로세스 P2 wait 호출, S는 1→0으로 감소
3. 프로세스 P3 wait 호출, S는 현재 0이므로 무한히 반복하며 S확인
4. 프로세스 P1 임계 구역 작업 종료, signal 호출, S는 0→1
5. 프로세스 P3에서 S가 1이 됨을 확인하고 S 1→0 만들고 임계 구역 진입

위의 3 과정에서 busy wait 반복하며 확인하며 CPU 사이클이 낭비됨
* busy wait: 쉴새없이 반복하며 확인해보며 기다리는 과정

해결 방법

1. 사용할 수 있는 자원이 없을 경우 대기 상태로 만듦 (해당 프로세스의 PCB를 waiting queue에 삽입)
2. 사용할 수 있는 자원이 생겼을 경우 대기 큐의 프로세스를 준비 상태로 만듦 (해당 프로세스의 PCB를 waiting queue → ready queue 로 이동)

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

signal()
{
    S++;
    if (S<=0) 
    # remove a process p from waiting Queue;
    wakeup(p); # waiting queue -> ready queue
  }
}

프로세스 4개이고, 공유 자원이 2개라고 가정해보면,

1. 프로세스 P1 wait 호출, S는 2→1로 감소
2. 프로세스 P2 wait 호출, S는 1→0으로 감소
3. 프로세스 P3 wait 호출, S는 0→-1이 되고 waiting queue로 이동
4. 프로세스 P4 wait 호출, S는 -1→-2가 되고 waiting queue로 이동
5. 프로세스 P1 임계 구역 작업 종료, signal 호출, S는 -2→-1이 되고 PCB를 waiting queue → ready queue로 이동
6. 프로세스 P2 임계 구역 작업 종료, signal 호출, S는 -1→0이 되고, PCB를 waiting queue → ready queue로 이동

세마포는 프로세스의 실행순서 동기화도 지원

• 변수 S를 0으로 두고 먼저 실행할 프로세스 뒤에 signal 함수, 다음에 실행할 프로세스 앞에 wait함수를 붙이면 됨

• 위의 경우 프로세스의 실행 순서에 상곤없이 P1→P2 순으로 임계 구역에 진입

모니터(Monitor)

• 세마포는 훌륭한 프로세스 동기화 도구지만 매번 임계 구역 앞뒤로 wait & signal 함수를 명시해야 함
• 모니터는 사용자(개발자)가 다루기에 편한 동기화 도구

상호 배제를 위한 동기화

• 공유자원과 공유 자원에 접근하기 위한 인터페이스를 묶어서 관리
• 프로세스는 반드시 인터페이스를 통해서만 공유 자원에 접근하도록 함

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

• 내부적으로 조건 변수(condition variable)를 이용
• 프로세스나 스레드의 실행 순서를 제어하기 위해 사용하는 특별한 변수

조건 변수별 queue가 있고 이를 통해 실행 순서를 결정할 수 있음

• 조건 변수로 wait과 signal 연산을 수행할 수 있음
  • 조건변수.wait(): 대기 상태로 변경, 조건 변수에 대한 큐에 삽입

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

모니터 안에는 하나의 프로세스만 있을 수 있음

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

참고

1. 책 "혼자 공부하는 컴퓨터 구조+운영체제"
2. 유튜브 "혼자 공부하는 컴퓨터 구조 + 운영체제"