[운영체제] 동기화(Synchronization)

패스트캠퍼스 운영체제 강의와 쉽게 배우는 운영체제 교재에 대한 TIL입니다.

 

 

멀티 프로세스나 멀티 스레드 환경에서는 여러 개의 프로세스나 스레드가 한정된 자원을 가지고 공동으로 작업할 수 있는데 이때, 문제가 발생할 수 있다.

경쟁 상태

공유 자원은 여러 프로세스나 스레드가 공동으로 이용하는 변수, 메모리, 파일 등을 말한다. 공유 자원은 공동으로 이용되기 때문에 누가 언제 데이터를 읽거나 쓰느냐에 따라 그 결과가 달라질 수 있고 이를 데이터 불일치(Data Inconsistency)라고 한다. 2개 이상의 프로세스나 스레드가 공유 자원을 병행해서 읽거나 쓰는 상황을 경쟁 상태(Race Condition)라고 한다.

 

따라서, 동기화는 경쟁 상태를 막고 데이터의 일관성(Data Consistency)을 유지하기 위해서 프로세스 간의 실행 순서를 정해주는 메커니즘이다.

 

임계 구역

임계 구역(Critical Section)은 코드 상에서 경쟁 상태가 일어날 수 있는 특정 부분을 말한다.

 

임계 구역과 관련된 전통적인 문제로 생산자-소비자 문제(Producer-Consumer Problem)가 있다.

 

 

생산자는 물건을 계속 생산해서 버퍼에 넣고 소비자는 버퍼에서 계속 물건을 가져온다. 버퍼가 비었는지 가득 찼는지 확인하기 위해 전역 변수 sum을 사용하는데, sum에는 현재 버퍼에 있는 상품의 총수가 저장된다.

 

이때, 생산자와 소비자가 서로 sum의 값에 접근해서 바꾸려 할 때 접근 순서에 대한 처리를 하지 않으면 예상치 못한 결과가 나올 수 있다. 따라서, sum의 값을 조작하려는 부분을 임계 구역이라고 지정할 수 있다.

 

임계 구역 문제 해결 방법

임계 구역 문제를 해결하는 방법은 여러 가지이다. 이때, 어떤 방법이든 다음 세 가지 조건을 만족해야 한다.

상호 배제(Mutal Exclusion)
한 프로세스/스레드가 임계 구역에 들어가면 다른 프로세스/스레드는 임계 구역에 들어갈 수 없다.

한정 대기(Bounded Waiting)
어떤 프로세스/스레드도 임계 영역에 진입하지 못하여 무한 대기 하지 않아야 한다. (기아 상태 해결)

진행의 융통성(Progress Flexibility)
임계 구역에서 작업 중인 프로세스/스레드가 없다면 언제든 들어와서 작업할 수 있어야 한다. 즉, 임계 구역이 비어있기만 하다면 한 프로세스/스레드가 다른 프로세스/스레드의 영향을 받지 않고 임계 구역에 들어와 작업할 수 있어야 한다. (교착 상태 해결)

 

임계 구역 문제를 해결하는 단순한 방법은 잠금(Lock)을 이용하는 것이다. 임계 구역에 들어가기 전에 해당 구역 진입 지점을 잠그고 임계 구역에서의 작업이 끝나면 잠금 해제(Unlock)와 동시에 동기화 신호를 보내 다른 프로세스/스레드가 들어와도 좋다는 사실을 알림으로써 임계 구역 문제를 해결할 수 있다.

 

하지만, 위에서 말했듯 상호 배제, 한정 대기, 진행의 융통성을 모두 만족하면서 해결해야 한다. 다음은 각각의 조건을 만족하지 못한 방법들이다.

 

상호 배제 조건을 충족하지 않는 경우

 

 

위의 코드는 상호 배제 조건을 충족하지 못한 잠금을 이용한 방법이다. 겉보기에는 상호 배제 조건을 충족한 것처럼 보이지만 문맥 교환 때문에 충족하지 못하게 된다. P1에서 먼저 while(lock==true)를 통과하고 lock=true를 실행하기 전에 문맥 교환이 일어났다고 생각해 보자. 이렇게 되면 아직 lock 변수가 true로 바뀌지 않았기 때문에 P2도 while(lock==true)를 통과하고 임계 구역에 들어올 수 있게 된다. 따라서 P1, P2 모두 임계 구역에 들어왔으니 상호 배제 조건을 충족하지 못하게 된다.

 

한정 대기 조건을 충족하지 않는 경우

 

 

위의 코드는 lock 변수를 프로세스 개수만큼 사용함으로써 상호 배제 조건을 충족하였다. 하지만, 효율적이지 않을뿐더러 문맥 교환 때문에 한정 대기 조건을 충족하지 못하였다.

 

