PDF de programación - Guía Informal al Bloqueo

Guía Informal al Bloqueo

Paul Rusty Russell
[email protected]

Guía Informal al Bloqueo
por Paul Rusty Russell

Copyright © 2000 por Paul Russell

Esta documentación es software libre; puedes redistrubuirla y/o modificarla bajo los términos de la GNU General Public License tal como ha sido
publicada por la Free Software Foundation; por la versión 2 de la licencia, o (a tu elección) por cualquier versión posterior.
Este programa es distribuido con la esperanza de que sea útil, pero SIN NINGUNA GARANTIA; sin incluso la garantía implicada de
COMERCIABILIDAD o ADECUACCION PARA UN PROPOSITO PARTICULAR. Para más detalles refiérase a la GNU General Public
License.
Debería de haber recibido una copia de la GNU General Public License con este programa; si no es así, escriba a la Free Software Foundation,
Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
Para más detalles véase el archivo COPYING en la distribución fuente de Linux.

Tabla de contenidos

1. Introducción ...........................................................................................................................................1
1.1. El Problema con la Concurrencia................................................................................................1
2. Dos Tipos Principales de Bloqueos del Núcleo: Spinlocks y Semáforos ...........................................3
2.1. Bloqueos y Núcleos Monoprocesador ........................................................................................3
2.2. Variantes de Bloqueo Lectura/Escritura......................................................................................3
2.3. Bloqueando Sólo en el Contexto de Usuario ..............................................................................3
2.4. Bloqueando entre Contexto de Usuario y BHs (Bottom Halves) ...............................................4
2.5. Bloqueando Entre Contexto de Usuario y Tasklets/Soft IRQs ...................................................4
2.6. Bloqueando Entre Bottom Halves...............................................................................................4
2.6.1. El Mismo BH..................................................................................................................4
2.6.2. Diferentes BHs ...............................................................................................................5
2.7. Bloqueando Entre Tasklets..........................................................................................................5
2.7.1. La Misma Tasklet ...........................................................................................................5
2.7.2. Diferentes Tasklets .........................................................................................................5
2.8. Bloqueando entre Softirqs...........................................................................................................5
2.8.1. La Misma Softirq............................................................................................................5
2.8.2. Diferentes Softirqs..........................................................................................................6
3. Contexto de IRQ de Hardware.............................................................................................................7
3.1. Bloqueando entre IRQs Hardware y Softirqs/Tasklets/BHs .......................................................7
4. Técnicas Comunes .................................................................................................................................8
4.1. En un Contexto de Interrupciones No Escritores........................................................................8
4.2. Deadlock: Simple y Avanzado ....................................................................................................8
4.2.1. Preveniendo los Deadlocks.............................................................................................9
4.2.2. Sobreentusiasmo en la Prevención de Deadlocks...........................................................9
4.3. Datos por cada CPU..................................................................................................................10
4.4. Bloqueos Gran Lector ...............................................................................................................10
4.5. Eliminando los bloqueos: Ordenamiento de Lecturas y Escrituras ..........................................10
4.6. Eliminando los Bloqueos: Operaciones Atómicas....................................................................11
4.7. Protegiendo Una Colección de Objetos: Cuentas de Referencia ..............................................11
4.7.1. Macros Para Ayudarte...................................................................................................13
4.8. Cosas Que Duermen..................................................................................................................13
4.9. La Follonera Sparc ....................................................................................................................14
4.10. Cronómetros de Carreras: Un Pasatiempo del Núcleo............................................................14
5. Lecturas Adicionales ...........................................................................................................................16
6. Gracias ..................................................................................................................................................17
7. Sobre la Traducción.............................................................................................................................18
Glosario.....................................................................................................................................................19

iii

Lista de tablas

1-1. Resultados Esperados ...........................................................................................................................1
1-2. Resultados Posibles ..............................................................................................................................1
4-1. Consecuencias ......................................................................................................................................9

iv

Capítulo 1. Introducción

