공룡책과 함께 OS를 배워보자 6일차 - 동기화 도구

본 포스트는 공룡책이라 불리는 Abraham Silberschatz, Peter B. Galvin, Greg Gagne의 『Operating System Concept 10th』 을 바탕으로 작성하였습니다.

 

 

Ch 6. Synchronization Tools

---

협력적 프로세스란 시스템 내에서 실행 중인 다른 프로세스의 실행에 영향을 주거나 영향을 받는 프로세스이다.

협력적 프로세스는 논리 주소 공간(코드 및 데이터)을 직접 공유하거나, 공유 메모리 또는 메시지 전달을 통해서만 데이터를 공유할 수 있다.

이번 챕터에서는 협력적 프로세스들의 질서 있는 실행을 보장하여, 데이터의 일관성을 유지하는 다양한 메커니즘을 논의한다.

 

 

6.1 배경

---

이미 우리는 프로세스가 병렬로 실행될 수 있다는 것을 배웠다. (비동기)
하지만, 병렬로 실행될 때 여러 프로세스가 공유하는 데이터의 무결성에는 문제점이 생길 수 있다.

 

생산자-소비자 문제를 생각해보자. 여기서 프로세스들 사이의 메모리 공유는 유한 버퍼를 이용해 구현한다.

버퍼에 새 항목을 추가할 때마다 count라는 변수 값을 증가시키고, 버퍼에서 한 항목을 꺼낼 때마다 count 값을 감소시킨다.

 

1) 생산자를 위한 코드

while(true){
	while(count == bufferSize) //do nothing
    
    buffer[in] = next_produced;
    in = (in + 1) % bufferSize;
    count++;
}

 

2) 소비자를 위한 코드

while(true){
	while(count == 0) //do nothing
    
    next_consumed = buffer[out];
    out = (out + 1) % bufferSize;
    count--;
}

 

위 두 가지 코드들은 개별적으로는 올바르지만, 병행적으로 수행시키면 올바르게 동작하지 않는다.

예를 들어 count의 현재 값은 5이고 생산자와 소비자는 "count++", count--"를 병행하게 실행한다면,

이 두 가지의 명령이 수행되는 중 count값은 (4, 5, 6) 중 하나가 돼버린다. 반드시 count는 5 여야 한다.

 

이런 부정확한 상태에 도달하는 것은 두 개의 프로세스가 동시에 변수 count를 조작하도록 허용했기 때문이다.

 

이처럼 여러 개의 프로세스가 동일한 자료를 접근하여 조작하고, 그 실행 결과가 접근이 발생한 특정 순서에 의존하는 상황을 경쟁 상황(race condition)이라고 한다.

 

이를 방지하기 위해, 우리는 한순간에 하나의 프로세스만이 변수 count를 조작하도록 보장해야 한다. 이러한 보장을 위해, 우리는 어떤 형태로든 프로세스들이 동기화되도록 할 필요가 있다.

 

* 동기화란? 시스템을 동시에 작동시키기 위해 여러 사건들을 조화시키는 것

 

 

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

---

n 개의 프로세스 {P0, P1, ..., Pn-1} 이 있는 시스템이 있다. 각 프로세스는 임계구역이라고 부르는 코드 부분을 포함하고 있고, 그 안에서는 적어도 하나 이상의 다른 프로세스와 공유하는 데이터에 접근하고 갱신할 수 있다.

 

중요한 특징은 한 프로세스가 자신의 임계구역에서 수행하는 동안에는 다른 프로세스들은 그들의 임계구역에 들어갈 수 없다는 사실이다.

임계구역 문제는 프로세스들이 데이터를 협력적으로 공유하기 위하여 자신들의 활동을 동기화할 때 사용할 수 있는 프로토콜을 설계하는 것이다. 

각 프로세스는 자신의 임계구역으로 진입하려면 진입 허가를 요청해야 한다. 이러한 요청을 구현하는 코드 부분을 진입 구역(entry section)이라고 부른다. 임계구역 뒤에는 퇴출 구역(exit section)이 따라올 수 있다. 또한 나머지 부분들은 나머지 구역(remainder section)이라고 부른다.

 

임계구역 문제에 대한 해결안은 다음 세 가지 요구 조건을 충족해야 한다.

 

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

 