P1에서 lock1=true를 실행하고 문맥 교환이 일어나서 P2로 넘어갔다고 생각해 보자. 이때, P2도 lock2=true를 실행하고 문맥 교환이 일어나서 P1으로 넘어갔다고 가정하면 P1, P2 두 프로세스 모두 각자의 while 조건문에 걸려 무한 루프에 빠져서 임계 구역에 진입하지 못한다. 따라서, 두 프로세스 모두 무한 대기를 하게 되므로 한정 대기 조건을 만족하지 못한다.

 

진행의 융통성 조건을 충족하지 않는 경우

 

 

위의 코드는 다른 두 코드와 달리 lock 변수를 boolean이 아닌 int 타입으로 선언해서 P1이 진입할 차례이면 lock=1, P2가 진입할 차례이면 lock=2를 함으로써 상호 배제, 한정 대기 조건을 충족한 방법이다.

 

하지만, 이 방법을 사용하면 한 프로세스가 연달아 임계 구역에 진입하고 싶어도 그럴 수 없다. 예를 들어, P1은 lock=2를 실행함으로써 무조건 다음 임계 구역에 진입할 프로세스는 P2임을 알린다. 즉, P1은 P2에 영향을 받아 P1이 임계 구역에 진입할 수 있는 상황임에도 임계 구역에 진입하지 못하게 될 수 있다. 이는 임계 구역이 비어있기만 한다면 어떤 프로세스/스레드도 들어올 수 있어야 한다는 진행의 융통성 조건을 충족하지 못한다. 이렇게 프로세스의 진행이 다른 프로세스로 인해 방해받는 현상을 경직된 동기화라고 한다.

 

다음은 세 가지 조건을 모두 충족하고 임계 구역 문제를 해결한 방법들이다.

 

검사와 지정(test-and-set)

 

 

상호 배제 조건이나 한정 대기 조건을 충족하지 못했던 코드들은 while(lock==true)과 lock=true가 분리되어서 문맥 교환이 일어났을 때 문제가 발생해서 각 조건들을 충족하지 못했다. 이러한 경우, 하드웨어의 도움을 받아 두 코드를 동시에 실행할 수 있게 해 줄 수 있다. 위의 그림처럼 검사와 지정 코드를 이용하면 명령어 실행 중간에 타임아웃이 걸려 임계 구역을 보호하지 못하는 문제가 발생하지 않는다. 

 

하지만, 바쁜 대기를 사용하여 검사하여 자원 낭비가 발생하기 때문에 효율적이지 못하다.

 

 

피터슨 알고리즘

 

피터슨 알고리즘의 아이디어는 간단하다. 프로세스가 자신만의 lock 변수로 임계 구역을 통과할 수 있게 하고 turn 변수로 어떤 프로세스가 현재 임계 구역에 들어왔는지 알려주는 방법이다.

 

프로세스 고유의 lock 변수를 가짐으로써 상호 배제 조건을 충족하였고, turn이라는 변수로 한정 대기 조건도 충족하였다. 하지만, 겉보기에는 turn 변수로 임계 구역에 들어올 다음 프로세스를 지정해 주는 것처럼 보여 진행의 융통성 조건을 만족시켰는가에 대한 의문이 들 수 있다.

 

while의 조건문을 자세하게 보면 의문이 풀린다. P1에서 while문에 들어가기 전에 turn=2를 함으로써 다음에는 P2가 들어올 차례인 것처럼 보인다. 하지만 while의 조건문을 보게 되면 turn==2라는 조건이 lock2==true라는 조건 뒤에 위치한다. 이는 lock2 변수의 값이 false라면 turn==2 조건의 검사는 하지 않게 된다. 즉, P2에서 lock2=true를 하지 않기 전까진 turn 변수의 값이 2라도 임계 구역에 진입할 수 있다는 것이다. 즉, P1이 임계 구역에 진입할 수 있는 상황임에도 P2에 영향을 받아 진입하지 못하게 되는 현상이 벌어지지 않는다. P2에서 lock2=true를 실행해야 비로소 P1이 임계 구역에 진입하지 못하게 된다. 따라서, turn을 이용한 조건문이 뒤에 위치함으로써 진행의 융통성 조건을 충족하는 동시에 임계 구역 진입 순서를 지정하여 임계 구역에 P1, P2가 동시에 들어오지 못하게 하여 한정 대기 조건을 충족할 수 있게 된 것이다.

 

하지만, 피터슨 알고리즘은 2개의 프로세스만 사용 가능하다는 한계가 있다. 여러 프로세스가 하나의 임계 구역을 사용하려면 공유 변수를 추가하고 코드를 변경해야 하는데 공유 변수가 늘어날수록 알고리즘의 복잡성이 증가하기 때문에 한계가 있다.

 

 

데커 알고리즘

 

