[운영체제] 6. 동기화 도구들

아래 도서 기반 정리

운영체제 | Abraham Silberschatz - 교보문고

목차

• 배경
• 임계구역 문제
• Peterson의 해결안
• 동기화를 위한 하드웨어 지원
• Mutex Locks
• 세마포
• 모니터
• 라이브니스

 

배경

---

프로세스가 병행(동시) 또는 병렬로 실행될 때, 여러 프로세스가 공유하는 데이터의 무결성에 문제를 일으킬 수 있다.

race condition (경쟁 상황)

여러 개의 프로세스가 동시에 동일한 자료를 접근하여 조작하고, 접근이 발생한 특정 순서에 따라 실행 결과가 바뀌는 상황

ex) 은행 계좌 인출 문제, 생산자 소비자 문제

이러한 문제로 프로세스들이 동기화되도록 할 필요가 있다.

 

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

---

임계구역 (Critical Section)

각 프로세스 별로 포함하고 있는 코드집합으로
하나 이상의 다른 프로세스와 공유하는 데이터에 접근하고 갱신할수 있는 부분

• Entry Section : 임계구역에 들어가기 전, 진입 가능한지의 여부 확인 후 관련 작업 요청하는 코드 영역
• Exit section : 임계 구역에서 모든 작업 끝난 후 진입하는 구역으로, 임계 구역에서 나왔다는 것을 다른 프로세스에게 알려주는 것과 관련된 작업을 수행한다.
• Remainder section : 프로세스 코드중 임계, entry, exit을 제외한 나머지 부분으로 데이터 무결성 문제를 일으키지 않는 코드 영역

 

임계구역 문제를 해결하기 위한 조건

• 상호 배제 (Mutual exclution)
  : 어떤 프로세스가 임계구역에서 실행된다면, 다른 프로세스들은 그들 자신의 임계구역에서 실행될 수 없다.
• 진행 (Progress)
  : 자신의 임계구역에서 실행되는 프로세스가 없고, 자신의 임계구역으로 진입하려고 하는 프로세스들이 있다면,
  나머지 구역에서 실행 중이지 않은 프로세스들만 다음에 누가 그 임계 구역으로 진입할 수 있는지 결정하는데 참여할 수 있으며, 이 선택은 무한정 연기될 수 없다.
• 한정된 대기 (Bounded waiting)
  : 프로세스가 자신의 임계구역에 진입하려는 요청을 한 후부터, 그 요청이 혀용될 때까지
  다른 프로세스들이 그들 자신의 임계구역에 진입하도록 허용되는 횟수에 한계가 있어야 한다.

 

비선점형 커널

• 커널모드에서 수행되는 프로세스의 선점을 허용하지 않고, 커널 모드 프로세스는 커널을 빠져나갈 때까지 또는 봉쇄될 때까지 또는 자발적으로 CPU 제어를 양보할 때까지 계속 수행된다.
• 따라서 비선점형 커널은 한 순간에 커널 안에서 실행 중인 프로세스는 하나밖에 없어 커널 자료구조에 대한 경쟁 조건을 염려할 필요 없다.
• 그러나 process starvation이 발생할 수 있고, 선점형이 실시간 프로세스에 더 적합하다.

 

Peterson 해결안 (Solution)

---

임계 구역에 대한 고전적인 소프트웨어 기반 해결책이다.

int turn;
boolean flag[2];

• turn : 임계 구역으로 진입할 순번을 나타낸다.
• flag : 프로세스가 임계구역으로 진입할 준비가 되었다는 것을 나타낸다.

while (true)
{
    flag[i] = true;
    turn = j;
    while (flag[j] && (turn == j));
    /* critical section */
    flag[i] = false;
    /* remainder section */
}

위의 코드는 앞의 임계 구역 문제를 해결하기 위한 조건 3가지를 만족한다.

