[OS] 동기화 문제, Peterson's solution, 하드웨어 명령어

동기화 문제를 다룹니다. 예제를 통해 어떤 경우에 동기화 문제가 필요한지 알아보고, race condition, critical section problem, 동기화 등 용어를 정리합니다. 그리고 동기화의 조건에 대해 알아본 뒤 Peterson's solution이 어떻게 조건을 만족하는지 살펴보겠습니다. 그리고 마지막으로 atomic한 하드웨어 명령어로 얼마나 간단하게 mutual exclusion을 만족하는지 살펴보겠습니다.

목차

1. 동기화 문제, race condition, critical section problem
2. Peterson's algorithm
3. Hardward Support for Synchronization

---

1. 동기화 문제

동기화가 무엇이고, 어떻게 동기화 문제를 해결할지 알아보기 전에 어떤 상황에서 동기화가 필요한지 예제를 먼저 살펴보겠습니다.

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <pthread.h>

int count;

void *increase(void *param);
void *decrease(void *param);

int main()
{
    pthread_t tid1, tid2;
    pthread_create(&tid1, NULL, increase, NULL);
    pthread_create(&tid2, NULL, decrease, NULL);
    pthread_join(tid1, NULL);
    pthread_join(tid2, NULL);
    printf("count test result : %d\n", count);
    return 0;
}

void *increase(void *param)
{
    int i;
    for (i = 0; i< 10000; i++)
        count++;
    pthread_exit(0);
}
void *decrease(void *param)
{
    int i;
    for (i = 0; i< 10000; i++)
        count--;
    pthread_exit(0);
}

 

 두 개의 쓰레드를 생성합니다. 하나의 쓰레드는 전역변수 count를 10000번 증가시키는 작업을 하고 또 하나의 쓰레드는 10000번 감소시키는 작업을 합니다.

 

두 쓰레드가 동시에 실행돼면 같은 값을 더하고 빼기 때문에 count의 결과를 0으로 예상할 수 있습니다.

 

실행 결과

하지만 실제로 여러 번 실행시켜보면 0이 아닌 값이 빈번하게 등장하는데, 그 이유는 count++가 기계어로 번역되면 아래와 같이 3줄에 걸쳐서 실행되고, 그 한 줄 한 줄 사이에 context switching이 일어나기 때문입니다.

 

$register_{1} = count$

$register_{1} = register_{1} + 1$

$count = register_{1}$

 

$register_{2} = count$

$register_{2} = register_{2} - 1$

$count = register_{2}$

 

먼저 첫번째 쓰레드에서 count 값을 레지스터에 저장합니다. 그리고 레지스터에 저장된 값을 1 증가시키고 count에 그 값을 넘겨줍니다. 그리고 두번째 쓰레드에서는 count 값을 레지스터에 저장하고, 그 값을 1 감소시키고 count에 그 값을 넘겨줍니다. 먼저 첫번째 쓰레드에서 3줄을 실행하고 context switching이 일어나서 두번째 쓰레드가 실행되면 문제는 없습니다.

 

그런데 첫번째 쓰레드에서 2번째 줄 $register_{1} = register_{1} + 1$까지 실행한 후 두번째 쓰레드로 context switching이 일어났다고 가정해봅니다.

 

초기 count 값은 0이고 $register_{1}$에 0이 저장됩니다. 그리고 $register_{1}$을 1로 증가시킵니다.

 

쓰레드2로 context switching이 일어나는데, 쓰레드는 레지스터에 값을 별도로 저장하는 것을 기억합시다.

 

그 다음 두번째 쓰레드에서 count는 아직 0이기 때문에 $register_{2}$에 0을 저장하고 -1로 감소시킵니다. 그리고 count에 -1을 복사합니다. count--을 전부 실행한 뒤에 다시 첫번째 쓰레드로 context switching이 일어납니다.

 

$register_{1}$에 아직 1이 저장돼있습니다. 1을 count에 복사하고 다시 context switching이 일어납니다.

 

이렇게 위처럼 기계어 3줄 실행 중에 context switching이 일어나면, increase()와 decrease()가 한번씩 일어났는데, count는 0이 아닌 1이 됩니다. 확률상 100번 increase()와 decrease()를 실행하면 count가 0이 아닌 경우가 드물게 나타나지만, 위처럼 10000으로 테스트하면 count가 종종 0이 아닌 값을 갖게 됩니다.

 

위와 같이 여러 프로세스가 동시에 공유 데이터에 접근하고 조작해서 그 결과가 특정 순서에 의존하게 되는 상황을 race condition이라고 합니다. race condition을 막고 데이터의 일관성 유지 위해 프로세스의 실행 순서를 조작해서 count에 한 시점에 하나의 프로세스만 접근할 수 있게 해야하는데 이를 동기화, synchronization이라고 합니다.

 

 임계구역문제 (critical section problem)

