Shortest job remaining

Programming Assignment

Objective
To implement Thread scheduling on the OSP2 simulator using a version of the Shortest Job
Remaining strategy with ageing. You will implement the module ThreadCB.java to further
your understanding of CPU scheduling.

Building and Executing the Simulation
Copy your files fromthe previous cpu scheduling project and starting with that version of ThreadCB.java modifyit to create the SJR solution. The only file you should have to modify is ThreadCB.java.
Modifying the other files will probably “break” OSP2.
The only changes you need to make to your code from the previous project are:
1) Each time you change the status of a thread from ThreadRunning to any other state, you
will estimate the cpu burst time using exponential averaging (tn = atn-1 + (1-a)tn-1). Use
an alpha value of 0.75, i.e., tn=0.75tn-1+0.25tn-1 . If tn < 5 then set tn = 5. To make this
work you will need to keep track of the last cpu burst for the thread. You will also need to
keep track of the last estimate of the burst time. Do this by adding additional variables to
the ThreadCB class:

  1. intlastCpuBurst (this is tn-1 in the equation)
    intestimatedBurstTime (this is tin the equation)
    c. long lastDispatch (you need this to compute lastCpuBurst)
    When you first create a thread you should initialize the values of lastCpuBurst and
    estimatedBurstTime to 10. The reason for initializing these values is that there are no
    previous values of tn-1 and tn-1 that you can use to compute estimatedBurstTime.
    2) In order to estimate the burst time, you need the value of lastCpuBurst. Each time you
    change the status of a thread from ThreadRunnig to some other state you should calculate
    the value of lastCpuBurst and save it in this variable. You calculate the value using the
    following equation:
    thread.lastCpuBurst = HClock.get() – thread.lastDispatch;
    As you can see, you will need the value of lastDispatch in order to do this. Be sure to set
    this variable each time you dispatch a new thread, i.e., thread.lastDispatch = HClock.get()
    just before returning from do_dispatch.
    3) Be sure to save the estimated burst time into the class variable estimatedBurstTime.
    4) When your do_dispatch()is invoked, after checking whether there was a thread
    running (and calculating how much time is remaining for that thread by taking the
    difference of the current time, HClock.get() and the lastDispatch time of that thread), you
    will check the ready queue to see if there is a thread that has a shorter remaining burst
    time. If the remaining burst time for the current thread is as short or shorter than theestimated burst time of the threads in the ready queue then continue with the current
    thread and return SUCCESS. Or if the current burst of the current thread is less than 2
    milliseconds, then continue with the current thread. In this case, do not change the value
    of lastDispatch since you are continuing to run the current thread. Otherwise, preempt the
    current thread and dispatch the thread in the ready queue with the shortest estimated burst
    time and return SUCCESS. In this case be sure to update lastDispatch for this new thread.
    If there is no current thread running and no threads are available in the ready queue then
    set PTBR=NULL and return FAILURE.
    5) Since we are not doing round robin, DO NOT SET THE TIMER.
    6) Ageing: every time you check the ready queue for a thread to dispatch, decrement the
    estimated burst time for each of the threads in the ready queue by one. If t< 5 then set t
    = 5. The reason for ageing is that we want to ensure that even threads with large
    estimated burst time eventually get scheduled.
    Some more hints:
    • The outlined algorithm for the solution to CPU scheduling is derived from a discussion inyour OSP2 book regarding the thread scheduling module ThreadCB. Your OSP2 book
    (and the Silberschatz book) are your best references for conceptual questions onimplementation of ThreadCB.java.
    • Be very careful that you do not leave a thread in the ready queue when it is dispatched. Ifyou do, and then re-insert it after a block, the queue may become disconnected, making
    some ready threads inaccessible. These stranded threads can never be re-scheduled, so
    threads may starve in the ready queue.
    Write up
    You must include with your code a one page write up of how you accomplished your assignment. In this write-up, you shoulddescribe your use, creation and manipulation of data structures used in the assignment as well asyour through process as you sent about solving the problem. 

