APIs del kernel, Parte 3: Temporizadores y listas en el kernel 2.6

Procesamiento eficiente con APIs de postergación de trabajos

El kernel de Linux® incluye una gran variedad de APIs concebidas para ayudar a los desarrolladores a construir aplicaciones del kernel y de drivers más simples y eficientes. Dos de las API más comunes usadas para la postergación de trabajos son la API de gestión de listas y la API de temporización. Descubra estas API y aprenda a desarrollar aplicaciones del kernel con temporizadores y listas.

M. Tim Jones, Consultant Engineer, Emulex Corp.

M. Tim JonesM. Tim Jones es arquitecto de firmware incrustado y es autor de Artificial Intelligence: A Systems Approach, GNU/Linux Application Programming (actualmente en su segunda edición), AI Application Programming (en su segunda edición) y BSD Sockets Programming from a Multilanguage Perspective. Sus antecedentes en la ingeniería abarcan desde el desarrollo de kernels para naves espaciales geosincrónicas hasta la arquitectura de sistemas incrustados y el desarrollo de protocolos de redes. Tim es Consultant Engineer de Emulex Corp. en Longmont, Colorado.



05-05-2010

Conéctese con Tim

Tim es uno de nuestros autores más populares y prolíficos. Navegue todos los artículos de Tim en developerWorks. Lea el perfil de Tim y conéctese con él, con otros autores y con lectores como usted en My developerWorks.

Este artículo retoma el tema de la postergación de trabajo que comencé a desarrollar en "Kernel APIs, Part 2: Deferrable functions, kernel tasklets, and work queues" (developerWorks, marzo de 2010). En esta ocasión, me referiré a la Interfaz de Programación de Aplicaciones (API) y a un elemento central de todos los esquemas de postergación de trabajo: la construcción de listas del kernel. También describiré la API de listas del kernel y los temporizadores y demás mecanismos de postergación de trabajo (como las colas de trabajo) usados por ésta.

Los temporizadores son una parte integral de todo sistema operativo y existen varios tipos de mecanismos temporizadores. Comenzaremos con una descripción de las generalidades de los esquemas temporizadores de Linux y luego pasaremos a explicar cómo funcionan.

Origen del tiempo (Linux)

En el kernel Linux, el tiempo se mide mediante una variable global denominada jiffies, la cual identifica la cantidad de tics transcurridos desde el arranque del sistema. En el nivel inferior, la forma de contar los tics dependerá de la plataforma de hardware sobre la que se está ejecutando; no obstante, el conteo generalmente se incrementa con cada interrupción. La tasa de tics (el bit más pequeño de jiffies) es configurable, pero en el reciente kernel 2.6 para x86, un tic es igual a 4ms (250Hz). La variable global de jiffies se aplica en el kernel para una gran variedad de propósitos, uno de ellos es la obtención del tiempo absoluto actual para calcular el valor de tiempo de espera de un temporizador (veremos ejemplos más adelante).


Temporizadores del kernel

Existen diferentes esquemas de temporizadores en los recientes kernels 2.6. El temporizador más sencillo y menos preciso (pero adecuado para casi todos los casos) es la API de temporización. Esta API permite la construcción de temporizadores que operen en el dominio jiffies(tiempo de espera mínimo: 4ms). Otra alternativa es la API de temporización de alta resolución, la cual permite construcciones de temporizadores cuyo tiempo se define en nanosegundos. Aunque la distancia recorrida variará en base al procesador y la velocidad de operación, la API ofrece una forma de programar los tiempos de espera por debajo del intervalo de tics de jiffies.

Temporizadores estándar

La API de temporización estándar forma parte del kernel Linux desde hace tiempo (ya se encontraba incluida en las versiones iniciales del kernel Linux). Si bien ésta ofrece menos precisión que los temporizadores de alta resolución, resulta ideal para los tiempos de espera de drivers tradicionales que cubren casos de errores en la manipulación de dispositivos físicos. En muchos casos, estos tiempos de espera nunca se activan, sino que se inician y luego se eliminan.