공유데이터에 접근하고 조작하는 코드를 임계 구역(critical section)이라고 합니다. 임계 구역 문제(critical section problem)은 프로세스를 잘 동기화해서 두 개 이상의 프로세스가 공유데이터에 접근하지 못하도록 프로토콜을 설계하는 것을 의미합니다. 다음 세 가지 요구 사항이 있습니다.

1. Mutual Exclusion : 어떤 프로세스가 임계 구역에 있으면, 다른 프로세스는 임계 구역을 실행할 수 없다.
2. Progress : 어떤 프로세스도 critical section에 있지 않은 상태에서 critical section에 들어가고자 하는 프로세스가 있으면 들어갈 수 있어야 한다.
3. Bounded Waiting : 프로세스가 critical section에 들어가려고 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 critical section에 들어가는 횟수에 한계가 있어야 한다. 즉 특정 프로세스 입장에서 지나치게 오래 기다리는 starvation을 막아야한다는 의미입니다.

 

임계 구역 말고도 코드를 크게 4 구역으로 나눌 수 있습니다.

while (true) {
    entry section
        critical section
    exit section
        remainder section
}

• entry section : critical section에 들어가기 위해 허가를 받는 구역입니다.
• critical section : 공유데이터에 접근하고 좆가하는 구역입니다.
• exit section : critical section에서 나왔음을 알리는 구역입니다.
• remainder section : 그 외 나머지 구역입니다.

앞으로 임계구역문제를 csp라고 줄여서 사용하겠습니다.

---

Peterson's Solution

Algorithm 1

피터슨 솔루션에 대해 설명하기 전에, 그 이전의 불완전한 알고리즘 2개를 소개하겠습니다. 피터슨 솔루션을 이해하는데 도움이 될 것입니다.

do {
    while (turn != 0):
    critical section
    turn = 1
    remainder section
} while (1);

turn의 의미

여기서 turn은 공유변수입니다. turn이 0이 아닐때는 무한대기하다가 다른 프로세스가 turn을 0으로 바꾸면 critical section에 들어갈 수 있습니다. 그리고 작업이 끝나면 critical section을 나와 turn을 1로 만들어서 다른 프로세스가 들어갈 수 있게 만들어줍니다. 즉 자신의 차례가 아닐 때는 while문에서 대기하고, critical section에서 들어갔다 나오면 turn을 상대편의 것으로 만들어 줍니다. 그리고 상대방의 입장에서 turn이 0일 때, while 문에서 기다리다가 1로 바뀌면 critical section에 들어가고 다시 turn을 0으로 만들어줍니다. mutual exclusion을 만족할 수 있는데 문제가 있습니다.

Progoress 불만족

progress 조건을 불만족합니다. 이유가 무엇일까요? 코드를 살펴보면 critical section은 반드시 교대로 들어가도록 프로그래밍 돼있습니다. critical section에 들어갔다 나와야지만 turn이 상대편이 되고 상대편이 나와야만 나의 turn이 됩니다. 이런 프로세스들이 critical section에 들어가려는 빈도가 균일하지 않을 수 있습니다. 예를 들어 어떤 프로세스 $P_{i}$가 critical section에 100번 들어가야하지만 $P_{j}$은 1번만 들어가고 싶다면  $P_{i}$는 99번 밖에 들어가지 못합니다. 왜냐하면 반드시 교대로 들어가야하기 때문입니다.

Algorithm2

이번에는 공유변수로 flag를 사용합니다. 프로세스 각각이 각자의 flag를 가지고 있습니다.

do {
    flag[i] = true;
    while (flag[j]);
    critical section
    flag[i] = false;
    remainder section
} while(1);

flag의 의미

이 알고리즘은 상대방 프로세스가 flag를 올렸는지 체크합니다. 자신이 critical section에 들어가기전에 flag를 올립니다. 그리고 상대방도 critical section에 들어가기 위해 flag를 올려두었다면 들어갈 차례를 양보하고 그냥 기다립니다. 즉 critical section에 들어가고 싶다면 flag를 올리고 표시를 한 뒤에, 상대방이 flag를 올리지 않았다면 critical section에 들어가고, 상대방이 flag를 올렸다면 상대방이 critical section에서 나올 때까지 기다립니다.

Progress 불만족

이 알고리즘은 어떤 문제가 있을까요?  $P_{i}$가 flag를 들고 CPU를 빼앗겼다고 가정합시다. 그 때  $P_{j}$이 자신도 critical section에 들어가기 위해 flag를 듭니다. 그런데 $P_{i}$ 또한 flag를 들었기 때문에 critical section에 들어가지 않고 대기합니다. 다시 $P_{i}$가 CPU를 점유해도 $P_{j}$이 깃발을 들고 있기 때문에 critical section에 들어갈 수 없습니다. 결국 critical section에 들어가기 전에 두 프로세스 모두 깃발만 들고 끊임없이 양보만 하는 상황으로 Progress에서 문제가 생깁니다.

Peterson's solution

