Linux Kernel Timer

Linux 시간의 원천

  Linux 커널에서는 jiffies라는 글로벌 변수를 이용해서 측정하며, 이 변수는 시스템 시동 이후의 틱의 수를 식별합니다. 틱의 수를 계산하는 방법은 최저 레벨인 실행인 중인 특정 하드웨어 플랫폼에 따라 달라지지만 일반적으로 틱은 인터럽트를 통해 증가합니다. 틱 속도(jiffies의 최하위 비트)는 구성 가능하지만, 최근 x86용 2.6 커널의 경우에는 1틱이 4ms(250Hz) 입니다.

  jiffies 글로벌 변수는 커널 내에서 다양한 용도로 널리 사용되고 있으며, 대표적으로 타이머의 제한시간 값을 계산하기 위한 현재 절대 시간에 사용됩니다.

커널 타이머

  최근 2.6 커널의 타이머에는 몇 가지 다양한 스키마가 있습니다. 타이머 API가 대부분의 경우에 적합하기는 하지만 모든 타이머 중에서 가장 단순하고 정확성이 낮습니다. 이 API를 사용하면 jiffies 도메인(제한시간 최소 4ms )에서 작동하는 타이머를 생성 할수 있으며, 또한 시간이 나노 초 단위로 정의도는 타이머를 생성할 수 있는 고분해능 타이머(high-resolution timer) API도 있습니다. 

  프로세서 및 그 작동 속도에 따라 성능의 차이가 있을 수 있지만, 이 API를 사용하면 제한시간을 jiffies 틱 간격 이하로 스케줄할 수 있습니다.

표준타이머

  표준타이머 API는 Linux 커널의 초기 버전부터 오랫동안 Linux 커널에 포함되어 있었습니다. 고분해능 타이머(high-resolution timer)에 비해 정확도가 떨어지기는 하지만 실제 장치를 처리할 때 발생하는 오류 케이스를 처리하는 데 사용되는 일반적인 드라이버 제한시간에 이상적입니다. 이러한 제한시간은 실제로 초과되는 경우가 많지 않으며 대부분의 경우에는 시작 되었다가 제거되는 형태를 보인다.

  단순 커널 타이머는 타이머 휠을 사용하여 구현됩니다. 이 아이디어는 1997년 Finn Arne Gangstad 에 의해 처음 소개 되었습니다. 이 타이머는 많은 수의 타이머를 관리하는 데 문제점이 있지만, 이를 무시하고 전형적인 경우인 합리적인 수의 타이머를 관리할 경우 좋은 성능을 제공합니다. (원래 타이머 구현에서는 단순히 만기 순서에 양방향으로 연결된 상태로 타이머를 유지합니다. 개념적으로 단순하지만 이 방법은 확장 될 수 없습니다.) 타이머 휠은 버켓의 컬렉션이며, 각 버켓은 타이머 만기를 위한 미래의 시간을 나타낸다. 버켓은 5개의 버켓을 기반으로 하는 로그 시간(logarithmic time)을 사용하여 정의됩니다. jiffies를 시간 단위로 사용하여 미래의 만기 기간을 나타내는 많은 그룹을 정의 합니다. (각 그룹은 타이머 목록으로 표시됨) 타이머는 복잡도가 O(1) 이고 O(N) 시간 이내에 만기가 되는 목록 작업을 사용하여 삽입되며, 타이머 만기는 계단식으로 발생하게 됩니다.

  즉, 타이머의 만기 시간이 줄어들면 타이머가 정밀도가 높은 버켓에서 제거된 다음 정밀도가 낮은 버켓에 삽입됩니다.

타이머 API

  Linux에는 타이머의 생성과 관리를 위한 간단한 API가 있습니다. 이 API는 타이머 작성, 취소 및 관리를 위한 함수(및 헬퍼 함수)로 구성되어 있습니다.

  타이머는 timer_list 구조체로 정의되며, 이 구조체에는 타이머 구현에 필요한 모든 데이터(컴파일 시 구성되는 선택적 타이머 통계 및 목록 포인터 포함)가 담겨 있습니다. 사용자의 관점에서 볼 때, timer_list에는 만기 시간, 콜백함수(타이머의 만기 시간/여부) 및 사용자 제공 컨텍스트가 있습니다. 그런 다음 사용자는 타이머를 초기화 해주어야 합니다. 초기화는 몇가지 방법으로 수행되는 데, 가장 간단한 방법은 setup_timer를 호출하는 것입니다. 이 함수는 타이머를 초기화하고 사용자 제공 콜백 함수 및 컨텍스트를 설정합니다. 이 함수를 사용하지 않을 경우에는 사용자가 타이머에서 이러한 값(함수 및 데이터를)을 설정하고 init_timer를 호출 할 수 있습니다. init_timer는 setup_timer에서 내부적으로 호출됩니다.