Los temporizadores simples del kernel se implementan mediante la rueda de temporización. Esta idea fue concebida por Finn Arne Gangstad en 1997. Si bien este concepto presenta problemas en la gestión de grandes cantidades de temporizadores, funciona bien cuando se busca gestionar cantidades razonables, es decir, en los casos típicos. (La implementación de temporizadores original simplemente mantenía temporizadores doblemente vinculados en orden de finalización. Este enfoque es conceptualmente simple, pero no escalable). La rueda de temporización es un conjunto de sectores de almacenamiento. Cada uno de estos sectores de almacenamiento representa un lapso de tiempo en el futuro para la finalización de temporizadores. Los sectores de almacenamiento se definen usando tiempo logarítmico basado en cinco sectores de almacenamiento. Usando jiffiescomo granularidad de tiempo, se definen una serie de grupos que representan futuros períodos de finalización (donde cada grupo está representado por una lista de temporizadores). La inserción de temporizadores se efectúa mediante operaciones de lista de complejidad O(1) y la finalización se da en el tiempo O(N). La finalización de temporizadores sucede en una operación en forma de cascada, en la que los temporizadores se van eliminando de los sectores de almacenamiento de mayor granularidad e insertando en sectores de almacenamiento de menor granularidad a medida que se acerca su tiempo de terminación. Ahora veamos la API para este tipo de implementación de temporizadores.

API de temporización

Linux proporciona una API simple para la construcción y gestión de temporizadores. Esta API está compuesta por funciones (y funciones auxiliares) para la creación, cancelación y gestión de temporizadores.

Los temporizadores se definen en la estructura timer_list, la cual incluye todos los datos necesarios para implementar un temporizador (como indicadores de tablas y estadísticas de temporizadores opcionales configurados en el tiempo de compilación). Desde el punto de vista del usuario,timer_list contiene un tiempo de terminación, una función de devolución de llamada (cuando/si el temporizador finaliza) y un contexto proporcionados por el usuario. Por lo tanto, el usuario debe inicializar el temporizador y puede hacerlo de distintas formas. El método más sencillo es llamar a setup_timer, que inicializará el temporizador y establecerá la función y el contexto de devolución de llamada proporcionados por el usuario. Otra opción es que el usuario establezca estos valores (función y datos) en el temporizador y simplemente llame a init_timer. Tome en cuenta que setup_timer llama internamente a init_timer"

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

Una vez inicializado el temporizador, el usuario debe establecer el tiempo de terminación llamando a mod_timer. Como los usuarios generalmente proporcionan un tiempo de terminación futuro, suelen agregar jiffies para contar desde el tiempo actual. Los usuarios también pueden eliminar un temporizador (que aún no haya finalizado) llamando a del_timer:

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

Por último, los usuarios pueden determinar si el temporizador está pendiente (aún no se ha activado) llamando a timer_pending(si el temporizador se encuentra pendiente, devolverá 1):

int timer_pending( const struct timer_list *timer );

Ejemplo de temporizador

Veamos algunas de estas funciones de la API en la práctica. El Listado 1 proporciona un módulo kernel simple que muestra los aspectos centrales de la API de temporización simple. Dentro de init_module se inicializa el temporizador con setup_timer y luego se arranca llamando a mod_timer. Cuando el temporizador finaliza, se invoca a la función de devolución de llamada (my_timer_callback). Finalmente, el temporizador se elimina (a través de del_timer) al eliminar el módulo. (Ver la verificación de devolución de del_timer; ésta indica si el temporizador continúa en uso).

Listado 1. Exploración de la API de temporización simple
#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; }

Conozca más acerca de la API de temporización consultando ./include/linux/timer.h. Si bien la API de temporización simple es sencilla y eficaz, no ofrece la precisión que requieren las aplicaciones en tiempo real. Veamos entonces una reciente incorporación a Linux que soporta temporizadores de alta resolución.

Temporizadores de alta resolución

