[운영체제/OS] 동기화 이슈 처리하기 - (2)

💡 1. High-level Synchronization ?

예전 포스팅에서 Software-only solution(피터슨 알고리즘)과 Hardware Atomic solution(Test-and-Set, Swap)으로 동기화 이슈를 처리하는 방법에 대해 공부해봤는데요.

 

* 해당 부분에 대한 포스팅이 궁금하신 분은 아래 링크에서 확인해주세요.

[운영체제/OS] 동기화 이슈 처리하기 - (1)

두 방법 모두 결정적으로 Spinlock으로 인한 리소스의 낭비가 심하기 때문에 효율적이지 않았습니다.

 

따라서 이번 글에서는 위 방법들보다 조금 더 고차원적인 방법에 대해 알아보려고 합니다. 이 방식들은 크게 두 가지를 목표로 합니다.

• Block waiting processes - Busy Waiting(Spinlock)과 달리 기다리고 있는 프로세스가 사용 가능한 상태로 존재하게 만든다.
• Critical Section안에 들어가도 Interrupts가 가능하게 되어 중요한 Interrupt에 대해 반응할 수 있게 한다.

 

그럼, 먼저 '세마포어'에 대해 살펴보겠습니다.

 

📒 2. 세마포어(Semaphore)

세마포어(Semaphore)는 다익스트라가 고안한 두 개의 원자적 함수로 조작되는 정수 변수로서, 동기화 이슈를 처리하는 데 사용되는 방법입니다. 

 

이 세마포어를 활용하는 방식은 크게 두 가지 방식이 있는데요.

 

Binary semaphore는 mutex를 이용해서 무조건 하나의 쓰레드/프로세스만 CS(Critical Section)에 입장할 수 있게 합니다. 따라서 counter값은 처음에 1로 설정됩니다.

 

Counting semphore는 2이상의 정수값을 가질 수 있는 세마포어입니다. Counting semaphore는 시스템에서 사용할 수 있는 리소스의 수로 초기화되며, counting semaphore가 0보다 클 때 CS에 진입할 수 있고, 0이면 프로세스가 signal 함수를 통해 counting semaphore값을 증가시킬 때까지 프로세스는 대기하게 됩니다.

 

wait(S) : while S <= 0 do no-ops;
    S:= S-1;
Signal(S): S:= S+1;

/// Critical Section using semaphore
repeat
    wait(mutex)             // var mutex: semaphore, initially mutex = 1
        critical section
    signal(mutex);
        remainder section
until false;

위 코드에서 wait()를 통해 세마포어 S가 open될 때까지 다른 프로세스들은 block됩니다. 

 

처음에 세마포어 값은 1이기 때문에 프로세스는 CS에 접근할 수 있고 세마포어 값에 1을 빼서 0으로 만들죠. 그러면 다른 프로세스들은 세마포어 값이 0이기 때문에 block이 되는 것입니다.

 

하지만 위 코드에서는 아직 다른 프로세스들에 대한 block이 제대로 걸리지 않았다는 것을 알 수 있는데요.

while S<=0 do no-op;

 

위에서 S가 0이 되면 계속 while문 안에 갇혀있기 때문에 spinlock과 비슷한 상태가 됩니다. 따라서 세마포어는 mutex값과 함께 기다리고 있는 프로세스들에 대해서 List를 만들어 주어야 합니다. 아래 코드를 보겠습니다.

wait(S): 
    S.value := S.value -1;
    if S.value < 0:
        then begin
            add this process to S.L;
            block;
            end;
signal(S):
    S.value := S.value + 1
    if S.value <= 0:
        then bigin
            remove a process P from S.L;
            wakeUp(P);
            end;

만약 프로세스가 세마포어 S를 기다리게 되면 block되고 세마포어의 대기 Queue에 들어가게 됩니다.

 

그리고 안에서 작업하던 녀석이 끝나면 signal operation을 통해 대기 큐에 있던 프로세스를 빼주게 됩니다. 이런 방식을 통해 세마포어는 Block에 의한 Spinlock을 방지할 수 있게 됩니다. 또한, 이를 이용하면 세마포어는 아래와 같이 작업의 순서를 정해주는 용도로도 사용될 수 있습니다.

 

만약 A 작업을 Pi가 수행한 후에 B작업을 Pj 프로세스가 수행하게 하려고 한다고 생각해보겠습니다.

세마포어를 통한 작업 순서 결정

위처럼 작업 순서를 구성하고, 세마포어값을 처음에 0으로 설정하면 Pj가 아무리 빨리와도 flag값은 0이기 때문에 기다리게 됩니다. 그래서 Pi가 먼저 A 작업을 할 수 있도록 만들어주죠.

 

