Práctica 03 - ProgProcesosYServicios/Practicas-2 GitHub Wiki

Práctica 2.3: Exclusión mutua: el algoritmo de Dekker (primer intento)

En la práctica 2.1 conseguimos un programa que sufría de condiciones de carrera continuamente) algo que nos permite probar nuestros intentos para evitarla.

La condición de carrera se producía porque el campo _suma era leído primero y modificado un rato después, dando la oportunidad a otra hebra a modiñcarlo entre medias, y que dicha modificación se perdiera. La solución es hacer uso de exclusión mutua sobre el campo _suma de manera que se garantice que únicamente una hebra esta utilizándola. Es decir, desde que se lee el valor (para pasarlo al método sumaN ) hasta que se establece el nuevo (cuando vuelve) nadie debe acceder al mismo tiempo al valor de _suma. La porción del código fuente durante el que se utiliza un recurso en exclusión mutua se llama sección critica. Lo que queremos, por tanto, es que el método run() de la clase de la práctica 2.1 sea algo así:

	public void run() {

		for (int i = 1; i <= NUM_VECES; ++i) {
			entradaSeccionCritica(numHebra);
			_suma = sumaN(_suma, NUMERO_SUMADO);
			salidaSeccionCritica(numHebra);
		}			

	} // run

de modo que se garantice que en la sección crítica sólo haya una hebra simultáneamente. El problema de la exclusión mutua es conseguir programar entradaSeccionCritíca() y salidaSeccíonCritica() sin hacer ningún tipo de suposición sobre el número de procesadores del sistema ni las velocidades relativas de las hebras.

Hay tres tipos de formas de afrontar el problema: por software, por hardware y con la ayuda del sistema Operativo (o del lenguaje). En ésta y las próximas prácticas veremos la primera solución por software conocida como el algoritmo de Dekker.

Este algoritmo es pedagógico porque suele presentarse de manera escalonada, y sirve para demostrar las dificultades que surgen en la programación concurrente. Pero no es útil en la práctica porque) entre otras cosas, exige conocer de antemano las hebras que cooperan y cuál esta entrando (o saliendo) en cada momento de la sección crítica. Esto nos lleva a tener que retocar el método run() a:

	public void run() {

		int numHebra;
		if (Thread.currentThread().getName().equals("Hebra0"))
			numHebra = 0;
		else
			numHebra = 1;
		
		for (int i = 1; i <= NUM_VECES; ++i) {
			entradaSeccionCritica(numHebra);
			_suma = sumaN(_suma, NUMERO_SUMADO);
			salidaSeccionCritica(numHebra);
		}

	} // run

Por su parte el programa principal tendrá que ajusta la creación de las hebras:

	public static void main(String[] args) throws InterruptedException {

		//...
                Thread t1, t2;
		
		t1 = new Thread(racer, "Hebra0");
		t2 = new Thread(racer, "Hebra1");

                 //...
       } // main

En el primer intento del algoritmo de Dekker se utiliza una variable (compartida) _turno que indica el identiñcador de la hebra que tiene el turno para entrar en la sección crítica. En entradaSeccíonCritíca(int) se hace una espera activa hasta que el turno sea el mismo que el identificador de nuestra hebra, y en salídaSeccionCritica(int) se modifica la variable del turno para cederlo a la hebra siguiente:

protected void entradaSeccionCritica(int numHebra) {

		while(_turno != numHebra);
		// ¡Nos toca!

	} // entradaSeccionCritica


	protected void salidaSeccionCritica(int numHebra) {
		
		int otraHebra = numHebra ^ 0x1;
		
		_turno = otraHebra;
		
	} // salidaSeccionCritica

	protected volatile int _turno = 0;

• Haz una copia del proyecto de la práctica 2.1 y renombra la clase principal a Dekker1.

• Modifica el método run() y el método main() como se ha descrito arriba.

• Añade los nuevos métodos y atributos protegidos.

• Ejecuta el programa varias veces (en multinúcleo) y comprueba que la condición de carrera ha desaparecido.

• Ejecuta el programa en un solo núcleo (con taskset o start / affinity). Comprueba la diferencia en velocidad. ¿A que es debido?

Con varios procesadores funciona, pero con uno se queda bloqueado porque están los dos pidiendo el turno

• El atributo _turno lo hemos declarado volatile. Quita este modificador y vuelve a probar la práctica. ¿Notas alguna diferencia?

Con varios procesadores funciona, pero con uno se queda bloqueado porque están los dos pidiendo el turno

• Para paliar la penalización de la espera activa, añade Thread.yield() en el interior del bucle del método entradaSeccionCritica().

• Esta primera solución software a la exclusión mutua funciona. ¿Qué problemas le ves?