Los temporizadores de alta resolución (o hrtimers) proporcionan un marco de alta precisión para la gestión de temporizadores. Este marco es independiente del marco de temporizadores antes explicado debido a las complejidades que plantearía la combinación de ambos. Si bien los temporizadores operan sobre la granularidad de jiffies, los hrtimers operan en granularidad de nanosegundos.

El marco hrtimer se implementa de manera diferente a la API de temporización tradicional. En lugar de usar sectores de almacenamiento y temporizadores en cascada, los hrtimers se mantienen en una estructura de datos ordenada por tiempo (los temporizadores se insertan en el tiempo para minimizar el procesamiento en el tiempo de activación). La estructura de datos que se aplica es de árbol rojo-negro, estructura que resulta ideal para aplicaciones centradas en el rendimiento (y que está disponible genéricamente como biblioteca dentro del kernel).

El marco hrtimer se encuentra disponible como API dentro del kernel y también es usado por aplicaciones del espacio de usuario a través de nanosleep, itimers y la interfaz de temporizadores denominada Portable Operating System Interface (POSIX). Este marco se incorporó dentro del kernel 2.6.21.

API de temporización de alta resolución

La API de hrtimer se asemeja en algunos aspectos a la API tradicional, pero presenta una serie de diferencias fundamentales en función del control de tiempos adicional. Lo primero que llamará su atención es que el tiempo no se encuentra representado en jiffies, sino en un tipo de datos especial llamado ktime. Esta representación oculta algunos de los detalles de la gestión del tiempo eficiente dentro de esta granularidad. La API formaliza la diferenciación entre tiempos absolutos y relativos y requiere que el llamante especifique el tipo de tiempo.

Al igual que en la API de temporización tradicional, los temporizadores se representan mediante una estructura— en este caso: hrtimer. Esta estructura define al temporizador desde la perspectiva del usuario (función de devolución de llamada, tiempo de terminación, etc.) y además incorpora la información de gestión (el temporizador dentro del árbol rojo-negro, estadísticas opcionales, etc.).

El proceso comienza con la inicialización de un temporizador llamando a hrtimer_init. Esta llamada incluye el temporizador, la definición del reloj y el modo del temporizador (de un solo disparo o reiniciable). El reloj a usar se encuentra definido en ./include/linux/time.h y representa los distintos relojes que soporta el sistema (entre otros: reloj de tiempo real y reloj monotónico que simplemente representa el tiempo desde un punto inicial, como el arranque del sistema). Una vez que el temporizador se ha inicializado, éste puede iniciarse llamando a hrtimer_start. Esta llamada incluye el tiempo de terminación (en ktime_t) y el modo de valoración del tiempo (valor absoluto o relativo).

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);

Una vez iniciado, hrtimer puede cancelarse llamando a hrtimer_cancelo a hrtimer_try_to_cancel. Ambas funciones incluyen la referencia a hrtimer como temporizador a detener. La diferencia entre estas funciones es que la función hrtimer_cancel intenta cancelar el temporizador, pero si éste ya se ha activado, espera a la función de devolución de llamada para finalizar, mientras que la función hrtimer_try_to_cancel también intenta cancelar el temporizador, pero si éste ya se ha activado, devuelve un error.

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

Es posible verificar si hrtimer ha activado la función de devolución de llamada llamando a hrtimer_callback_running. Considere que hrtimer_try_to_cancel llama internamente a esta función y devuelve un error si se llamó a la función de devolución de llamada del temporizador.

int hrtimer_callback_running  (struct hrtimer *timer);

La API de ktime

Este artículo no aborda la API de ktime, la cual proporciona un completo conjunto de funciones para la gestión del tiempo en alta resolución. La API de ktime se encuentra desarrollada en ./linux/include/ktime.h.

Ejemplo de hrtimer

