Simulación de procesos del SO

Si has estudiado, o estudias, sobre sistemas operativos te debe ser familiar terminos como procesos, los procesos o tareas (aplicaciones en ejecución) que lleva a cabo el CPU y son administrados desde el sistema operativo, los procesos se administran ya que no son secuenciales sino que se ejecutan en forma intercalada a traves de ranuras de tiempo.

La planificación de procesos es importante ya que dado el tiempo de ranura usado por cada proceso y la cantidad de procesos corriendo en un momento dara como resultado un mayor o menor gasto tiempo de tiempo en la ejecucion completa de los procesos, hay distintos tipos de planificación y hay varios algoritmos para ello.

En la materia de SO que lleve en 5to semestre vimos esto y para hacerlo mas claro soliamos hacer varios ejemplos de ejecución de un conjunto de procesos con un tiempo determinado usando los algoritmos FCFS, SJF y Round Robin.

Una de las tareas fue crear un programa que simule el funcionamiento de los algoritmos mencionados.

El programa se debia ejecutar desde linea de comandos de la siguiente manera:

SimulaPlanificacion [ -F | -S | -R num ] nombre_archivo

nombre_archivo indica un archivo de texto que contiene la información de los procesos a ejecutar en nuestra simulación por ejemplo:

1,0,7
2,2,4
3,4,1
4,5,4

Se encuentra por cada línea la siguiente informacion de un proceso: identificador, tiempo de llegada, tiempo de rafaga
El identificador es un entero, y los otros dos datos pueden ser enteros o reales.
Los argumentos: -F, -S y -R num indican:
-F Usar algoritmo FCFS (default)
-S Usa algoritmo SJF
-R num Usar algoritmo Round Robin con una ranura de tiempo de duracion num

La salida se debe mostrar con el formato (los datos corresponden a una ejecución con FCFS)

PROCESO	T_INICIO	T_FIN
1	0	7
2	7	11
3	11	12
4	12	16

Use java para crear ese programa ya que debido al uso de estructuras de datos necesario java me parecio la mejor opcion.

El programa de dos clases simulaPlanificacion y colaProcesos, aqui el código fuente:

// Simulador de ejecucion de procesos por algoritmos FCFS SJF y RoundRobin
import java.io.*; //Para lectura de archivo
import java.util.*; //Para manejo de una lista dinamica
import java.text.DecimalFormat; //Para redondeo a dos decimales al imprimir resultados

public class simulaPlanificacion{

  double datos[][]; //Para cargar los datos leidos desde el archivo, cada reglon de la matriz representa un proceso
  // y cada representa: la 1ra numero de proceso, la 2da tiempo de llegada del proceso y la 3ra rafaga del proceso
  DecimalFormat redondeo = new DecimalFormat("###.##"); //Para redondear numeros de resultados

