[OS] 프로세스 동기화, 교착 상태

프로세스 동기화

프로세스가 병렬로 실행될 때 여러 프로세스가 공유하는 데이터의 무결성이 유지되는 것을 의미한다.

공유자원, 경쟁상태, 임계구역

공유자원

• 여러 프로세스가 공유하는 자원 (메모리, 파일 등)

경쟁상태

• 멀티 태스킹 혹은 멀티 쓰레딩 환경에서 공유 자원을 사용할 때 발생한다.
• 데이터베이스에서 여러 트랜잭션이 동일한 레코드에 접근할 때에도 발생

임계 영역

• 공유 자원에 접근하는 코드 영역으로 접근 순서에 따라 실행 결과가 달라질 수 있다.
• 여러 프로세스 혹은 쓰레드 등이 한번에 접근하면 문제가 생길 수 있다.
• 해결 조건
  • 상호배제 : 한 프로세스가 임계구역에 진입하면 다른 프로세스는 진입할 수 없다.
  • 한정 대기 : 어떤 프로세스도 무한 대기하지 않는다. (기아 상태 X)
  • 유연한 진행 : 한 프로세스가 다른 프로세스의 진입을 방해해서는 안된다.

피터슨 알고리즘

• 3가지 조건(상호 배제, 진행, 한정 대기)을 보장하기 위한 알고리즘 중 하나이다.
• flag와 turn이라는 변수로 임계영역에 들어갈 프로세스(혹은 스레드)를 결정해 서로 교대로 실행되도록 한다.
  • flag : 어떤 프로세스가 임계영역에 진입할 것인지 나타내는 변수
  • turn : 어떤 프로세스가 임계영역에 진입할 차례인지 나타내는 변수

class PetersonAlgorithm {
    boolean[] flag = new boolean[2];
    int turn;

    void process1() {
        flag[0] = true;
        turn = 1;
        while (flag[1] && turn == 1) {
            // 상대 프로세스가 임계영역에 있고, 상대 프로세스의 차례일 때 대기
        }
        // 임계영역 진입
        // 임계영역에서 수행할 작업
        flag[0] = false;
        // 임계영역에서 빠져나옴
    }

    void process2() {
        flag[1] = true;
        turn = 0;
        while (flag[0] && turn == 0) {
            // 상대 프로세스가 임계영역에 있고, 상대 프로세스의 차례일 때 대기
        }
        // 임계영역 진입
        // 임계영역에서 수행할 작업
        flag[1] = false;
        // 임계영역에서 빠져나옴
    }
}

뮤텍스 (Mutual Exclusion)

• 프로세스 간 동기화에 사용되며 상호 배제를 의미한다.
• 공유된 자원의 데이터를 여러 스레드가 접근하는 것을 막아 한 공유자원에 하나의 프로세스만 접근할 수 있게 한다.
• Locking과 Unlocking을 사용한다,
  • 임계영역 진입시 lock을 하고, 나올 땐 unlock을 한다.
• Busy waiting : 대기 프로세스는 계속 실행중인 상태로 임계 구역을 확인한다.
• 이진 세마포어와 유사하다.(0 혹은 1의 값을 가지는 세마포어)

세마포어

• 프로세스 간 동기화에 사용된다.
• 여러개의 동기화 대상에 사용할 수 있다.
  • N개의 공유자원 - N개의 프로세스
• 세마포어는 자원의 상태를 나타내는 일종의 변수로 상태 변수이다.
• P : test, acquire() 혹은 wait()함수로 사용한다. (사용 가능 자원의 감소)
• V : increment, release() 혹은 signal()함수로 사용한다. (사용 가능 자원의 증가)
• P, V의 순서를 지켜 사용해야 하며 P 혹은 V를 한 임계구역에 중복해 사용하면 안된다.

	세마포어	뮤텍스
사용 방법	여러 프로세스 또는 스레드 간 상호배제	임계영역에 대한 상호배제
소유권	소유권 없음	소유권이 있고, 소유주가 해제해야 함
해제 권한	소유하지 않은 스레드가 해제 가능	소유한 스레드만이 해제 가능
대기 큐	대기 큐를 가지지 않음	대기 큐를 가질 수 있음
범위	시스템 범위	프로세스 범위
지속성	파일 시스템 상에 파일 형태로 존재	프로그램 종료 시 자동으로 지워짐
동기화 대상 수	여러 개의 동기화 대상 가능	오직 하나의 동기화 대상만 가능

모니터

