[운영체제(OS)] 프로세스 동기화 - (2) Critical Section 처리

0.🚶들어가며

이전 글에서는 동기화란 무엇인지, 동기화와 관련된 개념인 경쟁 조건과 임계 영역에 대해 알아보았습니다.

 

이번 글에서는 Critical Section에서 생길 수 있는 문제를 어떤 방법으로 해결하는지에 대해 알아보도록 하겠습니다.

 

기본적으로 Critical Section 처리는 다음과 같은 구조를 가지고 있습니다.

Critical Section을 entry section과 exit section으로 감싸고 입구(entry)에서는 다른 프로세스가 들어오지 못하도록 Lock을 출구(exit)에서는 Unlock을 해주는 방식입니다. 이러한 구조를 구현하는 방식은 다양한데 이에 대해 알아보도록 하겠습니다.

---

1.😀Low-Level Synchronization (Busy Waiting)

1) 소프트 웨어적 해결법

소프트웨어적 해결법은 위에서 살펴본 임계 구역 처리를 코드만을 사용해 구현하는 방식입니다. 이에 대한 시도는 여러 가지가 있는데 세 가지 정도를 알아보면서 어떤 방식으로 구현했는지, 어떤 점이 문제점인지 등에 대해 살펴보겠습니다.

 

첫 번째 방법

위 사진을 천천히 살펴보겠습니다. 간단한 상황 가정을 위해 P0, P1 두 프로세스가 있다고 해보겠습니다. 두 프로세스는 Critical section에 서로 접근하려는 프로세스입니다. 이때 Synchronization variable이라는 공유 변수(turn)를 두고 lock 역할을 수행시킵니다. 즉, turn이 자신에게 올 때 critical section을 사용한 뒤 상대방 turn으로 바꿔주는 방식이죠. 

 

이 정도만 살펴보면 lock, unlock 기능도 충실히 있고 잘 작동할 것으로 보이나 이 알고리즘에는 문제가 있습니다. 우선 지난 글에서 말한 임계 영역 처리 방법 3가지 조건 중 Progress를 만족 시키지 못합니다. 즉, P0가 turn을 반납하고 또 사용하려면 P1이 turn을 반납해야만 합니다. 만약 P1이 turn을 사용하지 않는다면 계속 P0는 대기해야 하는 것이죠. 번갈아가면서 사용해야만 하는 제약 조건이 생기는 것입니다.

 

두 번째 방법

위 방법보다 조금 더 발전된 방식을 알아봅시다. 이번에는 공유 변수로써 flag 배열을 사용하네요! 즉 자신이 critical section에 들어가려하면 flag를 true로 바꾸고 진입하는 것입니다. 이때 다른 flag도 true인 게 있다면 계속 대기하게 되는 구조입니다.

 

이 알고리즘에서도 문제점이 발견됩니다. 만약 flag[i] = true로 바꾼 순간 CPU를 빼앗겼다고 가정해봅시다. 그렇다면 다음 프로세스도 flag [j]를 true로 바꿀 것이고 이때 flag 두 개가 서로 동시에 들려있는 상황이라 끊임없이 양보하는 상황이 발생합니다. 따라서 이 알고리즘 역시 Mutual Exclusion은 만족하나 서로 끊임없이 양보하는 상황이 발생하여 critical section에 진입하지 못하는 상황이 발생합니다. 

 

Peterson's Algorithm

이제 마지막으로 Peterson's Algorithm에 대해 알아보겠습니다. Peterson's Algorithm의 경우 Critical section 처리 방법의 세 가지 조건을 모두 만족합니다. 위에서 살펴본 알고리즘들의 공유 변수 두 가지를 모두 사용하는 방식이죠. 즉, flag와 turn 개념을 모두 사용합니다. 해당 알고리즘을 사용하면 동기화 처리 문제를 해결할 수 있게 되는 것이죠.

 

다 해결된 것 같지만 여기에도 문제가 조금 있습니다,, 조건 세가지를 모두 만족시키기는 했으나 코드를 보면 while문을 계속 돌게 됩니다. while문의 조건은 프로세스가 계속 CPU를 잡고 있는다고 해결되지 않는 문제입니다. 따라서 이는 CPU 낭비 상황입니다. 이러한 상황을 Busy Waiting이라 합니다.

 

2) 하드웨어적 해결법

소프트웨어적으로 해결하는 방법이 복잡했던 이유는 모두 atomic한 상황을 구현하지 못해서라고 할 수 있습니다. CPU preempt에 의해 한꺼번에 수행해야 하는 코드를 atomic 하게 실행하지 못해서인 것이죠. 이 부분을 하드웨어의 도움을 받아 간단히 해결할 수도 있습니다. 아래 사진을 한 번 살펴봅시다.  

 

