Operating System Concepts (공룡책) 6장

울·3일 전

IT기초

목록 보기
6/6

"공유 데이터에 여러 프로세스가 동시에 접근하면 데이터 불일치가 발생할 수 있다."
협력하는 프로세스들이 데이터를 안전하게 공유하려면 실행 순서를 조율해야 한다. 이것이 동기화이며, 이를 위한 도구들이 6장의 핵심이다.

목표

  1. 경쟁 조건이 왜 발생하는지 이해
  2. 임계 구역 문제의 3가지 요구 조건을 파악
  3. 뮤텍스 락, 세마포어, 모니터의 동작 방식과 차이를 비교
  4. 교착 상태, 기아, 우선순위 역전 문제를 이해

6.1 배경

경쟁 조건 (Race Condition)

여러 프로세스가 공유 데이터에 동시에 접근하고 조작할 때, 실행 순서에 따라 결과가 달라지는 상황이다.

생산자-소비자 문제로 보는 예시

공유 변수 count가 현재 5라고 가정한다.

// 생산자 코드          // 소비자 코드
count++               count--

이 한 줄 코드는 실제로 CPU에서 3단계로 처리된다.

생산자                          소비자
① register1 = count   (=5)
② register1 = register1 + 1
                       ③ register2 = count   (=5)
                       ④ register2 = register2 - 1
③ count = register1   (=6)
                       ⑤ count = register2   (=4)  ← 잘못된 결과!

count++와 count--가 동시에 실행됐지만 결과는 5가 아닌 4가 되어버렸다. 이것이 경쟁 조건이다.

경쟁 조건을 막으려면 한 번에 하나의 프로세스만 공유 데이터를 다룰 수 있도록 보장해야 한다.

6.2 임계 구역 문제 (Critical-Section Problem)

임계 구역이란

공유 데이터에 접근하는 코드 구간을 임계 구역(Critical Section) 이라 한다.

while (true) {
    [entry section]      // 임계 구역 진입 요청
        critical section // 공유 자원 접근
    [exit section]       // 임계 구역 퇴출
        remainder section// 나머지 코드
}

3가지 요구 조건

임계 구역 문제를 올바르게 해결하려면 아래 3가지 조건을 동시에 만족해야 한다.

조건설명
상호 배제 (Mutual Exclusion)한 프로세스가 임계 구역에 있으면, 다른 프로세스는 진입 불가
진행 (Progress)임계 구역에 아무도 없을 때, 진입하려는 프로세스가 있으면 결정이 무한정 미뤄져선 안 됨
한정된 대기 (Bounded Waiting)한 프로세스가 진입 요청 후 무한히 기다리는 일이 없어야 함 (기아 방지)

