BlakStar

<1> 커널의 시간 개념 

커널에서는 시스템 타이머라고 하는 장치를 이용하여 시간을 측정한다. 시스템 타이머는 전자 시계 등의 전기적 신호를 이용해 일정 시간마다 '울린다'. 시스템 타이머가 울리게 되면 즉시 시스템 타이머 인터럽트가 발동하며 이를 이용해 시간을 측정할 수 있다. 시스템 타이머는 진동수에 따라 울리게 되며 이는 커널이 이미 알고 있는 상수이다. 두 시스템 타이머 인터럽트 사이를 tick이라고 부르며 이 값은 당연히 진동수 분의 1초가 된다.

<2> 진동수

시스템 타이머의 진동수는 정적 매크로인 HZ에 의해 정해진다. 현재 리눅스 커널에서는 100Hz로 설정되어 있다. 진동수를 크게 하는 데에는 몇가지 장점이 존재하는데 다음과 같다.

• 더 정교한 시간 해상도 및 정확도
• 타임아웃 값을 선택적으로 사용할 수 있는 poll()이나 select()같은 시스템 콜을 더 정밀하게 실행할 수 있다.
• 자원 사용률, 시스템 가동 시간 등의 측정값을 더 세밀하게 측정할 수 있다.
• 프로세스 스케줄링이 더 정확히 처리된다.

단점은 명확하다 : 시스템 타이머 인터럽트가 더 자주 발생하게 되므로 이에 따른 부담이 더욱 증가하게 된다. 현대적인 시스템에서는 대략 1000Hz정도의 진동수는 시스템에 크게 부담되지 않는다고 여겨진다. 

<3> jiffies과 xtime

jiffies는 unsigned long형태의 전역변수로서 시스템 시작 후의 틱수가 저장된다. 

xtime은 1970년 1월 1일 이후의 초를 저장하는 구조체이다. xtime은 seqlock을 사용해서 접근해야 한다.

<4> 시스템 타이머 인터럽트 핸들러

타이머 인터럽트 핸들러는 아키텍처 종속적인 부분과 독립적인 부분으로 나눌 수 있다. 우선 아키텍처 종속적인 부분은 인터럽트 핸들러 형태로 되어있으며 다음의 역할을 처리한다.

• 필요에 따라 시스템 타이머를 확인하고 재설정한다.
• 갱신된 현재 시간을 주기적으로 실시간 시계에 반영한다.
• jiffies 밑 현재 시간을 저장하는 xtime 변수에 접근하기 위한 xtime_lock을 얻는다.
• 아키텍처 독립적인 함수 tick_periodic()을 호출한다.

아키텍처 독립적인 부분은 tick_periodic()에서 처리되며 다음과 같은 일을 한다.

• jiffies의 값을 1 증가시킨다. 
• 현재 실행 중인 프로세스가 소모한 시스템 시간 사용자 시간과 같은 자원 통계값을 갱신한다.
• 설정 시간이 지난 동적 타이머를 실행한다
• scheduler_tick()을 실행한다.
• xtime에 저장된 현재 시간을 갱신한다.
• 평균 로드를 갱신한다.

타이머 인터럽트 핸들러에선 프로세스의 실행시간을 갱신할때 해당 프로세스가 하나의 틱 전체를 사용한 것으로 간주한다. 즉 하나의 틱에서 여러 프로세스가 선점되며 실행되었어도, 마지막에 실행된 프로세스가 전체 틱을 사용한 것으로 간주한다는 뜻이다. 진동수가 증가하게 되면 이러한 불공평함이 다소 해소될 수 있다.

<5> 타이머

때때로, 커널에서는 일정한 시간 이후에 함수가 실행되어야 하는 경우가 있다. 이를 위해 리눅스에서는 타이머를 지원한다. 타이머에 만료시간과 함수를 지정하면, 만료 시간 이후에 타이머가 '울리게' 되며 함수가 실행되고 타이머는 종료된다. 이 때, 만료시간 이전에 타이머가 울리지 않는 것은 보장되지만, 만료 시간 직후에 지연이 존재할 수 있다. 타이머는 링크드 리스트의 형태로 저장되며, 빠른 검색을 위해 5개의 리스트로 나뉜다.

<6> 실행 지연

리눅스에서 타이머와 같은 실행 지연은 실제로 어떻게 구현될까? 몇 가지 방법들을 생각해 볼 수 있다. 우선 가장 쉽게 생각할 수 있는 것으로

1) 루프 반복

- 원하는 만큼의 진동수가 지날때까지 의미없는 루프를 반복한다.

