[OS/운영체제] Atomic execution과 Semaphores / Mutex

1. Atomic이란?

• Atomic의 Atom은 원자라는 뜻이며, 원자란 물질을 구성하는 더 이상 쪼개질 수 없는 가장 작은 단위를 말한다. 
• 프로그래밍에서의 Atomic한 실행이란 어떤 연산이 분할되지 않고 한번의 연산으로 실행되는 것을 의미한다.

설명에 앞서 이 글에서는 프로세스, 스레드를 합쳐서 프로세스 라고만 지칭할 것이다.

가장 대표적으로 Atomic한 연산이 필요한 곳은 Critical Section에 대한 연산이다.

멀티 프로세스 환경에서 여러개의 프로세스가 임계영역에 있는 임의의 count라는 데이터에 접근해서 연산을 할 때 프로그래밍 언어에서는 단지 count++;한줄로 끝나지만 코드가 컴파일 되면 기계어로 번역되어 아래와 같이 약 3단계로 구분된다.

count = 1이라고 가정//
move eax, [count]  //1 - 레지스터(임시 변수)에 count값을 가져온다
add eax, 1 //2 - eax의 값을 1증가시킨다
move [count], eax //3 - 증가시킨 eax값을 다시 count에 넣어준다.

우리가 보는 코드는 1줄이지만 기계는 3줄을 완료해야 count가 1 올라가는 것이다. 이 상황에서 1번과정에서 프로세스 P1이 1번 연산을 실행 후 2번 연산을 하는 동시에 P2가 1번 연산에 들어와서 count를 가져오게 되면 아직 P1이 2번 연산에서 멈췄기 때문에 count값을 증가시기키 못했으므로 P2도 count=1을 가져오게 된다. 이 과정에서 count++연산이 한번 씹히게 되면서 Critical section에서의 Race condition문제가 발생하게 된다.

이때 count++하는 과정이 하나의 프로세스가 연산을 처리하는 동안 다른 프로세스가 중복 처리하지 않도록, 즉 Atomic하게 처리한다면 Race condition문제는 발생하지 않을 것이다. 이러한 Atomic한 연산을 지원하기 위해 Semaphores와 Mutex라는 개념이 있으며 이에 대해 살펴보자

2. Semaphores(세마포어)란?

• 위의 동기화 문제를 해결하기 위해 만들어진 개념이 Semaphores이다.
• 세마포어는 추상적인 개념이며 세마포어를 구현하는 방식에는 Busy-Wait(==spin lock)방식, Block & Wake up(==sleep lock)방식 두가지가 있다.

2-1. Busy-Wait 방식의 Semaphore 연산

추상 자료형 세마포어 변수를 S라고 하고 프로세스가 할당받을 수 있는 자원의 갯수를  S=5라고 가정했을 때 아래와 같은 연산이 있다.
아래의 두 가지 연산은 atomic한 연산에 의해서만 접근 가능하다는 것을 가정한다.

1. P(S) 연산

- 공유 데이터를 획득하는 과정. 코드로 보자면 아래와 같다.(실제 세마포어를 사용하는 코드와는 다르며, 단지 이해를 돕기위한 busy-wait방식의 코드이다.)

while(S <= 0) {
    //V연산으로 자원이 반납할 때 까지 무한 대기
    /*Infinite Loop*/
}
S--; //자원을 받을 수 있으면 무한루프를 빠져나와서 자원을 가져감

P연산을 한번 했을 때 자원을 하나 가져온다 > S--;

2. V(S) 연산

공유 데이터에 대한 연산을 완료하고 자원을 반납하는 과정

프로세스가 실행을 완료하게 되면 할당받은 자원 S를 반납한다 > S++;

3. Busy & wait 방식의 문제점

Busy & wait 방식은 다른말로 Spin lock이라고도 한다. Busy-Wait 방식에서는 프로세스가 할당받을 자원(세마포어)가 없으면, 자원이 생길 때 까지 무한 대기를 한다. 무한루프를 Spin하면서 대기한다고 해서 Spin lock이라고도 하는 것이다. 프로세스는 자신이 할당받은 시간동안 자원이 안나오게 되면 그냥 Spin만 돌다가 할당 시간이 끝나면 자원을 반납하고 다시 기다려야 하기 때문에 효율적이지 못하다.