  public static void main(String args[]){
    simulaPlanificacion sP = new simulaPlanificacion();
    int algoritmo=0; // Segun su valor indica el algoritmo a utilizar: 1=FCFS; 2=SJF; 3=RoundRobin 
    double RR_ranura=0; // Si el algoritmo es el round robin indica la ranura de tiempo a utilizar 
    String archivo=null; // Nombre del archivo de datos de entrada 
    if(args.length==0) sP.error(1); // Si no hay argumentos indicarlo y terminar el programa 
    // Se revisaran los argumentos 1x1 solo se aceptara el primer indicativo de tipo de algoritmo a
    // utilizar (si es el rr se esperara a continuacion el valor de la ranura de tiempo), cualquier otra cadena
    // se tomara como nombre del archivo y solo se aceptara la primera, si se encuentra un argumento extra o un
    // indicativo (cadena iniciada por -) se considerar error en los argumentos 
    for(int contador=0;contador<args.length;contador++){
      if(args[contador].charAt(0)=='-' && algoritmo==0){ //Asignando el parametro de algoritmo a ejecutar
        if(args[contador].equals("-F")) algoritmo=1;
 else if(args[contador].equals("-S")) algoritmo=2;
 else if(args[contador].equals("-R") && contador<(args.length-1)) algoritmo=3;
 else sP.error(2);
      }
      else if(args[contador].charAt(0)=='-' && algoritmo!=0) sP.error(2); //Error el algoritmo ya fue asignado
      else if(contador>0 && args[contador-1].equals("-R")){ //Si el anterior fue RoundRobin cargando tiempo de ranura
        try{
   RR_ranura=Double.valueOf(args[contador]).doubleValue();
 }
 catch(NumberFormatException err){
   sP.error(2); //Si el dato no esta o es erroneo indicarlo
 }
      }
      else if(archivo==null) //Aun no hay archivo y no fue una de las anteriores opciones cargar el parametro actual
        archivo=args[contador];
      else //Cualquier otro caso es por que hay un error en los parametros
        sP.error(2);
    }
    algoritmo=(algoritmo==0?1:algoritmo); // Si no habia algoritmo especificado indicar el FCFS 
    if(archivo==null) sP.error(2); // Si no habia archivo especificado mandar a error 
    sP.cargaDatosArchivo(archivo); //Mandar cargar los datos desde el archivo y llamar al algoritmo correspondiente
    if(algoritmo==1) sP.FCFS();
    else if(algoritmo==2) sP.SJF();
    else sP.RR(RR_ranura);
  }

  public void error(int n_error){ // Funcion para los mensajes de error posibles 
    if(n_error==1) System.out.println(" No hay argumentos");
    else if(n_error==2) System.out.println(" Error en los argumentos");
    else if(n_error==3) System.out.println(" No se pudo leer el archivo");
    System.exit(0); //Terminar la ejecucion del programa
  }

  public void cargaDatosArchivo(String dir){
    List listaTemp = new ArrayList(); //Usar lista dinamica para ir cargando los datos ya que no sabemos cuantos seran
    int listaTam=-1; //Para llevar un conteo de elementos que se insertan en la lista
    String reglon; //Para leer reglon x reglon del archivo
    try{ //Intentar leer abrir y leer el archivo capturar posibles excepciones
      FileReader ar = new FileReader(dir); //Declarando objeto archivo de lectura
      BufferedReader lineaArchivo = new BufferedReader(ar); //Declarando objeto buffer de lectura
      while((reglon=lineaArchivo.readLine())!=null && reglon.length()>1) {
        //Leer reglon mientras este exista y tenga contenido
        listaTemp.add(++listaTam,reglon); //Agregar la cadena obtenida a la lista
      }
      lineaArchivo.close(); //Cerrar buffer de lectura
      ar.close(); //Cerrar archivo
    }
    catch(java.io.IOException ex0){ //Si ocurrio una excepcion informar y terminar
      error(3);
    }
    datos = new double[listaTemp.size()][3]; //Indicar el tamaño de la matriz de datos segun los datos obtenidos en la lista
    for(int cnt=0;cnt<listaTemp.size();cnt++){ //Convertir los datos de la lista String a valores double y cargar en datos
      datos [cnt][0]=extraeVal(1,(String)(listaTemp.get(cnt)));
      datos [cnt][1]=extraeVal(2,(String)(listaTemp.get(cnt)));
      datos [cnt][2]=extraeVal(3,(String)(listaTemp.get(cnt)));
    }
  }

