<?php

/**************************************************************/
/*                                                            */
/* Programa ejemplo de una red de colas						  */
/* Tiempos entre llegadas uniformes                           */
/* Tiempos de servicio uniformes                              */
/*                                                            */
/* La topología se ve en la siguiente figura:				  */
/*
								 ------   /-\
							/----|    |--|   |--------->
                           /     ------   \-/
    ----|   /-\          p/
-->-    |--|   |----------
 |  ----|   \-/        1-p\
 |	                       \     ------   /-\     1-q
 ^	                        \----|    |--|   |---|----->
 |								 ------   \-/    |q
 |	                                             v
 |-----------------------------------------------|
															  */
/* Donde hay una cola primera, infinita a la que llegan las   */
/* llegadas externas. El tiempo de servicio ahí es uniforme.  */
/* Las salidas de esa cola se reparten entre otras dos.		  */
/* Las dos colas siguientes tienen cola finita. Los tiempos   */
/* de servicio de las otras dos colas son diferentes, también */
/* uniformemente distribuidos (no mantiene el tiempo de		  */
/* de servicio que tuvo en la primera cola.					  */
/* Los que salen de una de ellas terminan ahí pero los de la  */
/* otra tienen una probabiliad de regresar a la cola inicial. */
/*                                                            */
/* Se puede hacer con menos tipos de eventos que los		  */
/* empleados, pero parece más claro así.					  */
/*                                                            */
/**************************************************************/

	
/**************************************************************/
/* Funciones para gestionar la lista de eventos futuros (FEL) */

/* Cada evento es un array asociativo con 2 elementos:        */
/* 'tiempo': El instante de tiempo en que se produce          */
/* 'tipo':   El tipo de evento  (una cadena de texto)         */
/* Estas funciones solo requieren el elemento 'tiempo'        */
    
/* La FEL es simplemente un array con los eventos pero esto   */
/* es transparente al usuario, queda encapsulado en estas     */
/* funciones                                                  */
    
/* Crea, inicializa y devuelte la estructura de una nueva FEL */
function newFEL() {
	$FEL = array();
	return $FEL;
}

/* Función que devuelve el evento inminente de la FEL y lo    */
/* retira de la misma                                         */
/* Se recorre todo el array buscando el de menor instante de  */
/* tiempo. Es poco eficiente pero funciona                    */
function getEventoInminente(&$FEL) {
	if (count($FEL) == 0) return NULL;
	$inminente = -1;
	foreach ($FEL as $clave => $evento) {
		if ($inminente == -1) $inminente = $clave;
		else if ($evento['tiempo'] < $FEL[$inminente]['tiempo']) $inminente = $clave;
	}

	$eventoInminente = $FEL[$inminente];
	unset($FEL[$inminente]);

	return $eventoInminente;
}

/* Función para añadir un evento a la FEL                     */
/* Es trivial pero esto permite cambiar la implementación de  */
/* la FEL sin tener que tocar el resto del código.            */
function addEvento(&$FEL, $evento) {
	$FEL[] = $evento;
}

/* Fin de las funciones de gestión de la FEL                  */
/**************************************************************/


/* Función para generar tiempos entre llegadas o tiempos de   */
/* servicio. Simplemente genera un valor de una v.a. uniforme */
/* Los argumentos son el mínimo y el máximo de la v.a.        */
function getUniforme($minimo, $maximo) {
    $alea = mt_rand();
    return ($alea/mt_getrandmax())*($maximo-$minimo)+$minimo;
}

    
/** Inicializaciones **/

/* Datos de la simulación */
$min_tinter = 0.01; 	// Tiempo entre llegadas uniforme entre $min_tinter y $max_tinter. Todos los tiempos en las mismas unidades (las que sean)
$max_tinter = 0.09; 	//
$min_tserv1 = 0.01; 	// Tiempo de servicio en el primer servidor, uniforme entre $min_tserv1 y $max_tserv1
$max_tserv1 = 0.05; 	//
$propReparto = 0.3;     // Proporción de salidas de la primera cola que va a la segunda, el resto va a la tercera
$retAserv2 = 0.1;       // Retardo entre que se sale del servidor 1 y se llega al servidor 2
$retAserv3 = 0.2;       // Retardo entre que se sale del servidor 1 y se llega al servidor 3
$min_tserv2 = 0.01; 	// Tiempo de servicio en el segundo servidor, uniforme entre $min_tserv2 y $max_tserv2
$max_tserv2 = 0.05; 	//
$min_tserv3 = 0.01; 	// Tiempo de servicio en el tercer servidor, uniforme entre $min_tserv3 y $max_tserv3
$max_tserv3 = 0.05; 	//
$max_enServ2 = 2;       // Máximo número de clientes en el servidor 2 (cola+servidor). Es decir, tiene cola finita
$max_enServ3 = 4;       // Máximo número de clientes en el servidor 3 (cola+servidor). Es decir, tiene cola finita
$propRetorno = 0.5;		// Proporción de clientes que terminan en el servidor 3 e inmediatamente vuelven al servidor 1
    