Test_and_Set(lock)를 통해 프로세스가 진입할 수 있는지 여부와 함께 lock 기능까지 atomic하게 실행시켜줄 수 있는 기능을 제공해줍니다. 이를 통해 복잡한 알고리즘 없이도 Critical Section 처리를 할 수 있게 됩니다. 하지만 이 방법 역시 Busy Waiting을 하여 CPU 낭비가 발생하고 있습니다.  

---

 

지금부터 알아볼 방식은 Busy Waiting이 필요없는 High-Level Synchronization입니다. High-Level Synchronization 방식은 임계 영역에 진입이 불가능한 프로세스가 Busy Waiting을 하지않고 대기 큐에서 기다리는 방식입니다. 이러한 방법으로 CPU낭비를 줄이는 것이죠.

 

세마포어와 모니터 방식에 대해 알아보도록 하겠습니다.

2.🚩세마포어(Semaphore)

세마포어(Semaphore)는 다익스트라가 고안한 두 개의 원자적 함수로 조작되는 정수 변수로서, 멀티프로그래밍 환경에서 공유 자원에 대한 접근을 제한하는 방법으로 사용됩니다.

 

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

 

Counting semaphore는 2 이상의 정수 값을 가질 수 있는 세마포어입니다. 이때 정수 값은 사용 가능한 자원의 수입니다. Counting semaphore가 0보다 클 때는 임계 영역에 진입할 수 있고, 0 이하라면 누군가 wakeup 함수를 통해 counting semaphore값을 증가시킬 때까지 프로세스는 대기(block() 호출)하게 됩니다.

 

Binary semaphore는 0과 1만 값으로 가질 수 있는 세마포어입니다. 뮤텍스(mutex)라고도 하죠. 즉, 하나의 프로세스만 임계 영역에 입장할 수 있습니다.

 

위 사진은 두 개의 원자적 함수 P와 V를 사용하여 세마포어를 어떻게 사용하는지 보여줍니다.

S.value는 세마포어 값, P는 임계 구역 진입 함수, V는 임계 구역을 나가는 함수입니다.

 

P(S)를 보면 세마포어 값을 하나 낮추고 if문에서 자원이 남아 있는지를 체크합니다. 만약 자원이 남아있지 않다면 block()을 걸게 되죠. 

 

V(S)를 보면 임계 구역을 나가는 함수이므로 V(S)를 실행시키면 세마포어 값을 하나 올려주고 조건에 따라서 대기 중인 프로세스를 wake up 시킵니다.

---

3.💬모니터

위에서 살펴본 세마포어는 몇 가지 문제점이 있습니다.

위 사진과 같이 세마포어를 구성하면 데드락 문제가 생기며, 전적으로 개발자에게 임계 영역 처리를 맡기기 때문에 잘못된 사용을 초래할 수 있습니다. 이러한 잘못된 사용은 시스템 전체에 치명적인 문제를 유발할 수 있고 문제의 원인 파악을 쉽지 않게 합니다.

 

또한 공유 자원을 사용할 때 모든 프로세스가 세마포어 알고리즘을 따른다면 굳이 P, V 함수를 사용하지 않고 자동으로 처리할 수 없을까에 대한 고민을 하게 됩니다.

 

이러한 상황 속에서 탄생한 것이 모니터입니다. 모니터는 세마포어보다 좀 더 고수준의 동기화 기능을 제공합니다. 공유 자원을 내부적으로 숨기고 공유 자원에 접근하기 위한 인터페이스만 제공함으로써 자원을 보호하고 프로세스 간에 동기화를 시켜주죠. 뭔가 시스템 콜과 비슷한 냄새가 나기도 합니다.

 

위 사진을 살펴보면 모니터는 공유 자원과 공유 자원 접근 함수로 이루어져 있습니다. 또한 모니터 내부에는 한 번에 한 프로세스만 들어올 수 있습니다.

 

위와 같은 모니터의 도움을 받아 프로그래머는 직접 Lock을 관리하지 않고도 임계 영역을 처리할 수 있게 됩니다.

---

4.💨나가며

이번 글에서는 Critical Section 처리에 대한 다양한 방법을 알아보았습니다. 세마포어와 모니터의 경우 추후 조금 더 내부적인 구현을 알아보는 시간을 가진다면 임계 구역 처리에 대한 이해를 높일 수 있을 것 같습니다.