[운영체제] Process Synchronization

Process Synchronization

 

Process Synchronization은 여러 프로세스가 공유 데이터를 동시에 접근할 때 발생할 수 있는 문제를 해결하고, 데이터의 일관성(consistency)을 보장하기 위한 메커니즘이다.

 

이 메커니즘은 여러 프로세스 간의 Race Condition을 방지하고, 데이터의 무결성을 보장하며 시스템의 안정성을 유지한다.

 

 

 

 

Race Condition

 

컴퓨터는 데이터를 저장소에서 읽고, 이를 연산하여 다시 저장한다.

 

그러나 여러 프로세스가 같은 데이터를 동시에 접근하면 예상치 못한 결과가 발생할 수 있다.

 

만약 동일한 자원에 접근하는 두 프로세스가 동시에 실행된다면 데이터를 읽는 순간 값이 서로 충돌하여

최종 결과가 예측 불가능해진다. 이러한 문제를 Race Condition이라고 합니다.

 

 

 

 

 

 

 

Critical Section

 

 

Critical Section은 프로세스가 공유 데이터를 접근/수정하는 코드 부분이다.

 

동기화 문제를 해결하려면 Critical Section에서 하나의 프로세스만 실행되도록 해야 한다.

 

 

Critical Section 문제 해결 조건은 아래와 같다.

 

Mutual Exclusion (상호 배제)
한 프로세스가 Critical Section을 실행 중일 때, 다른 프로세스는 접근할 수 없어야 한다.

 

Progress (진행)
Critical Section에 진입하려는 프로세스가 있을 때, 선택된 프로세스는 적절한 시간 안에 진입해야 한다.

 

Bounded Waiting (한정 대기)

프로세스가 Critical Section에 진입 요청을 했을 때, 다른 프로세스들이 Critical Section에 들어가는 횟수는 제한적이어야 한다.

 

 

 

 

 

Peterson's Algorithm

 

flag와 turn 변수를 이용하여 Critical Section 접근 순서를 조정하는 알고리즘이다.

 

int turn;
bool flag[2]; // 프로세스 i가 들어가려는 의사 표시

// Process i
do {
    flag[i] = true;
    turn = j;           // 상대방에게 우선권 부여
    while (flag[j] && turn == j);  // 상대방이 들어가려 한다면 대기
    flag[i] = false;    // 나왔음
} while (true);

 

 

 

해당 알고리즘은 Mutual Exclusion, Progress, Bounded Waiting 조건을 충족하지만 Busy Waiting 문제가 발생한다.

 

 

 

 

 

Test-And-Set (TAS)

 

하드웨어 기반의 동기화 기법으로 하나의 명령어로 테스트와 업데이트를 원자적으로 수행한다.

 

bool TestAndSet(bool *target) {
    bool temp = *target;
    *target = true;
    return temp;
}

// Critical Section 접근
while (TestAndSet(&lock));  // lock이 해제될 때까지 대기
// Critical Section
lock = false;               // lock 해제

 

 

 

 

해당 알고리즘은 하드웨어 지원으로 효율적으로 사용이 가능하다.

하지만 Peterson's Algorithm과 마찬가지로 여전히 Busy Waiting 문제 존재한다.

 

 

 

 

 

 

Semaphore

 

wait와 signal 연산으로 동작하는 알고리즘이다.

 

// Semaphore 연산
P(S) {  // wait
    S--;
    if (S < 0) {
        // 프로세스 대기
        block();
    }
}

V(S) {  // signal
    S++;
    if (S <= 0) {
        // 대기 중인 프로세스 깨우기
        wakeup();
    }
}

 

 

 

 

Counting Semaphore

0 이상의 정수를 가지며 유한한 자원 관리에 사용한다.

 

Binary Semaphore (Mutex)

0과 1만 가지며 Mutual Exclusion에 사용한다.

 

 

 

 

 

 

생산자 소비자 문제 (Producer-Consumer Problem)

 

 

버퍼를 공유하는 생산자와 소비자가 동시에 작업할 때 데이터가 충돌하는 문제를 의미한다.

 

Semaphore를 사용하여 이를 해결할 수 있다.

 

// Synchronization Variables
semaphore mutex = 1;  // Mutual Exclusion
semaphore empty = N;  // 남은 버퍼 공간
semaphore full = 0;   // 채워진 버퍼 공간

// Producer
do {
    produce(item);
    P(empty);
    P(mutex);
    add(item);
    V(mutex);
    V(full);
} while (true);

// Consumer
do {
    P(full);
    P(mutex);
    remove(item);
    V(mutex);
    V(empty);
    consume(item);
} while (true);

 

 

 

 

 

 

 

독자 저자 문제 (Reader-Writer Problem)

 

 

여러 Reader와 Writer가 DB에 접근 시, 데이터 무결성을 유지할 수 없다는 문제가 존재한다.

 

Reader와 Writer의 접근 순서를 제어하여 이를 해결할 수 있다.

 

 

int readcount = 0;        // 현재 Reader의 수
semaphore mutex = 1;      // readcount 보호
semaphore db = 1;         // DB 접근 보호

// Reader
P(mutex);
readcount++;
if (readcount == 1) P(db);  // 첫 Reader가 DB 접근 잠금
V(mutex);

// Critical Section (Reading)
P(mutex);
readcount--;
if (readcount == 0) V(db);  // 마지막 Reader가 DB 접근 잠금 해제
V(mutex);

// Writer
P(db);
// Critical Section (Writing)
V(db);