$max_llegadas = 100000;	// Máximo número de llegadas a simular


/* Variables para cálculos estadísticos durante la simulación */
$acum_tespera = 0;      // Acumula los tiempos de espera en cola para calcular el tiempo medio
$acum_tenSistema = 0;	// Acumula los tiempos totales en el sistema para calcular al final la media
$acum_tservir = 0;      // Idem con los tiempos de servicio
$perdidosEnServ2 = 0;   // Número de llegadas al servidor 2 que se pierden
$perdidosEnServ3 = 0;   // Número de llegadas al servidor 3 que se pierden
$llegadasAServ2 = 0;    // Número de llegadas al servidor 2
$llegadasAServ3 = 0;    // Número de llegadas al servidor 3

/* Variables para describir el estado del sistema */
$ensistema1 = 0;                            // Número de clientes que hay en el primer sistema
$ensistema2 = 0;                            // Número de clientes que hay en el segundo sistema
$ensistema3 = 0;                            // Número de clientes que hay en el tercer sistema
$evt_inicial['tipo'] = "llegada externa";	// Un evento de llegada inicial
$evt_inicial['tiempo'] = getUniforme($min_tinter, $max_tinter);	// El instante de la primera llegada
$FEL = newFEL();
addEvento($FEL, $evt_inicial);		// La FEL (Future Event List) inicializada con un primer evento de llegada

$tSalidaAnteriorSistema1 = 0;   // Inicialización de cuándo se vacía el servidor primero
$tSalidaAnteriorSistema2 = 0;   // Inicialización de cuándo se vacía el servidor segundo
$tSalidaAnteriorSistema3 = 0;   // Inicialización de cuándo se vacía el servidor tercero

$CLOCK = 0;	// Reloj de la simulación

$numLlegadasProcesadas = 0;

/** Fin de inicializaciones **/


/** Bucle de eventos (event loop) **/