데커 알고리즘의 아이디어는 피터슨 알고리즘의 아이디어와 비슷하다. 임계 구역에 진입하기 위한 프로세스 고유의 lock 변수가 존재하고 turn 변수를 사용하여 현재 어떤 프로세스가 임계 구역에 접근해야 하는지 지정할 수 있다.

 

하지만, 피터슨 알고리즘과 마찬가지로 프로세스가 늘어나면 변수도 늘어나고 전체 알고리즘도 복잡해지는 단점이 존재한다.

 

임계 구역 보호를 위한 소프트웨어적 도구

임계 구역을 보호하기 위해서 하드웨어의 도움을 받거나 특정 알고리즘을 사용하는 것은 자원을 낭비하거나 복잡하다는 단점이 존재한다. 따라서, 이를 소프트웨어적으로 해결하고 사용자의 편리성을 위한 소프트웨어 도구들이 존재한다.

 

뮤텍스(Mutex)

이 책에는 뮤텍스에 대한 설명뿐만 아니라 언급조차 없다. 뮤텍스는 위에서 설명하였던 Locking 메커니즘을 사용해서 짜인 알고리즘들을 소프트웨어적 도구로 제공한 것이다. 자세한 설명은 링크를 참조하길 바란다.

 

[Programming/C] Mutex (상호배제, 상호배타)

 

세마포어(Semaphore)

세마포어의 동작은 프로세스/스레드가 임계 구역에 진입하기 전에 스위치를 사용 중으로 놓고 임계 구역으로 들어가는 것으로 비유해서 설명할 수 있다. 이때, 다른 프로세스/스레드는 앞의 프로세스/스레드가 작업을 마칠 때까지 기다리게 되는데 앞의 프로세스/스레드가 작업을 마치면 세마포어는 다음 프로세스/스레드에 임계 구역을 사용하라는 동기화 신호를 보낸다. 따라서 세마포어는 다른 해결 방법들처럼 임계 구역이 잠겼는지 직접 점검하거나, 바쁜 대기를 할 필요가 없다.

 

아래 그림은 세마포어를 사용해서 임계 구역을 보호하는 코드이다.

 

 

세마포어는 사용 전에 Semaphore(n)으로 초기화를 해야 하는데, 이때 n은 공유 가능한 자원의 수이다. 예를 들어, 공유 자원의 개수가 1개이면 Semaphore(1), 2개이면 Semaphore(2)이다.

 

세마포어는 초기화가 끝난 후 프로세스가 임계 구역에 진입하기 전에 P()로 사용 중이라고 표시하고 임계 구역에 나올 때 V()로 비었다고 표시하는 방법으로 임계 구역을 보호한다.

 

다음은 세마포어의 내부 코드이다.

 

 

초기화를 할 때 전역 변수 RS를 n으로 초기화한다. P()는 잠금을 수행하는 코드로, RS가 0보다 크면 1만큼 감소시키고 임계 구역에 진입한다. 만약 RS가 0보다 작으면 0보다 커질 때까지 기다린다. block()은 wake_up()이 신호를 보낼 때까지 기다리는 함수이다. V()는 잠금 해제와 동기화를 같이 수행하는 코드로 RS 값을 1 증가시키고 기다리고 있는 다른 프로세스/스레드에게 임계 구역에 진입해도 좋다는 wake_up() 신호를 보낸다.

 

세마포어에서 잠금이 해제되기를 기다리는 프로세스/스레드는 세마포어 큐에 저장되어 있다가 wake_up() 신호를 받으면 큐에서 나와 임계 구역에 진입한다. 이때, 세마포어의 P()나 V()의 내부 코드가 실행되는 도중에 문맥 교환이 일어나 다른 코드가 실행되면 상호 배제와 한정 대기 조건을 보장하지 못한다. 따라서, 내부 코드는 검사와 지정을 사용하여 완전히 실행되도록 구현된다.

 

다음은 프로세스가 3개이고 공유 자원이 2개일 때 세마포어의 내부 동작 예시이다.

 

 

하지만, 세마포어는 어디까지나 소프트웨어적 도구이기 때문에 P()를 써야 하는 곳에 V()를 쓴다던지의 사용자의 잘못된 사용으로 문제가 발생할 수 있다. 따라서, 자동으로 P()와 V()가 처리될 수 있게 만들면 되는데 이를 실제로 구현한 것이 모니터이다.

 

모니터

모니터는 운영체제의 시스템 호출과 같이 공유 자원을 내부적으로 숨기고 공유 자원에 접근하기 위한 인터페이스만 제공함으로써 자원을 보호하고 프로세스 간에 동기화시킨다.

 

모니터는의 작동 원리는 다음과 같다. 임계 구역으로 지정된 변수나 자원에 접근하고자 하는 프로세스는 직접 P()나 V()를 사용하지 않고 모니터에 작업 요청을 한다. 모니터는 요청받은 작업을 모니터 큐에 저장한 후 순서대로 처리하고 그 결과만 해당 프로세스에 알려준다.