세마포어

https://www.linux.co.kr/home/lecture/index.php?cateNo=&secNo=&theNo=&leccode=11129

 

까다롭고 어려운 동기화 문제

리눅스 커널이 2.0으로 발전하면서 SMP(SymmtricMultiprocessing)을 지원하기 시작했고 이로 인하여 커널의 공유 자원에 대한 Lock은 복잡해지기 시작했다. SMP를 지원하기 시작하면서 어떤 커널 코드이건 2개 이상의 CPU에서 수행될 수 있기 때문에 스택에 할당된 자원을 제외하고는 동시에 하나 이상의 CPU가 접근할 수 있게 됐으며 그로 인해 프로그래머는 여러 가지 고려해야 할 것이 많아졌다. 반면, 여전히 하나의 CPU만을 갖는 환경의 개발자들은 SMP

를 고려하지 않아도 되기 때문에 사실 동기화에 대해서는 큰 관심이 가지지 않아 왔다. 아직도 임베디드 환경에서는 일반적으로 CPU가 하나이기 때문에 동기화에 관하여 큰 신경을

쓰지 않기도 한다. 하지만 지금은 다 옛말이 됐다. 리눅스 커널이 2.6으로 발전하면서 선점형 커널(Preemptible Kernel)을 지원하기 시작했기 때문이다. 선점형 커널이란 커널 자체가

선점될 수 있다는 것이다. 즉, 커널이 특정 코드를 수행하고 있는 도중 선점되어 커널의 다른 부분의 코드를, 또는 전에 선점되기 직전에 실행하고 있던 코드를 다시 수행할 수 있다는 것

이다. 전에 수행하던 코드로 재진입한다는 것은 결국 SMP와 다를 바 없게 만든다. 이로 인하여 Up(Uniprocessor)환경에서의 Lock 또한 복잡해지기 시작했다. 그렇다. 이번 호에서 다룰

주제는 리눅스 커널의 동기화에 관한 것이다. 동기화 문제는 커널 프로그래밍에 있어 가장 까다롭고 어려운 부분이다. 처음부터 동기화 문제를 고려하고 제대로 설계하지 않으면 가장

발생하기는 쉬운 반면, 해결점을 찾기는 가장 어려운 것이 바로 이 동기화 문제이다. 이번 호에서는 동기화 문제를 겪지 않기 위해 커널에 사용되는 동기화 기법 중 대표적인 몇 가지를

살펴보기로 한다

 

 

1. 동시성(Concurrency) 문제

일반적으로 공유된 자원을 조작하는 코드가 있는 부분을 경쟁구간(Critical Region)이라고 한다. 경쟁구간의 코드는 원자적(Atomic)으로 수행되어야만 한다. 어떤 코드가 원자적으로 수

행되어야 한다는 것은 경쟁구간의 코드가 다른 코드에 의해 방해받지(Interrupted) 않고 최초 소유주가 계속해서 제어권(Control)을 갖고 실행하여야 한다는 것이다. 이런 상황이 지

켜지지 않으면 경쟁상태(Race Condition) 문제가 발생하여 예상치 못한 결과를 발생시키게 된다. 현재의 리눅스 커널은 많은 동시성 문제를 가지고 있다. 이런 문제를 일으키는 원인들은 다음과 같다.

 

● 인터럽트(interrupt)

● 선점가능한 커널(preemptible kernel)

● smp

● 지연 함수(delayed function)

 

 

각각을 살펴보면 다음과 같다.

인터럽트는 비동기적인 이벤트이다. 그러므로 인터럽트가 disable되어 있지 않는 한 언제든지 커널 코드의 수행도중 인터럽트는 발생될 수 있다. 이때 문제가 되는 것은 인터럽트가

발생하는 시간에 커널에서 수행되고 있던 코드가 커널의 공유자원을 사용하고 있을 경우이다. 또는 수행중이었던 함수가 재진입 가능하게 설계되어 있지 않은 경우이다. 인터럽트 핸

들러에서 선점되었던 함수로 재진입하거나 또는 인터럽트 핸들러에서 호출한 함수가 선점되었던 코드가 사용중이었던 커널의 공유자원에 대한 업데이트를 할 경우 자원의 안정성을