Peterson's Solution은 전통적인 software-based의 solution입니다. 위의 위에서 소개한 두 알고리즘과는 다르게 세 가지 requirements인 exclusion, progress, bound waiting을 모두 만족합니다. 하지만 임계 영역에 들어가기 전, entry 영역에서도 context switching이 발생할 수 있기 때문에 항상 csp를 해결한다고 보장할 수는 없습니다.

 

코드를 보면서 Peterson's Solution이 어떻게 Mutual exclusion을 지킬 수 있는지 알아보겠습니다. 위 알고리즘의 turn과 flag를 이해했으면 쉽게 이해할 수 있을 것입니다.

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

동작 방식

$P_{i}$가 critical section에 들어가고자할 때 자신의 깃발을 들어서 critical section에 들어가겠다는 의사표현을 합니다. 그리고 turn을 상대방의 턴, 즉 j의 turn으로 바꿔놓습니다.

critical section에 들어가기 전에, 상대방이 flag를 들고 있고, 상대방의 turn이라면 들어가지 않고 대기합니다. 상대방이 flag를 들고 있더라도 나의 turn이라면 critical section에 들어갈 수 있습니다. 혹은 상대방의 turn이어도 깃발을 들고있지 않다면 critical section에 들어갈 수 있습니다.

 

이런식으로 프로그래밍 되면 $P_{i}$는 Algorithm1에서와 다르게 $P_{j}$가 종료돼도 계속 critical section에 들어갈 수 있습니다. $P_{j}$는 flag를 내리고 종료됐을 것이기 때문입니다.

 

그리고 $P_{i}$와  $P_{j}$ 두 프로세스가 모두 entry section에서 대기하는 일은 없어집니다. 왜냐하면 두 프로세스 모두 깃발을 든 상태이고 turn은 i혹은 j의 것이기 때문에 둘 중하나는 무조건 critical section에 들어갈 수 있어서 Algorithm2에서 문제였던 점을 해결할 수 있습니다.

---

Hardware Support for Synchronization

코드가 복잡하게 길어진 이유는 고급 언어의 문장 하나가 실행되더라도, 한 문장이 아닌 여러 CPU 명령어로 구성되고, 명령어가 실행되는 도중에 CPU를 빼앗길 수 있기 때문입니다. 그런데 하드웨어적으로 고유의 인스트럭션이 지원되는 경우가 있습니다. 앞에서 발생한 문제는 데이터를 읽고 쓰는 것을 하나의 명령어로 처리할 수 없었기 떄문에 발생한 문제입니다. 데이터를 메모리에서 동시에 읽고 쓰는 것을 한 번의 명령어로 처리할 수 있으면, 하나의 명령어를 실행하는 중에 CPU를 빼앗길 일이 없어질 것입니다.

test_and_set

lock을 읽는 것과 lock을 1로 바꾸는 작업을 하나의 명령어로 만듭니다. 예를 들어 lock이 0이었다면 lock이 0인 것을 읽고 lock을 1로 바꿉니다. 그런데 만약 원래 lock이 1이었다면 1로 읽고 그대로 1로 세팅합니다. 이것을 atomic하게 하나의 명령어로 지원하는 것입니다.

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

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

위의 Peterson solution처럼 소프트웨어를 복잡하게 만들 이유가 없어집니다.

 

 

lock이 0인 경우를 생각해봅시다. 어떤 프로세스도 critical section에 들어가 있지 않다는 것을 의미합니다. 값을 읽을 때 while에서 lock이 0이기 때문에 critical section에 들어가고 동시에 lock이 1로 바뀝니다. 즉 다른 프로세스는 critical section에 들어올 수 없어진 것을 의미합니다.

 

이제 lock이 1로 바뀌고 다른 프로세스 입장에서 다시 살펴봅시다. Test_and_Set에서 lock이 1로 읽히고 while문에서 계속 대기하게 됩니다.

compare_and_swap

test_and_set과 마찬가지로 동시에 lock을 읽고 쓰는 일을 하지만 동작 과정이 조금 다릅니다. 코드로 살펴보겠습니다.

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));
    critical section
    lock = 0;
}

 

첫번째 인자 value가 두번째 인자 expected와 같은 값이라면  첫번째 인자 value를 new_value로 바꿔줍니다. 그리고 바꾸기 전의 원래 value를 반환합니다.

 

lock이 0이라면, 즉 lock이 걸려있지 않다면 어떻게 동작할까요? lock이 기대값 0과 같으니 lock을 1로 바꿔줍니다. 다른 프로세스가 critical section에 들어오지 못하게 lock을 거는 것입니다.  그리고 기존 값 0을 반환하고 즉시 critical section으로 들어갑니다.

 

다른 프로세스가 들어가고자 한다면, lock이 1로 바뀐 상태기 때문에 compare_and_swap에서 1을 반환하고 while문에서 기존의 프로세스가 critical section에서 나올 때까지 대기합니다.

---

다음 포스팅에서는 뮤텍스와 세마포어 모니터에 대해 알아보겠습니다.

Reference

1. 반효경 교수님 KOCW 운영체제 강의

2. Operating System Concepths, TENTH EDITION