운영체제 내에서 임계구역을 다루기 위해서 선점형 커널과 비선점형 커널의 두 가지 일반적인 접근법이 사용된다.

 

선점형 커널은 프로세스가 커널 모드에서 수행되는 동안 선점되는 것을 허용한다.

* 참고 - 선점 스케줄링이란?

프로세스가 CPU를 할당받아 실행하고 있을 때 우선순위가 높은 다른 프로세스가 CPU를 강제로 빼앗아 사용할 수 있는 스케줄링 기법

 

비선점형 커널은 커널 모드에서 수행되는 프로세스의 선점을 허용하지 않고, 커널 모드 프로세스는 커널을 빠져나가거나 봉쇄될 때까지 계속 수행된다.

 

일반적으로 선호되는 것은 선점형 커널인데, 이유는 프로세스가 오랫동안 실행할 위험이 적고, 실시간 프로세스에 적합하기 때문이다.

 

 

6.3 Peterson's Solution

---

임계 구역 문제를 해결하는 고전적인 소프트웨어 기반 해결책으로 Peterson's Solution이 있다.

이 해결안은 좋은 알고리즘적 설명을 제공하고 상호 배제, 진행, 한정된 대기의 요구 조건을 중점으로 다루는 소프트웨어를 설계하는 데 필요한 복잡성을 잘 설명하기 때문에 좋다.

 

Peterson's Solution은 임계구역과 나머지 구역을 번갈아 가며 실행하는 두 개의 프로세스로 한정된다.

(프로세스는 P(0), P(1)로 번호를 매긴다.)

Peterson's Solution은 두 프로세스가 두 개의 데이터 항목을 공유하도록 하여 해결한다.

 

int turn;
boolean flag[2];

 

변수 turn은 임계구역으로 진입할 순번을 나타낸다. 만약 turn ==  i 이면 프로세스 P(i)가 임계구역에서 실행될 수 있다.

flag 배열은 프로세스가 임계구역으로 진입할 준비가 되었다는 것을 나타낸다.

만약 flag[1] = true 라면 P(1)은 임계구역으로 진입할 준비가 되었다는 것이다.

 

임계 구역으로 진입하기 위해서는 P(i)는 먼저, flag[i]를 true로 만들고 turn을 j로 지정한다.

이렇게 함으로써, 프로세스 j가 임계 구역으로 진입하기를 원한다면 진입 가능하다는 것을 보장한다.

 

 

* Peterson의 해결안에서 프로세스 P(i)의 구조

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

 

Peterson's Solution이 올바르게 동작한다는 것을 증명하기 위해 다음 3가지 조건을 만족해야 한다.

 

1) 상호 배제가 제대로 지켜진다는 사실

 

• 프로세스 P(i)가 반드시 flag[j] == false 이거나, turn == i 라면 1번은 항상 만족하게 된다. (정의에 의해서)
• 만약 flag[0], flag[1]이 모두 true라고 하더라도, turn 값에 따라 임계 구역에 한 프로세스만 진입 가능하므로 위 코드의 while문을 두 프로세스가 모두 통과할 수 없다.
• 또한 정해진 프로세스가 임계 구역에 있을 동안 flag와 turn 값이 변경되지 않으므로, 상호 배제 조건은 지켜진다.

 

2) 진행에 대한 요구 조건을 만족한다는 사실(progress)

3) 대기 시간이 한없이 길어지지 않는다는 사실(bounded waiting)

 

2, 3번은 동시에 증명 가능하다.

 

• P(j)가 임계 구역에 들어갈 준비가 안되어 있을 때 flag[j]는 false일 것이고, P(i)는 임계 구역에 진입할 수 있다.
• P(j)의 flag[j]가 true일 때는 turn의 값에 따라 P(i) 또는 P(j)가 자신의 임계 구역에 진입하게 될 것이다.
• 위 코드 상 while문 실행 도중에 turn 값을 바꾸지 않기 때문에 P(i)는 P(j)가 지난번에 진입했다면 이번에는 자기도 한번은 들어갈 수 있게 보장(progress) 된다.

 

사실 Peterson's Solution은 최신 컴퓨터 아키텍처에서 작동한다고 보장되지 않는다. 시스템 성능을 향상하기 위해 프로세서가 종속성이 없는 읽기 및 쓰기 작업을 재정렬 할 수 있기 때문이다.

 

 

 

 

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