가 있을 수 있겠다. 하지만 이는 명백하게 프로세서 시간 낭비이며 너무 비효율적으라 실제로 사용되지 않는다. 1)을 개선한 방법으로

2)resched()

- 루프를 반복하되, 무의미한 루프를 돌지 않고 현재 프로세스를 resched()함수로 리스케줄하게 함.

- 스케줄러가 호출되므로 프로세스 컨텍스트에서만 사용 가능

가장 최적화된 방법으로 다음과 같은 함수를 사용할 수도 있다.

3)schedule_timeout

- 지정한 시간까지 현재 프로세스를 휴면 상태로 전환한다.

- 휴면상태로 전환되므로 프로세스 컨텍스트에서, lock을 사용하지 않는 경우에만 사용가능하다.

위와 같은 방법이 있을 수 있다. 위의 방법들 모두 지연 시간이 진동수보다 큰 경우를 다루고 있다. 즉 위의 두 방법 모두 jiffies값을 이용해 지연 시간이 만료되었는지 확인한다. 만약 지연 시간이 1진동수보다 작다면 어떻게 지연할 수 있을까? 이를 위해 커널에서는 다음과 같은 함수들을 제공한다.

4)udelay(), ndelay(), mdealy()

- ndealy()와 mdelay()는 각각 나노초와 마이크로초 단위로 실행을 지연한다.

- udelay()는 주어진 시간을 지연하려면 얼마나 루프를 돌아야 하는지 계산해놓은 루프로 구현되어 있다.

<참고>

http://hooneyo.tistory.com/entry/%EC%8B%A4%ED%96%89%EC%A7%80%EC%97%B0

<1> Atomic Operations

Ch.9에서 다룬 race condition을 다시 보자. 

여기에서 val++가 atomically하게 동작한다고 가정하면 다음과 같이 변화한다.

위의 atomic operation에서는 항상 결과가 2가 됨이 보장된다. 

즉 atomic operation이란 원자가 더 이상 쪼개질 수 없는(것으로 생각되었던) 

물질이듯이 더 이상 쪼개질 수 없는 연산으로 처리됨을 의미한다. 

당연하지만, 더 이상 쪼개질 수 없다는 뜻은 중간에 인터럽트가 존재할 수 없다는 것이고, 따라서 race condition이 발생할 수 없다. 

리눅스 커널에서는 integer와 bit연산에 대한 atomic interface를 각각 제공한다.

1)Atomic integer

atomic_t라는 자료형 및 관련 함수들로 구현된다. 이는 C의 int와 동일하게 32비트 정수이다. 

atomic operation에 굳이 int가 아닌 atomic_t라는 별도의 자료형을 사용하는데에는 두 가지 이유가 있다.

• atomic 함수에 nonatomic 변수가 전달되거나 nonatomic함수에 atomic 변수가 전달되는 것을 방지한다.

• 컴파일러가 이 변수의 접근을 최적화하는 것을 방지한다. 

주로 counter로 사용되는 변수에 atomic_t가 자주 사용되는데, 이는 뒤에서 다룰 lock등의 동기화보다 가벼우면서도 동기화를 유지할 수 있기 때문이다. 

2)Atomic bitwise opeartions

Architecture-specific하게 구현된다. 다양한 함수들이 존재하며 nonatomic 함수들과 기능적으로 차이는 없다. 구별을 위해 nonatomic bitwise operation은 __을 앞에 붙인다.

<2> Spinlock

스핀락에서는 단 하나의 스레드만 위험 지역에 진입가능하다. 이름이 '스핀'락인 이유는 위험지역에 진입하고자 하는 스레드들이 while문 등으로 계속 실행하면서 대기하기 때문이다. 물론 위험 지역에 미리 진입 하고 있는 스레드가 없다면 바로 진입 가능하다. 뒤에 나올 세마포어와 다르게, 락을 대기하면서 프로세서 시간을 소모하기 때문에, 위험지역에서 너무 오래 머무르는 일이 없도록 해야한다. 구체적으로는 spin time < 2 * context switch time이 되어야 효율적이라고 할 수 있다. 

또 하나의 특징으로는 스핀락을 얻은 스레드가 휴면 상태로 진입할 수 없다는 점이다. 이 덕분에 후술할 다른 락들과 다르게 인터럽트 핸들러에서 사용 가능하다. 

스핀락은 다음과 같은 형태로 사용한다.

<linux/spinlock.h>

spinlock_t mr_lock = SPIN_LOCK_UNLOCKED;

spin_lock(&mr_lock);
/* critical section */
spin_unlock(&mr_lock);

위와 같은 형태 때문에 락을 코드에 거는 것으로 착각할 수 있는데, 락은 항상 데이터에 거는 것임을 명심해야 한다. 이는 후술할 다른 락들도 마찬가지이다.

