CPU Scheduling

3 minute read

This is a project that I worked on for my Operating Systems class at college.  Our objective was to create a CPU Scheduling Algorithm simulator (for 6 different scheduling algorithms) and display the results in a nice graph format.  We were told to generate 500 random processes with 3 randomly generated values for the priority, burst time and arrival time.  I created a custom object to store these values, and then I created a custom Data Structure to hold these process as we needed to 10 sets of processes for each Algorithm.  Designing and building each algorithm really made me understand each one (which was after all the point of the project) and this part of the project kept me busy for about a week or so.  Then the challenging part came along and that was to build a interface to display the results.  I was itching to use a free Java Charting component called JFreeChart, the geek in me looked forward to using this library and started reading the JavaDoc’s and any other documentation to begin building the interface.  

Comparison (First Tab)

The first tab in the application allows you to compare the performance for each of the algorithms.  This was a major requirement for this project, but luckly for me my design of the application allowed me to implement this pretty quickly and easily.  One neat thing about this is the fact that the chart showing the results  change based when the user selects the appropriate citeria (i.e. avg. turnaround time, avg. waiting time, avg. response time, throughput,  and cpu %).

Comparison

First Come First Served

This is the simplest of all algorithms (and as a result, the easiest to implement).  The idea is basic in that as each process comes into the queue, and it’s given access to the CPU it will not release the cpu time until it’s done.  Other processes that come after it must wait until the current process is done.

First Come First Served

Shortest Job Next

This alrogithm is a bit more involved in that as a process comes in to the queue, the cpu starts to exectue it but if another process comes in and it has a shorter burst time then the current process executed is stopped and the shortest burst time process is then given CPU time.  This process continues until all processes have been completed.

Shortest Job First

Shortest Remaining Job Next

And even tricker algorithm in that it’s similar to the previous one but as processes accumulated (in the waiting state) the next process to execute must be the one that has the least amount of burst time.  The tricky part about this is designing such an algorithm but I was able to do it after careful thought and design.

Shortest Remaining Job Next

Non-Premptive Priority

Processes with higher priorities are executed first.  Those with a lower priority must wait for those with higher priorities to finish.  This is a non-preemptive algorithm in that as soon as each process is given CPU time, the process won’t release the CPU until it’s done.

Non-Preemptive Priority

Pre-emptive Priority

Similar to the algorithm above, but with pre-emptiveness.  This means that if a process is currently running and a newer process arrives in the queue that has a higher priority than the current one, the cpu is given to this new higher priority process.

Preemptive Priority

Round Robin

This was by far the most challenging and fun algorithm to code.  I had to devise a few data structures to keep track of the results for each result set.  Building the gui was also fun because it’s dynamic nature.  I wanted to allow the user to see the results of each data set by just simply selecting the data set from a drop down list.

Round Robin