void init_timer( struct timer_list *timer );
void setup_timer( struct timer_list *timer, 
                     void (*function)(unsigned long), unsigned long data );

  setup_timer로 타이머를 초기화한 다음에는 사용자가 mod_timer를 호출하여 만기 시간을 설정해야 합니다. 일반적으로 만기 시간은 미래이므로 여기에서는 jiffies를 추가하여 현재 시간을 기준으로 하는 오프셋을 설정합니다. 사용자는 del_timer를 호출하여 타이머를 삭제할 수 도 있습니다.

int mod_timer( struct timer_list *timer, unsigned long expires );
void del_timer( struct timer_list *timer );

  마지막으로 사용자는 timer_pending을 호출하여 타이머가 아직 만기되지 않고 보류 중인지 여부를 확인 할 수 있습니다. (타이머가 보류 중이면 1이 리턴됩니다.)

int timer_pending( const struct timer_list *timer );

타이머 예제

  이러한 API 함수 중 일부를 실제로 살펴봅시다. Listing 1 에서는 단순 타이머 API의 핵심 부분을 보여주는 단순 커널 모듈을 제공합니다. init_module에서 setup_timer를 사용하여 타이머를 초기화 한 다음 mod_timer를 호출하여 타이머를 시작합니다. 타이머가 만료되면 콜백 함수 (my_timer_callback)가 호출된다. 마지막으로 모듈을 제거하면 del_timer를 통해 타이머가 삭제됩니다.(del_timer의 리턴값을 검사하여 타이머가 사용 중인지 확인)

Listing 1.

#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/timer.h>

MODULE_LICENSE( "GPL" );

static struct timer_list my_timer;

void my_timer_callback( unsigned long data )
{
  printk( "my_timer_callback called (%ld).\n", jiffies );
}

int init_module( void )
{
  int ret;

  printk("Timer module installing\n");

  // my_timer.function, my_timer.data
  setup_timer( &my_timer, my_timer_callback, 0 );

  printk( "Starting timer to fire in 200ms (%ld)\n", jiffies );
  ret = mod_timer( &my_timer, jiffies + msecs_to_jiffies(200) );
  if (ret) printk("Error in mod_timer\n");

  return 0;
}

void cleanup_module( void )
{
  int ret;

  ret = del_timer( &my_timer );
  if (ret) printk("The timer is still in use...\n");

  printk("Timer module uninstalling\n");

  return;
}

/include/linux/timer.h 에서 타이머 API에 대하 ㄴ자세한 정보를 볼 수 있습니다. 단순 타이머 API는 쉽고 효율적이지만 실시간 어플리케이션에 필요한 정확도를 제공하지 못합니다. 따라서 최근에 Linux에 추가되어 더 높은 분해능 타이머를 지원하는 기능이 있습니다.

고분해능 타이머(High-resolution timers)

  고분해능 타이머(hrtimer)는 앞에서 설명한 타이머 프레임워크와는 독립된 고정밀 타이머 관리 프레임워크를 제공합니다. 이는 두 프레임워크를 병합하기가 복잡하기 때문입니다. 타이머는 jiffies 단위로 작동하는 반면 hrtimer는 나노초 단위로 작동합니다.

  hrtimer 프레임워크는 일반적인 타이머 API와 다르게 구현됩니다. 버켓 및 타이머 캐스케이딩 대신 hrtimer는 타이머로 구성된 시간순 데이터 구조를 관리한다. (활성 시간에 처리 시간을 최소화하기 위해 타이머가 시간순으로 삽입됩니다.) 이 프레임워크에 사용되는 데이터 구조는 레드-블랙 트리입니다. 이 트리는 성능에 중점을 둔 어플리케이션에 이상적이며 일반적으로 커널 내의 라이브러리로 사용할 수 있습니다.

  hrtimer 프레임워크는 커널 내에서 API로 사용할 수 있으며 nanosleep, itimers 및 POSIX 타이머 인터페이스를 통해 사용자 공간 어플리케이션에서도 사용됩니다. 이 프레임워크는 2.6.21 커널에 포함되어 있습니다.