깨뜨리는 문제가 발생할 수 있다.

커널 버젼이 2.6으로 올라가면서 커널 자체가 선점 가능하게 바뀌었다. 커널이 선점 가능하다, 하지 않다는 것은 다음과 같은 차이가 있다. 먼저 커널이 선점 가능하지 않다는 것은 커널

의 코드를 수행 도중 자신이 직접 제어권을 양보하지 않는 한 계속해서 제어권을 가지고 수행하는 것이다. 반면 커널이 선점 가능하다는 것은 커널의 코드 수행 중이라도 자신의 의지

와는 상관없이 다른 프로세스로 제어권을 양보할 수 있다는 것이다. 이 차이는 커널 프로그래머의 입장에서는 큰 변화로 느껴질 수 밖에 없다. 왜냐하면 자신이 만든 코드가 언제 선점되어 재진입되거나 또는 공유 자원이 불안정(Inconsistency)하게 될지 모르기 때문이다.

리눅스 커널이 2.0으로 발전하면서부터 SMP를 지원하기 시작했다. 초창기에는 SMP를 지원한다 하더라도 많은 Lock을 가지고 있지는 않았지만 점차 성능문제가 나타나면서 많은

Lock들이 더 잘게(Fine-Grained) 쪼개지며 현재는 1000여개 이상의 Lock들이 커널 내에 존재하고 있다. SMP에 관한 문제의 근본원인은 특정 경쟁구간이 2개 이상의 프로세서에

서 동시에 실행될 수 있다는 문제에서 비롯된다.

커널은 빠른 응답성을 보장하기 위해 많은 지연(Delayed) 함수(workqueue, softirq, tasklet, timer)들을 지원하고 있다. 지연 함수들의 사용은 특정 태스크의 코드를 수행하는 도중

수행되고 있던 태스크와 전혀 관련되지 않은 코드들이 언제나 호출될 수 있다는 것을 의미한다. 이 또한 앞에서 본 것들과 마찬가지로 재진입이나 공유 자원의 불안정성에 문제를 일으킬

소지를 가지고 있다. 앞으로 이러한 문제들을 막기 위하여 리눅스 커널은 어떤 기법들을 제공하는지 알아보도록 하자. (앞으로 강좌를 진행하면 Lock을 얻는 것을“잡았다”, Lock을 해지하는 것을“풀었다”라는 단어로 사용할 것이다.)

 

2. semaphore

리눅스에서 세마포어는 Sleeping Lock이다. Sleeping Lock이 의미하는 것은 하나의 태스크가 이미 Lock을 잡고 있는 상태에서 다른 태스크가 Lock을 다시 잡으려고 한다면 세마포

어는 나중에 Lock을 잡으려고 했던 태스크를 wait queue에 넣고 sleep상태로 만들어 버린다는 것을 의미한다. 그리고 세마포어의 lock을 먼저 잡고 있던 태스크가 세마포어를 풀게되

면 세마포어의 wait queue에 대기하고 있는 태스크 중 하나를 깨워서 세마포어를 잡게 만든다. 이러한 특성으로 인해 세마포어는 인터럽트 컨텍스트에서는 사용할 수 없다. 왜냐하면

인터럽트 컨텍스트에서는 태스크 스케줄링이 일어나서는 안되기 때문이다(이 부분은 나중에 자세히 설명하도록 한다.) 그러므로 세마포어를 사용할 수 있는 상황은 프로세스 컨텍스트

에서만 가능하다. 또한 세마포어는 앞으로 보게 될 spinlock보다 긴 시간을 기다려야 하는 상항에서 자주 사용된다. 세마포어를 얻으려고 하는 태스크를 sleep시키고 다시 스케줄링하

고 하는 시간은 CPU의 관점에서 봤을 때는 굉장히 큰 시간이기 때문이다. 그러므로 일반적으로 공유되는 자원을 얻기까지의 시간이 짧지 않은 경우 사용된다. 세마포어가 상호배제(mutual exclusion)을 위해 사용될 때, 즉 한 경쟁구간이 하나의 프로세스만 접근가능하도록 할 경우

