No es un bug, es una característica no documentada

martes, 15 de diciembre de 2015

Procesos y servicios. Procesos concurrentes

Esta sección ha sido extraída del libro Sistemas Operativos, de William Stallings.

Requisitos para la exclusión mutua

El uso adecuado de la concurrencia entre procesos exige la capacidad de definir secciones críticas y hacer cumplir la exclusión mutua. Esto es fundamental para cualquier esquema de proceso concurrente. Cualquier servicio o capacidad que dé soporte para la exclusión mutua debe cumplir los requisitos siguientes:
  1. Debe cumplirse la exclusión mutua: Sólo un proceso, de entre todos los que poseen secciones críticas por el mismo recurso u objeto compartido, debe tener permiso para entrar en ella en un instante dado.
  2. Un proceso que se interrumpe en una sección no crítica debe hacerlo sin estorbar a los otros procesos.
  3. Un proceso no debe poder solicitar acceso a una sección crítica para después ser demorado indefinidamente; no puede permitirse el interbloqueo o la inanición.
  4. Cuando ningún proceso está en su sección crítica, cualquier proceso que solicite entrar en la suya debe poder hacerlo sin dilación.
  5. No se pueden hacer suposiciones sobre la velocidad relativa de los procesos o su número.
  6. Un proceso permanece en su sección crítica sólo por un tiempo finito.

Hay varias formas de satisfacer los requisitos de exclusión mutua. Una manera es dejar la responsabilidad a los procesos que deseen ejecutar concurrentemente. Así pues, tanto si son programas del sistema como de aplicación, los procesos deben coordinarse unos con otros para cumplir la exclusión mutua, sin ayuda por parte del lenguaje de programación o del sistema operativo. Estos métodos se conocen corno soluciones por software. Aunque las soluciones por software son propensas a errores y a una fuerte carga de proceso, resulta útil estudiar estos métodos para tener un mejor entendimiento de la complejidad del proceso concurrente. Un segundo método propone el uso de instrucciones de la máquina a tal efecto. Estas tienen la ventaja de reducir la sobrecarga pero, sin embargo, no son interesantes. El tercer método consiste en dar algún tipo de soporte en el sistema operativo.

Exclusión mutua. Soluciones por software

Pueden implementarse soluciones de software para los procesos concurrentes que ejecuten en máquinas monoprocesador o multiprocesador con una memoria principal compartida. Formalmente, estas soluciones suponen que existe una exclusión mutua elemental en el acceso a memoria ([LAMP91]). Es decir, los accesos simultáneos (lecturas y/o escrituras) a la misma posición de memoria se hacen en serie, por medio de algún tipo de árbitro de memoria, aunque el orden en el que se conceden los accesos no se conoce por adelantado. Aparte de esto, no se requiere ningún soporte del hardware, del sistema operativo o del lenguaje de programación.

Algoritmo de Dekker

Dijkstra [DIJK65] presentó un algoritmo de exclusión mutua para dos procesos que diseñó el matemático holandés Dekker. Según Dijkstra, la solución se desarrolla por etapas. Este método tiene la ventaja de ilustrar la mayoría de los errores habituales que se producen en la construcción de programas concurrentes. A medida que se construya el algoritmo, se emplearán algunas ilustraciones pintorescas tomadas de Ben-Ari para escenificar la acción [BEN82].

Primer intento
Como se mencionó anteriormente, cualquier intento de exclusión mutua debe depender de algunos mecanismos básicos de exclusión en el hardware. El más habitual es la restricción de que sólo se puede realizar un acceso a una posición memoria en cada instante. Como metáfora de este arbitrio de la memoria, la figura 4.3 muestra el "protocolo del iglú". Tanto la entrada como el mismo iglú son tan pequeños que sólo puede entrar una persona a la vez en el iglú. Dentro, hay una pizarra en la que se puede escribir un único valor.