고분해능 타이머 API

  hrtimer API에는 기존 API와 유사한 점도 있지만 추가적인 시간 제어를 위한 몇 가지 근본적인 차이점도 있습니다. 첫번째 차이점은 시간이 jiffies가 아닌 ktime이라는 특수 데이터 유형으로 표시가 되는데, 이 표시는 이 단위에서 효율적인 시간 관리와 관련된 일부 세부 사항을 숨깁니다. 이 API는 절대 시간과 상대 시간을 구별하므로 호출자가 유형을 지정해야 합니다.

  기존 타이머 API와 마찬가지로 hrtimer도 구조체로 표현이 되는데, 이 구조체는 사용자 관점(콜백 함수, 만기 시간 등)에서 타이머를 정의하고 관리 정보를 통합합니다.( 이 경우에는 타이머가 레드-블랙 트리. 선택적 통계 등에 존재합니다.)

  먼저 hrtimer_init을 통해 타이머가 초기화 됩니다. 이 호출은 타이머, 클럭 정의 및 타이머 모드(한번 혹은 다시)를 포함합니다. 사용할 클럭은 /include/linux/time.h에 정의되어 있으며, 시스템에서 지원하는 다양한 클럭을 나타냅니다.(예 : 실시간 클럭 또는 시스템 시동과 같은 시작 시점의 시간을 나타내는 모노 클럭) 초기화된 타이머는 hrtimer_start를 사용하여 시작할 수 있습니다. 이 호출은 만기 시간(ktime_t) 및 시간 모드 값(절대값 또는 상대값)을 포함합니다.

void hrtimer_init( struct hrtimer *time, clockid_t which_clock, 
			enum hrtimer_mode mode );
int hrtimer_start(struct hrtimer *timer, ktime_t time, const 
			enum hrtimer_mode mode);

  hrtimer를 시작한 후에는 hrtimer_cancel 또는 hrtimer_try_to_cancel을 호출하여 최소 할 수 있습니다. 각 함수에는 중지할 타이머에 대한 hrtimer 참조가 들어 있으며, 두 함수의 차이점은 다음과 같다. hrtimer_cancel 함수는 타이머를 취소하려고 시도합니다. 하지만 타이머가 이미 시작되었으면 콜백함수가 종료될 때까지 기다립니다. 반면에, hrtimer_try_to_cancel 함수는 타이머를 취소하려고 시도할 때 타이머가 이미 시작되었으면 오류를 리턴합니다.

int hrtimer_cancel(struct hrtimer *timer);
int hrtimer_try_to_cancel(struct hrtimer *timer);

  hrtimer_callback_running을 호출하여 hrtimer가 해당 콜백을 활성화했는지 여부를 확인할 수 있습니다. 이 함수는 타이머의 콜백 함수가 호출되었을 때 오류를 리턴하기 위해 hrtimer_try_to_cancel에 의해 내부적으로 호출됩니다.

int hrtimer_callback_running(struct hrtimer *timer);

hrtimer 예제

  hrtimer API의 사용법은 Listing 2 에서 보여지듯이 매우 간단합니다. init_module 내에서 상대적인 제한시간(이 경우에는 200ms)을 정의하여 시작할 수 있습니다. hrtimer_init 호출을 사용하여 hrtimer를 초기화한(모노 클럭 사용) 다음에 콜백 함수를 설정합니다. 마지막으로 앞에서 작성한 ktime 값을 사용하여 타이머를 시작합니다. 타이머가 시작되면 my_hrtimer_callback 함수가 호출되면서 HRTIMER_NORESTART를 리턴합니다. 따라서 타이머가 자동으로 다시 시작되지 않게 됩니다. cleanup module 함수에서 hrtimer_cancel을 사용하여 타이머를 취소하면서 정리합니다.

Listing2. hrtimer API 탐색

#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/hrtimer.h>
#include <linux/ktime.h>

MODULE_LICENSE( "GPL" );

#define MS_TO_NS(x)	(x * 1E6L)

static struct hrtimer hr_timer;

enum hrtimer_restart my_hrtimer_callback( struct hrtimer *timer )
{
  printk( "my_hrtimer_callback called (%ld).\n", jiffies );

  return HRTIMER_NORESTART;
}