우리는 세마포어를 뮤텍스(mutex)라고 부른다. 뮤텍스는 mutual exclusion의 약어로써 리눅스에서 사용되는 거의 모든 세마포어는 뮤텍스로 사용되고 있다.

 

 

세마포어의 구현은 아키텍처마다 다르다. 그러므로 커널의 asm 디렉토리에 구현되어 있다. 먼저 세마포어를 사용하기위해서는 <asm/semaphore.h>를 include해야 한다. 정적으

로 선언된 세마포어를 만들기 위해서는 다음과 같은 인터페이스를 사용한다.

 

static declare_semaphore_generic(name, count);

 

name이 의미하는 것은 변수의 이름이고 count는 세마포어의 사용 count이다. count를 1로 하면 뮤텍스가 되는 것이다. 커널은 뮤텍스를 만들기 위해 더 편한 인터페이스를 제공한다.

 

static declare_mutex(name)

 

또한 세마포어를 동적으로 초기화하기 위해서는 다음과 같은 인터페이스를 사용한다.

 

void sema_init(struct semaphore *sem, int val);

void init_mutex(struct semaphore *sem);

 

 

여기서 sem은 세마포어의 포인터이며 count는 역시 usage count이다.

세마포어를 얻기 위한 함수로써는 down_interruptible( ) 함수가 있다. 이 함수는 세마포어를 얻으려는 데 실패하면 해당태스크를 task_interruptible 상태로 만든다. 태스크가

task_interruptible 상태에 있다는 것은 해당 태스크가 signal에 의해 깨어날 수 있다는 것을 의미한다. 그러므로 세마포어를 기다리고 있는 프로세스를 사용자가 중간에 인터럽트할 수

있게 만든다. down_interruptible함수가 lock을 얻어서 깨어난 경우가 아니고 중간의 다른 인터럽트로 인해 깨어나게 되면 eintr를 반환한다. 그러므로 down_interruptible( )을 사용

하는 사용자는 항상 반환값을 체크해야 한다. 반면 down( )함수는 호출한 프로세스를 non-interruptible state로 만들게 된다. 이는 여러분이 ps 명령을 통해 해당 태스크를 봤을 때

state에“d state”라 표시되는 태스크들이다.

세마포어를 해지하는 함수는 up( ) 함수이다. 일반적으로 세마포어를 사용하는 예제는 다음과 같다.

 

static declare_mutex(mr_sem);

...

if (down_interruptible(&mr_sem))

..

/* critical region ...*/

up(&mr_sem)

 

 

이밖에도 down_trylock( )과 같은 함수는 해당 세마포어를 얻으려고 시도해보고 세마포어가 lock되어 있다면 sleep 상태로 들어가는 것이 아니고 0이 아닌 값을 반환하게 된다.

 

 

3. read/write semaphore

세마포어는 각 쓰레드가 무엇을 하느냐와는 상관없이 무조건 모든 호출자를 위하여 상호배제를 제공한다. 하지만 많은 태스크들이 공유되는 자원에 대하여 하는 일은 읽기와 쓰기, 두

가지 type의 operation으로 구별될 수 있다. 이렇게 구별 될수 있다면 다음과 같은 일이 가능해진다. 공유되는 자원에 대하여 변경이 있지 않는 한 2개 이상의 reader들이 해당 자원

에 대하여 lock의 소유가 가능해지는 것이다. 그러므로 다른 reader가 경쟁구간에 있더라도 또 다른 reader가 경쟁구간에 진입이 가능하게 됨으로써 세마포어의 사용을 보다 최적화 할 수 있게 된다.

 

reader/writer 세마포어는 <linux/rwsem.h>에 정의되어 있다. 세마포어와 마찬가지로 정적으로 할당된 reader/writer 세마포어를 만들기 위해서는 다음과 같은 인터페이스를 사용하면 된다.

 

static declare_rwsem(name);

 

name은 새롭게 만들어질 세마포어의 이름이다. 동적으로는 다음과 같은 인터페이스로 만들 수 있다.

 

void init_rwsem(struct rw_semaphore *sem);

 