• 프로세스 간 동기화에 사용된다.
• 세마포어의 잘못된 사용(단점)을 개선하기 위해 등장하였다.
• 상호배제 큐(Mutual Exclusion Queue)와 조건동기 큐(Conditional Synchronization Queue)가 사용된다
  • 상호배제 큐 : 공유자원을 얻기위해 프로세스가 대기하는 큐
  • 조건동기 큐 : 공유자원을 점유하고 있던 프로세스가 block되면서 대기하는 큐 (다른 프로세스에게 자원을 뺏긴것)
• 프레임워크 혹은 라이브러리 자체에서 제공되며, Java에서 사용된다.
• synchronized가 붙은 코드 블록이 동기화된다.
• wait() : 자원을 점유하던 프로세스를 block시키는 메소드
• notify() : 조건동기 큐의 block 상태 프로세스를 깨우는 메소드
• notifyAll() : 조건동기 큐의 모든 block 상태 프로세스를 깨우는 메소드

교착 상태 (Deadlock)

정의

• 두 개 이상의 프로세스가 서로 상대방의 작업이 끝나기 만을 기다리고 있기 때문에 결과적으로 아무것도 완료되지 못하는 상태를 일컫는다.

조건

다음 4가지 조건을 모두 만족할 때 교착 상태가 발생할 수 있다.

1. 상호배제 - 배타적 통제권(동시 사용 불가)
2. 점유대기 - 할당된 자원을 가진 상태에서 다른 자원을 기다림
3. 비선점 - 자원을 뺏을 수 없음
4. 순환대기 - 각 프로세스는 순환적으로 다음 프로세스가 요구하는 자원을 갖고 있음

해결 방법

예방(Prevention)

교착 상태 발생 조건 중 한가지 이상을 사전에 일어나지 않게 한다.

1. 상호 배제(Mutual Exclusion) 부정
   • 읽기 전용 파일과 같은 공유 자원을 사용
2. 점유 및 대기(Hold and Wait) 부정
   • 프로세스 대기를 없애기 위해서 프로세스가 실행되기 전에 필요한 모든 자원을 할당한다. (자원 낭비 발생)
   • 자원을 점유하지 않고 있을 때에만 다른 자원을 요청할 수 있도록 한다. (기아상태가 될 수 있음)
3. 비선점(No Preemption) 부정
   • 모든 자원에 대한 선점을 허용
   • 프로세스가 할당받을 수 없는 자원을 요청하는 경우, 기존에 가지고 있던 자원을 모두 반납하고 새 자원과 이전 자원을 얻기 위해 대기시킨다. (자원 낭비 발생 )
4. 순환 대기(Circular Wait) 부정
   • 자원에 고유한 번호를 할당하고, 번호 순서대로 자원을 요구한다. (자원 낭비 발생)

회피 (Deadlock Avoidance)

• 교착 상태가 발생하기 전에 교착 상태를 예상하여 안전한 상태(safe state)에서만 자원 요청을 허용하는 방법이다.

회피를 하기 위해서는 다음과 같은 가정이 필요하다.

• 프로세스 수가 고정되어 있어야 한다.
• 자원의 종류와 수가 고정되어 있어야 한다.
• 프로세스가 요구하는 자원 및 최대 자원의 수를 알아야 한다.
• 프로세스는 반드시 자원을 사용 후 반납해야 한다.

교착상태 회피 방법은 이러한 가정들이 필요하기 때문에 현실성이 부족하며, 자원 요청이 있을 때마다 교착상태 회피 알고리즘을 사용하므로 상당한 오버헤드가 발생한다.

탐지 (Detection)

• 탐지 알고리즘을 사용하여 교착상태가 발생했는지 탐지한다.
• 발견
  • 타임아웃 : 특정 프로세스가 일정시간동안 작업이 진행되지 않으면 교착상태가 발생했다고 판단한다.
  • 자원할당 그래프 : 그래프를 보고 단일자원일때 사이클이 생기면 교착상태로 판단한다.
• 회복
  • 모든 프로세스 강제종료 : 재시작 후 동시에 실행하면 교착상태가 재발생할 수 있으므로 순차적으로 실행한다.
  • 교착상태 원인 프로세스를 하나씩 종료 : 우선순위가 낮은 프로세스부터 종료시킨다.

식사하는 철학자 문제

• 원형 테이블에 5명의 철학자와 5개의 젓가락이 있는 상황이 있다.
• 모든 철학자는 생각과 식사를 반복하며, 식사를 하기 위해서는 2개의 젓가락이 필요하다.
• 중간에 모든 철학자가 식사를 하지 못하고 굶는 문제가 발생한다. (Starvation)