int init_module( void )
{
  ktime_t ktime;
  unsigned long delay_in_ms = 200L;

  printk("HR Timer module installing\n");

  ktime = ktime_set( 0, MS_TO_NS(delay_in_ms) );

  hrtimer_init( &hr_timer, CLOCK_MONOTONIC, HRTIMER_MODE_REL );
  
  hr_timer.function = &my_hrtimer_callback;

  printk( "Starting timer to fire in %ldms (%ld)\n", delay_in_ms, jiffies );

  hrtimer_start( &hr_timer, ktime, HRTIMER_MODE_REL );

  return 0;
}

void cleanup_module( void )
{
  int ret;

  ret = hrtimer_cancel( &hr_timer );
  if (ret) printk("The timer was still in use...\n");

  printk("HR Timer module uninstalling\n");

  return;
}

hrtimer API에는 지금까지 살펴본 것보다 훨씬 더 많은 특성이 있습니다. 한가지 흥미로운 특성은 콜백 함수의 실행 컨텍스트(예 : softirq, hardirq 컨텍스트)를 정의할 수 잇따는 것입니다. /include/linux/hrtimer.h의 포함 파일에서 hrtimer API에 대한 자세한 정보를 볼 수 있습니다.

커널 목록

  앞에서 언급한 것처럼 목록은 아주 유용한 구조입니다. 따라서 커널에서는 일반적인 용도로 사용할 수 잇는 효율적인 구현을 제공합니다. 또한 지금까지 살펴본 API에도 목록이 있습니다. 양방향 연결 목록 API를 이해하면 이 효율적인 데이터 구조를 사용하여 개발 작업을 수행하고 목록을 활용하는 커널의 코드를 이해하는 데 많은 도움이 됩니다. 이제 커널 목록 API를 살펴보도록 합시다.

  이 API는 목록 헤드(앵커)뿐만 아니라 구조체 내 목록 포인터를 나타내는 데도 사용되는 list_head 구조체를 제공합니다. 목록 기능이 포함된 샘플 구조체는 Listing 3에 나와 있습니다. 이 샘플 구조체에는 오브젝트 연결에 사용되는 list_head 구조체가 추가 되어 있습니다. 그리고 일부 GCC magic (/include/kernel/kernel.h 에 정의된 list entry 및 container_of)을 통해 구조체의 어디에서나 list_head 구조체를 추가할 수 있으며 목록 포인터에서 수퍼 오브젝트로 역참조 할 수 있습니다.

Listing 3. 목록 참조를 사용하는 샘플 구조체

	
struct my_data_structure {
	int value;
	struct list_head list;
};

  모든 목록 구현에서와 마찬가지로 목록에 대한 앵커 역할을 수행할 목록 헤드가 필요합니다. 이 작업은 일바넞긍로 목록에 대한 선언 및 초기화를 제공하는 LIST_HEAD 매크로를 통해 수행됩니다. 이 매크로는 사용자가 오브젝트를 추가할 수 잇는 list_head 오브젝트 구조체를 작성합니다.

LIST_HEAD( new_list )

  또한 LIST_HEAD_INIT 매크로를 사용하여 수동으로 목록 헤드를 작성할 수 있습니다.( 예를들어, 목록 헤드가 다른 구조체에 있는 경우)

기본 초기화가 완료되면 list_add 및 list_del 함수를 포함한 여러 함수를 사용하여 목록을 조작할 수 있습니다. 이제 이 API의 사용법을 더 잘 보여주는 예제 코드를 살펴 보도록 합시다.

