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:
- 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.
- Un proceso que se interrumpe en una sección no crítica debe hacerlo sin estorbar a los otros procesos.
- 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.
- 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.
- No se pueden hacer suposiciones sobre la velocidad relativa de los procesos o su número.
- 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();
}
}
}
0 comentarios:
Publicar un comentario