El protocolo es el siguiente. Un proceso (P0 o P1) que desee ejecutar su sección crítica entra primero en el iglú y examina la pizarra. Si su número está escrito en ella, el proceso puede abandonar el iglú y continuar con su sección crítica. En otro caso, abandona el iglú y se ve obligado a esperar. De vez en cuando, el proceso vuelve a entrar en el iglú para mirar la pizarra. Esta operación la repite hasta que se le permite entrar en su sección crítica. Este procedimiento se denomina espera activa porque un proceso frustrado no puede hacer nada productivo hasta que obtiene permiso para entrar en su sección crítica. En su lugar, debe persistir y comprobar periódicamente el iglú; así pues, consume tiempo del procesador (está activo) mientras espera su oportunidad.
Después de que un proceso haya obtenido acceso a su sección crítica y una vez que termine con ella, debe volver al iglú y escribir el número del otro proceso en la pizarra.

En términos formales, hay una variable global compartida:
var turno: 0 .. 1;

El programa para los dos procesos:


Esta solución garantiza el cumplimiento de la exclusión mutua. Hay dos inconvenientes en esta solución. Primero, los procesos deben alternarse de forma estricta en el uso de sus secciones críticas; así pues, el ritmo de ejecución viene dictado por el más lento. Si P0 usa su sección crítica sólo una vez por hora, pero P1 quiere usarla con una tasa de 1000 veces por hora, P1 está obligado a adoptar el ritmo de P0. Un problema mucho más serio es que si un proceso falla (por ejemplo, se lo come un oso polar en su camino hacia el iglú), el otro proceso se bloquea permanentemente. Esto es cierto tanto si un proceso falla en su sección crítica como fuera de ella.
La estructura anterior es la de una corrutina. Las corrutinas se diseñaron para poder pasar el control de la ejecución de un proceso a otro. Aunque es una técnica de estructuración útil para un solo proceso, no resulta apropiada para dar soporte al proceso concurrente.

Segundo intento
El problema de la primera tentativa es que se almacenaba el nombre del proceso que podía entrar en su sección crítica cuando, de hecho, lo que hace falta es tener información del estado de ambos procesos. En realidad, cada proceso debería tener su propia llave de la sección crítica para que, si un oso polar elimina a uno de ellos, el otro pueda seguir accediendo a su sección crítica.
Esta filosofía queda ilustrada en la figura 4.4. Cada proceso tiene ahora su propio iglú y puede mirar la pizarra del otro, pero no modificarla. Cuando un proceso debe entrar en su sección crítica, comprueba periódicamente la pizarra del otro hasta que encuentra escrito en ella "falso", lo que indica que el otro proceso no está en su sección crítica. Entonces, se dirige rápidamente hacia su propio iglú, entra y escribe "cierto" en la pizarra. El proceso puede ahora continuar con su sección crítica. Cuando deja su sección crítica, cambia su pizarra para que ponga "falso".

La variable global compartida es ahora:
var señal: array [0 .. 1] of booleano;

Que está inicializada con falso. El programa para los dos procesos es:



Ahora, si uno de los procesos falla fuera de la sección crítica, incluyendo el código para dar valor a las señales, el otro proceso no se queda bloqueado. De hecho, el otro proceso puede entrar en su sección crítica tantas veces como quiera, porque la señal del otro proceso está siempre puesta a falso. Sin embargo, si un proceso falla en su sección crítica, el otro proceso está bloqueado permanentemente.
En realidad, esta solución es, si acaso, peor que el primer intento, pues no siempre se garantiza la exclusión mutua. Considérese la siguiente secuencia:
  • P0 ejecuta la sentencia while y encuentra señal [1] a falso.
  • P1 ejecuta la sentencia while y encuentra señal [0] a falso.
  • P0 pone señal [0] a cierto y entra en su sección crítica.
  • P1 pone señal [1] a cierto y entra en su sección crítica.

Puesto que ambos procesos están en sus secciones críticas, el programa es incorrecto. El problema está en que la solución propuesta no es independiente de la velocidad de ejecución relativa de los procesos.

Tercer intento
El segundo intento falla porque un proceso puede cambiar su estado después de que el otro proceso lo ha comprobado pero antes de que pueda entrar en su sección crítica. Quizá se pueda arreglar este problema con un simple intercambio de dos líneas:


Como antes, si un proceso falla dentro de la sección crítica, incluyendo el código para dar valor a las señales que controlan el acceso a la sección crítica, el otro proceso se bloquea y si un proceso falla fuera de su sección crítica, el otro proceso no se bloquea.

