혼자 공부하는 컴퓨터 구조 + 운영체제 - 프로세스 동기화와 교착 상태

개발지식

Aug 13, 2023

혼공학습단

혼공

혼공컴운

혼공단 10기 5주차 학습 기록

프로세스 동기화(Process Synchronization)

프로세스들은 서로 데이터를 주고받으며 실행되는데, 이들이 올바르게 실행되기 위해서는 수행 시기를 맞추는 동기화가 필수적이다. 동기화는 크게 실행 순서 제어와 상호 배제로 분류할 수 있다.

실행 순서 제어 동기화

프로세스는 자신의 순서에 맞게 실행되어야 한다. 예를 들어, A는 파일 1에 데이터를 저장하는 프로세스이고 B는 파일 1에 저장된 데이터를 읽는 프로세스라고 한다면, B는 A가 실행된 이후에만 실행할 수 있으므로 두 프로세스가 동시에 실행되면 A -> B 순서대로 실행해야 한다. 반대로 실행된다면 B는 파일의 데이터를 읽을 수 없기에 프로세스 실행에 문제가 발생하게 되는 것이다.

상호 배제 동기화

A는 기존 값에 3을 더하는 프로세스, B는 기존 값에 5를 더하는 프로세스라고 가정해 보자. 초깃값이 0이고 두 프로세스가 동시에 실행될 때 이상적인 결괏값은 0 + 3 + 5 = 8이어야 한다.

그러나 동기화가 이루어지지 않은 경우, 즉 기존 값을 A, B가 동시에 사용하게 된다면, A 프로세스가 기존 값에 접근하기도 전에 B가 기존 값에 접근하여 결괏값이 달라지는 문제가 발생한다. 여기서 동시에 실행하면 안 되는 자원에 접근하는 영역을 임계 구역(critical section)이라고 한다.

여러 프로세스가 임계 구역에 접근하려고 하면 하나의 프로세스를 제외한 나머지 프로세스들은 대기해야 하는데, 바로 이 과정을 관리하는 것이 상호 배제 동기화이다.

동기화 기법

뮤텍스 락(Mutex lock; MUTual EXclusion lock)

뮤텍스 락은 상호 배제를 위해 임계 구역에 잠금을 설정함으로써 동시에 접근하면 안 되는 자원을 보호하는 동기화 도구이다. 프로세스가 임계 구역에 들어가기 위해서는 잠겨 있는지 확인하고 잠겨 있지 않다면 잠근 후 임계 구역에 진입하며, 나올 때는 잠금을 해제하는 방식으로 구현할 수 있다.

간단한 구현 예시로 두 개의 함수 acquire(), release()와 전역 변수 available을 이용한 방법이 있다. acquire(), release()를 임계 구역 전후로 호출함으로써 뮤텍스 락을 구현한다.

acquire(): 임계 구역이 잠겨 있는지 확인하는 함수

release(): 임계 구역의 잠금을 해제하는 함수

available: 임계 구역에 진입할 수 있는지 확인하는 boolean 값 변수

acquire() {
  while (!available)
    ; // busy wait
  available = false;
}

// 임계 구역

release() {
  available = true;
}

acquire() 함수를 살펴보면 임계 구역에 진입할 수 있는지 쉴 새 없이 반복하는 과정이 포함된 것을 알 수 있다. 이러한 대기 방식을 busy wait이라고 한다.

세마포어(Semaphore)

세마포어는 뮤텍스 락과 비슷하지만 공유 자원이 여러 개 있는 상황에서도 사용할 수 있는 동기화 도구이다. 뮤텍스 락과 비슷하게 wait(), signal() 두 개의 함수와 전역 변수(S) 하나로 단순하게 구현할 수 있다.

wait()(또는 P()): 임계 구역에 진입할 수 있는지, 대기해야 하는지 알리는 함수

signal()(또는 V()): 대기 상태의 프로세스에 진입해도 된다는 신호를 주는 함수

S: 임계 구역에 진입할 수 있는 프로세스의 개수(N)를 나타내는 정수 변수

wait() {
  while (S <= 0)
    ; // busy wait
  S--;
}

// 임계 구역

signal() {
  S++;
}

뮤텍스 락과 비슷하게 세마포어 역시 wait() 함수 내 진입 가능 여부를 계속해서 확인하는 코드가 들어간다. 여기서 문제는 busy wait을 반복하는 시간에 CPU는 생산적인 작업을 할 수 없어 주기를 낭비한다는 것이다.

