Tempo più breve rimasto prima: Java Multithreading

Question

Sto provando a simulare gli algoritmi di schedulazione della CPU in java e sto usando il multithreading. Ho implementato con successo FCFS (First Come First Serve) e SJF (Shortest Job First). Ma il problema è quando inizio a pensare a SRTF (Shortest Remaining Time First) che è una forma preventiva di SJF. Sto usando il seguente modello:

• un thread per CPU, che ha una variabile CLOCK, che continua a ticchettare (un semplice incremento di clock) ogni 100ms. Ho un flag boolean isAvailable; per i processi per verificare se la CPU è disponibile prima di iniziare l'esecuzione.
• Un thread per Long Term Scheduler (LTS), che trasferisce il processo dall'elenco dei processi a una coda pronta.
• Un thread per Short Term Scheduler (STS), che accetta un processo da ReadyQueue e lo assegna alla CPU.
• Una volta che un processo viene rimosso da ReadyQueue da STS per l'esecuzione, il processo verifica il flag isAvailable della CPU. Se true, imposta il flag su false e inizia la sua esecuzione (per il quale sto semplicemente facendo in modo che il thread non funzioni per (100 * burstTime) ms in quanto si tratta solo di una simulazione). In caso contrario, il processo continua a essere occupato: while(CPU.isAvailable != true);.

Ho l'elenco dei processi insieme al loro arrivo e tempi di raffica prima mano. Va bene fino a quando simulo una pianificazione non preventiva (FCFS e SJF). Ma mentre provo per SRTF, non riesco a trovare un modo per anticipare il thread del processo attualmente in esecuzione.

Per SRTF, conosco la strada da percorrere per selezionare il processo successivo da ReadyQueue. Posso provare a impostare il flag isAvailable su false una volta selezionato un processo dalla coda, ma come posso sapere quale thread è stato originariamente in esecuzione? E poiché non sto usando molti thread di sincronizzazione in bianco e nero, avrò più processi usando il thread CPU. Sta diventando un po 'incasinato. Per favore aiuto. Grazie!

Questo è il codice per un processo:

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(); 
    } 
    } 
} 

Il codice per la 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(); 
      } 
    } 
} 

Il codice per la 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; 
    } 
} 

Answer 1

Problema numero 1 è che la vostra condiviso lo stato non è thread-safe. Anche le cose semplici come i booleani hanno bisogno di primitive di threading corrette per garantire la visibilità attraverso i thread (ovvero "volatile").