2-2. Block-Wake up 방식의 Semaphore 연산

추상 자료형 세마포어를 아래와 같이 정의한다.

typedef struct 
{
    int value;  /* Semaphore */
    struct process *Lock  /*process가 자원을 기다리는 queue*/
}semaphore;

1. P(S) 연산

S.value--; : 현재의 프로세스가 자원을 하나 가져간다
if(S.value < 0) : 현재의 프로세스가 자원을 가져가려고 했는데 할당 받을 수 있는 자원이 없다면 세마포어 구조체에서 정의한 queue에 넣어 대시시킨다.

S.value--;
if(S.value<0)
{   
    //S.L 즉, waiting queue에 넣어서 대기시킴 == block();
    block();
}

2. V(S) 연산

S.value++; : 현재 프로세스가 실행을 완료하고 자원을 반납한다.

if(S.value <= 0) : 프로세스가 실행을 완료하고 자원을 반납했음에도 불구하고 아직 0이하라는 것은 queue에 하나 이상의 프로세스가 실행 대기중이라는 의미이기 때문에 queue에서 대기중인 프로세스를 하나 깨워서 실행시킨다.

S.value++;
if(S.value <= 0)
{
    //자원을 반납했어도 S.value <= 0이라면, 아직 queue에 대기하는 애들이 있다면
    //queue에서 대기하고 있는 프로세스를 깨워서 실행시킨다.
    wakeup(P);
}

3. Busy-wait vs Block-Wake up

위의 설명을 봤으면 당연히 Block-Wake up 방식을 써야하는거 아냐? 라고 생각할 수 있다. 어떤 방식을 써야할지는 Critical section의 길이에 따라 나눌 수 있다.

Critical Section의 길이가 긴 경우 - Block & Wake up

Critical Section의 길이가 긴 경우 Busy-Wait 방식을 사용하면 다른 프로세스는 루프를 돌며 대기해야 하므로 자원낭비가 심해진다. 그러므로 queue에서 대기하는 Blcok-Wake up이 더 낫다.

Critical Section의 길이가 짧은 경우 - Busy & wait

Block & Wake up 방식이 자원 효율성이 좋긴 하지만 Block-Wake up이 Busy-Wait방식보다 오버헤드가 더 커질 수 있기 때문에 Busy & Wait방식을 사용해도 크게 상관이 없다.
사실 일반적으로는 Block & Wake up 방식이 좋다고 한다.

4. Semaphore의 종류

1. Binary semaphore

• 값이 0 or 1만을 가지는 세마포어이며 0이면 lock, 1이면 unlock을 의미한다.
• 여러개의 프로세스가 동시에 Binary semaphore를 획득 가능
• Mutex와 달리 소유권이 없기 때문에 다른 프로세스에서 lock을 해제 가능하다.

2. Mutex

• 주로 Mutual exclusion(lock/unlock)을 위해 사용한다.
• lock 상태에서는 뮤텍스를 획득한 프로세스가 임계영역에 진입하고 나머지 프로세스는 대기한다. 프로세스가 임계영역을 나오면서 뮤텍스를 해제하면 뮤텍스가 Unlock 상태로 변경되고 다른 프로세스가 다시 임계영역에 진입할 수 있는 상태가 된다.
• 한번에 한 프로세스 만이 뮤텍스를 소유할 수 있으며, 오직 뮤텍스를 가진 프로세스만이 뮤텍스를 해제 가능하다.

3. Counting semaphore

• 주로 사용 가능한 자원의 갯수를 나타낼 때 사용하는 세마포어이다.
• Block & Wake up 방식에서 사용하는 세마포어이다.
• 0초과면 사용할 자원이 있고 0이하면  대기중인 프로세스가 존재함을 나타낸다.

CS 지식을 공부하고 기록하는 개인 공부 블로그입니다.
내용 중 틀린 부분 피드백 혹은 궁금한 점이 있으면 댓글로 남겨주시면 참고 및 답변 달아드리겠습니다🧐