그래서 세마포어는 이를 해결하기 위해 실제로는 다른 방법을 사용한다. wait() 함수는 사용할 수 있는 자원이 없는 경우 해당 프로세스를 대기 상태로 만들고 PCB를 대기 큐에 넣는다. 그 후, 다른 프로세스가 작업이 끝나고 signal() 함수를 호출하면 대기 큐에서 프로세스를 제거하고 준비 큐로 옮긴다.

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

// 임계 구역

signal() {
  S++;
  if (S <= 0) {
    remove a process p from Queue;
    wakeup(p);
  }
}

모니터(Monitor)

세마포어처럼 매번 임계 구역 전후로 wait()와 signal()을 명시하는 것은 번거로운 일이다. 그래서 인터페이스를 통해서만 공유 자원에 접근하도록 하는 동기화 도구인 모니터가 등장했다.

모니터는 공유 자원에 접근하고자 하는 프로세스를 큐에 삽입하고 삽입된 순서대로 자원을 이용하게 한다. 그리고 인터페이스에 접근하기 위한 큐를 생성해 모니터 내부에는 하나에 프로세스만 들어오도록 하는 것이다.

모니터는 실행 순서를 위한 동기화도 제공하는데, 이때 조건 변수(condition variable)를 사용한다. 조건 변수가 여러 개 있다면, 각 변수에 대한 wait(), signal() 함수를 구분하여 특정 프로세스를 실행하고 중단할 수 있다.

교착 상태(Deadlock)

한 번쯤은 출퇴근 길이나 휴가철에 도로가 꽉 막혀 차량 정체가 심화되는 현상을 경험해 봤을 것이다. 이와 같이 프로세스 실행 과정에도 자원을 이용하고 기다리는 방식이 꼬여 더 이상 어떤 프로세스도 진행할 수 없는 현상이 발생하곤 한다.

예를 들어, 뮤텐스 락에서 A 프로세스는 임계 구역 진입 전에 lock 1을 잠그고 B 프로세스는 진입 전에 lock 2를 잠갔다고 가정해 보자. A 프로세스 lock 1에 해당하는 자원을 점유한 채 lock 2가 해제되길 기다리고 B 프로세스는 lock 2 자원을 점유한 채 lock 1이 해제되기를 기다리는 상황이라면, 여기서 더 이상 A, B 프로세스는 진행할 수가 없게 된다. 이처럼 일어나지 않을 사건을 기다리며 무한정 대기하는 상태를 교착 상태라고 한다.

자원 할당 그래프(Resource-Allocation Graph)

자원 할당 그래프는 어떤 프로세스가 어떤 자원을 사용하고 기다리는지를 간단하게 보여주는 그래프이다. 아래의 규칙을 따라 그려진다.

자원 할당 그래프 규칙

프로세스는 원, 자원 종류는 사각형

사용할 수 있는 자원의 개수(N)는 사각형 내부에 점으로 표현

프로세스가 자원을 할당받아 실행 중이라면 자원 -> 프로세스 화살표 표시

프로세스가 자원을 대기 중이라면 프로세스 -> 자원 화살표 표시

교착 상태가 발생한 상황은 자원 할당 그래프가 원의 형태를 띤다.

교착 상태 발생 조건

교착 상태는 아래 4가지 조건을 모두 만족하면 발생할 수 있다. 다만, 하나라도 만족되지 않으면 발생하지 않는다.

상호 배제(Multi Exclusion)
프로세스들이 자원을 동시에 사용하지 못하고 한 자원을 하나의 프로세스가 독점한다.

점유와 대기(Hold and Wait)
프로세스가 어떤 한 자원을 점유한 상태에서 다른 자원을 기다린다.

비선점(Nonpreemptive)
다른 프로세스의 자원을 강제로 뺏지 못하고 작업이 끝나길 기다린다.

원형 대기(Circular Wait)
자원 할당 그래프가 원의 형태를 띠는 것처럼 프로세스들이 원의 형태로 자원을 대기한다.

교착 상태 해결 방법

교착 상태 예방

교착 상태를 예방하려면 발생 조건 4가지 중 하나를 충족하지 못하게 하면 된다. 그중 어떤 조건이 가장 쉬운 방법일까?

상호 배제를 없애려면 모든 자원을 공유하게 하면 되지만, 현실적으로 무리가 있다.