<3> Semaphore

세마포어는 상술한 스핀락과 다르게, 프로세서 타임을 소모하면서 락을 대기하는 것이 아니라, 휴면상태로 진입한다. 세마포어를 얻은 스레드가 위험 지역의 처리를 마치고 나올때, 대기중인 스레드가 존재한다면 휴면상태에서 깨워줄 수 있다. 또한 세마포어는 count를 설정하여 위험 지역에 진입가능한 스레드의 개수를 정할 수 있다. 세마포어를 얻을 때 count를 1감소시키고, 반납할때 1증가 시킨다. 만약 count가 0이 된다면 세마포어를 얻을 수 없는 상태이므로 휴면상태로 돌입하여 대기한다. 따라서 초기 count가 3이라면 위험 지역에서 허용 간으한 스레드의 수가 3개란 뜻이다. 

당연하게도, 위험 지역에서 2개 이상의 스레드를 허용할 일은 보통 없다. 따라서 세마포어는 count를 1로 많이 사용하며 이를 상호 배제한 락이라고 하여 뮤텍스(mutex)라 표현한다. 또한 세마포어를 얻은 상태에서 휴면 가능하므로 인터럽트 컨텍스트에서 세마포어를 사용할 수 없고 프로세스 컨텍스트에서만 사용하여야 한다. 마찬가지 이유로 스핀락을 얻은 상태로 휴면상태에 돌입 할 수 없으므로 스핀락을 얻은 상태로 세마포어를 얻을 수는 없다.

<4> Mutex

위의 세마포어에서 설명한 뮤텍스와 별도의 구현으로서의 뮤텍스가 커널에 존재한다. 이후의 뮤텍스는 모두 별도의 구현으로서의 뮤텍스를 지칭한다고 보면 된다. 뮤텍스는 세마포어 버전의 뮤텍스보다 간단한 인터페이스, 더 뛰어난 성능과 더 많은 제약조건을 포함한다. 제약조건들은 다음과 같다.

1. 락을 획득한 컨텍스트가 반드시 락을 반납해야한다.
2. 재귀적인 락 획득이나 반납은 불가능하다.
3. 뮤텍스 락을 소유한 프로세스가 종료될 수 없다.
4. 인터럽트 핸들러나 bottom half가 뮤텍스를 획득할 수 없다.
5. 제공되는 API로만 뮤텍스를 관리할 수 있다.

이러한 제약조건들 덕분에 뮤텍스는 세마포어보다 더 뛰어난 성능과 디버깅을 가능하게 해준다.

<5> Semaphore vs Mutex

여기서 지칭하는 뮤텍스는 물론 별도의 구현으로서의 뮤텍스이다. 기본적으로 성능이 더 뛰어난 뮤텍스를 사용하되, 뮤텍스의 제약 조건에 걸리는 경우에만 세마포어를 사용한다.

<6> Spinlock vs Mutex

우선 인터럽트 컨텍스트에서는 휴면 상태에 돌입하지 않는 스핀락만 사용 가능하다. 프로세스 컨텍스트에서는 휴면 상태에 집입할 수 있으므로 뮤텍스만 사용할 수 있다. 만약 제한 조건이 없다면, 락 부담이 적어야 하거나 락의 사용 시간이 짧은 경우에는 스핀락을 사용하고, 그렇지 않은 경우에는 뮤텍스를 사용하면 된다.

<1> 동기화(=Synchronization)란?

- 두 개 이상의 스레드가 공통된 자원을 서로 사용하려고 할 때 이를 race condition이라고 한다. (동기화에서 스레드라고 함은 실행중인 코드라고 생각하면 된다.) 예를 들어 전역변수 val이 공유 자원이고, val의 초기값이 0일 때 다음과 같은 경우가 발생할 수 있다.

스레드 A와 B가 동시에 실행중이 아니라면 val이 2번 증가하므로 최종적으로 2가 저장되었을 것이다. 하지만 두 개의 스레드가 동시에 시행되면 위의 표와 같이 실행 순서에 따라서 결과가 달라지는 문제가 발생 할 수 있다.

위와 같이 두 개 이상의 스레드가 병렬적으로 실행 중일때 공유 자원이 존재하면 실행 순서에 따라 결과가 달라진다. 이럴 경우 프로그램의 결과를 예측하기 굉장히 어려우며 따라서 디버깅도 어렵다. 동기화란 이러한 race condition을 방지하면서 두 개 이상의 스레드를 병렬적으로 실행하게 할 수 있도록 해준다. 동기화의 자세한 구현과 기법은 다음 챕터에서 다룬다.