Solution: 

packageosp.Threads;

importjava.util.Vector;

importjava.util.Enumeration;

importosp.Utilities.*;

importosp.IFLModules.*;

importosp.Tasks.*;

importosp.EventEngine.*;

importosp.Hardware.*;

importosp.Devices.*;

importosp.Memory.*;

importosp.Resources.*;

import java.io.*;

/**

This class is responsible for actions related to threads, including

creating, killing, dispatching, resuming, and suspending threads.

This class uses a shortest job remaining method for dispatching threads.

@OSPProject Threads

*/

public class ThreadCB extends IflThreadCB

{

/**

The thread constructor. Must call

super();

as its first statement.

@OSPProject Threads

*/

publicThreadCB()

{

super();

}

private static GenericListreadyQueue;

privateintlastCpuBurst = 10;

privateintestimatedBurstTime =10;

private long lastDispatch = 0;

//qunatum is the number of ticks used for RR scheduling

final static int MINBURST = 5;

/**

This method will be called once at the beginning of the

simulation. The student can set up static variables here.

@OSPProject Threads

*/

public static void init()

{

readyQueue  = new <ThreadCB>GenericList();

}

/**

Sets up a new thread and adds it to the given task.

The method must set the ready status

and attempt to add thread to task. If the latter fails

because there are already too many threads in this task,

so does this method, otherwise, the thread is appended

to the ready queue and dispatch() is called.

The priority of the thread can be set using the getPriority/setPriority

methods. However, OSP itself doesn’t care what the actual value of

the priority is. These methods are just provided in case priority

scheduling is required.

@return thread or null

@OSPProject Threads

*/

static public ThreadCBdo_create(TaskCB task)

{

//checks to make there is a task

if(task == null)

{

dispatch();

return null;

}

//checks to make sure the the task can have more threads

if(task.getThreadCount() == MaxThreadsPerTask)

{

dispatch();

return null;

}

//creats new thread sets priority and

//associates threads and tasks

ThreadCBnewThread = new ThreadCB();

newThread.setPriority(task.getPriority());

newThread.setTask(task);

newThread.setStatus(ThreadReady);

//checks to see if the task added the thread

if(task.addThread(newThread)== 0)

{

dispatch();

return null;

}

//if thread is created and added to the task add to the

//ready queue

readyQueue.append(newThread);

dispatch();

returnnewThread;

}

/**

Kills the specified thread.

The status must be set to ThreadKill, the thread must be

removed from the task’s list of threads and its pending IORBs

must be purged from all device queues.

If some thread was on the ready queue, it must removed, if the

thread was running, the processor becomes idle, and dispatch()

must be called to resume a waiting thread.

@OSPProject Threads

*/

public void do_kill()

{

//if the thread is ready remove it from the ready queue

if(this.getStatus() == ThreadReady)

{

readyQueue.remove(this);

}

//if the thread is running set it to wait to die mwhahaha

if(this.getStatus() == ThreadRunning)

{

context_switch(ThreadWaiting);

}

//disaccociate the task and thread then set the thread status

//to kill

TaskCB task = this.getTask();

task.removeThread(this);

this.setStatus(ThreadKill);

//remove all threads waiting for IO devices from waiting queues

for(int i = 0 ; i <Device.getTableSize(); i++)

{

Device.get(i).cancelPendingIO(this);

}

ResourceCB.giveupResources(this);

//kill any task with no threads left

if(task.getThreadCount() == 0)

{

task.kill();

}

dispatch();

}

/** Suspends the thread that is currenly on the processor on the

specified event.

Note that the thread being suspended doesn’t need to be

running. It can also be waiting for completion of a pagefault

and be suspended on the IORB that is bringing the page in.

Thread’s status must be changed to ThreadWaiting or higher,

the processor set to idle, the thread must be in the right

waiting queue, and dispatch() must be called to give CPU

control to some other thread.

@param event – event on which to suspend this thread.

@OSPProject Threads

*/

public void do_suspend(Event event)

{

//if the thread is running set the status to wait

if(this.getStatus() == ThreadRunning)

{

context_switch(ThreadWaiting);

}

//if the thread is waiting increase the satus by one

else if(this.getStatus()>=ThreadWaiting)

{

this.setStatus(this.getStatus()+1);

}

//make sure the thread isn’t in the ready queue and adds

//thread to the event queue

readyQueue.remove(this);

event.addThread(this);

dispatch();

}

/** Resumes the thread.

Only a thread with the status ThreadWaiting or higher

can be resumed.  The status must be set to ThreadReady or

decremented, respectively.

A ready thread should be placed on the ready queue.

@OSPProject Threads

*/

public void do_resume()

{

//skips this method if the thread is not waiting

if(this.getStatus() <ThreadWaiting)

{

return;

}

//if the thread is waiting set to ready

if(this.getStatus() == ThreadWaiting)

{

this.setStatus(ThreadReady);

}

//decrease the amount of waiting by one

else if(this.getStatus() >ThreadWaiting)

{

this.setStatus(this.getStatus() – 1);

}

//if the thread was set to ready put it back in the ready queue

if(this.getStatus() == ThreadReady)

{

readyQueue.append(this);

}

dispatch();

}

/**

Selects a thread from the run queue and dispatches it.

If there is just one theread ready to run, reschedule the thread

currently on the processor.

In addition to setting the correct thread status it must

update the PTBR.

@return SUCCESS or FAILURE

@OSPProject Threads

*/

public static intdo_dispatch()

{

ThreadCBcompThread;

//removes the currently running thread if there is one

if(MMU.getPTBR() != null)

{

boolean preempt = false;

ThreadCBrunningThread = MMU.getPTBR().getTask().getCurrentThread();

TaskCB task = MMU.getPTBR().getTask();

intremainingTime =(int) (HClock.get() – runningThread.getLastDispatch());

remainingTime = runningThread.getBurstTime() – remainingTime;

//check for the shortest job if this is the current job keep going and return

//success or if the current has less than 2 milliseconds keep going

if(remainingTime< 2)

{

return SUCCESS;

}

//if there was a shorter job find it and give it control of cpu

Enumeration itr = readyQueue.forwardIterator();

while(itr.hasMoreElements())

{

compThread = (ThreadCB) itr.nextElement();

if(compThread.getBurstTime() <remainingTime)

{

preempt = true;

break;

}

}

if(!preempt)

{

return SUCCESS;

}

task.setCurrentThread(null);

runningThread.setStatus(ThreadReady);

MMU.setPTBR(null);

//update the cpu burst time used by the thread and use that to make estimate for the next run

runningThread.setCPUBurst((int) (HClock.get()-runningThread.getLastDispatch()));

runningThread.setBurstTime((int) (.75*runningThread.lastCpuBurst + .25*runningThread.getBurstTime()));

if(runningThread.estimatedBurstTime<MINBURST)

{

runningThread.estimatedBurstTime=MINBURST;

}

readyQueue.append(runningThread);

}

//if the ready queue is empty return that is failed to dispatch

if(readyQueue.isEmpty())

{

MMU.setPTBR(null);

return FAILURE;

}

//set the next thread in the ready queue to run

ThreadCBnextThread = (ThreadCB) readyQueue.getHead();

Enumeration itr = readyQueue.forwardIterator();

while(itr.hasMoreElements())

{

compThread = (ThreadCB) itr.nextElement();

if(compThread.getBurstTime() <nextThread.getBurstTime())

{

nextThread = compThread;

}

}

readyQueue.remove(nextThread);

ageing();

MMU.setPTBR(nextThread.getTask().getPageTable());

// for the shortest thread update the dispatch time  after giving the

// pagetable to the MMU

nextThread.getTask().setCurrentThread(nextThread);

nextThread.setStatus(ThreadRunning);

nextThread.setLastDispatch(HClock.get());

return SUCCESS;

}

/**

Called by OSP after printing an error message. The student can

insert code here to print various tables and data structures in

their state just after the error happened.  The body can be

left empty, if this feature is not used.

 

@OSPProject Threads

*/

public static void atError()

{

}

/** Called by OSP after printing a warning message. The student

can insert code here to print various tables and data

structures in their state just after the warning happened.

The body can be left empty, if this feature is not used.

 

@OSPProject Threads

*/

public static void atWarning()

{

// your code goes here

}

/**

@method context_switch(intthreadStatus)

this method sets the currently running thread to the input

status if set to ready add it back to the ready queue

 

@ Param: intthreadStatus set the status of the running thread

*/

public void context_switch(intthreadStatus)

{

//checks to see if there is a running thread

if(MMU.getPTBR() != null)

{

//if this thread is the running thread give up control of the cpu

//and change its status

ThreadCBrunningThread = MMU.getPTBR().getTask().getCurrentThread();

if(this == runningThread)

{

TaskCB task = MMU.getPTBR().getTask();

this.setStatus(threadStatus);

task.setCurrentThread(null);

MMU.setPTBR(null);

//update the cpu burst time used by the thread and use that to make estimate for the next run

this.lastCpuBurst=(int) (HClock.get()-this.lastDispatch);

this.estimatedBurstTime = (int) (.75*this.lastCpuBurst + .25*this.estimatedBurstTime);

if(this.estimatedBurstTime<MINBURST)

{

this.estimatedBurstTime =MINBURST;

}

if(this.getStatus() == ThreadReady)

{

readyQueue.append(runningThread);

}

}

}

}

/**

@method ageing

this method lowers the estimated burst time of a thread

in order to prevent starvation

*/

public static void ageing()

{

Enumeration itr = readyQueue.forwardIterator();

while(itr.hasMoreElements())

{

ThreadCBcompThread = (ThreadCB) itr.nextElement();

 

compThread.setBurstTime(compThread.getBurstTime()-1);

if(compThread.getBurstTime()<MINBURST)

{

compThread.setBurstTime(MINBURST);

}

}

}

/*****************************************************************************************

* Accessors and Mutators

**/

/**

@method public void setBurstTime(intburstTime)

this method sets estimated burst time based on the input passed

@ Param: int burst time the int that estimates the burst time

*/

public void setBurstTime(intburstTime)

{

this.estimatedBurstTime = burstTime;

}

/**

@method public void setCPUBurst(intCPUBurstTime)

this method sets the last cpu burst of the thread based on the value

passed to it

@ Param: intCPUBurstTime the value of the last cpu bur time

*/

public void setCPUBurst(intCPUBurstTime)

{

this.lastCpuBurst = CPUBurstTime;

}

/**

@method public void setLastDispatch(long lastDispatch)

this method sets lastDispatch to the time the thread was last dispatch

@ Param: long lastDispatch the time the thread was last dispatch

*/

public void setLastDispatch(long lastDispatch)

{

this.lastDispatch = lastDispatch;

}

/**

@method public void getBurstTime()

this method gets estimatedBurtTime the estimate for how long the thread

will to finish the task

@ Return: intestimatedBurtTime the estimate for how long the thread

will to finish the task

*/

publicintgetBurstTime()

{

returnthis.estimatedBurstTime;

}

/**

@method public void getCPUBUurst()

this method gets lastCpuBurst

@ Return: intlastCpuBurst the time the thread spent on the cpu

*/

publicintgetCPUBurst()

{

returnthis.lastCpuBurst;

}

/**

@method public void getLastDispatch()

this method gets lastDispatch the time the thread was last dispatch

@ Return: long lastDispatch the time the thread was last dispatch

*/

public long getLastDispatch()

{

returnthis.lastDispatch;

}

}

/*

Feel free to add local classes to improve the readability of your code

*/