점유와 대기를 없애면 특정 프로세스에 자원을 몰아주게 되어 자원의 활용률이 낮아진다.

비선점을 없애면 프로세스는 강제로 다른 프로세스의 자원을 빼앗게 할 수 있다. 그러나 프린터와 같이 출력 도중에 다른 프로세스가 빼앗을 수 없는 자원도 있기에 범용성이 떨어진다는 단점이 존재한다.

원형 대기를 없애려면 모든 자원에 번호를 붙여 오름차순으로 자원을 할당하면 된다. 앞 세 가지 조건보다는 비교적 현실적인 방안이지만, 모든 자원에 번호를 붙이기란 쉽지도 않을뿐더러 각 자원의 번호에 따라 특정 자원의 활용률이 떨어질 수 있다.

종합하면, 조건을 없애는 건 교착 상태가 발생하는 것을 확실하게 예방할 수 있지만 모두 부작용이 따른다.

교착 상태 회피

교착 상태를 회피한다는 것은 교착 상태가 발생하지 않을 정도로 조금씩 자원을 할당하는 방식이다. 회피 방식은 한정된 자원을 무분별하게 할당하기 때문에 교착 상태가 발생한다고 간주한다.

교착 상태 없이 안전하게 프로세스들에 자원을 할당하는 순서를 안전 순서열(safe sequence)이라고 한다. 그리고 안전 순서열대로 프로세스에 자원을 배분하여 교착 상태가 발생하지 않는 상태를 안전 상태(safe state), 안전 순서열이 없어 교착 상태가 발생할 수도 있는 상황을 불안전 상태(unsafe state)라고 한다.

운영체제가 교착 상태를 회피하기 위해서는 시스템의 상태가 항상 안전 상태를 유지하도록 자원을 할당하면 된다.

교착 상태 검출 후 회복

검출 후 회복 방식은 프로세스들이 자원을 요구할 때마다 매번 할당하면서 주기적으로 교착 상태 발생 여부를 검사한다. 교착 상태가 검출되면 아래와 같은 방식으로 회복한다.

선점을 통한 회복

교착 상태가 해결될 때까지 하나의 프로세스에 자원을 몰아준다.

프로세스 강제 종료를 통한 회복

가장 단순하면서 확실한 방법으로는 프로세스를 강제 종료하는 것이다. 교착 상태가 발생하면 그 상태에 놓인 모든 프로세스를 강제 종료하거나 하나씩 강제 종료한다. 전자는 한 번에 상태를 회복시킬 수 있지만 많은 프로세스가 작업 내역을 잃어버릴 수 있고, 후자는 작업 내역을 잃는 프로세스는 적지만 교착 상태 여부를 확인하는 과정에서 오버헤드가 발생할 수 있다.

기본 미션

p.363

1. 뮤텍스 락과 세마포에 대한 설명으로 옳지 않은 것을 고르세요.

(1) 뮤텍스 락은 임계 구역을 잠근 뒤 임계 구역에 진입함으로써 상호 배제를 위한 동기화를 이룹니다. (2) 세마포는 공유 자원이 여러 개 있는 상황에서도 이용할 수 있습니다. (3) 세마포를 이용해 프로세스 실행 순서 제어를 위한 동기화도 이룰 수 있습니다. (4) 세마포를 이용하면 반드시 바쁜 대기를 해야 합니다.

정답:

(4) busy wait를 필수로 실행하지 않고 대기 상태에 접어들게 만드는 것도 가능하다.

추가 미션

Q. 임계 구역, 상호 배제 개념을 정리하기

임계 구역이란, 동시에 실행하면 안 되는 자원에 접근하는 코드 영역을 말한다. 하나의 프로세스가 임계 구역에서 실행되고 있다면 그 이외의 프로세스들은 임계 구역 밖에서 대기하고 있어야 한다.

만약 임계 구역에 여러 프로세스가 동시에 진입할 경우, 데이터의 일관성이 깨지는 레이스 컨디션(race condition)이 발생한다.

그래서 임계 구역에 두 개 이상의 프로세스가 접근하지 못하게 제어하는 것이 필요한데, 이를 상호 배제라고 한다. 상호 배제 동기화는 올바른 프로세스 실행을 위해 꼭 필요한 과정이다.

References

[📚book] 혼자 공부하는 컴퓨터 구조 + 운영체제

Table Of Contents