2012-10-01 32 views
5

Estoy tratando de simular algoritmos de programación de CPU en Java y estoy usando multihilo. Implementé con éxito FCFS (First Come First Serve) y SJF (Shortest Job First). Pero el problema es cuando empiezo a pensar en SRTF (Tiempo restante más corto primero) que es una forma preventiva de SJF. estoy usando el siguiente modelo:Tiempo restante más corto primero: Java multiproceso

  • un hilo para CPU, que tiene una variable CLOCK, que sigue avanzando (un simple incremento del reloj) cada 100ms. Tengo un indicador boolean isAvailable; para los procesos para verificar si la CPU está disponible antes de comenzar la ejecución.
  • Un hilo para el planificador a largo plazo (LTS), que empuja el proceso de la lista de procesos a una cola lista.
  • Un hilo para el programador a corto plazo (STS), que toma un proceso del ReadyQueue y lo asigna a la CPU.
  • Una vez que STS ha eliminado un proceso del ReadyQueue para su ejecución, el proceso busca el indicador isAvailable de la CPU. Si true, establece el indicador en falso e inicia su ejecución (para lo cual solo estoy haciendo que el subproceso duerma para (100 * burstTime) ms ya que esto es solo una simulación). De lo contrario, el proceso simplemente se mantiene ocupado esperando: while(CPU.isAvailable != true);.

Tengo la lista de procesos junto con sus tiempos de llegada y ráfaga antes de la mano. Está bien hasta que estoy simulando la programación no preventiva (FCFS y SJF). Pero cuando intento para SRTF, no puedo encontrar una manera de adelantarse al hilo del proceso en ejecución.

Para SRTF, sé el camino a seguir para seleccionar el siguiente proceso de ReadyQueue. Puedo intentar establecer el indicador isAvailable en false una vez que selecciono un proceso de la cola, pero ¿cómo puedo saber qué hilo se estaba ejecutando originalmente? Y dado que no estoy usando mucha sincronización b/w, tendré varios procesos usando el hilo CPU. Es un poco desordenado. Por favor ayuda. ¡Gracias!

Este es el código para un proceso:

enum State {ARRIVED, WAITING, READY, RUNNING, EXECUTED} 
public class Process implements Runnable 
{ 
    int pid; 
    int arrTime; 
int burstTime; 
int priority; 
long startTime; 
long endTime; 
State procState = null; 

Process(int pid, int arrTime, int burstTime, int priority) 
{ 
    this.pid = pid; 
    this.arrTime = arrTime; 
    this.burstTime = burstTime; 
    this.priority = priority; 
    this.procState = State.ARRIVED; 
    this.startTime = 0; 


    this.endTime = 0; /* I also considered adding a timeElapsedUnderExecution 
attribute to the process. So I can check after every cycle if the CPU is still available 
and keep incrementing the time elapsed. Once the timeElapsed becomes same as burstTime, i 
stop the process. Or if after a cycle, the CPU is not available, i know from where to 
resume my Process. Is this the way to go ? */ 

    } 

boolean isReady() 
{ 
    if((this.arrTime <= CPU.CLOCK) && (this.procState == State.ARRIVED)) 
     return true; 
    else return false; 
} 

@Override 
public void run() { 
    // TODO Auto-generated method stub 
    if(this.procState == State.READY) 
     this.procState = State.WAITING; 

    while(!CPU.isAvailable()); 

    try 
    { 
     this.procState = State.RUNNING; 
     System.out.println("Process " + pid + " executing..."); 
     this.startTime = CPU.CLOCK; 
     System.out.println("Process " + this.pid + ": Begins at " + this.startTime); 
     Thread.sleep(this.burstTime * 100); 
     this.endTime = CPU.CLOCK; 
     System.out.println("Process " + this.pid + ": Ends at " + this.endTime); 
     this.procState = State.EXECUTED; 

    } 
    catch (InterruptedException e) 
    { 
     // TODO Auto-generated catch block 
     System.out.println("Interrupted: " + pid); 
     e.printStackTrace(); 
    } 
    } 
} 

El código para CPU:

import java.util.LinkedList; 
    import java.util.Queue; 

    public class CPU implements Runnable 

{ 
    static Long CLOCK = new Long(0); 
    static LinkedList<Process> ReadyQ = new LinkedList<Process>(); 
private static boolean isAvailable = true; 
static boolean done = false; 

public static boolean isAvailable() { 
    return isAvailable; 
} 

public static void setAvailable(boolean isAvailable) { 
    CPU.isAvailable = isAvailable; 
} 

static void incrementCLOCK() 
{ 
    LTS.checkArrival(); 
    CPU.CLOCK++; 
    try { 
     Thread.sleep(100); 
    } catch (InterruptedException e) { 
     // TODO Auto-generated catch block 
     e.printStackTrace(); 
    } 
    System.out.println("Clock Tick: " + CPU.CLOCK); 
} 

@Override 
public void run() { 
    // TODO Auto-generated method stub 
    System.out.println("CPU starts.!!!"); 
    while(CPU.done != true) 
     synchronized(CPU.CLOCK) 
     { 
      incrementCLOCK(); 
      } 
    } 
} 

El código para LTS:

public class LTS implements Runnable 
{ 
    private static Process[] pList = null; 
    private final int NUM; 
    static Integer procStarted; 
    static Integer procFinished; 
    static boolean STSDone = false; 


LTS(Process[] pList, int num) 
{ 
    this.NUM = num; 
    LTS.pList = pList; 
} 

static void checkArrival() 
{ 
    if(pList == null) return; 
    for(int i = 0; i < pList.length; i++) 
     if(pList[i].isReady()) 
     { 
      pList[i].procState = State.READY; 
      System.out.println("Process " + pList[i].pid + " is now ready."); 
      CPU.ReadyQ.add(pList[i]); 
     } 
} 

@Override 
public void run() { 
    // TODO Auto-generated method stub 
    System.out.println("Long Term Scheduler starts.!!!"); 
    while(LTS.STSDone != true) 
    { 
     try { 
      Thread.sleep(100); 
     } catch (InterruptedException e) { 
      // TODO Auto-generated catch block 
      e.printStackTrace(); 
     } 
    } 
    System.out.println(LTS.STSDone); 
    System.out.println("LTS ends.!!!"); 
     CPU.done = true; 
    } 
} 
+0

necesita mostrar más código, específicamente CPU. – jtahlborn

+0

He agregado el código para 'CPU' y 'LTS'. – akaHuman

Respuesta

0

El problema número 1 es que su compartían estado no es seguro para subprocesos. Incluso las cosas simples como los booleanos necesitan primitivas de subprocesamiento correctas para garantizar la visibilidad entre subprocesos (también conocido como "volátil").

+0

¿Pueden dar más detalles al respecto? ¡Gracias! – akaHuman

+1

El tema es demasiado grande para elaborar aquí, me temo. Muchas personas recomiendan leer este libro: http://www.amazon.com/Java-Concurrency-Practice-Brian-Goetz/dp/0321349601 –

Cuestiones relacionadas