초기화된 lock을 잡기 위한 경우 read 세마포어를 잡기 위한 인터페이스는 다음과 같다.

 

void down_read(struct rw_semaphore *sem);

int down_read_trylock(struct rw_semaphore *sem);

void up_read(struct rw_semaphore *sem);

 

down_read는 공유되는 자원에 대하여 read-only access를 제공한다. 이 함수는 태스크를 uninterruptible state로 만든 다. 그러므로 이를 원치 않을 경우 down_read_trylock 을 사

용하면 된다. 하지만 주의해야 할 것은 down_read_trylock은 다른 커널 함수와는 반환값이 다르다는 것이다. 일반적으로 0 을 반환하면 함수의 성공을 의미하고 그렇지 않으면 실패를

의미하는 것이 관례인데 이 함수는 그 반대로 0을 반환하면 lock을 이미 누가 잡고 있다는 것으로 의미한다. 그러므로 반환값에 주의해서 사용하자. down_read로부터 획득한 세마포

어는 up_read에 의해 해지된다. 이번에는 writer를 위한 인터페이스다. reader와 유사하므로

설명은 생략하기로 한다.

 

 

void down_write(struct rw_semaphore *sem);

int down_write_trylock(struct rw_semaphore *sem);

void up_write(struct rw_semaphore *sem);

 

reader/writer lock의 모든 reader들은 어떤 writer도 Lock을 소유하고 있지 않는 한 Lock을 잡을 수 있게 된다. 하지만 반대로 writer는 어떤 reader도 Lock을 잡고 있지 않고 다른 어떤 writer도 lock을 잡고 있지 않은 경우에만 Lock을 잡을 수 있게 된다. 이것이 의미하는 바는 writer는 reader보다 더 높은 우선순위를 가지고 있다는 것이다.

예를 들어 writer가 경쟁구간에 들어가게 되고 다른 writer가 먼저 lock을 소유한 writer를 기다리고 있고 또 다른 writer가 또 앞의 writer를 기다리고… 이런 상황이 계속해서 발생하게 되면 모든 writer 들이 일을 끝마치기 전에는 어떤 reader도 lock을 잡을 수 없게 될 것이다. 이러한 문제는 reader starvation문제를 발생시켜 어떤 reader로 lock을 잡지 못 하게 될 것이다. 그렇기 때문에 여러분이 reader-writer 세마포어를 사용하려 할 때 유념해야 할 것은 reader/writer 세마포어는 write접근이 별로 없고 접근을 하더라도 매우 짧게 사용하고 반납하는 경우에 사용해야 한다는 점이다.

 

4. completion

커널 프로그래밍을 하다 보면 특정 이벤트가 완료되기를 기다려야 하는 코드를 작성해야 할 경우가 많다. 세마포어를 배운 여러분들은 다음과 같은 코드를 작성하여 목적을 달성할 수

있을 것이다.

 

void test_xxx_function(void)

{

struct semaphore sem;

init_mutex_locked(&sem);

start_external_task(&sem);

down(&sem);

....

...

}

void start_external_task(struct semaphore *sem)

{

...

...

up(sem);

}

하지만 위와 같은 코드는 문제가 있다. 문제가 발생하는 이유는 여러분은 세마포어를 지역변수로 선언했기 때문이다. 또한 커널의 세마포어의 구현을 살펴보면 down과 up함수는 여러CPU에서 병렬적으로 수행될 수 있도록 만들어져 있기 때문이다. 즉 start_external_task가 호출한 up 함수에서는 test_xxx_function()함수의 스택에서 사라진 sem 변수를 접근할 수 있게 된다. 이런 문제를 해결하기 리눅스 커널 2.4.7에서 completion이 추가되었다. completion은 한 태스크가 다른 태스크에게 작업이 완료되었을 통지하는 간단한 메커니즘으로 되어 있다. completion의 내부는 다음에 배우게 될 spinlock을 사용하여 동시에 호출될 수 없도록 작성되어 있기때문에 세마포어에서 발생한 문제는 일어나지 않는다.

 

completion을 사용하기 위해서는 <linux/completion.h>를 include해야 한다. completion은 다음과 같이 만들어 질 수 있다.

 