---

지금까지는 소프트웨어 기반 해결책을 설명하였다. 하지만 소프트웨어 기반 해결책은 최신 컴퓨터 기반 아키텍처에서 작동하지 않을 수 있다. 이 절에서는 임계구역 문제를 해결하기 위한 지원을 제공하는 세 가지 하드웨어 명령어를 제시한다.

 

 

* 메모리 장벽

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

일반적으로 메모리 모델은 두 가지 중 하나에 속한다.

 

1. 강한 순서 : 한 프로세서의 메모리 변경 결과가 다른 모든 프로세서에 즉시 보임
2. 약한 순서 : 한 프로세서의 메모리 변경 결과가 다른 프로세서에 즉시 보이지 않음.

하지만 메모리 모델은 프로세서 유형에 따라 다르므로 개발자는 어떤 가정도 할 수 없다.

 

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

이러한 명령어를 메모리 장벽(memory barriers)이라고 한다.

 

 

* 하드웨어 명령어

현대 기계들은 인터럽트 되지 않는 하나의 단위로서, 특별한 하드웨어 명령어들을 제공한다.

이들 특별한 명령어들을 사용하여 임계구역 문제를 상대적 간단하게 해결할 수 있다.

 

1) test_and_set()

 

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

 

이 명령어는 원자적(atomically)으로 실행된다는 점이 중요하다.

따라서 두 개의 test_and_set() 명령어가 각각 다른 코어에서 동시에 실행된다면, 이들은 어떤 임의의 순서로 실행될 것이다.

만약 기계가 test_and_set() 명령을 지원한다면, false로 초기화되는 Boolean 타입의 lock 변수를 선언하여 아래와 같이 상호 배체를 구현할 수 있다.

 

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

 

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;
}

 

CAS는 3개의 피연산자를 대상으로 연산을 한다.

피연산자 value는 오직 if문의 수식이 참일 때만 new value로 지정된다. 또한 어떠한 경우에도 CAS 명령어는 value의 원래 값을 반환하게 된다.

 

위 알고리즘들은 상호 배제 조건은 만족하지만, 한정된 대기(Bounded Waiting)을 만족하지 못한다.

따라서 임계 구역 요구 조건을 모두 만족시키는 또 다른 알고리즘이 있다.

 

3) compare_and_swap() 업그레이드 버전

 

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

 

초기에 waiting 배열의 원소는 false로, lock은 0으로 모두 초기화된다.

 

위 코드는 위에서 설명한 상호 배제뿐만 아니라 나머지 두 조건을 모두 만족한다.

 

• Progress : 임계 구역을 떠나는 프로세스는 lock을 false로 하거나, waiting[j]를 false로 만들어 줌으로써 어느 쪽이든 임계 구역으로 들어가고자 하는 프로세스를 진입하게 만들어준다.
• Bounded waiting : 프로세스가 임계 구역을 떠날 때, waiting 배열을 순환하며 검사한다. 자신의 순서 이후부터 차례대로 보기 때문에, 임계 구역에 들어가고자 하는 프로세스는 최대 (n-1)번만 기다리면 된다.

 

 

 

6.5 Mutex Locks

---

앞 절에서 알아본 하드웨어 기반 해결책은 응용 프로그래머가 사용할 수 없다.

대신 상위 수준 소프트웨어 도구들이 존재하는데, 그중 가장 간단한 도구가 바로 mutex 락이다.

 

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

 

대략적인 코드 구성은 다음과 같다.

 

while(true){
	// acquire lock
    critical section
    
    //release lock
    remainder section
}

 

먼저 acquire() 함수가 락을 획득하고, release() 함수가 락을 반환하는 구조이다.

Mutex 락은 available이라는 boolean 변수를 가지는데, 이 변수 값이 락의 가용 여부를 표시한다.

 

지금까지 설명한 구현 방식의 단점은 바쁜 대기(busy waiting)를 해야 한다는 것이다.

즉, 한 프로세스가 임계 구역에 있는 동안에 다른 프로세스들은 계속해서 반복문을 호출해야 한다.

이런 mutex 락 유형을 스핀락(spinlock)이라고도 한다. (회전한다는 의미)

 

