Kürzeste verbleibende Zeit zuerst: Java Multithreading

Question

Ich versuche, CPU-Scheduling-Algorithmen in Java zu simulieren und verwende Multithreading. Ich habe erfolgreich FCFS (First Come First Serve) und SJF (Shortest Job First) implementiert. Aber das Problem ist, wenn ich an SRTF (Shortest Remaining Time First) denke, was eine präventive Form von SJF ist. Ich verwende das folgende Modell:

• einen Thread für CPU, die eine CLOCK Variable hat, die (eine einfache Taktzunahme) jedes 100ms hält tickt. Ich habe ein boolean isAvailable; Flag für die Prozesse, um zu überprüfen, ob die CPU verfügbar ist, bevor die Ausführung gestartet wird.
• Ein Thread für Long Term Scheduler (LTS), der den Prozess von der Prozessliste in eine Ready Queue verschiebt.
• Ein Thread für den Short Term Scheduler (STS), der einen Prozess von der ReadyQueue übernimmt und ihn der CPU zuweist.
• Sobald ein Prozess aus der ReadyQueue von STS zur Ausführung entfernt wird, prüft der Prozess auf das Flag isAvailable der CPU. Wenn true, setzt es das Flag auf false und startet seine Ausführung (für die ich nur den Thread in den Ruhezustand für (100 * burstTime) ms machen, da dies nur eine Simulation ist). Ansonsten wartet der Prozess nur auf das Warten: while(CPU.isAvailable != true);.

Ich habe die Liste der Prozesse zusammen mit ihrer Ankunft und Burst Zeiten vor der Hand. Es ist in Ordnung, bis ich nicht präventive Planung (FCFS und SJF) simuliere. Aber wie ich für SRTF versuche, kann ich keine Möglichkeit finden, den aktuell laufenden Prozess-Thread vorzuziehen.

Für SRTF kenne ich den Weg zur Auswahl des nächsten Prozesses aus ReadyQueue. Ich kann versuchen, das isAvailable Flag auf false zu setzen, sobald ich einen Prozess aus der Warteschlange auswähle, aber wie soll ich dann wissen, welcher Thread ursprünglich ausgeführt wurde? Und da ich nicht viele Synchronisations-SW-Threads verwende, werde ich mehrere Prozesse verwenden, die den CPU-Thread verwenden. Es wird ein wenig durcheinander gebracht. Bitte helfen Sie. Vielen Dank!

Dies ist der Code für einen Prozess:

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

Der Code für die 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(); 
      } 
    } 
} 

Der Code für 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

Problem Nummer 1 ist, daß die gemeinsame Zustand ist nicht threadsicher. Selbst einfache Dinge wie Booleans benötigen korrekte Threading-Primitive, um die Sichtbarkeit über Threads sicherzustellen (auch bekannt als "volatile").