[운영체제] 동기화 도구들 (뮤텍스, 세마포어, 모니터)

프로세스는 동시에 실행될 수 있으며, 여러 개의 프로세스가 협력할 때는 프로세스 사이에 데이터가 동기화되지 않는 문제가 발생할 수 있다. 만약 두 프로세스가 동시에 어떤 변수의 값을 바꾼다면 프로그래머의 의도와는 다른 결과가 나올 것이다. 이처럼 프로세스가 어떤 순서로 데이터에 접근하느냐에 따라 결과 값이 달라질 수 있는 상황을 경쟁 상태(race condition)라고 한다.

 

임계구역 (Critical Section)

---

코드상에서 경쟁 조건이 발생할 수 있는 특정 부분을 임계구역(critical section)이라고 부른다. 임계 구역은 둘 이상의 스레드가 동시에 접근해서는 안 되는 공유 자원이다. critical section problem를 해결하기 위해서는 몇가지 조건을 충족해야 한다.

1. 상호 배제(mutual exclusion): 한 프로세스가 임계구역에서 실행된다면, 다른 프로세스들은 임계구역에 접근해서는 안된다.

2. 진행(progress): critical section에서 작업중인 프로세스가 없다면 다른 프로세스가 critical section에 진입할 수 있어야 한다.

3. 한정된 대기(bounded waiting): critical section에 진입하려는 프로세스가 무한하게 대기해서는 안 된다. 프로세스가 자기의 임계구역에 진입하려는 요청을 한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 자신의 임계구역에 진입하도록 허용되는 횟수에 한계가 있어야 한다.

비선점형 커널(Non-preemptive kernels)로 구현하면 임계 영역 문제가 발생하지 않는다. 하지만 비선점 스케줄링은 반응성이 떨어지기 때문에 슈퍼 컴퓨터가 아니고선 잘 사용하지 않는다.

 

Peterson's Solution

---