  public double extraeVal(int val, String orig){
    //Este metodo recibe una cadena y extrae tres valores double que esten separados por una coma regresa el valor indicado en val
    String aux=""; //Cadena auxiliar
    int cont=-1; //Contador para ir recorriendo la cadena caracter por caracter
    while(orig.charAt(++cont)!=',') aux+=orig.charAt(cont); //Recorrer hasta la 1ra coma
    if(val==1)  return Double.valueOf(aux).doubleValue(); //Si se solicito el 1er valor regresalo
    aux=""; //Si no borrar contenido de aux y cargar siguiente valor
    while(orig.charAt(++cont)!=',' ) aux+=orig.charAt(cont); //Recorrer hasta la 2da coma
    if(val==2)  return Double.valueOf(aux).doubleValue(); //Si solicito 2do valor regresarlo
    aux=""; //Si no borrar contenido de aux y cargar ultimo valor
    while(++cont <=orig.length()-1) aux+=orig.charAt(cont); //Recorrrer hasta el final
    return Double.valueOf(aux).doubleValue(); //regresar 3er valor
  }

  public void FCFS(){
    //Este metodo trabaja asi: ordenar los datos por su tiempo de llegada, 2da columna de la matriz, e ir imprimiendo cada uno de ellos con su respectivo tiempo de inicio y final
    double lineaT=0; //Manejar el valor de la linea de tiempo de ejecucion
    mergeSort(1,datos.length,1); //Ordenar la matriz datos por su segunda columna, tiempo de llegada
    System.out.println("PROCESO \tT_INICIO \t\tT_FIN"); //Imprimir encabezado
    for(int i=0;i<datos.length;i++){
      //Recorrer cada proceso y calcular e imprimir su tiempo de inicio y su tiempo de fin
      System.out.println(redondeo.format(datos[i][0])+"\t\t"+redondeo.format(lineaT)+"\t\t"+redondeo.format((lineaT+=datos[i][2])));
    }
  }

  public void SJF(){
    //Este metodo trabaja asi: 1-. ordenar los datos por su tiempo de llegada, 2da columna de la matriz, 2.- imprimir
    // el primer proceso ha llegado, 3.- segun el tiempo de ejecucion transcurrido ver que nuevos han llegado y ordenarlos
    // por su menor tiempo de rafaga, 3ra columna de la matriz 4.- repetir desde el paso 3 hasta terminar
    double lineaT=0; //Manejar el valor de la linea de tiempo de ejecucion
    int hanLlegado; //Saber que nuevos procesos han llegado al terminar x proceso y ordenarlos por tiempo de rafaga
    mergeSort(1,datos.length,1); //Ordenar la matriz datos por su segunad columna, tiempo de llegada
    System.out.println("PROCESO \tT_INICIO \t\tT_FIN"); //Imprimir encabezado
    for(int i=0;i<datos.length;i++){
      //Recorrer cada proceso y calcular e imprimir su tiempo de inicio y su tiempo de fin
      System.out.println(redondeo.format(datos[i][0])+"\t\t"+redondeo.format(lineaT)+"\t\t"+redondeo.format((lineaT+=datos[i][2])));
      hanLlegado=0; //Vamos quienes han llegado partamos del caso de que ningun proceso ha llegado en este tiempo
      for(int j=(i+1);j<datos.length;j++)
        if(datos[j][1]<=lineaT) hanLlegado=j; //Si se cumple esta condicion el proceso subindice j ha llegado
      if(hanLlegado>(i+1)) mergeSort(i+2,hanLlegado+1,2); //Si han llegado >=2 procesos ordenarlos por tiempo de ragafa
    }
  }