La API de hrtimer es fácil de usar, como muestra el Listado 2. Dentro de init_module, lo primero es definir el tiempo relativo hasta el tiempo de espera (en este caso, 200ms). Para inicializar hrtimer, se debe llamar a hrtimer_init(con reloj monotónico) y luego establecer la función de devolución de llamada. Luego, se inicia el temporizador usando el valor ktime antes creado. Cuando el temporizador se haya activado, se llamará a la función my_hrtimer_callback, la cual devolverá HRTIMER_NORESTART para evitar que el temporizador se reinicie automáticamente. La función cleanup_module permite limpiar cancelando el temporizador con hrtimer_cancel.

Listado 2. Exploración de la API de hrtimer
 #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; }

Queda mucho por desarrollar de la API de hrtimer. Un aspecto interesante de esta API es la habilidad de definir el contexto de ejecución de la función de devolución de llamada (como en el contexto softirq o hardiirq). Conozca más acerca de la API de hrtimer consultando el archivo de inclusión ./include/linux/hrtimer.h.


Listas del kernel

Como mencioné anteriormente en este artículo, las listas son estructuras de gran utilidad y el kernel proporciona una implementación eficiente para su uso genérico. También encontrará listas en las API antes desarrolladas. Conociendo la API de listas doblemente vinculada podrá desarrollar una estructura de datos eficiente y comprender la amplia gama de código del kernel que utiliza listas. Veamos ahora una breve explicación de la API de listas del kernel.

Esta API proporciona una estructura list_head para representar tanto el encabezado de la lista (delimitador) como los indicadores de lista internos de la estructura. Veamos una estructura de muestra que incluye capacidades de listas (ver el Listado 3). Observe que se agregó la estructura list_head para la vinculación de objetos. También es posible agregar la estructura list_head en cualquier parte de la estructura y — a través de GCC (list_entry y container_of, definidos en ./include/kernel/kernel.h)— desreferenciar desde el indicador de lista al superobjeto.

Listado 3. Estructura con referencias de listas de muestra
struct my_data_structure { int
                    value; struct list_head list; };

Como en cualquier implementación en lista, se requiere de un encabezado de lista que actúe como delimitador de la lista. Esto suele llevarse a cabo con la macro LIST_HEAD, que proporciona la declaración e inicialización de la lista. Esta macro crea un objeto list_head de estructura dentro del cual se pueden agregar objetos.

LIST_HEAD( new_list )

También es posible agregar una encabezado de lista manualmente (por ejemplo, si el encabezado de lista se encuentra en otra estructura diferente) usando la macro LIST_HEAD_INIT.

Una vez finalizada la inicialización principal, la lista puede manipularse usando funciones como list_add ylist_del(y muchas otras más). Ahora, pasemos al código de ejemplo que ilustrará más claramente el uso de la API.

Ejemplo de API de listas

El Listado 4 proporciona un módulo kernel simple que explora varias funciones de la API de listas (si bien existen muchas otras, desarrolladas en ./include/linux/list.h). Este ejemplo crea dos listas, las puebla con la función init_module y luego manipula las listas con la función cleanup_module.

Para seguir este ejemplo, el primer paso es crear una estructura de datos (my_data_struct) que incluya algunos datos y dos encabezados de lista. Este ejemplo muestra que es posible insertar un objeto en listas múltiples simultáneamente. Cree dos encabezados de lista (my_full_list y my_odd_list).

Con la función init_module, cree 10 objetos de datos y cárguelos en las listas (todos los objetos deben cargarse en my_full_list y todos los objetos de valores ocasionales en my_odd_list) usando la funciónlist_add. Tome en cuenta que list_add posee dos argumentos, el primero es la referencia de la lista dentro del objeto a usar y el segundo es el limitador de la lista. Esto muestra cómo un objeto de datos puede estar incluido en listas múltiples usando los trucos internos del kernel para identificar el superobjeto que contiene la referencia de lista.

