A - zimmcl/Programacion-Concurrente GitHub Wiki

Se descubre que el requisito básico para conseguir ofrecer procesos concurrentes es la capacidad de hacer imperar la exclusión mutua; esto es, la capacidad de impedir a cualquier proceso realizar una acción mientras se le haya permitido a otro.

En un sistema multiprogramado de procesador único, los procesos se entrelazan en el tiempo para ofrecer la apariencia de ejecución simultánea. Aunque no se consigue procesamiento paralelo real (y supone cierta sobrecarga en el cambio entre procesos), la ejecución entrelazada proporciona importantes beneficios en la eficiencia del procesamiento y en la estructuración de los programas. En un sistema de múltiples procesadores no sólo es posible entrelazar la ejecución de múltiples procesos sino también solaparlas.

Es necesario proteger las variables globales compartidas (así como otros recursos compartidos), controlando el código de acceso a la variable.

Clasificación en base al grado en que perciben la existencia de cada uno de los otros procesos.

• Procesos que no se perciben entre sí. Procesos independientes que no se pretende que trabajen juntos. Aunque no estén trabajando juntos, el SO necesita preocuparse de la competencia por recursos. El SO debe regular estos accesos.

• Procesos que se perciben indirectamente entre sí. Son procesos que no están necesariamente al tanto de la presencia de los demás mediante sus respectivos ID, pero que comparten accesos a algún objeto. Tales procesos exhiben cooperación en la compartición del objeto común.

• Procesos que se perciben directamente entre sí. Son procesos capaces de comunicarse entre sí vía ID y que son diseñados para trabajar conjuntamente en cierta actividad. Tales procesos exhiben cooperación.

{IMAGEN}

Los procesos concurrentes entran en conflicto entre ellos cuando compiten por el uso del mismo recurso. Si dos procesos desean ambos acceder al mismo recurso único, el SO reservará el recurso para uno de ellos, y el otro tendrá que esperar, siendo ralentizado.

En el caso de procesos en competencia, deben afrontarse tres problemas de control:

• Exclusión mutua. Al menos dos procesos requieren acceso a un recurso único no compartible. Nos referimos a tal recurso como recurso crítico, y a la porción del programa que lo utiliza como sección crítica. Es importante que sólo se permita un programa al tiempo en su sección crítica. La exclusión mutua crea dos problemas de control adicional:

• Interbloqueo. Ningún proceso libera el recurso que ya posee hasta haber conseguido el recurso que posea el otro proceso y haber realizado la función que requiere ambos recursos. Los dos procesos están interbloqueados.

• Inanición. Proceso al cual nunca se le asigna tiempo de procesamiento o acceso a los recursos que necesita.

Competencia entre procesos. Los procesos necesitarán ser capaces por sí mismos de expresar de alguna manera el requisito de exclusión mutua, como bloqueando el recurso antes de usarlo. Para aplicar la exclusión mutua se proporcionan dos funciones: entrarcritica(R) y salircritica(R). Cada función toma como un argumento el recurso sujeto a competencia. A cualquier otro proceso que intente entrar en su sección crítica mientras otro proceso está en su sección crítica, por el mismo recurso, se le hace esperar.

/*PROCESO 1*/						/*PROCESO N*/				
void P1							void PN
{							{
	while(true)						while(true)
	{							{
		/*Código anterior*/;				/*Código anterior*/;
		entrarcritica(Ra);				entrarcritica(Ra);
		/*Sección crítica*/;		...		/*Sección crítica*/;
		salircritica(Ra);				salircritica(Ra);
		/*Código posterior*/;				/*Código posterior*/;
	}							}
}							}

Cooperación entre procesos. Los procesos pueden usar y actualizar los datos compartidos sin referenciar otros procesos pero saben que otros procesos pueden tener acceso a los mismos datos. Así, los procesos deben cooperar para asegurar que los datos que comparten son manipulados adecuadamente.

Cualquier mecanismo o técnica que vaya a proporcionar exclusión mutua debería cumplimentar los siguientes requisitos:

1. Sólo se permite un proceso al tiempo dentro de su sección crítica, de entre todos los procesos que tienen secciones críticas para el mismo recurso u objeto compartido.
2. Un proceso que se pare en su sección no crítica debe hacerlo sin interferir con otros procesos.
3. No debe ser posible que un proceso que solicite acceso a una sección crítica sea postergado indefinidamente: ni interbloqueo ni inanición.
4. Cuando ningún proceso esté en una sección crítica, a cualquier proceso que solicite entrar en su sección crítica debe permitírsele entrar sin demora.
5. No se hacen suposiciones sobre las velocidades relativas de los procesos ni sobre el número de procesadores.
6. Un proceso permanece dentro de su sección crítica sólo por un tiempo finito.

Deshabilitar interrupción. En una máquina monoprocesador para garantizar la exclusión mutua, basta con impedir que un proceso sea interrumpido. Esta técnica puede proporcionarse en forma de primitivas definidas por el núcleo del sistema para deshabilitar y habilitar las interrupciones. Un proceso puede cumplir la exclusión mutua del siguiente modo.