A continuación, se comprobará que la exclusión mutua está garantizada desde el punto de vista del proceso P0. Una vez que P0 ha puesto señal [0] a "cierto", P1 no puede entrar a su sección crítica hasta que P0 haya entrado y abandonado la suya. Puede ser que P1 esté todavía en su sección crítica cuando P0 activa su señal. En ese caso, P0 se bloqueará en la sentencia while hasta que P1 deje su sección crítica. El mismo razonamiento es aplicable desde el punto de vista de Pl.

Esta solución garantiza la exclusión mutua, pero origina un problema más. Si ambos procesos ponen sus señales a "cierto" antes de que ambos hayan ejecutado la sentencia while, cada uno pensará que el otro ha entrado en su sección crítica. El resultado es un interbloqueo.

Cuarto intento
En el tercer intento, un proceso fijaba su estado sin conocer el estado del otro. El interbloqueo se produce porque cada proceso puede insistir en su derecho para entrar en la sección crítica; no hay opción para volver atrás desde esta situación. Se puede intentar arreglar esto haciendo que los procesos sean más educados: Deben activar su señal para indicar que de¬sean entrar en la sección crítica, pero deben estar listos para desactivar la señal y ceder la preferencia al otro proceso:


Esta solución se aproxima a la correcta pero todavía es defectuosa. La exclusión mutua aún está garantizada con un razonamiento similar al seguido en el estudio del tercer intento. Sin embargo, considérese la siguiente secuencia de sucesos:
  • P0 pone señal [0] a cierto
  • P1 pone señal [1] a cierto
  • P0 comprueba señal [1]
  • P1 comprueba señal [0]
  • P0 pone señal [0] a falso
  • P1 pone señal [1] a falso
  • P0 pone señal [0] a cierto
  • P1 pone señal [1] a cierto

Esta secuencia podría prolongarse indefinidamente y ningún proceso podría entrar en su sección crítica. Estrictamente hablando, esto no es un interbloqueo, porque cualquier cambio en la velocidad relativa de los dos procesos rompería este ciclo y permitiría a uno entrar en la sección crítica. Aunque no es probable que esta secuencia se mantenga por mucho tiempo, es una situación posible. Así pues, se rechaza el cuarto intento.

Una solución correcta
Hay que poder observar el estado de ambos procesos, que viene dado por la variable señal. Pero, como demuestra el cuarto intento, esto no es suficiente. De algún modo, se hace necesario imponer algún orden en la actividad de los dos procesos para evitar el problema de "cortesía mutua" que se acaba de observar. La variable turno del primer intento puede usarse en esta labor; en este caso, la variable indica qué proceso tiene prioridad para exigir la entrada a la sección crítica.


Es posible describir esta solución en términos de iglúes fijándose en la figura 4.5. Ahora hay un iglú "árbitro" con una pizarra llamada "turno". Cuando P0 quiere entrar en su sección crítica, pone su señal a "cierto". A continuación, va y mira la señal de P1. Si ésta está puesta a falso, P0 puede entrar inmediatamente en su sección crítica. En otro caso, P0 va a consultar al árbitro. Si encuentra el turno = 0, sabe que es momento de insistir y comprueba periódicamente el iglú de P1. Este otro se percatará en algún momento de que es momento de ceder y escribirá "falso" en su pizarra, permitiendo continuar a P0. Después de que P0 haya ejecutado su sección crítica, pone su señal a "falso" para liberar la sección crítica y pone turno a 1 para traspasar el derecho de insistir a P1.

La figura 4.6 ofrece una especificación del algoritmo de Dekker. La demostración se deja como ejercicio:

Algoritmo de Peterson

El algoritmo de Dekker resuelve el problema de la exclusión mutua pero con un programa complejo, difícil de seguir y cuya corrección es difícil de demostrar. Peterson [PETE81] ha desarrollado una solución simple y elegante. Como antes, la variable global señal indica la posición de cada proceso con respecto a la exclusión mutua y la variable global turno resuelve los conflictos de simultaneidad. El algoritmo se expone en la figura 4.7.