while (1) {

	/****************************************************/
	/** Obtener el siguiente evento y actualizar CLOCK **/
	/****************************************************/
	
	$eventoInminente = getEventoInminente($FEL);
	$CLOCK = $eventoInminente['tiempo'];

    /************************/
	/** Procesar el evento **/
	/************************/
	
	if (($eventoInminente['tipo'] == "llegada externa")||($eventoInminente['tipo'] == "llegada retornada")) {
	
		// Es una llegada al primer servidor
		
		// Crear la salida correspondiente
		$tServirLlegada = getUniforme($min_tserv1, $max_tserv1); // Tiempo de servicio
		$tSalida = ($CLOCK>$tSalidaAnteriorSistema1)?($CLOCK+$tServirLlegada):($tSalidaAnteriorSistema1+$tServirLlegada); // Instante en que se producirá la salida
		$evt_nuevo['tipo'] = "salida de servidor 1";
		$evt_nuevo['tiempo'] = $tSalida;
		addEvento($FEL, $evt_nuevo);
		
		// Apuntar estadisticas
		$t_espera = $tSalida - ($CLOCK + $tServirLlegada);
		$acum_tespera += $t_espera;
		$acum_tservir += $tServirLlegada;

		// Crear nueva llegada para mantener vivo el sistema, pero solo si es una llegada externa
		if ($eventoInminente['tipo'] == "llegada externa") {
			$tinter = getUniforme($min_tinter, $max_tinter);
			$t_lleg = $CLOCK + $tinter;
			$evt_nuevo['tipo'] = "llegada externa";
			$evt_nuevo['tiempo'] = $t_lleg;
			addEvento($FEL, $evt_nuevo);
		}
		
		// Más modificacion del estado del sistema
		$ensistema1++;
		
		// Apuntar estadisticas
		$acum_tenSistema += $ensistema1;

		$numLlegadasProcesadas++;
        $tSalidaAnteriorSistema1 = $tSalida;
		
		if ($numLlegadasProcesadas % 1000 ==0) echo "Procesando... llevamos $numLlegadasProcesadas llegadas, ahora hay $ensistema1 en la cola 1, $ensistema2 en la cola 2 y $ensistema3 en la cola 3\n";


	} else if ($eventoInminente['tipo'] == "salida de servidor 1") {
	
		// Es una salida del primer servidor y se puede ir al segundo o al tercero
		
		// Modificación del estado del sistema
		$ensistema1--;
        
        // ¿Va al servidor 2 o al 3?
        if (getUniforme(0,1) < $propReparto) {
            // Va al servidor 2
            // Creamos una llegada al servidor 2 que se produce tras el tiempo de propagación hasta él
            $evt_nuevo['tiempo'] = $CLOCK + $retAserv2;
            $evt_nuevo['tipo'] = "llegada a servidor 2";
            addEvento($FEL, $evt_nuevo);
        } else {
            // Va al servidor 3
            // Creamos una llegada al servidor 2 que se produce tras el tiempo de propagación hasta él
            $evt_nuevo['tiempo'] = $CLOCK + $retAserv3;
            $evt_nuevo['tipo'] = "llegada a servidor 3";
            addEvento($FEL, $evt_nuevo);
        }
	
    } else if ($eventoInminente['tipo'] == "llegada a servidor 2") {
        
        // Es una llegada al segundo servidor
        $llegadasAServ2++;
        
        if ($ensistema2 >= $max_enServ2) $perdidosEnServ2++; // Se pierde, lo contamos
        else {
            // Cabe
			// Modificación del estado del sistema
			$ensistema2++;
			// Creamos la salida correspondiente
			$tServirLlegada = getUniforme($min_tserv2, $max_tserv2); // Tiempo de servicio. De nuevo al azar. ¿Cómo se podría hacer para que fuera el mismo de antes o al menos proporcional?
			$tSalida = ($CLOCK>$tSalidaAnteriorSistema2)?($CLOCK+$tServirLlegada):($tSalidaAnteriorSistema2+$tServirLlegada); // Instante en que se producirá la salida
			$evt_nuevo['tipo'] = "salida de servidor 2";
			$evt_nuevo['tiempo'] = $tSalida;
			addEvento($FEL, $evt_nuevo);
			$tSalidaAnteriorSistema2 = $tSalida;
        }
	} else if ($eventoInminente['tipo'] == "llegada a servidor 3") {
		
		// Es una llegada al tercer servidor
		$llegadasAServ3++;

		if ($ensistema3 >= $max_enServ3) $perdidosEnServ3++; // Se pierde, lo contamos
		else {
			// Cabe
			// Modificación del estado del sistema
			$ensistema3++;
			// Creamos la salida correspondiente
			$tServirLlegada = getUniforme($min_tserv3, $max_tserv3); // Tiempo de servicio. De nuevo al azar.
			$tSalida = ($CLOCK>$tSalidaAnteriorSistema3)?($CLOCK+$tServirLlegada):($tSalidaAnteriorSistema3+$tServirLlegada); // Instante en que se producirá la salida
			$evt_nuevo['tipo'] = "salida de servidor 3";
			$evt_nuevo['tiempo'] = $tSalida;
			addEvento($FEL, $evt_nuevo);
			$tSalidaAnteriorSistema3 = $tSalida;
		}
	} else if ($eventoInminente['tipo'] == "salida de servidor 2") {
		
		// Es una salida del segundo servidor
		
		// Modificación del estado del sistema
		$ensistema2--;
		
	} else if ($eventoInminente['tipo'] == "salida de servidor 3") {
		
		// Es una salida del tercer servidor

		// Modificación del estado del sistema
		$ensistema3--;

		// Una fracción de ellos vuelve al primer servidor
		if (getUniforme(0,1) < $propRetorno) {
			// Creamos un evento de llegada en este mismo instante
			$evt_nuevo['tipo'] = "llegada retornada";
			$evt_nuevo['tiempo'] = $CLOCK;
			addEvento($FEL, $evt_nuevo);
		}
		
	} else echo "Evento no soportado! (esto no deberia suceder)\n";
	
	// Condicion de terminacion de la simulacion
	if ($numLlegadasProcesadas >= $max_llegadas) break;
	
}
	
print "Tiempo medio de espera en el primer servidor: ".($acum_tespera/$max_llegadas)." unidades de tiempo\n";
print "Numero medio de clientes en el primer servidor: ".($acum_tenSistema/$max_llegadas)." \n";
print "Utilizacion del primer servidor: ".(100*$acum_tservir/$CLOCK)." %\n";

if ($llegadasAServ2 > 0) print "Porcentaje de perdidas en servidor 2: ".(100*$perdidosEnServ2/$llegadasAServ2)." %\n";
if ($llegadasAServ3 > 0) print "Porcentaje de perdidas en servidor 3: ".(100*$perdidosEnServ3/$llegadasAServ3)." %\n";

?>