while(true)
{
	/*deshabilitar interrupciones*/;
	/*Sección crítica*/;
	/*habilitar interrupciones*/;
	/*resto*/;
}

Dado que la sección crítica no puede ser interrumpida, se garantiza la exclusión mutua. Esta técnica degrada considerablemente el rendimiento del sistema porque impide el entrelazado de procesos.

Instrucciones máquina. El acceso a una posición de memoria excluye cualquier otro acceso a la misma posición. Con este fundamento, se han propuesto varias instrucciones máquina que llevan a cabo dos acciones atómicamente (único paso, sin interrupción) sobre una única posición de memoria con un único ciclo de búsqueda de instrucción. Durante la ejecución de la instrucción, el acceso a la posición de memoria se le bloquea a toda otra instrucción que referencie esa posición.

• Instrucción Test and Set Lock. TSL es una instrucción máquina que realiza dos acciones: leer el contenido de una palabra de la memoria en un registro y almacenar un valor distinto de cero en dicha palabra de memoria. Al tratarse de una instrucción máquina, el procesador nos garantiza que la instrucción TSL es realizada sin ningún tipo de interrupción por parte de otro proceso, es decir las operaciones de lectura y escritura de la palabra tienen la garantía de ser indivisibles. Además, si nos encontramos en un sistema multiprocesador, ninguno de los demás procesadores tendrá acceso a la palabra hasta que termine de ejecutarse la instrucción. El procesador que ejecuta la instrucción TSL cierra el bus de la memoria para prohibir a los demás el acceso a la memoria hasta el término de la instrucción.

/*Mecanica de funcionamiento de la instrucción*/

/*Cantidad de procesos*/
const int procesos = n;
int cerrojo;

bool testset(int i)
{
	if(i==0)
	{
		i=1;
		return true;
	}
	else
	{
		return false;
	}
}

void Proc(int i)
{
	while(true)
	{
		while(!testset(cerrojo))
		{
			/*Espera activa*/
		}
		/*SECCIÓN CRÍTICA*/
		cerrojo=0;
		/*Resto de código*/
	}
}

void main()
{
	cerrojo=0;
	paralelos(Proc(1), Proc(2), ... , Proc(n));
	return 0;
}

La construcción paralelos (Proc(1), Proc(2),…,Proc(n)) inicia la ejecución concurrente de los n procesos, suspendiendo temporalmente la ejecución del programa principal. Una variable compartida cerrojo se inicializa a 0. El único proceso que puede entrar en su sección crítica es aquél que encuentra la variable cerrojo igual a 0. Todos los otros procesos que intenten entrar en su sección crítica caen en un modo de espera activa, no pudiendo hacer nada hasta obtener permiso para entrar en su sección crítica salvo comprobar la variable cerrojo para conseguir entrar. Cuando un proceso abandona su sección crítica, restablece la variable cerrojo a 0; en este punto, a uno y sólo uno de los procesos en espera se le concederá accedo a su sección crítica.

• Instrucción Exchange. Intercambia los contenidos de las direcciones de memoria registro y memoria de forma atómica. Los protocolos para solucionar el problema de la exclusión mutua usando esta instrucción utilizan:

• Una variable compartida por todos los procesos que será la dirección de memoria inicializada en 0, en nuestra implementación la llamaremos cerrojo.
• Una variable local registro inicializada en 1, en nuestra implemetanción la llamaremos llave.

Mediante esta solución un proceso puede entrar en su sección crítica si encuentra la variable cerrojo en 0 y excluye a los demás procesos de la sección crítica poniendo a dicha variable a 1.

/*Mecanica de funcionamiento de la instrucción*/

/*Cantidad de procesos*/
const int procesos = n;
int cerrojo;

void exchange(int registro, int memoria)
{
	int temp;
	temp=memoria;
	memoria=registro;
	registro=temp;
}

void Proc(int i)
{
	int llave=1;
	while(true)
	{
		do
		{
			exchange(llave, cerrojo);
		}while(llave=0)
		/*SECCIÓN CRÍTICA*/
		exchange(llave, cerrojo);
		/*Resto de código*/
	}
}

void main()
{
	cerrojo=0;
	paralelos(Proc(1), Proc(2), ... , Proc(n));
	return 0;
}

1. Aplicable a cualquier número de procesos sobre mono/múltiples procesadores de memoria principal compartida.
2. Puede ser utilizado para dar soporte a múltiples secciones críticas. Cada sección puede ser definida por su propia variable.

1. Se emplea espera activa. Mientras un proceso está esperando para acceder a una sección crítica, continúa consumiendo tiempo de procesador.
2. Es posible la inanición. Cuando un proceso abandona su sección crítica y hay más de un proceso esperando, la selección del proceso en espera es arbitraria. Algún proceso podría denegársele indefinidamente el acceso.
3. Es posible el interbloqueo.