하지만 프로세스들이 짧은 시간 동안만 락을 소유할 것이라 예상되면, lock을 기다리는 동안 Context switch를 전혀 할 필요가 없기 때문에 스핀락이 좋을 수도 있다. 따라서 스핀락은 멀티 프로세서 환경에서 많이 사용된다.

 

 

6.6 세마포(Semaphores)

---

세마포는 mutex lock과 유사하게 동작하지만, 각 프로세스들이 자신들의 행동을 더 정교하게 동기화할 수 있는 방법을 제공한다.

 

세마포 S는 정수 변수로서, 초기화를 제외하고는 wait()와 signal()로만 접근할 수 있다.

 

 

* 세마포 사용법

운영체제는 카운팅(counting)과 이진(binary) 세마포를 구분한다.

 

• 카운팅 세마포 : 제한 없는 영역(domain)을 갖는다.
• 이진 세마포 : 0과 1 사이의 값만 가능하다. (mutex lock과 유사하게 동작한다.)

 

카운팅 세마포는 유한한 개수를 가진 자원에 대한 접근을 제어하는 데 사용될 수 있다.

먼저 세마포는 가용한 자원의 개수로 초기화되며, 각 자원을 사용하려는 프로세스는 세마포에 wait() 연산을 수행하고, 세마포의 값은 감소한다.

자원을 방출할 때는 signal() 연산을 수행하고, 세마포는 증가하게 된다. 만약 세마포의 값이 0이면 모든 자원이 사용 중임을 나타내는 것이다.

 

 

* 세마포 구현 (Semaphore Implementation)

위에서 강조했듯, mutex 락 구현은 바쁜 대기(Busy Waiting)를 해야 했다.

이를 극복하기 위해, wailt()와 signal() 세마포 연산의 정의를 다음과 같이 변경할 수 있다.

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

 

1) wait()

 

바쁜 대기 대신 프로세스는 자신을 일시 중지시킬 수 있다.

위 코드를 보면, 세마포의 value가 0보다 작은 경우, 모든 자원이 사용 중이기 때문에 sleep 모드로 들어가는 것을 알 수 있다.

 

2) sleep()

 

sleep 모드인 프로세스는 다른 프로세스가 signal 연산을 실행하면 재시작되어야 한다.

이 경우 프로세스는 ready queue에 넣어지게 된다. (대기상태에서 준비 완료 상태로 변한다.)

 

원래 바쁜 대기를 하는 세마포의 경우 세마포의 값이 음수가 될 수 없지만, 위 코드상으로는 세마포를 대기하는 프로세스의 수가 많은 경우 가능하다. 이 경우 자연스럽게 음수 값은 세마포를 대기하고 있는 프로세스들의 수를 나타낸다.

 

 

 

6.7 모니터 (Monitor)

---

위에서는 세마포나 mutex 락을 이용하여 임계구역 문제를 해결하는 소프트웨어적 방법을 배웠다.

하지만 이런 방법 또한 프로그래머가 잘못 사용하면 다양한 오류가 발생할 수 있는데, 아래는 그에 대한 예시이다.

 

signal(mutex);
	...
    critical section
    ...
wait(mutex);

- wait()와 signal() 연산의 순서가 뒤바뀐 경우 -> 여러 프로세스가 동시에 임계구역 안에서 실행될 수 있다.

 

wait(mutex);
	...
    critical section
    ...
wait(mutex);

- signal을 사용할 곳에 잘못해서 wait를 써버린다. -> 영구 봉쇄

 

이밖에도 프로그래머에 따라 수많은 방법의 오류가 발생하게 된다.

이러한 오류를 처리하기 위한 한 가지 전략은 간단한 동기화 도구를 통합하여 고급 언어 구조물을 제공하는 것이다.

이번엔 그중 하나인 모니터(monitors) 형을 설명한다.

 

모니터에 대한 부분은 책 내용이 잘 와닿지 않아 구글링 하던 중 자바 언어로 설명이 잘 된 블로그가 있어서 링크로 대체하겠다.

만약 추후 개인적으로 정리할 수 있다면 다시 와서 수정하도록 하겠다.

 

https://velog.io/@codemcd/%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9COS-11.-%EB%AA%A8%EB%8B%88%ED%84%B0

[운영체제(OS)] 11. 모니터