요즘 컴퓨터 구조에서는 피터슨 해법이 제대로 작동한다는 보장이 없다.
싱글 스레드에서는 문제될 것이 없지만, 공유 데이터를 갖는 멀티 스레드에서는 명령어 재배치에 의해 비일관적이거나 예측하지 못한 결과가 날 수 있다.

ex)

while (true)
{
    turn = j;
    flag[i] = true;
    while (flag[j] && (turn == j));
    /* critical section */
    flag[i] = false;
    /* remainder section */
}

위와 같이 코드가 변경되면, 다음 사진과 같이 임계구역에 두 스레드가 동시에 존재할 수도 있다.

 

동기화를 위한 하드웨어 지원

---

임계 구역 문제를 해결하는데 도움을 줄 세 가지 하드웨어 명령어

메모리 장벽 (Memory Barriers)

컴퓨터 아키텍처가 응용 프로그램에게 제공하는 메모리 접근 시 보장되는 사항을 결정한 방식이다.

메모리 모델은 아래 두 가지 중 하나에 속한다.

1. 강한 순서 (Strongly ordered) : 한 프로세서의 메모리 변경 결과가 다른 모든 프로세서에 즉시 보임
2. 약한 순서 (Weakly ordered) : 한 프로세서에서의 메모리 수정이 즉시 다른 프로세서에게 반영 안 될 수 있다. 즉 가시적이지 않다.

 

메모리 장벽 , 메모리 펜스 ( Memory barriers, fences)

컴퓨터 아키텍처는 메모리의 모든 변경 사항을 다른 모든 프로세서로 전파하는 명령어를 제공해, 다른 프로세서에서 실행중인 스레드에 메모리 변경사항이 보이는 것을 보장하는데 이러한 명령어다.

 

하드웨어 명령어

많은 현대 기계는 한 워드(word)의 내용을 검사하고 변경하거나, 두 워드의 내용을 원자적으로 (atomically) 교환 할 수 있는, 인터럽트 되지 않는 하나의 단위로서 특별한 하드웨어 명령을 제공한다.

1. test_and_set()

test_and_set(&lock) 한 라인으로 구현되었기 때문에, 중간에 침투할 수가 없다.
따라서 중간에 인터럽트가 발생되어 꼬일 일이 없어 원자적 이라고 하는 것이다.

boolean test_and_set(boolean *target)
{
    boolean rv = *target;
    *target = true;
    return (rv);
}

do {
    while (test_and_set(&lock)); // do nothing
    /* critical section */
    lock = false;
    /* remainder section */
} while(true);

• 이 명령어는 원자적으로 실행된다.
• 두 개의 test_and_set() 명령어가 동시에 실행된다면, 어떤 임의의 순서로 순차적 실행된다.
• 내용물이 교차되며 실행되지 않고, 함수 단위로 순차적으로 실행된다는 의미다.
• 위 코드는 false로 초기화되는 boolean 타입의 lock 변수를 선언해 구현한 것이다.

 

2. 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);
}

while (true)
{
    while(compare_and_swap(&lock, 0, 1) != 0); // do nothing
    /* critical section */
    lock = 0;
    /* remainder section */
}

• CAS 명령어는 test_and_set() 명령어처럼 두 워드 간에 원자적으로 처리되지만,
  두 워드의 내용을 교환한다는 다른 기법을 사용한다.
• 두 개의 CAS 명령어가 동시에 실행되면, 임의의 순서로 순차적으로 실행된다.

 

이 방법은 상호 배제는 만족하지만, 한정된 대기(Bounded waiting)를 만족시키지 않는다.

• CAS 코드에 waiting을 추가해 한정된 대기 조건을 만족 시킨다.

while (true)
{
    waiting[i] = true;
    key = 1;
    while (waiting[i] && key == 1)
        key = compare_and_swap(&lock, 0, 1);
    waiting[i] = false;
    
    /* critical section */
    
    j = (i + 1) % n;
    while ((j != i) && !waiting[j])
        j = (j + 1) %n;
    if (j == i)
        lock = 0;
    else
        waiting[j] = false;
        
    /* remainder section */
}

 