La función cleanup_modulemuestra otras capacidades de la API de listas; la primera es la macro list_for_each, que simplifica la iteración en listas. En esta macro, se debe proporcionar una referencia al objeto actual (pos) y una referencia a la lista a iterar. Con cada iteración, recibirá una referencia list_head, que podrá proporcionarse a list_entry para identificar el objeto contenedor (la estructura de datos). Especifique la estructura y el valor de lista dentro de la estructura, el cual se usará internamente para desreferenciar hacia el contenedor.

Para emitir la lista de valores ocasionales, use otra macro de iteración llamada list_for_each_entry. Esta macro es más sencilla porque proporciona automáticamente la estructura de datos, obviando la necesidad de llevar a cabo un list_entry.

Finalmente, use list_for_each_safe para iterar la lista a efectos de liberar los elementos asignados. Esta macro permite iterar en la lista con protección contra la eliminación de entradas de lista (lo cual se realizará como parte de la iteración). Use list_entry para obtener el objeto de datos (es decir, liberarlo al grupo del kernel) y luego use list_del para liberar la entrada de la lista.

Listado 4. Exploración de la API de listas
#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; }

Existen varias funciones para agregar a la cola en lugar de agregar al encabezado (list_add_tail), combinar listas (list_splice) y realizar pruebas del contenido de una lista (list_empty). Consulte la sección de Recursos para obtener más detalles acerca de las funciones de listas del kernel.


De aquí en más

Este artículo exploró algunas API que tienen la capacidad de separar funcionalidades de acuerdo con las necesidades (APIs de temporizador y APIs de hrtimer de alta precisión) y de uniformar código para su reutilización (API de listas). Los temporizadores tradicionales proveen un mecanismo eficiente para los tiempos de espera de drivers más comunes y los hrtimers proporcionan un nivel superior de calidad de servicio para obtener capacidades de temporizadores más precisas. La API de listas proporciona una interfaz que, a pesar de ser muy genérica, resulta eficaz y altamente funcional. Si usted escribe código para el kernel, seguramente se encontrará con una de estas API o con las tres, por lo cual vale la pena explorarlas.

Recursos

Aprender

Obtener los productos y tecnologías

  • Evalúe los productos IBM de la forma que prefiera: descargue una versión de prueba del producto, pruebe el producto online, use el producto en un entorno de nube o pase unas horas en el SOA Sandbox aprendiendo a implementar eficientemente una Arquitectura Orientada a Servicios.

Comentar

  • Participe en la comunidad My developerWorks. Conéctese con otros usuarios developerWorks mientras visita los blogs, foros, grupos y wikis orientados a los desarrolladores.

Comentarios

developerWorks: Ingrese

Los campos obligatorios están marcados con un asterisco (*).


¿Necesita un IBM ID?
¿Olvidó su IBM ID?


¿Olvidó su Password?
Cambie su Password

Al hacer clic en Enviar, usted está de acuerdo con los términos y condiciones de developerWorks.

 


La primera vez que inicie sesión en developerWorks, se creará un perfil para usted. La información en su propio perfil (nombre, país/región y nombre de la empresa) se muestra al público y acompañará a cualquier contenido que publique, a menos que opte por la opción de ocultar el nombre de su empresa. Puede actualizar su cuenta de IBM en cualquier momento.

Toda la información enviada es segura.

Elija su nombre para mostrar



La primera vez que inicia sesión en developerWorks se crea un perfil para usted, teniendo que elegir un nombre para mostrar en el mismo. Este nombre acompañará el contenido que usted publique en developerWorks.

Por favor elija un nombre de 3 - 31 caracteres. Su nombre de usuario debe ser único en la comunidad developerWorks y debe ser distinto a su dirección de email por motivos de privacidad.

Los campos obligatorios están marcados con un asterisco (*).

(Por favor elija un nombre de 3 - 31 caracteres.)

Al hacer clic en Enviar, usted está de acuerdo con los términos y condiciones de developerWorks.

 


Toda la información enviada es segura.


static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=90
Zone=Linux
ArticleID=487833
ArticleTitle=APIs del kernel, Parte 3: Temporizadores y listas en el kernel 2.6
publish-date=05052010