임계구역에 대한 고전적인 소프트웨어 기반 해결책이다. 피터슨의 알고리즘(Peterson's algorithm)은 상호 배제를 위한 병렬 프로그래밍 알고리즘으로서, 공유 메모리를 활용하여 여러 개의 프로세스가 하나의 자원을 함께 사용할 때 문제가 발생하지 않도록 해준다.

프로세스가 임계구역에 진입할 준비가 되어있는지 나타내는 변수flag와 critical section에 진입하고자하는 프로세스를 가리키는 변수 turn을 만들어 어떤 프로세스가 임계 영역에 진입하면 flag를 lock하고, 나오면 unlock 하는 방식으로 임계 영역 문제를 해결한다.

do {
  flag[i] = true;
  turn = j;
  while (flag[j] && turn == j);
  // Critical section
  flag[i] = false;
  // Remainder section
} while(true);

 

Mutex Locks

---

mutex는 MUTual EXclusion의 축약어이다. 임계구역을 보호하고, 경쟁 조건을 방지하기 위해 뮤텍스 락을 사용한다. 여러 스레드가 공통 리소스에 접근하는 것을 제어하는 기법으로, lock이 하나만 존재할 수 있는 locking 매커니즘을 따른다.

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

release() {
	available = true;
}

한 프로세스가 임계구역에 있는 동안 임계구역에 들어가기를 원하는 다른 프로세스들은 busy waiting(acquire함수를 반복해서 호출)을 해야한다. 계속된 루프의 실행은 CPU 사이클을 낭비하기 때문에 다중 프로그래밍 시스템에서 문제가 된다.

 

세마포어 (Semaphores)

---

세마포어(Semaphore)는 여러 개의 프로세스나 스레드가 critical section에 진입할 수 있는 locking 매커니즘이다. 세마포어는 카운터를 이용해 동시에 리소스에 접근할 수 있는 프로세스를 제한한다.

세마포어 S는 정수값을 가지는 변수이며, P와 V라는 명령에 의해서만 접근할 수 있다. P는 임계 구역에 들어가기 전에 수행되고, V는 임계 구역에서 나올 때 수행된다(“검사하다”를 의미하는 네덜란드어 proberen에서 P, 그리고 signal() 연산은 “증가하다”를 의미하는 verhogen에서 V라고 지어졌다.) 이때 변수 값을 수정하는 연산은 모두 원자성을 만족해야 한다. 다시 말해, 한 프로세스(또는 스레드)에서 세마포어 값을 변경하는 동안 다른 프로세스가 동시에 이 값을 변경해서는 안 된다.

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

signal(S) {
    S++;
}

세마포어 사용법 (Semaphore Usage)

세마포어의 값이 0과 1만 가능한 경우 바이너리 세마포어(Binary semaphore), 제한이 없는 경우 카운팅 세마포어(Counting semaphore)라고 한다. 이진 세마포어의 값은 0과 1만 가능하기 때문에 mutex lock과 유사하게 작동한다.

카운팅 세마포어는 유한한 개수를 가진 자원에 대한 접근을 제어하는데 사용될 수 있다. 세마포어는 가용한 자원의 개수로 초기화된다. 각 자원을 사용하려는 프로세스는 세마포어에 wait() 연산을 수행하며, 이때 세마포어의 값은 감소한다. 프로세스가 자원을 방출할 때는 signal() 연산을 수행하고 세마포어는 증가하게 된다. 세마포어의 값이 0이 되면 모든 자원이 사용중임을 나타낸다. 이후 자원을 사용하려는 프로세스는 세마포어 값이 0보다 커질 때까지 봉쇄된다.

세마포어 구현 (Semaphore Implementation)

Busy Waiting을 피하기 위해 세마포어 S를 대기하면서 일시 중지된 프로세스는 다른 프로세스가 signal() 연산을 실행하면 재시작되어야 한다. 프로세스는 sleep() 연산에 의해서 일시 중지되고 wakeup() 연산에 의하여 재시작된다. (대기상태 <-> 준비 완료 상태)

세마포어를 활용한 Critical Section 문제 해결 알고리즘을 구현하기 위해 세마포어의 정의는 다음과 같다.

typedef struct {
    int value; 
    struct process *list;
}semaphore;

wait과 signal

wait(semaphore *S) {
    S->value--;
    if (S->value < 0) {
        add this process to S -> list;
        sleep();
    }
}

signal(semaphore *S) {
    S->value ++;
    if (S->value <= 0) {
        remove a process P from S -> list;
        wakeup(P);    
    }
}

wakeup()과 sleep()은 프로세스를 일시 중지 or 재실행시키는 운영체제의 기본적인 시스템 콜이다.

세마포어의 프로세스 리스트는 Bounded Waiting를 보장하도록 잘 구현해야만 한다.

단일 Processor 환경에서는 wait()와 signal() 연산들이 원자적으로 실행되는것을 보장하기 위해 실행되는 동안 인터럽트를 금지함으로써 해결할 수 있지만, 다중 코어 환경에서는 모든 처리 코어에서 인터럽트를 금지하여야만 한다. 이는 매우 어려울 수 있으며 성능을 심각하게 감소시킬 수 있음으로 많은 부분을 고려해야만 한다.

 

모니터 (Monitor)

---

mutex락 혹은 세마포어를 사용할 때에도 타이밍 오류는 여전히 발생할 수 있다. 예로들어, wait()과 signal() 연산의 순서가 뒤바뀌는 경우, Critical Section이 끝나고 signal()대신 wait()이 호출되는 경우 오류가 발생한다. 이러한 오류를 해결하는 방법 중 하나로 고급 언어 구조물인 모니터(monitor)가 있다.

추상화된 데이터 형(abstract data type, ADT)은 데이터와 이 데이터를 조작하는 함수들의 집합을 하나의 단위로 묶어 보호한다. 이때 함수의 구현은 ADT의 특정한 구현과 독립적이다. 모니터 형은 모니터 내부에서 프로그래머가 정의한 상호 배제가 보장되는 일련의 연산자 집합을 포함하는 ADT이다. 모니터 형은 인스턴스의 상태를 정의하는 변수들과 이를 조작할 수 있는 프로시저 또는 함수들의 본체도 같이 포함하고 있다. 따라서 모니터 내에 정의된 함수만이 오직 모니터 내에 지역적으로 선언된 변수들과 형식 매개변수들에만 접근할 수 있다. (객체의 캡슐화와 매우 비슷한 구조)

• entry queue(진입 큐): 모니터 내의 procedure수만큼 존재
• mutual exclusion: 모니터 내에는 항상 하나의 프로세스만 진입 가능
• information hiding(정보 은폐): 공유 데이터는 모니터 내의 프로세스만 접근 가능
• condition queue(조건 큐): 모니터 내의 특정 이벤트를 기다리는 프로세스가 대기
• signaler queue(신호제공자 큐): 모니터에 항상 하나의 신호제공자 큐가 존재. singal() 명령을 실행한 프로세스가 임시 대기

 

라이브니스 (Liveness)

---

라이브니스는 프로세스가 실행 수명주기 동안 진행되는 것을 보장하기 위해 시스템이 충족해야 하는 일련의 속성을 말한다. 즉, 프로세스가 lock을 얻기 위해 무기한 대기하는 것은 “라이브니스 실패”의 한 예이다.

다양한 형태의 라이브니스 실패가 존재한다. 그러나 모두 성능과 응답성이 나쁜 것이 특징이다. 라이브니스 실패의 매우 간단한 예는 무한 루프이다. 즉, Mutex 락 및 Semaphore를 사용하여 상호 배제를 제공하려는 노력은 종종 병행 프로그래밍에서 이러한 실패로 이어질 수 있다.

교착 상태 (Deadlock)

대기 큐를 가진 Semaphore 구현은 두 개 이상의 프로세스들이, 오로지 대기 중인 프로세스들 중 하나에 의해서만 야기될 수 있는 signal()연산를 무한정 기다리는 상황이 발생할 수 있다. 이런 상태에 도달했을 때, 이들 프로세스들을 교착 상태(deadlock)라고 한다.

한 집합 내의 모든 프로세스가 그 집합 내의 다른 프로세스만이 유발할 수 있는 이벤트를 기다릴 때, 이 프로세스들의 집합이 교착 상태에 있다고 말한다. 우리가 여기서 주로 관심을 두고 있는 “이벤트”들은 mutex 락과 Sempahore 같은 자원의 획득과 방출이다.

우선순위 역전 (Priority Inversion)

높은 우선순위 프로세스가 현재 낮은 우선순위 프로세스 또는 연속된 낮은 우선순위 프로세스들에 의해 접근되고 있는 커널 데이터를 읽거나 변경할 필요가 있을 때 스케줄링의 어려움이 생기게 된다.

통상 커널데이터는 락에 의해 보호되기 때문에 낮은 우선순위 프로세스가 자원의 사용을 마칠 때까지 높은 우선순위 프로세스가 기다려야 한다. 낮은 우선순위 프로세스가 또 다른 높은 우선순위 프로세스에 의해 선점되는 경우에 상황은 더욱 복잡해진다. 이러한 경우 낮은 우선순위 프로세스는 계속 기다려야만 한다. 이 라이브니스 문제는 우선순위 역전(priority inversion)문제로 알려져 있다.

통상 우선순위 역전 문제는 우선순위 상속 프로토콜(priority-inheritance protocol)을 구현하여 해결한다. 우선순위 상속 프로토콜의 하나의 예시로서, 더 높은 우선순위 프로세스가 필요로 하는 자원에 접근하는 모든 프로세스는 문제가 된 자원의 사용이 끝날 때까지 더 높은 우선순위를 상속받는다. 자원 사용이 끝나면 원래 우선순위로 되돌아간다.

 

참조

https://www.youtube.com/watch?v=AnYN-kbCbRI