메모리 안에 있는 프로세스들은 대개 독립적이지 않고 협조하는 관계다. 서로에게 영향을 미치고, 영향을 받는데 이는 공통된 자원을 서로 접근하기 때문이다. 메인 메모리에 여러 프로세스가 동시에 존재하기 때문에, 프로세스 간 동기화 문제는 점점 더 중요해지고 있다.

1. 동기화 도구

1.1. 세마포어(Semaphore)

n. (철도의) 까치발 신호기, 시그널; U (군대의) 수기 신호
OS에서의 세마포어란, 동기화 문제를 해결하기 위한 소프트웨어 툴로, 역사가 굉장히 오래되었다.

세마포어는 정수형 변수와 두 개의 동작(P, V)으로 구성되어 있다.
P는 Proberen(test), 정수 값을 테스트한다는 의미이고 acquire()로 사용한다.
V는 Verhogen(increment), 정수 값을 증가시킨다는 의미이고 release()로 사용한다.

class Semaphore {
    int value; // number of permits
    
    Semaphore(int value) {
        ...
    }
    
    void acquire() {
        value--;
        if (value < 0) {
            add this process/thread to list;
            block;
    }
    
    void release() {
        value++;
        if (value <= 0) {
            remove a process P from list;
            wakeup P;
    }
}

Stack에 push, pop 동작이 있듯, 세마포어에는 acquire, release 동작이 있다.

acquire는 정수 값을 1만큼 감소시키고, 이 값이 0보다 작으면 이 acquire를 호출한 프로세스(혹은 스레드)를 세마포어의 큐에 집어 넣는다. 이 프로세스는 누가 꺼내주기 전까지 block 상태이다.

release는 정수 값을 1만큼 증가시키고, 이 값이 0보다 작거나 크면 세마포어 큐 안에 어떤 프로세스가 갇혀 있는 것을 의미한다. 따라서 해당 프로세스를 wakeup하여 세마포어 큐에서 해방시킨다.

세마포어의 일반적 사용에 대한 예시를 보며 이해해 보자.

1.1.1. Mutual exclusion

한 프로세스가 임계구역으로 들어가면 다른 프로세스는 들어가지 못한다.

세마포어의 초기값이 1이라고 해보자. 이 세마포어에 대해 acquire를 호출하면 value는 0이 되고, 해당 프로세스는 임계구역으로 진입한다.

이후 컨텍스트 스위치가 일어나 다른 프로세스가 acquire를 호출했다고 해보자. value는 0보다 작기 때문에 이 프로세스는 세마포어의 큐에 갇힌다. 즉, 임계구역으로 진입하지 못한다.

// Parent

sem.acquire();
/////////////////////////
int temp = balance + n;
System.out.print("+");
balance = temp;
/////////////////////////
sem.release();

// Child

sem.acquire();
/////////////////////////
int temp = balance - n;
System.out.print("-");
balance = temp;
/////////////////////////
sem.release();

여러 자원이 동시에 사용 가능한 경우는 어떨까?

세마포어 값은 1 이상이 될 수 있으며, 이때는 여러 프로세스가 동시에 자원에 접근할 수 있다. 이런 상황에서는 자원 간 경합이나 데이터 불일치 문제가 발생할 수 있기 때문에, Strict Mutual Exclusion(엄격한 상호 배제)이 요구되는 경우에는 세마포어만으로는 해결이 어렵다.

1.1.2. Ordering

세마포어의 초기값이 0이라고 해보자.

$P_1$	$P_2$
	sem.acquire()
$S_1$;	$S_2$;
sem.release();

$P_1→P_2$의 순서로 프로세스를 실행시키고 싶다. $P_1$부터 실행시키면 우리가 원하는 대로 될 것이고, 공교롭게도 CPU가 $P_2$를 먼저 돌린다고 하더라도 acquire을 호출하여 $P_2$는 세마포어 큐에 갇히게 된다. 그렇게 되면 $S_2$로 넘어가지 못하고 컨텍스트 스위치가 일어나 $P_1$이 실행된다. 이후 $P_1$이 release를 호출해 value를 증가시키고 $P_2$가 깨어나게 된다.

$P_1$	$P_2$
	sem.acquire()
$S_1$;	$S_2$;
wsem.release();	dsem.release();
dsem.acquire();

세마포어를 따로 두고 하나가 풀리면 하나를 가두는 것을 반복하면 두 프로세스를 교대로 실행할 수 있다.

1.1.3. 특징

이처럼 세마포어는 여러 프로세스가 동시에 자원에 접근하는 것을 제어하기 위해 사용된다. 예를 들어, 동시에 n개의 자원을 사용할 수 있는 환경에서는 세마포어가 유용하다. 또한 세마포어는 프로세스의 실행 순서를 제어하거나, 교대 작업을 수행할 때 유용하게 사용된다.

하지만 세마포어는 여러 자원을 관리할 수 있다는 점에서 유연했지만, 앞서 언급했듯 Strict Mutual Exclusion을 완벽히 보장하지는 못하는 한계가 있었다. 즉, 특정 자원에 오직 하나의 프로세스만 접근해야 할 경우를 안전하게 처리하기에는 부족했다. 이로 인해 더 엄격한 동기화가 필요하다는 요구가 생겨났고, 그 결과 뮤텍스가 등장하게 된다.

1.2. 뮤텍스(Mutex)

뮤텍스는 이진 잠금 장치로, 단 하나의 프로세스 또는 스레드만이 임계구역에 접근할 수 있도록 보장한다. 이 방식은 자원에 대해 엄격한 배타적 접근을 요구하는 경우에 적합하다.

1.2.1. 동작 과정

• Lock: 임계구역에 들어가기 전에 잠금을 설정하여 다른 프로세스가 접근하지 못하도록 한다.
• Unlock: 임계구역을 벗어나면 잠금을 해제하여 다른 프로세스가 자원에 접근할 수 있도록 한다.

class Mutex {
    boolean isLocked = false;
    
    void lock() {
        while (isLocked) {
            wait;  // 잠겨 있으면 대기
        }
        isLocked = true;  // 잠금 설정
    }
    
    void unlock() {
        isLocked = false;  // 잠금 해제
        notify();  // 기다리는 스레드를 깨움
    }
}

뮤텍스는 자원을 소유한 프로세스만이 unlock()을 호출할 수 있다는 점에서, 세마포어와 구분된다. 세마포어는 누가 release()를 호출해도 세마포어 값을 증가시킬 수 있지만, 뮤텍스는 자원을 점유한 프로세스만이 잠금을 해제할 수 있는 소유권 개념이 있다.

1.2.2. 특징

뮤텍스는 CPU 자원을 절약할 수 있는 장점이 있다. 자원이 사용 중일 때 스레드가 뮤텍스 큐에 들어가 대기 상태로 전환되기 때문에, CPU 사이클을 소모하지 않는다. 이는 특히 멀티 코어 시스템에서 스레드가 자주 대기해야 하는 상황에서 유리하다.

반면 스레드를 대기 상태로 전환하고 다시 실행 상태로 전환할 때, 컨텍스트 스위치가 발생하며 이 과정에서 성능 오버헤드가 발생할 수 있다는 단점이 있다.

❓ 뮤텍스 큐에서 임계구역이 해제되면, 순서가 된 프로세스가 CPU 점유권을 즉시 갖게 될까?

일반적으로 뮤텍스 큐에서 임계구역이 해제되면 그 큐에서 대기 중이던 프로세스 또는 스레드는 즉시 실행 상태(ready state)로 전환된다. 하지만 실행 상태로 전환된다고 해서 바로 CPU 점유권을 강제로 가져가지는 않는다. CPU를 실제로 점유하기 되는지 여부는 스케줄러에 의해 결정된다.

선점형 스케줄링의 경우 프로세스가 높은 우선순위를 갖고 있다면, 현재 CPU에서 실행 중인 스레드를 선점하고 CPU를 획득한다. 비선점형 스케줄링의 경우 임계구역이 해제되어도 즉시 CPU를 획득하지 못하고, 현재 CPU를 점유하고 있는 프로세스의 작업이 끝날 때까지 대기하게 된다.

만약 매번 뮤텍스 해제로 인해 강제로 CPU가 선점된다면, 컨텍스트 스위칭이 너무 자주 발생하여 성능 문제가 생길 수 있다. 이를 방지하기 위해 운영체제는 우선순위 기반 스케줄링, 타임 슬라이스 제어 등 다양한 기법을 사용해 효율적인 CPU 점유를 보장한다.

⇒ 정리하자면, 뮤텍스 해제 시 순서가 된 프로세스가 반드시 CPU를 강제로 점유하지는 않으며, 스케줄러가 적절한 시점에 프로세스를 실행하게 된다. 이로써 불필요한 컨텍스트 스위칭을 줄이면서도 효율적인 자원 할당이 이루어진다.

1.2.3. 스핀락 vs 뮤텍스

스핀락(Spinlock)은 뮤텍스와 유사하게 임계구역을 보호하기 위한 락이지만, 자원을 점유하고 있는 스레드가 해제될 때까지 계속해서 반복적으로 확인(스핀)한다. 즉, 자원이 사용 중일 때 자원을 기다리는 스레드는 대기 상태로 전환되지 않고, 그 자원이 풀릴 때까지 CPU 사이클을 소모하며 자원을 획득하려는 시도를 계속 반복한다. 이를 바쁜 대기(busy waiting)라고 부르기도 한다.

스핀락은 자원을 기다리는 동안 CPU 자원을 계속 소모하지만, 락을 짧은 시간 내에 해제할 수 있는 경우에는 뮤텍스보다 성능이 좋을 수 있다. 스핀락은 짧은 임계구역이나 컨텍스트 스위치가 비용이 큰 환경에서 효과적이다.

특성	뮤텍스	스핀락
대기 방식	대기 상태로 블록됨	계속 반복하여 자원 획득 시도(바쁜 대기)
CPU 자원 소모	대기 중에 CPU 자원을 소모하지 않음	자원이 사용 중일 때 CPU 자원을 계속 소모
컨텍스트 스위치	컨텍스트 스위치가 발생하여 성능 오버헤드 발생	컨텍스트 스위치 없음
자원 획득 시간	긴 대기 시간에 적합	짧은 대기 시간에 적합
적합한 환경	대기 시간이 길거나 자원이 자주 점유되는 상황	짧은 임계구역 또는 컨텍스트 스위치 비용이 큰 상황

---

Reference

• KOCW 양희재 운영체제