6.3 피터슨 해결안 (Peterson's Solution)

두 프로세스(P0, P1) 사이의 임계 구역 문제를 소프트웨어로 해결하는 고전적인 방법이다.

// 공유 변수
int turn;          // 누구 차례인지
bool flag[2];      // 각 프로세스가 진입을 원하는지

// Pi의 코드 (i = 0 또는 1, j = 1-i)
do {
    flag[i] = true;       // 나 진입하고 싶어
    turn = j;             // 상대방에게 양보
    while (flag[j] && turn == j);  // 상대가 원하고 상대 차례면 대기

        /* critical section */

    flag[i] = false;      // 나 끝났어
        /* remainder section */
} while (true);

3가지 요구 조건을 모두 만족하지만, 현대 컴퓨터에서는 컴파일러나 CPU가 명령어 순서를 바꿀 수 있어(재정렬) 항상 올바르게 동작하지 않을 수 있다. 하드웨어 지원이 필요한 이유다.

6.4 하드웨어 기반 동기화

소프트웨어만으로는 한계가 있다. 현대 CPU는 동기화를 위한 원자적(Atomic) 명령어를 제공한다.

원자적(Atomic) : 실행 도중 인터럽트나 다른 스레드의 개입 없이 한 번에 완료되는 연산

test_and_set

// 하드웨어가 원자적으로 실행
bool test_and_set(bool *target) {
    bool rv = *target;
    *target = true;  // 잠금 설정
    return rv;       // 이전 값 반환
}

// 사용 예
do {
    while (test_and_set(&lock));  // lock이 false가 될 때까지 대기
        /* critical section */
    lock = false;                 // 잠금 해제
} while (true);

compare_and_swap (CAS)

현대 시스템에서 더 많이 사용되는 방식이다.

// 하드웨어가 원자적으로 실행
int compare_and_swap(int *value, int expected, int new_value) {
    int temp = *value;
    if (*value == expected)
        *value = new_value;  // 기댓값과 같을 때만 변경
    return temp;
}

// 사용 예
do {
    while (compare_and_swap(&lock, 0, 1) != 0); // 0이면 1로 바꾸고 진입
        /* critical section */
    lock = 0;  // 잠금 해제
} while (true);

6.5 뮤텍스 락 (Mutex Lock)

Mutual Exclusion의 줄임말이다. 임계 구역을 보호하는 가장 단순한 동기화 도구다.

두 가지 연산만 존재한다.

  • acquire() : 락 획득 (임계 구역 진입)
  • release() : 락 반납 (임계 구역 퇴출)
do {
    acquire();
        /* critical section */
    release();
        /* remainder section */
} while (true);
acquire() {
    while (!available);  // 락이 없으면 대기
    available = false;   // 락 획득
}

release() {
    available = true;    // 락 반납
}

스핀락 (Spinlock)

위처럼 락을 얻을 때까지 루프를 돌며 계속 확인하는 방식을 Busy Waiting(바쁜 대기) 또는 스핀락이라 한다.

구분설명
단점대기 중에도 CPU를 계속 사용. 단일 코어에서 비효율
장점문맥 교환 없음. 대기 시간이 매우 짧을 때 오히려 유리
사용처멀티코어 환경에서 짧은 임계 구역 보호에 적합

6.6 세마포어 (Semaphore)

뮤텍스보다 더 강력한 동기화 도구다. 정수형 변수 S를 사용하며, 두 가지 원자적 연산으로만 접근한다.

연산다른 이름동작
wait(S)P 연산, DownS를 감소. S < 0이면 대기
signal(S)V 연산, UpS를 증가. 대기 중인 프로세스 깨움
wait(S) {
    S--;
    if (S < 0) {
        // 이 프로세스를 대기 큐에 추가
        block();
    }
}

signal(S) {
    S++;
    if (S <= 0) {
        // 대기 큐에서 프로세스 하나를 꺼냄
        wakeup(P);
    }
}

카운팅 세마포어 vs 이진 세마포어

구분카운팅 세마포어이진 세마포어
S 값 범위0 이상 정수0 또는 1
용도자원이 여러 개일 때상호 배제 (뮤텍스처럼 사용)
예시프린터 3대 관리임계 구역 1개 보호

세마포어 활용 예시

① 상호 배제 (Mutual Exclusion)

Semaphore mutex = 1;

// 프로세스 P1, P2 모두 동일
do {
    wait(mutex);
        /* critical section */
    signal(mutex);
} while (true);

② 실행 순서 동기화

P2의 코드 B가 반드시 P1의 코드 A 이후에 실행되어야 할 때

Semaphore synch = 0;

// P1                  // P2
A;                     wait(synch);
signal(synch);         B;

A가 완료된 후 signal(synch)를 호출해야 P2의 wait(synch)가 풀리므로, B는 반드시 A 이후에 실행된다.

세마포어의 문제점

세마포어를 잘못 사용하면 오히려 문제가 생긴다.

// ① signal → wait 순서 실수 : 상호 배제 깨짐
signal(mutex);
    /* critical section */
wait(mutex);

// ② wait → wait 이중 호출 : 교착 상태 발생
wait(mutex);
    /* critical section */
wait(mutex);

// ③ wait만 하고 signal 생략 : 영원히 블로킹
wait(mutex);
    /* critical section */
// signal(mutex) 빠짐!

이처럼 세마포어는 사용이 까다롭다. 이를 더 안전하게 다루기 위해 모니터가 등장한다.

6.7 모니터 (Monitor)

모니터는 프로세스 동기화를 위한 고수준 추상화다. 공유 자원과 그 자원을 다루는 프로시저(함수)를 하나의 단위로 묶어, 한 번에 하나의 프로세스만 모니터 내에서 실행되도록 보장한다.

┌────────────────────────────────┐
│           Monitor              │
│                                │
│  공유 변수 (Shared Variables)   │
│                                │
│  procedure P1() { ... }        │
│  procedure P2() { ... }        │
│  procedure P3() { ... }        │
│                                │
│  initialization code           │
└────────────────────────────────┘
        ↑ 한 번에 하나의 프로세스만 진입 가능

세마포어와 달리 프로그래머가 wait()/signal()을 직접 배치할 필요 없이, 모니터 내부의 프로시저만 호출하면 동기화가 자동으로 처리된다.

조건 변수 (Condition Variable)

모니터 내부에서 특정 조건을 기다리기 위해 사용하는 변수다.

condition x, y;

x.wait();    // 조건이 만족될 때까지 대기 (모니터 내 다른 프로세스 실행 허용)
x.signal();  // 대기 중인 프로세스 하나를 깨움

세마포어의 signal()과의 차이:

  • 세마포어의 signal() : 대기 프로세스가 없어도 S 값을 증가시켜 나중에 효과 발생
  • 모니터의 x.signal() : 대기 프로세스가 없으면 아무 효과 없음

Java의 모니터 - synchronized

Java는 언어 차원에서 모니터를 지원한다.

public class Counter {
    private int count = 0;

    public synchronized void increment() {
        count++;  // synchronized → 한 번에 하나의 스레드만 실행
    }

    public synchronized int getCount() {
        return count;
    }
}

6.8 활성 (Liveness)

동기화 도구를 사용해도 프로세스가 영원히 실행되지 못하는 상황이 생길 수 있다. 이를 Liveness 문제라 한다.

교착 상태 (Deadlock)

둘 이상의 프로세스가 서로 상대방이 가진 자원을 기다리며 영원히 멈춰있는 상태다.

P0: wait(S)  →  wait(Q)  →  ...
P1: wait(Q)  →  wait(S)  →  ...

P0는 S를 쥐고 Q를 기다림
P1는 Q를 쥐고 S를 기다림
→ 둘 다 영원히 대기

기아 (Starvation)

프로세스가 무한히 대기 상태에 머무는 상황이다. LIFO(후입선출) 방식의 대기 큐에서 발생할 수 있다.

우선순위 역전 (Priority Inversion)

높은 우선순위 프로세스가 낮은 우선순위 프로세스가 가진 자원을 기다리는 동안, 중간 우선순위 프로세스에 의해 낮은 우선순위 프로세스가 선점되어 실제로는 더 기다리게 되는 현상이다.

우선순위: H > M > L

① L이 자원 획득
② H가 자원 요청 → L 기다림
③ M이 L을 선점 → L이 더 오래 실행 못 함
④ H는 M이 끝날 때까지 기다려야 함

해결책: 우선순위 상속 (Priority Inheritance)

L이 자원을 보유 중이고 H가 기다리면, L의 우선순위를 H 수준으로 임시 상승시켜 M이 L을 선점하지 못하게 한다.

① L이 자원 획득
② H가 자원 요청 → L 우선순위 H 수준으로 상승
③ M이 L을 선점 못 함 (L 우선순위 높아짐)
④ L 작업 완료 → 자원 반납 → H 자원 획득

정리

절핵심 내용
6.1경쟁 조건: 실행 순서에 따라 결과가 달라지는 문제
6.2임계 구역 문제의 3대 요건: 상호 배제 / 진행 / 한정된 대기
6.3피터슨 해결안: 소프트웨어 기반. 현대 하드웨어에서 한계 존재
6.4하드웨어 해결: test_and_set, compare_and_swap (원자적 명령어)
6.5뮤텍스 락: acquire/release. 스핀락은 짧은 대기에 유리
6.6세마포어: 정수 변수 S. wait(P)/signal(V). 카운팅/이진 구분. 잘못 쓰면 교착 상태
6.7모니터: 고수준 추상화. 자동 상호 배제. 조건 변수로 대기 제어
6.8Liveness 문제: 교착 상태 / 기아 / 우선순위 역전(→ 우선순위 상속으로 해결)
profile
울
# h
이전 포스트

Operating System Concepts (공룡책) 5장

0개의 댓글