  public void RR(double ranura){
    colaProcesos cola = new colaProcesos(); //Usaremos una cola en este metodo
    double lineaT=0; //Manejar el valor de la linea de tiempo de ejecucion
    double[] prosActual; //Para cargar el proceso que se saque de la cola y que se valla a ejecutar
    int encolados=1; //Llevar el conteo de cuantos procesos han entrado a la cola
    mergeSort(1,datos.length,1); //Ordenar la matriz datos por su segunad columna, tiempo de llegada
    cola.encolar(datos[0][0],datos[0][2]); //mandar a la cola el primer proceso que ha llegado
    System.out.print("PROCESO \tT_INICIO \t\tT_FIN\n"); //Imprimir encabezado
    do{
      prosActual=cola.desencolar(); //Sacar de la cola el siguiente proceso que este listo
      //Calcular e imprimir su tiempo de inicio y si se ejecuta hasta el fin o solo el tiempo de ranura
      System.out.println(redondeo.format(prosActual[0])+"\t\t"+redondeo.format(lineaT)+"\t\t"+redondeo.format((lineaT+=(prosActual[1]>ranura?ranura:prosActual[1]))));
      //Buscar procesos que hayan llegado mientras se ejecutaba el anterior y mandarlos a la cola
      for(int i=encolados;i<datos.length;i++)
        if(datos[i][1]<=lineaT){
          cola.encolar(datos[i][0],datos[i][2]);
          encolados++;
        }
      //Si el ultimo proceso ejecutado no ha terminado aun mandarlo, con el tiempo de rafaga que le quede, a la cola
      if((prosActual[1]-ranura)>0) cola.encolar(prosActual[0],prosActual[1]-ranura);
    }while(cola.nElementos>-1); //Repetir mientras haya elementos en la cola
  }
  
//Lo siguiente es adaptacion del mergesort para que ordene la matriz datos por reglones basandose en cualquier columna
   public void mergeSort(int l, int r, int col){
    int q;
    if(l<r){
      q=(int)(Math.floor((l+r)/2));
      mergeSort(l,q,col);
      mergeSort(q+1,r,col);
      merge(l,q,r,col);
    }
  }
  public void merge(int l, int q, int r, int col){
    int i;
    int j;
    int k = 0;
    int n = r-l+1;
    double[][] B = new double[n][3];
    for(i=l;i<=q;i++){
      B[k][0] = datos[i-1][0];
      B[k][1] = datos[i-1][1];
      B[k++][2] = datos[i-1][2];
    }
    for(j=r;j>=q+1;j--){
      B[k][0]=datos[j-1][0];
      B[k][1]=datos[j-1][1];
      B[k++][2]=datos[j-1][2];
    }
    i = 1; j = n; k = l;
    while (i<=j)
      if (B[i-1][col]<=B[j-1][col]){
        datos[(k)-1][0] = B[(i)-1][0];
        datos[(k)-1][1] = B[(i)-1][1];
        datos[(k++)-1][2] = B[(i++)-1][2];
      }
      else{
        datos[(k)-1][0] = B[(j)-1][0];
        datos[(k)-1][1] = B[(j)-1][1];
        datos[(k++)-1][2] = B[(j--)-1][2];
      }
  }
}

Clase colaProcesos

import java.util.*;

public class colaProcesos{

  List listaComoCola = new ArrayList(); // Usare una lista dinamica como cola
  int nElementos; // Para llevar el conteo de los elementos que existan dentro de la cola

  colaProcesos(){
    nElementos=-1; // Al iniciar la cola esta vacia
  }

  public void encolar(double val1, double val2){ // Al encolar solo se agregan los nuevos elementos
    listaComoCola.add(++nElementos,""+val1);
    listaComoCola.add(++nElementos,""+val2);
  }

  public double[] desencolar(){
    double[] temp = new double[2];
    if(nElementos==0) return null;
    // Al desencolar se sacan los dos primero elementos
    temp[0]=Double.valueOf((String)(listaComoCola.get(0))).doubleValue();
    temp[1]=Double.valueOf((String)(listaComoCola.get(1))).doubleValue();
    // Luego los restantes se recorren dos posiciones hacia atras
    for(int i=0;i<(listaComoCola.size()-2);i+=2){
      listaComoCola.set(i,listaComoCola.get(i+2));
      listaComoCola.set(i+1,listaComoCola.get(i+3));
    }
    // Los dos elementos finales se borran
    listaComoCola.remove(listaComoCola.size()-2);
    listaComoCola.remove(listaComoCola.size()-1);
    nElementos-=2; // Se reasigna el valor de elementos dentro de la cola
    return temp; // Se regresan los valores sacados de la cola
  }
}