Práctica 2.10: Exclusión mutua: soluciones hardware

Las alternativas anteriores para garantizar la exclusión mutua son complicadas y están limitadas a dos procesos salvo que se añada aún más complejidad.

Otra Opción es hacer uso de soluciones hardware, es decir de capacidades de bajo nivel especíñcas que nos permitan entrar y salir de una sección crítica de una manera más sencilla y aun así se garantice el uso en exclusión mutua. La opción más drástica es, sencillamente, bloquear la multitarea. Para eso hay dos alternativas:

• Inhabilitar las interrupciones: en un sistema monoprocesador podemos anular las interrupciones y volverlas a habilitar alrededor de una sección crítica, de manera que evitamos cualquier posibilidad de que se ejecuten instrucciones externas a la hebra actual. En particular, anulamos la posibilidad de que entre el planificador, por lo que nadie más recibirá el procesador y será imposible que nadie entre en la sección crítica.

• Bloquear el bus de datos: la solución anterior no sirve en sistemas multiprocesador. En este caso, también se deberá bloquear el bus de datos mientras dure la sección crítica, de manera que el resto de procesadores no puedan acceder a memoria. Esto detendrá su ejecución, impidiendo, de nuevo, que hebras paralelas entren en la sección crítica.

Ambas soluciones son demasiado drásticas, porque anulan completamente la posibilidad de que otras hebras se ejecuten, incluso las que no tienen nada que ver con el recurso compartido que se protege. Además, esas instrucciones son demasiado delicadas como para que queramos que se puedan ejecutar desde modo usuario. El sistema operativo puede utilizarlas, internamente, para controlar rápida y fácilmente el acceso a sus recursos (por ejemplo, la cola de procesos) pero no es una opción válida para los procesos de usuario.

Una alternativa diferente es hacer uso de instrucciones específicas de la CPU. Algunas alternativas clásicas en la literatura son:

• Instrucción Test and set: es una instrucción de algunas plataformas que establece un valor en una posición de memoria de forma condicional al valor que tuviera previamente. El hardware garantiza que la secuencia de Operaciones lectura-escritura en memoria (si la condición se cumple) sera atómica para todas las CPUs. Normalmente la instrucción test and set se asume que pone a 1 una determinada posición de memoria si el valor original era 0, y nos dice si pudo o no realizar el cambio. En pseudocódigo:

boolean TestAndSet (int variable) {
// El parámetro se considera de entrada/salida
if (variable == 0){
variable = 1;
return true;
}
return false;
}

Instrucción de intercambiar: consiste en intercambiar el valor de un registro de la CPU por el valor de una posición de memoria. De nuevo, esto exige leer de memoria (para traer el dato) y escribir (para llevar el del registro), y el hardware garantiza el bloqueo del bus de datos para evitar interferencias de otros procesadores.

Haciendo uso de este tipo de instrucciones, se pueden programar versiones particulares de nuestros métodos de entrada y salida de la sección crítica) de manera que el resto de hebras no relacionadas con el recurso que se comparte puedan continuar. Para eso, hay que cambiar el modelo, acercándonos al funcionamiento de los semáforos que veremos más adelante.

En concreto, en lugar de intentar resolver el problema de la exclusión mutua desde el punto de vista de las hebras (quién tiene el turno, y si quiere o no una hebra entrar en la sección crítica) pasamos a verlo desde el punto de vista de los recursos. Tendremos una variable _cerro jo que indica si hay alguien usando en este momento el recurso compartido 0 no. La variable valdrá 1 si nadie la está usando y 0 si está en uso. Esta asignación es contraria al funcionamiento habitual de los booleanos, pero encaja mejor con el funcionamiento clásico de la instrucción Test and set.

• Haz una copia del proyecto de la práctica 2.3. Renombra la clase principal a TestAndSet.

• Los métodos de entrada y salida de la sección crítica ya no necesitan saber que hebra quiere entrar o salir, debido al cambio de filosofía. Elimina el parámetro pasado en el método run (); también puedes (aunque no es necesario) quitar el establecimiento del nombre en la creación de las hebras.

• Renombra el atributo _turno por _cerrojo, y programa las nuevas versiones de los métodos de entrada y salida de la sección crítica:

protected void entradaSeccionCritica() {

		while(!testAndSet())
			;
		
	} // entradaSeccionCritica

	protected void salidaSeccionCritica() {
		
		_cerrojo = 0;
		
	} // salidaSeccionCritica

protected boolean testAndSet() {
		if (_cerrojo == 0) {
			_cerrojo = 1;
			return true;
		}
		return false;
	}

Prueba la práctica sobre un único procesador) y sobre varios. ¿Funciona?

Es muy probable que con un solo procesador te haya funcionado bien, pero que no lo haya hecho con varios. El problema esta en el if de la línea 15; puede ocurrir que dos hebras comprueben ¿ la vez el estado del atributo _cerrojo, lo vean en 0 y lo pongan los dos en 1, entrando a la vez en la sección crítica.

Es por esto por lo que es muy importante que la instrucción Test and set sea atómica. Java proporciona el paquete java.util.concurrent.atomic desde la versión 1.5. Contiene una serie de clases con Operaciones que en- vuelven valores volatile y los dotan de operaciones atómicas tal y como necesitamos aquí. Por ejemplo) la clase AtomicInteger tiene un método compareAndset() que es, en esencia, similar a la instrucción Test and set mencionada antes, pero con la posibilidad de especificar el valor esperado y el nuevo (en lugar de que tengan que ser 0 y 1 respectivamente). Las implementaciones de los métodos hacen uso de código nativo que podría terminar usando instrucciones máquina específicas (y rápidas).

1.- Modifica el código de la práctica para que en lugar de utilizar una variable de tipo entero se utilice un AtomicInteger, que comience con el valor 0.

2.- Adapta el método de salida de la sección crítica tras el cambio del tipo de _cerrojo.

3.- Modifica el método testAndSet() para que utilice el método mencionado, compareAndSet(), de la clase AtomicInteger.

protected void salidaSeccionCritica() {
		
		_cerrojo.set(0);
		
	} // salidaSeccionCritica


	protected boolean testAndSet() {
		
		// Java garantiza atomicidad en esta operación.
		return _cerrojo.compareAndSet(0,1);

	}

	protected AtomicInteger _cerrojo = new AtomicInteger(0);

4.- Prueba el programa. ¿Funciona ahora?