Mutext Locks

---

Spin Lock

임계 구역을 보호하고, 경쟁조건을 방지하기 위한 기법이다.

프로세스는 임계구역에 들어가기 전에 반드시 lcok을 획득해야 하고, 임계구역을 빠져나올 때 lock을 반환해야 한다.

• mutual exclusion (상호 배제)의 줄임말이다.
• acquire() : lock을 획득하는 함수
• release() : lock을 반환하는 함수

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

release()
{
    abailable = true;
}

• available : boolean 타입으로 lock의 가용 여부를 표시한다.

 

Mutex lock을 사용한 임계구역 문제 해결책

• acquire() 호출에 성공하고, lock은 곧 사용 불가 상태가 된다.
• 사용 불가 상태의 lock을 획득하려고 시도하는 프로세스는 lock이 반환될 때까지 봉쇄된다.

 

단점

바쁜 대기(busy waiting)를 해야한다.

• 한 프로세스가 임계구역에 있는 동안, 임계 구역에 들어가기를 원하는 다른 프로세스들은 acquire() 함수를 호출하는 반복문을 실행해야 한다
• 계속 루프를 돈다면, 프로세스간 하나의 CPU 코어를 공유하는 멀티 프로그래밍 시스템에선 문제가 된다.
• CPU 사이클을 바쁜 대기에 낭비하는 상태가 된다.

 

스핀락의 단점을 개선할 수 있는 형태가 아래의 Mutex Lock과 Semaphore다.

 

Mutextlock

락을 취득할 때 까지 대기하며 계속 확인하는 방식이 아니라
운영체제가 관여해 공유자원을 대기하는 프로세스를 waiting 상태로 전환하고 (즉, CPU 자원 회수),
실행하는 프로세스가 로직을 끝내고 락을 반환하면, waiting 상태의 프로세스를 깨워 로직을 실행한다.

이처럼 락을 가질 수 있을 때까지 waiting 상태로 전환해 mutual exclusion을 보장하는 락을 뮤텍스 락이라고 한다.

 

+++
그렇다면 Mutex Lock이 항상 Spinlock보다 좋을까?

뮤텍스 락에선 스레드가 큐에 들어가고, 나중에 깨워주는 과정에서 context switch가 발생한다. 이는 앞 장에서 설명했듯 오버헤드가 발생하는 방법이다.
따라서 context switch가 발생하는 것보다 critical section에서 작업이 더 빨리 끝난다면, 스핀락 방식을 사용하는 것이 더 효율적이다.
다만, 이는 멀티 코어 환경에서만 해당한다. 멀티 코어에서 대기하는 스레드와 락을 취득한 스레드가 서로 다른 코어에서 실행중이라면, context switch가 발생하지 않는다.
싱글 코어 환경에선 context switch가 무조건 발생하기 때문에 전혀 이점이 없다.

 

Semaphores (세마포어)

---

Mutex lock과 유사하게 동작하며 프로세스를 좀 더 복잡하게 동기화할 수 있도록 해주는 방법을 제공한다.
하나 이상의 프로세스 || 스레드가 critical section에 접근 가능하도록 하는 방법이다.

 

Semaphore S

• 정수변수다.
• 원자적 연산인 wait() (-> like lock)와 signal() (-> like unlock) 함수로만 접근 가능하다.
• 원자적 연산 -> 한 스레드가 세마포 값을 변경시, 다른 어떤 스레드도 동시에 동일한 세마포 값을 변경할 수 없다.

 

세마포어 사용법 (Semaphore Usage)

• 카운팅 세마포어 (Countingsemaphore)
  • 변수 S가 범위 제한 없이 값을 갖는다.
• 이진 세마포어 (Binary semaphore)
  • 변수 S가 0과 1 사이의 값만 가질 수 있다.
  • mutex lock과 유사하게 동작한다.

 

