Shortest Remaining Time First: Java Multithreading

Question

I am trying to simulate CPU scheduling algorithms in java and am using multithreading. I have successfully implemented FCFS(First Come First Serve) and SJF(Shortest Job First). But the problem is when i start to think of SRTF(Shortest Remaining Time First) which is a preemptive form of SJF. I am using the following model:

• A thread for CPU, which has a CLOCK variable, which keeps ticking(a simple clock increment) every 100ms. I have a boolean isAvailable; flag for the processes to check if the CPU is available before starting execution.
• A thread for Long Term Scheduler(LTS), which pushes the process from the process list to a Ready Queue.
• A thread for Short Term Scheduler(STS), which takes a process from the ReadyQueue and assigns it to the CPU.
• Once a process is removed from the ReadyQueue by STS for execution, the process checks for the isAvailable flag of CPU. If true, it sets the flag to false and starts its execution (for which i am just making the thread to sleep for (100 * burstTime) ms as this is just a simulation). Otherwise, the process just keeps busy waiting : while(CPU.isAvailable != true);.

I have the list of processes along with their arrival and burst times before hand. It is ok till i am simulatiing non-preemptive scheduling(FCFS and SJF). But as i try for SRTF, I am unable to find a way to preempt the currently running process thread.

For SRTF, i know the way ahead to select the next process from ReadyQueue. I can try to set the isAvailable flag to false once i select a process from the queue, but then how am I to know which thread was originally executing? And since I am not using much of synchronization b/w threads, I will have multiple processes using the CPU thread. Its getting a little messed up. Please help. Thanks!

This is the code for a Process:

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

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

The code for 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 number 1 is that your shared state is not thread-safe. Even simple things like booleans need correct threading primitives to ensure visibility across threads (aka "volatile").