Mecanismos De Concurrencia En Linux

Mecanismos de concurrencia en Linux

Linux incluye todos los mecanismos de concurrencia encontrados en otros sistemas UNIX como SVR4, incluyendo tuberías, mensajes, memoria compartida y señales. Adicionalmente, Linux 2.6 incluye un rico conjunto de mecanismos de concurrencia específicamente creados para usarse cuando un hilo se está ejecutando en modo kernel. O sea, estos mecanismos se usan dentro del kernel para proveer concurrencia en la ejecución de código a nivel kernel. Aquí examinamos los mecanismos de concurrencia del núcleo de Linux.

Operaciones atómicas

Linux provee un conjunto de operaciones que garantizan las operaciones atómicas sobre una variable. Estas operaciones pueden usarse para evitar condiciones de competencia simples. Una operación atómica se ejecuta sin interrupción y sin interferencia. En un sistema con un solo procesador, un hilo llevando a cabo una operación atómica no puede ser interrumpido una vez que la operación ha iniciado hasta que esta termina. Adicionalmente, en un sistema multiprocesador, se bloquea el acceso a la variable sobre la que se está operando por parte de otros hilos hasta que la operación ha concluido.

Hay dos tipos de operaciones atómicas definidas en Linux: las operaciones enteras, que operan en una variable entera, y las operaciones de mapa de bits que operan en un bit de un mapa de bits (tabla 1). Estas operaciones deben implementarse en cualquier arquitectura que implemente Linux. Para algunas arquitecturas, existen las correspondientes instrucciones en lenguaje ensamblador para las operaciones atómicas. En otras arquitecturas, se usan operaciones que bloquean el bus de memoria para garantizar que la operación es atómica.

Operaciones atómicas enteras

ATOMIC_INIT (int i) En declaración: inicializa un atomic_t a i

int atomic_read(atomic_t *v) Lee el valor entero de v

void atomic_set(atomic_t *v, int i) Iguala el valor de v a i

void atomic_add(int i, atomic_t *v) suma i a v

void atomic_sub(int i, atomic_t *v) Resta i a v

void atomic_inc(atomic_t *v) Suma 1 a v

void atomic_dec(atomic_t *v) Resta 1 a v

int atomic_sub_and_test(int i, atomic_t *v) Resta i a v; regresa 1 si el resultado es cero; regresa 0 si no

int atomic_add_negative(int i, atomic_t *v) Suma i a v; regresa 1 si el resultado es negativo; regresa 0 si no (usado para implementar semáforos)

int atomic_dec_and_test(atomic_t *v) Resta 1 a v; regresa 1 si el resultado es cero; regresa 0 si no.

int atomic_inc_and_test(atomic_t *v) Suma 1 a v; regresa 1 si el resultado es cero; regresa 0 si no

Atomic Bitmap Operations

void set_bit(int nr, void *addr) Pone en 1 el bit nr en el mapa de bits apuntado por addr

void clear_bit(int nr, void *addr) Pone en 0 el bit nr en el mapa de bits apuntado por addr

void change_bit(int nr, void *addr) Invert bit nr in the bitmap pointed a by addr

int test_and_set_bit(int nr, void *addr) Pone en 1 el bit nr en el mapa de bits apuntado por addr; regresa el viejo valor

int test_and_clear_bit(int nr, void *addr) Pone en 0 el bit nr en el mapa de bits apuntado por addr; regresa el viejo valor

int test_and_change_bit(int nr, void *addr) Invierte el bit nr en el mapa de bits apuntado por addr; regresa el viejo valor

int test_bit(int nr, void *addr) Regresa el valor del bit nr en el mapa de bits apuntado por addr

Para operaciones atómicas enteras se usa un tipo de dato especial, atomic_t. Estas operaciones solo se pueden usar sobre este tipo de dato, y no se permiten otras operaciones para este tipo de dato. [LOVE04] lista las siguientes ventajas para estas restricciones:

1. Las operaciones atómicas nunca son usadas en variables que puedan bajo alguna circunstancia estar desprotegidas de condiciones de competencia.

2. Las variables de este tipo de dato están protegidas del uso inapropiado por operaciones no atómicas.

3. El compilador no puede optimizar erróneamente el acceso al valor (por ejemplo, usando un alias en vez de la dirección de memoria correcta).

4. Este tipo de dato sirve para esconder diferencias específicas a la arquitectura en su implementación.

Un uso típico del tipo de dato atómico entero es para implementar contadores.