이진 세마포어와 뮤텍스 차이점

• 뮤텍스는 락을 걸은 스레드만이 임계영역을 나갈 때 락을 해제할 수 있다.
• 하지만 세마포어는 락을 걸지 않은 스레드도 signal을 사용해 락을 해제할 수 있다.

 

세마포는 유한한 개수를 가진 자원에 접근할 때 사용할 수 있다.

• 세마포는 가용한 자원의 개수로 초기화 된다.
• 자원을 사용하려는 프로세스는 세마포에 wait() 연산을 수행하고, 세마포 값은 감소한다.
• 자원을 방출할 때는 signal() 연산을 수행하고, 세마포 값은 증가하게 된다.
• 만약 세마포 값이 0이라면, 모든 자원이 사용중임을 나타내는 것이다.

 

• p.317
• 세마포 S를 대기하면서 일시 중지된 프로세스는 다른 프로세스가 signal() 연산을 실행하면 재시작되어야 한다.
• 프로세스는 wakeup() 연산에 의해 재시작되는데 이것은 프로세스 상태를 대기상태에서 준비 완료 상태로 변경한다.
  그리고 프로세스는 준비 완료 큐에 넣어진다.

 

ex)
공중 화장실을 생각해보자. 화장실 칸이 3개라면 동시에 3명이 사용할 수 있다.
이 경우, 세마포 변수 값이 3으로 초기화된다.

 

세마포 구현 (Semaphore Implementation)

typedef struct{
    int value;
    struct process *list;
}
 
void wait(semaphore *S){
    S->value--;
    if(S->value < 0){
    	add this process to S->list;
        sleep();
    }
}
 
void signal(semaphore *S){
    S->value++;
    if(S->value <= 0){
    	remove a process P from S->list;
        wakeup(P);
    }
}

• Spin lock은 바쁜 대기를 해야한다.
  이를 극복하기 위해 wait() signal() 연산을 위와 같이 정의할 수 있다.
• wait() : 바쁜대기 대신 프로세스는 자신을 중지 시킨다.
  위 코드에서 세마포 value가 0보다 작은 경우, 모든 자원이 사용 중이기 때문에 sleep 모드로 들어간다.
• sleep() : sleep 모드인 프로세스는 다른 프로세스가 signal 연산을 실행하면 재시작 되어야 한다.
  이 경우 프로세스는 wait -> ready 상태가 된다. -> ready queue에 넣어진다.
• 바쁜 대기의 세마포는 값이 음수가 될 수 없다.
  위 코드에선 세마포를 대기하는 프로세스 수가 많은 경우 가능하다.
  따라서 음수의 절대값은 세마포를 대기하는 프로세스의 수다.

 

모니터 (Monitors)

---

세마포나 mutex lock을 사용해도 프로그래밍 오류 또는 프로그래머에 의해 문제가 발생할 수 있다.

발생 가능한 문제

1. wait()와 signal() 연산의 순서가 뒤바뀌는 경우
   -> 여러 프로세스가 동시에 임계구역 안에서 실행될 수 있다.
2. signal(mutext)를 써야할 곳에 wait(mutext)를 쓰는 경우
   -> 프로세스는 두 번째 wait()에서 영구 봉쇄된다.
3. wait(mutext) || signal(mutex) || 둘 모두를 빠트리는 경우
   -> 상호 배제 요구 조건을 위반 || 프로세스는 영원히 봉쇄

모니터

위의 문제들을 해결하기 위한 방법으로  동기화 도구를 통합해 고급 언어 구조물을 제공한다.

 

라이브니스 (Liveness)

---

라이브니스

프로세스가 실행 생명주기 동안 진행되는 것을 보장하기 위해 시스템이 충족해야 하는 일련의 속성이다.

라이브니스 실패로 이어질 수 있는 상황

1. 교착 상태 (DeadLock)
2. 우선순위 역전