Se puede demostrar fácilmente que se cumple la exclusión mutua. Considérese el proceso P0. Una vez que ha puesto señal[0] a cierto, P1 no puede entrar en su sección crítica. Si P1 está aún en su sección crítica, señal[l] = cierto y P0 está bloqueado para entrar en su sección crítica. Por otro lado, se impide el bloqueo mutuo. Supóngase que P0 está bloqueado en su
bucle while. Esto significa que señal[1] es cierto y turno = 1. P0 puede entrar en su sección crítica cuando señal[l] se ponga a falso o cuando turno se ponga a 0. Considérense ahora los siguientes casos exhaustivos:
  • P1 no está interesado en entrar en su sección crítica. Este caso es imposible porque implica que señal[l]= falso.
  • P1 está esperando entrar en su sección crítica. Este caso es también imposible porque si turno = 1, P1 podrá entrar en su sección crítica.
  • P1 entra en su sección crítica varias veces y monopoliza el acceso a ella. Esto no puede pasar porque P1 está obligado a dar a PO una oportunidad poniendo turno a O antes de cada intento de entrar en su sección crítica.

Así pues, se tiene una solución simple al problema de la exclusión mutua para dos procesos. Es más, el algoritmo de Peterson se puede generalizar fácilmente al caso de n procesos [HOFR90].

Ejercicio Dekker / Peterson

Crea una clase para gestionar el saldo de una Cuenta. Debe tener métodos para obtener el saldo actual, hacer un ingreso (se incrementa al saldo), hacer un reintegro (se le resta al saldo), controlar si hay algún error, por ejemplo, si se hace un reintegro y no hay saldo; o si se hace un ingreso y el saldo supera el máximo; mostrar mensajes con los movimientos que se realicen. Si ocurre alguno de los errores anteriores finaliza el proceso. La cuenta recibe en su constructor el saldo actual y el valor máximo que puede tener. Los métodos de ingreso y reintegro deben definirse como synchronized.
Crea después la clase Persona que extienda Thread y que realice en su método run() ingresos y/o reintegros de forma aleatoria y con algún sleep(int tiempo) en medio; hasta que ocurra alguno de los errores nombrados anteriormente.

 Para determinar la cantidad a ingresar o retirar en cada movimiento genera números aleatorios entre una cantidad mínima (CANTIDADMIN) y una cantidad máxima (CANTIDADMAX) con la función random():

