Process Synchronization (mutex, semaphore)

이전 글에서 Critical Section에서 동기화를 하기 위한 소프트웨어적인 해결 방법을 알아봤었다. Mutual Exclusion, Progress, Bounded Waiting 세가지 요구사항을 만족시켜야 Critical Section에 대한 문제를 해결할 수 있다. 이는 일종의 lock으로 볼 수 있는데, 이번 글에서는 하드웨어적으로 lock을 구현하는 방법에 대해 알아보자.

Synchronization Hardware

하드웨어적으로 Critical Section 문제를 해결하기 위한 제일 간단한 방법은 비선점형 커널을 사용하는 것이다. 비선점형 커널을 사용하여 프로세스가 Critical Section안에 있을 때 interrupt되지 않게 하면 된다. 하지만 응답성이 나빠서 real-time 시스템에는 쓸 수 없는 방법이다.

다른 방법은 atomic operation을 사용하는 것이다. atomic 연산은 interrupt 되지 않는 하나의 연산으로서 보장받는다.

아래 그림 1은 TestAndSet이라는 연산이 atomic 연산으로 주어졌을 때, 두 프로세스를 동기화하는 방법을 보여준다.

[그림 1] atomic TestAndSet

그림 1의 코드를 통한 동기화는 Mutual Exclusion, Progress는 만족하지만 Bounded Waiting은 만족하지 못한다. 프로세스의 순서가 보장되지 않음은 물론이고, 한 프로세스가 다른 프로세스에 비해 훨씬 빠르다면 lock을 해제하자마자 다른 프로세스가 기회를 얻기전에 다시 lock을 걸수도 있다. 따라서 같은 비율로 프로세스가 동작되지 않고 최악의 경우 한 프로세스가 starvation 상태가 될 수 있다.

아래 그림 2는 waiting이라는 bool 배열을 둬서 이러한 문제를 해결한다. waiting은 프로세스 개수만큼의 크기를 갖고 있는 bool 배열이다.

[그림 2] waiting 배열을 이용한 TestAndSet

그림 2의 코드에서 중요한 부분은 Critical Section 바로 다음에 다시 while문으로 block 되는 곳이다. 자신의 다음 프로세스부터 순서대로 waiting 상태인 프로세스가 있는지 검사하고, 있으면 그 프로세스의 waiting을 해제함으로써 lock을 양보한다.

순서대로 양보하는 방법을 통해 무한히 대기하거나 너무 적은 빈도로 실행되는 프로세스를 없앴다. 따라서 그림 2의 코드는 Mutual Exclusion, Progress, Bounded Waiting 세가지 요구사항을 모두 만족한다.

 

Mutex

위에서 설명한 하드웨어 솔루션은 프로그래머가 다루기 어렵고 플랫폼에 종속적인 솔루션이다.

그래서 대부분의 시스템에서는 mutex라는 API를 제공해준다. mutex가 Critical Section에 진입할 때 lock을 획득(acquire)한다고 말하고, 나갈 때 해제(release)한다고 표현한다. 이를 아래 그림 3처럼 나타낼 수 있다.

[그림 3] Mutex lock

mutex의 acquire과 release는 available이라는 bool 변수를 이용하여 구현할 수 있다. 이는 아래 그림 4와 같다.

[그림 4] Mutex acquire & release

그림 4의 acquire 구현을 보면 blocking을 busy waiting으로 구현하고 있는데 이를 spinlock이라 부른다.

spinlock은 CPU를 낭비시키는데, single-core single-threaded 환경에서는 전체 컴퓨터가 정지하므로 아주 안좋은 방법이다.

그러나 컨텍스트 스위치 비용이 들지 않으므로 lock 시간이 짧다면 multi-threaded 환경에서 효율적이다.

 

Semaphore

Mutex보다 더 강력한 대안으로 semaphore가 있다. semaphore는 Integer 변수에 대해 wait, signal이라는 atomic operation을 제공하는 방법이다.

아래 그림 5에 wait, signal 연산의 구현 방법이 나와있다. 주의할 점은 wait 연산이 while의 조건문이 false인 것을 확인하고 S--되기 전까지 interrupt 되면 안된다는 것이다. 다만 한 번 true인 것을 확인하면 interrupt 될 수 있다. 이는 시스템이 멈추는 것을 막기 위함이다.

[그림 5] Semaphore wait & signal

semaphore를 구현하는 두 가지 방법이 있다.

• Binary semaphore

  0, 1 둘 중의 한가지 값만 가지는 semaphore다. mutex처럼 critical section 문제를 해결하는데 사용할 수 있으며, 시스템에서 별도로 mutex를 제공해주지 않는 경우에 mutex로서 사용할 수 있다. semaphore를 mutex로 사용하는 경우 아래 그림 6처럼 사용할 수 있다.

  

  [그림 6] semaphore를 이용한 mutex 구현

• Counting semaphore

  2 이상의 정수값을 가질 수 있는 semaphore다. 자원이 제한되어 있을 때 남은 자원의 개수를 세는 데 사용된다.

  counting semaphore는 시스템에서 사용할 수 있는 리소스의 수로 초기화되며, counting semaphore가 0보다 클 때 critical section에 진입할 수 있고, 0이면 다른 프로세스가 signal 함수를 통해 counting semaphore 값을 증가시킬 때까지 프로세스가 대기한다.

semaphore는 두 프로세스의 operation을 동기화하는 데도 사용될 수 있다. 예를 들어 프로세스 p1, p2가 있을 때 p2는 p1의 연산이 끝난다음에 실행되어야만 한다면 아래와 같이 작성할 수 있다.

1. semaphore를 0으로 초기화한다.

2. 프로세스 p1의 코드

   S1;
   signal(semaphore);

3. 프로세스 p2의 코드

   wait(semaphore);
   S2;

지금까지 설명한 semaphore의 가장 큰 문제는 spinlock으로 CPU 사이클을 낭비한다는 것이다. spinlock을 사용하는 경우 컨텍스트 스위치 비용은 없지만 대기 시간이 길어질 경우 CPU 사이클의 낭비가 심하다.

프로세스가 대기하는 다른 방법으로는 대기하는 동안 프로세스를 block 시키고 semaphore가 사용가능해지면 컨텍스트 스위칭 하는것이다. 이 방법을 사용하려면 semaphore마다 ready queue를 가지고 있어야 한다. block된 프로세스들은 ready queue에서 대기하다가 semaphore가 사용가능해지면 컨텍스트 스위칭하는 방식이다.

이와 같은 방식으로 semaphore를 정의하면 아래 그림 7과같이 wait, signal 연산을 정의할 수 있다.

[그림 7] ready queue를 사용하는 semaphore 구현

위 그림 7 구현에서 특이한 점은 wait 연산이 semaphore 값을 검사하기 전에 값을 감소시킨다는 것이다. 이 경우 semaphore가 음수일 경우 semaphore의 절대값은 ready queue에서 대기하는 프로세스의 개수다. 

 

semaphore를 정리해보면 wait, signal 연산이 atomic operation이어야하고, spinlock 또는 ready queue를 이용해 프로세스를 대기시킬 수 있다.

 

Deadlocks & Starvation

mutex, semaphore를 사용하여 프로세스를 block 시킬 때 발생하는 문제 중 하나는 deadlock이다. deadlock은 process가 서로의 자원을 기다리며 계속 block된 상태로 존재하는 문제이다. 이를 그림으로 표현하면 아래 그림 8과 같다.

[그림 8] deadlock

두 번째 문제는 starvation이다. 만약 semaphore의 ready queue가 FIFO 대신 LIFO로 구현되어 있다면, 어떤 프로세스는 영원히 대기할 수도 있다. 

데드락과 관련된 내용은 나중에 별도의 글로 자세히 남길 것이다.

 

참고

https://www2.cs.uic.edu/~jbell/CourseNotes/OperatingSystems/5_Synchronization.html

Operating Systems: Process Synchronization