declare_completion(my_completion);

 

completion이 동적으로 생성되야 한다면 다음과 같이 할 수 있다.

 

struct completion my_completion;

...

init_completion(&my_completion);

 

completion을 기다려야 하는 측에서는 다음과 같은 함수 호출을 통하여 통지를 기다리면 된다.

 

void wait_for_completion(struct completion *c);

 

 

5. spinlock

위에서 언급하였던 것처럼 세마포어와 completion만으로 커널의 모든 영역의 lock을 커버할 수는 없다. 왜냐하면 세마포어나 completion은 태스크를 sleep하게 만들기 때문이다. 커널의 많은 함수들은 태스크가 sleep상태로 들어가면 안 되는 부분이 많이 있다. 커널 코드가 인터럽트 컨텍스트에서 수행되고 있을 때가 바로 그 때이다. 이때 sleep 상태로 들어가면 안 되는 이유는 현재의 태스크의 커널 스택에 nesting된 인터럽트의 복귀 주소와 문맥(CPU register set)이 들어가 있기 때문이다. 예를 들어 서로 다른 인터럽트 핸들러가 2번 이상 nesting된 경우를 생각해보자. 현재 태스크의 커널 스택에는 현재 수행중인 인터럽트 핸들러가 복귀할 주소와 선점되었을 당시의 문맥을 보관하고 있다. 그런데 이때 태스크 스위칭을 유발하는 함수를 호출했다고 하자. 그래서 태스크 스위칭이 발생하였다. 인터럽트 핸들러가 돌아올 곳을 저장하고 있는 곳은 이미 사라져 버렸다. 물론 다른 방법을 통해(이미 ingo molar가 관리하는 rt tree에는 irq처리 쓰레드를 따로 두어 인터럽트 컨텍스트에서도 스케줄이 가능하도록 되어 있음. 하지만 mainline에는 반영되어 있지 않음) 동작할 수 있게 만들 수도

있지만 현재까지의 리눅스 커널은 그런 부분을 감안하지 않고 단순하게 처리하고 있다.

이때 우리가 사용할 수 있는 것은 spinlock이다. spinlock은 이름에서 의미하는 것 처럼 한 CPU가 특정 플래그의 상태를 보며 루프를 돌고(spinning) 있는 것이다. 이렇게 하는 것의

장점은 세마포어보다 훨씬 가볍다는 점이다.

세마포어의 경우 프로세스를 sleep 상태로 두었다가 깨우는 즉, 2번의 컨텍스트 스위칭 비용일 발생할 뿐만 아니라 깨어나 기 전까지 다른 프로세스들의 실행으로 자원을 소유하기까지

는 오랜시간이 걸린다.

반면 spinlock은 CPU하나가 lock이 풀렸는지를 검사하며 계속해서 루프를 돌고 있기 때문에 다른 CPU가 lock을 풀자마자 기다리고 있던 CPU는 lock을 잡을 수 있게 된다. 물론 기다리고 있는 동안의 CPU 사용을 유용한 곳에 쓰지 못한다는 단점이 있긴 하지만 짧은 시간 동안의 lock이라면 spinlock을 사용하는 것이 효율적이다.

spinlock은 특성상 SMP 환경에서 사용되도록 만들어졌다. 하지만 2.6에서 선점형 커널을 지원하면서 UP 환경에서도 마치 SMP와 같이 커널 코드가 재진입될 수 있다. 그러므로 spinlock

이 UP 환경에서는 커널 선점을 비활성화하는 코드로 바뀐다.

UP 환경에서 커널을 컴파일 할 때 커널 선점을 활성화시키지 않은 경우에는 spinlock은 그냥 빈 코드로 바뀌어 아무것도 하지 않게 된다. 여러분이 작성한 코드가 UP 환경에서만 동작한다고 해도, 커널 선점때문에라도 여러분은 spinlock을 사용하여 보호하는 코드를 작성해야 할 필요가 있다.

 

spinlock을 사용하기 위해서는 <linux/spinlock.h>를 include해야 한다. 다른 것들과 마찬가지로 다음과 같이 생성될 수 있다.

 