int cantidad = ((int) (Math.random()*(CANTIDADMAX - CANTIDADMIN) + CANTIDADMIN);

Para simular clientes muy activos, que van muchas veces al banco, y clientes tranquilos, genera otro número aleatorio para el tiempo que transcurrirá entre dos movimientos, TIEMPOMIN y TIEMPOMAX.

int tiempo = ((int) (Math.random()*(TIEMPOMAX - TIEMPOMIN) + TIEMPOMIN) * 1000; //En ms

Para simular personas ahorradoras y personas gastadoras utilizarás un parámetro que indique el tanto por ciento de  veces que hace ingresos (caracterAhorradorGastador)

int tipoMovimiento= ((int) (Math.random()*100 + 1);
if (tipoMovimiento < caracterAhorradorGastador)
movimiento = +1;     //A ingresar dinero
else
movimiento = -1;     //A retirar dinero

El constructor de la clase debe llevar el nombre de la persona, CANTIDADMIN, CANTIDADMAX, TIEMPOMIN, TIEMPOMAX, caracterAhorradorGastador.
Crea en el método main() un objeto Cuenta compartido por varios objetos Persona e inicia el proceso de realizar movimientos en la cuenta.

Implementar la solución usando los algoritmos de Dekker o Peterson (mínimo para dos clientes).

ARCHIVO CUENTA.JAVA

package CompruebaTuAprendizaje4;
import java.util.Vector;

public class Cuenta {

       // Propiedades
       private boolean[] bandera = new boolean[2];
       private int turno = 0;
       private int saldoActual;
       private int saldoMaximo;
      
       // Constructor
       public Cuenta(int saldoActual, int saldoMaximo){
             inicializarArray(bandera);
             this.saldoActual = saldoActual;
             this.saldoMaximo = saldoMaximo;
       }
      
       // Metodos
       public synchronized void ingresar(int cantidad, int turno, Persona ultimoCliente){
             bandera[turno] = true;
            
             if (turno == 0)
                    this.turno = 1;
             else
                    this.turno = 0;
            
             if (turno == 0){
                    while(bandera[1] && turno == 1){
                           try{
                                  Thread.sleep(300);
                           }
                           catch(InterruptedException e){}
                    } // Fin While
                   
                    // SECCION CRITICA
                    seccionCriticaIngreso(cantidad, ultimoCliente);
             } // Fin if Thread 0
            
             if (turno == 1){
                    while(bandera[0] && turno == 0){
                           try{
                                  Thread.sleep(300);
                           }
                           catch(InterruptedException e){}
                    } // Fin While
                   
                    // SECCION CRITICA
                    seccionCriticaIngreso(cantidad, ultimoCliente);
             } // Fin if Thread 1
             bandera[turno] = false;
             notifyAll();
       } // Fin ingresar
      
       public synchronized void retirar(int cantidad, int turno, Persona ultimoCliente){
             bandera[turno] = true;
            
             if (turno == 0)
                    this.turno = 1;
             else
                    this.turno = 0;
            
             if (turno == 0){
                    while(bandera[1] && turno == 1){
                           try{
                                  Thread.sleep(300);
                           }
                           catch(InterruptedException e){}
                    } // Fin While
                   
                    // SECCION CRITICA
                    seccionCriticaRetirada(cantidad, ultimoCliente);
             } // Fin if Thread 0
            
             if (turno == 1){
                    while(bandera[0] && turno == 0){
                           try{
                                  Thread.sleep(300);
                           }
                           catch(InterruptedException e){}
                    } // Fin While
                   
                    // SECCION CRITICA
                    seccionCriticaRetirada(cantidad, ultimoCliente);
             } // Fin if Thread 1
             bandera[turno] = false;
             notifyAll();
       } // Fin retirar
      
       private void inicializarArray(boolean[] array){
             array[0] = false;
             array[1] = false;
       }
      
       private void seccionCriticaIngreso(int cantidad, Persona ultimoCliente){
             if (saldoActual + cantidad <= saldoMaximo){
                    saldoActual = saldoActual + cantidad;
                    System.out.println(ultimoCliente.getNombre() + " ha ingresado " + cantidad + " euros");
             }
             else{
                    System.out.println(ultimoCliente.getNombre() + " ha superado el máximo permitido");
                    ultimoCliente.stop();
             }// Fin if zona critica
       }
      
       private void seccionCriticaRetirada(int cantidad, Persona ultimoCliente){
             if (saldoActual - cantidad >= 0){
                    saldoActual = saldoActual + cantidad;
                    System.out.println(ultimoCliente.getNombre() + " ha retirado " + cantidad + " euros");
             }
             else{
                    System.out.println(ultimoCliente.getNombre() + " ha superado el máximo permitido");
                    ultimoCliente.stop();
             } // Fin if zona critica
       }
      
}



ARCHIVO PERSONA.JAVA

package CompruebaTuAprendizaje4;

public class Persona extends Thread{

       // Propiedades
       private String nombre;
       private int numCliente;
       private Cuenta cuenta;
      
       // Constructor
       public Persona(String nombre, int numCliente, Cuenta cuenta){
             this.nombre = nombre;
             this.numCliente = numCliente;
             this.cuenta = cuenta;
       }
      
       // Métodos
       public void run(){
             while(true){
                    cuenta.ingresar(generarCifra(), numCliente, this);
                    try{
                           sleep(300);
                    }
                    catch(InterruptedException e){}
                   
                    cuenta.retirar(generarCifra(), numCliente, this);
                    try{
                           sleep(300);
                    }
                    catch(InterruptedException e){}
             } // Fin while
       } // Fin run
      
       public int generarCifra(){
             return (int) (Math.random()*500+1);
       }
      
       public String getNombre(){
             return nombre;
       }
}

ARCHIVO MAIN.JAVA

package CompruebaTuAprendizaje4;
import java.util.Vector;

public class Main {

       public static void main(String[] args) {
             Cuenta cuenta = new Cuenta(2000, 10000);
             Vector<Persona> gente = new Vector<Persona>();
             gente.addElement(new Persona("Inazio", 0, cuenta));
             gente.addElement(new Persona("Claver", 1, cuenta));
             for (int i = 0; i < gente.size(); i++){
                    gente.elementAt(i).start();
             }
       }
}

3 comentarios: