Solved

Simulating CPU Scheduling

Posted on 2003-12-04
4
2,102 Views
Last Modified: 2012-05-04
I am attempting to write a program that simulates the First Come First Serve, Shortest Job Next, and Shortest Remaining Time scheduling algorithms.  For each algorithm I want to print, in the order of completion, the finishing time, wait time, and turnaround time for each process.  I am also going to display the average waiting and turnaround times for each algorithm.

The number of processes, arrival time, and CPU time is gathered from the user.  The arrival time and CPU time is stored into a two dimensional array.

I have the FCFS algorithm coded and working, but am having problems figuring out an algorithm for the SRT and SJN.  Any help would be appreciated.
0
Comment
Question by:sscrowell
  • 2
4 Comments
 
LVL 4

Expert Comment

by:dhyanesh
ID: 9879950
Hi

Shortest Job Next :
------------------------

This a non preemptive algorithm. You have to maintain a queue of jobs as they arrive in time. When a job arrives it should be placed in the queue or array whatever you use in a sorted order. The jobs will be stored in ascending order of CPU time required for the job.

Then as a job is over the first job in the array is picked and executed. However just before this check for an incoming job at the same time first and put it in array in sorted order first. Then only take the first job from the queue.

Dhyanesh
0
 
LVL 4

Expert Comment

by:dhyanesh
ID: 9879984
Shortest Remaining Time :
---------------------------------

This is a pre-emptive algorithm. It is similar to shortest job next algorithm. In this again you maintain a queue or array in sorted order. However the only difference is that when a job arrives say having CPU time 't1' and the job currently executing has CPU time 't2' REMAINING i.e. it requires 't2' time to complete.

Now if t1<t2 then the job currently executing is removed from CPU and newly arrived job starts executing. The removed job is placed in sorted order in the queue.

However if t1>=t2 then the newly arrived job is simply put in sorted order in the queue as in Shortest Job Next.

Dhyanesh
0
 
LVL 40

Accepted Solution

by:
Kyle Abrahams earned 500 total points
ID: 9885258
pseudo code:

SJN();
while ( no_jobs() == false)
{
  sort_job_list_by_time();

   do
  {
    job();
  } while (job_not_finished() == true);

}

SRT:

while (no_jobs()==false)
{
   sort_job_list_by_time();
   job(); //ONLY 1 TICK
}

When I was doing this I used a vector, and used jobs[0] as the one to be executed by the CPU.    The difference between SRT and SJN is that SRT will re-sort everytime, while SJN will wait until the job is completed, get the next one, and then continue.  Hope this helps.

 
0
 
LVL 5

Expert Comment

by:migoEX
ID: 10443432
No comment has been added lately, so it's time to clean up this TA.
I will leave a recommendation in the Cleanup topic area that this question is:

Accept dhyanesh's comment as answer.

Please leave any comments here within the next four days.

PLEASE DO NOT ACCEPT THIS COMMENT AS AN ANSWER!

migoEX
EE Cleanup Volunteer
0

Featured Post

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Unlike C#, C++ doesn't have native support for sealing classes (so they cannot be sub-classed). At the cost of a virtual base class pointer it is possible to implement a pseudo sealing mechanism The trick is to virtually inherit from a base class…
This article will show you some of the more useful Standard Template Library (STL) algorithms through the use of working examples.  You will learn about how these algorithms fit into the STL architecture, how they work with STL containers, and why t…
The viewer will learn additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.
The viewer will be introduced to the technique of using vectors in C++. The video will cover how to define a vector, store values in the vector and retrieve data from the values stored in the vector.

920 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

15 Experts available now in Live!

Get 1:1 Help Now