하지만 mutex, semaphore를 사용하여 프로세스를 block 시킬 때는 데드락(Deadlock) 문제가 생길 수 있습니다. 아래 그림을 볼까요?

세마포어에 의한 데드락(Deadlock)

S와 Q라는 두개의 세마포어를 이용해서 서로 상대방의 작업이 끝나고 자신의 작업을 하려는 프로세스를 관리한다고 해보겠습니다.

 

그러면 P0 입장에서는 P1이 자신에게 signal(S)를 보내주기를 기다리는데 P1입장에서는 P0가 자신에게 Signal(Q)를 보내주기를 기다리게 됩니다.

 

그러면 두 프로세스가 Lock에 갇혀서 빠져나오지 못하는 상황이 되는 것이죠.

 

 

 

2) Critical Region

위에서 세마포어의 종류를 봤을 때 Counting semaphore가 있었습니다. 이 말은 CS에 1개 이상의 프로세스나 쓰레드가 들어갈 수 있다는 뜻인데요.

 

그러면 만약에 거기서 프로세스나 쓰레드들이 공유된 자원을 같이 쓰려고 하면 또 다시 동기화 문제가 생기지 않을까요?

 

따라서 이 때 Critical Region은 공유되는 자원에 대해서 region 키워드를 통해서 누가 이걸 쓰고 있나?를 확인하게 해줍니다.

 

이전에 봤던 Producer, consumber의 예제를 다시 보겠습니다.

// Producer
region buffer when count < n
    do begin
        pool[in] := nextp;
        in := in + 1 mod n;
        count := count + 1;
    end;

// Consumer
region buffer when count > 0
    do begin
        nextc := pool[out];
        out := out + 1 mod n;
        count := count - 1;
    end;

코드를 보면 region 키워드를 통해서 공유되고 있는 buffer라는 자원을 지금 누가 있고 있는지를 먼저 확인해주고 있습니다.

 

 

📒 3. 모니터(Monitor)

모니터는 한번에 한 명만 들어올 수 있는 방이라고 이해할 수 있습니다. 모니터는 위에서 배운 세마포어보다 좀 더 고수준의 동기화 기능을 제공하는데요.

 

모니터는 공유 자원 + 공유 자원 접근함수로 이루어져 있고, 2개의 큐를 가지고 있습니다. 각각 Mutual Exclusion(상호배타) Queue, Conditional Synchronization(조건동기) Queue라고 하죠.

 

상호배타 큐는 말그대로 공유 자원에 하나의 프로세스만 진입하도록 하기 위한 큐이며, 프로세스가 모니터를 수행하다가 어떤 condition을 만족하지 못하면 Condition queue에서 기다리게 됩니다.

 

한편, wait(c) operation은 모니터의 Lock을 Release해줌으로써 다른 프로세스가 모니터로 들어올 수 있게 하며 signal(c) operation을 통해 wait하고 있는 프로세스를 깨울 수 있습니다. 만약 waiting process가 없으면 signal은 사라집니다.

 

다만, 어느 상황에서든 이미 공유자원을 사용하고 있는 프로세스가 해당 구역을 나가야만 비로소 큐에 있던 프로세스가 실행될 수 있습니다.

Monitor

Producer, consumber 예제에서 쓴 Bounded buffer를 Monitor로 구현해보면 아래와 같습니다.

Monitor bounded_buffer{
    buffer resources[N];
    condition not_full, not_empty;  // condition variable

    procedure add_entry(resource x){
        while (array "resource" is full){       // resource가 꽉 차있으면
            wait(not_full);                     // resource가 꽉 차있지 않을 때까지 wait!
        }
        add "x" to array "resource";
        signal(not_empty);                      // resource에 add를 했으니까 뺄 수도 있겠지? not_empty signal 보내!
    }
    
    procedure remove_entry(resource *x){
        while (array "resource" is empty){       // resource가 비어 있으면
            wait(not_empty);                    // resource가 채워질 때까지 wait! 위에서 not_empty signal 보내면 깨어남!
        }   
        *x = get resources from array "resources";
        signal(not_full)                        // resource에서 pop했으니까 자리가 비었겠지? not_full signal 보내!
    }

---

이렇게 이번 시간에는 세마포어와 모니터에 대해 공부를 해보았는데요. 다시 정리를 하면서도 내용이 헷갈리고 좀 어려운 것 같습니다.

 

좀 더 구체적인 코드와 예제를 가지고 이 부분은 좀 보완해야겠습니다.

 

감사합니다!