Me lo contaron y lo olvidé, lo leí y lo entendí, lo hice y lo aprendí.





lunes, 26 de septiembre de 2011

[Programación] Pseudo Ordenamiento de colas

EN un trabajo de la escuela tuve la "maravillosa" idea de usar una cola para el manejo de objetos. En su primera implementación tuvo éxito, pero después tuve la necesidad de usar la misma cola pero con los elementos ordenados de menor a mayor en base a cierto atributo... ¿Cómo hago eso sin alterar el funcionamiento de la cola? Bueno, pensé que si implementaba un método de ordenamiento de la cola y lo mandaba a llamar solo cuando necesitaba que la cola esté ordenada; justo de aquí surgió el verdadero problema: ¿Cómo ordenar una cola? Ya que el inicio de la cola no es forzosamente la posición 0 ni la posición final es la posición [tamaño_del_arreglo - 1]; puede empezar en cualquier posición y terminar en otra posición cualquiera y éstas posiciones varían durante toda la ejecución del programa. Entonces?
Es muy probable que se inventen millones de métodos para resolver este problema (dije probable); pero justo se me vino a la idea de que si necesito sacar los elementos en un orden, no es rotundamente necesario tener ordenada la cola, solo asegurarme que el objeto que voy a sacar es el más bajo (o más alto, según las necesidades) de la cola, ésto me simplifica muchas operaciones.

Bueno, comúnmente nosotros tenemos el método de sacar un objeto de la cola de la siguiente manera:

public Objeto sacarCola()
{
  Objeto a;
  if(delante<array.length-1)
  {
    delante++;
  }
  else
  {
    delante =0;
  }
  a=array[delante];  return a;
}

Vale, es sencillo y práctico, pero con unas cuantas correcciones se puede obtener una ilusión de ordenamiento de la cola para asegurarse de siempre sacar el objeto menor de la cola en cada vez.

Mi lógica es asegurarme en que el objeto en la posición delante sea el menor, de no ser así buscar el objeto que le sea menor y al final, que esté seguro de obtener el menor objeto, solo intercambio las posiciones del objeto menor con el del objeto en la posición delante.
Para lo anterior solo necesito hacer un recorrido desde el inicio del arreglo hasta el final y buscar cuál objeto es el menor de la cola.
Ahora, también es necesario no tomar en cuenta a los objetos que se suponen ya no deben estar en la cola (ésto por que es muy recurrido a no eliminarlos realmente de las cola, solo se excluyen). Ésto se arregla con que al sacar un objeto, lo ponga como NULL en la cola.

Mi algoritmo termina siendo el siguiente en un segundo método de sacar:

public Objeto sacarColaOrdenada()
{
  int referencia = delante;
  for(int i =0;i<array.length;i++)
  {
    if(array[i]!=NULL)
    {
      if(array[i]<array[referencia]
      {
        referencia = i;
      }
    }
  }


  Objeto intercambio;
  intercambio = array[delante];
  array[delante] = array[referencia]
  array[referencia] = intercambio;


   Objeto a;
  a=array[delante];
  array[delante]=null;
  if(delante<array.length-1)
  {
    delante++;
  }
  else
  {
    delante =0;
  }
  return a;
}

Parece complicado? Explico:
Lo que hago en el primer bloque (el for) es posicionar un indice de referencia (que servirá para indicar el supuesto objeto más bajo de valor) inicialmente en la posición delante. Luego con la variable i voy checando cada posición no nula (no nula por que más adelante, a la hora de sacar el objeto, lo elimino del array) si ésta posición es menor a la referencia, de ser así cambio la posición de referencia por la del índice y así me sigo hasta que termine el array.

En el segundo bloque solo hago el intercambio de objetos, el objeto en la posición delante se va a la posición que apunta referencia y viceversa.

La tercera parte es casi igual al método anterior de sacarCola salvo el detalle de que pongo como NULL la posición del objeto que voy a sacar para después no tomarlo en cuenta en próximas llamadas a la función.

Bueno, éste es mi método de Pseudo ordenamiento de colas, resulta económico para el procesador y versátil en cuestiones en donde no es realmente necesario tener la cola ordenada en todo momento.

jueves, 22 de septiembre de 2011

Política FCFS [Primero en entrar, primero en ser servido]

Esta política resulta ser la más sencilla, ya que consiste de 3 pasos:
1.- Ordenar los procesos por orden de llegada
2.- Resolver los instantes de finalización de los procesos
3.- Obtener los valores T,E,I con las fórmulas de esta política.

Ahora, debo aclarar que yo tengo mi clase de Procesos de esta manera:


class Proceso
    {
        public double instanteEntrada, tiempoEjecucion, t, e, i,instanteFinalizacion,tiempoEjecutado;
        int prioridad;
        public char[] nombre = new char[5];
        public Boolean dormido = true;


        public Proceso(char[] nombre, double instanteEntrada, double tiempoEjecucion,int prioridad)
        {
            this.nombre = nombre;
            this.instanteEntrada = instanteEntrada;
            this.tiempoEjecucion = tiempoEjecucion;
            this.t = 0;
            this.e = 0;
            this.i = 0;
            this.instanteFinalizacion=0;
            this.prioridad = prioridad;
        }
    }

Como ven, al crear un proceso recibe los valores: nombre, instanteEntrada, tiempoEjecucion y prioridad.
Ahora, tomando en cuenta que el instante de entrada es un número, resulta sencillo meter los procesos a un array y ordenarlos de menor a mayor de acuerdo a su instante de Entrada.

Proceso[] procesos = new Proceso(numero_de_procesos);
y voy agregando los procesos al arreglo:
procesos[0]= proceso;
procesos[1]= proceso2;
procesos[2]= proceso3;
..... //indefinidamente;
Luego se hace un ordenamiento con el método burbuja:
for(int i=0;i<procesos.Length-1;i++) //procesos.Lenght es la longitud del array en donde estan los procesos
{
  for(int j=i+1;j<procesos.Length;j++)
  {
    Proceso procesoTemp; //creo un objeto para guardar temporalmente los procesos
    if(procesos[j].instanteEntrada<procesos[i].instanteEntrada)
    {
      procesoTemp = procesos[j];
      procesos[j]=procesos[i];
      procesos[i]=procesoTemp;
    }
  }
}

Así tenemos en la posición 0 el primer proceso en entrar, y en la ultima posicion el ultimo proceso en entrar.
Falta calcular el instante de finalización:
Para la posición 0: instanteFinalizacion= instanteEntrada + tiempoEjecucion.
Para las siguientes posiciones
Si el instante de finalización del proceso anterior es igual o superior al instante de inicialización del proceso actual:

instanteFinalizacion = (instanteFinalización_procesoAnterior) + tiempoEjecución

Si no es así (si el proceso anterior acabó antes de que iniciara el actual)

instanteFinalización = (instanteEntrada + tiempoEjecución)


El resto de los valores (T,E,I) se calculan a partir de estos tres valores obtenidos.
Siento no ser más específico pero estoy con el tiempo encima