Las operaciones atómicas en mapas de bits operan en uno de una secuencia de bits en una localidad arbitraria de memoria indicada por un apuntador. Así, no hay un equivalente al tipo de dato atomic_t necesario para las operaciones atómicas enteras.

Las operaciones atómicas son las más simples de las formas de abordar la sincronización del kernel. A partir de ellas se pueden construir mecanismos más complejos.

Spinlocks

La técnica más común para proteger una sección crítica en Linux es el spinlock. Solo un hilo puede adquirir un spinlock en un instante dado. Cualquier otro hilo intentando adquirir el mismo spinlock seguirá intentándolo hasta que lo consiga. En esencia un spinlock se construye sobre una localidad en la memoria que es checada por cada hilo antes de entrar en su sección crítica. Si el valor es 0, el hilo lo pone en 1 y entra en su sección crítica. Si el valor no es 0 el hilo lo checa continuamente hasta que sea 0. El spinlock es fácil de implementar pero tiene la desventaja de que los hilos bloqueados siguen ejecutándose en modo ocupado-esperando. Así los spinlocks son más efectivos en situaciones donde el tiempo de espera para obtener el spinlock será muy corto, a lo más del orden de dos cambios de contexto.

La forma básica del spinlock es la siguiente:

Spin_lock(&lock)

/*seccion crítica*/

Spin_unlock(&lock)

Spinlocks básicos

El spinlock básico (al contrario del spinlock lector-escritor que se explica posteriormente) se divide en cuatro tipos (tabla 2):

• Simple: si la sección crítica del código no se ejecuta por los manejadores de interrupciones o si las interrupciones están desactivadas durante la e3jecución de la sección crítica, entonces el spinlock simple puede utilizarse. No afecta el estado de interrupción del procesador en que se ejecuta.

• _irq: si las interrupciones siempre están activadas, entonces este spinlock debería usarse.

• _irqsave: si no se sabe si las interrupciones estarán activadas o desactivadas en el momento de la ejecución, entonces debería usarse esta versión. Cuando se adquiere el seguro, el estado actual de las interrupciones en el procesador local se guarda, para restablecerse cuando se libera el seguro.

• _bh: cuando ocurre una interrupción, la cantidad mínima de trabajo es realizada por el correspondiente manejador de interrupciones. Una parte del código llamada la mitad inferior, realiza el rsto del trabajo relacionado con la interrupción, permitiendo que la interrupción actual se tan pronto como sea posible. El spinlock _bh se usa para desactivar y luego activar mitades inferiores para evitar conflicto con la sección cr´tica protegida.

El spinlock simple se usa si el programador sabe que los datos protegidos no son accedidos por un manejador de interrupciones o una mitad inferior. De otro modo, se usa el spinlock más apropiado.

Los spinlocks se implementan diferente en una maquina monoprocesador que en una multiprocesador. Para un sistema monoprocesador, las siguientes consideraciones aplican. Si el desalojo del kernel está desactivado, de modo que un hilo ejecutándose en modo kernel no pueda interrumpirse, entonces los seguros se borran en tiempo de compilación; no hacen falta. Si el desalojo de kernel está activado, lo que permite interrupciones, entonces los spinlocks de nuevo se desechan en compilación pero se implementan como código que simplemente activa/desactiva interrupciones. En una máquina multiprocesador, el spinlock se compila en código que realmente afecta la localización del spinlock.

El uso del mecanismo spinlock en un programa le permite ser independiente de si se ejecuta en maquina monoprocesador o multiprocesador.

void spin_lock(spinlock_t *lock) Adquiere el seguro especificado, girando si es necesari hasta que esté disponible.

void spin_lock_irq(spinlock_t *lock) Como spin_lock pero también desactiva las interrupciones en el procesador local.

void spin_lock_irqsave(spinlock_t *lock,

unsigned long flags) Como spin_lock_irq, pero también salva el estado actual de las interrupciones en las banderas.

void spin_lock_bh(spinlock_t *lock) Como spin_lock, but also disables the execution of all bottom halves pero también desactiva la ejecución de todas las mitades inferiores.

void spin_unlock(spinlock_t *lock) Libera el seguro especificado.

void spin_unlock_irq(spinlock_t *lock) Libera el seguro especificado y activa las interrupciones locales

void spin_unlock_irqrestore(spinlock_t *lock,

unsigned long flags) Libera el seguro especificado y restablece las interrupciones locales al estado previo.

void spin_unlock_bh(spinlock_t *lock) Libera el seguro especificado y activa las mitades inferiores.

void spin_lock_init(spinlock_t *lock) Inicializa el spinlock especificado

int spin_trylock(spinlock_t

...