목록 API 예제

  Listing 4에서는 수많은 목록 API 함수를 탐색하는 간단한 커널 모듈을 제공합니다.(/include/linux/list.h 에서 많은 함수를 찾아볼 수 있습니다.) 이 예제에서는 두개의 목록을 작성하고, init_module 함수를 이용하여 목록을 채운 다음 cleanup_module 함수에서 조작합니다.

  먼저 일부 데이터와 두개의 목록 헤더를 포함하는 데이터 구조(my_data_struct)를 작성합니다. 이 예제에서는 한 오브젝트를 여러 목록에 동시에 삽입할 수 있다는 것을 보여줍니다. 그런 다음 두개의 목록 헤드(my_full_list 및 my_odd_list)를 작성합니다.

  init_module 함수에서 10개의 데이터 오브젝트를 작성한 다음 list_add 함수를 사용하여 목록에 로드합니다.(my_full_list에 모든 오브젝트를 로드하고 my_odd_list에 모든 홀수 값 오브젝트를 로드합니다.) list_add는 두개의 인수를 사용하는데, 첫 번째 인수는 사용할 오브젝트 내의 목록 참조이고 두번째 인수는 목록 앵커입니다. 이는 목록 참조가 있는 수퍼 오브젝트를 식별하는 커널의 내부 기능을 사용하여 데이터 오브젝트를 여러 목록에 로드할 수 있음을 보여 줍니다.

  cleanup_modlue 함수는 목록 API의 몇 가지 추가 기능을 보여 줍니다. 첫번째 기능은 목록 반복을 쉽게 수행할 수 있도록 지원하는 list_for_each 매크로 입니다. 이 매크로를 사용하려면 현재 오브젝트에 대한 참조(pos)와 반복할 목록 ㅊ마조를 제공해야 합니다. 각 반복 마다 list_head 참조가 리턴되며, 리턴된 참조를 list_entry에 제공하여 컨테이너 오브젝트(사용자의 데이터 구조)를 식별할 수 있습니다. 사용자의 구조와 구조 내의 목록 변수를 지정합니다. 이 변수는 내부적으로 컨테이너를 역참조하는 데 사용됩니다.

  홀수 목록을 표시하기 위해 또 하나의 반복 매크로인 list_for_each_entry를 사용합니다 . 이 매크로는 사용자의 데이터 구조를 자동으로 제고하므로 list_entry를 수행하지 않아도 되기 때문에 더 간단합니다.

  마지막으로 할당된 요소를 해제하기 위해 list_for_each_safe를 사용하여 목록을 반복합니다. 이 매크로를 사용 하면 목록 항목을 제거(반복 작업의 일부로서 수행할 작업)하지 않으면서 안전하게 목록을 반복할 수 있습니다. list_entry를 사용하여 데이터 오브젝트를 찾은(커널 풀에 다시 해제하기 위해) 다음 list_del을 사용하여 목록의 항목을 해제합니다.

Listing 4. 목록 API 탐색

#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/list.h>

MODULE_LICENSE( "GPL" );

struct my_data_struct {
  int value;
  struct list_head full_list;
  struct list_head odd_list;
};

LIST_HEAD( my_full_list );
LIST_HEAD( my_odd_list );


int init_module( void )
{
  int count;
  struct my_data_struct *obj;

  for (count = 1 ; count < 11 ; count++) {

    obj = (struct my_data_struct *)
            kmalloc( sizeof(struct my_data_struct), GFP_KERNEL );

    obj->value = count;

    list_add( &obj->full_list, &my_full_list );

    if (obj->value & 0x1) {
      list_add( &obj->odd_list, &my_odd_list );
    }

  }

  return 0;
}


void cleanup_module( void )
{
  struct list_head *pos, *q;
  struct my_data_struct *my_obj;

  printk("Emit full list\n");
  list_for_each( pos, &my_full_list ) {
    my_obj = list_entry( pos, struct my_data_struct, full_list );
    printk( "%d\n", my_obj->value );
  }

  printk("Emit odd list\n");
  list_for_each_entry( my_obj, &my_odd_list, odd_list ) {
    printk( "%d\n", my_obj->value );
  }

  printk("Cleaning up\n");
  list_for_each_safe( pos, q, &my_full_list ) {
    struct my_data_struct *tmp;
    tmp = list_entry( pos, struct my_data_struct, full_list );
    list_del( pos );
    kfree( tmp );
  }

  return;
}

헤드 대신 목록의 후미에 추가하고 (list_add_tail), 목록을 결합하고(list_splice), 목록의 컨텐츠를 테스트하는(list_empty) 등의 기능을 제공하는 여러 다양한 함수가 있으니, 더 많은 자세한 정보를 찾아 보시기 바랍니다.

끝으로

  필요에 따라 기능을 분리하는 기능(타이머 및 고정밀 타이머) 뿐만 아니라 코드 재사용을 위해 코드를 일반화하는 기능(목록 API)을 보여주는 몇 가지 API를 설명하였습니다.

  일반 타이머는 일반 드라이버 제한시간에 효율적인 메커니즘을 제공하는 반면 hrtimer는 정밀도 높은 타이머 기능을 위한 높은 서비스 품질을 제공합니다.

  목록 API는 매우 일반적이지만 효율적이고 다양한 기능을 갖춘 인터페이스를 제공합니다.

커널 코드를 작성하게 되면 이러한 세 API 중 하나 이상을 실행 할 것이므로 깊은 이해가 필요한 주제 였습니다.