spinlock_t my_lock = spin_lock_unlocked;

 

동적으로 생성되야 한다면 다음과 같은 함수를 통하여 생성할 수 있다.

 

void spin_lock_init(spinlock_t *lock);

 

lock을 잡는 함수와 해지하는 함수는 다음과 같다.

 

void spin_lock(spinlock_t *lock);

void spin_unlock(spinlock_t *lock);

 

 

spinlock을 사용할 때는 매우 주의해야 한다. 왜냐하면 다음과 같은 경우가 발생할 수 있기 때문이다. 어떤 함수 a가 실행되고 있다. 이때 함수 a는 공유 자원 c를 사용하기 위해서 spin_lock(&c)를 잡고 있는 상태이다. 그런데 갑자기 인터럽트가 발생하였고 인터럽트 핸들러가 수행되었다. 수행된 인터럽트 핸들러 또한 공유 자원 c에 볼일을 가지고 있어서

spin_lock(&c)를 호출하였다. 그런데 아주 공교롭게도 a를 수행하던 CPU와 인터럽트 핸들러를 수행하던 CPU는 같은 CPU이다. 그렇다면 누가 lock을 풀어줄 것인가? 여러분의 컴퓨터는 아무것에도 응답하지 못하는 상태가 될 것이다. 이와 같은 현상을 막기 위해서 spinlock에는 다음과 같은 함수들이 추가로 있다.

 

void spin_lock_irqsave(spinlock_t

*lock,unsigned long flags);

void spin_lock_irq(spinlock_t *lock);

void spin_lock_bh(spinlock_t *lock);

void spin_unlock_irqrestore(spinlock_t

*lock, unsigned long flags);

void spin_unlock_irq(spinlock_t *lock);

void spin_unlock_bh(spinlock_t *lock);

 

 

spin_lock_irqsave 함수는 spinlock을 호출하기 이전에 local CPU의 인터럽트를 금지한다. 그리고 함수 호출 직전의 인터럽트 enable/disable 상태를 flags에 보관하여 둔다. 이것은

함수를 호출하기 직전의 인터럽트 enable/disable 상태를 알 수 없을 때 사용한다.

하지만 함수 호출 직전의 상태가 언제나 인터럽트 enable 상태라는 것을 알 수 있는 상황이면 spin_lock_irq를 사용하는 것이 더 효율적이다. spin_lock_bh 함수도 유사하지만 이것은 인터럽트는 enable상태로 유지하며 softirq만을 disable 하는 것이다. 이렇게 하면 인터럽트는 자유롭게 발생할 수 있어 시스템의 응답성이 좋아진다. 하지만 프로그래머가 인터럽트 핸들러에서는 공유 자원을 접근하지 않는다는 것을 보장해야만 한다.

 

지면상 이번 호에서는 커널에서 가장 흔히 사용되는 세마포어, reader/writer 세마포어, completion, spinlock만을 살펴보았다. 이외에도 커널에는 reader/writer spinlock, seqlock, atomic_t, rcu등 다양한 동기화 메커니즘을 많이 가지고 있다. 커널의 동기화 문제는 결코 만만한 문제가 아니다. 커널의 동기화가 어려운 것은 어떻게 사용하느냐가 아니라 자신이 작성한 코드에서 어떤 부분이 위와 상황을 만들어 낼 수 있는지를 인지한 후 어떤 상황에서 어떤 형태의 동기화 기법을 사용하는 것이 가장 효율적일 것인가를 판단하는 것이다.

하지만 동기화 코드를 작성하는 것에 있어서 가장 중요한 것은 여러분이 작성하고 있는 커널 코드가 가능한 한 공유되는 자원을 사용하지 않도록 설계하는 것일 것이다.

하지만 현실은 종종 그런 바램을 들어주진 않는다. 꼭 동기화기법을 써야 한다면 어떤 장소에 어떤 동기화 도구를 사용하느냐는 여러분의 시스템에 성능 더 나아가서는 안정성까지도 관련된 문제이므로 보다 심도 있는 학습을 통해 적재적소에 맞는 도구를 사용하길 바란다.