Bienvenido, a la Guía Informal de Bloqueo de Núcleo de Rusty. Este documento describe los sistemas de
bloqueo en el núcleo Linux como aproximación al 2.4.

Parece que es aquí donde tiene que estar SMP ; por lo tanto todo el mundo que esté en estos días
hackeando el núcleo necesita conocer los fundamentos de la concurrencia y el bloqueos para SMP.

1.1. El Problema con la Concurrencia

(Sáltate esto si sabes lo que es una Condición de Carrera (Race Condition).

En un programa normal, puedes incrementar un contador de la forma:

contador_muy_importante++;

Esto es lo que esperarías que pasase:

Tabla 1-1. Resultados Esperados

Instancia 1
lee contador_muy_importante (5)
añade 1 (6)
escribe contador_muy_importante (6)

Esto es lo que quizás pase:

Tabla 1-2. Resultados Posibles

Instancia 1
lee contador_muy_importante (5)

añade 1 (6)

escribe contador_muy_importante (6)

Instancia 2

lee contador_muy_importante (6)
añade 1 (7)
escribe contador_muy_importante (7)

Instancia 2

lee contador_muy_importante (5)

añade 1 (6)

escribe contador_muy_importante (6)

1

Este solapamiento, donde lo que sucede depende del tiempo relativo de múltiples tareas, es llamado
condición de carrera. La parte de código que contenie al punto de concurrencia se llamado región crítica.
Y especialmente desde que Linux se empezó a ejecutar en máquinas SMP, se ha convertido en uno de los
puntos más grandes del diseño e implementación del núcleo.

Capítulo 1. Introducción

La solución es reconocer cuando ocurren estos accesos simultáneos, y usar bloqueos para asegurar que
sólo una instancia puede entrar en la región crítica en cada instante. Hay muchas primitivas amigables en
el núcleo Linux que te ayudan a hacer esto. Y entonces hay primitivas no amigables, pero yo intento que
no existan.

2

Capítulo 2. Dos Tipos Principales de Bloqueos
del Núcleo: Spinlocks y Semáforos

Hay dos tipos principales de bloqueos del núcleo. El tipo fundamental es el spinlock
(include/asm/spinlock.h), que es un bloqueo muy simple receptáculo-simple; si no puedes coger el
spinlock, entonces te mantienes intentándolo (spinning) hasta que puedas. Los spinlocks son muy
pequeños y rápidos, y pueden ser usados en cualquier sitio.

El segundo tipo es el semáforo (include/asm/semaphore.h): puede tener más de un receptáculo en
algún momento (el número se decide en tiempo de inicialización), aunque es usado más comúnmente
como un bloqueo de receptáculo-simple (un mutex). Si no puedes obtener el semáforo, tus tareas se
pondrán en una cola, y serán despertadas cuando el semáforo sea liberado. Esto significa que la CPU
hará algo mientras que estás esperando, pero hay muchos casos en los que simplemente no puedes
dormir (ver Sección 4.8), y por lo tanto tienes que usar un spinlock en vez del semáforo.

Ningún tipo de bloqueo es recursivo: ver Sección 4.2.

2.1. Bloqueos y Núcleos Monoprocesador

Para núcleos compilados sin CONFIG_SMP, los spinlocks no existen. Esta es una excelente decisión de
diseño; cuando nadie se puede ejecutar al mismo tiempo, no hay motivo para tener un bloqueo.

Deberías siempre de probar tu código de bloqueo con CONFIG_SMP habilitado, incluso si no tienes un
equipo de prueba SMP, porque aún así pillará algunos tipos (simples) de deadlock.

Los semáforos todavía existen, porque son requeridos para la sincronización entre contextos de usuario,
tal como veremos a continuación.

2.2. Variantes de Bloqueo Lectura/Escritura

Los spinlocks y los semáforos tienen variantes de lectura/escritura: rwlock_t y struct rw_semaphore.
Estos dividen a los usuarios en dos clases: lo