[Chapter 6. 프로세스 동기화] Mutex의 SW적 / HW적 구현 (Peterson's Solution, Bakery 알고리즘 등)

* 본 글은 '운영체제(Operating System: Concepts) 9th edition'의 내용과 2021학년도 1학기에 수강한 '운영체제' 과목 강의 내용을 함께 정리하여 작성하였습니다.

 

 

공유 변수의 간섭 문제를 해결하기 위한 상호 배제 및 동기화 프로그래밍 수단으로는

뮤텍스(Mutual Exclusion, Mutex)와 세마포어(Semaphore)가 있다.

 

 

뮤텍스는 자원에 대한 접근을 동기화하기 위하여 사용되는 상호 배제 기술이다.

 

프로그램이 시작될 때 고유한 이름으로 생성되며,

프로세스 혹은 스레드는 임계 구역에 들어가기 전에 반드시 뮤텍스 lock을 얻어야 하고, 임계 구역을 빠져나올 때 반환해야 한다.

 

뮤텍스를 소프트웨어적으로 구현하는 방법과 하드웨어적으로 구현하는 방법에 대하여 알아보자.

 

 

1. 소프트웨어적 구현

 

• Peterson's Solution
• Bakery 알고리즘

 

2. 하드웨어적 구현

 

• test_and_set
• compare_and_swap
• 인터럽트 통제

 

Mutex의 SW적 구현

---

잘못된 구현의 예

// entry section
enter_mutex(lock) {
    while (lock == true);
    lock = true;
}

// critical section (임계 구역)

// exit section
exit_mutex(lock) {
    lock = false;
}

이렇게 구현했을 경우, 상호 배제가 성립되지 않는 상황이 발생한다.

 

만약 lock 변수가 false가 되어 한 프로세스가 while문을 빠져나왔지만,

lock 변수를 true로 변경시키기 전에 문맥 교환이 일어난다면 다른 프로세스가 while문을 통과되는 경우가 발생한다.

 

임계 구역의 근본적인 문제는 공유 변수 때문에 발생한 것인데,

이것을 또다시 공유 변수 lock으로 해결하려고 했기 때문에 문제가 발생하는 것이다.

 

피터슨의 해결안 (Peterson's Solution)

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

현대의 컴퓨터 구조에선 이 해결안이 제대로 실행된다는 것을 보장할 수는 없다.

 

하지만 임계 구역 문제를 해결하기 위한 좋은 알고리즘적인 설명을 제공하며,

상호 배제, 진행, 한정된 대기의 요구조건을 중점으로 다루는 소프트웨어를 설계하는 데 필요한 복잡성을 잘 설명하기에 해당 해결책을 제시한다.

 

 

Peterson's Solution은 임계 구역과 나머지 구역을 번갈아 수행하는 두 개의 프로세스(또는 스레드)로 한정된다. (프로세스 Pi, Pj)

 

두 프로세스는 두가지의 공유 변수를 가진다.

int turn; // 임계 구역에 진입할 순번 (i 또는 j)
// turn == i → 프로세스 Pi가 임계구역에서 실행될 수 있음

boolean flag[2]; // 임계 구역으로 진입할 준비가 되었는가? (true 또는 false)
// flag[i] == true → 프로세스 Pi가 임계구역으로 진입할 준비가 되었음

 

(1) 프로세스 Pi의 구조

// entry section
enter_mutex {
    flag[i] = true;
    turn = j; // 양보!
    
    // 프로세스 j가 임계 구역에 진입하기를 원한다면 j가 먼저 진입하는 것을 보장하고 기다림
    while (flag[j] && turn == j);
}

// critical section (임계 구역)

// exit section
exit_mutex {
    flag[i] = false;
}

 

(2) 프로세스 Pj의 구조

// entry section
enter_mutex {
    flag[j] = true;
    turn = i; // 양보!
    
    // 프로세스 i가 임계 구역에 진입하기를 원한다면 i가 먼저 진입하는 것을 보장하고 기다림
    while (flag[i] && turn == i);
}

// critical section (임계 구역)

// exit section
exit_mutex {
    flag[j] = false;
}

 

이 해결책이 올바르게 동작한다는 것을 증명하기 위해서는

임계 구역에 대한 요구사항 3가지가 모두 잘 지켜지는지 확인해보아야 한다.

 

1. 상호 배제가 지켜지는가?

 

2. 진행에 대한 요구 조건을 만족하는가?

(나머지 구역에서 실행 중이지 않은 프로세스들만 다음에 누가 그 임계 구역으로 진입할 수 있는 지를 결정하는 데에 참여할 수 있음)

 

3. 대기 시간이 한없이 길어지지 않는가?

 

 

(1번 증명)

프로세스 Pi와 Pj 둘 다 위 코드의 2번째 줄까지 수행하여 flag[i] == true, flag[j] == true인 상태라고 가정하자.

이 둘은 아래의 while문 때문에 동시에 임계구역에 진입할 수 없다.

 

turn 변수의 값은 i 또는 j 둘 중 하나이지, 동시에 두 값을 가질 수 없기 때문에

한 프로세스 만이 while문을 통과 & 나머지 하나는 루프에 한번 이상 더 걸렸을 것이다.

 

이에 "turn = i" 또는 "turn = j"를 먼저 수행하여 먼저 양보를 한쪽이 임계 구역이 먼저 들어가게 된다.

 

즉, 상호 배제가 지켜지는 것을 볼 수 있고

turn 변수는 프로세스 두개가 임계 구역 진입을 동시에 원하는 경우 tie-breaking의 역할을 한다고 볼 수 있다.

 

 

(2, 3번 증명)

임계구역을 빠져나갈 때 자신의 flag을 false로 되돌리는 것을 통해서

임계 구역 수행 완료 후 다른 프로세스가 임계 구역에 한 번은 진입할 수 있도록 보장하고 있다. (한정된 대기)

 

Bakery 알고리즘

위의 Peterson's Solution은 두 개의 프로세스에만 적용할 수 있는 한정된 방법이었다.

이와는 다르게 Bakery 알고리즘은 여러 개의 프로세스에 적용 가능한 소프트웨어 기반 임계구역 해결책이다.

 

 

1. 대기하는 각 프로세스는 번호표를 하나씩 뽑는다.

번호표에 적힌 숫자는 도착한 순서대로 번호가 1씩 증가한다.

 

2. 각 프로세스는 자신의 번호가 가장 작은 번호가 될 때까지 기다린다.

 

3. 자신이 발급받은 번호가 가장 작은 번호가 되었을 경우 임계 구역에 진입할 수 있다.

만약 프로세스끼리 발급 받은 숫자가 같은 경우 PID가 작은 것을 먼저 처리한다.

(number[j] < number[i]) || (number[j] == number[i] && j < i) // PID : j, i

// 아래의 코드로 간략히 표현
(number[j], j) < (number[i], i)

 

* 코드

// entry section
choosing[i] = true; // 번호를 발급받는 중임을 표시
number[i] = max(number[0], number[1], ..., number[n-1]) + 1; // 번호 발급
choosing[i] = false;

for (j = 0, j < n-1, j++) {
    while (choosing[j]); // Pj가 번호를 발급받는 동안은 wait
    
    // Pj의 번호가 자기보다 작으면 Pj가 임계 구역을 빠져나갈 때까지 wait
    while (number[j] != 0 && (number[j], j) < (number[i], i));
}

// critical section (임계 구역)

// exit section
number[i] = 0; // 번호 회수

 

Mutex의 HW적 구현

---

아래는 하드웨어에서부터 소프트웨어 기반 API를 망라한 기법을 사용한 임계 구역 문제 해결책들로, 하드웨어(CPU) 명령어들이다.

CPU 명령어 하나는 문맥 교환 없이 원소적으로 수행된다.

 

모든 해결책들은 락킹(locking) 즉, 임계 구역을 보호하기 위해서 락(lock)을 사용하는 것에 기반을 둔다.

 

test_and_set

while (test_and_set(&lock));
// critical section (임계 구역)
lock = false;

// remainder section

 

test_and_set()은 target의 값을 항상 true로 만들고, 바로 이전 값을 반환한다. (target은 lock의 포인터 변수)

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

 

프로세스 Pk가 임계구역을 빠져나가면서 lock을 false로 바꾸면

대기 중이던 프로세스 중 가장 먼저 test_and_set()을 수행시킨 단 하나의 프로세스가 딱 한 번만 0의 값을 리턴 받아

해당 프로세스가 임계 구역을 수행할 수 있게 된다.

 

 

compare_and_swap

compare_and_swap()은 swap()을 확장한 것이다.

먼저 swap에 대해 알아보자.

 

lock : 전역(공유) 변수 / key : 지역 변수

key = 1;
do {
    swap(&lock, &key);
} while (key == true);
// critical section (임계 구역)
lock = false;

// remainder section

 

swap()은 두 변수 lock과 key의 값을 교체한다.

void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

 

Pk가 임계구역을 빠져나가면서 lock을 false로 바꾸면

대기하고 있던 프로세스들 중 가장 먼저 swap()을 수행시킨 단 하나의 프로세스의 지역변수 key가 딱 한 번만 true로 설정되어

해당 프로세스는 임계 구역을 수행할 수 있게 되고, 공유변수 lock은 true로 원위치된다.

 

---

이것을 확장한 것이 compare_and_swap()이다.

while (compare_and_swap(&lock, 0, 1);
// critical section (임계 구역)
lock = false;

// remainder section

 

value는 lock의 포인터 변수이다.

void compare_and_swap(int *value, int expected, int new_value)
{
    int temp = *value;
    
    if (*value == expected)
        *value = new_value;
        
    return temp;
}

 

만약 value와 expected의 값이 같지 않다면 현재의 value 값을 반환,

같다면 value를 new_value로 설정하고 이전의 value 값을 반환한다. (compare_and_swap()은 언제나 value의 원래 값을 반환함)

 

즉, 현재 lock 변수가 0이라면 0을 반환하여 해당 프로세스는 임계 구역 수행 불가,

현재 lock 변수가 1이라면 lock을 0으로 변경한 후 1을 반환하여 해당 프로세스가 임계 구역을 수행할 수 있도록 하는 것이다.

 

인터럽트 통제 (interrupt-disable, interrupt-enable)

interrupt-disable과 interrupt-enable은 특권 명령어로, 이 둘을 통해 임계 구역 내의 문맥 교환 자체를 방지한다.

(사용자 모드에서는 사용 불가)

 

커널 내의 시스템 호출 부분과 인터럽트 처리기의 임계구역 보호를 위해서 사용한다.

 

interrupt-disable;
// critical section (임계 구역)
interrupt-enable;

// remainder seciton

 

---

 

위에서 설명한 알고리즘들은 모두 busy waiting 알고리즘이다.

한 프로세스가 임계구역을 수행하는 동안 임계 구역에 들어가기를 원하는 다른 프로세스들은 while문을 계속 돌아야 한다.

 

이런 유형의 뮤텍스 락(mutex lock)은 spinlock이라고 부른다.

(lock이 가용해지기를 기다리면서 프로세스가 계속 회전을 하고 있음)

 

단점 : 타임 슬라이스의 낭비를 초래한다.

장점 : lock을 기다리는 동안 문맥 교환을 전혀 필요로 하지 않는다. (문맥 교환의 오버헤드를 피할 수 있음)

 

따라서 상호 배제 관계에 있는 임계 구역들의 계산량이 적다면

busy waiting 방식의 lock을 사용하는 것이 효과적인 경우가 있으며, 이 때문에 커널에서 주로 활용된다.